ragel/parsedata.cpp

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