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