detail/core/state.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 // state.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_CORE_STATE_HPP_EAN_10_04_2005
0009 #define BOOST_XPRESSIVE_DETAIL_CORE_STATE_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 <boost/noncopyable.hpp>
0017 #include <boost/xpressive/detail/detail_fwd.hpp>
0018 #include <boost/xpressive/detail/core/access.hpp>
0019 #include <boost/xpressive/detail/core/action.hpp>
0020 #include <boost/xpressive/detail/core/sub_match_vector.hpp>
0021 #include <boost/xpressive/detail/utility/sequence_stack.hpp>
0022 #include <boost/xpressive/detail/core/regex_impl.hpp>
0023 #include <boost/xpressive/regex_constants.hpp>
0024
0025 namespace boost { namespace xpressive { namespace detail
0026 {
0027
0028 ///////////////////////////////////////////////////////////////////////////////
0029 // match_context
0030 //
0031 template<typename BidiIter>
0032 struct match_context
0033 {
0034     typedef typename iterator_value<BidiIter>::type char_type;
0035
0036     match_context()
0037       : results_ptr_(0)
0038       , prev_context_(0)
0039       , next_ptr_(0)
0040       , traits_(0)
0041     {
0042     }
0043
0044     // pointer to the current match results, passed to actions as a parameter.
0045     match_results<BidiIter> *results_ptr_;
0046
0047     // The previous match context, if this match_context corresponds to a nested regex invocation
0048     match_context<BidiIter> *prev_context_;
0049
0050     // If this is a nested match, the "next" sub-expression to execute after the nested match
0051     matchable<BidiIter> const *next_ptr_;
0052
0053     // A pointer to the current traits object
0054     detail::traits<char_type> const *traits_;
0055 };
0056
0057 ///////////////////////////////////////////////////////////////////////////////
0058 // attr_context
0059 //
0060 struct attr_context
0061 {
0062     // Slots for holding type-erased pointers to attributes
0063     void const **attr_slots_;
0064
0065     // The previous attr context, if one exists
0066     attr_context *prev_attr_context_;
0067 };
0068
0069 ///////////////////////////////////////////////////////////////////////////////
0070 // match_flags
0071 //
0072 struct match_flags
0073 {
0074     bool match_all_;
0075     bool match_prev_avail_;
0076     bool match_bol_;
0077     bool match_eol_;
0078     bool match_not_bow_;
0079     bool match_not_eow_;
0080     bool match_not_null_;
0081     bool match_continuous_;
0082     bool match_partial_;
0083
0084     explicit match_flags(regex_constants::match_flag_type flags)
0085       : match_all_(false)
0086       , match_prev_avail_(0 != (flags & regex_constants::match_prev_avail))
0087       , match_bol_(match_prev_avail_ || 0 == (flags & regex_constants::match_not_bol))
0088       , match_eol_(0 == (flags & regex_constants::match_not_eol))
0089       , match_not_bow_(!match_prev_avail_ && 0 != (flags & regex_constants::match_not_bow))
0090       , match_not_eow_(0 != (flags & regex_constants::match_not_eow))
0091       , match_not_null_(0 != (flags & regex_constants::match_not_null))
0092       , match_continuous_(0 != (flags & regex_constants::match_continuous))
0093       , match_partial_(0 != (flags & regex_constants::match_partial))
0094     {
0095     }
0096 };
0097
0098 ///////////////////////////////////////////////////////////////////////////////
0099 // match_state
0100 //
0101 template<typename BidiIter>
0102 struct match_state
0103   : noncopyable
0104 {
0105     typedef BidiIter iterator;
0106     typedef core_access<BidiIter> access;
0107     typedef detail::match_context<BidiIter> match_context;
0108     typedef detail::results_extras<BidiIter> results_extras;
0109     typedef detail::regex_impl<BidiIter> regex_impl;
0110     typedef detail::matchable<BidiIter> matchable;
0111     typedef xpressive::match_results<BidiIter> match_results;
0112     typedef detail::sub_match_impl<BidiIter> sub_match_impl;
0113     typedef detail::actionable actionable;
0114
0115     BidiIter cur_;
0116     sub_match_impl *sub_matches_;
0117     std::size_t mark_count_;
0118     BidiIter begin_;
0119     BidiIter end_;
0120
0121     match_flags flags_;
0122     bool found_partial_match_;
0123
0124     match_context context_;
0125     results_extras *extras_;
0126     actionable action_list_;
0127     actionable const **action_list_tail_;
0128     action_args_type *action_args_;
0129     attr_context attr_context_;
0130     BidiIter next_search_;
0131
0132     ///////////////////////////////////////////////////////////////////////////////
0133     //
0134     match_state
0135     (
0136         BidiIter begin
0137       , BidiIter end
0138       , match_results &what
0139       , regex_impl const &impl
0140       , regex_constants::match_flag_type flags
0141     )
0142       : cur_(begin)
0143       , sub_matches_(0)
0144       , mark_count_(0)
0145       , begin_(begin)
0146       , end_(end)
0147       , flags_(flags)
0148       , found_partial_match_(false)
0149       , context_() // zero-initializes the fields of context_
0150       , extras_(&core_access<BidiIter>::get_extras(what))
0151       , action_list_()
0152       , action_list_tail_(&action_list_.next)
0153       , action_args_(&core_access<BidiIter>::get_action_args(what))
0154       , attr_context_() // zero-initializes the fields of attr_context_
0155       , next_search_(begin)
0156     {
0157         // reclaim any cached memory in the match_results struct
0158         this->extras_->sub_match_stack_.unwind();
0159
0160         // initialize the context_ struct
0161         this->init_(impl, what);
0162
0163         // move all the nested match_results structs into the match_results cache
0164         this->extras_->results_cache_.reclaim_all(access::get_nested_results(what));
0165     }
0166
0167     ///////////////////////////////////////////////////////////////////////////////
0168     // reset
0169     void reset(match_results &what, regex_impl const &impl)
0170     {
0171         this->extras_ = &core_access<BidiIter>::get_extras(what);
0172         this->action_list_.next = 0;
0173         this->action_list_tail_ = &action_list_.next;
0174         this->action_args_ = &core_access<BidiIter>::get_action_args(what);
0175         this->attr_context_ = attr_context();
0176         this->context_.prev_context_ = 0;
0177         this->found_partial_match_ = false;
0178         this->extras_->sub_match_stack_.unwind();
0179         this->init_(impl, what);
0180         this->extras_->results_cache_.reclaim_all(access::get_nested_results(what));
0181     }
0182
0183     ///////////////////////////////////////////////////////////////////////////////
0184     // push_context
0185     //  called to prepare the state object for a regex match
0186     match_context push_context(regex_impl const &impl, matchable const &next, match_context &prev)
0187     {
0188         // save state
0189         match_context context = this->context_;
0190
0191         // create a new nested match_results for this regex
0192         nested_results<BidiIter> &nested = access::get_nested_results(*context.results_ptr_);
0193         match_results &what = this->extras_->results_cache_.append_new(nested);
0194
0195         // (re)initialize the match context
0196         this->init_(impl, what);
0197
0198         // create a linked list of match_context structs
0199         this->context_.prev_context_ = &prev;
0200         this->context_.next_ptr_ = &next;
0201
0202         // record the start of the zero-th sub-match
0203         this->sub_matches_[0].begin_ = this->cur_;
0204
0205         return context;
0206     }
0207
0208     ///////////////////////////////////////////////////////////////////////////////
0209     // pop_context
0210     //  called after a nested match failed to restore the context
0211     bool pop_context(regex_impl const &impl, bool success)
0212     {
0213         match_context &context = *this->context_.prev_context_;
0214         if(!success)
0215         {
0216             match_results &what = *context.results_ptr_;
0217             this->uninit_(impl, what);
0218
0219             // send the match_results struct back to the cache
0220             nested_results<BidiIter> &nested = access::get_nested_results(what);
0221             this->extras_->results_cache_.reclaim_last(nested);
0222         }
0223
0224         // restore the state
0225         this->context_ = context;
0226         match_results &results = *this->context_.results_ptr_;
0227         this->sub_matches_ = access::get_sub_matches(access::get_sub_match_vector(results));
0228         this->mark_count_ = results.size();
0229         return success;
0230     }
0231
0232     ///////////////////////////////////////////////////////////////////////////////
0233     // swap_context
0234     void swap_context(match_context &context)
0235     {
0236         std::swap(this->context_, context);
0237         match_results &results = *this->context_.results_ptr_;
0238         this->sub_matches_ = access::get_sub_matches(access::get_sub_match_vector(results));
0239         this->mark_count_ = results.size();
0240     }
0241
0242     // beginning of buffer
0243     bool bos() const
0244     {
0245         return this->cur_ == this->begin_;
0246     }
0247
0248     // end of buffer
0249     bool eos()
0250     {
0251         return this->cur_ == this->end_ && this->found_partial_match();
0252     }
0253
0254     // is this the regex that is currently executing?
0255     bool is_active_regex(regex_impl const &impl) const
0256     {
0257         return impl.xpr_.get() == this->context_.results_ptr_->regex_id();
0258     }
0259
0260     // fetch the n-th sub_match
0261     sub_match_impl &sub_match(int n)
0262     {
0263         return this->sub_matches_[n];
0264     }
0265
0266     // called when a partial match has succeeded
0267     void set_partial_match()
0268     {
0269         sub_match_impl &sub0 = this->sub_match(0);
0270         sub0.first = sub0.begin_;
0271         sub0.second = this->end_;
0272         sub0.matched = false;
0273     }
0274
0275     template<typename Traits>
0276     Traits const &get_traits() const
0277     {
0278         return static_cast<traits_holder<Traits> const *>(this->context_.traits_)->traits();
0279     }
0280
0281 private:
0282
0283     void init_(regex_impl const &impl, match_results &what)
0284     {
0285         regex_id_type const id = impl.xpr_.get();
0286         std::size_t const total_mark_count = impl.mark_count_ + impl.hidden_mark_count_ + 1;
0287
0288         // initialize the context and the sub_match vector
0289         this->context_.results_ptr_ = &what;
0290         this->context_.traits_ = impl.traits_.get();
0291         this->mark_count_ = impl.mark_count_ + 1;
0292         this->sub_matches_ = this->extras_->sub_match_stack_.push_sequence(total_mark_count, sub_match_impl(begin_), detail::fill);
0293         this->sub_matches_ += impl.hidden_mark_count_;
0294
0295         // initialize the match_results struct
0296         access::init_match_results(what, id, impl.traits_, this->sub_matches_, this->mark_count_, impl.named_marks_);
0297     }
0298
0299     void uninit_(regex_impl const &impl, match_results &)
0300     {
0301         extras_->sub_match_stack_.unwind_to(this->sub_matches_ - impl.hidden_mark_count_);
0302     }
0303
0304     bool found_partial_match()
0305     {
0306         this->found_partial_match_ = true;
0307         return true;
0308     }
0309 };
0310
0311 ///////////////////////////////////////////////////////////////////////////////
0312 // memento
0313 //
0314 template<typename BidiIter>
0315 struct memento
0316 {
0317     sub_match_impl<BidiIter> *old_sub_matches_;
0318     std::size_t nested_results_count_;
0319     actionable const *action_list_head_;
0320     actionable const **action_list_tail_;
0321     attr_context attr_context_;
0322 };
0323
0324 ///////////////////////////////////////////////////////////////////////////////
0325 // save_sub_matches
0326 //
0327 template<typename BidiIter>
0328 inline memento<BidiIter> save_sub_matches(match_state<BidiIter> &state)
0329 {
0330     memento<BidiIter> mem =
0331     {
0332         state.extras_->sub_match_stack_.push_sequence(state.mark_count_, sub_match_impl<BidiIter>(state.begin_))
0333       , state.context_.results_ptr_->nested_results().size()
0334       , state.action_list_.next
0335       , state.action_list_tail_
0336       , state.attr_context_
0337     };
0338     state.action_list_.next = 0;
0339     state.action_list_tail_ = &state.action_list_.next;
0340     std::copy(state.sub_matches_, state.sub_matches_ + state.mark_count_, mem.old_sub_matches_);
0341     return mem;
0342 }
0343
0344 ///////////////////////////////////////////////////////////////////////////////
0345 // restore_action_queue
0346 //
0347 template<typename BidiIter>
0348 inline void restore_action_queue(memento<BidiIter> const &mem, match_state<BidiIter> &state)
0349 {
0350     state.action_list_.next = mem.action_list_head_;
0351     state.action_list_tail_ = mem.action_list_tail_;
0352     *state.action_list_tail_ = 0;
0353 }
0354
0355 ///////////////////////////////////////////////////////////////////////////////
0356 // restore_sub_matches
0357 //
0358 template<typename BidiIter>
0359 inline void restore_sub_matches(memento<BidiIter> const &mem, match_state<BidiIter> &state)
0360 {
0361     typedef core_access<BidiIter> access;
0362     nested_results<BidiIter> &nested = access::get_nested_results(*state.context_.results_ptr_);
0363     std::size_t count = nested.size() - mem.nested_results_count_;
0364     state.extras_->results_cache_.reclaim_last_n(nested, count);
0365     std::copy(mem.old_sub_matches_, mem.old_sub_matches_ + state.mark_count_, state.sub_matches_);
0366     state.extras_->sub_match_stack_.unwind_to(mem.old_sub_matches_);
0367     state.attr_context_ = mem.attr_context_;
0368 }
0369
0370 ///////////////////////////////////////////////////////////////////////////////
0371 // reclaim_sub_matches
0372 //
0373 template<typename BidiIter>
0374 inline void reclaim_sub_matches(memento<BidiIter> const &mem, match_state<BidiIter> &state, bool success)
0375 {
0376     std::size_t count = state.context_.results_ptr_->nested_results().size() - mem.nested_results_count_;
0377     if(count == 0)
0378     {
0379         state.extras_->sub_match_stack_.unwind_to(mem.old_sub_matches_);
0380     }
0381     // else we have we must orphan this block of backrefs because we are using the stack
0382     // space above it.
0383
0384     if(!success)
0385     {
0386         state.attr_context_ = mem.attr_context_;
0387     }
0388 }
0389
0390 ///////////////////////////////////////////////////////////////////////////////
0391 // traits_cast
0392 //
0393 template<typename Traits, typename BidiIter>
0394 inline Traits const &traits_cast(match_state<BidiIter> const &state)
0395 {
0396     return state.template get_traits<Traits>();
0397 }
0398
0399 }}} // namespace boost::xpressive::detail
0400
0401 #endif