xref: /onnv-gate/usr/src/cmd/man/src/util/instant.src/tptregexp/regexp.c (revision 0:68f95e015346)
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; &regdummy = 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 = &regdummy;
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 == &regdummy) {
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 != &regdummy)
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 == &regdummy) {
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 == &regdummy)
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 == &regdummy || 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 == &regdummy)
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