ragel/parsedata.h

   1 /*
   2  *  Copyright 2001-2008 Adrian Thurston <thurston@complang.org>
   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 #ifndef _PARSEDATA_H
  23 #define _PARSEDATA_H
  24
  25 #include <iostream>
  26 #include <limits.h>
  27 #include <sstream>
  28 #include "avlmap.h"
  29 #include "bstmap.h"
  30 #include "vector.h"
  31 #include "dlist.h"
  32 #include "fsmgraph.h"
  33 #include "compare.h"
  34 #include "vector.h"
  35 #include "common.h"
  36 #include "parsetree.h"
  37
  38 /* Forwards. */
  39 using std::ostream;
  40
  41 struct VarDef;
  42 struct Join;
  43 struct Expression;
  44 struct Term;
  45 struct FactorWithAug;
  46 struct FactorWithLabel;
  47 struct FactorWithRep;
  48 struct FactorWithNeg;
  49 struct Factor;
  50 struct Literal;
  51 struct Range;
  52 struct RegExpr;
  53 struct ReItem;
  54 struct ReOrBlock;
  55 struct ReOrItem;
  56 struct LongestMatch;
  57 struct InputData;
  58 struct CodeGenData;
  59 typedef DList<LongestMatch> LmList;
  60
  61
  62 /* Graph dictionary. */
  63 struct GraphDictEl
  64 :
  65         public AvlTreeEl<GraphDictEl>,
  66         public DListEl<GraphDictEl>
  67 {
  68         GraphDictEl( const char *k )
  69                 : key(k), value(0), isInstance(false) { }
  70         GraphDictEl( const char *k, VarDef *value )
  71                 : key(k), value(value), isInstance(false) { }
  72
  73         const char *getKey() { return key; }
  74
  75         const char *key;
  76         VarDef *value;
  77         bool isInstance;
  78
  79         /* Location info of graph definition. Points to variable name of assignment. */
  80         InputLoc loc;
  81 };
  82
  83 typedef AvlTree<GraphDictEl, const char*, CmpStr> GraphDict;
  84 typedef DList<GraphDictEl> GraphList;
  85
  86 /* Priority name dictionary. */
  87 typedef AvlMapEl<char*, int> PriorDictEl;
  88 typedef AvlMap<char*, int, CmpStr> PriorDict;
  89
  90 /* Local error name dictionary. */
  91 typedef AvlMapEl<const char*, int> LocalErrDictEl;
  92 typedef AvlMap<const char*, int, CmpStr> LocalErrDict;
  93
  94 /* Tree of instantiated names. */
  95 typedef BstMapEl<const char*, NameInst*> NameMapEl;
  96 typedef BstMap<const char*, NameInst*, CmpStr> NameMap;
  97 typedef Vector<NameInst*> NameVect;
  98 typedef BstSet<NameInst*> NameSet;
  99
 100 /* Node in the tree of instantiated names. */
 101 struct NameInst
 102 {
 103         NameInst( const InputLoc &loc, NameInst *parent, const char *name, int id, bool isLabel ) :
 104                 loc(loc), parent(parent), name(name), id(id), isLabel(isLabel),
 105                 isLongestMatch(false), numRefs(0), numUses(0), start(0), final(0) {}
 106
 107         InputLoc loc;
 108
 109         /* Keep parent pointers in the name tree to retrieve
 110          * fully qulified names. */
 111         NameInst *parent;
 112
 113         const char *name;
 114         int id;
 115         bool isLabel;
 116         bool isLongestMatch;
 117
 118         int numRefs;
 119         int numUses;
 120
 121         /* Names underneath us, excludes anonymous names. */
 122         NameMap children;
 123
 124         /* All names underneath us in order of appearance. */
 125         NameVect childVect;
 126
 127         /* Join scopes need an implicit "final" target. */
 128         NameInst *start, *final;
 129
 130         /* During a fsm generation walk, lists the names that are referenced by
 131          * epsilon operations in the current scope. After the link is made by the
 132          * epsilon reference and the join operation is complete, the label can
 133          * have its refcount decremented. Once there are no more references the
 134          * entry point can be removed from the fsm returned. */
 135         NameVect referencedNames;
 136
 137         /* Pointers for the name search queue. */
 138         NameInst *prev, *next;
 139
 140         /* Check if this name inst or any name inst below is referenced. */
 141         bool anyRefsRec();
 142 };
 143
 144 typedef DList<NameInst> NameInstList;
 145
 146 /* Stack frame used in walking the name tree. */
 147 struct NameFrame
 148 {
 149         NameInst *prevNameInst;
 150         int prevNameChild;
 151         NameInst *prevLocalScope;
 152 };
 153
 154 /* Class to collect information about the machine during the
 155  * parse of input. */
 156 struct ParseData
 157 {
 158         /* Create a new parse data object. This is done at the beginning of every
 159          * fsm specification. */
 160         ParseData( const char *fileName, char *sectionName, const InputLoc &sectionLoc );
 161         ~ParseData();
 162
 163         /*
 164          * Setting up the graph dict.
 165          */
 166
 167         /* Initialize a graph dict with the basic fsms. */
 168         void initGraphDict();
 169         void createBuiltin( const char *name, BuiltinMachine builtin );
 170
 171         /* Make a name id in the current name instantiation scope if it is not
 172          * already there. */
 173         NameInst *addNameInst( const InputLoc &loc, const char *data, bool isLabel );
 174         void makeRootNames();
 175         void makeNameTree( GraphDictEl *gdNode );
 176         void makeExportsNameTree();
 177         void fillNameIndex( NameInst *from );
 178         void printNameTree();
 179
 180         /* Increments the usage count on entry names. Names that are no longer
 181          * needed will have their entry points unset. */
 182         void unsetObsoleteEntries( FsmAp *graph );
 183
 184         /* Resove name references in action code and epsilon transitions. */
 185         NameSet resolvePart( NameInst *refFrom, const char *data, bool recLabelsOnly );
 186         void resolveFrom( NameSet &result, NameInst *refFrom,
 187                         const NameRef &nameRef, int namePos );
 188         NameInst *resolveStateRef( const NameRef &nameRef, InputLoc &loc, Action *action );
 189         void resolveNameRefs( InlineList *inlineList, Action *action );
 190         void resolveActionNameRefs();
 191
 192         /* Set the alphabet type. If type types are not valid returns false. */
 193         bool setAlphType( const InputLoc &loc, char *s1, char *s2 );
 194         bool setAlphType( const InputLoc &loc, char *s1 );
 195
 196         /* Override one of the variables ragel uses. */
 197         bool setVariable( char *var, InlineList *inlineList );
 198
 199         /* Unique actions. */
 200         void removeDups( ActionTable &actionTable );
 201         void removeActionDups( FsmAp *graph );
 202
 203         /* Dumping the name instantiation tree. */
 204         void printNameInst( NameInst *nameInst, int level );
 205
 206         /* Make the graph from a graph dict node. Does minimization. */
 207         FsmAp *makeInstance( GraphDictEl *gdNode );
 208         FsmAp *makeSpecific( GraphDictEl *gdNode );
 209         FsmAp *makeAll();
 210
 211         /* Checking the contents of actions. */
 212         void checkAction( Action *action );
 213         void checkInlineList( Action *act, InlineList *inlineList );
 214
 215         void analyzeAction( Action *action, InlineList *inlineList );
 216         void analyzeGraph( FsmAp *graph );
 217         void makeExports();
 218
 219         void prepareMachineGen( GraphDictEl *graphDictEl );
 220         void prepareMachineGenTBWrapped( GraphDictEl *graphDictEl );
 221         void generateXML( ostream &out );
 222         void generateReduced( InputData &inputData );
 223         FsmAp *sectionGraph;
 224         bool generatingSectionSubset;
 225
 226         void initKeyOps();
 227
 228         /*
 229          * Data collected during the parse.
 230          */
 231
 232         /* Dictionary of graphs. Both instances and non-instances go here. */
 233         GraphDict graphDict;
 234
 235         /* The list of instances. */
 236         GraphList instanceList;
 237
 238         /* Dictionary of actions. Lets actions be defined and then referenced. */
 239         ActionDict actionDict;
 240
 241         /* Dictionary of named priorities. */
 242         PriorDict priorDict;
 243
 244         /* Dictionary of named local errors. */
 245         LocalErrDict localErrDict;
 246
 247         /* List of actions. Will be pasted into a switch statement. */
 248         ActionList actionList;
 249
 250         /* The id of the next priority name and label. */
 251         int nextPriorKey, nextLocalErrKey, nextNameId, nextCondId;
 252
 253         /* The default priority number key for a machine. This is active during
 254          * the parse of the rhs of a machine assignment. */
 255         int curDefPriorKey;
 256
 257         int curDefLocalErrKey;
 258
 259         /* Alphabet type. */
 260         HostType *userAlphType;
 261         bool alphTypeSet;
 262         InputLoc alphTypeLoc;
 263
 264         /* Element type and get key expression. */
 265         InlineList *getKeyExpr;
 266         InlineList *accessExpr;
 267
 268         /* Stack management */
 269         InlineList *prePushExpr;
 270         InlineList *postPopExpr;
 271
 272         /* Overriding variables. */
 273         InlineList *pExpr;
 274         InlineList *peExpr;
 275         InlineList *eofExpr;
 276         InlineList *csExpr;
 277         InlineList *topExpr;
 278         InlineList *stackExpr;
 279         InlineList *actExpr;
 280         InlineList *tokstartExpr;
 281         InlineList *tokendExpr;
 282         InlineList *dataExpr;
 283
 284         /* The alphabet range. */
 285         char *lowerNum, *upperNum;
 286         Key lowKey, highKey;
 287         InputLoc rangeLowLoc, rangeHighLoc;
 288
 289         /* The name of the file the fsm is from, and the spec name. */
 290         const char *fileName;
 291         char *sectionName;
 292         InputLoc sectionLoc;
 293
 294         /* Counting the action and priority ordering. */
 295         int curActionOrd;
 296         int curPriorOrd;
 297
 298         /* Root of the name tree. One root is for the instantiated machines. The
 299          * other root is for exported definitions. */
 300         NameInst *rootName;
 301         NameInst *exportsRootName;
 302
 303         /* Name tree walking. */
 304         NameInst *curNameInst;
 305         int curNameChild;
 306
 307         /* The place where resolved epsilon transitions go. These cannot go into
 308          * the parse tree because a single epsilon op can resolve more than once
 309          * to different nameInsts if the machine it's in is used more than once. */
 310         NameVect epsilonResolvedLinks;
 311         int nextEpsilonResolvedLink;
 312
 313         /* Root of the name tree used for doing local name searches. */
 314         NameInst *localNameScope;
 315
 316         void setLmInRetLoc( InlineList *inlineList );
 317         void initLongestMatchData();
 318         void setLongestMatchData( FsmAp *graph );
 319         void initNameWalk();
 320         void initExportsNameWalk();
 321         NameInst *nextNameScope() { return curNameInst->childVect[curNameChild]; }
 322         NameFrame enterNameScope( bool isLocal, int numScopes );
 323         void popNameScope( const NameFrame &frame );
 324         void resetNameScope( const NameFrame &frame );
 325
 326         /* Make name ids to name inst pointers. */
 327         NameInst **nameIndex;
 328
 329         /* Counter for assigning ids to longest match items. */
 330         int nextLongestMatchId;
 331         bool lmRequiresErrorState;
 332
 333         /* List of all longest match parse tree items. */
 334         LmList lmList;
 335
 336         Action *newAction( const char *name, InlineList *inlineList );
 337
 338         Action *initTokStart;
 339         int initTokStartOrd;
 340
 341         Action *setTokStart;
 342         int setTokStartOrd;
 343
 344         Action *initActId;
 345         int initActIdOrd;
 346
 347         Action *setTokEnd;
 348         int setTokEndOrd;
 349
 350         void beginProcessing()
 351         {
 352                 ::condData = &thisCondData;
 353                 ::keyOps = &thisKeyOps;
 354         }
 355
 356         CondData thisCondData;
 357         KeyOps thisKeyOps;
 358
 359         ExportList exportList;
 360
 361         CodeGenData *cgd;
 362 };
 363
 364 void afterOpMinimize( FsmAp *fsm, bool lastInSeq = true );
 365 Key makeFsmKeyHex( char *str, const InputLoc &loc, ParseData *pd );
 366 Key makeFsmKeyDec( char *str, const InputLoc &loc, ParseData *pd );
 367 Key makeFsmKeyNum( char *str, const InputLoc &loc, ParseData *pd );
 368 Key makeFsmKeyChar( char c, ParseData *pd );
 369 void makeFsmKeyArray( Key *result, char *data, int len, ParseData *pd );
 370 void makeFsmUniqueKeyArray( KeySet &result, char *data, int len,
 371                 bool caseInsensitive, ParseData *pd );
 372 FsmAp *makeBuiltin( BuiltinMachine builtin, ParseData *pd );
 373 FsmAp *dotFsm( ParseData *pd );
 374 FsmAp *dotStarFsm( ParseData *pd );
 375
 376 void errorStateLabels( const NameSet &locations );
 377
 378 struct InputItem
 379 {
 380         enum Type {
 381                 HostData,
 382                 Write,
 383         };
 384
 385         Type type;
 386         std::ostringstream data;
 387         std::string name;
 388         ParseData *pd;
 389         Vector<char *> writeArgs;
 390
 391         InputLoc loc;
 392
 393         InputItem *prev, *next;
 394 };
 395
 396 /*
 397  * Global data.
 398  */
 399
 400 struct Parser;
 401
 402 typedef AvlMap<char*, Parser *, CmpStr> ParserDict;
 403 typedef AvlMapEl<char*, Parser *> ParserDictEl;
 404
 405 typedef DList<InputItem> InputItemList;
 406
 407 extern ParserDict parserDict;
 408 extern InputItemList inputItems;
 409
 410 #endif