Atelier : recodez la Collection de Laravel

Séance 5 · ~2 périodes en classe, la fin chez vous

À la fin de ce chapitre, vous serez capables de :

1. écrire une pile, une liste et une collection qui font passer les tests fournis ;
2. lire et écrire une fonction passée en paramètre, avec la syntaxe courte fn comme avec function ;
3. justifier pourquoi une transformation renvoie une nouvelle collection au lieu de modifier l'ancienne ;
4. estimer le coût d'un bout de code en O(1), O(n) ou O(n²) ;
5. lire une chaîne d'appels collect(...)->filter(...)->map(...)->sum() dans la documentation de Laravel.

Le dépôt : https://github.com/opmvpc/collection-26

1. Le code qui sent mauvais#

Cinq minutes, en binôme. $items est le contenu du sac d'Arthur : quatre tableaux associatifs, chacun avec une clé name et une clé weight. Le but est d'afficher les objets légers et leur poids total. Ce code s'exécute. Il porte pourtant plusieurs défauts de conception, ce qu'on appelle un code qui sent mauvais (code smell). Lesquels ?

$total = 0;
$noms = '';
for ($i = 0; $i < count($items); $i++) {
    if ($items[$i]['weight'] < 5) {
        $total = $total + $items[$i]['weight'];
        $noms = $noms . $items[$i]['name'] . ', ';
    }
}

echo 'Léger : ' . $noms . '(' . $total . ' kg)';
// Léger : Épée longue, Potion de soin, Torche, (5 kg)

2. Pourquoi vous allez l'écrire vous-mêmes#

Dans Laravel, User::all() ne renvoie pas un tableau PHP. Il renvoie un objet : une Illuminate\Database\Eloquent\Collection, qui hérite de Illuminate\Support\Collection. C'est la même chose pour $post->comments, pour le résultat d'un where()->get(), et pour presque tout ce qui contient plusieurs éléments. La documentation de Laravel suppose que vous savez lire ceci :

$noms = $users->filter(fn ($user) => $user->isActive())
    ->sortBy(fn ($user) => $user->name)
    ->pluck('name');

Pour lire cet exemple, il faut comprendre filter(), sortBy(), pluck() et la syntaxe fn. Tant que ces quatre choses restent floues, un tiers de la documentation est illisible.

Vous allez donc construire votre propre Collection en trois étapes. À la fin, vous lancerez la même chaîne d'appels sur votre classe et sur celle de Laravel.

3. Le dépôt et les commandes#

composer install
composer test

Tout est rouge au départ. Chaque méthode de src/ lève LogicException('À implémenter'). Complétez-les pour qu'elles respectent les tests fournis.

Une étape à la fois :

composer test -- --group=etape-1
composer test -- --group=etape-2
composer test -- --group=etape-3
composer test -- --group=bonus

L'onglet Actions de votre fork lance une vérification par étape, indépendante des autres. Une étape 1 rouge n'empêche pas l'étape 3 de tourner.

Deux règles, les mêmes qu'au chapitre 7 : ne modifiez pas les tests fournis, et ne touchez pas à ListInterface. Les tests sont le cahier des charges, l'interface est le contrat.

4. Étape 1 : la pile#

Fourni : src/Stack.php, avec les cinq signatures et les indices en commentaire. À écrire : les cinq corps de méthode.

Une pile d'assiettes : on pose sur le dessus, on reprend sur le dessus. Le dernier arrivé est le premier servi. C'est une pile LIFO, pour last in, first out. Dans le Donjon, c'est l'historique des salles visitées, et pop() fait demi-tour.

@startuml
interface Countable {
  +count(): int
}
class Stack {
  -elements: array
  +push(element: mixed): void
  +pop(): mixed
  +peek(): mixed
  +isEmpty(): bool
  +count(): int
}
Countable <|.. Stack
note right of Stack : Le dernier empilé est le premier dépilé.
@enduml

Une fois la classe écrite :

$visitees = new Stack();
$visitees->push('Entrée');
$visitees->push('Couloir');
$visitees->push('Salle du trône');

echo $visitees->peek();   // Salle du trône
echo $visitees->pop();    // Salle du trône
echo $visitees->pop();    // Couloir
echo count($visitees);    // 1

Un mot sur count($visitees). Votre classe déclare implements Countable : PHP accepte donc de lui appliquer la fonction native count(), qui appelle votre méthode count(). Comme au chapitre 6, une interface native ouvre la syntaxe du langage à vos objets.

Ce que les tests attendent

Indice : tout se joue à la fin du tableau. array_pop() retire le dernier élément et vous le rend. array_key_last() donne l'index du dernier sans y toucher.

Vérification : composer test -- --group=etape-1, 9 tests verts.

Question : pourquoi une pile n'a-t-elle pas de méthode get(int $index) ? Qu'est-ce qu'on gagne à interdire quelque chose ?

5. Étape 2 : la liste et son contrat#

Fourni : l'interface src/ListInterface.php, à ne pas modifier, et src/ArrayList.php avec ses onze signatures et sa méthode guardIndex() déjà écrite. À écrire : les onze corps de méthode.

Une liste indexée de 0 à size() - 1, sans trou. C'est la contrainte importante : après remove(1), l'ancien index 2 devient l'index 1. Tout ce qui suit se décale.

@startuml
interface ListInterface {
  +push(element: mixed): void
  +get(index: int): mixed
  +set(index: int, element: mixed): void
  +remove(index: int): void
  +indexOf(element: mixed): int
  +includes(element: mixed): bool
  +size(): int
  +isEmpty(): bool
  +clear(): void
  +toArray(): array
  +__toString(): string
}
class ArrayList {
  #elements: array
  #guardIndex(index: int): void
}
ListInterface <|.. ArrayList
note right of ListInterface : Un contrat dit ce qu'on peut faire, pas comment.
@enduml

$compagnie = new ArrayList();
$compagnie->push('Arthur');
$compagnie->push('Perceval');
$compagnie->push('Merlin');
$compagnie->remove(1);

echo $compagnie->get(1);              // Merlin
echo $compagnie->size();              // 2
echo $compagnie->indexOf('Perceval'); // -1

Ce que les tests attendent

// TypeError: ArrayList::indexOf(): Return value must be of type int, false returned

Indice : array_splice() retire un élément et renumérote les suivants. La méthode guardIndex() est fournie : appelez-la au début de get(), set() et remove().

Vérification : composer test -- --group=etape-2, 18 tests verts.

Question : ListInterface ne contient aucune ligne de code, seulement des signatures. À quoi sert un fichier pareil ? Le bonus donne la réponse.

6. Une fonction passée en paramètre#

L'étape 3 repose sur une idée : une fonction est une valeur comme une autre. On peut la ranger dans une variable ou la passer en paramètre. Une fonction passée à une autre pour être appelée par elle s'appelle un callback.

$crier = fn (string $nom): string => mb_strtoupper($nom) . ' !';

echo $crier('Arthur');                                     // ARTHUR !
echo implode(' ', array_map($crier, ['Arthur', 'Merlin'])); // ARTHUR ! MERLIN !

fn (paramètres): type => expression est la fonction fléchée. Une seule expression, dont le résultat est renvoyé sans return. C'est la forme que vous verrez partout dans Laravel. Elle utilise les variables du code qui l'entoure sans avoir à les déclarer.

$limite = 5.0;
$estLeger = fn (Item $item): bool => $item->weight < $limite;

echo $estLeger(new Item('Torche', 1.0)) ? 'oui' : 'non';    // oui
echo $estLeger(new Item('Bouclier', 6.0)) ? 'oui' : 'non';  // non

L'écriture plus ancienne, function () { ... }, reste utile quand le corps fait plusieurs lignes. Mais elle n'emporte rien toute seule : il faut lister les variables extérieures après use.

$limite = 5.0;
$estLeger = function (Item $item): bool {
    return $item->weight < $limite;
};

echo $estLeger(new Item('Torche', 1.0)) ? 'oui' : 'non';
// Warning: Undefined variable $limite
// non

7. Étape 3 : la Collection#

Fourni : src/Collection.php, avec les treize signatures et un indice pour chacune. À écrire : les treize corps de méthode, en commençant par make().

Les exemples qui suivent travaillent sur le sac d'Arthur. La classe Item vient des tests du dépôt, dans tests/Fixtures/Item.php. C'est une version réduite de celle du chapitre 4 : un nom, un poids, tous deux public readonly. On écrit donc $item->weight sans accesseur.

$butin = [
    new Item('Épée longue', 3.5),
    new Item('Potion de soin', 0.5),
    new Item('Bouclier', 6.0),
    new Item('Torche', 1.0),
];

@startuml
interface Countable {
  +count(): int
}
interface IteratorAggregate {
  +getIterator(): Traversable
}
class ArrayList {
  #elements: array
  +push(element: mixed): void
  +size(): int
  +toArray(): array
}
class Collection {
  +{static} make(elements: array): Collection
  +map(callback: callable): Collection
  +filter(callback: callable): Collection
  +reduce(callback: callable, initial: mixed): mixed
  +each(callback: callable): Collection
  +first(callback: ?callable): mixed
  +last(callback: ?callable): mixed
  +sum(callback: ?callable): float|int
  +pluck(key: string): Collection
  +sortBy(callback: callable): Collection
  +reverse(): Collection
  +count(): int
  +getIterator(): Traversable
}
ArrayList <|-- Collection
Countable <|.. Collection
IteratorAggregate <|.. Collection
note right of Collection : Une transformation rend une nouvelle Collection.
@enduml

Le triangle plein se lit Collection extends ArrayList. Vous ne réécrivez ni push, ni get, ni size, ni toArray, ni __toString. Tout est hérité. Collection n'ajoute que les transformations, plus count(), qui vient de Countable.

La règle de l'étape#

Une transformation ne modifie jamais la collection de départ. Elle en renvoie une nouvelle. Cela vaut pour map, filter, pluck, sortBy et reverse. each() est la seule exception : elle exécute le callback pour son effet, puis rend la collection elle-même.

$sac = Collection::make($butin);
$legers = $sac->filter(fn (Item $item): bool => $item->weight < 5.0);

echo $sac->size();      // 4
echo $legers->size();   // 3

Le sac d'origine n'a pas bougé. C'est ce qui rend le chaînage sûr : chaque maillon reçoit une collection et en produit une autre, sans modifier la précédente.

$poids = Collection::make($butin)
    ->filter(fn (Item $item): bool => $item->weight < 5.0)
    ->pluck('weight')
    ->sum();

echo $poids;   // 5

Quatre lignes, et chacune fait une seule chose. Comparez avec les dix lignes du début du chapitre.

make(), la fabrique#

Collection::make([...]) est une méthode statique : on l'appelle sur la classe, pas sur un objet. Comme Dice::d6() au chapitre 1, et comme le collect([...]) de Laravel. Écrivez-la en premier, les autres méthodes s'appuient dessus. Pour map() et filter(), remplissez ensuite un nouveau tableau, puis rendez static::make($resultat).

Countable et IteratorAggregate#

Countable permet d'utiliser count() sur votre objet. IteratorAggregate permet de le parcourir avec foreach.

echo count($sac);   // 4

foreach ($sac->sortBy(fn (Item $item): float => $item->weight) as $item) {
    echo $item->name . ' (' . $item->weight . " kg)\n";
}
// Potion de soin (0.5 kg)
// Torche (1 kg)
// Épée longue (3.5 kg)
// Bouclier (6 kg)

IteratorAggregate demande une seule méthode, getIterator(), qui rend un ArrayIterator construit sur vos éléments. Une ligne, et votre classe se parcourt comme un tableau.

reduce, la plus abstraite des trois#

map() transforme chaque élément. filter() garde ceux qui passent le test. reduce() calcule une seule valeur à partir de tous les éléments, en promenant un accumulateur, c'est-à-dire une variable qui garde le résultat intermédiaire. Le callback le reçoit en premier argument, et l'élément en second.

$phrase = Collection::make($butin)
    ->pluck('name')
    ->reduce(fn (string $acc, string $nom): string => $acc === '' ? $nom : $acc . ', ' . $nom, '');

echo $phrase;   // Épée longue, Potion de soin, Bouclier, Torche

Le second argument, ici la chaîne vide, est la valeur de départ de l'accumulateur. Cet exemple ajoute le séparateur avant chaque nom sauf le premier, donc la virgule en trop du début de chapitre ne peut plus se produire.

Ce que les tests attendent

Vérification : composer test -- --group=etape-3, 24 tests verts.

8. Le coût d'un algorithme#

Vous avez deux façons d'atteindre un élément : par index avec get(), ou en parcourant avec indexOf(). Elles ne coûtent pas la même chose, et la notation Big O le dit en un symbole. On compte des étapes, pas des secondes, et on ne garde que ce qui domine quand n grandit.

$noms = ['Arthur', 'Perceval', 'Merlin', 'Guenièvre'];

$premier = $noms[0];          // O(1)  : une étape, quelle que soit la taille

foreach ($noms as $nom) {     // O(n)  : 4 étapes pour 4 éléments
}

foreach ($noms as $a) {       // O(n²) : 16 étapes pour 4 éléments
    foreach ($noms as $b) {
    }
}

Retenez la dernière ligne : deux boucles imbriquées qui parcourent chacune les n éléments donnent O(n²), et le coût grimpe très vite.

9. Côte à côte avec la Collection de Laravel#

Comparons. À gauche votre classe, à droite Illuminate\Support\Collection.

// Votre Collection
Collection::make($butin)
    ->filter(fn (Item $item): bool => $item->weight < 5.0)
    ->sum(fn (Item $item): float => $item->weight);
// 5

// Illuminate\Support\Collection
collect($butin)
    ->filter(fn (Item $item): bool => $item->weight < 5.0)
    ->sum(fn (Item $item): float => $item->weight);
// 5

Mêmes noms de méthodes, mêmes callbacks, même règle de la nouvelle collection. collect() est un raccourci pour new Collection(...), l'équivalent de votre make().

La vraie Collection a une centaine de méthodes de plus, comme groupBy ou chunk. Inutile de les mémoriser : vous avez de quoi les comprendre en lisant leur description.

10. Bonus : LinkedList#

Même contrat, autre mécanique. Les éléments ne sont plus rangés côte à côte : chaque Node garde un élément et pointe vers le suivant.

Lire le 50e élément demande donc de traverser les 49 précédents, soit O(n) au lieu de O(1). En revanche, retirer un maillon déjà trouvé ne décale rien : on rebranche un pointeur. Les tests du bonus sont les mêmes que ceux de l'étape 2. Un paramètre typé ListInterface accepte une ArrayList comme une LinkedList, alors que tout diffère à l'intérieur.

À retenir#

• Une transformation renvoie une nouvelle collection. map, filter, sortBy et reverse ne modifient jamais l'original, dans votre classe comme dans Laravel.
• Un callback est une fonction passée en paramètre. fn (…) => … utilise les variables autour d'elle. function (…) use (…) { … } demande de les lister.
• Collection extends ArrayList : on hérite de ce qui existe déjà, on n'ajoute que ce qui est nouveau.
• Les interfaces natives ouvrent la syntaxe de PHP à vos objets. Countable donne count(), IteratorAggregate donne foreach.
• Big O compte les étapes, pas les secondes. Accès par index O(1), parcours O(n), boucles imbriquées O(n²).

Exercices#

1. Obligatoire. Les groupes etape-1 à etape-3 verts, poussés, vérification verte dans l'onglet Actions.
2. Obligatoire. Réécrivez le code de l'ouverture avec votre Collection : quatre lignes, une virgule au bon endroit, un nom pour le 5.
3. Au choix. Ajoutez avg(?callable $callback = null): float, qui rend la moyenne et 0.0 sur une collection vide. Réutilisez sum() et count(). Ajoutez deux tests dans un nouveau fichier tests/Unit/AvgTest.php, avec ->group('etape-3'). Ne modifiez pas les tests fournis.
4. Au choix. Ouvrez la documentation de Laravel sur les collections et repérez trois méthodes dont le nom suffit à deviner le comportement. Notez ce que vous pensez qu'elles renvoient, puis vérifiez. On en discute en début de séance 6.
5. Bonus. LinkedList, groupe bonus.