Evitando Catastrophic Backtracking em Expressões Regulares
Fala, pessoal! Hoje quero falar sobre um problema que pode transformar suas expressões regulares em verdadeiras bombas-relógio para a performance da sua aplicação: o Catastrophic Backtracking. Talvez você já tenha passado por isso sem perceber, especialmente se sua regex faz buscas muito complexas ou trava inesperadamente.
Então, se você quer evitar travamentos, loops infinitos e dores de cabeça ao trabalhar com regex, esse artigo é para você. Bora entender esse problema e como evitá-lo!
O que é Catastrophic Backtracking?
O backtracking é um mecanismo que a maioria dos motores de regex usa para encontrar combinações. Basicamente, quando uma regex falha em uma tentativa de correspondência, o motor volta alguns passos e tenta outra abordagem.
O problema acontece quando a regex é escrita de forma que crie muitas possibilidades de combinação antes de finalmente falhar. Isso faz com que o motor de regex passe por um número exponencial de tentativas antes de desistir, podendo travar sua aplicação.
Como o problema acontece na prática?
Vamos entender esse problema com um exemplo prático. Imagine que você quer validar uma string que contém apenas a letra "a" seguida da letra "b" e escreve a seguinte expressão:
^(a+)+b$
Agora testamos com uma string que deveria falhar:
const regex = /^(a+)+b$/;
console.log(regex.test("aaab")); // true (válido)
console.log(regex.test("aaaaaaaaaaaaaaaaaaaaa")); // Falha, mas não imediatamente!
O primeiro teste funciona corretamente, mas o segundo pode travar o motor de regex. Isso acontece porque a regex (a+)+ permite múltiplas maneiras de agrupar os caracteres "a", e o motor tenta todas essas combinações antes de perceber que a string não contém um "b" no final.
Vamos visualizar o que o motor está fazendo:
- Ele começa tentando agrupar todos os "a" dentro do primeiro
(a+). - Como há outro
(a+)englobando esse grupo, ele tenta redistribuir os "a" de diversas formas. - Quando chega ao final da string e não encontra "b", ele volta e tenta outras distribuições possíveis de "a".
- Como há muitas formas de distribuir os "a", o número de tentativas cresce exponencialmente, causando um travamento.
Esse comportamento é chamado de Catastrophic Backtracking porque o tempo de execução cresce de forma imprevisível, dependendo do tamanho da entrada.
Como evitar o Catastrophic Backtracking?
Agora que você entendeu o problema, vamos ver algumas soluções para evitá-lo:
1. Evite grupos desnecessários
Se você não precisa capturar algo, remova os parênteses. No exemplo anterior, ^(a+)+b$ pode ser simplificado para:
^a+b$
2. Use âncoras de limite
Sempre que possível, use ^ e $ para indicar o início e o fim da string, evitando tentativas desnecessárias de backtracking.
3. **Use quantificadores não gananciosos (*?, +?, ??)
Se você precisa usar quantificadores repetitivos, tente usar a versão lazy para reduzir o número de tentativas. Por exemplo:
^a+?b$
Isso faz com que o motor pare assim que encontrar o "b", sem testar todas as combinações possíveis de "a".
4. Use Atomic Groups ((?>...))
Se você está lidando com grupos repetitivos, você pode dizer ao motor para não fazer backtracking dentro do grupo com (?>...).
^(?>a+)+b$
Conclusão
Se você já sofreu com regex travando sua aplicação ou rodando mais devagar do que deveria, agora você sabe que o Catastrophic Backtracking pode ser o problema, e evitar esse problema é questão de boas práticas.
Até a próxima!
Muito bom!
Mas vale lembrar que, dependendo do caso, usar um quantificador lazy não garante que vc está livre do problema. Segue um exemplo retirado deste artigo:
Suponha que tem um arquivo CSV, e quero fazer uma regex que pegue o décimo segundo campo, desde que o primeiro caractere seja "P". Pra isso, uso a regex ^(.*?,){11}P, que a princípio parece ok. O .*?, pega zero ou mais caracteres seguido de vírgula, mas de maneira não-gananciosa para que o ponto não pegue uma vírgula. O quantificador {11} garante que faço isso 11 vezes, e que o P esteja no décimo segundo campo.
O problema acontece quando o décimo segundo campo não começa com "P". Supondo que a linha seja 1,2,3,4,5,6,7,8,9,10,11,12,13: depois que o trecho ^(.*?,){11} consumiu os 11 primeiros campos, a regex falha ao encontrar o "P" (pois o décimo segundo campo começa com o caractere 1). Então ela faz o backtracking e o .*? consome a vírgula depois do 11.
Sim, afinal o ponto corresponde a qualquer caractere, inclusive a vírgula. O quantificador lazy não garante que o ponto nunca vai pegar uma vírgula, ele só garante que não vai pegar mais que o necessário. E neste caso, pegar zero vírgulas não foi o suficiente, então ele tenta de novo pegando uma.
Então agora a décima primeira ocorrência de (.*?,) vai consumir todo o trecho 11,12, e verificar se depois tem um "P", mas como não tem, ela faz mais um backtracking. E agora a décima primeira ocorrência passa a ser o trecho 11,12,13, mas na verdade ela nem chega a ser completada, pois não tem uma vírgula no final. Lembre-se que 11,12,13 corresponde agora a .*?, e depois teria que ter uma vírgula, mas como chegou ao final da string, a regex não encontra um match.
Só que ela não desiste! Agora ela faz o backtracking para a décima ocorrência de (.*?,), fazendo com que ela seja o trecho 10,11,, e aí a décima primeira ocorrência é 12,, para ver se depois tem um P. E como não tem, faz mais um backtracking: a décima ocorrência passa a ser 10,11,12, e assim vai até chegar ao final da string e não encontrar nenhum match.
E ela para pro aí? Claro que não, tem mais um backtracking: agora para a nona ocorrência, que será 9,10,, depois 9,10,11, e depois 9,10,11,12,. Mas entre cada uma dessas tentativas, há mais possibilidades a serem testadas. Por exemplo, ao tentar 9,10,, a décima ocorrência pode ser 11, e 11,12,. E mais uma vez ela chegará ao final da string sem encontrar um match e fará o backtracking para a oitava ocorrência (que abrirá mais possibilidades para a nona, décima, etc), depois novo backtracking para a sétima, e assim por diante.
Fiz um teste no Regex101, e neste link vc pode ver que todo esse backtracking gerou 32240 passos!
A solução, neste caso, foi mudar a expressão. O problema desta regex é que o ponto também pode incluir a própria vírgula, então o melhor é trocá-lo por uma expressão que não pegue a vírgula. Por exemplo, ^([^,\r\n]*,){11}P. Troquei o ponto por [^,\r\n], que é "qualquer caractere que não seja vírgula ou quebra de linha". Repare que assim nem preciso usar o quantificador lazy, pois agora não existe o risco dele pegar uma vírgula por engano.
Aqui podemos ver que agora a regex só precisa de 65 passos para detectar que não existe um match.
Aproveitando, existe também um mito de que o quantificador lazy sempre é "melhor" (ou "pior", já ouvi as duas coisas), ou "mais rápido" (ou "mais lento", também já ouvi ambos), mas isso também não é verdade. Dependendo da regex e das strings sendo buscadas, ele pode ou não ser a melhor opção, conforme eu demonstro aqui.
O mesmo vale para as demais dicas, cada um pode ter casos específicos em que eles podem ser a causa do backtracking excessivo. Usar um ou outro nem sempre garante que vc está livre do problema, cada caso é um caso.
Meus 2 cents:
Expressoes regulares ajudam um bocado, mas trabalhar com elas as vezes pode ser... trabalhoso !
Para quem nao conhece, um material legal para regex eh o:
Parabens pelo artigo, obrigado por compartilhar conosco !