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