xref: /freebsd/usr.bin/find/operator.c (revision 9336e0699bda8a301cd2bfa37106b6ec5e32012e)
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 #endif
41 #endif /* not lint */
42 
43 #include <sys/cdefs.h>
44 __FBSDID("$FreeBSD$");
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(PLAN **planp)
63 {
64 	PLAN *node;		/* top node removed from the plan */
65 
66 	if ((node = (*planp)) == NULL)
67 		return (NULL);
68 	(*planp) = (*planp)->next;
69 	node->next = NULL;
70 	return (node);
71 }
72 
73 /*
74  * yankexpr --
75  *	Removes one expression from the plan.  This is used mainly by
76  *	paren_squish.  In comments below, an expression is either a
77  *	simple node or a f_expr node containing a list of simple nodes.
78  */
79 static PLAN *
80 yankexpr(PLAN **planp)
81 {
82 	PLAN *next;		/* temp node holding subexpression results */
83 	PLAN *node;		/* pointer to returned node or expression */
84 	PLAN *tail;		/* pointer to tail of subplan */
85 	PLAN *subplan;		/* pointer to head of ( ) expression */
86 
87 	/* first pull the top node from the plan */
88 	if ((node = yanknode(planp)) == NULL)
89 		return (NULL);
90 
91 	/*
92 	 * If the node is an '(' then we recursively slurp up expressions
93 	 * until we find its associated ')'.  If it's a closing paren we
94 	 * just return it and unwind our recursion; all other nodes are
95 	 * complete expressions, so just return them.
96 	 */
97 	if (node->execute == f_openparen)
98 		for (tail = subplan = NULL;;) {
99 			if ((next = yankexpr(planp)) == NULL)
100 				errx(1, "(: missing closing ')'");
101 			/*
102 			 * If we find a closing ')' we store the collected
103 			 * subplan in our '(' node and convert the node to
104 			 * a f_expr.  The ')' we found is ignored.  Otherwise,
105 			 * we just continue to add whatever we get to our
106 			 * subplan.
107 			 */
108 			if (next->execute == f_closeparen) {
109 				if (subplan == NULL)
110 					errx(1, "(): empty inner expression");
111 				node->p_data[0] = subplan;
112 				node->execute = 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 "parenthesized" plans in our search plan with "expr" nodes.
130  */
131 PLAN *
132 paren_squish(PLAN *plan)
133 {
134 	PLAN *expr;		/* pointer to next expression */
135 	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 its 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->execute == f_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 *plan)
170 {
171 	PLAN *next;		/* next node being processed */
172 	PLAN *node;		/* temporary node used in f_not processing */
173 	PLAN *tail;		/* pointer to tail of result plan */
174 	PLAN *result;		/* pointer to head of result plan */
175 
176 	tail = result = NULL;
177 
178 	while ((next = yanknode(&plan))) {
179 		/*
180 		 * if we encounter a ( expression ) then look for nots in
181 		 * the expr subplan.
182 		 */
183 		if (next->execute == f_expr)
184 			next->p_data[0] = not_squish(next->p_data[0]);
185 
186 		/*
187 		 * if we encounter a not, then snag the next node and place
188 		 * it in the not's subplan.  As an optimization we compress
189 		 * several not's to zero or one not.
190 		 */
191 		if (next->execute == f_not) {
192 			int notlevel = 1;
193 
194 			node = yanknode(&plan);
195 			while (node != NULL && node->execute == f_not) {
196 				++notlevel;
197 				node = yanknode(&plan);
198 			}
199 			if (node == NULL)
200 				errx(1, "!: no following expression");
201 			if (node->execute == f_or)
202 				errx(1, "!: nothing between ! and -o");
203 			/*
204 			 * If we encounter ! ( expr ) then look for nots in
205 			 * the expr subplan.
206 			 */
207 			if (node->execute == f_expr)
208 				node->p_data[0] = not_squish(node->p_data[0]);
209 			if (notlevel % 2 != 1)
210 				next = node;
211 			else
212 				next->p_data[0] = node;
213 		}
214 
215 		/* add the node to our result plan */
216 		if (result == NULL)
217 			tail = result = next;
218 		else {
219 			tail->next = next;
220 			tail = next;
221 		}
222 		tail->next = NULL;
223 	}
224 	return (result);
225 }
226 
227 /*
228  * or_squish --
229  *	compresses -o expressions in our search plan.
230  */
231 PLAN *
232 or_squish(PLAN *plan)
233 {
234 	PLAN *next;		/* next node being processed */
235 	PLAN *tail;		/* pointer to tail of result plan */
236 	PLAN *result;		/* pointer to head of result plan */
237 
238 	tail = result = next = NULL;
239 
240 	while ((next = yanknode(&plan)) != NULL) {
241 		/*
242 		 * if we encounter a ( expression ) then look for or's in
243 		 * the expr subplan.
244 		 */
245 		if (next->execute == f_expr)
246 			next->p_data[0] = or_squish(next->p_data[0]);
247 
248 		/* if we encounter a not then look for or's in the subplan */
249 		if (next->execute == f_not)
250 			next->p_data[0] = or_squish(next->p_data[0]);
251 
252 		/*
253 		 * if we encounter an or, then place our collected plan in the
254 		 * or's first subplan and then recursively collect the
255 		 * remaining stuff into the second subplan and return the or.
256 		 */
257 		if (next->execute == f_or) {
258 			if (result == NULL)
259 				errx(1, "-o: no expression before -o");
260 			next->p_data[0] = result;
261 			next->p_data[1] = or_squish(plan);
262 			if (next->p_data[1] == NULL)
263 				errx(1, "-o: no expression after -o");
264 			return (next);
265 		}
266 
267 		/* add the node to our result plan */
268 		if (result == NULL)
269 			tail = result = next;
270 		else {
271 			tail->next = next;
272 			tail = next;
273 		}
274 		tail->next = NULL;
275 	}
276 	return (result);
277 }
278