【C++ Templates（26）】调试模板

• 调试模板时有两个挑战，一是如何确保满足条件时适用任何实参，二则完全相反，当模板表现不如预期如何找出违反要求的参数

浅实例化（Shallow Instantiation）

• 当模板出错时，问题通常被发现于一长串实例化之后，导致冗长的错误信息。为了解释这点，考虑如下有些做作的代码

template<typename T>
void clear (T& p)
{
    *p = 0; // assumes T is a pointer-like type
}

template<typename T>
void core (T& p)
{
    clear(p);
}

template<typename T>
void middle (typename T::Index p)
{
    core(p);
}

template<typename T>
void shell (T const& env)
{
    typename T::Index i;
    middle<T>(i);
}

• 这个例子解释了软件开发的典型分层：高层函数模板如shell()依赖于组件如middle()，而middle()又使用了基本的工具如core()。实例化shell()时，更低层都需要实例化。在这个例子中，问题在于最深层的core()用整型实例化（middle()中使用Client::Index），并尝试解引用整型值，于是出错。错误只在实例化时可检测，如

class Client
{
public:
    using Index = int;
};

int main()
{
    Client mainClient;
    shell(mainClient);
}

• 一个好的泛型诊断包括所有导致问题的层的跟踪，但冗长的信息显得笨拙
• 曾经关于此问题的讨论中，Bjarne Stroustrup定义了两类方法来更早地确定模板实参是否满足一些限制：通过一个语言扩展，或通过更早的参数使用。前者即Concepts，后者包括在浅实例化中强制任何错误，这点可通过插入没有其他目的的无用代码实现，而非如果实例化时模板实参不满足更深层模板的要求则触发错误
• 在之前的例子中，可以添加代码在shell()中尝试解引用一个T::Index类型的值，如

void ignore(T const&)
{
}

template<typename T>
void shell (T const& env)
{
    class ShallowChecks
    {
        void deref(typename T::Index ptr) {
            ignore(*ptr);
        }
    };
    typename T::Index i;
    middle(i);
}

• 如果T是一个类型则T::Index不能解引用，一个错误将在局部类ShallowChecks中被诊断。注意因为局部类未使用，添加的代码不影响shell()的运行时期。不幸的是，许多编译器将警告ShallowChecks未使用，使用如ignore()模板之类的技巧可以禁止这样的警告，但增加了代码的复杂度

Concept Checking

• 目前concepts还未实现，但一旦有了它，就有其他方法支持要求和期望行为的定义

静态断言（Static Assertion）

• assert()宏常用语检查程序执行中某个点的特别条件，如果断言失败则程序停顿以便修复问题
• C++11引入了static_assert，实现相同目的但在编译期计算：如果条件（必须是常量表达式）计算为false，编译器将产生一个错误信息，错误信息将包含一个字符串（static_assert本身的一部分）来说明问题，比如下列静态断言确保编译平台带64位指针

static_assert(sizeof(void*) * CHAR_BIT == 64, "Not a 64-bit platform");

• 当模板实参不满足约束，静态断言能提供有用的错误信息。先创建一个type trait来确定一个给定类型能否解引用

// debugging/hasderef.hpp

#include <utility> // for declval()
#include <type_traits> // for true_type and false_type

template<typename T>
class HasDereference {
private:
    template<typename U> struct Identity;
    template<typename U> static std::true_type
        test(Identity<decltype(*std::declval<U>())>*);
    template<typename U> static std::false_type
        test(...);
public:
    static constexpr bool value = decltype(test<T> (nullptr))::value;
};

• 现在可以为shell()引入一个静态断言，若实例化使用一个不能解引用类型，将提供更好的诊断

void shell (T const& env)
{
    static_assert(HasDereference<T>::value, "T is not dereferenceable");
    typename T::Index i;
    middle(i);
}

• 面对模板库时，静态断言能大大提升用户体验。静态断言也能用于类模板和所有的type trait

template<typename T>
class C {
    static_assert(HasDereference<T>::value,
        "T is not dereferenceable");
    static_assert(std::is_default_constructible<T>::value,
        "T is not default constructible");
    ...
};

原型（Archetype）

• 写模板的一个挑战是确保任何满足特定约束的模板实参都能通过编译。考虑一个简单的find()算法，它查找数组中的一个值，并考虑它的文档约束

// T must be EqualityComparable, meaning:
// two objects of type T can be compared with ==
// and the result converted to bool
template<typename T>
int find(T const* array, int n, T const& value);

• 可以马上想到如下直接的实现

template<typename T>
int find(T const* array, int n, T const& value) {
    int i = 0;
    while(i != n && array[i] != value)
        ++i;
    return i;
}

• 有两个问题，当给定某个严格满足满足要求的模板实参，每个问题都将显示汇编错误。将使用原型的概念来测试使用不满足要求的模板参数的实现
• 原型是用户定义的类，它能用作模板实参以测试模板定义对约束的依附。一个原型是特别制定的，以尽可能小的方式来满足模板大多数要求，而不提供任何外来的操作。如果一个带有原型作实参的的模板定义实例化成功，就能知道模板定义不尝试使用任何不需要的操作
• 下面是一个原型，它尝试满足find()算法中EqualityComparable的要求

class EqualityComparableArchetype
{
};

class ConvertibleToBoolArchetype
{
public:
    operator bool() const;
};

ConvertibleToBoolArchetype
operator==(EqualityComparableArchetype const&,
    EqualityComparableArchetype const&);

• EqualityComparableArchetype没有成员函数或数据，它提供的唯一操作是一个重载的operator==以满足find的等价要求，operator==返回另一个原型ConvertibleToBoolArchetype，它只有一个用户定义的转换到bool的操作
• EqualityComparableArchetype显然满足find()模板规定的要求，因此可以检查find()的实现是否尝试使用EqualityComparableArchetype实例化find()来终止约束的结尾

template int find(EqualityComparableArchetype const*, int,
    EqualityComparableArchetype const&);

• 实例化find<EqualityComparableArchetype>将失败，表明找到第一个问题：EqualityComparable描述只需要==，但是find()实现依赖于用!=比较T对象。我们的实现将适用于大多用户定义的将==和!=作为实现的一部分的类型，但是事实上它是不正确的。原型尝试在模板库开发的早期发现这样的问题
• 使用相等而非不等解决第一个问题，find()模板将成功使用原型编译

template<typename T>
int find(T const* array, int n, T const& value) {
    int i = 0;
    while(i != n && !(array[i] == value))
        ++i;
    return i;
}

• 使用原型解开第二个问题需要一点技巧。注意新定义的find()使用!直接产生到==的结果。在原型的情况中，这依赖于用户定义的到bool的转换以及内建的逻辑非operator!。一个ConvertibleToBoolArchetype更小心的实现禁止operator!，以使其不能被不适当地使用

class ConvertibleToBoolArchetype
{
public:
    operator bool() const;
    bool operator!() = delete; // logical negation was not explicitly required
};

• 可以把原型扩展得更远，也能使用删除的函数来禁用operator&&和||来帮助在其他模板定义中找出问题。通常情况下，一个模板实现者将希望模板库中开发一个适用每个concept的原型，并使用这些原型测试每个违反规定要求的模板定义

跟踪程序（Tracer）

• 以上讨论的都是编译或链接时的bug，然而更大的挑战通常是确保成功构建后，程序在运行期表现正确。一个tracer是一个软件设备，它在开发周期早期发现模板定义中的问题，以减轻调试方面的难度
• 一个tracer是一个用户定义的类，它能用作要测试的模板的实参。通常tracer也是一个原型，只要满足模板要求，然而更重要的是tracer应该生成一个调用它的操作的trace。这允许，比如，实际验证算法的效率和操作顺序，下面是一个用于测试排序算法的tracer的例子

// debugging/tracer.hpp

#include <iostream>
class SortTracer {
private:
    int value; // integer value to be sorted
    int generation; // generation of this tracer
    inline static long n_created = 0; // number of constructor calls
    inline static long n_destroyed = 0; // number of destructor calls
    inline static long n_assigned = 0; // number of assignments
    inline static long n_compared = 0; // number of comparisons
    inline static long n_max_live = 0; // maximum of existing objects

    // recompute maximum of existing objects
    static void update_max_live() {
        if (n_created-n_destroyed > n_max_live) {
            n_max_live = n_created-n_destroyed;
        }
    }

public:
    static long creations() {
        return n_created;
    }
    static long destructions() {
        return n_destroyed;
    }
    static long assignments() {
        return n_assigned;
    }
    static long comparisons() {
        return n_compared;
    }
    static long max_live() {
        return n_max_live;
    }

public:
    // constructor
    SortTracer (int v = 0) : value(v), generation(1) {
        ++n_created;
        update_max_live();
        std::cerr << "SortTracer #" << n_created
            << ", created generation " << generation
            << " (total: " << n_created - n_destroyed
            << ")\n";
    }

    // copy constructor
    SortTracer (SortTracer const& b)
    : value(b.value), generation(b.generation+1) {
        ++n_created;
        update_max_live();
        std::cerr << "SortTracer #" << n_created
            << ", copied as generation " << generation
            << " (total: " << n_created - n_destroyed
            << ")\n";
    }

    // destructor
    ~SortTracer() {
        ++n_destroyed;
        update_max_live();
        std::cerr << "SortTracer generation " << generation
            << " destroyed (total: "
            << n_created - n_destroyed << ")\n";
    }

    // assignment
    SortTracer& operator= (SortTracer const& b) {
        ++n_assigned;
        std::cerr << "SortTracer assignment #" << n_assigned
            << " (generation " << generation
            << " = " << b.generation
            << ")\n";
        value = b.value;
        return *this;
    }

    // comparison
    friend bool operator < (SortTracer const& a, SortTracer const& b) {
        ++n_compared;
        std::cerr << "SortTracer comparison #" << n_compared
            << " (generation " << a.generation
            << " < " << b.generation
            << ")\n";
        return a.value < b.value;
    }

    int val() const {
        return value;
    }
};

• 除了要排序的值value，tracer提供了几个成员跟踪一个实际的排序：对每个对象，generation跟踪从原始对象中移除多少复制操作。即一个原始对象有generation==1，一个原始对象的直接拷贝有generation==2，一个拷贝的拷贝有generation==3，以此类推。其他静态成员跟踪构造、析构、赋值比较等数量，以及对象存在的最大数量
• 这个特殊的tracer允许追踪实例创建和析构以及赋值、比较等模式，下面的测试程序为std::sort()解释了这点

// debugging/tracertest.cpp
#include <iostream>
#include <algorithm>
#include "tracer.hpp"

int main()
{
    // prepare sample input:
    SortTracer input[] = { 7, 3, 5, 6, 4, 2, 0, 1, 9, 8 };

    // print initial values:
    for (int i=0; i<10; ++i) {
        std::cerr << input[i].val() << ' ';
    }
    std::cerr << '\n';

    // remember initial conditions:
    long created_at_start = SortTracer::creations();
    long max_live_at_start = SortTracer::max_live();
    long assigned_at_start = SortTracer::assignments();
    long compared_at_start = SortTracer::comparisons();

    // execute algorithm:
    std::cerr << "---[ Start std::sort() ]--------------------\n";
    std::sort<>(&input[0], &input[9]+1);
    std::cerr << "---[ End std::sort() ]----------------------\n";

    // verify result:
    for (int i=0; i<10; ++i) {
        std::cerr << input[i].val() << ' ';
    }
    std::cerr << "\n\n";

    // final report:
    std::cerr << "std::sort() of 10 SortTracer's"
        << " was performed by:\n "
        << SortTracer::creations() - created_at_start
        << " temporary tracers\n "
        << "up to "
        << SortTracer::max_live()
        << " tracers at the same time ("
        << max_live_at_start << " before)\n "
        << SortTracer::assignments() - assigned_at_start
        << " assignments\n "
        << SortTracer::comparisons() - compared_at_start
        << " comparisons\n\n";
}

• 运行这个程序将创建大量输出，但很多都可以从最终报告中得出结论。对一个std::sort()的实现，找到下面的

std::sort() of 10 SortTracer's was performed by:
9 temporary tracers
up to 11 tracers at the same time (10 before)
33 assignments
27 comparisons

• 比如，我们发现尽管排序时创建了9个临时tracer，最多两个额外的tracer在任何时候存在
• tracer充当两个角色：它提供标准sort()算法而不需要更多的功能（比如operator==和>），并给出一个算法的开销的直观感觉。然而，它不揭示排序模板的正确性

Oracles

• tracer相对简单和有效，但只允许跟踪模板对于特定输入数据和一个相关功能的特定行为的执行。我们可能想知道，比如，排序算法有意义（或正确）的比较操作必须满足的条件，但在例子中，只测试了一个行为像int的<比较操作
• 一个tracer的扩展是oracles（或运行期分析oracles），他们是关联推理引擎（inference engine，一个能记住断言和推断某个结论的原因的程序）的tracer
• oracles允许在一些情况下动态判定模板算法，而不需要全部替代模板实参（oracles是实参）或输入数据（推理引擎被卡住时可能需要一些输入假设）。然而，能被用此方式分析的算法复杂度仍是适中的（由于推理引擎的限制），而工作量是巨大的。因为这些原因，我们不深入研究oracles的开发