operator.c revision 91400
11590Srgrimes/*- 21590Srgrimes * Copyright (c) 1990, 1993 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * This code is derived from software contributed to Berkeley by 61590Srgrimes * Cimarron D. Taylor of the University of California, Berkeley. 71590Srgrimes * 81590Srgrimes * Redistribution and use in source and binary forms, with or without 91590Srgrimes * modification, are permitted provided that the following conditions 101590Srgrimes * are met: 111590Srgrimes * 1. Redistributions of source code must retain the above copyright 121590Srgrimes * notice, this list of conditions and the following disclaimer. 131590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer in the 151590Srgrimes * documentation and/or other materials provided with the distribution. 161590Srgrimes * 3. All advertising materials mentioning features or use of this software 171590Srgrimes * must display the following acknowledgement: 181590Srgrimes * This product includes software developed by the University of 191590Srgrimes * California, Berkeley and its contributors. 201590Srgrimes * 4. Neither the name of the University nor the names of its contributors 211590Srgrimes * may be used to endorse or promote products derived from this software 221590Srgrimes * without specific prior written permission. 231590Srgrimes * 241590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341590Srgrimes * SUCH DAMAGE. 351590Srgrimes */ 361590Srgrimes 371590Srgrimes#ifndef lint 3861575Sroberto#if 0 391590Srgrimesstatic char sccsid[] = "@(#)operator.c 8.1 (Berkeley) 6/6/93"; 4061575Sroberto#else 4161575Srobertostatic const char rcsid[] = 4261575Sroberto "$FreeBSD: head/usr.bin/find/operator.c 91400 2002-02-27 17:57:00Z dwmalone $"; 4361575Sroberto#endif 441590Srgrimes#endif /* not lint */ 451590Srgrimes 461590Srgrimes#include <sys/types.h> 471590Srgrimes 481590Srgrimes#include <err.h> 491590Srgrimes#include <fts.h> 501590Srgrimes#include <stdio.h> 511590Srgrimes 521590Srgrimes#include "find.h" 538874Srgrimes 5491400Sdwmalonestatic PLAN *yanknode __P((PLAN **)); 5591400Sdwmalonestatic PLAN *yankexpr __P((PLAN **)); 5691400Sdwmalone 571590Srgrimes/* 581590Srgrimes * yanknode -- 591590Srgrimes * destructively removes the top from the plan 601590Srgrimes */ 611590Srgrimesstatic PLAN * 628874Srgrimesyanknode(planp) 631590Srgrimes PLAN **planp; /* pointer to top of plan (modified) */ 641590Srgrimes{ 651590Srgrimes PLAN *node; /* top node removed from the plan */ 668874Srgrimes 671590Srgrimes if ((node = (*planp)) == NULL) 681590Srgrimes return (NULL); 691590Srgrimes (*planp) = (*planp)->next; 701590Srgrimes node->next = NULL; 711590Srgrimes return (node); 721590Srgrimes} 738874Srgrimes 741590Srgrimes/* 751590Srgrimes * yankexpr -- 761590Srgrimes * Removes one expression from the plan. This is used mainly by 771590Srgrimes * paren_squish. In comments below, an expression is either a 7876250Sphk * simple node or a f_expr node containing a list of simple nodes. 791590Srgrimes */ 801590Srgrimesstatic PLAN * 818874Srgrimesyankexpr(planp) 821590Srgrimes PLAN **planp; /* pointer to top of plan (modified) */ 831590Srgrimes{ 8491400Sdwmalone PLAN *next; /* temp node holding subexpression results */ 851590Srgrimes PLAN *node; /* pointer to returned node or expression */ 861590Srgrimes PLAN *tail; /* pointer to tail of subplan */ 871590Srgrimes PLAN *subplan; /* pointer to head of ( ) expression */ 888874Srgrimes 891590Srgrimes /* first pull the top node from the plan */ 901590Srgrimes if ((node = yanknode(planp)) == NULL) 911590Srgrimes return (NULL); 928874Srgrimes 931590Srgrimes /* 941590Srgrimes * If the node is an '(' then we recursively slurp up expressions 951590Srgrimes * until we find its associated ')'. If it's a closing paren we 961590Srgrimes * just return it and unwind our recursion; all other nodes are 971590Srgrimes * complete expressions, so just return them. 981590Srgrimes */ 9976250Sphk if (node->execute == f_openparen) 1001590Srgrimes for (tail = subplan = NULL;;) { 1011590Srgrimes if ((next = yankexpr(planp)) == NULL) 1021590Srgrimes err(1, "(: missing closing ')'"); 1031590Srgrimes /* 1041590Srgrimes * If we find a closing ')' we store the collected 1051590Srgrimes * subplan in our '(' node and convert the node to 10676250Sphk * a f_expr. The ')' we found is ignored. Otherwise, 1071590Srgrimes * we just continue to add whatever we get to our 1081590Srgrimes * subplan. 1091590Srgrimes */ 11076250Sphk if (next->execute == f_closeparen) { 1111590Srgrimes if (subplan == NULL) 1121590Srgrimes errx(1, "(): empty inner expression"); 1131590Srgrimes node->p_data[0] = subplan; 11476250Sphk node->execute = f_expr; 1151590Srgrimes break; 1161590Srgrimes } else { 1171590Srgrimes if (subplan == NULL) 1181590Srgrimes tail = subplan = next; 1191590Srgrimes else { 1201590Srgrimes tail->next = next; 1211590Srgrimes tail = next; 1221590Srgrimes } 1231590Srgrimes tail->next = NULL; 1241590Srgrimes } 1251590Srgrimes } 1261590Srgrimes return (node); 1271590Srgrimes} 1288874Srgrimes 1291590Srgrimes/* 1301590Srgrimes * paren_squish -- 1311590Srgrimes * replaces "parentheisized" plans in our search plan with "expr" nodes. 1321590Srgrimes */ 1331590SrgrimesPLAN * 1341590Srgrimesparen_squish(plan) 1351590Srgrimes PLAN *plan; /* plan with ( ) nodes */ 1361590Srgrimes{ 13791400Sdwmalone PLAN *expr; /* pointer to next expression */ 13891400Sdwmalone PLAN *tail; /* pointer to tail of result plan */ 1391590Srgrimes PLAN *result; /* pointer to head of result plan */ 1408874Srgrimes 1411590Srgrimes result = tail = NULL; 1421590Srgrimes 1431590Srgrimes /* 1441590Srgrimes * the basic idea is to have yankexpr do all our work and just 14576250Sphk * collect its results together. 1461590Srgrimes */ 1471590Srgrimes while ((expr = yankexpr(&plan)) != NULL) { 1481590Srgrimes /* 1491590Srgrimes * if we find an unclaimed ')' it means there is a missing 1501590Srgrimes * '(' someplace. 1511590Srgrimes */ 15276250Sphk if (expr->execute == f_closeparen) 1531590Srgrimes errx(1, "): no beginning '('"); 1541590Srgrimes 1551590Srgrimes /* add the expression to our result plan */ 1561590Srgrimes if (result == NULL) 1571590Srgrimes tail = result = expr; 1581590Srgrimes else { 1591590Srgrimes tail->next = expr; 1601590Srgrimes tail = expr; 1611590Srgrimes } 1621590Srgrimes tail->next = NULL; 1631590Srgrimes } 1641590Srgrimes return (result); 1651590Srgrimes} 1668874Srgrimes 1671590Srgrimes/* 1681590Srgrimes * not_squish -- 1691590Srgrimes * compresses "!" expressions in our search plan. 1701590Srgrimes */ 1711590SrgrimesPLAN * 1721590Srgrimesnot_squish(plan) 1731590Srgrimes PLAN *plan; /* plan to process */ 1741590Srgrimes{ 17591400Sdwmalone PLAN *next; /* next node being processed */ 17691400Sdwmalone PLAN *node; /* temporary node used in f_not processing */ 17791400Sdwmalone PLAN *tail; /* pointer to tail of result plan */ 1781590Srgrimes PLAN *result; /* pointer to head of result plan */ 1798874Srgrimes 18076250Sphk tail = result = NULL; 1818874Srgrimes 18280235Sobrien while ((next = yanknode(&plan))) { 1831590Srgrimes /* 1841590Srgrimes * if we encounter a ( expression ) then look for nots in 1851590Srgrimes * the expr subplan. 1861590Srgrimes */ 18776250Sphk if (next->execute == f_expr) 1881590Srgrimes next->p_data[0] = not_squish(next->p_data[0]); 1891590Srgrimes 1901590Srgrimes /* 1911590Srgrimes * if we encounter a not, then snag the next node and place 1921590Srgrimes * it in the not's subplan. As an optimization we compress 1931590Srgrimes * several not's to zero or one not. 1941590Srgrimes */ 19576250Sphk if (next->execute == f_not) { 1961590Srgrimes int notlevel = 1; 1971590Srgrimes 1981590Srgrimes node = yanknode(&plan); 19976250Sphk while (node != NULL && node->execute == f_not) { 2001590Srgrimes ++notlevel; 2011590Srgrimes node = yanknode(&plan); 2021590Srgrimes } 2031590Srgrimes if (node == NULL) 2041590Srgrimes errx(1, "!: no following expression"); 20576250Sphk if (node->execute == f_or) 2061590Srgrimes errx(1, "!: nothing between ! and -o"); 20723614Sjoerg /* 20823614Sjoerg * If we encounter ! ( expr ) then look for nots in 20923614Sjoerg * the expr subplan. 21023614Sjoerg */ 21176250Sphk if (node->execute == f_expr) 21223614Sjoerg node->p_data[0] = not_squish(node->p_data[0]); 2131590Srgrimes if (notlevel % 2 != 1) 2141590Srgrimes next = node; 2151590Srgrimes else 2161590Srgrimes next->p_data[0] = node; 2171590Srgrimes } 2181590Srgrimes 2191590Srgrimes /* add the node to our result plan */ 2201590Srgrimes if (result == NULL) 2211590Srgrimes tail = result = next; 2221590Srgrimes else { 2231590Srgrimes tail->next = next; 2241590Srgrimes tail = next; 2251590Srgrimes } 2261590Srgrimes tail->next = NULL; 2271590Srgrimes } 2281590Srgrimes return (result); 2291590Srgrimes} 2308874Srgrimes 2311590Srgrimes/* 2321590Srgrimes * or_squish -- 2331590Srgrimes * compresses -o expressions in our search plan. 2341590Srgrimes */ 2351590SrgrimesPLAN * 2361590Srgrimesor_squish(plan) 2371590Srgrimes PLAN *plan; /* plan with ors to be squished */ 2381590Srgrimes{ 23991400Sdwmalone PLAN *next; /* next node being processed */ 24091400Sdwmalone PLAN *tail; /* pointer to tail of result plan */ 2411590Srgrimes PLAN *result; /* pointer to head of result plan */ 2428874Srgrimes 2431590Srgrimes tail = result = next = NULL; 2448874Srgrimes 2451590Srgrimes while ((next = yanknode(&plan)) != NULL) { 2461590Srgrimes /* 2471590Srgrimes * if we encounter a ( expression ) then look for or's in 2481590Srgrimes * the expr subplan. 2491590Srgrimes */ 25076250Sphk if (next->execute == f_expr) 2511590Srgrimes next->p_data[0] = or_squish(next->p_data[0]); 2521590Srgrimes 25323614Sjoerg /* if we encounter a not then look for or's in the subplan */ 25476250Sphk if (next->execute == f_not) 2551590Srgrimes next->p_data[0] = or_squish(next->p_data[0]); 2561590Srgrimes 2571590Srgrimes /* 2581590Srgrimes * if we encounter an or, then place our collected plan in the 2591590Srgrimes * or's first subplan and then recursively collect the 2601590Srgrimes * remaining stuff into the second subplan and return the or. 2611590Srgrimes */ 26276250Sphk if (next->execute == f_or) { 2631590Srgrimes if (result == NULL) 2641590Srgrimes errx(1, "-o: no expression before -o"); 2651590Srgrimes next->p_data[0] = result; 2661590Srgrimes next->p_data[1] = or_squish(plan); 2671590Srgrimes if (next->p_data[1] == NULL) 2681590Srgrimes errx(1, "-o: no expression after -o"); 2691590Srgrimes return (next); 2701590Srgrimes } 2711590Srgrimes 2721590Srgrimes /* add the node to our result plan */ 2731590Srgrimes if (result == NULL) 2741590Srgrimes tail = result = next; 2751590Srgrimes else { 2761590Srgrimes tail->next = next; 2771590Srgrimes tail = next; 2781590Srgrimes } 2791590Srgrimes tail->next = NULL; 2801590Srgrimes } 2811590Srgrimes return (result); 2821590Srgrimes} 283