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;
                }