एक लंबे समय तक चलने वाले रेगेक्स मैच को रद्द करना?

Question

कहें कि मैं एक सेवा चला रहा हूं जहां उपयोगकर्ता बहुत सारे डेटा के माध्यम से खोजने के लिए रेगेक्स सबमिट कर सकते हैं। यदि उपयोगकर्ता एक रेगेक्स सबमिट करता है जो बहुत धीमा होता है (यानी Matcher.find() को वापस करने के लिए मिनट लगते हैं), तो मैं उस मैच को रद्द करने का एक तरीका चाहता हूं। ऐसा करने का एकमात्र तरीका यह है कि मैं एक और थ्रेड मॉनिटर रखना चाहता हूं कि एक मैच कितना समय ले रहा है और यदि आवश्यक हो तो इसे रद्द करने के लिए Thread.stop() का उपयोग करें।

सदस्य चर:

long REGEX_TIMEOUT = 30000L; 
Object lock = new Object(); 
boolean finished = false; 
Thread matcherThread; 

Matcher धागा:

try { 
    matcherThread = Thread.currentThread(); 

    // imagine code to start monitor thread is here 

    try { 
     matched = matcher.find(); 
    } finally { 
     synchronized (lock) { 
      finished = true; 
      lock.notifyAll(); 
     } 
    } 
} catch (ThreadDeath td) { 
    // send angry message to client 
    // handle error without rethrowing td 
} 

मॉनिटर धागा:

synchronized (lock) { 
    while (! finished) { 
     try { 
      lock.wait(REGEX_TIMEOUT); 

      if (! finished) { 
       matcherThread.stop(); 
      } 
     } catch (InterruptedException ex) { 
      // ignore, top level method in dedicated thread, etc.. 
     } 
    } 
} 

मैं java.sun.com/j2se/1.4.2/ पढ़ा है दस्तावेज़/गाइड/Misc/threadPrimitiveDeprecation.html और मुझे लगता है कि यह उपयोग सुरक्षित है क्योंकि मैं नियंत्रण कर रहा हूं जहां थ्रेडडिथ सिंक्रनाइज़ेशन और हेक्टेयर के माध्यम से फेंक दिया गया है इसे खोलें और केवल क्षतिग्रस्त वस्तुएं मेरे पैटर्न और मैचर उदाहरण हो सकती हैं जिन्हें वैसे भी त्याग दिया जाएगा। मुझे लगता है कि यह थ्रेड.स्टॉप() को तोड़ता है क्योंकि मैं त्रुटि को पुनर्स्थापित नहीं कर रहा हूं, लेकिन मैं वास्तव में धागे को मरना नहीं चाहता हूं, बस ढूंढें() विधि को रोक दें।

मैंने अब तक इन बहिष्कृत एपीआई घटकों का उपयोग करने से बचने में कामयाब रहा है, लेकिन Matcher.find() में व्यवधानिक प्रतीत नहीं होता है और इसे वापस करने में बहुत लंबा समय लग सकता है। क्या ऐसा करने का कोई बेहतर तरीका है?

Answer 1

Heritrix से: (crawler.archive.org)

/** 
* CharSequence that noticed thread interrupts -- as might be necessary 
* to recover from a loose regex on unexpected challenging input. 
* 
* @author gojomo 
*/ 
public class InterruptibleCharSequence implements CharSequence { 
    CharSequence inner; 
    // public long counter = 0; 

    public InterruptibleCharSequence(CharSequence inner) { 
     super(); 
     this.inner = inner; 
    } 

    public char charAt(int index) { 
     if (Thread.interrupted()) { // clears flag if set 
      throw new RuntimeException(new InterruptedException()); 
     } 
     // counter++; 
     return inner.charAt(index); 
    } 

    public int length() { 
     return inner.length(); 
    } 

    public CharSequence subSequence(int start, int end) { 
     return new InterruptibleCharSequence(inner.subSequence(start, end)); 
    } 

    @Override 
    public String toString() { 
     return inner.toString(); 
    } 
} 

इस एक के साथ अपने CharSequence लपेटें और थ्रेड बीच में आता है काम करेंगे ...

Answer 2

एक और वैकल्पिक हल, मिलान के region सीमित करने के लिए किया जाएगा तो find() फोन , तब तक दोहराया जाता है जब तक धागा बाधित नहीं होता है या एक मैच मिलता है।

Answer 3

एक छोटे से भिन्नता यह इस बात के लिए अतिरिक्त धागे का उपयोग कर से बचने के लिए संभव है

:

public class RegularExpressionUtils { 

    // demonstrates behavior for regular expression running into catastrophic backtracking for given input 
    public static void main(String[] args) { 
     Matcher matcher = createMatcherWithTimeout(
       "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx", "(x+x+)+y", 2000); 
     System.out.println(matcher.matches()); 
    } 

    public static Matcher createMatcherWithTimeout(String stringToMatch, String regularExpression, int timeoutMillis) { 
     Pattern pattern = Pattern.compile(regularExpression); 
     return createMatcherWithTimeout(stringToMatch, pattern, timeoutMillis); 
    } 

    public static Matcher createMatcherWithTimeout(String stringToMatch, Pattern regularExpressionPattern, int timeoutMillis) { 
     CharSequence charSequence = new TimeoutRegexCharSequence(stringToMatch, timeoutMillis, stringToMatch, 
       regularExpressionPattern.pattern()); 
     return regularExpressionPattern.matcher(charSequence); 
    } 

    private static class TimeoutRegexCharSequence implements CharSequence { 

     private final CharSequence inner; 

     private final int timeoutMillis; 

     private final long timeoutTime; 

     private final String stringToMatch; 

     private final String regularExpression; 

     public TimeoutRegexCharSequence(CharSequence inner, int timeoutMillis, String stringToMatch, String regularExpression) { 
      super(); 
      this.inner = inner; 
      this.timeoutMillis = timeoutMillis; 
      this.stringToMatch = stringToMatch; 
      this.regularExpression = regularExpression; 
      timeoutTime = System.currentTimeMillis() + timeoutMillis; 
     } 

     public char charAt(int index) { 
      if (System.currentTimeMillis() > timeoutTime) { 
       throw new RuntimeException("Timeout occurred after " + timeoutMillis + "ms while processing regular expression '" 
           + regularExpression + "' on input '" + stringToMatch + "'!"); 
      } 
      return inner.charAt(index); 
     } 

     public int length() { 
      return inner.length(); 
     } 

     public CharSequence subSequence(int start, int end) { 
      return new TimeoutRegexCharSequence(inner.subSequence(start, end), timeoutMillis, stringToMatch, regularExpression); 
     } 

     @Override 
     public String toString() { 
      return inner.toString(); 
     } 
    } 

} 

धन्यवाद एक बहुत मुझे एक अनावश्यक जटिल question के जवाब में इस समाधान की ओर इशारा करते के लिए dawce करने के लिए!

Answer 4

शायद आपको जो चाहिए वह एक नया lib है जो एनएफए एल्गोरिदम लागू करता है।

एनएफए एल्गोरिदम जावा मानक लाइब्रेरी द्वारा उपयोग किए जाने वाले एल्गोरिदम की तुलना में सैकड़ों गुना तेज है।

और जावा std lib इनपुट regexp के प्रति संवेदनशील है, जो आपकी समस्या उत्पन्न कर सकता है - कुछ इनपुट CPU को वर्षों तक चलाते हैं।

और समय-समय पर उपयोग किए जाने वाले चरणों के माध्यम से एनएफए एल्गोरिदम द्वारा निर्धारित किया जा सकता है। यह थ्रेड समाधान से प्रभावी है। मेरा विश्वास करो मैं एक सापेक्ष समस्या के लिए थ्रेड टाइमआउट का उपयोग करता हूं, यह प्रदर्शन के लिए भयानक है। अंततः मैं अपने एल्गोरिदम कार्यान्वयन के मुख्य पाश को संशोधित करके समस्या को ठीक करता हूं। मैं समय की जांच करने के लिए मुख्य लूप पर कुछ चेक पॉइंट डालता हूं।

विवरण यहां पाया जा सकता है: https://swtch.com/~rsc/regexp/regexp1.html।