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
+ InvalidatedIteratorsCheck.cpp
MisplacedConstCheck.cpp
UnconventionalAssignOperatorCheck.cpp
BoolPointerImplicitConversionCheck.cpp
Index: clang-tidy/misc/InvalidatedIteratorsCheck.h
===================================================================
--- /dev/null
+++ clang-tidy/misc/InvalidatedIteratorsCheck.h
@@ -0,0 +1,60 @@
+//===--- InvalidatedIteratorsCheck.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_INVALIDATED_ITERATORS_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INVALIDATED_ITERATORS_H
+
+#include "../ClangTidy.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+/// This check warns about the possible use of the invalidated container
+/// iterators, pointers and/or references.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/misc-invalidated-iterators.html
+class InvalidatedIteratorsCheck : public ClangTidyCheck {
+public:
+ InvalidatedIteratorsCheck(StringRef Name, ClangTidyContext *Context)
+ : ClangTidyCheck(Name, Context) {}
+ void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+ void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+ using ExprMatcherType = ast_matchers::internal::BindableMatcher<Stmt>;
+
+ // Returns the clang-tidy matcher binding to the possibly invalidating uses
+ // of the container (either invoking a dangerous member call or calling
+ // another function with a non-const reference.)
+ ExprMatcherType getModifyingMatcher(const VarDecl *VectorDecl);
+
+ // Checks if given Func can invalidate the container at its given argument
+ // (ArgId). For convienience, number of Func's arguemnts is also passed.
+ bool canFuncInvalidate(const FunctionDecl *Func, unsigned ArgId,
+ unsigned NumCallArgs, ASTContext *Context);
+
+ // Checks if given Call can invalidate the container provided by Match.
+ bool canCallInvalidate(const CallExpr *Call, ast_matchers::BoundNodes Match,
+ ASTContext *Context);
+
+ // A cache which remembers the results of canFuncInvalidate calls. It
+ // is necessary in order to prevent canFuncInvalidate from looping or
+ // having exponential time behavior.
+ std::map<std::tuple<const FunctionDecl *, unsigned, unsigned>, bool>
+ CanFuncInvalidateMemo;
+};
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INVALIDATED_ITERATORS_H
Index: clang-tidy/misc/InvalidatedIteratorsCheck.cpp
===================================================================
--- /dev/null
+++ clang-tidy/misc/InvalidatedIteratorsCheck.cpp
@@ -0,0 +1,229 @@
+//===--- InvalidatedIteratorsCheck.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 "InvalidatedIteratorsCheck.h"
+#include "../utils/ExprSequence.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Analysis/CFG.h"
+#include <iostream>
+
+using namespace clang::ast_matchers;
+using namespace clang::tidy::utils;
+using namespace clang::ast_type_traits;
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+namespace {
+const char BlockFuncName[] = "BlockFunc";
+const char DeclStmtName[] = "DeclarationStmt";
+const char DeclName[] = "Declaration";
+const char ExprName[] = "Expr";
+const char VectorName[] = "TheVector";
+
+const char CallExprName[] = "CallExpr";
+const char CallName[] = "InvalidatingCall";
+const char CalledDeclName[] = "FuncDecl";
+const char CallArgName[] = "CallArg";
+}
+
+void InvalidatedIteratorsCheck::registerMatchers(MatchFinder *Finder) {
+ if (!getLangOpts().CPlusPlus)
+ return;
+
+ Finder->addMatcher(
+ declRefExpr(
+ hasDeclaration(
+ varDecl(allOf(hasAncestor(functionDecl().bind(BlockFuncName)),
+ hasParent(declStmt().bind(DeclStmtName)),
+ hasType(referenceType()),
+ hasDescendant(declRefExpr(
+ hasType(cxxRecordDecl(hasName("std::vector"))),
+ hasDeclaration(varDecl().bind(VectorName))))))
+ .bind(DeclName)))
+ .bind(ExprName),
+ this);
+}
+
+InvalidatedIteratorsCheck::ExprMatcherType
+InvalidatedIteratorsCheck::getModifyingMatcher(const VarDecl *VectorDecl) {
+ // An invalidation might occur by directly calling a risky method.
+ auto InvalidateMatcher =
+ cxxMemberCallExpr(has(memberExpr(hasDeclaration(cxxMethodDecl(hasAnyName(
+ "push_back", "emplace_back", "clear",
+ "insert", "emplace"))),
+ has(declRefExpr(hasDeclaration(
+ varDecl(equalsNode(VectorDecl))))))))
+ .bind(CallName);
+ // It may also occur by calling a method through a non-const reference.
+ auto FuncCallMatcher =
+ callExpr(hasDeclaration(functionDecl().bind(CalledDeclName)),
+ hasAnyArgument(
+ declRefExpr(hasDeclaration(varDecl(equalsNode(VectorDecl))))
+ .bind(CallArgName)))
+ .bind(CallExprName);
+ auto ModifyingMatcher = expr(eachOf(InvalidateMatcher, FuncCallMatcher));
+
+ return ModifyingMatcher;
+}
+
+bool InvalidatedIteratorsCheck::canFuncInvalidate(const FunctionDecl *Func,
+ unsigned ArgId,
+ unsigned NumCallArgs,
+ ASTContext *Context) {
+ // Try to find the result of some previous canFuncInvalidate call
+ // which matches our arguments.
+ const auto MemoTuple = std::make_tuple(Func, ArgId, NumCallArgs);
+ const auto MemoChkIter = CanFuncInvalidateMemo.find(MemoTuple);
+ if (MemoChkIter != CanFuncInvalidateMemo.end())
+ return MemoChkIter->second;
+
+ // Temporarily insert a negative answer so that recursive functions
+ // won't loop our method.
+ const auto InsertResult =
+ CanFuncInvalidateMemo.insert(std::make_pair(MemoTuple, false));
+ assert(InsertResult.second);
+ const auto MemoIter = InsertResult.first;
+
+ if (!Func->hasBody()) {
+ // We cannot assume anything about the function, not knowing its
+ // body; it possibly invalidates our iterators.
+ return (MemoIter->second = true);
+ }
+
+ if (Func->getNumParams() != NumCallArgs) {
+ // Sometimes number of call arguments is not equal to the number
+ // of declaration arguments. As far as we know, it happens only when
+ // calling some class operators. In this case, there is also an
+ // additional *this argument as the first argument of the call.
+ // We should get rid of it so as to match the declaration arguments.
+ assert(Func->getNumParams() == NumCallArgs - 1 &&
+ "Number of function parameters should be equal to number of call "
+ "arguments or call arguments minus one");
+
+ if (ArgId == 0) {
+ // We don't care about member calls. These should be covered in other
+ // matchers.
+ return false;
+ }
+ ArgId--;
+ }
+
+ const auto *Arg = Func->parameters()[ArgId];
+
+ // Get all possible invalidations of the container Arg.
+ auto ModifyingMatcher = functionDecl(hasDescendant(getModifyingMatcher(Arg)));
+
+ const auto Matches = match(ModifyingMatcher, *Func, *Context);
+ for (const auto &Match : Matches) {
+ // A dangerous method possibly invalidates iterators.
+ const bool IsInvalidatingCall =
+ Match.getNodeAs<CXXMemberCallExpr>(CallName) != nullptr;
+ if (IsInvalidatingCall)
+ return (MemoIter->second = true);
+
+ // A recursive call might invalidate.
+ const auto *CallUse = Match.getNodeAs<CallExpr>(CallExprName);
+ assert(CallUse);
+
+ if (canCallInvalidate(CallUse, Match, Context))
+ return (MemoIter->second = true);
+ }
+ return false;
+}
+
+bool InvalidatedIteratorsCheck::canCallInvalidate(
+ const CallExpr *Call, ast_matchers::BoundNodes Match, ASTContext *Context) {
+ const auto *FuncArg = Match.getNodeAs<Expr>(CallArgName);
+ const auto *FuncDecl = Match.getNodeAs<FunctionDecl>(CalledDeclName);
+
+ // Go through all call arguments and check if any of them matches to
+ // our argument and can invalidate iterators pointing to it.
+ for (unsigned i = 0; i < Call->getNumArgs(); ++i) {
+ const auto *Arg = Call->getArg(i);
+
+ if (Arg == FuncArg &&
+ canFuncInvalidate(FuncDecl, i, Call->getNumArgs(), Context))
+ return true;
+ }
+
+ return false;
+}
+
+void InvalidatedIteratorsCheck::check(const MatchFinder::MatchResult &Result) {
+ const auto *RefUse = Result.Nodes.getNodeAs<DeclRefExpr>(ExprName);
+ const auto *RefDecl = Result.Nodes.getNodeAs<VarDecl>(DeclName);
+ const auto *RefDeclStmt = Result.Nodes.getNodeAs<DeclStmt>(DeclStmtName);
+ const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>(BlockFuncName);
+ const auto *VectorDecl = Result.Nodes.getNodeAs<VarDecl>(VectorName);
+ Stmt *FuncBody = Func->getBody();
+
+ CFG::BuildOptions Options;
+
+ auto *Context = Result.Context;
+
+ // Construct a CFG and ExprSequence so that it is possible to find possible
+ // sequences of operations.
+ const std::unique_ptr<CFG> TheCFG =
+ CFG::buildCFG(nullptr, FuncBody, Result.Context, Options);
+ const std::unique_ptr<StmtToBlockMap> BlockMap(
+ new StmtToBlockMap(TheCFG.get(), Result.Context));
+ const std::unique_ptr<ExprSequence> Sequence(
+ new ExprSequence(TheCFG.get(), Result.Context));
+ const CFGBlock *Block = BlockMap->blockContainingStmt(RefUse);
+ if (!Block) {
+ return;
+ }
+
+ auto ModifyingMatcher = getModifyingMatcher(VectorDecl);
+
+ for (const auto &BlockElem : *Block) {
+ // In each block, find all possible invalidating operations and process
+ // all of them.
+ const auto StmtPtr = BlockElem.getAs<CFGStmt>();
+ if (!StmtPtr.hasValue())
+ continue;
+ auto Results = match(ModifyingMatcher, *(StmtPtr->getStmt()), *Context);
+
+ for (const auto &Match : Results) {
+ const auto *InvalidatingUse =
+ Match.getNodeAs<CXXMemberCallExpr>(CallName);
+ const auto *CallUse = Match.getNodeAs<CallExpr>(CallExprName);
+
+ // If the candidate invalidating operation is calling the function,
+ // it should be able to invalidate.
+ if (CallUse && !canCallInvalidate(CallUse, Match, Context))
+ continue;
+
+ const Expr *Use =
+ (InvalidatingUse != nullptr ? cast<Expr>(InvalidatingUse)
+ : cast<Expr>(CallUse));
+
+ // The incorrect order of operations is:
+ // 1. Declare a reference.
+ // 2. Make a possibly invalidating use of the container.
+ // 3. Use the reference.
+ if (Sequence->potentiallyAfter(Use, RefDeclStmt) &&
+ Sequence->potentiallyAfter(RefUse, Use)) {
+ diag(RefUse->getLocation(), "%0 might be invalidated before the access")
+ << RefDecl;
+ // TODO: add a whole possible chain of invalidations.
+ diag(Use->getExprLoc(), "possible place of invalidation",
+ DiagnosticIDs::Note);
+ return;
+ }
+ }
+ }
+}
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
Index: clang-tidy/misc/MiscTidyModule.cpp
===================================================================
--- clang-tidy/misc/MiscTidyModule.cpp
+++ clang-tidy/misc/MiscTidyModule.cpp
@@ -12,6 +12,9 @@
#include "../ClangTidyModuleRegistry.h"
#include "ArgumentCommentCheck.h"
#include "AssertSideEffectCheck.h"
+#include "InvalidatedIteratorsCheck.h"
+#include "MisplacedConstCheck.h"
+#include "UnconventionalAssignOperatorCheck.h"
#include "BoolPointerImplicitConversionCheck.h"
#include "DanglingHandleCheck.h"
#include "DefinitionsInHeadersCheck.h"
@@ -65,7 +68,10 @@
CheckFactories.registerCheck<ArgumentCommentCheck>("misc-argument-comment");
CheckFactories.registerCheck<AssertSideEffectCheck>(
"misc-assert-side-effect");
- CheckFactories.registerCheck<MisplacedConstCheck>("misc-misplaced-const");
+ CheckFactories.registerCheck<InvalidatedIteratorsCheck>(
+ "misc-invalidated-iterators");
+ CheckFactories.registerCheck<MisplacedConstCheck>(
+ "misc-misplaced-const");
CheckFactories.registerCheck<UnconventionalAssignOperatorCheck>(
"misc-unconventional-assign-operator");
CheckFactories.registerCheck<BoolPointerImplicitConversionCheck>(
Index: docs/clang-tidy/checks/list.rst
===================================================================
--- docs/clang-tidy/checks/list.rst
+++ docs/clang-tidy/checks/list.rst
@@ -66,6 +66,7 @@
misc-inaccurate-erase
misc-incorrect-roundings
misc-inefficient-algorithm
+ misc-invalidated-iterators
misc-macro-parentheses
misc-macro-repeated-side-effects
misc-misplaced-const
Index: docs/clang-tidy/checks/misc-invalidated-iterators.rst
===================================================================
--- /dev/null
+++ docs/clang-tidy/checks/misc-invalidated-iterators.rst
@@ -0,0 +1,19 @@
+.. title:: clang-tidy - misc-invalidated-iterators
+
+misc-invalidated-iterators
+==========================
+
+This check finds the possible invalidations of the iterators/references/pointers
+through the container reallocation. If a programmer takes an iterator
+to the element of the container and then twiddles with the container, it is
+possible that the reference does not point to the original variable anymore.
+
+Example:
+
+.. code-block:: c++
+
+ std::vector<int> vec{42};
+ int &ref = vec[0];
+ vec.push_back(2017);
+ ref++; // Incorrect - 'ref' might have been invalidated at 'push_back'.
+
Index: test/clang-tidy/misc-invalidated-iterators.cpp
===================================================================
--- /dev/null
+++ test/clang-tidy/misc-invalidated-iterators.cpp
@@ -0,0 +1,125 @@
+// RUN: %check_clang_tidy %s misc-invalidated-iterators %t
+
+// Sample std::vector implementation.
+namespace std {
+
+template <typename Type>
+class vector {
+ Type tmp;
+
+public:
+ class iterator {
+ Type *data;
+
+ public:
+ iterator(Type *ptr) : data(ptr) {}
+ Type &operator*() { return *data; }
+ };
+
+ vector() {}
+
+ void push_back(Type &&elem) {}
+ void pop_back() {}
+
+ Type &operator[](int position) { return tmp; }
+
+ iterator begin() { return iterator(&tmp); }
+};
+}
+
+// Correct std::vector use.
+void correct_sample() {
+ std::vector<int> VecGood;
+ VecGood.push_back(3);
+
+ int &ElemRef = VecGood[0];
+ ElemRef++;
+ ElemRef *= ElemRef;
+ auto ElemIter = VecGood.begin();
+ (*ElemIter)++;
+ int *ElemPtr = &VecGood[0];
+ (*ElemPtr)++;
+}
+
+// Incorrect std::vector use.
+void incorrect_sample() {
+ std::vector<int> VecBad;
+ VecBad.push_back(3);
+
+ int &ElemRef = VecBad[0];
+ auto ElemIter = VecBad.begin();
+ int *ElemPtr = &VecBad[0];
+
+ VecBad.push_back(42);
+ ElemRef = 42;
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'ElemRef' might be invalidated before the access
+ // CHECK-MESSAGES: :[[@LINE-3]]:10: note: possible place of invalidation
+ (*ElemIter)++;
+ // FIXME: Add a warning here.
+ (*ElemPtr)++;
+ // FIXME: Add a warning here.
+}
+
+
+void modifyVector(std::vector<int> &Vec) {
+ Vec.push_back(555);
+}
+
+void callModifyVector(std::vector<int> &Vec) {
+ modifyVector(Vec);
+}
+
+void checkVector(const std::vector<int> &){}
+void anotherCheckVector(std::vector<int>) {}
+
+
+void test_calling() {
+ std::vector<int> VecBad, VecGood;
+ VecBad.push_back(5);
+ VecGood.push_back(18);
+ VecGood.push_back(1818);
+ int &BadRef = VecBad[0];
+ int &GoodRef = VecGood[0];
+
+ modifyVector(VecBad);
+ checkVector(VecGood);
+ anotherCheckVector(VecGood);
+ VecGood.pop_back();
+
+ BadRef++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'BadRef' might be invalidated before the access
+ // CHECK-MESSAGES: :[[@LINE-7]]:3: note: possible place of invalidation
+ GoodRef++;
+}
+
+void test_recursive_calling() {
+ std::vector<int> RecVecBad, LambdaVecBad;
+ RecVecBad.push_back(99);
+ LambdaVecBad.push_back(0);
+ int &BadRef = RecVecBad[0];
+ int &BadLambdaRef = LambdaVecBad[0];
+
+ auto lambda = [](std::vector<int> &Vec) {
+ callModifyVector(Vec);
+ };
+
+ callModifyVector(RecVecBad);
+ BadRef++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'BadRef' might be invalidated before the access
+ // CHECK-MESSAGES: :[[@LINE-3]]:3: note: possible place of invalidation
+
+ lambda(LambdaVecBad);
+ BadLambdaRef++;
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'BadLambdaRef' might be invalidated before the access
+ // CHECK-MESSAGES: :[[@LINE-3]]:3: note: possible place of invalidation
+}
+
+void test_argument(std::vector<int> &a, std::vector<int> &b) {
+ int &ElemRef = a[0];
+ int &ElemRefGood = b[0];
+ a.push_back(42);
+ ElemRefGood += 42;
+ ElemRef += 42;
+ // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: 'ElemRef' might be invalidated before the access
+ // CHECK-MESSAGES: :[[@LINE-4]]:5: note: possible place of invalidation
+}
\ No newline at end of file