[TxMt] Re: regexp problem - eternal loop - how to cancel?

[Hans-Jörg Bibiko]

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ödel%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