Adición de un solo carácter a mi .NET RegEx hace que se cuelgue

Question

Estos son los datos de entrada:

       *** INVOICE ***         

           THE BIKE SHOP        
         1 NEW ROAD, TOWNVILLE,      
          SOMEWHERE, UK, AB1 2CD       
         TEL-567890 

To: COUNTER SALE         No: 243529 Page: 1 

                Date: 04/06/10 12:00 

                Ref: Aiden 

Cust No: 010000     

Aquí es una expresión regular que funciona (Opciones: SingleLine, ignoreWhitespace, compilado) - de que coincide inmediatamente y el grupos estén correctamente pobladas:

\W+INVOICE\W+ 
(?<shopAddr>.*?)\W+ 
To:\W+(?<custAddr>.*?)\W+ 
No:\W+(?<invNo>\d+).*? 
Date:\W+(?<invDate>[0-9/ :]+)\W+ 
Ref:\W+(?<ref>[\w ]*?)\W+ 
Cust 

tan pronto como agrego la 'N' de Cust No en el rex, analizar la entrada cuelga siempre:

\W+INVOICE\W+ 
(?<shopAddr>.*?)\W+ 
To:\W+(?<custAddr>.*?)\W+ 
No:\W+(?<invNo>\d+).*? 
Date:\W+(?<invDate>[0-9/ :]+)\W+ 
Ref:\W+(?<ref>[\w ]*?)\W+ 
Cust N 

Si añado algo así como "cualquier carácter":

\W+INVOICE\W+ 
(?<shopAddr>.*?)\W+ 
To:\W+(?<custAddr>.*?)\W+ 
No:\W+(?<invNo>\d+).*? 
Date:\W+(?<invDate>[0-9/ :]+)\W+ 
Ref:\W+(?<ref>[\w ]*?)\W+ 
Cust . 

Funciona, pero tan pronto como agrego un carácter fijo, el rex se bloquea de nuevo:

\W+INVOICE\W+ 
(?<shopAddr>.*?)\W+ 
To:\W+(?<custAddr>.*?)\W+ 
No:\W+(?<invNo>\d+).*? 
Date:\W+(?<invDate>[0-9/ :]+)\W+ 
Ref:\W+(?<ref>[\w ]*?)\W+ 
Cust ..: 

¿Puede cualquier persona aconsejar qué añadir algo ¿tan trivial haría que se caiga? ¿Puedo habilitar algún tipo de rastreo para ver la actividad de coincidencia para ver si se está atascando en un retroceso catastrófico?

Answer 1

Con RegexOptions.IgnorePatternWhitespace, le está diciendo al motor que ignore los espacios en blanco en su patrón. Por lo tanto, cuando escribe Cust No en el patrón, realmente significa CustNo, que no coincide con la entrada. Esta es la causa del problema.

De the documentation:

Por defecto, el espacio en blanco en un patrón de expresión regular es significativa; fuerza al motor de expresión regular a hacer coincidir un carácter de espacio en blanco en la cadena de entrada. [...]

La opción RegexOptions.IgnorePatternWhitespace, o la opción x en línea, cambia este comportamiento predeterminado de la siguiente manera:

• espacio en blanco sin formato de escape en el patrón de expresión regular se ignora. Para formar parte de un patrón de expresión regular, los caracteres de espacio en blanco se deben escapar (por ejemplo, como \s o "\ ").

Así que en lugar de Cust No, en IgnorePatternWhitespace modo, debe escribir Cust\ No, porque de lo contrario se interpreta como CustNo.

Answer 2

polygenelubricants ya explicado por qué su expresión regular falló. La razón por la cual cuelga es que se está ejecutando en catastrophic backtracking. Su expresión regular tiene muchas partes que pueden coincidir con el mismo texto de muchas maneras diferentes. Si falla la coincidencia general, el motor de expresiones regulares probará todas las permutaciones posibles hasta que las agote o anule con un desbordamiento de pila.

E. g. en To:\W+(?<custAddr>.*?)\W+ el .*? gustosamente coincidirá con los mismos caracteres que \W, y como está utilizando Singleline, el .*? también se cruzará en la parte No:... del texto de entrada y más y más.En su ejemplo, probé en RegexBuddy qué sucede si agrega la "N" después de "Cust": el motor de expresiones regulares aborta después de 1,000,000 pasos.

Para evitar esto, es necesario hacer que la expresión regular más específica, o (esto podría ser la mejor opción en este caso) mantener el motor de expresiones regulares de marcha atrás encerrando las piezas que ya han emparejado en "atomic groups":

(?>\W+INVOICE\W+) 
(?>(?<shopAddr>.*?)\W+To:) 
(?>\W+(?<custAddr>.*?)\W+No:) 
(?>\W+(?<invNo>\d+).*?Date:) 
(?>\W+(?<invDate>[0-9/\ :]+)\W+Ref:) 
(?>\W+(?<ref>[\w\ ]*?)\W+Cust) 

Esto permite que la expresión regular falle mucho más rápido si la entrada y la expresión regular no encajan juntas.

Answer 3

Tim Pietzcker es realmente algo aquí cuando se trata de evitar retrocesos catastróficos. .NET tiene una característica que falta llamada "cuantificadores posesivos". Básicamente significa que la expresión regular será tan codiciosa como sea posible y no cederá nada cuando retroceda.

Por ejemplo, si coincidiera con la expresión [abc] + c en "abc", tendrá éxito. El [abc] + coincidirá primero con los tres caracteres, luego la c final fallará porque ha llegado al final de la línea. Eso causará un retroceso y una coincidencia simplemente "ab", lo que deja a la c para una coincidencia exitosa.

Donde si intentas hacer coincidir la expresión [abc] ++ c en "abc", fallará. El [abc] ++ coincidirá primero con los tres caracteres, luego la c final fallará porque ha llegado al final de la línea. Sin embargo, esta vez no habrá un retroceso debido al cuantificador posessivo (el signo más + +), y la expresión no coincidirá.

Tim Pietzcker ha señalado una alternativa al uso de un cuantificador posessive. Un grupo atómico puede mantener la expresión regular del retroceso catastrófico. Entonces para todos los propósitos prácticos, la expresión posesiva [abc] ++ c y la expresión atómica (?> [Abc] +) c son equivalentes.

Me has ahorrado mucho tiempo. Gracias.