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