Implémenter le pattern Incremental/Affected

Dans l’introduction de Maîtriser les graphes orientés par l’exemple avec JavaScript, nous avons vu à quel point les graphes orientés pouvaient être utiles. Avant de lire ce billet, je vous recommande vivement de le lire avant d’aller plus loin dans cette série.

L’objectif de cette série est de démontrer l’utilité et la puissance des graphes orientés en implémentant des exemples concrets avec JavaScript.

Commençons par présenter le sujet du jour

Notre objectif du jour est d’expliquer de manière simplifiée comment fonctionne le pattern Affected/Incremental. Toute l’idée derrière la détection des projets/packages affectés consiste à n’exécuter les tâches (build, lint, test) que sur les parties d’un projet qui changent, optimisant ainsi les ressources et gagnant du temps lorsqu’on travaille sur de gros projets.

Prenons par exemple une simple application frontend JavaScript (app.jsx) avec deux libs :

une lib design system pour exporter vos composants UI personnalisés (par exemple : en encapsulant Material UI ou Angular Material avec des thèmes personnalisés)
une lib date formatting pour configurer un ensemble universel de règles permettant de manipuler les dates

Notre projet ressemblerait à ceci :

project-folder/
│
└───design-system/
|   |   dist/
│   │   component1.jsx

│
└───temporal/
│   |   dist/
│   │   dateFormat.js
|
|   dist/
|   app.jsx
|   package.json

Notre app.jsx représente notre fichier d’entrée et utilise des fonctionnalités provenant à la fois de la lib design-system et de la lib temporal.

app.jsx

import Component1 from "./design-system/component1.jsx";
import { hoursToMilliseconds } from "./temporal/dateFormat.js";

function myApp() {
  return <Component1> {hoursToMilliseconds(2)} </Component1>;
}

Pour builder l’application entière, imaginons que nous ayons un script npm qui bundle toutes les libs et le point d’entrée dans un unique fichier JavaScript :

# Bundle l'application entière, y compris les libs `design-system` et `temporal`
$ npm run build

Vous vous demandez peut-être quel est le problème avec cette approche. La réponse est qu’il n’y a pas encore de problème, et ce type de bundling convient probablement la plupart du temps pour des projets de petite à moyenne taille.

Cependant, si vos libs design-system et temporal finissent par grossir et que vous ajoutez encore plus de bibliothèques (plus de composants, mais aussi des assets comme des images, des polices, etc.), vous pourriez rencontrer des problèmes de performance lors du build de l’application complète.

Démontrons cela très facilement :

project-folder/
│
└───design-system/ # 100+ composants
│
└───temporal/ # 50+ fichiers
|
└───lib3/ # bibliothèque utilisant node-sass (près de 5 Mo)
|
└───lib4/ # bibliothèque utilisant de lourds modules npm

Disons que ce projet met X secondes à être entièrement bundlé. Maintenant, imaginez que vous ne changiez que la couleur de votre design-system/component1.jsx :

const component1 = styled.div`
  color: red;
`;

Génial ! Votre composant a maintenant fière allure… mais vous devez rebuilder votre application entière, ce qui inclut également le rebuild des lourdes lib3 et lib4. Nous devons builder tout, à chaque fois que nous voulons livrer l’application principale, alors que tout n’a pas changé et n’a donc pas nécessairement besoin d’être rebuildé.

Ce type de problème est souvent rencontré dans les monorepos où de nombreuses apps et bibliothèques partagent les mêmes outils de build/test/lint.

Présentation de la killer feature : le pattern Incremental/Affected

Si vous utilisez des outils de monorepo comme Nx, Turborepo ou Rush, vous avez probablement entendu parler des patterns Incremental et/ou Affected.

Si vous n’êtes pas à l’aise avec ce qu’est un monorepo et quels sont ses objectifs, je vous recommande de jeter un œil à un petit rappel à ce sujet ici.

Dans ce billet, nous utiliserons le mot Affected, mais Incremental signifie littéralement la même chose ici.

Ok, mais quel rapport avec les graphes orientés ? L’outil en charge de cela (par exemple : Turborepo, Nx, Rush) peut introspecter votre projet, et émettre en interne un graphe orienté acyclique chargé d’établir les dépendances entre les différentes parties de votre projet. En s’appuyant sur le graphe émis et un cache persisté (lui aussi géré par l’outil), cela permet des builds intelligents et bien d’autres tâches qui dépendent de l’état du projet (linting, testing, etc.).

Graphe orienté acyclique d'une application principale dépendant de cinq bibliothèques, où seules les bibliothèques affectées sont rebuildées.

Dans l’image ci-dessus, nous pouvons voir un projet utilisant une stratégie affected pour ne builder que ce qui avait réellement besoin d’être rebuildé. Lors du build de la Main App après que la Library 2 a changé, seules la Library 1 et la Library 2 doivent être rebuildées. L’autre partie du graphe (Library 3, Library 4, Library 5) reste non affectée, donc la version en cache de ces bibliothèques peut être utilisée dans le build final (pas besoin de les rebuilder).

Commençons par implémenter une version minimaliste du pattern Affected pour un projet contenant trois bibliothèques distinctes.

/**
 * lib1 dépend de lib3 (via l'utilisation de lib3.MyLib3Component)
 * tandis que la library 2 est indépendante.
 */
const lib1Metadata = {
  id: "lib1",
  adjacentTo: [],
  payload: {
    component: `<lib3.MyLib3Component/ >`,
  },
};

const lib2Metadata = {
  id: "lib2",
  adjacentTo: [],
  payload: { component: `<div>hello from lib2</div>` },
};

const lib3Metadata = {
  id: "lib3",
  adjacentTo: [],
  payload: { component: `<MyLib3Component>hello lib3</MyLib3Component>` },
};

Nous devons maintenant exprimer nos différents composants dans le contexte de notre graphe que nous utiliserons par la suite. Commençons par ajouter les éléments fondamentaux d’un graphe : les sommets (vertices). Un sommet peut représenter n’importe quel type d’élément, ce qui dans notre cas correspond à une bibliothèque d’un projet donné.

import { DiGraph } from "digraph-js";
const projectGraph = new DiGraph();

// Chaque projet est représenté par un sommet (nœud)
projectGraph.addVertices(lib1Metadata, lib2Metadata, lib3Metadata);

Trois nœuds de bibliothèque ajoutés au graphe en tant que sommets, sans aucune arête les reliant pour l'instant.

Maintenant que nous avons ajouté nos sommets, nous devons représenter les relations entre eux en ajoutant les arêtes appropriées. Dans notre projet d’exemple, lib1 dépend de lib3 (en utilisant le composant de lib3). Par conséquent, cet import crée une relation implicite entre ces nœuds et doit donc être représenté par une arête.

/**
 * lib1 dépend de lib3, nous devons représenter cette relation
 * en ajoutant une arête de lib1 vers lib3.
 */
projectGraph.addEdge({ from: lib1Metadata, to: lib3Metadata });

Trois nœuds de bibliothèque dans le graphe avec une arête orientée de lib1 vers lib3 représentant la dépendance.

Nous venons de terminer d’exprimer les relations entre les bibliothèques de notre projet, nous sommes donc maintenant prêts à implémenter notre système de cache afin de permettre les builds affected !

/**
 * Simulation d'un cache simple, persistant une valeur
 * hashée du composant.
 * Dans un projet réel, vous utiliseriez quelque chose
 * comme la bibliothèque "folder-hash" pour générer des hashes
 * pour un dossier donné contenant des sous-répertoires et des fichiers.
 */

const cache = {
  lib1: {},
  lib2: {},
  lib3: {},
};

La première fonction dont nous avons besoin est une fonction pour builder une bibliothèque. Durant ce processus de build, son contenu est hashé et stocké dans l’objet cache.

import crypto from "node:crypto";

function buildLibrary(library) {
  // Crée un SHA1 à partir du contenu de la bibliothèque
  const libraryHashedContent = crypto
    .createHash("sha1")
    .update(library.payload.component)
    .digest("hex");

  console.log(`Building library: '${library.id}'`);
  // Webpack, Rollup ou tout autre bundler peut être exécuté ici

  // Stocke le contenu hashé dans le cache
  cache[library.id].component = libraryHashedContent;
}

En utilisant ce cache, il est assez simple de comparer si une bibliothèque a changé. Si nous sommes capables de détecter qu’une bibliothèque a changé, cela signifie que nous sommes capables de détecter si elle doit être rebuildée :

function isLibraryAffected(library) {
  const libraryHashedContent = crypto
    .createHash("sha1")
    .update(library.payload.component)
    .digest("hex");

  return libraryHashedContent !== cache[library.id].component;
}

Désormais, dès que nous changeons quelque chose dans une bibliothèque, nous serons capables de détecter les changements et d’invalider le cache.

Build hashé + Cache = Build affected

Maintenant que nous sommes capables de builder une bibliothèque, d’en générer un hash et de le stocker dans un cache où les versions de build peuvent être comparées au fil du temps, nous pouvons assembler la fonction centrale du pattern Affected :

function buildAffected(library) {
  /**
   * Si le composant est toujours le même (i.e : la donnée de hash n'a pas changé), nous
   * ne voulons pas le rebuilder. S'il est "Affected", nous devons l'invalider
   */
  if (isLibraryAffected(library)) {
    // Le hash du composant a changé, ce qui signifie que nous devons builder la bibliothèque
    buildLibrary(library);

    return { hasLibraryBeenRebuilt: true };
  }

  // La lib n'a pas changé donc ne nécessite pas un nouveau build
  console.log(`Using cached version of '${library.id}'`);

  return { hasLibraryBeenRebuilt: false };
}

Essayons d’exécuter un build Affected sur une bibliothèque donnée :

// build lib1 en utilisant la détection Affected
buildAffected(lib1Metadata);
// => affiche :  "Building library: 'lib1'";

// relance un build sans aucun changement plusieurs fois
buildAffected(lib1Metadata);
buildAffected(lib1Metadata);
buildAffected(lib1Metadata);
// => affiche à chaque fois : "Using cached version of 'lib1'";

// change le contenu de lib1
lib1Metadata.payload.component = "<div> Hello lib1 </div>";

// relance un build
buildAffected(lib1Metadata);
// => affiche :  "Building library: 'lib1'";

Ok cool, nous avons démontré comment ce pattern fonctionne pour une bibliothèque donnée. Vous vous demandez peut-être pourquoi le pattern Affected est si utile dans les gros projets comprenant des centaines de bibliothèques qui dépendent les unes des autres. La réponse est que le pattern Affected se révèle extrêmement puissant et utile dans un projet où des calculs inutiles sont économisés. Si vous travaillez sur un projet de trois bibliothèques, cela ne vaut probablement pas la peine d’implémenter le pattern Affected, qui vous coûtera plus de CPU que de builder depuis zéro à chaque fois.

Assez parlé, continuons notre projet d’exemple avec un cas d’usage qui nous permettra de ressentir sa puissance montante.

Implémentation du pattern Affected avec digraph-js

digraph-js est une bibliothèque qui aide à construire des graphes orientés et nous permet de les parcourir sans effort

En suivant l’exemple, nous allons maintenant implémenter une version plus complète du pattern, qui inclut la détection de plusieurs bibliothèques en utilisant la bibliothèque digraph-js.

Pour rappel rapide, nous avons toujours trois libs dans notre projet d’exemple :

const lib1Metadata = {
  id: "lib1",
  adjacentTo: [],
  payload: {
    component: `<lib3.MyLib3Component />`,
  },
};

const lib2Metadata = {
  id: "lib2",
  adjacentTo: [],
  payload: { component: `<div>hello lib2</div>` },
};

const lib3Metadata = {
  id: "lib3",
  adjacentTo: [],
  payload: { component: `<MyLib3Component>hello lib3</MyLib3Component>` },
};

lib1 dépend de lib3 (lib1 utilise “MyLib3Component”)
lib2 ne dépend de rien (aucune dépendance)
lib3 ne dépend de rien (aucune dépendance)

Ce que les graphes orientés nous permettent, c’est qu’étant donné une bibliothèque racine (qui peut être n’importe quel nœud du graphe), nous pouvons parcourir toutes les dépendances de cette bibliothèque en suivant les arêtes pointant vers d’autres nœuds du graphe. Grâce à cette fonctionnalité, nous sommes capables de déterminer de quelles autres bibliothèques la bibliothèque racine dépend.

Construisons une fonction dont l’objectif est de builder toutes les dépendances d’un nœud racine donné. Pour l’instant, le nœud racine ne connaît pas le statut de tous ses enfants (qu’ils aient été rebuildés ou non).

// Étant donné un nœud racine, nous parcourons le graphe à la recherche de dépendances
function* buildAllRootLibraryDependencies(rootLibrary) {
  // Parcourt toutes les dépendances de rootLibrary
  for (const rootLibraryDependency of projectGraph.getAdjacentVerticesTo(
    rootLibrary
  )) {
    /**
     * Build récursivement les bibliothèques affected en partant des dépendances
     * les plus profondes de la bibliothèque racine.
     */
    yield* buildAllLibraryDependencies(rootLibraryDependency);
  }

  /**
   * Quand nous atteignons une dépendance qui n'a aucune autre dépendance, nous
   * savons que nous avons fini de descendre dans l'arbre des dépendances.
   * Si la bibliothèque a été rebuildée, nous devons en informer le
   * parent afin d'invalider récursivement les nœuds sur le
   * chemin parcouru.
   */
  const { hasLibraryBeenRebuilt } = buildAffected(rootLibrary);

  yield hasLibraryBeenRebuilt;
}

Nous pouvons parcourir chaque dépendance du nœud racine et la rebuilder si elle est affected. Maintenant, nous devons inclure le nœud racine dans ce processus affected en utilisant la fonction buildAllRootLibraryDependencies ci-dessus.

Il y a 2 conditions qui imposent que la bibliothèque racine soit rebuildée :

Au moins une des dépendances de la bibliothèque a changé (déterminable en gardant la trace de l’état de chaque enfant)
La bibliothèque racine elle-même a changé (la même comparaison de hash simple mentionnée dans la première partie du billet)

Implémentons cette dernière fonction :

/**
 * Build tout avec la stratégie affected, y compris la bibliothèque
 * racine elle-même
 */
function buildEverythingAffectedIncludingRootLibrary(rootLibrary) {
  const rootLibraryDependencies =
    projectGraph.getAdjacentVerticesTo(rootLibrary);
  const allRebuiltLibraries = [];

  for (const dependencyLibrary of rootLibraryDependencies) {
    /**
     * Garde la trace de tous les builds des enfants pour savoir si certains
     * ont été rebuildés. S'il n'y a aucune dépendance affected, le
     * tableau resterait vide
     */
    allRebuiltLibraries.push([
      ...buildAllRootLibraryDependencies(dependencyLibrary),
    ]);
  }

  /**
   * Toutes les dépendances de la bibliothèque racine ont été rebuildées si nécessaire (i.e : affected).
   * Cependant, nous devons maintenant déterminer si la bibliothèque racine doit elle aussi être
   * rebuildée. Il y a 2 conditions qui imposent que la bibliothèque racine soit rebuildée :
   * - La bibliothèque racine elle-même a changé
   * - Au moins une des dépendances de la bibliothèque a changé
   */
  const HAS_LIBRARY_BEEN_REBUILT = true;
  const atleastOneLibraryChanged = allRebuiltLibraries
    .flat()
    .includes(HAS_LIBRARY_BEEN_REBUILT);

  if (atleastOneLibraryChanged) {
    buildLibrary(rootLibrary);
  } else {
    // Vérifie si la bibliothèque elle-même a changé en lançant la détection affected sur la bibliothèque racine
    buildAffected(rootLibrary);
  }
}

C’est tout ! Le pattern Affected est maintenant pleinement démontré, en utilisant les graphes orientés pour parcourir toutes les dépendances d’un nœud racine donné et en utilisant une comparaison de cache pour déterminer si un nœud enfant doit être invalidé puis rebuildé.

Vous n’êtes pas convaincu ? Confirmons cela en testant avec une fonction :

function buildProjectUsingAffectedStrategy() {
  console.log("\n----STEP 1-----");
  // Build pour la première fois
  buildEverythingAffectedIncludingRootLibrary(lib1Metadata);

  console.log("\n----STEP 2-----");
  /**
   * Build pour la deuxième fois mais aucune dépendance de lib1 n'a changé (ni
   * lib3 ni lib4) donc elle reste UNAFFECTED (i.e : utilisation du cache)
   */
  buildEverythingAffectedIncludingRootLibrary(lib1Metadata);

  console.log("\n----STEP 3-----");
  /**
   * Changeons maintenant le contenu du composant de lib3.
   * Rappelez-vous, lib1 dépend de lib3 via l'utilisation de lib3.MyLib3Component donc
   * ce changement devrait déclencher un build affected.
   */
  console.log("Changing lib3's content...");
  // addMutation est une fonction qui met à jour la valeur d'un sommet donné dans le graphe
  projectGraph.addMutation(lib3Metadata, {
    // nouveau composant lib3
    component: `<MyLib3Component>Hello affected lib3!</MyLib3Component>`,
  });

  console.log("\n----STEP 4-----");
  /**
   * Maintenant que lib3 (dépendance de lib1) a changé, lib3 et lib1 sont toutes deux considérées
   * comme affected. Cela signifie que nous devons rebuilder les deux, en commençant par lib3 (lib1 doit être buildée
   * avec la dernière version de lib3).
   */
  buildEverythingAffectedIncludingRootLibrary(lib1Metadata);
}

Voici la sortie :

----STEP 1-----
Building library: 'lib3' // build pour la première fois
Building library: 'lib1' // build pour la première fois

----STEP 2-----
Using cached version of 'lib3' // build pour la deuxième fois mais rien n'a changé donc on peut utiliser une version en cache de lib3
Using cached version of 'lib1' // build pour la deuxième fois mais rien n'a changé ni du côté de lib3 ni de lib1 elle-même donc on peut utiliser une version en cache de lib1

----STEP 3-----
Changing lib3's content... // mise à jour du contenu de lib3

----STEP 4-----
Building library: 'lib3' // lib3 a changé donc doit être rebuildée
Building library: 'lib1' // lib1 n'a pas changé mais sa dépendance directe "lib3" a changé donc elle doit être rebuildée

Cette fois c’est vraiment tout ! Nous avons démontré la vue d’ensemble de la manière dont le pattern Affected fonctionne sous le capot.

Dépôt GitHub

N’hésitez pas à consulter l’exemple complet ici utilisé dans la dernière partie du billet.

À suivre

Dans la prochaine partie de cette série, nous parlerons de la détection de dépendances circulaires (qui est par exemple implémentée par un plugin ESLint du type eslint-plugin-import/no-cycle) rendue possible grâce aux graphes orientés !