1 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
2 * confused with the original package (see point 3 below). Thanks, Henry!
5 /* Additional note: this code is very heavily munged from Henry's version
6 * in places. In some spots I've traded clarity for efficiency, so don't
7 * blame Henry for some of the lack of readability.
10 /* $RCSfile: regcomp.c,v $$Revision: 4.0.1.1 $$Date: 91/04/12 09:04:45 $
13 * Revision 4.0.1.1 91/04/12 09:04:45 lwall
14 * patch1: random cleanup in cpp namespace
16 * Revision 4.0 91/03/20 01:39:01 lwall
22 * regcomp and regexec -- regsub and regerror are not used in perl
24 * Copyright (c) 1986 by University of Toronto.
25 * Written by Henry Spencer. Not derived from licensed software.
27 * Permission is granted to anyone to use this software for any
28 * purpose on any computer system, and to redistribute it freely,
29 * subject to the following restrictions:
31 * 1. The author is not responsible for the consequences of use of
32 * this software, no matter how awful, even if they arise
35 * 2. The origin of this software must not be misrepresented, either
36 * by explicit claim or by omission.
38 * 3. Altered versions must be plainly marked as such, and must not
39 * be misrepresented as being the original software.
42 **** Alterations to Henry's code are...
44 **** Copyright (c) 1989, Larry Wall
46 **** You may distribute under the terms of the GNU General Public License
47 **** as specified in the README file that comes with the perl 3.0 kit.
49 * Beware that some of this code is subtly aware of the way operator
50 * precedence is structured in regular expressions. Serious changes in
51 * regular-expression syntax might require a total rethink.
59 # if defined(BUGGY_MSC6)
60 /* MSC 6.00A breaks on op/regexp.t test 85 unless we turn this off */
61 # pragma optimize("a",off)
62 /* But MSC 6.00A is happy with 'w', for aliases only across function calls*/
63 # pragma optimize("w",on )
64 # endif /* BUGGY_MSC6 */
71 #define ISMULT1(c) ((c) == '*' || (c) == '+' || (c) == '?')
72 #define ISMULT2(s) ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
73 ((*s) == '{' && regcurly(s)))
74 #define META "^$.[()|?+*\\"
77 #undef SPSTART /* dratted cpp namespace... */
80 * Flags to be passed up and down.
82 #define HASWIDTH 01 /* Known never to match null string. */
83 #define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */
84 #define SPSTART 04 /* Starts with * or +. */
85 #define WORST 0 /* Worst case. */
88 * Global work variables for regcomp().
90 static char *regprecomp; /* uncompiled string. */
91 static char *regparse; /* Input-scan pointer. */
92 static char *regxend; /* End of input for compile */
93 static int regnpar; /* () count. */
94 static char *regcode; /* Code-emit pointer; ®dummy = don't. */
95 static long regsize; /* Code size. */
97 static int regsawbracket; /* Did we do {d,d} trick? */
100 * Forward declarations for regcomp()'s friends.
102 STATIC int regcurly();
104 STATIC char *regbranch();
105 STATIC char *regpiece();
106 STATIC char *regatom();
107 STATIC char *regclass();
108 STATIC char *regnode();
109 STATIC char *reganode();
111 STATIC void reginsert();
112 STATIC void regtail();
113 STATIC void regoptail();
116 - regcomp - compile a regular expression into internal code
118 * We can't allocate space until we know how big the compiled form will be,
119 * but we can't compile it (and thus know how big it is) until we've got a
120 * place to put the code. So we cheat: we compile it twice, once with code
121 * generation turned off and size counting turned on, and once "for real".
122 * This also means that we don't allocate space until we are sure that the
123 * thing really will compile successfully, and we never have to move the
124 * code and thus invalidate pointers into it. (Note that it has to be in
125 * one piece because free() must be able to free it all.) [NB: not true in perl]
127 * Beware that the optimization-preparation code in here knows about some
128 * of the structure of the compiled regexp. [I'll say.]
131 regcomp(exp,xend,fold)
138 register STR *longish;
141 register char *first;
146 extern char *safemalloc();
147 extern char *savestr();
151 fatal("NULL regexp argument");
153 /* First pass: determine size, legality. */
157 regprecomp = nsavestr(exp,xend-exp);
163 if (reg(0, &flags) == NULL) {
164 Safefree(regprecomp);
169 /* Small enough for pointer-storage convention? */
170 if (regsize >= 32767L) /* Probably could be 65535L. */
171 FAIL("regexp too big");
173 /* Allocate space. */
174 Newc(1001, r, sizeof(regexp) + (unsigned)regsize, char, regexp);
176 FAIL("regexp out of space");
178 /* Second pass: emit code. */
180 bcopy(regprecomp,exp,xend-exp);
181 r->precomp = regprecomp;
185 regcode = r->program;
187 if (reg(0, &flags) == NULL)
190 /* Dig out information for optimizations. */
191 r->regstart = Nullstr; /* Worst-case defaults. */
193 r->regmust = Nullstr;
195 r->regstclass = Nullch;
196 scan = r->program+1; /* First BRANCH. */
197 if (OP(regnext(scan)) == END) {/* Only one top-level choice. */
198 scan = NEXTOPER(scan);
201 while (OP(first) == OPEN ||
202 (OP(first) == BRANCH && OP(regnext(first)) != BRANCH) ||
203 (OP(first) == PLUS) ||
204 (OP(first) == CURLY && ARG1(first) > 0) ) {
205 if (OP(first) == PLUS)
208 first += regarglen[OP(first)];
209 first = NEXTOPER(first);
212 /* Starting-point info. */
213 if (OP(first) == EXACTLY) {
215 str_make(OPERAND(first)+1,*OPERAND(first));
216 if (r->regstart->str_cur > !(sawstudy|fold))
217 fbmcompile(r->regstart,fold);
219 else if ((exp = index(simple,OP(first))) && exp > simple)
220 r->regstclass = first;
221 else if (OP(first) == BOUND || OP(first) == NBOUND)
222 r->regstclass = first;
223 else if (OP(first) == BOL ||
224 (OP(first) == STAR && OP(NEXTOPER(first)) == ANY) )
225 r->reganch = 1; /* kinda turn .* into ^.* */
226 r->reganch |= sawplus;
230 fprintf(stderr,"first %d next %d offset %d\n",
231 OP(first), OP(NEXTOPER(first)), first - scan);
234 * If there's something expensive in the r.e., find the
235 * longest literal string that must appear and make it the
236 * regmust. Resolve ties in favor of later strings, since
237 * the regstart check works with the beginning of the r.e.
238 * and avoiding duplication strengthens checking. Not a
239 * strong reason, but sufficient in the absence of others.
240 * [Now we resolve ties in favor of the earlier string if
241 * it happens that curback has been invalidated, since the
242 * earlier string may buy us something the later one won't.]
244 longish = str_make("",0);
245 longest = str_make("",0);
250 while (OP(scan) != END) {
251 if (OP(scan) == BRANCH) {
252 if (OP(regnext(scan)) == BRANCH) {
254 while (OP(scan) == BRANCH)
255 scan = regnext(scan);
257 else /* single branch is ok */
258 scan = NEXTOPER(scan);
260 if (OP(scan) == EXACTLY) {
264 while (OP(t = regnext(scan)) == CLOSE)
266 if (curback - backish == len) {
267 str_ncat(longish, OPERAND(first)+1,
269 len += *OPERAND(first);
270 curback += *OPERAND(first);
271 first = regnext(scan);
273 else if (*OPERAND(first) >= len + (curback >= 0)) {
274 len = *OPERAND(first);
275 str_nset(longish, OPERAND(first)+1,len);
278 first = regnext(scan);
281 curback += *OPERAND(first);
283 else if (index(varies,OP(scan))) {
286 if (longish->str_cur > longest->str_cur) {
287 str_sset(longest,longish);
290 str_nset(longish,"",0);
292 else if (index(simple,OP(scan))) {
295 if (longish->str_cur > longest->str_cur) {
296 str_sset(longest,longish);
299 str_nset(longish,"",0);
301 scan = regnext(scan);
304 /* Prefer earlier on tie, unless we can tail match latter */
306 if (longish->str_cur + (OP(first) == EOL) > longest->str_cur) {
307 str_sset(longest,longish);
311 str_nset(longish,"",0);
316 !fbminstr(r->regstart->str_ptr,
317 r->regstart->str_ptr + r->regstart->str_cur,
322 r->regmust = longest;
325 r->regback = backest;
327 > !(sawstudy || fold || OP(first) == EOL) )
328 fbmcompile(r->regmust,fold);
329 r->regmust->str_u.str_useful = 100;
330 if (OP(first) == EOL && longish->str_cur)
331 r->regmust->str_pok |= SP_TAIL;
340 r->do_folding = fold;
341 r->nparens = regnpar - 1;
342 New(1002, r->startp, regnpar, char*);
343 New(1002, r->endp, regnpar, char*);
352 - reg - regular expression, i.e. main body or parenthesized thing
354 * Caller must absorb opening parenthesis.
356 * Combining parenthesis handling with the base level of regular expression
357 * is a trifle forced, but the need to tie the tails of the branches to what
358 * follows makes it hard to avoid.
362 int paren; /* Parenthesized? */
367 register char *ender;
371 *flagp = HASWIDTH; /* Tentatively. */
373 /* Make an OPEN node, if parenthesized. */
377 ret = reganode(OPEN, parno);
381 /* Pick up the branches, linking them together. */
382 br = regbranch(&flags);
386 regtail(ret, br); /* OPEN -> first. */
389 if (!(flags&HASWIDTH))
391 *flagp |= flags&SPSTART;
392 while (*regparse == '|') {
394 br = regbranch(&flags);
397 regtail(ret, br); /* BRANCH -> BRANCH. */
398 if (!(flags&HASWIDTH))
400 *flagp |= flags&SPSTART;
403 /* Make a closing node, and hook it on the end. */
405 ender = reganode(CLOSE, parno);
407 ender = regnode(END);
410 /* Hook the tails of the branches to the closing node. */
411 for (br = ret; br != NULL; br = regnext(br))
412 regoptail(br, ender);
414 /* Check for proper termination. */
415 if (paren && *regparse++ != ')') {
416 FAIL("unmatched () in regexp");
417 } else if (!paren && regparse < regxend) {
418 if (*regparse == ')') {
419 FAIL("unmatched () in regexp");
421 FAIL("junk on end of regexp"); /* "Can't happen". */
429 - regbranch - one alternative of an | operator
431 * Implements the concatenation operator.
438 register char *chain;
439 register char *latest;
442 *flagp = WORST; /* Tentatively. */
444 ret = regnode(BRANCH);
446 while (regparse < regxend && *regparse != '|' && *regparse != ')') {
447 latest = regpiece(&flags);
450 *flagp |= flags&HASWIDTH;
451 if (chain == NULL) /* First piece. */
452 *flagp |= flags&SPSTART;
454 regtail(chain, latest);
457 if (chain == NULL) /* Loop ran zero times. */
458 (void) regnode(NOTHING);
464 - regpiece - something followed by possible [*+?]
466 * Note that the branching code sequences used for ? and the general cases
467 * of * and + are somewhat optimized: they use the same NOTHING node as
468 * both the endmarker for their branch list and the body of the last branch.
469 * It might seem that this node could be dispensed with entirely, but the
470 * endmarker role is not redundant.
480 char *origparse = regparse;
481 int orignpar = regnpar;
486 ret = regatom(&flags);
492 /* Here's a total kludge: if after the atom there's a {\d+,?\d*}
493 * then we decrement the first number by one and reset our
494 * parsing back to the beginning of the same atom. If the first number
495 * is down to 0, decrement the second number instead and fake up
496 * a ? after it. Given the way this compiler doesn't keep track
497 * of offsets on the first pass, this is the only way to replicate
498 * a piece of code. Sigh.
500 if (op == '{' && regcurly(regparse)) {
503 while (isdigit(*next) || *next == ',') {
512 if (*next == '}') { /* got one */
516 iter = atoi(regparse);
517 if (flags&SIMPLE) { /* we can do it right after all */
520 reginsert(CURLY, ret);
522 *flagp = (WORST|HASWIDTH);
528 if (tmp && tmp < iter)
529 fatal("Can't do {n,m} with n > m");
530 if (regcode != ®dummy) {
532 *(unsigned short *)(ret+3) = iter;
533 *(unsigned short *)(ret+5) = tmp;
535 ret[3] = iter >> 8; ret[4] = iter & 0377;
536 ret[5] = tmp >> 8; ret[6] = tmp & 0377;
542 regsawbracket++; /* remember we clobbered exp */
545 sprintf(regparse,"%.*d", max-regparse, iter - 1);
547 if (*max == ',' && max[1] != '}') {
548 if (atoi(max+1) <= 0)
549 fatal("Can't do {n,m} with n > m");
551 sprintf(max+1,"%.*d", next-(max+1), atoi(max+1) - 1);
554 if (iter != 1 || *max == ',') {
555 regparse = origparse; /* back up input pointer */
556 regnpar = orignpar; /* don't make more parens */
568 if (max == next) { /* any number more? */
570 op = '*'; /* fake up one with a star */
573 op = '?'; /* fake up optional atom */
575 sprintf(max,"%.*d", next-max, iter - 1);
580 regparse = origparse - 1; /* offset ++ below */
585 fatal("Can't do {n,0}");
588 fatal("Can't do {0}");
597 if (!(flags&HASWIDTH) && op != '?')
598 FAIL("regexp *+ operand could be empty");
599 *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
601 if (op == '*' && (flags&SIMPLE))
602 reginsert(STAR, ret);
603 else if (op == '*') {
604 /* Emit x* as (x&|), where & means "self". */
605 reginsert(BRANCH, ret); /* Either x */
606 regoptail(ret, regnode(BACK)); /* and loop */
607 regoptail(ret, ret); /* back */
608 regtail(ret, regnode(BRANCH)); /* or */
609 regtail(ret, regnode(NOTHING)); /* null. */
610 } else if (op == '+' && (flags&SIMPLE))
611 reginsert(PLUS, ret);
612 else if (op == '+') {
613 /* Emit x+ as x(&|), where & means "self". */
614 next = regnode(BRANCH); /* Either */
616 regtail(regnode(BACK), ret); /* loop back */
617 regtail(next, regnode(BRANCH)); /* or */
618 regtail(ret, regnode(NOTHING)); /* null. */
619 } else if (op == '?') {
620 /* Emit x? as (x|) */
621 reginsert(BRANCH, ret); /* Either x */
622 regtail(ret, regnode(BRANCH)); /* or */
623 next = regnode(NOTHING); /* null. */
625 regoptail(ret, next);
629 if (ISMULT2(regparse))
630 FAIL("nested *?+ in regexp");
636 - regatom - the lowest level
638 * Optimization: gobbles an entire sequence of ordinary characters so that
639 * it can turn them into a single node, which is smaller to store and
640 * faster to run. Backslashed characters are exceptions, each becoming a
641 * separate node; the code is simpler that way and it's not worth fixing.
643 * [Yes, it is worth fixing, some scripts can run twice the speed.]
652 *flagp = WORST; /* Tentatively. */
654 switch (*regparse++) {
663 *flagp |= HASWIDTH|SIMPLE;
667 *flagp |= HASWIDTH|SIMPLE;
670 ret = reg(1, &flags);
673 *flagp |= flags&(HASWIDTH|SPSTART);
677 FAIL("internal urp in regexp"); /* Supposed to be caught earlier. */
682 FAIL("?+* follows nothing in regexp");
687 ret = regnode(ALNUM);
688 *flagp |= HASWIDTH|SIMPLE;
692 ret = regnode(NALNUM);
693 *flagp |= HASWIDTH|SIMPLE;
697 ret = regnode(BOUND);
702 ret = regnode(NBOUND);
707 ret = regnode(SPACE);
708 *flagp |= HASWIDTH|SIMPLE;
712 ret = regnode(NSPACE);
713 *flagp |= HASWIDTH|SIMPLE;
717 ret = regnode(DIGIT);
718 *flagp |= HASWIDTH|SIMPLE;
722 ret = regnode(NDIGIT);
723 *flagp |= HASWIDTH|SIMPLE;
736 case '1': case '2': case '3': case '4':
737 case '5': case '6': case '7': case '8': case '9':
739 int num = atoi(regparse);
741 if (num > 9 && num >= regnpar)
744 ret = reganode(REF, num);
745 while (isascii(*regparse) && isdigit(*regparse))
752 if (regparse >= regxend)
753 FAIL("trailing \\ in regexp");
767 ret = regnode(EXACTLY);
768 regc(0); /* save spot for len */
769 for (len=0, p=regparse-1;
770 len < 127 && p < regxend;
820 ender = scanhex(++p, 2, &numlen);
827 ender = toupper(ender);
830 case '0': case '1': case '2': case '3':case '4':
831 case '5': case '6': case '7': case '8':case '9':
833 (isdigit(p[1]) && atoi(p) >= regnpar) ) {
834 ender = scanoct(p, 3, &numlen);
844 FAIL("trailing \\ in regexp");
855 if (regfold && isupper(ender))
856 ender = tolower(ender);
857 if (ISMULT2(p)) { /* Back off on ?+*. */
871 FAIL("internal disaster in regexp");
875 if (regcode != ®dummy)
891 if (regcode == ®dummy)
895 bits[c >> 3] &= ~(1 << (c & 7));
897 bits[c >> 3] |= (1 << (c & 7));
905 register int lastclass;
906 register int range = 0;
911 ret = regnode(ANYOF);
912 if (*regparse == '^') { /* Complement of range. */
919 for (class = 0; class < 32; class++)
921 if (*regparse == ']' || *regparse == '-')
922 goto skipcond; /* allow 1st char to be ] or - */
923 while (regparse < regxend && *regparse != ']') {
925 class = UCHARAT(regparse++);
927 class = UCHARAT(regparse++);
930 for (class = 'a'; class <= 'z'; class++)
931 regset(bits,def,class);
932 for (class = 'A'; class <= 'Z'; class++)
933 regset(bits,def,class);
934 for (class = '0'; class <= '9'; class++)
935 regset(bits,def,class);
936 regset(bits,def,'_');
940 regset(bits,def,' ');
941 regset(bits,def,'\t');
942 regset(bits,def,'\r');
943 regset(bits,def,'\f');
944 regset(bits,def,'\n');
948 for (class = '0'; class <= '9'; class++)
949 regset(bits,def,class);
974 class = scanhex(regparse, 2, &numlen);
980 class = toupper(class);
983 case '0': case '1': case '2': case '3': case '4':
984 case '5': case '6': case '7': case '8': case '9':
985 class = scanoct(--regparse, 3, &numlen);
991 if (lastclass > class)
992 FAIL("invalid [] range in regexp");
997 if (*regparse == '-' && regparse+1 < regxend &&
998 regparse[1] != ']') {
1001 continue; /* do it next time */
1004 for ( ; lastclass <= class; lastclass++) {
1005 regset(bits,def,lastclass);
1006 if (regfold && isupper(lastclass))
1007 regset(bits,def,tolower(lastclass));
1011 if (*regparse != ']')
1012 FAIL("unmatched [] in regexp");
1018 - regnode - emit a node
1020 static char * /* Location. */
1028 if (ret == ®dummy) {
1039 if (!((long)ret & 1))
1045 *ptr++ = '\0'; /* Null "next" pointer. */
1053 - reganode - emit a node with an argument
1055 static char * /* Location. */
1064 if (ret == ®dummy) {
1075 if (!((long)ret & 1))
1081 *ptr++ = '\0'; /* Null "next" pointer. */
1084 *(unsigned short *)(ret+3) = arg;
1086 ret[3] = arg >> 8; ret[4] = arg & 0377;
1095 - regc - emit (if appropriate) a byte of code
1101 if (regcode != ®dummy)
1108 - reginsert - insert an operator in front of already-emitted operand
1110 * Means relocating the operand.
1119 register char *place;
1120 register offset = (op == CURLY ? 4 : 0);
1122 if (regcode == ®dummy) {
1124 regsize += 4 + offset;
1126 regsize += 3 + offset;
1133 regcode += 4 + offset;
1135 regcode += 3 + offset;
1141 place = opnd; /* Op node, where operand used to be. */
1145 while (offset-- > 0)
1150 - regtail - set the next-pointer at the end of a node chain
1157 register char *scan;
1158 register char *temp;
1159 register int offset;
1164 /* Find last node. */
1167 temp = regnext(scan);
1174 offset = val - scan;
1176 *(short*)(scan+1) = offset;
1181 if (OP(scan) == BACK)
1182 offset = scan - val;
1184 offset = val - scan;
1185 *(scan+1) = (offset>>8)&0377;
1186 *(scan+2) = offset&0377;
1191 - regoptail - regtail on operand of first argument; nop if operandless
1198 /* "Operandless" and "op != BRANCH" are synonymous in practice. */
1199 if (p == NULL || p == ®dummy || OP(p) != BRANCH)
1201 regtail(NEXTOPER(p), val);
1205 - regcurly - a little FSA that accepts {\d+,?\d*}
1229 - regdump - dump a regexp onto stderr in vaguely comprehensible form
1236 register char op = EXACTLY; /* Arbitrary non-END op. */
1237 register char *next;
1241 while (op != END) { /* While that wasn't END last time... */
1247 fprintf(stderr,"%2d%s", s-r->program, regprop(s)); /* Where, what. */
1250 if (next == NULL) /* Next ptr. */
1251 fprintf(stderr,"(0)");
1253 fprintf(stderr,"(%d)", (s-r->program)+(next-s));
1258 if (op == EXACTLY) {
1259 /* Literal string, where present. */
1261 while (*s != '\0') {
1267 (void)putchar('\n');
1270 /* Header fields of interest. */
1272 fprintf(stderr,"start `%s' ", r->regstart->str_ptr);
1274 fprintf(stderr,"stclass `%s' ", regprop(r->regstclass));
1276 fprintf(stderr,"anchored ");
1278 fprintf(stderr,"plus ");
1279 if (r->regmust != NULL)
1280 fprintf(stderr,"must have \"%s\" back %d ", r->regmust->str_ptr,
1282 fprintf(stderr,"\n");
1286 - regprop - printable representation of opcode
1294 (void) strcpy(buf, ":");
1349 (void)sprintf(buf+strlen(buf), "CURLY {%d,%d}",
1354 (void)sprintf(buf+strlen(buf), "REF%d", ARG1(op));
1358 (void)sprintf(buf+strlen(buf), "OPEN%d", ARG1(op));
1362 (void)sprintf(buf+strlen(buf), "CLOSE%d", ARG1(op));
1372 FAIL("corrupted regexp opcode");
1375 (void) strcat(buf, p);
1378 #endif /* DEBUGGING */
1384 Safefree(r->precomp);
1385 r->precomp = Nullch;
1388 Safefree(r->subbase);
1389 r->subbase = Nullch;
1392 str_free(r->regmust);
1393 r->regmust = Nullstr;
1396 str_free(r->regstart);
1397 r->regstart = Nullstr;
1399 Safefree(r->startp);