operator.c revision 116333
1219820Sjeff/*- 2219820Sjeff * Copyright (c) 1990, 1993 3219820Sjeff * The Regents of the University of California. All rights reserved. 4219820Sjeff * 5219820Sjeff * This code is derived from software contributed to Berkeley by 6219820Sjeff * Cimarron D. Taylor of the University of California, Berkeley. 7219820Sjeff * 8219820Sjeff * Redistribution and use in source and binary forms, with or without 9219820Sjeff * modification, are permitted provided that the following conditions 10219820Sjeff * are met: 11219820Sjeff * 1. Redistributions of source code must retain the above copyright 12219820Sjeff * notice, this list of conditions and the following disclaimer. 13219820Sjeff * 2. Redistributions in binary form must reproduce the above copyright 14219820Sjeff * notice, this list of conditions and the following disclaimer in the 15219820Sjeff * documentation and/or other materials provided with the distribution. 16219820Sjeff * 3. All advertising materials mentioning features or use of this software 17219820Sjeff * must display the following acknowledgement: 18219820Sjeff * This product includes software developed by the University of 19219820Sjeff * California, Berkeley and its contributors. 20219820Sjeff * 4. Neither the name of the University nor the names of its contributors 21219820Sjeff * may be used to endorse or promote products derived from this software 22219820Sjeff * without specific prior written permission. 23219820Sjeff * 24219820Sjeff * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25219820Sjeff * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26219820Sjeff * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27219820Sjeff * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28219820Sjeff * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29219820Sjeff * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30219820Sjeff * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31219820Sjeff * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32219820Sjeff * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33219820Sjeff * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34219820Sjeff * SUCH DAMAGE. 35219820Sjeff */ 36219820Sjeff 37219820Sjeff#ifndef lint 38219820Sjeff#if 0 39219820Sjeffstatic char sccsid[] = "@(#)operator.c 8.1 (Berkeley) 6/6/93"; 40219820Sjeff#endif 41219820Sjeff#endif /* not lint */ 42219820Sjeff 43219820Sjeff#include <sys/cdefs.h> 44219820Sjeff__FBSDID("$FreeBSD: head/usr.bin/find/operator.c 116333 2003-06-14 13:00:21Z markm $"); 45219820Sjeff 46219820Sjeff#include <sys/types.h> 47219820Sjeff 48219820Sjeff#include <err.h> 49219820Sjeff#include <fts.h> 50219820Sjeff#include <stdio.h> 51219820Sjeff 52219820Sjeff#include "find.h" 53219820Sjeff 54219820Sjeffstatic PLAN *yanknode(PLAN **); 55219820Sjeffstatic PLAN *yankexpr(PLAN **); 56219820Sjeff 57219820Sjeff/* 58219820Sjeff * yanknode -- 59219820Sjeff * destructively removes the top from the plan 60219820Sjeff */ 61219820Sjeffstatic PLAN * 62219820Sjeffyanknode(PLAN **planp) 63219820Sjeff{ 64219820Sjeff PLAN *node; /* top node removed from the plan */ 65219820Sjeff 66219820Sjeff if ((node = (*planp)) == NULL) 67219820Sjeff return (NULL); 68219820Sjeff (*planp) = (*planp)->next; 69219820Sjeff node->next = NULL; 70219820Sjeff return (node); 71219820Sjeff} 72219820Sjeff 73219820Sjeff/* 74219820Sjeff * yankexpr -- 75219820Sjeff * Removes one expression from the plan. This is used mainly by 76219820Sjeff * paren_squish. In comments below, an expression is either a 77219820Sjeff * simple node or a f_expr node containing a list of simple nodes. 78219820Sjeff */ 79219820Sjeffstatic PLAN * 80219820Sjeffyankexpr(PLAN **planp) 81219820Sjeff{ 82219820Sjeff PLAN *next; /* temp node holding subexpression results */ 83219820Sjeff PLAN *node; /* pointer to returned node or expression */ 84219820Sjeff PLAN *tail; /* pointer to tail of subplan */ 85219820Sjeff PLAN *subplan; /* pointer to head of ( ) expression */ 86219820Sjeff 87219820Sjeff /* first pull the top node from the plan */ 88219820Sjeff if ((node = yanknode(planp)) == NULL) 89219820Sjeff return (NULL); 90219820Sjeff 91219820Sjeff /* 92219820Sjeff * If the node is an '(' then we recursively slurp up expressions 93219820Sjeff * until we find its associated ')'. If it's a closing paren we 94219820Sjeff * just return it and unwind our recursion; all other nodes are 95219820Sjeff * complete expressions, so just return them. 96219820Sjeff */ 97219820Sjeff if (node->execute == f_openparen) 98219820Sjeff for (tail = subplan = NULL;;) { 99219820Sjeff if ((next = yankexpr(planp)) == NULL) 100219820Sjeff errx(1, "(: missing closing ')'"); 101219820Sjeff /* 102219820Sjeff * If we find a closing ')' we store the collected 103219820Sjeff * subplan in our '(' node and convert the node to 104219820Sjeff * a f_expr. The ')' we found is ignored. Otherwise, 105219820Sjeff * we just continue to add whatever we get to our 106219820Sjeff * subplan. 107219820Sjeff */ 108219820Sjeff if (next->execute == f_closeparen) { 109219820Sjeff if (subplan == NULL) 110219820Sjeff errx(1, "(): empty inner expression"); 111219820Sjeff node->p_data[0] = subplan; 112219820Sjeff node->execute = f_expr; 113219820Sjeff break; 114219820Sjeff } else { 115219820Sjeff if (subplan == NULL) 116219820Sjeff tail = subplan = next; 117219820Sjeff else { 118219820Sjeff tail->next = next; 119219820Sjeff tail = next; 120219820Sjeff } 121219820Sjeff tail->next = NULL; 122219820Sjeff } 123219820Sjeff } 124219820Sjeff return (node); 125219820Sjeff} 126219820Sjeff 127219820Sjeff/* 128219820Sjeff * paren_squish -- 129219820Sjeff * replaces "parenthesized" plans in our search plan with "expr" nodes. 130219820Sjeff */ 131219820SjeffPLAN * 132219820Sjeffparen_squish(PLAN *plan) 133219820Sjeff{ 134219820Sjeff PLAN *expr; /* pointer to next expression */ 135219820Sjeff PLAN *tail; /* pointer to tail of result plan */ 136219820Sjeff PLAN *result; /* pointer to head of result plan */ 137219820Sjeff 138219820Sjeff result = tail = NULL; 139219820Sjeff 140219820Sjeff /* 141219820Sjeff * the basic idea is to have yankexpr do all our work and just 142219820Sjeff * collect its results together. 143219820Sjeff */ 144219820Sjeff while ((expr = yankexpr(&plan)) != NULL) { 145219820Sjeff /* 146219820Sjeff * if we find an unclaimed ')' it means there is a missing 147219820Sjeff * '(' someplace. 148219820Sjeff */ 149219820Sjeff if (expr->execute == f_closeparen) 150219820Sjeff errx(1, "): no beginning '('"); 151219820Sjeff 152219820Sjeff /* add the expression to our result plan */ 153219820Sjeff if (result == NULL) 154219820Sjeff tail = result = expr; 155219820Sjeff else { 156219820Sjeff tail->next = expr; 157219820Sjeff tail = expr; 158219820Sjeff } 159219820Sjeff tail->next = NULL; 160219820Sjeff } 161219820Sjeff return (result); 162219820Sjeff} 163219820Sjeff 164219820Sjeff/* 165219820Sjeff * not_squish -- 166219820Sjeff * compresses "!" expressions in our search plan. 167219820Sjeff */ 168219820SjeffPLAN * 169219820Sjeffnot_squish(PLAN *plan) 170219820Sjeff{ 171219820Sjeff PLAN *next; /* next node being processed */ 172219820Sjeff PLAN *node; /* temporary node used in f_not processing */ 173219820Sjeff PLAN *tail; /* pointer to tail of result plan */ 174219820Sjeff PLAN *result; /* pointer to head of result plan */ 175219820Sjeff 176219820Sjeff tail = result = NULL; 177 178 while ((next = yanknode(&plan))) { 179 /* 180 * if we encounter a ( expression ) then look for nots in 181 * the expr subplan. 182 */ 183 if (next->execute == f_expr) 184 next->p_data[0] = not_squish(next->p_data[0]); 185 186 /* 187 * if we encounter a not, then snag the next node and place 188 * it in the not's subplan. As an optimization we compress 189 * several not's to zero or one not. 190 */ 191 if (next->execute == f_not) { 192 int notlevel = 1; 193 194 node = yanknode(&plan); 195 while (node != NULL && node->execute == f_not) { 196 ++notlevel; 197 node = yanknode(&plan); 198 } 199 if (node == NULL) 200 errx(1, "!: no following expression"); 201 if (node->execute == f_or) 202 errx(1, "!: nothing between ! and -o"); 203 /* 204 * If we encounter ! ( expr ) then look for nots in 205 * the expr subplan. 206 */ 207 if (node->execute == f_expr) 208 node->p_data[0] = not_squish(node->p_data[0]); 209 if (notlevel % 2 != 1) 210 next = node; 211 else 212 next->p_data[0] = node; 213 } 214 215 /* add the node to our result plan */ 216 if (result == NULL) 217 tail = result = next; 218 else { 219 tail->next = next; 220 tail = next; 221 } 222 tail->next = NULL; 223 } 224 return (result); 225} 226 227/* 228 * or_squish -- 229 * compresses -o expressions in our search plan. 230 */ 231PLAN * 232or_squish(PLAN *plan) 233{ 234 PLAN *next; /* next node being processed */ 235 PLAN *tail; /* pointer to tail of result plan */ 236 PLAN *result; /* pointer to head of result plan */ 237 238 tail = result = next = NULL; 239 240 while ((next = yanknode(&plan)) != NULL) { 241 /* 242 * if we encounter a ( expression ) then look for or's in 243 * the expr subplan. 244 */ 245 if (next->execute == f_expr) 246 next->p_data[0] = or_squish(next->p_data[0]); 247 248 /* if we encounter a not then look for or's in the subplan */ 249 if (next->execute == f_not) 250 next->p_data[0] = or_squish(next->p_data[0]); 251 252 /* 253 * if we encounter an or, then place our collected plan in the 254 * or's first subplan and then recursively collect the 255 * remaining stuff into the second subplan and return the or. 256 */ 257 if (next->execute == f_or) { 258 if (result == NULL) 259 errx(1, "-o: no expression before -o"); 260 next->p_data[0] = result; 261 next->p_data[1] = or_squish(plan); 262 if (next->p_data[1] == NULL) 263 errx(1, "-o: no expression after -o"); 264 return (next); 265 } 266 267 /* add the node to our result plan */ 268 if (result == NULL) 269 tail = result = next; 270 else { 271 tail->next = next; 272 tail = next; 273 } 274 tail->next = NULL; 275 } 276 return (result); 277} 278