Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to set a time limit on a java function running a regex

I am running a regex in a java function to parse a document and return true if it has found the string specified by the regex and return false if it hasn't. But the problem is that when the document doesn't contain the string specified by the regex It takes a very long time to return false and I want to terminate that function if it takes more than 6 seconds to execute.

How can I set a time limit of 6 seconds on that function so as to forcibly terminate that if it takes more than 6 seconds.

I am calling a method "method 1" of class 2 from class 1. The "method 1" calls "method 2" of the same class i.e. "class 2". Method 2 runs the regex code over a document. If it finds the string specified by the regex, then it returns the result to the method 1 which in turn return the result to the method in "class 1" which called the "method 1" of class 2. Now the problem is that the execution time of both the method1 and method2 of class 2 should be not more than 6 seconds.

So, I made a new RegexpThread class in the same file, in which my class2 was. Then I move the method2 of the class2 into class RegexpThread. Then whenever the method 1 is called, it instantiates the RegexpThread class as follows:

RegexpThread rt = new RegexpThread() {
    public void run() {
        method 2(m, urlCopy, document);
    }    
};

rt.start();

try {
    rt.join(6 * 1000);
} catch (InterruptedException e) {
    return "y";
}

if(rt.getResultXml().equals("")) {
    return "g";
}

resultXml.append(rt.getResultXml());

return resultXml.toString();

The code shown is in the method 1 of class2. The method 2 in the RegexpThread class perform some regex search over a document. There is a private field named "resultXml" in the RegexpThread class. If the method 2 has found the string specified by the regex then it assigns the result to the private field "resultXml". If not then the "resultXml" contains its default value i.e empty string.

So, in the above "if block", it is checking the "resultXml" field against empty string. If it is an empty string then that means the regex has not found its string in the document. But if it is not an empty string then that means the regex has found the string in the document and has assigned the result to the "resultXml" field.

so, look at this and tell me what to do...

like image 224
Yatendra Avatar asked Aug 15 '09 20:08

Yatendra


3 Answers

I might be mistaken here, but I think all ways to terminate a thread have been deprecated for some time. The recommended way is to use a shared isRunning variable that your worker thread periodically checks and gracefully exits when it's been set.

This will not work in your case, but it looks to me like you're treating the symptom - not the real problem. You should post the code of your regexp function, that takes 6 seconds to execute. If it's the regexp itself, the execution time may be a case of catastrophic backtracking.

like image 85
waxwing Avatar answered Sep 24 '22 01:09

waxwing


There are two ways to answer this question.

On the one hand, there is no practical/effective way that is known to be safe of killing a thread that is executing Matcher.find(...) or Matcher.match(...). Calling Thread.stop() would work, but there are significant safety issues. The only way to address this would be to develop your own regex engine that regularly checked the interrupted flag. (This is not totally impractical. For example, if GPL wasn't an issue for you, you could start with the existing regex engine in OpenJDK.)

On the other hand, the real root of your problem is (most likely) that you are using regexes the wrong way. Either you are trying to do something that is too complicated for a single regex, or your regex is suboptimal.

EDIT: The typical cause of regexes taking too long is multiple quantifiers (?, , +) causing pathological backtracking. For example, if you try to match a string of N "A" characters followed by a "B" with the regex "^AAAAAA$", the complexity of the computation is (at least) O(N**5). Here's a more "real world" example:

"(.*)<html>(.*)<head>(.*)</head>(.*)<body>(.*)</body>(.*)</html>(.*)"

Now imagine what happens if you encounter a "web page" like this:

<html><html><html><html><html><html><html><html><html><html>
<head><head><head><head><head><head><head><head><head><head>
</head></head></head></head></head></head></head></head></head></head>
<body><body><body><body><body><body><body><body><body><body><body>
</body></body></body></body></body></body></body></body></body></body>

Notice that there is no closing </html> tag. This will run for a long time before failing. (I'm not exactly sure what the complexity is ... but you can estimate it experimentally it you feel like it.)

In this case, a simple answer is to use simpler regexes to locate the 6 marker elements and then extract the stuff between then using substring().

like image 27
Stephen C Avatar answered Sep 21 '22 01:09

Stephen C


I will assume for the moment that your regexp code is correct, and it really is some computational code that is CPU-bound for 6s.

Given the above, I think you have only one option. To execute your code in a number of stages/iterations and check a variable for a request to halt. You can't do this using the normal Pattern/Matcher code.

You could do this by splitting your input string beforehand in some fashion, and then feeding to your regexp bit by bit (your initial split would have to be independent of your regexp).

You can't do this by:

  1. using Thread.stop() etc. This has been deprecated and doesn't work properly.
  2. Using Thread.interrupt(). This sets an interrupted flag on the thread which is only checked when the thread performs IO. If the thread is CPU-bound, then that flag will never be checked.

Given the above, I would look again at why the regexp is taking 6s to match. Is the regexp correct ? Can you perform a regexp on smaller text segments ?

like image 34
Brian Agnew Avatar answered Sep 20 '22 01:09

Brian Agnew