Deep Member Traversions (depthfirstforeach.h)

A reflected class may have reflected members that are themselves reflected classes. (So called compile time iterable members). Apart from that a reflected class may have reflected members that are std::container. (So called run time iterable members).
Both variants can be nested arbitrarily. Deep member traversions iterate into iterable members. (Sounds quite simple does'nt it?).

When iterating over members of reflected classes the traversion may need to consider members of base classes or may need to ignore members of base classes (this applies to base classes of attributes as well).

Independent from that, iterations starting with an instance of a reflected class may choose to consider static members only, non-static members only or static and non static members. According to that the type MemberKinds can be any of the following:




Because I did not see a usecase for traversing base classes of attributes but ignoring base classes of the root record there is no (half-) deep traversion which does that. Similarly there is no deep traversion that ignores base classes of attributes but considers base classes of the root record.

Deep traversions follow (dereference) pointers (recursively).

Deep traversions starting with a reflected object

template<class ReflectedClass, class Function, class MemberKinds> void
depthFirstForeach(ReflectedClass& dataTuple, Function& function, MemberKinds);

template<class ReflectedClass, class Function, class MemberKinds>
void depthFirstForeachIncAllBaseClasses(ReflectedClass& dataTuple, 
                                        Function& function,
                                        MemberKinds);

Deep traversions starting with a reflected class

When you only need to iterate over static members of a (root) reflected class then it might be convenient to be able to do so without having to supply the root instance that you don't need:

template<class ReflectedClass, class Function>
void depthFirstForeach(Function& function);

template<class ReflectedClass, class Function>
void depthFirstForeachIncAllBaseClasses(Function& function);

Deep traversions starting with two reflected objects

To be able to generate deep comparisons, the library contains binary overloads of the unary traversions mentioned above (binary and unary refers to the arity of the reflectedclass argument):

template<class ReflectedClass, class Function, class MemberKinds>
void depthFirstForeach(ReflectedClass& lhsRecord, ReflectedClass& rhsRecord,Function& function, MemberKinds);

template<class ReflectedClass, class Function, class MemberKinds>
void depthFirstForeachIncAllBaseClasses(ReflectedClass& lhsRecord, ReflectedClass& rhsRecord, Function& function, MemberKinds);

Other arities

(I did not need n-ary traversions with n > 2, and I did not need n-ary traversions with n > 1 for static members only nor flat n-ary traversions with n > 1, hence I did not bother to implement any of these.)

Graph traversion events

Depth-first traversion was used to print the state of a reflected object on a stream. The following "graph-events" turned out to be useful for that:

A user defined function object must supply suitable overloads of the function call operator for all of these events.
The enter-event functions will be called before the corresponding node is processed and the leave-event functions will be called after the corresponding node is processed.

Hence a user defined attribute function object that can be used with the depth-first algorithm has to define the following function-call operator overloads: (whether Scope and ValueType have to be const or not depends on what your attribute function has to accomplish)

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType&,NameTag, EnterAttributeTag, Scope* = NULL) 
{ /* whatever needs to be done        */} 

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType&,NameTag, LeaveAttributeTag,Scope* = NULL) 
{ /* whatever needs to be done        */} 

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType&,NameTag, EnterReflectedClassTag, Scope* = NULL) 
{ /* whatever needs to be done        */} 

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType&,NameTag, LeaveReflectedClassTag, Scope* = NULL) 
{ /* whatever needs to be done        */} 

template<class Scope,class NameTag,class CollectionType> 
void operator()(CollectionType&,NameTag, EnterCollectionTag, Scope* = NULL) 
{ /* whatever needs to be done        */} 

template<class Scope,class NameTag,class CollectionType> 
void operator()(CollectionType&,NameTag, LeaveCollectionTag, Scope* = NULL) 
{ /* whatever needs to be done        */}
 
template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& , NameTag, EnterCollItemTag, Scope* = NULL)
{ /* whatever needs to be done */        }

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& , NameTag, LeaveCollItemTag, Scope* = NULL)
{ /* whatever needs to be done */        }

finally: what has to happen when traversion reaches leafs (neither compile-time nor run-time iterable items):

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& value,NameTag, Scope* = NULL)
{ /* do something to process a "leaf" value*/         }
				

The default argument for the Scope allows to use the same attribute function object for traversions with a root instance and without an instance of a root reflected class (where the latter of course can only traverse static members of the root (which may include traversing the instance members, base classes and static members of the static members)).
If your attribute function object will allways be used with instances of a reflected class then you won't need to default the scope pointer. (And you can safely rely on that pointer being not NULL).

Because Visual C++ 6.0 does not allow to explicitly specify member template arguments that cannot be deduced, the function call operators for a deep attribute function object have to use slightly different signatures like this:

template<class WrappedScope, class NameTag, class ValueType> 
void operator()(ValueType&,NameTag, EnterReflectedClassTag, WrappedScope) 

Here WrappedScope is an instance of: PassScope<SomeReflectedClass> if the traversion started with an instance of a reflected class as root object and WrappedScope is an instance of PassType<SomeReflectedClass> otherwise. Both WrappedScopes contain a typedef for SomeReflectedClass and additionally PassScope contains a pointer to an instance of SomeReflectedClass where SomeReflectedClass is the scope containing attribute as member variable. The leaf function call operator will have to look so:

template<class WrappedScope, class NameTag, class ValueType> 
void operator()(ValueType& value,NameTag,WrappedScope) 

In general hese overloads can as well be implemented for all tags like this (with the workaround for VC6 described above):

template<class Scope, class ValueType,class NameTag, class WhatEverGraphEvent> 
void operator()(ValueType &, NameTag, WhatEverGraphEvent, Scope*)
{ /* whatever needs to be done for all graph-events*/ }

If your compiler supports partial ordering of function templates (which VC6 does not) then you can combine the general form above with selected events for which the general implementation does not fit - for instance like this:

template<class ValueType, class NameTag,class Scope > 
void operator()(ValueType &, NameTag, Scope*, 
                LeaveAttributeTag)
{ /* special treatment here */ }
		

The interface for binary traversions is quite similar:

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& lhsAttribute, ValueType& rhsAttribute, NameTag,
                EnterAttributeTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done */        }

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& lhsAttribute, ValueType& rhsAttribute, NameTag,
                LeaveAttributeTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done */        }

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& lhsAttribute, ValueType& rhsAttribute,NameTag ,
            EnterReflectedClassTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done */        }

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& lhsAttribute, ValueType& rhsAttribute,NameTag ,
            LeaveReflectedClassTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done */        }

template<class Scope,class NameTag,class CollectionType> 
void operator()(CollectionType& lhsCollection, CollectionType& rhsCollection, 
	NameTag, EnterCollectionTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done */        }

template<class Scope,class NameTag,class CollectionType> 
void operator()(CollectionType& lhsCollection, CollectionType& rhsCollection, 
	NameTag, LeaveCollectionTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done */        }

 
template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& lhsAttribute, ValueType& rhsAttribute , NameTag,
                EnterCollItemTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done */        }

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& lhsAttribute, ValueType& rhsAttribute , NameTag,
                LeaveCollItemTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done */        }
		

When processing pairs of pointers it may happen that only one of the pointers is NULL. A binary attribute function object that has to deal with attributes that are pointers must therefore supply these item function overloads as well:

template<class Scope, class NameTag, class ValueType> 
void operator()(PastEndTag,ValueType& /*rhsValue*/,
                NameTag, Scope* = NULL, Scope* = NULL)
{ /* whatever needs to be done when lhs was a null pointer and rhs was not */ }

template<class Scope, class NameTag, class ValueType> 
void operator()(ValueType& /*lhsValue*/,PastEndTag,
                NameTag, Scope* = NULL, Scope* = NULL)
{ /* whatever needs to be done when rhs was a null pointer and lhs was not */ }
		

(in both cases ValueType will be a dereferenced type) When processing pairs of collections it may happen that the sizes of these collections differ. A binary attribute function object that has to deal with attributes that are containers must therefore supply these item function overloads as well:

template<class Scope, class NameTag, class ValueIter> 
void operator()(PastEndTag,ValueIter /* rhsPos */,ValueIter /* rhsEnd */,
                NameTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done when lhs collection runs out of bullets */ }

template<class Scope, class NameTag, class ValueIter> 
void operator()(ValueIter/* lhsPos */,ValueIter /* lhsEnd */, PastEndTag,
                NameTag, Scope* lhsScope = NULL, Scope* rhsScope = NULL)
{ /* whatever needs to be done when rhs collection runs out of bullets */ }
		

(The compiler will tell you when you do not support these overloads and when an instantiation for some record needs it) All this is fine and beautiful but won't buy a thing if it was not easy to specify what has to happen with leaf values in a binary traversion:

template<class Scope, class NameTag, class ValueType> void 
operator()(ValueType& lhsAttribute, ValueType& rhsAttribute,NameTag, 
           Scope* lhsScope = NULL, Scope* rhsScope = NULL) 
{ /* do something to process corresponding leafvalues */ } 
		

Deep binary traversion is used in the library to compare records (template CompareRecord). When you compare records it may improve the performance to iterate over the attributes only until the comparison result is known.
To cater for that, all flavours of depthfirst traversion that are invoked with instances of root objects infer the need to check an end condition defined by the attribute function object by the presence of a member function bool done()const (or bool done()) in that attribute function. (For Visual C++ 6.0 and GCC 3.2 this alone won't be enough - here you will need to have a nested type named DoneTag (like typedef int DoneTag;) in an attribute function that might want to stop the iteration before each and every member in the root's objectgraph is traversed).

Comparisons are not polymorphic, allthough popular object oriented languages implement comparison in a polymorphic way. When you can compare objects with different most derived types and when these differences have an impact on the result of the comparison then it can be proved that the comparison will not be transitive.
In plain English: you can't compare apples and oranges. Hence you have to be extra careful when CompareRecord is used on polymorphic types (that includes when members of the comparison operands are polymorphic).

I did not see the immediate need to be able to stop flat attribute traversions nor the need to stop deep static member traversions without having a root object - hence these iterations end only after the last attribute of the root object is processed or after an exception is thrown.

Example: generated comparison operators

Due to built in peculiarities a workaround has to be used for VC6 once again.

template<template<class> class ValueCmp = std::less> class CompareRecord
{
public:
    CompareRecord():resultKnown_(false),everyThingTested_(false),result_(false){};
    template<class ReflectedClass> void 
    operator()(const ReflectedClass&, const ReflectedClass&)  
    {/* no op*/}

    template<class Scope, class NameTag, class ValueType> 
    void operator()(const ValueType& lhsValue,const ValueType& rhsValue,
                    NameTag,const Scope* = NULL, const Scope* = NULL)
    {
        typedef ValueCmp<ValueType> Comparison;
        // if it was not performance critical then I would have used a setfunction for result_
        // that checks first whether the result is known.
        // Since this library already may overstress the inlining abilities of a compiler 
        // I skipped that.
        if(!resultKnown_)       
        {                        
            Comparison cmp;     
            result_ = cmp(lhsValue, rhsValue);
            resultKnown_ = result_ ||              // lhs precedes rhs 
                            cmp(rhsValue,lhsValue); // rhs precedes lhs 
        }
    }
    template<class Scope, class NameTag, class ValueType> 
    void operator()(const ValueType&,const ValueType&,NameTag,
                    LeaveAttributeTag,const Scope* = NULL, const Scope* = NULL)
    {
        enum {lastAttribute = (Scope::template AttributePos<NameTag>::value == Scope::NumAttributes - 1)};
        // in a nested structure of reflected classes this may be true when
        // in the outermost class still attributes are to check.
        // but this is no problem as long as no attempt is made to treat the comparison 
        // result at that stage as a comparison result for the outermost class.
        everyThingTested_ = lastAttribute;
    };        

    template<class Scope, class NameTag, class ValueType, class GraphEvent> 
    void operator()(const ValueType&,const ValueType&,NameTag,
                    GraphEvent,const Scope* = NULL, const Scope* = NULL)
    {/* no op*/}

    // lhs collection ran out of bullets
    template<class Scope, class NameTag, class ValueIter> 
    void operator()(PastEndTag,ValueIter /* rhsPos */,ValueIter /* rhsEnd */,
                    NameTag,const Scope* = NULL, const Scope* = NULL)
    {
        // lexicographical sort: "a" < "aa"
        if(!resultKnown_)
        {
            result_ = true;
            resultKnown_ = true;
        }
    }
    // rhs collection ran out of bullets
    template<class Scope, class NameTag, class ValueIter> 
    void operator()(ValueIter/* lhsPos */,ValueIter /* lhsEnd */, PastEndTag,
                    NameTag,const Scope* = NULL, const Scope* = NULL)
    {
        if(!resultKnown_)
        {
            result_ = false;
            resultKnown_ = true;
        }
    }
    // lhs is a null pointer and rhs is not - hence it could be dereferenced
    template<class Scope, class NameTag, class ValueType> 
    void operator()(PastEndTag,const ValueType& /*rhsValue*/,
                    NameTag,const Scope* = NULL, const Scope* = NULL)
    {
        if(!resultKnown_)
        {
            result_ = true;
            resultKnown_ = true;
        }
    }
    // rhs is a null pointer and lhs is not - hence it could be dereferenced
    template<class Scope, class NameTag, class ValueType> 
    void operator()(const ValueType& /*lhsValue*/,PastEndTag,
                    NameTag,const Scope* = NULL, const Scope* = NULL)
    {
        if(!resultKnown_)
        {
            result_ = false;
            resultKnown_ = true;
        }
    }
    bool result()
    {
        if(!resultKnown_ && !everyThingTested_)
            throw std::logic_error("trying to access an undefined comparison result");
        return result_;
    }
    bool done()const
    {
        return resultKnown_;
    }
private:
    bool everyThingTested_;
    bool result_;
    bool resultKnown_;
};

template<class Record> inline bool recordIsLess(const Record& lhs, 
                                            const Record& rhs)
{
    CompareRecord<> comparison;
    depthFirstForeachIncAllBaseClasses(lhs, rhs, comparison, InstanceVariableTag()); 
    return comparison.result();
};
Last revised: September 13, 2004 Copyright 2004 Arne Adams