Backtracking: cenni

Quando un quantificatore greedy "esagera", l'engine fa backtracking: torna indietro di un passo, prova un'altra configurazione, riprova. Su pattern semplici e' invisibile; su pattern mal scritti puo' diventare esponenziale e bloccare il browser per secondi. E' la radice del ReDoS (Regular expression Denial of Service).

Code

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".

L'engine ci arriva sempre, ma se il quantificatore avido ha al suo interno un altro quantificatore avido (es. (a+)+), il numero di configurazioni da provare puo' esplodere.

Pattern catastrofici

Code

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Niente b finale → il pattern fallisce, ma per arrivarci l'engine prova tutte le partizioni possibili delle a. Crescita esponenziale: con 30 a puoi aspettare ore.

Pericoli del backtracking e ReDoS

Quando un pattern include quantificatori sovrapposti o nidificati (es. (a+)+), l'engine valuta un numero esponenziale di combinazioni prima di fallire. Sostituire i jolly generici con classi di caratteri escludenti riduce drasticamente i percorsi di backtracking.

Prova tu

Esercizio#regex.m2.l4.e1

Tentativi: 0Caricamento…

Estrai il contenuto fra parentesi quadre per ogni occorrenza nel testo. Usa la versione lazy del quantificatore per non saltare a chiusure successive.

Caricamento editor…

Mostra suggerimento

\\[.*?\\] si ferma al primo ] di chiusura: niente backtracking pesante.

Soluzione disponibile dopo 3 tentativi

Esercizio di ripasso

Esercizio#regex.m2.l4.e2

Tentativi: 0Caricamento…

Trova ogni URL `http://...` o `https://...` nel testo, usando il quantificatore `?` per la `s` opzionale e `\\S+` per i caratteri non-spazio del path.

Caricamento editor…

Mostra suggerimento

https? significa 'http' seguito da 's' opzionale. Poi //, poi \\S+ (non-spazi).

Soluzione disponibile dopo 3 tentativi

Sfida aggiuntiva

Esercizio#regex.m2.l4.e3

Tentativi: 0Caricamento…

Matcha le stringhe racchiuse tra virgolette doppie evitando backtracking eccessivo usando la classe negata `[^"]*` invece di `.*`.

Caricamento editor…

Mostra suggerimento

Sostituisci il punto con la classe negata [^"] per limitare i possibili tentativi dell'engine.

Soluzione disponibile dopo 3 tentativi