baloghadamsoftware created this revision.
If a container is moved by its move assignment operator, according to the
standard all their iterators except the past-end iterators remain valid but
refer to the new container. This patch introduces support for this case in the
iterator checkers.
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,23 @@
std::copy(v1.cbegin(), v1.cend(), v2.begin()); // no-warning
}
+void good_move_find(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 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_find(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}}
+}
Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
+++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
@@ -51,6 +51,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;
}
@@ -153,7 +157,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;
@@ -257,6 +263,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, SymbolManager &SymMgr, SymbolRef OldSym,
+ SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
const ContainerData *getContainerData(ProgramStateRef State,
const MemRegion *Cont);
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
@@ -386,7 +403,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(),
@@ -873,7 +895,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;
@@ -889,6 +912,51 @@
if (CData) {
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()) {
+ State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
+ OldEndSym, BO_GE);
+ auto &SymMgr = C.getSymbolManager();
+ auto NewEndSym =
+ SymMgr.conjureSymbol(CE, C.getLocationContext(),
+ C.getASTContext().LongTy, C.blockCount());
+ if (CData) {
+ State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
+ } else {
+ State = setContainerData(State, ContReg,
+ ContainerData::fromEnd(NewEndSym));
+ }
+ State = replaceSymbolInIteratorPositionsIf(
+ State, SymMgr, OldEndSym, NewEndSym, OldEndSym, BO_LT);
+ } else {
+ State = reassignAllIteratorPositions(State, OldContReg, ContReg);
+ }
+ if (const auto OldBeginSym = OldCData->getBegin()) {
+ 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 {
+ State = reassignAllIteratorPositions(State, OldContReg, ContReg);
+ }
+ }
+ }
C.addTransition(State);
}
@@ -925,6 +993,8 @@
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
BinaryOperator::Opcode Opc);
std::pair<SymbolRef, llvm::APSInt> decompose(const SymbolRef Sym);
+SymbolRef replaceSymbol(SymbolManager &SymMgr, SymbolRef Expr, SymbolRef OldSym,
+ SymbolRef NewSym);
bool isIteratorType(const QualType &Type) {
if (Type->isPointerType())
@@ -1276,6 +1346,45 @@
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, SymbolManager &SymMgr, 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(SymMgr, Pos.getOffset(), OldSym, NewSym));
+ };
+ return processIteratorPositions(State, LessThanEnd, ReplaceSymbol);
+}
+
bool isZero(ProgramStateRef State, const NonLoc &Val) {
return compareToZero(State, Val, BO_EQ);
}
@@ -1377,6 +1486,30 @@
return BVF.evalAPSInt(Opc, Int1, Int2)->getExtValue();
}
+SymbolRef replaceSymbol(SymbolManager &SymMgr, SymbolRef OrigExpr,
+ SymbolRef OldExpr, SymbolRef NewSym) {
+ // We have a symbolic expression in the format of A+n, where we want to
+ // replace A+m with B, so the result becomes B+k, where k==n-m.
+ SymbolRef OrigSym, OldSym;
+ llvm::APSInt OrigInt, OldInt;
+ std::tie(OrigSym, OrigInt) = decompose(OrigExpr);
+ std::tie(OldSym, OldInt) = decompose(OldExpr);
+ if (OrigSym == OldSym) {
+ auto NewInt = OrigInt - OldInt;
+ if (NewInt == 0) {
+ return NewSym;
+ } else {
+ auto OpCode = (NewInt > 0) ? BO_Add : BO_Sub;
+ auto &BVF = SymMgr.getBasicVals();
+ auto &AbsInt =
+ (NewInt > 0) ? BVF.getValue(NewInt) : BVF.getValue(-NewInt);
+ return SymMgr.getSymIntExpr(NewSym, OpCode, AbsInt, OrigExpr->getType());
+ }
+ } else {
+ return OrigExpr;
+ }
+}
+
SymbolRef compact(SymbolManager &SymMgr, const SymbolRef Sym) {
// Turn A+m+n into A+k, where k=m+n
if (const auto *Expr = dyn_cast<SymIntExpr>(Sym)) {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
