8000 minix/commands/awk/regexp.c at R3.1.4 · philipdongfei/minix · GitHub
[go: up one dir, main page]

Skip to content

Latest commit

 

History

History
executable file
·
1440 lines (1307 loc) · 30.7 KB

regexp.c

File metadata and controls

executable file
·
1440 lines (1307 loc) · 30.7 KB
while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
latest = regpiece(&flags);
if (latest == NULL)
return(NULL);
*flagp |= flags&HASWIDTH;
if (chain == NULL) /* First piece. */
*flagp |= flags&SPSTART;
else
regtail(chain, latest);
chain = latest;
}
if (chain == NULL) /* Loop ran zero times. */
(void) regnode(NOTHING);
return(ret);
}
/*
- regpiece - something followed by possible [*+?]
*
* Note that the branching code sequences used for ? and the general cases
* of * and + are somewhat optimized: they use the same NOTHING node as
* both the endmarker for their branch list and the body of the last branch.
* It might seem that this node could be dispensed with entirely, but the
* endmarker role is not redundant.
*/
static ushort *
regpiece(flagp)
int *flagp;
{
register ushort *ret;
register ushort op;
register ushort *next;
int flags;
ret = regatom(&flags);
if (ret == NULL)
return(NULL);
op = *regparse;
if (!ISMULT(op)) {
*flagp = flags;
return(ret);
}
if (!(flags&HASWIDTH) && op != '?')
FAIL("*+ operand could be empty");
*flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
if (op == '*' && (flags&SIMPLE))
reginsert(STAR, ret);
else if (op == '*') {
/* Emit x* as (x&|), where & means "self". */
reginsert(BRANCH, ret); /* Either x */
regoptail(ret, regnode(BACK)); /* and loop */
regoptail(ret, ret); /* back */
regtail(ret, regnode(BRANCH)); /* or */
regtail(ret, regnode(NOTHING)); /* null. */
} else if (op == '+' && (flags&SIMPLE))
reginsert(PLUS, ret);
else if (op == '+') {
/* Emit x+ as x(&|), where & means "self". */
next = regnode(BRANCH); /* Either */
regtail(ret, next);
regtail(regnode(BACK), ret); /* loop back */
regtail(next, regnode(BRANCH)); /* or */
regtail(ret, regnode(NOTHING)); /* null. */
} else if (op == '?') {
/* Emit x? as (x|) */
reginsert(BRANCH, ret); /* Either x */
regtail(ret, regnode(BRANCH)); /* or */
next = regnode(NOTHING); /* null. */
regtail(ret, next);
regoptail(ret, next);
}
regparse++;
if (ISMULT(*regparse))
FAIL("nested *?+");
return(ret);
}
/*
- regatom - the lowest level
*
* Optimization: gobbles an entire sequence of ordinary characters so that
* it can turn them into a single node, which is smaller to store and
* faster to run. Backslashed characters are exceptions, each becoming a
* separate node; the code is simpler that way and it's not worth fixing.
*/
static ushort *
regatom(flagp)
int *flagp;
{
register ushort *ret;
int flags;
ushort c, d;
*flagp = WORST; /* Tentatively. */
switch ((int) *regparse++) {
case '^':
ret = regnode(BOL);
break;
case '$':
ret = regnode(EOL);
break;
case '.':
ret = regnode(ANY);
*flagp |= HASWIDTH|SIMPLE;
break;
case '[': {
register int class;
register int classend;
register int c;
if (*regparse == '^') { /* Complement of range. */
ret = regnode(ANYBUT);
regparse++;
} else
ret = regnode(ANYOF);
if (*regparse == ']' || *regparse == '-')
regc(*regparse++);
while (*regparse != '\0' && *regparse != ']') {
if (*regparse == '-') {
regparse++;
if (*regparse == ']' || *regparse == '\0')
regc((ushort) '-');
else {
class = UCHARAT(regparse-2)+1;
classend = UCHARAT(regparse);
if (class > classend+1)
FAIL("invalid [] range");
regc((ushort) 0xffff);
regc((ushort) class);
regc((ushort) classend);
regparse++;
}
} else {
if ((c = *regparse++) == '\\') {
if ((c = *regparse++) == 'n')
c = '\n';
else if (c == 't')
c = '\t';
}
regc(c);
}
}
regc((ushort) 0);
if (*regparse != ']')
FAIL("unmatched []");
regparse++;
*flagp |= HASWIDTH|SIMPLE;
}
break;
case '(':
ret = reg(1, &flags);
if (ret == NULL)
return(NULL);
*flagp |= flags&(HASWIDTH|SPSTART);
break;
case '\0':
case '|':
case ')':
FAIL("internal urp"); /* Supposed to be caught earlier. */
break;
case '?':
case '+':
case '*':
FAIL("?+* follows nothing");
break;
case '\\':
if (*regparse == '\0')
FAIL("trailing \\");
ret = regnode(EXACTLY);
/*
regc(*regparse++);
*/
c = *regparse++;
if (c == 'n')
c = '\n';
else if (c == 't')
c = '\t';
else if (c == 'f')
c = '\f';
else if (c == '\r')
c = '\r';
else if (c == '\b')
c = '\b';
else if (IsDigid(c)) {
d = c - '0';
if (IsDigid(*regparse)) {
d = d * 8 + *regparse++ - '0';
if (IsDigid(*regparse))
d = d * 8 + *regparse++ - '0';
}
c = d;
}
regc(c);
regc((ushort) 0);
*flagp |= HASWIDTH|SIMPLE;
break;
default: {
register int len;
register char ender;
regparse--;
len = Strcspn(regparse, META);
if (len <= 0)
FAIL("internal disaster");
ender = *(regparse+len);
if (len > 1 && ISMULT(ender))
len--; /* Back off clear of ?+* operand. */
*flagp |= HASWIDTH;
if (len == 1)
*flagp |= SIMPLE;
ret = regnode(EXACTLY);
while (len > 0) {
regc(*regparse++);
len--;
}
regc((ushort) 0);
}
break;
}
return(ret);
}
IsDigid(c) ushort c;
{
return '0' <= c && c <= '9';
}
/*
- regnode - emit a node
*/
static ushort * /* Location. */
regnode(op)
ushort op;
{
register ushort *ret;
register ushort *ptr;
ret = regcode;
if (ret == &regdummy) {
regsize += 3;
return(ret);
}
ptr = ret;
*ptr++ = op;
*ptr++ = '\0'; /* Null "next" pointer. */
*ptr++ = '\0';
regcode = ptr;
return(ret);
}
/*
- regc - emit (if appropriate) a byte of code
*/
static void
regc(b)
ushort b;
{
if (regcode != &regdummy)
*regcode++ = b;
else
regsize++;
}
/*
- reginsert - insert an operator in front of already-emitted operand
*
* Means relocating the operand.
*/
static void
reginsert(op, opnd)
ushort op;
ushort *opnd;
{
register ushort *src;
register ushort *dst;
register ushort *place;
if (regcode == &regdummy) {
regsize += 3;
return;
}
src = regcode;
regcode += 3;
dst = regcode;
while (src > opnd)
*--dst = *--src;
place = opnd; /* Op node, where operand used to be. */
*place++ = op;
*place++ = '\0';
*place++ = '\0';
}
/*
- regtail - set the next-pointer at the end of a node chain
*/
static void
regtail(p, val)
ushort *p;
ushort *val;
{
register ushort *scan;
register ushort *temp;
register int offset;
if (p == &regdummy)
return;
/* Find last node. */
scan = p;
for (;;) {
temp = regnext(scan);
if (temp == NULL)
break;
scan = temp;
}
if (OP(scan) == BACK)
offset = scan - val;
else
offset = val - scan;
*(scan+1) = (offset>>8)&0377;
*(scan+2) = offset&0377;
}
/*
- regoptail - regtail on operand of first argument; nop if operandless
*/
static void
regoptail(p, val)
ushort *p;
ushort *val;
{
/* "Operandless" and "op != BRANCH" are synonymous in practice. */
if (p == NULL || p == &regdummy || OP(p) != BRANCH)
return;
regtail(OPERAND(p), val);
}
/*
* regexec and friends
*/
/*
* Global work variables for regexec().
*/
static ushort *reginput; /* String-input pointer. */
static ushort *regbol; /* Beginning of input, for ^ check. */
static ushort **regstartp; /* Pointer to startp array. */
static ushort **regendp; /* Ditto for endp. */
/*
* Forwards.
*/
STATIC int regtry();
STATIC int regmatch();
STATIC int regrepeat();
#ifdef DEBUG
int regnarrate = 0;
void regdump();
STATIC char *regprop();
#endif
/*
- regexec - match a regexp against a string
*/
int
regexec(prog, string, bolflag)
register regexp *prog;
register ushort *string;
int bolflag;
{
register ushort *s;
extern ushort *Strchr();
/* Be paranoid... */
if (prog == NULL || string == NULL) {
regerror("NULL parameter");
return(0);
}
/* Check validity of program. */
if (prog->program[0] != MAGIC) {
regerror("corrupted program");
return(0);
}
/* If there is a "must appear" string, look for it. */
if (prog->regmust != NULL) {
s = string;
while ((s = Strchr(s, prog->regmust[0])) != NULL) {
if (Strncmp(s, prog->regmust, prog->regmlen) == 0)
break; /* Found it. */
s++;
}
if (s == NULL) /* Not present. */
return(0);
}
/* Mark beginning of line for ^ . */
if(bolflag)
regbol = string;
else
regbol = NULL;
/* Simplest case: anchored match need be tried only once. */
if (prog->reganch)
return(regtry(prog, string));
/* Messy cases: unanchored match. */
s = string;
if (prog->regstart != '\0') {
/* We know what char it must start with. */
while ((s = Strchr(s, prog->regstart)) != NULL) {
if (regtry(prog, s))
return(1);
s++;
}
}
else
/* We don't -- general case. */
do {
if (regtry(prog, s))
return(1);
} while (*s++ != '\0');
/* Failure. */
return(0);
}
/*
- regtry - try match at specific point
*/
static int /* 0 failure, 1 success */
regtry(prog, string)
regexp *prog;
ushort *string;
{
register int i;
register ushort **sp;
register ushort **ep;
reginput = string;
regstartp = prog->startp;
regendp = prog->endp;
sp = prog->startp;
ep = prog->endp;
for (i = NSUBEXP; i > 0; i--) {
*sp++ = NULL;
*ep++ = NULL;
}
if (regmatch(prog->program + 1)) {
prog->startp[0] = string;
prog->endp[0] = reginput;
return(1);
} else
return(0);
}
/*
- regmatch - main matching routine
*
* Conceptually the strategy is simple: check to see whether the current
* node matches, call self recursively to see whether the rest matches,
* and then act accordingly. In practice we make some effort to avoid
* recursion, in particular by going through "ordinary" nodes (that don't
* need to know whether the rest of the match failed) by a loop instead of
* by recursion.
*/
static int /* 0 failure, 1 success */
regmatch(prog)
ushort *prog;
{
register ushort *scan; /* Current node. */
ushort *next; /* Next node. */
extern ushort *Strchr();
scan = prog;
#ifdef DEBUG
if (scan != NULL && regnarrate)
fprintf(stderr, "%s(\n", regprop(scan));
#endif
while (scan != NULL) {
#ifdef DEBUG
if (regnarrate)
fprintf(stderr, "%s...\n", regprop(scan));
#endif
next = regnext(scan);
switch ((int) OP(scan)) {
case BOL:
if (reginput != regbol)
return(0);
break;
case EOL:
if (*reginput != '\0')
return(0);
break;
case ANY:
if (*reginput == '\0')
return(0);
reginput++;
break;
case EXACTLY: {
register int len;
register ushort *opnd;
opnd = OPERAND(scan);
/* Inline the first character, for speed. */
if (*opnd != *reginput)
return(0);
len = Strlen(opnd);
if (len > 1 && Strncmp(opnd, reginput, len) != 0)
return(0);
reginput += len;
}
break;
case ANYOF:
if (*reginput == '\0' || isthere(OPERAND(scan), *reginput) == 0)
return(0);
reginput++;
break;
case ANYBUT:
if (*reginput == '\0' || isthere(OPERAND(scan), *reginput) != 0)
return(0);
reginput++;
break;
case NOTHING:
break;
case BACK:
break;
case OPEN+1:
case OPEN+2:
case OPEN+3:
case OPEN+4:
case OPEN+5:
case OPEN+6:
case OPEN+7:
case OPEN+8:
case OPEN+9: {
register int no;
register ushort *save;
no = OP(scan) - OPEN;
save = reginput;
if (regmatch(next)) {
/*
* Don't set startp if some later
* invocation of the same parentheses
* already has.
*/
if (regstartp[no] == NULL)
regstartp[no] = save;
return(1);
} else
return(0);
}
break;
case CLOSE+1:
case CLOSE+2:
case CLOSE+3:
case CLOSE+4:
case CLOSE+5:
case CLOSE+6:
case CLOSE+7:
case CLOSE+8:
case CLOSE+9: {
register int no;
register ushort *save;
no = OP(scan) - CLOSE;
save = reginput;
if (regmatch(next)) {
/*
* Don't set endp if some later
* invocation of the same parentheses
* already has.
*/
if (regendp[no] == NULL)
regendp[no] = save;
return(1);
} else
return(0);
}
break;
case BRANCH: {
register ushort *save;
if (OP(next) != BRANCH) /* No choice. */
next = OPERAND(scan); /* Avoid recursion. */
else {
do {
save = reginput;
if (regmatch(OPERAND(scan)))
return(1);
reginput = save;
scan = regnext(scan);
} while (scan != NULL && OP(scan) == BRANCH);
return(0);
/* NOTREACHED */
}
}
break;
case STAR:
case PLUS: {
register ushort nextch;
register int no;
register ushort *save;
register int min;
/*
* Lookahead to avoid useless match attempts
* when we know what character comes next.
*/
nextch = '\0';
if (OP(next) == EXACTLY)
nextch = *OPERAND(next);
0