[MPL] Runtime traversal of a type sequence until a condition is true
I'm interested in taking Andrei Alexandrescu's Ad Hoc Visitor technique (http://tinyurl.com/2k8h2h) and implementing it using the MPL. I need to implement a runtime function that iterates over an MPL type sequence until a dynamic_cast succeeds. Here's some pseudocode, where I use "typelist" to mean an MPL type sequence: class UnknownType { ... }; // for exceptions template <typename TL> // TL = "typelist" void visit(ASTNode *pn) { for (each type T in TL) { // try dynamic_ if (T *pT = dynamic_cast<T*>(pn)) { // casting to all v.process(pT); // the types in TL return; } throw UnknownType(typeid(*pn)); // throw an ex. if } // no type matches I can make this work if I replace the for loop with a use of mpl::for_each, but for_each iterates over all elements of the type sequence, and I want to stop when a dynamic_cast succeeds. I can hack the function object I pass to for_each to have it be a no-op once a successful dynamic_cast has been encountered, but the operative word there is "hack." What I really want is something more like do_until<Sequence>(unaryFunctionObject) that will loop over all the entries in Sequence until the unaryFunctionObject returns true. Is there something like this in the MPL, must I roll my own, or am I approaching this the wrong way entirely? Thanks, Scott
Scott Meyers ha escrito:
I'm interested in taking Andrei Alexandrescu's Ad Hoc Visitor technique (http://tinyurl.com/2k8h2h) and implementing it using the MPL. I need to implement a runtime function that iterates over an MPL type sequence until a dynamic_cast succeeds. Here's some pseudocode, where I use "typelist" to mean an MPL type sequence:
class UnknownType { ... }; // for exceptions
template <typename TL> // TL = "typelist" void visit(ASTNode *pn) { for (each type T in TL) { // try dynamic_ if (T *pT = dynamic_cast<T*>(pn)) { // casting to all v.process(pT); // the types in TL return; }
throw UnknownType(typeid(*pn)); // throw an ex. if } // no type matches
I can make this work if I replace the for loop with a use of mpl::for_each, but for_each iterates over all elements of the type sequence, and I want to stop when a dynamic_cast succeeds. I can hack the function object I pass to for_each to have it be a no-op once a successful dynamic_cast has been encountered, but the operative word there is "hack."
What I really want is something more like do_until<Sequence>(unaryFunctionObject) that will loop over all the entries in Sequence until the unaryFunctionObject returns true. Is there something like this in the MPL, must I roll my own, or am I approaching this the wrong way entirely?
AFAIK you must roll your own. Please find attached a possible implementation using mpl::fold. HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquín Mª López Muñoz wrote:
Scott Meyers ha escrito:
[...]
What I really want is something more like do_until<Sequence>(unaryFunctionObject) that will loop over all the entries in Sequence until the unaryFunctionObject returns true. Is there something like this in the MPL, must I roll my own, or am I approaching this the wrong way entirely?
AFAIK you must roll your own. Please find attached a possible implementation using mpl::fold.
This is unnecessarily inefficient. It's pretty easy to just use iterators, something like: template <class First, class Last, class F> bool do_until_impl(First, Last, F f) { boost::value_initialized<typename mpl::deref<First>::type> x; if (f(boost::get(x))) return true; return do_until_impl( typename mpl::next<First>::type(), Last(), f); } template <class Last, class F> bool do_until_impl(Last, Last, F) { return false; } template <class Seq, class F> bool do_until(F f) { return do_until_impl( typename mpl::begin<Seq>::type() , typename mpl::end<Seq>::type() , f ); } -- Daniel Wallin Boost Consulting www.boost-consulting.com
Daniel Wallin ha escrito:
Joaquín Mª López Muñoz wrote:
Scott Meyers ha escrito:
[...]
What I really want is something more like do_until<Sequence>(unaryFunctionObject) that will loop over all the entries in Sequence until the unaryFunctionObject returns true. Is there something like this in the MPL, must I roll my own, or am I approaching this the wrong way entirely?
AFAIK you must roll your own. Please find attached a possible implementation using mpl::fold.
This is unnecessarily inefficient. It's pretty easy to just use iterators, something like:
[...] So nice! Yep, this is much clearer, I guess I've got a case of fold-obsession :) Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Daniel Wallin wrote:
This is unnecessarily inefficient. It's pretty easy to just use iterators, something like:
template <class First, class Last, class F> bool do_until_impl(First, Last, F f) { boost::value_initialized<typename mpl::deref<First>::type> x;
Does this not require that mpl::deref<First>::type be default-constructable? Presumably this is the first type in my type sequence, and since I'm dynamic_casting to all types in the sequence, it's not unreasonable to assume that the type I'm casting to may be abstract. Will this work if my sequence consists of abstract types? And even if the type is concrete, I can't, in general, know anything about constructing it, i.e., I can't know if it can be value-constructed. It's entirely possible that I'm missing something important here. I'd never seen value_initialized before, and the documentation at http://www.boost.org/libs/utility/value_init.htm is rather dense going.
if (f(boost::get(x))) return true;
This is passing a runtime parameter to f, but what I want to pass to f is a compile-time type -- the type to dynamically_cast to. The pointer I'm casting is fixed, so I can bind it into f when I create f. Am I just missing something? Thanks, Scott
Scott Meyers wrote: <...>
This is passing a runtime parameter to f, but what I want to pass to f is a compile-time type -- the type to dynamically_cast to. The pointer I'm casting is fixed, so I can bind it into f when I create f. Am I just missing something?
Here is a modified version of Daniel's code to suit the case from your original post (seems it wasn't intended to be a complete solution but rather a tutorial on how to implement the recursively inlined iteration with the MPL). Regards, Tobias #include <iostream> #include <boost/mpl/vector.hpp> #include <boost/mpl/begin_end.hpp> #include <boost/mpl/next.hpp> #include <boost/mpl/deref.hpp> namespace mpl = boost::mpl; // a toy model namespace ast { class node { public: virtual ~node() { }; }; class expression_node : public node { }; class literal : public expression_node { }; class operator_node : public node { }; class unary_operator : public operator_node { }; class binary_operator : public operator_node { }; class statement_node : public node { }; class for_loop : public statement_node { }; } // a toy visitor struct ast_visitor { typedef mpl::vector<ast::expression_node, ast::operator_node> accepted_types; void operator()(ast::expression_node &) { std::cout << "got an expression_node" << std::endl; } void operator()(ast::operator_node &) { std::cout << "got an operator_node" << std::endl; } }; // visit facility namespace detail { template <class Last, class Visitor> bool visit(Last, Last, ast::node *, Visitor &) { throw "bummer"; } template <class First, class Last, class Visitor> bool visit(First, Last, ast::node * node, Visitor & v) { typedef typename mpl::deref<First>::type type; type * typed_node = dynamic_cast<type *>(node); if (! typed_node) detail::visit(typename mpl::next<First>::type(), Last(), node, v); else v(*typed_node); } } template<class Visitor> bool visit(ast::node * node, Visitor & with_visitor) { typedef typename Visitor::accepted_types seq; return detail::visit( typename mpl::begin<seq>::type() , typename mpl::end<seq>::type() , node, with_visitor ); } int main() { ast_visitor v; { ast::literal test; visit(& test, v); } { ast::unary_operator test; visit(& test, v); } { ast::binary_operator test; visit(& test, v); } { try { ast::for_loop test; visit(& test, v); } catch(...) { std::cout << "error handling works" << std::endl; } } return 0; }
Rereading my quick post from yesterday I notice: The visit facility could be generalized further to deduce the base type, so 'visit' is not limited to 'ast::node' arguments. We can also change the interface of 'visit' to hide all the pointers from the user (taking a reference instead and applying boost::addressof in case operator& is overloaded): namespace detail { template <class Last, class T, class Visitor> bool visit(Last, Last, T *, Visitor &) { throw "bummer"; } template <class First, class Last, class T, class Visitor> bool visit(First, Last, T * object, Visitor & v) { typedef typename mpl::deref<First>::type type; type * typed_object = dynamic_cast<type *>(object); if (! typed_object) detail::visit( typename mpl::next<First>::type() , Last() , object , v ); else v(*typed_object); } } template<class T, class Visitor> bool visit(T & object, Visitor & with_visitor) { typedef typename Visitor::accepted_types seq; return detail::visit( typename mpl::begin<seq>::type() , typename mpl::end<seq>::type() , boost::addressof(object) , with_visitor ); } Regards, Tobias
Scott Meyers wrote:
Daniel Wallin wrote:
This is unnecessarily inefficient. It's pretty easy to just use iterators, something like:
template <class First, class Last, class F> bool do_until_impl(First, Last, F f) { boost::value_initialized<typename mpl::deref<First>::type> x;
Does this not require that mpl::deref<First>::type be default-constructable? Presumably this is the first type in my type sequence, and since I'm dynamic_casting to all types in the sequence, it's not unreasonable to assume that the type I'm casting to may be abstract. Will this work if my sequence consists of abstract types? And even if the type is concrete, I can't, in general, know anything about constructing it, i.e., I can't know if it can be value-constructed.
I'm certainly not an MPL expert, but as far as I understand, the same problem exists in mpl::for_each. The unary functor passed to mpl::for_each looks like: struct F { template <typename T> void operator()(T) { .... } }; mpl::for_each<seq>(F()); so T is deduced by the argument being passed. T is constructed (probably default constructed) and then sent to the functor. Since we usually don't want to instantiate the types in the MPL sequence, we use a transform meta-function. Something like: struct F { template <typename T> void operator()(mpl::identity<T>) { .... } }; mpl::for_each<seq, mpl::make_identity<_> >(F()); and then the T's being instantiated are not the types in the sequence, but mpl::identity<> of the types in the sequence, which is much better. The solution proposed here could probably be extended to support transform meta-functions just like mpl::for_each does, and the problem is solved. I sure hope this (or similar) mpl::for_each_until will be added to MPL. I also find it useful. As I said, I'm not an expert, so I hope I'm not misleading anyone here...
participants (5)
-
Daniel Wallin -
Joaquín Mª López Muñoz -
Scott Meyers -
Tobias Schwinger -
Yuval Ronen