Algorithme pour l'implémentation C# yield statement

Question

J'aimerais bien le comprendre moi-même mais je me demandais à peu près quel est l'algorithme pour convertir une fonction avec des déclarations de rendement dans une machine d'état pour un énumérateur? Par exemple, comment fait C# tourner ceci:

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

dans ce:

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; 
} 

Bien sûr, le résultat peut être complètement différent en fonction du code d'origine.

Answer 1

L'exemple de code particulier que vous êtes à la recherche implique une série de transformations. Veuillez noter qu'il s'agit d'une description approximative de l'algorithme. Les noms réels utilisés par le compilateur et le code exact qu'il génère peuvent être différents. Alors l'idée est la même, cependant.

La première transformation est la transformation "foreach", qui transforme ce code:

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

dans le code suivant:

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

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

La deuxième transformation retrouve tous les états de retour d'écoulement dans le corps de la fonction , attribue un nombre à chacun (une valeur d'état), et crée une "étiquette goto" juste après le rendement.

La troisième transformation lève toutes les variables locales et les arguments de fonction dans le corps de la méthode dans un objet appelé fermeture.

Vu le code dans votre exemple, qui ressemble à ceci:

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; 
     } 
    } 
} 

Le corps de la méthode est ensuite déplacé de la méthode originale, une méthode dans « fermeture » appelée MoveNext, qui retourne un bool , et implémente IEnumerable.MoveNext. Tout accès aux locaux est routé via "this", et tout accès aux membres de la classe est routé via this.originalThis.

Tout « retour rendement expr » est traduit en:

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

Toute déclaration de rupture de rendement se traduit par:

state = -1; 
return false; 

Il y a une déclaration de rupture de rendement « implicite » à la fin de la fonction. Une instruction switch est ensuite introduite au début de la procédure. Elle examine le numéro d'état et passe à l'étiquette associée.

La méthode originale est ensuite traduit en quelque chose comme ceci:

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

Le fait que l'état de la méthode est tout poussé dans un objet et que la méthode MoveNext utilise une instruction switch/variable d'état est ce que permet à l'itérateur de se comporter comme si le contrôle était renvoyé au point immédiatement après la dernière instruction "return return" à la prochaine occurrence de "MoveNext".

Il est important de souligner, cependant, que la transformation utilisée par le compilateur C# n'est pas la meilleure façon de le faire. Il souffre de mauvaises performances lorsqu'il essaie d'utiliser "yield" avec des algorithmes récursifs. Il y a un bon papier qui présente une meilleure façon de le faire ici:

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

Il vaut la peine d'une lecture si vous avez pas encore lu.

Answer 2

Raymond chen répond à cette question; http://blogs.msdn.com/b/oldnewthing/archive/2008/08/12/8849519.aspx

(sous la direction pour pointer vers la partie 1 de la série, ne fait pas partie 4)

Answer 3

Juste repéré cette question - je wrote an article récemment. Je vais devoir ajouter les autres liens mentionnés ici à l'article si ...