From ebcb82cb52f64c4b2915e12f6514dcbd3552eed5 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Wed, 2 Sep 2015 13:28:48 +0100 Subject: [PATCH] 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 | 10 +++------- 1 file changed, 3 insertions(+), 7 deletions(-) diff --git a/re2c/src/codegen/skeleton/generate_data.cc b/re2c/src/codegen/skeleton/generate_data.cc index 5f4edb3f..fd93fe06 100644 --- a/re2c/src/codegen/skeleton/generate_data.cc +++ b/re2c/src/codegen/skeleton/generate_data.cc @@ -33,11 +33,11 @@ arccount_t Node::estimate_size_all (arccount_t wid, arccount_t len) { local_inc _ (loop); arccount_t size (0u); + const arccount_t new_len = len + arccount_t (1u); for (arcs_t::iterator i = arcs.begin (); i != arcs.end (); ++i) { const arccount_t new_wid = wid * arccount_t (i->second.size ()); - const arccount_t new_len = len + arccount_t (1u); - if (new_wid.overflow () || new_len.overflow ()) + if (new_wid.overflow ()) { return arccount_t::limit (); } @@ -67,14 +67,10 @@ arccount_t Node::estimate_size_cover (arccount_t wid, arccount_t len) local_inc _ (loop); arccount_t size (0u); arccount_t w (0u); + const arccount_t new_len = len + arccount_t (1u); for (wrap_iter i (arcs); !i.end () || w < wid; ++i) { const arccount_t new_wid = arccount_t (i->second.size ()); - const arccount_t new_len = len + arccount_t (1u); - if (new_wid.overflow () || new_len.overflow ()) - { - return arccount_t::limit (); - } size = size + i->first->estimate_size_cover (new_wid, new_len); if (size.overflow ()) { -- 2.50.1