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

[xazax.hun]

Summary

Checks for inaccurate use of \c erase() method.

Algorithms like \c 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
\c erase() method. This check warns when not all of the elements will be
removed due to using an inappropriate overload.

[xazax.hun]

clang-tidy/misc/InaccurateEraseCheck.cpp

25 ↗

(On Diff #19566)

It seems to work for, but I have some concerns. Is it guaranteed to work? Is there some kind of guaranteed matching/evaluating order or matcher priority? What is the idiomatic way to optionally match a construct?

[alexfh]

Looks good!

Thanks for the contribution! Could you run this on LLVM? I don't expect the check to find anything, but it may be useful as a smoke-testing.

A couple of typos in the comment. See below.

clang-tidy/misc/InaccurateEraseCheck.cpp

25 ↗

(On Diff #19566)

The order of evaluation is right-to-left, and anyOf is short-circuiting, so the construct is guaranteed to work. There was an idea to add an "optionally" matcher for this purpose, but nobody got around to do it yet.

clang-tidy/misc/InaccurateEraseCheck.h

20 ↗

(On Diff #19566)

nit: s/does not/do not/

21 ↗

(On Diff #19566)

nit: s/returns/return/

[xazax.hun]

Thank you. I have fixed the issues in the comment and commited in r228679.

[alexfh]

clang-tools-extra/trunk/clang-tidy/misc/InaccurateEraseCheck.cpp

27

Interestingly, the matcher also matches this code:

$ cat test.cc
#include <map>
#include <memory>

void f() {
  std::map<int, std::unique_ptr<int>> m;
  auto iter = m.begin();
  m.erase(iter++);
}

$ clang-tidy test.cc -- -std=c++11
...
test.cc:7:3: warning: this call will remove at most one item even when multiple items should be removed [misc-inaccurate-erase]
  m.erase(iter++);
  ^
...

I suspect that getQualifiedNameAsString() for std::unique_ptr<>::operator++ is matched by the "std::unique" part of the regexp. One possible solution is to enclose the regexp in ^$.

[xazax.hun]

Thank you for finding this issue. The original checker before port used hasName and anyOf. It looks like I should be more cautious when replacing such constructs with regexps. It should be fixed in r230483.

The issue was: the iterator has a template parameter that is substituted for the type that is stored inside the container. The postfix ++ operator has one parameter.

clang-tools-extra/trunk/clang-tidy/misc/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyMiscModule
   ArgumentCommentCheck.cpp
   AssignOperatorSignatureCheck.cpp
   BoolPointerImplicitConversion.cpp
+  InaccurateEraseCheck.cpp
   InefficientAlgorithmCheck.cpp
   MiscTidyModule.cpp
   SwappedArgumentsCheck.cpp
   UndelegatedConstructor.cpp
   UnusedRAII.cpp
   UniqueptrResetRelease.cpp
   UseOverride.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangLex
   clangTidy
   )

clang-tools-extra/trunk/clang-tidy/misc/InaccurateEraseCheck.h

+//===--- 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

clang-tools-extra/trunk/clang-tidy/misc/InaccurateEraseCheck.cpp

+//===--- 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

clang-tools-extra/trunk/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 "AssignOperatorSignatureCheck.h"
 #include "BoolPointerImplicitConversion.h"
+#include "InaccurateEraseCheck.h"
 #include "InefficientAlgorithmCheck.h"
 #include "SwappedArgumentsCheck.h"
 #include "UndelegatedConstructor.h"
 #include "UniqueptrResetRelease.h"
 #include "UnusedRAII.h"
 #include "UseOverride.h"
 
 namespace clang {
 namespace tidy {
 
 class MiscModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ArgumentCommentCheck>("misc-argument-comment");
     CheckFactories.registerCheck<AssignOperatorSignatureCheck>(
         "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>(
         "misc-swapped-arguments");
     CheckFactories.registerCheck<UndelegatedConstructorCheck>(
         "misc-undelegated-constructor");
     CheckFactories.registerCheck<UniqueptrResetRelease>(
         "misc-uniqueptr-reset-release");

clang-tools-extra/trunk/test/clang-tidy/misc-inaccurate-erase.cpp

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