Dr. Dobb's | Adapting Interface-Incomplete Types at Compile Time

Adapting Interface-Incomplete Types at Compile Time

When an adapter template makes demands that a potential underlying type cannot fulfill, Interred Interface Adaptation can expand the number of adaptable types.

December 01, 2005
URL:http://www.drdobbs.com/adapting-interface-incomplete-types-at-c/184402050

December, 2005: Adapting Interface-Incomplete Types At Compile Time

Matthew Wilson is a software-development consultant for Synesis Software, creator of the STLSoft libraries, and author of Imperfect C++ (Addison-Wesley, 2004) and Extended STL (Addison-Wesley, 2006). He can be contacted at http://imperfectcplusplus.com/.

SFINAE

[This article is, in part, an extract from Matthew's forthcoming book on STL extension, called Extended STL, which will be published by Addison-Wesley in 2006.]

adapter class templates are used to convert a class, or a related group of classes, from an existing interface to a new interface. A standard example of this is the std::stack<> template, which may be used to adapt sequence containers that do not contain stack operations—push(), pop()—into a stack; see Listing 1.

This works because all the features of an underlying container required by the std::stack template are implemented in terms of the public interfaces of the standard std::vector, std::list, and std::deque class templates, including member types size_type and value_type and methods back() and push_back().

The problem I address in this article is what to do when the adapter template makes demands that a potential underlying type cannot fulfill: How do you increase the spectrum of adaptable types by adding flexibility to the adapter? To answer this question, I introduce the technique of Inferred Interface Adaptation (IIA), which is comprised of three template metaprogramming techniques:

Type Detection
Type Fixing
Type Selection

Adapting Interface-Incomplete Types

The Iterator pattern [1] represents enumeration over a collection of elements as a single instance of a type that provides methods for advancing the iteration point and for accessing the element representing the current iteration point. The class template sequence_range (Listing 2) implements Iterator for collection classes that provide STL-like iterators (via begin() and end() methods), and presents iteration and access via the advance() and current() methods. (It's actually a chopped-down version of the class template of the same name in STLSoft's implementation of RangeLib, http://rangelib.org/; see [2, 3].)

To support mutating and nonmutating access to the elements of the underlying collection, the current() method is overloaded. The mutating form returns a (nonconst) reference, the nonmutating form a const_reference. This supports the three call forms in Example 1.

This is const-methods-101, and failing to facilitate this typical behavior in an adapter class would be unnecessarily restrictive. As you'll see, though, meeting such ostensibly straightforward behavioral requirements brings along quite a few complications.

Adapting Immutable Collections

In the real world, not all STL-like collections provide both mutable and immutable semantics. When the underlying collection does not support mutable (non-const) references, there's a problem with the sequence_range adapter previously mentioned. Consider what happens if you use the class in Example 2, a read-only vector.

If you try to adapt this class with sequence_range, you get compile errors in the definition of the member types of sequence_range<ro_vector>. Specifically, the compiler tells you that the adapted class has no member types reference and iterator.

You want the adapter to infer, at compile time, whether it's being used with a type that does not support mutable operations. If not, it defines suitable stand-in types based on the (public) interface of the adapted class. In other words, when adapting ro_vector, you should define sequence_range's reference and iterator member types as the const_reference and const_iterator member types of ro_vector. This would mean the effective definition of sequence_range would be:

template <typename C>
class sequence_range
{
  ...
  const_reference current()
  {
    return *m_current;
  }
  const_reference current() const
  {
    return *m_current;
  }
  ...
private:
  const_iterator m_current;  
  const_iterator m_end;  
};

Inferred Interface Adaptation

The IIA technique consists of three steps:

Infer the interface on the adapted type using Type Detection.
Fix any incompatibilities using Type Fixing.
Define the adaptor type's interface in terms of the actual or fixed types of the adapted type using Type Selection.

Before examining how it works, take a look at how it's used in Example 3. The member value, C_HAS_MUTABLE_INTERFACE, is a compile-time constant that indicates whether the adapted type, C, provides a mutable interface (Type Detection). Next comes the type-fixer template, typefixer_iterator, which defines the putative_iterator member type (Type Fixing). Finally, a type-selector template, select_first_type, selects either the putative_iterator or const_iterator types to define the iterator member type (Type Selection).

Type Selection

Type Selection, a well-established idiom in template metaprogramming, consists of a primary template and a partial specialization; see Example 4. In the general case, where the third Boolean template parameter is nonzero, the first type is selected. In the specific case where the third parameter is false, the second type is selected. Thus select_ first_type<int, char, true>::type is int, and select_first_type<int, char, false>::type is char.

Type Detection

The next problem you must solve is arguably the most mind bending. It involves the use of the SFINAE principle (see the accompanying sidebar), to define a template that can detect member types. Example 5 is a definition of the has_value_type used for detecting whether a class has a value_type member type.

Although this looks like a horrible indigestible mess, it's actually reasonably straightforward once you break it down. For a type T, specializing to has_value_type<T> involves determining which instantiation of the has_value_type_function() template function for T best matches an argument of 0. The second template, involving typename T::value_type const volatile*, is more specific than the one taking any arguments, the ellipsis parameter (...), and can be matched to 0 (since 0 can be a pointer literal as well as an integer literal), for any T that has a member type value_type. This is the Type Detection because has_value_type<T> ::value will be 1 if T has a member type value_type, and 0 if it does not. There's a full specialization of has_value_type for void, although that's not used in the application of the technique as I describe in this article.

The flaw in this technique is that you have to write this code for each member type to be detected because there's not—at least as far as I know—a "meta-meta" mechanism for specifying the name of the member type to a general template + functions set. Hence, it's a fair amount of manual effort, but thankfully there are not that many member types in standard/common usage that must be considered. (You can use macros if you choose, just be careful with the definitions.)

You can now see how to determine the value for C_HAS_MUTABLE_INTERFACE. You choose a member type that only a mutable collection would have (say iterator) and detect it:

template <typename C>

class sequence_range
{
private:
  enum { C_HAS_MUTABLE_INTERFACE = has_iterator_type<C>::value };

In fact, given the imperfect nature of some standard libraries and/or some STL extensions, it's wise to err on the side of caution, and detect several mutable-only member types:

template <typename C>

class sequence_range
{
private:<
  enum { C_HAS_MUTABLE_INTERFACE = has_iterator<C>::value && has_pointer<C>::value };

Type Fixing

You can now detect whether your collection has a mutable interface, and you know how to select a type. All that remains is to fix the types. A naive attempt at this might be Example 6.

The problem here, of course, is that select_first_type is specialized with the types C::reference and C::const_reference. When C is a type that does not have a reference member type, the specialization of select_first_type, and therefore of sequence_range as a whole, is invalid, and compilation errors ensue.

Partial template specialization comes to the rescue again, this time in the form of the fixer_reference primary class template, and its partial specialization:

template <typename T, bool HAS_MEMBER>
struct fixer_reference
{
  typedef typename T::reference reference;
};
template <typename T>
struct fixer_reference<T, false>
{
  typedef void reference;
};

The first parameter, T, is the collection. The second parameter is used to indicate whether the collection has such a member. The primary class template defines the member type reference from the reference member type of the collection. In the partial specialization, where the second template parameter is false to indicate that such a member is not defined, the member type reference is typedefed from void. This is the Type Fixing: According to the classic principle, we've added another layer of abstraction, and are now able to express ourselves in terms of the member type reference of collection types that may not define this type. Now the template expression:

typedef typename typefixer_reference< C, C_HAS_MUTABLE_INTERFACE>::reference putative_reference;

is eminently compilable, whether C_HAS_MUTABLE_INTERFACE is true or false.

If C_HAS_MUTABLE_INTERFACE is true, then typefixer_reference<C, C_HAS_MUTABLE_INTERFACE>::reference evaluates to be C::reference. Thus:

select_first_type<putative_reference, const_reference, C_HAS_MUTABLE_INTERFACE>::type<

evaluates to:

select_first_type<C::reference, C::const_reference, true>::type

which evaluates to C::reference.

If C_HAS_MUTABLE_INTERFACE is false, then typefixer_reference<C, C_HAS_MUTABLE_INTERFACE>::reference evaluates to void. Thus:

select_first_type<putative_reference , const_reference, C_HAS_MUTABLE_INTERFACE>::type

evaluates to:

select_first_type<void, C::const_reference, true>::type

which evaluates to C::const_reference.

At no point have we a type that doesn't exist—in its place is void—and so it is acceptable to the compiler. (Of course, if the adapted type doesn't have const_iterator or doesn't have const_reference, then the compiler will still complain, but expecting adapters to have intelligence to cope in that case is perhaps unreasonable; we can reasonably require users of the sequence_range adapter to use it with types that, at least, provide const_iterator and const_reference member types, along with begin() and end() methods.)

Applying IIA to the Range

Plugging all this back into the sequence_range class template, we have the definition as in Listing 3. Now the adapter works for types that support mutable and immutable operations and for types that support only immutable operations. There are some further complications in the actual definition of the sequence_range in STLSoft's RangeLib to handle parameterization of the adapter with const collection types, but they are also addressed by use of IIA. Feel free to download the STLSoft implementation of RangeLib (as part of the STLSoft distribution at http:// stlsoft.org/downloads.html), and check it out for yourself.

Acknowledgments

Thanks to Bjorn Karlsson, Nevin Liber, and Walter Bright for helping me sort through my nomenclatural perplexity and arrive at a relatively straightforward definition of the constituent elements of the technique of Inferred Interface Adaptation, and for helping me approach readability on what is a very daunting topic.