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