ragel/parsedata.cpp

   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 #include <iostream>
  23 #include <iomanip>
  24 #include <errno.h>
  25 #include <stdlib.h>
  26 #include <limits.h>
  27
  28 #include "ragel.h"
  29 #include "rlparse.h"
  30 #include "parsedata.h"
  31 #include "parsetree.h"
  32 #include "mergesort.h"
  33 #include "xmlcodegen.h"
  34 #include "version.h"
  35
  36 using namespace std;
  37
  38 char mainMachine[] = "main";
  39
  40 void Token::set( char *str, int len )
  41 {
  42         length = len;
  43         data = new char[len+1];
  44         memcpy( data, str, len );
  45         data[len] = 0;
  46 }
  47
  48 void Token::append( const Token &other )
  49 {
  50         int newLength = length + other.length;
  51         char *newString = new char[newLength+1];
  52         memcpy( newString, data, length );
  53         memcpy( newString + length, other.data, other.length );
  54         newString[newLength] = 0;
  55         data = newString;
  56         length = newLength;
  57 }
  58
  59 /* Perform minimization after an operation according
  60  * to the command line args. */
  61 void afterOpMinimize( FsmAp *fsm, bool lastInSeq )
  62 {
  63         /* Switch on the prefered minimization algorithm. */
  64         if ( minimizeOpt == MinimizeEveryOp || minimizeOpt == MinimizeMostOps && lastInSeq ) {
  65                 /* First clean up the graph. FsmAp operations may leave these
  66                  * lying around. There should be no dead end states. The subtract
  67                  * intersection operators are the only places where they may be
  68                  * created and those operators clean them up. */
  69                 fsm->removeUnreachableStates();
  70
  71                 switch ( minimizeLevel ) {
  72                         case MinimizeApprox:
  73                                 fsm->minimizeApproximate();
  74                                 break;
  75                         case MinimizePartition1:
  76                                 fsm->minimizePartition1();
  77                                 break;
  78                         case MinimizePartition2:
  79                                 fsm->minimizePartition2();
  80                                 break;
  81                         case MinimizeStable:
  82                                 fsm->minimizeStable();
  83                                 break;
  84                 }
  85         }
  86 }
  87
  88 /* Count the transitions in the fsm by walking the state list. */
  89 int countTransitions( FsmAp *fsm )
  90 {
  91         int numTrans = 0;
  92         StateAp *state = fsm->stateList.head;
  93         while ( state != 0 ) {
  94                 numTrans += state->outList.length();
  95                 state = state->next;
  96         }
  97         return numTrans;
  98 }
  99
 100 Key makeFsmKeyHex( char *str, const InputLoc &loc, ParseData *pd )
 101 {
 102         /* Reset errno so we can check for overflow or underflow. In the event of
 103          * an error, sets the return val to the upper or lower bound being tested
 104          * against. */
 105         errno = 0;
 106         unsigned int size = keyOps->alphType->size;
 107         bool unusedBits = size < sizeof(unsigned long);
 108
 109         unsigned long ul = strtoul( str, 0, 16 );
 110
 111         if ( errno == ERANGE || unusedBits && ul >> (size * 8) ) {
 112                 error(loc) << "literal " << str << " overflows the alphabet type" << endl;
 113                 ul = 1 << (size * 8);
 114         }
 115
 116         if ( unusedBits && keyOps->alphType->isSigned && ul >> (size * 8 - 1) )
 117                 ul |= (0xffffffff >> (size*8 ) ) << (size*8);
 118
 119         return Key( (long)ul );
 120 }
 121
 122 Key makeFsmKeyDec( char *str, const InputLoc &loc, ParseData *pd )
 123 {
 124         /* Convert the number to a decimal. First reset errno so we can check
 125          * for overflow or underflow. */
 126         errno = 0;
 127         long long minVal = keyOps->alphType->minVal;
 128         long long maxVal = keyOps->alphType->maxVal;
 129
 130         long long ll = strtoll( str, 0, 10 );
 131
 132         /* Check for underflow. */
 133         if ( errno == ERANGE && ll < 0 || ll < minVal) {
 134                 error(loc) << "literal " << str << " underflows the alphabet type" << endl;
 135                 ll = minVal;
 136         }
 137         /* Check for overflow. */
 138         else if ( errno == ERANGE && ll > 0 || ll > maxVal ) {
 139                 error(loc) << "literal " << str << " overflows the alphabet type" << endl;
 140                 ll = maxVal;
 141         }
 142
 143         if ( keyOps->alphType->isSigned )
 144                 return Key( (long)ll );
 145         else
 146                 return Key( (unsigned long)ll );
 147 }
 148
 149 /* Make an fsm key in int format (what the fsm graph uses) from an alphabet
 150  * number returned by the parser. Validates that the number doesn't overflow
 151  * the alphabet type. */
 152 Key makeFsmKeyNum( char *str, const InputLoc &loc, ParseData *pd )
 153 {
 154         /* Switch on hex/decimal format. */
 155         if ( str[0] == '0' && str[1] == 'x' )
 156                 return makeFsmKeyHex( str, loc, pd );
 157         else
 158                 return makeFsmKeyDec( str, loc, pd );
 159 }
 160
 161 /* Make an fsm int format (what the fsm graph uses) from a single character.
 162  * Performs proper conversion depending on signed/unsigned property of the
 163  * alphabet. */
 164 Key makeFsmKeyChar( char c, ParseData *pd )
 165 {
 166         if ( keyOps->isSigned ) {
 167                 /* Copy from a char type. */
 168                 return Key( c );
 169         }
 170         else {
 171                 /* Copy from an unsigned byte type. */
 172                 return Key( (unsigned char)c );
 173         }
 174 }
 175
 176 /* Make an fsm key array in int format (what the fsm graph uses) from a string
 177  * of characters. Performs proper conversion depending on signed/unsigned
 178  * property of the alphabet. */
 179 void makeFsmKeyArray( Key *result, char *data, int len, ParseData *pd )
 180 {
 181         if ( keyOps->isSigned ) {
 182                 /* Copy from a char star type. */
 183                 char *src = data;
 184                 for ( int i = 0; i < len; i++ )
 185                         result[i] = Key(src[i]);
 186         }
 187         else {
 188                 /* Copy from an unsigned byte ptr type. */
 189                 unsigned char *src = (unsigned char*) data;
 190                 for ( int i = 0; i < len; i++ )
 191                         result[i] = Key(src[i]);
 192         }
 193 }
 194
 195 /* Like makeFsmKeyArray except the result has only unique keys. They ordering
 196  * will be changed. */
 197 void makeFsmUniqueKeyArray( KeySet &result, char *data, int len,
 198                 bool caseInsensitive, ParseData *pd )
 199 {
 200         /* Use a transitions list for getting unique keys. */
 201         if ( keyOps->isSigned ) {
 202                 /* Copy from a char star type. */
 203                 char *src = data;
 204                 for ( int si = 0; si < len; si++ ) {
 205                         Key key( src[si] );
 206                         result.insert( key );
 207                         if ( caseInsensitive ) {
 208                                 if ( key.isLower() )
 209                                         result.insert( key.toUpper() );
 210                                 else if ( key.isUpper() )
 211                                         result.insert( key.toLower() );
 212                         }
 213                 }
 214         }
 215         else {
 216                 /* Copy from an unsigned byte ptr type. */
 217                 unsigned char *src = (unsigned char*) data;
 218                 for ( int si = 0; si < len; si++ ) {
 219                         Key key( src[si] );
 220                         result.insert( key );
 221                         if ( caseInsensitive ) {
 222                                 if ( key.isLower() )
 223                                         result.insert( key.toUpper() );
 224                                 else if ( key.isUpper() )
 225                                         result.insert( key.toLower() );
 226                         }
 227                 }
 228         }
 229 }
 230
 231 FsmAp *dotFsm( ParseData *pd )
 232 {
 233         FsmAp *retFsm = new FsmAp();
 234         retFsm->rangeFsm( keyOps->minKey, keyOps->maxKey );
 235         return retFsm;
 236 }
 237
 238 FsmAp *dotStarFsm( ParseData *pd )
 239 {
 240         FsmAp *retFsm = new FsmAp();
 241         retFsm->rangeStarFsm( keyOps->minKey, keyOps->maxKey );
 242         return retFsm;
 243 }
 244
 245 /* Make a builtin type. Depends on the signed nature of the alphabet type. */
 246 FsmAp *makeBuiltin( BuiltinMachine builtin, ParseData *pd )
 247 {
 248         /* FsmAp created to return. */
 249         FsmAp *retFsm = 0;
 250         bool isSigned = keyOps->isSigned;
 251
 252         switch ( builtin ) {
 253         case BT_Any: {
 254                 /* All characters. */
 255                 retFsm = dotFsm( pd );
 256                 break;
 257         }
 258         case BT_Ascii: {
 259                 /* Ascii characters 0 to 127. */
 260                 retFsm = new FsmAp();
 261                 retFsm->rangeFsm( 0, 127 );
 262                 break;
 263         }
 264         case BT_Extend: {
 265                 /* Ascii extended characters. This is the full byte range. Dependent
 266                  * on signed, vs no signed. If the alphabet is one byte then just use
 267                  * dot fsm. */
 268                 if ( isSigned ) {
 269                         retFsm = new FsmAp();
 270                         retFsm->rangeFsm( -128, 127 );
 271                 }
 272                 else {
 273                         retFsm = new FsmAp();
 274                         retFsm->rangeFsm( 0, 255 );
 275                 }
 276                 break;
 277         }
 278         case BT_Alpha: {
 279                 /* Alpha [A-Za-z]. */
 280                 FsmAp *upper = new FsmAp(), *lower = new FsmAp();
 281                 upper->rangeFsm( 'A', 'Z' );
 282                 lower->rangeFsm( 'a', 'z' );
 283                 upper->unionOp( lower );
 284                 upper->minimizePartition2();
 285                 retFsm = upper;
 286                 break;
 287         }
 288         case BT_Digit: {
 289                 /* Digits [0-9]. */
 290                 retFsm = new FsmAp();
 291                 retFsm->rangeFsm( '0', '9' );
 292                 break;
 293         }
 294         case BT_Alnum: {
 295                 /* Alpha numerics [0-9A-Za-z]. */
 296                 FsmAp *digit = new FsmAp(), *lower = new FsmAp();
 297                 FsmAp *upper = new FsmAp();
 298                 digit->rangeFsm( '0', '9' );
 299                 upper->rangeFsm( 'A', 'Z' );
 300                 lower->rangeFsm( 'a', 'z' );
 301                 digit->unionOp( upper );
 302                 digit->unionOp( lower );
 303                 digit->minimizePartition2();
 304                 retFsm = digit;
 305                 break;
 306         }
 307         case BT_Lower: {
 308                 /* Lower case characters. */
 309                 retFsm = new FsmAp();
 310                 retFsm->rangeFsm( 'a', 'z' );
 311                 break;
 312         }
 313         case BT_Upper: {
 314                 /* Upper case characters. */
 315                 retFsm = new FsmAp();
 316                 retFsm->rangeFsm( 'A', 'Z' );
 317                 break;
 318         }
 319         case BT_Cntrl: {
 320                 /* Control characters. */
 321                 FsmAp *cntrl = new FsmAp();
 322                 FsmAp *highChar = new FsmAp();
 323                 cntrl->rangeFsm( 0, 31 );
 324                 highChar->concatFsm( 127 );
 325                 cntrl->unionOp( highChar );
 326                 cntrl->minimizePartition2();
 327                 retFsm = cntrl;
 328                 break;
 329         }
 330         case BT_Graph: {
 331                 /* Graphical ascii characters [!-~]. */
 332                 retFsm = new FsmAp();
 333                 retFsm->rangeFsm( '!', '~' );
 334                 break;
 335         }
 336         case BT_Print: {
 337                 /* Printable characters. Same as graph except includes space. */
 338                 retFsm = new FsmAp();
 339                 retFsm->rangeFsm( ' ', '~' );
 340                 break;
 341         }
 342         case BT_Punct: {
 343                 /* Punctuation. */
 344                 FsmAp *range1 = new FsmAp();
 345                 FsmAp *range2 = new FsmAp();
 346                 FsmAp *range3 = new FsmAp();
 347                 FsmAp *range4 = new FsmAp();
 348                 range1->rangeFsm( '!', '/' );
 349                 range2->rangeFsm( ':', '@' );
 350                 range3->rangeFsm( '[', '`' );
 351                 range4->rangeFsm( '{', '~' );
 352                 range1->unionOp( range2 );
 353                 range1->unionOp( range3 );
 354                 range1->unionOp( range4 );
 355                 range1->minimizePartition2();
 356                 retFsm = range1;
 357                 break;
 358         }
 359         case BT_Space: {
 360                 /* Whitespace: [\t\v\f\n\r ]. */
 361                 FsmAp *cntrl = new FsmAp();
 362                 FsmAp *space = new FsmAp();
 363                 cntrl->rangeFsm( '\t', '\r' );
 364                 space->concatFsm( ' ' );
 365                 cntrl->unionOp( space );
 366                 cntrl->minimizePartition2();
 367                 retFsm = cntrl;
 368                 break;
 369         }
 370         case BT_Xdigit: {
 371                 /* Hex digits [0-9A-Fa-f]. */
 372                 FsmAp *digit = new FsmAp();
 373                 FsmAp *upper = new FsmAp();
 374                 FsmAp *lower = new FsmAp();
 375                 digit->rangeFsm( '0', '9' );
 376                 upper->rangeFsm( 'A', 'F' );
 377                 lower->rangeFsm( 'a', 'f' );
 378                 digit->unionOp( upper );
 379                 digit->unionOp( lower );
 380                 digit->minimizePartition2();
 381                 retFsm = digit;
 382                 break;
 383         }
 384         case BT_Lambda: {
 385                 retFsm = new FsmAp();
 386                 retFsm->lambdaFsm();
 387                 break;
 388         }
 389         case BT_Empty: {
 390                 retFsm = new FsmAp();
 391                 retFsm->emptyFsm();
 392                 break;
 393         }}
 394
 395         return retFsm;
 396 }
 397
 398 /* Check if this name inst or any name inst below is referenced. */
 399 bool NameInst::anyRefsRec()
 400 {
 401         if ( numRefs > 0 )
 402                 return true;
 403
 404         /* Recurse on children until true. */
 405         for ( NameVect::Iter ch = childVect; ch.lte(); ch++ ) {
 406                 if ( (*ch)->anyRefsRec() )
 407                         return true;
 408         }
 409
 410         return false;
 411 }
 412
 413 /*
 414  * ParseData
 415  */
 416
 417 /* Initialize the structure that will collect info during the parse of a
 418  * machine. */
 419 ParseData::ParseData( char *fileName, char *sectionName,
 420                 const InputLoc &sectionLoc )
 421 :
 422         sectionGraph(0),
 423         generatingSectionSubset(false),
 424         nextPriorKey(0),
 425         /* 0 is reserved for global error actions. */
 426         nextLocalErrKey(1),
 427         nextNameId(0),
 428         nextCondId(0),
 429         alphTypeSet(false),
 430         getKeyExpr(0),
 431         accessExpr(0),
 432         pExpr(0),
 433         peExpr(0),
 434         csExpr(0),
 435         topExpr(0),
 436         stackExpr(0),
 437         actExpr(0),
 438         tokstartExpr(0),
 439         tokendExpr(0),
 440         dataExpr(0),
 441         lowerNum(0),
 442         upperNum(0),
 443         fileName(fileName),
 444         sectionName(sectionName),
 445         sectionLoc(sectionLoc),
 446         curActionOrd(0),
 447         curPriorOrd(0),
 448         rootName(0),
 449         exportsRootName(0),
 450         nextEpsilonResolvedLink(0),
 451         nextLongestMatchId(1),
 452         lmRequiresErrorState(false)
 453 {
 454         /* Initialize the dictionary of graphs. This is our symbol table. The
 455          * initialization needs to be done on construction which happens at the
 456          * beginning of a machine spec so any assignment operators can reference
 457          * the builtins. */
 458         initGraphDict();
 459 }
 460
 461 /* Clean up the data collected during a parse. */
 462 ParseData::~ParseData()
 463 {
 464         /* Delete all the nodes in the action list. Will cause all the
 465          * string data that represents the actions to be deallocated. */
 466         actionList.empty();
 467 }
 468
 469 /* Make a name id in the current name instantiation scope if it is not
 470  * already there. */
 471 NameInst *ParseData::addNameInst( const InputLoc &loc, char *data, bool isLabel )
 472 {
 473         /* Create the name instantitaion object and insert it. */
 474         NameInst *newNameInst = new NameInst( loc, curNameInst, data, nextNameId++, isLabel );
 475         curNameInst->childVect.append( newNameInst );
 476         if ( data != 0 )
 477                 curNameInst->children.insertMulti( data, newNameInst );
 478         return newNameInst;
 479 }
 480
 481 void ParseData::initNameWalk()
 482 {
 483         curNameInst = rootName;
 484         curNameChild = 0;
 485 }
 486
 487 void ParseData::initExportsNameWalk()
 488 {
 489         curNameInst = exportsRootName;
 490         curNameChild = 0;
 491 }
 492
 493 /* Goes into the next child scope. The number of the child is already set up.
 494  * We need this for the syncronous name tree and parse tree walk to work
 495  * properly. It is reset on entry into a scope and advanced on poping of a
 496  * scope. A call to enterNameScope should be accompanied by a corresponding
 497  * popNameScope. */
 498 NameFrame ParseData::enterNameScope( bool isLocal, int numScopes )
 499 {
 500         /* Save off the current data. */
 501         NameFrame retFrame;
 502         retFrame.prevNameInst = curNameInst;
 503         retFrame.prevNameChild = curNameChild;
 504         retFrame.prevLocalScope = localNameScope;
 505
 506         /* Enter into the new name scope. */
 507         for ( int i = 0; i < numScopes; i++ ) {
 508                 curNameInst = curNameInst->childVect[curNameChild];
 509                 curNameChild = 0;
 510         }
 511
 512         if ( isLocal )
 513                 localNameScope = curNameInst;
 514
 515         return retFrame;
 516 }
 517
 518 /* Return from a child scope to a parent. The parent info must be specified as
 519  * an argument and is obtained from the corresponding call to enterNameScope.
 520  * */
 521 void ParseData::popNameScope( const NameFrame &frame )
 522 {
 523         /* Pop the name scope. */
 524         curNameInst = frame.prevNameInst;
 525         curNameChild = frame.prevNameChild+1;
 526         localNameScope = frame.prevLocalScope;
 527 }
 528
 529 void ParseData::resetNameScope( const NameFrame &frame )
 530 {
 531         /* Pop the name scope. */
 532         curNameInst = frame.prevNameInst;
 533         curNameChild = frame.prevNameChild;
 534         localNameScope = frame.prevLocalScope;
 535 }
 536
 537
 538 void ParseData::unsetObsoleteEntries( FsmAp *graph )
 539 {
 540         /* Loop the reference names and increment the usage. Names that are no
 541          * longer needed will be unset in graph. */
 542         for ( NameVect::Iter ref = curNameInst->referencedNames; ref.lte(); ref++ ) {
 543                 /* Get the name. */
 544                 NameInst *name = *ref;
 545                 name->numUses += 1;
 546
 547                 /* If the name is no longer needed unset its corresponding entry. */
 548                 if ( name->numUses == name->numRefs ) {
 549                         assert( graph->entryPoints.find( name->id ) != 0 );
 550                         graph->unsetEntry( name->id );
 551                         assert( graph->entryPoints.find( name->id ) == 0 );
 552                 }
 553         }
 554 }
 555
 556 NameSet ParseData::resolvePart( NameInst *refFrom, char *data, bool recLabelsOnly )
 557 {
 558         /* Queue needed for breadth-first search, load it with the start node. */
 559         NameInstList nameQueue;
 560         nameQueue.append( refFrom );
 561
 562         NameSet result;
 563         while ( nameQueue.length() > 0 ) {
 564                 /* Pull the next from location off the queue. */
 565                 NameInst *from = nameQueue.detachFirst();
 566
 567                 /* Look for the name. */
 568                 NameMapEl *low, *high;
 569                 if ( from->children.findMulti( data, low, high ) ) {
 570                         /* Record all instances of the name. */
 571                         for ( ; low <= high; low++ )
 572                                 result.insert( low->value );
 573                 }
 574
 575                 /* Name not there, do breadth-first operation of appending all
 576                  * childrent to the processing queue. */
 577                 for ( NameVect::Iter name = from->childVect; name.lte(); name++ ) {
 578                         if ( !recLabelsOnly || (*name)->isLabel )
 579                                 nameQueue.append( *name );
 580                 }
 581         }
 582
 583         /* Queue exhausted and name never found. */
 584         return result;
 585 }
 586
 587 void ParseData::resolveFrom( NameSet &result, NameInst *refFrom,
 588                 const NameRef &nameRef, int namePos )
 589 {
 590         /* Look for the name in the owning scope of the factor with aug. */
 591         NameSet partResult = resolvePart( refFrom, nameRef[namePos], false );
 592
 593         /* If there are more parts to the name then continue on. */
 594         if ( ++namePos < nameRef.length() ) {
 595                 /* There are more components to the name, search using all the part
 596                  * results as the base. */
 597                 for ( NameSet::Iter name = partResult; name.lte(); name++ )
 598                         resolveFrom( result, *name, nameRef, namePos );
 599         }
 600         else {
 601                 /* This is the last component, append the part results to the final
 602                  * results. */
 603                 result.insert( partResult );
 604         }
 605 }
 606
 607 /* Write out a name reference. */
 608 ostream &operator<<( ostream &out, const NameRef &nameRef )
 609 {
 610         int pos = 0;
 611         if ( nameRef[pos] == 0 ) {
 612                 out << "::";
 613                 pos += 1;
 614         }
 615         out << nameRef[pos++];
 616         for ( ; pos < nameRef.length(); pos++ )
 617                 out << "::" << nameRef[pos];
 618         return out;
 619 }
 620
 621 ostream &operator<<( ostream &out, const NameInst &nameInst )
 622 {
 623         /* Count the number fully qualified name parts. */
 624         int numParents = 0;
 625         NameInst *curParent = nameInst.parent;
 626         while ( curParent != 0 ) {
 627                 numParents += 1;
 628                 curParent = curParent->parent;
 629         }
 630
 631         /* Make an array and fill it in. */
 632         curParent = nameInst.parent;
 633         NameInst **parents = new NameInst*[numParents];
 634         for ( int p = numParents-1; p >= 0; p-- ) {
 635                 parents[p] = curParent;
 636                 curParent = curParent->parent;
 637         }
 638
 639         /* Write the parents out, skip the root. */
 640         for ( int p = 1; p < numParents; p++ )
 641                 out << "::" << ( parents[p]->name != 0 ? parents[p]->name : "<ANON>" );
 642
 643         /* Write the name and cleanup. */
 644         out << "::" << ( nameInst.name != 0 ? nameInst.name : "<ANON>" );
 645         delete[] parents;
 646         return out;
 647 }
 648
 649 struct CmpNameInstLoc
 650 {
 651         static int compare( const NameInst *ni1, const NameInst *ni2 )
 652         {
 653                 if ( ni1->loc.line < ni2->loc.line )
 654                         return -1;
 655                 else if ( ni1->loc.line > ni2->loc.line )
 656                         return 1;
 657                 else if ( ni1->loc.col < ni2->loc.col )
 658                         return -1;
 659                 else if ( ni1->loc.col > ni2->loc.col )
 660                         return 1;
 661                 return 0;
 662         }
 663 };
 664
 665 void errorStateLabels( const NameSet &resolved )
 666 {
 667         MergeSort<NameInst*, CmpNameInstLoc> mergeSort;
 668         mergeSort.sort( resolved.data, resolved.length() );
 669         for ( NameSet::Iter res = resolved; res.lte(); res++ )
 670                 error((*res)->loc) << "  -> " << **res << endl;
 671 }
 672
 673
 674 NameInst *ParseData::resolveStateRef( const NameRef &nameRef, InputLoc &loc, Action *action )
 675 {
 676         NameInst *nameInst = 0;
 677
 678         /* Do the local search if the name is not strictly a root level name
 679          * search. */
 680         if ( nameRef[0] != 0 ) {
 681                 /* If the action is referenced, resolve all of them. */
 682                 if ( action != 0 && action->actionRefs.length() > 0 ) {
 683                         /* Look for the name in all referencing scopes. */
 684                         NameSet resolved;
 685                         for ( ActionRefs::Iter actRef = action->actionRefs; actRef.lte(); actRef++ )
 686                                 resolveFrom( resolved, *actRef, nameRef, 0 );
 687
 688                         if ( resolved.length() > 0 ) {
 689                                 /* Take the first one. */
 690                                 nameInst = resolved[0];
 691                                 if ( resolved.length() > 1 ) {
 692                                         /* Complain about the multiple references. */
 693                                         error(loc) << "state reference " << nameRef <<
 694                                                         " resolves to multiple entry points" << endl;
 695                                         errorStateLabels( resolved );
 696                                 }
 697                         }
 698                 }
 699         }
 700
 701         /* If not found in the local scope, look in global. */
 702         if ( nameInst == 0 ) {
 703                 NameSet resolved;
 704                 int fromPos = nameRef[0] != 0 ? 0 : 1;
 705                 resolveFrom( resolved, rootName, nameRef, fromPos );
 706
 707                 if ( resolved.length() > 0 ) {
 708                         /* Take the first. */
 709                         nameInst = resolved[0];
 710                         if ( resolved.length() > 1 ) {
 711                                 /* Complain about the multiple references. */
 712                                 error(loc) << "state reference " << nameRef <<
 713                                                 " resolves to multiple entry points" << endl;
 714                                 errorStateLabels( resolved );
 715                         }
 716                 }
 717         }
 718
 719         if ( nameInst == 0 ) {
 720                 /* If not found then complain. */
 721                 error(loc) << "could not resolve state reference " << nameRef << endl;
 722         }
 723         return nameInst;
 724 }
 725
 726 void ParseData::resolveNameRefs( InlineList *inlineList, Action *action )
 727 {
 728         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
 729                 switch ( item->type ) {
 730                         case InlineItem::Entry: case InlineItem::Goto:
 731                         case InlineItem::Call: case InlineItem::Next: {
 732                                 /* Resolve, pass action for local search. */
 733                                 NameInst *target = resolveStateRef( *item->nameRef, item->loc, action );
 734
 735                                 /* Check if the target goes into a longest match. */
 736                                 NameInst *search = target->parent;
 737                                 while ( search != 0 ) {
 738                                         if ( search->isLongestMatch ) {
 739                                                 error(item->loc) << "cannot enter inside a longest "
 740                                                                 "match construction as an entry point" << endl;
 741                                                 break;
 742                                         }
 743                                         search = search->parent;
 744                                 }
 745
 746                                 /* Note the reference in the name. This will cause the entry
 747                                  * point to survive to the end of the graph generating walk. */
 748                                 if ( target != 0 )
 749                                         target->numRefs += 1;
 750                                 item->nameTarg = target;
 751                                 break;
 752                         }
 753                         default:
 754                                 break;
 755                 }
 756
 757                 /* Some of the item types may have children. */
 758                 if ( item->children != 0 )
 759                         resolveNameRefs( item->children, action );
 760         }
 761 }
 762
 763 /* Resolve references to labels in actions. */
 764 void ParseData::resolveActionNameRefs()
 765 {
 766         for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
 767                 /* Only care about the actions that are referenced. */
 768                 if ( act->actionRefs.length() > 0 )
 769                         resolveNameRefs( act->inlineList, act );
 770         }
 771 }
 772
 773 /* Walk a name tree starting at from and fill the name index. */
 774 void ParseData::fillNameIndex( NameInst *from )
 775 {
 776         /* Fill the value for from in the name index. */
 777         nameIndex[from->id] = from;
 778
 779         /* Recurse on the implicit final state and then all children. */
 780         if ( from->final != 0 )
 781                 fillNameIndex( from->final );
 782         for ( NameVect::Iter name = from->childVect; name.lte(); name++ )
 783                 fillNameIndex( *name );
 784 }
 785
 786 void ParseData::makeRootNames()
 787 {
 788         /* Create the root name. */
 789         rootName = new NameInst( InputLoc(), 0, 0, nextNameId++, false );
 790         exportsRootName = new NameInst( InputLoc(), 0, 0, nextNameId++, false );
 791 }
 792
 793 /* Build the name tree and supporting data structures. */
 794 void ParseData::makeNameTree( GraphDictEl *dictEl )
 795 {
 796         /* Set up curNameInst for the walk. */
 797         initNameWalk();
 798
 799         if ( dictEl != 0 ) {
 800                 /* A start location has been specified. */
 801                 dictEl->value->makeNameTree( dictEl->loc, this );
 802         }
 803         else {
 804                 /* First make the name tree. */
 805                 for ( GraphList::Iter glel = instanceList; glel.lte(); glel++ ) {
 806                         /* Recurse on the instance. */
 807                         glel->value->makeNameTree( glel->loc, this );
 808                 }
 809         }
 810
 811         /* The number of nodes in the tree can now be given by nextNameId */
 812         nameIndex = new NameInst*[nextNameId];
 813         memset( nameIndex, 0, sizeof(NameInst*)*nextNameId );
 814         fillNameIndex( rootName );
 815         fillNameIndex( exportsRootName );
 816 }
 817
 818
 819 void ParseData::createBuiltin( char *name, BuiltinMachine builtin )
 820 {
 821         Expression *expression = new Expression( builtin );
 822         Join *join = new Join( expression );
 823         JoinOrLm *joinOrLm = new JoinOrLm( join );
 824         VarDef *varDef = new VarDef( name, joinOrLm );
 825         GraphDictEl *graphDictEl = new GraphDictEl( name, varDef );
 826         graphDict.insert( graphDictEl );
 827 }
 828
 829 /* Initialize the graph dict with builtin types. */
 830 void ParseData::initGraphDict( )
 831 {
 832         createBuiltin( "any", BT_Any );
 833         createBuiltin( "ascii", BT_Ascii );
 834         createBuiltin( "extend", BT_Extend );
 835         createBuiltin( "alpha", BT_Alpha );
 836         createBuiltin( "digit", BT_Digit );
 837         createBuiltin( "alnum", BT_Alnum );
 838         createBuiltin( "lower", BT_Lower );
 839         createBuiltin( "upper", BT_Upper );
 840         createBuiltin( "cntrl", BT_Cntrl );
 841         createBuiltin( "graph", BT_Graph );
 842         createBuiltin( "print", BT_Print );
 843         createBuiltin( "punct", BT_Punct );
 844         createBuiltin( "space", BT_Space );
 845         createBuiltin( "xdigit", BT_Xdigit );
 846         createBuiltin( "null", BT_Lambda );
 847         createBuiltin( "zlen", BT_Lambda );
 848         createBuiltin( "empty", BT_Empty );
 849 }
 850
 851 /* Set the alphabet type. If the types are not valid returns false. */
 852 bool ParseData::setAlphType( const InputLoc &loc, char *s1, char *s2 )
 853 {
 854         alphTypeLoc = loc;
 855         userAlphType = findAlphType( s1, s2 );
 856         alphTypeSet = true;
 857         return userAlphType != 0;
 858 }
 859
 860 /* Set the alphabet type. If the types are not valid returns false. */
 861 bool ParseData::setAlphType( const InputLoc &loc, char *s1 )
 862 {
 863         alphTypeLoc = loc;
 864         userAlphType = findAlphType( s1 );
 865         alphTypeSet = true;
 866         return userAlphType != 0;
 867 }
 868
 869 bool ParseData::setVariable( char *var, InlineList *inlineList )
 870 {
 871         bool set = true;
 872
 873         if ( strcmp( var, "p" ) == 0 )
 874                 pExpr = inlineList;
 875         else if ( strcmp( var, "pe" ) == 0 )
 876                 peExpr = inlineList;
 877         else if ( strcmp( var, "cs" ) == 0 )
 878                 csExpr = inlineList;
 879         else if ( strcmp( var, "data" ) == 0 )
 880                 dataExpr = inlineList;
 881         else if ( strcmp( var, "top" ) == 0 )
 882                 topExpr = inlineList;
 883         else if ( strcmp( var, "stack" ) == 0 )
 884                 stackExpr = inlineList;
 885         else if ( strcmp( var, "act" ) == 0 )
 886                 actExpr = inlineList;
 887         else if ( strcmp( var, "tokstart" ) == 0 )
 888                 tokstartExpr = inlineList;
 889         else if ( strcmp( var, "tokend" ) == 0 )
 890                 tokendExpr = inlineList;
 891         else
 892                 set = false;
 893
 894         return set;
 895 }
 896
 897 /* Initialize the key operators object that will be referenced by all fsms
 898  * created. */
 899 void ParseData::initKeyOps( )
 900 {
 901         /* Signedness and bounds. */
 902         HostType *alphType = alphTypeSet ? userAlphType : hostLang->defaultAlphType;
 903         thisKeyOps.setAlphType( alphType );
 904
 905         if ( lowerNum != 0 ) {
 906                 /* If ranges are given then interpret the alphabet type. */
 907                 thisKeyOps.minKey = makeFsmKeyNum( lowerNum, rangeLowLoc, this );
 908                 thisKeyOps.maxKey = makeFsmKeyNum( upperNum, rangeHighLoc, this );
 909         }
 910
 911         thisCondData.lastCondKey = thisKeyOps.maxKey;
 912 }
 913
 914 void ParseData::printNameInst( NameInst *nameInst, int level )
 915 {
 916         for ( int i = 0; i < level; i++ )
 917                 cerr << "  ";
 918         cerr << (nameInst->name != 0 ? nameInst->name : "<ANON>") <<
 919                         "  id: " << nameInst->id <<
 920                         "  refs: " << nameInst->numRefs <<
 921                         "  uses: " << nameInst->numUses << endl;
 922         for ( NameVect::Iter name = nameInst->childVect; name.lte(); name++ )
 923                 printNameInst( *name, level+1 );
 924 }
 925
 926 /* Remove duplicates of unique actions from an action table. */
 927 void ParseData::removeDups( ActionTable &table )
 928 {
 929         /* Scan through the table looking for unique actions to
 930          * remove duplicates of. */
 931         for ( int i = 0; i < table.length(); i++ ) {
 932                 /* Remove any duplicates ahead of i. */
 933                 for ( int r = i+1; r < table.length(); ) {
 934                         if ( table[r].value == table[i].value )
 935                                 table.vremove(r);
 936                         else
 937                                 r += 1;
 938                 }
 939         }
 940 }
 941
 942 /* Remove duplicates from action lists. This operates only on transition and
 943  * eof action lists and so should be called once all actions have been
 944  * transfered to their final resting place. */
 945 void ParseData::removeActionDups( FsmAp *graph )
 946 {
 947         /* Loop all states. */
 948         for ( StateList::Iter state = graph->stateList; state.lte(); state++ ) {
 949                 /* Loop all transitions. */
 950                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
 951                         removeDups( trans->actionTable );
 952                 removeDups( state->toStateActionTable );
 953                 removeDups( state->fromStateActionTable );
 954                 removeDups( state->eofActionTable );
 955         }
 956 }
 957
 958 Action *ParseData::newAction( char *name, InlineList *inlineList )
 959 {
 960         InputLoc loc;
 961         loc.line = 1;
 962         loc.col = 1;
 963         loc.fileName = "<NONE>";
 964
 965         Action *action = new Action( loc, name, inlineList, nextCondId++ );
 966         action->actionRefs.append( rootName );
 967         actionList.append( action );
 968         return action;
 969 }
 970
 971 void ParseData::initLongestMatchData()
 972 {
 973         if ( lmList.length() > 0 ) {
 974                 /* The initTokStart action resets the token start. */
 975                 InlineList *il1 = new InlineList;
 976                 il1->append( new InlineItem( InputLoc(), InlineItem::LmInitTokStart ) );
 977                 initTokStart = newAction( "initts", il1 );
 978                 initTokStart->isLmAction = true;
 979
 980                 /* The initActId action gives act a default value. */
 981                 InlineList *il4 = new InlineList;
 982                 il4->append( new InlineItem( InputLoc(), InlineItem::LmInitAct ) );
 983                 initActId = newAction( "initact", il4 );
 984                 initActId->isLmAction = true;
 985
 986                 /* The setTokStart action sets tokstart. */
 987                 InlineList *il5 = new InlineList;
 988                 il5->append( new InlineItem( InputLoc(), InlineItem::LmSetTokStart ) );
 989                 setTokStart = newAction( "tokstart", il5 );
 990                 setTokStart->isLmAction = true;
 991
 992                 /* The setTokEnd action sets tokend. */
 993                 InlineList *il3 = new InlineList;
 994                 il3->append( new InlineItem( InputLoc(), InlineItem::LmSetTokEnd ) );
 995                 setTokEnd = newAction( "tokend", il3 );
 996                 setTokEnd->isLmAction = true;
 997
 998                 /* The action will also need an ordering: ahead of all user action
 999                  * embeddings. */
1000                 initTokStartOrd = curActionOrd++;
1001                 initActIdOrd = curActionOrd++;
1002                 setTokStartOrd = curActionOrd++;
1003                 setTokEndOrd = curActionOrd++;
1004         }
1005 }
1006
1007 /* After building the graph, do some extra processing to ensure the runtime
1008  * data of the longest mactch operators is consistent. */
1009 void ParseData::setLongestMatchData( FsmAp *graph )
1010 {
1011         if ( lmList.length() > 0 ) {
1012                 /* Make sure all entry points (targets of fgoto, fcall, fnext, fentry)
1013                  * init the tokstart. */
1014                 for ( EntryMap::Iter en = graph->entryPoints; en.lte(); en++ ) {
1015                         /* This is run after duplicates are removed, we must guard against
1016                          * inserting a duplicate. */
1017                         ActionTable &actionTable = en->value->toStateActionTable;
1018                         if ( ! actionTable.hasAction( initTokStart ) )
1019                                 actionTable.setAction( initTokStartOrd, initTokStart );
1020                 }
1021
1022                 /* Find the set of states that are the target of transitions with
1023                  * actions that have calls. These states will be targeted by fret
1024                  * statements. */
1025                 StateSet states;
1026                 for ( StateList::Iter state = graph->stateList; state.lte(); state++ ) {
1027                         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
1028                                 for ( ActionTable::Iter ati = trans->actionTable; ati.lte(); ati++ ) {
1029                                         if ( ati->value->anyCall && trans->toState != 0 )
1030                                                 states.insert( trans->toState );
1031                                 }
1032                         }
1033                 }
1034
1035
1036                 /* Init tokstart upon entering the above collected states. */
1037                 for ( StateSet::Iter ps = states; ps.lte(); ps++ ) {
1038                         /* This is run after duplicates are removed, we must guard against
1039                          * inserting a duplicate. */
1040                         ActionTable &actionTable = (*ps)->toStateActionTable;
1041                         if ( ! actionTable.hasAction( initTokStart ) )
1042                                 actionTable.setAction( initTokStartOrd, initTokStart );
1043                 }
1044         }
1045 }
1046
1047 /* Make the graph from a graph dict node. Does minimization and state sorting. */
1048 FsmAp *ParseData::makeInstance( GraphDictEl *gdNode )
1049 {
1050         /* Build the graph from a walk of the parse tree. */
1051         FsmAp *graph = gdNode->value->walk( this );
1052
1053         /* Resolve any labels that point to multiple states. Any labels that are
1054          * still around are referenced only by gotos and calls and they need to be
1055          * made into deterministic entry points. */
1056         graph->deterministicEntry();
1057
1058         /*
1059          * All state construction is now complete.
1060          */
1061
1062         /* Transfer global error actions. */
1063         for ( StateList::Iter state = graph->stateList; state.lte(); state++ )
1064                 graph->transferErrorActions( state, 0 );
1065
1066         removeActionDups( graph );
1067
1068         /* Remove unreachable states. There should be no dead end states. The
1069          * subtract and intersection operators are the only places where they may
1070          * be created and those operators clean them up. */
1071         graph->removeUnreachableStates();
1072
1073         /* No more fsm operations are to be done. Action ordering numbers are
1074          * no longer of use and will just hinder minimization. Clear them. */
1075         graph->nullActionKeys();
1076
1077         /* Transition priorities are no longer of use. We can clear them
1078          * because they will just hinder minimization as well. Clear them. */
1079         graph->clearAllPriorities();
1080
1081         if ( minimizeOpt != MinimizeNone ) {
1082                 /* Minimize here even if we minimized at every op. Now that function
1083                  * keys have been cleared we may get a more minimal fsm. */
1084                 switch ( minimizeLevel ) {
1085                         case MinimizeApprox:
1086                                 graph->minimizeApproximate();
1087                                 break;
1088                         case MinimizeStable:
1089                                 graph->minimizeStable();
1090                                 break;
1091                         case MinimizePartition1:
1092                                 graph->minimizePartition1();
1093                                 break;
1094                         case MinimizePartition2:
1095                                 graph->minimizePartition2();
1096                                 break;
1097                 }
1098         }
1099
1100         graph->compressTransitions();
1101
1102         return graph;
1103 }
1104
1105 void ParseData::printNameTree()
1106 {
1107         /* Print the name instance map. */
1108         for ( NameVect::Iter name = rootName->childVect; name.lte(); name++ )
1109                 printNameInst( *name, 0 );
1110
1111         cerr << "name index:" << endl;
1112         /* Show that the name index is correct. */
1113         for ( int ni = 0; ni < nextNameId; ni++ ) {
1114                 cerr << ni << ": ";
1115                 char *name = nameIndex[ni]->name;
1116                 cerr << ( name != 0 ? name : "<ANON>" ) << endl;
1117         }
1118 }
1119
1120 FsmAp *ParseData::makeSpecific( GraphDictEl *gdNode )
1121 {
1122         /* Build the name tree and supporting data structures. */
1123         makeNameTree( gdNode );
1124
1125         /* Resove name references from gdNode. */
1126         initNameWalk();
1127         gdNode->value->resolveNameRefs( this );
1128
1129         /* Do not resolve action references. Since we are not building the entire
1130          * graph there's a good chance that many name references will fail. This
1131          * is okay since generating part of the graph is usually only done when
1132          * inspecting the compiled machine. */
1133
1134         /* Same story for extern entry point references. */
1135
1136         /* Flag this case so that the XML code generator is aware that we haven't
1137          * looked up name references in actions. It can then avoid segfaulting. */
1138         generatingSectionSubset = true;
1139
1140         /* Just building the specified graph. */
1141         initNameWalk();
1142         FsmAp *mainGraph = makeInstance( gdNode );
1143
1144         return mainGraph;
1145 }
1146
1147 FsmAp *ParseData::makeAll()
1148 {
1149         /* Build the name tree and supporting data structures. */
1150         makeNameTree( 0 );
1151
1152         /* Resove name references in the tree. */
1153         initNameWalk();
1154         for ( GraphList::Iter glel = instanceList; glel.lte(); glel++ )
1155                 glel->value->resolveNameRefs( this );
1156
1157         /* Resolve action code name references. */
1158         resolveActionNameRefs();
1159
1160         /* Force name references to the top level instantiations. */
1161         for ( NameVect::Iter inst = rootName->childVect; inst.lte(); inst++ )
1162                 (*inst)->numRefs += 1;
1163
1164         FsmAp *mainGraph = 0;
1165         FsmAp **graphs = new FsmAp*[instanceList.length()];
1166         int numOthers = 0;
1167
1168         /* Make all the instantiations, we know that main exists in this list. */
1169         initNameWalk();
1170         for ( GraphList::Iter glel = instanceList; glel.lte();  glel++ ) {
1171                 if ( strcmp( glel->key, mainMachine ) == 0 ) {
1172                         /* Main graph is always instantiated. */
1173                         mainGraph = makeInstance( glel );
1174                 }
1175                 else {
1176                         /* Instantiate and store in others array. */
1177                         graphs[numOthers++] = makeInstance( glel );
1178                 }
1179         }
1180
1181         if ( mainGraph == 0 )
1182                 mainGraph = graphs[--numOthers];
1183
1184         if ( numOthers > 0 ) {
1185                 /* Add all the other graphs into main. */
1186                 mainGraph->globOp( graphs, numOthers );
1187         }
1188
1189         delete[] graphs;
1190         return mainGraph;
1191 }
1192
1193 void ParseData::analyzeAction( Action *action, InlineList *inlineList )
1194 {
1195         /* FIXME: Actions used as conditions should be very constrained. */
1196         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
1197                 if ( item->type == InlineItem::Call || item->type == InlineItem::CallExpr )
1198                         action->anyCall = true;
1199
1200                 /* Need to recurse into longest match items. */
1201                 if ( item->type == InlineItem::LmSwitch ) {
1202                         LongestMatch *lm = item->longestMatch;
1203                         for ( LmPartList::Iter lmi = *lm->longestMatchList; lmi.lte(); lmi++ ) {
1204                                 if ( lmi->action != 0 )
1205                                         analyzeAction( action, lmi->action->inlineList );
1206                         }
1207                 }
1208
1209                 if ( item->type == InlineItem::LmOnLast ||
1210                                 item->type == InlineItem::LmOnNext ||
1211                                 item->type == InlineItem::LmOnLagBehind )
1212                 {
1213                         LongestMatchPart *lmi = item->longestMatchPart;
1214                         if ( lmi->action != 0 )
1215                                 analyzeAction( action, lmi->action->inlineList );
1216                 }
1217
1218                 if ( item->children != 0 )
1219                         analyzeAction( action, item->children );
1220         }
1221 }
1222
1223
1224 /* Check actions for bad uses of fsm directives. We don't go inside longest
1225  * match items in actions created by ragel, since we just want the user
1226  * actions. */
1227 void ParseData::checkInlineList( Action *act, InlineList *inlineList )
1228 {
1229         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
1230                 /* EOF checks. */
1231                 if ( act->numEofRefs > 0 ) {
1232                         switch ( item->type ) {
1233                         case InlineItem::PChar:
1234                                 error(item->loc) << "pointer to current element does not exist in "
1235                                                 "EOF action code" << endl;
1236                                 break;
1237                         case InlineItem::Char:
1238                                 error(item->loc) << "current element does not exist in "
1239                                                 "EOF action code" << endl;
1240                                 break;
1241                         case InlineItem::Hold:
1242                                 error(item->loc) << "changing the current element not possible in "
1243                                                 "EOF action code" << endl;
1244                                 break;
1245                         case InlineItem::Exec:
1246                                 error(item->loc) << "changing the current element not possible in "
1247                                                 "EOF action code" << endl;
1248                                 break;
1249                         case InlineItem::Goto: case InlineItem::Call:
1250                         case InlineItem::Next: case InlineItem::GotoExpr:
1251                         case InlineItem::CallExpr: case InlineItem::NextExpr:
1252                         case InlineItem::Ret:
1253                                 error(item->loc) << "changing the current state not possible in "
1254                                                 "EOF action code" << endl;
1255                                 break;
1256                         default:
1257                                 break;
1258                         }
1259                 }
1260
1261                 /* Recurse. */
1262                 if ( item->children != 0 )
1263                         checkInlineList( act, item->children );
1264         }
1265 }
1266
1267 void ParseData::checkAction( Action *action )
1268 {
1269         /* Check for actions with calls that are embedded within a longest match
1270          * machine. */
1271         if ( !action->isLmAction && action->numRefs() > 0 && action->anyCall ) {
1272                 for ( ActionRefs::Iter ar = action->actionRefs; ar.lte(); ar++ ) {
1273                         NameInst *check = *ar;
1274                         while ( check != 0 ) {
1275                                 if ( check->isLongestMatch ) {
1276                                         error(action->loc) << "within a scanner, fcall is permitted"
1277                                                 " only in pattern actions" << endl;
1278                                         break;
1279                                 }
1280                                 check = check->parent;
1281                         }
1282                 }
1283         }
1284
1285         checkInlineList( action, action->inlineList );
1286 }
1287
1288
1289 void ParseData::analyzeGraph( FsmAp *graph )
1290 {
1291         for ( ActionList::Iter act = actionList; act.lte(); act++ )
1292                 analyzeAction( act, act->inlineList );
1293
1294         for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
1295                 /* The transition list. */
1296                 for ( TransList::Iter trans = st->outList; trans.lte(); trans++ ) {
1297                         for ( ActionTable::Iter at = trans->actionTable; at.lte(); at++ )
1298                                 at->value->numTransRefs += 1;
1299                 }
1300
1301                 for ( ActionTable::Iter at = st->toStateActionTable; at.lte(); at++ )
1302                         at->value->numToStateRefs += 1;
1303
1304                 for ( ActionTable::Iter at = st->fromStateActionTable; at.lte(); at++ )
1305                         at->value->numFromStateRefs += 1;
1306
1307                 for ( ActionTable::Iter at = st->eofActionTable; at.lte(); at++ )
1308                         at->value->numEofRefs += 1;
1309
1310                 for ( StateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
1311                         for ( CondSet::Iter sci = sc->condSpace->condSet; sci.lte(); sci++ )
1312                                 (*sci)->numCondRefs += 1;
1313                 }
1314         }
1315
1316         /* Checks for bad usage of directives in action code. */
1317         for ( ActionList::Iter act = actionList; act.lte(); act++ )
1318                 checkAction( act );
1319 }
1320
1321 void ParseData::makeExportsNameTree()
1322 {
1323         /* Make a name tree for the exports. */
1324         initExportsNameWalk();
1325
1326         /* First make the name tree. */
1327         for ( GraphDict::Iter gdel = graphDict; gdel.lte(); gdel++ ) {
1328                 if ( gdel->value->isExport ) {
1329                         /* Recurse on the instance. */
1330                         gdel->value->makeNameTree( gdel->loc, this );
1331                 }
1332         }
1333 }
1334
1335 void ParseData::makeExports()
1336 {
1337         makeExportsNameTree();
1338
1339         /* Resove name references in the tree. */
1340         initExportsNameWalk();
1341         for ( GraphDict::Iter gdel = graphDict; gdel.lte(); gdel++ ) {
1342                 if ( gdel->value->isExport )
1343                         gdel->value->resolveNameRefs( this );
1344         }
1345
1346         /* Make all the instantiations, we know that main exists in this list. */
1347         initExportsNameWalk();
1348         for ( GraphDict::Iter gdel = graphDict; gdel.lte();  gdel++ ) {
1349                 /* Check if this var def is an export. */
1350                 if ( gdel->value->isExport ) {
1351                         /* Build the graph from a walk of the parse tree. */
1352                         FsmAp *graph = gdel->value->walk( this );
1353
1354                         /* Build the graph from a walk of the parse tree. */
1355                         if ( !graph->checkSingleCharMachine() ) {
1356                                 error(gdel->loc) << "bad export machine, must define "
1357                                                 "a single character" << endl;
1358                         }
1359                         else {
1360                                 /* Safe to extract the key and declare the export. */
1361                                 Key exportKey = graph->startState->outList.head->lowKey;
1362                                 exportList.append( new Export( gdel->value->name, exportKey ) );
1363                         }
1364                 }
1365         }
1366
1367 }
1368
1369 /* Construct the machine and catch failures which can occur during
1370  * construction. */
1371 void ParseData::prepareMachineGen( GraphDictEl *graphDictEl )
1372 {
1373         try {
1374                 /* This machine construction can fail. */
1375                 prepareMachineGenTBWrapped( graphDictEl );
1376         }
1377         catch ( FsmConstructFail fail ) {
1378                 switch ( fail.reason ) {
1379                         case FsmConstructFail::CondNoKeySpace: {
1380                                 InputLoc &loc = alphTypeSet ? alphTypeLoc : sectionLoc;
1381                                 error(loc) << "sorry, no more characters are "
1382                                                 "available in the alphabet space" << endl;
1383                                 error(loc) << "  for conditions, please use a "
1384                                                 "smaller alphtype or reduce" << endl;
1385                                 error(loc) << "  the span of characters on which "
1386                                                 "conditions are embedded" << endl;
1387                                 break;
1388                         }
1389                 }
1390         }
1391 }
1392
1393 void ParseData::prepareMachineGenTBWrapped( GraphDictEl *graphDictEl )
1394 {
1395         beginProcessing();
1396         initKeyOps();
1397         makeRootNames();
1398         initLongestMatchData();
1399
1400         /* Make the graph, do minimization. */
1401         if ( graphDictEl == 0 )
1402                 sectionGraph = makeAll();
1403         else
1404                 sectionGraph = makeSpecific( graphDictEl );
1405
1406         /* Compute exports from the export definitions. */
1407         makeExports();
1408
1409         /* If any errors have occured in the input file then don't write anything. */
1410         if ( gblErrorCount > 0 )
1411                 return;
1412
1413         analyzeGraph( sectionGraph );
1414
1415         /* Depends on the graph analysis. */
1416         setLongestMatchData( sectionGraph );
1417
1418         /* Decide if an error state is necessary.
1419          *  1. There is an error transition
1420          *  2. There is a gap in the transitions
1421          *  3. The longest match operator requires it. */
1422         if ( lmRequiresErrorState || sectionGraph->hasErrorTrans() )
1423                 sectionGraph->errState = sectionGraph->addState();
1424
1425         /* State numbers need to be assigned such that all final states have a
1426          * larger state id number than all non-final states. This enables the
1427          * first_final mechanism to function correctly. We also want states to be
1428          * ordered in a predictable fashion. So we first apply a depth-first
1429          * search, then do a stable sort by final state status, then assign
1430          * numbers. */
1431
1432         sectionGraph->depthFirstOrdering();
1433         sectionGraph->sortStatesByFinal();
1434         sectionGraph->setStateNumbers( 0 );
1435 }
1436
1437 void ParseData::generateXML( ostream &out )
1438 {
1439         beginProcessing();
1440
1441         /* Make the generator. */
1442         XMLCodeGen codeGen( sectionName, this, sectionGraph, out );
1443
1444         /* Write out with it. */
1445         codeGen.writeXML();
1446
1447         if ( printStatistics ) {
1448                 cerr << "fsm name  : " << sectionName << endl;
1449                 cerr << "num states: " << sectionGraph->stateList.length() << endl;
1450                 cerr << endl;
1451         }
1452 }
1453
1454 /* Send eof to all parsers. */
1455 void terminateAllParsers( )
1456 {
1457         /* FIXME: a proper token is needed here. Suppose we should use the
1458          * location of EOF in the last file that the parser was referenced in. */
1459         InputLoc loc;
1460         loc.fileName = "<EOF>";
1461         loc.line = 0;
1462         loc.col = 0;
1463         for ( ParserDict::Iter pdel = parserDict; pdel.lte(); pdel++ )
1464                 pdel->value->token( loc, _eof, 0, 0 );
1465 }
1466
1467 void writeLanguage( std::ostream &out )
1468 {
1469         out << " lang=\"";
1470         switch ( hostLang->lang ) {
1471                 case HostLang::C:    out << "C"; break;
1472                 case HostLang::D:    out << "D"; break;
1473                 case HostLang::Java: out << "Java"; break;
1474                 case HostLang::Ruby: out << "Ruby"; break;
1475         }
1476         out << "\"";
1477
1478 }
1479
1480 void writeMachines( std::ostream &out, std::string hostData, char *inputFileName )
1481 {
1482         if ( machineSpec == 0 && machineName == 0 ) {
1483                 /* No machine spec or machine name given. Generate everything. */
1484                 for ( ParserDict::Iter parser = parserDict; parser.lte(); parser++ ) {
1485                         ParseData *pd = parser->value->pd;
1486                         if ( pd->instanceList.length() > 0 )
1487                                 pd->prepareMachineGen( 0 );
1488                 }
1489
1490                 if ( gblErrorCount == 0 ) {
1491                         out << "<ragel version=\"" VERSION "\" filename=\"" << inputFileName << "\"";
1492                         writeLanguage( out );
1493                         out << ">\n";
1494                         for ( ParserDict::Iter parser = parserDict; parser.lte(); parser++ ) {
1495                                 ParseData *pd = parser->value->pd;
1496                                 if ( pd->instanceList.length() > 0 )
1497                                         pd->generateXML( out );
1498                         }
1499                         out << hostData;
1500                         out << "</ragel>\n";
1501                 }
1502         }
1503         else if ( parserDict.length() > 0 ) {
1504                 /* There is either a machine spec or machine name given. */
1505                 ParseData *parseData = 0;
1506                 GraphDictEl *graphDictEl = 0;
1507
1508                 /* Traverse the sections, break out when we find a section/machine
1509                  * that matches the one specified. */
1510                 for ( ParserDict::Iter parser = parserDict; parser.lte(); parser++ ) {
1511                         ParseData *checkPd = parser->value->pd;
1512                         if ( machineSpec == 0 || strcmp( checkPd->sectionName, machineSpec ) == 0 ) {
1513                                 GraphDictEl *checkGdEl = 0;
1514                                 if ( machineName == 0 || (checkGdEl =
1515                                                 checkPd->graphDict.find( machineName )) != 0 )
1516                                 {
1517                                         /* Have a machine spec and/or machine name that matches
1518                                          * the -M/-S options. */
1519                                         parseData = checkPd;
1520                                         graphDictEl = checkGdEl;
1521                                         break;
1522                                 }
1523                         }
1524                 }
1525
1526                 if ( parseData == 0 )
1527                         error() << "could not locate machine specified with -S and/or -M" << endl;
1528                 else {
1529                         /* Section/Machine to emit was found. Prepare and emit it. */
1530                         parseData->prepareMachineGen( graphDictEl );
1531                         if ( gblErrorCount == 0 ) {
1532                                 out << "<ragel version=\"" VERSION "\" filename=\"" << inputFileName << "\"";
1533                                 writeLanguage( out );
1534                                 out << ">\n";
1535                                 parseData->generateXML( out );
1536                                 out << hostData;
1537                                 out << "</ragel>\n";
1538                         }
1539                 }
1540         }
1541 }