Retroceso en expresiones regulares
El retroceso se produce cuando un patrón de expresión regular contiene cuantificadores o construcciones de alternancia opcionales y el motor de expresiones regulares vuelve a un estado guardado anterior para continuar la búsqueda de una coincidencia. El retroceso es fundamental para la eficacia de las expresiones regulares; permite que las expresiones sean eficaces y flexibles, y que coincidan con modelos muy complejos. Al mismo tiempo, esta eficacia tiene un costo. El retroceso suele ser el factor único más importante que afecta al rendimiento del motor de expresiones regulares. Afortunadamente, el desarrollador tiene control sobre el comportamiento del motor de expresiones regulares y cómo usa el retroceso. En este artículo se explica cómo funciona el retroceso y cómo puede controlarlo.
Advertencia
Cuando se usa System.Text.RegularExpressions para procesar entradas que no son de confianza, pase un tiempo de expiración. Un usuario malintencionado puede proporcionar entradas a RegularExpressions y provocar un ataque por denegación de servicio. Las API del marco ASP.NET Core en las que se usa RegularExpressions pasan un tiempo de expiración.
Comparación lineal sin retroceso
Si un patrón de expresión regular no tiene ningún cuantificador o construcción de alternancia opcional, el motor de expresiones regulares se ejecuta en tiempo lineal. Es decir, una vez que el motor de expresiones regulares hace coincidir el primer elemento de lenguaje del patrón con texto de la cadena de entrada, intenta buscar una coincidencia del siguiente elemento de lenguaje del patrón con el siguiente carácter o grupo de caracteres de la cadena de entrada. Este proceso continúa hasta que la coincidencia se realiza correctamente o se produce un error. En cualquier caso, el motor de expresiones regulares avanza de carácter en carácter por la cadena de entrada.
Esto se muestra en el ejemplo siguiente. La expresión regular e{2}\w\b busca dos apariciones de la letra "e" seguida de cualquier carácter alfabético seguido de un límite de palabras.
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
Aunque esta expresión regular incluye el cuantificador {2}, se evalúa de manera lineal. El motor de expresiones regulares no retrocede porque {2} no es un cuantificador opcional, ya que especifica un número exacto y no un número variable de veces que la subexpresión anterior debe coincidir. Como resultado, el motor de expresiones regulares intenta hacer coincidir el patrón de expresión regular con la cadena de entrada como se muestra en la tabla siguiente.
| Operación | Posición en el patrón | Posición en la cadena | Resultado |
|---|---|---|---|
| 1 | e | "needing a reed" (índice 0) | Ninguna coincidencia. |
| 2 | e | "eeding a reed" (índice 1) | Posible coincidencia. |
| 3 | e{2} | "eding a reed" (índice 2) | Posible coincidencia. |
| 4 | \w | "ding a reed" (índice 3) | Posible coincidencia. |
| 5 | \b | "ing a reed" (índice 4) | Error en posible coincidencia. |
| 6 | e | "eding a reed" (índice 2) | Posible coincidencia. |
| 7 | e{2} | "ding a reed" (índice 3) | Error en posible coincidencia. |
| 8 | e | "ding a reed" (índice 3) | Se produce un error de coincidencia. |
| 9 | e | "ing a reed" (índice 4) | Ninguna coincidencia. |
| 10 | e | "ng a reed" (índice 5) | Ninguna coincidencia. |
| 11 | e | "g a reed" (índice 6) | Ninguna coincidencia. |
| 12 | e | " a reed" (índice 7) | Ninguna coincidencia. |
| 13 | e | “a reed” (índice 8) | Ninguna coincidencia. |
| 14 | e | " reed" (índice 9) | Ninguna coincidencia. |
| 15 | e | “reed” (índice 10) | Ninguna coincidencia |
| 16 | e | "eed" (índice 11) | Posible coincidencia. |
| 17 | e{2} | "ed" (índice 12) | Posible coincidencia. |
| 18 | \w | "d" (índice 13) | Posible coincidencia. |
| 19 | \b | "" (índice 14) | Coincidencia. |
Si un patrón de expresión regular no incluye ningún cuantificador o construcción de alternancia opcional, el número máximo de comparaciones necesarias para hacer coincidir el patrón de expresión regular con la cadena de entrada es aproximadamente equivalente al número de caracteres de la cadena de entrada. En este caso, el motor de expresiones regulares usa 19 comparaciones para identificar posibles coincidencias en esta cadena de 13 caracteres. Es decir, el motor de expresiones regulares se ejecuta en tiempo prácticamente lineal si no contiene ningún cuantificador o construcción de alternancia opcional.
Retroceso con cuantificadores o construcciones de alternancia opcionales
Cuando una expresión regular incluye cuantificadores o construcciones de alternancia opcionales, la evaluación de la cadena de entrada ya no es lineal. La coincidencia de modelos con un motor autómata finito no determinista (NFA) está controlada por los elementos del lenguaje de la expresión regular y no por los caracteres que se hacen coincidir en la cadena de entrada. Por tanto, el motor de expresiones regulares intenta hacer coincidir totalmente subexpresiones opcionales o alternativas. Cuando avanza al elemento de lenguaje siguiente de la subexpresión y la coincidencia no se realiza correctamente, el motor de expresiones regulares puede abandonar una parte de su coincidencia correcta y volver a un estado guardado anterior para hacer coincidir la expresión regular en su conjunto con la cadena de entrada. Este proceso de volver a un estado guardado anterior para encontrar una coincidencia se denomina retroceso.
Por ejemplo, considere el patrón de expresión regular .*(es), que hace coincidir los caracteres "es" y todos los caracteres que lo preceden. Como se muestra en el ejemplo siguiente, si la cadena de entrada es "Essential services are provided by regular expressions.", el patrón coincide con toda la cadena hasta e incluyendo "es" en "expressions".
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 ello, el motor de expresiones regulares usa el retroceso de la manera siguiente:
Coincide con
.*(que coincide con cero, una o más apariciones de cualquier carácter) con la cadena de entrada completa.Intenta hacer coincidir "e" en el patrón de expresión regular. Sin embargo, la cadena de entrada no tiene ningún carácter restante disponible para coincidir.
Retrocede hasta su última coincidencia correcta, "Essential services are provided by regular expressions", e intenta hacer coincidir "e" con el punto del final de la frase. Se produce un error de coincidencia.
Sigue retrocediendo hasta una coincidencia correcta anterior, de carácter en carácter, hasta que la subcadena coincidente tentativa sea "Essential services are provided by regular expr". A continuación, compara la "e" del patrón con la segunda "e" de "expressions" y encuentra una coincidencia.
Compara la "s" del patrón con la "s" que sigue al carácter "e" coincidente (la primera "s" de "expressions"). La coincidencia es correcta.
Cuando se usa retroceso, la coincidencia del patrón de expresión regular con la cadena de entrada, que tiene 55 caracteres de longitud, necesita 67 operaciones de comparación. Normalmente, si un patrón de expresión regular tiene una única construcción de alternancia o un único cuantificador opcional, el número de operaciones de comparación necesarias para que coincida con el patrón es más del doble del número de caracteres de la cadena de entrada.
Retroceso con cuantificadores opcionales anidados
El número de operaciones de comparación necesarias para coincidir con un patrón de expresión regular puede aumentar exponencial si el patrón incluye muchas construcciones de alternancia, si incluye construcciones de alternancia anidadas o, lo que es más frecuente, si incluye cuantificadores opcionales anidados. Por ejemplo, el patrón de expresión regular ^(a+)+$ está diseñado para coincidir con una cadena completa que contiene uno o más caracteres "a". El ejemplo proporciona dos cadenas de entrada de longitud idéntica, pero solo la primera cadena coincide con el patrón. La clase System.Diagnostics.Stopwatch se usa para determinar cuánto tiempo tarda la operación de coincidencia.
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 muestra el resultado del ejemplo, el motor de expresiones regulares tardó mucho más tiempo en descubrir que una cadena de entrada no coincidía con el patrón que en identificar una cadena coincidente. Esto se debe a que una coincidencia infructuosa siempre representa un escenario de caso peor. El motor de expresiones regulares debe usar la expresión regular para seguir todas las rutas posibles a través de los datos antes de poder concluir que la coincidencia no es correcta y los paréntesis anidados crean muchas rutas de acceso adicionales a través de los datos. El motor de expresiones regulares concluye que la segunda cadena no coincide con el patrón; para ello, hace lo siguiente:
Comprueba que está al principio de la cadena y, a continuación, busca una coincidencia de los cinco primeros caracteres de la cadena con el patrón
a+. A continuación, determina que no hay ningún grupo adicional de caracteres "a" en la cadena. Por último, comprueba que está al final de la cadena. Como en la cadena queda un carácter adicional, la coincidencia produce un error. Esta coincidencia errónea necesita 9 comparaciones. El motor de expresiones regulares también guarda información de estado de las coincidencias de "a" (que llamaremos coincidencia 1), "aa" (coincidencia 2), "aaa" (coincidencia 3) y "aaaa" (coincidencia 4).Vuelve a la coincidencia 4 guardada previamente. Determina que hay un carácter "a" adicional para asignar a un grupo capturado adicional. Por último, comprueba que está al final de la cadena. Como en la cadena queda un carácter adicional, la coincidencia produce un error. Esta coincidencia errónea necesita 4 comparaciones. Hasta ahora, se han realizado un total de 13 comparaciones.
Vuelve a la coincidencia 3 guardada previamente. Determina que hay dos caracteres "a" adicionales para asignar a un grupo capturado adicional. Sin embargo, se produce un error en la prueba de fin de cadena. Vuelva a la coincidencia 3 e intente hacer coincidir los dos caracteres "a" adicionales en dos grupos capturados adicionales. Se sigue produciendo un error en la prueba de fin de cadena. Estas coincidencias con error necesitan 12 comparaciones. Hasta ahora, se ha realizado un total de 25 comparaciones.
La comparación de la cadena de entrada con la expresión regular continúa de esta manera hasta que el motor de expresiones regulares ha intentado todas las posibles combinaciones de coincidencias y, a continuación, concluye que no hay ninguna coincidencia. Debido a los cuantificadores anidados, esta comparación es O(2n) o una operación exponencial, donde n es el número de caracteres de la cadena de entrada. Esto significa que, en el peor de los casos, una cadena de entrada de 30 caracteres necesita aproximadamente 1.073.741.824 comparaciones y una cadena de entrada de 40 caracteres necesita aproximadamente 1.099.511.627.776 comparaciones. Si usa cadenas de estas longitudes o incluso mayores, los métodos de expresión regular pueden tardar mucho tiempo en completarse cuando procesan datos de entrada que no coinciden con el patrón de expresión regular.
Control del retroceso
El retroceso permite crear expresiones regulares eficaces y flexibles. Sin embargo, como se ha mostrado en la sección anterior, estas ventajas pueden conllevar un bajo rendimiento inaceptable. Para evitar el retroceso excesivo, se debe definir un intervalo de tiempo de espera cuando se instancie un objeto Regex o se llame a un método estático de coincidencia de expresión regular. Esta técnica se analiza en la sección siguiente. Además, .NET admite tres elementos del lenguaje de expresiones regulares que limitan o suprimen la vuelta atrás (backtracking) y que admiten expresiones regulares complejas con poca o ninguna reducción del rendimiento: grupos atómicos, aserciones de búsqueda retrasada (lookbehind) y aserciones de búsqueda anticipada (lookahead). Para obtener más información sobre cada elemento del lenguaje, vea Construcciones de agrupamiento.
Motor de expresiones regulares de no vuelta atrás (backtracking)
Si no necesita usar construcciones que requieran vuelta atrás (backtracking) como por ejemplo, soluciones alternativas, referencias inversas o grupos atómicos, considere la posibilidad de usar el modo RegexOptions.NonBacktracking. Este modo está diseñado para ejecutarse con una duración proporcional a la longitud de la entrada. Para obtener más información, vea Modo de no vuelta atrás (backtracking). También puede establecer un valor de tiempo de espera.
Límite del tamaño de las entradas
Algunas expresiones regulares tienen un rendimiento aceptable a menos que la entrada sea excepcionalmente grande. Si se sabe que todas las entradas de texto razonables del escenario tienen una longitud determinada, considere la posibilidad de rechazar entradas más largas antes de aplicarles la expresión regular.
Especificación de un intervalo de tiempo de espera
Puede establecer un valor de tiempo de espera que represente el intervalo más largo durante el que el motor de expresiones regulares buscará una coincidencia única antes de abandonar el intento e iniciar una excepción RegexMatchTimeoutException. El intervalo de tiempo de espera se especifica al proporcionar un valor TimeSpan al constructor Regex(String, RegexOptions, TimeSpan) para las expresiones regulares de instancias. Además, cada método estático de coincidencia de patrones tiene una sobrecarga con un parámetro TimeSpan que permite especificar un valor de tiempo de espera.
Si no establece explícitamente un valor de tiempo de espera, el valor de tiempo de espera predeterminado se determina de la siguiente manera:
- Mediante el uso del valor de tiempo de espera de toda la aplicación, si existe uno. Puede ser cualquier valor de tiempo de espera que se aplique al dominio de aplicación en el que se cree una instancia del objeto Regex o se realice la llamada al método estático. Puede establecer el valor de tiempo de espera de toda la aplicación llamando al método AppDomain.SetData para asignar la representación de cadena de un valor TimeSpan a la propiedad
REGEX_DEFAULT_MATCH_TIMEOUT. - Mediante el uso del valor InfiniteMatchTimeout, si no se ha establecido ningún valor de tiempo de espera para toda la aplicación.
De forma predeterminada, el intervalo de tiempo de espera se establece en Regex.InfiniteMatchTimeout y el motor de expresiones regulares no agota dicho tiempo.
Importante
Cuando no se use RegexOptions.NonBacktracking, se recomienda establecer siempre un intervalo de tiempo de espera si la expresión regular se basa en la vuelta atrás (backtracking) o funciona en entradas que no son de confianza.
Una excepción RegexMatchTimeoutException indica que el motor de expresiones regulares no pudo encontrar una coincidencia en el intervalo de tiempo de espera especificado, pero no indica por qué se produjo la excepción. La razón puede ser un retroceso excesivo, aunque también es posible que el intervalo de tiempo de espera establecido fuera demasiado bajo, dada la carga del sistema en el momento en que se produjo la excepción. Cuando se controla la excepción, se puede elegir entre abandonar otras coincidencias con la cadena de entrada o incrementar el intervalo de tiempo de espera y reintentar la operación de coincidencia.
Por ejemplo, el código siguiente llama al constructor Regex(String, RegexOptions, TimeSpan) para crear instancias de un objeto Regex con un valor de tiempo de espera de un segundo. El patrón de expresión regular (a+)+$, que coincide con una o más secuencias de uno o varios caracteres "a" al final de una línea, está sujeto a un retroceso excesivo. Si se produce una excepción RegexMatchTimeoutException, el ejemplo incrementa el valor de tiempo de espera hasta un intervalo máximo de tres segundos. Después, abandona el intento de coincidir con el patrón.
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
El elemento del lenguaje (?>subexpresión) es una agrupación atómica. Evita la vuelta atrás (backtracking) en la subexpresión. Una vez que este elemento del lenguaje coincida correctamente, no cederá ninguna parte de su coincidencia a la vuelta atrás (backtracking) posterior. Por ejemplo, en el patrón (?>\w*\d*)1, si no se puede hacer coincidir 1, \d* no abandonará ninguna coincidencia, aunque esto signifique que permita que 1 coincida correctamente. Los grupos atómicos pueden ayudar a evitar los problemas de rendimiento asociados a las coincidencias con error.
En el ejemplo siguiente se muestra cómo la supresión del retroceso mejora el rendimiento cuando se usan cuantificadores anidados. Mide el tiempo necesario para que el motor de expresiones regulares determine que una cadena de entrada no coincide con dos expresiones regulares. La primera expresión regular usa el retroceso para intentar buscar una coincidencia de una cadena que contiene una o más apariciones de uno o más dígitos hexadecimales, seguidas de un signo de dos puntos, seguido de uno o más dígitos hexadecimales, seguido de dos signos de dos puntos. La segunda expresión regular es idéntica a la primera, salvo que deshabilita el retroceso. Como muestra el resultado del ejemplo, la mejora de rendimiento que supone deshabilitar el retroceso es 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
Aserciones de búsqueda tardía
.NET incluye dos elementos de lenguaje, (?<=subexpresión) y (?<!subexpresión), que buscan una coincidencia con el carácter o los caracteres anteriores de la cadena de entrada. Ambos elementos de lenguaje son aserciones de ancho cero, es decir, determinan si el carácter o los caracteres que preceden inmediatamente al carácter actual coinciden con subexpression, sin avanzar o retroceder.
(?<=subexpression) es una aserción de búsqueda retrasada (lookbehind) positiva, es decir, el carácter o los caracteres situados antes de la posición actual deben coincidir con subexpression. (?<!subexpression)es una aserción de búsqueda retrasada (lookbehind) negativa, es decir, el carácter o los caracteres situados antes de la posición actual no deben coincidir con subexpression. Tanto las aserciones de búsqueda tardía positivas como las negativas son más útiles cuando subexpression es un subconjunto de la subexpresión anterior.
En el ejemplo siguiente se usan dos patrones de expresiones regulares equivalentes que validan el nombre de usuario de una dirección de correo electrónico. El primer patrón tiene un rendimiento bajo debido a un retroceso excesivo. El segundo patrón modifica la primera expresión regular reemplazando un cuantificador anidado con una aserción de búsqueda tardía positiva. El resultado del ejemplo muestra el tiempo de ejecución del método Regex.IsMatch .
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example5
{
public static void Run()
{
Stopwatch sw;
string input = "test@contoso.com";
bool result;
string pattern = @"^[0-9A-Z]([-.\w]*[0-9A-Z])?@";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed);
string behindPattern = @"^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed);
}
}
// The example displays output similar to the following:
// Match: True in 00:00:00.0017549
// Match with Lookbehind: True in 00:00:00.0000659
Module Example5
Public Sub Run()
Dim sw As Stopwatch
Dim input As String = "test@contoso.com"
Dim result As Boolean
Dim pattern As String = "^[0-9A-Z]([-.\w]*[0-9A-Z])?@"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("Match: {0} in {1}", result, sw.Elapsed)
Dim behindPattern As String = "^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, behindPattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("Match with Lookbehind: {0} in {1}", result, sw.Elapsed)
End Sub
End Module
' The example displays output similar to the following:
' Match: True in 00:00:00.0017549
' Match with Lookbehind: True in 00:00:00.0000659
El primer patrón de expresión regular, ^[0-9A-Z]([-.\w]*[0-9A-Z])*@, se define como se muestra en la tabla siguiente.
| Patrón | Descripción |
|---|---|
^ |
Iniciar la búsqueda de coincidencias en el principio de la cadena. |
[0-9A-Z] |
Buscar coincidencias de un carácter alfanumérico. Esta comparación no distingue mayúsculas de minúsculas, ya que se llama al método Regex.IsMatch con la opción RegexOptions.IgnoreCase . |
[-.\w]* |
Buscar coincidencias con cero, una o más apariciones de un guión, un punto o un carácter alfabético. |
[0-9A-Z] |
Buscar coincidencias de un carácter alfanumérico. |
([-.\w]*[0-9A-Z])* |
Buscar coincidencias con cero o más apariciones de la combinación de cero o más guiones, puntos o caracteres alfabéticos, seguidos de un carácter alfanumérico. Este es el primer grupo de captura. |
@ |
Buscar coincidencias con una arroba ("@"). |
El segundo patrón de expresión regular, ^[0-9A-Z][-.\w]*(?<=[0-9A-Z])@, emplea una aserción de búsqueda tardía positiva. Se define como se muestra en la tabla siguiente.
| Modelo | Descripción |
|---|---|
^ |
Iniciar la búsqueda de coincidencias en el principio de la cadena. |
[0-9A-Z] |
Buscar coincidencias de un carácter alfanumérico. Esta comparación no distingue mayúsculas de minúsculas, ya que se llama al método Regex.IsMatch con la opción RegexOptions.IgnoreCase . |
[-.\w]* |
Buscar coincidencias con cero o más apariciones de un guión, un punto o un carácter alfabético. |
(?<=[0-9A-Z]) |
Volver a examinar el último carácter coincidente y continuar con la coincidencia si es alfanumérica. Tenga en cuenta que los caracteres alfanuméricos son un subconjunto del conjunto formado por puntos, guiones y todos los caracteres alfabéticos. |
@ |
Buscar coincidencias con una arroba ("@"). |
Aserciones de búsqueda anticipada
.NET incluye dos elementos de lenguaje, (?=subexpresión) y (?!subexpresión), que buscan una coincidencia con el carácter o los caracteres siguientes de la cadena de entrada. Ambos elementos de lenguaje son aserciones de ancho cero, es decir, determinan si el carácter o los caracteres que siguen inmediatamente al carácter actual coinciden con subexpression, sin avanzar o retroceder.
(?=subexpression) es una aserción de búsqueda anticipada (lookahead) positiva, es decir, el carácter o los caracteres situados después de la posición actual deben coincidir con subexpression. (?!subexpression) es una aserción de búsqueda anticipada (lookahead) negativa, es decir, el carácter o los caracteres situados después de la posición actual no deben coincidir con subexpression. Tanto las aserciones de búsqueda anticipada positivas como las negativas son más útiles cuando subexpression es un subconjunto de la siguiente subexpresión.
En el ejemplo siguiente se usan dos patrones de expresiones regulares que validan un nombre de tipo completo. El primer patrón tiene un rendimiento bajo debido a un retroceso excesivo. El segundo modifica la primera expresión regular reemplazando un cuantificador anidado con una aserción de búsqueda anticipada positiva. El resultado del ejemplo muestra el tiempo de ejecución del método Regex.IsMatch .
using System;
using System.Diagnostics;
using System.Text.RegularExpressions;
public class Example6
{
public static void Run()
{
string input = "aaaaaaaaaaaaaaaaaaaaaa.";
bool result;
Stopwatch sw;
string pattern = @"^(([A-Z]\w*)+\.)*[A-Z]\w*$";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("{0} in {1}", result, sw.Elapsed);
string aheadPattern = @"^((?=[A-Z])\w+\.)*[A-Z]\w*$";
sw = Stopwatch.StartNew();
result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase);
sw.Stop();
Console.WriteLine("{0} in {1}", result, sw.Elapsed);
}
}
// The example displays the following output:
// False in 00:00:03.8003793
// False in 00:00:00.0000866
Imports System.Text.RegularExpressions
Module Example6
Public Sub Run()
Dim input As String = "aaaaaaaaaaaaaaaaaaaaaa."
Dim result As Boolean
Dim sw As Stopwatch
Dim pattern As String = "^(([A-Z]\w*)+\.)*[A-Z]\w*$"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, pattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("{0} in {1}", result, sw.Elapsed)
Dim aheadPattern As String = "^((?=[A-Z])\w+\.)*[A-Z]\w*$"
sw = Stopwatch.StartNew()
result = Regex.IsMatch(input, aheadPattern, RegexOptions.IgnoreCase)
sw.Stop()
Console.WriteLine("{0} in {1}", result, sw.Elapsed)
End Sub
End Module
' The example displays the following output:
' False in 00:00:03.8003793
' False in 00:00:00.0000866
El primer patrón de expresión regular, ^(([A-Z]\w*)+\.)*[A-Z]\w*$, se define como se muestra en la tabla siguiente.
| Patrón | Descripción |
|---|---|
^ |
Iniciar la búsqueda de coincidencias en el principio de la cadena. |
([A-Z]\w*)+\. |
Buscar coincidencias con un carácter alfabético (A-Z) seguido de cero o más caracteres alfabéticos una o más veces, seguidas de un punto. Esta comparación no distingue mayúsculas de minúsculas, ya que se llama al método Regex.IsMatch con la opción RegexOptions.IgnoreCase . |
(([A-Z]\w*)+\.)* |
Buscar coincidencias con el patrón anterior cero o más veces. |
[A-Z]\w* |
Buscar coincidencias con un carácter alfabético seguido de cero o más caracteres alfabéticos. |
$ |
Finalizar la búsqueda de coincidencias al final de la cadena de entrada. |
El segundo patrón de expresión regular, ^((?=[A-Z])\w+\.)*[A-Z]\w*$, emplea una aserción de búsqueda anticipada positiva. Se define como se muestra en la tabla siguiente.
| Modelo | Descripción |
|---|---|
^ |
Iniciar la búsqueda de coincidencias en el principio de la cadena. |
(?=[A-Z]) |
Examinar hacia delante el primer carácter y continuar la búsqueda de coincidencias si es alfabético (A-Z). Esta comparación no distingue mayúsculas de minúsculas, ya que se llama al método Regex.IsMatch con la opción RegexOptions.IgnoreCase . |
\w+\. |
Buscar coincidencias con uno o más caracteres alfabéticos seguidos de un punto. |
((?=[A-Z])\w+\.)* |
Buscar coincidencias con el patrón de uno o varios caracteres alfabéticos seguidos de un punto una o varias veces. El carácter alfabético inicial debe ser alfabético. |
[A-Z]\w* |
Buscar coincidencias con un carácter alfabético seguido de cero o más caracteres alfabéticos. |
$ |
Finalizar la búsqueda de coincidencias al final de la cadena de entrada. |
Consideraciones generales de rendimiento
Las siguientes sugerencias no son específicas para evitar una vuelta atrás (backtracking) excesiva, pero pueden ayudar a aumentar el rendimiento de la expresión regular:
Precompile los patrones muy usados. La mejor manera de hacerlo consiste en usar el generador de código fuente de expresiones regulares para precompilarlo. Si el generador de código fuente no está disponible para la aplicación, por ejemplo, no tiene como destino .NET 7 o una versión posterior, o bien no conoce el patrón en tiempo de compilación, use la opción RegexOptions.Compiled.
Almacene en caché los objetos de expresión regular muy usados. Esto se produce de forma implícita cuando se usa el generador de código fuente. De lo contrario, cree un objeto de expresión regular y almacénelo para su reutilización, en lugar de usar los métodos de expresión regular estáticos, o bien crear y eliminar un objeto de expresión regular.
Comience a buscar coincidencias a partir de un desplazamiento. Si sabe que las coincidencias siempre comenzarán más allá de un determinado desplazamiento en el patrón, pase el desplazamiento en mediante una sobrecarga como Regex.Match(String, Int32). Esto reducirá la cantidad de texto que el motor debe tener en cuenta.
Recopile solo la información que necesite. Si solo necesita saber si se produce una coincidencia pero no dónde, es preferible usar Regex.IsMatch. Si solo necesita saber cuántas veces coincide algo, es preferible usar Regex.Count. Si solo necesita conocer los límites de una coincidencia, pero nada sobre las capturas de una coincidencia, es preferible usar Regex.EnumerateMatches. Cuanto menos información necesite proporcionar el motor, mejor.
Evite capturas innecesarias. De manera predeterminada, los paréntesis del patrón forman un grupo de captura. Si no necesita capturas, en su lugar especifique RegexOptions.ExplicitCapture o use grupos que no sean de captura. Esto evita que el motor tenga que realizar el seguimiento de esas capturas.
