El tiempo es un círculo plano. Cuando se lanzó la primera versión de grep en 1973, era una utilidad básica para hacer coincidir expresiones regulares en archivos de texto de un sistema de archivos. Con los años, a medida que las herramientas para desarrolladores se volvieron más avanzadas, fue siendo sustituida gradualmente por herramientas más especializadas. Primero, por índices sintácticos aproximados como ctags. Más tarde, muchos desarrolladores pasaron a IDE especializados para lenguajes de programación concretos que les permitían navegar bases de código con gran eficiencia mediante el análisis y la creación de índices sintácticos, a menudo complementados con información de tipos. Con el tiempo, esto se estandarizó en el Language Server Protocol (LSP), que llevó estos índices a todos los editores de texto, nuevos y antiguos. Luego, justo cuando LSP se estaba convirtiendo en un estándar, llegó la programación con agentes, y mira por dónde: a los agentes les encanta usar grep.

Existen otras técnicas de vanguardia para recopilar contexto para los agentes. Hemos hablado anteriormente de cuánto se puede mejorar el rendimiento del Agente usando índices semánticos para muchas tareas, pero hay consultas concretas que el modelo solo puede resolver buscando con expresiones regulares. Eso significa volver a 1973, aunque el campo haya avanzado un poco desde entonces.

La mayoría de los sistemas de agentes, incluido el nuestro, usan por defecto ripgrep cuando ofrecen una herramienta de búsqueda. Es un ejecutable independiente desarrollado por Andrew Gallant que ofrece una alternativa al clásico grep, pero con valores predeterminados más sensatos (por ejemplo, a la hora de ignorar archivos) y con un rendimiento mucho mejor. ripgrep es famoso por su velocidad porque Andrew ha dedicado mucho tiempo a pensar en la velocidad a la hora de hacer coincidir expresiones regulares.

Por muy rápido que ripgrep pueda encontrar coincidencias en el contenido de un archivo, tiene una limitación importante: necesita buscar en el contenido de todos los archivos. Esto está bien cuando se trabaja en un proyecto pequeño, pero muchos de los usuarios de Cursor, especialmente los grandes clientes de Enterprise, trabajan con monorepos enormes. Enormes hasta doler. Vemos habitualmente invocaciones de rg que tardan más de 15 segundos, y eso realmente frena el flujo de trabajo de cualquiera que esté interactuando activamente con el Agente para guiarlo mientras escribe código.

La búsqueda por expresiones regulares es ahora una parte crítica del desarrollo con agentes, y creemos que es crucial abordarla de forma explícita: igual que un IDE tradicional crea índices sintácticos localmente para operaciones como Go To Definition, nosotros estamos creando índices para la operación fundamental que realizan los agentes modernos cuando buscan texto.

#El algoritmo clásico

La idea de usar la indexación de datos textuales para acelerar las coincidencias con expresiones regulares dista mucho de ser nueva. Fue publicada por primera vez en 1993 por Zobel, Moffat y Sacks-Davis en un artículo llamado "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files". En él presentan un enfoque que usa n-gramas (segmentos de una cadena de n caracteres de longitud) para crear un índice invertido, y heurísticas para descomponer expresiones regulares en un árbol de n-gramas que puede consultarse en el índice.

Si ya has oído hablar de este concepto, probablemente no haya sido por ese artículo, sino por una entrada de blog que Russ Cox publicó en 2012, poco después del cierre de Google Code Search. Hagamos un repaso rápido de los componentes básicos de estos índices, porque se aplican a prácticamente cualquier otro enfoque de indexación que se haya desarrollado desde entonces.

#Índices invertidos

Un índice invertido es la estructura de datos fundamental de un motor de búsqueda. A partir de un conjunto de documentos que se van a indexar, se construye un índice invertido dividiendo cada documento en tokens. Esto se llama tokenización, y hay muchas formas distintas de hacerlo; para este ejemplo, usaremos el enfoque más simple posible: palabras individuales como tokens. Después, los tokens pasan a ser las claves de una estructura de datos similar a un diccionario, mientras que los valores son, para cada token, la lista de todos los documentos en los que aparece. Esta lista se conoce comúnmente como una posting list, porque cada documento se identifica de forma única mediante un valor numérico o "posting". Cuando buscas uno o más tokens, cargamos sus posting lists; si hay más de una, las intersectamos para encontrar los documentos que aparecen en todas.

Este diseño (con mucha complejidad añadida por encima) es la base de la mayoría de los motores de búsqueda disponibles hoy en día. Pero esos son motores de búsqueda para lenguaje natural, y aquí estamos intentando buscar expresiones regulares y hacerlas coincidir sobre código fuente. Esto no termina de funcionar.

Puedes intentar crear algo útil aquí pensando muy bien en la tokenización: teniendo en cuenta la sintaxis de cada lenguaje de programación, separando los identificadores del código fuente, etcétera. Hacer esto bien es muy difícil. En los primeros tiempos de GitHub, su función Code Search funcionaba así: con un tokenizador muy complejo para lenguajes de programación y un clúster enorme de ElasticSearch. Los resultados no eran buenos, y la gente tenía muy mala opinión de la función. Podías buscar identificadores (más o menos), pero no hacer coincidir expresiones regulares. Para lograr eso, necesitas una mejor forma de tokenizar.

#Descomposición en trigramas

La tokenización ingenua del código fuente no sirve para buscar coincidencias con expresiones regulares. Necesitamos dividir los documentos en unidades más básicas. El algoritmo clásico elige trigramas: un token es cada segmento superpuesto de tres caracteres de la cadena de entrada.

¿Por qué tres? Vamos a almacenar estos trigramas como claves en nuestro índice invertido. Si eligiéramos bigramas (fragmentos de 2), tendríamos muy pocas claves en nuestro índice, hasta 64k, pero las listas de postings de cada clave serían enormes, demasiado grandes para manejarlas con eficiencia. Si usáramos tetragramas (fragmentos de 4), las listas de postings serían diminutas, lo cual es muy bueno, pero tendríamos miles de millones de claves en nuestro índice invertido, y eso también es difícil de manejar.

Por eso, los trigramas son un punto intermedio bastante bueno. Esto hace que la tokenización al indexar documentos sea muy simple: extrae cada secuencia superpuesta de 3 caracteres del documento que se está indexando y úsala como token en el índice invertido.

La verdadera complejidad aparece al tokenizar una expresión regular para que pueda compararse con el índice. Las expresiones regulares tienen sintaxis, así que hay que analizarlas y usar heurísticas para determinar qué trigramas pueden extraerse de los segmentos de la expresión que realmente representan texto.

Descomponer una cadena literal en trigramas es sencillo, ya que usa el mismo algoritmo que al indexar un documento. Extrae cada trigrama superpuesto de la cadena; un documento que contenga todos esos trigramas probablemente contendrá el literal (¡aunque no necesariamente!). Las alternancias se descomponen por separado, lo que da como resultado dos ramas, de las cuales una u otra debe estar presente en un documento para que haya coincidencia. Esto se consulta en el índice invertido uniendo las listas de postings en lugar de intersectarlas. Las clases de caracteres pueden descomponerse en muchos trigramas. Las clases pequeñas como [rbc]at dan como resultado un trigrama por cada elemento de la clase. Al usar clases de caracteres más amplias, simplemente omitimos extraer esos trigramas a través de esos límites.

#Integrándolo todo

Sabemos que los trigramas son la forma correcta de tokenizar estos documentos, sabemos cómo tokenizar documentos al crear el índice y cómo tokenizar consultas al buscar. Podemos reunir todo esto en un índice de búsqueda real capaz de encontrar coincidencias con expresiones regulares muy eficientemente. Al descomponer cualquier expresión regular en un conjunto de trigramas y cargar todas las listas de postings relevantes del índice invertido, acabamos con una lista de documentos que potencialmente pueden coincidir con nuestra expresión regular. ¡Esto es importante! El conjunto final de resultados solo se obtiene cargando realmente todos los documentos potenciales y evaluando la expresión regular "a la manera tradicional". Pero contar con este subconjunto de documentos siempre es más rápido que tener que recorrer y comprobar toda la base de código, archivo por archivo.

Este diseño es, sin duda, completamente funcional. Proyectos como google/codesearch y sourcegraph/zoekt ofrecen un buen rendimiento para índices grandes usando un índice invertido de trigramas (y, como todos los motores de búsqueda, le añaden mucha más complejidad por encima). Pero aquí hay limitaciones claras: los índices no son pequeños, y la descomposición en tiempo de consulta obliga a asumir un compromiso. Si usas heurísticas simples, descompondrás las consultas en unos pocos trigramas, y eso dará como resultado muchos documentos potenciales que comprobar. Si usas heurísticas complejas, puedes acabar con decenas —quizá cientos— de trigramas, y cargar todos ellos desde el índice invertido puede llegar a ser tan lento como simplemente buscarlo todo desde cero.

Podemos hacerlo mejor.

#Arrays de sufijos: un desvío

Ya que estamos repasando la historia de la indexación de datos textuales para búsquedas con expresiones regulares, me gustaría hacer un desvío y hablar de esta implementación que Nelson Elhage desarrolló en 2015 para su servicio web livegrep. En comparación con otros grandes esfuerzos de la industria, livegrep es diminuto —solo indexa la versión más reciente del kernel de Linux—, pero precisamente por su alcance reducido, su implementación no se parece a casi nada de lo que hay por ahí, y eso la hace muy interesante y digna de comentar.

Nelson abordó el problema desde los principios más básicos: no hay ningún índice invertido que sustente este motor de búsqueda. En su lugar, todo el código fuente se indexa en un array de sufijos.

¿Cuáles son las limitaciones aquí? Un array de sufijos debe construirse a partir de una cadena de entrada. Esa es una gran limitación. Si estás intentando indexar una base de código grande (o quizá muchas bases de código diferentes), primero tendrás que concatenar todo el contenido en una sola cadena y construir el array de sufijos a partir de ella. Al buscar coincidencias dentro del array de sufijos, también necesitarás una estructura de datos auxiliar para mapear la posición de la coincidencia al archivo original que la contiene. No es una complejidad insuperable, pero hace que actualizar el índice de forma dinámica sea muy costoso. Es una solución muy difícil de escalar.

#Consultas de trigramas con máscaras probabilísticas

Volviendo a algunos diseños más tradicionales: aquí tenemos un enfoque que se desarrolló originalmente en GitHub para Project Blackbird. Era un proyecto de investigación que buscaba reemplazar la antigua función de búsqueda de código. Como comentamos antes, la búsqueda anterior se implementaba tokenizando el código fuente y no podía hacer coincidir expresiones regulares. El objetivo de esta nueva implementación era desarrollar algo que sí pudiera hacerlo.

Las primeras iteraciones intentaron usar el índice invertido clásico con trigramas como claves, pero enseguida surgieron problemas de capacidad. Hay muchísimo código en GitHub, y usar trigramas para indexarlo daba como resultado listas de postings demasiado grandes para consultarlas.

Como los trigramas no terminaban de funcionar, el siguiente paso fue encontrar un tamaño mejor para los n-gramas que se iban a indexar. Hemos visto que los bigramas son demasiado amplios, porque sus listas de postings se vuelven inmanejablemente grandes, y que los cuatrigramas son demasiado específicos, porque acabamos con demasiadas claves en nuestro índice. Los trigramas son un buen punto intermedio entre ambos, pero en la práctica, el tamaño ideal es más bien... 3,5-gramas. Pero no podemos partir un carácter en dos, ¿verdad?

De hecho, podemos hacer algo bastante parecido: este diseño propone usar trigramas como clave para el índice invertido y complementar las listas de postings con información adicional sobre el "cuarto carácter" que seguiría al trigrama en ese documento concreto. Para hacerlo, podríamos simplemente almacenar ese cuarto carácter como un byte adicional, pero eso convierte nuestro índice en uno de cuatrigramas, y ya hemos visto que esos son demasiado grandes para almacenarlos. Lo que almacenamos en su lugar es un filtro de Bloom que contiene todos los caracteres que siguen a ese trigrama específico.

Los índices resultantes son extremadamente eficientes, pero tienen una gran desventaja. Los filtros de Bloom pueden saturarse. Esa es una propiedad desafortunada de los filtros de Bloom; pueden actualizarse, pero si les añades demasiados datos, al final todos los bits del filtro quedan activados. Y, una vez que el filtro de Bloom se satura, coincide con todo, así que volvemos al rendimiento del primer índice del que hablamos.

Es un índice que minimiza el almacenamiento, pero se vuelve problemático cuando necesitas actualizarlo in situ.

#N-gramas dispersos: una selección de trigramas más inteligente

Aquí va otra idea muy ingeniosa. Puede que la hayas visto usada en ClickHouse para su operador de expresiones regulares, y también en GitHub, en la nueva funcionalidad Code Search que se lanzó hace un par de años y que sí permite buscar coincidencias con expresiones regulares. Se llama N-gramas dispersos, y es el más elegante de los términos medios.

Un índice de trigramas tradicional extrae cada secuencia consecutiva de 3 caracteres, pero es fácil ver cómo esto crea mucha redundancia. ¡Los caracteres de cada trigrama se duplican en los trigramas adyacentes! En este algoritmo, extraemos una cantidad aleatoria de n-gramas, y cada n-grama tiene una longitud aleatoria.

Por supuesto, aleatorio aquí no puede ser realmente aleatorio, porque entonces el índice no se podría consultar. Asignamos un "peso" a cada par de caracteres del documento. Ese peso puede ser cualquier cosa, siempre que sea determinista (ClickHouse usa el hash crc32 de los dos caracteres). Entonces, nuestros n-gramas dispersos son todas las subcadenas cuyos pesos en ambos extremos son estrictamente mayores que todos los pesos contenidos en su interior.

Lo importante es que esto significa que los n-gramas dispersos pueden tener cualquier longitud. No son uniformes. También significa que podemos acabar generando muchos: más que si simplemente extrajéramos trigramas. Pero, como los n-gramas se generan de forma determinista, podemos hacer algunas optimizaciones muy importantes en el momento de la consulta. Veamos cómo.

¿Podemos hacerlo mejor que esto? ¡Sí! Mucho mejor, de hecho. Hemos estado usando crc32 como función de peso en el algoritmo a modo de ejemplo. Sin embargo, aquí funcionaría cualquier función hash, siempre que sea determinista. Elijamos algo muy inteligente: una función hash que proporcione un peso alto a cada par de caracteres que en realidad sea muy raro, y un peso bajo a cada par que sea muy frecuente.

Esta función hash es fácil de calcular. Como vamos a hacer indexación de código fuente, podemos tomar un par de terabytes de código de código abierto de internet y crear una tabla de frecuencias para todos los pares de caracteres que encontremos en él. Esa tabla de frecuencias es nuestra función hash. Mira lo que sucede cuando la aplicamos a nuestro algoritmo: los pesos más altos ahora aparecen en los pares de caracteres menos frecuentes y, gracias a esto, el modo de cobertura da como resultado aún menos n-gramas que buscar y menos documentos que puedan coincidir.

Este enfoque, que minimiza la cantidad de búsquedas en las listas de postings, servirá como punto de partida perfecto para construir índices que puedan consultarse de forma eficiente en las máquinas de los usuarios.

#Todo esto, en tu máquina

Los índices para acelerar la búsqueda con expresiones regulares tienen que vivir en algún sitio. Todos los diseños que hemos visto hasta ahora se han implementado del lado del servidor, y los índices semánticos de los que hemos hablado también se gestionan y consultan en el servidor. Y, sin embargo, aquí hemos optado por una dirección distinta: crear y consultar los índices en las máquinas de los usuarios.

Hay varias razones por las que tiene sentido mantener estos índices en local. En primer lugar, los índices son solo una parte de lo necesario para hacer coincidir una expresión regular. Proporcionan un subconjunto acotado de documentos en los que las expresiones regulares podrían coincidir, pero aun así hay que escanear cada archivo individualmente. Hacer eso en el servidor implicaría o bien sincronizar todos los archivos, o bien realizar costosos viajes de ida y vuelta entre el servidor y el cliente. Hacerlo en el cliente es trivial y, además, evita muchas preocupaciones de seguridad y privacidad relacionadas con el almacenamiento de datos.

La latencia también importa mucho para esta funcionalidad. Nuestro modelo Composer tiene una de las velocidades de tokens por segundo (TPS) más altas de la industria, y estamos trabajando duro para hacerlo más inteligente y más rápido. Añadir viajes de ida y vuelta por la red a una operación tan crítica que el modelo usa constantemente (a menudo en paralelo) solo añade fricción, bloqueos y nos aleja de nuestro objetivo para la interacción con Agentes.

A diferencia de los índices semánticos, un índice para la búsqueda con expresiones regulares también tiene que estar muy actualizado, especialmente cuando se trata de que el modelo lea sus propias escrituras. No tenemos que actualizar continuamente nuestro índice semántico porque volver a calcular los embeddings de un archivo después de modificarlo no hace que el nuevo embedding se desplace significativamente en el espacio multidimensional. La búsqueda de vecinos más cercanos que realizamos seguirá guiando al Agente en la dirección correcta. Sin embargo, si el agente está buscando texto específico y no lo encuentra, a menudo acabará en una persecución inútil, desperdiciará tokens y echará por tierra el propósito de nuestra optimización del rendimiento desde el principio.

Llevar estos índices al cliente sí conlleva sus propios desafíos. Sincronizar datos en disco puede ser complejo y costoso, pero en la práctica lo hacemos de forma muy eficiente: controlamos el estado del índice basándonos en un commit del repositorio Git subyacente. Los cambios del usuario y del agente se almacenan como una capa por encima. Esto hace que actualizarlo sea muy rápido, y también que cargarlo y sincronizarlo al inicio sea muy rápido.

Para garantizar que el uso de memoria en el editor siga siendo mínimo, almacenamos nuestros índices en dos archivos separados. El primer archivo contiene todas las listas de postings del índice, una detrás de otra; las volcamos directamente a disco durante la construcción. El otro archivo contiene una tabla ordenada con los hashes de todos los n-gramas y el desplazamiento de su lista de postings correspondiente en el archivo de postings. Almacenar aquí los hashes sin guardar los n-gramas completos siempre es seguro: puede hacer que una lista de postings sea más amplia cuando dos hashes colisionan (algo extremadamente improbable en la práctica), pero no puede dar resultados incorrectos. Además, nos da un diseño muy compacto para la tabla de búsqueda. Después hacemos mmap de esta tabla, y solo de esta tabla, en el proceso del editor, y la usamos para atender consultas con una búsqueda binaria. La búsqueda devuelve un desplazamiento, y leemos directamente en ese desplazamiento del archivo de postings.

#Conclusiones

Hemos descubierto que proporcionar índices de búsqueda de texto a modelos rápidos, como nuestro propio Composer 2, marca una diferencia cualitativa en los flujos de trabajo con agentes. El impacto es mucho más pronunciado en repositorios Enterprise de mayor tamaño, porque grep es una de las pocas operaciones del Agente cuya latencia aumenta en función del tamaño y la complejidad del código sobre el que se está trabajando. Echa un vistazo a estos flujos de trabajo de ejemplo ejecutados con Composer 2: eliminar por completo el tiempo dedicado a buscar en la base de código supone un ahorro de tiempo significativo —sobre todo cuando el Agente investiga errores— y permite iterar con mucha más eficacia.

En cuanto a lo que viene después, ¡quién sabe! Hay muchos avances interesantes en torno a cómo proporcionar contexto a los Agentes, y muchos investigadores trabajando en este ámbito, incluidos los nuestros. Vamos a seguir optimizando el rendimiento de los enfoques actuales, incluidos los índices semánticos, y esperamos impulsar formas completamente nuevas de mejorar aún más el rendimiento de los Agentes, garantizando siempre que puedan operar allí donde realmente importa: en los repositorios más grandes del mundo, donde el futuro del desarrollo con agentes está cobrando verdadero impulso.