Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -161,6 +161,10 @@ void handleAssign(CheckerContext &C, const SVal &Cont, const Expr *CE = nullptr, const SVal &OldCont = UndefinedVal()) const; + void handlePushBack(CheckerContext &C, const SVal &Cont) const; + void handlePopBack(CheckerContext &C, const SVal &Cont) const; + void handlePushFront(CheckerContext &C, const SVal &Cont) const; + void handlePopFront(CheckerContext &C, const SVal &Cont) const; void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, const SVal &RetVal, const SVal &LHS, const SVal &RHS) const; @@ -227,6 +231,12 @@ bool isComparisonOperator(OverloadedOperatorKind OK); bool isBeginCall(const FunctionDecl *Func); bool isEndCall(const FunctionDecl *Func); +bool isPushBackCall(const FunctionDecl *Func); +bool isEmplaceBackCall(const FunctionDecl *Func); +bool isPopBackCall(const FunctionDecl *Func); +bool isPushFrontCall(const FunctionDecl *Func); +bool isEmplaceFrontCall(const FunctionDecl *Func); +bool isPopFrontCall(const FunctionDecl *Func); bool isAssignmentOperator(OverloadedOperatorKind OK); bool isSimpleComparisonOperator(OverloadedOperatorKind OK); bool isAccessOperator(OverloadedOperatorKind OK); @@ -234,6 +244,9 @@ bool isIncrementOperator(OverloadedOperatorKind OK); bool isDecrementOperator(OverloadedOperatorKind OK); bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); +bool hasSubscriptOperator(const MemRegion *Reg); +bool frontModifiable(const MemRegion *Reg); +bool backModifiable(const MemRegion *Reg); BinaryOperator::Opcode getOpcode(const SymExpr *SE); const RegionOrSymbol getRegionOrSymbol(const SVal &Val); const ProgramStateRef processComparison(ProgramStateRef State, @@ -270,6 +283,9 @@ bool Equal); ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, const MemRegion *Cont); +ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, + SymbolRef Offset, + BinaryOperator::Opcode Opc); ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, const MemRegion *Cont, const MemRegion *NewCont); @@ -478,6 +494,18 @@ } } } else { + if (const auto *InstCall = dyn_cast(&Call)) { + if (isPushBackCall(Func) || isEmplaceBackCall(Func)) { + handlePushBack(C, InstCall->getCXXThisVal()); + } else if (isPopBackCall(Func)) { + handlePopBack(C, InstCall->getCXXThisVal()); + } else if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) { + handlePushFront(C, InstCall->getCXXThisVal()); + } else if (isPopFrontCall(Func)) { + handlePopFront(C, InstCall->getCXXThisVal()); + } + } + const auto *OrigExpr = Call.getOriginExpr(); if (!OrigExpr) return; @@ -1032,6 +1060,139 @@ C.addTransition(State); } +void IteratorChecker::handlePushBack(CheckerContext &C, + const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // For deque-like containers invalidate all iterator positions + auto State = C.getState(); + if (hasSubscriptOperator(ContReg) && frontModifiable(ContReg)) { + State = invalidateAllIteratorPositions(State, ContReg); + C.addTransition(State); + return; + } + + const auto CData = getContainerData(State, ContReg); + if (!CData) + return; + + // For vector-like containers invalidate the past-end iterator positions + if (const auto EndSym = CData->getEnd()) { + if (hasSubscriptOperator(ContReg)) { + State = invalidateIteratorPositions(State, EndSym, BO_GE); + } + auto &SymMgr = C.getSymbolManager(); + const auto newEndSym = + compact(SymMgr, SymMgr.getSymIntExpr(EndSym, BO_Add, One, + SymMgr.getType(EndSym))); + State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); + } + C.addTransition(State); +} + +void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + auto State = C.getState(); + const auto CData = getContainerData(State, ContReg); + if (!CData) + return; + + if (const auto EndSym = CData->getEnd()) { + auto &SymMgr = C.getSymbolManager(); + const auto BackSym = + compact(SymMgr, SymMgr.getSymIntExpr(EndSym, BO_Sub, One, + SymMgr.getType(EndSym))); + // For vector-like and deque-like containers invalidate the last and the + // past-end iterator positions. For list-like containers only invalidate + // the last position + if (hasSubscriptOperator(ContReg) && backModifiable(ContReg)) { + State = invalidateIteratorPositions(State, BackSym, BO_GE); + State = setContainerData(State, ContReg, CData->newEnd(nullptr)); + } else { + State = invalidateIteratorPositions(State, BackSym, BO_EQ); + } + auto newEndSym = BackSym; + State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); + C.addTransition(State); + } +} + +void IteratorChecker::handlePushFront(CheckerContext &C, + const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // For deque-like containers invalidate all iterator positions + auto State = C.getState(); + if (hasSubscriptOperator(ContReg)) { + State = invalidateAllIteratorPositions(State, ContReg); + C.addTransition(State); + } else { + const auto CData = getContainerData(State, ContReg); + if (!CData) + return; + + if (const auto BeginSym = CData->getBegin()) { + auto &SymMgr = C.getSymbolManager(); + const auto newBeginSym = + compact(SymMgr, SymMgr.getSymIntExpr(BeginSym, BO_Sub, One, + SymMgr.getType(BeginSym))); + State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); + C.addTransition(State); + } + } +} + +void IteratorChecker::handlePopFront(CheckerContext &C, + const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + auto State = C.getState(); + const auto CData = getContainerData(State, ContReg); + if (!CData) + return; + + // For deque-like containers invalidate all iterator positions. For list-like + // iterators only invalidate the first position + if (const auto BeginSym = CData->getBegin()) { + if (hasSubscriptOperator(ContReg)) { + State = invalidateIteratorPositions(State, BeginSym, BO_LE); + } else { + State = invalidateIteratorPositions(State, BeginSym, BO_EQ); + } + auto &SymMgr = C.getSymbolManager(); + const auto newBeginSym = + compact(SymMgr, SymMgr.getSymIntExpr(BeginSym, BO_Add, One, + SymMgr.getType(BeginSym))); + State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); + C.addTransition(State); + } +} + void IteratorChecker::reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const { @@ -1065,6 +1226,7 @@ bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc); std::pair decompose(const SymbolRef Sym); +const CXXRecordDecl *getCXXRecordDecl(const MemRegion *Reg); SymbolRef replaceSymbol(SymbolManager &SymMgr, SymbolRef Expr, SymbolRef OldSym, SymbolRef NewSym); @@ -1139,6 +1301,60 @@ return IdInfo->getName().endswith_lower("end"); } +bool isPushBackCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() != 1) + return false; + return IdInfo->getName() == "push_back"; +} + +bool isEmplaceBackCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() < 1) + return false; + return IdInfo->getName() == "emplace_back"; +} + +bool isPopBackCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() > 0) + return false; + return IdInfo->getName() == "pop_back"; +} + +bool isPushFrontCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() != 1) + return false; + return IdInfo->getName() == "push_front"; +} + +bool isEmplaceFrontCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() < 1) + return false; + return IdInfo->getName() == "emplace_front"; +} + +bool isPopFrontCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() > 0) + return false; + return IdInfo->getName() == "pop_front"; +} + bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { @@ -1184,6 +1400,69 @@ return BO_Comma; // Extremal value, neither EQ nor NE } +bool hasSubscriptOperator(const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(Reg); + if (!CRD) + return false; + + for (const auto *Method : CRD->methods()) { + if (!Method->isOverloadedOperator()) + continue; + const auto OPK = Method->getOverloadedOperator(); + if (OPK == OO_Subscript) { + return true; + } + } + return false; +} + +bool frontModifiable(const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(Reg); + if (!CRD) + return false; + + for (const auto *Method : CRD->methods()) { + if (!Method->getDeclName().isIdentifier()) + continue; + if (Method->getName() == "push_front" || Method->getName() == "pop_front") { + return true; + } + } + return false; +} + +bool backModifiable(const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(Reg); + if (!CRD) + return false; + + for (const auto *Method : CRD->methods()) { + if (!Method->getDeclName().isIdentifier()) + continue; + if (Method->getName() == "push_back" || Method->getName() == "pop_back") { + return true; + } + } + return false; +} + +const CXXRecordDecl *getCXXRecordDecl(const MemRegion *Reg) { + QualType Type; + if (const auto *TVReg = Reg->getAs()) { + Type = TVReg->getValueType(); + } else if (const auto *SymReg = Reg->getAs()) { + Type = SymReg->getSymbol()->getType(); + } else { + return nullptr; + } + + if (const auto *RefT = Type->getAs()) { + Type = RefT->getPointeeType(); + } + + return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); +} + const RegionOrSymbol getRegionOrSymbol(const SVal &Val) { if (const auto Reg = Val.getAsRegion()) { return Reg; @@ -1423,6 +1702,18 @@ return processIteratorPositions(State, MatchCont, Invalidate); } +ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, + SymbolRef Offset, + BinaryOperator::Opcode Opc) { + auto Compare = [&](const IteratorPosition &Pos) { + return compare(State, Pos.getOffset(), Offset, Opc); + }; + auto Invalidate = [&](const IteratorPosition &Pos) { + return Pos.invalidate(); + }; + return processIteratorPositions(State, Compare, Invalidate); +} + ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, const MemRegion *Cont, const MemRegion *NewCont) { 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 @@ -265,6 +265,8 @@ void push_back(const T &value); void push_back(T &&value); + template + void emplace_back(Args&&... args); void pop_back(); T &operator[](size_t n) { @@ -317,6 +319,18 @@ void clear(); + void push_back(const T &value); + void push_back(T &&value); + template + void emplace_back(Args&&... args); + void pop_back(); + + void push_front(const T &value); + void push_front(T &&value); + template + void emplace_front(Args&&... args); + void pop_front(); + iterator begin() { return iterator(_start); } const_iterator begin() const { return const_iterator(_start); } const_iterator cbegin() const { return const_iterator(_start); } @@ -365,10 +379,14 @@ void push_back(const T &value); void push_back(T &&value); + template + void emplace_back(Args&&... args); void pop_back(); void push_front(const T &value); void push_front(T &&value); + template + void emplace_front(Args&&... args); void pop_front(); T &operator[](size_t n) { @@ -423,6 +441,8 @@ void push_front(const T &value); void push_front(T &&value); + template + void emplace_front(Args&&... args); void pop_front(); iterator begin() { return iterator(_start); } 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:546 {{Called C++ object pointer is null}} + // expected-warning@../Inputs/system-header-simulator-cxx.h:566 {{Called C++ object pointer is null}} #endif } Index: test/Analysis/invalidated-iterator.cpp =================================================================== --- test/Analysis/invalidated-iterator.cpp +++ test/Analysis/invalidated-iterator.cpp @@ -30,3 +30,170 @@ FL1 = FL2; *i0; // expected-warning{{Invalidated iterator accessed}} } + +void good_push_back_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.push_back(n); + *i0; // no-warning + --i1; // no-warning +} + +void good_push_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.push_back(n); + *i0; // no-warning +} + +void bad_push_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.push_back(n); + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_push_back_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.push_back(n); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_emplace_back_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.emplace_back(n); + *i0; // no-warning + --i1; // no-warning +} + +void good_emplace_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.emplace_back(n); + *i0; // no-warning +} + +void bad_emplace_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.emplace_back(n); + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_emplace_back_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.emplace_back(n); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_back_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(), i2 = i1--; + L.pop_back(); + *i0; // no-warning + *i2; // no-warning +} + +void bad_pop_back_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(), i2 = i1--; + L.pop_back(); + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--; + V.pop_back(); + *i0; // no-warning +} + +void bad_pop_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--; + V.pop_back(); + *i1; // expected-warning{{Invalidated iterator accessed}} + --i2; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_back_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--; + D.pop_back(); + *i0; // no-warning +} + +void bad_pop_back_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--; + D.pop_back(); + *i1; // expected-warning{{Invalidated iterator accessed}} + --i2; // expected-warning{{Invalidated iterator accessed}} +} + +void good_push_front_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.push_front(n); + *i0; // no-warning + --i1; // no-warning +} + +void bad_push_front_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.push_front(n); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_push_front_forward_list1(std::forward_list &FL, int n) { + auto i0 = FL.cbegin(), i1 = FL.cend(); + FL.push_front(n); + *i0; // no-warning +} + +void good_emplace_front_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.emplace_front(n); + *i0; // no-warning + --i1; // no-warning +} + +void bad_emplace_front_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.emplace_front(n); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_emplace_front_forward_list1(std::forward_list &FL, int n) { + auto i0 = FL.cbegin(), i1 = FL.cend(); + FL.emplace_front(n); + *i0; // no-warning +} + +void good_pop_front_list1(std::list &L, int n) { + auto i1 = L.cbegin(), i0 = i1++; + L.pop_front(); + *i1; // no-warning +} + +void bad_pop_front_list1(std::list &L, int n) { + auto i1 = L.cbegin(), i0 = i1++; + L.pop_front(); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_front_deque1(std::deque &D, int n) { + auto i1 = D.cbegin(), i0 = i1++; + D.pop_front(); + *i1; // no-warning +} + +void bad_pop_front_deque1(std::deque &D, int n) { + auto i1 = D.cbegin(), i0 = i1++; + D.pop_front(); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_front_forward_list1(std::forward_list &FL, int n) { + auto i1 = FL.cbegin(), i0 = i1++; + FL.pop_front(); + *i1; // no-warning +} + +void bad_pop_front_forward_list1(std::forward_list &FL, int n) { + auto i1 = FL.cbegin(), i0 = i1++; + FL.pop_front(); + *i0; // expected-warning{{Invalidated iterator accessed}} +} Index: test/Analysis/iterator-range.cpp =================================================================== --- test/Analysis/iterator-range.cpp +++ test/Analysis/iterator-range.cpp @@ -97,8 +97,66 @@ } } +void good_push_back(std::list &L, int n) { + auto i0 = --L.cend(); + L.push_back(n); + *++i0; // no-warning +} + +void bad_push_back(std::list &L, int n) { + auto i0 = --L.cend(); + L.push_back(n); + ++i0; + *++i0; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_pop_back(std::list &L, int n) { + auto i0 = --L.cend(); --i0; + L.pop_back(); + *i0; // no-warning +} + +void bad_pop_back(std::list &L, int n) { + auto i0 = --L.cend(); --i0; + L.pop_back(); + *++i0; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_push_front(std::list &L, int n) { + auto i0 = L.cbegin(); + L.push_front(n); + *--i0; // no-warning +} + +void bad_push_front(std::list &L, int n) { + auto i0 = L.cbegin(); + L.push_front(n); + --i0; + *--i0; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_pop_front(std::list &L, int n) { + auto i0 = ++L.cbegin(); + L.pop_front(); + *i0; // no-warning +} + +void bad_pop_front(std::list &L, int n) { + auto i0 = ++L.cbegin(); + L.pop_front(); + *--i0; // expected-warning{{Iterator accessed outside of its range}} +} + void bad_move(std::list &L1, std::list &L2) { auto i0 = --L2.cend(); L1 = std::move(L2); *++i0; // expected-warning{{Iterator accessed outside of its range}} } + +void bad_move_push_back(std::list &L1, std::list &L2, int n) { + auto i0 = --L2.cend(); + L2.push_back(n); + L1 = std::move(L2); + ++i0; + *++i0; // expected-warning{{Iterator accessed outside of its range}} +}