`IntMap` `isProperSubmapOfBy` test failure

[konsumlamm]

I got the following test failure for isProperSubmapOfBy in intmap-properties:

  isProperSubmapOfBy:                    FAIL
    *** Failed! Falsified (after 4 tests and 11 shrinks):
    {_->True}
    fromList [(-3,1),(-1,1)]
    fromList [(-3,1),(-1,1),(0,1)]
    False /= True
    Use --quickcheck-replay=905941 to reproduce.
    Use -p '$0=="intmap-properties.isProperSubmapOfBy"' to rerun this test only.

[meooow25]

This is a bug in isProperSubmapOfBy.

https://github.com/haskell/containers/blob/c651094ec026b90c4e9d4ed81bc15eb337d3fc2e/containers/src/Data/IntMap/Internal.hs#L2370-L2371

When the first tree is in the left/right child of the second tree, and the first tree and the left/right child compare equal, the EQ should be updated to LT since it's a proper submap.

I tried to trace the source of the error and looks like it has been there since the commit which introduced IntMap bbbba97cbcf12039810533e3a2daf2eefdefe7f0.

[jwaldmann]

whoa, indeed.

when translating the textual description to a property, with leancheck I get

ghci> checkFor 100000 $ \ f a b -> I.isProperSubmapOfBy f a b == (S.isProperSubsetOf  (I.keysSet a ) (I.keysSet b) && and (I.intersectionWith f a b))
*** Failed! Falsifiable (after 4652 tests):
(\_ _ -> True) (fromList [(0,()),(1,())]) (fromList [(-1,()),(0,()),(1,())])

Also,

ghci> I.isProperSubmapOf (I.fromList [(0,()),(1,())]) (I.fromList [(-1,()),(0,()),(1,())])
False

[meooow25]

This bug was fixed for IntSet in 71fe15fec4da46f3f0ee51742fa6b5b338d88f98 GHC #1762. Unfortunately they missed IntMap.

[treeowl]

That's an incredibly old bug. Wow.