Metaprogramming Problem

[continuation.nomad]

I am reading the book C++ Template Metaprogramming. One of the
exercises is as follows:

Write a ternary metafunction replace_type<c,x,y> that takes an
arbitrary compound type c as its first parameter, and replaces all
occurrences of a type x within c with y:

typedef replace_type< void*, void, int >::type t1; // int*
typedef replace_type<int const*[10], int const, long>::type t2; //
long* [10]
typedef replace_type<char& (*)(char&), char&, long&>::type t3; //
long& (*)(long&)


I worked on this for a while and I have what I think is a pretty good
solution. Sorry it's long, but I guess that's how it is with
metaprogramming. Anyway I think my solution handles the general
case. It only does functions with 2 arguments or less but it's
trivial to extend this by copy/pasting a simple partial specialization
and just adding more arguments.

I was wondering if someone could comment on this. Are there any cases
it doesn't handle? Is there a better solution that handles the
general case?





--------------------------------------------------------------------------------------------------------------------
//Helper template. Strips off all *'s and &'s, and allows access to
whatever comes below all of them.
//
//eventual_type<int****&>::type = int
//eventual_type<int>::type = int
//eventual_type<void(****)(int, int)>::type = void(int,int)
template<typename T>
struct eventual_type { typedef T type; };

template<typename T>
struct eventual_type<T&> { typedef typename eventual_type<T>::type
type; };

template<typename T>
struct eventual_type<T*> { typedef typename eventual_type<T>::type
type; };

//True if T is a function after an arbitrary number of levels of
indirection
template<typename T>
struct is_eventually_function
{
static const bool value =
boost::is_function<eventual_type<T>::type>::value;
};



//Helper template to choose a type based on a boolean. If true,
//the first type is chose, otherwise the second.
template<typename Yes, typename No, bool which>
struct choose_type //Default to yes { typedef Yes type; };
template<typename Yes, typename No>
struct choose_type<Yes, No, false> { typedef No type; };



//Helper template to do replacement without recursing through the
'SearchIn' argument
//in the case that it is a function. Replacement occurs only if
SearchIn is exactly
//equal to SearchFor, the only difference being *s and &s. Also adds
the original *s
//and &s back at the end after replacement is complete
template<typename SearchIn, typename SearchFor, typename Replace>
struct primitive_replace
{
typedef typename choose_type<Replace, SearchIn,
boost::is_same<SearchIn, SearchFor>::value>::type type;
};

template<typename SearchIn, typename SearchFor, typename Replace>
struct primitive_replace<SearchIn*, SearchFor, Replace>
{
typedef typename primitive_replace<SearchIn, SearchFor,
Replace>::type* type;
static const int y = 6;
};

template<typename SearchIn, typename SearchFor, typename Replace>
struct primitive_replace<SearchIn&, SearchFor, Replace>
{
typedef typename primitive_replace<SearchIn, SearchFor,
Replace>::type& type;
static const int z = 7;
};





//Generic replacement template. Does replacement in arbitrary types,
recursing through
//nested function arguments.
template<typename SearchIn, typename SearchFor, typename ReplaceWith>
struct replace_type;


//Given a function, replaces all arguments that are exactly equal to
'SearchFor' with
//'ReplaceWith'. If there is an exact match, the replacement happens
immediately. Otherwise
//if a non-matching argument is a function, recursion happens and an
attempt is made on its
//arguments. Note that it is easy to make this template support
arbitrary numbers of function
//arguments. Simply add additional specializations and no other
changes are necessary.
template<typename R, typename SearchFor, typename ReplaceWith>
struct replace_in_function
{
typedef typename replace_type<R, SearchFor, ReplaceWith>::type r;
typedef r(type);
};

template<typename R, typename T1, typename SearchFor, typename
ReplaceWith>
struct replace_in_function<R (T1), SearchFor, ReplaceWith>
{
typedef typename replace_type<R, SearchFor, ReplaceWith>::type r;
typedef typename replace_type<T1, SearchFor, ReplaceWith>::type t1;

typedef r (type)(t1);
};

template<typename R, typename T1, typename T2, typename SearchFor,
typename ReplaceWith>
struct replace_in_function<R (T1, T2), SearchFor, ReplaceWith>
{
typedef typename replace_type<R, SearchFor, ReplaceWith>::type r;
typedef typename replace_type<T1, SearchFor, ReplaceWith>::type t1;
typedef typename replace_type<T2, SearchFor, ReplaceWith>::type t2;

typedef r (type)(t1, t2);
};


//Helper class to split up the logic between functions and non-
functions, so that functions
//are treated differently. The boolean at the end specifies whether
the 'SearchIn' argument
//is a function.
template<typename SearchIn, typename SearchFor, typename ReplaceWith,
bool is_search_func>
struct replace_type_impl //is_search_func=true
{
typedef typename eventual_type<SearchIn>::type
eventual_function_type;

typedef typename replace_in_function<eventual_function_type,
SearchFor, ReplaceWith>::type replaced_eventual_type;

typedef typename primitive_replace<SearchIn, eventual_function_type,
replaced_eventual_type>::type type;
};

template<typename SearchIn, typename SearchFor, typename ReplaceWith>
struct replace_type_impl<SearchIn, SearchFor, ReplaceWith, false>
{
typedef typename primitive_replace<SearchIn, SearchFor,
ReplaceWith>::type type;
};


template<typename SearchIn, typename SearchFor, typename ReplaceWith>
struct replace_type
{
static const bool is_func = is_eventually_function<SearchIn>::value;
static const bool is_exactly_equal = boost::is_same<SearchIn,
SearchFor>::value;

typedef typename replace_type_impl<SearchIn, SearchFor, ReplaceWith,
is_func>::type type_if_not_equal;
typedef typename ReplaceWith type_if_equal;
typedef typename choose_type<type_if_equal, type_if_not_equal,
is_exactly_equal>::type type;
};



Example usage:
typedef void(& funcRefType)(int,int,double);
typedef void(* funcPtrPtrType)(int,int,double);
typedef void(nestedFuncType)(funcRefType, funcPtrType);

typedef replace_in_function<funcRefType, int, char>::type
funcRefReplaced; //void(&)(char,char,double)
typedef replace_in_function<funcPtrType, int, char>::type
funcPtrReplaced; //void(*)(char,char,double)
typedef replace_in_function<nestedFuncType, funcRefType,
funcRefReplaced>::type tempReplace; //void( void(&)(char,char,double),
void(*)(int,int,double)
typedef replace_in_function<tempReplace, funcPtrType,
funcPtrReplaced>::type correctAnswer; //void( void(&)
(char,char,double), void(*)(char,char,double)
typedef replace_in_function<nestedFuncType, int, char>::type
answerToCheck; //void( void(&)(char,char,double), void(*)
(char,char,double)

BOOST_STATIC_ASSERT((boost::is_same<correctAnswer,
answerToCheck>::value));

Email:
f(divisortheory,gmail)
f(a,b) -> (e-mail address removed)

 

[paulkp]

Sorry it's long, but I guess that's how it is with
metaprogramming.

I hope you don't mind me asking, but what is the purpose
of this metaprogramming, other than making the source
code unreadable?

 

[Zachary Turner]

I hope you don't mind me asking, but what is the purpose
of this metaprogramming, other than making the source
code unreadable?

Like Jeff said, it's just an exercise. Obviously you're not going be
typing code like this on a regular basis, but metaprogramming has some
valid applications. Maybe not this particular metaprogramming
problem, but on the other hand maybe so. Either way, code like this,
if it ever appeared in a production situation, would be highly hidden
and invisible to the user of the library. The entirety of boost
pretty much relies 100% on being able to do things like this. I agree
it's not pretty, and techniques such as this should be used with
caution, but when necessary, they allow to solve some very difficult
problems efficiently

 

[continuation.nomad]

I hope you don't mind me asking, but what is the purpose
of this metaprogramming, other than making the source
code unreadable?

Like Jeff said, it's just an exercise. Obviously you're not going be
typing code like this on a regular basis, but metaprogramming has some
valid applications. Maybe not this particular metaprogramming
problem, but on the other hand maybe so. Either way, code like this,
if it ever appeared in a production situation, would be highly hidden
and invisible to the user of the library. The entirety of boost
pretty much relies 100% on being able to do things like this. I agree
it's not pretty, and techniques such as this should be used with
caution, but when necessary, they allow to solve some very difficult
problems efficiently

 

[continuation.nomad]

I worked on this for a while and I have what I think is a pretty good
solution.  Sorry it's long, but I guess that's how it is with
metaprogramming.

Were the first programs you ever wrote clean and graceful?  Most newbie
code is ugly and verbose.  Well, metaprogramming is almost like learning
to program all over again.  That book will give you tools that help, but
there's no substitute for practice.

The code you posted would be a lot clearer if you made sure the lines
didn't wrap.  When you post code on Usenet, try to keep each line to 68
characters or fewer.

I was wondering if someone could comment on this.  Are there any cases
it doesn't handle?  Is there a better solution that handles the
general case?

I didn't properly solve that exercise, except as a kind of gedanken
experiment.  My understanding is that you:

1. Define the primary template to just return its argument.

2. Specialize for the case in which the first and second arguments are
the same, to return the replacement type.

3. Specialize for the various compound types, to:
        a. recurse on each sub-type
        b. combine the results of the recursions

You know, I think we just solved it.  Hang on a second.

OK, here you go.  Happy hacking!

/* Primary template:  Return C unchanged. */
template<class C, class X, class Y>
struct replace_type
{
     typedef C type;

};

/* Specialization for when C is the target type:  Return Y. */
template<class C, class Y>
struct replace_type<C, C, Y>
{
     typedef Y type;

};

/* Specialization for arrays: Recurse on the element type, and
  * return an array type of the same size as the original.
  */
template<class C, unsigned long N, class X, class Y>
struct replace_type<C[N], X, Y>
{
     typedef typename replace_type<C, X, Y>::type type[N];

};

/* Specialization for nullary functions. */
template<class R, class X, class Y>
struct replace_type<R(), X, Y>
{
     typedef typename replace_type<R, X, Y>::type type();

};

// ... specializations for other compound types ...

/* Everything below this line is test code. */

#include <boost/static_assert.hpp>
#include <boost/type_traits.hpp>

/* Tests for atomic types. */
BOOST_STATIC_ASSERT((
             boost::is_same<
                 replace_type<int,float,double>::type
               , int
             >::value));

BOOST_STATIC_ASSERT((
             boost::is_same<
                 replace_type<float,float,double>::type
               , double
             >::value));

/* Tests for array types. */
BOOST_STATIC_ASSERT((
             boost::is_same<
                 replace_type<int[42],float,double>::type
               , int[42]
             >::value));

BOOST_STATIC_ASSERT((
             boost::is_same<
                 replace_type<float[42],float,double>::type
               , double[42]
             >::value));

/* Tests for nullary function types. */
BOOST_STATIC_ASSERT((
             boost::is_same<
                 replace_type<int(),float,double>::type
               , int()
             >::value));

BOOST_STATIC_ASSERT((
             boost::is_same<
                 replace_type<float(),float,double>::type
               , double()
             >::value));

// ... tests of specializations for other compound types ...

Thanks! I'm going to paste your code into my dev environment and play
around with it a bit. Assuming it works it's obviously cleaner than
mine. Although I really have very little experience with
metaprogramming, so I was surprised that I was able to get a solution
at all, it was quite difficult. I did find out after the posting that
I never handled the case for array types, only for pointers and
references. But it was an easy matter of adding two more
specializations to fix that. Will yours work for const / volatile
modifiers, and arbitrary levels of compoundness like replaec
(int**const*,int,double) -> double**const*?

Well I'll play with it a bit.

 

[continuation.nomad]

But fun, isn't it?


Yes, the technique should work, although I did not implement modifers,
nor pointer types, nor non-nullary functions.

One change is needed to yours I think. Took me forever to figure this
out when I did mine. If the type that you're "searching" for is
itself a compound type (int* instead of int, or int(int,int), etc)
then the recursion proceeds anyway to the most primitive type, and a
match is never found. For example, replace(int(int,int), int
(int,int), float(double)) should return float(double). Without the
additional check though it returns int(int,int) because neither the
return type, nor either of the two arguments are equal to int
(int,int). It's not a difficult fix though. Change all the
replace_type templates to replace_type_impl, then make replace_type do
this:

static const bool is_exactly_equal = boost::is_same<SearchFor,
SearchIn>::value;

typedef ReplaceType equal_type;

typedef replace_type_impl<SearchFor,SearchIn,ReplaceType>::type
not_equal_type;

typedef choose_type<equal_type, not_equal_type, is_exactly_equal::type
type;

And make sure replace_type_impl's internal typedef's still use
replace_type instead of replace_type_impl. Otherwise I think your
method will probably work in the general case with enough
specializations

 

[Noah Roberts]

/* Everything below this line is test code. */

#include <boost/static_assert.hpp>
#include <boost/type_traits.hpp>

/* Tests for atomic types. */
BOOST_STATIC_ASSERT((
boost::is_same<


BOOST_STATIC_ASSERT((
boost::is_same<


/* Tests for array types. */
BOOST_STATIC_ASSERT((
boost::is_same<


BOOST_STATIC_ASSERT((
boost::is_same<


/* Tests for nullary function types. */
BOOST_STATIC_ASSERT((
boost::is_same<


BOOST_STATIC_ASSERT((
boost::is_same<


// ... tests of specializations for other compound types ...

What about

BOOST_STATIC_ASSERT((
boost::is_same<

>::value));

I think that might generate an ambiguity error.

You'd also want const and volatile metafunctions.