Introduction

When inside a const member function in C++, calls to other member functions on the same object may be made only if those functions are also const. The sole exception to this is when a cast is employed at the call site, i.e., when the constness of *this is cast away. We can view the constness of const member functions as a code feature, and we can view the rule that prohibits const member functions from calling non-const member functions as a constraint. Constraints prevent code dependent on a feature from invoking code lacking that feature.

The constraint involving const is enforced by C++ compilers, but it is easy to imagine useful code features that are not automatically checked:

• Thread-safe code should be allowed to call only other thread-safe code. Otherwise the result would not be guaranteed to be thread-safe.
• Exception-safe code should be allowed to call only other exception-safe code. Otherwise the result would not be guaranteed to be exception-safe.
• Portable code should be allowed to call only other portable code. Otherwise the code base would not be guaranteed to be portable.

It would be convenient to be able to specify arbitrary code features and have the resulting constraints verified during compilation. This paper describes how that can be achieved in C++.

C++'s enforcement of the constraint on const member functions actually has nothing to do with functions. const functions are simply member functions where the implicit *this object is declared const. What C++ compilers enforce is the rule prohibiting implicit conversion from const T* (pointer to const object) to T* (pointer to non-const object). const member functions are based on the constness of objects, not functions. Nevertheless, their behavior provides a motivation for the development of a way to specify and enforce arbitrary user-defined code feature constraints.

Creating code features

Code features can be created by defining empty “tag” structs, analogous to the structs used in the standard C++ library to represent STL iterator categories.¹⁷ Structs representing features are known as feature classes, analogous to the term traits classes for structs representing traits.^9,17 Here are some example feature classes:

struct ThreadSafe {};
struct ExceptionSafe {};
struct Portable {};

Like those for STL iterator categories, these structs serve only as identifiers. They have no semantics. The meaning of “ThreadSafe” and “Portable” (as well as the enforcement of those meanings, i.e., ensuring that the behavior of a function's code is consistent with the features it claims to offer) is entirely up to programmers.

Combinations of features can be represented by compile-time collections of feature classes, i.e., collections of types. Such collections are easy to create using the MPL library^1,10 for template metaprogramming available at Boost.⁷ The MPL (“Metaprogramming Library”) offers STL-like containers, iterators, and algorithms for working with compile-time information, including types. Code to create a compile-time vector-like container named TESafe that holds the types ThreadSafe and ExceptionSafe, for example, looks like this:

typedef boost::mpl::vector<ThreadSafe, ExceptionSafe> TESafe;

In principle, the proper container for code features is a set, because it makes no sense for a function to offer a feature more than once. The MPL includes a set container, but in Boost version 1.34 (the release current at the time this research was performed), bugs in mpl::set's implementation rendered it unusable for this project. The implementation shown here relies on mpl::vectors instead.

C++ macros can be used to offer clients an easy way to create both feature classes and an MPL container holding all such classes; the “_n” suffix on each macro name indicates how many features are in the universal set. For example,

CREATE_CODE_FEATURES_4(ThreadSafe, ExceptionSafe, Portable, Reviewed);

defines the feature classes ThreadSafe, ExceptionSafe, Portable, and Reviewed, and it also defines an MPL container, AllCodeFeatures, containing each of these types.

Feature constraints and nonvirtual functions

Nonvirtual functions (including non-member functions) document the features they offer through a parameter of type MakeFeatures<FeatureContainer>::type. MakeFeatures is a struct template that acts as a metafunction: a function that executes during compilation. Its result—a type— is accessed via the nested type typedef. MakeFeatures<FeatureContainer>::type thus refers to the type computed by MakeFeatures given an MPL container of types. This type, which we will examine in detail later, corresponds to a set of code features, so we will refer to it as a feature set type and to objects of such types as feature sets.

By convention, functions put their feature set parameter at the end of their parameter list. A function f taking parameters of type int and double and offering the ThreadSafe and ExceptionSafe features (i.e., the features in the container TESafe) would be defined this way:

void f(int x, double y, MakeFeatures<TESafe>::type features)
{ 
   ...     // normal function body
}

The feature set parameter serves an unconventional role, because it's not used at runtime. During compilation, however, it specifies the features that f supports and it participates in ensuring that calls to f requiring unsupported features are rejected.

When invoking a function taking a feature set parameter, the calling function passes an object corresponding to the features it requires. Often, this is the same object it has in its parameter list. For example, consider the following function g, which offers a larger set of code features than f,

typedef boost::mpl::vector<ThreadSafe, ExceptionSafe, Portable> TEPSafe;

void g(MakeFeatures<TEPSafe>::type features); // g offers/requires thread-safe, 
                                              // exception-safe, and portable code

and a call from f to g:

void f(int x, double y, MakeFeatures<TESafe>::type features)
{ 
  ...
  g(features);                                // fine, g offers the features f needs
  ...  
}

The reverse call—from g to f—will not compile, because g requires the Portable code feature, but f does not offer it:

void g(MakeFeatures<TEPSafe>::type features)
{
  int xVal, yVal;
  ...
  f(xVal, yVal, features);                    // error! f doesn't offer the Portable feature
  ...
}

The compilation failure is due to the lack of a conversion from MakeFeatures<TEPSafe>::type to MakeFeatures<TESafe>::type, a problem different compilers report in different ways—some more comprehensible than others. Figures 1 and 2 show the results of submitting the above code to g++ 4.1.1 and Visual C++ 9, respectively. Neither diagnostic is a paragon of clarity, but both identify type conversion as the fundamental problem.

articlecode.cpp: In function 'void g( 
        CodeFeatures::Features< 
            boost::mpl::v_item<
                CodeFeatures::Portable 
              , boost::mpl::v_item< 
                    CodeFeatures::ExceptionSafe 
                  , boost::mpl::v_item< 
                        CodeFeatures::ThreadSafe, boost::mpl::vector0<mpl_::na>
                        , 0 
                    >, 0 
                >, 0 
            > 
        > 
    )': 
articlecode.cpp:32: error: conversion from 'CodeFeatures::Features<
        boost::mpl::v_item< 
            CodeFeatures::Portable 
          , boost::mpl::v_item< 
                CodeFeatures::ExceptionSafe 
              , boost::mpl::v_item< 
                    CodeFeatures::ThreadSafe, boost::mpl::vector0<mpl_::na>, 0 
                >, 0 
            >, 0 
        > 
    >' to non-scalar type 'CodeFeatures::Features<
        boost::mpl::v_item<
            CodeFeatures::ExceptionSafe 
          , boost::mpl::v_item< 
                CodeFeatures::ThreadSafe, boost::mpl::vector0<mpl_::na>, 0 
            <, 0 
        > 
    >' requested 

Figure 1: Diagnostic from g++ for a violated code feature constraint.

articlecode.cpp(32) : error C2664: 'f' : cannot convert parameter 3 from 
'CodeFeatures::Features<S>' to 'CodeFeatures::Features<S>' 
        with 
        [ 
            S=boost::mpl::vector3<CodeFeatures::ThreadSafe,CodeFeatures::ExceptionSafe,CodeFeatures::Portable> 
        ] 
        and 
        [ 
            S=boost::mpl::vector2<CodeFeatures::ThreadSafe,CodeFeatures::ExceptionSafe>
        ] 
        No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called 

Figure 2: Diagnostic from Visual C++ for a violated code feature constraint.

Functions lacking MakeFeatures parameters can call functions that have them by creating the appropriate object prior to or at the point of the call:

void h()                                                // h has no feature set parameter
{
  typedef mpl::container<...> NeededFeatures;           // define features needed by h
  int xVal, yVal;
  ...
  f(xVal, yVal, MakeFeatures<NeededFeatures>::type());  // create anonymous feature set
  ...                                                   // object; call to f succeeds if all
                                                        // features in NeededFeatures
}                                                       // are in TESafe

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:

• Tneeded converts to Toffered only if Toffered has all the features in Tneeded.
• If Tneeded can be converted to more than one Toffered, conversions adding fewer features are preferred to those adding more. If conversions exist to more than one Toffered with the same number of features, the conversion is ambiguous.

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.

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,²¹ 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.

Figure 4: Local inheritance structure of Features instantiations.

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>.

Feature constraints and virtual functions

Virtual functions introduce a new issue, one arising from the C++ rule that virtual function overrides in derived classes must declare the same parameter types as their base class counterparts. A derived class override may be invoked through a pointer or reference to a base class, so the override must certainly offer the code features promised by the base class function, but there is no reason why a virtual function in a derived class shouldn't be allowed to offer more features than the corresponding base class function. Unfortunately, straightforward application of the current design fails to allow that:

class Base {
public:
  typedef mpl::vector<ThreadSafe, Reviewed> BaseFeatures; 
  virtual void vf(int x, std::string& s, MakeFeatures<BaseFeatures>::type features);
  ...
}; 

class Derived: public Base {
public:
  typedef mpl::vector<ThreadSafe, Reviewed, Portable> DerFeatures;                  // note revised  
                                                                                    // def'n compared
                                                                                    // to base class

  virtual void vf(int x, std::string& s, MakeFeatures<DerFeatures>::type features); // doesn't override 
  ...                                                                               // Base::vf!
};

What's needed is a way for derived classes to satisfy C++'s rule that virtual overrides have the same parameter types as their base class counterparts yet also advertise implementations offering additional code features. (Interestingly, this problem would vanish if C++ allowed contravariant parameter types, because MakeFeatures<BaseFeatures>::type (the base class function's feature set) inherits from MakeFeatures<DerFeatures>::type (the derived class function's feature set).)

Overloading provides an effective solution to this problem. The derived class declares two functions with the same name, one using the same feature set type as the base class, the other using the enhanced feature set the derived class wishes to offer. The implementation of the base class override consists of a simple inline call to the enhanced function. Class Derived above would thus be implemented like this:

class Derived: public Base {
public:
  typedef mpl::vector<ThreadSafe, Reviewed, Portable> DerFeatures;   // as before

  virtual void vf(int x, std::string& s,                             // override base
                  MakeFeatures<BaseFeatures>::type features)         // virtual function  
  {                                                                       
     // verify feature contravariance
     typedef MakeFeatures<BaseFeatures>::type BaseFeaturesClass; 
     typedef MakeFeatures<DerFeatures>::type DerFeaturesClass; 
     BOOST_MPL_ASSERT((boost::is_base_of<DerFeaturesClass,BaseFeaturesClass>)); 

     return vf(x, s, MakeFeatures<DerFeatures>::type());             // inline call to
  }                                                                  // enhanced function

  virtual void vf(int x, std::string& s,                             // as before
                  MakeFeatures<DerFeatures>::type features);  

  ...                          
};

This design offers callers invoking virtual functions through a base class interface the code features advertised by that interface while also allowing callers aware of the derived interface to take advantage of the additional code features provided by the derived class. It is thus analogous to C++'s support for covariant return types on virtual functions.¹²

Performance

In principle, feature checking incurs no runtime cost, because everything happens during compilation. Each feature set parameter, however, could lead to a runtime argument being passed from caller to callee, even though the argument would go unused. Whether this occurs depends on the optimization settings and capabilities of the C++ compiler. If such objects are not optimized away, Table 1 demonstrates that their size could be significant (up to many thousands of bytes per feature set), an artifact of the use of virtual inheritance¹⁴ in the current implementation.

Table 1: sizeof(feature set) for different 32-bit compilers given 5 total features.

C++ template metaprogramming has a reputation for causing significant increases in compilation times, and my experience is that this reputation is not undeserved. Test programs of a few dozen lines (excluding header contents) often took 30 seconds or longer to compile, and experiments with more than 5 total features were abandoned due to excessively long compilation times or, in the case of Visual C++, aborted compilations due to internal compiler errors.

The implementation described here was designed only as a proof of concept, however; efficiency was not a concern. It is reasonable to expect that less costly implementations would be devised were that aspect of the problem to become the focus of attention. For example, the current implementation passes feature set parameters by value rather than by pointer or reference-to-const, a decision motivated by the desire to avoid adding unnecessary symbols to the already somewhat cumbersome TMP-based syntax.

Open issues

The research described in this paper could be extended in several ways:

• Supporting operators. The technique described here is based on code feature constraint enforcement through a dedicated function parameter. Such designs are unsuitable for operator functions, because C++ prohibits such functions from taking more than the “natural” number of parameters. Even without this restriction, it's unclear how it would be possible to integrate the addition of a parameter for call features to the “normal” calling syntax for operators. For example, were it possible to pass more than two parameters to operator+, how would clients do this in an expression such as “a + b” without compromising the natural syntax that is the primary motivation for overloading operators? Support for feature constraint checking on operators remains an open question.
• Specifying code features for groups of functions. A comment on Sutter's blog entry²⁰ raised the question of how to extend the idea of feature constraint checking from individual functions to collections of functions, e.g., all functions in a class or namespace. Ideally, such checking would require only that the collection be annotated with the features it offers; individual functions would need no feature set parameter.
• Supporting inheritance among features classes. In this article, the notion of exception safety was treated as a binary characteristic: a function offers exception safety or it does not. Exception safety in C++ is typically broken down by degree, ranging from functions that never emit exceptions (the nothrow guarantee) to those offering transactional semantics (the strong guarantee) to those offering only invariant-preserving semantics (the basic guarantee).^2,16 These guarantees can be modeled by separate code features related by inheritance:

  struct BasicGuarantee {}; 
  struct StrongGuarantee: BasicGuarantee {}; 
  struct NoThrowGuarantee: StrongGuarantee {};
  

  It would be interesting to modify code feature constraint checking to offer support for such relationships.

• Elimination of AllCodeFeatures. The current design assumes the existence of a container holding all possible feature classes (i.e., AllCodeFeatures). A more flexible approach would do away with such a container, thus allowing different groups of developers to independently define their own sets of feature classes that, absent name conflicts, would work seamlessly in combination. The conventional approach to this problem would be self-registration of feature classes, but conventional self-registration takes place at runtime, and what's needed in this case is a compile-time approach.
• Allowing users to control feature set type conversion policy. Given a call to a function name that is overloaded on feature set types, the policy followed in this article is to prefer conversions adding fewer unneeded features to those requiring more. As noted, an alternative would be to decree such calls ambiguous. (Sutter has shown how to implement this alternative.²⁰) Other policies are certainly plausible. For example, users could assign different weights to different features, then prefer conversions adding the least unnecessary weight. It would be interesting to investigate how the feature set type conversion policy could be put under user control—possibly via policy-based design.³
• Improving diagnostics. Compiler diagnostics arising from feature constraint violations (e.g., Figures 1 and 2) are far from transparent. Clear, straightforward messages indicating the feature sets requested by the caller and provided by the callee would be a significant improvement. One approach to this issue would be development of a diagnostic post-processor similar to Zolman's STLFilt for improving the readability of STL-related diagnostics.²³
• Improving performance. As noted above, the proof-of-concept implementation described here may incur nontrivial costs in compilation time and runtime memory usage. Development of more efficient mechanisms to enforce code constraints would be highly desirable. Alternatively, it might be worth developing two versions of the constraint-enforcement code, a “slow” version with the behavior described here as well as a “fast” version consisting of only no-op API stubs with no behavior. As long as the slow version was used periodically to verify that no code constraint violations existed, the fast version could be used for most compilations.

Related work

I am unaware of other work facilitating the definition and combination of arbitrary code features, but the general issue of imposing restrictions on function invocation has certainly received attention. Bolten, for example, has described how the use of intermediate classes makes it possible to increase the granularity of friendship in C++,⁶ and Alexandrescu has demonstrated how C++'s type system can be employed to enable compile-time detection of race conditions in multithreaded systems.^4,5 Also related is Perl's Taint Mode,¹⁹ which tags data from outside sources and restricts the operations that may be performed with it. In contrast to the static checking underlying the work described in this paper and in the publications by Bolten and Alexandrescu, Perl's Taint Mode is enforced dynamically.

Summary

This paper describes a mechanism that allows users to define arbitrary sets of code features and to ensure during compilation that invoked functions offer all the code features callers require. The design takes advantage of C++'s template metaprogramming capabilities as embodied in the Boost MPL library. It applies to member functions, non-member functions, and function templates, but not to operators.

Acknowledgments

During my work on the research described in this paper as well as the paper itself, I was the beneficiary of assistance from many people. The members of the Boost Users mailing list provided invaluable help in learning how to apply the MPL; Steven Watanabe went so far as to contribute the essence of the MakeFeatures implementation.²¹ Herb Sutter suggested improvements to my original design that removed restrictions and laid the groundwork for additional refinements that ultimately yielded a fully compile-time-checked design.²⁰ Andrei Alexandrescu, Eric Niebler, Bartosz Milewski, and Hendrik Schober provided useful comments on earlier versions of this paper, including the exhortation to find a way to eliminate the runtime checking I employed for virtual functions at that time. Andrei suggested the use of inheritance as the basis of implicit conversions among feature set types, and he also suggested the use of overloading to allow virtual overrides in derived classes to offer more code features than their base class counterparts. Steve Dewhurst suggested using positions in a master type container as the basis for canonically ordering sequences of feature classes.

Sidebar 1: Red code, green code, and the design road to TMP

When working with code features and the constraints they lead to, it can be convenient to refer to red code and green code. Red code lacks the feature(s) in question, hence is unconstrained: it can call any other functions. Green code offers the feature(s) being considered and is constrained to call only other functions that also offer the feature(s), i.e., it requires the feature(s) in the functions it calls.

When I was initially confronted with the problem of finding a way to keep red code from calling green code without an explicit syntactic indication (e.g., a cast), template metaprogramming (TMP) was not the approach that came to mind. I thought instead of namespaces. My idea was that red and green code could be separated into different namespaces, with the green code imported into the red namespace, but not vice versa. That would allow red code to call green code without adornment, but green code could call red code only with an explicit namespace qualification.¹⁵ For example:

namespace green { 
    void greenFunc();               // callable by anybody, but can call only other code in this namespace 
} 

namespace red { 
    using namespace green;          // all green code is available to red code 
    void redFunc();                 // callable only by unconstrained code, but can call anything 
}  

void green::greenFunc() 
{ 
    redFunc();                      // error! Red code not visible in green namespace 
    red::redFunc();                 // okay – call explicitly allowed 
} 

void red::redFunc() 
{ 
    greenFunc();                    // okay
}

This approach quickly falls apart. It doesn't work for global functions, because they're not in a named namespace. If a green function makes an unqualified call to a red function with an argument whose type comes from the green namespace, C++'s argument-dependent lookup^11,22 will cause the function in the red namespace to be found, thus circumventing the constraint checking the namespaces are supposed to provide. In addition, constraints may occur in arbitrary combinations, but namespaces must nest, and I was unable to envision a way to model arbitrary combinations of constraints using nested namespaces.

My next idea was to try to apply a technique akin to that used by Barton and Nackman to enforce dimensional unit correctness during compilation.⁸ Their approach is based on associating information with objects, however, and my need was for a way to associate it with functions, and it was not clear how their approach could be modified to transcend this difference.

The need to control functions got me to thinking about the use of enable_if technology to enable and disable the applicability of functions for particular calls.¹³ Unfortunately, there was a semantic mismatch between what I wanted to do and what enable_if is designed to achieve. My goal was that calls from constrained to unconstrained code should not compile, but when the condition controlling an enable_if-guarded function is unsatisfied, the function is simply removed from the overload set, i.e., from the set of candidate functions considered for the call. The call itself might still compile, because overload resolution might succeed with a different function.

An additional problem with enable_if is that it doesn't apply to functions, only to function templates. This makes it unsuitable for virtual functions, because they may not be templatized. It also leads to the possibility of code bloat, because function templates with different enable_if arguments could, through multiple instantiations, lead to multiple copies of identical object code. This problem is one I overlooked during my initial design work, and my first implementation of code constraints,¹⁸ though not based on enable_if, did assume that all constrained functions were templates.

Unsatisfied with enable_if's behavior, I turned my attention to traits as a mechanism for associating constraint information with functions. Traits are primarily employed to map types to information, but they can associate information with values, too, so I considered using function addresses as such values. I abandoned this idea, however, in part because it was not clear how to deal with function templates (which generate multiple functions, hence multiple addresses), in part because traits would physically separate the constraints for a function from the function's declaration(s), and a function's constraints is a key part of its interface. As such, it's important that they be documented at or near the point where the function itself is declared.

I then noticed that compile-time dimensional analysis, enable_if, and traits had something in common: they were all based on template metaprogramming. That led me to ponder whether TMP in general and the MPL in particular could be used to solve the code constraint problem, and that, in conjunction with the observation that iterator categories in the STL are represented by empty classes, was the genesis of the design described in this article.

Sidebar 2: Code feature constraints in the D programming language

by Bartosz Milewski

On the surface, Scott's code features seem to be tied to their C++ implementation. It turns out that they can be translated into at least one other programming language. I took the challenge of implementing them in D, a relatively new general purpose language loosely based on C++ (for details, see http://www.digitalmars.com/d). What makes D a good candidate for the task is its extensive and well integrated support for metaprogramming. Metaprogramming in D does not require:

• Learning a separate language. A D metaprogram looks very much like a regular D program.
• Switching programming paradigms. Unlike in C++, where metaprograms are purely functional, in D you can run imperative-style programs at compile time.

Instead a D compiler has a built-in D interpreter. It can execute a substantial subset of D at compile time.

A metaprogram is a program that generates a program. In D you can generate a program in the form of a string. The string can then be converted to actual D code using a “string mixin”—all at compile time. For instance, this code:

mixin ("int x;");

is equivalent to:

int x;

The D implementation of the main article's code features is based on generating a string containing the definition of a hierarchy of types as in Figure 3. The crucial idea, suggested to me by Andrei Alexandrescu, was to use D interfaces rather than classes. D does not support multiple inheritance, but interfaces can be multiply inherited and their inheritance is virtual.

Client code that defines a set of code features looks like this:

mixin (declareAllFeatures (["Tested", "Portable"]));

The function declareAllFeatures() is run at compile time. It takes an array of feature names and generates a string with interface declarations. Here's the string corresponding to the above example (complete with newlines for easier debugging):

"interface Portable: Portable_Tested {} 

interface Tested: Portable_Tested {} 

interface Portable_Tested {} 

interface NoFeatures: Portable,Tested {}"

Incidentally, the same string can be generated and printed at run time using this line of code:

writeln (declareAllFeatures (["Tested", "Portable"]));

Such run time/compile time duality makes D metaprograms easy to test and debug.

Continuing with the client code, here's how you declare a function that guarantees "Portable" and "Tested":

void bar (ToType!(MakeFeatures (["Portable", "Tested"])) x)

The function MakeFeatures creates a string "Portable_Tested", which is converted to a D type using the template ToType. Notice that Portable_Tested is one of the interfaces declared using declareAllFeatures above.

The client may call the function bar with a particular set of requirements, which are declared using MakeFeatures. For instance,

ToType!(MakeFeatures (["Tested"])) tested; // require Tested 

bar (tested);

Notice that the interface Tested inherits from Portable_Tested, so this call will compile successfully.

Just to give you a taste of compile-time programming in D, here's the implementation of MakeFeatures:

string MakeFeatures (string[] a) 
{ 
    if (a.length == 0) 
        return "NoFeatures"; 
    else 
        return ctConcat (ctSort (a), '_'); 
}

It takes an array of strings (names of features). If the array is empty, it generates NoFeatures, the name I gave to the interface corresponding to the bottom class in Figure 3. Otherwise it sorts the array (compile-time sort) and concatenates its elements using the underscore as separator.

Here's the implementation of the compile-time concatenation function, without the separator option for simplicity:

string ctConcat (string [] arr) 
{ 
    string result = ""; 
    foreach (s; arr) 
        result ~= s; 
    return result; 
}

It's pretty self-explanatory if you know that the operator tilde is used to concatenate arrays (strings in this case). Notice that local variables and loops are okay at compile time.

Compilation times for the D implementation are negligible for up to seven features. The compilation of eight features took two minutes, and the compiler run out of memory at nine features.

The source code of the full D implementation is available at http://www.bartosz.com/features.

Bartosz Milewski is a member of the D design team.

1. Abrahams, David and Gurtovoy, Aleksey, C++ Template Metaprogramming, Addison- Wesley, 2004.
2. Abrahams, David, “Exception-Safety in Generic Components,” Generic Programming: Proceedings of a Dagstuhl Seminar, M. Jazayeri, R. Loos, and D. Musser, eds. (Springer Verlag, 1999), available at http://www.boost.org/community/exception_safety.html.
3. Alexandrescu, Andrei, Modern C++ Design, Addison-Wesley, 2001.
4. Alexandrescu, Andrei, “Multithreading and the C++ Type System,” February 8, 2002, http://www.informit.com/articles/article.aspx?p=25298
5. Alexandrescu, Andrei, “volatile – Multithreaded Programmer's Best Friend,” C/C++ Users Journal C++ Experts Forum, February 2001, available at http://www.ddj.com/cpp/184403766/.
6. Bolton, Alan R., “Friendship and the Attorney-Client Idiom,” C/C++ Users Journal, January 2006, available at http://www.ddj.com/cpp/184402053/.
7. Boost C++ Libraries Web Site, http://boost.org/
8. Barton, John J. and Nackman, Lee R., “Dimensional Analysis,” C++ Report, January 1995. This is a simplified version of the material covered in section 16.5 of the authors' Scientific and Engineering C++, Addison-Wesley, 1994.
9. Frogley, Thaddaeus, “An Introduction to C++ Traits,” http://thad.notagoth.org/cpptraits_intro
10. Gurtovoy, Aleksey and Abrahams, David, The Boost MPL Library, http://www.boost.org/libs/mpl/doc/index.html
11. ISO/IEC, International Standard: Programming Languages – C++, Second Edition, 15 October 2003, section 3.4.2 (“Argument-dependent name lookup”).
12. ISO/IEC, International Standard: Programming Languages – C++, Second Edition, 15 October 2003, section 10.3 (“Virtual functions”), paragraph 5.
13. Järvi, Jaakko et al., “Function Overloading Based on Arbitrary Properties of Types,” C/C++ Users Journal, June 2003, available at http://www.ddj.com/cpp/184401659.
14. Lippman, Stanley, Inside the C++ Object Model, Addison Wesley, 1996, pp. 95-101.
15. Meyers, Scott, “Using namespaces to partition code,” Usenet newsgroup comp.lang.c++.moderated, February 13, 2004, http://tinyurl.com/357n6w.
16. Meyers, Scott, Effective C++, Third Edition, Addison-Wesley, 2005, Item 29.
17. Meyers, Scott, Effective C++, Third Edition, Addison-Wesley, 2005, Item 47.
18. Meyers, Scott, “Red Code, Green Code: Generalizing const,” presentation to the Northwest C++ Users Group, April 2007. Video available at http://video.google.com/videoplay?docid=-4728145737208991310&hl=en, presentation materials at http://www.nwcpp.org/Downloads/2007/redcode_-_updated.pdf.
19. Ragle, Dan, “Introduction to Perl's Taint Mode,” http://www.webreference.com/programming/perl/taint/.
20. Sutter, Herb, “Thoughts on Scott's ‘Red Code / Green Code' Talk,” May 6, 2007, http://herbsutter.spaces.live.com/blog/cns!2D4327CC297151BB!207.entry.
21. Watanabe, Steven, “Re: [mpl] Hierarchy Generation,” Boost User's Mailing List, February 25, 2008.
22. Wikipedia, “Argument dependent name lookup,” http://en.wikipedia.org/wiki/Argument_dependent_name_lookup.
23. Zolman, Leor, “An STL Error Message Decryptor for Visual C++,” C/C++ Users Journal, July 2001, available at http://www.ddj.com/cpp/184401416.

Talk back!

Have an opinion? Readers have already posted 16 comments about this article. Why not add yours?

About the author

Scott Meyers is one of the world’s foremost authorities on C++; he provides training and consulting services to clients worldwide. He wrote the best-selling Effective C++ series (Effective C++, More Effective C++, and Effective STL), designed the innovative Effective C++ CD, is Consulting Editor for Addison Wesley’s Effective Software Development Series, and serves on the Advisory Board for The C++ Source (http://www.artima.com/cppsource/). He has a Ph.D in Computer Science from Brown University. His web site is aristeia.com.