BT

如何利用碎片时间提升技术认知与能力? 点击获取答案

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

| 作者 陈嘉栋 关注 0 他的粉丝 发布于 2015年7月17日. 估计阅读时间: 44 分钟 | GMTC大前端的下一站,PWA、Web框架、Node等最新最热的大前端话题邀你一起共同探讨。

0x00 前言

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

0x01 你好,迭代器

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

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

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

那么,在c#中,迭代器到底是以一个怎样的面目出现的呢?

如我们所知,它们被封装在IEnumerable和IEnumerator这两个接口中(当然,还有它们的泛型形式,要注意的是泛型形式显然是强类型的。且IEnumerator<T>实现了IDisposable接口)。

IEnumerable非泛型形式:

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

IEnumerator非泛型形式:

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

IEnumerable泛型形式:

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

IEnumerator泛型形式:

//IEnumerator泛型形式
public interface IEnumerator<out T> : IDisposable, IEnumerator
{

    void Dispose(); 
    Object Current {get;} 
    T Current {get;}
    bool MoveNext(); 
    void Reset(); 
}

[ComVisibleAttribute(true)]
public interface IDisposable
{
    void Dispose();
}

IEnumerable接口定义了一个可以获取IEnumerator的方法——GetEnumerator()。

而IEnumerator则在目标序列上实现循环迭代(使用MoveNext()方法,以及Current属性来实现),直到你不再需要任何数据或者没有数据可以被返回。使用这个接口,可以保证我们能够实现常见的foreach循环。

为什么会有2个接口?

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

OK,假设有两个不同的迭代器要对同一个序列进行迭代。当然,这种情况很常见,比如我们使用两个嵌套的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()方法的结果仅仅是调用了<TestIterator>d__0(编译器生成的用来实现迭代器的类)的构造函数。而这个构造函数会设置迭代器的初始状态,此时的参数为0,而构造函数会将0赋值给记录迭代器状态的字段:this.<>1__state = <>1__state;。注意,此时我们自己的代码并没有执行。
  3. <TestIterator>d__0这个类实现了3个接口:IEnumerator<int>, IEnumerator, IDisposable。
  4. IDisposable的实现十分重要。因为foreach语句会在它自己的finally代码块中调用实现了IDisposable接口的迭代器的Dispose方法。
  5. <TestIterator>d__0类有3个字段:<>1__state<>2__current<i>5__1。其中,<>1__state私有字段标识迭代器的状态,<>2__current私有字段则追踪当前的值,而<i>5__1共有字段则是我们在迭代器块中定义的局部变量i。
  6. MoveNext()方法的实现则依托与switch语句。根据状态机的状态,执行不同的代码。
  7. 在本例中Dispose方法什么都没有做。
  8. 在IEnumerator和IEnumerator<int>的实现中,Current都是单纯的返回<>2__current的值。

OK,IEnumerator接口我们看完了。下面再来看看另一个接口IEnumerable吧。

IEnumerator VS IEnumerable

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

using System;
using System.Collections.Generic;

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

之后,我们同样通过反编译,看看编译器又背着我们做了什么。

internal class Test
{
    private static IEnumerable<int> TestIterator()
    {
        return new <TestIterator>d__0(-2);
    }

    private sealed class <TestIterator>d__0 : IEnumerable<int>, IEnumerable, IEnumerator<int>, IEnumerator, IDisposable
    {
        // Fields
        private int <>1__state;
        private int <>2__current;
        private int <>l__initialThreadId;
        public int <count>5__1;

        public <TestIterator>d__0(int <>1__state)
        {
            this.<>1__state = <>1__state;
            this.<>l__initialThreadId = Thread.CurrentThread.ManagedThreadId;
        }

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

                case 1:
                    goto Label_0046;
            }
            return false;
        }

        IEnumerator<int> IEnumerable<int>.GetEnumerator()
        {
            if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))
            {
                this.<>1__state = 0;
                return this;
            }
            return new Test.<TestIterator>d__0(0);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<Int32>) this).GetEnumerator();
        }

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

        void IDisposable.Dispose()
        {
        }

        int IEnumerator<int>.Current
        {
            get
            {
                return this.<>2__current;
            }
        }

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

看到反编译出的代码,我们就很容易能对比出区别。

  1. <TestIterator>d__0类不仅实现了IEnumerable<int> 接口,而且还实现了IEnumerator<int>接口。
  2. IEnumerator和IEnumerator<int>的实现都和上面一样。IEnumerator的Reset方法会抛出NotSupportedException异常,而IEnumerator和IEnumerator<int>的Current仍旧会返回<>2__current字段的值。
  3. TestIterator()方法调用<TestIterator>d__0类的构造函数时,传入的参数由上面的0变成了-2:new <TestIterator>d__0(-2);。也就是说此时的初始状态是-2。
  4. 又多了一个新的私有字段<>l__initialThreadId,且会在<TestIterator>d__0的构造函数中被赋值,用来标识创建该实例的线程。
  5. 实现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()
{
    if ((Thread.CurrentThread.ManagedThreadId == this.<>l__initialThreadId) && (this.<>1__state == -2))
    {
        this.<>1__state = 0;
        return this;
    }
    return new Test.<TestIterator>d__0(0);
}

我们可以发现,-2这个状态,也就是此时的初始状态,表明了GetEnumerator()方法还没有执行。而0这个状态,则表明已经准备好了迭代,但是MoveNext()尚未调用过。

当在不同的线程上调用GetEnumerator方法或者是状态不是-2(证明已经不是初始状态了),则GetEnumerator方法会返回一个<TestIterator>d__0类的新实例用来保存不同的状态。

0x03 状态管理

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

状态切换

根据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之后,代码从哪里恢复执行。

0x04 总结

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


感谢丁晓昀对本文的审校。

给InfoQ中文站投稿或者参与内容翻译工作,请邮件至editors@cn.infoq.com。也欢迎大家通过新浪微博(@InfoQ@丁晓昀),微信(微信号:InfoQChina)关注我们,并与我们的编辑和其他读者朋友交流(欢迎加入InfoQ读者交流群InfoQ好读者)。

评价本文

专业度
风格

您好,朋友!

您需要 注册一个InfoQ账号 或者 才能进行评论。在您完成注册后还需要进行一些设置。

获得来自InfoQ的更多体验。

告诉我们您的想法

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我
社区评论

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

允许的HTML标签: a,b,br,blockquote,i,li,pre,u,ul,p

当有人回复此评论时请E-mail通知我

讨论

登陆InfoQ,与你最关心的话题互动。


找回密码....

Follow

关注你最喜爱的话题和作者

快速浏览网站内你所感兴趣话题的精选内容。

Like

内容自由定制

选择想要阅读的主题和喜爱的作者定制自己的新闻源。

Notifications

获取更新

设置通知机制以获取内容更新对您而言是否重要

BT