List<T>.AddRange with erroneous input has inconsistent behavior

[theodorzoulias]

Description

Out of curiosity I experimented with the List<T>.AddRange method, by passing as argument a custom ICollection<T> implementation with maximum Count and no-op CopyTo. The behavior changes depending on the existing size of the list, and may result in a negative List<T>.Count value.

Reproduction Steps

Here is my custom ICollection<T>:

class MyCollection<T> : ICollection<T>
{
    public int Count => Int32.MaxValue;
    public void CopyTo(T[] array, int arrayIndex) { } // Do nothing

    public bool IsReadOnly => throw new NotImplementedException();
    public void Add(T item) => throw new NotImplementedException();
    public bool Remove(T item) => throw new NotImplementedException();
    public void Clear() => throw new NotImplementedException();
    public bool Contains(T item) => throw new NotImplementedException();
    public IEnumerator<T> GetEnumerator() => throw new NotImplementedException();
    IEnumerator IEnumerable.GetEnumerator() => throw new NotImplementedException();
}

Passing an instance to List<T>.AddRange I expected to get an exception of some kind, which is indeed what happens:

new List<int>().AddRange(new MyCollection<int>());

Output:

System.OutOfMemoryException: Array dimensions exceeded supported range.
   at System.Collections.Generic.List`1.set_Capacity(Int32 value)
   at System.Collections.Generic.List`1.Grow(Int32 capacity)
   at System.Collections.Generic.List`1.InsertRange(Int32 index, IEnumerable`1 collection)
   at System.Collections.Generic.List`1.AddRange(IEnumerable`1 collection)
   at Program.Main(String[] args) in C:\Projects\Console1\Program.cs:line 9

But if the list is not empty before the AddRange, then there is no exception:

List<int> list = new();
list.Add(1);
list.AddRange(new MyCollection<int>());
Console.WriteLine($"list.Count: {list.Count}, list.Capacity: {list.Capacity}");

Output:

list.Count: -2147483648, list.Capacity: 8

Online demo.

Configuration

• .NET 6.0
• Console application
• 64-bit operating system, x64-based processor

This is not a realistic scenario, since the MyCollection<T> is not correctly implemented, but nevertheless I thought I should report it.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

Out of curiosity I experimented with the List<T>.AddRange method, by passing as argument a custom ICollection<T> implementation with maximum Count and no-op CopyTo. The behavior changes depending on the existing size of the list, and may result in a negative List<T>.Count value.

Reproduction Steps

Here is my custom ICollection<T>:

class MyCollection<T> : ICollection<T>
{
    public int Count => Int32.MaxValue;
    public void CopyTo(T[] array, int arrayIndex) { } // Do nothing

    public bool IsReadOnly => throw new NotImplementedException();
    public void Add(T item) => throw new NotImplementedException();
    public bool Remove(T item) => throw new NotImplementedException();
    public void Clear() => throw new NotImplementedException();
    public bool Contains(T item) => throw new NotImplementedException();
    public IEnumerator<T> GetEnumerator() => throw new NotImplementedException();
    IEnumerator IEnumerable.GetEnumerator() => throw new NotImplementedException();
}

Passing an instance to List<T>.AddRange I expected to get an exception of some kind, which is indeed what happens:

new List<int>().AddRange(new MyCollection<int>());

Output:

System.OutOfMemoryException: Array dimensions exceeded supported range.

But if the list is not empty before the AddRange, then there is no exception:

List<int> list = new();
list.Add(1);
list.AddRange(new MyCollection<int>());
Console.WriteLine($"list.Count: {list.Count}");

Output:

list.Count: -2147483648

Online demo.

This is not a realistic scenario, since the MyCollection<T> is not correctly implemented, but nevertheless I thought I should report it.

Author:	theodorzoulias
Assignees:	-
Labels:	area-System.Collections, untriaged
Milestone:	-

[eiriktsarpalis]

Most BCL optimizations using ICollections.Count rely on the assumption that the returned value is consistent with the actual size of the enumeration, but clearly that's not always the case. I don't think we should be adding defensive checks to account for pathological implementations, but we might want to consider adding checked arithmetic when computing the new size:

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs

Line 257 in 315bdd4

Grow(_size + count);

Would you be interested in contributing a PR?

[theodorzoulias]

@eiriktsarpalis yea I don't think that it needs fixing either. Adding an arithmetic check that will slow down everyone's code, just for the sake of rewarding incorrect implementations with consistent behavior, doesn't seem a good trade off. I reported this discovery more as a curiosity than anything else. Feel free to close this issue if you want.

[jkotas]

This can be a very cheap check in Grow method. Silent integer overflows are dangerous. We should not be leaving them to sneak through.

[eiriktsarpalis]

@theodorzoulias would you be interested in contributing a fix?

[theodorzoulias]

@eiriktsarpalis no, sorry. I don't have the environment ready, so I could only submit non-tested code, which I would prefer not to do. :-)

[theodorzoulias]

Funnily enough I just found an answer in StackOverflow that uses a custom ICollection<T> similar to MyCollection<T>, during the construction of a List<T>. The intention of implementing the ICollection<T>.CopyTo as a no-op in that case, is to initialize cheaply a List<T> to a desirable size, with default(T) values. That collection is not used with the AddRange, so it's not directly related with this issue.