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