O tempo é um círculo plano. Quando a primeira versão do grep foi lançada em 1973, ela era um utilitário básico para fazer correspondência de expressões regulares em arquivos de texto de um sistema de arquivos. Ao longo dos anos, à medida que as ferramentas para desenvolvedor se tornaram mais avançadas, ele foi gradualmente substituído por ferramentas mais especializadas. Primeiro, por índices sintáticos aproximados como ctags. Depois, muitos desenvolvedores migraram para IDEs especializadas em linguagens de programação específicas, que permitiam navegar por bases de código com muita eficiência ao analisar e construir índices sintáticos, muitas vezes enriquecidos com informações de tipos. Eventualmente, isso foi padronizado no Language Server Protocol (LSP), que levou esses índices a todos os editores de texto, novos e antigos. Então, justamente quando o LSP estava se consolidando como padrão, a programação com agentes chegou e, veja só: os agentes simplesmente adoram usar grep.

Existem outras técnicas de ponta para reunir contexto para Agentes. Já falamos antes sobre o quanto é possível melhorar o desempenho do Agente usando índices semânticos em muitas tarefas, mas há consultas específicas que o modelo só consegue resolver pesquisando com expressões regulares. Isso significa voltar a 1973, embora a área tenha avançado um pouco desde então.

A maioria das infraestruturas de Agente, incluindo a nossa, usa por padrão o ripgrep ao oferecer uma ferramenta de busca. É um executável independente desenvolvido por Andrew Gallant que oferece uma alternativa ao grep clássico, mas com padrões mais sensatos (por exemplo, quando se trata de ignorar arquivos) e com desempenho muito melhor. O ripgrep é notoriamente rápido porque Andrew dedicou muito tempo a pensar em velocidade na hora de fazer correspondência com expressões regulares.

Por mais rápido que o ripgrep consiga fazer correspondência no conteúdo de um arquivo, ele tem uma limitação séria: precisa fazer correspondência no conteúdo de todos os arquivos. Isso funciona bem em projetos pequenos, mas muitos usuários do Cursor, especialmente grandes clientes Enterprise, trabalham em monorepos enormes. Dolorosamente enormes. Vemos rotineiramente invocações de rg que levam mais de 15 segundos, e isso realmente trava o fluxo de trabalho de quem está interagindo ativamente com o Agente para orientá-lo enquanto ele escreve código.

Fazer correspondência com expressões regulares agora é uma parte crítica do desenvolvimento com agentes, e acreditamos que é crucial tratar isso de forma explícita: assim como uma IDE tradicional cria índices sintáticos localmente para operações como Go To Definition, estamos criando índices para a operação central que os Agentes modernos executam ao procurar texto.

#O algoritmo clássico

A ideia de indexação de dados textuais para acelerar correspondências com expressões regulares está longe de ser nova. Ela foi publicada pela primeira vez em 1993 por Zobel, Moffat e Sacks-Davis em um artigo chamado "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files". Eles apresentam uma abordagem que usa n-gramas (segmentos de uma string com largura de n caracteres) para criar um índice invertido, além de heurísticas para decompor expressões regulares em uma árvore de n-gramas que pode ser consultada no índice.

Se você já ouviu falar desse conceito antes, provavelmente não foi por esse artigo, mas por um post de blog que Russ Cox publicou em 2012, pouco depois do encerramento do Google Code Search. Vamos fazer uma rápida revisão dos elementos básicos desses índices, porque eles se aplicam basicamente a todas as outras abordagens de indexação desenvolvidas desde então.

#Índices invertidos

Um índice invertido é a estrutura de dados fundamental por trás de um mecanismo de busca. A partir de um conjunto de documentos a serem indexados, você constrói um índice invertido dividindo cada documento em tokens. Isso se chama tokenização, e há muitas formas diferentes de fazer isso — para este exemplo, vamos usar a abordagem mais simples possível: palavras individuais como tokens. Os tokens então se tornam as chaves de uma estrutura de dados semelhante a um dicionário, enquanto os valores são, para cada token, a lista de todos os documentos em que ele aparece. Essa lista é comumente conhecida como posting list, porque cada documento é identificado de forma única por um valor numérico, ou "posting". Quando você pesquisa um ou mais tokens, carregamos suas posting lists; se houver mais de uma posting list, fazemos a interseção entre elas para encontrar os documentos que aparecem em todas elas.

Esse projeto (com muita complexidade acrescentada por cima) é a base da maioria dos mecanismos de busca disponíveis hoje. Mas esses são mecanismos de busca para linguagem natural, e nós estamos tentando pesquisar expressões regulares em código-fonte. Isso não funciona muito bem.

Você pode tentar construir algo útil aqui pensando bastante na tokenização — levando em conta a sintaxe de cada linguagem de programação, separando os identificadores no código-fonte e assim por diante. É muito difícil fazer isso direito. Nos primeiros dias do GitHub, o recurso Code Search funcionava assim: com um tokenizador muito complexo para linguagens de programação e um cluster de ElasticSearch muito grande. Os resultados não eram bons, e as pessoas tinham uma opinião muito ruim sobre o recurso. Era possível pesquisar identificadores (mais ou menos), mas não encontrar correspondências para expressões regulares. Para fazer isso, você precisa de uma forma melhor de tokenizar.

#Decomposição em trigramas

A tokenização ingênua de código-fonte não é útil para fazer correspondência com expressões regulares. Precisamos dividir os documentos em partes mais fundamentais. O algoritmo clássico escolhe trigramas: um token é cada segmento sobreposto de três caracteres na string de entrada.

Por que três? Vamos armazenar esses trigramas como chaves no nosso índice invertido. Se escolhêssemos bigramas (blocos de 2), teríamos pouquíssimas chaves no nosso índice, até 64 mil, mas as listas de postings de cada chave seriam enormes — grandes demais para trabalhar com eficiência. Se usássemos quadgramas (blocos de 4), as listas de postings seriam minúsculas, o que é muito bom, mas teríamos bilhões de chaves no nosso índice invertido, e isso também seria difícil de manejar.

Os trigramas são, portanto, um meio-termo muito bom. Isso torna a tokenização durante a indexação de documentos muito simples: extraia cada sequência sobreposta de 3 caracteres do documento que está sendo indexado e use isso como seus tokens no índice invertido.

A verdadeira complexidade surge ao tokenizar uma expressão regular para que ela possa ser comparada com o índice. Expressões regulares têm sintaxe, então você precisa analisá-las e usar heurísticas para descobrir quais trigramas podem ser extraídos dos segmentos da expressão que de fato representam texto.

Decompor uma string literal em trigramas é simples, pois é o mesmo algoritmo usado quando você indexa um documento. Extraia cada trigrama sobreposto contido na string; um documento que contenha todos esses trigramas provavelmente conterá o literal (mas não necessariamente!). Alternâncias são decompostas separadamente, resultando em dois ramos, dos quais um ou outro deve estar contido em um documento para haver correspondência. Consultamos isso no índice invertido unindo as listas de postings em vez de intersectá-las. Classes de caracteres podem ser decompostas em muitos trigramas. Classes pequenas como [rbc]at resultam em um trigrama para cada elemento da classe. Ao usar classes de caracteres mais amplas, simplesmente deixamos de extrair esses trigramas através dessas fronteiras.

#Juntando tudo

Sabemos que trigramas são a forma correta de tokenizar esses documentos, sabemos como tokenizar documentos ao construir o índice e como tokenizar consultas ao pesquisar. Podemos juntar tudo isso em um índice de busca de verdade, capaz de corresponder a expressões regulares com muita eficiência. Ao decompor qualquer expressão regular em um conjunto de trigramas e carregar todas as listas de postings relevantes do índice invertido, chegamos a uma lista de documentos que potencialmente podem corresponder à nossa expressão regular. Isso é importante! O conjunto final de resultados só será obtido carregando de fato todos os documentos potenciais e aplicando a expressão regular "da maneira tradicional". Mas ter esse subconjunto de documentos é sempre mais rápido do que ter que varrer e verificar toda a base de código, arquivo por arquivo.

Esse design é, sem dúvida, totalmente funcional. Projetos como google/codesearch e sourcegraph/zoekt oferecem bom desempenho para índices grandes usando um índice invertido de trigramas (e, como todos os mecanismos de busca, adicionam muito mais complexidade por cima disso). Mas há limitações claras aqui: os tamanhos dos índices não são pequenos, e a decomposição no momento da consulta exige um trade-off. Se você usar heurísticas simples, vai decompor as consultas em poucos trigramas, e isso resultará em muitos documentos potenciais para verificar. Se usar heurísticas complexas, pode acabar com dezenas — talvez centenas — de trigramas, e carregar todos eles do índice invertido pode ficar tão lento quanto simplesmente pesquisar tudo do zero.

Podemos fazer melhor do que isso.

#Suffix Arrays: um desvio

Como estamos cobrindo a história da indexação de dados textuais para buscas com expressões regulares, gostaria de fazer um desvio e discutir esta implementação que Nelson Elhage desenvolveu em 2015 para seu serviço web livegrep. Em comparação com outros grandes esforços da indústria, o livegrep é minúsculo — indexa apenas a versão mais recente do Linux Kernel — mas, justamente por causa de seu escopo reduzido, sua implementação é bem diferente de qualquer outra por aí, o que a torna muito interessante e digna de discussão.

Nelson atacou o problema a partir de princípios fundamentais: não há nenhum índice invertido por trás desse mecanismo de busca. Em vez disso, todo o código-fonte é indexado em um suffix array.

Quais são as limitações aqui? Um suffix array precisa ser construído a partir de uma string de entrada. Essa é uma grande limitação. Se você estiver tentando indexar uma base de código grande (ou talvez várias bases de código diferentes), primeiro precisará concatenar todo o conteúdo em uma única string e construir o suffix array a partir dela. Ao fazer correspondências dentro do suffix array, você também precisará de uma estrutura de dados auxiliar para mapear a posição da correspondência ao arquivo original que a contém. Não é uma complexidade intransponível, mas torna a atualização dinâmica do índice muito cara. Esta é uma solução muito difícil de escalar.

#Consultas de trigramas com máscaras probabilísticas

Voltando a algumas abordagens mais tradicionais: aqui está uma solução que foi originalmente desenvolvida no GitHub para o Project Blackbird. Esse foi um projeto de pesquisa que buscava substituir o antigo recurso Code Search. Como discutimos antes, a busca antiga era implementada por meio da tokenização do código-fonte e não conseguia dar suporte a expressões regulares. O objetivo dessa nova implementação era desenvolver algo que conseguisse.

As primeiras iterações tentaram usar o índice invertido clássico com trigramas como chaves, mas rapidamente esbarraram em problemas de capacidade. Há muito código no GitHub, e usar trigramas para indexá-lo resultava em listas de ocorrências grandes demais para pesquisar.

Como os trigramas não estavam funcionando tão bem, o passo seguinte foi encontrar um tamanho melhor para os n-gramas que seriam indexados. Vimos que os bigramas são amplos demais, porque suas listas de ocorrências ficam grandes demais para gerenciar, e que os quadgramas são específicos demais, porque acabamos com chaves demais em nosso índice. Os trigramas são um meio-termo entre os dois, mas, na prática, o tamanho ideal é mais algo como... 3,5-gramas. Mas não podemos dividir um caractere em dois, podemos?

Na verdade, podemos fazer algo bem próximo disso: esta abordagem propõe usar trigramas como chave do índice invertido e complementar as listas de ocorrências com informações extras sobre o "quarto caractere" que viria depois do trigrama naquele documento específico. Para fazer isso, poderíamos simplesmente armazenar esse quarto caractere como um byte extra, mas isso transforma nosso índice em um índice de quadgramas, e já vimos que eles são grandes demais para armazenar. Em vez disso, o que armazenamos é um filtro de Bloom que contém todos os caracteres que seguem aquele trigrama específico.

Os índices resultantes são extremamente eficientes, mas têm uma grande limitação. Filtros de Bloom podem ficar saturados. Essa é uma propriedade infeliz dos filtros de Bloom; eles podem ser atualizados, mas, se você adicionar dados demais a eles, eventualmente todos os bits do filtro serão ativados. E, uma vez que o filtro de Bloom fica saturado, ele corresponde a tudo, então voltamos ao desempenho do primeiro índice sobre o qual falamos.

Este é um índice que minimiza o armazenamento, mas se torna problemático quando você precisa atualizá-lo in-place.

#Sparse N-grams: Seleção mais inteligente de trigramas

Aqui vai outra ideia muito inteligente. Você talvez já a tenha visto sendo usada no ClickHouse para o operador de expressão regular deles, e também no GitHub, no novo recurso Code Search, lançado há alguns anos, que permite corresponder expressões regulares. Ela se chama Sparse N-grams e é o melhor dos meios-termos.

Um índice tradicional de trigramas extrai toda sequência consecutiva de 3 caracteres, mas dá para ver como isso cria muita redundância. Os caracteres de cada trigrama se repetem nos trigramas adjacentes! Neste algoritmo, extraímos uma quantidade aleatória de n-gramas, e cada n-grama tem um comprimento aleatório.

Claro que aleatório, aqui, não pode ser realmente aleatório, porque nesse caso não seria possível consultar o índice. Estamos atribuindo um "peso" a cada par de caracteres no documento. Esse peso pode ser qualquer coisa, desde que seja determinístico (o ClickHouse usa o hash crc32 dos dois caracteres). Então, nossos sparse n-grams são todas as substrings cujos pesos nas duas extremidades são estritamente maiores do que todos os pesos contidos no interior.

O ponto crucial é que isso significa que os sparse n-grams podem ter qualquer comprimento. Eles não são uniformes. Isso também significa que podemos acabar gerando muitos deles — mais do que se estivéssemos apenas extraindo trigramas. Mas, como os n-gramas são gerados de forma determinística, podemos fazer algumas otimizações muito importantes no momento da consulta. Vamos ver como.

Podemos fazer melhor do que isso? Sim! Muito melhor, na verdade. Temos usado crc32 como nossa função de peso no algoritmo, como exemplo. No entanto, qualquer função hash funcionaria aqui, desde que seja determinística. Vamos escolher algo muito inteligente: uma função hash que atribui um peso alto a cada par de caracteres que é de fato muito raro e um peso baixo a cada par que é muito frequente.

Essa função hash é fácil de calcular. Como vamos fazer a indexação de código-fonte, podemos pegar alguns terabytes de código open source da internet e construir uma tabela de frequência para todos os pares de caracteres que encontrarmos nele. Essa tabela de frequência é a nossa função hash. Veja o que acontece quando a aplicamos ao nosso algoritmo: os pesos mais altos agora aparecem nos pares de caracteres menos frequentes e, por causa disso, o modo de cobertura resulta em ainda menos n-gramas para buscar e menos documentos que podem corresponder.

Essa abordagem, que minimiza a quantidade de buscas em postings, será o ponto de partida perfeito para construir índices que possam ser consultados com eficiência nas máquinas dos usuários.

#Tudo isso na sua máquina

Índices para acelerar a busca por expressões regulares precisam ficar em algum lugar. Todos os designs que vimos até agora foram implantados no lado do servidor, e os índices semânticos de que falamos também são gerenciados e consultados no servidor. Ainda assim, estamos optando por seguir em uma direção diferente aqui: estamos construindo e consultando os índices nas máquinas dos usuários.

Há vários motivos pelos quais manter esses índices localmente faz sentido. Primeiro, os índices são apenas uma parte do que é necessário para fazer a correspondência com uma expressão regular. Eles fornecem um subconjunto mais restrito de documentos em que as expressões regulares podem ter correspondência, mas ainda é preciso analisar cada arquivo individualmente. Fazer isso no servidor significaria sincronizar todos os arquivos ou realizar round trips caros entre servidor e cliente. Fazer isso no cliente é trivial e também evita muitas preocupações com segurança e privacidade relacionadas ao armazenamento de dados.

A latência também importa muito para essa funcionalidade. Nosso modelo Composer tem uma das maiores velocidades de tokens por segundo (TPS) do setor, e estamos trabalhando duro para torná-lo mais inteligente e mais rápido. Adicionar round trips de rede a uma operação tão crítica, que o modelo usa constantemente (muitas vezes em paralelo), só acrescenta atrito, interrupções e nos leva na direção oposta do nosso objetivo para a interação com Agentes.

Ao contrário dos índices semânticos, um índice para busca por expressões regulares também precisa estar muito atualizado, principalmente quando se trata de o modelo ler as próprias alterações. Não precisamos atualizar continuamente nosso índice semântico porque recalcular os embeddings de um arquivo depois que ele é modificado não faz com que o novo embedding se desloque significativamente no espaço multidimensional. A busca por vizinho mais próximo que realizamos ainda levará o Agente na direção certa. No entanto, se o agente estiver procurando um texto específico e não o encontrar, muitas vezes ele vai entrar em uma perseguição inútil, desperdiçar tokens e acabar frustrando o propósito da nossa otimização de desempenho.

Trazer esses índices para o cliente realmente traz seu próprio conjunto de desafios. Sincronizar dados em disco pode ser complexo e caro, mas na prática fazemos isso de forma muito eficiente: controlamos o estado do índice tomando como base um commit no repositório Git subjacente. As alterações do usuário e do agente são armazenadas como uma camada sobre ele. Isso torna a atualização muito rápida, e o carregamento e a sincronização na inicialização também muito rápidos.

Para garantir que o uso de memória no editor permaneça mínimo, armazenamos nossos índices em dois arquivos separados. O primeiro arquivo contém todas as posting lists do índice, uma após a outra — gravamos isso diretamente em disco durante a construção. O outro arquivo contém uma tabela ordenada com os hashes de todos os n-grams e o offset da posting list correspondente no arquivo de postings. Armazenar hashes aqui sem armazenar os n-grams completos é sempre seguro: isso pode fazer com que uma posting list se torne mais ampla quando dois hashes colidem (algo extremamente improvável na prática), mas não pode produzir resultados incorretos. Isso também nos dá um layout muito compacto para a tabela de consulta. Em seguida, fazemos mmap dessa tabela, e apenas dessa tabela, no processo do editor, e a usamos para atender consultas com uma busca binária. A busca retorna um offset, e lemos diretamente nesse offset no arquivo de postings.

#Conclusões

Descobrimos que fornecer índices de busca de texto para modelos rápidos, como o nosso Composer 2, cria uma diferença qualitativa nos fluxos de trabalho com Agentes. O impacto é muito mais pronunciado em repositórios Enterprise maiores, porque o grep é uma das poucas operações do Agente cuja latência aumenta junto com o tamanho e a complexidade do código em que se está trabalhando. Veja estes exemplos de fluxos de trabalho executados com o Composer 2: eliminar totalmente o tempo gasto procurando na base de código gera uma economia de tempo significativa — principalmente quando o Agente está investigando bugs — e permite iterar com muito mais eficácia.

Quanto ao que vem por aí, quem sabe! Há muitos avanços empolgantes em torno de fornecer contexto para Agentes, e muitos pesquisadores trabalhando nessa área — inclusive da nossa equipe. Vamos continuar otimizando o desempenho das abordagens atuais, incluindo índices semânticos, e esperamos trazer formas totalmente novas de melhorar ainda mais o desempenho dos Agentes, sempre garantindo que eles possam operar onde isso realmente importa: nos maiores repositórios do mundo, onde o futuro do desenvolvimento com Agentes está realmente ganhando força.