Home | History | Annotate | Download | only in util 
      1 #include "util.h"
      2 #include "string.h"
      3 #include "strfilter.h"
      4 
      5 /* Operators */
      6 static const char *OP_and	= "&";	/* Logical AND */
      7 static const char *OP_or	= "|";	/* Logical OR */
      8 static const char *OP_not	= "!";	/* Logical NOT */
      9 
     10 #define is_operator(c)	((c) == '|' || (c) == '&' || (c) == '!')
     11 #define is_separator(c)	(is_operator(c) || (c) == '(' || (c) == ')')
     12 
     13 static void strfilter_node__delete(struct strfilter_node *self)
     14 {
     15 	if (self) {
     16 		if (self->p && !is_operator(*self->p))
     17 			free((char *)self->p);
     18 		strfilter_node__delete(self->l);
     19 		strfilter_node__delete(self->r);
     20 		free(self);
     21 	}
     22 }
     23 
     24 void strfilter__delete(struct strfilter *self)
     25 {
     26 	if (self) {
     27 		strfilter_node__delete(self->root);
     28 		free(self);
     29 	}
     30 }
     31 
     32 static const char *get_token(const char *s, const char **e)
     33 {
     34 	const char *p;
     35 
     36 	while (isspace(*s))	/* Skip spaces */
     37 		s++;
     38 
     39 	if (*s == '\0') {
     40 		p = s;
     41 		goto end;
     42 	}
     43 
     44 	p = s + 1;
     45 	if (!is_separator(*s)) {
     46 		/* End search */
     47 retry:
     48 		while (*p && !is_separator(*p) && !isspace(*p))
     49 			p++;
     50 		/* Escape and special case: '!' is also used in glob pattern */
     51 		if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) {
     52 			p++;
     53 			goto retry;
     54 		}
     55 	}
     56 end:
     57 	*e = p;
     58 	return s;
     59 }
     60 
     61 static struct strfilter_node *strfilter_node__alloc(const char *op,
     62 						    struct strfilter_node *l,
     63 						    struct strfilter_node *r)
     64 {
     65 	struct strfilter_node *ret = zalloc(sizeof(struct strfilter_node));
     66 
     67 	if (ret) {
     68 		ret->p = op;
     69 		ret->l = l;
     70 		ret->r = r;
     71 	}
     72 
     73 	return ret;
     74 }
     75 
     76 static struct strfilter_node *strfilter_node__new(const char *s,
     77 						  const char **ep)
     78 {
     79 	struct strfilter_node root, *cur, *last_op;
     80 	const char *e;
     81 
     82 	if (!s)
     83 		return NULL;
     84 
     85 	memset(&root, 0, sizeof(root));
     86 	last_op = cur = &root;
     87 
     88 	s = get_token(s, &e);
     89 	while (*s != '\0' && *s != ')') {
     90 		switch (*s) {
     91 		case '&':	/* Exchg last OP->r with AND */
     92 			if (!cur->r || !last_op->r)
     93 				goto error;
     94 			cur = strfilter_node__alloc(OP_and, last_op->r, NULL);
     95 			if (!cur)
     96 				goto nomem;
     97 			last_op->r = cur;
     98 			last_op = cur;
     99 			break;
    100 		case '|':	/* Exchg the root with OR */
    101 			if (!cur->r || !root.r)
    102 				goto error;
    103 			cur = strfilter_node__alloc(OP_or, root.r, NULL);
    104 			if (!cur)
    105 				goto nomem;
    106 			root.r = cur;
    107 			last_op = cur;
    108 			break;
    109 		case '!':	/* Add NOT as a leaf node */
    110 			if (cur->r)
    111 				goto error;
    112 			cur->r = strfilter_node__alloc(OP_not, NULL, NULL);
    113 			if (!cur->r)
    114 				goto nomem;
    115 			cur = cur->r;
    116 			break;
    117 		case '(':	/* Recursively parses inside the parenthesis */
    118 			if (cur->r)
    119 				goto error;
    120 			cur->r = strfilter_node__new(s + 1, &s);
    121 			if (!s)
    122 				goto nomem;
    123 			if (!cur->r || *s != ')')
    124 				goto error;
    125 			e = s + 1;
    126 			break;
    127 		default:
    128 			if (cur->r)
    129 				goto error;
    130 			cur->r = strfilter_node__alloc(NULL, NULL, NULL);
    131 			if (!cur->r)
    132 				goto nomem;
    133 			cur->r->p = strndup(s, e - s);
    134 			if (!cur->r->p)
    135 				goto nomem;
    136 		}
    137 		s = get_token(e, &e);
    138 	}
    139 	if (!cur->r)
    140 		goto error;
    141 	*ep = s;
    142 	return root.r;
    143 nomem:
    144 	s = NULL;
    145 error:
    146 	*ep = s;
    147 	strfilter_node__delete(root.r);
    148 	return NULL;
    149 }
    150 
    151 /*
    152  * Parse filter rule and return new strfilter.
    153  * Return NULL if fail, and *ep == NULL if memory allocation failed.
    154  */
    155 struct strfilter *strfilter__new(const char *rules, const char **err)
    156 {
    157 	struct strfilter *ret = zalloc(sizeof(struct strfilter));
    158 	const char *ep = NULL;
    159 
    160 	if (ret)
    161 		ret->root = strfilter_node__new(rules, &ep);
    162 
    163 	if (!ret || !ret->root || *ep != '\0') {
    164 		if (err)
    165 			*err = ep;
    166 		strfilter__delete(ret);
    167 		ret = NULL;
    168 	}
    169 
    170 	return ret;
    171 }
    172 
    173 static bool strfilter_node__compare(struct strfilter_node *self,
    174 				    const char *str)
    175 {
    176 	if (!self || !self->p)
    177 		return false;
    178 
    179 	switch (*self->p) {
    180 	case '|':	/* OR */
    181 		return strfilter_node__compare(self->l, str) ||
    182 			strfilter_node__compare(self->r, str);
    183 	case '&':	/* AND */
    184 		return strfilter_node__compare(self->l, str) &&
    185 			strfilter_node__compare(self->r, str);
    186 	case '!':	/* NOT */
    187 		return !strfilter_node__compare(self->r, str);
    188 	default:
    189 		return strglobmatch(str, self->p);
    190 	}
    191 }
    192 
    193 /* Return true if STR matches the filter rules */
    194 bool strfilter__compare(struct strfilter *self, const char *str)
    195 {
    196 	if (!self)
    197 		return false;
    198 	return strfilter_node__compare(self->root, str);
    199 }
    200