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 7612 : static int _count_nodes(struct rx_node *rx)
43 : {
44 7612 : int r = 1;
45 :
46 7612 : if (rx->left)
47 3961 : r += _count_nodes(rx->left);
48 :
49 7612 : if (rx->right)
50 3648 : r += _count_nodes(rx->right);
51 :
52 7612 : return r;
53 : }
54 :
55 7612 : static void _fill_table(struct dm_regex *m, struct rx_node *rx)
56 : {
57 7612 : assert((rx->type != OR) || (rx->left && rx->right));
58 :
59 7612 : if (rx->left)
60 3961 : _fill_table(m, rx->left);
61 :
62 7612 : if (rx->right)
63 3648 : _fill_table(m, rx->right);
64 :
65 7612 : m->nodes[m->nodes_entered++] = rx;
66 7612 : }
67 :
68 3 : static void _create_bitsets(struct dm_regex *m)
69 : {
70 : int i;
71 :
72 7615 : for (i = 0; i < m->num_nodes; i++) {
73 7612 : struct rx_node *n = m->nodes[i];
74 7612 : n->firstpos = dm_bitset_create(m->scratch, m->num_nodes);
75 7612 : n->lastpos = dm_bitset_create(m->scratch, m->num_nodes);
76 7612 : 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 7615 : for (i = 0; i < m->num_nodes; i++) {
86 7612 : rx = m->nodes[i];
87 7612 : c1 = rx->left;
88 7612 : c2 = rx->right;
89 :
90 7612 : if (dm_bit(rx->charset, TARGET_TRANS))
91 308 : rx->final = final++;
92 :
93 7612 : switch (rx->type) {
94 : case CAT:
95 3343 : if (c1->nullable)
96 311 : dm_bit_union(rx->firstpos,
97 : c1->firstpos, c2->firstpos);
98 : else
99 3032 : dm_bit_copy(rx->firstpos, c1->firstpos);
100 :
101 3343 : if (c2->nullable)
102 2 : dm_bit_union(rx->lastpos,
103 : c1->lastpos, c2->lastpos);
104 : else
105 3341 : dm_bit_copy(rx->lastpos, c2->lastpos);
106 :
107 3343 : rx->nullable = c1->nullable && c2->nullable;
108 3343 : 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 305 : dm_bit_union(rx->firstpos, c1->firstpos, c2->firstpos);
118 305 : dm_bit_union(rx->lastpos, c1->lastpos, c2->lastpos);
119 305 : rx->nullable = c1->nullable || c2->nullable;
120 305 : break;
121 :
122 : case QUEST:
123 : case STAR:
124 313 : dm_bit_copy(rx->firstpos, c1->firstpos);
125 313 : dm_bit_copy(rx->lastpos, c1->lastpos);
126 313 : rx->nullable = 1;
127 313 : break;
128 :
129 : case CHARSET:
130 3651 : dm_bit_set(rx->firstpos, i);
131 3651 : dm_bit_set(rx->lastpos, i);
132 3651 : rx->nullable = 0;
133 3651 : 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 7612 : switch (rx->type) {
145 : case CAT:
146 24958059 : for (j = 0; j < m->num_nodes; j++) {
147 24954716 : if (dm_bit(c1->lastpos, j)) {
148 3345 : struct rx_node *n = m->nodes[j];
149 3345 : dm_bit_union(n->followpos,
150 : n->followpos, c2->firstpos);
151 : }
152 : }
153 3343 : break;
154 :
155 : case PLUS:
156 : case STAR:
157 2282909 : for (j = 0; j < m->num_nodes; j++) {
158 2282596 : if (dm_bit(rx->lastpos, j)) {
159 313 : struct rx_node *n = m->nodes[j];
160 313 : dm_bit_union(n->followpos,
161 : n->followpos, rx->firstpos);
162 : }
163 : }
164 : break;
165 : }
166 : }
167 3 : }
168 :
169 738 : static struct dfa_state *_create_dfa_state(struct dm_pool *mem)
170 : {
171 738 : return dm_pool_zalloc(mem, sizeof(struct dfa_state));
172 : }
173 :
174 738 : static struct state_queue *_create_state_queue(struct dm_pool *mem,
175 : struct dfa_state *dfa,
176 : dm_bitset_t bits)
177 : {
178 738 : struct state_queue *r = dm_pool_alloc(mem, sizeof(*r));
179 :
180 738 : if (!r) {
181 0 : stack;
182 0 : return NULL;
183 : }
184 :
185 738 : r->s = dfa;
186 738 : r->bits = dm_bitset_create(mem, bits[0]); /* first element is the size */
187 738 : dm_bit_copy(r->bits, bits);
188 738 : r->next = 0;
189 738 : 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 744 : while (h) {
215 : /* pop state off front of the queue */
216 738 : dfa = h->s;
217 738 : dfa_bits = h->bits;
218 738 : h = h->next;
219 :
220 : /* iterate through all the inputs for this state */
221 738 : dm_bit_clear_all(bs);
222 189666 : for (a = 0; a < 256; a++) {
223 : /* iterate through all the states in firstpos */
224 108567552 : for (i = dm_bit_get_first(dfa_bits);
225 108189696 : i >= 0; i = dm_bit_get_next(dfa_bits, i)) {
226 108189696 : if (dm_bit(m->nodes[i]->charset, a)) {
227 52999896 : if (a == TARGET_TRANS)
228 1342 : dfa->final = m->nodes[i]->final;
229 :
230 52999896 : dm_bit_union(bs, bs,
231 52999896 : m->nodes[i]->followpos);
232 52999896 : set_bits = 1;
233 : }
234 : }
235 :
236 188928 : if (set_bits) {
237 185928 : ldfa = ttree_lookup(tt, bs + 1);
238 185928 : if (!ldfa) {
239 : /* push */
240 735 : ldfa = _create_dfa_state(m->mem);
241 735 : ttree_insert(tt, bs + 1, ldfa);
242 735 : tmp =
243 735 : _create_state_queue(m->scratch,
244 : ldfa, bs);
245 735 : if (!h)
246 3 : h = t = tmp;
247 : else {
248 732 : t->next = tmp;
249 732 : t = tmp;
250 : }
251 :
252 735 : count++;
253 : }
254 :
255 185928 : dfa->lookup[a] = ldfa;
256 185928 : set_bits = 0;
257 185928 : 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 311 : for (i = 0; i < num_patterns; i++)
288 308 : 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 311 : for (i = 0; i < num_patterns; i++) {
296 308 : ptr += sprintf(ptr, "(.*(%s)%c)", patterns[i], TARGET_TRANS);
297 308 : if (i < (num_patterns - 1))
298 305 : *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 0 : return NULL;
328 : }
329 :
330 11590 : static struct dfa_state *_step_matcher(int c, struct dfa_state *cs, int *r)
331 : {
332 11590 : if (!(cs = cs->lookup[(unsigned char) c]))
333 0 : return NULL;
334 :
335 11590 : if (cs->final && (cs->final > *r))
336 821 : *r = cs->final;
337 :
338 11590 : return cs;
339 : }
340 :
341 520 : int dm_regex_match(struct dm_regex *regex, const char *s)
342 : {
343 520 : struct dfa_state *cs = regex->start;
344 520 : int r = 0;
345 :
346 520 : if (!(cs = _step_matcher(HAT_CHAR, cs, &r)))
347 0 : goto out;
348 :
349 11070 : for (; *s; s++)
350 10550 : if (!(cs = _step_matcher(*s, cs, &r)))
351 0 : goto out;
352 :
353 520 : _step_matcher(DOLLAR_CHAR, cs, &r);
354 :
355 : out:
356 : /* subtract 1 to get back to zero index */
357 520 : return r - 1;
358 : }
|
