Contiguous* containers can't grow past 2^30 elements: `Grow` doubles into an overflow and `Add` throws `ArgumentException`

[matt-edmondson]

What's wrong

Grow is identical in ContiguousCollection.cs (~L425-436), ContiguousSet.cs (~L588-599) and ContiguousMap.cs (~L646-657):

int newCapacity = items.Length == 0 ? DefaultCapacity : items.Length * 2;
if (newCapacity < minimumCapacity) newCapacity = minimumCapacity;
T[] newItems = new T[newCapacity];
Array.Copy(items, newItems, Count);

At items.Length == 2^30, items.Length * 2 wraps to int.MinValue. That is below the default minimumCapacity of 0, so newCapacity becomes 0. A zero-length array is allocated, and Array.Copy throws ArgumentException: Destination array was not long enough.

List<T> handles the same situation by growing to Array.MaxLength. So a ContiguousCollection<byte> stops at 1,073,741,824 elements while the List<byte> it is benchmarked against keeps going.

ContiguousSet.Add (~L201-218) also calls uniquenessSet.Add(item) before Grow(). When Grow throws, the item ends up in the hash set but not in the array:

• Contains(item) returns true.
• Count and enumeration omit the item.
• A retried Add returns false.

This part was confirmed by reading the code; the growth failure below was reproduced.

Repro (verified, ~2 GB RAM)

List<byte> l = new(new byte[1 << 30]); l.Add(1);                 // ok
ContiguousCollection<byte> c = new(new byte[1 << 30]); c.Add(1); // ArgumentException, Count stays 2^30

Suggested fix

• Compute the doubled capacity in long (or uint) and clamp it to Array.MaxLength. When Count == Array.MaxLength, throw a clear OutOfMemoryException or InvalidOperationException.
• In ContiguousSet.Add, and for symmetry ContiguousMap.Add and the indexer, grow before touching the uniqueness index, or roll the index back if growth fails.

Acceptance criteria

• Growth past 2^30 either succeeds up to Array.MaxLength or fails with a clear exception.
• A failed growth leaves the container, including the set/map index, unchanged.

[matt-edmondson]

Triage

• Category: Bug
• Priority: Low. It only triggers at 2^30 elements, around 1 GB or more, which few consumers reach. The ContiguousSet.Add index desync after a failed grow is the more serious half, and it should be fixed in the same change.
• Area / suggested assignment: Grow in ContiguousCollection/ContiguousSet/ContiguousMap, plus the ordering in ContiguousSet.Add and ContiguousMap.Add.
• Duplicates: none. It is the same overflow family as RingBuffer, SpscRingBuffer and DelayLine throw an undocumented OverflowException for sizes above 2^30, and a failed RingBuffer.Resize corrupts the buffer #89 (ring buffers), and the two could land together.
• In progress: no open PR.

Suggested next step: compute the new capacity in long and clamp it to Array.MaxLength, matching List<T>. Grow before touching the uniqueness index.

---

Generated by Claude Code