2 * Copyright 2001-2006 Adrian Thurston <thurston@complang.org>
5 /* This file is part of Ragel.
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.
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.
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
38 #include "mergesort.h"
41 #include "sbsttable.h"
43 #define TRANS_ERR_TRANS 0
44 #define STATE_ERR_STATE 0
45 #define FUNC_NO_FUNC 0
53 /* Location in an input file. */
67 Text, Goto, Call, Next, GotoExpr, CallExpr, NextExpr, Ret,
68 PChar, Char, Hold, Exec, Curs, Targs, Entry,
69 LmSwitch, LmSetActId, LmSetTokEnd, LmGetTokEnd, LmInitTokStart,
70 LmInitAct, LmSetTokStart, SubAction, Break
73 GenInlineItem( const GenInputLoc &loc, Type type ) :
74 loc(loc), data(0), targId(0), targState(0),
75 lmId(0), children(0), offset(0),
81 RedStateAp *targState;
83 GenInlineList *children;
87 GenInlineItem *prev, *next;
90 /* Normally this would be atypedef, but that would entail including DList from
91 * ptreetypes, which should be just typedef forwards. */
92 struct GenInlineList : public DList<GenInlineItem> { };
94 /* Element in list of actions. Contains the string for the code to exectute. */
97 public DListEl<GenAction>
111 /* Data collected during parse. */
114 GenInlineList *inlineList;
119 /* Number of references in the final machine. */
121 { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
124 int numFromStateRefs;
133 /* Transistion GenAction Element. */
134 typedef SBstMapEl< int, GenAction* > GenActionTableEl;
136 /* Transition GenAction Table. */
137 struct GenActionTable
138 : public SBstMap< int, GenAction*, CmpOrd<int> >
140 void setAction( int ordering, GenAction *action );
141 void setActions( int *orderings, GenAction **actions, int nActs );
142 void setActions( const GenActionTable &other );
145 /* Compare of a whole action table element (key & value). */
146 struct CmpGenActionTableEl
148 static int compare( const GenActionTableEl &action1,
149 const GenActionTableEl &action2 )
151 if ( action1.key < action2.key )
153 else if ( action1.key > action2.key )
155 else if ( action1.value < action2.value )
157 else if ( action1.value > action2.value )
163 /* Compare for GenActionTable. */
164 typedef CmpSTable< GenActionTableEl, CmpGenActionTableEl > CmpGenActionTable;
167 typedef BstSet<RedStateAp*> RedStateSet;
168 typedef BstSet<int> IntSet;
170 /* Reduced action. */
173 public AvlTreeEl<RedAction>
184 bAnyCurStateRef(false),
188 const GenActionTable &getKey()
196 /* Number of references in the final machine. */
198 { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
201 int numFromStateRefs;
204 bool anyNextStmt() { return bAnyNextStmt; }
205 bool anyCurStateRef() { return bAnyCurStateRef; }
206 bool anyBreakStmt() { return bAnyBreakStmt; }
209 bool bAnyCurStateRef;
212 typedef AvlTree<RedAction, GenActionTable, CmpGenActionTable> GenActionTableMap;
214 /* Reduced transition. */
217 public AvlTreeEl<RedTransAp>
219 RedTransAp( RedStateAp *targ, RedAction *action, int id )
220 : targ(targ), action(action), id(id), pos(-1), labelNeeded(true) { }
226 bool partitionBoundary;
230 /* Compare of transitions for the final reduction of transitions. Comparison
231 * is on target and the pointer to the shared action table. It is assumed that
232 * when this is used the action tables have been reduced. */
235 static int compare( const RedTransAp &t1, const RedTransAp &t2 )
237 if ( t1.targ < t2.targ )
239 else if ( t1.targ > t2.targ )
241 else if ( t1.action < t2.action )
243 else if ( t1.action > t2.action )
250 typedef AvlBasic<RedTransAp, CmpRedTransAp> TransApSet;
252 /* Element in out range. */
256 RedTransEl( Key lowKey, Key highKey, RedTransAp *value )
257 : lowKey(lowKey), highKey(highKey), value(value) { }
263 typedef Vector<RedTransEl> RedTransList;
264 typedef Vector<RedStateAp*> RedStateVect;
266 typedef BstMapEl<RedStateAp*, unsigned long long> RedSpanMapEl;
267 typedef BstMap<RedStateAp*, unsigned long long> RedSpanMap;
269 /* Compare used by span map sort. Reverse sorts by the span. */
270 struct CmpRedSpanMapEl
272 static int compare( const RedSpanMapEl &smel1, const RedSpanMapEl &smel2 )
274 if ( smel1.value > smel2.value )
276 else if ( smel1.value < smel2.value )
283 /* Sorting state-span map entries by span. */
284 typedef MergeSort<RedSpanMapEl, CmpRedSpanMapEl> RedSpanMapSort;
286 /* Set of entry ids that go into this state. */
287 typedef Vector<int> EntryIdVect;
288 typedef Vector<char*> EntryNameVect;
290 typedef Vector< GenAction* > GenCondSet;
295 : key(0), baseKey(0) {}
301 Condition *next, *prev;
303 typedef DList<Condition> ConditionList;
311 GenCondSpace *next, *prev;
313 typedef DList<GenCondSpace> CondSpaceList;
320 GenCondSpace *condSpace;
322 GenStateCond *prev, *next;
324 typedef DList<GenStateCond> GenStateCondList;
325 typedef Vector<GenStateCond*> StateCondVect;
344 bAnyRegCurStateRef(false),
345 partitionBoundary(false),
350 /* Transitions out. */
351 RedTransList outSingle;
352 RedTransList outRange;
353 RedTransAp *defTrans;
355 /* For flat conditions. */
356 Key condLowKey, condHighKey;
357 GenCondSpace **condList;
361 RedTransAp **transList;
363 /* The list of states that transitions from this state go to. */
364 RedStateVect targStates;
370 RedAction *toStateAction;
371 RedAction *fromStateAction;
372 RedAction *eofAction;
373 RedTransAp *eofTrans;
375 GenStateCondList stateCondList;
376 StateCondVect stateCondVect;
378 /* Pointers for the list of states. */
379 RedStateAp *prev, *next;
381 bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
382 bool bAnyRegCurStateRef;
385 bool partitionBoundary;
387 RedTransAp **inTrans;
391 /* List of states. */
392 typedef DList<RedStateAp> RedStateList;
394 /* Set of reduced transitons. Comparison is by pointer. */
395 typedef BstSet< RedTransAp*, CmpOrd<RedTransAp*> > RedTransSet;
397 /* Next version of the fsm machine. */
402 bool forcedErrorState;
407 /* Next State Id doubles as the total number of state ids. */
411 GenActionTableMap actionMap;
412 RedStateList stateList;
413 RedStateSet entryPoints;
414 RedStateAp *startState;
415 RedStateAp *errState;
416 RedTransAp *errTrans;
417 RedTransAp *errActionTrans;
418 RedStateAp *firstFinState;
422 bool bAnyToStateActions;
423 bool bAnyFromStateActions;
427 bool bAnyActionGotos;
428 bool bAnyActionCalls;
430 bool bAnyRegActionRets;
431 bool bAnyRegActionByValControl;
432 bool bAnyRegNextStmt;
433 bool bAnyRegCurStateRef;
446 unsigned long long maxSpan;
447 unsigned long long maxCondSpan;
448 int maxFlatIndexOffset;
453 int maxCondIndexOffset;
457 bool anyToStateActions() { return bAnyToStateActions; }
458 bool anyFromStateActions() { return bAnyFromStateActions; }
459 bool anyRegActions() { return bAnyRegActions; }
460 bool anyEofActions() { return bAnyEofActions; }
461 bool anyEofTrans() { return bAnyEofTrans; }
462 bool anyActionGotos() { return bAnyActionGotos; }
463 bool anyActionCalls() { return bAnyActionCalls; }
464 bool anyActionRets() { return bAnyActionRets; }
465 bool anyRegActionRets() { return bAnyRegActionRets; }
466 bool anyRegActionByValControl() { return bAnyRegActionByValControl; }
467 bool anyRegNextStmt() { return bAnyRegNextStmt; }
468 bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
469 bool anyRegBreak() { return bAnyRegBreak; }
470 bool anyConditions() { return bAnyConditions; }
473 /* Is is it possible to extend a range by bumping ranges that span only
474 * one character to the singles array. */
475 bool canExtend( const RedTransList &list, int pos );
477 /* Pick single transitions from the ranges. */
478 void moveTransToSingle( RedStateAp *state );
483 /* Move a selected transition from ranges to default. */
484 void moveToDefault( RedTransAp *defTrans, RedStateAp *state );
486 /* Pick a default transition by largest span. */
487 RedTransAp *chooseDefaultSpan( RedStateAp *state );
488 void chooseDefaultSpan();
490 /* Pick a default transition by most number of ranges. */
491 RedTransAp *chooseDefaultNumRanges( RedStateAp *state );
492 void chooseDefaultNumRanges();
494 /* Pick a default transition tailored towards goto driven machine. */
495 RedTransAp *chooseDefaultGoto( RedStateAp *state );
496 void chooseDefaultGoto();
498 /* Ordering states by transition connections. */
499 void optimizeStateOrdering( RedStateAp *state );
500 void optimizeStateOrdering();
502 /* Ordering states by transition connections. */
503 void depthFirstOrdering( RedStateAp *state );
504 void depthFirstOrdering();
507 void sequentialStateIds();
508 void sortStateIdsByFinal();
510 /* Arrange states in by final id. This is a stable sort. */
511 void sortStatesByFinal();
513 /* Sorting states by id. */
514 void sortByStateId();
516 /* Locating the first final state. This is the final state with the lowest
518 void findFirstFinState();
520 void assignActionLocs();
522 RedTransAp *getErrorTrans();
523 RedStateAp *getErrorState();
525 /* Is every char in the alphabet covered? */
526 bool alphabetCovered( RedTransList &outRange );
528 RedTransAp *allocateTrans( RedStateAp *targState, RedAction *actionTable );
530 void partitionFsm( int nParts );
536 #endif /* _REDFSM_H */