Branch data Line data Source code
1 : : /*
2 : : * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
3 : : * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
4 : : *
5 : : * This file is part of the device-mapper userspace tools.
6 : : *
7 : : * This copyrighted material is made available to anyone wishing to use,
8 : : * modify, copy, or redistribute it subject to the terms and conditions
9 : : * of the GNU Lesser General Public License v.2.1.
10 : : *
11 : : * You should have received a copy of the GNU Lesser General Public License
12 : : * along with this program; if not, write to the Free Software Foundation,
13 : : * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
14 : : */
15 : :
16 : : #include "dmlib.h"
17 : : #include "parse_rx.h"
18 : : #include "ttree.h"
19 : : #include "assert.h"
20 : :
21 : : struct dfa_state {
22 : : int final;
23 : : struct dfa_state *lookup[256];
24 : : };
25 : :
26 : : struct state_queue {
27 : : struct dfa_state *s;
28 : : dm_bitset_t bits;
29 : : struct state_queue *next;
30 : : };
31 : :
32 : : struct dm_regex { /* Instance variables for the lexer */
33 : : struct dfa_state *start;
34 : : unsigned num_nodes;
35 : : int nodes_entered;
36 : : struct rx_node **nodes;
37 : : struct dm_pool *scratch, *mem;
38 : : };
39 : :
40 : : #define TARGET_TRANS '\0'
41 : :
42 : 7682 : static int _count_nodes(struct rx_node *rx)
43 : : {
44 : 7682 : int r = 1;
45 : :
46 [ + + ]: 7682 : if (rx->left)
47 : 3997 : r += _count_nodes(rx->left);
48 : :
49 [ + + ]: 7682 : if (rx->right)
50 : 3682 : r += _count_nodes(rx->right);
51 : :
52 : 7682 : return r;
53 : : }
54 : :
55 : 7682 : static void _fill_table(struct dm_regex *m, struct rx_node *rx)
56 : : {
57 [ + + ][ + - ]: 7682 : assert((rx->type != OR) || (rx->left && rx->right));
[ - + ]
58 : :
59 [ + + ]: 7682 : if (rx->left)
60 : 3997 : _fill_table(m, rx->left);
61 : :
62 [ + + ]: 7682 : if (rx->right)
63 : 3682 : _fill_table(m, rx->right);
64 : :
65 : 7682 : m->nodes[m->nodes_entered++] = rx;
66 : 7682 : }
67 : :
68 : 3 : static void _create_bitsets(struct dm_regex *m)
69 : : {
70 : : int i;
71 : :
72 [ + + ]: 7685 : for (i = 0; i < m->num_nodes; i++) {
73 : 7682 : struct rx_node *n = m->nodes[i];
74 : 7682 : n->firstpos = dm_bitset_create(m->scratch, m->num_nodes);
75 : 7682 : n->lastpos = dm_bitset_create(m->scratch, m->num_nodes);
76 : 7682 : n->followpos = dm_bitset_create(m->scratch, m->num_nodes);
77 : : }
78 : 3 : }
79 : :
80 : 3 : static void _calc_functions(struct dm_regex *m)
81 : : {
82 : 3 : int i, j, final = 1;
83 : : struct rx_node *rx, *c1, *c2;
84 : :
85 [ + + ]: 7685 : for (i = 0; i < m->num_nodes; i++) {
86 : 7682 : rx = m->nodes[i];
87 : 7682 : c1 = rx->left;
88 : 7682 : c2 = rx->right;
89 : :
90 [ + + ]: 7682 : if (dm_bit(rx->charset, TARGET_TRANS))
91 : 312 : rx->final = final++;
92 : :
93 [ + - + + + : 7682 : switch (rx->type) {
- ]
94 : : case CAT:
95 [ + + ]: 3373 : if (c1->nullable)
96 : 315 : dm_bit_union(rx->firstpos,
97 : : c1->firstpos, c2->firstpos);
98 : : else
99 : 3058 : dm_bit_copy(rx->firstpos, c1->firstpos);
100 : :
101 [ - + ]: 3373 : if (c2->nullable)
102 : 0 : dm_bit_union(rx->lastpos,
103 : : c1->lastpos, c2->lastpos);
104 : : else
105 : 3373 : dm_bit_copy(rx->lastpos, c2->lastpos);
106 : :
107 [ + + ][ - + ]: 3373 : rx->nullable = c1->nullable && c2->nullable;
108 : 3373 : break;
109 : :
110 : : case PLUS:
111 : 0 : dm_bit_copy(rx->firstpos, c1->firstpos);
112 : 0 : dm_bit_copy(rx->lastpos, c1->lastpos);
113 : 0 : rx->nullable = c1->nullable;
114 : 0 : break;
115 : :
116 : : case OR:
117 : 309 : dm_bit_union(rx->firstpos, c1->firstpos, c2->firstpos);
118 : 309 : dm_bit_union(rx->lastpos, c1->lastpos, c2->lastpos);
119 [ + - - + ]: 309 : rx->nullable = c1->nullable || c2->nullable;
120 : 309 : break;
121 : :
122 : : case QUEST:
123 : : case STAR:
124 : 315 : dm_bit_copy(rx->firstpos, c1->firstpos);
125 : 315 : dm_bit_copy(rx->lastpos, c1->lastpos);
126 : 315 : rx->nullable = 1;
127 : 315 : break;
128 : :
129 : : case CHARSET:
130 : 3685 : dm_bit_set(rx->firstpos, i);
131 : 3685 : dm_bit_set(rx->lastpos, i);
132 : 3685 : rx->nullable = 0;
133 : 3685 : break;
134 : :
135 : : default:
136 [ # # ]: 0 : log_error(INTERNAL_ERROR "Unknown calc node type");
137 : : }
138 : :
139 : : /*
140 : : * followpos has it's own switch
141 : : * because PLUS and STAR do the
142 : : * same thing.
143 : : */
144 [ + + + ]: 7682 : switch (rx->type) {
145 : : case CAT:
146 [ + + ]: 24961389 : for (j = 0; j < m->num_nodes; j++) {
147 [ + + ]: 24958016 : if (dm_bit(c1->lastpos, j)) {
148 : 3373 : struct rx_node *n = m->nodes[j];
149 : 3373 : dm_bit_union(n->followpos,
150 : : n->followpos, c2->firstpos);
151 : : }
152 : : }
153 : 3373 : break;
154 : :
155 : : case PLUS:
156 : : case STAR:
157 [ + + ]: 2283411 : for (j = 0; j < m->num_nodes; j++) {
158 [ + + ]: 2283096 : if (dm_bit(rx->lastpos, j)) {
159 : 315 : struct rx_node *n = m->nodes[j];
160 : 315 : dm_bit_union(n->followpos,
161 : : n->followpos, rx->firstpos);
162 : : }
163 : : }
164 : : break;
165 : : }
166 : : }
167 : 3 : }
168 : :
169 : 790 : static struct dfa_state *_create_dfa_state(struct dm_pool *mem)
170 : : {
171 : 790 : return dm_pool_zalloc(mem, sizeof(struct dfa_state));
172 : : }
173 : :
174 : 790 : static struct state_queue *_create_state_queue(struct dm_pool *mem,
175 : : struct dfa_state *dfa,
176 : : dm_bitset_t bits)
177 : : {
178 : 790 : struct state_queue *r = dm_pool_alloc(mem, sizeof(*r));
179 : :
180 [ - + ]: 790 : if (!r) {
181 [ # # ]: 0 : stack;
182 : 0 : return NULL;
183 : : }
184 : :
185 : 790 : r->s = dfa;
186 : 790 : r->bits = dm_bitset_create(mem, bits[0]); /* first element is the size */
187 : 790 : dm_bit_copy(r->bits, bits);
188 : 790 : r->next = 0;
189 : 790 : return r;
190 : : }
191 : :
192 : 3 : static int _calc_states(struct dm_regex *m, struct rx_node *rx)
193 : : {
194 : 3 : unsigned iwidth = (m->num_nodes / DM_BITS_PER_INT) + 1;
195 : 3 : struct ttree *tt = ttree_create(m->scratch, iwidth);
196 : : struct state_queue *h, *t, *tmp;
197 : : struct dfa_state *dfa, *ldfa;
198 : 3 : int i, a, set_bits = 0, count = 0;
199 : : dm_bitset_t bs, dfa_bits;
200 : :
201 [ - + ]: 3 : if (!tt)
202 [ # # ]: 0 : return_0;
203 : :
204 [ - + ]: 3 : if (!(bs = dm_bitset_create(m->scratch, m->num_nodes)))
205 [ # # ]: 0 : return_0;
206 : :
207 : : /* create first state */
208 : 3 : dfa = _create_dfa_state(m->mem);
209 : 3 : m->start = dfa;
210 : 3 : ttree_insert(tt, rx->firstpos + 1, dfa);
211 : :
212 : : /* prime the queue */
213 : 3 : h = t = _create_state_queue(m->scratch, dfa, rx->firstpos);
214 [ + + ]: 793 : while (h) {
215 : : /* pop state off front of the queue */
216 : 790 : dfa = h->s;
217 : 790 : dfa_bits = h->bits;
218 : 790 : h = h->next;
219 : :
220 : : /* iterate through all the inputs for this state */
221 : 790 : dm_bit_clear_all(bs);
222 [ + + ]: 203030 : for (a = 0; a < 256; a++) {
223 : : /* iterate through all the states in firstpos */
224 [ + + ]: 108596736 : for (i = dm_bit_get_first(dfa_bits);
225 : 108394496 : i >= 0; i = dm_bit_get_next(dfa_bits, i)) {
226 [ + + ]: 108394496 : if (dm_bit(m->nodes[i]->charset, a)) {
227 [ + + ]: 53101516 : if (a == TARGET_TRANS)
228 : 1402 : dfa->final = m->nodes[i]->final;
229 : :
230 : 53101516 : dm_bit_union(bs, bs,
231 : 53101516 : m->nodes[i]->followpos);
232 : 53101516 : set_bits = 1;
233 : : }
234 : : }
235 : :
236 [ + + ]: 202240 : if (set_bits) {
237 : 199136 : ldfa = ttree_lookup(tt, bs + 1);
238 [ + + ]: 199136 : if (!ldfa) {
239 : : /* push */
240 : 787 : ldfa = _create_dfa_state(m->mem);
241 : 787 : ttree_insert(tt, bs + 1, ldfa);
242 : 787 : tmp =
243 : 787 : _create_state_queue(m->scratch,
244 : : ldfa, bs);
245 [ + + ]: 787 : if (!h)
246 : 3 : h = t = tmp;
247 : : else {
248 : 784 : t->next = tmp;
249 : 784 : t = tmp;
250 : : }
251 : :
252 : 787 : count++;
253 : : }
254 : :
255 : 199136 : dfa->lookup[a] = ldfa;
256 : 199136 : set_bits = 0;
257 : 199136 : dm_bit_clear_all(bs);
258 : : }
259 : : }
260 : : }
261 : :
262 [ - + ]: 3 : log_debug("Matcher built with %d dfa states", count);
263 : 3 : return 1;
264 : : }
265 : :
266 : 3 : struct dm_regex *dm_regex_create(struct dm_pool *mem, const char **patterns,
267 : : unsigned num_patterns)
268 : : {
269 : : char *all, *ptr;
270 : : int i;
271 : 3 : size_t len = 0;
272 : : struct rx_node *rx;
273 : 3 : struct dm_pool *scratch = dm_pool_create("regex matcher", 10 * 1024);
274 : : struct dm_regex *m;
275 : :
276 [ - + ]: 3 : if (!scratch)
277 [ # # ]: 0 : return_NULL;
278 : :
279 [ - + ]: 3 : if (!(m = dm_pool_alloc(mem, sizeof(*m)))) {
280 : 0 : dm_pool_destroy(scratch);
281 [ # # ]: 0 : return_NULL;
282 : : }
283 : :
284 : 3 : memset(m, 0, sizeof(*m));
285 : :
286 : : /* join the regexps together, delimiting with zero */
287 [ + + ]: 315 : for (i = 0; i < num_patterns; i++)
288 : 312 : len += strlen(patterns[i]) + 8;
289 : :
290 : 3 : ptr = all = dm_pool_alloc(scratch, len + 1);
291 : :
292 [ - + ]: 3 : if (!all)
293 [ # # ]: 0 : goto_bad;
294 : :
295 [ + + ]: 315 : for (i = 0; i < num_patterns; i++) {
296 : 312 : ptr += sprintf(ptr, "(.*(%s)%c)", patterns[i], TARGET_TRANS);
297 [ + + ]: 312 : if (i < (num_patterns - 1))
298 : 309 : *ptr++ = '|';
299 : : }
300 : :
301 : : /* parse this expression */
302 [ - + ]: 3 : if (!(rx = rx_parse_tok(scratch, all, ptr))) {
303 [ # # ]: 0 : log_error("Couldn't parse regex");
304 : 0 : goto bad;
305 : : }
306 : :
307 : 3 : m->mem = mem;
308 : 3 : m->scratch = scratch;
309 : 3 : m->num_nodes = _count_nodes(rx);
310 : 3 : m->nodes = dm_pool_alloc(scratch, sizeof(*m->nodes) * m->num_nodes);
311 : :
312 [ - + ]: 3 : if (!m->nodes)
313 [ # # ]: 0 : goto_bad;
314 : :
315 : 3 : _fill_table(m, rx);
316 : 3 : _create_bitsets(m);
317 : 3 : _calc_functions(m);
318 : 3 : _calc_states(m, rx);
319 : 3 : dm_pool_destroy(scratch);
320 : 3 : m->scratch = NULL;
321 : :
322 : 3 : return m;
323 : :
324 : : bad:
325 : 0 : dm_pool_destroy(scratch);
326 : 0 : dm_pool_free(mem, m);
327 : 3 : return NULL;
328 : : }
329 : :
330 : 3542 : static struct dfa_state *_step_matcher(int c, struct dfa_state *cs, int *r)
331 : : {
332 [ - + ]: 3542 : if (!(cs = cs->lookup[(unsigned char) c]))
333 : 0 : return NULL;
334 : :
335 [ + - ][ + + ]: 3542 : if (cs->final && (cs->final > *r))
336 : 121 : *r = cs->final;
337 : :
338 : 3542 : return cs;
339 : : }
340 : :
341 : 121 : int dm_regex_match(struct dm_regex *regex, const char *s)
342 : : {
343 : 121 : struct dfa_state *cs = regex->start;
344 : 121 : int r = 0;
345 : :
346 [ - + ]: 121 : if (!(cs = _step_matcher(HAT_CHAR, cs, &r)))
347 : 0 : goto out;
348 : :
349 [ + + ]: 3421 : for (; *s; s++)
350 [ - + ]: 3300 : if (!(cs = _step_matcher(*s, cs, &r)))
351 : 0 : goto out;
352 : :
353 : 121 : _step_matcher(DOLLAR_CHAR, cs, &r);
354 : :
355 : : out:
356 : : /* subtract 1 to get back to zero index */
357 : 121 : return r - 1;
358 : : }
|
