The Artima Developer Community
Sponsored Link

The C++ Source
Enforcing Code Feature Requirements in C++
by Scott Meyers
September 23, 2008

<<  Page 2 of 4  >>


Relaxing feature constraints

Callers will occasionally wish to explicitly relax constraints for a call. For example, a thread-safe function may wish to call another function not guaranteed to be thread-safe, because the call is made in a context where the thread-safety of the called function is not of concern (e.g., while holding a lock on all data accessed by the called function). There are two ways to relax feature constraints for a call. The easiest is to pass an object of type IgnoreFeatures as the feature set object. That causes all feature constraints to be ignored, i.e., to treat the call as if the calling function had no feature requirements:

void g(MakeFeatures<TEPSafe>::type features)  // as before 
  int xVal, yVal;
  f(xVal, yVal, IgnoreFeatures());            // fine, g's feature requirements are
  ...                                         // ignored

IgnoreFeatures itself is simply a typedef for a feature set type created from an empty container of features:

typedef MakeFeatures< mpl::vector<> >::type IgnoreFeatures;

The second way to relax feature constraints for a call is to create a new feature container with fewer features than the calling function usually requires. This is generally accomplished by erasing features from the function's MakeFeatures parameter and naming the result. The MPL supports only functional constructs, so there is no way to modify the contents of an MPL container after the container has been created. Erasing a type from an MPL container yields a new container; the original is unchanged. To eliminate only the Portable requirement in the call from g to f, the following code can be used:

void g(MakeFeatures<TEPSafe>::type features)             // as before 
  typedef eraseVal<TEPSafe, Portable>::type              // remove Portable from
          RevisedFeatures;                               // TEPSafe and name the
                                                         // result “RevisedFeatures”

  f( xVal, yVal, MakeFeatures<RevisedFeatures>::type()); // call f with RevisedFeatures

The MPL has no eraseVal metafunction, but it's easy to write, based on other MPL and Boost functionality:

template<typename Seq, typename T> // code explanation is below
struct eraseVal
: mpl::copy_if<Seq, mpl::not_<boost::is_same<_1,T> > >

Conceptually, this code says “eraseVal takes a type sequence Seq (e.g., an mpl::vector) and a type T, and it creates a new sequence by copying every type in Seq that is not the same as T.” Details on the syntax and semantics of the MPL are beyond the scope of this paper; interested readers are encouraged to consult the MPL documentation.1,10

Enforcing feature set constraints

Compile-time enforcement of feature requirements is based on the observation that in a call from a function requiring features to a function offering features, there are two feature set objects: the caller's (the argument passed) and the callee's (the formal parameter). The type of the caller's object is MakeFeatures<NeededFeatures>::type, while the type of the callee's is MakeFeatures<OfferedFeatures>::type. If these are the same type, the type needed and the type offered are identical, and the call succeeds. If they are not the same type, the call should succeed only if all the types in NeededFeatures are present in OfferedFeatures. But if MakeFeatures<NeededFeatures>::type (i.e., Tneeded) and MakeFeatures<OfferedFeatures>::type (Toffered) are different types, C++ specifies that the call is valid only if there is an implicit conversion from Tneeded to Toffered. The challenge is to design things so that only the appropriate conversions are available.

A complicating factor is that functions may be overloaded on their feature set types. Consider two declarations for an overloaded function g:

typedef boost::mpl::vector<ThreadSafe, ExceptionSafe> TESafe;             // as before
typedef boost::mpl::vector<ThreadSafe, ExceptionSafe, Portable> TEPSafe;  // as before

void g(parameters, MakeFeatures<TESafe>::type);   // call this function gTE

void g(parameters, MakeFeatures<TEPSafe>::type);  // call this function gTEP

Consider also a function f1 that requires only portability and that calls g:

typedef boost::mpl::vector<Portable> PSafe;
void f1(parameters, MakeFeatures<PSafe>::type features)
  g(parameters, features);  

This should unambiguously call gTEP (the version of g whose feature set is based on TEPSafe), i.e., that includes the Portable feature. In general, there should be an implicit conversion from Tneeded to Toffered if and only if all the features used to build Tneeded are also present in Toffered.

Consider now a function f2 that requires only thread safety and that calls g:

typedef boost::mpl::vector<ThreadSafe> TSafe;
void f2(parameters, MakeFeatures<TSafe>::type features)
  g(parameters, features);  

Both versions of g satisfy f2's requirements, so it would seem that the call is ambiguous. However, gTEP offers more unnecessary features than gTE, and the ambiguity would be avoided if we preferred fewer unnecessary features to more. If we assume that offering code features (i.e., imposing constraints on function implementers) may incur a runtime cost, it seems desirable to avoid imposing such costs on callers when we do not have to. The policy, therefore, is to prefer conversions among feature set types that add as few unnecessary features as possible. This policy dictates that in the call from f2 to g above, gTE should be unambiguously selected as the target function.

Conversions among feature set types should thus obey these two rules:

The behavior dictated by these rules can be achieved by use of an inheritance hierarchy, where each class in the hierarchy is a feature set type.

Inheritance hierarchy for feature sets

Figure 3: Inheritance hierarchy for feature sets comprised of features A, B, C, and D. All inheritance links are virtual. Highlighted parts of the figure are those needed for the feature set {B,C}.

Figure 3 shows the hierarchy for combinations of up to four features, where the features are named A, B, C, and D. The structure of the hierarchy makes clear that implicit conversions may only add features (i.e., no conversion exists if a caller requests more features than a callee offers) and that conversions adding fewer features are preferred over conversions adding more. To prevent ambiguity when more than one inheritance path leads from the source to the target of an allowed conversion, all inheritance links are virtual. This makes it possible, for example, for a caller requiring only feature B to unambiguously invoke a callee offering features A, B, and C, even though there is more than one inheritance path from the class for {B} to the class for {A,B,C}.

The central difficulty in compile-time feature constraint enforcement is implementing the MakeFeatures template such that a suitable inheritance hierarchy is automatically generated and that MakeFeatures<Features>::type is the appropriate class in that hierarchy. In general, a hierarchy such as shown in Figure 3 need not be generated in full. Rather, only the part of the hierarchy corresponding to Features and its supersets need be created. Figure 3 highlights the portion of the hierarchy that must be generated to support the conversions applicable to the feature set {B,C}.

The implementation, which is heavily based on code posted by Watanabe,21 is shown in Listings 1 and 2. Readers unfamiliar with the MPL are again encouraged to consult the library's documentation for details on its syntax and semantics. What follows is an overview of the implementation, the goal being to convey the essence of the approach employed.

1 namespace CodeFeatures { 
2   namespace mpl = boost::mpl; 
3   using mpl::_1; 
4   using mpl::_2; 

5   template<typename S, typename T> 
6   struct IndexOf: 
7     mpl::distance<typename mpl::begin<S>::type, 
8                   typename mpl::find<S, T>::type> 
9   {}; 

10   template<typename Unordered> 
11   struct Order: 
12     mpl::sort<Unordered, 
13               mpl::less<IndexOf<AllCodeFeatures, _1>, 
14                         IndexOf<AllCodeFeatures, _2> > > 
15   {}; 

16   template<typename CF> 
17   struct MakeFeatures { 
18     typedef 
19       Features<typename mpl::copy<typename Order<CF>::type, 
20                                   mpl::back_inserter<mpl::vector0<> > >::type> 
21       type; 
22   }; 

23 } 

Listing 1: Implementation of MakeFeatures.

The MakeFeatures metafunction itself is defined in lines 16-22 of Listing 1. Its parameter, CF, is an MPL collection of feature classes. The MPL supports several types of collections, including vector, list, and set, but parts of the code used to enforce feature constraints are applicable only to vector and deque, so lines 19-20 use mpl::copy to copy the feature classes in CF into a vector. Prior to the copy, the feature classes are put into a canonical order (via the call to Order on line 19) so that all permutations of feature classes corresponding to the same set of features are represented by a single type in the hierarchy. (Hence, MakeFeatures<mpl::vector<A,B> >::type and MakeFeatures<mpl::vector<B,A> >::type yield the same type.) The code to perform the ordering is on lines 10-15 and 5-9 (the latter being invoked by the former via the call to mpl::sort on lines 12-14).

1 namespace CodeFeatures { 
2   namespace mpl = boost::mpl; 
3   using mpl::_1; 
4   using mpl::_2; 
5   using mpl::_; 

6   template<typename Base1, typename Base2>
7   struct VirtualInherit : virtual Base1, virtual Base2 {}; 

8   template<typename S> 
9   struct MakeFeatures; 

10   template<typename S1, typename S2> 
11   struct Difference: 
12     mpl::remove_if<S1, mpl::contains<S2, _ > >
13   {}; 

14   template<typename Present, typename Omitted> 
15   struct GetFeaturesBases: 
16     mpl::transform<Omitted, MakeFeatures<mpl::push_back<Present, _> > > 
17   {}; 

18   template<typename S> 
19   struct Features: 
20     virtual mpl::fold< 
21       typename GetFeaturesBases<S, 
22                                 typename Difference<AllCodeFeatures, S>::type 
23                                >::type, 
24       mpl::empty_base, 
25       VirtualInherit<_, _> 
26     >::type 
27  {}; 

28 } 

Listing 2: Implementation of Features.

The type returned by MakeFeatures is an instantiation of the Features template, which is defined on lines 18-27 of Listing 2. Behaviorally, Features instantiations correspond to the classes in Figure 3. Each Features class virtually inherits (line 20) from mpl::fold<...>::type, which is a typedef for an instantiation of VirtualInherit, a template defined on lines 6-7. VirtualInherit itself inherits from two bases, so the local hierarchy around each Features instantiation is as shown in Figure 4.

Local inheritance structure

Figure 4: Local inheritance structure of Features instantiations.

As this figure suggests, no class in the hierarchy generated by MakeFeatures has more than two base classes, and that means MakeFeatures-generated hierarchies cannot have the structure depicted in Figure 3. For type conversion purposes, however, they can act as if they did, because inheriting from three base classes B1, B2, and B3 is behaviorally the same as inheriting from two base classes: B1 and VirtualInherit<B2,B3>.

The actual hierarchy generated from the code in Listing 2 for inheritance from B1, B2, and B3 is somewhat more complicated than this, but the insight that direct inheritance from an arbitrary number of base classes can be emulated by indirect inheritance from hierarchy of intermediate classes like VirtualInherit is the key to understanding how a hierarchy using no more than two base classes per class can, for purposes of implicit type conversion, behave like a hierarchy where classes have a greater number of bases.

Features<S> is the type in the hierarchy representing the set of feature classes in S. The hierarchy above it is generated by mpl::fold, which behaves similarly to the STL accumulate algorithm. mpl::fold takes a sequence of types on which to operate (lines 21-23 of Listing 2), an initial state (mpl::empty_base on line 24), and a binary operator to apply to the current type and the current state (VirtualInherit on line 25). In this case, the result is that mpl::fold iteratively takes a missing feature mf not in S and adds Features<S+mf> as an (indirect through VirtualInherit) base class. Features<S+mf> then applies mpl::fold again to create the hierarchy above it, and this proceeds recursively until Features classes for all supersets of the features classes in S have been generated as (indirect) bases of Features<S>.

<<  Page 2 of 4  >>

Sponsored Links

Copyright © 1996-2018 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use