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 mecanismo de expressão regular retorna a um estado salvo anterior para continuar sua busca por uma correspondência. O retrocesso é fundamental para o poder das expressões regulares; torna possível que as expressões sejam poderosas e flexíveis e 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 desenvolvedor tem controle sobre o comportamento do mecanismo de expressão regular e como ele usa o backtracking. Este tópico explica como funciona o backtracking e como ele pode ser controlado.
Aviso
Ao usar System.Text.RegularExpressions para processar entradas não confiáveis, passe um tempo limite. Um usuário mal-intencionado pode fornecer entrada para RegularExpressionso , causando um ataque de Negação de Serviço. ASP.NET APIs da estrutura principal que usam RegularExpressions passar um tempo limite.
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 e{2}\w\b regular procura duas ocorrências da letra "e" seguida por qualquer caractere de palavra seguido por um limite 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("{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
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.
| Operação | Posição no padrão | Posição na cadeia de caracteres | Resultado |
|---|---|---|---|
| 1 | e | "necessitando de uma cana" (índice 0) | Sem correspondência. |
| 2 | e | "Eeding a Reeding" (índice 1) | Possível correspondência. |
| 3 | e{2} | "Eding a Reed" (índice 2) | Possível correspondência. |
| 4 | \w | "ding a reed" (índice 3) | Possível correspondência. |
| 5 | \b | "ing a reed" (índice 4) | Possível correspondência falha. |
| 6 | e | "Eding a Reed" (índice 2) | Possível correspondência. |
| 7 | e{2} | "ding a reed" (índice 3) | Possível correspondência falha. |
| 8 | e | "ding a reed" (índice 3) | A correspondência falha. |
| 9 | e | "ing a reed" (índice 4) | Sem correspondência. |
| 10 | e | "ng a caniço" (índice 5) | Sem correspondência. |
| 11 | e | "g a caniço" (índice 6) | Sem correspondência. |
| 12 | e | "a caniço" (índice 7) | Sem correspondência. |
| 13 | e | "A Reed" (índice 8) | Sem correspondência. |
| 14 | e | " caniço" (índice 9) | Sem correspondência. |
| 15 | e | "caniço" (índice 10) | Sem correspondência |
| 16 | e | "eed" (índice 11) | Possível correspondência. |
| 17 | e{2} | "ed" (índice 12) | Possível correspondência. |
| 18 | \w | "d" (índice 13) | Possível correspondência. |
| 19 | \b | "" (índice 14) | Correspondência. |
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("'{0}' found at position {1}",
m.Value, m.Index);
Console.WriteLine("'es' found at position {0}",
m.Groups[1].Index);
}
}
}
// 'Essential services are provided by regular expressions 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 expressions found at position 0
' 'es' found at position 47
Para fazer isso, o mecanismo de expressão regular usa backtracking da seguinte maneira:
Ele corresponde ao (que corresponde a
.*zero, uma ou mais ocorrências de qualquer caractere) com toda a cadeia de caracteres de entrada.Ele tenta corresponder a "e" no padrão de expressão regular. No entanto, a cadeia de caracteres de entrada não tem caracteres restantes disponíveis para correspondência.
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.
Retrocesso 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 System.Diagnostics.Stopwatch classe é usada para determinar quanto tempo leva 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ão regular deve usar a expressão regular para seguir todos os caminhos possíveis através dos dados antes de concluir que a correspondência não foi bem-sucedida e os parênteses aninhados criam muitos caminhos adicionais através dos 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, ele testa o final 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 mecanismo de expressão regular também salva informações de estado de suas correspondências de "a" (que chamaremos de correspondência 1), "aa" (partida 2), "aaa" (partida 3) e "aaaa" (partida 4).Regressa ao jogo 4 anteriormente guardado. Ele determina que há um caractere "a" adicional para atribuir a um grupo capturado adicional. Finalmente, ele testa o final 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 ao jogo 3 anteriormente guardado. 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(2n) 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.
Controle o backtracking
O retrocesso 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 oferece suporte a três elementos de linguagem de expressão regular que limitam ou suprimem o backtracking e que oferecem suporte a expressões regulares complexas com pouca ou nenhuma penalidade de desempenho: grupos atômicos, asserções lookbehind e asserções lookahead. 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 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 todas as entradas de texto razoáveis em seu cenário forem conhecidas por terem um determinado comprimento, considere rejeitar entradas mais longas antes de aplicar a expressão regular a elas.
Especificar um intervalo de tempo limite
Você pode definir um valor de tempo limite que represente o intervalo mais longo que o mecanismo de expressão regular procurará por uma única correspondência antes de abandonar a tentativa e lançar uma RegexMatchTimeoutException exceção. Você especifica o intervalo de tempo limite fornecendo um TimeSpan valor para o construtor, por exemplo, Regex(String, RegexOptions, TimeSpan) expressões regulares. Além disso, cada método de correspondência de padrão estático tem uma sobrecarga com um TimeSpan parâmetro que permite especificar um valor de tempo limite.
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. Você pode definir o valor de tempo limite em todo o aplicativo chamando o AppDomain.SetData método para atribuir a representação de cadeia de caracteres de um TimeSpan valor à propriedade "REGEX_DEFAULT_MATCH_TIMEOUT".
- Usando o valor InfiniteMatchTimeout, se nenhum valor de tempo limite em todo o aplicativo tiver sido definido.
Por padrão, o intervalo de tempo limite é definido como Regex.InfiniteMatchTimeout e o mecanismo de expressão regular não atinge o tempo limite.
Importante
Quando não estiver usando RegexOptions.NonBacktrackingo , recomendamos que você sempre defina um intervalo de tempo limite se sua expressão regular depender de retrocesso ou operar em entradas não confiáveis.
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 o retrocesso excessivo, mas também é possível que o intervalo de tempo limite tenha sido definido muito baixo, dada a carga do sistema no momento em que a exceção foi lançada. 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 {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.
Grupos atómicos
O (?>elemento de linguagem de subexpressão) é um agrupamento atômico. Evita o retrocesso na subexpressão. Uma vez que esse elemento de idioma tenha correspondido com sucesso, ele não desistirá de nenhuma parte de sua correspondência para o retrocesso subsequente. Por exemplo, no padrão (?>\w*\d*)1, se o 1 não puder ser correspondido, o \d* não desistirá de nenhuma de suas correspondências, mesmo que isso signifique que permitiria que a 1 correspondência fosse bem-sucedida. 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 backtracking para tentar corresponder a uma cadeia de caracteres que contém uma ou mais ocorrências de um ou mais dígitos hexadecimais, seguido por dois pontos, seguido por um ou mais dígitos hexadecimais, seguido por dois dois-pontos. A segunda expressão regular é idêntica à primeira, exceto que desativa o retrocesso. Como mostra a saída do exemplo, a melhoria de desempenho 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: {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
Olhar por trás das asserções
O .NET inclui dois elementos de linguagem, (?<=subexpressão) e(?<! subexpressão), que correspondem ao caractere ou caracteres anteriores na cadeia de caracteres 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.
(?<=A subexpressão) é uma afirmação positiva, ou seja, o caractere ou caracteres antes da posição atual devem 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 positivas e negativas são mais úteis quando a subexpressão é 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 primeira expressão regular substituindo um quantificador aninhado por uma asserção de lookbehind 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: {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
O primeiro padrão de expressão regular, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, é definido conforme mostrado na tabela a seguir.
| Padrão | Description |
|---|---|
^ |
Inicie a partida no início da string. |
[0-9A-Z] |
Corresponder a um caractere alfanumérico. Essa comparação não diferencia maiúsculas de minúsculas, porque o Regex.IsMatch método é chamado com a RegexOptions.IgnoreCase opção. |
[-.\w]* |
Corresponder zero, uma ou mais ocorrências de um hífen, ponto ou caractere de palavra. |
[0-9A-Z] |
Corresponder a um caractere alfanumérico. |
([-.\w]*[0-9A-Z])* |
Corresponder zero ou mais ocorrências da combinação de zero ou mais hífenes, pontos ou caracteres de palavra, seguidos por um caractere alfanumérico. Este é o primeiro grupo de captura. |
@ |
Corresponder a um sinal de arroba ("@"). |
O segundo padrão de expressão regular, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, usa uma asserção positiva por trás. É definido como mostrado na tabela a seguir.
| Padrão | Description |
|---|---|
^ |
Inicie a partida no início da string. |
[0-9A-Z] |
Corresponder a um caractere alfanumérico. Essa comparação não diferencia maiúsculas de minúsculas, porque o Regex.IsMatch método é chamado com a RegexOptions.IgnoreCase opção. |
[-.\w]* |
Corresponder a zero ou mais ocorrências de um hífen, ponto ou caractere de palavra. |
(?<=[0-9A-Z]) |
Olhe para trás para o último caractere correspondente e continue a correspondência se for alfanumérico. Observe que os caracteres alfanuméricos são um subconjunto do conjunto que consiste em pontos, hífenes e todos os caracteres de palavra. |
@ |
Corresponder a um sinal de arroba ("@"). |
Afirmações prospetivas
O .NET inclui dois elementos de linguagem, (?=subexpressão) e subexpressão), que correspondem ao próximo caractere (?!ou caracteres na cadeia de caracteres 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 afirmação negativa, ou seja, o caractere ou caracteres após a posição atual não devem corresponder à subexpressão. As asserções positivas e negativas são mais úteis quando a subexpressão é um subconjunto da próxima subexpressão.
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("{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
O primeiro padrão de expressão regular, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, é definido conforme mostrado na tabela a seguir.
| Padrão | Description |
|---|---|
^ |
Inicie a partida no início da string. |
([A-Z]\w*)+\. |
Corresponder a um caractere alfabético (A-Z) seguido por zero ou mais caracteres de palavra uma ou mais vezes, seguido por um ponto. Essa comparação não diferencia maiúsculas de minúsculas, porque o Regex.IsMatch método é chamado com a RegexOptions.IgnoreCase opção. |
(([A-Z]\w*)+\.)* |
Corresponder ao padrão anterior zero ou mais vezes. |
[A-Z]\w* |
Corresponder a um caractere alfabético seguido de zero ou mais caracteres de palavras. |
$ |
Termine a partida no final da cadeia de caracteres de entrada. |
O segundo padrão de expressão regular, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, usa uma asserção positiva de lookahead. É definido como mostrado na tabela a seguir.
| Padrão | Description |
|---|---|
^ |
Inicie a partida no início da string. |
(?=[A-Z]) |
Olhe para a frente para o primeiro caractere e continue a correspondência se for alfabética (A-Z). Essa comparação não diferencia maiúsculas de minúsculas, porque o Regex.IsMatch método é chamado com a RegexOptions.IgnoreCase opção. |
\w+\. |
Corresponder a um ou mais caracteres de palavras seguidos de um ponto. |
((?=[A-Z])\w+\.)* |
Corresponder ao padrão de um ou mais caracteres de palavras seguido por um ponto zero ou mais vezes. O caractere inicial da palavra deve ser alfabético. |
[A-Z]\w* |
Corresponder a um caractere alfabético seguido de zero ou mais caracteres de palavras. |
$ |
Termine a partida no final da cadeia de caracteres de entrada. |
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:
Pré-compile padrões muito usados. A melhor maneira de fazer isso é usar o gerador de fonte de expressão regular para pré-compilá-lo. Se o gerador de código-fonte não estiver disponível para seu aplicativo, por exemplo, você não estiver direcionando o .NET 7 ou posterior, ou não souber o padrão em tempo de compilação, use a RegexOptions.Compiled opção.
Armazene em cache objetos Regex muito usados. 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.
Comece a corresponder 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.
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 você só precisa saber quantas vezes algo combina, prefira usar Regex.Counto . 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.
Evite capturas desnecessárias. Parênteses em seu padrão formam um grupo de captura por padrão. Se você não precisar de capturas, especifique RegexOptions.ExplicitCapture ou use grupos que não sejam capturados. Isso evita que o motor acompanhe essas capturas.
Consulte também
Comentários
Brevemente: Ao longo de 2024, vamos descontinuar progressivamente o GitHub Issues como mecanismo de feedback para conteúdos e substituí-lo por um novo sistema de feedback. Para obter mais informações, veja: https://aka.ms/ContentUserFeedback.
Submeter e ver comentários