--- /dev/null
+/*\r
+ * mrhoist.c\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.33MR10\r
+ *\r
+ */\r
+\r
+#include <stdio.h>\r
+\r
+#include "pcctscfg.h"\r
+\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
+void dumppred(Predicate *);\r
+#else\r
+void dumppred();\r
+#endif\r
+\r
+/*\r
+ Try to determine whether predicate "first" is true for\r
+ all cases where "second" is true. Comparison takes place\r
+ without regard to context.\r
+ Assumes that predicate symbols have been expanded.\r
+ Assumes that there are no NAND or NOR nodes\r
+\r
+*/\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_secondPredicateUnreachable(Predicate *first,Predicate *second)\r
+#else\r
+int MR_secondPredicateUnreachable(first,second)\r
+ Predicate *first;\r
+ Predicate *second;\r
+#endif\r
+{\r
+ Predicate *f;\r
+ Predicate *s;\r
+\r
+ if (first == NULL) {\r
+ return 1;\r
+ } else if (second == NULL) {\r
+ return 0;\r
+ } else if (first->down == NULL && second->down == NULL) {\r
+ if (first->source == second->source &&\r
+ first->inverted == second->inverted) {\r
+ return 1; /* look identical - will never reach alt2 */\r
+ } else {\r
+ return 0; /* look different */\r
+ };\r
+ } else if (first->down == NULL && second->down != NULL) {\r
+\r
+ if (second->expr == PRED_AND_LIST) {\r
+\r
+ /* unreachable if first covers any child of second */\r
+\r
+ for (s=second->down; s != NULL; s=s->right) {\r
+ if (MR_secondPredicateUnreachable(first,s)) {\r
+ return 1;\r
+ };\r
+ };\r
+ return 0;\r
+ } else if (second->expr == PRED_OR_LIST) {\r
+\r
+ /* unreachable if first covers every child of second */\r
+\r
+ for (s=second->down; s != NULL; s=s->right) {\r
+ if (!MR_secondPredicateUnreachable(first,s)) {\r
+ return 0;\r
+ };\r
+ };\r
+ return 1;\r
+ } else {\r
+ require (0,"Illegal pred->expr");\r
+ return 0; /* MR20 Make compiler happy */\r
+ };\r
+ } else if (first->down != NULL && second->down == NULL) {\r
+ if (first->expr == PRED_AND_LIST) {\r
+\r
+ /* unreachable if every child of first covers second */\r
+\r
+ for (f=first->down; f != NULL; f=f->right) {\r
+ if (!MR_secondPredicateUnreachable(f,second)) {\r
+ return 0;\r
+ };\r
+ };\r
+ return 1;\r
+ } else if (first->expr == PRED_OR_LIST) {\r
+\r
+ /* unreachable if any child of first covers second */\r
+\r
+ for (f=first->down; f != NULL; f=f->right) {\r
+ if (MR_secondPredicateUnreachable(f,second)) {\r
+ return 1;\r
+ };\r
+ };\r
+ return 0;\r
+ } else {\r
+ require (0,"Illegal predicate->expr");\r
+ return 0; /* MR20 Make compiler happy */\r
+ };\r
+ } else {\r
+\r
+ if (first->expr == PRED_AND_LIST && second->expr == PRED_AND_LIST) {\r
+\r
+ /* unreachable if each child of first covers at least one child of second */\r
+\r
+ for (f=first->down; f != NULL ; f=f->right) {\r
+ for (s=second->down; s != NULL ; s=s->right) {\r
+ if (MR_secondPredicateUnreachable(f,s)) goto A_next_f;\r
+ };\r
+ return 0;\r
+A_next_f:\r
+ continue;\r
+ };\r
+ return 1;\r
+\r
+ } else if (first->expr == PRED_AND_LIST && second->expr == PRED_OR_LIST) {\r
+\r
+ /* unreachable if each child of first covers ALL of second's children */\r
+\r
+ for (f=first->down; f != NULL ; f=f->right) {\r
+ for (s=second->down; s != NULL ; s=s->right) {\r
+ if (!MR_secondPredicateUnreachable(f,s)) return 0;\r
+ };\r
+ };\r
+ return 1;\r
+\r
+ } else if (first->expr == PRED_OR_LIST && second->expr == PRED_AND_LIST) {\r
+\r
+ /* unreachable if any child of second is covered by any child of first */\r
+\r
+ for (f=first->down; f != NULL ; f=f->right) {\r
+ for (s=second->down; s != NULL ; s=s->right) {\r
+ if (MR_secondPredicateUnreachable(f,s)) return 1;\r
+ };\r
+ };\r
+ return 0;\r
+\r
+ } else if (first->expr == PRED_OR_LIST && second->expr == PRED_OR_LIST) {\r
+\r
+ /* unreachable if every child of second is covered by some child of first */\r
+\r
+ for (f=first->down; f != NULL ; f=f->right) {\r
+ for (s=second->down; s != NULL ; s=s->right) {\r
+ if (MR_secondPredicateUnreachable(f,s)) goto B_next_f;\r
+ };\r
+ return 0;\r
+B_next_f:\r
+ continue;\r
+ };\r
+ return 1;\r
+\r
+ } else {\r
+ require (0,"Illegal predicate->expr");\r
+ return 0; /* MR20 Make compiler happy */\r
+ };\r
+ };\r
+ return 0; /* MR20 MSVC 5.0 complains about missing return statement */\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_xxxIndent(FILE *f,int depth)\r
+#else\r
+void MR_xxxIndent(f,depth)\r
+ FILE *f;\r
+ int depth;\r
+#endif\r
+{\r
+ int i;\r
+\r
+ for (i=0; i<depth ; i++) {\r
+ fprintf(f," ");\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_stderrIndent(int depth)\r
+#else\r
+void MR_stderrIndent(depth)\r
+ int depth;\r
+#endif\r
+{\r
+ MR_xxxIndent(stderr,depth);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_outputIndent(int depth)\r
+#else\r
+void MR_outputIndent(depth)\r
+ int depth;\r
+#endif\r
+{\r
+ MR_xxxIndent(output,depth);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_set_reuse(set *s)\r
+#else\r
+void MR_set_reuse(s)\r
+ set *s;\r
+#endif\r
+{\r
+ set_free(*s);\r
+ *s=empty;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_dumpPredRuleRefStack(FILE *iounit,int indent)\r
+#else\r
+void MR_dumpPredRuleRefStack(iounit,indent)\r
+ FILE *iounit;\r
+ int indent;\r
+#endif\r
+{\r
+ int i;\r
+ int j;\r
+ int count=MR_PredRuleRefStack.count;\r
+ RuleRefNode *rrn=NULL;\r
+ Junction *lastOne;\r
+\r
+ if (count == 0) {\r
+ fprintf(iounit,"empty\n");\r
+ return;\r
+ };\r
+ for (i=0; i < count; i++) {\r
+ rrn=(RuleRefNode *) MR_PredRuleRefStack.data[i];\r
+ for (j=0; j<indent; j++) fprintf(iounit," ");\r
+ fprintf(iounit,"#%-2d in rule %s (line %d %s) to rule %s\n",\r
+ i,rrn->rname,rrn->line,FileStr[rrn->file],rrn->text);\r
+ };\r
+ lastOne=MR_ruleReferenced(rrn);\r
+ if (lastOne != NULL) {\r
+ for (j=0; j<indent; j++) fprintf(iounit," ");\r
+ fprintf(iounit,"#%-2d in rule %s (line %d %s)\n",\r
+ count,lastOne->rname,lastOne->line,FileStr[lastOne->file]);\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_dumpTreeF(FILE *f,int depth,Tree *tree,int across)\r
+#else\r
+void MR_dumpTreeF(f,depth,tree,across)\r
+ FILE *f;\r
+ Tree *tree;\r
+ int depth;\r
+ int across;\r
+#endif\r
+{\r
+ int newAcross=across;\r
+\r
+ if (tree == NULL ) return;\r
+ if (tree->down != NULL ) {\r
+ fprintf(output,"\n");\r
+ MR_outputIndent(depth);\r
+ fprintf(output, "(root =");\r
+ };\r
+ if (tree->token == ALT ) {\r
+ fprintf(output," %-16s","Alt");\r
+ } else if (tree->token==EpToken ) {\r
+ fprintf(output,"(%d)%13s",tree->v.rk," ");\r
+ } else {\r
+ fprintf(output," %-16s",TerminalString(tree->token));\r
+ };\r
+ if (tree->down != NULL) {\r
+ fprintf(output,"\n");\r
+ MR_outputIndent(depth+1);\r
+ MR_dumpTreeF(f,depth+1,tree->down,1);\r
+ newAcross=0;\r
+ fprintf(output,"\n");\r
+ MR_outputIndent(depth);\r
+ fprintf(output,")");\r
+ };\r
+ if (newAcross > 3) {\r
+ fprintf(output,"\n");\r
+ MR_outputIndent(depth);\r
+ newAcross=0;\r
+ };\r
+ MR_dumpTreeF(f,depth,tree->right,newAcross+1);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_dumpTreeX(int depth,Tree *tree,int across)\r
+#else\r
+void MR_dumpTreeX(depth,tree,across)\r
+ Tree *tree;\r
+ int depth;\r
+ int across;\r
+#endif\r
+{\r
+ MR_dumpTreeF(output,depth,tree,across);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_dumpTokenSet(FILE *f,int depth,set s)\r
+#else\r
+void MR_dumpTokenSet(f,depth,s)\r
+ FILE *f;\r
+ int depth;\r
+ set s;\r
+#endif\r
+{\r
+ int i;\r
+ int j;\r
+\r
+ unsigned *pdq;\r
+\r
+ if (set_nil(s)) {\r
+ fprintf(f,"\n");\r
+ MR_xxxIndent(f,depth+1);\r
+ fprintf(f,"nil\n");\r
+ return;\r
+ };\r
+\r
+ pdq=set_pdq(s);\r
+ require(pdq != NULL,"set_pdq failed");\r
+ i=0;\r
+ for (i=0 ; ; i=i+4) {\r
+ fprintf(f,"\n");\r
+ MR_xxxIndent(f,depth+1);\r
+ for (j=0; j < 4 ; j++) {\r
+ if (pdq[i+j] == nil) break;\r
+ fprintf(f," %-16s",TerminalString(pdq[i+j]));\r
+ };\r
+ if (pdq[i+j] == nil) break;\r
+ };\r
+ fprintf(f,"\n");\r
+ free( (char *) pdq);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_dumpPred1(int depth,Predicate *p,int withContext)\r
+#else\r
+void MR_dumpPred1(depth,p,withContext)\r
+ int depth;\r
+ Predicate *p;\r
+ int withContext;\r
+#endif\r
+{\r
+ unsigned k;\r
+\r
+ if (p == NULL) {\r
+ MR_outputIndent(depth);\r
+ fprintf(output,"The predicate is empty (or always true)\n\n");\r
+ return;\r
+ };\r
+ if (p->down != NULL) {\r
+ MR_outputIndent(depth);\r
+ if (p->inverted) {\r
+\r
+ /* MR14a Left out print expression in fprintf\r
+ Reported by Manuel Kessler (mlkessle@cip.physik.uni-wuerzburg.de)\r
+ */\r
+\r
+ if (p->expr == PRED_AND_LIST) fprintf(output,"%s NAND (not AND) expr\n\n",p->expr);\r
+ if (p->expr == PRED_OR_LIST) fprintf(output,"%s NOR (not OR) expr\n\n",p->expr);\r
+ } else {\r
+ fprintf(output,"%s expr\n\n",p->expr);\r
+ };\r
+ } else {\r
+ MR_outputIndent(depth);\r
+ fprintf(output,"pred %s <<%s>>?\n",\r
+ (p->inverted ? " *not*" : ""),\r
+ (p->expr == NULL ? "null expr" : p->expr));\r
+ MR_outputIndent(depth+1);\r
+ fprintf(output," ");\r
+ fprintf(output," depth=k=%d",p->k);\r
+ if (p->source != NULL && p->source->guardpred) {\r
+ fprintf(output," (\"=>\" guard)");\r
+ }\r
+ if (p->source != NULL && p->source->ampersandPred != NULL) {\r
+ fprintf(output," (\"&&\" guard)");\r
+ };\r
+ k=set_int(p->completionSet);\r
+ if (k != nil) {\r
+ fprintf(output," Incomplete Set at k=%d !",k);\r
+ };\r
+ k=set_int(p->completionTree);\r
+ if (k != nil) {\r
+ fprintf(output," Incomplete Tree at k=%d !",k);\r
+ };\r
+ if (p->source != NULL) {\r
+ fprintf(output," rule %s line %d %s",\r
+ p->source->rname,p->source->line,FileStr[p->source->file]);\r
+ };\r
+ fprintf(output,"\n");\r
+ if (withContext &&\r
+ (HoistPredicateContext ||\r
+ ! set_nil(p->scontext[1]) ||\r
+ p->tcontext != NULL)) {\r
+ if (p->k == 1) {\r
+ MR_outputIndent(depth+1);\r
+ fprintf(output,"set context: ");\r
+ MR_dumpTokenSet(output,depth+1,p->scontext[1]);\r
+ }\r
+ if (p->k != 1) {\r
+ MR_outputIndent(depth+1);\r
+ fprintf(output,"tree context:");\r
+ if (p->tcontext == NULL) {\r
+ fprintf(output," null");\r
+ } else {\r
+ MR_dumpTreeX(depth+2,p->tcontext,0);\r
+ };\r
+ fprintf(output,"\n");\r
+ };\r
+ };\r
+ fprintf(output,"\n");\r
+ };\r
+ if (p->down != NULL) {\r
+ MR_dumpPred1(depth+1,p->down,withContext);\r
+ };\r
+ if (p->right != NULL) {\r
+ MR_dumpPred1(depth,p->right,withContext);\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_dumpPred(Predicate *p,int withContext)\r
+#else\r
+void MR_dumpPred(p,withContext)\r
+ Predicate *p;\r
+ int withContext;\r
+#endif\r
+{\r
+ MR_dumpPred1(0,p,withContext);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Tree * MR_make_tree_from_set(set s)\r
+#else\r
+Tree * MR_make_tree_from_set(s)\r
+ set s;\r
+#endif\r
+{\r
+ Tree *t=NULL;\r
+ Tree *node;\r
+ Tree **tp=&t;\r
+ int i;\r
+\r
+ unsigned *pdq=set_pdq(s);\r
+\r
+ if (pdq != NULL) {\r
+ for (i=0 ; pdq[i] != nil ; i++) {\r
+ node=tnode( (int) pdq[i]);\r
+ *tp=node;\r
+ tp=&(node->right);\r
+ };\r
+ *tp=NULL;\r
+ free ( (char *) pdq);\r
+ };\r
+ return t;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_check_pred_too_long(Predicate *p,set completion)\r
+#else\r
+void MR_check_pred_too_long(p,completion)\r
+ Predicate *p;\r
+ set completion;\r
+#endif\r
+{\r
+ if (p != NULL &&\r
+ p->source != NULL &&\r
+ ! p->source->predTooLong) {\r
+ if ( !set_nil(completion)) {\r
+ p->source->predTooLong=1;\r
+warnFL("It is unusual (but ok) for a semantic predicate to test context past the end of its own rule",\r
+ FileStr[p->source->file],p->source->line);\r
+ };\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_predicate_context_completed(Predicate *p)\r
+#else\r
+int MR_predicate_context_completed(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ if (p == NULL) return 1;\r
+ if (p->expr != PRED_AND_LIST &&\r
+ p->expr != PRED_OR_LIST) {\r
+ if ( ! set_nil(p->completionSet)) return 0;\r
+ if ( ! set_nil(p->completionTree)) return 0;\r
+ };\r
+ return MR_predicate_context_completed(p->down) &\r
+ MR_predicate_context_completed(p->right);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Node * MR_advance(Node *n)\r
+#else\r
+Node * MR_advance(n)\r
+ Node *n;\r
+#endif\r
+{\r
+ if (n == NULL) return NULL;\r
+ switch (n->ntype) {\r
+ case nJunction: return ((Junction *)n)->p1;\r
+ case nToken: return ((TokNode *)n)->next;\r
+ case nRuleRef: return ((RuleRefNode *)n)->next;\r
+ case nAction: return ((ActionNode *)n)->next;\r
+ default: return NULL;\r
+ };\r
+ return NULL; /* MSVC 5.0 complains about missing return statement */\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Junction * MR_find_endRule(Node *n)\r
+#else\r
+Junction * MR_find_endRule(n)\r
+ Node *n;\r
+#endif\r
+{\r
+ Node *next;\r
+ if (n == NULL) return NULL;\r
+ for (next=n; next != NULL; next=MR_advance(next)) {\r
+ if (next->ntype == nJunction &&\r
+ ( (Junction *) next)->jtype == EndRule) {\r
+ break;\r
+ };\r
+ };\r
+ return (Junction *)next;\r
+}\r
+\r
+/*\r
+ Intersection: a branch which is shorter is chosen\r
+ over one which is longer: (A B C) intersect (A B) yields (A B).\r
+\r
+ AND: a branch which is longer is chosen over the one\r
+ which is shorter: (A B C) AND (A B) yields (A B C)\r
+\r
+*/\r
+\r
+#ifdef __USE_PROTOS\r
+Tree *MR_computeTreeIntersection(Tree *l,Tree *r)\r
+#else\r
+Tree *MR_computeTreeIntersection(l,r)\r
+ Tree *l;\r
+ Tree *r;\r
+#endif\r
+{\r
+ Tree *result=NULL;\r
+ Tree **tail;\r
+ Tree *p;\r
+ Tree *q;\r
+ Tree *match;\r
+\r
+ if (l == NULL || r == NULL) return NULL;\r
+ for (p=l; p != NULL; p=p->right) {\r
+ require(p->token != EpToken,"MR_computeTreeIntersection: p->EpToken unexpected\n");\r
+ require (p->token != ALT,"MR_computeTreeIntersection: p->ALT unexpected\n");\r
+ };\r
+ for (q=r; q != NULL; q=q->right) {\r
+ require(q->token != EpToken,"MR_computeTreeIntersection: q->EpToken unexpected\n");\r
+ require(q->token != ALT,"MR_computeTreeIntersection: q->ALT unexpected\n");\r
+ };\r
+\r
+ result=tnode(ALT);\r
+ tail=&(result->down);\r
+\r
+ for (p=l; p != NULL ; p=p->right) {\r
+ for (q=r; q != NULL ; q=q->right) {\r
+ if (p->token == q->token) {\r
+ match=tnode(p->token);\r
+ match->down=MR_computeTreeIntersection(p->down,q->down);\r
+ *tail=match;\r
+ tail=&(match->right);\r
+ };\r
+ };\r
+ };\r
+\r
+ *tail=NULL;\r
+ result=tshrink(result);\r
+ result=tflatten( result );\r
+ result=tleft_factor( result );\r
+ return result;\r
+}\r
+\r
+/* the predicates which are ANDed together have a common\r
+ context: they must all have common roots. Thus the\r
+ AND operation is more like an OR operation because\r
+ branches which are longer are grafted onto shorter\r
+ branches of the AND tree. For instance combining\r
+ (A B C) with (A B C D) gives (A B C D). There\r
+ should never be a case of (A B C) and (A B D) because\r
+ they have the same context.\r
+\r
+ Actually, this may not be true once one throws in\r
+ guard predicates which are defined by the user, not\r
+ the context.\r
+*/\r
+\r
+/* requires input trees to be in "canonical" format */\r
+\r
+#ifdef __USE_PROTOS\r
+Tree *MR_computeTreeAND(Tree *l,Tree *r)\r
+#else\r
+Tree *MR_computeTreeAND(l,r)\r
+ Tree *l;\r
+ Tree *r;\r
+#endif\r
+{\r
+ Tree *result=NULL;\r
+ Tree **tail;\r
+ Tree *p;\r
+ Tree *q;\r
+ Tree *match;\r
+\r
+ if (l == NULL) return tdup(r);\r
+ if (r == NULL) return tdup(l);\r
+\r
+ for (p=l; p != NULL; p=p->right) {\r
+/**** require(p->token != EpToken,"MR_computeTreeAND: p->EpToken unexpected\n"); ****/\r
+ require (p->token != ALT,"MR_computeTreeAND: p->ALT unexpected\n");\r
+ };\r
+ for (q=r; q != NULL; q=q->right) {\r
+/**** require(q->token != EpToken,"MR_computeTreeAND: q->EpToken unexpected\n"); ****/\r
+ require(q->token != ALT,"MR_computeTreeAND: q->ALT unexpected\n");\r
+ };\r
+\r
+ result=tnode(ALT);\r
+ tail=&(result->down);\r
+\r
+ for (p=l; p != NULL ; p=p->right) {\r
+ for (q=r; q != NULL ; q=q->right) {\r
+ if (p->token == q->token) {\r
+ match=tnode(p->token);\r
+ match->down=MR_computeTreeAND(p->down,q->down);\r
+ *tail=match;\r
+ tail=&(match->right);\r
+ };\r
+ };\r
+ };\r
+\r
+ *tail=NULL;\r
+ result=tshrink(result);\r
+ result=tflatten( result );\r
+ result=tleft_factor( result );\r
+ return result;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_union_plain_sets1(Predicate *p,set *theUnion)\r
+#else\r
+void MR_union_plain_sets1(p,theUnion)\r
+ Predicate *p;\r
+ set *theUnion;\r
+#endif\r
+{\r
+ if (p == NULL) return;\r
+ MR_union_plain_sets1(p->down,theUnion);\r
+ MR_union_plain_sets1(p->right,theUnion);\r
+ set_orin(theUnion,p->plainSet);\r
+ return;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+set MR_union_plain_sets(Predicate *p)\r
+#else\r
+set MR_union_plain_sets(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ set theUnion;\r
+\r
+ theUnion=empty;\r
+\r
+ MR_union_plain_sets1(p,&theUnion);\r
+ return theUnion;\r
+}\r
+\r
+/* does NOT left factor: do not want to merge\r
+ (A B) with (A) to get (A B)\r
+ in fact the opposite: (A B) with (A) gives (A)\r
+*/\r
+\r
+#ifdef __USE_PROTOS\r
+Tree *MR_compute_pred_tree_ctxXX(Predicate *p)\r
+#else\r
+Tree *MR_compute_pred_tree_ctxXX(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ Tree *result=NULL;\r
+ Predicate *q;\r
+ Tree *t;\r
+\r
+ if (p == NULL) return NULL;\r
+\r
+/* this appears strange: why do we OR the context\r
+ of and AND predicate ? It is because of the way\r
+ that predicates are evaluated: if the context is\r
+ wrong then it's the same as if the predicate was\r
+ true. That means that even when one leg of an\r
+ AND has unmatched context, if the other leg has\r
+ matched context and is true then the predicate\r
+ succeeds. It's only when all the legs have unmatched\r
+ context that this one can skip evaluation of the\r
+ predicates.\r
+*/\r
+ if (p->expr == PRED_OR_LIST ||\r
+ p->expr == PRED_AND_LIST) {\r
+ for (q=p->down; q != NULL ; q=q->right) {\r
+ t=MR_compute_pred_tree_ctxXX(q);\r
+ result=tappend(result,t);\r
+ t=NULL;\r
+ };\r
+\r
+ result=tshrink(result);\r
+ result=tflatten( result );\r
+\r
+/* does NOT left factor: do not want to merge\r
+ (A B) with (A) to get (A B)\r
+ in fact the opposite: (A B) with (A) gives (A)\r
+*/\r
+\r
+/**** result=tleft_factor( result ); ****/\r
+ return result;\r
+ };\r
+\r
+#if 0\r
+** if (p->expr == PRED_AND_LIST) {\r
+**\r
+** Predicate *l;\r
+** Predicate *r;\r
+** Tree *l1;\r
+** Tree *r1;\r
+** Tree *prevl1;\r
+**\r
+** l=p->down;\r
+** require (l->right != NULL,"MR_compute_pred_tree - AND has only one child");\r
+**\r
+**/* l1 and r1 should already be in "canonical" format */\r
+**\r
+** l1=MR_compute_pred_tree(l);\r
+** for (r=l->right; r != NULL; r=r->right) {\r
+** r1=MR_compute_pred_tree(r);\r
+** prevl1=l1;\r
+** l1=MR_computeTreeAND(l1,r1);\r
+** Tfree(r1);\r
+** Tfree(prevl1);\r
+** };\r
+**\r
+**/* result from computeTreeAND should be in "canonical" format */\r
+**\r
+** result=l1;\r
+**\r
+**/* result of MR_computeTreeAND should be in "canonical" format */\r
+**\r
+** return result;\r
+** };\r
+#endif\r
+\r
+ if (p->k == 1) {\r
+ result=MR_make_tree_from_set(p->scontext[1]);\r
+ } else {\r
+ result=tdup(p->tcontext);\r
+ result=MR_remove_epsilon_from_tree(result);\r
+ result=tshrink(result);\r
+ result=tflatten(result);\r
+ result=tleft_factor(result);\r
+ };\r
+ return result;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_pred_depth(Predicate *p,int *maxDepth)\r
+#else\r
+void MR_pred_depth(p,maxDepth)\r
+ Predicate *p;\r
+ int *maxDepth;\r
+#endif\r
+{\r
+ if (p == NULL) return;\r
+ if (p->expr != PRED_OR_LIST &&\r
+ p->expr != PRED_AND_LIST) {\r
+ if (p->k > *maxDepth) *maxDepth=p->k;\r
+ };\r
+ MR_pred_depth(p->down,maxDepth);\r
+ MR_pred_depth(p->right,maxDepth);\r
+}\r
+\r
+/* this computes the OR of all the contexts */\r
+\r
+#ifdef __USE_PROTOS\r
+set MR_compute_pred_set(Predicate *p)\r
+#else\r
+set MR_compute_pred_set(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ set result;\r
+ Predicate *q;\r
+\r
+ result=empty;\r
+\r
+ if (p == NULL) return empty;\r
+\r
+ if (p->expr == PRED_OR_LIST ||\r
+ p->expr == PRED_AND_LIST) { /* yes, I do mean PRED_AND_LIST ! */\r
+ /* remember: r1: (A)? => <<p>>? r2; */\r
+ /* r2: (B)? => <<q>>? r3; */\r
+ set t;\r
+\r
+ t=empty;\r
+ result=empty;\r
+\r
+ for (q=p->down; q != NULL; q=q->right) {\r
+ t=MR_compute_pred_set(q);\r
+ set_orin(&result,t);\r
+ set_free(t);\r
+ };\r
+ return result;\r
+ } else if (p->k > 1) {\r
+ return empty;\r
+ } else {\r
+ return set_dup(p->scontext[1]);\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+set MR_First(int ck,Junction *j,set *incomplete)\r
+#else\r
+set MR_First(ck,j,incomplete)\r
+ int ck;\r
+ Junction *j;\r
+ set *incomplete;\r
+#endif\r
+{\r
+ Junction *p;\r
+ set tokensUsed;\r
+\r
+ tokensUsed=empty;\r
+\r
+ require(j->ntype==nJunction, "MR_First: non junction passed");\r
+\r
+ p = analysis_point((Junction *)j->p1);\r
+\r
+ REACH(p,ck,incomplete,tokensUsed);\r
+\r
+ return tokensUsed;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_cleanup_pred_trees(Predicate *p)\r
+#else\r
+void MR_cleanup_pred_trees(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ Tree *t;\r
+\r
+ if (p == NULL) return;\r
+ if (p->expr != PRED_OR_LIST &&\r
+ p->expr != PRED_AND_LIST) {\r
+ t=p->tcontext;\r
+ t=tshrink(t);\r
+ t=tflatten(t);\r
+ t=tleft_factor(t);\r
+ p->tcontext=t;\r
+ };\r
+ MR_cleanup_pred_trees(p->down);\r
+ MR_cleanup_pred_trees(p->right);\r
+}\r
+\r
+/* does NOT return canonical tree */\r
+\r
+#ifdef __USE_PROTOS\r
+Tree * MR_remove_epsilon_from_tree(Tree *t)\r
+#else\r
+Tree * MR_remove_epsilon_from_tree(t)\r
+ Tree *t;\r
+#endif\r
+{\r
+ if (t == NULL) return NULL;\r
+\r
+ /* I think ALT can be ignored as a special case */\r
+\r
+ if (t->token != EpToken) {\r
+ t->down=MR_remove_epsilon_from_tree(t->down);\r
+ t->right=MR_remove_epsilon_from_tree(t->right);\r
+ return t;\r
+ } else {\r
+ Tree *u;\r
+ u=MR_remove_epsilon_from_tree(t->right);\r
+ t->right=NULL;\r
+ Tfree(t);\r
+ return u;\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_complete_set(int predDepth,set *tokensUsed,set *incomplete)\r
+#else\r
+void MR_complete_set(predDepth,tokensUsed,incomplete)\r
+ int predDepth;\r
+ set *tokensUsed;\r
+ set *incomplete;\r
+#endif\r
+{\r
+ int i;\r
+ RuleRefNode *ruleRef;\r
+ set rk2;\r
+ set b;\r
+ int k2;\r
+ Junction *save_MR_RuleBlkWithHalt;\r
+\r
+ if (set_int(*incomplete) > (unsigned) predDepth) {\r
+ return;\r
+ };\r
+\r
+ require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,\r
+ "RuleRefStack and RuleBlkWithHaltStack not same size");\r
+\r
+ require(MR_RuleBlkWithHalt == NULL ||\r
+ (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),\r
+ "RuleBlkWithHalt has no halt set");\r
+\r
+ save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;\r
+\r
+ if (MR_RuleBlkWithHalt != NULL) {\r
+ MR_RuleBlkWithHalt->end->halt=FALSE;\r
+ };\r
+\r
+ for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {\r
+ ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];\r
+ if (ruleRef == NULL) continue;\r
+\r
+ MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];\r
+ if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;\r
+\r
+ rk2=empty;\r
+ b=empty;\r
+\r
+ while ( !set_nil(*incomplete) ) {\r
+ k2=set_int(*incomplete);\r
+ if (k2 > predDepth) break; /* <=== another exit from loop */\r
+ set_rm(k2,*incomplete);\r
+ REACH(ruleRef->next,k2,&rk2,b);\r
+ set_orin(tokensUsed,b);\r
+ set_free(b);\r
+ };\r
+\r
+ if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;\r
+\r
+ set_orin(incomplete,rk2); /* remember what we couldn't do */\r
+ set_free(rk2);\r
+ if (set_int(*incomplete) > (unsigned) predDepth) break; /* <=== another exit from loop */\r
+ };\r
+\r
+ MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;\r
+ if (MR_RuleBlkWithHalt != NULL) {\r
+ MR_RuleBlkWithHalt->end->halt=TRUE;\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_complete_tree(int predDepth,Tree **t,set *incomplete)\r
+#else\r
+void MR_complete_tree(predDepth,t,incomplete)\r
+ int predDepth;\r
+ Tree **t;\r
+ set *incomplete;\r
+#endif\r
+{\r
+ int i;\r
+ RuleRefNode *ruleRef;\r
+ set rk2;\r
+ Tree *u;\r
+ unsigned k2;\r
+ Junction *save_MR_RuleBlkWithHalt;\r
+ int saveConstrainSearch;\r
+\r
+ if (set_int(*incomplete) > (unsigned) predDepth) {\r
+ return;\r
+ };\r
+\r
+ require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,\r
+ "RuleRefStack and RuleBlkWithHaltStack not same size");\r
+\r
+ require(MR_RuleBlkWithHalt == NULL ||\r
+ (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),\r
+ "RuleBlkWithHalt has no halt set");\r
+\r
+ save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;\r
+ saveConstrainSearch=ConstrainSearch;\r
+ ConstrainSearch=0;\r
+\r
+ if (MR_RuleBlkWithHalt != NULL) {\r
+ MR_RuleBlkWithHalt->end->halt=FALSE;\r
+ };\r
+\r
+ for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {\r
+ ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];\r
+ if (ruleRef == NULL) continue;\r
+\r
+ MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];\r
+\r
+ if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;\r
+\r
+ rk2=empty;\r
+\r
+ while ( !set_nil(*incomplete) ) { \r
+ k2 = set_int(*incomplete);\r
+ if (k2 > (unsigned) predDepth) break; /* <=== another exit from loop */\r
+ set_rm(k2,*incomplete);\r
+ u = NULL;\r
+\r
+ TRAV(ruleRef->next,k2,&rk2,u);\r
+\r
+ /* any subtrees missing k2 tokens, add u onto end */\r
+\r
+ *t=tlink(*t,u,k2);\r
+ Tfree(u);\r
+ }\r
+\r
+ set_orin(incomplete,rk2); /* remember what we couldn't do */\r
+ set_free(rk2);\r
+\r
+ if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;\r
+\r
+ if (set_int(*incomplete) > (unsigned) predDepth) break; /* <=== another exit from loop */\r
+ };\r
+\r
+ MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;\r
+\r
+ if (MR_RuleBlkWithHalt != NULL) {\r
+ MR_RuleBlkWithHalt->end->halt=TRUE;\r
+ };\r
+ ConstrainSearch=saveConstrainSearch;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_complete_predicates(int predDepth,Predicate *pred)\r
+#else\r
+void MR_complete_predicates(predDepth,pred)\r
+ int predDepth;\r
+ Predicate *pred;\r
+#endif\r
+{\r
+ if (pred == NULL) return;\r
+ if (pred->expr != PRED_AND_LIST &&\r
+ pred->expr != PRED_OR_LIST) {\r
+ MR_complete_set(predDepth,&(pred->scontext[1]),&(pred->completionSet));\r
+ MR_complete_tree(predDepth,&(pred->tcontext),&(pred->completionTree));\r
+ };\r
+ MR_complete_predicates(predDepth,pred->down);\r
+ MR_complete_predicates(predDepth,pred->right);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Junction * MR_junctionWithoutP2(Junction *j)\r
+#else\r
+Junction * MR_junctionWithoutP2(j)\r
+ Junction *j;\r
+#endif\r
+{\r
+ Junction *thisAlt;\r
+\r
+/* don't want to follow p2 to the next alternative of this rule */\r
+/* insert a generic node with null p2 if necessary */\r
+/* however FIRST requires a junction */\r
+\r
+ thisAlt=j;\r
+ if (thisAlt->p2 != NULL) {\r
+ if (thisAlt->p1->ntype == nJunction) {\r
+ thisAlt=(Junction *) thisAlt->p1;\r
+ } else {\r
+ thisAlt=newJunction();\r
+ thisAlt->p1=j->p1;\r
+ thisAlt->rname=j->rname;\r
+ thisAlt->file=j->file;\r
+ thisAlt->line=j->line;\r
+ j->p1=(Node *)thisAlt;\r
+ };\r
+ };\r
+ return thisAlt;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_tree_equ(Tree *big, Tree *small) {\r
+#else\r
+int MR_tree_equ(big,small)\r
+ Tree *big;\r
+ Tree *small;\r
+{\r
+#endif\r
+\r
+ Tree *b;\r
+ Tree *s;\r
+ int bcount=0;\r
+ int scount=0;\r
+\r
+ if (small == NULL && big == NULL) return 1;\r
+ if (small == NULL) return 0;\r
+ if (big == NULL) return 0;\r
+\r
+ if (small->token == ALT) {\r
+ require(small->right == NULL,\r
+ "MR_tree_equ: small: ALT node has siblings");\r
+ return MR_tree_equ(big,small->down);\r
+ };\r
+ if (big->token == ALT) {\r
+ require(big->right == NULL,\r
+ "MR_tree_equ: big: ALT node has siblings");\r
+ return MR_tree_equ(big->down,small);\r
+ };\r
+ for (s=small; s != NULL; s=s->right) {\r
+ scount++;\r
+ require(s->token != EpToken,"MR_tree_equ: s->EpToken unexpected\n");\r
+ };\r
+ for (b=big; b != NULL; b=b->right) {\r
+ bcount++;\r
+ require(b->token != EpToken,"MR_tree_equ: b->EpToken unexpected\n");\r
+ };\r
+\r
+ if (bcount != scount) return 0;\r
+\r
+ for (s=small; s != NULL; s=s->right) {\r
+ for (b=big; b!= NULL; b=b->right) {\r
+ if (s->token == b->token) {\r
+ if (MR_tree_equ(b->down,s->down)) goto next_s;\r
+ };\r
+ };\r
+ return 0;\r
+next_s:\r
+ continue;\r
+ };\r
+ return 1;\r
+}\r
+\r
+/* this does not compare sources - only contexts ! */\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_identicalContext(Predicate *p,Predicate *q)\r
+#else\r
+int MR_identicalContext(p,q)\r
+ Predicate *p;\r
+ Predicate *q;\r
+#endif\r
+{\r
+ if (p->k != q->k) return 0;\r
+ require ( (p->tcontext == NULL) == (q->tcontext == NULL),\r
+ "tcontext inconsistent");\r
+ if (p->k == 1) {\r
+ return set_equ(p->scontext[1],q->scontext[1]);\r
+ } else {\r
+ return MR_tree_equ(p->tcontext,q->tcontext);\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_reportSetSuppression(int predDepth,\r
+ set predSet,set plainSet,Junction *jPred,Junction *jPlain,Predicate *p)\r
+#else\r
+void MR_reportSetSuppression(predDepth,predSet,plainSet,jPred,jPlain,p)\r
+ int predDepth;\r
+ set predSet;\r
+ set plainSet;\r
+ Junction *jPred;\r
+ Junction *jPlain;\r
+ Predicate *p;\r
+#endif\r
+{\r
+ if (InfoP) {\r
+ fprintf(output,"\n#if 0\n\n");\r
+ fprintf(output,"Hoisting of predicate suppressed by alternative without predicate.\n");\r
+ fprintf(output,"The alt without the predicate includes all cases where the predicate is false.\n\n");\r
+ fprintf(output," WITH predicate: line %d %s\n",jPred->line,FileStr[jPred->file]);\r
+ if (jPlain != NULL) {\r
+ fprintf(output," WITHOUT predicate: line %d %s\n",jPlain->line,FileStr[jPlain->file]);\r
+ } else {\r
+ fprintf(output," WITHOUT predicate: all alternatives without predicates (combined)\n");\r
+ };\r
+ if (predDepth == 1) {\r
+ fprintf(output,"\nThe context set for the predicate:\n");\r
+ MR_dumpTokenSet(output,1,predSet);\r
+ };\r
+ fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");\r
+ MR_dumpTokenSet(output,1,plainSet);\r
+ fprintf(output,"\nThe predicate:\n\n");\r
+ MR_dumpPred1(1,p,1);\r
+ fprintf(output,"Chain of referenced rules:\n\n");\r
+ MR_dumpPredRuleRefStack(output,4);\r
+ fprintf(output,"\n#endif\n");\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_reportSetRestriction(int predDepth,set predSet,set plainSet,\r
+ Junction *jPred,Junction *jPlain,Predicate *origPred,Predicate *newPred)\r
+#else\r
+void MR_reportSetRestriction(predDepth,predSet,plainSet,jPred,jPlain,origPred,newPred)\r
+ int predDepth;\r
+ set predSet;\r
+ set plainSet;\r
+ Junction *jPred;\r
+ Junction *jPlain;\r
+ Predicate *origPred;\r
+ Predicate *newPred;\r
+#endif\r
+{\r
+ set intersect;\r
+\r
+ intersect=empty;\r
+\r
+ if (! InfoP) return;\r
+ fprintf(output,"\n#if 0\n\n");\r
+ fprintf(output,"Restricting the context of a predicate because of overlap in the lookahead set\n");\r
+ fprintf(output," between the alternative with the semantic predicate and one without\n");\r
+ fprintf(output,"Without this restriction the alternative without the predicate could not\n");\r
+ fprintf(output," be reached when input matched the context of the predicate and the predicate\n");\r
+ fprintf(output," was false.\n\n");\r
+\r
+ fprintf(output," WITH predicate: line %d %s\n",jPred->line,FileStr[jPred->file]);\r
+ if (jPlain != NULL) {\r
+ fprintf(output," WITHOUT predicate: line %d %s\n",jPlain->line,FileStr[jPlain->file]);\r
+ } else {\r
+ fprintf(output," WITHOUT predicate: all alternatives without predicates (combined)\n");\r
+ };\r
+ if (predDepth == 1) {\r
+ fprintf(output,"\nThe original context set for the predicate:\n");\r
+ MR_dumpTokenSet(output,1,predSet);\r
+ };\r
+ fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");\r
+ MR_dumpTokenSet(output,1,plainSet);\r
+ if (predDepth == 1) {\r
+ fprintf(output,"\nThe intersection of the two sets\n");\r
+ intersect=set_and(predSet,plainSet);\r
+ MR_dumpTokenSet(output,1,intersect);\r
+ set_free(intersect);\r
+ };\r
+ fprintf(output,"\nThe original predicate:\n\n");\r
+ MR_dumpPred1(1,origPred,1);\r
+ fprintf(output,"The new (modified) form of the predicate:\n\n");\r
+ MR_dumpPred1(1,newPred,1);\r
+ fprintf(output,"#endif\n");\r
+}\r
+\r
+/* don't use Pass3 by itself unless you know that inverted is not important */\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate * MR_removeRedundantPredPass3(Predicate *p)\r
+#else\r
+Predicate * MR_removeRedundantPredPass3(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ Predicate *q;\r
+\r
+ if (p == NULL) return NULL;\r
+ p->right=MR_removeRedundantPredPass3(p->right);\r
+ p->down=MR_removeRedundantPredPass3(p->down);\r
+ if (p->redundant) {\r
+ q=p->right;\r
+ p->right=NULL;\r
+ predicate_free(p);\r
+ return q;\r
+ };\r
+ if (p->expr == PRED_AND_LIST ||\r
+ p->expr == PRED_OR_LIST) {\r
+ if (p->down == NULL) {\r
+ q=p->right;\r
+ p->right=NULL;\r
+ predicate_free(p);\r
+ return q;\r
+ };\r
+ if (p->down != NULL && p->down->right == NULL) {\r
+ q=p->down;\r
+ q->right=p->right;\r
+ p->right=NULL;\r
+ p->down=NULL;\r
+ return q;\r
+ };\r
+ };\r
+ return p;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_removeRedundantPredPass2(Predicate *p)\r
+#else\r
+void MR_removeRedundantPredPass2(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ Predicate *q;\r
+\r
+ if (p == NULL) return;\r
+\r
+ if (p->expr == PRED_AND_LIST) {\r
+ for (q=p->down ; q != NULL ; q=q->right) {\r
+ MR_removeRedundantPredPass2(q);\r
+ if (q->isConst) {\r
+ if (q->constValue == 0) {\r
+ p->isConst=1;\r
+ p->constValue=0;\r
+ return;\r
+ } else {\r
+ q->redundant=1;\r
+ };\r
+ };\r
+ };\r
+ };\r
+\r
+ if (p->expr == PRED_OR_LIST) {\r
+ for (q=p->down ; q != NULL ; q=q->right) {\r
+ MR_removeRedundantPredPass2(q);\r
+ if (q->isConst) {\r
+ if (q->constValue == 0) {\r
+ q->redundant=1;\r
+ } else {\r
+ p->isConst=1;\r
+ p->constValue=1;\r
+ return;\r
+ };\r
+ };\r
+ };\r
+ };\r
+\r
+ return;\r
+}\r
+\r
+#if 0\r
+ this totally ignores the implications of guarded predicates\r
+ in which the part after the guard could possibly cover a predicate.\r
+ that would be much harder:\r
+\r
+ rule : (A)? => <<p>>? sub1; /* 1 */\r
+ | (B)? => <<r>>? sub2 /* 2 */\r
+ sub1 : (A)? => <<q>>? A B /* 3 */\r
+ | B /* 4 - suppresses line 2 */\r
+ ;\r
+#endif\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_apply_restriction1(Predicate *pred,set *plainSet,int *changed)\r
+#else\r
+void MR_apply_restriction1(pred,plainSet,changed)\r
+ Predicate *pred;\r
+ set *plainSet;\r
+ int *changed;\r
+#endif\r
+{\r
+ if (pred == NULL) return;\r
+ MR_apply_restriction1(pred->right,plainSet,changed);\r
+ if (pred->down != NULL) {\r
+ MR_apply_restriction1(pred->down,plainSet,changed);\r
+ } else {\r
+ set t;\r
+ if (pred->k == 1) {\r
+ t=set_dif(pred->scontext[1],*plainSet);\r
+ if (*changed == 0 &&\r
+ !set_equ(t,pred->scontext[1])) {\r
+ *changed=1;\r
+ };\r
+ if (set_nil(t)) {\r
+ pred->redundant=1;\r
+ };\r
+ set_free(pred->scontext[1]);\r
+ pred->scontext[1]=t;\r
+ };\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_orin_plainSet(Predicate *p,set plainSet)\r
+#else\r
+void MR_orin_plainSet(p,plainSet)\r
+ Predicate *p;\r
+ set plainSet;\r
+#endif\r
+{\r
+ if (p == NULL) return;\r
+ MR_orin_plainSet(p->down,plainSet);\r
+ MR_orin_plainSet(p->right,plainSet);\r
+ set_orin(&p->plainSet,plainSet);\r
+}\r
+\r
+Predicate *PRED_SUPPRESS;\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate * MR_find_in_aSubBlk(Junction *alt)\r
+#else\r
+Predicate * MR_find_in_aSubBlk(alt)\r
+ Junction *alt;\r
+#endif\r
+{\r
+ Predicate *root=NULL;\r
+ Predicate **tail=NULL;\r
+\r
+ Junction *p;\r
+\r
+ int nAlts=0;\r
+ Junction **jList;\r
+ Predicate **predList;\r
+ int *matchList;\r
+ set predSet;\r
+ int i;\r
+ int j;\r
+ int m;\r
+ int predDepth;\r
+ set incomplete;\r
+ set union_plainSet;\r
+ set setChange;\r
+ int changed;\r
+ Predicate *newPred;\r
+ set setDif;\r
+ Predicate *origPred;\r
+ int depth1=1; /* const int */\r
+ set *plainContext;\r
+ set plainSet;\r
+\r
+ predSet=empty;\r
+ incomplete=empty;\r
+ union_plainSet=empty;\r
+ setChange=empty;\r
+ setDif=empty;\r
+ plainSet=empty;\r
+\r
+ if (PRED_SUPPRESS == NULL) {\r
+ PRED_SUPPRESS=new_pred();\r
+ PRED_SUPPRESS->expr="Predicate Suppressed";\r
+ };\r
+\r
+ /* this section just counts the number of "interesting" alternatives */\r
+ /* in order to allocate arrays */\r
+\r
+ for (p=alt; p!=NULL; p=(Junction *)p->p2) {\r
+ /* ignore empty alts */\r
+ if ( p->p1->ntype != nJunction ||\r
+ ((Junction *)p->p1)->jtype != EndBlk ) {\r
+ nAlts++;\r
+ };\r
+ };\r
+\r
+ /* if this is a (...)+ block then don't count the last alt because\r
+ it can't be taken until at least one time through the block.\r
+ In other words it isn't a real choice until the (...)+ is entered\r
+ at which point the hoisting issue is moot.\r
+ Maybe look at "ignore" instead ?\r
+ */\r
+\r
+ if (alt->jtype == aPlusBlk) {\r
+ nAlts--;\r
+ };\r
+\r
+ jList=(Junction **)calloc(nAlts,sizeof(Junction *));\r
+ require(jList!=NULL,"cannot allocate MR_find_in_aSubBlk jList");\r
+\r
+ plainContext=(set *)calloc(nAlts,sizeof(set));\r
+ require(plainContext!=NULL,"cannot allocate MR_find_in_aSubBlk plainContext");\r
+ for (m=0; m < nAlts; m++) plainContext[m]=empty;\r
+\r
+ predList=(Predicate **)calloc(nAlts,sizeof(Predicate *));\r
+ require(predList!=NULL,"cannot allocate MR_find_in_aSubBlk predList");\r
+\r
+ matchList=(int *)calloc(nAlts,sizeof(int));\r
+ require(matchList!=NULL,"cannot allocate MR_find_in_aSubBlk matchList");\r
+\r
+ /* this section just fills in the arrays previously allocated */\r
+ /* the most interesting one is matchList[] */\r
+ /* */\r
+ /* bit 0 => this alt has a semantic pred which is "covered" */\r
+ /* by an alt without a semantic pred. Don't hoist. */\r
+\r
+ for (i=0,p=alt;\r
+ p!=NULL && i<nAlts;\r
+ i++,p=(Junction *)p->p2) {\r
+\r
+ /* ignore empty alts */\r
+\r
+ if ( p->p1->ntype != nJunction ||\r
+ ((Junction *)p->p1)->jtype != EndBlk ) {\r
+ jList[i]=MR_junctionWithoutP2(p);\r
+ predList[i]=find_predicates(p->p1); /* should be jList ????? */\r
+ if (predList[i] != NULL) {\r
+ MR_cleanup_pred_trees(predList[i]); /* flatten & left factor */\r
+ plainContext[i]=MR_union_plain_sets(predList[i]);\r
+ } else {\r
+ MR_set_reuse(&plainSet);\r
+ MR_set_reuse(&incomplete);\r
+ plainSet=MR_First(depth1,jList[i],&incomplete);\r
+ MR_complete_set(depth1,&plainSet,&incomplete);\r
+ require(set_nil(incomplete),"couldn't complete k=1");\r
+ plainContext[i]=plainSet;\r
+ plainSet=empty;\r
+ };\r
+ set_orin(&union_plainSet,plainContext[i]);\r
+ };\r
+ };\r
+\r
+ if (nAlts == 1) {\r
+ goto EXIT_SIMPLE;\r
+ };\r
+\r
+/*\r
+ * Looking for cases where alt i has a semantic pred and alt j does not.\r
+ * Don't care about cases where lookahead for semantic predicates overlap\r
+ * because normal predicate hoisting does the correct thing automatically.\r
+ * Don't care about cases where lookahead for alts without semantic predicates\r
+ * overlap because normal prediction does the correct thing automatically.\r
+ *\r
+ * When we find such a case check for one of three subcases:\r
+ *\r
+ * 1. if lookahead for alt i is contained in the lookahead for any\r
+ * alt j then ignore semantic predicate of alt i\r
+ * 2. if lookahead for alt i is not contained in the lookahead for\r
+ * any alt j then add add predicate i to the OR list to be hoisted\r
+ * 3. if lookahead for alt i overlaps the lookahead for some alt j then\r
+ * add a dummy semantic predicate for alt j\r
+ *\r
+ * There is an implicit assumption that the context of all alternatives following\r
+ * the rule being processed here are identical (but may vary from hoist to\r
+ * hoist depending on the place where the rule was invoked that led to hoisting\r
+ * these predicates. In othere words in the fragment:\r
+ *\r
+ * ( <<a>>? a1 a2 a3 | <<b>>? b1 b2 b3 )\r
+ *\r
+ * both a3 and b3 have the same follow sets because they are both at the end of\r
+ * alternatives in the same block.\r
+ */\r
+\r
+ for (i=0; i < nAlts; i++) {\r
+ if (jList[i] == NULL) continue;\r
+ if (predList[i] == NULL) continue;\r
+\r
+ /* if the predicate depth turns out to be one token only */\r
+ /* then it is can be easily represented as a set and */\r
+ /* compared to the junction set create by MR_First() */\r
+\r
+ predDepth=0;\r
+ MR_pred_depth(predList[i],&predDepth);\r
+ require (predDepth >= 1,"MR_find_in_aSubBlk: pred depth < 1");\r
+ require (predDepth <= CLL_k,"MR_find_in_aSubBlk: predDepth > CLL_k");\r
+\r
+ /* complete predicates to predDepth\r
+ If completed to depth=1 then the context would be incomplete.\r
+ The context would be truncated and the predicate simplify routine\r
+ would have incomplete information. It would lead to\r
+ either false matches of failure to find true matches.\r
+ */\r
+\r
+ MR_complete_predicates(predDepth,predList[i]);\r
+\r
+ if (predList[i] != NULL) {\r
+ MR_cleanup_pred_trees(predList[i]); /* flatten & left factor */\r
+ };\r
+\r
+ /* If the predicate depth is 1 then it is possible to suppress\r
+ a predicate completely using a single plain alt. Check for suppression\r
+ by a single plain alt first because it gives better messages. If that\r
+ fails try the union of all the plain alts.\r
+ */\r
+\r
+ if (predDepth == 1) {\r
+\r
+ MR_set_reuse(&predSet);\r
+ predSet=MR_compute_pred_set(predList[i]); /* ignores k>1 predicates */\r
+\r
+ for (j=0; j < nAlts; j++) {\r
+ if (jList[j] == NULL) continue;\r
+ if (j == i) continue;\r
+\r
+ MR_set_reuse(&setDif);\r
+ setDif=set_dif(predSet,plainContext[j]);\r
+ if (set_nil(setDif)) {\r
+ matchList[i] |= 1;\r
+ MR_reportSetSuppression(predDepth,predSet,plainContext[j],jList[i],jList[j],predList[i]);\r
+ predicate_free(predList[i]);\r
+ predList[i]=PRED_SUPPRESS;\r
+ goto next_i;\r
+ };\r
+\r
+ }; /* end loop on j */\r
+\r
+ changed=0;\r
+\r
+ /* predicate_dup is only to give good error messages */\r
+ /* remember to do a predicate_free() */\r
+\r
+ origPred=predicate_dup(predList[i]);\r
+ MR_apply_restriction1(predList[i],&union_plainSet,&changed);\r
+ if (changed) {\r
+\r
+ /* don't use Pass3 by itself unless you know that inverted is not important */\r
+\r
+ newPred=MR_removeRedundantPredPass3(predList[i]);\r
+ newPred=MR_predSimplifyALL(newPred);\r
+ if (newPred == NULL) {\r
+ matchList[i] |= 1;\r
+ MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],\r
+ NULL,origPred);\r
+ predList[i]=PRED_SUPPRESS;\r
+ } else {\r
+ MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],\r
+ NULL,origPred,newPred);\r
+ predList[i]=newPred;\r
+ };\r
+ };\r
+ predicate_free(origPred);\r
+ origPred=NULL;\r
+ };\r
+\r
+ /*\r
+ If the predicate depth is > 1 then it can't be suppressed completely\r
+ because the code doesn't support inspection of such things. They're\r
+ much messier than k=1 sets.\r
+ */\r
+\r
+ if (predDepth > 1 ) {\r
+\r
+ changed=0;\r
+\r
+ /* predicate_dup is only to give good error messages */\r
+ /* remember to do a predicate_free() */\r
+\r
+ origPred=predicate_dup(predList[i]);\r
+ MR_apply_restriction1(predList[i],&union_plainSet,&changed);\r
+ if (changed) {\r
+ newPred=MR_removeRedundantPredPass3(predList[i]);\r
+ newPred=MR_predSimplifyALL(newPred);\r
+ if (newPred == NULL) {\r
+ matchList[i] |= 1;\r
+ MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],\r
+ NULL,origPred);\r
+ predList[i]=PRED_SUPPRESS;\r
+ } else {\r
+ MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],\r
+ NULL,origPred,newPred);\r
+ predList[i]=newPred;\r
+ };\r
+ };\r
+ predicate_free(origPred);\r
+ origPred=NULL;\r
+ };\r
+next_i:\r
+ continue;\r
+ };\r
+\r
+EXIT_SIMPLE:\r
+\r
+ root = new_pred();\r
+ root->expr=PRED_OR_LIST;\r
+ tail = &(root->down);\r
+\r
+ for (i=0 ; i< nAlts ; i++) {\r
+ if (jList[i] == NULL) continue;\r
+\r
+ if (predList[i] == NULL) {\r
+ continue;\r
+ } else if ( (matchList[i] & 1) != 0) {\r
+ if (predList[i] != PRED_SUPPRESS) {\r
+ predicate_free(predList[i]);\r
+ };\r
+ continue;\r
+ };\r
+\r
+ /* make an OR list of predicates */\r
+\r
+ *tail=predList[i];\r
+ tail=&(predList[i]->right);\r
+ };\r
+\r
+ /* if just one pred, remove OR root */\r
+\r
+ if (root->down == NULL) {\r
+ predicate_free(root);\r
+ root=NULL;\r
+ } else if (root->down->right == NULL) {\r
+ Predicate *p=root->down;\r
+ root->down=NULL;\r
+ predicate_free(root);\r
+ root=p;\r
+ }\r
+\r
+ root=MR_predSimplifyALL(root);\r
+\r
+ MR_orin_plainSet(root,union_plainSet);\r
+\r
+ set_free(predSet);\r
+ set_free(union_plainSet);\r
+ set_free(incomplete);\r
+ set_free(setChange);\r
+ set_free(setDif);\r
+\r
+ for (m=0; m < nAlts; m++) set_free(plainContext[m]);\r
+\r
+ free ( (char *) jList);\r
+ free ( (char *) predList);\r
+ free ( (char *) matchList);\r
+ free ( (char *) plainContext);\r
+\r
+ return root;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_predContextPresent(Predicate *p,int *allHaveContext,int *noneHaveContext)\r
+#else\r
+void MR_predContextPresent(p,allHaveContext,noneHaveContext)\r
+ Predicate *p;\r
+ int *allHaveContext;\r
+ int *noneHaveContext;\r
+#endif\r
+{\r
+ if (p == NULL) return;\r
+ MR_predContextPresent(p->right,allHaveContext,noneHaveContext);\r
+ if (p->expr != PRED_AND_LIST &&\r
+ p->expr != PRED_OR_LIST) {\r
+ if (set_nil(p->scontext[1]) == 0 ||\r
+ (p->tcontext != NULL)) {\r
+ *noneHaveContext=0;\r
+ } else {\r
+ *allHaveContext=0;\r
+ };\r
+ };\r
+ MR_predContextPresent(p->down,allHaveContext,noneHaveContext);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_pointerStackPush(PointerStack *ps,void *dataPointer)\r
+#else\r
+int MR_pointerStackPush(ps,dataPointer)\r
+ PointerStack *ps;\r
+ void *dataPointer;\r
+#endif\r
+{\r
+ void **newStack;\r
+ int newSize;\r
+ int i;\r
+\r
+ if (ps->count == ps->size) {\r
+ newSize=20+ps->size*2;\r
+ newStack=(void **)calloc(newSize,sizeof(void *));\r
+ require (newStack != NULL,"cannot allocate PointerStack");\r
+ for (i=0; i < ps->size; i++) {\r
+ newStack[i]=ps->data[i];\r
+ };\r
+ if (ps->data != NULL) free( (char *) ps->data);\r
+ ps->data=newStack;\r
+ ps->size=newSize;\r
+ };\r
+ ps->data[ps->count]=dataPointer;\r
+ ps->count++;\r
+ return ps->count-1;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void * MR_pointerStackPop(PointerStack *ps)\r
+#else\r
+void * MR_pointerStackPop(ps)\r
+ PointerStack *ps;\r
+#endif\r
+{\r
+ void *dataPointer;\r
+\r
+ require(ps->count > 0,"MR_pointerStackPop underflow");\r
+\r
+ dataPointer=ps->data[ps->count-1];\r
+ ps->data[ps->count-1]=NULL;\r
+ (ps->count)--;\r
+ return dataPointer;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void * MR_pointerStackTop(PointerStack *ps)\r
+#else\r
+void * MR_pointerStackTop(ps)\r
+ PointerStack *ps;\r
+#endif\r
+{\r
+ require(ps->count > 0,"MR_pointerStackTop underflow");\r
+ return ps->data[ps->count-1];\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_pointerStackReset(PointerStack *ps)\r
+#else\r
+void MR_pointerStackReset(ps)\r
+ PointerStack *ps;\r
+#endif\r
+{\r
+ int i;\r
+ if (ps->data != NULL) {\r
+ for (i=0; i < ps->count ; i++) {\r
+ ps->data[i]=NULL;\r
+ };\r
+ };\r
+ ps->count=0;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Junction *MR_nameToRuleBlk(char *name)\r
+#else\r
+Junction *MR_nameToRuleBlk(name)\r
+ char *name;\r
+#endif\r
+{\r
+ RuleEntry *q;\r
+\r
+ require (RulePtr != NULL,"MR_nameToRule: RulePtr not initialized");\r
+\r
+ if (name == NULL) return NULL;\r
+\r
+ q = (RuleEntry *) hash_get(Rname,name);\r
+\r
+ if ( q == NULL ) {\r
+ return NULL;\r
+ } else {\r
+ return RulePtr[q->rulenum];\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Junction * MR_ruleReferenced(RuleRefNode *rrn)\r
+#else\r
+Junction * MR_ruleReferenced(rrn)\r
+ RuleRefNode *rrn;\r
+#endif\r
+{\r
+ return MR_nameToRuleBlk(rrn->text);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_comparePredLeaves(Predicate *me,Predicate *myParent,Predicate *him,Predicate *hisParent)\r
+#else\r
+void MR_comparePredLeaves(me,myParent,him,hisParent)\r
+ Predicate *me;\r
+ Predicate *myParent;\r
+ Predicate *him;\r
+ Predicate *hisParent;\r
+#endif\r
+{\r
+ if (me == NULL) return;\r
+ if (me == him) {\r
+ MR_comparePredLeaves(me->right,myParent,him,hisParent);\r
+ return;\r
+ } else if (me->expr == PRED_AND_LIST ||\r
+ me->expr == PRED_OR_LIST) {\r
+ MR_comparePredLeaves(me->down,me,him,hisParent);\r
+ MR_comparePredLeaves(me->right,myParent,him,hisParent);\r
+ return;\r
+ } else {\r
+ if (me->source != NULL) {\r
+\r
+ /* predicate->invert can be set only in the predEntry predicates */\r
+ /* thus they are only visible after the predEntry predicates have been "unfolded" */\r
+\r
+ int sameSource=(me->source == him->source);\r
+ int sameInvert=1 &\r
+ (1 + me->inverted + him->inverted + me->source->inverted + him->source->inverted);\r
+ int samePredEntry=(me->source->predEntry != NULL\r
+ && him->source->predEntry != NULL\r
+ && me->source->predEntry == him->source->predEntry);\r
+ if (sameInvert && (sameSource || samePredEntry)) {\r
+ if (MR_identicalContext(me,him)) {\r
+\r
+ /* identical predicates */\r
+\r
+ if (hisParent->expr == PRED_OR_LIST &&\r
+ myParent->expr == PRED_OR_LIST) {\r
+ me->redundant=1;\r
+ } else if (hisParent->expr == PRED_AND_LIST &&\r
+ myParent->expr == PRED_AND_LIST) {\r
+ me->redundant=1;\r
+ } else if ( (hisParent->expr == PRED_OR_LIST &&\r
+ myParent->expr == PRED_AND_LIST)\r
+ ||\r
+ (hisParent->expr == PRED_AND_LIST &&\r
+ myParent->expr == PRED_OR_LIST)\r
+ ) {\r
+ myParent->redundant=1;\r
+ } else {\r
+ require (0,"MR_comparePredLeaves: not both PRED_LIST");\r
+ };\r
+ };\r
+ }; /* end same source or same predEntrr with same invert sense */\r
+\r
+ /* same predEntry but opposite invert sense */\r
+\r
+ if (!sameInvert && (sameSource || samePredEntry)) {\r
+ if (MR_identicalContext(me,him)) {\r
+ if (hisParent->expr == PRED_OR_LIST &&\r
+ myParent->expr == PRED_OR_LIST) {\r
+ myParent->isConst=1;\r
+ myParent->constValue=1;\r
+ } else if (hisParent->expr == PRED_AND_LIST &&\r
+ myParent->expr == PRED_AND_LIST) {\r
+ myParent->isConst=1;\r
+ myParent->constValue=0;\r
+ } else if ( (hisParent->expr == PRED_OR_LIST &&\r
+ myParent->expr == PRED_AND_LIST)\r
+ ||\r
+ (hisParent->expr == PRED_AND_LIST &&\r
+ myParent->expr == PRED_OR_LIST)\r
+ ) {\r
+ me->redundant=1;\r
+ } else {\r
+ require (0,"MR_comparePredLeaves: not both PRED_LIST");\r
+ };\r
+ };\r
+ }; /* end same predEntry with opposite invert sense */\r
+ };\r
+\r
+ MR_comparePredLeaves(me->right,myParent,him,hisParent);\r
+ return;\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_removeRedundantPredPass1(Predicate *me,Predicate *myParent)\r
+#else\r
+void MR_removeRedundantPredPass1(me,myParent)\r
+ Predicate *me;\r
+ Predicate *myParent;\r
+#endif\r
+{\r
+ if (me == NULL) return;\r
+ if (me->redundant) {\r
+ MR_removeRedundantPredPass1(me->right,myParent);\r
+ return;\r
+ };\r
+ if (me->expr == PRED_AND_LIST ||\r
+ me->expr == PRED_OR_LIST) {\r
+ MR_removeRedundantPredPass1(me->down,me);\r
+ MR_removeRedundantPredPass1(me->right,myParent);\r
+ } else {\r
+ require (me->source != NULL,"me->source == NULL");\r
+ if (myParent != NULL) {\r
+ MR_comparePredLeaves(myParent->down,myParent,me,myParent);\r
+ };\r
+ MR_removeRedundantPredPass1(me->right,myParent);\r
+ };\r
+}\r
+\r
+/* pretty much ignores things with the inverted bit set */\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate *MR_predFlatten(Predicate *p)\r
+#else\r
+Predicate *MR_predFlatten(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ if (p == NULL) return NULL;\r
+ if (p->expr == PRED_OR_LIST\r
+ || p->expr == PRED_AND_LIST) {\r
+\r
+ Predicate *child;\r
+ Predicate *gchild;\r
+ Predicate **tail;\r
+ Predicate *next;\r
+ char *PRED_XXX_LIST=p->expr;\r
+\r
+ require (p->down != NULL,"MR_predFlatten AND/OR no child");\r
+\r
+\r
+ p->down=MR_predFlatten(p->down);\r
+ p->right=MR_predFlatten(p->right);\r
+ child=p->down;\r
+ if (child->right == NULL) {\r
+ child->right=p->right;\r
+ p->right=NULL;\r
+ p->down=NULL;\r
+ if (p->inverted) child->inverted=!child->inverted;\r
+ predicate_free(p);\r
+ return child;\r
+ };\r
+\r
+ /* make a single list of all children and grandchildren */\r
+\r
+ tail=&(p->down);\r
+ for (child=p->down; child != NULL; child=next) {\r
+ if (child->expr != PRED_XXX_LIST\r
+ || child->inverted\r
+ || child->predEntry != NULL) {\r
+ *tail=child;\r
+ tail=&(child->right);\r
+ next=child->right;\r
+ } else {\r
+ for (gchild=child->down;\r
+ gchild != NULL;\r
+ gchild=gchild->right) {\r
+ *tail=gchild;\r
+ tail=&(gchild->right);\r
+ };\r
+ next=child->right;\r
+ child->right=NULL;\r
+ child->down=NULL;\r
+ predicate_free(child);\r
+ };\r
+ };\r
+ *tail=NULL;\r
+ return p;\r
+ } else {\r
+ p->right=MR_predFlatten(p->right);\r
+ return p;\r
+ };\r
+}\r
+\r
+static char *alwaysFalseWarning=NULL;\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate *checkPredicateConflict(Predicate *p)\r
+#else\r
+Predicate *checkPredicateConflict(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ if (p->isConst) {\r
+ if (p->constValue == 1) {\r
+ predicate_free(p);\r
+ return NULL;\r
+ } else {\r
+ if (InfoP && !p->conflictReported) {\r
+ p->conflictReported=1;\r
+ fprintf(output,"\n#if 0\n\n");\r
+ fprintf(output,"The following predicate expression will always be false:\n\n");\r
+ MR_dumpPred1(1,p,1);\r
+ fprintf(output,"\n#endif\n");\r
+ };\r
+\r
+ if (alwaysFalseWarning != CurRule) {\r
+ alwaysFalseWarning=CurRule;\r
+ if (InfoP) {\r
+ warnNoFL(eMsg1("one (or more) predicate expression hoisted into rule \"%s\" are always false \\r
+- see output file for more information",CurRule));\r
+ } else {\r
+ warnNoFL(eMsg1("one (or more) predicate expressions hoisted into rule \"%s\" are always false \\r
+- use \"-info p\" for more information",CurRule));\r
+ };\r
+ };\r
+ };\r
+ };\r
+ return p;\r
+}\r
+\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_countPredNodes(Predicate *p)\r
+#else\r
+int MR_countPredNodes(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ if (p == NULL) return 0;\r
+ return 1 + MR_countPredNodes(p->down) + MR_countPredNodes(p->right);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate *MR_predSimplifyALLX(Predicate *p,int skipPass3)\r
+#else\r
+Predicate *MR_predSimplifyALLX(p,skipPass3)\r
+ Predicate *p;\r
+ int skipPass3;\r
+#endif\r
+{\r
+ int countBefore;\r
+ int countAfter;\r
+\r
+ countAfter=MR_countPredNodes(p);\r
+\r
+ do {\r
+ if (p == NULL) return NULL;\r
+ if (p->right == NULL && p->down == NULL) return p;\r
+ countBefore=countAfter;\r
+ MR_simplifyInverted(p,0);\r
+ p=MR_predFlatten(p);\r
+ MR_removeRedundantPredPass1(p,NULL);\r
+ MR_removeRedundantPredPass2(p);\r
+ if (! skipPass3) {\r
+ p=checkPredicateConflict(p);\r
+ p=MR_removeRedundantPredPass3(p);\r
+ };\r
+ countAfter=MR_countPredNodes(p);\r
+ } while (countBefore != countAfter);\r
+\r
+ return p;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate *MR_predSimplifyALL(Predicate *p)\r
+#else\r
+Predicate *MR_predSimplifyALL(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ return MR_predSimplifyALLX(p,0);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_releaseResourcesUsedInRule(Node *n)\r
+#else\r
+void MR_releaseResourcesUsedInRule(n)\r
+ Node *n;\r
+#endif\r
+{\r
+ Node *next;\r
+ Junction *j;\r
+ int i;\r
+\r
+ if (n == NULL) return;\r
+ if (n->ntype == nJunction) {\r
+ j=(Junction *) n;\r
+\r
+ if (j->predicate != NULL) {\r
+ predicate_free(j->predicate);\r
+ j->predicate=NULL;\r
+ };\r
+ for (i=0; i< CLL_k; i++) {\r
+ set_free(j->fset[i]);\r
+ j->fset[i]=empty;\r
+ };\r
+ if (j->ftree != NULL) {\r
+ Tfree(j->ftree);\r
+ j->ftree=NULL;\r
+ };\r
+ if (j->jtype == EndRule) return;\r
+ if (j->jtype != RuleBlk && j->jtype != EndBlk) {\r
+ if (j->p2 != NULL && !j->ignore) { /* MR11 */\r
+ MR_releaseResourcesUsedInRule(j->p2);\r
+ };\r
+ };\r
+ };\r
+ next=MR_advance(n);\r
+ MR_releaseResourcesUsedInRule(next);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_allPredLeaves(Predicate *p)\r
+#else\r
+int MR_allPredLeaves(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ Predicate *q;\r
+\r
+ if (p == NULL) return 1;\r
+\r
+ for (q=p; q != NULL; q=q->right) {\r
+ if (q->down != NULL) return 0;\r
+ };\r
+ return 1;\r
+}\r
+\r
+/* make sure it works for the last rule in a file */\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_offsetFromRule(Node *n)\r
+#else\r
+int MR_offsetFromRule(n)\r
+ Node *n;\r
+#endif\r
+{\r
+ Junction *j;\r
+ int offset=(-1);\r
+\r
+ for (j=SynDiag; j != NULL; j=(Junction *)j->p2) {\r
+\r
+ require (j->ntype == nJunction && j->jtype == RuleBlk,"Not a rule block");\r
+\r
+ if (n->file < j->file) {\r
+ return offset;\r
+ };\r
+ if (n->file == j->file) {\r
+ if (n->line < j->line) {\r
+ return (offset < 0) ? 0 : offset;\r
+ } else {\r
+ offset=n->line - j->line;\r
+ if (offset == 0) return 0;\r
+ };\r
+ };\r
+ };\r
+ return offset;\r
+}\r
+\r
+#define ruleNameMax 50\r
+\r
+static char ruleNameStatic1[ruleNameMax];\r
+static char ruleNameStatic2[ruleNameMax+10];\r
+\r
+#ifdef __USE_PROTOS\r
+char * MR_ruleNamePlusOffset(Node *n)\r
+#else\r
+char * MR_ruleNamePlusOffset(n)\r
+ Node *n;\r
+#endif\r
+{\r
+ int offset=MR_offsetFromRule(n);\r
+\r
+ strncpy(ruleNameStatic1,n->rname,ruleNameMax);\r
+ if (offset < 0) {\r
+ sprintf(ruleNameStatic2,"%s/?",ruleNameStatic1);\r
+ } else {\r
+ sprintf(ruleNameStatic2,"%s/%d",ruleNameStatic1,offset+1);\r
+ };\r
+ return ruleNameStatic2;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_max_height_of_tree(Tree *t)\r
+#else\r
+int MR_max_height_of_tree(t)\r
+ Tree *t;\r
+#endif\r
+{\r
+ int h;\r
+ int height=0;\r
+ Tree *u;\r
+\r
+ if (t == NULL) return 0;\r
+\r
+ require (t->token != ALT && t->token != EpToken,"MR_max_height_of_tree ALT or EpToken");\r
+\r
+ for (u=t; u != NULL; u=u->right) {\r
+ h=MR_max_height_of_tree(u->down)+1;\r
+ if (h > height) height=h;\r
+ };\r
+ return height;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_all_leaves_same_height(Tree *t,int depth)\r
+#else\r
+int MR_all_leaves_same_height(t,depth)\r
+ Tree *t;\r
+ int depth;\r
+#endif\r
+{\r
+ if (t == NULL) {\r
+ return (depth==0);\r
+ };\r
+\r
+ require (t->token != ALT && t->token != EpToken,"MR_all_leaves_same_height ALT or EpToken");\r
+\r
+ if (depth == 0) {\r
+ return 0;\r
+ } else {\r
+ if ( ! MR_all_leaves_same_height(t->down,depth-1)) {\r
+ return 0;\r
+ };\r
+ if (t->right == NULL) {\r
+ return 1;\r
+ } else {\r
+ return MR_all_leaves_same_height(t->right,depth);\r
+ };\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_projectTreeOntoSet(Tree *tree,int ck,set *ckset)\r
+#else\r
+void MR_projectTreeOntoSet(tree,ck,ckset)\r
+ Tree *tree;\r
+ int ck;\r
+ set *ckset;\r
+#endif\r
+{\r
+ if (tree == NULL) return;\r
+\r
+ require(tree->token != EpToken,"MR_projectTreeOntoSet: EpToken unexpected\n");\r
+\r
+ MR_projectTreeOntoSet(tree->right,ck,ckset);\r
+ if (tree->token == ALT) {\r
+ MR_projectTreeOntoSet(tree->down,ck,ckset);\r
+ } else {\r
+ if (ck > 1) {\r
+ MR_projectTreeOntoSet(tree->down,ck-1,ckset);\r
+ } else {\r
+ set_orel(tree->token,ckset);\r
+ };\r
+ };\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_comparePredicates(Predicate *a,Predicate *b)\r
+#else\r
+int MR_comparePredicates(a,b)\r
+ Predicate *a;\r
+ Predicate *b;\r
+#endif\r
+{\r
+ Predicate *p;\r
+ Predicate *q;\r
+\r
+ if (a == b) return 1;\r
+ if (a == NULL || b == NULL ) return 0;\r
+ if (a->down == NULL && b->down == NULL) {\r
+\r
+ /* predicate->invert can be set only in the predEntry predicates */\r
+ /* thus they are only visible after the predEntry predicates have been "unfolded" */\r
+\r
+ int sameSource=(a->source == b->source);\r
+ int sameInvert= 1 & (1 +a->inverted + b->inverted +\r
+ a->source->inverted + b->source->inverted);\r
+ int samePredEntry=(a->source->predEntry != NULL\r
+ && b->source->predEntry != NULL\r
+ && a->source->predEntry == b->source->predEntry);\r
+ if (sameInvert && (sameSource || samePredEntry)) {\r
+ if (MR_identicalContext(a,b)) {\r
+ return 1;\r
+ };\r
+ };\r
+ return 0;\r
+ };\r
+ if (a->down == NULL || b->down == NULL) return 0;\r
+ if (a->expr != b->expr) return 0;\r
+\r
+ for (p=a->down; p != NULL; p=p->right) {\r
+ for (q=b->down; q != NULL; q=q->right) {\r
+ if (MR_comparePredicates(p,q)) goto NEXT_P;\r
+ };\r
+ return 0;\r
+NEXT_P:\r
+ continue;\r
+ };\r
+ return 1;\r
+}\r
+\r
+/*\r
+ * action->inverted can be set only when a predicate symbol appears in\r
+ * a rule: "rule : <<!XXX>>? X". It cannot be set under any\r
+ * other circumstances. In particular it cannot be set by\r
+ * "#pred NotA !A" or by "#pred Nota <<!A>>?". The first case\r
+ * creates a predEntry and the predicate expression of that predEntry\r
+ * has inverted set. In the second case, the code for handling "!"\r
+ * is only present in buildAction, which is not called by the #pred\r
+ * semantic routines, only when a <<...>>? is recognized as part of\r
+ * a rule definition.\r
+ *\r
+ * predicate->inverted can only be set by a predicate created by a #pred\r
+ * expression, such as "#pred NotA !A" or "#pred NotXY ! (X && Y) or\r
+ * "#pred XbarY !(X && Y)". In particular, it cannot be set by any\r
+ * predicate expression occurring under any other circumstances.\r
+ * The #pred predicate expresssions are stored with in predEntry->pred\r
+ * and do not normally appear anywhere else until the predicates are\r
+ * "unfolded" in order to recognize redundancies, conflicts, and\r
+ * tautologies.\r
+ *\r
+ * The unfold routine expands all references to #pred expressions.\r
+ *\r
+ * The simplifyInvert goes through and propagates the invert bit so that\r
+ * all OR and AND nodes are un-inverted.\r
+ *\r
+ * Note that !(A and B) => (!A or !B)\r
+ * !(A or B) => (!A and !B)\r
+ *\r
+ * MR_unfold() is called to expand predicate symbols by replacing predicates\r
+ * that reference predicate entries with the copies of the predicate entries.\r
+ * Each reference receives a duplicate of the original. This is necessary\r
+ * because the next phase involves simplification and removal of redundant\r
+ * predicate nodes. Anyway, the point I'm making is that predicate->invert\r
+ * should not be set in any predicate until it has been expanded.\r
+ *\r
+ * This is a recursive structure, but there is no need for "recursive expansion"\r
+ * by which I mean a predicate symbol refers to other predicate symbols which\r
+ * must also be expanded.\r
+ *\r
+ * Recursive expansion is *not* performed by this routine because it is not\r
+ * necessary. Expansion of references is performed by predPrimary when\r
+ * a new predicate symbol is created by referring to others in the pred expr.\r
+ */\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate *MR_unfold(Predicate *pred)\r
+#else\r
+Predicate *MR_unfold(pred)\r
+ Predicate *pred;\r
+#endif\r
+{\r
+ Predicate *result;\r
+\r
+ if (pred == NULL) return NULL;\r
+\r
+ pred->right=MR_unfold(pred->right);\r
+\r
+ if (pred->down == NULL) {\r
+ if (pred->source->predEntry != NULL) {\r
+ if (pred->source->predEntry->pred == NULL) {\r
+ ; /* do nothing */ /* a reference to a literal #pred (perhaps with "!" */\r
+ } else {\r
+ result=predicate_dup_without_context(pred->source->predEntry->pred);\r
+ if (pred->inverted) {\r
+ result->inverted=!result->inverted;\r
+ };\r
+ if (pred->source->inverted) {\r
+ result->inverted=!result->inverted;\r
+ };\r
+ result->right=pred->right;\r
+ pred->right=NULL;\r
+ predicate_free(pred);\r
+/*** result=MR_unfold(result); *** not necessary */ /* recursive expansion */\r
+ return result;\r
+ };\r
+ } else {\r
+ ; /* do nothing */ /* an inline literal predicate */\r
+ };\r
+ } else {\r
+ pred->down=MR_unfold(pred->down);\r
+ };\r
+ return pred;\r
+}\r
+\r
+/* this should be called immediately after MR_unfold() and\r
+ at no other times\r
+*/\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_simplifyInverted(Predicate *pred,int inverted)\r
+#else\r
+void MR_simplifyInverted(pred,inverted)\r
+ Predicate *pred;\r
+ int inverted;\r
+#endif\r
+{\r
+ int newInverted;\r
+\r
+ if (pred == NULL) return;\r
+\r
+ MR_simplifyInverted(pred->right,inverted);\r
+\r
+ newInverted= 1 & (inverted + pred->inverted);\r
+\r
+ if (pred->down == NULL) {\r
+ pred->inverted=newInverted;\r
+ } else {\r
+ if (newInverted != 0) {\r
+ if (pred->expr == PRED_AND_LIST) {\r
+ pred->expr=PRED_OR_LIST;\r
+ } else {\r
+ pred->expr=PRED_AND_LIST;\r
+ };\r
+ };\r
+ pred->inverted=0;\r
+ MR_simplifyInverted(pred->down,newInverted);\r
+ };\r
+}\r
+\r
+/* only remove it from AND and OR nodes, not leaves */\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_clearPredEntry(Predicate *p)\r
+#else\r
+void MR_clearPredEntry(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ if (p == NULL) return;\r
+ MR_clearPredEntry(p->down);\r
+ MR_clearPredEntry(p->right);\r
+ if (p->down != NULL) p->predEntry=NULL;\r
+}\r
+\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_orphanRules(FILE *f)\r
+#else\r
+void MR_orphanRules(f)\r
+ FILE *f;\r
+#endif\r
+{\r
+ set a;\r
+ Junction *p;\r
+ unsigned e;\r
+ RuleEntry *re;\r
+\r
+ a=empty;\r
+\r
+ if (! InfoO) return;\r
+\r
+ for (p=SynDiag; p!=NULL; p = (Junction *)p->p2) {\r
+ if ( (Junction *) (p->end)->p1 == NULL) {\r
+ re=(RuleEntry *) hash_get(Rname,p->rname);\r
+ require (re != NULL,"RuleEntry == NULL");\r
+ set_orel(re->rulenum, &a);\r
+ }\r
+ }\r
+\r
+ if (set_deg(a) > 1) {\r
+ fprintf(f,"note: Start rules: {");\r
+ for (; !set_nil(a); set_rm(e,a)) {\r
+ e=set_int(a);\r
+ fprintf(f," %s",RulePtr[e]->rname);\r
+ };\r
+ fprintf(f," }\n");\r
+ };\r
+ set_free( a );\r
+}\r
+\r
+/* merge (X Y) and (X) to create (X) */\r
+\r
+static int *mergeChain;\r
+static Tree *mergeTree;\r
+\r
+#ifdef __USE_PROTOS\r
+Tree *MR_merge_tree_contexts_client(Tree *t,int chain[])\r
+#else\r
+Tree *MR_merge_tree_contexts_client(t,chain)\r
+ Tree *t;\r
+ int chain[];\r
+#endif\r
+{\r
+ if (t == NULL) return NULL;\r
+ if (chain[0] == 0) {\r
+ Tree *u=t->right;\r
+ t->right=NULL;\r
+ Tfree(t);\r
+ return MR_merge_tree_contexts_client(u,&chain[0]);\r
+ }\r
+ if (chain[0] == t->token) {\r
+ t->down=MR_merge_tree_contexts_client(t->down,&chain[1]);\r
+ };\r
+ t->right=MR_merge_tree_contexts_client(t->right,&chain[0]);\r
+ return t;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_iterateOverTreeContexts(Tree *t,int chain[])\r
+#else\r
+void MR_iterateOverTreeContexts(t,chain)\r
+ Tree *t;\r
+ int chain[];\r
+#endif\r
+{\r
+ if (t == NULL) return;\r
+ chain[0]=t->token;\r
+ if (t->down != NULL) {\r
+ MR_iterateOverTreeContexts(t->down,&chain[1]);\r
+ } else {\r
+ MR_merge_tree_contexts_client(mergeTree,mergeChain);\r
+ };\r
+ MR_iterateOverTreeContexts(t->right,&chain[0]);\r
+ chain[0]=0;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Tree *MR_merge_tree_contexts(Tree *t)\r
+#else\r
+Tree *MR_merge_tree_contexts(t)\r
+ Tree *t;\r
+#endif\r
+{\r
+ int h=MR_max_height_of_tree(t);\r
+\r
+ mergeTree=t;\r
+ mergeChain=(int *) calloc(h+1,sizeof(int));\r
+ require (mergeChain != NULL,"MR_merge_tree_contexts: can't alloc chain");\r
+ MR_iterateOverTreeContexts(t,mergeChain);\r
+ t=tshrink(t);\r
+ t=tflatten(t);\r
+ t=tleft_factor(t);\r
+ free ( (char *) mergeChain);\r
+ mergeChain=NULL;\r
+ return t;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Tree *MR_compute_pred_tree_context(Predicate *p)\r
+#else\r
+Tree *MR_compute_pred_tree_context(p)\r
+ Predicate *p;\r
+#endif\r
+{\r
+ Tree *t;\r
+\r
+ t=MR_compute_pred_tree_ctxXX(p);\r
+ MR_merge_tree_contexts(t);\r
+ return t;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_guardPred_plainSet(ActionNode *anode,Predicate *pred)\r
+#else\r
+void MR_guardPred_plainSet(anode,pred)\r
+ ActionNode *anode;\r
+ Predicate *pred;\r
+#endif\r
+{\r
+ Junction *j;\r
+ Predicate *workPred;\r
+ set maskSet;\r
+\r
+ maskSet=empty;\r
+\r
+ if (!MRhoisting) return;\r
+\r
+ /* it doesn't really matter whether the predicate has\r
+ depth k=1 or k>1 because we're not really looking\r
+ at the predicate itself, just the stuff "behind"\r
+ the predicate.\r
+ */\r
+\r
+ /* shouldn't have to worry about REACHing off the end\r
+ of the rule containing the predicate because the\r
+ Rule->end->halt should have been set already by the\r
+ the code which handles RuleRef nodes.\r
+\r
+ We don't want to REACH off the end of the rule because\r
+ this would give the "global" follow context rather than\r
+ the "local" context.\r
+\r
+ r1a : (A)? => <<p>>? r2 (A|B)\r
+ r1b : (A)? => <<p>>? r2 (A|C)\r
+ r2 : ();\r
+\r
+ For r1a we want follow of predicate = {A B}\r
+ we want plainSet = {B}\r
+ For r1b we want follow of predicate = {A C}\r
+ we want plainSet = {C}\r
+ */\r
+\r
+ require (anode->next->ntype == nJunction,"MR_guardpred_plainSet not Junction");\r
+ j=(Junction *)(anode->next);\r
+\r
+ workPred=predicate_dup_without_context(pred);\r
+ workPred->k=1;\r
+ workPred->scontext[1]=MR_First(1,j, &(workPred->completionSet) );\r
+ MR_complete_predicates(1,workPred);\r
+ if (pred->k == 1) {\r
+ maskSet=pred->scontext[1];\r
+ } else {\r
+ MR_projectTreeOntoSet(pred->tcontext,1,&maskSet);\r
+ }\r
+ pred->plainSet=set_dif(workPred->scontext[1],maskSet);\r
+ predicate_free(workPred);\r
+}\r
+\r
+/*******************************************************************************/\r
+\r
+static Tree * suppressTree;\r
+static int * suppressChain; /* element 0 not used */\r
+static set * suppressSets;\r
+static Node * suppressNode;\r
+static int suppressChainLength;\r
+int MR_SuppressSearch=0;\r
+static int suppressSucceeded;\r
+static Predicate * suppressPredicate;\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_isChain(Tree *t)\r
+#else\r
+int MR_isChain(t)\r
+ Tree *t;\r
+#endif\r
+{\r
+ Tree *u;\r
+\r
+ for (u=t; u != NULL; u=u->down) {\r
+ if (u->right != NULL) return 0;\r
+ }\r
+ return 1;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+int MR_suppressK_client(Tree *tree,int tokensInChain[])\r
+#else\r
+int MR_suppressK_client(tree,tokensInChain)\r
+ Tree *tree;\r
+ int tokensInChain[];\r
+#endif\r
+{\r
+ int i;\r
+ set *save_fset;\r
+ int save_ConstrainSearch;\r
+ set incomplete;\r
+ Tree *t;\r
+\r
+ suppressSucceeded=0; /* volatile */\r
+\r
+ if (suppressSets == NULL) {\r
+ suppressSets=(set *) calloc (CLL_k+1,sizeof(set));\r
+ require (suppressSets != NULL,"MR_suppressK_client: suppressSets alloc");\r
+ };\r
+\r
+ for (suppressChainLength=1;\r
+ tokensInChain[suppressChainLength+1] != 0;\r
+ suppressChainLength++) {};\r
+\r
+ require (suppressChainLength != 0,"MR_suppressK_client: chain empty");\r
+\r
+ for (i=1 ; i <= suppressChainLength ; i++) {\r
+ set_clr(suppressSets[i]);\r
+ set_orel( (unsigned) tokensInChain[i],\r
+ &suppressSets[i]);\r
+ };\r
+\r
+ save_fset=fset;\r
+ save_ConstrainSearch=ConstrainSearch;\r
+\r
+ fset=suppressSets;\r
+\r
+ MR_SuppressSearch=1;\r
+ MR_AmbSourceSearch=1;\r
+ MR_MaintainBackTrace=1;\r
+ ConstrainSearch=1;\r
+\r
+ maxk = suppressChainLength;\r
+\r
+ incomplete=empty;\r
+ t=NULL;\r
+\r
+/*** constrain = &(fset[1]); ***/\r
+\r
+ MR_setConstrainPointer(&(fset[1])); /* MR18 */\r
+ \r
+ MR_pointerStackReset(&MR_BackTraceStack);\r
+\r
+ TRAV(suppressNode,maxk,&incomplete,t);\r
+\r
+ Tfree(t);\r
+\r
+ require (set_nil(incomplete),"MR_suppressK_client TRAV incomplete");\r
+ require (MR_BackTraceStack.count == 0,\r
+ "MR_suppressK_client: MR_BackTraceStack.count != 0");\r
+ set_free(incomplete);\r
+\r
+ ConstrainSearch=save_ConstrainSearch;\r
+ fset=save_fset;\r
+\r
+ MR_AmbSourceSearch=0;\r
+ MR_MaintainBackTrace=0;\r
+ MR_SuppressSearch=0;\r
+ return suppressSucceeded;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+Tree * MR_iterateOverTreeSuppressK(Tree *t,int chain[])\r
+#else\r
+Tree * MR_iterateOverTreeSuppressK(t,chain)\r
+ Tree *t;\r
+ int chain[];\r
+#endif\r
+{\r
+ if (t == NULL) return NULL;\r
+ t->right=MR_iterateOverTreeSuppressK(t->right,&chain[0]);\r
+ chain[0]=t->token;\r
+ if (t->down != NULL) {\r
+ t->down=MR_iterateOverTreeSuppressK(t->down,&chain[1]);\r
+ if (t->down == NULL) {\r
+ Tree *u=t->right;\r
+ t->right=NULL;\r
+ Tfree(t);\r
+ chain[0]=0;\r
+ return u;\r
+ };\r
+ } else {\r
+ MR_suppressK_client(suppressTree,suppressChain);\r
+ if (suppressSucceeded) {\r
+ Tree *u=t->right;\r
+ t->right=NULL;\r
+ Tfree(t);\r
+ chain[0]=0;\r
+ return u;\r
+ };\r
+ };\r
+ chain[0]=0;\r
+ return t;\r
+}\r
+\r
+/* @@@ */\r
+\r
+#ifdef __USE_PROTOS\r
+Predicate * MR_suppressK(Node *j,Predicate *p)\r
+#else\r
+Predicate * MR_suppressK(j,p)\r
+ Node *j;\r
+ Predicate *p;\r
+#endif\r
+{\r
+ Predicate *result;\r
+ int guardPred=0;\r
+ int ampersandPred=0;\r
+ Node *nodePrime;\r
+\r
+ if (! MRhoistingk) {\r
+ return p;\r
+ }\r
+\r
+ if (! MRhoisting) return p;\r
+ if (CLL_k == 1) return p;\r
+\r
+ if (suppressChain == NULL) {\r
+ suppressChain=(int *) calloc(CLL_k+2,sizeof(int));\r
+ require (suppressChain != NULL,"MR_suppressK: can't allocate chain");\r
+ }\r
+\r
+ if (p == NULL) return NULL;\r
+\r
+ if (j->ntype == nJunction) {\r
+ nodePrime=(Node *) MR_junctionWithoutP2( (Junction *) j);\r
+ } else {\r
+ nodePrime=j;\r
+ };\r
+\r
+ p->down=MR_suppressK(j,p->down);\r
+ p->right=MR_suppressK(j,p->right);\r
+ if (p->down != NULL) {\r
+ result=p;\r
+ goto EXIT;\r
+ };\r
+ if (p->k == 1) {\r
+ result=p;\r
+ goto EXIT;\r
+ };\r
+\r
+ if (p->source != NULL) {\r
+ if (p->source->guardpred != NULL) guardPred=1;\r
+ if (p->source->ampersandPred != NULL) ampersandPred=1;\r
+ }\r
+\r
+ suppressPredicate=p;\r
+ suppressNode=nodePrime; /* was j*/\r
+\r
+ suppressTree=p->tcontext;\r
+\r
+ if (guardPred || ampersandPred) {\r
+ p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);\r
+ if (p->tcontext == NULL) {\r
+ predicate_free(p);\r
+ result=NULL;\r
+ goto EXIT;\r
+ };\r
+ } else {\r
+ if (MR_isChain(p->tcontext)) {\r
+ p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);\r
+ if (p->tcontext == NULL) {\r
+ predicate_free(p);\r
+ result=NULL;\r
+ goto EXIT;\r
+ };\r
+ }\r
+ }\r
+ result=p;\r
+EXIT:\r
+ return result;\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_suppressSearchReport(void)\r
+#else\r
+void MR_suppressSearchReport()\r
+#endif\r
+{\r
+ int i;\r
+ Node *p;\r
+ TokNode *tn;\r
+ int depth;\r
+ set setAnd;\r
+\r
+ /* number of tokens in back trace stack matches length of chain */\r
+\r
+ depth=0;\r
+ for (i=0; i < MR_BackTraceStack.count ; i++) {\r
+ p=(Node *) MR_BackTraceStack.data[i];\r
+ if (p->ntype == nToken) depth++;\r
+ };\r
+\r
+ require (depth == suppressChainLength,"depth > suppressChainLength");\r
+\r
+ /* token codes match chain */\r
+\r
+ depth=0;\r
+ for (i=0; i < MR_BackTraceStack.count ; i++) {\r
+ p=(Node *) MR_BackTraceStack.data[i];\r
+ if (p->ntype != nToken) continue;\r
+ tn=(TokNode *) p;\r
+ depth++;\r
+ if (set_nil(tn->tset)) {\r
+ require(set_el( (unsigned) tn->token,fset[depth]),\r
+ "MR_suppressSearchReport: no match to #token in chain");\r
+ } else {\r
+ setAnd=set_and(fset[depth],tn->tset);\r
+ require(!set_nil(setAnd),\r
+ "MR_suppressSearchReport: no match to #token set in chain");\r
+ set_free(setAnd);\r
+ };\r
+ };\r
+\r
+ /* have a match - now remove it from the predicate */\r
+\r
+ suppressSucceeded=1;\r
+\r
+ if (suppressSucceeded) {\r
+ fprintf(output,"\n");\r
+ fprintf(output,"#if 0\n");\r
+ fprintf(output,"\n");\r
+ fprintf(output,"Part (or all) of predicate with depth > 1 suppressed by ");\r
+ fprintf(output,"alternative without predicate\n\n");\r
+ MR_dumpPred(suppressPredicate,1);\r
+ fprintf(output,"The token sequence which is suppressed:");\r
+ fprintf(output," (");\r
+ for (i=1; i <= suppressChainLength; i++) {\r
+ fprintf(output," %s",TerminalString(suppressChain[i]));\r
+ };\r
+ fprintf(output," )\n");\r
+ fprintf(output,"The sequence of references which generate that sequence of tokens:\n\n");\r
+\r
+ MR_backTraceDumpItemReset();\r
+\r
+ for (i=0; i < MR_BackTraceStack.count ; i++) {\r
+ MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);\r
+ };\r
+ fprintf(output,"\n");\r
+ fprintf(output,"#endif\n");\r
+ }\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_markCompromisedRule(Node *n)\r
+#else\r
+void MR_markCompromisedRule(n)\r
+ Node *n;\r
+#endif\r
+{\r
+ RuleEntry *q;\r
+ Node *mark=NULL;\r
+ Junction *j;\r
+\r
+ if (n->ntype == nRuleRef) {\r
+ mark=(Node *) MR_ruleReferenced( (RuleRefNode *) n);\r
+ } else if (n->ntype == nToken) {\r
+ mark=n;\r
+ } else if (n->ntype == nJunction) {\r
+ j=(Junction *)n;\r
+ switch (j->jtype) {\r
+ case aOptBlk:\r
+ case aLoopBlk:\r
+ case RuleBlk:\r
+ case EndRule:\r
+ case aPlusBlk:\r
+ case aLoopBegin:\r
+ mark=n;\r
+ break;\r
+ default:\r
+ break;\r
+ };\r
+ }\r
+\r
+ if (mark == NULL) return;\r
+\r
+ require (RulePtr != NULL,"RulePtr not initialized");\r
+\r
+ q = (RuleEntry *) hash_get(Rname,mark->rname);\r
+ require (q != NULL,"RuleEntry not found");\r
+ set_orel(q->rulenum,&MR_CompromisedRules);\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_alphaBetaTraceReport(void)\r
+#else\r
+void MR_alphaBetaTraceReport()\r
+#endif\r
+{\r
+ int i;\r
+\r
+ if (! AlphaBetaTrace) return;\r
+\r
+ MR_AlphaBetaMessageCount++;\r
+\r
+ fprintf(output,"\n");\r
+ fprintf(output,"#if 0\n");\r
+ fprintf(output,"\n");\r
+ fprintf(output,"Trace of references leading to attempt to compute the follow set of\n");\r
+ fprintf(output,"alpha in an \"(alpha)? beta\" block. It is not possible for antlr to\n");\r
+ fprintf(output,"compute this follow set because it is not known what part of beta has\n");\r
+ fprintf(output,"already been matched by alpha and what part remains to be matched.\n");\r
+ fprintf(output,"\n");\r
+ fprintf(output,"Rules which make use of the incorrect follow set will also be incorrect\n");\r
+ fprintf(output,"\n");\r
+\r
+ MR_backTraceDumpItemReset();\r
+\r
+ for (i=0; i < MR_BackTraceStack.count ; i++) {\r
+ MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);\r
+ if (i < MR_BackTraceStack.count-1) {\r
+ MR_markCompromisedRule( (Node *) MR_BackTraceStack.data[i]);\r
+ };\r
+ };\r
+ fprintf(output,"\n");\r
+ fprintf(output,"#endif\n");\r
+}\r
+\r
+#ifdef __USE_PROTOS\r
+void MR_dumpRuleSet(set s)\r
+#else\r
+void MR_dumpRuleSet(s)\r
+ set s;\r
+#endif\r
+{\r
+ unsigned *cursor;\r
+ unsigned *origin=set_pdq(s);\r
+\r
+ require(origin != NULL,"set_pdq failed");\r
+\r
+ if (RulePtr == NULL) {\r
+ fprintf(stderr,"RulePtr[] not yet initialized");\r
+ } else {\r
+ for (cursor=origin; *cursor != nil ; cursor++) {\r
+/**** if (cursor != origin) fprintf(stderr,","); ****/\r
+ fprintf(stderr," %s",RulePtr[*cursor]->rname);\r
+ fprintf(stderr,"\n");\r
+ };\r
+ free( (char *) origin);\r
+ };\r
+}\r
projects / mirror_edk2.git / blobdiff