1a5ecbe62SWolfgang Denk /*
2a5ecbe62SWolfgang Denk * Copyright (c) 2004-2005 Sergey Lyubka <valenok@gmail.com>
3a5ecbe62SWolfgang Denk * All rights reserved
4a5ecbe62SWolfgang Denk *
5a5ecbe62SWolfgang Denk * "THE BEER-WARE LICENSE" (Revision 42):
6a5ecbe62SWolfgang Denk * Sergey Lyubka wrote this file. As long as you retain this notice you
7a5ecbe62SWolfgang Denk * can do whatever you want with this stuff. If we meet some day, and you think
8a5ecbe62SWolfgang Denk * this stuff is worth it, you can buy me a beer in return.
9a5ecbe62SWolfgang Denk */
10a5ecbe62SWolfgang Denk
11a5ecbe62SWolfgang Denk /*
12a5ecbe62SWolfgang Denk * Downloaded Sat Nov 5 17:43:06 CET 2011 at
13a5ecbe62SWolfgang Denk * http://slre.sourceforge.net/1.0/slre.c
14a5ecbe62SWolfgang Denk */
15a5ecbe62SWolfgang Denk
16a5ecbe62SWolfgang Denk #ifdef SLRE_TEST
17a5ecbe62SWolfgang Denk #include <stdio.h>
18a5ecbe62SWolfgang Denk #include <assert.h>
19a5ecbe62SWolfgang Denk #include <ctype.h>
20a5ecbe62SWolfgang Denk #include <stdlib.h>
21a5ecbe62SWolfgang Denk #include <string.h>
22a5ecbe62SWolfgang Denk #else
23a5ecbe62SWolfgang Denk #include <common.h>
24a5ecbe62SWolfgang Denk #include <linux/ctype.h>
25a5ecbe62SWolfgang Denk #endif /* SLRE_TEST */
26a5ecbe62SWolfgang Denk
27a5ecbe62SWolfgang Denk #include <errno.h>
28a5ecbe62SWolfgang Denk
29a5ecbe62SWolfgang Denk #include <slre.h>
30a5ecbe62SWolfgang Denk
31a5ecbe62SWolfgang Denk enum {END, BRANCH, ANY, EXACT, ANYOF, ANYBUT, OPEN, CLOSE, BOL, EOL,
32a5ecbe62SWolfgang Denk STAR, PLUS, STARQ, PLUSQ, QUEST, SPACE, NONSPACE, DIGIT};
33a5ecbe62SWolfgang Denk
34a5ecbe62SWolfgang Denk #ifdef SLRE_TEST
35a5ecbe62SWolfgang Denk static struct {
36a5ecbe62SWolfgang Denk const char *name;
37a5ecbe62SWolfgang Denk int narg;
38a5ecbe62SWolfgang Denk const char *flags;
39a5ecbe62SWolfgang Denk } opcodes[] = {
40a5ecbe62SWolfgang Denk {"END", 0, ""}, /* End of code block or program */
41a5ecbe62SWolfgang Denk {"BRANCH", 2, "oo"}, /* Alternative operator, "|" */
42a5ecbe62SWolfgang Denk {"ANY", 0, ""}, /* Match any character, "." */
43a5ecbe62SWolfgang Denk {"EXACT", 2, "d"}, /* Match exact string */
44a5ecbe62SWolfgang Denk {"ANYOF", 2, "D"}, /* Match any from set, "[]" */
45a5ecbe62SWolfgang Denk {"ANYBUT", 2, "D"}, /* Match any but from set, "[^]"*/
46a5ecbe62SWolfgang Denk {"OPEN ", 1, "i"}, /* Capture start, "(" */
47a5ecbe62SWolfgang Denk {"CLOSE", 1, "i"}, /* Capture end, ")" */
48a5ecbe62SWolfgang Denk {"BOL", 0, ""}, /* Beginning of string, "^" */
49a5ecbe62SWolfgang Denk {"EOL", 0, ""}, /* End of string, "$" */
50a5ecbe62SWolfgang Denk {"STAR", 1, "o"}, /* Match zero or more times "*" */
51a5ecbe62SWolfgang Denk {"PLUS", 1, "o"}, /* Match one or more times, "+" */
52a5ecbe62SWolfgang Denk {"STARQ", 1, "o"}, /* Non-greedy STAR, "*?" */
53a5ecbe62SWolfgang Denk {"PLUSQ", 1, "o"}, /* Non-greedy PLUS, "+?" */
54a5ecbe62SWolfgang Denk {"QUEST", 1, "o"}, /* Match zero or one time, "?" */
55a5ecbe62SWolfgang Denk {"SPACE", 0, ""}, /* Match whitespace, "\s" */
56a5ecbe62SWolfgang Denk {"NONSPACE", 0, ""}, /* Match non-space, "\S" */
57a5ecbe62SWolfgang Denk {"DIGIT", 0, ""} /* Match digit, "\d" */
58a5ecbe62SWolfgang Denk };
59a5ecbe62SWolfgang Denk #endif /* SLRE_TEST */
60a5ecbe62SWolfgang Denk
61a5ecbe62SWolfgang Denk /*
62a5ecbe62SWolfgang Denk * Commands and operands are all unsigned char (1 byte long). All code offsets
63a5ecbe62SWolfgang Denk * are relative to current address, and positive (always point forward). Data
64a5ecbe62SWolfgang Denk * offsets are absolute. Commands with operands:
65a5ecbe62SWolfgang Denk *
66a5ecbe62SWolfgang Denk * BRANCH offset1 offset2
67a5ecbe62SWolfgang Denk * Try to match the code block that follows the BRANCH instruction
68a5ecbe62SWolfgang Denk * (code block ends with END). If no match, try to match code block that
69a5ecbe62SWolfgang Denk * starts at offset1. If either of these match, jump to offset2.
70a5ecbe62SWolfgang Denk *
71a5ecbe62SWolfgang Denk * EXACT data_offset data_length
72a5ecbe62SWolfgang Denk * Try to match exact string. String is recorded in data section from
73a5ecbe62SWolfgang Denk * data_offset, and has length data_length.
74a5ecbe62SWolfgang Denk *
75a5ecbe62SWolfgang Denk * OPEN capture_number
76a5ecbe62SWolfgang Denk * CLOSE capture_number
77a5ecbe62SWolfgang Denk * If the user have passed 'struct cap' array for captures, OPEN
78a5ecbe62SWolfgang Denk * records the beginning of the matched substring (cap->ptr), CLOSE
79a5ecbe62SWolfgang Denk * sets the length (cap->len) for respective capture_number.
80a5ecbe62SWolfgang Denk *
81a5ecbe62SWolfgang Denk * STAR code_offset
82a5ecbe62SWolfgang Denk * PLUS code_offset
83a5ecbe62SWolfgang Denk * QUEST code_offset
84a5ecbe62SWolfgang Denk * *, +, ?, respectively. Try to gobble as much as possible from the
85a5ecbe62SWolfgang Denk * matched buffer, until code block that follows these instructions
86a5ecbe62SWolfgang Denk * matches. When the longest possible string is matched,
87a5ecbe62SWolfgang Denk * jump to code_offset
88a5ecbe62SWolfgang Denk *
89a5ecbe62SWolfgang Denk * STARQ, PLUSQ are non-greedy versions of STAR and PLUS.
90a5ecbe62SWolfgang Denk */
91a5ecbe62SWolfgang Denk
92a5ecbe62SWolfgang Denk static const char *meta_chars = "|.^$*+?()[\\";
93a5ecbe62SWolfgang Denk
94a5ecbe62SWolfgang Denk #ifdef SLRE_TEST
95a5ecbe62SWolfgang Denk
96a5ecbe62SWolfgang Denk static void
print_character_set(FILE * fp,const unsigned char * p,int len)97a5ecbe62SWolfgang Denk print_character_set(FILE *fp, const unsigned char *p, int len)
98a5ecbe62SWolfgang Denk {
99a5ecbe62SWolfgang Denk int i;
100a5ecbe62SWolfgang Denk
101a5ecbe62SWolfgang Denk for (i = 0; i < len; i++) {
102a5ecbe62SWolfgang Denk if (i > 0)
103a5ecbe62SWolfgang Denk (void) fputc(',', fp);
104a5ecbe62SWolfgang Denk if (p[i] == 0) {
105a5ecbe62SWolfgang Denk i++;
106a5ecbe62SWolfgang Denk if (p[i] == 0)
107a5ecbe62SWolfgang Denk (void) fprintf(fp, "\\x%02x", p[i]);
108a5ecbe62SWolfgang Denk else
109a5ecbe62SWolfgang Denk (void) fprintf(fp, "%s", opcodes[p[i]].name);
110a5ecbe62SWolfgang Denk } else if (isprint(p[i])) {
111a5ecbe62SWolfgang Denk (void) fputc(p[i], fp);
112a5ecbe62SWolfgang Denk } else {
113a5ecbe62SWolfgang Denk (void) fprintf(fp, "\\x%02x", p[i]);
114a5ecbe62SWolfgang Denk }
115a5ecbe62SWolfgang Denk }
116a5ecbe62SWolfgang Denk }
117a5ecbe62SWolfgang Denk
118a5ecbe62SWolfgang Denk void
slre_dump(const struct slre * r,FILE * fp)119a5ecbe62SWolfgang Denk slre_dump(const struct slre *r, FILE *fp)
120a5ecbe62SWolfgang Denk {
121a5ecbe62SWolfgang Denk int i, j, ch, op, pc;
122a5ecbe62SWolfgang Denk
123a5ecbe62SWolfgang Denk for (pc = 0; pc < r->code_size; pc++) {
124a5ecbe62SWolfgang Denk
125a5ecbe62SWolfgang Denk op = r->code[pc];
126a5ecbe62SWolfgang Denk (void) fprintf(fp, "%3d %s ", pc, opcodes[op].name);
127a5ecbe62SWolfgang Denk
128a5ecbe62SWolfgang Denk for (i = 0; opcodes[op].flags[i] != '\0'; i++)
129a5ecbe62SWolfgang Denk switch (opcodes[op].flags[i]) {
130a5ecbe62SWolfgang Denk case 'i':
131a5ecbe62SWolfgang Denk (void) fprintf(fp, "%d ", r->code[pc + 1]);
132a5ecbe62SWolfgang Denk pc++;
133a5ecbe62SWolfgang Denk break;
134a5ecbe62SWolfgang Denk case 'o':
135a5ecbe62SWolfgang Denk (void) fprintf(fp, "%d ",
136a5ecbe62SWolfgang Denk pc + r->code[pc + 1] - i);
137a5ecbe62SWolfgang Denk pc++;
138a5ecbe62SWolfgang Denk break;
139a5ecbe62SWolfgang Denk case 'D':
140a5ecbe62SWolfgang Denk print_character_set(fp, r->data +
141a5ecbe62SWolfgang Denk r->code[pc + 1], r->code[pc + 2]);
142a5ecbe62SWolfgang Denk pc += 2;
143a5ecbe62SWolfgang Denk break;
144a5ecbe62SWolfgang Denk case 'd':
145a5ecbe62SWolfgang Denk (void) fputc('"', fp);
146a5ecbe62SWolfgang Denk for (j = 0; j < r->code[pc + 2]; j++) {
147a5ecbe62SWolfgang Denk ch = r->data[r->code[pc + 1] + j];
148a5ecbe62SWolfgang Denk if (isprint(ch)) {
149a5ecbe62SWolfgang Denk (void) fputc(ch, fp);
150a5ecbe62SWolfgang Denk } else {
151a5ecbe62SWolfgang Denk (void) fprintf(fp,
152a5ecbe62SWolfgang Denk "\\x%02x", ch);
153a5ecbe62SWolfgang Denk }
154a5ecbe62SWolfgang Denk }
155a5ecbe62SWolfgang Denk (void) fputc('"', fp);
156a5ecbe62SWolfgang Denk pc += 2;
157a5ecbe62SWolfgang Denk break;
158a5ecbe62SWolfgang Denk }
159a5ecbe62SWolfgang Denk
160a5ecbe62SWolfgang Denk (void) fputc('\n', fp);
161a5ecbe62SWolfgang Denk }
162a5ecbe62SWolfgang Denk }
163a5ecbe62SWolfgang Denk #endif /* SLRE_TEST */
164a5ecbe62SWolfgang Denk
165a5ecbe62SWolfgang Denk static void
set_jump_offset(struct slre * r,int pc,int offset)166a5ecbe62SWolfgang Denk set_jump_offset(struct slre *r, int pc, int offset)
167a5ecbe62SWolfgang Denk {
168a5ecbe62SWolfgang Denk assert(offset < r->code_size);
169a5ecbe62SWolfgang Denk
170a5ecbe62SWolfgang Denk if (r->code_size - offset > 0xff)
171a5ecbe62SWolfgang Denk r->err_str = "Jump offset is too big";
172a5ecbe62SWolfgang Denk else
173a5ecbe62SWolfgang Denk r->code[pc] = (unsigned char) (r->code_size - offset);
174a5ecbe62SWolfgang Denk }
175a5ecbe62SWolfgang Denk
176a5ecbe62SWolfgang Denk static void
emit(struct slre * r,int code)177a5ecbe62SWolfgang Denk emit(struct slre *r, int code)
178a5ecbe62SWolfgang Denk {
179a5ecbe62SWolfgang Denk if (r->code_size >= (int) (sizeof(r->code) / sizeof(r->code[0])))
180a5ecbe62SWolfgang Denk r->err_str = "RE is too long (code overflow)";
181a5ecbe62SWolfgang Denk else
182a5ecbe62SWolfgang Denk r->code[r->code_size++] = (unsigned char) code;
183a5ecbe62SWolfgang Denk }
184a5ecbe62SWolfgang Denk
185a5ecbe62SWolfgang Denk static void
store_char_in_data(struct slre * r,int ch)186a5ecbe62SWolfgang Denk store_char_in_data(struct slre *r, int ch)
187a5ecbe62SWolfgang Denk {
188a5ecbe62SWolfgang Denk if (r->data_size >= (int) sizeof(r->data))
189a5ecbe62SWolfgang Denk r->err_str = "RE is too long (data overflow)";
190a5ecbe62SWolfgang Denk else
191a5ecbe62SWolfgang Denk r->data[r->data_size++] = ch;
192a5ecbe62SWolfgang Denk }
193a5ecbe62SWolfgang Denk
194a5ecbe62SWolfgang Denk static void
exact(struct slre * r,const char ** re)195a5ecbe62SWolfgang Denk exact(struct slre *r, const char **re)
196a5ecbe62SWolfgang Denk {
197a5ecbe62SWolfgang Denk int old_data_size = r->data_size;
198a5ecbe62SWolfgang Denk
199a5ecbe62SWolfgang Denk while (**re != '\0' && (strchr(meta_chars, **re)) == NULL)
200a5ecbe62SWolfgang Denk store_char_in_data(r, *(*re)++);
201a5ecbe62SWolfgang Denk
202a5ecbe62SWolfgang Denk emit(r, EXACT);
203a5ecbe62SWolfgang Denk emit(r, old_data_size);
204a5ecbe62SWolfgang Denk emit(r, r->data_size - old_data_size);
205a5ecbe62SWolfgang Denk }
206a5ecbe62SWolfgang Denk
207a5ecbe62SWolfgang Denk static int
get_escape_char(const char ** re)208a5ecbe62SWolfgang Denk get_escape_char(const char **re)
209a5ecbe62SWolfgang Denk {
210a5ecbe62SWolfgang Denk int res;
211a5ecbe62SWolfgang Denk
212a5ecbe62SWolfgang Denk switch (*(*re)++) {
213a5ecbe62SWolfgang Denk case 'n':
214a5ecbe62SWolfgang Denk res = '\n';
215a5ecbe62SWolfgang Denk break;
216a5ecbe62SWolfgang Denk case 'r':
217a5ecbe62SWolfgang Denk res = '\r';
218a5ecbe62SWolfgang Denk break;
219a5ecbe62SWolfgang Denk case 't':
220a5ecbe62SWolfgang Denk res = '\t';
221a5ecbe62SWolfgang Denk break;
222a5ecbe62SWolfgang Denk case '0':
223a5ecbe62SWolfgang Denk res = 0;
224a5ecbe62SWolfgang Denk break;
225a5ecbe62SWolfgang Denk case 'S':
226a5ecbe62SWolfgang Denk res = NONSPACE << 8;
227a5ecbe62SWolfgang Denk break;
228a5ecbe62SWolfgang Denk case 's':
229a5ecbe62SWolfgang Denk res = SPACE << 8;
230a5ecbe62SWolfgang Denk break;
231a5ecbe62SWolfgang Denk case 'd':
232a5ecbe62SWolfgang Denk res = DIGIT << 8;
233a5ecbe62SWolfgang Denk break;
234a5ecbe62SWolfgang Denk default:
235a5ecbe62SWolfgang Denk res = (*re)[-1];
236a5ecbe62SWolfgang Denk break;
237a5ecbe62SWolfgang Denk }
238a5ecbe62SWolfgang Denk
239a5ecbe62SWolfgang Denk return res;
240a5ecbe62SWolfgang Denk }
241a5ecbe62SWolfgang Denk
242a5ecbe62SWolfgang Denk static void
anyof(struct slre * r,const char ** re)243a5ecbe62SWolfgang Denk anyof(struct slre *r, const char **re)
244a5ecbe62SWolfgang Denk {
245a5ecbe62SWolfgang Denk int esc, old_data_size = r->data_size, op = ANYOF;
246a5ecbe62SWolfgang Denk
247a5ecbe62SWolfgang Denk if (**re == '^') {
248a5ecbe62SWolfgang Denk op = ANYBUT;
249a5ecbe62SWolfgang Denk (*re)++;
250a5ecbe62SWolfgang Denk }
251a5ecbe62SWolfgang Denk
252a5ecbe62SWolfgang Denk while (**re != '\0')
253a5ecbe62SWolfgang Denk
254a5ecbe62SWolfgang Denk switch (*(*re)++) {
255a5ecbe62SWolfgang Denk case ']':
256a5ecbe62SWolfgang Denk emit(r, op);
257a5ecbe62SWolfgang Denk emit(r, old_data_size);
258a5ecbe62SWolfgang Denk emit(r, r->data_size - old_data_size);
259a5ecbe62SWolfgang Denk return;
260a5ecbe62SWolfgang Denk /* NOTREACHED */
261a5ecbe62SWolfgang Denk break;
262a5ecbe62SWolfgang Denk case '\\':
263a5ecbe62SWolfgang Denk esc = get_escape_char(re);
264a5ecbe62SWolfgang Denk if ((esc & 0xff) == 0) {
265a5ecbe62SWolfgang Denk store_char_in_data(r, 0);
266a5ecbe62SWolfgang Denk store_char_in_data(r, esc >> 8);
267a5ecbe62SWolfgang Denk } else {
268a5ecbe62SWolfgang Denk store_char_in_data(r, esc);
269a5ecbe62SWolfgang Denk }
270a5ecbe62SWolfgang Denk break;
271a5ecbe62SWolfgang Denk default:
272a5ecbe62SWolfgang Denk store_char_in_data(r, (*re)[-1]);
273a5ecbe62SWolfgang Denk break;
274a5ecbe62SWolfgang Denk }
275a5ecbe62SWolfgang Denk
276a5ecbe62SWolfgang Denk r->err_str = "No closing ']' bracket";
277a5ecbe62SWolfgang Denk }
278a5ecbe62SWolfgang Denk
279a5ecbe62SWolfgang Denk static void
relocate(struct slre * r,int begin,int shift)280a5ecbe62SWolfgang Denk relocate(struct slre *r, int begin, int shift)
281a5ecbe62SWolfgang Denk {
282a5ecbe62SWolfgang Denk emit(r, END);
283a5ecbe62SWolfgang Denk memmove(r->code + begin + shift, r->code + begin, r->code_size - begin);
284a5ecbe62SWolfgang Denk r->code_size += shift;
285a5ecbe62SWolfgang Denk }
286a5ecbe62SWolfgang Denk
287a5ecbe62SWolfgang Denk static void
quantifier(struct slre * r,int prev,int op)288a5ecbe62SWolfgang Denk quantifier(struct slre *r, int prev, int op)
289a5ecbe62SWolfgang Denk {
290a5ecbe62SWolfgang Denk if (r->code[prev] == EXACT && r->code[prev + 2] > 1) {
291a5ecbe62SWolfgang Denk r->code[prev + 2]--;
292a5ecbe62SWolfgang Denk emit(r, EXACT);
293a5ecbe62SWolfgang Denk emit(r, r->code[prev + 1] + r->code[prev + 2]);
294a5ecbe62SWolfgang Denk emit(r, 1);
295a5ecbe62SWolfgang Denk prev = r->code_size - 3;
296a5ecbe62SWolfgang Denk }
297a5ecbe62SWolfgang Denk relocate(r, prev, 2);
298a5ecbe62SWolfgang Denk r->code[prev] = op;
299a5ecbe62SWolfgang Denk set_jump_offset(r, prev + 1, prev);
300a5ecbe62SWolfgang Denk }
301a5ecbe62SWolfgang Denk
302a5ecbe62SWolfgang Denk static void
exact_one_char(struct slre * r,int ch)303a5ecbe62SWolfgang Denk exact_one_char(struct slre *r, int ch)
304a5ecbe62SWolfgang Denk {
305a5ecbe62SWolfgang Denk emit(r, EXACT);
306a5ecbe62SWolfgang Denk emit(r, r->data_size);
307a5ecbe62SWolfgang Denk emit(r, 1);
308a5ecbe62SWolfgang Denk store_char_in_data(r, ch);
309a5ecbe62SWolfgang Denk }
310a5ecbe62SWolfgang Denk
311a5ecbe62SWolfgang Denk static void
fixup_branch(struct slre * r,int fixup)312a5ecbe62SWolfgang Denk fixup_branch(struct slre *r, int fixup)
313a5ecbe62SWolfgang Denk {
314a5ecbe62SWolfgang Denk if (fixup > 0) {
315a5ecbe62SWolfgang Denk emit(r, END);
316a5ecbe62SWolfgang Denk set_jump_offset(r, fixup, fixup - 2);
317a5ecbe62SWolfgang Denk }
318a5ecbe62SWolfgang Denk }
319a5ecbe62SWolfgang Denk
320a5ecbe62SWolfgang Denk static void
compile(struct slre * r,const char ** re)321a5ecbe62SWolfgang Denk compile(struct slre *r, const char **re)
322a5ecbe62SWolfgang Denk {
323a5ecbe62SWolfgang Denk int op, esc, branch_start, last_op, fixup, cap_no, level;
324a5ecbe62SWolfgang Denk
325a5ecbe62SWolfgang Denk fixup = 0;
326a5ecbe62SWolfgang Denk level = r->num_caps;
327a5ecbe62SWolfgang Denk branch_start = last_op = r->code_size;
328a5ecbe62SWolfgang Denk
329a5ecbe62SWolfgang Denk for (;;)
330a5ecbe62SWolfgang Denk switch (*(*re)++) {
331a5ecbe62SWolfgang Denk case '\0':
332a5ecbe62SWolfgang Denk (*re)--;
333a5ecbe62SWolfgang Denk return;
334a5ecbe62SWolfgang Denk /* NOTREACHED */
335a5ecbe62SWolfgang Denk break;
336a5ecbe62SWolfgang Denk case '^':
337a5ecbe62SWolfgang Denk emit(r, BOL);
338a5ecbe62SWolfgang Denk break;
339a5ecbe62SWolfgang Denk case '$':
340a5ecbe62SWolfgang Denk emit(r, EOL);
341a5ecbe62SWolfgang Denk break;
342a5ecbe62SWolfgang Denk case '.':
343a5ecbe62SWolfgang Denk last_op = r->code_size;
344a5ecbe62SWolfgang Denk emit(r, ANY);
345a5ecbe62SWolfgang Denk break;
346a5ecbe62SWolfgang Denk case '[':
347a5ecbe62SWolfgang Denk last_op = r->code_size;
348a5ecbe62SWolfgang Denk anyof(r, re);
349a5ecbe62SWolfgang Denk break;
350a5ecbe62SWolfgang Denk case '\\':
351a5ecbe62SWolfgang Denk last_op = r->code_size;
352a5ecbe62SWolfgang Denk esc = get_escape_char(re);
353a5ecbe62SWolfgang Denk if (esc & 0xff00)
354a5ecbe62SWolfgang Denk emit(r, esc >> 8);
355a5ecbe62SWolfgang Denk else
356a5ecbe62SWolfgang Denk exact_one_char(r, esc);
357a5ecbe62SWolfgang Denk break;
358a5ecbe62SWolfgang Denk case '(':
359a5ecbe62SWolfgang Denk last_op = r->code_size;
360a5ecbe62SWolfgang Denk cap_no = ++r->num_caps;
361a5ecbe62SWolfgang Denk emit(r, OPEN);
362a5ecbe62SWolfgang Denk emit(r, cap_no);
363a5ecbe62SWolfgang Denk
364a5ecbe62SWolfgang Denk compile(r, re);
365a5ecbe62SWolfgang Denk if (*(*re)++ != ')') {
366a5ecbe62SWolfgang Denk r->err_str = "No closing bracket";
367a5ecbe62SWolfgang Denk return;
368a5ecbe62SWolfgang Denk }
369a5ecbe62SWolfgang Denk
370a5ecbe62SWolfgang Denk emit(r, CLOSE);
371a5ecbe62SWolfgang Denk emit(r, cap_no);
372a5ecbe62SWolfgang Denk break;
373a5ecbe62SWolfgang Denk case ')':
374a5ecbe62SWolfgang Denk (*re)--;
375a5ecbe62SWolfgang Denk fixup_branch(r, fixup);
376a5ecbe62SWolfgang Denk if (level == 0) {
377a5ecbe62SWolfgang Denk r->err_str = "Unbalanced brackets";
378a5ecbe62SWolfgang Denk return;
379a5ecbe62SWolfgang Denk }
380a5ecbe62SWolfgang Denk return;
381a5ecbe62SWolfgang Denk /* NOTREACHED */
382a5ecbe62SWolfgang Denk break;
383a5ecbe62SWolfgang Denk case '+':
384a5ecbe62SWolfgang Denk case '*':
385a5ecbe62SWolfgang Denk op = (*re)[-1] == '*' ? STAR : PLUS;
386a5ecbe62SWolfgang Denk if (**re == '?') {
387a5ecbe62SWolfgang Denk (*re)++;
388a5ecbe62SWolfgang Denk op = op == STAR ? STARQ : PLUSQ;
389a5ecbe62SWolfgang Denk }
390a5ecbe62SWolfgang Denk quantifier(r, last_op, op);
391a5ecbe62SWolfgang Denk break;
392a5ecbe62SWolfgang Denk case '?':
393a5ecbe62SWolfgang Denk quantifier(r, last_op, QUEST);
394a5ecbe62SWolfgang Denk break;
395a5ecbe62SWolfgang Denk case '|':
396a5ecbe62SWolfgang Denk fixup_branch(r, fixup);
397a5ecbe62SWolfgang Denk relocate(r, branch_start, 3);
398a5ecbe62SWolfgang Denk r->code[branch_start] = BRANCH;
399a5ecbe62SWolfgang Denk set_jump_offset(r, branch_start + 1, branch_start);
400a5ecbe62SWolfgang Denk fixup = branch_start + 2;
401a5ecbe62SWolfgang Denk r->code[fixup] = 0xff;
402a5ecbe62SWolfgang Denk break;
403a5ecbe62SWolfgang Denk default:
404a5ecbe62SWolfgang Denk (*re)--;
405a5ecbe62SWolfgang Denk last_op = r->code_size;
406a5ecbe62SWolfgang Denk exact(r, re);
407a5ecbe62SWolfgang Denk break;
408a5ecbe62SWolfgang Denk }
409a5ecbe62SWolfgang Denk }
410a5ecbe62SWolfgang Denk
411a5ecbe62SWolfgang Denk int
slre_compile(struct slre * r,const char * re)412a5ecbe62SWolfgang Denk slre_compile(struct slre *r, const char *re)
413a5ecbe62SWolfgang Denk {
414a5ecbe62SWolfgang Denk r->err_str = NULL;
415a5ecbe62SWolfgang Denk r->code_size = r->data_size = r->num_caps = r->anchored = 0;
416a5ecbe62SWolfgang Denk
417a5ecbe62SWolfgang Denk if (*re == '^')
418a5ecbe62SWolfgang Denk r->anchored++;
419a5ecbe62SWolfgang Denk
420a5ecbe62SWolfgang Denk emit(r, OPEN); /* This will capture what matches full RE */
421a5ecbe62SWolfgang Denk emit(r, 0);
422a5ecbe62SWolfgang Denk
423a5ecbe62SWolfgang Denk while (*re != '\0')
424a5ecbe62SWolfgang Denk compile(r, &re);
425a5ecbe62SWolfgang Denk
426a5ecbe62SWolfgang Denk if (r->code[2] == BRANCH)
427a5ecbe62SWolfgang Denk fixup_branch(r, 4);
428a5ecbe62SWolfgang Denk
429a5ecbe62SWolfgang Denk emit(r, CLOSE);
430a5ecbe62SWolfgang Denk emit(r, 0);
431a5ecbe62SWolfgang Denk emit(r, END);
432a5ecbe62SWolfgang Denk
433a5ecbe62SWolfgang Denk return (r->err_str == NULL ? 1 : 0);
434a5ecbe62SWolfgang Denk }
435a5ecbe62SWolfgang Denk
436a5ecbe62SWolfgang Denk static int match(const struct slre *, int,
437a5ecbe62SWolfgang Denk const char *, int, int *, struct cap *);
438a5ecbe62SWolfgang Denk
439a5ecbe62SWolfgang Denk static void
loop_greedy(const struct slre * r,int pc,const char * s,int len,int * ofs)440a5ecbe62SWolfgang Denk loop_greedy(const struct slre *r, int pc, const char *s, int len, int *ofs)
441a5ecbe62SWolfgang Denk {
442a5ecbe62SWolfgang Denk int saved_offset, matched_offset;
443a5ecbe62SWolfgang Denk
444*b8865e6bSxypron.glpk@gmx.de matched_offset = *ofs;
445a5ecbe62SWolfgang Denk
446a5ecbe62SWolfgang Denk while (match(r, pc + 2, s, len, ofs, NULL)) {
447a5ecbe62SWolfgang Denk saved_offset = *ofs;
448a5ecbe62SWolfgang Denk if (match(r, pc + r->code[pc + 1], s, len, ofs, NULL))
449a5ecbe62SWolfgang Denk matched_offset = saved_offset;
450a5ecbe62SWolfgang Denk *ofs = saved_offset;
451a5ecbe62SWolfgang Denk }
452a5ecbe62SWolfgang Denk
453a5ecbe62SWolfgang Denk *ofs = matched_offset;
454a5ecbe62SWolfgang Denk }
455a5ecbe62SWolfgang Denk
456a5ecbe62SWolfgang Denk static void
loop_non_greedy(const struct slre * r,int pc,const char * s,int len,int * ofs)457a5ecbe62SWolfgang Denk loop_non_greedy(const struct slre *r, int pc, const char *s, int len, int *ofs)
458a5ecbe62SWolfgang Denk {
459a5ecbe62SWolfgang Denk int saved_offset = *ofs;
460a5ecbe62SWolfgang Denk
461a5ecbe62SWolfgang Denk while (match(r, pc + 2, s, len, ofs, NULL)) {
462a5ecbe62SWolfgang Denk saved_offset = *ofs;
463a5ecbe62SWolfgang Denk if (match(r, pc + r->code[pc + 1], s, len, ofs, NULL))
464a5ecbe62SWolfgang Denk break;
465a5ecbe62SWolfgang Denk }
466a5ecbe62SWolfgang Denk
467a5ecbe62SWolfgang Denk *ofs = saved_offset;
468a5ecbe62SWolfgang Denk }
469a5ecbe62SWolfgang Denk
470a5ecbe62SWolfgang Denk static int
is_any_of(const unsigned char * p,int len,const char * s,int * ofs)471a5ecbe62SWolfgang Denk is_any_of(const unsigned char *p, int len, const char *s, int *ofs)
472a5ecbe62SWolfgang Denk {
473a5ecbe62SWolfgang Denk int i, ch;
474a5ecbe62SWolfgang Denk
475a5ecbe62SWolfgang Denk ch = s[*ofs];
476a5ecbe62SWolfgang Denk
477a5ecbe62SWolfgang Denk for (i = 0; i < len; i++)
478a5ecbe62SWolfgang Denk if (p[i] == ch) {
479a5ecbe62SWolfgang Denk (*ofs)++;
480a5ecbe62SWolfgang Denk return 1;
481a5ecbe62SWolfgang Denk }
482a5ecbe62SWolfgang Denk
483a5ecbe62SWolfgang Denk return 0;
484a5ecbe62SWolfgang Denk }
485a5ecbe62SWolfgang Denk
486a5ecbe62SWolfgang Denk static int
is_any_but(const unsigned char * p,int len,const char * s,int * ofs)487a5ecbe62SWolfgang Denk is_any_but(const unsigned char *p, int len, const char *s, int *ofs)
488a5ecbe62SWolfgang Denk {
489a5ecbe62SWolfgang Denk int i, ch;
490a5ecbe62SWolfgang Denk
491a5ecbe62SWolfgang Denk ch = s[*ofs];
492a5ecbe62SWolfgang Denk
493a5ecbe62SWolfgang Denk for (i = 0; i < len; i++) {
494a5ecbe62SWolfgang Denk if (p[i] == ch)
495a5ecbe62SWolfgang Denk return 0;
496a5ecbe62SWolfgang Denk }
497a5ecbe62SWolfgang Denk
498a5ecbe62SWolfgang Denk (*ofs)++;
499a5ecbe62SWolfgang Denk return 1;
500a5ecbe62SWolfgang Denk }
501a5ecbe62SWolfgang Denk
502a5ecbe62SWolfgang Denk static int
match(const struct slre * r,int pc,const char * s,int len,int * ofs,struct cap * caps)503a5ecbe62SWolfgang Denk match(const struct slre *r, int pc, const char *s, int len,
504a5ecbe62SWolfgang Denk int *ofs, struct cap *caps)
505a5ecbe62SWolfgang Denk {
506a5ecbe62SWolfgang Denk int n, saved_offset, res = 1;
507a5ecbe62SWolfgang Denk
508a5ecbe62SWolfgang Denk while (res && r->code[pc] != END) {
509a5ecbe62SWolfgang Denk
510a5ecbe62SWolfgang Denk assert(pc < r->code_size);
511a5ecbe62SWolfgang Denk assert(pc < (int) (sizeof(r->code) / sizeof(r->code[0])));
512a5ecbe62SWolfgang Denk
513a5ecbe62SWolfgang Denk switch (r->code[pc]) {
514a5ecbe62SWolfgang Denk case BRANCH:
515a5ecbe62SWolfgang Denk saved_offset = *ofs;
516a5ecbe62SWolfgang Denk res = match(r, pc + 3, s, len, ofs, caps);
517a5ecbe62SWolfgang Denk if (res == 0) {
518a5ecbe62SWolfgang Denk *ofs = saved_offset;
519a5ecbe62SWolfgang Denk res = match(r, pc + r->code[pc + 1],
520a5ecbe62SWolfgang Denk s, len, ofs, caps);
521a5ecbe62SWolfgang Denk }
522a5ecbe62SWolfgang Denk pc += r->code[pc + 2];
523a5ecbe62SWolfgang Denk break;
524a5ecbe62SWolfgang Denk case EXACT:
525a5ecbe62SWolfgang Denk res = 0;
526a5ecbe62SWolfgang Denk n = r->code[pc + 2]; /* String length */
527a5ecbe62SWolfgang Denk if (n <= len - *ofs && !memcmp(s + *ofs, r->data +
528a5ecbe62SWolfgang Denk r->code[pc + 1], n)) {
529a5ecbe62SWolfgang Denk (*ofs) += n;
530a5ecbe62SWolfgang Denk res = 1;
531a5ecbe62SWolfgang Denk }
532a5ecbe62SWolfgang Denk pc += 3;
533a5ecbe62SWolfgang Denk break;
534a5ecbe62SWolfgang Denk case QUEST:
535a5ecbe62SWolfgang Denk res = 1;
536a5ecbe62SWolfgang Denk saved_offset = *ofs;
537a5ecbe62SWolfgang Denk if (!match(r, pc + 2, s, len, ofs, caps))
538a5ecbe62SWolfgang Denk *ofs = saved_offset;
539a5ecbe62SWolfgang Denk pc += r->code[pc + 1];
540a5ecbe62SWolfgang Denk break;
541a5ecbe62SWolfgang Denk case STAR:
542a5ecbe62SWolfgang Denk res = 1;
543a5ecbe62SWolfgang Denk loop_greedy(r, pc, s, len, ofs);
544a5ecbe62SWolfgang Denk pc += r->code[pc + 1];
545a5ecbe62SWolfgang Denk break;
546a5ecbe62SWolfgang Denk case STARQ:
547a5ecbe62SWolfgang Denk res = 1;
548a5ecbe62SWolfgang Denk loop_non_greedy(r, pc, s, len, ofs);
549a5ecbe62SWolfgang Denk pc += r->code[pc + 1];
550a5ecbe62SWolfgang Denk break;
551a5ecbe62SWolfgang Denk case PLUS:
552a5ecbe62SWolfgang Denk res = match(r, pc + 2, s, len, ofs, caps);
553a5ecbe62SWolfgang Denk if (res == 0)
554a5ecbe62SWolfgang Denk break;
555a5ecbe62SWolfgang Denk
556a5ecbe62SWolfgang Denk loop_greedy(r, pc, s, len, ofs);
557a5ecbe62SWolfgang Denk pc += r->code[pc + 1];
558a5ecbe62SWolfgang Denk break;
559a5ecbe62SWolfgang Denk case PLUSQ:
560a5ecbe62SWolfgang Denk res = match(r, pc + 2, s, len, ofs, caps);
561a5ecbe62SWolfgang Denk if (res == 0)
562a5ecbe62SWolfgang Denk break;
563a5ecbe62SWolfgang Denk
564a5ecbe62SWolfgang Denk loop_non_greedy(r, pc, s, len, ofs);
565a5ecbe62SWolfgang Denk pc += r->code[pc + 1];
566a5ecbe62SWolfgang Denk break;
567a5ecbe62SWolfgang Denk case SPACE:
568a5ecbe62SWolfgang Denk res = 0;
569a5ecbe62SWolfgang Denk if (*ofs < len && isspace(((unsigned char *)s)[*ofs])) {
570a5ecbe62SWolfgang Denk (*ofs)++;
571a5ecbe62SWolfgang Denk res = 1;
572a5ecbe62SWolfgang Denk }
573a5ecbe62SWolfgang Denk pc++;
574a5ecbe62SWolfgang Denk break;
575a5ecbe62SWolfgang Denk case NONSPACE:
576a5ecbe62SWolfgang Denk res = 0;
577a5ecbe62SWolfgang Denk if (*ofs < len &&
578a5ecbe62SWolfgang Denk !isspace(((unsigned char *)s)[*ofs])) {
579a5ecbe62SWolfgang Denk (*ofs)++;
580a5ecbe62SWolfgang Denk res = 1;
581a5ecbe62SWolfgang Denk }
582a5ecbe62SWolfgang Denk pc++;
583a5ecbe62SWolfgang Denk break;
584a5ecbe62SWolfgang Denk case DIGIT:
585a5ecbe62SWolfgang Denk res = 0;
586a5ecbe62SWolfgang Denk if (*ofs < len && isdigit(((unsigned char *)s)[*ofs])) {
587a5ecbe62SWolfgang Denk (*ofs)++;
588a5ecbe62SWolfgang Denk res = 1;
589a5ecbe62SWolfgang Denk }
590a5ecbe62SWolfgang Denk pc++;
591a5ecbe62SWolfgang Denk break;
592a5ecbe62SWolfgang Denk case ANY:
593a5ecbe62SWolfgang Denk res = 0;
594a5ecbe62SWolfgang Denk if (*ofs < len) {
595a5ecbe62SWolfgang Denk (*ofs)++;
596a5ecbe62SWolfgang Denk res = 1;
597a5ecbe62SWolfgang Denk }
598a5ecbe62SWolfgang Denk pc++;
599a5ecbe62SWolfgang Denk break;
600a5ecbe62SWolfgang Denk case ANYOF:
601a5ecbe62SWolfgang Denk res = 0;
602a5ecbe62SWolfgang Denk if (*ofs < len)
603a5ecbe62SWolfgang Denk res = is_any_of(r->data + r->code[pc + 1],
604a5ecbe62SWolfgang Denk r->code[pc + 2], s, ofs);
605a5ecbe62SWolfgang Denk pc += 3;
606a5ecbe62SWolfgang Denk break;
607a5ecbe62SWolfgang Denk case ANYBUT:
608a5ecbe62SWolfgang Denk res = 0;
609a5ecbe62SWolfgang Denk if (*ofs < len)
610a5ecbe62SWolfgang Denk res = is_any_but(r->data + r->code[pc + 1],
611a5ecbe62SWolfgang Denk r->code[pc + 2], s, ofs);
612a5ecbe62SWolfgang Denk pc += 3;
613a5ecbe62SWolfgang Denk break;
614a5ecbe62SWolfgang Denk case BOL:
615a5ecbe62SWolfgang Denk res = *ofs == 0 ? 1 : 0;
616a5ecbe62SWolfgang Denk pc++;
617a5ecbe62SWolfgang Denk break;
618a5ecbe62SWolfgang Denk case EOL:
619a5ecbe62SWolfgang Denk res = *ofs == len ? 1 : 0;
620a5ecbe62SWolfgang Denk pc++;
621a5ecbe62SWolfgang Denk break;
622a5ecbe62SWolfgang Denk case OPEN:
623a5ecbe62SWolfgang Denk if (caps != NULL)
624a5ecbe62SWolfgang Denk caps[r->code[pc + 1]].ptr = s + *ofs;
625a5ecbe62SWolfgang Denk pc += 2;
626a5ecbe62SWolfgang Denk break;
627a5ecbe62SWolfgang Denk case CLOSE:
628a5ecbe62SWolfgang Denk if (caps != NULL)
629a5ecbe62SWolfgang Denk caps[r->code[pc + 1]].len = (s + *ofs) -
630a5ecbe62SWolfgang Denk caps[r->code[pc + 1]].ptr;
631a5ecbe62SWolfgang Denk pc += 2;
632a5ecbe62SWolfgang Denk break;
633a5ecbe62SWolfgang Denk case END:
634a5ecbe62SWolfgang Denk pc++;
635a5ecbe62SWolfgang Denk break;
636a5ecbe62SWolfgang Denk default:
637a5ecbe62SWolfgang Denk printf("unknown cmd (%d) at %d\n", r->code[pc], pc);
638a5ecbe62SWolfgang Denk assert(0);
639a5ecbe62SWolfgang Denk break;
640a5ecbe62SWolfgang Denk }
641a5ecbe62SWolfgang Denk }
642a5ecbe62SWolfgang Denk
643a5ecbe62SWolfgang Denk return res;
644a5ecbe62SWolfgang Denk }
645a5ecbe62SWolfgang Denk
646a5ecbe62SWolfgang Denk int
slre_match(const struct slre * r,const char * buf,int len,struct cap * caps)647a5ecbe62SWolfgang Denk slre_match(const struct slre *r, const char *buf, int len,
648a5ecbe62SWolfgang Denk struct cap *caps)
649a5ecbe62SWolfgang Denk {
650a5ecbe62SWolfgang Denk int i, ofs = 0, res = 0;
651a5ecbe62SWolfgang Denk
652a5ecbe62SWolfgang Denk if (r->anchored) {
653a5ecbe62SWolfgang Denk res = match(r, 0, buf, len, &ofs, caps);
654a5ecbe62SWolfgang Denk } else {
655a5ecbe62SWolfgang Denk for (i = 0; i < len && res == 0; i++) {
656a5ecbe62SWolfgang Denk ofs = i;
657a5ecbe62SWolfgang Denk res = match(r, 0, buf, len, &ofs, caps);
658a5ecbe62SWolfgang Denk }
659a5ecbe62SWolfgang Denk }
660a5ecbe62SWolfgang Denk
661a5ecbe62SWolfgang Denk return res;
662a5ecbe62SWolfgang Denk }
663a5ecbe62SWolfgang Denk
664a5ecbe62SWolfgang Denk #ifdef SLRE_TEST
665a5ecbe62SWolfgang Denk #define N_CAPS 5
666a5ecbe62SWolfgang Denk
main(int argc,char * argv[])667a5ecbe62SWolfgang Denk int main(int argc, char *argv[])
668a5ecbe62SWolfgang Denk {
669a5ecbe62SWolfgang Denk struct slre slre;
670a5ecbe62SWolfgang Denk struct cap caps[N_CAPS];
671a5ecbe62SWolfgang Denk unsigned char data[1 * 1024 * 1024];
672a5ecbe62SWolfgang Denk FILE *fp;
673a5ecbe62SWolfgang Denk int i, res, len;
674a5ecbe62SWolfgang Denk
675a5ecbe62SWolfgang Denk if (argc < 2) {
676a5ecbe62SWolfgang Denk fprintf(stderr, "Usage: %s 'slre' <file>\n", argv[0]);
677a5ecbe62SWolfgang Denk return 1;
678a5ecbe62SWolfgang Denk }
679a5ecbe62SWolfgang Denk
680a5ecbe62SWolfgang Denk fp = fopen(argv[2], "rb");
681a5ecbe62SWolfgang Denk if (fp == NULL) {
682a5ecbe62SWolfgang Denk fprintf(stderr, "Error: cannot open %s:%s\n",
683a5ecbe62SWolfgang Denk argv[2], strerror(errno));
684a5ecbe62SWolfgang Denk return 1;
685a5ecbe62SWolfgang Denk }
686a5ecbe62SWolfgang Denk
687a5ecbe62SWolfgang Denk if (!slre_compile(&slre, argv[1])) {
688a5ecbe62SWolfgang Denk fprintf(stderr, "Error compiling slre: %s\n", slre.err_str);
689a5ecbe62SWolfgang Denk return 1;
690a5ecbe62SWolfgang Denk }
691a5ecbe62SWolfgang Denk
692a5ecbe62SWolfgang Denk slre_dump(&slre, stderr);
693a5ecbe62SWolfgang Denk
694a5ecbe62SWolfgang Denk while (fgets(data, sizeof(data), fp) != NULL) {
695a5ecbe62SWolfgang Denk len = strlen(data);
696a5ecbe62SWolfgang Denk
697a5ecbe62SWolfgang Denk if ((len > 0) && (data[len-1] == '\n')) {
698a5ecbe62SWolfgang Denk data[len-1] = '\0';
699a5ecbe62SWolfgang Denk --len;
700a5ecbe62SWolfgang Denk }
701a5ecbe62SWolfgang Denk
702a5ecbe62SWolfgang Denk printf("Data = \"%s\"\n", data);
703a5ecbe62SWolfgang Denk
704a5ecbe62SWolfgang Denk (void) memset(caps, 0, sizeof(caps));
705a5ecbe62SWolfgang Denk
706a5ecbe62SWolfgang Denk res = slre_match(&slre, data, len, caps);
707a5ecbe62SWolfgang Denk printf("Result [%d]: %d\n", i, res);
708a5ecbe62SWolfgang Denk
709a5ecbe62SWolfgang Denk for (i = 0; i < N_CAPS; i++) {
710a5ecbe62SWolfgang Denk if (caps[i].len > 0) {
711a5ecbe62SWolfgang Denk printf("Substring %d: len=%d [%.*s]\n", i,
712a5ecbe62SWolfgang Denk caps[i].len,
713a5ecbe62SWolfgang Denk caps[i].len, caps[i].ptr);
714a5ecbe62SWolfgang Denk }
715a5ecbe62SWolfgang Denk }
716a5ecbe62SWolfgang Denk printf("----------------------------------------------------\n");
717a5ecbe62SWolfgang Denk }
718a5ecbe62SWolfgang Denk (void) fclose(fp);
719a5ecbe62SWolfgang Denk
720a5ecbe62SWolfgang Denk return 0;
721a5ecbe62SWolfgang Denk }
722a5ecbe62SWolfgang Denk #endif /* SLRE_TEST */
723