1 ///////////////////////////////////////////////////////////////////////////////
2 // optimize.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_CORE_OPTIMIZE_HPP_EAN_10_04_2005
9 #define BOOST_XPRESSIVE_DETAIL_CORE_OPTIMIZE_HPP_EAN_10_04_2005
10
11 #include <string>
12 #include <utility>
13 #include <boost/mpl/bool.hpp>
14 #include <boost/intrusive_ptr.hpp>
15 #include <boost/iterator/iterator_traits.hpp>
16 #include <boost/xpressive/detail/core/finder.hpp>
17 #include <boost/xpressive/detail/core/linker.hpp>
18 #include <boost/xpressive/detail/core/peeker.hpp>
19 #include <boost/xpressive/detail/core/regex_impl.hpp>
20
21 namespace boost { namespace xpressive { namespace detail
22 {
23
24 ///////////////////////////////////////////////////////////////////////////////
25 // optimize_regex
26 //
27 template<typename BidiIter, typename Traits>
optimize_regex(xpression_peeker<typename iterator_value<BidiIter>::type> const & peeker,Traits const & tr,mpl::false_)28 intrusive_ptr<finder<BidiIter> > optimize_regex
29 (
30 xpression_peeker<typename iterator_value<BidiIter>::type> const &peeker
31 , Traits const &tr
32 , mpl::false_
33 )
34 {
35 if(peeker.line_start())
36 {
37 return intrusive_ptr<finder<BidiIter> >
38 (
39 new line_start_finder<BidiIter, Traits>(tr)
40 );
41 }
42 else if(peeker.leading_simple_repeat())
43 {
44 return intrusive_ptr<finder<BidiIter> >
45 (
46 new leading_simple_repeat_finder<BidiIter>()
47 );
48 }
49 else if(256 != peeker.bitset().count())
50 {
51 return intrusive_ptr<finder<BidiIter> >
52 (
53 new hash_peek_finder<BidiIter, Traits>(peeker.bitset())
54 );
55 }
56
57 return intrusive_ptr<finder<BidiIter> >();
58 }
59
60 ///////////////////////////////////////////////////////////////////////////////
61 // optimize_regex
62 //
63 template<typename BidiIter, typename Traits>
optimize_regex(xpression_peeker<typename iterator_value<BidiIter>::type> const & peeker,Traits const & tr,mpl::true_)64 intrusive_ptr<finder<BidiIter> > optimize_regex
65 (
66 xpression_peeker<typename iterator_value<BidiIter>::type> const &peeker
67 , Traits const &tr
68 , mpl::true_
69 )
70 {
71 typedef typename iterator_value<BidiIter>::type char_type;
72
73 // if we have a leading string literal, initialize a boyer-moore struct with it
74 peeker_string<char_type> const &str = peeker.get_string();
75 if(str.begin_ != str.end_)
76 {
77 BOOST_ASSERT(1 == peeker.bitset().count());
78 return intrusive_ptr<finder<BidiIter> >
79 (
80 new boyer_moore_finder<BidiIter, Traits>(str.begin_, str.end_, tr, str.icase_)
81 );
82 }
83
84 return optimize_regex<BidiIter>(peeker, tr, mpl::false_());
85 }
86
87 ///////////////////////////////////////////////////////////////////////////////
88 // common_compile
89 //
90 template<typename BidiIter, typename Traits>
common_compile(intrusive_ptr<matchable_ex<BidiIter> const> const & regex,regex_impl<BidiIter> & impl,Traits const & tr)91 void common_compile
92 (
93 intrusive_ptr<matchable_ex<BidiIter> const> const ®ex
94 , regex_impl<BidiIter> &impl
95 , Traits const &tr
96 )
97 {
98 typedef typename iterator_value<BidiIter>::type char_type;
99
100 // "link" the regex
101 xpression_linker<char_type> linker(tr);
102 regex->link(linker);
103
104 // "peek" into the compiled regex to see if there are optimization opportunities
105 hash_peek_bitset<char_type> bset;
106 xpression_peeker<char_type> peeker(bset, tr, linker.has_backrefs());
107 regex->peek(peeker);
108
109 // optimization: get the peek chars OR the boyer-moore search string
110 impl.finder_ = optimize_regex<BidiIter>(peeker, tr, is_random<BidiIter>());
111 impl.xpr_ = regex;
112 }
113
114 }}} // namespace boost::xpressive
115
116 #endif
117