75#include "llvm/ADT/STLExtras.h"
83using namespace iterator;
88 :
public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
89 check::PostStmt<BinaryOperator>,
90 check::PostStmt<MaterializeTemporaryExpr>,
91 check::Bind, check::LiveSymbols, check::DeadSymbols> {
100 const AdvanceFn *Handler)
const;
114 const SVal &Iterator,
const SVal &Amount)
const;
127 const char *Sep)
const override;
133 {{{
"std",
"advance"}, 2}, &IteratorModeling::handleAdvance},
139 {{{
"std",
"prev"}, 2}, &IteratorModeling::handlePrev},
145 {{{
"std",
"next"}, 2}, &IteratorModeling::handleNext},
149 IteratorModeling() =
default;
175 const auto *
Func = dyn_cast_or_null<FunctionDecl>(
Call.getDecl());
179 if (
Func->isOverloadedOperator()) {
180 const auto Op =
Func->getOverloadedOperator();
181 handleOverloadedOperator(
C,
Call, Op);
185 const auto *OrigExpr =
Call.getOriginExpr();
189 const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(
Call);
191 handleAdvanceLikeFunction(
C,
Call, OrigExpr, Handler);
198 auto State =
C.getState();
205 if (isa<CXXConstructorCall>(&
Call) &&
Call.getNumArgs() == 1) {
208 if (cast<CXXConstructorDecl>(
Func)->isMoveConstructor()) {
209 State = removeIteratorPosition(State,
Call.getArgSVal(0));
211 C.addTransition(State);
221 for (
unsigned i = 0; i <
Call.getNumArgs(); ++i) {
223 Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType(
224 C.getASTContext()).getTypePtr() ==
225 Call.getResultType().getDesugaredType(
C.getASTContext()).getTypePtr()) {
227 assignToContainer(
C, OrigExpr,
Call.getReturnValue(),
228 Pos->getContainer());
237 auto State =
C.getState();
241 C.addTransition(State);
245 State = removeIteratorPosition(State,
Loc);
246 C.addTransition(State);
257 auto &SVB =
C.getSValBuilder();
260 SVB.makeArrayIndex(1));
269 const SVal LVal = State->getSVal(LHS,
C.getLocationContext());
270 const SVal RVal = State->getSVal(RHS,
C.getLocationContext());
272 if (isSimpleComparisonOperator(BO->
getOpcode())) {
273 SVal Result = State->getSVal(BO,
C.getLocationContext());
274 handleComparison(
C, BO, Result, LVal, RVal,
280 const Expr *
const &IterExpr = IsIterOnLHS ? LHS : RHS;
281 const Expr *
const &AmountExpr = IsIterOnLHS ? RHS : LHS;
286 const SVal &AmountVal = IsIterOnLHS ? RVal : LVal;
295 auto State =
C.getState();
300 C.addTransition(State);
309 if (isa<SymbolData>(Sym))
316 if (isa<SymbolData>(Sym))
321void IteratorModeling::checkDeadSymbols(
SymbolReaper &SR,
324 auto State =
C.getState();
327 for (
const auto &Reg : RegionMap) {
332 if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
339 for (
const auto &Sym : SymbolMap) {
340 if (!SR.
isLive(Sym.first)) {
345 C.addTransition(State);
352 if (isSimpleComparisonOperator(Op)) {
353 const auto *OrigExpr =
Call.getOriginExpr();
357 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
358 handleComparison(
C, OrigExpr,
Call.getReturnValue(),
359 InstCall->getCXXThisVal(),
Call.getArgSVal(0), Op);
363 handleComparison(
C, OrigExpr,
Call.getReturnValue(),
Call.getArgSVal(0),
364 Call.getArgSVal(1), Op);
367 const auto *OrigExpr =
Call.getOriginExpr();
371 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
372 if (
Call.getNumArgs() >= 1 &&
373 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
374 handleRandomIncrOrDecr(
C, OrigExpr, Op,
Call.getReturnValue(),
375 InstCall->getCXXThisVal(),
Call.getArgSVal(0));
378 }
else if (
Call.getNumArgs() >= 2) {
379 const Expr *FirstArg =
Call.getArgExpr(0);
380 const Expr *SecondArg =
Call.getArgExpr(1);
389 const SVal FirstArg =
Call.getArgSVal(0);
390 const SVal SecondArg =
Call.getArgSVal(1);
391 const SVal &Iterator = IsIterFirst ? FirstArg : SecondArg;
392 const SVal &Amount = IsIterFirst ? SecondArg : FirstArg;
394 handleRandomIncrOrDecr(
C, OrigExpr, Op,
Call.getReturnValue(),
400 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
401 handleIncrement(
C,
Call.getReturnValue(), InstCall->getCXXThisVal(),
406 handleIncrement(
C,
Call.getReturnValue(),
Call.getArgSVal(0),
410 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
411 handleDecrement(
C,
Call.getReturnValue(), InstCall->getCXXThisVal(),
416 handleDecrement(
C,
Call.getReturnValue(),
Call.getArgSVal(0),
425 const Expr *OrigExpr,
426 const AdvanceFn *Handler)
const {
428 (this->**Handler)(
C, OrigExpr,
Call.getReturnValue(),
429 Call.getArgSVal(0),
Call.getArgSVal(1));
435 const auto *IdInfo = cast<FunctionDecl>(
Call.getDecl())->getIdentifier();
437 if (IdInfo->getName() ==
"advance") {
438 if (noChangeInAdvance(
C,
Call.getArgSVal(0), OrigExpr)) {
439 (this->**Handler)(
C, OrigExpr,
Call.getReturnValue(),
440 Call.getArgSVal(0),
Call.getArgSVal(1));
454 auto State =
C.getState();
459 Cont = LPos->getContainer();
461 Cont = RPos->getContainer();
469 if (!LPos || !RPos) {
470 auto &SymMgr =
C.getSymbolManager();
471 Sym = SymMgr.conjureSymbol(CE,
C.getLocationContext(),
472 C.getASTContext().LongTy,
C.blockCount());
495 auto &SymMgr =
C.getSymbolManager();
496 auto *LCtx =
C.getLocationContext();
498 CE, LCtx,
C.getASTContext().BoolTy,
C.blockCount()));
499 State = State->BindExpr(CE, LCtx, RetVal);
502 processComparison(
C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
510 if ((State = relateSymbols(State, Sym1, Sym2,
511 (Op == OO_EqualEqual) ==
512 (TruthVal->getValue() != 0)))) {
513 C.addTransition(State);
515 C.generateSink(State,
C.getPredecessor());
524 if (
auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
525 StateTrue = StateTrue->assume(*ConditionVal,
true);
526 C.addTransition(StateTrue);
529 if (
auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
530 StateFalse = StateFalse->assume(*ConditionVal,
false);
531 C.addTransition(StateFalse);
536 const SVal &
Iter,
bool Postfix)
const {
539 auto State =
C.getState();
540 auto &BVF =
C.getSymbolManager().getBasicVals();
550 "Advancing position by concrete int should always be successful");
554 "Iterator should have position after successful advancement");
558 C.addTransition(State);
562 const SVal &
Iter,
bool Postfix)
const {
565 auto State =
C.getState();
566 auto &BVF =
C.getSymbolManager().getBasicVals();
576 "Advancing position by concrete int should always be successful");
580 "Iterator should have position after successful advancement");
584 C.addTransition(State);
590 const SVal &Iterator,
591 const SVal &Amount)
const {
594 auto State =
C.getState();
600 const auto *
Value = &Amount;
602 if (
auto LocAmount = Amount.
getAs<
Loc>()) {
603 Val = State->getRawSVal(*LocAmount);
608 (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iterator : RetVal;
617 "Iterator should have position after successful advancement");
620 C.addTransition(State);
622 assignToContainer(
C, CE, TgtVal, Pos->getContainer());
627 const Expr *Iterator,
630 if (!isa<DefinedSVal>(Offset))
639 SVal OldVal = State->getSVal(Iterator,
C.getLocationContext());
646 if (OK == OO_Plus || OK == OO_PlusEqual) {
647 NewVal = State->getLValue(ElementType, Offset, OldVal);
649 auto &SVB =
C.getSValBuilder();
650 SVal NegatedOffset = SVB.evalMinus(Offset.castAs<
NonLoc>());
651 NewVal = State->getLValue(ElementType, NegatedOffset, OldVal);
661 "Iterator should have position after successful advancement");
664 C.addTransition(NewState);
666 assignToContainer(
C, Iterator, NewVal, OldPos->
getContainer());
673 handleRandomIncrOrDecr(
C, CE, OO_PlusEqual, RetVal,
Iter, Amount);
678 handleRandomIncrOrDecr(
C, CE, OO_Minus, RetVal,
Iter, Amount);
683 handleRandomIncrOrDecr(
C, CE, OO_Plus, RetVal,
Iter, Amount);
691 auto State =
C.getState();
692 const auto *LCtx =
C.getLocationContext();
695 C.addTransition(State);
699 const Expr *CE)
const {
702 const auto StateAfter =
C.getState();
711 const ExplodedNode *N = findCallEnter(
C.getPredecessor(), CE);
712 assert(N &&
"Any call should have a `CallEnter` node.");
714 const auto StateBefore = N->
getState();
725 return PosBefore->getOffset() == PosAfter->getOffset();
728void IteratorModeling::printState(raw_ostream &Out,
ProgramStateRef State,
729 const char *NL,
const char *Sep)
const {
735 if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
736 Out << Sep <<
"Iterator Positions :" << NL;
737 for (
const auto &Sym : SymbolMap) {
743 const auto Pos = Sym.second;
744 Out << (Pos.isValid() ?
"Valid" :
"Invalid") <<
" ; Container == ";
745 Pos.getContainer()->dumpToStream(Out);
746 Out<<
" ; Offset == ";
747 Pos.getOffset()->dumpToStream(Out);
750 for (
const auto &Reg : RegionMap) {
754 Reg.first->dumpToStream(Out);
756 const auto Pos = Reg.second;
757 Out << (Pos.isValid() ?
"Valid" :
"Invalid") <<
" ; Container == ";
758 Pos.getContainer()->dumpToStream(Out);
759 Out<<
" ; Offset == ";
760 Pos.getOffset()->dumpToStream(Out);
768 return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
772 return OK == BO_EQ || OK == BO_NE;
777 Reg = Reg->getMostDerivedObjectRegion();
789 auto &SVB = State->getStateManager().getSValBuilder();
796 const auto comparison =
800 assert(isa<DefinedSVal>(comparison) &&
801 "Symbol comparison must be a `DefinedSVal`");
807 if (
const auto CompSym = comparison.getAsSymbol()) {
808 assert(isa<SymIntExpr>(CompSym) &&
809 "Symbol comparison must be a `SymIntExpr`");
811 cast<SymIntExpr>(CompSym)->getOpcode()) &&
812 "Symbol comparison must be a comparison");
821 for (
const auto &Binding :
Env) {
823 if (LCVal->getRegion() == Reg)
835 if (Enter->getCallExpr() ==
Call)
851bool ento::shouldRegisterIteratorModeling(
const CheckerManager &mgr) {
Defines the C++ template declaration subclasses.
A builtin binary operation expression such as "x + y" or "x <= y".
static OverloadedOperatorKind getOverloadedOperator(Opcode Opc)
Retrieve the overloaded operator kind that corresponds to the given binary opcode.
bool isComparisonOp() const
Represents a point when we begin processing an inlined call.
This represents one expression.
Represents a prvalue temporary that is written into memory so that a reference can bind to it.
Expr * getSubExpr() const
Retrieve the temporary-generating subexpression whose value will be materialized into a glvalue.
std::optional< T > getAs() const
Convert to the specified ProgramPoint type, returning std::nullopt if this ProgramPoint is not of the...
A (possibly-)qualified type.
Stmt - This represents one statement.
bool isPointerType() const
QualType getPointeeType() const
If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee.
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
bool isStructureOrClassType() const
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Expr * getSubExpr() const
An immutable map from CallDescriptions to arbitrary data.
Represents an abstract call to a function or method along a particular path.
virtual void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const
See CheckerManager::runCheckersForPrintState.
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
An immutable map from EnvironemntEntries to SVals.
const ProgramStateRef & getState() const
MemRegion - The root abstract class for all memory regions.
LLVM_ATTRIBUTE_RETURNS_NONNULL const MemRegion * getMostDerivedObjectRegion() const
Recursively retrieve the region of the most derived class instance of regions of C++ base class insta...
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
const MemRegion * getAsRegion() const
virtual void dumpToStream(raw_ostream &os) const
llvm::iterator_range< symbol_iterator > symbols() const
A class responsible for cleaning up unused symbols.
void markLive(SymbolRef sym)
Unconditionally marks a symbol as live.
bool isLiveRegion(const MemRegion *region)
bool isLive(SymbolRef sym)
Value representing integer constant.
Represents symbolic expression that isn't a location.
bool isIteratorType(const QualType &Type)
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance)
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale)
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, const IteratorPosition &Pos)
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
bool isDecrementOperator(OverloadedOperatorKind OK)
bool isIncrementOperator(OverloadedOperatorKind OK)
ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, const MemRegion *Cont, const Stmt *S, const LocationContext *LCtx, unsigned blockCount)
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
const MemRegion * getContainer() const
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of)