[clang-tidy] Add misc-for-loop-iterator-invalidation check.

[staronj]

Summary

This is the first version of a check looking for operator or method calls in C++11 for loop on iterated object that may lead to iterator invalidation and therefore to undefined behavior.

In general, it's hard to tell if call may lead to iterator invalidation. Check proposes heuristics and white-list to solve this problem. For heuristics description see ForLoopIteratorInvalidationCheck.cpp:104.

[Eugene.Zelenko]

I think this check belongs to Static Analyzer.

[Prazek]

In D32222#730454, @Eugene.Zelenko wrote:

I think this check belongs to Static Analyzer.

Why do you think so? We don't need path sensitive analysis to do it.
We just check if there is any instruction inside the for loop that looks like changing the container. It seems that the heuristic
is very good and for example it found code that was doing extra lookup in unorderd map

[mgehre]

Did you run this check over the llvm/clang code base?

clang-tidy/misc/ForLoopIteratorInvalidationCheck.cpp

55

nit: given
and maybe call the function HasEquivalentConstSubstitute?

[mgehre]

test/clang-tidy/misc-for-loop-iterator-invalidation.cpp

111

why should this be OK?

133

Why is this not triggering the diagnostic?

[Prazek]

clang-tidy/misc/ForLoopIteratorInvalidationCheck.cpp

36

function names start with lowerCase

72

This option has to be documented

test/clang-tidy/misc-for-loop-iterator-invalidation.cpp

111

because we exit the loop after invalidation with break.

133

lists are not ivalidated and we have seen cases in LLVM where we did loop on the list and add new things to it. This is default option to prevent false positives, but it can be changed.

[Prazek]

docs/clang-tidy/checks/misc-for-loop-iterator-invalidation.rst

17

The docs should also contain the info about

• the heuristic
• handling of loop exits

[Prazek]

clang-tidy/misc/ForLoopIteratorInvalidationCheck.cpp

80

What about pointers type? It is probably uncommon, but the fix should be easy.

[staronj]

Renames helper functions to start with lowercase.
HaveEqivalent... -> hasEquivalent....
Adds heuristic and option description to documentation.
Adds note about breaking from loop to documentation.

clang-tidy/misc/ForLoopIteratorInvalidationCheck.cpp

80

The case with pointer types is not so obvious. Look at following example:
std::vector<int> vec1, vec2;
...
auto p = &vec1;
for (auto x: *p) {

p = &vec2;
p -> push_back(x); // Completely valid call.

}

We can't assume that pointer will not change, so we can't assume that pointer is still pointing to iterated container.

[Prazek]

clang-tidy/misc/ForLoopIteratorInvalidationCheck.cpp

80

ok good point, it would require much more effort

clang-tidy/misc/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyMiscModule
   ArgumentCommentCheck.cpp
   AssertSideEffectCheck.cpp
+  ForLoopIteratorInvalidationCheck.cpp
   ForwardingReferenceOverloadCheck.cpp
   MisplacedConstCheck.cpp
   UnconventionalAssignOperatorCheck.cpp
   BoolPointerImplicitConversionCheck.cpp
   DanglingHandleCheck.cpp
   DefinitionsInHeadersCheck.cpp
   FoldInitTypeCheck.cpp
   ForwardDeclarationNamespaceCheck.cpp

clang-tidy/misc/ForLoopIteratorInvalidationCheck.h

+//===--- ForLoopIteratorInvalidationCheck.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_FOR_LOOP_ITERATOR_INVALIDATION_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_FOR_LOOP_ITERATOR_INVALIDATION_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+/// Finds suspicious method calls on objects iterated using
+/// C++11 for-range loop. If such call can invalidate iterators then
+/// behaviour is undefined.
+/// Example:
+/// \code
+///   std::vector<int> v = {1, 2, 3};
+///   for (auto i : v) {
+///     v.push_back(0); // Boom!
+///   }
+/// \endcode
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/misc-for-loop-iterator-invalidation.html
+class ForLoopIteratorInvalidationCheck : public ClangTidyCheck {
+public:
+  ForLoopIteratorInvalidationCheck(StringRef Name, ClangTidyContext *Context);
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  std::vector<std::string> SafeTypes;
+};
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_FOR_LOOP_ITERATOR_INVALIDATION_H

clang-tidy/misc/ForLoopIteratorInvalidationCheck.cpp

+//===--- ForLoopIteratorInvalidationCheck.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 "ForLoopIteratorInvalidationCheck.h"
+#include "../utils/ExprSequence.h"
+#include "../utils/OptionsUtils.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/Analyses/ReachableCode.h"
+#include "clang/Analysis/CFG.h"
+
+using namespace clang::ast_matchers;
+using namespace clang::tidy::utils;
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+namespace {
+
+const char CalledObject[] = "calledObject";
+const char MethodDeclaration[] = "methodDeclaration";
+const char MethodCall[] = "methodCall";
+const char ForStatement[] = "forRange";
+const char FunctionDeclaration[] = "functionDecl";
+const char DefaultSafeTypes[] = "::std::list; ::std::forward_list";
+
+/// \brief Checks if two methods (or overloaded operators) methods of the same
+/// class and have the same names.
+bool haveEqualNames(const CXXMethodDecl *First, const CXXMethodDecl *Second) {
+  return First->getQualifiedNameAsString() ==
+         Second->getQualifiedNameAsString();
+}
+
+/// \brief Checks if two functions have same parameter lists with regard to
+/// types.
+bool haveSameParameters(const CXXMethodDecl *First,
+                        const CXXMethodDecl *Second) {
+  if (First->param_size() != Second->param_size())
+    return false;
+
+  for (size_t i = 0; i < First->param_size(); i++)
+    if (First->parameters()[i]->getType() != Second->parameters()[i]->getType())
+      return false;
+
+  return true;
+};
+
+/// \brief Checks if class of given non-const method have method with the same
+/// name and parameters but const.
+bool hasEquivalentConstSubstitute(const CXXMethodDecl *Method) {
+  const auto *Class = Method->getParent();
+  for (const auto *M : Class->methods()) {
+    if (M != Method && M->isConst() && haveEqualNames(Method, M) &&
+        haveSameParameters(Method, M))
+      return true;
+  }
+  return false;
+};
+
+} // namespace
+
+ForLoopIteratorInvalidationCheck::ForLoopIteratorInvalidationCheck(
+    StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      SafeTypes(utils::options::parseStringList(
+          Options.get("SafeTypes", DefaultSafeTypes))) {}
+
+void ForLoopIteratorInvalidationCheck::registerMatchers(MatchFinder *Finder) {
+  auto SafeTypesMatcher = hasDeclaration(namedDecl(unless(hasAnyName(
+      SmallVector<StringRef, 5>(SafeTypes.begin(), SafeTypes.end())))));
+  auto CalledObjectRef = declRefExpr(to(
+      varDecl(hasType(qualType(anyOf(
+                  SafeTypesMatcher, referenceType(pointee(SafeTypesMatcher))))))
+          .bind(CalledObject)));
+  auto MethodMatcher = cxxMethodDecl(unless(isConst())).bind(MethodDeclaration);
+
+  Finder->addMatcher(
+      callExpr(
+          anyOf(cxxMemberCallExpr(on(CalledObjectRef)),
+                cxxOperatorCallExpr(hasArgument(0, CalledObjectRef))),
+          callee(MethodMatcher),
+          hasAncestor(cxxForRangeStmt(hasRangeInit(declRefExpr(to(varDecl(
+                                          equalsBoundNode(CalledObject))))))
+                          .bind(ForStatement)),
+          hasAncestor(functionDecl().bind(FunctionDeclaration)))
+          .bind(MethodCall),
+      this);
+}
+
+void ForLoopIteratorInvalidationCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  const auto *MatchedExpression = Result.Nodes.getNodeAs<CallExpr>(MethodCall);
+  const auto *MatchedForStatement =
+      Result.Nodes.getNodeAs<CXXForRangeStmt>(ForStatement);
+  const auto *MethodDecl =
+      Result.Nodes.getNodeAs<CXXMethodDecl>(MethodDeclaration);
+
+  // In general, it's hard to tell if method call will invalidate container
+  // iterators because it's implementation dependent. Listing all unsafe pairs
+  // (container, method) is exhausting task and do not generalize good to
+  // user-defined containers. Listing all unsafe containers would be better
+  // but would lead to more false positives - std::vector has both safe and
+  // unsafe methods.
+  // To solve this problem we apply following heuristics:
+  // We say that function is likely to invalidate iterators if this function
+  // is not const and container doesn't have function with the same name, same
+  // parameters (except 'this' parameter) but marked as const.
+  // Together with configurable SafeTypes list this check has reasonable number
+  // of false positives and automatically generalizes to user-defined
+  // containers.
+  if (hasEquivalentConstSubstitute(MethodDecl))
+    return;
+
+  CFG::BuildOptions Options;
+
+  // buildCFG takes Stmt* instead of const Stmt* so we need to const_cast
+  // TODO remove this cast and pass MatchedForStatement to buildCFG instead when
+  // buildCFG will be taking const Stmt*.
+  auto *ForStmt = const_cast<CXXForRangeStmt *>(MatchedForStatement);
+
+  // Construct a CFG and ExprSequence to find possible sequences of operations.
+  const std::unique_ptr<CFG> TheCFG =
+      CFG::buildCFG(nullptr, ForStmt, Result.Context, Options);
+  StmtToBlockMap BlockMap(TheCFG.get(), Result.Context);
+
+  auto *CallCFGBlock = BlockMap.blockContainingStmt(MatchedExpression);
+  auto *ForIncCFGBlock =
+      BlockMap.blockContainingStmt(MatchedForStatement->getInc());
+
+  llvm::BitVector Reachable(TheCFG->getNumBlockIDs());
+  reachable_code::ScanReachableFromBlock(CallCFGBlock, Reachable);
+
+  if (Reachable[ForIncCFGBlock->getBlockID()]) {
+    diag(MatchedExpression->getLocStart(),
+         "this call may lead to iterator invalidation");
+  }
+}
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang

clang-tidy/misc/MiscTidyModule.cpp

 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "ArgumentCommentCheck.h"
 #include "AssertSideEffectCheck.h"
 #include "BoolPointerImplicitConversionCheck.h"
 #include "DanglingHandleCheck.h"
 #include "DefinitionsInHeadersCheck.h"
 #include "FoldInitTypeCheck.h"
+#include "ForLoopIteratorInvalidationCheck.h"
 #include "ForwardDeclarationNamespaceCheck.h"
 #include "ForwardingReferenceOverloadCheck.h"
 #include "InaccurateEraseCheck.h"
 #include "IncorrectRoundings.h"
 #include "InefficientAlgorithmCheck.h"
 #include "MacroParenthesesCheck.h"
 #include "MacroRepeatedSideEffectsCheck.h"
 #include "MisplacedConstCheck.h"

 namespace misc {
 
 class MiscModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<ArgumentCommentCheck>("misc-argument-comment");
     CheckFactories.registerCheck<AssertSideEffectCheck>(
         "misc-assert-side-effect");
+    CheckFactories.registerCheck<ForLoopIteratorInvalidationCheck>(
+        "misc-for-loop-iterator-invalidation");
     CheckFactories.registerCheck<ForwardingReferenceOverloadCheck>(
         "misc-forwarding-reference-overload");
     CheckFactories.registerCheck<MisplacedConstCheck>("misc-misplaced-const");
     CheckFactories.registerCheck<UnconventionalAssignOperatorCheck>(
         "misc-unconventional-assign-operator");
     CheckFactories.registerCheck<BoolPointerImplicitConversionCheck>(
         "misc-bool-pointer-implicit-conversion");
     CheckFactories.registerCheck<DanglingHandleCheck>("misc-dangling-handle");

docs/ReleaseNotes.rst

- New `hicpp` module
   Adds checks that implement the `High Integrity C++ Coding Standard <http://www.codingstandard.com/section/index/>`_ and other safety
   standards. Many checks are aliased to other modules.
 
 - New `modernize-return-braced-init-list
   <http://clang.llvm.org/extra/clang-tidy/checks/modernize-return-braced-init-list.html>`_ check
 
   Finds and replaces explicit calls to the constructor in a return statement by
   a braced initializer list so that the return type is not needlessly repeated.
-  
+- New `misc-for-loop-iterator-invalidation
+  <http://clang.llvm.org/extra/clang-tidy/checks/misc-for-loop-iterator-invalidation.html>`_ check
+
+  Finds suspicious method calls on objects iterated using C++11 for-range loop.
+  If such call can invalidate iterators then behaviour is undefined.
+
 - New `misc-forwarding-reference-overload
   <http://clang.llvm.org/extra/clang-tidy/checks/misc-forwarding-reference-overload.html>`_ check
 
   Finds perfect forwarding constructors that can unintentionally hide copy or move constructors.
 
 - Support clang-formatting of the code around applied fixes (``-format-style``
   command-line option).
 

docs/clang-tidy/checks/list.rst

.. toctree::
    llvm-namespace-comment
    llvm-twine-local
    misc-argument-comment
    misc-assert-side-effect
    misc-bool-pointer-implicit-conversion
    misc-dangling-handle
    misc-definitions-in-headers
    misc-fold-init-type
+   misc-for-loop-iterator-invalidation
    misc-forward-declaration-namespace
    misc-forwarding-reference-overload
    misc-inaccurate-erase
    misc-incorrect-roundings
    misc-inefficient-algorithm
    misc-macro-parentheses
    misc-macro-repeated-side-effects
    misc-misplaced-const

docs/clang-tidy/checks/misc-for-loop-iterator-invalidation.rst

+.. title:: clang-tidy - misc-for-loop-iterator-invalidation
+
+misc-for-loop-iterator-invalidation
+==========================
+
+Finds suspicious method calls on objects iterated using
+C++11 for-range loop. If such call can invalidate iterators then
+the behaviour is undefined.
+
+.. code-block:: c++
+
+  std::vector<int> v = {1, 2, 3};
+  for (auto i : v) {
+    v.push_back(0); // Boom!
+  }
+
+The following heuristics is used to tell if a call is suspicious:
+
+Function is likely to invalidate iterators if this function
+is not const and container doesn't have a function with the same name, same
+parameters (except 'this' parameter) but marked as const.
+
+If the type of iterated object is on :option:`SafeTypes` list then call is ignored.
+
+If after call execution will not come back to loop then call is ignored. It means that
+following examples will not emit warning:
+
+.. code-block:: c++
+
+  std::vector<int> v = {1, 2, 3};
+  for (auto i : v) {
+    if (i == 2) {
+      v.push_back(0);
+      break;
+    }
+  }
+
+.. code-block:: c++
+
+  std::vector<int> v = {1, 2, 3};
+  for (auto i : v) {
+    if (i == 2) {
+      v.push_back(0);
+      return;
+    }
+  }
+
+Options
+-------
+
+.. option:: SafeTypes
+
+   Semicolon-separated list of names of types that should be considered safe. By default equal to
+   ``::std::list; ::std::forward_list``.

test/clang-tidy/misc-for-loop-iterator-invalidation.cpp

+// RUN: %check_clang_tidy %s misc-for-loop-iterator-invalidation %t
+
+namespace std {
+
+template <typename First, typename Second>
+class pair { };
+
+template <typename Key, typename Value>
+class unordered_map {
+public:
+  using value_type = pair<Key, Value>;
+  using iterator = value_type*;
+
+  Value& operator[](const Key&) { return *new Key(); }
+
+  void erase(const Key&) { }
+  void insert(const Key&, const Value&) { }
+
+  iterator find(const Key&) const { return nullptr; }
+
+  iterator begin() { return nullptr; }
+  iterator begin() const { return nullptr; }
+  iterator end() { return nullptr; }
+  iterator end() const { return nullptr; }
+};
+
+template <typename Value>
+class vector {
+public:
+  using iterator = Value*;
+
+  Value& operator[](int) { return *new Value(); }
+  const Value& operator[](int) const { return *new Value(); }
+
+  void erase(iterator) { }
+
+  void push_back(Value) { }
+
+  iterator begin() { return nullptr; }
+  iterator begin() const { return nullptr; }
+  iterator end() { return nullptr; }
+  iterator end() const { return nullptr; }
+};
+
+template <typename Value>
+class list {
+public:
+  using iterator = Value*;
+
+  void push_front(Value) { }
+
+  iterator begin() { return nullptr; }
+  iterator begin() const { return nullptr; }
+  iterator end() { return nullptr; }
+  iterator end() const { return nullptr; }
+};
+
+} // namespace std
+
+[[ noreturn ]] void NoReturn() {
+  throw 42;
+}
+
+
+void foo() {
+  std::unordered_map<int, int> unordered_map;
+
+  unordered_map.erase(10);
+
+  for (auto& z : unordered_map) {
+    unordered_map[1] = 42;
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: this call may lead to iterator invalidation [misc-for-loop-iterator-invalidation]
+
+    unordered_map.erase(10);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning:
+
+
+    unordered_map.insert(12, 34);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning:
+
+    unordered_map.find(123);
+
+    unordered_map.begin();
+    unordered_map.end();
+  }
+
+  unordered_map.erase(10);
+
+  std::unordered_map<int, int> unordered_map2;
+
+  for (auto& z : unordered_map2) {
+    unordered_map[1] = 42;
+    unordered_map.erase(10);
+
+    unordered_map2.erase(10);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning:
+  }
+
+  std::vector<char> vector;
+  for (auto& e: vector) {
+    vector[0] = char(e);
+
+    vector.begin();
+
+    vector.erase(nullptr);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: this call may lead to iterator invalidation [misc-for-loop-iterator-invalidation]
+
+
+    if (vector[0] == 'a') {
+      vector.erase(nullptr); // OK
+      break;
+    }
+    else if (vector[0] == 'b') {
+      vector.erase(nullptr); // also OK
+      return;
+    }
+
+    if (vector[1] == 'g') {
+      vector.erase(nullptr); // also OK
+      NoReturn();
+    }
+  }
+
+  std::vector<char>& vector_reference = vector;
+  for (auto& e: vector_reference) {
+    vector_reference.push_back(e);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: this call may lead to iterator invalidation [misc-for-loop-iterator-invalidation]
+  }
+
+  std::list<int> list;
+  for (auto& e: list) {
+    list.push_front(0);
+  }
+}
+
+void foo2(std::vector<int> v)  {
+  for (auto x: v) {
+    v.push_back(x);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: this call may lead to iterator invalidation [misc-for-loop-iterator-invalidation]
+  }
+}
+
+void foo3(std::vector<int>& v)  {
+  for (auto x: v) {
+    v.push_back(x);
+    // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: this call may lead to iterator invalidation [misc-for-loop-iterator-invalidation]
+  }
+}