//
// Copyright (c) 2003 by Stephen C. Dewhurst
// Permission to use, copy, modify, distribute and sell this software for any purpose is
// hereby granted without fee, provided that the above copyright notice appears in all copies
// and that both that copyright notice and this permission notice appear in supporting documentation.
// The author makes no representations about the suitability of this software for any purpose.
// It is provided "as is" without express or implied warranty.
//

#ifndef DISMANTLE_H
#define DISMANTLE_H

//
//	This is a quick and experimental version of a template metaprogramming
//	facility for compile time type manipulation.  It is described in
//	Semantics Consulting's "Once, Weakly" feature of 23 February 2003, at
//	http://www.semantics.org/once_weakly.html.
//
//	Basically, we dismantle a type into its constituent parts.  We then have
//	the opportunity to examine its parts, change them, remove some, add some
//	new pieces, perform regular-expression-like matching and substitution, etc.
//	Finally, we can regenerate a "regular" type from the (potentially) modified
//	dismantled type.
//
//	From the web posting: "In effect, we now have two equivalent, but structurally
//	distinct, versions of the same type.  The normal version is optimized for use
//	in a traditional fashion: accessing its operations, causing code to be generated
//	that will execute at runtime, etc.  The dismantled version is optimized for
//	compile time analysis and manipulation.  Therefore, we now have the ability to
//	move an arbitrary type among different representations according to how we want
//	to use it.  The invertibility of the representations assures us that either
//	representation will contain all the information present in the other."
//
//	In this preliminary version, the facilities for manipulating the dismantled
//	type are very primitive.  Bear with me...

//------------------------------
//	If your compiler has trouble translating some of the code below,
//	try recompiling with OMIT_PROBLEMATIC defined to get a limited
//	version of the facility.
//#define OMIT_PROBLEMATIC

//------------------------------
//	WHAT'S HERE?
//
// Dismantle a type into its constituent parts.
template <typename T>
struct Dis;

// Regenerate a dismantled type.
template <class T>
struct Regen;

// Substitute dismantled type S for any node satisfying Pred
// in dismantled type T

// ...for the first n appearances in T.
template <int n, class T, template <typename> class Pred, class S>
struct SubstN;

// ...for the first appearance in T.
template <class T, template <typename> class Pred, class S>
struct Subst;

// ...for all appearances in T.
template <class T, template <typename> class Pred, class S>
struct SubstAll;

// Substitute the result of applying applicator Apply to the
// current node for any node satisfying Pred in dismantled type T

// ...for the first N appearances in T.
template <int n, class T, template <typename> class Pred, template <typename> class Apply>
struct SubstAN;

//...for the first appearance in T.
template <class T, template <typename> class Pred, template <typename> class Apply>
struct SubstA;

//...for all appearances in T.
template <class T, template <typename> class Pred, template <typename> class Apply>
struct SubstAAll;

//------------------------------
//
//	Some utilities.
//
template <typename A, typename B>
struct IsSame
	{ enum { r = false }; };
template <typename A>
struct IsSame<A,A>
	{ enum { r = true }; };

template <bool, typename A, typename>
struct Select
	{ typedef A R; };
template <typename A, typename B>
struct Select<false,A,B>
	{ typedef B R; };
//------------------------------
//
//	A very simple typelist.  The head is a type,
//	the tail is a typelist.  A NullTList is a typelist.
//
template <typename T, class U>
struct TList {
	typedef T Head;
	typedef U Tail;
};

typedef struct {} NullTList;

template <class TL, typename T> // Alexandrescu's append
struct Append;

template <>
struct Append<NullTList,NullTList>
	{ typedef NullTList R; };

template <typename T>
struct Append<NullTList,T>
	{ typedef TList<T,NullTList> R; };

template <typename Head, typename Tail>
struct Append< NullTList,TList<Head,Tail> >
	{ typedef TList<Head,Tail> R; };

template <typename Head, typename Tail, typename T>
struct Append<TList<Head,Tail>,T>
	{ typedef TList<Head,typename Append<Tail,T>::R> R; };
//-------------------------------
//
//	Types that represent type qualifiers and type modifiers in
//	the dismantled version of a type.
//
struct Const {};
struct Volatile {};
struct Ref {};
struct Ptr {};

template <int b>
struct Ary
	{ enum { bound = b }; };

template <class C>
struct Pcm
	{ typedef typename Dis<C>::R Class; };

// Function modifiers (member and non-member) modify the return type.
// Therefore, only the arguments are available within these modifier types.
struct Fun0 {};

template <typename A>
struct Fun1
	{ typedef typename Dis<A>::R Arg; };
	
template <typename A1, typename A2>
struct Fun2 {
	typedef typename Dis<A1>::R Arg1;
	typedef typename Dis<A2>::R Arg2;
};

template <class C>
struct MFun0
	{ typedef typename Dis<C>::R Class; };

template <class C, typename A>
struct MFun1 {
	typedef typename Dis<C>::R Class;
	typedef typename Dis<A>::R Arg;
};

template <class C, typename A1, typename A2>
struct MFun2 {
	typedef typename Dis<C>::R Class;
	typedef typename Dis<A1>::R Arg1;
	typedef typename Dis<A2>::R Arg2;
};

template <class C>
struct CMFun0
	{ typedef typename Dis<C>::R Class; };
	
template <class C, typename A>
struct CMFun1 {
	typedef typename Dis<C>::R Class;
	typedef typename Dis<A>::R Arg;
};

template <class C, typename A1, typename A2>
struct CMFun2 {
	typedef typename Dis<C>::R Class;
	typedef typename Dis<A1>::R Arg1;
	typedef typename Dis<A2>::R Arg2;
};

//-------------------------------
//	TYPE DISMANTLING
//
//	The primary template is the catch-all for any type
//	that is not more specifically specialized.
//	See specialized types below.
//
template <typename T>
struct Dis {
	typedef TList<T,NullTList> R;
};

template <typename T>
struct Dis<const T> {
	typedef TList<Const, typename Dis<T>::R> R;
};

template <typename T>
struct Dis<volatile T> {
	typedef TList<Volatile, typename Dis<T>::R> R;
};

template <typename T>
struct Dis<const volatile T> {
	typedef TList<Const, typename Dis<volatile T>::R> R;
};

template <typename T>
struct Dis<T &> {
	typedef TList<Ref, typename Dis<T>::R> R;
};

template <typename T>
struct Dis<T *> {
	typedef TList<Ptr, typename Dis<T>::R> R;
};

template <typename T>
struct Dis< T *const> {
	typedef TList<Const, typename Dis<T *>::R> R;
};

template <typename T>
struct Dis< T *volatile> {
	typedef TList<Volatile, typename Dis<T *>::R> R;
};

template <typename T>
struct Dis< T *const volatile> {
	typedef TList<Const, typename Dis<T * volatile>::R> R;
};

template <typename T, int b>
struct Dis<T[b]> {
	typedef TList< Ary<b>,typename Dis<T>::R > R;
};

template <class C, typename T>
struct Dis<T C::*> {
	typedef TList<Pcm<C>,typename Dis<T>::R> R;
};

#ifndef OMIT_PROBLEMATIC

template <class C, typename T>
struct Dis<T C::*const> {
	typedef TList<Const,typename Dis<T C::*>::R> R;
};

template <class C, typename T>
struct Dis<T C::*volatile> {
	typedef TList<Volatile,typename Dis<T C::*>::R> R;
};

template <class C, typename T>
struct Dis<T C::*const volatile> {
	typedef TList<Const,typename Dis<T C::*volatile>::R> R;
};

#endif

template <typename Ret>
struct Dis<Ret(void)> {
	typedef TList<Fun0,typename Dis<Ret>::R> R;
};

template <typename Ret, typename Arg>
struct Dis<Ret(Arg)> {
	typedef TList<Fun1<Arg>,typename Dis<Ret>::R> R;
};

template <typename Ret, typename Arg1, typename Arg2>
struct Dis<Ret(Arg1,Arg2)> {
	typedef TList<Fun2<Arg1,Arg2>,typename Dis<Ret>::R> R;
};

template <class C, typename Ret>
struct Dis<Ret (C::*)()> {
	typedef TList<MFun0<C>,typename Dis<Ret>::R> R;
};

template <class C, typename Ret, typename Arg>
struct Dis<Ret (C::*)(Arg)> {
	typedef TList<MFun1<C,Arg>,typename Dis<Ret>::R> R;
};

template <class C, typename Ret, typename Arg1, typename Arg2>
struct Dis<Ret(C::*)(Arg1,Arg2)> {
	typedef TList<MFun2<C,Arg1,Arg2>,typename Dis<Ret>::R> R;
};

template <class C, typename Ret>
struct Dis<Ret (C::*)() const> {
	typedef TList< Const,TList<CMFun0<C>,typename Dis<Ret>::R> > R;
};

template <class C, typename Ret, typename Arg>
struct Dis<Ret (C::*)(Arg )const> {
	typedef TList< Const, TList<CMFun1<C,Arg>,typename Dis<Ret>::R> > R;
};

template <class C, typename Ret, typename Arg1, typename Arg2>
struct Dis<Ret(C::*)(Arg1,Arg2) const> {
	typedef TList< Const, TList<CMFun2<C,Arg1,Arg2>,typename Dis<Ret>::R> > R;
};
//------------------------------
//	REGENERATING A DISMANTLED TYPE
//
template <class T>
struct Regen;

template <typename T>
struct Regen< TList<T,NullTList> > {
	typedef T R;
};

template <class T>
struct Regen< TList<Const,T> > {
	typedef const typename Regen<T>::R R;
};

template <class T>
struct Regen< TList<Volatile,T> > {
	typedef volatile typename Regen<T>::R R;
};

template <class T>
struct Regen< TList<Ref,T> > {
	typedef typename Regen<T>::R &R;
};

template <class T>
struct Regen< TList<Ptr,T> > {
	typedef typename Regen<T>::R *R;
};

template <class T, int b>
struct Regen< TList<Ary<b>,T> > {
	typedef typename Regen<T>::R R[b];
};

template <class T, class C>
struct Regen< TList<Pcm<C>,T> > {
	typedef typename Regen<T>::R C::*R;
};

template <typename T>
struct Regen< TList<Fun0,T> > {
	typedef typename Regen<T>::R R();
};

template <typename T, typename A>
struct Regen< TList<Fun1<A>,T> > {
	typedef typename Regen<T>::R R( A );
};

template <typename T, typename A1, typename A2>
struct Regen< TList<Fun2<A1,A2>,T> > {
	typedef typename Regen<T>::R R( A1, A2 );
};

template <class C, typename T>
struct Regen< TList<MFun0<C>,T> > {
	typedef typename Regen<T>::R (C::*R)();
};

template <class C, typename T, typename A>
struct Regen< TList<MFun1<C,A>,T> > {
	typedef typename Regen<T>::R (C::*R)( A );
};

template <class C, typename T, typename A1, typename A2>
struct Regen< TList<MFun2<C,A1,A2>,T> > {
	typedef typename Regen<T>::R (C::*R)( A1, A2 );
};

template <class C, typename T>
struct Regen< TList<CMFun0<C>,T> > {
	typedef typename Regen<T>::R (C::*R)() const;
};

template <class C, typename T, typename A>
struct Regen< TList<CMFun1<C,A>,T> > {
	typedef typename Regen<T>::R (C::*R)( A ) const;
};

template <class C, typename T, typename A1, typename A2>
struct Regen< TList<CMFun2<C,A1,A2>,T> > {
	typedef typename Regen<T>::R (C::*R)( A1, A2 ) const;
};

//------------------------------
//	SUBSTITUTION
//
//	Note that, because modifiers and qualifiers are represented as
//	types in the dismantled representation, type substitution can
//	be used to modify these aspects of the type as well.  (For instance,
//	you can substitute Ptr for Ref in a dismantled type to change that
//	modifier in the regenerated type.)

//-------------------------------
//	Subst applies a predicate to each node.  If true, then the node is
//	replaced by S, which should be a Dis'ed type.
template <int n, class T, template <typename> class Pred, class S>
struct SubstN {
	typedef typename Select<Pred<typename T::Head>::r,
				typename Append<S,typename SubstN<n-1,typename T::Tail,Pred,S>::R>::R,
				TList<typename T::Head, typename SubstN<n,typename T::Tail,Pred,S>::R>
			>::R R;
};

template <int n, template <typename> class Pred, class S>
struct SubstN<n, NullTList, Pred, S > {
	typedef NullTList R;
};

template <class T, template <typename> class Pred, class S>
struct SubstN<0,T,Pred,S> {
	typedef T R;
};

template <template <typename> class Pred, class S>
struct SubstN<0,NullTList,Pred,S > {
	typedef NullTList R;
};

template <class T, template <typename> class Pred, class S>
struct Subst {
	typedef typename SubstN<1,T,Pred,S>::R R;
};

template <class T, template <typename> class Pred, class S>
struct SubstAll {
	typedef typename SubstN<32767,T,Pred,S>::R R;
};
//---------------------------------------
//	SubstA applies a predicate to each node.  If true, then the node is
//	replaced by the result of instantiating Apply with the node.  Presumably,
//	the applicator will "transform" the node into another Dis'ed component.
template <int n, class T, template <typename> class Pred, template <typename> class Apply>
struct SubstAN;
 
template <bool, int n, class T, template <typename> class Pred, template <typename> class Apply>
struct SubstANImpl {
	typedef typename T::Head Hd;
	typedef typename T::Tail Tl;
	typedef TList<Hd, typename SubstAN<n,Tl,Pred,Apply>::R> R;
};

template <int n, class T, template <typename> class Pred, template <typename> class Apply>
struct SubstANImpl<true,n,T,Pred,Apply> {
	typedef typename T::Head Hd;
	typedef typename T::Tail Tl;
	typedef typename Append<TList<typename Apply<Hd>::R,NullTList>,typename SubstAN<n-1,Tl,Pred,Apply>::R>::R R;
};

template <int n, class T, template <typename> class Pred, template <typename> class Apply>
struct SubstAN {
	// Have to be indirect here to avoid instantiation of Apply if Pred is false.  (Apply
	// may not be legal if Pred fails.)
	typedef typename SubstANImpl<Pred<typename T::Head>::r,n,T,Pred,Apply>::R R;
};

template <int n, template <typename> class Pred, template <typename> class Apply>
struct SubstAN<n,NullTList,Pred,Apply> {
	typedef NullTList R;
};

template <class T, template <typename> class Pred, template <typename> class Apply>
struct SubstAN<0,T,Pred,Apply> {
	typedef T R;
};

template <template <typename> class Pred, template <typename> class Apply>
struct SubstAN<0,NullTList,Pred,Apply> {
	typedef NullTList R;
};

template <class T, template <typename> class Pred, template <typename> class Apply>
struct SubstA {
	typedef typename SubstAN<1,T,Pred,Apply>::R R;
};

template <class T, template <typename> class Pred, template <typename> class Apply>
struct SubstAAll {
	typedef typename SubstAN<32767,T,Pred,Apply>::R R;
};
//---------------------------------
//	INDEXING
//
template <class,int> struct Index;

template <class H, class T, int i>
struct Index<TList<H,T>,i> {
	typedef typename Index<T,i-1>::R R;
};

template <class H, class T>
struct Index<TList<H,T>,0> {
	typedef H R;
};

template <int i>
struct Index<NullTList,i> {
	typedef NullTList R;
};

template <>
struct Index<NullTList,0> {
	typedef NullTList R;
};
//-------------------------------------
//	LENGTH (NUMBER OF PARTS IN DISASSEMBLED TYPE)
//
template <typename> struct Length;

template <typename T, class U>
struct Length< TList<T,U> > {
	enum { r = 1 + Length<U>::r };
};

template <>
struct Length<NullTList> {
	enum { r = 0 };
};

//------------------------------
//	SPECIAL CASE TYPES
//
//	The templates below allow us to special-case for types that are generated
//	from class templates for the argument combinations we select.
//	Otherwise, a type will be recognized "generically" by the primary Dis
//	template.
//
//	Of course, we can special-case for other kinds of types as well.
//
//---------------------------------------------
//	Types generated from templates with one type arg.
//

#ifndef OMIT_PROBLEMATIC

template <template <typename> class Templ, typename T>
struct TemplT {
	template <typename S>
	struct Subst
		{ typedef Templ<S> R; };
	typedef T Arg;
	typedef typename Dis<T>::R R;
};

template <template <typename> class Templ, typename T>
struct Dis < Templ<T> > {
	typedef TList<TemplT<Templ,T>, NullTList> R;
};

template <template <typename> class Templ, typename T>
struct Regen< TList<TemplT<Templ,T>,NullTList> > {
	typedef Templ<T> R;
};

//-------------------------------------------------
//	Types generated from templates with two type args.
//
template <template <typename,typename> class Templ, typename T1, typename T2>
struct TemplTT {
	template <typename S1, typename S2>
	struct Subst
		{ typedef Templ<S1,S2> R; };
	typedef T1 Arg1;
	typedef T2 Arg2;
	typedef typename Dis<T1>::R R1;
	typedef typename Dis<T2>::R R2;
};

template <template <typename,typename> class Templ, typename T1, typename T2>
struct Dis < Templ<T1,T2> > {
	typedef TList<TemplTT<Templ,T1,T2>, NullTList> R;
};

template <template <typename,typename> class Templ, typename T1, typename T2>
struct Regen< TList<TemplTT<Templ,T1,T2>,NullTList> > {
	typedef Templ<T1,T2> R;
};

#endif

#endif