detail/core/optimize.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 // optimize.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_OPTIMIZE_HPP_EAN_10_04_2005
0009 #define BOOST_XPRESSIVE_DETAIL_CORE_OPTIMIZE_HPP_EAN_10_04_2005
0010
0011 #include <string>
0012 #include <utility>
0013 #include <boost/mpl/bool.hpp>
0014 #include <boost/intrusive_ptr.hpp>
0015 #include <boost/iterator/iterator_traits.hpp>
0016 #include <boost/xpressive/detail/core/finder.hpp>
0017 #include <boost/xpressive/detail/core/linker.hpp>
0018 #include <boost/xpressive/detail/core/peeker.hpp>
0019 #include <boost/xpressive/detail/core/regex_impl.hpp>
0020
0021 namespace boost { namespace xpressive { namespace detail
0022 {
0023
0024 ///////////////////////////////////////////////////////////////////////////////
0025 // optimize_regex
0026 //
0027 template<typename BidiIter, typename Traits>
0028 intrusive_ptr<finder<BidiIter> > optimize_regex
0029 (
0030     xpression_peeker<typename iterator_value<BidiIter>::type> const &peeker
0031   , Traits const &tr
0032   , mpl::false_
0033 )
0034 {
0035     if(peeker.line_start())
0036     {
0037         return intrusive_ptr<finder<BidiIter> >
0038         (
0039             new line_start_finder<BidiIter, Traits>(tr)
0040         );
0041     }
0042     else if(peeker.leading_simple_repeat())
0043     {
0044         return intrusive_ptr<finder<BidiIter> >
0045         (
0046             new leading_simple_repeat_finder<BidiIter>()
0047         );
0048     }
0049     else if(256 != peeker.bitset().count())
0050     {
0051         return intrusive_ptr<finder<BidiIter> >
0052         (
0053             new hash_peek_finder<BidiIter, Traits>(peeker.bitset())
0054         );
0055     }
0056
0057     return intrusive_ptr<finder<BidiIter> >();
0058 }
0059
0060 ///////////////////////////////////////////////////////////////////////////////
0061 // optimize_regex
0062 //
0063 template<typename BidiIter, typename Traits>
0064 intrusive_ptr<finder<BidiIter> > optimize_regex
0065 (
0066     xpression_peeker<typename iterator_value<BidiIter>::type> const &peeker
0067   , Traits const &tr
0068   , mpl::true_
0069 )
0070 {
0071     typedef typename iterator_value<BidiIter>::type char_type;
0072
0073     // if we have a leading string literal, initialize a boyer-moore struct with it
0074     peeker_string<char_type> const &str = peeker.get_string();
0075     if(str.begin_ != str.end_)
0076     {
0077         BOOST_ASSERT(1 == peeker.bitset().count());
0078         return intrusive_ptr<finder<BidiIter> >
0079         (
0080             new boyer_moore_finder<BidiIter, Traits>(str.begin_, str.end_, tr, str.icase_)
0081         );
0082     }
0083
0084     return optimize_regex<BidiIter>(peeker, tr, mpl::false_());
0085 }
0086
0087 ///////////////////////////////////////////////////////////////////////////////
0088 // common_compile
0089 //
0090 template<typename BidiIter, typename Traits>
0091 void common_compile
0092 (
0093     intrusive_ptr<matchable_ex<BidiIter> const> const &regex
0094   , regex_impl<BidiIter> &impl
0095   , Traits const &tr
0096 )
0097 {
0098     typedef typename iterator_value<BidiIter>::type char_type;
0099
0100     // "link" the regex
0101     xpression_linker<char_type> linker(tr);
0102     regex->link(linker);
0103
0104     // "peek" into the compiled regex to see if there are optimization opportunities
0105     hash_peek_bitset<char_type> bset;
0106     xpression_peeker<char_type> peeker(bset, tr, linker.has_backrefs());
0107     regex->peek(peeker);
0108
0109     // optimization: get the peek chars OR the boyer-moore search string
0110     impl.finder_ = optimize_regex<BidiIter>(peeker, tr, is_random<BidiIter>());
0111     impl.xpr_ = regex;
0112 }
0113
0114 }}} // namespace boost::xpressive
0115
0116 #endif