長時間実行されている正規表現の一致をキャンセルしますか？

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 
} 

モニタースレッド：私はjava.sun.com/j2se/1.4.2/を読んだ

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

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

docs/guide/misc/threadPrimitiveDeprecation.htmlと私は、同期とハを介してThreadDeathがスローされる場所を制御しているので、この使用法は安全だと思いますそれを無視して、壊れた唯一のオブジェクトは、とにかく破棄される私のパターンとマッチャーのインスタンスになる可能性があります。私はこれがThread.stop（）を中断していると思います。なぜなら、エラーを再現しているわけではないからです。しかし、スレッドが死んでしまわないようにするために、find（）メソッドを中止するだけです。

これまで廃止予定だったAPIコンポーネントの使用を避けましたが、Matcher.find（）は中断されておらず、返却に非常に時間がかかることがあります。これを行うための良い方法はありますか？ Heritrixから

Answer 1

：（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(); 
    } 
} 

この1とあなたのCharSequenceをラップし、割り込みが動作するスレッド...

Answer 2

別の回避策はfind()を呼び出し、その後、マッチャーのregionを制限するだろうスレッドが中断されるか、一致が見つかるまで繰り返されます。このための追加のスレッドを使用して回避することが可能であるばらつきの少ない

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

あなたが必要とするのは、NFAアルゴリズムを実装する新しいライブラリです。

NFAアルゴリズムは、Java標準ライブラリで使用されるアルゴリズムより数百倍高速です。

Javaのstd libは入力regexpに敏感です。問題が起きる可能性があります。何らかの入力によってCPUが何年も実行されます。

タイムアウトは、NFAアルゴリズムで使用する手順で設定できます。スレッドソリューションよりも効果的です。私はスレッドタイムアウトを相対的な問題に使用していると信じています。パフォーマンスにとっては恐ろしいことです。私は最終的に私のアルゴリズム実装のメインループを修正して問題を解決します。メインループにチェックポイントを挿入して時間をテストします。

詳細はhttps://swtch.com/~rsc/regexp/regexp1.htmlです。