/*
    regex - Regular expression pattern matching  and replacement
    By: Ozan S. Yigit (oz)
        Dept. of Computer Science
        York University
    These routines are the PUBLIC DOMAIN equivalents of regex
    routines as found in 4.nBSD UN*X, with minor extensions.
    These routines are derived from various implementations found
    in software tools books, and Conroy's grep. They are NOT derived
    from licensed/restricted software.
    For more interesting/academic/complicated implementations,
    see Henry Spencer's regexp routines, or GNU Emacs pattern
    matching module.
    Modification history:
    $Log: regex.c,v $
    Revision 1.4  1991/10/17  03:56:42  oz
    miscellaneous changes, small cleanups etc.
    Revision 1.3  1989/04/01  14:18:09  oz
    Change all references to a dfa: this is actually an nfa.
    Revision 1.2  88/08/28  15:36:04  oz
    Use a complement bitmap to represent NCL.
    This removes the need to have seperate
    code in the pmatch case block - it is
    just CCL code now.
    Use the actual CCL code in the CLO
    section of ematch. No need for a recursive
    pmatch call.
    Use a bitmap table to set char bits in an
    8-bit chunk.
    Interfaces:
        re_comp:        compile a regular expression into a NFA.
            char *re_comp(s)
            char *s;
        re_exec:        execute the NFA to match a pattern.
            int re_exec(s)
            char *s;
    Regular Expressions:
        [1] char    matches itself, unless it is a special
            character (metachar): . \ [ ] * + ^ $
        [2] . matches any character.
        [3] \ matches the character following it.
            It is used as an escape character for all
            other meta-characters, and itself. When used
            in a set ([4]), it is treated as an ordinary
            character.
        [4] [set]   matches one of the characters in the set.
            If the first character in the set is "^",
            it matches a character NOT in the set, i.e.
            complements the set. A shorthand S-E is
            used to specify a set of characters S upto
            E, inclusive. The special characters "]" and
            "-" have no special meaning if they appear
            as the first chars in the set.
            examples:        match:
            [a-z]    any lowercase alpha
            [^]-]    any char except ] and -
            [^A-Z]   any char except uppercase alpha
            [a-zA-Z] any alpha
        [5]  *  any regular expression form [1] to [4], followed by
            closure char (*) matches zero or more matches of
            that form.
        [6]  +  same as [5], except it matches one or more.
        [10] a composite regular expression xy where x and y
            are in the form [1] to [10] matches the longest
            match of x followed by a match for y.
        [11] ^    a regular expression starting with a ^ character
            $    and/or ending with a $ character, restricts the
            pattern matching to the beginning of the line,
            or the end of line. [anchors] Elsewhere in the
            pattern, ^ and $ are treated as ordinary characters.
    Acknowledgements:
    HCR's Hugh Redelmeier has been most helpful in various
    stages of development. He convinced me to include BOW
    and EOW constructs, originally invented by Rob Pike at
    the University of Toronto.
    References:
        Software tools            Kernighan & Plauger
        Software tools in Pascal        Kernighan & Plauger
        Grep [rsx-11 C dist]            David Conroy
        ed - text editor        Un*x Programmer's Manual
        Advanced editing on Un*x    B. W. Kernighan
        RegExp routines            Henry Spencer
    Notes:
    This implementation uses a bit-set representation for character
    classes for speed and compactness. Each character is represented
    by one bit in a 128-bit block. Thus, CCL always takes a
    constant 16 bytes in the internal nfa, and re_exec does a single
    bit comparison to locate the character in the set.
    Examples:
    pattern:    foo*.*
    compile:    CHR f CHR o CLO CHR o END CLO ANY END END
    matches:    fo foo fooo foobar fobar foxx ...
    pattern:    fo[ob]a[rz]
    compile:    CHR f CHR o CCL bitset CHR a CCL bitset END
    matches:    fobar fooar fobaz fooaz
    pattern:    foo\\+
    compile:    CHR f CHR o CHR o CHR \ CLO CHR \ END END
    matches:    foo\ foo\\ foo\\\  ...
    pattern:    \(foo\)[1-3]\1    (same as foo[1-3]foo)
    compile:    BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
    matches:    foo1foo foo2foo foo3foo
    pattern:    \(fo.*\)-\1
    compile:    BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
    matches:    foo-foo fo-fo fob-fob foobar-foobar ...
*/
#include <config.h>
#include <stdio.h> /* printf() */
#include "dwarf.h"
#include "libdwarf.h"
#include "dd_regex.h"
#include "dd_safe_strcpy.h"
#include "dd_checkutil.h"
#include "dd_glflags.h"
/*  This version corrects two bugs (see 'code by davea'
    below).
    Compared to the original source:
    Regular expression grouping with ()
    is ignored and word checking is ignored.
    Except when using ^ or $ in the regex
    we find any matching substring.
    David Anderson.  2 September 2021.
*/
#ifndef DW_DLV_OK
/*  Makes testing easier, these
    must match libdwarf.h definitions */
#define DW_DLV_NO_ENTRY -1
#define DW_DLV_OK        0
#define DW_DLV_ERROR     1
#endif /* DW_DLV_OK */
#define inascii(x)    (0177&(x))
#define MAXNFA  2048
#define OKP     1
#define NOP     0
#define CHR     1
#define ANY     2
#define CCL     3 /* character class [ */
#define BOL     4 /* beginning of line, ^ */
#define EOL     5 /* end of line, 5 */
#define REF     10
#define CLO     11
#define END     0
#define MAXPREDEF 11
/*
    The following defines are not meant to be changeable.
    They are for readability only.
*/
#define MAXCHR    128
#define CHRBIT    8
#define BITBLK    MAXCHR/CHRBIT
#define BLKIND    0170
#define BITIND    07
#define ASCIIB    0177
#ifdef NO_UCHAR
typedef char CHAR;
#else
typedef unsigned char CHAR;
#endif
static CHAR nfa[MAXNFA];     /* automaton..       */
static int  sta = NOP;       /* status of lastpat */
static CHAR bittab[BITBLK];  /* bit table for CCL */
/* pre-set bits...   */
static CHAR bitarr[] = {1,2,4,8,16,32,64,128};
#ifdef DEBUG
static void nfadump(CHAR *);
static void symbolic(char *);
#endif
static void
chset(CHAR c)
{
    bittab[(CHAR) ((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
}
#define badpat    (nfa[0] = END)
#define store(x) do {                                    \
    if ( mp > endpoint){                                 \
        badpat;                                          \
        printf("ERROR: Pattern too large to store "      \
            "in regex\n");                               \
        glflags.gf_count_major_errors++;                 \
        return DW_DLV_ERROR;                             \
    }                                                    \
    *mp++ = (x);                                         \
    }  while(0)
static void
resetbittab(void)
{
    int j = 0;
    for (j = 0; j < BITBLK; ++j) {
        bittab[j] = 0;
    }
    for (j = 0; j < MAXNFA; ++j) {
        nfa[j] = 0;
    }
    sta = NOP;
}
#if 0
/* Some may not be alone,
. \ [ ] * + ^ $
but some can be.
*/
static int
dangermetachar(CHAR c)
{
    switch(c) {
    case '?':
    case '\\':
    case '[':
    case '+':
    case '^':
    case '$': return 1;
    default:
        return 0;
    }
}
#endif
int
dd_re_comp(const char *pat)
{
    const char *p  = 0;           /* pattern pointer   */
    CHAR *mp = nfa;
    CHAR *lp = 0;          /* saved pointer..   */
    CHAR *sp = nfa;      /* another one..     */
    CHAR *endpoint = nfa+MAXNFA - 2;
    int n    = 0;
    CHAR mask = 0;        /* xor mask -CCL/NCL */
    int c1   = 0;
    int c2   = 0;
    resetbittab();
    if (!pat || !*pat) {
        badpat;
        printf("ERROR: Empty or NULL not a valid "
            "regular expression\n");
        glflags.gf_count_major_errors++;
        return DW_DLV_NO_ENTRY;
    }
    for (p = pat; *p; p++) {
        int a =  (unsigned char)*p;
        int b =  inascii(*p);
        if (b != a) {
            badpat;
            printf("ERROR: Only the ASCII subset of "
                " characters are supported in dwarfdump "
                "regular expressions\n");
            glflags.gf_count_major_errors++;
            return DW_DLV_NO_ENTRY;
        }
    }
    for (p = pat; *p; p++) {
        lp = mp;
        switch(*p) {
        case '.':               /* match any char..  */
            store(ANY);
            break;
        case '^':               /* match beginning.. */
            if (p == pat)
                store(BOL);
            else {
                store(CHR);
                store(*p);
            }
            break;
        case '$':               /* match endofline.. */
            if (!*(p+1)) {
                store(EOL);
            } else {
                store(CHR);
                store(*p);
            }
            break;
        case '[':               /* match char class..*/
            store(CCL);
            if (*++p == '^') {
                mask = 0377;
                p++;
            } else {
                mask = 0;
            }
            if (*p == '-')  {       /* real dash */
                chset(*p++);
            }
            if (*p == ']') {       /* real brac */
                chset(*p++);
            }
            while (*p && *p != ']') {
                if (*p == '-' && *(p+1) && *(p+1) != ']') {
                    p++;
                    c1 = *(p-2) + 1;
                    c2 = *p++;
                    while (c1 <= c2)
                        chset((CHAR)c1++);
                }
#ifdef EXTEND
                else if (*p == '\\' && *(p+1)) {
                    p++;
                    chset(*p++);
                }
#endif /* EXTEND */
                else {
                    chset(*p++);
                }
            }
            if (!*p) {
                badpat;
                printf("ERROR: Regular expression %s missing ]\n",
                    pat) ;
                glflags.gf_count_major_errors++;
                return DW_DLV_ERROR;
            }
            /* Storing the bitmask into nfa  */
            for (n = 0; n < BITBLK; bittab[n++] =
                (char) 0) {
                store(mask ^ bittab[n]);
            }
            break;
        case '*':               /* match 0 or more.. */
        case '+':               /* match 1 or more.. */
            if (p == pat) {
                badpat;
                printf("ERROR: Regular expression %s has empty * +  "
                    "Closure\n",pat);
                glflags.gf_count_major_errors++;
                return DW_DLV_ERROR;
            }
            lp = sp;        /* previous opcode */
            if (*lp == CLO)  {      /* equivalence..   */
                break;
            }
            switch(*lp) {
            case BOL:
            case REF:
                badpat;
                printf("ERROR Regular expression %s has illegal "
                    "* + closure\n",pat);
                glflags.gf_count_major_errors++;
                return DW_DLV_ERROR;
            default:
                break;
            }
            if (*p == '+') {
                for (sp = mp; lp < sp; lp++) {
                    store(*lp);
                }
            }
            store(END);
            store(END);
            sp = mp;
            while (--mp > lp) {
                *mp = mp[-1];
            }
            store(CLO);
            mp = sp;
            break;
        case '\\':              /* tags, backrefs .. */
            ++p;
            if (!*p) {
                badpat;
                printf("ERROR Regular expression backslash"
                    " missing its operand. Erroneous regex\n");
                glflags.gf_count_major_errors++;
                return DW_DLV_ERROR;
            }
            store(CHR);
            store(*p);
            break;
        default :               /* an ordinary char  */
            store(CHR);
            store(*p);
            break;
        }
        sp = lp;
    }
    store(END);
    sta = OKP;
#ifdef DEBUG
    symbolic("Final nfa");
#endif /* DEBUG */
    return DW_DLV_OK;
}
static char *bol;
static int dd_pmatch(const char *, CHAR *,char **str_out,
    int level);
/*
   re_exec:
    execute nfa to find a match.
    special cases: (nfa[0])
        BOL Match only once, starting from the
            beginning.
        CHR First locate the character without
            calling pmatch, and if found, call
            pmatch for the remaining string.
        END re_comp failed, poor luser did not
            check for it. Fail fast.
    If a match is found, bopat[0] and eopat[0] are set
    to the beginning and the end of the matched fragment,
    respectively.
    return DW_DLV_OK, DW_DLV_NO_ENTRY or DW_DLV_ERROR
*/
int
dd_re_exec(char *lp)
{
    CHAR c   = 0;
    char *ep = 0;
    CHAR *ap = nfa;
    int res  = 0;
    int level = 0;
    bol = lp;
    switch(*ap) {
    case BOL:            /* anchored: match from BOL only */
        res = dd_pmatch(lp,ap,&ep,level);
        if (res != DW_DLV_OK) {
            return res;
        }
        break;
    case CHR:            /* ordinary char: locate it fast */
        c = *(ap+1);
        while (*lp && *lp != c) {
            lp++;
        }
        if (!*lp) {      /* if EOS, fail, else fall thru. */
            return DW_DLV_NO_ENTRY;
        }
        goto regmatch; /* GO TO avoids a fall-through
            warning from gcc */
    default:    {        /* regular matching all the way. */
        regmatch:
        do {
            res = dd_pmatch(lp,ap,&ep,level);
            if (res == DW_DLV_ERROR) {
                return res;
            }
            if (res == DW_DLV_OK) {
                break;
            }
            lp++;
        } while (*lp);
        break;
    }
    case END:            /* munged automaton. fail always */
        badpat;
        printf("ERROR in in regex automaton. "
            "END out of place\n");
        glflags.gf_count_major_errors++;
        return DW_DLV_ERROR;
    }
    if (res != DW_DLV_OK) {
        return res;
    }
    return DW_DLV_OK;
}
/*
    dd_pmatch: internal routine for the hard part
    This code is partly snarfed from an early grep written by
    David Conroy. The backref and tag stuff, and various other
    innovations are by oz.
    special case optimizations: (nfa[n], nfa[n+1])
        CLO ANY
            We KNOW .* will match everything upto the
            end of line. Thus, directly go to the end of
            line, without recursive pmatch calls. As in
            the other closure cases, the remaining pattern
            must be matched by moving backwards on the
            string recursively, to find a match for xy
            (x is ".*" and y is the remaining pattern)
            where the match satisfies the LONGEST match for
            x followed by a match for y.
        CLO CHR
            We can again scan the string forward for the
            single char and at the point of failure, we
            execute the remaining nfa recursively, same as
            above.
    At the end of a successful match, bopat[n] and eopat[n]
    are set to the beginning and end of subpatterns matched
    by tagged expressions (n = 1 to 9).
        returns DW_DLV_OK for a match, and sets the ep pointer
            to point into the input at the next char to check
        DW_DLV_NO_ENTRY for a non-match
        DW_DLV_NO_ERROR for an internal error
*/
/*
    character classification table for word boundary operators BOW
    and EOW. the reason for not using ctype macros is that we can
    let the user add into our own table. see re_modw. This table
    is not in the bitset form, since we may wish to extend it in the
    future for other character classifications.
    TRUE for 0-9 A-Z a-z _
*/
#if 0 /* For debugging only */
static char *
naming(CHAR c)
{
#define CHR     1
#define ANY     2
#define CCL     3 /* character class [ */
#define BOL     4 /* beginning of line, ^ */
#define EOL     5 /* end of line, 5 */
#define BOT     6 /* beginning of tag, ( */
#define EOT     7 /* end of tag, ) */
#define BOW     8 /* nonstandard beginning of ? < */
#define EOW     9 /* nonstandard end  of ? > */
    static int use1;
    /*  Two result arrays so we can allow naming called twice
        in one printf. Turns any UCHAR into a useful string.
        Array index must match the #define value for each name.*/
    static char nam1[10];
    static char nam2[10];
    static char * n[] = {
    "END(0)",
    "CHR",
    "ANY",
    "CCL",
    "BOL",
    "EOL",
    "BOT",
    "EOT",
    "BOW",
    "EOW",
    "REF",
    "CLO",
    "bogus",
    };
    char *outtab= 0;
    if (use1) {
        outtab = nam1;
    } else {
        outtab = nam2;
    }
    outtab[0] = 0;
    if (c && c <= MAXPREDEF) {
        dd_safe_strcpy(outtab,sizeof(nam1),n[c],strlen(n[c]));
    } else {
        sprintf(outtab,"0x%x",c); /* debugging only */
    }
    use1 = !use1;
    return outtab;
}
#define iswordc(x)   chrtyp[inascii(x)]
#endif /* 0 */
#define isinset(x,y) ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
/* skip values for CLO XXX to skip past the closure */
#define ANYSKIP    2    /* [CLO] ANY END ...         */
#define CHRSKIP    3    /* [CLO] CHR chr END ...     */
#define CCLSKIP   18    /* [CLO] CCL 16bytes END ... */
static int
dd_pmatch(const char *lp, CHAR *ap,char **end_ptr,
    int level)
{
    int op    = 0;
    int c    = 0;
    int n    = 0;
    char *e  = 0;    /* extra pointer for CLO */
    int res  = 0;
    while ((op = *ap) != END) {
        ap++;
        switch(op) {
        case CHR:
            if (*lp++ != *ap++) {
                return DW_DLV_NO_ENTRY;
            }
            break;
        case ANY:
            if (!*lp++) {
                return DW_DLV_NO_ENTRY;
            }
            break;
        case CCL:
            c = *lp++;
            if (!isinset(ap,c)) {
                return DW_DLV_NO_ENTRY;
            }
            ap += BITBLK;
            break;
        case BOL:
            if (lp != bol) {
                return DW_DLV_NO_ENTRY;
            }
            break;
        case EOL:
            if (*lp) {
                return DW_DLV_NO_ENTRY;
            }
            break;
        case CLO: {
            const char *are = lp;
            switch(*ap) {
            case ANY:
                while (*lp) {
                    lp++;
                }
                n = ANYSKIP;
                break;
            case CHR:
                c = *(ap+1);
                while (*lp && c == *lp) {
                    lp++;
                }
                n = CHRSKIP;
                break;
            case CCL:
                for (c = *lp ; c && isinset(ap+1,c); c = *lp) {
                    lp++;
                }
                n = CCLSKIP;
                break;
            default:
                badpat;
                printf("ERROR Regular expression has illegal "
                    "closure: bad nfa\n");
                glflags.gf_count_major_errors++;
                return DW_DLV_ERROR;
            }
            ap += n;
            if (lp == are) {
                /*  [code by davea]
                    Empty closure is fine for early accept iff
                    it is the end of the regex too. Else
                    this is a NO_ENTRY */
                if (!*lp && !*ap) {
                    /* early accept. Nothing left to check. */
                    return DW_DLV_OK;
                }
                return DW_DLV_NO_ENTRY;
            }
            while (lp >= are) {
                res = dd_pmatch(lp, ap,&e,level+1);
                if (res == DW_DLV_ERROR) {
                    return res;
                }
                if (res == DW_DLV_OK) {
                    *end_ptr = e;
                    return res;
                }
                /* NO_ENTRY so far */
                --lp;
            }
            }
            return DW_DLV_NO_ENTRY;
        default:
            badpat;
            printf("ERROR Regular expression has illegal "
                "dd_re_exec: bad nfa.\n");
            glflags.gf_count_major_errors++;
            return DW_DLV_ERROR;
        }
    }
    *end_ptr = (char *)lp;
    return DW_DLV_OK;
}
#ifdef DEBUG
/*  symbolic - produce a symbolic dump of the nfa */
static void
symbolic(char *s)
{
    printf("pattern: %s\n", s);
    printf("nfacode:\n");
    nfadump(nfa);
}
static void
nfadump(CHAR *ap)
{
    register int n = 0;
    while (*ap != END)
        switch(*ap++) {
        case CLO:
            printf("CLOSURE");
            nfadump(ap);
            switch(*ap) {
            case CHR:
                n = CHRSKIP;
                break;
            case ANY:
                n = ANYSKIP;
                break;
            case CCL:
                n = CCLSKIP;
                break;
            default: break;
            }
            ap += n;
            break;
        case CHR:
            printf("\tCHR %c\n",*ap++);
            break;
        case ANY:
            printf("\tANY .\n");
            break;
        case BOL:
            printf("\tBOL -\n");
            break;
        case EOL:
            printf("\tEOL -\n");
            break;
        case CCL:
            printf("\tCCL [");
            for (n = 0; n < MAXCHR; n++)
                if (isinset(ap,(CHAR)n)) {
                    if (n < ' ')
                        printf("^%c", n ^ 0x040);
                    else
                        printf("%c", n);
                }
            printf("]\n");
            ap += BITBLK;
            break;
        default:
            printf("bad nfa. opcode %o\n", ap[-1]);
            exit(EXIT_FAILURE);
            break;
        }
}
#endif /* DEBUG */