detail/dynamic/dynamic.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 // dynamic.hpp
0003 //
0004 //  Copyright 2008 Eric Niebler. Distributed under the Boost
0005 //  Software License, Version 1.0. (See accompanying file
0006 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0007
0008 #ifndef BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005
0009 #define BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005
0010
0011 // MS compatible compilers support #pragma once
0012 #if defined(_MSC_VER)
0013 # pragma once
0014 #endif
0015
0016 #include <vector>
0017 #include <utility>
0018 #include <algorithm>
0019 #include <boost/assert.hpp>
0020 #include <boost/mpl/int.hpp>
0021 #include <boost/mpl/assert.hpp>
0022 #include <boost/throw_exception.hpp>
0023 #include <boost/type_traits/is_same.hpp>
0024 #include <boost/xpressive/detail/detail_fwd.hpp>
0025 #include <boost/xpressive/detail/core/quant_style.hpp>
0026 #include <boost/xpressive/detail/dynamic/matchable.hpp>
0027 #include <boost/xpressive/detail/dynamic/sequence.hpp>
0028 #include <boost/xpressive/detail/core/icase.hpp>
0029
0030 namespace boost { namespace xpressive { namespace detail
0031 {
0032
0033 ///////////////////////////////////////////////////////////////////////////////
0034 // invalid_xpression
0035 template<typename BidiIter>
0036 struct invalid_xpression
0037   : matchable_ex<BidiIter>
0038 {
0039     invalid_xpression()
0040       : matchable_ex<BidiIter>()
0041     {
0042         intrusive_ptr_add_ref(this); // keep alive forever
0043     }
0044
0045     bool match(match_state<BidiIter> &) const
0046     {
0047         BOOST_ASSERT(false);
0048         return false;
0049     }
0050 };
0051
0052 ///////////////////////////////////////////////////////////////////////////////
0053 // get_invalid_xpression
0054 template<typename BidiIter>
0055 inline shared_matchable<BidiIter> const &get_invalid_xpression()
0056 {
0057     static invalid_xpression<BidiIter> const invalid_xpr;
0058     static intrusive_ptr<matchable_ex<BidiIter> const> const invalid_ptr(&invalid_xpr);
0059     static shared_matchable<BidiIter> const invalid_matchable(invalid_ptr);
0060     return invalid_matchable;
0061 }
0062
0063 ///////////////////////////////////////////////////////////////////////////////
0064 // dynamic_xpression
0065 template<typename Matcher, typename BidiIter>
0066 struct dynamic_xpression
0067   : Matcher
0068   , matchable_ex<BidiIter>
0069 {
0070     typedef typename iterator_value<BidiIter>::type char_type;
0071
0072     dynamic_xpression(Matcher const &matcher = Matcher())
0073       : Matcher(matcher)
0074       , next_(get_invalid_xpression<BidiIter>())
0075     {
0076     }
0077
0078     virtual bool match(match_state<BidiIter> &state) const
0079     {
0080         return this->Matcher::match(state, *this->next_.matchable());
0081     }
0082
0083     virtual void link(xpression_linker<char_type> &linker) const
0084     {
0085         linker.accept(*static_cast<Matcher const *>(this), this->next_.matchable().get());
0086         this->next_.link(linker);
0087     }
0088
0089     virtual void peek(xpression_peeker<char_type> &peeker) const
0090     {
0091         this->peek_next_(peeker.accept(*static_cast<Matcher const *>(this)), peeker);
0092     }
0093
0094     virtual void repeat(quant_spec const &spec, sequence<BidiIter> &seq) const
0095     {
0096         this->repeat_(spec, seq, quant_type<Matcher>(), is_same<Matcher, mark_begin_matcher>());
0097     }
0098
0099 private:
0100     friend struct sequence<BidiIter>;
0101
0102     void peek_next_(mpl::true_, xpression_peeker<char_type> &peeker) const
0103     {
0104         this->next_.peek(peeker);
0105     }
0106
0107     void peek_next_(mpl::false_, xpression_peeker<char_type> &) const
0108     {
0109         // no-op
0110     }
0111
0112     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_none>, mpl::false_) const
0113     {
0114         if(quant_none == seq.quant())
0115         {
0116             BOOST_THROW_EXCEPTION(
0117                 regex_error(regex_constants::error_badrepeat, "expression cannot be quantified")
0118             );
0119         }
0120         else
0121         {
0122             this->repeat_(spec, seq, mpl::int_<quant_variable_width>(), mpl::false_());
0123         }
0124     }
0125
0126     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_fixed_width>, mpl::false_) const
0127     {
0128         if(this->next_ == get_invalid_xpression<BidiIter>())
0129         {
0130             make_simple_repeat(spec, seq, matcher_wrapper<Matcher>(*this));
0131         }
0132         else
0133         {
0134             this->repeat_(spec, seq, mpl::int_<quant_variable_width>(), mpl::false_());
0135         }
0136     }
0137
0138     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_variable_width>, mpl::false_) const
0139     {
0140         if(!is_unknown(seq.width()) && seq.pure())
0141         {
0142             make_simple_repeat(spec, seq);
0143         }
0144         else
0145         {
0146             make_repeat(spec, seq);
0147         }
0148     }
0149
0150     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_fixed_width>, mpl::true_) const
0151     {
0152         make_repeat(spec, seq, this->mark_number_);
0153     }
0154
0155     shared_matchable<BidiIter> next_;
0156 };
0157
0158 ///////////////////////////////////////////////////////////////////////////////
0159 // make_dynamic
0160 template<typename BidiIter, typename Matcher>
0161 inline sequence<BidiIter> make_dynamic(Matcher const &matcher)
0162 {
0163     typedef dynamic_xpression<Matcher, BidiIter> xpression_type;
0164     intrusive_ptr<xpression_type> xpr(new xpression_type(matcher));
0165     return sequence<BidiIter>(xpr);
0166 }
0167
0168 ///////////////////////////////////////////////////////////////////////////////
0169 // alternates_vector
0170 template<typename BidiIter>
0171 struct alternates_vector
0172   : std::vector<shared_matchable<BidiIter> >
0173 {
0174     BOOST_STATIC_CONSTANT(std::size_t, width = unknown_width::value);
0175     BOOST_STATIC_CONSTANT(bool, pure = false);
0176 };
0177
0178 ///////////////////////////////////////////////////////////////////////////////
0179 // matcher_wrapper
0180 template<typename Matcher>
0181 struct matcher_wrapper
0182   : Matcher
0183 {
0184     matcher_wrapper(Matcher const &matcher = Matcher())
0185       : Matcher(matcher)
0186     {
0187     }
0188
0189     template<typename BidiIter>
0190     bool match(match_state<BidiIter> &state) const
0191     {
0192         return this->Matcher::match(state, matcher_wrapper<true_matcher>());
0193     }
0194
0195     template<typename Char>
0196     void link(xpression_linker<Char> &linker) const
0197     {
0198         linker.accept(*static_cast<Matcher const *>(this), 0);
0199     }
0200
0201     template<typename Char>
0202     void peek(xpression_peeker<Char> &peeker) const
0203     {
0204         peeker.accept(*static_cast<Matcher const *>(this));
0205     }
0206 };
0207
0208 //////////////////////////////////////////////////////////////////////////
0209 // make_simple_repeat
0210 template<typename BidiIter, typename Xpr>
0211 inline void
0212 make_simple_repeat(quant_spec const &spec, sequence<BidiIter> &seq, Xpr const &xpr)
0213 {
0214     if(spec.greedy_)
0215     {
0216         simple_repeat_matcher<Xpr, mpl::true_> quant(xpr, spec.min_, spec.max_, seq.width().value());
0217         seq = make_dynamic<BidiIter>(quant);
0218     }
0219     else
0220     {
0221         simple_repeat_matcher<Xpr, mpl::false_> quant(xpr, spec.min_, spec.max_, seq.width().value());
0222         seq = make_dynamic<BidiIter>(quant);
0223     }
0224 }
0225
0226 //////////////////////////////////////////////////////////////////////////
0227 // make_simple_repeat
0228 template<typename BidiIter>
0229 inline void
0230 make_simple_repeat(quant_spec const &spec, sequence<BidiIter> &seq)
0231 {
0232     seq += make_dynamic<BidiIter>(true_matcher());
0233     make_simple_repeat(spec, seq, seq.xpr());
0234 }
0235
0236 //////////////////////////////////////////////////////////////////////////
0237 // make_optional
0238 template<typename BidiIter>
0239 inline void
0240 make_optional(quant_spec const &spec, sequence<BidiIter> &seq)
0241 {
0242     typedef shared_matchable<BidiIter> xpr_type;
0243     seq += make_dynamic<BidiIter>(alternate_end_matcher());
0244     if(spec.greedy_)
0245     {
0246         optional_matcher<xpr_type, mpl::true_> opt(seq.xpr());
0247         seq = make_dynamic<BidiIter>(opt);
0248     }
0249     else
0250     {
0251         optional_matcher<xpr_type, mpl::false_> opt(seq.xpr());
0252         seq = make_dynamic<BidiIter>(opt);
0253     }
0254 }
0255
0256 //////////////////////////////////////////////////////////////////////////
0257 // make_optional
0258 template<typename BidiIter>
0259 inline void
0260 make_optional(quant_spec const &spec, sequence<BidiIter> &seq, int mark_nbr)
0261 {
0262     typedef shared_matchable<BidiIter> xpr_type;
0263     seq += make_dynamic<BidiIter>(alternate_end_matcher());
0264     if(spec.greedy_)
0265     {
0266         optional_mark_matcher<xpr_type, mpl::true_> opt(seq.xpr(), mark_nbr);
0267         seq = make_dynamic<BidiIter>(opt);
0268     }
0269     else
0270     {
0271         optional_mark_matcher<xpr_type, mpl::false_> opt(seq.xpr(), mark_nbr);
0272         seq = make_dynamic<BidiIter>(opt);
0273     }
0274 }
0275
0276 //////////////////////////////////////////////////////////////////////////
0277 // make_repeat
0278 template<typename BidiIter>
0279 inline void
0280 make_repeat(quant_spec const &spec, sequence<BidiIter> &seq)
0281 {
0282     // only bother creating a repeater if max is greater than one
0283     if(1 < spec.max_)
0284     {
0285         // create a hidden mark so this expression can be quantified
0286         int mark_nbr = -static_cast<int>(++*spec.hidden_mark_count_);
0287         seq = make_dynamic<BidiIter>(mark_begin_matcher(mark_nbr)) + seq
0288             + make_dynamic<BidiIter>(mark_end_matcher(mark_nbr));
0289         make_repeat(spec, seq, mark_nbr);
0290         return;
0291     }
0292
0293     // if min is 0, the repeat must be made optional
0294     if(0 == spec.min_)
0295     {
0296         make_optional(spec, seq);
0297     }
0298 }
0299
0300 //////////////////////////////////////////////////////////////////////////
0301 // make_repeat
0302 template<typename BidiIter>
0303 inline void
0304 make_repeat(quant_spec const &spec, sequence<BidiIter> &seq, int mark_nbr)
0305 {
0306     BOOST_ASSERT(spec.max_); // we should never get here if max is 0
0307
0308     // only bother creating a repeater if max is greater than one
0309     if(1 < spec.max_)
0310     {
0311         // TODO: statically bind the repeat matchers to the mark matchers for better perf
0312         unsigned int min = spec.min_ ? spec.min_ : 1U;
0313         repeat_begin_matcher repeat_begin(mark_nbr);
0314         if(spec.greedy_)
0315         {
0316             repeat_end_matcher<mpl::true_> repeat_end(mark_nbr, min, spec.max_);
0317             seq = make_dynamic<BidiIter>(repeat_begin) + seq
0318                 + make_dynamic<BidiIter>(repeat_end);
0319         }
0320         else
0321         {
0322             repeat_end_matcher<mpl::false_> repeat_end(mark_nbr, min, spec.max_);
0323             seq = make_dynamic<BidiIter>(repeat_begin) + seq
0324                 + make_dynamic<BidiIter>(repeat_end);
0325         }
0326     }
0327
0328     // if min is 0, the repeat must be made optional
0329     if(0 == spec.min_)
0330     {
0331         make_optional(spec, seq, mark_nbr);
0332     }
0333 }
0334
0335 }}} // namespace boost::xpressive::detail
0336
0337 #endif