Dlaczego "/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX") zajmuje tak dużo czasu?

Question

Kiedy biegnę

/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX") 

w Chrome lub IE, trwa ~ 10 sekund. (Firefox jest w stanie to ocenić prawie natychmiast.)

Dlaczego zajmuje to tyle czasu? (I dlaczego/w jaki sposób Firefox potrafi to zrobić tak szybko?)

(Oczywiście, nigdy bym nie uruchamiał tego konkretnego regexu, ale trafiam na podobny problem z wyrażeniem URL pod adresem http://daringfireball.net/2010/07/improved_regex_for_matching_urls i wydaje mi się, że sprowadzają się do tego, to istnieją pewne adresy URL, które spowodują, że przeglądarka zamknąć)

na przykład:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i; 
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA") 

Answer 1

jak wskazano thg435, to brzmi jak katastrofalnego back-tracking. Istnieje doskonały artykuł na ten temat, Regular Expression Matching Can Be Simple And Fast.

Opisuje efektywne podejście znane jako Thompson NFA. Jak jednak wspomniano, nie obsługuje to wszystkich funkcji współczesnych wyrażeń regularnych. Na przykład nie może tworzyć odsyłaczy wstecz. Jednak, jak zaproponowano w art.

„Mimo to, byłoby rozsądne, aby korzystać NFA symulację Thompson za wyrażeń najbardziej regularnie, a tylko wydobyć backtracking gdy jest Potrzebna jest szczególnie mądry realizacja może połączyć dwa, , odwołując się do wycofywania tylko w celu dostosowania do referencji. "

Podejrzewam, że może to robić Firefox.