Opened 11 years ago

Closed 11 years ago

#2647 closed bug (fixed)

Serious typo in IntMap.hs

Reported by: sedillard Owned by:
Priority: normal Milestone: 6.10.1
Component: libraries (other) Version: 6.9
Keywords: containers IntMap Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

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... :)

Attachments (2)

highestBitMask.patch (1011 bytes) - added by sedillard 11 years ago.
arbitrary.patch (2.2 KB) - added by sedillard 11 years ago.
Improved Arbitrary instances for IntMap / IntSet

Download all attachments as: .zip

Change History (8)

Changed 11 years ago by sedillard

Attachment: highestBitMask.patch added

comment:1 Changed 11 years ago by nominolo

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

comment:2 Changed 11 years ago by 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.

comment:3 Changed 11 years ago by 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.

comment:4 Changed 11 years ago by dons

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

Changed 11 years ago by sedillard

Attachment: arbitrary.patch added

Improved Arbitrary instances for IntMap / IntSet

comment:5 Changed 11 years ago by 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.

comment:6 Changed 11 years ago by igloo

difficulty: Unknown
Milestone: 6.10.1
Resolution: fixed
Status: newclosed
Version: 6.8.36.9

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

Note: See TracTickets for help on using tickets.