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