Annotation of src/usr.bin/find/operator.c, Revision 1.4
1.4 ! millert 1: /* $OpenBSD: operator.c,v 1.3 1998/08/11 02:53:04 deraadt 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.4 ! millert 41: static char rcsid[] = "$OpenBSD: operator.c,v 1.3 1998/08/11 02:53:04 deraadt Exp $";
1.1 deraadt 42: #endif /* not lint */
43:
44: #include <sys/types.h>
45:
46: #include <err.h>
47: #include <fts.h>
48: #include <stdio.h>
49:
50: #include "find.h"
51:
52: /*
53: * yanknode --
54: * destructively removes the top from the plan
55: */
56: static PLAN *
57: yanknode(planp)
58: PLAN **planp; /* pointer to top of plan (modified) */
59: {
60: PLAN *node; /* top node removed from the plan */
61:
62: if ((node = (*planp)) == NULL)
63: return (NULL);
64: (*planp) = (*planp)->next;
65: node->next = NULL;
66: return (node);
67: }
68:
69: /*
70: * yankexpr --
71: * Removes one expression from the plan. This is used mainly by
72: * paren_squish. In comments below, an expression is either a
73: * simple node or a N_EXPR node containing a list of simple nodes.
74: */
75: static PLAN *
76: yankexpr(planp)
77: PLAN **planp; /* pointer to top of plan (modified) */
78: {
79: register PLAN *next; /* temp node holding subexpression results */
80: PLAN *node; /* pointer to returned node or expression */
81: PLAN *tail; /* pointer to tail of subplan */
82: PLAN *subplan; /* pointer to head of ( ) expression */
83: int f_expr();
84:
85: /* first pull the top node from the plan */
86: if ((node = yanknode(planp)) == NULL)
87: return (NULL);
88:
89: /*
90: * If the node is an '(' then we recursively slurp up expressions
91: * until we find its associated ')'. If it's a closing paren we
92: * just return it and unwind our recursion; all other nodes are
93: * complete expressions, so just return them.
94: */
95: if (node->type == N_OPENPAREN)
96: for (tail = subplan = NULL;;) {
97: if ((next = yankexpr(planp)) == NULL)
98: err(1, "(: missing closing ')'");
99: /*
100: * If we find a closing ')' we store the collected
101: * subplan in our '(' node and convert the node to
102: * a N_EXPR. The ')' we found is ignored. Otherwise,
103: * we just continue to add whatever we get to our
104: * subplan.
105: */
106: if (next->type == N_CLOSEPAREN) {
107: if (subplan == NULL)
108: errx(1, "(): empty inner expression");
109: node->p_data[0] = subplan;
110: node->type = N_EXPR;
111: node->eval = f_expr;
112: break;
113: } else {
114: if (subplan == NULL)
115: tail = subplan = next;
116: else {
117: tail->next = next;
118: tail = next;
119: }
120: tail->next = NULL;
121: }
122: }
123: return (node);
124: }
125:
126: /*
127: * paren_squish --
128: * replaces "parentheisized" plans in our search plan with "expr" nodes.
129: */
130: PLAN *
131: paren_squish(plan)
132: PLAN *plan; /* plan with ( ) nodes */
133: {
134: register PLAN *expr; /* pointer to next expression */
135: register PLAN *tail; /* pointer to tail of result plan */
136: PLAN *result; /* pointer to head of result plan */
137:
138: result = tail = NULL;
139:
140: /*
141: * the basic idea is to have yankexpr do all our work and just
142: * collect it's results together.
143: */
144: while ((expr = yankexpr(&plan)) != NULL) {
145: /*
146: * if we find an unclaimed ')' it means there is a missing
147: * '(' someplace.
148: */
149: if (expr->type == N_CLOSEPAREN)
150: errx(1, "): no beginning '('");
151:
152: /* add the expression to our result plan */
153: if (result == NULL)
154: tail = result = expr;
155: else {
156: tail->next = expr;
157: tail = expr;
158: }
159: tail->next = NULL;
160: }
161: return (result);
162: }
163:
164: /*
165: * not_squish --
166: * compresses "!" expressions in our search plan.
167: */
168: PLAN *
169: not_squish(plan)
170: PLAN *plan; /* plan to process */
171: {
172: register PLAN *next; /* next node being processed */
173: register PLAN *node; /* temporary node used in N_NOT processing */
174: register PLAN *tail; /* pointer to tail of result plan */
175: PLAN *result; /* pointer to head of result plan */
176:
177: tail = result = next = NULL;
178:
179: while ((next = yanknode(&plan)) != NULL) {
180: /*
181: * if we encounter a ( expression ) then look for nots in
182: * the expr subplan.
183: */
184: if (next->type == N_EXPR)
185: next->p_data[0] = not_squish(next->p_data[0]);
186:
187: /*
188: * if we encounter a not, then snag the next node and place
189: * it in the not's subplan. As an optimization we compress
190: * several not's to zero or one not.
191: */
192: if (next->type == N_NOT) {
193: int notlevel = 1;
194:
195: node = yanknode(&plan);
1.3 deraadt 196: while (node != NULL && node->type == N_NOT) {
1.1 deraadt 197: ++notlevel;
198: node = yanknode(&plan);
199: }
200: if (node == NULL)
201: errx(1, "!: no following expression");
202: if (node->type == N_OR)
203: errx(1, "!: nothing between ! and -o");
1.4 ! millert 204: if (node->type == N_EXPR)
! 205: node = not_squish(node);
1.1 deraadt 206: if (notlevel % 2 != 1)
207: next = node;
208: else
209: next->p_data[0] = node;
210: }
211:
212: /* add the node to our result plan */
213: if (result == NULL)
214: tail = result = next;
215: else {
216: tail->next = next;
217: tail = next;
218: }
219: tail->next = NULL;
220: }
221: return (result);
222: }
223:
224: /*
225: * or_squish --
226: * compresses -o expressions in our search plan.
227: */
228: PLAN *
229: or_squish(plan)
230: PLAN *plan; /* plan with ors to be squished */
231: {
232: register PLAN *next; /* next node being processed */
233: register PLAN *tail; /* pointer to tail of result plan */
234: PLAN *result; /* pointer to head of result plan */
235:
236: tail = result = next = NULL;
237:
238: while ((next = yanknode(&plan)) != NULL) {
239: /*
240: * if we encounter a ( expression ) then look for or's in
241: * the expr subplan.
242: */
243: if (next->type == N_EXPR)
244: next->p_data[0] = or_squish(next->p_data[0]);
245:
246: /* if we encounter a not then look for not's in the subplan */
247: if (next->type == N_NOT)
248: next->p_data[0] = or_squish(next->p_data[0]);
249:
250: /*
251: * if we encounter an or, then place our collected plan in the
252: * or's first subplan and then recursively collect the
253: * remaining stuff into the second subplan and return the or.
254: */
255: if (next->type == N_OR) {
256: if (result == NULL)
257: errx(1, "-o: no expression before -o");
258: next->p_data[0] = result;
259: next->p_data[1] = or_squish(plan);
260: if (next->p_data[1] == NULL)
261: errx(1, "-o: no expression after -o");
262: return (next);
263: }
264:
265: /* add the node to our result plan */
266: if (result == NULL)
267: tail = result = next;
268: else {
269: tail->next = next;
270: tail = next;
271: }
272: tail->next = NULL;
273: }
274: return (result);
275: }