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

  1<itemtype>   
  2&gt;  {   
  3&gt;  IEnumerator<itemtype> GetEnumerator();   
  4&gt;  }   
  5&gt;  public interface IEnumerator<itemtype> : IDisposable   
  6&gt;  {   
  7&gt;  ItemType Current{get;}   
  8&gt;  bool MoveNext();   
  9&gt;  }   
 10&gt;  }   
 11&gt;   
 12&gt;   
 13&gt; ---  
 14  
 15  
 16  
 17这样一来即保障了遍历集合时的类型安全，又能够对集合的实际类型直接进行操作，避免冗余转换，提高了效率。   
 18
 19
 20&gt; **以下为引用：**
 21&gt;
 22&gt;&gt;   
 23&gt;  using System.Collections.Generic;   
 24&gt;    
 25&gt;  public class Tokens : IEnumerable<string>   
 26&gt;  {   
 27&gt;  ... // 实现 IEnumerable<string> 接口   
 28&gt;    
 29&gt;  Tokens f = new Tokens(...);   
 30&gt;    
 31&gt;  foreach (string item in f)   
 32&gt;  {   
 33&gt;  Console.WriteLine(item);   
 34&gt;  }   
 35&gt;  }   
 36&gt;   
 37&gt;   
 38&gt; ---  
 39  
 40  
 41  
 42上面的代码被自动转换为   
 43
 44
 45&gt; **以下为引用：**
 46&gt;
 47&gt;&gt;   
 48&gt;  Tokens f = new Tokens(...);   
 49&gt;    
 50&gt;  IEnumerator<string> enum = f.GetEnumerator();   
 51&gt;  try   
 52&gt;  {   
 53&gt;  do {   
 54&gt;  string item = enum.get_Current(); // 无需转换   
 55&gt;    
 56&gt;  Console.WriteLine(item);   
 57&gt;  } while(enum.MoveNext());   
 58&gt;  }   
 59&gt;  finally   
 60&gt;  {   
 61&gt;  if(enum) // 无需验证实现IEnumerator接口的类是否支持IDisposable接口，   
 62&gt;  // 因为所有由编译器自动生成的IEnumerator接口实现类都支持   
 63&gt;  {   
 64&gt;  ((IDisposable)enum).Dispose();   
 65&gt;  }   
 66&gt;  }   
 67&gt;   
 68&gt;   
 69&gt; ---  
 70  
 71  
 72  
 73  
 74除了遍历时的冗余转换降低性能外，C#现有版本另一个不爽之处在于实现IEnumerator接口实在太麻烦了。通常都是由一个内嵌类实现IEnumerator接口，而此内嵌类除了get_Current()函数外，其他部分的功能基本上都是相同的，如   
 75
 76
 77&gt; **以下为引用：**
 78&gt;
 79&gt;&gt;   
 80&gt;  public class Tokens : IEnumerable   
 81&gt;  {   
 82&gt;  public string[] elements;   
 83&gt;    
 84&gt;  Tokens(string source, char[] delimiters)   
 85&gt;  {   
 86&gt;  // Parse the string into tokens:   
 87&gt;  elements = source.Split(delimiters);   
 88&gt;  }   
 89&gt;    
 90&gt;  public IEnumerator GetEnumerator()   
 91&gt;  {   
 92&gt;  return new TokenEnumerator(this);   
 93&gt;  }   
 94&gt;    
 95&gt;  // Inner class implements IEnumerator interface:   
 96&gt;  private class TokenEnumerator : IEnumerator   
 97&gt;  {   
 98&gt;  private int position = -1;   
 99&gt;  private Tokens t;   
100&gt;    
101&gt;  public TokenEnumerator(Tokens t)   
102&gt;  {   
103&gt;  this.t = t;   
104&gt;  }   
105&gt;    
106&gt;  // Declare the MoveNext method required by IEnumerator:   
107&gt;  public bool MoveNext()   
108&gt;  {   
109&gt;  if (position &lt; t.elements.Length - 1)   
110&gt;  {   
111&gt;  position++;   
112&gt;  return true;   
113&gt;  }   
114&gt;  else   
115&gt;  {   
116&gt;  return false;   
117&gt;  }   
118&gt;  }   
119&gt;    
120&gt;  // Declare the Reset method required by IEnumerator:   
121&gt;  public void Reset()   
122&gt;  {   
123&gt;  position = -1;   
124&gt;  }   
125&gt;    
126&gt;  // Declare the Current property required by IEnumerator:   
127&gt;  public object Current   
128&gt;  {   
129&gt;  get // get_Current函数   
130&gt;  {   
131&gt;  return t.elements[position];   
132&gt;  }   
133&gt;  }   
134&gt;  }   
135&gt;  ...   
136&gt;  }   
137&gt;   
138&gt;   
139&gt; ---  
140  
141  
142  
143内嵌类TokenEnumerator的position和Tokens实际上是每个实现IEnumerator接口的类共有的，只是Current属性的get函数有所区别而已。这方面C# 2.0做了很大的改进，增加了yield关键字的支持，允许代码逻辑上的重用。上面冗长的代码在C# 2.0中只需要几行，如   
144
145
146&gt; **以下为引用：**
147&gt;
148&gt;&gt;   
149&gt;  using System.Collections.Generic;   
150&gt;    
151&gt;  public class Tokens : IEnumerable<string>   
152&gt;  {   
153&gt;  public IEnumerator<string> GetEnumerator()   
154&gt;  {   
155&gt;  for(int i = 0; i<elements.length; i++)="">  yield elements[i];   
156&gt;  }   
157&gt;  ...   
158&gt;  }   
159&gt;   
160&gt;   
161&gt; ---  
162  
163  
164  
165GetEnumerator函数是一个C# 2.0支持的迭代块(iterator block)，通过yield告诉编译器在什么时候返回什么值，再由编译器自动完成实现IEnumerator<string>接口的薄记工作。而yield break语句支持从迭代块中直接结束，如   
166
167
168&gt; **以下为引用：**
169&gt;
170&gt;&gt;   
171&gt;  public IEnumerator<int> GetEnumerator()   
172&gt;  {   
173&gt;  for(int i = 1;i&lt; 5;i++)   
174&gt;  {   
175&gt;  yield return i;   
176&gt;  if(i &gt; 2)   
177&gt;  yield break; // i &gt; 2 时结束遍历   
178&gt;  }   
179&gt;  }   
180&gt;   
181&gt;   
182&gt; ---  
183  
184  
185  
186这样一来，很容易就能实现IEnumerator接口，并可以方便地支持在一个类中提供多种枚举方式，如   
187
188
189&gt; **以下为引用：**
190&gt;
191&gt;&gt;   
192&gt;  public class CityCollection   
193&gt;  {   
194&gt;  string[] m_Cities = {"New York","Paris","London"};   
195&gt;  public IEnumerable<string> Reverse   
196&gt;  {   
197&gt;  get   
198&gt;  {   
199&gt;  for(int i=m_Cities.Length-1; i&gt;= 0; i--)   
200&gt;  yield m_Cities[i];   
201&gt;  }   
202&gt;  }   
203&gt;  }   
204&gt;   
205&gt;   
206&gt; ---  
207  
208  
209  
210  
211接下来我们看看如此方便的语言特性背后，编译器为我们做了哪些工作。以上面那个支持IEnumerable<string>接口的Tokens类为例，GetEnumerator函数的代码被编译器用一个类包装起来，伪代码如下   
212
213
214&gt; **以下为引用：**
215&gt;
216&gt;&gt;   
217&gt;  public class Tokens : IEnumerable<string>   
218&gt;  {   
219&gt;  private sealed class GetEnumerator$00000000__IEnumeratorImpl   
220&gt;  : IEnumerator<string>, IEnumerator, IDisposable   
221&gt;  {   
222&gt;  private int $PC = 0;   
223&gt;  private string $_current;   
224&gt;  private Tokens <this>;   
225&gt;  public int i$00000001 = 0;   
226&gt;    
227&gt;  // 实现 IEnumerator<string> 接口   
228&gt;  string IEnumerator<string>.get_Current()   
229&gt;  {   
230&gt;  return $_current;   
231&gt;  }   
232&gt;    
233&gt;  bool IEnumerator<string>.MoveNext()   
234&gt;  {   
235&gt;  switch($PC)   
236&gt;  {   
237&gt;  case 0:   
238&gt;  {   
239&gt;  $PC = -1;   
240&gt;  i$00000001 = 0;   
241&gt;  break;   
242&gt;  }   
243&gt;  case 1:   
244&gt;  {   
245&gt;  $PC = -1;   
246&gt;  i$00000001++;   
247&gt;  break;   
248&gt;  }   
249&gt;  default:   
250&gt;  {   
251&gt;  return false;   
252&gt;  }   
253&gt;  }   
254&gt;    
255&gt;  if(i$00000001 &lt; <this>.elements.Length)   
256&gt;  {   
257&gt;  $_current = <this>.elements[i$00000001];   
258&gt;  $PC = 1;   
259&gt;    
260&gt;  return true;   
261&gt;  }   
262&gt;  else   
263&gt;  {   
264&gt;  return false;   
265&gt;  }   
266&gt;  }   
267&gt;    
268&gt;  // 实现 IEnumerator 接口   
269&gt;  void IEnumerator.Reset()   
270&gt;  {   
271&gt;  throw new Exception();   
272&gt;  }   
273&gt;    
274&gt;  string IEnumerator.get_Current()   
275&gt;  {   
276&gt;  return $_current;   
277&gt;  }   
278&gt;    
279&gt;  bool IEnumerator.MoveNext()   
280&gt;  {   
281&gt;  return IEnumerator<string>.MoveNext(); // 调用 IEnumerator<string> 接口的实现   
282&gt;  }   
283&gt;    
284&gt;  // 实现 IDisposable 接口   
285&gt;  void Dispose()   
286&gt;  {   
287&gt;  }   
288&gt;  }   
289&gt;    
290&gt;  public IEnumerator<string> GetEnumerator()   
291&gt;  {   
292&gt;  GetEnumerator$00000000__IEnumeratorImpl impl = new GetEnumerator$00000000__IEnumeratorImpl();   
293&gt;    
294&gt;  impl.<this> = this;   
295&gt;    
296&gt;  return impl;   
297&gt;  }   
298&gt;  }   
299&gt;   
300&gt;   
301&gt; ---  
302  
303  
304  
305从上面的伪代码中我们可以看到，C# 2.0编译器实际上维护了一个和我们前面实现IEnumerator接口的TokenEnumerator类非常类似的内部类，用来封装IEnumerator<string>接口的实现。而这个内嵌类的实现逻辑，则根据GetEnumerator定义的yield返回地点决定。   
306我们接下来看一个较为复杂的迭代块的实现，支持递归迭代(Recursive Iterations)，代码如下：   
307
308
309&gt; **以下为引用：**
310&gt;
311&gt;&gt;   
312&gt;  using System;   
313&gt;  using System.Collections.Generic;   
314&gt;    
315&gt;  class Node<t>   
316&gt;  {   
317&gt;  public Node<t> LeftNode;   
318&gt;  public Node<t> RightNode;   
319&gt;  public T Item;   
320&gt;  }   
321&gt;    
322&gt;  public class BinaryTree<t>   
323&gt;  {   
324&gt;  Node<t> m_Root;   
325&gt;    
326&gt;  public void Add(params T[] items)   
327&gt;  {   
328&gt;  foreach(T item in items)   
329&gt;  Add(item);   
330&gt;  }   
331&gt;    
332&gt;  public void Add(T item)   
333&gt;  {   
334&gt;  // ...   
335&gt;  }   
336&gt;    
337&gt;  public IEnumerable<t> InOrder   
338&gt;  {   
339&gt;  get   
340&gt;  {   
341&gt;  return ScanInOrder(m_Root);   
342&gt;  }   
343&gt;  }   
344&gt;    
345&gt;  IEnumerable<t> ScanInOrder(Node<t> root)   
346&gt;  {   
347&gt;  if(root.LeftNode != null)   
348&gt;  {   
349&gt;  foreach(T item in ScanInOrder(root.LeftNode))   
350&gt;  {   
351&gt;  yield item;   
352&gt;  }   
353&gt;  }   
354&gt;    
355&gt;  yield root.Item;   
356&gt;    
357&gt;  if(root.RightNode != null)   
358&gt;  {   
359&gt;  foreach(T item in ScanInOrder(root.RightNode))   
360&gt;  {   
361&gt;  yield item;   
362&gt;  }   
363&gt;  }   
364&gt;  }   
365&gt;  }   
366&gt;   
367&gt;   
368&gt; ---  
369  
370  
371  
372BinaryTree<t>提供了一个支持IEnumerable<t>接口的InOrder属性，通过ScanInOrder函数遍历整个二叉树。因为实现IEnumerable<t>接口的不是类本身，而是一个属性，所以编译器首先要生成一个内嵌类支持IEnumerable<t>接口。伪代码如下   
373
374
375&gt; **以下为引用：**
376&gt;
377&gt;&gt;   
378&gt;  public class BinaryTree<t>   
379&gt;  {   
380&gt;  private sealed class ScanInOrder$00000000__IEnumeratorImpl<t>   
381&gt;  : IEnumerator<t>, IEnumerator, IDisposable   
382&gt;  {   
383&gt;  BinaryTree<t> <this>;   
384&gt;  Node<t> root;   
385&gt;    
386&gt;  // ...   
387&gt;  }   
388&gt;    
389&gt;  private sealed class ScanInOrder$00000000__IEnumerableImpl<t>   
390&gt;  : IEnumerable<t>, IEnumerable   
391&gt;  {   
392&gt;  BinaryTree<t> <this>;   
393&gt;  Node<t> root;   
394&gt;    
395&gt;  IEnumerator<t> IEnumerable<t>.GetEnumerator()   
396&gt;  {   
397&gt;  ScanInOrder$00000000__IEnumeratorImpl<t> impl = new ScanInOrder$00000000__IEnumeratorImpl<t>();   
398&gt;    
399&gt;  impl.<this> = this.<this>;   
400&gt;  impl.root = this.root;   
401&gt;    
402&gt;  return impl;   
403&gt;  }   
404&gt;    
405&gt;  IEnumerator IEnumerable.GetEnumerator()   
406&gt;  {   
407&gt;  ScanInOrder$00000000__IEnumeratorImpl<t> impl = new ScanInOrder$00000000__IEnumeratorImpl<t>();   
408&gt;    
409&gt;  impl.<this> = this.<this>;   
410&gt;  impl.root = this.root;   
411&gt;    
412&gt;  return impl;   
413&gt;  }   
414&gt;  }   
415&gt;    
416&gt;  IEnumerable<t> ScanInOrder(Node<t> root)   
417&gt;  {   
418&gt;  ScanInOrder$00000000__IEnumerableImpl<t> impl = new ScanInOrder$00000000__IEnumerableImpl<t>();   
419&gt;    
420&gt;  impl.<this> = this;   
421&gt;  impl.root = root;   
422&gt;    
423&gt;  return impl;   
424&gt;  }   
425&gt;  }   
426&gt;   
427&gt;   
428&gt; ---  
429  
430  
431  
432因为ScanInOrder函数内容需要用到root参数，故而IEnumerable<t>和IEnumerator<t>接口的包装类都需要有一个root字段，保存传入ScanInOrder函数的参数，并传递给最终的实现函数。   
433实现IEnumerator<t>接口的内嵌包装类ScanInOrder$00000000__IEnumeratorImpl<t>实现原理与前面例子里的大致相同，不同的是程序逻辑大大复杂化，并且需要用到IDisposable接口完成资源的回收。   
434
435
436&gt; **以下为引用：**
437&gt;
438&gt;&gt;   
439&gt;  public class BinaryTree<t>   
440&gt;  {   
441&gt;  private sealed class GetEnumerator$00000000__IEnumeratorImpl   
442&gt;  : IEnumerator<t>, IEnumerator, IDisposable   
443&gt;  {   
444&gt;  private int $PC = 0;   
445&gt;  private string $_current;   
446&gt;  private Tokens <this>;   
447&gt;  public int i$00000001 = 0;   
448&gt;    
449&gt;  public IEnumerator<t> __wrap$00000003;   
450&gt;  public IEnumerator<t> __wrap$00000004;   
451&gt;  public T item$00000001;   
452&gt;  public T item$00000002;   
453&gt;  public Node<t> root;   
454&gt;    
455&gt;  // 实现 IEnumerator<t> 接口   
456&gt;  string IEnumerator<t>.get_Current()   
457&gt;  {   
458&gt;  return $_current;   
459&gt;  }   
460&gt;    
461&gt;  bool IEnumerator<t>.MoveNext()   
462&gt;  {   
463&gt;  switch($PC)   
464&gt;  {   
465&gt;  case 0:   
466&gt;  {   
467&gt;  $PC = -1;   
468&gt;  if(root.LeftNode != null)   
469&gt;  {   
470&gt;  __wrap$00000003 = <this>.ScanInOrder(root.LeftNode).GetEnumerator();   
471&gt;    
472&gt;  goto ScanLeft;   
473&gt;  }   
474&gt;  else   
475&gt;  {   
476&gt;  goto GetItem;   
477&gt;  }   
478&gt;  }   
479&gt;  case 1:   
480&gt;  {   
481&gt;  return false;   
482&gt;  }   
483&gt;  case 2:   
484&gt;  {   
485&gt;  goto ScanLeft;   
486&gt;  }   
487&gt;  case 3:   
488&gt;  {   
489&gt;  $PC = -1;   
490&gt;  if(root.RightNode != null)   
491&gt;  {   
492&gt;  __wrap$00000004 = <this>.ScanInOrder(root.RightNode).GetEnumerator();   
493&gt;    
494&gt;  goto ScanRight;   
495&gt;  }   
496&gt;  else   
497&gt;  {   
498&gt;  return false;   
499&gt;  }   
500&gt;  break;   
501&gt;  }   
502&gt;  case 4:   
503&gt;  {   
504&gt;  return false;   
505&gt;  }   
506&gt;  case 5:   
507&gt;  {   
508&gt;  goto ScanRight;   
509&gt;  }   
510&gt;  default:   
511&gt;  {   
512&gt;  return false;   
513&gt;  }   
514&gt;  ScanLeft:   
515&gt;  $PC = 1;   
516&gt;    
517&gt;  if(__wrap$00000003.MoveNext())   
518&gt;  {   
519&gt;  $_current = item$00000001 = __wrap$00000003.get_Current();   
520&gt;  $PC = 2;   
521&gt;  return true;   
522&gt;  }   
523&gt;    
524&gt;  GetItem:   
525&gt;  $PC = -1;   
526&gt;  if(__wrap$00000003 != null)   
527&gt;  {   
528&gt;  ((IDisposable)__wrap$00000003).Dispose();   
529&gt;  }   
530&gt;  $_current = root.Item;   
531&gt;  $PC = 3;   
532&gt;  return true;   
533&gt;    
534&gt;  ScanRight:   
535&gt;  $PC = 4;   
536&gt;    
537&gt;  if(__wrap$00000004.MoveNext())   
538&gt;  {   
539&gt;  $_current = $item$00000002 = __wrap$00000004.get_Current();   
540&gt;  $PC = 5;   
541&gt;  return true;   
542&gt;  }   
543&gt;  else   
544&gt;  {   
545&gt;  $PC = -1;   
546&gt;  if(__wrap$00000004 != null)   
547&gt;  {   
548&gt;  ((IDisposable)__wrap$00000004).Dispose();   
549&gt;  }   
550&gt;  return false;   
551&gt;  }   
552&gt;  }   
553&gt;  // 实现 IDisposable 接口   
554&gt;  void Dispose()   
555&gt;  {   
556&gt;  switch($PC)   
557&gt;  {   
558&gt;  case 1:   
559&gt;  case 2:   
560&gt;  {   
561&gt;  $PC = -1;   
562&gt;  if(__wrap$00000003 != null)   
563&gt;  {   
564&gt;  ((IDisposable)__wrap$00000003).Dispose();   
565&gt;  }   
566&gt;  break;   
567&gt;  }   
568&gt;  case 4:   
569&gt;  case 5:   
570&gt;  {   
571&gt;  $PC = -1;   
572&gt;  if(__wrap$00000004 != null)   
573&gt;  {   
574&gt;  ((IDisposable)__wrap$00000004).Dispose();   
575&gt;  }   
576&gt;  break;   
577&gt;  }   
578&gt;  }   
579&gt;  }   
580&gt;  }   
581&gt;  }   
582&gt;   
583&gt;   
584&gt; ---  
585  
586  
587  
588通过上面的伪代码，我们可以看到，C# 2.0实际上是通过一个以$PC为自变量的有限状态机完成的递归迭代块，这可能是因为有限状态机可以很方便地通过程序自动生成吧。而Dispose()函数则负责处理状态机的中间变量。   
589  
590有兴趣进一步了解迭代特性的朋友，可以到  Grant Ri的BLog  上阅读  Iterators相关文章  。   
591在了解了Iterators的实现原理后，再看那些讨论就不会被其表象所迷惑了 :D</this></this></t></t></t></t></t></t></this></t></t></t></t></t></t></this></t></t></t></t></this></this></t></t></this></this></t></t></t></t></t></this></t></t></t></t></this></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></string></this></string></string></string></this></this></string></string></string></this></string></string></string></string></int></string></elements.length;></string></string></string></string></string></itemtype></itemtype></itemtype>