On 08.09.2008, at 16:11, Alaric Snell-Pym wrote:
It's not infinity that's necessarily the problem; the problem is that it's possible to write a regexp that takes millions of years to decide. Which isn't infinite, but is a long time to wait for dinner.
And you can't reliably tell if a loop is infinite. Any automated test, except in very restricted languages (non Turing-complete ones), can only classify loops (or any other bit of code into) these three categories:
- Will loop forever
- Won't loop forever (but might loop for a billion years)
- Might loop forever; who knows?
...and most samples will fall into the latter category, which tells you no more than you already knew ;-)
"In computability theory, the halting problem is a decision problem which can be stated as follows: given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input.
Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist."
Furthermore, due to the fact that regular expressions are a kind of a formal language (Chomsky Type 3) you may not forget "Gödel's incompleteness theorems" (esp. the second theoreme). http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems
That's why one could think more practically ;) Maybe it is possible to run the matching process in two threads. One thread (a) is used to match/replace/... and the other one (b) listens to a given keyboard event to kill the thread (a) if that process takes more time as expected. The 'only' thing which could be tricky is to remember the status of the text etc. before the regexp engine started.
Cheers,
--Hans