Retrocesso em expressões regulares

O backtracking ocorre quando um padrão de expressão regular contém quantificadores opcionais ou construções de alternância, e o motor de expressões regulares volta a um estado anterior guardado para continuar a procura de uma correspondência. O mecanismo de retrocesso está no cerne da capacidade das expressões regulares; permite que sejam poderosas e flexíveis e que correspondam a padrões muito complexos. Ao mesmo tempo, este poder tem um custo. O backtracking é muitas vezes o fator mais importante que afeta o desempenho do mecanismo de expressão regular. Felizmente, o programador pode controlar o comportamento do motor de expressões regulares e a forma como este utiliza retrocesso. Este artigo explica como funciona o backtracking e como você pode controlá-lo.

Comparação linear sem retrocesso

Se um padrão de expressão regular não tiver quantificadores opcionais ou construções de alternância, o mecanismo de expressão regular será executado em tempo linear. Ou seja, depois que o mecanismo de expressão regular faz a correspondência entre o primeiro elemento de idioma no padrão e o texto na cadeia de caracteres de entrada, ele tenta fazer a correspondência entre o próximo elemento de idioma no padrão e o próximo caractere ou grupo de caracteres na cadeia de caracteres de entrada. Isso continua até que a partida seja bem-sucedida ou falhe. Em ambos os casos, o mecanismo de expressão regular avança um caractere de cada vez na cadeia de caracteres de entrada.

O exemplo a seguir fornece uma ilustração. A expressão regular e{2}\w\b procura duas ocorrências da letra «e», seguidas de qualquer carácter alfanumérico e de uma fronteira de palavra.

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

Embora esta expressão regular inclua o quantificador {2}, ela é avaliada de forma linear. O mecanismo de expressão regular não retrocede porque {2} não é um quantificador opcional, ele especifica um número exato e não um número variável de vezes que a subexpressão anterior deve corresponder. Como resultado, o mecanismo de expressão regular tenta corresponder o padrão de expressão regular com a cadeia de caracteres de entrada, conforme mostrado na tabela a seguir.

Se um padrão de expressão regular não incluir quantificadores opcionais ou construções de alternância, o número máximo de comparações necessárias para corresponder ao padrão de expressão regular com a cadeia de entrada será aproximadamente equivalente ao número de caracteres na cadeia de caracteres de entrada. Nesse caso, o mecanismo de expressão regular usa 19 comparações para identificar possíveis correspondências nessa cadeia de caracteres de 13 caracteres. Em outras palavras, o mecanismo de expressão regular é executado em tempo quase linear se não contiver quantificadores opcionais ou construções de alternância.

Retrocesso com quantificadores opcionais ou construções de alternância

Quando uma expressão regular inclui quantificadores opcionais ou construções de alternância, a avaliação da cadeia de entrada não é mais linear. A correspondência de padrões com um mecanismo de autômato finito não determinístico (NFA) é conduzida pelos elementos de linguagem na expressão regular e não pelos caracteres a serem correspondidos na cadeia de caracteres de entrada. Portanto, o mecanismo de expressão regular tenta corresponder totalmente às subexpressões opcionais ou alternativas. Quando ele avança para o próximo elemento de idioma na subexpressão e a correspondência não é bem-sucedida, o mecanismo de expressão regular pode abandonar uma parte de sua correspondência bem-sucedida e retornar a um estado salvo anteriormente no interesse de corresponder a expressão regular como um todo com a cadeia de caracteres de entrada. Esse processo de retornar a um estado salvo anteriormente para encontrar uma correspondência é conhecido como backtracking.

Por exemplo, considere o padrão .*(es)de expressão regular , que corresponde aos caracteres "es" e todos os caracteres que o precedem. Como mostra o exemplo a seguir, se a cadeia de caracteres de entrada for "Serviços essenciais são fornecidos por expressões regulares.", o padrão corresponderá a toda a cadeia de caracteres até e incluindo o "es" em "expressões".

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

Para fazer isso, o mecanismo de expressão regular recorre a backtracking da seguinte maneira:

• Corresponde a .* (que corresponde a zero, uma ou mais ocorrências de qualquer caráter) em toda a cadeia de caracteres de entrada.

• Ele tenta corresponder a "e" no padrão de expressão regular. No entanto, a string de entrada já não contém caracteres disponíveis para corresponder.

• Ele recua para sua última partida bem-sucedida, "Serviços essenciais são fornecidos por expressões regulares", e tenta combinar "e" com o período no final da frase. A partida falha.

• Ele continua a retroceder para uma correspondência anterior bem-sucedida, um caractere de cada vez, até que a substring provisoriamente correspondida seja "Serviços essenciais são fornecidos por expr regular". Em seguida, compara o "e" no padrão com o segundo "e" em "expressões" e encontra uma correspondência.

• Ele compara "s" no padrão com o "s" que segue o caractere "e" correspondente (o primeiro "s" em "expressões"). A partida foi bem-sucedida.

Quando você usa backtracking, a correspondência do padrão de expressão regular com a cadeia de caracteres de entrada, que tem 55 caracteres, requer 67 operações de comparação. Geralmente, se um padrão de expressão regular tiver uma única construção de alternância ou um único quantificador opcional, o número de operações de comparação necessárias para corresponder ao padrão será mais de duas vezes o número de caracteres na cadeia de caracteres de entrada.

Retrospetiva com quantificadores opcionais aninhados

O número de operações de comparação necessárias para corresponder a um padrão de expressão regular pode aumentar exponencialmente se o padrão incluir um grande número de construções de alternância, se incluir construções de alternância aninhadas ou, mais comumente, se incluir quantificadores opcionais aninhados. Por exemplo, o padrão ^(a+)+$ de expressão regular é projetado para corresponder a uma cadeia de caracteres completa que contém um ou mais caracteres "a". O exemplo fornece duas cadeias de caracteres de entrada de comprimento idêntico, mas apenas a primeira cadeia de caracteres corresponde ao padrão. A classe System.Diagnostics.Stopwatch é usada para determinar quanto tempo demora a operação de correspondência.

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

Como mostra a saída do exemplo, o mecanismo de expressão regular levou significativamente mais tempo para descobrir que uma cadeia de caracteres de entrada não correspondia ao padrão como fazia para identificar uma cadeia de caracteres correspondente. Isso ocorre porque uma partida malsucedida sempre representa o pior cenário. O mecanismo de expressões regulares tem de usar a expressão regular para seguir todos os caminhos possíveis nos dados antes de poder concluir que a correspondência falhou, e os parênteses aninhados criam muitos caminhos adicionais nos dados. O mecanismo de expressão regular conclui que a segunda cadeia de caracteres não correspondeu ao padrão fazendo o seguinte:

• Ele verifica se estava no início da cadeia de caracteres e, em seguida, faz a correspondência entre os cinco primeiros caracteres da cadeia de caracteres e o padrão a+. Em seguida, determina que não há grupos adicionais de caracteres "a" na cadeia de caracteres. Finalmente, verifica o fim da cadeia de caracteres. Como um caractere adicional permanece na cadeia de caracteres, a correspondência falha. Esta partida falhada requer 9 comparações. O motor de expressões regulares também guarda informações de estado relativas às suas correspondências de "a" (a que chamaremos correspondência 1), "aa" (correspondência 2), "aaa" (correspondência 3) e "aaaa" (correspondência 4).

• Volta à partida 4 guardada anteriormente. Ele determina que há um caractere "a" adicional para atribuir a um grupo capturado adicional. Por fim, verifica o fim da cadeia de caracteres. Como um caractere adicional permanece na cadeia de caracteres, a correspondência falha. Esta partida falhou requer 4 comparações. Até agora, foram realizadas 13 comparações.

• Regressa à partida 3 anteriormente guardada. Ele determina que há dois caracteres "a" adicionais para atribuir a um grupo capturado adicional. No entanto, o teste de fim de cadeia de caracteres falha. Em seguida, ele retorna para a correspondência 3 e tenta corresponder os dois caracteres "a" adicionais em dois grupos capturados adicionais. O teste de fim de cadeia de caracteres ainda falha. Estas partidas falhadas requerem 12 comparações. Até agora, foram realizadas 25 comparações.

A comparação da cadeia de caracteres de entrada com a expressão regular continua dessa maneira até que o mecanismo de expressão regular tenha tentado todas as combinações possíveis de correspondências e, em seguida, conclua que não há correspondência. Devido aos quantificadores aninhados, essa comparação é uma operação O(2ⁿ) ou exponencial, onde n é o número de caracteres na cadeia de entrada. Isso significa que, na pior das hipóteses, uma sequência de entrada de 30 caracteres requer aproximadamente 1.073.741.824 comparações, e uma sequência de entrada de 40 caracteres requer aproximadamente 1.099.511.627.776 comparações. Se você usar cadeias de caracteres desses ou de comprimentos ainda maiores, os métodos de expressão regular podem levar um tempo extremamente longo para serem concluídos quando processam entradas que não correspondem ao padrão de expressão regular.

Controlo de backtracking

O backtracking permite criar expressões regulares poderosas e flexíveis. No entanto, como a secção anterior demonstrou, estes benefícios podem estar associados a um desempenho inaceitavelmente fraco. Para evitar retrocesso excessivo, você deve definir um intervalo de tempo limite ao instanciar um Regex objeto ou chamar um método de correspondência de expressão regular estática. Isso é discutido na próxima seção. Além disso, o .NET suporta três elementos da linguagem de expressões regulares que limitam ou suprimem o retrocesso e suportam expressões regulares complexas com pouca ou nenhuma penalização no desempenho: grupos atómicos, asserções retrospetivas e asserções prospetivas. Para obter mais informações sobre cada elemento de linguagem, consulte Agrupando construções.

Mecanismo de expressão regular sem retrocesso

Se você não precisar usar nenhuma construção que exija backtracking (por exemplo, lookarounds, backreferences ou grupos atômicos), considere usar o RegexOptions.NonBacktracking modo. Este modo é projetado para executar em tempo proporcional ao comprimento da entrada. Para obter mais informações, consulte o modo NonBacktracking. Você também pode definir um valor de tempo limite.

Limitar o tamanho das entradas

Algumas expressões regulares têm um desempenho aceitável, a menos que a entrada seja excepcionalmente grande. Se souber que, no seu cenário, todas as entradas de texto razoáveis têm um comprimento inferior a um determinado valor, considere rejeitar as entradas mais longas antes de lhes aplicar a expressão regular.

Especificar um intervalo de tempo limite

Pode definir um valor de limite de tempo que representa o intervalo máximo durante o qual o motor de expressões regulares tentará encontrar uma única correspondência antes de abandonar a tentativa e lançar a exceção RegexMatchTimeoutException. Especifica o intervalo de tempo de espera ao fornecer um valor TimeSpan ao construtor Regex(String, RegexOptions, TimeSpan) para instâncias de expressões regulares. Além disso, cada método estático de correspondência de padrões dispõe de uma sobrecarga com um parâmetro TimeSpan que lhe permite especificar um valor de limite de tempo.

Se você não definir um valor de tempo limite explicitamente, o valor de tempo limite padrão será determinado da seguinte maneira:

• Usando o valor de tempo limite em todo o aplicativo, se existir. Isso pode ser qualquer valor de tempo limite que se aplique ao domínio do aplicativo no qual o objeto é instanciado Regex ou a chamada de método estático é feita. Pode definir o valor global de tempo de espera da aplicação chamando o método AppDomain.SetData para atribuir a representação em cadeia de caracteres de um valor TimeSpan à propriedade REGEX_DEFAULT_MATCH_TIMEOUT.
• Usando o valor InfiniteMatchTimeout, se nenhum valor de tempo limite em todo o aplicativo tiver sido definido.

Por predefinição, o intervalo de expiração está definido como Regex.InfiniteMatchTimeout e o motor de expressões regulares não expira.

Uma RegexMatchTimeoutException exceção indica que o mecanismo de expressão regular não conseguiu encontrar uma correspondência dentro do intervalo de tempo limite especificado, mas não indica por que a exceção foi lançada. O motivo pode ser um retrocesso excessivo, mas também é possível que o tempo limite tenha sido definido com um valor demasiado baixo, tendo em conta a carga do sistema no momento em que a exceção foi gerada. Ao lidar com a exceção, você pode optar por abandonar outras correspondências com a cadeia de caracteres de entrada ou aumentar o intervalo de tempo limite e tentar novamente a operação correspondente.

Por exemplo, o código a seguir chama o Regex(String, RegexOptions, TimeSpan) construtor para instanciar um Regex objeto com um valor de tempo limite de 1 segundo. O padrão (a+)+$de expressão regular, que corresponde a uma ou mais sequências de um ou mais caracteres "a" no final de uma linha, está sujeito a retrocesso excessivo. Se um RegexMatchTimeoutException for lançado, o exemplo aumenta o valor de tempo limite até um intervalo máximo de 3 segundos. Depois disso, abandona a tentativa de corresponder ao padrão.

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.

Grupos atómicos

O (?>elemento de linguagem de subexpressão) é um agrupamento atômico. Evita o retrocesso na subexpressão. Uma vez que este elemento da linguagem tiver sido correspondido com êxito, não cederá nenhuma parte da correspondência ao retrocesso posterior. Por exemplo, no padrão (?>\w*\d*)1, se não for possível fazer corresponder 1, \d* não cederá nenhuma parte da sua correspondência, mesmo que isso permitisse que 1 correspondesse com êxito. Os grupos atômicos podem ajudar a evitar os problemas de desempenho associados a partidas com falha.

O exemplo a seguir ilustra como a supressão do backtracking melhora o desempenho ao usar quantificadores aninhados. Ele mede o tempo necessário para o mecanismo de expressão regular determinar que uma cadeia de caracteres de entrada não corresponde a duas expressões regulares. A primeira expressão regular usa retrocesso para tentar fazer corresponder uma cadeia de caracteres que contém uma ou mais ocorrências de um ou mais dígitos hexadecimais, seguidas de um carácter de dois-pontos, seguido de um ou mais dígitos hexadecimais, seguidos de dois caracteres de dois-pontos. A segunda expressão regular é idêntica à primeira, exceto que desativa o retrocesso. Como mostra o resultado do exemplo, a melhoria de desempenho resultante da desativação do backtracking é significativa.

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

Olhar por trás das asserções

O .NET inclui dois elementos de linguagem, (?<=subexpressão) e (?<!subexpressão), que correspondem ao carácter ou aos caracteres anteriores na cadeia de entrada. Ambos os elementos de linguagem são asserções de largura zero; ou seja, eles determinam se o caractere ou caracteres que precedem imediatamente o caractere atual podem ser correspondidos por subexpressão, sem avançar ou retroceder.

(?<= subexpressão) é uma asserção retrospetiva positiva; ou seja, o carácter ou caracteres antes da posição atual têm de corresponder à subexpressão. (?<! Subexpressão) é uma afirmação negativa, ou seja, o caractere ou caracteres antes da posição atual não devem corresponder à subexpressão. As asserções retrospetivas positivas e negativas são mais úteis quando subexpression é um subconjunto da subexpressão anterior.

O exemplo a seguir usa dois padrões de expressão regular equivalentes que validam o nome de usuário em um endereço de email. O primeiro padrão está sujeito a um desempenho fraco devido ao retrocesso excessivo. O segundo padrão modifica a expressão regular inicial, substituindo um quantificador aninhado por uma asserção retrospetiva positiva. A saída do exemplo exibe o tempo de execução do Regex.IsMatch método.

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

O primeiro padrão de expressão regular, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, é definido conforme mostrado na tabela a seguir.

O segundo padrão de expressão regular, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, usa uma asserção lookbehind positiva. É definido como mostrado na tabela a seguir.

Afirmações prospetivas

O .NET inclui dois elementos da linguagem, (?=subexpressão) e (?!subexpressão), que correspondem ao caráter ou aos carateres seguintes na cadeia de entrada. Ambos os elementos de linguagem são asserções de largura zero; ou seja, eles determinam se o caractere ou caracteres que seguem imediatamente o caractere atual podem ser correspondidos por subexpressão, sem avançar ou retroceder.

(?= A subexpressão) é uma afirmação de antecipação positiva, ou seja, o caractere ou caracteres após a posição atual devem corresponder à subexpressão. (?! subexpressão) é uma asserção de lookahead negativa; ou seja, o caráter ou os caracteres após a posição atual não devem corresponder a subexpressão. As asserções de lookahead positivas e negativas são mais úteis quando subexpressão é um subconjunto da subexpressão seguinte.

O exemplo a seguir usa dois padrões de expressão regular equivalentes que validam um nome de tipo totalmente qualificado. O primeiro padrão está sujeito a um desempenho fraco devido ao retrocesso excessivo. A segunda modifica a primeira expressão regular substituindo um quantificador aninhado por uma afirmação de antecipação positiva. A saída do exemplo exibe o tempo de execução do Regex.IsMatch método.

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

O primeiro padrão de expressão regular, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, é definido conforme mostrado na tabela a seguir.

O segundo padrão de expressão regular, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, usa uma asserção de antecipação positiva. É definido como mostrado na tabela a seguir.

Considerações gerais sobre desempenho

As sugestões a seguir não são especificamente para evitar retrocesso excessivo, mas podem ajudar a aumentar o desempenho de sua expressão regular:

1. Compile previamente os padrões frequentemente utilizados. A melhor maneira de o fazer é usar o gerador de código-fonte de expressão regular para o pré-compilar. Se o gerador de código-fonte não estiver disponível para a sua aplicação, por exemplo, se esta não tiver como destino o .NET 7 ou posterior, ou se não souber o padrão em tempo de compilação, utilize a opção RegexOptions.Compiled.

2. Coloque em cache objetos Regex muito utilizados. Isso ocorre implicitamente quando você está usando o gerador de código-fonte. Caso contrário, crie um objeto Regex e armazene-o para reutilização, em vez de usar os métodos Regex estáticos ou criar e jogar fora um objeto Regex.

3. Inicie a correspondência a partir de um deslocamento. Se você sabe que as correspondências sempre começarão além de um determinado deslocamento no padrão, passe o deslocamento usando uma sobrecarga como Regex.Match(String, Int32). Isso reduzirá a quantidade de texto que o mecanismo precisa considerar.

4. Reúna apenas as informações de que necessita. Se você só precisa saber se uma correspondência ocorre, mas não onde a correspondência ocorre, prefira Regex.IsMatch. Se só precisar de saber quantas vezes algo corresponde, prefira usar Regex.Count. Se você só precisa saber os limites de uma partida, mas não nada sobre as capturas de uma partida, prefira usar Regex.EnumerateMatcheso . Quanto menos informações o motor precisar fornecer, melhor.

5. Evite capturas desnecessárias. Os parênteses no seu padrão formam, por predefinição, um grupo de captura. Se não precisar de capturas, especifique RegexOptions.ExplicitCapture ou utilize grupos sem captura. Isto evita que o mecanismo tenha de manter o registo dessas capturas.

Consulte também

• Expressões regulares do .NET
• Linguagem de Expressão Regular - Referência Rápida
• Quantificadores
• Construções de alternância
• Construções de agrupamento