Hoje meu amigo Metal estava com um probleminha pra escrever um mapeamento de URL para o Django. O Django usa uma idéia que eu acho meio estúpida, que é mapear expressões regulares para métodos, com partes capturadas sendo transformadas em argumentos. Flexível, mas muito propensa a erros e mais complexa do que eu acho que mapeamento de URLs tem que ser.
De qualquer forma, o método dele tinha de receber um endereço de email como único argumento. O mapeamento que ele estava usando era o seguinte:
- (r’^login/(?P<e>.*)/?$’, ‘projeto.aplicacao.views.login’)
Isso fazia com que a variável ‘e’ do método login recebesse o endereço de email, quando o usuário acessasse a URL /login/endereco@deemail.com. O problema é que algumas vezes a URL acessada é /login/endereco@deemail.com/ (note a barra no final). “Ah, mas tem aquela barra depois do parentese, com o ponto de interrogação que serve justamente pra esse caso”, dirá você… e eu já te digo que se a barra estiver presente ela vai ser capturada para a variável ‘e’! Bug? Nah, só uma peculiaridade de como funcionam as expressões regulares.
Entender duas coisas simples faz você subir de nível em expressões regulares:
- ERs são batidas caractere a caractere
- * e + são gulosos, e vão comer tudo que você der pra eles
Um exemplo simples; considere o seguinte texto:
"a" b "c"
Se você aplicar a esse texto a seguinte expressão regular: “.*” o que você acha que vai bater? Vejamos? Note que as aspas duplas fazem parte da ER; as aspas simples são só pra impedir o shell de tentar expandir os caracteres especiais.
$ echo ‘”a” b “c”‘ | egrep –colour ‘”.*”‘
“a” b “c”
O egrep coloriu o texto inteiro; isso aconteceu porque a ER foi batida da seguinte forma:
- pega o primeiro caractere da ER, “; bate com o primeiro caractere da string, “? bate
- pega o segundo caractere da ER, ., ou seja, qualquer caractere; bate com o segundo caractere da string, a? bate
- pega o terceiro caractere da ER, *, opa, é só repetir o último o tanto que der agora…; bate com o terceiro caractere da string, “? bate
- ainda no terceiro caractere da ER, *; bate com o quarto caractere da string, [espaço_em_branco]? bate
- …
- ainda no terceiro caractere da ER, *; bate com o oitavo caractere da string, c? bate
- ainda no terceiro caractere da ER, *; bate com o nono caractere da string, “? bate
- acabaram os caracteres da string… e agora? bom, pegamos o quarto caractere da ER, “; como estamos no final da string vamos voltar até achar um caractere que bata com ele… voltamos para o nono caractere da stirng, “, bateu, acabou aqui
Esse último passo, voltar para tentar bater na string caracteres que ainda existem na ER é chamado de backtracking, e dependendo do tamanho do texto que está sendo processado pode destruir o desempenho da aplicação que estiver usando ER. Bom… mas como resolvemos isso?
$ echo ‘”a” b “c”‘ | egrep –colour ‘”[^"]*”‘
“a” b “c”
O que eu fiz? Basicamente eu troquei o . por uma expressão que diz não “. Ou seja, estou pedindo a ER para bater qualquer número de caracteres que não sejam aspas duplas. Vamos repetir o processo:
- pega o primeiro caractere da ER, “, bate com o primeiro caractere da string, “? bate
- pega o segundo caractere da ER, [^"], opa aqui temos uma expressão dizendo que não serve o caractere “; bate com o segundo caractere da string, a? bate
- pega o terceiro caractere da ER, *, opa, é só repetir o último o tanto que der agora…; bate com o terceiro caractere da string, “? não
- …
O fato de termos usado uma expressão que diz, simplificando, não ” repetido n vezes fez com que o operador * parasse antes de chegar ao final do texto, o que nos poupou muito tempo, e ainda deu o resultado esperado. A solução para o problema do Metal era, portanto, trocar o . por [^/] na expressão dele. Dessa forma a barra, quando aparecia, era batida do lado de fora do parentese, e não era capturada.
Fica como exercício para o leitor imaginar o que acontece quando tentamos pegar o que existe, num gigantesco arquivo HTML, entre a tag <html> e a tag <head> usando a ER <html>.*<head>; eu já posso adiantar que não é nada eficiente… alguém se habilita a postar nos comentários? =D
Update: o coredump lembrou o operador *?, que é o * não-greedy; ele é útil, mas veja nos comentários por que ele não é uma solução para esse problema específico.