ceph/src/boost/libs/xpressive/include/boost/xpressive/detail/dynamic/dynamic.hpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // dynamic.hpp
   3 //
   4 //  Copyright 2008 Eric Niebler. Distributed under the Boost
   5 //  Software License, Version 1.0. (See accompanying file
   6 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   7
   8 #ifndef BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005
   9 #define BOOST_XPRESSIVE_DETAIL_DYNAMIC_DYNAMIC_HPP_EAN_10_04_2005
  10
  11 // MS compatible compilers support #pragma once
  12 #if defined(_MSC_VER)
  13 # pragma once
  14 #endif
  15
  16 #include <vector>
  17 #include <utility>
  18 #include <algorithm>
  19 #include <boost/assert.hpp>
  20 #include <boost/mpl/int.hpp>
  21 #include <boost/mpl/assert.hpp>
  22 #include <boost/throw_exception.hpp>
  23 #include <boost/type_traits/is_same.hpp>
  24 #include <boost/xpressive/detail/detail_fwd.hpp>
  25 #include <boost/xpressive/detail/core/quant_style.hpp>
  26 #include <boost/xpressive/detail/dynamic/matchable.hpp>
  27 #include <boost/xpressive/detail/dynamic/sequence.hpp>
  28 #include <boost/xpressive/detail/core/icase.hpp>
  29
  30 namespace boost { namespace xpressive { namespace detail
  31 {
  32
  33 ///////////////////////////////////////////////////////////////////////////////
  34 // invalid_xpression
  35 template<typename BidiIter>
  36 struct invalid_xpression
  37   : matchable_ex<BidiIter>
  38 {
  39     invalid_xpression()
  40       : matchable_ex<BidiIter>()
  41     {
  42         intrusive_ptr_add_ref(this); // keep alive forever
  43     }
  44
  45     bool match(match_state<BidiIter> &) const
  46     {
  47         BOOST_ASSERT(false);
  48         return false;
  49     }
  50 };
  51
  52 ///////////////////////////////////////////////////////////////////////////////
  53 // get_invalid_xpression
  54 template<typename BidiIter>
  55 inline shared_matchable<BidiIter> const &get_invalid_xpression()
  56 {
  57     static invalid_xpression<BidiIter> const invalid_xpr;
  58     static intrusive_ptr<matchable_ex<BidiIter> const> const invalid_ptr(&invalid_xpr);
  59     static shared_matchable<BidiIter> const invalid_matchable(invalid_ptr);
  60     return invalid_matchable;
  61 }
  62
  63 ///////////////////////////////////////////////////////////////////////////////
  64 // dynamic_xpression
  65 template<typename Matcher, typename BidiIter>
  66 struct dynamic_xpression
  67   : Matcher
  68   , matchable_ex<BidiIter>
  69 {
  70     typedef typename iterator_value<BidiIter>::type char_type;
  71
  72     dynamic_xpression(Matcher const &matcher = Matcher())
  73       : Matcher(matcher)
  74       , next_(get_invalid_xpression<BidiIter>())
  75     {
  76     }
  77
  78     virtual bool match(match_state<BidiIter> &state) const
  79     {
  80         return this->Matcher::match(state, *this->next_.matchable());
  81     }
  82
  83     virtual void link(xpression_linker<char_type> &linker) const
  84     {
  85         linker.accept(*static_cast<Matcher const *>(this), this->next_.matchable().get());
  86         this->next_.link(linker);
  87     }
  88
  89     virtual void peek(xpression_peeker<char_type> &peeker) const
  90     {
  91         this->peek_next_(peeker.accept(*static_cast<Matcher const *>(this)), peeker);
  92     }
  93
  94     virtual void repeat(quant_spec const &spec, sequence<BidiIter> &seq) const
  95     {
  96         this->repeat_(spec, seq, quant_type<Matcher>(), is_same<Matcher, mark_begin_matcher>());
  97     }
  98
  99 private:
 100     friend struct sequence<BidiIter>;
 101
 102     void peek_next_(mpl::true_, xpression_peeker<char_type> &peeker) const
 103     {
 104         this->next_.peek(peeker);
 105     }
 106
 107     void peek_next_(mpl::false_, xpression_peeker<char_type> &) const
 108     {
 109         // no-op
 110     }
 111
 112     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_none>, mpl::false_) const
 113     {
 114         if(quant_none == seq.quant())
 115         {
 116             BOOST_THROW_EXCEPTION(
 117                 regex_error(regex_constants::error_badrepeat, "expression cannot be quantified")
 118             );
 119         }
 120         else
 121         {
 122             this->repeat_(spec, seq, mpl::int_<quant_variable_width>(), mpl::false_());
 123         }
 124     }
 125
 126     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_fixed_width>, mpl::false_) const
 127     {
 128         if(this->next_ == get_invalid_xpression<BidiIter>())
 129         {
 130             make_simple_repeat(spec, seq, matcher_wrapper<Matcher>(*this));
 131         }
 132         else
 133         {
 134             this->repeat_(spec, seq, mpl::int_<quant_variable_width>(), mpl::false_());
 135         }
 136     }
 137
 138     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_variable_width>, mpl::false_) const
 139     {
 140         if(!is_unknown(seq.width()) && seq.pure())
 141         {
 142             make_simple_repeat(spec, seq);
 143         }
 144         else
 145         {
 146             make_repeat(spec, seq);
 147         }
 148     }
 149
 150     void repeat_(quant_spec const &spec, sequence<BidiIter> &seq, mpl::int_<quant_fixed_width>, mpl::true_) const
 151     {
 152         make_repeat(spec, seq, this->mark_number_);
 153     }
 154
 155     shared_matchable<BidiIter> next_;
 156 };
 157
 158 ///////////////////////////////////////////////////////////////////////////////
 159 // make_dynamic
 160 template<typename BidiIter, typename Matcher>
 161 inline sequence<BidiIter> make_dynamic(Matcher const &matcher)
 162 {
 163     typedef dynamic_xpression<Matcher, BidiIter> xpression_type;
 164     intrusive_ptr<xpression_type> xpr(new xpression_type(matcher));
 165     return sequence<BidiIter>(xpr);
 166 }
 167
 168 ///////////////////////////////////////////////////////////////////////////////
 169 // alternates_vector
 170 template<typename BidiIter>
 171 struct alternates_vector
 172   : std::vector<shared_matchable<BidiIter> >
 173 {
 174     BOOST_STATIC_CONSTANT(std::size_t, width = unknown_width::value);
 175     BOOST_STATIC_CONSTANT(bool, pure = false);
 176 };
 177
 178 ///////////////////////////////////////////////////////////////////////////////
 179 // matcher_wrapper
 180 template<typename Matcher>
 181 struct matcher_wrapper
 182   : Matcher
 183 {
 184     matcher_wrapper(Matcher const &matcher = Matcher())
 185       : Matcher(matcher)
 186     {
 187     }
 188
 189     template<typename BidiIter>
 190     bool match(match_state<BidiIter> &state) const
 191     {
 192         return this->Matcher::match(state, matcher_wrapper<true_matcher>());
 193     }
 194
 195     template<typename Char>
 196     void link(xpression_linker<Char> &linker) const
 197     {
 198         linker.accept(*static_cast<Matcher const *>(this), 0);
 199     }
 200
 201     template<typename Char>
 202     void peek(xpression_peeker<Char> &peeker) const
 203     {
 204         peeker.accept(*static_cast<Matcher const *>(this));
 205     }
 206 };
 207
 208 //////////////////////////////////////////////////////////////////////////
 209 // make_simple_repeat
 210 template<typename BidiIter, typename Xpr>
 211 inline void
 212 make_simple_repeat(quant_spec const &spec, sequence<BidiIter> &seq, Xpr const &xpr)
 213 {
 214     if(spec.greedy_)
 215     {
 216         simple_repeat_matcher<Xpr, mpl::true_> quant(xpr, spec.min_, spec.max_, seq.width().value());
 217         seq = make_dynamic<BidiIter>(quant);
 218     }
 219     else
 220     {
 221         simple_repeat_matcher<Xpr, mpl::false_> quant(xpr, spec.min_, spec.max_, seq.width().value());
 222         seq = make_dynamic<BidiIter>(quant);
 223     }
 224 }
 225
 226 //////////////////////////////////////////////////////////////////////////
 227 // make_simple_repeat
 228 template<typename BidiIter>
 229 inline void
 230 make_simple_repeat(quant_spec const &spec, sequence<BidiIter> &seq)
 231 {
 232     seq += make_dynamic<BidiIter>(true_matcher());
 233     make_simple_repeat(spec, seq, seq.xpr());
 234 }
 235
 236 //////////////////////////////////////////////////////////////////////////
 237 // make_optional
 238 template<typename BidiIter>
 239 inline void
 240 make_optional(quant_spec const &spec, sequence<BidiIter> &seq)
 241 {
 242     typedef shared_matchable<BidiIter> xpr_type;
 243     seq += make_dynamic<BidiIter>(alternate_end_matcher());
 244     if(spec.greedy_)
 245     {
 246         optional_matcher<xpr_type, mpl::true_> opt(seq.xpr());
 247         seq = make_dynamic<BidiIter>(opt);
 248     }
 249     else
 250     {
 251         optional_matcher<xpr_type, mpl::false_> opt(seq.xpr());
 252         seq = make_dynamic<BidiIter>(opt);
 253     }
 254 }
 255
 256 //////////////////////////////////////////////////////////////////////////
 257 // make_optional
 258 template<typename BidiIter>
 259 inline void
 260 make_optional(quant_spec const &spec, sequence<BidiIter> &seq, int mark_nbr)
 261 {
 262     typedef shared_matchable<BidiIter> xpr_type;
 263     seq += make_dynamic<BidiIter>(alternate_end_matcher());
 264     if(spec.greedy_)
 265     {
 266         optional_mark_matcher<xpr_type, mpl::true_> opt(seq.xpr(), mark_nbr);
 267         seq = make_dynamic<BidiIter>(opt);
 268     }
 269     else
 270     {
 271         optional_mark_matcher<xpr_type, mpl::false_> opt(seq.xpr(), mark_nbr);
 272         seq = make_dynamic<BidiIter>(opt);
 273     }
 274 }
 275
 276 //////////////////////////////////////////////////////////////////////////
 277 // make_repeat
 278 template<typename BidiIter>
 279 inline void
 280 make_repeat(quant_spec const &spec, sequence<BidiIter> &seq)
 281 {
 282     // only bother creating a repeater if max is greater than one
 283     if(1 < spec.max_)
 284     {
 285         // create a hidden mark so this expression can be quantified
 286         int mark_nbr = -static_cast<int>(++*spec.hidden_mark_count_);
 287         seq = make_dynamic<BidiIter>(mark_begin_matcher(mark_nbr)) + seq
 288             + make_dynamic<BidiIter>(mark_end_matcher(mark_nbr));
 289         make_repeat(spec, seq, mark_nbr);
 290         return;
 291     }
 292
 293     // if min is 0, the repeat must be made optional
 294     if(0 == spec.min_)
 295     {
 296         make_optional(spec, seq);
 297     }
 298 }
 299
 300 //////////////////////////////////////////////////////////////////////////
 301 // make_repeat
 302 template<typename BidiIter>
 303 inline void
 304 make_repeat(quant_spec const &spec, sequence<BidiIter> &seq, int mark_nbr)
 305 {
 306     BOOST_ASSERT(spec.max_); // we should never get here if max is 0
 307
 308     // only bother creating a repeater if max is greater than one
 309     if(1 < spec.max_)
 310     {
 311         // TODO: statically bind the repeat matchers to the mark matchers for better perf
 312         unsigned int min = spec.min_ ? spec.min_ : 1U;
 313         repeat_begin_matcher repeat_begin(mark_nbr);
 314         if(spec.greedy_)
 315         {
 316             repeat_end_matcher<mpl::true_> repeat_end(mark_nbr, min, spec.max_);
 317             seq = make_dynamic<BidiIter>(repeat_begin) + seq
 318                 + make_dynamic<BidiIter>(repeat_end);
 319         }
 320         else
 321         {
 322             repeat_end_matcher<mpl::false_> repeat_end(mark_nbr, min, spec.max_);
 323             seq = make_dynamic<BidiIter>(repeat_begin) + seq
 324                 + make_dynamic<BidiIter>(repeat_end);
 325         }
 326     }
 327
 328     // if min is 0, the repeat must be made optional
 329     if(0 == spec.min_)
 330     {
 331         make_optional(spec, seq, mark_nbr);
 332     }
 333 }
 334
 335 }}} // namespace boost::xpressive::detail
 336
 337 #endif