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 : : #ifndef _re2c_dfa_h
15 : : #define _re2c_dfa_h
16 : :
17 : : #include <iosfwd>
18 : : #include <map>
19 : : #include "re2c-regex.h"
20 : :
21 : : namespace re2c
22 : : {
23 : :
24 : : extern void prtCh(std::ostream&, unsigned);
25 : : extern void prtHex(std::ostream&, unsigned);
26 : : extern void prtChOrHex(std::ostream&, unsigned);
27 : : extern void printSpan(std::ostream&, unsigned, unsigned);
28 : :
29 : : class DFA;
30 : :
31 : : class State;
32 : :
33 : : class Action
34 : : {
35 : :
36 : : public:
37 : : State *state;
38 : :
39 : : public:
40 : : Action(State*);
41 : : virtual ~Action();
42 : :
43 : : virtual void emit(std::ostream&, unsigned, bool&, const std::string&) const = 0;
44 : : virtual bool isRule() const;
45 : : virtual bool isMatch() const;
46 : : virtual bool isInitial() const;
47 : : virtual bool readAhead() const;
48 : :
49 : : #ifdef PEDANTIC
50 : : protected:
51 : : Action(const Action& oth)
52 : : : state(oth.state)
53 : : {
54 : : }
55 : : Action& operator = (const Action& oth)
56 : : {
57 : : state = oth.state;
58 : : return *this;
59 : : }
60 : : #endif
61 : : };
62 : :
63 [ - + ]: 261 : class Match: public Action
64 : : {
65 : : public:
66 : : Match(State*);
67 : : void emit(std::ostream&, unsigned, bool&, const std::string&) const;
68 : : bool isMatch() const;
69 : : };
70 : :
71 [ # # ]: 0 : class Enter: public Action
72 : : {
73 : : public:
74 : : unsigned label;
75 : :
76 : : public:
77 : : Enter(State*, unsigned);
78 : : void emit(std::ostream&, unsigned, bool&, const std::string&) const;
79 : : };
80 : :
81 [ # # ]: 0 : class Initial: public Enter
82 : : {
83 : : public:
84 : : bool setMarker;
85 : :
86 : : public:
87 : : Initial(State*, unsigned, bool);
88 : : void emit(std::ostream&, unsigned, bool&, const std::string&) const;
89 : : bool isInitial() const;
90 : : };
91 : :
92 [ - + ]: 322 : class Save: public Match
93 : : {
94 : :
95 : : public:
96 : : unsigned selector;
97 : :
98 : : public:
99 : : Save(State*, unsigned);
100 : : void emit(std::ostream&, unsigned, bool&, const std::string&) const;
101 : : bool isMatch() const;
102 : : };
103 : :
104 [ # # ]: 0 : class Move: public Action
105 : : {
106 : :
107 : : public:
108 : : Move(State*);
109 : : void emit(std::ostream&, unsigned, bool&, const std::string&) const;
110 : : };
111 : :
112 [ # # ][ # # ]: 0 : class Accept: public Action
113 : : {
114 : :
115 : : public:
116 : : typedef std::map<unsigned, State*> RuleMap;
117 : :
118 : : unsigned nRules;
119 : : unsigned *saves;
120 : : State **rules;
121 : : RuleMap mapRules;
122 : :
123 : : public:
124 : : Accept(State*, unsigned, unsigned*, State**);
125 : : void emit(std::ostream&, unsigned, bool&, const std::string&) const;
126 : : void emitBinary(std::ostream &o, unsigned ind, unsigned l, unsigned r, bool &readCh) const;
127 : : void genRuleMap();
128 : :
129 : : #ifdef PEDANTIC
130 : : private:
131 : : Accept(const Accept& oth)
132 : : : Action(oth)
133 : : , nRules(oth.nRules)
134 : : , saves(oth.saves)
135 : : , rules(oth.rules)
136 : : {
137 : : }
138 : : Accept& operator=(const Accept& oth)
139 : : {
140 : : new(this) Accept(oth);
141 : : return *this;
142 : : }
143 : : #endif
144 : : };
145 : :
146 [ # # ]: 0 : class Rule: public Action
147 : : {
148 : :
149 : : public:
150 : : RuleOp *rule;
151 : :
152 : : public:
153 : : Rule(State*, RuleOp*);
154 : : void emit(std::ostream&, unsigned, bool&, const std::string&) const;
155 : : bool isRule() const;
156 : :
157 : : #ifdef PEDANTIC
158 : : private:
159 : : Rule (const Rule& oth)
160 : : : Action(oth)
161 : : , rule(oth.rule)
162 : : {
163 : : }
164 : : Rule& operator=(const Rule& oth)
165 : : {
166 : : new(this) Rule(oth);
167 : : return *this;
168 : : }
169 : : #endif
170 : : };
171 : :
172 : : class Span
173 : : {
174 : :
175 : : public:
176 : : unsigned ub;
177 : : State *to;
178 : :
179 : : public:
180 : : unsigned show(std::ostream&, unsigned) const;
181 : : };
182 : :
183 : : class Go
184 : : {
185 : : public:
186 : 279 : Go()
187 : : : nSpans(0)
188 : : , wSpans(~0u)
189 : : , lSpans(~0u)
190 : : , dSpans(~0u)
191 : : , lTargets(~0u)
192 : 279 : , span(NULL)
193 : : {
194 : 279 : }
195 : :
196 : : public:
197 : : unsigned nSpans; // number of spans
198 : : unsigned wSpans; // number of spans in wide mode
199 : : unsigned lSpans; // number of low (non wide) spans
200 : : unsigned dSpans; // number of decision spans (decide between g and b mode)
201 : : unsigned lTargets;
202 : : Span *span;
203 : :
204 : : public:
205 : : void genGoto( std::ostream&, unsigned ind, const State *from, const State *next, bool &readCh);
206 : : void genBase( std::ostream&, unsigned ind, const State *from, const State *next, bool &readCh, unsigned mask) const;
207 : : void genLinear(std::ostream&, unsigned ind, const State *from, const State *next, bool &readCh, unsigned mask) const;
208 : : void genBinary(std::ostream&, unsigned ind, const State *from, const State *next, bool &readCh, unsigned mask) const;
209 : : void genSwitch(std::ostream&, unsigned ind, const State *from, const State *next, bool &readCh, unsigned mask) const;
210 : : void genCpGoto(std::ostream&, unsigned ind, const State *from, const State *next, bool &readCh) const;
211 : : void compact();
212 : : void unmap(Go*, const State*);
213 : : };
214 : :
215 : : class State
216 : : {
217 : :
218 : : public:
219 : : unsigned label; // number of state inside DFA
220 : : State *next; // pointer to next state inside DFA
221 : :
222 : : RuleOp *rule;
223 : : State *link; // for the DFA builder's to-process list
224 : : unsigned depth; // for finding SCCs
225 : :
226 : : unsigned kCount;
227 : : Ins **kernel; // set of Ins which exit this state
228 : :
229 : : bool isPreCtxt;
230 : : bool isBase;
231 : : Go go;
232 : : Action *action;
233 : :
234 : : public:
235 : : State();
236 : : ~State();
237 : : void emit(std::ostream&, unsigned, bool&, const std::string&) const;
238 : : friend std::ostream& operator<<(std::ostream&, const State&);
239 : : friend std::ostream& operator<<(std::ostream&, const State*);
240 : :
241 : : #ifdef PEDANTIC
242 : : private:
243 : : State(const State& oth)
244 : : : label(oth.label)
245 : : , rule(oth.rule)
246 : : , next(oth.next)
247 : : , link(oth.link)
248 : : , depth(oth.depth)
249 : : , kCount(oth.kCount)
250 : : , kernel(oth.kernel)
251 : : , isBase(oth.isBase)
252 : : , go(oth.go)
253 : : , action(oth.action)
254 : : {
255 : : }
256 : : State& operator = (const State& oth)
257 : : {
258 : : new(this) State(oth);
259 : : return *this;
260 : : }
261 : : #endif
262 : : };
263 : :
264 : : class DFA
265 : : {
266 : :
267 : : public:
268 : : unsigned lbChar;
269 : : unsigned ubChar;
270 : : unsigned nStates;
271 : : State *head, **tail;
272 : : State *toDo;
273 : : const Ins *free_ins;
274 : : const Char *free_rep;
275 : :
276 : : protected:
277 : : bool bSaveOnHead;
278 : : unsigned *saves;
279 : : State **rules;
280 : :
281 : : public:
282 : : DFA(Ins*, unsigned, unsigned, unsigned, const Char*);
283 : : ~DFA();
284 : : void addState(State**, State*);
285 : : State *findState(Ins**, unsigned);
286 : : void split(State*);
287 : :
288 : : void findSCCs();
289 : : void findBaseState();
290 : : void prepare();
291 : : void emit(std::ostream&, unsigned&, const RegExpMap*, const std::string&, bool, bool&);
292 : :
293 : : friend std::ostream& operator<<(std::ostream&, const DFA&);
294 : : friend std::ostream& operator<<(std::ostream&, const DFA*);
295 : :
296 : : #ifdef PEDANTIC
297 : : DFA(const DFA& oth)
298 : : : lbChar(oth.lbChar)
299 : : , ubChar(oth.ubChar)
300 : : , nStates(oth.nStates)
301 : : , head(oth.head)
302 : : , tail(oth.tail)
303 : : , toDo(oth.toDo)
304 : : {
305 : : }
306 : : DFA& operator = (const DFA& oth)
307 : : {
308 : : new(this) DFA(oth);
309 : : return *this;
310 : : }
311 : : #endif
312 : : };
313 : :
314 : 489 : inline Action::Action(State *s) : state(s)
315 : : {
316 [ - + ]: 489 : delete s->action;
317 : 489 : s->action = this;
318 : 489 : }
319 : :
320 : 211 : inline Action::~Action()
321 : : {
322 [ - + ]: 211 : }
323 : :
324 : 12 : inline bool Action::isRule() const
325 : : {
326 : 12 : return false;
327 : : }
328 : :
329 : 0 : inline bool Action::isMatch() const
330 : : {
331 : 0 : return false;
332 : : }
333 : :
334 : 0 : inline bool Action::isInitial() const
335 : : {
336 : 0 : return false;
337 : : }
338 : :
339 : 20 : inline bool Action::readAhead() const
340 : : {
341 [ + - ][ + - ]: 20 : return !isMatch() || (state && state->next && state->next->action && !state->next->action->isRule());
[ + + ][ + - ]
[ + + ]
342 : : }
343 : :
344 : 342 : inline Match::Match(State *s) : Action(s)
345 : 342 : { }
346 : :
347 : 20 : inline bool Match::isMatch() const
348 : : {
349 : 20 : return true;
350 : : }
351 : :
352 : 23 : inline Enter::Enter(State *s, unsigned l) : Action(s), label(l)
353 : 23 : { }
354 : :
355 : 23 : inline Initial::Initial(State *s, unsigned l, bool b) : Enter(s, l), setMarker(b)
356 : 23 : { }
357 : :
358 : 0 : inline bool Initial::isInitial() const
359 : : {
360 : 0 : return true;
361 : : }
362 : :
363 : 187 : inline Save::Save(State *s, unsigned i) : Match(s), selector(i)
364 : 187 : { }
365 : :
366 : 0 : inline bool Save::isMatch() const
367 : : {
368 : 0 : return false;
369 : : }
370 : :
371 : 4 : inline bool Rule::isRule() const
372 : : {
373 : 4 : return true;
374 : : }
375 : :
376 : 0 : inline std::ostream& operator<<(std::ostream &o, const State *s)
377 : : {
378 : 0 : return o << *s;
379 : : }
380 : :
381 : 0 : inline std::ostream& operator<<(std::ostream &o, const DFA *dfa)
382 : : {
383 : 0 : return o << *dfa;
384 : : }
385 : :
386 : : } // end namespace re2c
387 : :
388 : : #endif
|
