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