CTR54-CPP. 不要相减不是指向同一个容器的迭代器

原文链接：

CTR54-CPP. Do not subtract iterators that do not refer to the same container

https://wiki.sei.cmu.edu/confluence/display/cplusplus/CTR54-CPP.+Do+not+subtract+iterators+that+do+not+refer+to+the+same+container

当两个指针相减，两个指针必须指向同一个数组对象的元素或者指向数组对象最后一个元素之后；结果就是两个数组元素下标的差值。类似地，当两个迭代器相减时 (包括通过 std::distance())，两个迭代器必须指向相同的容器对象或者必须通过在同一个迭代器对象调用 end() 获得 (或者 cend())。

如果两个无关的迭代器 (包括指针) 相减，该操作导致undefined behavior [ISO/IEC 14882-2014]。不要相减两个迭代器 (包括指针) ，除非两个指向同一个迭代器或者其中一个迭代器超过容器的尾部。

When two pointers are subtracted, both must point to elements of the same array object or to one past the last element of the array object; the result is the difference of the subscripts of the two array elements. Similarly, when two iterators are subtracted (including via std::distance()), both iterators must refer to the same container object or must be obtained via a call to end() (or cend()) on the same container object.

If two unrelated iterators (including pointers) are subtracted, the operation results in undefined behavior [ISO/IEC 14882-2014]. Do not subtract two iterators (including pointers) unless both point into the same container or one past the end of the same container.

不合规的代码示例 Noncompliant Code Example

这个不合规的代码示例试图判断指针 test 是否在范围[r, r + n] 内。然而，当 test 不指向给定的范围内，像在这个例子中，相减将产生未定义行为。

This noncompliant code example attempts to determine whether the pointer test is within the range [r, r + n]. However, when test does not point within the given range, as in this example, the subtraction produces undefined behavior.

#include <cstddef>
#include <iostream>

template <typename Ty>
bool in_range(const Ty *test, const Ty *r, size_t n) {
  return 0 < (test - r) && (test - r) < (std::ptrdiff_t)n;
}

void f() {
  double foo[10];
  double *x = &foo[0];
  double bar;
  std::cout << std::boolalpha << in_range(&bar, x, 10);
}

不合规的代码示例 Noncompliant Code Example

在这个不合规的代码示例中，in_range() 函数通过使用比较函数代替减法来实现。C++ 标准， [expr.rel], paragraph 4 [ISO/IEC 14882-2014], 陈述如下:

In this noncompliant code example, the in_range() function is implemented using a comparison expression instead of subtraction. The C++ Standard, [expr.rel], paragraph 4 [ISO/IEC 14882-2014], states the following:

If two operands p and q compare equal, p<=q and p>=q both yield true and p<q and p>q both yield false. Otherwise, if a pointer p compares greater than a pointer q, p>=q, p>q, q<=p, and q<p all yield true and p<=q, p<q, q>=p, and q>p all yield false. Otherwise, the result of each of the operators is unspecified.

因此，比较两个不是指向同一个容器的指针或者其中之一超出容器之后将造成 unspecified behavior。虽然下面的例子是先前不合规代码示例的提升，但是它不会产生可移植代码并且在分段内存架构 (例如一些果实的 x86 变体) 机器上执行是可能失败。所以，这是不合规的。

Thus, comparing two pointers that do not point into the same container or one past the end of the container results in unspecified behavior. Although the following example is an improvement over the previous noncompliant code example, it does not result in portable code and may fail when executed on a segmented memory architecture (such as some antiquated x86 variants). Consequently, it is noncompliant.

#include <iostream>

template <typename Ty>
bool in_range(const Ty *test, const Ty *r, size_t n) {
  return test >= r && test < (r + n);
}

void f() {
  double foo[10];
  double *x = &foo[0];
  double bar;
  std::cout << std::boolalpha << in_range(&bar, x, 10);
}

不合规的代码示例 Noncompliant Code Example

这个不合规的代码示例和先前的示例大致相同，只是它是使用迭代器来替换原始指针。和先前的例子一样， in_range_impl() 函数呈现了 unspecified behavior ，当迭代器没有指向同一个容器，因为操作语义 a < b 对于随机访问的迭代器是 b - a > 0，并且>= 是由 < 实现的.

This noncompliant code example is roughly equivalent to the previous example, except that it uses iterators in place of raw pointers. As with the previous example, the in_range_impl() function exhibits unspecified behavior when the iterators do not refer into the same container because the operational semantics of a < b on a random access iterator are b - a > 0, and >= is implemented in terms of <.

#include <iostream>
#include <iterator>
#include <vector>

template <typename RandIter>
bool in_range_impl(RandIter test, RandIter r_begin, RandIter r_end, std::random_access_iterator_tag) {
  return test >= r_begin && test < r_end;
}

template <typename Iter>
bool in_range(Iter test, Iter r_begin, Iter r_end) {
  typename std::iterator_traits<Iter>::iterator_category cat;
  return in_range_impl(test, r_begin, r_end, cat);
}

void f() {
  std::vector<double> foo(10);
  std::vector<double> bar(1);
  std::cout << std::boolalpha << in_range(bar.begin(), foo.begin(), foo.end());
}

不合规的代码示例 Noncompliant Code Example

在这个不合规的代码示例中，std::less<> 用来替换 < 操作。C++ 标准 [comparisons], paragraph 14 [ISO/IEC 14882-2014]，陈述如下：

In this noncompliant code example, std::less<> is used in place of the < operator. The C++ Standard, [comparisons], paragraph 14 [ISO/IEC 14882-2014], states the following:

For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not.

虽然这个方式生成了全序，但是这个全序的定义根据实现依然不是特定的。举个例子，下述对于给定的，无关的指针， a 和 b 会导致触发断言：assert(std::less<T *>()(a, b) == std::greater<T *>()(a, b));。因此，这个不合规的代码例子依然是不可移植的，并且对于 std::less<> 一般的实现，当调用 < 运算符时，可能甚至导致 undefined behavior 。

Although this approach yields a total ordering, the definition of that total ordering is still unspecified by the implementation. For instance, the following statement could result in the assertion triggering for a given, unrelated pair of pointers, a and b: assert(std::less<T *>()(a, b) == std::greater<T *>()(a, b));. Consequently, this noncompliant code example is still nonportable and, on common implementations of std::less<>, may even result in undefined behavior when the < operator is invoked.

#include <functional>
#include <iostream>

template <typename Ty>
bool in_range(const Ty *test, const Ty *r, size_t n) {
  std::less<const Ty *> less;
  return !less(test, r) && less(test, r + n);
}

void f() {
  double foo[10];
  double *x = &foo[0];
  double bar;
  std::cout << std::boolalpha << in_range(&bar, x, 10);
}

合规的方案 Compliant Solution

这个合规的方案呈现了一个完全可移植的，但是或许低效的 in_range() 的实现，通过比较 test 和范围 [r, n] 内每个可能的地址。一个兼顾效率和完全可移植的合规方案目前未知。

This compliant solution demonstrates a fully portable, but likely inefficient, implementation of in_range() that compares test against each possible address in the range [r, n]. A compliant solution that is both efficient and fully portable is currently unknown.

#include <iostream>

template <typename Ty>
bool in_range(const Ty *test, const Ty *r, size_t n) {
  auto *cur = reinterpret_cast<const unsigned char *>(r);
  auto *end = reinterpret_cast<const unsigned char *>(r + n);
  auto *testPtr = reinterpret_cast<const unsigned char *>(test);

  for (; cur != end; ++cur) {
    if (cur == testPtr) {
      return true;
    }
  }
  return false;
}

void f() {
  double foo[10];
  double *x = &foo[0];
  double bar;
  std::cout << std::boolalpha << in_range(&bar, x, 10);
}

风险预估 Risk Assessment

Rule	Severity	Likelihood	Remediation Cost	Priority	Level
CTR54-CPP	Medium	Probable	Medium	P8	L2

Automated Detection

Tool	Checker	Description
LDRA tool suite	70 S, 87 S, 437 S, 438 S	Enhanced Enforcement
Parasoft C/C++test	CERT_CPP-CTR54-a CERT_CPP-CTR54-b	Do not compare iterators from different containers Do not compare two unrelated pointers
PRQA QA-C++	2668, 2761, 2762, 2763, 2766, 2767, 2768	Enforced by QA-CPP