///////////////////////////////////////////////////////////////////////////////
/// \file match_results.hpp
/// Contains the definition of the match_results type and associated helpers.
/// The match_results type holds the results of a regex_match() or
/// regex_search() operation.
//
//  Copyright 2007 Eric Niebler. Distributed under the Boost
//  Software License, Version 1.0. (See accompanying file
//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
// Acknowledgements: Thanks to Markus Sch\:opflin for helping to track down
// a tricky formatting bug on HP Tru64, and to Steven Watanabe for suggesting
// the fix.

#ifndef BOOST_XPRESSIVE_MATCH_RESULTS_HPP_EAN_10_04_2005
#define BOOST_XPRESSIVE_MATCH_RESULTS_HPP_EAN_10_04_2005

// MS compatible compilers support #pragma once
#if defined(_MSC_VER) && (_MSC_VER >= 1020)
# pragma once
#endif

#include <map>
#include <vector>
#include <utility>
#include <iterator>
#include <typeinfo>
#include <algorithm>
#include <boost/config.hpp>
#include <boost/assert.hpp>
#include <boost/integer.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/intrusive_ptr.hpp>
#include <boost/throw_exception.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/numeric/conversion/converter.hpp>
#if BOOST_ITERATOR_ADAPTORS_VERSION >= 0x0200
# include <boost/iterator/filter_iterator.hpp>
#endif
#include <boost/xpressive/regex_constants.hpp>
#include <boost/xpressive/detail/detail_fwd.hpp>
#include <boost/xpressive/detail/core/regex_impl.hpp>
#include <boost/xpressive/detail/core/sub_match_vector.hpp>
#include <boost/xpressive/detail/utility/sequence_stack.hpp>
#include <boost/xpressive/detail/core/results_cache.hpp>
#include <boost/xpressive/detail/utility/literals.hpp>
#include <boost/xpressive/detail/utility/algorithm.hpp>
#include <boost/xpressive/detail/utility/counted_base.hpp>

namespace boost { namespace xpressive { namespace detail
{

///////////////////////////////////////////////////////////////////////////////
// type_info_less
//
struct type_info_less
{
    bool operator()(std::type_info const *left, std::type_info const *right) const
    {
        return 0 != left->before(*right);
    }
};

///////////////////////////////////////////////////////////////////////////////
// ActionArgBinding
//
struct ActionArgBinding
  : proto::assign<proto::terminal<action_arg<proto::_, proto::_> >, proto::terminal<proto::_> >
{
};

///////////////////////////////////////////////////////////////////////////////
// results_extras
//
template<typename BidiIter>
struct results_extras
  : counted_base<results_extras<BidiIter> >
{
    sequence_stack<sub_match_impl<BidiIter> > sub_match_stack_;
    results_cache<BidiIter> results_cache_;
};

///////////////////////////////////////////////////////////////////////////////
// char_overflow_handler_
//
struct char_overflow_handler_
{
    void operator ()(numeric::range_check_result result) const // throw(regex_error)
    {
        if(numeric::cInRange != result)
        {
            boost::throw_exception(
                regex_error(
                    regex_constants::error_escape
                  , "character escape too large to fit in target character type"
                )
            );
        }
    }
};

///////////////////////////////////////////////////////////////////////////////
// transform_op enum
//
enum transform_op { None = 0, Upper = 1, Lower = 2 };
enum transform_scope { Next = 0, Rest = 1 };

///////////////////////////////////////////////////////////////////////////////
// case_converting_iterator
//
template<typename OutputIterator, typename Char>
struct case_converting_iterator
  : std::iterator<std::output_iterator_tag, Char, void, void, case_converting_iterator<OutputIterator, Char> >
{
    case_converting_iterator(OutputIterator const &out, traits<Char> const *traits)
      : out_(out)
      , traits_(traits)
      , next_(None)
      , rest_(None)
    {}

    OutputIterator base() const
    {
        return this->out_;
    }

    case_converting_iterator &operator ++()
    {
        ++this->out_;
        this->next_ = None;
        return *this;
    }

    case_converting_iterator operator ++(int)
    {
        case_converting_iterator tmp(*this);
        ++*this;
        return tmp;
    }

    case_converting_iterator &operator *()
    {
        return *this;
    }

    friend bool set_transform(case_converting_iterator &iter, transform_op trans, transform_scope scope)
    {
        BOOST_ASSERT(scope == Next || scope == Rest);
        if(scope == Next)
            iter.next_ = trans;
        else
            iter.rest_ = trans;
        return true;
    }

    case_converting_iterator &operator =(Char ch)
    {
        switch(this->next_ ? this->next_ : this->rest_)
        {
        case Lower:
            ch = this->traits_->tolower(ch);
            break;

        case Upper:
            ch = this->traits_->toupper(ch);
            break;

        default:;
        }

        *this->out_ = ch;
        return *this;
    }

private:
    OutputIterator out_;
    traits<Char> const *traits_;
    transform_op next_, rest_;
};

template<typename Iterator>
inline bool set_transform(Iterator &, transform_op, transform_scope)
{
    return false;
}

///////////////////////////////////////////////////////////////////////////////
// noop_output_iterator
//
template<typename Char>
struct noop_output_iterator
  : std::iterator<std::output_iterator_tag, Char, void, void, noop_output_iterator<Char> >
{
    noop_output_iterator &operator ++()
    {
        return *this;
    }

    noop_output_iterator &operator ++(int)
    {
        return *this;
    }

    noop_output_iterator &operator *()
    {
        return *this;
    }

    noop_output_iterator &operator =(Char const &)
    {
        return *this;
    }
};

} // detail

///////////////////////////////////////////////////////////////////////////////
// match_results
/// \brief Class template match_results\<\> holds the results of a regex_match() or a
/// regex_search() as a collection of sub_match objects.
///
/// Class template match_results\<\> denotes a collection of sequences representing the result of
/// a regular expression match. Storage for the collection is allocated and freed as necessary by
/// the member functions of class match_results\<\>.
///
/// The class template match_results\<\> conforms to the requirements of a Sequence, as specified
/// in (lib.sequence.reqmts), except that only operations defined for const-qualified Sequences are
/// supported.
template<typename BidiIter>
struct match_results
{
private:
    /// INTERNAL ONLY
    ///
    struct dummy { int i_; };
    typedef int dummy::*bool_type;

public:
    typedef typename iterator_value<BidiIter>::type char_type;
    typedef typename detail::string_type<char_type>::type string_type;
    typedef std::size_t size_type;
    typedef sub_match<BidiIter> value_type;
    typedef typename iterator_difference<BidiIter>::type difference_type;
    typedef value_type const &reference;
    typedef value_type const &const_reference;

    typedef typename detail::sub_match_vector<BidiIter>::iterator iterator;
    typedef typename detail::sub_match_vector<BidiIter>::const_iterator const_iterator;
    typedef typename detail::nested_results<BidiIter> nested_results_type;

    /// \post regex_id() == 0
    /// \post size()     == 0
    /// \post empty()    == true
    /// \post str()      == string_type()
    match_results()
      : regex_id_(0)
      , sub_matches_()
      , base_()
      , prefix_()
      , suffix_()
      , nested_results_()
      , extras_ptr_()
      , traits_()
      , args_()
      , named_marks_()
    {
    }

    /// \param that The match_results object to copy
    /// \post regex_id()  == that.regex_id().
    /// \post size()      == that.size().
    /// \post empty()     == that.empty().
    /// \post str(n)      == that.str(n) for all positive integers n \< that.size().
    /// \post prefix()    == that.prefix().
    /// \post suffix()    == that.suffix().
    /// \post (*this)[n]  == that[n] for all positive integers n \< that.size().
    /// \post length(n)   == that.length(n) for all positive integers n \< that.size().
    /// \post position(n) == that.position(n) for all positive integers n \< that.size().
    match_results(match_results<BidiIter> const &that)
      : regex_id_(that.regex_id_)
      , sub_matches_()
      , base_()
      , prefix_()
      , suffix_()
      , nested_results_()
      , extras_ptr_()
      , traits_()
      , args_(that.args_)
      , named_marks_(that.named_marks_)
    {
        if(that)
        {
            extras_type &extras = this->get_extras_();
            std::size_t size = that.sub_matches_.size();
            detail::sub_match_impl<BidiIter> *sub_matches = extras.sub_match_stack_.push_sequence(size);
            detail::core_access<BidiIter>::init_sub_match_vector(this->sub_matches_, sub_matches, size, that.sub_matches_);

            // BUGBUG this doesn't share the extras::sequence_stack
            this->nested_results_ = that.nested_results_;
            this->prefix_ = that.prefix_;
            this->suffix_ = that.suffix_;
            this->base_ = that.base_;
            this->traits_ = that.traits_;
        }
    }

    ~match_results()
    {
    }

    /// \param that The match_results object to copy.
    /// \post regex_id()  == that.regex_id().
    /// \post size()      == that.size().
    /// \post empty()     == that.empty().
    /// \post str(n)      == that.str(n) for all positive integers n \< that.size().
    /// \post prefix()    == that.prefix().
    /// \post suffix()    == that.suffix().
    /// \post (*this)[n]  == that[n] for all positive integers n \< that.size().
    /// \post length(n)   == that.length(n) for all positive integers n \< that.size().
    /// \post position(n) == that.position(n) for all positive integers n \< that.size().
    match_results<BidiIter> &operator =(match_results<BidiIter> const &that)
    {
        match_results<BidiIter>(that).swap(*this);
        return *this;
    }

    /// Returns one plus the number of marked sub-expressions in the regular 
    /// expression that was matched if *this represents the result of a 
    /// successful match. Otherwise returns 0.
    size_type size() const
    {
        return this->sub_matches_.size();
    }

    /// Returns size() == 0.
    ///
    bool empty() const
    {
        return 0 == this->size();
    }

    /// Returns (*this)[sub].length().
    ///
    difference_type length(size_type sub = 0) const
    {
        return this->sub_matches_[ sub ].length();
    }

    /// If !(*this)[sub].matched then returns -1. Otherwise returns std::distance(base, (*this)[sub].first),
    /// where base is the start iterator of the sequence that was searched. [Note - unless this is part
    /// of a repeated search with a regex_iterator then base is the same as prefix().first - end note]
    difference_type position(size_type sub = 0) const
    {
        return this->sub_matches_[ sub ].matched ? std::distance(this->base_, this->sub_matches_[ sub ].first) : -1;
    }

    /// Returns (*this)[sub].str().
    ///
    string_type str(size_type sub = 0) const
    {
        return this->sub_matches_[ sub ].str();
    }

    /// Returns a reference to the sub_match object representing the sequence that
    /// matched marked sub-expression sub. If sub == 0 then returns a reference to
    /// a sub_match object representing the sequence that matched the whole regular
    /// expression. If sub >= size() then returns a sub_match object representing an
    /// unmatched sub-expression.
    template<typename Sub>
    const_reference operator [](Sub const &sub) const
    {
        return this->at_(sub);
    }

    /// Returns a reference to the sub_match object representing the character sequence from
    /// the start of the string being matched/searched, to the start of the match found.
    ///
    const_reference prefix() const
    {
        return this->prefix_;
    }

    /// Returns a reference to the sub_match object representing the character sequence from
    /// the end of the match found to the end of the string being matched/searched.
    ///
    const_reference suffix() const
    {
        return this->suffix_;
    }

    /// Returns a starting iterator that enumerates over all the marked sub-expression matches
    /// stored in *this.
    ///
    const_iterator begin() const
    {
        return this->sub_matches_.begin();
    }

    /// Returns a terminating iterator that enumerates over all the marked sub-expression
    /// matches stored in *this.
    ///
    const_iterator end() const
    {
        return this->sub_matches_.end();
    }

    /// Returns a true value if (*this)[0].matched, else returns a false value.
    ///
    operator bool_type() const
    {
        return this->sub_matches_[ 0 ].matched ? &dummy::i_ : 0;
    }

    /// Returns true if empty() || !(*this)[0].matched, else returns false.
    ///
    bool operator !() const
    {
        return this->empty() || !this->sub_matches_[ 0 ].matched;
    }

    /// Returns the id of the basic_regex object most recently used with this match_results object.
    ///
    regex_id_type regex_id() const
    {
        return this->regex_id_;
    }

    /// Returns a Sequence of nested match_results elements.
    ///
    nested_results_type const &nested_results() const
    {
        return this->nested_results_;
    }

    /// Copies the character sequence [fmt.begin(), fmt.end()) to OutputIterator out. For each format
    /// specifier or escape sequence in fmt, replace that sequence with either the character(s) it
    /// represents, or the sequence within *this to which it refers. The bitmasks specified in flags
    /// determines what format specifiers or escape sequences are recognized, by default this is the
    /// format used by ECMA-262, ECMAScript Language Specification, Chapter 15 part 5.4.11 String.prototype.replace.
    template<typename OutputIterator>
    OutputIterator format
    (
        OutputIterator out
      , const string_type &fmt
      , regex_constants::match_flag_type flags = regex_constants::format_default
    ) const
    {
        typename string_type::const_iterator cur = fmt.begin(), end = fmt.end();

        if(0 != (regex_constants::format_literal & flags))
        {
            return std::copy(cur, end, out);
        }
        else if(0 != (regex_constants::format_perl & flags))
        {
            return this->format_perl_(cur, end, out);
        }
        else if(0 != (regex_constants::format_sed & flags))
        {
            return this->format_sed_(cur, end, out);
        }
        else if(0 != (regex_constants::format_all & flags))
        {
            return this->format_all_(cur, end, out);
        }

        return this->format_ecma_262_(cur, end, out);
    }

    /// Returns a copy of the string fmt. For each format specifier or escape sequence in fmt,
    /// replace that sequence with either the character(s) it represents, or the sequence within
    /// *this to which it refers. The bitmasks specified in flags determines what format specifiers
    /// or escape sequences are recognized, by default this is the format used by ECMA-262,
    /// ECMAScript Language Specification, Chapter 15 part 5.4.11 String.prototype.replace.
    string_type format(string_type const &fmt, regex_constants::match_flag_type flags = regex_constants::format_default) const
    {
        string_type result;
        result.reserve(fmt.length() * 2);
        this->format(std::back_inserter(result), fmt, flags);
        return result;
    }

    /// Swaps the contents of two match_results objects. Guaranteed not to throw.
    /// \param that The match_results object to swap with.
    /// \post *this contains the sequence of matched sub-expressions that were in that,
    /// that contains the sequence of matched sub-expressions that were in *this.
    /// \throw nothrow
    void swap(match_results<BidiIter> &that) // throw()
    {
        std::swap(this->regex_id_, that.regex_id_);
        this->sub_matches_.swap(that.sub_matches_);
        std::swap(this->base_, that.base_);
        std::swap(this->prefix_, that.prefix_);
        std::swap(this->suffix_, that.suffix_);
        this->nested_results_.swap(that.nested_results_);
        this->extras_ptr_.swap(that.extras_ptr_);
        this->traits_.swap(that.traits_);
        this->args_.swap(that.args_);
    }

    /// TODO document me
    ///
    template<typename Arg>
    match_results<BidiIter> &let(Arg const &arg)
    {
        typedef typename proto::result_of::left<Arg>::type left_type;
        typedef typename proto::result_of::right<Arg>::type right_type;
        typedef typename proto::result_of::arg<left_type>::type arg_left_type;
        typedef typename proto::result_of::arg<right_type>::type arg_right_type;
        BOOST_MPL_ASSERT((proto::matches<Arg, detail::ActionArgBinding>));
        BOOST_MPL_ASSERT((is_same<typename arg_left_type::type, arg_right_type>));
        this->args_[&typeid(proto::arg(proto::left(arg)))] = &proto::arg(proto::right(arg));
        return *this;
    }

    /// INTERNAL ONLY
    ///
    match_results<BidiIter> const &operator ()(regex_id_type regex_id, size_type index = 0) const
    {
        // BUGBUG this is linear, make it O(1)
        static match_results<BidiIter> const s_null;

        regex_id_filter_predicate<BidiIter> pred(regex_id);
        typename nested_results_type::const_iterator
            begin = this->nested_results_.begin()
          , end = this->nested_results_.end()
          , cur = detail::find_nth_if(begin, end, index, pred);

        return (cur == end) ? s_null : *cur;
    }

    /// INTERNAL ONLY
    ///
    match_results<BidiIter> const &operator ()(basic_regex<BidiIter> const &rex, std::size_t index = 0) const
    {
        return (*this)(rex.regex_id(), index);
    }

private:

    friend struct detail::core_access<BidiIter>;
    typedef detail::results_extras<BidiIter> extras_type;

    /// INTERNAL ONLY
    ///
    void init_
    (
        regex_id_type regex_id
      , intrusive_ptr<detail::traits<char_type> const> const &traits
      , detail::sub_match_impl<BidiIter> *sub_matches
      , size_type size
      , std::vector<detail::named_mark<char_type> > const &named_marks
    )
    {
        this->traits_ = traits;
        this->regex_id_ = regex_id;
        this->named_marks_ = named_marks;
        detail::core_access<BidiIter>::init_sub_match_vector(this->sub_matches_, sub_matches, size);
    }

    /// INTERNAL ONLY
    ///
    extras_type &get_extras_()
    {
        if(!this->extras_ptr_)
        {
            this->extras_ptr_ = new extras_type;
        }

        return *this->extras_ptr_;
    }

    /// INTERNAL ONLY
    ///
    void set_prefix_suffix_(BidiIter begin, BidiIter end)
    {
        this->base_ = begin;

        this->prefix_.first = begin;
        this->prefix_.second = this->sub_matches_[ 0 ].first;
        this->prefix_.matched = this->prefix_.first != this->prefix_.second;

        this->suffix_.first = this->sub_matches_[ 0 ].second;
        this->suffix_.second = end;
        this->suffix_.matched = this->suffix_.first != this->suffix_.second;

        typename nested_results_type::iterator ibegin = this->nested_results_.begin();
        typename nested_results_type::iterator iend = this->nested_results_.end();
        for( ; ibegin != iend; ++ibegin )
        {
            ibegin->set_prefix_suffix_(begin, end);
        }
    }

    /// INTERNAL ONLY
    ///
    void reset_()
    {
        detail::core_access<BidiIter>::init_sub_match_vector(this->sub_matches_, 0, 0);
    }

    /// INTERNAL ONLY
    ///
    void set_base_(BidiIter base)
    {
        this->base_ = base;

        typename nested_results_type::iterator ibegin = this->nested_results_.begin();
        typename nested_results_type::iterator iend = this->nested_results_.end();
        for( ; ibegin != iend; ++ibegin )
        {
            ibegin->set_base_(base);
        }
    }

    /// INTERNAL ONLY
    ///
    const_reference at_(size_type sub) const
    {
        return this->sub_matches_[ sub ];
    }

    /// INTERNAL ONLY
    ///
    const_reference at_(detail::basic_mark_tag const &mark) const
    {
        return this->sub_matches_[ detail::get_mark_number(mark) ];
    }

    /// INTERNAL ONLY
    ///
    const_reference at_(char_type const *name) const
    {
        for(std::size_t i = 0; i < this->named_marks_.size(); ++i)
        {
            if(this->named_marks_[i].name_ == name)
            {
                return this->sub_matches_[ this->named_marks_[i].mark_nbr_ ];
            }
        }
        boost::throw_exception(
            regex_error(regex_constants::error_badmark, "invalid named back-reference")
        );
        // Should never execute, but if it does, this returns
        // a "null" sub_match.
        return this->sub_matches_[this->sub_matches_.size()];
    }

    /// INTERNAL ONLY
    ///
    const_reference at_(string_type const &name) const
    {
        return (*this)[name.c_str()];
    }

    /// INTERNAL ONLY
    ///
    template<typename ForwardIterator, typename OutputIterator>
    OutputIterator format_ecma_262_(ForwardIterator cur, ForwardIterator end, OutputIterator out) const
    {
        while(cur != end)
        {
            switch(*cur)
            {
            case BOOST_XPR_CHAR_(char_type, '$'):
                out = this->format_backref_(++cur, end, out);
                break;

            default:
                *out++ = *cur++;
                break;
            }
        }

        return out;
    }

    /// INTERNAL ONLY
    ///
    template<typename ForwardIterator, typename OutputIterator>
    OutputIterator format_sed_(ForwardIterator cur, ForwardIterator end, OutputIterator out) const
    {
        while(cur != end)
        {
            switch(*cur)
            {
            case BOOST_XPR_CHAR_(char_type, '&'):
                ++cur;
                out = std::copy(this->sub_matches_[ 0 ].first, this->sub_matches_[ 0 ].second, out);
                break;

            case BOOST_XPR_CHAR_(char_type, '\\'):
                out = this->format_escape_(++cur, end, out);
                break;

            default:
                *out++ = *cur++;
                break;
            }
        }

        return out;
    }

    /// INTERNAL ONLY
    ///
    template<typename ForwardIterator, typename OutputIterator>
    OutputIterator format_perl_(ForwardIterator cur, ForwardIterator end, OutputIterator out) const
    {
        detail::case_converting_iterator<OutputIterator, char_type> iout(out, this->traits_.get());

        while(cur != end)
        {
            switch(*cur)
            {
            case BOOST_XPR_CHAR_(char_type, '$'):
                iout = this->format_backref_(++cur, end, iout);
                break;

            case BOOST_XPR_CHAR_(char_type, '\\'):
                if(++cur != end && BOOST_XPR_CHAR_(char_type, 'g') == *cur)
                {
                    iout = this->format_named_backref_(++cur, end, iout);
                }
                else
                {
                    iout = this->format_escape_(cur, end, iout);
                }
                break;

            default:
                *iout++ = *cur++;
                break;
            }
        }

        return iout.base();
    }

    /// INTERNAL ONLY
    ///
    template<typename ForwardIterator, typename OutputIterator>
    OutputIterator format_all_(ForwardIterator cur, ForwardIterator end, OutputIterator out) const
    {
        detail::case_converting_iterator<OutputIterator, char_type> iout(out, this->traits_.get());
        iout = this->format_all_impl_(cur, end, iout);
        detail::ensure(cur == end
          , regex_constants::error_paren, "unbalanced parentheses in format string");
        return iout.base();
    }

    /// INTERNAL ONLY
    ///
    template<typename ForwardIterator, typename OutputIterator>
    OutputIterator format_all_impl_(ForwardIterator &cur, ForwardIterator end, OutputIterator out, bool metacolon = false) const
    {
        int max = 0, sub = 0;
        detail::noop_output_iterator<char_type> noop;

        while(cur != end)
        {
            switch(*cur)
            {
            case BOOST_XPR_CHAR_(char_type, '$'):
                out = this->format_backref_(++cur, end, out);
                break;

            case BOOST_XPR_CHAR_(char_type, '\\'):
                if(++cur != end && BOOST_XPR_CHAR_(char_type, 'g') == *cur)
                {
                    out = this->format_named_backref_(++cur, end, out);
                }
                else
                {
                    out = this->format_escape_(cur, end, out);
                }
                break;

            case BOOST_XPR_CHAR_(char_type, '('):
                out = this->format_all_impl_(++cur, end, out);
                detail::ensure(BOOST_XPR_CHAR_(char_type, ')') == *(cur-1)
                  , regex_constants::error_paren, "unbalanced parentheses in format string");
                break;

            case BOOST_XPR_CHAR_(char_type, '?'):
                detail::ensure(++cur != end
                  , regex_constants::error_subreg, "malformed conditional in format string");
                max = static_cast<int>(this->size() - 1);
                sub = detail::toi(cur, end, *this->traits_, 10, max);
                detail::ensure(0 != sub, regex_constants::error_subreg, "invalid back-reference");
                if(this->sub_matches_[ sub ].matched)
                {
                    out = this->format_all_impl_(cur, end, out, true);
                    if(BOOST_XPR_CHAR_(char_type, ':') == *(cur-1))
                        this->format_all_impl_(cur, end, noop);
                }
                else
                {
                    this->format_all_impl_(cur, end, noop, true);
                    if(BOOST_XPR_CHAR_(char_type, ':') == *(cur-1))
                        out = this->format_all_impl_(cur, end, out);
                }
                return out;

            case BOOST_XPR_CHAR_(char_type, ':'):
                if(metacolon)
                {
            case BOOST_XPR_CHAR_(char_type, ')'):
                    ++cur;
                    return out;
                }
                // else fall-through

            default:
                *out++ = *cur++;
                break;
            }
        }

        return out;
    }

    /// INTERNAL ONLY
    ///
    template<typename OutputIterator>
    OutputIterator format_backref_
    (
        typename string_type::const_iterator &cur
      , typename string_type::const_iterator end
      , OutputIterator out
    ) const
    {
        if(cur == end)
        {
            *out++ = BOOST_XPR_CHAR_(char_type, '$');
        }
        else if(BOOST_XPR_CHAR_(char_type, '$') == *cur)
        {
            *out++ = *cur++;
        }
        else if(BOOST_XPR_CHAR_(char_type, '&') == *cur) // whole match
        {
            ++cur;
            out = std::copy(this->sub_matches_[ 0 ].first, this->sub_matches_[ 0 ].second, out);
        }
        else if(BOOST_XPR_CHAR_(char_type, '`') == *cur) // prefix
        {
            ++cur;
            out = std::copy(this->prefix().first, this->prefix().second, out);
        }
        else if(BOOST_XPR_CHAR_(char_type, '\'') == *cur) // suffix
        {
            ++cur;
            out = std::copy(this->suffix().first, this->suffix().second, out);
        }
        else if(-1 != this->traits_->value(*cur, 10)) // a sub-match
        {
            int max = static_cast<int>(this->size() - 1);
            int sub = detail::toi(cur, end, *this->traits_, 10, max);
            detail::ensure(0 != sub, regex_constants::error_subreg, "invalid back-reference");
            if(this->sub_matches_[ sub ].matched)
                out = std::copy(this->sub_matches_[ sub ].first, this->sub_matches_[ sub ].second, out);
        }
        else
        {
            *out++ = BOOST_XPR_CHAR_(char_type, '$');
            *out++ = *cur++;
        }

        return out;
    }

    /// INTERNAL ONLY
    ///
    template<typename OutputIterator>
    OutputIterator format_escape_
    (
        typename string_type::const_iterator &cur
      , typename string_type::const_iterator end
      , OutputIterator out
    ) const
    {
        using namespace regex_constants;
        typename string_type::const_iterator tmp;
        // define an unsigned type the same size as char_type
        typedef typename boost::uint_t<CHAR_BIT * sizeof(char_type)>::least uchar_t;
        BOOST_MPL_ASSERT_RELATION(sizeof(uchar_t), ==, sizeof(char_type));
        typedef numeric::conversion_traits<uchar_t, int> converstion_traits;
        numeric::converter<int, uchar_t, converstion_traits, detail::char_overflow_handler_> converter;

        if(cur == end)
        {
            *out++ = BOOST_XPR_CHAR_(char_type, '\\');
            return out;
        }

        char_type ch = *cur++;
        switch(ch)
        {
        case BOOST_XPR_CHAR_(char_type, 'a'):
            *out++ = BOOST_XPR_CHAR_(char_type, '\a');
            break;

        case BOOST_XPR_CHAR_(char_type, 'e'):
            *out++ = converter(27);
            break;

        case BOOST_XPR_CHAR_(char_type, 'f'):
            *out++ = BOOST_XPR_CHAR_(char_type, '\f');
            break;

        case BOOST_XPR_CHAR_(char_type, 'n'):
            *out++ = BOOST_XPR_CHAR_(char_type, '\n');
            break;

        case BOOST_XPR_CHAR_(char_type, 'r'):
            *out++ = BOOST_XPR_CHAR_(char_type, '\r');
            break;

        case BOOST_XPR_CHAR_(char_type, 't'):
            *out++ = BOOST_XPR_CHAR_(char_type, '\t');
            break;

        case BOOST_XPR_CHAR_(char_type, 'v'):
            *out++ = BOOST_XPR_CHAR_(char_type, '\v');
            break;

        case BOOST_XPR_CHAR_(char_type, 'x'):
            detail::ensure(cur != end, error_escape, "unexpected end of format found");
            if(BOOST_XPR_CHAR_(char_type, '{') == *cur)
            {
                detail::ensure(++cur != end, error_escape, "unexpected end of format found");
                tmp = cur;
                *out++ = converter(detail::toi(cur, end, *this->traits_, 16, 0xffff));
                detail::ensure(4 == std::distance(tmp, cur) && cur != end && BOOST_XPR_CHAR_(char_type, '}') == *cur++
                  , error_escape, "invalid hex escape : must be \\x { HexDigit HexDigit HexDigit HexDigit }");
            }
            else
            {
                tmp = cur;
                *out++ = converter(detail::toi(cur, end, *this->traits_, 16, 0xff));
                detail::ensure(2 == std::distance(tmp, cur), error_escape
                  , "invalid hex escape : must be \\x HexDigit HexDigit");
            }
            break;

        case BOOST_XPR_CHAR_(char_type, 'c'):
            detail::ensure(cur != end, error_escape, "unexpected end of format found");
            detail::ensure
            (
                this->traits_->in_range(BOOST_XPR_CHAR_(char_type, 'a'), BOOST_XPR_CHAR_(char_type, 'z'), *cur)
             || this->traits_->in_range(BOOST_XPR_CHAR_(char_type, 'A'), BOOST_XPR_CHAR_(char_type, 'Z'), *cur)
              , error_escape
              , "invalid escape control letter; must be one of a-z or A-Z"
            );
            // Convert to character according to ECMA-262, section 15.10.2.10:
            *out++ = converter(*cur % 32);
            ++cur;
            break;

        case BOOST_XPR_CHAR_(char_type, 'l'):
            if(!set_transform(out, detail::Lower, detail::Next))
            {
                *out++ = BOOST_XPR_CHAR_(char_type, 'l');
            }
            break;

        case BOOST_XPR_CHAR_(char_type, 'L'):
            if(!set_transform(out, detail::Lower, detail::Rest))
            {
                *out++ = BOOST_XPR_CHAR_(char_type, 'L');
            }
            break;

        case BOOST_XPR_CHAR_(char_type, 'u'):
            if(!set_transform(out, detail::Upper, detail::Next))
            {
                *out++ = BOOST_XPR_CHAR_(char_type, 'u');
            }
            break;

        case BOOST_XPR_CHAR_(char_type, 'U'):
            if(!set_transform(out, detail::Upper, detail::Rest))
            {
                *out++ = BOOST_XPR_CHAR_(char_type, 'U');
            }
            break;

        case BOOST_XPR_CHAR_(char_type, 'E'):
            if(!set_transform(out, detail::None, detail::Rest))
            {
                *out++ = BOOST_XPR_CHAR_(char_type, 'E');
            }
            break;

        default:
            // BUGBUG what about backreferences like \12 ?
            if(0 < this->traits_->value(ch, 10))
            {
                int sub = this->traits_->value(ch, 10);
                if(this->sub_matches_[ sub ].matched)
                    out = std::copy(this->sub_matches_[ sub ].first, this->sub_matches_[ sub ].second, out);
            }
            else
            {
                *out++ = ch;
            }
            break;
        }

        return out;
    }

    /// INTERNAL ONLY
    ///
    template<typename OutputIterator>
    OutputIterator format_named_backref_
    (
        typename string_type::const_iterator &cur
      , typename string_type::const_iterator end
      , OutputIterator out
    ) const
    {
        using namespace regex_constants;
        detail::ensure(cur != end && BOOST_XPR_CHAR_(char_type, '<') == *cur++
            , error_badmark, "invalid named back-reference");
        typename string_type::const_iterator begin = cur;
        for(; cur != end && BOOST_XPR_CHAR_(char_type, '>') != *cur; ++cur)
        {}
        detail::ensure(cur != begin && cur != end && BOOST_XPR_CHAR_(char_type, '>') == *cur
            , error_badmark, "invalid named back-reference");

        string_type name(begin, cur++);
        for(std::size_t i = 0; i < this->named_marks_.size(); ++i)
        {
            if(this->named_marks_[i].name_ == name)
            {
                std::size_t sub = this->named_marks_[i].mark_nbr_;
                return std::copy(this->sub_matches_[ sub ].first, this->sub_matches_[ sub ].second, out);
            }
        }

        boost::throw_exception(regex_error(error_badmark, "invalid named back-reference"));
        // Should never get here
        return out;
    }

    regex_id_type regex_id_;
    detail::sub_match_vector<BidiIter> sub_matches_;
    BidiIter base_;
    sub_match<BidiIter> prefix_;
    sub_match<BidiIter> suffix_;
    nested_results_type nested_results_;
    intrusive_ptr<extras_type> extras_ptr_;
    intrusive_ptr<detail::traits<char_type> const> traits_;
    detail::action_args_type args_;
    std::vector<detail::named_mark<char_type> > named_marks_;
};

///////////////////////////////////////////////////////////////////////////////
// regex_id_filter_predicate
//
template<typename BidiIter>
struct regex_id_filter_predicate
  : std::unary_function<match_results<BidiIter>, bool>
{
    regex_id_filter_predicate(regex_id_type regex_id)
      : regex_id_(regex_id)
    {
    }

    bool operator ()(match_results<BidiIter> const &res) const
    {
        return this->regex_id_ == res.regex_id();
    }

private:

    regex_id_type regex_id_;
};

}} // namespace boost::xpressive

#ifdef BOOST_HAS_CONCEPTS
// Better living through concepts. :-P
namespace std
{
    template<typename Iter_, typename Char_>
    concept_map OutputIterator<
        boost::xpressive::detail::case_converting_iterator<Iter_, Char_>
      , Char_
    >
    {};

    template<typename Char_>
    concept_map OutputIterator<
        boost::xpressive::detail::noop_output_iterator<Char_>
      , Char_
    >
    {};
}
#endif

#endif