[CWB] [ cwb-Bugs-1492044 ] <s> * </s> gets stuck in infinite loop

[SourceForge.net]

Bugs item #1492044, was opened at 2006-05-20 13:49
Message generated for change (Comment added) made by schtepf
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=722303&aid=1492044&group_id=131809

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: CQP engine
>Group: TODO-4.0
>Status: Pending
>Resolution: Fixed
>Priority: 5
Private: No
Submitted By: Stefan Evert (schtepf)
Assigned to: Stefan Evert (schtepf)
Summary: <s> * </s> gets stuck in infinite loop

Initial Comment:
The (meaningless) query "<s> * </s>" (which seems quite
natural to try for people who access CQP through a Web
interface and don't know its query language) gets
caught in an infinite loop, i.e. CQP runs forever with
full CPU power.



----------------------------------------------------------------------

>Comment By: Stefan Evert (schtepf)
Date: 2011-08-01 17:32

Message:
A partial fix for this bug has been in place for some time (since before
v3.0.0).  In the specific example listed in the bug report, CQP will abort
with this error message:

CQP Error:
	Infinite loop detected: did you quantify over a zero-width element (XML
tag or lookahead)?
	If you are reasonably sure that your query is valid, please contact the
CWB development team and file a bug report!
	Query execution aborted.

However, due to the messy internals of the query implementation, it may
still be possible to write CQP queries that trigger an infinite loop.

A clean solution will be possible when the query evaluation mechanism is
completely overhauled for CWB 4.0.  We should keep the ticket pending until
then so we remember to consider the case of such "empty loop" queries.

----------------------------------------------------------------------

Comment By: Stefan Evert (schtepf)
Date: 2006-08-30 14:31

Message:
Logged In: YES 
user_id=545257

This is especially a problem for Web interfaces, which
should try to catch queries of this type until the problem
is fixed.



----------------------------------------------------------------------

Comment By: Stefan Evert (schtepf)
Date: 2006-08-30 13:00

Message:
Logged In: YES 
user_id=545257

This is especially a problem for Web interfaces, which
should try to catch queries of this type until the problem
is fixed.



----------------------------------------------------------------------

Comment By: Stefan Evert (schtepf)
Date: 2006-05-20 14:17

Message:
Logged In: YES 
user_id=545257

What happens is that in the FSA constructed from the query,
<s> is a transition that does not "consume" a token, so <s>*
(Kleene star over <s>) effectively generates an eps-loop at
the start state of the FSA.  Normally, such errors are
caught because the start state is also a final state (the
query "<s> *" would result in such an error message), but in
this case, the additional constraint </s> (which can never
be satisfied) inserts another transition.

There should probably some test for eps-loops in the FSA
simulation, which can never do anything useful (unless I'm
mistaken).

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=722303&aid=1492044&group_id=131809