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