2 * Copyright (c) 1992, 1993, 1994 Henry Spencer.
3 * Copyright (c) 1992, 1993, 1994
4 * The Regents of the University of California. All rights reserved.
6 * This code is derived from software contributed to Berkeley by
7 * Henry Spencer of the University of Toronto.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed by the University of
20 * California, Berkeley and its contributors.
21 * 4. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * @(#)regcomp.c 8.4 (Berkeley) 3/19/94
40 #if defined(LIBC_SCCS) && !defined(lint)
41 static char sccsid
[] = "@(#)regcomp.c 8.4 (Berkeley) 3/19/94";
42 #endif /* LIBC_SCCS and not lint */
44 #include <sys/types.h>
59 * parse structure, passed up and down to avoid global variables and
63 RCHAR_T
*next
; /* next character in RE */
64 RCHAR_T
*end
; /* end of string (-> NUL normally) */
65 int error
; /* has an error been seen? */
66 sop
*strip
; /* malloced strip */
67 sopno ssize
; /* malloced strip size (allocated) */
68 sopno slen
; /* malloced strip length (used) */
69 int ncsalloc
; /* number of csets allocated */
71 # define NPAREN 10 /* we need to remember () 1-9 for back refs */
72 sopno pbegin
[NPAREN
]; /* -> ( ([0] unused) */
73 sopno pend
[NPAREN
]; /* -> ) ([0] unused) */
76 /* ========= begin header generated by ./mkh ========= */
81 /* === regcomp.c === */
82 static void p_ere
__P((struct parse
*p
, int stop
));
83 static void p_ere_exp
__P((struct parse
*p
));
84 static void p_str
__P((struct parse
*p
));
85 static void p_bre
__P((struct parse
*p
, int end1
, int end2
));
86 static int p_simp_re
__P((struct parse
*p
, int starordinary
));
87 static int p_count
__P((struct parse
*p
));
88 static void p_bracket
__P((struct parse
*p
));
89 static void p_b_term
__P((struct parse
*p
, cset
*cs
));
90 static void p_b_cclass
__P((struct parse
*p
, cset
*cs
));
91 static void p_b_eclass
__P((struct parse
*p
, cset
*cs
));
92 static char p_b_symbol
__P((struct parse
*p
));
93 static char p_b_coll_elem
__P((struct parse
*p
, int endc
));
94 static char othercase
__P((int ch
));
95 static void bothcases
__P((struct parse
*p
, int ch
));
96 static void ordinary
__P((struct parse
*p
, int ch
));
97 static void nonnewline
__P((struct parse
*p
));
98 static void repeat
__P((struct parse
*p
, sopno start
, int from
, int to
));
99 static int seterr
__P((struct parse
*p
, int e
));
100 static cset
*allocset
__P((struct parse
*p
));
101 static void freeset
__P((struct parse
*p
, cset
*cs
));
102 static int freezeset
__P((struct parse
*p
, cset
*cs
));
103 static int firstch
__P((struct parse
*p
, cset
*cs
));
104 static int nch
__P((struct parse
*p
, cset
*cs
));
105 static void mcadd
__P((struct parse
*p
, cset
*cs
, char *cp
));
106 static void mcsub
__P((cset
*cs
, char *cp
));
107 static int mcin
__P((cset
*cs
, char *cp
));
108 static char *mcfind
__P((cset
*cs
, char *cp
));
109 static void mcinvert
__P((struct parse
*p
, cset
*cs
));
110 static void mccase
__P((struct parse
*p
, cset
*cs
));
111 static int isinsets
__P((struct re_guts
*g
, int c
));
112 static int samesets
__P((struct re_guts
*g
, int c1
, int c2
));
113 static void categorize
__P((struct parse
*p
, struct re_guts
*g
));
114 static sopno dupl
__P((struct parse
*p
, sopno start
, sopno finish
));
115 static void doemit
__P((struct parse
*p
, sop op
, size_t opnd
));
116 static void doinsert
__P((struct parse
*p
, sop op
, size_t opnd
, sopno pos
));
117 static void dofwd
__P((struct parse
*p
, sopno pos
, sop value
));
118 static void enlarge
__P((struct parse
*p
, sopno size
));
119 static void stripsnug
__P((struct parse
*p
, struct re_guts
*g
));
120 static void findmust
__P((struct parse
*p
, struct re_guts
*g
));
121 static sopno pluscount
__P((struct parse
*p
, struct re_guts
*g
));
126 /* ========= end header generated by ./mkh ========= */
128 static RCHAR_T nuls
[10]; /* place to point scanner in event of error */
131 * macros for use with parse structure
132 * BEWARE: these know that the parse structure is named `p' !!!
134 #define PEEK() (*p->next)
135 #define PEEK2() (*(p->next+1))
136 #define MORE() (p->next < p->end)
137 #define MORE2() (p->next+1 < p->end)
138 #define SEE(c) (MORE() && PEEK() == (c))
139 #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
140 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
141 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
142 #define NEXT() (p->next++)
143 #define NEXT2() (p->next += 2)
144 #define NEXTn(n) (p->next += (n))
145 #define GETNEXT() (*p->next++)
146 #define SETERROR(e) seterr(p, (e))
147 #define REQUIRE(co, e) ((co) || SETERROR(e))
148 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
149 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
150 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e))
151 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
152 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
153 #define AHEAD(pos) dofwd(p, pos, HERE()-(pos))
154 #define ASTERN(sop, pos) EMIT(sop, HERE()-pos)
155 #define HERE() (p->slen)
156 #define THERE() (p->slen - 1)
157 #define THERETHERE() (p->slen - 2)
158 #define DROP(n) (p->slen -= (n))
161 static int never
= 0; /* for use in asserts; shuts lint up */
163 #define never 0 /* some <assert.h>s have bugs too */
167 - regcomp - interface for parser and compilation
168 = extern int regcomp(regex_t *, const RCHAR_T *, int);
169 = #define REG_BASIC 0000
170 = #define REG_EXTENDED 0001
171 = #define REG_ICASE 0002
172 = #define REG_NOSUB 0004
173 = #define REG_NEWLINE 0010
174 = #define REG_NOSPEC 0020
175 = #define REG_PEND 0040
176 = #define REG_DUMP 0200
178 int /* 0 success, otherwise REG_something */
179 regcomp(regex_t
*preg
, const RCHAR_T
*pattern
, int cflags
)
182 register struct re_guts
*g
;
183 register struct parse
*p
= &pa
;
187 # define GOODFLAGS(f) (f)
189 # define GOODFLAGS(f) ((f)&~REG_DUMP)
192 cflags
= GOODFLAGS(cflags
);
193 if ((cflags
®_EXTENDED
) && (cflags
®_NOSPEC
))
196 if (cflags
®_PEND
) {
197 if (preg
->re_endp
< pattern
)
199 len
= preg
->re_endp
- pattern
;
201 len
= STRLEN(pattern
);
203 /* do the mallocs early so failure handling is easy */
204 g
= (struct re_guts
*)malloc(sizeof(struct re_guts
) +
205 (NC
-1)*sizeof(cat_t
));
208 p
->ssize
= len
/(size_t)2*(size_t)3 + (size_t)1; /* ugh */
209 p
->strip
= (sop
*)malloc(p
->ssize
* sizeof(sop
));
211 if (p
->strip
== NULL
) {
218 p
->next
= (RCHAR_T
*)pattern
; /* convenience; we do not modify it */
219 p
->end
= p
->next
+ len
;
222 for (i
= 0; i
< NPAREN
; i
++) {
238 g
->ncategories
= 1; /* category 0 is "everything else" */
239 g
->categories
= &g
->catspace
[-(CHAR_MIN
)];
240 (void) memset((char *)g
->catspace
, 0, NC
*sizeof(cat_t
));
246 g
->firststate
= THERE();
247 if (cflags
®_EXTENDED
)
249 else if (cflags
®_NOSPEC
)
254 g
->laststate
= THERE();
256 /* tidy up loose ends and fill things in */
260 g
->nplus
= pluscount(p
, g
);
262 preg
->re_nsub
= g
->nsub
;
264 preg
->re_magic
= MAGIC1
;
266 /* not debugging, so can't rely on the assert() in regexec() */
268 SETERROR(REG_ASSERT
);
271 /* win or lose, we're done */
272 if (p
->error
!= 0) /* lose */
278 - p_ere - ERE parser top level, concatenation and alternation
279 == static void p_ere(register struct parse *p, int stop);
282 p_ere(register struct parse
*p
, int stop
)
284 /* character this ERE should end at */
287 register sopno prevback
;
288 register sopno prevfwd
;
290 register int first
= 1; /* is this the first alternative? */
293 /* do a bunch of concatenated expressions */
295 while (MORE() && (c
= PEEK()) != '|' && c
!= stop
)
297 REQUIRE(HERE() != conc
, REG_EMPTY
); /* require nonempty */
300 break; /* NOTE BREAK OUT */
303 INSERT(OCH_
, conc
); /* offset is wrong */
308 ASTERN(OOR1
, prevback
);
310 AHEAD(prevfwd
); /* fix previous offset */
312 EMIT(OOR2
, 0); /* offset is very wrong */
315 if (!first
) { /* tail-end fixups */
317 ASTERN(O_CH
, prevback
);
320 assert(!MORE() || SEE(stop
));
324 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
325 == static void p_ere_exp(register struct parse *p);
328 p_ere_exp(register struct parse
*p
)
334 register sopno subno
;
337 assert(MORE()); /* caller should have ensured this */
343 REQUIRE(MORE(), REG_EPAREN
);
347 p
->pbegin
[subno
] = HERE();
348 EMIT(OLPAREN
, subno
);
351 if (subno
< NPAREN
) {
352 p
->pend
[subno
] = HERE();
353 assert(p
->pend
[subno
] != 0);
355 EMIT(ORPAREN
, subno
);
356 MUSTEAT(')', REG_EPAREN
);
358 #ifndef POSIX_MISTAKE
359 case ')': /* happens only if no current unmatched ( */
361 * You may ask, why the ifndef? Because I didn't notice
362 * this until slightly too late for 1003.2, and none of the
363 * other 1003.2 regular-expression reviewers noticed it at
364 * all. So an unmatched ) is legal POSIX, at least until
365 * we can get it fixed.
367 SETERROR(REG_EPAREN
);
372 p
->g
->iflags
|= USEBOL
;
378 p
->g
->iflags
|= USEEOL
;
387 SETERROR(REG_BADRPT
);
390 if (p
->g
->cflags
®_NEWLINE
)
399 REQUIRE(MORE(), REG_EESCAPE
);
403 case '{': /* okay as ordinary except if digit follows */
404 REQUIRE(!MORE() || !isdigit(PEEK()), REG_BADRPT
);
414 /* we call { a repetition if followed by a digit */
415 if (!( c
== '*' || c
== '+' || c
== '?' ||
416 (c
== '{' && MORE2() && isdigit(PEEK2())) ))
417 return; /* no repetition, we're done */
420 REQUIRE(!wascaret
, REG_BADRPT
);
422 case '*': /* implemented as +? */
423 /* this case does not require the (y|) trick, noKLUDGE */
426 INSERT(OQUEST_
, pos
);
427 ASTERN(O_QUEST
, pos
);
434 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
435 INSERT(OCH_
, pos
); /* offset slightly wrong */
436 ASTERN(OOR1
, pos
); /* this one's right */
437 AHEAD(pos
); /* fix the OCH_ */
438 EMIT(OOR2
, 0); /* offset very wrong... */
439 AHEAD(THERE()); /* ...so fix it */
440 ASTERN(O_CH
, THERETHERE());
445 if (isdigit(PEEK())) {
447 REQUIRE(count
<= count2
, REG_BADBR
);
448 } else /* single number with comma */
450 } else /* just a single number */
452 repeat(p
, pos
, count
, count2
);
453 if (!EAT('}')) { /* error heuristics */
454 while (MORE() && PEEK() != '}')
456 REQUIRE(MORE(), REG_EBRACE
);
465 if (!( c
== '*' || c
== '+' || c
== '?' ||
466 (c
== '{' && MORE2() && isdigit(PEEK2())) ) )
468 SETERROR(REG_BADRPT
);
472 - p_str - string (no metacharacters) "parser"
473 == static void p_str(register struct parse *p);
476 p_str(register struct parse
*p
)
478 REQUIRE(MORE(), REG_EMPTY
);
480 ordinary(p
, GETNEXT());
484 - p_bre - BRE parser top level, anchoring and concatenation
485 == static void p_bre(register struct parse *p, register int end1, \
486 == register int end2);
487 * Giving end1 as OUT essentially eliminates the end1/end2 check.
489 * This implementation is a bit of a kludge, in that a trailing $ is first
490 * taken as an ordinary character and then revised to be an anchor. The
491 * only undesirable side effect is that '$' gets included as a character
492 * category in such cases. This is fairly harmless; not worth fixing.
493 * The amount of lookahead needed to avoid this kludge is excessive.
496 p_bre(register struct parse
*p
, register int end1
, register int end2
)
498 /* first terminating character */
499 /* second terminating character */
501 register sopno start
= HERE();
502 register int first
= 1; /* first subexpression? */
503 register int wasdollar
= 0;
507 p
->g
->iflags
|= USEBOL
;
510 while (MORE() && !SEETWO(end1
, end2
)) {
511 wasdollar
= p_simp_re(p
, first
);
514 if (wasdollar
) { /* oops, that was a trailing anchor */
517 p
->g
->iflags
|= USEEOL
;
521 REQUIRE(HERE() != start
, REG_EMPTY
); /* require nonempty */
525 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
526 == static int p_simp_re(register struct parse *p, int starordinary);
528 static int /* was the simple RE an unbackslashed $? */
529 p_simp_re(register struct parse
*p
, int starordinary
)
531 /* is a leading * an ordinary character? */
538 register sopno subno
;
539 # define BACKSL (1<<RCHAR_BIT)
541 pos
= HERE(); /* repetion op, if any, covers from here */
543 assert(MORE()); /* caller should have ensured this */
546 REQUIRE(MORE(), REG_EESCAPE
);
547 c
= BACKSL
| (unsigned char)GETNEXT();
551 if (p
->g
->cflags
®_NEWLINE
)
560 SETERROR(REG_BADRPT
);
566 p
->pbegin
[subno
] = HERE();
567 EMIT(OLPAREN
, subno
);
568 /* the MORE here is an error heuristic */
569 if (MORE() && !SEETWO('\\', ')'))
571 if (subno
< NPAREN
) {
572 p
->pend
[subno
] = HERE();
573 assert(p
->pend
[subno
] != 0);
575 EMIT(ORPAREN
, subno
);
576 REQUIRE(EATTWO('\\', ')'), REG_EPAREN
);
578 case BACKSL
|')': /* should not get here -- must be user */
580 SETERROR(REG_EPAREN
);
591 i
= (c
&~BACKSL
) - '0';
593 if (p
->pend
[i
] != 0) {
594 assert(i
<= p
->g
->nsub
);
596 assert(p
->pbegin
[i
] != 0);
597 assert(OP(p
->strip
[p
->pbegin
[i
]]) == OLPAREN
);
598 assert(OP(p
->strip
[p
->pend
[i
]]) == ORPAREN
);
599 (void) dupl(p
, p
->pbegin
[i
]+1, p
->pend
[i
]);
602 SETERROR(REG_ESUBREG
);
606 REQUIRE(starordinary
, REG_BADRPT
);
609 ordinary(p
, c
&~ BACKSL
);
613 if (EAT('*')) { /* implemented as +? */
614 /* this case does not require the (y|) trick, noKLUDGE */
617 INSERT(OQUEST_
, pos
);
618 ASTERN(O_QUEST
, pos
);
619 } else if (EATTWO('\\', '{')) {
622 if (MORE() && isdigit(PEEK())) {
624 REQUIRE(count
<= count2
, REG_BADBR
);
625 } else /* single number with comma */
627 } else /* just a single number */
629 repeat(p
, pos
, count
, count2
);
630 if (!EATTWO('\\', '}')) { /* error heuristics */
631 while (MORE() && !SEETWO('\\', '}'))
633 REQUIRE(MORE(), REG_EBRACE
);
636 } else if (c
== (unsigned char)'$') /* $ (but not \$) ends it */
643 - p_count - parse a repetition count
644 == static int p_count(register struct parse *p);
646 static int /* the value */
647 p_count(register struct parse
*p
)
649 register int count
= 0;
650 register int ndigits
= 0;
652 while (MORE() && isdigit(PEEK()) && count
<= DUPMAX
) {
653 count
= count
*10 + (GETNEXT() - '0');
657 REQUIRE(ndigits
> 0 && count
<= DUPMAX
, REG_BADBR
);
662 - p_bracket - parse a bracketed character list
663 == static void p_bracket(register struct parse *p);
665 * Note a significant property of this code: if the allocset() did SETERROR,
666 * no set operations are done.
669 p_bracket(register struct parse
*p
)
672 register cset
*cs
= allocset(p
);
673 register int invert
= 0;
674 static RCHAR_T bow
[] = { '[', ':', '<', ':', ']', ']' };
675 static RCHAR_T eow
[] = { '[', ':', '>', ':', ']', ']' };
677 /* Dept of Truly Sickening Special-Case Kludges */
678 if (p
->next
+ 5 < p
->end
&& MEMCMP(p
->next
, bow
, 6) == 0) {
683 if (p
->next
+ 5 < p
->end
&& MEMCMP(p
->next
, eow
, 6) == 0) {
690 invert
++; /* make note to invert set at end */
695 while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
699 MUSTEAT(']', REG_EBRACK
);
701 if (p
->error
!= 0) /* don't mess things up further */
704 if (p
->g
->cflags
®_ICASE
) {
708 for (i
= p
->g
->csetsize
- 1; i
>= 0; i
--)
709 if (CHIN(cs
, i
) && isalpha(i
)) {
714 if (cs
->multis
!= NULL
)
720 for (i
= p
->g
->csetsize
- 1; i
>= 0; i
--)
725 if (p
->g
->cflags
®_NEWLINE
)
727 if (cs
->multis
!= NULL
)
731 assert(cs
->multis
== NULL
); /* xxx */
733 if (nch(p
, cs
) == 1) { /* optimize singleton sets */
734 ordinary(p
, firstch(p
, cs
));
737 EMIT(OANYOF
, freezeset(p
, cs
));
741 - p_b_term - parse one term of a bracketed character list
742 == static void p_b_term(register struct parse *p, register cset *cs);
745 p_b_term(register struct parse
*p
, register cset
*cs
)
748 register char start
, finish
;
751 /* classify what we've got */
752 switch ((MORE()) ? PEEK() : '\0') {
754 c
= (MORE2()) ? PEEK2() : '\0';
757 SETERROR(REG_ERANGE
);
758 return; /* NOTE RETURN */
766 case ':': /* character class */
768 REQUIRE(MORE(), REG_EBRACK
);
770 REQUIRE(c
!= '-' && c
!= ']', REG_ECTYPE
);
772 REQUIRE(MORE(), REG_EBRACK
);
773 REQUIRE(EATTWO(':', ']'), REG_ECTYPE
);
775 case '=': /* equivalence class */
777 REQUIRE(MORE(), REG_EBRACK
);
779 REQUIRE(c
!= '-' && c
!= ']', REG_ECOLLATE
);
781 REQUIRE(MORE(), REG_EBRACK
);
782 REQUIRE(EATTWO('=', ']'), REG_ECOLLATE
);
784 default: /* symbol, ordinary character, or range */
785 /* xxx revision needed for multichar stuff */
786 start
= p_b_symbol(p
);
787 if (SEE('-') && MORE2() && PEEK2() != ']') {
793 finish
= p_b_symbol(p
);
796 /* xxx what about signed chars here... */
797 REQUIRE(start
<= finish
, REG_ERANGE
);
798 for (i
= start
; i
<= finish
; i
++)
805 - p_b_cclass - parse a character-class name and deal with it
806 == static void p_b_cclass(register struct parse *p, register cset *cs);
809 p_b_cclass(register struct parse
*p
, register cset
*cs
)
811 register RCHAR_T
*sp
= p
->next
;
812 register struct cclass
*cp
;
817 while (MORE() && isalpha(PEEK()))
820 for (cp
= cclasses
; cp
->name
!= NULL
; cp
++)
821 if (STRLEN(cp
->name
) == len
&& MEMCMP(cp
->name
, sp
, len
))
823 if (cp
->name
== NULL
) {
824 /* oops, didn't find it */
825 SETERROR(REG_ECTYPE
);
830 while ((c
= *u
++) != '\0')
832 for (u
= cp
->multis
; *u
!= '\0'; u
+= strlen(u
) + 1)
837 - p_b_eclass - parse an equivalence-class name and deal with it
838 == static void p_b_eclass(register struct parse *p, register cset *cs);
840 * This implementation is incomplete. xxx
843 p_b_eclass(register struct parse
*p
, register cset
*cs
)
847 c
= p_b_coll_elem(p
, '=');
852 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
853 == static char p_b_symbol(register struct parse *p);
855 static char /* value of symbol */
856 p_b_symbol(register struct parse
*p
)
860 REQUIRE(MORE(), REG_EBRACK
);
861 if (!EATTWO('[', '.'))
864 /* collating symbol */
865 value
= p_b_coll_elem(p
, '.');
866 REQUIRE(EATTWO('.', ']'), REG_ECOLLATE
);
871 - p_b_coll_elem - parse a collating-element name and look it up
872 == static char p_b_coll_elem(register struct parse *p, int endc);
874 static char /* value of collating element */
875 p_b_coll_elem(register struct parse
*p
, int endc
)
877 /* name ended by endc,']' */
879 register RCHAR_T
*sp
= p
->next
;
880 register struct cname
*cp
;
884 while (MORE() && !SEETWO(endc
, ']'))
887 SETERROR(REG_EBRACK
);
891 for (cp
= cnames
; cp
->name
!= NULL
; cp
++)
892 if (STRLEN(cp
->name
) == len
&& MEMCMP(cp
->name
, sp
, len
))
893 return(cp
->code
); /* known name */
895 return(*sp
); /* single character */
896 SETERROR(REG_ECOLLATE
); /* neither */
901 - othercase - return the case counterpart of an alphabetic
902 == static char othercase(int ch);
904 static char /* if no counterpart, return ch */
910 else if (islower(ch
))
912 else /* peculiar, but could happen */
917 - bothcases - emit a dualcase version of a two-case character
918 == static void bothcases(register struct parse *p, int ch);
920 * Boy, is this implementation ever a kludge...
923 bothcases(register struct parse
*p
, int ch
)
925 register RCHAR_T
*oldnext
= p
->next
;
926 register RCHAR_T
*oldend
= p
->end
;
929 assert(othercase(ch
) != ch
); /* p_bracket() would recurse */
936 assert(p
->next
== bracket
+2);
942 - ordinary - emit an ordinary character
943 == static void ordinary(register struct parse *p, register int ch);
946 ordinary(register struct parse
*p
, register int ch
)
949 register cat_t *cap = p->g->categories;
952 if ((p
->g
->cflags
®_ICASE
) && isalpha(ch
) && othercase(ch
) != ch
)
955 EMIT(OCHAR
, (UCHAR_T
)ch
);
958 cap[ch] = p->g->ncategories++;
964 - nonnewline - emit REG_NEWLINE version of OANY
965 == static void nonnewline(register struct parse *p);
967 * Boy, is this implementation ever a kludge...
970 nonnewline(register struct parse
*p
)
972 register RCHAR_T
*oldnext
= p
->next
;
973 register RCHAR_T
*oldend
= p
->end
;
983 assert(p
->next
== bracket
+3);
989 - repeat - generate code for a bounded repetition, recursively if needed
990 == static void repeat(register struct parse *p, sopno start, int from, int to);
993 repeat(register struct parse
*p
, sopno start
, int from
, int to
)
995 /* operand from here to end of strip */
996 /* repeated from this number */
997 /* to this number of times (maybe INFINITY) */
999 register sopno finish
= HERE();
1002 # define REP(f, t) ((f)*8 + (t))
1003 # define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
1004 register sopno copy
;
1006 if (p
->error
!= 0) /* head off possible runaway recursion */
1011 switch (REP(MAP(from
), MAP(to
))) {
1012 case REP(0, 0): /* must be user doing this */
1013 DROP(finish
-start
); /* drop the operand */
1015 case REP(0, 1): /* as x{1,1}? */
1016 case REP(0, N
): /* as x{1,n}? */
1017 case REP(0, INF
): /* as x{1,}? */
1018 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1019 INSERT(OCH_
, start
); /* offset is wrong... */
1020 repeat(p
, start
+1, 1, to
);
1021 ASTERN(OOR1
, start
);
1022 AHEAD(start
); /* ... fix it */
1025 ASTERN(O_CH
, THERETHERE());
1027 case REP(1, 1): /* trivial case */
1030 case REP(1, N
): /* as x?x{1,n-1} */
1031 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1032 INSERT(OCH_
, start
);
1033 ASTERN(OOR1
, start
);
1035 EMIT(OOR2
, 0); /* offset very wrong... */
1036 AHEAD(THERE()); /* ...so fix it */
1037 ASTERN(O_CH
, THERETHERE());
1038 copy
= dupl(p
, start
+1, finish
+1);
1039 assert(copy
== finish
+4);
1040 repeat(p
, copy
, 1, to
-1);
1042 case REP(1, INF
): /* as x+ */
1043 INSERT(OPLUS_
, start
);
1044 ASTERN(O_PLUS
, start
);
1046 case REP(N
, N
): /* as xx{m-1,n-1} */
1047 copy
= dupl(p
, start
, finish
);
1048 repeat(p
, copy
, from
-1, to
-1);
1050 case REP(N
, INF
): /* as xx{n-1,INF} */
1051 copy
= dupl(p
, start
, finish
);
1052 repeat(p
, copy
, from
-1, to
);
1054 default: /* "can't happen" */
1055 SETERROR(REG_ASSERT
); /* just in case */
1061 - seterr - set an error condition
1062 == static int seterr(register struct parse *p, int e);
1064 static int /* useless but makes type checking happy */
1065 seterr(register struct parse
*p
, int e
)
1067 if (p
->error
== 0) /* keep earliest error condition */
1069 p
->next
= nuls
; /* try to bring things to a halt */
1071 return(0); /* make the return value well-defined */
1075 - allocset - allocate a set of characters for []
1076 == static cset *allocset(register struct parse *p);
1079 allocset(register struct parse
*p
)
1081 register int no
= p
->g
->ncsets
++;
1083 register size_t nbytes
;
1085 register size_t css
= (size_t)p
->g
->csetsize
;
1088 if (no
>= p
->ncsalloc
) { /* need another column of space */
1089 p
->ncsalloc
+= CHAR_BIT
;
1091 assert(nc
% CHAR_BIT
== 0);
1092 nbytes
= nc
/ CHAR_BIT
* css
;
1093 if (p
->g
->sets
== NULL
)
1094 p
->g
->sets
= (cset
*)malloc(nc
* sizeof(cset
));
1096 p
->g
->sets
= (cset
*)realloc((char *)p
->g
->sets
,
1098 if (p
->g
->setbits
== NULL
)
1099 p
->g
->setbits
= (uch
*)malloc(nbytes
);
1101 p
->g
->setbits
= (uch
*)realloc((char *)p
->g
->setbits
,
1103 /* xxx this isn't right if setbits is now NULL */
1104 for (i
= 0; i
< no
; i
++)
1105 p
->g
->sets
[i
].ptr
= p
->g
->setbits
+ css
*(i
/CHAR_BIT
);
1107 if (p
->g
->sets
!= NULL
&& p
->g
->setbits
!= NULL
)
1108 (void) memset((char *)p
->g
->setbits
+ (nbytes
- css
),
1112 SETERROR(REG_ESPACE
);
1113 /* caller's responsibility not to do set ops */
1117 assert(p
->g
->sets
!= NULL
); /* xxx */
1118 cs
= &p
->g
->sets
[no
];
1119 cs
->ptr
= p
->g
->setbits
+ css
*((no
)/CHAR_BIT
);
1120 cs
->mask
= 1 << ((no
) % CHAR_BIT
);
1129 - freeset - free a now-unused set
1130 == static void freeset(register struct parse *p, register cset *cs);
1133 freeset(register struct parse
*p
, register cset
*cs
)
1136 register cset
*top
= &p
->g
->sets
[p
->g
->ncsets
];
1137 register size_t css
= (size_t)p
->g
->csetsize
;
1139 for (i
= 0; i
< css
; i
++)
1141 if (cs
== top
-1) /* recover only the easy case */
1146 - freezeset - final processing on a set of characters
1147 == static int freezeset(register struct parse *p, register cset *cs);
1149 * The main task here is merging identical sets. This is usually a waste
1150 * of time (although the hash code minimizes the overhead), but can win
1151 * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash
1152 * is done using addition rather than xor -- all ASCII [aA] sets xor to
1155 static int /* set number */
1156 freezeset(register struct parse
*p
, register cset
*cs
)
1158 register uch h
= cs
->hash
;
1160 register cset
*top
= &p
->g
->sets
[p
->g
->ncsets
];
1162 register size_t css
= (size_t)p
->g
->csetsize
;
1164 /* look for an earlier one which is the same */
1165 for (cs2
= &p
->g
->sets
[0]; cs2
< top
; cs2
++)
1166 if (cs2
->hash
== h
&& cs2
!= cs
) {
1168 for (i
= 0; i
< css
; i
++)
1169 if (!!CHIN(cs2
, i
) != !!CHIN(cs
, i
))
1175 if (cs2
< top
) { /* found one */
1180 return((int)(cs
- p
->g
->sets
));
1184 - firstch - return first character in a set (which must have at least one)
1185 == static int firstch(register struct parse *p, register cset *cs);
1187 static int /* character; there is no "none" value */
1188 firstch(register struct parse
*p
, register cset
*cs
)
1191 register size_t css
= (size_t)p
->g
->csetsize
;
1193 for (i
= 0; i
< css
; i
++)
1197 return(0); /* arbitrary */
1201 - nch - number of characters in a set
1202 == static int nch(register struct parse *p, register cset *cs);
1205 nch(register struct parse
*p
, register cset
*cs
)
1208 register size_t css
= (size_t)p
->g
->csetsize
;
1211 for (i
= 0; i
< css
; i
++)
1218 - mcadd - add a collating element to a cset
1219 == static void mcadd(register struct parse *p, register cset *cs, \
1220 == register char *cp);
1223 mcadd(register struct parse
*p
, register cset
*cs
, register char *cp
)
1225 register size_t oldend
= cs
->smultis
;
1227 cs
->smultis
+= strlen(cp
) + 1;
1228 if (cs
->multis
== NULL
)
1229 cs
->multis
= malloc(cs
->smultis
);
1231 cs
->multis
= realloc(cs
->multis
, cs
->smultis
);
1232 if (cs
->multis
== NULL
) {
1233 SETERROR(REG_ESPACE
);
1237 (void) strcpy(cs
->multis
+ oldend
- 1, cp
);
1238 cs
->multis
[cs
->smultis
- 1] = '\0';
1242 - mcsub - subtract a collating element from a cset
1243 == static void mcsub(register cset *cs, register char *cp);
1246 mcsub(register cset
*cs
, register char *cp
)
1248 register char *fp
= mcfind(cs
, cp
);
1249 register size_t len
= strlen(fp
);
1252 (void) memmove(fp
, fp
+ len
+ 1,
1253 cs
->smultis
- (fp
+ len
+ 1 - cs
->multis
));
1256 if (cs
->smultis
== 0) {
1262 cs
->multis
= realloc(cs
->multis
, cs
->smultis
);
1263 assert(cs
->multis
!= NULL
);
1267 - mcin - is a collating element in a cset?
1268 == static int mcin(register cset *cs, register char *cp);
1271 mcin(register cset
*cs
, register char *cp
)
1273 return(mcfind(cs
, cp
) != NULL
);
1277 - mcfind - find a collating element in a cset
1278 == static char *mcfind(register cset *cs, register char *cp);
1281 mcfind(register cset
*cs
, register char *cp
)
1285 if (cs
->multis
== NULL
)
1287 for (p
= cs
->multis
; *p
!= '\0'; p
+= strlen(p
) + 1)
1288 if (strcmp(cp
, p
) == 0)
1294 - mcinvert - invert the list of collating elements in a cset
1295 == static void mcinvert(register struct parse *p, register cset *cs);
1297 * This would have to know the set of possibilities. Implementation
1301 mcinvert(register struct parse
*p
, register cset
*cs
)
1303 assert(cs
->multis
== NULL
); /* xxx */
1307 - mccase - add case counterparts of the list of collating elements in a cset
1308 == static void mccase(register struct parse *p, register cset *cs);
1310 * This would have to know the set of possibilities. Implementation
1314 mccase(register struct parse
*p
, register cset
*cs
)
1316 assert(cs
->multis
== NULL
); /* xxx */
1320 - isinsets - is this character in any sets?
1321 == static int isinsets(register struct re_guts *g, int c);
1323 static int /* predicate */
1324 isinsets(register struct re_guts
*g
, int c
)
1328 register int ncols
= (g
->ncsets
+(CHAR_BIT
-1)) / CHAR_BIT
;
1329 register unsigned uc
= (unsigned char)c
;
1331 for (i
= 0, col
= g
->setbits
; i
< ncols
; i
++, col
+= g
->csetsize
)
1338 - samesets - are these two characters in exactly the same sets?
1339 == static int samesets(register struct re_guts *g, int c1, int c2);
1341 static int /* predicate */
1342 samesets(register struct re_guts
*g
, int c1
, int c2
)
1346 register int ncols
= (g
->ncsets
+(CHAR_BIT
-1)) / CHAR_BIT
;
1347 register unsigned uc1
= (unsigned char)c1
;
1348 register unsigned uc2
= (unsigned char)c2
;
1350 for (i
= 0, col
= g
->setbits
; i
< ncols
; i
++, col
+= g
->csetsize
)
1351 if (col
[uc1
] != col
[uc2
])
1357 - categorize - sort out character categories
1358 == static void categorize(struct parse *p, register struct re_guts *g);
1361 categorize(struct parse
*p
, register struct re_guts
*g
)
1364 register cat_t *cats = g->categories;
1370 /* avoid making error situations worse */
1375 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
1376 if (cats[c] == 0 && isinsets(g, c)) {
1377 cat = g->ncategories++;
1379 for (c2 = c+1; c2 <= CHAR_MAX; c2++)
1380 if (cats[c2] == 0 && samesets(g, c, c2))
1387 - dupl - emit a duplicate of a bunch of sops
1388 == static sopno dupl(register struct parse *p, sopno start, sopno finish);
1390 static sopno
/* start of duplicate */
1391 dupl(register struct parse
*p
, sopno start
, sopno finish
)
1394 /* to this less one */
1396 register sopno ret
= HERE();
1397 register sopno len
= finish
- start
;
1399 assert(finish
>= start
);
1402 enlarge(p
, p
->ssize
+ len
); /* this many unexpected additions */
1403 assert(p
->ssize
>= p
->slen
+ len
);
1404 (void) memcpy((char *)(p
->strip
+ p
->slen
),
1405 (char *)(p
->strip
+ start
), (size_t)len
*sizeof(sop
));
1411 - doemit - emit a strip operator
1412 == static void doemit(register struct parse *p, sop op, size_t opnd);
1414 * It might seem better to implement this as a macro with a function as
1415 * hard-case backup, but it's just too big and messy unless there are
1416 * some changes to the data structures. Maybe later.
1419 doemit(register struct parse
*p
, sop op
, size_t opnd
)
1421 /* avoid making error situations worse */
1425 /* deal with oversize operands ("can't happen", more or less) */
1426 assert(opnd
< 1<<OPSHIFT
);
1428 /* deal with undersized strip */
1429 if (p
->slen
>= p
->ssize
)
1430 enlarge(p
, (p
->ssize
+1) / 2 * 3); /* +50% */
1431 assert(p
->slen
< p
->ssize
);
1433 /* finally, it's all reduced to the easy case */
1434 p
->strip
[p
->slen
++] = SOP(op
, opnd
);
1438 - doinsert - insert a sop into the strip
1439 == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos);
1442 doinsert(register struct parse
*p
, sop op
, size_t opnd
, sopno pos
)
1448 /* avoid making error situations worse */
1453 EMIT(op
, opnd
); /* do checks, ensure space */
1454 assert(HERE() == sn
+1);
1457 /* adjust paren pointers */
1459 for (i
= 1; i
< NPAREN
; i
++) {
1460 if (p
->pbegin
[i
] >= pos
) {
1463 if (p
->pend
[i
] >= pos
) {
1468 memmove((char *)&p
->strip
[pos
+1], (char *)&p
->strip
[pos
],
1469 (HERE()-pos
-1)*sizeof(sop
));
1474 - dofwd - complete a forward reference
1475 == static void dofwd(register struct parse *p, sopno pos, sop value);
1478 dofwd(register struct parse
*p
, register sopno pos
, sop value
)
1480 /* avoid making error situations worse */
1484 assert(value
< 1<<OPSHIFT
);
1485 p
->strip
[pos
] = OP(p
->strip
[pos
]) | value
;
1489 - enlarge - enlarge the strip
1490 == static void enlarge(register struct parse *p, sopno size);
1493 enlarge(register struct parse
*p
, register sopno size
)
1497 if (p
->ssize
>= size
)
1500 sp
= (sop
*)realloc(p
->strip
, size
*sizeof(sop
));
1502 SETERROR(REG_ESPACE
);
1510 - stripsnug - compact the strip
1511 == static void stripsnug(register struct parse *p, register struct re_guts *g);
1514 stripsnug(register struct parse
*p
, register struct re_guts
*g
)
1516 g
->nstates
= p
->slen
;
1517 g
->strip
= (sop
*)realloc((char *)p
->strip
, p
->slen
* sizeof(sop
));
1518 if (g
->strip
== NULL
) {
1519 SETERROR(REG_ESPACE
);
1520 g
->strip
= p
->strip
;
1525 - findmust - fill in must and mlen with longest mandatory literal string
1526 == static void findmust(register struct parse *p, register struct re_guts *g);
1528 * This algorithm could do fancy things like analyzing the operands of |
1529 * for common subsequences. Someday. This code is simple and finds most
1530 * of the interesting cases.
1532 * Note that must and mlen got initialized during setup.
1535 findmust(struct parse
*p
, register struct re_guts
*g
)
1539 register sop
*newstart
;
1540 register sopno newlen
;
1542 register RCHAR_T
*cp
;
1545 /* avoid making error situations worse */
1549 /* find the longest OCHAR sequence in strip */
1551 scan
= g
->strip
+ 1;
1555 case OCHAR
: /* sequence member */
1556 if (newlen
== 0) /* new sequence */
1557 newstart
= scan
- 1;
1560 case OPLUS_
: /* things that don't break one */
1564 case OQUEST_
: /* things that must be skipped */
1570 /* assert() interferes w debug printouts */
1571 if (OP(s
) != O_QUEST
&& OP(s
) != O_CH
&&
1576 } while (OP(s
) != O_QUEST
&& OP(s
) != O_CH
);
1578 default: /* things that break a sequence */
1579 if (newlen
> g
->mlen
) { /* ends one */
1586 } while (OP(s
) != OEND
);
1588 if (g
->mlen
== 0) /* there isn't one */
1591 /* turn it into a character string */
1592 g
->must
= malloc(((size_t)g
->mlen
+ 1) * sizeof(RCHAR_T
));
1593 if (g
->must
== NULL
) { /* argh; just forget it */
1599 for (i
= g
->mlen
; i
> 0; i
--) {
1600 while (OP(s
= *scan
++) != OCHAR
)
1602 assert(cp
< g
->must
+ g
->mlen
);
1603 *cp
++ = (RCHAR_T
)OPND(s
);
1605 assert(cp
== g
->must
+ g
->mlen
);
1606 *cp
++ = '\0'; /* just on general principles */
1610 - pluscount - count + nesting
1611 == static sopno pluscount(register struct parse *p, register struct re_guts *g);
1613 static sopno
/* nesting depth */
1614 pluscount(struct parse
*p
, register struct re_guts
*g
)
1618 register sopno plusnest
= 0;
1619 register sopno maxnest
= 0;
1622 return(0); /* there may not be an OEND */
1624 scan
= g
->strip
+ 1;
1632 if (plusnest
> maxnest
)
1637 } while (OP(s
) != OEND
);