TL;DR
Ré-indexer 10 000 fichiers à chaque enregistrement coûte plusieurs secondes. En implémentant un Merkle tree, seules les arêtes affectées sont re-résolues. Résultat : ~15 ms pour un fichier modifié, ~3 ms à vide.
Pour tester directement : documentation · code source.
Les articles précédents construisent un graph de code complet : symboles extraits par tree-sitter, embeddings sémantiques, arêtes résolues par heuristique et LSP. Mais ce graph est recalculé intégralement à chaque cartog index.
Sur un petit projet (69 fichiers, 4k lignes), ça prend ~95 ms. Acceptable. Sur un projet de 10 000 fichiers, ça grimpe à plusieurs secondes, un frein réel, surtout en mode watch où chaque sauvegarde déclenche une ré-indexation.
Si le développeur modifie un seul fichier, pourquoi ré-parser les 9 999 autres ?
Pour ne pas tout re-parser il faut savoir ce qui a changé.
Mais comment comparer deux versions d’une fonction si son numéro de ligne a seulement bougé ?
Pour faire de l’incrémental, il faut pouvoir identifier un symbole de manière stable entre deux indexations. Si le symbole change quand une ligne est ajoutée au-dessus ou au-dessus, toute comparaison devient impossible. Il ne faut donc garder que ce qui est stable.
Cartog identifie chaque symbole par file_path:kind:qualified_name : le chemin du fichier, le type de symbole (class, method, function…) et son nom qualifié, c’est-à-dire préfixé par son conteneur (UserService.authenticate plutôt que authenticate seul) :
src/auth.py:class:UserService
src/auth.py:method:UserService.authenticate
src/auth.py:function:verify_tokenCe format est :
- Stable : ajouter une ligne blanche au-dessus de
verify_tokenne change pas son ID - Déterministe : même codeg génère le même symbole ID, pas de UUID aléatoire
- Lisible : utile pour le debug et les logs
La seule chose qui invalide un ID : renommer le symbole, changer son kind, ou le déplacer dans un autre fichier. Ce sont exactement les cas où une ré-indexation est nécessaire.
Avant de parser quoi que ce soit, Cartog filtre les fichiers à travers une cascade, où chaque niveau élimine plus que le précédent :
flowchart TD
START["cartog index"] --> FORCE{"--force ?"}
FORCE -->|oui| REINSERT["Reparser tous les fichiers<br>→ réinsertion complète<br>(hashes Merkle recalculés)"]
FORCE -->|non| GIT{"Niveau 1<br>git diff disponible ?"}
GIT -->|oui| GITLIST["Fichiers signalés par git"]
GIT -->|non| ALL["Tous les fichiers"]
GITLIST --> HASH{"Niveau 2<br>SHA-256 identique ?"}
ALL --> HASH
HASH -->|oui| SKIP["Skip fichier<br>(touché mais inchangé)"]
HASH -->|non| PARSE["Niveau 3<br>Parser → diff Merkle"]Niveau 1 — Git diff : quand .git est disponible et qu’un last_commit est stocké, l’union de git diff --name-only last_commit..HEAD, git ls-files --others --exclude-standard, et des diffs working tree/cached identifie les fichiers committed, staged, unstaged, et non trackés. Les fichiers hors de cet ensemble ne sont même pas lus du disque : c’est le filtre qui apporte le plus.
Niveau 2 — SHA-256 : pour chaque fichier que le niveau 1 a laissé passer (ou tous les fichiers, à froid), le contenu est lu et hashé. Si le hash correspond à celui stocké en base, le fichier est sauté avant le parsing. Cela rattrape le cas fréquent d’un éditeur qui sauvegarde un fichier sans changement réel (timestamp modifié, contenu identique).
Niveau 3 — Merkle des symboles : seuls les fichiers réellement modifiés sont parsés, et le diff Merkle (section suivante) descend à la granularité du symbole.
Le flag --force saute les niveaux 1 et 2 : tous les fichiers sont reparsés et leurs symboles réinsérés. Les hashes Merkle (niveau 3) sont bien recalculés et restockés, mais le diff chirurgical n’est pas appliqué : c’est une réinsertion complète. Utile en cas de corruption d’index ou après un git rebase qui invalide le last_commit stocké.
Et un Merkle au niveau des dossiers ? Si on hashait
src/, on saurait que rien dedans n’a changé sans descendre.
Idée séduisante mais piégeuse. Sur tous les filesystems que Cartog cible (APFS, ext4, NTFS, btrfs), le mtime d’un dossier ne change que quand l’ensemble des noms de ses enfants change : création, suppression, renommage.Modifier le contenu d’un fichier ne remonte pas. Se fier au mtime du dossier raterait silencieusement le cas le plus fréquent (ex: un développeur qui sauve un fichier modifié).
Parcourir le dossier et hasher chaque fichier reste obligatoire : c’est exactement ce que fait le niveau 2.
On sait qu’un fichier a changé mais pas quels symboles dedans. Si on a ajouté une méthode à une classe, il est inutile de supprimer et recréer tous les symboles du fichier, y compris ses imports, ses autres fonctions, ses constantes.
Comment savoir sans tout re-parser qu’un symbole précis a changé alors qu’il vit au milieu de centaines d’autres ?
Un Merkle tree est un arbre où chaque nœud stocke un hash dérivé des hashes de ses enfants. Un changement dans n’importe quelle feuille se propage donc vers la racine.
La propriété qui rend la chose rapide : si le hash d’un nœud est identique des deux côtés, tout son sous-arbre est inchangé, on n’a pas besoin de regarder dedans. Comparer les deux hashes racines répond d’un coup à « quelque chose a-t-il bougé ? » ; et là où ils diffèrent, on ne descend que dans les branches concernées. Au lieu de comparer les centaines de symboles un à un, on suit seulement le chemin des hashes qui ont changé. C’est la même structure que Git utilise pour ses commits, et que Bitcoin pour ses blocs.
Cartog applique cette idée aux symboles extraits d’un fichier :
Les valeurs ci-dessous sont des hashes fictifs raccourcis à 4 caractères pour la lisibilité (en vrai, du SHA-256 sur 64 caractères). Point clé : un parent combine le subtree_hash de chaque enfant (pas son content_hash), pour qu’un changement dans une feuille profonde remonte bien jusqu’à la racine. Pour une feuille sans enfant, subtree_hash = content_hash.
graph TD
FILE["auth.py<br>file_hash = sha256(9f3a + 7c01)<br>= b8d2"] -->|subtree_hash 9f3a| F
F["class UserService<br>content_hash = c4e7<br>subtree_hash = sha256(c4e7 + 1a2b + 5d6e)<br>= 9f3a"] -->|subtree_hash 1a2b| M1["authenticate()<br>content_hash = 1a2b"]
F -->|subtree_hash 5d6e| M2["refresh_token()<br>content_hash = 5d6e"]
FILE -->|subtree_hash 7c01| V["verify_token()<br>content_hash = 7c01"]
style FILE fill:#e8eaf6,stroke:#3f51b5
style F fill:#e3f2fd,stroke:#1976d2
style M1 fill:#f3e5f5,stroke:#7b1fa2
style M2 fill:#f3e5f5,stroke:#7b1fa2
style V fill:#f3e5f5,stroke:#7b1fa2Le file_hash combine donc 9f3a (le subtree_hash de UserService, qui inclut déjà ses méthodes) et 7c01 (verify_token, une feuille), et non le content_hash c4e7 de la classe, qui ignorerait ses méthodes.
Si le corps de authenticate() change, son content_hash passe de 1a2b à autre chose ; le subtree_hash de UserService change donc (9f3a → nouvelle valeur), puis le file_hash de auth.py. En revanche verify_token (7c01) reste intact : son hash n’a pas bougé, on ne le ré-insère pas.
Deux niveaux de hash par symbole :
content_hash = SHA-256(kind + name + signature + code source brut du symbole)
Capture l’état exact du symbole lui-même.
subtree_hash = SHA-256(content_hash + hash des enfants triés)
Capture l’état du symbole ET de toute sa descendance (méthodes d’une classe, fonctions imbriquées).
Le tri des enfants garantit un hash canonique : l’ordre de déclaration n’affecte pas le hash si les enfants sont les mêmes.
En comparant les hashes anciens (en base) aux hashes nouveaux (extraction fraîche), Cartog classifie chaque symbole :
flowchart TD
SYM["Symbole extrait"] --> EXISTS{"ID existe<br>en base ?"}
EXISTS -->|non| ADDED["Added<br>→ INSERT"]
EXISTS -->|oui| CH{"content_hash<br>identique ?"}
CH -->|non| MODIFIED["Modified<br>→ UPDATE"]
CH -->|oui| SH{"subtree_hash<br>identique ?"}
SH -->|oui| UNCHANGED["Unchanged<br>→ SKIP"]
SH -->|non| CHILDREN["Children changed<br>→ UPDATE subtree_hash"]
OLD["Symbole en base<br>mais pas extrait"] --> REMOVED["Removed<br>→ DELETE"]
style ADDED fill:#c8e6c9,stroke:#388e3c
style MODIFIED fill:#fff9c4,stroke:#f9a825
style REMOVED fill:#ffcdd2,stroke:#d32f2f
style UNCHANGED fill:#e0e0e0,stroke:#757575
style CHILDREN fill:#e1f5fe,stroke:#0288d1| Catégorie | Condition | Action |
|---|---|---|
| Added | ID absent de la base | INSERT symbole |
| Modified | ID existe, content_hash différent | UPDATE symbole |
| Children changed | content_hash identique, subtree_hash différent | UPDATE subtree_hash uniquement |
| Unchanged | Les deux hashes identiques | Rien |
| Removed | ID en base mais pas dans l’extraction | DELETE symbole |
La catégorie “children changed” est la clé de la granularité : si on ajoute une méthode à UserService, la classe elle-même (son corps, sa signature) n’a pas changé, seul son subtree_hash est mis à jour. Les arêtes existantes vers UserService restent valides.
Modifier un symbole dans un fichier peut casser des arêtes venant d’autres fichiers. Faut-il alors réindexer tous ceux qui pointaient vers lui ?
Pas tous, seulement les arêtes affectées. Une arête est une relation entre deux symboles (A appelle B, A importe B, A hérite de B) ; c’est ce qui fait du graph un graph. Si verify_token est renommé en validate_token, les arêtes calls → verify_token depuis d’autres fichiers pointent dans le vide.
Il faut les retrouver et les ré-résoudre, mais sans toucher aux milliers d’autres arêtes restées valides.
La résolution se fait en deux étapes :
sequenceDiagram
participant DB as SQLite
participant IDX as Indexer
Note over IDX: Phase 1 : Invalidation
IDX->>DB: Trouver les arêtes dont la cible n'existe plus
DB-->>IDX: edges avec target_id dangling
IDX->>DB: SET target_id = NULL
Note over IDX: Phase 2 : Re-résolution
IDX->>DB: Résoudre les arêtes avec target_id = NULL
Note over DB: Heuristique 6 niveaux<br>uniquement sur les non-résolues
Note over IDX: Phase 3 : Centralité
IDX->>DB: Recalculer in_degree<br>pour les fichiers dirtySeules les arêtes affectées sont re-résolues, pas les milliers d’arêtes des fichiers inchangés.
La phase 3 ne recalcule la centralité (détermniné par le nombre de symboles qui pointent vers une cible donnée) que pour les fichiers dirty, c’est-à-dire ceux touchés par le diff, inutile de la recalculer partout.
En mode cartog watch, un file watcher détecte les modifications et déclenche une ré-indexation incrémentale. À chaque changement, l’index structurel (symboles et arêtes) est mis à jour : c’est tout ce dont un agent a besoin pour naviguer (recherche par nom, callees, impact).
flowchart LR
FS["Filesystem events"] -->|debounce 5s| IDX["Index incrémental<br>(symboles + arêtes)"]
IDX --> FS
style IDX fill:#e8f5e9,stroke:#4caf50Le debounce filesystem (5s par défaut, configurable via --debounce) regroupe les événements : sauvegarder un fichier en génère souvent plusieurs (write, chmod, rename), le debounce les fusionne en un seul re-index. La valeur de 5 secondes absorbe les rafales massives (git pull, branch switch) sans déclencher des tempêtes de re-index, tout en restant assez courte pour rester « live » à la frappe.
Le graph reste frais en continu : l’agent MCP qui tourne en parallèle voit les changements en quasi temps réel grâce au mode WAL (Write-Ahead Logging) de SQLite, qui permet des lectures concurrentes pendant les écritures.
Sur le projet de test (69 fichiers Python, 4k lignes) :
| Scénario | Temps |
|---|---|
| Index complet (cold) | ~95ms |
| Index incrémental (1 fichier modifié) | ~15ms |
| Index incrémental (0 changement) | ~3ms |
Le chiffre cold est publié dans le README du projet ; les deux chiffres incrémentaux sont mesurés localement via cargo bench -p cartog-indexer.
Le cas “0 changement” est le plus fréquent en mode watch (debounce sur un événement qui ne produit pas de diff réel).
Les 3ms correspondent au git diff + vérification des hashes : aucun parsing tree-sitter.
Le graph est maintenant précis et maintenu à jour en quelques secondes voire millisecondes. Tout cela est stocké un fichier SQLite local.
L’agent LLM qui doit l’exploiter n’y a pas encore accès directement.
Comment exposer ce graph à Claude Code, Cursor ou autre coding agent sans réécrire un client par éditeur ?
Ce sera le sujet du prochain article de la série : exposer un graph de code à un agent LLM via Model Context Protocol.
