7 #define NGRPS 64 /* maximum number of groups */
8 #define NREPS 128 /* maximum repetitions */
9 #define NDEPT 256 /* re_rec() recursion depth limit */
11 #define MAX(a, b) ((a) < (b) ? (b) : (a))
12 #define LEN(a) (sizeof(a) / sizeof((a)[0]))
14 /* regular expressions atoms */
15 #define RA_CHR '\0' /* character literal */
16 #define RA_BEG '^' /* string start */
17 #define RA_END '$' /* string end */
18 #define RA_ANY '.' /* any character */
19 #define RA_BRK '[' /* bracket expression */
20 #define RA_WBEG '<' /* word start */
21 #define RA_WEND '>' /* word end */
23 /* regular expression node types */
24 #define RN_ATOM '\0' /* regular expression */
25 #define RN_CAT 'c' /* concatenation */
26 #define RN_ALT '|' /* alternate expressions */
27 #define RN_GRP '(' /* pattern group */
29 /* regular expression program instructions */
30 #define RI_ATOM '\0' /* regular expression */
31 #define RI_FORK 'f' /* fork the execution */
32 #define RI_JUMP 'j' /* jump to the given instruction */
33 #define RI_MARK 'm' /* mark the current position */
34 #define RI_MATCH 'q' /* the pattern is matched */
36 /* regular expression atom */
38 int ra
; /* atom type (RA_*) */
39 char *s
; /* atom argument */
42 /* regular expression instruction */
44 struct ratom ra
; /* regular expression atom (RI_ATOM) */
45 int ri
; /* instruction type (RI_*) */
46 int a1
, a2
; /* destination of RI_FORK and RI_JUMP */
47 int mark
; /* mark (RI_MARK) */
50 /* regular expression program */
52 struct rinst
*p
; /* the program */
53 int n
; /* number of instructions */
54 int flg
; /* regcomp() flags */
57 /* regular expression matching state */
59 char *s
; /* the current position in the string */
60 char *o
; /* the beginning of the string */
61 int mark
[NGRPS
* 2]; /* marks for RI_MARK */
62 int pc
; /* program counter */
63 int flg
; /* flags passed to regcomp() and regexec() */
64 int dep
; /* re_rec() depth */
67 /* regular expression tree; used for parsing */
69 struct ratom ra
; /* regular expression atom (RN_ATOM) */
70 struct rnode
*c1
, *c2
; /* children */
71 int mincnt
, maxcnt
; /* number of repetitions */
72 int grp
; /* group number */
73 int rn
; /* node type (RN_*) */
76 static struct rnode
*rnode_make(int rn
, struct rnode
*c1
, struct rnode
*c2
)
78 struct rnode
*rnode
= malloc(sizeof(*rnode
));
79 memset(rnode
, 0, sizeof(*rnode
));
88 static void rnode_free(struct rnode
*rnode
)
91 rnode_free(rnode
->c1
);
93 rnode_free(rnode
->c2
);
98 static int uc_len(char *s
)
100 int c
= (unsigned char) s
[0];
101 if (~c
& 0xc0) /* ASCII or invalid */
112 static int uc_dec(char *s
)
114 int c
= (unsigned char) s
[0];
115 if (~c
& 0xc0) /* ASCII or invalid */
118 return ((c
& 0x1f) << 6) | (s
[1] & 0x3f);
120 return ((c
& 0x0f) << 12) | ((s
[1] & 0x3f) << 6) | (s
[2] & 0x3f);
122 return ((c
& 0x07) << 18) | ((s
[1] & 0x3f) << 12) | ((s
[2] & 0x3f) << 6) | (s
[3] & 0x3f);
126 static void ratom_copy(struct ratom
*dst
, struct ratom
*src
)
131 int len
= strlen(src
->s
);
132 dst
->s
= malloc(len
+ 1);
133 memcpy(dst
->s
, src
->s
, len
+ 1);
137 static int brk_len(char *s
)
140 if (s
[n
] == '^') /* exclusion mark */
142 if (s
[n
] == ']') /* handling []a] */
144 while (s
[n
] && s
[n
] != ']') {
145 if (s
[n
] == '[' && (s
[n
+ 1] == ':' || s
[n
+ 1] == '='))
146 while (s
[n
] && s
[n
] != ']')
151 return s
[n
] == ']' ? n
+ 1 : n
;
154 static void ratom_readbrk(struct ratom
*ra
, char **pat
)
156 int len
= brk_len(*pat
);
158 ra
->s
= malloc(len
+ 1);
159 memcpy(ra
->s
, *pat
, len
);
164 static void ratom_read(struct ratom
*ra
, char **pat
)
167 switch ((unsigned char) **pat
) {
181 ratom_readbrk(ra
, pat
);
184 if ((*pat
)[1] == '<' || (*pat
)[1] == '>') {
185 ra
->ra
= (*pat
)[1] == '<' ? RA_WBEG
: RA_WEND
;
194 memcpy(ra
->s
, *pat
, len
);
200 static char *uc_beg(char *beg
, char *s
)
202 while (s
> beg
&& (((unsigned char) *s
) & 0xc0) == 0x80)
207 static int isword(char *s
)
209 int c
= (unsigned char) s
[0];
210 return isalnum(c
) || c
== '_' || c
> 127;
213 static char *brk_classes
[][2] = {
214 {":alnum:", "a-zA-Z0-9"},
215 {":alpha:", "a-zA-Z"},
219 {":print:", "\x20-\x7e"},
220 {":punct:", "][!\"#$%&'()*+,./:;<=>?@\\^_`{|}~-"},
221 {":space:", " \t\r\n\v\f"},
223 {":word:", "a-zA-Z0-9_"},
224 {":xdigit:", "a-fA-F0-9"},
227 static int brk_match(char *brk
, int c
, int flg
)
231 int not = brk
[0] == '^';
232 char *p
= not ? brk
+ 1 : brk
;
234 if (flg
& REG_ICASE
&& c
< 128 && isupper(c
))
236 while (*p
&& (p
== p0
|| *p
!= ']')) {
237 if (p
[0] == '[' && p
[1] == ':') {
238 for (i
= 0; i
< LEN(brk_classes
); i
++) {
239 char *cc
= brk_classes
[i
][0];
240 char *cp
= brk_classes
[i
][1];
241 if (!strncmp(cc
, p
+ 1, strlen(cc
)))
242 if (!brk_match(cp
, c
, flg
))
251 if (p
[0] == '-' && p
[1] && p
[1] != ']') {
256 if (flg
& REG_ICASE
&& beg
< 128 && isupper(beg
))
258 if (flg
& REG_ICASE
&& end
< 128 && isupper(end
))
260 if (c
>= beg
&& c
<= end
)
266 static int ratom_match(struct ratom
*ra
, struct rstate
*rs
)
268 if (ra
->ra
== RA_CHR
) {
269 int c1
= uc_dec(ra
->s
);
270 int c2
= uc_dec(rs
->s
);
271 if (rs
->flg
& REG_ICASE
&& c1
< 128 && isupper(c1
))
273 if (rs
->flg
& REG_ICASE
&& c2
< 128 && isupper(c2
))
277 rs
->s
+= uc_len(ra
->s
);
280 if (ra
->ra
== RA_ANY
) {
281 if (!rs
->s
[0] || (rs
->s
[0] == '\n' && !(rs
->flg
& REG_NOTEOL
)))
283 rs
->s
+= uc_len(rs
->s
);
286 if (ra
->ra
== RA_BRK
) {
287 int c
= uc_dec(rs
->s
);
288 if (!c
|| (c
== '\n' && !(rs
->flg
& REG_NOTEOL
)))
290 rs
->s
+= uc_len(rs
->s
);
291 return brk_match(ra
->s
+ 1, c
, rs
->flg
);
293 if (ra
->ra
== RA_BEG
&& !(rs
->flg
& REG_NOTBOL
))
294 return !(rs
->s
== rs
->o
|| rs
->s
[-1] == '\n');
295 if (ra
->ra
== RA_END
&& !(rs
->flg
& REG_NOTEOL
))
296 return rs
->s
[0] != '\0' && rs
->s
[0] != '\n';
297 if (ra
->ra
== RA_WBEG
)
298 return !((rs
->s
== rs
->o
|| !isword(uc_beg(rs
->o
, rs
->s
- 1))) &&
300 if (ra
->ra
== RA_WEND
)
301 return !(rs
->s
!= rs
->o
&& isword(uc_beg(rs
->o
, rs
->s
- 1)) &&
302 (!rs
->s
[0] || !isword(rs
->s
)));
306 static struct rnode
*rnode_parse(char **pat
);
308 static struct rnode
*rnode_grp(char **pat
)
310 struct rnode
*rnode
= NULL
;
311 if ((*pat
)[0] != '(')
314 if ((*pat
)[0] != ')') {
315 rnode
= rnode_parse(pat
);
319 if ((*pat
)[0] != ')') {
324 return rnode_make(RN_GRP
, rnode
, NULL
);
327 static struct rnode
*rnode_atom(char **pat
)
332 if ((*pat
)[0] == '|' || (*pat
)[0] == ')')
334 if ((*pat
)[0] == '(') {
335 rnode
= rnode_grp(pat
);
337 rnode
= rnode_make(RN_ATOM
, NULL
, NULL
);
338 ratom_read(&rnode
->ra
, pat
);
342 if ((*pat
)[0] == '*' || (*pat
)[0] == '?') {
344 rnode
->maxcnt
= (*pat
)[0] == '*' ? -1 : 1;
347 if ((*pat
)[0] == '+') {
352 if ((*pat
)[0] == '{') {
356 while (isdigit((unsigned char) **pat
))
357 rnode
->mincnt
= rnode
->mincnt
* 10 + *(*pat
)++ - '0';
360 if ((*pat
)[0] == '}')
362 while (isdigit((unsigned char) **pat
))
363 rnode
->maxcnt
= rnode
->maxcnt
* 10 + *(*pat
)++ - '0';
365 rnode
->maxcnt
= rnode
->mincnt
;
368 if (rnode
->mincnt
> NREPS
|| rnode
->maxcnt
> NREPS
) {
376 static struct rnode
*rnode_seq(char **pat
)
378 struct rnode
*c1
= rnode_atom(pat
);
383 return c2
? rnode_make(RN_CAT
, c1
, c2
) : c1
;
386 static struct rnode
*rnode_parse(char **pat
)
388 struct rnode
*c1
= rnode_seq(pat
);
390 if ((*pat
)[0] != '|')
393 c2
= rnode_parse(pat
);
394 return c2
? rnode_make(RN_ALT
, c1
, c2
) : c1
;
397 static int rnode_count(struct rnode
*rnode
)
402 if (rnode
->rn
== RN_CAT
)
403 n
= rnode_count(rnode
->c1
) + rnode_count(rnode
->c2
);
404 if (rnode
->rn
== RN_ALT
)
405 n
= rnode_count(rnode
->c1
) + rnode_count(rnode
->c2
) + 2;
406 if (rnode
->rn
== RN_GRP
)
407 n
= rnode_count(rnode
->c1
) + 2;
408 if (rnode
->mincnt
== 0 && rnode
->maxcnt
== 0)
410 if (rnode
->mincnt
== 1 && rnode
->maxcnt
== 1)
412 if (rnode
->maxcnt
< 0) {
413 n
= (rnode
->mincnt
+ 1) * n
+ 1;
415 n
= (rnode
->mincnt
+ rnode
->maxcnt
) * n
+
416 rnode
->maxcnt
- rnode
->mincnt
;
423 static int rnode_grpnum(struct rnode
*rnode
, int num
)
428 if (rnode
->rn
== RN_GRP
)
429 rnode
->grp
= num
+ cur
++;
430 cur
+= rnode_grpnum(rnode
->c1
, num
+ cur
);
431 cur
+= rnode_grpnum(rnode
->c2
, num
+ cur
);
435 static int re_insert(struct regex
*p
, int ri
)
437 p
->p
[p
->n
++].ri
= ri
;
441 static void rnode_emit(struct rnode
*n
, struct regex
*p
);
443 static void rnode_emitnorep(struct rnode
*n
, struct regex
*p
)
445 int fork
, done
, mark
;
446 if (n
->rn
== RN_ALT
) {
447 fork
= re_insert(p
, RI_FORK
);
448 p
->p
[fork
].a1
= p
->n
;
449 rnode_emit(n
->c1
, p
);
450 done
= re_insert(p
, RI_JUMP
);
451 p
->p
[fork
].a2
= p
->n
;
452 rnode_emit(n
->c2
, p
);
453 p
->p
[done
].a1
= p
->n
;
455 if (n
->rn
== RN_CAT
) {
456 rnode_emit(n
->c1
, p
);
457 rnode_emit(n
->c2
, p
);
459 if (n
->rn
== RN_GRP
) {
460 mark
= re_insert(p
, RI_MARK
);
461 p
->p
[mark
].mark
= 2 * n
->grp
;
462 rnode_emit(n
->c1
, p
);
463 mark
= re_insert(p
, RI_MARK
);
464 p
->p
[mark
].mark
= 2 * n
->grp
+ 1;
466 if (n
->rn
== RN_ATOM
) {
467 int atom
= re_insert(p
, RI_ATOM
);
468 ratom_copy(&p
->p
[atom
].ra
, &n
->ra
);
472 static void rnode_emit(struct rnode
*n
, struct regex
*p
)
480 if (n
->mincnt
== 0 && n
->maxcnt
== 0)
482 if (n
->mincnt
== 1 && n
->maxcnt
== 1) {
483 rnode_emitnorep(n
, p
);
486 if (n
->mincnt
== 0) {
487 int fork
= re_insert(p
, RI_FORK
);
488 p
->p
[fork
].a1
= p
->n
;
489 jmpend
[jmpend_cnt
++] = fork
;
491 for (i
= 0; i
< MAX(1, n
->mincnt
); i
++) {
493 rnode_emitnorep(n
, p
);
497 fork
= re_insert(p
, RI_FORK
);
498 p
->p
[fork
].a1
= last
;
499 p
->p
[fork
].a2
= p
->n
;
501 for (i
= MAX(1, n
->mincnt
); i
< n
->maxcnt
; i
++) {
502 int fork
= re_insert(p
, RI_FORK
);
503 p
->p
[fork
].a1
= p
->n
;
504 jmpend
[jmpend_cnt
++] = fork
;
505 rnode_emitnorep(n
, p
);
507 for (i
= 0; i
< jmpend_cnt
; i
++)
508 p
->p
[jmpend
[i
]].a2
= p
->n
;
511 int regcomp(regex_t
*preg
, char *pat
, int flg
)
513 struct rnode
*rnode
= rnode_parse(&pat
);
515 int n
= rnode_count(rnode
) + 3;
519 rnode_grpnum(rnode
, 1);
520 re
= malloc(sizeof(*re
));
521 memset(re
, 0, sizeof(*re
));
522 re
->p
= malloc(n
* sizeof(re
->p
[0]));
523 memset(re
->p
, 0, n
* sizeof(re
->p
[0]));
524 mark
= re_insert(re
, RI_MARK
);
525 re
->p
[mark
].mark
= 0;
526 rnode_emit(rnode
, re
);
527 mark
= re_insert(re
, RI_MARK
);
528 re
->p
[mark
].mark
= 1;
529 mark
= re_insert(re
, RI_MATCH
);
536 void regfree(regex_t
*preg
)
538 struct regex
*re
= *preg
;
540 for (i
= 0; i
< re
->n
; i
++)
541 if (re
->p
[i
].ri
== RI_ATOM
)
547 static int re_rec(struct regex
*re
, struct rstate
*rs
)
549 struct rinst
*ri
= NULL
;
550 if (rs
->dep
>= NDEPT
)
555 if (ri
->ri
== RI_ATOM
) {
556 if (ratom_match(&ri
->ra
, rs
))
561 if (ri
->ri
== RI_MARK
) {
562 if (ri
->mark
< NGRPS
)
563 rs
->mark
[ri
->mark
] = rs
->s
- rs
->o
;
567 if (ri
->ri
== RI_JUMP
) {
571 if (ri
->ri
== RI_FORK
) {
572 struct rstate base
= *rs
;
583 return ri
->ri
!= RI_MATCH
;
586 static int re_recmatch(struct regex
*re
, struct rstate
*rs
, int nsub
, regmatch_t
*psub
)
590 for (i
= 0; i
< LEN(rs
->mark
); i
++)
593 if (!re_rec(re
, rs
)) {
594 for (i
= 0; i
< nsub
; i
++) {
595 psub
[i
].rm_so
= i
* 2 < LEN(rs
->mark
) ? rs
->mark
[i
* 2] : -1;
596 psub
[i
].rm_eo
= i
* 2 < LEN(rs
->mark
) ? rs
->mark
[i
* 2 + 1] : -1;
603 int regexec(regex_t
*preg
, char *s
, int nsub
, regmatch_t psub
[], int flg
)
605 struct regex
*re
= *preg
;
607 memset(&rs
, 0, sizeof(rs
));
608 rs
.flg
= re
->flg
| flg
;
613 if (!re_recmatch(re
, &rs
, flg
& REG_NOSUB
? 0 : nsub
, psub
))
619 int regerror(int errcode
, regex_t
*preg
, char *errbuf
, int errbuf_size
)