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 /* $Header: regcomp.c,v 3.0 89/10/18 15:22:29 lwall Locked $
13 * Revision 3.0 89/10/18 15:22:29 lwall
19 * regcomp and regexec -- regsub and regerror are not used in perl
21 * Copyright (c) 1986 by University of Toronto.
22 * Written by Henry Spencer. Not derived from licensed software.
24 * Permission is granted to anyone to use this software for any
25 * purpose on any computer system, and to redistribute it freely,
26 * subject to the following restrictions:
28 * 1. The author is not responsible for the consequences of use of
29 * this software, no matter how awful, even if they arise
32 * 2. The origin of this software must not be misrepresented, either
33 * by explicit claim or by omission.
35 * 3. Altered versions must be plainly marked as such, and must not
36 * be misrepresented as being the original software.
39 **** Alterations to Henry's code are...
41 **** Copyright (c) 1989, Larry Wall
43 **** You may distribute under the terms of the GNU General Public License
44 **** as specified in the README file that comes with the perl 3.0 kit.
46 * Beware that some of this code is subtly aware of the way operator
47 * precedence is structured in regular expressions. Serious changes in
48 * regular-expression syntax might require a total rethink.
59 #define ISMULT1(c) ((c) == '*' || (c) == '+' || (c) == '?')
60 #define ISMULT2(s) ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
61 ((*s) == '{' && regcurly(s)))
62 #define META "^$.[()|?+*\\"
65 * Flags to be passed up and down.
67 #define HASWIDTH 01 /* Known never to match null string. */
68 #define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */
69 #define SPSTART 04 /* Starts with * or +. */
70 #define WORST 0 /* Worst case. */
73 * Global work variables for regcomp().
75 static char *regprecomp; /* uncompiled string. */
76 static char *regparse; /* Input-scan pointer. */
77 static char *regxend; /* End of input for compile */
78 static int regnpar; /* () count. */
79 static char *regcode; /* Code-emit pointer; ®dummy = don't. */
80 static long regsize; /* Code size. */
82 static int regsawbracket; /* Did we do {d,d} trick? */
85 * Forward declarations for regcomp()'s friends.
87 STATIC int regcurly();
89 STATIC char *regbranch();
90 STATIC char *regpiece();
91 STATIC char *regatom();
92 STATIC char *regclass();
93 STATIC char *regnode();
95 STATIC void reginsert();
96 STATIC void regtail();
97 STATIC void regoptail();
100 - regcomp - compile a regular expression into internal code
102 * We can't allocate space until we know how big the compiled form will be,
103 * but we can't compile it (and thus know how big it is) until we've got a
104 * place to put the code. So we cheat: we compile it twice, once with code
105 * generation turned off and size counting turned on, and once "for real".
106 * This also means that we don't allocate space until we are sure that the
107 * thing really will compile successfully, and we never have to move the
108 * code and thus invalidate pointers into it. (Note that it has to be in
109 * one piece because free() must be able to free it all.) [NB: not true in perl]
111 * Beware that the optimization-preparation code in here knows about some
112 * of the structure of the compiled regexp. [I'll say.]
115 regcomp(exp,xend,fold,rare)
123 register STR *longest;
125 register char *first;
129 extern char *safemalloc();
130 extern char *savestr();
133 fatal("NULL regexp argument");
135 /* First pass: determine size, legality. */
139 regprecomp = nsavestr(exp,xend-exp);
145 if (reg(0, &flags) == NULL) {
146 Safefree(regprecomp);
150 /* Small enough for pointer-storage convention? */
151 if (regsize >= 32767L) /* Probably could be 65535L. */
152 FAIL("regexp too big");
154 /* Allocate space. */
155 Newc(1001, r, sizeof(regexp) + (unsigned)regsize, char, regexp);
157 FAIL("regexp out of space");
159 /* Second pass: emit code. */
161 bcopy(regprecomp,exp,xend-exp);
162 r->precomp = regprecomp;
166 regcode = r->program;
168 if (reg(0, &flags) == NULL)
171 /* Dig out information for optimizations. */
172 r->regstart = Nullstr; /* Worst-case defaults. */
174 r->regmust = Nullstr;
176 r->regstclass = Nullch;
177 scan = r->program+1; /* First BRANCH. */
178 if (OP(regnext(scan)) == END) {/* Only one top-level choice. */
179 scan = NEXTOPER(scan);
182 while ((OP(first) > OPEN && OP(first) < CLOSE) ||
183 (OP(first) == BRANCH && OP(regnext(first)) != BRANCH) ||
184 (OP(first) == PLUS) )
185 first = NEXTOPER(first);
187 /* Starting-point info. */
188 if (OP(first) == EXACTLY) {
190 str_make(OPERAND(first)+1,*OPERAND(first));
191 if (r->regstart->str_cur > !(sawstudy|fold))
192 fbmcompile(r->regstart,fold);
194 else if ((exp = index(simple,OP(first))) && exp > simple)
195 r->regstclass = first;
196 else if (OP(first) == BOUND || OP(first) == NBOUND)
197 r->regstclass = first;
198 else if (OP(first) == BOL)
203 fprintf(stderr,"first %d next %d offset %d\n",
204 OP(first), OP(NEXTOPER(first)), first - scan);
207 * If there's something expensive in the r.e., find the
208 * longest literal string that must appear and make it the
209 * regmust. Resolve ties in favor of later strings, since
210 * the regstart check works with the beginning of the r.e.
211 * and avoiding duplication strengthens checking. Not a
212 * strong reason, but sufficient in the absence of others.
213 * [Now we resolve ties in favor of the earlier string if
214 * it happens that curback has been invalidated, since the
215 * earlier string may buy us something the later one won't.]
217 longest = str_make("",0);
221 while (scan != NULL) {
222 if (OP(scan) == BRANCH) {
223 if (OP(regnext(scan)) == BRANCH) {
225 while (OP(scan) == BRANCH)
226 scan = regnext(scan);
228 else /* single branch is ok */
229 scan = NEXTOPER(scan);
231 if (OP(scan) == EXACTLY) {
233 while (OP(regnext(scan)) >= CLOSE)
234 scan = regnext(scan);
235 if (curback - back == len) {
236 str_ncat(longest, OPERAND(first)+1,
238 len += *OPERAND(first);
239 curback += *OPERAND(first);
240 first = regnext(scan);
242 else if (*OPERAND(first) >= len + (curback >= 0)) {
243 len = *OPERAND(first);
244 str_nset(longest, OPERAND(first)+1,len);
247 first = regnext(scan);
250 curback += *OPERAND(first);
252 else if (index(varies,OP(scan)))
254 else if (index(simple,OP(scan)))
256 scan = regnext(scan);
259 r->regmust = longest;
263 if (len > !(sawstudy||fold||OP(first)==EOL))
264 fbmcompile(r->regmust,fold);
265 r->regmust->str_u.str_useful = 100;
266 if (OP(first) == EOL) /* is match anchored to EOL? */
267 r->regmust->str_pok |= SP_TAIL;
273 r->do_folding = fold;
274 r->nparens = regnpar - 1;
283 - reg - regular expression, i.e. main body or parenthesized thing
285 * Caller must absorb opening parenthesis.
287 * Combining parenthesis handling with the base level of regular expression
288 * is a trifle forced, but the need to tie the tails of the branches to what
289 * follows makes it hard to avoid.
293 int paren; /* Parenthesized? */
298 register char *ender;
302 *flagp = HASWIDTH; /* Tentatively. */
304 /* Make an OPEN node, if parenthesized. */
306 if (regnpar >= NSUBEXP)
307 FAIL("too many () in regexp");
310 ret = regnode(OPEN+parno);
314 /* Pick up the branches, linking them together. */
315 br = regbranch(&flags);
319 regtail(ret, br); /* OPEN -> first. */
322 if (!(flags&HASWIDTH))
324 *flagp |= flags&SPSTART;
325 while (*regparse == '|') {
327 br = regbranch(&flags);
330 regtail(ret, br); /* BRANCH -> BRANCH. */
331 if (!(flags&HASWIDTH))
333 *flagp |= flags&SPSTART;
336 /* Make a closing node, and hook it on the end. */
337 ender = regnode((paren) ? CLOSE+parno : END);
340 /* Hook the tails of the branches to the closing node. */
341 for (br = ret; br != NULL; br = regnext(br))
342 regoptail(br, ender);
344 /* Check for proper termination. */
345 if (paren && *regparse++ != ')') {
346 FAIL("unmatched () in regexp");
347 } else if (!paren && regparse < regxend) {
348 if (*regparse == ')') {
349 FAIL("unmatched () in regexp");
351 FAIL("junk on end of regexp"); /* "Can't happen". */
359 - regbranch - one alternative of an | operator
361 * Implements the concatenation operator.
368 register char *chain;
369 register char *latest;
372 *flagp = WORST; /* Tentatively. */
374 ret = regnode(BRANCH);
376 while (regparse < regxend && *regparse != '|' && *regparse != ')') {
377 latest = regpiece(&flags);
380 *flagp |= flags&HASWIDTH;
381 if (chain == NULL) /* First piece. */
382 *flagp |= flags&SPSTART;
384 regtail(chain, latest);
387 if (chain == NULL) /* Loop ran zero times. */
388 (void) regnode(NOTHING);
394 - regpiece - something followed by possible [*+?]
396 * Note that the branching code sequences used for ? and the general cases
397 * of * and + are somewhat optimized: they use the same NOTHING node as
398 * both the endmarker for their branch list and the body of the last branch.
399 * It might seem that this node could be dispensed with entirely, but the
400 * endmarker role is not redundant.
410 char *origparse = regparse;
411 int orignpar = regnpar;
416 ret = regatom(&flags);
422 /* Here's a total kludge: if after the atom there's a {\d+,?\d*}
423 * then we decrement the first number by one and reset our
424 * parsing back to the beginning of the same atom. If the first number
425 * is down to 0, decrement the second number instead and fake up
426 * a ? after it. Given the way this compiler doesn't keep track
427 * of offsets on the first pass, this is the only way to replicate
428 * a piece of code. Sigh.
430 if (op == '{' && regcurly(regparse)) {
433 while (isdigit(*next) || *next == ',') {
442 if (*next == '}') { /* got one */
443 regsawbracket++; /* remember we clobbered exp */
447 iter = atoi(regparse);
450 sprintf(regparse,"%.*d", max-regparse, iter - 1);
452 if (*max == ',' && atoi(max+1) > 0) {
454 sprintf(max+1,"%.*d", next-(max+1), atoi(max+1) - 1);
457 if (iter != 1 || (*max == ',' || atoi(max+1))) {
458 regparse = origparse; /* back up input pointer */
459 regnpar = orignpar; /* don't make more parens */
471 if (max == next) { /* any number more? */
473 op = '*'; /* fake up one with a star */
476 op = '?'; /* fake up optional atom */
478 sprintf(max,"%.*d", next-max, iter - 1);
483 regparse = origparse - 1; /* offset ++ below */
488 fatal("Can't do {n,0}");
491 fatal("Can't do {0}");
500 if (!(flags&HASWIDTH) && op != '?')
501 FAIL("regexp *+ operand could be empty");
502 *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
504 if (op == '*' && (flags&SIMPLE))
505 reginsert(STAR, ret);
506 else if (op == '*') {
507 /* Emit x* as (x&|), where & means "self". */
508 reginsert(BRANCH, ret); /* Either x */
509 regoptail(ret, regnode(BACK)); /* and loop */
510 regoptail(ret, ret); /* back */
511 regtail(ret, regnode(BRANCH)); /* or */
512 regtail(ret, regnode(NOTHING)); /* null. */
513 } else if (op == '+' && (flags&SIMPLE))
514 reginsert(PLUS, ret);
515 else if (op == '+') {
516 /* Emit x+ as x(&|), where & means "self". */
517 next = regnode(BRANCH); /* Either */
519 regtail(regnode(BACK), ret); /* loop back */
520 regtail(next, regnode(BRANCH)); /* or */
521 regtail(ret, regnode(NOTHING)); /* null. */
522 } else if (op == '?') {
523 /* Emit x? as (x|) */
524 reginsert(BRANCH, ret); /* Either x */
525 regtail(ret, regnode(BRANCH)); /* or */
526 next = regnode(NOTHING); /* null. */
528 regoptail(ret, next);
532 if (ISMULT2(regparse))
533 FAIL("nested *?+ in regexp");
539 - regatom - the lowest level
541 * Optimization: gobbles an entire sequence of ordinary characters so that
542 * it can turn them into a single node, which is smaller to store and
543 * faster to run. Backslashed characters are exceptions, each becoming a
544 * separate node; the code is simpler that way and it's not worth fixing.
546 * [Yes, it is worth fixing, some scripts can run twice the speed.]
555 *flagp = WORST; /* Tentatively. */
557 switch (*regparse++) {
566 *flagp |= HASWIDTH|SIMPLE;
570 *flagp |= HASWIDTH|SIMPLE;
573 ret = reg(1, &flags);
576 *flagp |= flags&(HASWIDTH|SPSTART);
580 FAIL("internal urp in regexp"); /* Supposed to be caught earlier. */
585 FAIL("?+* follows nothing in regexp");
590 ret = regnode(ALNUM);
591 *flagp |= HASWIDTH|SIMPLE;
595 ret = regnode(NALNUM);
596 *flagp |= HASWIDTH|SIMPLE;
600 ret = regnode(BOUND);
605 ret = regnode(NBOUND);
610 ret = regnode(SPACE);
611 *flagp |= HASWIDTH|SIMPLE;
615 ret = regnode(NSPACE);
616 *flagp |= HASWIDTH|SIMPLE;
620 ret = regnode(DIGIT);
621 *flagp |= HASWIDTH|SIMPLE;
625 ret = regnode(NDIGIT);
626 *flagp |= HASWIDTH|SIMPLE;
634 case '0': case '1': case '2': case '3': case '4':
635 case '5': case '6': case '7': case '8': case '9':
636 if (isdigit(regparse[1]))
639 ret = regnode(REF + *regparse++ - '0');
644 if (regparse >= regxend)
645 FAIL("trailing \\ in regexp");
659 ret = regnode(EXACTLY);
660 regc(0); /* save spot for len */
661 for (len=0, p=regparse-1;
662 len < 127 && p < regxend;
703 case '0': case '1': case '2': case '3':case '4':
704 case '5': case '6': case '7': case '8':case '9':
710 foo = (foo<<3) + *++p - '0';
721 FAIL("trailing \\ in regexp");
732 if (regfold && isupper(ender))
733 ender = tolower(ender);
734 if (ISMULT2(p)) { /* Back off on ?+*. */
748 FAIL("internal disaster in regexp");
752 if (regcode != ®dummy)
768 if (regcode == ®dummy)
771 bits[c >> 3] &= ~(1 << (c & 7));
773 bits[c >> 3] |= (1 << (c & 7));
781 register int lastclass;
782 register int range = 0;
786 if (*regparse == '^') { /* Complement of range. */
787 ret = regnode(ANYBUT);
791 ret = regnode(ANYOF);
795 for (class = 0; class < 32; class++)
797 if (*regparse == ']' || *regparse == '-')
798 regset(bits,def,lastclass = *regparse++);
799 while (regparse < regxend && *regparse != ']') {
800 class = UCHARAT(regparse++);
802 class = UCHARAT(regparse++);
805 for (class = 'a'; class <= 'z'; class++)
806 regset(bits,def,class);
807 for (class = 'A'; class <= 'Z'; class++)
808 regset(bits,def,class);
809 for (class = '0'; class <= '9'; class++)
810 regset(bits,def,class);
811 regset(bits,def,'_');
815 regset(bits,def,' ');
816 regset(bits,def,'\t');
817 regset(bits,def,'\r');
818 regset(bits,def,'\f');
819 regset(bits,def,'\n');
823 for (class = '0'; class <= '9'; class++)
824 regset(bits,def,class);
842 case '0': case '1': case '2': case '3': case '4':
843 case '5': case '6': case '7': case '8': case '9':
845 if (isdigit(*regparse)) {
847 class += *regparse++ - '0';
849 if (isdigit(*regparse)) {
851 class += *regparse++ - '0';
856 if (!range && class == '-' && regparse < regxend &&
862 if (lastclass > class)
863 FAIL("invalid [] range in regexp");
866 lastclass = class - 1;
868 for (lastclass++; lastclass <= class; lastclass++) {
869 regset(bits,def,lastclass);
870 if (regfold && isupper(lastclass))
871 regset(bits,def,tolower(lastclass));
875 if (*regparse != ']')
876 FAIL("unmatched [] in regexp");
877 regset(bits,0,0); /* always bomb out on null */
883 - regnode - emit a node
885 static char * /* Location. */
893 if (ret == ®dummy) {
904 if (!((long)ret & 1))
910 *ptr++ = '\0'; /* Null "next" pointer. */
918 - regc - emit (if appropriate) a byte of code
924 if (regcode != ®dummy)
931 - reginsert - insert an operator in front of already-emitted operand
933 * Means relocating the operand.
942 register char *place;
944 if (regcode == ®dummy) {
963 place = opnd; /* Op node, where operand used to be. */
970 - regtail - set the next-pointer at the end of a node chain
984 /* Find last node. */
987 temp = regnext(scan);
996 *(short*)(scan+1) = offset;
1001 if (OP(scan) == BACK)
1002 offset = scan - val;
1004 offset = val - scan;
1005 *(scan+1) = (offset>>8)&0377;
1006 *(scan+2) = offset&0377;
1011 - regoptail - regtail on operand of first argument; nop if operandless
1018 /* "Operandless" and "op != BRANCH" are synonymous in practice. */
1019 if (p == NULL || p == ®dummy || OP(p) != BRANCH)
1021 regtail(NEXTOPER(p), val);
1025 - regcurly - a little FSA that accepts {\d+,?\d*}
1049 - regdump - dump a regexp onto stderr in vaguely comprehensible form
1056 register char op = EXACTLY; /* Arbitrary non-END op. */
1057 register char *next;
1058 extern char *index();
1062 while (op != END) { /* While that wasn't END last time... */
1068 fprintf(stderr,"%2d%s", s-r->program, regprop(s)); /* Where, what. */
1070 if (next == NULL) /* Next ptr. */
1071 fprintf(stderr,"(0)");
1073 fprintf(stderr,"(%d)", (s-r->program)+(next-s));
1075 if (op == ANYOF || op == ANYBUT) {
1078 if (op == EXACTLY) {
1079 /* Literal string, where present. */
1081 while (*s != '\0') {
1087 (void)putchar('\n');
1090 /* Header fields of interest. */
1092 fprintf(stderr,"start `%s' ", r->regstart->str_ptr);
1094 fprintf(stderr,"stclass `%s' ", regprop(r->regstclass));
1096 fprintf(stderr,"anchored ");
1097 if (r->regmust != NULL)
1098 fprintf(stderr,"must have \"%s\" back %d ", r->regmust->str_ptr,
1100 fprintf(stderr,"\n");
1104 - regprop - printable representation of opcode
1112 (void) strcpy(buf, ":");
1179 (void)sprintf(buf+strlen(buf), "REF%d", OP(op)-REF);
1191 (void)sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
1203 (void)sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
1213 FAIL("corrupted regexp opcode");
1216 (void) strcat(buf, p);
1219 #endif /* DEBUGGING */
1225 Safefree(r->precomp);
1227 Safefree(r->subbase);
1229 str_free(r->regmust);
1231 str_free(r->regstart);