operator.c revision 256281
1254721Semaste/*- 2254721Semaste * Copyright (c) 1990, 1993 3254721Semaste * The Regents of the University of California. All rights reserved. 4254721Semaste * 5254721Semaste * This code is derived from software contributed to Berkeley by 6254721Semaste * Cimarron D. Taylor of the University of California, Berkeley. 7254721Semaste * 8254721Semaste * Redistribution and use in source and binary forms, with or without 9254721Semaste * modification, are permitted provided that the following conditions 10254721Semaste * are met: 11254721Semaste * 1. Redistributions of source code must retain the above copyright 12254721Semaste * notice, this list of conditions and the following disclaimer. 13254721Semaste * 2. Redistributions in binary form must reproduce the above copyright 14254721Semaste * notice, this list of conditions and the following disclaimer in the 15254721Semaste * documentation and/or other materials provided with the distribution. 16254721Semaste * 4. Neither the name of the University nor the names of its contributors 17254721Semaste * may be used to endorse or promote products derived from this software 18254721Semaste * without specific prior written permission. 19254721Semaste * 20254721Semaste * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21254721Semaste * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22254721Semaste * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23254721Semaste * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24254721Semaste * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25254721Semaste * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26254721Semaste * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27254721Semaste * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28254721Semaste * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29254721Semaste * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30254721Semaste * SUCH DAMAGE. 31254721Semaste */ 32254721Semaste 33254721Semaste#ifndef lint 34254721Semaste#if 0 35254721Semastestatic char sccsid[] = "@(#)operator.c 8.1 (Berkeley) 6/6/93"; 36254721Semaste#endif 37254721Semaste#endif /* not lint */ 38254721Semaste 39254721Semaste#include <sys/cdefs.h> 40254721Semaste__FBSDID("$FreeBSD: stable/10/usr.bin/find/operator.c 216370 2010-12-11 08:32:16Z joel $"); 41254721Semaste 42254721Semaste#include <sys/types.h> 43254721Semaste 44254721Semaste#include <err.h> 45254721Semaste#include <fts.h> 46254721Semaste#include <stdio.h> 47254721Semaste 48254721Semaste#include "find.h" 49254721Semaste 50254721Semastestatic PLAN *yanknode(PLAN **); 51254721Semastestatic PLAN *yankexpr(PLAN **); 52254721Semaste 53254721Semaste/* 54254721Semaste * yanknode -- 55254721Semaste * destructively removes the top from the plan 56254721Semaste */ 57254721Semastestatic PLAN * 58254721Semasteyanknode(PLAN **planp) 59254721Semaste{ 60254721Semaste PLAN *node; /* top node removed from the plan */ 61254721Semaste 62254721Semaste if ((node = (*planp)) == NULL) 63254721Semaste return (NULL); 64254721Semaste (*planp) = (*planp)->next; 65254721Semaste node->next = NULL; 66254721Semaste return (node); 67254721Semaste} 68254721Semaste 69254721Semaste/* 70254721Semaste * yankexpr -- 71254721Semaste * Removes one expression from the plan. This is used mainly by 72254721Semaste * paren_squish. In comments below, an expression is either a 73254721Semaste * simple node or a f_expr node containing a list of simple nodes. 74254721Semaste */ 75254721Semastestatic PLAN * 76254721Semasteyankexpr(PLAN **planp) 77254721Semaste{ 78254721Semaste PLAN *next; /* temp node holding subexpression results */ 79254721Semaste PLAN *node; /* pointer to returned node or expression */ 80254721Semaste PLAN *tail; /* pointer to tail of subplan */ 81254721Semaste PLAN *subplan; /* pointer to head of ( ) expression */ 82254721Semaste 83254721Semaste /* first pull the top node from the plan */ 84254721Semaste if ((node = yanknode(planp)) == NULL) 85254721Semaste return (NULL); 86254721Semaste 87254721Semaste /* 88254721Semaste * If the node is an '(' then we recursively slurp up expressions 89254721Semaste * until we find its associated ')'. If it's a closing paren we 90254721Semaste * just return it and unwind our recursion; all other nodes are 91254721Semaste * complete expressions, so just return them. 92254721Semaste */ 93254721Semaste if (node->execute == f_openparen) 94254721Semaste for (tail = subplan = NULL;;) { 95254721Semaste if ((next = yankexpr(planp)) == NULL) 96254721Semaste errx(1, "(: missing closing ')'"); 97254721Semaste /* 98254721Semaste * If we find a closing ')' we store the collected 99254721Semaste * subplan in our '(' node and convert the node to 100254721Semaste * a f_expr. The ')' we found is ignored. Otherwise, 101254721Semaste * we just continue to add whatever we get to our 102254721Semaste * subplan. 103254721Semaste */ 104254721Semaste if (next->execute == f_closeparen) { 105254721Semaste if (subplan == NULL) 106254721Semaste errx(1, "(): empty inner expression"); 107254721Semaste node->p_data[0] = subplan; 108254721Semaste node->execute = f_expr; 109254721Semaste break; 110254721Semaste } else { 111254721Semaste if (subplan == NULL) 112254721Semaste tail = subplan = next; 113254721Semaste else { 114254721Semaste tail->next = next; 115254721Semaste tail = next; 116254721Semaste } 117254721Semaste tail->next = NULL; 118254721Semaste } 119254721Semaste } 120254721Semaste return (node); 121254721Semaste} 122254721Semaste 123254721Semaste/* 124254721Semaste * paren_squish -- 125254721Semaste * replaces "parenthesized" plans in our search plan with "expr" nodes. 126254721Semaste */ 127254721SemastePLAN * 128254721Semasteparen_squish(PLAN *plan) 129254721Semaste{ 130254721Semaste PLAN *expr; /* pointer to next expression */ 131254721Semaste PLAN *tail; /* pointer to tail of result plan */ 132254721Semaste PLAN *result; /* pointer to head of result plan */ 133254721Semaste 134254721Semaste result = tail = NULL; 135254721Semaste 136254721Semaste /* 137254721Semaste * the basic idea is to have yankexpr do all our work and just 138254721Semaste * collect its results together. 139254721Semaste */ 140254721Semaste while ((expr = yankexpr(&plan)) != NULL) { 141254721Semaste /* 142254721Semaste * if we find an unclaimed ')' it means there is a missing 143254721Semaste * '(' someplace. 144254721Semaste */ 145254721Semaste if (expr->execute == f_closeparen) 146254721Semaste errx(1, "): no beginning '('"); 147254721Semaste 148254721Semaste /* add the expression to our result plan */ 149254721Semaste if (result == NULL) 150254721Semaste tail = result = expr; 151254721Semaste else { 152254721Semaste tail->next = expr; 153254721Semaste tail = expr; 154254721Semaste } 155254721Semaste tail->next = NULL; 156254721Semaste } 157254721Semaste return (result); 158254721Semaste} 159254721Semaste 160254721Semaste/* 161254721Semaste * not_squish -- 162254721Semaste * compresses "!" expressions in our search plan. 163254721Semaste */ 164254721SemastePLAN * 165254721Semastenot_squish(PLAN *plan) 166254721Semaste{ 167254721Semaste PLAN *next; /* next node being processed */ 168254721Semaste PLAN *node; /* temporary node used in f_not processing */ 169254721Semaste PLAN *tail; /* pointer to tail of result plan */ 170254721Semaste PLAN *result; /* pointer to head of result plan */ 171254721Semaste 172254721Semaste tail = result = NULL; 173254721Semaste 174254721Semaste while ((next = yanknode(&plan))) { 175254721Semaste /* 176254721Semaste * if we encounter a ( expression ) then look for nots in 177254721Semaste * the expr subplan. 178254721Semaste */ 179254721Semaste if (next->execute == f_expr) 180254721Semaste next->p_data[0] = not_squish(next->p_data[0]); 181254721Semaste 182254721Semaste /* 183254721Semaste * if we encounter a not, then snag the next node and place 184254721Semaste * it in the not's subplan. As an optimization we compress 185 * several not's to zero or one not. 186 */ 187 if (next->execute == f_not) { 188 int notlevel = 1; 189 190 node = yanknode(&plan); 191 while (node != NULL && node->execute == f_not) { 192 ++notlevel; 193 node = yanknode(&plan); 194 } 195 if (node == NULL) 196 errx(1, "!: no following expression"); 197 if (node->execute == f_or) 198 errx(1, "!: nothing between ! and -o"); 199 /* 200 * If we encounter ! ( expr ) then look for nots in 201 * the expr subplan. 202 */ 203 if (node->execute == f_expr) 204 node->p_data[0] = not_squish(node->p_data[0]); 205 if (notlevel % 2 != 1) 206 next = node; 207 else 208 next->p_data[0] = node; 209 } 210 211 /* add the node to our result plan */ 212 if (result == NULL) 213 tail = result = next; 214 else { 215 tail->next = next; 216 tail = next; 217 } 218 tail->next = NULL; 219 } 220 return (result); 221} 222 223/* 224 * or_squish -- 225 * compresses -o expressions in our search plan. 226 */ 227PLAN * 228or_squish(PLAN *plan) 229{ 230 PLAN *next; /* next node being processed */ 231 PLAN *tail; /* pointer to tail of result plan */ 232 PLAN *result; /* pointer to head of result plan */ 233 234 tail = result = next = NULL; 235 236 while ((next = yanknode(&plan)) != NULL) { 237 /* 238 * if we encounter a ( expression ) then look for or's in 239 * the expr subplan. 240 */ 241 if (next->execute == f_expr) 242 next->p_data[0] = or_squish(next->p_data[0]); 243 244 /* if we encounter a not then look for or's in the subplan */ 245 if (next->execute == f_not) 246 next->p_data[0] = or_squish(next->p_data[0]); 247 248 /* 249 * if we encounter an or, then place our collected plan in the 250 * or's first subplan and then recursively collect the 251 * remaining stuff into the second subplan and return the or. 252 */ 253 if (next->execute == f_or) { 254 if (result == NULL) 255 errx(1, "-o: no expression before -o"); 256 next->p_data[0] = result; 257 next->p_data[1] = or_squish(plan); 258 if (next->p_data[1] == NULL) 259 errx(1, "-o: no expression after -o"); 260 return (next); 261 } 262 263 /* add the node to our result plan */ 264 if (result == NULL) 265 tail = result = next; 266 else { 267 tail->next = next; 268 tail = next; 269 } 270 tail->next = NULL; 271 } 272 return (result); 273} 274