ReTabNews

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.