diff options
Diffstat (limited to 'src/libfsm/gendata.h')
| -rw-r--r-- | src/libfsm/gendata.h | 477 |
1 files changed, 477 insertions, 0 deletions
diff --git a/src/libfsm/gendata.h b/src/libfsm/gendata.h new file mode 100644 index 00000000..f34f2629 --- /dev/null +++ b/src/libfsm/gendata.h @@ -0,0 +1,477 @@ +/* + * Copyright 2005-2018 Adrian Thurston <thurston@colm.net> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#ifndef _GENDATA_H +#define _GENDATA_H + +#include <iostream> +#include <string> +#include <vector> +#include "config.h" +#include "redfsm.h" +#include "common.h" +#include "fsmgraph.h" + +/* Forwards. */ +struct TransAp; +struct FsmAp; +struct PdBase; +struct InputData; +struct FsmGbl; +struct GenInlineList; +struct InlineItem; + +struct RedActionTable +: + public AvlTreeEl<RedActionTable> +{ + RedActionTable( const ActionTable &key ) + : + key(key), + id(0) + { } + + const ActionTable &getKey() + { return key; } + + ActionTable key; + int id; +}; + +typedef AvlTree<RedActionTable, ActionTable, CmpActionTable> ActionTableMap; + +struct NextRedTrans +{ + Key lowKey, highKey; + TransAp *trans; + TransAp *next; + + void load() { + if ( trans != 0 ) { + next = trans->next; + lowKey = trans->lowKey; + highKey = trans->highKey; + } + } + + NextRedTrans( TransAp *t ) { + trans = t; + load(); + } + + void increment() { + trans = next; + load(); + } +}; + +struct RedBase +{ + RedBase( FsmGbl *id, FsmCtx *fsmCtx, FsmAp *fsm, std::string fsmName, int machineId ) + : + id(id), + fsmCtx(fsmCtx), + fsm(fsm), + fsmName(fsmName), + machineId(machineId), + keyOps(fsm->ctx->keyOps), + nextActionTableId(0) + { + } + + FsmGbl *id; + FsmCtx *fsmCtx; + FsmAp *fsm; + std::string fsmName; + int machineId; + + KeyOps *keyOps; + + ActionTableMap actionTableMap; + int nextActionTableId; +}; + +struct NameInst; +typedef DList<GenAction> GenActionList; + +typedef unsigned long ulong; + +void openHostBlock( char opener, InputData *id, std::ostream &out, const char *fileName, int line ); + +string itoa( int i ); + +struct Reducer + : public RedBase +{ + Reducer( FsmGbl *id, FsmCtx *fsmCtx, FsmAp *fsm, std::string fsmName, int machineId ) + : + RedBase( id, fsmCtx, fsm, fsmName, machineId ), + redFsm(0), + allActions(0), + allActionTables(0), + allConditions(0), + allCondSpaces(0), + allStates(0), + nameIndex(0), + startState(-1), + errState(-1), + getKeyExpr(0), + accessExpr(0), + prePushExpr(0), + postPopExpr(0), + nfaPrePushExpr(0), + nfaPostPopExpr(0), + pExpr(0), + peExpr(0), + eofExpr(0), + csExpr(0), + topExpr(0), + stackExpr(0), + actExpr(0), + tokstartExpr(0), + tokendExpr(0), + dataExpr(0), + hasLongestMatch(false) + { + } + + ~Reducer() + { + if ( redFsm != 0 ) + delete redFsm; + + delete[] allActions; + delete[] allActionTables; + delete[] allConditions; + delete[] allCondSpaces; + + actionTableMap.empty(); + + if ( getKeyExpr != 0 ) + delete getKeyExpr; + if ( accessExpr != 0 ) + delete accessExpr; + if ( prePushExpr != 0 ) + delete prePushExpr; + if ( postPopExpr != 0 ) + delete postPopExpr; + if ( nfaPrePushExpr != 0 ) + delete nfaPrePushExpr; + if ( nfaPostPopExpr != 0 ) + delete nfaPostPopExpr; + if ( pExpr != 0 ) + delete pExpr; + if ( peExpr != 0 ) + delete peExpr; + if ( eofExpr != 0 ) + delete eofExpr; + if ( csExpr != 0 ) + delete csExpr; + if ( topExpr != 0 ) + delete topExpr; + if ( stackExpr != 0 ) + delete stackExpr; + if ( actExpr != 0 ) + delete actExpr; + if ( tokstartExpr != 0 ) + delete tokstartExpr; + if ( tokendExpr != 0 ) + delete tokendExpr; + if ( dataExpr != 0 ) + delete dataExpr; + } + +protected: + /* Collected during parsing. */ + int curAction; + int curActionTable; + int curState; + + void makeKey( GenInlineList *outList, Key key ); + void makeText( GenInlineList *outList, InlineItem *item ); + void makeLmOnLast( GenInlineList *outList, InlineItem *item ); + void makeLmOnNext( GenInlineList *outList, InlineItem *item ); + void makeLmOnLagBehind( GenInlineList *outList, InlineItem *item ); + void makeLmSwitch( GenInlineList *outList, InlineItem *item ); + void makeLmNfaOnLast( GenInlineList *outList, InlineItem *item ); + void makeLmNfaOnNext( GenInlineList *outList, InlineItem *item ); + void makeLmNfaOnEof( GenInlineList *outList, InlineItem *item ); + void makeActionExec( GenInlineList *outList, InlineItem *item ); + void makeSetTokend( GenInlineList *outList, long offset ); + void makeSetAct( GenInlineList *outList, long lmId ); + void makeSubList( GenInlineList *outList, InlineList *inlineList, + GenInlineItem::Type type ); + void makeTargetItem( GenInlineList *outList, NameInst *nameTarg, + GenInlineItem::Type type ); + void makeExecGetTokend( GenInlineList *outList ); + void makeActionList(); + void makeAction( Action *action ); + void makeActionTableList(); + void makeConditions(); + void makeEntryPoints(); + bool makeNameInst( std::string &out, NameInst *nameInst ); + void makeStateList(); + + void makeStateActions( StateAp *state ); + void makeEofTrans( StateAp *state ); + void makeTransList( StateAp *state ); + void makeTrans( Key lowKey, Key highKey, TransAp *trans ); + void newTrans( RedStateAp *state, Key lowKey, Key highKey, RedTransAp *trans ); + + void makeSubList( GenInlineList *outList, const InputLoc &loc, + InlineList *inlineList, GenInlineItem::Type type ); + + void createMachine(); + void initActionList( unsigned long length ); + void newAction( int anum, std::string name, + const InputLoc &loc, GenInlineList *inlineList ); + void initActionTableList( unsigned long length ); + void initStateList( unsigned long length ); + void setStartState( unsigned long startState ); + void setErrorState( unsigned long errState ); + void addEntryPoint( char *name, unsigned long entryState ); + void setId( int snum, int id ); + void setFinal( int snum ); + void initTransList( int snum, unsigned long length ); + + void newTrans( int snum, int tnum, Key lowKey, Key highKey, + GenCondSpace *gcs, RedTransAp *trans ); + + void finishTransList( int snum ); + void setStateActions( int snum, long toStateAction, + long fromStateAction, long eofAction ); + void setEofTrans( int snum, long targ, long eofAction ); + void setEofTrans( int snum, GenCondSpace *condSpace, + RedCondEl *outConds, int numConds, RedCondAp *errCond ); + void setForcedErrorState() + { redFsm->forcedErrorState = true; } + + void condSpaceItem( int cnum, long condActionId ); + void newCondSpace( int cnum, int condSpaceId ); + + void initStateCondList( int snum, ulong length ); + void addStateCond( int snum, Key lowKey, Key highKey, long condNum ); + + + void resolveTargetStates( GenInlineList *inlineList ); + void resolveTargetStates(); + + + /* Gather various info on the machine. */ + void analyzeActionList( RedAction *redAct, GenInlineList *inlineList ); + void analyzeAction( GenAction *act, GenInlineList *inlineList ); + void actionActionRefs( RedAction *action ); + void transListActionRefs( RedTransList &list ); + void transActionRefs( RedTransAp *trans ); + void findFinalActionRefs(); + + void setValueLimits(); + void assignActionIds(); + + + void appendTrans( TransListVect &outList, Key lowKey, Key highKey, TransAp *trans ); + void reduceActionTables(); + +public: + + Key findMaxKey(); + void makeMachine(); + void makeExports(); + void makeGenInlineList( GenInlineList *outList, InlineList *inList ); + bool setAlphType( const HostLang *hostLang, const char *data ); + void analyzeMachine(); + void make( const HostLang *hostLang, const HostType *alphType ); + + /* + * Collecting the machine. + */ + + RedFsmAp *redFsm; + GenAction *allActions; + RedAction *allActionTables; + Condition *allConditions; + GenCondSpace *allCondSpaces; + RedStateAp *allStates; + NameInst **nameIndex; + int startState; + int errState; + GenActionList actionList; + CondSpaceList condSpaceList; + + GenInlineList *getKeyExpr; + GenInlineList *accessExpr; + GenInlineExpr *prePushExpr; + GenInlineExpr *postPopExpr; + + GenInlineExpr *nfaPrePushExpr; + GenInlineExpr *nfaPostPopExpr; + + /* Overriding variables. */ + GenInlineList *pExpr; + GenInlineList *peExpr; + GenInlineList *eofExpr; + GenInlineList *csExpr; + GenInlineList *topExpr; + GenInlineList *stackExpr; + GenInlineList *actExpr; + GenInlineList *tokstartExpr; + GenInlineList *tokendExpr; + GenInlineList *dataExpr; + + EntryIdVect entryPointIds; + EntryNameVect entryPointNames; + bool hasLongestMatch; + ExportList exportList; + Action *curInlineAction; +}; + +struct CodeGenArgs +{ + CodeGenArgs( FsmGbl *id, Reducer *red, HostType *alphType, + int machineId, std::string sourceFileName, + std::string fsmName, std::ostream &out, + CodeStyle codeStyle ) + : + id(id), + red(red), + alphType(alphType), + machineId(machineId), + sourceFileName(sourceFileName), + fsmName(fsmName), + out(out), + codeStyle(codeStyle), + lineDirectives(true), + forceVar(false), + loopLabels(false) + {} + + FsmGbl *id; + Reducer *red; + HostType *alphType; + int machineId; + std::string sourceFileName; + std::string fsmName; + std::ostream &out; + CodeStyle codeStyle; + bool lineDirectives; + GenLineDirectiveT genLineDirective; + bool forceVar; + bool loopLabels; +}; + +struct CodeGenData +{ + CodeGenData( const CodeGenArgs &args ) + : + red(args.red), + redFsm(args.red->redFsm), + sourceFileName(args.sourceFileName), + fsmName(args.fsmName), + keyOps(red->keyOps), + alphType(args.alphType), + out(args.out), + noEnd(false), + noPrefix(false), + noFinal(false), + noError(false), + noCS(false), + lineDirectives(args.lineDirectives), + cleared(false), + referencesCollected(false), + genLineDirective(args.id->hostLang->genLineDirective) + { + } + + /* + * The interface to the code generator. + */ + virtual void genAnalysis() = 0; + + /* These are invoked by writeStatement and are normally what are used to + * implement the code generators. */ + virtual void writeData() {}; + virtual void writeInit() {}; + virtual void writeExec() {}; + virtual void writeExports() {}; + virtual void writeStart() {}; + virtual void writeFirstFinal() {}; + virtual void writeError() {}; + virtual void writeClear(); + + /* Show some stats after a write data. */ + virtual void statsSummary() = 0; + + /* This can also be overridden to modify the processing of write + * statements. */ + virtual void writeStatement( InputLoc &loc, int nargs, + std::vector<std::string> &args, bool generateDot, const HostLang *hostLang ); + + /********************/ + + virtual ~CodeGenData() + { + } + + void clear() + { + delete red->redFsm; + red->redFsm = 0; + } + + void collectReferences(); + +protected: + + Reducer *red; + RedFsmAp *redFsm; + std::string sourceFileName; + std::string fsmName; + KeyOps *keyOps; + HostType *alphType; + ostream &out; + + /* Write options. */ + bool noEnd; + bool noPrefix; + bool noFinal; + bool noError; + bool noCS; + + void write_option_error( InputLoc &loc, std::string arg ); + + bool lineDirectives; + bool cleared; + + bool referencesCollected; + + void genOutputLineDirective( std::ostream &out ) const; + GenLineDirectiveT genLineDirective; +}; + +/* Selects and constructs the codegen based on the output options. */ +CodeGenData *makeCodeGen( const HostLang *hostLang, const CodeGenArgs &args ); +CodeGenData *asm_makeCodeGen( const HostLang *hostLang, const CodeGenArgs &args ); + +typedef AvlMap<char *, CodeGenData*, CmpStr> CodeGenMap; +typedef AvlMapEl<char *, CodeGenData*> CodeGenMapEl; + +#endif |