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

01-28

0x00 前言

在我之前的一篇博客《細說C#：不是「棧類型」的值類型，從生命周期聊存儲位置》的最後，我以總結和後記的方式涉及到一部分迭代器的知識。但是覺得還是不夠過癮，很多需要說清楚的內容還是含糊不清，所以本文就專門寫一下c#中的迭代器吧。

0x01 你好，迭代器

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

假設我們有一個數據容器（可能是Array，List，Tree等等），對我們這些使用者來說，我們顯然希望這個數據容器能提供一種無需了解它的內部實現就可以獲取其元素的方法，無論它是Array還是List或者別的什麼，我們希望可以通過相同的方法達到我們的目的。

此時，迭代器模式（iterator pattern）便應運而生，它通過持有迭代狀態，追蹤當前元素並且識別下一個需要被迭代的元素，從而可以讓使用者透過特定的界面巡訪容器中的每一個元素而不用了解底層的實現。nn

那麼，在c#中，迭代器到底是以一個怎樣的面目出現的呢？

如我們所知，它們被封裝在IEnumerable和IEnumerator這兩個介面中（當然，還有它們的泛型形式，要注意的是泛型形式顯然是強類型的。且IEnumerator<T>實現了IDisposable介面）。

IEnumerable非泛型形式:

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

IEnumerator非泛型形式:

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

IEnumerable泛型形式:

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

IEnumerator泛型形式:

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

IEnumerable介面定義了一個可以獲取IEnumerator的方法——GetEnumerator()。

而IEnumerator則在目標序列上實現循環迭代（使用MoveNext()方法，以及Current屬性來實現），直到你不再需要任何數據或者沒有數據可以被返回。使用這個介面，可以保證我們能夠實現常見的foreach循環。

為什麼會有2個介面？

到此，各位看官是否和曾經的我有相同的疑惑呢？那就是為何IEnumerable自己不直接實現MoveNext()方法、提供Current屬性呢？為何還需要額外的一個介面IEnumerator來專門做這個工作？

OK，假設有兩個不同的迭代器要對同一個序列進行迭代。當然，這種情況很常見，比如我們使用兩個嵌套的foreach語句。我們自然希望兩者相安無n事，不要互相影響彼此。所以自然而然的，我們需要保證這兩個獨立的迭代狀態能夠被正確的保存、處理。這也正是IEnumerator要做的工作。而為了不n違背單一職責原則，不使IEnumerable擁有過多職責從而陷入分工不明的窘境，所以IEnumerable自己並沒有實現MoveNext()方n法。

迭代器的執行步驟

為了更直觀的了解一個迭代器，我這裡提供一個小例子。

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

輸出結果如圖：

nnOK，那麼我就給各位捋一下這段代碼的執行過程。

OK，那麼我就給各位捋一下這段代碼的執行過程。nn

Main調用GetEnumerableTest()方法。
GetEnumerableTest()方法會為我們創建一個編譯器生成的新的類」Class1/』c__Iterator0』」（本例中）的實例。注意，此時GetEnumerableTest()方法中，我們自己的代碼尚未執行。
Main調用MoveNext()方法。
迭代器開始執行，直到它遇到第一個yield return語句。此時迭代器會獲取當前的值是「begin」，並且返回true以告知此時還有數據。
Main使用Current屬性以獲取數據，並列印出來。
Main再次調用MoveNext()方法。
迭代器繼續從上次遇到yield return的地方開始執行，並且和之前一樣，直到遇到下一個yield return。
迭代器按照這種方式循環，直到MoveNext()方法返回false，以告知此時已經沒有數據了。

這個例子中迭代器的執行過程，我已經給各位看官簡單的描述了一下。但是還有幾點需要關注的，我也想提醒各位注意一下。

在第一次調用MoveNext()方法之前，我們自己在GetEnumerableTest中的代碼不會執行。
之後調用MoveNext()方法時，會從上次暫停（yield return）的地方開始。
編譯器會保證GetEnumerableTest方法中的局部變數能夠被保留，換句話說，雖然本例中的i是值類型實例，但是它的值其實是被迭代器n保存在堆上的，這樣才能保證每次調用MoveNext時，它是可用的。這也是我之前的一篇文章中說迭代器塊中的局部變數會被分配在堆上的原因。

好了，簡單總結了一下C#中的迭代器的外觀。那麼接下來，我們繼續向內部前進，來看看迭代器究竟是如何實現的。

0x02 原來是狀態機呀

上一節我們已經從外部看到了IEnumerable和IEnumerator這兩個介面的用法了，但是它們的內部到底是如何實現的呢？兩者之間又有何區別呢？

既然要深入迭代器的內部，這就是一個不得不面對的問題。

那麼我就寫一個小程序，之後再通過反編譯的方式，看看在我們自己手動寫的代碼背後，編譯器究竟又給我們做了哪些工作吧。

為了簡便起見，這個小程序僅僅實現一個按順序返回0-9這10個數字的功能。

IEnumerator的內部實現

首先，我們定義一個返回IEnumerator的方法TestIterator()。

//IEnumerator<T>測試nusing System;nusing System.Collections;nnclass Testn{n static IEnumerator<int> TestIterator()n {n for (int i = 0; i < 10; i++)n {n yield return i;n }n }n}n

接下來，我們看看反編譯之後的代碼，探查一下編譯器到底為我們做了什麼吧。

internal class Testn{n // Methods 注，此時還沒有執行任何我們寫的代碼n private static IEnumerator<int> TestIterator()n {n return new <TestIterator>d__0(0);n }nn // Nested Types 編譯器生成的類，用來實現迭代器。n [CompilerGenerated]n private sealed class <TestIterator>d__0 : IEnumerator<int>, IEnumerator, IDisposablen {n // Fields 欄位：state和current是默認出現的n private int <>1__state;n private int <>2__current;n public int 5__1;//5__1來自我們迭代器塊中的局部變數nn // Methods 構造函數，初始化狀態n [DebuggerHidden]n public <TestIterator>d__0(int <>1__state)n {n this.<>1__state = <>1__state;n }n // 幾乎所有的邏輯在這裡n private bool MoveNext()n {n switch (this.<>1__state)n {n case 0:n this.<>1__state = -1;n this.5__1 = 0;n while (this.5__1 < 10)n {n this.<>2__current = this.5__1;n this.<>1__state = 1;n return true;n Label_0046:n this.<>1__state = -1;n this.5__1++;n }n break;nn case 1:n goto Label_0046;n }n return false;n }nn [DebuggerHidden]n void IEnumerator.Reset()n {n throw new NotSupportedException();n }nn void IDisposable.Dispose()n {n }nn // Propertiesn int IEnumerator<int>.Currentn {n [DebuggerHidden]n getn {n return this.<>2__current;n }n }nn object IEnumerator.Currentn {n [DebuggerHidden]n getn {n return this.<>2__current;n }n }n }n}n

我們先全面的看一下反編譯之後的代碼，可以發現幾乎所有的邏輯都發生在MoveNext()方法中。那麼之後我們再詳細介紹下它，現在我們先從上到下把代碼捋一遍。

這段代碼給人的第一印象就是命名似乎很不雅觀。的確，這種在正常的C#代碼中不會出現的命名，在編譯器生成的代碼中卻是常常出現。因為這樣就可以避免和已經存在的正常名字發生衝突的可能性。
調用TestIterator()方法的結果僅僅是調用了<TestIterator>d__0（編譯器生成的用來實現迭代器的類）的構造函數。而這個構造函數會設置迭代器的初始狀態，此時的參數為0，而構造函數會將0賦值給記錄迭代器狀態的欄位：this.<>1__state = <>1__state;。注意，此時我們自己的代碼並沒有執行。
<TestIterator>d__0這個類實現了3個介面：IEnumerator<int>， IEnumerator， IDisposable。
IDisposable的實現十分重要。因為foreach語句會在它自己的finally代碼塊中調用實現了IDisposable介面的迭代器的Dispose方法。
<TestIterator>d__0類有3個欄位：<>1__state，<>2__current， 5__1。其中，<>1__state私有欄位標識迭代器的狀態，<>2__current私有欄位則追蹤當前的值，而5__1共有欄位則是我們在迭代器塊中定義的局部變數i。
MoveNext()方法的實現則依託與switch語句。根據狀態機的狀態，執行不同的代碼。
在本例中Dispose方法什麼都沒有做。
在IEnumerator和IEnumerator<int>的實現中，Current都是單純的返回<>2__current的值。

OK，IEnumerator介面我們看完了。下面再來看看另一個介面IEnumerable吧。

IEnumerator VS IEnumerable

依樣畫葫蘆，這次我們仍然是寫一個實現按順序返回0-9這10個數字的功能的小程序，只不過返回類型變為IEnumerable<T>。

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

之後，我們同樣通過反編譯，看看編譯器又背著我們做了什麼。

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

看到反編譯出的代碼，我們就很容易能對比出區別。

<TestIterator>d__0類不僅實現了IEnumerable<int> 介面，而且還實現了IEnumerator<int>介面。
IEnumerator和IEnumerator<int>的實現都和上面一樣。IEnumerator的Reset方法會拋出NotSupportedException異常，而IEnumerator和IEnumerator<int>的Current仍舊會返回<>2__current欄位的值。
TestIterator()方法調用<TestIterator>d__0類的構造函數時，傳入的參數由上面的0變成了-2：new <TestIterator>d__0(-2);。也就是說此時的初始狀態是-2。
又多了一個新的私有欄位<>l__initialThreadId，且會在<TestIterator>d__0的構造函數中被賦值，用來標識創建該實例的線程。
實現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()n{n if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))n {n this.<>1__state = 0;n return this;n }n return new Test.<TestIterator>d__0(0);n}n

我們可以發現，-2這個狀態，也就是此時的初始狀態，表明了GetEnumerator()方法還沒有執行。而0這個狀態，則表明已經準備好了迭代，但是MoveNext()尚未調用過。

當在不同的線程上調用GetEnumerator方法或者是狀態不是-2（證明已經不是初始狀態了），則GetEnumerator方法會返回一個<TestIterator>d__0類的新實例用來保存不同的狀態。

0x03 狀態管理

OK，我們深入了迭代器的內部，發現了原來它的實現主要依靠的是一個狀態機。那麼，下面就讓我繼續和大夥聊聊這個狀態機是如何管理狀態的。

狀態切換

根據Ecma-334標準，也就是c#語言標準的第26.2 Enumerator objects小節，我們可以知道迭代器有4種可能狀態：

before狀態
running狀態
suspended狀態
after狀態

而其中before狀態是作為初始狀態出現的。

在我們討論狀態如何切換之前，我還要帶領大家回想一下上面提到的，也就是在調用一個使用了迭代器塊，返回類型為一個IEnumerator或nIEnumerable介面的方法時，這個方法並非立刻執行我們自己寫的代碼的。而是會創建一個編譯器生成的類的實例，之後當調用MoveNext()方n法時（當然如果方法的返回類型是IEnumerable，則要先調用GetEnumerator()方法），我們的代碼才會開始執行，直到遇到第一個nyield return語句或yield nbreak語句，此時會返回一個布爾值來判斷迭代是否結束。當下次再調用MoveNext()方法時，我們的方法會繼續從上一個yield nreturn語句處開始執行。

為了能夠直觀的觀察狀態的切換，下面我提供另一個例子：

class Testn{nn static IEnumerable<int> TestStateChange()n {n Console.WriteLine("----我TestStateChange是第一行代碼");n Console.WriteLine("----我是第一個yield return前的代碼");n yield return 1;n Console.WriteLine("----我是第一個yield return後的代碼");nn Console.WriteLine("----我是第二個yield return前的代碼");n yield return 2;n Console.WriteLine("----我是第二個yield return前的代碼");n }nn static void Main()n {n Console.WriteLine("調用TestStateChange");n IEnumerable<int> iteratorable = TestStateChange();n Console.WriteLine("調用GetEnumerator");n IEnumerator<int> iterator = iteratorable.GetEnumerator();n Console.WriteLine("調用MoveNext()");n bool hasNext = iterator.MoveNext();n Console.WriteLine("是否有數據={0}; Current={1}", hasNext, iterator.Current);nn Console.WriteLine("第二次調用MoveNext");n hasNext = iterator.MoveNext();n Console.WriteLine("是否還有數據={0}; Current={1}", hasNext, iterator.Current);nn Console.WriteLine("第三次調用MoveNext");n hasNext = iterator.MoveNext();n Console.WriteLine("是否還有數據={0}", hasNext);n }n}n

之後，我們運行這段代碼看看結果如何。

可見，代碼的執行順序就是我剛剛總結的那樣。那麼我們將這段編譯後的代碼再反編譯回C#，看看編譯器到底是如何處理這裡的狀態切換的。

這裡我們只關心兩個方法，首先是GetEnumerator方法。其次是MoveNext方法。

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

看GetEnumerator方法，我們可以發現：

此時的初始狀態是-2。
不過一旦調用GetEnumerator，則會將狀態置為0。也就是狀態從最初的-2，在調用過GetEnumerator方法後變成了0。

我們再來看看MoveNext方法。

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

由於第一次調用MoveNext方法發生在調用GetEnumerator方法之後，所以此時狀態已經變成了0。

可以清晰的看到此時從0——>1——>2——>-1這樣的狀態切換過程。而且還要注意，每個分支中，this.<>1__state都會首先被置為-1：this.<>1__state = -1。之後才會根據不同的階段賦值不同的值。而這些不同的值也就用來標識代碼從哪裡恢復執行。

我們再拿之前實現了按順序返回0-9這10個數字的小程序的狀態管理作為例子，來讓我們更加深刻的理解迭代器除了剛剛的例子，還有什麼手段可以用來實現「當下次再調用MoveNext()方法時，我們的方法會繼續從上一個yield return語句處開始執行。」這一個功能的。

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

不錯，此時狀態機是靠著goto語句實現半路插入，進而實現了從yield return處繼續執行的功能。

好吧，讓我們總結一下關於迭代器內部狀態機的狀態切換：

-2狀態：只有IEnumerable才有，表明在第一次調用GetEnumerator之前的狀態。
-1狀態：即上文中提到的C#語言標準中規定的Running狀態，表明此時迭代器正在執行。當然，也會用於After狀態，例如上例中的case 2中，this.<>1__state被賦值為-1，但是此時迭代結束了。
0狀態：即上文中提到的Before狀態，表明MoveNext()還一次都沒有調用過。
正數（1，2，3…），主要用來標識從遇到yield之後，代碼從哪裡恢復執行。

0x04 總結

通過我上文的分析，可以看出迭代器的實現的確十分複雜。不過值得慶幸的是很多工作都由編譯器在幕後為我們做好了。那麼，本文就到此結束。歡迎大家探討。