1 /* tree.c -- helper functions to build and evaluate the expression tree.
2 Copyright (C) 1990, 91, 92, 93, 94, 2000, 2003, 2004, 2005 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2, or (at your option)
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.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 #include "../gnulib/lib/xalloc.h"
28 # define _(Text) gettext (Text)
33 # define N_(String) gettext_noop (String)
35 /* See locate.c for explanation as to why not use (String) */
36 # define N_(String) String
41 /* All predicates for each path to process. */
42 static struct predicate
*predicates
= NULL
;
44 /* The root of the evaluation tree. */
45 static struct predicate
*eval_tree
= NULL
;
47 /* The last predicate allocated. */
48 static struct predicate
*last_pred
= NULL
;
51 static struct predicate
*scan_rest
PARAMS((struct predicate
**input
,
52 struct predicate
*head
,
53 short int prev_prec
));
54 static void merge_pred
PARAMS((struct predicate
*beg_list
, struct predicate
*end_list
, struct predicate
**last_p
));
55 static struct predicate
*set_new_parent
PARAMS((struct predicate
*curr
, enum predicate_precedence high_prec
, struct predicate
**prevp
));
56 static const char *cost_name
PARAMS((enum EvaluationCost cost
));
59 /* Return a pointer to a tree that represents the
60 expression prior to non-unary operator *INPUT.
61 Set *INPUT to point at the next input predicate node.
63 Only accepts the following:
66 expression [operators of higher precedence]
68 (arbitrary expression)
69 <uni_op>(arbitrary expression)
71 In other words, you can not start out with a bi_op or close_paren.
73 If the following operator (if any) is of a higher precedence than
74 PREV_PREC, the expression just nabbed is part of a following
75 expression, which really is the expression that should be handed to
76 our caller, so get_expr recurses. */
79 get_expr (struct predicate
**input
,
81 const struct predicate
* prev_pred
)
83 struct predicate
*next
= NULL
;
84 struct predicate
*this_pred
= (*input
);
87 error (1, 0, _("invalid expression"));
89 switch ((*input
)->p_type
)
92 error (1, 0, _("invalid expression"));
96 /* e.g. "find . -a" */
97 error (1, 0, _("invalid expression; you have used a binary operator '%s' with nothing before it."), this_pred
->p_name
);
101 if ((UNI_OP
== prev_pred
->p_type
102 || BI_OP
== prev_pred
->p_type
)
103 && !this_pred
->artificial
)
105 /* e.g. "find \( -not \)" or "find \( -true -a \" */
106 error(1, 0, _("expected an expression between '%s' and ')'"),
109 else if ( (*input
)->artificial
)
111 /* We have reached the end of the user-supplied predicates
114 /* e.g. "find . -true -a" */
115 error (1, 0, _("expected an expression after '%s'"), prev_pred
->p_name
);
119 error (1, 0, _("invalid expression; you have too many ')'"));
125 *input
= (*input
)->pred_next
;
130 *input
= (*input
)->pred_next
;
131 next
->pred_right
= get_expr (input
, NEGATE_PREC
, next
);
135 if ( (NULL
== (*input
)->pred_next
) || (*input
)->pred_next
->artificial
)
137 /* user typed something like "find . (", and so the ) we are
138 * looking at is from the artificial "( ) -print" that we
141 error (1, 0, _("invalid expression; expected to find a ')' but didn't see one. Perhaps you need an extra predicate after '%s'"), this_pred
->p_name
);
143 prev_pred
= (*input
);
144 *input
= (*input
)->pred_next
;
145 if ( (*input
)->p_type
== CLOSE_PAREN
)
147 error (1, 0, _("invalid expression; empty parentheses are not allowed."));
149 next
= get_expr (input
, NO_PREC
, prev_pred
);
151 || ((*input
)->p_type
!= CLOSE_PAREN
))
152 error (1, 0, _("invalid expression; I was expecting to find a ')' somewhere but did not see one."));
153 *input
= (*input
)->pred_next
; /* move over close */
157 error (1, 0, _("oops -- invalid expression type!"));
161 /* We now have the first expression and are positioned to check
162 out the next operator. If NULL, all done. Otherwise, if
163 PREV_PREC < the current node precedence, we must continue;
164 the expression we just nabbed is more tightly bound to the
165 following expression than to the previous one. */
168 if ((int) (*input
)->p_prec
> (int) prev_prec
)
170 next
= scan_rest (input
, next
, prev_prec
);
172 error (1, 0, _("invalid expression"));
177 /* Scan across the remainder of a predicate input list starting
178 at *INPUT, building the rest of the expression tree to return.
179 Stop at the first close parenthesis or the end of the input list.
180 Assumes that get_expr has been called to nab the first element
181 of the expression tree.
183 *INPUT points to the current input predicate list element.
184 It is updated as we move along the list to point to the
185 terminating input element.
186 HEAD points to the predicate element that was obtained
187 by the call to get_expr.
188 PREV_PREC is the precedence of the previous predicate element. */
190 static struct predicate
*
191 scan_rest (struct predicate
**input
,
192 struct predicate
*head
,
195 struct predicate
*tree
; /* The new tree we are building. */
197 if ((*input
== NULL
) || ((*input
)->p_type
== CLOSE_PAREN
))
200 while ((*input
!= NULL
) && ((int) (*input
)->p_prec
> (int) prev_prec
))
202 switch ((*input
)->p_type
)
208 /* I'm not sure how we get here, so it is not obvious what
209 * sort of mistakes might give rise to this condition.
211 error (1, 0, _("invalid expression"));
216 struct predicate
*prev
= (*input
);
217 (*input
)->pred_left
= tree
;
219 *input
= (*input
)->pred_next
;
220 tree
->pred_right
= get_expr (input
, tree
->p_prec
, prev
);
229 _("oops -- invalid expression type (%d)!"),
230 (int)(*input
)->p_type
);
237 /* Returns true if the specified predicate is reorderable. */
239 predicate_is_cost_free(const struct predicate
*p
)
241 PRED_FUNC pred_func
= p
->pred_func
;
243 if (pred_func
== pred_name
|| pred_func
== pred_path
||
244 pred_func
== pred_iname
|| pred_func
== pred_ipath
)
246 /* Traditionally (at least 4.1.7 through 4.2.x) GNU find always
247 * optimised these cases.
251 else if (options
.optimisation_level
> 0)
253 if (pred_func
== pred_and
|| pred_func
== pred_negate
||
254 pred_func
== pred_comma
|| pred_func
== pred_or
)
257 return NeedsNothing
== p
->p_cost
;
265 /* Prints a predicate */
266 void print_predicate(FILE *fp
, const struct predicate
*p
)
268 fprintf (fp
, "%s%s%s",
270 p
->arg_text
? " " : "",
271 p
->arg_text
? p
->arg_text
: "");
277 struct predicate
*head
;
278 struct predicate
*tail
;
282 predlist_init(struct predlist
*p
)
284 p
->head
= p
->tail
= NULL
;
288 predlist_insert(struct predlist
*list
,
289 struct predicate
*curr
,
290 struct predicate
**pprev
)
292 struct predicate
**insertpos
= &(list
->head
);
294 *pprev
= curr
->pred_left
;
295 if (options
.optimisation_level
> 2)
297 /* Insert the new node in the list after any other entries which
298 * are more selective.
301 while ( (*insertpos
) && ((*insertpos
)->est_success_rate
< curr
->est_success_rate
) )
303 insertpos
= &((*insertpos
)->pred_left
);
306 curr
->pred_left
= (*insertpos
);
308 if (NULL
== list
->tail
)
309 list
->tail
= list
->head
;
314 predlist_dump(FILE *fp
, const char *label
, const struct predlist
*list
)
316 const struct predicate
*p
;
317 fprintf(fp
, "%s:\n", label
);
318 for (p
=list
->head
; p
; p
=p
->pred_left
)
320 print_optlist(fp
, p
);
327 predlist_merge_nosort(struct predlist
*list
,
328 struct predicate
**last
)
332 calculate_derived_rates(list
->head
);
333 merge_pred(list
->head
, list
->tail
, last
);
340 pred_cost_compare(const struct predicate
*p1
, const struct predicate
*p2
, boolean wantfailure
)
342 if (p1
->p_cost
== p2
->p_cost
)
344 if (p1
->est_success_rate
== p2
->est_success_rate
)
346 else if (wantfailure
)
347 return p1
->est_success_rate
< p2
->est_success_rate
? -1 : 1;
349 return p1
->est_success_rate
< p2
->est_success_rate
? 1 : -1;
353 return p1
->p_cost
< p2
->p_cost
? -1 : 1;
359 predlist_merge_sort(struct predlist
*list
,
360 struct predicate
**last
)
362 struct predlist new_list
;
363 struct predicate
*p
, *q
;
365 if (NULL
== list
->head
)
366 return; /* nothing to do */
368 if (options
.debug_options
& DebugTreeOpt
)
370 fprintf(stderr
, "%s:\n", "predlist before merge sort");
371 print_tree(stderr
, list
->head
, 2);
374 calculate_derived_rates(list
->head
);
375 predlist_init(&new_list
);
378 /* remove head of source list */
380 list
->head
= list
->head
->pred_left
;
383 /* insert it into the new list */
384 for (p
=new_list
.head
; p
; p
=p
->pred_left
)
386 /* If these operations are OR operations, we want to get a
387 * successful test as soon as possible, to take advantage of
388 * the short-circuit evaluation. If they're AND, we want to
389 * get an unsuccessful result early for the same reason.
390 * Therefore we invert the sense of the comparison for the
391 * OR case. We only want to invert the sense of the success
392 * rate comparison, not the operation cost comparison. Hence we
393 * pass a flag into pred_cost_compare().
395 boolean wantfailure
= (OR_PREC
!= p
->p_prec
);
396 if (pred_cost_compare(p
->pred_right
, q
->pred_right
, wantfailure
) >= 0)
401 /* insert into existing list */
402 q
->pred_left
= p
->pred_left
;
403 if (NULL
== q
->pred_left
)
409 q
->pred_left
= new_list
.head
; /* prepend */
411 if (NULL
== new_list
.tail
)
412 new_list
.tail
= q
; /* first item in new list */
415 if (options
.debug_options
& DebugTreeOpt
)
417 fprintf(stderr
, "%s:\n", "predlist after merge sort");
418 print_tree(stderr
, new_list
.head
, 2);
421 calculate_derived_rates(new_list
.head
);
422 merge_pred(new_list
.head
, new_list
.tail
, last
);
427 merge_lists(struct predlist lists
[], int nlists
,
428 struct predlist
*name_list
,
429 struct predlist
*regex_list
,
430 struct predicate
**last
)
433 static void (*mergefn
)(struct predlist
*, struct predicate
**);
435 mergefn
= predlist_merge_sort
;
437 mergefn(name_list
, last
);
438 mergefn(regex_list
, last
);
440 for (i
=0; i
<nlists
; i
++)
441 mergefn(&lists
[i
], last
);
447 subtree_has_side_effects(const struct predicate
*p
)
451 return p
->side_effects
452 || subtree_has_side_effects(p
->pred_left
)
453 || subtree_has_side_effects(p
->pred_right
);
463 worst_cost (const struct predicate
*p
)
467 unsigned int cost_r
, cost_l
, worst
;
468 cost_l
= worst_cost(p
->pred_left
);
469 cost_r
= worst_cost(p
->pred_right
);
470 worst
= (cost_l
> cost_r
) ? cost_l
: cost_r
;
471 if (worst
< p
->p_cost
)
484 perform_arm_swap(struct predicate
*p
)
486 struct predicate
*tmp
= p
->pred_left
->pred_right
;
487 p
->pred_left
->pred_right
= p
->pred_right
;
491 /* Consider swapping p->pred_left->pred_right with p->pred_right,
492 * if that yields a faster evaluation. Normally the left predicate is
495 * If the operation is an OR, we want the left predicate to be the one that
496 * succeeds most often. If it is an AND, we want it to be the predicate that
499 * We don't consider swapping arms of an operator where their cost is
500 * different or where they have side effects.
502 * A viable test case for this is
503 * ./find -D opt -O3 . \! -type f -o -type d
504 * Here, the ! -type f should be evaluated first,
505 * as we assume that 95% of inodes are vanilla files.
508 consider_arm_swap(struct predicate
*p
)
510 int left_cost
, right_cost
;
511 const char *reason
= NULL
;
512 struct predicate
**pl
, **pr
;
514 if (BI_OP
!= p
->p_type
)
515 reason
= "Not a binary operation";
519 if (NULL
== p
->pred_left
|| NULL
== p
->pred_right
)
520 reason
= "Doesn't have two arms";
526 if (NULL
== p
->pred_left
->pred_right
)
527 reason
= "Left arm has no child on RHS";
530 pl
= &p
->pred_left
->pred_right
;
534 if (subtree_has_side_effects(*pl
))
535 reason
= "Left subtree has side-effects";
539 if (subtree_has_side_effects(*pr
))
540 reason
= "Right subtree has side-effects";
545 left_cost
= worst_cost(*pl
);
546 right_cost
= worst_cost(*pr
);
548 if (left_cost
< right_cost
)
550 reason
= "efficient as-is";
557 if (left_cost
== right_cost
)
559 /* it's a candidate */
560 float succ_rate_l
= (*pl
)->est_success_rate
;
561 float succ_rate_r
= (*pr
)->est_success_rate
;
563 if (options
.debug_options
& DebugTreeOpt
)
565 fprintf(stderr
, "Success rates: l=%f, r=%f\n", succ_rate_l
, succ_rate_r
);
568 if (pred_or
== p
->pred_func
)
570 want_swap
= succ_rate_r
< succ_rate_l
;
572 reason
= "Operation is OR and right success rate >= left";
574 else if (pred_and
== p
->pred_func
)
576 want_swap
= succ_rate_r
> succ_rate_l
;
578 reason
= "Operation is AND and right success rate <= left";
583 reason
= "Not AND or OR";
593 if (options
.debug_options
& DebugTreeOpt
)
595 fprintf(stderr
, "Performing arm swap on:\n");
596 print_tree (stderr
, p
, 0);
604 if (options
.debug_options
& DebugTreeOpt
)
606 fprintf(stderr
, "Not an arm swap candidate (%s):\n", reason
);
607 print_tree (stderr
, p
, 0);
613 do_arm_swaps(struct predicate
*p
)
621 if (consider_arm_swap(p
)
622 || do_arm_swaps(p
->pred_left
)
623 || do_arm_swaps(p
->pred_right
))
638 /* Optimize the ordering of the predicates in the tree. Rearrange
639 them to minimize work. Strategies:
640 * Evaluate predicates that don't need inode information first;
641 the predicates are divided into 1 or more groups separated by
642 predicates (if any) which have "side effects", such as printing.
643 The grouping implements the partial ordering on predicates which
644 those with side effects impose.
646 * Place -name, -iname, -path, -ipath, -regex and -iregex at the front
647 of a group, with -name, -iname, -path and -ipath ahead of
648 -regex and -iregex. Predicates which are moved to the front
649 of a group by definition do not have side effects. Both
650 -regex and -iregex both use pred_regex.
652 If higher optimisation levels have been selected, reordering also
653 occurs according to the p_cost member of each predicate (which
654 reflects the performance cost of the test). The ordering also
655 bears in mind whether these operations are more likely to succeed
656 or fail. When evauating a chain of OR conditions, we prefer
657 tests likely to succeed at the front of the list. For AND, we
658 prefer tests likely to fail at the front of the list.
660 This routine "normalizes" the predicate tree by ensuring that
661 all expression predicates have AND (or OR or COMMA) parent nodes
662 which are linked along the left edge of the expression tree.
663 This makes manipulation of subtrees easier.
665 EVAL_TREEP points to the root pointer of the predicate tree
666 to be rearranged. opt_expr may return a new root pointer there.
667 Return true if the tree contains side effects, false if not. */
670 opt_expr (struct predicate
**eval_treep
)
672 struct predlist regex_list
={NULL
,NULL
}, name_list
={NULL
,NULL
};
673 struct predlist cbo_list
[NumEvaluationCosts
];
675 struct predicate
*curr
;
676 struct predicate
**prevp
; /* Address of `curr' node. */
677 struct predicate
**last_sidep
; /* Last predicate with side effects. */
679 enum predicate_type p_type
;
680 boolean has_side_effects
= false; /* Return value. */
681 enum predicate_precedence prev_prec
, /* precedence of last BI_OP in branch */
682 biop_prec
; /* topmost BI_OP precedence in branch */
684 if (eval_treep
== NULL
|| *eval_treep
== NULL
)
687 for (i
=0; i
<NumEvaluationCosts
; i
++)
688 predlist_init(&cbo_list
[i
]);
690 /* Set up to normalize tree as a left-linked list of ANDs or ORs.
691 Set `curr' to the leftmost node, `prevp' to its address, and
692 `pred_func' to the predicate type of its parent. */
694 prev_prec
= AND_PREC
;
696 while (curr
->pred_left
!= NULL
)
698 prevp
= &curr
->pred_left
;
699 prev_prec
= curr
->p_prec
; /* must be a BI_OP */
700 curr
= curr
->pred_left
;
703 /* Link in the appropriate BI_OP for the last expression, if needed. */
704 if (curr
->p_type
!= BI_OP
)
705 set_new_parent (curr
, prev_prec
, prevp
);
707 if (options
.debug_options
& (DebugExpressionTree
|DebugTreeOpt
))
709 /* Normalized tree. */
710 fprintf (stderr
, "Normalized Eval Tree:\n");
711 print_tree (stderr
, *eval_treep
, 0);
714 /* Rearrange the predicates. */
716 biop_prec
= NO_PREC
; /* not COMMA_PREC */
717 if ((*prevp
) && (*prevp
)->p_type
== BI_OP
)
718 biop_prec
= (*prevp
)->p_prec
;
719 while ((curr
= *prevp
) != NULL
)
721 /* If there is a BI_OP of different precedence from the first
722 in the pred_left chain, create a new parent of the
723 original precedence, link the new parent to the left of the
724 previous and link CURR to the right of the new parent.
725 This preserves the precedence of expressions in the tree
726 in case we rearrange them. */
727 if (curr
->p_type
== BI_OP
)
729 if (curr
->p_prec
!= biop_prec
)
730 curr
= set_new_parent(curr
, biop_prec
, prevp
);
733 /* See which predicate type we have. */
734 p_type
= curr
->pred_right
->p_type
;
735 pred_func
= curr
->pred_right
->pred_func
;
742 /* Don't rearrange the arguments of the comma operator, it is
744 if (biop_prec
== COMMA_PREC
)
747 /* If this predicate has no side effects, consider reordering it. */
748 if (!curr
->pred_right
->side_effects
)
752 /* If it's one of our special primaries, move it to the
753 front of the list for that primary. */
754 if (predicate_is_cost_free(curr
->pred_right
))
756 if (options
.debug_options
& DebugTreeOpt
)
758 fprintf(stderr
, "-O%d: promoting cheap predicate ",
759 (int)options
.optimisation_level
);
760 print_predicate(stderr
, curr
->pred_right
);
761 fprintf(stderr
, " into name_list\n");
763 predlist_insert(&name_list
, curr
, prevp
);
767 if (pred_func
== pred_regex
)
769 predlist_insert(®ex_list
, curr
, prevp
);
773 reorder
= ((options
.optimisation_level
> 1)
774 && (NeedsType
== curr
->pred_right
->p_cost
)
775 && !curr
->pred_right
->need_stat
) ||
776 (options
.optimisation_level
> 2);
780 if (options
.debug_options
& DebugTreeOpt
)
782 fprintf(stderr
, "-O%d: categorising predicate ",
783 (int)options
.optimisation_level
);
784 print_predicate(stderr
, curr
->pred_right
);
785 fprintf(stderr
, " by cost (%s)\n",
786 cost_name(curr
->pred_right
->p_cost
));
788 predlist_insert(&cbo_list
[curr
->pred_right
->p_cost
], curr
, prevp
);
796 /* For NOT, check the expression trees below the NOT. */
797 curr
->pred_right
->side_effects
798 = opt_expr (&curr
->pred_right
->pred_right
);
802 /* For nested AND or OR, recurse (AND/OR form layers on the left of
803 the tree), and continue scanning this level of AND or OR. */
804 curr
->pred_right
->side_effects
= opt_expr (&curr
->pred_right
);
807 /* At this point, get_expr and scan_rest have already removed
808 all of the user's parentheses. */
811 error (1, 0, _("oops -- invalid expression type!"));
815 if (curr
->pred_right
->side_effects
== true)
819 /* Incorporate lists and reset list pointers for this group. */
820 merge_lists(cbo_list
, NumEvaluationCosts
, &name_list
, ®ex_list
, last_sidep
);
821 has_side_effects
= true;
824 prevp
= &curr
->pred_left
;
827 /* Do final list merges. */
829 merge_lists(cbo_list
, NumEvaluationCosts
, &name_list
, ®ex_list
, last_sidep
);
830 return has_side_effects
;
834 constrain_rate(float rate
)
844 /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
847 static struct predicate
*
848 set_new_parent (struct predicate
*curr
, enum predicate_precedence high_prec
, struct predicate
**prevp
)
850 struct predicate
*new_parent
;
852 new_parent
= (struct predicate
*) xmalloc (sizeof (struct predicate
));
853 new_parent
->p_type
= BI_OP
;
854 new_parent
->p_prec
= high_prec
;
855 new_parent
->need_stat
= false;
856 new_parent
->need_type
= false;
857 new_parent
->p_cost
= NeedsNothing
;
862 new_parent
->pred_func
= pred_comma
;
863 new_parent
->p_name
= ",";
864 new_parent
->est_success_rate
= 1.0;
867 new_parent
->pred_func
= pred_or
;
868 new_parent
->p_name
= "-o";
869 new_parent
->est_success_rate
= constrain_rate(curr
->est_success_rate
);
872 new_parent
->pred_func
= pred_and
;
873 new_parent
->p_name
= "-a";
874 new_parent
->est_success_rate
= constrain_rate(curr
->est_success_rate
);
880 new_parent
->side_effects
= false;
881 new_parent
->no_default_print
= false;
882 new_parent
->args
.str
= NULL
;
883 new_parent
->pred_next
= NULL
;
885 /* Link in new_parent.
886 Pushes rest of left branch down 1 level to new_parent->pred_right. */
887 new_parent
->pred_left
= NULL
;
888 new_parent
->pred_right
= curr
;
894 /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
895 into the tree at LAST_P. */
898 merge_pred (struct predicate
*beg_list
, struct predicate
*end_list
, struct predicate
**last_p
)
900 end_list
->pred_left
= *last_p
;
904 /* Find the first node in expression tree TREE that requires
905 a stat call and mark the operator above it as needing a stat
906 before calling the node. Since the expression precedences
907 are represented in the tree, some preds that need stat may not
908 get executed (because the expression value is determined earlier.)
909 So every expression needing stat must be marked as such, not just
910 the earliest, to be sure to obtain the stat. This still guarantees
911 that a stat is made as late as possible. Return true if the top node
912 in TREE requires a stat, false if not. */
915 mark_stat (struct predicate
*tree
)
917 /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
918 to find the first predicate for which the stat is needed. */
919 switch (tree
->p_type
)
923 return tree
->need_stat
;
926 if (mark_stat (tree
->pred_right
))
927 tree
->need_stat
= true;
931 /* ANDs and ORs are linked along ->left ending in NULL. */
932 if (tree
->pred_left
!= NULL
)
933 mark_stat (tree
->pred_left
);
935 if (mark_stat (tree
->pred_right
))
936 tree
->need_stat
= true;
941 error (1, 0, _("oops -- invalid expression type in mark_stat!"));
946 /* Find the first node in expression tree TREE that we will
947 need to know the file type, if any. Operates in the same
951 mark_type (struct predicate
*tree
)
953 /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
954 to find the first predicate for which the type information is needed. */
955 switch (tree
->p_type
)
959 return tree
->need_type
;
962 if (mark_type (tree
->pred_right
))
963 tree
->need_type
= true;
967 /* ANDs and ORs are linked along ->left ending in NULL. */
968 if (tree
->pred_left
!= NULL
)
969 mark_type (tree
->pred_left
);
971 if (mark_type (tree
->pred_right
))
972 tree
->need_type
= true;
977 error (1, 0, _("oops -- invalid expression type in mark_type!"));
982 struct pred_cost_lookup
985 enum EvaluationCost cost
;
987 static struct pred_cost_lookup costlookup
[] =
989 { pred_amin
, NeedsStatInfo
},
990 { pred_and
, NeedsNothing
, },
991 { pred_anewer
, NeedsStatInfo
, },
992 { pred_atime
, NeedsStatInfo
, },
993 { pred_close
, NeedsNothing
},
994 { pred_cmin
, NeedsStatInfo
, },
995 { pred_cnewer
, NeedsStatInfo
, },
996 { pred_comma
, NeedsNothing
, },
997 { pred_ctime
, NeedsStatInfo
, },
998 { pred_delete
, NeedsSyncDiskHit
},
999 { pred_empty
, NeedsStatInfo
},
1000 { pred_exec
, NeedsEventualExec
},
1001 { pred_execdir
, NeedsEventualExec
},
1002 { pred_executable
, NeedsAccessInfo
},
1003 { pred_false
, NeedsNothing
},
1004 { pred_fprint
, NeedsNothing
},
1005 { pred_fprint0
, NeedsNothing
},
1006 { pred_fprintf
, NeedsNothing
},
1007 { pred_fstype
, NeedsStatInfo
}, /* true for amortised cost */
1008 { pred_gid
, NeedsStatInfo
},
1009 { pred_group
, NeedsStatInfo
},
1010 { pred_ilname
, NeedsLinkName
},
1011 { pred_iname
, NeedsNothing
},
1012 { pred_inum
, NeedsStatInfo
},
1013 { pred_ipath
, NeedsNothing
},
1014 { pred_links
, NeedsStatInfo
},
1015 { pred_lname
, NeedsLinkName
},
1016 { pred_ls
, NeedsStatInfo
},
1017 { pred_mmin
, NeedsStatInfo
},
1018 { pred_mtime
, NeedsStatInfo
},
1019 { pred_name
, NeedsNothing
},
1020 { pred_negate
, NeedsNothing
, },
1021 { pred_newer
, NeedsStatInfo
, },
1022 { pred_nogroup
, NeedsStatInfo
}, /* true for amortised cost if caching is on */
1023 { pred_nouser
, NeedsStatInfo
}, /* true for amortised cost if caching is on */
1024 { pred_ok
, NeedsUserInteraction
},
1025 { pred_okdir
, NeedsUserInteraction
},
1026 { pred_open
, NeedsNothing
},
1027 { pred_or
, NeedsNothing
, },
1028 { pred_path
, NeedsNothing
},
1029 { pred_perm
, NeedsStatInfo
},
1030 { pred_print
, NeedsNothing
},
1031 { pred_print0
, NeedsNothing
},
1032 { pred_prune
, NeedsNothing
},
1033 { pred_quit
, NeedsNothing
},
1034 { pred_readable
, NeedsAccessInfo
},
1035 { pred_regex
, NeedsNothing
},
1036 { pred_samefile
, NeedsStatInfo
},
1037 { pred_size
, NeedsStatInfo
},
1038 { pred_true
, NeedsNothing
},
1039 { pred_type
, NeedsType
},
1040 { pred_uid
, NeedsStatInfo
},
1041 { pred_used
, NeedsStatInfo
},
1042 { pred_user
, NeedsStatInfo
},
1043 { pred_writable
, NeedsAccessInfo
},
1044 { pred_xtype
, NeedsType
} /* roughly correct unless most files are symlinks */
1046 static int pred_table_sorted
= 0;
1049 check_sorted(void *base
, size_t members
, size_t membersize
,
1050 int (*cmpfn
)(const void*, const void*))
1052 const char *p
= base
;
1054 for (i
=1u; i
<members
; ++i
)
1056 int result
= cmpfn(p
+i
*membersize
, p
+(i
-1)*membersize
);
1059 result
= cmpfn(p
+(i
-1)*membersize
, p
+i
*membersize
);
1060 assert(result
<= 0);
1062 for (i
=1u; i
<members
; ++i
)
1064 const struct pred_cost_lookup
*pl1
= (const struct pred_cost_lookup
*)(p
+(i
-1)*membersize
);
1065 const struct pred_cost_lookup
*pl2
= (const struct pred_cost_lookup
*)(p
+(i
-0)*membersize
);
1066 assert(pl1
->fn
<= pl2
->fn
);
1073 cost_table_comparison(const void *p1
, const void *p2
)
1075 const struct pred_cost_lookup
*pc1
= p1
;
1076 const struct pred_cost_lookup
*pc2
= p2
;
1079 if (pc1
->fn
== pc2
->fn
)
1081 else if (pc1
->fn
> pc2
->fn
)
1087 static enum EvaluationCost
1088 get_pred_cost(struct predicate
*p
)
1090 enum EvaluationCost data_requirement_cost
= NeedsNothing
;
1091 enum EvaluationCost inherent_cost
= NeedsUnknown
;
1092 PRED_FUNC f
= p
->pred_func
;
1096 data_requirement_cost
= NeedsStatInfo
;
1098 else if (p
->need_type
)
1100 data_requirement_cost
= NeedsType
;
1104 data_requirement_cost
= NeedsNothing
;
1107 if (pred_exec
== f
|| pred_execdir
== f
)
1109 if (p
->args
.exec_vec
.multiple
)
1110 inherent_cost
= NeedsEventualExec
;
1112 inherent_cost
= NeedsImmediateExec
;
1114 else if (pred_fprintf
== f
)
1116 /* the parser calculated the cost for us. */
1117 inherent_cost
= p
->p_cost
;
1121 struct pred_cost_lookup key
;
1124 if (!pred_table_sorted
)
1127 sizeof(costlookup
)/sizeof(costlookup
[0]),
1128 sizeof(costlookup
[0]),
1129 cost_table_comparison
);
1131 if (!check_sorted(costlookup
,
1132 sizeof(costlookup
)/sizeof(costlookup
[0]),
1133 sizeof(costlookup
[0]),
1134 cost_table_comparison
))
1136 error(1, 0, "Failed to sort the costlookup array.");
1138 pred_table_sorted
= 1;
1140 key
.fn
= p
->pred_func
;
1141 entry
= bsearch(&key
, costlookup
,
1142 sizeof(costlookup
)/sizeof(costlookup
[0]),
1143 sizeof(costlookup
[0]),
1144 cost_table_comparison
);
1147 inherent_cost
= ((const struct pred_cost_lookup
*)entry
)->cost
;
1151 error(0, 0, "warning: no cost entry for predicate %s", p
->p_name
);
1152 inherent_cost
= NeedsUnknown
;
1156 if (inherent_cost
> data_requirement_cost
)
1157 return inherent_cost
;
1159 return data_requirement_cost
;
1163 estimate_costs (struct predicate
*tree
)
1167 estimate_costs(tree
->pred_right
);
1168 estimate_costs(tree
->pred_left
);
1170 tree
->p_cost
= get_pred_cost(tree
);
1181 getrate(const struct predicate
*p
)
1184 return p
->est_success_rate
;
1191 calculate_derived_rates(struct predicate
*p
)
1196 calculate_derived_rates(p
->pred_right
);
1198 calculate_derived_rates(p
->pred_left
);
1200 assert(p
->p_type
!= CLOSE_PAREN
);
1201 assert(p
->p_type
!= OPEN_PAREN
);
1206 assert(NULL
== p
->pred_right
);
1207 assert(NULL
== p
->pred_left
);
1208 return p
->est_success_rate
;
1211 assert(NULL
== p
->pred_right
);
1212 assert(NULL
== p
->pred_left
);
1213 return p
->est_success_rate
;
1216 /* Unary operators must have exactly one operand */
1217 assert(pred_negate
== p
->pred_func
);
1218 assert(NULL
== p
->pred_left
);
1219 p
->est_success_rate
= (1.0 - p
->pred_right
->est_success_rate
);
1220 return p
->est_success_rate
;
1225 /* Binary operators must have two operands */
1226 if (pred_and
== p
->pred_func
)
1228 rate
= getrate(p
->pred_right
) * getrate(p
->pred_left
);
1230 else if (pred_comma
== p
->pred_func
)
1234 else if (pred_or
== p
->pred_func
)
1236 rate
= getrate(p
->pred_right
) + getrate(p
->pred_left
);
1240 /* only and, or and comma are BI_OP. */
1244 p
->est_success_rate
= constrain_rate(rate
);
1246 return p
->est_success_rate
;
1250 p
->est_success_rate
= 1.0;
1251 return p
->est_success_rate
;
1255 /* opt_expr() rearranges predicates such that each left subtree is
1256 * rooted at a logical predicate (e.g. and or or). check_normalization()
1257 * asserts that this property still holds.
1260 static void check_normalization(struct predicate
*p
, boolean at_root
)
1264 assert(BI_OP
== p
->p_type
);
1269 assert(BI_OP
== p
->pred_left
->p_type
);
1270 check_normalization(p
->pred_left
, false);
1274 check_normalization(p
->pred_right
, false);
1279 build_expression_tree(int argc
, char *argv
[], int end_of_leading_options
)
1281 const struct parser_table
*parse_entry
; /* Pointer to the parsing table entry for this expression. */
1282 char *predicate_name
; /* Name of predicate being parsed. */
1283 struct predicate
*cur_pred
;
1284 const struct parser_table
*entry_close
, *entry_print
, *entry_open
;
1289 /* Find where in ARGV the predicates begin by skipping the list of
1292 for (i
= end_of_leading_options
; i
< argc
&& !looks_like_expression(argv
[i
], true); i
++)
1297 /* Enclose the expression in `( ... )' so a default -print will
1298 apply to the whole expression. */
1299 entry_open
= find_parser("(");
1300 entry_close
= find_parser(")");
1301 entry_print
= find_parser("print");
1302 assert(entry_open
!= NULL
);
1303 assert(entry_close
!= NULL
);
1304 assert(entry_print
!= NULL
);
1306 parse_open (entry_open
, argv
, &argc
);
1307 last_pred
->p_name
= "(";
1308 predicates
->artificial
= true;
1309 parse_begin_user_args(argv
, argc
, last_pred
, predicates
);
1310 pred_sanity_check(last_pred
);
1312 /* Build the input order list. */
1315 if (!looks_like_expression(argv
[i
], false))
1317 error (0, 0, _("paths must precede expression: %s"), argv
[i
]);
1318 usage(stderr
, 1, NULL
);
1321 predicate_name
= argv
[i
];
1322 parse_entry
= find_parser (predicate_name
);
1323 if (parse_entry
== NULL
)
1325 /* Command line option not recognized */
1326 error (1, 0, _("invalid predicate `%s'"), predicate_name
);
1331 if (!(*(parse_entry
->parser_func
)) (parse_entry
, argv
, &i
))
1333 if (argv
[i
] == NULL
)
1334 /* Command line option requires an argument */
1335 error (1, 0, _("missing argument to `%s'"), predicate_name
);
1337 error (1, 0, _("invalid argument `%s' to `%s'"),
1338 argv
[i
], predicate_name
);
1342 last_pred
->p_name
= predicate_name
;
1344 /* If the parser consumed an argument, save it. */
1346 last_pred
->arg_text
= argv
[oldi
];
1348 last_pred
->arg_text
= NULL
;
1350 pred_sanity_check(last_pred
);
1351 pred_sanity_check(predicates
); /* XXX: expensive */
1353 parse_end_user_args(argv
, argc
, last_pred
, predicates
);
1354 if (predicates
->pred_next
== NULL
)
1356 /* No predicates that do something other than set a global variable
1357 were given; remove the unneeded initial `(' and add `-print'. */
1358 cur_pred
= predicates
;
1359 predicates
= last_pred
= predicates
->pred_next
;
1360 free ((char *) cur_pred
);
1361 parse_print (entry_print
, argv
, &argc
);
1362 last_pred
->p_name
= "-print";
1363 pred_sanity_check(last_pred
);
1364 pred_sanity_check(predicates
); /* XXX: expensive */
1366 else if (!default_prints (predicates
->pred_next
))
1368 /* One or more predicates that produce output were given;
1369 remove the unneeded initial `('. */
1370 cur_pred
= predicates
;
1371 predicates
= predicates
->pred_next
;
1372 pred_sanity_check(predicates
); /* XXX: expensive */
1373 free ((char *) cur_pred
);
1377 /* `( user-supplied-expression ) -print'. */
1378 parse_close (entry_close
, argv
, &argc
);
1379 last_pred
->p_name
= ")";
1380 last_pred
->artificial
= true;
1381 pred_sanity_check(last_pred
);
1382 parse_print (entry_print
, argv
, &argc
);
1383 last_pred
->p_name
= "-print";
1384 last_pred
->artificial
= true;
1385 pred_sanity_check(last_pred
);
1386 pred_sanity_check(predicates
); /* XXX: expensive */
1389 if (options
.debug_options
& (DebugExpressionTree
|DebugTreeOpt
))
1391 fprintf (stderr
, "Predicate List:\n");
1392 print_list (stderr
, predicates
);
1395 /* do a sanity check */
1396 pred_sanity_check(predicates
);
1398 /* Done parsing the predicates. Build the evaluation tree. */
1399 cur_pred
= predicates
;
1400 eval_tree
= get_expr (&cur_pred
, NO_PREC
, NULL
);
1401 calculate_derived_rates(eval_tree
);
1403 /* Check if we have any left-over predicates (this fixes
1404 * Debian bug #185202).
1406 if (cur_pred
!= NULL
)
1408 /* cur_pred->p_name is often NULL here */
1409 if (cur_pred
->pred_func
== pred_close
)
1411 /* e.g. "find \( -true \) \)" */
1412 error (1, 0, _("you have too many ')'"), cur_pred
->p_name
);
1416 if (cur_pred
->p_name
)
1417 error (1, 0, _("unexpected extra predicate '%s'"), cur_pred
->p_name
);
1419 error (1, 0, _("unexpected extra predicate"));
1423 if (options
.debug_options
& (DebugExpressionTree
|DebugTreeOpt
))
1425 fprintf (stderr
, "Eval Tree:\n");
1426 print_tree (stderr
, eval_tree
, 0);
1429 estimate_costs(eval_tree
);
1431 /* Rearrange the eval tree in optimal-predicate order. */
1432 opt_expr (&eval_tree
);
1434 /* Check that the tree is in normalised order (opt_expr does this) */
1435 check_normalization(eval_tree
, true);
1437 do_arm_swaps(eval_tree
);
1439 /* Check that the tree is still in normalised order */
1440 check_normalization(eval_tree
, true);
1442 /* Determine the point, if any, at which to stat the file. */
1443 mark_stat (eval_tree
);
1444 /* Determine the point, if any, at which to determine file type. */
1445 mark_type (eval_tree
);
1447 if (options
.debug_options
& (DebugExpressionTree
|DebugTreeOpt
))
1449 fprintf (stderr
, "Optimized Eval Tree:\n");
1450 print_tree (stderr
, eval_tree
, 0);
1451 fprintf (stderr
, "Optimized command line:\n");
1452 print_optlist(stderr
, eval_tree
);
1453 fprintf(stderr
, "\n");
1459 /* Return a pointer to a new predicate structure, which has been
1460 linked in as the last one in the predicates list.
1462 Set `predicates' to point to the start of the predicates list.
1463 Set `last_pred' to point to the new last predicate in the list.
1465 Set all cells in the new structure to the default values. */
1468 get_new_pred (const struct parser_table
*entry
)
1470 register struct predicate
*new_pred
;
1473 /* Options should not be turned into predicates. */
1474 assert(entry
->type
!= ARG_OPTION
);
1475 assert(entry
->type
!= ARG_POSITIONAL_OPTION
);
1477 if (predicates
== NULL
)
1479 predicates
= (struct predicate
*)
1480 xmalloc (sizeof (struct predicate
));
1481 last_pred
= predicates
;
1485 new_pred
= (struct predicate
*) xmalloc (sizeof (struct predicate
));
1486 last_pred
->pred_next
= new_pred
;
1487 last_pred
= new_pred
;
1489 last_pred
->parser_entry
= entry
;
1490 last_pred
->pred_func
= NULL
;
1491 last_pred
->p_name
= NULL
;
1492 last_pred
->p_type
= NO_TYPE
;
1493 last_pred
->p_prec
= NO_PREC
;
1494 last_pred
->side_effects
= false;
1495 last_pred
->no_default_print
= false;
1496 last_pred
->need_stat
= true;
1497 last_pred
->need_type
= true;
1498 last_pred
->args
.str
= NULL
;
1499 last_pred
->pred_next
= NULL
;
1500 last_pred
->pred_left
= NULL
;
1501 last_pred
->pred_right
= NULL
;
1502 last_pred
->literal_control_chars
= options
.literal_control_chars
;
1503 last_pred
->artificial
= false;
1504 last_pred
->est_success_rate
= 1.0;
1508 /* Return a pointer to a new predicate, with operator check.
1509 Like get_new_pred, but it checks to make sure that the previous
1510 predicate is an operator. If it isn't, the AND operator is inserted. */
1513 get_new_pred_chk_op (const struct parser_table
*entry
)
1515 struct predicate
*new_pred
;
1516 static const struct parser_table
*entry_and
= NULL
;
1518 /* Locate the entry in the parser table for the "and" operator */
1519 if (NULL
== entry_and
)
1520 entry_and
= find_parser("and");
1522 /* Check that it's actually there. If not, that is a bug.*/
1523 assert(entry_and
!= NULL
);
1526 switch (last_pred
->p_type
)
1529 error (1, 0, _("oops -- invalid default insertion of and!"));
1534 /* We need to interpose the and operator. */
1535 new_pred
= get_new_pred (entry_and
);
1536 new_pred
->pred_func
= pred_and
;
1537 new_pred
->p_name
= "-a";
1538 new_pred
->p_type
= BI_OP
;
1539 new_pred
->p_prec
= AND_PREC
;
1540 new_pred
->need_stat
= false;
1541 new_pred
->need_type
= false;
1542 new_pred
->args
.str
= NULL
;
1543 new_pred
->side_effects
= false;
1544 new_pred
->no_default_print
= false;
1551 new_pred
= get_new_pred (entry
);
1552 new_pred
->parser_entry
= entry
;
1558 enum EvaluationCost cost
;
1561 struct cost_assoc cost_table
[] =
1563 { NeedsNothing
, "Nothing" },
1564 { NeedsType
, "Type" },
1565 { NeedsStatInfo
, "StatInfo" },
1566 { NeedsLinkName
, "LinkName" },
1567 { NeedsAccessInfo
, "AccessInfo" },
1568 { NeedsSyncDiskHit
, "SyncDiskHit" },
1569 { NeedsEventualExec
, "EventualExec" },
1570 { NeedsImmediateExec
, "ImmediateExec" },
1571 { NeedsUserInteraction
, "UserInteraction" },
1572 { NeedsUnknown
, "Unknown" }
1581 static struct prec_assoc prec_table
[] =
1584 {COMMA_PREC
, "comma"},
1587 {NEGATE_PREC
, "negate"},
1598 static struct op_assoc type_table
[] =
1601 {PRIMARY_TYPE
, "primary"},
1604 {OPEN_PAREN
, "open_paren "},
1605 {CLOSE_PAREN
, "close_paren "},
1610 cost_name (enum EvaluationCost cost
)
1613 unsigned int n
= sizeof(cost_table
)/sizeof(cost_table
[0]);
1615 for (i
= 0; i
<n
; ++i
)
1616 if (cost_table
[i
].cost
== cost
)
1617 return cost_table
[i
].name
;
1628 for (i
= 0; type_table
[i
].type
!= (short) -1; i
++)
1629 if (type_table
[i
].type
== type
)
1631 return (type_table
[i
].type_name
);
1640 for (i
= 0; prec_table
[i
].prec
!= (short) -1; i
++)
1641 if (prec_table
[i
].prec
== prec
)
1643 return (prec_table
[i
].prec_name
);
1647 /* Walk the expression tree NODE to stdout.
1648 INDENT is the number of levels to indent the left margin. */
1651 print_tree (FILE *fp
, struct predicate
*node
, int indent
)
1657 for (i
= 0; i
< indent
; i
++)
1659 fprintf (fp
, "pred=[");
1660 print_predicate(fp
, node
);
1661 fprintf (fp
, "] type=%s prec=%s",
1662 type_name (node
->p_type
), prec_name (node
->p_prec
));
1663 fprintf (fp
, " cost=%s rate=%#03.2g %sside effects ",
1664 cost_name(node
->p_cost
),
1665 node
->est_success_rate
,
1666 (node
->side_effects
? "" : "no "));
1668 if (node
->need_stat
|| node
->need_type
)
1672 fprintf (fp
, "Needs ");
1673 if (node
->need_stat
)
1675 fprintf (fp
, "stat");
1678 if (node
->need_type
)
1680 fprintf (fp
, "%stype", comma
? "," : "");
1686 for (i
= 0; i
< indent
; i
++)
1688 if (NULL
== node
->pred_left
&& NULL
== node
->pred_right
)
1690 fprintf (fp
, "no children.\n");
1694 if (node
->pred_left
)
1696 fprintf (fp
, "left:\n");
1697 print_tree (fp
, node
->pred_left
, indent
+ 1);
1701 fprintf (fp
, "no left.\n");
1704 for (i
= 0; i
< indent
; i
++)
1706 if (node
->pred_right
)
1708 fprintf (fp
, "right:\n");
1709 print_tree (fp
, node
->pred_right
, indent
+ 1);
1713 fprintf (fp
, "no right.\n");