From 251f292c2be185532036cd403bb13c4cbbe90be3 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Mon, 13 Aug 2018 21:47:13 +0100 Subject: [PATCH] Merged a couple of small headers into one. --- re2c/Makefile.am | 2 - re2c/src/dfa/closure.cc | 8 +- re2c/src/dfa/closure.h | 70 ----------------- re2c/src/dfa/determinization.cc | 24 ++++-- re2c/src/dfa/determinization.h | 134 +++++++++++++++++++++++++------- re2c/src/dfa/dump.cc | 35 +++++---- re2c/src/dfa/find_state.cc | 4 +- re2c/src/dfa/find_state.h | 56 ------------- re2c/src/dfa/tagpool.cc | 9 +-- re2c/src/dfa/tagpool.h | 18 +---- re2c/src/dfa/tagtree.cc | 2 +- 11 files changed, 158 insertions(+), 204 deletions(-) delete mode 100644 re2c/src/dfa/closure.h delete mode 100644 re2c/src/dfa/find_state.h diff --git a/re2c/Makefile.am b/re2c/Makefile.am index f1479dad..abffc587 100644 --- a/re2c/Makefile.am +++ b/re2c/Makefile.am @@ -23,11 +23,9 @@ SRC_HDR = \ src/adfa/adfa.h \ src/adfa/dump.h \ src/dfa/cfg/cfg.h \ - src/dfa/closure.h \ src/dfa/determinization.h \ src/dfa/dfa.h \ src/dfa/dump.h \ - src/dfa/find_state.h \ src/dfa/tagpool.h \ src/dfa/tagtree.h \ src/dfa/tcmd.h \ diff --git a/re2c/src/dfa/closure.cc b/re2c/src/dfa/closure.cc index 5323bc84..17e1f58f 100644 --- a/re2c/src/dfa/closure.cc +++ b/re2c/src/dfa/closure.cc @@ -9,7 +9,6 @@ #include #include "src/conf/opt.h" -#include "src/dfa/closure.h" #include "src/dfa/determinization.h" #include "src/dfa/dfa.h" #include "src/dfa/tagpool.h" @@ -17,6 +16,7 @@ #include "src/nfa/nfa.h" #include "src/re/rule.h" + namespace re2c { @@ -210,8 +210,8 @@ void closure_posix(determ_context_t &ctx) const closure_t &init = ctx.dc_reached; closure_t &done = ctx.dc_closure; std::stack - &topsort = ctx.dc_tagpool.astack, - &linear = ctx.dc_tagpool.bstack; + &topsort = ctx.dc_stack_topsort, + &linear = ctx.dc_stack_linear; nfa_state_t *q, *p; done.clear(); @@ -301,7 +301,7 @@ void closure_leftmost(determ_context_t &ctx) { const closure_t &init = ctx.dc_reached; closure_t &done = ctx.dc_closure; - std::stack &todo = ctx.dc_tagpool.cstack; + std::stack &todo = ctx.dc_stack_dfs; // enqueue all initial states done.clear(); diff --git a/re2c/src/dfa/closure.h b/re2c/src/dfa/closure.h deleted file mode 100644 index 4e75e12c..00000000 --- a/re2c/src/dfa/closure.h +++ /dev/null @@ -1,70 +0,0 @@ -#ifndef _RE2C_DFA_CLOSURE_ -#define _RE2C_DFA_CLOSURE_ - -#include -#include -#include - -#include "src/dfa/dfa.h" -#include "src/dfa/tagtree.h" -#include "src/nfa/nfa.h" -#include "src/re/tag.h" -#include "src/util/slab_allocator.h" - -namespace re2c -{ - -struct Tagpool; -struct dfa_t; -struct tcmd_t; - -typedef slab_allocator_t<> allocator_t; - -struct clos_t -{ - nfa_state_t *state; - uint32_t origin; - uint32_t tvers; // vector of tag versions (including lookahead tags) - hidx_t ttran; // history of transition tags - hidx_t tlook; // history of lookahead tags - - static inline bool fin(const clos_t &c) { return c.state->type == nfa_state_t::FIN; } - static inline bool ran(const clos_t &c) { return c.state->type == nfa_state_t::RAN; } -}; - -typedef std::vector closure_t; -typedef closure_t::iterator clositer_t; -typedef closure_t::const_iterator cclositer_t; -typedef closure_t::reverse_iterator rclositer_t; -typedef closure_t::const_reverse_iterator rcclositer_t; - -struct newver_t -{ - size_t tag; - tagver_t base; - hidx_t history; -}; - -struct newver_cmp_t -{ - tagtree_t &history; - - explicit newver_cmp_t(tagtree_t &h) : history(h) {} - - bool operator()(const newver_t &x, const newver_t &y) const - { - if (x.tag < y.tag) return true; - if (x.tag > y.tag) return false; - - if (x.base < y.base) return true; - if (x.base > y.base) return false; - - return history.compare_reversed(x.history, y.history, x.tag) < 0; - } -}; - -typedef std::map newvers_t; - -} // namespace re2c - -#endif // _RE2C_DFA_CLOSURE_ diff --git a/re2c/src/dfa/determinization.cc b/re2c/src/dfa/determinization.cc index e7072b91..2bff8819 100644 --- a/re2c/src/dfa/determinization.cc +++ b/re2c/src/dfa/determinization.cc @@ -10,11 +10,9 @@ #include "src/conf/opt.h" #include "src/conf/warn.h" -#include "src/dfa/closure.h" #include "src/dfa/dfa.h" #include "src/dfa/determinization.h" #include "src/dfa/dump.h" -#include "src/dfa/find_state.h" #include "src/dfa/tagpool.h" #include "src/dfa/tagtree.h" #include "src/dfa/tcmd.h" @@ -23,6 +21,7 @@ #include "src/re/tag.h" #include "src/util/range.h" + namespace re2c { @@ -206,6 +205,7 @@ determ_context_t::determ_context_t(const opt_t *opts, Warn &warn , dc_condname(condname) , dc_nfa(nfa) , dc_dfa(dfa) + , dc_allocator() , dc_origin(dfa_t::NIL) , dc_target(dfa_t::NIL) , dc_symbol(0) @@ -213,12 +213,14 @@ determ_context_t::determ_context_t(const opt_t *opts, Warn &warn , dc_reached() , dc_closure() , dc_prectbl(NULL) - , dc_tagpool(opts, nfa.tags.size()) - , dc_allocator(dc_tagpool.alc) - , dc_tagtrie(dc_tagpool.history) + , dc_tagpool(nfa.tags.size()) + , dc_tagtrie() , dc_kernels() , dc_buffers(dc_allocator) , dc_newvers(newver_cmp_t(dc_tagtrie)) + , dc_stack_topsort() + , dc_stack_linear() + , dc_stack_dfs() , dc_dump(opts) {} @@ -234,5 +236,17 @@ dfa_t::~dfa_t() } } + +bool newver_cmp_t::operator()(const newver_t &x, const newver_t &y) const +{ + if (x.tag < y.tag) return true; + if (x.tag > y.tag) return false; + + if (x.base < y.base) return true; + if (x.base > y.base) return false; + + return history.compare_reversed(x.history, y.history, x.tag) < 0; +} + } // namespace re2c diff --git a/re2c/src/dfa/determinization.h b/re2c/src/dfa/determinization.h index 4ac2a502..3cb28cd9 100644 --- a/re2c/src/dfa/determinization.h +++ b/re2c/src/dfa/determinization.h @@ -1,15 +1,21 @@ #ifndef _RE2C_DFA_DETERMINIZATION_ #define _RE2C_DFA_DETERMINIZATION_ +#include #include "src/util/c99_stdint.h" +#include +#include #include +#include -#include "src/dfa/closure.h" +#include "src/nfa/nfa.h" #include "src/dfa/dump.h" #include "src/dfa/tagpool.h" #include "src/dfa/tagtree.h" -#include "src/dfa/find_state.h" #include "src/util/forbid_copy.h" +#include "src/util/lookup.h" +#include "src/util/slab_allocator.h" + namespace re2c { @@ -17,44 +23,120 @@ namespace re2c // fwd struct opt_t; struct Warn; -struct nfa_t; struct dfa_t; +struct tcmd_t; + + +typedef slab_allocator_t<> allocator_t; + + +struct clos_t +{ + nfa_state_t *state; + uint32_t origin; + uint32_t tvers; // vector of tag versions (including lookahead tags) + hidx_t ttran; // history of transition tags + hidx_t tlook; // history of lookahead tags + + static inline bool fin(const clos_t &c) { return c.state->type == nfa_state_t::FIN; } + static inline bool ran(const clos_t &c) { return c.state->type == nfa_state_t::RAN; } +}; + + +typedef std::vector closure_t; +typedef closure_t::iterator clositer_t; +typedef closure_t::const_iterator cclositer_t; +typedef closure_t::reverse_iterator rclositer_t; +typedef closure_t::const_reverse_iterator rcclositer_t; + + +struct newver_t +{ + size_t tag; + tagver_t base; + hidx_t history; +}; + + +struct newver_cmp_t +{ + tagtree_t &history; + + explicit newver_cmp_t(tagtree_t &h) : history(h) {} + bool operator()(const newver_t &, const newver_t &) const; +}; + + +typedef std::map newvers_t; + + +struct kernel_t +{ + size_t size; + const prectable_t *prectbl; + nfa_state_t **state; + uint32_t *tvers; // tag versions + hidx_t *tlook; // lookahead tags + + FORBID_COPY(kernel_t); +}; + + +struct kernel_buffers_t +{ + size_t maxsize; + kernel_t *kernel; + tagver_t cap; // capacity (greater or equal to max) + tagver_t max; // maximal tag version + char *memory; + tagver_t *x2y; + tagver_t *y2x; + size_t *x2t; + uint32_t *indegree; + tcmd_t *backup_actions; + + explicit kernel_buffers_t(allocator_t &alc); +}; + + +typedef lookup_t kernels_t; + struct determ_context_t { // determinization input - const opt_t *dc_opts; // options - Warn &dc_warn; // warnings - const std::string &dc_condname; // the name of current condition (with -c) - const nfa_t &dc_nfa; // TNFA + const opt_t *dc_opts; // options + Warn &dc_warn; // warnings + const std::string &dc_condname; // the name of current condition (with -c) + const nfa_t &dc_nfa; // TNFA // determinization output - dfa_t &dc_dfa; // resulting TDFA -// tcpool_t &dc_tcmdpool; // pool of tag actions -// uint32_t dc_maxtagver; // maximal tag version -// tagver_t *dc_finvers; // tag versions used in final states -// std::set &dc_mtagvers; // the set of m-tags + dfa_t &dc_dfa; // resulting TDFA // temporary structures used by determinization - uint32_t dc_origin; // from-state of the current transition - uint32_t dc_target; // to-state of the current transition - uint32_t dc_symbol; // alphabet symbol of the current transition - tcmd_t *dc_actions; // tag actions of the current transition - closure_t dc_reached; - closure_t dc_closure; - prectable_t *dc_prectbl; // precedence table for Okui POSIX disambiguation - Tagpool dc_tagpool; - allocator_t &dc_allocator; - tagtree_t &dc_tagtrie; // prefix trie of tag histories - kernels_t dc_kernels; // TDFA states under construction - kernel_buffers_t dc_buffers; - newvers_t dc_newvers; - dump_dfa_t dc_dump; + allocator_t dc_allocator; + uint32_t dc_origin; // from-state of the current transition + uint32_t dc_target; // to-state of the current transition + uint32_t dc_symbol; // alphabet symbol of the current transition + tcmd_t *dc_actions; // tag actions of the current transition + closure_t dc_reached; + closure_t dc_closure; + prectable_t *dc_prectbl; // precedence table for Okui POSIX disambiguation + Tagpool dc_tagpool; + tagtree_t dc_tagtrie; // prefix trie of tag histories + kernels_t dc_kernels; // TDFA states under construction + kernel_buffers_t dc_buffers; + newvers_t dc_newvers; + std::stack dc_stack_topsort; + std::stack dc_stack_linear; + std::stack dc_stack_dfs; + dump_dfa_t dc_dump; determ_context_t(const opt_t *, Warn &, const std::string &, const nfa_t &, dfa_t &); FORBID_COPY(determ_context_t); }; + void tagged_epsilon_closure(determ_context_t &ctx); void find_state(determ_context_t &ctx); int32_t precedence(determ_context_t &, const clos_t &, const clos_t &, int32_t &, int32_t &); diff --git a/re2c/src/dfa/dump.cc b/re2c/src/dfa/dump.cc index bf208d10..98fa4870 100644 --- a/re2c/src/dfa/dump.cc +++ b/re2c/src/dfa/dump.cc @@ -8,7 +8,6 @@ #include "src/dfa/dfa.h" #include "src/dfa/determinization.h" #include "src/dfa/dump.h" -#include "src/dfa/find_state.h" #include "src/dfa/tagpool.h" #include "src/dfa/tagtree.h" #include "src/dfa/tcmd.h" @@ -16,12 +15,13 @@ #include "src/re/rule.h" #include "src/re/tag.h" + namespace re2c { -static void dump_tcmd_or_tcid(tcmd_t *const *tcmd, const tcid_t *tcid, size_t sym, const tcpool_t &tcpool); -static const char *tagname(const Tag &t); -static void dump_tags(const Tagpool &tagpool, hidx_t ttran, uint32_t tvers); +static void dump_tcmd_or_tcid(tcmd_t *const *, const tcid_t *, size_t, const tcpool_t &); +static const char *tagname(const Tag &); +static void dump_tags(const Tagpool &, const tagtree_t &, hidx_t, uint32_t); dump_dfa_t::dump_dfa_t(const opt_t *opts) @@ -119,7 +119,7 @@ void dump_dfa_t::state(const determ_context_t &ctx, bool isnew) uint32_t i = 0; for (c = b; c != e; ++c, ++i) { fprintf(stderr, " void -> 0:%u:w [style=dotted label=\"", i); - dump_tags(tagpool, c->ttran, c->tvers); + dump_tags(tagpool, ctx.dc_tagtrie, c->ttran, c->tvers); fprintf(stderr, "\"]\n"); } } @@ -140,7 +140,7 @@ void dump_dfa_t::state(const determ_context_t &ctx, bool isnew) fprintf(stderr, " %u:%u:e -> %s%u:%u:w [label=\"%u", origin, c->origin, prefix, state, i, symbol); - dump_tags(tagpool, c->ttran, c->tvers); + dump_tags(tagpool, ctx.dc_tagtrie, c->ttran, c->tvers); fprintf(stderr, "\"]\n"); } } @@ -271,23 +271,28 @@ const char *tagname(const Tag &t) } -void dump_tags(const Tagpool &tagpool, hidx_t ttran, uint32_t tvers) +void dump_tags(const Tagpool &tagpool, const tagtree_t &tagtrie, + hidx_t ttran, uint32_t tvers) { if (ttran == HROOT) return; - const tagver_t *vers = tagpool[tvers]; - const tagtree_t &h = tagpool.history; - fprintf(stderr, "/"); + const tagver_t *vers = tagpool[tvers]; for (size_t i = 0; i < tagpool.ntags; ++i) { - if (h.last(ttran, i) == TAGVER_ZERO) continue; + + if (tagtrie.last(ttran, i) == TAGVER_ZERO) { + continue; + } fprintf(stderr, "%d", abs(vers[i])); - for (hidx_t t = ttran; t != HROOT; t = h.pred(t)) { - if (h.tag(t) != i) continue; - if (h.elem(t) < TAGVER_ZERO) { + for (hidx_t t = ttran; t != HROOT; t = tagtrie.pred(t)) { + if (tagtrie.tag(t) != i) { + continue; + } + else if (tagtrie.elem(t) < TAGVER_ZERO) { fprintf(stderr, "↓"); - } else if (t > TAGVER_ZERO) { + } + else if (t > TAGVER_ZERO) { fprintf(stderr, "↑"); } } diff --git a/re2c/src/dfa/find_state.cc b/re2c/src/dfa/find_state.cc index 7e54476d..3b68795e 100644 --- a/re2c/src/dfa/find_state.cc +++ b/re2c/src/dfa/find_state.cc @@ -7,13 +7,13 @@ #include "src/dfa/determinization.h" #include "src/dfa/dfa.h" #include "src/dfa/dump.h" -#include "src/dfa/find_state.h" #include "src/dfa/tagpool.h" #include "src/dfa/tcmd.h" #include "src/nfa/nfa.h" #include "src/re/rule.h" #include "src/util/hash32.h" + namespace re2c { @@ -236,7 +236,7 @@ bool equal_lookahead_tags(const kernel_t *x, const kernel_t *y, const determ_con return true; } - tagtree_t &trie = ctx.dc_tagtrie; + const tagtree_t &trie = ctx.dc_tagtrie; const Tagpool &tagpool = ctx.dc_tagpool; const std::vector &tags = ctx.dc_dfa.tags; diff --git a/re2c/src/dfa/find_state.h b/re2c/src/dfa/find_state.h deleted file mode 100644 index 5f65d19b..00000000 --- a/re2c/src/dfa/find_state.h +++ /dev/null @@ -1,56 +0,0 @@ -#ifndef _RE2C_DFA_FIND_STATE_ -#define _RE2C_DFA_FIND_STATE_ - -#include -#include "src/util/c99_stdint.h" -#include - -#include "src/dfa/closure.h" -#include "src/dfa/dump.h" -#include "src/dfa/tagtree.h" -#include "src/re/tag.h" -#include "src/util/forbid_copy.h" -#include "src/util/lookup.h" - -namespace re2c -{ - -class tcpool_t; -struct Tagpool; -struct dfa_t; -struct dump_dfa_t; -struct nfa_state_t; -struct tcmd_t; - -struct kernel_t -{ - size_t size; - const prectable_t *prectbl; - nfa_state_t **state; - uint32_t *tvers; // tag versions - hidx_t *tlook; // lookahead tags - - FORBID_COPY(kernel_t); -}; - -struct kernel_buffers_t -{ - size_t maxsize; - kernel_t *kernel; - tagver_t cap; // capacity (greater or equal to max) - tagver_t max; // maximal tag version - char *memory; - tagver_t *x2y; - tagver_t *y2x; - size_t *x2t; - uint32_t *indegree; - tcmd_t *backup_actions; - - explicit kernel_buffers_t(allocator_t &alc); -}; - -typedef lookup_t kernels_t; - -} // namespace re2c - -#endif // _RE2C_DFA_FIND_STATE_ diff --git a/re2c/src/dfa/tagpool.cc b/re2c/src/dfa/tagpool.cc index 1178de12..f2756aac 100644 --- a/re2c/src/dfa/tagpool.cc +++ b/re2c/src/dfa/tagpool.cc @@ -1,4 +1,3 @@ -#include "src/util/c99_stdint.h" #include // malloc #include // memcpy, memcmp #include @@ -21,16 +20,10 @@ struct eqtag_t }; -Tagpool::Tagpool(const opt_t *o, size_t n) +Tagpool::Tagpool(size_t n) : lookup() - , opts(o) , ntags(n) , buffer(new tagver_t[n]) - , alc() - , history() - , astack() - , bstack() - , cstack() {} diff --git a/re2c/src/dfa/tagpool.h b/re2c/src/dfa/tagpool.h index f45bedba..4f275379 100644 --- a/re2c/src/dfa/tagpool.h +++ b/re2c/src/dfa/tagpool.h @@ -2,20 +2,16 @@ #define _RE2C_DFA_TAGPOOL_ #include -#include +#include "src/util/c99_stdint.h" -#include "src/dfa/closure.h" -#include "src/dfa/tagtree.h" #include "src/re/tag.h" #include "src/util/forbid_copy.h" #include "src/util/lookup.h" + namespace re2c { -struct nfa_state_t; -struct opt_t; - static const size_t ZERO_TAGS = 0; struct Tagpool @@ -25,18 +21,10 @@ private: taglookup_t lookup; public: - const opt_t *opts; const size_t ntags; tagver_t *buffer; - allocator_t alc; - - tagtree_t history; - std::stack astack; - std::stack bstack; - std::stack cstack; - - Tagpool(const opt_t *o, size_t n); + explicit Tagpool(size_t n); ~Tagpool(); uint32_t insert_const(tagver_t ver); uint32_t insert_succ(tagver_t fst); diff --git a/re2c/src/dfa/tagtree.cc b/re2c/src/dfa/tagtree.cc index 07ec71e8..d984e50c 100644 --- a/re2c/src/dfa/tagtree.cc +++ b/re2c/src/dfa/tagtree.cc @@ -1,10 +1,10 @@ #include #include -#include "src/dfa/closure.h" #include "src/dfa/determinization.h" #include "src/dfa/tagtree.h" + namespace re2c { -- 2.40.0