2 * Copyright (c) 2006, Maxime Henrion <mux@FreeBSD.org>
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 #include <sys/types.h>
40 * The "GlobTree" interface allows one to construct arbitrarily complex
41 * boolean expressions for evaluating whether to accept or reject a
42 * filename. The globtree_test() function returns true or false
43 * according to whether the name is accepted or rejected by the
46 * Expressions are trees constructed from nodes representing either
47 * primitive matching operations (primaries) or operators that are
48 * applied to their subexpressions. The simplest primitives are
49 * globtree_false(), which matches nothing, and globtree_true(), which
52 * A more useful primitive is the matching operation, constructed with
53 * globtree_match(). It will call fnmatch() with the suppliedi
54 * shell-style pattern to determine if the filename matches.
56 * Expressions can be combined with the boolean operators AND, OR, and
57 * NOT, to form more complex expressions.
61 #define GLOBTREE_NOT 0
62 #define GLOBTREE_AND 1
64 #define GLOBTREE_MATCH 3
65 #define GLOBTREE_REGEX 4
66 #define GLOBTREE_TRUE 5
67 #define GLOBTREE_FALSE 6
72 struct globtree *left;
73 struct globtree *right;
75 /* The "data" field points to the text pattern for GLOBTREE_MATCH
76 nodes, and to the regex_t for GLOBTREE_REGEX nodes. For any
77 other node, it is set to NULL. */
79 /* The "flags" field contains the flags to pass to fnmatch() for
80 GLOBTREE_MATCH nodes. */
84 static struct globtree *globtree_new(int);
85 static int globtree_eval(struct globtree *, const char *);
87 static struct globtree *
88 globtree_new(int type)
92 gt = xmalloc(sizeof(struct globtree));
106 gt = globtree_new(GLOBTREE_TRUE);
115 gt = globtree_new(GLOBTREE_FALSE);
120 globtree_match(const char *pattern, int flags)
124 gt = globtree_new(GLOBTREE_MATCH);
125 gt->data = xstrdup(pattern);
131 globtree_regex(const char *pattern)
136 gt = globtree_new(GLOBTREE_REGEX);
137 gt->data = xmalloc(sizeof(regex_t));
138 error = regcomp(gt->data, pattern, REG_NOSUB);
144 globtree_and(struct globtree *left, struct globtree *right)
148 if (left->type == GLOBTREE_FALSE || right->type == GLOBTREE_FALSE) {
150 globtree_free(right);
151 gt = globtree_false();
154 if (left->type == GLOBTREE_TRUE) {
158 if (right->type == GLOBTREE_TRUE) {
159 globtree_free(right);
162 gt = globtree_new(GLOBTREE_AND);
169 globtree_or(struct globtree *left, struct globtree *right)
173 if (left->type == GLOBTREE_TRUE || right->type == GLOBTREE_TRUE) {
175 globtree_free(right);
176 gt = globtree_true();
179 if (left->type == GLOBTREE_FALSE) {
183 if (right->type == GLOBTREE_FALSE) {
184 globtree_free(right);
187 gt = globtree_new(GLOBTREE_OR);
194 globtree_not(struct globtree *child)
198 if (child->type == GLOBTREE_TRUE) {
199 globtree_free(child);
200 gt = globtree_new(GLOBTREE_FALSE);
203 if (child->type == GLOBTREE_FALSE) {
204 globtree_free(child);
205 gt = globtree_new(GLOBTREE_TRUE);
208 gt = globtree_new(GLOBTREE_NOT);
213 /* Evaluate one node (must be a leaf node). */
215 globtree_eval(struct globtree *gt, const char *path)
225 assert(gt->data != NULL);
226 rv = fnmatch(gt->data, path, gt->flags);
229 assert(rv == FNM_NOMATCH);
232 assert(gt->data != NULL);
233 rv = regexec(gt->data, path, 0, NULL, 0);
236 assert(rv == REG_NOMATCH);
244 /* Small stack API to walk the tree iteratively. */
251 struct stackelem *stack;
257 struct globtree *node;
262 stack_init(struct stack *stack)
266 stack->size = 8; /* Initial size. */
267 stack->stack = xmalloc(sizeof(struct stackelem) * stack->size);
271 stack_size(struct stack *stack)
278 stack_push(struct stack *stack, struct globtree *node, walkstate_t state)
282 if (stack->in == stack->size) {
284 stack->stack = xrealloc(stack->stack,
285 sizeof(struct stackelem) * stack->size);
287 e = stack->stack + stack->in++;
293 stack_pop(struct stack *stack, struct globtree **node, walkstate_t *state)
297 assert(stack->in > 0);
298 e = stack->stack + --stack->in;
304 stack_free(struct stack *s)
310 /* Tests if the supplied filename matches. */
312 globtree_test(struct globtree *gt, const char *path)
321 /* Descend to the left until we hit bottom. */
322 while (gt->left != NULL) {
323 stack_push(&stack, gt, STATE_DOINGLEFT);
327 /* Now we're at a leaf node. Evaluate it. */
328 val = globtree_eval(gt, path);
329 /* Ascend, propagating the value through operator nodes. */
331 if (stack_size(&stack) == 0) {
335 stack_pop(&stack, >, &state);
341 /* If we haven't yet evaluated the right subtree
342 and the partial result is true, descend to
343 the right. Otherwise the result is already
344 determined to be val. */
345 if (state == STATE_DOINGLEFT && val) {
346 stack_push(&stack, gt,
353 /* If we haven't yet evaluated the right subtree
354 and the partial result is false, descend to
355 the right. Otherwise the result is already
356 determined to be val. */
357 if (state == STATE_DOINGLEFT && !val) {
358 stack_push(&stack, gt,
365 /* We only push nodes that have children. */
374 * We could de-recursify this function using a stack, but it would be
375 * overkill since it is never called from a thread context with a
376 * limited stack size nor used in a critical path, so I think we can
377 * afford keeping it recursive.
380 globtree_free(struct globtree *gt)
383 if (gt->data != NULL) {
384 if (gt->type == GLOBTREE_REGEX)
388 if (gt->left != NULL)
389 globtree_free(gt->left);
390 if (gt->right != NULL)
391 globtree_free(gt->right);