#include <iostream>
#include <boost/proto/proto.hpp>

namespace proto = boost::proto;
namespace mpl = boost::mpl;

namespace detail
{
    struct action_not_found_ {};

    template <typename Actions, typename Rule>
    struct has_action
    {
        typedef char yes;
        typedef struct { char c[2]; } no;

        template <typename A, typename R>
        static yes check(typename A::template when<R, A>::transform_type*);
        template <typename A, typename R>
        static no check(...);

        static const bool value = (sizeof(check<Actions, Rule>(0)) == sizeof(yes));

        typedef mpl::bool_<value> type;
    };
    
    template <typename Actions, typename Grammar, typename Action, typename Expr>
    struct select_action_;

    template <
        typename Actions
      , typename Grammar
      , template <typename, typename> class Action
      , typename Rule
      , typename Expr>
    struct select_action_<Actions, Grammar, Action<Rule, Actions>, Expr>
    {
        typedef
            typename mpl::eval_if<
                mpl::and_<
                    has_action<Actions, Rule>
                  , proto::matches<Expr, Rule>
                >
              , mpl::identity<Action<Rule, Actions> >
              , mpl::identity<action_not_found_>
            >::type
        type;
    };

    template <typename Actions>
    struct fold_actions
       : mpl::fold<
            Actions
          , action_not_found_
          , mpl::if_<
                boost::is_same<
                    mpl::_2
                  , action_not_found_
                >
              , mpl::_1
              , mpl::_2
            >
        >
    {};

#define M0(Z, N, DATA)                                                          \
    typename select_action_<                                                    \
        Actions                                                                 \
      , typename BOOST_PP_CAT(G, N)::proto_grammar                              \
      , typename Actions::template when<                                        \
            BOOST_PP_CAT(G, N), Actions                                         \
        >, Expr                                                                 \
    >::type                                                                     \
    /**/

#define M1(Z, N, DATA)                                                          \
    template <                                                                  \
        typename Actions                                                        \
        BOOST_PP_ENUM_TRAILING_PARAMS(N, typename G)                            \
      , template <typename, typename> class Action                              \
      , typename Rule                                                           \
      , typename Expr>                                                          \
    struct select_action_<                                                      \
        Actions                                                                 \
      , proto::DATA<BOOST_PP_ENUM_PARAMS(N, G)>                                 \
      , Action<Rule, Actions>                                                   \
      , Expr>                                                                   \
    {                                                                           \
        struct hide                                                             \
            : proto::DATA<BOOST_PP_ENUM_PARAMS(N, G)>                           \
        {};                                                                     \
        typedef                                                                 \
            BOOST_PP_CAT(mpl::vector, BOOST_PP_INC(N))<                         \
                typename select_action_<                                        \
                    Actions                                                     \
                  , hide                                                        \
                  , Action<Rule, Actions>                                       \
                  , Expr                                                        \
                >::type                                                         \
              BOOST_PP_ENUM_TRAILING(N, M0, _)                                  \
          >                                                                     \
          actions;                                                              \
        typedef typename fold_actions<actions>::type type;                      \
    };                                                                          \
    /**/

    BOOST_PP_REPEAT(BOOST_PROTO_MAX_LOGICAL_ARITY, M1, or_)
    BOOST_PP_REPEAT(BOOST_PROTO_MAX_LOGICAL_ARITY, M1, and_)

#undef M0
#undef M1
    
    template <
        typename Actions
      , typename Cases
      , template <typename, typename> class Action
      , typename Rule
      , typename Expr>
    struct select_action_<
        Actions
      , proto::switch_<Cases>
      , Action<Rule, Actions>
      , Expr>
    {
        struct hide
            : proto::switch_<Cases>
        {};

        typedef
            typename Cases::template case_<
                typename proto::tag_of<Expr>::type
            >
            case_;

        typedef
            mpl::vector3<
                typename select_action_<
                    Actions
                  , hide
                  , Action<Rule, Actions>
                  , Expr
                >::type
              , typename select_action_<
                    Actions
                  , typename case_::proto_grammar
                  , typename Actions::template when<case_, Actions>
                  , Expr
                >::type
              , typename select_action_<
                    Actions
                  , typename case_::proto_grammar
                  , typename Actions::template when<
                        typename case_::proto_grammar
                      , Actions
                    >
                  , Expr
                >::type
            >
            actions;
        
        typedef typename fold_actions<actions>::type type;
    };
}

template <typename Grammar, typename Actions, typename Expr>
struct select_action
    : detail::select_action_<
        Actions
      , typename Grammar::proto_grammar
      , typename Actions::template when<Grammar, Actions>, Expr
    >
{};

template <typename Grammar, typename Actions>
struct _traverse
    : proto::transform<_traverse<Grammar, Actions> >
{
    template <typename Expr, typename State, typename Data>
    struct impl
      : proto::transform_impl<Expr, State, Data>
    {
        typedef 
            typename select_action<Grammar, Actions, Expr>::type
            action;

        template <typename Action>
        struct result_helper
        {
            typedef
                typename Action::template impl<
                    Expr, State, Data
                >::result_type
                type;
        };

        typedef
            typename mpl::eval_if<
                boost::is_same<
                    action
                  , detail::action_not_found_
                >
              , mpl::identity<Expr>
              , result_helper<action>
            >::type
            result_type;

        result_type operator()(
            typename impl::expr_param   e
          , typename impl::state_param  s
          , typename impl::data_param   d
        ) const
        {
            return invoke(e,s,d, action());
        }

        private:
        template <typename Action>
        result_type invoke(
            typename impl::expr_param   e
          , typename impl::state_param  s
          , typename impl::data_param   d
          , Action
        ) const
        {
            return typename Action::template impl<Expr, State, Data>()(e, s, d);
        }
        
        result_type invoke(
            typename impl::expr_param   e
          , typename impl::state_param  s
          , typename impl::data_param   d
          , detail::action_not_found_
        ) const
        {
            return e;
        }
    };
};

namespace boost { namespace proto
{
    template <typename Grammar, typename Actions>
    struct is_callable<_traverse<Grammar, Actions> > : mpl::true_ {};
}}

template <typename Grammar, typename Actions, typename Expr>
typename
        _traverse<
            Grammar
          , Actions>::template impl<
                Expr const &
              , int
              , int
            >::result_type
traverse(Expr const& expr)
{   
    return
        typename _traverse<
            Grammar
          , Actions>::template impl<
                Expr const &
              , int
              , int
            >()(expr, 0, 0);
}

template <typename DefaultActions>
struct action
{
    template <typename Rule, typename Actions = DefaultActions>
    struct when;
};

struct int_terminal
    : proto::terminal<int>
{};

struct char_terminal
    : proto::terminal<char>
{};

struct my_grammar
    : proto::or_<
        int_terminal
      , char_terminal
      , proto::plus<int_terminal, int_terminal>
    >
{};

struct my_actions;

struct print : proto::callable
{
    typedef std::string result_type;

    result_type operator()(int) const
    {
        return "int";
    }

    result_type operator()(char) const
    {
        return "char";
    }

    template <typename T1, typename T2>
    result_type operator()(T1 const& t1, T2 const& t2) const
    {
        std::string res("");
        res += traverse<my_grammar, my_actions>(t1);
        res += " + ";
        res += traverse<my_grammar, my_actions>(t2);
        return res;
    }
};

struct my_actions
    : action<my_actions>
{
    template <typename Actions>
    struct when<int_terminal, Actions>
        : proto::call<print(proto::_value)>
    {};
    
    template <typename Actions>
    struct when<char_terminal, Actions>
        : proto::call<print(proto::_value)>
    {};
    
    template <typename Actions>
    struct when<proto::plus<int_terminal, int_terminal>, Actions>
        : proto::call<
            print(
                proto::_left
              , proto::_right
            )
        >
    {};
};

int main()
{
    proto::literal<int> i(8), j(9);
    proto::literal<char> a('a'), b('b');

   
    std::cout << traverse<char_terminal, my_actions>(a)  << "\n"; // printing char
    std::cout << traverse<int_terminal, my_actions>(a)   << "\n"; // printing nothing, cause no char terminal in the int_terminal grammar
    std::cout << traverse<char_terminal, my_actions>(i)  << "\n"; // printing nothing, cause no int terminal in char_terminal grammar
    std::cout << traverse<int_terminal, my_actions>(j)   << "\n"; // printing int
    std::cout << traverse<my_grammar, my_actions>(j)     << "\n"; // printing int
    std::cout << traverse<my_grammar, my_actions>(a)     << "\n"; // printing char
    std::cout << traverse<my_grammar, my_actions>(i + i) << "\n"; // printing int + int
}