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, 2005 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 #include <assert.h>
  24 #include <stdlib.h>
  25
  26 #if ENABLE_NLS
  27 # include <libintl.h>
  28 # define _(Text) gettext (Text)
  29 #else
  30 # define _(Text) Text
  31 #endif
  32 #ifdef gettext_noop
  33 # define N_(String) gettext_noop (String)
  34 #else
  35 /* See locate.c for explanation as to why not use (String) */
  36 # define N_(String) String
  37 #endif
  38
  39
  40
  41 /* All predicates for each path to process. */
  42 static struct predicate *predicates = NULL;
  43
  44 /* The root of the evaluation tree. */
  45 static struct predicate *eval_tree  = NULL;
  46
  47 /* The last predicate allocated. */
  48 static struct predicate *last_pred = NULL;
  49
  50
  51 static struct predicate *scan_rest PARAMS((struct predicate **input,
  52                                        struct predicate *head,
  53                                        short int prev_prec));
  54 static void merge_pred PARAMS((struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p));
  55 static struct predicate *set_new_parent PARAMS((struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp));
  56 static const char *cost_name PARAMS((enum EvaluationCost cost));
  57
  58
  59 /* Return a pointer to a tree that represents the
  60    expression prior to non-unary operator *INPUT.
  61    Set *INPUT to point at the next input predicate node.
  62
  63    Only accepts the following:
  64
  65    <primary>
  66    expression           [operators of higher precedence]
  67    <uni_op><primary>
  68    (arbitrary expression)
  69    <uni_op>(arbitrary expression)
  70
  71    In other words, you can not start out with a bi_op or close_paren.
  72
  73    If the following operator (if any) is of a higher precedence than
  74    PREV_PREC, the expression just nabbed is part of a following
  75    expression, which really is the expression that should be handed to
  76    our caller, so get_expr recurses. */
  77
  78 struct predicate *
  79 get_expr (struct predicate **input,
  80           short int prev_prec,
  81           const struct predicate* prev_pred)
  82 {
  83   struct predicate *next = NULL;
  84   struct predicate *this_pred = (*input);
  85
  86   if (*input == NULL)
  87     error (1, 0, _("invalid expression"));
  88
  89   switch ((*input)->p_type)
  90     {
  91     case NO_TYPE:
  92       error (1, 0, _("invalid expression"));
  93       break;
  94
  95     case BI_OP:
  96       /* e.g. "find . -a" */
  97       error (1, 0, _("invalid expression; you have used a binary operator '%s' with nothing before it."), this_pred->p_name);
  98       break;
  99
 100     case CLOSE_PAREN:
 101       if ((UNI_OP == prev_pred->p_type
 102           || BI_OP == prev_pred->p_type)
 103           && !this_pred->artificial)
 104         {
 105           /* e.g. "find \( -not \)" or "find \( -true -a \" */
 106           error(1, 0, _("expected an expression between '%s' and ')'"),
 107                 prev_pred->p_name);
 108         }
 109       else if ( (*input)->artificial )
 110         {
 111           /* We have reached the end of the user-supplied predicates
 112            * unexpectedly.
 113            */
 114           /* e.g. "find . -true -a" */
 115           error (1, 0, _("expected an expression after '%s'"), prev_pred->p_name);
 116         }
 117       else
 118         {
 119           error (1, 0, _("invalid expression; you have too many ')'"));
 120         }
 121       break;
 122
 123     case PRIMARY_TYPE:
 124       next = *input;
 125       *input = (*input)->pred_next;
 126       break;
 127
 128     case UNI_OP:
 129       next = *input;
 130       *input = (*input)->pred_next;
 131       next->pred_right = get_expr (input, NEGATE_PREC, next);
 132       break;
 133
 134     case OPEN_PAREN:
 135       if ( (NULL == (*input)->pred_next) || (*input)->pred_next->artificial )
 136         {
 137           /* user typed something like "find . (", and so the ) we are
 138            * looking at is from the artificial "( ) -print" that we
 139            * add.
 140            */
 141           error (1, 0, _("invalid expression; expected to find a ')' but didn't see one.  Perhaps you need an extra predicate after '%s'"), this_pred->p_name);
 142         }
 143       prev_pred = (*input);
 144       *input = (*input)->pred_next;
 145       if ( (*input)->p_type == CLOSE_PAREN )
 146         {
 147           error (1, 0, _("invalid expression; empty parentheses are not allowed."));
 148         }
 149       next = get_expr (input, NO_PREC, prev_pred);
 150       if ((*input == NULL)
 151           || ((*input)->p_type != CLOSE_PAREN))
 152         error (1, 0, _("invalid expression; I was expecting to find a ')' somewhere but did not see one."));
 153       *input = (*input)->pred_next;     /* move over close */
 154       break;
 155
 156     default:
 157       error (1, 0, _("oops -- invalid expression type!"));
 158       break;
 159     }
 160
 161   /* We now have the first expression and are positioned to check
 162      out the next operator.  If NULL, all done.  Otherwise, if
 163      PREV_PREC < the current node precedence, we must continue;
 164      the expression we just nabbed is more tightly bound to the
 165      following expression than to the previous one. */
 166   if (*input == NULL)
 167     return (next);
 168   if ((int) (*input)->p_prec > (int) prev_prec)
 169     {
 170       next = scan_rest (input, next, prev_prec);
 171       if (next == NULL)
 172         error (1, 0, _("invalid expression"));
 173     }
 174   return (next);
 175 }
 176 \f
 177 /* Scan across the remainder of a predicate input list starting
 178    at *INPUT, building the rest of the expression tree to return.
 179    Stop at the first close parenthesis or the end of the input list.
 180    Assumes that get_expr has been called to nab the first element
 181    of the expression tree.
 182
 183    *INPUT points to the current input predicate list element.
 184    It is updated as we move along the list to point to the
 185    terminating input element.
 186    HEAD points to the predicate element that was obtained
 187    by the call to get_expr.
 188    PREV_PREC is the precedence of the previous predicate element. */
 189
 190 static struct predicate *
 191 scan_rest (struct predicate **input,
 192            struct predicate *head,
 193            short int prev_prec)
 194 {
 195   struct predicate *tree;       /* The new tree we are building. */
 196
 197   if ((*input == NULL) || ((*input)->p_type == CLOSE_PAREN))
 198     return (NULL);
 199   tree = head;
 200   while ((*input != NULL) && ((int) (*input)->p_prec > (int) prev_prec))
 201     {
 202       switch ((*input)->p_type)
 203         {
 204         case NO_TYPE:
 205         case PRIMARY_TYPE:
 206         case UNI_OP:
 207         case OPEN_PAREN:
 208           /* I'm not sure how we get here, so it is not obvious what
 209            * sort of mistakes might give rise to this condition.
 210            */
 211           error (1, 0, _("invalid expression"));
 212           break;
 213
 214         case BI_OP:
 215           {
 216             struct predicate *prev = (*input);
 217             (*input)->pred_left = tree;
 218             tree = *input;
 219             *input = (*input)->pred_next;
 220             tree->pred_right = get_expr (input, tree->p_prec, prev);
 221             break;
 222           }
 223
 224         case CLOSE_PAREN:
 225           return tree;
 226
 227         default:
 228           error (1, 0,
 229                  _("oops -- invalid expression type (%d)!"),
 230                  (int)(*input)->p_type);
 231           break;
 232         }
 233     }
 234   return tree;
 235 }
 236 \f
 237 /* Returns true if the specified predicate is reorderable. */
 238 static boolean
 239 predicate_is_cost_free(const struct predicate *p)
 240 {
 241   PRED_FUNC pred_func = p->pred_func;
 242
 243   if (pred_func == pred_name || pred_func == pred_path ||
 244       pred_func == pred_iname || pred_func == pred_ipath)
 245     {
 246       /* Traditionally (at least 4.1.7 through 4.2.x) GNU find always
 247        * optimised these cases.
 248        */
 249       return true;
 250     }
 251   else if (options.optimisation_level > 0)
 252     {
 253       if (pred_func == pred_and || pred_func == pred_negate ||
 254                pred_func == pred_comma || pred_func == pred_or)
 255         return false;
 256       else
 257         return NeedsNothing == p->p_cost;
 258     }
 259   else
 260     {
 261       return false;
 262     }
 263 }
 264 \f
 265 /* Prints a predicate */
 266 void print_predicate(FILE *fp, const struct predicate *p)
 267 {
 268   fprintf (fp, "%s%s%s",
 269            p->p_name,
 270            p->arg_text ? " " : "",
 271            p->arg_text ? p->arg_text : "");
 272 }
 273
 274 \f
 275 struct predlist
 276 {
 277   struct predicate *head;
 278   struct predicate *tail;
 279 };
 280 \f
 281 static void
 282 predlist_init(struct predlist *p)
 283 {
 284   p->head = p->tail = NULL;
 285 }
 286
 287 static void
 288 predlist_insert(struct predlist *list,
 289                 struct predicate *curr,
 290                 struct predicate **pprev)
 291 {
 292   struct predicate **insertpos = &(list->head);
 293
 294   *pprev = curr->pred_left;
 295   if (options.optimisation_level > 2)
 296     {
 297       /* Insert the new node in the list after any other entries which
 298        * are more selective.
 299        */
 300       if (0)
 301         while ( (*insertpos) && ((*insertpos)->est_success_rate < curr->est_success_rate) )
 302           {
 303             insertpos = &((*insertpos)->pred_left);
 304           }
 305     }
 306   curr->pred_left = (*insertpos);
 307   (*insertpos) = curr;
 308   if (NULL == list->tail)
 309     list->tail = list->head;
 310 }
 311 \f
 312 static void
 313 predlist_dump(FILE *fp, const char *label, const struct predlist *list)
 314 {
 315   const struct predicate *p;
 316   fprintf(fp, "%s:\n", label);
 317   for (p=list->head; p; p=p->pred_left)
 318     {
 319       print_optlist(fp, p);
 320       fprintf(fp, " ");
 321     }
 322   fprintf(fp, "\n");
 323 }
 324 \f
 325 static void
 326 predlist_merge_nosort(struct predlist *list,
 327                       struct predicate **last)
 328 {
 329   if (list->head)
 330     {
 331       calculate_derived_rates(list->head);
 332       merge_pred(list->head, list->tail, last);
 333       predlist_init(list);
 334     }
 335 }
 336 \f
 337 static int
 338 pred_cost_compare(const struct predicate *p1, const struct predicate *p2, boolean wantfailure)
 339 {
 340   if (p1->p_cost == p2->p_cost)
 341     {
 342       if (p1->est_success_rate == p2->est_success_rate)
 343         return 0;
 344       else if (wantfailure)
 345         return p1->est_success_rate < p2->est_success_rate ? -1 :  1;
 346       else
 347         return p1->est_success_rate < p2->est_success_rate ?  1 : -1;
 348     }
 349   else
 350     {
 351       return p1->p_cost < p2->p_cost ? -1 : 1;
 352     }
 353 }
 354
 355 \f
 356 static void
 357 predlist_merge_sort(struct predlist *list,
 358                     struct predicate **last)
 359 {
 360   struct predlist new_list;
 361   struct predicate *p, *q;
 362
 363   if (NULL == list->head)
 364     return;                     /* nothing to do */
 365
 366   if (options.debug_options & DebugTreeOpt)
 367     {
 368       fprintf(stderr, "%s:\n", "predlist before merge sort");
 369       print_tree(stderr, list->head, 2);
 370     }
 371
 372   calculate_derived_rates(list->head);
 373   predlist_init(&new_list);
 374   while (list->head)
 375     {
 376       /* remove head of source list */
 377       q = list->head;
 378       list->head = list->head->pred_left;
 379       q->pred_left = NULL;
 380
 381       /* insert it into the new list */
 382       for (p=new_list.head; p; p=p->pred_left)
 383         {
 384           /* If these operations are OR operations, we want to get a
 385            * successful test as soon as possible, to take advantage of
 386            * the short-circuit evaluation.  If they're AND, we want to
 387            * get an unsuccessful result early for the same reason.
 388            * Therefore we invert the sense of the comparison for the
 389            * OR case.  We only want to invert the sense of the success
 390            * rate comparison, not the operation cost comparison.  Hence we
 391            * pass a flag into pred_cost_compare().
 392            */
 393           boolean wantfailure = (OR_PREC != p->p_prec);
 394           if (pred_cost_compare(p->pred_right, q->pred_right, wantfailure) >= 0)
 395             break;
 396         }
 397       if (p)
 398         {
 399           /* insert into existing list */
 400           q->pred_left = p->pred_left;
 401           if (NULL == q->pred_left)
 402             new_list.tail = q;
 403           p->pred_left = q;
 404         }
 405       else
 406         {
 407           q->pred_left = new_list.head; /* prepend */
 408           new_list.head = q;
 409           if (NULL == new_list.tail)
 410             new_list.tail = q; /* first item in new list */
 411         }
 412     }
 413   if (options.debug_options & DebugTreeOpt)
 414     {
 415       fprintf(stderr, "%s:\n", "predlist after merge sort");
 416       print_tree(stderr, new_list.head, 2);
 417     }
 418
 419   calculate_derived_rates(new_list.head);
 420   merge_pred(new_list.head, new_list.tail, last);
 421   predlist_init(list);
 422 }
 423 \f
 424 static void
 425 merge_lists(struct predlist lists[], int nlists,
 426             struct predlist *name_list,
 427             struct predlist *regex_list,
 428             struct predicate **last)
 429 {
 430   int i;
 431   static void (*mergefn)(struct predlist *, struct predicate**);
 432
 433   mergefn = predlist_merge_sort;
 434
 435   mergefn(name_list,   last);
 436   mergefn(regex_list,  last);
 437
 438   for (i=0; i<nlists; i++)
 439     mergefn(&lists[i], last);
 440 }
 441
 442
 443 \f
 444 static boolean
 445 subtree_has_side_effects(const struct predicate *p)
 446 {
 447   if (p)
 448     {
 449       return p->side_effects
 450         || subtree_has_side_effects(p->pred_left)
 451         || subtree_has_side_effects(p->pred_right);
 452     }
 453   else
 454     {
 455
 456       return false;
 457     }
 458 }
 459 \f
 460 static int
 461 worst_cost (const struct predicate *p)
 462 {
 463   if (p)
 464     {
 465       unsigned int cost_r, cost_l, worst;
 466       cost_l = worst_cost(p->pred_left);
 467       cost_r = worst_cost(p->pred_right);
 468       worst = (cost_l > cost_r) ? cost_l : cost_r;
 469       if (worst < p->p_cost)
 470         worst = p->p_cost;
 471       return worst;
 472     }
 473   else
 474     {
 475       return 0;
 476     }
 477 }
 478
 479
 480 \f
 481 static void
 482 perform_arm_swap(struct predicate *p)
 483 {
 484   struct predicate *tmp = p->pred_left->pred_right;
 485   p->pred_left->pred_right = p->pred_right;
 486   p->pred_right = tmp;
 487 }
 488 \f
 489 /* Consider swapping p->pred_left->pred_right with p->pred_right,
 490  * if that yields a faster evaluation.   Normally the left predicate is
 491  * evaluated first.
 492  *
 493  * If the operation is an OR, we want the left predicate to be the one that
 494  * succeeds most often.   If it is an AND, we want it to be the predicate that
 495  * fails most often.
 496  *
 497  * We don't consider swapping arms of an operator where their cost is
 498  * different or where they have side effects.
 499  *
 500  * A viable test case for this is
 501  * ./find -D opt   -O3  .   \! -type f -o -type d
 502  * Here, the ! -type f should be evaluated first,
 503  * as we assume that 95% of inodes are vanilla files.
 504  */
 505 static boolean
 506 consider_arm_swap(struct predicate *p)
 507 {
 508   int left_cost, right_cost;
 509   const char *reason = NULL;
 510   struct predicate **pl, **pr;
 511
 512   if (BI_OP != p->p_type)
 513     reason = "Not a binary operation";
 514
 515   if (!reason)
 516     {
 517       if (NULL == p->pred_left || NULL == p->pred_right)
 518         reason = "Doesn't have two arms";
 519     }
 520
 521
 522   if (!reason)
 523     {
 524       if (NULL == p->pred_left->pred_right)
 525         reason = "Left arm has no child on RHS";
 526     }
 527   pr = &p->pred_right;
 528   pl = &p->pred_left->pred_right;
 529
 530   if (!reason)
 531     {
 532       if (subtree_has_side_effects(*pl))
 533         reason = "Left subtree has side-effects";
 534     }
 535   if (!reason)
 536     {
 537       if (subtree_has_side_effects(*pr))
 538         reason = "Right subtree has side-effects";
 539     }
 540
 541   if (!reason)
 542     {
 543       left_cost = worst_cost(*pl);
 544       right_cost = worst_cost(*pr);
 545
 546       if (left_cost < right_cost)
 547         {
 548           reason = "efficient as-is";
 549         }
 550     }
 551   if (!reason)
 552     {
 553       boolean want_swap;
 554
 555       if (left_cost == right_cost)
 556         {
 557           /* it's a candidate */
 558           float succ_rate_l = (*pl)->est_success_rate;
 559           float succ_rate_r = (*pr)->est_success_rate;
 560
 561           if (options.debug_options & DebugTreeOpt)
 562             {
 563               fprintf(stderr, "Success rates: l=%f, r=%f\n", succ_rate_l, succ_rate_r);
 564             }
 565
 566           if (pred_or == p->pred_func)
 567             {
 568               want_swap = succ_rate_r < succ_rate_l;
 569               if (!want_swap)
 570                 reason = "Operation is OR and right success rate >= left";
 571             }
 572           else if (pred_and == p->pred_func)
 573             {
 574               want_swap = succ_rate_r > succ_rate_l;
 575               if (!want_swap)
 576                 reason = "Operation is AND and right success rate <= left";
 577             }
 578           else
 579             {
 580               want_swap = false;
 581               reason = "Not AND or OR";
 582             }
 583         }
 584       else
 585         {
 586           want_swap = true;
 587         }
 588
 589       if (want_swap)
 590         {
 591           if (options.debug_options & DebugTreeOpt)
 592             {
 593               fprintf(stderr, "Performing arm swap on:\n");
 594               print_tree (stderr, p, 0);
 595             }
 596           perform_arm_swap(p);
 597           return true;
 598         }
 599     }
 600
 601
 602   if (options.debug_options & DebugTreeOpt)
 603     {
 604       fprintf(stderr, "Not an arm swap candidate (%s):\n", reason);
 605       print_tree (stderr, p, 0);
 606     }
 607   return false;
 608 }
 609 \f
 610 static boolean
 611 do_arm_swaps(struct predicate *p)
 612 {
 613   if (p)
 614     {
 615       boolean swapped;
 616       do
 617         {
 618           swapped = false;
 619           if (consider_arm_swap(p)
 620               || do_arm_swaps(p->pred_left)
 621               || do_arm_swaps(p->pred_right))
 622             {
 623               swapped = true;
 624             }
 625         } while (swapped);
 626       return swapped;
 627     }
 628   else
 629     {
 630       return false;
 631     }
 632 }
 633
 634
 635 \f
 636 /* Optimize the ordering of the predicates in the tree.  Rearrange
 637    them to minimize work.  Strategies:
 638    * Evaluate predicates that don't need inode information first;
 639      the predicates are divided into 1 or more groups separated by
 640      predicates (if any) which have "side effects", such as printing.
 641      The grouping implements the partial ordering on predicates which
 642      those with side effects impose.
 643
 644    * Place -name, -iname, -path, -ipath, -regex and -iregex at the front
 645      of a group, with -name, -iname, -path and -ipath ahead of
 646      -regex and -iregex.  Predicates which are moved to the front
 647      of a group by definition do not have side effects.  Both
 648      -regex and -iregex both use pred_regex.
 649
 650      If higher optimisation levels have been selected, reordering also
 651      occurs according to the p_cost member of each predicate (which
 652      reflects the performance cost of the test).  The ordering also
 653      bears in mind whether these operations are more likely to succeed
 654      or fail.  When evauating a chain of OR conditions, we prefer
 655      tests likely to succeed at the front of the list.  For AND, we
 656      prefer tests likely to fail at the front of the list.
 657
 658      This routine "normalizes" the predicate tree by ensuring that
 659      all expression predicates have AND (or OR or COMMA) parent nodes
 660      which are linked along the left edge of the expression tree.
 661      This makes manipulation of subtrees easier.
 662
 663      EVAL_TREEP points to the root pointer of the predicate tree
 664      to be rearranged.  opt_expr may return a new root pointer there.
 665      Return true if the tree contains side effects, false if not. */
 666
 667 static boolean
 668 opt_expr (struct predicate **eval_treep)
 669 {
 670   struct predlist regex_list={NULL,NULL}, name_list={NULL,NULL};
 671   struct predlist cbo_list[NumEvaluationCosts];
 672   int i;
 673   struct predicate *curr;
 674   struct predicate **prevp;     /* Address of `curr' node. */
 675   struct predicate **last_sidep; /* Last predicate with side effects. */
 676   PRED_FUNC pred_func;
 677   enum predicate_type p_type;
 678   boolean has_side_effects = false; /* Return value. */
 679   enum predicate_precedence prev_prec, /* precedence of last BI_OP in branch */
 680                             biop_prec; /* topmost BI_OP precedence in branch */
 681
 682   if (eval_treep == NULL || *eval_treep == NULL)
 683     return (false);
 684
 685   for (i=0; i<NumEvaluationCosts; i++)
 686     predlist_init(&cbo_list[i]);
 687
 688   /* Set up to normalize tree as a left-linked list of ANDs or ORs.
 689      Set `curr' to the leftmost node, `prevp' to its address, and
 690      `pred_func' to the predicate type of its parent. */
 691   prevp = eval_treep;
 692   prev_prec = AND_PREC;
 693   curr = *prevp;
 694   while (curr->pred_left != NULL)
 695     {
 696       prevp = &curr->pred_left;
 697       prev_prec = curr->p_prec; /* must be a BI_OP */
 698       curr = curr->pred_left;
 699     }
 700
 701   /* Link in the appropriate BI_OP for the last expression, if needed. */
 702   if (curr->p_type != BI_OP)
 703     set_new_parent (curr, prev_prec, prevp);
 704
 705   if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
 706     {
 707       /* Normalized tree. */
 708       fprintf (stderr, "Normalized Eval Tree:\n");
 709       print_tree (stderr, *eval_treep, 0);
 710     }
 711
 712   /* Rearrange the predicates. */
 713   prevp = eval_treep;
 714   biop_prec = NO_PREC; /* not COMMA_PREC */
 715   if ((*prevp) && (*prevp)->p_type == BI_OP)
 716     biop_prec = (*prevp)->p_prec;
 717   while ((curr = *prevp) != NULL)
 718     {
 719       /* If there is a BI_OP of different precedence from the first
 720          in the pred_left chain, create a new parent of the
 721          original precedence, link the new parent to the left of the
 722          previous and link CURR to the right of the new parent.
 723          This preserves the precedence of expressions in the tree
 724          in case we rearrange them. */
 725       if (curr->p_type == BI_OP)
 726         {
 727           if (curr->p_prec != biop_prec)
 728             curr = set_new_parent(curr, biop_prec, prevp);
 729         }
 730
 731       /* See which predicate type we have. */
 732       p_type = curr->pred_right->p_type;
 733       pred_func = curr->pred_right->pred_func;
 734
 735
 736       switch (p_type)
 737         {
 738         case NO_TYPE:
 739         case PRIMARY_TYPE:
 740           /* Don't rearrange the arguments of the comma operator, it is
 741              not commutative.  */
 742           if (biop_prec == COMMA_PREC)
 743             break;
 744
 745           /* If this predicate has no side effects, consider reordering it. */
 746           if (!curr->pred_right->side_effects)
 747             {
 748               boolean reorder;
 749
 750               /* If it's one of our special primaries, move it to the
 751                  front of the list for that primary. */
 752               if (predicate_is_cost_free(curr->pred_right))
 753                 {
 754                   if (options.debug_options & DebugTreeOpt)
 755                     {
 756                       fprintf(stderr, "-O%d: promoting cheap predicate ",
 757                               (int)options.optimisation_level);
 758                       print_predicate(stderr, curr->pred_right);
 759                       fprintf(stderr, " into name_list\n");
 760                     }
 761                   predlist_insert(&name_list, curr, prevp);
 762                   continue;
 763                 }
 764
 765               if (pred_func == pred_regex)
 766                 {
 767                   predlist_insert(&regex_list, curr, prevp);
 768                   continue;
 769                 }
 770
 771               reorder = ((options.optimisation_level > 1)
 772                           && (NeedsType == curr->pred_right->p_cost)
 773                           && !curr->pred_right->need_stat) ||
 774                 (options.optimisation_level > 2);
 775
 776               if (reorder)
 777                 {
 778                   if (options.debug_options & DebugTreeOpt)
 779                     {
 780                       fprintf(stderr, "-O%d: categorising predicate ",
 781                               (int)options.optimisation_level);
 782                       print_predicate(stderr, curr->pred_right);
 783                       fprintf(stderr, " by cost (%s)\n",
 784                               cost_name(curr->pred_right->p_cost));
 785                     }
 786                   predlist_insert(&cbo_list[curr->pred_right->p_cost], curr, prevp);
 787                   continue;
 788                 }
 789             }
 790
 791           break;
 792
 793         case UNI_OP:
 794           /* For NOT, check the expression trees below the NOT. */
 795           curr->pred_right->side_effects
 796             = opt_expr (&curr->pred_right->pred_right);
 797           break;
 798
 799         case BI_OP:
 800           /* For nested AND or OR, recurse (AND/OR form layers on the left of
 801              the tree), and continue scanning this level of AND or OR. */
 802           curr->pred_right->side_effects = opt_expr (&curr->pred_right);
 803           break;
 804
 805           /* At this point, get_expr and scan_rest have already removed
 806              all of the user's parentheses. */
 807
 808         default:
 809           error (1, 0, _("oops -- invalid expression type!"));
 810           break;
 811         }
 812
 813       if (curr->pred_right->side_effects == true)
 814         {
 815           last_sidep = prevp;
 816
 817           /* Incorporate lists and reset list pointers for this group.  */
 818           merge_lists(cbo_list, NumEvaluationCosts, &name_list, &regex_list, last_sidep);
 819           has_side_effects = true;
 820         }
 821
 822       prevp = &curr->pred_left;
 823     }
 824
 825   /* Do final list merges. */
 826   last_sidep = prevp;
 827   merge_lists(cbo_list, NumEvaluationCosts, &name_list, &regex_list, last_sidep);
 828   return has_side_effects;
 829 }
 830 \f
 831 static float
 832 constrain_rate(float rate)
 833 {
 834   if (rate > 1.0f)
 835     return 1.0;
 836   else if (rate < 0.0)
 837     return 0.0;
 838   else
 839     return rate;
 840 }
 841 \f
 842 /* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
 843    HIGH_PREC. */
 844
 845 static struct predicate *
 846 set_new_parent (struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp)
 847 {
 848   struct predicate *new_parent;
 849
 850   new_parent = (struct predicate *) xmalloc (sizeof (struct predicate));
 851   new_parent->p_type = BI_OP;
 852   new_parent->p_prec = high_prec;
 853   new_parent->need_stat = false;
 854   new_parent->need_type = false;
 855   new_parent->p_cost = NeedsNothing;
 856
 857   switch (high_prec)
 858     {
 859     case COMMA_PREC:
 860       new_parent->pred_func = pred_comma;
 861       new_parent->p_name = ",";
 862       new_parent->est_success_rate = 1.0;
 863       break;
 864     case OR_PREC:
 865       new_parent->pred_func = pred_or;
 866       new_parent->p_name = "-o";
 867       new_parent->est_success_rate = constrain_rate(curr->est_success_rate);
 868       break;
 869     case AND_PREC:
 870       new_parent->pred_func = pred_and;
 871       new_parent->p_name = "-a";
 872       new_parent->est_success_rate = constrain_rate(curr->est_success_rate);
 873       break;
 874     default:
 875       ;                         /* empty */
 876     }
 877
 878   new_parent->side_effects = false;
 879   new_parent->no_default_print = false;
 880   new_parent->args.str = NULL;
 881   new_parent->pred_next = NULL;
 882
 883   /* Link in new_parent.
 884      Pushes rest of left branch down 1 level to new_parent->pred_right. */
 885   new_parent->pred_left = NULL;
 886   new_parent->pred_right = curr;
 887   *prevp = new_parent;
 888
 889   return new_parent;
 890 }
 891
 892 /* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
 893    into the tree at LAST_P. */
 894
 895 static void
 896 merge_pred (struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p)
 897 {
 898   end_list->pred_left = *last_p;
 899   *last_p = beg_list;
 900 }
 901 \f
 902 /* Find the first node in expression tree TREE that requires
 903    a stat call and mark the operator above it as needing a stat
 904    before calling the node.   Since the expression precedences
 905    are represented in the tree, some preds that need stat may not
 906    get executed (because the expression value is determined earlier.)
 907    So every expression needing stat must be marked as such, not just
 908    the earliest, to be sure to obtain the stat.  This still guarantees
 909    that a stat is made as late as possible.  Return true if the top node
 910    in TREE requires a stat, false if not. */
 911
 912 static boolean
 913 mark_stat (struct predicate *tree)
 914 {
 915   /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
 916      to find the first predicate for which the stat is needed. */
 917   switch (tree->p_type)
 918     {
 919     case NO_TYPE:
 920     case PRIMARY_TYPE:
 921       return tree->need_stat;
 922
 923     case UNI_OP:
 924       if (mark_stat (tree->pred_right))
 925         tree->need_stat = true;
 926       return (false);
 927
 928     case BI_OP:
 929       /* ANDs and ORs are linked along ->left ending in NULL. */
 930       if (tree->pred_left != NULL)
 931         mark_stat (tree->pred_left);
 932
 933       if (mark_stat (tree->pred_right))
 934         tree->need_stat = true;
 935
 936       return (false);
 937
 938     default:
 939       error (1, 0, _("oops -- invalid expression type in mark_stat!"));
 940       return (false);
 941     }
 942 }
 943 \f
 944 /* Find the first node in expression tree TREE that we will
 945    need to know the file type, if any.   Operates in the same
 946    was as mark_stat().
 947 */
 948 static boolean
 949 mark_type (struct predicate *tree)
 950 {
 951   /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
 952      to find the first predicate for which the type information is needed. */
 953   switch (tree->p_type)
 954     {
 955     case NO_TYPE:
 956     case PRIMARY_TYPE:
 957       return tree->need_type;
 958
 959     case UNI_OP:
 960       if (mark_type (tree->pred_right))
 961         tree->need_type = true;
 962       return false;
 963
 964     case BI_OP:
 965       /* ANDs and ORs are linked along ->left ending in NULL. */
 966       if (tree->pred_left != NULL)
 967         mark_type (tree->pred_left);
 968
 969       if (mark_type (tree->pred_right))
 970         tree->need_type = true;
 971
 972       return false;
 973
 974     default:
 975       error (1, 0, _("oops -- invalid expression type in mark_type!"));
 976       return (false);
 977     }
 978 }
 979 \f
 980 struct pred_cost_lookup
 981 {
 982   PRED_FUNC             fn;
 983   enum EvaluationCost   cost;
 984 };
 985 static struct pred_cost_lookup costlookup[] =
 986   {
 987     { pred_amin      ,  NeedsStatInfo        },
 988     { pred_and       ,  NeedsNothing,        },
 989     { pred_anewer    ,  NeedsStatInfo,       },
 990     { pred_atime     ,  NeedsStatInfo,       },
 991     { pred_close     ,  NeedsNothing         },
 992     { pred_cmin      ,  NeedsStatInfo,       },
 993     { pred_cnewer    ,  NeedsStatInfo,       },
 994     { pred_comma     ,  NeedsNothing,        },
 995     { pred_ctime     ,  NeedsStatInfo,       },
 996     { pred_delete    ,  NeedsSyncDiskHit     },
 997     { pred_empty     ,  NeedsStatInfo        },
 998     { pred_exec      ,  NeedsEventualExec    },
 999     { pred_execdir   ,  NeedsEventualExec    },
1000     { pred_executable,  NeedsAccessInfo      },
1001     { pred_false     ,  NeedsNothing         },
1002     { pred_fprint    ,  NeedsNothing         },
1003     { pred_fprint0   ,  NeedsNothing         },
1004     { pred_fprintf   ,  NeedsNothing         },
1005     { pred_fstype    ,  NeedsStatInfo        }, /* true for amortised cost */
1006     { pred_gid       ,  NeedsStatInfo        },
1007     { pred_group     ,  NeedsStatInfo        },
1008     { pred_ilname    ,  NeedsLinkName        },
1009     { pred_iname     ,  NeedsNothing         },
1010     { pred_inum      ,  NeedsStatInfo        },
1011     { pred_ipath     ,  NeedsNothing         },
1012     { pred_links     ,  NeedsStatInfo        },
1013     { pred_lname     ,  NeedsLinkName        },
1014     { pred_ls        ,  NeedsStatInfo        },
1015     { pred_mmin      ,  NeedsStatInfo        },
1016     { pred_mtime     ,  NeedsStatInfo        },
1017     { pred_name      ,  NeedsNothing         },
1018     { pred_negate    ,  NeedsNothing,        },
1019     { pred_newer     ,  NeedsStatInfo,       },
1020     { pred_nogroup   ,  NeedsStatInfo        }, /* true for amortised cost if caching is on */
1021     { pred_nouser    ,  NeedsStatInfo        }, /* true for amortised cost if caching is on */
1022     { pred_ok        ,  NeedsUserInteraction },
1023     { pred_okdir     ,  NeedsUserInteraction },
1024     { pred_open      ,  NeedsNothing         },
1025     { pred_or        ,  NeedsNothing,        },
1026     { pred_path      ,  NeedsNothing         },
1027     { pred_perm      ,  NeedsStatInfo        },
1028     { pred_print     ,  NeedsNothing         },
1029     { pred_print0    ,  NeedsNothing         },
1030     { pred_prune     ,  NeedsNothing         },
1031     { pred_quit      ,  NeedsNothing         },
1032     { pred_readable  ,  NeedsAccessInfo      },
1033     { pred_regex     ,  NeedsNothing         },
1034     { pred_samefile  ,  NeedsStatInfo        },
1035     { pred_size      ,  NeedsStatInfo        },
1036     { pred_true      ,  NeedsNothing         },
1037     { pred_type      ,  NeedsType            },
1038     { pred_uid       ,  NeedsStatInfo        },
1039     { pred_used      ,  NeedsStatInfo        },
1040     { pred_user      ,  NeedsStatInfo        },
1041     { pred_writable  ,  NeedsAccessInfo      },
1042     { pred_xtype     ,  NeedsType            } /* roughly correct unless most files are symlinks */
1043   };
1044 static int pred_table_sorted = 0;
1045 \f
1046 static boolean
1047 check_sorted(void *base, size_t members, size_t membersize,
1048              int (*cmpfn)(const void*, const void*))
1049 {
1050   const char *p = base;
1051   size_t i;
1052   for (i=1u; i<members; ++i)
1053     {
1054       int result = cmpfn(p+i*membersize, p+(i-1)*membersize);
1055       if (result < 0)
1056         return false;
1057       result = cmpfn(p+(i-1)*membersize, p+i*membersize);
1058       assert(result <= 0);
1059     }
1060   for (i=1u; i<members; ++i)
1061     {
1062       const struct pred_cost_lookup *pl1 = (const struct pred_cost_lookup*)(p+(i-1)*membersize);
1063       const struct pred_cost_lookup *pl2 = (const struct pred_cost_lookup*)(p+(i-0)*membersize);
1064       assert(pl1->fn <= pl2->fn);
1065     }
1066   return true;
1067 }
1068
1069 \f
1070 static int
1071 cost_table_comparison(const void *p1, const void *p2)
1072 {
1073   const struct pred_cost_lookup *pc1 = p1;
1074   const struct pred_cost_lookup *pc2 = p2;
1075
1076
1077   if (pc1->fn == pc2->fn)
1078     return 0;
1079   else if (pc1->fn > pc2->fn)
1080     return 1;
1081   else
1082     return -1;
1083 }
1084 \f
1085 static enum EvaluationCost
1086 get_pred_cost(struct predicate *p)
1087 {
1088   enum EvaluationCost data_requirement_cost = NeedsNothing;
1089   enum EvaluationCost inherent_cost = NeedsUnknown;
1090   PRED_FUNC f = p->pred_func;
1091
1092   if (p->need_stat)
1093     {
1094       data_requirement_cost = NeedsStatInfo;
1095     }
1096   else if (p->need_type)
1097     {
1098       data_requirement_cost = NeedsType;
1099     }
1100   else
1101     {
1102       data_requirement_cost = NeedsNothing;
1103     }
1104
1105   if (pred_exec == f || pred_execdir == f)
1106     {
1107       if (p->args.exec_vec.multiple)
1108         inherent_cost = NeedsEventualExec;
1109       else
1110         inherent_cost = NeedsImmediateExec;
1111     }
1112   else if (pred_fprintf == f)
1113     {
1114       /* the parser calculated the cost for us. */
1115       inherent_cost = p->p_cost;
1116     }
1117   else
1118     {
1119       struct pred_cost_lookup key;
1120       void *entry;
1121
1122       if (!pred_table_sorted)
1123         {
1124           qsort(costlookup,
1125                 sizeof(costlookup)/sizeof(costlookup[0]),
1126                 sizeof(costlookup[0]),
1127                 cost_table_comparison);
1128
1129           if (!check_sorted(costlookup,
1130                             sizeof(costlookup)/sizeof(costlookup[0]),
1131                             sizeof(costlookup[0]),
1132                             cost_table_comparison))
1133             {
1134               error(1, 0, "Failed to sort the costlookup array.");
1135             }
1136           pred_table_sorted = 1;
1137         }
1138       key.fn = p->pred_func;
1139       entry = bsearch(&key, costlookup,
1140                       sizeof(costlookup)/sizeof(costlookup[0]),
1141                       sizeof(costlookup[0]),
1142                       cost_table_comparison);
1143       if (entry)
1144         {
1145           inherent_cost = ((const struct pred_cost_lookup*)entry)->cost;
1146         }
1147       else
1148         {
1149           error(0, 0, "warning: no cost entry for predicate %s", p->p_name);
1150           inherent_cost = NeedsUnknown;
1151         }
1152     }
1153
1154   if (inherent_cost > data_requirement_cost)
1155     return inherent_cost;
1156   else
1157     return data_requirement_cost;
1158 }
1159 \f
1160 static void
1161 estimate_costs (struct predicate *tree)
1162 {
1163   if (tree)
1164     {
1165       estimate_costs(tree->pred_right);
1166       estimate_costs(tree->pred_left);
1167
1168       tree->p_cost = get_pred_cost(tree);
1169     }
1170 }
1171
1172 struct predicate*
1173 get_eval_tree(void)
1174 {
1175   return eval_tree;
1176 }
1177
1178 static float
1179 getrate(const struct predicate *p)
1180 {
1181   if (p)
1182     return p->est_success_rate;
1183   else
1184     return 1.0;
1185 }
1186
1187
1188 float
1189 calculate_derived_rates(struct predicate *p)
1190 {
1191   float rate;
1192
1193   assert(NULL != p);
1194
1195   if (p->pred_right)
1196     calculate_derived_rates(p->pred_right);
1197   if (p->pred_left)
1198     calculate_derived_rates(p->pred_left);
1199
1200   assert(p->p_type != CLOSE_PAREN);
1201   assert(p->p_type != OPEN_PAREN);
1202
1203   if (p->p_type == PRIMARY_TYPE)
1204     {
1205       assert(NULL == p->pred_right);
1206       assert(NULL == p->pred_left);
1207       return p->est_success_rate;
1208     }
1209   else if (p->p_type == UNI_OP)
1210     {
1211       /* Unary operators must have exactly one operand */
1212       assert(pred_negate == p->pred_func);
1213       assert(NULL == p->pred_left);
1214       rate = 1.0 - p->pred_right->est_success_rate;
1215     }
1216   else if (p->p_type == BI_OP)
1217     {
1218       /* Binary operators must have two operands */
1219       if (pred_and == p->pred_func)
1220         {
1221           rate = getrate(p->pred_right) * getrate(p->pred_left);
1222         }
1223       else if (pred_comma == p->pred_func)
1224         {
1225           rate = 1.0;
1226         }
1227       else if (pred_or == p->pred_func)
1228         {
1229           rate = getrate(p->pred_right) + getrate(p->pred_left);
1230         }
1231     }
1232   else if (p->p_type == CLOSE_PAREN || p->p_type == OPEN_PAREN)
1233     {
1234       rate = 1.0;
1235     }
1236   else if (p->p_type == NO_TYPE)
1237     {
1238       assert(NULL == p->pred_right);
1239       assert(NULL == p->pred_left);
1240       return p->est_success_rate;
1241     }
1242   p->est_success_rate = constrain_rate(rate);
1243   return p->est_success_rate;
1244 }
1245 \f
1246 /* opt_expr() rearranges predicates such that each left subtree is
1247  * rooted at a logical predicate (e.g. and or or).  check_normalization()
1248  * asserts that this property still holds.
1249  *
1250  */
1251 static void check_normalization(struct predicate *p, boolean at_root)
1252 {
1253   if (at_root)
1254     {
1255       assert(BI_OP == p->p_type);
1256     }
1257
1258   if (p->pred_left)
1259     {
1260       assert(BI_OP == p->pred_left->p_type);
1261       check_normalization(p->pred_left, false);
1262     }
1263   if (p->pred_right)
1264     {
1265       check_normalization(p->pred_right, false);
1266     }
1267 }
1268 \f
1269 struct predicate*
1270 build_expression_tree(int argc, char *argv[], int end_of_leading_options)
1271 {
1272   const struct parser_table *parse_entry; /* Pointer to the parsing table entry for this expression. */
1273   char *predicate_name;         /* Name of predicate being parsed. */
1274   struct predicate *cur_pred;
1275   const struct parser_table *entry_close, *entry_print, *entry_open;
1276   int i, oldi;
1277
1278   predicates = NULL;
1279
1280   /* Find where in ARGV the predicates begin by skipping the list of start points. */
1281   for (i = end_of_leading_options; i < argc && !looks_like_expression(argv[i], true); i++)
1282     {
1283       /* fprintf(stderr, "Looks like %s is not a predicate\n", argv[i]); */
1284       /* Do nothing. */ ;
1285     }
1286
1287   /* XXX: beginning of bit we need factor out of both find.c and ftsfind.c */
1288   /* Enclose the expression in `( ... )' so a default -print will
1289      apply to the whole expression. */
1290   entry_open  = find_parser("(");
1291   entry_close = find_parser(")");
1292   entry_print = find_parser("print");
1293   assert(entry_open  != NULL);
1294   assert(entry_close != NULL);
1295   assert(entry_print != NULL);
1296
1297   parse_open (entry_open, argv, &argc);
1298   last_pred->p_name = "(";
1299   predicates->artificial = true;
1300   parse_begin_user_args(argv, argc, last_pred, predicates);
1301   pred_sanity_check(last_pred);
1302
1303   /* Build the input order list. */
1304   while (i < argc )
1305     {
1306       if (!looks_like_expression(argv[i], false))
1307         {
1308           error (0, 0, _("paths must precede expression: %s"), argv[i]);
1309           usage(stderr, 1, NULL);
1310         }
1311
1312       predicate_name = argv[i];
1313       parse_entry = find_parser (predicate_name);
1314       if (parse_entry == NULL)
1315         {
1316           /* Command line option not recognized */
1317           error (1, 0, _("invalid predicate `%s'"), predicate_name);
1318         }
1319
1320       i++;
1321       oldi = i;
1322       if (!(*(parse_entry->parser_func)) (parse_entry, argv, &i))
1323         {
1324           if (argv[i] == NULL)
1325             /* Command line option requires an argument */
1326             error (1, 0, _("missing argument to `%s'"), predicate_name);
1327           else
1328             error (1, 0, _("invalid argument `%s' to `%s'"),
1329                    argv[i], predicate_name);
1330         }
1331       else
1332         {
1333           last_pred->p_name = predicate_name;
1334
1335           /* If the parser consumed an argument, save it. */
1336           if (i != oldi)
1337             last_pred->arg_text = argv[oldi];
1338           else
1339             last_pred->arg_text = NULL;
1340         }
1341       pred_sanity_check(last_pred);
1342       pred_sanity_check(predicates); /* XXX: expensive */
1343     }
1344   parse_end_user_args(argv, argc, last_pred, predicates);
1345   if (predicates->pred_next == NULL)
1346     {
1347       /* No predicates that do something other than set a global variable
1348          were given; remove the unneeded initial `(' and add `-print'. */
1349       cur_pred = predicates;
1350       predicates = last_pred = predicates->pred_next;
1351       free ((char *) cur_pred);
1352       parse_print (entry_print, argv, &argc);
1353       last_pred->p_name = "-print";
1354       pred_sanity_check(last_pred);
1355       pred_sanity_check(predicates); /* XXX: expensive */
1356     }
1357   else if (!default_prints (predicates->pred_next))
1358     {
1359       /* One or more predicates that produce output were given;
1360          remove the unneeded initial `('. */
1361       cur_pred = predicates;
1362       predicates = predicates->pred_next;
1363       pred_sanity_check(predicates); /* XXX: expensive */
1364       free ((char *) cur_pred);
1365     }
1366   else
1367     {
1368       /* `( user-supplied-expression ) -print'. */
1369       parse_close (entry_close, argv, &argc);
1370       last_pred->p_name = ")";
1371       last_pred->artificial = true;
1372       pred_sanity_check(last_pred);
1373       parse_print (entry_print, argv, &argc);
1374       last_pred->p_name = "-print";
1375       last_pred->artificial = true;
1376       pred_sanity_check(last_pred);
1377       pred_sanity_check(predicates); /* XXX: expensive */
1378     }
1379
1380   if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1381     {
1382       fprintf (stderr, "Predicate List:\n");
1383       print_list (stderr, predicates);
1384     }
1385
1386   /* do a sanity check */
1387   pred_sanity_check(predicates);
1388
1389   /* Done parsing the predicates.  Build the evaluation tree. */
1390   cur_pred = predicates;
1391   eval_tree = get_expr (&cur_pred, NO_PREC, NULL);
1392   calculate_derived_rates(eval_tree);
1393
1394   /* Check if we have any left-over predicates (this fixes
1395    * Debian bug #185202).
1396    */
1397   if (cur_pred != NULL)
1398     {
1399       /* cur_pred->p_name is often NULL here */
1400       if (cur_pred->pred_func == pred_close)
1401         {
1402           /* e.g. "find \( -true \) \)" */
1403           error (1, 0, _("you have too many ')'"), cur_pred->p_name);
1404         }
1405       else
1406         {
1407           if (cur_pred->p_name)
1408             error (1, 0, _("unexpected extra predicate '%s'"), cur_pred->p_name);
1409           else
1410             error (1, 0, _("unexpected extra predicate"));
1411         }
1412     }
1413
1414   if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1415     {
1416       fprintf (stderr, "Eval Tree:\n");
1417       print_tree (stderr, eval_tree, 0);
1418     }
1419
1420   estimate_costs(eval_tree);
1421
1422   /* Rearrange the eval tree in optimal-predicate order. */
1423   opt_expr (&eval_tree);
1424
1425   /* Check that the tree is in normalised order (opt_expr does this) */
1426   check_normalization(eval_tree, true);
1427
1428   do_arm_swaps(eval_tree);
1429
1430   /* Check that the tree is still in normalised order */
1431   check_normalization(eval_tree, true);
1432
1433   /* Determine the point, if any, at which to stat the file. */
1434   mark_stat (eval_tree);
1435   /* Determine the point, if any, at which to determine file type. */
1436   mark_type (eval_tree);
1437
1438   if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1439     {
1440       fprintf (stderr, "Optimized Eval Tree:\n");
1441       print_tree (stderr, eval_tree, 0);
1442       fprintf (stderr, "Optimized command line:\n");
1443       print_optlist(stderr, eval_tree);
1444       fprintf(stderr, "\n");
1445     }
1446
1447   return eval_tree;
1448 }
1449 \f
1450 /* Return a pointer to a new predicate structure, which has been
1451    linked in as the last one in the predicates list.
1452
1453    Set `predicates' to point to the start of the predicates list.
1454    Set `last_pred' to point to the new last predicate in the list.
1455
1456    Set all cells in the new structure to the default values. */
1457
1458 struct predicate *
1459 get_new_pred (const struct parser_table *entry)
1460 {
1461   register struct predicate *new_pred;
1462   (void) entry;
1463
1464   /* Options should not be turned into predicates. */
1465   assert(entry->type != ARG_OPTION);
1466   assert(entry->type != ARG_POSITIONAL_OPTION);
1467
1468   if (predicates == NULL)
1469     {
1470       predicates = (struct predicate *)
1471         xmalloc (sizeof (struct predicate));
1472       last_pred = predicates;
1473     }
1474   else
1475     {
1476       new_pred = (struct predicate *) xmalloc (sizeof (struct predicate));
1477       last_pred->pred_next = new_pred;
1478       last_pred = new_pred;
1479     }
1480   last_pred->parser_entry = entry;
1481   last_pred->pred_func = NULL;
1482   last_pred->p_name = NULL;
1483   last_pred->p_type = NO_TYPE;
1484   last_pred->p_prec = NO_PREC;
1485   last_pred->side_effects = false;
1486   last_pred->no_default_print = false;
1487   last_pred->need_stat = true;
1488   last_pred->need_type = true;
1489   last_pred->args.str = NULL;
1490   last_pred->pred_next = NULL;
1491   last_pred->pred_left = NULL;
1492   last_pred->pred_right = NULL;
1493   last_pred->literal_control_chars = options.literal_control_chars;
1494   last_pred->artificial = false;
1495   last_pred->est_success_rate = 1.0;
1496   return last_pred;
1497 }
1498 \f
1499 /* Return a pointer to a new predicate, with operator check.
1500    Like get_new_pred, but it checks to make sure that the previous
1501    predicate is an operator.  If it isn't, the AND operator is inserted. */
1502
1503 struct predicate *
1504 get_new_pred_chk_op (const struct parser_table *entry)
1505 {
1506   struct predicate *new_pred;
1507   static const struct parser_table *entry_and = NULL;
1508
1509   /* Locate the entry in the parser table for the "and" operator */
1510   if (NULL == entry_and)
1511     entry_and = find_parser("and");
1512
1513   /* Check that it's actually there. If not, that is a bug.*/
1514   assert(entry_and != NULL);
1515
1516   if (last_pred)
1517     switch (last_pred->p_type)
1518       {
1519       case NO_TYPE:
1520         error (1, 0, _("oops -- invalid default insertion of and!"));
1521         break;
1522
1523       case PRIMARY_TYPE:
1524       case CLOSE_PAREN:
1525         /* We need to interpose the and operator. */
1526         new_pred = get_new_pred (entry_and);
1527         new_pred->pred_func = pred_and;
1528         new_pred->p_name = "-a";
1529         new_pred->p_type = BI_OP;
1530         new_pred->p_prec = AND_PREC;
1531         new_pred->need_stat = false;
1532         new_pred->need_type = false;
1533         new_pred->args.str = NULL;
1534         new_pred->side_effects = false;
1535         new_pred->no_default_print = false;
1536         break;
1537
1538       default:
1539         break;
1540       }
1541
1542   new_pred = get_new_pred (entry);
1543   new_pred->parser_entry = entry;
1544   return new_pred;
1545 }
1546 \f
1547 struct cost_assoc
1548 {
1549   enum EvaluationCost cost;
1550   char *name;
1551 };
1552 struct cost_assoc cost_table[] =
1553   {
1554     { NeedsNothing,         "Nothing" },
1555     { NeedsType,            "Type" },
1556     { NeedsStatInfo,        "StatInfo" },
1557     { NeedsLinkName,        "LinkName" },
1558     { NeedsAccessInfo,      "AccessInfo" },
1559     { NeedsSyncDiskHit,     "SyncDiskHit" },
1560     { NeedsEventualExec,    "EventualExec" },
1561     { NeedsImmediateExec,   "ImmediateExec" },
1562     { NeedsUserInteraction, "UserInteraction" },
1563     { NeedsUnknown,         "Unknown" }
1564   };
1565 \f
1566 struct prec_assoc
1567 {
1568   short prec;
1569   char *prec_name;
1570 };
1571
1572 static struct prec_assoc prec_table[] =
1573 {
1574   {NO_PREC, "no"},
1575   {COMMA_PREC, "comma"},
1576   {OR_PREC, "or"},
1577   {AND_PREC, "and"},
1578   {NEGATE_PREC, "negate"},
1579   {MAX_PREC, "max"},
1580   {-1, "unknown "}
1581 };
1582 \f
1583 struct op_assoc
1584 {
1585   short type;
1586   char *type_name;
1587 };
1588
1589 static struct op_assoc type_table[] =
1590 {
1591   {NO_TYPE,      "no"},
1592   {PRIMARY_TYPE, "primary"},
1593   {UNI_OP,       "uni_op"},
1594   {BI_OP,        "bi_op"},
1595   {OPEN_PAREN,   "open_paren  "},
1596   {CLOSE_PAREN,  "close_paren "},
1597   {-1,           "unknown"}
1598 };
1599 \f
1600 static const char *
1601 cost_name (enum EvaluationCost cost)
1602 {
1603   unsigned int i;
1604   unsigned int n = sizeof(cost_table)/sizeof(cost_table[0]);
1605
1606   for (i = 0; i<n; ++i)
1607     if (cost_table[i].cost == cost)
1608       return cost_table[i].name;
1609   return "unknown";
1610 }
1611 \f
1612
1613 static char *
1614 type_name (type)
1615      short type;
1616 {
1617   int i;
1618
1619   for (i = 0; type_table[i].type != (short) -1; i++)
1620     if (type_table[i].type == type)
1621       break;
1622   return (type_table[i].type_name);
1623 }
1624 \f
1625 static char *
1626 prec_name (prec)
1627      short prec;
1628 {
1629   int i;
1630
1631   for (i = 0; prec_table[i].prec != (short) -1; i++)
1632     if (prec_table[i].prec == prec)
1633       break;
1634   return (prec_table[i].prec_name);
1635 }
1636
1637 \f
1638 /* Walk the expression tree NODE to stdout.
1639    INDENT is the number of levels to indent the left margin. */
1640
1641 void
1642 print_tree (FILE *fp, struct predicate *node, int indent)
1643 {
1644   int i;
1645
1646   if (node == NULL)
1647     return;
1648   for (i = 0; i < indent; i++)
1649     fprintf (fp, "    ");
1650   fprintf (fp, "pred=[");
1651   print_predicate(fp, node);
1652   fprintf (fp, "] type=%s prec=%s",
1653           type_name (node->p_type), prec_name (node->p_prec));
1654   fprintf (fp, " cost=%s rate=%#03.2g %sside effects ",
1655            cost_name(node->p_cost),
1656            node->est_success_rate,
1657            (node->side_effects ? "" : "no "));
1658
1659   if (node->need_stat || node->need_type)
1660     {
1661       int comma = 0;
1662
1663       fprintf (fp, "Needs ");
1664       if (node->need_stat)
1665         {
1666           fprintf (fp, "stat");
1667           comma = 1;
1668         }
1669       if (node->need_type)
1670         {
1671           fprintf (fp, "%stype", comma ? "," : "");
1672         }
1673     }
1674   fprintf (fp, "\n");
1675
1676
1677   for (i = 0; i < indent; i++)
1678     fprintf (fp, "    ");
1679   if (NULL == node->pred_left && NULL == node->pred_right)
1680     {
1681       fprintf (fp, "no children.\n");
1682     }
1683   else
1684     {
1685       if (node->pred_left)
1686         {
1687           fprintf (fp, "left:\n");
1688           print_tree (fp, node->pred_left, indent + 1);
1689         }
1690       else
1691         {
1692           fprintf (fp, "no left.\n");
1693         }
1694
1695       for (i = 0; i < indent; i++)
1696         fprintf (fp, "    ");
1697       if (node->pred_right)
1698         {
1699           fprintf (fp, "right:\n");
1700           print_tree (fp, node->pred_right, indent + 1);
1701         }
1702       else
1703         {
1704           fprintf (fp, "no right.\n");
1705         }
1706     }
1707 }