find/tree.c

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