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