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

[mgehre]

Summary

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

[mgehre]

Remove dead codet

[sbenza]

Thanks for the patch.
A few comments below.

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

23 ↗

(On Diff #37401)

All this code needs to be reformatted to 80 cols.
http://llvm.org/docs/CodingStandards.html#source-code-width

Have you tried clang-format?
It does a great job here.

28 ↗

(On Diff #37401)

hasType(qualType(hasDeclaration(classTemplateSpecializationDecl(hasName("::std::array"))))

can be written as

hasType(cxxRecordDecl(hasName("::std::array")))

36 ↗

(On Diff #37401)

Move this declaration closer to its first use.

55 ↗

(On Diff #37401)

Space after //

55 ↗

(On Diff #37401)

If this check is enabled, it is very likely that the library is available.
Maybe we should suggest the fix.
You can use clang::tidy::IncludeInserter to add the include if needed.

We could also add a configuration option to enable/disable the automated fix for this case.

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.h

18 ↗

(On Diff #37401)

reflow to 80 cols

[mgehre]

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

55 ↗

(On Diff #37401)

One issue I see is that the gsl header does not have a standard name. I currently know of the microsoft gsl and gsl-lite (https://github.com/martinmoene/gsl-lite), and they don't agree on the name of the header.

I could make an option "gsl-header-name", which defaults to an empty string. If it is set to an non-empty filename,
the fix is enabled and that header is used.

What do you think?

[mgehre]

Thanks for the comments!

[mgehre]

Fixed most comments in updated revision

[sbenza]

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

55 ↗

(On Diff #37401)

Interesting.
The only downside I see with that is gsl-header-name might be useful for other checks in this package, and the options API only supports per-check options.
You would have to pass it once for every check that needs it.
They are specified as <CheckName>.<OptionName>.
Maybe we can add a Global category or package level flags so that it can apply to all checks under cppcoreguidelines-*.

[alexfh]

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

56 ↗

(On Diff #37627)

We can go for a local setting for now, and if we introduce global or module-wide options, we can clean up these local settings in a single step.

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

50 ↗

(On Diff #37627)

What's the difference between this warning and the -Warray-bounds compiler diagnostic that is turned on by default?

$ cat /tmp/q.cc 
void f() {
  int a[7];
  a[10];
}
$ clang_check /tmp/q.cc --
...
/tmp/q.cc:3:3: warning: array index 10 is past the end of the array (which contains 7 elements) [-Warray-bounds]
  a[10];
  ^ ~~
/tmp/q.cc:2:3: note: array 'a' declared here
  int a[7];
  ^

[mgehre]

Add option GslHeader, generate fixes

[alexfh]

Sorry for the delay. A few more comments.

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

86 ↗

(On Diff #39601)

nit: What is true here? Please add an argument comment.

102 ↗

(On Diff #39601)

I'm not sure initializer lists are supported by all toolchains this code needs to compile on. Please explicitly specify SourceRange here.

124 ↗

(On Diff #39601)

nit: please add trailing period.

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

12 ↗

(On Diff #39601)

nit: please add trailing period.

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

51 ↗

(On Diff #39601)

So what's the difference between this warning and -Warray-bounds?

[mgehre]

update for review comments; removed bounds check on static arrays in favor of clang-diagnostic-array-bounds

[mgehre]

simplify code

[alexfh]

Looks good with one comment.

Thank you!

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

107 ↗

(On Diff #39953)

To avoid confusion, I suggest explicitly stating that this is an std::array, not a regular array ("std::array<> index %0 is before ..."). Same for the message below.

Also, it's fine to have this in clang-tidy for now, but ultimately, it may be reasonable and more consistent to analyze this in Clang as a part of -Warray-bounds. However, I'm not sure whether it's better to make a library-specific warning in Clang or introduce some annotation to tell the compiler that it can statically check indexes using a certain expression, for example.

[chapuni]

I have reverted in r253428, since I can reproduce failure locally. I'll investigate later, too.

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

2

Standard headers might be unavailable depending on a target, like host=linux target=msvc.
Could you improve it?

1. Avoid <array>
2. Introduce a new feature like "native"

[mgehre]

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

2

Just to make sure that I understand this: The array header is unavailble because the target is a pre-C++11 msvc?

I can replace #include <array> by an stub definition of std::array. I'm not sure what you mean by 'Introduce a new feature like "native"'?

[chapuni]

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

2

It'd be good that stub version of <array>.

"Features" mean like

REQUIRES: foo-supported-feature

See also clang-tools-extra/test/lit.cfg, or clang/test/lit.cfg.

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 {
+  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);
+}
+
+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

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 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.

clang-tools-extra/trunk/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

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 -- -config='{CheckOptions: [{key: cppcoreguidelines-pro-bounds-constant-array-index.GslHeader, value: "dir1/gslheader.h"}]}' -- -std=c++11
+#include <array>
+// CHECK-FIXES: #include "dir1/gslheader.h"
+
+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
+}