#4 <s> * </s> gets stuck in infinite loop

TODO-4.0
pending-fixed
CQP engine (8)
5
2011-08-01
2006-05-20
No

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.

Discussion

  • Stefan Evert

    Stefan Evert - 2006-05-20
    • assigned_to: nobody --> schtepf
     
  • Stefan Evert

    Stefan Evert - 2006-05-20

    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).

     
  • Stefan Evert

    Stefan Evert - 2006-08-30
    • priority: 5 --> 7
     
  • Stefan Evert

    Stefan Evert - 2006-08-30

    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.

     
  • Stefan Evert

    Stefan Evert - 2006-08-30

    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.

     
  • Stefan Evert

    Stefan Evert - 2006-08-30
    • labels: 853490 --> CQP engine
     
  • Andrew Hardie

    Andrew Hardie - 2011-07-31
    • milestone: --> 2104577
     
  • Stefan Evert

    Stefan Evert - 2011-08-01
    • priority: 7 --> 5
    • milestone: 2104577 --> TODO-4.0
    • status: open --> pending-fixed
     
  • Stefan Evert

    Stefan Evert - 2011-08-01

    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.

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks