Tools/CodeTools/Source/Pccts/h/PCCTSAST.cpp

   1 /*
   2  * PCCTSAST.C
   3  *
   4  * SOFTWARE RIGHTS
   5  *
   6  * We reserve no LEGAL rights to SORCERER -- SORCERER is in the public
   7  * domain.  An individual or company may do whatever they wish with
   8  * source code distributed with SORCERER or the code generated by
   9  * SORCERER, including the incorporation of SORCERER, or its output, into
  10  * commerical software.
  11  *
  12  * We encourage users to develop software with SORCERER.  However, we do
  13  * ask that credit is given to us for developing SORCERER.  By "credit",
  14  * we mean that if you incorporate our source code into one of your
  15  * programs (commercial product, research project, or otherwise) that you
  16  * acknowledge this fact somewhere in the documentation, research report,
  17  * etc...  If you like SORCERER and have developed a nice tool with the
  18  * output, please mention that you developed it using SORCERER.  In
  19  * addition, we ask that this header remain intact in our source code.
  20  * As long as these guidelines are kept, we expect to continue enhancing
  21  * this system and expect to make other tools available as they are
  22  * completed.
  23  *
  24  * SORCERER 1.00B14 and ANTLR 1.33
  25  * Terence Parr
  26  * Parr Research Corporation
  27  * AHPCRC, University of Minnesota
  28  * 1992-2000
  29  */
  30
  31 #define ANTLR_SUPPORT_CODE
  32
  33 #include "pcctscfg.h"
  34
  35 #include "PCCTSAST.h"
  36 #include "pccts_stdarg.h"
  37
  38 PCCTS_NAMESPACE_STD
  39
  40 #include <ctype.h>
  41
  42 //#include "SList.h"
  43
  44                /* String Scanning/Parsing Stuff */
  45
  46 const char *PCCTS_AST::scan_token_tbl[] = {     /* MR20 const */
  47         "invalid",      /*      0 */
  48         "LPAREN",       /*      1 */
  49         "RPAREN",       /*      2 */
  50         "PERCENT",      /*      3 */
  51         "INT",          /*      4 */
  52         "COLON",        /*      5 */
  53         "POUND",        /*      6 */
  54         "PERIOD",       /*      7 */
  55 };
  56
  57 void PCCTS_AST::
  58 addChild(PCCTS_AST *t)
  59 {
  60         if ( t==NULL ) return;
  61         PCCTS_AST *s = down();
  62         if ( s!=NULL )
  63         {
  64                 while ( s->right()!=NULL ) s = s->right();
  65                 s->setRight(t);
  66         }
  67         else
  68                 this->setDown(t);
  69 }
  70
  71 void PCCTS_AST::
  72 lisp(FILE *f)
  73 {
  74         if ( down() != NULL ) /* MR23 */ printMessage(f," (");
  75         lisp_action(f);
  76         if ( down()!=NULL ) down()->lisp(f);
  77         if ( down() != NULL ) /* MR23 */ printMessage(f," )");
  78         if ( right()!=NULL ) right()->lisp(f);
  79 }
  80
  81 /* build a tree (root child1 child2 ... NULL)
  82  * If root is NULL, simply make the children siblings and return ptr
  83  * to 1st sibling (child1).  If root is not single node, return NULL.
  84  *
  85  * Siblings that are actually sibling lists themselves are handled
  86  * correctly.  For example #( NULL, #( NULL, A, B, C), D) results
  87  * in the tree ( NULL A B C D ).
  88  *
  89  * Requires at least two parameters with the last one being NULL.  If
  90  * both are NULL, return NULL.
  91  *
  92  * The down() and right() down/right pointers are used to make the tree.
  93  */
  94 PCCTS_AST *PCCTS_AST::
  95 make(PCCTS_AST *rt, ...)
  96 {
  97         va_list ap;
  98         register PCCTS_AST *child, *sibling=NULL, *tail=NULL /*MR23*/, *w;
  99         PCCTS_AST *root;
 100
 101         va_start(ap, rt);
 102         root = rt;
 103
 104         if ( root != NULL )
 105                 if ( root->down() != NULL ) return NULL;
 106         child = va_arg(ap, PCCTS_AST *);
 107         while ( child != NULL )
 108         {
 109                 /* find end of child */
 110                 for (w=child; w->right()!=NULL; w=w->right()) {;}
 111                 if ( sibling == NULL ) {sibling = child; tail = w;}
 112                 else {tail->setRight(child); tail = w;}
 113                 child = va_arg(ap, PCCTS_AST *);
 114         }
 115         if ( root==NULL ) root = sibling;
 116         else root->setDown(sibling);
 117         va_end(ap);
 118         return root;
 119 }
 120
 121 /* The following push and pop routines are only used by ast_find_all() */
 122
 123 void PCCTS_AST::
 124 _push(PCCTS_AST **st, int *sp, PCCTS_AST *e)
 125 {
 126         (*sp)--;
 127         require((*sp)>=0, "stack overflow");
 128         st[(*sp)] = e;
 129 }
 130
 131 PCCTS_AST *PCCTS_AST::
 132 _pop(PCCTS_AST **st, int *sp)
 133 {
 134         PCCTS_AST *e = st[*sp];
 135         (*sp)++;
 136         require((*sp)<=MaxTreeStackDepth, "stack underflow");
 137         return e;
 138 }
 139
 140 /* Find all occurrences of u in t.
 141  * 'cursor' must be initialized to 't'.  It eventually
 142  * returns NULL when no more occurrences of 'u' are found.
 143  */
 144 PCCTS_AST *PCCTS_AST::
 145 ast_find_all(PCCTS_AST *u, PCCTS_AST **cursor)
 146 {
 147         PCCTS_AST *sib;
 148         /*** static ***/ PCCTS_AST *template_stack[MaxTreeStackDepth];  /* MR23 Remove "static" */
 149         /*** static ***/ int tsp = MaxTreeStackDepth;                   /* MR23 Remove "static" */
 150
 151 ////static int nesting = 0;                                         /* MR23 Not referenced */
 152
 153         if ( *cursor == NULL ) return NULL;
 154         if ( *cursor!=this ) sib = *cursor;
 155         else {
 156                 /* else, first time--start at top of template 't' */
 157                 tsp = MaxTreeStackDepth;
 158                 sib = this;
 159                 /* bottom of stack is always a NULL--"cookie" indicates "done" */
 160                 _push(template_stack, &tsp, NULL);
 161         }
 162
 163 keep_looking:
 164         if ( sib==NULL )        /* hit end of sibling list */
 165         {
 166                 sib = _pop(template_stack, &tsp);
 167                 if ( sib == NULL ) { *cursor = NULL; return NULL; }
 168         }
 169
 170         if ( sib->type() != u->type() )
 171         {
 172                 /* look for another match */
 173                 if ( sib->down()!=NULL )
 174                 {
 175                         if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
 176                         sib=sib->down();
 177                         goto keep_looking;
 178                 }
 179                 /* nothing below to try, try next sibling */
 180                 sib=sib->right();
 181                 goto keep_looking;
 182         }
 183
 184         /* found a matching root node, try to match what's below */
 185         if ( match_partial(sib, u) )
 186         {
 187                 /* record sibling cursor so we can pick up next from there */
 188                 if ( sib->down()!=NULL )
 189                 {
 190                         if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
 191                         *cursor = sib->down();
 192                 }
 193                 else if ( sib->right()!=NULL ) *cursor = sib->right();
 194                 else *cursor = _pop(template_stack, &tsp);
 195                 return sib;
 196         }
 197
 198         /* no match, keep searching */
 199         if ( sib->down()!=NULL )
 200         {
 201                 if ( sib->right()!=NULL ) _push(template_stack, &tsp, sib->right());
 202                 sib=sib->down();
 203         }
 204         else sib = sib->right();        /* else, try to right if zip below */
 205         goto keep_looking;
 206 }
 207
 208 /* are two trees exactly alike? */
 209 int PCCTS_AST::
 210 match(PCCTS_AST *u)
 211 {
 212         PCCTS_AST *t = this;
 213         PCCTS_AST *sib;
 214
 215         if ( u==NULL ) return 0;
 216
 217         for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
 218         {
 219                 if ( sib->type() != u->type() ) return 0;
 220                 if ( sib->down()!=NULL )
 221                         if ( !sib->down()->match(u->down()) ) return 0;
 222         }
 223         return 1;
 224 }
 225
 226 /* Is 'u' a subtree of 't' beginning at the root? */
 227 int PCCTS_AST::
 228 match_partial(PCCTS_AST *t, PCCTS_AST *u)
 229 {
 230         PCCTS_AST *sib;
 231
 232         if ( u==NULL ) return 1;
 233         if ( t==NULL ) return 0; /* MR23 removed unreachable code */
 234
 235         for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
 236         {
 237                 if ( sib->type() != u->type() ) return 0;
 238                 if ( sib->down()!=NULL )
 239                         if ( !match_partial(sib->down(), u->down()) ) return 0;
 240         }
 241         return 1;
 242 }
 243
 244 #ifdef _MSC_VER  // MR23
 245 //Turn off "unreachable code" warning
 246 #pragma warning(disable : 4702)
 247 #endif
 248 /* Walk the template tree 't' (matching against 'this'), filling in the
 249  * 'labels' array, and setting 'n' according to how many labels were matched.
 250  */
 251 int PCCTS_AST::
 252 scanmatch(ScanAST *t, PCCTS_AST **labels[], int *n)
 253 {
 254         ScanAST *sib;
 255         PCCTS_AST *u = this;
 256
 257         if ( u==NULL ) return 0;
 258
 259         for (sib=t; sib!=NULL&&u!=NULL; sib=sib->right(), u=u->right())
 260         {
 261                 /* make sure tokens match; token of '0' means wildcard match */
 262                 if ( sib->type() != u->type() && sib->type()!=0 ) return 0;
 263                 /* we have a matched token here; set label pointers if exists */
 264                 if ( sib->label_num>0 )
 265                 {
 266                         require(labels!=NULL, "label found in template, but no array of labels");
 267                         (*n)++;
 268                         *(labels[sib->label_num-1]) = u;
 269                 }
 270                 /* match what's below if something there and current node is not wildcard */
 271                 if ( sib->down()!=NULL && sib->type()!=0 )
 272                 {
 273                         if ( sib->down()==NULL )
 274                         {
 275                                 if ( u->down()!=NULL )
 276                                         return 0;
 277                                 else
 278                                         return 1;
 279                         }
 280                         if ( !u->down()->scanmatch(sib->down(), labels, n) ) return 0;
 281                 }
 282         }
 283         return 1;
 284 }
 285 #ifdef _MSC_VER  // MR23
 286 #pragma warning(default : 4702)
 287 #endif
 288
 289 void PCCTS_AST::
 290 insert_after(PCCTS_AST *b)
 291 {
 292         PCCTS_AST *end;
 293         if ( b==NULL ) return;
 294         /* find end of b's child list */
 295         for (end=b; end->right()!=NULL; end=end->right()) {;}
 296         end->setRight(this->right());
 297         this->setRight(b);
 298 }
 299
 300 void PCCTS_AST::
 301 append(PCCTS_AST *b)
 302 {
 303         PCCTS_AST *end;
 304         require(b!=NULL, "append: NULL input tree");
 305         /* find end of child list */
 306         for (end=this; end->right()!=NULL; end=end->right()) {;}
 307         end->setRight(b);
 308 }
 309
 310 PCCTS_AST *PCCTS_AST::
 311 tail()
 312 {
 313         PCCTS_AST *end;
 314         /* find end of child list */
 315         for (end=this; end->right()!=NULL; end=end->right()) {;}
 316         return end;
 317 }
 318
 319 PCCTS_AST *PCCTS_AST::
 320 bottom()
 321 {
 322         PCCTS_AST *end;
 323         /* find end of child list */
 324         for (end=this; end->down()!=NULL; end=end->down()) {;}
 325         return end;
 326 }
 327
 328 PCCTS_AST *PCCTS_AST::
 329 cut_between(PCCTS_AST *a, PCCTS_AST *b)
 330 {
 331         PCCTS_AST *end, *ret;
 332         if (a==NULL||b==NULL) return NULL;
 333         /* find node pointing to b */
 334         for (end=a; end->right()!=NULL&&end->right()!=b; end=end->right())
 335                 {;}
 336         if (end->right()==NULL) return NULL; //ast_cut_between: a,b not connected
 337         end->setRight(NULL);    /* don't want it point to 'b' anymore */
 338         ret = a->right();
 339         a->setRight(b);
 340         return ret;
 341 }
 342
 343 #ifdef NOT_YET
 344 SList *PCCTS_AST::
 345 to_slist()
 346 {
 347         SList *list = new SList;
 348         PCCTS_AST *p;
 349
 350         for (p=this; p!=NULL; p=p->right())
 351         {
 352                 list->add(p);
 353         }
 354         return list;
 355 }
 356 #endif
 357
 358 void PCCTS_AST::
 359 tfree()
 360 {
 361         PCCTS_AST *t = this;
 362     if ( t->down()!=NULL ) t->down()->tfree();
 363     if ( t->right()!=NULL ) t->right()->tfree();
 364     delete t;
 365 }
 366
 367 int PCCTS_AST::
 368 nsiblings()
 369 {
 370         PCCTS_AST *t = this;
 371         int n=0;
 372
 373         while ( t!=NULL )
 374         {
 375                 n++;
 376                 t = t->right();
 377         }
 378         return n;
 379 }
 380
 381 PCCTS_AST *PCCTS_AST::
 382 sibling_index(int i)
 383 {
 384         PCCTS_AST *t = this;
 385         int j=1;
 386         require(i>0, "sibling_index: i<=0");
 387
 388         while ( t!=NULL )
 389         {
 390                 if ( j==i ) return t;
 391                 j++;
 392                 t = t->right();
 393         }
 394         return NULL;
 395 }
 396
 397 /* Assume this is a root node of a tree--
 398  * duplicate that node and what's below; ignore siblings of root node.
 399  */
 400
 401 // MR9 23-Sep-97 RJV
 402 // MR9
 403 // MR9 RJV: Original version only duplicated the node and down elements.
 404 // MR9      Made copies of the pointers to sibling.
 405 // MR9      Changed call "down()->deepCopy()" to "down()->deepCopyBushy()"
 406 // MR9
 407
 408 PCCTS_AST *PCCTS_AST::
 409 deepCopy()
 410 {
 411         PCCTS_AST *u = this->shallowCopy();
 412         if ( down()!=NULL ) u->setDown(down()->deepCopyBushy());
 413     u->setRight(NULL);
 414         return u;
 415 }
 416
 417 /* Copy all nodes including siblings of root. */
 418 PCCTS_AST *PCCTS_AST::
 419 deepCopyBushy()
 420 {
 421         PCCTS_AST *u = this->shallowCopy();
 422         /* copy the rest of the tree */
 423         if ( down()!=NULL ) u->setDown(down()->deepCopyBushy());
 424         if ( right()!=NULL ) u->setRight(right()->deepCopyBushy());
 425         return u;
 426 }
 427
 428 void PCCTS_AST::
 429 scanast_free(ScanAST *t)
 430 {
 431     if ( t == NULL ) return;
 432     scanast_free( t->down() );
 433     scanast_free( t->right() );
 434     free( (char *) t );                                                 // MR1
 435 }
 436
 437 /*
 438  * scan
 439  *
 440  * This function is like scanf(): it attempts to match a template
 441  * against an input tree.  A variable number of tree pointers
 442  * may be set according to the '%i' labels in the template string.
 443  * For example:
 444  *
 445  *   t->ast_scan("#( 6 #(5 %1:4 %2:3) #(1 %3:3 %4:3) )",
 446  *            &w, &x, &y, &z);
 447  *
 448  * Naturally, you'd want this converted from
 449  *
 450  *       t->ast_scan("#( RangeOp #(Minus %1:IConst %2:Var) #(Plus %3:Var %4Var) )",
 451  *                        &w, &x, &y, &z);
 452  *
 453  * by SORCERER.
 454  *
 455  * This function call must be done withing a SORCERER file because SORCERER
 456  * must convert the token references to the associated token number.
 457  *
 458  * This functions parses the template and creates trees which are then
 459  * matched against the input tree.  The labels are set as they are
 460  * encountered; hence, partial matches may leave some pointers set
 461  * and some NULL.  This routines initializes all argument pointers to NULL
 462  * at the beginning.
 463  *
 464  * This function returns the number of labels matched.
 465  */
 466 int PCCTS_AST::
 467 ast_scan(char *templ, ...)
 468 {
 469         va_list ap;
 470         ScanAST *tmpl;
 471         int n, i, found=0;
 472         PCCTS_AST ***label_ptrs=NULL;
 473
 474         va_start(ap, templ);
 475
 476         /* make a ScanAST tree out of the template */
 477         tmpl = stringparser_parse_scanast(templ, &n);
 478
 479         /* make an array out of the labels */
 480         if ( n>0 )
 481         {
 482                 label_ptrs = (PCCTS_AST ***) calloc(n, sizeof(PCCTS_AST **));
 483                 require(label_ptrs!=NULL, "scan: out of memory");
 484                 for (i=1; i<=n; i++)
 485                 {
 486                         label_ptrs[i-1] = va_arg(ap, PCCTS_AST **);
 487                         *(label_ptrs[i-1]) = NULL;
 488                 }
 489         }
 490
 491         /* match the input tree against the template */
 492         scanmatch(tmpl, label_ptrs, &found);
 493
 494         scanast_free(tmpl);
 495         free( (char *) label_ptrs);                                     // MR1
 496
 497         return found;
 498 }
 499
 500 ScanAST *PCCTS_AST::
 501 new_scanast(int tok)
 502 {
 503     ScanAST *p = (ScanAST *) calloc(1, sizeof(ScanAST));
 504 //
 505 //  7-Apr-97 133MR1
 506 //
 507     if ( p == NULL )
 508         panic("out of memory\n");                       // MR23
 509         p->_token = tok;
 510         return p;
 511 }
 512
 513 ScanAST *PCCTS_AST::
 514 stringparser_parse_scanast(char *templ, int *num_labels)
 515 {
 516         StringLexer lex;
 517         StringParser parser;
 518         ScanAST *t;
 519
 520         stringlexer_init(&lex, templ);
 521         stringparser_init(&parser, &lex);
 522         t = stringparser_parse_tree(&parser);
 523         *num_labels = parser.num_labels;
 524         return t;
 525 }
 526
 527 void PCCTS_AST::
 528 stringparser_match(StringParser *parser, int token)
 529 {
 530         if ( parser->token != token ) panic("bad tree in scan()");
 531 }
 532
 533 /*
 534  * Match a tree of the form:
 535  *              (root child1 child2 ... childn)
 536  * or,
 537  *              node
 538  *
 539  * where the elements are integers or labeled integers.
 540  */
 541 ScanAST *PCCTS_AST::
 542 stringparser_parse_tree(StringParser *parser)
 543 {
 544         ScanAST *t=NULL, *root, *child, *last=NULL /*MR23*/;
 545
 546         if ( parser->token != __POUND )
 547         {
 548                 return stringparser_parse_element(parser);
 549         }
 550         stringparser_match(parser,__POUND);
 551         parser->token = stringscan_gettok(parser->lexer);
 552         stringparser_match(parser,__LPAREN);
 553         parser->token = stringscan_gettok(parser->lexer);
 554         root = stringparser_parse_element(parser);
 555         while ( parser->token != __RPAREN )
 556         {
 557                 child = stringparser_parse_element(parser);
 558                 if ( t==NULL ) { t = child; last = t; }
 559                 else { last->_right = child; last = child; }
 560         }
 561         stringparser_match(parser,__RPAREN);
 562         parser->token = stringscan_gettok(parser->lexer);
 563         root->_down = t;
 564         return root;
 565 }
 566
 567 ScanAST *PCCTS_AST::
 568 stringparser_parse_element(StringParser *parser)
 569 {
 570         char ebuf[100];
 571         int label = 0;
 572
 573         if ( parser->token == __POUND )
 574         {
 575                 return stringparser_parse_tree(parser);
 576         }
 577         if ( parser->token == __PERCENT )
 578         {
 579                 parser->token = stringscan_gettok(parser->lexer);
 580                 stringparser_match(parser,__INT);
 581                 label = atoi(parser->lexer->text);
 582                 parser->num_labels++;
 583                 if ( label==0 ) panic("%%0 is an invalid label");
 584                 parser->token = stringscan_gettok(parser->lexer);
 585                 stringparser_match(parser,__COLON);
 586                 parser->token = stringscan_gettok(parser->lexer);
 587                 /* can label tokens and wildcards */
 588                 if ( parser->token != __INT && parser->token != __PERIOD )
 589                         panic("can only label tokens");
 590         }
 591         if ( parser->token == __INT )
 592         {
 593                 ScanAST *p = new_scanast(atoi(parser->lexer->text));
 594                 parser->token = stringscan_gettok(parser->lexer);
 595                 p->label_num = label;
 596                 return p;
 597         }
 598         if ( parser->token == __PERIOD )
 599         {
 600                 ScanAST *p = new_scanast(0);    /* token of 0 is wildcard */
 601                 parser->token = stringscan_gettok(parser->lexer);
 602                 p->label_num = label;
 603                 return p;
 604         }
 605         sprintf(ebuf, "mismatch token in scan(): %s", scan_token_str(parser->token));
 606         panic(ebuf);
 607         return NULL;
 608 }
 609
 610 void PCCTS_AST::
 611 stringparser_init(StringParser *parser, StringLexer *input)
 612 {
 613         parser->lexer = input;
 614         parser->token = stringscan_gettok(parser->lexer);
 615         parser->num_labels = 0;
 616 }
 617
 618 void PCCTS_AST::
 619 stringlexer_init(StringLexer *scanner, char *input)
 620 {
 621         scanner->text[0]='\0';
 622         scanner->input = input;
 623         scanner->p = input;
 624         stringscan_advance(scanner);
 625 }
 626
 627 void PCCTS_AST::
 628 stringscan_advance(StringLexer *scanner)
 629 {
 630         if ( *(scanner->p) == '\0' ) scanner->c = __StringScanEOF;
 631         scanner->c = *(scanner->p)++;
 632 }
 633
 634 int PCCTS_AST::
 635 stringscan_gettok(StringLexer *scanner)
 636 {
 637         char *index = &scanner->text[0];
 638         char ebuf[100]; /* MR23 Remove static */
 639
 640         while ( isspace(scanner->c) ) { stringscan_advance(scanner); }
 641         if ( isdigit(scanner->c) )
 642         {
 643                 int tok = __INT;
 644                 while ( isdigit(scanner->c) ) {
 645                         *index++ = (char) /* static_cast<char> */ (scanner->c);     // MR23
 646                         stringscan_advance(scanner);
 647                 }
 648                 *index = '\0';
 649                 return tok;
 650         }
 651         switch ( scanner->c )
 652         {
 653                 case '#' : stringscan_advance(scanner); return __POUND;
 654                 case '(' : stringscan_advance(scanner); return __LPAREN;
 655                 case ')' : stringscan_advance(scanner); return __RPAREN;
 656                 case '%' : stringscan_advance(scanner); return __PERCENT;
 657                 case ':' : stringscan_advance(scanner); return __COLON;
 658                 case '.' : stringscan_advance(scanner); return __PERIOD;
 659                 case '\0' : return __StringScanEOF;
 660                 case __StringScanEOF : return __StringScanEOF;
 661                 default  :
 662                         sprintf(ebuf, "invalid char in scan: '%c'", scanner->c);
 663                         panic(ebuf);
 664         }
 665         return __StringScanEOF; // never reached
 666 }
 667
 668 const char *PCCTS_AST:: /* MR20 const */
 669 scan_token_str(int t)
 670 {
 671         if ( VALID_SCAN_TOKEN(t) ) return scan_token_tbl[t];
 672         else if ( t==__StringScanEOF ) return "<end-of-string>";
 673         else return "<invalid-token>";
 674 }
 675
 676 //MR23
 677 int PCCTS_AST::printMessage(FILE* pFile, const char* pFormat, ...)
 678 {
 679         va_list marker;
 680         va_start( marker, pFormat );
 681         int iRet = vfprintf(pFile, pFormat, marker);
 682         va_end( marker );
 683         return iRet;
 684 }