[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

24

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.

29

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

can be written as

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

37

Move this declaration closer to its first use.

56

Space after //

56

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

19

reflow to 80 cols

[mgehre]

clang-tidy/cppcoreguidelines/ProBoundsConstantArrayIndexCheck.cpp

56

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

56

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

57

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

51

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

87

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

103

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

125

nit: please add trailing period.

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

13

nit: please add trailing period.

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

52

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

108

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 ↗

(On Diff #40449)

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 ↗

(On Diff #40449)

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 ↗

(On Diff #40449)

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-tidy/cppcoreguidelines/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyCppCoreGuidelinesModule
   CppCoreGuidelinesTidyModule.cpp
+  ProBoundsConstantArrayIndexCheck.cpp
   ProBoundsPointerArithmeticCheck.cpp
   ProTypeConstCastCheck.cpp
   ProTypeReinterpretCastCheck.cpp
   ProTypeStaticCastDowncastCheck.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangLex
   clangTidy
   clangTidyUtils
   clangTooling
   )

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 "ProBoundsConstantArrayIndexCheck.h"
 #include "ProBoundsPointerArithmeticCheck.h"
 #include "ProTypeConstCastCheck.h"
 #include "ProTypeReinterpretCastCheck.h"
 #include "ProTypeStaticCastDowncastCheck.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<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<ProTypeReinterpretCastCheck>(
         "cppcoreguidelines-pro-type-reinterpret-cast");
     CheckFactories.registerCheck<ProTypeStaticCastDowncastCheck>(
         "cppcoreguidelines-pro-type-static-cast-downcast");

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"
+
+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 {
+public:
+  ProBoundsConstantArrayIndexCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) 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"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+
+AST_MATCHER(Expr, isIntegerConstantExpr) {
+  return Node.isIntegerConstantExpr(Finder->getASTContext(), nullptr);
+}
+
+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(qualType(hasDeclaration(classTemplateSpecializationDecl(hasName("::std::array")).bind("type"))))),
+                                         hasArgument(1, expr().bind("index"))
+                                        ).bind("expr"),
+                     this);
+}
+
+void ProBoundsConstantArrayIndexCheck::check(const MatchFinder::MatchResult &Result) {
+  llvm::APInt ArraySize;
+  const auto *Matched = Result.Nodes.getNodeAs<Expr>("expr");
+  if (const auto *ConstArrayType = Result.Nodes.getNodeAs<ConstantArrayType>("type")) {
+    ArraySize = ConstArrayType->getSize();
+  }
+
+  if (const auto *StdArrayDecl = Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("type")) {
+    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;
+    ArraySize = SizeArg.getAsIntegral();
+  }
+
+  const auto *IndexExpr = Result.Nodes.getNodeAs<Expr>("index");
+  llvm::APSInt Index;
+  if (!IndexExpr->isIntegerConstantExpr(Index, *Result.Context, nullptr, true)) {
+    //Fixit would need gsl::at()
+    diag(Matched->getExprLoc(), "do not use array subscript when the index is not a compile-time constant; use gsl::at() instead");
+    return;
+  }
+
+  if (Index.isSigned() && Index.isNegative()) {
+    diag(Matched->getExprLoc(), "array index %0 is before the beginning of the array")
+      << Index.toString(10);
+    return;
+  }
+
+  if (Index.uge(ArraySize)) {
+    diag(Matched->getExprLoc(), "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.
+
+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

docs/clang-tidy/checks/list.rst

 List of clang-tidy Checks
 =========================
 
 .. toctree::
    cert-setlongjmp
    cert-variadic-function-def
+   cppcoreguidelines-pro-bounds-constant-array-index
    cppcoreguidelines-pro-bounds-pointer-arithmetic
    cppcoreguidelines-pro-type-const-cast
    cppcoreguidelines-pro-type-reinterpret-cast
    cppcoreguidelines-pro-type-static-cast-downcast
    google-build-explicit-make-pair
    google-build-namespaces
    google-build-using-namespace
    google-explicit-constructor

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

+// RUN: %python %S/check_clang_tidy.py %s cppcoreguidelines-pro-bounds-constant-array-index %t
+#include <array>
+
+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] = 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]
+  a[pos - 1] = 2;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: do not use array subscript when the index is not a compile-time constant; 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: 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: 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: 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
+    gsl::at(a, i) = i; // OK, gsl::at() instead of []
+  }
+
+  a[-1] = 3;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: array index -1 is before the beginning of the array
+  a[10] = 4;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: array index 10 is past the end of the array (which contains 10 elements)
+  a[const_index(7)] = 3;
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 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
+}
+
+struct S {
+  int& operator[](int i);
+};
+
+void customOperator() {
+  S s;
+  int i = 0;
+  s[i] = 3; // OK, custom operator
+}