//+---------------------------------------------------------------------------
//
//  Copyright (C) Microsoft, 1994 - 2002.
//
//  File:       reimpl2.h
//
//  Functions:  helpers for matching and substituting regular expressions
//
//  Notes:      implementation details that really belong in a cpp file,
//              but can't because of template weirdness
//
//  Author:     Eric Niebler (ericne@microsoft.com)
//
//  History:    8/15/2001   ericne   Created
//
//------------------------------------------------------------------------------------------------------------------------------

#ifndef REIMPL_H
#define REIMPL_H

//
// Helper functions for match and substitute
//

namespace detail
{

// For use while doing uppercase/lowercase conversions:
inline  char   regex_toupper( char   ch) { using namespace std; return ( char  )toupper(ch); }
inline  char   regex_tolower( char   ch) { using namespace std; return ( char  )tolower(ch); }
inline wchar_t regex_toupper(wchar_t ch) { using namespace std; return (wchar_t)towupper(ch); }
inline wchar_t regex_tolower(wchar_t ch) { using namespace std; return (wchar_t)towlower(ch); }

template< typename IBeginT, typename IEndT >
inline VOID regex_toupper(IBeginT ibegin, IEndT iend)
{
    typedef typename std::iterator_traits<IEndT>::value_type char_type;
    typedef std::char_traits<char_type> traits_type;

    for(; iend != ibegin; ++ibegin)
        traits_type::assign(*ibegin, regex_toupper(*ibegin));
}

template< typename IBeginT, typename IEndT >
inline VOID regex_tolower(IBeginT ibegin, IEndT iend)
{
    typedef typename std::iterator_traits<IEndT>::value_type char_type;
    typedef std::char_traits<char_type> traits_type;

    for(; iend != ibegin; ++ibegin)
        traits_type::assign(*ibegin, regex_tolower(*ibegin));
}

//
// Helper fn for swapping two auto_ptr's
//
template< typename T >
inline VOID swap_auto_ptr(std::auto_ptr<T> & left, std::auto_ptr<T> & right)
{
    std::auto_ptr<T> temp(left);
    left  = right;
    right = temp;
}

template< typename T >
inline VOID reset_auto_ptr(std::auto_ptr<T> & left)
{
    std::auto_ptr<T> temp(0);
    left = temp;
}

template< typename T, typename U >
inline VOID reset_auto_ptr(std::auto_ptr<T> & left, U * right)
{
    std::auto_ptr<T> temp(right);
    left = temp;
}

typedef int instantiator;

inline instantiator REGEX_CDECL instantiator_helper(...)
{
    return instantiator();
}

// --------------------------------------------------------------------------
//
// Class:       match_param
//
// Description: Struct that contains the state of the matching operation.
//              Passed by reference to all recursive_match_all and recursive_match_this routines.
//
// Methods:     match_param - ctor
//
// Members:     ibufferbegin - start of the buffer
//              ibegin       - start of this iteration
//              iend        - end of the string
//              prgbackrefs  - pointer to backref array
//
// History:     8/14/2000 - ericne - Created
//
// --------------------------------------------------------------------------
template< typename IterT >
struct match_param
{
    typedef backref_tag<IterT>              backref_type;
    typedef sub_expr_base<IterT> CONST *    sub_expr_ptr;

    // for performance reasons, the most frequently used fields 
    // are placed at offsets which are a power of 2 (assuming
    // a 32-bit architecture, and iterators which are 32 bits).

    backref_type *      m_prgbackrefs;      // offsetof == 0
    IterT               m_iend;             // offsetof == 4
    IterT               m_icur;             // offsetof == 8
    size_t              m_cbackrefs;
    sub_expr_ptr        m_pnext;            // offsetof == 16
    IterT               m_ibufferbegin;
    IterT               m_imatchbegin;
    sub_expr_ptr        m_pfirst;
    unsafe_stack *      m_pstack;           // offsetof == 32
    bool                m_no0len;
    bool                m_reserved;

    match_param
    (
        IterT           ibufferbegin,
        IterT           imatchbegin,
        IterT           iend,
        backref_type *  prgbackrefs,
        size_t          cbackrefs
   )
        : m_prgbackrefs(prgbackrefs)
        , m_iend(iend)
        , m_icur(imatchbegin)
        , m_cbackrefs(cbackrefs)
        , m_pnext(0)
        , m_ibufferbegin(ibufferbegin)
        , m_imatchbegin(imatchbegin)
        , m_pfirst(0)
        , m_pstack(0)
        , m_no0len(false)
        , m_reserved(false)
    {
    }
};

// --------------------------------------------------------------------------
//
// Class:       arena_allocator
//
// Description: A small, fast allocator for speeding up pattern compilation.
//              Every basic_rpattern object has an arena as a member.
//              sub_expr objects can only be allocated from this arena.
//              Memory is alloc'ed in chunks using the underlying allocator.
//              Chunks are freed en-masse when clear() or finalize() is called.
//
// History:     8/17/2001 - ericne - Created
//
// Notes:       This is NOT a std-compliant allocator and CANNOT be used with
//              STL containers. arena_allocator objects maintain state, and
//              STL containers are allowed to assume their allocators do
//              not maintain state. In regexpr2.cpp, I define slist<>, a simple
//              arena-friendly singly-linked list for use with the arena
//              allocator.
//
// --------------------------------------------------------------------------
template< typename AllocT = std::allocator<char> >
struct pool_impl
{
    typedef typename rebind<AllocT, char>::type char_allocator_type;

    struct mem_block
    {
        size_t  m_offset;
        size_t  m_blocksize;
        mem_block * m_pnext;
        unsigned char m_data[ 1 ];
    };
#if !defined(_MSC_VER) | 1200 < _MSC_VER
    struct pool_data : char_allocator_type
    {
        pool_data(size_t default_size, char_allocator_type CONST & alloc)
            : char_allocator_type(alloc)
            , m_pfirst(0)
            , m_default_size(default_size)
        {
        }
        mem_block * m_pfirst;
        size_t      m_default_size;
        char_allocator_type & get_allocator()
        {
            return *this;
        }
    } m_data;
#else
    struct pool_data
    {
        pool_data(size_t default_size, char_allocator_type CONST & alloc)
            : m_alloc(alloc)
            , m_pfirst(0)
            , m_default_size(default_size)
        {
        }
        char_allocator_type m_alloc;
        mem_block * m_pfirst;
        size_t      m_default_size;
        char_allocator_type & get_allocator()
        {
            return m_alloc;
        }
    } m_data;
#endif
    VOID new_block(size_t size);
    VOID clear();
    VOID * allocate(size_t size);
    explicit pool_impl(size_t default_size, char_allocator_type CONST & alloc = char_allocator_type());
    ~pool_impl();
    char_allocator_type get_allocator() CONST
    {
        return const_cast<pool_impl*>(this)->m_data.get_allocator();
    }
};

template< typename T, typename AllocT = std::allocator<char> >
class arena_allocator
{
public:
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T *pointer;
    typedef T CONST *const_pointer;
    typedef T & reference;
    typedef T CONST & const_reference;
    typedef T value_type;

    typedef typename rebind<AllocT, char>::type			char_alloc_type;
    typedef pool_impl<AllocT> pool_impl_t;
    typedef typename rebind<AllocT, pool_impl_t>::type	pool_alloc_type;

    explicit arena_allocator(size_t default_size, char_alloc_type CONST & alloc = char_alloc_type())
        : m_pool(0)
    {
        char_alloc_type char_alloc(alloc);
        pool_alloc_type pool_alloc(convert_allocator<pool_impl_t>(char_alloc, 0));
        m_pool = pool_alloc.allocate(1, 0);
        pool_alloc.construct(m_pool, pool_impl_t(default_size, char_alloc)); // can't throw
    }
#if !defined(_MSC_VER) | 1200 < _MSC_VER
    arena_allocator(arena_allocator CONST & that)
        : m_pool(that.m_pool)
    {
    }
#endif
    template< typename U >
    arena_allocator(arena_allocator<U> CONST & that)
        : m_pool(that.m_pool)
    {
    }
    ~arena_allocator()
    { // Many arena_allocators may point to m_pool, so don't delete it.
    } // Rather, wait for someone to call finalize().
    pointer allocate(size_type size, VOID CONST * =0)
    {
        return static_cast<T*>(m_pool->allocate(size * sizeof(T)));
    }
    VOID deallocate(VOID *, size_type)
    { // no-op. deallocation happens when pool is finalized or cleared.
    }
    VOID construct(pointer p, T CONST & t)
    {
        new(static_cast<VOID*>(p)) T(t);
    }
    VOID destroy(pointer p)
    {
        regex::detail::destroy(p);
    }
#if !defined(_MSC_VER) | 1200 < _MSC_VER
    template< typename U > struct rebind
    {
        typedef arena_allocator<U> other;
    };
#endif
    VOID clear()
    {
        m_pool->clear();
    }
    VOID finalize()
    {
        char_alloc_type char_alloc(m_pool->get_allocator());
        pool_alloc_type pool_alloc(convert_allocator<pool_impl_t>(char_alloc, 0));
        pool_alloc.destroy(m_pool);
        pool_alloc.deallocate(m_pool, 1);
        m_pool = 0;
    }
    VOID swap(arena_allocator & that)
    {
        using std::swap;
        swap(m_pool, that.m_pool);
    }

    // the pool lives here
    pool_impl_t * m_pool;
};

// Dummy struct used by the pool allocator to align returned pointers
struct not_pod
{
    virtual ~not_pod() {}
};

template< typename AllocT >
inline pool_impl<AllocT>::pool_impl(size_t default_size, char_allocator_type CONST & alloc)
    : m_data(default_size, alloc)
{
}

template< typename AllocT >
inline pool_impl<AllocT>::~pool_impl()
{
    clear();
}

template< typename AllocT >
inline VOID pool_impl<AllocT>::clear()
{
    for(mem_block * pnext; m_data.m_pfirst; m_data.m_pfirst = pnext)
    {
        pnext = m_data.m_pfirst->m_pnext;
        m_data.get_allocator().deallocate(reinterpret_cast<char*>(m_data.m_pfirst), m_data.m_pfirst->m_blocksize);
    }
}

template< typename AllocT >
inline VOID pool_impl<AllocT>::new_block(size_t size)
{
    size_t blocksize = regex_max(m_data.m_default_size, size) + offsetof(mem_block, m_data);
    mem_block * pnew = reinterpret_cast<mem_block*>(m_data.get_allocator().allocate(blocksize, 0));
    if(0 == pnew)
    {
        throw std::bad_alloc();
    }
    pnew->m_offset      = 0;
    pnew->m_blocksize   = blocksize;
    pnew->m_pnext       = m_data.m_pfirst;
    m_data.m_pfirst     = pnew;
}

template< typename AllocT >
inline VOID * pool_impl<AllocT>::allocate(size_t size)
{
    if(0 == size)
        size = 1;

    if(0 == m_data.m_pfirst || m_data.m_pfirst->m_offset + size > m_data.m_default_size)
        new_block(size);

    VOID * pnew = m_data.m_pfirst->m_data + m_data.m_pfirst->m_offset;

    // ensure returned pointers are always suitably aligned
    m_data.m_pfirst->m_offset += ((size + alignof<not_pod>::value - 1)
                                 & ~(alignof<not_pod>::value - 1));

    return pnew;
}

// The regex_arena is a basic, vanilla arena_allocator.
typedef arena_allocator<char> regex_arena;

template< typename T >
type_with_size<3> allocator_picker(arena_allocator<T> CONST &, int);

template<> struct rebind_helper<3>
{
	template< typename, typename ElemT>
	struct inner
	{
		typedef arena_allocator<ElemT> type;
	};
};

// --------------------------------------------------------------------------
//
// Class:       sub_expr_base
//
// Description: patterns are "compiled" into a directed graph of sub_expr_base
//              structs.  Matching is accomplished by traversing this graph.
//
// Methods:     ~sub_expr_base - virt dtor so cleanup happens correctly
//              recursive_match_all      - match this sub-expression and all following
//                               sub-expression
//
// History:     8/14/2000 - ericne - Created
//
// --------------------------------------------------------------------------
template< typename IterT >
struct sub_expr_base
{
    virtual bool recursive_match_all_s(match_param<IterT> &, IterT) CONST = 0; //throw() (offset 0)
    virtual bool recursive_match_all_c(match_param<IterT> &, IterT) CONST = 0; //throw() (offset 4)
    virtual bool iterative_match_this_s(match_param<IterT> &) CONST = 0; //throw()       (offset 8)
    virtual bool iterative_match_this_c(match_param<IterT> &) CONST = 0; //throw()       (offset 12)
    virtual bool iterative_rematch_this_s(match_param<IterT> &) CONST = 0; //throw()     (offset 16)
    virtual bool iterative_rematch_this_c(match_param<IterT> &) CONST = 0; //throw()     (offset 20)

    virtual ~sub_expr_base() = 0;                                                       // (offset 24)

    // Use the regex_arena for memory management
    static VOID * operator new(size_t size, regex_arena & arena)
    {
        return arena.allocate(size);
    }
    static VOID operator delete(VOID *, regex_arena &)
    {
    }

    // Invoke the d'tor, but don't bother freeing memory. That will
    // happen automatically when the arena object gets destroyed.
    static VOID operator delete(VOID *)
    {
    }

    // For choosing an appropriate virtual function based on a compile time constant
    bool recursive_match_all(match_param<IterT> & param, IterT icur, false_t) CONST //throw()
    {
        return recursive_match_all_s(param, icur);
    }
    bool recursive_match_all(match_param<IterT> & param, IterT icur, true_t) CONST //throw()
    {
        return recursive_match_all_c(param, icur);
    }
    bool iterative_match_this(match_param<IterT> & param, false_t) CONST //throw()
    {
        return iterative_match_this_s(param);
    }
    bool iterative_match_this(match_param<IterT> & param, true_t) CONST //throw()
    {
        return iterative_match_this_c(param);
    }
    bool iterative_rematch_this(match_param<IterT> & param, false_t) CONST //throw()
    {
        return iterative_rematch_this_s(param);
    }
    bool iterative_rematch_this(match_param<IterT> & param, true_t) CONST //throw()
    {
        return iterative_rematch_this_c(param);
    }
private:
    // don't allocate sub-expressions directly on the heap; they should
    // be allocated from an arena
    static VOID * operator new(size_t size) throw(std::bad_alloc);
    // disable all the vector new's and delete's.
    static VOID * operator new[](size_t size, regex_arena & arena) throw(std::bad_alloc);
    static VOID operator delete[](VOID *, regex_arena &);
    static VOID * operator new[](size_t size) throw(std::bad_alloc);
    static VOID operator delete[](VOID *);
};

template< typename IterT >
inline sub_expr_base<IterT>::~sub_expr_base()
{
}

// --------------------------------------------------------------------------
//
// Class:       subst_node
//
// Description: Substitution strings are parsed into an array of these
//              structures in order to speed up subst operations.
//
// Members:     stype         - type of this struct
//              .m_subst_string  - do a string substitution
//             .m_subst_backref - do a bacref substitution
//              op            - execute an operation
//
// History:     8/14/2000 - ericne - Created
//
// --------------------------------------------------------------------------
struct subst_node
{
    enum
    {
        PREMATCH  = -1,
        POSTMATCH = -2
    };

    enum subst_type
    {
        SUBST_STRING,
        SUBST_BACKREF,
        SUBST_OP
    };

    enum op_type
    {
        UPPER_ON   = SUBST_UPPER_ON,
        UPPER_NEXT = SUBST_UPPER_NEXT,
        LOWER_ON   = SUBST_LOWER_ON,
        LOWER_NEXT = SUBST_LOWER_NEXT,
        ALL_OFF    = SUBST_ALL_OFF
    };

    struct string_offsets
    {
        ptrdiff_t       m_rstart;
        ptrdiff_t       m_rlength;
    };

    subst_type          m_stype;

    union
    {
        string_offsets  m_subst_string;
        size_t          m_subst_backref;
        op_type         m_op;
    };
};

typedef std::list<subst_node> subst_list_type;
size_t DEFAULT_BLOCK_SIZE();

template< typename IterT >
class boyer_moore;

// --------------------------------------------------------------------------
//
// Class:       basic_rpattern_base_impl
//
// Description:
//
// Methods:     basic_rpattern_base_impl - ctor
//              flags                   - get the state of the flags
//              uses_backrefs           - true if the backrefs are referenced
//              get_first_subexpression - return ptr to first sub_expr struct
//              get_width               - get min/max nbr chars this pattern can match
//              loops                   - if false, we only need to try to match at 1st position
//              cgroups                 - number of visible groups
//              _cgroups_total          - total number of groups, including hidden (?:) groups
//              get_pat                 - get string representing the pattern
//              get_subst               - get string representing the substitution string
//              get_subst_list          - get the list of subst nodes
//              _normalize_string       - perform character escaping
//
// Members:     m_fuses_backrefs        - true if subst string refers to backrefs
//              m_floop                 - false if pat only needs to be matched in one place
//              m_cgroups               - total count of groups
//              m_cgroups_visible       - count of visible groups
//              m_flags                 - the flags
//              m_nwidth                - width of this pattern
//              m_pat                   - pattern string
//              m_subst                 - substitution string
//              m_subst_list            - list of substitution nodes
//              m_pfirst                - ptr to first subexpression to match
//
// Typedefs:    char_type               -
//              string_type             -
//              size_type               -
//
// History:     8/14/2000 - ericne - Created
//
// --------------------------------------------------------------------------
template< typename IterT >
class basic_rpattern_base_impl
{
    basic_rpattern_base_impl(basic_rpattern_base_impl<IterT> CONST &);
    basic_rpattern_base_impl & operator=(basic_rpattern_base_impl<IterT> CONST &);
protected:
    typedef typename std::iterator_traits<IterT>::value_type char_type;
    typedef std::char_traits<char_type>                   traits_type;

    typedef std::basic_string<char_type>                  string_type;
    typedef size_t                                        size_type;

    typedef backref_tag<IterT>                             backref_type;
    typedef std::vector<backref_type>                     backref_vector;

    friend struct regex_access<IterT>;

    explicit basic_rpattern_base_impl
    (
        REGEX_FLAGS         flags = NOFLAGS,
        REGEX_MODE          mode  = MODE_DEFAULT,
        string_type CONST & pat   = string_type(),
        string_type CONST & subst = string_type()
   )                                               //throw()
        : m_arena(DEFAULT_BLOCK_SIZE())
        , m_fuses_backrefs(false)
        , m_floop(true)
        , m_fok_to_recurse(true)
        , m_cgroups(0)
        , m_cgroups_visible(0)
        , m_flags(flags)
        , m_mode(mode)
        , m_nwidth(uninit_width())
        , m_pat(new string_type(pat))
        , m_subst(new string_type(subst))
        , m_subst_list()
        , m_pfirst(0)
        , m_invisible_groups()
        , m_search(0)
    {
    }

    virtual ~basic_rpattern_base_impl()
    {
        // We're not going to be calling destructors because all allocated
        // memory associated with the parsed pattern resides in the arena.
        // The memory will be freed when the arena gets destroyed.
        //delete m_pfirst;
        reset_auto_ptr(m_pat);
        reset_auto_ptr(m_subst);
        m_arena.finalize();
    }

    regex_arena m_arena;           // The sub_expr arena

    bool        m_fuses_backrefs;  // true if the substitution uses backrefs
    bool        m_floop;           // false if m_pfirst->recursive_match_all only needs to be called once
    bool        m_fok_to_recurse;  // false if the pattern would recurse too deeply
    size_t      m_cgroups;         // number of groups (always at least one)
    size_t      m_cgroups_visible; // number of visible groups
    REGEX_FLAGS m_flags;           // flags used to customize search/replace
    REGEX_MODE  m_mode;            // Used to pick the fast or safe algorithm
    width_type  m_nwidth;          // width of the pattern

    std::auto_ptr<string_type>   m_pat;   // contains the unparsed pattern
    std::auto_ptr<string_type>   m_subst; // contains the unparsed substitution

    subst_list_type              m_subst_list; // used to speed up substitution
    sub_expr_base<IterT> CONST * m_pfirst;     // first subexpression in pattern

    std::list<size_t>           m_invisible_groups; // groups w/o backrefs

    boyer_moore<typename string_type::const_iterator>  * m_search;

    size_t _cgroups_total() CONST //throw()
    {
        return m_cgroups;
    }

    bool _loops() CONST //throw()
    {
        return m_floop;
    }

    size_t _get_next_group_nbr()
    {
        return m_cgroups++;
    }

    VOID _normalize_string(string_type & str) CONST //throw()
    {
        if(NORMALIZE & flags())
            process_escapes(str, true);
    }

    bool _save_backrefs() CONST //throw()
    {
        return m_fuses_backrefs || ! (flags() & NOBACKREFS);
    }

    sub_expr_base<IterT> CONST * _get_first_subexpression() CONST //throw()
    {
        return m_pfirst;
    }

    REGEX_FLAGS flags() CONST //throw()
    {
        return m_flags;
    }

    REGEX_MODE mode() CONST // throw()
    {
        return m_mode;
    }

    width_type get_width() CONST //throw()
    {
        return m_nwidth;
    }

    size_t cgroups() CONST //throw()
    {
        return m_cgroups_visible;
    }

    string_type CONST & get_pat() CONST //throw()
    {
        return *m_pat;
    }

    string_type CONST & get_subst() CONST //throw()
    {
        return *m_subst;
    }

    bool _ok_to_recurse() CONST; //throw();

    VOID swap(basic_rpattern_base_impl<IterT> & that); // throw();

    enum { npos = static_cast<size_type>(-1) };

    static instantiator instantiate()
    {
        typedef basic_rpattern_base_impl this_type;

        return instantiator_helper
        (
            &this_type::_ok_to_recurse,
            &this_type::swap
       );
    }
};

template< typename IterT >
struct regex_access
{
    typedef basic_rpattern_base_impl< IterT >    rpattern_type;
    typedef typename rpattern_type::size_type    size_type;
    typedef typename rpattern_type::char_type    char_type;
    typedef typename rpattern_type::traits_type  traits_type;
    typedef typename rpattern_type::backref_type backref_type;

    static bool _do_match_iterative_helper_s
    (
        sub_expr_base<IterT> CONST * expr,
        match_param<IterT> & param,
        IterT icur
   );

    static bool _do_match_iterative_helper_c
    (
        sub_expr_base<IterT> CONST * expr,
        match_param<IterT> & param,
        IterT icur
   );

    static bool _do_match_recursive_s
    (
        sub_expr_base<IterT> CONST * expr,
        match_param<IterT> & param,
        IterT icur
   );

    static bool _do_match_recursive_c
    (
        sub_expr_base<IterT> CONST * expr,
        match_param<IterT> & param,
        IterT icur
   );

    static bool _do_match_impl
    (
        rpattern_type CONST & pat,
        match_param<IterT> & param,
        bool CONST use_null
   );

    static bool _do_match_with_stack
    (
        rpattern_type CONST & pat,
        match_param<IterT> & param,
        bool CONST use_null
   );

    template< typename Alloc1T, typename Alloc2T >
    static VOID _fixup_backrefs
    (
        std::vector<backref_type,Alloc1T> & rgbackrefs,
        std::list<size_t,Alloc2T> CONST & invisible
   )
    {
        typedef typename std::list<size_t,Alloc2T>::const_iterator iter_type;

        // Remove information about the "invisible" groups
        if(rgbackrefs[0].matched)
        {
            size_t dropped = 0;
            iter_type CONST end = invisible.end();
            iter_type curr = invisible.begin(), next = invisible.begin();

            for(; end != curr; curr = next, ++dropped)
            {
                if(end == ++next)
                {
                    std::copy(
                        rgbackrefs.begin() + *curr + 1,
                        rgbackrefs.end(),
                        rgbackrefs.begin() + *curr - dropped);
                }
                else
                {
                    std::copy(
                        rgbackrefs.begin() + *curr + 1,
                        rgbackrefs.begin() + *next,
                        rgbackrefs.begin() + *curr - dropped);
                }
            }

            rgbackrefs.resize(rgbackrefs.size() - dropped);
        }
        else
        {
            rgbackrefs.resize(rgbackrefs.size() - invisible.size());
        }
    }

    template< typename AllocT >
    static bool _do_try_match
    (
        rpattern_type CONST & pat,
        match_param<IterT> & param,
        std::vector<backref_type,AllocT> & rgbackrefs,
        bool CONST use_null
   )
    {
        bool success;
        rgbackrefs.resize(pat._cgroups_total());
        param.m_prgbackrefs = & rgbackrefs[0];
        param.m_cbackrefs = rgbackrefs.size();

        REGEX_SEH_TRY
        {
            if(pat._ok_to_recurse())
            {
                success = _do_match_impl(pat, param, use_null);
            }
            else
            {
                success = _do_match_with_stack(pat, param, use_null);
            }
        }
        REGEX_SEH_EXCEPT(REGEX_SEH_STACK_OVERFLOW == _exception_code())
        {
            // we have overflowed the stack. reset the guard page.
            REGEX_RESET_STK_OFLW();

            // This match fails silently.
            for(size_t i=0; i < param.m_cbackrefs; ++i)
            {
                param.m_prgbackrefs[i] = static_init<backref_type>::value;
            }

            success = false;
        }

        _fixup_backrefs(rgbackrefs, pat.m_invisible_groups);
        return success;
    }

    template< typename AllocT >
    static bool _do_match
    (
        rpattern_type CONST & pat,
        basic_match_results<IterT,AllocT> & results,
        IterT ibegin,
        IterT iend,
        bool use_null
   )
    {
        typedef typename basic_match_results<IterT,AllocT>::backref_vector backref_vector;

        results.m_ibegin = ibegin;
        match_param<IterT> param(ibegin, ibegin, iend, 0, 0);

        if(GLOBAL & pat.flags()) // do a global find
        {
            // The NOBACKREFS flag is ignored in the match method.
            bool CONST fAll   = (ALLBACKREFS   == (ALLBACKREFS   & pat.flags()));
            bool CONST fFirst = (FIRSTBACKREFS == (FIRSTBACKREFS & pat.flags()));

            backref_vector rgtempbackrefs(results.m_rgbackrefs.get_allocator());

            while(_do_try_match(pat, param, results.m_rgbackrefs, use_null))
            {
                backref_type CONST & br = param.m_prgbackrefs[0];

                // Handle specially the backref flags
                if(fFirst)
                {
                    rgtempbackrefs.push_back(br);
                }
                else if(fAll)
                {
                    rgtempbackrefs.insert(
                        rgtempbackrefs.end(),
                        results.m_rgbackrefs.begin(),
                        results.m_rgbackrefs.end());
                }
                else
                {
                    rgtempbackrefs.swap(results.m_rgbackrefs);
                }

                param.m_imatchbegin = br.second;
                param.m_no0len = (br.first == br.second);
            }

            // restore the backref vectors
            results.m_rgbackrefs.swap(rgtempbackrefs);
            return ! results.m_rgbackrefs.empty();
        }
        else
        {
            return _do_try_match(pat, param, results.m_rgbackrefs, use_null);
        }
    }

    template< typename AllocT >
    static bool _do_match_c
    (
        rpattern_type CONST & pat,
        basic_match_results<IterT,AllocT> & results,
        char_type CONST * szbegin
   )
    {
        if(RIGHTMOST & pat.flags())
        {
            // We need to know the end of the string if we're doing a
            // RIGHTMOST match.
            char_type CONST * szend = szbegin;
            std::advance(szend, traits_type::length(szbegin));
            return _do_match(pat, results, szbegin, szend, false);
        }
        else
        {
            return _do_match(pat, results, szbegin, 0, true);
        }
    }

    static size_t _do_count
    (
        rpattern_type CONST & pat,
        IterT ibegin,
        IterT iend,
        bool use_null
   )
    {
        size_t cmatches = 0;
        std::vector<backref_type> rgbackrefs;

        // If your compile breaks here, it is because CharT CONST * is not
        // convertible to type IterT. Check the declaration of your rpattern object.
        match_param<IterT> param(ibegin, ibegin, iend, 0, 0);

        while(_do_try_match(pat, param, rgbackrefs, use_null))
        {
            backref_type CONST & br = param.m_prgbackrefs[0];
            ++cmatches;
            param.m_imatchbegin = br.second;

            param.m_no0len = (br.first == br.second);
        }

        return cmatches;
    }

    template< typename CharT, typename TraitsT, typename AllocT >
    static size_t _do_split
    (
        rpattern_type CONST & pat,
        basic_split_results<CharT, TraitsT, AllocT> & results,
        IterT ibegin,
        IterT iend,
        int limit,
        bool use_null
   )
    {
        typedef typename basic_split_results<CharT, TraitsT, AllocT>::string_type   string_type;
        typedef typename rebind<AllocT, backref_type>::type                         backref_allocator;

        std::vector<backref_type,backref_allocator> rgbackrefs(
            convert_allocator<backref_type>(results.strings().get_allocator(), 0));
            
        typedef typename rebind<AllocT, CharT>::type                                char_allocator_type;
        char_allocator_type char_allocator = 
            convert_allocator<CharT>(results.strings().get_allocator(), 0);

        // reserve some initial space
        results.strings().clear();
        results.strings().reserve(10);

        match_param<IterT> param(ibegin, ibegin, iend, 0, 0);

        while(1 != limit && _do_try_match(pat, param, rgbackrefs, use_null))
        {
            backref_type CONST & br = param.m_prgbackrefs[0];
            param.m_no0len = (br.first == br.second);

            // discard zero-width matches at the beginning and end of the buffer
            if(param.m_no0len)
            {
                // if we're at the beginning, skip
                if(br.first == param.m_ibufferbegin)
                    continue;

                // if we're at the end, break
                if(use_null ? 0 == *param.m_imatchbegin : param.m_imatchbegin == param.m_iend)
                    break;
            }

            string_type tmp(param.m_imatchbegin, br.first, char_allocator);
            results.strings().push_back(tmp);
            param.m_imatchbegin = br.second;

            // add any groups
            for(size_t i = 1; i < rgbackrefs.size(); ++i)
            {
                backref_type CONST & br = rgbackrefs[i];
                string_type tmp(br.first, br.second, char_allocator);
                results.strings().push_back(tmp);
            }

            if(limit > 0)
                --limit;
        }

        // append the last string, unless it's empty and limit is 0
        if(use_null)
        {
            if(*param.m_imatchbegin || 0 != limit)
                results.strings().push_back(string_type(&*param.m_imatchbegin, char_allocator));
        }
        else
        {
            if(param.m_imatchbegin != param.m_iend || 0 != limit)
                results.strings().push_back(string_type(param.m_imatchbegin, param.m_iend, char_allocator));
        }

        // remove trailing empty fields
        if(0 == limit)
        {
            while(results.size() && results.back().empty())
            {
                results.strings().pop_back();
            }
        }

        return results.size();
    }

    template< typename CharT, typename TraitsT, typename AllocT >
    static size_t _do_subst_internal
    (
        std::basic_string<CharT, TraitsT, AllocT> & str,
        basic_subst_results<CharT, TraitsT, AllocT> CONST & results,
        rpattern_type CONST & pat,
        size_type strpos,
        size_type strlen
   )
    {
        typedef subst_list_type::const_iterator iter_type;
        enum { UPPER = -1, NIL, LOWER } next = NIL, rest = NIL;
        bool first = true;
        size_t old_strpos = strpos;
        typename std::basic_string<CharT, TraitsT, AllocT>::iterator itstrlen = str.begin();
        std::advance(itstrlen, strpos + strlen);
        std::basic_string<char_type> CONST & subst = pat.get_subst();

        for(iter_type isubst = pat.m_subst_list.begin(); pat.m_subst_list.end() != isubst; ++isubst)
        {
            size_t sublen = 0;
            typename std::basic_string<CharT, TraitsT, AllocT>::const_iterator itsubpos1; // iter into str
            typename std::basic_string<CharT, TraitsT, AllocT>::const_iterator itsublen1;
            typename std::basic_string<char_type>::const_iterator              itsubpos2; // iter into subst string
            typename std::basic_string<char_type>::const_iterator              itsublen2;
            typename std::basic_string<CharT, TraitsT, AllocT>::iterator       itstrpos = str.begin();
            std::advance(itstrpos, strpos);

            switch(isubst->m_stype)
            {
            case subst_node::SUBST_STRING:
                itsubpos2 = subst.begin();
                std::advance(itsubpos2, isubst->m_subst_string.m_rstart);
                itsublen2 = itsubpos2;
                std::advance(itsublen2, isubst->m_subst_string.m_rlength);

                if(first)
                    str.replace(itstrpos, itstrlen, itsubpos2, itsublen2);
                else
                    str.insert(itstrpos, itsubpos2, itsublen2);
                sublen = std::distance(itsubpos2, itsublen2);
                break;

            case subst_node::SUBST_BACKREF:
                switch(isubst->m_subst_backref)
                {
                case subst_node::PREMATCH:
                    itsubpos1 = results.backref_str().begin();
                    itsublen1 = itsubpos1;
                    std::advance(itsublen1, sublen = results.rstart());
                    break;
                case subst_node::POSTMATCH:
                    itsubpos1 = results.backref_str().begin();
                    std::advance(itsubpos1, results.rstart() + results.rlength());
                    itsublen1 = results.backref_str().end();
                    break;
                default:
                    itsubpos1 = results.backref_str().begin();
                    std::advance(itsubpos1, results.rstart(isubst->m_subst_backref));
                    itsublen1 = itsubpos1;
                    std::advance(itsublen1, results.rlength(isubst->m_subst_backref));
                    break;
                }

                if(first)
                    str.replace(itstrpos, itstrlen, itsubpos1, itsublen1);
                else
                    str.insert(itstrpos, itsubpos1, itsublen1);
                sublen = std::distance(itsubpos1, itsublen1);
                break;

            case subst_node::SUBST_OP:
                switch(isubst->m_op)
                {
                case subst_node::UPPER_ON:
                    rest = UPPER;
                    break;
                case subst_node::UPPER_NEXT:
                    next = UPPER;
                    break;
                case subst_node::LOWER_ON:
                    rest = LOWER;
                    break;
                case subst_node::LOWER_NEXT:
                    next = LOWER;
                    break;
                case subst_node::ALL_OFF:
                    rest = NIL;
                    break;
                default:
                    REGEX_ASSERT(false);
                    break;
                }
                continue; // jump to the next item in the list

            default:
                REGEX_ASSERT(false);
                break;
            }

            first = false;

            // Are we upper- or lower-casing this string?
            if(rest)
            {
                typename std::basic_string<CharT, TraitsT, AllocT>::iterator ibegin = str.begin();
                std::advance(ibegin, strpos);
                typename std::basic_string<CharT, TraitsT, AllocT>::const_iterator iend = ibegin;
                std::advance(iend, sublen);
                switch(rest)
                {
                case UPPER:
                    regex_toupper(ibegin, iend);
                    break;
                case LOWER:
                    regex_tolower(ibegin, iend);
                    break;
                default:
                    REGEX_ASSERT(false);
                    break;
                }
            }

            // Are we upper- or lower-casing the next character?
            if(next)
            {
                switch(next)
                {
                case UPPER:
                    traits_type::assign(str[strpos], regex_toupper(str[strpos]));
                    break;
                case LOWER:
                    traits_type::assign(str[strpos], regex_tolower(str[strpos]));
                    break;
                default:
                    REGEX_ASSERT(false);
                    break;
                }
                next = NIL;
            }

            strpos += sublen;
        }

        // If *first* is still true, then we never called str.replace, and the substitution
        // string is empty. Erase the part of the string that the pattern matched.
        if(first)
            str.erase(strpos, strlen);

        // return length of the substitution
        return strpos - old_strpos;
    }

    template< typename CharT, typename TraitsT, typename AllocT >
    static size_t _do_subst
    (
        rpattern_type CONST & pat,
        std::basic_string<CharT, TraitsT, AllocT> & str,
        basic_subst_results<CharT, TraitsT, AllocT> & results,
        size_type pos,
        size_type len
   )
    {
        typedef std::basic_string<CharT, TraitsT, AllocT> string_type;
        typedef typename basic_subst_results<CharT, TraitsT, AllocT>::backref_vector backref_vector;

        results.m_pbackref_str = pat._save_backrefs() ? &(results.m_backref_str = str) : &str;
        results.m_ibegin = results.m_pbackref_str->begin();

        size_t csubst = 0;
        size_type stop_offset = results.m_pbackref_str->size();
        if(len != rpattern_type::npos)
            stop_offset = regex_min(size_t(pos + len), stop_offset);

        match_param<IterT> param(results.m_ibegin, results.m_ibegin, results.m_ibegin, 0, 0);

        std::advance(param.m_imatchbegin, pos);
        std::advance(param.m_iend, stop_offset);
        param.m_ibufferbegin = param.m_imatchbegin;

        if(GLOBAL & pat.flags())
        {
            bool CONST fAll   = (ALLBACKREFS   == (ALLBACKREFS   & pat.flags()));
            bool CONST fFirst = (FIRSTBACKREFS == (FIRSTBACKREFS & pat.flags()));
            backref_vector rgtempbackrefs(results.m_rgbackrefs.get_allocator()); // temporary vector used if fsave_backrefs

            size_type pos_offset = 0; // keep track of how much the backref_str and
                                      // the current string are out of sync

            while(_do_try_match(pat, param, results.m_rgbackrefs, false))
            {
                backref_type CONST & br = param.m_prgbackrefs[0];
                ++csubst;
                size_type match_length = std::distance(br.first, br.second);
                pos = std::distance(results.m_ibegin, br.first);
                size_type subst_length = _do_subst_internal(str, results, pat, pos + pos_offset, match_length);

                if(pat._save_backrefs())
                {
                    pos += match_length;
                    pos_offset += (subst_length - match_length);

                    // Handle specially the backref flags
                    if(fFirst)
                    {
                        rgtempbackrefs.push_back(br);
                    }
                    else if(fAll)
                    {
                        rgtempbackrefs.insert(
                            rgtempbackrefs.end(),
                            results.m_rgbackrefs.begin(),
                            results.m_rgbackrefs.end());
                    }
                    else
                    {
                        rgtempbackrefs.swap(results.m_rgbackrefs);
                    }
                }
                else
                {
                    pos += subst_length;
                    stop_offset += (subst_length - match_length);
                    results.m_ibegin = results.m_pbackref_str->begin();

                    // we're not saving backref information, so we don't
                    // need to do any special backref maintenance here
                }

                // prevent a pattern that matches 0 characters from matching
                // again at the same point in the string
                param.m_no0len = (0 == match_length);

                param.m_imatchbegin = results.m_ibegin;
                std::advance(param.m_imatchbegin, pos); // ineffecient for bidirectional iterators.

                param.m_iend = results.m_ibegin;
                std::advance(param.m_iend, stop_offset); // ineffecient for bidirectional iterators.
            }

            // If we did special backref handling, swap the backref vectors
            if(pat._save_backrefs())
            {
                results.m_rgbackrefs.swap(rgtempbackrefs);
            }
            else if(! results.m_rgbackrefs[0].matched)
            {
                results.m_rgbackrefs.clear();
            }
        }
        else if(_do_try_match(pat, param, results.m_rgbackrefs, false))
        {
            backref_type CONST & br = param.m_prgbackrefs[0];
            ++csubst;
            _do_subst_internal(
                str, results, pat,
                std::distance(results.m_ibegin, br.first),
                std::distance(br.first, br.second));
            results.m_ibegin = results.m_pbackref_str->begin();
        }

        if(NOBACKREFS == (pat.flags() & NOBACKREFS))
        {
            results.m_rgbackrefs.clear();
        }

        return csubst;
    }

    static instantiator instantiate()
    {
        return instantiator_helper
        (
            &regex_access::_do_match_iterative_helper_s,
            &regex_access::_do_match_iterative_helper_c,
            &regex_access::_do_match_recursive_s,
            &regex_access::_do_match_recursive_c,
            &regex_access::_do_match_with_stack,
            &regex_access::_do_match_impl
       );
    }
};


//
// Some helper functions needed by process_escapes
//
template< typename CharT >
inline bool regex_isxdigit(CharT ch)
{
    return (REGEX_CHAR(CharT,'0') <= ch && REGEX_CHAR(CharT,'9') >= ch)
        || (REGEX_CHAR(CharT,'a') <= ch && REGEX_CHAR(CharT,'f') >= ch)
        || (REGEX_CHAR(CharT,'A') <= ch && REGEX_CHAR(CharT,'F') >= ch);
}

template< typename CharT >
inline int regex_xdigit2int(CharT ch)
{
    if(REGEX_CHAR(CharT,'a') <= ch && REGEX_CHAR(CharT,'f') >= ch)
        return ch - REGEX_CHAR(CharT,'a') + 10;
    if(REGEX_CHAR(CharT,'A') <= ch && REGEX_CHAR(CharT,'F') >= ch)
        return ch - REGEX_CHAR(CharT,'A') + 10;
    return ch - REGEX_CHAR(CharT,'0');
}

} // namespace detail

// --------------------------------------------------------------------------
//
// Function:    process_escapes
//
// Description: Turn the escape sequnces \f \n \r \t \v \\ into their
//              ASCII character equivalents. Also, optionally process
//              perl escape sequences.
//
// Returns:     VOID
//
// Arguments:   str      - the string to process
//              fPattern - true if the string is to be processed as a regex
//
// Notes:       When fPattern is true, the perl escape sequences are not
//              processed.  If there is an octal or hex excape sequence, we
//              don't want to turn it into a regex metacharacter here.  We
//              leave it unescaped so the regex parser correctly interprests
//              it as a character literal.
//
// History:     8/1/2001 - ericne - Created
//
// --------------------------------------------------------------------------
template< typename CharT, typename TraitsT, typename AllocT >
inline VOID process_escapes(std::basic_string<CharT, TraitsT, AllocT> & str, bool fPattern) //throw()
{
    typedef typename std::basic_string<CharT, TraitsT, AllocT>::size_type size_type;

    size_type i = 0;
    size_type CONST npos = std::basic_string<CharT, TraitsT, AllocT>::npos;

    if(str.empty())
        return;

    while(npos != (i = str.find(REGEX_CHAR(CharT,'\\'), i)))
    {
        if(str.size() - 1 == i)
            return;

        switch(str[i+1])
        {
        case REGEX_CHAR(CharT,'a'):
            str.replace(i, 2, 1, REGEX_CHAR(CharT,'\a'));
            break;
        case REGEX_CHAR(CharT,'b'):
            if(! fPattern)
                str.replace(i, 2, 1, REGEX_CHAR(CharT,'\b'));
            else
                ++i;
            break;
        case REGEX_CHAR(CharT,'e'):
            str.replace(i, 2, 1, CharT(27));
            break;
        case REGEX_CHAR(CharT,'f'):
            str.replace(i, 2, 1, REGEX_CHAR(CharT,'\f'));
            break;
        case REGEX_CHAR(CharT,'n'):
            str.replace(i, 2, 1, REGEX_CHAR(CharT,'\n'));
            break;
        case REGEX_CHAR(CharT,'r'):
            str.replace(i, 2, 1, REGEX_CHAR(CharT,'\r'));
            break;
        case REGEX_CHAR(CharT,'t'):
            str.replace(i, 2, 1, REGEX_CHAR(CharT,'\t'));
            break;
        case REGEX_CHAR(CharT,'v'):
            str.replace(i, 2, 1, REGEX_CHAR(CharT,'\v'));
            break;
        case REGEX_CHAR(CharT,'\\'):
            if(fPattern)
            {
                if(i+3 < str.size() && REGEX_CHAR(CharT,'\\') == str[i+2] && REGEX_CHAR(CharT,'\\') == str[i+3])
                    str.erase(i, 2);
                ++i;
            }
            else
                str.erase(i, 1);
            break;
        case REGEX_CHAR(CharT,'0'): case REGEX_CHAR(CharT,'1'): case REGEX_CHAR(CharT,'2'): case REGEX_CHAR(CharT,'3'):
        case REGEX_CHAR(CharT,'4'): case REGEX_CHAR(CharT,'5'): case REGEX_CHAR(CharT,'6'): case REGEX_CHAR(CharT,'7'):
            if(! fPattern)
            {
                size_t j=i+2;
                CharT ch = CharT(str[i+1] - REGEX_CHAR(CharT,'0'));
                for(; j-i < 4 && j < str.size() && REGEX_CHAR(CharT,'0') <= str[j] && REGEX_CHAR(CharT,'7') >= str[j]; ++j)
                    ch = CharT(ch * 8 + (str[j] - REGEX_CHAR(CharT,'0')));
                str.replace(i, j-i, 1, ch);
            }
            break;
        case REGEX_CHAR(CharT,'x'):
            if(! fPattern)
            {
                CharT ch = 0;
                size_t j=i+2;
                for(; j-i < 4 && j < str.size() && detail::regex_isxdigit(str[j]); ++j)
                    ch = CharT(ch * 16 + detail::regex_xdigit2int(str[j]));
                str.replace(i, j-i, 1, ch);
            }
            break;
        case REGEX_CHAR(CharT,'c'):
            if(! fPattern && i+2 < str.size())
            {
                CharT ch = str[i+2];
                if(REGEX_CHAR(CharT,'a') <= ch && REGEX_CHAR(CharT,'z') >= ch)
                    ch = detail::regex_toupper(ch);
                str.replace(i, 3, 1, CharT(ch ^ 0x40));
            }
            break;
        default:
            if(fPattern)
                ++i;
            else
                str.erase(i, 1);
            break;
        }
        ++i;
        if(str.size() <= i)
            return;
    }
}

#endif
