Réimplémentation de LINQ to Objects : Partie 11 - « First », « Single », « Last » et leur variante « OrDefault »

Aujourd'hui, j'ai implémenté six opérateurs, chacun avec deux surcharges. Au début, je m'attendais à ce que leurs implémentations soient fort similaires mais finalement, ils se sont tous montrés légèrement différents.

Nous avons trois types de permutations ici : {First / Last / Single}, {avec/sans OrDefault} et {avec/sans prédicat}. Cela nous donne douze signatures :

public static TSource First<TSource>( 
    this IEnumerable<TSource> source) 

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

public static TSource FirstOrDefault<TSource>( 
    this IEnumerable<TSource> source) 

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

public static TSource Last<TSource>( 
    this IEnumerable<TSource> source) 

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

public static TSource LastOrDefault<TSource>( 
    this IEnumerable<TSource> source) 

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

public static TSource Single<TSource>( 
    this IEnumerable<TSource> source) 

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

public static TSource SingleOrDefault<TSource>( 
    this IEnumerable<TSource> source) 

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

Les points communs sont les suivants :

• ce sont toutes des méthodes d'extension avec un seul paramètre générique ;
• elles sont toutes implémentées selon le principe de l'exécution immédiate ;
• elles vérifient toutes que leurs paramètres sont non-nuls ;
• les surcharges avec un prédicat sont équivalentes à un appel à source.Where(predicat).MemeOperateur(). En d'autres termes, elles ajoutent juste un filtre avant d'appliquer l'opérateur.

Avec ces règles en tête, nous avons uniquement à nous concentrer sur trois possibilités pour chaque opérateur : que se passe-t-il si la séquence d'entrée est vide, ne contient qu'un seul élément ou contient de multiples éléments. Il va de soi que ça s'applique après le filtrage si un prédicat est précisé. Nous pouvons dresser les résultats dans un tableau :

Comme vous pouvez le constater, pour une séquence d'entrée avec un seul élément, le résultat est incroyablement uniforme. De même, pour une séquence d'entrée vide, n'importe quel opérateur sans le suffixe « OrDefault » lève une exception (InvalidOperationException en fait) et n'importe quel opérateur avec le suffixe « OrDefault » retourne la valeur par défaut pour le type de l'élément (null pour les types référence, 0 pour le type int, etc.). Les opérateurs divergent vraiment si la séquence (potentiellement filtrée) d'entrée compte plusieurs éléments. First et Last se comportent de façon évidente et Single lève une exception. Il est intéressant de noter que l'opérateur SingleOrDefault lève également une exception. Il ne semble donc pas signifier : « Si la séquence est composée d'un seul élément, retourne-le, sinon retourne la valeur par défaut ». Si vous voulez un opérateur qui gère de multiples éléments, vous devriez utiliser First ou Last, avec leur version OrDefault si une séquence peut légitimement ne pas contenir d'éléments. Notez que si vous utilisez un opérateur dans sa version « OrDefault », le résultat est exactement le même pour une séquence d'entrée vide que pour une séquence d'entrée qui compte comme élément unique la valeur par défaut. (Nous verrons l'opérateur DefaultIfEmpty prochainement).

Maintenant que nous savons ce que les opérateurs font, testons-les.

Ce matin, j'ai tweeté que j'avais écrit 72 tests avant d'écrire la moindre implémentation. Finalement, j'en ai écrit 80, pour différentes raisons que j'expliquerai dans un instant. Pour chaque opérateur, j'ai testé les 12 cas suivants :

• source null (surcharge sans prédicat) ;
• source null (surcharge avec prédicat) ;
• prédicat null ;
• séquence vide, pas de prédicat ;
• séquence vide, avec prédicat ;
• séquence avec un élément unique, sans prédicat ;
• séquence avec un élément unique qui valide le prédicat ;
• séquence avec un élément unique qui ne valide pas le prédicat ;
• séquence avec plusieurs éléments, sans prédicat ;
• séquence avec plusieurs éléments ;
• séquence avec plusieurs éléments, dont un qui valide le prédicat ;
• séquence avec plusieurs éléments, dont plusieurs valident le prédicat.

Cela consistait principalement en des travaux de copier-coller. J'ai utilisé les mêmes données pour chaque opérateur et me suis contenté de modifier les résultats attendus.

Il y a deux tests supplémentaires pour First et FirstOrDefault, et deux autres pour Last et LastOrDefault :

• First/FirstOrDefault devraient se terminer, quand il n'y a pas de prédicat, dès qu'ils ont parcouru le premier élément. Ils ne devraient pas parcourir le reste de la séquence ;
• First / FirstOrDefault devraient se terminer, lorsqu'il y a un prédicat, dès que le premier élément le validant est parcouru ;
• Last / LastOrDefault sont optimisés pour le cas où la séquence d'entrée implémente IList<T> et qu'il n'y a pas de prédicat : il utilise la propriété Count et l'indexeur pour accéder à l'élément final ;
• Last / LastOrDefault n'est pas optimisé pour le cas où la séquence d'entrée implémente IList<T> et qu'il y a un prédicat : il parcourt la séquence entière.

Les deux derniers tests impliquent d'écrire une nouvelle collection appelée NonEnumerableList qui implémente IList<T> en déléguant toutes les opérations à une List<T> encapsulée, excepté GetEnumerator() (tant dans la forme générique que dans la forme non-générique) qui lève simplement une exception de type NotSupportedException. Elle devrait s'avérer pratique pour tester des optimisations dans le futur. Je discuterai des optimisations pour Last quand nous y serons.

Ces opérateurs étaient plus intéressants à implémenter que ce que je croyais, je vais donc montrer les 12 méthodes. C'était finalement moins une question de copier-coller que ce que je craignais, excepté pour la validation des arguments.

Évidemment, si nous choisissons d'implémenter les versions avec prédicat en utilisant « Where », et les versions sans prédicat ainsi que les versions « OrDefault » en utilisant « DefaultIfEmpty » suivi par la version non OrDefault, nous aurions uniquement à traiter les trois versions non OrDefault, sans prédicat. Mais comme je l'ai dit précédemment, il y a un intérêt à implémenter chaque opérateur séparément.

Afin d'éviter le surplus de texte, j'ai retiré la validation des arguments de toutes les méthodes. Évidemment, la validation est présente dans le code réel. Commençons avec First :

public static TSource First<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    // Argument validation elided 
    using (IEnumerator<TSource> iterator = source.GetEnumerator()) 
    { 
        if (iterator.MoveNext()) 
        { 
            return iterator.Current; 
        } 
        throw new InvalidOperationException("Sequence was empty"); 
    } 
} 

public static TSource First<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    // Argument validation elided 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            return item; 
        } 
    } 
    throw new InvalidOperationException("No items matched the predicate"); 
}

Les implémentations sont étonnemment différentes, et c'était une décision délibérée. J'aurais également facilement pu implémenter la version sans prédicat avec une boucle foreach, retournant inconditionnellement depuis son corps. Cependant, j'ai décidé d'accentuer le fait que nous ne bouclons pas dans First : nous nous déplaçons simplement jusqu'au premier élément si nous le pouvons et le retournons ou alors levons une exception. Il n'y a pas d'allusion au fait que nous pourrions appeler MoveNext à nouveau. Dans la forme avec prédicat, bien sûr, nous devons boucler jusqu'à ce que nous trouvions une valeur qui valide le prédicat, levant une exception uniquement lorsque nous avons épuisé toutes les possibilités.

Maintenant, voyons à quoi ça ressemble quand nous retournons la valeur par défaut pour une séquence vide :

public static TSource FirstOrDefault<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    // Argument validation elided 
    using (IEnumerator<TSource> iterator = source.GetEnumerator()) 
    { 
        return iterator.MoveNext() ? iterator.Current : default(TSource); 
    } 
} 

public static TSource FirstOrDefault<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    // Argument validation elided 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            return item; 
        } 
    } 
    return default(TSource); 
}

Ici, la forme avec prédicat ressemble très fort à First, mais la version sans prédicat est légèrement différente : au lieu d'utiliser un bloc if (qui serait bien sûr une approche parfaitement valide), j'ai utilisé l'opérateur conditionnel. Nous allons retourner quelque chose, que nous réussissions à passer au premier élément ou non. Évidemment, il serait bien que l'opérateur conditionnel autorise que le second ou le troisième opérande soit une expression « throw », déduisant le type général de l'expression sur la base de l'opérande restante, mais ce serait trop facile.

Ensuite, nous allons implémenter Single qui est finalement plus proche de First que Last ne l'est, en quelques sortes :

public static TSource Single<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    // Argument validation elided 
    using (IEnumerator<TSource> iterator = source.GetEnumerator()) 
    { 
        if (!iterator.MoveNext()) 
        { 
            throw new InvalidOperationException("Sequence was empty"); 
        } 
        TSource ret = iterator.Current; 
        if (iterator.MoveNext()) 
        { 
            throw new InvalidOperationException("Sequence contained multiple elements"); 
        } 
        return ret; 
    } 
} 

public static TSource Single<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    // Argument validation elided 
    TSource ret = default(TSource); 
    bool foundAny = false; 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            if (foundAny) 
            { 
                throw new InvalidOperationException("Sequence contained multiple matching elements"); 
            } 
            foundAny = true; 
            ret = item; 
        } 
    } 
    if (!foundAny) 
    { 
        throw new InvalidOperationException("No items matched the predicate"); 
    } 
    return ret; 
}

L'implémentation est déjà significativement plus complexe que pour l'opérateur First. La version sans prédicat débute de la même manière mais si nous tentons d'atteindre le premier élément, nous devons mémoriser la valeur (car nous espérons la renvoyer) et ensuite essayer d'atteindre le deuxième élément. Cette fois, si nous y arrivons, nous devons lever une exception, sinon, nous pouvons retourner la valeur précédemment mémorisée.

La version avec prédicat est un peu plus tirée par les cheveux. Nous devons toujours mémoriser la première valeur valide que nous trouvons, mais cette fois, nous devons parcourir la totalité de la liste. Nous devons donc également mémoriser si nous avons, ou pas, déjà trouvé une valeur valide. Si nous trouvons une seconde valeur valide, nous devons lever une exception. Nous devons également lever une exception si nous atteignons la fin sans ne trouver aucune valeur valide. Notez que même si nous attribuons une valeur initiale de default(TSource) à ret, nous n'atteignons jamais une instruction de retour sans qu'une valeur n'y ait été attribuée. Cependant, les règles concernant les variables non assignées ne sont pas suffisamment intelligentes pour en tenir compte. Il nous faut donc l'initialiser avec une valeur « déchet » et default(TSource) est vraiment la seule valeur disponible. Il existe une approche alternative qui n'utilise pas de foreach, dans laquelle on boucle jusqu'à trouver le premier élément valide. On l'assigne à une variable locale qui n'est déclarée qu'à ce moment-là. On enchaîne ensuite avec une seconde boucle dans laquelle on s'assure qu'il n'y a pas d'autre élément correspondant. Personnellement, je pense que c'est un peu plus complexe, raison pour laquelle j'ai utilisé le foreach ici.

La différence n'est plus aussi marquée lorsque nous implémentons SingleOrDefault :

public static TSource SingleOrDefault<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    // Argument validation elided 
    using (IEnumerator<TSource> iterator = source.GetEnumerator()) 
    { 
        if (!iterator.MoveNext()) 
        { 
            return default(TSource); 
        } 
        TSource ret = iterator.Current; 
        if (iterator.MoveNext()) 
        { 
            throw new InvalidOperationException("Sequence contained multiple elements"); 
        } 
        return ret; 
    } 
} 

public static TSource SingleOrDefault<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    // Argument validation elided 
    TSource ret = default(TSource); 
    bool foundAny = false; 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            if (foundAny) 
            { 
                throw new InvalidOperationException("Sequence contained multiple matching elements"); 
            } 
            foundAny = true; 
            ret = item; 
        } 
    } 
    return ret; 
}

Cette fois, nous nous sommes contenté de remplacer dans la version sans prédicat une instruction « throw » par une instruction « return » et nous avons retiré, dans la méthode avec prédicat, le test qui vérifie qu'un élément existe. Ici, notre instruction d'affectation de default(TSource) à la variable ret joue vraiment en notre faveur : si à aucun moment nous ne lui assignons de valeur, nous avons déjà la bonne valeur !

Voici maintenant Last :

public static TSource Last<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    // Argument validation elided 
    IList<TSource> list = source as IList<TSource>; 
    if (list != null) 
    { 
        if (list.Count == 0) 
        { 
            throw new InvalidOperationException("Sequence was empty"); 
        } 
        return list[list.Count - 1]; 
    } 

    using (IEnumerator<TSource> iterator = source.GetEnumerator()) 
    { 
        if (!iterator.MoveNext()) 
        { 
            throw new InvalidOperationException("Sequence was empty"); 
        } 
        TSource last = iterator.Current; 
        while (iterator.MoveNext()) 
        { 
            last = iterator.Current; 
        } 
        return last; 
    } 
} 

public static TSource Last<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    // Argument validation elided 
    bool foundAny = false; 
    TSource last = default(TSource); 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            foundAny = true; 
            last = item; 
        } 
    } 
    if (!foundAny) 
    { 
        throw new InvalidOperationException("No items matched the predicate"); 
    } 
    return last; 
}

Commençons par l'optimisation au début de la méthode sans prédicat. Si nous constatons que nous traitons une liste, nous pouvons simplement récupérer son nombre d'éléments, et ensuite, soit lever une exception, soit retourner l'élément avec le plus grand index. Comme optimisation supplémentaire, je pourrais sauver le nombre d'éléments dans une variable locale, mais je suppose que la propriété Count d'une IList<T> est peu coûteuse à calculer. S'il y a des objections significatives à cette supposition, je serais heureux de changer ça. Notez qu'il s'agit d'une autre situation où je présuppose que tout ce qui implémente IList<T> contiendra au maximum Int32.MaxValue éléments. Autrement, l'optimisation échouera.

Si nous n'empruntons pas le chemin optimisé, nous parcourons simplement toute la séquence en assignant à une variable locale, à chaque itération, la dernière valeur connue. Cette fois, sans raison particulière, je n'ai pas utilisé la boucle foreach. Nous aurions tout aussi bien pu avoir une variable foundAny à laquelle on aurait assigné « true » à chaque itération et qu'on aurait testé à la fin. En fait, c'est exactement le modèle que suit la version avec prédicat. Certes, cette décision nous est imposée dans une certaine mesure : nous ne pouvons pas nous déplacer juste une fois et ensuite prendre la première valeur comme « première dernière valeur connue », car elle pourrait ne pas valider le prédicat.

Il n'y a aucune optimisation pour la version de Last avec prédicat. Elle est conforme à LINQ to Objects et honnêtement, je ne sais pas pourquoi elle n'est pas optimisée. Nous pourrions facilement parcourir la séquence en sens inverse, en partant de la fin, en utilisant l'indexeur à chaque itération. Une raison possible qui semble non dénuée de sens est que quand il y a un prédicat, ce dernier peut lever une exception pour certaines valeurs. Si nous débutons de la fin alors que la collection implémente IList<T>, cela constituerait une différence notable. Je serais intéressé de savoir si c'est ou non la raison. Si quelqu'un dispose d'informations internes qu'il peut partager, j'actualiserai ce billet.

Il ne nous reste plus qu'un opérateur à implémenter, LastOrDefault :

public static TSource LastOrDefault<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    // Argument validation elided 
    IList<TSource> list = source as IList<TSource>; 
    if (list != null) 
    { 
        return list.Count == 0 ? default(TSource) : list[list.Count - 1]; 
    } 

    TSource last = default(TSource); 
    foreach (TSource item in source) 
    { 
        last = item; 
    } 
    return last; 
} 

public static TSource LastOrDefault<TSource>( 
    this IEnumerable<TSource> source, 
    Func<TSource, bool> predicate) 
{ 
    // Argument validation elided 
    TSource last = default(TSource); 
    foreach (TSource item in source) 
    { 
        if (predicate(item)) 
        { 
            last = item; 
        } 
    } 
    return last; 
}

Cette fois, mise à part l'optimisation, les formes avec et sans prédicat semblent très similaires, bien plus que pour les autres opérateurs. Dans chaque cas, nous débutons avec une valeur de retour default(TSource), et nous parcourons entièrement la séquence en mettant à jour la valeur de retour (uniquement si elle valide le prédicat lorsque nous en avons un).

Ce fut un billet plus long que ce que j'avais estimé en me levant ce matin, mais j'espère que la différence subtile entre les implémentations et le mystère de la non-optimisation de l'opérateur Last / LastOrDefault avec prédicat valaient la peine que je m'obstine un peu.

En revanche, et comme je l'ai déjà mentionné dans ce billet, je parlerai de DefaultIfEmpty la semaine prochaine. Je pense que je peux encore m'y atteler ce soir, si je me dépêche…

Il semble que je sois passé à côté de certains tests pour Single et SingleOrDefault : comment doivent-ils se comporter si le parcours complet de la séquence provoque une exception ? Il semble que dans LINQ to Objects, la surcharge sans prédicat lève une exception InvalidOperationException aussitôt qu'elle voit un deuxième élément alors que la version avec prédicat continue son parcours, même lorsqu'elle tombe sur un deuxième élément qui valide le prédicat. Cela me semble ridiculement inconsistant. J'ai ouvert un ticket Connect à ce sujet. Nous verrons ce qu'il en est…

Merci à Jon Skeet de m'avoir autorisé à traduire son article Reimplementing LINQ to Objects : Part 11 - First / Single / Last and the …OrDefault versions.

Merci à Thomas Levesque (tomlev) pour sa relecture technique toujours bienvenue.

Merci à Cédric Duprez pour la relecture orthographique de ce document.