*   Copyright (c) 1998, 2002 Michael J. Roberts.  All Rights Reserved.

 *   

 *   Please see the accompanying license file, LICENSE.TXT, for information

 *   on using and copying this software.  

 */

/*

Name

  vmregex.h - regular expression parser for T3

Function

Notes

  Adapted from the TADS 2 regular expression parser.  This version

  uses UTF-8 strings rather than simple single-byte character strings,

  and is organized into a C++ class.

Modified

  04/11/99 CNebel     - Fix warnings.

  10/07/98 MJRoberts  - Creation

*/

#ifndef VMREGEX_H

#define VMREGEX_H

#include <stdlib.h>

#include "t3std.h"

#include "vmuni.h"

#include "utf8.h"

#include "vmerr.h"

#include "vmerrnum.h"

/* state ID */

typedef int re_state_id;

/* invalid state ID - used to mark null machines */

#define RE_STATE_INVALID   ((re_state_id)-1)

/* first valid state ID */

#define RE_STATE_FIRST_VALID  ((re_state_id)0)

/* ------------------------------------------------------------------------ */

/*

 *   Group register structure.  Each register keeps track of the starting

 *   and ending offset of the group's text within the original search

 *   string.  

 */

struct re_group_register

{

    int start_ofs;

    int end_ofs;

};

/* maximum number of group registers we keep */

#define RE_GROUP_REG_CNT  10

/* maximum group nesting depth */

#define RE_GROUP_NESTING_MAX  20

/* 

 *   the maximum number of separate loop variables we need is the same as

 *   the group nesting level, since we only need one loop variable per

 *   nested group 

 */

#define RE_LOOP_VARS_MAX  RE_GROUP_NESTING_MAX

/* ------------------------------------------------------------------------ */

/*

 *   Recognizer types. 

 */

enum re_recog_type

{

    /* invalid/uninitialized */

    RE_INVALID,

    /* literal character recognizer */

    RE_LITERAL,

    /* "epsilon" recognizer - match without consuming anything */

    RE_EPSILON,

    /* wildcard character */

    RE_WILDCARD,

    /* beginning and end of text */

    RE_TEXT_BEGIN,

    RE_TEXT_END,

    /* start and end of a word */

    RE_WORD_BEGIN,

    RE_WORD_END,

    /* word-char and non-word-char */

    RE_WORD_CHAR,

    RE_NON_WORD_CHAR,

    /* word-boundary and non-word-boundary */

    RE_WORD_BOUNDARY,

    RE_NON_WORD_BOUNDARY,

    /* a character range/exclusion range */

    RE_RANGE,

    RE_RANGE_EXCL,

    /* group entry/exit transition */

    RE_GROUP_ENTER,

    RE_GROUP_EXIT,

    /* 

     *   group matcher - the character code has the group number (0 for

     *   group 0, etc) rather than a literal to match 

     */

    RE_GROUP_MATCH,

    /* any alphabetic character */

    RE_ALPHA,

    /* any digit */

    RE_DIGIT,

    /* any upper-case alphabetic */

    RE_UPPER,

    /* any lower-case alphabetic */

    RE_LOWER,

    /* any alphanumeric */

    RE_ALPHANUM,

    /* space character */

    RE_SPACE,

    /* punctuation character */

    RE_PUNCT,

    /* newline character */

    RE_NEWLINE,

    /* null character (used in range recognizers) */

    RE_NULLCHAR,

    /* positive assertion */

    RE_ASSERT_POS,

    /* negative assertion */

    RE_ASSERT_NEG,

    /* loop entry: zero the associated loop variable */

    RE_ZERO_VAR,

    /* loop branch: inspect loop criteria and branch accordingly */

    RE_LOOP_BRANCH

};

/* ------------------------------------------------------------------------ */

/* 

 *   Denormalized state transition tuple.  Each tuple represents the

 *   complete set of transitions out of a particular state.  A particular

 *   state can have one character transition, or two epsilon transitions.

 *   Note that we don't need to store the state ID of the tuple itself in

 *   the tuple, because the state ID is the index of the tuple in an array

 *   of state tuples.  

 */

struct re_tuple

{

    /* recognizer type */

    re_recog_type typ;

    /* the character we must match to transition to the target state */

    union

    {

        /* 

         *   if this is a character transition, this is the character (used

         *   as the character literal in RE_LITERAL, and as the group ID in

         *   RE_GROUP_MATCH and in RE_EPSILON nodes with the group flag set) 

         */

        wchar_t ch;

        /* 

         *   if this has a sub-machine, this is the start and end info (used

         *   for RE_ASSERT_POS, RE_ASSERT_NEG) 

         */

        struct

        {

            re_state_id init;

            re_state_id final;

        } sub;

        /* 

         *   if this is a loop, the loop parameters (used for RE_ZERO_VAR,

         *   RE_LOOP_BRANCH) 

         */

        struct

        {

            int loop_min;

            int loop_max;

            int loop_var;

        } loop;

        /* 

         *   Character range match table - this is used if the recognizer

         *   type is RE_RANGE or RE_RANGE_EXCL; for other recognizer types,

         *   this is not used.

         *   

         *   If used, this is an array of pairs of characters.  In each pair,

         *   the first is the low end of the range, and the second is the

         *   high end of the range, both ends inclusive.  A single character

         *   takes up two entries, both identical, to specify a range of only

         *   one character.

         *   

         *   If the first character is '\0', then neither wchar_t is a

         *   character in the ordinary sense described above.  Instead, the

         *   second wchar_t is actually one of the recognizer type codes

         *   (re_recog_type) for a character class (RE_ALPHA, RE_DIGIT, etc).

         *   The pair in this case is to be taken to match (or exclude) the

         *   entire class.

         *   

         *   To represent a match for '\0', use '\0' for the first wchar_t

         *   and RE_NULLCHAR for the second wchar_t.  Note that the special

         *   meaning of '\0' in the first character of a pair makes it

         *   impossible to represent a range including a null byte with a

         *   single pair; instead, representing a range like [\000-\017]

         *   requires two pairs: the first pair is ('\0', RE_NULLCHAR), and

         *   the second pair is ('\001', '\017').  

         */

        struct

        {

            wchar_t *char_range;

            size_t char_range_cnt;

        } range;

    } info;

    /* the target states */

    re_state_id next_state_1;

    re_state_id next_state_2;

    /* flags */

    unsigned char flags;

};

/*

 *   Tuple flags 

 */

/* this state is being tested for a cycle */

#define RE_STATE_CYCLE_TEST   0x08

/* 

 *   for branching states: take the shortest, rather than longest, branch

 *   when both branches are successful 

 */

#define RE_STATE_SHORTEST     0x10

/* ------------------------------------------------------------------------ */

/*

 *   A "machine" description.  A machines is fully described by its initial

 *   and final state ID's.  

 */

struct re_machine

{

    /* the machine's initial state */

    re_state_id init;

    /* the machine's final state */

    re_state_id final;

};

/* ------------------------------------------------------------------------ */

/*

 *   Compiled pattern description.  This is not a complete compiled pattern,

 *   since the tuple array is separate; this is just a description of the

 *   compiled pattern that can be combined with the tuple array to form a

 *   full compiled pattern.

 */

struct re_compiled_pattern_base

{

    /* the pattern's machine description */

    re_machine machine;

    /* the number of tuples in the tuple array */

    re_state_id tuple_cnt;

    /* number of capturing groups in the expression */

    int group_cnt;

    /* maximum number of looping variables in the expression */

    int loop_var_cnt;

    /*

     *   <Case> or <NoCase> mode.  If this flag is clear, the search is not

     *   case-sensitive, so alphabetic characters in the pattern are matched

     *   without regard to case.  

     */

    int case_sensitive : 1;

    /* 

     *   <MIN> or <MAX> match mode -- if this flag is set, we match the

     *   longest string in case of ambiguity; otherwise we match the

     *   shortest.  

     */

    int longest_match : 1;

    /* 

     *   <FirstEnd> or <FirstBeg> match mode -- if this flag is set, we

     *   match (in a search) the string that starts first in case of

     *   ambiguity; otherwise, we match the string that ends first 

     */

    int first_begin : 1;

};

/*

 *   Compiled pattern object.  This is a pattern compiled and saved for use

 *   in searches and matches.  This is a compiled pattern description

 *   coupled with its tuple array, which in combination provide a complete

 *   compiled pattern.  

 */

struct re_compiled_pattern: re_compiled_pattern_base

{

    /* 

     *   the tuple array (the structure is overallocated to make room for

     *   tuple_cnt entries in this array) 

     */

    re_tuple tuples[1];

};

/* ------------------------------------------------------------------------ */

/*

 *   Status codes 

 */

typedef enum

{

    /* success */

    RE_STATUS_SUCCESS = 0,

    /* compilation error - group nesting too deep */

    RE_STATUS_GROUP_NESTING_TOO_DEEP

} re_status_t;

/* ------------------------------------------------------------------------ */

/*

 *   Regular expression compilation context structure.  This tracks the

 *   state of the compilation and stores the resources associated with the

 *   compiled expression.  

 */

class CRegexParser

{

    friend class CRegexSearcher;

    friend class CRegexSearcherSimple;

public:

    /* initialize */

    CRegexParser();

    /* delete */

    ~CRegexParser();

    /* 

     *   Compile an expression and create a compiled pattern object, filling

     *   in *pattern with a pointer to the newly-allocated pattern object.

     *   The caller is responsible for freeing the pattern by calling

     *   free_pattern(pattern).  

     */

    re_status_t compile_pattern(const char *expr_str, size_t exprlen,

                                re_compiled_pattern **pattern);

    /* free a pattern previously created with compile_pattern() */

    static void free_pattern(re_compiled_pattern *pattern);

    /* set the default case sensitivity */

    void set_default_case_sensitive(int f) { default_case_sensitive_ = f; }

protected:

    /* reset the parser */

    void reset();

    /* allocate a new state ID */

    re_state_id alloc_state();

    /* set a transition from a state to a given destination state */

    void set_trans(re_state_id id, re_state_id dest_id,

                   re_recog_type typ, wchar_t ch);

    /* initialize a new machine, setting up the initial and final state */

    void init_machine(struct re_machine *machine);

    /* build a character recognizer */

    void build_char(struct re_machine *machine, wchar_t ch);

    /* build a special recognizer */

    void build_special(struct re_machine *machine,

                       re_recog_type typ, wchar_t ch);

    /* build a character range recognizer */

    void build_char_range(struct re_machine *machine, int exclusion);

    /* build a group recognizer */

    void build_group_matcher(struct re_machine *machine, int group_num);

    /* build a concatenation recognizer */

    void build_concat(struct re_machine *new_machine,

                      struct re_machine *lhs, struct re_machine *rhs);

    /* build a group machine */

    void build_group(struct re_machine *new_machine,

                     struct re_machine *sub_machine, int group_id);

    /* build a positive or negative assertion machine */

    void build_assert(struct re_machine *new_machine,

                      struct re_machine *sub_machine, int is_negative);

    /* build an alternation recognizer */

    void build_alter(struct re_machine *new_machine,

                     struct re_machine *lhs, struct re_machine *rhs);

    /* build a closure recognizer */

    void build_closure(struct re_machine *new_machine,

                       struct re_machine *sub, wchar_t specifier,

                       int shortest);

    /* build an interval matcher */

    void build_interval(struct re_machine *new_machine,

                        struct re_machine *sub, int min_val, int max_val,

                        int var_id, int shortest);

    /* build a null machine */

    void build_null_machine(struct re_machine *machine);

    /* determine if a machine is null */

    int is_machine_null(struct re_machine *machine);

    /* concate the second machine onto the first machine */

    void concat_onto(struct re_machine *dest, struct re_machine *rhs);

    /* alternate the second machine onto the first */

    void alternate_onto(struct re_machine *dest, struct re_machine *rhs);

    /* compile an expression */

    re_status_t compile(const char *expr_str, size_t exprlen,

                        re_compiled_pattern_base *pat);

    /* compile a character class or class range expression */

    int compile_char_class_expr(utf8_ptr *expr, size_t *exprlen,

                                re_machine *result_machine);

    /* parse an integer value */

    int parse_int(utf8_ptr *p, size_t *rem);

    /* add a character to our range buffer */

    void add_range_char(wchar_t ch) { add_range_char(ch, ch); }

    void add_range_char(wchar_t ch_lo, wchar_t ch_hi);

    /* add a character class to our range buffer */

    void add_range_class(re_recog_type cl);

    /* ensure space in the range buffer for another entry */

    void ensure_range_buf_space();

    /* break any infinite loops in the machine */

    void break_loops(re_machine *machine);

    /* find an infinite loop back to the given state */

    int find_loop(re_machine *machine, re_state_id cur_state);

    /* optimize away meaningless branch-to-branch transitions */

    void remove_branch_to_branch(re_machine *machine);

    void optimize_transition(const re_machine *machine, re_state_id *trans);

    /* next available state ID */

    re_state_id next_state_;

    /*

     *   The array of transition tuples.  We'll allocate this array and

     *   expand it as necessary.  

     */

    re_tuple *tuple_arr_;

    /* number of transition tuples allocated in the array */

    int tuples_alloc_;

    /* buffer for building range exprssions */

    wchar_t *range_buf_;

    /* current number of entries in range buffer */

    size_t range_buf_cnt_;

    /* maximum number of entries in range buffer */

    size_t range_buf_max_;

    /* are our expressions case-sensitive by default? */

    int default_case_sensitive_;

};

/* ------------------------------------------------------------------------ */

/*

 *   Pattern recognizer state stack.  Each time we need to process a

 *   sub-state (a two-way epsilon, or a nested assertion), we stack the

 *   current state so that we can backtrack when we're done with the

 *   sub-expression.  The state we store consists of:

 *   

 *   - backtrack type - this is an arbitrary uchar identifier that the

 *   pattern matcher uses to identify where to go when we pop the state

 *   

 *   - the current state ID

 *   

 *   - the current offset in the string being matched

 *   

 *   - the state ID of the terminating state of the machine

 *   

 *   - saved group registers; we only store the ones we've actually

 *   modified, to avoid unnecessary copying

 *   

 *   - saved loop variables; we only store the ones we've actually modified,

 *   to avoid unnecessary copying 

 */

/* the base structure for a stacked state */

struct regex_stack_entry

{

    /* the backtrack type identifier */

    short typ;

    /* the starting offset in the string */

    int start_ofs;

    /* the current offset in the string */

    int str_ofs;

    /* the pattern state */

    re_state_id state;

    /* the final state of the machine */

    re_state_id final;

    /* the return value for this state */

    int retval;

    /* stack offset of previous frame */

    int prv_sp;

};

/* saved group/loop entry */

struct regex_stack_var

{

    /* 

     *   The ID - this is in the range 0..RE_GROUP_REG_CNT-1 for group

     *   registers, RE_GROUP_REG_CNT..RE_GROUP_REG_CNT+RE_LOOP_VARS_MAX-1

     *   for loop variables.  In other words, a loop variable is identified

     *   by its loop variable number plus RE_GROUP_REG_CNT.  The special ID

     *   value -1 indicates the integer 'retval' value (a saved return value

     *   for the stack state).  

     */

    int id;

    /* the value */

    union

    {

        re_group_register group;

        short loopvar;

        int retval;

    } val;

};

/* state stack class */

class CRegexStack

{

public:

    CRegexStack()

    {

        /* allocate the initial state buffer */

        bufsiz_ = 8192;

        buf_ = (char *)t3malloc(bufsiz_);

        /* we don't have anything on the stack yet */

        sp_ = -1;

        used_ = 0;

    }

    ~CRegexStack()

    {

        /* delete the stack buffer */

        t3free(buf_);

    }

    /* reset the stack */

    void reset()

    {

        /* empty the stack */

        sp_ = -1;

        used_ = 0;

    }

    /* push a new state */

    void push(ushort typ, int start_ofs, int str_ofs,

              re_state_id state, re_state_id final)

    {

        regex_stack_entry *fp;

        /* 

         *   Ensure we have enough space for the base state structure plus a

         *   full complement of group registers, loop variables, and return

         *   value.  We might not actually need all of the registers and

         *   loop variables, so we won't commit all of this space yet, but

         *   check in advance to make sure we have it so that we don't have

         *   to check again when and if we get around to consuming

         *   group/loop slots.  

         */

        ensure_space(sizeof(regex_stack_entry)

                     + ((RE_GROUP_REG_CNT + RE_LOOP_VARS_MAX + 1)

                        *sizeof(regex_stack_var)));

        /* allocate the base stack frame */

        fp = (regex_stack_entry *)alloc_space(sizeof(regex_stack_entry));

        /* set it up */

        fp->typ = typ;

        fp->start_ofs = start_ofs;

        fp->str_ofs = str_ofs;

        fp->state = state;

        fp->final = final;

        /* push it onto the stack */

        fp->prv_sp = sp_;

        sp_ = (char *)fp - buf_;

    }

    /* save a group register */

    void save_group_reg(int id, const re_group_register *regs)

    {

        regex_stack_var *var;

        /* allocate a new slot if needed and save the value */

        if (sp_ != -1 && (var = new_reg_or_var(id)) != 0)

            var->val.group = regs[id];

    }

    /* save a loop variable */

    void save_loop_var(int id, const short *loop_vars)

    {

        regex_stack_var *var;

        /* 

         *   allocate a new slot if needed and save the value; note that

         *   loop variables are identified by the loop variable ID plus the

         *   base index RE_GROUP_REG_CNT 

         */

        if (sp_ != -1 && (var = new_reg_or_var(id + RE_GROUP_REG_CNT)) != 0)

            var->val.loopvar = loop_vars[id];

    }

    /* 

     *   get the type of the state at top of stack; if there is no state,

     *   returns -1 

     */

    int get_top_type()

    {

        /* 

         *   if there's nothing on the stack, so indicate, otherwise get the

         *   type from the top stack element 

         */

        if (sp_ == -1)

            return -1;

        else

            return ((regex_stack_entry *)(buf_ + sp_))->typ;

    }

    /* get the stack frame at the given depth (0 is top of stack) */

    regex_stack_entry *get_frame(int depth)

    {

        regex_stack_entry *fp;

        /* traverse the given number of frames from the top of the stack */

        for (fp = (regex_stack_entry *)(buf_ + sp_) ; depth != 0 ; --depth)

            fp = (regex_stack_entry *)(buf_ + fp->prv_sp);

        /* return the frame pointer */

        return fp;

    }

    /* pop a state */

    void pop(int *start_ofs, int *str_ofs,

             re_state_id *state, re_state_id *final,

             re_group_register *regs, short *loop_vars)

    {

        regex_stack_entry *fp;

        regex_stack_var *var;

        /* get the stack pointer */

        fp = (regex_stack_entry *)(buf_ + sp_);

        /* restore the string offset and state ID */

        *start_ofs = fp->start_ofs;

        *str_ofs = fp->str_ofs;

        *state = fp->state;

        *final = fp->final;

        /* run through the saved registers/variables in the state */

        for (var = (regex_stack_var *)(fp + 1) ;

             var < (regex_stack_var *)(buf_ + used_) ; ++var)

        {

            /* sense the type */

            if (var->id < RE_GROUP_REG_CNT)

            {

                /* it's a group register */

                regs[var->id] = var->val.group;

            }

            else

            {

                /* it's a loop variable */

                loop_vars[var->id - RE_GROUP_REG_CNT] = var->val.loopvar;

            }

        }

        /* we're done with the stop stack frame, so discard it */

        discard();

    }

    /* discard the top stack state */

    void discard()

    {

        regex_stack_entry *fp;

        /* get the stack pointer */

        fp = (regex_stack_entry *)(buf_ + sp_);

        /* unwind the stack */

        used_ = (size_t)sp_;

        sp_ = fp->prv_sp;

    }

    /* 

     *   Save the current state at the top of the stack and push a new

     *   state.  This is used to traverse the second branch of a two-branch

     *   epsilon: we first have to save the results of the first branch,

     *   including the return value and its registers, and we then have to

     *   restore the initial register/loop state as it was before the first

     *   branch.

     *   

     *   We save the final state and restore the initial state by swapping

     *   the group registers in the saved state with those in the current

     *   state.  This brings back the initial conditions to the current

     *   machine state, while saving everything that's changed in the

     *   current machine state in the stack frame.  We'll likewise swap the

     *   machine state and string offset.  Later, this same final machine

     *   state can be restored by first restoring the machine state to the

     *   initial state, then popping this frame.

     *   

     *   On return, the stack frame that was active on entry will be set to

     *   contain the current machine state, and the current machine state

     *   will be replaced with what was in that stack frame.  In addition,

     *   we'll have pushed a new stack frame for the new current machine

     *   state.  

     */

    void save_and_push(int retval,

                       ushort typ, int *start_ofs, int *str_ofs,

                       re_state_id *state, re_state_id *final,

                       re_group_register *regs, short *loop_vars)

    {

        regex_stack_entry *fp;

        regex_stack_var *var;

        int tmp_ofs;

        re_state_id tmp_id;

        /* get the stack pointer */

        fp = (regex_stack_entry *)(buf_ + sp_);

        /* swap the string offset */

        tmp_ofs = *str_ofs;

        *str_ofs = fp->str_ofs;

        fp->str_ofs = tmp_ofs;

        /* swap the starting offset */

        tmp_ofs = *start_ofs;

        *start_ofs = fp->start_ofs;

        fp->start_ofs = tmp_ofs;

        /* swap the current machine state */

        tmp_id = *state;

        *state = fp->state;

        fp->state = tmp_id;

        /* swap the final machine state */

        tmp_id = *final;

        *final = fp->final;

        fp->final = tmp_id;

        /* swap all group and loop registers with the current state */

        for (var = (regex_stack_var *)(fp + 1) ;

             var < (regex_stack_var *)(buf_ + used_) ; ++var)

        {

            /* sense the type */

            if (var->id < RE_GROUP_REG_CNT)

            {

                re_group_register tmp;

                /* it's a group register */

                tmp = regs[var->id];

                regs[var->id] = var->val.group;

                var->val.group = tmp;

            }

            else

            {

                short tmp;

                /* it's a loop variable */

                tmp = loop_vars[var->id - RE_GROUP_REG_CNT];

                loop_vars[var->id - RE_GROUP_REG_CNT] = var->val.loopvar;

                var->val.loopvar = tmp;

            }

        }

        /* save the return value from the outgoing state */

        fp->retval = retval;

        /* push a copy of the restored state */

        push(typ, *start_ofs, *str_ofs, *state, *final);

    }

protected:

    /* 

     *   allocate a new register or group variable in the stack frame; if we

     *   find an existing copy of the same variable, we'll return null to

     *   indicate that we don't have to save it again 

     */

    regex_stack_var *new_reg_or_var(int id)

    {

        regex_stack_entry *fp;

        regex_stack_var *var;

        /* get the stack pointer */

        fp = (regex_stack_entry *)(buf_ + sp_);

        /* scan the frame for a register/variable with this ID */

        for (var = (regex_stack_var *)(fp + 1) ;

             var < (regex_stack_var *)(buf_ + used_) ; ++var)

        {

            /* if this is the one, we don't need to save it again */

            if (var->id == id)

                return 0;

        }

        /* we didn't find it, so return a new entry with the given ID */

        var = (regex_stack_var *)alloc_space(sizeof(regex_stack_var));

        var->id = id;

        return var;

    }

    /* ensure space in our stack buffer */

    void ensure_space(size_t siz)

    {

        /* if it's within range, we're fine */

        if (used_ + siz <= bufsiz_)

            return;

        /* expand */

        bufsiz_ += 8192;

        /* if it's too large, throw an error */

        if (bufsiz_ > OSMALMAX)

            err_throw(VMERR_OUT_OF_MEMORY);

        /* reallocate at the new size */

        buf_ = (char *)t3realloc(buf_, bufsiz_);

        /* make sure we're not out of memory */

        if (buf_ == 0)

            err_throw(VMERR_OUT_OF_MEMORY);

    }

    /*