validate - Regex alfanumérico simple(espaciado simple) sin retroceso catastrófico
validate regex javascript (1)
Tengo la siguiente expresión REGEX (que funciona) para permitir Alpha-Numeric (así como
''
y
-
) y sin doble espacio:
^([a-zA-Z0-9''-]+/s?)*$
Debido a la agrupación anidada, esto permite que ocurra el Retroceso catastrófico, ¡lo cual es malo!
¿Cómo puedo simplificar esta expresión para evitar el retroceso catastrófico? (Idealmente, esto tampoco permitiría espacios en blanco en el primer y último carácter)
Explicación
El grupo anidado no causa automáticamente un retroceso catastrófico.
En su caso, es porque su expresión regular degenera en el ejemplo clásico de retroceso catastrófico
(a*)*
.
Como
/s
en opcional en
^([a-zA-Z0-9''-]+/s?)*$
, En la entrada sin espacios pero tiene caracteres fuera de la lista permitida, la expresión regular simplemente degenera en
^([a-zA-Z0-9''-]+)*$
.
También puede pensar en términos de expansión de la expresión regular original:
[a-zA-Z0-9''-]+/s?[a-zA-Z0-9''-]+/s?[a-zA-Z0-9''-]+/s?[a-zA-Z0-9''-]+/s?...
Como
/s
es opcional, podemos eliminarlo:
[a-zA-Z0-9''-]+[a-zA-Z0-9''-]+[a-zA-Z0-9''-]+[a-zA-Z0-9''-]+...
Y obtuvimos una serie de
[a-zA-Z0-9''-]+
consecutivos, que intentarán todas las formas de distribuir los personajes entre ellos y explotar la complejidad.
Solución
La forma estándar de escribir una expresión regular para que coincida con el
token delimiter token ... delimiter token
es
token (delimiter token)*
.
Si bien es posible reescribir la expresión regular para evitar repetir el
token
, recomendaría no hacerlo, ya que es más difícil hacerlo bien.
Para evitar la repetición, es posible que desee construir la expresión regular por concatenación de cadenas en su lugar.
Siguiendo la receta anterior:
^[a-zA-Z0-9''-]+(/s[a-zA-Z0-9''-]+)*$
Aunque puede ver la repetición en la repetición aquí, no hay retroceso catastrófico, ya que la expresión regular solo puede expandirse a:
[a-zA-Z0-9''-]+/s[a-zA-Z0-9''-]+/s[a-zA-Z0-9''-]+/s[a-zA-Z0-9''-]+...
Y
/s
[a-zA-Z0-9''-]
son mutuamente exclusivos: solo hay una forma de hacer coincidir cualquier cadena.