]> granicus.if.org Git - re2c/commit
Fixed bug in tag liveness analyses (tags lost in loops).
authorUlya Trofimovich <skvadrik@gmail.com>
Tue, 17 May 2016 16:11:40 +0000 (17:11 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Tue, 17 May 2016 16:11:40 +0000 (17:11 +0100)
commita7a26d17cee825afcbe8659cb31a04a165172eed
treef5ad63a0f0e090206b1b4d896b3fbe1b8a51f2ec
parent68578324292871b752c34221f24d429f725ba9cd
Fixed bug in tag liveness analyses (tags lost in loops).

Example that revealed failure (added as test):
    (@p "ac")* "b" { @p }

We used forward propagation: starting from initial state, walk DFA
in deep-first order; in each state, add tags associated with rule
or fallback set if necessary, then recurse to child states, then
merge all child sets into this node's live set.

This algorithm cannot propagate live tags in loops in cases when
DFS visits loopbacks before non-looping paths (tags don't propagate
into loopback states).

The usual algorithm for liveness analyses doesn't use DFS;
instead, it iterates on DFA states until fix point is reached
(next iteration adds no changes to live set compared to the
previous iteration). The fix applies this algorithm.

A more efficient algorithm may be possible; one that uses backwards
propagation instead of fix point (I'm not sure).
re2c/src/ir/dfa/tag_deduplication.cc
re2c/src/ir/tagpool.h
re2c/test/tags/dedup5.i--tags.c [new file with mode: 0644]
re2c/test/tags/dedup5.i--tags.re [new file with mode: 0644]