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 mainMachine[] = "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                         assert( graph->entryPoints.find( name->id ) == 0 );
 544                 }
 545         }
 546 }
 547
 548 NameSet ParseData::resolvePart( NameInst *refFrom, char *data, bool recLabelsOnly )
 549 {
 550         /* Queue needed for breadth-first search, load it with the start node. */
 551         NameInstList nameQueue;
 552         nameQueue.append( refFrom );
 553
 554         NameSet result;
 555         while ( nameQueue.length() > 0 ) {
 556                 /* Pull the next from location off the queue. */
 557                 NameInst *from = nameQueue.detachFirst();
 558
 559                 /* Look for the name. */
 560                 NameMapEl *low, *high;
 561                 if ( from->children.findMulti( data, low, high ) ) {
 562                         /* Record all instances of the name. */
 563                         for ( ; low <= high; low++ )
 564                                 result.insert( low->value );
 565                 }
 566
 567                 /* Name not there, do breadth-first operation of appending all
 568                  * childrent to the processing queue. */
 569                 for ( NameVect::Iter name = from->childVect; name.lte(); name++ ) {
 570                         if ( !recLabelsOnly || (*name)->isLabel )
 571                                 nameQueue.append( *name );
 572                 }
 573         }
 574
 575         /* Queue exhausted and name never found. */
 576         return result;
 577 }
 578
 579 void ParseData::resolveFrom( NameSet &result, NameInst *refFrom,
 580                 const NameRef &nameRef, int namePos )
 581 {
 582         /* Look for the name in the owning scope of the factor with aug. */
 583         NameSet partResult = resolvePart( refFrom, nameRef[namePos], false );
 584
 585         /* If there are more parts to the name then continue on. */
 586         if ( ++namePos < nameRef.length() ) {
 587                 /* There are more components to the name, search using all the part
 588                  * results as the base. */
 589                 for ( NameSet::Iter name = partResult; name.lte(); name++ )
 590                         resolveFrom( result, *name, nameRef, namePos );
 591         }
 592         else {
 593                 /* This is the last component, append the part results to the final
 594                  * results. */
 595                 result.insert( partResult );
 596         }
 597 }
 598
 599 /* Write out a name reference. */
 600 ostream &operator<<( ostream &out, const NameRef &nameRef )
 601 {
 602         int pos = 0;
 603         if ( nameRef[pos] == 0 ) {
 604                 out << "::";
 605                 pos += 1;
 606         }
 607         out << nameRef[pos++];
 608         for ( ; pos < nameRef.length(); pos++ )
 609                 out << "::" << nameRef[pos];
 610         return out;
 611 }
 612
 613 ostream &operator<<( ostream &out, const NameInst &nameInst )
 614 {
 615         /* Count the number fully qualified name parts. */
 616         int numParents = 0;
 617         NameInst *curParent = nameInst.parent;
 618         while ( curParent != 0 ) {
 619                 numParents += 1;
 620                 curParent = curParent->parent;
 621         }
 622
 623         /* Make an array and fill it in. */
 624         curParent = nameInst.parent;
 625         NameInst **parents = new NameInst*[numParents];
 626         for ( int p = numParents-1; p >= 0; p-- ) {
 627                 parents[p] = curParent;
 628                 curParent = curParent->parent;
 629         }
 630
 631         /* Write the parents out, skip the root. */
 632         for ( int p = 1; p < numParents; p++ )
 633                 out << "::" << ( parents[p]->name != 0 ? parents[p]->name : "<ANON>" );
 634
 635         /* Write the name and cleanup. */
 636         out << "::" << ( nameInst.name != 0 ? nameInst.name : "<ANON>" );
 637         delete[] parents;
 638         return out;
 639 }
 640
 641 struct CmpNameInstLoc
 642 {
 643         static int compare( const NameInst *ni1, const NameInst *ni2 )
 644         {
 645                 if ( ni1->loc.line < ni2->loc.line )
 646                         return -1;
 647                 else if ( ni1->loc.line > ni2->loc.line )
 648                         return 1;
 649                 else if ( ni1->loc.col < ni2->loc.col )
 650                         return -1;
 651                 else if ( ni1->loc.col > ni2->loc.col )
 652                         return 1;
 653                 return 0;
 654         }
 655 };
 656
 657 void errorStateLabels( const NameSet &resolved )
 658 {
 659         MergeSort<NameInst*, CmpNameInstLoc> mergeSort;
 660         mergeSort.sort( resolved.data, resolved.length() );
 661         for ( NameSet::Iter res = resolved; res.lte(); res++ )
 662                 error((*res)->loc) << "  -> " << **res << endl;
 663 }
 664
 665
 666 NameInst *ParseData::resolveStateRef( const NameRef &nameRef, InputLoc &loc, Action *action )
 667 {
 668         NameInst *nameInst = 0;
 669
 670         /* Do the local search if the name is not strictly a root level name
 671          * search. */
 672         if ( nameRef[0] != 0 ) {
 673                 /* If the action is referenced, resolve all of them. */
 674                 if ( action != 0 && action->actionRefs.length() > 0 ) {
 675                         /* Look for the name in all referencing scopes. */
 676                         NameSet resolved;
 677                         for ( ActionRefs::Iter actRef = action->actionRefs; actRef.lte(); actRef++ )
 678                                 resolveFrom( resolved, *actRef, nameRef, 0 );
 679
 680                         if ( resolved.length() > 0 ) {
 681                                 /* Take the first one. */
 682                                 nameInst = resolved[0];
 683                                 if ( resolved.length() > 1 ) {
 684                                         /* Complain about the multiple references. */
 685                                         error(loc) << "state reference " << nameRef <<
 686                                                         " resolves to multiple entry points" << endl;
 687                                         errorStateLabels( resolved );
 688                                 }
 689                         }
 690                 }
 691         }
 692
 693         /* If not found in the local scope, look in global. */
 694         if ( nameInst == 0 ) {
 695                 NameSet resolved;
 696                 int fromPos = nameRef[0] != 0 ? 0 : 1;
 697                 resolveFrom( resolved, rootName, nameRef, fromPos );
 698
 699                 if ( resolved.length() > 0 ) {
 700                         /* Take the first. */
 701                         nameInst = resolved[0];
 702                         if ( resolved.length() > 1 ) {
 703                                 /* Complain about the multiple references. */
 704                                 error(loc) << "state reference " << nameRef <<
 705                                                 " resolves to multiple entry points" << endl;
 706                                 errorStateLabels( resolved );
 707                         }
 708                 }
 709         }
 710
 711         if ( nameInst == 0 ) {
 712                 /* If not found then complain. */
 713                 error(loc) << "could not resolve state reference " << nameRef << endl;
 714         }
 715         return nameInst;
 716 }
 717
 718 void ParseData::resolveNameRefs( InlineList *inlineList, Action *action )
 719 {
 720         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
 721                 switch ( item->type ) {
 722                         case InlineItem::Entry: case InlineItem::Goto:
 723                         case InlineItem::Call: case InlineItem::Next: {
 724                                 /* Resolve, pass action for local search. */
 725                                 NameInst *target = resolveStateRef( *item->nameRef, item->loc, action );
 726
 727                                 /* Check if the target goes into a longest match. */
 728                                 NameInst *search = target->parent;
 729                                 while ( search != 0 ) {
 730                                         if ( search->isLongestMatch ) {
 731                                                 error(item->loc) << "cannot enter inside a longest "
 732                                                                 "match construction as an entry point" << endl;
 733                                                 break;
 734                                         }
 735                                         search = search->parent;
 736                                 }
 737
 738                                 /* Note the reference in the name. This will cause the entry
 739                                  * point to survive to the end of the graph generating walk. */
 740                                 if ( target != 0 )
 741                                         target->numRefs += 1;
 742                                 item->nameTarg = target;
 743                                 break;
 744                         }
 745                         default:
 746                                 break;
 747                 }
 748
 749                 /* Some of the item types may have children. */
 750                 if ( item->children != 0 )
 751                         resolveNameRefs( item->children, action );
 752         }
 753 }
 754
 755 /* Resolve references to labels in actions. */
 756 void ParseData::resolveActionNameRefs()
 757 {
 758         for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
 759                 /* Only care about the actions that are referenced. */
 760                 if ( act->actionRefs.length() > 0 )
 761                         resolveNameRefs( act->inlineList, act );
 762         }
 763 }
 764
 765 /* Walk a name tree starting at from and fill the name index. */
 766 void ParseData::fillNameIndex( NameInst *from )
 767 {
 768         /* Fill the value for from in the name index. */
 769         nameIndex[from->id] = from;
 770
 771         /* Recurse on the implicit final state and then all children. */
 772         if ( from->final != 0 )
 773                 fillNameIndex( from->final );
 774         for ( NameVect::Iter name = from->childVect; name.lte(); name++ )
 775                 fillNameIndex( *name );
 776 }
 777
 778 void ParseData::makeRootNames()
 779 {
 780         /* Create the root name. */
 781         rootName = new NameInst( InputLoc(), 0, 0, nextNameId++, false );
 782         exportsRootName = new NameInst( InputLoc(), 0, 0, nextNameId++, false );
 783 }
 784
 785 /* Build the name tree and supporting data structures. */
 786 void ParseData::makeNameTree( GraphDictEl *dictEl )
 787 {
 788         /* Set up curNameInst for the walk. */
 789         initNameWalk();
 790
 791         if ( dictEl != 0 ) {
 792                 /* A start location has been specified. */
 793                 dictEl->value->makeNameTree( dictEl->loc, this );
 794         }
 795         else {
 796                 /* First make the name tree. */
 797                 for ( GraphList::Iter glel = instanceList; glel.lte(); glel++ ) {
 798                         /* Recurse on the instance. */
 799                         glel->value->makeNameTree( glel->loc, this );
 800                 }
 801         }
 802
 803         /* The number of nodes in the tree can now be given by nextNameId */
 804         nameIndex = new NameInst*[nextNameId];
 805         memset( nameIndex, 0, sizeof(NameInst*)*nextNameId );
 806         fillNameIndex( rootName );
 807         fillNameIndex( exportsRootName );
 808 }
 809
 810
 811 void ParseData::createBuiltin( char *name, BuiltinMachine builtin )
 812 {
 813         Expression *expression = new Expression( builtin );
 814         Join *join = new Join( expression );
 815         JoinOrLm *joinOrLm = new JoinOrLm( join );
 816         VarDef *varDef = new VarDef( name, joinOrLm );
 817         GraphDictEl *graphDictEl = new GraphDictEl( name, varDef );
 818         graphDict.insert( graphDictEl );
 819 }
 820
 821 /* Initialize the graph dict with builtin types. */
 822 void ParseData::initGraphDict( )
 823 {
 824         createBuiltin( "any", BT_Any );
 825         createBuiltin( "ascii", BT_Ascii );
 826         createBuiltin( "extend", BT_Extend );
 827         createBuiltin( "alpha", BT_Alpha );
 828         createBuiltin( "digit", BT_Digit );
 829         createBuiltin( "alnum", BT_Alnum );
 830         createBuiltin( "lower", BT_Lower );
 831         createBuiltin( "upper", BT_Upper );
 832         createBuiltin( "cntrl", BT_Cntrl );
 833         createBuiltin( "graph", BT_Graph );
 834         createBuiltin( "print", BT_Print );
 835         createBuiltin( "punct", BT_Punct );
 836         createBuiltin( "space", BT_Space );
 837         createBuiltin( "xdigit", BT_Xdigit );
 838         createBuiltin( "null", BT_Lambda );
 839         createBuiltin( "zlen", BT_Lambda );
 840         createBuiltin( "empty", BT_Empty );
 841 }
 842
 843 /* Set the alphabet type. If the types are not valid returns false. */
 844 bool ParseData::setAlphType( char *s1, char *s2 )
 845 {
 846         bool valid = false;
 847         for ( int i = 0; i < hostLang->numHostTypes; i++ ) {
 848                 if ( strcmp( s1, hostLang->hostTypes[i].data1 ) == 0 &&
 849                                 hostLang->hostTypes[i].data2 != 0 &&
 850                                 strcmp( s2, hostLang->hostTypes[i].data2 ) == 0 )
 851                 {
 852                         valid = true;
 853                         userAlphType = hostLang->hostTypes + i;
 854                         break;
 855                 }
 856         }
 857
 858         alphTypeSet = true;
 859         return valid;
 860 }
 861
 862 /* Set the alphabet type. If the types are not valid returns false. */
 863 bool ParseData::setAlphType( char *s1 )
 864 {
 865         bool valid = false;
 866         for ( int i = 0; i < hostLang->numHostTypes; i++ ) {
 867                 if ( strcmp( s1, hostLang->hostTypes[i].data1 ) == 0 &&
 868                                 hostLang->hostTypes[i].data2 == 0 )
 869                 {
 870                         valid = true;
 871                         userAlphType = hostLang->hostTypes + i;
 872                         break;
 873                 }
 874         }
 875
 876         alphTypeSet = true;
 877         return valid;
 878 }
 879
 880 /* Initialize the key operators object that will be referenced by all fsms
 881  * created. */
 882 void ParseData::initKeyOps( )
 883 {
 884         /* Signedness and bounds. */
 885         HostType *alphType = alphTypeSet ? userAlphType : hostLang->defaultAlphType;
 886         thisKeyOps.setAlphType( alphType );
 887
 888         if ( lowerNum != 0 ) {
 889                 /* If ranges are given then interpret the alphabet type. */
 890                 thisKeyOps.minKey = makeFsmKeyNum( lowerNum, rangeLowLoc, this );
 891                 thisKeyOps.maxKey = makeFsmKeyNum( upperNum, rangeHighLoc, this );
 892         }
 893
 894         thisCondData.nextCondKey = thisKeyOps.maxKey;
 895         thisCondData.nextCondKey.increment();
 896 }
 897
 898 void ParseData::printNameInst( NameInst *nameInst, int level )
 899 {
 900         for ( int i = 0; i < level; i++ )
 901                 cerr << "  ";
 902         cerr << (nameInst->name != 0 ? nameInst->name : "<ANON>") <<
 903                         "  id: " << nameInst->id <<
 904                         "  refs: " << nameInst->numRefs <<
 905                         "  uses: " << nameInst->numUses << endl;
 906         for ( NameVect::Iter name = nameInst->childVect; name.lte(); name++ )
 907                 printNameInst( *name, level+1 );
 908 }
 909
 910 /* Remove duplicates of unique actions from an action table. */
 911 void ParseData::removeDups( ActionTable &table )
 912 {
 913         /* Scan through the table looking for unique actions to
 914          * remove duplicates of. */
 915         for ( int i = 0; i < table.length(); i++ ) {
 916                 /* Remove any duplicates ahead of i. */
 917                 for ( int r = i+1; r < table.length(); ) {
 918                         if ( table[r].value == table[i].value )
 919                                 table.vremove(r);
 920                         else
 921                                 r += 1;
 922                 }
 923         }
 924 }
 925
 926 /* Remove duplicates from action lists. This operates only on transition and
 927  * eof action lists and so should be called once all actions have been
 928  * transfered to their final resting place. */
 929 void ParseData::removeActionDups( FsmAp *graph )
 930 {
 931         /* Loop all states. */
 932         for ( StateList::Iter state = graph->stateList; state.lte(); state++ ) {
 933                 /* Loop all transitions. */
 934                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
 935                         removeDups( trans->actionTable );
 936                 removeDups( state->toStateActionTable );
 937                 removeDups( state->fromStateActionTable );
 938                 removeDups( state->eofActionTable );
 939         }
 940 }
 941
 942 Action *ParseData::newAction( char *name, InlineList *inlineList )
 943 {
 944         InputLoc loc;
 945         loc.line = 1;
 946         loc.col = 1;
 947         loc.fileName = "<NONE>";
 948
 949         Action *action = new Action( loc, name, inlineList, nextCondId++ );
 950         action->actionRefs.append( rootName );
 951         actionList.append( action );
 952         return action;
 953 }
 954
 955 void ParseData::initLongestMatchData()
 956 {
 957         if ( lmList.length() > 0 ) {
 958                 /* The initTokStart action resets the token start. */
 959                 InlineList *il1 = new InlineList;
 960                 il1->append( new InlineItem( InputLoc(), InlineItem::LmInitTokStart ) );
 961                 initTokStart = newAction( "initts", il1 );
 962                 initTokStart->isLmAction = true;
 963
 964                 /* The initActId action gives act a default value. */
 965                 InlineList *il4 = new InlineList;
 966                 il4->append( new InlineItem( InputLoc(), InlineItem::LmInitAct ) );
 967                 initActId = newAction( "initact", il4 );
 968                 initActId->isLmAction = true;
 969
 970                 /* The setTokStart action sets tokstart. */
 971                 InlineList *il5 = new InlineList;
 972                 il5->append( new InlineItem( InputLoc(), InlineItem::LmSetTokStart ) );
 973                 setTokStart = newAction( "tokstart", il5 );
 974                 setTokStart->isLmAction = true;
 975
 976                 /* The setTokEnd action sets tokend. */
 977                 InlineList *il3 = new InlineList;
 978                 il3->append( new InlineItem( InputLoc(), InlineItem::LmSetTokEnd ) );
 979                 setTokEnd = newAction( "tokend", il3 );
 980                 setTokEnd->isLmAction = true;
 981
 982                 /* The action will also need an ordering: ahead of all user action
 983                  * embeddings. */
 984                 initTokStartOrd = curActionOrd++;
 985                 initActIdOrd = curActionOrd++;
 986                 setTokStartOrd = curActionOrd++;
 987                 setTokEndOrd = curActionOrd++;
 988         }
 989 }
 990
 991 /* After building the graph, do some extra processing to ensure the runtime
 992  * data of the longest mactch operators is consistent. */
 993 void ParseData::setLongestMatchData( FsmAp *graph )
 994 {
 995         if ( lmList.length() > 0 ) {
 996                 /* Make sure all entry points (targets of fgoto, fcall, fnext, fentry)
 997                  * init the tokstart. */
 998                 for ( EntryMap::Iter en = graph->entryPoints; en.lte(); en++ ) {
 999                         /* This is run after duplicates are removed, we must guard against
1000                          * inserting a duplicate. */
1001                         ActionTable &actionTable = en->value->toStateActionTable;
1002                         if ( ! actionTable.hasAction( initTokStart ) )
1003                                 actionTable.setAction( initTokStartOrd, initTokStart );
1004                 }
1005
1006                 /* Find the set of states that are the target of transitions with
1007                  * actions that have calls. These states will be targeted by fret
1008                  * statements. */
1009                 StateSet states;
1010                 for ( StateList::Iter state = graph->stateList; state.lte(); state++ ) {
1011                         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
1012                                 for ( ActionTable::Iter ati = trans->actionTable; ati.lte(); ati++ ) {
1013                                         if ( ati->value->anyCall && trans->toState != 0 )
1014                                                 states.insert( trans->toState );
1015                                 }
1016                         }
1017                 }
1018
1019
1020                 /* Init tokstart upon entering the above collected states. */
1021                 for ( StateSet::Iter ps = states; ps.lte(); ps++ ) {
1022                         /* This is run after duplicates are removed, we must guard against
1023                          * inserting a duplicate. */
1024                         ActionTable &actionTable = (*ps)->toStateActionTable;
1025                         if ( ! actionTable.hasAction( initTokStart ) )
1026                                 actionTable.setAction( initTokStartOrd, initTokStart );
1027                 }
1028         }
1029 }
1030
1031 /* Make the graph from a graph dict node. Does minimization and state sorting. */
1032 FsmAp *ParseData::makeInstance( GraphDictEl *gdNode )
1033 {
1034         /* Build the graph from a walk of the parse tree. */
1035         FsmAp *graph = gdNode->value->walk( this );
1036
1037         /* Resolve any labels that point to multiple states. Any labels that are
1038          * still around are referenced only by gotos and calls and they need to be
1039          * made into deterministic entry points. */
1040         graph->deterministicEntry();
1041
1042         /*
1043          * All state construction is now complete.
1044          */
1045
1046         /* Transfer global error actions. */
1047         for ( StateList::Iter state = graph->stateList; state.lte(); state++ )
1048                 graph->transferErrorActions( state, 0 );
1049
1050         removeActionDups( graph );
1051
1052         /* Remove unreachable states. There should be no dead end states. The
1053          * subtract and intersection operators are the only places where they may
1054          * be created and those operators clean them up. */
1055         graph->removeUnreachableStates();
1056
1057         /* No more fsm operations are to be done. Action ordering numbers are
1058          * no longer of use and will just hinder minimization. Clear them. */
1059         graph->nullActionKeys();
1060
1061         /* Transition priorities are no longer of use. We can clear them
1062          * because they will just hinder minimization as well. Clear them. */
1063         graph->clearAllPriorities();
1064
1065         if ( minimizeOpt != MinimizeNone ) {
1066                 /* Minimize here even if we minimized at every op. Now that function
1067                  * keys have been cleared we may get a more minimal fsm. */
1068                 switch ( minimizeLevel ) {
1069                         case MinimizeApprox:
1070                                 graph->minimizeApproximate();
1071                                 break;
1072                         case MinimizeStable:
1073                                 graph->minimizeStable();
1074                                 break;
1075                         case MinimizePartition1:
1076                                 graph->minimizePartition1();
1077                                 break;
1078                         case MinimizePartition2:
1079                                 graph->minimizePartition2();
1080                                 break;
1081                 }
1082         }
1083
1084         graph->compressTransitions();
1085
1086         return graph;
1087 }
1088
1089 void ParseData::printNameTree()
1090 {
1091         /* Print the name instance map. */
1092         for ( NameVect::Iter name = rootName->childVect; name.lte(); name++ )
1093                 printNameInst( *name, 0 );
1094
1095         cerr << "name index:" << endl;
1096         /* Show that the name index is correct. */
1097         for ( int ni = 0; ni < nextNameId; ni++ ) {
1098                 cerr << ni << ": ";
1099                 char *name = nameIndex[ni]->name;
1100                 cerr << ( name != 0 ? name : "<ANON>" ) << endl;
1101         }
1102 }
1103
1104 FsmAp *ParseData::makeSpecific( GraphDictEl *gdNode )
1105 {
1106         /* Build the name tree and supporting data structures. */
1107         makeNameTree( gdNode );
1108
1109         /* Resove name references from gdNode. */
1110         initNameWalk();
1111         gdNode->value->resolveNameRefs( this );
1112
1113         /* Do not resolve action references. Since we are not building the entire
1114          * graph there's a good chance that many name references will fail. This
1115          * is okay since generating part of the graph is usually only done when
1116          * inspecting the compiled machine. */
1117
1118         /* Same story for extern entry point references. */
1119
1120         /* Flag this case so that the XML code generator is aware that we haven't
1121          * looked up name references in actions. It can then avoid segfaulting. */
1122         generatingSectionSubset = true;
1123
1124         /* Just building the specified graph. */
1125         initNameWalk();
1126         FsmAp *mainGraph = makeInstance( gdNode );
1127
1128         return mainGraph;
1129 }
1130
1131 FsmAp *ParseData::makeAll()
1132 {
1133         /* Build the name tree and supporting data structures. */
1134         makeNameTree( 0 );
1135
1136         /* Resove name references in the tree. */
1137         initNameWalk();
1138         for ( GraphList::Iter glel = instanceList; glel.lte(); glel++ )
1139                 glel->value->resolveNameRefs( this );
1140
1141         /* Resolve action code name references. */
1142         resolveActionNameRefs();
1143
1144         /* Force name references to the top level instantiations. */
1145         for ( NameVect::Iter inst = rootName->childVect; inst.lte(); inst++ )
1146                 (*inst)->numRefs += 1;
1147
1148         FsmAp *mainGraph = 0;
1149         FsmAp **graphs = new FsmAp*[instanceList.length()];
1150         int numOthers = 0;
1151
1152         /* Make all the instantiations, we know that main exists in this list. */
1153         initNameWalk();
1154         for ( GraphList::Iter glel = instanceList; glel.lte();  glel++ ) {
1155                 if ( strcmp( glel->key, mainMachine ) == 0 ) {
1156                         /* Main graph is always instantiated. */
1157                         mainGraph = makeInstance( glel );
1158                 }
1159                 else {
1160                         /* Instantiate and store in others array. */
1161                         graphs[numOthers++] = makeInstance( glel );
1162                 }
1163         }
1164
1165         if ( mainGraph == 0 )
1166                 mainGraph = graphs[--numOthers];
1167
1168         if ( numOthers > 0 ) {
1169                 /* Add all the other graphs into main. */
1170                 mainGraph->globOp( graphs, numOthers );
1171         }
1172
1173         delete[] graphs;
1174         return mainGraph;
1175 }
1176
1177 void ParseData::analyzeAction( Action *action, InlineList *inlineList )
1178 {
1179         /* FIXME: Actions used as conditions should be very constrained. */
1180         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
1181                 if ( item->type == InlineItem::Call || item->type == InlineItem::CallExpr )
1182                         action->anyCall = true;
1183
1184                 /* Need to recurse into longest match items. */
1185                 if ( item->type == InlineItem::LmSwitch ) {
1186                         LongestMatch *lm = item->longestMatch;
1187                         for ( LmPartList::Iter lmi = *lm->longestMatchList; lmi.lte(); lmi++ ) {
1188                                 if ( lmi->action != 0 )
1189                                         analyzeAction( action, lmi->action->inlineList );
1190                         }
1191                 }
1192
1193                 if ( item->type == InlineItem::LmOnLast ||
1194                                 item->type == InlineItem::LmOnNext ||
1195                                 item->type == InlineItem::LmOnLagBehind )
1196                 {
1197                         LongestMatchPart *lmi = item->longestMatchPart;
1198                         if ( lmi->action != 0 )
1199                                 analyzeAction( action, lmi->action->inlineList );
1200                 }
1201
1202                 if ( item->children != 0 )
1203                         analyzeAction( action, item->children );
1204         }
1205 }
1206
1207
1208 /* Check actions for bad uses of fsm directives. We don't go inside longest
1209  * match items in actions created by ragel, since we just want the user
1210  * actions. */
1211 void ParseData::checkInlineList( Action *act, InlineList *inlineList )
1212 {
1213         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
1214                 /* EOF checks. */
1215                 if ( act->numEofRefs > 0 ) {
1216                         switch ( item->type ) {
1217                         case InlineItem::PChar:
1218                                 error(item->loc) << "pointer to current element does not exist in "
1219                                                 "EOF action code" << endl;
1220                                 break;
1221                         case InlineItem::Char:
1222                                 error(item->loc) << "current element does not exist in "
1223                                                 "EOF action code" << endl;
1224                                 break;
1225                         case InlineItem::Hold:
1226                                 error(item->loc) << "changing the current element not possible in "
1227                                                 "EOF action code" << endl;
1228                                 break;
1229                         case InlineItem::Exec:
1230                                 error(item->loc) << "changing the current element not possible in "
1231                                                 "EOF action code" << endl;
1232                                 break;
1233                         case InlineItem::Goto: case InlineItem::Call:
1234                         case InlineItem::Next: case InlineItem::GotoExpr:
1235                         case InlineItem::CallExpr: case InlineItem::NextExpr:
1236                         case InlineItem::Ret:
1237                                 error(item->loc) << "changing the current state not possible in "
1238                                                 "EOF action code" << endl;
1239                                 break;
1240                         default:
1241                                 break;
1242                         }
1243                 }
1244
1245                 /* Recurse. */
1246                 if ( item->children != 0 )
1247                         checkInlineList( act, item->children );
1248         }
1249 }
1250
1251 void ParseData::checkAction( Action *action )
1252 {
1253         /* Check for actions with calls that are embedded within a longest match
1254          * machine. */
1255         if ( !action->isLmAction && action->numRefs() > 0 && action->anyCall ) {
1256                 for ( ActionRefs::Iter ar = action->actionRefs; ar.lte(); ar++ ) {
1257                         NameInst *check = *ar;
1258                         while ( check != 0 ) {
1259                                 if ( check->isLongestMatch ) {
1260                                         error(action->loc) << "within a scanner, fcall is permitted"
1261                                                 " only in pattern actions" << endl;
1262                                         break;
1263                                 }
1264                                 check = check->parent;
1265                         }
1266                 }
1267         }
1268
1269         checkInlineList( action, action->inlineList );
1270 }
1271
1272
1273 void ParseData::analyzeGraph( FsmAp *graph )
1274 {
1275         for ( ActionList::Iter act = actionList; act.lte(); act++ )
1276                 analyzeAction( act, act->inlineList );
1277
1278         for ( StateList::Iter st = graph->stateList; st.lte(); st++ ) {
1279                 /* The transition list. */
1280                 for ( TransList::Iter trans = st->outList; trans.lte(); trans++ ) {
1281                         for ( ActionTable::Iter at = trans->actionTable; at.lte(); at++ )
1282                                 at->value->numTransRefs += 1;
1283                 }
1284
1285                 for ( ActionTable::Iter at = st->toStateActionTable; at.lte(); at++ )
1286                         at->value->numToStateRefs += 1;
1287
1288                 for ( ActionTable::Iter at = st->fromStateActionTable; at.lte(); at++ )
1289                         at->value->numFromStateRefs += 1;
1290
1291                 for ( ActionTable::Iter at = st->eofActionTable; at.lte(); at++ )
1292                         at->value->numEofRefs += 1;
1293
1294                 for ( StateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
1295                         for ( CondSet::Iter sci = sc->condSpace->condSet; sci.lte(); sci++ )
1296                                 (*sci)->numCondRefs += 1;
1297                 }
1298         }
1299
1300         /* Checks for bad usage of directives in action code. */
1301         for ( ActionList::Iter act = actionList; act.lte(); act++ )
1302                 checkAction( act );
1303 }
1304
1305 void ParseData::makeExportsNameTree()
1306 {
1307         /* Make a name tree for the exports. */
1308         initExportsNameWalk();
1309
1310         /* First make the name tree. */
1311         for ( GraphDict::Iter gdel = graphDict; gdel.lte(); gdel++ ) {
1312                 if ( gdel->value->isExport ) {
1313                         /* Recurse on the instance. */
1314                         gdel->value->makeNameTree( gdel->loc, this );
1315                 }
1316         }
1317 }
1318
1319 void ParseData::makeExports()
1320 {
1321         makeExportsNameTree();
1322
1323         /* Resove name references in the tree. */
1324         initExportsNameWalk();
1325         for ( GraphDict::Iter gdel = graphDict; gdel.lte(); gdel++ ) {
1326                 if ( gdel->value->isExport )
1327                         gdel->value->resolveNameRefs( this );
1328         }
1329
1330         /* Make all the instantiations, we know that main exists in this list. */
1331         initExportsNameWalk();
1332         for ( GraphDict::Iter gdel = graphDict; gdel.lte();  gdel++ ) {
1333                 /* Check if this var def is an export. */
1334                 if ( gdel->value->isExport ) {
1335                         /* Build the graph from a walk of the parse tree. */
1336                         FsmAp *graph = gdel->value->walk( this );
1337
1338                         /* Build the graph from a walk of the parse tree. */
1339                         if ( !graph->checkSingleCharMachine() ) {
1340                                 error(gdel->loc) << "bad export machine, must define "
1341                                                 "a single character" << endl;
1342                         }
1343                         else {
1344                                 /* Safe to extract the key and declare the export. */
1345                                 Key exportKey = graph->startState->outList.head->lowKey;
1346                                 exportList.append( new Export( gdel->value->name, exportKey ) );
1347                         }
1348                 }
1349         }
1350
1351 }
1352
1353 void ParseData::prepareMachineGen( GraphDictEl *graphDictEl )
1354 {
1355         beginProcessing();
1356         initKeyOps();
1357         makeRootNames();
1358         initLongestMatchData();
1359
1360         /* Make the graph, do minimization. */
1361         if ( graphDictEl == 0 )
1362                 sectionGraph = makeAll();
1363         else
1364                 sectionGraph = makeSpecific( graphDictEl );
1365
1366         /* Compute exports from the export definitions. */
1367         makeExports();
1368
1369         /* If any errors have occured in the input file then don't write anything. */
1370         if ( gblErrorCount > 0 )
1371                 return;
1372
1373         analyzeGraph( sectionGraph );
1374
1375         /* Depends on the graph analysis. */
1376         setLongestMatchData( sectionGraph );
1377
1378         /* Decide if an error state is necessary.
1379          *  1. There is an error transition
1380          *  2. There is a gap in the transitions
1381          *  3. The longest match operator requires it. */
1382         if ( lmRequiresErrorState || sectionGraph->hasErrorTrans() )
1383                 sectionGraph->errState = sectionGraph->addState();
1384
1385         /* State numbers need to be assigned such that all final states have a
1386          * larger state id number than all non-final states. This enables the
1387          * first_final mechanism to function correctly. We also want states to be
1388          * ordered in a predictable fashion. So we first apply a depth-first
1389          * search, then do a stable sort by final state status, then assign
1390          * numbers. */
1391
1392         sectionGraph->depthFirstOrdering();
1393         sectionGraph->sortStatesByFinal();
1394         sectionGraph->setStateNumbers( 0 );
1395 }
1396
1397 void ParseData::generateXML( ostream &out )
1398 {
1399         beginProcessing();
1400
1401         /* Make the generator. */
1402         XMLCodeGen codeGen( sectionName, this, sectionGraph, out );
1403
1404         /* Write out with it. */
1405         codeGen.writeXML();
1406
1407         if ( printStatistics ) {
1408                 cerr << "fsm name  : " << sectionName << endl;
1409                 cerr << "num states: " << sectionGraph->stateList.length() << endl;
1410                 cerr << endl;
1411         }
1412 }
1413
1414 /* Send eof to all parsers. */
1415 void terminateAllParsers( )
1416 {
1417         /* FIXME: a proper token is needed here. Suppose we should use the
1418          * location of EOF in the last file that the parser was referenced in. */
1419         InputLoc loc;
1420         loc.fileName = "<EOF>";
1421         loc.line = 0;
1422         loc.col = 0;
1423         for ( ParserDict::Iter pdel = parserDict; pdel.lte(); pdel++ )
1424                 pdel->value->token( loc, _eof, 0, 0 );
1425 }
1426
1427 void writeLanguage( std::ostream &out )
1428 {
1429         out << " lang=\"";
1430         switch ( hostLangType ) {
1431                 case CCode:    out << "C"; break;
1432                 case DCode:    out << "D"; break;
1433                 case JavaCode: out << "Java"; break;
1434                 case RubyCode: out << "Ruby"; break;
1435         }
1436         out << "\"";
1437
1438 }
1439
1440 void writeMachines( std::ostream &out, std::string hostData, char *inputFileName )
1441 {
1442         if ( machineSpec == 0 && machineName == 0 ) {
1443                 /* No machine spec or machine name given. Generate everything. */
1444                 for ( ParserDict::Iter parser = parserDict; parser.lte(); parser++ ) {
1445                         ParseData *pd = parser->value->pd;
1446                         if ( pd->instanceList.length() > 0 )
1447                                 pd->prepareMachineGen( 0 );
1448                 }
1449
1450                 if ( gblErrorCount == 0 ) {
1451                         out << "<ragel filename=\"" << inputFileName << "\"";
1452                         writeLanguage( out );
1453                         out << ">\n";
1454                         for ( ParserDict::Iter parser = parserDict; parser.lte(); parser++ ) {
1455                                 ParseData *pd = parser->value->pd;
1456                                 if ( pd->instanceList.length() > 0 )
1457                                         pd->generateXML( out );
1458                         }
1459                         out << hostData;
1460                         out << "</ragel>\n";
1461                 }
1462         }
1463         else if ( parserDict.length() > 0 ) {
1464                 /* There is either a machine spec or machine name given. */
1465                 ParseData *parseData = 0;
1466                 GraphDictEl *graphDictEl = 0;
1467
1468                 /* Traverse the sections, break out when we find a section/machine
1469                  * that matches the one specified. */
1470                 for ( ParserDict::Iter parser = parserDict; parser.lte(); parser++ ) {
1471                         ParseData *checkPd = parser->value->pd;
1472                         if ( machineSpec == 0 || strcmp( checkPd->sectionName, machineSpec ) == 0 ) {
1473                                 GraphDictEl *checkGdEl = 0;
1474                                 if ( machineName == 0 || (checkGdEl =
1475                                                 checkPd->graphDict.find( machineName )) != 0 )
1476                                 {
1477                                         /* Have a machine spec and/or machine name that matches
1478                                          * the -M/-S options. */
1479                                         parseData = checkPd;
1480                                         graphDictEl = checkGdEl;
1481                                         break;
1482                                 }
1483                         }
1484                 }
1485
1486                 if ( parseData == 0 )
1487                         error() << "could not locate machine specified with -S and/or -M" << endl;
1488                 else {
1489                         /* Section/Machine to emit was found. Prepare and emit it. */
1490                         parseData->prepareMachineGen( graphDictEl );
1491                         if ( gblErrorCount == 0 ) {
1492                                 out << "<ragel filename=\"" << inputFileName << "\"";
1493                                 writeLanguage( out );
1494                                 out << ">\n";
1495                                 parseData->generateXML( out );
1496                                 out << hostData;
1497                                 out << "</ragel>\n";
1498                         }
1499                 }
1500         }
1501 }