source: trunk/essentials/sys-apps/findutils/find/tree.c

Last change on this file was 3170, checked in by bird, 18 years ago

findutils 4.3.2
File size: 45.3 KB
Line 
1/* tree.c -- helper functions to build and evaluate the expression tree.
2 Copyright (C) 1990, 91, 92, 93, 94, 2000, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2, or (at your option)
7 any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
17 USA.
18*/
19
20#include "defs.h"
21#include "../gnulib/lib/xalloc.h"
22
23#include <assert.h>
24#include <stdlib.h>
25
26#if ENABLE_NLS
27# include <libintl.h>
28# define _(Text) gettext (Text)
29#else
30# define _(Text) Text
31#endif
32#ifdef gettext_noop
33# define N_(String) gettext_noop (String)
34#else
35/* See locate.c for explanation as to why not use (String) */
36# define N_(String) String
37#endif
38
39
40
41/* All predicates for each path to process. */
42static struct predicate *predicates = NULL;
43
44/* The root of the evaluation tree. */
45static struct predicate *eval_tree = NULL;
46
47/* The last predicate allocated. */
48static struct predicate *last_pred = NULL;
49
50
51static struct predicate *scan_rest PARAMS((struct predicate **input,
52 struct predicate *head,
53 short int prev_prec));
54static void merge_pred PARAMS((struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p));
55static struct predicate *set_new_parent PARAMS((struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp));
56static const char *cost_name PARAMS((enum EvaluationCost cost));
57
58
59/* Return a pointer to a tree that represents the
60 expression prior to non-unary operator *INPUT.
61 Set *INPUT to point at the next input predicate node.
62
63 Only accepts the following:
64
65 <primary>
66 expression [operators of higher precedence]
67 <uni_op><primary>
68 (arbitrary expression)
69 <uni_op>(arbitrary expression)
70
71 In other words, you can not start out with a bi_op or close_paren.
72
73 If the following operator (if any) is of a higher precedence than
74 PREV_PREC, the expression just nabbed is part of a following
75 expression, which really is the expression that should be handed to
76 our caller, so get_expr recurses. */
77
78struct predicate *
79get_expr (struct predicate **input,
80 short int prev_prec,
81 const struct predicate* prev_pred)
82{
83 struct predicate *next = NULL;
84 struct predicate *this_pred = (*input);
85
86 if (*input == NULL)
87 error (1, 0, _("invalid expression"));
88
89 switch ((*input)->p_type)
90 {
91 case NO_TYPE:
92 error (1, 0, _("invalid expression"));
93 break;
94
95 case BI_OP:
96 /* e.g. "find . -a" */
97 error (1, 0, _("invalid expression; you have used a binary operator '%s' with nothing before it."), this_pred->p_name);
98 break;
99
100 case CLOSE_PAREN:
101 if ((UNI_OP == prev_pred->p_type
102 || BI_OP == prev_pred->p_type)
103 && !this_pred->artificial)
104 {
105 /* e.g. "find \( -not \)" or "find \( -true -a \" */
106 error(1, 0, _("expected an expression between '%s' and ')'"),
107 prev_pred->p_name);
108 }
109 else if ( (*input)->artificial )
110 {
111 /* We have reached the end of the user-supplied predicates
112 * unexpectedly.
113 */
114 /* e.g. "find . -true -a" */
115 error (1, 0, _("expected an expression after '%s'"), prev_pred->p_name);
116 }
117 else
118 {
119 error (1, 0, _("invalid expression; you have too many ')'"));
120 }
121 break;
122
123 case PRIMARY_TYPE:
124 next = *input;
125 *input = (*input)->pred_next;
126 break;
127
128 case UNI_OP:
129 next = *input;
130 *input = (*input)->pred_next;
131 next->pred_right = get_expr (input, NEGATE_PREC, next);
132 break;
133
134 case OPEN_PAREN:
135 if ( (NULL == (*input)->pred_next) || (*input)->pred_next->artificial )
136 {
137 /* user typed something like "find . (", and so the ) we are
138 * looking at is from the artificial "( ) -print" that we
139 * add.
140 */
141 error (1, 0, _("invalid expression; expected to find a ')' but didn't see one. Perhaps you need an extra predicate after '%s'"), this_pred->p_name);
142 }
143 prev_pred = (*input);
144 *input = (*input)->pred_next;
145 if ( (*input)->p_type == CLOSE_PAREN )
146 {
147 error (1, 0, _("invalid expression; empty parentheses are not allowed."));
148 }
149 next = get_expr (input, NO_PREC, prev_pred);
150 if ((*input == NULL)
151 || ((*input)->p_type != CLOSE_PAREN))
152 error (1, 0, _("invalid expression; I was expecting to find a ')' somewhere but did not see one."));
153 *input = (*input)->pred_next; /* move over close */
154 break;
155
156 default:
157 error (1, 0, _("oops -- invalid expression type!"));
158 break;
159 }
160
161 /* We now have the first expression and are positioned to check
162 out the next operator. If NULL, all done. Otherwise, if
163 PREV_PREC < the current node precedence, we must continue;
164 the expression we just nabbed is more tightly bound to the
165 following expression than to the previous one. */
166 if (*input == NULL)
167 return (next);
168 if ((int) (*input)->p_prec > (int) prev_prec)
169 {
170 next = scan_rest (input, next, prev_prec);
171 if (next == NULL)
172 error (1, 0, _("invalid expression"));
173 }
174 return (next);
175}
176
177
178/* Scan across the remainder of a predicate input list starting
179 at *INPUT, building the rest of the expression tree to return.
180 Stop at the first close parenthesis or the end of the input list.
181 Assumes that get_expr has been called to nab the first element
182 of the expression tree.
183
184 *INPUT points to the current input predicate list element.
185 It is updated as we move along the list to point to the
186 terminating input element.
187 HEAD points to the predicate element that was obtained
188 by the call to get_expr.
189 PREV_PREC is the precedence of the previous predicate element. */
190
191static struct predicate *
192scan_rest (struct predicate **input,
193 struct predicate *head,
194 short int prev_prec)
195{
196 struct predicate *tree; /* The new tree we are building. */
197
198 if ((*input == NULL) || ((*input)->p_type == CLOSE_PAREN))
199 return (NULL);
200 tree = head;
201 while ((*input != NULL) && ((int) (*input)->p_prec > (int) prev_prec))
202 {
203 switch ((*input)->p_type)
204 {
205 case NO_TYPE:
206 case PRIMARY_TYPE:
207 case UNI_OP:
208 case OPEN_PAREN:
209 /* I'm not sure how we get here, so it is not obvious what
210 * sort of mistakes might give rise to this condition.
211 */
212 error (1, 0, _("invalid expression"));
213 break;
214
215 case BI_OP:
216 {
217 struct predicate *prev = (*input);
218 (*input)->pred_left = tree;
219 tree = *input;
220 *input = (*input)->pred_next;
221 tree->pred_right = get_expr (input, tree->p_prec, prev);
222 break;
223 }
224
225 case CLOSE_PAREN:
226 return tree;
227
228 default:
229 error (1, 0,
230 _("oops -- invalid expression type (%d)!"),
231 (int)(*input)->p_type);
232 break;
233 }
234 }
235 return tree;
236}
237
238
239/* Returns true if the specified predicate is reorderable. */
240static boolean
241predicate_is_cost_free(const struct predicate *p)
242{
243 PRED_FUNC pred_func = p->pred_func;
244
245 if (pred_func == pred_name || pred_func == pred_path ||
246 pred_func == pred_iname || pred_func == pred_ipath)
247 {
248 /* Traditionally (at least 4.1.7 through 4.2.x) GNU find always
249 * optimised these cases.
250 */
251 return true;
252 }
253 else if (options.optimisation_level > 0)
254 {
255 if (pred_func == pred_and || pred_func == pred_negate ||
256 pred_func == pred_comma || pred_func == pred_or)
257 return false;
258 else
259 return NeedsNothing == p->p_cost;
260 }
261 else
262 {
263 return false;
264 }
265}
266
267
268/* Prints a predicate */
269void print_predicate(FILE *fp, const struct predicate *p)
270{
271 fprintf (fp, "%s%s%s",
272 p->p_name,
273 p->arg_text ? " " : "",
274 p->arg_text ? p->arg_text : "");
275}
276
277
278
279struct predlist
280{
281 struct predicate *head;
282 struct predicate *tail;
283};
284
285
286static void
287predlist_init(struct predlist *p)
288{
289 p->head = p->tail = NULL;
290}
291
292static void
293predlist_insert(struct predlist *list,
294 struct predicate *curr,
295 struct predicate **pprev)
296{
297 struct predicate **insertpos = &(list->head);
298
299 *pprev = curr->pred_left;
300 if (options.optimisation_level > 2)
301 {
302 /* Insert the new node in the list after any other entries which
303 * are more selective.
304 */
305 if (0)
306 while ( (*insertpos) && ((*insertpos)->est_success_rate < curr->est_success_rate) )
307 {
308 insertpos = &((*insertpos)->pred_left);
309 }
310 }
311 curr->pred_left = (*insertpos);
312 (*insertpos) = curr;
313 if (NULL == list->tail)
314 list->tail = list->head;
315}
316
317
318static void
319predlist_dump(FILE *fp, const char *label, const struct predlist *list)
320{
321 const struct predicate *p;
322 fprintf(fp, "%s:\n", label);
323 for (p=list->head; p; p=p->pred_left)
324 {
325 print_optlist(fp, p);
326 fprintf(fp, " ");
327 }
328 fprintf(fp, "\n");
329}
330
331
332static void
333predlist_merge_nosort(struct predlist *list,
334 struct predicate **last)
335{
336 if (list->head)
337 {
338 calculate_derived_rates(list->head);
339 merge_pred(list->head, list->tail, last);
340 predlist_init(list);
341 }
342}
343
344
345static int
346pred_cost_compare(const struct predicate *p1, const struct predicate *p2, boolean wantfailure)
347{
348 if (p1->p_cost == p2->p_cost)
349 {
350 if (p1->est_success_rate == p2->est_success_rate)
351 return 0;
352 else if (wantfailure)
353 return p1->est_success_rate < p2->est_success_rate ? -1 : 1;
354 else
355 return p1->est_success_rate < p2->est_success_rate ? 1 : -1;
356 }
357 else
358 {
359 return p1->p_cost < p2->p_cost ? -1 : 1;
360 }
361}
362
363
364
365static void
366predlist_merge_sort(struct predlist *list,
367 struct predicate **last)
368{
369 struct predlist new_list;
370 struct predicate *p, *q;
371
372 if (NULL == list->head)
373 return; /* nothing to do */
374
375 if (options.debug_options & DebugTreeOpt)
376 {
377 fprintf(stderr, "%s:\n", "predlist before merge sort");
378 print_tree(stderr, list->head, 2);
379 }
380
381 calculate_derived_rates(list->head);
382 predlist_init(&new_list);
383 while (list->head)
384 {
385 /* remove head of source list */
386 q = list->head;
387 list->head = list->head->pred_left;
388 q->pred_left = NULL;
389
390 /* insert it into the new list */
391 for (p=new_list.head; p; p=p->pred_left)
392 {
393 /* If these operations are OR operations, we want to get a
394 * successful test as soon as possible, to take advantage of
395 * the short-circuit evaluation. If they're AND, we want to
396 * get an unsuccessful result early for the same reason.
397 * Therefore we invert the sense of the comparison for the
398 * OR case. We only want to invert the sense of the success
399 * rate comparison, not the operation cost comparison. Hence we
400 * pass a flag into pred_cost_compare().
401 */
402 boolean wantfailure = (OR_PREC != p->p_prec);
403 if (pred_cost_compare(p->pred_right, q->pred_right, wantfailure) >= 0)
404 break;
405 }
406 if (p)
407 {
408 /* insert into existing list */
409 q->pred_left = p->pred_left;
410 if (NULL == q->pred_left)
411 new_list.tail = q;
412 p->pred_left = q;
413 }
414 else
415 {
416 q->pred_left = new_list.head; /* prepend */
417 new_list.head = q;
418 if (NULL == new_list.tail)
419 new_list.tail = q; /* first item in new list */
420 }
421 }
422 if (options.debug_options & DebugTreeOpt)
423 {
424 fprintf(stderr, "%s:\n", "predlist after merge sort");
425 print_tree(stderr, new_list.head, 2);
426 }
427
428 calculate_derived_rates(new_list.head);
429 merge_pred(new_list.head, new_list.tail, last);
430 predlist_init(list);
431}
432
433
434static void
435merge_lists(struct predlist lists[], int nlists,
436 struct predlist *name_list,
437 struct predlist *regex_list,
438 struct predicate **last)
439{
440 int i;
441 static void (*mergefn)(struct predlist *, struct predicate**);
442
443 mergefn = predlist_merge_sort;
444
445 mergefn(name_list, last);
446 mergefn(regex_list, last);
447
448 for (i=0; i<nlists; i++)
449 mergefn(&lists[i], last);
450}
451
452
453
454
455static boolean
456subtree_has_side_effects(const struct predicate *p)
457{
458 if (p)
459 {
460 return p->side_effects
461 || subtree_has_side_effects(p->pred_left)
462 || subtree_has_side_effects(p->pred_right);
463 }
464 else
465 {
466
467 return false;
468 }
469}
470
471
472static int
473worst_cost (const struct predicate *p)
474{
475 if (p)
476 {
477 unsigned int cost_r, cost_l, worst;
478 cost_l = worst_cost(p->pred_left);
479 cost_r = worst_cost(p->pred_right);
480 worst = (cost_l > cost_r) ? cost_l : cost_r;
481 if (worst < p->p_cost)
482 worst = p->p_cost;
483 return worst;
484 }
485 else
486 {
487 return 0;
488 }
489}
490
491
492
493
494static void
495perform_arm_swap(struct predicate *p)
496{
497 struct predicate *tmp = p->pred_left->pred_right;
498 p->pred_left->pred_right = p->pred_right;
499 p->pred_right = tmp;
500}
501
502
503/* Consider swapping p->pred_left->pred_right with p->pred_right,
504 * if that yields a faster evaluation. Normally the left predicate is
505 * evaluated first.
506 *
507 * If the operation is an OR, we want the left predicate to be the one that
508 * succeeds most often. If it is an AND, we want it to be the predicate that
509 * fails most often.
510 *
511 * We don't consider swapping arms of an operator where their cost is
512 * different or where they have side effects.
513 *
514 * A viable test case for this is
515 * ./find -D opt -O3 . \! -type f -o -type d
516 * Here, the ! -type f should be evaluated first,
517 * as we assume that 95% of inodes are vanilla files.
518 */
519static boolean
520consider_arm_swap(struct predicate *p)
521{
522 int left_cost, right_cost;
523 const char *reason = NULL;
524 struct predicate **pl, **pr;
525
526 if (BI_OP != p->p_type)
527 reason = "Not a binary operation";
528
529 if (!reason)
530 {
531 if (NULL == p->pred_left || NULL == p->pred_right)
532 reason = "Doesn't have two arms";
533 }
534
535
536 if (!reason)
537 {
538 if (NULL == p->pred_left->pred_right)
539 reason = "Left arm has no child on RHS";
540 }
541 pr = &p->pred_right;
542 pl = &p->pred_left->pred_right;
543
544 if (!reason)
545 {
546 if (subtree_has_side_effects(*pl))
547 reason = "Left subtree has side-effects";
548 }
549 if (!reason)
550 {
551 if (subtree_has_side_effects(*pr))
552 reason = "Right subtree has side-effects";
553 }
554
555 if (!reason)
556 {
557 left_cost = worst_cost(*pl);
558 right_cost = worst_cost(*pr);
559
560 if (left_cost < right_cost)
561 {
562 reason = "efficient as-is";
563 }
564 }
565 if (!reason)
566 {
567 boolean want_swap;
568
569 if (left_cost == right_cost)
570 {
571 /* it's a candidate */
572 float succ_rate_l = (*pl)->est_success_rate;
573 float succ_rate_r = (*pr)->est_success_rate;
574
575 if (options.debug_options & DebugTreeOpt)
576 {
577 fprintf(stderr, "Success rates: l=%f, r=%f\n", succ_rate_l, succ_rate_r);
578 }
579
580 if (pred_or == p->pred_func)
581 {
582 want_swap = succ_rate_r < succ_rate_l;
583 if (!want_swap)
584 reason = "Operation is OR and right success rate >= left";
585 }
586 else if (pred_and == p->pred_func)
587 {
588 want_swap = succ_rate_r > succ_rate_l;
589 if (!want_swap)
590 reason = "Operation is AND and right success rate <= left";
591 }
592 else
593 {
594 want_swap = false;
595 reason = "Not AND or OR";
596 }
597 }
598 else
599 {
600 want_swap = true;
601 }
602
603 if (want_swap)
604 {
605 if (options.debug_options & DebugTreeOpt)
606 {
607 fprintf(stderr, "Performing arm swap on:\n");
608 print_tree (stderr, p, 0);
609 }
610 perform_arm_swap(p);
611 return true;
612 }
613 }
614
615
616 if (options.debug_options & DebugTreeOpt)
617 {
618 fprintf(stderr, "Not an arm swap candidate (%s):\n", reason);
619 print_tree (stderr, p, 0);
620 }
621 return false;
622}
623
624
625static boolean
626do_arm_swaps(struct predicate *p)
627{
628 if (p)
629 {
630 boolean swapped;
631 do
632 {
633 swapped = false;
634 if (consider_arm_swap(p)
635 || do_arm_swaps(p->pred_left)
636 || do_arm_swaps(p->pred_right))
637 {
638 swapped = true;
639 }
640 } while (swapped);
641 return swapped;
642 }
643 else
644 {
645 return false;
646 }
647}
648
649
650
651
652/* Optimize the ordering of the predicates in the tree. Rearrange
653 them to minimize work. Strategies:
654 * Evaluate predicates that don't need inode information first;
655 the predicates are divided into 1 or more groups separated by
656 predicates (if any) which have "side effects", such as printing.
657 The grouping implements the partial ordering on predicates which
658 those with side effects impose.
659
660 * Place -name, -iname, -path, -ipath, -regex and -iregex at the front
661 of a group, with -name, -iname, -path and -ipath ahead of
662 -regex and -iregex. Predicates which are moved to the front
663 of a group by definition do not have side effects. Both
664 -regex and -iregex both use pred_regex.
665
666 If higher optimisation levels have been selected, reordering also
667 occurs according to the p_cost member of each predicate (which
668 reflects the performance cost of the test). The ordering also
669 bears in mind whether these operations are more likely to succeed
670 or fail. When evauating a chain of OR conditions, we prefer
671 tests likely to succeed at the front of the list. For AND, we
672 prefer tests likely to fail at the front of the list.
673
674 This routine "normalizes" the predicate tree by ensuring that
675 all expression predicates have AND (or OR or COMMA) parent nodes
676 which are linked along the left edge of the expression tree.
677 This makes manipulation of subtrees easier.
678
679 EVAL_TREEP points to the root pointer of the predicate tree
680 to be rearranged. opt_expr may return a new root pointer there.
681 Return true if the tree contains side effects, false if not. */
682
683static boolean
684opt_expr (struct predicate **eval_treep)
685{
686 struct predlist regex_list={NULL,NULL}, name_list={NULL,NULL};
687 struct predlist cbo_list[NumEvaluationCosts];
688 int i;
689 struct predicate *curr;
690 struct predicate **prevp; /* Address of `curr' node. */
691 struct predicate **last_sidep; /* Last predicate with side effects. */
692 PRED_FUNC pred_func;
693 enum predicate_type p_type;
694 boolean has_side_effects = false; /* Return value. */
695 enum predicate_precedence prev_prec, /* precedence of last BI_OP in branch */
696 biop_prec; /* topmost BI_OP precedence in branch */
697
698 if (eval_treep == NULL || *eval_treep == NULL)
699 return (false);
700
701 for (i=0; i<NumEvaluationCosts; i++)
702 predlist_init(&cbo_list[i]);
703
704 /* Set up to normalize tree as a left-linked list of ANDs or ORs.
705 Set `curr' to the leftmost node, `prevp' to its address, and
706 `pred_func' to the predicate type of its parent. */
707 prevp = eval_treep;
708 prev_prec = AND_PREC;
709 curr = *prevp;
710 while (curr->pred_left != NULL)
711 {
712 prevp = &curr->pred_left;
713 prev_prec = curr->p_prec; /* must be a BI_OP */
714 curr = curr->pred_left;
715 }
716
717 /* Link in the appropriate BI_OP for the last expression, if needed. */
718 if (curr->p_type != BI_OP)
719 set_new_parent (curr, prev_prec, prevp);
720
721 if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
722 {
723 /* Normalized tree. */
724 fprintf (stderr, "Normalized Eval Tree:\n");
725 print_tree (stderr, *eval_treep, 0);
726 }
727
728 /* Rearrange the predicates. */
729 prevp = eval_treep;
730 biop_prec = NO_PREC; /* not COMMA_PREC */
731 if ((*prevp) && (*prevp)->p_type == BI_OP)
732 biop_prec = (*prevp)->p_prec;
733 while ((curr = *prevp) != NULL)
734 {
735 /* If there is a BI_OP of different precedence from the first
736 in the pred_left chain, create a new parent of the
737 original precedence, link the new parent to the left of the
738 previous and link CURR to the right of the new parent.
739 This preserves the precedence of expressions in the tree
740 in case we rearrange them. */
741 if (curr->p_type == BI_OP)
742 {
743 if (curr->p_prec != biop_prec)
744 curr = set_new_parent(curr, biop_prec, prevp);
745 }
746
747 /* See which predicate type we have. */
748 p_type = curr->pred_right->p_type;
749 pred_func = curr->pred_right->pred_func;
750
751
752 switch (p_type)
753 {
754 case NO_TYPE:
755 case PRIMARY_TYPE:
756 /* Don't rearrange the arguments of the comma operator, it is
757 not commutative. */
758 if (biop_prec == COMMA_PREC)
759 break;
760
761 /* If this predicate has no side effects, consider reordering it. */
762 if (!curr->pred_right->side_effects)
763 {
764 boolean reorder;
765
766 /* If it's one of our special primaries, move it to the
767 front of the list for that primary. */
768 if (predicate_is_cost_free(curr->pred_right))
769 {
770 if (options.debug_options & DebugTreeOpt)
771 {
772 fprintf(stderr, "-O%d: promoting cheap predicate ",
773 (int)options.optimisation_level);
774 print_predicate(stderr, curr->pred_right);
775 fprintf(stderr, " into name_list\n");
776 }
777 predlist_insert(&name_list, curr, prevp);
778 continue;
779 }
780
781 if (pred_func == pred_regex)
782 {
783 predlist_insert(&regex_list, curr, prevp);
784 continue;
785 }
786
787 reorder = ((options.optimisation_level > 1)
788 && (NeedsType == curr->pred_right->p_cost)
789 && !curr->pred_right->need_stat) ||
790 (options.optimisation_level > 2);
791
792 if (reorder)
793 {
794 if (options.debug_options & DebugTreeOpt)
795 {
796 fprintf(stderr, "-O%d: categorising predicate ",
797 (int)options.optimisation_level);
798 print_predicate(stderr, curr->pred_right);
799 fprintf(stderr, " by cost (%s)\n",
800 cost_name(curr->pred_right->p_cost));
801 }
802 predlist_insert(&cbo_list[curr->pred_right->p_cost], curr, prevp);
803 continue;
804 }
805 }
806
807 break;
808
809 case UNI_OP:
810 /* For NOT, check the expression trees below the NOT. */
811 curr->pred_right->side_effects
812 = opt_expr (&curr->pred_right->pred_right);
813 break;
814
815 case BI_OP:
816 /* For nested AND or OR, recurse (AND/OR form layers on the left of
817 the tree), and continue scanning this level of AND or OR. */
818 curr->pred_right->side_effects = opt_expr (&curr->pred_right);
819 break;
820
821 /* At this point, get_expr and scan_rest have already removed
822 all of the user's parentheses. */
823
824 default:
825 error (1, 0, _("oops -- invalid expression type!"));
826 break;
827 }
828
829 if (curr->pred_right->side_effects == true)
830 {
831 last_sidep = prevp;
832
833 /* Incorporate lists and reset list pointers for this group. */
834 merge_lists(cbo_list, NumEvaluationCosts, &name_list, &regex_list, last_sidep);
835 has_side_effects = true;
836 }
837
838 prevp = &curr->pred_left;
839 }
840
841 /* Do final list merges. */
842 last_sidep = prevp;
843 merge_lists(cbo_list, NumEvaluationCosts, &name_list, &regex_list, last_sidep);
844 return has_side_effects;
845}
846
847
848static float
849constrain_rate(float rate)
850{
851 if (rate > 1.0f)
852 return 1.0;
853 else if (rate < 0.0)
854 return 0.0;
855 else
856 return rate;
857}
858
859
860/* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
861 HIGH_PREC. */
862
863static struct predicate *
864set_new_parent (struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp)
865{
866 struct predicate *new_parent;
867
868 new_parent = (struct predicate *) xmalloc (sizeof (struct predicate));
869 new_parent->p_type = BI_OP;
870 new_parent->p_prec = high_prec;
871 new_parent->need_stat = false;
872 new_parent->need_type = false;
873 new_parent->p_cost = NeedsNothing;
874
875 switch (high_prec)
876 {
877 case COMMA_PREC:
878 new_parent->pred_func = pred_comma;
879 new_parent->p_name = ",";
880 new_parent->est_success_rate = 1.0;
881 break;
882 case OR_PREC:
883 new_parent->pred_func = pred_or;
884 new_parent->p_name = "-o";
885 new_parent->est_success_rate = constrain_rate(curr->est_success_rate);
886 break;
887 case AND_PREC:
888 new_parent->pred_func = pred_and;
889 new_parent->p_name = "-a";
890 new_parent->est_success_rate = constrain_rate(curr->est_success_rate);
891 break;
892 default:
893 ; /* empty */
894 }
895
896 new_parent->side_effects = false;
897 new_parent->no_default_print = false;
898 new_parent->args.str = NULL;
899 new_parent->pred_next = NULL;
900
901 /* Link in new_parent.
902 Pushes rest of left branch down 1 level to new_parent->pred_right. */
903 new_parent->pred_left = NULL;
904 new_parent->pred_right = curr;
905 *prevp = new_parent;
906
907 return new_parent;
908}
909
910/* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
911 into the tree at LAST_P. */
912
913static void
914merge_pred (struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p)
915{
916 end_list->pred_left = *last_p;
917 *last_p = beg_list;
918}
919
920
921/* Find the first node in expression tree TREE that requires
922 a stat call and mark the operator above it as needing a stat
923 before calling the node. Since the expression precedences
924 are represented in the tree, some preds that need stat may not
925 get executed (because the expression value is determined earlier.)
926 So every expression needing stat must be marked as such, not just
927 the earliest, to be sure to obtain the stat. This still guarantees
928 that a stat is made as late as possible. Return true if the top node
929 in TREE requires a stat, false if not. */
930
931static boolean
932mark_stat (struct predicate *tree)
933{
934 /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
935 to find the first predicate for which the stat is needed. */
936 switch (tree->p_type)
937 {
938 case NO_TYPE:
939 case PRIMARY_TYPE:
940 return tree->need_stat;
941
942 case UNI_OP:
943 if (mark_stat (tree->pred_right))
944 tree->need_stat = true;
945 return (false);
946
947 case BI_OP:
948 /* ANDs and ORs are linked along ->left ending in NULL. */
949 if (tree->pred_left != NULL)
950 mark_stat (tree->pred_left);
951
952 if (mark_stat (tree->pred_right))
953 tree->need_stat = true;
954
955 return (false);
956
957 default:
958 error (1, 0, _("oops -- invalid expression type in mark_stat!"));
959 return (false);
960 }
961}
962
963
964/* Find the first node in expression tree TREE that we will
965 need to know the file type, if any. Operates in the same
966 was as mark_stat().
967*/
968static boolean
969mark_type (struct predicate *tree)
970{
971 /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
972 to find the first predicate for which the type information is needed. */
973 switch (tree->p_type)
974 {
975 case NO_TYPE:
976 case PRIMARY_TYPE:
977 return tree->need_type;
978
979 case UNI_OP:
980 if (mark_type (tree->pred_right))
981 tree->need_type = true;
982 return false;
983
984 case BI_OP:
985 /* ANDs and ORs are linked along ->left ending in NULL. */
986 if (tree->pred_left != NULL)
987 mark_type (tree->pred_left);
988
989 if (mark_type (tree->pred_right))
990 tree->need_type = true;
991
992 return false;
993
994 default:
995 error (1, 0, _("oops -- invalid expression type in mark_type!"));
996 return (false);
997 }
998}
999
1000
1001struct pred_cost_lookup
1002{
1003 PRED_FUNC fn;
1004 enum EvaluationCost cost;
1005};
1006static struct pred_cost_lookup costlookup[] =
1007 {
1008 { pred_amin , NeedsStatInfo },
1009 { pred_and , NeedsNothing, },
1010 { pred_anewer , NeedsStatInfo, },
1011 { pred_atime , NeedsStatInfo, },
1012 { pred_close , NeedsNothing },
1013 { pred_cmin , NeedsStatInfo, },
1014 { pred_cnewer , NeedsStatInfo, },
1015 { pred_comma , NeedsNothing, },
1016 { pred_ctime , NeedsStatInfo, },
1017 { pred_delete , NeedsSyncDiskHit },
1018 { pred_empty , NeedsStatInfo },
1019 { pred_exec , NeedsEventualExec },
1020 { pred_execdir , NeedsEventualExec },
1021 { pred_executable, NeedsAccessInfo },
1022 { pred_false , NeedsNothing },
1023 { pred_fprint , NeedsNothing },
1024 { pred_fprint0 , NeedsNothing },
1025 { pred_fprintf , NeedsNothing },
1026 { pred_fstype , NeedsStatInfo }, /* true for amortised cost */
1027 { pred_gid , NeedsStatInfo },
1028 { pred_group , NeedsStatInfo },
1029 { pred_ilname , NeedsLinkName },
1030 { pred_iname , NeedsNothing },
1031 { pred_inum , NeedsStatInfo },
1032 { pred_ipath , NeedsNothing },
1033 { pred_links , NeedsStatInfo },
1034 { pred_lname , NeedsLinkName },
1035 { pred_ls , NeedsStatInfo },
1036 { pred_mmin , NeedsStatInfo },
1037 { pred_mtime , NeedsStatInfo },
1038 { pred_name , NeedsNothing },
1039 { pred_negate , NeedsNothing, },
1040 { pred_newer , NeedsStatInfo, },
1041 { pred_nogroup , NeedsStatInfo }, /* true for amortised cost if caching is on */
1042 { pred_nouser , NeedsStatInfo }, /* true for amortised cost if caching is on */
1043 { pred_ok , NeedsUserInteraction },
1044 { pred_okdir , NeedsUserInteraction },
1045 { pred_open , NeedsNothing },
1046 { pred_or , NeedsNothing, },
1047 { pred_path , NeedsNothing },
1048 { pred_perm , NeedsStatInfo },
1049 { pred_print , NeedsNothing },
1050 { pred_print0 , NeedsNothing },
1051 { pred_prune , NeedsNothing },
1052 { pred_quit , NeedsNothing },
1053 { pred_readable , NeedsAccessInfo },
1054 { pred_regex , NeedsNothing },
1055 { pred_samefile , NeedsStatInfo },
1056 { pred_size , NeedsStatInfo },
1057 { pred_true , NeedsNothing },
1058 { pred_type , NeedsType },
1059 { pred_uid , NeedsStatInfo },
1060 { pred_used , NeedsStatInfo },
1061 { pred_user , NeedsStatInfo },
1062 { pred_writable , NeedsAccessInfo },
1063 { pred_xtype , NeedsType } /* roughly correct unless most files are symlinks */
1064 };
1065static int pred_table_sorted = 0;
1066
1067
1068static boolean
1069check_sorted(void *base, size_t members, size_t membersize,
1070 int (*cmpfn)(const void*, const void*))
1071{
1072 const char *p = base;
1073 size_t i;
1074 for (i=1u; i<members; ++i)
1075 {
1076 int result = cmpfn(p+i*membersize, p+(i-1)*membersize);
1077 if (result < 0)
1078 return false;
1079 result = cmpfn(p+(i-1)*membersize, p+i*membersize);
1080 assert(result <= 0);
1081 }
1082 for (i=1u; i<members; ++i)
1083 {
1084 const struct pred_cost_lookup *pl1 = (const struct pred_cost_lookup*)(p+(i-1)*membersize);
1085 const struct pred_cost_lookup *pl2 = (const struct pred_cost_lookup*)(p+(i-0)*membersize);
1086 assert(pl1->fn <= pl2->fn);
1087 }
1088 return true;
1089}
1090
1091
1092
1093static int
1094cost_table_comparison(const void *p1, const void *p2)
1095{
1096 const struct pred_cost_lookup *pc1 = p1;
1097 const struct pred_cost_lookup *pc2 = p2;
1098
1099
1100 if (pc1->fn == pc2->fn)
1101 return 0;
1102 else if (pc1->fn > pc2->fn)
1103 return 1;
1104 else
1105 return -1;
1106}
1107
1108
1109static enum EvaluationCost
1110get_pred_cost(struct predicate *p)
1111{
1112 enum EvaluationCost data_requirement_cost = NeedsNothing;
1113 enum EvaluationCost inherent_cost = NeedsUnknown;
1114 PRED_FUNC f = p->pred_func;
1115
1116 if (p->need_stat)
1117 {
1118 data_requirement_cost = NeedsStatInfo;
1119 }
1120 else if (p->need_type)
1121 {
1122 data_requirement_cost = NeedsType;
1123 }
1124 else
1125 {
1126 data_requirement_cost = NeedsNothing;
1127 }
1128
1129 if (pred_exec == f || pred_execdir == f)
1130 {
1131 if (p->args.exec_vec.multiple)
1132 inherent_cost = NeedsEventualExec;
1133 else
1134 inherent_cost = NeedsImmediateExec;
1135 }
1136 else if (pred_fprintf == f)
1137 {
1138 /* the parser calculated the cost for us. */
1139 inherent_cost = p->p_cost;
1140 }
1141 else
1142 {
1143 struct pred_cost_lookup key;
1144 void *entry;
1145
1146 if (!pred_table_sorted)
1147 {
1148 qsort(costlookup,
1149 sizeof(costlookup)/sizeof(costlookup[0]),
1150 sizeof(costlookup[0]),
1151 cost_table_comparison);
1152
1153 if (!check_sorted(costlookup,
1154 sizeof(costlookup)/sizeof(costlookup[0]),
1155 sizeof(costlookup[0]),
1156 cost_table_comparison))
1157 {
1158 error(1, 0, "Failed to sort the costlookup array.");
1159 }
1160 pred_table_sorted = 1;
1161 }
1162 key.fn = p->pred_func;
1163 entry = bsearch(&key, costlookup,
1164 sizeof(costlookup)/sizeof(costlookup[0]),
1165 sizeof(costlookup[0]),
1166 cost_table_comparison);
1167 if (entry)
1168 {
1169 inherent_cost = ((const struct pred_cost_lookup*)entry)->cost;
1170 }
1171 else
1172 {
1173 error(0, 0, "warning: no cost entry for predicate %s", p->p_name);
1174 inherent_cost = NeedsUnknown;
1175 }
1176 }
1177
1178 if (inherent_cost > data_requirement_cost)
1179 return inherent_cost;
1180 else
1181 return data_requirement_cost;
1182}
1183
1184
1185static void
1186estimate_costs (struct predicate *tree)
1187{
1188 if (tree)
1189 {
1190 estimate_costs(tree->pred_right);
1191 estimate_costs(tree->pred_left);
1192
1193 tree->p_cost = get_pred_cost(tree);
1194 }
1195}
1196
1197struct predicate*
1198get_eval_tree(void)
1199{
1200 return eval_tree;
1201}
1202
1203static float
1204getrate(const struct predicate *p)
1205{
1206 if (p)
1207 return p->est_success_rate;
1208 else
1209 return 1.0;
1210}
1211
1212
1213float
1214calculate_derived_rates(struct predicate *p)
1215{
1216 float rate;
1217
1218 assert(NULL != p);
1219
1220 if (p->pred_right)
1221 calculate_derived_rates(p->pred_right);
1222 if (p->pred_left)
1223 calculate_derived_rates(p->pred_left);
1224
1225 assert(p->p_type != CLOSE_PAREN);
1226 assert(p->p_type != OPEN_PAREN);
1227
1228 if (p->p_type == PRIMARY_TYPE)
1229 {
1230 assert(NULL == p->pred_right);
1231 assert(NULL == p->pred_left);
1232 return p->est_success_rate;
1233 }
1234 else if (p->p_type == UNI_OP)
1235 {
1236 /* Unary operators must have exactly one operand */
1237 assert(pred_negate == p->pred_func);
1238 assert(NULL == p->pred_left);
1239 rate = 1.0 - p->pred_right->est_success_rate;
1240 }
1241 else if (p->p_type == BI_OP)
1242 {
1243 /* Binary operators must have two operands */
1244 if (pred_and == p->pred_func)
1245 {
1246 rate = getrate(p->pred_right) * getrate(p->pred_left);
1247 }
1248 else if (pred_comma == p->pred_func)
1249 {
1250 rate = 1.0;
1251 }
1252 else if (pred_or == p->pred_func)
1253 {
1254 rate = getrate(p->pred_right) + getrate(p->pred_left);
1255 }
1256 }
1257 else if (p->p_type == CLOSE_PAREN || p->p_type == OPEN_PAREN)
1258 {
1259 rate = 1.0;
1260 }
1261 else if (p->p_type == NO_TYPE)
1262 {
1263 assert(NULL == p->pred_right);
1264 assert(NULL == p->pred_left);
1265 return p->est_success_rate;
1266 }
1267 p->est_success_rate = constrain_rate(rate);
1268 return p->est_success_rate;
1269}
1270
1271
1272/* opt_expr() rearranges predicates such that each left subtree is
1273 * rooted at a logical predicate (e.g. and or or). check_normalization()
1274 * asserts that this property still holds.
1275 *
1276 */
1277static void check_normalization(struct predicate *p, boolean at_root)
1278{
1279 if (at_root)
1280 {
1281 assert(BI_OP == p->p_type);
1282 }
1283
1284 if (p->pred_left)
1285 {
1286 assert(BI_OP == p->pred_left->p_type);
1287 check_normalization(p->pred_left, false);
1288 }
1289 if (p->pred_right)
1290 {
1291 check_normalization(p->pred_right, false);
1292 }
1293}
1294
1295
1296struct predicate*
1297build_expression_tree(int argc, char *argv[], int end_of_leading_options)
1298{
1299 const struct parser_table *parse_entry; /* Pointer to the parsing table entry for this expression. */
1300 char *predicate_name; /* Name of predicate being parsed. */
1301 struct predicate *cur_pred;
1302 const struct parser_table *entry_close, *entry_print, *entry_open;
1303 int i, oldi;
1304
1305 predicates = NULL;
1306
1307 /* Find where in ARGV the predicates begin by skipping the list of start points. */
1308 for (i = end_of_leading_options; i < argc && !looks_like_expression(argv[i], true); i++)
1309 {
1310 /* fprintf(stderr, "Looks like %s is not a predicate\n", argv[i]); */
1311 /* Do nothing. */ ;
1312 }
1313
1314 /* XXX: beginning of bit we need factor out of both find.c and ftsfind.c */
1315 /* Enclose the expression in `( ... )' so a default -print will
1316 apply to the whole expression. */
1317 entry_open = find_parser("(");
1318 entry_close = find_parser(")");
1319 entry_print = find_parser("print");
1320 assert(entry_open != NULL);
1321 assert(entry_close != NULL);
1322 assert(entry_print != NULL);
1323
1324 parse_open (entry_open, argv, &argc);
1325 last_pred->p_name = "(";
1326 predicates->artificial = true;
1327 parse_begin_user_args(argv, argc, last_pred, predicates);
1328 pred_sanity_check(last_pred);
1329
1330 /* Build the input order list. */
1331 while (i < argc )
1332 {
1333 if (!looks_like_expression(argv[i], false))
1334 {
1335 error (0, 0, _("paths must precede expression: %s"), argv[i]);
1336 usage(stderr, 1, NULL);
1337 }
1338
1339 predicate_name = argv[i];
1340 parse_entry = find_parser (predicate_name);
1341 if (parse_entry == NULL)
1342 {
1343 /* Command line option not recognized */
1344 error (1, 0, _("invalid predicate `%s'"), predicate_name);
1345 }
1346
1347 i++;
1348 oldi = i;
1349 if (!(*(parse_entry->parser_func)) (parse_entry, argv, &i))
1350 {
1351 if (argv[i] == NULL)
1352 /* Command line option requires an argument */
1353 error (1, 0, _("missing argument to `%s'"), predicate_name);
1354 else
1355 error (1, 0, _("invalid argument `%s' to `%s'"),
1356 argv[i], predicate_name);
1357 }
1358 else
1359 {
1360 last_pred->p_name = predicate_name;
1361
1362 /* If the parser consumed an argument, save it. */
1363 if (i != oldi)
1364 last_pred->arg_text = argv[oldi];
1365 else
1366 last_pred->arg_text = NULL;
1367 }
1368 pred_sanity_check(last_pred);
1369 pred_sanity_check(predicates); /* XXX: expensive */
1370 }
1371 parse_end_user_args(argv, argc, last_pred, predicates);
1372 if (predicates->pred_next == NULL)
1373 {
1374 /* No predicates that do something other than set a global variable
1375 were given; remove the unneeded initial `(' and add `-print'. */
1376 cur_pred = predicates;
1377 predicates = last_pred = predicates->pred_next;
1378 free ((char *) cur_pred);
1379 parse_print (entry_print, argv, &argc);
1380 last_pred->p_name = "-print";
1381 pred_sanity_check(last_pred);
1382 pred_sanity_check(predicates); /* XXX: expensive */
1383 }
1384 else if (!default_prints (predicates->pred_next))
1385 {
1386 /* One or more predicates that produce output were given;
1387 remove the unneeded initial `('. */
1388 cur_pred = predicates;
1389 predicates = predicates->pred_next;
1390 pred_sanity_check(predicates); /* XXX: expensive */
1391 free ((char *) cur_pred);
1392 }
1393 else
1394 {
1395 /* `( user-supplied-expression ) -print'. */
1396 parse_close (entry_close, argv, &argc);
1397 last_pred->p_name = ")";
1398 last_pred->artificial = true;
1399 pred_sanity_check(last_pred);
1400 parse_print (entry_print, argv, &argc);
1401 last_pred->p_name = "-print";
1402 last_pred->artificial = true;
1403 pred_sanity_check(last_pred);
1404 pred_sanity_check(predicates); /* XXX: expensive */
1405 }
1406
1407 if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1408 {
1409 fprintf (stderr, "Predicate List:\n");
1410 print_list (stderr, predicates);
1411 }
1412
1413 /* do a sanity check */
1414 pred_sanity_check(predicates);
1415
1416 /* Done parsing the predicates. Build the evaluation tree. */
1417 cur_pred = predicates;
1418 eval_tree = get_expr (&cur_pred, NO_PREC, NULL);
1419 calculate_derived_rates(eval_tree);
1420
1421 /* Check if we have any left-over predicates (this fixes
1422 * Debian bug #185202).
1423 */
1424 if (cur_pred != NULL)
1425 {
1426 /* cur_pred->p_name is often NULL here */
1427 if (cur_pred->pred_func == pred_close)
1428 {
1429 /* e.g. "find \( -true \) \)" */
1430 error (1, 0, _("you have too many ')'"), cur_pred->p_name);
1431 }
1432 else
1433 {
1434 if (cur_pred->p_name)
1435 error (1, 0, _("unexpected extra predicate '%s'"), cur_pred->p_name);
1436 else
1437 error (1, 0, _("unexpected extra predicate"));
1438 }
1439 }
1440
1441 if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1442 {
1443 fprintf (stderr, "Eval Tree:\n");
1444 print_tree (stderr, eval_tree, 0);
1445 }
1446
1447 estimate_costs(eval_tree);
1448
1449 /* Rearrange the eval tree in optimal-predicate order. */
1450 opt_expr (&eval_tree);
1451
1452 /* Check that the tree is in normalised order (opt_expr does this) */
1453 check_normalization(eval_tree, true);
1454
1455 do_arm_swaps(eval_tree);
1456
1457 /* Check that the tree is still in normalised order */
1458 check_normalization(eval_tree, true);
1459
1460 /* Determine the point, if any, at which to stat the file. */
1461 mark_stat (eval_tree);
1462 /* Determine the point, if any, at which to determine file type. */
1463 mark_type (eval_tree);
1464
1465 if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1466 {
1467 fprintf (stderr, "Optimized Eval Tree:\n");
1468 print_tree (stderr, eval_tree, 0);
1469 fprintf (stderr, "Optimized command line:\n");
1470 print_optlist(stderr, eval_tree);
1471 fprintf(stderr, "\n");
1472 }
1473
1474 return eval_tree;
1475}
1476
1477
1478/* Return a pointer to a new predicate structure, which has been
1479 linked in as the last one in the predicates list.
1480
1481 Set `predicates' to point to the start of the predicates list.
1482 Set `last_pred' to point to the new last predicate in the list.
1483
1484 Set all cells in the new structure to the default values. */
1485
1486struct predicate *
1487get_new_pred (const struct parser_table *entry)
1488{
1489 register struct predicate *new_pred;
1490 (void) entry;
1491
1492 /* Options should not be turned into predicates. */
1493 assert(entry->type != ARG_OPTION);
1494 assert(entry->type != ARG_POSITIONAL_OPTION);
1495
1496 if (predicates == NULL)
1497 {
1498 predicates = (struct predicate *)
1499 xmalloc (sizeof (struct predicate));
1500 last_pred = predicates;
1501 }
1502 else
1503 {
1504 new_pred = (struct predicate *) xmalloc (sizeof (struct predicate));
1505 last_pred->pred_next = new_pred;
1506 last_pred = new_pred;
1507 }
1508 last_pred->parser_entry = entry;
1509 last_pred->pred_func = NULL;
1510 last_pred->p_name = NULL;
1511 last_pred->p_type = NO_TYPE;
1512 last_pred->p_prec = NO_PREC;
1513 last_pred->side_effects = false;
1514 last_pred->no_default_print = false;
1515 last_pred->need_stat = true;
1516 last_pred->need_type = true;
1517 last_pred->args.str = NULL;
1518 last_pred->pred_next = NULL;
1519 last_pred->pred_left = NULL;
1520 last_pred->pred_right = NULL;
1521 last_pred->literal_control_chars = options.literal_control_chars;
1522 last_pred->artificial = false;
1523 last_pred->est_success_rate = 1.0;
1524 return last_pred;
1525}
1526
1527
1528/* Return a pointer to a new predicate, with operator check.
1529 Like get_new_pred, but it checks to make sure that the previous
1530 predicate is an operator. If it isn't, the AND operator is inserted. */
1531
1532struct predicate *
1533get_new_pred_chk_op (const struct parser_table *entry)
1534{
1535 struct predicate *new_pred;
1536 static const struct parser_table *entry_and = NULL;
1537
1538 /* Locate the entry in the parser table for the "and" operator */
1539 if (NULL == entry_and)
1540 entry_and = find_parser("and");
1541
1542 /* Check that it's actually there. If not, that is a bug.*/
1543 assert(entry_and != NULL);
1544
1545 if (last_pred)
1546 switch (last_pred->p_type)
1547 {
1548 case NO_TYPE:
1549 error (1, 0, _("oops -- invalid default insertion of and!"));
1550 break;
1551
1552 case PRIMARY_TYPE:
1553 case CLOSE_PAREN:
1554 /* We need to interpose the and operator. */
1555 new_pred = get_new_pred (entry_and);
1556 new_pred->pred_func = pred_and;
1557 new_pred->p_name = "-a";
1558 new_pred->p_type = BI_OP;
1559 new_pred->p_prec = AND_PREC;
1560 new_pred->need_stat = false;
1561 new_pred->need_type = false;
1562 new_pred->args.str = NULL;
1563 new_pred->side_effects = false;
1564 new_pred->no_default_print = false;
1565 break;
1566
1567 default:
1568 break;
1569 }
1570
1571 new_pred = get_new_pred (entry);
1572 new_pred->parser_entry = entry;
1573 return new_pred;
1574}
1575
1576
1577struct cost_assoc
1578{
1579 enum EvaluationCost cost;
1580 char *name;
1581};
1582struct cost_assoc cost_table[] =
1583 {
1584 { NeedsNothing, "Nothing" },
1585 { NeedsType, "Type" },
1586 { NeedsStatInfo, "StatInfo" },
1587 { NeedsLinkName, "LinkName" },
1588 { NeedsAccessInfo, "AccessInfo" },
1589 { NeedsSyncDiskHit, "SyncDiskHit" },
1590 { NeedsEventualExec, "EventualExec" },
1591 { NeedsImmediateExec, "ImmediateExec" },
1592 { NeedsUserInteraction, "UserInteraction" },
1593 { NeedsUnknown, "Unknown" }
1594 };
1595
1596
1597struct prec_assoc
1598{
1599 short prec;
1600 char *prec_name;
1601};
1602
1603static struct prec_assoc prec_table[] =
1604{
1605 {NO_PREC, "no"},
1606 {COMMA_PREC, "comma"},
1607 {OR_PREC, "or"},
1608 {AND_PREC, "and"},
1609 {NEGATE_PREC, "negate"},
1610 {MAX_PREC, "max"},
1611 {-1, "unknown "}
1612};
1613
1614
1615struct op_assoc
1616{
1617 short type;
1618 char *type_name;
1619};
1620
1621static struct op_assoc type_table[] =
1622{
1623 {NO_TYPE, "no"},
1624 {PRIMARY_TYPE, "primary"},
1625 {UNI_OP, "uni_op"},
1626 {BI_OP, "bi_op"},
1627 {OPEN_PAREN, "open_paren "},
1628 {CLOSE_PAREN, "close_paren "},
1629 {-1, "unknown"}
1630};
1631
1632
1633static const char *
1634cost_name (enum EvaluationCost cost)
1635{
1636 unsigned int i;
1637 unsigned int n = sizeof(cost_table)/sizeof(cost_table[0]);
1638
1639 for (i = 0; i<n; ++i)
1640 if (cost_table[i].cost == cost)
1641 return cost_table[i].name;
1642 return "unknown";
1643}
1644
1645
1646
1647static char *
1648type_name (type)
1649 short type;
1650{
1651 int i;
1652
1653 for (i = 0; type_table[i].type != (short) -1; i++)
1654 if (type_table[i].type == type)
1655 break;
1656 return (type_table[i].type_name);
1657}
1658
1659
1660static char *
1661prec_name (prec)
1662 short prec;
1663{
1664 int i;
1665
1666 for (i = 0; prec_table[i].prec != (short) -1; i++)
1667 if (prec_table[i].prec == prec)
1668 break;
1669 return (prec_table[i].prec_name);
1670}
1671
1672
1673
1674/* Walk the expression tree NODE to stdout.
1675 INDENT is the number of levels to indent the left margin. */
1676
1677void
1678print_tree (FILE *fp, struct predicate *node, int indent)
1679{
1680 int i;
1681
1682 if (node == NULL)
1683 return;
1684 for (i = 0; i < indent; i++)
1685 fprintf (fp, " ");
1686 fprintf (fp, "pred=[");
1687 print_predicate(fp, node);
1688 fprintf (fp, "] type=%s prec=%s",
1689 type_name (node->p_type), prec_name (node->p_prec));
1690 fprintf (fp, " cost=%s rate=%#03.2g %sside effects ",
1691 cost_name(node->p_cost),
1692 node->est_success_rate,
1693 (node->side_effects ? "" : "no "));
1694
1695 if (node->need_stat || node->need_type)
1696 {
1697 int comma = 0;
1698
1699 fprintf (fp, "Needs ");
1700 if (node->need_stat)
1701 {
1702 fprintf (fp, "stat");
1703 comma = 1;
1704 }
1705 if (node->need_type)
1706 {
1707 fprintf (fp, "%stype", comma ? "," : "");
1708 }
1709 }
1710 fprintf (fp, "\n");
1711
1712
1713 for (i = 0; i < indent; i++)
1714 fprintf (fp, " ");
1715 if (NULL == node->pred_left && NULL == node->pred_right)
1716 {
1717 fprintf (fp, "no children.\n");
1718 }
1719 else
1720 {
1721 if (node->pred_left)
1722 {
1723 fprintf (fp, "left:\n");
1724 print_tree (fp, node->pred_left, indent + 1);
1725 }
1726 else
1727 {
1728 fprintf (fp, "no left.\n");
1729 }
1730
1731 for (i = 0; i < indent; i++)
1732 fprintf (fp, " ");
1733 if (node->pred_right)
1734 {
1735 fprintf (fp, "right:\n");
1736 print_tree (fp, node->pred_right, indent + 1);
1737 }
1738 else
1739 {
1740 fprintf (fp, "no right.\n");
1741 }
1742 }
1743}
Note: See TracBrowser for help on using the repository browser.