Added the eofTarget to StateAp. This will be used only to track the transition
[external/ragel.git] / ragel / fsmbase.cpp
1 /*
2  *  Copyright 2001-2007 Adrian Thurston <thurston@cs.queensu.ca>
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 <string.h>
23 #include <assert.h>
24 #include "fsmgraph.h"
25
26 /* Simple singly linked list append routine for the fill list. The new state
27  * goes to the end of the list. */
28 void MergeData::fillListAppend( StateAp *state )
29 {
30         state->alg.next = 0;
31
32         if ( stfillHead == 0 ) {
33                 /* List is empty, state becomes head and tail. */
34                 stfillHead = state;
35                 stfillTail = state;
36         }
37         else {
38                 /* List is not empty, state goes after last element. */
39                 stfillTail->alg.next = state;
40                 stfillTail = state;
41         }
42 }
43
44 /* Graph constructor. */
45 FsmAp::FsmAp()
46 :
47         /* No start state. */
48         startState(0),
49         errState(0),
50
51         /* Misfit accounting is a switch, turned on only at specific times. It
52          * controls what happens when states have no way in from the outside
53          * world.. */
54         misfitAccounting(false)
55 {
56 }
57
58 /* Copy all graph data including transitions. */
59 FsmAp::FsmAp( const FsmAp &graph )
60 :
61         /* Lists start empty. Will be filled by copy. */
62         stateList(),
63         misfitList(),
64
65         /* Copy in the entry points, 
66          * pointers will be resolved later. */
67         entryPoints(graph.entryPoints),
68         startState(graph.startState),
69         errState(0),
70
71         /* Will be filled by copy. */
72         finStateSet(),
73         
74         /* Misfit accounting is only on during merging. */
75         misfitAccounting(false)
76 {
77         /* Create the states and record their map in the original state. */
78         StateList::Iter origState = graph.stateList;
79         for ( ; origState.lte(); origState++ ) {
80                 /* Make the new state. */
81                 StateAp *newState = new StateAp( *origState );
82
83                 /* Add the state to the list.  */
84                 stateList.append( newState );
85
86                 /* Set the mapsTo item of the old state. */
87                 origState->alg.stateMap = newState;
88         }
89         
90         /* Derefernce all the state maps. */
91         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
92                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
93                         /* The points to the original in the src machine. The taget's duplicate
94                          * is in the statemap. */
95                         StateAp *toState = trans->toState != 0 ? trans->toState->alg.stateMap : 0;
96
97                         /* Attach The transition to the duplicate. */
98                         trans->toState = 0;
99                         attachTrans( state, toState, trans );
100                 }
101
102                 /* Fix the eofTarg, if set. */
103                 if ( state->eofTarget != 0 )
104                         state->eofTarget = state->eofTarget->alg.stateMap;
105         }
106
107         /* Fix the state pointers in the entry points array. */
108         EntryMapEl *eel = entryPoints.data;
109         for ( int e = 0; e < entryPoints.length(); e++, eel++ ) {
110                 /* Get the duplicate of the state. */
111                 eel->value = eel->value->alg.stateMap;
112
113                 /* Foreign in transitions must be built up when duping machines so
114                  * increment it here. */
115                 eel->value->foreignInTrans += 1;
116         }
117
118         /* Fix the start state pointer and the new start state's count of in
119          * transiions. */
120         startState = startState->alg.stateMap;
121         startState->foreignInTrans += 1;
122
123         /* Build the final state set. */
124         StateSet::Iter st = graph.finStateSet; 
125         for ( ; st.lte(); st++ ) 
126                 finStateSet.insert((*st)->alg.stateMap);
127 }
128
129 /* Deletes all transition data then deletes each state. */
130 FsmAp::~FsmAp()
131 {
132         /* Delete all the transitions. */
133         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
134                 /* Iterate the out transitions, deleting them. */
135                 state->outList.empty();
136         }
137
138         /* Delete all the states. */
139         stateList.empty();
140 }
141
142 /* Set a state final. The state has its isFinState set to true and the state
143  * is added to the finStateSet. */
144 void FsmAp::setFinState( StateAp *state )
145 {
146         /* Is it already a fin state. */
147         if ( state->stateBits & SB_ISFINAL )
148                 return;
149         
150         state->stateBits |= SB_ISFINAL;
151         finStateSet.insert( state );
152 }
153
154 /* Set a state non-final. The has its isFinState flag set false and the state
155  * is removed from the final state set. */
156 void FsmAp::unsetFinState( StateAp *state )
157 {
158         /* Is it already a non-final state? */
159         if ( ! (state->stateBits & SB_ISFINAL) )
160                 return;
161
162         /* When a state looses its final state status it must relinquish all the
163          * properties that are allowed only for final states. */
164         clearOutData( state );
165
166         state->stateBits &= ~ SB_ISFINAL;
167         finStateSet.remove( state );
168 }
169
170 /* Set and unset a state as the start state. */
171 void FsmAp::setStartState( StateAp *state )
172 {
173         /* Sould change from unset to set. */
174         assert( startState == 0 );
175         startState = state;
176
177         if ( misfitAccounting ) {
178                 /* If the number of foreign in transitions is about to go up to 1 then
179                  * take it off the misfit list and put it on the head list. */
180                 if ( state->foreignInTrans == 0 )
181                         stateList.append( misfitList.detach( state ) );
182         }
183
184         /* Up the foreign in transitions to the state. */
185         state->foreignInTrans += 1;
186 }
187
188 void FsmAp::unsetStartState()
189 {
190         /* Should change from set to unset. */
191         assert( startState != 0 );
192
193         /* Decrement the entry's count of foreign entries. */
194         startState->foreignInTrans -= 1;
195
196         if ( misfitAccounting ) {
197                 /* If the number of foreign in transitions just went down to 0 then take
198                  * it off the main list and put it on the misfit list. */
199                 if ( startState->foreignInTrans == 0 )
200                         misfitList.append( stateList.detach( startState ) );
201         }
202
203         startState = 0;
204 }
205
206 /* Associate an id with a state. Makes the state a named entry point. Has no
207  * effect if the entry point is already mapped to the state. */
208 void FsmAp::setEntry( int id, StateAp *state )
209 {
210         /* Insert the id into the state. If the state is already labelled with id,
211          * nothing to do. */
212         if ( state->entryIds.insert( id ) ) {
213                 /* Insert the entry and assert that it succeeds. */
214                 entryPoints.insertMulti( id, state );
215
216                 if ( misfitAccounting ) {
217                         /* If the number of foreign in transitions is about to go up to 1 then
218                          * take it off the misfit list and put it on the head list. */
219                         if ( state->foreignInTrans == 0 )
220                                 stateList.append( misfitList.detach( state ) );
221                 }
222
223                 /* Up the foreign in transitions to the state. */
224                 state->foreignInTrans += 1;
225         }
226 }
227
228 /* Remove the association of an id with a state. The state looses it's entry
229  * point status. Assumes that the id is indeed mapped to state. */
230 void FsmAp::unsetEntry( int id, StateAp *state )
231 {
232         /* Find the entry point in on id. */
233         EntryMapEl *enLow = 0, *enHigh = 0;
234         entryPoints.findMulti( id, enLow, enHigh );
235         while ( enLow->value != state )
236                 enLow += 1;
237
238         /* Remove the record from the map. */
239         entryPoints.remove( enLow );
240
241         /* Remove the state's sense of the link. */
242         state->entryIds.remove( id );
243         state->foreignInTrans -= 1;
244         if ( misfitAccounting ) {
245                 /* If the number of foreign in transitions just went down to 0 then take
246                  * it off the main list and put it on the misfit list. */
247                 if ( state->foreignInTrans == 0 )
248                         misfitList.append( stateList.detach( state ) );
249         }
250 }
251
252 /* Remove all association of an id with states. Assumes that the id is indeed
253  * mapped to a state. */
254 void FsmAp::unsetEntry( int id )
255 {
256         /* Find the entry point in on id. */
257         EntryMapEl *enLow = 0, *enHigh = 0;
258         entryPoints.findMulti( id, enLow, enHigh );
259         for ( EntryMapEl *mel = enLow; mel <= enHigh; mel++ ) {
260                 /* Remove the state's sense of the link. */
261                 mel->value->entryIds.remove( id );
262                 mel->value->foreignInTrans -= 1;
263                 if ( misfitAccounting ) {
264                         /* If the number of foreign in transitions just went down to 0
265                          * then take it off the main list and put it on the misfit list. */
266                         if ( mel->value->foreignInTrans == 0 )
267                                 misfitList.append( stateList.detach( mel->value ) );
268                 }
269         }
270
271         /* Remove the records from the entry points map. */
272         entryPoints.removeMulti( enLow, enHigh );
273 }
274
275
276 void FsmAp::changeEntry( int id, StateAp *to, StateAp *from )
277 {
278         /* Find the entry in the entry map. */
279         EntryMapEl *enLow = 0, *enHigh = 0;
280         entryPoints.findMulti( id, enLow, enHigh );
281         while ( enLow->value != from )
282                 enLow += 1;
283         
284         /* Change it to the new target. */
285         enLow->value = to;
286
287         /* Remove from's sense of the link. */
288         from->entryIds.remove( id );
289         from->foreignInTrans -= 1;
290         if ( misfitAccounting ) {
291                 /* If the number of foreign in transitions just went down to 0 then take
292                  * it off the main list and put it on the misfit list. */
293                 if ( from->foreignInTrans == 0 )
294                         misfitList.append( stateList.detach( from ) );
295         }
296
297         /* Add to's sense of the link. */
298         if ( to->entryIds.insert( id ) != 0 ) {
299                 if ( misfitAccounting ) {
300                         /* If the number of foreign in transitions is about to go up to 1 then
301                          * take it off the misfit list and put it on the head list. */
302                         if ( to->foreignInTrans == 0 )
303                                 stateList.append( misfitList.detach( to ) );
304                 }
305
306                 /* Up the foreign in transitions to the state. */
307                 to->foreignInTrans += 1;
308         }
309 }
310
311
312 /* Clear all entry points from a machine. */
313 void FsmAp::unsetAllEntryPoints()
314 {
315         for ( EntryMap::Iter en = entryPoints; en.lte(); en++ ) {
316                 /* Kill all the state's entry points at once. */
317                 if ( en->value->entryIds.length() > 0 ) {
318                         en->value->foreignInTrans -= en->value->entryIds.length();
319
320                         if ( misfitAccounting ) {
321                                 /* If the number of foreign in transitions just went down to 0
322                                  * then take it off the main list and put it on the misfit
323                                  * list. */
324                                 if ( en->value->foreignInTrans == 0 )
325                                         misfitList.append( stateList.detach( en->value ) );
326                         }
327
328                         /* Clear the set of ids out all at once. */
329                         en->value->entryIds.empty();
330                 }
331         }
332
333         /* Now clear out the entry map all at once. */
334         entryPoints.empty();
335 }
336
337 /* Assigning an epsilon transition into final states. */
338 void FsmAp::epsilonTrans( int id )
339 {
340         for ( StateSet::Iter fs = finStateSet; fs.lte(); fs++ )
341                 (*fs)->epsilonTrans.append( id );
342 }
343
344 /* Mark all states reachable from state. Traverses transitions forward. Used
345  * for removing states that have no path into them. */
346 void FsmAp::markReachableFromHere( StateAp *state )
347 {
348         /* Base case: return; */
349         if ( state->stateBits & SB_ISMARKED )
350                 return;
351         
352         /* Set this state as processed. We are going to visit all states that this
353          * state has a transition to. */
354         state->stateBits |= SB_ISMARKED;
355
356         /* Recurse on all out transitions. */
357         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
358                 if ( trans->toState != 0 )
359                         markReachableFromHere( trans->toState );
360         }
361 }
362
363 void FsmAp::markReachableFromHereStopFinal( StateAp *state )
364 {
365         /* Base case: return; */
366         if ( state->stateBits & SB_ISMARKED )
367                 return;
368         
369         /* Set this state as processed. We are going to visit all states that this
370          * state has a transition to. */
371         state->stateBits |= SB_ISMARKED;
372
373         /* Recurse on all out transitions. */
374         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
375                 StateAp *toState = trans->toState;
376                 if ( toState != 0 && !toState->isFinState() )
377                         markReachableFromHereStopFinal( toState );
378         }
379 }
380
381 /* Mark all states reachable from state. Traverse transitions backwards. Used
382  * for removing dead end paths in graphs. */
383 void FsmAp::markReachableFromHereReverse( StateAp *state )
384 {
385         /* Base case: return; */
386         if ( state->stateBits & SB_ISMARKED )
387                 return;
388         
389         /* Set this state as processed. We are going to visit all states with
390          * transitions into this state. */
391         state->stateBits |= SB_ISMARKED;
392
393         /* Recurse on all items in transitions. */
394         for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ ) 
395                 markReachableFromHereReverse( trans->fromState );
396 }
397
398 /* Determine if there are any entry points into a start state other than the
399  * start state. Setting starting transitions requires that the start state be
400  * isolated. In most cases a start state will already be isolated. */
401 bool FsmAp::isStartStateIsolated()
402 {
403         /* If there are any in transitions then the state is not isolated. */
404         if ( startState->inList.head != 0 )
405                 return false;
406
407         /* If there are any entry points then isolated. */
408         if ( startState->entryIds.length() > 0 )
409                 return false;
410
411         return true;
412 }
413
414 /* Bring in other's entry points. Assumes others states are going to be
415  * copied into this machine. */
416 void FsmAp::copyInEntryPoints( FsmAp *other )
417 {
418         /* Use insert multi because names are not unique. */
419         for ( EntryMap::Iter en = other->entryPoints; en.lte(); en++ )
420                 entryPoints.insertMulti( en->key, en->value );
421 }
422
423
424 void FsmAp::unsetAllFinStates()
425 {
426         for ( StateSet::Iter st = finStateSet; st.lte(); st++ )
427                 (*st)->stateBits &= ~ SB_ISFINAL;
428         finStateSet.empty();
429 }
430
431 void FsmAp::setFinBits( int finStateBits )
432 {
433         for ( int s = 0; s < finStateSet.length(); s++ )
434                 finStateSet.data[s]->stateBits |= finStateBits;
435 }
436
437
438 /* Tests the integrity of the transition lists and the fromStates. */
439 void FsmAp::verifyIntegrity()
440 {
441         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
442                 /* Walk the out transitions and assert fromState is correct. */
443                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
444                         assert( trans->fromState == state );
445
446                 /* Walk the inlist and assert toState is correct. */
447                 for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ ) 
448                         assert( trans->toState == state );
449         }
450 }
451
452 void FsmAp::verifyReachability()
453 {
454         /* Mark all the states that can be reached 
455          * through the set of entry points. */
456         markReachableFromHere( startState );
457         for ( EntryMap::Iter en = entryPoints; en.lte(); en++ )
458                 markReachableFromHere( en->value );
459
460         /* Check that everything got marked. */
461         for ( StateList::Iter st = stateList; st.lte(); st++ ) {
462                 /* Assert it got marked and then clear the mark. */
463                 assert( st->stateBits & SB_ISMARKED );
464                 st->stateBits &= ~ SB_ISMARKED;
465         }
466 }
467
468 void FsmAp::verifyNoDeadEndStates()
469 {
470         /* Mark all states that have paths to the final states. */
471         for ( StateSet::Iter pst = finStateSet; pst.lte(); pst++ )
472                 markReachableFromHereReverse( *pst );
473
474         /* Start state gets honorary marking. Must be done AFTER recursive call. */
475         startState->stateBits |= SB_ISMARKED;
476
477         /* Make sure everything got marked. */
478         for ( StateList::Iter st = stateList; st.lte(); st++ ) {
479                 /* Assert the state got marked and unmark it. */
480                 assert( st->stateBits & SB_ISMARKED );
481                 st->stateBits &= ~ SB_ISMARKED;
482         }
483 }
484
485 void FsmAp::depthFirstOrdering( StateAp *state )
486 {
487         /* Nothing to do if the state is already on the list. */
488         if ( state->stateBits & SB_ONLIST )
489                 return;
490
491         /* Doing depth first, put state on the list. */
492         state->stateBits |= SB_ONLIST;
493         stateList.append( state );
494         
495         /* Recurse on everything ranges. */
496         for ( TransList::Iter tel = state->outList; tel.lte(); tel++ ) {
497                 if ( tel->toState != 0 )
498                         depthFirstOrdering( tel->toState );
499         }
500 }
501
502 /* Ordering states by transition connections. */
503 void FsmAp::depthFirstOrdering()
504 {
505         /* Init on state list flags. */
506         for ( StateList::Iter st = stateList; st.lte(); st++ )
507                 st->stateBits &= ~SB_ONLIST;
508         
509         /* Clear out the state list, we will rebuild it. */
510         int stateListLen = stateList.length();
511         stateList.abandon();
512
513         /* Add back to the state list from the start state and all other entry
514          * points. */
515         if ( errState != 0 )
516                 depthFirstOrdering( errState );
517         depthFirstOrdering( startState );
518         for ( EntryMap::Iter en = entryPoints; en.lte(); en++ )
519                 depthFirstOrdering( en->value );
520         
521         /* Make sure we put everything back on. */
522         assert( stateListLen == stateList.length() );
523 }
524
525 /* Stable sort the states by final state status. */
526 void FsmAp::sortStatesByFinal()
527 {
528         /* Move forward through the list and throw final states onto the end. */
529         StateAp *state = 0;
530         StateAp *next = stateList.head;
531         StateAp *last = stateList.tail;
532         while ( state != last ) {
533                 /* Move forward and load up the next. */
534                 state = next;
535                 next = state->next;
536
537                 /* Throw to the end? */
538                 if ( state->isFinState() ) {
539                         stateList.detach( state );
540                         stateList.append( state );
541                 }
542         }
543 }
544
545 void FsmAp::setStateNumbers( int base )
546 {
547         for ( StateList::Iter state = stateList; state.lte(); state++ )
548                 state->alg.stateNum = base++;
549 }
550
551
552 bool FsmAp::checkErrTrans( StateAp *state, TransAp *trans )
553 {
554         /* Might go directly to error state. */
555         if ( trans->toState == 0 )
556                 return true;
557
558         if ( trans->prev == 0 ) {
559                 /* If this is the first transition. */
560                 if ( keyOps->minKey < trans->lowKey )
561                         return true;
562         }
563         else {
564                 /* Not the first transition. Compare against the prev. */
565                 TransAp *prev = trans->prev;
566                 Key nextKey = prev->highKey;
567                 nextKey.increment();
568                 if ( nextKey < trans->lowKey )
569                         return true; 
570         }
571         return false;
572 }
573
574 bool FsmAp::checkErrTransFinish( StateAp *state )
575 {
576         /* Check if there are any ranges already. */
577         if ( state->outList.length() == 0 )
578                 return true;
579         else {
580                 /* Get the last and check for a gap on the end. */
581                 TransAp *last = state->outList.tail;
582                 if ( last->highKey < keyOps->maxKey )
583                         return true;
584         }
585         return 0;
586 }
587
588 bool FsmAp::hasErrorTrans()
589 {
590         bool result;
591         for ( StateList::Iter st = stateList; st.lte(); st++ ) {
592                 for ( TransList::Iter tr = st->outList; tr.lte(); tr++ ) {
593                         result = checkErrTrans( st, tr );
594                         if ( result )
595                                 return true;
596                 }
597                 result = checkErrTransFinish( st );
598                 if ( result )
599                         return true;
600         }
601         return false;
602 }