1 /*
2 * Copyright 2002-2004 Adrian Thurston <thurston@complang.org>
3 */
4
5 /* This file is part of Ragel.
6 *
7 * Ragel is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * Ragel is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with Ragel; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21
22 #include "fsmgraph.h"
23 #include <iostream>
24 using std::cerr;
25 using std::endl;
26
27 CondData *condData = 0;
28 KeyOps *keyOps = 0;
29
30 /* Insert an action into an action table. */
setAction(int ordering,Action * action)31 void ActionTable::setAction( int ordering, Action *action )
32 {
33 /* Multi-insert in case specific instances of an action appear in a
34 * transition more than once. */
35 insertMulti( ordering, action );
36 }
37
38 /* Set all the action from another action table in this table. */
setActions(const ActionTable & other)39 void ActionTable::setActions( const ActionTable &other )
40 {
41 for ( ActionTable::Iter action = other; action.lte(); action++ )
42 insertMulti( action->key, action->value );
43 }
44
setActions(int * orderings,Action ** actions,int nActs)45 void ActionTable::setActions( int *orderings, Action **actions, int nActs )
46 {
47 for ( int a = 0; a < nActs; a++ )
48 insertMulti( orderings[a], actions[a] );
49 }
50
hasAction(Action * action)51 bool ActionTable::hasAction( Action *action )
52 {
53 for ( int a = 0; a < length(); a++ ) {
54 if ( data[a].value == action )
55 return true;
56 }
57 return false;
58 }
59
60 /* Insert an action into an action table. */
setAction(int ordering,LongestMatchPart * action)61 void LmActionTable::setAction( int ordering, LongestMatchPart *action )
62 {
63 /* Multi-insert in case specific instances of an action appear in a
64 * transition more than once. */
65 insertMulti( ordering, action );
66 }
67
68 /* Set all the action from another action table in this table. */
setActions(const LmActionTable & other)69 void LmActionTable::setActions( const LmActionTable &other )
70 {
71 for ( LmActionTable::Iter action = other; action.lte(); action++ )
72 insertMulti( action->key, action->value );
73 }
74
setAction(int ordering,Action * action,int transferPoint)75 void ErrActionTable::setAction( int ordering, Action *action, int transferPoint )
76 {
77 insertMulti( ErrActionTableEl( action, ordering, transferPoint ) );
78 }
79
setActions(const ErrActionTable & other)80 void ErrActionTable::setActions( const ErrActionTable &other )
81 {
82 for ( ErrActionTable::Iter act = other; act.lte(); act++ )
83 insertMulti( ErrActionTableEl( act->action, act->ordering, act->transferPoint ) );
84 }
85
86 /* Insert a priority into this priority table. Looks out for priorities on
87 * duplicate keys. */
setPrior(int ordering,PriorDesc * desc)88 void PriorTable::setPrior( int ordering, PriorDesc *desc )
89 {
90 PriorEl *lastHit = 0;
91 PriorEl *insed = insert( PriorEl(ordering, desc), &lastHit );
92 if ( insed == 0 ) {
93 /* This already has a priority on the same key as desc. Overwrite the
94 * priority if the ordering is larger (later in time). */
95 if ( ordering >= lastHit->ordering )
96 *lastHit = PriorEl( ordering, desc );
97 }
98 }
99
100 /* Set all the priorities from a priorTable in this table. */
setPriors(const PriorTable & other)101 void PriorTable::setPriors( const PriorTable &other )
102 {
103 /* Loop src priorities once to overwrite duplicates. */
104 PriorTable::Iter priorIt = other;
105 for ( ; priorIt.lte(); priorIt++ )
106 setPrior( priorIt->ordering, priorIt->desc );
107 }
108
109 /* Set the priority of starting transitions. Isolates the start state so it has
110 * no other entry points, then sets the priorities of all the transitions out
111 * of the start state. If the start state is final, then the outPrior of the
112 * start state is also set. The idea is that a machine that accepts the null
113 * string can still specify the starting trans prior for when it accepts the
114 * null word. */
startFsmPrior(int ordering,PriorDesc * prior)115 void FsmAp::startFsmPrior( int ordering, PriorDesc *prior )
116 {
117 /* Make sure the start state has no other entry points. */
118 isolateStartState();
119
120 /* Walk all transitions out of the start state. */
121 for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
122 if ( trans->toState != 0 )
123 trans->priorTable.setPrior( ordering, prior );
124 }
125
126 /* If the new start state is final then set the out priority. This follows
127 * the same convention as setting start action in the out action table of
128 * a final start state. */
129 if ( startState->stateBits & STB_ISFINAL )
130 startState->outPriorTable.setPrior( ordering, prior );
131 }
132
133 /* Set the priority of all transitions in a graph. Walks all transition lists
134 * and all def transitions. */
allTransPrior(int ordering,PriorDesc * prior)135 void FsmAp::allTransPrior( int ordering, PriorDesc *prior )
136 {
137 /* Walk the list of all states. */
138 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
139 /* Walk the out list of the state. */
140 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
141 if ( trans->toState != 0 )
142 trans->priorTable.setPrior( ordering, prior );
143 }
144 }
145 }
146
147 /* Set the priority of all transitions that go into a final state. Note that if
148 * any entry states are final, we will not be setting the priority of any
149 * transitions that may go into those states in the future. The graph does not
150 * support pending in transitions in the same way pending out transitions are
151 * supported. */
finishFsmPrior(int ordering,PriorDesc * prior)152 void FsmAp::finishFsmPrior( int ordering, PriorDesc *prior )
153 {
154 /* Walk all final states. */
155 for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) {
156 /* Walk all in transitions of the final state. */
157 for ( TransInList::Iter trans = (*state)->inList; trans.lte(); trans++ )
158 trans->priorTable.setPrior( ordering, prior );
159 }
160 }
161
162 /* Set the priority of any future out transitions that may be made going out of
163 * this state machine. */
leaveFsmPrior(int ordering,PriorDesc * prior)164 void FsmAp::leaveFsmPrior( int ordering, PriorDesc *prior )
165 {
166 /* Set priority in all final states. */
167 for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
168 (*state)->outPriorTable.setPrior( ordering, prior );
169 }
170
171
172 /* Set actions to execute on starting transitions. Isolates the start state
173 * so it has no other entry points, then adds to the transition functions
174 * of all the transitions out of the start state. If the start state is final,
175 * then the func is also added to the start state's out func list. The idea is
176 * that a machine that accepts the null string can execute a start func when it
177 * matches the null word, which can only be done when leaving the start/final
178 * state. */
startFsmAction(int ordering,Action * action)179 void FsmAp::startFsmAction( int ordering, Action *action )
180 {
181 /* Make sure the start state has no other entry points. */
182 isolateStartState();
183
184 /* Walk the start state's transitions, setting functions. */
185 for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
186 if ( trans->toState != 0 )
187 trans->actionTable.setAction( ordering, action );
188 }
189
190 /* If start state is final then add the action to the out action table.
191 * This means that when the null string is accepted the start action will
192 * not be bypassed. */
193 if ( startState->stateBits & STB_ISFINAL )
194 startState->outActionTable.setAction( ordering, action );
195 }
196
197 /* Set functions to execute on all transitions. Walks the out lists of all
198 * states. */
allTransAction(int ordering,Action * action)199 void FsmAp::allTransAction( int ordering, Action *action )
200 {
201 /* Walk all states. */
202 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
203 /* Walk the out list of the state. */
204 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
205 if ( trans->toState != 0 )
206 trans->actionTable.setAction( ordering, action );
207 }
208 }
209 }
210
211 /* Specify functions to execute upon entering final states. If the start state
212 * is final we can't really specify a function to execute upon entering that
213 * final state the first time. So function really means whenever entering a
214 * final state from within the same fsm. */
finishFsmAction(int ordering,Action * action)215 void FsmAp::finishFsmAction( int ordering, Action *action )
216 {
217 /* Walk all final states. */
218 for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) {
219 /* Walk the final state's in list. */
220 for ( TransInList::Iter trans = (*state)->inList; trans.lte(); trans++ )
221 trans->actionTable.setAction( ordering, action );
222 }
223 }
224
225 /* Add functions to any future out transitions that may be made going out of
226 * this state machine. */
leaveFsmAction(int ordering,Action * action)227 void FsmAp::leaveFsmAction( int ordering, Action *action )
228 {
229 /* Insert the action in the outActionTable of all final states. */
230 for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
231 (*state)->outActionTable.setAction( ordering, action );
232 }
233
234 /* Add functions to the longest match action table for constructing scanners. */
longMatchAction(int ordering,LongestMatchPart * lmPart)235 void FsmAp::longMatchAction( int ordering, LongestMatchPart *lmPart )
236 {
237 /* Walk all final states. */
238 for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) {
239 /* Walk the final state's in list. */
240 for ( TransInList::Iter trans = (*state)->inList; trans.lte(); trans++ )
241 trans->lmActionTable.setAction( ordering, lmPart );
242 }
243 }
244
fillGaps(StateAp * state)245 void FsmAp::fillGaps( StateAp *state )
246 {
247 if ( state->outList.length() == 0 ) {
248 /* Add the range on the lower and upper bound. */
249 attachNewTrans( state, 0, keyOps->minKey, keyOps->maxKey );
250 }
251 else {
252 TransList srcList;
253 srcList.transfer( state->outList );
254
255 /* Check for a gap at the beginning. */
256 TransList::Iter trans = srcList, next;
257 if ( keyOps->minKey < trans->lowKey ) {
258 /* Make the high key and append. */
259 Key highKey = trans->lowKey;
260 highKey.decrement();
261
262 attachNewTrans( state, 0, keyOps->minKey, highKey );
263 }
264
265 /* Write the transition. */
266 next = trans.next();
267 state->outList.append( trans );
268
269 /* Keep the last high end. */
270 Key lastHigh = trans->highKey;
271
272 /* Loop each source range. */
273 for ( trans = next; trans.lte(); trans = next ) {
274 /* Make the next key following the last range. */
275 Key nextKey = lastHigh;
276 nextKey.increment();
277
278 /* Check for a gap from last up to here. */
279 if ( nextKey < trans->lowKey ) {
280 /* Make the high end of the range that fills the gap. */
281 Key highKey = trans->lowKey;
282 highKey.decrement();
283
284 attachNewTrans( state, 0, nextKey, highKey );
285 }
286
287 /* Reduce the transition. If it reduced to anything then add it. */
288 next = trans.next();
289 state->outList.append( trans );
290
291 /* Keep the last high end. */
292 lastHigh = trans->highKey;
293 }
294
295 /* Now check for a gap on the end to fill. */
296 if ( lastHigh < keyOps->maxKey ) {
297 /* Get a copy of the default. */
298 lastHigh.increment();
299
300 attachNewTrans( state, 0, lastHigh, keyOps->maxKey );
301 }
302 }
303 }
304
setErrorActions(StateAp * state,const ActionTable & other)305 void FsmAp::setErrorActions( StateAp *state, const ActionTable &other )
306 {
307 /* Fill any gaps in the out list with an error transition. */
308 fillGaps( state );
309
310 /* Set error transitions in the transitions that go to error. */
311 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
312 if ( trans->toState == 0 )
313 trans->actionTable.setActions( other );
314 }
315 }
316
setErrorAction(StateAp * state,int ordering,Action * action)317 void FsmAp::setErrorAction( StateAp *state, int ordering, Action *action )
318 {
319 /* Fill any gaps in the out list with an error transition. */
320 fillGaps( state );
321
322 /* Set error transitions in the transitions that go to error. */
323 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
324 if ( trans->toState == 0 )
325 trans->actionTable.setAction( ordering, action );
326 }
327 }
328
329
330 /* Give a target state for error transitions. */
setErrorTarget(StateAp * state,StateAp * target,int * orderings,Action ** actions,int nActs)331 void FsmAp::setErrorTarget( StateAp *state, StateAp *target, int *orderings,
332 Action **actions, int nActs )
333 {
334 /* Fill any gaps in the out list with an error transition. */
335 fillGaps( state );
336
337 /* Set error target in the transitions that go to error. */
338 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
339 if ( trans->toState == 0 ) {
340 /* The trans goes to error, redirect it. */
341 redirectErrorTrans( trans->fromState, target, trans );
342 trans->actionTable.setActions( orderings, actions, nActs );
343 }
344 }
345 }
346
transferOutActions(StateAp * state)347 void FsmAp::transferOutActions( StateAp *state )
348 {
349 for ( ActionTable::Iter act = state->outActionTable; act.lte(); act++ )
350 state->eofActionTable.setAction( act->key, act->value );
351 state->outActionTable.empty();
352 }
353
transferErrorActions(StateAp * state,int transferPoint)354 void FsmAp::transferErrorActions( StateAp *state, int transferPoint )
355 {
356 for ( int i = 0; i < state->errActionTable.length(); ) {
357 ErrActionTableEl *act = state->errActionTable.data + i;
358 if ( act->transferPoint == transferPoint ) {
359 /* Transfer the error action and remove it. */
360 setErrorAction( state, act->ordering, act->action );
361 if ( ! state->isFinState() )
362 state->eofActionTable.setAction( act->ordering, act->action );
363 state->errActionTable.vremove( i );
364 }
365 else {
366 /* Not transfering and deleting, skip over the item. */
367 i += 1;
368 }
369 }
370 }
371
372 /* Set error actions in the start state. */
startErrorAction(int ordering,Action * action,int transferPoint)373 void FsmAp::startErrorAction( int ordering, Action *action, int transferPoint )
374 {
375 /* Make sure the start state has no other entry points. */
376 isolateStartState();
377
378 /* Add the actions. */
379 startState->errActionTable.setAction( ordering, action, transferPoint );
380 }
381
382 /* Set error actions in all states where there is a transition out. */
allErrorAction(int ordering,Action * action,int transferPoint)383 void FsmAp::allErrorAction( int ordering, Action *action, int transferPoint )
384 {
385 /* Insert actions in the error action table of all states. */
386 for ( StateList::Iter state = stateList; state.lte(); state++ )
387 state->errActionTable.setAction( ordering, action, transferPoint );
388 }
389
390 /* Set error actions in final states. */
finalErrorAction(int ordering,Action * action,int transferPoint)391 void FsmAp::finalErrorAction( int ordering, Action *action, int transferPoint )
392 {
393 /* Add the action to the error table of final states. */
394 for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
395 (*state)->errActionTable.setAction( ordering, action, transferPoint );
396 }
397
notStartErrorAction(int ordering,Action * action,int transferPoint)398 void FsmAp::notStartErrorAction( int ordering, Action *action, int transferPoint )
399 {
400 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
401 if ( state != startState )
402 state->errActionTable.setAction( ordering, action, transferPoint );
403 }
404 }
405
notFinalErrorAction(int ordering,Action * action,int transferPoint)406 void FsmAp::notFinalErrorAction( int ordering, Action *action, int transferPoint )
407 {
408 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
409 if ( ! state->isFinState() )
410 state->errActionTable.setAction( ordering, action, transferPoint );
411 }
412 }
413
414 /* Set error actions in the states that have transitions into a final state. */
middleErrorAction(int ordering,Action * action,int transferPoint)415 void FsmAp::middleErrorAction( int ordering, Action *action, int transferPoint )
416 {
417 /* Isolate the start state in case it is reachable from in inside the
418 * machine, in which case we don't want it set. */
419 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
420 if ( state != startState && ! state->isFinState() )
421 state->errActionTable.setAction( ordering, action, transferPoint );
422 }
423 }
424
425 /* Set EOF actions in the start state. */
startEOFAction(int ordering,Action * action)426 void FsmAp::startEOFAction( int ordering, Action *action )
427 {
428 /* Make sure the start state has no other entry points. */
429 isolateStartState();
430
431 /* Add the actions. */
432 startState->eofActionTable.setAction( ordering, action );
433 }
434
435 /* Set EOF actions in all states where there is a transition out. */
allEOFAction(int ordering,Action * action)436 void FsmAp::allEOFAction( int ordering, Action *action )
437 {
438 /* Insert actions in the EOF action table of all states. */
439 for ( StateList::Iter state = stateList; state.lte(); state++ )
440 state->eofActionTable.setAction( ordering, action );
441 }
442
443 /* Set EOF actions in final states. */
finalEOFAction(int ordering,Action * action)444 void FsmAp::finalEOFAction( int ordering, Action *action )
445 {
446 /* Add the action to the error table of final states. */
447 for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
448 (*state)->eofActionTable.setAction( ordering, action );
449 }
450
notStartEOFAction(int ordering,Action * action)451 void FsmAp::notStartEOFAction( int ordering, Action *action )
452 {
453 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
454 if ( state != startState )
455 state->eofActionTable.setAction( ordering, action );
456 }
457 }
458
notFinalEOFAction(int ordering,Action * action)459 void FsmAp::notFinalEOFAction( int ordering, Action *action )
460 {
461 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
462 if ( ! state->isFinState() )
463 state->eofActionTable.setAction( ordering, action );
464 }
465 }
466
467 /* Set EOF actions in the states that have transitions into a final state. */
middleEOFAction(int ordering,Action * action)468 void FsmAp::middleEOFAction( int ordering, Action *action )
469 {
470 /* Set the actions in all states that are not the start state and not final. */
471 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
472 if ( state != startState && ! state->isFinState() )
473 state->eofActionTable.setAction( ordering, action );
474 }
475 }
476
477 /*
478 * Set To State Actions.
479 */
480
481 /* Set to state actions in the start state. */
startToStateAction(int ordering,Action * action)482 void FsmAp::startToStateAction( int ordering, Action *action )
483 {
484 /* Make sure the start state has no other entry points. */
485 isolateStartState();
486 startState->toStateActionTable.setAction( ordering, action );
487 }
488
489 /* Set to state actions in all states. */
allToStateAction(int ordering,Action * action)490 void FsmAp::allToStateAction( int ordering, Action *action )
491 {
492 /* Insert the action on all states. */
493 for ( StateList::Iter state = stateList; state.lte(); state++ )
494 state->toStateActionTable.setAction( ordering, action );
495 }
496
497 /* Set to state actions in final states. */
finalToStateAction(int ordering,Action * action)498 void FsmAp::finalToStateAction( int ordering, Action *action )
499 {
500 /* Add the action to the error table of final states. */
501 for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
502 (*state)->toStateActionTable.setAction( ordering, action );
503 }
504
notStartToStateAction(int ordering,Action * action)505 void FsmAp::notStartToStateAction( int ordering, Action *action )
506 {
507 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
508 if ( state != startState )
509 state->toStateActionTable.setAction( ordering, action );
510 }
511 }
512
notFinalToStateAction(int ordering,Action * action)513 void FsmAp::notFinalToStateAction( int ordering, Action *action )
514 {
515 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
516 if ( ! state->isFinState() )
517 state->toStateActionTable.setAction( ordering, action );
518 }
519 }
520
521 /* Set to state actions in states that are not final and not the start state. */
middleToStateAction(int ordering,Action * action)522 void FsmAp::middleToStateAction( int ordering, Action *action )
523 {
524 /* Set the action in all states that are not the start state and not final. */
525 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
526 if ( state != startState && ! state->isFinState() )
527 state->toStateActionTable.setAction( ordering, action );
528 }
529 }
530
531 /*
532 * Set From State Actions.
533 */
534
startFromStateAction(int ordering,Action * action)535 void FsmAp::startFromStateAction( int ordering, Action *action )
536 {
537 /* Make sure the start state has no other entry points. */
538 isolateStartState();
539 startState->fromStateActionTable.setAction( ordering, action );
540 }
541
allFromStateAction(int ordering,Action * action)542 void FsmAp::allFromStateAction( int ordering, Action *action )
543 {
544 /* Insert the action on all states. */
545 for ( StateList::Iter state = stateList; state.lte(); state++ )
546 state->fromStateActionTable.setAction( ordering, action );
547 }
548
finalFromStateAction(int ordering,Action * action)549 void FsmAp::finalFromStateAction( int ordering, Action *action )
550 {
551 /* Add the action to the error table of final states. */
552 for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
553 (*state)->fromStateActionTable.setAction( ordering, action );
554 }
555
notStartFromStateAction(int ordering,Action * action)556 void FsmAp::notStartFromStateAction( int ordering, Action *action )
557 {
558 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
559 if ( state != startState )
560 state->fromStateActionTable.setAction( ordering, action );
561 }
562 }
563
notFinalFromStateAction(int ordering,Action * action)564 void FsmAp::notFinalFromStateAction( int ordering, Action *action )
565 {
566 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
567 if ( ! state->isFinState() )
568 state->fromStateActionTable.setAction( ordering, action );
569 }
570 }
571
middleFromStateAction(int ordering,Action * action)572 void FsmAp::middleFromStateAction( int ordering, Action *action )
573 {
574 /* Set the action in all states that are not the start state and not final. */
575 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
576 if ( state != startState && ! state->isFinState() )
577 state->fromStateActionTable.setAction( ordering, action );
578 }
579 }
580
581 /* Shift the function ordering of the start transitions to start
582 * at fromOrder and increase in units of 1. Useful before staring.
583 * Returns the maximum number of order numbers used. */
shiftStartActionOrder(int fromOrder)584 int FsmAp::shiftStartActionOrder( int fromOrder )
585 {
586 int maxUsed = 0;
587
588 /* Walk the start state's transitions, shifting function ordering. */
589 for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
590 /* Walk the function data for the transition and set the keys to
591 * increasing values starting at fromOrder. */
592 int curFromOrder = fromOrder;
593 ActionTable::Iter action = trans->actionTable;
594 for ( ; action.lte(); action++ )
595 action->key = curFromOrder++;
596
597 /* Keep track of the max number of orders used. */
598 if ( curFromOrder - fromOrder > maxUsed )
599 maxUsed = curFromOrder - fromOrder;
600 }
601
602 return maxUsed;
603 }
604
605 /* Remove all priorities. */
clearAllPriorities()606 void FsmAp::clearAllPriorities()
607 {
608 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
609 /* Clear out priority data. */
610 state->outPriorTable.empty();
611
612 /* Clear transition data from the out transitions. */
613 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
614 trans->priorTable.empty();
615 }
616 }
617
618 /* Zeros out the function ordering keys. This may be called before minimization
619 * when it is known that no more fsm operations are going to be done. This
620 * will achieve greater reduction as states will not be separated on the basis
621 * of function ordering. */
nullActionKeys()622 void FsmAp::nullActionKeys( )
623 {
624 /* For each state... */
625 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
626 /* Walk the transitions for the state. */
627 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
628 /* Walk the action table for the transition. */
629 for ( ActionTable::Iter action = trans->actionTable;
630 action.lte(); action++ )
631 action->key = 0;
632
633 /* Walk the action table for the transition. */
634 for ( LmActionTable::Iter action = trans->lmActionTable;
635 action.lte(); action++ )
636 action->key = 0;
637 }
638
639 /* Null the action keys of the to state action table. */
640 for ( ActionTable::Iter action = state->toStateActionTable;
641 action.lte(); action++ )
642 action->key = 0;
643
644 /* Null the action keys of the from state action table. */
645 for ( ActionTable::Iter action = state->fromStateActionTable;
646 action.lte(); action++ )
647 action->key = 0;
648
649 /* Null the action keys of the out transtions. */
650 for ( ActionTable::Iter action = state->outActionTable;
651 action.lte(); action++ )
652 action->key = 0;
653
654 /* Null the action keys of the error action table. */
655 for ( ErrActionTable::Iter action = state->errActionTable;
656 action.lte(); action++ )
657 action->ordering = 0;
658
659 /* Null the action keys eof action table. */
660 for ( ActionTable::Iter action = state->eofActionTable;
661 action.lte(); action++ )
662 action->key = 0;
663 }
664 }
665
666 /* Walk the list of states and verify that non final states do not have out
667 * data, that all stateBits are cleared, and that there are no states with
668 * zero foreign in transitions. */
verifyStates()669 void FsmAp::verifyStates()
670 {
671 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
672 /* Non final states should not have leaving data. */
673 if ( ! (state->stateBits & STB_ISFINAL) ) {
674 assert( state->outActionTable.length() == 0 );
675 assert( state->outCondSet.length() == 0 );
676 assert( state->outPriorTable.length() == 0 );
677 }
678
679 /* Data used in algorithms should be cleared. */
680 assert( (state->stateBits & STB_BOTH) == 0 );
681 assert( state->foreignInTrans > 0 );
682 }
683 }
684
685 /* Compare two transitions according to their relative priority. Since the
686 * base transition has no priority associated with it, the default is to
687 * return equal. */
comparePrior(const PriorTable & priorTable1,const PriorTable & priorTable2)688 int FsmAp::comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 )
689 {
690 /* Looking for differing priorities on same keys. Need to concurrently
691 * scan the priority lists. */
692 PriorTable::Iter pd1 = priorTable1;
693 PriorTable::Iter pd2 = priorTable2;
694 while ( pd1.lte() && pd2.lte() ) {
695 /* Check keys. */
696 if ( pd1->desc->key < pd2->desc->key )
697 pd1.increment();
698 else if ( pd1->desc->key > pd2->desc->key )
699 pd2.increment();
700 /* Keys are the same, check priorities. */
701 else if ( pd1->desc->priority < pd2->desc->priority )
702 return -1;
703 else if ( pd1->desc->priority > pd2->desc->priority )
704 return 1;
705 else {
706 /* Keys and priorities are equal, advance both. */
707 pd1.increment();
708 pd2.increment();
709 }
710 }
711
712 /* No differing priorities on the same key. */
713 return 0;
714 }
715
716 /* Compares two transitions according to priority and functions. Pointers
717 * should not be null. Does not consider to state or from state. Compare two
718 * transitions according to the data contained in the transitions. Data means
719 * any properties added to user transitions that may differentiate them. Since
720 * the base transition has no data, the default is to return equal. */
compareTransData(TransAp * trans1,TransAp * trans2)721 int FsmAp::compareTransData( TransAp *trans1, TransAp *trans2 )
722 {
723 /* Compare the prior table. */
724 int cmpRes = CmpPriorTable::compare( trans1->priorTable,
725 trans2->priorTable );
726 if ( cmpRes != 0 )
727 return cmpRes;
728
729 /* Compare longest match action tables. */
730 cmpRes = CmpLmActionTable::compare(trans1->lmActionTable,
731 trans2->lmActionTable);
732 if ( cmpRes != 0 )
733 return cmpRes;
734
735 /* Compare action tables. */
736 return CmpActionTable::compare(trans1->actionTable,
737 trans2->actionTable);
738 }
739
740 /* Callback invoked when another trans (or possibly this) is added into this
741 * transition during the merging process. Draw in any properties of srcTrans
742 * into this transition. AddInTrans is called when a new transitions is made
743 * that will be a duplicate of another transition or a combination of several
744 * other transitions. AddInTrans will be called for each transition that the
745 * new transition is to represent. */
addInTrans(TransAp * destTrans,TransAp * srcTrans)746 void FsmAp::addInTrans( TransAp *destTrans, TransAp *srcTrans )
747 {
748 /* Protect against adding in from ourselves. */
749 if ( srcTrans == destTrans ) {
750 /* Adding in ourselves, need to make a copy of the source transitions.
751 * The priorities are not copied in as that would have no effect. */
752 destTrans->lmActionTable.setActions( LmActionTable(srcTrans->lmActionTable) );
753 destTrans->actionTable.setActions( ActionTable(srcTrans->actionTable) );
754 }
755 else {
756 /* Not a copy of ourself, get the functions and priorities. */
757 destTrans->lmActionTable.setActions( srcTrans->lmActionTable );
758 destTrans->actionTable.setActions( srcTrans->actionTable );
759 destTrans->priorTable.setPriors( srcTrans->priorTable );
760 }
761 }
762
763 /* Compare the properties of states that are embedded by users. Compares out
764 * priorities, out transitions, to, from, out, error and eof action tables. */
compareStateData(const StateAp * state1,const StateAp * state2)765 int FsmAp::compareStateData( const StateAp *state1, const StateAp *state2 )
766 {
767 /* Compare the out priority table. */
768 int cmpRes = CmpPriorTable::
769 compare( state1->outPriorTable, state2->outPriorTable );
770 if ( cmpRes != 0 )
771 return cmpRes;
772
773 /* Test to state action tables. */
774 cmpRes = CmpActionTable::compare( state1->toStateActionTable,
775 state2->toStateActionTable );
776 if ( cmpRes != 0 )
777 return cmpRes;
778
779 /* Test from state action tables. */
780 cmpRes = CmpActionTable::compare( state1->fromStateActionTable,
781 state2->fromStateActionTable );
782 if ( cmpRes != 0 )
783 return cmpRes;
784
785 /* Test out action tables. */
786 cmpRes = CmpActionTable::compare( state1->outActionTable,
787 state2->outActionTable );
788 if ( cmpRes != 0 )
789 return cmpRes;
790
791 /* Test out condition sets. */
792 cmpRes = CmpOutCondSet::compare( state1->outCondSet,
793 state2->outCondSet );
794 if ( cmpRes != 0 )
795 return cmpRes;
796
797 /* Test out error action tables. */
798 cmpRes = CmpErrActionTable::compare( state1->errActionTable,
799 state2->errActionTable );
800 if ( cmpRes != 0 )
801 return cmpRes;
802
803 /* Test eof action tables. */
804 return CmpActionTable::compare( state1->eofActionTable,
805 state2->eofActionTable );
806 }
807
808
809 /* Invoked when a state looses its final state status and the leaving
810 * transition embedding data should be deleted. */
clearOutData(StateAp * state)811 void FsmAp::clearOutData( StateAp *state )
812 {
813 /* Kill the out actions and priorities. */
814 state->outActionTable.empty();
815 state->outCondSet.empty();
816 state->outPriorTable.empty();
817 }
818
hasOutData(StateAp * state)819 bool FsmAp::hasOutData( StateAp *state )
820 {
821 return ( state->outActionTable.length() > 0 ||
822 state->outCondSet.length() > 0 ||
823 state->outPriorTable.length() > 0 );
824 }
825
826 /*
827 * Setting Conditions.
828 */
829
830 void logNewExpansion( Expansion *exp );
831 void logCondSpace( CondSpace *condSpace );
832
addCondSpace(const CondSet & condSet)833 CondSpace *FsmAp::addCondSpace( const CondSet &condSet )
834 {
835 CondSpace *condSpace = condData->condSpaceMap.find( condSet );
836 if ( condSpace == 0 ) {
837 /* Do we have enough keyspace left? */
838 Size availableSpace = condData->lastCondKey.availableSpace();
839 Size neededSpace = (1 << condSet.length() ) * keyOps->alphSize();
840 if ( neededSpace > availableSpace )
841 throw FsmConstructFail( FsmConstructFail::CondNoKeySpace );
842
843 Key baseKey = condData->lastCondKey;
844 baseKey.increment();
845 condData->lastCondKey += (1 << condSet.length() ) * keyOps->alphSize();
846
847 condSpace = new CondSpace( condSet );
848 condSpace->baseKey = baseKey;
849 condData->condSpaceMap.insert( condSpace );
850
851 #ifdef LOG_CONDS
852 cerr << "adding new condition space" << endl;
853 cerr << " condition set: ";
854 logCondSpace( condSpace );
855 cerr << endl;
856 cerr << " baseKey: " << baseKey.getVal() << endl;
857 #endif
858 }
859 return condSpace;
860 }
861
startFsmCondition(Action * condAction,bool sense)862 void FsmAp::startFsmCondition( Action *condAction, bool sense )
863 {
864 /* Make sure the start state has no other entry points. */
865 isolateStartState();
866 embedCondition( startState, condAction, sense );
867 }
868
allTransCondition(Action * condAction,bool sense)869 void FsmAp::allTransCondition( Action *condAction, bool sense )
870 {
871 for ( StateList::Iter state = stateList; state.lte(); state++ )
872 embedCondition( state, condAction, sense );
873 }
874
leaveFsmCondition(Action * condAction,bool sense)875 void FsmAp::leaveFsmCondition( Action *condAction, bool sense )
876 {
877 for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
878 (*state)->outCondSet.insert( OutCond( condAction, sense ) );
879 }
880