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