1 #ifdef RE2C_DEBUG
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <algorithm>
6 #include <string>
7 #include <valarray>
8 #include <vector>
9
10 #include "src/options/opt.h"
11 #include "src/debug/debug.h"
12 #include "src/dfa/dfa.h"
13 #include "src/dfa/determinization.h"
14 #include "src/dfa/tag_history.h"
15 #include "src/dfa/tagver_table.h"
16 #include "src/dfa/tcmd.h"
17 #include "src/nfa/nfa.h"
18 #include "src/regexp/rule.h"
19 #include "src/regexp/tag.h"
20
21
22 namespace re2c {
23
24 template<typename ctx_t> static void dump_history(const dfa_t &, const typename ctx_t::history_t &, hidx_t);
25 template<typename ctx_t> static void dump_tags(const tagver_table_t &, const typename ctx_t::history_t &, hidx_t, uint32_t);
26 static void dump_tcmd_or_tcid(tcmd_t *const *, const tcid_t *, size_t, const tcpool_t &);
27 static const char *tagname(const Tag &);
28 template <typename ctx_t> static void dump_stacmd(const ctx_t &, const stacmd_t *);
29
30 // explicit instantiation for context types
31 template void dump_dfa_t::state<pdetctx_t>(const pdetctx_t &ctx, bool isnew);
32 template void dump_dfa_t::state<ldetctx_t>(const ldetctx_t &ctx, bool isnew);
33 template void dump_clstats<pdetctx_t>(const pdetctx_t &);
34 template void dump_clstats<ldetctx_t>(const ldetctx_t &);
35 template void reset_clstats<pdetctx_t>(pdetctx_t &);
36 template void reset_clstats<ldetctx_t>(ldetctx_t &);
37
dump_dfa_t(const opt_t * opts)38 dump_dfa_t::dump_dfa_t(const opt_t *opts)
39 : debug(opts->dump_dfa_raw)
40 , uniqidx(0)
41 {
42 if (!debug) return;
43
44 fprintf(stderr, "digraph DFA {\n"
45 " rankdir=LR\n"
46 " node[shape=plaintext fontname=Courier]\n"
47 " edge[arrowhead=vee fontname=Courier]\n\n");
48 }
49
~dump_dfa_t()50 dump_dfa_t::~dump_dfa_t()
51 {
52 if (!debug) return;
53
54 fprintf(stderr, "}\n");
55 }
56
57 template<typename ctx_t>
state(const ctx_t & ctx,bool isnew)58 void dump_dfa_t::state(const ctx_t &ctx, bool isnew)
59 {
60 if (!debug) return;
61
62 const closure_t &closure = ctx.state;
63 cclositer_t b = closure.begin(), e = closure.end(), c;
64 const uint32_t origin = ctx.dc_origin;
65 const uint32_t target = ctx.dc_target;
66 const uint32_t symbol = ctx.dc_symbol;
67 const dfa_t &dfa = ctx.dfa;
68 const tagver_table_t &tvtbl = ctx.dc_tagvertbl;
69 const typename ctx_t::history_t &thist = ctx.history;
70 uint32_t i;
71
72 if (target == dfa_t::NIL) return;
73
74 const uint32_t state = isnew ? target : ++uniqidx;
75 const char *prefix = isnew ? "" : "i";
76 const char *style = isnew ? "" : " STYLE=\"dotted\"";
77
78 // closure
79 fprintf(stderr, " %s%u [label=<<TABLE"
80 " BORDER=\"0\""
81 " CELLBORDER=\"1\""
82 ">", prefix, state);
83 i = 0;
84 for (c = b; c != e; ++c, ++i) {
85 fprintf(stderr, "<TR><TD ALIGN=\"left\" PORT=\"%u\"%s>%u",
86 i, style, static_cast<uint32_t>(c->state - ctx.nfa.states));
87
88 if (c->tvers != ZERO_TAGS) {
89 const tagver_t *vers = tvtbl[c->tvers];
90 const size_t ntag = dfa.tags.size();
91
92 for (size_t t = 0; t < ntag; ++t) {
93 fprintf(stderr, " %s%d", tagname(dfa.tags[t]), abs(vers[t]));
94 }
95
96 if (c->thist != HROOT) {
97 dump_history<ctx_t>(dfa, thist, c->thist);
98 }
99 }
100
101 fprintf(stderr, "</TD></TR>");
102 }
103 if (ctx.dc_opts->stadfa) {
104 fprintf(stderr, "<TR><TD>");
105 dump_stacmd(ctx, ctx.stadfa_actions);
106 fprintf(stderr, "</TD></TR>");
107 }
108 fprintf(stderr, "</TABLE>>]\n");
109
110 // transitions (initial state)
111 if (origin == dfa_t::NIL) {
112 fprintf(stderr, " void [shape=point]\n");
113
114 uint32_t j = 0;
115 for (c = b; c != e; ++c, ++j) {
116 fprintf(stderr, " void -> 0:%u:w [style=dotted label=\"", j);
117 dump_tags<ctx_t>(tvtbl, thist, c->ttran, c->tvers);
118 fprintf(stderr, "\"]\n");
119 }
120 }
121
122 // transitions (other states)
123 else {
124 if (!isnew) {
125 const dfa_state_t *o = dfa.states[origin];
126 fprintf(stderr,
127 " i%u [style=dotted]\n"
128 " i%u:s -> %u:s [style=dotted label=\"",
129 state, state, static_cast<uint32_t>(o->arcs[symbol]));
130 dump_tcmd(o->tcmd[symbol]);
131 fprintf(stderr, "\"]\n");
132 }
133
134 uint32_t j = 0;
135 for (c = b; c != e; ++c, ++j) {
136 fprintf(stderr,
137 " %u:%u:e -> %s%u:%u:w [label=\"%u",
138 origin, c->origin, prefix, state, j, symbol);
139 dump_tags<ctx_t>(tvtbl, thist, c->ttran, c->tvers);
140 fprintf(stderr, "\"]\n");
141 }
142 }
143
144 // if final state, dump finalizer
145 const dfa_state_t *t = dfa.states[target];
146 if (t->rule != Rule::NONE) {
147 const Rule &r = dfa.rules[t->rule];
148 const tcmd_t *cmd = t->tcmd[dfa.nchars];
149
150 // see note [at most one final item per closure]
151 c = std::find_if(b, e, clos_t::fin);
152 DASSERT(c != e);
153
154 fprintf(stderr, " r%u [shape=none label=\"(", state);
155 for (size_t j = r.ltag; j < r.htag; ++j) {
156 if (j > r.ltag) fprintf(stderr, " ");
157 fprintf(stderr, "%s%d", tagname(dfa.tags[j]), abs(dfa.finvers[j]));
158 }
159 fprintf(stderr, ")\"]\n");
160
161 fprintf(stderr, " %u:%u:e -> r%u [style=dotted label=\"",
162 state, static_cast<uint32_t>(c - b), state);
163 dump_tcmd(cmd);
164 fprintf(stderr, "\"]\n");
165 }
166 }
167
168 template<typename ctx_t>
dump_history(const dfa_t & dfa,const typename ctx_t::history_t & h,hidx_t i)169 void dump_history(const dfa_t &dfa
170 , const typename ctx_t::history_t &h, hidx_t i)
171 {
172 if (i == HROOT) {
173 fprintf(stderr, " /");
174 return;
175 }
176
177 const typename ctx_t::history_t::node_t &n = h.node(i);
178 dump_history<ctx_t>(dfa, h, n.pred);
179 dump_tag(dfa.tags[n.info.idx], n.info.neg);
180 fprintf(stderr, " ");
181 }
182
dump_dfa(const dfa_t & dfa)183 void dump_dfa(const dfa_t &dfa)
184 {
185 const size_t
186 nstate = dfa.states.size(),
187 nsym = dfa.nchars;
188
189 fprintf(stderr,
190 "digraph DFA {\n"
191 " rankdir=LR\n"
192 " node[fontname=Courier]\n"
193 " edge[arrowhead=vee fontname=Courier]\n\n");
194
195 // initializer
196 fprintf(stderr,
197 " n [shape=point]"
198 " n -> n0 [style=dotted label=\"");
199 dump_tcmd_or_tcid(dfa.tcmd0 ? &dfa.tcmd0 : NULL, &dfa.tcid0, 0, dfa.tcpool);
200 fprintf(stderr, "\"]\n");
201
202 for (uint32_t i = 0; i < nstate; ++i) {
203 const dfa_state_t *s = dfa.states[i];
204
205 // state
206 fprintf(stderr, " n%u [height=0.2 width=0.2 label=\"%u", i, i);
207 dump_tcmd_or_tcid(s->stacmd ? &s->stacmd : NULL, &s->stacid, 0, dfa.tcpool);
208 fprintf(stderr, "\"]\n");
209
210 // finalizer
211 if (s->rule != Rule::NONE) {
212 const Rule &r = dfa.rules[s->rule];
213
214 fprintf(stderr,
215 "subgraph { rank=same"
216 " n%u [style=filled fillcolor=lightgray]"
217 " dr%u [shape=none label=\"",
218 i, i);
219 dump_tcmd_or_tcid(s->tcmd, s->tcid, nsym, dfa.tcpool);
220
221 fprintf(stderr, "(");
222 for (size_t t = r.ltag; t < r.htag; ++t) {
223 if (t > r.ltag) fprintf(stderr, " ");
224 fprintf(stderr, "%d", dfa.finvers[t]);
225 }
226 fprintf(stderr, ")");
227
228 fprintf(stderr, "\"]"
229 " n%u:s -> dr%u:n [style=dotted minlen=0]}\n",
230 i, i);
231 }
232
233 // transitions
234 for (uint32_t c = 0; c < nsym; ++c) {
235 const size_t j = s->arcs[c];
236 if (j != dfa_t::NIL) {
237 fprintf(stderr, " n%u -> n%u [label=\"%u",
238 i, static_cast<uint32_t>(j), c);
239 dump_tcmd_or_tcid(s->tcmd, s->tcid, c, dfa.tcpool);
240 fprintf(stderr, "\"]\n");
241 }
242 }
243 }
244
245 fprintf(stderr, "}\n");
246 }
247
dump_tcmd_or_tcid(tcmd_t * const * tcmd,const tcid_t * tcid,size_t sym,const tcpool_t & tcpool)248 void dump_tcmd_or_tcid(tcmd_t *const *tcmd, const tcid_t *tcid,
249 size_t sym, const tcpool_t &tcpool)
250 {
251 const tcmd_t *cmd = tcmd ? tcmd[sym] : tcpool[tcid[sym]];
252 dump_tcmd(cmd);
253 }
254
dump_tcmd(const tcmd_t * p)255 void dump_tcmd(const tcmd_t *p)
256 {
257 if (!p) return;
258
259 fprintf(stderr, "/");
260 for (; p; p = p->next) {
261 const tagver_t l = p->lhs, r = p->rhs, *h = p->history;
262 if (tcmd_t::iscopy(p)) {
263 fprintf(stderr, "%d=%d ", l, r);
264 } else {
265 fprintf(stderr, "%d", l);
266 if (r != TAGVER_ZERO) {
267 fprintf(stderr, "=%d", r);
268 }
269 for (; *h != TAGVER_ZERO; ++h) {
270 fprintf(stderr, "%s", *h == TAGVER_BOTTOM ? "↓" : "↑");
271 }
272 fprintf(stderr, " ");
273 }
274 }
275 }
276
277 template <typename ctx_t>
dump_stacmd(const ctx_t & ctx,const stacmd_t * p)278 void dump_stacmd(const ctx_t &ctx, const stacmd_t *p)
279 {
280 for (; p; p = p->next) {
281 const tagver_t v = last(ctx.history, p->hist, p->tag);
282 const uint32_t t = static_cast<uint32_t>(p->tag);
283
284 switch (p->kind) {
285 case stacmd_t::STORE:
286 fprintf(stderr, "S(%u,%d,%d,%s)", t, p->lhs, p->rhs,
287 v == TAGVER_BOTTOM ? "↓" : "↑");
288 break;
289 case stacmd_t::TRANSFER:
290 fprintf(stderr, "T(%u,%d,%d)", t, p->lhs, p->rhs);
291 break;
292 case stacmd_t::ACCEPT:
293 if (v == TAGVER_CURSOR) {
294 fprintf(stderr, "A(%u,%d,↑)", t, p->rhs);
295 }
296 else if (v == TAGVER_BOTTOM) {
297 fprintf(stderr, "A(%u,%d,↓)", t, p->rhs);
298 }
299 else {
300 fprintf(stderr, "A(%u,%d)", t, p->rhs);
301 }
302 break;
303 }
304 if (p->next) fprintf(stderr, "<BR/>");
305 }
306 }
307
tagname(const Tag & t)308 const char *tagname(const Tag &t)
309 {
310 return t.name ? t.name->c_str() : "";
311 }
312
313 template<typename ctx_t>
dump_tags(const tagver_table_t & tagvertbl,const typename ctx_t::history_t & taghistory,hidx_t ttran,uint32_t tvers)314 void dump_tags(const tagver_table_t &tagvertbl
315 , const typename ctx_t::history_t &taghistory
316 , hidx_t ttran, uint32_t tvers)
317 {
318 if (ttran == HROOT) return;
319
320 fprintf(stderr, "/");
321 const tagver_t *vers = tagvertbl[tvers];
322 for (size_t t = 0; t < tagvertbl.ntags; ++t) {
323
324 if (last(taghistory, ttran, t) == TAGVER_ZERO) {
325 continue;
326 }
327
328 fprintf(stderr, "%d", abs(vers[t]));
329 for (hidx_t i = ttran; i != HROOT; ) {
330 const typename ctx_t::history_t::node_t &n = taghistory.node(i);
331 if (n.info.idx == t) {
332 fprintf(stderr, n.info.neg ? "↓" : "↑");
333 }
334 i = n.pred;
335 }
336 fprintf(stderr, " ");
337 }
338 }
339
340 template<typename ctx_t>
reset_clstats(ctx_t & ctx)341 void reset_clstats(ctx_t &ctx)
342 {
343 closure_stats_t &cs = ctx.dc_clstats;
344 cs.nscans = 0;
345 cs.nprec = 0;
346 cs.length = 0;
347 }
348
349 template<typename ctx_t>
dump_clstats(const ctx_t & ctx)350 void dump_clstats(const ctx_t &ctx)
351 {
352 const closure_stats_t &cs = ctx.dc_clstats;
353 if (ctx.dc_opts->dump_closure_stats) {
354 fprintf(stderr, "scans: %-10u prec: %-10u length: %-10lu\n"
355 , cs.nscans, cs.nprec, (unsigned long)cs.length);
356 }
357 }
358
359 } // namespace re2c
360
361 #endif // RE2C_DEBUG
362