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 | |
a76ed48d | 12 | static char sccsid[] = "@(#)operator.c 5.5 (Berkeley) %G%"; |
45fc66f9 KB |
13 | #endif /* not lint */ |
14 | ||
15 | #include <sys/types.h> | |
a76ed48d KB |
16 | |
17 | #include <err.h> | |
18 | #include <fts.h> | |
45fc66f9 | 19 | #include <stdio.h> |
a76ed48d | 20 | |
45fc66f9 KB |
21 | #include "find.h" |
22 | ||
23 | /* | |
e0482c58 | 24 | * yanknode -- |
45fc66f9 KB |
25 | * destructively removes the top from the plan |
26 | */ | |
ff92ccf9 | 27 | static PLAN * |
e0482c58 | 28 | yanknode(planp) |
45fc66f9 KB |
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) | |
a76ed48d | 34 | return (NULL); |
45fc66f9 KB |
35 | (*planp) = (*planp)->next; |
36 | node->next = NULL; | |
a76ed48d | 37 | return (node); |
45fc66f9 KB |
38 | } |
39 | ||
40 | /* | |
e0482c58 | 41 | * yankexpr -- |
45fc66f9 | 42 | * Removes one expression from the plan. This is used mainly by |
e0482c58 | 43 | * paren_squish. In comments below, an expression is either a |
a872c6c4 | 44 | * simple node or a N_EXPR node containing a list of simple nodes. |
45fc66f9 | 45 | */ |
ff92ccf9 | 46 | static PLAN * |
e0482c58 | 47 | yankexpr(planp) |
45fc66f9 KB |
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 */ | |
e0482c58 | 57 | if ((node = yanknode(planp)) == NULL) |
a76ed48d | 58 | return (NULL); |
45fc66f9 KB |
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 | */ | |
a872c6c4 | 66 | if (node->type == N_OPENPAREN) |
45fc66f9 | 67 | for (tail = subplan = NULL;;) { |
e0482c58 | 68 | if ((next = yankexpr(planp)) == NULL) |
a76ed48d | 69 | err(1, "(: missing closing ')'"); |
45fc66f9 KB |
70 | /* |
71 | * If we find a closing ')' we store the collected | |
72 | * subplan in our '(' node and convert the node to | |
a872c6c4 | 73 | * a N_EXPR. The ')' we found is ignored. Otherwise, |
45fc66f9 KB |
74 | * we just continue to add whatever we get to our |
75 | * subplan. | |
76 | */ | |
a872c6c4 | 77 | if (next->type == N_CLOSEPAREN) { |
45fc66f9 | 78 | if (subplan == NULL) |
a76ed48d | 79 | errx(1, "(): empty inner expression"); |
45fc66f9 | 80 | node->p_data[0] = subplan; |
a872c6c4 | 81 | node->type = N_EXPR; |
45fc66f9 KB |
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 | } | |
a76ed48d | 94 | return (node); |
45fc66f9 KB |
95 | } |
96 | ||
97 | /* | |
e0482c58 | 98 | * paren_squish -- |
45fc66f9 KB |
99 | * replaces "parentheisized" plans in our search plan with "expr" nodes. |
100 | */ | |
101 | PLAN * | |
e0482c58 | 102 | paren_squish(plan) |
45fc66f9 KB |
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 | /* | |
e0482c58 | 112 | * the basic idea is to have yankexpr do all our work and just |
45fc66f9 KB |
113 | * collect it's results together. |
114 | */ | |
e0482c58 | 115 | while ((expr = yankexpr(&plan)) != NULL) { |
45fc66f9 KB |
116 | /* |
117 | * if we find an unclaimed ')' it means there is a missing | |
118 | * '(' someplace. | |
119 | */ | |
a872c6c4 | 120 | if (expr->type == N_CLOSEPAREN) |
a76ed48d | 121 | errx(1, "): no beginning '('"); |
45fc66f9 KB |
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 | } | |
a76ed48d | 132 | return (result); |
45fc66f9 KB |
133 | } |
134 | ||
135 | /* | |
e0482c58 | 136 | * not_squish -- |
45fc66f9 KB |
137 | * compresses "!" expressions in our search plan. |
138 | */ | |
139 | PLAN * | |
e0482c58 | 140 | not_squish(plan) |
45fc66f9 KB |
141 | PLAN *plan; /* plan to process */ |
142 | { | |
143 | register PLAN *next; /* next node being processed */ | |
a872c6c4 | 144 | register PLAN *node; /* temporary node used in N_NOT processing */ |
45fc66f9 KB |
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 | ||
e0482c58 | 150 | while ((next = yanknode(&plan)) != NULL) { |
45fc66f9 KB |
151 | /* |
152 | * if we encounter a ( expression ) then look for nots in | |
153 | * the expr subplan. | |
154 | */ | |
a872c6c4 | 155 | if (next->type == N_EXPR) |
e0482c58 | 156 | next->p_data[0] = not_squish(next->p_data[0]); |
45fc66f9 KB |
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 | */ | |
a872c6c4 | 163 | if (next->type == N_NOT) { |
45fc66f9 KB |
164 | int notlevel = 1; |
165 | ||
e0482c58 | 166 | node = yanknode(&plan); |
a872c6c4 | 167 | while (node->type == N_NOT) { |
45fc66f9 | 168 | ++notlevel; |
e0482c58 | 169 | node = yanknode(&plan); |
45fc66f9 KB |
170 | } |
171 | if (node == NULL) | |
a76ed48d | 172 | errx(1, "!: no following expression"); |
a872c6c4 | 173 | if (node->type == N_OR) |
a76ed48d | 174 | errx(1, "!: nothing between ! and -o"); |
45fc66f9 KB |
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 | } | |
a76ed48d | 190 | return (result); |
45fc66f9 KB |
191 | } |
192 | ||
193 | /* | |
e0482c58 | 194 | * or_squish -- |
45fc66f9 KB |
195 | * compresses -o expressions in our search plan. |
196 | */ | |
197 | PLAN * | |
e0482c58 | 198 | or_squish(plan) |
45fc66f9 KB |
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 | ||
e0482c58 | 207 | while ((next = yanknode(&plan)) != NULL) { |
45fc66f9 KB |
208 | /* |
209 | * if we encounter a ( expression ) then look for or's in | |
210 | * the expr subplan. | |
211 | */ | |
a872c6c4 | 212 | if (next->type == N_EXPR) |
e0482c58 | 213 | next->p_data[0] = or_squish(next->p_data[0]); |
45fc66f9 KB |
214 | |
215 | /* if we encounter a not then look for not's in the subplan */ | |
a872c6c4 | 216 | if (next->type == N_NOT) |
e0482c58 | 217 | next->p_data[0] = or_squish(next->p_data[0]); |
45fc66f9 KB |
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 | */ | |
a872c6c4 | 224 | if (next->type == N_OR) { |
45fc66f9 | 225 | if (result == NULL) |
a76ed48d | 226 | errx(1, "-o: no expression before -o"); |
45fc66f9 | 227 | next->p_data[0] = result; |
e0482c58 | 228 | next->p_data[1] = or_squish(plan); |
45fc66f9 | 229 | if (next->p_data[1] == NULL) |
a76ed48d KB |
230 | errx(1, "-o: no expression after -o"); |
231 | return (next); | |
45fc66f9 KB |
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 | } | |
a76ed48d | 243 | return (result); |
45fc66f9 | 244 | } |