程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C# 2.0 中Iterators的改進與實現原理淺析

C# 2.0 中Iterators的改進與實現原理淺析

編輯：關於C語言

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