Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // dynamic.hpp
Chris@16: //
Chris@16: //  Copyright 2008 Eric Niebler. Distributed under the Boost
Chris@16: //  Software License, Version 1.0. (See accompanying file
Chris@16: //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005
Chris@16: #define BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005
Chris@16: 
Chris@16: // MS compatible compilers support #pragma once
Chris@101: #if defined(_MSC_VER)
Chris@16: # pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <utility>
Chris@16: #include <algorithm>
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/mpl/int.hpp>
Chris@16: #include <boost/mpl/assert.hpp>
Chris@16: #include <boost/throw_exception.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: #include <boost/xpressive/detail/detail_fwd.hpp>
Chris@16: #include <boost/xpressive/detail/core/quant_style.hpp>
Chris@16: #include <boost/xpressive/detail/dynamic/matchable.hpp>
Chris@16: #include <boost/xpressive/detail/dynamic/sequence.hpp>
Chris@16: #include <boost/xpressive/detail/core/icase.hpp>
Chris@16: 
Chris@16: namespace boost { namespace xpressive { namespace detail
Chris@16: {
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // invalid_xpression
Chris@16: template<typename BidiIter>
Chris@16: struct invalid_xpression
Chris@16:   : matchable_ex<BidiIter>
Chris@16: {
Chris@16:     invalid_xpression()
Chris@16:       : matchable_ex<BidiIter>()
Chris@16:     {
Chris@16:         intrusive_ptr_add_ref(this); // keep alive forever
Chris@16:     }
Chris@16: 
Chris@16:     bool match(match_state<BidiIter> &) const
Chris@16:     {
Chris@16:         BOOST_ASSERT(false);
Chris@16:         return false;
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // get_invalid_xpression
Chris@16: template<typename BidiIter>
Chris@16: inline shared_matchable<BidiIter> const &get_invalid_xpression()
Chris@16: {
Chris@16:     static invalid_xpression<BidiIter> const invalid_xpr;
Chris@16:     static intrusive_ptr<matchable_ex<BidiIter> const> const invalid_ptr(&invalid_xpr);
Chris@16:     static shared_matchable<BidiIter> const invalid_matchable(invalid_ptr);
Chris@16:     return invalid_matchable;
Chris@16: }
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // dynamic_xpression
Chris@16: template<typename Matcher, typename BidiIter>
Chris@16: struct dynamic_xpression
Chris@16:   : Matcher
Chris@16:   , matchable_ex<BidiIter>
Chris@16: {
Chris@16:     typedef typename iterator_value<BidiIter>::type char_type;
Chris@16: 
Chris@16:     dynamic_xpression(Matcher const &matcher = Matcher())
Chris@16:       : Matcher(matcher)
Chris@16:       , next_(get_invalid_xpression<BidiIter>())
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     virtual bool match(match_state<BidiIter> &state) const
Chris@16:     {
Chris@16:         return this->Matcher::match(state, *this->next_.matchable());
Chris@16:     }
Chris@16: 
Chris@16:     virtual void link(xpression_linker<char_type> &linker) const
Chris@16:     {
Chris@16:         linker.accept(*static_cast<Matcher const *>(this), this->next_.matchable().get());
Chris@16:         this->next_.link(linker);
Chris@16:     }
Chris@16: 
Chris@16:     virtual void peek(xpression_peeker<char_type> &peeker) const
Chris@16:     {
Chris@16:         this->peek_next_(peeker.accept(*static_cast<Matcher const *>(this)), peeker);
Chris@16:     }
Chris@16: 
Chris@16:     virtual void repeat(quant_spec const &spec, sequence<BidiIter> &seq) const
Chris@16:     {
Chris@16:         this->repeat_(spec, seq, quant_type<Matcher>(), is_same<Matcher, mark_begin_matcher>());
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     friend struct sequence<BidiIter>;
Chris@16: 
Chris@16:     void peek_next_(mpl::true_, xpression_peeker<char_type> &peeker) const
Chris@16:     {
Chris@16:         this->next_.peek(peeker);
Chris@16:     }
Chris@16: 
Chris@16:     void peek_next_(mpl::false_, xpression_peeker<char_type> &) const
Chris@16:     {
Chris@16:         // no-op
Chris@16:     }
Chris@16: 
Chris@16:     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_none>, mpl::false_) const
Chris@16:     {
Chris@16:         if(quant_none == seq.quant())
Chris@16:         {
Chris@16:             BOOST_THROW_EXCEPTION(
Chris@16:                 regex_error(regex_constants::error_badrepeat, "expression cannot be quantified")
Chris@16:             );
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             this->repeat_(spec, seq, mpl::int_<quant_variable_width>(), mpl::false_());
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_fixed_width>, mpl::false_) const
Chris@16:     {
Chris@16:         if(this->next_ == get_invalid_xpression<BidiIter>())
Chris@16:         {
Chris@16:             make_simple_repeat(spec, seq, matcher_wrapper<Matcher>(*this));
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             this->repeat_(spec, seq, mpl::int_<quant_variable_width>(), mpl::false_());
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_variable_width>, mpl::false_) const
Chris@16:     {
Chris@16:         if(!is_unknown(seq.width()) && seq.pure())
Chris@16:         {
Chris@16:             make_simple_repeat(spec, seq);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             make_repeat(spec, seq);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_fixed_width>, mpl::true_) const
Chris@16:     {
Chris@16:         make_repeat(spec, seq, this->mark_number_);
Chris@16:     }
Chris@16: 
Chris@16:     shared_matchable<BidiIter> next_;
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // make_dynamic
Chris@16: template<typename BidiIter, typename Matcher>
Chris@16: inline sequence<BidiIter> make_dynamic(Matcher const &matcher)
Chris@16: {
Chris@16:     typedef dynamic_xpression<Matcher, BidiIter> xpression_type;
Chris@16:     intrusive_ptr<xpression_type> xpr(new xpression_type(matcher));
Chris@16:     return sequence<BidiIter>(xpr);
Chris@16: }
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // alternates_vector
Chris@16: template<typename BidiIter>
Chris@16: struct alternates_vector
Chris@16:   : std::vector<shared_matchable<BidiIter> >
Chris@16: {
Chris@16:     BOOST_STATIC_CONSTANT(std::size_t, width = unknown_width::value);
Chris@16:     BOOST_STATIC_CONSTANT(bool, pure = false);
Chris@16: };
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // matcher_wrapper
Chris@16: template<typename Matcher>
Chris@16: struct matcher_wrapper
Chris@16:   : Matcher
Chris@16: {
Chris@16:     matcher_wrapper(Matcher const &matcher = Matcher())
Chris@16:       : Matcher(matcher)
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     template<typename BidiIter>
Chris@16:     bool match(match_state<BidiIter> &state) const
Chris@16:     {
Chris@16:         return this->Matcher::match(state, matcher_wrapper<true_matcher>());
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Char>
Chris@16:     void link(xpression_linker<Char> &linker) const
Chris@16:     {
Chris@16:         linker.accept(*static_cast<Matcher const *>(this), 0);
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Char>
Chris@16:     void peek(xpression_peeker<Char> &peeker) const
Chris@16:     {
Chris@16:         peeker.accept(*static_cast<Matcher const *>(this));
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: //////////////////////////////////////////////////////////////////////////
Chris@16: // make_simple_repeat
Chris@16: template<typename BidiIter, typename Xpr>
Chris@16: inline void
Chris@16: make_simple_repeat(quant_spec const &spec, sequence<BidiIter> &seq, Xpr const &xpr)
Chris@16: {
Chris@16:     if(spec.greedy_)
Chris@16:     {
Chris@16:         simple_repeat_matcher<Xpr, mpl::true_> quant(xpr, spec.min_, spec.max_, seq.width().value());
Chris@16:         seq = make_dynamic<BidiIter>(quant);
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         simple_repeat_matcher<Xpr, mpl::false_> quant(xpr, spec.min_, spec.max_, seq.width().value());
Chris@16:         seq = make_dynamic<BidiIter>(quant);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////////////////////////////////////////////
Chris@16: // make_simple_repeat
Chris@16: template<typename BidiIter>
Chris@16: inline void
Chris@16: make_simple_repeat(quant_spec const &spec, sequence<BidiIter> &seq)
Chris@16: {
Chris@16:     seq += make_dynamic<BidiIter>(true_matcher());
Chris@16:     make_simple_repeat(spec, seq, seq.xpr());
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////////////////////////////////////////////
Chris@16: // make_optional
Chris@16: template<typename BidiIter>
Chris@16: inline void
Chris@16: make_optional(quant_spec const &spec, sequence<BidiIter> &seq)
Chris@16: {
Chris@16:     typedef shared_matchable<BidiIter> xpr_type;
Chris@16:     seq += make_dynamic<BidiIter>(alternate_end_matcher());
Chris@16:     if(spec.greedy_)
Chris@16:     {
Chris@16:         optional_matcher<xpr_type, mpl::true_> opt(seq.xpr());
Chris@16:         seq = make_dynamic<BidiIter>(opt);
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         optional_matcher<xpr_type, mpl::false_> opt(seq.xpr());
Chris@16:         seq = make_dynamic<BidiIter>(opt);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////////////////////////////////////////////
Chris@16: // make_optional
Chris@16: template<typename BidiIter>
Chris@16: inline void
Chris@16: make_optional(quant_spec const &spec, sequence<BidiIter> &seq, int mark_nbr)
Chris@16: {
Chris@16:     typedef shared_matchable<BidiIter> xpr_type;
Chris@16:     seq += make_dynamic<BidiIter>(alternate_end_matcher());
Chris@16:     if(spec.greedy_)
Chris@16:     {
Chris@16:         optional_mark_matcher<xpr_type, mpl::true_> opt(seq.xpr(), mark_nbr);
Chris@16:         seq = make_dynamic<BidiIter>(opt);
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         optional_mark_matcher<xpr_type, mpl::false_> opt(seq.xpr(), mark_nbr);
Chris@16:         seq = make_dynamic<BidiIter>(opt);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////////////////////////////////////////////
Chris@16: // make_repeat
Chris@16: template<typename BidiIter>
Chris@16: inline void
Chris@16: make_repeat(quant_spec const &spec, sequence<BidiIter> &seq)
Chris@16: {
Chris@16:     // only bother creating a repeater if max is greater than one
Chris@16:     if(1 < spec.max_)
Chris@16:     {
Chris@16:         // create a hidden mark so this expression can be quantified
Chris@16:         int mark_nbr = -static_cast<int>(++*spec.hidden_mark_count_);
Chris@16:         seq = make_dynamic<BidiIter>(mark_begin_matcher(mark_nbr)) + seq
Chris@16:             + make_dynamic<BidiIter>(mark_end_matcher(mark_nbr));
Chris@16:         make_repeat(spec, seq, mark_nbr);
Chris@16:         return;
Chris@16:     }
Chris@16: 
Chris@16:     // if min is 0, the repeat must be made optional
Chris@16:     if(0 == spec.min_)
Chris@16:     {
Chris@16:         make_optional(spec, seq);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: //////////////////////////////////////////////////////////////////////////
Chris@16: // make_repeat
Chris@16: template<typename BidiIter>
Chris@16: inline void
Chris@16: make_repeat(quant_spec const &spec, sequence<BidiIter> &seq, int mark_nbr)
Chris@16: {
Chris@16:     BOOST_ASSERT(spec.max_); // we should never get here if max is 0
Chris@16: 
Chris@16:     // only bother creating a repeater if max is greater than one
Chris@16:     if(1 < spec.max_)
Chris@16:     {
Chris@16:         // TODO: statically bind the repeat matchers to the mark matchers for better perf
Chris@16:         unsigned int min = spec.min_ ? spec.min_ : 1U;
Chris@16:         repeat_begin_matcher repeat_begin(mark_nbr);
Chris@16:         if(spec.greedy_)
Chris@16:         {
Chris@16:             repeat_end_matcher<mpl::true_> repeat_end(mark_nbr, min, spec.max_);
Chris@16:             seq = make_dynamic<BidiIter>(repeat_begin) + seq
Chris@16:                 + make_dynamic<BidiIter>(repeat_end);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             repeat_end_matcher<mpl::false_> repeat_end(mark_nbr, min, spec.max_);
Chris@16:             seq = make_dynamic<BidiIter>(repeat_begin) + seq
Chris@16:                 + make_dynamic<BidiIter>(repeat_end);
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     // if min is 0, the repeat must be made optional
Chris@16:     if(0 == spec.min_)
Chris@16:     {
Chris@16:         make_optional(spec, seq, mark_nbr);
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: }}} // namespace boost::xpressive::detail
Chris@16: 
Chris@16: #endif