Index de Trigrammes Cursor pour une Recherche Regex Rapide

Les index trigramme locaux de Cursor accélèrent la recherche regex dans les grands dépôts

Cursor a implémenté des index locaux pour la recherche regex directement dans l'IDE. Cela résout le problème du balayage lent dans les grands monorepos, où ripgrep classique prend plus de 15 secondes par appel, et l'agent AI génère des dizaines de telles requêtes.

La technologie repose sur l'index inversé trigramme de 1993. Le texte est décomposé en toutes les séquences de 3 caractères (trigrammes), qui servent de clés dans un dictionnaire. Chaque clé correspond à une liste de fichiers contenant cette séquence. La requête regex est décomposée en un ensemble de trigrammes, les listes de postings sont intersectées pour sélectionner les candidats. Puis grep est appliqué uniquement à une dizaine de fichiers au lieu de milliers.

N-grammes épars pour une délimitation précise

Au-dessus de l'index de base, des n-grammes épars sont ajoutés. La longueur de chaque n-gramme est calculée de manière déterministe : en utilisant des poids de paires de caractères basés sur crc32 ou une table de fréquences construite à partir de téraoctets de code open source.

Lors de l'indexation, tous les n-grammes possibles sont générés ; lors de la recherche, un ensemble couvrant minimal. Cela réduit le nombre de recherches et améliore la précision du filtrage.

// Example dekompozitsii regex in n-grams
regex: \w+@\w+\.com
n-grams: ['@', 'w+', '.c', 'com', ...]  // sparse pokryodkrycie
candidates = intersect(postings(ngrams))

Stockage local et liaison au commit

L'index est stocké localement sur la machine de l'utilisateur dans deux fichiers mmap. Raisons :

• L'agent AI lit quand même les fichiers localement pour la vérification finale.
• Les allers-retours réseau anéantissent le gain de vitesse.

L'index est lié à un commit git spécifique. Les modifications non validées sont superposées par-dessus sans reconstruction.

• Avantages de mmap : surcharge nulle au chargement, navigation rapide dans les listes de postings.
• Mise à jour : déclenchée lors d'un git pull/push ou reconstruction manuelle.
• Taille : proportionnelle au codebase ; pour 10M LoC — ~500MB.

Comparaison des performances

| Approche | Temps par requête (10k fichiers) | Candidats pour grep |

|----------|----------------------------|---------------------|

| ripgrep | 15–20 sec | 10k |

| Cursor index | 50–200 ms | 10–50 |

Dans des scénarios réels avec plus de 100 requêtes de l'agent, l'accélération globale atteint 100x.

Les trigrammes assurent l'exhaustivité (rappel=1 pour les sous-chaînes exactes), tandis que les n-grammes épars ajoutent de la précision sans faux positifs.

Points clés

• L'index trigramme réduit les candidats de milliers à des dizaines de fichiers.
• Les n-grammes épars minimisent les recherches via un ensemble couvrant minimal.
• Le stockage mmap local élimine les délais réseau.
• Liaison au commit git avec superposition des modifications non validées.
• Accélération 100x pour la recherche regex des agents AI dans les grands monorepos.

— Editorial Team