Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -114,6 +114,10 @@ return IteratorPosition(Cont, Valid, NewOf); } + IteratorPosition reAssign(const MemRegion *NewCont) const { + return IteratorPosition(NewCont, Valid, Offset); + } + bool operator==(const IteratorPosition &X) const { return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset; } @@ -219,7 +223,9 @@ 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 handleAssign(CheckerContext &C, const SVal &Cont, + const Expr *CE = nullptr, + const SVal &OldCont = UndefinedVal()) const; void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, const SVal &RetVal, const SVal &LHS, const SVal &RHS) const; @@ -317,6 +323,17 @@ bool Equal); ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, const MemRegion *Cont); +ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont, + const MemRegion *NewCont); +ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, + const MemRegion *Cont, + const MemRegion *NewCont, + SymbolRef Offset, + BinaryOperator::Opcode Opc); +ProgramStateRef replaceSymbolInIteratorPositionsIf( + ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, + SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc); const ContainerData *getContainerData(ProgramStateRef State, const MemRegion *Cont); ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, @@ -453,7 +470,12 @@ const auto Op = Func->getOverloadedOperator(); if (isAssignmentOperator(Op)) { const auto *InstCall = dyn_cast(&Call); - handleAssign(C, InstCall->getCXXThisVal()); + if (Func->getParamDecl(0)->getType()->isRValueReferenceType()) { + handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), + Call.getArgSVal(0)); + } else { + handleAssign(C, InstCall->getCXXThisVal()); + } } else if (isSimpleComparisonOperator(Op)) { if (const auto *InstCall = dyn_cast(&Call)) { handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(), @@ -502,9 +524,6 @@ return; auto State = C.getState(); - // Already bound to container? - if (getIteratorPosition(State, Call.getReturnValue())) - return; if (const auto *InstCall = dyn_cast(&Call)) { if (isBeginCall(Func)) { @@ -519,6 +538,10 @@ } } + // Already bound to container? + if (getIteratorPosition(State, Call.getReturnValue())) + return; + // Copy-like and move constructors if (isa(&Call) && Call.getNumArgs() == 1) { if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) { @@ -994,7 +1017,8 @@ C.addTransition(State); } -void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont) const { +void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont, + const Expr *CE, const SVal &OldCont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -1011,6 +1035,65 @@ State = invalidateAllIteratorPositions(State, ContReg); } + // In case of move, iterators of the old container (except the past-end + // iterators) remain valid but refer to the new container + if (!OldCont.isUndef()) { + const auto *OldContReg = OldCont.getAsRegion(); + if (OldContReg) { + while (const auto *CBOR = OldContReg->getAs()) { + OldContReg = CBOR->getSuperRegion(); + } + const auto OldCData = getContainerData(State, OldContReg); + if (OldCData) { + if (const auto OldEndSym = OldCData->getEnd()) { + // If we already assigned an "end" symbol to the old conainer, then + // first reassign all iterator positions to the new container which + // are not past the container (thus not greater or equal to the + // current "end" symbol. + State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg, + OldEndSym, BO_GE); + auto &SymMgr = C.getSymbolManager(); + auto &SVB = C.getSValBuilder(); + // Then generate and assign a new "end" symbol for the new container. + auto NewEndSym = + SymMgr.conjureSymbol(CE, C.getLocationContext(), + C.getASTContext().LongTy, C.blockCount()); + State = assumeNoOverflow(State, NewEndSym); + if (CData) { + State = setContainerData(State, ContReg, CData->newEnd(NewEndSym)); + } else { + State = setContainerData(State, ContReg, + ContainerData::fromEnd(NewEndSym)); + } + // Finally, replace the old "end" symbol in the already reassigned + // iterator positions with the new "end" symbol. + State = replaceSymbolInIteratorPositionsIf( + State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT); + } else { + // There was no "end" symbol assigned yet to the old container, + // so reassign all iterator positions to the new container. + State = reassignAllIteratorPositions(State, OldContReg, ContReg); + } + if (const auto OldBeginSym = OldCData->getBegin()) { + // If we already assigned a "begin" symbol to the old container, then + // assign it to the new container and remove it from the old one. + if (CData) { + State = + setContainerData(State, ContReg, CData->newBegin(OldBeginSym)); + } else { + State = setContainerData(State, ContReg, + ContainerData::fromBegin(OldBeginSym)); + } + State = + setContainerData(State, OldContReg, OldCData->newEnd(nullptr)); + } + } else { + // There was neither "begin" nor "end" symbol assigned yet to the old + // container, so reassign all iterator positions to the new container. + State = reassignAllIteratorPositions(State, OldContReg, ContReg); + } + } + } C.addTransition(State); } @@ -1048,6 +1131,8 @@ BinaryOperator::Opcode Opc); bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, BinaryOperator::Opcode Opc); +SymbolRef replaceSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr, + SymbolRef OldSym, SymbolRef NewSym); bool isIteratorType(const QualType &Type) { if (Type->isPointerType()) @@ -1387,6 +1472,62 @@ return processIteratorPositions(State, MatchCont, Invalidate); } +ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont, + const MemRegion *NewCont) { + auto MatchCont = [&](const IteratorPosition &Pos) { + return Pos.getContainer() == Cont; + }; + auto ReAssign = [&](const IteratorPosition &Pos) { + return Pos.reAssign(NewCont); + }; + return processIteratorPositions(State, MatchCont, ReAssign); +} + +ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, + const MemRegion *Cont, + const MemRegion *NewCont, + SymbolRef Offset, + BinaryOperator::Opcode Opc) { + auto MatchContAndCompare = [&](const IteratorPosition &Pos) { + return Pos.getContainer() == Cont && + !compare(State, Pos.getOffset(), Offset, Opc); + }; + auto ReAssign = [&](const IteratorPosition &Pos) { + return Pos.reAssign(NewCont); + }; + return processIteratorPositions(State, MatchContAndCompare, ReAssign); +} + +ProgramStateRef replaceSymbolInIteratorPositionsIf( + ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, + SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) { + auto LessThanEnd = [&](const IteratorPosition &Pos) { + return compare(State, Pos.getOffset(), CondSym, Opc); + }; + auto ReplaceSymbol = [&](const IteratorPosition &Pos) { + return Pos.setTo(replaceSymbol(State, SVB, Pos.getOffset(), OldSym, + NewSym)); + }; + return processIteratorPositions(State, LessThanEnd, ReplaceSymbol); +} + +SymbolRef replaceSymbol(ProgramStateRef State, SValBuilder &SVB, + SymbolRef OrigExpr, SymbolRef OldExpr, + SymbolRef NewSym) { + auto &SymMgr = SVB.getSymbolManager(); + auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr), + nonloc::SymbolVal(OldExpr), + SymMgr.getType(OrigExpr)); + + const auto DiffInt = Diff.getAs(); + if (!DiffInt) + return OrigExpr; + + return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym), + SymMgr.getType(OrigExpr)).getAsSymbol(); +} + bool isZero(ProgramStateRef State, const NonLoc &Val) { auto &BVF = State->getBasicVals(); return compare(State, Val, Index: test/Analysis/mismatched-iterator.cpp =================================================================== --- test/Analysis/mismatched-iterator.cpp +++ test/Analysis/mismatched-iterator.cpp @@ -15,6 +15,25 @@ std::copy(v1.cbegin(), v1.cend(), v2.begin()); // no-warning } +void good_move_find1(std::vector &v1, std::vector &v2, int n) { + auto i0 = v2.cbegin(); + v1 = std::move(v2); + std::find(i0, v1.cend(), n); // no-warning +} + +void good_move_find2(std::vector &v1, std::vector &v2, int n) { + auto i0 = --v2.cend(); + v1 = std::move(v2); + std::find(i0, v1.cend(), n); // no-warning +} + +void good_move_find3(std::vector &v1, std::vector &v2, int n) { + auto i0 = v2.cend(); + v1 = std::move(v2); + v2.push_back(n); + std::find(v2.cbegin(), i0, n); // 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}} } @@ -23,3 +42,21 @@ 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}} } + +void bad_move_find1(std::vector &v1, std::vector &v2, int n) { + auto i0 = v2.cbegin(); + v1 = std::move(v2); + std::find(i0, v2.cend(), n); // expected-warning{{Iterator access mismatched}} +} + +void bad_move_find2(std::vector &v1, std::vector &v2, int n) { + auto i0 = --v2.cend(); + v1 = std::move(v2); + std::find(i0, v2.cend(), n); // expected-warning{{Iterator access mismatched}} +} + +void bad_move_find3(std::vector &v1, std::vector &v2, int n) { + auto i0 = v2.cend(); + v1 = std::move(v2); + std::find(v1.cbegin(), i0, n); // expected-warning{{Iterator access mismatched}} +}