GenVoca SmartIterator exploration (long)

From: Mat Marcus (mmarcus_at_[hidden])
Date: 2002-01-23 20:20:48

* Intro

About month ago, as an experiment, I tried refactoring parts of Loki 
SmartPtr into a stacked GenVoca model. My goals:

1.	try to develop a deeper understanding of the theory underlying "policy 
based design"
2.	explore issues in designing Dave Abraham's SmartIterator.

My explorations are far from complete. But perhaps some of the ideas will 
be of use in our SmartPtr and policy based design discussions. In this 
article I will endeavor to

1.	discuss a theoretical framework for creating layered designs using 
parametrized inheritance (sometimes referred to as nested inheritance on 
the boost list)
2.	begin refactoring the orthogonal Loki SmartPtr design into a sequence of 
communicating refinement layers
3.	consider some issues in developing a SmartIterator
4.	discuss the separation of the [feature model] Domain Specific Language 
(DSL) from the Implementation Components Configuration Language (ICCL)
5.	employ a compact notation for discussing design alternatives
6. briefly discuss the strucutre of an implementation

Disclaimer: I am not suggesting that this is the best design for a 
SmartPtr, or even a complete design. In fact the GenVoca approach might be 
too big of a hammer for the "simple" layers in the Loki SmartPtr feature 
model. Also, I am not an expert in GenVoca, so my layering or sample 
implementation might not bear any resemblance to what an experienced 
practitioner might produce. Finally, please excuse the formatting as this 
post was autogenerated from some independent Wiki pages I've been working 
on.

* GenVoca

To quote from Krzysztof Czarnecki & Ulrich Eisenecker's seminal book, 
GenerativeProgramming:

" GenVoca is an approach to building software system generators based on 
composing object-oriented layers of abstraction, whereby layers are 
stacked. Each layer contains a number of object classes and the layer 
'above' refines the layer 'below' it by adding new classes, adding new 
methods to existing classes, and so on..."

"...The first step is to identify layers of abstraction in the framework... 
(the next) step is to view each layer as a parametrized component, where 
the layer 'below' becomes a parameter to the layer above it. As you see, a 
given layer can access the classes contained in its parameter, that is, the 
layer 'below' it.... (the final) step is to provide families of 
alternative, parametrized layers, so that we can use them to compose 
different frameworks...GenVoca layers can be implemented in C++ as class 
templates containing member classes..."

"Designing a GenVoca architecture requires the following steps,

1. Identify the main responsibilies in the feature diagrams from the Domain 
Analysis.

2. Enumerate component categories and componenets per category.

3. Identify "uses" dependencies between component categories.

4. Sort the categories into a layered architecture.

5. Write down the GenVoca model."

The GenVoca model originated in the work of Don Batory and O'Malley in the 
late 80's and early 90's. GenVoca makes use of several advanced C++ 
techniques including Domain Specific Languages (DSL's), Implementation 
Component Configuration Languages (ICL's), and configuration generators.

* Original Loki SmartPtr Feature Model

In the original Loki SmartPtr design all "policies" are orthogonal 
policies, there is no Configuration Repository, and no separation between 
the DSL and the ICCL. Examining the Loki SmartPtr header file suggests the 
following Feature Model for the SmartPtr domain.

GenVoca model

    SmartPtr                :   SmartPtr [ElementType,
                                          OwnershipPolicy,
                                          ConversionPolicy,
                                          CheckingPolicy,
                                          StoragePolicy]
    ElementType             :   T

    OwnershipPolicy         :  RefCounted | RefCountedMT
                               | ComRefCounted | RefLinked
                               | DeepCopy
                               | DestructiveCopy | NoCopy

    ConversionPolicy        :  AllowConversion
                               | DisallowConversion

    CheckingPolicy          :  AssertCheck
                               | AssertCheckStrict
                               | NoCheck
                               | RejectNullStatic
                               | RejectNull
                               | RejectNullStrict

    StoragePolicy           :  DefaultSPStorage

Keeping the layers independent has some nice advantages. In this case the 
implementation directly mirrors the presumed feature model for the SmartPtr 
domain. That is, the DSL and the ICCL are one and the same. No elaborate 
template metaprogramming is required. The disadvantage is that the lack of 
communication between layers constrains the implementation somewhat, and 
may limit the framework's power.

Model for Loki SmartPtr using a Configuration Repository
Towards an eventual GenVoca design we can slightly refactor the original 
slightly so that SmartPtr takes a single template parameter representing a 
configuration repository. In this design policies remain orthogonal but we 
migrate them to Config.

GenVoca model

    SmartPtr                : SmartPtr[Config]

Config
    ElementType             :   T

    OwnershipPolicy         :  RefCounted | RefCountedMT
                               | ComRefCounted | RefLinked
                               | DeepCopy
                               | DestructiveCopy | NoCopy

    ConversionPolicy        :  AllowConversion
                               | DisallowConversion

    CheckingPolicy          :  AssertCheck
                               | AssertCheckStrict
                               | NoCheck
                               | RejectNullStatic
                               | RejectNull
                               | RejectNullStrict

    StoragePolicy           :  DefaultSPStorage

* A layered GenVoca model

Here is a first attempt at organizing 'policies' into refinement layers. No 
'policies' reside in the configuration repository.

GenVoca model:

    SmartPtrType           :
                SmartPtr[AssignmentLayer]

    CopyLayer              :
                RefCountedCopier[OptCheckingLayer]
                | RefCountedMTCopier[OptCheckingLayer]
                | COMRefCountedCopier[OptCheckingLayer]
                | DeepCopier[OptCheckingLayer]
                | RefLinkedCopier[OptCheckingLayer]
                | DestructiveCopier[OptCheckingLayer]
                | NoCopier[OptCheckingLayer]

    OptCheckingLayer       :
                AssertChecker[OptConversionLayer]
                | AssertStrictChecker[OptConversionLayer]
                | RejectNullStaticChecker[OptConversionLayer]
                | RejectNullChecker[OptConversionLayer]
                | RejectNullStrictChecker[OptConversionLayer]
                | OptConversionLayer

    OptConversionLayer     :
                PointerConvertible[StorageLayer]
                | StorageLayer

    StorageLayer           :
                DefaultStoredPointer[Config]

Config

    ElementType            :   T

Now that we're beginning to move from independent policies to refinement 
layers our model no longer will serve as a natural DSL. In fact what we 
have is a model for an ICCL. This suggests that we create an accompanying 
DSL. But first let's consider the SmartIterator that Dave Abrahams 
suggested. If we want SmartIterator's we could add an optional iteration 
layer, perhaps at the very top of the model stack. That is,

    OptSmartIteratorType   :
                RandomAccessIterator[SmartPtrType]
                | BidirectionalIterator[SmartPtrType]
                | ForwardIterator[SmartPtrType]
                | SmartPtrType

Of course life isn't quite so simple. We must reconsider the 
OptCheckingLayer since validity checking for iterators is different then 
checking for pointers. We could push the raw duplication protocol down into 
the StorageLayer to try to avoid complicating the CopyLayer. Or maybe a 
different set refinement layers makes sense in the larger Smartiterator 
domain. Perhaps Dave or Jeremy's experince with IteratorAdaptors could be 
prove useful here. We could probably simplify the DSL by determining the 
iterator category with a metafunction. decide w

* A congfiguration generator for the Loki SmartPtr feature model

This section is the most incomplete. The recipe for the configuration 
generator is spelled out in some detail in C&E. But this article is already 
ten pages long and time pressed on. I will flesh this out if the whole 
GenVoca idea generates any interest.

We employ the feature model reverse engineered from Loki SmartPtr as our 
DSL. That is, we have four independent policies that can be specified for a 
given SmartPtr. We would like a users to be able to easily specify policy 
combinations. That is, we would like them to be able to write, for example:

    typename SmartPtrGenerator<T, ref_counted,
                default_storage, assert_checking,
                disallow_conversion>::type;

(Aside: typedef templates would be nice here). The implementation of such a 
SmartPtrGenerator on top of our SmartPtr ICCL is straightforward, using 
standard metaprogramming techniques and I will leave it for another article 
if there is any interest. Or see for example C&E page 587 and page 654.

Note that LokiSmartPtr makes no separation between the DSL and the ICCL. 
There is less (meta-code) and less flexibility. Another C&E quote:

"Generators introduce a separation between the featural desciptions of the 
problem space and the implemenataiotn components in the solution space, 
which allows you to make useful extensions to the implementation components 
(e.g. modify the componenet structure or add new components) without having 
to change the existing client code... Moreover we can even make certain 
extensions to the feature space without changing client code. For example, 
we could append new parameters...to the parameter list expected by the 
generator. By choosing appropriate defaults for the new parameters, 
existing calls to the generator will still work properly."

* Sketch of implementation for a GenVoca SmartIterator

To illustrate this notation I'll outline how one possible C++ 
implementation might look. I'm not including all the member functions or 
all the classes that comprise the layers from the diagram above.

// Begin SmartPtrICCL.h -------------------------------

namespace SmartPtrICCL {
/*
OptSmartIteratorType :
      RandomAccessIterator[SmartPtrType]
      | BidirectionalIterator[SmartPtrType]
      | ForwardIterator[SmartPtrType]
      | SmartPtrType
 */

   template <class SmartPtrType>
   class RandomAccessIterator;

   template <class SmartPtrType>
   class BidirectionalIterator;

   template <class SmartPtrType>
   class ForwardIterator;

/*
CopyLayer              :
      RefCountedCopier[OptCheckingLayer]
      | RefCountedMTCopier[OptCheckingLayer]
      | COMRefCountedCopier[OptCheckingLayer]
      | DeepCopier[OptCheckingLayer]
      | RefLinkedCopier[OptCheckingLayer]
      | DestructiveCopier[OptCheckingLayer]
      | NoCopier[OptCheckingLayer]
*/

   template <class OptCheckingLayer>
   class RefCountedCopier;

   template <class OptCheckingLayer>
   class RefCountedMTCopier;

   template <class OptCheckingLayer>
   class COMRefCountedCopier;

   template <class OptCheckingLayer>
   class DeepCopier;

   template <class OptCheckingLayer>
   class RefLinkedCopier;

   template <class OptCheckingLayer>
   class NoCopier;

/*
OptCheckingLayer       :
      AssertChecker[OptConversionLayer]
      | AssertStrictChecker[OptConversionLayer]
      | RejectNullStaticChecker[OptConversionLayer]
      | RejectNullChecker[OptConversionLayer]
      | RejectNullStrictChecker[OptConversionLayer]
      | OptConversionLayer

*/

   template <class OptConversionLayer>
   class AssertChecker;

   template <class OptConversionLayer>
   class AssertStrictChecker;

   template <class OptConversionLayer>
   class RejectNullStaticChecker;

   template <class OptConversionLayer>
   class RejectNullChecker;

   template <class OptConversionLayer>
   class RejectNullStrictChecker;

/*
OptConversionLayer     :
      PointerConvertible[StorageLayer]
      | StorageLayer

*/
   template <class StorageLayer>
   class PointerConvertible;

/*
    StorageLayer           :
                DefaultStoredPointer[Config]
*/

   template <class Config>
   struct DefaultStoredPointer;
}
// Begin SmartPtrICCL.h -------------------------------

// Begin SmartPtrStorageLayer.h -------------------------------
   #include "SmartPtrICCL.h"

namespace SmartPtrICCL {
    template <class Config>
    struct DefaultStoredPointer : public Config
    {
      typedef typename Config::value_type* PointerType;
      DefaultStoredPointer() {}
      DefaultStoredPointer(PointerType p) : pointee(_p) {}
      PointerType operator->() { return pointee_; }
      friend inline PointerType
      GetImpl(const DefaultStoredPointer<Config>& sp) { ... }
      // ...
    private:
        PointerType pointee_;
    };
}
// End SmartPtrStorageLayer.h -------------------------------

// Begin OptConversionLayer.h -------------------------------
   #include "SmartPtrStorageLayer.h"

namespace SmartPtrICCL {
    template <class StorageLayer>
    struct PointerConvertible : public StorageLayer
    {
   private:
      typedef StorageLayer Inherited;
      typedef typename
         Inherited::Config::PointerType PointerType;
    public:
      PointerConvertible() {}
      PointerConvertible(PointerType p) : Inherited(p) {}
        operator PointerType { return GetImpl(*this); }
    };
}

// End OptConversionLayer.h -------------------------------

// Begin OptCheckingLayer.h -------------------------------

namespace SmartPtrICCL {
    template <class OptConversionLayer>
    struct AssertChecker : public OptConversionLayer
    {
   private:
      typedef OptConversionLayer Inherited;
      typedef typename
         Inherited::StorageLayer::PointerType PointerType;
      typedef typename
         Inherited::StorageLayer::ReferenceType ReferenceType;
   public:
      AssertChecker() {}
      AssertChecker(PointerType p) : Inherited(p) {}
        PointerType operator->()
           { ASSERT(nil != GetImpl(*this));
              return Inherited::operator->(); }
        ReferenceType operator*()
           { ASSERT(nil != GetImpl(*this));
           return Inherited::operator*(); }
    };
}
// End OptCheckingLayer.h -------------------------------

// And so on for all the layers. Of course Copier layer is somewhat
// more interesting. Perhaps we should follow Andrei's approach
// with a Clone member function and let the top layer hook it
// up to assignment and copy construction... We omit the details
// for now.

// Next let's configure a SmartPtr by hand.
// To specify default storage, conversion, assert
// checking and reference counting owenrship we
// write:

 using namespace SmartPtrICCL
    template <class T>
    struct MySmartPtrConfig
    {
        // Assemble the layers
        typedef DefaultStoredPointer<MySmartPtrConfig<T> >
             StorageLayer;

      typedef PointerConvertible<StorageLayer>
             OptConvertiblePointer;

      typedef AssertChecker<OptConvertiblePointer>
             OptCheckingPointer;

      typedef RefCountedCopier<OptCheckingPointer>
             CopyLayer;

        typedef SmartPtr<CopyLayer>
                    type;

        typedef T value_type;
     };

Of course manual construction of Config's is painful and requires end users 
to be familiar with the ICL. This motivates the introduction of the DSL and 
an associated configuration generator for end users to specify SmartPtr in 
a natural way. We leave this for another article if there is interest.

* Final thoughts

Much more can be said about designing with refinement layers regarding 
validation and testing strategies, feature dependency matrixes and so on. 
The configuration generator implementation is an interesting topic in and 
of itself. Anyone interested in discussing this further?

- Mat