1 /*
2 * regcomp and regexec -- regsub and regerror are elsewhere
3 *
4 * Copyright (c) 1986 by University of Toronto.
5 * Written by Henry Spencer. Not derived from licensed software.
6 *
7 * Permission is granted to anyone to use this software for any
8 * purpose on any computer system, and to redistribute it freely,
9 * subject to the following restrictions:
10 *
11 * 1. The author is not responsible for the consequences of use of
12 * this software, no matter how awful, even if they arise
13 * from defects in it.
14 *
15 * 2. The origin of this software must not be misrepresented, either
16 * by explicit claim or by omission.
17 *
18 * 3. Altered versions must be plainly marked as such, and must not
19 * be misrepresented as being the original software.
20 *
21 * Beware that some of this code is subtly aware of the way operator
22 * precedence is structured in regular expressions. Serious changes in
23 * regular-expression syntax might require a total rethink.
24 */
25 #pragma ident "%Z%%M% %I% %E% SMI"
26 #include <stdio.h>
27 #include <string.h>
28 #include <tptregexp.h>
29 #include "regmagic.h"
30
31 /*
32 * The "internal use only" fields in regexp.h are present to pass info from
33 * compile to execute that permits the execute phase to run lots faster on
34 * simple cases. They are:
35 *
36 * regstart char that must begin a match; '\0' if none obvious
37 * reganch is the match anchored (at beginning-of-line only)?
38 * regmust string (pointer into program) that match must include, or NULL
39 * regmlen length of regmust string
40 *
41 * Regstart and reganch permit very fast decisions on suitable starting points
42 * for a match, cutting down the work a lot. Regmust permits fast rejection
43 * of lines that cannot possibly match. The regmust tests are costly enough
44 * that regcomp() supplies a regmust only if the r.e. contains something
45 * potentially expensive (at present, the only such thing detected is * or +
46 * at the start of the r.e., which can involve a lot of backup). Regmlen is
47 * supplied because the test in regexec() needs it and regcomp() is computing
48 * it anyway.
49 */
50
51 /*
52 * Structure for regexp "program". This is essentially a linear encoding
53 * of a nondeterministic finite-state machine (aka syntax charts or
54 * "railroad normal form" in parsing technology). Each node is an opcode
55 * plus a "next" pointer, possibly plus an operand. "Next" pointers of
56 * all nodes except BRANCH implement concatenation; a "next" pointer with
57 * a BRANCH on both ends of it is connecting two alternatives. (Here we
58 * have one of the subtle syntax dependencies: an individual BRANCH (as
59 * opposed to a collection of them) is never concatenated with anything
60 * because of operator precedence.) The operand of some types of node is
61 * a literal string; for others, it is a node leading into a sub-FSM. In
62 * particular, the operand of a BRANCH node is the first node of the branch.
63 * (NB this is *not* a tree structure: the tail of the branch connects
64 * to the thing following the set of BRANCHes.) The opcodes are:
65 */
66
67 /* definition number opnd? meaning */
68 #define END 0 /* no End of program. */
69 #define BOL 1 /* no Match "" at beginning of line. */
70 #define EOL 2 /* no Match "" at end of line. */
71 #define ANY 3 /* no Match any one character. */
72 #define ANYOF 4 /* str Match any character in this string. */
73 #define ANYBUT 5 /* str Match any character not in this string. */
74 #define BRANCH 6 /* node Match this alternative, or the next... */
75 #define BACK 7 /* no Match "", "next" ptr points backward. */
76 #define EXACTLY 8 /* str Match this string. */
77 #define NOTHING 9 /* no Match empty string. */
78 #define STAR 10 /* node Match this (simple) thing 0 or more times. */
79 #define PLUS 11 /* node Match this (simple) thing 1 or more times. */
80 #define OPEN 20 /* no Mark this point in input as start of #n. */
81 /* OPEN+1 is number 1, etc. */
82 #define CLOSE 30 /* no Analogous to OPEN. */
83
84 /*
85 * Opcode notes:
86 *
87 * BRANCH The set of branches constituting a single choice are hooked
88 * together with their "next" pointers, since precedence prevents
89 * anything being concatenated to any individual branch. The
90 * "next" pointer of the last BRANCH in a choice points to the
91 * thing following the whole choice. This is also where the
92 * final "next" pointer of each individual branch points; each
93 * branch starts with the operand node of a BRANCH node.
94 *
95 * BACK Normal "next" pointers all implicitly point forward; BACK
96 * exists to make loop structures possible.
97 *
98 * STAR,PLUS '?', and complex '*' and '+', are implemented as circular
99 * BRANCH structures using BACK. Simple cases (one character
100 * per match) are implemented with STAR and PLUS for speed
101 * and to minimize recursive plunges.
102 *
103 * OPEN,CLOSE ...are numbered at compile time.
104 */
105
106 /*
107 * A node is one char of opcode followed by two chars of "next" pointer.
108 * "Next" pointers are stored as two 8-bit pieces, high order first. The
109 * value is a positive offset from the opcode of the node containing it.
110 * An operand, if any, simply follows the node. (Note that much of the
111 * code generation knows about this implicit relationship.)
112 *
113 * Using two bytes for the "next" pointer is vast overkill for most things,
114 * but allows patterns to get big without disasters.
115 */
116 #define OP(p) (*(p))
117 #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
118
119 #define OPERAND(p) ((p) + 3)
120
121 /*
122 * See regmagic.h for one further detail of program structure.
123 */
124
125
126 /*
127 * Utility definitions.
128 */
129 #ifndef CHARBITS
130 #define UCHARAT(p) ((int)*(unsigned char *)(p))
131 #else
132 #define UCHARAT(p) ((int)*(p)&CHARBITS)
133 #endif
134
135 #define FAIL(m) { tpt_regerror(m); return(NULL); }
136 #define ISMULT(c) ((c) == '*' || (c) == '+' || (c) == '?')
137 #define META "^$.[()|?+*\\"
138
139 /*
140 * Flags to be passed up and down.
141 */
142 #define HASWIDTH 01 /* Known never to match null string. */
143 #define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */
144 #define SPSTART 04 /* Starts with * or +. */
145 #define WORST 0 /* Worst case. */
146
147 /*
148 * Global work variables for regcomp().
149 */
150 static char *regparse; /* Input-scan pointer. */
151 static int regnpar; /* () count. */
152 static char regdummy;
153 static char *regcode; /* Code-emit pointer; ®dummy = don't. */
154 static long regsize; /* Code size. */
155
156 /*
157 * Forward declarations for regcomp()'s friends.
158 */
159 #ifndef STATIC
160 #define STATIC static
161 #endif
162 STATIC char *reg();
163 STATIC char *regbranch();
164 STATIC char *regpiece();
165 STATIC char *regatom();
166 STATIC char *regnode();
167 STATIC char *regnext();
168 STATIC void regc();
169 STATIC void reginsert();
170 STATIC void regtail();
171 STATIC void regoptail();
172 #ifdef STRCSPN
173 STATIC int strcspn();
174 #endif
175
176 /*
177 - regcomp - compile a regular expression into internal code
178 *
179 * We can't allocate space until we know how big the compiled form will be,
180 * but we can't compile it (and thus know how big it is) until we've got a
181 * place to put the code. So we cheat: we compile it twice, once with code
182 * generation turned off and size counting turned on, and once "for real".
183 * This also means that we don't allocate space until we are sure that the
184 * thing really will compile successfully, and we never have to move the
185 * code and thus invalidate pointers into it. (Note that it has to be in
186 * one piece because free() must be able to free it all.)
187 *
188 * Beware that the optimization-preparation code in here knows about some
189 * of the structure of the compiled regexp.
190 */
191 regexp *
tpt_regcomp(exp)192 tpt_regcomp(exp)
193 char *exp;
194 {
195 register regexp *r;
196 register char *scan;
197 register char *longest;
198 register int len;
199 int flags;
200 extern char *malloc();
201
202 if (exp == NULL)
203 FAIL("NULL argument");
204
205 /* First pass: determine size, legality. */
206 regparse = exp;
207 regnpar = 1;
208 regsize = 0L;
209 regcode = ®dummy;
210 regc(MAGIC);
211 if (reg(0, &flags) == NULL)
212 return(NULL);
213
214 /* Small enough for pointer-storage convention? */
215 if (regsize >= 32767L) /* Probably could be 65535L. */
216 FAIL("regexp too big");
217
218 /* Allocate space. */
219 r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
220 if (r == NULL)
221 FAIL("out of space");
222
223 /* Second pass: emit code. */
224 regparse = exp;
225 regnpar = 1;
226 regcode = r->program;
227 regc(MAGIC);
228 if (reg(0, &flags) == NULL)
229 return(NULL);
230
231 /* Dig out information for optimizations. */
232 r->regstart = '\0'; /* Worst-case defaults. */
233 r->reganch = 0;
234 r->regmust = NULL;
235 r->regmlen = 0;
236 scan = r->program+1; /* First BRANCH. */
237 if (OP(regnext(scan)) == END) { /* Only one top-level choice. */
238 scan = OPERAND(scan);
239
240 /* Starting-point info. */
241 if (OP(scan) == EXACTLY)
242 r->regstart = *OPERAND(scan);
243 else if (OP(scan) == BOL)
244 r->reganch++;
245
246 /*
247 * If there's something expensive in the r.e., find the
248 * longest literal string that must appear and make it the
249 * regmust. Resolve ties in favor of later strings, since
250 * the regstart check works with the beginning of the r.e.
251 * and avoiding duplication strengthens checking. Not a
252 * strong reason, but sufficient in the absence of others.
253 */
254 if (flags&SPSTART) {
255 longest = NULL;
256 len = 0;
257 for (; scan != NULL; scan = regnext(scan))
258 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
259 longest = OPERAND(scan);
260 len = strlen(OPERAND(scan));
261 }
262 r->regmust = longest;
263 r->regmlen = len;
264 }
265 }
266
267 return(r);
268 }
269
270 /*
271 - reg - regular expression, i.e. main body or parenthesized thing
272 *
273 * Caller must absorb opening parenthesis.
274 *
275 * Combining parenthesis handling with the base level of regular expression
276 * is a trifle forced, but the need to tie the tails of the branches to what
277 * follows makes it hard to avoid.
278 */
279 static char *
reg(paren,flagp)280 reg(paren, flagp)
281 int paren; /* Parenthesized? */
282 int *flagp;
283 {
284 register char *ret;
285 register char *br;
286 register char *ender;
287 register int parno;
288 int flags;
289
290 *flagp = HASWIDTH; /* Tentatively. */
291
292 /* Make an OPEN node, if parenthesized. */
293 if (paren) {
294 if (regnpar >= NSUBEXP)
295 FAIL("too many ()");
296 parno = regnpar;
297 regnpar++;
298 ret = regnode(OPEN+parno);
299 } else
300 ret = NULL;
301
302 /* Pick up the branches, linking them together. */
303 br = regbranch(&flags);
304 if (br == NULL)
305 return(NULL);
306 if (ret != NULL)
307 regtail(ret, br); /* OPEN -> first. */
308 else
309 ret = br;
310 if (!(flags&HASWIDTH))
311 *flagp &= ~HASWIDTH;
312 *flagp |= flags&SPSTART;
313 while (*regparse == '|') {
314 regparse++;
315 br = regbranch(&flags);
316 if (br == NULL)
317 return(NULL);
318 regtail(ret, br); /* BRANCH -> BRANCH. */
319 if (!(flags&HASWIDTH))
320 *flagp &= ~HASWIDTH;
321 *flagp |= flags&SPSTART;
322 }
323
324 /* Make a closing node, and hook it on the end. */
325 ender = regnode((paren) ? CLOSE+parno : END);
326 regtail(ret, ender);
327
328 /* Hook the tails of the branches to the closing node. */
329 for (br = ret; br != NULL; br = regnext(br))
330 regoptail(br, ender);
331
332 /* Check for proper termination. */
333 if (paren && *regparse++ != ')') {
334 FAIL("unmatched ()");
335 } else if (!paren && *regparse != '\0') {
336 if (*regparse == ')') {
337 FAIL("unmatched ()");
338 } else
339 FAIL("junk on end"); /* "Can't happen". */
340 /* NOTREACHED */
341 }
342
343 return(ret);
344 }
345
346 /*
347 - regbranch - one alternative of an | operator
348 *
349 * Implements the concatenation operator.
350 */
351 static char *
regbranch(flagp)352 regbranch(flagp)
353 int *flagp;
354 {
355 register char *ret;
356 register char *chain;
357 register char *latest;
358 int flags;
359
360 *flagp = WORST; /* Tentatively. */
361
362 ret = regnode(BRANCH);
363 chain = NULL;
364 while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
365 latest = regpiece(&flags);
366 if (latest == NULL)
367 return(NULL);
368 *flagp |= flags&HASWIDTH;
369 if (chain == NULL) /* First piece. */
370 *flagp |= flags&SPSTART;
371 else
372 regtail(chain, latest);
373 chain = latest;
374 }
375 if (chain == NULL) /* Loop ran zero times. */
376 (void) regnode(NOTHING);
377
378 return(ret);
379 }
380
381 /*
382 - regpiece - something followed by possible [*+?]
383 *
384 * Note that the branching code sequences used for ? and the general cases
385 * of * and + are somewhat optimized: they use the same NOTHING node as
386 * both the endmarker for their branch list and the body of the last branch.
387 * It might seem that this node could be dispensed with entirely, but the
388 * endmarker role is not redundant.
389 */
390 static char *
regpiece(flagp)391 regpiece(flagp)
392 int *flagp;
393 {
394 register char *ret;
395 register char op;
396 register char *next;
397 int flags;
398
399 ret = regatom(&flags);
400 if (ret == NULL)
401 return(NULL);
402
403 op = *regparse;
404 if (!ISMULT(op)) {
405 *flagp = flags;
406 return(ret);
407 }
408
409 if (!(flags&HASWIDTH) && op != '?')
410 FAIL("*+ operand could be empty");
411 *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
412
413 if (op == '*' && (flags&SIMPLE))
414 reginsert(STAR, ret);
415 else if (op == '*') {
416 /* Emit x* as (x&|), where & means "self". */
417 reginsert(BRANCH, ret); /* Either x */
418 regoptail(ret, regnode(BACK)); /* and loop */
419 regoptail(ret, ret); /* back */
420 regtail(ret, regnode(BRANCH)); /* or */
421 regtail(ret, regnode(NOTHING)); /* null. */
422 } else if (op == '+' && (flags&SIMPLE))
423 reginsert(PLUS, ret);
424 else if (op == '+') {
425 /* Emit x+ as x(&|), where & means "self". */
426 next = regnode(BRANCH); /* Either */
427 regtail(ret, next);
428 regtail(regnode(BACK), ret); /* loop back */
429 regtail(next, regnode(BRANCH)); /* or */
430 regtail(ret, regnode(NOTHING)); /* null. */
431 } else if (op == '?') {
432 /* Emit x? as (x|) */
433 reginsert(BRANCH, ret); /* Either x */
434 regtail(ret, regnode(BRANCH)); /* or */
435 next = regnode(NOTHING); /* null. */
436 regtail(ret, next);
437 regoptail(ret, next);
438 }
439 regparse++;
440 if (ISMULT(*regparse))
441 FAIL("nested *?+");
442
443 return(ret);
444 }
445
446 /*
447 - regatom - the lowest level
448 *
449 * Optimization: gobbles an entire sequence of ordinary characters so that
450 * it can turn them into a single node, which is smaller to store and
451 * faster to run. Backslashed characters are exceptions, each becoming a
452 * separate node; the code is simpler that way and it's not worth fixing.
453 */
454 static char *
regatom(flagp)455 regatom(flagp)
456 int *flagp;
457 {
458 register char *ret;
459 int flags;
460
461 *flagp = WORST; /* Tentatively. */
462
463 switch (*regparse++) {
464 case '':
465 ret = regnode(BOL);
466 break;
467 case '$':
468 ret = regnode(EOL);
469 break;
470 case '.':
471 ret = regnode(ANY);
472 *flagp |= HASWIDTH|SIMPLE;
473 break;
474 case '[': {
475 register int class;
476 register int classend;
477
478 if (*regparse == '') { /* Complement of range. */
479 ret = regnode(ANYBUT);
480 regparse++;
481 } else
482 ret = regnode(ANYOF);
483 if (*regparse == ']' || *regparse == '-')
484 regc(*regparse++);
485 while (*regparse != '\0' && *regparse != ']') {
486 if (*regparse == '-') {
487 regparse++;
488 if (*regparse == ']' || *regparse == '\0')
489 regc('-');
490 else {
491 class = UCHARAT(regparse-2)+1;
492 classend = UCHARAT(regparse);
493 if (class > classend+1)
494 FAIL("invalid [] range");
495 for (; class <= classend; class++)
496 regc(class);
497 regparse++;
498 }
499 } else
500 regc(*regparse++);
501 }
502 regc('\0');
503 if (*regparse != ']')
504 FAIL("unmatched []");
505 regparse++;
506 *flagp |= HASWIDTH|SIMPLE;
507 }
508 break;
509 case '(':
510 ret = reg(1, &flags);
511 if (ret == NULL)
512 return(NULL);
513 *flagp |= flags&(HASWIDTH|SPSTART);
514 break;
515 case '\0':
516 case '|':
517 case ')':
518 FAIL("internal urp"); /* Supposed to be caught earlier. */
519 break;
520 case '?':
521 case '+':
522 case '*':
523 FAIL("?+* follows nothing");
524 break;
525 case '\\':
526 if (*regparse == '\0')
527 FAIL("trailing \\");
528 ret = regnode(EXACTLY);
529 regc(*regparse++);
530 regc('\0');
531 *flagp |= HASWIDTH|SIMPLE;
532 break;
533 default: {
534 register int len;
535 register char ender;
536
537 regparse--;
538 len = strcspn(regparse, META);
539 if (len <= 0)
540 FAIL("internal disaster");
541 ender = *(regparse+len);
542 if (len > 1 && ISMULT(ender))
543 len--; /* Back off clear of ?+* operand. */
544 *flagp |= HASWIDTH;
545 if (len == 1)
546 *flagp |= SIMPLE;
547 ret = regnode(EXACTLY);
548 while (len > 0) {
549 regc(*regparse++);
550 len--;
551 }
552 regc('\0');
553 }
554 break;
555 }
556
557 return(ret);
558 }
559
560 /*
561 - regnode - emit a node
562 */
563 static char * /* Location. */
regnode(op)564 regnode(op)
565 char op;
566 {
567 register char *ret;
568 register char *ptr;
569
570 ret = regcode;
571 if (ret == ®dummy) {
572 regsize += 3;
573 return(ret);
574 }
575
576 ptr = ret;
577 *ptr++ = op;
578 *ptr++ = '\0'; /* Null "next" pointer. */
579 *ptr++ = '\0';
580 regcode = ptr;
581
582 return(ret);
583 }
584
585 /*
586 - regc - emit (if appropriate) a byte of code
587 */
588 static void
regc(b)589 regc(b)
590 char b;
591 {
592 if (regcode != ®dummy)
593 *regcode++ = b;
594 else
595 regsize++;
596 }
597
598 /*
599 - reginsert - insert an operator in front of already-emitted operand
600 *
601 * Means relocating the operand.
602 */
603 static void
reginsert(op,opnd)604 reginsert(op, opnd)
605 char op;
606 char *opnd;
607 {
608 register char *src;
609 register char *dst;
610 register char *place;
611
612 if (regcode == ®dummy) {
613 regsize += 3;
614 return;
615 }
616
617 src = regcode;
618 regcode += 3;
619 dst = regcode;
620 while (src > opnd)
621 *--dst = *--src;
622
623 place = opnd; /* Op node, where operand used to be. */
624 *place++ = op;
625 *place++ = '\0';
626 *place++ = '\0';
627 }
628
629 /*
630 - regtail - set the next-pointer at the end of a node chain
631 */
632 static void
regtail(p,val)633 regtail(p, val)
634 char *p;
635 char *val;
636 {
637 register char *scan;
638 register char *temp;
639 register int offset;
640
641 if (p == ®dummy)
642 return;
643
644 /* Find last node. */
645 scan = p;
646 for (;;) {
647 temp = regnext(scan);
648 if (temp == NULL)
649 break;
650 scan = temp;
651 }
652
653 if (OP(scan) == BACK)
654 offset = scan - val;
655 else
656 offset = val - scan;
657 *(scan+1) = (offset>>8)&0377;
658 *(scan+2) = offset&0377;
659 }
660
661 /*
662 - regoptail - regtail on operand of first argument; nop if operandless
663 */
664 static void
regoptail(p,val)665 regoptail(p, val)
666 char *p;
667 char *val;
668 {
669 /* "Operandless" and "op != BRANCH" are synonymous in practice. */
670 if (p == NULL || p == ®dummy || OP(p) != BRANCH)
671 return;
672 regtail(OPERAND(p), val);
673 }
674
675 /*
676 * regexec and friends
677 */
678
679 /*
680 * Global work variables for regexec().
681 */
682 static char *reginput; /* String-input pointer. */
683 static char *regbol; /* Beginning of input, for check. */
684 static char **regstartp; /* Pointer to startp array. */
685 static char **regendp; /* Ditto for endp. */
686
687 /*
688 * Forwards.
689 */
690 STATIC int regtry();
691 STATIC int regmatch();
692 STATIC int regrepeat();
693
694 #ifdef DEBUG
695 int regnarrate = 0;
696 void regdump();
697 STATIC char *regprop();
698 #endif
699
700 /*
701 - regexec - match a regexp against a string
702 */
703 int
tpt_regexec(prog,string)704 tpt_regexec(prog, string)
705 register regexp *prog;
706 register char *string;
707 {
708 register char *s;
709 extern char *strchr();
710
711 /* Be paranoid... */
712 if (prog == NULL || string == NULL) {
713 tpt_regerror("NULL parameter");
714 return(0);
715 }
716
717 /* Check validity of program. */
718 if (UCHARAT(prog->program) != MAGIC) {
719 tpt_regerror("corrupted program");
720 return(0);
721 }
722
723 /* If there is a "must appear" string, look for it. */
724 if (prog->regmust != NULL) {
725 s = string;
726 while ((s = strchr(s, prog->regmust[0])) != NULL) {
727 if (strncmp(s, prog->regmust, prog->regmlen) == 0)
728 break; /* Found it. */
729 s++;
730 }
731 if (s == NULL) /* Not present. */
732 return(0);
733 }
734
735 /* Mark beginning of line for . */
736 regbol = string;
737
738 /* Simplest case: anchored match need be tried only once. */
739 if (prog->reganch)
740 return(regtry(prog, string));
741
742 /* Messy cases: unanchored match. */
743 s = string;
744 if (prog->regstart != '\0')
745 /* We know what char it must start with. */
746 while ((s = strchr(s, prog->regstart)) != NULL) {
747 if (regtry(prog, s))
748 return(1);
749 s++;
750 }
751 else
752 /* We don't -- general case. */
753 do {
754 if (regtry(prog, s))
755 return(1);
756 } while (*s++ != '\0');
757
758 /* Failure. */
759 return(0);
760 }
761
762 /*
763 - regtry - try match at specific point
764 */
765 static int /* 0 failure, 1 success */
regtry(prog,string)766 regtry(prog, string)
767 regexp *prog;
768 char *string;
769 {
770 register int i;
771 register char **sp;
772 register char **ep;
773
774 reginput = string;
775 regstartp = prog->startp;
776 regendp = prog->endp;
777
778 sp = prog->startp;
779 ep = prog->endp;
780 for (i = NSUBEXP; i > 0; i--) {
781 *sp++ = NULL;
782 *ep++ = NULL;
783 }
784 if (regmatch(prog->program + 1)) {
785 prog->startp[0] = string;
786 prog->endp[0] = reginput;
787 return(1);
788 } else
789 return(0);
790 }
791
792 /*
793 - regmatch - main matching routine
794 *
795 * Conceptually the strategy is simple: check to see whether the current
796 * node matches, call self recursively to see whether the rest matches,
797 * and then act accordingly. In practice we make some effort to avoid
798 * recursion, in particular by going through "ordinary" nodes (that don't
799 * need to know whether the rest of the match failed) by a loop instead of
800 * by recursion.
801 */
802 static int /* 0 failure, 1 success */
regmatch(prog)803 regmatch(prog)
804 char *prog;
805 {
806 register char *scan; /* Current node. */
807 char *next; /* Next node. */
808 extern char *strchr();
809
810 scan = prog;
811 #ifdef DEBUG
812 if (scan != NULL && regnarrate)
813 fprintf(stderr, "%s(\n", regprop(scan));
814 #endif
815 while (scan != NULL) {
816 #ifdef DEBUG
817 if (regnarrate)
818 fprintf(stderr, "%s...\n", regprop(scan));
819 #endif
820 next = regnext(scan);
821
822 switch (OP(scan)) {
823 case BOL:
824 if (reginput != regbol)
825 return(0);
826 break;
827 case EOL:
828 if (*reginput != '\0')
829 return(0);
830 break;
831 case ANY:
832 if (*reginput == '\0')
833 return(0);
834 reginput++;
835 break;
836 case EXACTLY: {
837 register int len;
838 register char *opnd;
839
840 opnd = OPERAND(scan);
841 /* Inline the first character, for speed. */
842 if (*opnd != *reginput)
843 return(0);
844 len = strlen(opnd);
845 if (len > 1 && strncmp(opnd, reginput, len) != 0)
846 return(0);
847 reginput += len;
848 }
849 break;
850 case ANYOF:
851 if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
852 return(0);
853 reginput++;
854 break;
855 case ANYBUT:
856 if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
857 return(0);
858 reginput++;
859 break;
860 case NOTHING:
861 break;
862 case BACK:
863 break;
864 case OPEN+1:
865 case OPEN+2:
866 case OPEN+3:
867 case OPEN+4:
868 case OPEN+5:
869 case OPEN+6:
870 case OPEN+7:
871 case OPEN+8:
872 case OPEN+9: {
873 register int no;
874 register char *save;
875
876 no = OP(scan) - OPEN;
877 save = reginput;
878
879 if (regmatch(next)) {
880 /*
881 * Don't set startp if some later
882 * invocation of the same parentheses
883 * already has.
884 */
885 if (regstartp[no] == NULL)
886 regstartp[no] = save;
887 return(1);
888 } else
889 return(0);
890 }
891 break;
892 case CLOSE+1:
893 case CLOSE+2:
894 case CLOSE+3:
895 case CLOSE+4:
896 case CLOSE+5:
897 case CLOSE+6:
898 case CLOSE+7:
899 case CLOSE+8:
900 case CLOSE+9: {
901 register int no;
902 register char *save;
903
904 no = OP(scan) - CLOSE;
905 save = reginput;
906
907 if (regmatch(next)) {
908 /*
909 * Don't set endp if some later
910 * invocation of the same parentheses
911 * already has.
912 */
913 if (regendp[no] == NULL)
914 regendp[no] = save;
915 return(1);
916 } else
917 return(0);
918 }
919 break;
920 case BRANCH: {
921 register char *save;
922
923 if (OP(next) != BRANCH) /* No choice. */
924 next = OPERAND(scan); /* Avoid recursion. */
925 else {
926 do {
927 save = reginput;
928 if (regmatch(OPERAND(scan)))
929 return(1);
930 reginput = save;
931 scan = regnext(scan);
932 } while (scan != NULL && OP(scan) == BRANCH);
933 return(0);
934 /* NOTREACHED */
935 }
936 }
937 break;
938 case STAR:
939 case PLUS: {
940 register char nextch;
941 register int no;
942 register char *save;
943 register int min;
944
945 /*
946 * Lookahead to avoid useless match attempts
947 * when we know what character comes next.
948 */
949 nextch = '\0';
950 if (OP(next) == EXACTLY)
951 nextch = *OPERAND(next);
952 min = (OP(scan) == STAR) ? 0 : 1;
953 save = reginput;
954 no = regrepeat(OPERAND(scan));
955 while (no >= min) {
956 /* If it could work, try it. */
957 if (nextch == '\0' || *reginput == nextch)
958 if (regmatch(next))
959 return(1);
960 /* Couldn't or didn't -- back up. */
961 no--;
962 reginput = save + no;
963 }
964 return(0);
965 }
966 break;
967 case END:
968 return(1); /* Success! */
969 break;
970 default:
971 tpt_regerror("memory corruption");
972 return(0);
973 break;
974 }
975
976 scan = next;
977 }
978
979 /*
980 * We get here only if there's trouble -- normally "case END" is
981 * the terminating point.
982 */
983 tpt_regerror("corrupted pointers");
984 return(0);
985 }
986
987 /*
988 - regrepeat - repeatedly match something simple, report how many
989 */
990 static int
regrepeat(p)991 regrepeat(p)
992 char *p;
993 {
994 register int count = 0;
995 register char *scan;
996 register char *opnd;
997
998 scan = reginput;
999 opnd = OPERAND(p);
1000 switch (OP(p)) {
1001 case ANY:
1002 count = strlen(scan);
1003 scan += count;
1004 break;
1005 case EXACTLY:
1006 while (*opnd == *scan) {
1007 count++;
1008 scan++;
1009 }
1010 break;
1011 case ANYOF:
1012 while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
1013 count++;
1014 scan++;
1015 }
1016 break;
1017 case ANYBUT:
1018 while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
1019 count++;
1020 scan++;
1021 }
1022 break;
1023 default: /* Oh dear. Called inappropriately. */
1024 tpt_regerror("internal foulup");
1025 count = 0; /* Best compromise. */
1026 break;
1027 }
1028 reginput = scan;
1029
1030 return(count);
1031 }
1032
1033 /*
1034 - regnext - dig the "next" pointer out of a node
1035 */
1036 static char *
regnext(p)1037 regnext(p)
1038 register char *p;
1039 {
1040 register int offset;
1041
1042 if (p == ®dummy)
1043 return(NULL);
1044
1045 offset = NEXT(p);
1046 if (offset == 0)
1047 return(NULL);
1048
1049 if (OP(p) == BACK)
1050 return(p-offset);
1051 else
1052 return(p+offset);
1053 }
1054
1055 #ifdef DEBUG
1056
1057 STATIC char *regprop();
1058
1059 /*
1060 - regdump - dump a regexp onto stdout in vaguely comprehensible form
1061 */
1062 void
regdump(r)1063 regdump(r)
1064 regexp *r;
1065 {
1066 register char *s;
1067 register char op = EXACTLY; /* Arbitrary non-END op. */
1068 register char *next;
1069 extern char *strchr();
1070
1071
1072 s = r->program + 1;
1073 while (op != END) { /* While that wasn't END last time... */
1074 op = OP(s);
1075 printf("%2d%s", s-r->program, regprop(s)); /* Where, what. */
1076 next = regnext(s);
1077 if (next == NULL) /* Next ptr. */
1078 printf("(0)");
1079 else
1080 printf("(%d)", (s-r->program)+(next-s));
1081 s += 3;
1082 if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
1083 /* Literal string, where present. */
1084 while (*s != '\0') {
1085 putchar(*s);
1086 s++;
1087 }
1088 s++;
1089 }
1090 putchar('\n');
1091 }
1092
1093 /* Header fields of interest. */
1094 if (r->regstart != '\0')
1095 printf("start `%c' ", r->regstart);
1096 if (r->reganch)
1097 printf("anchored ");
1098 if (r->regmust != NULL)
1099 printf("must have \"%s\"", r->regmust);
1100 printf("\n");
1101 }
1102
1103 /*
1104 - regprop - printable representation of opcode
1105 */
1106 static char *
regprop(op)1107 regprop(op)
1108 char *op;
1109 {
1110 register char *p;
1111 static char buf[50];
1112
1113 (void) strcpy(buf, ":");
1114
1115 switch (OP(op)) {
1116 case BOL:
1117 p = "BOL";
1118 break;
1119 case EOL:
1120 p = "EOL";
1121 break;
1122 case ANY:
1123 p = "ANY";
1124 break;
1125 case ANYOF:
1126 p = "ANYOF";
1127 break;
1128 case ANYBUT:
1129 p = "ANYBUT";
1130 break;
1131 case BRANCH:
1132 p = "BRANCH";
1133 break;
1134 case EXACTLY:
1135 p = "EXACTLY";
1136 break;
1137 case NOTHING:
1138 p = "NOTHING";
1139 break;
1140 case BACK:
1141 p = "BACK";
1142 break;
1143 case END:
1144 p = "END";
1145 break;
1146 case OPEN+1:
1147 case OPEN+2:
1148 case OPEN+3:
1149 case OPEN+4:
1150 case OPEN+5:
1151 case OPEN+6:
1152 case OPEN+7:
1153 case OPEN+8:
1154 case OPEN+9:
1155 sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
1156 p = NULL;
1157 break;
1158 case CLOSE+1:
1159 case CLOSE+2:
1160 case CLOSE+3:
1161 case CLOSE+4:
1162 case CLOSE+5:
1163 case CLOSE+6:
1164 case CLOSE+7:
1165 case CLOSE+8:
1166 case CLOSE+9:
1167 sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
1168 p = NULL;
1169 break;
1170 case STAR:
1171 p = "STAR";
1172 break;
1173 case PLUS:
1174 p = "PLUS";
1175 break;
1176 default:
1177 tpt_regerror("corrupted opcode");
1178 break;
1179 }
1180 if (p != NULL)
1181 (void) strcat(buf, p);
1182 return(buf);
1183 }
1184 #endif
1185
1186 /*
1187 * The following is provided for those people who do not have strcspn() in
1188 * their C libraries. They should get off their butts and do something
1189 * about it; at least one public-domain implementation of those (highly
1190 * useful) string routines has been published on Usenet.
1191 */
1192 #ifdef STRCSPN
1193 /*
1194 * strcspn - find length of initial segment of s1 consisting entirely
1195 * of characters not from s2
1196 */
1197
1198 static int
strcspn(s1,s2)1199 strcspn(s1, s2)
1200 char *s1;
1201 char *s2;
1202 {
1203 register char *scan1;
1204 register char *scan2;
1205 register int count;
1206
1207 count = 0;
1208 for (scan1 = s1; *scan1 != '\0'; scan1++) {
1209 for (scan2 = s2; *scan2 != '\0';) /* ++ moved down. */
1210 if (*scan1 == *scan2++)
1211 return(count);
1212 count++;
1213 }
1214 return(count);
1215 }
1216 #endif
1217