cmd/awk/b.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*  Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
/*    All Rights Reserved   */

#pragma ident   "%Z%%M% %I% %E% SMI"

#define DEBUG

#include "awk.h"
#include "y.tab.h"

#define HAT (NCHARS-1)  /* matches ^ in regular expr */
                /* NCHARS is 2**n */
#define MAXLIN (3 * LINE_MAX)

#define type(v)     (v)->nobj
#define left(v)     (v)->narg[0]
#define right(v)    (v)->narg[1]
#define parent(v)   (v)->nnext

#define LEAF    case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL:
#define UNARY   case STAR: case PLUS: case QUEST:

/*
 * encoding in tree Nodes:
 *  leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL):
 *      left is index, right contains value or pointer to value
 *  unary (STAR, PLUS, QUEST): left is child, right is null
 *  binary (CAT, OR): left and right are children
 *  parent contains pointer to parent
 */

int setvec[MAXLIN];
int tmpset[MAXLIN];
Node    *point[MAXLIN];

int rtok;       /* next token in current re */
int rlxval;
uchar   *rlxstr;
uchar   *prestr;    /* current position in current re */
uchar   *lastre;    /* origin of last re */

static  int setcnt;
static  int poscnt;

uchar   *patbeg;
int patlen;

#define NFA 20  /* cache this many dynamic fa's */
fa  *fatab[NFA];
int nfatab  = 0;    /* entries in fatab */

static fa   *mkdfa(uchar *, int);
static int  makeinit(fa *, int);
static void penter(Node *);
static void freetr(Node *);
static void overflo(char *);
static void cfoll(fa *, Node *);
static void follow(Node *);
static Node *reparse(uchar *);
static int  relex(void);
static void freefa(fa *);
static int  cgoto(fa *, int, int);

fa *
makedfa(uchar *s, int anchor)   /* returns dfa for reg expr s */
{
    int i, use, nuse;
    fa *pfa;

    if (compile_time)   /* a constant for sure */
        return (mkdfa(s, anchor));
    for (i = 0; i < nfatab; i++) {  /* is it there already? */
        if (fatab[i]->anchor == anchor &&
            strcmp((char *)fatab[i]->restr, (char *)s) == 0) {
            fatab[i]->use++;
            return (fatab[i]);
        }
    }
    pfa = mkdfa(s, anchor);
    if (nfatab < NFA) { /* room for another */
        fatab[nfatab] = pfa;
        fatab[nfatab]->use = 1;
        nfatab++;
        return (pfa);
    }
    use = fatab[0]->use;    /* replace least-recently used */
    nuse = 0;
    for (i = 1; i < nfatab; i++)
        if (fatab[i]->use < use) {
            use = fatab[i]->use;
            nuse = i;
        }
    freefa(fatab[nuse]);
    fatab[nuse] = pfa;
    pfa->use = 1;
    return (pfa);
}

fa *
mkdfa(uchar *s, int anchor) /* does the real work of making a dfa */
    /* anchor = 1 for anchored matches, else 0 */
{
    Node *p, *p1;
    fa *f;

    p = reparse(s);
    p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p);
        /* put ALL STAR in front of reg.  exp. */
    p1 = op2(CAT, p1, op2(FINAL, NIL, NIL));
        /* put FINAL after reg.  exp. */

    poscnt = 0;
    penter(p1); /* enter parent pointers and leaf indices */
    if ((f = (fa *)calloc(1, sizeof (fa) + poscnt * sizeof (rrow))) == NULL)
        overflo("no room for fa");
    /* penter has computed number of positions in re */
    f->accept = poscnt-1;
    cfoll(f, p1);   /* set up follow sets */
    freetr(p1);
    if ((f->posns[0] =
        (int *)calloc(1, *(f->re[0].lfollow) * sizeof (int))) == NULL) {
            overflo("out of space in makedfa");
    }
    if ((f->posns[1] = (int *)calloc(1, sizeof (int))) == NULL)
        overflo("out of space in makedfa");
    *f->posns[1] = 0;
    f->initstat = makeinit(f, anchor);
    f->anchor = anchor;
    f->restr = tostring(s);
    return (f);
}

static int
makeinit(fa *f, int anchor)
{
    register int i, k;

    f->curstat = 2;
    f->out[2] = 0;
    f->reset = 0;
    k = *(f->re[0].lfollow);
    xfree(f->posns[2]);
    if ((f->posns[2] = (int *)calloc(1, (k+1) * sizeof (int))) == NULL)
        overflo("out of space in makeinit");
    for (i = 0; i <= k; i++) {
        (f->posns[2])[i] = (f->re[0].lfollow)[i];
    }
    if ((f->posns[2])[1] == f->accept)
        f->out[2] = 1;
    for (i = 0; i < NCHARS; i++)
        f->gototab[2][i] = 0;
    f->curstat = cgoto(f, 2, HAT);
    if (anchor) {
        *f->posns[2] = k-1; /* leave out position 0 */
        for (i = 0; i < k; i++) {
            (f->posns[0])[i] = (f->posns[2])[i];
        }

        f->out[0] = f->out[2];
        if (f->curstat != 2)
            --(*f->posns[f->curstat]);
    }
    return (f->curstat);
}

void
penter(Node *p) /* set up parent pointers and leaf indices */
{
    switch (type(p)) {
    LEAF
        left(p) = (Node *) poscnt;
        point[poscnt++] = p;
        break;
    UNARY
        penter(left(p));
        parent(left(p)) = p;
        break;
    case CAT:
    case OR:
        penter(left(p));
        penter(right(p));
        parent(left(p)) = p;
        parent(right(p)) = p;
        break;
    default:
        ERROR "unknown type %d in penter", type(p) FATAL;
        break;
    }
}

static void
freetr(Node *p) /* free parse tree */
{
    switch (type(p)) {
    LEAF
        xfree(p);
        break;
    UNARY
        freetr(left(p));
        xfree(p);
        break;
    case CAT:
    case OR:
        freetr(left(p));
        freetr(right(p));
        xfree(p);
        break;
    default:
        ERROR "unknown type %d in freetr", type(p) FATAL;
        break;
    }
}

uchar *
cclenter(uchar *p)
{
    register int i, c;
    uchar *op, *chars, *ret;
    size_t  bsize;

    init_buf(&chars, &bsize, LINE_INCR);
    op = p;
    i = 0;
    while ((c = *p++) != 0) {
        if (c == '\\') {
            if ((c = *p++) == 't')
                c = '\t';
            else if (c == 'n')
                c = '\n';
            else if (c == 'f')
                c = '\f';
            else if (c == 'r')
                c = '\r';
            else if (c == 'b')
                c = '\b';
            else if (c == '\\')
                c = '\\';
            else if (isdigit(c)) {
                int n = c - '0';
                if (isdigit(*p)) {
                    n = 8 * n + *p++ - '0';
                    if (isdigit(*p))
                        n = 8 * n + *p++ - '0';
                }
                c = n;
            } /* else */
                /* c = c; */
        } else if (c == '-' && i > 0 && chars[i-1] != 0) {
            if (*p != 0) {
                c = chars[i-1];
                while ((uchar)c < *p) { /* fails if *p is \\ */
                    expand_buf(&chars, &bsize, i);
                    chars[i++] = ++c;
                }
                p++;
                continue;
            }
        }
        expand_buf(&chars, &bsize, i);
        chars[i++] = c;
    }
    chars[i++] = '\0';
    dprintf(("cclenter: in = |%s|, out = |%s|\n", op, chars));
    xfree(op);
    ret = tostring(chars);
    free(chars);
    return (ret);
}

static void
overflo(char *s)
{
    ERROR "regular expression too big: %s", gettext((char *)s) FATAL;
}

/* enter follow set of each leaf of vertex v into lfollow[leaf] */
static void
cfoll(fa *f, Node *v)
{
    register int i;
    register int *p;

    switch (type(v)) {
    LEAF
        f->re[(int)left(v)].ltype = type(v);
        f->re[(int)left(v)].lval = (int)right(v);
        for (i = 0; i <= f->accept; i++)
            setvec[i] = 0;
        setcnt = 0;
        follow(v);  /* computes setvec and setcnt */
        if ((p = (int *)calloc(1, (setcnt+1) * sizeof (int))) == NULL)
            overflo("follow set overflow");
        f->re[(int)left(v)].lfollow = p;
        *p = setcnt;
        for (i = f->accept; i >= 0; i--) {
            if (setvec[i] == 1)
                *++p = i;
        }
        break;
    UNARY
        cfoll(f, left(v));
        break;
    case CAT:
    case OR:
        cfoll(f, left(v));
        cfoll(f, right(v));
        break;
    default:
        ERROR "unknown type %d in cfoll", type(v) FATAL;
    }
}

/*
 * collects initially active leaves of p into setvec
 * returns 0 or 1 depending on whether p matches empty string
 */
static int
first(Node *p)
{
    register int b;

    switch (type(p)) {
    LEAF
        if (setvec[(int)left(p)] != 1) {
            setvec[(int)left(p)] = 1;
            setcnt++;
        }
        if (type(p) == CCL && (*(uchar *)right(p)) == '\0')
            return (0);     /* empty CCL */
        else
            return (1);
    case PLUS:
        if (first(left(p)) == 0)
            return (0);
        return (1);
    case STAR:
    case QUEST:
        (void) first(left(p));
        return (0);
    case CAT:
        if (first(left(p)) == 0 && first(right(p)) == 0)
            return (0);
        return (1);
    case OR:
        b = first(right(p));
        if (first(left(p)) == 0 || b == 0)
            return (0);
        return (1);
    }
    ERROR "unknown type %d in first", type(p) FATAL;
    return (-1);
}

/* collects leaves that can follow v into setvec */
static void
follow(Node *v)
{
    Node *p;

    if (type(v) == FINAL)
        return;
    p = parent(v);
    switch (type(p)) {
    case STAR:
    case PLUS:
        (void) first(v);
        follow(p);
        return;

    case OR:
    case QUEST:
        follow(p);
        return;

    case CAT:
        if (v == left(p)) { /* v is left child of p */
            if (first(right(p)) == 0) {
                follow(p);
                return;
            }
        } else      /* v is right child */
            follow(p);
        return;
    default:
        ERROR "unknown type %d in follow", type(p) FATAL;
        break;
    }
}

static int
member(uchar c, uchar *s)   /* is c in s? */
{
    while (*s)
        if (c == *s++)
            return (1);
    return (0);
}


int
match(fa *f, uchar *p)
{
    register int s, ns;

    s = f->reset ? makeinit(f, 0) : f->initstat;
    if (f->out[s])
        return (1);
    do {
        if ((ns = f->gototab[s][*p]) != 0)
            s = ns;
        else
            s = cgoto(f, s, *p);
        if (f->out[s])
            return (1);
    } while (*p++ != 0);
    return (0);
}

int
pmatch(fa *f, uchar *p)
{
    register int s, ns;
    register uchar *q;
    int i, k;

    if (f->reset) {
        f->initstat = s = makeinit(f, 1);
    } else {
        s = f->initstat;
    }
    patbeg = p;
    patlen = -1;
    do {
        q = p;
        do {
            if (f->out[s])      /* final state */
                patlen = q-p;
            if ((ns = f->gototab[s][*q]) != 0)
                s = ns;
            else
                s = cgoto(f, s, *q);
            if (s == 1) {   /* no transition */
                if (patlen >= 0) {
                    patbeg = p;
                    return (1);
                } else
                    goto nextin;    /* no match */
            }
        } while (*q++ != 0);
        if (f->out[s])
            patlen = q - p - 1; /* don't count $ */
        if (patlen >= 0) {
            patbeg = p;
            return (1);
        }
    nextin:
        s = 2;
        if (f->reset) {
            for (i = 2; i <= f->curstat; i++)
                xfree(f->posns[i]);
            k = *f->posns[0];
            if ((f->posns[2] =
                (int *)calloc(1, (k + 1) * sizeof (int))) == NULL) {
                overflo("out of space in pmatch");
            }
            for (i = 0; i <= k; i++)
                (f->posns[2])[i] = (f->posns[0])[i];
            f->initstat = f->curstat = 2;
            f->out[2] = f->out[0];
            for (i = 0; i < NCHARS; i++)
                f->gototab[2][i] = 0;
        }
    } while (*p++ != 0);
    return (0);
}

int
nematch(fa *f, uchar *p)
{
    register int s, ns;
    register uchar *q;
    int i, k;

    if (f->reset) {
        f->initstat = s = makeinit(f, 1);
    } else {
        s = f->initstat;
    }
    patlen = -1;
    while (*p) {
        q = p;
        do {
            if (f->out[s])      /* final state */
                patlen = q-p;
            if ((ns = f->gototab[s][*q]) != 0)
                s = ns;
            else
                s = cgoto(f, s, *q);
            if (s == 1) {   /* no transition */
                if (patlen > 0) {
                    patbeg = p;
                    return (1);
                } else
                    goto nnextin;   /* no nonempty match */
            }
        } while (*q++ != 0);
        if (f->out[s])
            patlen = q - p - 1; /* don't count $ */
        if (patlen > 0) {
            patbeg = p;
            return (1);
        }
    nnextin:
        s = 2;
        if (f->reset) {
            for (i = 2; i <= f->curstat; i++)
                xfree(f->posns[i]);
            k = *f->posns[0];
            if ((f->posns[2] =
                (int *)calloc(1, (k + 1) * sizeof (int))) == NULL) {
                overflo("out of state space");
            }
            for (i = 0; i <= k; i++)
                (f->posns[2])[i] = (f->posns[0])[i];
            f->initstat = f->curstat = 2;
            f->out[2] = f->out[0];
            for (i = 0; i < NCHARS; i++)
                f->gototab[2][i] = 0;
        }
        p++;
    }
    return (0);
}

static Node *regexp(void), *primary(void), *concat(Node *);
static Node *alt(Node *), *unary(Node *);

static Node *
reparse(uchar *p)
{
    /* parses regular expression pointed to by p */
    /* uses relex() to scan regular expression */
    Node *np;

    dprintf(("reparse <%s>\n", p));
    lastre = prestr = p;    /* prestr points to string to be parsed */
    rtok = relex();
    if (rtok == '\0')
        ERROR "empty regular expression" FATAL;
    np = regexp();
    if (rtok == '\0') {
        return (np);
    } else {
        ERROR "syntax error in regular expression %s at %s",
            lastre, prestr FATAL;
    }
    /*NOTREACHED*/
    return (NULL);
}

static Node *
regexp(void)
{
    return (alt(concat(primary())));
}

static Node *
primary(void)
{
    Node *np;

    switch (rtok) {
    case CHAR:
        np = op2(CHAR, NIL, (Node *)rlxval);
        rtok = relex();
        return (unary(np));
    case ALL:
        rtok = relex();
        return (unary(op2(ALL, NIL, NIL)));
    case DOT:
        rtok = relex();
        return (unary(op2(DOT, NIL, NIL)));
    case CCL:
        /*LINTED align*/
        np = op2(CCL, NIL, (Node *)cclenter(rlxstr));
        rtok = relex();
        return (unary(np));
    case NCCL:
        /*LINTED align*/
        np = op2(NCCL, NIL, (Node *)cclenter(rlxstr));
        rtok = relex();
        return (unary(np));
    case '^':
        rtok = relex();
        return (unary(op2(CHAR, NIL, (Node *)HAT)));
    case '$':
        rtok = relex();
        return (unary(op2(CHAR, NIL, NIL)));
    case '(':
        rtok = relex();
        if (rtok == ')') {  /* special pleading for () */
            rtok = relex();
            return (unary(op2(CCL, NIL,
                /*LINTED align*/
                (Node *)tostring((uchar *)""))));
        }
        np = regexp();
        if (rtok == ')') {
            rtok = relex();
            return (unary(np));
        } else {
            ERROR "syntax error in regular expression %s at %s",
                lastre, prestr FATAL;
        }
    default:
        ERROR "illegal primary in regular expression %s at %s",
            lastre, prestr FATAL;
    }
    /*NOTREACHED*/
    return (NULL);
}

static Node *
concat(Node *np)
{
    switch (rtok) {
    case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(':
        return (concat(op2(CAT, np, primary())));
    default:
        return (np);
    }
}

static Node *
alt(Node *np)
{
    if (rtok == OR) {
        rtok = relex();
        return (alt(op2(OR, np, concat(primary()))));
    }
    return (np);
}

static Node *
unary(Node *np)
{
    switch (rtok) {
    case STAR:
        rtok = relex();
        return (unary(op2(STAR, np, NIL)));
    case PLUS:
        rtok = relex();
        return (unary(op2(PLUS, np, NIL)));
    case QUEST:
        rtok = relex();
        return (unary(op2(QUEST, np, NIL)));
    default:
        return (np);
    }
}

static int
relex(void)     /* lexical analyzer for reparse */
{
    register int c;
    uchar *cbuf;
    int clen, cflag;

    switch (c = *prestr++) {
    case '|': return OR;
    case '*': return STAR;
    case '+': return PLUS;
    case '?': return QUEST;
    case '.': return DOT;
    case '\0': prestr--; return '\0';
    case '^':
    case '$':
    case '(':
    case ')':
        return (c);
    case '\\':
        if ((c = *prestr++) == 't')
            c = '\t';
        else if (c == 'n')
            c = '\n';
        else if (c == 'f')
            c = '\f';
        else if (c == 'r')
            c = '\r';
        else if (c == 'b')
            c = '\b';
        else if (c == '\\')
            c = '\\';
        else if (isdigit(c)) {
            int n = c - '0';
            if (isdigit(*prestr)) {
                n = 8 * n + *prestr++ - '0';
                if (isdigit(*prestr))
                    n = 8 * n + *prestr++ - '0';
            }
            c = n;
        } /* else it's now in c */
        rlxval = c;
        return (CHAR);
    default:
        rlxval = c;
        return (CHAR);
    case '[':
        clen = 0;
        if (*prestr == '^') {
            cflag = 1;
            prestr++;
        } else
            cflag = 0;
        init_buf(&cbuf, NULL, strlen((char *)prestr) * 2 + 1);
        for (;;) {
            if ((c = *prestr++) == '\\') {
                cbuf[clen++] = '\\';
                if ((c = *prestr++) == '\0') {
                    ERROR
            "nonterminated character class %s", lastre FATAL;
                }
                cbuf[clen++] = c;
            } else if (c == ']') {
                cbuf[clen] = 0;
                rlxstr = tostring(cbuf);
                free(cbuf);
                if (cflag == 0)
                    return (CCL);
                else
                    return (NCCL);
            } else if (c == '\n') {
                ERROR "newline in character class %s...",
                    lastre FATAL;
            } else if (c == '\0') {
                ERROR "nonterminated character class %s",
                    lastre FATAL;
            } else
                cbuf[clen++] = c;
        }
        /*NOTREACHED*/
    }
    return (0);
}

static int
cgoto(fa *f, int s, int c)
{
    register int i, j, k;
    register int *p, *q;

    for (i = 0; i <= f->accept; i++)
        setvec[i] = 0;
    setcnt = 0;
    /* compute positions of gototab[s,c] into setvec */
    p = f->posns[s];
    for (i = 1; i <= *p; i++) {
        if ((k = f->re[p[i]].ltype) != FINAL) {
            if (k == CHAR && c == f->re[p[i]].lval ||
                k == DOT && c != 0 && c != HAT ||
                k == ALL && c != 0 ||
                k == CCL &&
                member(c, (uchar *)f->re[p[i]].lval) ||
                k == NCCL &&
                !member(c, (uchar *)f->re[p[i]].lval) &&
                c != 0 && c != HAT) {
                q = f->re[p[i]].lfollow;
                for (j = 1; j <= *q; j++) {
                    if (setvec[q[j]] == 0) {
                        setcnt++;
                        setvec[q[j]] = 1;
                    }
                }
            }
        }
    }
    /* determine if setvec is a previous state */
    tmpset[0] = setcnt;
    j = 1;
    for (i = f->accept; i >= 0; i--)
        if (setvec[i]) {
            tmpset[j++] = i;
        }
    /* tmpset == previous state? */
    for (i = 1; i <= f->curstat; i++) {
        p = f->posns[i];
        if ((k = tmpset[0]) != p[0])
            goto different;
        for (j = 1; j <= k; j++)
            if (tmpset[j] != p[j])
                goto different;
        /* setvec is state i */
        f->gototab[s][c] = i;
        return (i);
    different:;
    }

    /* add tmpset to current set of states */
    if (f->curstat >= NSTATES-1) {
        f->curstat = 2;
        f->reset = 1;
        for (i = 2; i < NSTATES; i++)
            xfree(f->posns[i]);
    } else
        ++(f->curstat);
    for (i = 0; i < NCHARS; i++)
        f->gototab[f->curstat][i] = 0;
    xfree(f->posns[f->curstat]);
    if ((p = (int *)calloc(1, (setcnt + 1) * sizeof (int))) == NULL)
        overflo("out of space in cgoto");

    f->posns[f->curstat] = p;
    f->gototab[s][c] = f->curstat;
    for (i = 0; i <= setcnt; i++)
        p[i] = tmpset[i];
    if (setvec[f->accept])
        f->out[f->curstat] = 1;
    else
        f->out[f->curstat] = 0;
    return (f->curstat);
}

static void
freefa(fa *f)
{

    register int i;

    if (f == NULL)
        return;
    for (i = 0; i <= f->curstat; i++)
        xfree(f->posns[i]);
    for (i = 0; i <= f->accept; i++)
        xfree(f->re[i].lfollow);
    xfree(f->restr);
    xfree(f);
}