[clang-tidy] add check cppcoreguidelines-pro-bounds-constant-array-index

[mgehre]

Summary

This is http://reviews.llvm.org/D13746 but instead of including <array>,
a stub is provided.
This check flags all array subscriptions on static arrays and
std::arrays that either have a non-compile-time-constant index or are
out of bounds.

Dynamic accesses into arrays are difficult for both tools and humans to
validate as safe. array_view is a bounds-checked, safe type for
accessing arrays of data. at() is another alternative that ensures
single accesses are bounds-checked. If iterators are needed to access an
array, use the iterators from an array_view constructed over the array.

This rule is part of the "Bounds safety" profile of the C++ Core
Guidelines, see
https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#-bounds2-only-index-into-arrays-using-constant-expressions

[aaron.ballman]

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

29

Why GslHeader but not IncludeStyle?

79

instead of "compile-time constant", we should use "integer constant expression".

89

Please do not use auto here, it is not obvious what type will be returned.

92

Can just use if (Insertion) instead.

107

"index %0 is negative" is shorter and should be obvious as to what the issue is.

112

Please do not use auto here either.

docs/clang-tidy/checks/cppcoreguidelines-pro-bounds-constant-array-index.rst

4

Instead of "array subscriptions" it should be "array subscript expressions". Can also change "non-compile-time constant" to "that either do not have a constant integer expression"

7

I'm not comfortable with directly copying the text from the C++ Core Guidelines into our own documentation. I don't believe their license allows this.

9

s/generated/generate

test/clang-tidy/cppcoreguidelines-pro-bounds-constant-array-index.cpp

1

We should have an additional test that does not have the GslHeader option set as well.

[alexfh]

Sorry for the delay. Missed this patch somehow. A couple of comments in addition to what Aaron wrote.

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.h

25

This can be const.

docs/clang-tidy/checks/cppcoreguidelines-pro-bounds-constant-array-index.rst

4

nit: I believe, .rst files should also have the 80 columns limit.

[mgehre]

Thanks for the comments!

[alexfh]

One more nit. Leaving the rest to Aaron, since most of the comments were his.

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.h

26

GslHeader can be const as well.

[aaron.ballman]

With the fix for Alex's last comment, LGTM!

clang-tidy/cppcoreguidelines/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyCppCoreGuidelinesModule
   CppCoreGuidelinesTidyModule.cpp
   ProBoundsArrayToPointerDecayCheck.cpp
+  ProBoundsConstantArrayIndexCheck.cpp
   ProBoundsPointerArithmeticCheck.cpp
   ProTypeConstCastCheck.cpp
   ProTypeCstyleCastCheck.cpp
   ProTypeReinterpretCastCheck.cpp
   ProTypeStaticCastDowncastCheck.cpp
   ProTypeUnionAccessCheck.cpp
   ProTypeVarargCheck.cpp
 

clang-tidy/cppcoreguidelines/CppCoreGuidelinesTidyModule.cpp

 //===--- CppCoreGuidelinesModule.cpp - clang-tidy -------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "../misc/AssignOperatorSignatureCheck.h"
 #include "ProBoundsArrayToPointerDecayCheck.h"
+#include "ProBoundsConstantArrayIndexCheck.h"
 #include "ProBoundsPointerArithmeticCheck.h"
 #include "ProTypeConstCastCheck.h"
 #include "ProTypeCstyleCastCheck.h"
 #include "ProTypeReinterpretCastCheck.h"
 #include "ProTypeStaticCastDowncastCheck.h"
 #include "ProTypeUnionAccessCheck.h"
 #include "ProTypeVarargCheck.h"
 
 namespace clang {
 namespace tidy {
 namespace cppcoreguidelines {
 
 /// A module containing checks of the C++ Core Guidelines
 class CppCoreGuidelinesModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ProBoundsArrayToPointerDecayCheck>(
         "cppcoreguidelines-pro-bounds-array-to-pointer-decay");
+    CheckFactories.registerCheck<ProBoundsConstantArrayIndexCheck>(
+        "cppcoreguidelines-pro-bounds-constant-array-index");
     CheckFactories.registerCheck<ProBoundsPointerArithmeticCheck>(
         "cppcoreguidelines-pro-bounds-pointer-arithmetic");
     CheckFactories.registerCheck<ProTypeConstCastCheck>(
         "cppcoreguidelines-pro-type-const-cast");
     CheckFactories.registerCheck<ProTypeCstyleCastCheck>(
         "cppcoreguidelines-pro-type-cstyle-cast");
     CheckFactories.registerCheck<ProTypeReinterpretCastCheck>(
         "cppcoreguidelines-pro-type-reinterpret-cast");

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.h

+//===--- ProBoundsConstantArrayIndexCheck.h - clang-tidy---------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_CPPCOREGUIDELINES_PRO_BOUNDS_CONSTANT_ARRAY_INDEX_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_CPPCOREGUIDELINES_PRO_BOUNDS_CONSTANT_ARRAY_INDEX_H
+
+#include "../ClangTidy.h"
+#include "../utils/IncludeInserter.h"
+
+namespace clang {
+namespace tidy {
+
+/// This checks that all array subscriptions on static arrays and std::arrays
+/// have a constant index and are within bounds
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/cppcoreguidelines-pro-bounds-constant-array-index.html
+class ProBoundsConstantArrayIndexCheck : public ClangTidyCheck {
+  std::string GslHeader;
+  const IncludeSorter::IncludeStyle IncludeStyle;
+  std::unique_ptr<IncludeInserter> Inserter;
+
+public:
+  ProBoundsConstantArrayIndexCheck(StringRef Name, ClangTidyContext *Context);
+  void registerPPCallbacks(CompilerInstance &Compiler) override;
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_CPPCOREGUIDELINES_PRO_BOUNDS_CONSTANT_ARRAY_INDEX_H

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

+//===--- ProBoundsConstantArrayIndexCheck.cpp - clang-tidy-----------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ProBoundsConstantArrayIndexCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Lex/Preprocessor.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+
+ProBoundsConstantArrayIndexCheck::ProBoundsConstantArrayIndexCheck(
+    StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context), GslHeader(Options.get("GslHeader", "")),
+      IncludeStyle(IncludeSorter::parseIncludeStyle(
+          Options.get("IncludeStyle", "llvm"))) {}
+
+void ProBoundsConstantArrayIndexCheck::storeOptions(
+    ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "GslHeader", GslHeader);
+}
+
+void ProBoundsConstantArrayIndexCheck::registerPPCallbacks(
+    CompilerInstance &Compiler) {
+  if (!getLangOpts().CPlusPlus)
+    return;
+
+  Inserter.reset(new IncludeInserter(Compiler.getSourceManager(),
+                                     Compiler.getLangOpts(), IncludeStyle));
+  Compiler.getPreprocessor().addPPCallbacks(Inserter->CreatePPCallbacks());
+}
+
+void ProBoundsConstantArrayIndexCheck::registerMatchers(MatchFinder *Finder) {
+  if (!getLangOpts().CPlusPlus)
+    return;
+
+  Finder->addMatcher(arraySubscriptExpr(hasBase(ignoringImpCasts(hasType(
+                                            constantArrayType().bind("type")))),
+                                        hasIndex(expr().bind("index")))
+                         .bind("expr"),
+                     this);
+
+  Finder->addMatcher(
+      cxxOperatorCallExpr(
+          hasOverloadedOperatorName("[]"),
+          hasArgument(
+              0, hasType(cxxRecordDecl(hasName("::std::array")).bind("type"))),
+          hasArgument(1, expr().bind("index")))
+          .bind("expr"),
+      this);
+}
+
+void ProBoundsConstantArrayIndexCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  const auto *Matched = Result.Nodes.getNodeAs<Expr>("expr");
+  const auto *IndexExpr = Result.Nodes.getNodeAs<Expr>("index");
+  llvm::APSInt Index;
+  if (!IndexExpr->isIntegerConstantExpr(Index, *Result.Context, nullptr,
+                                        /*isEvaluated=*/true)) {
+    SourceRange BaseRange;
+    if (const auto *ArraySubscriptE = dyn_cast<ArraySubscriptExpr>(Matched))
+      BaseRange = ArraySubscriptE->getBase()->getSourceRange();
+    else
+      BaseRange =
+          dyn_cast<CXXOperatorCallExpr>(Matched)->getArg(0)->getSourceRange();
+    SourceRange IndexRange = IndexExpr->getSourceRange();
+
+    auto Diag = diag(Matched->getExprLoc(),
+                     "do not use array subscript when the index is "
+                     "not a compile-time constant; use gsl::at() "
+                     "instead");
+    if (!GslHeader.empty()) {
+      Diag << FixItHint::CreateInsertion(BaseRange.getBegin(), "gsl::at(")
+           << FixItHint::CreateReplacement(
+                  SourceRange(BaseRange.getEnd().getLocWithOffset(1),
+                              IndexRange.getBegin().getLocWithOffset(-1)),
+                  ", ")
+           << FixItHint::CreateReplacement(Matched->getLocEnd(), ")");
+
+      auto Insertion = Inserter->CreateIncludeInsertion(
+          Result.SourceManager->getMainFileID(), GslHeader,
+          /*IsAngled=*/false);
+      if (Insertion.hasValue())
+        Diag << Insertion.getValue();
+    }
+    return;
+  }
+
+  const auto *StdArrayDecl =
+      Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("type");
+
+  // For static arrays, this is handled in clang-diagnostic-array-bounds.
+  if (!StdArrayDecl)
+    return;
+
+  if (Index.isSigned() && Index.isNegative()) {
+    diag(Matched->getExprLoc(),
+         "std::array<> index %0 is before the beginning of the array")
+        << Index.toString(10);
+    return;
+  }
+
+  const auto &TemplateArgs = StdArrayDecl->getTemplateArgs();
+  if (TemplateArgs.size() < 2)
+    return;
+  // First template arg of std::array is the type, second arg is the size.
+  const auto &SizeArg = TemplateArgs[1];
+  if (SizeArg.getKind() != TemplateArgument::Integral)
+    return;
+  llvm::APInt ArraySize = SizeArg.getAsIntegral();
+
+  // Get uint64_t values, because different bitwidths would lead to an assertion
+  // in APInt::uge.
+  if (Index.getZExtValue() >= ArraySize.getZExtValue()) {
+    diag(Matched->getExprLoc(), "std::array<> index %0 is past the end of the array "
+                                "(which contains %1 elements)")
+        << Index.toString(10) << ArraySize.toString(10, false);
+  }
+}
+
+} // namespace tidy
+} // namespace clang

docs/clang-tidy/checks/cppcoreguidelines-pro-bounds-constant-array-index.rst

+cppcoreguidelines-pro-bounds-constant-array-index
+=================================================
+
+This check flags all array subscriptions on static arrays and std::arrays that either have a non-compile-time constant index or are out of bounds (for std::array).
+For out-of-bounds checking of static arrays, see the clang-diagnostic-array-bounds check.
+
+Dynamic accesses into arrays are difficult for both tools and humans to validate as safe. gsl::span is a bounds-checked, safe type for accessing arrays of data. gsl::at() is another alternative that ensures single accesses are bounds-checked. If iterators are needed to access an array, use the iterators from an gsl::span constructed over the array.
+
+The check can generated fixes after the option cppcoreguidelines-pro-bounds-constant-array-index.GslHeader has been set to the name of the
+include file that contains gsl::at(), e.g. "gsl/gsl.h".
+
+This rule is part of the "Bounds safety" profile of the C++ Core Guidelines, see
+https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#-bounds2-only-index-into-arrays-using-constant-expressions.

docs/clang-tidy/checks/list.rst

 List of clang-tidy Checks
 =========================
 
 .. toctree::
    cert-setlongjmp
    cert-thrown-exception-type
    cert-variadic-function-def
    cppcoreguidelines-pro-bounds-array-to-pointer-decay
+   cppcoreguidelines-pro-bounds-constant-array-index
    cppcoreguidelines-pro-bounds-pointer-arithmetic
    cppcoreguidelines-pro-type-const-cast
    cppcoreguidelines-pro-type-cstyle-cast
    cppcoreguidelines-pro-type-reinterpret-cast
    cppcoreguidelines-pro-type-static-cast-downcast
    cppcoreguidelines-pro-type-union-access
    cppcoreguidelines-pro-type-vararg
    google-build-explicit-make-pair

test/clang-tidy/cppcoreguidelines-pro-bounds-constant-array-index.cpp

+// RUN: %check_clang_tidy %s cppcoreguidelines-pro-bounds-constant-array-index %t -- -config='{CheckOptions: [{key: cppcoreguidelines-pro-bounds-constant-array-index.GslHeader, value: "dir1/gslheader.h"}]}' -- -std=c++11
+// CHECK-FIXES: #include "dir1/gslheader.h"
+
+typedef unsigned int size_t;
+
+namespace std {
+  template<typename T, size_t N>
+  struct array {
+    T& operator[](size_t n);
+    T& at(size_t n);
+  };
+}
+
+
+namespace gsl {
+  template<class T, size_t N>
+  T& at( T(&a)[N], size_t index );
+
+  template<class T, size_t N>
+  T& at( std::array<T, N> &a, size_t index );
+}
+
+constexpr int const_index(int base) {
+  return base + 3;
+}
+
+void f(std::array<int, 10> a, int pos) {
+  a [ pos / 2 /*comment*/] = 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: do not use array subscript when the index is not a compile-time constant; use gsl::at() instead [cppcoreguidelines-pro-bounds-constant-array-index]
+  // CHECK-FIXES: gsl::at(a,  pos / 2 /*comment*/) = 1;
+  int j = a[pos - 1];
+  // CHECK-MESSAGES: :[[@LINE-1]]:11: warning: do not use array subscript when the index is not a compile-time constant; use gsl::at() instead
+  // CHECK-FIXES: int j = gsl::at(a, pos - 1);
+
+  a.at(pos-1) = 2; // OK, at() instead of []
+  gsl::at(a, pos-1) = 2; // OK, gsl::at() instead of []
+
+  a[-1] = 3;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: std::array<> index -1 is before the beginning of the array [cppcoreguidelines-pro-bounds-constant-array-index]
+  a[10] = 4;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: std::array<> index 10 is past the end of the array (which contains 10 elements) [cppcoreguidelines-pro-bounds-constant-array-index]
+
+  a[const_index(7)] = 3;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: std::array<> index 10 is past the end of the array (which contains 10 elements)
+
+  a[0] = 3; // OK, constant index and inside bounds
+  a[1] = 3; // OK, constant index and inside bounds
+  a[9] = 3; // OK, constant index and inside bounds
+  a[const_index(6)] = 3; // OK, constant index and inside bounds
+}
+
+void g() {
+  int a[10];
+  for (int i = 0; i < 10; ++i) {
+    a[i] = i;
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: do not use array subscript when the index is not a compile-time constant; use gsl::at() instead
+    // CHECK-FIXES: gsl::at(a, i) = i;
+    gsl::at(a, i) = i; // OK, gsl::at() instead of []
+  }
+
+  a[-1] = 3; // flagged by clang-diagnostic-array-bounds
+  a[10] = 4; // flagged by clang-diagnostic-array-bounds
+  a[const_index(7)] = 3; // flagged by clang-diagnostic-array-bounds
+
+  a[0] = 3; // OK, constant index and inside bounds
+  a[1] = 3; // OK, constant index and inside bounds
+  a[9] = 3; // OK, constant index and inside bounds
+  a[const_index(6)] = 3; // OK, constant index and inside bounds
+}
+
+struct S {
+  int& operator[](int i);
+};
+
+void customOperator() {
+  S s;
+  int i = 0;
+  s[i] = 3; // OK, custom operator
+}