ragel/parsedata.h

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