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