Алгоритм реализации оператора C # yield

Question

Я бы хотел сам разобраться, но мне было интересно примерно, каков алгоритм преобразования функции с операторами yield в конечный автомат для перечислителя? Например, как C # превращает это:

IEnumerator<string> strings(IEnumerable<string> args)
 { IEnumerator<string> enumerator2 = getAnotherEnumerator();     
   foreach(var arg in arg) 
    { enumerator2.MoveNext();
      yield return arg+enumerator.Current;
    } 
 }

в это:

bool MoveNext()
 { switch (this.state)
    {
        case 0:
            this.state = -1;
            this.enumerator2 = getAnotherEnumerator();
            this.argsEnumerator = this.args.GetEnumerator();
            this.state = 1;
            while (this.argsEnumerator.MoveNext())
            {
                this.arg = this.argsEnumerator.Current;
                this.enumerator2.MoveNext();
                this.current = this.arg + this.enumerator2.Current;
                this.state = 2;
                return true;

              state1:
                this.state = 1;
            }
            this.state = -1;
            if (this.argsEnumerator != null) this.argsEnumerator.Dispose();
            break;

        case 2:
            goto state1;
    }
    return false;
}

Конечно, результат может быть совершенно другим в зависимости от исходного кода.

Answer 1

Конкретный пример кода, на который вы смотрите, включает в себя серию преобразований. Обратите внимание, что это приблизительное описание алгоритма. Фактические имена, используемые компилятором, и точный код, который он генерирует, могут отличаться. Однако идея та же самая.

Первым преобразованием является преобразование "foreach", которое преобразует этот код:

foreach (var x in y)
{
   //body
}

в этот код:

var enumerator = y.GetEnumerator();
while (enumerator.MoveNext())
{
    var x = enumerator.Current;
    //body
}

if (y != null)
{
    enumerator.Dispose();
}

Второе преобразование находит все операторы yield return в теле функции, присваивает число каждому (значение состояния) и создает «метку перехода» сразу после yield.

Третье преобразование поднимает все локальные переменные и аргументы функции в теле метода в объект, называемый замыканием.

Учитывая код в вашем примере, это будет выглядеть примерно так:

 class ClosureEnumerable : IEnumerable<string>
 {
    private IEnumerable<string> args;
    private ClassType originalThis;
    public ClosureEnumerator(ClassType origThis, IEnumerable<string> args)
    {
        this.args = args;
        this.origianlThis = origThis;
    }
    public IEnumerator<string> GetEnumerator()
    {
        return new Closure(origThis, args);
    }
 }

class Closure : IEnumerator<string>
{
    public Closure(ClassType originalThis, IEnumerable<string> args)
    {
        state = 0;
        this.args = args;
        this.originalThis = originalThis;
    }

    private IEnumerable<string> args;
    private IEnumerator<string> enumerator2;
    private IEnumerator<string> argEnumerator;

    //- Here ClassType is the type of the object that contained the method
    //  This may be optimized away if the method does not access any 
    //  class members
    private ClassType originalThis;

    //This holds the state value.
    private int state;
    //The current value to return
    private string currentValue;

    public string Current
    {
        get 
        {
            return currentValue;
        }
    }
}

Тело метода затем перемещается из исходного метода в метод внутри «Closure» с именем MoveNext, который возвращает bool и реализует IEnumerable.MoveNext. Любой доступ к любым местным жителям направляется через «this», а любой доступ к любым членам класса - через this.originalThis.

Любой "expr возврата дохода" переводится на:

currentValue = expr;
state = //the state number of the yield statement;
return true;

Любая выписка о доходности переводится в:

state = -1;
return false;

В конце функции есть "неявный" оператор yield break. Затем в начале процедуры вводится оператор switch, который просматривает номер состояния и переходит к соответствующей метке.

Затем оригинальный метод переводится примерно так:

IEnumerator<string> strings(IEnumerable<string> args)
{
   return new ClosureEnumerable(this,args);
}

Тот факт, что состояние метода все помещается в объект и что метод MoveNext использует оператор switch / переменную состояния, позволяет итератору вести себя так, как будто управление передается обратно в точку сразу после последнего оператор yield return при следующем вызове MoveNext.

Важно отметить, однако, что преобразование, используемое компилятором C #, не лучший способ сделать это. Он страдает от низкой производительности при попытке использовать «yield» с рекурсивными алгоритмами. Здесь есть хорошая статья, в которой описан лучший способ сделать это:

http://research.microsoft.com/en-us/projects/specsharp/iterators.pdf

Стоит прочитать, если вы еще не читали.

Answer 2

Только что заметил этот вопрос - я недавно написал статью . Я должен добавить другие ссылки, упомянутые здесь, к статье, хотя ...

Answer 3

Раймонд Чен отвечает на это; http://blogs.msdn.com/b/oldnewthing/archive/2008/08/12/8849519.aspx

(отредактировано так, чтобы указывать на часть 1 серии, а не часть 4)