1/* tree.c -- helper functions to build and evaluate the expression tree. 2 Copyright (C) 1990, 91, 92, 93, 94, 2000, 2001, 2003, 2004, 2005, 2006, 2007 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 <http://www.gnu.org/licenses/>. 16*/ 17 18#include "defs.h" 19#include "../gnulib/lib/xalloc.h" 20 21#if ENABLE_NLS 22# include <libintl.h> 23# define _(Text) gettext (Text) 24#else 25# define _(Text) Text 26#endif 27#ifdef gettext_noop 28# define N_(String) gettext_noop (String) 29#else 30/* See locate.c for explanation as to why not use (String) */ 31# define N_(String) String 32#endif 33 34static struct predicate *scan_rest PARAMS((struct predicate **input, 35 struct predicate *head, 36 short int prev_prec)); 37static void merge_pred PARAMS((struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p)); 38static struct predicate *set_new_parent PARAMS((struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp)); 39 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. 43 44 Only accepts the following: 45 46 <primary> 47 expression [operators of higher precedence] 48 <uni_op><primary> 49 (arbitrary expression) 50 <uni_op>(arbitrary expression) 51 52 In other words, you can not start out with a bi_op or close_paren. 53 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. */ 58 59struct predicate * 60get_expr (struct predicate **input, short int prev_prec) 61{ 62 struct predicate *next = NULL; 63 64 if (*input == NULL) 65 error (1, 0, _("invalid expression")); 66 67 switch ((*input)->p_type) 68 { 69 case NO_TYPE: 70 error (1, 0, _("invalid expression")); 71 break; 72 73 case BI_OP: 74 error (1, 0, _("invalid expression; you have used a binary operator with nothing before it.")); 75 break; 76 77 case CLOSE_PAREN: 78 error (1, 0, _("invalid expression; you have too many ')'")); 79 break; 80 81 case PRIMARY_TYPE: 82 next = *input; 83 *input = (*input)->pred_next; 84 break; 85 86 case UNI_OP: 87 next = *input; 88 *input = (*input)->pred_next; 89 next->pred_right = get_expr (input, NEGATE_PREC); 90 break; 91 92 case OPEN_PAREN: 93 *input = (*input)->pred_next; 94 next = get_expr (input, NO_PREC); 95 if ((*input == NULL) 96 || ((*input)->p_type != CLOSE_PAREN)) 97 error (1, 0, _("invalid expression; I was expecting to find a ')' somewhere but did not see one.")); 98 *input = (*input)->pred_next; /* move over close */ 99 break; 100 101 default: 102 error (1, 0, _("oops -- invalid expression type!")); 103 break; 104 } 105 106 /* We now have the first expression and are positioned to check 107 out the next operator. If NULL, all done. Otherwise, if 108 PREV_PREC < the current node precedence, we must continue; 109 the expression we just nabbed is more tightly bound to the 110 following expression than to the previous one. */ 111 if (*input == NULL) 112 return (next); 113 if ((int) (*input)->p_prec > (int) prev_prec) 114 { 115 next = scan_rest (input, next, prev_prec); 116 if (next == NULL) 117 error (1, 0, _("invalid expression")); 118 } 119 return (next); 120} 121 122/* Scan across the remainder of a predicate input list starting 123 at *INPUT, building the rest of the expression tree to return. 124 Stop at the first close parenthesis or the end of the input list. 125 Assumes that get_expr has been called to nab the first element 126 of the expression tree. 127 128 *INPUT points to the current input predicate list element. 129 It is updated as we move along the list to point to the 130 terminating input element. 131 HEAD points to the predicate element that was obtained 132 by the call to get_expr. 133 PREV_PREC is the precedence of the previous predicate element. */ 134 135static struct predicate * 136scan_rest (struct predicate **input, 137 struct predicate *head, 138 short int prev_prec) 139{ 140 struct predicate *tree; /* The new tree we are building. */ 141 142 if ((*input == NULL) || ((*input)->p_type == CLOSE_PAREN)) 143 return (NULL); 144 tree = head; 145 while ((*input != NULL) && ((int) (*input)->p_prec > (int) prev_prec)) 146 { 147 switch ((*input)->p_type) 148 { 149 case NO_TYPE: 150 case PRIMARY_TYPE: 151 case UNI_OP: 152 case OPEN_PAREN: 153 /* I'm not sure how we get here, so it is not obvious what 154 * sort of mistakes might give rise to this condition. 155 */ 156 error (1, 0, _("invalid expression")); 157 break; 158 159 case BI_OP: 160 (*input)->pred_left = tree; 161 tree = *input; 162 *input = (*input)->pred_next; 163 tree->pred_right = get_expr (input, tree->p_prec); 164 break; 165 166 case CLOSE_PAREN: 167 return tree; 168 169 default: 170 error (1, 0, 171 _("oops -- invalid expression type (%d)!"), 172 (int)(*input)->p_type); 173 break; 174 } 175 } 176 return tree; 177} 178 179/* Optimize the ordering of the predicates in the tree. Rearrange 180 them to minimize work. Strategies: 181 * Evaluate predicates that don't need inode information first; 182 the predicates are divided into 1 or more groups separated by 183 predicates (if any) which have "side effects", such as printing. 184 The grouping implements the partial ordering on predicates which 185 those with side effects impose. 186 187 * Place -name, -iname, -path, -ipath, -regex and -iregex at the front 188 of a group, with -name, -iname, -path and -ipath ahead of 189 -regex and -iregex. Predicates which are moved to the front 190 of a group by definition do not have side effects. Both 191 -regex and -iregex both use pred_regex. 192 193 This routine "normalizes" the predicate tree by ensuring that 194 all expression predicates have AND (or OR or COMMA) parent nodes 195 which are linked along the left edge of the expression tree. 196 This makes manipulation of subtrees easier. 197 198 EVAL_TREEP points to the root pointer of the predicate tree 199 to be rearranged. opt_expr may return a new root pointer there. 200 Return true if the tree contains side effects, false if not. */ 201 202boolean 203opt_expr (struct predicate **eval_treep) 204{ 205 /* List of -name and -path predicates to move. */ 206 struct predicate *name_list = NULL; 207 struct predicate *end_name_list = NULL; 208 /* List of -regex predicates to move. */ 209 struct predicate *regex_list = NULL; 210 struct predicate *end_regex_list = NULL; 211 struct predicate *curr; 212 struct predicate **prevp; /* Address of `curr' node. */ 213 struct predicate **last_sidep; /* Last predicate with side effects. */ 214 PRED_FUNC pred_func; 215 enum predicate_type p_type; 216 boolean has_side_effects = false; /* Return value. */ 217 enum predicate_precedence prev_prec, /* precedence of last BI_OP in branch */ 218 biop_prec; /* topmost BI_OP precedence in branch */ 219 220 221 if (eval_treep == NULL || *eval_treep == NULL) 222 return (false); 223 224 /* Set up to normalize tree as a left-linked list of ANDs or ORs. 225 Set `curr' to the leftmost node, `prevp' to its address, and 226 `pred_func' to the predicate type of its parent. */ 227 prevp = eval_treep; 228 prev_prec = AND_PREC; 229 curr = *prevp; 230 while (curr->pred_left != NULL) 231 { 232 prevp = &curr->pred_left; 233 prev_prec = curr->p_prec; /* must be a BI_OP */ 234 curr = curr->pred_left; 235 } 236 237 /* Link in the appropriate BI_OP for the last expression, if needed. */ 238 if (curr->p_type != BI_OP) 239 set_new_parent (curr, prev_prec, prevp); 240 241#ifdef DEBUG 242 /* Normalized tree. */ 243 fprintf (stderr, "Normalized Eval Tree:\n"); 244 print_tree (stderr, *eval_treep, 0); 245#endif 246 247 /* Rearrange the predicates. */ 248 prevp = eval_treep; 249 biop_prec = NO_PREC; /* not COMMA_PREC */ 250 if ((*prevp) && (*prevp)->p_type == BI_OP) 251 biop_prec = (*prevp)->p_prec; 252 while ((curr = *prevp) != NULL) 253 { 254 /* If there is a BI_OP of different precedence from the first 255 in the pred_left chain, create a new parent of the 256 original precedence, link the new parent to the left of the 257 previous and link CURR to the right of the new parent. 258 This preserves the precedence of expressions in the tree 259 in case we rearrange them. */ 260 if (curr->p_type == BI_OP) 261 { 262 if (curr->p_prec != biop_prec) 263 curr = set_new_parent(curr, biop_prec, prevp); 264 } 265 266 /* See which predicate type we have. */ 267 p_type = curr->pred_right->p_type; 268 pred_func = curr->pred_right->pred_func; 269 270 switch (p_type) 271 { 272 case NO_TYPE: 273 case PRIMARY_TYPE: 274 /* Don't rearrange the arguments of the comma operator, it is 275 not commutative. */ 276 if (biop_prec == COMMA_PREC) 277 break; 278 279 /* If it's one of our special primaries, move it to the 280 front of the list for that primary. */ 281 if (pred_func == pred_name || pred_func == pred_path || 282 pred_func == pred_iname || pred_func == pred_ipath) 283 { 284 *prevp = curr->pred_left; 285 curr->pred_left = name_list; 286 name_list = curr; 287 288 if (end_name_list == NULL) 289 end_name_list = curr; 290 291 continue; 292 } 293 294 if (pred_func == pred_regex) 295 { 296 *prevp = curr->pred_left; 297 curr->pred_left = regex_list; 298 regex_list = curr; 299 300 if (end_regex_list == NULL) 301 end_regex_list = curr; 302 303 continue; 304 } 305 306 break; 307 308 case UNI_OP: 309 /* For NOT, check the expression trees below the NOT. */ 310 curr->pred_right->side_effects 311 = opt_expr (&curr->pred_right->pred_right); 312 break; 313 314 case BI_OP: 315 /* For nested AND or OR, recurse (AND/OR form layers on the left of 316 the tree), and continue scanning this level of AND or OR. */ 317 curr->pred_right->side_effects = opt_expr (&curr->pred_right); 318 break; 319 320 /* At this point, get_expr and scan_rest have already removed 321 all of the user's parentheses. */ 322 323 default: 324 error (1, 0, _("oops -- invalid expression type!")); 325 break; 326 } 327 328 if (curr->pred_right->side_effects == true) 329 { 330 last_sidep = prevp; 331 332 /* Incorporate lists and reset list pointers for this group. */ 333 if (name_list != NULL) 334 { 335 merge_pred (name_list, end_name_list, last_sidep); 336 name_list = end_name_list = NULL; 337 } 338 339 if (regex_list != NULL) 340 { 341 merge_pred (regex_list, end_regex_list, last_sidep); 342 regex_list = end_regex_list = NULL; 343 } 344 345 has_side_effects = true; 346 } 347 348 prevp = &curr->pred_left; 349 } 350 351 /* Do final list merges. */ 352 last_sidep = prevp; 353 if (name_list != NULL) 354 merge_pred (name_list, end_name_list, last_sidep); 355 if (regex_list != NULL) 356 merge_pred (regex_list, end_regex_list, last_sidep); 357 358 return (has_side_effects); 359} 360 361/* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence 362 HIGH_PREC. */ 363 364static struct predicate * 365set_new_parent (struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp) 366{ 367 struct predicate *new_parent; 368 369 new_parent = (struct predicate *) xmalloc (sizeof (struct predicate)); 370 new_parent->p_type = BI_OP; 371 new_parent->p_prec = high_prec; 372 new_parent->need_stat = false; 373 new_parent->need_type = false; 374 375 switch (high_prec) 376 { 377 case COMMA_PREC: 378 new_parent->pred_func = pred_comma; 379 break; 380 case OR_PREC: 381 new_parent->pred_func = pred_or; 382 break; 383 case AND_PREC: 384 new_parent->pred_func = pred_and; 385 break; 386 default: 387 ; /* empty */ 388 } 389 390 new_parent->side_effects = false; 391 new_parent->no_default_print = false; 392 new_parent->args.str = NULL; 393 new_parent->pred_next = NULL; 394 395 /* Link in new_parent. 396 Pushes rest of left branch down 1 level to new_parent->pred_right. */ 397 new_parent->pred_left = NULL; 398 new_parent->pred_right = curr; 399 *prevp = new_parent; 400 401#ifdef DEBUG 402 new_parent->p_name = (char *) find_pred_name (new_parent->pred_func); 403#endif /* DEBUG */ 404 405 return (new_parent); 406} 407 408/* Merge the predicate list that starts at BEG_LIST and ends at END_LIST 409 into the tree at LAST_P. */ 410 411static void 412merge_pred (struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p) 413{ 414 end_list->pred_left = *last_p; 415 *last_p = beg_list; 416} 417 418/* Find the first node in expression tree TREE that requires 419 a stat call and mark the operator above it as needing a stat 420 before calling the node. Since the expression precedences 421 are represented in the tree, some preds that need stat may not 422 get executed (because the expression value is determined earlier.) 423 So every expression needing stat must be marked as such, not just 424 the earliest, to be sure to obtain the stat. This still guarantees 425 that a stat is made as late as possible. Return true if the top node 426 in TREE requires a stat, false if not. */ 427 428boolean 429mark_stat (struct predicate *tree) 430{ 431 /* The tree is executed in-order, so walk this way (apologies to Aerosmith) 432 to find the first predicate for which the stat is needed. */ 433 switch (tree->p_type) 434 { 435 case NO_TYPE: 436 case PRIMARY_TYPE: 437 return tree->need_stat; 438 439 case UNI_OP: 440 if (mark_stat (tree->pred_right)) 441 tree->need_stat = true; 442 return (false); 443 444 case BI_OP: 445 /* ANDs and ORs are linked along ->left ending in NULL. */ 446 if (tree->pred_left != NULL) 447 mark_stat (tree->pred_left); 448 449 if (mark_stat (tree->pred_right)) 450 tree->need_stat = true; 451 452 return (false); 453 454 default: 455 error (1, 0, _("oops -- invalid expression type in mark_stat!")); 456 return (false); 457 } 458} 459 460/* Find the first node in expression tree TREE that we will 461 need to know the file type, if any. Operates in the same 462 was as mark_stat(). 463*/ 464boolean 465mark_type (struct predicate *tree) 466{ 467 /* The tree is executed in-order, so walk this way (apologies to Aerosmith) 468 to find the first predicate for which the type information is needed. */ 469 switch (tree->p_type) 470 { 471 case NO_TYPE: 472 case PRIMARY_TYPE: 473 return tree->need_type; 474 475 case UNI_OP: 476 if (mark_type (tree->pred_right)) 477 tree->need_type = true; 478 return false; 479 480 case BI_OP: 481 /* ANDs and ORs are linked along ->left ending in NULL. */ 482 if (tree->pred_left != NULL) 483 mark_type (tree->pred_left); 484 485 if (mark_type (tree->pred_right)) 486 tree->need_type = true; 487 488 return false; 489 490 default: 491 error (1, 0, _("oops -- invalid expression type in mark_type!")); 492 return (false); 493 } 494} 495 496