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