Mundur: gambaran umum

Saat pengukur serakah "melampaui", mesin akan melakukan pelacakan mundur: ia mundur, mencoba konfigurasi lain, mencoba lagi. Pada pola sederhana itu tidak terlihat; pada pola yang ditulis dengan buruk, ini bisa menjadi eksponensial dan membekukan browser selama beberapa detik. Ini adalah akar dari ReDoS (Reguler ekspresi Penolakan Layanan).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consumes everything: "abc123def"
  2.  \d  fails (end of string).
  3.  Backtrack: .* drops 'f' -> "abc123de", \d fails on 'f'.
  4.  Backtrack: .* drops 'ef' -> "abc123d", \d fails on 'e'.
  5.  ... and so on until \d finds a digit: match = "abc123" + "?"... actually
       the pattern matches "abc123" because .* leaves "def" and \d looks at '3'? No: the
       backtrack continues and .* ends up being "abc12", \d=3.  Final match: "abc123".

Mesinnya selalu sampai di sana, tetapi jika ada pengukur serakah penghitung serakah lainnya (misalnya (a+)+), jumlah konfigurasi untuk mencoba bisa meledak.

Pola bencana

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Tidak ada tambahan b → polanya gagal, tetapi untuk mencapainya mesin mencoba setiap saat kemungkinan partisi as. Pertumbuhan Eksponensial: dengan 30 as Anda bisa menunggu berjam-jam.

Bahaya kemunduran dan ReDoS

Ketika suatu pola berisi bilangan yang tumpang tindih atau bersarang (misalnya (a+)+), mesin mengevaluasi sejumlah jalur secara eksponensial sebelum gagal. Mengganti wildcard generik dengan mengecualikan kelas karakter secara dramatis mengurangi jalur kemunduran.

Cobalah

Tinjau latihan

Tantangan tambahan