Nawroty w wyrażeniach regularnych

Wycofywanie występuje, gdy wzorzec wyrażenia regularnego zawiera opcjonalne kwantyfikatory lub konstrukcje zmiany, a aparat wyrażeń regularnych powraca do poprzedniego zapisanego stanu, aby kontynuować wyszukiwanie dopasowania. Nawroty mają zasadnicze znaczenie dla możliwości wyrażeń regularnych; dzięki nim wyrażenia są wydajne i elastyczne oraz pozwalają dopasowywać bardzo złożone wzorce. Jednocześnie te możliwości są obciążone kosztami. Nawroty są często najważniejszym czynnikiem wpływającym na wydajność silnika wyrażeń regularnych. Na szczęście deweloper ma kontrolę nad zachowaniem silnika wyrażeń regularnych oraz nad tym, jak wykorzystuje on nawroty. W tym artykule wyjaśniono, jak działa wycofywanie i jak można go kontrolować.

Porównanie liniowe bez wycofywania

Jeśli wzorzec wyrażenia regularnego nie ma opcjonalnych kwantyfikatorów ani konstrukcji zmiany, aparat wyrażeń regularnych wykonuje go liniowo. Oznacza to, że gdy aparat wyrażeń regularnych znajdzie pierwszy element języka ze wzorca w tekście w ciągu wejściowym, próbuje dopasować następny element języka ze wzorca do następnego znaku lub grupy znaków w ciągu wejściowym. Trwa to, dopóki dopasowanie nie zakończy się powodzeniem albo niepowodzeniem. W obu przypadkach silnik wyrażeń regularnych przesuwa się o jeden znak naraz w łańcuchu wejściowym.

Poniższy przykład stanowi ilustrację. Wyrażenie regularne e{2}\w\b wyszukuje dwa wystąpienia litery „e”, po których następuje dowolny znak słowa, a następnie granica słowa.

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($"{match.Value} found at position {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

Mimo że to wyrażenie regularne zawiera kwantyfikator {2}, jest obliczane liniowo. Silnik wyrażeń regularnych nie wykonuje powrotów, ponieważ {2} nie jest kwantyfikatorem opcjonalnym; określa dokładną liczbę wystąpień, a nie zmienną liczbę, z jaką poprzednie podwyrażenie musi pasować. W wyniku tego aparat wyrażeń regularnych próbuje dopasować wzorzec wyrażenia regularnego do ciągu wejściowego, tak jak pokazano w poniższej tabeli.

Jeśli wzorzec wyrażenia regularnego nie zawiera opcjonalnych kwantyfikatorów ani konstrukcji zmiany, maksymalna liczba porównań niezbędna do wykonania dopasowania wzorca wyrażenia regularnego do ciągu wejściowego jest w przybliżeniu równa liczbie znaków w ciągu wejściowym. W tym przypadku aparat wyrażeń regularnych wykonuje 19 porównań w celu zidentyfikowania możliwych dopasowań w 13-znakowy ciągu. Innymi słowy, silnik wyrażeń regularnych działa w czasie bliskim liniowemu, jeśli nie zawiera opcjonalnych kwantyfikatorów ani konstrukcji alternatywy.

Nawroty z opcjonalnymi kwantyfikatorami lub konstrukcjami alternatywy

Gdy wyrażenie regularne zawiera opcjonalne kwantyfikatory lub konstrukcje zmiany, obliczenia wykonywane na ciągu wejściowym nie są już liniowe. Dopasowywanie wzorca za pomocą silnika niedeterministycznego automatu skończonego (NFA) jest determinowane przez elementy języka użyte w wyrażeniu regularnym, a nie przez znaki w ciągu wejściowym, które mają zostać dopasowane. Dlatego aparat wyrażeń regularnych próbuje w pełni dopasować opcjonalne lub alternatywne podwyrażenia. Gdy mechanizm wyrażeń regularnych przechodzi do następnego elementu języka w podwyrażeniu i dopasowanie się nie powiedzie, może porzucić część udanego dopasowania i powrócić do wcześniej zapisanego stanu, aby spróbować dopasować wyrażenie regularne jako całość do ciągu wejściowego. Ten proces wracania do poprzednio zapisanego stanu w celu znalezienia dopasowania jest nazywany wycofywaniem.

Rozważmy na przykład wzorzec .*(es)wyrażenia regularnego, który odpowiada znakom "es" i wszystkim znakom poprzedzającym go. W poniższym przykładzie pokazano, że jeśli ciągiem wejściowym jest ciąg „Essential services are provided by regular expressions.”, wzorzec dopasowuje cały ciąg aż do znaków „es” w wyrazie „expressions” włącznie.

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

W tym celu mechanizm wyrażeń regularnych stosuje nawroty w następujący sposób:

• Dopasowuje wyrażenie .* (które odpowiada zeru, jednemu lub większej liczbie wystąpień dowolnego znaku) do całego ciągu wejściowego.

• Podejmuje próbę dopasowania symbolu „e” we wzorcu wyrażenia regularnego. Jednak ciąg wejściowy nie zawiera już znaków, z którymi można by wykonać porównanie.

• Mechanizm wycofuje się do ostatniego pomyślnego dopasowania, „Essential services are provided by regular expressions”, i próbuje dopasować literę „e” do kropki „.” na końcu zdania. Dopasowanie nie powiodło się.

• Mechanizm nadal cofa się do poprzedniego udanego dopasowania, po jednym znaku na raz, aż tymczasowo dopasowany podciąg przyjmie postać „Essential services are provided by regular expr”. Następnie porównuje znak „e” we wzorcu z drugą literą „e” w wyrazie „expressions” i znajduje dopasowanie.

• Porównuje znak „s” we wzorcu ze znakiem „s” następującym po dopasowanym znaku „e” (pierwszy znak „s” w słowie „expressions”). Dopasowanie zakończyło się powodzeniem.

Gdy jest używane wycofywanie, wykonanie dopasowania wzorca wyrażenia regularnego do ciągu wejściowego składającego się z 55 znaków wymaga wykonania 67 operacji porównania. Ogólnie, jeśli wzorzec wyrażenia regularnego zawiera jedną konstrukcję zmiany lub jeden opcjonalny kwantyfikator, liczba operacji porównania wymaganych do wykonania dopasowania wzorca jest ponad dwa razy większa niż liczba znaków w ciągu wejściowym.

Nawracanie z użyciem zagnieżdżonych opcjonalnych kwantyfikatorów

Liczba operacji porównania wymaganych do wykonania dopasowania wzorca wyrażenia regularnego rośnie wykładniczo, gdy wzorzec zawiera dużą liczbę konstrukcji zmiany, jeśli zawiera zagnieżdżone konstrukcje zmiany lub, co występuje najczęściej, zawiera zagnieżdżone kwantyfikatory opcjonalne. Na przykład wzorzec wyrażenia regularnego ^(a+)+$ służy do dopasowywania całego ciągu zawierającego co najmniej jeden znak „a”. W przykładzie podano dwa ciągi wejściowe o identycznej długości, ale tylko pierwszy ciąg pasuje do wzorca. Klasa System.Diagnostics.Stopwatch służy do określania, jak długo trwa operacja dopasowania.

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

Jak pokazują wyniki przykładu, mechanizm wyrażeń regularnych potrzebował znacznie więcej czasu, aby stwierdzić, że ciąg wejściowy nie pasował do wzorca, niż aby zidentyfikować pasujący ciąg. Dzieje się tak, ponieważ nieudane dopasowanie zawsze oznacza najgorszy możliwy scenariusz. Silnik wyrażeń regularnych musi użyć tego wyrażenia regularnego, aby prześledzić wszystkie możliwe ścieżki w danych, zanim będzie mógł stwierdzić, że dopasowanie zakończyło się niepowodzeniem, a zagnieżdżone nawiasy tworzą w danych wiele dodatkowych ścieżek. Aparat wyrażeń regularnych dochodzi do wniosku, że drugi ciąg nie pasuje do wzorca, wykonując następujące czynności:

• Sprawdza, czy znajduje się na początku ciągu, a następnie dopasowuje pierwszych pięć znaków ciągu do wzorca a+. Następnie ustala, że w ciągu nie znajdują się dodatkowe grupy liter „a”. Na końcu sprawdza, czy to koniec ciągu. Ponieważ w łańcuchu pozostaje jeden dodatkowy znak, dopasowanie się nie powiedzie. To nieudane dopasowanie wymaga wykonania 9 porównań. Silnik wyrażeń regularnych zapisuje również informacje o stanie dotyczące dopasowań „a” (które będziemy nazywać dopasowaniem 1), „aa” (dopasowanie 2), „aaa” (dopasowanie 3) i „aaaa” (dopasowanie 4).

• Aparat powraca do uprzednio zapisanego dopasowania 4. Ustala, że istnieje jeden dodatkowy znak „a”, który można przypisać do dodatkowej przechwyconej grupy. Na końcu sprawdza, czy to koniec ciągu. Ponieważ w łańcuchu pozostaje jeden dodatkowy znak, dopasowanie się nie powiedzie. To nieudane dopasowanie wymaga 4 porównań. Do tego momentu zostało wykonanych 13 porównań.

• Powraca do poprzednio zapisanego poziomu match-3. Ustala, że istnieją dwa dodatkowe znaki „a”, które można przypisać do dodatkowej przechwyconej grupy. Jednak test końca ciągu kończy się niepowodzeniem. Następnie wraca do trzeciego dopasowania i próbuje dopasować dwa dodatkowe znaki „a” w dwóch kolejnych przechwyconych grupach. Test końca ciągu nadal kończy się niepowodzeniem. Te nieudane dopasowania wymagały wykonania 12 porównań. Do tej pory wykonano łącznie 25 porównań.

Porównywanie ciągu wejściowego z wyrażeniem regularnym w ten sposób będzie kontynuowane, dopóki aparat wyrażeń regularnych nie wypróbuje wszystkich możliwych kombinacji dopasowań, a następnie uzna, że nie istnieje dopasowanie. Ze względu na zagnieżdżone kwantyfikatory, to porównanie jest operacją O(2ⁿ) lub operacją wykładniczą, gdzie n jest liczbą znaków w ciągu wejściowym. Oznacza to, że w najgorszym przypadku ciąg wejściowy o długości 30 znaków będzie wymagał wykonania ok. 1 073 741 824 porównań, a ciąg wejściowy o długości 40 znaków będzie wymagał wykonania ok. 1 099 511 627 776 porównań. Gdy są używane ciągi o takiej lub większej długości, wykonanie metod opartych na wyrażeniach regularnych może trwać niezwykle długo, jeśli w przetwarzanych ciągach nie będą znajdować się dopasowania do wzorca wyrażenia regularnego.

Kontrolowanie wycofywania

Nawroty umożliwiają tworzenie potężnych, elastycznych wyrażeń regularnych. Jednak, tak jak pokazano w poprzedniej sekcji, ich zalety może przesłonić nieakceptowalnie niska wydajność. Aby zapobiec nadmiernym nawrotom, należy zdefiniować limit czasu podczas tworzenia obiektu Regex lub podczas wywoływania statycznej metody dopasowywania wyrażeń regularnych. Ta czynność została omówiona w następnej sekcji. Ponadto platforma .NET obsługuje trzy elementy języka wyrażeń regularnych, które ograniczają lub eliminują nawroty i umożliwiają stosowanie złożonych wyrażeń regularnych przy niewielkim lub zerowym spadku wydajności: grupy atomowe, asercje wsteczne i asercje wyprzedzające. Aby uzyskać więcej informacji na temat każdego elementu języka, zobacz Konstrukcje grupowania.

Silnik wyrażeń regularnych niewykonujący cofania

Jeśli nie musisz używać żadnych konstrukcji wymagających wstecznego śledzenia (na przykład spojrzeń wprzód i wstecz, odwołań wstecznych lub grup atomowych), rozważ użycie trybu RegexOptions.NonBacktracking. Ten tryb jest przeznaczony do wykonywania w czasie proporcjonalnym do długości danych wejściowych. Aby uzyskać więcej informacji, zobacz tryb bez wycofywania. Można również ustawić wartość limitu czasu.

Ograniczanie rozmiaru danych wejściowych

Niektóre wyrażenia regularne mają akceptowalną wydajność, chyba że dane wejściowe są wyjątkowo duże. Jeśli wiadomo, że wszystkie sensowne dane wejściowe tekstowe w danym scenariuszu nie przekraczają określonej długości, rozważ odrzucanie dłuższych danych wejściowych przed zastosowaniem do nich wyrażenia regularnego.

Określ limit czasu

Możesz ustawić wartość limitu czasu określającą maksymalny czas, przez jaki aparat wyrażeń regularnych będzie szukał pojedynczego dopasowania, zanim porzuci próbę i zgłosi wyjątek RegexMatchTimeoutException. Limit czasu określasz, przekazując wartość TimeSpan do konstruktora Regex(String, RegexOptions, TimeSpan) dla instancji wyrażeń regularnych. Ponadto każda metoda dopasowania wzorca statycznego ma przeciążenie z parametrem TimeSpan , który umożliwia określenie wartości limitu czasu.

Jeśli jawnie nie ustawisz wartości limitu czasu, domyślna wartość limitu czasu zostanie określona w następujący sposób:

• Za pomocą wartości limitu czasu obowiązującej dla całej aplikacji, jeśli taka istnieje. Może to być dowolna wartość limitu czasu obowiązująca w domenie aplikacji, w której tworzona jest instancja obiektu Regex lub wywoływana jest metoda statyczna. Możesz ustawić wartość limitu czasu dla całej aplikacji, wywołując AppDomain.SetData metodę w celu przypisania reprezentacji TimeSpan ciągu wartości do REGEX_DEFAULT_MATCH_TIMEOUT właściwości.
• Używając wartości InfiniteMatchTimeout, jeśli nie ustawiono wartości limitu czasu dla całej aplikacji.

Domyślnie limit czasu jest ustawiony na Regex.InfiniteMatchTimeout, a mechanizm wyrażeń regularnych nie jest ograniczany limitem czasu.

Wyjątek RegexMatchTimeoutException wskazuje, że aparat wyrażeń regularnych nie może odnaleźć dopasowania w określonym interwale limitu czasu, ale nie wskazuje, dlaczego wyjątek został zgłoszony. Przyczyną może być nadmierne cofanie, ale możliwe jest również, że limit czasu ustawiono na zbyt niską wartość, biorąc pod uwagę obciążenie systemu w chwili zgłoszenia wyjątku. Podczas obsługi tego wyjątku można określić, że nie mają być wykonywane kolejne porównania z ciągiem wejściowym, albo zwiększyć interwał limitu czasu i ponowić próbę wykonania operacji dopasowywania.

Na przykład, poniższy kod wywołuje konstruktor Regex(String, RegexOptions, TimeSpan), aby utworzyć obiekt Regex z limitem czasu wynoszącym 1 sekundę. Wzorzec wyrażenia regularnego (a+)+$, który dopasowuje jedną lub większą liczbę sekwencji złożonych z co najmniej jednego znaku „a” na końcu wiersza, powoduje nadmierne cofanie. Jeśli zostanie zgłoszony wyjątek RegexMatchTimeoutException, w przykładzie wartość limitu czasu jest zwiększana maksymalnie do 3 sekund. Następnie porzuca próbę dopasowania do wzorca.

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 {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 {MaxTimeoutInSeconds} seconds exceeded.");
                        timedOut = false;
                    }
                    else
                    {
                        Console.WriteLine($"Changing the timeout interval to {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.

Grupy atomowe

Element języka (?>podwyrażenie) to grupowanie atomowe. Zapobiega to nawracaniu do podwyrażenia. Po pomyślnym dopasowaniu ten element składni nie odda żadnej części swojego dopasowania podczas późniejszego wycofywania. Na przykład we wzorcu (?>\w*\d*)1, jeśli nie można dopasować 1, to \d* nie odda żadnej części swojego dopasowania, nawet jeśli oznacza to, że 1 mogłoby zostać pomyślnie dopasowane. Grupy atomowe mogą pomóc zapobiegać problemom z wydajnością związanym z nieudanymi dopasowaniami.

Poniższy przykład ilustruje, jak wyłączenie mechanizmu nawrotów poprawia wydajność podczas używania zagnieżdżonych kwantyfikatorów. Mierzony jest czas potrzebny aparatowi wyrażeń regularnych na ustalenie, że ciąg wejściowy nie pasuje do dwóch wyrażeń regularnych. Pierwsze wyrażenie regularne wykorzystuje mechanizm wycofywania, aby dopasować ciąg zawierający co najmniej jedno wystąpienie co najmniej jednej cyfry szesnastkowej, po której następuje dwukropek, następnie co najmniej jedna cyfra szesnastkowa, po której następują dwa dwukropki. Drugie wyrażenie regularne jest identyczne z pierwszym, z tą różnicą, że wyłącza mechanizm nawrotów. Jak pokazuje wynik przykładu, poprawa wydajności wynikająca z wyłączenia wycofywania jest znacząca.

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: {Regex.IsMatch(input, backPattern)} in {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: {Regex.IsMatch(input, noBackPattern)} in {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

Asercje wsteczne

Platforma .NET zawiera dwa elementy języka, (?<=podwyrażenie) oraz (?<!podwyrażenie), które odpowiadają poprzedniemu znakowi lub znakom w ciągu wejściowym. Oba elementy języka są asercją o zerowej szerokości; oznacza to, że określają, czy znak lub znaki, które bezpośrednio poprzedzają bieżący znak, można dopasować przez podwyrażenie, bez przechodzenia lub wycofywania.

(?<= podwyrażenie) jest pozytywną asercją lookbehind; to znaczy znak lub znaki przed bieżącą pozycją muszą pasować do podwyrażenia. (?<! podwyrażenie) jest negatywną asercją lookbehind; oznacza to, że znak lub znaki przed bieżącym położeniem nie mogą być zgodne z podwyrażeniem. Zarówno pozytywne, jak i negatywne asercje lookbehind są najbardziej przydatne, gdy podwyrażenie jest podzbiorem poprzedniego podwyrażenia.

W poniższym przykładzie użyto dwóch równoważnych wzorców wyrażeń regularnych, które weryfikują nazwę użytkownika na adresie e-mail. Pierwszy wzorzec działa z niską wydajnością z powodu nadmiernego wycofywania. Drugi wzorzec modyfikuje pierwsze wyrażenie regularne, zastępując zagnieżdżony kwantyfikator pozytywną asercją wsteczną. Dane wyjściowe przykładu wyświetlają czas wykonywania metody 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: {result} in {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: {result} in {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

Pierwszy wzorzec wyrażenia regularnego , ^[0-9A-Z]([-.\w]*[0-9A-Z])*@jest zdefiniowany, jak pokazano w poniższej tabeli.

Drugi wzorzec wyrażenia regularnego, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, używa pozytywnego sprawdzenia wstecz. Definicję tego wyrażenia pokazano w poniższej tabeli.

Asercje wybiegające wprzód

Platforma .NET zawiera dwa elementy języka, (?=podwyrażenie) i (?!podwyrażenie), które dopasowują następny znak lub znaki w ciągu wejściowym. Oba elementy języka są asercją o zerowej szerokości; oznacza to, że określają, czy znak lub znaki, które natychmiast podążają za bieżącym znakiem, mogą być dopasowywane przez podwyrażenie, bez przechodzenia lub wycofywania.

(?= podwyrażenie) jest pozytywną asercją lookahead; oznacza to, że znak lub znaki po bieżącej pozycji muszą odpowiadać elementowi podwyrażenie. (?! podwyrażenie) jest negatywną asercją wyprzedzającą; oznacza to, że znak lub znaki po bieżącym położeniu nie mogą być zgodne z podwyrażeniem. Zarówno dodatnie, jak i negatywne asercje lookahead są najbardziej przydatne, gdy podwyrażenie jest podzbiorem następnego podwyrażenia.

W poniższym przykładzie są używane dwa równoważne wzorce wyrażenia regularnego sprawdzające w pełni kwalifikowaną nazwę typu. Pierwszy wzorzec działa z niską wydajnością z powodu nadmiernego wycofywania. Drugi wzorzec modyfikuje pierwsze wyrażenie regularne, zastępując zagnieżdżony kwantyfikator pozytywną asercją wyprzedzającą. Dane wyjściowe przykładu wyświetlają czas wykonywania metody 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($"{result} in {sw.Elapsed}");

        string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
        sw = Stopwatch.StartNew();
        result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
        sw.Stop();
        Console.WriteLine($"{result} in {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

Pierwszy wzorzec wyrażenia regularnego , ^(([A-Z]\w*)+\.)*[A-Z]\w*$jest zdefiniowany, jak pokazano w poniższej tabeli.

Drugi wzorzec wyrażenia regularnego, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, wykorzystuje asercję pozytywnego wyprzedzenia. Definicję tego wyrażenia pokazano w poniższej tabeli.

Ogólne zagadnienia dotyczące wydajności

Poniższe sugestie nie służą konkretnie zapobieganiu nadmiernemu cofaniu, ale mogą pomóc poprawić wydajność wyrażenia regularnego:

1. Wstępnie kompiluj mocno używane wzorce. Najlepszym sposobem, aby to zrobić, jest użycie generatora źródła wyrażeń regularnych, aby wstępnie go skompilować. Jeśli generator źródłowy nie jest dostępny dla Twojej aplikacji, na przykład Twoja aplikacja nie jest przeznaczona dla platformy .NET 7 lub nowszej albo nie znasz wzorca w czasie kompilacji, użyj opcji RegexOptions.Compiled.

2. Buforuj często używane obiekty wyrażeń regularnych. Dzieje się tak niejawnie, gdy używasz generatora źródłowego. W przeciwnym razie utwórz obiekt regex i zapisz go do ponownego użycia, zamiast używać statycznych metod wyrażeń regularnych lub tworzenia i wyrzucania obiektu Regex.

3. Rozpocznij dopasowanie od przesunięcia. Jeśli wiesz, że dopasowania zawsze będą zaczynać się od pewnego przesunięcia we wzorcu, przekaż to przesunięcie za pomocą przeciążenia, takiego jak Regex.Match(String, Int32). Spowoduje to zmniejszenie ilości tekstu, który aparat musi wziąć pod uwagę.

4. Zbierz tylko potrzebne informacje. Jeśli chcesz jedynie wiedzieć, czy występuje dopasowanie, ale nie miejsce jego wystąpienia, wybierz Regex.IsMatch. Jeśli musisz tylko wiedzieć, ile razy coś pasuje, preferuj użycie polecenia Regex.Count. Jeśli musisz tylko znać granice dopasowania, ale nie cokolwiek w przypadku przechwytywania dopasowania, preferuj użycie polecenia Regex.EnumerateMatches. Tym mniej informacji aparat musi zapewnić, tym lepiej.

5. Unikaj niepotrzebnych przechwyceń. Nawiasy w wzorcu tworzą domyślnie grupę przechwytywania. Jeśli nie potrzebujesz przechwytywania, określ RegexOptions.ExplicitCapture lub zamiast tego użyj grup nieprzechwytujących. Dzięki temu silnik nie musi śledzić tych przechwyceń.

Zobacz też

• Wyrażenia regularne platformy .NET
• Język wyrażeń regularnych — podręczny wykaz
• Kwantyfikatory
• Konstrukcje alternatywy
• Konstrukcje grupujące