src
emit_dfa.cc
Go to the documentation of this file.
1 #include "src/util/c99_stdint.h"
2 #include <stddef.h>
3 #include <set>
4 #include <string>
5 #include <utility>
6 #include <vector>
7 
8 #include "src/codegen/bitmap.h"
9 #include "src/codegen/emit.h"
10 #include "src/codegen/go.h"
11 #include "src/codegen/input_api.h"
12 #include "src/codegen/label.h"
13 #include "src/codegen/output.h"
14 #include "src/conf/opt.h"
15 #include "src/globals.h"
16 #include "src/ir/adfa/action.h"
17 #include "src/ir/adfa/adfa.h"
19 #include "src/util/counter.h"
20 
21 namespace re2c
22 {
23 
24 static std::string genGetCondition ();
25 static void genCondGotoSub (OutputFile & o, uint32_t ind, const std::vector<std::string> & condnames, uint32_t cMin, uint32_t cMax);
26 static void genCondTable (OutputFile & o, uint32_t ind, const std::vector<std::string> & condnames);
27 static void genCondGoto (OutputFile & o, uint32_t ind, const std::vector<std::string> & condnames);
28 static void emit_state (OutputFile & o, uint32_t ind, const State * s, bool used_label);
29 
30 std::string genGetCondition()
31 {
32  return opts->cond_get_naked
33  ? opts->cond_get
34  : opts->cond_get + "()";
35 }
36 
37 void genGoTo(OutputFile & o, uint32_t ind, const State *from, const State *to, bool & readCh)
38 {
39  if (opts->target == opt_t::DOT)
40  {
41  o.wlabel(from->label).ws(" -> ").wlabel(to->label).ws("\n");
42  return;
43  }
44 
45  if (readCh && from->next != to)
46  {
47  o.wstring(opts->input_api.stmt_peek (ind));
48  readCh = false;
49  }
50 
51  o.wind(ind).ws("goto ").wstring(opts->labelPrefix).wlabel(to->label).ws(";\n");
52 }
53 
54 void emit_state (OutputFile & o, uint32_t ind, const State * s, bool used_label)
55 {
56  if (opts->target != opt_t::DOT)
57  {
58  if (used_label)
59  {
60  o.wstring(opts->labelPrefix).wlabel(s->label).ws(":\n");
61  }
62  if (opts->dFlag && (s->action.type != Action::INITIAL))
63  {
64  o.wind(ind).wstring(opts->yydebug).ws("(").wlabel(s->label).ws(", ").wstring(opts->input_api.expr_peek ()).ws(");\n");
65  }
66  }
67 }
68 
69 void DFA::count_used_labels (std::set<label_t> & used, label_t start, label_t initial, bool force_start) const
70 {
71  // In '-f' mode, default state is always state 0
72  if (opts->fFlag)
73  {
74  used.insert (label_t::first ());
75  }
76  if (force_start)
77  {
78  used.insert (start);
79  }
80  for (State * s = head; s; s = s->next)
81  {
82  s->go.used_labels (used);
83  }
84  for (uint32_t i = 0; i < accepts.size (); ++i)
85  {
86  used.insert (accepts[i]->label);
87  }
88  // must go last: it needs the set of used labels
89  if (used.count (head->label))
90  {
91  used.insert (initial);
92  }
93 }
94 
95 void DFA::emit_body (OutputFile & o, uint32_t& ind, const std::set<label_t> & used_labels, label_t initial) const
96 {
97  // If DFA has transitions to initial state, then initial state
98  // has a piece of code that advances input position. Wee must
99  // skip it when entering DFA.
100  if (used_labels.count(head->label))
101  {
102  o.wind(ind).ws("goto ").wstring(opts->labelPrefix).wlabel(initial).ws(";\n");
103  }
104 
105  const bool save_yyaccept = accepts.size () > 1;
106  for (State * s = head; s; s = s->next)
107  {
108  bool readCh = false;
109  emit_state (o, ind, s, used_labels.count (s->label));
110  emit_action (s->action, o, ind, readCh, s, cond, skeleton, used_labels, save_yyaccept);
111  s->go.emit(o, ind, readCh);
112  }
113 }
114 
115 void DFA::emit(Output & output, uint32_t& ind, bool isLastCond, bool& bPrologBrace)
116 {
117  OutputFile & o = output.source;
118 
119  bool bProlog = (!opts->cFlag || !bWroteCondCheck);
120 
121  // start_label points to the beginning of current re2c block
122  // (prior to condition dispatch in '-c' mode)
123  // it can forced by configuration 're2c:startlabel = <integer>;'
124  label_t start_label = o.label_counter.next ();
125  // initial_label points to the beginning of DFA
126  // in '-c' mode this is NOT equal to start_label
127  label_t initial_label = bProlog && opts->cFlag
128  ? o.label_counter.next ()
129  : start_label;
130  for (State * s = head; s; s = s->next)
131  {
132  s->label = o.label_counter.next ();
133  }
134  std::set<label_t> used_labels;
135  count_used_labels (used_labels, start_label, initial_label, o.get_force_start_label ());
136 
137  head->action.set_initial (initial_label, head->action.type == Action::SAVE);
138 
139  skeleton->warn_undefined_control_flow ();
140  skeleton->warn_unreachable_rules ();
141  skeleton->warn_match_empty ();
142 
143  if (opts->target == opt_t::SKELETON)
144  {
145  if (output.skeletons.insert (name).second)
146  {
147  skeleton->emit_data (o.file_name);
149  uint32_t i = 2;
150  emit_body (o, i, used_labels, initial_label);
151  skeleton->emit_end (o, need_backup, need_backupctx);
152  }
153  }
154  else
155  {
156  // Generate prolog
157  if (bProlog)
158  {
159  o.ws("\n").wdelay_line_info ();
160  if (opts->target == opt_t::DOT)
161  {
162  bPrologBrace = true;
163  o.ws("digraph re2c {\n");
164  }
165  else if ((!opts->fFlag && o.get_used_yyaccept ())
166  || (!opts->fFlag && opts->bEmitYYCh)
167  || (opts->bFlag && !opts->cFlag && BitMap::first)
168  || (opts->cFlag && !bWroteCondCheck && opts->gFlag)
169  || (opts->fFlag && !bWroteGetState && opts->gFlag)
170  )
171  {
172  bPrologBrace = true;
173  o.wind(ind++).ws("{\n");
174  }
175  else if (ind == 0)
176  {
177  ind = 1;
178  }
179  if (!opts->fFlag && opts->target != opt_t::DOT)
180  {
181  if (opts->bEmitYYCh)
182  {
183  o.wind(ind).wstring(opts->yyctype).ws(" ").wstring(opts->yych).ws(";\n");
184  }
185  o.wdelay_yyaccept_init (ind);
186  }
187  else
188  {
189  o.ws("\n");
190  }
191  }
192  if (opts->bFlag && !opts->cFlag && BitMap::first)
193  {
194  BitMap::gen(o, ind, lbChar, ubChar <= 256 ? ubChar : 256);
195  }
196  if (bProlog)
197  {
198  if (opts->cFlag && !bWroteCondCheck && opts->gFlag)
199  {
200  genCondTable(o, ind, output.types);
201  }
202  o.wdelay_state_goto (ind);
203  if (opts->cFlag && opts->target != opt_t::DOT)
204  {
205  if (used_labels.count(start_label))
206  {
207  o.wstring(opts->labelPrefix).wlabel(start_label).ws(":\n");
208  }
209  }
210  o.wuser_start_label ();
211  if (opts->cFlag && !bWroteCondCheck)
212  {
213  genCondGoto(o, ind, output.types);
214  }
215  }
216  if (opts->cFlag && !cond.empty())
217  {
218  if (opts->condDivider.length())
219  {
221  }
222  if (opts->target == opt_t::DOT)
223  {
224  o.wstring(cond).ws(" -> ").wlabel(head->label).ws("\n");
225  }
226  else
227  {
228  o.wstring(opts->condPrefix).wstring(cond).ws(":\n");
229  }
230  }
231  if (opts->cFlag && opts->bFlag && BitMap::first)
232  {
233  o.wind(ind++).ws("{\n");
234  BitMap::gen(o, ind, lbChar, ubChar <= 256 ? ubChar : 256);
235  }
236  // Generate code
237  emit_body (o, ind, used_labels, initial_label);
238  if (opts->cFlag && opts->bFlag && BitMap::first)
239  {
240  o.wind(--ind).ws("}\n");
241  }
242  // Generate epilog
243  if ((!opts->cFlag || isLastCond) && bPrologBrace)
244  {
245  o.wind(--ind).ws("}\n");
246  }
247  }
248 
249  // Cleanup
250  if (BitMap::first)
251  {
252  delete BitMap::first;
253  BitMap::first = NULL;
254  }
255 }
256 
257 void genCondTable(OutputFile & o, uint32_t ind, const std::vector<std::string> & condnames)
258 {
259  const size_t conds = condnames.size ();
260  o.wind(ind++).ws("static void *").wstring(opts->yyctable).ws("[").wu64(conds).ws("] = {\n");
261  for (size_t i = 0; i < conds; ++i)
262  {
263  o.wind(ind).ws("&&").wstring(opts->condPrefix).wstring(condnames[i]).ws(",\n");
264  }
265  o.wind(--ind).ws("};\n");
266 }
267 
268 void genCondGotoSub(OutputFile & o, uint32_t ind, const std::vector<std::string> & condnames, uint32_t cMin, uint32_t cMax)
269 {
270  if (cMin == cMax)
271  {
272  o.wind(ind).ws("goto ").wstring(opts->condPrefix).wstring(condnames[cMin]).ws(";\n");
273  }
274  else
275  {
276  uint32_t cMid = cMin + ((cMax - cMin + 1) / 2);
277 
278  o.wind(ind).ws("if (").wstring(genGetCondition()).ws(" < ").wu32(cMid).ws(") {\n");
279  genCondGotoSub(o, ind + 1, condnames, cMin, cMid - 1);
280  o.wind(ind).ws("} else {\n");
281  genCondGotoSub(o, ind + 1, condnames, cMid, cMax);
282  o.wind(ind).ws("}\n");
283  }
284 }
285 
286 /*
287  * note [condition order]
288  *
289  * In theory re2c makes no guarantee about the order of conditions in
290  * the generated lexer. Users should define condition type 'YYCONDTYPE'
291  * and use values of this type with 'YYGETCONDITION' and 'YYSETCONDITION'.
292  * This way code is independent of internal re2c condition numbering.
293  *
294  * However, it is possible to manually hardcode condition numbers and make
295  * re2c generate condition dispatch without explicit use of condition names
296  * (nested 'if' statements with '-b' or computed 'goto' table with '-g').
297  * This code is syntactically valid (compiles), but unsafe:
298  * - change of re2c options may break compilation
299  * - change of internal re2c condition numbering may break runtime
300  *
301  * re2c has to preserve the existing numbering scheme.
302  *
303  * re2c warns about implicit assumptions about condition order, unless:
304  * - condition type is defined with 'types:re2c' or '-t, --type-header'
305  * - dispatch is independent of condition order: either it uses
306  * explicit condition names or there's only one condition and
307  * dispatch shrinks to unconditional jump
308  */
309 void genCondGoto(OutputFile & o, uint32_t ind, const std::vector<std::string> & condnames)
310 {
311  const size_t conds = condnames.size ();
312  if (opts->target == opt_t::DOT)
313  {
314  o.warn_condition_order = false; // see note [condition order]
315  for (size_t i = 0; i < conds; ++i)
316  {
317  const std::string cond = condnames[i];
318  o.ws("0 -> ").wstring(cond).ws(" [label=\"state=").wstring(cond).ws("\"]\n");
319  }
320  }
321  else if (opts->gFlag)
322  {
323  o.wind(ind).ws("goto *").wstring(opts->yyctable).ws("[").wstring(genGetCondition()).ws("];\n");
324  }
325  else if (opts->sFlag)
326  {
327  if (conds == 1)
328  {
329  o.warn_condition_order = false; // see note [condition order]
330  }
331  genCondGotoSub(o, ind, condnames, 0, static_cast<uint32_t> (conds) - 1);
332  }
333  else
334  {
335  o.warn_condition_order = false; // see note [condition order]
336  o.wind(ind).ws("switch (").wstring(genGetCondition()).ws(") {\n");
337  for (size_t i = 0; i < conds; ++i)
338  {
339  const std::string & cond = condnames[i];
340  o.wind(ind).ws("case ").wstring(opts->condEnumPrefix).wstring(cond).ws(": goto ").wstring(opts->condPrefix).wstring(cond).ws(";\n");
341  }
342  o.wind(ind).ws("}\n");
343  }
345  bWroteCondCheck = true;
346 }
347 
348 } // end namespace re2c
void emit_action(const Action &action, OutputFile &o, uint32_t ind, bool &readCh, const State *const s, const std::string &condName, const Skeleton *skeleton, const std::set< label_t > &used_labels, bool save_yyaccept)
Definition: emit_action.cc:36
OutputFile & wdelay_warn_condition_order()
Definition: output.cc:228
bool bFlag
Definition: opt.h:118
bool bWroteGetState
Definition: main.cc:17
size_t max_fill
Definition: adfa.h:69
bool get_used_yyaccept() const
Definition: output.cc:254
std::string replaceParam(std::string str, const std::string &param, const _Ty &value)
Definition: emit.h:26
std::string condPrefix
Definition: opt.h:118
std::string expr_peek() const
Definition: input_api.cc:25
OutputFile & wuser_start_label()
Definition: output.cc:139
std::vector< std::string > types
Definition: output.h:138
static void genCondGotoSub(OutputFile &o, uint32_t ind, const std::vector< std::string > &condnames, uint32_t cMin, uint32_t cMax)
Definition: emit_dfa.cc:268
static void genCondTable(OutputFile &o, uint32_t ind, const std::vector< std::string > &condnames)
Definition: emit_dfa.cc:257
const std::string cond
Definition: adfa.h:60
std::string cond_get
Definition: opt.h:118
InputAPI input_api
Definition: opt.h:118
std::string yych
Definition: opt.h:118
static void genCondGoto(OutputFile &o, uint32_t ind, const std::vector< std::string > &condnames)
Definition: emit_dfa.cc:309
static void gen(OutputFile &, uint32_t ind, uint32_t, uint32_t)
Definition: bitmap.cc:75
OutputFile & ws(const char *s)
Definition: output.cc:173
OutputFile & wu32(uint32_t n)
Definition: output.cc:155
std::string condDivider
Definition: opt.h:118
OutputFile & wdelay_state_goto(uint32_t ind)
Definition: output.cc:209
void emit_end(OutputFile &o, bool backup, bool backupctx) const
OutputFile & wind(uint32_t ind)
Definition: output.cc:191
OutputFile & wlabel(label_t l)
Definition: output.cc:179
void emit_start(OutputFile &o, size_t maxfill, bool backup, bool backupctx, bool accept) const
OutputFile source
Definition: output.h:136
bool bWroteCondCheck
Definition: main.cc:18
bool cFlag
Definition: opt.h:118
bool sFlag
Definition: opt.h:118
bool dFlag
Definition: opt.h:118
uint32_t lbChar
Definition: adfa.h:63
std::string condEnumPrefix
Definition: opt.h:118
void warn_match_empty()
Definition: match_empty.cc:14
OutputFile & wdelay_line_info()
Definition: output.cc:202
bool cond_get_naked
Definition: opt.h:118
opt_t::target_t target
Definition: opt.h:118
OutputFile & wu64(uint64_t n)
Definition: output.cc:161
void emit(Output &, uint32_t &, bool, bool &)
Definition: emit_dfa.cc:115
bool gFlag
Definition: opt.h:118
std::string yyctable
Definition: opt.h:118
Action action
Definition: adfa.h:33
bool need_backup
Definition: adfa.h:70
std::string labelPrefix
Definition: opt.h:118
bool need_backupctx
Definition: adfa.h:71
uint32_t ubChar
Definition: adfa.h:64
bool fFlag
Definition: opt.h:118
bool warn_condition_order
Definition: output.h:66
label_t label
Definition: adfa.h:25
State * head
Definition: adfa.h:66
Opt opts
Definition: opt.cc:7
static label_t first()
Definition: label.cc:18
std::string yydebug
Definition: opt.h:118
static void emit_state(OutputFile &o, uint32_t ind, const State *s, bool used_label)
Definition: emit_dfa.cc:54
static std::string genGetCondition()
Definition: emit_dfa.cc:30
OutputFile & wdelay_yyaccept_init(uint32_t ind)
Definition: output.cc:235
void genGoTo(OutputFile &o, uint32_t ind, const State *from, const State *to, bool &readCh)
Definition: emit_dfa.cc:37
std::string stmt_peek(uint32_t ind) const
Definition: input_api.cc:45
const char * file_name
Definition: output.h:58
static BitMap * first
Definition: bitmap.h:19
size_t size() const
Definition: uniq_vector.h:21
void emit_data(const char *fname)
bool bEmitYYCh
Definition: opt.h:118
bool get_force_start_label() const
Definition: output.cc:269
void warn_unreachable_rules()
Definition: unreachable.cc:37
void warn_undefined_control_flow()
Definition: control_flow.cc:43
counter_t< label_t > label_counter
Definition: output.h:65
Definition: bitmap.cc:10
void set_initial(label_t label, bool used_marker)
Definition: action.h:59
enum re2c::Action::type_t type
std::set< std::string > skeletons
Definition: output.h:139
OutputFile & wstring(const std::string &s)
Definition: output.cc:167
bool need_accept
Definition: adfa.h:72
std::string condDividerParam
Definition: opt.h:118
std::string yyctype
Definition: opt.h:118
const std::string name
Definition: adfa.h:59
State * next
Definition: adfa.h:27