ACCU Home page ACCU Conference Page
Search Contact us ACCU at Flickr ACCU at GitHib ACCU at Google+ ACCU at Facebook ACCU at Linked-in ACCU at Twitter Skip Navigation

pinFrom Mechanism to Method:

Overload Journal #59 - Feb 2004 + Programming Topics   Author: Kevlin Henney

Further Qualifications

Qualification is often used as a simple constraint on behavior. For instance, a non-const member function cannot be executed on a const-qualified object. In the general case, a const-qualified member function can be used with both const- and non-`const qualified objects; the exception is when the function is also overloaded privately as non-const. This exception highlights the other common use of qualification to distinguish between two functions and two different outcomes, although normally in a more substitutable fashion (i.e., so that the non-const version is effectively a subtype specialization of the const version [Henney2001a]).

Qualification, Separation, and Unification

You can see this kind of substitutability in action with iterator access in the C++ Standard's container requirements: non-const container access yields iterators whereas const container access yields const_iterators, and, furthermore, an iterator may be used where a const_iterator is expected. In this case, qualification-based separation leads to iterator and const_iterator types.

Qualification can also be used as a means for unification. Consider an object that supports both reader locks and writer locks for safe multithreaded access: so long as there are no writers, multiple reader locks can be acquired and the owners can look at the object without changing it (i.e., only const operations); the owner of a writer lock has exclusive read-write access to an object (i.e., both const and non-const operations). Translating these concepts directly into code suggests the following:

class table 
{
public:
  void lock() const;   // acquire lock for reading
  void lock();         // acquire lock for
                       // reading and writing
  void unlock() const; // release reader lock
  void unlock();       // release writer lock
  ...
};

The acquisition and release of the lock now reflects the permissions of the calling context:

void reader_example(const table *target) 
{
  target->lock(); // acquires lock for reading
  ...
  target->unlock(); // releases reader lock
}
void writer_example(table *target) 
{
  target->lock(); // acquires lock for
  // reading and writing
  ...
  target->unlock(); // releases writer lock
}

Such access is made exception safe by introducing an acquisition-release object [Stroustrup1997, Henney2000a]:

template<typename lockee_type>
class locker 
{
public:
  locker(lockee_type &target) : target(target) 
  {
    target.lock(); 
  }
  ~locker() 
  {
    target.unlock();
  }
private:
  locker(const locker &);
  locker &operator=(const locker &);
  lockee_type &target;
};

What's neat about this design is that only a single locker template is needed to cater for both const and non-const variants:

void reader_example(const table *target) 
{
  locker<const table> guard(*target);
                     // acquires reader lock
  ...
}
void writer_example(table *target) 
{
  locker<table> guard(*target);
              // acquires writer lock
  ...
}

Code that is written to be both scope constrained and const correct will avoid pessimistic locking scenarios, where a lock is acquired for longer than is strictly necessary or the lock acquired is too strong for the required access.

Write-Back Proxies

Consider a slightly different scenario: objects that can be loaded on demand into memory and, when changed, written back. It is safe to assume that non-const operations will cause change and const operations won't, and that users will perform predominantly const or non-const operations on a given object in a particular role:

class datapoint 
{
public:
  double upper_bound() const;
  void upper_bound(double);
  double lower_bound() const;
  void lower_bound(double);
  ...
};

The only problem is that the objects are independent of your loading and saving framework. They do not contain convenient features that would make this problem trivial to resolve, such as a dirty flag to show when they've been modified. A simplistic, verbose, and errorprone approach would be to save or not in response to each call:

void view(const datapoint *target) 
{
  double = target->upper_bound();
  // no save required
  ...
}
void manipulate(datapoint *target,
                double new_upper_bound) 
{
  ...
  target->upper_bound(new_upper_bound);
  // save required
  save(target); // assume a non-member
  // save for target
}

This code also assumes that the object has been preloaded into memory.

Custom Proxies

The standard solution to such problems is to manage the level of indirection with a proxy object [Buschmann-, Gamma-et-al]. A custom proxy, written to handle each of the member functions individually, can be written to encapsulate both the lazy loading and the save policy:

class datapoint_view 
{
public:
  double upper_bound() const 
  {
    if(!target)
      load();
    return target->upper_bound();
  }
  void upper_bound(double new_upper_bound) 
  {
    if(!target)
      load();
    target->upper_bound(new_upper_bound);
    save();
  }
  ...
private:
  void load() const;
  void save();
  mutable datapoint *target;  // null when
                              // not loaded
  persistence_key target_key; // used by load
};

Clients now work in terms of datapoint_view instead of datapoint. Although conventional, proxies and targets do not necessarily have to inherit from a common base class, in this case, unless the datapoint author included an interface class for another reason, it may not even be possible to perform such inheritance without further adaptation.

However, although simple in many ways, this design is tediously repetitive. Each function follows a similar flow: load if not yet loaded, forward call, and then optionally a call to save state. It is also hardwired to a single target type. A generic solution would allow arbitrary data types to be managed in the same way. Smart pointers offer the most common idiom for such generic managed indirection.

Smart References

Consider first a simple case for a generic loading-and-saving smart pointer: working with built-in types or user-defined value types that, like built-ins, are manipulated only in terms of operators. The focus of operations is, therefore, on the dereferenced value. Another proxy variant, a smart reference, allows basic reads and writes to be distinguished:

template<typename target_type>
class loading_ptr {
public:
  ...
  class reference 
  {
  public:
    explicit reference(const loading_ptr *that)
      : that(that) {}
    operator target_type() const 
    {
      return *that->target;
    }
    reference &operator=(const target_type &rhs) 
    {
      *that->target = rhs;
      that->save();
      return *this;
    }
  private:
    const loading_ptr *that;
  };

  reference operator*() const 
  {
    if(!target)
      load();
    return reference(this);
  }
  ...
private:
  ...
  friend class reference;
  void load() const;
  void save() const;
  mutable target_type *target; // null when
  // not loaded
  persistence_key target_key;  // used by load
};

A smart reference cannot be a perfect match for a real reference [Meyers], but such a limitation on transparency is true to a greater or lesser extent of any kind of proxy. For instance, the UDC (user-defined conversion) operator means that the result of dereferencing a loading_ptr is an rvalue rather than an lvalue. The disadvantage of the UDC as it stands is that it uses up the allotment of one userdefined conversion. A little generic thinking gets round this problem:

template<typename target_type>
class loading_ptr 
{
public:
  ...
  class reference 
  {
  public:
    ...
    template<typename result_type>
    operator result_type() const 
    {
      return *that->target;
    }
    ...
  private:
    loading_ptr *that;
  };
  ...
};

The downside is that this permissive conversion can create some fresh new ambiguities: the templated UDC now eagerly matching all possibilities unless explicitly disambiguated. You have to choose between evils according to which least affects your code - I guess that you probably don't need reminding that the world is not a perfect place.

Almost all the overloadable operators can be overloaded to make working with the smart reference reflect the natural use of its target type more accurately. This is fine for built-in types and like-minded value classes, but not for targets with named members: for them, operator-> must be overloaded.

Bracketing Smart Pointers

But over-eagerness to implement operator-> will lead you straight into a brick wall:

template<typename target_type>
class loading_ptr {
public:
  ...
  target_type *operator->() const 
  {
    if(!target)
      load();
    return target;
  }
  ...
};

Sure, the object may have been successfully loaded into memory, but when and how will it be saved? The save needs to occur after the pointer has been returned and a member dereferenced through it - in other words, outside the body of operator-> over which you have control.

It would appear that you can never have too many proxies: the solution is to return a smart pointer from loading_ptr's operator-> and have its destructor perform the save:

template<typename target_type>
class loading_ptr 
{
public:
  ...
  class pointer 
  {
  public:
    explicit pointer(const loading_ptr *that)
      : that(that), accessed(false) 
    {
    }
    target_type *operator->() const {
      accessed = true;
      return that->target;
    }
    ~pointer() 
    {
      if(accessed)
      that->save();
    }
  private:
    const loading_ptr *that;
    bool accessed;
  };
  pointer operator->() const 
  {
    if(!target)
      load();
    return pointer(this);
  }
  ...
private:
  friend class pointer;
  ...
};

What makes this idiom tick is that operator-> chains: if the result of operator-> also supports an operator->, this latter operator is called automatically, and so on until the result chain reaches a real pointer. What makes this idiom tock is the binding of a temporary object's lifetime to the end of the surrounding full expression. So, when used in a simple expression, the load is performed in the first operator->, which returns a temporary object used to access the members - either function or data - of the underlying target, and the save is performed by the destruction of the temporary object at the end of the expression:

void manipulate(loading_ptr<datapoint> target,
                double new_upper_bound) 
{
  ...
  target->upper_bound(new_upper_bound);
  // ^load if necessary ^save
}

This versatile bracketing technique has acquired various names over time: locking pointer in the context of thread synchronization [Henney1996], call wrappers [Stroustrup2000], and execute-around pointers [Henney2000b].

The Depths of Qualification

But before you get too distracted or overwhelmed by the many levels and kinds of proxy you have at your disposal, remember that part of the design requirement was to distinguish between const and non-const usage. The code currently assumes the non-const case (i.e., always save). How can you distinguish a const target?

A common, but alas incorrect, solution to this problem is to reflect the qualification of the smart pointer in the qualification of the result:

template<typename target_type>
class loading_ptr 
{
public:
  ...
  pointer operator->() 
  {
    if(!target)
      load();
    return pointer(this);
  }
  const target_type *operator->() const 
  {
    if(!target)
      load();
    return target; // return actual pointer as
                   // no save needed
  }
  ...
};

There are certainly designs in which you would want such deep qualification, but this isn't one of them. For a composition relationship through a pointer, where an object pointed to by another is considered a part of a whole, qualification should run deeply, just as it does for a data member by value. For association, where the relationship represented is not whole-part, qualification should be shallow, which is the case for many indirection-based relationships. Making it deep arises from confusion - albeit commonplace - over levels of indirection: the qualification of your smart pointer relates to whether or not you can affect the smart pointer itself, not its referand.

Many Roads Lead to Rome

There are two user roles with respect to target usage for the writeback proxy: a read-only role, which we can equate to accessing a const target, and a write-mostly role, which we can equate to accessing a non-const target and typically accessing non-const members. If deep qualification were the only solution to this kind of problem, iterators to const containers would be stuck on the starting blocks. The good news is that not only is there a solution, there are many solutions, each with a different set of tradeoffs.

Separately Qualified Types

Taking a leaf straight out of the standard library, the iterator model can be used as the inspiration for a pair of class templates:

template<typename target_type>
class loading_ptr 
{
public:
  ...
  class pointer 
  {
    ...
  };
  pointer operator->() const 
  {
    if(!target)
      load();
    return pointer(this);
  }
  ...
};

template<typename target_type>
class const_loading_ptr 
{
public:
  const_loading_ptr(
            const loading_ptr<target_type> &);
  ...
  const target_type *operator->() const 
  {
    if(!target)
      load();
    return target;
  }
  ...
};

Note the converting constructor from a loading_ptr to a const_loading_ptr. This could also be supported by introducing a UDC to a const_loading_ptr in the loading_ptr template. Either way, a loading_ptr is substitutable for a const_loading_ptr. Note also that there is potentially a certain amount of duplicated code. A simple alternative that offers both substitutability and factoring of common code is to introduce an inheritance relationship:

template<typename target_type>
class const_loading_ptr 
{
  ...
};
template<typename target_type>
class loading_ptr
  : public const_loading_ptr<target_type> 
{
  ...
};

Some members will be fully "specialized" and "overridden" in the derived class (i.e., operator-> will be provided in loading_ptr and will block the one in const_loading_ptr from view). This is compile-time polymorphism rather than run-time polymorphism - there are no virtual functions in sight, nor should there be.

Qualified Type Specialization

The const_loading_ptr solution is OK except that it leaves us with two different type names. This means that for an arbitrary type T, which may or may not be const qualified, you cannot simply write loading_ptr<T> and expect it to do the right thing (i.e., loading_ptr<const datapoint> is not equivalent to const_loading_ptr<datapoint>). Template specialization with respect to qualification offers a simplification [Henney2001b]:

// primary class template
template<typename target_type>
class loading_ptr 
{
public:
  ...
  class pointer 
  {
    ...
  };
  pointer operator->() const 
  {
    if(!target)
      load();
    return pointer(this);
  }
  ...
};
// partial specialization
template<typename target_type>
class loading_ptr<const target_type> 
{
public:
  loading_ptr(
        const loading_ptr<target_type> &);
  ...
  const target_type *operator->() const 
  {
    if(!target)
      load();
    return target;
  }
  ...
};

This means that one template name, loading_ptr, covers both cases, with loading_ptr<datapoint> corresponding to the primary template definition and loading_ptr<const datapoint> corresponding to the partial specialization. Inheritance can again be used to provide substitutability and cure the common code:

// forward declare primary class template
template<typename target_type>
class loading_ptr;
// partial specialization
template<typename target_type>
class loading_ptr<const target_type> 
{
  ...
};
template<typename target_type>
class loading_ptr
  : public loading_ptr<const target_type> 
{
  ...
};

It is worth pointing out that not all compilers support specialization with respect to qualification.

Explicit Qualification Check

There are only a few parts of the loading_ptr template that need to be different between the const and non-const variant. Instead of partially specializing the whole class template, why not just do so for the affected functions? This is an elegant and economic idea; unfortunately it also won't work: the C++ Standard currently disallows partial specialization of function templates. You can overload or fully specialize a function template, but alas neither of these options is directly suitable for the member functions in this particular problem.

However, the effect of const partial specialization can, to a limited degree, be emulated. Instead of focusing on the loading_ptr, focus on the result of operator->. Return the pointer proxy in each case and determine only in the destructor whether or not a save is required.

Here is a brute force run-time type checked approach:

template<typename target_type>
loading_ptr<target_type>::pointer::~pointer() 
{
  if(accessed &&
       typeid(target_type *)
       != typeid(const target_type *))
    that->save();
}

Because typeid ignores top-level qualifiers, the code is phrased in terms of pointers. The trick that allows the const discrimination to work is to recall that const qualifying something that is already const qualified has no effect. However, this approach lacks both elegance and economy. You can eliminate the run-time type check by introducing a predicate:

template<typename target_type>
loading_ptr<target_type>::pointer::~pointer() 
{
  if(accessed && !is_const(that->target))
    that->save();
}

Here, it is overloading with respect to const that allows the predicate approach to work:

template<typename type>
bool is_const(type *) 
{
  return false;
}
template<typename type>
bool is_const(const type *) 
{
  return true;
}

If these functions are inlined - and your compiler is doing at least a halfway decent job with inlining - there will be no run-time overhead in this approach. Compile-time selection is the territory of traits - a far more elegant approach:

template<typename target_type>
loading_ptr<target_type>::pointer::~pointer() 
{
  if(accessed && !is_const<target_type>::value)
    that->save();
}

The following mono-trait class template uses const partial specialization to make the distinction:

template<typename type>
struct is_const 
{
  static const bool value = false;
};
template<typename type>
struct is_const<const type> 
{
  static const bool value = true;
};

This approach can also be made to work using const-qualified pointers and partial specialization [Boost] if your compiler does not support direct const specialization.

Qualified Double Dispatch

There is a way to have selection without explicit control flow and to simulate the partial specialization of function templates. Double dispatch allows you to select an action on an object externally based on the type of the object. A family of functions performs the selection on your behalf calling back on the object you pass. This is normally described in terms of different classes in a hierarchy and forms the basis of the conventional form of the VISITOR pattern [Gamma-et-al]. We can also frame double dispatch in terms of qualification, which is simply a different, more constrained form of subtyping.

Depending on the kind of extensibility you want in your design, you can define your dispatch functions either outside or inside the class. The following code uses class statics to retain some consistency with the previous solutions:

template<typename target_type>
class loading_ptr {
public:
  ...
  class pointer 
  {
  public:
    ...
    ~pointer() 
    {
      if(accessed)
        save(that); // select appropriate
                    // save strategy
    }
  private:
    template<typename save_type>
    static void save(
         loading_ptr<save_type> *that) 
    {
      that->save();
    }
    template<typename save_type>
    static void save(
         loading_ptr<const save_type> *) 
    {
      // do nothing as no save is needed
    }
    loading_ptr *that;
    bool accessed;
  };
  ...
};

If overloading with respect to the full loading_ptr type does not work for your compiler, restructure the code so that you overload with respect to the target pointer.

Conclusion

Overloading with respect to qualification combines with templates to provide a valuable form of subtyping and specialization. Whilst not all of the techniques demonstrated are within reach of all compilers, there is enough overlap between their applicability to allow you some implementation wriggle room.

The write-back proxy allows a number of issues to be explored, although it is not intended to demonstrate all that you would need in such a design. For instance, matters of object lifetime and thread synchronization have been glossed over. There is also an important assumption in the applicability of the core design: if the non-const access is not write mostly there will be a lot of wasted saves. However, as C++ is currently defined there is no way that a proxy can both be made generic and distinguish on the qualification of the actual target member accessed, so this is unfortunately a natural constraint.

References

[Henney2001a] Kevlin Henney. "From Mechanism to Method: Good Qualifications," C/C++ Users Journal C++ Experts Forum, January 2001, www.cuj.com/experts/1901/henney.htm

[Stroustrup1997] Bjarne Stroustrup. C++ Programming Language, 3rd Edition (Addison-Wesley, 1997).

[Henney2000a] Kevlin Henney. "C++ Patterns: Executing Around Sequences," EuroPLoP 2000, July 2000, also available from www.curbralan.com

[Buschmann-] Frank Buschmann, Regine Meunier, Hans Rohnert, Peter Sommerlad, and Michael Stal. Pattern-Oriented Software Architecture: A System of Patterns (Wiley, 1996).

[Gamma-et-al] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley, 1995).

[Meyers] Scott Meyers. More Effective C++: 35 New Ways to Improve Your Programs and Designs, (Addison-Wesley, 1996).

[Henney1996] Kevlin Henney. "C++ Advanced Design Issues: Asynchronous C++," Visual Tools Developers' Academy (Oxford, September 1996).

[Stroustrup2000] Bjarne Stroustrup. "Wrapping C++ Member Function Calls," C++ Report, June 2000.

[Henney2000b] Kevlin Henney. "From Mechanism to Method: Substitutability," C++ Report, May 2000, also available from www.curbralan.com

[Henney2001b] Kevlin Henney. "From Mechanism to Method: Distinctly Qualified," C/C++ Users Journal C++ Experts Forum, May 2001, www.cuj.com/experts/1905/henney.htm

[Boost] Boost library website, www.boost.org

Overload Journal #59 - Feb 2004 + Programming Topics