Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -314,6 +314,14 @@ HelpText<"Check for iterators used outside their valid ranges">, DescFile<"IteratorChecker.cpp">; +def MismatchedIteratorChecker : Checker<"MismatchedIterator">, + HelpText<"Check for use of iterators of different containers where iterators of the same container are expected">, + DescFile<"IteratorChecker.cpp">; + +def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">, + HelpText<"Check for use of invalidated iterators">, + DescFile<"IteratorChecker.cpp">; + def MisusedMovedObjectChecker: Checker<"MisusedMovedObject">, HelpText<"Method calls on a moved-from object and copying a moved-from " "object will be reported">, Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -67,11 +67,14 @@ // a constraint which we later retrieve when doing an actual comparison. #include "ClangSACheckers.h" +#include "clang/AST/DeclTemplate.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" +#include + using namespace clang; using namespace ento; @@ -85,34 +88,43 @@ // Container the iterator belongs to const MemRegion *Cont; + // Whether iterator is valid + bool Valid; + // Abstract offset const SymbolRef Offset; - IteratorPosition(const MemRegion *C, SymbolRef Of) - : Cont(C), Offset(Of) {} + IteratorPosition(const MemRegion *C, bool V, SymbolRef Of) + : Cont(C), Valid(V), Offset(Of) {} public: const MemRegion *getContainer() const { return Cont; } + bool isValid() const { return Valid; } SymbolRef getOffset() const { return Offset; } + IteratorPosition invalidate() const { + return IteratorPosition(Cont, false, Offset); + } + static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) { - return IteratorPosition(C, Of); + return IteratorPosition(C, true, Of); } IteratorPosition setTo(SymbolRef NewOf) const { - return IteratorPosition(Cont, NewOf); + return IteratorPosition(Cont, Valid, NewOf); } bool operator==(const IteratorPosition &X) const { - return Cont == X.Cont && Offset == X.Offset; + return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset; } bool operator!=(const IteratorPosition &X) const { - return Cont != X.Cont || Offset != X.Offset; + return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset; } void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddPointer(Cont); + ID.AddInteger(Valid); ID.Add(Offset); } }; @@ -187,9 +199,12 @@ eval::Assume> { std::unique_ptr OutOfRangeBugType; + std::unique_ptr MismatchedBugType; + std::unique_ptr InvalidatedBugType; void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal, const SVal &RVal, OverloadedOperatorKind Op) const; + void verifyAccess(CheckerContext &C, const SVal &Val) const; void verifyDereference(CheckerContext &C, const SVal &Val) const; void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, bool Postfix) const; @@ -204,17 +219,28 @@ const SVal &Cont) const; void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, const MemRegion *Cont) const; + void handleAssign(CheckerContext &C, const SVal &Cont) const; void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, const SVal &RetVal, const SVal &LHS, const SVal &RHS) const; + void verifyMatch(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) const; + void reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const; + void reportMismatchedBug(const StringRef &Message, const SVal &Val1, + const SVal &Val2, CheckerContext &C, + ExplodedNode *ErrNode) const; + void reportInvalidatedBug(const StringRef &Message, const SVal &Val, + CheckerContext &C, ExplodedNode *ErrNode) const; public: IteratorChecker(); enum CheckKind { CK_IteratorRangeChecker, + CK_MismatchedIteratorChecker, + CK_InvalidatedIteratorChecker, CK_NumCheckKinds }; @@ -248,7 +274,9 @@ bool isIterator(const CXXRecordDecl *CRD); bool isBeginCall(const FunctionDecl *Func); bool isEndCall(const FunctionDecl *Func); +bool isAssignmentOperator(OverloadedOperatorKind OK); bool isSimpleComparisonOperator(OverloadedOperatorKind OK); +bool isAccessOperator(OverloadedOperatorKind OK); bool isDereferenceOperator(OverloadedOperatorKind OK); bool isIncrementOperator(OverloadedOperatorKind OK); bool isDecrementOperator(OverloadedOperatorKind OK); @@ -287,6 +315,8 @@ const IteratorPosition &Pos1, const IteratorPosition &Pos2, bool Equal); +ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont); const ContainerData *getContainerData(ProgramStateRef State, const MemRegion *Cont); ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, @@ -299,16 +329,32 @@ OutOfRangeBugType.reset( new BugType(this, "Iterator out of range", "Misuse of STL APIs")); OutOfRangeBugType->setSuppressOnSink(true); + MismatchedBugType.reset( + new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs")); + MismatchedBugType->setSuppressOnSink(true); + InvalidatedBugType.reset( + new BugType(this, "Iterator invalidated", "Misuse of STL APIs")); + InvalidatedBugType->setSuppressOnSink(true); } void IteratorChecker::checkPreCall(const CallEvent &Call, CheckerContext &C) const { - // Check for out of range access + // Check for out of range access or access of invalidated position and + // iterator mismatches const auto *Func = dyn_cast_or_null(Call.getDecl()); if (!Func) return; if (Func->isOverloadedOperator()) { + if (ChecksEnabled[CK_InvalidatedIteratorChecker] && + isAccessOperator(Func->getOverloadedOperator())) { + // Check for any kind of access of invalidated iterator positions + if (const auto *InstCall = dyn_cast(&Call)) { + verifyAccess(C, InstCall->getCXXThisVal()); + } else { + verifyAccess(C, Call.getArgSVal(0)); + } + } if (ChecksEnabled[CK_IteratorRangeChecker] && isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { if (const auto *InstCall = dyn_cast(&Call)) { @@ -334,6 +380,65 @@ verifyDereference(C, Call.getArgSVal(0)); } } + } else if (!isa(&Call)) { + // The main purpose of iterators is to abstract away from different + // containers and provide a (maybe limited) uniform access to them. + // This implies that any correctly written template function that + // works on multiple containers using iterators takes different + // template parameters for different containers. So we can safely + // assume that passing iterators of different containers as arguments + // whose type replaces the same template parameter is a bug. + // + // Example: + // template + // void f(I1 first1, I1 last1, I2 first2, I2 last2); + // + // In this case the first two arguments to f() must be iterators must belong + // to the same container and the last to also to the same container but + // not neccessarily to the same as the first two. + + if (!ChecksEnabled[CK_MismatchedIteratorChecker]) + return; + + const auto *Templ = Func->getPrimaryTemplate(); + if (!Templ) + return; + + const auto *TParams = Templ->getTemplateParameters(); + const auto *TArgs = Func->getTemplateSpecializationArgs(); + + // Iterate over all the template parameters + for (size_t i = 0; i < TParams->size(); ++i) { + const auto *TPDecl = dyn_cast(TParams->getParam(i)); + if (!TPDecl) + continue; + + if (TPDecl->isParameterPack()) + continue; + + const auto TAType = TArgs->get(i).getAsType(); + if (!isIteratorType(TAType)) + continue; + + SVal LHS = UndefinedVal(); + + // For every template parameter which is an iterator type in the + // instantiation look for all functions parameters type by it and + // check whether they belong to the same container + for (auto j = 0U; j < Func->getNumParams(); ++j) { + const auto *Param = Func->getParamDecl(j); + const auto *ParamType = + Param->getType()->getAs(); + if (!ParamType || + ParamType->getReplacedParameter()->getDecl() != TPDecl) + continue; + if (LHS.isUndef()) { + LHS = Call.getArgSVal(j); + } else { + verifyMatch(C, LHS, Call.getArgSVal(j)); + } + } + } } } @@ -346,7 +451,10 @@ if (Func->isOverloadedOperator()) { const auto Op = Func->getOverloadedOperator(); - if (isSimpleComparisonOperator(Op)) { + if (isAssignmentOperator(Op)) { + const auto *InstCall = dyn_cast(&Call); + handleAssign(C, InstCall->getCXXThisVal()); + } else if (isSimpleComparisonOperator(Op)) { if (const auto *InstCall = dyn_cast(&Call)) { handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(), Call.getArgSVal(0), Op); @@ -456,7 +564,7 @@ // FIXME: This solution is unreliable. It may happen that another checker // subscribes to the pre-statement check of `CXXOperatorCallExpr` // and adds a transition before us. The proper fix is to make the - // CFG provide a `ConstructionContext` for the `CXXOperatorCallExpr`, + // CFG provide a `ConstructionContext` for the `CXXOperatorCallExpr` // which would turn the corresponding `CFGStmt` element into a // `CFGCXXRecordTypedCall` element, which will allow `ExprEngine` to // foresee that the `begin()`/`end()` call constructs the object @@ -623,6 +731,21 @@ } } +void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Val); + if (Pos && !Pos->isValid()) { + // If I do not put a tag here, some invalidation tests will fail + static CheckerProgramPointTag Tag("InvalidatedIteratorChecker", + "InvalidatedIterator"); + auto *N = C.generateNonFatalErrorNode(State, &Tag); + if (!N) { + return; + } + reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N); + } +} + void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, bool Postfix) const { // Increment the symbolic expressions which represents the position of the @@ -794,6 +917,24 @@ } } +void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) const { + // Verify match between the containers of two iterators + auto State = C.getState(); + const auto *Pos1 = getIteratorPosition(State, Iter1); + const auto *Pos2 = getIteratorPosition(State, Iter2); + if (Pos1 && Pos2 && Pos1->getContainer() != Pos2->getContainer()) { + // If I do not put a tag here, the comparison test will fail + static CheckerProgramPointTag Tag("MismatchedIteratorChecker", + "MismatchedIterator"); + auto *N = C.generateNonFatalErrorNode(State, &Tag); + if (!N) { + return; + } + reportMismatchedBug("Iterator access mismatched.", Iter1, Iter2, C, N); + } +} + void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); @@ -863,6 +1004,26 @@ C.addTransition(State); } +void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // Assignment of a new value to a container always invalidates all its + // iterators + auto State = C.getState(); + const auto CData = getContainerData(State, ContReg); + if (CData) { + State = invalidateAllIteratorPositions(State, ContReg); + } + + C.addTransition(State); +} + void IteratorChecker::reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const { @@ -871,6 +1032,24 @@ C.emitReport(std::move(R)); } +void IteratorChecker::reportMismatchedBug(const StringRef &Message, + const SVal &Val1, const SVal &Val2, + CheckerContext &C, + ExplodedNode *ErrNode) const { + auto R = llvm::make_unique(*MismatchedBugType, Message, ErrNode); + R->markInteresting(Val1); + R->markInteresting(Val2); + C.emitReport(std::move(R)); +} + +void IteratorChecker::reportInvalidatedBug(const StringRef &Message, + const SVal &Val, CheckerContext &C, + ExplodedNode *ErrNode) const { + auto R = llvm::make_unique(*InvalidatedBugType, Message, ErrNode); + R->markInteresting(Val); + C.emitReport(std::move(R)); +} + namespace { bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); @@ -946,10 +1125,17 @@ return IdInfo->getName().endswith_lower("end"); } +bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } + bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { return OK == OO_EqualEqual || OK == OO_ExclaimEqual; } +bool isAccessOperator(OverloadedOperatorKind OK) { + return isDereferenceOperator(OK) || isIncrementOperator(OK) || + isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK); +} + bool isDereferenceOperator(OverloadedOperatorKind OK) { return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || OK == OO_Subscript; @@ -1174,6 +1360,49 @@ return State; } +template +ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, + Process Proc) { + auto &RegionMapFactory = State->get_context(); + auto RegionMap = State->get(); + bool Changed = false; + for (const auto Reg : RegionMap) { + if (Cond(Reg.second)) { + RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second)); + Changed = true; + } + } + + if (Changed) + State = State->set(RegionMap); + + auto &SymbolMapFactory = State->get_context(); + auto SymbolMap = State->get(); + Changed = false; + for (const auto Sym : SymbolMap) { + if (Cond(Sym.second)) { + SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second)); + Changed = true; + } + } + + if (Changed) + State = State->set(SymbolMap); + + return State; +} + +ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont) { + auto MatchCont = [&](const IteratorPosition &Pos) { + return Pos.getContainer() == Cont; + }; + auto Invalidate = [&](const IteratorPosition &Pos) { + return Pos.invalidate(); + }; + return processIteratorPositions(State, MatchCont, Invalidate); +} + bool isZero(ProgramStateRef State, const NonLoc &Val) { auto &BVF = State->getBasicVals(); return compare(State, Val, @@ -1246,4 +1475,5 @@ } REGISTER_CHECKER(IteratorRangeChecker) - +REGISTER_CHECKER(MismatchedIteratorChecker) +REGISTER_CHECKER(InvalidatedIteratorChecker) Index: test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- test/Analysis/Inputs/system-header-simulator-cxx.h +++ test/Analysis/Inputs/system-header-simulator-cxx.h @@ -252,6 +252,15 @@ return size_t(_finish - _start); } + vector& operator=(const vector &other); + vector& operator=(vector &&other); + vector& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + void clear(); void push_back(const T &value); @@ -301,8 +310,21 @@ list& operator=(list &&other); list& operator=(std::initializer_list ilist); + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + void clear(); + void push_back(const T &value); + void push_back(T &&value); + void pop_back(); + + void push_front(const T &value); + void push_front(T &&value); + void pop_front(); + iterator begin() { return iterator(_start); } const_iterator begin() const { return const_iterator(_start); } const_iterator cbegin() const { return const_iterator(_start); } @@ -338,6 +360,15 @@ return size_t(_finish - _start); } + deque& operator=(const deque &other); + deque& operator=(deque &&other); + deque& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + void clear(); void push_back(const T &value); @@ -351,11 +382,11 @@ T &operator[](size_t n) { return _start[n]; } - + const T &operator[](size_t n) const { return _start[n]; } - + iterator begin() { return iterator(_start); } const_iterator begin() const { return const_iterator(_start); } const_iterator cbegin() const { return const_iterator(_start); } @@ -367,7 +398,7 @@ T& back() { return *(end() - 1); } const T& back() const { return *(end() - 1); } }; - + template class forward_list { struct __item { @@ -387,6 +418,15 @@ forward_list(forward_list &&other); ~forward_list(); + forward_list& operator=(const forward_list &other); + forward_list& operator=(forward_list &&other); + forward_list& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + void clear(); void push_front(const T &value); @@ -602,6 +642,12 @@ template InputIterator find(InputIterator first, InputIterator last, const T &val); + template + ForwardIterator1 find_first_of(ForwardIterator1 first1, + ForwardIterator1 last1, + ForwardIterator2 first2, + ForwardIterator2 last2); + template OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); Index: test/Analysis/diagnostics/explicit-suppression.cpp =================================================================== --- test/Analysis/diagnostics/explicit-suppression.cpp +++ test/Analysis/diagnostics/explicit-suppression.cpp @@ -19,6 +19,6 @@ void testCopyNull(C *I, C *E) { std::copy(I, E, (C *)0); #ifndef SUPPRESSED - // expected-warning@../Inputs/system-header-simulator-cxx.h:514 {{Called C++ object pointer is null}} + // expected-warning@../Inputs/system-header-simulator-cxx.h:554 {{Called C++ object pointer is null}} #endif } Index: test/Analysis/invalidated-iterator.cpp =================================================================== --- /dev/null +++ test/Analysis/invalidated-iterator.cpp @@ -0,0 +1,32 @@ +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=false %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +void bad_copy_assign_operator_list1(std::list &L1, + const std::list &L2) { + auto i0 = L1.cbegin(); + L1 = L2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_vector1(std::vector &V1, + const std::vector &V2) { + auto i0 = V1.cbegin(); + V1 = V2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_deque1(std::deque &D1, + const std::deque &D2) { + auto i0 = D1.cbegin(); + D1 = D2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_forward_list1(std::forward_list &FL1, + const std::forward_list &FL2) { + auto i0 = FL1.cbegin(); + FL1 = FL2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} Index: test/Analysis/mismatched-iterator.cpp =================================================================== --- /dev/null +++ test/Analysis/mismatched-iterator.cpp @@ -0,0 +1,25 @@ +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=false %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +void good_find(std::vector &v, int n) { + std::find(v.cbegin(), v.cend(), n); // no-warning +} + +void good_find_first_of(std::vector &v1, std::vector &v2) { + std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend()); // no-warning +} + +void good_copy(std::vector &v1, std::vector &v2, int n) { + std::copy(v1.cbegin(), v1.cend(), v2.begin()); // no-warning +} + +void bad_find(std::vector &v1, std::vector &v2, int n) { + std::find(v1.cbegin(), v2.cend(), n); // expected-warning{{Iterator access mismatched}} +} + +void bad_find_first_of(std::vector &v1, std::vector &v2) { + std::find_first_of(v1.cbegin(), v2.cend(), v2.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}} + std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}} +}