From d58c90b50b553d29ab75528830044fe4485ec8a3 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Wed, 5 Apr 2017 17:01:54 +0100 Subject: [PATCH] Started to add optional history for each tag. This patch adds tracking and saving tag history during determinization; however, optimizations and codegen totally neglect histories. --- re2c/src/dfa/closure.cc | 100 +++++++++++++++----------------- re2c/src/dfa/closure.h | 31 +++++++++- re2c/src/dfa/determinization.cc | 16 +++-- re2c/src/dfa/dump.cc | 51 ++++++++-------- re2c/src/dfa/fallback_tags.cc | 6 +- re2c/src/dfa/find_state.cc | 55 ++++++------------ re2c/src/dfa/find_state.h | 9 ++- re2c/src/dfa/tagpool.cc | 6 +- re2c/src/dfa/tagpool.h | 6 +- re2c/src/dfa/tcmd.cc | 20 +++++-- re2c/src/dfa/tcmd.h | 3 +- re2c/src/re/tag.h | 5 ++ 12 files changed, 157 insertions(+), 151 deletions(-) diff --git a/re2c/src/dfa/closure.cc b/re2c/src/dfa/closure.cc index 42f0589a..a93a33ee 100644 --- a/re2c/src/dfa/closure.cc +++ b/re2c/src/dfa/closure.cc @@ -11,13 +11,14 @@ 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); -static void update_versions(closure_t &clos, Tagpool &tagpool, tagver_t &maxver, tagver_t *newvers); +static tcmd_t *generate_versions(closure_t &clos, const std::vector &tags, Tagpool &tagpool, tcpool_t &tcpool, tagver_t &maxver, newvers_t &newvers); static void orders(closure_t &clos, Tagpool &tagpool, tagtree_t &tagtree, const std::vector &tags); 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, - bool lookahead, closure_t *shadow, const std::vector &tags) +tcmd_t *closure(closure_t &clos1, closure_t &clos2, Tagpool &tagpool, + tcpool_t &tcpool, tagtree_t &tagtree, std::valarray &rules, + tagver_t &maxver, newvers_t &newvers, bool lookahead, closure_t *shadow, + const std::vector &tags) { // build tagged epsilon-closure of the given set of NFA states clos2.clear(); @@ -38,8 +39,10 @@ void closure(closure_t &clos1, closure_t &clos2, Tagpool &tagpool, tagtree_t &ta } // merge tags from different rules, find nondeterministic tags - update_versions(clos2, tagpool, maxver, newvers); - if (shadow) update_versions(*shadow, tagpool, maxver, newvers); + tcmd_t *cmd = generate_versions(clos2, tags, tagpool, tcpool, maxver, newvers); + if (shadow) generate_versions(*shadow, tags, tagpool, tcpool, maxver, newvers); + + return cmd; } bool cmpby_rule_state(const clos_t &x, const clos_t &y) @@ -227,71 +230,64 @@ void lower_lookahead_to_transition(closure_t &clos) } } -void update_versions(closure_t &clos, Tagpool &tagpool, - tagver_t &maxver, tagver_t *newvers) +tcmd_t *generate_versions(closure_t &clos, const std::vector &tags, + Tagpool &tagpool, tcpool_t &tcpool, tagver_t &maxver, newvers_t &newvers) { + tcmd_t *cmd = NULL, *p; const size_t ntag = tagpool.ntags; - tagver_t *cur = tagpool.buffer1, - *bot = tagpool.buffer2, - *vers = tagpool.buffer3, - *tran = tagpool.buffer4; + tagver_t *vers = tagpool.buffer; clositer_t b = clos.begin(), e = clos.end(), c; // for each tag, if there is at least one tagged transition, // allocate new version (negative for bottom and positive for // normal transition, however absolute value should be unique // among all versions of all tags) - for (size_t t = 0; t < ntag; ++t) { - tagver_t &newcur = newvers[t], - &newbot = newvers[ntag + t]; - cur[t] = bot[t] = TAGVER_ZERO; - - for (c = b; c != e; ++c) { - if (tagpool[c->ttran][t] == TAGVER_CURSOR) { - if (newcur == TAGVER_ZERO) { - newcur = ++maxver; - } - cur[t] = newcur; - break; - } - } - - for (c = b; c != e; ++c) { - if (tagpool[c->ttran][t] == TAGVER_BOTTOM) { - if (newbot == TAGVER_ZERO) { - newbot = -(++maxver); - } - bot[t] = newbot; - break; + for (c = b; c != e; ++c) { + const tagver_t + *ls = tagpool[c->tlook], + *us = tagpool[c->ttran], + *vs = tagpool[c->tvers]; + for (size_t t = 0; t < ntag; ++t) { + const Tag &tag = tags[t]; + const tagver_t u = us[t]; + if (u == TAGVER_ZERO) continue; + + const tagver_t h = history(tag) ? vs[t] : TAGVER_ZERO; + newver_t x = {t, h, u}; + const tagver_t + n = (maxver + 1) * (u == TAGVER_BOTTOM ? -1 : 1), + m = newvers.insert(std::make_pair(x, n)).first->second; + if (n == m) ++maxver; + + // add action unless already have an identical one + if (fixed(tag) || (ls[t] && !history(tag))) continue; + for (p = cmd; p; p = p->next) { + if (p->lhs == abs(m) && p->rhs == u && p->pred == h) break; } + if (!p) cmd = tcpool.make_tcmd(cmd, abs(m), u, h); } } - // set transition tags and update versions + // update tag versions in closure for (c = b; c != e; ++c) { if (c->ttran == ZERO_TAGS) continue; - const tagver_t - *oldt = tagpool[c->ttran], - *oldv = tagpool[c->tvers]; - - for (size_t i = 0; i < ntag; ++i) { - const tagver_t ov = oldv[i], ot = oldt[i]; - tagver_t &v = vers[i], &t = tran[i]; - - if (ot == TAGVER_CURSOR) { - v = t = cur[i]; - } else if (ot == TAGVER_BOTTOM) { - v = t = bot[i]; + *us = tagpool[c->ttran], + *vs = tagpool[c->tvers]; + for (size_t t = 0; t < ntag; ++t) { + const tagver_t u = us[t], v = vs[t], + h = history(tags[t]) ? v : TAGVER_ZERO; + if (u == TAGVER_ZERO) { + vers[t] = v; } else { - v = ov; - t = TAGVER_ZERO; + newver_t x = {t, h, u}; + vers[t] = newvers[x]; } } - c->tvers = tagpool.insert(vers); - c->ttran = tagpool.insert(tran); } + + return cmd; } /* note [POSIX disambiguation] @@ -403,7 +399,7 @@ void orders(closure_t &clos, Tagpool &tagpool, } // flatten lookahead tags (take the last on each path) - tagver_t *look = tagpool.buffer1; + tagver_t *look = tagpool.buffer; for (clositer_t c = clos.begin(); c != clos.end(); ++c) { if (c->tlook == ZERO_TAGS) continue; const tagver_t *oldl = tagpool[c->tlook]; diff --git a/re2c/src/dfa/closure.h b/re2c/src/dfa/closure.h index 7ae7df44..ff5be7e3 100644 --- a/re2c/src/dfa/closure.h +++ b/re2c/src/dfa/closure.h @@ -2,6 +2,7 @@ #define _RE2C_DFA_CLOSURE_ #include "src/util/c99_stdint.h" +#include #include "src/dfa/dfa.h" #include "src/dfa/tagtree.h" @@ -27,9 +28,33 @@ typedef std::vector closure_t; typedef closure_t::iterator clositer_t; 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, - bool lookahead, closure_t *shadow, const std::vector &tags); +struct newver_t +{ + size_t tag; + tagver_t ver; + tagver_t act; +}; + +inline bool operator<(const newver_t &x, const newver_t &y) +{ + if (x.tag < y.tag) return true; + if (x.tag > y.tag) return false; + + if (x.ver < y.ver) return true; + if (x.ver > y.ver) return false; + + if (x.act < y.act) return true; + if (x.act > y.act) return false; + + return false; +} + +typedef std::map newvers_t; + +tcmd_t *closure(closure_t &clos1, closure_t &clos2, Tagpool &tagpool, + tcpool_t &tcpool, tagtree_t &tagtree, std::valarray &rules, + tagver_t &maxver, newvers_t &newvers, 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 f80315a4..733bfcfd 100644 --- a/re2c/src/dfa/determinization.cc +++ b/re2c/src/dfa/determinization.cc @@ -67,7 +67,8 @@ dfa_t::dfa_t(const nfa_t &nfa, const opt_t *opts, tagtree_t tagtree(ntag); kernels_t kernels(tagpool, tcpool, tags); closure_t clos1, clos2; - tagver_t *newvers = new tagver_t[ntag * 2]; + newvers_t newvers; + tcmd_t *acts; dump_dfa_t dump(*this, tagpool, nfa, opts->dump_dfa_raw); // all-zero tag configuration must have static number zero @@ -87,22 +88,19 @@ dfa_t::dfa_t(const nfa_t &nfa, const opt_t *opts, 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, lookahead, dump.shadow, tags); - find_state(*this, dfa_t::NIL, 0/* any */, kernels, clos2, dump); + acts = closure(clos1, clos2, tagpool, tcpool, tagtree, rules, maxtagver, newvers, lookahead, dump.shadow, tags); + find_state(*this, dfa_t::NIL, 0/* any */, kernels, clos2, acts, dump); for (size_t i = 0; i < kernels.size(); ++i) { - std::fill(newvers, newvers + ntag * 2, TAGVER_ZERO); + newvers.clear(); for (size_t c = 0; c < nchars; ++c) { reach(kernels[i], clos1, charset[c]); - closure(clos1, clos2, tagpool, tagtree, rules, maxtagver, newvers, lookahead, dump.shadow, tags); - find_state(*this, i, c, kernels, clos2, dump); + acts = closure(clos1, clos2, tagpool, tcpool, tagtree, rules, maxtagver, newvers, lookahead, dump.shadow, tags); + find_state(*this, i, c, kernels, clos2, acts, dump); } } warn_nondeterministic_tags(kernels, tagpool, tags, rules, cond, warn); - - delete[] newvers; } /* diff --git a/re2c/src/dfa/dump.cc b/re2c/src/dfa/dump.cc index a61e6fc3..73ec7bc7 100644 --- a/re2c/src/dfa/dump.cc +++ b/re2c/src/dfa/dump.cc @@ -8,7 +8,7 @@ namespace re2c static void dump_tcmd_or_tcid(tcmd_t *const *tcmd, const tcid_t *tcid, size_t sym, const tcpool_t &tcpool); static void dump_tcmd(const tcmd_t *p); static const char *tagname(const Tag &t); -static void dump_tags(const Tagpool &tagpool, size_t ttran); +static void dump_tags(const Tagpool &tagpool, size_t ttran, size_t tvers); dump_dfa_t::dump_dfa_t(const dfa_t &d, const Tagpool &pool, const nfa_t &n, bool dbg) : debug(dbg) @@ -87,7 +87,7 @@ void dump_dfa_t::closure(const closure_t &clos, uint32_t state, bool isnew) " CELLBORDER=\"1\"" ">", isnew ? "" : "i", state); - tagver_t *look = tagpool.buffer1; + tagver_t *look = tagpool.buffer; 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); @@ -120,12 +120,12 @@ void dump_dfa_t::state0(const closure_t &clos) fprintf(stderr, " void [shape=point]\n"); for (cclositer_t c = shadow->begin(); c != shadow->end(); ++c) { fprintf(stderr, " void -> 0:_%u_%ld:w [style=dotted color=lightgray fontcolor=lightgray label=\"", index(c->state), c - shadow->begin()); - dump_tags(tagpool, c->ttran); + dump_tags(tagpool, c->ttran, c->tvers); fprintf(stderr, "\"]\n"); } for (cclositer_t c = clos.begin(); c != clos.end(); ++c) { fprintf(stderr, " void -> 0:%u:w [style=dotted label=\"", index(c->state)); - dump_tags(tagpool, c->ttran); + dump_tags(tagpool, c->ttran, c->tvers); fprintf(stderr, "\"]\n"); } } @@ -157,13 +157,13 @@ void dump_dfa_t::state(const closure_t &clos, size_t state, size_t symbol, bool for (cclositer_t b = shadow->begin(), c = b; c != shadow->end(); ++c) { fprintf(stderr, " %u:%u:e -> %s%u:_%u_%ld:w [color=lightgray fontcolor=lightgray label=\"%u", x, index(c->origin), prefix, z, index(c->state), c - b, a); - dump_tags(tagpool, c->ttran); + dump_tags(tagpool, c->ttran, c->tvers); fprintf(stderr, "\"]\n"); } for (cclositer_t c = clos.begin(); c != clos.end(); ++c) { fprintf(stderr, " %u:%u:e -> %s%u:%u:w [label=\"%u", x, index(c->origin), prefix, z, index(c->state), a); - dump_tags(tagpool, c->ttran); + dump_tags(tagpool, c->ttran, c->tvers); fprintf(stderr, "\"]\n"); } } @@ -205,7 +205,7 @@ void dump_dfa(const dfa_t &dfa) fprintf(stderr, " n [shape=point]" " n -> n0 [style=dotted label=\""); - dump_tcmd_or_tcid(&dfa.tcmd0, &dfa.tcid0, 0, dfa.tcpool); + dump_tcmd_or_tcid(dfa.tcmd0 ? &dfa.tcmd0 : NULL, &dfa.tcid0, 0, dfa.tcpool); fprintf(stderr, "\"]\n"); for (uint32_t i = 0; i < nstate; ++i) { @@ -255,13 +255,8 @@ void dump_dfa(const dfa_t &dfa) void dump_tcmd_or_tcid(tcmd_t *const *tcmd, const tcid_t *tcid, size_t sym, const tcpool_t &tcpool) { - if (tcmd) { - const tcmd_t *cmd = tcmd[sym]; - dump_tcmd(cmd); - } else { - const tcmd_t *cmd = tcpool[tcid[sym]]; - dump_tcmd(cmd); - } + const tcmd_t *cmd = tcmd ? tcmd[sym] : tcpool[tcid[sym]]; + dump_tcmd(cmd); } void dump_tcmd(const tcmd_t *p) @@ -270,13 +265,15 @@ void dump_tcmd(const tcmd_t *p) fprintf(stderr, "/"); for (; p; p = p->next) { - const tagver_t l = p->lhs, r = p->rhs; - if (r == TAGVER_BOTTOM) { - fprintf(stderr, "%d%s ", l, "↓"); - } else if (r == TAGVER_CURSOR) { - fprintf(stderr, "%d%s ", l, "↑"); - } else { + const tagver_t l = p->lhs, r = p->rhs, v = p->pred; + if (tcmd_t::iscopy(r)) { fprintf(stderr, "%d=%d ", l, r); + } else { + fprintf(stderr, "%d", l); + if (v != TAGVER_ZERO) { + fprintf(stderr, "=%d", v); + } + fprintf(stderr, "%s ", r == TAGVER_BOTTOM ? "↓" : "↑"); } } } @@ -286,17 +283,19 @@ const char *tagname(const Tag &t) return t.name ? t.name->c_str() : ""; } -void dump_tags(const Tagpool &tagpool, size_t ttran) +void dump_tags(const Tagpool &tagpool, size_t ttran, size_t tvers) { if (ttran == ZERO_TAGS) return; fprintf(stderr, "/"); - const tagver_t *tran = tagpool[ttran]; - for (size_t t = 0; t < tagpool.ntags; ++t) { - const tagver_t v = tran[t]; - if (v < TAGVER_ZERO) { + const tagver_t + *tran = tagpool[ttran], + *vers = tagpool[tvers]; + for (size_t i = 0; i < tagpool.ntags; ++i) { + const tagver_t t = tran[i], v = vers[i]; + if (t < TAGVER_ZERO) { fprintf(stderr, "%d↓ ", -v); - } else if (v > TAGVER_ZERO) { + } else if (t > TAGVER_ZERO) { fprintf(stderr, "%d↑ ", v); } } diff --git a/re2c/src/dfa/fallback_tags.cc b/re2c/src/dfa/fallback_tags.cc index d4656071..a196db86 100644 --- a/re2c/src/dfa/fallback_tags.cc +++ b/re2c/src/dfa/fallback_tags.cc @@ -72,12 +72,12 @@ void insert_fallback_tags(dfa_t &dfa) tcmd_t *p = s->tcmd[nsym], *&f = s->tcmd[nsym + 1]; for (; p; p = p->next) { - const tagver_t l = p->lhs, r = p->rhs; + const tagver_t l = p->lhs, r = p->rhs, v = p->pred; // 'save' commands are the same as for final transition // non-overwritten tags need 'copy' on fallback transition if (!tcmd_t::iscopy(r) || !owrt[r]) { - f = pool.make_tcmd(f, l, r); + f = pool.make_tcmd(f, l, r, v); continue; } @@ -87,7 +87,7 @@ void insert_fallback_tags(dfa_t &dfa) size_t j = s->arcs[c]; if (j != dfa_t::NIL && dfa.states[j]->fallthru) { tcmd_t *&q = s->tcmd[c]; - q = pool.make_tcmd(q, l, r); + q = pool.make_tcmd(q, l, r, v); } } } diff --git a/re2c/src/dfa/find_state.cc b/re2c/src/dfa/find_state.cc index bd8fe66e..62237473 100644 --- a/re2c/src/dfa/find_state.cc +++ b/re2c/src/dfa/find_state.cc @@ -82,7 +82,7 @@ bool kernels_t::operator()(const kernel_t *k1, const kernel_t *k2) for (size_t t = 0; t < ntag; ++t) { // see note [mapping ignores items with lookahead tags] - if (xl[t] != TAGVER_ZERO) continue; + if (xl[t] != TAGVER_ZERO && !history(tags[t])) continue; const tagver_t x = xv[t], y = yv[t]; tagver_t &x0 = y2x[y], &y0 = x2y[x]; @@ -199,7 +199,8 @@ const kernel_t *kernels_t::operator[](size_t idx) const * more complex analysis (and are not so useful after all), so we drop them. */ -kernels_t::result_t kernels_t::insert(const closure_t &clos, tagver_t maxver) +kernels_t::result_t kernels_t::insert(const closure_t &clos, + tcmd_t *acts, tagver_t maxver) { const size_t nkern = clos.size(); size_t x = dfa_t::NIL; @@ -229,36 +230,16 @@ kernels_t::result_t kernels_t::insert(const closure_t &clos, tagver_t maxver) // try to find identical kernel kernel_eq_t eq; x = lookup.find_with(hash, buffer, eq); - if (x != index_t::NIL) return result_t(x, commands1(clos), false); + if (x != index_t::NIL) return result_t(x, acts, false); // else try to find mappable kernel // see note [bijective mappings] x = lookup.find_with(hash, buffer, *this); - if (x != index_t::NIL) return result_t(x, commands2(clos), false); + if (x != index_t::NIL) return result_t(x, actions(acts), false); // otherwise add new kernel x = lookup.push(hash, kernel_t::copy(*buffer)); - return result_t(x, commands1(clos), true); -} - -tcmd_t *kernels_t::commands1(const closure_t &closure) -{ - tcmd_t *cmd = NULL; - cclositer_t c1 = closure.begin(), c2 = closure.end(), c; - tagver_t v; - - // at most one new cursor and one new bottom version per tag - // no mapping => only save commands, no copy commands - for (size_t t = 0; t < tagpool.ntags; ++t) { - if (fixed(tags[t])) continue; - - for (c = c1; c != c2 && (v = tagpool[c->ttran][t]) <= TAGVER_ZERO; ++c); - if (c != c2) cmd = tcpool.make_tcmd(cmd, v, TAGVER_CURSOR); - - for (c = c1; c != c2 && (v = tagpool[c->ttran][t]) >= TAGVER_ZERO; ++c); - if (c != c2) cmd = tcpool.make_tcmd(cmd, -v, TAGVER_BOTTOM); - } - return cmd; + return result_t(x, acts, true); } /* note [save(X), copy(Y,X) optimization] @@ -284,9 +265,9 @@ tcmd_t *kernels_t::commands1(const closure_t &closure) * cannot affect the check. */ -tcmd_t *kernels_t::commands2(const closure_t &closure) +tcmd_t *kernels_t::actions(tcmd_t *save) { - tcmd_t *save = commands1(closure), *copy = NULL, *s, **p; + tcmd_t *copy = NULL, *s, **p; // see note [save(X), copy(Y,X) optimization] for (tagver_t x = -max; x < max; ++x) { @@ -303,7 +284,7 @@ tcmd_t *kernels_t::commands2(const closure_t &closure) s->lhs = ax; } else if (x != y) { assert(ax != ay); - copy = tcpool.make_tcmd(copy, ax, ay); + copy = tcpool.make_tcmd(copy, ax, ay, 0); } } @@ -318,7 +299,7 @@ tcmd_t *kernels_t::commands2(const closure_t &closure) } static tcmd_t *finalizer(const clos_t &clos, size_t ridx, - dfa_t &dfa, const Tagpool &tagpool) + dfa_t &dfa, const Tagpool &tagpool, const std::vector &tags) { tcpool_t &tcpool = dfa.tcpool; const Rule &rule = dfa.rules[ridx]; @@ -328,7 +309,8 @@ static tcmd_t *finalizer(const clos_t &clos, size_t ridx, tcmd_t *copy = NULL, *save = NULL, **p; for (size_t t = rule.ltag; t < rule.htag; ++t) { - const tagver_t l = look[t], v = abs(vers[t]); + const tagver_t l = look[t], v = abs(vers[t]), + h = history(tags[t]) ? v : TAGVER_ZERO; tagver_t &f = dfa.finvers[t]; // don't waste versions on fixed tags @@ -340,9 +322,9 @@ static tcmd_t *finalizer(const clos_t &clos, size_t ridx, } if (l == TAGVER_ZERO) { - copy = tcpool.make_tcmd(copy, f, abs(v)); + copy = tcpool.make_tcmd(copy, f, v, TAGVER_ZERO); } else { - save = tcpool.make_tcmd(save, f, l); + save = tcpool.make_tcmd(save, f, l, h); } } @@ -353,11 +335,11 @@ static tcmd_t *finalizer(const clos_t &clos, size_t ridx, return copy; } -void find_state(dfa_t &dfa, size_t state, size_t symbol, - kernels_t &kernels, const closure_t &closure, dump_dfa_t &dump) +void find_state(dfa_t &dfa, size_t state, size_t symbol, kernels_t &kernels, + const closure_t &closure, tcmd_t *acts, dump_dfa_t &dump) { const kernels_t::result_t - result = kernels.insert(closure, dfa.maxtagver); + result = kernels.insert(closure, acts, dfa.maxtagver); if (result.isnew) { // create new DFA state @@ -370,7 +352,8 @@ void find_state(dfa_t &dfa, size_t state, size_t symbol, c = std::find_if(c1, c2, clos_t::fin); if (c != c2) { t->rule = c->state->rule; - t->tcmd[dfa.nchars] = finalizer(*c, t->rule, dfa, kernels.tagpool); + t->tcmd[dfa.nchars] = finalizer(*c, t->rule, dfa, + kernels.tagpool, kernels.tags); dump.final(result.state, c->state); } } diff --git a/re2c/src/dfa/find_state.h b/re2c/src/dfa/find_state.h index 45538294..ecb6f347 100644 --- a/re2c/src/dfa/find_state.h +++ b/re2c/src/dfa/find_state.h @@ -65,15 +65,14 @@ public: void init(tagver_t v, size_t k); size_t size() const; const kernel_t* operator[](size_t idx) const; - result_t insert(const closure_t &clos, tagver_t maxver); + result_t insert(const closure_t &clos, tcmd_t *acts, tagver_t maxver); bool operator()(const kernel_t *k1, const kernel_t *k2); - tcmd_t *commands1(const closure_t &closure); - tcmd_t *commands2(const closure_t &closure); + tcmd_t *actions(tcmd_t *save); FORBID_COPY(kernels_t); }; -void find_state(dfa_t &dfa, size_t state, size_t symbol, - kernels_t &kernels, const closure_t &closure, dump_dfa_t &dump); +void find_state(dfa_t &dfa, size_t state, size_t symbol, kernels_t &kernels, + const closure_t &closure, tcmd_t *acts, dump_dfa_t &dump); } // namespace re2c diff --git a/re2c/src/dfa/tagpool.cc b/re2c/src/dfa/tagpool.cc index 37930d7e..0ac8734c 100644 --- a/re2c/src/dfa/tagpool.cc +++ b/re2c/src/dfa/tagpool.cc @@ -20,12 +20,8 @@ struct eqtag_t Tagpool::Tagpool(size_t n) : lookup() - , buffer(new tagver_t[n * 5]) , ntags(n) - , buffer1(&buffer[n * 1]) - , buffer2(&buffer[n * 2]) - , buffer3(&buffer[n * 3]) - , buffer4(&buffer[n * 4]) + , buffer(new tagver_t[n]) , maxclos(0) , orders(NULL) {} diff --git a/re2c/src/dfa/tagpool.h b/re2c/src/dfa/tagpool.h index da6545f6..20ee9a06 100644 --- a/re2c/src/dfa/tagpool.h +++ b/re2c/src/dfa/tagpool.h @@ -15,14 +15,10 @@ struct Tagpool private: typedef lookup_t taglookup_t; taglookup_t lookup; - tagver_t *buffer; public: const size_t ntags; - tagver_t *buffer1; - tagver_t *buffer2; - tagver_t *buffer3; - tagver_t *buffer4; + tagver_t *buffer; size_t maxclos; tagver_t *orders; diff --git a/re2c/src/dfa/tcmd.cc b/re2c/src/dfa/tcmd.cc index 7493d0ec..0ccdb731 100644 --- a/re2c/src/dfa/tcmd.cc +++ b/re2c/src/dfa/tcmd.cc @@ -12,19 +12,26 @@ void tcmd_t::swap(tcmd_t &x, tcmd_t &y) { std::swap(x.lhs, y.lhs); std::swap(x.rhs, y.rhs); + std::swap(x.pred, y.pred); } bool tcmd_t::less(const tcmd_t &x, const tcmd_t &y) { - const tagver_t - lx = x.lhs, ly = y.lhs, - rx = x.rhs, ry = y.rhs; - return (lx < ly) || (lx == ly && rx < ry); + if (x.lhs < y.lhs) return true; + if (x.lhs > y.lhs) return false; + + if (x.rhs < y.rhs) return true; + if (x.rhs > y.rhs) return false; + + if (x.pred < y.pred) return true; + if (x.pred > y.pred) return false; + + return false; } bool tcmd_t::equal(const tcmd_t &x, const tcmd_t &y) { - return x.lhs == y.lhs && x.rhs == y.rhs; + return x.lhs == y.lhs && x.rhs == y.rhs && x.pred == y.pred; } /* note [topological ordering of copy commands] @@ -125,12 +132,13 @@ tcpool_t::tcpool_t() assert(TCID0 == insert(NULL)); } -tcmd_t *tcpool_t::make_tcmd(tcmd_t *next, tagver_t lhs, tagver_t rhs) +tcmd_t *tcpool_t::make_tcmd(tcmd_t *next, tagver_t lhs, tagver_t rhs, tagver_t pred) { tcmd_t *p = alc.alloct(1); p->next = next; p->lhs = lhs; p->rhs = rhs; + p->pred = pred; return p; } diff --git a/re2c/src/dfa/tcmd.h b/re2c/src/dfa/tcmd.h index eb2908fb..d4d382e7 100644 --- a/re2c/src/dfa/tcmd.h +++ b/re2c/src/dfa/tcmd.h @@ -15,6 +15,7 @@ struct tcmd_t tcmd_t *next; tagver_t lhs; // left hand side tagver_t rhs; // right hand side + tagver_t pred; // history static bool less(const tcmd_t &x, const tcmd_t &y); static void swap(tcmd_t &x, tcmd_t &y); @@ -38,7 +39,7 @@ class tcpool_t public: tcpool_t(); - tcmd_t *make_tcmd(tcmd_t *next, tagver_t lhs, tagver_t rhs); + tcmd_t *make_tcmd(tcmd_t *next, tagver_t lhs, tagver_t rhs, tagver_t pred); tcid_t insert(const tcmd_t *tcmd); const tcmd_t *operator[](tcid_t id) const; }; diff --git a/re2c/src/re/tag.h b/re2c/src/re/tag.h index 2dec17e2..a1d59958 100644 --- a/re2c/src/re/tag.h +++ b/re2c/src/re/tag.h @@ -68,6 +68,11 @@ inline bool preorbit(const std::vector &tags, size_t idx) && tags[idx + 2].ncap == ncap + 2; } +inline bool history(const Tag &/*tag*/) +{ + return false; +} + } // namespace re2c #endif // _RE2C_RE_TAG_ -- 2.40.0