1 /* $NetBSD: regcomp.c,v 1.7 2011/11/19 17:45:11 tnozaki Exp $ */
4 * Copyright (c) 1992, 1993, 1994 Henry Spencer.
5 * Copyright (c) 1992, 1993, 1994
6 * The Regents of the University of California. All rights reserved.
8 * This code is derived from software contributed to Berkeley by
9 * Henry Spencer of the University of Toronto.
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * @(#)regcomp.c 8.4 (Berkeley) 3/19/94
38 #if defined(LIBC_SCCS) && !defined(lint)
39 static char sccsid
[] = "@(#)regcomp.c 8.4 (Berkeley) 3/19/94";
40 #endif /* LIBC_SCCS and not lint */
42 #include <sys/types.h>
57 * parse structure, passed up and down to avoid global variables and
61 RCHAR_T
*next
; /* next character in RE */
62 RCHAR_T
*end
; /* end of string (-> NUL normally) */
63 int error
; /* has an error been seen? */
64 sop
*strip
; /* malloced strip */
65 RCHAR_T
*stripdata
; /* malloced stripdata */
66 sopno ssize
; /* malloced strip size (allocated) */
67 sopno slen
; /* malloced strip length (used) */
68 int ncsalloc
; /* number of csets allocated */
70 # define NPAREN 10 /* we need to remember () 1-9 for back refs */
71 sopno pbegin
[NPAREN
]; /* -> ( ([0] unused) */
72 sopno pend
[NPAREN
]; /* -> ) ([0] unused) */
75 /* ========= begin header generated by ./mkh ========= */
80 /* === regcomp.c === */
81 static void p_ere(struct parse
*p
, int stop
, size_t reclimit
);
82 static void p_ere_exp(struct parse
*p
, size_t reclimit
);
83 static void p_str(struct parse
*p
);
84 static void p_bre(struct parse
*p
, int end1
, int end2
, size_t reclimit
);
85 static int p_simp_re(struct parse
*p
, int starordinary
, size_t reclimit
);
86 static int p_count(struct parse
*p
);
87 static void p_bracket(struct parse
*p
);
88 static void p_b_term(struct parse
*p
, cset
*cs
);
89 static void p_b_cclass(struct parse
*p
, cset
*cs
);
90 static void p_b_eclass(struct parse
*p
, cset
*cs
);
91 static char p_b_symbol(struct parse
*p
);
92 static char p_b_coll_elem(struct parse
*p
, int endc
);
93 static char othercase(int ch
);
94 static void bothcases(struct parse
*p
, int ch
);
95 static void ordinary(struct parse
*p
, int ch
);
96 static void nonnewline(struct parse
*p
);
97 static void repeat(struct parse
*p
, sopno start
, int from
, int to
, size_t reclimit
);
98 static int seterr(struct parse
*p
, int e
);
99 static cset
*allocset(struct parse
*p
);
100 static void freeset(struct parse
*p
, cset
*cs
);
101 static int freezeset(struct parse
*p
, cset
*cs
);
102 static int firstch(struct parse
*p
, cset
*cs
);
103 static int nch(struct parse
*p
, cset
*cs
);
104 static void mcadd(struct parse
*p
, cset
*cs
, const char *cp
);
106 static void mcsub(cset
*cs
, char *cp
);
107 static int mcin(cset
*cs
, char *cp
);
108 static char *mcfind(cset
*cs
, char *cp
);
110 static void mcinvert(struct parse
*p
, cset
*cs
);
111 static void mccase(struct parse
*p
, cset
*cs
);
113 static int isinsets(struct re_guts
*g
, int c
);
114 static int samesets(struct re_guts
*g
, int c1
, int c2
);
116 static void categorize(struct parse
*p
, struct re_guts
*g
);
117 static sopno
dupl(struct parse
*p
, sopno start
, sopno finish
);
118 static void doemit(struct parse
*p
, sop op
, size_t opnd
);
119 static void doinsert(struct parse
*p
, sop op
, size_t opnd
, sopno pos
);
120 static void dofwd(struct parse
*p
, sopno pos
, sop value
);
121 static int enlarge(struct parse
*p
, sopno size
);
122 static void stripsnug(struct parse
*p
, struct re_guts
*g
);
123 static void findmust(struct parse
*p
, struct re_guts
*g
);
124 static sopno
pluscount(struct parse
*p
, struct re_guts
*g
);
129 /* ========= end header generated by ./mkh ========= */
131 static RCHAR_T nuls
[10]; /* place to point scanner in event of error */
134 * macros for use with parse structure
135 * BEWARE: these know that the parse structure is named `p' !!!
137 #define PEEK() (*p->next)
138 #define PEEK2() (*(p->next+1))
139 #define MORE() (p->next < p->end)
140 #define MORE2() (p->next+1 < p->end)
141 #define SEE(c) (MORE() && PEEK() == (c))
142 #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
143 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
144 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
145 #define NEXT() (p->next++)
146 #define NEXT2() (p->next += 2)
147 #define NEXTn(n) (p->next += (n))
148 #define GETNEXT() (*p->next++)
149 #define SETERROR(e) seterr(p, (e))
150 #define REQUIRE(co, e) ((co) || SETERROR(e))
151 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
152 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
153 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e))
154 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
155 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
156 #define AHEAD(pos) dofwd(p, pos, HERE()-(pos))
157 #define ASTERN(sop, pos) EMIT(sop, HERE()-pos)
158 #define HERE() (p->slen)
159 #define THERE() (p->slen - 1)
160 #define THERETHERE() (p->slen - 2)
161 #define DROP(n) (p->slen -= (n))
164 static int never
= 0; /* for use in asserts; shuts lint up */
166 #define never 0 /* some <assert.h>s have bugs too */
169 #define MEMLIMIT 0x8000000
171 ((p)->ncsalloc / CHAR_BIT * (p)->g->csetsize + \
172 (p)->ncsalloc * sizeof(cset) + \
173 (p)->ssize * sizeof(sop))
177 - regcomp - interface for parser and compilation
179 int /* 0 success, otherwise REG_something */
180 regcomp(regex_t
*preg
, const RCHAR_T
*pattern
, int cflags
)
184 struct parse
*p
= &pa
;
188 # define GOODFLAGS(f) (f)
190 # define GOODFLAGS(f) ((f)&~REG_DUMP)
193 cflags
= GOODFLAGS(cflags
);
194 if ((cflags
®_EXTENDED
) && (cflags
®_NOSPEC
))
197 if (cflags
®_PEND
) {
198 if (preg
->re_endp
< pattern
)
200 len
= preg
->re_endp
- pattern
;
202 len
= STRLEN(pattern
);
204 /* do the mallocs early so failure handling is easy */
205 g
= (struct re_guts
*)malloc(sizeof(struct re_guts
) +
206 (NC
-1)*sizeof(cat_t
));
209 p
->ssize
= len
/(size_t)2*(size_t)3 + (size_t)1; /* ugh */
210 p
->strip
= (sop
*)malloc(p
->ssize
* sizeof(sop
));
211 if (p
->strip
== NULL
) {
215 p
->stripdata
= (RCHAR_T
*)malloc(p
->ssize
* sizeof(RCHAR_T
));
216 if (p
->stripdata
== NULL
) {
217 free((char *)p
->strip
);
225 p
->next
= (RCHAR_T
*)pattern
; /* convenience; we do not modify it */
226 p
->end
= p
->next
+ len
;
229 for (i
= 0; i
< NPAREN
; i
++) {
245 g
->ncategories
= 1; /* category 0 is "everything else" */
246 g
->categories
= &g
->catspace
[-(CHAR_MIN
)];
247 memset((char *)g
->catspace
, 0, NC
*sizeof(cat_t
));
253 g
->firststate
= THERE();
254 if (cflags
®_EXTENDED
)
256 else if (cflags
®_NOSPEC
)
259 p_bre(p
, OUT
, OUT
, 0);
261 g
->laststate
= THERE();
263 /* tidy up loose ends and fill things in */
267 g
->nplus
= pluscount(p
, g
);
269 preg
->re_nsub
= g
->nsub
;
271 preg
->re_magic
= MAGIC1
;
273 /* not debugging, so can't rely on the assert() in regexec() */
275 SETERROR(REG_ASSERT
);
278 /* win or lose, we're done */
279 if (p
->error
!= 0) /* lose */
285 - p_ere - ERE parser top level, concatenation and alternation
288 p_ere(struct parse
*p
, int stop
, size_t reclimit
)
289 /* character this ERE should end at */
295 int first
= 1; /* is this the first alternative? */
297 if (reclimit
++ > RECLIMIT
|| p
->error
== REG_ESPACE
) {
298 p
->error
= REG_ESPACE
;
303 /* do a bunch of concatenated expressions */
305 while (MORE() && (c
= PEEK()) != '|' && c
!= stop
)
306 p_ere_exp(p
, reclimit
);
307 (void)REQUIRE(HERE() != conc
, REG_EMPTY
); /* require nonempty */
310 break; /* NOTE BREAK OUT */
313 INSERT(OCH_
, conc
); /* offset is wrong */
318 ASTERN(OOR1
, prevback
);
320 AHEAD(prevfwd
); /* fix previous offset */
322 EMIT(OOR2
, 0); /* offset is very wrong */
325 if (!first
) { /* tail-end fixups */
327 ASTERN(O_CH
, prevback
);
330 assert(!MORE() || SEE(stop
));
334 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
337 p_ere_exp(struct parse
*p
, size_t reclimit
)
346 assert(MORE()); /* caller should have ensured this */
352 (void)REQUIRE(MORE(), REG_EPAREN
);
356 p
->pbegin
[subno
] = HERE();
357 EMIT(OLPAREN
, subno
);
359 p_ere(p
, ')', reclimit
);
360 if (subno
< NPAREN
) {
361 p
->pend
[subno
] = HERE();
362 assert(p
->pend
[subno
] != 0);
364 EMIT(ORPAREN
, subno
);
365 (void)MUSTEAT(')', REG_EPAREN
);
367 #ifndef POSIX_MISTAKE
368 case ')': /* happens only if no current unmatched ( */
370 * You may ask, why the ifndef? Because I didn't notice
371 * this until slightly too late for 1003.2, and none of the
372 * other 1003.2 regular-expression reviewers noticed it at
373 * all. So an unmatched ) is legal POSIX, at least until
374 * we can get it fixed.
376 SETERROR(REG_EPAREN
);
381 p
->g
->iflags
|= USEBOL
;
387 p
->g
->iflags
|= USEEOL
;
396 SETERROR(REG_BADRPT
);
399 if (p
->g
->cflags
®_NEWLINE
)
408 (void)REQUIRE(MORE(), REG_EESCAPE
);
412 case '{': /* okay as ordinary except if digit follows */
413 (void)REQUIRE(!MORE() || !ISDIGIT((UCHAR_T
)PEEK()), REG_BADRPT
);
423 /* we call { a repetition if followed by a digit */
424 if (!( c
== '*' || c
== '+' || c
== '?' ||
425 (c
== '{' && MORE2() && ISDIGIT((UCHAR_T
)PEEK2())) ))
426 return; /* no repetition, we're done */
429 (void)REQUIRE(!wascaret
, REG_BADRPT
);
431 case '*': /* implemented as +? */
432 /* this case does not require the (y|) trick, noKLUDGE */
435 INSERT(OQUEST_
, pos
);
436 ASTERN(O_QUEST
, pos
);
443 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
444 INSERT(OCH_
, pos
); /* offset slightly wrong */
445 ASTERN(OOR1
, pos
); /* this one's right */
446 AHEAD(pos
); /* fix the OCH_ */
447 EMIT(OOR2
, 0); /* offset very wrong... */
448 AHEAD(THERE()); /* ...so fix it */
449 ASTERN(O_CH
, THERETHERE());
454 if (ISDIGIT((UCHAR_T
)PEEK())) {
456 (void)REQUIRE(count
<= count2
, REG_BADBR
);
457 } else /* single number with comma */
459 } else /* just a single number */
461 repeat(p
, pos
, count
, count2
, 0);
462 if (!EAT('}')) { /* error heuristics */
463 while (MORE() && PEEK() != '}')
465 (void)REQUIRE(MORE(), REG_EBRACE
);
474 if (!( c
== '*' || c
== '+' || c
== '?' ||
475 (c
== '{' && MORE2() && ISDIGIT((UCHAR_T
)PEEK2())) ) )
477 SETERROR(REG_BADRPT
);
481 - p_str - string (no metacharacters) "parser"
484 p_str(struct parse
*p
)
486 (void)REQUIRE(MORE(), REG_EMPTY
);
488 ordinary(p
, GETNEXT());
492 - p_bre - BRE parser top level, anchoring and concatenation
493 * Giving end1 as OUT essentially eliminates the end1/end2 check.
495 * This implementation is a bit of a kludge, in that a trailing $ is first
496 * taken as an ordinary character and then revised to be an anchor. The
497 * only undesirable side effect is that '$' gets included as a character
498 * category in such cases. This is fairly harmless; not worth fixing.
499 * The amount of lookahead needed to avoid this kludge is excessive.
502 p_bre(struct parse
*p
,
503 int end1
, /* first terminating character */
504 int end2
, /* second terminating character */
508 int first
= 1; /* first subexpression? */
511 if (reclimit
++ > RECLIMIT
|| p
->error
== REG_ESPACE
) {
512 p
->error
= REG_ESPACE
;
520 p
->g
->iflags
|= USEBOL
;
523 while (MORE() && !SEETWO(end1
, end2
)) {
524 wasdollar
= p_simp_re(p
, first
, reclimit
);
527 if (wasdollar
) { /* oops, that was a trailing anchor */
530 p
->g
->iflags
|= USEEOL
;
534 (void)REQUIRE(HERE() != start
, REG_EMPTY
); /* require nonempty */
538 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
540 static int /* was the simple RE an unbackslashed $? */
541 p_simp_re(struct parse
*p
,
542 int starordinary
, /* is a leading * an ordinary character? */
553 pos
= HERE(); /* repetion op, if any, covers from here */
555 assert(MORE()); /* caller should have ensured this */
559 (void)REQUIRE(MORE(), REG_EESCAPE
);
560 c
= (unsigned char)GETNEXT();
563 SETERROR(REG_BADRPT
);
569 p
->pbegin
[subno
] = HERE();
570 EMIT(OLPAREN
, subno
);
571 /* the MORE here is an error heuristic */
572 if (MORE() && !SEETWO('\\', ')'))
573 p_bre(p
, '\\', ')', reclimit
);
574 if (subno
< NPAREN
) {
575 p
->pend
[subno
] = HERE();
576 assert(p
->pend
[subno
] != 0);
578 EMIT(ORPAREN
, subno
);
579 (void)REQUIRE(EATTWO('\\', ')'), REG_EPAREN
);
581 case ')': /* should not get here -- must be user */
583 SETERROR(REG_EPAREN
);
596 if (p
->pend
[i
] != 0) {
597 assert(i
<= p
->g
->nsub
);
599 assert(p
->pbegin
[i
] != 0);
600 assert(p
->strip
[p
->pbegin
[i
]] == OLPAREN
);
601 assert(p
->strip
[p
->pend
[i
]] == ORPAREN
);
602 (void) dupl(p
, p
->pbegin
[i
]+1, p
->pend
[i
]);
605 SETERROR(REG_ESUBREG
);
615 if (p
->g
->cflags
®_NEWLINE
)
624 (void)REQUIRE(starordinary
, REG_BADRPT
);
632 if (EAT('*')) { /* implemented as +? */
633 /* this case does not require the (y|) trick, noKLUDGE */
636 INSERT(OQUEST_
, pos
);
637 ASTERN(O_QUEST
, pos
);
638 } else if (EATTWO('\\', '{')) {
641 if (MORE() && ISDIGIT((UCHAR_T
)PEEK())) {
643 (void)REQUIRE(count
<= count2
, REG_BADBR
);
644 } else /* single number with comma */
646 } else /* just a single number */
648 repeat(p
, pos
, count
, count2
, reclimit
);
649 if (!EATTWO('\\', '}')) { /* error heuristics */
650 while (MORE() && !SEETWO('\\', '}'))
652 (void)REQUIRE(MORE(), REG_EBRACE
);
655 } else if (!backsl
&& c
== (unsigned char)'$') /* $ (but not \$) ends it */
662 - p_count - parse a repetition count
664 static int /* the value */
665 p_count(struct parse
*p
)
670 while (MORE() && ISDIGIT((UCHAR_T
)PEEK()) && count
<= DUPMAX
) {
671 count
= count
*10 + (GETNEXT() - '0');
675 (void)REQUIRE(ndigits
> 0 && count
<= DUPMAX
, REG_BADBR
);
680 - p_bracket - parse a bracketed character list
682 * Note a significant property of this code: if the allocset() did SETERROR,
683 * no set operations are done.
686 p_bracket(struct parse
*p
)
690 static RCHAR_T bow
[] = { '[', ':', '<', ':', ']', ']' };
691 static RCHAR_T eow
[] = { '[', ':', '>', ':', ']', ']' };
697 /* Dept of Truly Sickening Special-Case Kludges */
698 if (p
->next
+ 5 < p
->end
&& MEMCMP(p
->next
, bow
, 6) == 0) {
703 if (p
->next
+ 5 < p
->end
&& MEMCMP(p
->next
, eow
, 6) == 0) {
710 invert
++; /* make note to invert set at end */
715 while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
719 (void)MUSTEAT(']', REG_EBRACK
);
721 if (p
->error
!= 0) /* don't mess things up further */
724 if (p
->g
->cflags
®_ICASE
) {
728 for (i
= p
->g
->csetsize
- 1; i
>= 0; i
--)
729 if (CHIN(cs
, i
) && isalpha(i
)) {
734 if (cs
->multis
!= NULL
)
740 for (i
= p
->g
->csetsize
- 1; i
>= 0; i
--)
745 if (p
->g
->cflags
®_NEWLINE
)
747 if (cs
->multis
!= NULL
)
751 assert(cs
->multis
== NULL
); /* xxx */
753 if (nch(p
, cs
) == 1) { /* optimize singleton sets */
754 ordinary(p
, firstch(p
, cs
));
757 EMIT(OANYOF
, freezeset(p
, cs
));
761 - p_b_term - parse one term of a bracketed character list
764 p_b_term(struct parse
*p
, cset
*cs
)
770 /* classify what we've got */
771 switch ((MORE()) ? PEEK() : '\0') {
773 c
= (MORE2()) ? PEEK2() : '\0';
776 SETERROR(REG_ERANGE
);
777 return; /* NOTE RETURN */
785 case ':': /* character class */
787 (void)REQUIRE(MORE(), REG_EBRACK
);
789 (void)REQUIRE(c
!= '-' && c
!= ']', REG_ECTYPE
);
791 (void)REQUIRE(MORE(), REG_EBRACK
);
792 (void)REQUIRE(EATTWO(':', ']'), REG_ECTYPE
);
794 case '=': /* equivalence class */
796 (void)REQUIRE(MORE(), REG_EBRACK
);
798 (void)REQUIRE(c
!= '-' && c
!= ']', REG_ECOLLATE
);
800 (void)REQUIRE(MORE(), REG_EBRACK
);
801 (void)REQUIRE(EATTWO('=', ']'), REG_ECOLLATE
);
803 default: /* symbol, ordinary character, or range */
804 /* xxx revision needed for multichar stuff */
805 start
= p_b_symbol(p
);
806 if (SEE('-') && MORE2() && PEEK2() != ']') {
812 finish
= p_b_symbol(p
);
815 /* xxx what about signed chars here... */
816 (void)REQUIRE(start
<= finish
, REG_ERANGE
);
817 for (i
= start
; i
<= finish
; i
++)
824 - p_b_cclass - parse a character-class name and deal with it
827 p_b_cclass(struct parse
*p
, cset
*cs
)
829 RCHAR_T
*sp
= p
->next
;
835 while (MORE() && isalpha(PEEK()))
838 for (cp
= cclasses
; cp
->name
!= NULL
; cp
++)
839 if (STRLEN(cp
->name
) == len
&& !MEMCMP(cp
->name
, sp
, len
))
841 if (cp
->name
== NULL
) {
842 /* oops, didn't find it */
843 SETERROR(REG_ECTYPE
);
848 while ((c
= *u
++) != '\0')
850 for (u
= cp
->multis
; *u
!= '\0'; u
+= strlen(u
) + 1)
855 - p_b_eclass - parse an equivalence-class name and deal with it
857 * This implementation is incomplete. xxx
860 p_b_eclass(struct parse
*p
, cset
*cs
)
864 c
= p_b_coll_elem(p
, '=');
869 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
871 static char /* value of symbol */
872 p_b_symbol(struct parse
*p
)
876 (void)REQUIRE(MORE(), REG_EBRACK
);
877 if (!EATTWO('[', '.'))
880 /* collating symbol */
881 value
= p_b_coll_elem(p
, '.');
882 (void)REQUIRE(EATTWO('.', ']'), REG_ECOLLATE
);
887 - p_b_coll_elem - parse a collating-element name and look it up
889 static char /* value of collating element */
890 p_b_coll_elem(struct parse
*p
, int endc
)
892 /* name ended by endc,']' */
894 RCHAR_T
*sp
= p
->next
;
898 while (MORE() && !SEETWO(endc
, ']'))
901 SETERROR(REG_EBRACK
);
905 for (cp
= cnames
; cp
->name
!= NULL
; cp
++)
906 if (STRLEN(cp
->name
) == len
&& MEMCMP(cp
->name
, sp
, len
))
907 return(cp
->code
); /* known name */
909 return(*sp
); /* single character */
910 SETERROR(REG_ECOLLATE
); /* neither */
915 - othercase - return the case counterpart of an alphabetic
917 static char /* if no counterpart, return ch */
923 else if (islower(ch
))
925 else /* peculiar, but could happen */
930 - bothcases - emit a dualcase version of a two-case character
932 * Boy, is this implementation ever a kludge...
935 bothcases(struct parse
*p
, int ch
)
937 RCHAR_T
*oldnext
= p
->next
;
938 RCHAR_T
*oldend
= p
->end
;
941 assert(othercase(ch
) != ch
); /* p_bracket() would recurse */
948 assert(p
->next
== bracket
+2);
954 - ordinary - emit an ordinary character
957 ordinary(struct parse
*p
, int ch
)
960 cat_t *cap = p->g->categories;
963 if ((p
->g
->cflags
®_ICASE
) && isalpha(ch
) && othercase(ch
) != ch
)
966 EMIT(OCHAR
, (UCHAR_T
)ch
);
969 cap[ch] = p->g->ncategories++;
975 - nonnewline - emit REG_NEWLINE version of OANY
977 * Boy, is this implementation ever a kludge...
980 nonnewline(struct parse
*p
)
982 RCHAR_T
*oldnext
= p
->next
;
983 RCHAR_T
*oldend
= p
->end
;
993 assert(p
->next
== bracket
+3);
999 - repeat - generate code for a bounded repetition, recursively if needed
1002 repeat(struct parse
*p
,
1003 sopno start
, /* operand from here to end of strip */
1004 int from
, /* repeated from this number */
1005 int to
, /* to this number of times (maybe INFINITY) */
1011 # define REP(f, t) ((f)*8 + (t))
1012 # define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
1015 if (reclimit
++ > RECLIMIT
)
1016 p
->error
= REG_ESPACE
;
1024 switch (REP(MAP(from
), MAP(to
))) {
1025 case REP(0, 0): /* must be user doing this */
1026 DROP(finish
-start
); /* drop the operand */
1028 case REP(0, 1): /* as x{1,1}? */
1029 case REP(0, N
): /* as x{1,n}? */
1030 case REP(0, INF
): /* as x{1,}? */
1031 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1032 INSERT(OCH_
, start
); /* offset is wrong... */
1033 repeat(p
, start
+1, 1, to
, reclimit
);
1034 ASTERN(OOR1
, start
);
1035 AHEAD(start
); /* ... fix it */
1038 ASTERN(O_CH
, THERETHERE());
1040 case REP(1, 1): /* trivial case */
1043 case REP(1, N
): /* as x?x{1,n-1} */
1044 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1045 INSERT(OCH_
, start
);
1046 ASTERN(OOR1
, start
);
1048 EMIT(OOR2
, 0); /* offset very wrong... */
1049 AHEAD(THERE()); /* ...so fix it */
1050 ASTERN(O_CH
, THERETHERE());
1051 copy
= dupl(p
, start
+1, finish
+1);
1052 assert(copy
== finish
+4);
1053 repeat(p
, copy
, 1, to
-1, reclimit
);
1055 case REP(1, INF
): /* as x+ */
1056 INSERT(OPLUS_
, start
);
1057 ASTERN(O_PLUS
, start
);
1059 case REP(N
, N
): /* as xx{m-1,n-1} */
1060 copy
= dupl(p
, start
, finish
);
1061 repeat(p
, copy
, from
-1, to
-1, reclimit
);
1063 case REP(N
, INF
): /* as xx{n-1,INF} */
1064 copy
= dupl(p
, start
, finish
);
1065 repeat(p
, copy
, from
-1, to
, reclimit
);
1067 default: /* "can't happen" */
1068 SETERROR(REG_ASSERT
); /* just in case */
1074 - seterr - set an error condition
1076 static int /* useless but makes type checking happy */
1077 seterr(struct parse
*p
, int e
)
1079 if (p
->error
== 0) /* keep earliest error condition */
1081 p
->next
= nuls
; /* try to bring things to a halt */
1083 return(0); /* make the return value well-defined */
1087 - allocset - allocate a set of characters for []
1090 allocset(struct parse
*p
)
1092 int no
= p
->g
->ncsets
++;
1096 size_t css
= (size_t)p
->g
->csetsize
;
1099 if (no
>= p
->ncsalloc
) { /* need another column of space */
1100 p
->ncsalloc
+= CHAR_BIT
;
1102 assert(nc
% CHAR_BIT
== 0);
1103 nbytes
= nc
/ CHAR_BIT
* css
;
1104 if (MEMSIZE(p
) > MEMLIMIT
)
1106 if (p
->g
->sets
== NULL
)
1107 p
->g
->sets
= (cset
*)malloc(nc
* sizeof(cset
));
1109 p
->g
->sets
= (cset
*)realloc((char *)p
->g
->sets
,
1111 if (p
->g
->setbits
== NULL
)
1112 p
->g
->setbits
= (uch
*)malloc(nbytes
);
1114 p
->g
->setbits
= (uch
*)realloc((char *)p
->g
->setbits
,
1116 /* xxx this isn't right if setbits is now NULL */
1117 for (i
= 0; i
< no
; i
++)
1118 p
->g
->sets
[i
].ptr
= p
->g
->setbits
+ css
*(i
/CHAR_BIT
);
1120 if (p
->g
->sets
!= NULL
&& p
->g
->setbits
!= NULL
)
1121 memset((char *)p
->g
->setbits
+ (nbytes
- css
),
1126 SETERROR(REG_ESPACE
);
1127 /* caller's responsibility not to do set ops */
1132 cs
= &p
->g
->sets
[no
];
1133 cs
->ptr
= p
->g
->setbits
+ css
*((no
)/CHAR_BIT
);
1134 cs
->mask
= 1 << ((no
) % CHAR_BIT
);
1143 - freeset - free a now-unused set
1146 freeset(struct parse
*p
, cset
*cs
)
1149 cset
*top
= &p
->g
->sets
[p
->g
->ncsets
];
1150 size_t css
= (size_t)p
->g
->csetsize
;
1152 for (i
= 0; i
< css
; i
++)
1154 if (cs
== top
-1) /* recover only the easy case */
1159 - freezeset - final processing on a set of characters
1161 * The main task here is merging identical sets. This is usually a waste
1162 * of time (although the hash code minimizes the overhead), but can win
1163 * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash
1164 * is done using addition rather than xor -- all ASCII [aA] sets xor to
1167 static int /* set number */
1168 freezeset(struct parse
*p
, cset
*cs
)
1172 cset
*top
= &p
->g
->sets
[p
->g
->ncsets
];
1174 size_t css
= (size_t)p
->g
->csetsize
;
1176 /* look for an earlier one which is the same */
1177 for (cs2
= &p
->g
->sets
[0]; cs2
< top
; cs2
++)
1178 if (cs2
->hash
== h
&& cs2
!= cs
) {
1180 for (i
= 0; i
< css
; i
++)
1181 if (!!CHIN(cs2
, i
) != !!CHIN(cs
, i
))
1187 if (cs2
< top
) { /* found one */
1192 return((int)(cs
- p
->g
->sets
));
1196 - firstch - return first character in a set (which must have at least one)
1198 static int /* character; there is no "none" value */
1199 firstch(struct parse
*p
, cset
*cs
)
1202 size_t css
= (size_t)p
->g
->csetsize
;
1204 for (i
= 0; i
< css
; i
++)
1208 return(0); /* arbitrary */
1212 - nch - number of characters in a set
1215 nch(struct parse
*p
, cset
*cs
)
1218 size_t css
= (size_t)p
->g
->csetsize
;
1221 for (i
= 0; i
< css
; i
++)
1228 - mcadd - add a collating element to a cset
1231 mcadd(struct parse
*p
, cset
*cs
, const char *cp
)
1233 size_t oldend
= cs
->smultis
;
1236 cs
->smultis
+= strlen(cp
) + 1;
1237 np
= realloc(cs
->multis
, cs
->smultis
);
1242 SETERROR(REG_ESPACE
);
1247 strlcpy(cs
->multis
+ oldend
- 1, cp
, cs
->smultis
- oldend
+ 1);
1251 - mcinvert - invert the list of collating elements in a cset
1253 * This would have to know the set of possibilities. Implementation
1257 mcinvert(struct parse
*p
, cset
*cs
)
1259 assert(cs
->multis
== NULL
); /* xxx */
1263 - mccase - add case counterparts of the list of collating elements in a cset
1265 * This would have to know the set of possibilities. Implementation
1269 mccase(struct parse
*p
, cset
*cs
)
1271 assert(cs
->multis
== NULL
); /* xxx */
1276 - isinsets - is this character in any sets?
1278 static int /* predicate */
1279 isinsets(struct re_guts
*g
, int c
)
1283 int ncols
= (g
->ncsets
+(CHAR_BIT
-1)) / CHAR_BIT
;
1284 unsigned uc
= (unsigned char)c
;
1286 for (i
= 0, col
= g
->setbits
; i
< ncols
; i
++, col
+= g
->csetsize
)
1293 - samesets - are these two characters in exactly the same sets?
1295 static int /* predicate */
1296 samesets(struct re_guts
*g
, int c1
, int c2
)
1300 int ncols
= (g
->ncsets
+(CHAR_BIT
-1)) / CHAR_BIT
;
1301 unsigned uc1
= (unsigned char)c1
;
1302 unsigned uc2
= (unsigned char)c2
;
1304 for (i
= 0, col
= g
->setbits
; i
< ncols
; i
++, col
+= g
->csetsize
)
1305 if (col
[uc1
] != col
[uc2
])
1312 - categorize - sort out character categories
1315 categorize(struct parse
*p
, struct re_guts
*g
)
1318 cat_t
*cats
= g
->categories
;
1323 /* avoid making error situations worse */
1327 for (c
= CHAR_MIN
; c
<= CHAR_MAX
; c
++)
1328 if (cats
[c
] == 0 && isinsets(g
, c
)) {
1329 cat
= g
->ncategories
++;
1331 for (c2
= c
+1; c2
<= CHAR_MAX
; c2
++)
1332 if (cats
[c2
] == 0 && samesets(g
, c
, c2
))
1339 - dupl - emit a duplicate of a bunch of sops
1341 static sopno
/* start of duplicate */
1342 dupl(struct parse
*p
,
1343 sopno start
, /* from here */
1344 sopno finish
) /* to this less one */
1347 sopno len
= finish
- start
;
1349 assert(finish
>= start
);
1352 if (!enlarge(p
, p
->ssize
+ len
)) /* this many unexpected additions */
1354 assert(p
->ssize
>= p
->slen
+ len
);
1355 (void) memcpy((char *)(p
->strip
+ p
->slen
),
1356 (char *)(p
->strip
+ start
), (size_t)len
*sizeof(sop
));
1357 (void) memcpy((char *)(p
->stripdata
+ p
->slen
),
1358 (char *)(p
->stripdata
+ start
), (size_t)len
*sizeof(RCHAR_T
));
1364 - doemit - emit a strip operator
1366 * It might seem better to implement this as a macro with a function as
1367 * hard-case backup, but it's just too big and messy unless there are
1368 * some changes to the data structures. Maybe later.
1371 doemit(struct parse
*p
, sop op
, size_t opnd
)
1373 /* avoid making error situations worse */
1377 /* deal with oversize operands ("can't happen", more or less) */
1380 /* deal with undersized strip */
1381 if (p
->slen
>= p
->ssize
)
1382 if (!enlarge(p
, (p
->ssize
+1) / 2 * 3)) /* +50% */
1385 /* finally, it's all reduced to the easy case */
1386 p
->strip
[p
->slen
] = op
;
1387 p
->stripdata
[p
->slen
] = opnd
;
1392 - doinsert - insert a sop into the strip
1395 doinsert(struct parse
*p
, sop op
, size_t opnd
, sopno pos
)
1402 /* avoid making error situations worse */
1407 EMIT(op
, opnd
); /* do checks, ensure space */
1408 assert(HERE() == sn
+1);
1410 d
= p
->stripdata
[sn
];
1412 /* adjust paren pointers */
1414 for (i
= 1; i
< NPAREN
; i
++) {
1415 if (p
->pbegin
[i
] >= pos
) {
1418 if (p
->pend
[i
] >= pos
) {
1423 memmove((char *)&p
->strip
[pos
+1], (char *)&p
->strip
[pos
],
1424 (HERE()-pos
-1)*sizeof(sop
));
1425 memmove((char *)&p
->stripdata
[pos
+1], (char *)&p
->stripdata
[pos
],
1426 (HERE()-pos
-1)*sizeof(RCHAR_T
));
1428 p
->stripdata
[pos
] = d
;
1432 - dofwd - complete a forward reference
1435 dofwd(struct parse
*p
, sopno pos
, sop value
)
1437 /* avoid making error situations worse */
1442 p
->stripdata
[pos
] = value
;
1446 - enlarge - enlarge the strip
1449 enlarge(struct parse
*p
, sopno size
)
1455 if (p
->ssize
>= size
)
1460 if (MEMSIZE(p
) > MEMLIMIT
)
1462 sp
= realloc(p
->strip
, p
->ssize
* sizeof(sop
));
1466 dp
= realloc(p
->stripdata
, p
->ssize
* sizeof(RCHAR_T
));
1470 SETERROR(REG_ESPACE
);
1478 - stripsnug - compact the strip
1481 stripsnug(struct parse
*p
, struct re_guts
*g
)
1483 g
->nstates
= p
->slen
;
1484 g
->strip
= (sop
*)realloc((char *)p
->strip
,
1485 p
->slen
* sizeof(sop
));
1486 if (g
->strip
== NULL
) {
1487 SETERROR(REG_ESPACE
);
1488 g
->strip
= p
->strip
;
1490 g
->stripdata
= (RCHAR_T
*)realloc((char *)p
->stripdata
,
1491 p
->slen
* sizeof(RCHAR_T
));
1492 if (g
->stripdata
== NULL
) {
1493 SETERROR(REG_ESPACE
);
1494 g
->stripdata
= p
->stripdata
;
1499 - findmust - fill in must and mlen with longest mandatory literal string
1501 * This algorithm could do fancy things like analyzing the operands of |
1502 * for common subsequences. Someday. This code is simple and finds most
1503 * of the interesting cases.
1505 * Note that must and mlen got initialized during setup.
1508 findmust(struct parse
*p
, struct re_guts
*g
)
1513 RCHAR_T
*startd
= NULL
;
1515 RCHAR_T
*newstartd
= NULL
;
1522 /* avoid making error situations worse */
1526 /* find the longest OCHAR sequence in strip */
1528 scans
= g
->strip
+ 1;
1529 scand
= g
->stripdata
+ 1;
1534 case OCHAR
: /* sequence member */
1535 if (newlen
== 0) { /* new sequence */
1536 newstarts
= scans
- 1;
1537 newstartd
= scand
- 1;
1541 case OPLUS_
: /* things that don't break one */
1545 case OQUEST_
: /* things that must be skipped */
1554 /* assert() interferes w debug printouts */
1555 if (s
!= O_QUEST
&& s
!= O_CH
&& s
!= OOR2
) {
1559 } while (s
!= O_QUEST
&& s
!= O_CH
);
1561 default: /* things that break a sequence */
1562 if (newlen
> g
->mlen
) { /* ends one */
1570 } while (s
!= OEND
);
1572 if (g
->mlen
== 0) /* there isn't one */
1575 /* turn it into a character string */
1576 g
->must
= malloc(((size_t)g
->mlen
+ 1) * sizeof(RCHAR_T
));
1577 if (g
->must
== NULL
) { /* argh; just forget it */
1584 for (i
= g
->mlen
; i
> 0; i
--) {
1591 assert(cp
< g
->must
+ g
->mlen
);
1594 assert(cp
== g
->must
+ g
->mlen
);
1595 *cp
++ = '\0'; /* just on general principles */
1599 - pluscount - count + nesting
1601 static sopno
/* nesting depth */
1602 pluscount(struct parse
*p
, struct re_guts
*g
)
1610 return(0); /* there may not be an OEND */
1612 scan
= g
->strip
+ 1;
1620 if (plusnest
> maxnest
)
1625 } while (s
!= OEND
);