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