Annotation of src/usr.bin/find/operator.c, Revision 1.5
1.5 ! millert 1: /* $OpenBSD: operator.c,v 1.4 1999/01/04 21:36:01 millert Exp $ */
1.2 deraadt 2:
1.1 deraadt 3: /*-
4: * Copyright (c) 1990, 1993
5: * The Regents of the University of California. All rights reserved.
6: *
7: * This code is derived from software contributed to Berkeley by
8: * Cimarron D. Taylor of the University of California, Berkeley.
9: *
10: * Redistribution and use in source and binary forms, with or without
11: * modification, are permitted provided that the following conditions
12: * are met:
13: * 1. Redistributions of source code must retain the above copyright
14: * notice, this list of conditions and the following disclaimer.
15: * 2. Redistributions in binary form must reproduce the above copyright
16: * notice, this list of conditions and the following disclaimer in the
17: * documentation and/or other materials provided with the distribution.
18: * 3. All advertising materials mentioning features or use of this software
19: * must display the following acknowledgement:
20: * This product includes software developed by the University of
21: * California, Berkeley and its contributors.
22: * 4. Neither the name of the University nor the names of its contributors
23: * may be used to endorse or promote products derived from this software
24: * without specific prior written permission.
25: *
26: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
27: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
30: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
31: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
32: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
33: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
35: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36: * SUCH DAMAGE.
37: */
38:
39: #ifndef lint
40: /*static char sccsid[] = "from: @(#)operator.c 8.1 (Berkeley) 6/6/93";*/
1.5 ! millert 41: static char rcsid[] = "$OpenBSD: operator.c,v 1.4 1999/01/04 21:36:01 millert Exp $";
1.1 deraadt 42: #endif /* not lint */
43:
44: #include <sys/types.h>
1.5 ! millert 45: #include <sys/stat.h>
1.1 deraadt 46:
47: #include <err.h>
48: #include <fts.h>
49: #include <stdio.h>
50:
51: #include "find.h"
52:
53: /*
54: * yanknode --
55: * destructively removes the top from the plan
56: */
57: static PLAN *
58: yanknode(planp)
59: PLAN **planp; /* pointer to top of plan (modified) */
60: {
61: PLAN *node; /* top node removed from the plan */
62:
63: if ((node = (*planp)) == NULL)
64: return (NULL);
65: (*planp) = (*planp)->next;
66: node->next = NULL;
67: return (node);
68: }
69:
70: /*
71: * yankexpr --
72: * Removes one expression from the plan. This is used mainly by
73: * paren_squish. In comments below, an expression is either a
74: * simple node or a N_EXPR node containing a list of simple nodes.
75: */
76: static PLAN *
77: yankexpr(planp)
78: PLAN **planp; /* pointer to top of plan (modified) */
79: {
80: register PLAN *next; /* temp node holding subexpression results */
81: PLAN *node; /* pointer to returned node or expression */
82: PLAN *tail; /* pointer to tail of subplan */
83: PLAN *subplan; /* pointer to head of ( ) expression */
84: int f_expr();
85:
86: /* first pull the top node from the plan */
87: if ((node = yanknode(planp)) == NULL)
88: return (NULL);
89:
90: /*
91: * If the node is an '(' then we recursively slurp up expressions
92: * until we find its associated ')'. If it's a closing paren we
93: * just return it and unwind our recursion; all other nodes are
94: * complete expressions, so just return them.
95: */
96: if (node->type == N_OPENPAREN)
97: for (tail = subplan = NULL;;) {
98: if ((next = yankexpr(planp)) == NULL)
99: err(1, "(: missing closing ')'");
100: /*
101: * If we find a closing ')' we store the collected
102: * subplan in our '(' node and convert the node to
103: * a N_EXPR. The ')' we found is ignored. Otherwise,
104: * we just continue to add whatever we get to our
105: * subplan.
106: */
107: if (next->type == N_CLOSEPAREN) {
108: if (subplan == NULL)
109: errx(1, "(): empty inner expression");
110: node->p_data[0] = subplan;
111: node->type = N_EXPR;
112: node->eval = f_expr;
113: break;
114: } else {
115: if (subplan == NULL)
116: tail = subplan = next;
117: else {
118: tail->next = next;
119: tail = next;
120: }
121: tail->next = NULL;
122: }
123: }
124: return (node);
125: }
126:
127: /*
128: * paren_squish --
129: * replaces "parentheisized" plans in our search plan with "expr" nodes.
130: */
131: PLAN *
132: paren_squish(plan)
133: PLAN *plan; /* plan with ( ) nodes */
134: {
135: register PLAN *expr; /* pointer to next expression */
136: register PLAN *tail; /* pointer to tail of result plan */
137: PLAN *result; /* pointer to head of result plan */
138:
139: result = tail = NULL;
140:
141: /*
142: * the basic idea is to have yankexpr do all our work and just
143: * collect it's results together.
144: */
145: while ((expr = yankexpr(&plan)) != NULL) {
146: /*
147: * if we find an unclaimed ')' it means there is a missing
148: * '(' someplace.
149: */
150: if (expr->type == N_CLOSEPAREN)
151: errx(1, "): no beginning '('");
152:
153: /* add the expression to our result plan */
154: if (result == NULL)
155: tail = result = expr;
156: else {
157: tail->next = expr;
158: tail = expr;
159: }
160: tail->next = NULL;
161: }
162: return (result);
163: }
164:
165: /*
166: * not_squish --
167: * compresses "!" expressions in our search plan.
168: */
169: PLAN *
170: not_squish(plan)
171: PLAN *plan; /* plan to process */
172: {
173: register PLAN *next; /* next node being processed */
174: register PLAN *node; /* temporary node used in N_NOT processing */
175: register PLAN *tail; /* pointer to tail of result plan */
176: PLAN *result; /* pointer to head of result plan */
177:
178: tail = result = next = NULL;
179:
180: while ((next = yanknode(&plan)) != NULL) {
181: /*
182: * if we encounter a ( expression ) then look for nots in
183: * the expr subplan.
184: */
185: if (next->type == N_EXPR)
186: next->p_data[0] = not_squish(next->p_data[0]);
187:
188: /*
189: * if we encounter a not, then snag the next node and place
190: * it in the not's subplan. As an optimization we compress
191: * several not's to zero or one not.
192: */
193: if (next->type == N_NOT) {
194: int notlevel = 1;
195:
196: node = yanknode(&plan);
1.3 deraadt 197: while (node != NULL && node->type == N_NOT) {
1.1 deraadt 198: ++notlevel;
199: node = yanknode(&plan);
200: }
201: if (node == NULL)
202: errx(1, "!: no following expression");
203: if (node->type == N_OR)
204: errx(1, "!: nothing between ! and -o");
1.4 millert 205: if (node->type == N_EXPR)
206: node = not_squish(node);
1.1 deraadt 207: if (notlevel % 2 != 1)
208: next = node;
209: else
210: next->p_data[0] = node;
211: }
212:
213: /* add the node to our result plan */
214: if (result == NULL)
215: tail = result = next;
216: else {
217: tail->next = next;
218: tail = next;
219: }
220: tail->next = NULL;
221: }
222: return (result);
223: }
224:
225: /*
226: * or_squish --
227: * compresses -o expressions in our search plan.
228: */
229: PLAN *
230: or_squish(plan)
231: PLAN *plan; /* plan with ors to be squished */
232: {
233: register PLAN *next; /* next node being processed */
234: register PLAN *tail; /* pointer to tail of result plan */
235: PLAN *result; /* pointer to head of result plan */
236:
237: tail = result = next = NULL;
238:
239: while ((next = yanknode(&plan)) != NULL) {
240: /*
241: * if we encounter a ( expression ) then look for or's in
242: * the expr subplan.
243: */
244: if (next->type == N_EXPR)
245: next->p_data[0] = or_squish(next->p_data[0]);
246:
247: /* if we encounter a not then look for not's in the subplan */
248: if (next->type == N_NOT)
249: next->p_data[0] = or_squish(next->p_data[0]);
250:
251: /*
252: * if we encounter an or, then place our collected plan in the
253: * or's first subplan and then recursively collect the
254: * remaining stuff into the second subplan and return the or.
255: */
256: if (next->type == N_OR) {
257: if (result == NULL)
258: errx(1, "-o: no expression before -o");
259: next->p_data[0] = result;
260: next->p_data[1] = or_squish(plan);
261: if (next->p_data[1] == NULL)
262: errx(1, "-o: no expression after -o");
263: return (next);
264: }
265:
266: /* add the node to our result plan */
267: if (result == NULL)
268: tail = result = next;
269: else {
270: tail->next = next;
271: tail = next;
272: }
273: tail->next = NULL;
274: }
275: return (result);
276: }