![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to regexp.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Micropolis - Activity] / micropolis / src / tcl|
Return to regexp.c CVS log | Up to [Micropolis - Activity] / micropolis / src / tcl |
1.1 root 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; ®dummy = 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 = ®dummy;
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 == ®dummy) {
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 != ®dummy)
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 == ®dummy) {
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 == ®dummy)
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 == ®dummy || 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 == ®dummy)
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
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.