80 using namespace clang;
82 using namespace iterator;
86 class IteratorModeling
87 :
public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
88 check::PostStmt<BinaryOperator>,
89 check::PostStmt<MaterializeTemporaryExpr>,
90 check::Bind, check::LiveSymbols, check::DeadSymbols> {
92 using AdvanceFn = void (IteratorModeling::*)(CheckerContext &,
const Expr *,
93 SVal, SVal, SVal)
const;
95 void handleOverloadedOperator(CheckerContext &C,
const CallEvent &Call,
97 void handleAdvanceLikeFunction(CheckerContext &C,
const CallEvent &Call,
99 const AdvanceFn *Handler)
const;
101 void handleComparison(CheckerContext &C,
const Expr *CE, SVal RetVal,
102 const SVal &LVal,
const SVal &RVal,
107 void handleIncrement(CheckerContext &C,
const SVal &RetVal,
const SVal &Iter,
109 void handleDecrement(CheckerContext &C,
const SVal &RetVal,
const SVal &Iter,
111 void handleRandomIncrOrDecr(CheckerContext &C,
const Expr *CE,
113 const SVal &Iterator,
const SVal &Amount)
const;
114 void handlePtrIncrOrDecr(CheckerContext &C,
const Expr *Iterator,
116 void handleAdvance(CheckerContext &C,
const Expr *CE, SVal RetVal, SVal Iter,
118 void handlePrev(CheckerContext &C,
const Expr *CE, SVal RetVal, SVal Iter,
120 void handleNext(CheckerContext &C,
const Expr *CE, SVal RetVal, SVal Iter,
122 void assignToContainer(CheckerContext &C,
const Expr *CE,
const SVal &RetVal,
123 const MemRegion *Cont)
const;
124 bool noChangeInAdvance(CheckerContext &C, SVal Iter,
const Expr *CE)
const;
126 const char *Sep)
const override;
129 CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {
132 {{{
"std",
"advance"}, 2}, &IteratorModeling::handleAdvance},
138 {{{
"std",
"prev"}, 2}, &IteratorModeling::handlePrev},
144 {{{
"std",
"next"}, 2}, &IteratorModeling::handleNext},
148 IteratorModeling() =
default;
150 void checkPostCall(
const CallEvent &Call, CheckerContext &C)
const;
151 void checkBind(SVal Loc, SVal Val,
const Stmt *S, CheckerContext &C)
const;
152 void checkPostStmt(
const UnaryOperator *UO, CheckerContext &C)
const;
153 void checkPostStmt(
const BinaryOperator *BO, CheckerContext &C)
const;
155 CheckerContext &C)
const;
157 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C)
const;
165 bool isBoundThroughLazyCompoundVal(
const Environment &Env,
166 const MemRegion *Reg);
167 const ExplodedNode *findCallEnter(
const ExplodedNode *
Node,
const Expr *Call);
171 void IteratorModeling::checkPostCall(
const CallEvent &Call,
172 CheckerContext &C)
const {
174 const auto *Func = dyn_cast_or_null<FunctionDecl>(
Call.getDecl());
178 if (Func->isOverloadedOperator()) {
179 const auto Op = Func->getOverloadedOperator();
180 handleOverloadedOperator(C, Call, Op);
184 const auto *OrigExpr =
Call.getOriginExpr();
188 const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(Call);
190 handleAdvanceLikeFunction(C, Call, OrigExpr, Handler);
197 auto State =
C.getState();
204 if (isa<CXXConstructorCall>(&Call) &&
Call.getNumArgs() == 1) {
207 if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
220 for (
unsigned i = 0; i <
Call.getNumArgs(); ++i) {
222 Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType(
223 C.getASTContext()).getTypePtr() ==
224 Call.getResultType().getDesugaredType(
C.getASTContext()).getTypePtr()) {
226 assignToContainer(C, OrigExpr,
Call.getReturnValue(),
227 Pos->getContainer());
234 void IteratorModeling::checkBind(SVal Loc, SVal Val,
const Stmt *S,
235 CheckerContext &C)
const {
236 auto State =
C.getState();
250 void IteratorModeling::checkPostStmt(
const UnaryOperator *UO,
251 CheckerContext &C)
const {
256 auto &SVB =
C.getSValBuilder();
259 SVB.makeArrayIndex(1));
263 CheckerContext &C)
const {
268 const SVal LVal =
State->getSVal(LHS,
C.getLocationContext());
269 const SVal RVal =
State->getSVal(RHS,
C.getLocationContext());
271 if (isSimpleComparisonOperator(BO->
getOpcode())) {
272 SVal Result =
State->getSVal(BO,
C.getLocationContext());
273 handleComparison(C, BO, Result, LVal, RVal,
279 const Expr *
const &IterExpr = IsIterOnLHS ? LHS : RHS;
280 const Expr *
const &AmountExpr = IsIterOnLHS ? RHS : LHS;
285 const SVal &AmountVal = IsIterOnLHS ? RVal : LVal;
292 CheckerContext &C)
const {
294 auto State =
C.getState();
303 SymbolReaper &SR)
const {
305 auto RegionMap =
State->get<IteratorRegionMap>();
306 for (
const auto &Reg : RegionMap) {
307 const auto Offset = Reg.second.getOffset();
308 for (
auto i =
Offset->symbol_begin(); i !=
Offset->symbol_end(); ++i)
309 if (isa<SymbolData>(*i))
313 auto SymbolMap =
State->get<IteratorSymbolMap>();
314 for (
const auto &Sym : SymbolMap) {
315 const auto Offset = Sym.second.getOffset();
316 for (
auto i =
Offset->symbol_begin(); i !=
Offset->symbol_end(); ++i)
317 if (isa<SymbolData>(*i))
323 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
324 CheckerContext &C)
const {
326 auto State =
C.getState();
328 auto RegionMap =
State->get<IteratorRegionMap>();
329 for (
const auto &Reg : RegionMap) {
330 if (!SR.isLiveRegion(Reg.first)) {
334 if (!isBoundThroughLazyCompoundVal(
State->getEnvironment(), Reg.first)) {
335 State =
State->remove<IteratorRegionMap>(Reg.first);
340 auto SymbolMap =
State->get<IteratorSymbolMap>();
341 for (
const auto &Sym : SymbolMap) {
342 if (!SR.isLive(Sym.first)) {
343 State =
State->remove<IteratorSymbolMap>(Sym.first);
351 IteratorModeling::handleOverloadedOperator(CheckerContext &C,
352 const CallEvent &Call,
354 if (isSimpleComparisonOperator(Op)) {
355 const auto *OrigExpr =
Call.getOriginExpr();
359 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
360 handleComparison(C, OrigExpr,
Call.getReturnValue(),
361 InstCall->getCXXThisVal(),
Call.getArgSVal(0), Op);
365 handleComparison(C, OrigExpr,
Call.getReturnValue(),
Call.getArgSVal(0),
366 Call.getArgSVal(1), Op);
369 const auto *OrigExpr =
Call.getOriginExpr();
373 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
374 if (
Call.getNumArgs() >= 1 &&
375 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
376 handleRandomIncrOrDecr(C, OrigExpr, Op,
Call.getReturnValue(),
377 InstCall->getCXXThisVal(),
Call.getArgSVal(0));
380 }
else if (
Call.getNumArgs() >= 2) {
381 const Expr *FirstArg =
Call.getArgExpr(0);
382 const Expr *SecondArg =
Call.getArgExpr(1);
391 const SVal FirstArg =
Call.getArgSVal(0);
392 const SVal SecondArg =
Call.getArgSVal(1);
393 const SVal &Iterator = IsIterFirst ? FirstArg : SecondArg;
394 const SVal &Amount = IsIterFirst ? SecondArg : FirstArg;
396 handleRandomIncrOrDecr(C, OrigExpr, Op,
Call.getReturnValue(),
402 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
403 handleIncrement(C,
Call.getReturnValue(), InstCall->getCXXThisVal(),
408 handleIncrement(C,
Call.getReturnValue(),
Call.getArgSVal(0),
412 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
413 handleDecrement(C,
Call.getReturnValue(), InstCall->getCXXThisVal(),
418 handleDecrement(C,
Call.getReturnValue(),
Call.getArgSVal(0),
425 IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,
426 const CallEvent &Call,
427 const Expr *OrigExpr,
428 const AdvanceFn *Handler)
const {
430 (this->**Handler)(C, OrigExpr,
Call.getReturnValue(),
431 Call.getArgSVal(0),
Call.getArgSVal(1));
437 const auto *IdInfo = cast<FunctionDecl>(
Call.getDecl())->getIdentifier();
439 if (IdInfo->getName() ==
"advance") {
440 if (noChangeInAdvance(C,
Call.getArgSVal(0), OrigExpr)) {
441 (this->**Handler)(C, OrigExpr,
Call.getReturnValue(),
442 Call.getArgSVal(0),
Call.getArgSVal(1));
448 void IteratorModeling::handleComparison(CheckerContext &C,
const Expr *CE,
449 SVal RetVal,
const SVal &LVal,
456 auto State =
C.getState();
459 const MemRegion *Cont =
nullptr;
461 Cont = LPos->getContainer();
463 Cont = RPos->getContainer();
471 if (!LPos || !RPos) {
472 auto &SymMgr =
C.getSymbolManager();
473 Sym = SymMgr.conjureSymbol(CE,
C.getLocationContext(),
474 C.getASTContext().LongTy,
C.blockCount());
496 if (RetVal.isUnknown()) {
497 auto &SymMgr =
C.getSymbolManager();
498 auto *LCtx =
C.getLocationContext();
499 RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
500 CE, LCtx,
C.getASTContext().BoolTy,
C.blockCount()));
504 processComparison(C,
State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
507 void IteratorModeling::processComparison(CheckerContext &C,
511 if (
const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
513 (Op == OO_EqualEqual) ==
514 (TruthVal->getValue() != 0)))) {
517 C.generateSink(
State,
C.getPredecessor());
522 const auto ConditionVal = RetVal.getAs<DefinedSVal>();
526 if (
auto StateTrue = relateSymbols(
State, Sym1, Sym2, Op == OO_EqualEqual)) {
527 StateTrue = StateTrue->assume(*ConditionVal,
true);
528 C.addTransition(StateTrue);
531 if (
auto StateFalse = relateSymbols(
State, Sym1, Sym2, Op != OO_EqualEqual)) {
532 StateFalse = StateFalse->assume(*ConditionVal,
false);
533 C.addTransition(StateFalse);
537 void IteratorModeling::handleIncrement(CheckerContext &C,
const SVal &RetVal,
538 const SVal &Iter,
bool Postfix)
const {
541 auto State =
C.getState();
542 auto &BVF =
C.getSymbolManager().getBasicVals();
550 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
552 "Advancing position by concrete int should always be successful");
556 "Iterator should have position after successful advancement");
563 void IteratorModeling::handleDecrement(CheckerContext &C,
const SVal &RetVal,
564 const SVal &Iter,
bool Postfix)
const {
567 auto State =
C.getState();
568 auto &BVF =
C.getSymbolManager().getBasicVals();
576 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
578 "Advancing position by concrete int should always be successful");
582 "Iterator should have position after successful advancement");
589 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C,
const Expr *CE,
592 const SVal &Iterator,
593 const SVal &Amount)
const {
596 auto State =
C.getState();
602 const auto *
Value = &Amount;
604 if (
auto LocAmount = Amount.getAs<Loc>()) {
605 Val =
State->getRawSVal(*LocAmount);
610 (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iterator : RetVal;
619 "Iterator should have position after successful advancement");
624 assignToContainer(C, CE, TgtVal, Pos->getContainer());
628 void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
629 const Expr *Iterator,
632 if (!isa<DefinedSVal>(
Offset))
641 SVal OldVal =
State->getSVal(Iterator,
C.getLocationContext());
648 if (OK == OO_Plus || OK == OO_PlusEqual) {
649 NewVal =
State->getLValue(ElementType,
Offset, OldVal);
651 auto &SVB =
C.getSValBuilder();
652 SVal NegatedOffset = SVB.evalMinus(
Offset.castAs<NonLoc>());
653 NewVal =
State->getLValue(ElementType, NegatedOffset, OldVal);
663 "Iterator should have position after successful advancement");
666 C.addTransition(NewState);
668 assignToContainer(C, Iterator, NewVal, OldPos->getContainer());
672 void IteratorModeling::handleAdvance(CheckerContext &C,
const Expr *CE,
673 SVal RetVal, SVal Iter,
675 handleRandomIncrOrDecr(C, CE, OO_PlusEqual, RetVal, Iter, Amount);
678 void IteratorModeling::handlePrev(CheckerContext &C,
const Expr *CE,
679 SVal RetVal, SVal Iter, SVal Amount)
const {
680 handleRandomIncrOrDecr(C, CE, OO_Minus, RetVal, Iter, Amount);
683 void IteratorModeling::handleNext(CheckerContext &C,
const Expr *CE,
684 SVal RetVal, SVal Iter, SVal Amount)
const {
685 handleRandomIncrOrDecr(C, CE, OO_Plus, RetVal, Iter, Amount);
688 void IteratorModeling::assignToContainer(CheckerContext &C,
const Expr *CE,
690 const MemRegion *Cont)
const {
691 Cont = Cont->getMostDerivedObjectRegion();
693 auto State =
C.getState();
694 const auto *LCtx =
C.getLocationContext();
700 bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,
701 const Expr *CE)
const {
704 const auto StateAfter =
C.getState();
713 const ExplodedNode *N = findCallEnter(
C.getPredecessor(), CE);
714 assert(N &&
"Any call should have a `CallEnter` node.");
716 const auto StateBefore = N->getState();
727 return PosBefore->getOffset() == PosAfter->getOffset();
731 const char *NL,
const char *Sep)
const {
732 auto SymbolMap =
State->get<IteratorSymbolMap>();
733 auto RegionMap =
State->get<IteratorRegionMap>();
737 if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
738 Out << Sep <<
"Iterator Positions :" << NL;
739 for (
const auto &Sym : SymbolMap) {
743 Sym.first->dumpToStream(Out);
745 const auto Pos = Sym.second;
746 Out << (Pos.isValid() ?
"Valid" :
"Invalid") <<
" ; Container == ";
747 Pos.getContainer()->dumpToStream(Out);
748 Out<<
" ; Offset == ";
749 Pos.getOffset()->dumpToStream(Out);
752 for (
const auto &Reg : RegionMap) {
756 Reg.first->dumpToStream(Out);
758 const auto Pos = Reg.second;
759 Out << (Pos.isValid() ?
"Valid" :
"Invalid") <<
" ; Container == ";
760 Pos.getContainer()->dumpToStream(Out);
761 Out<<
" ; Offset == ";
762 Pos.getOffset()->dumpToStream(Out);
770 return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
774 return OK == BO_EQ || OK == BO_NE;
778 if (
auto Reg = Val.getAsRegion()) {
779 Reg = Reg->getMostDerivedObjectRegion();
780 return State->remove<IteratorRegionMap>(Reg);
781 }
else if (
const auto Sym = Val.getAsSymbol()) {
782 return State->remove<IteratorSymbolMap>(Sym);
783 }
else if (
const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
784 return State->remove<IteratorRegionMap>(LCVal->getRegion());
791 auto &SVB =
State->getStateManager().getSValBuilder();
798 const auto comparison =
799 SVB.evalBinOp(
State, BO_EQ, nonloc::SymbolVal(Sym1),
800 nonloc::SymbolVal(Sym2), SVB.getConditionType());
802 assert(isa<DefinedSVal>(comparison) &&
803 "Symbol comparison must be a `DefinedSVal`");
805 auto NewState =
State->assume(comparison.castAs<DefinedSVal>(), Equal);
809 if (
const auto CompSym = comparison.getAsSymbol()) {
810 assert(isa<SymIntExpr>(CompSym) &&
811 "Symbol comparison must be a `SymIntExpr`");
813 cast<SymIntExpr>(CompSym)->getOpcode()) &&
814 "Symbol comparison must be a comparison");
821 bool isBoundThroughLazyCompoundVal(
const Environment &Env,
822 const MemRegion *Reg) {
823 for (
const auto &Binding : Env) {
824 if (
const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
825 if (LCVal->getRegion() == Reg)
833 const ExplodedNode *findCallEnter(
const ExplodedNode *
Node,
const Expr *Call) {
837 if (Enter->getCallExpr() == Call)
849 void ento::registerIteratorModeling(CheckerManager &mgr) {
850 mgr.registerChecker<IteratorModeling>();
853 bool ento::shouldRegisterIteratorModeling(
const CheckerManager &mgr) {