//+---------------------------------------------------------------------------
//
//  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;