From 5a27bafae146deb84d93ff8a22e9674c2558aa31 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Wed, 16 Mar 2016 14:15:25 +0000 Subject: [PATCH] Moved loop counters out of skeleton; they belong to algorithm-local stuff. --- re2c/src/ir/skeleton/control_flow.cc | 46 ++++++++++++-------- re2c/src/ir/skeleton/maxpath.cc | 12 ++--- re2c/src/ir/skeleton/skeleton.cc | 2 - re2c/src/ir/skeleton/skeleton.h | 9 ++-- re2c/src/ir/skeleton/unreachable_nullable.cc | 12 ++--- 5 files changed, 44 insertions(+), 37 deletions(-) diff --git a/re2c/src/ir/skeleton/control_flow.cc b/re2c/src/ir/skeleton/control_flow.cc index 92f57c7e..20e41c9f 100644 --- a/re2c/src/ir/skeleton/control_flow.cc +++ b/re2c/src/ir/skeleton/control_flow.cc @@ -15,25 +15,37 @@ namespace re2c // These paths are stored on heap, so the limit should be low. // Most real-world cases have only a few short paths. // We don't need all paths anyway, just some examples. -typedef u32lim_t<1024> nakeds_t; // ~1Kb +typedef u32lim_t<1024> ucf_size_t; // ~1Kb + +// UCF stands for 'undefined control flow' +struct ucf_t +{ + std::vector loops; + std::vector paths; + path_t prefix; + ucf_size_t size; + + ucf_t(size_t nnodes): loops(nnodes), paths(), + prefix(0), size(ucf_size_t::from32(0u)) {} +}; // We don't need all patterns that cause undefined behaviour. // We only need some examples, the shorter the better. static void naked_paths( - Skeleton &skel, - std::vector &paths, - path_t &prefix, - nakeds_t &size, + const Skeleton &skel, + ucf_t &ucf, size_t i) { const Node &node = skel.nodes[i]; - uint8_t &loop = skel.loops[i]; + uint8_t &loop = ucf.loops[i]; + path_t &prefix = ucf.prefix; + ucf_size_t &size = ucf.size; if (node.rule) { return; } else if (node.end()) { - paths.push_back(prefix); - size = size + nakeds_t::from64(prefix.len()); + ucf.paths.push_back(prefix); + size = size + ucf_size_t::from64(prefix.len()); } else if (loop < 2) { local_inc _(loop); Node::arcsets_t::const_iterator @@ -42,23 +54,19 @@ static void naked_paths( for (; arc != end && !size.overflow(); ++arc) { const size_t j = arc->first; prefix.push(j); - naked_paths(skel, paths, prefix, size, j); + naked_paths(skel, ucf, j); prefix.pop(); } } } -void warn_undefined_control_flow(Skeleton &skel) +void warn_undefined_control_flow(const Skeleton &skel) { - path_t prefix(0); - std::vector paths; - nakeds_t size = nakeds_t::from32(0u); - - naked_paths(skel, paths, prefix, size, 0); - - if (!paths.empty()) { - warn.undefined_control_flow(skel, paths, size.overflow()); - } else if (size.overflow()) { + ucf_t ucf(skel.nodes_count); + naked_paths(skel, ucf, 0); + if (!ucf.paths.empty()) { + warn.undefined_control_flow(skel, ucf.paths, ucf.size.overflow()); + } else if (ucf.size.overflow()) { warn.fail(Warn::UNDEFINED_CONTROL_FLOW, skel.line, "DFA is too large to check undefined control flow"); } diff --git a/re2c/src/ir/skeleton/maxpath.cc b/re2c/src/ir/skeleton/maxpath.cc index a5ea7770..288489dc 100644 --- a/re2c/src/ir/skeleton/maxpath.cc +++ b/re2c/src/ir/skeleton/maxpath.cc @@ -16,12 +16,13 @@ static const uint32_t DIST_MAX = DIST_ERROR - 1; // different from YYMAXFILL calculation // in the way it handles loops and empty regexp static void calc_dist( - Skeleton &skel, + const Skeleton &skel, + std::vector &loops, std::vector &dists, size_t i) { const Node &node = skel.nodes[i]; - uint8_t &loop = skel.loops[i]; + uint8_t &loop = loops[i]; uint32_t &dist = dists[i]; if (dist != DIST_ERROR) { @@ -35,7 +36,7 @@ static void calc_dist( end = node.arcs.end(); for (; arc != end; ++arc) { const size_t j = arc->first; - calc_dist(skel, dists, j); + calc_dist(skel, loops, dists, j); uint32_t &d = dists[j]; if (d != DIST_ERROR) { if (dist == DIST_ERROR) { @@ -50,10 +51,11 @@ static void calc_dist( } // calculate maximal path length, check overflow -uint32_t maxpath(Skeleton &skel) +uint32_t maxpath(const Skeleton &skel) { + std::vector loops(skel.nodes_count); std::vector dists(skel.nodes_count); - calc_dist(skel, dists, 0); + calc_dist(skel, loops, dists, 0); const uint32_t maxlen = dists[0]; if (maxlen == DIST_MAX) { error("DFA path %sis too long", incond(skel.cond).c_str()); diff --git a/re2c/src/ir/skeleton/skeleton.cc b/re2c/src/ir/skeleton/skeleton.cc index ee6f2464..3486e578 100644 --- a/re2c/src/ir/skeleton/skeleton.cc +++ b/re2c/src/ir/skeleton/skeleton.cc @@ -63,7 +63,6 @@ Skeleton::Skeleton( line(dfa_line), nodes_count(dfa.states.size() + 1), // +1 for default state nodes(new Node[nodes_count]), - loops(new uint8_t[nodes_count]()), sizeof_key(4), rules(rs) { @@ -113,7 +112,6 @@ Skeleton::Skeleton( Skeleton::~Skeleton() { delete[] nodes; - delete[] loops; } uint32_t Skeleton::rule2key(rule_rank_t r) const diff --git a/re2c/src/ir/skeleton/skeleton.h b/re2c/src/ir/skeleton/skeleton.h index 7b1ae6f6..9e500273 100644 --- a/re2c/src/ir/skeleton/skeleton.h +++ b/re2c/src/ir/skeleton/skeleton.h @@ -54,9 +54,6 @@ struct Skeleton const size_t nodes_count; Node *nodes; - // visit counters (for graph traversal) - uint8_t *loops; - size_t sizeof_key; rules_t rules; @@ -82,10 +79,10 @@ template key_t Skeleton::rule2key(rule_rank_t r) } } -uint32_t maxpath(Skeleton &skel); -void warn_undefined_control_flow(Skeleton &skel); +uint32_t maxpath(const Skeleton &skel); +void warn_undefined_control_flow(const Skeleton &skel); void fprint_default_path(FILE *f, const Skeleton &skel, const path_t &p); -void warn_unreachable_nullable_rules(Skeleton &skel); +void warn_unreachable_nullable_rules(const Skeleton &skel); void emit_data(const Skeleton &skel, const char *fname); void emit_prolog(OutputFile & o); void emit_start(const Skeleton &skel, OutputFile &o, size_t maxfill, diff --git a/re2c/src/ir/skeleton/unreachable_nullable.cc b/re2c/src/ir/skeleton/unreachable_nullable.cc index 4c7111ce..609d4382 100644 --- a/re2c/src/ir/skeleton/unreachable_nullable.cc +++ b/re2c/src/ir/skeleton/unreachable_nullable.cc @@ -12,12 +12,13 @@ namespace re2c { static void calc_reachable( - Skeleton &skel, + const Skeleton &skel, + std::vector &loops, std::vector > &reachs, size_t i) { const Node &node = skel.nodes[i]; - uint8_t &loop = skel.loops[i]; + uint8_t &loop = loops[i]; std::set &reach = reachs[i]; if (!reach.empty()) { @@ -31,17 +32,18 @@ static void calc_reachable( end = node.arcs.end(); for (; arc != end; ++arc) { const size_t j = arc->first; - calc_reachable(skel, reachs, j); + calc_reachable(skel, loops, reachs, j); reach.insert(reachs[j].begin(), reachs[j].end()); } } } -void warn_unreachable_nullable_rules(Skeleton &skel) +void warn_unreachable_nullable_rules(const Skeleton &skel) { // calculate reachable rules + std::vector loops(skel.nodes_count); std::vector > reachs(skel.nodes_count); - calc_reachable(skel, reachs, 0); + calc_reachable(skel, loops, reachs, 0); for (uint32_t i = 0; i < skel.nodes_count; ++i) { RuleInfo *r1 = skel.nodes[i].rule; -- 2.40.0