Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -182,6 +182,8 @@ void handleComparison(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &LVal, const SVal &RVal, OverloadedOperatorKind Op) const; + void handleSize(CheckerContext &C, const Expr *CE, const SVal &Cont, + const SVal &RetVal) const; void processComparison(CheckerContext &C, ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal, OverloadedOperatorKind Op) const; @@ -272,6 +274,7 @@ bool isIteratorType(const QualType &Type); bool isIterator(const CXXRecordDecl *CRD); +bool isContainerType(const QualType &Type); bool isComparisonOperator(OverloadedOperatorKind OK); bool isBeginCall(const FunctionDecl *Func); bool isEndCall(const FunctionDecl *Func); @@ -287,6 +290,7 @@ bool isEraseCall(const FunctionDecl *Func); bool isEraseAfterCall(const FunctionDecl *Func); bool isEmplaceCall(const FunctionDecl *Func); +bool isSizeCall(const FunctionDecl *Func); bool isAssignmentOperator(OverloadedOperatorKind OK); bool isSimpleComparisonOperator(OverloadedOperatorKind OK); bool isAccessOperator(OverloadedOperatorKind OK); @@ -314,6 +318,8 @@ ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val); ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale); +const llvm::APSInt* calculateSize(ProgramStateRef State, SymbolRef Begin, + SymbolRef End); ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, const MemRegion *Cont); ProgramStateRef @@ -691,6 +697,16 @@ if (!OrigExpr) return; + if (const auto *InstCall = dyn_cast(&Call)) { + if (isContainerType(InstCall->getCXXThisExpr()->getType())) { + if (isSizeCall(Func)) { + handleSize(C, OrigExpr, InstCall->getCXXThisVal(), + Call.getReturnValue()); + return; + } + } + } + if (!isIteratorType(Call.getResultType())) return; @@ -918,6 +934,68 @@ } } +void IteratorChecker::handleSize(CheckerContext &C, const Expr *CE, + const SVal &Cont, const SVal &RetVal) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + ContReg = ContReg->getMostDerivedObjectRegion(); + + auto State = C.getState(); + + State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy, + C.getLocationContext(), C.blockCount()); + auto BeginSym = getContainerBegin(State, ContReg); + State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy, + C.getLocationContext(), C.blockCount()); + auto EndSym = getContainerEnd(State, ContReg); + const llvm::APSInt *CalcSize = calculateSize(State, BeginSym, EndSym); + + auto &SVB = C.getSValBuilder(); + auto &BVF = State->getBasicVals(); + const llvm::APSInt *RetSize = nullptr; + if (const auto *KnownSize = SVB.getKnownValue(State, RetVal)) { + RetSize = &BVF.Convert(C.getASTContext().LongTy, *KnownSize); + } + + if (RetSize) { + // If the return value is a concrete integer, then try to adjust the size + // of the container (the difference between its `begin()` and `end()` to + // this size. Function `relateSymbols()` returns null if it contradits + // the current size. + const auto CalcEnd = + SVB.evalBinOp(State, BO_Add, nonloc::SymbolVal(EndSym), + nonloc::ConcreteInt(*RetSize), C.getASTContext().LongTy) + .getAsSymbol(); + if (CalcEnd) { + State = relateSymbols(State, BeginSym, EndSym, true); + } + } else { + if (CalcSize) { + // If the current size is a concrete integer, bind this to the return + // value of the function instead of the current one. + auto CSize = nonloc::ConcreteInt(BVF.Convert(CE->getType(), *CalcSize)); + State = State->BindExpr(CE, C.getLocationContext(), CSize); + } else { + // If neither the returned nor the current size is a concrete integer, + // replace the return value with the symbolic difference of the + // container's `begin()` and `end()` symbols. + auto Size = SVB.evalBinOp(State, BO_Sub, nonloc::SymbolVal(EndSym), + nonloc::SymbolVal(BeginSym), + C.getASTContext().LongTy); + if (Size.isUnknown()) + return; + + auto CastedSize = SVB.evalCast(Size, CE->getType(), + C.getASTContext().LongTy); + State = State->BindExpr(CE, C.getLocationContext(), CastedSize); + } + } + + C.addTransition(State); +} + void IteratorChecker::verifyDereference(CheckerContext &C, const SVal &Val) const { auto State = C.getState(); @@ -1622,6 +1700,7 @@ namespace { +bool isContainer(const CXXRecordDecl *CRD); bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); @@ -1686,6 +1765,39 @@ HasPostIncrOp && HasDerefOp; } +bool isContainerType(const QualType &Type) { + if (isIteratorType(Type)) + return false; + + const auto *CRD = Type.getNonReferenceType() + ->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); + return isContainer(CRD); +} + +bool isContainer(const CXXRecordDecl *CRD) { + if (!CRD) + return false; + + for (const auto *Decl : CRD->decls()) { + const auto *TD = dyn_cast(Decl); + if (!TD) + continue; + + const auto *Type = TD->getTypeForDecl(); + if (!Type) + continue; + + const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); + if(!CRD) + continue; + + if (isIterator(CRD)) + return true; + } + + return false; +} + bool isComparisonOperator(OverloadedOperatorKind OK) { return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less || OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual; @@ -1827,6 +1939,17 @@ return IdInfo->getName() == "erase_after"; } +bool isSizeCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() > 0) + return false; + if (!Func->getReturnType()->isUnsignedIntegerType()) + return false; + return IdInfo->getName() == "size"; +} + bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { @@ -2127,6 +2250,40 @@ return NewState; } +const llvm::APSInt* calculateSize(ProgramStateRef State, SymbolRef Begin, + SymbolRef End) { + if (!Begin || !End) + return nullptr; + + auto &SVB = State->getStateManager().getSValBuilder(); + auto &SymMgr = State->getSymbolManager(); + auto Size = SVB.evalBinOp(State, BO_Sub, nonloc::SymbolVal(End), + nonloc::SymbolVal(Begin), + SymMgr.getType(End)).getAsSymbol(); + if (!Size) + return nullptr; + + llvm::APSInt Diff = llvm::APSInt::get(0); + if (const auto *SizeExpr = dyn_cast(Size)) { + assert(BinaryOperator::isAdditiveOp(SizeExpr->getOpcode()) && + "Symbolic positions must be additive expressions"); + if (SizeExpr->getOpcode() == BO_Add) { + Diff = SizeExpr->getRHS(); + } else { + Diff = -SizeExpr->getRHS(); + } + Size = SizeExpr->getLHS(); + } + + auto &CM = State->getConstraintManager(); + if (const auto *SizeInt = CM.getSymVal(State, Size)) { + auto &BVF = SymMgr.getBasicVals(); + return &BVF.getValue(Diff + *SizeInt); + } + + return nullptr; +} + template ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, Process Proc) { Index: test/Analysis/iterator-range.cpp =================================================================== --- test/Analysis/iterator-range.cpp +++ test/Analysis/iterator-range.cpp @@ -236,3 +236,19 @@ *i0; // no-warning } } + +void size0(const std::vector& V) { + if (V.size() != 0) + return; + + *V.begin(); // expected-warning{{Past-the-end iterator dereferenced}} +} + +void size1(const std::vector& V) { + if(V.size() != 1) + return; + *V.begin(); // no-warning + auto i = V.cbegin(); + ++i; + *i; // expected-warning{{Past-the-end iterator dereferenced}} +}