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