Una vez más sobre expresiones regulares, retroceso y cómo puede poner dos líneas de código "inofensivo" en las hojas de JVM

Temprano en la mañana, la décima taza de café, intentos fallidos de comprender por qué la aplicación Java de su cliente (o peor aún, el servidor) está colgando mortalmente mientras calcula una expresión regular simple en una línea pequeña ... Si ya ha ocurrido una situación similar en su vida , probablemente ya sepa sobre el retroceso y el lado oscuro de las expresiones regulares. El resto, ¡bienvenido bajo el corte!

Retroceso o eterna expectativa del resultado

(, , ), . – "evil regexes" ( ):

@Test
public void testRegexJDK8Only() {
  final Pattern pattern = Pattern.compile("(0*)*1");
  Assert.assertFalse(pattern.matcher("0000000000000000000000000000000000000000").matches());
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

: * (" ") . , ?, +, {n} (n – ).

JDK8 ( – ), JVM matches(). , .

? Pattern/Matcher java.util.regex



:

1. * - , . , (0) , , , . .

   
   
   
   
   

2. (backtrack) . ; . (0) , , . .

   
   
   
   
   

3.   (0) . (0)! , , .

   
   
   
   
   

, "" (0), . ; – – , .

" ! ?" - . : , . , - , , 10 , . , :

@Test
public void testRegexAnyJDK() {
	final Pattern pattern = Pattern.compile("([A-Za-z,.!?]+( |\\-|\\')?){1,10}");
  Assert.assertFalse(pattern.matcher("scUojcUOWpBImlSBLxoCTfWxGPvaNhczGpvxsiqagxdHPNTTeqkoOeL3FlxKROMrMzJDf7rvgvSc72kQ").matches());
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

80 . JVM JDK8+ – 30 – , . - ReDoS-. , , , – "+" "{1,10}" – .

Java SDK?

, . , , . , . : JDK-5026912, JDK-7006761, JDK-8139263. StackOverflowError, (JDK-5050507). : " ", " ", " ". 

"" , . (, - ), API java.util.regex



JDK ( JDK-8234713, JDK-8054028, JDK-7178072). ; , " , , " (). 

. , JDK9 : , , , , . , , (JDK-6328855, ). testRegexJDK8Only()



jdk9-b119, JDK. , .

:

, , , ; , "" . , , npmjs.com. , , , , , . – , .

, , . , , . RE2, DFA - . ; – RE2 Rust, Google. JDK7+ RE2/J, C++ - .

2021 JEP-, , RE2.

RE2/J - ?

, RE2/J – . ?

• RE2/J API Matcher;

  
  
  
  
  

• ( RE2/J , – , backreferences). , ;

  
  
  
  
  

• , Google, , – .

  
  
  
  
  

• : " RE2/J . , , java.util.regex ".

  
  
  
  
  

, , : RE2/J – ; . , .

1. ReDoS.

   
   
   
   
   

2. , , , .

   
   
   
   
   

3. – , .

   
   
   
   
   

, , – , , RE2/J.