<div class="markdown_content"><ul>
<li>Description has changed:</li>
</ul>
<p>Diff:</p>
<div class="codehilite"><pre><span></span><span class="gd">--- old</span>
<span class="gi">+++ new</span>
<span class="gu">@@ -1,25 +1,27 @@</span>
In version 3, the following (meaningless) query used to get caught in an infinite loop, i.e. CQP runs forever with full CPU power.
<span class="gd">-&#34;&lt;s&gt; * &lt;/s&gt;&#34;</span>
<span class="gi">+ &#34;&lt;s&gt; * &lt;/s&gt;&#34;</span>
(this was bug #4: https://sourceforge.net/p/cwb/bugs/4/ )
The explanation:
<span class="gd">-==================</span>
<span class="gi">+(begin quote)==================</span>
<span class="gi">+</span>
What happens is that in the FSA constructed from the query,
<span class="gd">-&lt;s&gt; is a transition that does not &#34;consume&#34; a token, so &lt;s&gt;*</span>
<span class="gd">-(Kleene star over &lt;s&gt;) effectively generates an eps-loop at</span>
<span class="gi">+&amp;lt;s&gt; is a transition that does not &#34;consume&#34; a token, so &amp;lt;s&gt;*</span>
<span class="gi">+(Kleene star over &amp;lt;s&gt;) effectively generates an eps-loop at</span>
the start state of the FSA. Normally, such errors are
caught because the start state is also a final state (the
<span class="gd">-query &#34;&lt;s&gt; *&#34; would result in such an error message), but in</span>
<span class="gd">-this case, the additional constraint &lt;/s&gt; (which can never</span>
<span class="gi">+query &#34;&amp;lt;s&gt; \*&#34; would result in such an error message), but in</span>
<span class="gi">+this case, the additional constraint &amp;lt;/s&gt; (which can never</span>
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&#39;m
mistaken).
<span class="gd">-==================</span>
<span class="gi">+</span>
<span class="gi">+(end quote)==================</span>
The bug was fixed long ago, with a check for infinite loops which aborts CQP:
</pre></div>
<ul>
<li><strong>assigned_to</strong>: Stefan Evert</li>
</ul>
<hr/>
<p><strong> <a class="alink" href="https://sourceforge.net/p/cwb/feature-requests/66/">[feature-requests:#66]</a> Cleanly avoid infinite loop queries</strong></p>
<p><strong>Status:</strong> open<br/>
<strong>Group:</strong> TODO-4.0<br/>
<strong>Labels:</strong> CQP engine <br/>
<strong>Created:</strong> Thu Apr 08, 2021 12:30 AM UTC by Andrew Hardie<br/>
<strong>Last Updated:</strong> Thu Apr 08, 2021 12:30 AM UTC<br/>
<strong>Owner:</strong> Stefan Evert</p>
<p>In version 3, the following (meaningless) query used to get caught in an infinite loop, i.e. CQP runs forever with full CPU power.</p>
<div class="codehilite"><pre><span></span>"<span class="nt"><s></span> * <span class="nt"></s></span>"
</pre></div>
<p>(this was bug #4: <a href="https://sourceforge.net/p/cwb/bugs/4/">https://sourceforge.net/p/cwb/bugs/4/</a> )</p>
<p>The explanation:</p>
<p>(begin quote)==================</p>
<p>What happens is that in the FSA constructed from the query,<br/>
<s> is a transition that does not "consume" a token, so <s>*<br/>
(Kleene star over <s>) effectively generates an eps-loop at<br/>
the start state of the FSA. Normally, such errors are<br/>
caught because the start state is also a final state (the<br/>
query "<s> *" would result in such an error message), but in<br/>
this case, the additional constraint </s> (which can never<br/>
be satisfied) inserts another transition.</p>
<p>There should probably some test for eps-loops in the FSA<br/>
simulation, which can never do anything useful (unless I'm<br/>
mistaken).</p>
<p>(end quote)==================</p>
<p>The bug was fixed long ago, with a check for infinite loops which aborts CQP:</p>
<div class="codehilite"><pre><span></span><span class="nv">CQP</span> <span class="nv">Error</span>:
<span class="nv">Infinite</span> <span class="k">loop</span> <span class="nv">detected</span>: <span class="nv">did</span> <span class="nv">you</span> <span class="nv">quantify</span> <span class="nv">over</span> <span class="nv">a</span> <span class="nv">zero</span><span class="o">-</span><span class="nv">width</span> <span class="nv">element</span> <span class="ss">(</span><span class="nv">XML</span> <span class="nv">tag</span> <span class="nv">or</span> <span class="nv">lookahead</span><span class="ss">)</span>?
<span class="k">If</span> <span class="nv">you</span> <span class="nv">are</span> <span class="nv">reasonably</span> <span class="nv">sure</span> <span class="nv">that</span> <span class="nv">your</span> <span class="nv">query</span> <span class="nv">is</span> <span class="nv">valid</span>, <span class="nv">please</span> <span class="nv">contact</span> <span class="nv">the</span> <span class="nv">CWB</span> <span class="nv">development</span> <span class="nv">team</span> <span class="nv">and</span> <span class="nv">file</span> <span class="nv">a</span> <span class="nv">bug</span> <span class="nv">report</span><span class="o">!</span>
<span class="nv">Query</span> <span class="nv">execution</span> <span class="nv">aborted</span>.
</pre></div>
<p>But, as Stefan noted,</p>
<p>"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."</p>
<p>This FR records the need for a clean mechanism to avoid such infinite loops in CWB4.</p>
<hr/>
<p>Sent from sourceforge.net because cwb@sslmit.unibo.it is subscribed to <a href="https://sourceforge.net/p/cwb/feature-requests/">https://sourceforge.net/p/cwb/feature-requests/</a></p>
<p>To unsubscribe from further messages, a project admin can change settings at <a href="https://sourceforge.net/p/cwb/admin/feature-requests/options.">https://sourceforge.net/p/cwb/admin/feature-requests/options.</a> Or, if this is a mailing list, you can unsubscribe from the mailing list.</p></div>