Backtracking: podstawy

Kiedy zachłanny kwantyfikator „przesadzi”, silnik cofa się: cofnij się o krok, spróbuj innej konfiguracji, spróbuj ponownie. Chodź proste wzory są niewidoczne; na źle napisanych wzorach może się stać wykładniczy i zablokuj przeglądarkę na kilka sekund. To jest korzeń ReDoS (Wyrażenie regularne Odmowa usługi).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consuma tutto: "abc123def"
  2.  \d  fallisce (fine stringa).
  3.  Backtrack: .* lascia 'f' -> "abc123de", \d fallisce su 'f'.
  4.  Backtrack: .* lascia 'ef' -> "abc123d", \d fallisce su 'e'.
  5.  ... e cosi' via finche' \d trova una cifra: match = "abc123" + "?"... in realta'
       il pattern matcha "abc123" perche' .* lascia "def" e \d cerca su '3'? No: il backtrack
       continua e .* finisce per essere "abc12", \d=3.  Match finale: "abc123".

Silnik zawsze tam dotrze, ale jeśli ma go zachłanny kwantyfikator inny zachłanny kwantyfikator (np. (a+)+), liczba konfiguracje do wypróbowania mogą eksplodować.

Katastrofalne wzorce

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Nic ostatecznego b → wzorzec nie działa, ale silnik próbuje się tam dostać wszystkie możliwe partycje a. wykładniczy wzrost: z 30 a możesz czekać godzinami.

Niebezpieczeństwa związane z wycofywaniem się i ReDoS

Gdy wzorzec zawiera nakładające się lub zagnieżdżone kwantyfikatory (np. (a+)+), silnik ocenia wykładniczą liczbę kombinacji, zanim zakończy się niepowodzeniem. Zastąpienie ogólnych symboli wieloznacznych wykluczającymi klasami znaków radykalnie zmniejsza liczbę ścieżek wycofywania się.

Spróbuj sam

Przejrzyj ćwiczenie

Dodatkowe wyzwanie