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 /*static char sccsid[] = "from: @(#)operator.c 8.1 (Berkeley) 6/6/93";*/ 39 static char rcsid[] = "$Id: operator.c,v 1.3 1993/12/30 21:15:31 jtc Exp $"; 40 #endif /* not lint */ 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 static PLAN * 55 yanknode(planp) 56 PLAN **planp; /* pointer to top of plan (modified) */ 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 N_EXPR node containing a list of simple nodes. 72 */ 73 static PLAN * 74 yankexpr(planp) 75 PLAN **planp; /* pointer to top of plan (modified) */ 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 int f_expr(); 82 83 /* first pull the top node from the plan */ 84 if ((node = yanknode(planp)) == NULL) 85 return (NULL); 86 87 /* 88 * If the node is an '(' then we recursively slurp up expressions 89 * until we find its associated ')'. If it's a closing paren we 90 * just return it and unwind our recursion; all other nodes are 91 * complete expressions, so just return them. 92 */ 93 if (node->type == N_OPENPAREN) 94 for (tail = subplan = NULL;;) { 95 if ((next = yankexpr(planp)) == NULL) 96 err(1, "(: missing closing ')'"); 97 /* 98 * If we find a closing ')' we store the collected 99 * subplan in our '(' node and convert the node to 100 * a N_EXPR. The ')' we found is ignored. Otherwise, 101 * we just continue to add whatever we get to our 102 * subplan. 103 */ 104 if (next->type == N_CLOSEPAREN) { 105 if (subplan == NULL) 106 errx(1, "(): empty inner expression"); 107 node->p_data[0] = subplan; 108 node->type = N_EXPR; 109 node->eval = 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 "parentheisized" plans in our search plan with "expr" nodes. 127 */ 128 PLAN * 129 paren_squish(plan) 130 PLAN *plan; /* plan with ( ) nodes */ 131 { 132 register PLAN *expr; /* pointer to next expression */ 133 register PLAN *tail; /* pointer to tail of result plan */ 134 PLAN *result; /* pointer to head of result plan */ 135 136 result = tail = NULL; 137 138 /* 139 * the basic idea is to have yankexpr do all our work and just 140 * collect it's results together. 141 */ 142 while ((expr = yankexpr(&plan)) != NULL) { 143 /* 144 * if we find an unclaimed ')' it means there is a missing 145 * '(' someplace. 146 */ 147 if (expr->type == N_CLOSEPAREN) 148 errx(1, "): no beginning '('"); 149 150 /* add the expression to our result plan */ 151 if (result == NULL) 152 tail = result = expr; 153 else { 154 tail->next = expr; 155 tail = expr; 156 } 157 tail->next = NULL; 158 } 159 return (result); 160 } 161 162 /* 163 * not_squish -- 164 * compresses "!" expressions in our search plan. 165 */ 166 PLAN * 167 not_squish(plan) 168 PLAN *plan; /* plan to process */ 169 { 170 register PLAN *next; /* next node being processed */ 171 register PLAN *node; /* temporary node used in N_NOT processing */ 172 register PLAN *tail; /* pointer to tail of result plan */ 173 PLAN *result; /* pointer to head of result plan */ 174 175 tail = result = next = NULL; 176 177 while ((next = yanknode(&plan)) != NULL) { 178 /* 179 * if we encounter a ( expression ) then look for nots in 180 * the expr subplan. 181 */ 182 if (next->type == N_EXPR) 183 next->p_data[0] = not_squish(next->p_data[0]); 184 185 /* 186 * if we encounter a not, then snag the next node and place 187 * it in the not's subplan. As an optimization we compress 188 * several not's to zero or one not. 189 */ 190 if (next->type == N_NOT) { 191 int notlevel = 1; 192 193 node = yanknode(&plan); 194 while (node->type == N_NOT) { 195 ++notlevel; 196 node = yanknode(&plan); 197 } 198 if (node == NULL) 199 errx(1, "!: no following expression"); 200 if (node->type == N_OR) 201 errx(1, "!: nothing between ! and -o"); 202 if (notlevel % 2 != 1) 203 next = node; 204 else 205 next->p_data[0] = node; 206 } 207 208 /* add the node to our result plan */ 209 if (result == NULL) 210 tail = result = next; 211 else { 212 tail->next = next; 213 tail = next; 214 } 215 tail->next = NULL; 216 } 217 return (result); 218 } 219 220 /* 221 * or_squish -- 222 * compresses -o expressions in our search plan. 223 */ 224 PLAN * 225 or_squish(plan) 226 PLAN *plan; /* plan with ors to be squished */ 227 { 228 register PLAN *next; /* next node being processed */ 229 register PLAN *tail; /* pointer to tail of result plan */ 230 PLAN *result; /* pointer to head of result plan */ 231 232 tail = result = next = NULL; 233 234 while ((next = yanknode(&plan)) != NULL) { 235 /* 236 * if we encounter a ( expression ) then look for or's in 237 * the expr subplan. 238 */ 239 if (next->type == N_EXPR) 240 next->p_data[0] = or_squish(next->p_data[0]); 241 242 /* if we encounter a not then look for not's in the subplan */ 243 if (next->type == N_NOT) 244 next->p_data[0] = or_squish(next->p_data[0]); 245 246 /* 247 * if we encounter an or, then place our collected plan in the 248 * or's first subplan and then recursively collect the 249 * remaining stuff into the second subplan and return the or. 250 */ 251 if (next->type == N_OR) { 252 if (result == NULL) 253 errx(1, "-o: no expression before -o"); 254 next->p_data[0] = result; 255 next->p_data[1] = or_squish(plan); 256 if (next->p_data[1] == NULL) 257 errx(1, "-o: no expression after -o"); 258 return (next); 259 } 260 261 /* add the node to our result plan */ 262 if (result == NULL) 263 tail = result = next; 264 else { 265 tail->next = next; 266 tail = next; 267 } 268 tail->next = NULL; 269 } 270 return (result); 271 } 272