boost/xpressive/detail/dynamic/dynamic.hpp
/////////////////////////////////////////////////////////////////////////////// // dynamic.hpp // // Copyright 2004 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) #ifndef BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005 #define BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005 // MS compatible compilers support #pragma once #if defined(_MSC_VER) && (_MSC_VER >= 1020) # pragma once #endif #include <list> #include <utility> #include <algorithm> #include <boost/assert.hpp> #include <boost/mpl/int.hpp> #include <boost/mpl/assert.hpp> #include <boost/xpressive/detail/detail_fwd.hpp> #include <boost/xpressive/detail/core/quant_style.hpp> #include <boost/xpressive/detail/dynamic/matchable.hpp> #include <boost/xpressive/detail/core/icase.hpp> namespace boost { namespace xpressive { namespace detail { /////////////////////////////////////////////////////////////////////////////// // invalid_xpression // template<typename BidiIter> struct invalid_xpression : matchable<BidiIter> { invalid_xpression() : matchable<BidiIter>() { } bool match(state_type<BidiIter> &) const { BOOST_ASSERT(false); return false; } std::size_t get_width(state_type<BidiIter> *) const { return 0; } static void noop(matchable<BidiIter> const *) { } }; /////////////////////////////////////////////////////////////////////////////// // get_invalid_xpression // template<typename BidiIter> inline shared_ptr<matchable<BidiIter> const> const &get_invalid_xpression() { static invalid_xpression<BidiIter> const invalid_xpr; static shared_ptr<matchable<BidiIter> const> const invalid_ptr ( static_cast<matchable<BidiIter> const *>(&invalid_xpr) , &invalid_xpression<BidiIter>::noop ); return invalid_ptr; } /////////////////////////////////////////////////////////////////////////////// // dynamic_xpression // template<typename Matcher, typename BidiIter> struct dynamic_xpression : Matcher , matchable<BidiIter> { typedef typename iterator_value<BidiIter>::type char_type; shared_ptr<matchable<BidiIter> const> next_; dynamic_xpression(Matcher const &matcher = Matcher()) : Matcher(matcher) , next_(get_invalid_xpression<BidiIter>()) { } bool match(state_type<BidiIter> &state) const { return this->Matcher::match(state, *this->next_); } std::size_t get_width(state_type<BidiIter> *state) const { std::size_t this_width = this->Matcher::get_width(state); if(this_width == unknown_width()) return unknown_width(); std::size_t that_width = this->next_->get_width(state); if(that_width == unknown_width()) return unknown_width(); return this_width + that_width; } void link(xpression_linker<char_type> &linker) const { linker.link(*static_cast<Matcher const *>(this), this->next_.get()); this->next_->link(linker); } void peek(xpression_peeker<char_type> &peeker) const { this->peek_next_(peeker.peek(*static_cast<Matcher const *>(this)), peeker); } sequence<BidiIter> quantify ( quant_spec const &spec , std::size_t &hidden_mark_count , sequence<BidiIter> seq , alternates_factory<BidiIter> const &factory ) const { return this->quantify_(spec, hidden_mark_count, seq, quant_type<Matcher>(), factory, this); } bool is_quantifiable() const { return quant_type<Matcher>::value != (int)quant_none || this->next_ != get_invalid_xpression<BidiIter>(); } private: void peek_next_(mpl::true_, xpression_peeker<char_type> &peeker) const { this->next_->peek(peeker); } void peek_next_(mpl::false_, xpression_peeker<char_type> &) const { // no-op } sequence<BidiIter> quantify_ ( quant_spec const & , std::size_t & , sequence<BidiIter> , mpl::int_<quant_none> , alternates_factory<BidiIter> const & , void const * ) const; sequence<BidiIter> quantify_ ( quant_spec const & , std::size_t & , sequence<BidiIter> , mpl::int_<quant_fixed_width> , alternates_factory<BidiIter> const & , void const * ) const; sequence<BidiIter> quantify_ ( quant_spec const & , std::size_t & , sequence<BidiIter> , mpl::int_<quant_variable_width> , alternates_factory<BidiIter> const & , void const * ) const; sequence<BidiIter> quantify_ ( quant_spec const & , std::size_t & , sequence<BidiIter> , mpl::int_<quant_fixed_width> , alternates_factory<BidiIter> const & , mark_begin_matcher const * ) const; }; /////////////////////////////////////////////////////////////////////////////// // make_dynamic_xpression // template<typename BidiIter, typename Matcher> inline sequence<BidiIter> make_dynamic_xpression(Matcher const &matcher) { typedef dynamic_xpression<Matcher, BidiIter> xpression_type; std::auto_ptr<xpression_type> xpr(new xpression_type(matcher)); sequence<BidiIter> seq; seq.second = &xpr->next_; seq.first = xpr; return seq; } /////////////////////////////////////////////////////////////////////////////// // alternates_factory // template<typename BidiIter> struct alternates_factory { typedef std::vector<shared_ptr<matchable<BidiIter> const> > alternates_vector; virtual ~alternates_factory() {} virtual std::pair<sequence<BidiIter>, alternates_vector *> operator ()() const = 0; }; template<typename BidiIter, typename Traits> struct alternates_factory_impl : alternates_factory<BidiIter> { typedef typename alternates_factory<BidiIter>::alternates_vector alternates_vector; std::pair<sequence<BidiIter>, alternates_vector *> operator ()() const { typedef alternate_matcher<alternates_vector, Traits> alternate_matcher; typedef dynamic_xpression<alternate_matcher, BidiIter> alternate_xpression; shared_ptr<alternate_xpression> alt_xpr(new alternate_xpression); sequence<BidiIter> seq(alt_xpr, &alt_xpr->next_); return std::make_pair(seq, &alt_xpr->alternates_); } }; /////////////////////////////////////////////////////////////////////////////// // alternates_to_matchable // template<typename BidiIter> inline sequence<BidiIter> alternates_to_matchable ( std::list<sequence<BidiIter> > const &alternates , alternates_factory<BidiIter> const &factory ) { BOOST_ASSERT(0 != alternates.size()); // If there is only 1 alternate, just return it. if(1 == alternates.size()) { return alternates.front(); } typedef std::vector<shared_ptr<matchable<BidiIter> const> > alternates_vector; std::pair<sequence<BidiIter>, alternates_vector *> result = factory(); // through the wonders of reference counting, all alternates can share an end_alternate typedef dynamic_xpression<alternate_end_matcher, BidiIter> alternate_end_xpression; shared_ptr<alternate_end_xpression> end_alt_xpr(new alternate_end_xpression); // terminate each alternate with an alternate_end_matcher result.second->reserve(alternates.size()); typedef std::list<sequence<BidiIter> > alternates_list; typename alternates_list::const_iterator begin = alternates.begin(), end = alternates.end(); for(; begin != end; ++begin) { if(!begin->is_empty()) { result.second->push_back(begin->first); *begin->second = end_alt_xpr; } else { result.second->push_back(end_alt_xpr); } } return result.first; } /////////////////////////////////////////////////////////////////////////////// // matcher_wrapper // template<typename Matcher> struct matcher_wrapper : Matcher { matcher_wrapper(Matcher const &matcher = Matcher()) : Matcher(matcher) { } template<typename BidiIter> bool match(state_type<BidiIter> &state) const { return this->Matcher::match(state, matcher_wrapper<true_matcher>()); } template<typename Char> void link(xpression_linker<Char> &linker) const { linker.link(*static_cast<Matcher const *>(this), 0); } template<typename Char> void peek(xpression_peeker<Char> &peeker) const { peeker.peek(*static_cast<Matcher const *>(this)); } }; ////////////////////////////////////////////////////////////////////////// // dynamic_xpression::quantify_ // // unquantifiable template<typename Matcher, typename BidiIter> inline sequence<BidiIter> dynamic_xpression<Matcher, BidiIter>::quantify_ ( quant_spec const &spec , std::size_t &hidden_mark_count , sequence<BidiIter> seq , mpl::int_<quant_none> , alternates_factory<BidiIter> const &factory , void const * ) const { BOOST_ASSERT(this->next_ != get_invalid_xpression<BidiIter>()); return this->quantify_(spec, hidden_mark_count, seq, mpl::int_<quant_variable_width>(), factory, this); } // fixed-width matchers template<typename Matcher, typename BidiIter> inline sequence<BidiIter> dynamic_xpression<Matcher, BidiIter>::quantify_ ( quant_spec const &spec , std::size_t &hidden_mark_count , sequence<BidiIter> seq , mpl::int_<quant_fixed_width> , alternates_factory<BidiIter> const &factory , void const * ) const { if(this->next_ != get_invalid_xpression<BidiIter>()) { return this->quantify_(spec, hidden_mark_count, seq, mpl::int_<quant_variable_width>(), factory, this); } typedef matcher_wrapper<Matcher> xpr_type; if(spec.greedy_) { simple_repeat_matcher<xpr_type, true> quant(*this, spec.min_, spec.max_); return make_dynamic_xpression<BidiIter>(quant); } else { simple_repeat_matcher<xpr_type, false> quant(*this, spec.min_, spec.max_); return make_dynamic_xpression<BidiIter>(quant); } } // variable-width, no mark template<typename Matcher, typename BidiIter> inline sequence<BidiIter> dynamic_xpression<Matcher, BidiIter>::quantify_ ( quant_spec const &spec , std::size_t &hidden_mark_count , sequence<BidiIter> seq , mpl::int_<quant_variable_width> , alternates_factory<BidiIter> const &factory , void const * ) const { // create a hidden mark so this expression can be quantified int mark_nbr = -static_cast<int>(++hidden_mark_count); mark_begin_matcher mark_begin(mark_nbr); mark_end_matcher mark_end(mark_nbr); sequence<BidiIter> new_seq = make_dynamic_xpression<BidiIter>(mark_begin); new_seq += seq; new_seq += make_dynamic_xpression<BidiIter>(mark_end); return new_seq.first->quantify(spec, hidden_mark_count, new_seq, factory); } // variable-width with mark template<typename Matcher, typename BidiIter> inline sequence<BidiIter> dynamic_xpression<Matcher, BidiIter>::quantify_ ( quant_spec const &spec , std::size_t & , sequence<BidiIter> seq , mpl::int_<quant_fixed_width> , alternates_factory<BidiIter> const &factory , mark_begin_matcher const * ) const { BOOST_ASSERT(spec.max_); // we should never get here if max is 0 int mark_number = this->mark_number_; // only bother creating a quantifier if max is greater than one if(1 < spec.max_) { unsigned int min = spec.min_ ? spec.min_ : 1U; detail::sequence<BidiIter> seq_quant; // TODO: statically bind the repeat_begin_matcher to the mark_begin for better perf seq_quant += make_dynamic_xpression<BidiIter>(repeat_begin_matcher(mark_number)); // TODO: statically bind the mark_end to the quantifier_end for better perf if(spec.greedy_) { repeat_end_matcher<true> end_quant(mark_number, min, spec.max_); seq += make_dynamic_xpression<BidiIter>(end_quant); } else { repeat_end_matcher<false> end_quant(mark_number, min, spec.max_); seq += make_dynamic_xpression<BidiIter>(end_quant); } seq_quant += seq; seq = seq_quant; } // if min is 0, the quant must be made alternate with an empty matcher. if(0 == spec.min_) { epsilon_mark_matcher mark(mark_number); std::list<sequence<BidiIter> > alts; alts.push_back(make_dynamic_xpression<BidiIter>(mark)); alts.push_back(seq); if(spec.greedy_) alts.reverse(); seq = alternates_to_matchable(alts, factory); } return seq; } }}} // namespace boost::xpressive::detail #endif