ragel/parsedata.cpp

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