GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/find/operator.c Lines: 65 75 86.7 %
Date: 2017-11-07 Branches: 44 54 81.5 %

Line Branch Exec Source
1
/*	$OpenBSD: operator.c,v 1.10 2009/10/27 23:59:38 deraadt Exp $	*/
2
3
/*-
4
 * Copyright (c) 1990, 1993
5
 *	The Regents of the University of California.  All rights reserved.
6
 *
7
 * This code is derived from software contributed to Berkeley by
8
 * Cimarron D. Taylor of the University of California, Berkeley.
9
 *
10
 * Redistribution and use in source and binary forms, with or without
11
 * modification, are permitted provided that the following conditions
12
 * are met:
13
 * 1. Redistributions of source code must retain the above copyright
14
 *    notice, this list of conditions and the following disclaimer.
15
 * 2. Redistributions in binary form must reproduce the above copyright
16
 *    notice, this list of conditions and the following disclaimer in the
17
 *    documentation and/or other materials provided with the distribution.
18
 * 3. Neither the name of the University nor the names of its contributors
19
 *    may be used to endorse or promote products derived from this software
20
 *    without specific prior written permission.
21
 *
22
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32
 * SUCH DAMAGE.
33
 */
34
35
#include <sys/types.h>
36
#include <sys/stat.h>
37
38
#include <err.h>
39
#include <fts.h>
40
#include <stdio.h>
41
42
#include "find.h"
43
#include "extern.h"
44
45
/*
46
 * yanknode --
47
 *	destructively removes the top from the plan
48
 */
49
static PLAN *
50
yanknode(PLAN **planp)		/* pointer to top of plan (modified) */
51
{
52
	PLAN *node;		/* top node removed from the plan */
53
54
2870
	if ((node = (*planp)) == NULL)
55
441
		return (NULL);
56
994
	(*planp) = (*planp)->next;
57
994
	node->next = NULL;
58
994
	return (node);
59
1435
}
60
61
/*
62
 * yankexpr --
63
 *	Removes one expression from the plan.  This is used mainly by
64
 *	paren_squish.  In comments below, an expression is either a
65
 *	simple node or a N_EXPR node containing a list of simple nodes.
66
 */
67
static PLAN *
68
yankexpr(PLAN **planp)		/* pointer to top of plan (modified) */
69
{
70
	PLAN *next;	/* temp node holding subexpression results */
71
	PLAN *node;		/* pointer to returned node or expression */
72
	PLAN *tail;		/* pointer to tail of subplan */
73
	PLAN *subplan;		/* pointer to head of ( ) expression */
74
	extern int f_expr(PLAN *, FTSENT *);
75
76
	/* first pull the top node from the plan */
77
950
	if ((node = yanknode(planp)) == NULL)
78
113
		return (NULL);
79
80
	/*
81
	 * If the node is an '(' then we recursively slurp up expressions
82
	 * until we find its associated ')'.  If it's a closing paren we
83
	 * just return it and unwind our recursion; all other nodes are
84
	 * complete expressions, so just return them.
85
	 */
86
362
	if (node->type == N_OPENPAREN)
87
115
		for (tail = subplan = NULL;;) {
88
115
			if ((next = yankexpr(planp)) == NULL)
89
				errx(1, "(: missing closing ')'");
90
			/*
91
			 * If we find a closing ')' we store the collected
92
			 * subplan in our '(' node and convert the node to
93
			 * a N_EXPR.  The ')' we found is ignored.  Otherwise,
94
			 * we just continue to add whatever we get to our
95
			 * subplan.
96
			 */
97
115
			if (next->type == N_CLOSEPAREN) {
98
47
				if (subplan == NULL)
99
					errx(1, "(): empty inner expression");
100
47
				node->p_data[0] = subplan;
101
47
				node->type = N_EXPR;
102
47
				node->eval = f_expr;
103
				break;
104
			} else {
105
68
				if (subplan == NULL)
106
47
					tail = subplan = next;
107
				else {
108
21
					tail->next = next;
109
					tail = next;
110
				}
111
68
				tail->next = NULL;
112
			}
113
47
		}
114
362
	return (node);
115
475
}
116
117
/*
118
 * paren_squish --
119
 *	replaces "parentheisized" plans in our search plan with "expr" nodes.
120
 */
121
PLAN *
122
paren_squish(PLAN *plan)		/* plan with ( ) nodes */
123
{
124
	PLAN *expr;	/* pointer to next expression */
125
	PLAN *tail;	/* pointer to tail of result plan */
126
	PLAN *result;		/* pointer to head of result plan */
127
128
	result = tail = NULL;
129
130
	/*
131
	 * the basic idea is to have yankexpr do all our work and just
132
	 * collect it's results together.
133
	 */
134
720
	while ((expr = yankexpr(&plan)) != NULL) {
135
		/*
136
		 * if we find an unclaimed ')' it means there is a missing
137
		 * '(' someplace.
138
		 */
139
247
		if (expr->type == N_CLOSEPAREN)
140
			errx(1, "): no beginning '('");
141
142
		/* add the expression to our result plan */
143
247
		if (result == NULL)
144
113
			tail = result = expr;
145
		else {
146
134
			tail->next = expr;
147
			tail = expr;
148
		}
149
247
		tail->next = NULL;
150
	}
151
113
	return (result);
152
}
153
154
/*
155
 * not_squish --
156
 *	compresses "!" expressions in our search plan.
157
 */
158
PLAN *
159
not_squish(PLAN *plan)		/* plan to process */
160
{
161
	PLAN *next;	/* next node being processed */
162
	PLAN *node;	/* temporary node used in N_NOT processing */
163
	PLAN *tail;	/* pointer to tail of result plan */
164
	PLAN *result;		/* pointer to head of result plan */
165
166
	tail = result = next = NULL;
167
168
946
	while ((next = yanknode(&plan)) != NULL) {
169
		/*
170
		 * if we encounter a ( expression ) then look for nots in
171
		 * the expr subplan.
172
		 */
173
311
		if (next->type == N_EXPR)
174
47
			next->p_data[0] = not_squish(next->p_data[0]);
175
176
		/*
177
		 * if we encounter a not, then snag the next node and place
178
		 * it in the not's subplan.  As an optimization we compress
179
		 * several not's to zero or one not.
180
		 */
181
311
		if (next->type == N_NOT) {
182
			int notlevel = 1;
183
184
6
			node = yanknode(&plan);
185

18
			while (node != NULL && node->type == N_NOT) {
186
				++notlevel;
187
				node = yanknode(&plan);
188
			}
189
6
			if (node == NULL)
190
				errx(1, "!: no following expression");
191
6
			if (node->type == N_OR)
192
				errx(1, "!: nothing between ! and -o");
193
6
			if (node->type == N_EXPR)
194
2
				node = not_squish(node);
195
6
			if (notlevel % 2 != 1)
196
				next = node;
197
			else
198
6
				next->p_data[0] = node;
199
6
		}
200
201
		/* add the node to our result plan */
202
311
		if (result == NULL)
203
162
			tail = result = next;
204
		else {
205
149
			tail->next = next;
206
			tail = next;
207
		}
208
311
		tail->next = NULL;
209
	}
210
162
	return (result);
211
}
212
213
/*
214
 * or_squish --
215
 *	compresses -o expressions in our search plan.
216
 */
217
PLAN *
218
or_squish(PLAN *plan)		/* plan with ors to be squished */
219
{
220
	PLAN *next;	/* next node being processed */
221
	PLAN *tail;	/* pointer to tail of result plan */
222
	PLAN *result;		/* pointer to head of result plan */
223
224
	tail = result = next = NULL;
225
226
962
	while ((next = yanknode(&plan)) != NULL) {
227
		/*
228
		 * if we encounter a ( expression ) then look for or's in
229
		 * the expr subplan.
230
		 */
231
315
		if (next->type == N_EXPR)
232
47
			next->p_data[0] = or_squish(next->p_data[0]);
233
234
		/* if we encounter a not then look for not's in the subplan */
235
315
		if (next->type == N_NOT)
236
6
			next->p_data[0] = or_squish(next->p_data[0]);
237
238
		/*
239
		 * if we encounter an or, then place our collected plan in the
240
		 * or's first subplan and then recursively collect the
241
		 * remaining stuff into the second subplan and return the or.
242
		 */
243
315
		if (next->type == N_OR) {
244
8
			if (result == NULL)
245
				errx(1, "-o: no expression before -o");
246
8
			next->p_data[0] = result;
247
8
			next->p_data[1] = or_squish(plan);
248
8
			if (next->p_data[1] == NULL)
249
				errx(1, "-o: no expression after -o");
250
8
			return (next);
251
		}
252
253
		/* add the node to our result plan */
254
307
		if (result == NULL)
255
174
			tail = result = next;
256
		else {
257
133
			tail->next = next;
258
			tail = next;
259
		}
260
307
		tail->next = NULL;
261
	}
262
166
	return (result);
263
174
}