baloghadamsoftware updated this revision to Diff 144106.
baloghadamsoftware added a comment.
Herald added a reviewer: george.karpenkov.
One test failed after rebased to the current master branch. Depending on the
internal implementation of the iterator and the move operation of the container
it could happen that after moving a container the begin() or end() of the
target of the move returns an already existing iterator position to the source
of the move which is wrong. Therefore we must first check for begin() and end()
and only then check for the existence of the iterator position of the return
value of a function returning an iterator.
https://reviews.llvm.org/D32859
Files:
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
test/Analysis/mismatched-iterator.cpp
Index: test/Analysis/mismatched-iterator.cpp
===================================================================
--- test/Analysis/mismatched-iterator.cpp
+++ test/Analysis/mismatched-iterator.cpp
@@ -15,11 +15,48 @@
std::copy(v1.cbegin(), v1.cend(), v2.begin()); // no-warning
}
+void good_move_find1(std::vector<int> &v1, std::vector<int> &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<int> &v1, std::vector<int> &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<int> &v1, std::vector<int> &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<int> &v1, std::vector<int> &v2, int n) {
std::find(v1.cbegin(), v2.cend(), n); // expected-warning{{Iterator access mismatched}}
}
void bad_find_first_of(std::vector<int> &v1, std::vector<int> &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}}
}
+
+void bad_move_find1(std::vector<int> &v1, std::vector<int> &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<int> &v1, std::vector<int> &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<int> &v1, std::vector<int> &v2, int n) {
+ auto i0 = v2.cend();
+ v1 = std::move(v2);
+ std::find(v1.cbegin(), i0, n); // expected-warning{{Iterator access mismatched}}
+}
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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXConstructorCall>(&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<CXXBaseObjectRegion>()) {
+ 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<nonloc::ConcreteInt>();
+ 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,
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
