25-模板的调试

浅实例化(Shallow Instantiation)

  • 模板出错时通常伴随着冗长的诊断信息,真正的问题一般出现在一长串实例化之后
template<typename T>
void f1(T& p)
{
  *p = 0; // assumes T is a pointer-like type
}

template<typename T>
void f2(T& p)
{
  f1(p);
}

template<typename T>
void f3(typename T::Type p)
{
  f2(p);
}

template<typename T>
void f4(const T& x)
{
  typename T::Type i;
  f3<T>(i);
}

class X {
 public:
  using Type = int;
};

int main()
{
  X x;
  f4(x); // 错误(只能在实例化时被检测到)
}
  • 实例化f4()时,其中嵌套的模板都需要实例化,最终出错的原因是f1()中对一个int变量解引用
f4(x)
// 实例化
f4<X>(const X&)
// 实例化
f3<X>(X::Type)
// 实例化
f2<X::Type>(X::Type&)
// 实例化
f1<X::Type>(X::Type&)
// 即
f1(int& p)
{
  *p = 0; // 出错
}
  • 一般泛型的诊断信息会跟踪导致问题的所有层次,这就产生了冗长的信息,从而使调试变得更为繁琐。关于此问题,Bjarne Stroustrup定义了两类方法来提前确定模板实参满足一些限制:一是添加一个语言扩展(即Concepts,但C++17中仍未引入),二是借助无其他目的的代码提前使用参数,如提前在f4()中尝试解引用T::Type类型值
void ignore(const T&) {}

template<typename T>
void f4(const T& x)
{
  class ShallowChecks
  {
    void deref(typename T::Type p)
    {
      ignore(*p);
    }
  };
  typename T::Type i;
  f3(i);
}
  • T::Type不能解引用时,错误将在局部类ShallowChecks中被诊断。因为局部类未使用,添加的代码不影响f4()的运行期,不过许多编译器将警告ShallowChecks未使用,使用ignore()之类的技巧可以避免这样的警告,但增加了代码的复杂度

静态断言(Static Assertion)

  • C++11引入了static_assert,在编译期进行断言,比如下列静态断言确保编译平台带64位指针
static_assert(sizeof(void*) * CHAR_BIT == 64, "Not a 64-bit platform");
  • 创建一个检查解引用的type traits,即可用static_assert为f4()提供更明确的诊断信息
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;
};

void f4 (const T& x)
{
  static_assert(HasDereference<T>::value, "T is not dereferenceable");
  typename T::Type i;
  f3(i);
}
template<typename T>
class C {
  static_assert(HasDereference<T>::value, "T is not dereferenceable");
  static_assert(std::is_default_constructible_v<T>, "T is not default constructible");
  ...
};

原型(Archetype)

  • 模板的一个挑战是确保满足特定约束的实参都能通过编译。考虑一个简单的find()算法,它查找数组中的一个值所在的位置
// 要求T必须是可比较的类型,即两个T对象能用==比较,且结果为bool
template<typename T>
int find(const T* a, int n, const T& val)
{
  int i = 0;
  while (i != n && a[i] != val) ++i;
  return i;
}
  • 为了测试满足要求的模板参数,引入原型的概念。原型是用户定义的类,以尽可能小的方式来满足模板大多数要求,而不提供任何外来的操作。下面是尝试满足可比较要求的原型
class EqualityComparableArchetype {};

class ConvertibleToBoolArchetype {
 public:
  operator bool() const; // 提供本类型到bool的隐式转换
};

ConvertibleToBoolArchetype // 返回类型要求能转换为bool
operator==(const EqualityComparableArchetype&, const EqualityComparableArchetype&);

// 实例化find<EqualityComparableArchetype>
template int find(const EqualityComparableArchetype*, int,
  const EqualityComparableArchetype&);
  • 实例化将失败,于是可以发现问题:EqualityComparable描述只需要operator==,但是find()中用operator!=比较。改用operator==比较即可解决此问题
template<typename T>
int find(const T* a, int n, const T& val)
{
  int i = 0;
  while (i != n && !(a[i] == val)) ++i;
  return i;
}
  • 新定义的find()使用operator!直接产生到operator==的结果。在原型的情况中,这依赖于用户定义的到bool的转换以及内建的operator!。ConvertibleToBoolArchetype中禁用operator!即可使其不能被不适当地使用
class ConvertibleToBoolArchetype {
 public:
  operator bool() const;
  bool operator!() = delete;
};
  • 原型可以扩展得更远,比如禁用operator&&operator||来找出其他的一些模板定义中的问题

跟踪程序(Tracer)

  • 以上讨论的都是编译或链接时的bug,然而更大的挑战通常是确保成功构建后,程序在运行期表现正确
  • tracer是一个用户定义的类,它能用作要测试的模板的实参。通常tracer也是一个原型,但包含一些额外的信息。下面是一个用于测试排序算法的tracer
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(const SortTracer& 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=(const SortTracer& b)
  {
    ++n_assigned;
    std::cerr << "SortTracer assignment #" << n_assigned
      << " (generation " << generation
      << " = " << b.generation
      << ")\n";
    value = b.value;
    return *this;
  }

  // comparison
  friend bool operator<(const SortTracer& a, const SortTracer& 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,对每个对象,generation跟踪从原始对象中移除多少复制操作,其他静态成员跟踪构造、析构、赋值比较等数量,以及对象存在的最大数量。下面用这个tracer测试std::sort
int main()
{
  SortTracer input[] = { 7, 3, 5, 6, 4, 2, 0, 1, 9, 8 };

  // 打印初始值
  for (int i = 0; i < 10; ++i)
  {
    std::cerr << input[i].val() << ' ';
  }
  std::cerr << '\n';

  // 记录初始条件
  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();

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

  // 检查结果
  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";
}
  • final report中将打印
std::sort() of 10 SortTracer's was performed by:
9 temporary tracers
up to 11 tracers at the same time (10 before)
33 assignments
42 comparisons
  • tracer提供std::sort需要的功能(比如operator==operator>),并给出算法开销的直观结果,但不揭示排序模板的正确性

Oracles

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

文章作者: 张小飞
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 张小飞 !
 本篇
25-模板的调试 25-模板的调试
浅实例化(Shallow Instantiation) 模板出错时通常伴随着冗长的诊断信息,真正的问题一般出现在一长串实例化之后 template<typename T> void f1(T& p) { *p = 0;
下一篇 
24-表达式模板 24-表达式模板
表达式模板是为了支持一种数值数组的类引入的技术。比如希望像内置类型一样对数组进行下列操作,要在支持这种紧凑写法的同时获得高效率,就需要通过表达式模板来完成。表达式模板与元编程互补,元编程主要用于小的、大小固定的数组,表达式模板则用于能在运
  目录