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