email address update: thurston@cs.queensu.ca -> thurston@complang.org
[external/ragel.git] / ragel / fsmap.cpp
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. */
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. */
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
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
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. */
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. */
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
75 void ErrActionTable::setAction( int ordering, Action *action, int transferPoint )
76 {
77         insertMulti( ErrActionTableEl( action, ordering, transferPoint ) );
78 }
79
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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
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
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
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. */
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
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
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. */
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. */
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. */
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
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
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. */
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. */
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. */
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. */
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
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
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. */
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. */
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. */
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. */
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
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
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. */
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
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
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
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
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
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
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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
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
831 void logNewExpansion( Expansion *exp );
832 void logCondSpace( CondSpace *condSpace );
833
834 CondSpace *FsmAp::addCondSpace( const CondSet &condSet )
835 {
836         CondSpace *condSpace = condData->condSpaceMap.find( condSet );
837         if ( condSpace == 0 ) {
838                 /* Do we have enough keyspace left? */
839                 Size availableSpace = condData->lastCondKey.availableSpace();
840                 Size neededSpace = (1 << condSet.length() ) * keyOps->alphSize();
841                 if ( neededSpace > availableSpace )
842                         throw FsmConstructFail( FsmConstructFail::CondNoKeySpace );
843
844                 Key baseKey = condData->lastCondKey;
845                 baseKey.increment();
846                 condData->lastCondKey += (1 << condSet.length() ) * keyOps->alphSize();
847
848                 condSpace = new CondSpace( condSet );
849                 condSpace->baseKey = baseKey;
850                 condData->condSpaceMap.insert( condSpace );
851
852                 #ifdef LOG_CONDS
853                 cerr << "adding new condition space" << endl;
854                 cerr << "  condition set: ";
855                 logCondSpace( condSpace );
856                 cerr << endl;
857                 cerr << "  baseKey: " << baseKey.getVal() << endl;
858                 #endif
859         }
860         return condSpace;
861 }
862
863 void FsmAp::startFsmCondition( Action *condAction, bool sense )
864 {
865         /* Make sure the start state has no other entry points. */
866         isolateStartState();
867         embedCondition( startState, condAction, sense );
868 }
869
870 void FsmAp::allTransCondition( Action *condAction, bool sense )
871 {
872         for ( StateList::Iter state = stateList; state.lte(); state++ )
873                 embedCondition( state, condAction, sense );
874 }
875
876 void FsmAp::leaveFsmCondition( Action *condAction, bool sense )
877 {
878         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
879                 (*state)->outCondSet.insert( OutCond( condAction, sense ) );
880 }