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

http://flier_lu.blogone.net/?id=1511638

    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的实现原理后，再看那些讨论就不会被其表象所迷惑了 :D

本文地址：http://com.8s8s.com/it/it44967.htm