Réimplémentation de LINQ to Objects : Partie 9 - « SelectMany »

L'opérateur que nous allons maintenant implémenter est le plus important des opérateurs LINQ. La plupart (tous?) des autres opérateurs qui retournent des séquences peuvent être implémentés via SelectMany. Nous y reviendrons plus tard, mais commençons d'abord par l'implémenter.

SelectMany dispose de quatre surcharges qui semblent plus effrayantes les unes que les autres :

public static IEnumerable<TResult> SelectMany<TSource, TResult>( 
    this IEnumerable<TSource> source, 
    Func<TSource, IEnumerable<TResult>> selector) 

public static IEnumerable<TResult> SelectMany<TSource, TResult>( 
    this IEnumerable<TSource> source, 
    Func<TSource, int, IEnumerable<TResult>> selector) 

public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult>( 
    this IEnumerable<TSource> source, 
    Func<TSource, IEnumerable<TCollection>> collectionSelector, 
    Func<TSource, TCollection, TResult> resultSelector) 

public static IEnumerable<TResult> SelectMany<TSource, TCollection, TResult>( 
    this IEnumerable<TSource> source, 
    Func<TSource, int, IEnumerable<TCollection>> collectionSelector, 
    Func<TSource, TCollection, TResult> resultSelector)

Elles ne sont cependant pas si complexes. Il s'agit simplement de variantes de la même opération avec deux éléments « optionnels ».

Dans tous les cas, nous débutons avec une séquence. Nous générons une sous-séquence basée sur chaque élément de la séquence d'entrée en utilisant un délégué qui peut éventuellement prendre en paramètre l'index de l'élément dans la collection d'origine.

Ensuite, soit nous retournons chaque élément de chaque sous-séquence directement, soit nous appliquons un autre délégué qui reçoit en paramètre l'élément original dans la séquence initiale et l'élément dans la sous-séquence.

D'après mon expérience, les surcharges utilisant un délégué de sélection avec l'index en paramètre sont rarement utilisées, mais les autres (la première et la troisième dans la liste ci-dessus) le sont très couramment. Le compilateur C#, notamment, utilise la troisième surcharge dès que, dans une expression de requête, il trouve plus d'une clause « from ».

C'est plus simple à comprendre avec un exemple. Supposons que nous ayons l'expression de requête suivante :

var query = from file in Directory.GetFiles("logs") 
            from line in File.ReadLines(file) 
            select Path.GetFileName(file) + ": " + line;

Cela devrait être converti en une instruction « normale » telle que celle-ci :

var query = Directory.GetFiles("logs") 
                     .SelectMany(file => File.ReadLines(file), 
                                 (file, line) => Path.GetFileName(file) + ": " + line);

Dans ce cas, le compilateur a utilisé notre clause « select » finale comme projection ; si l'expression de requête avait été prolongée par une clause « where », cela aurait entraîné la création d'une projection retournant un type anonyme composé de « file » et « line ». C'est probablement le point le plus déroutant du processus de traduction de requête, avec les identifiants transparents. Pour le moment, nous nous contenterons de la version simple ci-dessus.

Au final, l'appel à SelectMany ci-dessus reçoit réellement trois arguments :

• la source, qui est une liste de chaînes (les noms de fichiers retournés par Directory.GetFiles) ;
• une projection initiale qui convertit un simple nom de fichier en la liste des lignes de texte qui le compose ;
• une projection finale qui convertit des couples (file, line) en une chaîne unique, simplement en les séparant par le symbole « : ».

Le résultat est une liste simple de chaînes - chaque ligne de chaque fichier journal - préfixée par le nom du fichier dans lequel elle apparaît. Voici un exemple de sortie que cette requête pourrait produire :

test1.log: foo 
test1.log: bar 
test1.log: baz 
test2.log: Second log file 
test2.log: Another line from the second log file

Cela peut prendre un certain temps pour vous familiariser avec SelectMany - du moins, ça m'en a pris - mais c'est un opérateur vraiment important à comprendre.

Encore quelques détails avant de passer aux tests :

• les arguments sont validés immédiatement : ils doivent tous être non-nuls ;
• tout est traité par niveau. Ainsi, un seul élément de la source est lu à la fois. Ensuite la sous-séquence qui lui est associée est créée. Un seul élément de la sous-séquence est alors lu à la fois, itérant sur les résultats au fur et à mesure. Nous passons ensuite à l'élément suivant dans la séquence source, ensuite à la sous-séquence, et ainsi de suite ;
• chaque itérateur est fermé quand on a fini de l'utiliser, tout à fait comme vous seriez en droit de l'attendre à ce stade.

Je crains d'être devenu fainéant à ce stade. Je ne peux plus faire face à l'écriture de toujours plus de tests pour les arguments nuls. J'ai écrit un seul test pour chacune des surcharges. J'ai eu du mal à trouver un moyen clair d'écrire des tests mais voici un exemple pour la surcharge la plus complexe :

[Test] 
public void FlattenWithProjectionAndIndex() 
{ 
    int[] numbers = { 3, 5, 20, 15 }; 
    var query = numbers.SelectMany((x, index) => (x + index).ToString().ToCharArray(), 
                                   (x, c) => x + ": " + c); 
    // 3 => "3: 3" 
    // 5 => "5: 6" 
    // 20 => "20: 2", "20: 2" 
    // 15 => "15: 1", "15: 8" 
    query.AssertSequenceEqual("3: 3", "5: 6", "20: 2", "20: 2", "15: 1", "15: 8"); 
}

Quelques explications complémentaires s'imposent :

• chaque nombre est additionné à son index (3+0, 5+1, 20+2, 15+3) ;
• chaque somme est transformée en chaîne et convertie ensuite en tableau de caractères (nous n'avons pas réellement besoin d'appeler ToCharArray, car le type string implémente déjà IEnumerable<char>, mais j'ai trouvé que cela clarifiait l'exemple) ;
• nous combinons ensuite chaque caractère de la sous-séquence avec l'élément d'origine dont la sous-séquence est issue, sous la forme : « valeur originale : caractère de la sous-séquence ».

Le commentaire montre les résultats éventuels de chaque entrée et le test final montre la séquence résultante.

Limpide comme de la boue ? Espérons que ça s'améliore en y regardant étape par étape. Bon, faisons en sorte que ça réussisse les tests…

Nous pourrions implémenter les trois premières surcharges de façon à invoquer la dernière ou, plus vraisemblablement, une seule méthode « Impl », sans validation des arguments, appelée par les quatre méthodes publiques. Par exemple, la méthode la plus simple pourrait être implémentée comme ceci :

public static IEnumerable<TResult> SelectMany<TSource, TResult>( 
    this IEnumerable<TSource> source, 
    Func<TSource, IEnumerable<TResult>> selector) 
{ 
    if (source == null) 
    { 
        throw new ArgumentNullException("source"); 
    } 
    if (selector == null) 
    { 
        throw new ArgumentNullException("selector"); 
    } 
    return SelectManyImpl(source, 
                          (value, index) => selector(value), 
                          (originalElement, subsequenceElement) => subsequenceElement); 
}

Cependant, j'ai décidé d'implémenter les différentes méthodes séparément, en les scindant en une méthode d'extension et une méthode « SelectManyImpl » avec la même signature chaque fois. Je pense que ce sera plus simple de parcourir le code si jamais il devait y avoir un problème… et cela nous permet également de voir les différences entre la version simple et la version compliquée :

// Simplest overload 
private static IEnumerable<TResult> SelectManyImpl<TSource, TResult>( 
    IEnumerable<TSource> source, 
    Func<TSource, IEnumerable<TResult>> selector) 
{ 
    foreach (TSource item in source) 
    { 
        foreach (TResult result in selector(item)) 
        { 
            yield return result; 
        } 
    } 
} 

// Most complicated overload: 
// - Original projection takes index as well as value 
// - There's a second projection for each original/subsequence element pair 
private static IEnumerable<TResult> SelectManyImpl<TSource, TCollection, TResult>( 
    IEnumerable<TSource> source, 
    Func<TSource, int, IEnumerable<TCollection>> collectionSelector, 
    Func<TSource, TCollection, TResult> resultSelector) 
{ 
    int index = 0; 
    foreach (TSource item in source) 
    { 
        foreach (TCollection collectionItem in collectionSelector(item, index++)) 
        { 
            yield return resultSelector(item, collectionItem); 
        } 
    } 
}

La correspondance entre les deux méthodes est évidente, mais je trouve utile de disposer de la première méthode, de sorte que si jamais je suis perplexe sur un des aspects fondamentaux de SelectMany il soit plus facile à comprendre avec la version simple. Ce n'est alors plus un trop gros travail d'ajouter les complications « optionnelles » et ainsi obtenir la méthode finale. La méthode simple est, en quelque sorte, un tremplin conceptuel.

Deux remarques mineures :

• La première méthode aurait pu être implémentée avec une expression telle que « yield foreach selector(item) » si une telle expression avait existé en C#. Utiliser une construction similaire dans la version plus compliquée serait plus difficile et impliquerait un autre appel à Select, j'imagine… Probablement plus de tracas que ça n'en vaut la peine ;
• Je n'utilise pas explicitement un bloc « checked » dans la seconde forme, même si « index » pourrait provoquer un dépassement de capacité. Pour être honnête, je ne suis pas allé voir comment c'est implémenté dans la version officielle, mais je pense que cela a peu de chance de se produire. Par souci de cohérence, je devrais probablement utiliser un bloc « checked » pour toutes les méthodes qui utilisent un index tel que celui-ci, ou alors simplement activer l'option pour l'entièreté de l'assembly.

J'ai mentionné précédemment dans ce billet que beaucoup des opérateurs LINQ peuvent être implémentés via SelectMany. Comme exemple rapide, voici des implémentations alternatives pour Select, Where et Concat :

public static IEnumerable<TResult> Select<TSource, TResult>( 
    this IEnumerable<TSource> source, 
    Func<TSource, TResult> selector) 
{ 
    if (source == null) 
    { 
        throw new ArgumentNullException("source"); 
    } 
    if (selector == null) 
    { 
        throw new ArgumentNullException("selector"); 
    } 
    return source.SelectMany(x => Enumerable.Repeat(selector(x), 1)); 
} 

public static IEnumerable<TSource> Where<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    if (source == null) 
    { 
        throw new ArgumentNullException("source"); 
    } 
    if (predicate == null) 
    { 
        throw new ArgumentNullException("predicate"); 
    } 
    return source.SelectMany(x => Enumerable.Repeat(x, predicate(x) ? 1 : 0)); 
} 

public static IEnumerable<TSource> Concat<TSource>( 
    this IEnumerable<TSource> first, 
    IEnumerable<TSource> second) 
{ 
    if (first == null) 
    { 
        throw new ArgumentNullException("first"); 
    } 
    if (second == null) 
    { 
        throw new ArgumentNullException("second"); 
    } 
    return new[] { first, second }.SelectMany(x => x); 
}

Select et Where utilisent Enumerable.Repeat pour facilement créer une séquence sans ou avec un élément. Vous pouvez éventuellement créer un nouveau tableau à la place. Concat utilise directement un tableau. En y songeant, Concat est un candidat idéal pour SelectMany et son opération d'aplatissement. J'imagine que Empty et Repeat sont probablement faisables avec de la récursivité même si les performances en seraient fortement dégradées.

Actuellement, les implémentations ci-dessus sont dans le même code en utilisant la compilation conditionnelle. Selon la demande, je pourrais envisager de répartir cela dans des projets séparés. Dites-moi ce que vous en pensez, bien que mon sentiment personnel soit que cela ne nous apprendra pas grand-chose de plus… à part que SelectMany est très polyvalent.

SelectMany est également important sur le plan théorique, en ce sens qu'il est la base de l'aspect monadique de LINQ. C'est l'opération de « liaison » dans la monade LINQ. Je ne compte pas en dire plus sur le sujet mais je vous invite à lire le billet de Wes Dyer (http://blogs.msdn.com/b/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx) sur le sujet pour plus de détails ou à effectuer une recherche sur « bind monad SelectMany » pour de nombreux billets rédigés par des gens plus intelligents que moi.

SelectMany est une des opérations fondamentales de LINQ et, à première vue, c'est une bête redoutable. Dès que vous comprenez qu'il s'agit simplement d'une projection avec aplatissement et quelques variations optionnelles, elle est facilement apprivoisée.

La prochaine fois, j'implémenterai « All » et « Any » qui sont simples et faciles à décrire en comparaison.

Merci à Jon Skeet de m'avoir autorisé à traduire son article Reimplementing LINQ to Objects : Part 9 - SelectMany

Merci à Thomas Levesque (tomlev) pour sa relecture et ses corrections toujours avisées.

Merci à Cédric Duprez(ced) pour la relecture orthographique.