]>
Commit | Line | Data |
---|---|---|
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 | |
40 | void dumppred(Predicate *);\r | |
41 | #else\r | |
42 | void 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 | |
55 | int MR_secondPredicateUnreachable(Predicate *first,Predicate *second)\r | |
56 | #else\r | |
57 | int 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 | |
138 | A_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 | |
174 | B_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 | |
188 | void MR_xxxIndent(FILE *f,int depth)\r | |
189 | #else\r | |
190 | void 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 | |
203 | void MR_stderrIndent(int depth)\r | |
204 | #else\r | |
205 | void 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 | |
213 | void MR_outputIndent(int depth)\r | |
214 | #else\r | |
215 | void 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 | |
223 | void MR_set_reuse(set *s)\r | |
224 | #else\r | |
225 | void 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 | |
234 | void MR_dumpPredRuleRefStack(FILE *iounit,int indent)\r | |
235 | #else\r | |
236 | void 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 | |
266 | void MR_dumpTreeF(FILE *f,int depth,Tree *tree,int across)\r | |
267 | #else\r | |
268 | void 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 | |
308 | void MR_dumpTreeX(int depth,Tree *tree,int across)\r | |
309 | #else\r | |
310 | void 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 | |
320 | void MR_dumpTokenSet(FILE *f,int depth,set s)\r | |
321 | #else\r | |
322 | void 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 | |
357 | void MR_dumpPred1(int depth,Predicate *p,int withContext)\r | |
358 | #else\r | |
359 | void 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 | |
443 | void MR_dumpPred(Predicate *p,int withContext)\r | |
444 | #else\r | |
445 | void 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 | |
454 | Tree * MR_make_tree_from_set(set s)\r | |
455 | #else\r | |
456 | Tree * 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 | |
480 | void MR_check_pred_too_long(Predicate *p,set completion)\r | |
481 | #else\r | |
482 | void 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 | |
492 | warnFL("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 | |
499 | int MR_predicate_context_completed(Predicate *p)\r | |
500 | #else\r | |
501 | int 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 | |
516 | Node * MR_advance(Node *n)\r | |
517 | #else\r | |
518 | Node * 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 | |
534 | Junction * MR_find_endRule(Node *n)\r | |
535 | #else\r | |
536 | Junction * 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 | |
561 | Tree *MR_computeTreeIntersection(Tree *l,Tree *r)\r | |
562 | #else\r | |
563 | Tree *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 | |
622 | Tree *MR_computeTreeAND(Tree *l,Tree *r)\r | |
623 | #else\r | |
624 | Tree *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 | |
669 | void MR_union_plain_sets1(Predicate *p,set *theUnion)\r | |
670 | #else\r | |
671 | void 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 | |
684 | set MR_union_plain_sets(Predicate *p)\r | |
685 | #else\r | |
686 | set 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 | |
704 | Tree *MR_compute_pred_tree_ctxXX(Predicate *p)\r | |
705 | #else\r | |
706 | Tree *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 | |
793 | void MR_pred_depth(Predicate *p,int *maxDepth)\r | |
794 | #else\r | |
795 | void 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 | |
812 | set MR_compute_pred_set(Predicate *p)\r | |
813 | #else\r | |
814 | set 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 | |
848 | set MR_First(int ck,Junction *j,set *incomplete)\r | |
849 | #else\r | |
850 | set 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 | |
871 | void MR_cleanup_pred_trees(Predicate *p)\r | |
872 | #else\r | |
873 | void 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 | |
895 | Tree * MR_remove_epsilon_from_tree(Tree *t)\r | |
896 | #else\r | |
897 | Tree * 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 | |
919 | void MR_complete_set(int predDepth,set *tokensUsed,set *incomplete)\r | |
920 | #else\r | |
921 | void 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 | |
984 | void MR_complete_tree(int predDepth,Tree **t,set *incomplete)\r | |
985 | #else\r | |
986 | void 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 | |
1060 | void MR_complete_predicates(int predDepth,Predicate *pred)\r | |
1061 | #else\r | |
1062 | void 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 | |
1078 | Junction * MR_junctionWithoutP2(Junction *j)\r | |
1079 | #else\r | |
1080 | Junction * 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 | |
1107 | int MR_tree_equ(Tree *big, Tree *small) {\r | |
1108 | #else\r | |
1109 | int 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 | |
1152 | next_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 | |
1161 | int MR_identicalContext(Predicate *p,Predicate *q)\r | |
1162 | #else\r | |
1163 | int 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 | |
1179 | void MR_reportSetSuppression(int predDepth,\r | |
1180 | set predSet,set plainSet,Junction *jPred,Junction *jPlain,Predicate *p)\r | |
1181 | #else\r | |
1182 | void 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 | |
1216 | void MR_reportSetRestriction(int predDepth,set predSet,set plainSet,\r | |
1217 | Junction *jPred,Junction *jPlain,Predicate *origPred,Predicate *newPred)\r | |
1218 | #else\r | |
1219 | void 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 | |
1269 | Predicate * MR_removeRedundantPredPass3(Predicate *p)\r | |
1270 | #else\r | |
1271 | Predicate * 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 | |
1306 | void MR_removeRedundantPredPass2(Predicate *p)\r | |
1307 | #else\r | |
1308 | void 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 | |
1362 | void MR_apply_restriction1(Predicate *pred,set *plainSet,int *changed)\r | |
1363 | #else\r | |
1364 | void 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 | |
1392 | void MR_orin_plainSet(Predicate *p,set plainSet)\r | |
1393 | #else\r | |
1394 | void 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 | |
1405 | Predicate *PRED_SUPPRESS;\r | |
1406 | \r | |
1407 | #ifdef __USE_PROTOS\r | |
1408 | Predicate * MR_find_in_aSubBlk(Junction *alt)\r | |
1409 | #else\r | |
1410 | Predicate * 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 | |
1662 | next_i:\r | |
1663 | continue;\r | |
1664 | };\r | |
1665 | \r | |
1666 | EXIT_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 | |
1723 | void MR_predContextPresent(Predicate *p,int *allHaveContext,int *noneHaveContext)\r | |
1724 | #else\r | |
1725 | void 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 | |
1746 | int MR_pointerStackPush(PointerStack *ps,void *dataPointer)\r | |
1747 | #else\r | |
1748 | int 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 | |
1774 | void * MR_pointerStackPop(PointerStack *ps)\r | |
1775 | #else\r | |
1776 | void * 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 | |
1791 | void * MR_pointerStackTop(PointerStack *ps)\r | |
1792 | #else\r | |
1793 | void * 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 | |
1802 | void MR_pointerStackReset(PointerStack *ps)\r | |
1803 | #else\r | |
1804 | void 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 | |
1818 | Junction *MR_nameToRuleBlk(char *name)\r | |
1819 | #else\r | |
1820 | Junction *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 | |
1840 | Junction * MR_ruleReferenced(RuleRefNode *rrn)\r | |
1841 | #else\r | |
1842 | Junction * 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 | |
1850 | void MR_comparePredLeaves(Predicate *me,Predicate *myParent,Predicate *him,Predicate *hisParent)\r | |
1851 | #else\r | |
1852 | void 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 | |
1936 | void MR_removeRedundantPredPass1(Predicate *me,Predicate *myParent)\r | |
1937 | #else\r | |
1938 | void 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 | |
1964 | Predicate *MR_predFlatten(Predicate *p)\r | |
1965 | #else\r | |
1966 | Predicate *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 | |
2026 | static char *alwaysFalseWarning=NULL;\r | |
2027 | \r | |
2028 | #ifdef __USE_PROTOS\r | |
2029 | Predicate *checkPredicateConflict(Predicate *p)\r | |
2030 | #else\r | |
2031 | Predicate *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 | |
2065 | int MR_countPredNodes(Predicate *p)\r | |
2066 | #else\r | |
2067 | int 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 | |
2076 | Predicate *MR_predSimplifyALLX(Predicate *p,int skipPass3)\r | |
2077 | #else\r | |
2078 | Predicate *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 | |
2107 | Predicate *MR_predSimplifyALL(Predicate *p)\r | |
2108 | #else\r | |
2109 | Predicate *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 | |
2117 | void MR_releaseResourcesUsedInRule(Node *n)\r | |
2118 | #else\r | |
2119 | void 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 | |
2155 | int MR_allPredLeaves(Predicate *p)\r | |
2156 | #else\r | |
2157 | int 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 | |
2174 | int MR_offsetFromRule(Node *n)\r | |
2175 | #else\r | |
2176 | int 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 | |
2204 | static char ruleNameStatic1[ruleNameMax];\r | |
2205 | static char ruleNameStatic2[ruleNameMax+10];\r | |
2206 | \r | |
2207 | #ifdef __USE_PROTOS\r | |
2208 | char * MR_ruleNamePlusOffset(Node *n)\r | |
2209 | #else\r | |
2210 | char * 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 | |
2226 | int MR_max_height_of_tree(Tree *t)\r | |
2227 | #else\r | |
2228 | int 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 | |
2248 | int MR_all_leaves_same_height(Tree *t,int depth)\r | |
2249 | #else\r | |
2250 | int 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 | |
2276 | void MR_projectTreeOntoSet(Tree *tree,int ck,set *ckset)\r | |
2277 | #else\r | |
2278 | void 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 | |
2301 | int MR_comparePredicates(Predicate *a,Predicate *b)\r | |
2302 | #else\r | |
2303 | int 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 | |
2339 | NEXT_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 | |
2390 | Predicate *MR_unfold(Predicate *pred)\r | |
2391 | #else\r | |
2392 | Predicate *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 | |
2434 | void MR_simplifyInverted(Predicate *pred,int inverted)\r | |
2435 | #else\r | |
2436 | void 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 | |
2467 | void MR_clearPredEntry(Predicate *p)\r | |
2468 | #else\r | |
2469 | void 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 | |
2481 | void MR_orphanRules(FILE *f)\r | |
2482 | #else\r | |
2483 | void 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 | |
2517 | static int *mergeChain;\r | |
2518 | static Tree *mergeTree;\r | |
2519 | \r | |
2520 | #ifdef __USE_PROTOS\r | |
2521 | Tree *MR_merge_tree_contexts_client(Tree *t,int chain[])\r | |
2522 | #else\r | |
2523 | Tree *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 | |
2543 | void MR_iterateOverTreeContexts(Tree *t,int chain[])\r | |
2544 | #else\r | |
2545 | void 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 | |
2562 | Tree *MR_merge_tree_contexts(Tree *t)\r | |
2563 | #else\r | |
2564 | Tree *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 | |
2583 | Tree *MR_compute_pred_tree_context(Predicate *p)\r | |
2584 | #else\r | |
2585 | Tree *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 | |
2597 | void MR_guardPred_plainSet(ActionNode *anode,Predicate *pred)\r | |
2598 | #else\r | |
2599 | void 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 | |
2655 | static Tree * suppressTree;\r | |
2656 | static int * suppressChain; /* element 0 not used */\r | |
2657 | static set * suppressSets;\r | |
2658 | static Node * suppressNode;\r | |
2659 | static int suppressChainLength;\r | |
2660 | int MR_SuppressSearch=0;\r | |
2661 | static int suppressSucceeded;\r | |
2662 | static Predicate * suppressPredicate;\r | |
2663 | \r | |
2664 | #ifdef __USE_PROTOS\r | |
2665 | int MR_isChain(Tree *t)\r | |
2666 | #else\r | |
2667 | int 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 | |
2680 | int MR_suppressK_client(Tree *tree,int tokensInChain[])\r | |
2681 | #else\r | |
2682 | int 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 | |
2752 | Tree * MR_iterateOverTreeSuppressK(Tree *t,int chain[])\r | |
2753 | #else\r | |
2754 | Tree * 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 | |
2788 | Predicate * MR_suppressK(Node *j,Predicate *p)\r | |
2789 | #else\r | |
2790 | Predicate * 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 | |
2859 | EXIT:\r | |
2860 | return result;\r | |
2861 | }\r | |
2862 | \r | |
2863 | #ifdef __USE_PROTOS\r | |
2864 | void MR_suppressSearchReport(void)\r | |
2865 | #else\r | |
2866 | void 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 | |
2934 | void MR_markCompromisedRule(Node *n)\r | |
2935 | #else\r | |
2936 | void 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 | |
2974 | void MR_alphaBetaTraceReport(void)\r | |
2975 | #else\r | |
2976 | void 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 | |
3009 | void MR_dumpRuleSet(set s)\r | |
3010 | #else\r | |
3011 | void 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 |