C++语言概念域检查

Dr. Dobb's Journal June 2001

出处：http://hyper.vcsun.org/HyperNews/rlingard/get/CS380f2002/sharing/201.html

使用模板进行编程的更佳实践。

By Jeremy Siek and Andrew Lumsdaine

Jeremy and Andrew work in the computer science department at Indiana University. They can be contacted at lums@cs.indiana.edu.

（WQ注：本文知识可参看《More Exceptional C++》 Item 4。）

--------------------------------------------------------------------------------

C++的泛型编程表现形式上就是用模板参数作为抽象数据类型，也就SGI STL的文档中所用的“概念域（Concept）”这个术语(参见《Generic Programming and the STL》，M.H.Austern , Addison-Wesley, 1999，和标准模板库的SGI实现，http:// www.sgi.com/Technology/STL/) 。很不幸，随模板提供的灵活性而来的就是牺牲了接口安全性。在本文中，我们将介绍一个技术以重新将接口安全性引入模板函数。

看一下例1(a)（WQ注：我所找到的版本中，这几个例子的代码都缺失）。如果一个函数作用于整型的stack容器上，你可以使用一个面向对象的方法来描述这个需要一个stack类型的需求：使用一个抽象基类。随后的函数调用foo(y)只有在参数y是从Stack派生时才成立。这确保了类型y至少有push()和pop()成员函数，这样在foo()内部对它们的调用能保证被很好地定义。

使用模板，接口安全变得非常含糊。举例来说，假设有例1(b)这样一个函数模板。在这种情况下，编译器允许任何类型的对象作为参数传给bar()，根本不在意它是否是一个stack对象(也就是说有push()和pop()成员函数)。如果使用了一个不正确的类型，将会发生编译错误。然而，错误并不是在调用bar()的地方被捕获，而是在bar()的实现内部某处。你需要一个机制以使得模板函数能与抽象基类方法一样提供接口安全性。藉由一些新的C++惯用法来指定并检查对模板参数的需求，我们能做到这一点。我们使用术语“概念域（concept）”来表示需求集，而称呼我们的方法为“概念域检查（concept checking）”。

我们一群在SGI和the University of Notre Dame工作的人于一年以前开始了概念域检查机制的研究，并产生了现在出现在SGI STL发行版本中概念域检查。这一工作被更进一步发展(参见“Concept Checking: Binding Parametric Polymorphism in C++”,by J. Siek and A. Lumsdaine, First Workshop on C++ Template Programming, October 2000，（WQ注：http://www.osl.iu.edu/~jsiek/concept_checking.pdf）) 并呈现为Boost Concept Checking Library这样的可用形式（http://www .boost.org/libs/concept_check/ concept_check.htm）。本文中，我们将涉及概念域检查的两个互补面：概念域检查和概念域覆盖（concept covering）。概念域检查处理的是概念的完整需求，确认模板参数满足这些需求，并当用户提供的模板参数不满足需求时提供恰当的错误消息。概念域覆盖确认模板规定的需求是有效的；也就是说，检查所有使用模板参数的途径，以确认没有引入不必要的需求。

概念域

概念域就是需求集(有效表达式，相关类型，语义不变，复杂性保证，等等valid expressions, associated types, semantic invariants, complexity guarantees)，一个类型必须满足它们，才被正确用为泛型运算的参数。然而，C++语言中并没有概念域的显式表现机制，模板形参只不过是占位符，不能对实参表示任何约束。根据习惯，模板形参将被给予一个满足概念域需求的名字，但C++编译器并不在模板形参绑定到实际类型时强迫满足这点。

自然，如果调用泛型运算时，类型不满足概念域的语法要求，一个编译期错误将会发生。然而，这个错误将不反映为类型不满足概念域的要求。错误可能发生在对此类型将会无效的表达式上，或某假定相关类型不可用时。产生的错误消息通常不提供有用信息，并难以理解。

在实例化时强迫“概念域安全”的机制是必需的。Boost Concept Checking Library (BCCL)使用标准的C++语言结构来强迫满足概念域，并在不满足时提供更具信息量的错误消息。本文描述的技术只涉及概念域的语法需求(有效表达式和相关类型)，不涉及语意不变或复杂性保证(虽然这是我们研究小组的一个活跃主题)。

例子扩展

它发生在我们所有人身上：使用标准库（SL）泛型算法的一个小错误，编译器产生了数页之多的难以理解的错误消息。当然，这个问题不是SL特有的，它影响所有的模板类和模板函数。例2说明了一个这样的错误。它调用SL中的泛型算法std::stable_sort()，将它应用到list上。

用GNU C++编译器编译例3将得到编译错误。对于本例，根本错误在于std::list::iterator不满足RandomAccessIterator的概念。list的iterator只是双向选择子，不能随机存取(象std::vector::iterator那样)。很不幸，错误信息中没有任何东西向用户指出这一点。在对模板库很富经验的C++程序员看来，错误可能很显而易见。然而，不管怎么说，基于几个理由，可以认为这个错误信息是难以理解的。

l 位置错误。例2的第5行没有被错误信息提到，即使是GNU C++打印出深达4层的调用栈。

l 在错误信息和std::stable_sort()和RandomAccessfterator的文档化需求间没有文字联系。

l 错误信息太长，列出了SL内部的函数，而它们是用户不（并且是不应该）知道或关心的。

l 由于列出了这么多库内部函数，用户很容易推论错误是源于库本身，而不是他们的代码。

例4说明了你期望从有价值的信息中得到什么(事实上，这也正是BCCL产生的)。这个信息弥补了前面的错误信息的不足。

l 发生错误的位置在错误信息中被描述。

l 信息明确地提到了用户能在SL文档中找到的概念(RandomAccessIterator) 。

l 错误信息非常短，并且没有提及STL的内部函数。

l 错误信息中出现的check.hpp 和constraints()，提醒用户错误位于用户代码，而不是模板的实现中。

概念域检查类

为了检查一项概念，我们使用了一个特别的类(一个概念域检查类)，以确保一个（或一组）给定类型满足给定的概念。来自BCCL中的一个概念域检查类的例子是EqualityComparableConcept，对应于C++标准 20.1.1中描述的EqualityComparable需求和SGI STL文档中的EqualityComparable概念。

template <class T>

struct EqualityComparableConcept;

模板参数T就是要被检查的类型。也就是说，EqualityComparableConcept的目的是确保给定的模板参数T，满足EqualityComparable的概念。每个概念域检查类都有成员函数constraints()，内部包含了概念域的有效表达式。为了检查某个类型是否EqualityComparable，我们需要用这个类型实例化概念域检查类，并找到一个方法让编译器编译constraints()函数而不需要执行它。BCCL定义了两个工具以使这一切简单：function_requires() 和 BOOST_CLASS_REQUIRES。function_requires()函数可以被用于函数体内部，而BOOST_ CLASS_REQUIRES可以被用于类体内。

function_requires()函数没有参数，但有一个模板参数供概念域检查类使用。这意味着实例化概念域检查类时，必须给予显式的模板参数；见Listing One(a)。插入这个概念域检查后，如果类foo不满足EqualityComparable(没有== 和!=操作)，function_requires() 将会在开头处捕获错误，而不是让错误发生在模板函数内部某处。

BOOST_CLASS_REQUIRES宏可以在一个类定义体内使用，以检查某个类型是否满足一个概念；见Listing One(b)。

概念域检查的应用程序

一个好的概念域检查程序会在std::stable_sort()的开始处插入 function_requires()以确保模板参数满足RandomAccessIterator。还有，std::stable_sort()需要iterators指向的类型是LessThanComparable的，所以你也应该使用function_requires()来检查这一点；见Listing Two(a)。

作为使用BOOST_CLASS_REQUIRES的例子，来看一下应该加到std::vector上的概念域检查。一个需求是元素类型必须是Assignable的。你能通过在std::vector的定义体开始处插入BOOST_CLASS_REQUIRES来检查，见Listing Two(b)。

虽然概念域检查被设计为供泛型库的实现者使用的，但它们对最终用户同样有用。有时，你不确定某个类型是否满足特定的概念。通过创建一段小程序，对问题域内的类型和概念使用function_requires()，是很容易检查这一点的。BCCL的文件stl_concept_checks.cpp提供了对SL容器进行概念检查的例子。

实现

理想中，我们想要在实例化的点上捕捉(并指出)概念域违反。如Bjarne Stroustrup的《C++语言设计与演化》 (Addison-Wesley, 1994) 所提到的，错误可以藉由演习（exercise）函数模板的所有需求而被捕获。如何正确演习这些需求(尤其是有效表达式)，这比较微妙，因为我们希望代码被编译但不被执行。我们的方法是在一个独立函数中演习需求，并将这个函数赋给一个函数指针。这样，编译器实例化函数但不真的调用它。另外，优化编译时会把指针赋值作为死代码移除（虽然赋值的运行期开销怎么着都可忽略不记的）。必须要考虑到编译器跳过语意分析而不在约束函数第一次出现的地方编译它的情况，这将造成函数指针技术失效。然而，这不太可能发生，因为移除不必要的代码和函数通常在编译后期进行。我们在GNU C++、Microsoft Visual C++和基于EDG的几个编译器（KAI C++、SGI MIPSpro）上成功运用了函数指针技术。Listing Four展示了如何对std::stable_sort()函数运用这个技术。

通常有一大组的需求需要被检查，并且，对库的实现人员来说，为每个公有函数都写出stable_sort_constrainst()这样的约束函数也很麻烦。实际上，我们可以根据概念域聚集相应的有效表达式。对于每个概念域，定义一个概念域检查类模板，其模板参数就是被检查的类型。这样的类包含一个constraints()成员函数，它演习概念域的所有有效表达式。在constraints()函数内部使用的对象，比如n和i，被申明为概念域检查类的数据成员；参见Listing Five。你仍然可以使用函数指针体系来导致实例化constraints()函数，但现在是成员函数指针了。为了简化库的实现者定义概念域检查的工作，我们将成员函数指针体系封装入函数function_requires()。Listing Six(a)展示了如何使用function_requires()来确保选择子是一个RandomAccessIterator。

function_requires() 的定义如下；Concept是被实例化的概念域检查类。我们将constraints()成员函数的地址赋给函数指针x，这导致了constraints()函数的实例化，并检查了概念域的有效表达式。然后将x传给ignore_unused_variable_warning()函数，并将这一切封装入一个循环以防止do-while冲突；参见Listing Six(b)。

为了检查类模板的类型参数，我们提供了BOOST_CLASS_REQUIRS宏，它可被用于一个类的定义体内(而function_requires()只能被用于函数体内)。这个宏申明了一个嵌套类模板，其模板参数是一个函数指针。然后用一个typedef来使用这个嵌套类，见Listing Six(c)，将指向constraints()函数类型的指针作为模板参数。我们在嵌套类上使用type_var和concept和typedef以避免名字冲突。

另外，有各种版本的BOOST_CLASS_REQUIRES，它们接受更多的参数以处理涉及两个及更多类型间交互的概念。BOOST_CLASS_REQUIRES没有被用于BCCL概念域检查类的实现，因为有几个编译器不支持函数指针作为模板参数。

构造概念检查类

作为创建概念检查类的例子，看一下如何为RandomAccessIterator概念创建相应的检查。首先，基于习惯，我们命名概念域检查类为概念名加加上“Concept”。然后，定义一个成员函数constraints()，并于其中演习概念的有效表达式。function_requires()期望这个函数的签名（signature）如Listing Three中所示的：无返回类型，无参数，非const的成员函数。

constraints()的第一部分包含了那些需求，对应了RandomAccessIterator和它建立的概念之间的联系：BidirectionalIterator和LessThanComparable。我们可以使用BOOST_CLASS_REQUIRES以代替将这些需求放在类体内，然而，BOOST_ CLASS_REQUIRES使用了稍许不可移植的C++特性。

然后，我们检查iterator的类别是否为std::random_access_iterator或其派生类。再下来，我们写出符合 RandomAccessIterator概念的有效表达式的一些代码，typedef也可被增加进来以检查概念的相关类型；参见Listing Three。

一个易犯的错误是在设计概念域检查类时在constraints()函数中使用的表达式超过了必须的数目。举例来说，很容易偶然地使用了默认构造函数创建一个对象，以供表达式使用（但不是所有的概念都要求有默认构造函数）。这是将constraints()写成类的成员函数的原因。表达式对应的对象被申明为类的数据成员。因为constraints()类模板的对象从不实例化，概念域检查类的默认构造函数也从不实例化。因此，数据成员的默认构造函数也将从不实例化 (C++语言标准第 14.7.19 节)

概念域覆盖和原型

如同为组件的输入选择最小需求集（概念）很重要，校验覆盖泛型运算的概念同样重要。也就是说，任何的可能的用户错误都应该被概念域检查捕获而无遗漏，概念域覆盖可以通过使用原型类来校验。原型类是与某个特别概念相关的接口的精确实现。原型类的运行期行为并不重要，函数可以为空。将原型类作为组件的输入，一个简单的测试程序就可以编译出来了。如果程序编译通过，将可以认为概念覆盖了组件。

Listing Seven展示了针对TrivialIterator概念的原型类。要确保原型精确匹配于概念。举例来说，概念陈述了operator*()的返回值必须要能转换到value_type。它并不强迫要求返回类型必须是T&或const T&。正确的方法是创建一个（间接的）返回类型，它能转换到T，比如我们这儿使用的input_proxy。原型类测试的有效性完全取决于它精确匹配于概念，这必须通过仔细的（人工）检查来校验。

泛型运算通常被用大量的普通输入类型来实例化而测试。举例来说，你可能将基本指针类型作iterator用于std::stable_sort()。虽然对测试泛型算法的运行期行为来说是适合的，但它对确保概念域覆盖毫无帮助，因为C++的类型从不匹配特定概念，它们通常提供了远超某个概念的最小需求的功能。也就是说，即使函数模板用某个给定类型进行了编译，概念需求可能仍然达不到函数的真实需求。这就是为什么除了对通常输入类型测试外，还要对原型类进行编译很重要的原因。

Listing Eight摘自BCCL的文件stl_concept_covering.cpp，它展示了原型类如何用于检查std::stable_sort()的需求的。在本例，看起来SGI STL的文档漏了CopyConstructible和Assignable的需求(尝试一下移除那些原型)。Boost原型类被设计得可以层叠。在本例中，iterator的value_type由两个原型类组合而成。在Listing Eight中，命名为Bsase的模板参数示意了分层的原型类可用于何处。

需求最小化

决定该如何将需求聚集进概念域和决定每个泛型运算使用哪个概念域的过程可能是构建泛型库过程中最困难(也是最重要)的。用于此过程的一个指导原则被称为“需求最小化”，最小化组件在输入参数上的需求以增加它的可重用性。

这个陈述中存在着有一个自然的对立面。根据定义，输入参数必须要被组件使用以完成它的任务(这里的“组件”意指一个函数模板或类模板)。挑战在于用最少的假设（最小的需求）完成同样的任务来实现组件。传统的抽象方法直接地和需求最小化联系在一起。输入越抽象，需求越少。因此，概念是抽象数据类型在C++模板程序中简单展现。当为某些问题域设计概念时，关注它们的目的（也就是对组件输入表述出的要求）很重要。根据需求最小化原则，这意味着我们将概念减到最少。

概念的最小性是和问题域表述的内在语义联系在一起的一个特性。对于基本容器的问题域，单向遍历的要求在需求上要弱于双向遍历的要求(ForwardIterator和BidirectionalIterator之间的区别由此而来)。语义的不同可以很容易地从具体的数据结构间（forward iterator对比bidirectional iterator）的差异上看出来。举例来说，单向链表将会产生一个有forward iterator的数据结构，而不会有bidirectional iterator。除此之外，只使用前向选择子的泛型运算与使用双向选择子的泛型运算在实现上有相当的不同。因为这个原因，将需求族分类成良好定义的概念域是很重要的。举例来说，对选择子的需求可分成六个SL iterator概念（trivial，input，output， forward，bidirectional，和random access）。

Boost的概念域检查库

Boost的概念域检查库包含了针对C++标准库中所有概念的概念域检查类（还多加了一些）。除此之外，其它的Boost库还包含了对它们的特有概念进行检查的概念域检查类。比如，Boost Graph库包含了对所提供的图形概念和property map概念的检查。我们鼓励你将概念域检查作开发泛型运算的工作的一部分。当实现使用已有概念的泛型运算时，你可以简单地重用相关的概念域检查。当引入新的概念时，你应该开发相应的概念域检查供自己和用户使用。

展望未来

为C++泛型库设计、实现和校验概念域检查，目前还必须由手工完成。结果，这个过程很花时间，并且(很可能)出错。如果这个过程的某些或全部步骤能被自动化，实现者将会大受其益。

第一步是要有一个工具能静态地分析一个类模板或函数模板，并记录所有种类的涉及模板参数的表达式。这样的工具能简化校验概念域覆盖的任务。第二步将是对必须的表达式与标准概念集（或库的自定义集）进行模式匹配，以汇总概念域的需求。这个信息然后可以以两种方式来使用。首先，它可用于产生供库文档使用的可读报表。其次，它能用来提供有价值的编译出错信息，而不需要手工插入概念域检查。最后，我们发现在泛型编程的广大领域中有太多的工作需要做了。在C++语言之外，有许多方法可用以设计一个直接支持概念的语言。

感谢

Thanks to Alexander Stepanov for originating the idea of using function pointers to trigger the instantiation of concept checking code. Thanks also to Matthew Austern for establishing the concepts of the SGI STL; Beman Dawes for managing the Boost review of the BCCL; and to all the Boost members for reviewing BCCL. Parts of this work were performed while Jeremy was interning at SGI, and Andrew was on sabbatical at Lawrence Berkeley National Lab. This work was partially funded by NSF grant ACI-9982205.

Listing One

(a)

// In my library:

template <class T>

void some_function_template(T x)

{

function_requires< EqualityComparableConcept<T> >();

// ...

};

// In the user's code:

class foo {

//...

};

int main() {

foo f;

some_function_template(f);

return 0;

}

(b)

// In my library:

template <class T>

struct some_class_template

{

BOOST_CLASS_REQUIRES(T, EqualityComparableConcept);

// ...

};

// In the user's code:

class foo {

//...

};

int main() {

some_class_template<foo> glc;

// ...

return 0;

}

Listing Two

(a)

template <class RandomAccessIter>

void stable_sort(RandomAccessIter first, RandomAccessIter last)

{

function_requires< RandomAccessIteratorConcept<RandomAccessIter> >();

typedef typename std::iterator_traits<RandomAccessIter>::

value_type value_type;

function_requires< LessThanComparableConcept<value_type> >();

...

}

(b)

namespace std {

template <class T>

struct vector {

BOOST_CLASS_REQUIRES(T, AssignableConcept);

...

};

}

Listing Three

template <class Iter>

struct RandomAccessIteratorConcept

{

void constraints() {

function_requires< BidirectionalIteratorConcept<Iter> >();

function_requires< LessThanComparableConcept<Iter> >();

function_requires< ConvertibleConcept<

typename std::iterator_traits<Iter>::iterator_category,

std::random_access_iterator_tag> >();

i += n;

i = i + n; i = n + i;

i -= n;

i = i - n;

n = i - j;

i[n];

}

Iter a, b;

Iter i, j;

typename std::iterator_traits<Iter>::difference_type n;

};

}

Listing Four

template <class RandomAccessIterator>

void stable_sort_constraints(RandomAccessIterator i)

{

typename std::iterator_traits<RandomAccessIterator>

::difference_type n;

i += n; // exercise the requirements for RandomAccessIterator

...

}

template <class RandomAccessIterator>

void stable_sort(RandomAccessIterator first, RandomAccessIterator last)

{

typedef void (*fptr_type)(RandomAccessIterator);

fptr_type x = &stable_sort_constraints;

...

}

Listing Five

template <class Iter>

struct RandomAccessIterator_concept

{

void constraints()

{

i += n;

...

}

typename std::iterator_traits<RandomAccessIterator>

::difference_type n;

Iter i;

...

};

Listing Six

(a)

template <class Iter>

void stable_sort(Iter first, Iter last)

{

function_requires< RandomAccessIteratorConcept<Iter> >();

...

}

(b)

template <class Concept>

void function_requires()

{

void (Concept::*x)() = BOOST_FPTR Concept::constraints;

ignore_unused_variable_warning(x);

}

(c)

#define BOOST_CLASS_REQUIRES(type_var, concept)

typedef void (concept <type_var>::* func##type_var##concept)();

template <func##type_var##concept _Tp1>

struct concept_checking_##type_var##concept { };

typedef concept_checking_##type_var##concept<

BOOST_FPTR concept <type_var>::constraints>

concept_checking_typedef_##type_var##concept

Listing Seven

template <class T>

struct input_proxy {

operator const T&() {

return static_object<T>::get(); // Get a reference without constructing

}

};

template <class T>

class trivial_iterator_archetype

{

typedef trivial_iterator_archetype self;

public:

trivial_iterator_archetype() { }

trivial_iterator_archetype(const self&) { }

self& operator=(const self&) { return *this; }

friend bool operator==(const self&, const self&) { return true; }

friend bool operator!=(const self&, const self&) { return true; }

input_proxy<T> operator*() { return input_proxy<T>(); }

};

namespace std {

template <class T>

struct iterator_traits< trivial_iterator_archetype<T> >

{

typedef T value_type;

};

}

Listing Eight

{

typedef less_than_comparable_archetype<

sgi_assignable_archetype<> > ValueType;

random_access_iterator_archetype<ValueType> ri;

std::stable_sort(ri, ri);

}