]> granicus.if.org Git - re2c/commit
Use the same tag version for all transitions from the given state.
authorUlya Trofimovich <skvadrik@gmail.com>
Mon, 23 Jan 2017 17:42:37 +0000 (17:42 +0000)
committerUlya Trofimovich <skvadrik@gmail.com>
Mon, 23 Jan 2017 17:42:37 +0000 (17:42 +0000)
commit31a8afdf15e3140c9f608f1cc54872efc0dd9e14
tree62f6412456adc240c8498a7a446d2e0a27d3aaf0
parent322fbb30eb2bfc5c7883a9eb054e0488ff26283a
Use the same tag version for all transitions from the given state.

This reduces the overall number of versions greatly, which is crucial
for the space and time efficiency of tag liveness analysis.

Of course, bottom and normal transitions still have different versions.

Differents tags on the same transition also have different versions.
It is not incorrect to give them the same version: all tags updated by
one and the same transition are either set to bottom, or to current
input position (which is the same for all tags on the given transition).
But this would create many states with a very special "shape" that do
not map to other states. In fact, this would cause exponential blowup
in the number of states (even in simple cases).
16 files changed:
re2c/src/ir/dfa/closure.cc
re2c/src/ir/dfa/closure.h
re2c/src/ir/dfa/determinization.cc
re2c/test/tags/fix3.i--tags.c
re2c/test/tags/fix3_trail.i--tags--input(custom).c
re2c/test/tags/fix3_trail.i--tags.c
re2c/test/tags/fix4.i--tags.c
re2c/test/tags/fix4_trail.i--tags--input(custom).c
re2c/test/tags/fix4_trail.i--tags.c
re2c/test/tags/fix5.i--tags.c
re2c/test/tags/fix5_trail.i--tags--input(custom).c
re2c/test/tags/fix5_trail.i--tags.c
re2c/test/tags/mapping1.i--tags--non-bijective-mapping.c
re2c/test/tags/mapping1.i--tags.c
re2c/test/tags/topsort2.i--tags.c
re2c/test/tags/twopass.i--tags.c