2 * Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
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, HoldTE, ExecTE, Curs, Targs, Entry,
69 LmSwitch, LmSetActId, LmSetTokEnd, LmGetTokEnd, LmInitTokStart,
70 LmInitAct, LmSetTokStart, SubAction, Break
73 InlineItem( const InputLoc &loc, Type type ) :
74 loc(loc), data(0), targId(0), targState(0),
75 lmId(0), children(0), offset(0),
76 handlesError(false), type(type) { }
81 RedStateAp *targState;
88 InlineItem *prev, *next;
91 /* Normally this would be atypedef, but that would entail including DList from
92 * ptreetypes, which should be just typedef forwards. */
93 struct InlineList : public DList<InlineItem> { };
95 /* Element in list of actions. Contains the string for the code to exectute. */
98 public DListEl<Action>
112 /* Data collected during parse. */
115 InlineList *inlineList;
120 /* Number of references in the final machine. */
122 { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
125 int numFromStateRefs;
134 /* Transistion Action Element. */
135 typedef SBstMapEl< int, Action* > ActionTableEl;
137 /* Transition Action Table. */
139 : public SBstMap< int, Action*, CmpOrd<int> >
141 void setAction( int ordering, Action *action );
142 void setActions( int *orderings, Action **actions, int nActs );
143 void setActions( const ActionTable &other );
146 /* Compare of a whole action table element (key & value). */
147 struct CmpActionTableEl
149 static int compare( const ActionTableEl &action1,
150 const ActionTableEl &action2 )
152 if ( action1.key < action2.key )
154 else if ( action1.key > action2.key )
156 else if ( action1.value < action2.value )
158 else if ( action1.value > action2.value )
164 /* Compare for ActionTable. */
165 typedef CmpSTable< ActionTableEl, CmpActionTableEl > CmpActionTable;
168 typedef BstSet<RedStateAp*> RedStateSet;
169 typedef BstSet<int> IntSet;
171 /* Reduced action. */
174 public AvlTreeEl<RedAction>
185 bAnyCurStateRef(false),
189 const ActionTable &getKey()
197 /* Number of references in the final machine. */
199 { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
202 int numFromStateRefs;
205 bool anyNextStmt() { return bAnyNextStmt; }
206 bool anyCurStateRef() { return bAnyCurStateRef; }
207 bool anyBreakStmt() { return bAnyBreakStmt; }
210 bool bAnyCurStateRef;
213 typedef AvlTree<RedAction, ActionTable, CmpActionTable> ActionTableMap;
215 /* Reduced transition. */
218 public AvlTreeEl<RedTransAp>
220 RedTransAp( RedStateAp *targ, RedAction *action, int id )
221 : targ(targ), action(action), id(id), 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< Action* > CondSet;
295 : key(0), baseKey(0) {}
301 Condition *next, *prev;
303 typedef DList<Condition> ConditionList;
311 CondSpace *next, *prev;
313 typedef DList<CondSpace> CondSpaceList;
320 CondSpace *condSpace;
322 StateCond *prev, *next;
324 typedef DList<StateCond> StateCondList;
325 typedef Vector<StateCond*> StateCondVect;
343 bAnyRegCurStateRef(false),
344 partitionBoundary(false),
349 /* Transitions out. */
350 RedTransList outSingle;
351 RedTransList outRange;
352 RedTransAp *defTrans;
354 /* For flat conditions. */
355 Key condLowKey, condHighKey;
356 CondSpace **condList;
360 RedTransAp **transList;
362 /* The list of states that transitions from this state go to. */
363 RedStateVect targStates;
369 RedAction *toStateAction;
370 RedAction *fromStateAction;
371 RedAction *eofAction;
373 StateCondList stateCondList;
374 StateCondVect stateCondVect;
376 /* Pointers for the list of states. */
377 RedStateAp *prev, *next;
379 bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
380 bool bAnyRegCurStateRef;
383 bool partitionBoundary;
385 RedTransAp **inTrans;
389 /* List of states. */
390 typedef DList<RedStateAp> RedStateList;
392 /* Set of reduced transitons. Comparison is by pointer. */
393 typedef BstSet< RedTransAp*, CmpOrd<RedTransAp*> > RedTransSet;
395 /* Next version of the fsm machine. */
400 bool forcedErrorState;
405 /* Next State Id doubles as the total number of state ids. */
409 ActionTableMap actionMap;
410 RedStateList stateList;
411 RedStateSet entryPoints;
412 RedStateAp *startState;
413 RedStateAp *errState;
414 RedTransAp *errTrans;
415 RedTransAp *errActionTrans;
416 RedStateAp *firstFinState;
420 bool bAnyToStateActions;
421 bool bAnyFromStateActions;
424 bool bAnyActionGotos;
425 bool bAnyActionCalls;
427 bool bAnyRegActionRets;
428 bool bAnyRegActionByValControl;
429 bool bAnyRegNextStmt;
430 bool bAnyRegCurStateRef;
432 bool bAnyLmSwitchError;
444 unsigned long long maxSpan;
445 unsigned long long maxCondSpan;
446 int maxFlatIndexOffset;
451 int maxCondIndexOffset;
455 bool anyToStateActions() { return bAnyToStateActions; }
456 bool anyFromStateActions() { return bAnyFromStateActions; }
457 bool anyRegActions() { return bAnyRegActions; }
458 bool anyEofActions() { return bAnyEofActions; }
459 bool anyActionGotos() { return bAnyActionGotos; }
460 bool anyActionCalls() { return bAnyActionCalls; }
461 bool anyActionRets() { return bAnyActionRets; }
462 bool anyRegActionRets() { return bAnyRegActionRets; }
463 bool anyRegActionByValControl() { return bAnyRegActionByValControl; }
464 bool anyRegNextStmt() { return bAnyRegNextStmt; }
465 bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
466 bool anyRegBreak() { return bAnyRegBreak; }
467 bool anyLmSwitchError() { return bAnyLmSwitchError; }
468 bool anyConditions() { return bAnyConditions; }
471 /* Is is it possible to extend a range by bumping ranges that span only
472 * one character to the singles array. */
473 bool canExtend( const RedTransList &list, int pos );
475 /* Pick single transitions from the ranges. */
476 void moveTransToSingle( RedStateAp *state );
481 /* Move a selected transition from ranges to default. */
482 void moveToDefault( RedTransAp *defTrans, RedStateAp *state );
484 /* Pick a default transition by largest span. */
485 RedTransAp *chooseDefaultSpan( RedStateAp *state );
486 void chooseDefaultSpan();
488 /* Pick a default transition by most number of ranges. */
489 RedTransAp *chooseDefaultNumRanges( RedStateAp *state );
490 void chooseDefaultNumRanges();
492 /* Pick a default transition tailored towards goto driven machine. */
493 RedTransAp *chooseDefaultGoto( RedStateAp *state );
494 void chooseDefaultGoto();
496 /* Ordering states by transition connections. */
497 void optimizeStateOrdering( RedStateAp *state );
498 void optimizeStateOrdering();
500 /* Ordering states by transition connections. */
501 void depthFirstOrdering( RedStateAp *state );
502 void depthFirstOrdering();
505 void sequentialStateIds();
506 void sortStateIdsByFinal();
508 /* Arrange states in by final id. This is a stable sort. */
509 void sortStatesByFinal();
511 /* Sorting states by id. */
512 void sortByStateId();
514 /* Locating the first final state. This is the final state with the lowest
516 void findFirstFinState();
518 void assignActionLocs();
520 RedTransAp *getErrorTrans();
521 RedStateAp *getErrorState();
523 /* Is every char in the alphabet covered? */
524 bool alphabetCovered( RedTransList &outRange );
526 RedTransAp *allocateTrans( RedStateAp *targState, RedAction *actionTable );
528 void partitionFsm( int nParts );
534 #endif /* _REDFSM_H */