Regex o podanie nazwy użytkownika zwiększa zużycie procesora

Question

Mamy następujące zasady naszej walidacji Nazwa użytkownika:

• Nazwa może mieć znaków alfanumerycznych
• Nazwa może mieć podkreślenia, myślnika lub okres
• Na razie zakładamy, nazwa użytkownika jest w ASCII
• Nazwa nie może zaczynać lub kończyć się kropką
• Nazwa użytkownika nie może początek, koniec lub mieć żadnych spacji

Mamy następujące regex samo:

^(([a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*)([\\.]*[a-zA-Z0-9])*)+$ 

Teraz stara się dopasować dany ciąg, użycie procesora rośnie wykładniczo. Na przykład:

M45766235H.M96312865E@EXAMPLE.COM 

oczywiście, pasujące ciąg jak powyżej powinien zawieść natychmiast, ale chcę wiedzieć, dlaczego jest tak dużo biorąc cykli procesora. Kod końcowa:

import java.util.regex.*; 
public class R { 
    static final Pattern namePattern = Pattern.compile("^(([a-zA-Z0-9]+[_-]*[a-zA-Z0-9]*)([\\.]*[a-zA-Z0-9])*)+$"); 

    public static void main(String... args) { 
     final String userName = "M45766235H.M96312865E@EXAMPLE.COM"; 
     Matcher matcher = namePattern.matcher(userName); 
     System.out.println(matcher.matches()); 
    } 
} 

na innej linii, przepisałem regex jak poniżej i targi dobrze:

^[\\w]+[\\w-_\\.]*[\\w]+$ 

Answer 1

Kiedy regularne silniki wyrażenie używać backtracking dużo, proces dopasowywania się bardzo powoli. Powracanie do tyłu dzieje się bardzo często, gdy pozwalasz, aby różne części wyrażenia pasowały do ​​nakładających się części danych wejściowych, zwłaszcza gdy nie ma żadnego dopasowania: silnik próbuje różnych możliwości rozdzielenia danych wejściowych między częściami wyrażenia regularnego.

Rozważmy prosty przykład z Twojego regex: użyjmy [a-zA-Z0-9]+[_-]*[a-zA-Z0-9]* dopasować M45766235H. pamiętać, że istnieją dwa sub-wyrażeń, które mogą obejmować wszystkie znaki zaczynające się na drugim jednym: Silnik musi wziąć pod uwagę wszystkie te możliwości:

[a-zA-Z0-9]+ [a-zA-Z0-9]* 
------------ ------------ 
M45766235H <nothing> 
M45766235 H 
M4576623  5H 
M457662  35H 
M45766  235H 
M4576  6235H 
M457   66235H 
M45   766235H 
M4   5766235H 
M   45766235H 

Biorąc pod uwagę, że nie ma dopasowania, jest to dziesięć bezużytecznych powtórzeń. Ale to nie koniec! Gdy w miksie znajdują się inne podwyrażenia, które mogą powodować niejednoznaczny zasięg, te dziesięć możliwych dopasowań będzie wypróbowane dla każdego z możliwych dopasowań dalej w ciągu znaków.

Stwierdzenie, że efekty powrotu do tyłu szybko się uzupełniają, byłoby niedopowiedzeniem: pomnożyłyby one geometryczną progresję, pochłaniając w znacznym stopniu procesor.

Morał tej historii polega na próbie zmniejszenia liczby cofnięć. Na przykład, drugie wyrażenie

^[\\w]+[\\w-_\\.]*[\\w]+$ 

może być zapisane tak:

^\\w[\\w-_\\.]*\\w$ 

Oba wyrażenia będzie pasował ten sam zestaw wejść, ale kiedy jest mecz, drugi wyraz będzie miał unikalne dopasowanie, podczas gdy oryginalne wyrażenie miałoby około (N-2)^3 różnych sposobów dzielenia dopasowanego ciągu na trzy podwyrażenia pasujące do znaków słownych.

Oto trochę więcej informacji na podobny temat: Performance of Greedy vs. Lazy Quantifiers.