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., 9 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 # define N_(String) (String)
  32 #endif
  33
  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));
  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
  59 struct predicate *
  60 get_expr (struct predicate **input, short int prev_prec)
  61 {
  62   struct predicate *next;
  63
  64   if (*input == NULL)
  65     error (1, 0, _("invalid expression"));
  66   switch ((*input)->p_type)
  67     {
  68     case NO_TYPE:
  69     case BI_OP:
  70     case CLOSE_PAREN:
  71       error (1, 0, _("invalid expression"));
  72       break;
  73
  74     case PRIMARY_TYPE:
  75       next = *input;
  76       *input = (*input)->pred_next;
  77       break;
  78
  79     case UNI_OP:
  80       next = *input;
  81       *input = (*input)->pred_next;
  82       next->pred_right = get_expr (input, NEGATE_PREC);
  83       break;
  84
  85     case OPEN_PAREN:
  86       *input = (*input)->pred_next;
  87       next = get_expr (input, NO_PREC);
  88       if ((*input == NULL)
  89           || ((*input)->p_type != CLOSE_PAREN))
  90         error (1, 0, _("invalid expression"));
  91       *input = (*input)->pred_next;     /* move over close */
  92       break;
  93
  94     default:
  95       error (1, 0, _("oops -- invalid expression type!"));
  96       break;
  97     }
  98
  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. */
 104   if (*input == NULL)
 105     return (next);
 106   if ((int) (*input)->p_prec > (int) prev_prec)
 107     {
 108       next = scan_rest (input, next, prev_prec);
 109       if (next == NULL)
 110         error (1, 0, _("invalid expression"));
 111     }
 112   return (next);
 113 }
 114 \f
 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.
 120
 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. */
 127
 128 static struct predicate *
 129 scan_rest (struct predicate **input,
 130            struct predicate *head,
 131            short int prev_prec)
 132 {
 133   struct predicate *tree;       /* The new tree we are building. */
 134
 135   if ((*input == NULL) || ((*input)->p_type == CLOSE_PAREN))
 136     return (NULL);
 137   tree = head;
 138   while ((*input != NULL) && ((int) (*input)->p_prec > (int) prev_prec))
 139     {
 140       switch ((*input)->p_type)
 141         {
 142         case NO_TYPE:
 143         case PRIMARY_TYPE:
 144         case UNI_OP:
 145         case OPEN_PAREN:
 146           error (1, 0, _("invalid expression"));
 147           break;
 148
 149         case BI_OP:
 150           (*input)->pred_left = tree;
 151           tree = *input;
 152           *input = (*input)->pred_next;
 153           tree->pred_right = get_expr (input, tree->p_prec);
 154           break;
 155
 156         case CLOSE_PAREN:
 157           return (tree);
 158
 159         default:
 160           error (1, 0, _("oops -- invalid expression type!"));
 161           break;
 162         }
 163     }
 164   return (tree);
 165 }
 166 \f
 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.
 174
 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.
 180
 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.
 185
 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. */
 189
 190 boolean
 191 opt_expr (struct predicate **eval_treep)
 192 {
 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. */
 202   PFB pred_func;
 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 */
 207
 208
 209   if (eval_treep == NULL || *eval_treep == NULL)
 210     return (false);
 211
 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. */
 215   prevp = eval_treep;
 216   prev_prec = AND_PREC;
 217   curr = *prevp;
 218   while (curr->pred_left != NULL)
 219     {
 220       prevp = &curr->pred_left;
 221       prev_prec = curr->p_prec; /* must be a BI_OP */
 222       curr = curr->pred_left;
 223     }
 224
 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);
 228
 229 #ifdef DEBUG
 230   /* Normalized tree. */
 231   printf (_("Normalized Eval Tree:\n"));
 232   print_tree (*eval_treep, 0);
 233 #endif
 234
 235   /* Rearrange the predicates. */
 236   prevp = eval_treep;
 237   if ((*prevp) && (*prevp)->p_type == BI_OP)
 238     biop_prec = (*prevp)->p_prec;
 239   while ((curr = *prevp) != NULL)
 240     {
 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)
 248         {
 249           if (curr->p_prec != biop_prec)
 250             curr = set_new_parent(curr, biop_prec, prevp);
 251         }
 252
 253       /* See which predicate type we have. */
 254       p_type = curr->pred_right->p_type;
 255       pred_func = curr->pred_right->pred_func;
 256
 257       switch (p_type)
 258         {
 259         case NO_TYPE:
 260         case PRIMARY_TYPE:
 261           /* Don't rearrange the arguments of the comma operator, it is
 262              not commutative.  */
 263           if (biop_prec == COMMA_PREC)
 264             break;
 265
 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)
 270             {
 271               *prevp = curr->pred_left;
 272               curr->pred_left = name_list;
 273               name_list = curr;
 274
 275               if (end_name_list == NULL)
 276                 end_name_list = curr;
 277
 278               continue;
 279             }
 280
 281           if (pred_func == pred_regex)
 282             {
 283               *prevp = curr->pred_left;
 284               curr->pred_left = regex_list;
 285               regex_list = curr;
 286
 287               if (end_regex_list == NULL)
 288                 end_regex_list = curr;
 289
 290               continue;
 291             }
 292
 293           break;
 294
 295         case UNI_OP:
 296           /* For NOT, check the expression trees below the NOT. */
 297           curr->pred_right->side_effects
 298             = opt_expr (&curr->pred_right->pred_right);
 299           break;
 300
 301         case BI_OP:
 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);
 305           break;
 306
 307           /* At this point, get_expr and scan_rest have already removed
 308              all of the user's parentheses. */
 309
 310         default:
 311           error (1, 0, _("oops -- invalid expression type!"));
 312           break;
 313         }
 314
 315       if (curr->pred_right->side_effects == true)
 316         {
 317           last_sidep = prevp;
 318
 319           /* Incorporate lists and reset list pointers for this group.  */
 320           if (name_list != NULL)
 321             {
 322               merge_pred (name_list, end_name_list, last_sidep);
 323               name_list = end_name_list = NULL;
 324             }
 325
 326           if (regex_list != NULL)
 327             {
 328               merge_pred (regex_list, end_regex_list, last_sidep);
 329               regex_list = end_regex_list = NULL;
 330             }
 331
 332           has_side_effects = true;
 333         }
 334
 335       prevp = &curr->pred_left;
 336     }
 337
 338   /* Do final list merges. */
 339   last_sidep = prevp;
 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);
 344
 345   return (has_side_effects);
 346 }
 347
 348 /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
 349    HIGH_PREC. */
 350
 351 static struct predicate *
 352 set_new_parent (struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp)
 353 {
 354   struct predicate *new_parent;
 355
 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;
 360
 361   switch (high_prec)
 362     {
 363     case COMMA_PREC:
 364       new_parent->pred_func = pred_comma;
 365       break;
 366     case OR_PREC:
 367       new_parent->pred_func = pred_or;
 368       break;
 369     case AND_PREC:
 370       new_parent->pred_func = pred_and;
 371       break;
 372     default:
 373       ;                         /* empty */
 374     }
 375
 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;
 380
 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;
 385   *prevp = new_parent;
 386
 387 #ifdef  DEBUG
 388   new_parent->p_name = (char *) find_pred_name (new_parent->pred_func);
 389 #endif /* DEBUG */
 390
 391   return (new_parent);
 392 }
 393
 394 /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
 395    into the tree at LAST_P. */
 396
 397 static void
 398 merge_pred (struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p)
 399 {
 400   end_list->pred_left = *last_p;
 401   *last_p = beg_list;
 402 }
 403 \f
 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. */
 413
 414 boolean
 415 mark_stat (struct predicate *tree)
 416 {
 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)
 420     {
 421     case NO_TYPE:
 422     case PRIMARY_TYPE:
 423       return tree->need_stat;
 424
 425     case UNI_OP:
 426       if (mark_stat (tree->pred_right))
 427         tree->need_stat = true;
 428       return (false);
 429
 430     case BI_OP:
 431       /* ANDs and ORs are linked along ->left ending in NULL. */
 432       if (tree->pred_left != NULL)
 433         mark_stat (tree->pred_left);
 434
 435       if (mark_stat (tree->pred_right))
 436         tree->need_stat = true;
 437
 438       return (false);
 439
 440     default:
 441       error (1, 0, _("oops -- invalid expression type!"));
 442       return (false);
 443     }
 444 }