regex · elaborazione del testo · sicurezza

Che cos'è esattamente una regex?

Un'espressione regolare, o regex, è un piccolo linguaggio che descrive la forma del testo anziché il suo contenuto esatto. Invece di chiedere «questa stringa è uguale a abc?», chiedi «questa stringa ha la forma di tre lettere, un trattino e quattro cifre?».

L'idea è tutta qui. Il resto è notazione.

La notazione, in una passata

Quasi tutto ciò che leggerai si costruisce con una manciata di pezzi:

• . un carattere qualsiasi, \d una cifra, \w un carattere di parola, \s uno spazio
• * zero o più, + uno o più, ? zero o uno, 5 tra due e cinque
• [abc] uno qualsiasi di questi, [^abc] tutto tranne questi, [a-z] un intervallo
• ^ l'inizio della stringa, $ la sua fine
• (...) un gruppo che puoi ripetere o catturare, | l'uno o l'altro

Così ^\d3-\d4$ si legge: dall'inizio, tre cifre, un trattino, quattro cifre, poi la fine. Nulla di più.

Perché lo stesso pattern si comporta diversamente in due linguaggi

Non esiste una regex. Esiste una famiglia di dialetti che concordano sulle basi e divergono oltre: POSIX, PCRE, la variante integrata in JavaScript, quella di Python, quella di Go. Il lookbehind, i gruppi con nome, gli escape di proprietà Unicode e persino ciò che \d considera una cifra sono punti in cui si separano.

La conseguenza pratica è che un pattern copiato da una risposta scritta per un altro linguaggio può fare in silenzio qualcos'altro nel tuo. Provalo dove verrà eseguito, non dove l'hai trovato. È a questo che serve il tester di regex di questo sito.

Il modo di fallire da conoscere: il backtracking catastrofico

Ecco ciò che trasforma un'utilità di ricerca testuale in un problema operativo.

La maggior parte dei motori di regex dei linguaggi diffusi funziona per backtracking. Quando un pattern può corrispondere in più modi, il motore prova una suddivisione e, se il resto fallisce, torna indietro e ne prova un'altra. Per i pattern ordinari costa poco. Per alcuni no.

La forma pericolosa è una ripetizione dentro una ripetizione, dove le due possono spartirsi lo stesso testo in molti modi. L'esempio da manuale è (a+)+$. Di fronte a una lunga sequenza di a seguita da un carattere che non può corrispondere, il motore deve provare ogni possibile modo di ripartire quelle a tra la ripetizione interna e quella esterna prima di poter concludere che fallisce. Il numero di combinazioni cresce esponenzialmente con la lunghezza dell'input.

Venti caratteri possono essere istantanei. Trenta possono richiedere un secondo. Quaranta possono non finire finché ci lavori. E poiché ciò accade solo su input che quasi corrispondono, non compare mai nei test che hai scritto con input che corrispondono.

Quando quella regex gira su input fornito dall'utente lato server, il caso esponenziale è raggiungibile da chiunque possa inviare una richiesta. È la classe di denial of service nota come ReDoS, catalogata da OWASP come denial of service da espressione regolare.

Come restarne fuori

Diffida dei quantificatori annidati. Un + o un * applicato a un gruppo che già ne contiene uno è la forma da cercare. Spesso si può appiattire in qualcosa con un solo modo inequivocabile di corrispondere.

Ancora e sii specifico. ^, $ e classi di caratteri precise riducono il numero di suddivisioni che il motore deve considerare. [^"]* di solito è meglio di .*.

Non far passare con leggerezza l'input dell'utente in una regex scritta a mano. Per email, URL e date, un parser o una libreria collaudata batte un pattern ingegnoso, e fallisce in modo leggibile.

Conosci il tuo motore. Alcuni, come RE2 in Go, si basano su un algoritmo diverso e non fanno alcun backtracking. Rinunciano a funzioni come i riferimenti all'indietro in cambio di una corrispondenza garantita in tempo lineare. Se una regex deve girare su input ostile, quel compromesso è spesso quello giusto.

In breve

Una regex descrive la forma del testo, con una notazione più piccola di quanto sembri e meno portabile di quanto appaia. Impara la dozzina di simboli, verifica il dialetto dove il codice girerà, e tratta un quantificatore dentro un quantificatore come un difetto finché non è dimostrato il contrario. Il pattern che supera tutti i tuoi test non è quello che manderà giù il sito.