Hard stuff - traversing the base class-graph

So far we have seen two families of compile-time iterations:

Both can be used with a user defined attribute function.
For any of these it might be necessary to combine the attribute-wise iteration with the base class traversion (that is to apply the user defined function object to each attribute of each base class as well).

For instance when printing the values of the member variables of a reflected class the values of all reflected attributes of each base class should be printed as well.
It would be a nice feature if this traversion would respect virtual base classes.
If the most derived class contains only one base class subobject then the attributes of that subobject should be printed only once regardless of the number of vertices in the inheritance graph that have this base class as target.
Example 1:

In this situation we would expect that the state of the B subobject of AA be printed once and only once when an instance of AA gets printed.

Example 2:


In this situation we would expect that the state of the virtual B subobject of AA will be printed once and the state of the non-virtual B subobject would be printed as well (note that this state will be accessible only through qualified access like aa.Z::setFoo(23);)

It turns out, that we can store at compiletime the virtual base classes that were already traversed in a typelist and use that typelist as parameter for the next recursion.

As always I use tag-dispatching to plug in the correct variant of a given function.
Two different situations need to be handled here:

Hence these two tags come in quite naturally:

struct VirtualBaseClassAlreadyHandledTag{};

struct VirtualBaseClassNotHandledYetTag{};

I store the virtual base classes that were already handled in a typelist to be able to answer the question whether a given class is already handled. Thus I need a compiletime function that retrieves that information for a given base class and a given typelist.

template<class ClassList,class WhichBaseClass, bool isVirtual = true> 
struct GetVBaseClassHandled
{
    enum {handledPreviously = Loki::TL::IndexOf<ClassList,WhichBaseClass>::value > -1};
    typedef typename boost::ct_if<(handledPreviously != 0),
                                VirtualBaseClassAlreadyHandledTag,
                                VirtualBaseClassNotHandledYetTag >::type
    type;
};

If the current occurrence of a base class is not virtual then this class should be processed in any case. That is why the specialization for isVirtual == false "returns" VirtualBaseClassNotHandledYetTag

template<class ClassList,class WhichBaseClass> struct 
GetVBaseClassHandled<ClassList, WhichBaseClass, false>
{
    typedef VirtualBaseClassNotHandledYetTag type;
};

Of course I need a compiletime function to store a base class that was already handled in the typelist of all handled virtual base classes.

template<class HandledVBaseClasses, class BaseClass, class DecisionTag> struct AddBaseClassConditionallyImpl;

When the base class was already handled then this function has to do nothing.

template< class HandledVBaseClasses, class BaseClass> struct 
AddBaseClassConditionallyImpl< HandledVBaseClasses,BaseClass, VirtualBaseClassAlreadyHandledTag>
{
    typedef HandledVBaseClasses type;
};

When the base class was not handled then this function prepends the base class to the list.

template< class HandledVBaseClasses, class BaseClass> struct 
AddBaseClassConditionallyImpl< HandledVBaseClasses,BaseClass, VirtualBaseClassNotHandledYetTag>
{
    typedef Loki::Typelist<BaseClass,HandledVBaseClasses> type;
};

I use the typelist from Andrei Alexandrescus Loki library because this list does not impose restrictions on the possible number of elements in that list.
Even if it can be proven (which I doubt) that there will never be a sound design that requires having like 50 virtual base classes of one class, a library should not try to enforce design rules on it's users.

template< class HandledVBaseClasses, class BaseClass, bool isVirtual> struct AddBaseClassConditionally
{
    typedef typename GetVBaseClassHandled<HandledVBaseClasses,BaseClass,isVirtual>::type 
              DecisionTag;
    typedef typename AddBaseClassConditionallyImpl<HandledVBaseClasses,BaseClass,
              DecisionTag>::type
        type;
};

When the base class is not virtual it does not belong to the list of virtual base classes that were already handled.

template<class HandledVBaseClasses, class BaseClass> struct 
AddBaseClassConditionally< HandledVBaseClasses,BaseClass,false>
{
    typedef HandledVBaseClasses type;
};

The iteration over all direct base classes is similar to the iteration over all direct member variables in AllAttributes.

template<class ReflectedClass, class InitialHandledVBaseClassesT> struct AllBaseClasses
{
    typedef InitialHandledVBaseClassesT InitialHandledVBaseClasses;
    enum {TotalNumBaseClasses = ReflectedClass::NumBaseClasses};
    template<class CTRecursion, int Num> struct BaseClassVisitor
    {
        // . . .
        static void processSingleBaseClass(ReflectedClass& recordData,CTRecursion& ctRecursion);
    };
    template<class CTRecursion, int RestToDo> struct 
                 HorizontalIter:BaseClassVisitor<CTRecursion,TotalNumBaseClasses-RestToDo>
    {
        static void process(ReflectedClass& recordData,CTRecursion& ctRecursion);
    };
    template<class CTRecursion> static void
    doForeach(ReflectedClass& dataTuple, CTRecursion& ctRecursion)
    {
        HorizontalIter<CTRecursion,TotalNumBaseClasses>::process(dataTuple,ctRecursion);
    }
    template<class CTRecursion> struct AfterEnd
    {
        typedef HorizontalIter<CTRecursion,0> Impl;
        typedef typename Impl::HandledVBaseClasses HandledVBaseClasses;
    };
};

AfterEnd hides the implementation detail that the handled base classes are accessible through the HorizontalIter instantiation with 0 as second template argument. If more than one base class is left to process I have to process that base class and after that process the next direct base class of ReflectedClass.

template<class ReflectedClass, class InitialHandledVBaseClassesT> 
    template<class CTRecursion, int RestToDo>
void AllBaseClasses<ReflectedClass,
   InitialHandledVBaseClassesT>::HorizontalIter<CTRecursion,
                                        RestToDo>::process(ReflectedClass& recordData,
                                                          CTRecursion& ctRecursion)
{
    processSingleBaseClass(recordData, ctRecursion);
    HorizontalIter<CTRecursion,RestToDo-1>::process(recordData, ctRecursion);
}

If only one base class is left to process I only have to process that base class.

template<class ReflectedClass, class InitialHandledVBaseClassesT> 
template<class CTRecursion> struct 
AllBaseClasses<ReflectedClass,InitialHandledVBaseClassesT>::HorizontalIter<CTRecursion,1>
                                        :BaseClassVisitor<CTRecursion,TotalNumBaseClasses-1>
{
    static void process(ReflectedClass& recordData,CTRecursion& ctRecursion)
    {
        processSingleBaseClass(recordData, ctRecursion);
    }
};

(Note that in C++ there is no such thing as partial specialization of function templates - hence I must partially specialize the nested class template HorizontalIter.) If no base class is left to process it is quite wise to have a process function that does not even try to do something. Each BaseClassVisitor stores the list of all classes that are handled after this BaseClassVisitor has been instantiated. In particular the list of all base classes that are processed after the last direct base class of ReflectedClass has been processed is the list defined in the BaseClassVisitor of the last direct base class.

template<class ReflectedClass, class InitialHandledVBaseClassesT> 
template<class CTRecursion> struct AllBaseClasses<ReflectedClass,
                                      InitialHandledVBaseClassesT>::HorizontalIter<CTRecursion,0>
{
    typedef BaseClassVisitor<CTRecursion,TotalNumBaseClasses-1> Prev;
    typedef typename Prev::HandledVBaseClasses HandledVBaseClasses;
    static void process(ReflectedClass& ,CTRecursion& )
    {}
};

When ReflectedClass has no BaseClass (which will eventually be the case) then TotalNumBaseClasses == 0 and the following specialization of BaseClassVisitor will be chosen. The list of handled virtual base classes cannot increase in this case because there are no base classes at all to be handled in this instantiation of the AllBaseClasses algorithm - hence the list of all handled classes remains the same as it was initially.

template<class ReflectedClass, class InitialHandledVBaseClassesT> 
template<class CTRecursion> struct AllBaseClasses<ReflectedClass,
                                 InitialHandledVBaseClassesT>::BaseClassVisitor<CTRecursion,-1>
{
    typedef InitialHandledVBaseClasses HandledVBaseClasses;
};

Now to the general BaseClassVisitor:

template<class ReflectedClass, class InitialHandledVBaseClassesT> struct AllBaseClasses
{
    template<class CTRecursion, int Num> struct BaseClassVisitor
    {
        typedef typename ReflectedClass::template GetBaseClass<Num> CurrentBaseClassTraits;
        typedef typename CurrentBaseClassTraits::type CurrentBaseClassType;     // (1)
        typedef typename GetQualifiedMemberType<ReflectedClass,CurrentBaseClassType>::type 
           BaseClass;                                                           // (2)
        typedef BaseClassVisitor<CTRecursion,Num - 1> Previous;
        typedef typename Previous::HandledVBaseClasses HandledSofar;
        typedef AllBaseClasses<BaseClass,HandledSofar> BaseClassesOfBaseClass;  // (3)
        typedef typename BaseClassesOfBaseClass::template                                 
            AfterEnd<CTRecursion>::HandledVBaseClasses SofarPlusVBaseClassesOfBaseClass;
        typedef typename AddBaseClassConditionally<SofarPlusVBaseClassesOfBaseClass, 
                BaseClass, CurrentBaseClassTraits::isVirtual>::type HandledVBaseClasses; // (4)
        static void processSingleBaseClass(ReflectedClass& recordData,CTRecursion& ctRecursion)
        {
            typedef typename GetVBaseClassHandled<HandledSofar,BaseClass,
                              CurrentBaseClassTraits::isVirtual>::type VBaseClassHandledTag;
            processAsBaseClass(static_cast<BaseClass&>(recordData),ctRecursion, 
                              VBaseClassHandledTag());                          // (5)
        } 
        static void processAsBaseClass(BaseClass&,CTRecursion&,VirtualBaseClassAlreadyHandledTag)
        {}                                                                      // (6)
        static void processAsBaseClass(BaseClass& recordData, CTRecursion& ctRecursion, 
                                     VirtualBaseClassNotHandledYetTag)    
        {                                                                       // (7)
            BaseClassesOfBaseClass::doForeach(recordData,ctRecursion);
            ctRecursion(recordData);
        }
    };
. . .
}

The macros that define a reflected base class (DEF_REFLECTED_BASECLASS, DEF_REFLECTED_VIRTUAL_BASECLASS) specialize a class template that has two members:

This class template is named GetBaseClass. (1)
GetQualifiedMemberType is a compile time function that "adds" the c(onst) v(olatile) qualification of its first parameter to its second parameter. (2)
BaseClassesOfBaseClass is the next full depth recursion step for the current base class. (3)
Since this instantiation of BaseClassVisitor will trigger the instantiation of BaseClassesOfBaseClass and will handle BaseClass after this instantiation is processed, the list of handled virtual base classes will be the union of the base classes handled so far and the base classes handled in the deeper recursion plus the current base class. (4)
When the current base class is in the list of base classes handled so far then VBaseClassHandledTag will be VirtualBaseClassAlreadyHandledTag and the overload of processAsBaseClass that does nothing will be chosen. (5, 6)
Otherwise VBaseClassHandledTag will be VirtualBaseClassNotHandledYetTag. In that case the deeper recursion will be instantiated to call the user supplied function object on each base class and after that (whether there were base classes or not) the user supplied function object will be invoked on the current base class. (5, 7)

So far we have seen that base class iteration requires a function object as one of its parameters. As mentioned above this function object may come in two flavours:

Hence I need to wrap the flavours into a class template. I show this for the attribute-wise depth first algorithm family when one or two root instances are supplied. To be able to store and retrieve the information whether base classes of the root object(s) and of member variables shall be considered or not the following tag types are used:

struct IncludeBaseClassesOfAttributesTag{};

struct DontIncludeBaseClassesOfAttributesTag{};

The overloads of depthFirstForeachPassTag allow the use of a compile time variable that stores the information about base class traversion.

template<class ReflectedClass, class Function, class MemberKinds>
void depthFirstForeachPassTag(ReflectedClass& dataTuple, Function& function,
                        MemberKinds,DontIncludeBaseClassesOfAttributesTag)
{
    DepthFirst<ReflectedClass,MemberKinds,
        DontIncludeBaseClassesOfAttributesTag>::doForeach(dataTuple,
                                                        function);
}
// binary (ReflectedClass) overload
template<class ReflectedClass, class Function, class MemberKinds>
void depthFirstForeachPassTag(ReflectedClass& lhsTuple,ReflectedClass& rhsTuple, 
	   Function& function, MemberKinds, DontIncludeBaseClassesOfAttributesTag)
{
    DepthFirst<ReflectedClass,MemberKinds,
        DontIncludeBaseClassesOfAttributesTag>::doForeach(lhsTuple, rhsTuple,
                                                        function);
}

template<class ReflectedClass, class Function, class MemberKinds>
void depthFirstForeachPassTag(ReflectedClass& dataTuple, Function& function,
                            MemberKinds,IncludeBaseClassesOfAttributesTag)
{
    DepthFirst<ReflectedClass,MemberKinds,
        IncludeBaseClassesOfAttributesTag>::doForeach(dataTuple,function);
}

// binary (ReflectedClass) overload
template<class ReflectedClass, class Function, class MemberKinds>
void depthFirstForeachPassTag(ReflectedClass& lhsTuple,ReflectedClass& rhsTuple, 
           Function& function, MemberKinds,IncludeBaseClassesOfAttributesTag)
{
    DepthFirst<ReflectedClass,MemberKinds,
        IncludeBaseClassesOfAttributesTag>::doForeach(lhsTuple, rhsTuple,function);
}

Member traversions have several orthogonal properties:

When a base class is visited during traversion, then I must be able to start a member traversion with the same values for the aforementioned properties. For deep attribute traversions DeepAttributeFunction does this job.

template<bool IncludeBaseClasses> struct IncludeBases;

template<> struct IncludeBases<false>
{
    typedef DontIncludeBaseClassesOfAttributesTag MemberTraversionType;
};

template<> struct IncludeBases<true>
{
    typedef IncludeBaseClassesOfAttributesTag MemberTraversionType;
};

template<class Function, class MemberKinds, 
        bool IncludeBaseClassesOfMembers> struct 
DeepAttributeFunction :IncludeBases<IncludeBaseClassesOfMembers>
{
    typedef IncludeBases<IncludeBaseClassesOfMembers> Inherited;
    DeepAttributeFunction(Function& function):function_(function)
    {}
    template<class ReflectedClass> void
    operator()(ReflectedClass& dataTuple)const
    {
        function_(dataTuple);    // useful when printing a baseclass
        typename Inherited::MemberTraversionType traversionType;
        depthFirstForeachPassTag(dataTuple,function_,MemberKinds(),
                            traversionType);
    }
    template<class ReflectedClass> void
    operator()(ReflectedClass& lhsTuple, ReflectedClass& rhsTuple)const
    {
	  // this gets called when a base class is entered    
        function_(lhsTuple, rhsTuple);                                          
        typename Inherited::MemberTraversionType traversionType;
        depthFirstForeachPassTag(lhsTuple, rhsTuple,function_,MemberKinds(),
                            traversionType);
    }
    Function& function_;
};

To apply a user defined function recursively depth-first on each attribute of a ReflectedClass and recursively depth-first on each attribute of each base class of that class I need to construct an attribute-wise depth-first traversion and pass that to the foreachBaseClass algorithm.

template<class ReflectedClass, class Function, class MemberKinds>
void depthFirstForeachIncAllBaseClasses(ReflectedClass& dataTuple, 
                                        Function& function,
                                        MemberKinds)
{
    DeepAttributeFunction<Function,MemberKinds,true> 
                            depthFirstIteration(function);
    foreachBaseClass(dataTuple,depthFirstIteration);
    depthFirstIteration(dataTuple);
}

The foreachBaseClass algorithm in turn needs to know the list of all already handled virtual base classes (which will be empty at this point), send the user defined function over each base class and after that send the user defined function to the most derived class as well.

template<class ReflectedClass, class CompileTimeRecursion> 
void foreachBaseClass(ReflectedClass& dataTuple, CompileTimeRecursion& ctRecursion)   
{
    typedef typename Loki::TL::MakeTypelist<>::Result EmptyList;
    AllBaseClasses<ReflectedClass,EmptyList>::doForeach(dataTuple,ctRecursion);
    ctRecursion(dataTuple);
}

		

Back to our usage example of PrintRecord.

template<class ReflectedClass> void PrintRecord::print(const ReflectedClass& PrintThis)  
{        
    . . .
    depthFirstForeachIncAllBaseClasses(PrintThis,*this, 
                            TraverseInstanceAndClassVariables()); //(1)
    . . .

}       

Line (1) will instantiate depthFirstForeachIncAllBaseClasses(ReflectedClass&, Function&, MemberKinds) with PrintRecord as Function and TraverseInstanceAndClassVariables as MemberKinds.
This in turn will instantiate foreachBaseClass(ReflectedClass&, CompileTimeRecursion&) with DeepAttributeFunction<PrintRecord, TraverseInstanceAndClassVariables, true> as CompileTimeRecursion.

Maybe you have noted that printing an inheritance graph where the base classes had no state did print only the classnames of the base classes. That was so, because this instantiation of foreachBaseClass calls (through the BaseClassVisitor) DeepAttributeFunction<PrintRecord,.>::operator() with each base class of ReflectedClass as parameter, which calls a PrintRecord::operator() overload with the base class as parameter and this overload finally prints the class name of that base class on a stream:

template<class ReflectedClass> void PrintRecord::operator()(const ReflectedClass& PrintThis)  
{        
    stream_ << ReflectedClass::getClassName() << ":\t";
}

(Afternote: I know I did a lousy job in explaining what's going on here but you might have seen that the matter is not really simple)

Last revised: September 13, 2004 Copyright 2004 Arne Adams