/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


/*
 * RegComp and RegExec
 *
 *      Copyright (c) 1986 by University of Toronto.
 *      Written by Henry Spencer.  Not derived from licensed software.
 *
 *      Modified By Craig Eisler
 *              - editor specific code/errors
 *              - case insensitive search
 *              - CurrentRegComp
 *              - nomagic
 *              - MakeExpressionNonRegular
 *              - case sensitivity atoms (~ and @)
 *              - SetMajickString
 *              - bug fixes, fun fun fun
 *
 *      Permission is granted to anyone to use this software for any
 *      purpose on any computer system, and to redistribute it freely,
 *      subject to the following restrictions:
 *
 *      1. The author is not responsible for the consequences of use of
 *              this software, no matter how awful, even if they arise
 *              from defects in it.
 *
 *      2. The origin of this software must not be misrepresented, either
 *              by explicit claim or by omission.
 *
 *      3. Altered versions must be plainly marked as such, and must not
 *              be misrepresented as being the original software.
 *
 * Beware that some of this code is subtly aware of the way operator
 * precedence is structured in regular expressions.  Serious changes in
 * regular-expression syntax might require a total rethink.
 */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#ifdef UNIX
    #include "clibext.h"
    #include "wndregx.h"
#endif
#include "../h/regexp.h"


/* IMPORTANT: must have ^$\\ FIRST */

char
#ifdef __WATCOMC__
near
#endif
META[]="^$\\.[()|?+*~@";

#if !defined(REALTABS)
#define REALTABS        RealTabs
char    RealTabs=TRUE;
#endif
#if !defined(CASEIGNORE)
#define CASEIGNORE      CaseIgnore
char    CaseIgnore=TRUE;
#endif
#if !defined(MAGICFLAG)
#define MAGICFLAG       MagicFlag
char    MagicFlag=TRUE;
#endif
#if !defined(MAGICSTR)
#define MAGICSTR        MagicString
char    *MagicString="()";
#endif
#if !defined(ALLOC)
#define ALLOC           malloc
#include <malloc.h>
#endif
#ifdef STANDALONE_RX
int     RegExpError;
#endif

/*
 * regError - set regular expression error
 */
static void regError( int rc )
{
    RegExpError = rc;

} /* regError */

/*
 * StrChr - case sensitive/insensitive version of strchr
 */
static char *StrChr( char *s, int c )
{
    char        ch;

    ch = c;
    if( CASEIGNORE ) {
        while( (tolower(*s) != tolower(ch)) && *s != 0 ) {
            s++;
        }
    } else {
        while( *s != ch && *s != 0 ) {
            s++;
        }
    }
    if( !(*s) ) {
        return( NULL );
    }
    return( s );

}  /* StrChr */

/*
 * The "internal use only" fields in regexp.h are present to pass info from
 * compile to execute that permits the execute phase to run lots faster on
 * simple cases.  They are:
 *
 * regstart     char that must begin a match; '\0' if none obvious
 * reganch      is the match anchored (at beginning-of-line only)?
 * regmust      string (pointer into program) that match must include, or NULL
 * regmlen      length of regmust string
 *
 * Regstart and reganch permit very fast decisions on suitable starting points
 * for a match, cutting down the work a lot.  Regmust permits fast rejection
 * of lines that cannot possibly match.  The regmust tests are costly enough
 * that RegComp() supplies a regmust only if the r.e. contains something
 * potentially expensive (at present, the only such thing detected is * or +
 * at the start of the r.e., which can involve a lot of backup).  Regmlen is
 * supplied because the test in RegExec() needs it and RegComp() is computing
 * it anyway.
 */

/*
 * Structure for regexp "program".  This is essentially a linear encoding
 * of a nondeterministic finite-state machine (aka syntax charts or
 * "railroad normal form" in parsing technology).  Each node is an opcode
 * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
 * all nodes except BRANCH implement concatenation; a "next" pointer with
 * a BRANCH on both ends of it is connecting two alternatives.  (Here we
 * have one of the subtle syntax dependencies:  an individual BRANCH (as
 * opposed to a collection of them) is never concatenated with anything
 * because of operator precedence.)  The operand of some types of node is
 * a literal string; for others, it is a node leading into a sub-FSM.  In
 * particular, the operand of a BRANCH node is the first node of the branch.
 * (NB this is *not* a tree structure:  the tail of the branch connects
 * to the thing following the set of BRANCHes.)  The opcodes are:
 */

/* definition   number  opnd?   meaning */
#define END     0       /* no   End of program. */
#define BOL     1       /* no   Match "" at beginning of line. */
#define EOL     2       /* no   Match "" at end of line. */
#define ANY     3       /* no   Match any one character. */
#define ANYOF   4       /* str  Match any character in this string. */
#define ANYBUT  5       /* str  Match any character not in this string. */
#define BRANCH  6       /* node Match this alternative, or the next... */
#define BACK    7       /* no   Match "", "next" ptr points backward. */
#define EXACTLY 8       /* str  Match this string. */
#define NOTHING 9       /* no   Match empty string. */
#define STAR    10      /* node Match this (simple) thing 0 or more times. */
#define PLUS    11      /* node Match this (simple) thing 1 or more times. */
#define CASEI   12      /* no   Set CASEIGNORE to TRUE */
#define NOCASEI 13      /* no   Set CASEIGNORE to FALSE */
#define OPEN    20      /* no   Mark this point in input as start of #n. */
                        /*      OPEN+1 is number 1, etc. */
#define CLOSE   40      /* no   Analogous to OPEN. */

/*
 * Opcode notes:
 *
 * BRANCH       The set of branches constituting a single choice are hooked
 *              together with their "next" pointers, since precedence prevents
 *              anything being concatenated to any individual branch.  The
 *              "next" pointer of the last BRANCH in a choice points to the
 *              thing following the whole choice.  This is also where the
 *              final "next" pointer of each individual branch points; each
 *              branch starts with the operand node of a BRANCH node.
 *
 * BACK         Normal "next" pointers all implicitly point forward; BACK
 *              exists to make loop structures possible.
 *
 * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
 *              BRANCH structures using BACK.  Simple cases (one character
 *              per match) are implemented with STAR and PLUS for speed
 *              and to minimize recursive plunges.
 *
 * OPEN,CLOSE   ...are numbered at compile time.
 */

/*
 * A node is one char of opcode followed by two chars of "next" pointer.
 * "Next" pointers are stored as two 8-bit pieces, high order first.  The
 * value is a positive offset from the opcode of the node containing it.
 * An operand, if any, simply follows the node.  (Note that much of the
 * code generation knows about this implicit relationship.)
 *
 * Using two bytes for the "next" pointer is vast overkill for most things,
 * but allows patterns to get big without disasters.
 */
#define OP(p)   (*(p))
#define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
#define OPERAND(p)      ((p) + 3)

/*
 * See regmagic.h for one further detail of program structure.
 */


/*
 * Utility definitions.
 */
#ifndef CHARBITS
#define UCHARAT(p)      ((int)*(unsigned char *)(p))
#else
#define UCHARAT(p)      ((int)*(p)&CHARBITS)
#endif

#define FAIL(m) { regError(m); return(NULL); }
#define ISMULT(c)       ((c) == '*' || (c) == '+' || (c) == '?')

/*
 * Flags to be passed up and down.
 */
#define HASWIDTH        01      /* Known never to match null string. */
#define SIMPLE          02      /* Simple enough to be STAR/PLUS operand. */
#define SPSTART         04      /* Starts with * or +. */
#define WORST           0       /* Worst case. */

/*
 * Global work variables for RegComp().
 */
static char *regparse;          /* Input-scan pointer. */
static int regnpar;             /* () count. */
static char regdummy;
static char *regcode;           /* Code-emit pointer; &regdummy = don't. */
static long regsize;            /* Code size. */

/*
 * Forward declarations for RegComp()'s friends.
 */
static char *reg();
static char *regbranch();
static char *regpiece();
static char *regatom();
static char *regnode( char op );
static char *regnext();
static void regc( char b );
static void reginsert( char op, char * opnd);
static void regtail();
static void regoptail();

/*
 - RegComp - compile a regular expression into internal code
 *
 * We can't allocate space until we know how big the compiled form will be,
 * but we can't compile it (and thus know how big it is) until we've got a
 * place to put the code.  So we cheat:  we compile it twice, once with code
 * generation turned off and size counting turned on, and once "for real".
 * This also means that we don't allocate space until we are sure that the
 * thing really will compile successfully, and we never have to move the
 * code and thus invalidate pointers into it.  (Note that it has to be in
 * one piece because free() must be able to free it all.)
 *
 * Beware that the optimization-preparation code in here knows about some
 * of the structure of the compiled regexp.
 */
regexp *RegComp( char *instr )
{
    regexp      *r;
    char        *scan,*longest,*exp;
    char        buff[MAX_STR*2];
    int         len,flags,i,j,ignmag=FALSE,k;

#ifdef WANT_EXCLAMATION
    if( instr[0] == '!' ) {
        instr++;
        ignmag = TRUE;
    }
#endif

    /*
     * flip roles of magic chars
     */
    if( !ignmag && (!MAGICFLAG && MAGICSTR != NULL) ) {
        j = 0;
        k = strlen( instr );
        for( i=0;i<k;i++ ) {

            if( instr[i] == '\\' ) {
                if( strchr( MAGICSTR, instr[i+1] ) == NULL ) {
                    buff[j++] = '\\';
                }
                i++;
            } else {
                if( strchr( MAGICSTR, instr[i] ) != NULL ) {
                    buff[j++] = '\\';
                }
            }
            buff[j++] = instr[i];

        }
        buff[j] = 0;
        exp = buff;
    } else {
        exp = instr;
    }

    regError( ERR_NO_ERR );
    if( exp == NULL ) {
        FAIL( ERR_RE_NULL_ARGUMENT );
    }

    /* First pass: determine size, legality. */
    regparse = exp;
    regnpar = 1;
    regsize = 0L;
    regcode = &regdummy;
    regc( MAGIC );
    if( reg( 0, &flags ) == NULL ) {
        return( NULL );
    }

    /* Allocate space. */
    r = ALLOC( sizeof(regexp) + (unsigned) regsize );

    /* Second pass: emit code. */
    regparse = exp;
    regnpar = 1;
    regcode = r->program;
    regc( MAGIC );
    if( reg( 0, &flags ) == NULL ) {
        return( NULL );
    }

    /* Dig out information for optimizations. */
    r->regstart = '\0';     /* Worst-case defaults. */
    r->reganch = 0;
    r->regmust = NULL;
    r->regmlen = 0;
    scan = r->program+1;                    /* First BRANCH. */
    if( OP(regnext(scan)) == END ) {         /* Only one top-level choice. */
        scan = OPERAND(scan);

        /* Starting-point info. */
        if( OP(scan) == EXACTLY ) {
            r->regstart = *OPERAND(scan);
        } else if( OP(scan) == BOL ) {
            r->reganch++;
        }

        /*
         * If there's something expensive in the r.e., find the
         * longest literal string that must appear and make it the
         * regmust.  Resolve ties in favor of later strings, since
         * the regstart check works with the beginning of the r.e.
         * and avoiding duplication strengthens checking.  Not a
         * strong reason, but sufficient in the absence of others.
         */
        if( flags & SPSTART ) {
            longest = NULL;
            len = 0;
            for(; scan != NULL; scan = regnext(scan)) {
                if( OP(scan) == EXACTLY &&
                                        (int)strlen(OPERAND(scan)) >= len ) {
                    longest = OPERAND(scan);
                    len = strlen(OPERAND(scan));
                }
            }
            r->regmust = longest;
            r->regmlen = len;
        }
    }

    return(r);
}

/*
 * reg - regular expression, i.e. main body or parenthesized thing
 *
 * Caller must absorb opening parenthesis.
 *
 * Combining parenthesis handling with the base level of regular expression
 * is a trifle forced, but the need to tie the tails of the branches to what
 * follows makes it hard to avoid.
 */
static char *reg(int paren, int *flagp)
{
    char        *ret,*br,*ender;
    int         parno,flags;

    *flagp = HASWIDTH;      /* Tentatively. */

    /* Make an OPEN node, if parenthesized. */
    if( paren ) {
        if( regnpar >= NSUBEXP ) {
            FAIL(ERR_RE_TOO_MANY_ROUND_BRACKETS);
        }
        parno = regnpar;
        regnpar++;
        ret = regnode(OPEN+parno);
    } else {
        ret = NULL;
    }

    /* Pick up the branches, linking them together. */
    br = regbranch(&flags);
    if( br == NULL ) {
        return(NULL);
    }
    if( ret != NULL ) {
        regtail(ret, br);       /* OPEN -> first. */
    } else {
        ret = br;
    }
    if( !(flags & HASWIDTH) ) {
        *flagp &= ~HASWIDTH;
    }
    *flagp |= flags&SPSTART;
    while (*regparse == '|') {
        regparse++;
        br = regbranch(&flags);
        if( br == NULL ) {
            return(NULL);
        }
        regtail(ret, br);       /* BRANCH -> BRANCH. */
        if( !(flags & HASWIDTH) ) {
            *flagp &= ~HASWIDTH;
        }
        *flagp |= flags & SPSTART;
    }

    /* Make a closing node, and hook it on the end. */
    ender = regnode((paren) ? CLOSE+parno : END);
    regtail( ret, ender );

    /* Hook the tails of the branches to the closing node. */
    for( br = ret; br != NULL; br = regnext( br ) ) {
        regoptail( br, ender );
    }

    /* Check for proper termination. */
    if( paren && *regparse++ != ')' ) {
        FAIL(ERR_RE_UNMATCHED_ROUND_BRACKETS);
    } else if( !paren && *regparse != '\0' ) {
        if( *regparse == ')' ) {
            FAIL(ERR_RE_UNMATCHED_ROUND_BRACKETS);
        } else {
            FAIL(ERR_RE_INTERNAL_FOULUP);    /* "Can't happen". */
        }
    }

    return(ret);
}

/*
 - regbranch - one alternative of an | operator
 *
 * Implements the concatenation operator.
 */
static char *regbranch( int *flagp )
{
    char        *ret,*chain,*latest;
    int         flags;

    *flagp = WORST;         /* Tentatively. */

    ret = regnode( BRANCH );
    chain = NULL;
    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 char *regpiece( int *flagp)
{
    char        *ret,op,*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(ERR_RE_EMPTY_OPERAND );
    }
    *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(ERR_RE_NESTED_OPERAND );
    }

    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 char *regatom( int *flagp )
{
    char *ret;
    int flags;

    *flagp = WORST;         /* Tentatively. */

    switch( *regparse++ ) {
    case '~':
        if( *regparse == 0 ) {
            FAIL( ERR_RE_INVALID_CASETOGGLE );
        }
        ret = regnode( CASEI );
        break;
    case '@':
        if( *regparse == 0 ) {
            FAIL( ERR_RE_INVALID_CASETOGGLE );
        }
        ret = regnode( NOCASEI );
        break;
    case '^':
        ret = regnode( BOL );
        break;
    case '$':
        ret = regnode( EOL );
        break;
    case '.':
        ret = regnode( ANY );
        *flagp |= HASWIDTH|SIMPLE;
        break;
    case '[':
        {
            int class;
            int classend;

            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( '-' );
                    } else {
                        class = UCHARAT( regparse-2 )+1;
                        classend = UCHARAT( regparse );
                        if( class > classend+1 ) {
                            FAIL(ERR_RE_INVALID_SB_RANGE);
                        }
                        for( ; class <= classend; class++ ) {
                            regc( class );
                        }
                        regparse++;
                    }
                } else {
                    if( *regparse == '\\' && *(regparse+1)=='t' && REALTABS ) {
                        regparse += 2;
                        regc( '\t' );
                    } else {
                        regc( *regparse++ );
                    }
                }
            }
            regc( '\0' );
            if( *regparse != ']' ) {
                FAIL(ERR_RE_UNMATCHED_SQUARE_BRACKET);
            }
            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(ERR_RE_INTERNAL_FOULUP);   /* Supposed to be caught earlier. */
        break;
    case '?':
    case '+':
    case '*':
        FAIL(ERR_RE_OPERAND_FOLLOWS_NOTHING);
        break;
    case '\\':
        if(*regparse == '\0') {
            FAIL(ERR_RE_TRAILING_SLASH);
        }
        ret = regnode(EXACTLY);
        if( *regparse == 't' && REALTABS ) {
            regc( '\t' );
            regparse++;
        } else {
            regc(*regparse++);
        }
        regc('\0');
        *flagp |= HASWIDTH|SIMPLE;
        break;
    default:
        {
            int len;
            char ender;

            regparse--;
            len = strcspn( regparse, META );
            if( len <= 0 ) {
                FAIL(ERR_RE_INTERNAL_FOULUP);
            }
            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('\0');
        }
        break;
    }

    return(ret);
}

/*
 * regnode - emit a node
 */
static char *regnode( char op )
{
    char        *ret,*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( char 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( char op, char *opnd)
{
    char        *src,*dst,*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( char *p,  char *val )
{
    char        *scan,*temp;
    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( char *p,  char *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 char *reginput;          /* String-input pointer. */
static char *regbol;            /* Beginning of input, for ^ check. */
static char **regstartp;        /* Pointer to startp array. */
static char **regendp;          /* Ditto for endp. */

/*
 * Forwards.
 */
static int regtry();
static int regmatch();
static int regrepeat();

/*
 - RegExec2 - match a regexp against a string
 */
static int RegExec2( regexp *prog, char *string, bool anchflag)
{
    char *s;

    regError( ERR_NO_ERR );

    /* 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( CASEIGNORE ) {
                if( strnicmp( s, prog->regmust, prog->regmlen ) == 0 ) {
                    break;
                }
            } else {
                if( strncmp( s, prog->regmust, prog->regmlen ) == 0 ) {
                    break;
                }
            }
            s++;
        }
        if( s == NULL ) return(0); /* Not present. */
    }

    /* Mark beginning of line for ^ . */
    if( anchflag) {
        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);

} /* RegExec2 */

int RegExec( regexp *prog, char *string, char anchflag )
{
    bool        oldign;
    int         rc;

    oldign = CASEIGNORE;
    rc = RegExec2( prog, string, anchflag );
    CASEIGNORE = oldign;
    return( rc );

} /* RegExec */

/*
 * regtry - try match at specific point
 */
static int regtry( regexp *prog, char *string)
{
    int         i;
    char        **sp,**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.                      ( 0 failure, 1 success )
 */
static int regmatch( char *prog )
{
    char        *scan;  /* Current node. */
    char        *next;  /* Next node. */

    scan = prog;
    while( scan != NULL ) {
        next = regnext( scan );

        switch( 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:
            {
                int len;
                char *opnd;

                opnd = OPERAND(scan);
                /* Inline the first character, for speed. */
                if( CASEIGNORE ) {
                    if( tolower(*opnd) != tolower(*reginput) ) {
                        return( 0 );
                    }
                } else {
                    if( *opnd != *reginput) {
                        return( 0 );
                    }
                }
                len = strlen( opnd );
                if (len > 1 ) {
                    if( CASEIGNORE ) {
                        if( strnicmp( opnd, reginput, len ) != 0) {
                            return( 0 );
                        }
                    } else {
                        if( strncmp( opnd, reginput, len ) != 0) {
                            return( 0 );
                        }
                    }
                }
                reginput += len;
            }
            break;
        case ANYOF:
            if( *reginput == '\0' || StrChr( OPERAND(scan), *reginput) == NULL ) {
                return(0);
            }
            reginput++;
            break;
        case ANYBUT:
            if( *reginput == '\0' || StrChr( OPERAND(scan), *reginput) != NULL ) {
                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: case OPEN+10:  case OPEN+11:  case OPEN+12:
        case OPEN+13:  case OPEN+14:  case OPEN+15:  case OPEN+16:
        case OPEN+17:  case OPEN+18:
        case OPEN+19:
            {
                int no;
                char *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 );
                }
                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: case CLOSE+10: case CLOSE+11: case CLOSE+12:
        case CLOSE+13: case CLOSE+14: case CLOSE+15: case CLOSE+16:
        case CLOSE+17: case CLOSE+18:
        case CLOSE+19:
            {
                int no;
                char *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);
                }
                return(0);

            }
            break;
#if 0
        case MATCHPREV+1: case MATCHPREV+2: case MATCHPREV+3:
        case MATCHPREV+4: case MATCHPREV+5: case MATCHPREV+6:
        case MATCHPREV+7: case MATCHPREV+8: case MATCHPREV+9:
        case MATCHPREV+10: case MATCHPREV+11: case MATCHPREV+12:
        case MATCHPREV+13: case MATCHPREV+14: case MATCHPREV+15:
        case MATCHPREV+16: case MATCHPREV+17: case MATCHPREV+18:
        case MATCHPREV+19:
            {
                int no;
                char *curr,*save;

                no = OP(scan) - OPEN;

                if( regstartp[no] == NULL ||
                        regendp[no] == NULL ) return( 0 );
                curr = regstartp[no];
                save = reginput;
                if(CASEIGNORE ) {
                    while( 1 ) {
                        if( tolower(*curr) == tolower(*reginput) ) {
                            if( curr == regendp[no] ) {
                                return( 1 );
                            }
                            curr++;
                            reginput++;
                        } else {
                            reginput = save;
                            return( 0 );
                        }
                    }
                } else {
                    while( 1 ) {
                        if( *curr == *reginput ) {
                            if( curr == regendp[no] ) {
                                return( 1 );
                            }
                            curr++;
                            reginput++;
                        } else {
                            reginput = save;
                            return( 0 );
                        }
                    }

                }
            }
            break;
#endif
        case BRANCH:
            {
                char *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:
            {
                char nextch;
                int no;
                char *save;
                int min;

                /*
                 * Lookahead to avoid useless match attempts
                 * when we know what character comes next.
                 */
                nextch = '\0';
                if( OP(next) == EXACTLY ) {
                    nextch = *OPERAND(next);
                }
                min = (OP(scan) == STAR) ? 0 : 1;
                save = reginput;
                no = regrepeat(OPERAND(scan));
                while( no >= min ) {
                    /* If it could work, try it. */
                    if( CASEIGNORE ) {
                        if( nextch == '\0' || tolower(*reginput) == tolower(nextch) ) {
                            if( regmatch(next) ) {
                                return(1);
                            }
                        }
                    } else {
                        if( nextch == '\0' || *reginput == nextch ) {
                            if( regmatch( next ) ) {
                                return(1);
                            }
                        }
                    }
                    /* Couldn't or didn't -- back up. */
                    no--;
                    reginput = save + no;
                }
                return(0);
            }
            break;
        case CASEI:
            CASEIGNORE = TRUE;
            break;
        case NOCASEI:
            CASEIGNORE = FALSE;
            break;
        case END:
            return(1);      /* Success! */
            break;
        default:
            regError( ERR_RE_MEMORY_CORRUPTION );
            return( 0 );
            break;
        }

        scan = next;
    }

    /*
     * We get here only if there's trouble -- normally "case END" is
     * the terminating point.
     */
    regError( ERR_RE_CORRUPTED_POINTER );
    return( 0 );
}

/*
 * regrepeat - repeatedly match something simple, report how many
 */
static int regrepeat( char *p )
{
    int         count = 0;
    char        *scan,*opnd;

    scan = reginput;
    opnd = OPERAND(p);
    switch (OP(p)) {
    case ANY:
        count = strlen(scan);
        scan += count;
        break;
    case EXACTLY:
        if( CASEIGNORE ) {
            while( tolower(*opnd) == tolower(*scan) ) {
                count++;
                scan++;
            }
        } else {
            while( *opnd == *scan ) {
                count++;
                scan++;
            }
        }
        break;
    case ANYOF:
        while( *scan != '\0' && StrChr(opnd, *scan) != NULL ) {
            count++;
            scan++;
        }
        break;
    case ANYBUT:
        while( *scan != '\0' && StrChr(opnd, *scan) == NULL ) {
            count++;
            scan++;
        }
        break;
    default:                /* Oh dear.  Called inappropriately. */
        regError(ERR_RE_INTERNAL_FOULUP);
        count = 0;      /* Best compromise. */
        break;
    }
    reginput = scan;

    return(count);
}

/*
 - regnext - dig the "next" pointer out of a node
 */
static char *regnext( char *p )
{
    int offset;

    if( p == &regdummy ) {
        return( NULL );
    }

    offset = NEXT(p);
    if( offset == 0 ) {
        return( NULL );
    }

    if (OP(p) == BACK) {
        return( p-offset );
    } else {
        return( p+offset );
    }
}

void RegAnchor( regexp * reg )
/****************************/
/* mark a regular expression as being "anchored", i.e. as an expression that
 * occurs at the beginning-of-line only */
{
    if( reg != NULL ) {
        reg->reganch = TRUE;
    }
}
