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)
Change History (8)
Changed 11 years ago by
Attachment: | highestBitMask.patch added |
---|
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
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
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
How about adding a QuickCheck property that can distinguish the error, so it can't happen again.
Changed 11 years ago by
Attachment: | arbitrary.patch added |
---|
Improved Arbitrary instances for IntMap / IntSet
comment:5 Changed 11 years ago by
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
difficulty: | → Unknown |
---|---|
Milestone: | → 6.10.1 |
Resolution: | → fixed |
Status: | new → closed |
Version: | 6.8.3 → 6.9 |
Like others have said, good spot; thanks! I've applied your patch to HEAD and 6.10.
I presume this was changed in order to avoid warnings (many of the core libraries are not
-Wall
clean yet). Good catch.