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