O interior de um mecanismo de regex como biblioteca

• O crate regex do Rust, após anos de reescrita, expôs uma parte considerável de seus mecanismos internos como a API do crate regex-automata com versionamento separado, e a transição foi concluída no regex 1.9
• A reescrita começou por causa da dificuldade de combinar estratégias de busca, da dificuldade de testar cada mecanismo interno, da demanda por uma API de múltiplos padrões mais detalhada que RegexSet e da necessidade de compartilhar DFAs totalmente compilados
• O regex-automata organiza o processamento de regex no fluxo Ast → Hir → extração de literais/Prefilter → Thompson NFA → PikeVM·BoundedBacktracker·one-pass DFA·DFA·lazy DFA → meta engine
• O desempenho é garantido priorizando, sempre que possível, a busca por literais e mecanismos da família DFA, com PikeVM, bounded backtracker e one-pass DFA complementando nos casos de grupos de captura ou situações excepcionais
• A API pública e as abstrações reutilizáveis facilitaram testes e experimentação, mas aumentaram a quantidade de código, o tamanho do binário e o tempo de compilação; o DFA totalmente compilado passou a ser opt-in, e o regex-lite foi adicionado como alternativa leve

---

A reescrita de regex e a abertura do regex-automata

• O crate regex do Rust foi reescrito ao longo de vários anos para melhorar a composição interna e facilitar a adição de otimizações, mantendo a correção
• Nesse processo, foi criado o regex-automata, que expõe como API separada uma parte considerável da implementação interna do crate regex
• O regex-automata é apresentado como o primeiro caso em que o interior de uma biblioteca de regex foi exposto nesse nível como uma biblioteca separada e versionada
• O regex 1.9 foi lançado em 5 de julho de 2023, concluindo essa reescrita
• O material é voltado a programadores Rust e a pessoas interessadas na implementação de mecanismos de regex baseados em autômatos finitos, assumindo experiência prévia com regex

Problemas antes da reescrita

• O crate regex anterior seguia a tradição do RE2 e usava internamente várias estratégias de busca, mas, à medida que elas foram sendo adicionadas de forma orgânica, ficou difícil combiná-las
  • O PikeVM foi projetado como a estratégia inicial e não tinha o tratamento necessário de início e interrupção de busca em slices parciais ao ser combinado com lazy DFA
  • Era difícil inferir qual estratégia era usada para qual regex
  • Várias expressões match reimplementavam a mesma lógica, tornando fácil que a sincronização entre elas se perdesse
  • Mesmo em regexes que só precisavam de Aho-Corasick, um Thompson NFA que não seria usado podia acabar sendo criado desnecessariamente
• Testar os mecanismos internos também era complicado
  • A API pública parece um único mecanismo de regex, mas internamente há várias estratégias, e todas precisam se comportar da mesma forma para a mesma entrada
  • Antes do regex 1.9, as estratégias internas não faziam parte da API pública, então era difícil testar cada mecanismo de forma independente
  • Os testes existentes tinham uma estrutura quase de hack, dependente de exposição de API interna, implementações From não documentadas, macros e alvos de teste específicos por mecanismo
• Também havia pedidos de várias APIs de nicho que não se encaixavam bem na superfície da API existente
  • RegexSet só informa quais padrões casaram em algum ponto da haystack, sem fornecer offsets do match nem offsets de grupos de captura
  • Havia necessidade de executar busca anchored sem colocar ^ no padrão
  • Era requisitada a capacidade de passar diretamente um mutable scratch space, sem sincronização interna durante a busca
  • Também foram pedidos recursos para executar regex sobre haystacks não contíguas, como streams ou ropes
• Ao expor os internos em um crate versionado separadamente, tornou-se possível não complicar a API regex de uso geral e, ao mesmo tempo, experimentar APIs para especialistas com um ciclo mais rápido de breaking changes

A fronteira de abstração criada pelo DFA totalmente compilado

• A motivação inicial do regex-automata era oferecer um runtime mínimo que permitisse criar um DFA totalmente compilado, serializá-lo e depois fazer buscas com desserialização zero-copy
• O regex-automata inicial foi usado para criar os DFAs da implementação dos algoritmos Unicode do bstr
• Ao construir o DFA, surgiu a necessidade de uma estrutura de dados de NFA e de um compilador semelhantes aos do crate regex, e, à medida que esse código ficava complexo, cresceu a necessidade de compartilhá-lo
• No começo, chegou-se a considerar um crate separado como regex-nfa, mas mais código — incluindo o processo de determinização — podia ser compartilhado entre regex e regex-automata
• A fronteira de abstração ficou mais próxima de um mecanismo de regex do que de um “NFA”, e no fim o regex-automata foi redefinido como um conjunto de vários mecanismos
• O plano de longo prazo era colocar todos os mecanismos de regex no regex-automata e transformar o crate regex em um wrapper fino sobre ele

Inspecionando a estrutura interna com regex-cli

• O regex-cli é um programa mantido no repositório do crate regex e oferece acesso via linha de comando a várias APIs de regex-syntax, regex-automata e regex
• A instalação pode ser feita com o seguinte comando

cargo install regex-cli

• regex-cli debug pode exibir AST, HIR, literais, Thompson NFA, one-pass DFA, dense DFA, sparse DFA e outros
• A regex . com Unicode ativado gera um Thompson NFA muito mais complexo para processar valores escalares UTF-8, enquanto (?-u:.) com Unicode desativado gera um NFA mais simples
• regex-cli find permite executar buscas ad hoc e, com o meta engine, também fazer busca por múltiplos padrões e exibir grupos de captura

Fluxo de dados do processamento de regex

• A string de padrão passada para Regex::new é primeiro analisada em um Ast
• O Ast é convertido em Hir
  • O Hir tem menos detalhes que o Ast, e o Unicode case folding e as referências a Unicode character classes são expandidos durante a conversão
• A partir do Hir, são geradas duas coisas
  • Sequências literais usadas para otimização de busca
  • Um Thompson NFA
• O NFA serve de base para criar vários mecanismos
  • PikeVM: processa todas as regexes analisáveis e informa offsets de grupos de captura
  • BoundedBacktracker: informa offsets de grupos de captura usando bounded backtracking
  • one-pass DFA: informa rapidamente offsets de grupos de captura em regexes restritas
  • dense DFA: é muito rápido, mas só informa início e fim do match completo, e sua construção pode exigir tempo e espaço O(2^m) no pior caso
  • lazy DFA: constrói o DFA a partir do NFA durante a busca, geralmente sendo tão rápido quanto um full DFA e evitando o custo exponencial de construção de um full DFA
• Esses mecanismos e o Prefilter são combinados em um único meta regex engine, e o crate regex é um wrapper fino desse meta engine

Otimização de literais

• A extração de literais é uma otimização central dentro de regex
  • Por exemplo, todos os matches de (foo|bar|quux)(\s+\w+) começam com um entre foo, bar e quux
• Os literais são importantes porque algoritmos de busca por uma única string ou por poucas strings são muito rápidos
  • É possível processar vários bytes do haystack de uma vez com instruções vetoriais
  • Algoritmos gerais de correspondência de regex são difíceis de acelerar de forma consistente da mesma maneira
• Uma busca de substring bem otimizada frequentemente foi pelo menos uma ordem de grandeza mais rápida do que um mecanismo geral de regex
• A extração de literais é heurística
  • É preciso reduzir a taxa de falsos positivos dos matches candidatos
  • Também é preciso minimizar o impacto do prefilter na latência total
  • Ambas as condições dependem do haystack, mas analisá-lo antes da busca pode piorar o tempo total da pesquisa
• Uma sequência de literais não é um conjunto, e sim uma sequência ordenada
  • Como o crate regex segue semântica Perl-like de leftmost-first, | não é comutativo
  • Em sam|samwise, só sam pode ser extraído, mas em samwise|sam, ambos são considerados
• Para busca de string única, é usado o módulo memmem do crate memchr
  • O algoritmo principal é o Two-Way, com tempo O(n) no pior caso e espaço constante
  • Rabin-Karp é usado para needle e haystack curtos
  • Em x86_64, é usada uma variante SIMD genérica
• Para busca de múltiplas strings, o Teddy portado do Hyperscan é o principal algoritmo, e em alguns casos também é usado Aho-Corasick

Thompson NFA e otimizações

• A estrutura de dados central dentro do crate regex é a Thompson NFA
• Thompson’s construction cria uma NFA a partir da representação estruturada da regex em tempo O(m), em que m é proporcional ao tamanho da regex após a expansão de repetições contadas
• A NFA pode ser usada diretamente como mecanismo de regex e também convertida em outros tipos, como DFA, para servir de base a outros motores
• A principal otimização do novo compilador de NFA se concentra em reduzir epsilon transitions
  • A Thompson NFA é boa em tempo de construção, mas usa muitas epsilon transitions
  • O cálculo de epsilon closure pode gerar custo recorrente durante a busca ou na construção de DFA
• A otimização de estado sparse representa várias transições de intervalo em um único estado, reduzindo várias instruções Split da abordagem anterior
  • Remove epsilon transitions desnecessárias em regex como [A-Za-z0-9]
  • Na representação atual, pode haver impacto de cache e aumento de memória heap por causa da indireção
• A otimização de autômato UTF-8 mínimo reduz bastante o tamanho da NFA em classes Unicode grandes
  • Na antiga NFA orientada a bytes, \w podia gerar 3.564 states
  • O novo compilador usa o algoritmo de Daciuk para criar uma estrutura com muito menos states e zero epsilon transition
  • A redução da NFA reversa fica desativada por padrão por causa do custo em tempo de compilação
• A otimização de trie de literais compila alternações literais como zap|z|zapper e abc|xyz em um trie para reduzir epsilon transitions
  • Para preservar a semântica leftmost-first, o bloco de transições é dividido em cada ponto onde um match pode aparecer
• Como trabalho futuro para a NFA, estão sendo avaliados a Glushkov NFA e o armazenamento em uma única alocação contígua
  • A Glushkov NFA não tem epsilon transitions, mas sua complexidade de compilação é pior
  • A alocação contígua pode trazer melhor uso de cache e permitir serialização e desserialização zero-copy, mas com maior complexidade de código e possível uso de unsafe

Motores de regex individuais

• Os motores de regex-automata compartilham APIs parecidas
  • Input: define haystack, intervalo de busca, se é anchored e se deve parar cedo
  • Match: contém o intervalo de bytes do match e o PatternID
  • MatchError: indica um erro em que não é possível determinar o resultado da busca

• PikeVM

  • Suporta todo o conjunto de recursos que regex-syntax consegue fazer parse e funciona com haystacks de qualquer tamanho
  • Rastreia as posições dos grupos de captura e calcula os states ativos em lock-step, garantindo tempo O(m * n) no pior caso
  • Como precisa rastrear muitos states e posições de grupos de captura, desempenho é seu principal ponto fraco
  • Tem a característica única, entre os motores de regex-automata, de não retornar erro durante a busca

• BoundedBacktracker

  • Usa backtracking sobre a Thompson NFA, mas com estado adicional para não revisitar trabalho já feito
  • Garante tempo O(m * n) no pior caso, mas usa espaço O(m * n)
  • Em experimentos aproximados, costuma ser cerca de 2 vezes mais rápido que o PikeVM
  • Pode falhar se o tamanho do haystack e o tamanho da regex ultrapassarem a capacidade de visited configurada

• one-pass DFA

  • Reporta offsets de grupos de captura muito rapidamente em uma one-pass NFA restrita
  • É considerado o modo mais rápido de reportar grupos de captura
  • Suporta apenas busca anchored, e muitas regex não são one-pass
  • No modo Unicode, regex que não eram one-pass podem se tornar one-pass ao desativar Unicode por causa da sobreposição de transições em nível de byte

• fully compiled DFA

  • É composto por duas DFAs, uma forward e uma reverse, para encontrar o fim e o início do match completo
  • Sua construção é O(2^m) em tempo e espaço no pior caso, e a DFA densa consome muita memória
  • O motor de DFA completa vem desativado por padrão no crate regex e exige opt-in com a feature perf-dfa-full
  • Funciona sem Cache mutável e pode ser serializado como bytes brutos, permitindo usar o runtime de busca até em ambientes com apenas core

• hybrid NFA/DFA, lazy DFA

  • É semelhante à DFA completa, mas constrói a tabela de transições durante a busca
  • Se a transição já calculada estiver no cache, ela é reutilizada; caso contrário, só aquela transição é calculada com powerset construction da NFA
  • O tempo de busca no pior caso é O(m * n), e o espaço é limitado pela capacidade de cache definida na construção
  • No caso geral, a maioria dos states e transições fica em cache, então na média se comporta como O(n), e na prática mostra desempenho de busca parecido com o da DFA completa em muitas regex
  • Se o cache ficar cheio repetidamente e se tornar ineficiente, retorna erro; no meta engine, normalmente há uma nova tentativa com outro motor

O papel do meta regex engine

• O meta regex engine busca agrupar vários motores em um só e fornecer ao chamador uma API infalível
• O chamador não precisa criar e passar manualmente um Cache a cada busca
  • o meta engine gerencia internamente um pool de cache thread-safe
  • para evitar o custo de sincronização, também oferece uma API de nível mais baixo que permite passar explicitamente um Cache
• regex::Regex, regex::RegexSet, regex::bytes::Regex, regex::bytes::RegexSet são todos wrappers finos do meta engine
• A estratégia interna do meta engine é, em linhas gerais, a seguinte
  • se for possível resolver apenas com busca de substring única ou múltipla, ele evita até mesmo construir um NFA
  • sempre que possível, extrai uma sequência literal de prefixo para usar como Prefilter
  • se o prefixo não for adequado, tenta as otimizações reverse anchored, reverse suffix e reverse inner
  • fora isso, recorre à estratégia central, que inclui PikeVM, bounded backtracker, one-pass DFA, lazy DFA e full DFA
• A estratégia geral pode ser resumida em duas frases
  • buscar literais sempre que possível
  • evitar usar PikeVM sempre que possível
• As otimizações reverse suffix e reverse inner podem, se usadas incorretamente, cair no pior caso O(m * n^2) em relação ao tamanho do haystack
  • o meta engine detecta quando uma varredura reversa tentaria passar do fim de um match de suffix anterior e faz fallback para a estratégia central, preservando a garantia de complexidade temporal

Diferenças em relação ao RE2

• O crate regex e o RE2 têm muitas semelhanças
  • o RE2 também tem um NFA equivalente ao PikeVM, bitstate backtracker, one-pass NFA, lazy DFA e uma estrutura que combina vários motores
  • entre os motores acima, o único que não existe no RE2 é o fully compiled DFA
• As principais diferenças são as seguintes
  • o RE2 oferece opcionalmente semântica POSIX de leftmost-longest além de leftmost-first
  • o RE2 tem suporte mais limitado a Unicode e não oferece opção para usar \w, \s, \d e \b com definições Unicode
  • o RE2 tem suporte limitado a operações de conjunto em character classes além de union
  • o PikeVM do RE2 pode ser mais eficiente em memória
  • as otimizações com literais no RE2 são limitadas, e o crate regex faz mais otimizações desse tipo
  • o lazy DFA do RE2 compartilha o mesmo transition cache entre várias threads, exigindo sincronização, enquanto o crate regex requer um cache separado por thread e usa mais memória
  • o crate regex publica regex-syntax e regex-automata como bibliotecas separadas e versionadas, mas o RE2 não oferece isso
  • regex-automata oferece suporte first-class a regex multi-pattern em todos os motores e também pode reportar o match e os offsets dos grupos de captura de cada padrão correspondente

Estratégia de testes e benchmark

• A nova estratégia de testes consiste em transformar os motores internos em APIs first-class independentes e testar cada motor diretamente
• Todos os testes de regex são definidos em arquivos TOML
• O crate regex-test lê os testes em TOML e os converte para uma representação estruturada
• Para cada configuração de motor, há um teste unitário Rust que executa todos os testes TOML aplicáveis àquele motor
• Como o framework de testes unitários do Rust não é extensível, foi adicionada uma infraestrutura própria com environment variables para filtrar testes específicos
• Só o regex-automata já tem mais de 450 documentation tests
• Durante a preparação do regex 1.9, também foram adicionados muitos alvos de fuzz testing, e alguns bugs foram encontrados com a ajuda de Addison Crump
• Os benchmarks são publicados como um barômetro de regex chamado rebar
  • o rebar faz benchmark não só do crate regex, mas também de vários motores de regex
  • em 242 benchmarks, o regex 1.9 foi em média 1,5 vez mais rápido que o regex 1.7.3 em tempo de busca
  • o tempo para compilar regex teve alguma regressão
  • o 1.8 foi um release de transição com parte do trabalho de migração, por isso 1.7 foi usado como base de comparação

Custos e alternativa leve

• A reescrita consumiu a maior parte do tempo livre do autor nos últimos anos, e projetos como o ripgrep ficaram sem lançamento por um tempo
• Abstrações públicas reutilizáveis tendem a gerar mais código do que abstrações exclusivamente internas
  • como resultado, o tamanho do binário e o tempo de compilação aumentam
• Como a API interna dos motores foi publicada separadamente e com versão própria, quebrar a API exige um breaking change release apropriado de regex-automata
• Para mitigar os custos, foram adotadas duas medidas
  • o motor fully compiled DFA vem desativado por padrão e fica como feature opt-in
  • regex-lite foi publicado como um novo crate
• O regex-lite busca ser praticamente um drop-in replacement do crate regex, mas com foco em otimizar tamanho de binário e tempo de compilação
  • abre mão de recursos ligados a Unicode e desempenho
  • mantém a garantia de complexidade temporal O(m * n)
  • tem zero dependências, inclui seu próprio parser de regex e não compartilha código com o crate regex
• O regex-lite ainda é uma medida experimental de mitigação, mas mostra que, mesmo desativando otimizações e recursos de Unicode via features do crate regex, é difícil chegar perto do tamanho de binário e do tempo de compilação do regex-lite

[GN⁺]

Opiniões do Hacker News

• Mesmo tendo apenas passado os olhos por cima, o crate regex do Rust é realmente impressionante
  Há muitas coisas excelentes feitas pelo BurntSushi, mas o crate regex do Rust é lendário, e o fato de o ecossistema Rust ter há muito tempo uma biblioteca de expressões regulares rápida e fácil de usar é uma grande bênção para a comunidade
  A série de artigos do Russ Cox sobre expressões regulares também é excelente, e recorri a ela durante um verão em que fiz um motor de regex, quando expressões regulares começaram a parecer a interseção perfeita entre teoria e prática
  As mudanças mais profundas de teste neste artigo também são interessantes, e, por se tratar de um crate essencial para o ecossistema, é ótimo ter uma explicação sobre temas tão profundos
  Expressões regulares às vezes são difíceis de ler e também são usadas em excesso em coisas como validação de e-mail, mas são uma das ferramentas mais densas em praticamente qualquer linguagem
  Como livro prático, só conheço bem o Mastering Regular Expressions, de Jeffrey Friedl; no lado teórico, livros de compiladores tratam do assunto, e o Dragon Book também foi bom do ponto de vista de implementação. Gostaria de recomendações de outros livros sobre expressões regulares

  • https://www.cs.princeton.edu/courses/archive/fall19/cos226/l... e https://kean.blog/post/lets-build-regex são excelentes introduções à implementação de um motor de expressões regulares simplificado
    A abordagem é construir um autômato finito não determinístico para a expressão regular e, nesse grafo direcionado resultante, fazer uma busca; se for possível alcançar um vértice correspondente a um estado final, considera-se que houve match
    Para quem usa expressões regulares, esse exercício ajuda a entender que há menos magia do que parece, e, ao imaginar bolinhas saltando por cima de um NFA, os bugs de backtracking catastrófico que você acaba encontrando em produção também passam a ter um significado físico
    Em relação ao texto original, o último comentário do BurntSushi em https://github.com/rust-lang/regex/issues/822 acrescenta um contexto útil à seção sobre APIs de nicho em https://blog.burntsushi.net/regex-internals/#problem-request.... Procurar várias expressões regulares simultaneamente em um texto é algo muito complexo, mas muito útil, então estou ansioso para ver o que a comunidade vai criar com esse padrão
  • Um caso clássico em que expressões regulares brilham em tarefas parecidas com parsing é ao lidar com formatos com delimitadores variados
    Por exemplo, em um formato com número fixo de campos, como header:field1,field2,field3"data"hash, ou em um formato em que a maioria dos elementos é opcional, como suite~split/test1,test2@opt1:opt2^hw1^hw2#flags1#flags2, ferramentas básicas como split não bastam, e expressões regulares se encaixam bem
    É também por isso que expressões regulares rapidamente ficam difíceis de ler. Em uma única regex ficam misturados os delimitadores entre campos, a validade de cada campo e quais campos são opcionais
    Na verdade, são três preocupações separadas, mas a maioria das APIs de regex não permite separá-las em etapas e só aceita uma única string com tudo combinado
  • Fico curioso se esta biblioteca RegEx usa JIT, como a maioria das implementações de JavaScript. Se não, talvez seja um caso em que JavaScript vença Rust
  • Recentemente fiz um pouco de trabalho com RegEx e dei uma olhada neste artigo; pela linguagem usada e pelo fato de ela não retornar erros, ao contrário de outros motores, parecia usar PikeVM
    Por causa das restrições da linguagem e do status de proteção por copyright, precisei criar a funcionalidade de RegEx por conta própria, e expressões regulares às vezes realmente parecem vodu
    Não sei com que frequência outros motores são usados, mas, se muitas linguagens de programação usam PikeVM, entendo por que o Google criou seu próprio SO para servidores e tentou economizar até alguns ciclos de clock usando motores mais rápidos em determinadas situações
    Sei muito bem que acrescentar apenas alguns caracteres à string de busca pode deixar o casamento de padrões muito mais lento. O ditado “cuide dos centavos e os milhões cuidarão de si mesmos” também se aplica bem a RegEx e a ciclos de clock; olhando para conversas dos anos 90 sobre processar milhões de registros por segundo, isso provavelmente deixou alguns programadores muito ricos
  • Minha maior reclamação são as pequenas diferenças entre dialetos de expressões regulares
    Especialmente porque o tratamento de aspas e a forma de encerrar expressões variam demais conforme o dialeto e o contexto; acabei desistindo de memorizar e procuro exemplos sempre que preciso

• Na ActiveState, fui encarregado, junto com um colega recém-saído da faculdade, de criar um depurador de expressões regulares para o editor Komodo
  Contratamos o lendário especialista em Perl Mark Jason Dominus para inserir hooks no motor de regex do Perl, e expusemos esses hooks na UI para que o usuário pudesse acompanhar a execução da expressão regular passo a passo
  Hoje as ferramentas baseadas na web são melhores, mas, em 2001, o Rx Debugger do Komodo era de ponta e também foi muito divertido de desenvolver

  • No passado, precisei de um depurador de expressões regulares offline
    Eu lidava com uma rede air-gapped, então as pessoas que precisavam usar a ferramenta não podiam acessar sites online, e colocar dados de trabalho em qualquer ferramenta online estava totalmente fora de cogitação em qualquer desenho
    Mas a maior parte do esforço está concentrada em ferramentas online, e ferramentas offline são raras e inferiores em comparação com algo como https://regex101.com/
  • Gostaria de recomendações específicas de ferramentas baseadas na web que sirvam para esse uso

• Fico curioso para saber se isso também pode ser usado em listas que não sejam strings
  Existem mecanismos poderosos para pesquisar e modificar listas de caracteres, mas sempre foi frustrante ver tudo isso desaparecer no momento em que se trata de listas de números ou datas
  Por exemplo, se eu quiser encontrar, em uma lista de datas de tentativas de login, todas as sequências em que um sucesso vem depois de 5 ou mais falhas, isso seria simples com regex, mas na prática é preciso criar loops, flags e listas temporárias manualmente
  Também daria para transformar a lista em string, processar e depois converter de volta, mas as desvantagens são óbvias. Mesmo que não seja tão rápido quanto regex baseada em strings, não entendo por que não deveria existir uma regex para tipos arbitrários de lista
  Também encontrei um protótipo em Python que fiz tempos atrás: https://github.com/boppreh/listregex
  É muito lento, mas satisfatório como experimento de API, e também oferece ferramentas que regex não tem, como inversão de padrões, interseção e pareamento

  • Não dá. Esta biblioteca de regex é fortemente acoplada à busca em strings, e isso é uma decisão de design intencional
    Fazer um motor de regex desse tipo ter um alfabeto genérico já é inviável desde o começo. Em especial, é realisticamente muito difícil fazer isso de uma forma que não prejudique o design da API e o desempenho dos principais casos de uso
    Não é difícil criar um motor de regex desses sem se preocupar com desempenho. Por exemplo, você pode pegar o crate regex-lite que publiquei e torná-lo tão genérico quanto quiser, e no processo vai encontrar alguns desafios interessantes
    Também não é que algo assim não exista. As pessoas tentaram criar isso[1]. Só que parecem exagerar um pouco a utilidade geral, então normalmente não ganham muita tração :-)
    [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html
  • O std::basic_regex da biblioteca padrão do C++ tenta fazer isso ao expor uma classe template para tipos de caracteres definidos pelo usuário: https://en.cppreference.com/w/cpp/regex/basic_regex
    É possível fornecer uma classe de traits que define o comportamento necessário para o “caractere” definido pelo usuário
    Mas o desempenho cai bastante, e é provável que funcione tão bem quanto colocar objetos arbitrários não textuais em uma std::basic_string definida pelo usuário
  • Seria preciso definir de alguma forma uma API que faça matching sobre uma janela deslizante de valores
    Não é impossível, mas a maioria das linguagens não tem uma boa interface para isso

• Uso Ripgrep todos os dias para encontrar coisas em código ou arquivos de texto, e sou grato sempre que o uso, seja no Windows, Linux, Mac, VSCode ou Vim
  É um dos softwares que mudou minha vida e minha forma de trabalhar
  Quando sou obrigado a usar grep, parece que voltei para a época em que tudo rodava em uma CPU single-core e os dados ficavam em um disco rígido giratório PATA/IDE lento
  BurntSushi merece respeito suficiente entre os grandes programadores

  • O ripgrep tem uma linhagem. Antes dele havia o ag, antes dele o ack, e todos tentavam oferecer uma interface muito melhor que o simples grep

• Por causa de um problema de trabalho, precisei criar um RegexSet com mais de 10 milhões de regexes muito longas
  Nenhum motor conseguia lidar com isso no estado padrão, e o RegexSet do Rust também não era suficiente com os valores padrão
  Ainda assim, usar regex-automata e regex-syntax e ler o código foi um material de aprendizado muito útil mesmo em 2018
  No fim, o projeto de trabalho tomou a API do Lucene como modelo, mas isso só foi possível depois de aprender os fundamentos com os crates de regex

  • 10 milhões de regexes é uma escala enorme. Até Aho-Corasick mal dá conta de 10 milhões de literais
    O trabalho daqui em diante é fazer o motor de regex escalar melhor com mais padrões. Hoje ele quebraria muito antes de 10 milhões de regexes, e é difícil ter certeza se esse objetivo é realmente possível
    Ainda assim, com certeza dá para ficar melhor do que está agora
    Claro, em busca com múltiplos padrões, o Hyperscan é praticamente o padrão-ouro. Só não sei quão bem ele lidaria com 10 milhões de padrões
  • Pelo fato de você não ter detalhado isso desde o começo, imagino que a resposta seja “não”, mas, se for possível, fico curioso para saber se você poderia compartilhar mais sobre qual era esse problema ou projeto

• Há algum tempo experimentei o crate regex-automata, e ele era a única biblioteca que eu podia usar em um editor de texto porque dava acesso direto ao DFA interno
  A API de uma biblioteca de regex comum espera que a entrada seja uma única string contínua, mas essa abordagem é compatível com qualquer estrutura de dados de texto

• Eu estava escrevendo código que usa o crate regex-automata, especificamente o release inicial 0.2.0, quando este artigo saiu
  Parece que chegou a hora de verificar se preciso explorar de novo a nova estrutura interna
  Ainda não li o artigo, mas parece muito interessante e com timing perfeito
  Alguns minutos depois, vi que a resposta está mais para “talvez”, mas, por ser um release oficial, talvez isso até permita simplificar bastante o código
  Cerca de mais 10 minutos depois, foi bem painless, e o novo método Builder::patch foi uma melhoria completa
  P.S.: ainda estou bloqueado em todos os seus repositórios no GitHub, e considerando que muitos crates são amplamente usados, acho isso meio injusto. Não lembro qual foi o incidente original. O próprio crate regex agora parece estar sob a organização rust-lang, mas ainda há coisas com as quais não consigo interagir

  • A documentação do regex-automata 0.2.0 tinha um grande aviso sobre isso e recomendava fortemente usar o 0.1: https://docs.rs/regex-automata/0.2.0/regex_automata/
    Eu também não lembro qual foi o incidente original. Bloqueio muita gente por vários motivos, mas agora desbloqueei você

• A BioJulia lançou o Automa.jl, um mecanismo de expressões regulares em Julia puro que permite inserir código Julia arbitrário em tempo de compilação
  Não quero diminuir o fato de que o regex do Rust é muito mais avançado que o Automa, mas é difícil concordar com a afirmação de que este é o primeiro caso de expor os internos de expressões regulares como uma biblioteca

  • Isso soa como duas coisas diferentes
    Por exemplo, o PCRE2 tem suporte a “callout”, que soa parecido com o que foi mencionado: https://www.pcre.org/current/doc/html/pcre2callout.html
    Coisas como ragel ou re2c também vêm fazendo trabalhos semelhantes
    O que este blog está falando é pegar os internos da própria biblioteca de regex, transformá-los em uma biblioteca versionada separadamente e permitir que outras pessoas os componham
    Para backtrackers, isso é menos natural, já que em geral o motor só tem um backtracker, mas bibliotecas baseadas em autômatos frequentemente combinam vários motores de diversas maneiras
    Ainda assim, backtrackers também poderiam expor coisas como o parser de regex ou a AST, que na prática não costumam ser expostos