0005349: Hashtbl.replace is incorrect according to its specification

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0005349

OCaml

OCaml general

public

2011-08-26 16:35

2012-09-25 20:07

Reporter

Julien Signoles

Assigned To

xleroy

Priority

normal

Severity

minor

Reproducibility

always

Status

closed

Resolution

fixed

Platform

OS Version

Product Version

3.12.1

Target Version

Fixed in Version

3.13.0+dev

Summary

0005349: Hashtbl.replace is incorrect according to its specification

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

Tags

No 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