Background question: boost.proto + modify expression tree in place
Hi, consider the following transform to extract the value_type from a vector_expr (see previous questions)
template <class T> struct value_type_trait;
template <std::size_t D, class T>
struct value_type_trait<vector<D, T> >
{
typedef typename vector<D, T>::value_type type;
};
struct deduce_value_type
: proto::or_<
proto::when <vector_terminal, value_type_trait<proto::_value>() >
, proto::when <scalar_terminal, proto::_value>
, proto::otherwise <
proto::_default<deduce_value_type>()
>
>
{};
The above code can be used to provide 'maximal' value_type to the expression tree, which is obtained applying the usual C++ promotion rules and Boost.TypeOf magic. The above is used as follows
template <class Expr>
struct vector_expr : proto::extends <Expr, vector_expr <Expr>, vector_domain>
{
typedef proto::extends <Expr, vector_expr <Expr>, vector_domain> base_type;
// OK! now my expression has a 'value_type'
typedef typename boost::result_of<deduce_value_type(Expr)>::type value_type;
vector_expr (Expr const &e) : base_type (e) {}
};
But now, the following code (check previous question: boost.proto + modify expression tree in place and the code in the accepted answer) is broken (with the usual humongous template instantiation error backtrace, for my pleasure)
int main ()
{
double data[] = {1, 2, 3};
vector<3, double> a(data, data+3), b(data,data+3), c(data,data+3);
auto iter = vector_begin_algo()(a + b);
return 0;
}
The reason is simple. The type of typename boost::result_of<vector_begin_algo(a+b)>::type is:
vector_expr<
basic_expr<
tag::plus
, list2< expr<tag::terminal, term<vector_iterator<double*> >, 0l>
, expr<tag::terminal, term<vector_iterator<double*> >, 0l>
>
,
2l>
>
So, the external vector_expr<...> triggers the evaluation of the nested value_type, but the deduce_value_type algorithm doesn't know how to extract the nested value_type from vector_iterator<double*>. One solution is to define a new traits and modify deduce_value_type as follows
// A further trait
template <class Iter>
struct value_type_trait<vector_iterator<Iter> >
{
typedef typename std::iterator_traits<Iter>::value_type type;
};
// Algorithm to deduce the value type of an expression.
struct deduce_value_type
: proto::or_<
proto::when <vector_terminal, value_type_trait<proto::_value>() >
, proto::when <scalar_terminal, proto::_value>
, proto::when <proto::terminal<vector_iterator<proto::_> > , value_type_trait<proto::_value>()> // <- need this now
, proto::otherwise <
proto::_default<deduce_value_type>()
>
>
{};
There are several problems with this approach, but the most important is: for each typedef or static constant that i find convenient defining in the vector_expr struct, I will need to perform all the above only to have the expression compile, even if an iterator-expression IS-NOT vector-expression and it makes no sense to enlarge the interface of vector_expr to accommodate transformed trees.
The question is: there is a way to transform the vector_expr tree, converting vector nodes into iterator nodes, while at the same time removing the vector-ness from the tree itself so that i do not incur in the above problems?
Thanks in advance, best regards!
UPDATE Sorry, i changed the last part of the question now that my mind is more clear about what (i think) should be achieved. In the meantime, i tried to solve the thing by myself with a partial success (?), but I feel that there should be a better way (so I still need help!).
It seems to me that the problems come from having all the tree nodes wrapped in the vector_expr thing, that has the side-effect of putting requirement on the terminals (mainly the static stuff for successfully compiling). OTOH, once a valid vector_exp has been constructed (namely: obeying the vector_grammar), then i can transform it to a valid iterator_tree without further checks.
I tried to create a transform that changes back all vector_expr nodes in a tree into 'proto::expr'. The code is as follows:
template <class Expr, long Arity = Expr::proto_arity_c>
struct deep_copy_unwrap_impl;
template <class Expr>
struct deep_copy_unwrap_impl <Expr,0>
{
typedef typename proto::tag_of <Expr>::type Tag;
typedef typename proto::result_of::value<Expr>::type A0;
typedef typename proto::result_of::make_expr<Tag, proto::default_domain, A0>::type result_type;
template<typename Expr2, typename S, typename D>
result_type operator()(Expr2 const &e, S const &, D const &) const
{
return proto::make_expr <Tag, proto::default_domain> (e.proto_base().child0);
}
};
template <class Expr>
struct deep_copy_unwrap_impl <Expr,1>
{
typedef typename proto::tag_of <Expr>::type Tag;
typedef typename proto::result_of::child_c<Expr, 0>::type A0;
typedef typename proto::result_of::make_expr<Tag, proto::default_domain, A0>::type result_type;
template<typename Expr2, typename S, typename D>
result_type operator()(Expr2 const &e, S const &, D const &) const
{
return proto::make_expr <Tag, proto::default_domain> (e.proto_base().child0);
}
};
template <class Expr>
struct deep_copy_unwrap_impl <Expr,2>
{
typedef typename proto::tag_of <Expr>::type Tag;
typedef typename proto::result_of::child_c<Expr, 0>::type A0;
typedef typename proto::result_of::child_c<Expr, 1>::type A1;
typedef typename proto::result_of::make_expr<Tag, proto::default_domain, A0, A1>::type result_type;
template<typename Expr2, typename S, typename D>
result_type operator()(Expr2 const &e, S const &, D const &) const
{
return proto::make_expr <Tag, proto::default_domain> (e.proto_base().child0, e.proto_base().child1);
}
};
struct unwrap : proto::callable
{
template <class Sig> struct result;
template <class This, class Expr>
struct result <This(Expr)>
{
typedef typename
deep_copy_unwrap_impl <Expr>
::result_type type;
};
template <class This, class Expr>
struct result <This(Expr&)>
: result<This(Expr)> {};
template <class This, class Expr>
struct result <This(Expr const&)>
: result<This(Expr)> {};
template <class Expr>
typename result <unwrap(Expr)>::type
operator () (Expr const &e) const
{
return deep_copy_unwrap_impl<Expr>()(e, 0, 0);
}
};
struct retarget
: proto::otherwise <
unwrap(proto::nary_expr<proto::_, proto::vararg<retarget> >)
>
{};
int main ()
{
int data[] = {1, 2, 3};
vector<3, int> a(data, data+3), b(data,data+3), c(data,data+3);
auto x=a+b+c; // <- x is an expression tree made up of vector_expr<...> nodes
auto y=retarget()(x); // <- y is an expression tree made up of proto::expr<...> nodes
return 0;
}
The problem you're running into is that Proto's pass_through transform creates new expressions that are in the same domain as the original. This happens in your vector_begin_algo algorithm, in the otherwise clause. You don't want this, but it's what pass_through gives you. You have two strategies: don't use pass_through, or trick pass_through into building an expression in the default domain.
If you're using the latest version of Proto (1.51), you can use make_expr and an unpacking expression instead of pass_through:
// Turn all vector terminals into vector iterator terminals
struct vector_begin_algo
: proto::or_<
proto::when<
proto::terminal<std::vector<_, _> >
, proto::_make_terminal(
vector_iterator<begin(proto::_value)>(begin(proto::_value))
)
>
, proto::when<
proto::terminal<_>
, proto::_make_terminal(proto::_byval(proto::_value))
>
, proto::otherwise<
proto::lazy<
proto::functional::make_expr<proto::tag_of<_>()>(
vector_begin_algo(proto::pack(_))...
)
>
>
>
{};
proto::lazy is needed here because you first need to build the make_expr function object before you can invoke it. It's not a thing of beauty, but it works.
If you are using an older version of Proto, you can get the same effect by tricking pass_through by first removing the domain-specific wrapper from your expression. First, I write a callable to strip the domain-specific wrapper:
struct get_base_expr
: proto::callable
{
template<typename Expr>
struct result;
template<typename This, typename Expr>
struct result<This(Expr)>
{
typedef
typename boost::remove_reference<Expr>::type::proto_base_expr
type;
};
template<typename Expr>
typename Expr::proto_base_expr operator()(Expr const &expr) const
{
return expr.proto_base();
}
};
Then, the vector_begin_algo would be changed as follows:
// Turn all vector terminals into vector iterator terminals
struct vector_begin_algo
: proto::or_<
proto::when<
proto::terminal<std::vector<_, _> >
, proto::_make_terminal(
vector_iterator<begin(proto::_value)>(begin(proto::_value))
)
>
, proto::when<
proto::terminal<_>
, proto::_make_terminal(proto::_byval(proto::_value))
>
, proto::otherwise<
proto::_byval(proto::pass_through<
proto::nary_expr<_, proto::vararg<vector_begin_algo> >
>(get_base_expr(_)))
>
>
{};
This is also not a work of art, but it gets the job done. Don't forget the proto::_byval to work around the const weirdness in the pass_through transform (which is fixed is boost trunk and will be in 1.52, btw).
I can think of one final solution that takes advantage of the fact that Proto expressions are Fusion sequences of their children. You create a Fusion transform_view that wraps the expression and transforms each child with vector_begin_algo. That gets passed to proto::functional::unpack_expr, much like in the first example with make_expr. You'd need proto::lazy there also, for the same reason.
Thanks for pointing out this limitation on Proto's built-in pass_through transform. It'd be good to have a nicer way to do this.