← Back to branch summary

~ubuntu-branches/ubuntu/raring/findutils/raring

« back to all changes in this revision

Viewing changes to find/tree.c

  • Committer: Bazaar Package Importer
  • Author(s): Michael Vogt
  • Date: 2008-05-06 11:32:24 UTC
  • mfrom: (1.2.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 23.
  • Revision ID: james.westby@ubuntu.com-20080506113224-gy4ecmxu48tnvva4
Tags: upstream-4.4.0
Import upstream version 4.4.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
find/tree.c
1
1
/* tree.c -- helper functions to build and evaluate the expression tree.
2
 
   Copyright (C) 1990, 91, 92, 93, 94, 2000, 2001, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
 
2
   Copyright (C) 1990, 91, 92, 93, 94, 2000, 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3
3
 
4
4
   This program is free software: you can redistribute it and/or modify
5
5
   it under the terms of the GNU General Public License as published by
15
15
   along with this program.  If not, see <http://www.gnu.org/licenses/>.
16
16
*/
17
17
 
 
18
#include <config.h>
18
19
#include "defs.h"
19
 
#include "../gnulib/lib/xalloc.h"
 
20
 
 
21
#include <assert.h>
 
22
#include <stdlib.h>
 
23
 
 
24
#include "xalloc.h"
 
25
#include "error.h"
 
26
 
20
27
 
21
28
#if ENABLE_NLS
22
29
# include <libintl.h>
31
38
# define N_(String) String
32
39
#endif
33
40
 
 
41
 
 
42
 
 
43
/* All predicates for each path to process. */
 
44
static struct predicate *predicates = NULL;
 
45
 
 
46
/* The root of the evaluation tree. */
 
47
static struct predicate *eval_tree  = NULL;
 
48
 
 
49
/* The last predicate allocated. */
 
50
static struct predicate *last_pred = NULL;
 
51
 
 
52
 
34
53
static struct predicate *scan_rest PARAMS((struct predicate **input,
35
54
                                       struct predicate *head,
36
55
                                       short int prev_prec));
37
56
static void merge_pred PARAMS((struct predicate *beg_list, struct predicate *end_list, struct predicate **last_p));
38
57
static struct predicate *set_new_parent PARAMS((struct predicate *curr, enum predicate_precedence high_prec, struct predicate **prevp));
 
58
static const char *cost_name PARAMS((enum EvaluationCost cost));
 
59
 
39
60
 
40
61
/* Return a pointer to a tree that represents the
41
62
   expression prior to non-unary operator *INPUT.
57
78
   our caller, so get_expr recurses. */
58
79
 
59
80
struct predicate *
60
 
get_expr (struct predicate **input, short int prev_prec)
 
81
get_expr (struct predicate **input,
 
82
          short int prev_prec,
 
83
          const struct predicate* prev_pred)
61
84
{
62
85
  struct predicate *next = NULL;
 
86
  struct predicate *this_pred = (*input);
63
87
 
64
88
  if (*input == NULL)
65
89
    error (1, 0, _("invalid expression"));
71
95
      break;
72
96
 
73
97
    case BI_OP:
74
 
      error (1, 0, _("invalid expression; you have used a binary operator with nothing before it."));
 
98
      /* e.g. "find . -a" */
 
99
      error (1, 0, _("invalid expression; you have used a binary operator '%s' with nothing before it."), this_pred->p_name);
75
100
      break;
76
101
 
77
102
    case CLOSE_PAREN:
78
 
      error (1, 0, _("invalid expression; you have too many ')'"));
 
103
      if ((UNI_OP == prev_pred->p_type
 
104
          || BI_OP == prev_pred->p_type)
 
105
          && !this_pred->artificial)
 
106
        {
 
107
          /* e.g. "find \( -not \)" or "find \( -true -a \" */
 
108
          error(1, 0, _("expected an expression between '%s' and ')'"),
 
109
                prev_pred->p_name);
 
110
        }
 
111
      else if ( (*input)->artificial )
 
112
        {
 
113
          /* We have reached the end of the user-supplied predicates
 
114
           * unexpectedly. 
 
115
           */
 
116
          /* e.g. "find . -true -a" */
 
117
          error (1, 0, _("expected an expression after '%s'"), prev_pred->p_name);
 
118
        }
 
119
      else
 
120
        {
 
121
          error (1, 0, _("invalid expression; you have too many ')'"));
 
122
        }
79
123
      break;
80
124
 
81
125
    case PRIMARY_TYPE:
86
130
    case UNI_OP:
87
131
      next = *input;
88
132
      *input = (*input)->pred_next;
89
 
      next->pred_right = get_expr (input, NEGATE_PREC);
 
133
      next->pred_right = get_expr (input, NEGATE_PREC, next);
90
134
      break;
91
135
 
92
136
    case OPEN_PAREN:
 
137
      if ( (NULL == (*input)->pred_next) || (*input)->pred_next->artificial )
 
138
        {
 
139
          /* user typed something like "find . (", and so the ) we are
 
140
           * looking at is from the artificial "( ) -print" that we
 
141
           * add.
 
142
           */
 
143
          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);
 
144
        }
 
145
      prev_pred = (*input);
93
146
      *input = (*input)->pred_next;
94
 
      next = get_expr (input, NO_PREC);
 
147
      if ( (*input)->p_type == CLOSE_PAREN )
 
148
        {
 
149
          error (1, 0, _("invalid expression; empty parentheses are not allowed."));
 
150
        }
 
151
      next = get_expr (input, NO_PREC, prev_pred);
95
152
      if ((*input == NULL)
96
153
          || ((*input)->p_type != CLOSE_PAREN))
97
154
        error (1, 0, _("invalid expression; I was expecting to find a ')' somewhere but did not see one."));
98
155
      *input = (*input)->pred_next;     /* move over close */
99
156
      break;
100
 
 
 
157
      
101
158
    default:
102
159
      error (1, 0, _("oops -- invalid expression type!"));
103
160
      break;
157
214
          break;
158
215
 
159
216
        case BI_OP:
160
 
          (*input)->pred_left = tree;
161
 
          tree = *input;
162
 
          *input = (*input)->pred_next;
163
 
          tree->pred_right = get_expr (input, tree->p_prec);
164
 
          break;
 
217
          {
 
218
            struct predicate *prev = (*input);
 
219
            (*input)->pred_left = tree;
 
220
            tree = *input;
 
221
            *input = (*input)->pred_next;
 
222
            tree->pred_right = get_expr (input, tree->p_prec, prev);
 
223
            break;
 
224
          }
165
225
 
166
226
        case CLOSE_PAREN:
167
227
          return tree;
176
236
  return tree;
177
237
}
178
238
 
 
239
/* Returns true if the specified predicate is reorderable. */
 
240
static boolean
 
241
predicate_is_cost_free(const struct predicate *p)
 
242
{
 
243
  if (pred_is(p, pred_name) ||
 
244
      pred_is(p, pred_path) ||
 
245
      pred_is(p, pred_iname) ||
 
246
      pred_is(p, pred_ipath))
 
247
    {
 
248
      /* Traditionally (at least 4.1.7 through 4.2.x) GNU find always
 
249
       * optimised these cases.
 
250
       */
 
251
      return true;
 
252
    }
 
253
  else if (options.optimisation_level > 0)
 
254
    {
 
255
      if (pred_is(p, pred_and) ||
 
256
          pred_is(p, pred_negate) ||
 
257
          pred_is(p, pred_comma) ||
 
258
          pred_is(p, pred_or))
 
259
        return false;
 
260
      else
 
261
        return NeedsNothing == p->p_cost;
 
262
    }
 
263
  else
 
264
    {
 
265
      return false;
 
266
    }
 
267
}
 
268
 
 
269
/* Prints a predicate */
 
270
void print_predicate(FILE *fp, const struct predicate *p)
 
271
{
 
272
  fprintf (fp, "%s%s%s",
 
273
           p->p_name,
 
274
           p->arg_text ? " " : "",
 
275
           p->arg_text ? p->arg_text : "");
 
276
}
 
277
 
 
278
 
 
279
struct predlist 
 
280
{
 
281
  struct predicate *head;
 
282
  struct predicate *tail;
 
283
};
 
284
 
 
285
static void
 
286
predlist_init(struct predlist *p)
 
287
{
 
288
  p->head = p->tail = NULL;
 
289
}
 
290
 
 
291
static void
 
292
predlist_insert(struct predlist *list,
 
293
                struct predicate *curr,
 
294
                struct predicate **pprev)
 
295
{
 
296
  struct predicate **insertpos = &(list->head);
 
297
  
 
298
  *pprev = curr->pred_left;
 
299
  if (options.optimisation_level > 2)
 
300
    {
 
301
      /* Insert the new node in the list after any other entries which
 
302
       * are more selective.
 
303
       */
 
304
      if (0)
 
305
        while ( (*insertpos) && ((*insertpos)->est_success_rate < curr->est_success_rate) )
 
306
          {
 
307
            insertpos = &((*insertpos)->pred_left);
 
308
          }
 
309
    }
 
310
  curr->pred_left = (*insertpos);
 
311
  (*insertpos) = curr;
 
312
  if (NULL == list->tail)
 
313
    list->tail = list->head;
 
314
}
 
315
 
 
316
static int
 
317
pred_cost_compare(const struct predicate *p1, const struct predicate *p2, boolean wantfailure)
 
318
{
 
319
  if (p1->p_cost == p2->p_cost)
 
320
    {
 
321
      if (p1->est_success_rate == p2->est_success_rate)
 
322
        return 0;
 
323
      else if (wantfailure)
 
324
        return p1->est_success_rate < p2->est_success_rate ? -1 :  1;
 
325
      else
 
326
        return p1->est_success_rate < p2->est_success_rate ?  1 : -1;
 
327
    }
 
328
  else 
 
329
    {
 
330
      return p1->p_cost < p2->p_cost ? -1 : 1;
 
331
    }
 
332
}
 
333
 
 
334
 
 
335
static void 
 
336
predlist_merge_sort(struct predlist *list,
 
337
                    struct predicate **last)
 
338
{
 
339
  struct predlist new_list;
 
340
  struct predicate *p, *q;
 
341
 
 
342
  if (NULL == list->head)
 
343
    return;                     /* nothing to do */
 
344
 
 
345
  if (options.debug_options & DebugTreeOpt)
 
346
    {
 
347
      fprintf(stderr, "%s:\n", "predlist before merge sort");
 
348
      print_tree(stderr, list->head, 2);
 
349
    }
 
350
  
 
351
  calculate_derived_rates(list->head);
 
352
  predlist_init(&new_list);
 
353
  while (list->head)
 
354
    {
 
355
      /* remove head of source list */
 
356
      q = list->head;
 
357
      list->head = list->head->pred_left;
 
358
      q->pred_left = NULL;
 
359
 
 
360
      /* insert it into the new list */
 
361
      for (p=new_list.head; p; p=p->pred_left)
 
362
        {
 
363
          /* If these operations are OR operations, we want to get a
 
364
           * successful test as soon as possible, to take advantage of
 
365
           * the short-circuit evaluation.  If they're AND, we want to
 
366
           * get an unsuccessful result early for the same reason.
 
367
           * Therefore we invert the sense of the comparison for the
 
368
           * OR case.  We only want to invert the sense of the success
 
369
           * rate comparison, not the operation cost comparison.  Hence we 
 
370
           * pass a flag into pred_cost_compare().
 
371
           */
 
372
          boolean wantfailure = (OR_PREC != p->p_prec);
 
373
          if (pred_cost_compare(p->pred_right, q->pred_right, wantfailure) >= 0)
 
374
            break;
 
375
        }
 
376
      if (p)
 
377
        {
 
378
          /* insert into existing list */
 
379
          q->pred_left = p->pred_left;
 
380
          if (NULL == q->pred_left)
 
381
            new_list.tail = q;
 
382
          p->pred_left = q;
 
383
        }
 
384
      else 
 
385
        {
 
386
          q->pred_left = new_list.head; /* prepend */
 
387
          new_list.head = q;
 
388
          if (NULL == new_list.tail)
 
389
            new_list.tail = q; /* first item in new list */
 
390
        }
 
391
    }
 
392
  if (options.debug_options & DebugTreeOpt)
 
393
    {
 
394
      fprintf(stderr, "%s:\n", "predlist after merge sort");
 
395
      print_tree(stderr, new_list.head, 2);
 
396
    }
 
397
  
 
398
  calculate_derived_rates(new_list.head);
 
399
  merge_pred(new_list.head, new_list.tail, last);
 
400
  predlist_init(list);
 
401
}
 
402
 
 
403
static void 
 
404
merge_lists(struct predlist lists[], int nlists,
 
405
            struct predlist *name_list,
 
406
            struct predlist *regex_list,
 
407
            struct predicate **last)
 
408
{
 
409
  int i;
 
410
  static void (*mergefn)(struct predlist *, struct predicate**);
 
411
 
 
412
  mergefn = predlist_merge_sort;
 
413
  
 
414
  mergefn(name_list,   last);
 
415
  mergefn(regex_list,  last);
 
416
  
 
417
  for (i=0; i<nlists; i++)
 
418
    mergefn(&lists[i], last);
 
419
}
 
420
 
 
421
 
 
422
 
 
423
static boolean 
 
424
subtree_has_side_effects(const struct predicate *p)
 
425
{
 
426
  if (p)
 
427
    {
 
428
      return p->side_effects
 
429
        || subtree_has_side_effects(p->pred_left)
 
430
        || subtree_has_side_effects(p->pred_right);
 
431
    }
 
432
  else
 
433
    {
 
434
 
 
435
      return false;
 
436
    }
 
437
}
 
438
 
 
439
static int
 
440
worst_cost (const struct predicate *p)
 
441
{
 
442
  if (p)
 
443
    {
 
444
      unsigned int cost_r, cost_l, worst;
 
445
      cost_l = worst_cost(p->pred_left);
 
446
      cost_r = worst_cost(p->pred_right);
 
447
      worst = (cost_l > cost_r) ? cost_l : cost_r;
 
448
      if (worst < p->p_cost)
 
449
        worst = p->p_cost;
 
450
      return worst;
 
451
    }
 
452
  else
 
453
    {
 
454
      return 0;
 
455
    }
 
456
}
 
457
 
 
458
 
 
459
 
 
460
static void
 
461
perform_arm_swap(struct predicate *p)
 
462
{
 
463
  struct predicate *tmp = p->pred_left->pred_right;
 
464
  p->pred_left->pred_right = p->pred_right;
 
465
  p->pred_right = tmp;
 
466
}
 
467
 
 
468
/* Consider swapping p->pred_left->pred_right with p->pred_right, 
 
469
 * if that yields a faster evaluation.   Normally the left predicate is 
 
470
 * evaluated first.
 
471
 *
 
472
 * If the operation is an OR, we want the left predicate to be the one that 
 
473
 * succeeds most often.   If it is an AND, we want it to be the predicate that 
 
474
 * fails most often.
 
475
 *
 
476
 * We don't consider swapping arms of an operator where their cost is
 
477
 * different or where they have side effects.
 
478
 *
 
479
 * A viable test case for this is 
 
480
 * ./find -D opt   -O3  .   \! -type f -o -type d
 
481
 * Here, the ! -type f should be evaluated first,
 
482
 * as we assume that 95% of inodes are vanilla files.
 
483
 */
 
484
static boolean
 
485
consider_arm_swap(struct predicate *p)
 
486
{
 
487
  int left_cost, right_cost;
 
488
  const char *reason = NULL;
 
489
  struct predicate **pl, **pr;
 
490
 
 
491
  if (BI_OP != p->p_type)
 
492
    reason = "Not a binary operation";
 
493
 
 
494
  if (!reason)
 
495
    {
 
496
      if (NULL == p->pred_left || NULL == p->pred_right)
 
497
        reason = "Doesn't have two arms";
 
498
    }
 
499
 
 
500
  
 
501
  if (!reason)
 
502
    {
 
503
      if (NULL == p->pred_left->pred_right)
 
504
        reason = "Left arm has no child on RHS";
 
505
    }
 
506
  pr = &p->pred_right;
 
507
  pl = &p->pred_left->pred_right;
 
508
  
 
509
  if (!reason)
 
510
    {
 
511
      if (subtree_has_side_effects(*pl))
 
512
        reason = "Left subtree has side-effects";
 
513
    }
 
514
  if (!reason)
 
515
    {
 
516
      if (subtree_has_side_effects(*pr))
 
517
        reason = "Right subtree has side-effects";
 
518
    }
 
519
 
 
520
  if (!reason)
 
521
    {
 
522
      left_cost = worst_cost(*pl);
 
523
      right_cost = worst_cost(*pr);
 
524
      
 
525
      if (left_cost < right_cost)
 
526
        {
 
527
          reason = "efficient as-is";
 
528
        }
 
529
    }
 
530
  if (!reason)
 
531
    {
 
532
      boolean want_swap;
 
533
      
 
534
      if (left_cost == right_cost)
 
535
        {
 
536
          /* it's a candidate */
 
537
          float succ_rate_l = (*pl)->est_success_rate;
 
538
          float succ_rate_r = (*pr)->est_success_rate;
 
539
 
 
540
          if (options.debug_options & DebugTreeOpt)
 
541
            {
 
542
              fprintf(stderr, "Success rates: l=%f, r=%f\n", succ_rate_l, succ_rate_r);
 
543
            }
 
544
          
 
545
          if (pred_is(p, pred_or))
 
546
            {
 
547
              want_swap = succ_rate_r < succ_rate_l;
 
548
              if (!want_swap)
 
549
                reason = "Operation is OR and right success rate >= left";
 
550
            }
 
551
          else if (pred_is(p, pred_and))
 
552
            {
 
553
              want_swap = succ_rate_r > succ_rate_l;
 
554
              if (!want_swap)
 
555
                reason = "Operation is AND and right success rate <= left";
 
556
            }
 
557
          else
 
558
            {
 
559
              want_swap = false;
 
560
              reason = "Not AND or OR";
 
561
            }
 
562
        }
 
563
      else 
 
564
        {
 
565
          want_swap = true;
 
566
        }
 
567
      
 
568
      if (want_swap)
 
569
        {
 
570
          if (options.debug_options & DebugTreeOpt)
 
571
            {
 
572
              fprintf(stderr, "Performing arm swap on:\n");
 
573
              print_tree (stderr, p, 0);
 
574
            }
 
575
          perform_arm_swap(p);
 
576
          return true;
 
577
        }
 
578
    }
 
579
      
 
580
 
 
581
  if (options.debug_options & DebugTreeOpt)
 
582
    {
 
583
      fprintf(stderr, "Not an arm swap candidate (%s):\n", reason);
 
584
      print_tree (stderr, p, 0);
 
585
    }
 
586
  return false;
 
587
}
 
588
 
 
589
static boolean
 
590
do_arm_swaps(struct predicate *p)
 
591
{
 
592
  if (p)
 
593
    {
 
594
      boolean swapped;
 
595
      do 
 
596
        {
 
597
          swapped = false;
 
598
          if (consider_arm_swap(p)
 
599
              || do_arm_swaps(p->pred_left)
 
600
              || do_arm_swaps(p->pred_right))
 
601
            {
 
602
              swapped = true;
 
603
            }
 
604
        } while (swapped);
 
605
      return swapped;
 
606
    }
 
607
  else
 
608
    {
 
609
      return false;
 
610
    }
 
611
}
 
612
 
 
613
 
 
614
 
179
615
/* Optimize the ordering of the predicates in the tree.  Rearrange
180
616
   them to minimize work.  Strategies:
181
617
   * Evaluate predicates that don't need inode information first;
190
626
     of a group by definition do not have side effects.  Both
191
627
     -regex and -iregex both use pred_regex.
192
628
 
 
629
     If higher optimisation levels have been selected, reordering also
 
630
     occurs according to the p_cost member of each predicate (which
 
631
     reflects the performance cost of the test).  The ordering also
 
632
     bears in mind whether these operations are more likely to succeed
 
633
     or fail.  When evauating a chain of OR conditions, we prefer
 
634
     tests likely to succeed at the front of the list.  For AND, we
 
635
     prefer tests likely to fail at the front of the list.
 
636
     
193
637
     This routine "normalizes" the predicate tree by ensuring that
194
638
     all expression predicates have AND (or OR or COMMA) parent nodes
195
639
     which are linked along the left edge of the expression tree.
199
643
     to be rearranged.  opt_expr may return a new root pointer there.
200
644
     Return true if the tree contains side effects, false if not. */
201
645
 
202
 
boolean
 
646
static boolean
203
647
opt_expr (struct predicate **eval_treep)
204
648
{
205
 
  /* List of -name and -path predicates to move. */
206
 
  struct predicate *name_list = NULL;
207
 
  struct predicate *end_name_list = NULL;
208
 
  /* List of -regex predicates to move. */
209
 
  struct predicate *regex_list = NULL;
210
 
  struct predicate *end_regex_list = NULL;
 
649
  struct predlist regex_list={NULL,NULL}, name_list={NULL,NULL};
 
650
  struct predlist cbo_list[NumEvaluationCosts];
 
651
  int i;
211
652
  struct predicate *curr;
212
653
  struct predicate **prevp;     /* Address of `curr' node. */
213
654
  struct predicate **last_sidep; /* Last predicate with side effects. */
217
658
  enum predicate_precedence prev_prec, /* precedence of last BI_OP in branch */
218
659
                            biop_prec; /* topmost BI_OP precedence in branch */
219
660
 
220
 
 
221
661
  if (eval_treep == NULL || *eval_treep == NULL)
222
662
    return (false);
223
663
 
 
664
  for (i=0; i<NumEvaluationCosts; i++)
 
665
    predlist_init(&cbo_list[i]);
 
666
  
224
667
  /* Set up to normalize tree as a left-linked list of ANDs or ORs.
225
668
     Set `curr' to the leftmost node, `prevp' to its address, and
226
669
     `pred_func' to the predicate type of its parent. */
238
681
  if (curr->p_type != BI_OP)
239
682
    set_new_parent (curr, prev_prec, prevp);
240
683
  
241
 
#ifdef DEBUG
242
 
  /* Normalized tree. */
243
 
  fprintf (stderr, "Normalized Eval Tree:\n");
244
 
  print_tree (stderr, *eval_treep, 0);
245
 
#endif
246
 
 
 
684
  if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
 
685
    {
 
686
      /* Normalized tree. */
 
687
      fprintf (stderr, "Normalized Eval Tree:\n");
 
688
      print_tree (stderr, *eval_treep, 0);
 
689
    }
 
690
  
247
691
  /* Rearrange the predicates. */
248
692
  prevp = eval_treep;
249
693
  biop_prec = NO_PREC; /* not COMMA_PREC */
267
711
      p_type = curr->pred_right->p_type;
268
712
      pred_func = curr->pred_right->pred_func;
269
713
 
 
714
 
270
715
      switch (p_type)
271
716
        {
272
717
        case NO_TYPE:
276
721
          if (biop_prec == COMMA_PREC)
277
722
            break;
278
723
 
279
 
          /* If it's one of our special primaries, move it to the
280
 
             front of the list for that primary. */
281
 
          if (pred_func == pred_name || pred_func == pred_path ||
282
 
              pred_func == pred_iname || pred_func == pred_ipath)
283
 
            {
284
 
              *prevp = curr->pred_left;
285
 
              curr->pred_left = name_list;
286
 
              name_list = curr;
287
 
 
288
 
              if (end_name_list == NULL)
289
 
                end_name_list = curr;
290
 
 
291
 
              continue;
292
 
            }
293
 
 
294
 
          if (pred_func == pred_regex)
295
 
            {
296
 
              *prevp = curr->pred_left;
297
 
              curr->pred_left = regex_list;
298
 
              regex_list = curr;
299
 
 
300
 
              if (end_regex_list == NULL)
301
 
                end_regex_list = curr;
302
 
 
303
 
              continue;
304
 
            }
305
 
 
 
724
          /* If this predicate has no side effects, consider reordering it. */
 
725
          if (!curr->pred_right->side_effects)            
 
726
            {
 
727
              boolean reorder;
 
728
              
 
729
              /* If it's one of our special primaries, move it to the
 
730
                 front of the list for that primary. */
 
731
              if (predicate_is_cost_free(curr->pred_right))
 
732
                {
 
733
                  if (options.debug_options & DebugTreeOpt)
 
734
                    {
 
735
                      fprintf(stderr, "-O%d: promoting cheap predicate ",
 
736
                              (int)options.optimisation_level);
 
737
                      print_predicate(stderr, curr->pred_right);
 
738
                      fprintf(stderr, " into name_list\n");
 
739
                    }
 
740
                  predlist_insert(&name_list, curr, prevp);
 
741
                  continue;
 
742
                }
 
743
              
 
744
              if (pred_func == pred_regex)
 
745
                {
 
746
                  predlist_insert(&regex_list, curr, prevp);
 
747
                  continue;
 
748
                }
 
749
 
 
750
              reorder = ((options.optimisation_level > 1)
 
751
                          && (NeedsType == curr->pred_right->p_cost)
 
752
                          && !curr->pred_right->need_stat) ||
 
753
                (options.optimisation_level > 2);
 
754
              
 
755
              if (reorder)
 
756
                {
 
757
                  if (options.debug_options & DebugTreeOpt)
 
758
                    {
 
759
                      fprintf(stderr, "-O%d: categorising predicate ",
 
760
                              (int)options.optimisation_level);
 
761
                      print_predicate(stderr, curr->pred_right);
 
762
                      fprintf(stderr, " by cost (%s)\n",
 
763
                              cost_name(curr->pred_right->p_cost));
 
764
                    }
 
765
                  predlist_insert(&cbo_list[curr->pred_right->p_cost], curr, prevp);
 
766
                  continue;
 
767
                }
 
768
            }
 
769
          
306
770
          break;
307
771
 
308
772
        case UNI_OP:
330
794
          last_sidep = prevp;
331
795
 
332
796
          /* Incorporate lists and reset list pointers for this group.  */
333
 
          if (name_list != NULL)
334
 
            {
335
 
              merge_pred (name_list, end_name_list, last_sidep);
336
 
              name_list = end_name_list = NULL;
337
 
            }
338
 
 
339
 
          if (regex_list != NULL)
340
 
            {
341
 
              merge_pred (regex_list, end_regex_list, last_sidep);
342
 
              regex_list = end_regex_list = NULL;
343
 
            }
344
 
 
 
797
          merge_lists(cbo_list, NumEvaluationCosts, &name_list, &regex_list, last_sidep);
345
798
          has_side_effects = true;
346
799
        }
347
800
 
350
803
 
351
804
  /* Do final list merges. */
352
805
  last_sidep = prevp;
353
 
  if (name_list != NULL)
354
 
    merge_pred (name_list, end_name_list, last_sidep);
355
 
  if (regex_list != NULL)
356
 
    merge_pred (regex_list, end_regex_list, last_sidep);
357
 
 
358
 
  return (has_side_effects);
359
 
}
360
 
 
 
806
  merge_lists(cbo_list, NumEvaluationCosts, &name_list, &regex_list, last_sidep);
 
807
  return has_side_effects;
 
808
}
 
809
 
 
810
static float
 
811
constrain_rate(float rate)
 
812
{
 
813
  if (rate > 1.0f)
 
814
    return 1.0;
 
815
  else if (rate < 0.0)
 
816
    return 0.0;
 
817
  else
 
818
    return rate;
 
819
}
 
820
 
361
821
/* Link in a new parent BI_OP node for CURR, at *PREVP, with precedence
362
822
   HIGH_PREC. */
363
823
 
366
826
{
367
827
  struct predicate *new_parent;
368
828
 
369
 
  new_parent = (struct predicate *) xmalloc (sizeof (struct predicate));
 
829
  new_parent = xmalloc (sizeof (struct predicate));
370
830
  new_parent->p_type = BI_OP;
371
831
  new_parent->p_prec = high_prec;
372
832
  new_parent->need_stat = false;
373
833
  new_parent->need_type = false;
374
 
 
 
834
  new_parent->p_cost = NeedsNothing;
 
835
  
375
836
  switch (high_prec)
376
837
    {
377
838
    case COMMA_PREC:
378
839
      new_parent->pred_func = pred_comma;
 
840
      new_parent->p_name = ",";
 
841
      new_parent->est_success_rate = 1.0;
379
842
      break;
380
843
    case OR_PREC:
381
844
      new_parent->pred_func = pred_or;
 
845
      new_parent->p_name = "-o";
 
846
      new_parent->est_success_rate = constrain_rate(curr->est_success_rate);
382
847
      break;
383
848
    case AND_PREC:
384
849
      new_parent->pred_func = pred_and;
 
850
      new_parent->p_name = "-a";
 
851
      new_parent->est_success_rate = constrain_rate(curr->est_success_rate);
385
852
      break;
386
853
    default:
387
854
      ;                         /* empty */
398
865
  new_parent->pred_right = curr;
399
866
  *prevp = new_parent;
400
867
 
401
 
#ifdef  DEBUG
402
 
  new_parent->p_name = (char *) find_pred_name (new_parent->pred_func);
403
 
#endif /* DEBUG */
404
 
 
405
 
  return (new_parent);
 
868
  return new_parent;
406
869
}
407
870
 
408
871
/* Merge the predicate list that starts at BEG_LIST and ends at END_LIST
425
888
   that a stat is made as late as possible.  Return true if the top node 
426
889
   in TREE requires a stat, false if not. */
427
890
 
428
 
boolean
429
 
mark_stat (struct predicate *tree)
430
 
{
431
 
  /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
432
 
     to find the first predicate for which the stat is needed. */
433
 
  switch (tree->p_type)
434
 
    {
435
 
    case NO_TYPE:
436
 
    case PRIMARY_TYPE:
437
 
      return tree->need_stat;
438
 
 
439
 
    case UNI_OP:
440
 
      if (mark_stat (tree->pred_right))
441
 
        tree->need_stat = true;
442
 
      return (false);
443
 
 
444
 
    case BI_OP:
445
 
      /* ANDs and ORs are linked along ->left ending in NULL. */
446
 
      if (tree->pred_left != NULL)
447
 
        mark_stat (tree->pred_left);
448
 
 
449
 
      if (mark_stat (tree->pred_right))
450
 
        tree->need_stat = true;
451
 
 
452
 
      return (false);
453
 
 
454
 
    default:
455
 
      error (1, 0, _("oops -- invalid expression type in mark_stat!"));
456
 
      return (false);
457
 
    }
458
 
}
459
 
 
460
 
/* Find the first node in expression tree TREE that we will
461
 
   need to know the file type, if any.   Operates in the same 
462
 
   was as mark_stat().
463
 
*/
464
 
boolean
465
 
mark_type (struct predicate *tree)
466
 
{
467
 
  /* The tree is executed in-order, so walk this way (apologies to Aerosmith)
468
 
     to find the first predicate for which the type information is needed. */
469
 
  switch (tree->p_type)
470
 
    {
471
 
    case NO_TYPE:
472
 
    case PRIMARY_TYPE:
473
 
      return tree->need_type;
474
 
 
475
 
    case UNI_OP:
476
 
      if (mark_type (tree->pred_right))
477
 
        tree->need_type = true;
478
 
      return false;
479
 
 
480
 
    case BI_OP:
481
 
      /* ANDs and ORs are linked along ->left ending in NULL. */
482
 
      if (tree->pred_left != NULL)
483
 
        mark_type (tree->pred_left);
484
 
 
485
 
      if (mark_type (tree->pred_right))
486
 
        tree->need_type = true;
487
 
 
488
 
      return false;
489
 
 
490
 
    default:
491
 
      error (1, 0, _("oops -- invalid expression type in mark_type!"));
492
 
      return (false);
493
 
    }
494
 
}
495
 
 
 
891
 
 
892
struct pred_cost_lookup
 
893
{
 
894
  PRED_FUNC             fn;
 
895
  enum EvaluationCost   cost;
 
896
};
 
897
static struct pred_cost_lookup costlookup[] = 
 
898
  {
 
899
    { pred_amin      ,  NeedsStatInfo        },
 
900
    { pred_and       ,  NeedsNothing,        },
 
901
    { pred_anewer    ,  NeedsStatInfo,       },
 
902
    { pred_atime     ,  NeedsStatInfo,       },
 
903
    { pred_closeparen,  NeedsNothing         },
 
904
    { pred_cmin      ,  NeedsStatInfo,       },
 
905
    { pred_cnewer    ,  NeedsStatInfo,       },
 
906
    { pred_comma     ,  NeedsNothing,        },
 
907
    { pred_ctime     ,  NeedsStatInfo,       },
 
908
    { pred_delete    ,  NeedsSyncDiskHit     },
 
909
    { pred_empty     ,  NeedsStatInfo        },
 
910
    { pred_exec      ,  NeedsEventualExec    },
 
911
    { pred_execdir   ,  NeedsEventualExec    },
 
912
    { pred_executable,  NeedsAccessInfo      },
 
913
    { pred_false     ,  NeedsNothing         }, 
 
914
    { pred_fprint    ,  NeedsNothing         }, 
 
915
    { pred_fprint0   ,  NeedsNothing         }, 
 
916
    { pred_fprintf   ,  NeedsNothing         }, 
 
917
    { pred_fstype    ,  NeedsStatInfo        }, /* true for amortised cost */
 
918
    { pred_gid       ,  NeedsStatInfo        },
 
919
    { pred_group     ,  NeedsStatInfo        },
 
920
    { pred_ilname    ,  NeedsLinkName        },
 
921
    { pred_iname     ,  NeedsNothing         },
 
922
    { pred_inum      ,  NeedsStatInfo        },
 
923
    { pred_ipath     ,  NeedsNothing         },
 
924
    { pred_links     ,  NeedsStatInfo        },
 
925
    { pred_lname     ,  NeedsLinkName        },
 
926
    { pred_ls        ,  NeedsStatInfo        },
 
927
    { pred_fls       ,  NeedsStatInfo        },
 
928
    { pred_mmin      ,  NeedsStatInfo        },
 
929
    { pred_mtime     ,  NeedsStatInfo        },
 
930
    { pred_name      ,  NeedsNothing         },
 
931
    { pred_negate    ,  NeedsNothing,        },
 
932
    { pred_newer     ,  NeedsStatInfo,       },
 
933
    { pred_newerXY   ,  NeedsStatInfo,       },
 
934
    { pred_nogroup   ,  NeedsStatInfo        }, /* true for amortised cost if caching is on */
 
935
    { pred_nouser    ,  NeedsStatInfo        }, /* true for amortised cost if caching is on */
 
936
    { pred_ok        ,  NeedsUserInteraction },
 
937
    { pred_okdir     ,  NeedsUserInteraction },
 
938
    { pred_openparen ,  NeedsNothing         },
 
939
    { pred_or        ,  NeedsNothing,        },
 
940
    { pred_path      ,  NeedsNothing         },
 
941
    { pred_perm      ,  NeedsStatInfo        },
 
942
    { pred_print     ,  NeedsNothing         },
 
943
    { pred_print0    ,  NeedsNothing         }, 
 
944
    { pred_prune     ,  NeedsNothing         },
 
945
    { pred_quit      ,  NeedsNothing         },
 
946
    { pred_readable  ,  NeedsAccessInfo      },
 
947
    { pred_regex     ,  NeedsNothing         },
 
948
    { pred_samefile  ,  NeedsStatInfo        },
 
949
    { pred_size      ,  NeedsStatInfo        },
 
950
    { pred_true      ,  NeedsNothing         },
 
951
    { pred_type      ,  NeedsType            },
 
952
    { pred_uid       ,  NeedsStatInfo        },
 
953
    { pred_used      ,  NeedsStatInfo        },
 
954
    { pred_user      ,  NeedsStatInfo        },
 
955
    { pred_writable  ,  NeedsAccessInfo      },
 
956
    { pred_xtype     ,  NeedsType            } /* roughly correct unless most files are symlinks */
 
957
  };
 
958
static int pred_table_sorted = 0;
 
959
 
 
960
static boolean
 
961
check_sorted(void *base, size_t members, size_t membersize,
 
962
             int (*cmpfn)(const void*, const void*))
 
963
{
 
964
  const char *p = base;
 
965
  size_t i;
 
966
  for (i=1u; i<members; ++i)
 
967
    {
 
968
      int result = cmpfn(p+i*membersize, p+(i-1)*membersize);
 
969
      if (result < 0)
 
970
        return false;
 
971
      result = cmpfn(p+(i-1)*membersize, p+i*membersize);
 
972
      assert (result <= 0);
 
973
    }
 
974
  return true;
 
975
}
 
976
 
 
977
 
 
978
static int
 
979
cost_table_comparison(const void *p1, const void *p2)
 
980
{
 
981
  /* We have to compare the function pointers with memcmp(), 
 
982
   * because ISO C does not allow magnitude comparison of 
 
983
   * function pointers (just equality testing).
 
984
   */
 
985
  const struct pred_cost_lookup *pc1 = p1;
 
986
  const struct pred_cost_lookup *pc2 = p2;
 
987
  union {
 
988
    PRED_FUNC pfn;
 
989
    char mem[sizeof (PRED_FUNC)];
 
990
  } u1, u2;
 
991
 
 
992
  u1.pfn = pc1->fn;
 
993
  u2.pfn = pc2->fn;
 
994
  return memcmp(u1.mem, u2.mem, sizeof(u1.pfn));
 
995
}
 
996
 
 
997
static enum EvaluationCost
 
998
get_pred_cost(const struct predicate *p)
 
999
{
 
1000
  enum EvaluationCost data_requirement_cost = NeedsNothing;
 
1001
  enum EvaluationCost inherent_cost = NeedsUnknown;
 
1002
 
 
1003
  if (p->need_stat)
 
1004
    {
 
1005
      data_requirement_cost = NeedsStatInfo;
 
1006
    }
 
1007
  else if (p->need_type)
 
1008
    {
 
1009
      data_requirement_cost = NeedsType;
 
1010
    }
 
1011
  else 
 
1012
    {
 
1013
      data_requirement_cost = NeedsNothing;
 
1014
    }
 
1015
  
 
1016
  if (pred_is(p, pred_exec) || pred_is(p, pred_execdir))
 
1017
    {
 
1018
      if (p->args.exec_vec.multiple)
 
1019
        inherent_cost = NeedsEventualExec;
 
1020
      else
 
1021
        inherent_cost = NeedsImmediateExec;
 
1022
    }
 
1023
  else if (pred_is(p, pred_fprintf))
 
1024
    {
 
1025
      /* the parser calculated the cost for us. */
 
1026
      inherent_cost = p->p_cost;
 
1027
    }
 
1028
  else 
 
1029
    {
 
1030
      struct pred_cost_lookup key;
 
1031
      void *entry;
 
1032
 
 
1033
      if (!pred_table_sorted)
 
1034
        {
 
1035
          qsort(costlookup,
 
1036
                sizeof(costlookup)/sizeof(costlookup[0]),
 
1037
                sizeof(costlookup[0]),
 
1038
                cost_table_comparison);
 
1039
 
 
1040
          if (!check_sorted(costlookup,
 
1041
                            sizeof(costlookup)/sizeof(costlookup[0]),
 
1042
                            sizeof(costlookup[0]),
 
1043
                            cost_table_comparison))
 
1044
            {
 
1045
              error(1, 0, "Failed to sort the costlookup array (indirect).");
 
1046
            }
 
1047
          pred_table_sorted = 1;
 
1048
        }
 
1049
      key.fn = p->pred_func;
 
1050
      entry = bsearch(&key, costlookup, 
 
1051
                      sizeof(costlookup)/sizeof(costlookup[0]),
 
1052
                      sizeof(costlookup[0]),
 
1053
                      cost_table_comparison);
 
1054
      if (entry)
 
1055
        {
 
1056
          inherent_cost = ((const struct pred_cost_lookup*)entry)->cost;
 
1057
        }
 
1058
      else
 
1059
        {
 
1060
          error(0, 0, "warning: no cost entry for predicate %s", p->p_name);
 
1061
          inherent_cost = NeedsUnknown;
 
1062
        }
 
1063
    }
 
1064
 
 
1065
  if (inherent_cost > data_requirement_cost)
 
1066
    return inherent_cost;
 
1067
  else
 
1068
    return data_requirement_cost;
 
1069
}
 
1070
 
 
1071
static void
 
1072
estimate_costs (struct predicate *tree)
 
1073
{
 
1074
  if (tree)
 
1075
    {
 
1076
      estimate_costs(tree->pred_right);
 
1077
      estimate_costs(tree->pred_left);
 
1078
      
 
1079
      tree->p_cost = get_pred_cost(tree);
 
1080
    }
 
1081
}
 
1082
 
 
1083
struct predicate*
 
1084
get_eval_tree(void)
 
1085
{
 
1086
  return eval_tree;
 
1087
}
 
1088
 
 
1089
static float 
 
1090
getrate(const struct predicate *p)
 
1091
{
 
1092
  if (p)
 
1093
    return p->est_success_rate;
 
1094
  else
 
1095
    return 1.0f;
 
1096
}
 
1097
 
 
1098
 
 
1099
float 
 
1100
calculate_derived_rates(struct predicate *p)
 
1101
{
 
1102
  assert (NULL != p);
 
1103
 
 
1104
  if (p->pred_right)
 
1105
    calculate_derived_rates(p->pred_right);
 
1106
  if (p->pred_left)
 
1107
    calculate_derived_rates(p->pred_left);
 
1108
 
 
1109
  assert (p->p_type != CLOSE_PAREN);
 
1110
  assert (p->p_type != OPEN_PAREN);
 
1111
 
 
1112
  switch (p->p_type)
 
1113
    {
 
1114
    case NO_TYPE:
 
1115
      assert (NULL == p->pred_right);
 
1116
      assert (NULL == p->pred_left);
 
1117
      return p->est_success_rate;
 
1118
      
 
1119
    case PRIMARY_TYPE:
 
1120
      assert (NULL == p->pred_right);
 
1121
      assert (NULL == p->pred_left);
 
1122
      return p->est_success_rate;
 
1123
 
 
1124
    case UNI_OP:
 
1125
      /* Unary operators must have exactly one operand */
 
1126
      assert (pred_is(p, pred_negate));
 
1127
      assert (NULL == p->pred_left);
 
1128
      p->est_success_rate = (1.0 - p->pred_right->est_success_rate);
 
1129
      return p->est_success_rate;
 
1130
 
 
1131
    case BI_OP:
 
1132
      {
 
1133
        float rate;
 
1134
        /* Binary operators must have two operands */
 
1135
        if (pred_is(p, pred_and))
 
1136
          {
 
1137
            rate = getrate(p->pred_right) * getrate(p->pred_left);
 
1138
          }
 
1139
        else if (pred_is(p, pred_comma))
 
1140
          {
 
1141
            rate = 1.0f;
 
1142
          }
 
1143
        else if (pred_is(p, pred_or))
 
1144
          {
 
1145
            rate = getrate(p->pred_right) + getrate(p->pred_left);
 
1146
          }
 
1147
        else
 
1148
          {
 
1149
            /* only and, or and comma are BI_OP. */
 
1150
            assert (0);
 
1151
            abort ();
 
1152
          }
 
1153
        p->est_success_rate = constrain_rate(rate);
 
1154
      }
 
1155
      return p->est_success_rate;
 
1156
 
 
1157
    case OPEN_PAREN:
 
1158
    case CLOSE_PAREN:
 
1159
      p->est_success_rate = 1.0;
 
1160
      return p->est_success_rate;
 
1161
    }
 
1162
  assert (0);
 
1163
  abort ();
 
1164
}
 
1165
 
 
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
 
 
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
  check_option_combinations(predicates);
 
1329
  pred_sanity_check(predicates);
 
1330
  
 
1331
  /* Done parsing the predicates.  Build the evaluation tree. */
 
1332
  cur_pred = predicates;
 
1333
  eval_tree = get_expr (&cur_pred, NO_PREC, NULL);
 
1334
  calculate_derived_rates(eval_tree);
 
1335
  
 
1336
  /* Check if we have any left-over predicates (this fixes
 
1337
   * Debian bug #185202).
 
1338
   */
 
1339
  if (cur_pred != NULL)
 
1340
    {
 
1341
      /* cur_pred->p_name is often NULL here */
 
1342
      if (pred_is(cur_pred, pred_closeparen))
 
1343
        {
 
1344
          /* e.g. "find \( -true \) \)" */
 
1345
          error (1, 0, _("you have too many ')'"));
 
1346
        }
 
1347
      else
 
1348
        {
 
1349
          if (cur_pred->p_name)
 
1350
            error (1, 0, _("unexpected extra predicate '%s'"), cur_pred->p_name);
 
1351
          else
 
1352
            error (1, 0, _("unexpected extra predicate"));
 
1353
        }
 
1354
    }
 
1355
  
 
1356
  if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
 
1357
    {
 
1358
      fprintf (stderr, "Eval Tree:\n");
 
1359
      print_tree (stderr, eval_tree, 0);
 
1360
    }
 
1361
 
 
1362
  estimate_costs(eval_tree);
 
1363
  
 
1364
  /* Rearrange the eval tree in optimal-predicate order. */
 
1365
  opt_expr (&eval_tree);
 
1366
 
 
1367
  /* Check that the tree is in normalised order (opt_expr does this) */
 
1368
  check_normalization(eval_tree, true);
 
1369
  
 
1370
  do_arm_swaps(eval_tree);
 
1371
  
 
1372
  /* Check that the tree is still in normalised order */
 
1373
  check_normalization(eval_tree, true);
 
1374
 
 
1375
  if (options.debug_options & (DebugExpressionTree|DebugTreeOpt))
 
1376
    {
 
1377
      fprintf (stderr, "Optimized Eval Tree:\n");
 
1378
      print_tree (stderr, eval_tree, 0);
 
1379
      fprintf (stderr, "Optimized command line:\n");
 
1380
      print_optlist(stderr, eval_tree);
 
1381
      fprintf(stderr, "\n");
 
1382
    }
 
1383
 
 
1384
  return eval_tree;
 
1385
}
 
1386
 
 
1387
/* Initialise the performance data for a predicate. 
 
1388
 */
 
1389
static void
 
1390
init_pred_perf(struct predicate *pred)
 
1391
{
 
1392
  struct predicate_performance_info *p = &pred->perf;
 
1393
  p->visits = p->successes = 0;
 
1394
}
 
1395
 
 
1396
 
 
1397
/* Return a pointer to a new predicate structure, which has been
 
1398
   linked in as the last one in the predicates list.
 
1399
 
 
1400
   Set `predicates' to point to the start of the predicates list.
 
1401
   Set `last_pred' to point to the new last predicate in the list.
 
1402
   
 
1403
   Set all cells in the new structure to the default values. */
 
1404
 
 
1405
struct predicate *
 
1406
get_new_pred (const struct parser_table *entry)
 
1407
{
 
1408
  register struct predicate *new_pred;
 
1409
  (void) entry;
 
1410
 
 
1411
  /* Options should not be turned into predicates. */
 
1412
  assert (entry->type != ARG_OPTION);
 
1413
  assert (entry->type != ARG_POSITIONAL_OPTION);
 
1414
  
 
1415
  if (predicates == NULL)
 
1416
    {
 
1417
      predicates = (struct predicate *)
 
1418
        xmalloc (sizeof (struct predicate));
 
1419
      last_pred = predicates;
 
1420
    }
 
1421
  else
 
1422
    {
 
1423
      new_pred = xmalloc (sizeof (struct predicate));
 
1424
      last_pred->pred_next = new_pred;
 
1425
      last_pred = new_pred;
 
1426
    }
 
1427
  last_pred->parser_entry = entry;
 
1428
  last_pred->pred_func = NULL;
 
1429
  last_pred->p_name = NULL;
 
1430
  last_pred->p_type = NO_TYPE;
 
1431
  last_pred->p_prec = NO_PREC;
 
1432
  last_pred->side_effects = false;
 
1433
  last_pred->no_default_print = false;
 
1434
  last_pred->need_stat = true;
 
1435
  last_pred->need_type = true;
 
1436
  last_pred->args.str = NULL;
 
1437
  last_pred->pred_next = NULL;
 
1438
  last_pred->pred_left = NULL;
 
1439
  last_pred->pred_right = NULL;
 
1440
  last_pred->literal_control_chars = options.literal_control_chars;
 
1441
  last_pred->artificial = false;
 
1442
  last_pred->est_success_rate = 1.0;
 
1443
  init_pred_perf(last_pred);
 
1444
  return last_pred;
 
1445
}
 
1446
 
 
1447
/* Return a pointer to a new predicate, with operator check.
 
1448
   Like get_new_pred, but it checks to make sure that the previous
 
1449
   predicate is an operator.  If it isn't, the AND operator is inserted. */
 
1450
 
 
1451
struct predicate *
 
1452
get_new_pred_chk_op (const struct parser_table *entry)
 
1453
{
 
1454
  struct predicate *new_pred;
 
1455
  static const struct parser_table *entry_and = NULL;
 
1456
 
 
1457
  /* Locate the entry in the parser table for the "and" operator */
 
1458
  if (NULL == entry_and)
 
1459
    entry_and = find_parser("and");
 
1460
 
 
1461
  /* Check that it's actually there. If not, that is a bug.*/
 
1462
  assert (entry_and != NULL);   
 
1463
 
 
1464
  if (last_pred)
 
1465
    switch (last_pred->p_type)
 
1466
      {
 
1467
      case NO_TYPE:
 
1468
        error (1, 0, _("oops -- invalid default insertion of and!"));
 
1469
        break;
 
1470
 
 
1471
      case PRIMARY_TYPE:
 
1472
      case CLOSE_PAREN:
 
1473
        /* We need to interpose the and operator. */
 
1474
        new_pred = get_new_pred (entry_and);
 
1475
        new_pred->pred_func = pred_and;
 
1476
        new_pred->p_name = "-a";
 
1477
        new_pred->p_type = BI_OP;
 
1478
        new_pred->p_prec = AND_PREC;
 
1479
        new_pred->need_stat = false;
 
1480
        new_pred->need_type = false;
 
1481
        new_pred->args.str = NULL;
 
1482
        new_pred->side_effects = false;
 
1483
        new_pred->no_default_print = false;
 
1484
        break;
 
1485
 
 
1486
      default:
 
1487
        break;
 
1488
      }
 
1489
  
 
1490
  new_pred = get_new_pred (entry);
 
1491
  new_pred->parser_entry = entry;
 
1492
  return new_pred;
 
1493
}
 
1494
 
 
1495
struct cost_assoc
 
1496
{
 
1497
  enum EvaluationCost cost;
 
1498
  char *name;
 
1499
};
 
1500
struct cost_assoc cost_table[] = 
 
1501
  {
 
1502
    { NeedsNothing,         "Nothing" },
 
1503
    { NeedsType,            "Type" },
 
1504
    { NeedsStatInfo,        "StatInfo" },
 
1505
    { NeedsLinkName,        "LinkName" },
 
1506
    { NeedsAccessInfo,      "AccessInfo" },
 
1507
    { NeedsSyncDiskHit,     "SyncDiskHit" },
 
1508
    { NeedsEventualExec,    "EventualExec" },
 
1509
    { NeedsImmediateExec,   "ImmediateExec" },
 
1510
    { NeedsUserInteraction, "UserInteraction" },
 
1511
    { NeedsUnknown,         "Unknown" }
 
1512
  };
 
1513
 
 
1514
struct prec_assoc
 
1515
{
 
1516
  short prec;
 
1517
  char *prec_name;
 
1518
};
 
1519
 
 
1520
static struct prec_assoc prec_table[] =
 
1521
{
 
1522
  {NO_PREC, "no"},
 
1523
  {COMMA_PREC, "comma"},
 
1524
  {OR_PREC, "or"},
 
1525
  {AND_PREC, "and"},
 
1526
  {NEGATE_PREC, "negate"},
 
1527
  {MAX_PREC, "max"},
 
1528
  {-1, "unknown "}
 
1529
};
 
1530
 
 
1531
struct op_assoc
 
1532
{
 
1533
  short type;
 
1534
  char *type_name;
 
1535
};
 
1536
 
 
1537
static struct op_assoc type_table[] =
 
1538
{
 
1539
  {NO_TYPE,      "no"},
 
1540
  {PRIMARY_TYPE, "primary"},
 
1541
  {UNI_OP,       "uni_op"},
 
1542
  {BI_OP,        "bi_op"},
 
1543
  {OPEN_PAREN,   "open_paren  "},
 
1544
  {CLOSE_PAREN,  "close_paren "},
 
1545
  {-1,           "unknown"}
 
1546
};
 
1547
 
 
1548
static const char *
 
1549
cost_name (enum EvaluationCost cost)
 
1550
{
 
1551
  unsigned int i;
 
1552
  unsigned int n = sizeof(cost_table)/sizeof(cost_table[0]);
 
1553
  
 
1554
  for (i = 0; i<n; ++i)
 
1555
    if (cost_table[i].cost == cost)
 
1556
      return cost_table[i].name;
 
1557
  return "unknown";
 
1558
}
 
1559
 
 
1560
 
 
1561
static char *
 
1562
type_name (type)
 
1563
     short type;
 
1564
{
 
1565
  int i;
 
1566
 
 
1567
  for (i = 0; type_table[i].type != (short) -1; i++)
 
1568
    if (type_table[i].type == type)
 
1569
      break;
 
1570
  return (type_table[i].type_name);
 
1571
}
 
1572
 
 
1573
static char *
 
1574
prec_name (prec)
 
1575
     short prec;
 
1576
{
 
1577
  int i;
 
1578
 
 
1579
  for (i = 0; prec_table[i].prec != (short) -1; i++)
 
1580
    if (prec_table[i].prec == prec)
 
1581
      break;
 
1582
  return (prec_table[i].prec_name);
 
1583
}
 
1584
 
 
1585
 
 
1586
/* Walk the expression tree NODE to stdout.
 
1587
   INDENT is the number of levels to indent the left margin. */
 
1588
 
 
1589
void
 
1590
print_tree (FILE *fp, struct predicate *node, int indent)
 
1591
{
 
1592
  int i;
 
1593
 
 
1594
  if (node == NULL)
 
1595
    return;
 
1596
  for (i = 0; i < indent; i++)
 
1597
    fprintf (fp, "    ");
 
1598
  fprintf (fp, "pred=[");
 
1599
  print_predicate(fp, node);
 
1600
  fprintf (fp, "] type=%s prec=%s",
 
1601
          type_name (node->p_type), prec_name (node->p_prec));
 
1602
  fprintf (fp, " cost=%s rate=%#03.2g %sside effects ",
 
1603
           cost_name(node->p_cost),
 
1604
           node->est_success_rate,
 
1605
           (node->side_effects ? "" : "no "));
 
1606
  
 
1607
  if (node->need_stat || node->need_type)
 
1608
    {
 
1609
      int comma = 0;
 
1610
      
 
1611
      fprintf (fp, "Needs ");
 
1612
      if (node->need_stat)
 
1613
        {
 
1614
          fprintf (fp, "stat");
 
1615
          comma = 1;
 
1616
        }
 
1617
      if (node->need_type)
 
1618
        {
 
1619
          fprintf (fp, "%stype", comma ? "," : "");
 
1620
        }
 
1621
    }
 
1622
  fprintf (fp, "\n");
 
1623
 
 
1624
 
 
1625
  for (i = 0; i < indent; i++)
 
1626
    fprintf (fp, "    ");
 
1627
  if (NULL == node->pred_left && NULL == node->pred_right)
 
1628
    {
 
1629
      fprintf (fp, "no children.\n");
 
1630
    }
 
1631
  else
 
1632
    {
 
1633
      if (node->pred_left)
 
1634
        {
 
1635
          fprintf (fp, "left:\n");
 
1636
          print_tree (fp, node->pred_left, indent + 1);
 
1637
        }
 
1638
      else 
 
1639
        {
 
1640
          fprintf (fp, "no left.\n");
 
1641
        }
 
1642
      
 
1643
      for (i = 0; i < indent; i++)
 
1644
        fprintf (fp, "    ");
 
1645
      if (node->pred_right)
 
1646
        {
 
1647
          fprintf (fp, "right:\n");
 
1648
          print_tree (fp, node->pred_right, indent + 1);
 
1649
        }
 
1650
      else
 
1651
        {
 
1652
          fprintf (fp, "no right.\n");
 
1653
        }
 
1654
    }
 
1655
}