1156230Smux/*- 2156230Smux * Copyright (c) 2006, Maxime Henrion <mux@FreeBSD.org> 3156230Smux * All rights reserved. 4156230Smux * 5156230Smux * Redistribution and use in source and binary forms, with or without 6156230Smux * modification, are permitted provided that the following conditions 7156230Smux * are met: 8156230Smux * 1. Redistributions of source code must retain the above copyright 9156230Smux * notice, this list of conditions and the following disclaimer. 10156230Smux * 2. Redistributions in binary form must reproduce the above copyright 11156230Smux * notice, this list of conditions and the following disclaimer in the 12156230Smux * documentation and/or other materials provided with the distribution. 13156230Smux * 14156230Smux * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15156230Smux * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16156230Smux * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17156230Smux * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18156230Smux * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19156230Smux * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20156230Smux * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21156230Smux * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22156230Smux * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23156230Smux * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24156230Smux * SUCH DAMAGE. 25156230Smux * 26156230Smux * $FreeBSD$ 27156230Smux */ 28156230Smux 29156230Smux#include <sys/types.h> 30156230Smux 31156230Smux#include <assert.h> 32156230Smux#include <regex.h> 33156230Smux#include <stdlib.h> 34156230Smux 35156701Smux#include "fnmatch.h" 36156230Smux#include "globtree.h" 37156230Smux#include "misc.h" 38156230Smux 39156230Smux/* 40156230Smux * The "GlobTree" interface allows one to construct arbitrarily complex 41156230Smux * boolean expressions for evaluating whether to accept or reject a 42156230Smux * filename. The globtree_test() function returns true or false 43156230Smux * according to whether the name is accepted or rejected by the 44156230Smux * expression. 45156230Smux * 46156230Smux * Expressions are trees constructed from nodes representing either 47156230Smux * primitive matching operations (primaries) or operators that are 48156230Smux * applied to their subexpressions. The simplest primitives are 49156230Smux * globtree_false(), which matches nothing, and globtree_true(), which 50156230Smux * matches everything. 51156230Smux * 52156230Smux * A more useful primitive is the matching operation, constructed with 53156230Smux * globtree_match(). It will call fnmatch() with the suppliedi 54156230Smux * shell-style pattern to determine if the filename matches. 55156230Smux * 56156230Smux * Expressions can be combined with the boolean operators AND, OR, and 57156230Smux * NOT, to form more complex expressions. 58156230Smux */ 59156230Smux 60156230Smux/* Node types. */ 61156230Smux#define GLOBTREE_NOT 0 62156230Smux#define GLOBTREE_AND 1 63156230Smux#define GLOBTREE_OR 2 64156230Smux#define GLOBTREE_MATCH 3 65156230Smux#define GLOBTREE_REGEX 4 66156230Smux#define GLOBTREE_TRUE 5 67156230Smux#define GLOBTREE_FALSE 6 68156230Smux 69156230Smux/* A node. */ 70156230Smuxstruct globtree { 71156230Smux int type; 72156230Smux struct globtree *left; 73156230Smux struct globtree *right; 74156230Smux 75156230Smux /* The "data" field points to the text pattern for GLOBTREE_MATCH 76156230Smux nodes, and to the regex_t for GLOBTREE_REGEX nodes. For any 77156230Smux other node, it is set to NULL. */ 78156230Smux void *data; 79156230Smux /* The "flags" field contains the flags to pass to fnmatch() for 80156230Smux GLOBTREE_MATCH nodes. */ 81156230Smux int flags; 82156230Smux}; 83156230Smux 84156230Smuxstatic struct globtree *globtree_new(int); 85156230Smuxstatic int globtree_eval(struct globtree *, const char *); 86156230Smux 87156230Smuxstatic struct globtree * 88156230Smuxglobtree_new(int type) 89156230Smux{ 90156230Smux struct globtree *gt; 91156230Smux 92156230Smux gt = xmalloc(sizeof(struct globtree)); 93156230Smux gt->type = type; 94156230Smux gt->data = NULL; 95156230Smux gt->flags = 0; 96156230Smux gt->left = NULL; 97156230Smux gt->right = NULL; 98156230Smux return (gt); 99156230Smux} 100156230Smux 101156230Smuxstruct globtree * 102156230Smuxglobtree_true(void) 103156230Smux{ 104156230Smux struct globtree *gt; 105156230Smux 106156230Smux gt = globtree_new(GLOBTREE_TRUE); 107156230Smux return (gt); 108156230Smux} 109156230Smux 110156230Smuxstruct globtree * 111156230Smuxglobtree_false(void) 112156230Smux{ 113156230Smux struct globtree *gt; 114156230Smux 115156230Smux gt = globtree_new(GLOBTREE_FALSE); 116156230Smux return (gt); 117156230Smux} 118156230Smux 119156230Smuxstruct globtree * 120156230Smuxglobtree_match(const char *pattern, int flags) 121156230Smux{ 122156230Smux struct globtree *gt; 123156230Smux 124156230Smux gt = globtree_new(GLOBTREE_MATCH); 125156230Smux gt->data = xstrdup(pattern); 126156230Smux gt->flags = flags; 127156230Smux return (gt); 128156230Smux} 129156230Smux 130156230Smuxstruct globtree * 131156230Smuxglobtree_regex(const char *pattern) 132156230Smux{ 133156230Smux struct globtree *gt; 134156230Smux int error; 135156230Smux 136156230Smux gt = globtree_new(GLOBTREE_REGEX); 137156230Smux gt->data = xmalloc(sizeof(regex_t)); 138156230Smux error = regcomp(gt->data, pattern, REG_NOSUB); 139156230Smux assert(!error); 140156230Smux return (gt); 141156230Smux} 142156230Smux 143156230Smuxstruct globtree * 144156230Smuxglobtree_and(struct globtree *left, struct globtree *right) 145156230Smux{ 146156230Smux struct globtree *gt; 147156230Smux 148156230Smux if (left->type == GLOBTREE_FALSE || right->type == GLOBTREE_FALSE) { 149156230Smux globtree_free(left); 150156230Smux globtree_free(right); 151156230Smux gt = globtree_false(); 152156230Smux return (gt); 153156230Smux } 154156230Smux if (left->type == GLOBTREE_TRUE) { 155156230Smux globtree_free(left); 156156230Smux return (right); 157156230Smux } 158156230Smux if (right->type == GLOBTREE_TRUE) { 159156230Smux globtree_free(right); 160156230Smux return (left); 161156230Smux } 162156230Smux gt = globtree_new(GLOBTREE_AND); 163156230Smux gt->left = left; 164156230Smux gt->right = right; 165156230Smux return (gt); 166156230Smux} 167156230Smux 168156230Smuxstruct globtree * 169156230Smuxglobtree_or(struct globtree *left, struct globtree *right) 170156230Smux{ 171156230Smux struct globtree *gt; 172156230Smux 173156230Smux if (left->type == GLOBTREE_TRUE || right->type == GLOBTREE_TRUE) { 174156230Smux globtree_free(left); 175156230Smux globtree_free(right); 176156230Smux gt = globtree_true(); 177156230Smux return (gt); 178156230Smux } 179156230Smux if (left->type == GLOBTREE_FALSE) { 180156230Smux globtree_free(left); 181156230Smux return (right); 182156230Smux } 183156230Smux if (right->type == GLOBTREE_FALSE) { 184156230Smux globtree_free(right); 185156230Smux return (left); 186156230Smux } 187156230Smux gt = globtree_new(GLOBTREE_OR); 188156230Smux gt->left = left; 189156230Smux gt->right = right; 190156230Smux return (gt); 191156230Smux} 192156230Smux 193156230Smuxstruct globtree * 194156230Smuxglobtree_not(struct globtree *child) 195156230Smux{ 196156230Smux struct globtree *gt; 197156230Smux 198156230Smux if (child->type == GLOBTREE_TRUE) { 199156230Smux globtree_free(child); 200156230Smux gt = globtree_new(GLOBTREE_FALSE); 201156230Smux return (gt); 202156230Smux } 203156230Smux if (child->type == GLOBTREE_FALSE) { 204156230Smux globtree_free(child); 205156230Smux gt = globtree_new(GLOBTREE_TRUE); 206156230Smux return (gt); 207156230Smux } 208156230Smux gt = globtree_new(GLOBTREE_NOT); 209156230Smux gt->left = child; 210156230Smux return (gt); 211156230Smux} 212156230Smux 213156230Smux/* Evaluate one node (must be a leaf node). */ 214156230Smuxstatic int 215156230Smuxglobtree_eval(struct globtree *gt, const char *path) 216156230Smux{ 217156230Smux int rv; 218156230Smux 219156230Smux switch (gt->type) { 220156230Smux case GLOBTREE_TRUE: 221156230Smux return (1); 222156230Smux case GLOBTREE_FALSE: 223156230Smux return (0); 224156230Smux case GLOBTREE_MATCH: 225156230Smux assert(gt->data != NULL); 226156230Smux rv = fnmatch(gt->data, path, gt->flags); 227156230Smux if (rv == 0) 228156230Smux return (1); 229156230Smux assert(rv == FNM_NOMATCH); 230156230Smux return (0); 231156230Smux case GLOBTREE_REGEX: 232156230Smux assert(gt->data != NULL); 233156230Smux rv = regexec(gt->data, path, 0, NULL, 0); 234156230Smux if (rv == 0) 235156230Smux return (1); 236156230Smux assert(rv == REG_NOMATCH); 237156230Smux return (0); 238156230Smux } 239156230Smux 240156230Smux assert(0); 241156230Smux return (-1); 242156230Smux} 243156230Smux 244156230Smux/* Small stack API to walk the tree iteratively. */ 245156230Smuxtypedef enum { 246156230Smux STATE_DOINGLEFT, 247156230Smux STATE_DOINGRIGHT 248156230Smux} walkstate_t; 249156230Smux 250156230Smuxstruct stack { 251156230Smux struct stackelem *stack; 252156230Smux size_t size; 253156230Smux size_t in; 254156230Smux}; 255156230Smux 256156230Smuxstruct stackelem { 257156230Smux struct globtree *node; 258156230Smux walkstate_t state; 259156230Smux}; 260156230Smux 261156230Smuxstatic void 262156230Smuxstack_init(struct stack *stack) 263156230Smux{ 264156230Smux 265156230Smux stack->in = 0; 266156230Smux stack->size = 8; /* Initial size. */ 267156230Smux stack->stack = xmalloc(sizeof(struct stackelem) * stack->size); 268156230Smux} 269156230Smux 270156230Smuxstatic size_t 271156230Smuxstack_size(struct stack *stack) 272156230Smux{ 273156230Smux 274156230Smux return (stack->in); 275156230Smux} 276156230Smux 277156230Smuxstatic void 278156230Smuxstack_push(struct stack *stack, struct globtree *node, walkstate_t state) 279156230Smux{ 280156230Smux struct stackelem *e; 281156230Smux 282156230Smux if (stack->in == stack->size) { 283156230Smux stack->size *= 2; 284156230Smux stack->stack = xrealloc(stack->stack, 285156230Smux sizeof(struct stackelem) * stack->size); 286156230Smux } 287156230Smux e = stack->stack + stack->in++; 288156230Smux e->node = node; 289156230Smux e->state = state; 290156230Smux} 291156230Smux 292156230Smuxstatic void 293156230Smuxstack_pop(struct stack *stack, struct globtree **node, walkstate_t *state) 294156230Smux{ 295156230Smux struct stackelem *e; 296156230Smux 297156230Smux assert(stack->in > 0); 298156230Smux e = stack->stack + --stack->in; 299156230Smux *node = e->node; 300156230Smux *state = e->state; 301156230Smux} 302156230Smux 303156230Smuxstatic void 304156230Smuxstack_free(struct stack *s) 305156230Smux{ 306156230Smux 307156230Smux free(s->stack); 308156230Smux} 309156230Smux 310156230Smux/* Tests if the supplied filename matches. */ 311156230Smuxint 312156230Smuxglobtree_test(struct globtree *gt, const char *path) 313156230Smux{ 314156230Smux struct stack stack; 315156230Smux walkstate_t state; 316156230Smux int val; 317156230Smux 318156230Smux stack_init(&stack); 319156230Smux for (;;) { 320156230Smuxdoleft: 321156230Smux /* Descend to the left until we hit bottom. */ 322156230Smux while (gt->left != NULL) { 323156230Smux stack_push(&stack, gt, STATE_DOINGLEFT); 324156230Smux gt = gt->left; 325156230Smux } 326156230Smux 327156230Smux /* Now we're at a leaf node. Evaluate it. */ 328156230Smux val = globtree_eval(gt, path); 329156230Smux /* Ascend, propagating the value through operator nodes. */ 330156230Smux for (;;) { 331156230Smux if (stack_size(&stack) == 0) { 332156230Smux stack_free(&stack); 333156230Smux return (val); 334156230Smux } 335156230Smux stack_pop(&stack, >, &state); 336156230Smux switch (gt->type) { 337156230Smux case GLOBTREE_NOT: 338156230Smux val = !val; 339156230Smux break; 340156230Smux case GLOBTREE_AND: 341156230Smux /* If we haven't yet evaluated the right subtree 342156230Smux and the partial result is true, descend to 343156230Smux the right. Otherwise the result is already 344156230Smux determined to be val. */ 345156230Smux if (state == STATE_DOINGLEFT && val) { 346156230Smux stack_push(&stack, gt, 347156230Smux STATE_DOINGRIGHT); 348156230Smux gt = gt->right; 349156230Smux goto doleft; 350156230Smux } 351156230Smux break; 352156230Smux case GLOBTREE_OR: 353156230Smux /* If we haven't yet evaluated the right subtree 354156230Smux and the partial result is false, descend to 355156230Smux the right. Otherwise the result is already 356156230Smux determined to be val. */ 357156230Smux if (state == STATE_DOINGLEFT && !val) { 358156230Smux stack_push(&stack, gt, 359156230Smux STATE_DOINGRIGHT); 360156230Smux gt = gt->right; 361156230Smux goto doleft; 362156230Smux } 363156230Smux break; 364156230Smux default: 365156230Smux /* We only push nodes that have children. */ 366156230Smux assert(0); 367156230Smux return (-1); 368156230Smux } 369156230Smux } 370156230Smux } 371156230Smux} 372156230Smux 373156230Smux/* 374156230Smux * We could de-recursify this function using a stack, but it would be 375156230Smux * overkill since it is never called from a thread context with a 376156230Smux * limited stack size nor used in a critical path, so I think we can 377156230Smux * afford keeping it recursive. 378156230Smux */ 379156230Smuxvoid 380156230Smuxglobtree_free(struct globtree *gt) 381156230Smux{ 382156230Smux 383156230Smux if (gt->data != NULL) { 384156230Smux if (gt->type == GLOBTREE_REGEX) 385156230Smux regfree(gt->data); 386156230Smux free(gt->data); 387156230Smux } 388156230Smux if (gt->left != NULL) 389156230Smux globtree_free(gt->left); 390156230Smux if (gt->right != NULL) 391156230Smux globtree_free(gt->right); 392156230Smux free(gt); 393156230Smux} 394