Expressões Regulares IV - as três regras da regex I - backtracking

Alguns anos atrás eu comecei a falar que há três regras para se usar expressões regulares

1. não use regex
2. reconsidere se você precisa usar regex
3. conheça sua engine

Pode parecer engraçado eu usar duas regras para desencorajar o uso de regex sendo que eu estudo isso e estou inclusive escrevendo uma série de artigos dedicados a ensinar como usá-la, mas eu vou explicar.

A primeira e a segunda regra são na verdade a mesma e estão duplicadas para efeito de ênfase.

Quando começamos a aprender regex (e até quando já sabemos há um tempo), ficamos tentados a usar para solucionar qualquer problema. Daí fazemos coisas como essa para validar uma data.

/^(?:([0-1])|(2)|(3))(?(1)[0-9])(?(2)(?:([0-8])|(9)))(?(3)[0-1])\/
(?:(01|03|05|07|09|11)|(04|06|08|10|12)|(02))(?(3)(?(8)(?!)))\/\d*
(?:(04|08|12|16|20|24|28|32|36|40|44|48|52|56|60|64|68|72|76|80|84|
88|92|96)|(\d\d))(?:(00)|(04|08|12|16|20|24|28|32|36|40|44|48|52|56|
60|64|68|72|76|80|84|88|92|96)|\d{2})(?(2)(?(5)(?(8)(?(11)(?(9)|
(?!))|(?(12)|(?!))))))/

(podem testá-la, a propósito 😉 https://regex101.com/r/aqEsf1/1)

Essa atrocidade de regex valida não somente o formato da data (que precisa ser dd/MM/yyyy), mas também valida se a data é válida. Dia 31 de setembro não é validada. Dia 29 de fevereiro de 2021 não é validada. Eu tenho um certo orgulho dessa regex, francamente (sim, eu que fiz).

Porque não a usamos então? Eu apresento dois motivos.

O primeiro é mais óbvio: essa regex é incompreensível e um pesadelo de se mexer. Se houver algum bug nela, qualquer tentativa de mudá-la será muito custosa.
O segundo não é tão óbvio, mas deve ser simples de entender: essa regex é muito custosa para a engine.

Para explicar, precisamos falar sobre como a engine funciona internamente. Apertem os cintos e vamos lá!

Funcionamento interno das engines de regex

Embora cada engine tenha uma particularidade, podemos dividí-las em duas categorias: engines text-directed e regex-directed.
Não falaremos de engines text-directed aqui, pois seu funcionamento é trivial porque não existe backtracking e as engines mais usadas são as regex-directed. Vamos a elas então.

As engines regex-directed, chamadas a partir de agora somente de engines, funcionam basicamente da seguinte forma:

1. Enquanto houver tokens na regex, pegue o próximo token
2. Tente dar match com o próximo caracter da string
3. Se houver match, avance para o próximo token da regex e o próximo caracter da string
4. Se não, volte até uma posição anterior da regex para testar um outro caminho por ela (esse é o backtracking)

Vamos de exemplo. Vamos aplicar a regex /<.*?>/ no texto <span>Teste</span>.

1. Enquanto houver tokens na regex, pegue o próximo token (<)
2. Dá match com o próximo caracter da string (<) 1 Houve match, então avança para o próximo token da regex (.*?) e próximo caracter da string (s)
3. O token .*? é o quantificador lazy que vai dar match no mínimo possível para que a regex seja válida. A primeira tentativa é de um match sem tamanho (match em '').
4. Dá match, então avança para o próximo token da regex (>) e o próximo caracter da string (s).
5. Não dá match, então retorna a regex pro token anterior (.*?)
6. Dá match, pois . dá match em qualquer caracter (exceto quebra de linha), então avança para o próximo token da regex (>) e o próximo caracter da string (p).
7. Não dá match, então retorna regex (.*?).
8. .*? deu match em s antes, mas agora precisa dar match em sp. Tudo bem, pois . dá match em qualquer caracter (exceto quebra de linha) e * dá match em mais de um caracter.
9. Dá match, então avança regex (>) e string (a).
10. Não dá match. Isso vai se repetir até a regex encontrar na string o caracter >. Nesse caso, ela vai dar match e retornar ok.

Segue um esquema tirado da aplicação RegexBuddy para explicar melhor.

Beginning match attempt at character 0
<
< ok
< backtrack
<s
<s backtrack
<sp
<sp backtrack
<spa
<spa backtrack
<span
<span backtrack
<span>
Match found in 11 steps

(espaços adicionados por clareza)

Dessa maneira, é possível notar que há as engines vão e voltam na string até encontrar uma solução para a regex. Vamos pegar o diagrama do RegexBuddy para uma data e aquela regex.

Beggining match attempt at character 0
ok
1
1
1
12
12
12 ok
12 ok
12 ok
12 ok
12/
12/0
12/0 backtrack
12/0
12/0 backtrack
12/0
12/0 backtrack
12/0
12/0 backtrack
12/0
12/0 backtrack
12/ backtrack
12/ backtrack
12/0
12/0 backtrack
12/0
12/0 backtrack
12/0
12/0 backtrack
12/ backtrack
12/ backtrack
12/ backtrack
12/0
12/02
12/02
12/02
12/02 ok
12/02 ok
12/02/
12/02/ backtrack
12/02/ backtrack
12/02/ backtrack
12/02/ backtrack
12/20/2
12/02/20
12/02/20
12/02/20
12/02/200
12/02/200 backtrack
12/02/20 backtrack
12/02/200
12/02/200 backtrack
12/02/200
12/02/200 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/20 backtrack
12/02/2003
12/02/2003
12/03/2003 ok
12/03/2003 ok
Match found in 81 steps

Um tanto mais complexo que a solução preferida, que em Java seria algo como:

Date date = new Date('12/02/2003');

Pois a implementação do Java já testa se a data é válida ao instanciar o objeto.
É importante lembrar que nenhuma engine de regex tem informações semânticas sobre o texto. Enquanto o Java tem como saber que 12 na data é dia e 2003 é ano, a engine de regex só entende texto.

A mesma coisa para email. Em vez de usar uma regex monstruosa como a seguinte:

(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ 
\t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+
(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:
(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)
?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\
r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[
 \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)
?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t]
)*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[
 \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*
)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)
*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+
|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r
\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:
\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t
]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031
]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](
?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?
:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?
:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?
:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?
[ \t]))*"(?:(?:\r\n)?[ \t])*)*:(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|
\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>
@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"
(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?
:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[
\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-
\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(
?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;
:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([
^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\"
.\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\
]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\
[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\
r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] 
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]
|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \0
00-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\
.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,
;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?
:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[
^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]
]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)(?:,\s*(
?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(
?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[
\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t
])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t
])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?
:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|
\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:
[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\
]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)
?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["
()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)
?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>
@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[
 \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,
;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:
\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\[
"()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])
*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])
+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\
.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(
?:\r\n)?[ \t])*))*)?;\s*)

uma solução mais simples é mandar um email para o endereço. Se estiver válido, o email chegará. Para auxiliar o usuário a preencher o formulário, basta verificar com essa regex

.*@.*\..*

ou algo parecido.

A terceira regra será tratada no próximo artigo. Abraços.