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