--- /dev/null
+/*\r
+ * pred.c -- source for predicate detection, manipulation\r
+ *\r
+ * SOFTWARE RIGHTS\r
+ *\r
+ * We reserve no LEGAL rights to the Purdue Compiler Construction Tool\r
+ * Set (PCCTS) -- PCCTS is in the public domain. An individual or\r
+ * company may do whatever they wish with source code distributed with\r
+ * PCCTS or the code generated by PCCTS, including the incorporation of\r
+ * PCCTS, or its output, into commerical software.\r
+ *\r
+ * We encourage users to develop software with PCCTS. However, we do ask\r
+ * that credit is given to us for developing PCCTS. By "credit",\r
+ * we mean that if you incorporate our source code into one of your\r
+ * programs (commercial product, research project, or otherwise) that you\r
+ * acknowledge this fact somewhere in the documentation, research report,\r
+ * etc... If you like PCCTS and have developed a nice tool with the\r
+ * output, please mention that you developed it using PCCTS. In\r
+ * addition, we ask that this header remain intact in our source code.\r
+ * As long as these guidelines are kept, we expect to continue enhancing\r
+ * this system and expect to make other tools available as they are\r
+ * completed.\r
+ *\r
+ * ANTLR 1.33\r
+ * Terence Parr\r
+ * Parr Research Corporation\r
+ * with Purdue University and AHPCRC, University of Minnesota\r
+ * 1989-2001\r
+ */\r
+\r
+#include <stdio.h>\r
+#include "pcctscfg.h"\r
+#include "set.h"\r
+#include "syn.h"\r
+#include "hash.h"\r
+#include "generic.h"\r
+#include "dlgdef.h"\r
+#include <ctype.h>\r
+\r
+#ifdef __USE_PROTOS\r
+static void complete_context_sets(RuleRefNode *, Predicate *);\r
+static void complete_context_trees(RuleRefNode *, Predicate *);\r
+#else\r
+static void complete_context_sets();\r
+static void complete_context_trees();\r
+#endif\r
+\r
+char *PRED_AND_LIST = "AND";\r
+char *PRED_OR_LIST = "OR";\r
+\r
+/*\r
+ * In C mode, return the largest constant integer found as the\r
+ * sole argument to LATEXT(i).\r
+ *\r
+ * In C++ mode, return the largest constant integer found as the\r
+ * sole argument to LT(i) given that the char before is nonalpha.\r
+ */\r
+\r
+int\r
+#ifdef __USE_PROTOS\r
+predicateLookaheadDepth(ActionNode *a)\r
+#else\r
+predicateLookaheadDepth(a)\r
+ActionNode *a;\r
+#endif\r
+{\r
+ int max_k=0;\r
+\r
+ if (a->predEntry != NULL) {\r
+ MR_pred_depth(a->predEntry->pred,&max_k);\r
+ goto PREDENTRY_EXIT;\r
+ }\r
+\r
+ if ( GenCC )\r
+ {\r
+ /* scan for LT(i) */\r
+ int k = 0;\r
+ char *p = a->action;\r
+ while ( p!=NULL )\r
+ {\r
+ p = strstr(p, "LT(");\r
+ if ( p!=NULL )\r
+ {\r
+ if ( p>=a->action && !isalpha(*(p-1)) )\r
+ {\r
+ k = atoi(p+strlen("LT("));\r
+ if ( k>max_k ) max_k=k;\r
+ }\r
+ p += strlen("LT(");\r
+ }\r
+ }\r
+ }\r
+ else {\r
+ /* scan for LATEXT(i) */\r
+ int k = 0;\r
+ char *p = a->action;\r
+ while ( p!=NULL )\r
+ {\r
+ p = strstr(p, "LATEXT(");\r
+ if ( p!=NULL )\r
+ {\r
+ p += strlen("LATEXT(");\r
+ k = atoi(p);\r
+ if ( k>max_k ) max_k=k;\r
+ }\r
+ }\r
+ }\r
+\r
+ if (max_k==0) {\r
+ max_k = 1; /* MR33 Badly designed if didn't set max_k when CLL_k = 1 */\r
+ if (CLL_k > 1) /* MR27 Don't warn if max(k,ck) == 1 */\r
+ {\r
+ if ( !a->frmwarned )\r
+ {\r
+ a->frmwarned = 1;\r
+ warnFL(eMsg1("predicate: %s missing, bad, or with i=0; assuming i=1",\r
+ GenCC?"LT(i)":"LATEXT(i)"),\r
+ FileStr[a->file], a->line);\r
+ }\r
+ }\r
+ }\r
+\r
+/* MR10 */ if ( max_k > CLL_k) {\r
+/* MR10 */ if ( !a->frmwarned )\r
+/* MR10 */ {\r
+/* MR10 */ a->frmwarned = 1;\r
+/* MR11 */ errFL(eMsgd2("predicate refers to lookahead token %d. Semantic lookahead is limited to max(k,ck)==%d",\r
+/* MR10 */ max_k,CLL_k),\r
+/* MR10 */ FileStr[a->file],a->line);\r
+/* MR10 */ if (max_k >= OutputLL_k) {\r
+/* MR10 */ if (!GenCC) {\r
+/* MR10 */ errFL(eMsgd(" the lookahead buffer size in C mode is %d token(s) (including the one just recognized)",\r
+/* MR10 */ OutputLL_k),\r
+/* MR10 */ FileStr[a->file],a->line);\r
+/* MR10 */ };\r
+/* MR10 */ };\r
+/* MR10 */ };\r
+/* MR10 */ max_k= CLL_k;\r
+/* MR10 */ };\r
+\r
+PREDENTRY_EXIT:\r
+ return max_k;\r
+}\r
+\r
+/* Find all predicates in a block of alternatives. DO NOT find predicates\r
+ * behind the block because that predicate could depend on things set in\r
+ * one of the nonoptional blocks\r
+ */\r
+\r
+Predicate *\r
+#ifdef __USE_PROTOS\r
+find_in_aSubBlk( Junction *alt )\r
+#else\r
+find_in_aSubBlk( alt )\r
+Junction *alt;\r
+#endif\r
+{\r
+ Predicate *a, *head=NULL, *tail=NULL, *root=NULL;\r
+ Junction *p = alt;\r
+\r
+ if (MRhoisting) {\r
+ return MR_find_in_aSubBlk(alt);\r
+ };\r
+ for (; p!=NULL; p=(Junction *)p->p2)\r
+ {\r
+ /* ignore empty alts */\r
+ if ( p->p1->ntype != nJunction ||\r
+ ((Junction *)p->p1)->jtype != EndBlk )\r
+ {\r
+ a = find_predicates(p->p1); /* get preds for this alt */\r
+ if ( a==NULL ) continue;\r
+\r
+ /* make an OR list of predicates */\r
+ if ( head==NULL )\r
+ {\r
+ root = new_pred();\r
+ root->expr = PRED_OR_LIST;\r
+ head = tail = a;\r
+ root->down = head;\r
+ }\r
+ else {\r
+ tail->right = a;\r
+ a->left = tail;\r
+ a->up = tail->up;\r
+ tail = a;\r
+ }\r
+ }\r
+ }\r
+\r
+ /* if just one pred, remove OR root */\r
+ if ( root!=NULL && root->down->right == NULL )\r
+ {\r
+ Predicate *d = root->down;\r
+ free( (char *) root);\r
+ return d;\r
+ }\r
+\r
+ return root;\r
+}\r
+\r
+Predicate *\r
+#ifdef __USE_PROTOS\r
+find_in_aOptBlk( Junction *alt )\r
+#else\r
+find_in_aOptBlk( alt )\r
+Junction *alt;\r
+#endif\r
+{\r
+ return find_in_aSubBlk( alt );\r
+}\r
+\r
+Predicate *\r
+#ifdef __USE_PROTOS\r
+find_in_aLoopBegin( Junction *alt )\r
+#else\r
+find_in_aLoopBegin( alt )\r
+Junction *alt;\r
+#endif\r
+{\r
+ return find_in_aSubBlk( (Junction *) alt->p1 ); /* get preds in alts */\r
+}\r
+\r
+Predicate *\r
+#ifdef __USE_PROTOS\r
+find_in_aPlusBlk( Junction *alt )\r
+#else\r
+find_in_aPlusBlk( alt )\r
+Junction *alt;\r
+#endif\r
+{\r
+ require(alt!=NULL&&alt->p2!=NULL, "invalid aPlusBlk");\r
+ return find_in_aSubBlk( alt );\r
+}\r
+\r
+/* Look for a predicate;\r
+ *\r
+ * Do not pass anything but Junction nodes; no Actions, Tokens, RuleRefs.\r
+ * This means that a "hoisting distance" of zero is the only distance\r
+ * allowable. Init actions are ignored.\r
+ *\r
+ * WARNING:\r
+ * Assumes no (..)? block after predicate for the moment.\r
+ * Does not check to see if pred is in production that can generate\r
+ * a sequence contained in the set of ambiguous tuples.\r
+ *\r
+ * Return the predicate found if any.\r
+ */\r
+\r
+\r
+Predicate *\r
+#ifdef __USE_PROTOS\r
+find_predicates( Node *alt )\r
+#else\r
+find_predicates( alt )\r
+Node *alt;\r
+#endif\r
+{\r
+#ifdef DBG_PRED\r
+ Junction *j;\r
+ RuleRefNode *r;\r
+ TokNode *t;\r
+#endif\r
+ Predicate *pred;\r
+\r
+ if ( alt==NULL ) return NULL;\r
+\r
+#ifdef DBG_PRED\r
+ switch ( alt->ntype )\r
+ {\r
+ case nJunction :\r
+ j = (Junction *) alt;\r
+ fprintf(stderr, "Junction(in %s)", j->rname);\r
+ switch ( j->jtype )\r
+ {\r
+ case aSubBlk :\r
+ fprintf(stderr,"aSubBlk\n");\r
+ break;\r
+ case aOptBlk :\r
+ fprintf(stderr,"aOptBlk\n");\r
+ break;\r
+ case aLoopBegin :\r
+ fprintf(stderr,"aLoopBeginBlk\n");\r
+ break;\r
+ case aLoopBlk :\r
+ fprintf(stderr,"aLoopBlk\n");\r
+ break;\r
+ case aPlusBlk :\r
+ fprintf(stderr,"aPlusBlk\n");\r
+ break;\r
+ case EndBlk :\r
+ fprintf(stderr,"EndBlk\n");\r
+ break;\r
+ case RuleBlk :\r
+ fprintf(stderr,"RuleBlk\n");\r
+ break;\r
+ case Generic :\r
+ fprintf(stderr,"Generic\n");\r
+ break;\r
+ case EndRule :\r
+ fprintf(stderr,"EndRule\n");\r
+ break;\r
+ }\r
+ break;\r
+ case nRuleRef :\r
+ r = (RuleRefNode *) alt;\r
+ fprintf(stderr, "RuleRef(in %s)\n", r->rname);\r
+ break;\r
+ case nToken :\r
+ t = (TokNode *) alt;\r
+ fprintf(stderr, "TokenNode(in %s)%s\n", t->rname, TokenString(t->token));\r
+ break;\r
+ case nAction :\r
+ fprintf(stderr, "Action\n");\r
+ break;\r
+ }\r
+#endif\r
+\r
+ switch ( alt->ntype )\r
+ {\r
+ case nJunction :\r
+ {\r
+ Predicate *a, *b;\r
+ Junction *p = (Junction *) alt; \r
+\r
+ /* lock nodes */\r
+ if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||\r
+ p->jtype==aPlusBlk || p->jtype==EndRule )\r
+ {\r
+ require(p->pred_lock!=NULL, "rJunc: lock array is NULL");\r
+ if ( p->pred_lock[1] )\r
+ {\r
+ return NULL;\r
+ }\r
+ p->pred_lock[1] = TRUE;\r
+ }\r
+\r
+ switch ( p->jtype )\r
+ {\r
+ case aSubBlk :\r
+ a = find_in_aSubBlk(p);\r
+ return a; /* nothing is visible past this guy */\r
+ case aOptBlk :\r
+ a = find_in_aOptBlk(p);\r
+ return a;\r
+ case aLoopBegin :\r
+ a = find_in_aLoopBegin(p);\r
+ return a;\r
+ case aLoopBlk :\r
+ a = find_in_aSubBlk(p);\r
+ p->pred_lock[1] = FALSE;\r
+ return a;\r
+ case aPlusBlk :\r
+ a = find_in_aPlusBlk(p);\r
+ p->pred_lock[1] = FALSE;\r
+ return a; /* nothing is visible past this guy */\r
+ case RuleBlk :\r
+ a = find_predicates(p->p1);\r
+ p->pred_lock[1] = FALSE;\r
+ return a;\r
+ case Generic :\r
+ a = find_predicates(p->p1);\r
+ b = find_predicates(p->p2);\r
+ if ( p->pred_lock!=NULL ) p->pred_lock[1] = FALSE;\r
+ if ( a==NULL ) return b;\r
+ if ( b==NULL ) return a;\r
+ /* otherwise OR the two preds together */\r
+ {\r
+ fatal_internal("hit unknown situation during predicate hoisting");\r
+ }\r
+ case EndBlk :\r
+ case EndRule : /* Find no predicates after a rule ref */\r
+ return NULL;\r
+ default:\r
+ fatal_internal("this cannot be printed\n");\r
+ break;\r
+ }\r
+ }\r
+ case nAction :\r
+ {\r
+ ActionNode *p = (ActionNode *) alt;\r
+ if ( p->noHoist) return NULL; /* MR12c */\r
+ if ( p->init_action ) return find_predicates(p->next);\r
+ if ( p->is_predicate )\r
+ {\r
+ Tree *t=NULL;\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "predicate: <<%s>>?\n", p->action);\r
+#endif\r
+ if ( p->guardpred!=NULL )\r
+ {\r
+ pred = predicate_dup(p->guardpred);\r
+ MR_guardPred_plainSet(p,pred); /* MR12c */\r
+ }\r
+ else\r
+ {\r
+ pred = new_pred();\r
+ pred->k = predicateLookaheadDepth(p);\r
+ pred->source = p;\r
+ pred->expr = p->action;\r
+ if ( HoistPredicateContext && pred->k > 1 )\r
+ {\r
+ /* MR30 No need to use first_item_is_guess_block_extra\r
+ since we know this is an action, not a (...)* or\r
+ (...)+ block.\r
+ */\r
+\r
+ if ( first_item_is_guess_block((Junction *)p->next) )\r
+ {\r
+ warnFL("cannot compute context of predicate in front of (..)? block",\r
+ FileStr[p->file], p->line);\r
+ }\r
+ else\r
+ {\r
+ ConstrainSearch = 0;\r
+/* MR11 */ if (p->ampersandPred != NULL) {\r
+/* MR11 */ TRAV(p,\r
+/* MR11 */ pred->k,\r
+/* MR11 */ &(pred->completionTree), t);\r
+/* MR11 */ } else {\r
+ TRAV(p->next,\r
+ pred->k,\r
+ &(pred->completionTree), t);\r
+ };\r
+ pred->tcontext = t;\r
+ MR_check_pred_too_long(pred,pred->completionTree);\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "LL(%d) context:", pred->k);\r
+ preorder(t);\r
+ fprintf(stderr, "\n");\r
+#endif\r
+ }\r
+ }\r
+ else if ( HoistPredicateContext && pred->k == 1 )\r
+ {\r
+ pred->scontext[1] = empty;\r
+ /* MR30 No need to use first_item_is_guess_block_extra\r
+ since we know this is an action.\r
+ */\r
+ if ( first_item_is_guess_block((Junction *)p->next) )\r
+ {\r
+ warnFL("cannot compute context of predicate in front of (..)? block",\r
+ FileStr[p->file], p->line);\r
+ }\r
+ else\r
+ {\r
+ REACH((Junction *)p->next,\r
+ 1,\r
+ &(pred->completionSet),\r
+ pred->scontext[1]);\r
+ MR_check_pred_too_long(pred,pred->completionSet);\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "LL(1) context:");\r
+ s_fprT(stderr, pred->scontext[1]);\r
+ fprintf(stderr, "\n");\r
+#endif\r
+ }\r
+ }\r
+ }\r
+ {\r
+ Predicate *d = find_predicates(p->next);\r
+ Predicate *root;\r
+\r
+/* Warning: Doesn't seem like the up pointers will all be set correctly;\r
+ * TJP: that's ok, we're not using them now.\r
+ */\r
+ if ( d!=NULL )\r
+ {\r
+ root = new_pred();\r
+ root->expr = PRED_AND_LIST;\r
+ root->down = pred;\r
+ pred->right = d;\r
+ pred->up = root;\r
+ d->left = pred;\r
+ d->up = pred->up;\r
+ return root;\r
+ }\r
+ }\r
+ return pred;\r
+ }\r
+ return NULL;\r
+ }\r
+ case nRuleRef :\r
+ {\r
+ Predicate *a;\r
+ RuleRefNode *p = (RuleRefNode *) alt;\r
+ Junction *r;\r
+ Junction *save_MR_RuleBlkWithHalt;\r
+\r
+ RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);\r
+ if ( q == NULL )\r
+ {\r
+ warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );\r
+ return NULL;\r
+ }\r
+ r = RulePtr[q->rulenum];\r
+ if ( r->pred_lock[1] )\r
+ {\r
+ /* infinite left-recursion; ignore 'cause LL sup 1 (k) analysis\r
+ * must have seen it earlier.\r
+ */\r
+ return NULL;\r
+ }\r
+\r
+ /* MR10 There should only be one halt set at a time. */\r
+ /* MR10 Life would have been easier with a global variable */\r
+ /* MR10 (at least for this particular need) */\r
+ /* MR10 Unset the old one and set the new one, later undo. */\r
+\r
+ require(r->end->halt == FALSE,"should only have one halt at a time");\r
+\r
+/* MR10 */ require(MR_RuleBlkWithHalt == NULL ||\r
+/* MR10 */ (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),\r
+/* MR10 */ "RuleBlkWithHalt->end not RuleBlk or does not have halt set");\r
+/* MR10 */ if (MR_RuleBlkWithHalt != NULL) {\r
+/* MR10 */ MR_RuleBlkWithHalt->end->halt=FALSE;\r
+/* MR10 */ };\r
+\r
+/*** fprintf(stderr,"\nSetting halt on junction #%d\n",r->end->seq); ***/\r
+\r
+ require(r->end->halt == FALSE,"rule->end->halt already set");\r
+\r
+ save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;\r
+\r
+/* MR10 */ MR_pointerStackPush(&MR_RuleBlkWithHaltStack,MR_RuleBlkWithHalt);\r
+/* MR10 */ MR_pointerStackPush(&MR_PredRuleRefStack,p);\r
+\r
+ r->end->halt = TRUE;\r
+/* MR10 */ MR_RuleBlkWithHalt=r;\r
+\r
+ a = find_predicates((Node *)r);\r
+\r
+ require(r->end->halt == TRUE,"rule->end->halt not set");\r
+ r->end->halt = FALSE;\r
+\r
+/* MR10 */ MR_pointerStackPop(&MR_PredRuleRefStack);\r
+/* MR10 */ MR_RuleBlkWithHalt=(Junction *) MR_pointerStackPop(&MR_RuleBlkWithHaltStack);\r
+\r
+ require (MR_RuleBlkWithHalt==save_MR_RuleBlkWithHalt,\r
+ "RuleBlkWithHaltStack not consistent");\r
+\r
+/* MR10 */ require(MR_RuleBlkWithHalt == NULL ||\r
+/* MR10 */ (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == FALSE),\r
+/* MR10 */ "RuleBlkWithHalt->end not RuleBlk or has no halt set");\r
+/* MR10 */ if (MR_RuleBlkWithHalt != NULL) {\r
+/* MR10 */ MR_RuleBlkWithHalt->end->halt=TRUE;\r
+/* MR10 */ };\r
+\r
+/*** fprintf(stderr,"\nRestoring halt on junction #%d\n",r->end->seq); ***/\r
+\r
+ if ( a==NULL ) return NULL;\r
+\r
+ /* attempt to compute the "local" FOLLOW just like in normal lookahead\r
+ * computation if needed\r
+ */\r
+\r
+ complete_context_sets(p,a);\r
+ complete_context_trees(p,a);\r
+\r
+/* MR10 */ MR_cleanup_pred_trees(a);\r
+\r
+ return a;\r
+ }\r
+ case nToken :\r
+ break;\r
+ }\r
+\r
+ return NULL;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate *MR_find_predicates_and_supp(Node *alt)\r
+#else\r
+Predicate *MR_find_predicates_and_supp(alt)\r
+ Node *alt;\r
+#endif\r
+{\r
+ Predicate *p;\r
+\r
+ p=find_predicates(alt);\r
+ p=MR_suppressK(alt,p);\r
+ return p;\r
+}\r
+\r
+Predicate *\r
+#ifdef __USE_PROTOS\r
+new_pred( void )\r
+#else\r
+new_pred( )\r
+#endif\r
+{\r
+ Predicate *p = (Predicate *) calloc(1,sizeof(Predicate)); /* MR10 */\r
+ require(p!=NULL, "new_pred: cannot alloc predicate");\r
+ p->scontext[0]=empty;\r
+ p->scontext[1]=empty;\r
+ p->completionTree=empty;\r
+ p->completionSet=empty;\r
+ p->plainSet=empty;\r
+ return p;\r
+}\r
+\r
+static void\r
+#ifdef __USE_PROTOS\r
+complete_context_sets( RuleRefNode *p, Predicate *a )\r
+#else\r
+complete_context_sets( p, a )\r
+RuleRefNode *p;\r
+Predicate *a;\r
+#endif\r
+{\r
+ set rk2, b;\r
+ int k2;\r
+\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "enter complete_context_sets\n");\r
+#endif\r
+ for (; a!=NULL; a=a->right)\r
+ {\r
+ if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )\r
+ {\r
+ complete_context_sets(p,a->down);\r
+ continue;\r
+ }\r
+ rk2 = b = empty;\r
+ while ( !set_nil(a->completionSet) )\r
+ {\r
+ k2 = set_int(a->completionSet);\r
+ set_rm(k2, a->completionSet);\r
+\r
+ REACH(p->next, k2, &rk2, b);\r
+ set_orin(&(a->scontext[1]), b);\r
+ set_free(b);\r
+ }\r
+\r
+ set_orin(&(a->completionSet), rk2);/* remember what we couldn't do */\r
+ set_free(rk2);\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "LL(1) context for %s(addr 0x%x) after ruleref:", a->expr, a);\r
+ s_fprT(stderr, a->scontext[1]);\r
+ fprintf(stderr, "\n");\r
+#endif\r
+/* complete_context_sets(p, a->down);*/\r
+ }\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "exit complete_context_sets\n");\r
+#endif\r
+}\r
+\r
+static void\r
+#ifdef __USE_PROTOS\r
+complete_context_trees( RuleRefNode *p, Predicate *a )\r
+#else\r
+complete_context_trees( p, a )\r
+RuleRefNode *p;\r
+Predicate *a;\r
+#endif\r
+{\r
+ set rk2;\r
+ int k2;\r
+ Tree *u;\r
+\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "enter complete_context_trees\n");\r
+#endif\r
+ for (; a!=NULL; a=a->right)\r
+ {\r
+ if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )\r
+ {\r
+ complete_context_trees(p, a->down);\r
+ continue;\r
+ }\r
+ rk2 = empty;\r
+\r
+ /* any k left to do? if so, link onto tree */\r
+ while ( !set_nil(a->completionTree) )\r
+ { \r
+ k2 = set_int(a->completionTree);\r
+ set_rm(k2, a->completionTree);\r
+ u = NULL;\r
+\r
+ TRAV(p->next, k2, &rk2, u);\r
+\r
+ /* any subtrees missing k2 tokens, add u onto end */\r
+ a->tcontext = tlink(a->tcontext, u, k2);\r
+ Tfree(u); /* MR10 */\r
+ }\r
+ set_orin(&(a->completionTree), rk2);/* remember what we couldn't do */\r
+ set_free(rk2);\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "LL(i<%d) context after ruleref:", LL_k);\r
+ preorder(a->tcontext);\r
+ fprintf(stderr, "\n");\r
+#endif\r
+/* complete_context_trees(p, a->down);*/\r
+ }\r
+#ifdef DBG_PRED\r
+ fprintf(stderr, "exit complete_context_trees\n");\r
+#endif\r
+}\r
+\r
+/* Walk a list of predicates and return the set of all tokens in scontext[1]'s */\r
+set\r
+#ifdef __USE_PROTOS\r
+covered_set( Predicate *p )\r
+#else\r
+covered_set( p )\r
+Predicate *p;\r
+#endif\r
+{\r
+ set a;\r
+\r
+ a = empty;\r
+ for (; p!=NULL; p=p->right)\r
+ {\r
+ if ( p->expr == PRED_AND_LIST || p->expr == PRED_OR_LIST )\r
+ {\r
+ set_orin(&a, covered_set(p->down));\r
+ continue;\r
+ }\r
+ set_orin(&a, p->scontext[1]);\r
+ set_orin(&a, covered_set(p->down));\r
+ }\r
+ return a;\r
+}\r
+\r
+/* MR10 predicate_free()\r
+ MR10 Don't free the leaf nodes since they are part of the action node\r
+*/\r
+\r
+#ifdef __USE_PROTOS\r
+void predicate_free(Predicate *p)\r
+#else\r
+void predicate_free(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ if (p == NULL) return;\r
+ predicate_free(p->right);\r
+ predicate_free(p->down);\r
+ if (p->cloned ||\r
+ p->source == NULL ||\r
+ p->source->guardpred == NULL ||\r
+ p->expr == PRED_AND_LIST ||\r
+ p->expr == PRED_OR_LIST) {\r
+ set_free(p->scontext[1]);\r
+ set_free(p->completionSet);\r
+ set_free(p->completionTree);\r
+ set_free(p->plainSet);\r
+ Tfree(p->tcontext);\r
+ free( (char *) p);\r
+ } else {\r
+ p->right=NULL;\r
+ p->down=NULL; /* MR13 *** debug */\r
+ };\r
+}\r
+\r
+/* MR10 predicate_dup() */\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate * predicate_dup_xxx(Predicate *p,int contextToo)\r
+#else\r
+Predicate * predicate_dup_xxx(p,contextToo)\r
+ Predicate *p;\r
+ int contextToo;\r
+#endif\r
+{\r
+ Predicate *q;\r
+\r
+ if (p == NULL) return NULL;\r
+ q=new_pred();\r
+ q->down=predicate_dup(p->down);\r
+ q->right=predicate_dup(p->right);\r
+\r
+ /*\r
+ don't replicate expr - it is read-only\r
+ and address comparison is used to look\r
+ for identical predicates.\r
+ */\r
+\r
+ q->expr=p->expr;\r
+ q->k=p->k;\r
+ q->source=p->source;\r
+ q->cloned=1;\r
+ q->ampersandStyle=p->ampersandStyle;\r
+ q->inverted=p->inverted;\r
+ q->predEntry=p->predEntry;\r
+ q->plainSet=set_dup(p->plainSet);\r
+\r
+ if (contextToo) {\r
+ q->tcontext=tdup(p->tcontext);\r
+ q->scontext[0]=set_dup(p->scontext[0]);\r
+ q->scontext[1]=set_dup(p->scontext[1]);\r
+ q->completionTree=set_dup(p->completionTree);\r
+ q->completionSet=set_dup(p->completionSet);\r
+ };\r
+\r
+ /* don't need to dup "redundant" */\r
+\r
+ return q;\r
+\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate * predicate_dup_without_context(Predicate *p)\r
+#else\r
+Predicate * predicate_dup_without_context(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ return predicate_dup_xxx(p,0);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate * predicate_dup(Predicate *p)\r
+#else\r
+Predicate * predicate_dup(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ return predicate_dup_xxx(p,1);\r
+}\r
+\r