位置: Linuxeden主页>新闻动态>

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

来源:InfoQ 作者:陈嘉栋
　　

前言

在我之前的一篇博客“细说C#：不是“栈类型”的值类型，从生命周期聊存储位置”的最后，我以总结和后记的方式介绍了一些迭代器的知识。但是觉得还是不够过瘾，很多需要说清楚的内容还是含糊不清，所以本文就专门写一下C#中的迭代器。

你好，迭代器

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

假设我们有一个数据容器（可能是Array，List，Tree等），对我们这些使用者来说，我们显然希望这个数据容器能提供一种无需了解它的内部实现就可以获取其元素的方法，无论它是Array还是List或者别的什么，我们希望可以通过相同的方法达到目的。

 

此时，迭代器模式（Iterator Pattern）便应运而生，它通过持有迭代状态，追踪当前元素并且识别下一个需要被迭代的元素，从而可以让使用者透过特定的界面巡访容器中的每个元素而不用了解底层的实现。

那么，在C#中，迭代器到底是以一个怎样的面目出现的呢？

如我们所知，它们被封装在IEnumerable和IEnumerator这两个接口中。（当然，还有它们的泛型形式，要注意的是泛型形式显然是强类型的。且IEnumerator\

 

为什么会有2个接口？

 

 

 

到此，各位看官是否和曾经的我有相同的疑惑呢？那就是为何IEnumerable自己不直接实现MoveNext()方法、提供Current属性呢？为何还需要一个额外的接口IEnumerator来专门做这个工作呢？

我们假设有两个不同的迭代器要对同一个序列进行迭代。当然，这种情况很常见，比如我们使用两个嵌套的foreach语句。我们自然希望两者相安无事，不要互相影响彼此。所以理所当然，我们需要保证这两个独立的迭代状态能够被正确地保存、处理。这也正是IEnumerator要做的工作。而为了不违背单一职责原则，不使IEnumerable拥有过多职责从而陷入分工不明的窘境，所以IEnumerable自己并没有实现MoveNext()方法。

迭代器的执行步骤

 

 

 

为了更直观地了解一个迭代器，我这里提供一个小例子。

using System;
using System.Collections.Generic;

class Class1
{ 
    static void Main()
    {
        foreach (string s in GetEnumerableTest())
        {
            Console.WriteLine(s);
        }
    }

     static IEnumerable<string> GetEnumerableTest()
    {
        yield return "begin";

        for (int i=0; i < 10; i++)
        {
            yield return i.ToString();
        }

        yield return "end";
    }
}

输出结果如图：

OK，那么我就给各位梳理一下这段代码的执行过程。

  1. Main调用GetEnumerableTest()方法。
  2. GetEnumerableTest()方法会为我们创建一个编译器生成的新的类”Class1/’c__Iterator0’”（本例中）的实例。注意，此时GetEnumerableTest()方法中，我们自己的代码尚未执行。
  3. Main调用MoveNext()方法。
  4. 迭代器开始执行，直到它遇到第一个yield return语句。此时迭代器会获取当前的值“begin”，并且返回true以告知此时还有数据。
  5. Main使用Current属性以获取数据，并打印出来。
  6. Main再次调用MoveNext()方法。
  7. 迭代器继续从上次遇到yield return的地方开始执行，并且和之前一样，直到遇到下一个yield return。
  8. 迭代器按照这种方式循环，直到MoveNext()方法返回false，以通知此时已经没有数据了。

以上简单地描述了这个例子中迭代器的执行过程。但是还有几点需要关注的，我想提醒各位注意。

  • 在第一次调用MoveNext()方法之前，在GetEnumerableTest中的代码不会执行。
  • 之后调用MoveNext()方法时，会从上次暂停（yield return）的地方开始。
  • 编译器会保证GetEnumerableTest方法中的局部变量能够被保留，换句话说，虽然本例中的i是值类型实例，但是它的值其实是被迭代器保存在堆上的，这样才能保证每次调用MoveNext时，它是可用的。这也是我之前的一篇文章中说迭代器块中的局部变量会被分配在堆上的原因。

好了，简单总结了一下C#中的迭代器的外观。接下来，我们继续向内部前进，来看看迭代器究竟是如何实现的。

0x02 原来是状态机呀

上一节我们已经从外部看到了IEnumerable和IEnumerator这两个接口的用法了，但是它们的内部到底是如何实现的呢？两者之间又有何区别呢？

既然要深入迭代器的内部，这就是一个不得不面对的问题。

那么我就写一个小程序，之后再通过反编译的方式，看看在我们手动写的代码背后，编译器究竟又给我们做了哪些工作吧。

为了简便起见，这个小程序仅仅实现一个按顺序返回0-9这10个数字的功能。

IEnumerator的内部实现

 

 

 

首先，我们定义一个返回IEnumerator的方法TestIterator()。

//IEnumerator<T>测试
using System;
using System.Collections;

class Test
{
    static IEnumerator<int> TestIterator()
    {
        for (int i = 0; i < 10; i++)
        {
            yield return i;
        }
    }
}

接下来，我们看看反编译之后的代码，探查一下编译器到底做了什么吧。

internal class Test
{
    // Methods 注，此时还没有执行任何我们写的代码
    private static IEnumerator<int> TestIterator()
    {
        return new <TestIterator>d__0(0);
    }

    // Nested Types 编译器生成的类，用来实现迭代器。
    [CompilerGenerated]
    private sealed class <TestIterator>d__0 : IEnumerator<int>, IEnumerator, IDisposable
    {
        // Fields 字段：state和current是默认出现的
        private int <>1__state;
        private int <>2__current;
        public int <i>5__1;//<i>5__1来自我们迭代器块中的局部变量

        // Methods 构造函数，初始化状态
        [DebuggerHidden]
        public <TestIterator>d__0(int <>1__state)
        {
            this.<>1__state = <>1__state;
        }
        // 几乎所有的逻辑在这里
        private bool MoveNext()
        {
            switch (this.<>1__state)
            {
                case 0:
                    this.<>1__state = -1;
                    this.<i>5__1 = 0;
                    while (this.<i>5__1 < 10)
                    {
                        this.<>2__current = this.<i>5__1;
                        this.<>1__state = 1;
                        return true;
                    Label_0046:
                        this.<>1__state = -1;
                        this.<i>5__1++;
                    }
                    break;

                case 1:
                    goto Label_0046;
            }
            return false;
        }

        [DebuggerHidden]
        void IEnumerator.Reset()
        {
            throw new NotSupportedException();
        }

        void IDisposable.Dispose()
        {
        }

        // Properties
        int IEnumerator<int>.Current
        {
            [DebuggerHidden]
            get
            {
                return this.<>2__current;
            }
        }

        object IEnumerator.Current
        {
            [DebuggerHidden]
            get
            {
                return this.<>2__current;
            }
        }
    }
}

我们先全面看一下反编译之后的代码，可以发现几乎所有的逻辑都发生在MoveNext()方法中。之后我们再详细介绍它，现在先从上到下把代码梳理一遍。

  1. 这段代码给人的第一印象就是命名似乎很不雅观。的确，这种在正常的C#代码中不会出现的命名，在编译器生成的代码中却是常常出现。因为这样就可以避免和已经存在的正常名字发生冲突。
  2. 调用TestIterator()方法的结果仅仅是调用了\

IEnumerator VS IEnumerable

 

 

 

依样画葫芦，这次我们仍然是写一个小程序，实现按顺序返回0～9这10个数字的功能，只不过返回类型变为IEnumerable\

状态管理

我们深入了迭代器的内部，发现了原来它的实现主要依靠的是一个状态机。那么，下面就让我继续和大伙聊聊这个状态机是如何管理状态的。

状态切换

 

 

 

根据Ecma-334标准，也就是C#语言标准的第26.2 Enumerator objects小节，我们可以知道迭代器有4种状态：

  1. before状态
  2. running状态
  3. suspended状态
  4. after状态

而其中before状态是作为初始状态出现的。

在讨论状态如何切换之前，我还要带领大家回想一下上面提到的，也就是在调用一个使用了迭代器块，返回类型为一个IEnumerator或IEnumerable接口的方法时，这个方法并不会立刻执行我们自己写的代码，而是会创建一个编译器生成的类的实例，之后当调用MoveNext()方法时（当然如果方法的返回类型是IEnumerable，则要先调用GetEnumerator()方法），我们的代码才会开始执行，直到遇到第一个yield return语句或yield break语句，此时会返回一个布尔值来判断迭代是否结束。当下次再调用MoveNext()方法时，我们的方法会继续从上一个yield return语句处开始执行。

为了能够直观地观察状态的切换，下面提供另一个例子：

class Test
{

    static IEnumerable<int> TestStateChange()
    {
        Console.WriteLine("----我TestStateChange是第一行代码");
        Console.WriteLine("----我是第一个yield return前的代码");
        yield return 1;
        Console.WriteLine("----我是第一个yield return后的代码");

        Console.WriteLine("----我是第二个yield return前的代码");
        yield return 2;
        Console.WriteLine("----我是第二个yield return前的代码");
    }

    static void Main()
    {
        Console.WriteLine("调用TestStateChange");
        IEnumerable<int> iteratorable = TestStateChange();
        Console.WriteLine("调用GetEnumerator");
        IEnumerator<int> iterator = iteratorable.GetEnumerator();
        Console.WriteLine("调用MoveNext()");
        bool hasNext = iterator.MoveNext();
        Console.WriteLine("是否有数据={0}; Current={1}", hasNext, iterator.Current);

        Console.WriteLine("第二次调用MoveNext");
        hasNext = iterator.MoveNext();
        Console.WriteLine("是否还有数据={0}; Current={1}", hasNext, iterator.Current);

        Console.WriteLine("第三次调用MoveNext");
        hasNext = iterator.MoveNext();
        Console.WriteLine("是否还有数据={0}", hasNext);
    }
}

运行这段代码看看结果如何：

可见，代码的执行顺序就是我刚刚总结的那样。那么我们将这段编译后的代码再反编译回C#，看看编译器到底是如何处理这里的状态切换的。

这里我们只关心两个方法，首先是GetEnumerator方法。其次是MoveNext方法。

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

观察GetEnumerator方法，我们可以发现：

  1. 此时的初始状态是-2；
  2. 不过一旦调用GetEnumerator，则会将状态置为0。也就是状态从最初的-2，在调用过GetEnumerator方法后变成了0。

我们再来看看MoveNext方法。

private bool MoveNext()
{
    switch (this.<>1__state)
    {
        case 0:
            this.<>1__state = -1;
            Console.WriteLine("----我TestStateChange是第一行代码");
            Console.WriteLine("----我是第一个yield return前的代码");
            this.<>2__current = 1;
            this.<>1__state = 1;
            return true;

        case 1:
            this.<>1__state = -1;
            Console.WriteLine("----我是第一个yield return后的代码");
            Console.WriteLine("----我是第二个yield return前的代码");
            this.<>2__current = 2;
            this.<>1__state = 2;
            return true;

        case 2:
            this.<>1__state = -1;
            Console.WriteLine("----我是第二个yield return前的代码");
            break;
    }
    return false;
}

由于第一次调用MoveNext方法发生在调用GetEnumerator方法之后，所以此时状态已经变成了0。

可以清晰地看到此时从0——>1——>2——>-1这样的状态切换过程。而且还要注意，每个分支中，this.\<>1__state都会首先被置为-1：this.\<>1__state = -1。之后才会根据不同的阶段赋值不同的值。而这些不同的值用来标识代码从哪里恢复执行。

我们再拿之前实现了按顺序返回0～9这10个数字的小程序的状态管理作为例子，来让我们更加深刻地理解迭代器除了刚刚的例子，还有什么手段可以用来实现“当下次再调用MoveNext()方法时，我们的方法会继续从上一个yield return语句处开始执行”这个功能的。

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

        case 1:
            goto Label_0046;
    }
    return false;
}

不错，此时状态机是靠着goto语句实现半路插入，进而实现了从yield return处继续执行的功能。

好吧，让我们总结一下关于迭代器内部状态机的状态切换。

  • -2状态：只有IEnumerable才有，表明在第一次调用GetEnumerator之前的状态。
  • -1状态：即上文中提到的C#语言标准中规定的Running状态，表明此时迭代器正在执行。当然，也会用于After状态，例如上例中的case 2中，this.\<>1__state被赋值为-1，但是此时迭代结束了。
  • 0状态：即上文中提到的Before状态，表明MoveNext()没有被调用过。
  • 正数（1，2，3…），主要用来标识从遇到yield之后，代码从哪里恢复执行。

总结

通过我上文的分析，可以看出迭代器的实现的确十分复杂。不过值得庆幸的是很多工作都由编译器在幕后为我们做好了。本文就到此结束。欢迎大家探讨。

转自 http://www.infoq.com/cn/articles/detailed-analysis-of-iterator?utm_campaign=infoq_content&utm_source=infoq&utm_medium=feed&utm_term=global


时间:2015-07-16 22:06 来源:InfoQ 作者:陈嘉栋 原文链接

好文,顶一下
(1)
100%
文章真差,踩一下
(0)
0%
------分隔线----------------------------


把开源带在你的身边-精美linux小纪念品
文章分类
软件导航
论坛导航
论坛精华
一周热点
无觅相关文章插件，快速提升流量