regex_algorithms.hpp

来自「support vector clustering for vc++」· HPP 代码 · 共 489 行 · 第 1/2 页

///////////////////////////////////////////////////////////////////////////////
/// \file regex_algorithms.hpp
/// Contains the regex_match(), regex_search() and regex_replace() algorithms.
//
//  Copyright 2004 Eric Niebler. Distributed under the Boost
//  Software License, Version 1.0. (See accompanying file
//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_XPRESSIVE_ALGORITHMS_HPP_EAN_10_04_2005
#define BOOST_XPRESSIVE_ALGORITHMS_HPP_EAN_10_04_2005

// MS compatible compilers support #pragma once
#if defined(_MSC_VER) && (_MSC_VER >= 1020)
# pragma once
#endif

#include <iterator>
#include <boost/xpressive/detail/detail_fwd.hpp>
#include <boost/xpressive/detail/core/state.hpp>
#include <boost/xpressive/detail/utility/save_restore.hpp>

namespace boost { namespace xpressive
{

///////////////////////////////////////////////////////////////////////////////
// regex_match
///////////////////////////////////////////////////////////////////////////////

/// \brief See if a regex matches a sequence from beginning to end.
///
/// Determines whether there is an exact match between the regular expression re,
/// and all of the sequence [begin, end).
///
/// \pre Types BidiIter and OtherBidiIter meet the requirements of a Bidirectional Iterator (24.1.4).
/// \pre OtherBidiIter is convertible to BidiIter.
/// \pre [begin,end) denotes a valid iterator range.
/// \param begin The beginning of the sequence.
/// \param end The end of the sequence.
/// \param what The match_results struct into which the sub_matches will be written
/// \param re The regular expression object to use
/// \param flags Optional match flags, used to control how the expression is matched against the sequence. (See match_flag_type.)
/// \return true if a match is found, false otherwise
/// \throw regex_error on stack exhaustion
template<typename OtherBidiIter, typename BidiIter>
inline bool regex_match
(
    OtherBidiIter begin
  , OtherBidiIter end
  , match_results<BidiIter> &what
  , basic_regex<BidiIter> const &re
  , regex_constants::match_flag_type flags = regex_constants::match_default
)
{
    typedef detail::core_access<BidiIter> access;

    // an invlid regex matches nothing
    if(!access::invalid(re))
    {
        // the state object holds matching state and
        // is passed by reference to all the matchers
        detail::state_type<BidiIter> state(begin, end, what, *access::get_regex_impl(re), flags);
        state.flags_.match_all_ = true;
        state.sub_match(0).begin_ = begin;

        if(access::match(re, state))
        {
            access::set_prefix_suffix(what, begin, end);
            return true;
        }

        // handle partial matches
        else if(state.found_partial_match_ && 0 != (flags & regex_constants::match_partial))
        {
            return state.set_partial_match(), true;
        }
    }

    access::reset(what);
    return false;
}

/// \overload
template<typename OtherBidiIter, typename BidiIter>
inline bool regex_match
(
    OtherBidiIter begin
  , OtherBidiIter end
  , basic_regex<BidiIter> const &re
  , regex_constants::match_flag_type flags = regex_constants::match_default
)
{
    // BUGBUG this is inefficient
    match_results<BidiIter> what;
    return regex_match(begin, end, what, re, flags);
}

/// \overload
template<typename Char>
inline bool regex_match
(
    Char const *begin
  , match_results<Char const*> &what
  , basic_regex<Char const*> const &re
  , regex_constants::match_flag_type flags = regex_constants::match_default
)
{
    // BUGBUG this is inefficient
    Char const *end = begin + std::char_traits<Char>::length(begin);
    return regex_match(begin, end, what, re, flags);
}

/// \overload
template<typename Char, typename Traits, typename Alloc>
inline bool regex_match
(
    std::basic_string<Char, Traits, Alloc> const &str
  , match_results<typename std::basic_string<Char, Traits, Alloc>::const_iterator> &what
  , basic_regex<typename std::basic_string<Char, Traits, Alloc>::const_iterator> const &re
  , regex_constants::match_flag_type flags = regex_constants::match_default
)
{
    return regex_match(str.begin(), str.end(), what, re, flags);
}

/// \overload
template<typename Char>
inline bool regex_match
(
    Char const *begin
  , basic_regex<Char const *> const &re
  , regex_constants::match_flag_type flags = regex_constants::match_default
)
{
    // BUGBUG this is inefficient
    match_results<Char const *> what;
    return regex_match(begin, what, re, flags);
}

/// \overload
template<typename Char, typename Traits, typename Alloc>
inline bool regex_match
(
    std::basic_string<Char, Traits, Alloc> const &str
  , basic_regex<typename std::basic_string<Char, Traits, Alloc>::const_iterator> const &re
  , regex_constants::match_flag_type flags = regex_constants::match_default
)
{
    // BUGBUG this is inefficient
    match_results<typename std::basic_string<Char, Traits, Alloc>::const_iterator> what;
    return regex_match(str, what, re, flags);
}


///////////////////////////////////////////////////////////////////////////////
// regex_search
///////////////////////////////////////////////////////////////////////////////

namespace detail
{
///////////////////////////////////////////////////////////////////////////////
// regex_search_impl
template<typename BidiIter>
inline bool regex_search_impl
(
    state_type<BidiIter> &state
  , basic_regex<BidiIter> const &re
  , bool not_initial_null = false
)
{
    typedef core_access<BidiIter> access;
    typedef typename iterator_value<BidiIter>::type char_type;
    match_results<BidiIter> &what = *state.context_.results_ptr_;

    // an invlid regex matches nothing
    if(!access::invalid(re))
    {
        bool const partial_ok = state.flags_.match_partial_;
        save_restore<bool> not_null(state.flags_.match_not_null_, state.flags_.match_not_null_ || not_initial_null);
        state.flags_.match_prev_avail_ = state.flags_.match_prev_avail_ || !state.bos();

        regex_impl<BidiIter> const &impl = *access::get_regex_impl(re);
        BidiIter const begin = state.cur_, end = state.end_;
        BidiIter &sub0begin = state.sub_match(0).begin_;
        sub0begin = state.cur_;

        // If match_continuous is set, we only need to check for a match at the current position
        if(state.flags_.match_continuous_)
        {
            if(access::match(re, state))
            {
                access::set_prefix_suffix(what, begin, end);
                return true;
            }

            // handle partial matches
            else if(partial_ok && state.found_partial_match_)
            {
                state.set_partial_match();
                return true;
            }
        }

        // If we have a finder, use it to find where a potential match can start
        else if(impl.finder_)
        {
            finder<BidiIter> const &find = *impl.finder_;
            if(find(state))
            {
                if(state.cur_ != begin)
                {
                    not_null.restore();
                }

                do
                {
                    sub0begin = state.cur_;
                    if(access::match(re, state))
                    {
                        access::set_prefix_suffix(what, begin, end);
                        return true;
                    }

                    // handle partial matches
                    else if(partial_ok && state.found_partial_match_)
                    {
                        state.set_partial_match();
                        return true;
                    }

                    BOOST_ASSERT(state.cur_ == sub0begin);
                    not_null.restore();
                }
                while(state.cur_ != state.end_ && (++state.cur_, find(state)));
            }
        }

        // Otherwise, use brute force search at every position.
        else
        {
            for(;;)
            {
                if(access::match(re, state))
                {
                    access::set_prefix_suffix(what, begin, end);
                    return true;