Data.Set can overflow Int on balance check
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.
Trac metadata
Trac field | Value |
---|---|
Version | 6.12.2 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | libraries (other) |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |