Branch data Line data Source code
1 : : // -*- C++ -*-
2 : : // Copyright (C) 2012-2013 Red Hat Inc.
3 : : //
4 : : // This file is part of systemtap, and is free software. You can
5 : : // redistribute it and/or modify it under the terms of the GNU General
6 : : // Public License (GPL); either version 2, or (at your option) any
7 : : // later version.
8 : : //
9 : : // ---
10 : : //
11 : : // This file incorporates code from the re2c project; please see
12 : : // re2c-migrate/README for details.
13 : :
14 : : #include <stdlib.h>
15 : : #include <ctype.h>
16 : : #include <string.h>
17 : : #include "re2c-globals.h"
18 : : #include "re2c-dfa.h"
19 : :
20 : : namespace re2c
21 : : {
22 : :
23 : 1138 : void prtChOrHex(std::ostream& o, unsigned c)
24 : : {
25 [ - + ]: 1138 : if (eFlag)
26 : : {
27 [ # # ]: 0 : if (DFlag) o << '"';
28 : 0 : prtHex(o, c);
29 [ # # ]: 0 : if (DFlag) o << '"';
30 : : }
31 [ + - ][ + + ]: 1138 : else if ((c < 256u) && (isprint(c) || isspace(c)))
[ - + ]
32 : : {
33 [ - + ]: 880 : o << (DFlag ? '"' : '\'');
34 : 880 : prtCh(o, c);
35 [ - + ]: 880 : o << (DFlag ? '"' : '\'');
36 : : }
37 : : else
38 : : {
39 [ - + ]: 258 : if (DFlag) o << '"';
40 : 258 : prtHex(o, c);
41 [ - + ]: 258 : if (DFlag) o << '"';
42 : : }
43 : 1138 : }
44 : :
45 : 258 : void prtHex(std::ostream& o, unsigned c)
46 : : {
47 : 258 : int oc = (int)(c);
48 : :
49 [ - + ]: 258 : if (re2c::uFlag)
50 : : {
51 : 0 : o << "0x"
52 : 0 : << hexCh(oc >> 28)
53 : 0 : << hexCh(oc >> 24)
54 : 0 : << hexCh(oc >> 20)
55 : 0 : << hexCh(oc >> 16)
56 : 0 : << hexCh(oc >> 12)
57 : 0 : << hexCh(oc >> 8)
58 : 0 : << hexCh(oc >> 4)
59 : 0 : << hexCh(oc);
60 : : }
61 [ - + ]: 258 : else if (re2c::wFlag)
62 : : {
63 : 0 : o << "0x"
64 : 0 : << hexCh(oc >> 12)
65 : 0 : << hexCh(oc >> 8)
66 : 0 : << hexCh(oc >> 4)
67 : 0 : << hexCh(oc);
68 : : }
69 : : else
70 : : {
71 : 258 : o << "0x"
72 : 258 : << hexCh(oc >> 4)
73 : 258 : << hexCh(oc);
74 : : }
75 : 258 : }
76 : :
77 : 880 : void prtCh(std::ostream& o, unsigned c)
78 : : {
79 [ - + ]: 880 : if (eFlag)
80 : : {
81 : 0 : prtHex(o, c);
82 : 880 : return;
83 : : }
84 : :
85 : 880 : int oc = (int)(c);
86 : :
87 [ - - - - : 880 : switch (oc)
- - - - -
+ + ]
88 : : {
89 : : case '\'':
90 [ # # ]: 0 : o << (DFlag ? "'" : "\\'");
91 : 0 : break;
92 : :
93 : : case '"':
94 [ # # ]: 0 : o << (DFlag ? "\\\"" : "\"");
95 : 0 : break;
96 : :
97 : : case '\n':
98 : 0 : o << "\\n";
99 : 0 : break;
100 : :
101 : : case '\t':
102 : 0 : o << "\\t";
103 : 0 : break;
104 : :
105 : : case '\v':
106 : 0 : o << "\\v";
107 : 0 : break;
108 : :
109 : : case '\b':
110 : 0 : o << "\\b";
111 : 0 : break;
112 : :
113 : : case '\r':
114 : 0 : o << "\\r";
115 : 0 : break;
116 : :
117 : : case '\f':
118 : 0 : o << "\\f";
119 : 0 : break;
120 : :
121 : : case '\a':
122 : 0 : o << "\\a";
123 : 0 : break;
124 : :
125 : : case '\\':
126 : 6 : o << "\\\\";
127 : 6 : break;
128 : :
129 : : default:
130 : :
131 [ + - ][ + - ]: 874 : if ((oc < 256) && isprint(oc))
132 : : {
133 : 874 : o << (char) oc;
134 : : }
135 [ # # ]: 0 : else if (re2c::uFlag)
136 : : {
137 : 0 : o << "0x"
138 : 0 : << hexCh(oc >> 20)
139 : 0 : << hexCh(oc >> 16)
140 : 0 : << hexCh(oc >> 12)
141 : 0 : << hexCh(oc >> 8)
142 : 0 : << hexCh(oc >> 4)
143 : 0 : << hexCh(oc);
144 : : }
145 [ # # ]: 0 : else if (re2c::wFlag)
146 : : {
147 : 0 : o << "0x"
148 : 0 : << hexCh(oc >> 12)
149 : 0 : << hexCh(oc >> 8)
150 : 0 : << hexCh(oc >> 4)
151 : 0 : << hexCh(oc);
152 : : }
153 : : else
154 : : {
155 : 0 : o << '\\' << octCh(oc / 64) << octCh(oc / 8) << octCh(oc);
156 : : }
157 : : }
158 : : }
159 : :
160 : 0 : void printSpan(std::ostream& o, unsigned lb, unsigned ub)
161 : : {
162 [ # # ]: 0 : if (lb > ub)
163 : : {
164 : 0 : o << "*";
165 : : }
166 : :
167 : 0 : o << "[";
168 : :
169 [ # # ]: 0 : if ((ub - lb) == 1)
170 : : {
171 : 0 : prtCh(o, lb);
172 : : }
173 : : else
174 : : {
175 : 0 : prtCh(o, lb);
176 : 0 : o << "-";
177 : 0 : prtCh(o, ub - 1);
178 : : }
179 : :
180 : 0 : o << "]";
181 : 0 : }
182 : :
183 : 0 : unsigned Span::show(std::ostream &o, unsigned lb) const
184 : : {
185 [ # # ]: 0 : if (to)
186 : : {
187 : 0 : printSpan(o, lb, ub);
188 : 0 : o << " " << to->label << "; ";
189 : : }
190 : :
191 : 0 : return ub;
192 : : }
193 : :
194 : 0 : std::ostream& operator<<(std::ostream &o, const State &s)
195 : : {
196 : 0 : o << "state " << s.label;
197 : :
198 [ # # ]: 0 : if (s.rule)
199 : : {
200 : 0 : o << " accepts " << s.rule->accept;
201 : : }
202 : :
203 : 0 : o << "\n";
204 : :
205 : 0 : unsigned lb = 0;
206 : :
207 [ # # ]: 0 : for (unsigned i = 0; i < s.go.nSpans; ++i)
208 : : {
209 : 0 : lb = s.go.span[i].show(o, lb);
210 : : }
211 : :
212 : 0 : return o;
213 : : }
214 : :
215 : 0 : std::ostream& operator<<(std::ostream &o, const DFA &dfa)
216 : : {
217 [ # # ]: 0 : for (State *s = dfa.head; s; s = s->next)
218 : : {
219 : 0 : o << s << "\n\n";
220 : : }
221 : :
222 : 0 : return o;
223 : : }
224 : :
225 : 279 : State::State()
226 : : : label(0)
227 : : , next(0)
228 : : , rule(NULL)
229 : : , link(NULL)
230 : : , depth(0)
231 : : , kCount(0)
232 : : , kernel(NULL)
233 : : , isPreCtxt(false)
234 : : , isBase(false)
235 : : , go()
236 : 279 : , action(NULL)
237 : : {
238 : 279 : }
239 : :
240 : 0 : State::~State()
241 : : {
242 [ # # ]: 0 : delete action;
243 [ # # ]: 0 : delete [] kernel;
244 [ # # ]: 0 : delete [] go.span;
245 : 0 : }
246 : :
247 : : /* Mark all Ins reachable from a given point without slurping a
248 : : character. The list of Ins locations gets written out to a given
249 : : work array starting at cP. */
250 : 4792 : static Ins **closure(Ins **cP, Ins *i, bool isInitial)
251 : : {
252 [ + + ]: 9196 : while (!isMarked(i))
253 : : {
254 : 9141 : mark(i);
255 : 9141 : *(cP++) = i;
256 : :
257 [ + + ]: 9141 : if (i->i.tag == FORK)
258 : : {
259 : 3236 : cP = closure(cP, i + 1, isInitial);
260 : 3236 : i = (Ins*) i->i.link;
261 : : }
262 [ + + ][ - + ]: 5905 : else if (i->i.tag == GOTO || i->i.tag == CTXT)
263 : : {
264 : 1166 : i = (Ins*) i->i.link;
265 : : }
266 [ + + ][ + + ]: 4739 : else if (i->i.tag == INIT && isInitial)
267 : : {
268 : : /* The kernel of an initial vs. a non-initial
269 : : state is distinguished not by the presence
270 : : of the INIT itself, but by the presence of
271 : : additional kernel Ins on the other side of
272 : : the INIT. */
273 : 2 : i = (Ins*) i->i.link;
274 : : }
275 : : else
276 : 4737 : break;
277 : : }
278 : :
279 : 4792 : return cP;
280 : : }
281 : :
282 : : struct GoTo
283 : : {
284 : : Char ch;
285 : : void *to;
286 : : };
287 : :
288 : 24 : DFA::DFA(Ins *ins, unsigned ni, unsigned lb, unsigned ub, const Char *rep)
289 : : : lbChar(lb)
290 : : , ubChar(ub)
291 : : , nStates(0)
292 : : , head(NULL)
293 : : , tail(&head)
294 : : , toDo(NULL)
295 : : , free_ins(ins)
296 : 24 : , free_rep(rep)
297 : : {
298 [ + - ]: 24 : Ins **work = new Ins * [ni + 1];
299 : 24 : unsigned nc = ub - lb;
300 [ + - ]: 24 : GoTo *goTo = new GoTo[nc];
301 [ + - ]: 24 : Span *span = new Span[nc];
302 : 24 : memset((char*) goTo, 0, nc*sizeof(GoTo));
303 : :
304 : : /* Build the initial state, based on the set of Ins
305 : : that can be reached from &ins[0], including Ins
306 : : reachable only through ^/INIT operations. */
307 : 24 : findState(work, closure(work, &ins[0], true) - work);
308 : :
309 [ + + ]: 179 : while (toDo)
310 : : {
311 : 155 : State *s = toDo;
312 : 155 : toDo = s->link;
313 : :
314 : : Ins **cP, **iP, *i;
315 : 155 : unsigned nGoTos = 0;
316 : : unsigned j;
317 : :
318 : 155 : s->rule = NULL;
319 : :
320 [ + + ]: 815 : for (iP = s->kernel; (i = *iP); ++iP)
321 : : {
322 [ + + ]: 660 : if (i->i.tag == CHAR)
323 : : {
324 [ + + ]: 2135 : for (Ins *j = i + 1; j < (Ins*) i->i.link; ++j)
325 : : {
326 [ + + ]: 1532 : if (!(j->c.link = goTo[j->c.value - lb].to))
327 : 1061 : goTo[nGoTos++].ch = j->c.value;
328 : :
329 : 1532 : goTo[j->c.value - lb].to = j;
330 : : }
331 : : }
332 [ + - ]: 57 : else if (i->i.tag == TERM)
333 : : {
334 [ + + ][ - + ]: 57 : if (!s->rule || ((RuleOp*) i->i.link)->accept < s->rule->accept)
335 : 56 : s->rule = (RuleOp*) i->i.link;
336 : : }
337 [ # # ]: 0 : else if (i->i.tag == CTXT)
338 : : {
339 : 0 : s->isPreCtxt = true;
340 : : }
341 : : }
342 : :
343 [ + + ]: 1216 : for (j = 0; j < nGoTos; ++j)
344 : : {
345 : 1061 : GoTo *go = &goTo[goTo[j].ch - lb];
346 : 1061 : i = (Ins*) go->to;
347 : :
348 [ + + ]: 2593 : for (cP = work; i; i = (Ins*) i->c.link)
349 : 1532 : cP = closure(cP, i + i->c.bump, false);
350 : :
351 : 1061 : go->to = findState(work, cP - work);
352 : : }
353 : :
354 : 155 : s->go.nSpans = 0;
355 : :
356 [ + + ]: 1028 : for (j = 0; j < nc;)
357 : : {
358 : 873 : State *to = (State*) goTo[rep[j]].to;
359 : :
360 [ + + ][ + + ]: 39680 : while (++j < nc && goTo[rep[j]].to == to) ;
[ + + ]
361 : :
362 : 873 : span[s->go.nSpans].ub = lb + j;
363 : :
364 : 873 : span[s->go.nSpans].to = to;
365 : :
366 : 873 : s->go.nSpans++;
367 : : }
368 : :
369 [ + + ]: 1216 : for (j = nGoTos; j-- > 0;)
370 : 1061 : goTo[goTo[j].ch - lb].to = NULL;
371 : :
372 [ + - ]: 155 : s->go.span = new Span[s->go.nSpans];
373 : :
374 : 155 : memcpy((char*) s->go.span, (char*) span, s->go.nSpans*sizeof(Span));
375 : :
376 [ + - ]: 155 : (void) new Match(s);
377 : :
378 : : }
379 : :
380 [ + - ]: 24 : delete [] work;
381 [ + - ]: 24 : delete [] goTo;
382 [ + - ]: 24 : delete [] span;
383 : 24 : }
384 : :
385 : 0 : DFA::~DFA()
386 : : {
387 : : State *s;
388 : :
389 [ # # ]: 0 : while ((s = head))
390 : : {
391 : 0 : head = s->next;
392 [ # # ]: 0 : delete s;
393 : : }
394 [ # # ]: 0 : delete [] free_ins;
395 [ # # ]: 0 : delete [] free_rep;
396 [ # # ]: 0 : delete [] saves;
397 [ # # ]: 0 : delete [] rules;
398 : 0 : }
399 : :
400 : 279 : void DFA::addState(State **a, State *s)
401 : : {
402 : 279 : s->label = nStates++;
403 : 279 : s->next = *a;
404 : 279 : *a = s;
405 : :
406 [ + + ]: 279 : if (a == tail)
407 : 175 : tail = &s->next;
408 : 279 : }
409 : :
410 : : /* Finds or creates the unique state in the DFA with specified kernel.
411 : : In order for this function to work, the kernel *must* have been
412 : : obtained from an invocation of closure(), which marks the appropriate
413 : : Ins belonging to the kernel. */
414 : 1085 : State *DFA::findState(Ins **kernel, unsigned kCount)
415 : : {
416 : : Ins **cP, **iP, *i;
417 : : State *s;
418 : :
419 : 1085 : kernel[kCount] = NULL;
420 : :
421 : 1085 : cP = kernel;
422 : :
423 : : /* Unmark all Ins which don't cross state boundaries, to
424 : : obtain the genuine kernel. */
425 [ + + ]: 10226 : for (iP = kernel; (i = *iP); ++iP)
426 : : {
427 [ + + ][ + + ]: 9141 : if (i->i.tag == CHAR || i->i.tag == TERM || i->i.tag == CTXT)
[ - + ]
428 : : {
429 : 4681 : *cP++ = i;
430 : : }
431 : : else
432 : : {
433 : 4460 : unmark(i);
434 : : }
435 : : }
436 : :
437 : 1085 : kCount = cP - kernel;
438 : 1085 : kernel[kCount] = NULL;
439 : :
440 : : /* Compare to the kernels of existing states (by checking
441 : : if the kernel sizes match and if s->kernel contains no
442 : : unmarked Ins). */
443 [ + + ]: 3121 : for (s = head; s; s = s->next)
444 : : {
445 [ + + ]: 2966 : if (s->kCount == kCount)
446 : : {
447 [ + + ]: 6712 : for (iP = s->kernel; (i = *iP); ++iP)
448 [ + + ]: 5782 : if (!isMarked(i))
449 : 538 : goto nextState;
450 : :
451 : 930 : goto unmarkAll;
452 : : }
453 : :
454 : : nextState:
455 : : ;
456 : : }
457 : :
458 : : /* If no existing state found, create one and push it
459 : : on the toDo list (using s->link to maintain a stack). */
460 : 155 : s = new State;
461 : 155 : addState(tail, s);
462 : 155 : s->kCount = kCount;
463 [ + - ]: 155 : s->kernel = new Ins * [kCount + 1];
464 : 155 : memcpy(s->kernel, kernel, (kCount + 1)*sizeof(Ins*));
465 : 155 : s->link = toDo;
466 : 155 : toDo = s;
467 : :
468 : : unmarkAll:
469 : :
470 [ + + ]: 5766 : for (iP = kernel; (i = *iP); ++iP)
471 : 4681 : unmark(i);
472 : :
473 : 1085 : return s;
474 : : }
475 : :
476 [ + - ][ + - ]: 7242 : } // end namespace re2c
477 : :
|
