[clang-tidy] Checker for inaccurate use of erase() method.

Algorithms like remove() does not actually remove any element from the
container but returns an iterator to the first redundant element at the end
of the container. These redundant elements must be removed using the
erase() method. This check warns when not all of the elements will be
removed due to using an inappropriate overload.

Reviewer: alexfh

Differential Revision: http://reviews.llvm.org/D7496

llvm-svn: 228679

5 files changed, 171 insertions, 0 deletions

diff --git a/clang-tools-extra/clang-tidy/misc/CMakeLists.txt b/clang-tools-extra/clang-tidy/misc/CMakeLists.txt
index b68648b629e..1f2d9960a50 100644
--- a/clang-tools-extra/clang-tidy/misc/CMakeLists.txt
+++ b/clang-tools-extra/clang-tidy/misc/CMakeLists.txt
@@ -4,6 +4,7 @@ add_clang_library(clangTidyMiscModule
   ArgumentCommentCheck.cpp
   AssignOperatorSignatureCheck.cpp
   BoolPointerImplicitConversion.cpp
+  InaccurateEraseCheck.cpp
   InefficientAlgorithmCheck.cpp
   MiscTidyModule.cpp
   SwappedArgumentsCheck.cpp
diff --git a/clang-tools-extra/clang-tidy/misc/InaccurateEraseCheck.cpp b/clang-tools-extra/clang-tidy/misc/InaccurateEraseCheck.cpp
new file mode 100644
index 00000000000..033e0a15d87
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/misc/InaccurateEraseCheck.cpp
@@ -0,0 +1,64 @@
+//===--- InaccurateEraseCheck.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 "InaccurateEraseCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Lex/Lexer.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+
+void InaccurateEraseCheck::registerMatchers(MatchFinder *Finder) {
+  const auto CheckForEndCall = hasArgument(
+      1,
+      anyOf(constructExpr(has(memberCallExpr(callee(methodDecl(hasName("end"))))
+                                  .bind("InaccEndCall"))),
+            anything()));
+
+  Finder->addMatcher(
+      memberCallExpr(
+          on(hasType(namedDecl(matchesName("std::")))),
+          callee(methodDecl(hasName("erase"))), argumentCountIs(1),
+          hasArgument(0, has(callExpr(callee(functionDecl(matchesName(
+                                          "std::(remove_if|remove|unique)"))),
+                                      CheckForEndCall).bind("InaccAlgCall"))),
+          unless(isInTemplateInstantiation())).bind("InaccErase"),
+      this);
+}
+
+void InaccurateEraseCheck::check(const MatchFinder::MatchResult &Result) {
+  const auto *MemberCall =
+      Result.Nodes.getNodeAs<CXXMemberCallExpr>("InaccErase");
+  const auto *EndExpr =
+      Result.Nodes.getNodeAs<CXXMemberCallExpr>("InaccEndCall");
+  const SourceLocation Loc = MemberCall->getLocStart();
+
+  FixItHint Hint;
+
+  if (!Loc.isMacroID() && EndExpr) {
+    const auto *AlgCall = Result.Nodes.getNodeAs<CallExpr>("InaccAlgCall");
+    std::string ReplacementText = Lexer::getSourceText(
+        CharSourceRange::getTokenRange(EndExpr->getSourceRange()),
+        *Result.SourceManager, Result.Context->getLangOpts());
+    const SourceLocation EndLoc = Lexer::getLocForEndOfToken(
+        AlgCall->getLocEnd(), 0, *Result.SourceManager,
+        Result.Context->getLangOpts());
+    Hint = FixItHint::CreateInsertion(EndLoc, ", " + ReplacementText);
+  }
+
+  diag(Loc, "this call will remove at most one item even when multiple items "
+            "should be removed")
+      << Hint;
+}
+
+} // namespace tidy
+} // namespace clang
diff --git a/clang-tools-extra/clang-tidy/misc/InaccurateEraseCheck.h b/clang-tools-extra/clang-tidy/misc/InaccurateEraseCheck.h
new file mode 100644
index 00000000000..cde7320a2be
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/misc/InaccurateEraseCheck.h
@@ -0,0 +1,36 @@
+//===--- InaccurateEraseCheck.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_INACCURATE_ERASE_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INACCURATE_ERASE_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+
+/// \brief Checks for inaccurate use of \c erase() method.
+///
+/// Algorithms like \c remove() do not actually remove any element from the
+/// container but return an iterator to the first redundant element at the end
+/// of the container. These redundant elements must be removed using the
+/// \c erase() method. This check warns when not all of the elements will be
+/// removed due to using an inappropriate overload.
+class InaccurateEraseCheck : public ClangTidyCheck {
+public:
+  InaccurateEraseCheck(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_MISC_INACCURATE_ERASE_H
diff --git a/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp b/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
index dfd5a49986b..a43efabcfd3 100644
--- a/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
+++ b/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
@@ -13,6 +13,7 @@
 #include "ArgumentCommentCheck.h"
 #include "AssignOperatorSignatureCheck.h"
 #include "BoolPointerImplicitConversion.h"
+#include "InaccurateEraseCheck.h"
 #include "InefficientAlgorithmCheck.h"
 #include "SwappedArgumentsCheck.h"
 #include "UndelegatedConstructor.h"
@@ -31,6 +32,8 @@ public:
         "misc-assign-operator-signature");
     CheckFactories.registerCheck<BoolPointerImplicitConversion>(
         "misc-bool-pointer-implicit-conversion");
+    CheckFactories.registerCheck<InaccurateEraseCheck>(
+        "misc-inaccurate-erase");
     CheckFactories.registerCheck<InefficientAlgorithmCheck>(
         "misc-inefficient-algorithm");
     CheckFactories.registerCheck<SwappedArgumentsCheck>(
diff --git a/clang-tools-extra/test/clang-tidy/misc-inaccurate-erase.cpp b/clang-tools-extra/test/clang-tidy/misc-inaccurate-erase.cpp
new file mode 100644
index 00000000000..1693b9f455c
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/misc-inaccurate-erase.cpp
@@ -0,0 +1,67 @@
+// RUN: $(dirname %s)/check_clang_tidy.sh %s misc-inaccurate-erase %t
+// REQUIRES: shell
+
+namespace std {
+struct vec_iterator {};
+
+template <typename T> struct vector {
+  typedef vec_iterator iterator;
+
+  iterator begin();
+  iterator end();
+
+  void erase(iterator);
+  void erase(iterator, iterator);
+};
+
+template <typename FwIt, typename T>
+FwIt remove(FwIt begin, FwIt end, const T &val);
+
+template <typename FwIt, typename Func>
+FwIt remove_if(FwIt begin, FwIt end, Func f);
+
+template <typename FwIt> FwIt unique(FwIt begin, FwIt end);
+} // namespace std
+
+struct custom_iter {};
+struct custom_container {
+  void erase(...);
+  custom_iter begin();
+  custom_iter end();
+};
+
+template <typename T> void g() {
+  T t;
+  t.erase(std::remove(t.begin(), t.end(), 10));
+  // CHECK-FIXES: {{^  }}t.erase(std::remove(t.begin(), t.end(), 10));{{$}}
+
+  std::vector<int> v;
+  v.erase(remove(v.begin(), v.end(), 10));
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this call will remove at most one
+  // CHECK-FIXES: {{^  }}v.erase(remove(v.begin(), v.end(), 10), v.end());{{$}}
+}
+
+#define ERASE(x, y) x.erase(remove(x.begin(), x.end(), y))
+// CHECK-FIXES: #define ERASE(x, y) x.erase(remove(x.begin(), x.end(), y))
+
+int main() {
+  std::vector<int> v;
+
+  v.erase(remove(v.begin(), v.end(), 10));
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this call will remove at most one item even when multiple items should be removed [misc-inaccurate-erase]
+  // CHECK-FIXES: {{^  }}v.erase(remove(v.begin(), v.end(), 10), v.end());{{$}}
+  v.erase(remove(v.begin(), v.end(), 20), v.end());
+
+  // Fix is not trivial.
+  auto it = v.end();
+  v.erase(remove(v.begin(), it, 10));
+  // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this call will remove at most one
+  // CHECK-FIXES: {{^  }}v.erase(remove(v.begin(), it, 10));{{$}}
+
+  g<std::vector<int>>();
+  g<custom_container>();
+
+  ERASE(v, 15);
+  // CHECK-MESSAGES: :[[@LINE-1]]:9: warning: this call will remove at most one
+  // CHECK-FIXES: {{^  }}ERASE(v, 15);{{$}}
+}