Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005349OCamlOCaml generalpublic2011-08-26 16:352012-09-25 20:07
ReporterJulien Signoles 
Assigned Toxleroy 
PrioritynormalSeverityminorReproducibilityalways
StatusclosedResolutionfixed 
PlatformOSOS Version
Product Version3.12.1 
Target VersionFixed in Version3.13.0+dev 
Summary0005349: Hashtbl.replace is incorrect according to its specification
DescriptionThe 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 ReproduceJust 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 InformationHere 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
TagsNo tags attached.
Attached Files

- Relationships

-  Notes
(0006115)
xleroy (administrator)
2011-09-06 16:25

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.
(0006130)
xleroy (administrator)
2011-09-18 11:41

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

- Issue History
Date Modified Username Field Change
2011-08-26 16:35 Julien Signoles New Issue
2011-09-06 16:25 xleroy Note Added: 0006115
2011-09-06 16:25 xleroy Status new => acknowledged
2011-09-18 11:41 xleroy Note Added: 0006130
2011-09-18 11:41 xleroy Assigned To => xleroy
2011-09-18 11:41 xleroy Status acknowledged => resolved
2011-09-18 11:41 xleroy Resolution open => fixed
2011-09-18 11:41 xleroy Fixed in Version => 3.13.0+dev
2012-09-25 20:07 xleroy Status resolved => closed


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker