Added the eofTarget to StateAp. This will be used only to track the transition
[external/ragel.git] / ragel / fsmstate.cpp
1 /*
2  *  Copyright 2002 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 #include <iostream>
27 using namespace std;
28
29 /* Construct a mark index for a specified number of states. Must new up
30  * an array that is states^2 in size. */
31 MarkIndex::MarkIndex( int states ) : numStates(states)
32 {
33         /* Total pairs is states^2. Actually only use half of these, but we allocate
34          * them all to make indexing into the array easier. */
35         int total = states * states;
36
37         /* New up chars so that individual DListEl constructors are
38          * not called. Zero out the mem manually. */
39         array = new bool[total];
40         memset( array, 0, sizeof(bool) * total );
41 }
42
43 /* Free the array used to store state pairs. */
44 MarkIndex::~MarkIndex()
45 {
46         delete[] array;
47 }
48
49 /* Mark a pair of states. States are specified by their number. The
50  * marked states are moved from the unmarked list to the marked list. */
51 void MarkIndex::markPair(int state1, int state2)
52 {
53         int pos = ( state1 >= state2 ) ?
54                 ( state1 * numStates ) + state2 :
55                 ( state2 * numStates ) + state1;
56
57         array[pos] = true;
58 }
59
60 /* Returns true if the pair of states are marked. Returns false otherwise.
61  * Ordering of states given does not matter. */
62 bool MarkIndex::isPairMarked(int state1, int state2)
63 {
64         int pos = ( state1 >= state2 ) ?
65                 ( state1 * numStates ) + state2 :
66                 ( state2 * numStates ) + state1;
67
68         return array[pos];
69 }
70
71 /* Create a new fsm state. State has not out transitions or in transitions, not
72  * out out transition data and not number. */
73 StateAp::StateAp()
74 :
75         /* No out or in transitions. */
76         outList(),
77         inList(),
78
79         /* No EOF target. */
80         eofTarget(0),
81
82         /* No entry points, or epsilon trans. */
83         entryIds(),
84         epsilonTrans(),
85
86         /* Conditions. */
87         stateCondList(),
88
89         /* No transitions in from other states. */
90         foreignInTrans(0),
91
92         /* Only used during merging. Normally null. */
93         stateDictEl(0),
94         eptVect(0),
95
96         /* No state identification bits. */
97         stateBits(0),
98
99         /* No Priority data. */
100         outPriorTable(),
101
102         /* No Action data. */
103         toStateActionTable(),
104         fromStateActionTable(),
105         outActionTable(),
106         outCondSet(),
107         errActionTable(),
108         eofActionTable()
109 {
110 }
111
112 /* Copy everything except actual the transitions. That is left up to the
113  * FsmAp copy constructor. */
114 StateAp::StateAp(const StateAp &other)
115 :
116         /* All lists are cleared. They will be filled in when the
117          * individual transitions are duplicated and attached. */
118         outList(),
119         inList(),
120
121         /* Set this using the original state's eofTarget. It will get mapped back
122          * to the new machine in the Fsm copy constructor. */
123         eofTarget(other.eofTarget),
124
125         /* Duplicate the entry id set and epsilon transitions. These
126          * are sets of integers and as such need no fixing. */
127         entryIds(other.entryIds),
128         epsilonTrans(other.epsilonTrans),
129
130         /* Copy in the elements of the conditions. */
131         stateCondList( other.stateCondList ),
132
133         /* No transitions in from other states. */
134         foreignInTrans(0),
135
136         /* This is only used during merging. Normally null. */
137         stateDictEl(0),
138         eptVect(0),
139
140         /* Fsm state data. */
141         stateBits(other.stateBits),
142
143         /* Copy in priority data. */
144         outPriorTable(other.outPriorTable),
145
146         /* Copy in action data. */
147         toStateActionTable(other.toStateActionTable),
148         fromStateActionTable(other.fromStateActionTable),
149         outActionTable(other.outActionTable),
150         outCondSet(other.outCondSet),
151         errActionTable(other.errActionTable),
152         eofActionTable(other.eofActionTable)
153 {
154         /* Duplicate all the transitions. */
155         for ( TransList::Iter trans = other.outList; trans.lte(); trans++ ) {
156                 /* Dupicate and store the orginal target in the transition. This will
157                  * be corrected once all the states have been created. */
158                 TransAp *newTrans = new TransAp(*trans);
159                 newTrans->toState = trans->toState;
160                 outList.append( newTrans );
161         }
162 }
163
164 /* If there is a state dict element, then delete it. Everything else is left
165  * up to the FsmGraph destructor. */
166 StateAp::~StateAp()
167 {
168         if ( stateDictEl != 0 )
169                 delete stateDictEl;
170 }
171
172 /* Compare two states using pointers to the states. With the approximate
173  * compare the idea is that if the compare finds them the same, they can
174  * immediately be merged. */
175 int ApproxCompare::compare( const StateAp *state1 , const StateAp *state2 )
176 {
177         int compareRes;
178
179         /* Test final state status. */
180         if ( (state1->stateBits & SB_ISFINAL) && !(state2->stateBits & SB_ISFINAL) )
181                 return -1;
182         else if ( !(state1->stateBits & SB_ISFINAL) && (state2->stateBits & SB_ISFINAL) )
183                 return 1;
184         
185         /* Test epsilon transition sets. */
186         compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans, 
187                         state2->epsilonTrans );
188         if ( compareRes != 0 )
189                 return compareRes;
190         
191         /* Compare the out transitions. */
192         compareRes = FsmAp::compareStateData( state1, state2 );
193         if ( compareRes != 0 )
194                 return compareRes;
195
196         /* Use a pair iterator to get the transition pairs. */
197         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
198         for ( ; !outPair.end(); outPair++ ) {
199                 switch ( outPair.userState ) {
200
201                 case RangeInS1:
202                         compareRes = FsmAp::compareFullPtr( outPair.s1Tel.trans, 0 );
203                         if ( compareRes != 0 )
204                                 return compareRes;
205                         break;
206
207                 case RangeInS2:
208                         compareRes = FsmAp::compareFullPtr( 0, outPair.s2Tel.trans );
209                         if ( compareRes != 0 )
210                                 return compareRes;
211                         break;
212
213                 case RangeOverlap:
214                         compareRes = FsmAp::compareFullPtr( 
215                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
216                         if ( compareRes != 0 )
217                                 return compareRes;
218                         break;
219
220                 case BreakS1:
221                 case BreakS2:
222                         break;
223                 }
224         }
225
226         /* Got through the entire state comparison, deem them equal. */
227         return 0;
228 }
229
230 /* Compare class for the sort that does the intial partition of compaction. */
231 int InitPartitionCompare::compare( const StateAp *state1 , const StateAp *state2 )
232 {
233         int compareRes;
234
235         /* Test final state status. */
236         if ( (state1->stateBits & SB_ISFINAL) && !(state2->stateBits & SB_ISFINAL) )
237                 return -1;
238         else if ( !(state1->stateBits & SB_ISFINAL) && (state2->stateBits & SB_ISFINAL) )
239                 return 1;
240
241         /* Test epsilon transition sets. */
242         compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans, 
243                         state2->epsilonTrans );
244         if ( compareRes != 0 )
245                 return compareRes;
246
247         /* Compare the out transitions. */
248         compareRes = FsmAp::compareStateData( state1, state2 );
249         if ( compareRes != 0 )
250                 return compareRes;
251
252         /* Use a pair iterator to test the condition pairs. */
253         PairIter<StateCond> condPair( state1->stateCondList.head, state2->stateCondList.head );
254         for ( ; !condPair.end(); condPair++ ) {
255                 switch ( condPair.userState ) {
256                 case RangeInS1:
257                         return 1;
258                 case RangeInS2:
259                         return -1;
260
261                 case RangeOverlap: {
262                         CondSpace *condSpace1 = condPair.s1Tel.trans->condSpace;
263                         CondSpace *condSpace2 = condPair.s2Tel.trans->condSpace;
264                         if ( condSpace1 < condSpace2 )
265                                 return -1;
266                         else if ( condSpace1 > condSpace2 )
267                                 return 1;
268                         break;
269                 }
270                 case BreakS1:
271                 case BreakS2:
272                         break;
273                 }
274         }
275
276         /* Use a pair iterator to test the transition pairs. */
277         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
278         for ( ; !outPair.end(); outPair++ ) {
279                 switch ( outPair.userState ) {
280
281                 case RangeInS1:
282                         compareRes = FsmAp::compareDataPtr( outPair.s1Tel.trans, 0 );
283                         if ( compareRes != 0 )
284                                 return compareRes;
285                         break;
286
287                 case RangeInS2:
288                         compareRes = FsmAp::compareDataPtr( 0, outPair.s2Tel.trans );
289                         if ( compareRes != 0 )
290                                 return compareRes;
291                         break;
292
293                 case RangeOverlap:
294                         compareRes = FsmAp::compareDataPtr( 
295                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
296                         if ( compareRes != 0 )
297                                 return compareRes;
298                         break;
299
300                 case BreakS1:
301                 case BreakS2:
302                         break;
303                 }
304         }
305
306         return 0;
307 }
308
309 /* Compare class for the sort that does the partitioning. */
310 int PartitionCompare::compare( const StateAp *state1, const StateAp *state2 )
311 {
312         int compareRes;
313
314         /* Use a pair iterator to get the transition pairs. */
315         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
316         for ( ; !outPair.end(); outPair++ ) {
317                 switch ( outPair.userState ) {
318
319                 case RangeInS1:
320                         compareRes = FsmAp::comparePartPtr( outPair.s1Tel.trans, 0 );
321                         if ( compareRes != 0 )
322                                 return compareRes;
323                         break;
324
325                 case RangeInS2:
326                         compareRes = FsmAp::comparePartPtr( 0, outPair.s2Tel.trans );
327                         if ( compareRes != 0 )
328                                 return compareRes;
329                         break;
330
331                 case RangeOverlap:
332                         compareRes = FsmAp::comparePartPtr( 
333                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
334                         if ( compareRes != 0 )
335                                 return compareRes;
336                         break;
337
338                 case BreakS1:
339                 case BreakS2:
340                         break;
341                 }
342         }
343
344         return 0;
345 }
346
347 /* Compare class for the sort that does the partitioning. */
348 bool MarkCompare::shouldMark( MarkIndex &markIndex, const StateAp *state1, 
349                         const StateAp *state2 )
350 {
351         /* Use a pair iterator to get the transition pairs. */
352         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
353         for ( ; !outPair.end(); outPair++ ) {
354                 switch ( outPair.userState ) {
355
356                 case RangeInS1:
357                         if ( FsmAp::shouldMarkPtr( markIndex, outPair.s1Tel.trans, 0 ) )
358                                 return true;
359                         break;
360
361                 case RangeInS2:
362                         if ( FsmAp::shouldMarkPtr( markIndex, 0, outPair.s2Tel.trans ) )
363                                 return true;
364                         break;
365
366                 case RangeOverlap:
367                         if ( FsmAp::shouldMarkPtr( markIndex,
368                                         outPair.s1Tel.trans, outPair.s2Tel.trans ) )
369                                 return true;
370                         break;
371
372                 case BreakS1:
373                 case BreakS2:
374                         break;
375                 }
376         }
377
378         return false;
379 }
380
381 /*
382  * Transition Comparison.
383  */
384
385 /* Compare target partitions. Either pointer may be null. */
386 int FsmAp::comparePartPtr( TransAp *trans1, TransAp *trans2 )
387 {
388         if ( trans1 != 0 ) {
389                 /* If trans1 is set then so should trans2. The initial partitioning
390                  * guarantees this for us. */
391                 if ( trans1->toState == 0 && trans2->toState != 0 )
392                         return -1;
393                 else if ( trans1->toState != 0 && trans2->toState == 0 )
394                         return 1;
395                 else if ( trans1->toState != 0 ) {
396                         /* Both of targets are set. */
397                         return CmpOrd< MinPartition* >::compare( 
398                                 trans1->toState->alg.partition, trans2->toState->alg.partition );
399                 }
400         }
401         return 0;
402 }
403
404
405 /* Compares two transition pointers according to priority and functions.
406  * Either pointer may be null. Does not consider to state or from state. */
407 int FsmAp::compareDataPtr( TransAp *trans1, TransAp *trans2 )
408 {
409         if ( trans1 == 0 && trans2 != 0 )
410                 return -1;
411         else if ( trans1 != 0 && trans2 == 0 )
412                 return 1;
413         else if ( trans1 != 0 ) {
414                 /* Both of the transition pointers are set. */
415                 int compareRes = compareTransData( trans1, trans2 );
416                 if ( compareRes != 0 )
417                         return compareRes;
418         }
419         return 0;
420 }
421
422 /* Compares two transitions according to target state, priority and functions.
423  * Does not consider from state. Either of the pointers may be null. */
424 int FsmAp::compareFullPtr( TransAp *trans1, TransAp *trans2 )
425 {
426         if ( (trans1 != 0) ^ (trans2 != 0) ) {
427                 /* Exactly one of the transitions is set. */
428                 if ( trans1 != 0 )
429                         return -1;
430                 else
431                         return 1;
432         }
433         else if ( trans1 != 0 ) {
434                 /* Both of the transition pointers are set. Test target state,
435                  * priority and funcs. */
436                 if ( trans1->toState < trans2->toState )
437                         return -1;
438                 else if ( trans1->toState > trans2->toState )
439                         return 1;
440                 else if ( trans1->toState != 0 ) {
441                         /* Test transition data. */
442                         int compareRes = compareTransData( trans1, trans2 );
443                         if ( compareRes != 0 )
444                                 return compareRes;
445                 }
446         }
447         return 0;
448 }
449
450
451 bool FsmAp::shouldMarkPtr( MarkIndex &markIndex, TransAp *trans1, 
452                                 TransAp *trans2 )
453 {
454         if ( (trans1 != 0) ^ (trans2 != 0) ) {
455                 /* Exactly one of the transitions is set. The initial mark round
456                  * should rule out this case. */
457                 assert( false );
458         }
459         else if ( trans1 != 0 ) {
460                 /* Both of the transitions are set. If the target pair is marked, then
461                  * the pair we are considering gets marked. */
462                 return markIndex.isPairMarked( trans1->toState->alg.stateNum, 
463                                 trans2->toState->alg.stateNum );
464         }
465
466         /* Neither of the transitiosn are set. */
467         return false;
468 }
469
470