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  * 4. 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
  33 #ifndef lint
  34 #if 0
  35 static char sccsid[] = "@(#)operator.c  8.1 (Berkeley) 6/6/93";
  36 #endif
  37 #endif /* not lint */
  38
  39 #include <sys/cdefs.h>
  40 __FBSDID("$FreeBSD: src/usr.bin/find/operator.c,v 1.17 2010/12/11 08:32:16 joel Exp $");
  41
  42 #include <sys/types.h>
  43
  44 #include <err.h>
  45 #include <fts.h>
  46 #include <stdio.h>
  47
  48 #include "find.h"
  49
  50 static PLAN *yanknode(PLAN **);
  51 static PLAN *yankexpr(PLAN **);
  52
  53 /*
  54  * yanknode --
  55  *      destructively removes the top from the plan
  56  */
  57 static PLAN *
  58 yanknode(PLAN **planp)
  59 {
  60         PLAN *node;             /* top node removed from the plan */
  61
  62         if ((node = (*planp)) == NULL)
  63                 return (NULL);
  64         (*planp) = (*planp)->next;
  65         node->next = NULL;
  66         return (node);
  67 }
  68
  69 /*
  70  * yankexpr --
  71  *      Removes one expression from the plan.  This is used mainly by
  72  *      paren_squish.  In comments below, an expression is either a
  73  *      simple node or a f_expr node containing a list of simple nodes.
  74  */
  75 static PLAN *
  76 yankexpr(PLAN **planp)
  77 {
  78         PLAN *next;             /* temp node holding subexpression results */
  79         PLAN *node;             /* pointer to returned node or expression */
  80         PLAN *tail;             /* pointer to tail of subplan */
  81         PLAN *subplan;          /* pointer to head of ( ) expression */
  82
  83         /* first pull the top node from the plan */
  84         if ((node = yanknode(planp)) == NULL)
  85                 return (NULL);
  86
  87         /*
  88          * If the node is an '(' then we recursively slurp up expressions
  89          * until we find its associated ')'.  If it's a closing paren we
  90          * just return it and unwind our recursion; all other nodes are
  91          * complete expressions, so just return them.
  92          */
  93         if (node->execute == f_openparen)
  94                 for (tail = subplan = NULL;;) {
  95                         if ((next = yankexpr(planp)) == NULL)
  96                                 errx(1, "(: missing closing ')'");
  97                         /*
  98                          * If we find a closing ')' we store the collected
  99                          * subplan in our '(' node and convert the node to
 100                          * a f_expr.  The ')' we found is ignored.  Otherwise,
 101                          * we just continue to add whatever we get to our
 102                          * subplan.
 103                          */
 104                         if (next->execute == f_closeparen) {
 105                                 if (subplan == NULL)
 106                                         errx(1, "(): empty inner expression");
 107                                 node->p_data[0] = subplan;
 108                                 node->execute = f_expr;
 109                                 break;
 110                         } else {
 111                                 if (subplan == NULL)
 112                                         tail = subplan = next;
 113                                 else {
 114                                         tail->next = next;
 115                                         tail = next;
 116                                 }
 117                                 tail->next = NULL;
 118                         }
 119                 }
 120         return (node);
 121 }
 122
 123 /*
 124  * paren_squish --
 125  *      replaces "parenthesized" plans in our search plan with "expr" nodes.
 126  */
 127 PLAN *
 128 paren_squish(PLAN *plan)
 129 {
 130         PLAN *expr;             /* pointer to next expression */
 131         PLAN *tail;             /* pointer to tail of result plan */
 132         PLAN *result;           /* pointer to head of result plan */
 133
 134         result = tail = NULL;
 135
 136         /*
 137          * the basic idea is to have yankexpr do all our work and just
 138          * collect its results together.
 139          */
 140         while ((expr = yankexpr(&plan)) != NULL) {
 141                 /*
 142                  * if we find an unclaimed ')' it means there is a missing
 143                  * '(' someplace.
 144                  */
 145                 if (expr->execute == f_closeparen)
 146                         errx(1, "): no beginning '('");
 147
 148                 /* add the expression to our result plan */
 149                 if (result == NULL)
 150                         tail = result = expr;
 151                 else {
 152                         tail->next = expr;
 153                         tail = expr;
 154                 }
 155                 tail->next = NULL;
 156         }
 157         return (result);
 158 }
 159
 160 /*
 161  * not_squish --
 162  *      compresses "!" expressions in our search plan.
 163  */
 164 PLAN *
 165 not_squish(PLAN *plan)
 166 {
 167         PLAN *next;             /* next node being processed */
 168         PLAN *node;             /* temporary node used in f_not processing */
 169         PLAN *tail;             /* pointer to tail of result plan */
 170         PLAN *result;           /* pointer to head of result plan */
 171
 172         tail = result = NULL;
 173
 174         while ((next = yanknode(&plan))) {
 175                 /*
 176                  * if we encounter a ( expression ) then look for nots in
 177                  * the expr subplan.
 178                  */
 179                 if (next->execute == f_expr)
 180                         next->p_data[0] = not_squish(next->p_data[0]);
 181
 182                 /*
 183                  * if we encounter a not, then snag the next node and place
 184                  * it in the not's subplan.  As an optimization we compress
 185                  * several not's to zero or one not.
 186                  */
 187                 if (next->execute == f_not) {
 188                         int notlevel = 1;
 189
 190                         node = yanknode(&plan);
 191                         while (node != NULL && node->execute == f_not) {
 192                                 ++notlevel;
 193                                 node = yanknode(&plan);
 194                         }
 195                         if (node == NULL)
 196                                 errx(1, "!: no following expression");
 197                         if (node->execute == f_or)
 198                                 errx(1, "!: nothing between ! and -o");
 199                         /*
 200                          * If we encounter ! ( expr ) then look for nots in
 201                          * the expr subplan.
 202                          */
 203                         if (node->execute == f_expr)
 204                                 node->p_data[0] = not_squish(node->p_data[0]);
 205                         if (notlevel % 2 != 1)
 206                                 next = node;
 207                         else
 208                                 next->p_data[0] = node;
 209                 }
 210
 211                 /* add the node to our result plan */
 212                 if (result == NULL)
 213                         tail = result = next;
 214                 else {
 215                         tail->next = next;
 216                         tail = next;
 217                 }
 218                 tail->next = NULL;
 219         }
 220         return (result);
 221 }
 222
 223 /*
 224  * or_squish --
 225  *      compresses -o expressions in our search plan.
 226  */
 227 PLAN *
 228 or_squish(PLAN *plan)
 229 {
 230         PLAN *next;             /* next node being processed */
 231         PLAN *tail;             /* pointer to tail of result plan */
 232         PLAN *result;           /* pointer to head of result plan */
 233
 234         tail = result = next = NULL;
 235
 236         while ((next = yanknode(&plan)) != NULL) {
 237                 /*
 238                  * if we encounter a ( expression ) then look for or's in
 239                  * the expr subplan.
 240                  */
 241                 if (next->execute == f_expr)
 242                         next->p_data[0] = or_squish(next->p_data[0]);
 243
 244                 /* if we encounter a not then look for or's in the subplan */
 245                 if (next->execute == f_not)
 246                         next->p_data[0] = or_squish(next->p_data[0]);
 247
 248                 /*
 249                  * if we encounter an or, then place our collected plan in the
 250                  * or's first subplan and then recursively collect the
 251                  * remaining stuff into the second subplan and return the or.
 252                  */
 253                 if (next->execute == f_or) {
 254                         if (result == NULL)
 255                                 errx(1, "-o: no expression before -o");
 256                         next->p_data[0] = result;
 257                         next->p_data[1] = or_squish(plan);
 258                         if (next->p_data[1] == NULL)
 259                                 errx(1, "-o: no expression after -o");
 260                         return (next);
 261                 }
 262
 263                 /* add the node to our result plan */
 264                 if (result == NULL)
 265                         tail = result = next;
 266                 else {
 267                         tail->next = next;
 268                         tail = next;
 269                 }
 270                 tail->next = NULL;
 271         }
 272         return (result);
 273 }