]> git.proxmox.com Git - mirror_edk2.git/blame - Tools/CCode/Source/Pccts/antlr/pred.c
projects / mirror_edk2.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Fixed all scripts to use new directory layout.
[mirror_edk2.git] / Tools / CCode / Source / Pccts / antlr / pred.c
CommitLineData
878ddf1f 1/*\r
2 * pred.c -- source for predicate detection, manipulation\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.33\r
25 * Terence Parr\r
26 * Parr Research Corporation\r
27 * with Purdue University and AHPCRC, University of Minnesota\r
28 * 1989-2001\r
29 */\r
30\r
31#include <stdio.h>\r
32#include "pcctscfg.h"\r
33#include "set.h"\r
34#include "syn.h"\r
35#include "hash.h"\r
36#include "generic.h"\r
37#include "dlgdef.h"\r
38#include <ctype.h>\r
39\r
40#ifdef __USE_PROTOS\r
41static void complete_context_sets(RuleRefNode *, Predicate *);\r
42static void complete_context_trees(RuleRefNode *, Predicate *);\r
43#else\r
44static void complete_context_sets();\r
45static void complete_context_trees();\r
46#endif\r
47\r
48char *PRED_AND_LIST = "AND";\r
49char *PRED_OR_LIST = "OR";\r
50\r
51/*\r
52 * In C mode, return the largest constant integer found as the\r
53 * sole argument to LATEXT(i).\r
54 *\r
55 * In C++ mode, return the largest constant integer found as the\r
56 * sole argument to LT(i) given that the char before is nonalpha.\r
57 */\r
58\r
59int\r
60#ifdef __USE_PROTOS\r
61predicateLookaheadDepth(ActionNode *a)\r
62#else\r
63predicateLookaheadDepth(a)\r
64ActionNode *a;\r
65#endif\r
66{\r
67 int max_k=0;\r
68\r
69 if (a->predEntry != NULL) {\r
70 MR_pred_depth(a->predEntry->pred,&max_k);\r
71 goto PREDENTRY_EXIT;\r
72 }\r
73\r
74 if ( GenCC )\r
75 {\r
76 /* scan for LT(i) */\r
77 int k = 0;\r
78 char *p = a->action;\r
79 while ( p!=NULL )\r
80 {\r
81 p = strstr(p, "LT(");\r
82 if ( p!=NULL )\r
83 {\r
84 if ( p>=a->action && !isalpha(*(p-1)) )\r
85 {\r
86 k = atoi(p+strlen("LT("));\r
87 if ( k>max_k ) max_k=k;\r
88 }\r
89 p += strlen("LT(");\r
90 }\r
91 }\r
92 }\r
93 else {\r
94 /* scan for LATEXT(i) */\r
95 int k = 0;\r
96 char *p = a->action;\r
97 while ( p!=NULL )\r
98 {\r
99 p = strstr(p, "LATEXT(");\r
100 if ( p!=NULL )\r
101 {\r
102 p += strlen("LATEXT(");\r
103 k = atoi(p);\r
104 if ( k>max_k ) max_k=k;\r
105 }\r
106 }\r
107 }\r
108\r
109 if (max_k==0) {\r
110 max_k = 1; /* MR33 Badly designed if didn't set max_k when CLL_k = 1 */\r
111 if (CLL_k > 1) /* MR27 Don't warn if max(k,ck) == 1 */\r
112 {\r
113 if ( !a->frmwarned )\r
114 {\r
115 a->frmwarned = 1;\r
116 warnFL(eMsg1("predicate: %s missing, bad, or with i=0; assuming i=1",\r
117 GenCC?"LT(i)":"LATEXT(i)"),\r
118 FileStr[a->file], a->line);\r
119 }\r
120 }\r
121 }\r
122\r
123/* MR10 */ if ( max_k > CLL_k) {\r
124/* MR10 */ if ( !a->frmwarned )\r
125/* MR10 */ {\r
126/* MR10 */ a->frmwarned = 1;\r
127/* MR11 */ errFL(eMsgd2("predicate refers to lookahead token %d. Semantic lookahead is limited to max(k,ck)==%d",\r
128/* MR10 */ max_k,CLL_k),\r
129/* MR10 */ FileStr[a->file],a->line);\r
130/* MR10 */ if (max_k >= OutputLL_k) {\r
131/* MR10 */ if (!GenCC) {\r
132/* MR10 */ errFL(eMsgd(" the lookahead buffer size in C mode is %d token(s) (including the one just recognized)",\r
133/* MR10 */ OutputLL_k),\r
134/* MR10 */ FileStr[a->file],a->line);\r
135/* MR10 */ };\r
136/* MR10 */ };\r
137/* MR10 */ };\r
138/* MR10 */ max_k= CLL_k;\r
139/* MR10 */ };\r
140\r
141PREDENTRY_EXIT:\r
142 return max_k;\r
143}\r
144\r
145/* Find all predicates in a block of alternatives. DO NOT find predicates\r
146 * behind the block because that predicate could depend on things set in\r
147 * one of the nonoptional blocks\r
148 */\r
149\r
150Predicate *\r
151#ifdef __USE_PROTOS\r
152find_in_aSubBlk( Junction *alt )\r
153#else\r
154find_in_aSubBlk( alt )\r
155Junction *alt;\r
156#endif\r
157{\r
158 Predicate *a, *head=NULL, *tail=NULL, *root=NULL;\r
159 Junction *p = alt;\r
160\r
161 if (MRhoisting) {\r
162 return MR_find_in_aSubBlk(alt);\r
163 };\r
164 for (; p!=NULL; p=(Junction *)p->p2)\r
165 {\r
166 /* ignore empty alts */\r
167 if ( p->p1->ntype != nJunction ||\r
168 ((Junction *)p->p1)->jtype != EndBlk )\r
169 {\r
170 a = find_predicates(p->p1); /* get preds for this alt */\r
171 if ( a==NULL ) continue;\r
172\r
173 /* make an OR list of predicates */\r
174 if ( head==NULL )\r
175 {\r
176 root = new_pred();\r
177 root->expr = PRED_OR_LIST;\r
178 head = tail = a;\r
179 root->down = head;\r
180 }\r
181 else {\r
182 tail->right = a;\r
183 a->left = tail;\r
184 a->up = tail->up;\r
185 tail = a;\r
186 }\r
187 }\r
188 }\r
189\r
190 /* if just one pred, remove OR root */\r
191 if ( root!=NULL && root->down->right == NULL )\r
192 {\r
193 Predicate *d = root->down;\r
194 free( (char *) root);\r
195 return d;\r
196 }\r
197\r
198 return root;\r
199}\r
200\r
201Predicate *\r
202#ifdef __USE_PROTOS\r
203find_in_aOptBlk( Junction *alt )\r
204#else\r
205find_in_aOptBlk( alt )\r
206Junction *alt;\r
207#endif\r
208{\r
209 return find_in_aSubBlk( alt );\r
210}\r
211\r
212Predicate *\r
213#ifdef __USE_PROTOS\r
214find_in_aLoopBegin( Junction *alt )\r
215#else\r
216find_in_aLoopBegin( alt )\r
217Junction *alt;\r
218#endif\r
219{\r
220 return find_in_aSubBlk( (Junction *) alt->p1 ); /* get preds in alts */\r
221}\r
222\r
223Predicate *\r
224#ifdef __USE_PROTOS\r
225find_in_aPlusBlk( Junction *alt )\r
226#else\r
227find_in_aPlusBlk( alt )\r
228Junction *alt;\r
229#endif\r
230{\r
231 require(alt!=NULL&&alt->p2!=NULL, "invalid aPlusBlk");\r
232 return find_in_aSubBlk( alt );\r
233}\r
234\r
235/* Look for a predicate;\r
236 *\r
237 * Do not pass anything but Junction nodes; no Actions, Tokens, RuleRefs.\r
238 * This means that a "hoisting distance" of zero is the only distance\r
239 * allowable. Init actions are ignored.\r
240 *\r
241 * WARNING:\r
242 * Assumes no (..)? block after predicate for the moment.\r
243 * Does not check to see if pred is in production that can generate\r
244 * a sequence contained in the set of ambiguous tuples.\r
245 *\r
246 * Return the predicate found if any.\r
247 */\r
248\r
249\r
250Predicate *\r
251#ifdef __USE_PROTOS\r
252find_predicates( Node *alt )\r
253#else\r
254find_predicates( alt )\r
255Node *alt;\r
256#endif\r
257{\r
258#ifdef DBG_PRED\r
259 Junction *j;\r
260 RuleRefNode *r;\r
261 TokNode *t;\r
262#endif\r
263 Predicate *pred;\r
264\r
265 if ( alt==NULL ) return NULL;\r
266\r
267#ifdef DBG_PRED\r
268 switch ( alt->ntype )\r
269 {\r
270 case nJunction :\r
271 j = (Junction *) alt;\r
272 fprintf(stderr, "Junction(in %s)", j->rname);\r
273 switch ( j->jtype )\r
274 {\r
275 case aSubBlk :\r
276 fprintf(stderr,"aSubBlk\n");\r
277 break;\r
278 case aOptBlk :\r
279 fprintf(stderr,"aOptBlk\n");\r
280 break;\r
281 case aLoopBegin :\r
282 fprintf(stderr,"aLoopBeginBlk\n");\r
283 break;\r
284 case aLoopBlk :\r
285 fprintf(stderr,"aLoopBlk\n");\r
286 break;\r
287 case aPlusBlk :\r
288 fprintf(stderr,"aPlusBlk\n");\r
289 break;\r
290 case EndBlk :\r
291 fprintf(stderr,"EndBlk\n");\r
292 break;\r
293 case RuleBlk :\r
294 fprintf(stderr,"RuleBlk\n");\r
295 break;\r
296 case Generic :\r
297 fprintf(stderr,"Generic\n");\r
298 break;\r
299 case EndRule :\r
300 fprintf(stderr,"EndRule\n");\r
301 break;\r
302 }\r
303 break;\r
304 case nRuleRef :\r
305 r = (RuleRefNode *) alt;\r
306 fprintf(stderr, "RuleRef(in %s)\n", r->rname);\r
307 break;\r
308 case nToken :\r
309 t = (TokNode *) alt;\r
310 fprintf(stderr, "TokenNode(in %s)%s\n", t->rname, TokenString(t->token));\r
311 break;\r
312 case nAction :\r
313 fprintf(stderr, "Action\n");\r
314 break;\r
315 }\r
316#endif\r
317\r
318 switch ( alt->ntype )\r
319 {\r
320 case nJunction :\r
321 {\r
322 Predicate *a, *b;\r
323 Junction *p = (Junction *) alt; \r
324\r
325 /* lock nodes */\r
326 if ( p->jtype==aLoopBlk || p->jtype==RuleBlk ||\r
327 p->jtype==aPlusBlk || p->jtype==EndRule )\r
328 {\r
329 require(p->pred_lock!=NULL, "rJunc: lock array is NULL");\r
330 if ( p->pred_lock[1] )\r
331 {\r
332 return NULL;\r
333 }\r
334 p->pred_lock[1] = TRUE;\r
335 }\r
336\r
337 switch ( p->jtype )\r
338 {\r
339 case aSubBlk :\r
340 a = find_in_aSubBlk(p);\r
341 return a; /* nothing is visible past this guy */\r
342 case aOptBlk :\r
343 a = find_in_aOptBlk(p);\r
344 return a;\r
345 case aLoopBegin :\r
346 a = find_in_aLoopBegin(p);\r
347 return a;\r
348 case aLoopBlk :\r
349 a = find_in_aSubBlk(p);\r
350 p->pred_lock[1] = FALSE;\r
351 return a;\r
352 case aPlusBlk :\r
353 a = find_in_aPlusBlk(p);\r
354 p->pred_lock[1] = FALSE;\r
355 return a; /* nothing is visible past this guy */\r
356 case RuleBlk :\r
357 a = find_predicates(p->p1);\r
358 p->pred_lock[1] = FALSE;\r
359 return a;\r
360 case Generic :\r
361 a = find_predicates(p->p1);\r
362 b = find_predicates(p->p2);\r
363 if ( p->pred_lock!=NULL ) p->pred_lock[1] = FALSE;\r
364 if ( a==NULL ) return b;\r
365 if ( b==NULL ) return a;\r
366 /* otherwise OR the two preds together */\r
367 {\r
368 fatal_internal("hit unknown situation during predicate hoisting");\r
369 }\r
370 case EndBlk :\r
371 case EndRule : /* Find no predicates after a rule ref */\r
372 return NULL;\r
373 default:\r
374 fatal_internal("this cannot be printed\n");\r
375 break;\r
376 }\r
377 }\r
378 case nAction :\r
379 {\r
380 ActionNode *p = (ActionNode *) alt;\r
381 if ( p->noHoist) return NULL; /* MR12c */\r
382 if ( p->init_action ) return find_predicates(p->next);\r
383 if ( p->is_predicate )\r
384 {\r
385 Tree *t=NULL;\r
386#ifdef DBG_PRED\r
387 fprintf(stderr, "predicate: <<%s>>?\n", p->action);\r
388#endif\r
389 if ( p->guardpred!=NULL )\r
390 {\r
391 pred = predicate_dup(p->guardpred);\r
392 MR_guardPred_plainSet(p,pred); /* MR12c */\r
393 }\r
394 else\r
395 {\r
396 pred = new_pred();\r
397 pred->k = predicateLookaheadDepth(p);\r
398 pred->source = p;\r
399 pred->expr = p->action;\r
400 if ( HoistPredicateContext && pred->k > 1 )\r
401 {\r
402 /* MR30 No need to use first_item_is_guess_block_extra\r
403 since we know this is an action, not a (...)* or\r
404 (...)+ block.\r
405 */\r
406\r
407 if ( first_item_is_guess_block((Junction *)p->next) )\r
408 {\r
409 warnFL("cannot compute context of predicate in front of (..)? block",\r
410 FileStr[p->file], p->line);\r
411 }\r
412 else\r
413 {\r
414 ConstrainSearch = 0;\r
415/* MR11 */ if (p->ampersandPred != NULL) {\r
416/* MR11 */ TRAV(p,\r
417/* MR11 */ pred->k,\r
418/* MR11 */ &(pred->completionTree), t);\r
419/* MR11 */ } else {\r
420 TRAV(p->next,\r
421 pred->k,\r
422 &(pred->completionTree), t);\r
423 };\r
424 pred->tcontext = t;\r
425 MR_check_pred_too_long(pred,pred->completionTree);\r
426#ifdef DBG_PRED\r
427 fprintf(stderr, "LL(%d) context:", pred->k);\r
428 preorder(t);\r
429 fprintf(stderr, "\n");\r
430#endif\r
431 }\r
432 }\r
433 else if ( HoistPredicateContext && pred->k == 1 )\r
434 {\r
435 pred->scontext[1] = empty;\r
436 /* MR30 No need to use first_item_is_guess_block_extra\r
437 since we know this is an action.\r
438 */\r
439 if ( first_item_is_guess_block((Junction *)p->next) )\r
440 {\r
441 warnFL("cannot compute context of predicate in front of (..)? block",\r
442 FileStr[p->file], p->line);\r
443 }\r
444 else\r
445 {\r
446 REACH((Junction *)p->next,\r
447 1,\r
448 &(pred->completionSet),\r
449 pred->scontext[1]);\r
450 MR_check_pred_too_long(pred,pred->completionSet);\r
451#ifdef DBG_PRED\r
452 fprintf(stderr, "LL(1) context:");\r
453 s_fprT(stderr, pred->scontext[1]);\r
454 fprintf(stderr, "\n");\r
455#endif\r
456 }\r
457 }\r
458 }\r
459 {\r
460 Predicate *d = find_predicates(p->next);\r
461 Predicate *root;\r
462\r
463/* Warning: Doesn't seem like the up pointers will all be set correctly;\r
464 * TJP: that's ok, we're not using them now.\r
465 */\r
466 if ( d!=NULL )\r
467 {\r
468 root = new_pred();\r
469 root->expr = PRED_AND_LIST;\r
470 root->down = pred;\r
471 pred->right = d;\r
472 pred->up = root;\r
473 d->left = pred;\r
474 d->up = pred->up;\r
475 return root;\r
476 }\r
477 }\r
478 return pred;\r
479 }\r
480 return NULL;\r
481 }\r
482 case nRuleRef :\r
483 {\r
484 Predicate *a;\r
485 RuleRefNode *p = (RuleRefNode *) alt;\r
486 Junction *r;\r
487 Junction *save_MR_RuleBlkWithHalt;\r
488\r
489 RuleEntry *q = (RuleEntry *) hash_get(Rname, p->text);\r
490 if ( q == NULL )\r
491 {\r
492 warnFL( eMsg1("rule %s not defined",p->text), FileStr[p->file], p->line );\r
493 return NULL;\r
494 }\r
495 r = RulePtr[q->rulenum];\r
496 if ( r->pred_lock[1] )\r
497 {\r
498 /* infinite left-recursion; ignore 'cause LL sup 1 (k) analysis\r
499 * must have seen it earlier.\r
500 */\r
501 return NULL;\r
502 }\r
503\r
504 /* MR10 There should only be one halt set at a time. */\r
505 /* MR10 Life would have been easier with a global variable */\r
506 /* MR10 (at least for this particular need) */\r
507 /* MR10 Unset the old one and set the new one, later undo. */\r
508\r
509 require(r->end->halt == FALSE,"should only have one halt at a time");\r
510\r
511/* MR10 */ require(MR_RuleBlkWithHalt == NULL ||\r
512/* MR10 */ (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == TRUE),\r
513/* MR10 */ "RuleBlkWithHalt->end not RuleBlk or does not have halt set");\r
514/* MR10 */ if (MR_RuleBlkWithHalt != NULL) {\r
515/* MR10 */ MR_RuleBlkWithHalt->end->halt=FALSE;\r
516/* MR10 */ };\r
517\r
518/*** fprintf(stderr,"\nSetting halt on junction #%d\n",r->end->seq); ***/\r
519\r
520 require(r->end->halt == FALSE,"rule->end->halt already set");\r
521\r
522 save_MR_RuleBlkWithHalt=MR_RuleBlkWithHalt;\r
523\r
524/* MR10 */ MR_pointerStackPush(&MR_RuleBlkWithHaltStack,MR_RuleBlkWithHalt);\r
525/* MR10 */ MR_pointerStackPush(&MR_PredRuleRefStack,p);\r
526\r
527 r->end->halt = TRUE;\r
528/* MR10 */ MR_RuleBlkWithHalt=r;\r
529\r
530 a = find_predicates((Node *)r);\r
531\r
532 require(r->end->halt == TRUE,"rule->end->halt not set");\r
533 r->end->halt = FALSE;\r
534\r
535/* MR10 */ MR_pointerStackPop(&MR_PredRuleRefStack);\r
536/* MR10 */ MR_RuleBlkWithHalt=(Junction *) MR_pointerStackPop(&MR_RuleBlkWithHaltStack);\r
537\r
538 require (MR_RuleBlkWithHalt==save_MR_RuleBlkWithHalt,\r
539 "RuleBlkWithHaltStack not consistent");\r
540\r
541/* MR10 */ require(MR_RuleBlkWithHalt == NULL ||\r
542/* MR10 */ (MR_RuleBlkWithHalt->jtype == RuleBlk && MR_RuleBlkWithHalt->end->halt == FALSE),\r
543/* MR10 */ "RuleBlkWithHalt->end not RuleBlk or has no halt set");\r
544/* MR10 */ if (MR_RuleBlkWithHalt != NULL) {\r
545/* MR10 */ MR_RuleBlkWithHalt->end->halt=TRUE;\r
546/* MR10 */ };\r
547\r
548/*** fprintf(stderr,"\nRestoring halt on junction #%d\n",r->end->seq); ***/\r
549\r
550 if ( a==NULL ) return NULL;\r
551\r
552 /* attempt to compute the "local" FOLLOW just like in normal lookahead\r
553 * computation if needed\r
554 */\r
555\r
556 complete_context_sets(p,a);\r
557 complete_context_trees(p,a);\r
558\r
559/* MR10 */ MR_cleanup_pred_trees(a);\r
560\r
561 return a;\r
562 }\r
563 case nToken :\r
564 break;\r
565 }\r
566\r
567 return NULL;\r
568}\r
569\r
570#ifdef __USE_PROTOS\r
571Predicate *MR_find_predicates_and_supp(Node *alt)\r
572#else\r
573Predicate *MR_find_predicates_and_supp(alt)\r
574 Node *alt;\r
575#endif\r
576{\r
577 Predicate *p;\r
578\r
579 p=find_predicates(alt);\r
580 p=MR_suppressK(alt,p);\r
581 return p;\r
582}\r
583\r
584Predicate *\r
585#ifdef __USE_PROTOS\r
586new_pred( void )\r
587#else\r
588new_pred( )\r
589#endif\r
590{\r
591 Predicate *p = (Predicate *) calloc(1,sizeof(Predicate)); /* MR10 */\r
592 require(p!=NULL, "new_pred: cannot alloc predicate");\r
593 p->scontext[0]=empty;\r
594 p->scontext[1]=empty;\r
595 p->completionTree=empty;\r
596 p->completionSet=empty;\r
597 p->plainSet=empty;\r
598 return p;\r
599}\r
600\r
601static void\r
602#ifdef __USE_PROTOS\r
603complete_context_sets( RuleRefNode *p, Predicate *a )\r
604#else\r
605complete_context_sets( p, a )\r
606RuleRefNode *p;\r
607Predicate *a;\r
608#endif\r
609{\r
610 set rk2, b;\r
611 int k2;\r
612\r
613#ifdef DBG_PRED\r
614 fprintf(stderr, "enter complete_context_sets\n");\r
615#endif\r
616 for (; a!=NULL; a=a->right)\r
617 {\r
618 if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )\r
619 {\r
620 complete_context_sets(p,a->down);\r
621 continue;\r
622 }\r
623 rk2 = b = empty;\r
624 while ( !set_nil(a->completionSet) )\r
625 {\r
626 k2 = set_int(a->completionSet);\r
627 set_rm(k2, a->completionSet);\r
628\r
629 REACH(p->next, k2, &rk2, b);\r
630 set_orin(&(a->scontext[1]), b);\r
631 set_free(b);\r
632 }\r
633\r
634 set_orin(&(a->completionSet), rk2);/* remember what we couldn't do */\r
635 set_free(rk2);\r
636#ifdef DBG_PRED\r
637 fprintf(stderr, "LL(1) context for %s(addr 0x%x) after ruleref:", a->expr, a);\r
638 s_fprT(stderr, a->scontext[1]);\r
639 fprintf(stderr, "\n");\r
640#endif\r
641/* complete_context_sets(p, a->down);*/\r
642 }\r
643#ifdef DBG_PRED\r
644 fprintf(stderr, "exit complete_context_sets\n");\r
645#endif\r
646}\r
647\r
648static void\r
649#ifdef __USE_PROTOS\r
650complete_context_trees( RuleRefNode *p, Predicate *a )\r
651#else\r
652complete_context_trees( p, a )\r
653RuleRefNode *p;\r
654Predicate *a;\r
655#endif\r
656{\r
657 set rk2;\r
658 int k2;\r
659 Tree *u;\r
660\r
661#ifdef DBG_PRED\r
662 fprintf(stderr, "enter complete_context_trees\n");\r
663#endif\r
664 for (; a!=NULL; a=a->right)\r
665 {\r
666 if ( a->expr == PRED_AND_LIST || a->expr == PRED_OR_LIST )\r
667 {\r
668 complete_context_trees(p, a->down);\r
669 continue;\r
670 }\r
671 rk2 = empty;\r
672\r
673 /* any k left to do? if so, link onto tree */\r
674 while ( !set_nil(a->completionTree) )\r
675 { \r
676 k2 = set_int(a->completionTree);\r
677 set_rm(k2, a->completionTree);\r
678 u = NULL;\r
679\r
680 TRAV(p->next, k2, &rk2, u);\r
681\r
682 /* any subtrees missing k2 tokens, add u onto end */\r
683 a->tcontext = tlink(a->tcontext, u, k2);\r
684 Tfree(u); /* MR10 */\r
685 }\r
686 set_orin(&(a->completionTree), rk2);/* remember what we couldn't do */\r
687 set_free(rk2);\r
688#ifdef DBG_PRED\r
689 fprintf(stderr, "LL(i<%d) context after ruleref:", LL_k);\r
690 preorder(a->tcontext);\r
691 fprintf(stderr, "\n");\r
692#endif\r
693/* complete_context_trees(p, a->down);*/\r
694 }\r
695#ifdef DBG_PRED\r
696 fprintf(stderr, "exit complete_context_trees\n");\r
697#endif\r
698}\r
699\r
700/* Walk a list of predicates and return the set of all tokens in scontext[1]'s */\r
701set\r
702#ifdef __USE_PROTOS\r
703covered_set( Predicate *p )\r
704#else\r
705covered_set( p )\r
706Predicate *p;\r
707#endif\r
708{\r
709 set a;\r
710\r
711 a = empty;\r
712 for (; p!=NULL; p=p->right)\r
713 {\r
714 if ( p->expr == PRED_AND_LIST || p->expr == PRED_OR_LIST )\r
715 {\r
716 set_orin(&a, covered_set(p->down));\r
717 continue;\r
718 }\r
719 set_orin(&a, p->scontext[1]);\r
720 set_orin(&a, covered_set(p->down));\r
721 }\r
722 return a;\r
723}\r
724\r
725/* MR10 predicate_free()\r
726 MR10 Don't free the leaf nodes since they are part of the action node\r
727*/\r
728\r
729#ifdef __USE_PROTOS\r
730void predicate_free(Predicate *p)\r
731#else\r
732void predicate_free(p)\r
733 Predicate *p;\r
734#endif\r
735{\r
736 if (p == NULL) return;\r
737 predicate_free(p->right);\r
738 predicate_free(p->down);\r
739 if (p->cloned ||\r
740 p->source == NULL ||\r
741 p->source->guardpred == NULL ||\r
742 p->expr == PRED_AND_LIST ||\r
743 p->expr == PRED_OR_LIST) {\r
744 set_free(p->scontext[1]);\r
745 set_free(p->completionSet);\r
746 set_free(p->completionTree);\r
747 set_free(p->plainSet);\r
748 Tfree(p->tcontext);\r
749 free( (char *) p);\r
750 } else {\r
751 p->right=NULL;\r
752 p->down=NULL; /* MR13 *** debug */\r
753 };\r
754}\r
755\r
756/* MR10 predicate_dup() */\r
757\r
758#ifdef __USE_PROTOS\r
759Predicate * predicate_dup_xxx(Predicate *p,int contextToo)\r
760#else\r
761Predicate * predicate_dup_xxx(p,contextToo)\r
762 Predicate *p;\r
763 int contextToo;\r
764#endif\r
765{\r
766 Predicate *q;\r
767\r
768 if (p == NULL) return NULL;\r
769 q=new_pred();\r
770 q->down=predicate_dup(p->down);\r
771 q->right=predicate_dup(p->right);\r
772\r
773 /*\r
774 don't replicate expr - it is read-only\r
775 and address comparison is used to look\r
776 for identical predicates.\r
777 */\r
778\r
779 q->expr=p->expr;\r
780 q->k=p->k;\r
781 q->source=p->source;\r
782 q->cloned=1;\r
783 q->ampersandStyle=p->ampersandStyle;\r
784 q->inverted=p->inverted;\r
785 q->predEntry=p->predEntry;\r
786 q->plainSet=set_dup(p->plainSet);\r
787\r
788 if (contextToo) {\r
789 q->tcontext=tdup(p->tcontext);\r
790 q->scontext[0]=set_dup(p->scontext[0]);\r
791 q->scontext[1]=set_dup(p->scontext[1]);\r
792 q->completionTree=set_dup(p->completionTree);\r
793 q->completionSet=set_dup(p->completionSet);\r
794 };\r
795\r
796 /* don't need to dup "redundant" */\r
797\r
798 return q;\r
799\r
800}\r
801\r
802#ifdef __USE_PROTOS\r
803Predicate * predicate_dup_without_context(Predicate *p)\r
804#else\r
805Predicate * predicate_dup_without_context(p)\r
806 Predicate *p;\r
807#endif\r
808{\r
809 return predicate_dup_xxx(p,0);\r
810}\r
811\r
812#ifdef __USE_PROTOS\r
813Predicate * predicate_dup(Predicate *p)\r
814#else\r
815Predicate * predicate_dup(p)\r
816 Predicate *p;\r
817#endif\r
818{\r
819 return predicate_dup_xxx(p,1);\r
820}\r
821\r
EFI Development Kit II mirror for PVE