[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 ↗

(On Diff #41274)

Why GslHeader but not IncludeStyle?

79 ↗

(On Diff #41274)

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

89 ↗

(On Diff #41274)

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

92 ↗

(On Diff #41274)

Can just use if (Insertion) instead.

107 ↗

(On Diff #41274)

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

112 ↗

(On Diff #41274)

Please do not use auto here either.

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

4 ↗

(On Diff #41274)

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 ↗

(On Diff #41274)

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 ↗

(On Diff #41274)

s/generated/generate

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

1 ↗

(On Diff #41274)

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 ↗

(On Diff #41274)

This can be const.

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

4 ↗

(On Diff #41274)

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

25 ↗

(On Diff #42338)

GslHeader can be const as well.

[aaron.ballman]

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

clang-tools-extra/trunk/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-tools-extra/trunk/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-tools-extra/trunk/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 {
+  const 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-tools-extra/trunk/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);
+  Options.store(Opts, "IncludeStyle", IncludeStyle);
+}
+
+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 an integer constant expression; 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(), ")");
+
+      Optional<FixItHint> Insertion = Inserter->CreateIncludeInsertion(
+          Result.SourceManager->getMainFileID(), GslHeader,
+          /*IsAngled=*/false);
+      if (Insertion)
+        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 negative")
+        << Index.toString(10);
+    return;
+  }
+
+  const TemplateArgumentList &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

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

+cppcoreguidelines-pro-bounds-constant-array-index
+=================================================
+
+This check flags all array subscript expressions on static arrays and
+std::arrays that either do not have a constant integer expression index or
+are out of bounds (for std::array). For out-of-bounds checking of static
+arrays, see the clang-diagnostic-array-bounds check.
+
+The check can generate 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.

clang-tools-extra/trunk/docs/clang-tidy/checks/list.rst

 List of clang-tidy Checks
 =========================
 
 .. toctree::   
    cert-setlongjmp
    cert-static-object-exception
    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

clang-tools-extra/trunk/test/clang-tidy/cppcoreguidelines-pro-bounds-constant-array-index-gslheader.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 an integer constant expression; 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 an integer constant expression; 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 negative [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 an integer constant expression; 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
+}

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

+// RUN: %check_clang_tidy %s cppcoreguidelines-pro-bounds-constant-array-index %t
+
+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 an integer constant expression; use gsl::at() instead [cppcoreguidelines-pro-bounds-constant-array-index]
+  int j = a[pos - 1];
+  // CHECK-MESSAGES: :[[@LINE-1]]:11: warning: do not use array subscript when the index is not an integer constant expression; use gsl::at() instead
+
+  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 negative [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 an integer constant expression; 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
+}