1 /*
2  * mrhoist.c
3  *
4  * SOFTWARE RIGHTS
5  *
6  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
7  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
8  * company may do whatever they wish with source code distributed with
9  * PCCTS or the code generated by PCCTS, including the incorporation of
10  * PCCTS, or its output, into commerical software.
11  *
12  * We encourage users to develop software with PCCTS.  However, we do ask
13  * that credit is given to us for developing PCCTS.  By "credit",
14  * we mean that if you incorporate our source code into one of your
15  * programs (commercial product, research project, or otherwise) that you
16  * acknowledge this fact somewhere in the documentation, research report,
17  * etc...  If you like PCCTS and have developed a nice tool with the
18  * output, please mention that you developed it using PCCTS.  In
19  * addition, we ask that this header remain intact in our source code.
20  * As long as these guidelines are kept, we expect to continue enhancing
21  * this system and expect to make other tools available as they are
22  * completed.
23  *
24  * ANTLR 1.33MR10
25  *
26  */
27 
28 #include <stdio.h>
29 
30 #include "pcctscfg.h"
31 
32 #include "set.h"
33 #include "syn.h"
34 #include "hash.h"
35 #include "generic.h"
36 #include "dlgdef.h"
37 #include <ctype.h>
38 
39 #ifdef __USE_PROTOS
40 void dumppred(Predicate *);
41 #else
42 void dumppred();
43 #endif
44 
45 /*
46   Try to determine whether predicate "first" is true for
47     all cases where "second" is true.  Comparison takes place
48     without regard to context.
49   Assumes that predicate symbols have been expanded.
50   Assumes that there are no NAND or NOR nodes
51 
52 */
53 
54 #ifdef __USE_PROTOS
MR_secondPredicateUnreachable(Predicate * first,Predicate * second)55 int MR_secondPredicateUnreachable(Predicate *first,Predicate *second)
56 #else
57 int MR_secondPredicateUnreachable(first,second)
58   Predicate     *first;
59   Predicate     *second;
60 #endif
61 {
62   Predicate     *f;
63   Predicate     *s;
64 
65   if (first == NULL) {
66     return 1;
67   } else if (second == NULL) {
68     return 0;
69   } else if (first->down == NULL && second->down == NULL) {
70     if (first->source == second->source &&
71         first->inverted == second->inverted) {
72       return 1; /* look identical - will never reach alt2 */
73     } else {
74       return 0; /* look different */
75     };
76   } else if (first->down == NULL && second->down != NULL) {
77 
78     if (second->expr == PRED_AND_LIST) {
79 
80       /* unreachable if first covers any child of second */
81 
82       for (s=second->down; s != NULL; s=s->right) {
83         if (MR_secondPredicateUnreachable(first,s)) {
84           return 1;
85         };
86       };
87       return 0;
88     } else if (second->expr == PRED_OR_LIST) {
89 
90       /* unreachable if first covers every child of second */
91 
92       for (s=second->down; s != NULL; s=s->right) {
93         if (!MR_secondPredicateUnreachable(first,s)) {
94           return 0;
95         };
96       };
97       return 1;
98     } else {
99       require (0,"Illegal pred->expr");
100       return 0; /* MR20 Make compiler happy */
101     };
102   } else if (first->down != NULL && second->down == NULL) {
103     if (first->expr == PRED_AND_LIST) {
104 
105       /* unreachable if every child of first covers second */
106 
107       for (f=first->down; f != NULL; f=f->right) {
108         if (!MR_secondPredicateUnreachable(f,second)) {
109           return 0;
110         };
111       };
112       return 1;
113     } else if (first->expr == PRED_OR_LIST) {
114 
115       /* unreachable if any child of first covers second */
116 
117       for (f=first->down; f != NULL; f=f->right) {
118         if (MR_secondPredicateUnreachable(f,second)) {
119           return 1;
120         };
121       };
122       return 0;
123     } else {
124       require (0,"Illegal predicate->expr");
125       return 0; /* MR20 Make compiler happy */
126     };
127   } else {
128 
129     if (first->expr == PRED_AND_LIST && second->expr == PRED_AND_LIST) {
130 
131       /* unreachable if each child of first covers at least one child of second */
132 
133       for (f=first->down; f != NULL ; f=f->right) {
134         for (s=second->down; s != NULL ; s=s->right) {
135           if (MR_secondPredicateUnreachable(f,s)) goto A_next_f;
136         };
137         return 0;
138 A_next_f:
139         continue;
140       };
141       return 1;
142 
143     } else if (first->expr == PRED_AND_LIST && second->expr == PRED_OR_LIST) {
144 
145       /* unreachable if each child of first covers ALL of second's children */
146 
147       for (f=first->down; f != NULL ; f=f->right) {
148         for (s=second->down; s != NULL ; s=s->right) {
149           if (!MR_secondPredicateUnreachable(f,s)) return 0;
150         };
151       };
152       return 1;
153 
154     } else if (first->expr == PRED_OR_LIST && second->expr == PRED_AND_LIST) {
155 
156       /* unreachable if any child of second is covered by any child of first */
157 
158       for (f=first->down; f != NULL ; f=f->right) {
159         for (s=second->down; s != NULL ; s=s->right) {
160           if (MR_secondPredicateUnreachable(f,s)) return 1;
161         };
162       };
163       return 0;
164 
165     } else if (first->expr == PRED_OR_LIST && second->expr == PRED_OR_LIST) {
166 
167       /* unreachable if every child of second is covered by some child of first */
168 
169       for (f=first->down; f != NULL ; f=f->right) {
170         for (s=second->down; s != NULL ; s=s->right) {
171           if (MR_secondPredicateUnreachable(f,s)) goto B_next_f;
172         };
173         return 0;
174 B_next_f:
175        continue;
176       };
177       return 1;
178 
179     } else {
180       require (0,"Illegal predicate->expr");
181       return 0; /* MR20 Make compiler happy */
182     };
183   };
184   return 0; /* MR20 MSVC 5.0 complains about missing return statement */
185 }
186 
187 #ifdef __USE_PROTOS
MR_xxxIndent(FILE * f,int depth)188 void MR_xxxIndent(FILE *f,int depth)
189 #else
190 void MR_xxxIndent(f,depth)
191   FILE  *f;
192   int   depth;
193 #endif
194 {
195   int   i;
196 
197   for (i=0; i<depth ; i++) {
198     fprintf(f,"  ");
199   };
200 }
201 
202 #ifdef __USE_PROTOS
MR_stderrIndent(int depth)203 void MR_stderrIndent(int depth)
204 #else
205 void MR_stderrIndent(depth)
206   int   depth;
207 #endif
208 {
209   MR_xxxIndent(stderr,depth);
210 }
211 
212 #ifdef __USE_PROTOS
MR_outputIndent(int depth)213 void MR_outputIndent(int depth)
214 #else
215 void MR_outputIndent(depth)
216   int   depth;
217 #endif
218 {
219   MR_xxxIndent(output,depth);
220 }
221 
222 #ifdef __USE_PROTOS
MR_set_reuse(set * s)223 void MR_set_reuse(set *s)
224 #else
225 void MR_set_reuse(s)
226   set   *s;
227 #endif
228 {
229   set_free(*s);
230   *s=empty;
231 }
232 
233 #ifdef __USE_PROTOS
MR_dumpPredRuleRefStack(FILE * iounit,int indent)234 void MR_dumpPredRuleRefStack(FILE *iounit,int indent)
235 #else
236 void MR_dumpPredRuleRefStack(iounit,indent)
237   FILE  *iounit;
238   int   indent;
239 #endif
240 {
241     int             i;
242     int             j;
243     int             count=MR_PredRuleRefStack.count;
244     RuleRefNode     *rrn=NULL;
245     Junction        *lastOne;
246 
247     if (count == 0) {
248       fprintf(iounit,"empty\n");
249       return;
250     };
251     for (i=0; i < count; i++) {
252       rrn=(RuleRefNode *) MR_PredRuleRefStack.data[i];
253       for (j=0; j<indent; j++) fprintf(iounit," ");
254       fprintf(iounit,"#%-2d in rule %s (line %d %s) to rule %s\n",
255             i,rrn->rname,rrn->line,FileStr[rrn->file],rrn->text);
256     };
257     lastOne=MR_ruleReferenced(rrn);
258     if (lastOne != NULL) {
259       for (j=0; j<indent; j++) fprintf(iounit," ");
260       fprintf(iounit,"#%-2d in rule %s (line %d %s)\n",
261         count,lastOne->rname,lastOne->line,FileStr[lastOne->file]);
262     };
263 }
264 
265 #ifdef __USE_PROTOS
MR_dumpTreeF(FILE * f,int depth,Tree * tree,int across)266 void MR_dumpTreeF(FILE *f,int depth,Tree *tree,int across)
267 #else
268 void MR_dumpTreeF(f,depth,tree,across)
269   FILE  *f;
270   Tree  *tree;
271   int   depth;
272   int   across;
273 #endif
274 {
275     int     newAcross=across;
276 
277 	if (tree == NULL ) return;
278 	if (tree->down != NULL ) {
279       fprintf(output,"\n");
280       MR_outputIndent(depth);
281       fprintf(output, "(root =");
282     };
283 	if (tree->token == ALT ) {
284       fprintf(output," %-16s","Alt");
285 	} else if (tree->token==EpToken ) {
286       fprintf(output,"(%d)%13s",tree->v.rk," ");
287 	} else {
288       fprintf(output," %-16s",TerminalString(tree->token));
289     };
290     if (tree->down != NULL) {
291       fprintf(output,"\n");
292       MR_outputIndent(depth+1);
293       MR_dumpTreeF(f,depth+1,tree->down,1);
294       newAcross=0;
295       fprintf(output,"\n");
296       MR_outputIndent(depth);
297       fprintf(output,")");
298     };
299     if (newAcross > 3) {
300       fprintf(output,"\n");
301       MR_outputIndent(depth);
302       newAcross=0;
303     };
304     MR_dumpTreeF(f,depth,tree->right,newAcross+1);
305 }
306 
307 #ifdef __USE_PROTOS
MR_dumpTreeX(int depth,Tree * tree,int across)308 void MR_dumpTreeX(int depth,Tree *tree,int across)
309 #else
310 void MR_dumpTreeX(depth,tree,across)
311   Tree  *tree;
312   int   depth;
313   int   across;
314 #endif
315 {
316   MR_dumpTreeF(output,depth,tree,across);
317 }
318 
319 #ifdef __USE_PROTOS
MR_dumpTokenSet(FILE * f,int depth,set s)320 void MR_dumpTokenSet(FILE *f,int depth,set s)
321 #else
322 void MR_dumpTokenSet(f,depth,s)
323   FILE  *f;
324   int   depth;
325   set   s;
326 #endif
327 {
328     int     i;
329     int     j;
330 
331     unsigned  *pdq;
332 
333     if (set_nil(s)) {
334       fprintf(f,"\n");
335       MR_xxxIndent(f,depth+1);
336       fprintf(f,"nil\n");
337       return;
338     };
339 
340     pdq=set_pdq(s);
341     require(pdq != NULL,"set_pdq failed");
342     i=0;
343     for (i=0 ; ; i=i+4) {
344       fprintf(f,"\n");
345       MR_xxxIndent(f,depth+1);
346       for (j=0; j < 4 ; j++) {
347         if (pdq[i+j] == nil) break;
348         fprintf(f," %-16s",TerminalString(pdq[i+j]));
349       };
350       if (pdq[i+j] == nil) break;
351     };
352     fprintf(f,"\n");
353     free( (char *) pdq);
354 }
355 
356 #ifdef __USE_PROTOS
MR_dumpPred1(int depth,Predicate * p,int withContext)357 void MR_dumpPred1(int depth,Predicate *p,int withContext)
358 #else
359 void MR_dumpPred1(depth,p,withContext)
360   int           depth;
361   Predicate     *p;
362   int           withContext;
363 #endif
364 {
365   unsigned      k;
366 
367   if (p == NULL) {
368     MR_outputIndent(depth);
369     fprintf(output,"The predicate is empty (or always true)\n\n");
370     return;
371   };
372   if (p->down != NULL) {
373     MR_outputIndent(depth);
374     if (p->inverted) {
375 
376         /* MR14a Left out print expression in fprintf
377                  Reported by Manuel Kessler (mlkessle@cip.physik.uni-wuerzburg.de)
378         */
379 
380       if (p->expr == PRED_AND_LIST) fprintf(output,"%s NAND (not AND) expr\n\n",p->expr);
381       if (p->expr == PRED_OR_LIST) fprintf(output,"%s NOR (not OR) expr\n\n",p->expr);
382     } else {
383       fprintf(output,"%s expr\n\n",p->expr);
384     };
385   } else {
386     MR_outputIndent(depth);
387     fprintf(output,"pred %s <<%s>>?\n",
388             (p->inverted ? " *not*" : ""),
389             (p->expr == NULL ? "null expr" : p->expr));
390     MR_outputIndent(depth+1);
391     fprintf(output,"              ");
392     fprintf(output,"  depth=k=%d",p->k);
393     if (p->source != NULL && p->source->guardpred) {
394       fprintf(output,"  (\"=>\" guard)");
395     }
396     if (p->source != NULL && p->source->ampersandPred != NULL) {
397       fprintf(output,"  (\"&&\" guard)");
398     };
399     k=set_int(p->completionSet);
400     if (k != nil) {
401       fprintf(output," Incomplete Set at k=%d !",k);
402     };
403     k=set_int(p->completionTree);
404     if (k != nil) {
405       fprintf(output," Incomplete Tree at k=%d !",k);
406     };
407     if (p->source != NULL) {
408       fprintf(output,"  rule %s  line %d  %s",
409                     p->source->rname,p->source->line,FileStr[p->source->file]);
410     };
411     fprintf(output,"\n");
412     if (withContext &&
413             (HoistPredicateContext ||
414              ! set_nil(p->scontext[1]) ||
415              p->tcontext != NULL)) {
416       if (p->k == 1) {
417         MR_outputIndent(depth+1);
418         fprintf(output,"set context: ");
419         MR_dumpTokenSet(output,depth+1,p->scontext[1]);
420       }
421       if (p->k != 1) {
422         MR_outputIndent(depth+1);
423         fprintf(output,"tree context:");
424         if (p->tcontext == NULL) {
425           fprintf(output," null");
426         } else {
427           MR_dumpTreeX(depth+2,p->tcontext,0);
428         };
429         fprintf(output,"\n");
430       };
431     };
432     fprintf(output,"\n");
433   };
434   if (p->down != NULL) {
435     MR_dumpPred1(depth+1,p->down,withContext);
436   };
437   if (p->right != NULL) {
438     MR_dumpPred1(depth,p->right,withContext);
439   };
440 }
441 
442 #ifdef __USE_PROTOS
MR_dumpPred(Predicate * p,int withContext)443 void MR_dumpPred(Predicate *p,int withContext)
444 #else
445 void MR_dumpPred(p,withContext)
446   Predicate     *p;
447   int           withContext;
448 #endif
449 {
450   MR_dumpPred1(0,p,withContext);
451 }
452 
453 #ifdef __USE_PROTOS
MR_make_tree_from_set(set s)454 Tree * MR_make_tree_from_set(set s)
455 #else
456 Tree * MR_make_tree_from_set(s)
457   set   s;
458 #endif
459 {
460   Tree  *t=NULL;
461   Tree  *node;
462   Tree  **tp=&t;
463   int   i;
464 
465   unsigned *pdq=set_pdq(s);
466 
467   if (pdq != NULL) {
468     for (i=0 ; pdq[i] != nil ; i++) {
469       node=tnode( (int) pdq[i]);
470       *tp=node;
471       tp=&(node->right);
472     };
473     *tp=NULL;
474     free ( (char *) pdq);
475   };
476   return t;
477 }
478 
479 #ifdef __USE_PROTOS
MR_check_pred_too_long(Predicate * p,set completion)480 void MR_check_pred_too_long(Predicate *p,set completion)
481 #else
482 void MR_check_pred_too_long(p,completion)
483   Predicate     *p;
484   set           completion;
485 #endif
486 {
487   if (p != NULL &&
488       p->source != NULL &&
489       ! p->source->predTooLong) {
490     if ( !set_nil(completion)) {
491       p->source->predTooLong=1;
492 warnFL("It is unusual (but ok) for a semantic predicate to test context past the end of its own rule",
493                                 FileStr[p->source->file],p->source->line);
494     };
495   };
496 }
497 
498 #ifdef __USE_PROTOS
MR_predicate_context_completed(Predicate * p)499 int MR_predicate_context_completed(Predicate *p)
500 #else
501 int MR_predicate_context_completed(p)
502   Predicate     *p;
503 #endif
504 {
505   if (p == NULL) return 1;
506   if (p->expr != PRED_AND_LIST &&
507       p->expr != PRED_OR_LIST) {
508     if ( ! set_nil(p->completionSet)) return 0;
509     if ( ! set_nil(p->completionTree)) return 0;
510   };
511   return MR_predicate_context_completed(p->down) &
512          MR_predicate_context_completed(p->right);
513 }
514 
515 #ifdef __USE_PROTOS
MR_advance(Node * n)516 Node * MR_advance(Node *n)
517 #else
518 Node * MR_advance(n)
519   Node  *n;
520 #endif
521 {
522     if (n == NULL) return NULL;
523     switch (n->ntype) {
524       case nJunction:   return ((Junction *)n)->p1;
525       case nToken:      return ((TokNode *)n)->next;
526       case nRuleRef:    return ((RuleRefNode *)n)->next;
527       case nAction:     return ((ActionNode *)n)->next;
528       default:          return NULL;
529     };
530   return NULL; /* MSVC 5.0 complains about missing return statement */
531 }
532 
533 #ifdef __USE_PROTOS
MR_find_endRule(Node * n)534 Junction * MR_find_endRule(Node *n)
535 #else
536 Junction * MR_find_endRule(n)
537   Node  *n;
538 #endif
539 {
540     Node    *next;
541     if (n == NULL) return NULL;
542     for (next=n; next != NULL; next=MR_advance(next)) {
543       if (next->ntype == nJunction &&
544             ( (Junction *) next)->jtype == EndRule) {
545         break;
546       };
547     };
548     return (Junction *)next;
549 }
550 
551 /*
552    Intersection:  a branch which is shorter is chosen
553    over one which is longer: (A B C) intersect (A B) yields (A B).
554 
555    AND: a branch which is longer is chosen over the one
556    which is shorter: (A B C) AND (A B) yields (A B C)
557 
558 */
559 
560 #ifdef __USE_PROTOS
MR_computeTreeIntersection(Tree * l,Tree * r)561 Tree *MR_computeTreeIntersection(Tree *l,Tree *r)
562 #else
563 Tree *MR_computeTreeIntersection(l,r)
564     Tree    *l;
565     Tree    *r;
566 #endif
567 {
568     Tree    *result=NULL;
569     Tree    **tail;
570     Tree    *p;
571     Tree    *q;
572     Tree    *match;
573 
574     if (l == NULL || r == NULL) return NULL;
575     for (p=l; p != NULL; p=p->right) {
576       require(p->token != EpToken,"MR_computeTreeIntersection: p->EpToken unexpected\n");
577       require (p->token != ALT,"MR_computeTreeIntersection: p->ALT unexpected\n");
578     };
579     for (q=r; q != NULL; q=q->right) {
580       require(q->token != EpToken,"MR_computeTreeIntersection: q->EpToken unexpected\n");
581       require(q->token != ALT,"MR_computeTreeIntersection: q->ALT unexpected\n");
582     };
583 
584     result=tnode(ALT);
585     tail=&(result->down);
586 
587     for (p=l; p != NULL ; p=p->right) {
588       for (q=r; q != NULL ; q=q->right) {
589         if (p->token == q->token) {
590           match=tnode(p->token);
591           match->down=MR_computeTreeIntersection(p->down,q->down);
592           *tail=match;
593           tail=&(match->right);
594         };
595       };
596     };
597 
598     *tail=NULL;
599     result=tshrink(result);
600     result=tflatten( result );
601     result=tleft_factor( result );
602     return result;
603 }
604 
605 /* the predicates which are ANDed together have a common
606    context:  they must all have common roots.  Thus the
607    AND operation is more like an OR operation because
608    branches which are longer are grafted onto shorter
609    branches of the AND tree.  For instance combining
610    (A B C) with (A B C D) gives (A B C D).  There
611    should never be a case of (A B C) and (A B D) because
612    they have the same context.
613 
614    Actually, this may not be true once one throws in
615    guard predicates which are defined by the user, not
616    the context.
617 */
618 
619 /* requires input trees to be in "canonical" format */
620 
621 #ifdef __USE_PROTOS
MR_computeTreeAND(Tree * l,Tree * r)622 Tree *MR_computeTreeAND(Tree *l,Tree *r)
623 #else
624 Tree *MR_computeTreeAND(l,r)
625     Tree    *l;
626     Tree    *r;
627 #endif
628 {
629     Tree    *result=NULL;
630     Tree    **tail;
631     Tree    *p;
632     Tree    *q;
633     Tree    *match;
634 
635     if (l == NULL) return tdup(r);
636     if (r == NULL) return tdup(l);
637 
638     for (p=l; p != NULL; p=p->right) {
639 /**** require(p->token != EpToken,"MR_computeTreeAND: p->EpToken unexpected\n"); ****/
640       require (p->token != ALT,"MR_computeTreeAND: p->ALT unexpected\n");
641     };
642     for (q=r; q != NULL; q=q->right) {
643 /**** require(q->token != EpToken,"MR_computeTreeAND: q->EpToken unexpected\n"); ****/
644       require(q->token != ALT,"MR_computeTreeAND: q->ALT unexpected\n");
645     };
646 
647     result=tnode(ALT);
648     tail=&(result->down);
649 
650     for (p=l; p != NULL ; p=p->right) {
651       for (q=r; q != NULL ; q=q->right) {
652         if (p->token == q->token) {
653           match=tnode(p->token);
654           match->down=MR_computeTreeAND(p->down,q->down);
655           *tail=match;
656           tail=&(match->right);
657         };
658       };
659     };
660 
661     *tail=NULL;
662     result=tshrink(result);
663     result=tflatten( result );
664     result=tleft_factor( result );
665     return result;
666 }
667 
668 #ifdef __USE_PROTOS
MR_union_plain_sets1(Predicate * p,set * theUnion)669 void MR_union_plain_sets1(Predicate *p,set *theUnion)
670 #else
671 void MR_union_plain_sets1(p,theUnion)
672   Predicate     *p;
673   set           *theUnion;
674 #endif
675 {
676   if (p == NULL) return;
677   MR_union_plain_sets1(p->down,theUnion);
678   MR_union_plain_sets1(p->right,theUnion);
679   set_orin(theUnion,p->plainSet);
680   return;
681 }
682 
683 #ifdef __USE_PROTOS
MR_union_plain_sets(Predicate * p)684 set MR_union_plain_sets(Predicate *p)
685 #else
686 set MR_union_plain_sets(p)
687   Predicate     *p;
688 #endif
689 {
690   set   theUnion;
691 
692   theUnion=empty;
693 
694   MR_union_plain_sets1(p,&theUnion);
695   return theUnion;
696 }
697 
698 /* does NOT left factor: do not want to merge
699      (A B) with (A) to get (A B)
700    in fact the opposite: (A B) with (A) gives (A)
701 */
702 
703 #ifdef __USE_PROTOS
MR_compute_pred_tree_ctxXX(Predicate * p)704 Tree *MR_compute_pred_tree_ctxXX(Predicate *p)
705 #else
706 Tree *MR_compute_pred_tree_ctxXX(p)
707   Predicate     *p;
708 #endif
709 {
710     Tree        *result=NULL;
711     Predicate   *q;
712     Tree        *t;
713 
714     if (p == NULL) return NULL;
715 
716 /* this appears strange: why do we OR the context
717    of and AND predicate ?  It is because of the way
718    that predicates are evaluated: if the context is
719    wrong then it's the same as if the predicate was
720    true.  That means that even when one leg of an
721    AND has unmatched context, if the other leg has
722    matched context and is true then the predicate
723    succeeds.  It's only when all the legs have unmatched
724    context that this one can skip evaluation of the
725    predicates.
726 */
727     if (p->expr == PRED_OR_LIST ||
728         p->expr == PRED_AND_LIST) {
729       for (q=p->down; q != NULL ; q=q->right) {
730         t=MR_compute_pred_tree_ctxXX(q);
731         result=tappend(result,t);
732         t=NULL;
733       };
734 
735       result=tshrink(result);
736       result=tflatten( result );
737 
738 /* does NOT left factor: do not want to merge
739      (A B) with (A) to get (A B)
740    in fact the opposite: (A B) with (A) gives (A)
741 */
742 
743 /**** result=tleft_factor( result ); ****/
744       return result;
745     };
746 
747 #if 0
748 **    if (p->expr == PRED_AND_LIST) {
749 **
750 **      Predicate     *l;
751 **      Predicate     *r;
752 **      Tree          *l1;
753 **      Tree          *r1;
754 **      Tree          *prevl1;
755 **
756 **      l=p->down;
757 **      require (l->right != NULL,"MR_compute_pred_tree - AND has only one child");
758 **
759 **/* l1 and r1 should already be in "canonical" format */
760 **
761 **      l1=MR_compute_pred_tree(l);
762 **      for (r=l->right; r != NULL; r=r->right) {
763 **        r1=MR_compute_pred_tree(r);
764 **        prevl1=l1;
765 **        l1=MR_computeTreeAND(l1,r1);
766 **        Tfree(r1);
767 **        Tfree(prevl1);
768 **      };
769 **
770 **/* result from computeTreeAND should be in "canonical" format */
771 **
772 **      result=l1;
773 **
774 **/* result of MR_computeTreeAND should be in "canonical" format */
775 **
776 **      return result;
777 **    };
778 #endif
779 
780     if (p->k == 1) {
781       result=MR_make_tree_from_set(p->scontext[1]);
782     } else {
783       result=tdup(p->tcontext);
784       result=MR_remove_epsilon_from_tree(result);
785       result=tshrink(result);
786       result=tflatten(result);
787       result=tleft_factor(result);
788     };
789     return result;
790 }
791 
792 #ifdef __USE_PROTOS
MR_pred_depth(Predicate * p,int * maxDepth)793 void MR_pred_depth(Predicate *p,int *maxDepth)
794 #else
795 void MR_pred_depth(p,maxDepth)
796   Predicate     *p;
797   int           *maxDepth;
798 #endif
799 {
800   if (p == NULL) return;
801   if (p->expr != PRED_OR_LIST &&
802       p->expr != PRED_AND_LIST) {
803     if (p->k > *maxDepth) *maxDepth=p->k;
804   };
805   MR_pred_depth(p->down,maxDepth);
806   MR_pred_depth(p->right,maxDepth);
807 }
808 
809 /* this computes the OR of all the contexts */
810 
811 #ifdef __USE_PROTOS
MR_compute_pred_set(Predicate * p)812 set MR_compute_pred_set(Predicate *p)
813 #else
814 set MR_compute_pred_set(p)
815   Predicate     *p;
816 #endif
817 {
818     set         result;
819     Predicate   *q;
820 
821     result=empty;
822 
823     if (p == NULL) return empty;
824 
825     if (p->expr == PRED_OR_LIST ||
826         p->expr == PRED_AND_LIST) {         /* yes, I do mean PRED_AND_LIST !   */
827                                             /* remember: r1: (A)? => <<p>>? r2; */
828                                             /*           r2: (B)? => <<q>>? r3; */
829       set   t;
830 
831       t=empty;
832       result=empty;
833 
834       for (q=p->down; q != NULL; q=q->right) {
835         t=MR_compute_pred_set(q);
836         set_orin(&result,t);
837         set_free(t);
838       };
839       return result;
840     } else if (p->k > 1) {
841       return empty;
842     } else {
843       return set_dup(p->scontext[1]);
844     };
845 }
846 
847 #ifdef __USE_PROTOS
MR_First(int ck,Junction * j,set * incomplete)848 set MR_First(int ck,Junction *j,set *incomplete)
849 #else
850 set MR_First(ck,j,incomplete)
851   int       ck;
852   Junction  *j;
853   set       *incomplete;
854 #endif
855 {
856     Junction    *p;
857     set         tokensUsed;
858 
859     tokensUsed=empty;
860 
861 	require(j->ntype==nJunction, "MR_First: non junction passed");
862 
863 	p = analysis_point((Junction *)j->p1);
864 
865 	REACH(p,ck,incomplete,tokensUsed);
866 
867     return tokensUsed;
868 }
869 
870 #ifdef __USE_PROTOS
MR_cleanup_pred_trees(Predicate * p)871 void MR_cleanup_pred_trees(Predicate *p)
872 #else
873 void MR_cleanup_pred_trees(p)
874   Predicate     *p;
875 #endif
876 {
877   Tree      *t;
878 
879   if (p == NULL) return;
880   if (p->expr != PRED_OR_LIST &&
881       p->expr != PRED_AND_LIST) {
882     t=p->tcontext;
883     t=tshrink(t);
884     t=tflatten(t);
885     t=tleft_factor(t);
886     p->tcontext=t;
887   };
888   MR_cleanup_pred_trees(p->down);
889   MR_cleanup_pred_trees(p->right);
890 }
891 
892 /* does NOT return canonical tree */
893 
894 #ifdef __USE_PROTOS
MR_remove_epsilon_from_tree(Tree * t)895 Tree * MR_remove_epsilon_from_tree(Tree *t)
896 #else
897 Tree * MR_remove_epsilon_from_tree(t)
898   Tree  *t;
899 #endif
900 {
901   if (t == NULL) return NULL;
902 
903   /* I think ALT can be ignored as a special case */
904 
905   if (t->token != EpToken) {
906     t->down=MR_remove_epsilon_from_tree(t->down);
907     t->right=MR_remove_epsilon_from_tree(t->right);
908     return t;
909   } else {
910     Tree    *u;
911     u=MR_remove_epsilon_from_tree(t->right);
912     t->right=NULL;
913     Tfree(t);
914     return u;
915   };
916 }
917 
918 #ifdef __USE_PROTOS
MR_complete_set(int predDepth,set * tokensUsed,set * incomplete)919 void MR_complete_set(int predDepth,set *tokensUsed,set *incomplete)
920 #else
921 void MR_complete_set(predDepth,tokensUsed,incomplete)
922   int       predDepth;
923   set       *tokensUsed;
924   set       *incomplete;
925 #endif
926 {
927     int             i;
928     RuleRefNode     *ruleRef;
929 	set             rk2;
930     set             b;
931 	int             k2;
932     Junction        *save_MR_RuleBlkWithHalt;
933 
934     if (set_int(*incomplete) > (unsigned) predDepth) {
935       return;
936     };
937 
938     require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,
939                 "RuleRefStack and RuleBlkWithHaltStack not same size");
940 
941     require(MR_RuleBlkWithHalt == NULL ||
942          (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
943                      "RuleBlkWithHalt has no halt set");
944 
945     save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;
946 
947     if (MR_RuleBlkWithHalt != NULL) {
948       MR_RuleBlkWithHalt->end->halt=FALSE;
949     };
950 
951     for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {
952       ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];
953       if (ruleRef == NULL) continue;
954 
955       MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];
956       if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;
957 
958       rk2=empty;
959       b=empty;
960 
961       while ( !set_nil(*incomplete) ) {
962 		k2=set_int(*incomplete);
963         if (k2 > predDepth) break;                    /* <=== another exit from loop */
964 		set_rm(k2,*incomplete);
965         REACH(ruleRef->next,k2,&rk2,b);
966 		set_orin(tokensUsed,b);
967 		set_free(b);
968       };
969 
970       if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;
971 
972 	  set_orin(incomplete,rk2);                       /* remember what we couldn't do */
973       set_free(rk2);
974 	  if (set_int(*incomplete) > (unsigned) predDepth) break;    /* <=== another exit from loop */
975     };
976 
977     MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;
978     if (MR_RuleBlkWithHalt != NULL) {
979       MR_RuleBlkWithHalt->end->halt=TRUE;
980     };
981 }
982 
983 #ifdef __USE_PROTOS
MR_complete_tree(int predDepth,Tree ** t,set * incomplete)984 void MR_complete_tree(int predDepth,Tree **t,set *incomplete)
985 #else
986 void MR_complete_tree(predDepth,t,incomplete)
987   int       predDepth;
988   Tree      **t;
989   set       *incomplete;
990 #endif
991 {
992     int             i;
993     RuleRefNode     *ruleRef;
994 	set             rk2;
995     Tree            *u;
996 	unsigned        k2;
997     Junction        *save_MR_RuleBlkWithHalt;
998     int             saveConstrainSearch;
999 
1000     if (set_int(*incomplete) > (unsigned) predDepth) {
1001       return;
1002     };
1003 
1004     require(MR_PredRuleRefStack.count == MR_RuleBlkWithHaltStack.count,
1005                 "RuleRefStack and RuleBlkWithHaltStack not same size");
1006 
1007     require(MR_RuleBlkWithHalt == NULL ||
1008          (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),
1009                      "RuleBlkWithHalt has no halt set");
1010 
1011     save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;
1012     saveConstrainSearch=ConstrainSearch;
1013     ConstrainSearch=0;
1014 
1015     if (MR_RuleBlkWithHalt != NULL) {
1016       MR_RuleBlkWithHalt->end->halt=FALSE;
1017     };
1018 
1019     for (i=MR_PredRuleRefStack.count-1; i >= 0 ; i--) {
1020       ruleRef=(RuleRefNode *)MR_PredRuleRefStack.data[i];
1021       if (ruleRef == NULL) continue;
1022 
1023       MR_RuleBlkWithHalt=(Junction *)MR_RuleBlkWithHaltStack.data[i];
1024 
1025       if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=TRUE;
1026 
1027       rk2=empty;
1028 
1029       while ( !set_nil(*incomplete) ) {
1030 		k2 = set_int(*incomplete);
1031         if (k2 > (unsigned) predDepth) break;       /* <=== another exit from loop */
1032 		set_rm(k2,*incomplete);
1033 		u = NULL;
1034 
1035         TRAV(ruleRef->next,k2,&rk2,u);
1036 
1037 			/* any subtrees missing k2 tokens, add u onto end */
1038 
1039 		*t=tlink(*t,u,k2);
1040         Tfree(u);
1041       }
1042 
1043 	  set_orin(incomplete,rk2);         /* remember what we couldn't do */
1044       set_free(rk2);
1045 
1046       if (MR_RuleBlkWithHalt != NULL) MR_RuleBlkWithHalt->end->halt=FALSE;
1047 
1048 	  if (set_int(*incomplete) > (unsigned) predDepth) break;    /* <=== another exit from loop */
1049     };
1050 
1051     MR_RuleBlkWithHalt=save_MR_RuleBlkWithHalt;
1052 
1053     if (MR_RuleBlkWithHalt != NULL) {
1054       MR_RuleBlkWithHalt->end->halt=TRUE;
1055     };
1056     ConstrainSearch=saveConstrainSearch;
1057 }
1058 
1059 #ifdef __USE_PROTOS
MR_complete_predicates(int predDepth,Predicate * pred)1060 void MR_complete_predicates(int predDepth,Predicate *pred)
1061 #else
1062 void MR_complete_predicates(predDepth,pred)
1063   int           predDepth;
1064   Predicate     *pred;
1065 #endif
1066 {
1067   if (pred == NULL) return;
1068   if (pred->expr != PRED_AND_LIST &&
1069       pred->expr != PRED_OR_LIST) {
1070     MR_complete_set(predDepth,&(pred->scontext[1]),&(pred->completionSet));
1071     MR_complete_tree(predDepth,&(pred->tcontext),&(pred->completionTree));
1072   };
1073   MR_complete_predicates(predDepth,pred->down);
1074   MR_complete_predicates(predDepth,pred->right);
1075 }
1076 
1077 #ifdef __USE_PROTOS
MR_junctionWithoutP2(Junction * j)1078 Junction * MR_junctionWithoutP2(Junction *j)
1079 #else
1080 Junction * MR_junctionWithoutP2(j)
1081   Junction  *j;
1082 #endif
1083 {
1084   Junction  *thisAlt;
1085 
1086 /* don't want to follow p2 to the next alternative of this rule */
1087 /* insert a generic node with null p2 if necessary              */
1088 /* however FIRST requires a junction                            */
1089 
1090   thisAlt=j;
1091   if (thisAlt->p2 != NULL) {
1092     if (thisAlt->p1->ntype == nJunction) {
1093       thisAlt=(Junction *) thisAlt->p1;
1094     } else {
1095       thisAlt=newJunction();
1096       thisAlt->p1=j->p1;
1097       thisAlt->rname=j->rname;
1098       thisAlt->file=j->file;
1099       thisAlt->line=j->line;
1100       j->p1=(Node *)thisAlt;
1101     };
1102   };
1103   return thisAlt;
1104 }
1105 
1106 #ifdef __USE_PROTOS
MR_tree_equ(Tree * big,Tree * small)1107 int MR_tree_equ(Tree *big, Tree *small) {
1108 #else
1109 int MR_tree_equ(big,small)
1110   Tree  *big;
1111   Tree  *small;
1112 {
1113 #endif
1114 
1115   Tree      *b;
1116   Tree      *s;
1117   int       bcount=0;
1118   int       scount=0;
1119 
1120   if (small == NULL && big == NULL) return 1;
1121   if (small == NULL) return 0;
1122   if (big == NULL) return 0;
1123 
1124   if (small->token == ALT) {
1125     require(small->right == NULL,
1126                 "MR_tree_equ: small: ALT node has siblings");
1127     return MR_tree_equ(big,small->down);
1128   };
1129   if (big->token == ALT) {
1130     require(big->right == NULL,
1131                 "MR_tree_equ: big: ALT node has siblings");
1132     return MR_tree_equ(big->down,small);
1133   };
1134   for (s=small; s != NULL; s=s->right) {
1135     scount++;
1136     require(s->token != EpToken,"MR_tree_equ: s->EpToken unexpected\n");
1137   };
1138   for (b=big; b != NULL; b=b->right) {
1139     bcount++;
1140     require(b->token != EpToken,"MR_tree_equ: b->EpToken unexpected\n");
1141   };
1142 
1143   if (bcount != scount) return 0;
1144 
1145   for (s=small; s != NULL; s=s->right) {
1146     for (b=big; b!= NULL; b=b->right) {
1147       if (s->token == b->token) {
1148         if (MR_tree_equ(b->down,s->down)) goto next_s;
1149       };
1150     };
1151     return 0;
1152 next_s:
1153     continue;
1154   };
1155   return 1;
1156 }
1157 
1158 /* this does not compare sources - only contexts ! */
1159 
1160 #ifdef __USE_PROTOS
1161 int MR_identicalContext(Predicate *p,Predicate *q)
1162 #else
1163 int MR_identicalContext(p,q)
1164   Predicate     *p;
1165   Predicate     *q;
1166 #endif
1167 {
1168   if (p->k != q->k) return 0;
1169   require ( (p->tcontext == NULL) == (q->tcontext == NULL),
1170         "tcontext inconsistent");
1171   if (p->k == 1) {
1172     return set_equ(p->scontext[1],q->scontext[1]);
1173   } else {
1174     return MR_tree_equ(p->tcontext,q->tcontext);
1175   };
1176 }
1177 
1178 #ifdef __USE_PROTOS
1179 void MR_reportSetSuppression(int predDepth,
1180             set predSet,set plainSet,Junction *jPred,Junction *jPlain,Predicate *p)
1181 #else
1182 void MR_reportSetSuppression(predDepth,predSet,plainSet,jPred,jPlain,p)
1183   int       predDepth;
1184   set       predSet;
1185   set       plainSet;
1186   Junction  *jPred;
1187   Junction  *jPlain;
1188   Predicate *p;
1189 #endif
1190 {
1191   if (InfoP) {
1192     fprintf(output,"\n#if 0\n\n");
1193     fprintf(output,"Hoisting of predicate suppressed by alternative without predicate.\n");
1194     fprintf(output,"The alt without the predicate includes all cases where the predicate is false.\n\n");
1195     fprintf(output,"   WITH predicate: line %d  %s\n",jPred->line,FileStr[jPred->file]);
1196     if (jPlain != NULL) {
1197       fprintf(output,"   WITHOUT predicate: line %d  %s\n",jPlain->line,FileStr[jPlain->file]);
1198     } else {
1199       fprintf(output,"   WITHOUT predicate: all alternatives without predicates (combined)\n");
1200     };
1201     if (predDepth == 1) {
1202       fprintf(output,"\nThe context set for the predicate:\n");
1203       MR_dumpTokenSet(output,1,predSet);
1204     };
1205     fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");
1206     MR_dumpTokenSet(output,1,plainSet);
1207     fprintf(output,"\nThe predicate:\n\n");
1208     MR_dumpPred1(1,p,1);
1209     fprintf(output,"Chain of referenced rules:\n\n");
1210     MR_dumpPredRuleRefStack(output,4);
1211     fprintf(output,"\n#endif\n");
1212   };
1213 }
1214 
1215 #ifdef __USE_PROTOS
1216 void MR_reportSetRestriction(int predDepth,set predSet,set plainSet,
1217             Junction *jPred,Junction *jPlain,Predicate *origPred,Predicate *newPred)
1218 #else
1219 void MR_reportSetRestriction(predDepth,predSet,plainSet,jPred,jPlain,origPred,newPred)
1220   int       predDepth;
1221   set       predSet;
1222   set       plainSet;
1223   Junction  *jPred;
1224   Junction  *jPlain;
1225   Predicate *origPred;
1226   Predicate *newPred;
1227 #endif
1228 {
1229   set       intersect;
1230 
1231   intersect=empty;
1232 
1233   if (! InfoP) return;
1234   fprintf(output,"\n#if 0\n\n");
1235   fprintf(output,"Restricting the context of a predicate because of overlap in the lookahead set\n");
1236   fprintf(output,"  between the alternative with the semantic predicate and one without\n");
1237   fprintf(output,"Without this restriction the alternative without the predicate could not\n");
1238   fprintf(output,"  be reached when input matched the context of the predicate and the predicate\n");
1239   fprintf(output,"  was false.\n\n");
1240 
1241   fprintf(output,"   WITH predicate: line %d  %s\n",jPred->line,FileStr[jPred->file]);
1242   if (jPlain != NULL) {
1243     fprintf(output,"   WITHOUT predicate: line %d  %s\n",jPlain->line,FileStr[jPlain->file]);
1244   } else {
1245     fprintf(output,"   WITHOUT predicate: all alternatives without predicates (combined)\n");
1246   };
1247   if (predDepth == 1) {
1248     fprintf(output,"\nThe original context set for the predicate:\n");
1249     MR_dumpTokenSet(output,1,predSet);
1250   };
1251   fprintf(output,"\nThe lookahead set for the alt WITHOUT the semantic predicate:\n");
1252   MR_dumpTokenSet(output,1,plainSet);
1253   if (predDepth == 1) {
1254     fprintf(output,"\nThe intersection of the two sets\n");
1255     intersect=set_and(predSet,plainSet);
1256     MR_dumpTokenSet(output,1,intersect);
1257     set_free(intersect);
1258   };
1259   fprintf(output,"\nThe original predicate:\n\n");
1260   MR_dumpPred1(1,origPred,1);
1261   fprintf(output,"The new (modified) form of the predicate:\n\n");
1262   MR_dumpPred1(1,newPred,1);
1263   fprintf(output,"#endif\n");
1264 }
1265 
1266 /* don't use Pass3 by itself unless you know that inverted is not important */
1267 
1268 #ifdef __USE_PROTOS
1269 Predicate * MR_removeRedundantPredPass3(Predicate *p)
1270 #else
1271 Predicate * MR_removeRedundantPredPass3(p)
1272   Predicate *p;
1273 #endif
1274 {
1275   Predicate     *q;
1276 
1277   if (p == NULL) return NULL;
1278   p->right=MR_removeRedundantPredPass3(p->right);
1279   p->down=MR_removeRedundantPredPass3(p->down);
1280   if (p->redundant) {
1281     q=p->right;
1282     p->right=NULL;
1283     predicate_free(p);
1284     return q;
1285   };
1286   if (p->expr == PRED_AND_LIST ||
1287       p->expr == PRED_OR_LIST) {
1288     if (p->down == NULL) {
1289       q=p->right;
1290       p->right=NULL;
1291       predicate_free(p);
1292       return q;
1293     };
1294     if (p->down != NULL && p->down->right == NULL) {
1295       q=p->down;
1296       q->right=p->right;
1297       p->right=NULL;
1298       p->down=NULL;
1299       return q;
1300     };
1301   };
1302   return p;
1303 }
1304 
1305 #ifdef __USE_PROTOS
1306 void MR_removeRedundantPredPass2(Predicate *p)
1307 #else
1308 void MR_removeRedundantPredPass2(p)
1309   Predicate *p;
1310 #endif
1311 {
1312   Predicate     *q;
1313 
1314   if (p == NULL) return;
1315 
1316   if (p->expr == PRED_AND_LIST) {
1317     for (q=p->down ; q != NULL ; q=q->right) {
1318       MR_removeRedundantPredPass2(q);
1319       if (q->isConst) {
1320         if (q->constValue == 0) {
1321           p->isConst=1;
1322           p->constValue=0;
1323           return;
1324         } else {
1325           q->redundant=1;
1326         };
1327       };
1328     };
1329   };
1330 
1331   if (p->expr == PRED_OR_LIST) {
1332     for (q=p->down ; q != NULL ; q=q->right) {
1333       MR_removeRedundantPredPass2(q);
1334       if (q->isConst) {
1335         if (q->constValue == 0) {
1336           q->redundant=1;
1337         } else {
1338           p->isConst=1;
1339           p->constValue=1;
1340           return;
1341         };
1342       };
1343     };
1344   };
1345 
1346   return;
1347 }
1348 
1349 #if 0
1350    this totally ignores the implications of guarded predicates
1351      in which the part after the guard could possibly cover a predicate.
1352    that would be much harder:
1353 
1354         rule : (A)? => <<p>>? sub1;     /* 1 */
1355              | (B)? => <<r>>? sub2      /* 2 */
1356         sub1 : (A)? => <<q>>? A B       /* 3 */
1357              | B                        /* 4 - suppresses line 2 */
1358              ;
1359 #endif
1360 
1361 #ifdef __USE_PROTOS
1362 void MR_apply_restriction1(Predicate *pred,set *plainSet,int *changed)
1363 #else
1364 void MR_apply_restriction1(pred,plainSet,changed)
1365   Predicate     *pred;
1366   set           *plainSet;
1367   int           *changed;
1368 #endif
1369 {
1370   if (pred == NULL) return;
1371   MR_apply_restriction1(pred->right,plainSet,changed);
1372   if (pred->down != NULL) {
1373     MR_apply_restriction1(pred->down,plainSet,changed);
1374   } else {
1375     set     t;
1376     if (pred->k == 1) {
1377       t=set_dif(pred->scontext[1],*plainSet);
1378       if (*changed == 0 &&
1379           !set_equ(t,pred->scontext[1])) {
1380         *changed=1;
1381       };
1382       if (set_nil(t)) {
1383         pred->redundant=1;
1384       };
1385       set_free(pred->scontext[1]);
1386       pred->scontext[1]=t;
1387     };
1388   };
1389 }
1390 
1391 #ifdef __USE_PROTOS
1392 void MR_orin_plainSet(Predicate *p,set plainSet)
1393 #else
1394 void MR_orin_plainSet(p,plainSet)
1395   Predicate     *p;
1396   set           plainSet;
1397 #endif
1398 {
1399   if (p == NULL) return;
1400   MR_orin_plainSet(p->down,plainSet);
1401   MR_orin_plainSet(p->right,plainSet);
1402   set_orin(&p->plainSet,plainSet);
1403 }
1404 
1405 Predicate   *PRED_SUPPRESS;
1406 
1407 #ifdef __USE_PROTOS
1408 Predicate * MR_find_in_aSubBlk(Junction *alt)
1409 #else
1410 Predicate * MR_find_in_aSubBlk(alt)
1411   Junction  *alt;
1412 #endif
1413 {
1414     Predicate       *root=NULL;
1415     Predicate       **tail=NULL;
1416 
1417 	Junction        *p;
1418 
1419     int             nAlts=0;
1420     Junction        **jList;
1421     Predicate       **predList;
1422     int             *matchList;
1423     set             predSet;
1424     int             i;
1425     int             j;
1426     int             m;
1427     int             predDepth;
1428     set             incomplete;
1429     set             union_plainSet;
1430     set             setChange;
1431     int             changed;
1432     Predicate       *newPred;
1433     set             setDif;
1434     Predicate       *origPred;
1435     int             depth1=1;             /* const int */
1436     set             *plainContext;
1437     set             plainSet;
1438 
1439     predSet=empty;
1440     incomplete=empty;
1441     union_plainSet=empty;
1442     setChange=empty;
1443     setDif=empty;
1444     plainSet=empty;
1445 
1446     if (PRED_SUPPRESS == NULL) {
1447       PRED_SUPPRESS=new_pred();
1448       PRED_SUPPRESS->expr="Predicate Suppressed";
1449     };
1450 
1451     /* this section just counts the number of "interesting" alternatives  */
1452     /*   in order to allocate arrays                                      */
1453 
1454 	for (p=alt; p!=NULL; p=(Junction *)p->p2) {
1455 	  /* ignore empty alts */
1456 	  if ( p->p1->ntype != nJunction ||
1457 	        ((Junction *)p->p1)->jtype != EndBlk )	{
1458         nAlts++;
1459       };
1460     };
1461 
1462     /* if this is a (...)+ block then don't count the last alt because
1463        it can't be taken until at least one time through the block.
1464        In other words it isn't a real choice until the (...)+ is entered
1465          at which point the hoisting issue is moot.
1466        Maybe look at "ignore" instead ?
1467     */
1468 
1469     if (alt->jtype == aPlusBlk) {
1470       nAlts--;
1471     };
1472 
1473     jList=(Junction **)calloc(nAlts,sizeof(Junction *));
1474     require(jList!=NULL,"cannot allocate MR_find_in_aSubBlk jList");
1475 
1476     plainContext=(set *)calloc(nAlts,sizeof(set));
1477     require(plainContext!=NULL,"cannot allocate MR_find_in_aSubBlk plainContext");
1478     for (m=0; m < nAlts; m++) plainContext[m]=empty;
1479 
1480     predList=(Predicate **)calloc(nAlts,sizeof(Predicate *));
1481     require(predList!=NULL,"cannot allocate MR_find_in_aSubBlk predList");
1482 
1483     matchList=(int *)calloc(nAlts,sizeof(int));
1484     require(matchList!=NULL,"cannot allocate MR_find_in_aSubBlk matchList");
1485 
1486     /* this section just fills in the arrays previously allocated       */
1487     /* the most interesting one is matchList[]                          */
1488     /*                                                                  */
1489     /*   bit 0 => this alt has a semantic pred which is "covered"       */
1490     /*              by an alt without a semantic pred.  Don't hoist.    */
1491 
1492 	for (i=0,p=alt;
1493          p!=NULL && i<nAlts;
1494          i++,p=(Junction *)p->p2) {
1495 
1496 	  /* ignore empty alts */
1497 
1498 	  if ( p->p1->ntype != nJunction ||
1499 	        ((Junction *)p->p1)->jtype != EndBlk )	{
1500         jList[i]=MR_junctionWithoutP2(p);
1501         predList[i]=find_predicates(p->p1);      /* should be jList ????? */
1502         if (predList[i] != NULL) {
1503           MR_cleanup_pred_trees(predList[i]);    /* flatten & left factor */
1504           plainContext[i]=MR_union_plain_sets(predList[i]);
1505         } else {
1506           MR_set_reuse(&plainSet);
1507           MR_set_reuse(&incomplete);
1508           plainSet=MR_First(depth1,jList[i],&incomplete);
1509           MR_complete_set(depth1,&plainSet,&incomplete);
1510           require(set_nil(incomplete),"couldn't complete k=1");
1511           plainContext[i]=plainSet;
1512           plainSet=empty;
1513         };
1514         set_orin(&union_plainSet,plainContext[i]);
1515       };
1516     };
1517 
1518     if (nAlts == 1) {
1519       goto EXIT_SIMPLE;
1520     };
1521 
1522 /*
1523  *  Looking for cases where alt i has a semantic pred and alt j does not.
1524  *  Don't care about cases where lookahead for semantic predicates overlap
1525  *    because normal predicate hoisting does the correct thing automatically.
1526  *  Don't care about cases where lookahead for alts without semantic predicates
1527  *    overlap because normal prediction does the correct thing automatically.
1528  *
1529  *  When we find such a case check for one of three subcases:
1530  *
1531  *      1.  if lookahead for alt i is contained in the lookahead for any
1532  *          alt j then ignore semantic predicate of alt i
1533  *      2.  if lookahead for alt i is not contained in the lookahead for
1534  *          any alt j then add add predicate i to the OR list to be hoisted
1535  *      3.  if lookahead for alt i overlaps the lookahead for some alt j then
1536  *          add a dummy semantic predicate for alt j
1537  *
1538  *  There is an implicit assumption that the context of all alternatives following
1539  *  the rule being processed here are identical (but may vary from hoist to
1540  *  hoist depending on the place where the rule was invoked that led to hoisting
1541  *  these predicates.  In othere words in the fragment:
1542  *
1543  *            ( <<a>>? a1 a2 a3 | <<b>>? b1 b2 b3 )
1544  *
1545  *  both a3 and b3 have the same follow sets  because they are both at the end of
1546  *  alternatives in the same block.
1547  */
1548 
1549     for (i=0; i < nAlts; i++) {
1550       if (jList[i] == NULL) continue;
1551       if (predList[i] == NULL) continue;
1552 
1553         /* if the predicate depth turns out to be one token only */
1554         /*   then it is can be easily represented as a set and   */
1555         /*   compared to the junction set create by MR_First()   */
1556 
1557       predDepth=0;
1558       MR_pred_depth(predList[i],&predDepth);
1559       require (predDepth >= 1,"MR_find_in_aSubBlk: pred depth < 1");
1560       require (predDepth <= CLL_k,"MR_find_in_aSubBlk: predDepth > CLL_k");
1561 
1562         /* complete predicates to predDepth
1563            If completed to depth=1 then the context would be incomplete.
1564            The context would be truncated and the predicate simplify routine
1565              would have incomplete information.  It would lead to
1566              either false matches of failure to find true matches.
1567         */
1568 
1569       MR_complete_predicates(predDepth,predList[i]);
1570 
1571       if (predList[i] != NULL) {
1572         MR_cleanup_pred_trees(predList[i]);    /* flatten & left factor */
1573       };
1574 
1575       /* If the predicate depth is 1 then it is possible to suppress
1576            a predicate completely using a single plain alt.  Check for suppression
1577            by a single plain alt first because it gives better messages.  If that
1578            fails try the union of all the plain alts.
1579       */
1580 
1581       if (predDepth == 1) {
1582 
1583         MR_set_reuse(&predSet);
1584         predSet=MR_compute_pred_set(predList[i]);   /* ignores k>1 predicates */
1585 
1586         for (j=0; j < nAlts; j++) {
1587           if (jList[j] == NULL) continue;
1588           if (j == i) continue;
1589 
1590           MR_set_reuse(&setDif);
1591           setDif=set_dif(predSet,plainContext[j]);
1592           if (set_nil(setDif)) {
1593             matchList[i] |= 1;
1594             MR_reportSetSuppression(predDepth,predSet,plainContext[j],jList[i],jList[j],predList[i]);
1595             predicate_free(predList[i]);
1596             predList[i]=PRED_SUPPRESS;
1597             goto next_i;
1598           };
1599 
1600         }; /* end loop on j */
1601 
1602         changed=0;
1603 
1604         /* predicate_dup is only to give good error messages */
1605         /* remember to do a predicate_free()                 */
1606 
1607         origPred=predicate_dup(predList[i]);
1608         MR_apply_restriction1(predList[i],&union_plainSet,&changed);
1609         if (changed) {
1610 
1611           /* don't use Pass3 by itself unless you know that inverted is not important */
1612 
1613           newPred=MR_removeRedundantPredPass3(predList[i]);
1614           newPred=MR_predSimplifyALL(newPred);
1615           if (newPred == NULL) {
1616             matchList[i] |= 1;
1617             MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
1618                                                             NULL,origPred);
1619             predList[i]=PRED_SUPPRESS;
1620           } else {
1621             MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
1622                                                     NULL,origPred,newPred);
1623             predList[i]=newPred;
1624           };
1625         };
1626         predicate_free(origPred);
1627         origPred=NULL;
1628       };
1629 
1630       /*
1631          If the predicate depth is > 1 then it can't be suppressed completely
1632            because the code doesn't support inspection of such things.  They're
1633            much messier than k=1 sets.
1634       */
1635 
1636       if (predDepth > 1 ) {
1637 
1638         changed=0;
1639 
1640         /* predicate_dup is only to give good error messages */
1641         /* remember to do a predicate_free()                 */
1642 
1643         origPred=predicate_dup(predList[i]);
1644         MR_apply_restriction1(predList[i],&union_plainSet,&changed);
1645         if (changed) {
1646           newPred=MR_removeRedundantPredPass3(predList[i]);
1647           newPred=MR_predSimplifyALL(newPred);
1648           if (newPred == NULL) {
1649             matchList[i] |= 1;
1650             MR_reportSetSuppression(predDepth,predSet,union_plainSet,jList[i],
1651                                                             NULL,origPred);
1652             predList[i]=PRED_SUPPRESS;
1653           } else {
1654             MR_reportSetRestriction(predDepth,predSet,union_plainSet,jList[i],
1655                                                     NULL,origPred,newPred);
1656             predList[i]=newPred;
1657           };
1658         };
1659         predicate_free(origPred);
1660         origPred=NULL;
1661       };
1662 next_i:
1663       continue;
1664     };
1665 
1666 EXIT_SIMPLE:
1667 
1668     root = new_pred();
1669     root->expr=PRED_OR_LIST;
1670     tail = &(root->down);
1671 
1672     for (i=0 ; i< nAlts ; i++) {
1673       if (jList[i] == NULL) continue;
1674 
1675       if (predList[i] == NULL) {
1676         continue;
1677       } else if ( (matchList[i] & 1) != 0) {
1678         if (predList[i] != PRED_SUPPRESS) {
1679           predicate_free(predList[i]);
1680         };
1681         continue;
1682       };
1683 
1684       /* make an OR list of predicates */
1685 
1686       *tail=predList[i];
1687       tail=&(predList[i]->right);
1688     };
1689 
1690 	/* if just one pred, remove OR root */
1691 
1692 	if (root->down == NULL) {
1693       predicate_free(root);
1694       root=NULL;
1695     } else if (root->down->right == NULL) {
1696       Predicate     *p=root->down;
1697       root->down=NULL;
1698       predicate_free(root);
1699       root=p;
1700 	}
1701 
1702     root=MR_predSimplifyALL(root);
1703 
1704     MR_orin_plainSet(root,union_plainSet);
1705 
1706     set_free(predSet);
1707     set_free(union_plainSet);
1708     set_free(incomplete);
1709     set_free(setChange);
1710     set_free(setDif);
1711 
1712     for (m=0; m < nAlts; m++) set_free(plainContext[m]);
1713 
1714     free ( (char *) jList);
1715     free ( (char *) predList);
1716     free ( (char *) matchList);
1717     free ( (char *) plainContext);
1718 
1719 	return root;
1720 }
1721 
1722 #ifdef __USE_PROTOS
1723 void MR_predContextPresent(Predicate *p,int *allHaveContext,int *noneHaveContext)
1724 #else
1725 void MR_predContextPresent(p,allHaveContext,noneHaveContext)
1726   Predicate     *p;
1727   int           *allHaveContext;
1728   int           *noneHaveContext;
1729 #endif
1730 {
1731   if (p == NULL) return;
1732   MR_predContextPresent(p->right,allHaveContext,noneHaveContext);
1733   if (p->expr != PRED_AND_LIST &&
1734       p->expr != PRED_OR_LIST) {
1735     if (set_nil(p->scontext[1]) == 0 ||
1736             (p->tcontext != NULL)) {
1737       *noneHaveContext=0;
1738     } else {
1739       *allHaveContext=0;
1740     };
1741   };
1742   MR_predContextPresent(p->down,allHaveContext,noneHaveContext);
1743 }
1744 
1745 #ifdef __USE_PROTOS
1746 int MR_pointerStackPush(PointerStack *ps,void *dataPointer)
1747 #else
1748 int MR_pointerStackPush(ps,dataPointer)
1749   PointerStack  *ps;
1750   void          *dataPointer;
1751 #endif
1752 {
1753   void             **newStack;
1754   int              newSize;
1755   int              i;
1756 
1757   if (ps->count == ps->size) {
1758     newSize=20+ps->size*2;
1759     newStack=(void **)calloc(newSize,sizeof(void *));
1760     require (newStack != NULL,"cannot allocate PointerStack");
1761     for (i=0; i < ps->size; i++) {
1762       newStack[i]=ps->data[i];
1763     };
1764     if (ps->data != NULL) free( (char *) ps->data);
1765     ps->data=newStack;
1766     ps->size=newSize;
1767   };
1768   ps->data[ps->count]=dataPointer;
1769   ps->count++;
1770   return ps->count-1;
1771 }
1772 
1773 #ifdef __USE_PROTOS
1774 void * MR_pointerStackPop(PointerStack *ps)
1775 #else
1776 void * MR_pointerStackPop(ps)
1777   PointerStack  *ps;
1778 #endif
1779 {
1780   void  *dataPointer;
1781 
1782   require(ps->count > 0,"MR_pointerStackPop underflow");
1783 
1784   dataPointer=ps->data[ps->count-1];
1785   ps->data[ps->count-1]=NULL;
1786   (ps->count)--;
1787   return dataPointer;
1788 }
1789 
1790 #ifdef __USE_PROTOS
1791 void * MR_pointerStackTop(PointerStack *ps)
1792 #else
1793 void * MR_pointerStackTop(ps)
1794   PointerStack  *ps;
1795 #endif
1796 {
1797   require(ps->count > 0,"MR_pointerStackTop underflow");
1798   return ps->data[ps->count-1];
1799 }
1800 
1801 #ifdef __USE_PROTOS
1802 void MR_pointerStackReset(PointerStack *ps)
1803 #else
1804 void MR_pointerStackReset(ps)
1805   PointerStack  *ps;
1806 #endif
1807 {
1808   int i;
1809   if (ps->data != NULL) {
1810     for (i=0; i < ps->count ; i++) {
1811        ps->data[i]=NULL;
1812     };
1813   };
1814   ps->count=0;
1815 }
1816 
1817 #ifdef __USE_PROTOS
1818 Junction *MR_nameToRuleBlk(char *name)
1819 #else
1820 Junction *MR_nameToRuleBlk(name)
1821   char  *name;
1822 #endif
1823 {
1824     RuleEntry *q;
1825 
1826     require (RulePtr != NULL,"MR_nameToRule: RulePtr not initialized");
1827 
1828     if (name == NULL) return NULL;
1829 
1830     q = (RuleEntry *) hash_get(Rname,name);
1831 
1832 	if ( q == NULL ) {
1833       return NULL;
1834     } else {
1835       return RulePtr[q->rulenum];
1836     };
1837 }
1838 
1839 #ifdef __USE_PROTOS
1840 Junction * MR_ruleReferenced(RuleRefNode *rrn)
1841 #else
1842 Junction * MR_ruleReferenced(rrn)
1843   RuleRefNode   *rrn;
1844 #endif
1845 {
1846     return MR_nameToRuleBlk(rrn->text);
1847 }
1848 
1849 #ifdef __USE_PROTOS
1850 void MR_comparePredLeaves(Predicate *me,Predicate *myParent,Predicate *him,Predicate *hisParent)
1851 #else
1852 void MR_comparePredLeaves(me,myParent,him,hisParent)
1853     Predicate *me;
1854     Predicate *myParent;
1855     Predicate *him;
1856     Predicate *hisParent;
1857 #endif
1858 {
1859     if (me == NULL) return;
1860     if (me == him) {
1861       MR_comparePredLeaves(me->right,myParent,him,hisParent);
1862       return;
1863     } else if (me->expr == PRED_AND_LIST ||
1864                me->expr == PRED_OR_LIST) {
1865       MR_comparePredLeaves(me->down,me,him,hisParent);
1866       MR_comparePredLeaves(me->right,myParent,him,hisParent);
1867       return;
1868     } else {
1869       if (me->source != NULL) {
1870 
1871         /* predicate->invert can be set only in the predEntry predicates        */
1872         /* thus they are only visible after the predEntry predicates have been "unfolded" */
1873 
1874         int     sameSource=(me->source == him->source);
1875         int     sameInvert=1 &
1876                  (1 + me->inverted + him->inverted + me->source->inverted + him->source->inverted);
1877         int     samePredEntry=(me->source->predEntry != NULL
1878                                  && him->source->predEntry != NULL
1879                                     && me->source->predEntry == him->source->predEntry);
1880         if (sameInvert && (sameSource || samePredEntry)) {
1881           if (MR_identicalContext(me,him)) {
1882 
1883             /* identical predicates */
1884 
1885             if (hisParent->expr == PRED_OR_LIST &&
1886                 myParent->expr == PRED_OR_LIST) {
1887               me->redundant=1;
1888             } else if (hisParent->expr == PRED_AND_LIST &&
1889                        myParent->expr == PRED_AND_LIST) {
1890               me->redundant=1;
1891             } else if (  (hisParent->expr == PRED_OR_LIST &&
1892                           myParent->expr == PRED_AND_LIST)
1893                        ||
1894                          (hisParent->expr == PRED_AND_LIST &&
1895                           myParent->expr == PRED_OR_LIST)
1896                       ) {
1897               myParent->redundant=1;
1898             } else {
1899               require (0,"MR_comparePredLeaves: not both PRED_LIST");
1900             };
1901           };
1902         };  /* end same source or same predEntrr with same invert sense */
1903 
1904         /* same predEntry but opposite invert sense */
1905 
1906         if (!sameInvert && (sameSource || samePredEntry)) {
1907           if (MR_identicalContext(me,him)) {
1908             if (hisParent->expr == PRED_OR_LIST &&
1909                 myParent->expr == PRED_OR_LIST) {
1910               myParent->isConst=1;
1911               myParent->constValue=1;
1912             } else if (hisParent->expr == PRED_AND_LIST &&
1913                        myParent->expr == PRED_AND_LIST) {
1914               myParent->isConst=1;
1915               myParent->constValue=0;
1916             } else if (  (hisParent->expr == PRED_OR_LIST &&
1917                           myParent->expr == PRED_AND_LIST)
1918                        ||
1919                          (hisParent->expr == PRED_AND_LIST &&
1920                           myParent->expr == PRED_OR_LIST)
1921                       ) {
1922               me->redundant=1;
1923             } else {
1924               require (0,"MR_comparePredLeaves: not both PRED_LIST");
1925             };
1926           };
1927         };  /* end same predEntry with opposite invert sense */
1928       };
1929 
1930       MR_comparePredLeaves(me->right,myParent,him,hisParent);
1931       return;
1932     };
1933 }
1934 
1935 #ifdef __USE_PROTOS
1936 void MR_removeRedundantPredPass1(Predicate *me,Predicate *myParent)
1937 #else
1938 void MR_removeRedundantPredPass1(me,myParent)
1939   Predicate     *me;
1940   Predicate     *myParent;
1941 #endif
1942 {
1943     if (me == NULL) return;
1944     if (me->redundant) {
1945       MR_removeRedundantPredPass1(me->right,myParent);
1946       return;
1947     };
1948     if (me->expr == PRED_AND_LIST ||
1949         me->expr == PRED_OR_LIST) {
1950       MR_removeRedundantPredPass1(me->down,me);
1951       MR_removeRedundantPredPass1(me->right,myParent);
1952     } else {
1953       require (me->source != NULL,"me->source == NULL");
1954       if (myParent != NULL) {
1955         MR_comparePredLeaves(myParent->down,myParent,me,myParent);
1956       };
1957       MR_removeRedundantPredPass1(me->right,myParent);
1958     };
1959 }
1960 
1961 /* pretty much ignores things with the inverted bit set */
1962 
1963 #ifdef __USE_PROTOS
1964 Predicate *MR_predFlatten(Predicate *p)
1965 #else
1966 Predicate *MR_predFlatten(p)
1967   Predicate     *p;
1968 #endif
1969 {
1970     if (p == NULL) return NULL;
1971     if (p->expr == PRED_OR_LIST
1972         || p->expr == PRED_AND_LIST) {
1973 
1974       Predicate     *child;
1975       Predicate     *gchild;
1976       Predicate     **tail;
1977       Predicate     *next;
1978       char          *PRED_XXX_LIST=p->expr;
1979 
1980       require (p->down != NULL,"MR_predFlatten AND/OR no child");
1981 
1982 
1983       p->down=MR_predFlatten(p->down);
1984       p->right=MR_predFlatten(p->right);
1985       child=p->down;
1986       if (child->right == NULL) {
1987         child->right=p->right;
1988         p->right=NULL;
1989         p->down=NULL;
1990         if (p->inverted) child->inverted=!child->inverted;
1991         predicate_free(p);
1992         return child;
1993       };
1994 
1995       /* make a single list of all children and grandchildren */
1996 
1997       tail=&(p->down);
1998       for (child=p->down; child != NULL; child=next) {
1999         if (child->expr != PRED_XXX_LIST
2000               || child->inverted
2001                 || child->predEntry != NULL) {
2002           *tail=child;
2003           tail=&(child->right);
2004           next=child->right;
2005         } else {
2006           for (gchild=child->down;
2007                gchild != NULL;
2008                gchild=gchild->right) {
2009             *tail=gchild;
2010             tail=&(gchild->right);
2011           };
2012           next=child->right;
2013           child->right=NULL;
2014           child->down=NULL;
2015           predicate_free(child);
2016         };
2017       };
2018       *tail=NULL;
2019       return p;
2020     } else {
2021       p->right=MR_predFlatten(p->right);
2022       return p;
2023     };
2024 }
2025 
2026 static char *alwaysFalseWarning=NULL;
2027 
2028 #ifdef __USE_PROTOS
2029 Predicate *checkPredicateConflict(Predicate *p)
2030 #else
2031 Predicate *checkPredicateConflict(p)
2032   Predicate     *p;
2033 #endif
2034 {
2035   if (p->isConst) {
2036     if (p->constValue == 1) {
2037       predicate_free(p);
2038       return NULL;
2039     } else {
2040       if (InfoP && !p->conflictReported) {
2041         p->conflictReported=1;
2042         fprintf(output,"\n#if 0\n\n");
2043         fprintf(output,"The following predicate expression will always be false:\n\n");
2044         MR_dumpPred1(1,p,1);
2045         fprintf(output,"\n#endif\n");
2046       };
2047 
2048       if (alwaysFalseWarning != CurRule) {
2049         alwaysFalseWarning=CurRule;
2050         if (InfoP) {
2051           warnNoFL(eMsg1("one (or more) predicate expression hoisted into rule \"%s\" are always false \
2052 - see output file for more information",CurRule));
2053         } else {
2054           warnNoFL(eMsg1("one (or more) predicate expressions hoisted into rule \"%s\" are always false \
2055 - use \"-info p\" for more information",CurRule));
2056         };
2057       };
2058     };
2059   };
2060   return p;
2061 }
2062 
2063 
2064 #ifdef __USE_PROTOS
2065 int MR_countPredNodes(Predicate *p)
2066 #else
2067 int MR_countPredNodes(p)
2068   Predicate     *p;
2069 #endif
2070 {
2071   if (p == NULL) return 0;
2072   return 1 + MR_countPredNodes(p->down) + MR_countPredNodes(p->right);
2073 }
2074 
2075 #ifdef __USE_PROTOS
2076 Predicate *MR_predSimplifyALLX(Predicate *p,int skipPass3)
2077 #else
2078 Predicate *MR_predSimplifyALLX(p,skipPass3)
2079   Predicate     *p;
2080   int           skipPass3;
2081 #endif
2082 {
2083   int       countBefore;
2084   int       countAfter;
2085 
2086   countAfter=MR_countPredNodes(p);
2087 
2088   do {
2089       if (p == NULL) return NULL;
2090       if (p->right == NULL && p->down == NULL) return p;
2091       countBefore=countAfter;
2092       MR_simplifyInverted(p,0);
2093       p=MR_predFlatten(p);
2094       MR_removeRedundantPredPass1(p,NULL);
2095       MR_removeRedundantPredPass2(p);
2096       if (! skipPass3) {
2097         p=checkPredicateConflict(p);
2098         p=MR_removeRedundantPredPass3(p);
2099       };
2100       countAfter=MR_countPredNodes(p);
2101   } while (countBefore != countAfter);
2102 
2103   return p;
2104 }
2105 
2106 #ifdef __USE_PROTOS
2107 Predicate *MR_predSimplifyALL(Predicate *p)
2108 #else
2109 Predicate *MR_predSimplifyALL(p)
2110   Predicate     *p;
2111 #endif
2112 {
2113   return MR_predSimplifyALLX(p,0);
2114 }
2115 
2116 #ifdef __USE_PROTOS
2117 void MR_releaseResourcesUsedInRule(Node *n)
2118 #else
2119 void MR_releaseResourcesUsedInRule(n)
2120   Node  *n;
2121 #endif
2122 {
2123    Node         *next;
2124    Junction     *j;
2125    int          i;
2126 
2127    if (n == NULL) return;
2128    if (n->ntype == nJunction) {
2129      j=(Junction *) n;
2130 
2131      if (j->predicate != NULL) {
2132        predicate_free(j->predicate);
2133        j->predicate=NULL;
2134      };
2135      for (i=0; i< CLL_k; i++) {
2136        set_free(j->fset[i]);
2137        j->fset[i]=empty;
2138      };
2139      if (j->ftree != NULL) {
2140        Tfree(j->ftree);
2141        j->ftree=NULL;
2142      };
2143      if (j->jtype == EndRule) return;
2144      if (j->jtype != RuleBlk && j->jtype != EndBlk) {
2145        if (j->p2 != NULL && !j->ignore) {   /* MR11 */
2146           MR_releaseResourcesUsedInRule(j->p2);
2147        };
2148      };
2149    };
2150    next=MR_advance(n);
2151    MR_releaseResourcesUsedInRule(next);
2152 }
2153 
2154 #ifdef __USE_PROTOS
2155 int MR_allPredLeaves(Predicate *p)
2156 #else
2157 int MR_allPredLeaves(p)
2158   Predicate *p;
2159 #endif
2160 {
2161   Predicate     *q;
2162 
2163   if (p == NULL) return 1;
2164 
2165   for (q=p; q != NULL; q=q->right) {
2166    if (q->down != NULL) return 0;
2167   };
2168   return 1;
2169 }
2170 
2171 /* make sure it works for the last rule in a file */
2172 
2173 #ifdef __USE_PROTOS
2174 int MR_offsetFromRule(Node *n)
2175 #else
2176 int MR_offsetFromRule(n)
2177   Node      *n;
2178 #endif
2179 {
2180   Junction  *j;
2181   int       offset=(-1);
2182 
2183   for (j=SynDiag; j != NULL; j=(Junction *)j->p2) {
2184 
2185     require (j->ntype == nJunction && j->jtype == RuleBlk,"Not a rule block");
2186 
2187     if (n->file < j->file) {
2188       return offset;
2189     };
2190     if (n->file == j->file) {
2191       if (n->line < j->line) {
2192         return (offset < 0) ? 0 : offset;
2193       } else {
2194         offset=n->line - j->line;
2195         if (offset == 0) return 0;
2196       };
2197     };
2198   };
2199   return offset;
2200 }
2201 
2202 #define ruleNameMax 50
2203 
2204 static char ruleNameStatic1[ruleNameMax];
2205 static char ruleNameStatic2[ruleNameMax+10];
2206 
2207 #ifdef __USE_PROTOS
2208 char * MR_ruleNamePlusOffset(Node *n)
2209 #else
2210 char * MR_ruleNamePlusOffset(n)
2211   Node      *n;
2212 #endif
2213 {
2214     int     offset=MR_offsetFromRule(n);
2215 
2216     strncpy(ruleNameStatic1,n->rname,ruleNameMax);
2217     if (offset < 0) {
2218       sprintf(ruleNameStatic2,"%s/?",ruleNameStatic1);
2219     } else {
2220       sprintf(ruleNameStatic2,"%s/%d",ruleNameStatic1,offset+1);
2221     };
2222     return ruleNameStatic2;
2223 }
2224 
2225 #ifdef __USE_PROTOS
2226 int MR_max_height_of_tree(Tree *t)
2227 #else
2228 int MR_max_height_of_tree(t)
2229   Tree  *t;
2230 #endif
2231 {
2232   int       h;
2233   int       height=0;
2234   Tree      *u;
2235 
2236   if (t == NULL) return 0;
2237 
2238   require (t->token != ALT && t->token != EpToken,"MR_max_height_of_tree ALT or EpToken");
2239 
2240   for (u=t; u != NULL; u=u->right) {
2241     h=MR_max_height_of_tree(u->down)+1;
2242     if (h > height) height=h;
2243   };
2244   return height;
2245 }
2246 
2247 #ifdef __USE_PROTOS
2248 int MR_all_leaves_same_height(Tree *t,int depth)
2249 #else
2250 int MR_all_leaves_same_height(t,depth)
2251   Tree  *t;
2252   int   depth;
2253 #endif
2254 {
2255   if (t == NULL) {
2256     return (depth==0);
2257   };
2258 
2259   require (t->token != ALT && t->token != EpToken,"MR_all_leaves_same_height ALT or EpToken");
2260 
2261   if (depth == 0) {
2262     return 0;
2263   } else {
2264     if ( ! MR_all_leaves_same_height(t->down,depth-1)) {
2265       return 0;
2266     };
2267     if (t->right == NULL) {
2268       return 1;
2269     } else {
2270       return MR_all_leaves_same_height(t->right,depth);
2271     };
2272   };
2273 }
2274 
2275 #ifdef __USE_PROTOS
2276 void MR_projectTreeOntoSet(Tree *tree,int ck,set *ckset)
2277 #else
2278 void MR_projectTreeOntoSet(tree,ck,ckset)
2279   Tree  *tree;
2280   int   ck;
2281   set   *ckset;
2282 #endif
2283 {
2284     if (tree == NULL) return;
2285 
2286     require(tree->token != EpToken,"MR_projectTreeOntoSet: EpToken unexpected\n");
2287 
2288     MR_projectTreeOntoSet(tree->right,ck,ckset);
2289     if (tree->token == ALT) {
2290       MR_projectTreeOntoSet(tree->down,ck,ckset);
2291     } else {
2292       if (ck > 1) {
2293         MR_projectTreeOntoSet(tree->down,ck-1,ckset);
2294       } else {
2295         set_orel(tree->token,ckset);
2296       };
2297     };
2298 }
2299 
2300 #ifdef __USE_PROTOS
2301 int MR_comparePredicates(Predicate *a,Predicate *b)
2302 #else
2303 int MR_comparePredicates(a,b)
2304   Predicate     *a;
2305   Predicate     *b;
2306 #endif
2307 {
2308   Predicate     *p;
2309   Predicate     *q;
2310 
2311   if (a == b) return 1;
2312   if (a == NULL || b == NULL ) return 0;
2313   if (a->down == NULL && b->down == NULL) {
2314 
2315     /* predicate->invert can be set only in the predEntry predicates                  */
2316     /* thus they are only visible after the predEntry predicates have been "unfolded" */
2317 
2318     int     sameSource=(a->source == b->source);
2319     int     sameInvert= 1 & (1 +a->inverted + b->inverted +
2320                                 a->source->inverted + b->source->inverted);
2321     int     samePredEntry=(a->source->predEntry != NULL
2322                                  && b->source->predEntry != NULL
2323                                     && a->source->predEntry == b->source->predEntry);
2324     if (sameInvert && (sameSource || samePredEntry)) {
2325       if (MR_identicalContext(a,b)) {
2326          return 1;
2327       };
2328     };
2329     return 0;
2330   };
2331   if (a->down == NULL || b->down == NULL) return 0;
2332   if (a->expr != b->expr) return 0;
2333 
2334   for (p=a->down; p != NULL; p=p->right) {
2335     for (q=b->down; q != NULL; q=q->right) {
2336       if (MR_comparePredicates(p,q)) goto NEXT_P;
2337     };
2338     return 0;
2339 NEXT_P:
2340     continue;
2341   };
2342   return 1;
2343 }
2344 
2345 /*
2346  *  action->inverted can be set only when a predicate symbol appears in
2347  *      a rule:  "rule : <<!XXX>>? X".  It cannot be set under any
2348  *      other circumstances.  In particular it cannot be set by
2349  *      "#pred NotA !A" or by "#pred Nota <<!A>>?".  The first case
2350  *      creates a predEntry and the predicate expression of that predEntry
2351  *      has inverted set.  In the second case, the code for handling "!"
2352  *      is only present in buildAction, which is not called by the #pred
2353  *      semantic routines, only when a <<...>>? is recognized as part of
2354  *      a rule definition.
2355  *
2356  *  predicate->inverted can only be set by a predicate created by a #pred
2357  *      expression, such as "#pred NotA !A" or "#pred NotXY ! (X && Y) or
2358  *      "#pred XbarY !(X && Y)".  In particular, it cannot be set by any
2359  *      predicate expression occurring under any other circumstances.
2360  *      The #pred predicate expresssions are stored with in predEntry->pred
2361  *      and do not normally appear anywhere else until the predicates are
2362  *      "unfolded" in order to recognize redundancies, conflicts, and
2363  *      tautologies.
2364  *
2365  *  The unfold routine expands all references to #pred expressions.
2366  *
2367  *  The simplifyInvert goes through and propagates the invert bit so that
2368  *      all OR and AND nodes are un-inverted.
2369  *
2370  *  Note that !(A and B) => (!A or !B)
2371  *            !(A or B)  => (!A and !B)
2372  *
2373  *  MR_unfold() is called to expand predicate symbols by replacing predicates
2374  *    that reference predicate entries with the copies of the predicate entries.
2375  *    Each reference receives a duplicate of the original.  This is necessary
2376  *    because the next phase involves simplification and removal of redundant
2377  *    predicate nodes.  Anyway, the point I'm making is that predicate->invert
2378  *    should not be set in any predicate until it has been expanded.
2379  *
2380  *    This is a recursive structure, but there is no need for "recursive expansion"
2381  *    by which I mean a predicate symbol refers to other predicate symbols which
2382  *    must also be expanded.
2383  *
2384  *    Recursive expansion is *not* performed by this routine because it is not
2385  *    necessary.  Expansion of references is performed by predPrimary when
2386  *    a new predicate symbol is created by referring to others in the pred expr.
2387  */
2388 
2389 #ifdef __USE_PROTOS
2390 Predicate *MR_unfold(Predicate *pred)
2391 #else
2392 Predicate *MR_unfold(pred)
2393   Predicate     *pred;
2394 #endif
2395 {
2396   Predicate     *result;
2397 
2398   if (pred == NULL) return NULL;
2399 
2400   pred->right=MR_unfold(pred->right);
2401 
2402   if (pred->down == NULL) {
2403     if (pred->source->predEntry != NULL) {
2404       if (pred->source->predEntry->pred == NULL) {
2405         ; /* do nothing */ /* a reference to a literal #pred (perhaps with "!" */
2406       } else {
2407         result=predicate_dup_without_context(pred->source->predEntry->pred);
2408         if (pred->inverted) {
2409           result->inverted=!result->inverted;
2410         };
2411         if (pred->source->inverted) {
2412           result->inverted=!result->inverted;
2413         };
2414         result->right=pred->right;
2415         pred->right=NULL;
2416         predicate_free(pred);
2417 /***    result=MR_unfold(result); *** not necessary */    /* recursive expansion */
2418         return result;
2419       };
2420     } else {
2421       ; /* do nothing */ /* an inline literal predicate */
2422     };
2423   } else {
2424     pred->down=MR_unfold(pred->down);
2425   };
2426   return pred;
2427 }
2428 
2429 /* this should be called immediately after MR_unfold() and
2430    at no other times
2431 */
2432 
2433 #ifdef __USE_PROTOS
2434 void MR_simplifyInverted(Predicate *pred,int inverted)
2435 #else
2436 void MR_simplifyInverted(pred,inverted)
2437   Predicate     *pred;
2438   int           inverted;
2439 #endif
2440 {
2441   int       newInverted;
2442 
2443   if (pred == NULL) return;
2444 
2445   MR_simplifyInverted(pred->right,inverted);
2446 
2447   newInverted= 1 & (inverted + pred->inverted);
2448 
2449   if (pred->down == NULL) {
2450     pred->inverted=newInverted;
2451   } else {
2452     if (newInverted != 0) {
2453       if (pred->expr == PRED_AND_LIST) {
2454         pred->expr=PRED_OR_LIST;
2455       } else {
2456         pred->expr=PRED_AND_LIST;
2457       };
2458     };
2459     pred->inverted=0;
2460     MR_simplifyInverted(pred->down,newInverted);
2461   };
2462 }
2463 
2464 /* only remove it from AND and OR nodes, not leaves */
2465 
2466 #ifdef __USE_PROTOS
2467 void MR_clearPredEntry(Predicate *p)
2468 #else
2469 void MR_clearPredEntry(p)
2470   Predicate     *p;
2471 #endif
2472 {
2473    if (p == NULL) return;
2474    MR_clearPredEntry(p->down);
2475    MR_clearPredEntry(p->right);
2476    if (p->down != NULL) p->predEntry=NULL;
2477 }
2478 
2479 
2480 #ifdef __USE_PROTOS
2481 void MR_orphanRules(FILE *f)
2482 #else
2483 void MR_orphanRules(f)
2484   FILE      *f;
2485 #endif
2486 {
2487 	set         a;
2488     Junction    *p;
2489     unsigned    e;
2490     RuleEntry   *re;
2491 
2492 	a=empty;
2493 
2494     if (! InfoO) return;
2495 
2496 	for (p=SynDiag; p!=NULL; p = (Junction *)p->p2)	{
2497       if ( (Junction *) (p->end)->p1 == NULL) {
2498         re=(RuleEntry *) hash_get(Rname,p->rname);
2499         require (re != NULL,"RuleEntry == NULL");
2500 		set_orel(re->rulenum, &a);
2501       }
2502   	}
2503 
2504     if (set_deg(a) > 1) {
2505       fprintf(f,"note: Start rules: {");
2506       for (; !set_nil(a); set_rm(e,a)) {
2507         e=set_int(a);
2508         fprintf(f," %s",RulePtr[e]->rname);
2509       };
2510       fprintf(f," }\n");
2511     };
2512 	set_free( a );
2513 }
2514 
2515 /*  merge (X Y) and (X) to create (X)  */
2516 
2517 static int      *mergeChain;
2518 static Tree     *mergeTree;
2519 
2520 #ifdef __USE_PROTOS
2521 Tree *MR_merge_tree_contexts_client(Tree *t,int chain[])
2522 #else
2523 Tree *MR_merge_tree_contexts_client(t,chain)
2524   Tree  *t;
2525   int   chain[];
2526 #endif
2527 {
2528   if (t == NULL)  return NULL;
2529   if (chain[0] == 0) {
2530     Tree    *u=t->right;
2531     t->right=NULL;
2532     Tfree(t);
2533     return MR_merge_tree_contexts_client(u,&chain[0]);
2534   }
2535   if (chain[0] == t->token) {
2536     t->down=MR_merge_tree_contexts_client(t->down,&chain[1]);
2537   };
2538   t->right=MR_merge_tree_contexts_client(t->right,&chain[0]);
2539   return t;
2540 }
2541 
2542 #ifdef __USE_PROTOS
2543 void MR_iterateOverTreeContexts(Tree *t,int chain[])
2544 #else
2545 void MR_iterateOverTreeContexts(t,chain)
2546   Tree          *t;
2547   int           chain[];
2548 #endif
2549 {
2550   if (t == NULL) return;
2551   chain[0]=t->token;
2552   if (t->down != NULL) {
2553     MR_iterateOverTreeContexts(t->down,&chain[1]);
2554   } else {
2555     MR_merge_tree_contexts_client(mergeTree,mergeChain);
2556   };
2557   MR_iterateOverTreeContexts(t->right,&chain[0]);
2558   chain[0]=0;
2559 }
2560 
2561 #ifdef __USE_PROTOS
2562 Tree *MR_merge_tree_contexts(Tree *t)
2563 #else
2564 Tree *MR_merge_tree_contexts(t)
2565   Tree  *t;
2566 #endif
2567 {
2568     int     h=MR_max_height_of_tree(t);
2569 
2570     mergeTree=t;
2571     mergeChain=(int *) calloc(h+1,sizeof(int));
2572     require (mergeChain != NULL,"MR_merge_tree_contexts: can't alloc chain");
2573     MR_iterateOverTreeContexts(t,mergeChain);
2574     t=tshrink(t);
2575     t=tflatten(t);
2576     t=tleft_factor(t);
2577     free ( (char *) mergeChain);
2578     mergeChain=NULL;
2579     return t;
2580 }
2581 
2582 #ifdef __USE_PROTOS
2583 Tree *MR_compute_pred_tree_context(Predicate *p)
2584 #else
2585 Tree *MR_compute_pred_tree_context(p)
2586   Predicate *p;
2587 #endif
2588 {
2589   Tree  *t;
2590 
2591   t=MR_compute_pred_tree_ctxXX(p);
2592   MR_merge_tree_contexts(t);
2593   return t;
2594 }
2595 
2596 #ifdef __USE_PROTOS
2597 void MR_guardPred_plainSet(ActionNode *anode,Predicate *pred)
2598 #else
2599 void MR_guardPred_plainSet(anode,pred)
2600   ActionNode    *anode;
2601   Predicate     *pred;
2602 #endif
2603 {
2604   Junction      *j;
2605   Predicate     *workPred;
2606   set           maskSet;
2607 
2608   maskSet=empty;
2609 
2610   if (!MRhoisting) return;
2611 
2612   /* it doesn't really matter whether the predicate has
2613      depth k=1 or k>1 because we're not really looking
2614      at the predicate itself, just the stuff "behind"
2615      the predicate.
2616   */
2617 
2618   /* shouldn't have to worry about REACHing off the end
2619      of the rule containing the predicate because the
2620      Rule->end->halt should have been set already by the
2621      the code which handles RuleRef nodes.
2622 
2623      We don't want to REACH off the end of the rule because
2624      this would give the "global" follow context rather than
2625      the "local" context.
2626 
2627          r1a : (A)? => <<p>>? r2 (A|B)
2628          r1b : (A)? => <<p>>? r2 (A|C)
2629          r2  : ();
2630 
2631      For r1a we want follow of predicate = {A B}
2632              we want plainSet = {B}
2633      For r1b we want follow of predicate = {A C}
2634              we want plainSet = {C}
2635   */
2636 
2637   require (anode->next->ntype == nJunction,"MR_guardpred_plainSet not Junction");
2638   j=(Junction *)(anode->next);
2639 
2640   workPred=predicate_dup_without_context(pred);
2641   workPred->k=1;
2642   workPred->scontext[1]=MR_First(1,j, &(workPred->completionSet) );
2643   MR_complete_predicates(1,workPred);
2644   if (pred->k == 1) {
2645     maskSet=pred->scontext[1];
2646   } else {
2647     MR_projectTreeOntoSet(pred->tcontext,1,&maskSet);
2648   }
2649   pred->plainSet=set_dif(workPred->scontext[1],maskSet);
2650   predicate_free(workPred);
2651 }
2652 
2653 /*******************************************************************************/
2654 
2655 static Tree *       suppressTree;
2656 static int *        suppressChain;  /* element 0 not used */
2657 static set *        suppressSets;
2658 static Node *       suppressNode;
2659 static int          suppressChainLength;
2660 int                 MR_SuppressSearch=0;
2661 static int          suppressSucceeded;
2662 static Predicate *  suppressPredicate;
2663 
2664 #ifdef __USE_PROTOS
2665 int MR_isChain(Tree *t)
2666 #else
2667 int MR_isChain(t)
2668   Tree  *t;
2669 #endif
2670 {
2671   Tree  *u;
2672 
2673   for (u=t; u != NULL; u=u->down) {
2674     if (u->right != NULL) return 0;
2675   }
2676   return 1;
2677 }
2678 
2679 #ifdef __USE_PROTOS
2680 int MR_suppressK_client(Tree *tree,int tokensInChain[])
2681 #else
2682 int MR_suppressK_client(tree,tokensInChain)
2683   Tree      *tree;
2684   int       tokensInChain[];
2685 #endif
2686 {
2687   int       i;
2688   set       *save_fset;
2689   int       save_ConstrainSearch;
2690   set       incomplete;
2691   Tree      *t;
2692 
2693   suppressSucceeded=0;  /* volatile */
2694 
2695   if (suppressSets == NULL) {
2696     suppressSets=(set *) calloc (CLL_k+1,sizeof(set));
2697     require (suppressSets != NULL,"MR_suppressK_client: suppressSets alloc");
2698   };
2699 
2700   for (suppressChainLength=1;
2701        tokensInChain[suppressChainLength+1] != 0;
2702        suppressChainLength++) {};
2703 
2704   require (suppressChainLength != 0,"MR_suppressK_client: chain empty");
2705 
2706   for (i=1 ; i <= suppressChainLength ; i++) {
2707     set_clr(suppressSets[i]);
2708     set_orel( (unsigned) tokensInChain[i],
2709                               &suppressSets[i]);
2710   };
2711 
2712   save_fset=fset;
2713   save_ConstrainSearch=ConstrainSearch;
2714 
2715   fset=suppressSets;
2716 
2717   MR_SuppressSearch=1;
2718   MR_AmbSourceSearch=1;
2719   MR_MaintainBackTrace=1;
2720   ConstrainSearch=1;
2721 
2722   maxk = suppressChainLength;
2723 
2724   incomplete=empty;
2725   t=NULL;
2726 
2727 /***  constrain = &(fset[1]); ***/
2728 
2729   MR_setConstrainPointer(&(fset[1]));	/* MR18 */
2730 
2731   MR_pointerStackReset(&MR_BackTraceStack);
2732 
2733   TRAV(suppressNode,maxk,&incomplete,t);
2734 
2735   Tfree(t);
2736 
2737   require (set_nil(incomplete),"MR_suppressK_client TRAV incomplete");
2738   require (MR_BackTraceStack.count == 0,
2739             "MR_suppressK_client: MR_BackTraceStack.count != 0");
2740   set_free(incomplete);
2741 
2742   ConstrainSearch=save_ConstrainSearch;
2743   fset=save_fset;
2744 
2745   MR_AmbSourceSearch=0;
2746   MR_MaintainBackTrace=0;
2747   MR_SuppressSearch=0;
2748   return suppressSucceeded;
2749 }
2750 
2751 #ifdef __USE_PROTOS
2752 Tree * MR_iterateOverTreeSuppressK(Tree *t,int chain[])
2753 #else
2754 Tree * MR_iterateOverTreeSuppressK(t,chain)
2755   Tree          *t;
2756   int           chain[];
2757 #endif
2758 {
2759   if (t == NULL) return NULL;
2760   t->right=MR_iterateOverTreeSuppressK(t->right,&chain[0]);
2761   chain[0]=t->token;
2762   if (t->down != NULL) {
2763     t->down=MR_iterateOverTreeSuppressK(t->down,&chain[1]);
2764     if (t->down == NULL) {
2765       Tree *u=t->right;
2766       t->right=NULL;
2767       Tfree(t);
2768       chain[0]=0;
2769       return u;
2770     };
2771   } else {
2772     MR_suppressK_client(suppressTree,suppressChain);
2773     if (suppressSucceeded) {
2774       Tree  *u=t->right;
2775       t->right=NULL;
2776       Tfree(t);
2777       chain[0]=0;
2778       return u;
2779     };
2780   };
2781   chain[0]=0;
2782   return t;
2783 }
2784 
2785 /* @@@ */
2786 
2787 #ifdef __USE_PROTOS
2788 Predicate * MR_suppressK(Node *j,Predicate *p)
2789 #else
2790 Predicate * MR_suppressK(j,p)
2791   Node          *j;
2792   Predicate     *p;
2793 #endif
2794 {
2795   Predicate     *result;
2796   int           guardPred=0;
2797   int           ampersandPred=0;
2798   Node          *nodePrime;
2799 
2800   if (! MRhoistingk) {
2801      return p;
2802   }
2803 
2804   if (! MRhoisting) return p;
2805   if (CLL_k == 1) return p;
2806 
2807   if (suppressChain == NULL) {
2808     suppressChain=(int *) calloc(CLL_k+2,sizeof(int));
2809     require (suppressChain != NULL,"MR_suppressK: can't allocate chain");
2810   }
2811 
2812   if (p == NULL) return NULL;
2813 
2814   if (j->ntype == nJunction) {
2815     nodePrime=(Node *) MR_junctionWithoutP2( (Junction *) j);
2816   } else {
2817     nodePrime=j;
2818   };
2819 
2820   p->down=MR_suppressK(j,p->down);
2821   p->right=MR_suppressK(j,p->right);
2822   if (p->down != NULL) {
2823     result=p;
2824     goto EXIT;
2825   };
2826   if (p->k == 1) {
2827     result=p;
2828     goto EXIT;
2829   };
2830 
2831   if (p->source != NULL) {
2832     if (p->source->guardpred != NULL) guardPred=1;
2833     if (p->source->ampersandPred != NULL) ampersandPred=1;
2834   }
2835 
2836   suppressPredicate=p;
2837   suppressNode=nodePrime;   /* was j*/
2838 
2839   suppressTree=p->tcontext;
2840 
2841   if (guardPred || ampersandPred) {
2842     p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);
2843     if (p->tcontext == NULL) {
2844       predicate_free(p);
2845       result=NULL;
2846       goto EXIT;
2847     };
2848   } else {
2849     if (MR_isChain(p->tcontext)) {
2850       p->tcontext=MR_iterateOverTreeSuppressK(suppressTree,&suppressChain[1]);
2851       if (p->tcontext == NULL) {
2852         predicate_free(p);
2853         result=NULL;
2854         goto EXIT;
2855       };
2856     }
2857   }
2858   result=p;
2859 EXIT:
2860   return result;
2861 }
2862 
2863 #ifdef __USE_PROTOS
2864 void MR_suppressSearchReport(void)
2865 #else
2866 void MR_suppressSearchReport()
2867 #endif
2868 {
2869   int       i;
2870   Node      *p;
2871   TokNode   *tn;
2872   int       depth;
2873   set       setAnd;
2874 
2875   /* number of tokens in back trace stack matches length of chain */
2876 
2877   depth=0;
2878   for (i=0; i < MR_BackTraceStack.count ; i++) {
2879     p=(Node *) MR_BackTraceStack.data[i];
2880     if (p->ntype == nToken) depth++;
2881   };
2882 
2883   require (depth == suppressChainLength,"depth > suppressChainLength");
2884 
2885   /* token codes match chain */
2886 
2887   depth=0;
2888   for (i=0; i < MR_BackTraceStack.count ; i++) {
2889     p=(Node *) MR_BackTraceStack.data[i];
2890     if (p->ntype != nToken) continue;
2891     tn=(TokNode *) p;
2892     depth++;
2893     if (set_nil(tn->tset)) {
2894       require(set_el( (unsigned) tn->token,fset[depth]),
2895         "MR_suppressSearchReport: no match to #token in chain");
2896     } else {
2897       setAnd=set_and(fset[depth],tn->tset);
2898       require(!set_nil(setAnd),
2899         "MR_suppressSearchReport: no match to #token set in chain");
2900       set_free(setAnd);
2901     };
2902   };
2903 
2904   /* have a match - now remove it from the predicate */
2905 
2906   suppressSucceeded=1;
2907 
2908   if (suppressSucceeded) {
2909     fprintf(output,"\n");
2910     fprintf(output,"#if 0\n");
2911     fprintf(output,"\n");
2912     fprintf(output,"Part (or all) of predicate with depth > 1 suppressed by ");
2913         fprintf(output,"alternative without predicate\n\n");
2914     MR_dumpPred(suppressPredicate,1);
2915     fprintf(output,"The token sequence which is suppressed:");
2916     fprintf(output," (");
2917     for (i=1; i <= suppressChainLength; i++) {
2918       fprintf(output," %s",TerminalString(suppressChain[i]));
2919     };
2920     fprintf(output," )\n");
2921     fprintf(output,"The sequence of references which generate that sequence of tokens:\n\n");
2922 
2923     MR_backTraceDumpItemReset();
2924 
2925     for (i=0; i < MR_BackTraceStack.count ; i++) {
2926        MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);
2927     };
2928     fprintf(output,"\n");
2929     fprintf(output,"#endif\n");
2930   }
2931 }
2932 
2933 #ifdef __USE_PROTOS
2934 void MR_markCompromisedRule(Node *n)
2935 #else
2936 void MR_markCompromisedRule(n)
2937   Node *n;
2938 #endif
2939 {
2940   RuleEntry     *q;
2941   Node          *mark=NULL;
2942   Junction      *j;
2943 
2944   if (n->ntype == nRuleRef) {
2945     mark=(Node *) MR_ruleReferenced( (RuleRefNode *) n);
2946   } else if (n->ntype == nToken) {
2947     mark=n;
2948   } else if (n->ntype == nJunction) {
2949     j=(Junction *)n;
2950     switch (j->jtype) {
2951       case aOptBlk:
2952       case aLoopBlk:
2953       case RuleBlk:
2954       case EndRule:
2955       case aPlusBlk:
2956       case aLoopBegin:
2957         mark=n;
2958         break;
2959       default:
2960         break;
2961     };
2962   }
2963 
2964   if (mark == NULL) return;
2965 
2966   require (RulePtr != NULL,"RulePtr not initialized");
2967 
2968   q = (RuleEntry *) hash_get(Rname,mark->rname);
2969   require (q != NULL,"RuleEntry not found");
2970   set_orel(q->rulenum,&MR_CompromisedRules);
2971 }
2972 
2973 #ifdef __USE_PROTOS
2974 void MR_alphaBetaTraceReport(void)
2975 #else
2976 void MR_alphaBetaTraceReport()
2977 #endif
2978 {
2979   int       i;
2980 
2981   if (! AlphaBetaTrace) return;
2982 
2983   MR_AlphaBetaMessageCount++;
2984 
2985   fprintf(output,"\n");
2986   fprintf(output,"#if 0\n");
2987   fprintf(output,"\n");
2988   fprintf(output,"Trace of references leading to attempt to compute the follow set of\n");
2989   fprintf(output,"alpha in an \"(alpha)? beta\" block. It is not possible for antlr to\n");
2990   fprintf(output,"compute this follow set because it is not known what part of beta has\n");
2991   fprintf(output,"already been matched by alpha and what part remains to be matched.\n");
2992   fprintf(output,"\n");
2993   fprintf(output,"Rules which make use of the incorrect follow set will also be incorrect\n");
2994   fprintf(output,"\n");
2995 
2996   MR_backTraceDumpItemReset();
2997 
2998   for (i=0; i < MR_BackTraceStack.count ; i++) {
2999      MR_backTraceDumpItem(output,0,(Node *) MR_BackTraceStack.data[i]);
3000      if (i < MR_BackTraceStack.count-1) {
3001         MR_markCompromisedRule( (Node *) MR_BackTraceStack.data[i]);
3002      };
3003   };
3004   fprintf(output,"\n");
3005   fprintf(output,"#endif\n");
3006 }
3007 
3008 #ifdef __USE_PROTOS
3009 void MR_dumpRuleSet(set s)
3010 #else
3011 void MR_dumpRuleSet(s)
3012   set   s;
3013 #endif
3014 {
3015     unsigned    *cursor;
3016     unsigned    *origin=set_pdq(s);
3017 
3018     require(origin != NULL,"set_pdq failed");
3019 
3020     if (RulePtr == NULL) {
3021       fprintf(stderr,"RulePtr[] not yet initialized");
3022     } else {
3023       for (cursor=origin; *cursor != nil ; cursor++) {
3024 /****   if (cursor != origin) fprintf(stderr,","); ****/
3025         fprintf(stderr,"    %s",RulePtr[*cursor]->rname);
3026         fprintf(stderr,"\n");
3027       };
3028       free( (char *) origin);
3029     };
3030 }
3031