baloghadamsoftware created this revision.
baloghadamsoftware added a reviewer: NoQ.
baloghadamsoftware added a project: clang.
Herald added subscribers: donat.nagy, Szelethus, mikhail.ramalho, a.sidorin,
rnkovacs, szepet, whisperity.
Herald added a reviewer: george.karpenkov.
Currently iterator checkers record comparison of iterator positions and process
them for keeping track the distance between them (e.g. whether a position is
the same as the end position). However this makes some processing unnecessarily
complex and it is not needed at all: we only need to keep track between the
abstract symbols stored in these iterator positions. This patch changes this
and opens the path to comparisons to the `begin()` and `end()` symbols between
the container (e.g. size, emptiness) which are stored as symbols, not iterator
positions. The functionality of the checker is unchanged.
Repository:
rC Clang
https://reviews.llvm.org/D53701
Files:
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
===================================================================
--- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
+++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
@@ -134,8 +134,6 @@
}
};
-typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
-
// Structure to record the symbolic begin and end position of a container
struct ContainerData {
private:
@@ -173,27 +171,31 @@
}
};
-// Structure fo recording iterator comparisons. We needed to retrieve the
-// original comparison expression in assumptions.
-struct IteratorComparison {
+// Structure fo recording symbol comparisons. We need to retrieve the original
+// comparison expression in assumptions.
+struct SymbolComparison {
private:
- RegionOrSymbol Left, Right;
+ SymbolRef Left, Right;
bool Equality;
public:
- IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
+ SymbolComparison(SymbolRef L, SymbolRef R, bool Eq)
: Left(L), Right(R), Equality(Eq) {}
- RegionOrSymbol getLeft() const { return Left; }
- RegionOrSymbol getRight() const { return Right; }
+ SymbolRef getLeft() const { return Left; }
+ SymbolRef getRight() const { return Right; }
bool isEquality() const { return Equality; }
- bool operator==(const IteratorComparison &X) const {
+ bool operator==(const SymbolComparison &X) const {
return Left == X.Left && Right == X.Right && Equality == X.Equality;
}
- bool operator!=(const IteratorComparison &X) const {
+ bool operator!=(const SymbolComparison &X) const {
return Left != X.Left || Right != X.Right || Equality != X.Equality;
}
- void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
+ void Profile(llvm::FoldingSetNodeID &ID) const {
+ ID.Add(Left);
+ ID.Add(Right);
+ ID.AddInteger(Equality);
+ }
};
class IteratorChecker
@@ -206,8 +208,12 @@
std::unique_ptr<BugType> MismatchedBugType;
std::unique_ptr<BugType> InvalidatedBugType;
- void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
- const SVal &RVal, OverloadedOperatorKind Op) const;
+ void handleComparison(CheckerContext &C, const Expr *CE, const SVal &RetVal,
+ const SVal &LVal, const SVal &RVal,
+ OverloadedOperatorKind Op) const;
+ void processComparison(CheckerContext &C, ProgramStateRef State,
+ SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
+ OverloadedOperatorKind Op) const;
void verifyAccess(CheckerContext &C, const SVal &Val) const;
void verifyDereference(CheckerContext &C, const SVal &Val) const;
void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
@@ -290,8 +296,8 @@
REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
-REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
- IteratorComparison)
+REGISTER_MAP_WITH_PROGRAMSTATE(SymbolComparisonMap, const SymExpr *,
+ SymbolComparison)
namespace {
@@ -323,15 +329,10 @@
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,
- RegionOrSymbol LVal,
- RegionOrSymbol RVal, bool Equal);
-const ProgramStateRef saveComparison(ProgramStateRef State,
- const SymExpr *Condition, const SVal &LVal,
- const SVal &RVal, bool Eq);
-const IteratorComparison *loadComparison(ProgramStateRef State,
- const SymExpr *Condition);
+const ProgramStateRef saveComparison(ProgramStateRef State, SymbolRef Condition,
+ SymbolRef LSym, SymbolRef RSym, bool Eq);
+const SymbolComparison *loadComparison(ProgramStateRef State,
+ const SymExpr *Condition);
SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
ProgramStateRef createContainerBegin(ProgramStateRef State,
@@ -341,21 +342,9 @@
const SymbolRef Sym);
const IteratorPosition *getIteratorPosition(ProgramStateRef State,
const SVal &Val);
-const IteratorPosition *getIteratorPosition(ProgramStateRef State,
- RegionOrSymbol RegOrSym);
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
const IteratorPosition &Pos);
-ProgramStateRef setIteratorPosition(ProgramStateRef State,
- RegionOrSymbol RegOrSym,
- const IteratorPosition &Pos);
ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
-ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
- RegionOrSymbol RegOrSym,
- const IteratorPosition &Pos, bool Equal);
-ProgramStateRef relateIteratorPositions(ProgramStateRef State,
- const IteratorPosition &Pos1,
- const IteratorPosition &Pos2,
- bool Equal);
ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
const MemRegion *Cont);
ProgramStateRef
@@ -381,6 +370,8 @@
ProgramStateRef rebaseSymbolInIteratorPositionsIf(
ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
+ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
+ SymbolRef Sym2, bool Equal);
const ContainerData *getContainerData(ProgramStateRef State,
const MemRegion *Cont);
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
@@ -594,11 +585,15 @@
handleAssign(C, InstCall->getCXXThisVal());
}
} else if (isSimpleComparisonOperator(Op)) {
+ const auto *OrigExpr = Call.getOriginExpr();
+ if (!OrigExpr)
+ return;
+
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
- handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
- Call.getArgSVal(0), Op);
+ handleComparison(C, OrigExpr, Call.getReturnValue(),
+ InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
} else {
- handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
+ handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
Call.getArgSVal(1), Op);
}
} else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
@@ -817,10 +812,10 @@
}
}
- auto ComparisonMap = State->get<IteratorComparisonMap>();
+ auto ComparisonMap = State->get<SymbolComparisonMap>();
for (const auto Comp : ComparisonMap) {
if (!SR.isLive(Comp.first)) {
- State = State->remove<IteratorComparisonMap>(Comp.first);
+ State = State->remove<SymbolComparisonMap>(Comp.first);
}
}
@@ -861,29 +856,54 @@
return State;
}
- return processComparison(State, Comp->getLeft(), Comp->getRight(),
- (Comp->isEquality() == Assumption) != Negated);
+ return relateSymbols(State, Comp->getLeft(), Comp->getRight(),
+ (Comp->isEquality() == Assumption) != Negated);
}
-void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
- const SVal &LVal, const SVal &RVal,
+void IteratorChecker::handleComparison(CheckerContext &C, const Expr *CE,
+ const SVal &RetVal, const SVal &LVal,
+ const SVal &RVal,
OverloadedOperatorKind Op) const {
// Record the operands and the operator of the comparison for the next
// evalAssume, if the result is a symbolic expression. If it is a concrete
// value (only one branch is possible), then transfer the state between
// the operands according to the operator and the result
- auto State = C.getState();
- if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
- const auto *LPos = getIteratorPosition(State, LVal);
- const auto *RPos = getIteratorPosition(State, RVal);
- if (!LPos && !RPos)
+ auto State = C.getState();
+ const auto *LPos = getIteratorPosition(State, LVal);
+ const auto *RPos = getIteratorPosition(State, RVal);
+ const MemRegion *Cont = nullptr;
+ if (LPos) {
+ Cont = LPos->getContainer();
+ } else if (RPos) {
+ Cont = RPos->getContainer();
+ }
+ if (!Cont)
+ return;
+
+ if (!LPos) {
+ assignToContainer(C, CE, LVal, Cont);
+ if (!(LPos = getIteratorPosition(State, LVal)))
+ return;
+ } else if (!RPos) {
+ assignToContainer(C, CE, RVal, Cont);
+ if (!(RPos = getIteratorPosition(State, RVal)))
return;
- State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
+ }
+
+ processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
+}
+
+void IteratorChecker::processComparison(CheckerContext &C,
+ ProgramStateRef State, SymbolRef Sym1,
+ SymbolRef Sym2, const SVal &RetVal,
+ OverloadedOperatorKind Op) const {
+ if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
+ State = saveComparison(State, Condition, Sym1, Sym2, Op == OO_EqualEqual);
C.addTransition(State);
} else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
- if ((State = processComparison(
- State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
- (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
+ if (State = relateSymbols(State, Sym1, Sym2,
+ (Op == OO_EqualEqual) ==
+ (TruthVal->getValue() != 0))) {
C.addTransition(State);
} else {
C.generateSink(State, C.getPredecessor());
@@ -1914,46 +1934,15 @@
return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
}
-const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
- if (const auto Reg = Val.getAsRegion()) {
- return Reg;
- } else if (const auto Sym = Val.getAsSymbol()) {
- return Sym;
- } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
- return LCVal->getRegion();
- }
- return RegionOrSymbol();
-}
-
-const ProgramStateRef processComparison(ProgramStateRef State,
- RegionOrSymbol LVal,
- RegionOrSymbol RVal, bool Equal) {
- const auto *LPos = getIteratorPosition(State, LVal);
- const auto *RPos = getIteratorPosition(State, RVal);
- if (LPos && !RPos) {
- State = adjustIteratorPosition(State, RVal, *LPos, Equal);
- } else if (!LPos && RPos) {
- State = adjustIteratorPosition(State, LVal, *RPos, Equal);
- } else if (LPos && RPos) {
- State = relateIteratorPositions(State, *LPos, *RPos, Equal);
- }
- return State;
+const ProgramStateRef saveComparison(ProgramStateRef State, SymbolRef Condition,
+ SymbolRef LSym, SymbolRef RSym, bool Eq) {
+ return State->set<SymbolComparisonMap>(Condition,
+ SymbolComparison(LSym, RSym, Eq));
}
-const ProgramStateRef saveComparison(ProgramStateRef State,
- const SymExpr *Condition, const SVal &LVal,
- const SVal &RVal, bool Eq) {
- const auto Left = getRegionOrSymbol(LVal);
- const auto Right = getRegionOrSymbol(RVal);
- if (!Left || !Right)
- return State;
- return State->set<IteratorComparisonMap>(Condition,
- IteratorComparison(Left, Right, Eq));
-}
-
-const IteratorComparison *loadComparison(ProgramStateRef State,
- const SymExpr *Condition) {
- return State->get<IteratorComparisonMap>(Condition);
+const SymbolComparison *loadComparison(ProgramStateRef State,
+ SymbolRef Condition) {
+ return State->get<SymbolComparisonMap>(Condition);
}
SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
@@ -2025,16 +2014,6 @@
return nullptr;
}
-const IteratorPosition *getIteratorPosition(ProgramStateRef State,
- RegionOrSymbol RegOrSym) {
- if (RegOrSym.is<const MemRegion *>()) {
- return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
- } else if (RegOrSym.is<SymbolRef>()) {
- return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
- }
- return nullptr;
-}
-
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
const IteratorPosition &Pos) {
if (const auto Reg = Val.getAsRegion()) {
@@ -2047,18 +2026,6 @@
return nullptr;
}
-ProgramStateRef setIteratorPosition(ProgramStateRef State,
- RegionOrSymbol RegOrSym,
- const IteratorPosition &Pos) {
- if (RegOrSym.is<const MemRegion *>()) {
- return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
- Pos);
- } else if (RegOrSym.is<SymbolRef>()) {
- return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
- }
- return nullptr;
-}
-
ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
if (const auto Reg = Val.getAsRegion()) {
return State->remove<IteratorRegionMap>(Reg);
@@ -2070,37 +2037,26 @@
return nullptr;
}
-ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
- RegionOrSymbol RegOrSym,
- const IteratorPosition &Pos,
- bool Equal) {
- if (Equal) {
- return setIteratorPosition(State, RegOrSym, Pos);
- } else {
- return State;
- }
-}
-
-ProgramStateRef relateIteratorPositions(ProgramStateRef State,
- const IteratorPosition &Pos1,
- const IteratorPosition &Pos2,
- bool Equal) {
+ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
+ SymbolRef Sym2, bool Equal) {
auto &SVB = State->getStateManager().getSValBuilder();
// FIXME: This code should be reworked as follows:
// 1. Subtract the operands using evalBinOp().
// 2. Assume that the result doesn't overflow.
// 3. Compare the result to 0.
// 4. Assume the result of the comparison.
const auto comparison =
- SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
- nonloc::SymbolVal(Pos2.getOffset()),
- SVB.getConditionType());
+ SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
+ nonloc::SymbolVal(Sym2), SVB.getConditionType());
assert(comparison.getAs<DefinedSVal>() &&
"Symbol comparison must be a `DefinedSVal`");
auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
+ if (!NewState)
+ return nullptr;
+
if (const auto CompSym = comparison.getAsSymbol()) {
assert(isa<SymIntExpr>(CompSym) &&
"Symbol comparison must be a `SymIntExpr`");
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
