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