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