Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Hashtbl.replace is incorrect according to its specification #5349

vicuna opened this issue Aug 26, 2011 · 2 comments


None yet
2 participants
Copy link

commented Aug 26, 2011

Original bug ID: 5349
Reporter: Julien Signoles
Assigned to: @xavierleroy
Status: closed (set by @xavierleroy on 2012-09-25T18:07:21Z)
Resolution: fixed
Priority: normal
Severity: minor
Version: 3.12.1
Fixed in version: 3.13.0+dev
Category: ~DO NOT USE (was: OCaml general)
Monitored by: mehdi "Pascal Cuoq"

Bug description

The specification of Hashtbl.replace says "This is functionally equivalent to Hashtbl.remove tbl x followed by Hashtbl.add tbl x y."

That is not true if there is a binding [x'] of [tbl] such that [equal x x' = true] but [(x = x') = false] (with [equal] being the equality used for comparing keys of the table).

Steps to reproduce

Just compile and run the following program. If Hashtbl.replace correctly implements its specification, then the printed lines would be the same.

=== ===
type name = { id: int; name: string }

module H =
type t = name
let equal x y = =
let hash x = Hashtbl.hash

let h = H.create 7
let n = { id = 0; name = "foo" }
let () = H.add h n ()
let () = H.replace h { n with name = "bar" } ()
let () = H.iter (fun k () -> print_endline h

(* same implementation, but replacing H.replace by H.remove followed by H.add *)
let h = H.create 7
let n = { id = 0; name = "foo" }
let () = H.add h n ()
let () = H.remove h { n with name = "bar" }
let () = H.add h { n with name = "bar" } ()
let () = H.iter (fun k () -> print_endline h

$ ocamlc -o h && ./h

Additional information

Here is an untested patch of against SVN revision 11173:

julien@is010215:~/ocaml-svn/trunk$ svn info
Path: .
Repository Root:
Repository UUID: f963ae5c-01c2-4b8c-9fe0-0dff7051ff02
Revision: 11173
Node Kind: directory
Schedule: normal
Last Changed Author: garrigue
Last Changed Rev: 11173
Last Changed Date: 2011-08-20 04:51:34 +0200 (sam., 20 août 2011)

julien@is010215:~/ocaml-svn/trunk$ svn diff stdlib/
Index: stdlib/

--- stdlib/ (revision 11173)
+++ stdlib/ (working copy)
@@ -131,7 +131,7 @@
raise Not_found
| Cons(k, i, next) ->
if compare k key = 0

  •    then Cons(k, info, next)
  •    then Cons(key, info, next)
       else Cons(k, i, replace_bucket next) in
    let i = key_index h key in
    let l = in

This comment has been minimized.

Copy link

commented Sep 6, 2011

Comment author: @xavierleroy

Well spotted, thanks. Does anyone see any practical reason to stick with the current behavior? Otherwise I'd rather change the implementation to conform to the documentation.


This comment has been minimized.

Copy link

commented Sep 18, 2011

Comment author: @xavierleroy

I went ahead and implemented proposed change in the SVN trunk. Will go in release 3.13 along with new hashtable implementation.

@vicuna vicuna closed this Sep 25, 2012

@vicuna vicuna added the bug label Mar 20, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.