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