C# internals: iterators

In my last post, we got familiar with the internals of string switch statement in C#. Today, we are going to deeply understand another language feature – iterators.

 

Iterators in C#

Despite the fact that iterators (using yield keyword) were introduced back in C# 2.0, many folks are still confused how they work. Honestly, I’m not surprised at all, because to me this mechanism was a mystery for a long time. Of course, we have to clearly distinguish two things here:

  • How does yield return work? (on C# level)
  • How does yield return actually work THIS way? (this is the topic of today’s article)

Let’s start with the first question. Asking a statistical C# developer, what’s the advantage of using yield return statement we could probably hear the following answer:

It allows you to return a sequence without initializing a collection

Yes, that’s one of the benefits. Let’s see an example to be sure that we are on the same page:

 


        public static IEnumerable<T> Where<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {
            var result = new List<T>();

            foreach(var s in source)
            {
                if(predicate(s))
                {
                    result.Add(s);
                }
            }

            return result;
        }

 

The above code is simplified implementation of Linq’s Where extension method. On the input, we have a collection of integers and a predicate that needs to be applied to each argument. On the output, filtered collection is returned. As you see, because yield keyword wasn’t present, I had to initialize a List<int> at the beginning of a method. Let’s see the second version of Where, but this time using yield keyword:

 

        public static IEnumerable<T> Where<T>(this IEnumerable<T> source, Func<T, bool> predicate)
        {

            foreach(var s in source)
            {
                if(predicate(s))
                {
                    yield return s;
                }
            }
        }

 

Indeed, this implementation does not initialize any list to return a filtered collection. In fact, yield keyword is very common in the actual implementation of Linq. If you want to check it, I encourage you once again to visit referencesource.microsoft.com 😉
The above example above presented just one (most popular) advantage of iterators. But there are at least two more that we should keep in mind:

  • Sequences returned by iterators are lazily evaluated since return type must be either IEnumerable or IEnumerator
  • Sequences returned by iterators can be infinite

These two are very powerful „side effects” and should not be forgotten when it comes to iterators. However, I’ll not put any examples since this is not a topic of the following article.

Ok, I assume that you more or less know how yield keyword works in C#. But here comes the weird part:

 


        public static void Main()
        {
            var sequence = GetSequence();

            sequence.MoveNext();
            Console.WriteLine(sequence.Current);

            sequence.MoveNext();
            Console.WriteLine(sequence.Current);

            sequence.MoveNext();
            Console.WriteLine(sequence.Current);

            Console.ReadLine();
        }

        public static IEnumerator<int> GetSequence()
        {
            var a = 3;

            Console.WriteLine("I'm inside iterator!");
            yield return 1;

            Console.WriteLine("I know where to resume the execution!");
            yield return 2;

            Console.WriteLine("I did it once again!");
            yield return a;
        }

 

In this code, I used IEnumerator<T> version of iterator just to iterate over the sequence „manually”. Notice two interesting things. Each time MoveNext method is called, a value of Current changes and next part of GetSequence method is processed. This looks like some sort of magic since program knows somehow where to resume execution of iterator method. This thing can be found on MSDN:

When a […] yield return statement is reached, the current location in code is remembered. Execution is restarted from that location the next time the iterator function is called.

Besides that GetSequence method contains a local variable whose lifetime is „bound” to the iterator’s stack frame. As soon as the stack frame is gone, a value of the variable should not be accessible. However, when we look at the code above, we can clearly spot that each time we invoke WritleLine method after MoveNext, we „destroy” stack frame but still, at the end of the method we can yield value of the local variable.

So, for a now we have two questions to answer:

  1. How do iterators remember the current location in code?
  2. How do iterators extend the lifetime of local variables?

 

Remembering the current location

To find out how this whole thing is implemented on the IL level, I’m going to use a dotPeek decompiler. The following code is the one generated for the last example:

 

Click to zoom

 

The Main method looks almost the same (except explicit IEnumerable<int> typing). But the interesting part starts inside GetSequence method. The whole body is gone and the instance of some weird type called d__1 is returned instead. It turns out that in fact, this weird thing is a state machine – a compiler’s secret which allows a program to keep the current state of iterator’s execution. Let’s look at the implementation.

As you see, the state machine implements three interfaces:

  • IEnumerable<int>
  • IEnumerable
  • IDisposable

This is quite obvious – since iterator returns IEnumerator<int> the d__1 type needs to implement this interface. Then we can see a declaration of three fields:

  • this.<>1_state – represents a current state of the state machine. Will be used to „jump into” right location in the code and resume the execution.
  • this.<>2_current – represent a current element of the sequence (sequence.Current)
  • this.<a>5__1 – represents local variable

Moving next we can see a constructor of the state machine which takes an initial state as a parameter. When we look at the GetSequence method, we can spot that by default this is set to 0:

 


return (IEnumerator<int>) new Program.<GetSequence>d__1(0);

 

We can also confirm that 0 is actually the initial state, by visiting Roslyn’s GitHub and navigating to StateMachineStates.cs:

 

    internal static class StateMachineStates
    {
        internal const int FinishedStateMachine = -2;
        internal const int NotStartedStateMachine = -1;
        internal const int FirstUnusedState = 0;
    }

 

Then we have a Dispose method which in this case is not implemented. We’ll get back to it later in this article.
Finally, we reach MoveNext method. This is indeed, the heart of state machine which contains switch statement. When you look closely you can spot something familiar – this is the implementation of the iterator method but „chopped” by yield keywords:

 

 

At this point I assume, you know how each state is determined. Let’s look at the structure of each one inside switch statement:

  1. State is set to -1. According to StateMachineStates.cs file this is NotStartedStateMachine .
  2. The code between yield return is executed. In our example, it prints the hardcoded string on console.
  3. Value returned by yield return statement (on C# level) is assigned to local this.<>1_current field. That’s why each time we call MoveNext method, the Current value changes.
  4. The state is changed to next one which does the whole trick. Next time the MoveNext method gets called, the switch will „navigate” to a different part of the method and will process it.
  5. A boolean value is returned which informs whether some element of the sequence has just been returned to the caller.

So far this is quite easy to understand. However, one thing which seems quite odd is the first point. Why is the state changed to -1 if it is then set to another one? Well, I agree that in our (simple) example this looks odd, but we should remember that sometimes the values returned by iterator can be the result of some calculations/additional processing like in the following code:

 


yield return Convert.ToInt32("WTF IS THAT");

 

The above line will throw FormtException inside the iterator. Now, let’s think about the scenario when we don’t change the state to -1 at the beginning of each state:

  1. MoveNext is called.
  2. this.<>2_current = Convert.ToInt32(„WTF IS THAT”) throws FormatException.
  3. The exception is caught somewhere and execution of the program is resumed.
  4. The caller invokes MoveNext method.
  5. this.<>2_current = Convert.ToInt32(„WTF IS THAT”) throws FormatException….

So in this case, we would be stuck because the state would be changed only after converting a string to a number. With -1 state things look significantly different:

  1. MoveNext is called.
  2. this.<>2_current = Convert.ToInt32(„WTF IS THAT”) throws FormatException.
  3. The exception is caught somewhere and execution of the program is resumed.
  4. The caller invokes MoveNext method.
  5. Since there’s no case for -1, the default block is reached which informs about the end of a sequence.

So, the whole mystery of remembering the location in code has been revealed! But before we move to the next paragraph, I’d like to change our example C# code a little bit. Instead of IEnumerator<int>, the iterator will return IEnumerable<int>:

 


        public static void Main()
        {
            var sequence = GetSequence().GetEnumerator();

            sequence.MoveNext();
            Console.WriteLine(sequence.Current);

            sequence.MoveNext();
            Console.WriteLine(sequence.Current);

            sequence.MoveNext();
            Console.WriteLine(sequence.Current);

            Console.ReadLine();
        }

        public static IEnumerable<int> GetSequence()
        {
            var a = 3;

            Console.WriteLine("I'm inside iterator!");
            yield return 1;

            Console.WriteLine("I know where to resume the execution!");
            yield return 2;

            Console.WriteLine("I did it once again!");
            yield return a;
        }

 

The compiler-generated code looks as follows:

 

Click to zoom

 

There are few changes comparing to the previous one:

  1. The state machine implements two, additional interfaces: IEnumerable<int> and IEnumerable. Thanks to that there’s no need to allocate an additional object when GetEnumerator method is called (like in our example).
  2. The initial state is now -2 (FinishedStateMachine).
  3. The compiler generates additional field this.<>1_initialThreadId which is set inside the constructor. In this case, it’s Environment.CurrentManagedThreadId due to the fact, I’m running this on .NET Core. However, this will look different on .NET Framework (see the Roslyn’s IteratorRewriter.cs – line 260)

All right, so what’s going on with the initial state and initial TID (Thread Id)? To find it out, we need to move to the GetEnumerator method where we can find the following condition:

 

        Program.<GetSequence>d__1 getSequenceD1;
        if (this.<>1__state == -2 && this.<>1__initialThreadId == Environment.CurrentManagedThreadId)
        {
          this.<>1__state = 0;
          getSequenceD1 = this;
        }
        else
          getSequenceD1 = new Program.<GetSequence>d__1(0);
        return (IEnumerator<int>) getSequenceD1;

 

Now everything is clear. If GetEnumerator method is called more than once or it’s called from the thread other than captured, then the new instance of a state machine is returned. This means that each caller can have it’s own, independent state of the iterator and moreover, the iterator’s implementation is thread-safe.

 

Iterators and local variables

I guess that more apprehensive readers have spotted one thing which somehow answers the second question. The state machine is implemented as a private sealed class, so a reference type which lives on a heap. This is how local variables can „survive”. They are hoisted from stack to heap by turning them into private fields of a class. It’s a simple trick but does the job. However, this can also be dangerous in some sort of situations. Imagine that you allocated a lot of memory to calculate one value for a sequence. Even though you return the value using yield return statement, the actual private field lives below on the IL level until state machine is disposed and then collected by garbage collector. Keep this in mind, because it can put you in a trouble quite easily. The rule of thumb here is quite simple. If the variable is no more needed inside the iterator, assign it to null. This will become a clear mark for a GC that it can be collected, so the memory will not leak.

 

Iterators and error handling

The last thing, I’d like to discuss is error handling which is very interesting when it comes to iterators. Why? First, rules describing allowed and prohibited combinations of yield keyword and try block seem quite inconsistent:

  • try-catchyield return can be put neither in try block nor in a catch handler
  • try-finallyyield return can be put inside try block but not inside finally handler
  • try-catchyield break can be put in a try block and in a catch handler
  • try-finallyyield break can be put in a try block but not in a finally handler

Of course, there are quite a few reasons for that which make perfect sense. I’m not going to describe all of the scenarios because this post would grow way too much and you can always do a small investigation on your own 😉 However, to understand what kind of problem language designer had to overcome, let’s analyze the second rule.

Say, we have the following code:

 


        public static void Main()
        {
            var sequence = GetSequence();

            foreach(var s in sequence)
                Console.WriteLine(s);

            Console.ReadLine();
        }

        public static IEnumerable<int> GetSequence()
        {
            try
            {

                yield return 1;
                yield return 2;
                yield return 3;
            }
            finally
            {
                Console.WriteLine("I'm inside finally!");
            }
        }

 

The first question we need to answer is, how many times finally handler will actually run? Well, this might be a little bit confusing knowing that each time the element of the sequence is yielded, the control is passed back to the caller. So, on the one hand – calling finally each time we „leave” the method seems reasonable. But on the other hand, it would be inconsistent with the rest of the language. Let’s run the program and see the result:

 

 

All right, we know that finally is called at the end of the iterator method. The same thing happens when an iterator gets disposed (at any time). Now we get to the fun part:

 


        public static void Main()
        {
            var sequence = GetSequence();

            sequence.MoveNext();

            sequence.Dispose(); // WAT?

            Console.ReadLine();
        }

        public static IEnumerator<int> GetSequence()
        {
            try
            {

                yield return 1;
                yield return 2;
                yield return 3;
            }
            finally
            {
                yield return 4;
            }
        }

 

Assuming yield return would be allowed inside finally handler, what this program would actually do? As I’ve just written, the code inside finally is executed when the iterator is disposed. But Dispose method returns void, so how the heck would it return the element of the sequence?! Besides that, there’s more confusion. Let’s say the result is skipped and we simply ignore it. But in the above example, a value was hardcoded. What would happen in the following example:

 



        public static IEnumerator<int> GetSequence()
        {
            try
            {

                yield return 1;
                yield return 2;
                yield return 3;
            }
            finally
            {
                yield return GetValue();
            }
        }

        public static int GetValue()
        {
            Console.WriteLine("Nooooo, side effect!");
            return 4;
        }

 

Here, things got even more complicated because GetValue has a side effect of its execution. So in this case, shall we skip the whole yield statement to avoid it or do something else? Of course, there are more edge cases in which behavior of the program would be hard to determine, but as mentioned – you can find it on your own 😉

However, since we discuss try-finally together with iterators, I think it’s a good idea to see how it looks on the IL level. Trust me, you’ll not regret it 😉 Here’s the code we’ll decompile in dotPeek:

 


        public static IEnumerator<int> GetSequence()
        {
            try
            {

                yield return 1;
                yield return 2;
                yield return 3;
            }
            finally
            {
                Console.WriteLine("I'm inside finally!");
            }
        }

 

Now, this is the code generated by the compiler:

 

 

There are four differences here, comparing to previous examples:

  • this.<>1__state is set twice before the this.<>2__current assignment
  • finally handler was replaced with __fault handler
  • code form finally was moved to separate method outside the MoveNext (can be inlined anyway)
  • Dispose method is implemented

Let’s start with the state because this looks kinda weird. We know the reason for setting a state to -1 before we do the assignment of the this.<>2_current field. But what’s going on with -3?! The answer can be found once again, deeply inside Roslyn’s GitHub (IteratorMethodToStateMachineRewriter.cs) :

Finally state is a negative decreasing number starting with -3. (-2 is used for something else). Root frame has finally state -1. The Finally state is the state that we are in when „between states”. Regular states are positive and are the only states that can be resumed to. The purpose of distinct finally states is to have enough information about which finally handlers must run when we need to finalize iterator after a fault.

This actually explains most of the above points. Additional state helps the program to determine which finally block should be reached after fault. In our case, this is not so useful since we have only one finally handler. But we could do something like that:

 


        public static IEnumerator<int> GetSequence()
        {
            try
            {
                yield return 1;
               
            }
            finally
            {
                Console.WriteLine("I'm inside first finally!");
            }

            try
            {
                yield return 2;
            }
            finally
            {
                Console.WriteLine("I'm inside second finally!");
            }
        }

 

or even that:

 


        public static IEnumerator<int> GetSequence()
        {
            try
            {
                yield return 1;

                try
                {
                    yield return 2;
                }
                finally
                {
                    Console.WriteLine("I'm inside nested finally!");
                }

            }
            finally
            {
                Console.WriteLine("I'm inside finally!");
            }
        }

 

In such scenarios, having only one „finally state” (-1) would not provide enough information which code from particular finally handlers (extracted to separate method) should be called inside Dispose method.
Finally, we got to the __fault handler. What is that? Well, it’s additional, hidden handler for protected (try) block. C# legal equivalent would look like this:

 


            var isFault = false;

            try
            {

                //...
            }
            catch
            {
                isFault = true;
            }
            finally
            {
                if(isFault)
                {

                }
            }

 

So it works a little bit like finally handler but only in case of…fault. To me it’s truly exciting because so far, this is the only case in which the try-fault was generated by the C# compiler 😀

The last thing we should cover is, why the iterator calls Dispose method on fault? This is once again briefly described on GitHub:

C# spec requires that iterators trap all exceptions and self-dispose eagerly.10.14.4.1 The MoveNext method
When an exception is thrown and propagated out of the iterator block:
o Appropriate finally blocks in the iterator body will have been executed by the exception propagation.
o The state of the enumerator object is changed to after.
o The exception propagation continues to the caller of the MoveNext method.

Nothing more nothing less.

Well, that was quite a long journey, wasn’t it? Hopefully, everything was clear to you and you liked this entry. If you have any suggestions or I simply messed something up, please let me know down in the comments 😉

You may also like...