1 /*_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/
5 * Function:..Routine for TWEB -> regular expressions *
9 * Authors:...Dr. Kurt Spanier & Bernhard Winkler, *
10 * Zentrum fuer Datenverarbeitung, Bereich Entwicklung *
11 * neuer Dienste, Universitaet Tuebingen, GERMANY *
14 * Creation date: Z D D V V *
15 * January 20 1998 Z D D V V *
16 * Last modification: Z D D V V *
17 * December 31 1998 ZZZZZ DDD V *
19 _/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_*/
21 * $Id: regular.c,v 1.6 1999/09/10 15:01:19 zrnsk01 Exp $
28 #include "regular_exp.h"
30 #include "support_exp.h"
33 PUBLIC void tweb_regerror(s)
37 error("regexp: %s", s);
39 /* fprintf(stderr, "regexp(3): %s", s);
42 /* TWEB: error-logging by syslog */
43 if (dosyslog) syslog (LOG_INFO,
44 "ALLOW/DENY/GRANT/REFUSE - regexp-error: %s", s);
52 * Copyright (c) 1986 by University of Toronto.
53 * Written by Henry Spencer. Not derived from licensed software.
55 * Permission is granted to anyone to use this software for any
56 * purpose on any computer system, and to redistribute it freely,
57 * subject to the following restrictions:
59 * 1. The author is not responsible for the consequences of use of
60 * this software, no matter how awful, even if they arise
63 * 2. The origin of this software must not be misrepresented, either
64 * by explicit claim or by omission.
66 * 3. Altered versions must be plainly marked as such, and must not
67 * be misrepresented as being the original software.
71 #define UCHARAT(p) ((int)*(unsigned char *)(p))
73 #define UCHARAT(p) ((int)*(p)&CHARBITS)
77 - tweb_regsub - perform substitutions after a regexp match
79 PUBLIC void tweb_regsub(prog, source, dest)
89 extern char *strncpy();
91 if (prog == NULL || source == NULL || dest == NULL) {
92 tweb_regerror("NULL parm to tweb_regsub");
95 if (UCHARAT(prog->program) != MAGIC) {
96 tweb_regerror("damaged regexp fed to tweb_regsub");
102 while ((c = *src++) != '\0') {
105 else if (c == '\\' && '0' <= *src && *src <= '9')
110 if (no < 0) { /* Ordinary character. */
111 if (c == '\\' && (*src == '\\' || *src == '&'))
114 } else if (prog->startp[no] != NULL && prog->endp[no] != NULL) {
115 len = prog->endp[no] - prog->startp[no];
116 (void) strncpy(dst, prog->startp[no], len);
118 if (len != 0 && *(dst-1) == '\0') { /* strncpy hit NUL. */
119 tweb_regerror("damaged match string");
127 * tweb_regcomp and tweb_regexec -- tweb_regsub and tweb_regerror are elsewhere
129 * Copyright (c) 1986 by University of Toronto.
130 * Written by Henry Spencer. Not derived from licensed software.
132 * Permission is granted to anyone to use this software for any
133 * purpose on any computer system, and to redistribute it freely,
134 * subject to the following restrictions:
136 * 1. The author is not responsible for the consequences of use of
137 * this software, no matter how awful, even if they arise
138 * from defects in it.
140 * 2. The origin of this software must not be misrepresented, either
141 * by explicit claim or by omission.
143 * 3. Altered versions must be plainly marked as such, and must not
144 * be misrepresented as being the original software.
146 * Beware that some of this code is subtly aware of the way operator
147 * precedence is structured in regular expressions. Serious changes in
148 * regular-expression syntax might require a total rethink.
152 * The "internal use only" fields in regexp.h are present to pass info from
153 * compile to execute that permits the execute phase to run lots faster on
154 * simple cases. They are:
156 * regstart char that must begin a match; '\0' if none obvious
157 * reganch is the match anchored (at beginning-of-line only)?
158 * regmust string (pointer into program) that match must include, or NULL
159 * regmlen length of regmust string
161 * Regstart and reganch permit very fast decisions on suitable starting points
162 * for a match, cutting down the work a lot. Regmust permits fast rejection
163 * of lines that cannot possibly match. The regmust tests are costly enough
164 * that tweb_regcomp() supplies a regmust only if the r.e. contains something
165 * potentially expensive (at present, the only such thing detected is * or +
166 * at the start of the r.e., which can involve a lot of backup). Regmlen is
167 * supplied because the test in tweb_regexec() needs it and tweb_regcomp() is computing
172 * Structure for regexp "program". This is essentially a linear encoding
173 * of a nondeterministic finite-state machine (aka syntax charts or
174 * "railroad normal form" in parsing technology). Each node is an opcode
175 * plus a "next" pointer, possibly plus an operand. "Next" pointers of
176 * all nodes except BRANCH implement concatenation; a "next" pointer with
177 * a BRANCH on both ends of it is connecting two alternatives. (Here we
178 * have one of the subtle syntax dependencies: an individual BRANCH (as
179 * opposed to a collection of them) is never concatenated with anything
180 * because of operator precedence.) The operand of some types of node is
181 * a literal string; for others, it is a node leading into a sub-FSM. In
182 * particular, the operand of a BRANCH node is the first node of the branch.
183 * (NB this is *not* a tree structure: the tail of the branch connects
184 * to the thing following the set of BRANCHes.) The opcodes are:
186 /*#include "regular.h"*/
189 - tweb_regcomp - compile a regular expression into internal code
191 * We can't allocate space until we know how big the compiled form will be,
192 * but we can't compile it (and thus know how big it is) until we've got a
193 * place to put the code. So we cheat: we compile it twice, once with code
194 * generation turned off and size counting turned on, and once "for real".
195 * This also means that we don't allocate space until we are sure that the
196 * thing really will compile successfully, and we never have to move the
197 * code and thus invalidate pointers into it. (Note that it has to be in
198 * one piece because free() must be able to free it all.)
200 * Beware that the optimization-preparation code in here knows about some
201 * of the structure of the compiled regexp.
203 PUBLIC regexp * tweb_regcomp(exp)
208 register char *longest;
213 FAIL("NULL argument");
215 /* First pass: determine size, legality. */
221 if (tweb_reg(0, &flags) == NULL)
224 /* Small enough for pointer-storage convention? */
225 if (regsize >= 32767L) /* Probably could be 65535L. */
226 FAIL("regexp too big");
228 /* Allocate space. */
229 r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
231 FAIL("out of space");
233 /* Second pass: emit code. */
236 regcode = r->program;
238 if (tweb_reg(0, &flags) == NULL)
241 /* Dig out information for optimizations. */
242 r->regstart = '\0'; /* Worst-case defaults. */
246 scan = r->program+1; /* First BRANCH. */
247 if (OP(tweb_regnext(scan)) == END) { /* Only one top-level choice. */
248 scan = OPERAND(scan);
250 /* Starting-point info. */
251 if (OP(scan) == EXACTLY)
252 r->regstart = *OPERAND(scan);
253 else if (OP(scan) == BOL)
257 * If there's something expensive in the r.e., find the
258 * longest literal string that must appear and make it the
259 * regmust. Resolve ties in favor of later strings, since
260 * the regstart check works with the beginning of the r.e.
261 * and avoiding duplication strengthens checking. Not a
262 * strong reason, but sufficient in the absence of others.
267 for (; scan != NULL; scan = tweb_regnext(scan))
268 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
269 longest = OPERAND(scan);
270 len = strlen(OPERAND(scan));
272 r->regmust = longest;
281 - reg - regular expression, i.e. main body or parenthesized thing
283 * Caller must absorb opening parenthesis.
285 * Combining parenthesis handling with the base level of regular expression
286 * is a trifle forced, but the need to tie the tails of the branches to what
287 * follows makes it hard to avoid.
289 PRIVATE char * tweb_reg(paren, flagp)
290 int paren; /* Parenthesized? */
295 register char *ender;
296 register int parno = 0;
299 *flagp = HASWIDTH; /* Tentatively. */
301 /* Make an OPEN node, if parenthesized. */
303 if (regnpar >= NSUBEXP)
307 ret = tweb_regnode(OPEN+parno);
311 /* Pick up the branches, linking them together. */
312 br = tweb_regbranch(&flags);
316 tweb_regtail(ret, br); /* OPEN -> first. */
319 if (!(flags&HASWIDTH))
321 *flagp |= flags&SPSTART;
322 while (*regparse == '|') {
324 br = tweb_regbranch(&flags);
327 tweb_regtail(ret, br); /* BRANCH -> BRANCH. */
328 if (!(flags&HASWIDTH))
330 *flagp |= flags&SPSTART;
333 /* Make a closing node, and hook it on the end. */
334 ender = tweb_regnode((paren) ? CLOSE+parno : END);
335 tweb_regtail(ret, ender);
337 /* Hook the tails of the branches to the closing node. */
338 for (br = ret; br != NULL; br = tweb_regnext(br))
339 tweb_regoptail(br, ender);
341 /* Check for proper termination. */
342 if (paren && *regparse++ != ')') {
343 FAIL("unmatched ()");
344 } else if (!paren && *regparse != '\0') {
345 if (*regparse == ')') {
346 FAIL("unmatched ()");
348 FAIL("junk on end"); /* "Can't happen". */
356 - tweb_regbranch - one alternative of an | operator
358 * Implements the concatenation operator.
360 PRIVATE char * tweb_regbranch(flagp)
364 register char *chain;
365 register char *latest;
368 *flagp = WORST; /* Tentatively. */
370 ret = tweb_regnode(BRANCH);
372 while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
373 latest = tweb_regpiece(&flags);
376 *flagp |= flags&HASWIDTH;
377 if (chain == NULL) /* First piece. */
378 *flagp |= flags&SPSTART;
380 tweb_regtail(chain, latest);
383 if (chain == NULL) /* Loop ran zero times. */
384 (void) tweb_regnode(NOTHING);
390 - tweb_regpiece - something followed by possible [*+?]
392 * Note that the branching code sequences used for ? and the general cases
393 * of * and + are somewhat optimized: they use the same NOTHING node as
394 * both the endmarker for their branch list and the body of the last branch.
395 * It might seem that this node could be dispensed with entirely, but the
396 * endmarker role is not redundant.
398 PRIVATE char * tweb_regpiece(flagp)
406 ret = tweb_regatom(&flags);
416 if (!(flags&HASWIDTH) && op != '?')
417 FAIL("*+ operand could be empty");
418 *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
420 if (op == '*' && (flags&SIMPLE))
421 tweb_reginsert(STAR, ret);
422 else if (op == '*') {
423 /* Emit x* as (x&|), where & means "self". */
424 tweb_reginsert(BRANCH, ret); /* Either x */
425 tweb_regoptail(ret, tweb_regnode(BACK)); /* and loop */
426 tweb_regoptail(ret, ret); /* back */
427 tweb_regtail(ret, tweb_regnode(BRANCH)); /* or */
428 tweb_regtail(ret, tweb_regnode(NOTHING)); /* null. */
429 } else if (op == '+' && (flags&SIMPLE))
430 tweb_reginsert(PLUS, ret);
431 else if (op == '+') {
432 /* Emit x+ as x(&|), where & means "self". */
433 next = tweb_regnode(BRANCH); /* Either */
434 tweb_regtail(ret, next);
435 tweb_regtail(tweb_regnode(BACK), ret); /* loop back */
436 tweb_regtail(next, tweb_regnode(BRANCH)); /* or */
437 tweb_regtail(ret, tweb_regnode(NOTHING)); /* null. */
438 } else if (op == '?') {
439 /* Emit x? as (x|) */
440 tweb_reginsert(BRANCH, ret); /* Either x */
441 tweb_regtail(ret, tweb_regnode(BRANCH)); /* or */
442 next = tweb_regnode(NOTHING); /* null. */
443 tweb_regtail(ret, next);
444 tweb_regoptail(ret, next);
447 if (ISMULT(*regparse))
454 - tweb_regatom - the lowest level
456 * Optimization: gobbles an entire sequence of ordinary characters so that
457 * it can turn them into a single node, which is smaller to store and
458 * faster to run. Backslashed characters are exceptions, each becoming a
459 * separate node; the code is simpler that way and it's not worth fixing.
461 PRIVATE char * tweb_regatom(flagp)
467 *flagp = WORST; /* Tentatively. */
469 switch (*regparse++) {
471 ret = tweb_regnode(BOL);
474 ret = tweb_regnode(EOL);
477 ret = tweb_regnode(ANY);
478 *flagp |= HASWIDTH|SIMPLE;
482 register int classend;
484 if (*regparse == '^') { /* Complement of range. */
485 ret = tweb_regnode(ANYBUT);
488 ret = tweb_regnode(ANYOF);
489 if (*regparse == ']' || *regparse == '-')
490 tweb_regc(*regparse++);
491 while (*regparse != '\0' && *regparse != ']') {
492 if (*regparse == '-') {
494 if (*regparse == ']' || *regparse == '\0')
497 class = UCHARAT(regparse-2)+1;
498 classend = UCHARAT(regparse);
499 if (class > classend+1)
500 FAIL("invalid [] range");
501 for (; class <= classend; class++)
506 tweb_regc(*regparse++);
509 if (*regparse != ']')
510 FAIL("unmatched []");
512 *flagp |= HASWIDTH|SIMPLE;
516 ret = tweb_reg(1, &flags);
519 *flagp |= flags&(HASWIDTH|SPSTART);
524 FAIL("internal urp"); /* Supposed to be caught earlier. */
529 FAIL("?+* follows nothing");
532 if (*regparse == '\0')
534 ret = tweb_regnode(EXACTLY);
535 tweb_regc(*regparse++);
537 *flagp |= HASWIDTH|SIMPLE;
544 len = strcspn(regparse, META);
546 FAIL("internal disaster");
547 ender = *(regparse+len);
548 if (len > 1 && ISMULT(ender))
549 len--; /* Back off clear of ?+* operand. */
553 ret = tweb_regnode(EXACTLY);
555 tweb_regc(*regparse++);
567 - tweb_regnode - emit a node
569 PRIVATE char * tweb_regnode(op)
576 if (ret == ®dummy) {
583 *ptr++ = '\0'; /* Null "next" pointer. */
591 - regc - emit (if appropriate) a byte of code
593 PRIVATE void tweb_regc(b)
596 if (regcode != ®dummy)
603 - tweb_reginsert - insert an operator in front of already-emitted operand
605 * Means relocating the operand.
607 PRIVATE void tweb_reginsert(op, opnd)
613 register char *place;
615 if (regcode == ®dummy) {
626 place = opnd; /* Op node, where operand used to be. */
633 - tweb_regtail - set the next-pointer at the end of a node chain
635 PRIVATE void tweb_regtail(p, val)
646 /* Find last node. */
649 temp = tweb_regnext(scan);
655 if (OP(scan) == BACK)
659 *(scan+1) = (offset>>8)&0377;
660 *(scan+2) = offset&0377;
664 - tweb_regoptail - tweb_regtail on operand of first argument; nop if operandless
666 PRIVATE void tweb_regoptail(p, val)
670 /* "Operandless" and "op != BRANCH" are synonymous in practice. */
671 if (p == NULL || p == ®dummy || OP(p) != BRANCH)
673 tweb_regtail(OPERAND(p), val);
677 * tweb_regexec and friends
681 * Global work variables for tweb_regexec().
683 static char *reginput; /* String-input pointer. */
684 static char *regbol; /* Beginning of input, for ^ check. */
685 static char **regstartp; /* Pointer to startp array. */
686 static char **regendp; /* Ditto for endp. */
691 STATIC int tweb_regtry();
692 STATIC int tweb_regmatch();
693 STATIC int tweb_regrepeat();
698 STATIC char *tweb_regprop();
702 - tweb_regexec - match a regexp against a string
705 PUBLIC tweb_regexec(prog, string)
706 register regexp *prog;
707 register char *string;
710 extern char *strchr();
713 if (prog == NULL || string == NULL) {
714 tweb_regerror("NULL parameter");
718 /* Check validity of program. */
719 if (UCHARAT(prog->program) != MAGIC) {
720 tweb_regerror("corrupted program");
724 /* If there is a "must appear" string, look for it. */
725 if (prog->regmust != NULL) {
727 while ((s = strchr(s, prog->regmust[0])) != NULL) {
728 if (strncmp(s, prog->regmust, prog->regmlen) == 0)
729 break; /* Found it. */
732 if (s == NULL) /* Not present. */
736 /* Mark beginning of line for ^ . */
739 /* Simplest case: anchored match need be tried only once. */
741 return(tweb_regtry(prog, string));
743 /* Messy cases: unanchored match. */
745 if (prog->regstart != '\0')
746 /* We know what char it must start with. */
747 while ((s = strchr(s, prog->regstart)) != NULL) {
748 if (tweb_regtry(prog, s))
753 /* We don't -- general case. */
755 if (tweb_regtry(prog, s))
757 } while (*s++ != '\0');
764 - tweb_regtry - try match at specific point
766 PRIVATE int tweb_regtry(prog, string)
775 regstartp = prog->startp;
776 regendp = prog->endp;
780 for (i = NSUBEXP; i > 0; i--) {
784 if (tweb_regmatch(prog->program + 1)) {
785 prog->startp[0] = string;
786 prog->endp[0] = reginput;
793 - tweb_regmatch - main matching routine
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
802 PRIVATE int tweb_regmatch(prog)
805 register char *scan; /* Current node. */
806 char *next; /* Next node. */
807 extern char *strchr();
811 if (scan != NULL && regnarrate)
812 fprintf(stderr, "%s(\n", tweb_regprop(scan));
814 while (scan != NULL) {
817 fprintf(stderr, "%s...\n", tweb_regprop(scan));
819 next = tweb_regnext(scan);
823 if (reginput != regbol)
827 if (*reginput != '\0')
831 if (*reginput == '\0')
839 opnd = OPERAND(scan);
840 /* Inline the first character, for speed. */
841 if (*opnd != *reginput)
844 if (len > 1 && strncmp(opnd, reginput, len) != 0)
850 if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
855 if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
875 no = OP(scan) - OPEN;
878 if (tweb_regmatch(next)) {
880 * Don't set startp if some later
881 * invocation of the same parentheses
884 if (regstartp[no] == NULL)
885 regstartp[no] = save;
903 no = OP(scan) - CLOSE;
906 if (tweb_regmatch(next)) {
908 * Don't set endp if some later
909 * invocation of the same parentheses
912 if (regendp[no] == NULL)
922 if (OP(next) != BRANCH) /* No choice. */
923 next = OPERAND(scan); /* Avoid recursion. */
927 if (tweb_regmatch(OPERAND(scan)))
930 scan = tweb_regnext(scan);
931 } while (scan != NULL && OP(scan) == BRANCH);
939 register char nextch;
945 * Lookahead to avoid useless match attempts
946 * when we know what character comes next.
949 if (OP(next) == EXACTLY)
950 nextch = *OPERAND(next);
951 min = (OP(scan) == STAR) ? 0 : 1;
953 no = tweb_regrepeat(OPERAND(scan));
955 /* If it could work, try it. */
956 if (nextch == '\0' || *reginput == nextch)
957 if (tweb_regmatch(next))
959 /* Couldn't or didn't -- back up. */
961 reginput = save + no;
967 return(1); /* Success! */
970 tweb_regerror("memory corruption");
979 * We get here only if there's trouble -- normally "case END" is
980 * the terminating point.
982 tweb_regerror("corrupted pointers");
987 - tweb_regrepeat - repeatedly match something simple, report how many
989 PRIVATE int tweb_regrepeat(p)
992 register int count = 0;
995 extern char *strchr();
1001 count = strlen(scan);
1005 while (*opnd == *scan) {
1011 while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
1017 while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
1022 default: /* Oh dear. Called inappropriately. */
1023 tweb_regerror("internal foulup");
1024 count = 0; /* Best compromise. */
1033 - tweb_regnext - dig the "next" pointer out of a node
1035 PRIVATE char * tweb_regnext(p)
1038 register int offset;
1055 PRIVATE char *tweb_regprop();
1058 - tweb_regdump - dump a regexp onto stdout in vaguely comprehensible form
1060 PUBLIC void tweb_regdump(r)
1064 register char op = EXACTLY; /* Arbitrary non-END op. */
1065 register char *next;
1066 extern char *strchr();
1070 while (op != END) { /* While that wasn't END last time... */
1072 printf("%2d%s", s-r->program, tweb_regprop(s)); /* Where, what. */
1073 next = tweb_regnext(s);
1074 if (next == NULL) /* Next ptr. */
1077 printf("(%d)", (s-r->program)+(next-s));
1079 if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
1080 /* Literal string, where present. */
1081 while (*s != '\0') {
1090 /* Header fields of interest. */
1091 if (r->regstart != '\0')
1092 printf("start `%c' ", r->regstart);
1094 printf("anchored ");
1095 if (r->regmust != NULL)
1096 printf("must have \"%s\"", r->regmust);
1101 - tweb_regprop - printable representation of opcode
1103 PRIVATE char * tweb_regprop(op)
1107 static char buf[50];
1109 (void) strcpy(buf, ":");
1151 sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
1163 sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
1173 tweb_regerror("corrupted opcode");
1177 (void) strcat(buf, p);
1183 * The following is provided for those people who do not have strcspn() in
1184 * their C libraries. They should get off their butts and do something
1185 * about it; at least one public-domain implementation of those (highly
1186 * useful) string routines has been published on Usenet.
1190 * strcspn - find length of initial segment of s1 consisting entirely
1191 * of characters not from s2
1194 PRIVATE int strcspn(s1, s2)
1198 register char *scan1;
1199 register char *scan2;
1203 for (scan1 = s1; *scan1 != '\0'; scan1++) {
1204 for (scan2 = s2; *scan2 != '\0';) /* ++ moved down. */
1205 if (*scan1 == *scan2++)