From a6935985400ee6fa39adc5971cfcb24e7ef39af8 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Wed, 5 Apr 2017 12:42:05 +0100 Subject: [PATCH] Separated lookahead tags from tag versions in closure items. This commit reverts commit 0b2ca9bf141259baf6cb0b067621c06db5f06b46: "Pack lookahead tags together with tag versions in TDFA state." Packing was possible because we were not interested in tag version if closure item had this tag in lookahead set. However, if we are to store the full history of each tag, we'll need this intermediate version in spite of the fact that it is overwritten on the next transition. --- re2c/src/dfa/closure.cc | 113 +++++++++++--------------------- re2c/src/dfa/closure.h | 3 +- re2c/src/dfa/determinization.cc | 61 +++++++++++++---- re2c/src/dfa/dump.cc | 48 +++++++++----- re2c/src/dfa/dump.h | 2 +- re2c/src/dfa/find_state.cc | 43 ++++++------ re2c/src/dfa/find_state.h | 1 + 7 files changed, 145 insertions(+), 126 deletions(-) diff --git a/re2c/src/dfa/closure.cc b/re2c/src/dfa/closure.cc index 64d148d6..42f0589a 100644 --- a/re2c/src/dfa/closure.cc +++ b/re2c/src/dfa/closure.cc @@ -10,15 +10,14 @@ namespace re2c static void closure_one(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, clos_t &c0, nfa_state_t *n, const std::vector &tags, closure_t *shadow, std::valarray &rules); static bool better(const clos_t &c1, const clos_t &c2, Tagpool &tagpool, tagtree_t &tagtree, const std::vector &tags); -static void lower_lookahead_to_transition(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree); -static void update_versions(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, tagver_t &maxver, tagver_t *newvers); +static void lower_lookahead_to_transition(closure_t &clos); +static void update_versions(closure_t &clos, Tagpool &tagpool, tagver_t &maxver, tagver_t *newvers); static void orders(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, const std::vector &tags); -static void find_nondet(const closure_t &clos, size_t *nondet, const Tagpool &tagpool, const std::valarray &rules); static bool cmpby_rule_state(const clos_t &x, const clos_t &y); void closure(closure_t &clos1, closure_t &clos2, Tagpool &tagpool, tagtree_t &tagtree, std::valarray &rules, tagver_t &maxver, tagver_t *newvers, - size_t *nondet, bool lookahead, closure_t *shadow, const std::vector &tags) + bool lookahead, closure_t *shadow, const std::vector &tags) { // build tagged epsilon-closure of the given set of NFA states clos2.clear(); @@ -34,15 +33,13 @@ void closure(closure_t &clos1, closure_t &clos2, Tagpool &tagpool, tagtree_t &ta // see note [the difference between TDFA(0) and TDFA(1)] if (!lookahead) { - lower_lookahead_to_transition(clos2, tagpool, tagtree); - if (shadow) lower_lookahead_to_transition(*shadow, tagpool, tagtree); + lower_lookahead_to_transition(clos2); + if (shadow) lower_lookahead_to_transition(*shadow); } - find_nondet(clos2, nondet, tagpool, rules); - // merge tags from different rules, find nondeterministic tags - update_versions(clos2, tagpool, tagtree, maxver, newvers); - if (shadow) update_versions(*shadow, tagpool, tagtree, maxver, newvers); + update_versions(clos2, tagpool, maxver, newvers); + if (shadow) update_versions(*shadow, tagpool, maxver, newvers); } bool cmpby_rule_state(const clos_t &x, const clos_t &y) @@ -107,7 +104,7 @@ void closure_one(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, clos_t & break; } - clos_t c2 = {c0.origin, n, c0.tvers, + clos_t c2 = {c0.origin, n, c0.tvers, c0.ttran, tagpool.insert(tagtree.leaves()), c0.order, c0.index++}; if (c == e) { clos.push_back(c2); @@ -141,11 +138,13 @@ bool better(const clos_t &c1, const clos_t &c2, { if (c1.ttran == c2.ttran && c1.tvers == c2.tvers + && c1.tlook == c2.tlook && c1.order == c2.order && c1.index == c2.index) return false; const tagver_t - *l1 = tagpool[c1.ttran], *l2 = tagpool[c2.ttran], + *l1 = tagpool[c1.tlook], *l2 = tagpool[c2.tlook], + *t1 = tagpool[c1.ttran], *t2 = tagpool[c2.ttran], *v1 = tagpool[c1.tvers], *v2 = tagpool[c2.tvers], *o1 = tagpool[c1.order], *o2 = tagpool[c2.order]; tagver_t x, y; @@ -174,6 +173,11 @@ bool better(const clos_t &c1, const clos_t &c2, if (x > y) return false; if (x < y) return true; + x = t1[t]; y = t2[t]; + if (x < 0 || y < 0) goto leftmost; + if (x > y) return false; + if (x < y) return true; + x = v1[t]; y = v2[t]; if (x < 0 || y < 0) goto leftmost; if (x > y) return false; @@ -215,34 +219,15 @@ bool better(const clos_t &c1, const clos_t &c2, * Thus in general TDFA(1) raises less conflicts than TDFA(0). */ -// Make TDFA(0) look like TDFA(1), which expects that after epsilon-closure -// lookahead tags occupy the place of future transition tags, while -// transition tags are scattered across tag versions inherited from the -// previous kernel. TDFA(0)'s representation is simpler and more logical, -// and 'lowering' is just a waste for TDFA(0). However, supporting two -// different handlers for TDFA(0) and TDFA(1) is unmaintainable, and since -// TDFA(1) is default, it has the fast path. -void lower_lookahead_to_transition(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree) +void lower_lookahead_to_transition(closure_t &clos) { - const size_t ntag = tagpool.ntags; - tagver_t *vers = tagpool.buffer1; - for (clositer_t c = clos.begin(); c != clos.end(); ++c) { - if (c->ttran == ZERO_TAGS) continue; - - const tagver_t - *look = tagpool[c->ttran], - *oldv = tagpool[c->tvers]; - for (size_t t = 0; t < ntag; ++t) { - const tagver_t l = tagtree.elem(look[t]); - vers[t] = l == TAGVER_ZERO ? oldv[t] : l; - } - c->tvers = tagpool.insert(vers); - c->ttran = ZERO_TAGS; + c->ttran = c->tlook; + c->tlook = ZERO_TAGS; } } -void update_versions(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, +void update_versions(closure_t &clos, Tagpool &tagpool, tagver_t &maxver, tagver_t *newvers) { const size_t ntag = tagpool.ntags; @@ -262,7 +247,7 @@ void update_versions(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, cur[t] = bot[t] = TAGVER_ZERO; for (c = b; c != e; ++c) { - if (tagpool[c->tvers][t] == TAGVER_CURSOR) { + if (tagpool[c->ttran][t] == TAGVER_CURSOR) { if (newcur == TAGVER_ZERO) { newcur = ++maxver; } @@ -272,7 +257,7 @@ void update_versions(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, } for (c = b; c != e; ++c) { - if (tagpool[c->tvers][t] == TAGVER_BOTTOM) { + if (tagpool[c->ttran][t] == TAGVER_BOTTOM) { if (newbot == TAGVER_ZERO) { newbot = -(++maxver); } @@ -284,23 +269,22 @@ void update_versions(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, // set transition tags and update versions for (c = b; c != e; ++c) { + if (c->ttran == ZERO_TAGS) continue; + const tagver_t - *look = tagpool[c->ttran], + *oldt = tagpool[c->ttran], *oldv = tagpool[c->tvers]; for (size_t i = 0; i < ntag; ++i) { - const tagver_t o = oldv[i], l = tagtree.elem(look[i]); + const tagver_t ov = oldv[i], ot = oldt[i]; tagver_t &v = vers[i], &t = tran[i]; - if (l != TAGVER_ZERO) { - v = l; - t = TAGVER_ZERO; - } else if (o == TAGVER_CURSOR) { + if (ot == TAGVER_CURSOR) { v = t = cur[i]; - } else if (o == TAGVER_BOTTOM) { + } else if (ot == TAGVER_BOTTOM) { v = t = bot[i]; } else { - v = o; + v = ov; t = TAGVER_ZERO; } } @@ -390,11 +374,11 @@ void orders(closure_t &clos, Tagpool &tagpool, if (orbit(tags[t])) { keys1.clear(); for (c = b; c != e; ++c) { - keys1.insert(key1_t(tagpool[c->order][t], tagpool[c->ttran][t])); + keys1.insert(key1_t(tagpool[c->order][t], tagpool[c->tlook][t])); } for (c = b; c != e; ++c, o += ntag) { const ptrdiff_t d = std::distance(keys1.begin(), - keys1.find(key1_t(tagpool[c->order][t], tagpool[c->ttran][t]))); + keys1.find(key1_t(tagpool[c->order][t], tagpool[c->tlook][t]))); o[t] = static_cast(d); } @@ -417,35 +401,16 @@ void orders(closure_t &clos, Tagpool &tagpool, for (c = b; c != e; ++c, o += ntag) { c->order = tagpool.insert(o); } -} - -/* - * For each tag, find the number of parallel versions of this tag - * used in this closure (degree of non-determinism). - */ -void find_nondet(const closure_t &clos, size_t *nondet, - const Tagpool &tagpool, const std::valarray &rules) -{ - std::set uniq; - cclositer_t b = clos.begin(), e = clos.end(), c, x0, x; - size_t r0 = 0; - for (c = b; c != e;) { - const size_t r = c->state->rule; - const Rule &rule = rules[r]; - - // closure items must be grouped by rule - assert(r >= r0); r0 = r; - - for (x0 = c; ++c != e && c->state->rule == r;); - - for (size_t t = rule.ltag; t < rule.htag; ++t) { - uniq.clear(); - for (x = x0; x != c; ++x) { - uniq.insert(tagpool[x->tvers][t]); - } - nondet[t] = std::max(nondet[t], uniq.size()); + // flatten lookahead tags (take the last on each path) + tagver_t *look = tagpool.buffer1; + for (clositer_t c = clos.begin(); c != clos.end(); ++c) { + if (c->tlook == ZERO_TAGS) continue; + const tagver_t *oldl = tagpool[c->tlook]; + for (size_t t = 0; t < ntag; ++t) { + look[t] = tagtree.elem(oldl[t]); } + c->tlook = tagpool.insert(look); } } diff --git a/re2c/src/dfa/closure.h b/re2c/src/dfa/closure.h index 6f16331a..7ae7df44 100644 --- a/re2c/src/dfa/closure.h +++ b/re2c/src/dfa/closure.h @@ -16,6 +16,7 @@ struct clos_t nfa_state_t *state; size_t tvers; // vector of tag versions (including lookahead tags) size_t ttran; // vector of transition tags + size_t tlook; // vector of lookahead tags size_t order; // vector of orders size_t index; // leftmost order in NFA traversal @@ -28,7 +29,7 @@ typedef closure_t::const_iterator cclositer_t; void closure(closure_t &clos1, closure_t &clos2, Tagpool &tagpool, tagtree_t &tagtree, std::valarray &rules, tagver_t &maxver, tagver_t *newvers, - size_t *nondet, bool lookahead, closure_t *shadow, const std::vector &tags); + bool lookahead, closure_t *shadow, const std::vector &tags); } // namespace re2c diff --git a/re2c/src/dfa/determinization.cc b/re2c/src/dfa/determinization.cc index a92da455..f80315a4 100644 --- a/re2c/src/dfa/determinization.cc +++ b/re2c/src/dfa/determinization.cc @@ -15,9 +15,9 @@ namespace re2c static nfa_state_t *transition(nfa_state_t *state, uint32_t symbol); static void reach(const kernel_t *kernel, closure_t &clos, uint32_t symbol); -static void warn_nondeterministic_tags(const size_t *nondet, - const std::vector &tags, const std::valarray &rules, - const std::string &cond, Warn &warn); +static void warn_nondeterministic_tags(const kernels_t &kernels, + const Tagpool &tagpool, const std::vector &tags, + const std::valarray &rules, const std::string &cond, Warn &warn); const size_t dfa_t::NIL = std::numeric_limits::max(); @@ -41,7 +41,8 @@ void reach(const kernel_t *kernel, closure_t &clos, uint32_t symbol) nfa_state_t *s1 = kernel->state[i], *s2 = transition(s1, symbol); if (s2) { - clos_t c = {s1, s2, kernel->tvers[i], ZERO_TAGS, kernel->order[i], 0}; + clos_t c = {s1, s2, kernel->tvers[i], kernel->tlook[i], + ZERO_TAGS, kernel->order[i], 0}; clos.push_back(c); } } @@ -67,7 +68,6 @@ dfa_t::dfa_t(const nfa_t &nfa, const opt_t *opts, kernels_t kernels(tagpool, tcpool, tags); closure_t clos1, clos2; tagver_t *newvers = new tagver_t[ntag * 2]; - size_t *nondet = new size_t[ntag](); dump_dfa_t dump(*this, tagpool, nfa, opts->dump_dfa_raw); // all-zero tag configuration must have static number zero @@ -85,36 +85,69 @@ dfa_t::dfa_t(const nfa_t &nfa, const opt_t *opts, // build tagged epsilon-closure of all reachable NFA states, // then find identical or mappable DFA state or add a new one - clos_t c0 = {NULL, nfa.root, INITIAL_TAGS, ZERO_TAGS, ZERO_TAGS, 0}; + clos_t c0 = {NULL, nfa.root, INITIAL_TAGS, ZERO_TAGS, ZERO_TAGS, ZERO_TAGS, 0}; clos1.push_back(c0); std::fill(newvers, newvers + ntag * 2, TAGVER_ZERO); - closure(clos1, clos2, tagpool, tagtree, rules, maxtagver, newvers, nondet, lookahead, dump.shadow, tags); + closure(clos1, clos2, tagpool, tagtree, rules, maxtagver, newvers, lookahead, dump.shadow, tags); find_state(*this, dfa_t::NIL, 0/* any */, kernels, clos2, dump); for (size_t i = 0; i < kernels.size(); ++i) { std::fill(newvers, newvers + ntag * 2, TAGVER_ZERO); for (size_t c = 0; c < nchars; ++c) { reach(kernels[i], clos1, charset[c]); - closure(clos1, clos2, tagpool, tagtree, rules, maxtagver, newvers, nondet, lookahead, dump.shadow, tags); + closure(clos1, clos2, tagpool, tagtree, rules, maxtagver, newvers, lookahead, dump.shadow, tags); find_state(*this, i, c, kernels, clos2, dump); } } - warn_nondeterministic_tags(nondet, tags, rules, cond, warn); + warn_nondeterministic_tags(kernels, tagpool, tags, rules, cond, warn); delete[] newvers; - delete[] nondet; } -void warn_nondeterministic_tags(const size_t *nondet, - const std::vector &tags, const std::valarray &rules, - const std::string &cond, Warn &warn) +/* + * For each tag, find maximal number of parallel versions of this tag + * used in each kernel (degree of non-determinism) and warn about tags with + * maximum degree two or more. + * + * WARNING: this function assumes that kernel items are grouped by rule + */ +void warn_nondeterministic_tags(const kernels_t &kernels, + const Tagpool &tagpool, const std::vector &tags, + const std::valarray &rules, const std::string &cond, Warn &warn) { + const size_t + ntag = tagpool.ntags, + nkrn = kernels.size(); + std::vector maxv(ntag, 0); + std::set uniq; + + for (size_t i = 0; i < nkrn; ++i) { + const kernel_t *k = kernels[i]; + nfa_state_t **s = k->state; + const size_t n = k->size, *v = k->tvers; + + for (size_t u = 0; u < n;) { + const size_t r = s[u]->rule; + const Rule &rule = rules[r]; + + const size_t l = u; + for (; ++u < n && s[u]->rule == r;); + for (size_t t = rule.ltag; t < rule.htag; ++t) { + uniq.clear(); + for (size_t m = l; m < u; ++m) { + uniq.insert(tagpool[v[m]][t]); + } + maxv[t] = std::max(maxv[t], uniq.size()); + } + } + } + const size_t nrule = rules.size(); for (size_t r = 0; r < nrule; ++r) { const Rule &rule = rules[r]; for (size_t t = rule.ltag; t < rule.htag; ++t) { - const size_t m = nondet[t]; + const size_t m = maxv[t]; if (m > 1) { const Tag &tag = tags[t]; const uint32_t line = rule.code->fline; diff --git a/re2c/src/dfa/dump.cc b/re2c/src/dfa/dump.cc index 64d8c1b5..a61e6fc3 100644 --- a/re2c/src/dfa/dump.cc +++ b/re2c/src/dfa/dump.cc @@ -40,29 +40,34 @@ uint32_t dump_dfa_t::index(const nfa_state_t *s) return static_cast(s - base); } -void dump_dfa_t::closure_tags(cclositer_t c, bool shadowed) +void dump_dfa_t::closure_tags(cclositer_t c, + const tagver_t *lookahead, bool shadowed) { if (!debug) return; if (c->tvers == ZERO_TAGS) return; - const tagver_t *vers = tagpool[c->tvers]; + const tagver_t + *look = tagpool[c->tlook], + *vers = tagpool[c->tvers], + *ord = tagpool[c->order]; const size_t ntag = tagpool.ntags; for (size_t t = 0; t < ntag; ++t) { const Tag &tag = dfa.tags[t]; fprintf(stderr, " %s", tagname(tag)); - - const tagver_t v = vers[t]; - if (v == TAGVER_BOTTOM) { - fprintf(stderr, "↓"); - } else if (v == TAGVER_CURSOR) { - fprintf(stderr, "↑"); - } else { - fprintf(stderr, "%d", abs(v)); + fprintf(stderr, "%d", abs(vers[t])); + if (lookahead[t]) { + const tagver_t l = look[t]; + if (l == TAGVER_BOTTOM) { + fprintf(stderr, " ↓"); + } else if (l == TAGVER_CURSOR) { + fprintf(stderr, " ↑"); + } else { + fprintf(stderr, " "); + } } - if (!shadowed && capture(tag)) { - fprintf(stderr, "[%d]", tagpool[c->order][t]); + fprintf(stderr, "[%d]", ord[t]); } } } @@ -71,6 +76,8 @@ void dump_dfa_t::closure(const closure_t &clos, uint32_t state, bool isnew) { if (!debug) return; + cclositer_t c1 = clos.begin(), c2 = clos.end(), c, + s1 = shadow->begin(), s2 = shadow->end(), s; const char *style = isnew ? "" : " STYLE=\"dotted\"", *color = " COLOR=\"lightgray\""; @@ -80,19 +87,26 @@ void dump_dfa_t::closure(const closure_t &clos, uint32_t state, bool isnew) " CELLBORDER=\"1\"" ">", isnew ? "" : "i", state); - for (cclositer_t b = shadow->begin(), c = b; c != shadow->end(); ++c) { + tagver_t *look = tagpool.buffer1; + for (size_t t = 0; t < tagpool.ntags; ++t) { + for (c = c1; c != c2 && tagpool[c->tlook][t] == TAGVER_ZERO; ++c); + for (s = s1; s != s2 && tagpool[s->tlook][t] == TAGVER_ZERO; ++s); + look[t] = c != c2 || s != s2; + } + + for (s = s1; s != s2; ++s) { fprintf(stderr, "%u", - index(c->state), c - b, color, style, color, index(c->state)); - closure_tags(c, true); + index(s->state), s - s1, color, style, color, index(s->state)); + closure_tags(s, look, true); fprintf(stderr, ""); } if (!shadow->empty()) { fprintf(stderr, ""); } - for (cclositer_t c = clos.begin(); c != clos.end(); ++c) { + for (c = c1; c != c2; ++c) { fprintf(stderr, "%u", index(c->state), style, index(c->state)); - closure_tags(c, true); + closure_tags(c, look, true); fprintf(stderr, ""); } fprintf(stderr, ">]\n"); diff --git a/re2c/src/dfa/dump.h b/re2c/src/dfa/dump.h index 7f3e7f2a..b643e398 100644 --- a/re2c/src/dfa/dump.h +++ b/re2c/src/dfa/dump.h @@ -18,7 +18,7 @@ struct dump_dfa_t dump_dfa_t(const dfa_t &d, const Tagpool &pool, const nfa_t &n, bool dbg); ~dump_dfa_t(); - void closure_tags(cclositer_t c, bool shadowed); + void closure_tags(cclositer_t c, const tagver_t *lookahead, bool shadowed); void closure(const closure_t &clos, uint32_t state, bool isnew); void state0(const closure_t &clos); void state(const closure_t &clos, size_t state, size_t symbol, bool isnew); diff --git a/re2c/src/dfa/find_state.cc b/re2c/src/dfa/find_state.cc index 9ea485c3..bd8fe66e 100644 --- a/re2c/src/dfa/find_state.cc +++ b/re2c/src/dfa/find_state.cc @@ -10,6 +10,7 @@ kernel_t::kernel_t(size_t n) : size(n) , state(new nfa_state_t*[size]) , tvers(new size_t[size]) + , tlook(new size_t[size]) , order(new size_t[size]) {} @@ -19,6 +20,7 @@ kernel_t *kernel_t::copy(const kernel_t &k) kernel_t *kcopy = new kernel_t(n); memcpy(kcopy->state, k.state, n * sizeof(void*)); memcpy(kcopy->tvers, k.tvers, n * sizeof(size_t)); + memcpy(kcopy->tlook, k.tlook, n * sizeof(size_t)); memcpy(kcopy->order, k.order, n * sizeof(size_t)); return kcopy; } @@ -27,6 +29,7 @@ kernel_t::~kernel_t() { delete[] state; delete[] tvers; + delete[] tlook; delete[] order; } @@ -36,8 +39,9 @@ struct kernel_eq_t { return x->size == y->size && memcmp(x->state, y->state, x->size * sizeof(void*)) == 0 - && memcmp(x->tvers, y->tvers, x->size * sizeof(size_t)) == 0; - // no need to compare orders: if versions coincide, so do orders + && memcmp(x->tvers, y->tvers, x->size * sizeof(size_t)) == 0 + && memcmp(x->tlook, y->tlook, x->size * sizeof(size_t)) == 0; + // no need to compare orders: if versions and lookahead coincide, so do orders } }; @@ -61,6 +65,7 @@ bool kernels_t::operator()(const kernel_t *k1, const kernel_t *k2) // check that kernel sizes, NFA states and orders coincide const bool compatible = k1->size == k2->size && memcmp(k1->state, k2->state, k1->size * sizeof(void*)) == 0 + && memcmp(k1->tlook, k2->tlook, k1->size * sizeof(size_t)) == 0 && memcmp(k1->order, k2->order, k1->size * sizeof(size_t)) == 0; if (!compatible) return false; @@ -72,19 +77,16 @@ bool kernels_t::operator()(const kernel_t *k1, const kernel_t *k2) for (size_t i = 0; i < k1->size; ++i) { const tagver_t *xv = tagpool[k1->tvers[i]], - *yv = tagpool[k2->tvers[i]]; + *yv = tagpool[k2->tvers[i]], + *xl = tagpool[k2->tlook[i]]; for (size_t t = 0; t < ntag; ++t) { - const tagver_t x = xv[t], y = yv[t]; - // see note [mapping ignores items with lookahead tags] - if (x == TAGVER_CURSOR || x == TAGVER_BOTTOM - || y == TAGVER_CURSOR || y == TAGVER_BOTTOM) { - if (x == y) continue; - return false; - } + if (xl[t] != TAGVER_ZERO) continue; + const tagver_t x = xv[t], y = yv[t]; tagver_t &x0 = y2x[y], &y0 = x2y[x]; + if (y0 == TAGVER_ZERO && x0 == TAGVER_ZERO) { x0 = x; y0 = y; @@ -214,12 +216,14 @@ kernels_t::result_t kernels_t::insert(const closure_t &clos, tagver_t maxver) const clos_t &c = clos[i]; buffer->state[i] = c.state; buffer->tvers[i] = c.tvers; + buffer->tlook[i] = c.tlook; buffer->order[i] = c.order; } // get kernel hash uint32_t hash = static_cast(nkern); // seed hash = hash32(hash, buffer->state, nkern * sizeof(void*)); + hash = hash32(hash, buffer->tlook, nkern * sizeof(size_t)); hash = hash32(hash, buffer->order, nkern * sizeof(size_t)); // try to find identical kernel @@ -282,8 +286,7 @@ tcmd_t *kernels_t::commands1(const closure_t &closure) tcmd_t *kernels_t::commands2(const closure_t &closure) { - tcmd_t *copy = NULL, *save = NULL, **p; - cclositer_t c1 = closure.begin(), c2 = closure.end(), c; + tcmd_t *save = commands1(closure), *copy = NULL, *s, **p; // see note [save(X), copy(Y,X) optimization] for (tagver_t x = -max; x < max; ++x) { @@ -295,9 +298,9 @@ tcmd_t *kernels_t::commands2(const closure_t &closure) if (fixed(tags[t])) continue; const tagver_t ax = abs(x), ay = abs(y); - for (c = c1; c != c2 && tagpool[c->ttran][t] != y; ++c); - if (c != c2) { - save = tcpool.make_tcmd(save, ax, y < TAGVER_ZERO ? TAGVER_BOTTOM : TAGVER_CURSOR); + for (s = save; s && s->lhs != ay; s = s->next); + if (s) { + s->lhs = ax; } else if (x != y) { assert(ax != ay); copy = tcpool.make_tcmd(copy, ax, ay); @@ -319,11 +322,13 @@ static tcmd_t *finalizer(const clos_t &clos, size_t ridx, { tcpool_t &tcpool = dfa.tcpool; const Rule &rule = dfa.rules[ridx]; - const tagver_t *vers = tagpool[clos.tvers]; + const tagver_t + *look = tagpool[clos.tlook], + *vers = tagpool[clos.tvers]; tcmd_t *copy = NULL, *save = NULL, **p; for (size_t t = rule.ltag; t < rule.htag; ++t) { - const tagver_t v = vers[t]; + const tagver_t l = look[t], v = abs(vers[t]); tagver_t &f = dfa.finvers[t]; // don't waste versions on fixed tags @@ -334,10 +339,10 @@ static tcmd_t *finalizer(const clos_t &clos, size_t ridx, f = ++dfa.maxtagver; } - if (tcmd_t::iscopy(v)) { + if (l == TAGVER_ZERO) { copy = tcpool.make_tcmd(copy, f, abs(v)); } else { - save = tcpool.make_tcmd(save, f, v); + save = tcpool.make_tcmd(save, f, l); } } diff --git a/re2c/src/dfa/find_state.h b/re2c/src/dfa/find_state.h index 03d76793..45538294 100644 --- a/re2c/src/dfa/find_state.h +++ b/re2c/src/dfa/find_state.h @@ -14,6 +14,7 @@ struct kernel_t size_t size; nfa_state_t **state; size_t *tvers; // tag versions + size_t *tlook; // lookahead tags size_t *order; // see note [orbit order of closure items] explicit kernel_t(size_t n); -- 2.40.0