Sekali lagi tentang regexps, backtracking dan bagaimana Anda dapat menempatkan dua baris kode "tidak berbahaya" pada pisau JVM

Pagi-pagi sekali, secangkir kopi kesepuluh, usaha yang gagal untuk memahami mengapa aplikasi java klien Anda (atau bahkan lebih buruk - server) mati suri saat menghitung regexp sederhana pada baris kecil ... Jika situasi serupa telah terjadi dalam hidup Anda , Anda mungkin sudah tahu tentang kemunduran dan sisi gelap ekspresi reguler. Sisanya - selamat datang di bawah potongan!

Mundur, atau harapan abadi akan hasilnya

(, , ), . – "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.