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