Software Testing Blog

Why does my enumerator not advance?

Here’s an interesting bug pattern that I am occasionally asked about, involving iteration over a collection that appears to not move forwards. Before we get into that though I’ll need to introduce a little helper method:

static void Apply<T>(Action<T> action, T item)
{
  action(item);
}

The behaviour of this method is utterly trivial: it takes an action and a value and performs the action on the value. You might think that this is a ridiculous method; after all, if you have an action and an item in hand then why not simply call action(item) rather than going through the unnecessary rigamarole of Apply(action, item)? But clearly this method is neither more nor less than simply adding a layer of indirection around the invocation. The reason for this indirection will become apparent later.

Right, now that we’ve got that out of the way, let’s take a look at our bug. We make a list and its enumerator. We advance the enumerator from its starting position, which is before the first element, to the first element. And then we print out that first element:

var list = new List<int> { 10, 20, 30 };
var enumerator = list.GetEnumerator();
enumerator.MoveNext();
Console.WriteLine(enumerator.Current);

This prints 10, as you’d expect. Sharp-eyed readers will have noted that normally you’d check to see if MoveNext() returns false before checking Current, but since I know that this collection has three elements, I’ve omitted that code for the sake of brevity.

Now let’s add a couple more lines at the end there:

Apply(e => { e.MoveNext(); }, enumerator);
Console.WriteLine(enumerator.Current);

When we append those lines to our previous fragment, what is the output of the new code? If you guessed 20, you are WRONG WRONG WRONG. It prints out 10 again! This seems impossible; the MoveNext is running and all we have done is inserted what we’ve already said is a clearly pointless layer of indirection that has no actual effect on the action of the program. Before you read on, see if you can figure out what is going on here. I’ve led you astray somewhere.

.
.
.
.
.
.
.
.
.
.

Did you work it out? Here, let me help you by rewriting the code to state every type inferred by the compiler:

List<int> list = new List<int> { 10, 20, 30 };
List<int>.Enumerator enumerator = list.GetEnumerator();
enumerator.MoveNext();
Console.WriteLine(enumerator.Current);
Apply<List<int>.Enumerator>(
  (List<int>.Enumerator e) => { e.MoveNext(); }, enumerator);
Console.WriteLine(enumerator.Current);

Did you expect the compiler to infer that GetEnumerator returns an IEnumerator<int>? It does not; List<T> explicitly implements IEnumerable<T>.GetEnumerator() and provides a public method with a different signature that returns a mutable value type.

Since value types are by definition copied by value what happens is the call to Apply makes a copy of the enumerator, and then when the delegate is invoked a second copy is made. The delegate mutates the second copy, and discards the mutated enumerator. Had the enumerator variable been a class type in the first place, or had it been boxed to IEnumerator<int> then the mutation would not have been lost.

Long-time readers of my blogs will know that “clearly” is a clear sign that some unwarranted assumption is being made, and today is no different. I said clearly this method is neither more nor less than simply adding a layer of indirection around the invocation, which is true for reference types and immutable value types, but is not true at all for mutable value types. In order to be true for mutable value types we need to make an Apply method that takes a ref T in both the action and the item. item then becomes an alias for enumerator rather than a copy.

Long-time readers will also know that I consider mutable value types to be enough pure concentrated evil to turn you all into hermit crabs. Why then did the designers of the base class library choose to make the iterator of a list be a mutable value type? For an answer to that question, see my 2011 article on that subject.


As always, if you have questions about a bug you’ve found in a C, C++, C# or Java program that you think would make a good episode of ATBG, please send your question along with a small reproducer of the problem to TheBugGuys@Coverity.com. We cannot promise to answer every question or solve every problem, but we’ll take a selection of the best questions that we can answer and address them on the dev testing blog every couple of weeks.

  1. So the most surprising thing here is that the behavior of this program changes when you change either of these lines:

    var list = new List { 10, 20, 30 };

    to

    IList list = new List { 10, 20, 30 };

    or

    var enumerator = list.GetEnumerator();

    to

    IEnumerator enumerator = list.GetEnumerator();

    I think that strongly suggests that it should be at least a warnable offence to hide – or even overload – a method in a way that might cause the semantics of its return type to change from value to reference, or vice versa, depending on the type interface used to access it or the types of the arguments used to call it.

  2. In your linked blog entry, you have a sentence which reads: “In this case the design team who built iterators for lists did experiments and determined that the risks of using immutable structs were worth the measurable performance gains.” Do you not mean mutable structs there since that’s what was being discussed beforehand?

  3. Hi,

    I learned a couple of things that I had not been aware so far.
    And made me thinking.

    Although I think your statement: “… provides a public method with a different signature that returns a mutable value type.” isn’t quite right since the signature does not include the return type:

    http://msdn.microsoft.com/en-us/library/aa691131(v=vs.71).aspx

    Which, I think, classifies explicitly implemented methods also as evil or rather methods that have the same signature but are not interface methods like List.GetEnumerator.

    Also the behaviour of the sample program changes if you change the type to IList or IEnumerable.

    Lastly the post ‘Following the pattern’ doesn’t quite explain the rationale
    for the List.Enumerator List.GetEnumerator().

    Cheers,
    Stefan

  4. Similar things happen when you put the Enumerator into a using-statement, arguably a bug, but following will result in an infinite loop:

    var list = new List { 10, 20, 30 };
    using(var iter = list.GetEnumerator())
    while(iter.MoveNext())
    yield return iter.Current;

    Removing the variable declaration from the using statement is enough to make it work, though:

    var list = new List { 10, 20, 30 };
    List.Enumerator iter;
    using(iter = list.GetEnumerator())
    while(iter.MoveNext())
    yield return iter.Current;

  5. One thing I have long wished for would be a means of tagging via attribute methods which should not be invokable upon read-only struct instances (method parameters which are not marked to indicate that they’re intended to be used as initialized temporary variables should probably be considered “immutable” for such purposes). Rather than complain that struct methods which modify `this` are “evil” because compilers will silently generate bogus code when they’re used inappropriately, it would be more helpful to allow those methods to specify that certain uses are inappropriate.

    Another thing that would have been helpful, though I’m not sure adding it now would help much, would have been to make C#’s “duck-typed” foreach look for a method called `GetForEachEnumerator` before trying `GetEnumerator`. The former method would have no obligation to implement `IEnumerator`, while the latter would have little reason to use anything other than `IEnumerator` as its return type [note that casting the return value from `List.GetEnumerator` to `IEnumerable` will cause it to behave with class-type semantics; the fact that it's a struct won't affect anything *except* with code that stores it in struct-type storage locations]

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Current day month ye@r *