?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
regex: \< and \> word boundaries
[neatlibc.git] / regex.c
bloba4ccb35ce4f1dca804d5afd536eb68107245ee4f
1 #include <ctype.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
5 #include "regex.h"
6
7 #define NGRPS 32
8 #define NREPS 64
9
10 #define MAX(a, b) ((a) < (b) ? (b) : (a))
11 #define LEN(a) (sizeof(a) / sizeof((a)[0]))
12
13 /* regular expressions atoms */
14 #define RA_CHR '\0' /* character literal */
15 #define RA_BEG '^' /* string start */
16 #define RA_END '$' /* string end */
17 #define RA_ANY '.' /* any character */
18 #define RA_BRK '[' /* bracket expression */
19 #define RA_WBEG '<' /* word start */
20 #define RA_WEND '>' /* word end */
21
22 /* regular expression node types */
23 #define RN_ATOM '\0' /* regular expression */
24 #define RN_CAT 'c' /* concatenation */
25 #define RN_ALT '|' /* alternate expressions */
26 #define RN_GRP '(' /* pattern group */
27
28 /* regular expression program instructions */
29 #define RI_ATOM '\0' /* regular expression */
30 #define RI_FORK 'f' /* fork the execution */
31 #define RI_JUMP 'j' /* jump to the given instruction */
32 #define RI_MARK 'm' /* mark the current position */
33 #define RI_MATCH 'q' /* the pattern is matched */
34
35 /* regular expression atom */
36 struct ratom {
37 int ra; /* atom type (RA_*) */
38 char *s; /* atom argument */
39 };
40
41 /* regular expression instruction */
42 struct rinst {
43 int ri; /* instruction type (RI_*) */
44 struct ratom ra; /* regular expression atom (RI_ATOM) */
45 int a1, a2; /* destination of RE_FORK and RI_JUMP */
46 int mark; /* mark (RI_MARK) */
47 };
48
49 /* regular expression program */
50 struct regex {
51 struct rinst *p; /* the program */
52 int n; /* number of instructions */
53 int grpcnt; /* number of groups */
54 int flg; /* regcomp() flags */
55 };
56
57 /* regular expression matching state */
58 struct rstate {
59 int mark[NGRPS * 2]; /* marks for RI_MARK */
60 int pc; /* program counter */
61 char *s; /* the current position in the string */
62 char *o; /* the beginning of the string */
63 int flg; /* flags passed to regcomp() and regexec() */
64 };
65
66 /* regular expression tree; used for parsing */
67 struct rnode {
68 int rn; /* node type (RN_*) */
69 struct ratom ra; /* regular expression atom (RN_ATOM) */
70 int mincnt, maxcnt; /* number of repetitions */
71 struct rnode *c1, *c2; /* children */
72 };
73
74 static struct rnode *rnode_make(int rn, struct rnode *c1, struct rnode *c2)
75 {
76 struct rnode *rnode = malloc(sizeof(*rnode));
77 memset(rnode, 0, sizeof(*rnode));
78 rnode->rn = rn;
79 rnode->c1 = c1;
80 rnode->c2 = c2;
81 rnode->mincnt = 1;
82 rnode->maxcnt = 1;
83 return rnode;
84 }
85
86 static void rnode_free(struct rnode *rnode)
87 {
88 if (rnode->c1)
89 rnode_free(rnode->c1);
90 if (rnode->c2)
91 rnode_free(rnode->c2);
92 free(rnode->ra.s);
93 free(rnode);
94 }
95
96 static int uc_len(char *s)
97 {
98 int c = (unsigned char) s[0];
99 if (c > 0 && c <= 0x7f)
100 return 1;
101 if (c >= 0xfc)
102 return 6;
103 if (c >= 0xf8)
104 return 5;
105 if (c >= 0xf0)
106 return 4;
107 if (c >= 0xe0)
108 return 3;
109 if (c >= 0xc0)
110 return 2;
111 return c != 0;
112 }
113
114 static int uc_dec(char *s)
115 {
116 int result;
117 int l = uc_len(s);
118 if (l <= 1)
119 return (unsigned char) *s;
120 result = (0x3f >> --l) & (unsigned char) *s++;
121 while (l--)
122 result = (result << 6) | ((unsigned char) *s++ & 0x3f);
123 return result;
124 }
125
126 static void ratom_copy(struct ratom *dst, struct ratom *src)
127 {
128 dst->ra = src->ra;
129 dst->s = NULL;
130 if (src->s) {
131 int len = strlen(src->s);
132 dst->s = malloc(len + 1);
133 memcpy(dst->s, src->s, len + 1);
134 }
135 }
136
137 static void ratom_readbrk(struct ratom *ra, char **pat)
138 {
139 char *beg = ++*pat;
140 int len;
141 ra->ra = RA_BRK;
142 if (**pat == '^') /* exclusion mark */
143 (*pat)++;
144 if (**pat) /* handling []a] */
145 (*pat)++;
146 while (**pat && *(*pat)++ != ']')
147 ;
148 len = *pat - beg - 1;
149 if (len >= 0) {
150 ra->s = malloc(len + 1);
151 memcpy(ra->s, beg, len);
152 ra->s[len] = '\0';
153 }
154 }
155
156 static void ratom_read(struct ratom *ra, char **pat)
157 {
158 int len;
159 switch ((unsigned char) **pat) {
160 case '.':
161 ra->ra = RA_ANY;
162 (*pat)++;
163 break;
164 case '^':
165 ra->ra = RA_BEG;
166 (*pat)++;
167 break;
168 case '$':
169 ra->ra = RA_END;
170 (*pat)++;
171 break;
172 case '[':
173 ratom_readbrk(ra, pat);
174 break;
175 case '\\':
176 if ((*pat)[1] == '<' || (*pat)[1] == '>') {
177 ra->ra = (*pat)[1] == '<' ? RA_WBEG : RA_WEND;
178 *pat += 2;
179 break;
180 }
181 (*pat)++;
182 default:
183 ra->ra = RA_CHR;
184 len = uc_len(*pat);
185 ra->s = malloc(8);
186 memcpy(ra->s, *pat, len);
187 ra->s[len] = '\0';
188 *pat += len;
189 }
190 }
191
192 static int isword(int c)
193 {
194 return isalpha(c) || isdigit(c) || c == '_';
195 }
196
197 static char *charclasses[][2] = {
198 {":alnum:", "a-zA-Z0-9"},
199 {":alpha:", "a-zA-Z"},
200 {":blank:", " \t"},
201 {":digit:", "0-9"},
202 {":lower:", "a-z"},
203 {":print:", "\x20-\x7e"},
204 {":punct:", "][!\"#$%&'()*+,./:;<=>?@\\^_`{|}~-"},
205 {":space:", " \t\r\n\v\f"},
206 {":upper:", "A-Z"},
207 {":word:", "a-zA-Z0-9_"},
208 {":xdigit:", "a-fA-F0-9"},
209 };
210
211 static int ratom_match(struct ratom *ra, struct rstate *rs)
212 {
213 typedef unsigned char uc_t;
214 int i;
215 if (ra->ra == RA_CHR) {
216 int c1 = uc_dec(ra->s);
217 int c2 = uc_dec(rs->s);
218 if (rs->flg & REG_ICASE && c1 < 128 && isupper(c1))
219 c1 = tolower(c1);
220 if (rs->flg & REG_ICASE && c2 < 128 && isupper(c2))
221 c2 = tolower(c2);
222 if (c1 != c2)
223 return 1;
224 rs->s += uc_len(ra->s);
225 return 0;
226 }
227 if (ra->ra == RA_BRK) {
228 int not = ra->s[0] == '^';
229 char *p = not ? ra->s + 1 : ra->s;
230 int c, clen;
231 int beg, end;
232 if (!rs->s[0])
233 return 1;
234 if (p[0] == ':')
235 for (i = 0; i < LEN(charclasses); i++)
236 if (!strcmp(charclasses[i][0], p))
237 p = charclasses[i][1];
238 c = uc_dec(rs->s);
239 rs->s += uc_len(rs->s);
240 if (rs->flg & REG_ICASE && c < 128 && isupper(c))
241 c = tolower(c);
242 while (*p) {
243 beg = uc_dec(p);
244 p += uc_len(p);
245 end = beg;
246 if (p[0] == '-' && p[1]) {
247 p++;
248 end = uc_dec(p);
249 p += uc_len(p);
250 }
251 if (rs->flg & REG_ICASE && beg < 128 && isupper(beg))
252 beg = tolower(beg);
253 if (rs->flg & REG_ICASE && end < 128 && isupper(end))
254 end = tolower(end);
255 if (c >= beg && c <= end)
256 return not;
257 }
258 return !not;
259 }
260 if (ra->ra == RA_ANY) {
261 if (!rs->s[0])
262 return 1;
263 rs->s += uc_len(rs->s);
264 return 0;
265 }
266 if (ra->ra == RA_BEG && !(rs->flg & REG_NOTBOL))
267 return rs->s != rs->o;
268 if (ra->ra == RA_END && !(rs->flg & REG_NOTEOL))
269 return rs->s[0] != '\0';
270 if (ra->ra == RA_WBEG)
271 return !((rs->s == rs->o || !isword((uc_t) rs->s[-1])) &&
272 isword((uc_t) rs->s[0]));
273 if (ra->ra == RA_WEND)
274 return !(rs->s != rs->o && isword((uc_t) rs->s[-1]) &&
275 (!rs->s[0] || !isword((uc_t) rs->s[0])));
276 return 1;
277 }
278
279 static struct rnode *rnode_parse(char **pat);
280
281 static struct rnode *rnode_grp(char **pat)
282 {
283 struct rnode *rnode;
284 if ((*pat)[0] != '(')
285 return NULL;
286 *pat += 1;
287 rnode = rnode_parse(pat);
288 if ((*pat)[0] != ')') {
289 rnode_free(rnode);
290 return NULL;
291 }
292 *pat += 1;
293 return rnode_make(RN_GRP, rnode, NULL);
294 }
295
296 static struct rnode *rnode_atom(char **pat)
297 {
298 struct rnode *rnode;
299 if (!**pat)
300 return NULL;
301 if ((*pat)[0] == '|' || (*pat)[0] == ')')
302 return NULL;
303 if ((*pat)[0] == '(') {
304 rnode = rnode_grp(pat);
305 } else {
306 rnode = rnode_make(RN_ATOM, NULL, NULL);
307 ratom_read(&rnode->ra, pat);
308 }
309 if ((*pat)[0] == '*' || (*pat)[0] == '?') {
310 rnode->mincnt = 0;
311 rnode->maxcnt = (*pat)[0] == '*' ? -1 : 1;
312 (*pat)++;
313 }
314 if ((*pat)[0] == '+') {
315 rnode->mincnt = 1;
316 rnode->maxcnt = -1;
317 *pat += 1;
318 }
319 if ((*pat)[0] == '{') {
320 rnode->mincnt = 0;
321 rnode->maxcnt = 0;
322 *pat += 1;
323 while (isdigit((unsigned char) **pat))
324 rnode->mincnt = rnode->mincnt * 10 + *(*pat)++ - '0';
325 if (**pat == ',') {
326 (*pat)++;
327 if ((*pat)[0] == '}')
328 rnode->maxcnt = -1;
329 while (isdigit((unsigned char) **pat))
330 rnode->maxcnt = rnode->maxcnt * 10 + *(*pat)++ - '0';
331 } else {
332 rnode->maxcnt = rnode->mincnt;
333 }
334 *pat += 1;
335 if (rnode->mincnt > NREPS || rnode->maxcnt > NREPS) {
336 rnode_free(rnode);
337 return NULL;
338 }
339 }
340 return rnode;
341 }
342
343 static struct rnode *rnode_seq(char **pat)
344 {
345 struct rnode *c1 = rnode_atom(pat);
346 struct rnode *c2;
347 if (!c1)
348 return NULL;
349 c2 = rnode_seq(pat);
350 return c2 ? rnode_make(RN_CAT, c1, c2) : c1;
351 }
352
353 static struct rnode *rnode_parse(char **pat)
354 {
355 struct rnode *c1 = rnode_seq(pat);
356 struct rnode *c2;
357 if ((*pat)[0] != '|')
358 return c1;
359 *pat += 1;
360 c2 = rnode_parse(pat);
361 return c2 ? rnode_make(RN_ALT, c1, c2) : c1;
362 }
363
364 static int rnode_count(struct rnode *rnode)
365 {
366 int n = 1;
367 if (!rnode)
368 return 0;
369 if (rnode->rn == RN_CAT)
370 n = rnode_count(rnode->c1) + rnode_count(rnode->c2);
371 if (rnode->rn == RN_ALT)
372 n = rnode_count(rnode->c1) + rnode_count(rnode->c2) + 2;
373 if (rnode->rn == RN_GRP)
374 n = rnode_count(rnode->c1) + 2;
375 if (rnode->mincnt == 0 && rnode->maxcnt == 0)
376 return 0;
377 if (rnode->mincnt == 1 && rnode->maxcnt == 1)
378 return n;
379 if (rnode->maxcnt < 0) {
380 n = (rnode->mincnt + 1) * n + 1;
381 } else {
382 n = (rnode->mincnt + rnode->maxcnt) * n +
383 rnode->maxcnt - rnode->mincnt;
384 }
385 if (!rnode->mincnt)
386 n++;
387 return n;
388 }
389
390 static int re_insert(struct regex *p, int ri)
391 {
392 p->p[p->n++].ri = ri;
393 return p->n - 1;
394 }
395
396 static void rnode_emit(struct rnode *n, struct regex *p);
397
398 static void rnode_emitnorep(struct rnode *n, struct regex *p)
399 {
400 int fork, done, mark;
401 if (n->rn == RN_ALT) {
402 fork = re_insert(p, RI_FORK);
403 p->p[fork].a1 = p->n;
404 rnode_emit(n->c1, p);
405 done = re_insert(p, RI_JUMP);
406 p->p[fork].a2 = p->n;
407 rnode_emit(n->c2, p);
408 p->p[done].a1 = p->n;
409 }
410 if (n->rn == RN_CAT) {
411 rnode_emit(n->c1, p);
412 rnode_emit(n->c2, p);
413 }
414 if (n->rn == RN_GRP) {
415 int grp = p->grpcnt++ + 1;
416 mark = re_insert(p, RI_MARK);
417 p->p[mark].mark = 2 * grp;
418 rnode_emit(n->c1, p);
419 mark = re_insert(p, RI_MARK);
420 p->p[mark].mark = 2 * grp + 1;
421 }
422 if (n->rn == RN_ATOM) {
423 int atom = re_insert(p, RI_ATOM);
424 ratom_copy(&p->p[atom].ra, &n->ra);
425 }
426 }
427
428 static void rnode_emit(struct rnode *n, struct regex *p)
429 {
430 int last;
431 int jmpend[NREPS];
432 int jmpend_cnt = 0;
433 int i;
434 if (!n)
435 return;
436 if (n->mincnt == 0 && n->maxcnt == 0)
437 return;
438 if (n->mincnt == 1 && n->maxcnt == 1) {
439 rnode_emitnorep(n, p);
440 return;
441 }
442 if (n->mincnt == 0) {
443 int fork = re_insert(p, RI_FORK);
444 p->p[fork].a1 = p->n;
445 jmpend[jmpend_cnt++] = fork;
446 }
447 for (i = 0; i < MAX(1, n->mincnt); i++) {
448 last = p->n;
449 rnode_emitnorep(n, p);
450 }
451 if (n->maxcnt < 0) {
452 int fork;
453 fork = re_insert(p, RI_FORK);
454 p->p[fork].a1 = last;
455 p->p[fork].a2 = p->n;
456 }
457 for (i = MAX(1, n->mincnt); i < n->maxcnt; i++) {
458 int fork = re_insert(p, RI_FORK);
459 p->p[fork].a1 = p->n;
460 jmpend[jmpend_cnt++] = fork;
461 rnode_emitnorep(n, p);
462 }
463 for (i = 0; i < jmpend_cnt; i++)
464 p->p[jmpend[i]].a2 = p->n;
465 }
466
467 int regcomp(regex_t *preg, char *pat, int flg)
468 {
469 struct rnode *rnode = rnode_parse(&pat);
470 struct regex *re = malloc(sizeof(*re));
471 int n = rnode_count(rnode) + 3;
472 int mark;
473 memset(re, 0, sizeof(*re));
474 re->p = malloc(n * sizeof(re->p[0]));
475 memset(re->p, 0, n * sizeof(re->p[0]));
476 mark = re_insert(re, RI_MARK);
477 re->p[mark].mark = 0;
478 rnode_emit(rnode, re);
479 mark = re_insert(re, RI_MARK);
480 re->p[mark].mark = 1;
481 mark = re_insert(re, RI_MATCH);
482 rnode_free(rnode);
483 re->flg = flg;
484 *preg = re;
485 return 0;
486 }
487
488 void regfree(regex_t *preg)
489 {
490 struct regex *re = *preg;
491 int i;
492 for (i = 0; i < re->n; i++)
493 if (re->p[i].ri == RI_ATOM)
494 free(re->p[i].ra.s);
495 free(re->p);
496 free(re);
497 }
498
499 static int re_rec(struct regex *re, struct rstate *rs)
500 {
501 struct rinst *ri = &re->p[rs->pc];
502 if (ri->ri == RI_ATOM) {
503 if (ratom_match(&ri->ra, rs))
504 return 1;
505 rs->pc++;
506 return re_rec(re, rs);
507 }
508 if (ri->ri == RI_MARK) {
509 if (ri->mark < NGRPS)
510 rs->mark[ri->mark] = rs->s - rs->o;
511 rs->pc++;
512 return re_rec(re, rs);
513 }
514 if (ri->ri == RI_JUMP) {
515 rs->pc = ri->a1;
516 return re_rec(re, rs);
517 }
518 if (ri->ri == RI_FORK) {
519 struct rstate base = *rs;
520 rs->pc = ri->a1;
521 if (!re_rec(re, rs))
522 return 0;
523 *rs = base;
524 rs->pc = ri->a2;
525 return re_rec(re, rs);
526 }
527 if (ri->ri == RI_MATCH)
528 return 0;
529 return 1;
530 }
531
532 static int re_recmatch(struct regex *re, struct rstate *rs, int nsub, regmatch_t *psub)
533 {
534 int i;
535 rs->pc = 0;
536 for (i = 0; i < LEN(rs->mark); i++)
537 rs->mark[i] = -1;
538 if (!re_rec(re, rs)) {
539 for (i = 0; i < nsub; i++) {
540 psub[i].rm_so = i * 2 < LEN(rs->mark) ? rs->mark[i * 2] : -1;
541 psub[i].rm_eo = i * 2 < LEN(rs->mark) ? rs->mark[i * 2 + 1] : -1;
542 }
543 return 0;
544 }
545 return 1;
546 }
547
548 int regexec(regex_t *preg, char *s, int nsub, regmatch_t psub[], int flg)
549 {
550 struct regex *re = *preg;
551 struct rstate rs;
552 memset(&rs, 0, sizeof(rs));
553 rs.flg = re->flg | flg;
554 rs.o = s;
555 while (*s) {
556 rs.s = s++;
557 if (!re_recmatch(re, &rs, flg & REG_NOSUB ? 0 : nsub, psub))
558 return 0;
559 }
560 return 1;
561 }
562
563 int regerror(int errcode, regex_t *preg, char *errbuf, int errbuf_size)
564 {
565 return 0;
566 }
A small ARM/x86(_64) libc