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