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