[mpl] Hierarchy Generation
I have a set of types representing features code might have, e.g., typedef mpl::vector<ExceptionSafe, ThreadSafe, ReallyFast, GPLed> Features; These can occur in any combination as sets of features, e.g., tyepdef FeatureSet<ExceptionSafe> F1; typedef FeatureSet<ThreadSafe, ExceptionSafe> F2; typedef FeatureSet<ReallyFast, ExceptionSafe, GPLed> F3; There should be an implicit conversion from one FeatureSet to another if and only if we don't lose any features in the conversion. So converting from F1 to F2 or F3 is okay (since both F2 and F3 contain ExceptionSafe), but converting from F2 to F3 is not okay (because we'd lose ThreadSafe). Furthermore, a conversion that adds fewer features is preferable to one that adds more, so the conversion from F1 to F2 is better than the conversion from F1 to F3 (because the former adds only one feature while the latter adds two). I'm looking for a way to automatically generate an inheritance hierarchy that will give me the behavior I've described. For the above example, the hierarchy has four levels. The root is all the features, because any subset of features is permitted to be implicitly convertible to the set of all features. Root: FeatureSet<ExceptionSafe, ThreadSafe, ReallyFast, GPLed> The leaves are the individual features: Leaves: FeatureSet<ExceptionSafe> FeatureSet<ThreadSafe> FeatureSet<ReallyFast> FeatureSet<GPLed> The next level up is pairs of features: One level FeatureSet<ExceptionSafe, ThreadSafe> up from FeatureSet<ExceptionSafe, ReallyFast> leaves: FeatureSet<ExceptionSafe, GPLed> ... The next level up (which is one below the root) is triplets of features: One level FeatureSet<ExceptionSafe, ThreadSafe, ReallyFast> down from FeatureSet<ExceptionSafe, ThreadSafe, GPLed> root: FeatureSet<ExceptionSafe, ReallyFast, GPLed> ... In general, given a list of n features, I need a hierarchy n levels deep, with one class at the root, n classes at the leaves, and m-wise combinations of the n features at the intervening levels (where m varies from 2 to n-1). Fortunately, I don't need to worry about permutations of the ordering of the features, because I already have a way to canonically order them. (Not a great way, but it works, and that's a different problem.) Is there some way for me to use the MPL to automatically generate the hierarchy I need? Thanks, Scott
AMDG Scott Meyers wrote:
I have a set of types representing features code might have, e.g.,
typedef mpl::vector<ExceptionSafe, ThreadSafe, ReallyFast, GPLed> Features;
These can occur in any combination as sets of features, e.g.,
tyepdef FeatureSet<ExceptionSafe> F1; typedef FeatureSet<ThreadSafe, ExceptionSafe> F2; typedef FeatureSet<ReallyFast, ExceptionSafe, GPLed> F3; <snip>
I'm looking for a way to automatically generate an inheritance hierarchy that will give me the behavior I've described. For the above example, the hierarchy has four levels. The root is all the features, because any subset of features is permitted to be implicitly convertible to the set of all features.
Root: FeatureSet<ExceptionSafe, ThreadSafe, ReallyFast, GPLed>
The leaves are the individual features:
Leaves: FeatureSet<ExceptionSafe> FeatureSet<ThreadSafe> FeatureSet<ReallyFast> FeatureSet<GPLed> <snip>
Is there some way for me to use the MPL to automatically generate the hierarchy I need?
Thanks,
Scott
There's nothing that works out of the box. Here's a quick hack: #include <boost/mpl/begin.hpp> #include <boost/mpl/end.hpp> #include <boost/mpl/empty_base.hpp> #include <boost/mpl/erase.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/copy.hpp> #include <boost/mpl/assert.hpp> #include <boost/mpl/size.hpp> #include <boost/mpl/int.hpp> #include <boost/mpl/not_equal_to.hpp> #include <boost/mpl/eval_if.hpp> #include <boost/mpl/identity.hpp> #include <boost/type_traits/is_base_and_derived.hpp> namespace mpl = boost::mpl; template<class T1, class T2=void> struct virtual_inherit : virtual T1, virtual T2 {}; template<class T1> struct virtual_inherit<T1, void> : virtual T1 {}; template<class S> struct make_features; template<class S, class Iter = typename mpl::begin<S>::type> struct make_features_base { typedef typename make_features<typename mpl::erase<S, Iter>::type>::type item; typedef typename make_features_base<S, typename mpl::next<Iter>::type>::type next; typedef virtual_inherit<next, item> type; }; template<class S> struct make_features_base<S, typename mpl::end<S>::type> { typedef virtual_inherit<mpl::empty_base> type; }; template<class S> struct features : virtual mpl::eval_if<mpl::not_equal_to<mpl::size<S>, mpl::int_<1> >, make_features_base<S>, mpl::identity<virtual_inherit<mpl::empty_base> > >::type {}; template<class S> struct make_features { typedef features<typename mpl::copy<S, mpl::back_inserter<mpl::vector0<> > >::type> type; }; int main() { typedef make_features<mpl::vector<int, char, double> >::type f1; typedef make_features<mpl::vector<int, double> >::type f2; typedef make_features<mpl::vector<char> >::type f3; BOOST_MPL_ASSERT((boost::is_base_and_derived<f2, f1>)); BOOST_MPL_ASSERT((boost::is_base_and_derived<f3, f1>)); } In Christ, Steven Watanabe
I don't know whether it is important for Scott, but the following example is failed to compile. .............. int main() { typedef make_features<mpl::vector<int, char, double> >::type f1; typedef make_features<mpl::vector<double, int> >::type f4; BOOST_MPL_ASSERT((boost::is_base_and_derived<f4, f1>)); } In other words the order of "features" is taken into account.
Steven Watanabe wrote:
typedef make_features<mpl::vector<int, char, double> >::type f1; typedef make_features<mpl::vector<int, double> >::type f2; typedef make_features<mpl::vector<char> >::type f3; BOOST_MPL_ASSERT((boost::is_base_and_derived<f2, f1>)); BOOST_MPL_ASSERT((boost::is_base_and_derived<f3, f1>));
Sorry for taking so long to reply, but TMP always makes my head explode, and it takes a while to pick up the pieces and put them back together. In this case, I could have saved myself the explosion, because this interface offers behavior that is backwards from what I want. The conversion I want to allow is from fewer features to more, so I don't want f2 and f3 to be bases of f1, I want f1 to be a base for both f2 and f3. My current thinking is that this can't be done without knowing all possible features, so I'm thinking about an approach where I first define that: typedef mpl::vector< ... > AllPossibleFeatures; What I then want to define is template<typename MyFeatures> // sequence of features struct Features... subject to the following: typedef difference<AllFeatures, MyFeatures> TypesToAdd; // Features in // AllFeatures that // are not in // MyFeatures For each type T in TypesToAdd, Features<MyFeatures> virtually inherits from Features<insert<MyFeatures,T>::type>. So given typedef mpl::vector<int, char, double> AllPossibleFeatures; Features<mpl::vector<int>> (C++0x says I can omit the space between angle brackets :-}) would virtually inherit from Features<mpl::vector<int, char>> and Features<mpl::vector<int, double>. In turn, Features<mpl::vector<int, char>> and Features<mpl::vector<int, double>> would both virtually inherit from Features<mpl::vector<int, char, double>. I can write the difference metafunction above and I can write a rotate metafunction to help me iterate through all the types in the difference set. What I don't know is a good way to give Features<T> the appropriate number of virtual base classes. Can somebody help? Thanks, Scott
AMDG Scott Meyers wrote:
Steven Watanabe wrote:
typedef make_features<mpl::vector<int, char, double> >::type f1; typedef make_features<mpl::vector<int, double> >::type f2; typedef make_features<mpl::vector<char> >::type f3; BOOST_MPL_ASSERT((boost::is_base_and_derived<f2, f1>)); BOOST_MPL_ASSERT((boost::is_base_and_derived<f3, f1>));
Sorry for taking so long to reply, but TMP always makes my head explode, and it takes a while to pick up the pieces and put them back together. In this case, I could have saved myself the explosion, because this interface offers behavior that is backwards from what I want. The conversion I want to allow is from fewer features to more, so I don't want f2 and f3 to be bases of f1, I want f1 to be a base for both f2 and f3.
Oops. I see.
What I don't know is a good way to give Features<T> the appropriate number of virtual base classes. Can somebody help?
The key thing to note is that you don't need to directly inherit from N base classes. You can create a two argument template and chain them together. #include <boost/mpl/empty_base.hpp> #include <boost/mpl/vector.hpp> #include <boost/mpl/copy.hpp> #include <boost/mpl/assert.hpp> #include <boost/mpl/remove_if.hpp> #include <boost/mpl/at.hpp> #include <boost/mpl/transform.hpp> #include <boost/mpl/push_back.hpp> #include <boost/mpl/back_inserter.hpp> #include <boost/mpl/contains.hpp> #include <boost/mpl/copy_if.hpp> #include <boost/type_traits/is_base_and_derived.hpp> template<class Base1, class Base2> struct VirtualInherit : virtual Base1, virtual Base2 { }; template<class Sequence> struct MakeFeatures; using namespace boost::mpl; typedef vector<int, char, double, void> AllFeatures; template<class T, class U> struct Difference : remove_if<T, contains<U, _> > {}; template<class Original, class New> struct Insert : copy_if<AllFeatures, contains<typename push_back<Original, New>::type, _1> > {}; template<class Original, class Added> struct GetFeaturesBases : transform<Added, MakeFeatures<Insert<Original, _1> > > {}; template<class FeatureList> struct Features : virtual fold< typename GetFeaturesBases<FeatureList, typename Difference<AllFeatures, FeatureList>::type>::type, empty_base, VirtualInherit<_, _>
::type {};
template<class Sequence> struct MakeFeatures { typedef Features<typename copy<Sequence, back_inserter<vector0<> >
::type> type; };
int main() { typedef MakeFeatures<vector<int, char, double> >::type f1; typedef MakeFeatures<vector<int, double> >::type f2; typedef MakeFeatures<vector<char> >::type f3; BOOST_MPL_ASSERT((boost::is_base_and_derived<f1, f2>)); BOOST_MPL_ASSERT((boost::is_base_and_derived<f1, f3>)); } In Christ, Steven Watanabe
Steven Watanabe wrote:
The key thing to note is that you don't need to directly inherit from N base classes. You can create a two argument template and chain them together.
I knew that, but what with my exploding head and all, I didn't want to make any bigger mess at the outset than I had to. I figured I'd add that as a refinement later. Your revised code seems to behave exactly as I want, thank you VERY much. It will take me a while to really understand it, and I'm sure there will be head innards all over the place a few times, but I'm grateful for your speedy and detailed assistance. Scott
Steven Watanabe wrote:
template<class Sequence> struct MakeFeatures { typedef Features<typename copy<Sequence, back_inserter<vector0<> >
::type> type; };
I'm trying to understand the code you posted, but I'm having trouble, probably because I'm missing some basic concepts. I hope people here won't mind helping me with something I'm sure is basic: why do we need to make a copy of Sequence here? I've tried replacing the above typedef with typedef Features<Sequence> type; and everything breaks, so it's clear that the copy is there for a reason, but what is it? Thanks, Scott
AMDG Scott Meyers wrote:
Steven Watanabe wrote:
template<class Sequence> struct MakeFeatures { typedef Features<typename copy<Sequence, back_inserter<vector0<> >
::type> type; };
I'm trying to understand the code you posted, but I'm having trouble, probably because I'm missing some basic concepts. I hope people here won't mind helping me with something I'm sure is basic: why do we need to make a copy of Sequence here? I've tried replacing the above typedef with
typedef Features<Sequence> type;
and everything breaks, so it's clear that the copy is there for a reason, but what is it?
The copy is to guarantee uniqueness. If you have a Features<mpl::list<...> > this will not be the same as a Features<mpl::vector<...> >. The mpl::copy<> makes sure that Features<> always holds a type built by push_back on vector0<>. Thus, MakeFeatures<mpl::list<int, char, double> >::type is the same as MakeFeatures<mpl::vector<int, char double> >::type. Does that help? In Christ, Steven Watanabe
Steven Watanabe wrote:
The copy is to guarantee uniqueness. If you have a Features<mpl::list<...> > this will not be the same as a Features<mpl::vector<...> >. The mpl::copy<> makes sure that Features<> always holds a type built by push_back on vector0<>. Thus, MakeFeatures<mpl::list<int, char, double> >::type is the same as MakeFeatures<mpl::vector<int, char double> >::type. Does that help?
Very much, thank you. Scott
participants (3)
-
Scott Meyers -
Sergei Politov -
Steven Watanabe