Can be logic around `List<T>.Enumerator._version` considered control flow exploitation?

Question

List<T>.Enumerator “snapshots” list version upon creation by _version = list._version;. This allows enumerator to halt enumeration when List<T> changed during it.

This behavior likely originates from need to move what is hidden under foreach statement into forefront while in obedience to contract (for each).

foreach(var i in numbers)
{
  if (i > 3)
    numbers.Remove(i);
}

After removal item order is shifted to left. If there is no versioning, then enumeration can continue on the 2nd next item. By this chance versioning seems fine.

In contrast

var enumerator = numbers.GetEnumerator();
while (enumerator.MoveNext())
{
  var i = enumerator.Current;
  if (i > 3)
    numbers.Remove(i);
}

does not have for each contract. Now it is just decision of List<T>.Enumerator to be exhaustive making sure it is.

Let consult Sort method

public void Sort() => Sort(0, Count, null);
public void Sort(int index, int count, IComparer<T>? comparer)
{
   … // Some code omitted. Code bellow differently formatted.   

  if (count > 1)
    Array.Sort<T>(_items, index, count, comparer);

  _version++;
}

I think, I wonder who would ever do

foreach(var i in numbers)
{
  if (some condition)
    numbers.Sort();
}

Similar applies to Reverse.

public void Reverse() => Reverse(0, Count);
public void Reverse(int index, int count)
{
    … // Some code omitted. Code bellow differently formatted.

  if (count > 1)  
    Array.Reverse(_items, index, count);
            
  _version++;
}

On other hand

foreach(var i in numbers)
{
  if (i % 3)
    numbers.Reverse();
}

I expect could produce nice series but I am not mathematician.

This count there are some points from which List<T>.Enumerator can be viewed:

1. It is exhaustive as feature and negative impact on List<T> and enumerator performance should be consumed as levy.
2. It is exhaustive as safeguard. Versioning in this case substitutes analyzer function that helps developers to avoid items miss or repeating them during enumeration due items shift. For this point penalties are debatable.
3. List<T> exhibits wastrel implementation.

• Versioning addresses truly only cases that causes left/right items shift copy – removal, insertion.
• Version is also handled for Reverse, Sort but what scenario allows for accidental such change during enumeration? I guess none.
• Version is handled in methods: T this [int index] set – there it can make sense but I doubt anyone would ever expect previous value when it is deliberately replaced at exact index; Add – adds to end and enumerator perfectly can work with this (relying on size), no need for version; Clear – affects enumeration but in safe way, check against size is sufficient; EnsureCapacity – I do not get how this can threat enumeration; Insert – avoids items repetition; InsertRange – avoids items miss and repetition, RemoveAll, RemoveAt, RemoveRange – avoids items miss
• If so then, in total, this most likely means that some methods could be freed from versioning by virtue of common sense and/or low probability of misuse while for shifting ones this counts still debatable.

Worth noting that _version is not protected against overflow. That it turn draws back to point 2. If versioning should serve run-time, should it be overflow protected? Likely.

It seems so List<T> versioning was designed in order to serve development (time) and there could be provided analyzers, checking shifting methods inside loops. Exception cannot go unnoticed, that is for sure. Also shift can occur outside the loop (method call).

Answer 1

So if there is change to List, there is in fact no threat to enumeration.

Yes there is. You might repeat an element, or skip it. Just because the index refers to an element doesn't mean the enumerator is valid.

What you've shown is that if you carefully craft a situation, you can trick one of the safety checks. You are staggeringly unlikely to come across this situation accidentally. It remains a beneficial check for the vast majority of uses.

List is not written to be immune to carefully crafted malice, but to be robust to ordinary situations.

Answer 2

OK so, my understanding of your code is that you alter the list 2 times max int number of times. Each change increments the int _version so that it loops over max int and goes to negative max int, then all the way back up to -1.

This breaks the internal check that _version should be equal to the expected _version when you change it one more time as its now equal when you have changed the list.

Congrats you found a bug!

But. Consider how you might eliminate this bug. If you just change it to long then you still have the same bug, just a higher number of changes. Its not a trivial problem to solve as you essentially have n possible versions of a list, with no real limit.

Should you prevent changes to a list which has reached your max? Should you invalidate linked enumerations when the underlying list changes?

We can only guess on the reasons why this way was chosen, you can see that all options have downsides. However! Given that _version is int and not uint, I have feeling this is just an oversight and it should be possible to implement a fix without major downsides.

Answer 3

As I see the case, there was no best one options for authors than to exploit control flow constructs in List<T> methods in order to preserve common contract of foreaching.

I mean mostly that not everyone needs help in ensuring something is valid/complete and that nobody ever said that enumeration has to be definitely exhaustive.

When this versioning caught sight of world should be that time accompanied with at least fast enumerator that does not check against version that could be consumed manually.

Or even better whole List<T> should have been provided with fast counterpart that does not version. (System.Collection.Performance)

It would be copy-paste-edit epsilon-zero-like implementation.