Re: [Patch 2/3] Make regex's infinite loop detection accurate

[Tim Shen <timshen91 at gmail dot com>]

On Sat, Apr 26, 2014 at 1:00 PM, Jonathan Wakely <jwakely@redhat.com> wrote:
> Maybe a dumb question (I don't understand a lot of the regex code!)
> but is it correct to set this to 1 in the case where
> __rep_count.first != _M_current ?  Could that result in the count
> going downwards from 2 to 1? (Maybe that's correct?)

As I said in the comment, __rep_count records how many times
(__rep_count.second) this node is visited *under certain input
iterator* (__rep_count.first).

That is to say, if the current iterator (_M_current) is not changing,
but the executor keeps visiting this node, times of visit needs to be
recorded. Once the _M_current changed, the count should be reset to 0.
We simply set it to 1 for the "set to 0 then increase by 1"
operations.

The idea behind this is that, for example, regex "(?:)*" will form a
self-epsilon-circle in the NFA graph. While it's executed, an infinite
loop may be entered because this circle doesn't consumes any input
(aka, the current iterator is not changing). So for given node, we
need to prevent from entering infinite loop by checking the iterator
since last visited. If the iterator didn't change, we shall refuse to
follow the edge-on-the-circle.

There's one more question: we shouldn't simply refuse to follow the
edge that last visited under the same iterator, because visiting some
node (begin capture, end capture) on the circle has side effects. To
make sure these side effects happen, one more time of reentering is
permitted. That is why we set the counter and permitted entering the
node for at most 2 times.

About the overall regex code, I think I can compose a blog entry to
explain it, if necessary?


-- 
Regards,
Tim Shen

Attachment: 2.diff
Description: Text document