Set.map does not work reliably

[vicuna]

Original bug ID: 7403
Reporter: talex
Assigned to: @gasche
Status: resolved (set by @gasche on 2016-11-07T19:34:09Z)
Resolution: fixed
Priority: normal
Severity: major
Version: 4.04.0
Fixed in version: 4.04.1+dev
Category: standard library

Bug description

There seems to be a bug in the new Set.map in 4.04.

I think perhaps the two v variables here should be v':

ocaml/stdlib/set.ml

Line 387 in d27c578

if (l' = Empty || Ord.compare (max_elt l') v < 0)

Steps to reproduce

module S = Set.Make(String)

let f = function
| "b" -> "z"
| x -> x

let () =
let a = S.of_list ["b"; "a"; "c"] in
let b = S.map f a in
print_endline "Elements of b:";
S.iter (Printf.printf "- %s\n") b;
let b_has x =
Printf.printf "%S in b = %b\n" x (S.mem x b) in
List.iter b_has ["a"; "b"; "c"; "z"]

Produces:

Elements of b:

• a
• z
• c
  "a" in b = true
  "b" in b = false
  "c" in b = false
  "z" in b = true

[vicuna]

Comment author: @gasche

Ouch, I'm to blame on that one... The code was too clever for its own good.

Could you submit a pull-request with a testsuite regression test?

[vicuna]

Comment author: @gasche

I will write the pull-request and regression test. I hope that we can put the fix as an opam patch, and warn the packagers, so that users are not too affected -- I think it would make sense to wait a bit more to consider a 4.04.1 bugfix release, given that other issues may be encountered as 4.04.0 adoption progresses.

[vicuna]

Comment author: @gasche

#894

[vicuna]

Comment author: @gasche

Fixed in the 4.04 branch -- will cherry-pick in trunk.