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 = (struct predicate *) 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   for (i=1u; i<members; ++i)
 977     {
 978       const struct pred_cost_lookup *pl1 = (const struct pred_cost_lookup*)(p+(i-1)*membersize);
 979       const struct pred_cost_lookup *pl2 = (const struct pred_cost_lookup*)(p+(i-0)*membersize);
 980       assert(pl1->fn <= pl2->fn);
 981     }
 982   return true;
 983 }
 984
 985 \f
 986 static int
 987 cost_table_comparison(const void *p1, const void *p2)
 988 {
 989   const struct pred_cost_lookup *pc1 = p1;
 990   const struct pred_cost_lookup *pc2 = p2;
 991
 992
 993   if (pc1->fn == pc2->fn)
 994     return 0;
 995   else if (pc1->fn > pc2->fn)
 996     return 1;
 997   else
 998     return -1;
 999 }
1000 \f
1001 static enum EvaluationCost
1002 get_pred_cost(const struct predicate *p)
1003 {
1004   enum EvaluationCost data_requirement_cost = NeedsNothing;
1005   enum EvaluationCost inherent_cost = NeedsUnknown;
1006
1007   if (p->need_stat)
1008     {
1009       data_requirement_cost = NeedsStatInfo;
1010     }
1011   else if (p->need_type)
1012     {
1013       data_requirement_cost = NeedsType;
1014     }
1015   else
1016     {
1017       data_requirement_cost = NeedsNothing;
1018     }
1019
1020   if (pred_is(p, pred_exec) || pred_is(p, pred_execdir))
1021     {
1022       if (p->args.exec_vec.multiple)
1023         inherent_cost = NeedsEventualExec;
1024       else
1025         inherent_cost = NeedsImmediateExec;
1026     }
1027   else if (pred_is(p, pred_fprintf))
1028     {
1029       /* the parser calculated the cost for us. */
1030       inherent_cost = p->p_cost;
1031     }
1032   else
1033     {
1034       struct pred_cost_lookup key;
1035       void *entry;
1036
1037       if (!pred_table_sorted)
1038         {
1039           qsort(costlookup,
1040                 sizeof(costlookup)/sizeof(costlookup[0]),
1041                 sizeof(costlookup[0]),
1042                 cost_table_comparison);
1043
1044           if (!check_sorted(costlookup,
1045                             sizeof(costlookup)/sizeof(costlookup[0]),
1046                             sizeof(costlookup[0]),
1047                             cost_table_comparison))
1048             {
1049               error(1, 0, "Failed to sort the costlookup array.");
1050             }
1051           pred_table_sorted = 1;
1052         }
1053       key.fn = p->pred_func;
1054       entry = bsearch(&key, costlookup,
1055                       sizeof(costlookup)/sizeof(costlookup[0]),
1056                       sizeof(costlookup[0]),
1057                       cost_table_comparison);
1058       if (entry)
1059         {
1060           inherent_cost = ((const struct pred_cost_lookup*)entry)->cost;
1061         }
1062       else
1063         {
1064           error(0, 0, "warning: no cost entry for predicate %s", p->p_name);
1065           inherent_cost = NeedsUnknown;
1066         }
1067     }
1068
1069   if (inherent_cost > data_requirement_cost)
1070     return inherent_cost;
1071   else
1072     return data_requirement_cost;
1073 }
1074 \f
1075 static void
1076 estimate_costs (struct predicate *tree)
1077 {
1078   if (tree)
1079     {
1080       estimate_costs(tree->pred_right);
1081       estimate_costs(tree->pred_left);
1082
1083       tree->p_cost = get_pred_cost(tree);
1084     }
1085 }
1086
1087 struct predicate*
1088 get_eval_tree(void)
1089 {
1090   return eval_tree;
1091 }
1092
1093 static float
1094 getrate(const struct predicate *p)
1095 {
1096   if (p)
1097     return p->est_success_rate;
1098   else
1099     return 1.0f;
1100 }
1101
1102
1103 float
1104 calculate_derived_rates(struct predicate *p)
1105 {
1106   assert(NULL != p);
1107
1108   if (p->pred_right)
1109     calculate_derived_rates(p->pred_right);
1110   if (p->pred_left)
1111     calculate_derived_rates(p->pred_left);
1112
1113   assert(p->p_type != CLOSE_PAREN);
1114   assert(p->p_type != OPEN_PAREN);
1115
1116   switch (p->p_type)
1117     {
1118     case NO_TYPE:
1119       assert(NULL == p->pred_right);
1120       assert(NULL == p->pred_left);
1121       return p->est_success_rate;
1122
1123     case PRIMARY_TYPE:
1124       assert(NULL == p->pred_right);
1125       assert(NULL == p->pred_left);
1126       return p->est_success_rate;
1127
1128     case UNI_OP:
1129       /* Unary operators must have exactly one operand */
1130       assert(pred_is(p, pred_negate));
1131       assert(NULL == p->pred_left);
1132       p->est_success_rate = (1.0 - p->pred_right->est_success_rate);
1133       return p->est_success_rate;
1134
1135     case BI_OP:
1136       {
1137         float rate;
1138         /* Binary operators must have two operands */
1139         if (pred_is(p, pred_and))
1140           {
1141             rate = getrate(p->pred_right) * getrate(p->pred_left);
1142           }
1143         else if (pred_is(p, pred_comma))
1144           {
1145             rate = 1.0f;
1146           }
1147         else if (pred_is(p, pred_or))
1148           {
1149             rate = getrate(p->pred_right) + getrate(p->pred_left);
1150           }
1151         else
1152           {
1153             /* only and, or and comma are BI_OP. */
1154             assert(0);
1155             rate = 0.0f;
1156           }
1157         p->est_success_rate = constrain_rate(rate);
1158       }
1159       return p->est_success_rate;
1160
1161     case OPEN_PAREN:
1162     case CLOSE_PAREN:
1163       p->est_success_rate = 1.0;
1164       return p->est_success_rate;
1165     }
1166 }
1167 \f
1168 /* opt_expr() rearranges predicates such that each left subtree is
1169  * rooted at a logical predicate (e.g. and or or).  check_normalization()
1170  * asserts that this property still holds.
1171  *
1172  */
1173 static void check_normalization(struct predicate *p, boolean at_root)
1174 {
1175   if (at_root)
1176     {
1177       assert(BI_OP == p->p_type);
1178     }
1179
1180   if (p->pred_left)
1181     {
1182       assert(BI_OP == p->pred_left->p_type);
1183       check_normalization(p->pred_left, false);
1184     }
1185   if (p->pred_right)
1186     {
1187       check_normalization(p->pred_right, false);
1188     }
1189 }
1190 \f
1191 struct predicate*
1192 build_expression_tree(int argc, char *argv[], int end_of_leading_options)
1193 {
1194   const struct parser_table *parse_entry; /* Pointer to the parsing table entry for this expression. */
1195   char *predicate_name;         /* Name of predicate being parsed. */
1196   struct predicate *cur_pred;
1197   const struct parser_table *entry_close, *entry_print, *entry_open;
1198   int i, oldi;
1199
1200   predicates = NULL;
1201
1202   /* Find where in ARGV the predicates begin by skipping the list of
1203    * start points.
1204    */
1205   for (i = end_of_leading_options; i < argc && !looks_like_expression(argv[i], true); i++)
1206     {
1207       /* Do nothing. */ ;
1208     }
1209
1210   /* Enclose the expression in `( ... )' so a default -print will
1211      apply to the whole expression. */
1212   entry_open  = find_parser("(");
1213   entry_close = find_parser(")");
1214   entry_print = find_parser("print");
1215   assert(entry_open  != NULL);
1216   assert(entry_close != NULL);
1217   assert(entry_print != NULL);
1218
1219   parse_openparen (entry_open, argv, &argc);
1220   last_pred->p_name = "(";
1221   predicates->artificial = true;
1222   parse_begin_user_args(argv, argc, last_pred, predicates);
1223   pred_sanity_check(last_pred);
1224
1225   /* Build the input order list. */
1226   while (i < argc )
1227     {
1228       if (!looks_like_expression(argv[i], false))
1229         {
1230           error (0, 0, _("paths must precede expression: %s"), argv[i]);
1231           usage(stderr, 1, NULL);
1232         }
1233
1234       predicate_name = argv[i];
1235       parse_entry = find_parser (predicate_name);
1236       if (parse_entry == NULL)
1237         {
1238           /* Command line option not recognized */
1239           error (1, 0, _("unknown predicate `%s'"), predicate_name);
1240         }
1241
1242       /* We have recognised a test of the form -foo.  Eat that,
1243        * unless it is a predicate like -newerXY.
1244        */
1245       if (parse_entry->type != ARG_SPECIAL_PARSE)
1246         {
1247           i++;
1248         }
1249       oldi = i;
1250       if (!(*(parse_entry->parser_func)) (parse_entry, argv, &i))
1251         {
1252           if (argv[i])
1253             {
1254               if ( (ARG_SPECIAL_PARSE == parse_entry->type) && (i == oldi) )
1255                 {
1256                   /* The special parse function spat out the
1257                    * predicate.  It must be invalid, or not tasty.
1258                    */
1259                   error (1, 0, _("invalid predicate `%s'"),
1260                          predicate_name);
1261                 }
1262               else
1263                 {
1264                   error (1, 0, _("invalid argument `%s' to `%s'"),
1265                          argv[i], predicate_name);
1266                 }
1267             }
1268           else
1269             {
1270               /* Command line option requires an argument */
1271               error (1, 0, _("missing argument to `%s'"), predicate_name);
1272             }
1273         }
1274       else
1275         {
1276           last_pred->p_name = predicate_name;
1277
1278           /* If the parser consumed an argument, save it. */
1279           if (i != oldi)
1280             last_pred->arg_text = argv[oldi];
1281           else
1282             last_pred->arg_text = NULL;
1283         }
1284       pred_sanity_check(last_pred);
1285       pred_sanity_check(predicates); /* XXX: expensive */
1286     }
1287   parse_end_user_args(argv, argc, last_pred, predicates);
1288   if (predicates->pred_next == NULL)
1289     {
1290       /* No predicates that do something other than set a global variable
1291          were given; remove the unneeded initial `(' and add `-print'. */
1292       cur_pred = predicates;
1293       predicates = last_pred = predicates->pred_next;
1294       free ((char *) cur_pred);
1295       parse_print (entry_print, argv, &argc);
1296       last_pred->p_name = "-print";
1297       pred_sanity_check(last_pred);
1298       pred_sanity_check(predicates); /* XXX: expensive */
1299     }
1300   else if (!default_prints (predicates->pred_next))
1301     {
1302       /* One or more predicates that produce output were given;
1303          remove the unneeded initial `('. */
1304       cur_pred = predicates;
1305       predicates = predicates->pred_next;
1306       pred_sanity_check(predicates); /* XXX: expensive */
1307       free ((char *) cur_pred);
1308     }
1309   else
1310     {
1311       /* `( user-supplied-expression ) -print'. */
1312       parse_closeparen (entry_close, argv, &argc);
1313       last_pred->p_name = ")";
1314       last_pred->artificial = true;
1315       pred_sanity_check(last_pred);
1316       parse_print (entry_print, argv, &argc);
1317       last_pred->p_name = "-print";
1318       last_pred->artificial = true;
1319       pred_sanity_check(last_pred);
1320       pred_sanity_check(predicates); /* XXX: expensive */
1321     }
1322
1323   if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1324     {
1325       fprintf (stderr, "Predicate List:\n");
1326       print_list (stderr, predicates);
1327     }
1328
1329   /* do a sanity check */
1330   pred_sanity_check(predicates);
1331
1332   /* Done parsing the predicates.  Build the evaluation tree. */
1333   cur_pred = predicates;
1334   eval_tree = get_expr (&cur_pred, NO_PREC, NULL);
1335   calculate_derived_rates(eval_tree);
1336
1337   /* Check if we have any left-over predicates (this fixes
1338    * Debian bug #185202).
1339    */
1340   if (cur_pred != NULL)
1341     {
1342       /* cur_pred->p_name is often NULL here */
1343       if (pred_is(cur_pred, pred_closeparen))
1344         {
1345           /* e.g. "find \( -true \) \)" */
1346           error (1, 0, _("you have too many ')'"));
1347         }
1348       else
1349         {
1350           if (cur_pred->p_name)
1351             error (1, 0, _("unexpected extra predicate '%s'"), cur_pred->p_name);
1352           else
1353             error (1, 0, _("unexpected extra predicate"));
1354         }
1355     }
1356
1357   if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1358     {
1359       fprintf (stderr, "Eval Tree:\n");
1360       print_tree (stderr, eval_tree, 0);
1361     }
1362
1363   estimate_costs(eval_tree);
1364
1365   /* Rearrange the eval tree in optimal-predicate order. */
1366   opt_expr (&eval_tree);
1367
1368   /* Check that the tree is in normalised order (opt_expr does this) */
1369   check_normalization(eval_tree, true);
1370
1371   do_arm_swaps(eval_tree);
1372
1373   /* Check that the tree is still in normalised order */
1374   check_normalization(eval_tree, true);
1375
1376   if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
1377     {
1378       fprintf (stderr, "Optimized Eval Tree:\n");
1379       print_tree (stderr, eval_tree, 0);
1380       fprintf (stderr, "Optimized command line:\n");
1381       print_optlist(stderr, eval_tree);
1382       fprintf(stderr, "\n");
1383     }
1384
1385   return eval_tree;
1386 }
1387 \f
1388 /* Initialise the performance data for a predicate.
1389  */
1390 static void
1391 init_pred_perf(struct predicate *pred)
1392 {
1393   struct predicate_performance_info *p = &pred->perf;
1394   p->visits = p->successes = 0;
1395 }
1396
1397 \f
1398 /* Return a pointer to a new predicate structure, which has been
1399    linked in as the last one in the predicates list.
1400
1401    Set `predicates' to point to the start of the predicates list.
1402    Set `last_pred' to point to the new last predicate in the list.
1403
1404    Set all cells in the new structure to the default values. */
1405
1406 struct predicate *
1407 get_new_pred (const struct parser_table *entry)
1408 {
1409   register struct predicate *new_pred;
1410   (void) entry;
1411
1412   /* Options should not be turned into predicates. */
1413   assert(entry->type != ARG_OPTION);
1414   assert(entry->type != ARG_POSITIONAL_OPTION);
1415
1416   if (predicates == NULL)
1417     {
1418       predicates = (struct predicate *)
1419         xmalloc (sizeof (struct predicate));
1420       last_pred = predicates;
1421     }
1422   else
1423     {
1424       new_pred = (struct predicate *) xmalloc (sizeof (struct predicate));
1425       last_pred->pred_next = new_pred;
1426       last_pred = new_pred;
1427     }
1428   last_pred->parser_entry = entry;
1429   last_pred->pred_func = NULL;
1430   last_pred->p_name = NULL;
1431   last_pred->p_type = NO_TYPE;
1432   last_pred->p_prec = NO_PREC;
1433   last_pred->side_effects = false;
1434   last_pred->no_default_print = false;
1435   last_pred->need_stat = true;
1436   last_pred->need_type = true;
1437   last_pred->args.str = NULL;
1438   last_pred->pred_next = NULL;
1439   last_pred->pred_left = NULL;
1440   last_pred->pred_right = NULL;
1441   last_pred->literal_control_chars = options.literal_control_chars;
1442   last_pred->artificial = false;
1443   last_pred->est_success_rate = 1.0;
1444   init_pred_perf(last_pred);
1445   return last_pred;
1446 }
1447 \f
1448 /* Return a pointer to a new predicate, with operator check.
1449    Like get_new_pred, but it checks to make sure that the previous
1450    predicate is an operator.  If it isn't, the AND operator is inserted. */
1451
1452 struct predicate *
1453 get_new_pred_chk_op (const struct parser_table *entry)
1454 {
1455   struct predicate *new_pred;
1456   static const struct parser_table *entry_and = NULL;
1457
1458   /* Locate the entry in the parser table for the "and" operator */
1459   if (NULL == entry_and)
1460     entry_and = find_parser("and");
1461
1462   /* Check that it's actually there. If not, that is a bug.*/
1463   assert(entry_and != NULL);
1464
1465   if (last_pred)
1466     switch (last_pred->p_type)
1467       {
1468       case NO_TYPE:
1469         error (1, 0, _("oops -- invalid default insertion of and!"));
1470         break;
1471
1472       case PRIMARY_TYPE:
1473       case CLOSE_PAREN:
1474         /* We need to interpose the and operator. */
1475         new_pred = get_new_pred (entry_and);
1476         new_pred->pred_func = pred_and;
1477         new_pred->p_name = "-a";
1478         new_pred->p_type = BI_OP;
1479         new_pred->p_prec = AND_PREC;
1480         new_pred->need_stat = false;
1481         new_pred->need_type = false;
1482         new_pred->args.str = NULL;
1483         new_pred->side_effects = false;
1484         new_pred->no_default_print = false;
1485         break;
1486
1487       default:
1488         break;
1489       }
1490
1491   new_pred = get_new_pred (entry);
1492   new_pred->parser_entry = entry;
1493   return new_pred;
1494 }
1495 \f
1496 struct cost_assoc
1497 {
1498   enum EvaluationCost cost;
1499   char *name;
1500 };
1501 struct cost_assoc cost_table[] =
1502   {
1503     { NeedsNothing,         "Nothing" },
1504     { NeedsType,            "Type" },
1505     { NeedsStatInfo,        "StatInfo" },
1506     { NeedsLinkName,        "LinkName" },
1507     { NeedsAccessInfo,      "AccessInfo" },
1508     { NeedsSyncDiskHit,     "SyncDiskHit" },
1509     { NeedsEventualExec,    "EventualExec" },
1510     { NeedsImmediateExec,   "ImmediateExec" },
1511     { NeedsUserInteraction, "UserInteraction" },
1512     { NeedsUnknown,         "Unknown" }
1513   };
1514 \f
1515 struct prec_assoc
1516 {
1517   short prec;
1518   char *prec_name;
1519 };
1520
1521 static struct prec_assoc prec_table[] =
1522 {
1523   {NO_PREC, "no"},
1524   {COMMA_PREC, "comma"},
1525   {OR_PREC, "or"},
1526   {AND_PREC, "and"},
1527   {NEGATE_PREC, "negate"},
1528   {MAX_PREC, "max"},
1529   {-1, "unknown "}
1530 };
1531 \f
1532 struct op_assoc
1533 {
1534   short type;
1535   char *type_name;
1536 };
1537
1538 static struct op_assoc type_table[] =
1539 {
1540   {NO_TYPE,      "no"},
1541   {PRIMARY_TYPE, "primary"},
1542   {UNI_OP,       "uni_op"},
1543   {BI_OP,        "bi_op"},
1544   {OPEN_PAREN,   "open_paren  "},
1545   {CLOSE_PAREN,  "close_paren "},
1546   {-1,           "unknown"}
1547 };
1548 \f
1549 static const char *
1550 cost_name (enum EvaluationCost cost)
1551 {
1552   unsigned int i;
1553   unsigned int n = sizeof(cost_table)/sizeof(cost_table[0]);
1554
1555   for (i = 0; i<n; ++i)
1556     if (cost_table[i].cost == cost)
1557       return cost_table[i].name;
1558   return "unknown";
1559 }
1560 \f
1561
1562 static char *
1563 type_name (type)
1564      short type;
1565 {
1566   int i;
1567
1568   for (i = 0; type_table[i].type != (short) -1; i++)
1569     if (type_table[i].type == type)
1570       break;
1571   return (type_table[i].type_name);
1572 }
1573 \f
1574 static char *
1575 prec_name (prec)
1576      short prec;
1577 {
1578   int i;
1579
1580   for (i = 0; prec_table[i].prec != (short) -1; i++)
1581     if (prec_table[i].prec == prec)
1582       break;
1583   return (prec_table[i].prec_name);
1584 }
1585
1586 \f
1587 /* Walk the expression tree NODE to stdout.
1588    INDENT is the number of levels to indent the left margin. */
1589
1590 void
1591 print_tree (FILE *fp, struct predicate *node, int indent)
1592 {
1593   int i;
1594
1595   if (node == NULL)
1596     return;
1597   for (i = 0; i < indent; i++)
1598     fprintf (fp, "    ");
1599   fprintf (fp, "pred=[");
1600   print_predicate(fp, node);
1601   fprintf (fp, "] type=%s prec=%s",
1602           type_name (node->p_type), prec_name (node->p_prec));
1603   fprintf (fp, " cost=%s rate=%#03.2g %sside effects ",
1604            cost_name(node->p_cost),
1605            node->est_success_rate,
1606            (node->side_effects ? "" : "no "));
1607
1608   if (node->need_stat || node->need_type)
1609     {
1610       int comma = 0;
1611
1612       fprintf (fp, "Needs ");
1613       if (node->need_stat)
1614         {
1615           fprintf (fp, "stat");
1616           comma = 1;
1617         }
1618       if (node->need_type)
1619         {
1620           fprintf (fp, "%stype", comma ? "," : "");
1621         }
1622     }
1623   fprintf (fp, "\n");
1624
1625
1626   for (i = 0; i < indent; i++)
1627     fprintf (fp, "    ");
1628   if (NULL == node->pred_left && NULL == node->pred_right)
1629     {
1630       fprintf (fp, "no children.\n");
1631     }
1632   else
1633     {
1634       if (node->pred_left)
1635         {
1636           fprintf (fp, "left:\n");
1637           print_tree (fp, node->pred_left, indent + 1);
1638         }
1639       else
1640         {
1641           fprintf (fp, "no left.\n");
1642         }
1643
1644       for (i = 0; i < indent; i++)
1645         fprintf (fp, "    ");
1646       if (node->pred_right)
1647         {
1648           fprintf (fp, "right:\n");
1649           print_tree (fp, node->pred_right, indent + 1);
1650         }
1651       else
1652         {
1653           fprintf (fp, "no right.\n");
1654         }
1655     }
1656 }