Réimplémentation de Linq to Objects : Partie 2 - « Where »

Attention : Ce billet est un assez long. Bien que j'aie choisi un opérateur simple à implémenter, nous allons rencontrer en cours de route un certain nombre des cas marginaux et des principes mis en œuvre dans LINQ. Ce sera aussi un billet quelque peu expérimental en termes de format, puisque je cherche encore la meilleure façon de présenter le contenu.

Nous allons implémenter la clause/méthode/opérateur « Where ». Elle est raisonnablement simple à comprendre en général, mais elle fait entrer en jeu tous les aspects d'exécution différée et de streaming qui peuvent poser problème. Elle est générique, mais utilise un seul paramètre de type (ce qui est important à mon avis - plus une méthode a de paramètres de type, plus je la trouve difficile à comprendre en général). Oh, et c'est un point de départ pour les expressions de requête, ce qui est un bonus.

« Where » a deux surcharges :

public static IEnumerable<TSource> Where( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
public static IEnumerable<TSource> Where( 
    this IEnumerable<TSource> source, 
    Func<TSource, int, bool> predicate)

Avant d'entrer dans le détail de ce qu'elle fait, je vais souligner quelques points qui vont être communs à presque tous les opérateurs LINQ que nous allons implémenter :

• ce sont des méthodes d'extension - elles sont déclarées dans une classe statique de niveau supérieur, non-imbriquée, et le premier paramètre a le modificateur « this ». Elles peuvent être invoquées à peu près comme si c'était des méthodes d'instance du type du premier paramètre ;

• ce sont des méthodes génériques - dans ce cas il y a juste un unique paramètre de type (TSource), qui indique le type de séquence auquel nous avons affaire. Donc, pour (par exemple) une liste de chaînes de caractères, TSource serait string ;
• ils prennent en paramètre des délégués génériques de la famille Func<…>. Ceux-ci sont généralement spécifiés avec des expressions lambda, mais toute autre manière de fournir un délégué fonctionnera très bien aussi ;
• ils traitent des séquences. Celles-ci sont représentées par IEnumerable<T>, avec un itérateur sur une séquence représentée par IEnumerator <T>.

Je m'attends à ce que la plupart des lecteurs soient à l'aise avec tous ces concepts, je ne vais pas les passer en revue plus en détail. Si un des points de ce qui précède vous rend nerveux, merci de vous familiariser avec avant de continuer, sinon vous risquez d'avoir du mal à suivre.

Le but de « Where » est de filtrer une séquence. Il prend une séquence d'entrée et un prédicat, et renvoie une autre séquence. La séquence de sortie a le même type d'élément (si vous y mettez une séquence de chaînes de caractères, vous obtiendrez une séquence de chaînes de caractères) et elle ne contiendra que des éléments de la séquence d'entrée qui satisfont le prédicat. (Chaque élément sera passé au prédicat à son tour. Si le prédicat renvoie true, l'élément fera partie de la séquence de sortie ; sinon il en sera exclu).

Maintenant, quelques détails importants sur le comportement :

• la séquence d'entrée n'est absolument pas modifiée : ce n'est pas comme List<T>.RemoveAll, par exemple ;
• la méthode utilise l'exécution différée - tant que vous n'avez pas commencé à essayer de récupérer les éléments de la séquence de sortie, elle ne commence pas à aller chercher les éléments de la séquence d'entrée ;
• malgré l'exécution différée, elle permettra de valider immédiatement que les paramètres ne sont pas nuls ;
• elle fournit ses résultats sous forme de flux : elle ne considère qu'un résultat à la fois, et le renverra sans garder de référence dessus. Cela signifie que vous pouvez l'appliquer à une séquence de longueur infinie (par exemple une séquence de nombres aléatoires) ;
• elle va parcourir la séquence d'entrée exactement une fois à chaque fois que vous parcourez la séquence de sortie ;
• « disposer » (NdT : au sens de la méthode Dispose) un itérateur sur la séquence de sortie va disposer l'itérateur correspondant associé à la séquence d'entrée. (Au cas où vous n'en étiez pas conscient, l'instruction foreach en C# utilise un bloc try/finally pour s'assurer que l'itérateur est toujours disposé quelle que soit la façon dont la boucle se termine).

Bon nombre de ces points seront vrais aussi pour beaucoup de nos autres opérateurs.

La surcharge qui prend une Func<TSource, int, bool> permet au prédicat d'utiliser l'indice dans la séquence, ainsi que la valeur. L'indice commence toujours à 0, et s'incrémente de 1 à chaque fois indépendamment des résultats antérieurs du prédicat.

Idéalement, nous aimerions tester tous les points ci-dessus. Les détails du streaming et de combien de fois la séquence est itérée sont franchement pénibles à traiter, malheureusement. Étant donné tout ce qu'il y a déjà à implémenter, nous y reviendrons plus tard.

Jetons un coup d'œil à certains tests. Tout d'abord, voici un test « positif » simple - nous commençons avec un tableau d'entiers et en utilisant une expression lambda pour n'inclure que les éléments inférieurs à 4 dans la sortie. (Le terme « filtre » est omniprésent mais malheureux. Il est plus naturel de parler de « filtrer » les éléments quand il s'agit de les exclure que de les inclure, mais le prédicat est exprimé d'une manière positive.)

[Test] 
public void SimpleFiltering() 
{ 
    int[] source = { 1, 3, 4, 2, 8, 1 }; 
    var result = source.Where(x => x < 4); 
    result.AssertSequenceEqual(1, 3, 2, 1); 
}

J'ai gardé les TestExtensions de MoreLINQ, bien que NUnit propose déjà CollectionAssert. Je trouve plus facile de travailler avec les méthodes d'extension pour trois raisons :

• ce sont des méthodes d'extension, ce qui contribue à réduire la verbosité du code ;
• elles peuvent utiliser un tableau de paramètres pour la sortie attendue, ce qui rend le test plus simple à exprimer ;
• le message est plus clair lorsque l'assertion échoue.

Fondamentalement, AssertSequenceEqual fait ce à quoi on pourrait s'attendre : elle vérifie que le résultat réel (généralement exprimé dans la variable sur laquelle vous appelez la méthode) correspond au résultat attendu (généralement exprimée en un tableau de paramètres).

Jusqu'ici, tout va bien. Maintenant, vérifions la validation des arguments :

[Test] 
public void NullSourceThrowsNullArgumentException() 
{ 
    IEnumerable<int> source = null; 
    Assert.Throws<ArgumentNullException>(() => source.Where(x => x > 5)); 
} 

[Test] 
public void NullPredicateThrowsNullArgumentException() 
{ 
    int[] source = { 1, 3, 7, 9, 10 }; 
    Func<int, bool> predicate = null; 
    Assert.Throws<ArgumentNullException>(() => source.Where(predicate)); 
}

Je ne vais pas prendre la peine de vérifier le nom dans le ArgumentNullException, mais il est important de tester que les arguments sont validés immédiatement. Je ne cherche pas à itérer sur le résultat - si la validation est différée, le test échouera.

Le dernier test intéressant pour le moment concerne aussi l'exécution différée, en utilisant une classe utilitaire appelée ThrowingEnumerable. C'est une séquence qui explose en lançant une InvalidOperationException si jamais vous essayez de la parcourir. Essentiellement, nous voulons vérifier deux choses :

• juste appeler Where ne commence pas à itérer sur la séquence source ;
• lorsque nous appelons GetEnumerator() pour obtenir un itérateur puis MoveNext() sur cet itérateur, nous devrions commencer l'itération, provoquant une levée de l'exception.

Nous aurons besoin de faire quelque chose de similaire pour les autres opérateurs, donc j'ai écrit une petite méthode utilitaire dans ThrowingEnumerable :

internal static void AssertDeferred<T>( 
    Func<IEnumerable<int>, IEnumerable<T>> deferredFunction) 
{ 
    ThrowingEnumerable source = new ThrowingEnumerable(); 
    var result = deferredFunction(source); 
    using (var iterator = result.GetEnumerator()) 
    { 
        Assert.Throws<InvalidOperationException>(() => iterator.MoveNext()); 
    } 
}

Maintenant, nous pouvons l'utiliser pour vérifier que l'exécution de Where est vraiment différée :

[Test] 
public void ExecutionIsDeferred() 
{ 
    ThrowingEnumerable.AssertDeferred(src => src.Where(x => x > 0)); 
}

Ces tests concernaient tous la surcharge la plus simple - celle où le prédicat transmet uniquement l'élément et non pas l'indice. Les essais portant sur l'indice sont très similaires.

Maintenant que tous les tests passent lors de l'exécution avec le vrai LINQ to Objects, il est temps d'implémenter notre code de production. Nous allons utiliser des blocs itérateurs, qui ont été introduits dans C# 2 pour rendre plus facile l'implémentation de IEnumerable<T>. J'ai deux articles que vous pouvez lire si vous voulez découvrir plus de détails… ou alors lisez le chapitre 6 de C# In Depth (n'importe quelle édition). Les itérateurs nous fournissent l'exécution différée gratuitement… mais cela peut être une malédiction ainsi bien qu'une bénédiction, comme nous le verrons dans un instant.

Le cœur de l'implémentation va ressembler à ceci :

// Implementation naïve
public static IEnumerable<TSource> Where<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            yield return item; 
        } 
    } 
}

Simple, n'est-ce pas ? Les blocs itérateurs nous permettent d'écrire du code à peu près comme nous pourrions le décrire : nous itérons sur chaque élément de la source, et si le prédicat retourne true pour cet élément particulier, nous le renvoyons (l'incluons) dans la séquence de sortie.

Et voilà, certains de nos tests passent déjà. Maintenant nous avons juste besoin de la validation des arguments. C'est facile, non ? Allons-y :

// Naive validation - broken! 
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"); 
    } 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            yield return item; 
        } 
    } 
}

Hmm. Nos tests de validation semblent être encore rouges, et mettre un point d'arrêt sur les instructions « throw » ne nous aide pas… Elles ne sont pas exécutées. Que se passe-t-il ?

Je vous ai déjà donné quelques indices assez vagues. Le problème, c'est l'exécution différée. Tant que nous n'avons pas commencé à essayer de parcourir le résultat, pas une ligne de notre code ne sera exécutée. Nos tests n'ont délibérément pas itéré sur le résultat, par conséquent aucune validation n'est effectuée.

Nous venons de toucher un défaut de conception de C#. Les blocs itérateurs en C# ne fonctionnent pas bien quand vous voulez séparer l'exécution entre « immédiat » (généralement pour la validation) et « différé ». Au lieu de cela, nous devons diviser notre implémentation en deux : une méthode normale pour la validation, qui appelle ensuite la méthode itérateur pour le traitement différé :

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 WhereImpl(source, predicate); 
} 

private static IEnumerable<TSource> WhereImpl<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            yield return item; 
        } 
    } 
}

C'est moche, mais ça marche : tous nos tests sans l'indice sont passés au vert. À partir de là, il n'y a qu'un pas pour implémenter aussi la version utilisant un indice :

public static IEnumerable<TSource> Where<TSource>( 
    this IEnumerable<TSource> source, 
    Func<T, int, bool> predicate) 
{ 
    if (source == null) 
    { 
        throw new ArgumentNullException("source"); 
    } 
    if (predicate == null) 
    { 
        throw new ArgumentNullException("predicate"); 
    } 
    return WhereImpl(source, predicate); 
} 

private static IEnumerable<TSource> WhereImpl<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, int, bool> predicate) 
{ 
    int index = 0; 
    foreach (TSource item in source) 
    { 
        if (predicate(item, index)) 
        { 
            yield return item; 
        } 
        index++; 
    } 
}

Maintenant, la barre est verte et nous avons terminé. Mais attendez un instant… nous ne l'avons pas encore utilisé de toutes les façons possibles.

Jusqu'à présent, nous avons appelé la méthode directement (bien qu'en tant que méthode d'extension) - mais LINQ nous fournit également les expressions de requête. Voici notre test « SimpleFiltering » réécrit pour utiliser une expression de requête :

[Test] 
public void QueryExpressionSimpleFiltering() 
{ 
    int[] source = { 1, 3, 4, 2, 8, 1 }; 
    var result = from x in source 
                 where x < 4 
                 select x; 
    result.AssertSequenceEqual(1, 3, 2, 1); 
}

(Notez que le nom est différent entre ici et le code téléchargeable, pour empêcher que le logiciel du serveur de blog ne bloque le nom de la méthode. Grr.)

Cela va produire exactement le même code que notre test précédent. Le compilateur traduit essentiellement de cette forme vers la précédente, laissant la condition (x < 4) comme une expression lambda, puis en la convertissant de façon appropriée (en un délégué dans ce cas). Vous pourriez être surpris que cela fonctionne, car nous n'avons pas encore la méthode Select… Mais dans ce cas, nous avons une projection de sélection qui ne fait rien, nous n'avons pas réellement effectué une véritable transformation. Dans ce cas - et du moment qu'il y a autre chose dans la requête, en l'occurrence notre clause « where » - le compilateur omet effectivement la clause « select », si bien que ça n'a pas d'importance que nous ne l'ayons pas implémentée. Si vous changiez « select x » en « select x * 2 », ça ne compilerait pas avec notre implémentation de LINQ qui ne contient que Where.

Le fait que les expressions de requête sont simplement basées sur des motifs de ce genre est une fonctionnalité très puissante pour la flexibilité - c'est comme cela que LINQ to Rx peut n'implémenter que les opérateurs qui ont du sens dans cet environnement, par exemple. De même, il n'y a rien dans le compilateur C# qui « connaît » IEnumerable<T> quand il s'agit des expressions de requête - ce qui explique que ça fonctionne tout aussi bien avec des interfaces complètement distinctes, telle que IObservable<T>.

Il y a eu beaucoup de choses à assimiler ici, tant en termes d'implémentation que de principes fondamentaux de LINQ :

• LINQ to Objects est basée sur les méthodes d'extension, les délégués et IEnumerable<T> ;
• les opérateurs utilisent l'exécution différée quand c'est approprié et diffusent leurs données sous forme de flux quand cela est possible ;
• les opérateurs ne modifient pas la source d'origine, mais retournent une nouvelle séquence qui va retourner les données appropriées ;
• les expressions de requête sont basées sur des traductions de motifs par le compilateur ; vous n'avez à implémenter que la partie du motif qui est nécessaire à l'expression des requêtes en question ;
• les blocs itérateurs sont parfaits pour l'implémentation de l'exécution différée…
• … mais rendent difficile la validation immédiate des arguments.

Linq-To-Objects-2.zip

Beaucoup de gens ont demandé un dépôt de code source pour le projet et c'est une bonne idée. Je suis en train de mettre en place un dépôt ; ce sera sans doute fait avant que je ne publie la prochaine partie.

Je tiens ici à remercier Jon Skeet de m'avoir autorisé à traduire son article, Reimplementing LINQ to Objects: Part 2 - "Where"

Je remercie Tomlev pour sa relecture technique et ses propositions.

Je remercie également F-leb pour sa relecture orthographique et ses propositions.