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

Closed
vicuna opened this issue Aug 26, 2011 · 2 comments
Closed

Hashtbl.replace is incorrect according to its specification #5349

vicuna opened this issue Aug 26, 2011 · 2 comments
Assignees
Labels

Comments

@vicuna
Copy link

vicuna 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.

=== h.ml ===
type name = { id: int; name: string }

module H =
Hashtbl.Make
(struct
type t = name
let equal x y = x.id = y.id
let hash x = Hashtbl.hash x.id
end)

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 k.name) 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 k.name) h

$ ocamlc -o h h.ml && ./h
foo
bar

Additional information

Here is an untested patch of hashtbl.ml against SVN revision 11173:

julien@is010215:~/ocaml-svn/trunk$ svn info
Path: .
URL: http://caml.inria.fr/svn/ocaml/trunk
Repository Root: http://caml.inria.fr/svn
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/hashtbl.ml
Index: stdlib/hashtbl.ml

--- stdlib/hashtbl.ml (revision 11173)
+++ stdlib/hashtbl.ml (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 = h.data.(i) in
@vicuna
Copy link
Author

vicuna 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.

@vicuna
Copy link
Author

vicuna 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants