]> granicus.if.org Git - re2c/commit
Fixed eternal loop in path cover generation algorithm for '--skeleton'.
authorUlya Trofimovich <skvadrik@gmail.com>
Sun, 6 Sep 2015 21:22:12 +0000 (22:22 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Mon, 7 Sep 2015 08:30:06 +0000 (09:30 +0100)
commit56e684f2005b58eefc711e3b214b4f7ab747f7da
tree2fd87742add47177d722777c5bf03db04a826716
parentc17f717d2114063c9cdf4e00b83884ff62cb6e81
Fixed eternal loop in path cover generation algorithm for '--skeleton'.

The simplest example I was able to come up with that reveals eternal
loop is the following:
    /*!re2c
        ( [^acf] | "0b" | "a"[^] | "a0"[^] )+ {}
    */
The problem was caused by my assumption that from any node there is
at least one non-looping path to end node. The assumption is true;
what I didn't take into account was that all such paths may go via
nodes that have already occured twice on the way to current node
(their loop counter is greater than 1). In this case the algorithm
would find no path to end node. Since not all prefixes would have
been covered (exactly none of them) the algorithm would loop forever.

Such branch may be abandoned safely: the algorithm will later find
another path to current state without loops.

As soon as I realized the problem the fix was trivial: if all outgoing
arcs have been exhausted and none of them yielded any results, abandon
current branch.
re2c/src/codegen/skeleton/generate_data.cc