Regex tomando un tiempo sorprendentemente largo

Question

Tengo una cadena de búsqueda ingresada por un usuario. Normalmente, la cadena de búsqueda se divide utilizando espacios en blanco y luego se realiza una búsqueda OR (un elemento coincide si coincide con cualquiera de los elementos de la cadena de búsqueda). Deseo proporcionar algunas características de consulta "avanzadas", como la posibilidad de utilizar comillas para encerrar frases literales que contengan espacios en blanco.

Pensé que había creado una expresión regular decente para separar las cuerdas, pero me tomó un tiempo sorprendentemente largo en la ejecución (> 2 segundos en mi máquina). Lo encontré para averiguar dónde estaba el problema, y ​​lo que es más interesante parece que ocurre después de que coincida el último Match (presumiblemente, al final de la entrada). Todas las coincidencias hasta el final de la cadena coinciden en menos tiempo que luego puedo capturar, pero esa última coincidencia (si eso es lo que es, nada vuelve) toma casi todos los 2 segundos.

Esperaba que alguien pudiera tener alguna idea de cómo puedo acelerar esta expresión regular un poco. Sé que estoy usando un vistazo con un cuantificador ilimitado pero, como dije, esto no parece causar ningún problema de rendimiento hasta después de que se haya emparejado el último partido.

CÓDIGO

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Text.RegularExpressions; 

namespace RegexSandboxCSharp { 
    class Program { 
     static void Main(string[] args) { 

      string l_input1 = "# one \"two three\" four five:\"six seven\" eight \"nine ten\""; 

      string l_pattern = 
       @"(?<=^([^""]*([""][^""]*[""])?)*)\s+"; 

      Regex l_regex = new Regex(l_pattern); 

      MatchCollection l_matches = l_regex.Matches(l_input1); 
      System.Collections.IEnumerator l_matchEnumerator = l_matches.GetEnumerator(); 

      DateTime l_listStart = DateTime.Now; 
      List<string> l_elements = new List<string>(); 
      int l_previousIndex = 0; 
      int l_previousLength = 0; 
      //  The final MoveNext(), which returns false, takes 2 seconds. 
      while (l_matchEnumerator.MoveNext()) { 
       Match l_match = (Match) l_matchEnumerator.Current; 
       int l_start = l_previousIndex + l_previousLength; 
       int l_length = l_match.Index - l_start; 
       l_elements.Add(l_input1.Substring(l_start, l_length)); 

       l_previousIndex = l_match.Index; 
       l_previousLength = l_match.Length; 
      } 
      Console.WriteLine("List Composition Time: " + (DateTime.Now - l_listStart).TotalMilliseconds.ToString()); 

      string[] l_terms = l_elements.ToArray(); 

      Console.WriteLine(String.Join("\n", l_terms)); 

      Console.ReadKey(true); 

     } 
    } 
} 

SALIDA
(Esto es exactamente lo que estoy haciendo.)

uno
"dos tres "
cuatro
cinco:" seis siete"
ocho
"nueve diez"

Answer 1

trate de cambiar su expresión regular a lo siguiente:

(?<=^((?>[^"]*)(["][^"]*["])?)*)\s+ 

El único cambio aquí es ponga el [^"]* en un atomic group, que previene el catastrophic backtracking que ocurre.

Nota: la expresión regular anterior es, obviamente, no utilizar C sintaxis de cadena # expresiones regulares, que no estoy familiarizado con, pero yo creo que sería la siguiente:

@"(?<=^((?>[^""]*)([""][^""]*[""])?)*)\s+"; 

¿Por qué se produce el retroceso catastrófico:
Una vez que se han encontrado todas las coincidencias válidas, la próxima coincidencia que se intenta es el espacio dentro de la sección final citada. El lookbehind fallará porque hay un número impar de citas antes del espacio.

En este punto, la expresión regular dentro del lookbehind comenzará a retroceder. El ancla significa que siempre comenzará al principio de la cuerda, pero aún puede retroceder al soltar los elementos desde el final de la coincidencia.Veamos la expresión regular en el interior de la búsqueda hacia atrás:

^([^"]*(["][^"]*["])?)* 

Desde las secciones citadas son opcionales, se puede quitar como la expresión regular da marcha atrás. Para cada fragmento de caracteres sin comillas que no están dentro de una sección entre comillas, antes de retroceder cada carácter se habría emparejado como parte del [^"]* al comienzo de la expresión regular. A medida que retrocede en esa sección, el último carácter se eliminará de la coincidencia de [^"]*, y será recogido por la repetición externa. En este punto, se vuelve muy similar al ejemplo en el enlace de retroceso catastrófico anterior.