find/tree.c

   1 /* tree.c -- helper functions to build and evaluate the expression tree.
   2    Copyright (C) 1990, 91, 92, 93, 94 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., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 #include <config.h>
  19 #include <sys/types.h>
  20 #include <sys/stat.h>
  21 #include <stdio.h>
  22 #include "defs.h"
  23
  24 #if ENABLE_NLS
  25 # include <libintl.h>
  26 # define _(Text) gettext (Text)
  27 #else
  28 # define _(Text) Text
  29 #endif
  30 #ifdef gettext_noop
  31 # define N_(String) gettext_noop (String)
  32 #else
  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;
  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    * 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.
 179
 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.
 184
 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. */
 188
 189 boolean
 190 opt_expr (struct predicate **eval_treep)
 191 {
 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. */
 201   PFB pred_func;
 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 */
 206
 207
 208   if (eval_treep == NULL || *eval_treep == NULL)
 209     return (false);
 210
 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. */
 214   prevp = eval_treep;
 215   prev_prec = AND_PREC;
 216   curr = *prevp;
 217   while (curr->pred_left != NULL)
 218     {
 219       prevp = &curr->pred_left;
 220       prev_prec = curr->p_prec; /* must be a BI_OP */
 221       curr = curr->pred_left;
 222     }
 223
 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);
 227
 228 #ifdef DEBUG
 229   /* Normalized tree. */
 230   printf (_("Normalized Eval Tree:\n"));
 231   print_tree (*eval_treep, 0);
 232 #endif
 233
 234   /* Rearrange the predicates. */
 235   prevp = eval_treep;
 236   if ((*prevp) && (*prevp)->p_type == BI_OP)
 237     biop_prec = (*prevp)->p_prec;
 238   while ((curr = *prevp) != NULL)
 239     {
 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)
 247         {
 248           if (curr->p_prec != biop_prec)
 249             curr = set_new_parent(curr, biop_prec, prevp);
 250         }
 251
 252       /* See which predicate type we have. */
 253       p_type = curr->pred_right->p_type;
 254       pred_func = curr->pred_right->pred_func;
 255
 256       switch (p_type)
 257         {
 258         case NO_TYPE:
 259         case PRIMARY_TYPE:
 260           /* Don't rearrange the arguments of the comma operator, it is
 261              not commutative.  */
 262           if (biop_prec == COMMA_PREC)
 263             break;
 264
 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)
 268             {
 269               *prevp = curr->pred_left;
 270               curr->pred_left = name_list;
 271               name_list = curr;
 272
 273               if (end_name_list == NULL)
 274                 end_name_list = curr;
 275
 276               continue;
 277             }
 278
 279           if (pred_func == pred_regex)
 280             {
 281               *prevp = curr->pred_left;
 282               curr->pred_left = regex_list;
 283               regex_list = curr;
 284
 285               if (end_regex_list == NULL)
 286                 end_regex_list = curr;
 287
 288               continue;
 289             }
 290
 291           break;
 292
 293         case UNI_OP:
 294           /* For NOT, check the expression trees below the NOT. */
 295           curr->pred_right->side_effects
 296             = opt_expr (&curr->pred_right->pred_right);
 297           break;
 298
 299         case BI_OP:
 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);
 303           break;
 304
 305           /* At this point, get_expr and scan_rest have already removed
 306              all of the user's parentheses. */
 307
 308         default:
 309           error (1, 0, _("oops -- invalid expression type!"));
 310           break;
 311         }
 312
 313       if (curr->pred_right->side_effects == true)
 314         {
 315           last_sidep = prevp;
 316
 317           /* Incorporate lists and reset list pointers for this group.  */
 318           if (name_list != NULL)
 319             {
 320               merge_pred (name_list, end_name_list, last_sidep);
 321               name_list = end_name_list = NULL;
 322             }
 323
 324           if (regex_list != NULL)
 325             {
 326               merge_pred (regex_list, end_regex_list, last_sidep);
 327               regex_list = end_regex_list = NULL;
 328             }
 329
 330           has_side_effects = true;
 331         }
 332
 333       prevp = &curr->pred_left;
 334     }
 335
 336   /* Do final list merges. */
 337   last_sidep = prevp;
 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);
 342
 343   return (has_side_effects);
 344 }
 345
 346 /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
 347    HIGH_PREC. */
 348
 349 static struct predicate *
 350 set_new_parent (struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp)
 351 {
 352   struct predicate *new_parent;
 353
 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;
 358
 359   switch (high_prec)
 360     {
 361     case COMMA_PREC:
 362       new_parent->pred_func = pred_comma;
 363       break;
 364     case OR_PREC:
 365       new_parent->pred_func = pred_or;
 366       break;
 367     case AND_PREC:
 368       new_parent->pred_func = pred_and;
 369       break;
 370     default:
 371       ;                         /* empty */
 372     }
 373
 374   new_parent->side_effects = false;
 375   new_parent->args.str = NULL;
 376   new_parent->pred_next = NULL;
 377
 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;
 382   *prevp = new_parent;
 383
 384 #ifdef  DEBUG
 385   new_parent->p_name = (char *) find_pred_name (new_parent->pred_func);
 386 #endif /* DEBUG */
 387
 388   return (new_parent);
 389 }
 390
 391 /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
 392    into the tree at LAST_P. */
 393
 394 static void
 395 merge_pred (struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p)
 396 {
 397   end_list->pred_left = *last_p;
 398   *last_p = beg_list;
 399 }
 400 \f
 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. */
 410
 411 boolean
 412 mark_stat (struct predicate *tree)
 413 {
 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)
 417     {
 418     case NO_TYPE:
 419     case PRIMARY_TYPE:
 420       return tree->need_stat;
 421
 422     case UNI_OP:
 423       if (mark_stat (tree->pred_right))
 424         tree->need_stat = true;
 425       return (false);
 426
 427     case BI_OP:
 428       /* ANDs and ORs are linked along ->left ending in NULL. */
 429       if (tree->pred_left != NULL)
 430         mark_stat (tree->pred_left);
 431
 432       if (mark_stat (tree->pred_right))
 433         tree->need_stat = true;
 434
 435       return (false);
 436
 437     default:
 438       error (1, 0, _("oops -- invalid expression type!"));
 439       return (false);
 440     }
 441 }