]> granicus.if.org Git - re2c/commit
Omit some highly unlikely conditional exits from deep-first search.
authorUlya Trofimovich <skvadrik@gmail.com>
Wed, 2 Sep 2015 12:28:48 +0000 (13:28 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Wed, 2 Sep 2015 12:28:48 +0000 (13:28 +0100)
commitebcb82cb52f64c4b2915e12f6514dcbd3552eed5
tree7c8ad0daa0e088fd2e0f145d1107a399a872b70d
parent838d94f2308e73ea81c73ba163306477443d6eaf
Omit some highly unlikely conditional exits from deep-first search.

With '--skeleton' re2c builds DFA skeleton and performs DFS in order to
estimate the size of data to be generated. It maintains size counter: as
soon as the counter reaches certain limit, DFS should stop.

Size counter is always checked when recursion returns.
Sometimes it is clear that size counter will overflow upon recursion
return (when arguments overflow already) and DFS can exit early (before
entering recursion).

This commit omits checks of some arguments (and correponding early exits
from DFS): first, path length is very unlikely to overflow (one has to
write/generate a regular expression with length of ~1Gb, in which case
skeleton generation won't be the worst problem); second, the number of
outgoing arcs in each vertex is also highly unlikely to exceed 1Gb limit.
re2c/src/codegen/skeleton/generate_data.cc