1 /* tree.c -- helper functions to build and evaluate the expression tree.
2 Copyright (C) 1990, 91, 92, 93, 94, 2000 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., 9 Temple Place - Suite 330, Boston, MA 02111-1307,
24 # define _(Text) gettext (Text)
29 # define N_(String) gettext_noop (String)
31 # define N_(String) (String)
34 static struct predicate
*scan_rest
PARAMS((struct predicate
**input
,
35 struct predicate
*head
,
36 short int prev_prec
));
37 static void merge_pred
PARAMS((struct predicate
*beg_list
, struct predicate
*end_list
, struct predicate
**last_p
));
38 static struct predicate
*set_new_parent
PARAMS((struct predicate
*curr
, enum predicate_precedence high_prec
, struct predicate
**prevp
));
40 /* Return a pointer to a tree that represents the
41 expression prior to non-unary operator *INPUT.
42 Set *INPUT to point at the next input predicate node.
44 Only accepts the following:
47 expression [operators of higher precedence]
49 (arbitrary expression)
50 <uni_op>(arbitrary expression)
52 In other words, you can not start out with a bi_op or close_paren.
54 If the following operator (if any) is of a higher precedence than
55 PREV_PREC, the expression just nabbed is part of a following
56 expression, which really is the expression that should be handed to
57 our caller, so get_expr recurses. */
60 get_expr (struct predicate
**input
, short int prev_prec
)
62 struct predicate
*next
;
65 error (1, 0, _("invalid expression"));
66 switch ((*input
)->p_type
)
71 error (1, 0, _("invalid expression"));
76 *input
= (*input
)->pred_next
;
81 *input
= (*input
)->pred_next
;
82 next
->pred_right
= get_expr (input
, NEGATE_PREC
);
86 *input
= (*input
)->pred_next
;
87 next
= get_expr (input
, NO_PREC
);
89 || ((*input
)->p_type
!= CLOSE_PAREN
))
90 error (1, 0, _("invalid expression"));
91 *input
= (*input
)->pred_next
; /* move over close */
95 error (1, 0, _("oops -- invalid expression type!"));
99 /* We now have the first expression and are positioned to check
100 out the next operator. If NULL, all done. Otherwise, if
101 PREV_PREC < the current node precedence, we must continue;
102 the expression we just nabbed is more tightly bound to the
103 following expression than to the previous one. */
106 if ((int) (*input
)->p_prec
> (int) prev_prec
)
108 next
= scan_rest (input
, next
, prev_prec
);
110 error (1, 0, _("invalid expression"));
115 /* Scan across the remainder of a predicate input list starting
116 at *INPUT, building the rest of the expression tree to return.
117 Stop at the first close parenthesis or the end of the input list.
118 Assumes that get_expr has been called to nab the first element
119 of the expression tree.
121 *INPUT points to the current input predicate list element.
122 It is updated as we move along the list to point to the
123 terminating input element.
124 HEAD points to the predicate element that was obtained
125 by the call to get_expr.
126 PREV_PREC is the precedence of the previous predicate element. */
128 static struct predicate
*
129 scan_rest (struct predicate
**input
,
130 struct predicate
*head
,
133 struct predicate
*tree
; /* The new tree we are building. */
135 if ((*input
== NULL
) || ((*input
)->p_type
== CLOSE_PAREN
))
138 while ((*input
!= NULL
) && ((int) (*input
)->p_prec
> (int) prev_prec
))
140 switch ((*input
)->p_type
)
146 error (1, 0, _("invalid expression"));
150 (*input
)->pred_left
= tree
;
152 *input
= (*input
)->pred_next
;
153 tree
->pred_right
= get_expr (input
, tree
->p_prec
);
160 error (1, 0, _("oops -- invalid expression type!"));
167 /* Optimize the ordering of the predicates in the tree. Rearrange
168 them to minimize work. Strategies:
169 * Evaluate predicates that don't need inode information first;
170 the predicates are divided into 1 or more groups separated by
171 predicates (if any) which have "side effects", such as printing.
172 The grouping implements the partial ordering on predicates which
173 those with side effects impose.
175 * Place -name, -iname, -path, -ipath, -regex and -iregex at the front
176 of a group, with -name, -iname, -path and -ipath ahead of
177 -regex and -iregex. Predicates which are moved to the front
178 of a group by definition do not have side effects. Both
179 -regex and -iregex both use pred_regex.
181 This routine "normalizes" the predicate tree by ensuring that
182 all expression predicates have AND (or OR or COMMA) parent nodes
183 which are linked along the left edge of the expression tree.
184 This makes manipulation of subtrees easier.
186 EVAL_TREEP points to the root pointer of the predicate tree
187 to be rearranged. opt_expr may return a new root pointer there.
188 Return true if the tree contains side effects, false if not. */
191 opt_expr (struct predicate
**eval_treep
)
193 /* List of -name and -path predicates to move. */
194 struct predicate
*name_list
= NULL
;
195 struct predicate
*end_name_list
= NULL
;
196 /* List of -regex predicates to move. */
197 struct predicate
*regex_list
= NULL
;
198 struct predicate
*end_regex_list
= NULL
;
199 struct predicate
*curr
;
200 struct predicate
**prevp
; /* Address of `curr' node. */
201 struct predicate
**last_sidep
; /* Last predicate with side effects. */
203 enum predicate_type p_type
;
204 boolean has_side_effects
= false; /* Return value. */
205 enum predicate_precedence prev_prec
, /* precedence of last BI_OP in branch */
206 biop_prec
; /* topmost BI_OP precedence in branch */
209 if (eval_treep
== NULL
|| *eval_treep
== NULL
)
212 /* Set up to normalize tree as a left-linked list of ANDs or ORs.
213 Set `curr' to the leftmost node, `prevp' to its address, and
214 `pred_func' to the predicate type of its parent. */
216 prev_prec
= AND_PREC
;
218 while (curr
->pred_left
!= NULL
)
220 prevp
= &curr
->pred_left
;
221 prev_prec
= curr
->p_prec
; /* must be a BI_OP */
222 curr
= curr
->pred_left
;
225 /* Link in the appropriate BI_OP for the last expression, if needed. */
226 if (curr
->p_type
!= BI_OP
)
227 set_new_parent (curr
, prev_prec
, prevp
);
230 /* Normalized tree. */
231 printf (_("Normalized Eval Tree:\n"));
232 print_tree (*eval_treep
, 0);
235 /* Rearrange the predicates. */
237 if ((*prevp
) && (*prevp
)->p_type
== BI_OP
)
238 biop_prec
= (*prevp
)->p_prec
;
239 while ((curr
= *prevp
) != NULL
)
241 /* If there is a BI_OP of different precedence from the first
242 in the pred_left chain, create a new parent of the
243 original precedence, link the new parent to the left of the
244 previous and link CURR to the right of the new parent.
245 This preserves the precedence of expressions in the tree
246 in case we rearrange them. */
247 if (curr
->p_type
== BI_OP
)
249 if (curr
->p_prec
!= biop_prec
)
250 curr
= set_new_parent(curr
, biop_prec
, prevp
);
253 /* See which predicate type we have. */
254 p_type
= curr
->pred_right
->p_type
;
255 pred_func
= curr
->pred_right
->pred_func
;
261 /* Don't rearrange the arguments of the comma operator, it is
263 if (biop_prec
== COMMA_PREC
)
266 /* If it's one of our special primaries, move it to the
267 front of the list for that primary. */
268 if (pred_func
== pred_name
|| pred_func
== pred_path
||
269 pred_func
== pred_iname
|| pred_func
== pred_ipath
)
271 *prevp
= curr
->pred_left
;
272 curr
->pred_left
= name_list
;
275 if (end_name_list
== NULL
)
276 end_name_list
= curr
;
281 if (pred_func
== pred_regex
)
283 *prevp
= curr
->pred_left
;
284 curr
->pred_left
= regex_list
;
287 if (end_regex_list
== NULL
)
288 end_regex_list
= curr
;
296 /* For NOT, check the expression trees below the NOT. */
297 curr
->pred_right
->side_effects
298 = opt_expr (&curr
->pred_right
->pred_right
);
302 /* For nested AND or OR, recurse (AND/OR form layers on the left of
303 the tree), and continue scanning this level of AND or OR. */
304 curr
->pred_right
->side_effects
= opt_expr (&curr
->pred_right
);
307 /* At this point, get_expr and scan_rest have already removed
308 all of the user's parentheses. */
311 error (1, 0, _("oops -- invalid expression type!"));
315 if (curr
->pred_right
->side_effects
== true)
319 /* Incorporate lists and reset list pointers for this group. */
320 if (name_list
!= NULL
)
322 merge_pred (name_list
, end_name_list
, last_sidep
);
323 name_list
= end_name_list
= NULL
;
326 if (regex_list
!= NULL
)
328 merge_pred (regex_list
, end_regex_list
, last_sidep
);
329 regex_list
= end_regex_list
= NULL
;
332 has_side_effects
= true;
335 prevp
= &curr
->pred_left
;
338 /* Do final list merges. */
340 if (name_list
!= NULL
)
341 merge_pred (name_list
, end_name_list
, last_sidep
);
342 if (regex_list
!= NULL
)
343 merge_pred (regex_list
, end_regex_list
, last_sidep
);
345 return (has_side_effects
);
348 /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
351 static struct predicate
*
352 set_new_parent (struct predicate
*curr
, enum predicate_precedence high_prec
, struct predicate
**prevp
)
354 struct predicate
*new_parent
;
356 new_parent
= (struct predicate
*) xmalloc (sizeof (struct predicate
));
357 new_parent
->p_type
= BI_OP
;
358 new_parent
->p_prec
= high_prec
;
359 new_parent
->need_stat
= false;
364 new_parent
->pred_func
= pred_comma
;
367 new_parent
->pred_func
= pred_or
;
370 new_parent
->pred_func
= pred_and
;
376 new_parent
->side_effects
= false;
377 new_parent
->no_default_print
= false;
378 new_parent
->args
.str
= NULL
;
379 new_parent
->pred_next
= NULL
;
381 /* Link in new_parent.
382 Pushes rest of left branch down 1 level to new_parent->pred_right. */
383 new_parent
->pred_left
= NULL
;
384 new_parent
->pred_right
= curr
;
388 new_parent
->p_name
= (char *) find_pred_name (new_parent
->pred_func
);
394 /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
395 into the tree at LAST_P. */
398 merge_pred (struct predicate
*beg_list
, struct predicate
*end_list
, struct predicate
**last_p
)
400 end_list
->pred_left
= *last_p
;
404 /* Find the first node in expression tree TREE that requires
405 a stat call and mark the operator above it as needing a stat
406 before calling the node. Since the expression precedences
407 are represented in the tree, some preds that need stat may not
408 get executed (because the expression value is determined earlier.)
409 So every expression needing stat must be marked as such, not just
410 the earliest, to be sure to obtain the stat. This still guarantees
411 that a stat is made as late as possible. Return true if the top node
412 in TREE requires a stat, false if not. */
415 mark_stat (struct predicate
*tree
)
417 /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
418 to find the first predicate for which the stat is needed. */
419 switch (tree
->p_type
)
423 return tree
->need_stat
;
426 if (mark_stat (tree
->pred_right
))
427 tree
->need_stat
= true;
431 /* ANDs and ORs are linked along ->left ending in NULL. */
432 if (tree
->pred_left
!= NULL
)
433 mark_stat (tree
->pred_left
);
435 if (mark_stat (tree
->pred_right
))
436 tree
->need_stat
= true;
441 error (1, 0, _("oops -- invalid expression type!"));