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
 173    * Place -name, -iname, -path, -ipath, -regex and -iregex at the front
 174      of a group, with -name, -iname, -path and -ipath ahead of
 175      -regex and -iregex.  Predicates which are moved to the front
 176      of a group by definition do not have side effects.  Both
 177      -regex and -iregex both use pred_regex.
 178
 179      This routine "normalizes" the predicate tree by ensuring that
 180      all expression predicates have AND (or OR or COMMA) parent nodes
 181      which are linked along the left edge of the expression tree.
 182      This makes manipulation of subtrees easier.
 183
 184      EVAL_TREEP points to the root pointer of the predicate tree
 185      to be rearranged.  opt_expr may return a new root pointer there.
 186      Return true if the tree contains side effects, false if not. */
 187
 188 boolean
 189 opt_expr (struct predicate **eval_treep)
 190 {
 191   /* List of -name and -path predicates to move. */
 192   struct predicate *name_list = NULL;
 193   struct predicate *end_name_list = NULL;
 194   /* List of -regex predicates to move. */
 195   struct predicate *regex_list = NULL;
 196   struct predicate *end_regex_list = NULL;
 197   struct predicate *curr;
 198   struct predicate **prevp;     /* Address of `curr' node. */
 199   struct predicate **last_sidep; /* Last predicate with side effects. */
 200   PFB pred_func;
 201   enum predicate_type p_type;
 202   boolean has_side_effects = false; /* Return value. */
 203   enum predicate_precedence prev_prec, /* precedence of last BI_OP in branch */
 204                             biop_prec; /* topmost BI_OP precedence in branch */
 205
 206
 207   if (eval_treep == NULL || *eval_treep == NULL)
 208     return (false);
 209
 210   /* Set up to normalize tree as a left-linked list of ANDs or ORs.
 211      Set `curr' to the leftmost node, `prevp' to its address, and
 212      `pred_func' to the predicate type of its parent. */
 213   prevp = eval_treep;
 214   prev_prec = AND_PREC;
 215   curr = *prevp;
 216   while (curr->pred_left != NULL)
 217     {
 218       prevp = &curr->pred_left;
 219       prev_prec = curr->p_prec; /* must be a BI_OP */
 220       curr = curr->pred_left;
 221     }
 222
 223   /* Link in the appropriate BI_OP for the last expression, if needed. */
 224   if (curr->p_type != BI_OP)
 225     set_new_parent (curr, prev_prec, prevp);
 226
 227 #ifdef DEBUG
 228   /* Normalized tree. */
 229   printf (_("Normalized Eval Tree:\n"));
 230   print_tree (*eval_treep, 0);
 231 #endif
 232
 233   /* Rearrange the predicates. */
 234   prevp = eval_treep;
 235   if ((*prevp) && (*prevp)->p_type == BI_OP)
 236     biop_prec = (*prevp)->p_prec;
 237   while ((curr = *prevp) != NULL)
 238     {
 239       /* If there is a BI_OP of different precedence from the first
 240          in the pred_left chain, create a new parent of the
 241          original precedence, link the new parent to the left of the
 242          previous and link CURR to the right of the new parent.
 243          This preserves the precedence of expressions in the tree
 244          in case we rearrange them. */
 245       if (curr->p_type == BI_OP)
 246         {
 247           if (curr->p_prec != biop_prec)
 248             curr = set_new_parent(curr, biop_prec, prevp);
 249         }
 250
 251       /* See which predicate type we have. */
 252       p_type = curr->pred_right->p_type;
 253       pred_func = curr->pred_right->pred_func;
 254
 255       switch (p_type)
 256         {
 257         case NO_TYPE:
 258         case PRIMARY_TYPE:
 259           /* Don't rearrange the arguments of the comma operator, it is
 260              not commutative.  */
 261           if (biop_prec == COMMA_PREC)
 262             break;
 263
 264           /* If it's one of our special primaries, move it to the
 265              front of the list for that primary. */
 266           if (pred_func == pred_name || pred_func == pred_path ||
 267               pred_func == pred_iname || pred_func == pred_ipath)
 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 }