usr.bin/find/operator.c

   1 /*-
   2  * Copyright (c) 1990, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Cimarron D. Taylor of the University of California, Berkeley.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * $FreeBSD: src/usr.bin/find/operator.c,v 1.17 2010/12/11 08:32:16 joel Exp $
  33  *
  34  * @(#)operator.c       8.1 (Berkeley) 6/6/93
  35  */
  36
  37 #include <sys/types.h>
  38
  39 #include <err.h>
  40 #include <fts.h>
  41 #include <stdio.h>
  42
  43 #include "find.h"
  44
  45 static PLAN *yanknode(PLAN **);
  46 static PLAN *yankexpr(PLAN **);
  47
  48 /*
  49  * yanknode --
  50  *      destructively removes the top from the plan
  51  */
  52 static PLAN *
  53 yanknode(PLAN **planp)
  54 {
  55         PLAN *node;             /* top node removed from the plan */
  56
  57         if ((node = (*planp)) == NULL)
  58                 return (NULL);
  59         (*planp) = (*planp)->next;
  60         node->next = NULL;
  61         return (node);
  62 }
  63
  64 /*
  65  * yankexpr --
  66  *      Removes one expression from the plan.  This is used mainly by
  67  *      paren_squish.  In comments below, an expression is either a
  68  *      simple node or a f_expr node containing a list of simple nodes.
  69  */
  70 static PLAN *
  71 yankexpr(PLAN **planp)
  72 {
  73         PLAN *next;             /* temp node holding subexpression results */
  74         PLAN *node;             /* pointer to returned node or expression */
  75         PLAN *tail;             /* pointer to tail of subplan */
  76         PLAN *subplan;          /* pointer to head of ( ) expression */
  77
  78         /* first pull the top node from the plan */
  79         if ((node = yanknode(planp)) == NULL)
  80                 return (NULL);
  81
  82         /*
  83          * If the node is an '(' then we recursively slurp up expressions
  84          * until we find its associated ')'.  If it's a closing paren we
  85          * just return it and unwind our recursion; all other nodes are
  86          * complete expressions, so just return them.
  87          */
  88         if (node->execute == f_openparen)
  89                 for (tail = subplan = NULL;;) {
  90                         if ((next = yankexpr(planp)) == NULL)
  91                                 errx(1, "(: missing closing ')'");
  92                         /*
  93                          * If we find a closing ')' we store the collected
  94                          * subplan in our '(' node and convert the node to
  95                          * a f_expr.  The ')' we found is ignored.  Otherwise,
  96                          * we just continue to add whatever we get to our
  97                          * subplan.
  98                          */
  99                         if (next->execute == f_closeparen) {
 100                                 if (subplan == NULL)
 101                                         errx(1, "(): empty inner expression");
 102                                 node->p_data[0] = subplan;
 103                                 node->execute = f_expr;
 104                                 break;
 105                         } else {
 106                                 if (subplan == NULL)
 107                                         tail = subplan = next;
 108                                 else {
 109                                         tail->next = next;
 110                                         tail = next;
 111                                 }
 112                                 tail->next = NULL;
 113                         }
 114                 }
 115         return (node);
 116 }
 117
 118 /*
 119  * paren_squish --
 120  *      replaces "parenthesized" plans in our search plan with "expr" nodes.
 121  */
 122 PLAN *
 123 paren_squish(PLAN *plan)
 124 {
 125         PLAN *expr;             /* pointer to next expression */
 126         PLAN *tail;             /* pointer to tail of result plan */
 127         PLAN *result;           /* pointer to head of result plan */
 128
 129         result = tail = NULL;
 130
 131         /*
 132          * the basic idea is to have yankexpr do all our work and just
 133          * collect its results together.
 134          */
 135         while ((expr = yankexpr(&plan)) != NULL) {
 136                 /*
 137                  * if we find an unclaimed ')' it means there is a missing
 138                  * '(' someplace.
 139                  */
 140                 if (expr->execute == f_closeparen)
 141                         errx(1, "): no beginning '('");
 142
 143                 /* add the expression to our result plan */
 144                 if (result == NULL)
 145                         tail = result = expr;
 146                 else {
 147                         tail->next = expr;
 148                         tail = expr;
 149                 }
 150                 tail->next = NULL;
 151         }
 152         return (result);
 153 }
 154
 155 /*
 156  * not_squish --
 157  *      compresses "!" expressions in our search plan.
 158  */
 159 PLAN *
 160 not_squish(PLAN *plan)
 161 {
 162         PLAN *next;             /* next node being processed */
 163         PLAN *node;             /* temporary node used in f_not processing */
 164         PLAN *tail;             /* pointer to tail of result plan */
 165         PLAN *result;           /* pointer to head of result plan */
 166
 167         tail = result = NULL;
 168
 169         while ((next = yanknode(&plan))) {
 170                 /*
 171                  * if we encounter a ( expression ) then look for nots in
 172                  * the expr subplan.
 173                  */
 174                 if (next->execute == f_expr)
 175                         next->p_data[0] = not_squish(next->p_data[0]);
 176
 177                 /*
 178                  * if we encounter a not, then snag the next node and place
 179                  * it in the not's subplan.  As an optimization we compress
 180                  * several not's to zero or one not.
 181                  */
 182                 if (next->execute == f_not) {
 183                         int notlevel = 1;
 184
 185                         node = yanknode(&plan);
 186                         while (node != NULL && node->execute == f_not) {
 187                                 ++notlevel;
 188                                 node = yanknode(&plan);
 189                         }
 190                         if (node == NULL)
 191                                 errx(1, "!: no following expression");
 192                         if (node->execute == f_or)
 193                                 errx(1, "!: nothing between ! and -o");
 194                         /*
 195                          * If we encounter ! ( expr ) then look for nots in
 196                          * the expr subplan.
 197                          */
 198                         if (node->execute == f_expr)
 199                                 node->p_data[0] = not_squish(node->p_data[0]);
 200                         if (notlevel % 2 != 1)
 201                                 next = node;
 202                         else
 203                                 next->p_data[0] = node;
 204                 }
 205
 206                 /* add the node to our result plan */
 207                 if (result == NULL)
 208                         tail = result = next;
 209                 else {
 210                         tail->next = next;
 211                         tail = next;
 212                 }
 213                 tail->next = NULL;
 214         }
 215         return (result);
 216 }
 217
 218 /*
 219  * or_squish --
 220  *      compresses -o expressions in our search plan.
 221  */
 222 PLAN *
 223 or_squish(PLAN *plan)
 224 {
 225         PLAN *next;             /* next node being processed */
 226         PLAN *tail;             /* pointer to tail of result plan */
 227         PLAN *result;           /* pointer to head of result plan */
 228
 229         tail = result = next = NULL;
 230
 231         while ((next = yanknode(&plan)) != NULL) {
 232                 /*
 233                  * if we encounter a ( expression ) then look for or's in
 234                  * the expr subplan.
 235                  */
 236                 if (next->execute == f_expr)
 237                         next->p_data[0] = or_squish(next->p_data[0]);
 238
 239                 /* if we encounter a not then look for or's in the subplan */
 240                 if (next->execute == f_not)
 241                         next->p_data[0] = or_squish(next->p_data[0]);
 242
 243                 /*
 244                  * if we encounter an or, then place our collected plan in the
 245                  * or's first subplan and then recursively collect the
 246                  * remaining stuff into the second subplan and return the or.
 247                  */
 248                 if (next->execute == f_or) {
 249                         if (result == NULL)
 250                                 errx(1, "-o: no expression before -o");
 251                         next->p_data[0] = result;
 252                         next->p_data[1] = or_squish(plan);
 253                         if (next->p_data[1] == NULL)
 254                                 errx(1, "-o: no expression after -o");
 255                         return (next);
 256                 }
 257
 258                 /* add the node to our result plan */
 259                 if (result == NULL)
 260                         tail = result = next;
 261                 else {
 262                         tail->next = next;
 263                         tail = next;
 264                 }
 265                 tail->next = NULL;
 266         }
 267         return (result);
 268 }