JavaScript Regex Hangs (usando V8)

Question

Estou usando este regex para obter o conteúdo de uma tag em um arquivo.

var regex = new RegExp("<tag:main>((?:.|\\s)*)</tag:main>");

Isso faz com que o motor V8 pendure indefinidamente.

Agora, se eu usar new RegExp("<tag:main>([\s\S]*)</tag:main>"), tudo está bem.

Alguém tem uma ideia por que o primeiro leva muito tempo?

Answer 1

Isso catastroficamente recua em longas sequências de espaços que ocorrem após o último fechamento </tag:main> marcação. Considere o caso em que a sequência de sujeitos termina com 100 espaços. Primeiro, corresponde a todos eles com o . À esquerda da alternância. Isso falha porque não há tag de fechamento, por isso tenta combinar o último personagem com o \s em vez de. Isso também falha, então tenta corresponder ao segundo espaço como um \s e o último espaço como um .. Isso falha (ainda sem tag de fechamento), por isso tenta o último espaço como um \s. Quando isso falha, corresponde ao terceiro a poucos espaço como um \s e tenta todas as quatro maneiras de combinar os dois últimos espaços. Quando isso falha, ele tenta o quarto espaço de quarta ao longo como um \s e todas as 8 maneiras nos últimos 3 espaços. Então 16, 32 etc. O universo termina antes de chegar ao espaço de 100ª para o longo.

Diferentes VMs têm reações diferentes para correspondências regexp que levam eternamente por causa do retorno catastrófico. Alguns simplesmente relatam 'sem correspondência'. No V8, é como escrever qualquer outro loop infinito ou próximo infinito.

Usando não-greedos * fará o que quiser (você quer parar no primeiro </tag:main>, não o último), mas ainda fará tracking catastrófico para longas cordas de espaços onde falta a sequência de fechamento.

Garantir que os mesmos caracteres no suporte interno não possam corresponder aos dois lados da alternância reduzirá o problema de um exponencial para um que é linear no comprimento da corda. Use uma classe de caracteres em vez de uma alternância ou coloque \n no lado direito da barra de alternância. \n está disjunto com . Portanto, se você acertar uma longa sequência de espaços, o mecanismo Regexp não tentará todas as combinações esquerda-esquerda, etc. antes de terminar.

Answer 2

Presumo que seja catastroficamente rastreamento traseiro.

Eu acho que parte da questão pode muito bem ser que os pontos e os não sejam mutuamente exclusivos.

Se eu mudar sua expressão para

<tag:main>((?:.|[\r\n])*)</tag:main>

e executá -lo no depurador Regex Buddy, falha muito mais rápido no caso de a sequência de testes não ser uma correspondência.

Answer 3

Ao invés de (?:.|\s)*, você pode usar [^]* Para combinar com qualquer personagem, incluindo várias formas de nova linha.

Não há alternância, portanto, nenhum risco de retrocesso catastrófico.