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 5504 : static int _rx_get_token(struct parse_sp *ps)
42 : {
43 5504 : int neg = 0, range = 0;
44 5504 : char c, lc = 0;
45 5504 : const char *ptr = ps->cursor;
46 5504 : if (ptr == ps->rx_end) { /* end of input ? */
47 3 : ps->type = -1;
48 3 : return 0;
49 : }
50 :
51 5501 : switch (*ptr) {
52 : /* charsets and ncharsets */
53 : case '[':
54 0 : ptr++;
55 0 : 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 0 : dm_bit_clear_all(ps->charset);
65 :
66 0 : while ((ptr < ps->rx_end) && (*ptr != ']')) {
67 0 : 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 0 : } else if (*ptr == '-' && lc) {
84 : /* we've got a range on our hands */
85 0 : range = 1;
86 0 : ptr++;
87 0 : if (ptr == ps->rx_end) {
88 0 : log_error("Incomplete range"
89 : "specification");
90 0 : return -1;
91 : }
92 0 : c = *ptr;
93 : } else
94 0 : c = *ptr;
95 :
96 0 : if (range) {
97 : /* add lc - c into the bitset */
98 0 : if (lc > c) {
99 0 : char tmp = c;
100 0 : c = lc;
101 0 : lc = tmp;
102 : }
103 :
104 0 : for (; lc <= c; lc++) {
105 0 : if (neg)
106 0 : dm_bit_clear(ps->charset, lc);
107 : else
108 0 : dm_bit_set(ps->charset, lc);
109 : }
110 0 : range = 0;
111 : } else {
112 : /* add c into the bitset */
113 0 : if (neg)
114 0 : dm_bit_clear(ps->charset, c);
115 : else
116 0 : dm_bit_set(ps->charset, c);
117 : }
118 0 : ptr++;
119 0 : lc = c;
120 : }
121 :
122 0 : if (ptr >= ps->rx_end) {
123 0 : ps->type = -1;
124 0 : return -1;
125 : }
126 :
127 0 : ps->type = 0;
128 0 : ps->cursor = ptr + 1;
129 0 : 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 1850 : ps->type = (int) *ptr;
141 1850 : ps->cursor = ptr + 1;
142 1850 : 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 311 : ps->type = 0;
155 311 : ps->cursor = ptr + 1;
156 311 : dm_bit_set_all(ps->charset);
157 311 : dm_bit_clear(ps->charset, (int) '\n');
158 311 : dm_bit_clear(ps->charset, (int) '\r');
159 311 : dm_bit_clear(ps->charset, 0);
160 311 : 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 3340 : ps->type = 0;
193 3340 : ps->cursor = ptr + 1;
194 3340 : dm_bit_clear_all(ps->charset);
195 3340 : dm_bit_set(ps->charset, (int) *ptr);
196 : break;
197 : }
198 :
199 5501 : return 1;
200 : }
201 :
202 7612 : static struct rx_node *_node(struct dm_pool *mem, int type,
203 : struct rx_node *l, struct rx_node *r)
204 : {
205 7612 : struct rx_node *n = dm_pool_zalloc(mem, sizeof(*n));
206 :
207 7612 : if (n) {
208 7612 : if (!(n->charset = dm_bitset_create(mem, 256))) {
209 0 : dm_pool_free(mem, n);
210 0 : return NULL;
211 : }
212 :
213 7612 : n->type = type;
214 7612 : n->left = l;
215 7612 : n->right = r;
216 : }
217 :
218 7612 : return n;
219 : }
220 :
221 4886 : static struct rx_node *_term(struct parse_sp *ps)
222 : {
223 : struct rx_node *n;
224 :
225 4886 : switch (ps->type) {
226 : case 0:
227 3651 : if (!(n = _node(ps->mem, CHARSET, NULL, NULL))) {
228 0 : stack;
229 0 : return NULL;
230 : }
231 :
232 3651 : dm_bit_copy(n->charset, ps->charset);
233 3651 : _rx_get_token(ps); /* match charset */
234 3651 : break;
235 :
236 : case '(':
237 616 : _rx_get_token(ps); /* match '(' */
238 616 : n = _or_term(ps);
239 616 : if (ps->type != ')') {
240 0 : log_error("missing ')' in regular expression");
241 0 : return 0;
242 : }
243 616 : _rx_get_token(ps); /* match ')' */
244 616 : break;
245 :
246 : default:
247 619 : n = 0;
248 : }
249 :
250 4886 : return n;
251 : }
252 :
253 4886 : static struct rx_node *_closure_term(struct parse_sp *ps)
254 : {
255 : struct rx_node *l, *n;
256 :
257 4886 : if (!(l = _term(ps)))
258 619 : return NULL;
259 :
260 : for (;;) {
261 4580 : switch (ps->type) {
262 : case '*':
263 313 : n = _node(ps->mem, STAR, l, NULL);
264 313 : 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 4267 : return l;
276 : }
277 :
278 313 : if (!n) {
279 0 : stack;
280 0 : return NULL;
281 : }
282 :
283 313 : _rx_get_token(ps);
284 313 : l = n;
285 313 : }
286 :
287 : return n;
288 : }
289 :
290 4886 : static struct rx_node *_cat_term(struct parse_sp *ps)
291 : {
292 : struct rx_node *l, *r, *n;
293 :
294 4886 : if (!(l = _closure_term(ps)))
295 619 : return NULL;
296 :
297 4267 : if (ps->type == '|')
298 305 : return l;
299 :
300 3962 : if (!(r = _cat_term(ps)))
301 619 : return l;
302 :
303 3343 : if (!(n = _node(ps->mem, CAT, l, r)))
304 0 : stack;
305 :
306 3343 : return n;
307 : }
308 :
309 924 : static struct rx_node *_or_term(struct parse_sp *ps)
310 : {
311 : struct rx_node *l, *r, *n;
312 :
313 924 : if (!(l = _cat_term(ps)))
314 0 : return NULL;
315 :
316 924 : if (ps->type != '|')
317 619 : return l;
318 :
319 305 : _rx_get_token(ps); /* match '|' */
320 :
321 305 : if (!(r = _or_term(ps))) {
322 0 : log_error("Badly formed 'or' expression");
323 0 : return NULL;
324 : }
325 :
326 305 : if (!(n = _node(ps->mem, OR, l, r)))
327 0 : stack;
328 :
329 305 : 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 : }
|
