find/tree.c

   1 /* tree.c -- helper functions to build and evaluate the expression tree.
   2    Copyright (C) 1990, 91, 92, 93, 94, 2000, 2003, 2004 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  17    USA.
  18 */
  19
  20 #include "defs.h"
  21 #include "../gnulib/lib/xalloc.h"
  22
  23 #if ENABLE_NLS
  24 # include <libintl.h>
  25 # define _(Text) gettext (Text)
  26 #else
  27 # define _(Text) Text
  28 #endif
  29 #ifdef gettext_noop
  30 # define N_(String) gettext_noop (String)
  31 #else
  32 /* See locate.c for explanation as to why not use (String) */
  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,
  63           short int prev_prec,
  64           const struct predicate* prev_pred)
  65 {
  66   struct predicate *next = NULL;
  67
  68   if (*input == NULL)
  69     error (1, 0, _("invalid expression"));
  70
  71   switch ((*input)->p_type)
  72     {
  73     case NO_TYPE:
  74       error (1, 0, _("invalid expression"));
  75       break;
  76
  77     case BI_OP:
  78       error (1, 0, _("invalid expression; you have used a binary operator with nothing before it."));
  79       break;
  80
  81     case CLOSE_PAREN:
  82       if ( (*input)->artificial )
  83         {
  84           /* We have reached the end of the user-supplied predicates
  85            * unexpectedly.
  86            */
  87           error (1, 0, _("expected an expression after '%s'"), prev_pred->p_name);
  88         }
  89       else
  90         {
  91           error (1, 0, _("invalid expression; you have too many ')'"));
  92         }
  93       break;
  94
  95     case PRIMARY_TYPE:
  96       next = *input;
  97       *input = (*input)->pred_next;
  98       break;
  99
 100     case UNI_OP:
 101       next = *input;
 102       *input = (*input)->pred_next;
 103       next->pred_right = get_expr (input, NEGATE_PREC, next);
 104       break;
 105
 106     case OPEN_PAREN:
 107       prev_pred = (*input);
 108       *input = (*input)->pred_next;
 109       if ( (*input)->p_type == CLOSE_PAREN )
 110         {
 111           error (1, 0, _("invalid expression; empty parentheses are not allowed."));
 112         }
 113       next = get_expr (input, NO_PREC, prev_pred);
 114       if ((*input == NULL)
 115           || ((*input)->p_type != CLOSE_PAREN))
 116         error (1, 0, _("invalid expression; I was expecting to find a ')' somewhere but did not see one."));
 117       *input = (*input)->pred_next;     /* move over close */
 118       break;
 119
 120     default:
 121       error (1, 0, _("oops -- invalid expression type!"));
 122       break;
 123     }
 124
 125   /* We now have the first expression and are positioned to check
 126      out the next operator.  If NULL, all done.  Otherwise, if
 127      PREV_PREC < the current node precedence, we must continue;
 128      the expression we just nabbed is more tightly bound to the
 129      following expression than to the previous one. */
 130   if (*input == NULL)
 131     return (next);
 132   if ((int) (*input)->p_prec > (int) prev_prec)
 133     {
 134       next = scan_rest (input, next, prev_prec);
 135       if (next == NULL)
 136         error (1, 0, _("invalid expression"));
 137     }
 138   return (next);
 139 }
 140 \f
 141 /* Scan across the remainder of a predicate input list starting
 142    at *INPUT, building the rest of the expression tree to return.
 143    Stop at the first close parenthesis or the end of the input list.
 144    Assumes that get_expr has been called to nab the first element
 145    of the expression tree.
 146
 147    *INPUT points to the current input predicate list element.
 148    It is updated as we move along the list to point to the
 149    terminating input element.
 150    HEAD points to the predicate element that was obtained
 151    by the call to get_expr.
 152    PREV_PREC is the precedence of the previous predicate element. */
 153
 154 static struct predicate *
 155 scan_rest (struct predicate **input,
 156            struct predicate *head,
 157            short int prev_prec)
 158 {
 159   struct predicate *tree;       /* The new tree we are building. */
 160
 161   if ((*input == NULL) || ((*input)->p_type == CLOSE_PAREN))
 162     return (NULL);
 163   tree = head;
 164   while ((*input != NULL) && ((int) (*input)->p_prec > (int) prev_prec))
 165     {
 166       switch ((*input)->p_type)
 167         {
 168         case NO_TYPE:
 169         case PRIMARY_TYPE:
 170         case UNI_OP:
 171         case OPEN_PAREN:
 172           /* I'm not sure how we get here, so it is not obvious what
 173            * sort of mistakes might give rise to this condition.
 174            */
 175           error (1, 0, _("invalid expression"));
 176           break;
 177
 178         case BI_OP:
 179           {
 180             struct predicate *prev = (*input);
 181             (*input)->pred_left = tree;
 182             tree = *input;
 183             *input = (*input)->pred_next;
 184             tree->pred_right = get_expr (input, tree->p_prec, prev);
 185             break;
 186           }
 187
 188         case CLOSE_PAREN:
 189           return tree;
 190
 191         default:
 192           error (1, 0,
 193                  _("oops -- invalid expression type (%d)!"),
 194                  (int)(*input)->p_type);
 195           break;
 196         }
 197     }
 198   return tree;
 199 }
 200 \f
 201 /* Optimize the ordering of the predicates in the tree.  Rearrange
 202    them to minimize work.  Strategies:
 203    * Evaluate predicates that don't need inode information first;
 204      the predicates are divided into 1 or more groups separated by
 205      predicates (if any) which have "side effects", such as printing.
 206      The grouping implements the partial ordering on predicates which
 207      those with side effects impose.
 208
 209    * Place -name, -iname, -path, -ipath, -regex and -iregex at the front
 210      of a group, with -name, -iname, -path and -ipath ahead of
 211      -regex and -iregex.  Predicates which are moved to the front
 212      of a group by definition do not have side effects.  Both
 213      -regex and -iregex both use pred_regex.
 214
 215      This routine "normalizes" the predicate tree by ensuring that
 216      all expression predicates have AND (or OR or COMMA) parent nodes
 217      which are linked along the left edge of the expression tree.
 218      This makes manipulation of subtrees easier.
 219
 220      EVAL_TREEP points to the root pointer of the predicate tree
 221      to be rearranged.  opt_expr may return a new root pointer there.
 222      Return true if the tree contains side effects, false if not. */
 223
 224 boolean
 225 opt_expr (struct predicate **eval_treep)
 226 {
 227   /* List of -name and -path predicates to move. */
 228   struct predicate *name_list = NULL;
 229   struct predicate *end_name_list = NULL;
 230   /* List of -regex predicates to move. */
 231   struct predicate *regex_list = NULL;
 232   struct predicate *end_regex_list = NULL;
 233   struct predicate *curr;
 234   struct predicate **prevp;     /* Address of `curr' node. */
 235   struct predicate **last_sidep; /* Last predicate with side effects. */
 236   PRED_FUNC pred_func;
 237   enum predicate_type p_type;
 238   boolean has_side_effects = false; /* Return value. */
 239   enum predicate_precedence prev_prec, /* precedence of last BI_OP in branch */
 240                             biop_prec; /* topmost BI_OP precedence in branch */
 241
 242
 243   if (eval_treep == NULL || *eval_treep == NULL)
 244     return (false);
 245
 246   /* Set up to normalize tree as a left-linked list of ANDs or ORs.
 247      Set `curr' to the leftmost node, `prevp' to its address, and
 248      `pred_func' to the predicate type of its parent. */
 249   prevp = eval_treep;
 250   prev_prec = AND_PREC;
 251   curr = *prevp;
 252   while (curr->pred_left != NULL)
 253     {
 254       prevp = &curr->pred_left;
 255       prev_prec = curr->p_prec; /* must be a BI_OP */
 256       curr = curr->pred_left;
 257     }
 258
 259   /* Link in the appropriate BI_OP for the last expression, if needed. */
 260   if (curr->p_type != BI_OP)
 261     set_new_parent (curr, prev_prec, prevp);
 262
 263 #ifdef DEBUG
 264   /* Normalized tree. */
 265   fprintf (stderr, "Normalized Eval Tree:\n");
 266   print_tree (stderr, *eval_treep, 0);
 267 #endif
 268
 269   /* Rearrange the predicates. */
 270   prevp = eval_treep;
 271   biop_prec = NO_PREC; /* not COMMA_PREC */
 272   if ((*prevp) && (*prevp)->p_type == BI_OP)
 273     biop_prec = (*prevp)->p_prec;
 274   while ((curr = *prevp) != NULL)
 275     {
 276       /* If there is a BI_OP of different precedence from the first
 277          in the pred_left chain, create a new parent of the
 278          original precedence, link the new parent to the left of the
 279          previous and link CURR to the right of the new parent.
 280          This preserves the precedence of expressions in the tree
 281          in case we rearrange them. */
 282       if (curr->p_type == BI_OP)
 283         {
 284           if (curr->p_prec != biop_prec)
 285             curr = set_new_parent(curr, biop_prec, prevp);
 286         }
 287
 288       /* See which predicate type we have. */
 289       p_type = curr->pred_right->p_type;
 290       pred_func = curr->pred_right->pred_func;
 291
 292       switch (p_type)
 293         {
 294         case NO_TYPE:
 295         case PRIMARY_TYPE:
 296           /* Don't rearrange the arguments of the comma operator, it is
 297              not commutative.  */
 298           if (biop_prec == COMMA_PREC)
 299             break;
 300
 301           /* If it's one of our special primaries, move it to the
 302              front of the list for that primary. */
 303           if (pred_func == pred_name || pred_func == pred_path ||
 304               pred_func == pred_iname || pred_func == pred_ipath)
 305             {
 306               *prevp = curr->pred_left;
 307               curr->pred_left = name_list;
 308               name_list = curr;
 309
 310               if (end_name_list == NULL)
 311                 end_name_list = curr;
 312
 313               continue;
 314             }
 315
 316           if (pred_func == pred_regex)
 317             {
 318               *prevp = curr->pred_left;
 319               curr->pred_left = regex_list;
 320               regex_list = curr;
 321
 322               if (end_regex_list == NULL)
 323                 end_regex_list = curr;
 324
 325               continue;
 326             }
 327
 328           break;
 329
 330         case UNI_OP:
 331           /* For NOT, check the expression trees below the NOT. */
 332           curr->pred_right->side_effects
 333             = opt_expr (&curr->pred_right->pred_right);
 334           break;
 335
 336         case BI_OP:
 337           /* For nested AND or OR, recurse (AND/OR form layers on the left of
 338              the tree), and continue scanning this level of AND or OR. */
 339           curr->pred_right->side_effects = opt_expr (&curr->pred_right);
 340           break;
 341
 342           /* At this point, get_expr and scan_rest have already removed
 343              all of the user's parentheses. */
 344
 345         default:
 346           error (1, 0, _("oops -- invalid expression type!"));
 347           break;
 348         }
 349
 350       if (curr->pred_right->side_effects == true)
 351         {
 352           last_sidep = prevp;
 353
 354           /* Incorporate lists and reset list pointers for this group.  */
 355           if (name_list != NULL)
 356             {
 357               merge_pred (name_list, end_name_list, last_sidep);
 358               name_list = end_name_list = NULL;
 359             }
 360
 361           if (regex_list != NULL)
 362             {
 363               merge_pred (regex_list, end_regex_list, last_sidep);
 364               regex_list = end_regex_list = NULL;
 365             }
 366
 367           has_side_effects = true;
 368         }
 369
 370       prevp = &curr->pred_left;
 371     }
 372
 373   /* Do final list merges. */
 374   last_sidep = prevp;
 375   if (name_list != NULL)
 376     merge_pred (name_list, end_name_list, last_sidep);
 377   if (regex_list != NULL)
 378     merge_pred (regex_list, end_regex_list, last_sidep);
 379
 380   return (has_side_effects);
 381 }
 382
 383 /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
 384    HIGH_PREC. */
 385
 386 static struct predicate *
 387 set_new_parent (struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp)
 388 {
 389   struct predicate *new_parent;
 390
 391   new_parent = (struct predicate *) xmalloc (sizeof (struct predicate));
 392   new_parent->p_type = BI_OP;
 393   new_parent->p_prec = high_prec;
 394   new_parent->need_stat = false;
 395   new_parent->need_type = false;
 396
 397   switch (high_prec)
 398     {
 399     case COMMA_PREC:
 400       new_parent->pred_func = pred_comma;
 401       break;
 402     case OR_PREC:
 403       new_parent->pred_func = pred_or;
 404       break;
 405     case AND_PREC:
 406       new_parent->pred_func = pred_and;
 407       break;
 408     default:
 409       ;                         /* empty */
 410     }
 411
 412   new_parent->side_effects = false;
 413   new_parent->no_default_print = false;
 414   new_parent->args.str = NULL;
 415   new_parent->pred_next = NULL;
 416
 417   /* Link in new_parent.
 418      Pushes rest of left branch down 1 level to new_parent->pred_right. */
 419   new_parent->pred_left = NULL;
 420   new_parent->pred_right = curr;
 421   *prevp = new_parent;
 422
 423 #ifdef  DEBUG
 424   new_parent->p_name = (char *) find_pred_name (new_parent->pred_func);
 425 #endif /* DEBUG */
 426
 427   return (new_parent);
 428 }
 429
 430 /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
 431    into the tree at LAST_P. */
 432
 433 static void
 434 merge_pred (struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p)
 435 {
 436   end_list->pred_left = *last_p;
 437   *last_p = beg_list;
 438 }
 439 \f
 440 /* Find the first node in expression tree TREE that requires
 441    a stat call and mark the operator above it as needing a stat
 442    before calling the node.   Since the expression precedences
 443    are represented in the tree, some preds that need stat may not
 444    get executed (because the expression value is determined earlier.)
 445    So every expression needing stat must be marked as such, not just
 446    the earliest, to be sure to obtain the stat.  This still guarantees
 447    that a stat is made as late as possible.  Return true if the top node
 448    in TREE requires a stat, false if not. */
 449
 450 boolean
 451 mark_stat (struct predicate *tree)
 452 {
 453   /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
 454      to find the first predicate for which the stat is needed. */
 455   switch (tree->p_type)
 456     {
 457     case NO_TYPE:
 458     case PRIMARY_TYPE:
 459       return tree->need_stat;
 460
 461     case UNI_OP:
 462       if (mark_stat (tree->pred_right))
 463         tree->need_stat = true;
 464       return (false);
 465
 466     case BI_OP:
 467       /* ANDs and ORs are linked along ->left ending in NULL. */
 468       if (tree->pred_left != NULL)
 469         mark_stat (tree->pred_left);
 470
 471       if (mark_stat (tree->pred_right))
 472         tree->need_stat = true;
 473
 474       return (false);
 475
 476     default:
 477       error (1, 0, _("oops -- invalid expression type in mark_stat!"));
 478       return (false);
 479     }
 480 }
 481 \f
 482 /* Find the first node in expression tree TREE that we will
 483    need to know the file type, if any.   Operates in the same
 484    was as mark_stat().
 485 */
 486 boolean
 487 mark_type (struct predicate *tree)
 488 {
 489   /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
 490      to find the first predicate for which the type information is needed. */
 491   switch (tree->p_type)
 492     {
 493     case NO_TYPE:
 494     case PRIMARY_TYPE:
 495       return tree->need_type;
 496
 497     case UNI_OP:
 498       if (mark_type (tree->pred_right))
 499         tree->need_type = true;
 500       return false;
 501
 502     case BI_OP:
 503       /* ANDs and ORs are linked along ->left ending in NULL. */
 504       if (tree->pred_left != NULL)
 505         mark_type (tree->pred_left);
 506
 507       if (mark_type (tree->pred_right))
 508         tree->need_type = true;
 509
 510       return false;
 511
 512     default:
 513       error (1, 0, _("oops -- invalid expression type in mark_type!"));
 514       return (false);
 515     }
 516 }
 517