Data.Sequence does not check for `Int` overflow about containers HOT 5 OPEN

One request: since this will be a somewhat invasive fix, I'd like to have enough time to finish the digit size experiment first, to avoid a difficult merge.

from containers.

The Word is Haskell 2010, so why not.

Nevertheless, I am not sure that performing run-time checks is the right way to go (because of efficiency). Another way to tacke this could be using Word64 and specifying that all representable sequences can have at most 2^64 elements. Wait -- that would mean that the index type would be Word64, which is a big API change.

This also casts shadow on the Word size -- does it mean the index will use Word as index type? If so, I think it is not worth it.

from containers.

Word64 is pretty bad in 32-bit code, and also could be quite bad for an implementation using pointer tagging, so I don't think we want that. index isn't a big deal. That can stay as it is and get converted to a Word. There just might be elements that can't be reached by index. It might pay to add a Word-based indexing function alongside. About the same thing goes for length, except that in this case the length function would have to check the range.

Yes, you could "solve" the range problem for repeated appends by specifying that it's prohibited, but silently giving wrong answers when someone does something wrong doesn't really seem like the Haskell way. Most people seem to think such runtime checks usually get predicted correctly and have minimal cost, but some benchmarks would be required to see.

from containers.

If index is using Int on the outside, I am not sure whether it is worth it changing the internal representation to Word, as the observable size type will still be Int. Thit probably applies to length even more.

I understand that silent bugs and failures are very bad. I am just not sure what the overhead will be, so as you say, we should look at the benchmarks. BTW, note that similar silent failures will happen with Map and Set larger than Int -- the Int size field will overflow, causing rotations to stop working correctly, cause wrong results of size, elemAt etc. With the Map and Set, we are neverless reasonably sure that such large structures will not exist (as creating such structures requires a huge amount of memory), which is not the case for replicate.

from containers.

I think you may (sadly) be right about the Word thing. But I also realized that a 32-bit implementation using tagging could have a problem using Int for sizes. Just something to keep in mind; not necessarily something to do anything about right now.

The overflow tests should be cheap under GHC, I believe, as I believe it offers primops giving access to hardware overflow flags. But yes, benchmarking required.

from containers.