Index: clang-tidy/misc/CMakeLists.txt =================================================================== --- clang-tidy/misc/CMakeLists.txt +++ clang-tidy/misc/CMakeLists.txt @@ -3,6 +3,7 @@ add_clang_library(clangTidyMiscModule ArgumentCommentCheck.cpp AssertSideEffectCheck.cpp + ForLoopIteratorInvalidationCheck.cpp ForwardingReferenceOverloadCheck.cpp MisplacedConstCheck.cpp UnconventionalAssignOperatorCheck.cpp Index: clang-tidy/misc/ForLoopIteratorInvalidationCheck.h =================================================================== --- /dev/null +++ clang-tidy/misc/ForLoopIteratorInvalidationCheck.h @@ -0,0 +1,46 @@ +//===--- 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 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 SafeTypes; +}; + +} // namespace misc +} // namespace tidy +} // namespace clang + +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_FOR_LOOP_ITERATOR_INVALIDATION_H Index: clang-tidy/misc/ForLoopIteratorInvalidationCheck.cpp =================================================================== --- /dev/null +++ clang-tidy/misc/ForLoopIteratorInvalidationCheck.cpp @@ -0,0 +1,147 @@ +//===--- 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(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(MethodCall); + const auto *MatchedForStatement = + Result.Nodes.getNodeAs(ForStatement); + const auto *MethodDecl = + Result.Nodes.getNodeAs(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(MatchedForStatement); + + // Construct a CFG and ExprSequence to find possible sequences of operations. + const std::unique_ptr 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 Index: clang-tidy/misc/MiscTidyModule.cpp =================================================================== --- clang-tidy/misc/MiscTidyModule.cpp +++ clang-tidy/misc/MiscTidyModule.cpp @@ -16,6 +16,7 @@ #include "DanglingHandleCheck.h" #include "DefinitionsInHeadersCheck.h" #include "FoldInitTypeCheck.h" +#include "ForLoopIteratorInvalidationCheck.h" #include "ForwardDeclarationNamespaceCheck.h" #include "ForwardingReferenceOverloadCheck.h" #include "InaccurateEraseCheck.h" @@ -66,6 +67,8 @@ CheckFactories.registerCheck("misc-argument-comment"); CheckFactories.registerCheck( "misc-assert-side-effect"); + CheckFactories.registerCheck( + "misc-for-loop-iterator-invalidation"); CheckFactories.registerCheck( "misc-forwarding-reference-overload"); CheckFactories.registerCheck("misc-misplaced-const"); Index: docs/ReleaseNotes.rst =================================================================== --- docs/ReleaseNotes.rst +++ docs/ReleaseNotes.rst @@ -86,7 +86,13 @@ 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 + `_ 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 `_ check Index: docs/clang-tidy/checks/list.rst =================================================================== --- docs/clang-tidy/checks/list.rst +++ docs/clang-tidy/checks/list.rst @@ -76,6 +76,7 @@ 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 Index: docs/clang-tidy/checks/misc-for-loop-iterator-invalidation.rst =================================================================== --- /dev/null +++ docs/clang-tidy/checks/misc-for-loop-iterator-invalidation.rst @@ -0,0 +1,54 @@ +.. 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 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 v = {1, 2, 3}; + for (auto i : v) { + if (i == 2) { + v.push_back(0); + break; + } + } + +.. code-block:: c++ + + std::vector 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``. Index: test/clang-tidy/misc-for-loop-iterator-invalidation.cpp =================================================================== --- /dev/null +++ test/clang-tidy/misc-for-loop-iterator-invalidation.cpp @@ -0,0 +1,148 @@ +// RUN: %check_clang_tidy %s misc-for-loop-iterator-invalidation %t + +namespace std { + +template +class pair { }; + +template +class unordered_map { +public: + using value_type = pair; + 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 +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 +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 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 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 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& 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 list; + for (auto& e: list) { + list.push_front(0); + } +} + +void foo2(std::vector 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& 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] + } +}