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