common.hpp

C++的一个好库。。。现在很流行

//  forward declaration
template <
    typename IteratorT,
    typename NodeFactoryT = node_val_data_factory<nil_t>,
    typename T = nil_t
>
class tree_match;

namespace impl {

    ///////////////////////////////////////////////////////////////////////////
    // can't call unqualified swap from within classname::swap
    // as Koenig lookup rules will find only the classname::swap
    // member function not the global declaration, so use cp_swap
    // as a forwarding function (JM):
#if __GNUC__ == 2
    using ::std::swap;
#endif
    template <typename T>
    inline void cp_swap(T& t1, T& t2)
    {
        using std::swap;
        using boost::spirit::swap;
        using boost::swap;
        swap(t1, t2);
    }
}

//////////////////////////////////
template <typename IteratorT, typename NodeFactoryT, typename T>
class tree_match : public match<T>
{
public:

    typedef typename NodeFactoryT::template factory<IteratorT> node_factory_t;
    typedef typename node_factory_t::node_t parse_node_t;
    typedef tree_node<parse_node_t> node_t;
    typedef typename node_t::children_t container_t;
    typedef typename container_t::iterator tree_iterator;
    typedef typename container_t::const_iterator const_tree_iterator;

    typedef T attr_t;
    typedef typename boost::call_traits<T>::param_type      param_type;
    typedef typename boost::call_traits<T>::reference       reference;
    typedef typename boost::call_traits<T>::const_reference const_reference;

    tree_match()
    : match<T>(), trees()
    {}

    explicit
    tree_match(std::size_t length)
    : match<T>(length), trees()
    {}

    tree_match(std::size_t length, parse_node_t const& n)
    : match<T>(length), trees()
    { 
        trees.reserve(10); // this is more or less an arbitraty number...
        trees.push_back(node_t(n)); 
    }

    tree_match(std::size_t length, param_type val, parse_node_t const& n)
    : match<T>(length, val), trees()
    {
        trees.reserve(10); // this is more or less an arbitraty number...
        trees.push_back(node_t(n));
    }

    // attention, these constructors will change the second parameter!
    tree_match(std::size_t length, container_t& c)
    : match<T>(length), trees()
    { 
        impl::cp_swap(trees, c);
    }

    tree_match(std::size_t length, param_type val, container_t& c)
    : match<T>(length, val), trees()
    {
        impl::cp_swap(trees, c);
    }

    template <typename T2>
    tree_match(match<T2> const& other)
    : match<T>(other), trees()
    {}

    template <typename T2, typename T3, typename T4>
    tree_match(tree_match<T2, T3, T4> const& other)
    : match<T>(other), trees()
    { impl::cp_swap(trees, other.trees); }

    template <typename T2>
    tree_match&
    operator=(match<T2> const& other)
    {
        match<T>::operator=(other);
        return *this;
    }

    template <typename T2, typename T3, typename T4>
    tree_match&
    operator=(tree_match<T2, T3, T4> const& other)
    {
        match<T>::operator=(other);
        impl::cp_swap(trees, other.trees);
        return *this;
    }

    tree_match(tree_match const& x)
    : match<T>(x), trees()
    {
        // use auto_ptr like ownership for the trees data member
        impl::cp_swap(trees, x.trees);
    }

    tree_match& operator=(tree_match const& x)
    {
        tree_match tmp(x);
        this->swap(tmp);
        return *this;
    }

    void swap(tree_match& x)
    {
        match<T>::swap(x);
        impl::cp_swap(trees, x.trees);
    }

    mutable container_t trees;
};

#if defined(BOOST_SPIRIT_DEBUG) && \
    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)
template <typename IteratorT, typename NodeFactoryT, typename T>
inline std::ostream&
operator<<(std::ostream& o, tree_match<IteratorT, NodeFactoryT, T> const& m)
{
    typedef
        typename tree_match<IteratorT, NodeFactoryT, T>::container_t::iterator
        iterator;

    o << "(length = " << (int)m.length();
    int c = 0;
    for (iterator i = m.trees.begin(); i != m.trees.end(); ++i)
    {
        o << " trees[" << c++ << "] = " << *i;
    }
    o << "\n)";
    return o;
}
#endif

//////////////////////////////////
struct tree_policy
{
    template <typename FunctorT, typename MatchT>
    static void apply_op_to_match(FunctorT const& /*op*/, MatchT& /*m*/)
    {}

    template <typename MatchT, typename Iterator1T, typename Iterator2T>
    static void group_match(MatchT& /*m*/, parser_id const& /*id*/,
            Iterator1T const& /*first*/, Iterator2T const& /*last*/)
    {}

    template <typename MatchT>
    static void concat(MatchT& /*a*/, MatchT const& /*b*/)
    {}
};

//////////////////////////////////
template <
    typename MatchPolicyT,
    typename IteratorT,
    typename NodeFactoryT,
    typename TreePolicyT
>
struct common_tree_match_policy : public match_policy
{
    template <typename T>
    struct result { typedef tree_match<IteratorT, NodeFactoryT, T> type; };

    typedef tree_match<IteratorT, NodeFactoryT> match_t;
    typedef IteratorT iterator_t;
    typedef TreePolicyT tree_policy_t;
    typedef NodeFactoryT factory_t;

    static const match_t no_match() { return match_t(); }
    static const match_t empty_match()
    { return match_t(0, tree_policy_t::empty_node()); }

    template <typename AttrT, typename Iterator1T, typename Iterator2T>
    static tree_match<IteratorT, NodeFactoryT, AttrT> create_match(
        std::size_t length,
        AttrT const& val,
        Iterator1T const& first,
        Iterator2T const& last)
    {
#if defined(BOOST_SPIRIT_DEBUG) && \
    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)

        BOOST_SPIRIT_DEBUG_OUT << "\n>>> create_node(begin) <<<\n" 
            "creating node text: \"";
        for (Iterator1T it = first; it != last; ++it)
            impl::token_printer(BOOST_SPIRIT_DEBUG_OUT, *it);
        BOOST_SPIRIT_DEBUG_OUT << "\"\n";
        BOOST_SPIRIT_DEBUG_OUT << ">>> create_node(end) <<<\n\n"; 
#endif
        return tree_match<IteratorT, NodeFactoryT, AttrT>(length, val,
            tree_policy_t::create_node(length, first, last, true));
    }

    template <typename Match1T, typename Match2T>
    static void concat_match(Match1T& a, Match2T const& b)
    {
#if defined(BOOST_SPIRIT_DEBUG) && \
    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_NODES)

        BOOST_SPIRIT_DEBUG_OUT << "\n>>> concat_match(begin) <<<\n";
        BOOST_SPIRIT_DEBUG_OUT << "tree a:\n" << a << "\n";
        BOOST_SPIRIT_DEBUG_OUT << "tree b:\n" << b << "\n";
        BOOST_SPIRIT_DEBUG_OUT << ">>> concat_match(end) <<<\n\n";
#endif
        BOOST_SPIRIT_ASSERT(a && b);
        if (a.length() == 0)
        {
            a = b;
            return;
        }
        else if (b.length() == 0
#ifdef BOOST_SPIRIT_NO_TREE_NODE_COLLAPSING
            && !b.trees.begin()->value.id().to_long()
#endif
            )
        {
            return;
        }
        a.concat(b);
        tree_policy_t::concat(a, b);
    }

    template <typename MatchT, typename IteratorT2>
    void
    group_match(
        MatchT&             m,
        parser_id const&    id,
        IteratorT2 const&   first,
        IteratorT2 const&   last) const
    {
        if (!m) return;
        
#if defined(BOOST_SPIRIT_DEBUG) && \
    (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_TREES)

        BOOST_SPIRIT_DEBUG_OUT << "\n>>> group_match(begin) <<<\n"
            "new node(" << id << ") \"";
        for (IteratorT2 it = first; it != last; ++it)
            impl::token_printer(BOOST_SPIRIT_DEBUG_OUT, *it);
        BOOST_SPIRIT_DEBUG_OUT << "\"\n";
        BOOST_SPIRIT_DEBUG_OUT << "new child tree (before grouping):\n" << m << "\n";

        tree_policy_t::group_match(m, id, first, last);

        BOOST_SPIRIT_DEBUG_OUT << "new child tree (after grouping):\n" << m << "\n";
        BOOST_SPIRIT_DEBUG_OUT << ">>> group_match(end) <<<\n\n";
#else
        tree_policy_t::group_match(m, id, first, last);
#endif
    }
};

//////////////////////////////////
template <typename MatchPolicyT, typename NodeFactoryT>
struct common_tree_tree_policy
{
    typedef typename MatchPolicyT::iterator_t iterator_t;
    typedef typename MatchPolicyT::match_t match_t;
    typedef typename NodeFactoryT::template factory<iterator_t> factory_t;
    typedef typename factory_t::node_t node_t;

    template <typename Iterator1T, typename Iterator2T>
        static node_t
        create_node(std::size_t /*length*/, Iterator1T const& first,
            Iterator2T const& last, bool leaf_node)
    {
        return factory_t::create_node(first, last, leaf_node);
    }

    static node_t
        empty_node()
    {
        return factory_t::empty_node();
    }

    template <typename FunctorT>
        static void apply_op_to_match(FunctorT const& op, match_t& m)
    {
        op(m);
    }
};

//////////////////////////////////
// directives to modify how the parse tree is generated

struct no_tree_gen_node_parser_gen;

template <typename T>
struct no_tree_gen_node_parser
:   public unary<T, parser<no_tree_gen_node_parser<T> > >
{
    typedef no_tree_gen_node_parser<T> self_t;
    typedef no_tree_gen_node_parser_gen parser_generator_t;
    typedef unary_parser_category parser_category_t;
//    typedef no_tree_gen_node_parser<T> const &embed_t;

    no_tree_gen_node_parser(T const& a)
    : unary<T, parser<no_tree_gen_node_parser<T> > >(a) {}

    template <typename ScannerT>
    typename parser_result<self_t, ScannerT>::type
    parse(ScannerT const& scanner) const
    {
        typedef typename ScannerT::iteration_policy_t iteration_policy_t;
        typedef match_policy match_policy_t;
        typedef typename ScannerT::action_policy_t action_policy_t;
        typedef scanner_policies<
            iteration_policy_t,
            match_policy_t,
            action_policy_t
        > policies_t;

        return this->subject().parse(scanner.change_policies(policies_t(scanner)));
    }
};

//////////////////////////////////
struct no_tree_gen_node_parser_gen
{
    template <typename T>
    struct result {

        typedef no_tree_gen_node_parser<T> type;
    };

    template <typename T>
    static no_tree_gen_node_parser<T>
    generate(parser<T> const& s)
    {
        return no_tree_gen_node_parser<T>(s.derived());
    }

    template <typename T>
    no_tree_gen_node_parser<T>
    operator[](parser<T> const& s) const
    {
        return no_tree_gen_node_parser<T>(s.derived());
    }
};

//////////////////////////////////
const no_tree_gen_node_parser_gen no_node_d = no_tree_gen_node_parser_gen();


//////////////////////////////////
namespace impl {

    template <typename MatchPolicyT>
    struct tree_policy_selector
    {
        typedef tree_policy type;
    };

} // namespace impl

//////////////////////////////////
template <typename NodeParserT>
struct node_parser_gen;

template <typename T, typename NodeParserT>
struct node_parser
:   public unary<T, parser<node_parser<T, NodeParserT> > >
{
    typedef node_parser<T, NodeParserT> self_t;
    typedef node_parser_gen<NodeParserT> parser_generator_t;
    typedef unary_parser_category parser_category_t;
//    typedef node_parser<T, NodeParserT> const &embed_t;

    node_parser(T const& a)
    : unary<T, parser<node_parser<T, NodeParserT> > >(a) {}

    template <typename ScannerT>
    typename parser_result<self_t, ScannerT>::type
    parse(ScannerT const& scanner) const
    {
        typename parser_result<self_t, ScannerT>::type hit = this->subject().parse(scanner);
        if (hit)
        {
            impl::tree_policy_selector<typename ScannerT::match_policy_t>::type::apply_op_to_match(NodeParserT(), hit);
        }
        return hit;
    }
};

//////////////////////////////////
template <typename NodeParserT>
struct node_parser_gen
{
    template <typename T>
    struct result {

        typedef node_parser<T, NodeParserT> type;
    };

    template <typename T>
    static node_parser<T, NodeParserT>
    generate(parser<T> const& s)
    {
        return node_parser<T, NodeParserT>(s.derived());
    }

    template <typename T>
    node_parser<T, NodeParserT>
    operator[](parser<T> const& s) const
    {
        return node_parser<T, NodeParserT>(s.derived());
    }
};

struct discard_node_op
{
    template <typename MatchT>
    void operator()(MatchT& m) const
    {
        m.trees.clear();
    }
};

const node_parser_gen<discard_node_op> discard_node_d =
    node_parser_gen<discard_node_op>();

struct leaf_node_op
{
    template <typename MatchT>
    void operator()(MatchT& m) const
    {
        if (m.trees.size() == 1)
        {
            m.trees.begin()->children.clear();
        }
        else if (m.trees.size() > 1)
        {
            typedef typename MatchT::node_factory_t node_factory_t;
            m = MatchT(m.length(), node_factory_t::group_nodes(m.trees));
        }
    }
};

const node_parser_gen<leaf_node_op> leaf_node_d =
    node_parser_gen<leaf_node_op>();
const node_parser_gen<leaf_node_op> token_node_d =
    node_parser_gen<leaf_node_op>();

struct infix_node_op
{
    template <typename MatchT>
    void operator()(MatchT& m) const
    {
        typedef typename MatchT::container_t container_t;
        typedef typename MatchT::container_t::iterator iter_t;
        typedef typename MatchT::container_t::value_type value_t;

        using std::swap;
        using boost::swap;
        using boost::spirit::swap;

        // copying the tree nodes is expensive, since it may copy a whole
        // tree.  swapping them is cheap, so swap the nodes we want into
        // a new container of children.
        container_t new_children;
        std::size_t length = 0;
        std::size_t tree_size = m.trees.size();

        // the infix_node_d[] make no sense for nodes with no subnodes
        BOOST_SPIRIT_ASSERT(tree_size >= 1);

        bool keep = true;
        new_children.reserve((tree_size+1)/2);
        iter_t i_end = m.trees.end();
        for (iter_t i = m.trees.begin(); i != i_end; ++i)
        {