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  * $FreeBSD: src/usr.bin/find/operator.c,v 1.5.6.1 2001/05/06 09:53:22 phk Exp $
  37  * $DragonFly: src/usr.bin/find/operator.c,v 1.4 2004/07/09 19:11:20 drhodus Exp $
  38  *
  39  * @(#)operator.c       8.1 (Berkeley) 6/6/93
  40  */
  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 /*
  51  * yanknode --
  52  *      destructively removes the top from the plan
  53  */
  54 /* planp: pointer to top of plan (modified) */
  55 static PLAN *
  56 yanknode(PLAN **planp)
  57 {
  58         PLAN *node;             /* top node removed from the plan */
  59
  60         if ((node = (*planp)) == NULL)
  61                 return (NULL);
  62         (*planp) = (*planp)->next;
  63         node->next = NULL;
  64         return (node);
  65 }
  66
  67 /*
  68  * yankexpr --
  69  *      Removes one expression from the plan.  This is used mainly by
  70  *      paren_squish.  In comments below, an expression is either a
  71  *      simple node or a f_expr node containing a list of simple nodes.
  72  */
  73 /* planp: pointer to top of plan (modified) */
  74 static PLAN *
  75 yankexpr(PLAN **planp)
  76 {
  77         register PLAN *next;    /* temp node holding subexpression results */
  78         PLAN *node;             /* pointer to returned node or expression */
  79         PLAN *tail;             /* pointer to tail of subplan */
  80         PLAN *subplan;          /* pointer to head of ( ) expression */
  81
  82         /* first pull the top node from the plan */
  83         if ((node = yanknode(planp)) == NULL)
  84                 return (NULL);
  85
  86         /*
  87          * If the node is an '(' then we recursively slurp up expressions
  88          * until we find its associated ')'.  If it's a closing paren we
  89          * just return it and unwind our recursion; all other nodes are
  90          * complete expressions, so just return them.
  91          */
  92         if (node->execute == f_openparen)
  93                 for (tail = subplan = NULL;;) {
  94                         if ((next = yankexpr(planp)) == NULL)
  95                                 err(1, "(: missing closing ')'");
  96                         /*
  97                          * If we find a closing ')' we store the collected
  98                          * subplan in our '(' node and convert the node to
  99                          * a f_expr.  The ')' we found is ignored.  Otherwise,
 100                          * we just continue to add whatever we get to our
 101                          * subplan.
 102                          */
 103                         if (next->execute == f_closeparen) {
 104                                 if (subplan == NULL)
 105                                         errx(1, "(): empty inner expression");
 106                                 node->p_data[0] = subplan;
 107                                 node->execute = f_expr;
 108                                 break;
 109                         } else {
 110                                 if (subplan == NULL)
 111                                         tail = subplan = next;
 112                                 else {
 113                                         tail->next = next;
 114                                         tail = next;
 115                                 }
 116                                 tail->next = NULL;
 117                         }
 118                 }
 119         return (node);
 120 }
 121
 122 /*
 123  * paren_squish --
 124  *      replaces "parentheisized" plans in our search plan with "expr" nodes.
 125  */
 126 /* plan: plan with ( ) nodes */
 127 PLAN *
 128 paren_squish(PLAN *plan)
 129 {
 130         register PLAN *expr;    /* pointer to next expression */
 131         register 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: plan to process */
 165 PLAN *
 166 not_squish(PLAN *plan)
 167 {
 168         register PLAN *next;    /* next node being processed */
 169         register PLAN *node;    /* temporary node used in f_not processing */
 170         register 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: plan with ors to be squished */
 229 PLAN *
 230 or_squish(PLAN *plan)
 231 {
 232         register PLAN *next;    /* next node being processed */
 233         register PLAN *tail;    /* pointer to tail of result plan */
 234         PLAN *result;           /* pointer to head of result plan */
 235
 236         tail = result = next = NULL;
 237
 238         while ((next = yanknode(&plan)) != NULL) {
 239                 /*
 240                  * if we encounter a ( expression ) then look for or's in
 241                  * the expr subplan.
 242                  */
 243                 if (next->execute == f_expr)
 244                         next->p_data[0] = or_squish(next->p_data[0]);
 245
 246                 /* if we encounter a not then look for or's in the subplan */
 247                 if (next->execute == f_not)
 248                         next->p_data[0] = or_squish(next->p_data[0]);
 249
 250                 /*
 251                  * if we encounter an or, then place our collected plan in the
 252                  * or's first subplan and then recursively collect the
 253                  * remaining stuff into the second subplan and return the or.
 254                  */
 255                 if (next->execute == f_or) {
 256                         if (result == NULL)
 257                                 errx(1, "-o: no expression before -o");
 258                         next->p_data[0] = result;
 259                         next->p_data[1] = or_squish(plan);
 260                         if (next->p_data[1] == NULL)
 261                                 errx(1, "-o: no expression after -o");
 262                         return (next);
 263                 }
 264
 265                 /* add the node to our result plan */
 266                 if (result == NULL)
 267                         tail = result = next;
 268                 else {
 269                         tail->next = next;
 270                         tail = next;
 271                 }
 272                 tail->next = NULL;
 273         }
 274         return (result);
 275 }