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