xref: /freebsd/usr.bin/find/operator.c (revision 2e620256bd76c449c835c604e404483437743011)
1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
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. Neither the name of the University nor the names of its contributors
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 #if 0
36 static char sccsid[] = "@(#)operator.c	8.1 (Berkeley) 6/6/93";
37 #endif
38 
39 #include <sys/cdefs.h>
40 #include <sys/types.h>
41 
42 #include <err.h>
43 #include <fts.h>
44 #include <stdio.h>
45 #include <time.h>
46 
47 #include "find.h"
48 
49 static PLAN *yanknode(PLAN **);
50 static PLAN *yankexpr(PLAN **);
51 
52 /*
53  * yanknode --
54  *	destructively removes the top from the plan
55  */
56 static PLAN *
57 yanknode(PLAN **planp)
58 {
59 	PLAN *node;		/* top node removed from the plan */
60 
61 	if ((node = (*planp)) == NULL)
62 		return (NULL);
63 	(*planp) = (*planp)->next;
64 	node->next = NULL;
65 	return (node);
66 }
67 
68 /*
69  * yankexpr --
70  *	Removes one expression from the plan.  This is used mainly by
71  *	paren_squish.  In comments below, an expression is either a
72  *	simple node or a f_expr node containing a list of simple nodes.
73  */
74 static PLAN *
75 yankexpr(PLAN **planp)
76 {
77 	PLAN *next;		/* temp node holding subexpression results */
78 	PLAN *node;		/* pointer to returned node or expression */
79 	PLAN *tail;		/* pointer to tail of subplan */
80 	PLAN *subplan;		/* pointer to head of ( ) expression */
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->execute == f_openparen)
93 		for (tail = subplan = NULL;;) {
94 			if ((next = yankexpr(planp)) == NULL)
95 				errx(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 f_expr.  The ')' we found is ignored.  Otherwise,
100 			 * we just continue to add whatever we get to our
101 			 * subplan.
102 			 */
103 			if (next->execute == f_closeparen) {
104 				if (subplan == NULL)
105 					errx(1, "(): empty inner expression");
106 				node->p_data[0] = subplan;
107 				node->execute = 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 "parenthesized" plans in our search plan with "expr" nodes.
125  */
126 PLAN *
127 paren_squish(PLAN *plan)
128 {
129 	PLAN *expr;		/* pointer to next expression */
130 	PLAN *tail;		/* pointer to tail of result plan */
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 its 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->execute == f_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 *
164 not_squish(PLAN *plan)
165 {
166 	PLAN *next;		/* next node being processed */
167 	PLAN *node;		/* temporary node used in f_not processing */
168 	PLAN *tail;		/* pointer to tail of result plan */
169 	PLAN *result;		/* pointer to head of result plan */
170 
171 	tail = result = NULL;
172 
173 	while ((next = yanknode(&plan))) {
174 		/*
175 		 * if we encounter a ( expression ) then look for nots in
176 		 * the expr subplan.
177 		 */
178 		if (next->execute == f_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->execute == f_not) {
187 			int notlevel = 1;
188 
189 			node = yanknode(&plan);
190 			while (node != NULL && node->execute == f_not) {
191 				++notlevel;
192 				node = yanknode(&plan);
193 			}
194 			if (node == NULL)
195 				errx(1, "!: no following expression");
196 			if (node->execute == f_or)
197 				errx(1, "!: nothing between ! and -o");
198 			/*
199 			 * If we encounter ! ( expr ) then look for nots in
200 			 * the expr subplan.
201 			 */
202 			if (node->execute == f_expr)
203 				node->p_data[0] = not_squish(node->p_data[0]);
204 			if (notlevel % 2 != 1)
205 				next = node;
206 			else
207 				next->p_data[0] = node;
208 		}
209 
210 		/* add the node to our result plan */
211 		if (result == NULL)
212 			tail = result = next;
213 		else {
214 			tail->next = next;
215 			tail = next;
216 		}
217 		tail->next = NULL;
218 	}
219 	return (result);
220 }
221 
222 /*
223  * or_squish --
224  *	compresses -o expressions in our search plan.
225  */
226 PLAN *
227 or_squish(PLAN *plan)
228 {
229 	PLAN *next;		/* next node being processed */
230 	PLAN *tail;		/* pointer to tail of result plan */
231 	PLAN *result;		/* pointer to head of result plan */
232 
233 	tail = result = next = NULL;
234 
235 	while ((next = yanknode(&plan)) != NULL) {
236 		/*
237 		 * if we encounter a ( expression ) then look for or's in
238 		 * the expr subplan.
239 		 */
240 		if (next->execute == f_expr)
241 			next->p_data[0] = or_squish(next->p_data[0]);
242 
243 		/* if we encounter a not then look for or's in the subplan */
244 		if (next->execute == f_not)
245 			next->p_data[0] = or_squish(next->p_data[0]);
246 
247 		/*
248 		 * if we encounter an or, then place our collected plan in the
249 		 * or's first subplan and then recursively collect the
250 		 * remaining stuff into the second subplan and return the or.
251 		 */
252 		if (next->execute == f_or) {
253 			if (result == NULL)
254 				errx(1, "-o: no expression before -o");
255 			next->p_data[0] = result;
256 			next->p_data[1] = or_squish(plan);
257 			if (next->p_data[1] == NULL)
258 				errx(1, "-o: no expression after -o");
259 			return (next);
260 		}
261 
262 		/* add the node to our result plan */
263 		if (result == NULL)
264 			tail = result = next;
265 		else {
266 			tail->next = next;
267 			tail = next;
268 		}
269 		tail->next = NULL;
270 	}
271 	return (result);
272 }
273