Le temps est un cercle plat. Lorsque la première version de grep est sortie en 1973, c'était un utilitaire simple permettant de faire correspondre des expressions régulières dans des fichiers texte d'un système de fichiers. Au fil des années, à mesure que les outils de développement gagnaient en sophistication, il a progressivement été supplanté par des outils plus spécialisés. D'abord, par des index syntaxiques approximatifs comme ctags. Puis, de nombreux développeurs sont passés à des IDE spécialisés pour certains langages de programmation, qui leur permettaient de naviguer très efficacement dans des bases de code en les analysant et en créant des index syntaxiques, souvent enrichis d'informations de type. Cela a fini par se standardiser avec le Language Server Protocol (LSP), qui a apporté ces index à tous les éditeurs de texte, anciens comme nouveaux. Puis, au moment même où le LSP devenait un standard, le codage agentique est arrivé, et devinez quoi : les agents adorent utiliser grep.

Il existe d'autres techniques de pointe pour fournir du contexte aux Agents. Nous avons déjà expliqué à quel point on peut améliorer les performances d'Agent en utilisant des index sémantiques pour de nombreuses tâches, mais certaines requêtes ne peuvent être résolues par le modèle qu'au moyen de recherches par expressions régulières. Cela signifie revenir à 1973, même si le domaine a quelque peu progressé depuis.

La plupart des environnements d'exécution d'Agent, y compris le nôtre, utilisent par défaut ripgrep lorsqu'ils proposent un outil de recherche. Il s'agit d'un exécutable autonome développé par Andrew Gallant, qui offre une alternative au grep classique avec des valeurs par défaut plus judicieuses (par exemple pour l'exclusion de fichiers) et de bien meilleures performances. ripgrep est réputé pour sa rapidité parce qu'Andrew a consacré beaucoup de temps à réfléchir à la vitesse de mise en correspondance des expressions régulières.

Aussi rapide que soit ripgrep pour faire des correspondances dans le contenu d'un fichier, il a une limite importante : il doit faire des correspondances dans le contenu de tous les fichiers. Ce n'est pas un problème sur un petit projet, mais beaucoup d'utilisateurs de Cursor, en particulier de grands clients Enterprise, travaillent dans d'immenses monorepos. Vraiment immenses. Nous voyons régulièrement des appels à rg qui prennent plus de 15 secondes, et cela ralentit fortement le workflow de toute personne qui interagit activement avec l'Agent pour le guider pendant qu'il écrit du code.

La correspondance d'expressions régulières est désormais un élément critique du développement agentique, et nous pensons qu'il est essentiel de l'optimiser explicitement : tout comme un IDE traditionnel crée localement des index syntaxiques pour des opérations comme Go To Definition, nous créons des index pour l'opération centrale qu'effectuent les Agents modernes lorsqu'ils recherchent du texte.

#L’algorithme classique

L’idée de l’indexation de données textuelles pour accélérer les recherches par expressions régulières est loin d’être nouvelle. Elle a été publiée pour la première fois en 1993 par Zobel, Moffat et Sacks-Davis dans un article intitulé "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files". Ils y présentent une approche fondée sur les n-grammes (segments d’une chaîne d’une largeur de n caractères) pour créer un index inversé, ainsi que des heuristiques permettant de décomposer les expressions régulières en un arbre de n-grammes que l’on peut rechercher dans l’index.

Si vous avez déjà entendu parler de ce concept, ce n’est probablement pas par cet article, mais par un billet de blog que Russ Cox a publié en 2012, peu après l’arrêt de Google Code Search. Revenons rapidement sur les éléments de base de ces index, car ils s’appliquent à pratiquement toutes les autres approches d’indexation développées depuis.

#Index inversés

Un index inversé est la structure de données fondamentale d'un moteur de recherche. À partir d'un ensemble de documents à indexer, vous construisez un index inversé en divisant chaque document en tokens. C'est ce qu'on appelle la tokenisation, et il existe de nombreuses façons de procéder — pour cet exemple, nous utiliserons l'approche la plus simple possible, à savoir des mots individuels comme tokens. Les tokens deviennent alors les clés d'une structure de données de type dictionnaire, tandis que les valeurs sont, pour chaque token, la liste de tous les documents dans lesquels il apparaît. Cette liste est généralement appelée posting list, car chaque document est identifié de manière unique par une valeur numérique, ou « posting ». Lorsque vous recherchez un ou plusieurs tokens, nous chargeons leurs posting lists ; s'il y en a plusieurs, nous calculons leur intersection afin de trouver les documents qui apparaissent dans toutes.

Cette conception (avec beaucoup de complexité ajoutée par-dessus) est à la base de la plupart des moteurs de recherche disponibles aujourd'hui. Mais il s'agit de moteurs de recherche pour le langage naturel, alors que nous essayons de rechercher des expressions régulières et de les faire correspondre à du code source. Cela ne fonctionne pas vraiment.

Vous pouvez essayer de créer quelque chose d'utile ici en réfléchissant très sérieusement à la tokenisation — en tenant compte de la syntaxe de chaque langage de programmation, en découpant les identifiants dans le code source, etc. C'est très difficile à réussir. Au début de GitHub, leur fonctionnalité Code Search fonctionnait ainsi : avec un tokenizer très complexe pour les langages de programmation et un très gros cluster ElasticSearch. Les résultats n'étaient pas bons, et les utilisateurs avaient une très mauvaise opinion de la fonctionnalité. Vous pouviez rechercher des identifiants (plus ou moins), mais pas faire correspondre des expressions régulières. Pour y parvenir, il faut une meilleure façon de tokeniser.

#Décomposition en trigrammes

Une tokenisation naïve du code source n'est pas utile pour faire correspondre des expressions régulières. Nous devons découper les documents en unités plus fondamentales. L'algorithme classique choisit les trigrammes : un token correspond à chaque segment chevauchant de trois caractères dans la chaîne d'entrée.

Pourquoi trois ? Nous allons stocker ces trigrammes comme clés dans notre index inversé. Si nous choisissions des bigrammes (segments de 2), nous aurions très peu de clés dans notre index, au plus 64k, mais les listes de postings associées à chaque clé seraient énormes — trop volumineuses pour être exploitées efficacement. Si nous choisissions des quadgrammes (segments de 4), les listes de postings seraient minuscules, ce qui est une très bonne chose, mais nous aurions des milliards de clés dans notre index inversé, et cela aussi serait difficile à exploiter.

Les trigrammes constituent donc un assez bon compromis. Cela rend la tokenisation lors de l'indexation des documents très simple : extrayez chaque séquence chevauchante de 3 caractères du document en cours d'indexation et utilisez-la comme token dans l'index inversé.

La véritable complexité apparaît lorsqu'on tokenise une expression régulière afin de pouvoir la faire correspondre à l'index. Les expressions régulières ont une syntaxe ; il faut donc les analyser et utiliser des heuristiques pour déterminer quels trigrammes peuvent être extraits des segments de l'expression qui représentent réellement du texte.

Décomposer une chaîne littérale en trigrammes est simple, car c'est le même algorithme que lorsque vous indexez un document. Extrayez chaque trigramme chevauchant contenu dans la chaîne ; un document qui contient tous ces trigrammes contiendra probablement la chaîne littérale (mais pas nécessairement !). Les alternances sont décomposées séparément, ce qui produit deux branches dont l'une ou l'autre doit être présente dans un document pour qu'il y ait correspondance. Nous interrogeons alors l'index inversé en fusionnant les listes de postings au lieu de les intersecter. Les classes de caractères peuvent être décomposées en de nombreux trigrammes. Les petites classes comme [rbc]at produisent un trigramme pour chaque élément de la classe. Lorsqu'on utilise des classes de caractères plus larges, nous ignorons simplement l'extraction de ces trigrammes à travers ces frontières.

#Tout assembler

Nous savons que les trigrammes sont la bonne façon de tokeniser ces documents, nous savons comment tokeniser les documents lors de la création de l’index, et comment tokeniser les requêtes au moment de la recherche. Nous pouvons assembler tout cela dans un véritable index de recherche capable de faire correspondre des expressions régulières très efficacement. En décomposant n’importe quelle expression régulière en un ensemble de trigrammes et en chargeant toutes les listes de postings pertinentes depuis l’index inversé, nous obtenons une liste de documents susceptibles de correspondre à notre expression régulière. C’est important ! L’ensemble de résultats final ne sera obtenu qu’en chargeant réellement tous les documents potentiels et en appliquant l’expression régulière « à l’ancienne ». Mais disposer de ce sous-ensemble de documents est toujours plus rapide que de devoir parcourir et tester toute la base de code, fichier par fichier.

Cette approche est, à tous points de vue, pleinement fonctionnelle. Des projets comme google/codesearch et sourcegraph/zoekt offrent de bonnes performances sur de grands index grâce à un index inversé de trigrammes (et, comme tous les moteurs de recherche, ils y ajoutent beaucoup d’autres couches de complexité). Mais cette approche présente aussi des limites évidentes : la taille des index n’est pas négligeable, et la décomposition au moment de la requête impose un compromis. Si vous utilisez des heuristiques simples, vous décomposerez les requêtes en quelques trigrammes, ce qui produira un grand nombre de documents potentiels à vérifier. Si vous utilisez des heuristiques complexes, vous risquez de vous retrouver avec des dizaines — voire des centaines — de trigrammes, et charger tout cela depuis l’index inversé peut devenir aussi lent que de tout rechercher depuis zéro.

Nous pouvons faire mieux.

#Tableaux de suffixes : un détour

Puisque nous retraçons l’histoire de l’indexation des données textuelles pour les recherches par expressions régulières, j’aimerais faire un détour pour parler de cette implémentation que Nelson Elhage a développée en 2015 pour son service web livegrep. Comparé aux autres grands projets du secteur, livegrep est minuscule — il n’indexe que la version la plus récente du noyau Linux — mais, justement grâce à ce périmètre réduit, son implémentation ne ressemble à rien d’autre, ce qui la rend particulièrement intéressante et digne qu’on s’y attarde.

Nelson a abordé le problème à partir des principes fondamentaux : aucun index inversé ne sous-tend ce moteur de recherche. À la place, tout le code source est indexé dans un tableau de suffixes.

Quelles sont les limites de cette approche ? Un tableau de suffixes doit être construit à partir d’une chaîne en entrée. C’est une contrainte importante. Si vous essayez d’indexer une grande base de code (ou peut-être plusieurs bases de code différentes), vous devrez d’abord concaténer tout le contenu en une seule chaîne, puis construire le tableau de suffixes à partir de celle-ci. Lors de la recherche de correspondances dans le tableau de suffixes, vous aurez aussi besoin d’une structure de données auxiliaire pour associer la position trouvée au fichier d’origine qui la contient. Cette complexité n’est pas insurmontable, mais elle rend les mises à jour dynamiques de l’index très coûteuses. C’est une solution très difficile à faire passer à l’échelle.

#Requêtes trigrammes avec masques probabilistes

Revenons à des conceptions plus traditionnelles : voici une approche développée à l’origine chez GitHub pour Project Blackbird. Il s’agissait d’un projet de recherche visant à remplacer l’ancienne fonctionnalité Code Search. Comme nous l’avons vu plus tôt, l’ancienne recherche reposait sur la tokenisation du code source et ne pouvait pas prendre en charge les expressions régulières. L’objectif de cette nouvelle implémentation était donc de développer quelque chose qui le puisse.

Les premières itérations ont tenté d’utiliser l’index inversé classique avec des trigrammes comme clés, mais elles se sont rapidement heurtées à des problèmes de capacité. Il y a énormément de code sur GitHub, et l’utilisation de trigrammes pour l’indexer produisait des listes de postings tout simplement trop volumineuses pour la recherche.

Comme les trigrammes ne donnaient pas tout à fait satisfaction, l’étape suivante a consisté à trouver une meilleure taille pour les n-grammes à indexer. Nous avons vu que les bigrammes sont trop larges, car leurs listes de postings deviennent ingérables, et que les quadgrammes sont trop spécifiques, car nous nous retrouvons avec trop de clés dans notre index. Les trigrammes constituent un bon compromis entre les deux, mais en pratique, la taille idéale se rapproche plutôt de... 3,5-grammes. Pourtant, on ne peut pas couper un caractère en deux, n’est-ce pas ?

En réalité, on peut faire quelque chose qui s’en approche beaucoup : cette conception propose d’utiliser des trigrammes comme clé de l’index inversé, et d’enrichir les listes de postings avec des informations supplémentaires sur le « quatrième caractère » qui suivrait le trigramme dans ce document précis. Pour cela, nous pourrions simplement stocker ce quatrième caractère dans un octet supplémentaire, mais cela transformerait notre index en index de quadgrammes, et nous avons vu que ceux-ci sont tout simplement trop volumineux à stocker. À la place, nous stockons un filtre de Bloom qui contient tous les caractères suivant ce trigramme précis.

Les index obtenus sont extrêmement efficaces, mais ils présentent un défaut majeur. Les filtres de Bloom peuvent devenir saturés. C’est une propriété regrettable des filtres de Bloom : ils peuvent être mis à jour, mais si vous y ajoutez trop de données, tous les bits du filtre finissent par être activés. Et une fois le filtre de Bloom saturé, il correspond à tout, ce qui nous ramène aux performances du tout premier index dont nous avons parlé.

C’est un index qui minimise l’espace de stockage, mais il devient pénible quand vous devez le mettre à jour sur place.

#Sparse N-grams : une sélection plus intelligente des trigrammes

Voici une autre idée très ingénieuse. Vous l'avez peut-être déjà vue à l'œuvre dans ClickHouse pour son opérateur d'expressions régulières, ainsi que chez GitHub, dans la nouvelle fonctionnalité Code Search lancée il y a quelques années, qui permet elle aussi de faire des correspondances par expressions régulières. On appelle cela les Sparse N-grams, et c'est un excellent compromis.

Un index trigramme traditionnel extrait toutes les séquences consécutives de 3 caractères, mais on voit bien que cela crée beaucoup de redondance. Les caractères de chaque trigramme sont dupliqués dans les trigrammes adjacents ! Dans cet algorithme, nous extrayons un nombre aléatoire de n-grammes, chacun ayant une longueur aléatoire.

Bien sûr, ici, aléatoire ne peut pas vouloir dire réellement aléatoire, sinon l'index ne pourrait pas être interrogé. Nous attribuons un « poids » à chaque paire de caractères du document. Ce poids peut être n'importe quoi, à condition d'être déterministe (ClickHouse utilise le hash crc32 des deux caractères). Ensuite, nos n-grammes épars sont toutes les sous-chaînes dont les poids aux deux extrémités sont strictement supérieurs à tous les poids contenus à l'intérieur.

Point essentiel : cela signifie que les n-grammes épars peuvent avoir n'importe quelle longueur. Ils ne sont pas uniformes. Cela signifie aussi que nous pouvons finir par en générer beaucoup — davantage que si nous extrayions simplement des trigrammes. Mais comme les n-grammes sont générés de façon déterministe, nous pouvons faire des optimisations très importantes au moment de la requête. Voyons comment.

Peut-on faire mieux que ça ? Oui ! Bien mieux, en fait. Nous avons pris crc32 comme fonction de poids dans l’algorithme à titre d’exemple. Cependant, n’importe quelle fonction de hachage ferait l’affaire ici, à condition qu’elle soit déterministe. Choisissons quelque chose de très intelligent : une fonction de hachage qui attribue un poids élevé à chaque paire de caractères en réalité très rare, et un poids faible à chaque paire très fréquente.

Cette fonction de hachage est facile à calculer. Puisque nous allons faire l’indexation de code source, nous pouvons récupérer quelques téraoctets de code open source sur Internet et créer une table de fréquence pour toutes les paires de caractères que nous y trouvons. Cette table de fréquence est notre fonction de hachage. Voyez ce qui se passe quand nous l’appliquons à notre algorithme : les poids les plus élevés apparaissent désormais pour les paires de caractères les moins fréquentes et, grâce à cela, le mode de couverture donne encore moins de n-grammes à rechercher, et moins de documents susceptibles de correspondre.

Cette approche, qui minimise le nombre de consultations des listes de postings, constitue le point de départ idéal pour construire des index interrogeables efficacement sur les machines des utilisateurs.

#Tout cela, sur votre machine

Les index destinés à accélérer la recherche par expression régulière doivent bien être stockés quelque part. Toutes les architectures que nous avons vues jusqu’ici ont été déployées côté serveur, et les index sémantiques dont nous avons parlé sont eux aussi gérés et interrogés sur le serveur. Pourtant, nous faisons ici un autre choix : nous créons et interrogeons les index directement sur les machines des utilisateurs.

Il y a plusieurs raisons pour lesquelles il est judicieux de conserver ces index en local. D’abord, les index ne sont qu’une partie de ce qui est nécessaire pour faire correspondre une expression régulière. Ils fournissent un sous-ensemble restreint de documents dans lesquels les expressions régulières pourraient correspondre, mais il faut malgré tout analyser chaque fichier individuellement. Faire cela sur le serveur impliquerait soit de synchroniser tous les fichiers, soit d’effectuer des allers-retours coûteux avec le client. Le faire côté client est trivial, et permet aussi d’éviter de nombreuses préoccupations de sécurité et de confidentialité liées au stockage des données.

La latence compte aussi énormément pour cette fonctionnalité. Notre modèle Composer affiche l’un des débits en tokens par seconde (TPS) les plus rapides du secteur, et nous travaillons dur pour le rendre à la fois plus intelligent et plus rapide. Ajouter des allers-retours réseau à une opération aussi critique, que le modèle utilise constamment (souvent en parallèle), ne fait qu’ajouter des frictions, des temps d’attente, et nous éloigne de l’objectif que nous visons pour l’interaction avec les Agents.

Contrairement aux index sémantiques, un index de recherche par expression régulière doit aussi être très à jour, en particulier lorsque le modèle relit ses propres écritures. Nous n’avons pas besoin de mettre à jour continuellement notre index sémantique, car recalculer les embeddings d’un fichier après sa modification ne fait pas en sorte que le nouvel embedding se déplace significativement dans l’espace multidimensionnel. La recherche des plus proches voisins que nous effectuons continuera d’orienter l’Agent dans la bonne direction. En revanche, si l’agent recherche un texte précis et ne le trouve pas, il se lancera souvent dans une fausse piste, gaspillera des tokens et annulera d’emblée l’intérêt de notre optimisation des performances.

Déplacer ces index côté client apporte aussi son lot de défis. La synchronisation des données sur disque peut être complexe et coûteuse, mais en pratique, nous la rendons très efficace : nous contrôlons l’état de l’index en le basant sur un commit du dépôt Git sous-jacent. Les modifications de l’utilisateur et de l’agent sont stockées comme une couche par-dessus. Cela le rend très rapide à mettre à jour, mais aussi très rapide à charger et à synchroniser au démarrage.

Pour garantir que l’utilisation de la mémoire dans l’éditeur reste minimale, nous stockons nos index dans deux fichiers distincts. Le premier fichier contient toutes les listes de postings de l’index, l’une après l’autre — nous l’écrivons directement sur le disque pendant la construction. L’autre fichier contient une table triée avec les hachages de tous les n-grammes et l’offset de leur liste de postings correspondante dans le fichier de postings. Stocker ici les hachages sans stocker les n-grammes complets est toujours sans risque : cela peut élargir une liste de postings lorsque deux hachages entrent en collision (ce qui est extrêmement improbable en pratique), mais cela ne peut pas produire de résultats incorrects. Cela nous donne aussi une disposition très compacte pour la table de consultation. Nous mmap ensuite cette table, et uniquement cette table, dans le processus de l’éditeur, et nous l’utilisons pour traiter les requêtes avec une recherche binaire. La recherche renvoie un offset, et nous lisons directement à cet offset dans le fichier de postings.

#Conclusions

Nous avons constaté que le fait de fournir des index de recherche textuelle à des modèles rapides, comme notre propre Composer 2, crée une différence qualitative pour les workflows agentiques. L’impact est bien plus marqué dans les grands dépôts Enterprise, car grep est l’une des rares opérations de l’Agent dont la latence évolue avec la taille et la complexité du code en cours de traitement. Regardez ces exemples de workflows exécutés avec Composer 2 : supprimer entièrement le temps passé à rechercher dans la base de code permet de réaliser des gains de temps significatifs — en particulier lorsque l’Agent enquête sur des bugs — et permet une itération bien plus efficace.

Quant à la suite, qui sait ! Les avancées autour de la fourniture de contexte aux Agents sont nombreuses et passionnantes, et beaucoup de chercheurs travaillent dans ce domaine — y compris chez nous. Nous allons continuer à optimiser les performances des approches actuelles, notamment les index sémantiques, et nous espérons faire émerger des méthodes entièrement nouvelles pour améliorer encore davantage les performances des Agents, tout en veillant à ce qu’ils restent utilisables là où cela compte vraiment : dans les plus grands dépôts du monde, là où l’avenir du développement agentique prend véritablement son essor.