Serious typo in IntMap.hs

[sedillard]

Someone has recently (since 6.8.3) taken a "style" pass over IntMap.hs. Apparently they didn't like reusing identifiers in different scopes, so they changed this function (at the very core of IntMap) from this

highestBitMask :: Nat -> Nat
highestBitMask x
  = case (x .|. shiftRL x 1) of 
     x -> case (x .|. shiftRL x 2) of 
      x -> case (x .|. shiftRL x 4) of 
       x -> case (x .|. shiftRL x 8) of 
        x -> case (x .|. shiftRL x 16) of 
         x -> case (x .|. shiftRL x 32) of   -- for 64 bit platforms
          x -> (x `xor` (shiftRL x 1))

to this

highestBitMask :: Nat -> Nat
highestBitMask x0
  = case (x0 .|. shiftRL x0 1) of
     x1 -> case (x1 .|. shiftRL x1 2) of
      x2 -> case (x2 .|. shiftRL x2 4) of
       x3 -> case (x3 .|. shiftRL x3 8) of
        x4 -> case (x3 .|. shiftRL x4 16) of
         x5 -> case (x4 .|. shiftRL x5 32) of   -- for 64 bit platforms
          x6 -> (x6 `xor` (shiftRL x6 1))

If you stare at it long enough, you might find the typo. Don't cheat and look at the patch. I'll give you a hint: quickcheck won't find it because the tests don't use big enough integers.

Needless to say this completely breaks the library, and if it ain't broke... :)

[nominolo]

I presume this was changed in order to avoid warnings (many of the core libraries are not -Wall clean yet). Good catch.

[sedillard]

Oh, my mistake. I'm not familiar with the types of things -Wall warns abouts. TBH I don't use it. Now I'll have to get in the habit. I hope I didn't come off as smug.

[malcolm.wallace@…]

No need to apologise. The fact that someone introduced a new bug, by changing the code to remove a -Wall warning, is a salutary lesson in the danger of trusting a mechanical warning system to tell you about real problems.

[dons]

How about adding a QuickCheck property that can distinguish the error, so it can't happen again.

[sedillard]

Improved Arbitrary instances for IntMap / IntSet

[sedillard]

The properties are fine. (Well, each one on its own is fine. Together they don't cover the entire library, but that's another issue.) The problem was that the default Arbitrary instance for Int generates small numbers, so building on top of that we get trees filled with small numbers. I've changed the Arbitrary instance for IntMap / IntSet to flip random bits before building the tree.

[igloo]

Like others have said, good spot; thanks! I've applied your patch to HEAD and 6.10.