C# 2.0 中Iterators的改进与实现原理浅析

　　 C#语言从VB中吸取了一个非常实用的foreach语句。对所有支持IEnumerable接口的类的实例，foreach语句使用统一的接口遍历其子项，使得以前冗长的for循环中繁琐的薄记工作完全由编译器自动完成。支持IEnumerable接口的类通常用一个内嵌类实现IEnumerator接口，并通过IEnumerable.GetEnumerator函数，允许类的使用者如foreach语句完成遍历工作。

　　 这一特性使用起来非常方便，但需要付出一定的代价。Juval Lowy发表在MSDN杂志2004年第5期上的Create Elegant Code with Anonymous Methods, Iterators, and Partial Classes一文中，较为详细地介绍了C# 2.0中迭代支持和其他新特性。

　　 首先，因为IEnumerator.Current属性是一个object类型的值，所以值类型(value type)集合在被foreach语句遍历时，每个值都必须经历一次无用的box和unbox操作；就算是引用类型(reference type)集合，在被foreach语句使用时，也需要有一个冗余的castclass指令，保障枚举出来的值进行类型转换的正确性。

　　以下为引用：

　　using System.Collections;

　　public class Tokens : IEnumerable

　　{

　　 ...

　　 Tokens f = new Tokens(...);

　　 foreach (string item in f)

　　 {

　　 Console.WriteLine(item);

　　 }

　　 ...

　　}

　　 上面的简单代码被自动转换为

　　以下为引用：

　　Tokens f = new Tokens(...);

　　IEnumerator enum = f.GetEnumerator();

　　try

　　{

　　 do {

　　 string item = (string)enum.get_Current(); // 冗余转换

　　 Console.WriteLine(item);

　　 } while(enum.MoveNext());

　　}

　　finally

　　{

　　 if(enum is IDisposable) // 需要验证实现IEnumerator接口的类是否支持IDisposable接口

　　 {

　　 ((IDisposable)enum).Dispose();

　　 }

　　}

　　 好在C# 2.0中支持了泛型(generic)的概念，提供了强类型的泛型版本IEnumerable定义，伪代码如下：

　　以下为引用：

　　namespace System.Collections.Generic

　　{

　　 public interface IEnumerable<ItemType>

　　 {

　　 IEnumerator<ItemType> GetEnumerator();

　　 }

　　 public interface IEnumerator<ItemType> : IDisposable

　　 {

　　 ItemType Current{get;}

　　 bool MoveNext();

　　 }

　　}

　　 这样一来即保障了遍历集合时的类型安全，又能够对集合的实际类型直接进行操作，避免冗余转换，提高了效率。

　　以下为引用：

　　using System.Collections.Generic;

　　public class Tokens : IEnumerable<string>

　　{

　　 ... // 实现 IEnumerable<string> 接口

　　 Tokens f = new Tokens(...);

　　 foreach (string item in f)

　　 {

　　 Console.WriteLine(item);

　　 }

　　}

　　 上面的代码被自动转换为

　　以下为引用：

　　Tokens f = new Tokens(...);

　　IEnumerator<string> enum = f.GetEnumerator();

　　try

　　{

　　 do {

　　 string item = enum.get_Current(); // 无需转换

　　 Console.WriteLine(item);

　　 } while(enum.MoveNext());

　　}

　　finally

　　{

　　 if(enum) // 无需验证实现IEnumerator接口的类是否支持IDisposable接口，

　　 // 因为所有由编译器自动生成的IEnumerator接口实现类都支持

　　 {

　　 ((IDisposable)enum).Dispose();

　　 }

　　}

　　 除了遍历时的冗余转换降低性能外，C#现有版本另一个不爽之处在于实现IEnumerator接口实在太麻烦了。通常都是由一个内嵌类实现IEnumerator接口，而此内嵌类除了get_Current()函数外，其他部分的功能基本上都是相同的，如

　　以下为引用：

　　public class Tokens : IEnumerable

　　{

　　 public string[] elements;

　　 Tokens(string source, char[] delimiters)

　　 {

　　 // Parse the string into tokens:

　　 elements = source.Split(delimiters);

　　 }

　　 public IEnumerator GetEnumerator()

　　 {

　　 return new TokenEnumerator(this);

　　 }

　　 // Inner class implements IEnumerator interface:

　　 private class TokenEnumerator : IEnumerator

　　 {

　　 private int position = -1;

　　 private Tokens t;

　　 public TokenEnumerator(Tokens t)

　　 {

　　 this.t = t;

　　 }

　　 // Declare the MoveNext method required by IEnumerator:

　　 public bool MoveNext()

　　 {

　　 if (position < t.elements.Length - 1)

　　 {

　　 position++;

　　 return true;

　　 }

　　 else

　　 {

　　 return false;

　　 }

　　 }

　　 // Declare the Reset method required by IEnumerator:

　　 public void Reset()

　　 {

　　 position = -1;

　　 }

　　 // Declare the Current property required by IEnumerator:

　　 public object Current

　　 {

　　 get // get_Current函数

　　 {

　　 return t.elements[position];

　　 }

　　 }

　　 }

　　 ...

　　}

　　 内嵌类TokenEnumerator的position和Tokens实际上是每个实现IEnumerator接口的类共有的，只是Current属性的get函数有所区别而已。这方面C# 2.0做了很大的改进，增加了yield关键字的支持，允许代码逻辑上的重用。上面冗长的代码在C# 2.0中只需要几行，如

　　以下为引用：

　　using System.Collections.Generic;

　　public class Tokens : IEnumerable<string>

　　{

　　 public IEnumerator<string> GetEnumerator()

　　 {

　　 for(int i = 0; i<elements.Length; i++)

　　 yield elements[i];

　　 }

　　 ...

　　}

　　 GetEnumerator函数是一个C# 2.0支持的迭代块(iterator block)，通过yield告诉编译器在什么时候返回什么值，再由编译器自动完成实现IEnumerator<string>接口的薄记工作。而yield break语句支持从迭代块中直接结束，如

　　以下为引用：

　　public IEnumerator<int> GetEnumerator()

　　{

　　 for(int i = 1;i< 5;i++)

　　 {

　　 yield return i;

　　 if(i > 2)

　　 yield break; // i > 2 时结束遍历

　　 }

　　}

　　 这样一来，很容易就能实现IEnumerator接口，并可以方便地支持在一个类中提供多种枚举方式，如

　　以下为引用：

　　public class CityCollection

　　{

　　 string[] m_Cities = {"New York","Paris","London"};

　　 public IEnumerable<string> Reverse

　　 {

　　 get

　　 {

　　 for(int i=m_Cities.Length-1; i>= 0; i--)

　　 yield m_Cities[i];

　　 }

　　 }

　　}

　　 接下来我们看看如此方便的语言特性背后，编译器为我们做了哪些工作。以上面那个支持IEnumerable<string>接口的Tokens类为例，GetEnumerator函数的代码被编译器用一个类包装起来，伪代码如下

　　以下为引用：

　　public class Tokens : IEnumerable<string>

　　{

　　 private sealed class GetEnumerator$00000000__IEnumeratorImpl

　　 : IEnumerator<string>, IEnumerator, IDisposable

　　 {

　　 private int $PC = 0;

　　 private string $_current;

　　 private Tokens <this>;

　　 public int i$00000001 = 0;

　　 // 实现 IEnumerator<string> 接口

　　 string IEnumerator<string>.get_Current()

　　 {

　　 return $_current;

　　 }

　　 bool IEnumerator<string>.MoveNext()

　　 {

　　 switch($PC)

　　 {

　　 case 0:

　　 {

　　 $PC = -1;

　　 i$00000001 = 0;

　　 break;

　　 }

　　 case 1:

　　 {

　　 $PC = -1;

　　 i$00000001++;

　　 break;

　　 }

　　 default:

　　 {

　　 return false;

　　 }

　　 }

　　 if(i$00000001 < <this>.elements.Length)

　　 {

　　 $_current = <this>.elements[i$00000001];

　　 $PC = 1;

　　 return true;

　　 }

　　 else

　　 {

　　 return false;

　　 }

　　 }

　　 // 实现 IEnumerator 接口

　　 void IEnumerator.Reset()

　　 {

　　 throw new Exception();

　　 }

　　 string IEnumerator.get_Current()

　　 {

　　 return $_current;

　　 }

　　 bool IEnumerator.MoveNext()

　　 {

　　 return IEnumerator<string>.MoveNext(); // 调用 IEnumerator<string> 接口的实现

　　 }

　　 // 实现 IDisposable 接口

　　 void Dispose()

　　 {

　　 }

　　 }

　　 public IEnumerator<string> GetEnumerator()

　　 {

　　 GetEnumerator$00000000__IEnumeratorImpl impl = new GetEnumerator$00000000__IEnumeratorImpl();

　　 impl.<this> = this;

　　 return impl;

　　 }

　　}

　　 从上面的伪代码中我们可以看到，C# 2.0编译器实际上维护了一个和我们前面实现IEnumerator接口的TokenEnumerator类非常类似的内部类，用来封装IEnumerator<string>接口的实现。而这个内嵌类的实现逻辑，则根据GetEnumerator定义的yield返回地点决定。

　　 我们接下来看一个较为复杂的迭代块的实现，支持递归迭代(Recursive Iterations)，代码如下：

　　以下为引用：

　　using System;

　　using System.Collections.Generic;

　　class Node<T>

　　{

　　 public Node<T> LeftNode;

　　 public Node<T> RightNode;

　　 public T Item;

　　}

　　public class BinaryTree<T>

　　{

　　 Node<T> m_Root;

　　 public void Add(params T[] items)

　　 {

　　 foreach(T item in items)

　　 Add(item);

　　 }

　　 public void Add(T item)

　　 {

　　 // ...

　　 }

　　 public IEnumerable<T> InOrder

　　 {

　　 get

　　 {

　　 return ScanInOrder(m_Root);

　　 }

　　 }

　　 IEnumerable<T> ScanInOrder(Node<T> root)

　　 {

　　 if(root.LeftNode != null)

　　 {

　　 foreach(T item in ScanInOrder(root.LeftNode))

　　 {

　　 yield item;

　　 }

　　 }

　　 yield root.Item;

　　 if(root.RightNode != null)

　　 {

　　 foreach(T item in ScanInOrder(root.RightNode))

　　 {

　　 yield item;

　　 }

　　 }

　　 }

　　}

　　 BinaryTree<T>提供了一个支持IEnumerable<T>接口的InOrder属性，通过ScanInOrder函数遍历整个二叉树。因为实现IEnumerable<T>接口的不是类本身，而是一个属性，所以编译器首先要生成一个内嵌类支持IEnumerable<T>接口。伪代码如下

　　以下为引用：

　　public class BinaryTree<T>

　　{

　　 private sealed class ScanInOrder$00000000__IEnumeratorImpl<T>

　　 : IEnumerator<T>, IEnumerator, IDisposable

　　 {

　　 BinaryTree<T> <this>;

　　 Node<T> root;

　　 // ...

　　 }

　　 private sealed class ScanInOrder$00000000__IEnumerableImpl<T>

　　 : IEnumerable<T>, IEnumerable

　　 {

　　 BinaryTree<T> <this>;

　　 Node<T> root;

　　 IEnumerator<T> IEnumerable<T>.GetEnumerator()

　　 {

　　 ScanInOrder$00000000__IEnumeratorImpl<T> impl = new ScanInOrder$00000000__IEnumeratorImpl<T>();

　　 impl.<this> = this.<this>;

　　 impl.root = this.root;

　　 return impl;

　　 }

　　 IEnumerator IEnumerable.GetEnumerator()

　　 {

　　 ScanInOrder$00000000__IEnumeratorImpl<T> impl = new ScanInOrder$00000000__IEnumeratorImpl<T>();

　　 impl.<this> = this.<this>;

　　 impl.root = this.root;

　　 return impl;

　　 }

　　 }

　　 IEnumerable<T> ScanInOrder(Node<T> root)

　　 {

　　 ScanInOrder$00000000__IEnumerableImpl<T> impl = new ScanInOrder$00000000__IEnumerableImpl<T>();

　　 impl.<this> = this;

　　 impl.root = root;

　　 return impl;

　　 }

　　}

　　 因为ScanInOrder函数内容需要用到root参数，故而IEnumerable<T>和IEnumerator<T>接口的包装类都需要有一个root字段，保存传入ScanInOrder函数的参数，并传递给最终的实现函数。

　　 实现IEnumerator<T>接口的内嵌包装类ScanInOrder$00000000__IEnumeratorImpl<T>实现原理与前面例子里的大致相同，不同的是程序逻辑大大复杂化，并且需要用到IDisposable接口完成资源的回收。

　　以下为引用：

　　public class BinaryTree<T>

　　{

　　 private sealed class GetEnumerator$00000000__IEnumeratorImpl

　　 : IEnumerator<T>, IEnumerator, IDisposable

　　 {

　　 private int $PC = 0;

　　 private string $_current;

　　 private Tokens <this>;

　　 public int i$00000001 = 0;

　　 public IEnumerator<T> __wrap$00000003;

　　 public IEnumerator<T> __wrap$00000004;

　　 public T item$00000001;

　　 public T item$00000002;

　　 public Node<T> root;

　　 // 实现 IEnumerator<T> 接口

　　 string IEnumerator<T>.get_Current()

　　 {

　　 return $_current;

　　 }

　　 bool IEnumerator<T>.MoveNext()

　　 {

　　 switch($PC)

　　 {

　　 case 0:

　　 {

　　 $PC = -1;

　　 if(root.LeftNode != null)

　　 {

　　 __wrap$00000003 = <this>.ScanInOrder(root.LeftNode).GetEnumerator();

　　 goto ScanLeft;

　　 }

　　 else

　　 {

　　 goto GetItem;

　　 }

　　 }

　　 case 1:

　　 {

　　 return false;

　　 }

　　 case 2:

　　 {

　　 goto ScanLeft;

　　 }

　　 case 3:

　　 {

　　 $PC = -1;

　　 if(root.RightNode != null)

　　 {

　　 __wrap$00000004 = <this>.ScanInOrder(root.RightNode).GetEnumerator();

　　 goto ScanRight;

　　 }

　　 else

　　 {

　　 return false;

　　 }

　　 break;

　　 }

　　 case 4:

　　 {

　　 return false;

　　 }

　　 case 5:

　　 {

　　 goto ScanRight;

　　 }

　　 default:

　　 {

　　 return false;

　　 }

　　 ScanLeft:

　　 $PC = 1;

　　 if(__wrap$00000003.MoveNext())

　　 {

　　 $_current = item$00000001 = __wrap$00000003.get_Current();

　　 $PC = 2;

　　 return true;

　　 }

　　 GetItem:

　　 $PC = -1;

　　 if(__wrap$00000003 != null)

　　 {

　　 ((IDisposable)__wrap$00000003).Dispose();

　　 }

　　 $_current = root.Item;

　　 $PC = 3;

　　 return true;

　　 ScanRight:

　　 $PC = 4;

　　 if(__wrap$00000004.MoveNext())

　　 {

　　 $_current = $item$00000002 = __wrap$00000004.get_Current();

　　 $PC = 5;

　　 return true;

　　 }

　　 else

　　 {

　　 $PC = -1;

　　 if(__wrap$00000004 != null)

　　 {

　　 ((IDisposable)__wrap$00000004).Dispose();

　　 }

　　 return false;

　　 }

　　 }

　　 // 实现 IDisposable 接口

　　 void Dispose()

　　 {

　　 switch($PC)

　　 {

　　 case 1:

　　 case 2:

　　 {

　　 $PC = -1;

　　 if(__wrap$00000003 != null)

　　 {

　　 ((IDisposable)__wrap$00000003).Dispose();

　　 }

　　 break;

　　 }

　　 case 4:

　　 case 5:

　　 {

　　 $PC = -1;

　　 if(__wrap$00000004 != null)

　　 {

　　 ((IDisposable)__wrap$00000004).Dispose();

　　 }

　　 break;

　　 }

　　 }

　　 }

　　 }

　　}

　　 通过上面的伪代码，我们可以看到，C# 2.0实际上是通过一个以$PC为自变量的有限状态机完成的递归迭代块，这可能是因为有限状态机可以很方便地通过程序自动生成吧。而Dispose()函数则负责处理状态机的中间变量。

　　 有兴趣进一步了解迭代特性的朋友，可以到Grant Ri的BLog上阅读Iterators相关文章。

　　 在了解了Iterators的实现原理后，再看那些讨论就不会被其表象所迷惑了