[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:  closed           
Priority:  normal                |      Component:  libraries (other)
 Version:  6.12.2                |     Resolution:  invalid          
Keywords:  containers, overflow  |             Os:  Unknown/Multiple 
Testcase:                        |   Architecture:  Unknown/Multiple 
 Failure:  Runtime crash         |  
---------------------------------+------------------------------------------

Comment(by japple):

 Let me just add that I don't ever calculate node sizes, so I can't vouch
 for that part of the calculation.

 Although I expect that this bug can't be triggered as things currently
 stand, I think it is a boobytrap for a few reasons. Each one of these
 seems unlikely, but given that there are a few of them, and that Edward
 worked out a possible way to check and correct the overflow without using
 Integers, (change the '*' to a `div` on the other side) I think this issue
 may still be worth looking over. Possible ways it could pop up in the
 future:

  * Data.Set gets some more space-efficient construction functions like
 "replicate" in Data.Seq
  * The constants for bounding balance increase dramatically
  * The Bin constructor is made lazy in its children

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