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; + + // 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, 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 + +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(CallName) != nullptr; + if (IsInvalidatingCall) + return (MemoIter->second = true); + + // A recursive call might invalidate. + const auto *CallUse = Match.getNodeAs(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(CallArgName); + const auto *FuncDecl = Match.getNodeAs(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(ExprName); + const auto *RefDecl = Result.Nodes.getNodeAs(DeclName); + const auto *RefDeclStmt = Result.Nodes.getNodeAs(DeclStmtName); + const auto *Func = Result.Nodes.getNodeAs(BlockFuncName); + const auto *VectorDecl = Result.Nodes.getNodeAs(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 TheCFG = + CFG::buildCFG(nullptr, FuncBody, Result.Context, Options); + const std::unique_ptr BlockMap( + new StmtToBlockMap(TheCFG.get(), Result.Context)); + const std::unique_ptr 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(); + if (!StmtPtr.hasValue()) + continue; + auto Results = match(ModifyingMatcher, *(StmtPtr->getStmt()), *Context); + + for (const auto &Match : Results) { + const auto *InvalidatingUse = + Match.getNodeAs(CallName); + const auto *CallUse = Match.getNodeAs(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(InvalidatingUse) + : cast(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("misc-argument-comment"); CheckFactories.registerCheck( "misc-assert-side-effect"); - CheckFactories.registerCheck("misc-misplaced-const"); + CheckFactories.registerCheck( + "misc-invalidated-iterators"); + CheckFactories.registerCheck( + "misc-misplaced-const"); CheckFactories.registerCheck( "misc-unconventional-assign-operator"); CheckFactories.registerCheck( 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 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 +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 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 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 &Vec) { + Vec.push_back(555); +} + +void callModifyVector(std::vector &Vec) { + modifyVector(Vec); +} + +void checkVector(const std::vector &){} +void anotherCheckVector(std::vector) {} + + +void test_calling() { + std::vector 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 RecVecBad, LambdaVecBad; + RecVecBad.push_back(99); + LambdaVecBad.push_back(0); + int &BadRef = RecVecBad[0]; + int &BadLambdaRef = LambdaVecBad[0]; + + auto lambda = [](std::vector &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 &a, std::vector &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