1 /* tree.c -- helper functions to build and evaluate the expression tree.
2 Copyright (C) 1990, 91, 92, 93, 94, 2000, 2003, 2004 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"
25 # define _(Text) gettext (Text)
30 # define N_(String) gettext_noop (String)
32 /* See locate.c for explanation as to why not use (String) */
33 # define N_(String) String
36 static struct predicate
*scan_rest
PARAMS((struct predicate
**input
,
37 struct predicate
*head
,
38 short int prev_prec
));
39 static void merge_pred
PARAMS((struct predicate
*beg_list
, struct predicate
*end_list
, struct predicate
**last_p
));
40 static struct predicate
*set_new_parent
PARAMS((struct predicate
*curr
, enum predicate_precedence high_prec
, struct predicate
**prevp
));
42 /* Return a pointer to a tree that represents the
43 expression prior to non-unary operator *INPUT.
44 Set *INPUT to point at the next input predicate node.
46 Only accepts the following:
49 expression [operators of higher precedence]
51 (arbitrary expression)
52 <uni_op>(arbitrary expression)
54 In other words, you can not start out with a bi_op or close_paren.
56 If the following operator (if any) is of a higher precedence than
57 PREV_PREC, the expression just nabbed is part of a following
58 expression, which really is the expression that should be handed to
59 our caller, so get_expr recurses. */
62 get_expr (struct predicate
**input
,
64 const struct predicate
* prev_pred
)
66 struct predicate
*next
= NULL
;
69 error (1, 0, _("invalid expression"));
71 switch ((*input
)->p_type
)
74 error (1, 0, _("invalid expression"));
78 error (1, 0, _("invalid expression; you have used a binary operator with nothing before it."));
82 if ( (*input
)->artificial
)
84 /* We have reached the end of the user-supplied predicates
87 error (1, 0, _("expected an expression after '%s'"), prev_pred
->p_name
);
91 error (1, 0, _("invalid expression; you have too many ')'"));
97 *input
= (*input
)->pred_next
;
102 *input
= (*input
)->pred_next
;
103 next
->pred_right
= get_expr (input
, NEGATE_PREC
, next
);
107 prev_pred
= (*input
);
108 *input
= (*input
)->pred_next
;
109 if ( (*input
)->p_type
== CLOSE_PAREN
)
111 error (1, 0, _("invalid expression; empty parentheses are not allowed."));
113 next
= get_expr (input
, NO_PREC
, prev_pred
);
115 || ((*input
)->p_type
!= CLOSE_PAREN
))
116 error (1, 0, _("invalid expression; I was expecting to find a ')' somewhere but did not see one."));
117 *input
= (*input
)->pred_next
; /* move over close */
121 error (1, 0, _("oops -- invalid expression type!"));
125 /* We now have the first expression and are positioned to check
126 out the next operator. If NULL, all done. Otherwise, if
127 PREV_PREC < the current node precedence, we must continue;
128 the expression we just nabbed is more tightly bound to the
129 following expression than to the previous one. */
132 if ((int) (*input
)->p_prec
> (int) prev_prec
)
134 next
= scan_rest (input
, next
, prev_prec
);
136 error (1, 0, _("invalid expression"));
141 /* Scan across the remainder of a predicate input list starting
142 at *INPUT, building the rest of the expression tree to return.
143 Stop at the first close parenthesis or the end of the input list.
144 Assumes that get_expr has been called to nab the first element
145 of the expression tree.
147 *INPUT points to the current input predicate list element.
148 It is updated as we move along the list to point to the
149 terminating input element.
150 HEAD points to the predicate element that was obtained
151 by the call to get_expr.
152 PREV_PREC is the precedence of the previous predicate element. */
154 static struct predicate
*
155 scan_rest (struct predicate
**input
,
156 struct predicate
*head
,
159 struct predicate
*tree
; /* The new tree we are building. */
161 if ((*input
== NULL
) || ((*input
)->p_type
== CLOSE_PAREN
))
164 while ((*input
!= NULL
) && ((int) (*input
)->p_prec
> (int) prev_prec
))
166 switch ((*input
)->p_type
)
172 /* I'm not sure how we get here, so it is not obvious what
173 * sort of mistakes might give rise to this condition.
175 error (1, 0, _("invalid expression"));
180 struct predicate
*prev
= (*input
);
181 (*input
)->pred_left
= tree
;
183 *input
= (*input
)->pred_next
;
184 tree
->pred_right
= get_expr (input
, tree
->p_prec
, prev
);
193 _("oops -- invalid expression type (%d)!"),
194 (int)(*input
)->p_type
);
201 /* Optimize the ordering of the predicates in the tree. Rearrange
202 them to minimize work. Strategies:
203 * Evaluate predicates that don't need inode information first;
204 the predicates are divided into 1 or more groups separated by
205 predicates (if any) which have "side effects", such as printing.
206 The grouping implements the partial ordering on predicates which
207 those with side effects impose.
209 * Place -name, -iname, -path, -ipath, -regex and -iregex at the front
210 of a group, with -name, -iname, -path and -ipath ahead of
211 -regex and -iregex. Predicates which are moved to the front
212 of a group by definition do not have side effects. Both
213 -regex and -iregex both use pred_regex.
215 This routine "normalizes" the predicate tree by ensuring that
216 all expression predicates have AND (or OR or COMMA) parent nodes
217 which are linked along the left edge of the expression tree.
218 This makes manipulation of subtrees easier.
220 EVAL_TREEP points to the root pointer of the predicate tree
221 to be rearranged. opt_expr may return a new root pointer there.
222 Return true if the tree contains side effects, false if not. */
225 opt_expr (struct predicate
**eval_treep
)
227 /* List of -name and -path predicates to move. */
228 struct predicate
*name_list
= NULL
;
229 struct predicate
*end_name_list
= NULL
;
230 /* List of -regex predicates to move. */
231 struct predicate
*regex_list
= NULL
;
232 struct predicate
*end_regex_list
= NULL
;
233 struct predicate
*curr
;
234 struct predicate
**prevp
; /* Address of `curr' node. */
235 struct predicate
**last_sidep
; /* Last predicate with side effects. */
237 enum predicate_type p_type
;
238 boolean has_side_effects
= false; /* Return value. */
239 enum predicate_precedence prev_prec
, /* precedence of last BI_OP in branch */
240 biop_prec
; /* topmost BI_OP precedence in branch */
243 if (eval_treep
== NULL
|| *eval_treep
== NULL
)
246 /* Set up to normalize tree as a left-linked list of ANDs or ORs.
247 Set `curr' to the leftmost node, `prevp' to its address, and
248 `pred_func' to the predicate type of its parent. */
250 prev_prec
= AND_PREC
;
252 while (curr
->pred_left
!= NULL
)
254 prevp
= &curr
->pred_left
;
255 prev_prec
= curr
->p_prec
; /* must be a BI_OP */
256 curr
= curr
->pred_left
;
259 /* Link in the appropriate BI_OP for the last expression, if needed. */
260 if (curr
->p_type
!= BI_OP
)
261 set_new_parent (curr
, prev_prec
, prevp
);
264 /* Normalized tree. */
265 fprintf (stderr
, "Normalized Eval Tree:\n");
266 print_tree (stderr
, *eval_treep
, 0);
269 /* Rearrange the predicates. */
271 biop_prec
= NO_PREC
; /* not COMMA_PREC */
272 if ((*prevp
) && (*prevp
)->p_type
== BI_OP
)
273 biop_prec
= (*prevp
)->p_prec
;
274 while ((curr
= *prevp
) != NULL
)
276 /* If there is a BI_OP of different precedence from the first
277 in the pred_left chain, create a new parent of the
278 original precedence, link the new parent to the left of the
279 previous and link CURR to the right of the new parent.
280 This preserves the precedence of expressions in the tree
281 in case we rearrange them. */
282 if (curr
->p_type
== BI_OP
)
284 if (curr
->p_prec
!= biop_prec
)
285 curr
= set_new_parent(curr
, biop_prec
, prevp
);
288 /* See which predicate type we have. */
289 p_type
= curr
->pred_right
->p_type
;
290 pred_func
= curr
->pred_right
->pred_func
;
296 /* Don't rearrange the arguments of the comma operator, it is
298 if (biop_prec
== COMMA_PREC
)
301 /* If it's one of our special primaries, move it to the
302 front of the list for that primary. */
303 if (pred_func
== pred_name
|| pred_func
== pred_path
||
304 pred_func
== pred_iname
|| pred_func
== pred_ipath
)
306 *prevp
= curr
->pred_left
;
307 curr
->pred_left
= name_list
;
310 if (end_name_list
== NULL
)
311 end_name_list
= curr
;
316 if (pred_func
== pred_regex
)
318 *prevp
= curr
->pred_left
;
319 curr
->pred_left
= regex_list
;
322 if (end_regex_list
== NULL
)
323 end_regex_list
= curr
;
331 /* For NOT, check the expression trees below the NOT. */
332 curr
->pred_right
->side_effects
333 = opt_expr (&curr
->pred_right
->pred_right
);
337 /* For nested AND or OR, recurse (AND/OR form layers on the left of
338 the tree), and continue scanning this level of AND or OR. */
339 curr
->pred_right
->side_effects
= opt_expr (&curr
->pred_right
);
342 /* At this point, get_expr and scan_rest have already removed
343 all of the user's parentheses. */
346 error (1, 0, _("oops -- invalid expression type!"));
350 if (curr
->pred_right
->side_effects
== true)
354 /* Incorporate lists and reset list pointers for this group. */
355 if (name_list
!= NULL
)
357 merge_pred (name_list
, end_name_list
, last_sidep
);
358 name_list
= end_name_list
= NULL
;
361 if (regex_list
!= NULL
)
363 merge_pred (regex_list
, end_regex_list
, last_sidep
);
364 regex_list
= end_regex_list
= NULL
;
367 has_side_effects
= true;
370 prevp
= &curr
->pred_left
;
373 /* Do final list merges. */
375 if (name_list
!= NULL
)
376 merge_pred (name_list
, end_name_list
, last_sidep
);
377 if (regex_list
!= NULL
)
378 merge_pred (regex_list
, end_regex_list
, last_sidep
);
380 return (has_side_effects
);
383 /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
386 static struct predicate
*
387 set_new_parent (struct predicate
*curr
, enum predicate_precedence high_prec
, struct predicate
**prevp
)
389 struct predicate
*new_parent
;
391 new_parent
= (struct predicate
*) xmalloc (sizeof (struct predicate
));
392 new_parent
->p_type
= BI_OP
;
393 new_parent
->p_prec
= high_prec
;
394 new_parent
->need_stat
= false;
395 new_parent
->need_type
= false;
400 new_parent
->pred_func
= pred_comma
;
403 new_parent
->pred_func
= pred_or
;
406 new_parent
->pred_func
= pred_and
;
412 new_parent
->side_effects
= false;
413 new_parent
->no_default_print
= false;
414 new_parent
->args
.str
= NULL
;
415 new_parent
->pred_next
= NULL
;
417 /* Link in new_parent.
418 Pushes rest of left branch down 1 level to new_parent->pred_right. */
419 new_parent
->pred_left
= NULL
;
420 new_parent
->pred_right
= curr
;
424 new_parent
->p_name
= (char *) find_pred_name (new_parent
->pred_func
);
430 /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
431 into the tree at LAST_P. */
434 merge_pred (struct predicate
*beg_list
, struct predicate
*end_list
, struct predicate
**last_p
)
436 end_list
->pred_left
= *last_p
;
440 /* Find the first node in expression tree TREE that requires
441 a stat call and mark the operator above it as needing a stat
442 before calling the node. Since the expression precedences
443 are represented in the tree, some preds that need stat may not
444 get executed (because the expression value is determined earlier.)
445 So every expression needing stat must be marked as such, not just
446 the earliest, to be sure to obtain the stat. This still guarantees
447 that a stat is made as late as possible. Return true if the top node
448 in TREE requires a stat, false if not. */
451 mark_stat (struct predicate
*tree
)
453 /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
454 to find the first predicate for which the stat is needed. */
455 switch (tree
->p_type
)
459 return tree
->need_stat
;
462 if (mark_stat (tree
->pred_right
))
463 tree
->need_stat
= true;
467 /* ANDs and ORs are linked along ->left ending in NULL. */
468 if (tree
->pred_left
!= NULL
)
469 mark_stat (tree
->pred_left
);
471 if (mark_stat (tree
->pred_right
))
472 tree
->need_stat
= true;
477 error (1, 0, _("oops -- invalid expression type in mark_stat!"));
482 /* Find the first node in expression tree TREE that we will
483 need to know the file type, if any. Operates in the same
487 mark_type (struct predicate
*tree
)
489 /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
490 to find the first predicate for which the type information is needed. */
491 switch (tree
->p_type
)
495 return tree
->need_type
;
498 if (mark_type (tree
->pred_right
))
499 tree
->need_type
= true;
503 /* ANDs and ORs are linked along ->left ending in NULL. */
504 if (tree
->pred_left
!= NULL
)
505 mark_type (tree
->pred_left
);
507 if (mark_type (tree
->pred_right
))
508 tree
->need_type
= true;
513 error (1, 0, _("oops -- invalid expression type in mark_type!"));