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