Cartographier un Codebase pour un LLM avec Tree-sitter + PageRank

Cartographier un Codebase pour un LLM avec Tree-sitter + PageRank

Le probleme : un LLM ne peut pas lire tout votre code

Quand vous donnez un codebase a un LLM, vous avez un choix douloureux. Soit vous lui envoyez tous les fichiers et vous explosez la fenetre de contexte (et la facture). Soit vous selectionnez manuellement les fichiers pertinents et vous passez votre temps a deviner ce dont il a besoin. Dans les deux cas, c’est perdant.

Le coeur du probleme est une question de priorisation. Dans un projet de 500 fichiers, peut-etre 30 sont vraiment importants pour la tache en cours. Mais lesquels ? Un humain le sait instinctivement — il connait les fichiers centraux, les modules tres references, les points d’entree. Un LLM, lui, ne sait rien avant de lire.

C’est exactement ce que resout RepoMap : un outil qui genere une carte condensee du code source, triee par importance, en utilisant Tree-sitter pour le parsing et PageRank pour le classement. J’ai construit cet outil pour mes propres besoins d’orchestration d’agents IA sur des codebases reels, et il tourne aujourd’hui en production comme serveur MCP.

L’architecture en 4 couches

RepoMap est organise en couches claires, chacune avec une responsabilite unique :

  1. Parsing Tree-sitter (get_tags_raw) — extrait definitions et references de chaque fichier
  2. Graphe de dependances (get_ranked_tags) — construit un graphe oriente entre fichiers
  3. PageRank (nx.pagerank) — classe les fichiers par importance structurelle
  4. Rendu contraint (to_tree) — genere la sortie en respectant un budget de tokens

Regardons chaque couche en detail.

Couche 1 : Tree-sitter plutot que ctags ou grep

Le choix de Tree-sitter n’est pas anodin. J’ai longtemps utilise ctags, et la raison pour laquelle j’ai bascule est simple : ctags ne capture que les definitions, pas les references. Or, ce sont les references qui forment les aretes du graphe.

Voici comment fonctionne l’extraction dans repomap_class.py :

def get_tags_raw(self, fname: str, rel_fname: str) -> List[Tag]:
    lang = filename_to_lang(fname)
    if not lang:
        return []

    language = get_language(lang)
    parser = get_parser(lang)
    scm_fname = get_scm_fname(lang)

    code = self.read_text_func_internal(fname)
    tree = parser.parse(bytes(code, "utf-8"))

    query_text = read_text(scm_fname, silent=True)
    query = language.query(query_text)
    cursor = QueryCursor(query)
    captures = cursor.captures(tree.root_node)

    tags = []
    for capture_name, nodes in captures.items():
        for node in nodes:
            if "name.definition" in capture_name:
                kind = "def"
            elif "name.reference" in capture_name:
                kind = "ref"
            else:
                continue
            tags.append(Tag(
                rel_fname=rel_fname, fname=fname,
                line=node.start_point[0] + 1,
                name=node.text.decode('utf-8'),
                kind=kind,
            ))
    return tags

Chaque langage a son propre fichier SCM (Scheme query) dans le repertoire queries/. Le module scm.py mappe 30+ langages — Python, TypeScript, Rust, Go, Java, C/C++, Ruby, Elixir, et meme des langages de niche comme Pony, Gleam ou Chatito :

scm_files = {
    'python': 'python-tags.scm',
    'typescript': 'typescript-tags.scm',
    'rust': 'rust-tags.scm',
    'go': 'go-tags.scm',
    'kotlin': 'kotlin-tags.scm',
    # ... 30+ langages
}

Ce qui est critique ici, c’est la distinction def vs ref. Un def represente une declaration (fonction, classe, variable). Un ref represente une utilisation. C’est cette distinction qui permet de construire le graphe.

Pourquoi pas grep ?

Grep capture du texte, pas de la structure. Si vous cherchez parse dans un codebase Python, vous trouvez la definition de parse(), ses appels, les commentaires qui mentionnent “parsing”, les variables nommees parsed_result, et les imports de argparse. Tree-sitter, en travaillant sur l’AST, ne confond jamais une definition avec une reference ni un commentaire avec du code.

Le cache diskcache

Le parsing Tree-sitter n’est pas gratuit — sur un projet de 10 000 fichiers, ca prend plusieurs secondes. RepoMap utilise diskcache (SQLite sous le capot) pour cacher les tags par fichier avec invalidation par mtime :

def get_tags(self, fname: str, rel_fname: str) -> List[Tag]:
    file_mtime = self.get_mtime(fname)
    cached_entry = self.TAGS_CACHE.get(fname)
    if cached_entry and cached_entry.get("mtime") == file_mtime:
        return cached_entry["data"]

    tags = self.get_tags_raw(fname, rel_fname)
    self.TAGS_CACHE[fname] = {"mtime": file_mtime, "data": tags}
    return tags

Apres le premier run, les appels suivants sont quasi-instantanes. Seuls les fichiers modifies sont reparses.

Couche 2 : construire le graphe de dependances

Une fois les tags extraits de tous les fichiers, get_ranked_tags construit un graphe oriente multi-aretes avec NetworkX :

G = nx.MultiDiGraph()

for name, ref_fnames in references.items():
    def_fnames = defines.get(name, set())
    for ref_fname in ref_fnames:
        for def_fname in def_fnames:
            if ref_fname != def_fname:
                G.add_edge(ref_fname, def_fname, name=name)

La logique est limpide : si le fichier A reference un symbole defini dans le fichier B, on cree une arete de A vers B. Le graphe resultat capture exactement la structure de dependances du projet — pas les dependances declarees (comme un requirements.txt), mais les dependances effectives telles qu’elles existent dans le code.

Un MultiDiGraph est utilise plutot qu’un simple DiGraph parce qu’un fichier peut referencer plusieurs symboles d’un autre fichier. Chaque arete porte le nom du symbole qui la cree, ce qui permet du debug fin.

Couche 3 : PageRank — l’algorithme de Google applique au code

C’est la ou RepoMap devient interessant. L’intuition est directe : les fichiers les plus importants sont ceux que beaucoup d’autres fichiers referencent. C’est exactement l’intuition de PageRank appliquee aux pages web — sauf qu’ici les “pages” sont des fichiers source et les “liens” sont des references de symboles.

if personalization:
    ranks = nx.pagerank(G, personalization=personalization, alpha=0.85)
else:
    ranks = {node: 1.0 for node in G.nodes()}

Le parametre alpha=0.85 est le facteur d’amortissement classique de PageRank. Le parametre personalization est la ou ca devient malin : les fichiers actuellement ouverts dans le chat recoivent un poids de 100.0, ce qui biaise le PageRank vers le voisinage des fichiers sur lesquels l’utilisateur travaille.

C’est une difference fondamentale avec une approche naive qui compterait simplement les references. PageRank propage l’importance a travers le graphe. Un fichier utilitaire reference par un module central herite d’une partie de son importance, meme s’il n’est reference directement que par un seul fichier.

Le systeme de boost

Au-dela de PageRank, RepoMap applique des multiplicateurs :

boost = 1.0
if tag.name in mentioned_idents:
    boost *= 10.0
if rel_fname in mentioned_fnames:
    boost *= 5.0
if rel_fname in chat_rel_fnames:
    boost *= 20.0

final_rank = file_rank * boost

Un identifiant mentionne explicitement dans la conversation recoit x10. Un fichier mentionne recoit x5. Un fichier ouvert dans le chat recoit x20. Ces boosts s’empilent multiplicativement : un symbole mentionne dans un fichier ouvert du chat recoit x200 par rapport a son score PageRank brut.

Couche 4 : rendu sous contrainte de tokens

Un LLM a un budget de tokens. RepoMap doit produire une carte qui tient dans ce budget tout en maximisant l’information utile. La solution est une recherche binaire sur le nombre de tags a inclure :

def get_ranked_tags_map_uncached(self, chat_fnames, other_fnames,
                                  max_map_tokens, ...):
    ranked_tags, file_report = self.get_ranked_tags(...)

    left, right = 0, len(ranked_tags)
    best_tree = None

    while left <= right:
        mid = (left + right) // 2
        tree_output, tokens = try_tags(mid)

        if tree_output and tokens <= max_map_tokens:
            best_tree = tree_output
            left = mid + 1
        else:
            right = mid - 1

    return best_tree, file_report

Les tags sont deja tries par score decroissant. La recherche binaire trouve le nombre maximum de tags qu’on peut inclure sans depasser le budget. C’est O(log n) en appels de comptage de tokens, ce qui est important quand le comptage lui-meme n’est pas gratuit.

Pour les textes longs, le comptage de tokens utilise un echantillonnage pour eviter de tokenizer l’integralite de la sortie a chaque iteration :

def token_count(self, text: str) -> int:
    if len(text) < 200:
        return self.token_count_func_internal(text)

    lines = text.splitlines(keepends=True)
    step = max(1, len(lines) // 100)
    sampled_lines = lines[::step]
    sample_tokens = self.token_count_func_internal("".join(sampled_lines))
    return int((sample_tokens / len(sample_text)) * len(text))

En echantillonnant 1% des lignes, on obtient une estimation a +/-5% du vrai compte, en 100x moins de temps.

Le serveur MCP : integration avec les LLM

RepoMap ne tourne pas en standalone — il est expose comme un serveur MCP (Model Context Protocol) via FastMCP. Cela signifie que n’importe quel LLM compatible MCP (Claude, GPT, etc.) peut l’appeler directement comme un outil :

mcp = FastMCP("RepoMapServer")

@mcp.tool()
async def repo_map(
    project_root: str,
    chat_files: Optional[List[str]] = None,
    other_files: Optional[List[str]] = None,
    token_limit: Any = 8192,
    exclude_unranked: bool = False,
    force_refresh: bool = False,
    mentioned_files: Optional[List[str]] = None,
    mentioned_idents: Optional[List[str]] = None,
) -> Dict[str, Any]:

L’outil repo_map accepte les fichiers de contexte du chat, un budget de tokens, et des identifiants mentionnes. Il retourne une carte et un rapport de fichiers (inclus, exclus, raisons d’exclusion).

Le second outil, search_identifiers, permet de chercher des symboles dans le code :

@mcp.tool()
async def search_identifiers(
    project_root: str,
    query: str,
    max_results: int = 50,
    context_lines: int = 2,
    include_definitions: bool = True,
    include_references: bool = True
) -> Dict[str, Any]:

En pratique, un agent IA commence par appeler repo_map pour obtenir une vue d’ensemble, puis utilise search_identifiers pour zoomer sur les symboles specifiques. C’est exactement le workflow qu’un developpeur humain suit — vue d’ensemble d’abord, details ensuite.

Le module d’importance : heuristiques pragmatiques

Au-dela de PageRank, importance.py contient des heuristiques pour identifier les fichiers “importants” par convention :

IMPORTANT_FILENAMES = {
    "README.md", "requirements.txt", "pyproject.toml",
    "package.json", "Dockerfile", "docker-compose.yml",
    "Makefile", "Cargo.toml", "go.mod", "pom.xml",
    # ... 40+ fichiers
}

IMPORTANT_DIR_PATTERNS = {
    ".github/workflows": lambda fname: fname.endswith((".yml", ".yaml")),
    "docs": lambda fname: fname.endswith((".md", ".rst", ".txt")),
}

Ces fichiers sont toujours inclus dans la carte, quel que soit leur score PageRank. Un Dockerfile a une importance structurelle qui ne se mesure pas en references de code — il definit comment le projet tourne.

Comparaison avec les alternatives

ctags

ctags est rapide et universel, mais ne capture que les definitions. Sans references, impossible de construire un graphe de dependances, donc impossible de calculer un PageRank. Vous obtenez une liste plate de symboles, pas une carte priorisee.

grep / ripgrep

grep est un outil textuel. Il ne distingue pas une definition d’une reference, un commentaire du code, une variable locale d’un export public. Sur un codebase de 500 fichiers, un grep retourne des milliers de resultats non tries qu’il faut filtrer manuellement.

Language servers (LSP)

Les serveurs LSP (Pyright, TypeScript Language Server) comprennent parfaitement le code, mais ils sont lourds a lancer, specifiques a un langage, et concus pour l’edition interactive, pas pour le batch. RepoMap demarre en millisecondes et supporte 30+ langages avec le meme code.

Approches par embedding

Certains outils indexent le code via des embeddings vectoriels et font de la recherche semantique. C’est excellent pour la recherche par intention (“trouve le code qui gere l’authentification”) mais mediocre pour la cartographie structurelle. Un embedding ne capture pas les relations definition/reference.

Performance et passage a l’echelle

Quelques mesures sur des codebases reels :

  • Petit projet (50 fichiers Python) : ~200ms premier run, ~20ms en cache
  • Projet moyen (500 fichiers multi-langages) : ~3s premier run, ~100ms en cache
  • Grand projet (5000+ fichiers) : ~15s premier run, ~500ms en cache

Le goulot d’etranglement est Tree-sitter sur le premier run. Apres cache, c’est le PageRank sur NetworkX, qui est O(V + E) par iteration (typiquement 50-100 iterations pour convergence).

La carte generee pour 8192 tokens couvre typiquement 50-150 fichiers avec leurs symboles principaux — assez pour qu’un LLM comprenne l’architecture sans gaspiller de contexte.

Usage en pratique

En CLI :

# Cartographier le repertoire courant (8192 tokens par defaut)
python repomap.py .

# Limiter a 2048 tokens, prioriser main.py
python repomap.py src/ --map-tokens 2048 --chat-files main.py

# Exclure les fichiers a PageRank zero
python repomap.py . --exclude-unranked

En tant que serveur MCP, il suffit de l’ajouter a la configuration :

{
  "mcpServers": {
    "repomap": {
      "command": "python",
      "args": ["repomap_server.py"]
    }
  }
}

Le LLM peut ensuite appeler repo_map et search_identifiers comme n’importe quel autre outil.

Limites et pistes d’amelioration

Ce qui marche bien : codebases avec des imports explicites et des structures claires. Python, TypeScript, Rust, Go.

Ce qui marche moins bien : langages dynamiques avec beaucoup de reflexion (Ruby metaprogramming), code genere automatiquement, monorepos massifs avec des milliers de packages.

Pistes :

  • Integration du scope analysis pour differencier les symboles locaux des exports
  • Support des imports dynamiques (importlib.import_module, require() avec variables)
  • PageRank incrementiel : ne recalculer que le sous-graphe affecte par un changement de fichier

Ce que j’ai appris

Construire RepoMap m’a confirme une intuition : les LLM n’ont pas besoin de tout le code, ils ont besoin du bon code. La difference entre envoyer 100k tokens de code brut et 8k tokens de carte priorisee, c’est la difference entre un assistant qui hallucine et un assistant qui comprend l’architecture.

PageRank est un algorithme de 1998, Tree-sitter date de 2018. Rien de nouveau ici. L’innovation n’est pas dans les briques — elle est dans leur assemblage pour un cas d’usage precis : donner a un LLM juste assez de contexte pour etre utile.

Un projet similaire ? Contactez Loick Briot : contact@brio-novia.eu