Regular Expressions
backtracking

Cosa causa Backtracking?

Per trovare una corrispondenza, il motore regex consumerà i caratteri uno per uno. Quando inizia una partita parziale, il motore ricorderà la posizione di partenza in modo che possa tornare indietro nel caso in cui i seguenti personaggi non completino la partita.

• Se la partita è completa, non c'è il backtracking
• Se la partita non è completa, il motore farà retrocedere la stringa (come quando si riavvolge un vecchio nastro) per cercare di trovare un'intera partita.

Ad esempio: \d{3}[az]{2} contro la stringa abc123def sarà sfogliato come tale:

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does match \d (third one)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

Ora lascia cambiare la regex in \d{2}[az]{2} con la stessa stringa ( abc123def ):

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does not match [a-z]
abc123def
    ^ BACKTRACK to catch \d{2} => (23)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

Perché il backtracking può essere una trappola?

Il backtracking può essere causato da quantificatori o costrutti di alternanza opzionali, perché il motore regex cercherà di esplorare ogni percorso. Se esegui regex a+b contro aaaaaaaaaaaaaa non c'è corrispondenza e il motore lo troverà piuttosto veloce.

Ma se cambi la regex in (aa*)+b il numero di combinazioni crescerà abbastanza velocemente, e la maggior parte dei motori (non ottimizzati) cercheranno di esplorare tutti i percorsi e impiegheranno un'eternità per cercare di trovare una corrispondenza o lanciare un eccezione di timeout. Questo è chiamato backtracking catastrofico .

Certo, (aa*)+b sembra un errore newbie ma è qui per illustrare il punto e a volte si finirà con lo stesso problema ma con schemi più complicati.

Un caso più estremo di backtracking catastrofico si verifica con la regex (x+x+)+y (probabilmente lo avete visto prima qui e qui ), che ha bisogno di tempo esponenziale per capire che una stringa che contiene x nient'altro (es. xxxxxxxxxxxxxxxxxxxx ) non corrispondono.

Come evitarlo?

Sii il più specifico possibile, riduci il più possibile i possibili percorsi. Nota che alcuni reenerx matcher non sono vulnerabili al backtracking, come quelli inclusi in awk o grep perché sono basati su Thompson NFA .