1 /* tree.c -- helper functions to build and evaluate the expression tree.
2 Copyright (C) 1990, 91, 92, 93, 94 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., 675 Mass Ave, Cambridge, MA 02139, USA. */
19 #include <sys/types.h>
26 # define _(Text) gettext (Text)
31 # define N_(String) gettext_noop (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
, short int prev_prec
)
64 struct predicate
*next
;
67 error (1, 0, _("invalid expression"));
68 switch ((*input
)->p_type
)
73 error (1, 0, _("invalid expression"));
78 *input
= (*input
)->pred_next
;
83 *input
= (*input
)->pred_next
;
84 next
->pred_right
= get_expr (input
, NEGATE_PREC
);
88 *input
= (*input
)->pred_next
;
89 next
= get_expr (input
, NO_PREC
);
91 || ((*input
)->p_type
!= CLOSE_PAREN
))
92 error (1, 0, _("invalid expression"));
93 *input
= (*input
)->pred_next
; /* move over close */
97 error (1, 0, _("oops -- invalid expression type!"));
101 /* We now have the first expression and are positioned to check
102 out the next operator. If NULL, all done. Otherwise, if
103 PREV_PREC < the current node precedence, we must continue;
104 the expression we just nabbed is more tightly bound to the
105 following expression than to the previous one. */
108 if ((int) (*input
)->p_prec
> (int) prev_prec
)
110 next
= scan_rest (input
, next
, prev_prec
);
112 error (1, 0, _("invalid expression"));
117 /* Scan across the remainder of a predicate input list starting
118 at *INPUT, building the rest of the expression tree to return.
119 Stop at the first close parenthesis or the end of the input list.
120 Assumes that get_expr has been called to nab the first element
121 of the expression tree.
123 *INPUT points to the current input predicate list element.
124 It is updated as we move along the list to point to the
125 terminating input element.
126 HEAD points to the predicate element that was obtained
127 by the call to get_expr.
128 PREV_PREC is the precedence of the previous predicate element. */
130 static struct predicate
*
131 scan_rest (struct predicate
**input
,
132 struct predicate
*head
,
135 struct predicate
*tree
; /* The new tree we are building. */
137 if ((*input
== NULL
) || ((*input
)->p_type
== CLOSE_PAREN
))
140 while ((*input
!= NULL
) && ((int) (*input
)->p_prec
> (int) prev_prec
))
142 switch ((*input
)->p_type
)
148 error (1, 0, _("invalid expression"));
152 (*input
)->pred_left
= tree
;
154 *input
= (*input
)->pred_next
;
155 tree
->pred_right
= get_expr (input
, tree
->p_prec
);
162 error (1, 0, _("oops -- invalid expression type!"));
169 /* Optimize the ordering of the predicates in the tree. Rearrange
170 them to minimize work. Strategies:
171 * Evaluate predicates that don't need inode information first;
172 the predicates are divided into 1 or more groups separated by
173 predicates (if any) which have "side effects", such as printing.
174 The grouping implements the partial ordering on predicates which
175 those with side effects impose.
176 * Place -name, -path, and -regex at the front of a group, with
177 -name and -path ahead of -regex. Predicates that are moved to the
178 front of a group by definition do not have side effects.
180 This routine "normalizes" the predicate tree by ensuring that
181 all expression predicates have AND (or OR or COMMA) parent nodes
182 which are linked along the left edge of the expression tree.
183 This makes manipulation of subtrees easier.
185 EVAL_TREEP points to the root pointer of the predicate tree
186 to be rearranged. opt_expr may return a new root pointer there.
187 Return true if the tree contains side effects, false if not. */
190 opt_expr (struct predicate
**eval_treep
)
192 /* List of -name and -path predicates to move. */
193 struct predicate
*name_list
= NULL
;
194 struct predicate
*end_name_list
= NULL
;
195 /* List of -regex predicates to move. */
196 struct predicate
*regex_list
= NULL
;
197 struct predicate
*end_regex_list
= NULL
;
198 struct predicate
*curr
;
199 struct predicate
**prevp
; /* Address of `curr' node. */
200 struct predicate
**last_sidep
; /* Last predicate with side effects. */
202 enum predicate_type p_type
;
203 boolean has_side_effects
= false; /* Return value. */
204 enum predicate_precedence prev_prec
, /* precedence of last BI_OP in branch */
205 biop_prec
; /* topmost BI_OP precedence in branch */
208 if (eval_treep
== NULL
|| *eval_treep
== NULL
)
211 /* Set up to normalize tree as a left-linked list of ANDs or ORs.
212 Set `curr' to the leftmost node, `prevp' to its address, and
213 `pred_func' to the predicate type of its parent. */
215 prev_prec
= AND_PREC
;
217 while (curr
->pred_left
!= NULL
)
219 prevp
= &curr
->pred_left
;
220 prev_prec
= curr
->p_prec
; /* must be a BI_OP */
221 curr
= curr
->pred_left
;
224 /* Link in the appropriate BI_OP for the last expression, if needed. */
225 if (curr
->p_type
!= BI_OP
)
226 set_new_parent (curr
, prev_prec
, prevp
);
229 /* Normalized tree. */
230 printf (_("Normalized Eval Tree:\n"));
231 print_tree (*eval_treep
, 0);
234 /* Rearrange the predicates. */
236 if ((*prevp
) && (*prevp
)->p_type
== BI_OP
)
237 biop_prec
= (*prevp
)->p_prec
;
238 while ((curr
= *prevp
) != NULL
)
240 /* If there is a BI_OP of different precedence from the first
241 in the pred_left chain, create a new parent of the
242 original precedence, link the new parent to the left of the
243 previous and link CURR to the right of the new parent.
244 This preserves the precedence of expressions in the tree
245 in case we rearrange them. */
246 if (curr
->p_type
== BI_OP
)
248 if (curr
->p_prec
!= biop_prec
)
249 curr
= set_new_parent(curr
, biop_prec
, prevp
);
252 /* See which predicate type we have. */
253 p_type
= curr
->pred_right
->p_type
;
254 pred_func
= curr
->pred_right
->pred_func
;
260 /* Don't rearrange the arguments of the comma operator, it is
262 if (biop_prec
== COMMA_PREC
)
265 /* If it's one of our special primaries, move it to the
266 front of the list for that primary. */
267 if (pred_func
== pred_name
|| pred_func
== pred_path
)
269 *prevp
= curr
->pred_left
;
270 curr
->pred_left
= name_list
;
273 if (end_name_list
== NULL
)
274 end_name_list
= curr
;
279 if (pred_func
== pred_regex
)
281 *prevp
= curr
->pred_left
;
282 curr
->pred_left
= regex_list
;
285 if (end_regex_list
== NULL
)
286 end_regex_list
= curr
;
294 /* For NOT, check the expression trees below the NOT. */
295 curr
->pred_right
->side_effects
296 = opt_expr (&curr
->pred_right
->pred_right
);
300 /* For nested AND or OR, recurse (AND/OR form layers on the left of
301 the tree), and continue scanning this level of AND or OR. */
302 curr
->pred_right
->side_effects
= opt_expr (&curr
->pred_right
);
305 /* At this point, get_expr and scan_rest have already removed
306 all of the user's parentheses. */
309 error (1, 0, _("oops -- invalid expression type!"));
313 if (curr
->pred_right
->side_effects
== true)
317 /* Incorporate lists and reset list pointers for this group. */
318 if (name_list
!= NULL
)
320 merge_pred (name_list
, end_name_list
, last_sidep
);
321 name_list
= end_name_list
= NULL
;
324 if (regex_list
!= NULL
)
326 merge_pred (regex_list
, end_regex_list
, last_sidep
);
327 regex_list
= end_regex_list
= NULL
;
330 has_side_effects
= true;
333 prevp
= &curr
->pred_left
;
336 /* Do final list merges. */
338 if (name_list
!= NULL
)
339 merge_pred (name_list
, end_name_list
, last_sidep
);
340 if (regex_list
!= NULL
)
341 merge_pred (regex_list
, end_regex_list
, last_sidep
);
343 return (has_side_effects
);
346 /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
349 static struct predicate
*
350 set_new_parent (struct predicate
*curr
, enum predicate_precedence high_prec
, struct predicate
**prevp
)
352 struct predicate
*new_parent
;
354 new_parent
= (struct predicate
*) xmalloc (sizeof (struct predicate
));
355 new_parent
->p_type
= BI_OP
;
356 new_parent
->p_prec
= high_prec
;
357 new_parent
->need_stat
= false;
362 new_parent
->pred_func
= pred_comma
;
365 new_parent
->pred_func
= pred_or
;
368 new_parent
->pred_func
= pred_and
;
374 new_parent
->side_effects
= false;
375 new_parent
->args
.str
= NULL
;
376 new_parent
->pred_next
= NULL
;
378 /* Link in new_parent.
379 Pushes rest of left branch down 1 level to new_parent->pred_right. */
380 new_parent
->pred_left
= NULL
;
381 new_parent
->pred_right
= curr
;
385 new_parent
->p_name
= (char *) find_pred_name (new_parent
->pred_func
);
391 /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
392 into the tree at LAST_P. */
395 merge_pred (struct predicate
*beg_list
, struct predicate
*end_list
, struct predicate
**last_p
)
397 end_list
->pred_left
= *last_p
;
401 /* Find the first node in expression tree TREE that requires
402 a stat call and mark the operator above it as needing a stat
403 before calling the node. Since the expression precedences
404 are represented in the tree, some preds that need stat may not
405 get executed (because the expression value is determined earlier.)
406 So every expression needing stat must be marked as such, not just
407 the earliest, to be sure to obtain the stat. This still guarantees
408 that a stat is made as late as possible. Return true if the top node
409 in TREE requires a stat, false if not. */
412 mark_stat (struct predicate
*tree
)
414 /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
415 to find the first predicate for which the stat is needed. */
416 switch (tree
->p_type
)
420 return tree
->need_stat
;
423 if (mark_stat (tree
->pred_right
))
424 tree
->need_stat
= true;
428 /* ANDs and ORs are linked along ->left ending in NULL. */
429 if (tree
->pred_left
!= NULL
)
430 mark_stat (tree
->pred_left
);
432 if (mark_stat (tree
->pred_right
))
433 tree
->need_stat
= true;
438 error (1, 0, _("oops -- invalid expression type!"));