http://www.artima.com/cppsource/codefeatures.html
http://docs.google.com/Doc?id=dnc5d3v_109gmz4xwgb
Enforcing Code Feature Requirements in C++by Scott Meyers
September 23, 2008SummaryFunctions often depend on particular behavioral characteristics (“features”) of code they invoke. For example, thread-safe code must invoke only thread-safe code if it is to remain thread-safe, and exception-safe code must invoke only exception-safe code. This paper describes a technique that enables the specification of arbitrary combinations of user-defined code features on a per-function basis and that detects violations of feature constraints during compilation. The technique applies to member functions (both nonvirtual and virtual), non-member functions, and function templates; operators are excluded.
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.
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.17 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 library1,10 for template metaprogramming available at Boost.7 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:
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.
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:
{
… // 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,
void g(MakeFeatures<TEPSafe>::type features); // g offers/requires thread-safe,
// exception-safe, and portable code
and a call from f to g:
{
…
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:
{
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.
CodeFeatures::Features<
boost::mpl::v_item<
CodeFeatures::Portable
, boost::mpl::v_item<
CodeFeatures::ExceptionSafe
, boost::mpl::vitem<
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::vitem<
CodeFeatures::ThreadSafe, boost::mpl::vector0<mpl::na>, 0
>, 0
>, 0
>
>’ to non-scalar type ‘CodeFeatures::Features<
boost::mpl::v_item<
CodeFeatures::ExceptionSafe
, boost::mpl::vitem<
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:
{
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:
{
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:
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:
{
…
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:
struct eraseVal
: mpl::copyif<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
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, 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:
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:
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:
Tneededconverts toTofferedonly ifTofferedhas all the features inTneeded.- If
Tneededcan be converted to more than oneToffered, conversions adding fewer features are preferred to those adding more. If conversions exist to more than oneTofferedwith 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.
{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).
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::removeif<S1, mpl::contains<S2, > >
13 {};
14 template<typename Present, typename Omitted>
15 struct GetFeaturesBases:
16 mpl::transform<Omitted, MakeFeatures<mpl::pushback<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::emptybase,
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.
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>.
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:
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.12
PerformanceIn 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 inheritance14 in the current implementation.
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.