庖丁解牛迭代器，聊聊那些藏在幕后的秘密

0x00 前言

在我之前的一篇博客《细说C#：不是“栈类型”的值类型，从生命周期聊存储位置》的最后，我以总结和后记的方式涉及到一部分迭代器的知识。但是觉得还是不够过瘾，很多需要说清楚的内容还是含糊不清，所以本文就专门写一下c#中的迭代器吧。

0x01 你好，迭代器

首先思考一下，在什么情景下我们需要使用到迭代器？

假设我们有一个数据容器（可能是 Array，List，Tree 等等），对我们这些使用者来说，我们显然希望这个数据容器能提供一种无需了解它的内部实现就可以获取其元素的方法，无论它是 Array 还是 List 或者别的什么，我们希望可以通过相同的方法达到我们的目的。

此时，迭代器模式（iterator pattern）便应运而生，它通过持有迭代状态，追踪当前元素并且识别下一个需要被迭代的元素，从而可以让使用者透过特定的界面巡访容器中的每一个元素而不用了解底层的实现。

那么，在 c#中，迭代器到底是以一个怎样的面目出现的呢？

如我们所知，它们被封装在 IEnumerable 和 IEnumerator 这两个接口中（当然，还有它们的泛型形式，要注意的是泛型形式显然是强类型的。且IEnumerator<T>实现了 IDisposable 接口）。

IEnumerable 非泛型形式:

//IEnumerable 非泛型形式
[ComVisibleAttribute(True)]
[GuidAttribute("496B0ABE-   CDEE-11d3-88E8-00902754C43A")]
public interface IEnumerable
{
   IEnumerator GetEnumerator();
}
 

IEnumerator 非泛型形式:

//IEnumerator 非泛型形式
[ComVisibleAttribute(true)]
[GuidAttribute("496B0ABF-CDEE-11d3-88E8-00902754C43A")]
public interface IEnumerator
{
   Object Current {get;}
   bool MoveNext();
   void Reset();
}
 

IEnumerable 泛型形式:

//IEnumerable 泛型形式
public interface IEnumerable<out T> : IEnumerable
{
   IEnumerator<T> GetEnumerator();
   IEnumerator GetEnumerator(); 
}
 

IEnumerator 泛型形式:

//IEnumerator 泛型形式
public interface IEnumerator<out T> : IDisposable, IEnumerator
{
 
   void Dispose(); 
   Object Current {get;} 
   T Current {get;}
   bool MoveNext(); 
   void Reset(); 
}
 
[ComVisibleAttribute(true)]
public interface IDisposable
{
   void Dispose();
}
 

IEnumerable 接口定义了一个可以获取 IEnumerator 的方法——GetEnumerator()。

而 IEnumerator 则在目标序列上实现循环迭代（使用 MoveNext() 方法，以及 Current 属性来实现），直到你不再需要任何数据或者没有数据可以被返回。使用这个接口，可以保证我们能够实现常见的 foreach 循环。

为什么会有 2 个接口？

到此，各位看官是否和曾经的我有相同的疑惑呢？那就是为何 IEnumerable 自己不直接实现 MoveNext() 方法、提供 Current 属性呢？为何还需要额外的一个接口 IEnumerator 来专门做这个工作？

OK，假设有两个不同的迭代器要对同一个序列进行迭代。当然，这种情况很常见，比如我们使用两个嵌套的 foreach 语句。我们自然希望两者相安无事，不要互相影响彼此。所以自然而然的，我们需要保证这两个独立的迭代状态能够被正确的保存、处理。这也正是 IEnumerator 要做的工作。而为了不违背单一职责原则，不使 IEnumerable 拥有过多职责从而陷入分工不明的窘境，所以 IEnumerable 自己并没有实现 MoveNext() 方法。

迭代器的执行步骤

为了更直观的了解一个迭代器，我这里提供一个小例子。

using System;
using System.Collections.Generic;
 
class Class1
{ 
   static void Main()
   {
       foreach (string s in GetEnumerableTest())
       {
           Console.WriteLine(s);
       }
   }
 
    static IEnumerable<string> GetEnumerableTest()
   {
       yield return "begin";
 
       for (int i=0; i < 10; i++)
       {
           yield return i.ToString();
       }
 
       yield return "end";
   }
}
 

输出结果如图：

OK，那么我就给各位捋一下这段代码的执行过程。

1. Main 调用 GetEnumerableTest() 方法。
2. GetEnumerableTest() 方法会为我们创建一个编译器生成的新的类”Class1/’c__Iterator0’”（本例中）的实例。注意，此时 GetEnumerableTest() 方法中，我们自己的代码尚未执行。
3. Main 调用 MoveNext() 方法。
4. 迭代器开始执行，直到它遇到第一个 yield return 语句。此时迭代器会获取当前的值是“begin”，并且返回 true 以告知此时还有数据。
5. Main 使用 Current 属性以获取数据，并打印出来。
6. Main 再次调用 MoveNext() 方法。
7. 迭代器继续从上次遇到 yield return 的地方开始执行，并且和之前一样，直到遇到下一个 yield return。
8. 迭代器按照这种方式循环，直到 MoveNext() 方法返回 false，以告知此时已经没有数据了。

这个例子中迭代器的执行过程，我已经给各位看官简单的描述了一下。但是还有几点需要关注的，我也想提醒各位注意一下。

• 在第一次调用 MoveNext() 方法之前，我们自己在 GetEnumerableTest 中的代码不会执行。
• 之后调用 MoveNext() 方法时，会从上次暂停（yield return）的地方开始。
• 编译器会保证 GetEnumerableTest 方法中的局部变量能够被保留，换句话说，虽然本例中的 i 是值类型实例，但是它的值其实是被迭代器保存在堆上的，这样才能保证每次调用 MoveNext 时，它是可用的。这也是我之前的一篇文章中说迭代器块中的局部变量会被分配在堆上的原因。

好了，简单总结了一下 C#中的迭代器的外观。那么接下来，我们继续向内部前进，来看看迭代器究竟是如何实现的。

0x02 原来是状态机呀

上一节我们已经从外部看到了 IEnumerable 和 IEnumerator 这两个接口的用法了，但是它们的内部到底是如何实现的呢？两者之间又有何区别呢？

既然要深入迭代器的内部，这就是一个不得不面对的问题。

那么我就写一个小程序，之后再通过反编译的方式，看看在我们自己手动写的代码背后，编译器究竟又给我们做了哪些工作吧。

为了简便起见，这个小程序仅仅实现一个按顺序返回 0-9 这 10 个数字的功能。

IEnumerator 的内部实现

首先，我们定义一个返回 IEnumerator 的方法 TestIterator()。

//IEnumerator<T> 测试
using System;
using System.Collections;
 
class Test
{
   static IEnumerator<int> TestIterator()
   {
       for (int i = 0; i < 10; i++)
       {
           yield return i;
       }
   }
}
 

接下来，我们看看反编译之后的代码，探查一下编译器到底为我们做了什么吧。

internal class Test
{
   // Methods 注，此时还没有执行任何我们写的代码
   private static IEnumerator<int> TestIterator()
   {
       return new <TestIterator>d__0(0);
   }
 
   // Nested Types 编译器生成的类，用来实现迭代器。
   [CompilerGenerated]
   private sealed class <TestIterator>d__0 : IEnumerator<int>, IEnumerator, IDisposable
   {
       // Fields 字段：state 和 current 是默认出现的
       private int <>1__state;
       private int <>2__current;
       public int <i>5__1;//<i>5__1 来自我们迭代器块中的局部变量
 
       // Methods 构造函数，初始化状态
       [DebuggerHidden]
       public <TestIterator>d__0(int <>1__state)
       {
           this.<>1__state = <>1__state;
       }
       // 几乎所有的逻辑在这里
       private bool MoveNext()
       {
           switch (this.<>1__state)
           {
               case 0:
                   this.<>1__state = -1;
                   this.<i>5__1 = 0;
                   while (this.<i>5__1 < 10)
                   {
                       this.<>2__current = this.<i>5__1;
                       this.<>1__state = 1;
                       return true;
                   Label_0046:
                       this.<>1__state = -1;
                       this.<i>5__1++;
                   }
                   break;
 
               case 1:
                   goto Label_0046;
           }
           return false;
       }
       [DebuggerHidden]
       void IEnumerator.Reset()
       {
           throw new NotSupportedException();
       }
 
       void IDisposable.Dispose()
       {
       }
 
       // Properties
       int IEnumerator<int>.Current
       {
           [DebuggerHidden]
           get
           {
               return this.<>2__current;
           }
       }
 
       object IEnumerator.Current
       {
           [DebuggerHidden]
           get
           {
               return this.<>2__current;
           }
       }
   }
}
 

我们先全面的看一下反编译之后的代码，可以发现几乎所有的逻辑都发生在 MoveNext() 方法中。那么之后我们再详细介绍下它，现在我们先从上到下把代码捋一遍。

1. 这段代码给人的第一印象就是命名似乎很不雅观。的确，这种在正常的 C#代码中不会出现的命名，在编译器生成的代码中却是常常出现。因为这样就可以避免和已经存在的正常名字发生冲突的可能性。
2. 调用 TestIterator() 方法的结果仅仅是调用了<TestIterator>d__0（编译器生成的用来实现迭代器的类）的构造函数。而这个构造函数会设置迭代器的初始状态，此时的参数为 0，而构造函数会将 0 赋值给记录迭代器状态的字段：this.<>1__state = <>1__state;。注意，此时我们自己的代码并没有执行。
3. <TestIterator>d__0这个类实现了 3 个接口：IEnumerator<int>， IEnumerator， IDisposable。
4. IDisposable 的实现十分重要。因为 foreach 语句会在它自己的 finally 代码块中调用实现了 IDisposable 接口的迭代器的 Dispose 方法。
5. <TestIterator>d__0类有 3 个字段：<>1__state，<>2__current， <i>5__1。其中，<>1__state私有字段标识迭代器的状态，<>2__current私有字段则追踪当前的值，而<i>5__1共有字段则是我们在迭代器块中定义的局部变量 i。
6. MoveNext() 方法的实现则依托与 switch 语句。根据状态机的状态，执行不同的代码。
7. 在本例中 Dispose 方法什么都没有做。
8. 在 IEnumerator 和IEnumerator<int>的实现中，Current 都是单纯的返回<>2__current的值。

OK，IEnumerator 接口我们看完了。下面再来看看另一个接口 IEnumerable 吧。

IEnumerator VS IEnumerable

依样画葫芦，这次我们仍然是写一个实现按顺序返回 0-9 这 10 个数字的功能的小程序，只不过返回类型变为IEnumerable<T>。

using System;
using System.Collections.Generic;
 
class Test
{
   static IEnumerable<int> TestIterator()
   {
       for (int i = 0; i < 10; i++)
       {
           yield return i;
       }
   }
}
 

之后，我们同样通过反编译，看看编译器又背着我们做了什么。

internal class Test
{
   private static IEnumerable<int> TestIterator()
   {
       return new <TestIterator>d__0(-2);
   }
 
   private sealed class <TestIterator>d__0 : IEnumerable<int>, IEnumerable, IEnumerator<int>, IEnumerator, IDisposable
   {
       // Fields
       private int <>1__state;
       private int <>2__current;
       private int <>l__initialThreadId;
       public int <count>5__1;
 
       public <TestIterator>d__0(int <>1__state)
       {
           this.<>1__state = <>1__state;
           this.<>l__initialThreadId = Thread.CurrentThread.ManagedThreadId;
       }
 
       private bool MoveNext()
       {
           switch (this.<>1__state)
           {
               case 0:
                   this.<>1__state = -1;
                   this.<count>5__1 = 0;
                   while (this.<count>5__1 < 10)
                   {
                       this.<>2__current = this.<count>5__1;
                       this.<>1__state = 1;
                       return true;
                   Label_0046:
                       this.<>1__state = -1;
                       this.<count>5__1++;
                   }
                   break;
 
               case 1:
                   goto Label_0046;
           }
           return false;
       }
 
       IEnumerator<int> IEnumerable<int>.GetEnumerator()
       {
           if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))
           {
               this.<>1__state = 0;
               return this;
           }
           return new Test.<TestIterator>d__0(0);
       }
 
       IEnumerator IEnumerable.GetEnumerator()
       {
           return ((IEnumerable<Int32>) this).GetEnumerator();
       }
 
       void IEnumerator.Reset()
       {
           throw new NotSupportedException();
       }
 
       void IDisposable.Dispose()
       {
       }
 
       int IEnumerator<int>.Current
       {
           get
           {
               return this.<>2__current;
           }
       }
 
       object IEnumerator.Current
       {
           get
           {
               return this.<>2__current;
           }
       }
   }
}
 

看到反编译出的代码，我们就很容易能对比出区别。

1. <TestIterator>d__0类不仅实现了IEnumerable<int> 接口，而且还实现了IEnumerator<int>接口。
2. IEnumerator 和IEnumerator<int>的实现都和上面一样。IEnumerator 的 Reset 方法会抛出 NotSupportedException 异常，而 IEnumerator 和IEnumerator<int>的 Current 仍旧会返回<>2__current字段的值。
3. TestIterator() 方法调用<TestIterator>d__0类的构造函数时，传入的参数由上面的 0 变成了 -2：new <TestIterator>d__0(-2);。也就是说此时的初始状态是 -2。
4. 又多了一个新的私有字段<>l__initialThreadId，且会在<TestIterator>d__0的构造函数中被赋值，用来标识创建该实例的线程。
5. 实现 IEnumerable 的 GetEnumerator 方法，在 GetEnumerator 方法中要么将状态置为 0，并返回 this：this.<>1__state = 0；return this；要么就返回一个新的<TestIterator>d__0实例，且初始状态置为 0：return new Test.<TestIterator>d__0(0);

所以，从这些对比中我们能发现些什么吗？思考一下我们经常使用的一些用法，包括我在上一节中提供的小例子。不错，我们会创建一个IEnumerable<T>的实例，之后一些语句（例如 foreach）会去调用 GetEnumerator 方法获取一个Enumerator<T>的实例，之后迭代数据，最终结束后释放掉迭代器的实例（这一步 foreach 会帮我们做）。

而分析 IEnumerable 的 GetEnumerator 方法：

IEnumerator<int> IEnumerable<int>.GetEnumerator()
{
   if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))
   {
       this.<>1__state = 0;
       return this;
   }
   return new Test.<TestIterator>d__0(0);
}
 

我们可以发现，-2 这个状态，也就是此时的初始状态，表明了 GetEnumerator() 方法还没有执行。而 0 这个状态，则表明已经准备好了迭代，但是 MoveNext() 尚未调用过。

当在不同的线程上调用 GetEnumerator 方法或者是状态不是 -2（证明已经不是初始状态了），则 GetEnumerator 方法会返回一个<TestIterator>d__0类的新实例用来保存不同的状态。

0x03 状态管理

OK，我们深入了迭代器的内部，发现了原来它的实现主要依靠的是一个状态机。那么，下面就让我继续和大伙聊聊这个状态机是如何管理状态的。

状态切换

根据 Ecma-334 标准，也就是 c#语言标准的第 26.2 Enumerator objects小节，我们可以知道迭代器有 4 种可能状态：

1. before 状态
2. running 状态
3. suspended 状态
4. after 状态

而其中 before 状态是作为初始状态出现的。

在我们讨论状态如何切换之前，我还要带领大家回想一下上面提到的，也就是在调用一个使用了迭代器块，返回类型为一个 IEnumerator 或 IEnumerable 接口的方法时，这个方法并非立刻执行我们自己写的代码的。而是会创建一个编译器生成的类的实例，之后当调用 MoveNext() 方法时（当然如果方法的返回类型是 IEnumerable，则要先调用 GetEnumerator() 方法），我们的代码才会开始执行，直到遇到第一个 yield return 语句或 yield break 语句，此时会返回一个布尔值来判断迭代是否结束。当下次再调用 MoveNext() 方法时，我们的方法会继续从上一个 yield return 语句处开始执行。

为了能够直观的观察状态的切换，下面我提供另一个例子：

class Test
{
 
   static IEnumerable<int> TestStateChange()
   {
       Console.WriteLine("---- 我 TestStateChange 是第一行代码 ");
       Console.WriteLine("---- 我是第一个 yield return 前的代码 ");
       yield return 1;
       Console.WriteLine("---- 我是第一个 yield return 后的代码 ");
 
       Console.WriteLine("---- 我是第二个 yield return 前的代码 ");
       yield return 2;
       Console.WriteLine("---- 我是第二个 yield return 前的代码 ");
   }
 
   static void Main()
   {
       Console.WriteLine(" 调用 TestStateChange");
       IEnumerable<int> iteratorable = TestStateChange();
       Console.WriteLine(" 调用 GetEnumerator");
       IEnumerator<int> iterator = iteratorable.GetEnumerator();
       Console.WriteLine(" 调用 MoveNext()");
       bool hasNext = iterator.MoveNext();
       Console.WriteLine(" 是否有数据 ={0}; Current={1}", hasNext, iterator.Current);
 
       Console.WriteLine(" 第二次调用 MoveNext");
       hasNext = iterator.MoveNext();
       Console.WriteLine(" 是否还有数据 ={0}; Current={1}", hasNext, iterator.Current);
 
       Console.WriteLine(" 第三次调用 MoveNext");
       hasNext = iterator.MoveNext();
       Console.WriteLine(" 是否还有数据 ={0}", hasNext);
   }
}
 

之后，我们运行这段代码看看结果如何。

可见，代码的执行顺序就是我刚刚总结的那样。那么我们将这段编译后的代码再反编译回 C#，看看编译器到底是如何处理这里的状态切换的。

这里我们只关心两个方法，首先是 GetEnumerator 方法。其次是 MoveNext 方法。

[DebuggerHidden]
IEnumerator<int> IEnumerable<int>.GetEnumerator()
{
   if ((Environment.CurrentManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))
   {
       this.<>1__state = 0;
       return this;
   }
   return new Test.<TestStateChange>d__0(0);
}
 

看 GetEnumerator 方法，我们可以发现：

1. 此时的初始状态是 -2。
2. 不过一旦调用 GetEnumerator，则会将状态置为 0。也就是状态从最初的 -2，在调用过 GetEnumerator 方法后变成了 0。

我们再来看看 MoveNext 方法。

private bool MoveNext()
{
   switch (this.<>1__state)
   {
       case 0:
           this.<>1__state = -1;
           Console.WriteLine("---- 我 TestStateChange 是第一行代码 ");
           Console.WriteLine("---- 我是第一个 yield return 前的代码 ");
           this.<>2__current = 1;
           this.<>1__state = 1;
           return true;
 
       case 1:
           this.<>1__state = -1;
           Console.WriteLine("---- 我是第一个 yield return 后的代码 ");
           Console.WriteLine("---- 我是第二个 yield return 前的代码 ");
           this.<>2__current = 2;
           this.<>1__state = 2;
           return true;
 
       case 2:
           this.<>1__state = -1;
           Console.WriteLine("---- 我是第二个 yield return 前的代码 ");
           break;
   }
   return false;
}
 

由于第一次调用 MoveNext 方法发生在调用 GetEnumerator 方法之后，所以此时状态已经变成了 0。

可以清晰的看到此时从 0——>1——>2——>-1 这样的状态切换过程。而且还要注意，每个分支中，this.<>1__state都会首先被置为 -1：this.<>1__state = -1。之后才会根据不同的阶段赋值不同的值。而这些不同的值也就用来标识代码从哪里恢复执行。

我们再拿之前实现了按顺序返回 0-9 这 10 个数字的小程序的状态管理作为例子，来让我们更加深刻的理解迭代器除了刚刚的例子，还有什么手段可以用来实现“当下次再调用 MoveNext() 方法时，我们的方法会继续从上一个 yield return 语句处开始执行。”这一个功能的。

private bool MoveNext()
{
   switch (this.<>1__state)
   {
       case 0:
           this.<>1__state = -1;
           this.<i>5__1 = 0;
           while (this.<i>5__1 < 10)
           {
               this.<>2__current = this.<i>5__1;
               this.<>1__state = 1;
               return true;
           Label_0046:
               this.<>1__state = -1;
               this.<i>5__1++;
           }
           break;
 
       case 1:
           goto Label_0046;
   }
   return false;
}
 

不错，此时状态机是靠着 goto 语句实现半路插入，进而实现了从 _yield return_ 处继续执行的功能。

好吧，让我们总结一下关于迭代器内部状态机的状态切换：

• -2 状态：只有 IEnumerable 才有，表明在第一次调用 GetEnumerator 之前的状态。
• -1 状态：即上文中提到的 C#语言标准中规定的 Running 状态，表明此时迭代器正在执行。当然，也会用于 After 状态，例如上例中的 case 2 中，this.<>1__state被赋值为 -1，但是此时迭代结束了。
• 0 状态：即上文中提到的 Before 状态，表明 MoveNext() 还一次都没有调用过。
• 正数（1，2，3…），主要用来标识从遇到 yield 之后，代码从哪里恢复执行。

0x04 总结

通过我上文的分析，可以看出迭代器的实现的确十分复杂。不过值得庆幸的是很多工作都由编译器在幕后为我们做好了。那么，本文就到此结束。欢迎大家探讨。

感谢丁晓昀对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ， @丁晓昀），微信（微信号： InfoQChina ）关注我们，并与我们的编辑和其他读者朋友交流（欢迎加入 InfoQ 读者交流群）。