Backtracking nelle espressioni regolari

Articolo
08/11/2023

Il backtracking si verifica quando un modello di espressione regolare contiene quantificatori o costrutti di alternanza facoltativi e il motore delle espressioni regolari torna a uno stato salvato in precedenza per continuare la ricerca di una corrispondenza. Il backtracking è fondamentale per la potenza delle espressioni regolari. Consente alle espressioni di essere potenti e flessibili e di cercare una corrispondenza di modelli molto complessi. Questa tecnica presenta tuttavia anche alcuni svantaggi. Il backtracking spesso è il fattore più importante che influisce sulle prestazioni del motore delle espressioni regolari. Fortunatamente, lo sviluppatore è in grado di controllare il comportamento del motore delle espressioni regolari e il modo in cui viene utilizzato il backtracking. In questo articolo viene illustrato il funzionamento del backtracking e il modo in cui può essere controllato.

Avviso

Quando si usa System.Text.RegularExpressions per elaborare l'input non attendibile, passare un timeout. Un utente malintenzionato può fornire input a RegularExpressions, provocando un attacco Denial of Service. Le API del framework ASP.NET Core che usano RegularExpressions passano un timeout.

Confronto lineare senza backtracking

Se un modello di espressione regolare non contiene quantificatori facoltativi o costrutti di alternanza, il motore delle espressioni regolari viene eseguito in un tempo lineare, ovvero dopo che il motore delle espressioni regolari trova una corrispondenza tra il primo elemento del linguaggio del modello e il testo della stringa di input, prova a trovare una corrispondenza tra l'elemento del linguaggio successivo del modello e il carattere o il gruppo di caratteri successivi della stringa di input. Il processo continua finché la ricerca della corrispondenza non avrà esito positivo o negativo. In entrambi i casi, il motore delle espressioni regolari avanza di un carattere alla volta nella stringa di input.

Di seguito ne viene illustrato un esempio. L'espressione regolare e{2}\w\b cerca due occorrenze della lettera "e", seguite da qualsiasi carattere alfanumerico, seguito da un confine di parola.

using System;
using System.Text.RegularExpressions;

public class Example1
{
    public static void Run()
    {
        string input = "needing a reed";
        string pattern = @"e{2}\w\b";
        foreach (Match match in Regex.Matches(input, pattern))
            Console.WriteLine("{0} found at position {1}",
                              match.Value, match.Index);
    }
}
// The example displays the following output:
//       eed found at position 11

Imports System.Text.RegularExpressions

Module Example1
    Public Sub Run()
        Dim input As String = "needing a reed"
        Dim pattern As String = "e{2}\w\b"
        For Each match As Match In Regex.Matches(input, pattern)
            Console.WriteLine("{0} found at position {1}",
                              match.Value, match.Index)
        Next
    End Sub
End Module
' The example displays the following output:
'       eed found at position 11

Benché questa espressione regolare includa il quantificatore {2}, viene valutata in modo lineare. Il motore delle espressioni regolari non esegue il backtracking perché {2} non è un quantificatore facoltativo, ma specifica un numero esatto e non un numero variabile di volte in cui trovare la corrispondenza della sottoespressione precedente. Di conseguenza, il motore delle espressioni regolari tenta di trovare una corrispondenza tra il modello di espressione regolare e la stringa di input come illustrato nella tabella seguente.

Operazione	Posizione nel modello	Posizione nella stringa	Risultato
1	e	"needing a reed" (indice 0)	Nessuna corrispondenza.
2	e	"eeding a reed" (indice 1)	Possibile corrispondenza.
3	e{2}	"eding a reed" (indice 2)	Possibile corrispondenza.
4	\w	"ding a reed" (indice 3)	Possibile corrispondenza.
5	\b	"ing a reed" (indice 4)	Possibile corrispondenza non riuscita.
6	e	"eding a reed" (indice 2)	Possibile corrispondenza.
7	e{2}	"ding a reed" (indice 3)	Possibile corrispondenza non riuscita.
8	e	"ding a reed" (indice 3)	La corrispondenza ha esito negativo.
9	e	"ing a reed" (indice 4)	Nessuna corrispondenza.
10	e	"ng a reed" (indice 5)	Nessuna corrispondenza.
11	e	"g a reed" (indice 6)	Nessuna corrispondenza.
12	e	" a reed" (indice 7)	Nessuna corrispondenza.
13	e	"a reed" (indice 8)	Nessuna corrispondenza.
14	e	" reed" (indice 9)	Nessuna corrispondenza.
15	e	"reed" (indice 10)	Nessuna corrispondenza.
16	e	"eed" (indice 11)	Possibile corrispondenza.
17	e{2}	"ed" (indice 12)	Possibile corrispondenza.
18	\w	"d" (indice 13)	Possibile corrispondenza.
19	\b	"" (indice 14)	Corrispondenza.

Se un modello di espressione regolare non include quantificatori facoltativi o costrutti di alternanza, il numero massimo di confronti necessari per trovare una corrispondenza tra il modello di espressione regolare e la stringa di input equivale approssimativamente al numero di caratteri della stringa di input. In questo caso, l'espressione regolare utilizza 19 confronti per identificare le possibili corrispondenze nella stringa di 13 caratteri. In altre parole, il motore delle espressioni regolari viene eseguito in un tempo quasi lineare se non contiene quantificatori facoltativi o costrutti di alternanza.

Backtracking con quantificatori facoltativi o costrutti di alternanza

Quando un'espressione regolare include quantificatori facoltativi o costrutti di alternanza, la valutazione della stringa di input non è più lineare. La corrispondenza dei modelli con un motore NFA (Nondeterministic Finite Automaton) è determinata dagli elementi del linguaggio nell'espressione regolare e non dai caratteri con cui trovare una corrispondenza nella stringa di input. Il motore delle espressioni regolari prova pertanto a trovare una piena corrispondenza con le sottoespressioni facoltative o alternative. Quando avanza all'elemento del linguaggio successivo nella sottoespressione e la corrispondenza ha esito negativo, il motore delle espressioni regolari può abbandonare una parte della corrispondenza esatta e tornare a uno stato salvato in precedenza al fine di trovare una corrispondenza tra l'intera espressione regolare e la stringa di input. Questo processo di tornare a uno stato salvato in precedenza per trovare una corrispondenza è noto come backtracking.

Si consideri, ad esempio, il modello di espressione regolare .*(es)che cerca una corrispondenza con i caratteri "es" e tutti i caratteri che li precedono. Come illustrato nell'esempio seguente, se la stringa di input è "Essential services are provided by regular expressions.", il modello cerca una corrispondenza con l'intera stringa fino ai caratteri "es" in "expressions" compresi.

using System;
using System.Text.RegularExpressions;

public class Example2
{
    public static void Run()
    {
        string input = "Essential services are provided by regular expressions.";
        string pattern = ".*(es)";
        Match m = Regex.Match(input, pattern, RegexOptions.IgnoreCase);
        if (m.Success)
        {
            Console.WriteLine($"'{m.Value}' found at position {m.Index}");
            Console.WriteLine($"'es' found at position {m.Groups[1].Index}");
        }
    }
}
//    'Essential services are provided by regular expres' found at position 0
//    'es' found at position 47

Imports System.Text.RegularExpressions

Module Example2
    Public Sub Run()
        Dim input As String = "Essential services are provided by regular expressions."
        Dim pattern As String = ".*(es)"
        Dim m As Match = Regex.Match(input, pattern, RegexOptions.IgnoreCase)
        If m.Success Then
            Console.WriteLine("'{0}' found at position {1}",
                              m.Value, m.Index)
            Console.WriteLine("'es' found at position {0}",
                              m.Groups(1).Index)
        End If
    End Sub
End Module
'    'Essential services are provided by regular expres' found at position 0
'    'es' found at position 47

A tale scopo, il motore delle espressioni regolari utilizza il backtracking come segue:

Trova la corrispondenza di .* , ovvero di zero, uno o più occorrenze di qualsiasi carattere, con l'intera stringa di input.
Tenta di trovare una corrispondenza di "e" nel modello di espressione regolare. Tuttavia, nella stringa di input non sono presenti altri caratteri di cui cercare una corrispondenza.
Esegue il backtracking fino all'ultima corrispondenza esatta, "Essential services are provided by regular expressions", e tenta di trovare una corrispondenza di "e" con il punto alla fine della frase. La corrispondenza ha esito negativo.
Continua a eseguire il backtracking fino a una corrispondenza esatta precedente, un carattere alla volta, finché la sottostringa temporaneamente corrispondente non è "Essential services are provided by regular expr". Confronta quindi la "e" nel modello con la seconda "e" in "expressions" e trova una corrispondenza.
Confronta la "s" nel modello con la "s" che segue il carattere "e" corrispondente (la prima "s" in "expressions"). La corrispondenza ha esito positivo.

Quando si utilizza il backtracking, la ricerca di una corrispondenza tra il modello di espressione regolare e la stringa di input, con una lunghezza pari a 55 caratteri, richiede 67 operazioni di confronto. In genere, se un modello di espressione regolare include un singolo costrutto di alternanza o un singolo quantificatore facoltativo, il numero di operazioni di confronto necessarie per trovare una corrispondenza del modello è più del doppio rispetto al numero di caratteri della stringa di input.

Backtracking con quantificatori facoltativi annidati

Il numero di operazioni di confronto necessarie per trovare una corrispondenza di un modello di espressione regolare può aumentare in modo esponenziale se il modello include un numero elevato di costrutti di alternanza, se include costrutti di alternanza annidati o se include sopratutto quantificatori facoltativi annidati. Il modello di espressione regolare ^(a+)+$ , ad esempio, è progettato per cercare una corrispondenza con una stringa completa contenente uno o più caratteri "a". Nell'esempio vengono fornite due stringhe di input di lunghezza identica, ma solo la prima stringa corrisponde al modello. La classe System.Diagnostics.Stopwatch viene utilizzata per determinare il tempo richiesto dall'operazione di corrispondenza.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example3
{
    public static void Run()
    {
        string pattern = "^(a+)+$";
        string[] inputs = { "aaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaa!" };
        Regex rgx = new Regex(pattern);
        Stopwatch sw;

        foreach (string input in inputs)
        {
            sw = Stopwatch.StartNew();
            Match match = rgx.Match(input);
            sw.Stop();
            if (match.Success)
                Console.WriteLine($"Matched {match.Value} in {sw.Elapsed}");
            else
                Console.WriteLine($"No match found in {sw.Elapsed}");
        }
    }
}
//    Matched aaaaaaaaaaaaaaaaaaaaaaaaaaa in 00:00:00.0018281
//    No match found in 00:00:05.1882144

Imports System.Text.RegularExpressions

Module Example3
    Public Sub Run()
        Dim pattern As String = "^(a+)+$"
        Dim inputs() As String = {"aaaaaaaaaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaaaaaaaaa!"}
        Dim rgx As New Regex(pattern)
        Dim sw As Stopwatch

        For Each input As String In inputs
            sw = Stopwatch.StartNew()
            Dim match As Match = rgx.Match(input)
            sw.Stop()
            If match.Success Then
                Console.WriteLine("Matched {0} in {1}", match.Value, sw.Elapsed)
            Else
                Console.WriteLine("No match found in {0}", sw.Elapsed)
            End If
        Next
    End Sub
End Module
'    Matched aaaaaaaaaaaaaaaaaaaaaaaaaaa in 00:00:00.0018281
'    No match found in 00:00:05.1882144

Come illustrato nell'output dell'esempio, il motore delle espressioni regolari ha impiegato significativamente più tempo per rilevare che una stringa di input non corrisponde al modello rispetto al tempo impiegato per identificare una stringa corrispondente. Ciò è dovuto al fatto che una corrispondenza negativa rappresenta sempre lo scenario peggiore. Il motore delle espressioni regolari deve utilizzare l'espressione regolare per seguire tutti i percorsi possibili nei dati prima di poter concludere che la corrispondenza è negativa e le parentesi annidate creano molti percorsi aggiuntivi nei dati. Il motore delle espressioni regolari conclude che la seconda stringa non corrisponde al modello effettuando le operazioni seguenti:

Verifica di essere all'inizio della stringa, quindi cerca una corrispondenza tra i primi cinque caratteri della stringa e il modello a+. Determina quindi che non esistono altri gruppi di caratteri "a" nella stringa. Infine, verifica la fine della stringa. Poiché nella stringa rimane un ulteriore carattere, la corrispondenza ha esito negativo. La corrispondenza non riuscita richiede 9 confronti. Il motore delle espressioni regolari salva inoltre le informazioni di stato dalle relative corrispondenze di "a" (che chiameremo corrispondenza 1), "aa" (corrispondenza 2), "aaa" (corrispondenza 3) e "aaaa" (corrispondenza 4).
Torna alla corrispondenza 4 salvata in precedenza. Determina che esiste un altro carattere "a" da assegnare a un gruppo acquisito aggiuntivo. Infine, verifica la fine della stringa. Poiché nella stringa rimane un ulteriore carattere, la corrispondenza ha esito negativo. La corrispondenza non riuscita richiede 4 confronti. Fino a questo momento sono stati eseguiti complessivamente 13 confronti.
Torna alla corrispondenza 3 salvata in precedenza. Determina che esistono sono altri due caratteri "a" da assegnare a un gruppo acquisito aggiuntivo. Tuttavia, il test di fine della stringa ha esito negativo. Torna quindi alla corrispondenza 3 e prova a trovare una corrispondenza degli altri due caratteri "a" nei due gruppi acquisiti aggiuntivi. Il test di fine della stringa ha ancora esito negativo. Le corrispondenza non riuscite richiedono 12 confronti. Fino a questo punto, sono stati eseguiti complessivamente 25 confronti.

Il confronto della stringa di input con l'espressione regolare continua in questo modo fino a quando il motore delle espressioni regolari non ha tentato tutte le combinazioni di corrispondenze possibili, concludendo infine che non vi è alcuna corrispondenza. A causa dei quantificatori annidati, questo confronto è un'operazione O(2ⁿ) o un'operazione esponenziale, dove n è il numero di caratteri all'interno della stringa di input. Ciò significa che nei casi peggiori una stringa di input di 30 caratteri richiede circa 1.073.741.824 confronti e una stringa di input di 40 caratteri richiede circa 1.099.511.627.776 confronti. Se si utilizzano stringhe di queste lunghezze o di lunghezze ancora maggiore, i metodi delle espressioni regolari possono richiedere una quantità di tempo eccessiva per il completamento quando elaborano un input che non corrisponde al modello di espressione regolare.

Controllare il backtracking

Il backtracking consente di creare espressioni regolari potenti e flessibili. Tuttavia, come illustrato nella sezione precedente, insieme a questi vantaggi si ottiene una notevole riduzione delle prestazioni. Per evitare un utilizzo eccessivo del backtracking, è necessario definire un intervallo di timeout quando si crea un'istanza di un oggetto Regex o si chiama un metodo di espressione regolare statica corrispondente. Questo è discusso nella sezione seguente. .NET supporta anche tre elementi del linguaggio delle espressioni regolari che limitano o evitano del tutto l'uso del backtracking e che supportano espressioni regolari complesse senza o con una minima riduzione delle prestazioni: gruppi atomici, asserzioni lookbehind e asserzioni lookahead. Per altre informazioni su ogni elemento del linguaggio, vedere Costrutti di raggruppamento.

Motore delle espressioni regolari senza backtracking

Se non è necessario usare costrutti che richiedono il backtracking, ad esempio, lookaround, backreference o gruppi atomici, è consigliabile usare la modalità RegexOptions.NonBacktracking. Questa modalità è progettata per l'esecuzione con una durata proporzionale alla lunghezza dell'input. Per altre informazioni, vedere Modalità NonBacktracking. È anche possibile impostare un valore di timeout.

Limitare le dimensioni degli input

Alcune espressioni regolari hanno prestazioni accettabili, a meno che l'input non sia estremamente grande. Se è noto che tutti gli input di testo ragionevoli nello scenario sono al di sotto di una determinata lunghezza, è consigliabile rifiutare input più lunghi prima di applicarli all'espressione regolare.

Specificare un intervallo di timeout

È possibile impostare un valore di timeout che rappresenta l'intervallo più lungo per cui il motore delle espressioni regolari cercherà una singola corrispondenza prima di abbandonare il tentativo e generare un'eccezione RegexMatchTimeoutException. Specificare l'intervallo di timeout fornendo un valore TimeSpan al costruttore Regex(String, RegexOptions, TimeSpan) per instanziare espressioni regolari. Inoltre, ogni metodo statico di criteri di ricerca ha un overload con un parametro TimeSpan che consente di specificare un valore di timeout.

Se non si imposta un valore di timeout in modo esplicito, il valore di timeout predefinito viene determinato nel modo seguente:

Usando il valore di timeout a livello di applicazione, se presente. Può trattarsi di qualsiasi valore di timeout applicabile al dominio dell'applicazione in cui viene creata un'istanza dell'oggetto Regex oppure viene eseguita la chiamata al metodo statico. È possibile impostare il valore di timeout a livello di applicazione chiamando il metodo AppDomain.SetData per assegnare la rappresentazione di stringa di un valore TimeSpan alla proprietà REGEX_DEFAULT_MATCH_TIMEOUT.
Usando il valore InfiniteMatchTimeout, se non è stato impostato alcun valore di timeout a livello di applicazione.

Per impostazione predefinita, l'intervallo di timeout viene impostato su Regex.InfiniteMatchTimeout e il motore delle espressioni regolari non ha timeout.

Importante

Quando non si usa RegexOptions.NonBacktracking, è consigliabile impostare sempre un intervallo di timeout se l'espressione regolare si basa sul backtracking oppure opera su input non attendibili.

Un'eccezione RegexMatchTimeoutException indica che il motore delle espressioni regolari non è in grado di trovare una corrispondenza nell'intervallo di timeout specificato, ma non indica perché è stata generata l'eccezione. Il motivo può essere l'utilizzo eccessivo del backtracking, ma è anche possibile che l'intervallo di timeout sia stato impostato su un valore troppo basso dato il carico di sistema al momento in cui l'eccezione è stata generata. Quando si gestisce l'eccezione, è possibile scegliere di ignorare ulteriori corrispondenze con la stringa di input o aumentare l'intervallo di timeout e ritentare l'operazione corrispondente.

Ad esempio, il codice seguente chiama il costruttore Regex(String, RegexOptions, TimeSpan) per creare un'istanza di un oggetto Regex con un valore di timeout di 1 secondo. Il modello di espressione regolare (a+)+$, che corrisponde a uno o più sequenze di uno o più caratteri "a" alla fine di una riga, è soggetto all'utilizzo eccessivo del backtracking. Se viene generata una RegexMatchTimeoutException, l'esempio aumenta il valore di timeout fino a un intervallo massimo di 3 secondi. Successivamente, ignora il tentativo di corrispondere al modello.

using System;
using System.ComponentModel;
using System.Diagnostics;
using System.Security;
using System.Text.RegularExpressions;
using System.Threading;

public class Example
{
    const int MaxTimeoutInSeconds = 3;

    public static void Main()
    {
        string pattern = @"(a+)+$";    // DO NOT REUSE THIS PATTERN.
        Regex rgx = new Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1));
        Stopwatch? sw = null;

        string[] inputs = { "aa", "aaaa>",
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                         "aaaaaaaaaaaaaaaaaaaaaa>",
                         "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>" };

        foreach (var inputValue in inputs)
        {
            Console.WriteLine("Processing {0}", inputValue);
            bool timedOut = false;
            do
            {
                try
                {
                    sw = Stopwatch.StartNew();
                    // Display the result.
                    if (rgx.IsMatch(inputValue))
                    {
                        sw.Stop();
                        Console.WriteLine(@"Valid: '{0}' ({1:ss\.fffffff} seconds)",
                                          inputValue, sw.Elapsed);
                    }
                    else
                    {
                        sw.Stop();
                        Console.WriteLine(@"'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
                                          inputValue, sw.Elapsed);
                    }
                }
                catch (RegexMatchTimeoutException e)
                {
                    sw.Stop();
                    // Display the elapsed time until the exception.
                    Console.WriteLine(@"Timeout with '{0}' after {1:ss\.fffff}",
                                      inputValue, sw.Elapsed);
                    Thread.Sleep(1500);       // Pause for 1.5 seconds.

                    // Increase the timeout interval and retry.
                    TimeSpan timeout = e.MatchTimeout.Add(TimeSpan.FromSeconds(1));
                    if (timeout.TotalSeconds > MaxTimeoutInSeconds)
                    {
                        Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
                                          MaxTimeoutInSeconds);
                        timedOut = false;
                    }
                    else
                    {
                        Console.WriteLine("Changing the timeout interval to {0}",
                                          timeout);
                        rgx = new Regex(pattern, RegexOptions.IgnoreCase, timeout);
                        timedOut = true;
                    }
                }
            } while (timedOut);
            Console.WriteLine();
        }
    }
}
// The example displays output like the following :
//    Processing aa
//    Valid: 'aa' (00.0000779 seconds)
//
//    Processing aaaa>
//    'aaaa>' is not a valid string. (00.00005 seconds)
//
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
//    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
//
//    Processing aaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
//    Changing the timeout interval to 00:00:02
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
//    Changing the timeout interval to 00:00:03
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
//    Maximum timeout interval of 3 seconds exceeded.
//
//    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
//    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
//    Maximum timeout interval of 3 seconds exceeded.

Imports System.ComponentModel
Imports System.Diagnostics
Imports System.Security
Imports System.Text.RegularExpressions
Imports System.Threading

Module Example
    Const MaxTimeoutInSeconds As Integer = 3

    Public Sub Main()
        Dim pattern As String = "(a+)+$"    ' DO NOT REUSE THIS PATTERN.
        Dim rgx As New Regex(pattern, RegexOptions.IgnoreCase, TimeSpan.FromSeconds(1))
        Dim sw As Stopwatch = Nothing

        Dim inputs() As String = {"aa", "aaaa>",
                                   "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
                                   "aaaaaaaaaaaaaaaaaaaaaa>",
                                   "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>"}

        For Each inputValue In inputs
            Console.WriteLine("Processing {0}", inputValue)
            Dim timedOut As Boolean = False
            Do
                Try
                    sw = Stopwatch.StartNew()
                    ' Display the result.
                    If rgx.IsMatch(inputValue) Then
                        sw.Stop()
                        Console.WriteLine("Valid: '{0}' ({1:ss\.fffffff} seconds)",
                                          inputValue, sw.Elapsed)
                    Else
                        sw.Stop()
                        Console.WriteLine("'{0}' is not a valid string. ({1:ss\.fffff} seconds)",
                                          inputValue, sw.Elapsed)
                    End If
                Catch e As RegexMatchTimeoutException
                    sw.Stop()
                    ' Display the elapsed time until the exception.
                    Console.WriteLine("Timeout with '{0}' after {1:ss\.fffff}",
                                      inputValue, sw.Elapsed)
                    Thread.Sleep(1500)       ' Pause for 1.5 seconds.

                    ' Increase the timeout interval and retry.
                    Dim timeout As TimeSpan = e.MatchTimeout.Add(TimeSpan.FromSeconds(1))
                    If timeout.TotalSeconds > MaxTimeoutInSeconds Then
                        Console.WriteLine("Maximum timeout interval of {0} seconds exceeded.",
                                          MaxTimeoutInSeconds)
                        timedOut = False
                    Else
                        Console.WriteLine("Changing the timeout interval to {0}",
                                          timeout)
                        rgx = New Regex(pattern, RegexOptions.IgnoreCase, timeout)
                        timedOut = True
                    End If
                End Try
            Loop While timedOut
            Console.WriteLine()
        Next
    End Sub
End Module
' The example displays output like the following:
'    Processing aa
'    Valid: 'aa' (00.0000779 seconds)
'    
'    Processing aaaa>
'    'aaaa>' is not a valid string. (00.00005 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
'    Valid: 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (00.0000043 seconds)
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 01.00469
'    Changing the timeout interval to 00:00:02
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 02.01202
'    Changing the timeout interval to 00:00:03
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaa>' after 03.01043
'    Maximum timeout interval of 3 seconds exceeded.
'    
'    Processing aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>
'    Timeout with 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa>' after 03.01018
'    Maximum timeout interval of 3 seconds exceeded.

Gruppi atomici

L'elemento del linguaggio (?>sottoespressione) è un raggruppamento atomico. Impedisce il backtracking nella sottoespressione. Dopo che questo elemento del linguaggio è stato confrontato correttamente, non rinuncia ad alcuna parte della corrispondenza con il backtracking successivo. Ad esempio, se nel modello (?>\w*\d*)1 non è possibile trovare corrispondenze per 1, \d* non rinuncia ad alcuna corrispondenza, anche se ciò significa che si consente una corrispondenza corretta per 1. I gruppi atomici consentono di evitare i problemi di prestazioni associati a corrispondenze non riuscite.

Nell'esempio seguente vengono illustrati i miglioramenti nelle prestazioni con i quantificatori annidati quando non si utilizza il backtracking. Viene calcolato il tempo impiegato dal motore delle espressioni regolari per determinare che una stringa di input non corrisponde a due espressioni regolari. La prima espressione regolare utilizza il backtracking per tentare di trovare una corrispondenza con una stringa contenente una o più occorrenze di una o più cifre esadecimali seguite da due punti, seguiti da una o più cifre esadecimali, seguite da un doppio due punti. La seconda espressione regolare è identica alla prima, con la differenza che il backtracking è disabilitato. Come illustrato nell'output dell'esempio, il miglioramento delle prestazioni derivante dalla disabilitazione del backtracking è significativo.

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example4
{
    public static void Run()
    {
        string input = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:";
        bool matched;
        Stopwatch sw;

        Console.WriteLine("With backtracking:");
        string backPattern = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$";
        sw = Stopwatch.StartNew();
        matched = Regex.IsMatch(input, backPattern);
        sw.Stop();
        Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed);
        Console.WriteLine();

        Console.WriteLine("Without backtracking:");
        string noBackPattern = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$";
        sw = Stopwatch.StartNew();
        matched = Regex.IsMatch(input, noBackPattern);
        sw.Stop();
        Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed);
    }
}
// The example displays output like the following:
//       With backtracking:
//       Match: False in 00:00:27.4282019
//
//       Without backtracking:
//       Match: False in 00:00:00.0001391

Imports System.Text.RegularExpressions

Module Example4
    Public Sub Run()
        Dim input As String = "b51:4:1DB:9EE1:5:27d60:f44:D4:cd:E:5:0A5:4a:D24:41Ad:"
        Dim matched As Boolean
        Dim sw As Stopwatch

        Console.WriteLine("With backtracking:")
        Dim backPattern As String = "^(([0-9a-fA-F]{1,4}:)*([0-9a-fA-F]{1,4}))*(::)$"
        sw = Stopwatch.StartNew()
        matched = Regex.IsMatch(input, backPattern)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, backPattern), sw.Elapsed)
        Console.WriteLine()

        Console.WriteLine("Without backtracking:")
        Dim noBackPattern As String = "^((?>[0-9a-fA-F]{1,4}:)*(?>[0-9a-fA-F]{1,4}))*(::)$"
        sw = Stopwatch.StartNew()
        matched = Regex.IsMatch(input, noBackPattern)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", Regex.IsMatch(input, noBackPattern), sw.Elapsed)
    End Sub
End Module
' The example displays the following output:
'       With backtracking:
'       Match: False in 00:00:27.4282019
'       
'       Without backtracking:
'       Match: False in 00:00:00.0001391

Asserzioni lookbehind

.NET include due elementi del linguaggio, (?<=sottoespressione) e (?<!sottoespressione), che trovano il carattere o i caratteri precedenti nella stringa di input. Entrambi gli elementi di linguaggio sono asserzioni di larghezza zero, ovvero determinano se il carattere o i caratteri che precedono immediatamente il carattere corrente possono essere trovati da una sottoespressione, senza avanzamento o backtracking.

(?<=sottoespressione) è un'asserzione lookbehind positiva, ovvero il carattere o i caratteri prima della posizione corrente devono corrispondere a sottoespressione. (?<!sottoespressione) è un'asserzione lookbehind negativa, ovvero il carattere o i caratteri prima della posizione corrente non devono corrispondere a sottoespressione. Le asserzioni lookbehind positive e negative sono entrambe particolarmente utili quando sottoespressione è un subset della sottoespressione precedente.

L'esempio seguente usa due modelli di espressione regolare equivalenti che convalidano il nome utente in un indirizzo di posta elettronica. Il primo modello è soggetto a una riduzione delle prestazioni a causa di un utilizzo eccessivo del backtracking. Il secondo modello modifica la prima espressione regolare sostituendo un quantificatore annidato con un'asserzione lookbehind positiva. Nell'output dell'esempio viene visualizzato il tempo di esecuzione del metodo Regex.IsMatch .

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example5
{
    public static void Run()
    {
        Stopwatch sw;
        string input = "test@contoso.com";
        bool result;

        string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed);

        string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed);
    }
}
// The example displays output similar to the following:
//       Match: True in 00:00:00.0017549
//       Match with Lookbehind: True in 00:00:00.0000659

Module Example5
    Public Sub Run()
        Dim sw As Stopwatch
        Dim input As String = "test@contoso.com"
        Dim result As Boolean

        Dim pattern As String = "^[0-9A-Z]([-.\w]*[0-9A-Z])?@"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed)

        Dim behindPattern As String = "^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed)
    End Sub
End Module
' The example displays output similar to the following:
'       Match: True in 00:00:00.0017549
'       Match with Lookbehind: True in 00:00:00.0000659

Il primo criterio di espressione regolare, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, è definito nel modo illustrato nella tabella seguente.

Modello	Descrizione
`^`	Inizia la ricerca della corrispondenza all'inizio della stringa.
`[0-9A-Z]`	Trova la corrispondenza di un carattere alfanumerico. Poiché il metodo Regex.IsMatch viene richiamato con l'opzione RegexOptions.IgnoreCase , il confronto non rileva la distinzione tra maiuscole e minuscole.
`[-.\w]*`	Trova la corrispondenza di zero, una o più occorrenze di un trattino, un punto o un carattere alfanumerico.
`[0-9A-Z]`	Trova la corrispondenza di un carattere alfanumerico.
`([-.\w][0-9A-Z])`	Trova la corrispondenza di zero o più occorrenze della combinazione di zero o più trattini, punti o caratteri alfanumerici seguiti da un carattere alfanumerico. Equivale al primo gruppo di acquisizione.
`@`	Trova la corrispondenza di una chiocciola ("@").

Il secondo criterio di espressione regolare, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, usa un'asserzione lookbehind positiva e viene definito come illustrato nella tabella seguente.

Modello	Descrizione
`^`	Inizia la ricerca della corrispondenza all'inizio della stringa.
`[0-9A-Z]`	Trova la corrispondenza di un carattere alfanumerico. Poiché il metodo Regex.IsMatch viene richiamato con l'opzione RegexOptions.IgnoreCase , il confronto non rileva la distinzione tra maiuscole e minuscole.
`[-.\w]*`	Trova la corrispondenza di zero o più occorrenze di un trattino, un punto o un carattere alfanumerico.
`(?<=[0-9A-Z])`	Esegue la ricerca dell'ultimo carattere corrispondente e continua la ricerca della corrispondenza se si tratta di un carattere alfanumerico. Si noti che i caratteri alfanumerici sono un subset del set costituito da punti, trattini e tutti i caratteri alfanumerici.
`@`	Trova la corrispondenza di una chiocciola ("@").

Asserzioni lookahead

.NET include due elementi di linguaggio, (?=sottoespressione) e (?!sottoespressione), che trovano il carattere o i caratteri successivi nella stringa di input. Entrambi gli elementi del linguaggio sono asserzioni di larghezza zero, ovvero determinano se il carattere o i caratteri che seguono immediatamente il carattere corrente possono essere trovati da sottoespressione, senza avanzamento o backtracking.

(?=sottoespressione) è un'asserzione lookahead positiva, ovvero il carattere o i caratteri dopo la posizione corrente devono corrispondere a sottoespressione. (?!sottoespressione) è un'asserzione lookahead negativa, ovvero il carattere o i caratteri dopo la posizione corrente non devono corrispondere a sottoespressione. Le asserzioni lookahead positive e negative sono entrambe particolarmente utili quando sottoespressione è un subset della sottoespressione successiva.

Nell'esempio seguente vengono utilizzati due modelli di espressione regolare equivalenti per verificare un nome di tipo completo. Il primo modello è soggetto a una riduzione delle prestazioni a causa di un utilizzo eccessivo del backtracking. Il secondo modello modifica la prima espressione regolare sostituendo un quantificatore annidato con un'asserzione lookahead positiva. Nell'output dell'esempio viene visualizzato il tempo di esecuzione del metodo Regex.IsMatch .

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

public class Example6
{
    public static void Run()
    {
        string input = "aaaaaaaaaaaaaaaaaaaaaa.";
        bool result;
        Stopwatch sw;

        string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine("{0} in {1}", result, sw.Elapsed);

        string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine("{0} in {1}", result, sw.Elapsed);
    }
}
// The example displays the following output:
//       False in 00:00:03.8003793
//       False in 00:00:00.0000866

Imports System.Text.RegularExpressions

Module Example6
    Public Sub Run()
        Dim input As String = "aaaaaaaaaaaaaaaaaaaaaa."
        Dim result As Boolean
        Dim sw As Stopwatch

        Dim pattern As String = "^(([A-Z]\w*)+\.)*[A-Z]\w*$"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("{0} in {1}", result, sw.Elapsed)

        Dim aheadPattern As String = "^((?=[A-Z])\w+\.)*[A-Z]\w*$"
        sw = Stopwatch.StartNew()
        result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase)
        sw.Stop()
        Console.WriteLine("{0} in {1}", result, sw.Elapsed)
    End Sub
End Module
' The example displays the following output:
'       False in 00:00:03.8003793
'       False in 00:00:00.0000866

Il primo criterio di espressione regolare, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, è definito nel modo illustrato nella tabella seguente.

Modello	Descrizione
`^`	Inizia la ricerca della corrispondenza all'inizio della stringa.
`([A-Z]\w*)+\.`	Trova la corrispondenza di un carattere alfabetico (A-Z) seguito da zero o più caratteri alfanumerici una o più volte seguiti da un punto. Poiché il metodo Regex.IsMatch viene richiamato con l'opzione RegexOptions.IgnoreCase , il confronto non rileva la distinzione tra maiuscole e minuscole.
`(([A-Z]\w)+\.)`	Trova la corrispondenza del modello precedente zero o più volte.
`[A-Z]\w*`	Trova la corrispondenza di un carattere alfabetico seguito da zero o più caratteri alfanumerici.
`$`	Termina la ricerca della corrispondenza alla fine della stringa di input.

Il secondo criterio di espressione regolare, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, usa un'asserzione lookahead positiva e viene definito come illustrato nella tabella seguente.

Modello	Descrizione
`^`	Inizia la ricerca della corrispondenza all'inizio della stringa.
`(?=[A-Z])`	Esegue la ricerca fino primo carattere e continua la ricerca della corrispondenza se si tratta di un carattere alfabetico (A-Z). Poiché il metodo Regex.IsMatch viene richiamato con l'opzione RegexOptions.IgnoreCase , il confronto non rileva la distinzione tra maiuscole e minuscole.
`\w+\.`	Trova la corrispondenza di uno o più caratteri alfanumerici seguiti da un punto.
`((?=[A-Z])\w+\.)*`	Trova la corrispondenza del modello di uno o più caratteri alfanumerici seguiti da un punto zero o più volte. Il carattere alfanumerico iniziale deve essere alfabetico.
`[A-Z]\w*`	Trova la corrispondenza di un carattere alfabetico seguito da zero o più caratteri alfanumerici.
`$`	Termina la ricerca della corrispondenza alla fine della stringa di input.

Considerazioni generali sulle prestazioni

I suggerimenti seguenti non mirano in modo specifico a evitare un backtracking eccessivo, ma possono contribuire ad aumentare le prestazioni dell'espressione regolare:

Precompilare modelli usati di frequente. Il modo migliore per eseguire questa operazione consiste nell'usare il generatore di origini delle espressioni regolari per la precompilazione. Se il generatore di origini non è disponibile per l'app, ad esempio non si ha come destinazione .NET 7 o versione successiva o non si conosce il modello in fase di compilazione, usare l'opzione RegexOptions.Compiled.
Memorizzare nella cache oggetti Regex usati di frequente. Ciò si verifica in modo implicito quando si usa il generatore di origini. In caso contrario, creare un oggetto Regex e archiviarlo per il riutilizzo, anziché usare i metodi Regex statici o creare e rimuovere un oggetto Regex.
Iniziare la corrispondenza da un offset. Se si è certi che le corrispondenze inizieranno sempre oltre un determinato offset nel modello, passare l'offset usando un overload come Regex.Match(String, Int32). In questo modo si ridurrà la quantità di testo che il motore deve prendere in considerazione.
Raccogliere solo le informazioni necessarie. Se è sufficiente sapere solo se si verifica una corrispondenza ma non dove si verifica la corrispondenza, preferire Regex.IsMatch. Se è sufficiente sapere quante volte viene rilevata una corrispondenza, preferire l'uso di Regex.Count. Se è sufficiente conoscere i limiti di una corrispondenza, ma non sono necessarie informazioni sulle acquisizioni di una corrispondenza, preferire l'uso di Regex.EnumerateMatches. È consigliabile ridurre al minimo la quantità di informazioni che il motore deve fornire.
Evitare acquisizioni non necessarie. Le parentesi nel modello formano un gruppo di acquisizione per impostazione predefinita. Se non sono necessarie acquisizioni, specificare RegexOptions.ExplicitCapture o usare invece gruppi non di acquisizione. In questo modo il motore non dovrà tenere traccia di tali acquisizioni.

Condividi tramite