From 2d145e666fd88c16f84a28e48baf101c0ef3f384 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Sat, 8 Apr 2017 09:46:41 +0100 Subject: [PATCH] When mapping states, avoid double substitution in 'save' commands. When mapping states, we need to create a list of 'copy' commands. However, if there is a 'save' command with LHS equal to RHS of the 'copy' command, then instead of the 'copy' command we just fix LHS of the 'save' command, as explained in this note: /* note [save(X), copy(Y,X) optimization] * * save(X) command followed by a copy(Y,X) command can be optimized to * save(Y). This helps reduce the number commands and versions (new version * X is gone), but what is more important, it allows to put copy commands * in front of save commands. This order is necessary when it comes to * fallback commands. * * Note that in case of injective mapping there may be more than one copy * command matching the same save command: save(X), copy(Y,X), copy(Z,X). * In this case save command must be replicated for each copy command: * save(Y), save(Z). * * For each save(X) command there must be at least one copy(Y,X) command * (exactly one case of bijective mapping). This is because X version in * save(X) command must be a new version which cannot occur in the older * DFA state. Thus all save commands are transformed (maybe replicated) by * copy commands, and some copy commands are erased by save commands. * * This optimization is applied after checking priority violation, so it * cannot affect the check. */ However, the previous implementation would sometimes erroneously re-fix the already fixed 'save' commands. This patch rewrites it in a way that avoids re-fixing. --- re2c/src/dfa/find_state.cc | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-) diff --git a/re2c/src/dfa/find_state.cc b/re2c/src/dfa/find_state.cc index 62237473..95a85423 100644 --- a/re2c/src/dfa/find_state.cc +++ b/re2c/src/dfa/find_state.cc @@ -265,32 +265,31 @@ kernels_t::result_t kernels_t::insert(const closure_t &clos, * cannot affect the check. */ -tcmd_t *kernels_t::actions(tcmd_t *save) +tcmd_t *kernels_t::actions(tcmd_t *acts) { - tcmd_t *copy = NULL, *s, **p; + tcmd_t *copy = NULL, *a, **pa; + // fix LHS of 'save' commands to reuse old version // see note [save(X), copy(Y,X) optimization] - for (tagver_t x = -max; x < max; ++x) { - const tagver_t y = x2y[x]; - if (y == TAGVER_ZERO) continue; - - // at most one new cursor and one new bottom version per tag - const size_t t = x2t[x]; - if (fixed(tags[t])) continue; + for (a = acts; a; a = a->next) { + const tagver_t + y = a->lhs * (a->rhs == TAGVER_BOTTOM ? -1 : 1), + x = y2x[y]; + a->lhs = abs(x); + y2x[y] = x2y[x] = TAGVER_ZERO; + } - const tagver_t ax = abs(x), ay = abs(y); - for (s = save; s && s->lhs != ay; s = s->next); - if (s) { - s->lhs = ax; - } else if (x != y) { + for (tagver_t x = -max; x < max; ++x) { + const tagver_t y = x2y[x], ax = abs(x), ay = abs(y); + if (y != TAGVER_ZERO && x != y && !fixed(tags[x2t[x]])) { assert(ax != ay); copy = tcpool.make_tcmd(copy, ax, ay, 0); } } // join 'copy' and 'save' commands - for (p = © *p; p = &(*p)->next); - *p = save; + for (pa = © *pa; pa = &(*pa)->next); + *pa = acts; // see note [topological ordering of copy commands] tcmd_t::topsort(©, indeg); -- 2.40.0