usr.bin/find/operator.c

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