Index: cfe/trunk/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- cfe/trunk/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ cfe/trunk/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -72,6 +72,7 @@ #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h" #include @@ -225,6 +226,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; @@ -282,6 +287,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); @@ -289,6 +300,9 @@ bool isIncrementOperator(OverloadedOperatorKind OK); bool isDecrementOperator(OverloadedOperatorKind OK); bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); +bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg); +bool frontModifiable(ProgramStateRef State, const MemRegion *Reg); +bool backModifiable(ProgramStateRef State, const MemRegion *Reg); BinaryOperator::Opcode getOpcode(const SymExpr *SE); const RegionOrSymbol getRegionOrSymbol(const SVal &Val); const ProgramStateRef processComparison(ProgramStateRef State, @@ -325,6 +339,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); @@ -561,6 +578,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; @@ -653,9 +682,13 @@ const auto CData = Cont.second; if (CData.getBegin()) { SR.markLive(CData.getBegin()); + if(const auto *SIE = dyn_cast(CData.getBegin())) + SR.markLive(SIE->getLHS()); } if (CData.getEnd()) { SR.markLive(CData.getEnd()); + if(const auto *SIE = dyn_cast(CData.getEnd())) + SR.markLive(SIE->getLHS()); } } } @@ -1128,6 +1161,156 @@ 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(State, ContReg) && frontModifiable(State, 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(State, ContReg)) { + State = invalidateIteratorPositions(State, EndSym, BO_GE); + } + auto &SymMgr = C.getSymbolManager(); + auto &BVF = SymMgr.getBasicVals(); + auto &SVB = C.getSValBuilder(); + const auto newEndSym = + SVB.evalBinOp(State, BO_Add, + nonloc::SymbolVal(EndSym), + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), + SymMgr.getType(EndSym)).getAsSymbol(); + 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(); + auto &BVF = SymMgr.getBasicVals(); + auto &SVB = C.getSValBuilder(); + const auto BackSym = + SVB.evalBinOp(State, BO_Sub, + nonloc::SymbolVal(EndSym), + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), + SymMgr.getType(EndSym)).getAsSymbol(); + // 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(State, ContReg) && + backModifiable(State, 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(State, 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(); + auto &BVF = SymMgr.getBasicVals(); + auto &SVB = C.getSValBuilder(); + const auto newBeginSym = + SVB.evalBinOp(State, BO_Sub, + nonloc::SymbolVal(BeginSym), + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), + SymMgr.getType(BeginSym)).getAsSymbol(); + 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(State, ContReg)) { + State = invalidateIteratorPositions(State, BeginSym, BO_LE); + } else { + State = invalidateIteratorPositions(State, BeginSym, BO_EQ); + } + auto &SymMgr = C.getSymbolManager(); + auto &BVF = SymMgr.getBasicVals(); + auto &SVB = C.getSValBuilder(); + const auto newBeginSym = + SVB.evalBinOp(State, BO_Add, + nonloc::SymbolVal(BeginSym), + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), + SymMgr.getType(BeginSym)).getAsSymbol(); + State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); + C.addTransition(State); + } +} + void IteratorChecker::reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const { @@ -1172,6 +1355,8 @@ BinaryOperator::Opcode Opc); bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, BinaryOperator::Opcode Opc); +const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, + const MemRegion *Reg); SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr, SymbolRef OldSym, SymbolRef NewSym); @@ -1246,6 +1431,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) { @@ -1292,6 +1531,66 @@ return BO_Comma; // Extremal value, neither EQ nor NE } +bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(State, 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(ProgramStateRef State, const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(State, 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(ProgramStateRef State, const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(State, 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(ProgramStateRef State, + const MemRegion *Reg) { + auto TI = getDynamicTypeInfo(State, Reg); + if (!TI.isValid()) + return nullptr; + + auto Type = TI.getType(); + 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; @@ -1562,6 +1861,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) { @@ -1670,6 +1981,7 @@ return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); } + bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, BinaryOperator::Opcode Opc) { auto &SVB = State->getStateManager().getSValBuilder(); Index: cfe/trunk/test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- cfe/trunk/test/Analysis/Inputs/system-header-simulator-cxx.h +++ cfe/trunk/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) { @@ -319,10 +321,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(); iterator begin() { return iterator(_start); } @@ -373,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) { @@ -431,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: cfe/trunk/test/Analysis/diagnostics/explicit-suppression.cpp =================================================================== --- cfe/trunk/test/Analysis/diagnostics/explicit-suppression.cpp +++ cfe/trunk/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:554 {{Called C++ object pointer is null}} + // expected-warning@../Inputs/system-header-simulator-cxx.h:566 {{Called C++ object pointer is null}} #endif } Index: cfe/trunk/test/Analysis/invalidated-iterator.cpp =================================================================== --- cfe/trunk/test/Analysis/invalidated-iterator.cpp +++ cfe/trunk/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: cfe/trunk/test/Analysis/iterator-range.cpp =================================================================== --- cfe/trunk/test/Analysis/iterator-range.cpp +++ cfe/trunk/test/Analysis/iterator-range.cpp @@ -115,8 +115,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}} +}