Head

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 %


/*	$OpenBSD: operator.c,v 1.10 2009/10/27 23:59:38 deraadt Exp $	*/

/*-
 * Copyright (c) 1990, 1993
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Cimarron D. Taylor of the University of California, Berkeley.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/types.h>
#include <sys/stat.h>

#include <err.h>
#include <fts.h>
#include <stdio.h>

#include "find.h"
#include "extern.h"

/*
 * yanknode --
 *	destructively removes the top from the plan
 */
static PLAN *
yanknode(PLAN **planp)		/* pointer to top of plan (modified) */
{
	PLAN *node;		/* top node removed from the plan */

	if ((node = (*planp)) == NULL)
		return (NULL);
	(*planp) = (*planp)->next;
	node->next = NULL;
	return (node);
}

/*
 * yankexpr --
 *	Removes one expression from the plan.  This is used mainly by
 *	paren_squish.  In comments below, an expression is either a
 *	simple node or a N_EXPR node containing a list of simple nodes.
 */
static PLAN *
yankexpr(PLAN **planp)		/* pointer to top of plan (modified) */
{
	PLAN *next;	/* temp node holding subexpression results */
	PLAN *node;		/* pointer to returned node or expression */
	PLAN *tail;		/* pointer to tail of subplan */
	PLAN *subplan;		/* pointer to head of ( ) expression */
	extern int f_expr(PLAN *, FTSENT *);

	/* first pull the top node from the plan */
	if ((node = yanknode(planp)) == NULL)
		return (NULL);

	/*
	 * If the node is an '(' then we recursively slurp up expressions
	 * until we find its associated ')'.  If it's a closing paren we
	 * just return it and unwind our recursion; all other nodes are
	 * complete expressions, so just return them.
	 */
	if (node->type == N_OPENPAREN)
		for (tail = subplan = NULL;;) {
			if ((next = yankexpr(planp)) == NULL)
				errx(1, "(: missing closing ')'");
			/*
			 * If we find a closing ')' we store the collected
			 * subplan in our '(' node and convert the node to
			 * a N_EXPR.  The ')' we found is ignored.  Otherwise,
			 * we just continue to add whatever we get to our
			 * subplan.
			 */
			if (next->type == N_CLOSEPAREN) {
				if (subplan == NULL)
					errx(1, "(): empty inner expression");
				node->p_data[0] = subplan;
				node->type = N_EXPR;
				node->eval = f_expr;
				break;
			} else {
				if (subplan == NULL)
					tail = subplan = next;
				else {
					tail->next = next;
					tail = next;
				}
				tail->next = NULL;
			}
		}
	return (node);
}

/*
 * paren_squish --
 *	replaces "parentheisized" plans in our search plan with "expr" nodes.
 */
PLAN *
paren_squish(PLAN *plan)		/* plan with ( ) nodes */
{
	PLAN *expr;	/* pointer to next expression */
	PLAN *tail;	/* pointer to tail of result plan */
	PLAN *result;		/* pointer to head of result plan */

	result = tail = NULL;

	/*
	 * the basic idea is to have yankexpr do all our work and just
	 * collect it's results together.
	 */
	while ((expr = yankexpr(&plan)) != NULL) {
		/*
		 * if we find an unclaimed ')' it means there is a missing
		 * '(' someplace.
		 */
		if (expr->type == N_CLOSEPAREN)
			errx(1, "): no beginning '('");

		/* add the expression to our result plan */
		if (result == NULL)
			tail = result = expr;
		else {
			tail->next = expr;
			tail = expr;
		}
		tail->next = NULL;
	}
	return (result);
}

/*
 * not_squish --
 *	compresses "!" expressions in our search plan.
 */
PLAN *
not_squish(PLAN *plan)		/* plan to process */
{
	PLAN *next;	/* next node being processed */
	PLAN *node;	/* temporary node used in N_NOT processing */
	PLAN *tail;	/* pointer to tail of result plan */
	PLAN *result;		/* pointer to head of result plan */

	tail = result = next = NULL;

	while ((next = yanknode(&plan)) != NULL) {
		/*
		 * if we encounter a ( expression ) then look for nots in
		 * the expr subplan.
		 */
		if (next->type == N_EXPR)
			next->p_data[0] = not_squish(next->p_data[0]);

		/*
		 * if we encounter a not, then snag the next node and place
		 * it in the not's subplan.  As an optimization we compress
		 * several not's to zero or one not.
		 */
		if (next->type == N_NOT) {
			int notlevel = 1;

			node = yanknode(&plan);
			while (node != NULL && node->type == N_NOT) {
				++notlevel;
				node = yanknode(&plan);
			}
			if (node == NULL)
				errx(1, "!: no following expression");
			if (node->type == N_OR)
				errx(1, "!: nothing between ! and -o");
			if (node->type == N_EXPR)
				node = not_squish(node);
			if (notlevel % 2 != 1)
				next = node;
			else
				next->p_data[0] = node;
		}

		/* add the node to our result plan */
		if (result == NULL)
			tail = result = next;
		else {
			tail->next = next;
			tail = next;
		}
		tail->next = NULL;
	}
	return (result);
}

/*
 * or_squish --
 *	compresses -o expressions in our search plan.
 */
PLAN *
or_squish(PLAN *plan)		/* plan with ors to be squished */
{
	PLAN *next;	/* next node being processed */
	PLAN *tail;	/* pointer to tail of result plan */
	PLAN *result;		/* pointer to head of result plan */

	tail = result = next = NULL;

	while ((next = yanknode(&plan)) != NULL) {
		/*
		 * if we encounter a ( expression ) then look for or's in
		 * the expr subplan.
		 */
		if (next->type == N_EXPR)
			next->p_data[0] = or_squish(next->p_data[0]);

		/* if we encounter a not then look for not's in the subplan */
		if (next->type == N_NOT)
			next->p_data[0] = or_squish(next->p_data[0]);

		/*
		 * if we encounter an or, then place our collected plan in the
		 * or's first subplan and then recursively collect the
		 * remaining stuff into the second subplan and return the or.
		 */
		if (next->type == N_OR) {
			if (result == NULL)
				errx(1, "-o: no expression before -o");
			next->p_data[0] = result;
			next->p_data[1] = or_squish(plan);
			if (next->p_data[1] == NULL)
				errx(1, "-o: no expression after -o");
			return (next);
		}

		/* add the node to our result plan */
		if (result == NULL)
			tail = result = next;
		else {
			tail->next = next;
			tail = next;
		}
		tail->next = NULL;
	}
	return (result);
}


Generated by: GCOVR (Version 3.3)

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	}