commands/find/operator.c

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