Tools/CodeTools/TianoTools/Pccts/antlr/pred.c

   1 /*
   2  * pred.c -- source for predicate detection, manipulation
   3  *
   4  * SOFTWARE RIGHTS
   5  *
   6  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
   7  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
   8  * company may do whatever they wish with source code distributed with
   9  * PCCTS or the code generated by PCCTS, including the incorporation of
  10  * PCCTS, or its output, into commerical software.
  11  *
  12  * We encourage users to develop software with PCCTS.  However, we do ask
  13  * that credit is given to us for developing PCCTS.  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 PCCTS and have developed a nice tool with the
  18  * output, please mention that you developed it using PCCTS.  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  * ANTLR 1.33
  25  * Terence Parr
  26  * Parr Research Corporation
  27  * with Purdue University and AHPCRC, University of Minnesota
  28  * 1989-2001
  29  */
  30
  31 #include <stdio.h>
  32 #include "pcctscfg.h"
  33 #include "set.h"
  34 #include "syn.h"
  35 #include "hash.h"
  36 #include "generic.h"
  37 #include "dlgdef.h"
  38 #include <ctype.h>
  39
  40 #ifdef __USE_PROTOS
  41 static void complete_context_sets(RuleRefNode *, Predicate *);
  42 static void complete_context_trees(RuleRefNode *, Predicate *);
  43 #else
  44 static void complete_context_sets();
  45 static void complete_context_trees();
  46 #endif
  47
  48 char *PRED_AND_LIST = "AND";
  49 char *PRED_OR_LIST = "OR";
  50
  51 /*
  52  * In C mode, return the largest constant integer found as the
  53  * sole argument to LATEXT(i).
  54  *
  55  * In C++ mode, return the largest constant integer found as the
  56  * sole argument to LT(i) given that the char before is nonalpha.
  57  */
  58
  59 int
  60 #ifdef __USE_PROTOS
  61 predicateLookaheadDepth(ActionNode *a)
  62 #else
  63 predicateLookaheadDepth(a)
  64 ActionNode *a;
  65 #endif
  66 {
  67         int     max_k=0;
  68
  69     if (a->predEntry != NULL) {
  70        MR_pred_depth(a->predEntry->pred,&max_k);
  71        goto PREDENTRY_EXIT;
  72     }
  73
  74         if ( GenCC )
  75         {
  76                 /* scan for LT(i) */
  77                 int k = 0;
  78                 char *p = a->action;
  79                 while ( p!=NULL )
  80                 {
  81                         p = strstr(p, "LT(");
  82                         if ( p!=NULL )
  83                         {
  84                                 if ( p>=a->action && !isalpha(*(p-1)) )
  85                                 {
  86                                         k = atoi(p+strlen("LT("));
  87                                         if ( k>max_k ) max_k=k;
  88                                 }
  89                                 p += strlen("LT(");
  90                         }
  91                 }
  92         }
  93         else {
  94                 /* scan for LATEXT(i) */
  95                 int k = 0;
  96                 char *p = a->action;
  97                 while ( p!=NULL )
  98                 {
  99                         p = strstr(p, "LATEXT(");
 100                         if ( p!=NULL )
 101                         {
 102                                 p += strlen("LATEXT(");
 103                                 k = atoi(p);
 104                                 if ( k>max_k ) max_k=k;
 105                         }
 106                 }
 107         }
 108
 109         if (max_k==0) {
 110                 max_k = 1;         /* MR33 Badly designed if didn't set max_k when CLL_k = 1 */
 111                 if (CLL_k > 1) /* MR27 Don't warn if max(k,ck) == 1 */
 112                 {
 113                         if ( !a->frmwarned )
 114                         {
 115                                 a->frmwarned = 1;
 116                                 warnFL(eMsg1("predicate: %s missing, bad, or with i=0; assuming i=1",
 117                                                          GenCC?"LT(i)":"LATEXT(i)"),
 118                                            FileStr[a->file], a->line);
 119                         }
 120                 }
 121         }
 122
 123 /* MR10 */    if ( max_k > CLL_k) {
 124 /* MR10 */              if ( !a->frmwarned )
 125 /* MR10 */        {
 126 /* MR10 */                      a->frmwarned = 1;
 127 /* MR11 */ errFL(eMsgd2("predicate refers to lookahead token %d. Semantic lookahead is limited to max(k,ck)==%d",
 128 /* MR10 */                        max_k,CLL_k),
 129 /* MR10 */                        FileStr[a->file],a->line);
 130 /* MR10 */          if (max_k >= OutputLL_k) {
 131 /* MR10 */            if (!GenCC) {
 132 /* MR10 */              errFL(eMsgd("    the lookahead buffer size in C mode is %d token(s) (including the one just recognized)",
 133 /* MR10 */                        OutputLL_k),
 134 /* MR10 */                        FileStr[a->file],a->line);
 135 /* MR10 */            };
 136 /* MR10 */          };
 137 /* MR10 */        };
 138 /* MR10 */        max_k= CLL_k;
 139 /* MR10 */    };
 140
 141 PREDENTRY_EXIT:
 142         return max_k;
 143 }
 144
 145 /* Find all predicates in a block of alternatives.  DO NOT find predicates
 146  * behind the block because that predicate could depend on things set in
 147  * one of the nonoptional blocks
 148  */
 149
 150 Predicate *
 151 #ifdef __USE_PROTOS
 152 find_in_aSubBlk( Junction *alt )
 153 #else
 154 find_in_aSubBlk( alt )
 155 Junction *alt;
 156 #endif
 157 {
 158         Predicate *a, *head=NULL, *tail=NULL, *root=NULL;
 159         Junction *p = alt;
 160
 161     if (MRhoisting) {
 162       return MR_find_in_aSubBlk(alt);
 163     };
 164         for (; p!=NULL; p=(Junction *)p->p2)
 165         {
 166                 /* ignore empty alts */
 167                 if ( p->p1->ntype != nJunction ||
 168                          ((Junction *)p->p1)->jtype != EndBlk )
 169                 {
 170                         a = find_predicates(p->p1);     /* get preds for this alt */
 171                         if ( a==NULL ) continue;
 172
 173                         /* make an OR list of predicates */
 174                         if ( head==NULL )
 175                         {
 176                                 root = new_pred();
 177                                 root->expr = PRED_OR_LIST;
 178                                 head = tail = a;
 179                                 root->down = head;
 180                         }
 181                         else {
 182                                 tail->right = a;
 183                                 a->left = tail;
 184                                 a->up = tail->up;
 185                                 tail = a;
 186                         }
 187                 }
 188         }
 189
 190         /* if just one pred, remove OR root */
 191         if ( root!=NULL && root->down->right == NULL )
 192         {
 193                 Predicate *d = root->down;
 194                 free( (char *) root);
 195                 return d;
 196         }
 197
 198         return root;
 199 }
 200
 201 Predicate *
 202 #ifdef __USE_PROTOS
 203 find_in_aOptBlk( Junction *alt )
 204 #else
 205 find_in_aOptBlk( alt )
 206 Junction *alt;
 207 #endif
 208 {
 209         return find_in_aSubBlk( alt );
 210 }
 211
 212 Predicate *
 213 #ifdef __USE_PROTOS
 214 find_in_aLoopBegin( Junction *alt )
 215 #else
 216 find_in_aLoopBegin( alt )
 217 Junction *alt;
 218 #endif
 219 {
 220         return find_in_aSubBlk( (Junction *) alt->p1 ); /* get preds in alts */
 221 }
 222
 223 Predicate *
 224 #ifdef __USE_PROTOS
 225 find_in_aPlusBlk( Junction *alt )
 226 #else
 227 find_in_aPlusBlk( alt )
 228 Junction *alt;
 229 #endif
 230 {
 231         require(alt!=NULL&&alt->p2!=NULL, "invalid aPlusBlk");
 232         return find_in_aSubBlk( alt );
 233 }
 234
 235 /* Look for a predicate;
 236  *
 237  * Do not pass anything but Junction nodes; no Actions, Tokens, RuleRefs.
 238  * This means that a "hoisting distance" of zero is the only distance
 239  * allowable.  Init actions are ignored.
 240  *
 241  * WARNING:
 242  *              Assumes no (..)? block after predicate for the moment.
 243  *              Does not check to see if pred is in production that can generate
 244  *                      a sequence contained in the set of ambiguous tuples.
 245  *
 246  * Return the predicate found if any.
 247  */
 248
 249
 250 Predicate *
 251 #ifdef __USE_PROTOS
 252 find_predicates( Node *alt )
 253 #else
 254 find_predicates( alt )
 255 Node *alt;
 256 #endif
 257 {
 258 #ifdef DBG_PRED
 259         Junction *j;
 260         RuleRefNode *r;
 261         TokNode *t;
 262 #endif
 263         Predicate *pred;
 264
 265         if ( alt==NULL ) return NULL;
 266
 267 #ifdef DBG_PRED
 268         switch ( alt->ntype )
 269         {
 270                 case nJunction :
 271                         j = (Junction *) alt;
 272                         fprintf(stderr, "Junction(in %s)", j->rname);
 273                         switch ( j->jtype )
 274                         {
 275                                 case aSubBlk :
 276                                         fprintf(stderr,"aSubBlk\n");
 277                                         break;
 278                                 case aOptBlk :
 279                                         fprintf(stderr,"aOptBlk\n");
 280                                         break;
 281                                 case aLoopBegin :
 282                                         fprintf(stderr,"aLoopBeginBlk\n");
 283                                         break;
 284                                 case aLoopBlk :
 285                                         fprintf(stderr,"aLoopBlk\n");
 286                                         break;
 287                                 case aPlusBlk :
 288                                         fprintf(stderr,"aPlusBlk\n");
 289                                         break;
 290                                 case EndBlk :
 291                                         fprintf(stderr,"EndBlk\n");
 292                                         break;
 293                                 case RuleBlk :
 294                                         fprintf(stderr,"RuleBlk\n");
 295                                         break;
 296                                 case Generic :
 297                                         fprintf(stderr,"Generic\n");
 298                                         break;
 299                                 case EndRule :
 300                                         fprintf(stderr,"EndRule\n");
 301                                         break;
 302                         }
 303                         break;
 304                 case nRuleRef :
 305                         r = (RuleRefNode *) alt;
 306                         fprintf(stderr, "RuleRef(in %s)\n", r->rname);
 307                         break;
 308                 case nToken :
 309                         t = (TokNode *) alt;
 310                         fprintf(stderr, "TokenNode(in %s)%s\n", t->rname, TokenString(t->token));
 311                         break;
 312                 case nAction :
 313                         fprintf(stderr, "Action\n");
 314                         break;
 315         }
 316 #endif
 317
 318         switch ( alt->ntype )
 319         {
 320                 case nJunction :
 321                 {
 322                         Predicate *a, *b;
 323                         Junction *p = (Junction *) alt;
 324
 325                         /* lock nodes */
 326                         if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||
 327                                  p->jtype==aPlusBlk || p->jtype==EndRule )
 328                         {
 329                                 require(p->pred_lock!=NULL, "rJunc: lock array is NULL");
 330                                 if ( p->pred_lock[1] )
 331                                 {
 332                                         return NULL;
 333                                 }
 334                                 p->pred_lock[1] = TRUE;
 335                         }
 336
 337                         switch ( p->jtype )
 338                         {
 339                                 case aSubBlk :
 340                                         a = find_in_aSubBlk(p);
 341                                         return a;       /* nothing is visible past this guy */
 342                                 case aOptBlk :
 343                                         a = find_in_aOptBlk(p);
 344                                         return a;
 345                                 case aLoopBegin :
 346                                         a = find_in_aLoopBegin(p);
 347                                         return a;
 348                                 case aLoopBlk :
 349                                         a = find_in_aSubBlk(p);
 350                                         p->pred_lock[1] = FALSE;
 351                                         return a;
 352                                 case aPlusBlk :
 353                                         a = find_in_aPlusBlk(p);
 354                                         p->pred_lock[1] = FALSE;
 355                                         return a;       /* nothing is visible past this guy */
 356                                 case RuleBlk :
 357                                         a = find_predicates(p->p1);
 358                                         p->pred_lock[1] = FALSE;
 359                                         return a;
 360                                 case Generic :
 361                                         a = find_predicates(p->p1);
 362                                         b = find_predicates(p->p2);
 363                                         if ( p->pred_lock!=NULL ) p->pred_lock[1] = FALSE;
 364                                         if ( a==NULL ) return b;
 365                                         if ( b==NULL ) return a;
 366                                         /* otherwise OR the two preds together */
 367                                         {
 368                                         fatal_internal("hit unknown situation during predicate hoisting");
 369                                         }
 370                                 case EndBlk :
 371                                 case EndRule :  /* Find no predicates after a rule ref */
 372                                         return NULL;
 373                                 default:
 374                                         fatal_internal("this cannot be printed\n");
 375                                         break;
 376                         }
 377                 }
 378                 case nAction :
 379                 {
 380                         ActionNode *p = (ActionNode *) alt;
 381             if ( p->noHoist) return NULL;                           /* MR12c */
 382                         if ( p->init_action ) return find_predicates(p->next);
 383                         if ( p->is_predicate )
 384                         {
 385                                 Tree *t=NULL;
 386 #ifdef DBG_PRED
 387                                 fprintf(stderr, "predicate: <<%s>>?\n", p->action);
 388 #endif
 389                                 if ( p->guardpred!=NULL )
 390                                 {
 391                                         pred = predicate_dup(p->guardpred);
 392                     MR_guardPred_plainSet(p,pred);                  /* MR12c */
 393                                 }
 394                                 else
 395                                 {
 396                                         pred = new_pred();
 397                                         pred->k = predicateLookaheadDepth(p);
 398                                         pred->source = p;
 399                                         pred->expr = p->action;
 400                                         if ( HoistPredicateContext && pred->k > 1 )
 401                                         {
 402                                                 /* MR30 No need to use first_item_is_guess_block_extra
 403                                                    since we know this is an action, not a (...)* or
 404                                                    (...)+ block.
 405                                                 */
 406
 407                                                 if ( first_item_is_guess_block((Junction *)p->next) )
 408                                                 {
 409                             warnFL("cannot compute context of predicate in front of (..)? block",
 410                             FileStr[p->file], p->line);
 411                                                 }
 412                                                 else
 413                                                 {
 414                                                         ConstrainSearch = 0;
 415 /* MR11 */                  if (p->ampersandPred != NULL) {
 416 /* MR11 */                                      TRAV(p,
 417 /* MR11 */                                                       pred->k,
 418 /* MR11 */                                               &(pred->completionTree), t);
 419 /* MR11 */                  } else {
 420                                                         TRAV(p->next,
 421                                                                  pred->k,
 422                                                                  &(pred->completionTree), t);
 423                             };
 424                                                         pred->tcontext = t;
 425                             MR_check_pred_too_long(pred,pred->completionTree);
 426 #ifdef DBG_PRED
 427                                                         fprintf(stderr, "LL(%d) context:", pred->k);
 428                                                         preorder(t);
 429                                                         fprintf(stderr, "\n");
 430 #endif
 431                                                 }
 432                                         }
 433                                         else if ( HoistPredicateContext && pred->k == 1 )
 434                                         {
 435                                                 pred->scontext[1] = empty;
 436                                                 /* MR30 No need to use first_item_is_guess_block_extra
 437                                                    since we know this is an action.
 438                                                 */
 439                                                 if ( first_item_is_guess_block((Junction *)p->next) )
 440                                                 {
 441                         warnFL("cannot compute context of predicate in front of (..)? block",
 442                                              FileStr[p->file], p->line);
 443                                                 }
 444                                                 else
 445                                                 {
 446                                                         REACH((Junction *)p->next,
 447                                                                   1,
 448                                                                   &(pred->completionSet),
 449                                                                   pred->scontext[1]);
 450                             MR_check_pred_too_long(pred,pred->completionSet);
 451 #ifdef DBG_PRED
 452                                                         fprintf(stderr, "LL(1) context:");
 453                                                         s_fprT(stderr, pred->scontext[1]);
 454                                                         fprintf(stderr, "\n");
 455 #endif
 456                                                 }
 457                                         }
 458                                 }
 459                                 {
 460                                         Predicate  *d = find_predicates(p->next);
 461                     Predicate  *root;
 462
 463 /* Warning: Doesn't seem like the up pointers will all be set correctly;
 464  * TJP: that's ok, we're not using them now.
 465  */
 466                                         if ( d!=NULL )
 467                                         {
 468                                                 root = new_pred();
 469                                                 root->expr = PRED_AND_LIST;
 470                                                 root->down = pred;
 471                                                 pred->right = d;
 472                                                 pred->up = root;
 473                                                 d->left = pred;
 474                                                 d->up = pred->up;
 475                                                 return root;
 476                                         }
 477                                 }
 478                                 return pred;
 479                         }
 480                         return NULL;
 481                 }
 482                 case nRuleRef :
 483                 {
 484                         Predicate   *a;
 485                         RuleRefNode *p = (RuleRefNode *) alt;
 486                         Junction    *r;
 487             Junction    *save_MR_RuleBlkWithHalt;
 488
 489                         RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);
 490                         if ( q == NULL )
 491                         {
 492                                 warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );
 493                                 return NULL;
 494                         }
 495                         r = RulePtr[q->rulenum];
 496                         if ( r->pred_lock[1] )
 497                         {
 498                                 /* infinite left-recursion; ignore 'cause LL sup 1 (k) analysis
 499                                  * must have seen it earlier.
 500                                  */
 501                                 return NULL;
 502                         }
 503
 504             /* MR10 There should only be one halt set at a time.        */
 505             /* MR10 Life would have been easier with a global variable  */
 506             /* MR10    (at least for this particular need)              */
 507             /* MR10 Unset the old one and set the new one, later undo.  */
 508
 509             require(r->end->halt == FALSE,"should only have one halt at a time");
 510
 511 /* MR10 */  require(MR_RuleBlkWithHalt == NULL ||
 512 /* MR10 */          (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
 513 /* MR10 */             "RuleBlkWithHalt->end not RuleBlk or does not have halt set");
 514 /* MR10 */  if (MR_RuleBlkWithHalt != NULL) {
 515 /* MR10 */    MR_RuleBlkWithHalt->end->halt=FALSE;
 516 /* MR10 */  };
 517
 518 /***        fprintf(stderr,"\nSetting halt on junction #%d\n",r->end->seq);     ***/
 519
 520             require(r->end->halt == FALSE,"rule->end->halt already set");
 521
 522             save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;
 523
 524 /* MR10 */  MR_pointerStackPush(&MR_RuleBlkWithHaltStack,MR_RuleBlkWithHalt);
 525 /* MR10 */  MR_pointerStackPush(&MR_PredRuleRefStack,p);
 526
 527                         r->end->halt = TRUE;
 528 /* MR10 */  MR_RuleBlkWithHalt=r;
 529
 530                         a = find_predicates((Node *)r);
 531
 532             require(r->end->halt == TRUE,"rule->end->halt not set");
 533             r->end->halt = FALSE;
 534
 535 /* MR10 */  MR_pointerStackPop(&MR_PredRuleRefStack);
 536 /* MR10 */  MR_RuleBlkWithHalt=(Junction *) MR_pointerStackPop(&MR_RuleBlkWithHaltStack);
 537
 538             require (MR_RuleBlkWithHalt==save_MR_RuleBlkWithHalt,
 539                     "RuleBlkWithHaltStack not consistent");
 540
 541 /* MR10 */  require(MR_RuleBlkWithHalt == NULL ||
 542 /* MR10 */          (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == FALSE),
 543 /* MR10 */             "RuleBlkWithHalt->end not RuleBlk or has no halt set");
 544 /* MR10 */  if (MR_RuleBlkWithHalt != NULL) {
 545 /* MR10 */    MR_RuleBlkWithHalt->end->halt=TRUE;
 546 /* MR10 */  };
 547
 548 /***        fprintf(stderr,"\nRestoring halt on junction #%d\n",r->end->seq);   ***/
 549
 550                         if ( a==NULL ) return NULL;
 551
 552                         /* attempt to compute the "local" FOLLOW just like in normal lookahead
 553                          * computation if needed
 554                          */
 555
 556                         complete_context_sets(p,a);
 557                         complete_context_trees(p,a);
 558
 559 /* MR10 */  MR_cleanup_pred_trees(a);
 560
 561                         return a;
 562                 }
 563                 case nToken :
 564                         break;
 565         }
 566
 567         return NULL;
 568 }
 569
 570 #ifdef __USE_PROTOS
 571 Predicate *MR_find_predicates_and_supp(Node *alt)
 572 #else
 573 Predicate *MR_find_predicates_and_supp(alt)
 574   Node      *alt;
 575 #endif
 576 {
 577     Predicate   *p;
 578
 579     p=find_predicates(alt);
 580     p=MR_suppressK(alt,p);
 581     return p;
 582 }
 583
 584 Predicate *
 585 #ifdef __USE_PROTOS
 586 new_pred( void )
 587 #else
 588 new_pred( )
 589 #endif
 590 {
 591         Predicate *p = (Predicate *) calloc(1,sizeof(Predicate)); /* MR10 */
 592         require(p!=NULL, "new_pred: cannot alloc predicate");
 593     p->scontext[0]=empty;
 594     p->scontext[1]=empty;
 595     p->completionTree=empty;
 596     p->completionSet=empty;
 597     p->plainSet=empty;
 598         return p;
 599 }
 600
 601 static void
 602 #ifdef __USE_PROTOS
 603 complete_context_sets( RuleRefNode *p, Predicate *a )
 604 #else
 605 complete_context_sets( p, a )
 606 RuleRefNode *p;
 607 Predicate *a;
 608 #endif
 609 {
 610         set rk2, b;
 611         int k2;
 612
 613 #ifdef DBG_PRED
 614         fprintf(stderr, "enter complete_context_sets\n");
 615 #endif
 616         for (; a!=NULL; a=a->right)
 617         {
 618                 if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )
 619                 {
 620                         complete_context_sets(p,a->down);
 621                         continue;
 622                 }
 623                 rk2 = b = empty;
 624                 while ( !set_nil(a->completionSet) )
 625                 {
 626                         k2 = set_int(a->completionSet);
 627                         set_rm(k2, a->completionSet);
 628
 629             REACH(p->next, k2, &rk2, b);
 630                         set_orin(&(a->scontext[1]), b);
 631                         set_free(b);
 632                 }
 633
 634                 set_orin(&(a->completionSet), rk2);/* remember what we couldn't do */
 635                 set_free(rk2);
 636 #ifdef DBG_PRED
 637                 fprintf(stderr, "LL(1) context for %s(addr 0x%x) after ruleref:", a->expr, a);
 638                 s_fprT(stderr, a->scontext[1]);
 639                 fprintf(stderr, "\n");
 640 #endif
 641 /*              complete_context_sets(p, a->down);*/
 642         }
 643 #ifdef DBG_PRED
 644         fprintf(stderr, "exit complete_context_sets\n");
 645 #endif
 646 }
 647
 648 static void
 649 #ifdef __USE_PROTOS
 650 complete_context_trees( RuleRefNode *p, Predicate *a )
 651 #else
 652 complete_context_trees( p, a )
 653 RuleRefNode *p;
 654 Predicate *a;
 655 #endif
 656 {
 657         set rk2;
 658         int k2;
 659         Tree *u;
 660
 661 #ifdef DBG_PRED
 662         fprintf(stderr, "enter complete_context_trees\n");
 663 #endif
 664         for (; a!=NULL; a=a->right)
 665         {
 666                 if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )
 667                 {
 668                         complete_context_trees(p, a->down);
 669                         continue;
 670                 }
 671                 rk2 = empty;
 672
 673                 /* any k left to do? if so, link onto tree */
 674                 while ( !set_nil(a->completionTree) )
 675                 {
 676                         k2 = set_int(a->completionTree);
 677                         set_rm(k2, a->completionTree);
 678                         u = NULL;
 679
 680             TRAV(p->next, k2, &rk2, u);
 681
 682                         /* any subtrees missing k2 tokens, add u onto end */
 683                         a->tcontext = tlink(a->tcontext, u, k2);
 684             Tfree(u);   /* MR10 */
 685                 }
 686                 set_orin(&(a->completionTree), rk2);/* remember what we couldn't do */
 687                 set_free(rk2);
 688 #ifdef DBG_PRED
 689                 fprintf(stderr, "LL(i<%d) context after ruleref:", LL_k);
 690                 preorder(a->tcontext);
 691                 fprintf(stderr, "\n");
 692 #endif
 693 /*              complete_context_trees(p, a->down);*/
 694         }
 695 #ifdef DBG_PRED
 696         fprintf(stderr, "exit complete_context_trees\n");
 697 #endif
 698 }
 699
 700 /* Walk a list of predicates and return the set of all tokens in scontext[1]'s */
 701 set
 702 #ifdef __USE_PROTOS
 703 covered_set( Predicate *p )
 704 #else
 705 covered_set( p )
 706 Predicate *p;
 707 #endif
 708 {
 709         set a;
 710
 711         a = empty;
 712         for (; p!=NULL; p=p->right)
 713         {
 714                 if ( p->expr == PRED_AND_LIST || p->expr == PRED_OR_LIST )
 715                 {
 716                         set_orin(&a, covered_set(p->down));
 717                         continue;
 718                 }
 719                 set_orin(&a, p->scontext[1]);
 720                 set_orin(&a, covered_set(p->down));
 721         }
 722         return a;
 723 }
 724
 725 /* MR10 predicate_free()
 726    MR10 Don't free the leaf nodes since they are part of the action node
 727 */
 728
 729 #ifdef __USE_PROTOS
 730 void predicate_free(Predicate *p)
 731 #else
 732 void predicate_free(p)
 733   Predicate     *p;
 734 #endif
 735 {
 736   if (p == NULL) return;
 737   predicate_free(p->right);
 738   predicate_free(p->down);
 739   if (p->cloned ||
 740       p->source == NULL ||
 741       p->source->guardpred == NULL ||
 742       p->expr == PRED_AND_LIST ||
 743       p->expr == PRED_OR_LIST) {
 744     set_free(p->scontext[1]);
 745     set_free(p->completionSet);
 746     set_free(p->completionTree);
 747     set_free(p->plainSet);
 748     Tfree(p->tcontext);
 749     free( (char *) p);
 750   } else {
 751     p->right=NULL;
 752     p->down=NULL;  /* MR13 *** debug */
 753   };
 754 }
 755
 756 /* MR10 predicate_dup() */
 757
 758 #ifdef __USE_PROTOS
 759 Predicate * predicate_dup_xxx(Predicate *p,int contextToo)
 760 #else
 761 Predicate * predicate_dup_xxx(p,contextToo)
 762   Predicate     *p;
 763   int           contextToo;
 764 #endif
 765 {
 766   Predicate     *q;
 767
 768   if (p == NULL) return NULL;
 769   q=new_pred();
 770   q->down=predicate_dup(p->down);
 771   q->right=predicate_dup(p->right);
 772
 773   /*
 774      don't replicate expr - it is read-only
 775      and address comparison is used to look
 776      for identical predicates.
 777   */
 778
 779   q->expr=p->expr;
 780   q->k=p->k;
 781   q->source=p->source;
 782   q->cloned=1;
 783   q->ampersandStyle=p->ampersandStyle;
 784   q->inverted=p->inverted;
 785   q->predEntry=p->predEntry;
 786   q->plainSet=set_dup(p->plainSet);
 787
 788   if (contextToo) {
 789     q->tcontext=tdup(p->tcontext);
 790     q->scontext[0]=set_dup(p->scontext[0]);
 791     q->scontext[1]=set_dup(p->scontext[1]);
 792     q->completionTree=set_dup(p->completionTree);
 793     q->completionSet=set_dup(p->completionSet);
 794   };
 795
 796   /* don't need to dup "redundant" */
 797
 798   return q;
 799
 800 }
 801
 802 #ifdef __USE_PROTOS
 803 Predicate * predicate_dup_without_context(Predicate *p)
 804 #else
 805 Predicate * predicate_dup_without_context(p)
 806   Predicate     *p;
 807 #endif
 808 {
 809   return predicate_dup_xxx(p,0);
 810 }
 811
 812 #ifdef __USE_PROTOS
 813 Predicate * predicate_dup(Predicate *p)
 814 #else
 815 Predicate * predicate_dup(p)
 816   Predicate     *p;
 817 #endif
 818 {
 819   return predicate_dup_xxx(p,1);
 820 }
 821