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 * 4. Neither the name of the University nor the names of its contributors 171590Srgrimes * may be used to endorse or promote products derived from this software 181590Srgrimes * without specific prior written permission. 191590Srgrimes * 201590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 211590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 221590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 231590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 241590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 251590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 261590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 271590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 281590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 291590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 301590Srgrimes * SUCH DAMAGE. 311590Srgrimes */ 321590Srgrimes 33207705Sdelphij#ifndef lint 34207705Sdelphij#if 0 35207705Sdelphijstatic char sccsid[] = "@(#)operator.c 8.1 (Berkeley) 6/6/93"; 36207705Sdelphij#endif 37207705Sdelphij#endif /* not lint */ 38207705Sdelphij 3993604Sobrien#include <sys/cdefs.h> 4093604Sobrien__FBSDID("$FreeBSD$"); 411590Srgrimes 421590Srgrimes#include <sys/types.h> 431590Srgrimes 441590Srgrimes#include <err.h> 451590Srgrimes#include <fts.h> 461590Srgrimes#include <stdio.h> 471590Srgrimes 481590Srgrimes#include "find.h" 498874Srgrimes 5092786Smarkmstatic PLAN *yanknode(PLAN **); 5192786Smarkmstatic PLAN *yankexpr(PLAN **); 5291400Sdwmalone 531590Srgrimes/* 541590Srgrimes * yanknode -- 551590Srgrimes * destructively removes the top from the plan 561590Srgrimes */ 571590Srgrimesstatic PLAN * 58116333Smarkmyanknode(PLAN **planp) 591590Srgrimes{ 601590Srgrimes PLAN *node; /* top node removed from the plan */ 618874Srgrimes 621590Srgrimes if ((node = (*planp)) == NULL) 631590Srgrimes return (NULL); 641590Srgrimes (*planp) = (*planp)->next; 651590Srgrimes node->next = NULL; 661590Srgrimes return (node); 671590Srgrimes} 688874Srgrimes 691590Srgrimes/* 701590Srgrimes * yankexpr -- 711590Srgrimes * Removes one expression from the plan. This is used mainly by 721590Srgrimes * paren_squish. In comments below, an expression is either a 7376250Sphk * simple node or a f_expr node containing a list of simple nodes. 741590Srgrimes */ 751590Srgrimesstatic PLAN * 76116333Smarkmyankexpr(PLAN **planp) 771590Srgrimes{ 7891400Sdwmalone PLAN *next; /* temp node holding subexpression results */ 791590Srgrimes PLAN *node; /* pointer to returned node or expression */ 801590Srgrimes PLAN *tail; /* pointer to tail of subplan */ 811590Srgrimes PLAN *subplan; /* pointer to head of ( ) expression */ 828874Srgrimes 831590Srgrimes /* first pull the top node from the plan */ 841590Srgrimes if ((node = yanknode(planp)) == NULL) 851590Srgrimes return (NULL); 868874Srgrimes 871590Srgrimes /* 881590Srgrimes * If the node is an '(' then we recursively slurp up expressions 891590Srgrimes * until we find its associated ')'. If it's a closing paren we 901590Srgrimes * just return it and unwind our recursion; all other nodes are 911590Srgrimes * complete expressions, so just return them. 921590Srgrimes */ 9376250Sphk if (node->execute == f_openparen) 941590Srgrimes for (tail = subplan = NULL;;) { 951590Srgrimes if ((next = yankexpr(planp)) == NULL) 9694558Scharnier errx(1, "(: missing closing ')'"); 971590Srgrimes /* 981590Srgrimes * If we find a closing ')' we store the collected 991590Srgrimes * subplan in our '(' node and convert the node to 10076250Sphk * a f_expr. The ')' we found is ignored. Otherwise, 1011590Srgrimes * we just continue to add whatever we get to our 1021590Srgrimes * subplan. 1031590Srgrimes */ 10476250Sphk if (next->execute == f_closeparen) { 1051590Srgrimes if (subplan == NULL) 1061590Srgrimes errx(1, "(): empty inner expression"); 1071590Srgrimes node->p_data[0] = subplan; 10876250Sphk node->execute = f_expr; 1091590Srgrimes break; 1101590Srgrimes } else { 1111590Srgrimes if (subplan == NULL) 1121590Srgrimes tail = subplan = next; 1131590Srgrimes else { 1141590Srgrimes tail->next = next; 1151590Srgrimes tail = next; 1161590Srgrimes } 1171590Srgrimes tail->next = NULL; 1181590Srgrimes } 1191590Srgrimes } 1201590Srgrimes return (node); 1211590Srgrimes} 1228874Srgrimes 1231590Srgrimes/* 1241590Srgrimes * paren_squish -- 12593212Scharnier * replaces "parenthesized" plans in our search plan with "expr" nodes. 1261590Srgrimes */ 1271590SrgrimesPLAN * 128116333Smarkmparen_squish(PLAN *plan) 1291590Srgrimes{ 13091400Sdwmalone PLAN *expr; /* pointer to next expression */ 13191400Sdwmalone PLAN *tail; /* pointer to tail of result plan */ 1321590Srgrimes PLAN *result; /* pointer to head of result plan */ 1338874Srgrimes 1341590Srgrimes result = tail = NULL; 1351590Srgrimes 1361590Srgrimes /* 1371590Srgrimes * the basic idea is to have yankexpr do all our work and just 13876250Sphk * collect its results together. 1391590Srgrimes */ 1401590Srgrimes while ((expr = yankexpr(&plan)) != NULL) { 1411590Srgrimes /* 1421590Srgrimes * if we find an unclaimed ')' it means there is a missing 1431590Srgrimes * '(' someplace. 1441590Srgrimes */ 14576250Sphk if (expr->execute == f_closeparen) 1461590Srgrimes errx(1, "): no beginning '('"); 1471590Srgrimes 1481590Srgrimes /* add the expression to our result plan */ 1491590Srgrimes if (result == NULL) 1501590Srgrimes tail = result = expr; 1511590Srgrimes else { 1521590Srgrimes tail->next = expr; 1531590Srgrimes tail = expr; 1541590Srgrimes } 1551590Srgrimes tail->next = NULL; 1561590Srgrimes } 1571590Srgrimes return (result); 1581590Srgrimes} 1598874Srgrimes 1601590Srgrimes/* 1611590Srgrimes * not_squish -- 1621590Srgrimes * compresses "!" expressions in our search plan. 1631590Srgrimes */ 1641590SrgrimesPLAN * 165116333Smarkmnot_squish(PLAN *plan) 1661590Srgrimes{ 16791400Sdwmalone PLAN *next; /* next node being processed */ 16891400Sdwmalone PLAN *node; /* temporary node used in f_not processing */ 16991400Sdwmalone PLAN *tail; /* pointer to tail of result plan */ 1701590Srgrimes PLAN *result; /* pointer to head of result plan */ 1718874Srgrimes 17276250Sphk tail = result = NULL; 1738874Srgrimes 17480235Sobrien while ((next = yanknode(&plan))) { 1751590Srgrimes /* 1761590Srgrimes * if we encounter a ( expression ) then look for nots in 1771590Srgrimes * the expr subplan. 1781590Srgrimes */ 17976250Sphk if (next->execute == f_expr) 1801590Srgrimes next->p_data[0] = not_squish(next->p_data[0]); 1811590Srgrimes 1821590Srgrimes /* 1831590Srgrimes * if we encounter a not, then snag the next node and place 1841590Srgrimes * it in the not's subplan. As an optimization we compress 1851590Srgrimes * several not's to zero or one not. 1861590Srgrimes */ 18776250Sphk if (next->execute == f_not) { 1881590Srgrimes int notlevel = 1; 1891590Srgrimes 1901590Srgrimes node = yanknode(&plan); 19176250Sphk while (node != NULL && node->execute == f_not) { 1921590Srgrimes ++notlevel; 1931590Srgrimes node = yanknode(&plan); 1941590Srgrimes } 1951590Srgrimes if (node == NULL) 1961590Srgrimes errx(1, "!: no following expression"); 19776250Sphk if (node->execute == f_or) 1981590Srgrimes errx(1, "!: nothing between ! and -o"); 19923614Sjoerg /* 20023614Sjoerg * If we encounter ! ( expr ) then look for nots in 20123614Sjoerg * the expr subplan. 20223614Sjoerg */ 20376250Sphk if (node->execute == f_expr) 20423614Sjoerg node->p_data[0] = not_squish(node->p_data[0]); 2051590Srgrimes if (notlevel % 2 != 1) 2061590Srgrimes next = node; 2071590Srgrimes else 2081590Srgrimes next->p_data[0] = node; 2091590Srgrimes } 2101590Srgrimes 2111590Srgrimes /* add the node to our result plan */ 2121590Srgrimes if (result == NULL) 2131590Srgrimes tail = result = next; 2141590Srgrimes else { 2151590Srgrimes tail->next = next; 2161590Srgrimes tail = next; 2171590Srgrimes } 2181590Srgrimes tail->next = NULL; 2191590Srgrimes } 2201590Srgrimes return (result); 2211590Srgrimes} 2228874Srgrimes 2231590Srgrimes/* 2241590Srgrimes * or_squish -- 2251590Srgrimes * compresses -o expressions in our search plan. 2261590Srgrimes */ 2271590SrgrimesPLAN * 228116333Smarkmor_squish(PLAN *plan) 2291590Srgrimes{ 23091400Sdwmalone PLAN *next; /* next node being processed */ 23191400Sdwmalone PLAN *tail; /* pointer to tail of result plan */ 2321590Srgrimes PLAN *result; /* pointer to head of result plan */ 2338874Srgrimes 2341590Srgrimes tail = result = next = NULL; 2358874Srgrimes 2361590Srgrimes while ((next = yanknode(&plan)) != NULL) { 2371590Srgrimes /* 2381590Srgrimes * if we encounter a ( expression ) then look for or's in 2391590Srgrimes * the expr subplan. 2401590Srgrimes */ 24176250Sphk if (next->execute == f_expr) 2421590Srgrimes next->p_data[0] = or_squish(next->p_data[0]); 2431590Srgrimes 24423614Sjoerg /* if we encounter a not then look for or's in the subplan */ 24576250Sphk if (next->execute == f_not) 2461590Srgrimes next->p_data[0] = or_squish(next->p_data[0]); 2471590Srgrimes 2481590Srgrimes /* 2491590Srgrimes * if we encounter an or, then place our collected plan in the 2501590Srgrimes * or's first subplan and then recursively collect the 2511590Srgrimes * remaining stuff into the second subplan and return the or. 2521590Srgrimes */ 25376250Sphk if (next->execute == f_or) { 2541590Srgrimes if (result == NULL) 2551590Srgrimes errx(1, "-o: no expression before -o"); 2561590Srgrimes next->p_data[0] = result; 2571590Srgrimes next->p_data[1] = or_squish(plan); 2581590Srgrimes if (next->p_data[1] == NULL) 2591590Srgrimes errx(1, "-o: no expression after -o"); 2601590Srgrimes return (next); 2611590Srgrimes } 2621590Srgrimes 2631590Srgrimes /* add the node to our result plan */ 2641590Srgrimes if (result == NULL) 2651590Srgrimes tail = result = next; 2661590Srgrimes else { 2671590Srgrimes tail->next = next; 2681590Srgrimes tail = next; 2691590Srgrimes } 2701590Srgrimes tail->next = NULL; 2711590Srgrimes } 2721590Srgrimes return (result); 2731590Srgrimes} 274