Commit | Line | Data |
---|---|---|
15637ed4 | 1 | /*- |
6b479535 NW |
2 | * Copyright (c) 1990, 1993 |
3 | * The Regents of the University of California. All rights reserved. | |
15637ed4 RG |
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 | |
6b479535 | 38 | static char sccsid[] = "@(#)operator.c 8.1 (Berkeley) 6/6/93"; |
15637ed4 RG |
39 | #endif /* not lint */ |
40 | ||
41 | #include <sys/types.h> | |
6b479535 NW |
42 | |
43 | #include <err.h> | |
44 | #include <fts.h> | |
15637ed4 | 45 | #include <stdio.h> |
6b479535 | 46 | |
15637ed4 RG |
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) | |
6b479535 | 60 | return (NULL); |
15637ed4 RG |
61 | (*planp) = (*planp)->next; |
62 | node->next = NULL; | |
6b479535 | 63 | return (node); |
15637ed4 RG |
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) | |
6b479535 | 84 | return (NULL); |
15637ed4 RG |
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) | |
6b479535 | 95 | err(1, "(: missing closing ')'"); |
15637ed4 RG |
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) | |
6b479535 | 105 | errx(1, "(): empty inner expression"); |
15637ed4 RG |
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 | } | |
6b479535 | 120 | return (node); |
15637ed4 RG |
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) | |
6b479535 | 147 | errx(1, "): no beginning '('"); |
15637ed4 RG |
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 | } | |
6b479535 | 158 | return (result); |
15637ed4 RG |
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) | |
6b479535 | 198 | errx(1, "!: no following expression"); |
15637ed4 | 199 | if (node->type == N_OR) |
6b479535 | 200 | errx(1, "!: nothing between ! and -o"); |
15637ed4 RG |
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 | } | |
6b479535 | 216 | return (result); |
15637ed4 RG |
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) | |
6b479535 | 252 | errx(1, "-o: no expression before -o"); |
15637ed4 RG |
253 | next->p_data[0] = result; |
254 | next->p_data[1] = or_squish(plan); | |
255 | if (next->p_data[1] == NULL) | |
6b479535 NW |
256 | errx(1, "-o: no expression after -o"); |
257 | return (next); | |
15637ed4 RG |
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 | } | |
6b479535 | 269 | return (result); |
15637ed4 | 270 | } |