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 : :
19 : : struct parse_sp { /* scratch pad for the parsing process */
20 : : struct dm_pool *mem;
21 : : int type; /* token type, 0 indicates a charset */
22 : : dm_bitset_t charset; /* The current charset */
23 : : const char *cursor; /* where we are in the regex */
24 : : const char *rx_end; /* 1pte for the expression being parsed */
25 : : };
26 : :
27 : : static struct rx_node *_or_term(struct parse_sp *ps);
28 : :
29 : 0 : static void _single_char(struct parse_sp *ps, unsigned int c, const char *ptr)
30 : : {
31 : 0 : ps->type = 0;
32 : 0 : ps->cursor = ptr + 1;
33 : 0 : dm_bit_clear_all(ps->charset);
34 : 0 : dm_bit_set(ps->charset, c);
35 : 0 : }
36 : :
37 : : /*
38 : : * Get the next token from the regular expression.
39 : : * Returns: 1 success, 0 end of input, -1 error.
40 : : */
41 : 5560 : static int _rx_get_token(struct parse_sp *ps)
42 : : {
43 : 5560 : int neg = 0, range = 0;
44 : 5560 : char c, lc = 0;
45 : 5560 : const char *ptr = ps->cursor;
46 [ + + ]: 5560 : if (ptr == ps->rx_end) { /* end of input ? */
47 : 3 : ps->type = -1;
48 : 3 : return 0;
49 : : }
50 : :
51 [ + + - - + : 5557 : switch (*ptr) {
- + ]
52 : : /* charsets and ncharsets */
53 : : case '[':
54 : 4 : ptr++;
55 [ - + ]: 4 : if (*ptr == '^') {
56 : 0 : dm_bit_set_all(ps->charset);
57 : :
58 : : /* never transition on zero */
59 : 0 : dm_bit_clear(ps->charset, 0);
60 : 0 : neg = 1;
61 : 0 : ptr++;
62 : :
63 : : } else
64 : 4 : dm_bit_clear_all(ps->charset);
65 : :
66 [ + - ][ + + ]: 12 : while ((ptr < ps->rx_end) && (*ptr != ']')) {
67 [ - + ]: 8 : if (*ptr == '\\') {
68 : : /* an escaped character */
69 : 0 : ptr++;
70 [ # # # # ]: 0 : switch (*ptr) {
71 : : case 'n':
72 : 0 : c = '\n';
73 : 0 : break;
74 : : case 'r':
75 : 0 : c = '\r';
76 : 0 : break;
77 : : case 't':
78 : 0 : c = '\t';
79 : 0 : break;
80 : : default:
81 : 0 : c = *ptr;
82 : : }
83 [ + + ][ + - ]: 10 : } else if (*ptr == '-' && lc) {
84 : : /* we've got a range on our hands */
85 : 2 : range = 1;
86 : 2 : ptr++;
87 [ - + ]: 2 : if (ptr == ps->rx_end) {
88 [ # # ]: 0 : log_error("Incomplete range"
89 : : "specification");
90 : 0 : return -1;
91 : : }
92 : 2 : c = *ptr;
93 : : } else
94 : 6 : c = *ptr;
95 : :
96 [ + + ]: 8 : if (range) {
97 : : /* add lc - c into the bitset */
98 [ - + ]: 2 : if (lc > c) {
99 : 0 : char tmp = c;
100 : 0 : c = lc;
101 : 0 : lc = tmp;
102 : : }
103 : :
104 [ + + ]: 12 : for (; lc <= c; lc++) {
105 [ - + ]: 10 : if (neg)
106 : 0 : dm_bit_clear(ps->charset, lc);
107 : : else
108 : 10 : dm_bit_set(ps->charset, lc);
109 : : }
110 : 2 : range = 0;
111 : : } else {
112 : : /* add c into the bitset */
113 [ - + ]: 6 : if (neg)
114 : 0 : dm_bit_clear(ps->charset, c);
115 : : else
116 : 6 : dm_bit_set(ps->charset, c);
117 : : }
118 : 8 : ptr++;
119 : 8 : lc = c;
120 : : }
121 : :
122 [ - + ]: 4 : if (ptr >= ps->rx_end) {
123 : 0 : ps->type = -1;
124 : 0 : return -1;
125 : : }
126 : :
127 : 4 : ps->type = 0;
128 : 4 : ps->cursor = ptr + 1;
129 : 4 : break;
130 : :
131 : : /* These characters are special, we just return their ASCII
132 : : codes as the type. Sorted into ascending order to help the
133 : : compiler */
134 : : case '(':
135 : : case ')':
136 : : case '*':
137 : : case '+':
138 : : case '?':
139 : : case '|':
140 : 1872 : ps->type = (int) *ptr;
141 : 1872 : ps->cursor = ptr + 1;
142 : 1872 : break;
143 : :
144 : : case '^':
145 : 0 : _single_char(ps, HAT_CHAR, ptr);
146 : 0 : break;
147 : :
148 : : case '$':
149 : 0 : _single_char(ps, DOLLAR_CHAR, ptr);
150 : 0 : break;
151 : :
152 : : case '.':
153 : : /* The 'all but newline' character set */
154 : 315 : ps->type = 0;
155 : 315 : ps->cursor = ptr + 1;
156 : 315 : dm_bit_set_all(ps->charset);
157 : 315 : dm_bit_clear(ps->charset, (int) '\n');
158 : 315 : dm_bit_clear(ps->charset, (int) '\r');
159 : 315 : dm_bit_clear(ps->charset, 0);
160 : 315 : break;
161 : :
162 : : case '\\':
163 : : /* escaped character */
164 : 0 : ptr++;
165 [ # # ]: 0 : if (ptr >= ps->rx_end) {
166 [ # # ]: 0 : log_error("Badly quoted character at end "
167 : : "of expression");
168 : 0 : ps->type = -1;
169 : 0 : return -1;
170 : : }
171 : :
172 : 0 : ps->type = 0;
173 : 0 : ps->cursor = ptr + 1;
174 : 0 : dm_bit_clear_all(ps->charset);
175 [ # # # # ]: 0 : switch (*ptr) {
176 : : case 'n':
177 : 0 : dm_bit_set(ps->charset, (int) '\n');
178 : 0 : break;
179 : : case 'r':
180 : 0 : dm_bit_set(ps->charset, (int) '\r');
181 : 0 : break;
182 : : case 't':
183 : 0 : dm_bit_set(ps->charset, (int) '\t');
184 : 0 : break;
185 : : default:
186 : 0 : dm_bit_set(ps->charset, (int) *ptr);
187 : : }
188 : 0 : break;
189 : :
190 : : default:
191 : : /* add a single character to the bitset */
192 : 3366 : ps->type = 0;
193 : 3366 : ps->cursor = ptr + 1;
194 : 3366 : dm_bit_clear_all(ps->charset);
195 : 3366 : dm_bit_set(ps->charset, (int) *ptr);
196 : : break;
197 : : }
198 : :
199 : 5560 : return 1;
200 : : }
201 : :
202 : 7682 : static struct rx_node *_node(struct dm_pool *mem, int type,
203 : : struct rx_node *l, struct rx_node *r)
204 : : {
205 : 7682 : struct rx_node *n = dm_pool_zalloc(mem, sizeof(*n));
206 : :
207 [ + - ]: 7682 : if (n) {
208 [ - + ]: 7682 : if (!(n->charset = dm_bitset_create(mem, 256))) {
209 : 0 : dm_pool_free(mem, n);
210 : 0 : return NULL;
211 : : }
212 : :
213 : 7682 : n->type = type;
214 : 7682 : n->left = l;
215 : 7682 : n->right = r;
216 : : }
217 : :
218 : 7682 : return n;
219 : : }
220 : :
221 : 4936 : static struct rx_node *_term(struct parse_sp *ps)
222 : : {
223 : : struct rx_node *n;
224 : :
225 [ + + + ]: 4936 : switch (ps->type) {
226 : : case 0:
227 [ - + ]: 3685 : if (!(n = _node(ps->mem, CHARSET, NULL, NULL))) {
228 [ # # ]: 0 : stack;
229 : 0 : return NULL;
230 : : }
231 : :
232 : 3685 : dm_bit_copy(n->charset, ps->charset);
233 : 3685 : _rx_get_token(ps); /* match charset */
234 : 3685 : break;
235 : :
236 : : case '(':
237 : 624 : _rx_get_token(ps); /* match '(' */
238 : 624 : n = _or_term(ps);
239 [ - + ]: 624 : if (ps->type != ')') {
240 [ # # ]: 0 : log_error("missing ')' in regular expression");
241 : 0 : return 0;
242 : : }
243 : 624 : _rx_get_token(ps); /* match ')' */
244 : 624 : break;
245 : :
246 : : default:
247 : 627 : n = 0;
248 : : }
249 : :
250 : 4936 : return n;
251 : : }
252 : :
253 : 4936 : static struct rx_node *_closure_term(struct parse_sp *ps)
254 : : {
255 : : struct rx_node *l, *n;
256 : :
257 [ + + ]: 4936 : if (!(l = _term(ps)))
258 : 627 : return NULL;
259 : :
260 : : for (;;) {
261 [ + - - + ]: 4624 : switch (ps->type) {
262 : : case '*':
263 : 315 : n = _node(ps->mem, STAR, l, NULL);
264 : 315 : break;
265 : :
266 : : case '+':
267 : 0 : n = _node(ps->mem, PLUS, l, NULL);
268 : 0 : break;
269 : :
270 : : case '?':
271 : 0 : n = _node(ps->mem, QUEST, l, NULL);
272 : 0 : break;
273 : :
274 : : default:
275 : 4309 : return l;
276 : : }
277 : :
278 [ - + ]: 315 : if (!n) {
279 [ # # ]: 0 : stack;
280 : 0 : return NULL;
281 : : }
282 : :
283 : 315 : _rx_get_token(ps);
284 : 315 : l = n;
285 : 5251 : }
286 : :
287 : : return n;
288 : : }
289 : :
290 : 4936 : static struct rx_node *_cat_term(struct parse_sp *ps)
291 : : {
292 : : struct rx_node *l, *r, *n;
293 : :
294 [ + + ]: 4936 : if (!(l = _closure_term(ps)))
295 : 627 : return NULL;
296 : :
297 [ + + ]: 4309 : if (ps->type == '|')
298 : 309 : return l;
299 : :
300 [ + + ]: 4000 : if (!(r = _cat_term(ps)))
301 : 627 : return l;
302 : :
303 [ - + ]: 3373 : if (!(n = _node(ps->mem, CAT, l, r)))
304 [ # # ]: 0 : stack;
305 : :
306 : 4936 : return n;
307 : : }
308 : :
309 : 936 : static struct rx_node *_or_term(struct parse_sp *ps)
310 : : {
311 : : struct rx_node *l, *r, *n;
312 : :
313 [ - + ]: 936 : if (!(l = _cat_term(ps)))
314 : 0 : return NULL;
315 : :
316 [ + + ]: 936 : if (ps->type != '|')
317 : 627 : return l;
318 : :
319 : 309 : _rx_get_token(ps); /* match '|' */
320 : :
321 [ - + ]: 309 : if (!(r = _or_term(ps))) {
322 [ # # ]: 0 : log_error("Badly formed 'or' expression");
323 : 0 : return NULL;
324 : : }
325 : :
326 [ - + ]: 309 : if (!(n = _node(ps->mem, OR, l, r)))
327 [ # # ]: 0 : stack;
328 : :
329 : 936 : return n;
330 : : }
331 : :
332 : 3 : struct rx_node *rx_parse_tok(struct dm_pool *mem,
333 : : const char *begin, const char *end)
334 : : {
335 : : struct rx_node *r;
336 : 3 : struct parse_sp *ps = dm_pool_zalloc(mem, sizeof(*ps));
337 : :
338 [ - + ]: 3 : if (!ps) {
339 [ # # ]: 0 : stack;
340 : 0 : return NULL;
341 : : }
342 : :
343 : 3 : ps->mem = mem;
344 : 3 : ps->charset = dm_bitset_create(mem, 256);
345 : 3 : ps->cursor = begin;
346 : 3 : ps->rx_end = end;
347 : 3 : _rx_get_token(ps); /* load the first token */
348 : :
349 [ - + ]: 3 : if (!(r = _or_term(ps))) {
350 [ # # ]: 0 : log_error("Parse error in regex");
351 : 0 : dm_pool_free(mem, ps);
352 : : }
353 : :
354 : 3 : return r;
355 : : }
356 : :
357 : 0 : struct rx_node *rx_parse_str(struct dm_pool *mem, const char *str)
358 : : {
359 : 0 : return rx_parse_tok(mem, str, str + strlen(str));
360 : : }
|