ForRangeCopyCheck that warns on and fixes unnecessary copies of loop variables.

[flx]

Summary

This change depends on http://reviews.llvm.org/D13845 which adds a new matcher that allows you match arguments and their parameter declarations together.

[alexfh]

Thank you for the patch! One of its dependencies (D13845) is not yet in, but you can in the meantime polish this patch.

clang-tidy/misc/ForRangeCopyCheck.cpp

98

How about a solution that doesn't create unnecessary temporary sets? Something similar to:

std::set<const DeclRefExpr *> Nodes = extractNodesById<...>(...);
DeclRefs.insert(Nodes.begin(), Nodes.end());
Matches = ...;
Nodes = extractNodesById...;
DeclRefs.insert(Nodes.begin(), Nodes.end());
return DeclRefs;

?

117

I'd remove the variable and use the expression itself below.

142

nit: It's not common to use braces around single-line for/if bodies in LLVM.

152

Use isa<AutoType>(...) instead of dyn_cast<...>(...) == nullptr.

155

Remove the braces around if, so it becomes else if.

190

setDifference is only used once, and only to check whether it's empty. I'd prefer to replace it with setDifferenceEmpty (feel free to choose a better name) that can be implemented without allocating a set and actually calculating set difference.

194

Diagnostic messages are not complete sentences, so they don't need periods and capitalization:

... as const reference; consider ...

[alexfh]

I think, we can arrange a better place for this check. Could you add a new module performance and put this check there?

Thanks!

clang-tidy/misc/ForRangeCopyCheck.cpp

49

nit: No braces needed here.

63

nit: No braces needed here.

96

While I appreciate your effort to bring more functional style to C++ code, this is not always optimal ;)

You only use insertAll together with extractNodesById. It looks like you could instead change the interface of the latter to accept an output parameter (void extractNodesByIdTo(const SmallVector<BoundNodes, 1> &Matches, StringRef ID, set<const Node *> &Nodes)). The result would be fewer allocations of temporary sets.

137

s/VarDecl/auto/ for consistency with the line below.

150

nit: If the first if has braces, it's else/else if branch should use braces too.

156

Please change the punctuation here: "... not a reference type; this ...".

[flx]

I'm planning to first submit both http://reviews.llvm.org/D13845 (new argument/param matcher required for this patch) and http://reviews.llvm.org/D15623 (unnecessary copy initialization which introduces the "performance" module).

Then I can update this patch and move the check over to the performance module as well.

[flx]

I moved the ForRangeCopyCheck into the performance module and removed the getPreviousNonCommentToken() function in favor of calling lexer_utils::getPreviousNonCommentToken().

[flx]

I updated this patch to also look at the first argument (the implicit object argument) of const method CxxOperatorCallExprs and added tests to ensure that const member operator invocations as well as non-const member operator invocations are correctly detected.

[flx]

Updated patch against latest head now that the forEachArgumentWithParam matcher is in this patch is not blocked on any external dependencies.

Latest change: I made the LoopVar matcher in registerMatchers() more narrow by not allowing the loop var to be initialized by a MaterializeTemporaryExpr which means that a conversion has already taken place and a const& would not make the loop more performant.

I also added test cases with implicit constructor conversion and user-defined conversion operator to test for this.

[flx]

One more update: Disable the check inside of macros since we cannot place the fixes correctly.

[flx]

Added test to ensure typedef typename T::const_reference does not trigger false positives.

[flx]

The test for const reference typedefs was not complete since the loop variable was not accessed in a const manner in the loop. After I changed that the LoopVar matcher had to be adapted to use hasCanonicalType instead of qualType().

[alexfh]

Thank you for the update and sorry for the long delay. Mostly looks good, but you should add user-facing documentation. See docs/clang-tidy/checks/misc-unused-raii.rst for a good example.

clang-tidy/performance/ForRangeCopyCheck.h

20 ↗

(On Diff #45521)

Please add a link to the user-facing documentation. In general, we should use the template suggested by add_new_check.py:

/// A short description of the check.
///
/// For the user-facing documentation see:
/// http://clang.llvm.org/extra/clang-tidy/checks/<check-name>.htm

32 ↗

(On Diff #45521)

nit: I'd insert a linebreak before the comment.

[alexfh]

Looks good modulo comments (documentation can be added as a follow-up).

Thank you for this awesome check!

clang-tidy/performance/ForRangeCopyCheck.cpp

34 ↗

(On Diff #45521)

An ArrayRef<BoundNodes> should be used here instead. Sorry for missing this initially and giving you a sub-optimal suggestion.

35 ↗

(On Diff #45521)

A SmallPtrSet<const Node*, ...> might be a better choice here depending on the usual number of nodes in the set. Anyway, this can wait until this shows up in a profile.

[alexfh]

docs/clang-tidy/checks/performance-for-range-copy.rst

3 ↗

(On Diff #45769)

This needs to be updated.

clang-tidy/misc/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyMiscModule
   ArgumentCommentCheck.cpp
   AssertSideEffectCheck.cpp
   AssignOperatorSignatureCheck.cpp
   BoolPointerImplicitConversionCheck.cpp
+  ForRangeCopyCheck.cpp
   InaccurateEraseCheck.cpp
   InefficientAlgorithmCheck.cpp
   MacroParenthesesCheck.cpp
   MacroRepeatedSideEffectsCheck.cpp
   MiscTidyModule.cpp
   MoveConstantArgumentCheck.cpp 
   MoveConstructorInitCheck.cpp
   NewDeleteOverloadsCheck.cpp

clang-tidy/misc/ForRangeCopyCheck.h

+//===--- ForRangeCopyCheck.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_MISC_FORRANGECOPYCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_FORRANGECOPYCHECK_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+
+// A check that detects copied loop variables and suggests using const
+// references.
+class ForRangeCopyCheck : public ClangTidyCheck {
+public:
+  ForRangeCopyCheck(StringRef Name, ClangTidyContext *Context);
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  // Checks if the loop variable is a const value and expensive to copy. If so
+  // suggests it be converted to a const reference.
+  bool handleConstValueCopy(const VarDecl &LoopVar, ASTContext &Context);
+  // Checks if the loop variable is a non-const value and whether only
+  // const methods are invoked on it or whether it is only used as a const
+  // reference argument. If so it suggests it be made a const reference.
+  bool handleCopyIsOnlyConstReferenced(const VarDecl &LoopVar,
+                                       const CXXForRangeStmt &ForRange,
+                                       ASTContext &Context);
+
+  const bool WarnOnAllAutoCopies;
+};
+
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_FORRANGECOPYCHECK_H

clang-tidy/misc/ForRangeCopyCheck.cpp

+//===--- ForRangeCopyCheck.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 "ForRangeCopyCheck.h"
+#include "../utils/TypeTraits.h"
+#include "clang/Lex/Lexer.h"
+
+#include <set>
+
+namespace clang {
+namespace tidy {
+
+using namespace ::clang::ast_matchers;
+
+namespace {
+
+Token getPreviousNonCommentToken(const ASTContext &Context,
+                                 SourceLocation Location) {
+  const auto &SourceManager = Context.getSourceManager();
+  Token Token;
+  Token.setKind(tok::unknown);
+  Location = Location.getLocWithOffset(-1);
+  auto StartOfFile =
+      SourceManager.getLocForStartOfFile(SourceManager.getFileID(Location));
+  while (Location != StartOfFile) {
+    Location = Lexer::GetBeginningOfToken(Location, SourceManager,
+                                          Context.getLangOpts());
+    if (!Lexer::getRawToken(Location, Token, SourceManager,
+                            Context.getLangOpts()) &&
+        !Token.is(tok::comment)) {
+      break;
+    }
+    Location = Location.getLocWithOffset(-1);
+  }
+  return Token;
+}
+
+template <typename S> void insertAll(const S &S1, S &S2) {
+  S2.insert(S1.begin(), S1.end());
+}
+
+template <typename S> bool isSetDifferenceEmpty(const S &S1, const S &S2) {
+  for (const auto &E : S1) {
+    if (S2.find(E) == S2.end()) {
+      return false;
+    }
+  }
+  return true;
+}
+
+// Extracts all Nodes keyed by ID from Matches and returns them as
+// set for comparison.
+template <typename Node>
+std::set<const Node *>
+extractNodesById(const SmallVector<BoundNodes, 1> &Matches, StringRef ID) {
+  std::set<const Node *> Nodes;
+  for (const auto &Match : Matches) {
+    Nodes.insert(Match.getNodeAs<Node>(ID));
+  }
+  return Nodes;
+}
+
+// Finds all DeclRefExprs to VarDecl in Stmt.
+std::set<const DeclRefExpr *>
+declRefExprs(const VarDecl &VarDecl, const Stmt &Stmt, ASTContext &Context) {
+  auto Matches = match(
+      findAll(declRefExpr(to(varDecl(equalsNode(&VarDecl)))).bind("declRef")),
+      Stmt, Context);
+  return extractNodesById<DeclRefExpr>(Matches, "declRef");
+}
+
+// Finds all DeclRefExprs where a const method is called on VarDecl or VarDecl
+// is the a const reference or value argument to a CallExpr or CXXConstructExpr.
+std::set<const DeclRefExpr *> constReferenceDeclRefExprs(const VarDecl &VarDecl,
+                                                         const Stmt &Stmt,
+                                                         ASTContext &Context) {
+  auto Matches = match(
+      findAll(cxxMemberCallExpr(
+          callee(cxxMethodDecl(isConst())),
+          on(declRefExpr(to(varDecl(equalsNode(&VarDecl)))).bind("declRef")))),
+      Stmt, Context);
+  auto DeclRefs = extractNodesById<DeclRefExpr>(Matches, "declRef");
+  auto ConstReferenceOrValue =
+      qualType(anyOf(referenceType(pointee(qualType(isConstQualified()))),
+                     unless(anyOf(referenceType(), pointerType()))));
+  auto UsedAsConstRefOrValueArg = forEachArgumentWithParam(
+      declRefExpr(to(varDecl(equalsNode(&VarDecl)))).bind("declRef"),
+      parmVarDecl(hasType(ConstReferenceOrValue)));
+  Matches = match(findAll(callExpr(UsedAsConstRefOrValueArg)), Stmt, Context);
+  insertAll(extractNodesById<DeclRefExpr>(Matches, "declRef"), DeclRefs);
+  Matches =
+      match(findAll(cxxConstructExpr(UsedAsConstRefOrValueArg)), Stmt, Context);
+  insertAll(extractNodesById<DeclRefExpr>(Matches, "declRef"), DeclRefs);
+  return DeclRefs;
+}
+
+// Modifies VarDecl to be a reference.
+FixItHint createAmpersandFix(const VarDecl &VarDecl, ASTContext &Context) {
+  SourceLocation AmpLocation = VarDecl.getLocation();
+  auto Token = getPreviousNonCommentToken(Context, AmpLocation);
+  if (!Token.is(tok::unknown)) {
+    AmpLocation = Token.getLocation().getLocWithOffset(Token.getLength());
+  }
+  return FixItHint::CreateInsertion(AmpLocation, "&");
+}
+
+// Modifies VarDecl to be const.
+FixItHint createConstFix(const VarDecl &VarDecl) {
+  return FixItHint::CreateInsertion(VarDecl.getTypeSpecStartLoc(), "const ");
+}
+
+} // namespace
+
+ForRangeCopyCheck::ForRangeCopyCheck(StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      WarnOnAllAutoCopies(Options.get("WarnOnAllAutoCopies", 0)) {}
+
+void ForRangeCopyCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "WarnOnAllAutoCopies", WarnOnAllAutoCopies);
+}
+
+void ForRangeCopyCheck::registerMatchers(MatchFinder *Finder) {
+  auto LoopVar =
+      varDecl(hasType(qualType(unless(anyOf(referenceType(), pointerType())))));
+  Finder->addMatcher(cxxForRangeStmt(hasLoopVariable(LoopVar.bind("loopVar")))
+                         .bind("forRange"),
+                     this);
+}
+
+void ForRangeCopyCheck::check(const MatchFinder::MatchResult &Result) {
+  const VarDecl *Var = Result.Nodes.getNodeAs<VarDecl>("loopVar");
+  const auto *ForRange = Result.Nodes.getNodeAs<CXXForRangeStmt>("forRange");
+  if (handleConstValueCopy(*Var, *Result.Context))
+    return;
+  handleCopyIsOnlyConstReferenced(*Var, *ForRange, *Result.Context);
+}
+
+bool ForRangeCopyCheck::handleConstValueCopy(const VarDecl &LoopVar,
+                                             ASTContext &Context) {
+  if (WarnOnAllAutoCopies) {
+    // For aggressive check just test that loop variable has auto type.
+    if (!isa<AutoType>(LoopVar.getType()))
+      return false;
+  } else if (!LoopVar.getType().isConstQualified())
+    return false;
+  if (!type_traits::isExpensiveToCopy(LoopVar.getType(), Context))
+    return false;
+  auto Diagnostic =
+      diag(LoopVar.getLocation(),
+           "the loop variable's type is not a reference type. This creates a "
+           "copy in each iteration; consider making this a reference")
+      << createAmpersandFix(LoopVar, Context);
+  if (!LoopVar.getType().isConstQualified())
+    Diagnostic << createConstFix(LoopVar);
+  return true;
+}
+
+bool ForRangeCopyCheck::handleCopyIsOnlyConstReferenced(
+    const VarDecl &LoopVar, const CXXForRangeStmt &ForRange,
+    ASTContext &Context) {
+  if (LoopVar.getType().isConstQualified() ||
+      !type_traits::isExpensiveToCopy(LoopVar.getType(), Context)) {
+    return false;
+  }
+  // Collect all DeclRefExprs to the loop variable and all CallExprs and
+  // CXXConstructExprs where the loop variable is used as argument to a const
+  // reference parameter.
+  // If the difference is empty it is safe for the loop variable to be a const
+  // reference.
+  auto AllDeclRefs = declRefExprs(LoopVar, *ForRange.getBody(), Context);
+  auto ConstReferenceDeclRefs =
+      constReferenceDeclRefExprs(LoopVar, *ForRange.getBody(), Context);
+  if (AllDeclRefs.empty() ||
+      !isSetDifferenceEmpty(AllDeclRefs, ConstReferenceDeclRefs))
+    return false;
+  diag(LoopVar.getLocation(),
+       "loop variable is copied but only used as const reference; consider "
+       "making it a const reference")
+      << createConstFix(LoopVar) << createAmpersandFix(LoopVar, Context);
+  return true;
+}
+
+} // namespace tidy
+} // namespace clang

clang-tidy/misc/MiscTidyModule.cpp

 //===--- MiscTidyModule.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 "ArgumentCommentCheck.h"
 #include "AssertSideEffectCheck.h"
 #include "AssignOperatorSignatureCheck.h"
 #include "BoolPointerImplicitConversionCheck.h"
+#include "ForRangeCopyCheck.h"
 #include "InaccurateEraseCheck.h"
 #include "InefficientAlgorithmCheck.h"
 #include "MacroParenthesesCheck.h"
 #include "MacroRepeatedSideEffectsCheck.h"
 #include "MoveConstantArgumentCheck.h"
 #include "MoveConstructorInitCheck.h"
 #include "NewDeleteOverloadsCheck.h"
 #include "NoexceptMoveConstructorCheck.h"
public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ArgumentCommentCheck>("misc-argument-comment");
     CheckFactories.registerCheck<AssertSideEffectCheck>(
         "misc-assert-side-effect");
     CheckFactories.registerCheck<AssignOperatorSignatureCheck>(
         "misc-assign-operator-signature");
     CheckFactories.registerCheck<BoolPointerImplicitConversionCheck>(
         "misc-bool-pointer-implicit-conversion");
+    CheckFactories.registerCheck<ForRangeCopyCheck>("misc-for-range-copy");
     CheckFactories.registerCheck<InaccurateEraseCheck>(
         "misc-inaccurate-erase");
     CheckFactories.registerCheck<InefficientAlgorithmCheck>(
         "misc-inefficient-algorithm");
     CheckFactories.registerCheck<MacroParenthesesCheck>(
         "misc-macro-parentheses");
     CheckFactories.registerCheck<MacroRepeatedSideEffectsCheck>(
         "misc-macro-repeated-side-effects");

test/clang-tidy/misc-for-range-copy-warn-on-all-auto-copies.cpp

+// RUN: %python %S/check_clang_tidy.py %s misc-for-range-copy %t -config="{CheckOptions: [{key: "misc-for-range-copy.WarnOnAllAutoCopies", value: 1}]}" -- -std=c++11
+
+template <typename T>
+struct Iterator {
+  void operator++() {}
+  T operator*() { return T(); }
+  bool operator!=(const Iterator &) { return false; }
+};
+template <typename T>
+struct View {
+  T begin() { return T(); }
+  T begin() const { return T(); }
+  T end() { return T(); }
+  T end() const { return T(); }
+};
+
+struct S {
+  S();
+  S(const S &);
+  ~S();
+  S &operator=(const S &);
+};
+
+void NegativeLoopVariableNotAuto() {
+  for (S S1 : View<Iterator<S>>()) {
+    S* S2 = &S1;
+  }
+}
+
+void PositiveTriggeredForAutoLoopVariable() {
+  for (auto S1 : View<Iterator<S>>()) {
+    // CHECK-MESSAGES: [[@LINE-1]]:13: warning: the loop variable's type is not a reference type. This creates a copy in each iteration. Consider making this a reference [misc-for-range-copy]
+    // CHECK-FIXES: for (const auto& S1 : View<Iterator<S>>()) {
+    S* S2 = &S1;
+  }
+}

test/clang-tidy/misc-for-range-copy.cpp

+// RUN: %python %S/check_clang_tidy.py %s misc-for-range-copy %t
+
+namespace std {
+
+template <typename _Tp>
+struct remove_reference { typedef _Tp type; };
+
+template <typename _Tp>
+constexpr typename std::remove_reference<_Tp>::type &&move(_Tp &&__t) {
+  return static_cast<typename std::remove_reference<_Tp>::type &&>(__t);
+}
+
+} // std
+
+template <typename T>
+struct Iterator {
+  void operator++() {}
+  T operator*() { return T(); }
+  bool operator!=(const Iterator &) { return false; }
+};
+template <typename T>
+struct View {
+  T begin() { return T(); }
+  T begin() const { return T(); }
+  T end() { return T(); }
+  T end() const { return T(); }
+};
+
+struct S {
+  S();
+  S(const S &);
+  ~S();
+  S &operator=(const S &);
+};
+
+void NegativeConstReference() {
+  for (const S &S1 : View<Iterator<S>>()) {
+  }
+}
+
+template <typename T>
+void uninstantiated() {
+  for (const S S1 : View<Iterator<S>>()) {}
+  // CHECK-MESSAGES: [[@LINE-1]]:16: warning: the loop variable's type is not a reference type. This creates a copy in each iteration; consider making this a reference [misc-for-range-copy]
+  // CHECK-FIXES: {{^}}  for (const S& S1 : View<Iterator<S>>()) {}
+
+  // Don't warn on dependent types.
+  for (const T t1 : View<Iterator<T>>()) {
+  }
+}
+
+template <typename T>
+void instantiated() {
+  for (const S S2 : View<Iterator<S>>()) {}
+  // CHECK-MESSAGES: [[@LINE-1]]:16: warning: the loop variable's type is {{.*}}
+  // CHECK-FIXES: {{^}}  for (const S& S2 : View<Iterator<S>>()) {}
+
+  for (const T T2 : View<Iterator<T>>()) {}
+  // CHECK-MESSAGES: [[@LINE-1]]:16: warning: the loop variable's type is {{.*}}
+  // CHECK-FIXES: {{^}}  for (const T& T2 : View<Iterator<T>>()) {}
+}
+
+void f() {
+  instantiated<int>();
+  instantiated<S>();
+}
+
+struct Mutable {
+  Mutable() {}
+  Mutable(const Mutable &) = default;
+  Mutable(const Mutable &, const Mutable &) {}
+  void setBool(bool B) {}
+  bool constMethod() const {
+    return true;
+  }
+  ~Mutable() {}
+};
+
+void use(const Mutable &M);
+void useTwice(const Mutable &M1, const Mutable &M2);
+void useByValue(Mutable M);
+void useByConstValue(const Mutable M);
+void mutate(Mutable *M);
+void mutate(Mutable &M);
+void onceConstOnceMutated(const Mutable &M1, Mutable &M2);
+
+void negativeVariableIsMutated() {
+  for (auto M : View<Iterator<Mutable>>()) {
+    mutate(M);
+  }
+  for (auto M : View<Iterator<Mutable>>()) {
+    mutate(&M);
+  }
+  for (auto M : View<Iterator<Mutable>>()) {
+    M.setBool(true);
+  }
+}
+
+void negativeOnceConstOnceMutated() {
+  for (auto M : View<Iterator<Mutable>>()) {
+    onceConstOnceMutated(M, M);
+  }
+}
+
+void negativeVarIsMoved() {
+  for (auto M : View<Iterator<Mutable>>()) {
+    auto Moved = std::move(M);
+  }
+}
+
+void positiveOnlyConstMethodInvoked() {
+  for (auto M : View<Iterator<Mutable>>()) {
+    // CHECK-MESSAGES: [[@LINE-1]]:13: warning: loop variable is copied but only used as const reference; consider making it a const reference [misc-for-range-copy]
+    // CHECK-FIXES: for (const auto& M : View<Iterator<Mutable>>()) {
+    M.constMethod();
+  }
+}
+
+void positiveOnlyUsedAsConstArguments() {
+  for (auto UsedAsConst : View<Iterator<Mutable>>()) {
+    // CHECK-MESSAGES: [[@LINE-1]]:13: warning: loop variable is copied but only used as const reference; consider making it a const reference [misc-for-range-copy]
+    // CHECK-FIXES: for (const auto& UsedAsConst : View<Iterator<Mutable>>()) {
+    use(UsedAsConst);
+    useTwice(UsedAsConst, UsedAsConst);
+    useByValue(UsedAsConst);
+    useByConstValue(UsedAsConst);
+  }
+}
+
+void positiveOnlyUsedInCopyConstructor() {
+  for (auto A : View<Iterator<Mutable>>()) {
+    // CHECK-MESSAGES: [[@LINE-1]]:13: warning: loop variable is copied but only used as const reference; consider making it a const reference [misc-for-range-copy]
+    // CHECK-FIXES: for (const auto& A : View<Iterator<Mutable>>()) {
+    Mutable Copy = A;
+    Mutable Copy2(A);
+  }
+}
+
+void positiveTwoConstConstructorArgs() {
+  for (auto A : View<Iterator<Mutable>>()) {
+    // CHECK-MESSAGES: [[@LINE-1]]:13: warning: loop variable is copied but only used as const reference; consider making it a const reference [misc-for-range-copy]
+    // CHECK-FIXES: for (const auto& A : View<Iterator<Mutable>>()) {
+    Mutable Copy(A, A);
+  }
+}