[GHC] #4143: Data.Set can overflow Int on balance check

[GHC]

#4143: Data.Set can overflow Int on balance check
---------------------------------+------------------------------------------
    Reporter:  japple            |       Owner:                      
        Type:  bug               |      Status:  new                 
    Priority:  normal            |   Component:  libraries (other)   
     Version:  6.12.2            |    Keywords:  containers, overflow
          Os:  Unknown/Multiple  |    Testcase:                      
Architecture:  Unknown/Multiple  |     Failure:  Runtime crash       
---------------------------------+------------------------------------------
 Data.Set uses Ints to track tree sizes. Rotation decisions, however, are
 made based on multiples of tree sizes. Tree sizes substantially less than
 the maxBound of Int can trigger run time exceptions.

 The attached files are as follows:

   * local-set.patch -- Apply this to Set.hs, then compile & run SetBug.hs.
 This patch changes the word size to 16 bits so it can be tested on 32-bit
 machines without using a huge portion of the RAM
   * SetBug.hs -- builds a set with maxBound/2 + 1 elements in such a way
 that tree rotation causes a run time error. I suspect there are other ways
 of building a set that can trigger this error even for sets of size
 maxBound/4+1.
   * fixed-set.patch -- changes rotation tests to use Integers to prevent
 overflow.

-- 
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4143>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler