Possible bug in CCIntMap.union

[fpottier]

Hello!

This may or may not be a bug, depending on how union is expected to behave. (It currently has no documentation.)

When I call union f m1 m2, I would expect the function f to always be called with a call of the form f k v1 v2 where the value v1 comes from the map m1 and the value v2 comes from the map m2. However, the code does not respect this convention, and can actually issue calls of the form f k v2 v1 where the values are exchanged.

The following example illustrates this:

#require "containers-data";;
open CCIntMap;;

let minus m1 m2 =
  union (fun _key v1 v2 -> v1 - v2) m1 m2;;

let key = 0;;
let m0 = singleton key 1;;       (* a map of [key] to the value 1 *)
let m1 = minus m0 m0;;           (* a map of [key] to the value 0 *)
let m2 = minus m0 m1;;           (* a map of [key] to the value 1 *)
let observed = equal (=) m2 m0;; (* [m0] and [m2] should be equal *)
assert (observed = true);;       (* this fails, but I would expect it to succeed!  *)

Is this a bug? This depends on the specification of union. Does union require its argument f to be commutative? Does union guarantee that f is always applied to a value v1 from the map m1 and a value v2 from the map m2, in this order?

(Bug found by fuzzing with afl-fuzz and the monolith library.)

[c-cube]

Looking at the code, I see:

…
    | L (k, v), o
    | o, L (k, v) ->
      (* insert k, v into o *)
      insert_ (fun ~old v -> f k old v) k v o
…

which means that on leaf nodes it indeed can swap arguments to f. I think that's a bug, or at least too surprising to be a good behavior.

note that minus might still not behave like you want if a key is only in the right hand side, it will not negate it. You probably want to use merge for that :)

[fpottier]

Sure, minus is just an artificial example anyway.
Looking at the code, I think other functions (such as inter) might exhibit the same problem.

[c-cube]

Thanks for the report btw 🙂

I also updated inter.