82using namespace iterator;
87 :
public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
88 check::PostStmt<BinaryOperator>,
89 check::PostStmt<MaterializeTemporaryExpr>,
90 check::Bind, check::LiveSymbols, check::DeadSymbols> {
99 const AdvanceFn *Handler)
const;
113 const SVal &Iterator,
const SVal &Amount)
const;
126 const char *Sep)
const override;
132 {{{
"std",
"advance"}, 2}, &IteratorModeling::handleAdvance},
138 {{{
"std",
"prev"}, 2}, &IteratorModeling::handlePrev},
144 {{{
"std",
"next"}, 2}, &IteratorModeling::handleNext},
148 IteratorModeling() =
default;
165bool isBoundThroughLazyCompoundVal(
const Environment &Env,
171void IteratorModeling::checkPostCall(
const CallEvent &Call,
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()) {
208 State = removeIteratorPosition(State,
Call.getArgSVal(0));
210 C.addTransition(State);
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());
236 auto State =
C.getState();
240 C.addTransition(State);
244 State = removeIteratorPosition(State,
Loc);
245 C.addTransition(State);
256 auto &SVB =
C.getSValBuilder();
259 SVB.makeArrayIndex(1));
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;
294 auto State =
C.getState();
299 C.addTransition(State);
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))
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))
323void IteratorModeling::checkDeadSymbols(
SymbolReaper &SR,
326 auto State =
C.getState();
329 for (
const auto &Reg : RegionMap) {
334 if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
341 for (
const auto &Sym : SymbolMap) {
342 if (!SR.
isLive(Sym.first)) {
347 C.addTransition(State);
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),
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));
456 auto State =
C.getState();
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());
497 auto &SymMgr =
C.getSymbolManager();
498 auto *LCtx =
C.getLocationContext();
500 CE, LCtx,
C.getASTContext().BoolTy,
C.blockCount()));
501 State = State->BindExpr(CE, LCtx, RetVal);
504 processComparison(
C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
512 if ((State = relateSymbols(State, Sym1, Sym2,
513 (Op == OO_EqualEqual) ==
514 (TruthVal->getValue() != 0)))) {
515 C.addTransition(State);
517 C.generateSink(State,
C.getPredecessor());
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);
538 const SVal &Iter,
bool Postfix)
const {
541 auto State =
C.getState();
542 auto &BVF =
C.getSymbolManager().getBasicVals();
552 "Advancing position by concrete int should always be successful");
556 "Iterator should have position after successful advancement");
560 C.addTransition(State);
564 const SVal &Iter,
bool Postfix)
const {
567 auto State =
C.getState();
568 auto &BVF =
C.getSymbolManager().getBasicVals();
578 "Advancing position by concrete int should always be successful");
582 "Iterator should have position after successful advancement");
586 C.addTransition(State);
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");
622 C.addTransition(State);
624 assignToContainer(
C, CE, TgtVal, Pos->getContainer());
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();
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());
675 handleRandomIncrOrDecr(
C, CE, OO_PlusEqual, RetVal, Iter, Amount);
680 handleRandomIncrOrDecr(
C, CE, OO_Minus, RetVal, Iter, Amount);
685 handleRandomIncrOrDecr(
C, CE, OO_Plus, RetVal, Iter, Amount);
693 auto State =
C.getState();
694 const auto *LCtx =
C.getLocationContext();
697 C.addTransition(State);
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();
730void IteratorModeling::printState(raw_ostream &Out,
ProgramStateRef State,
731 const char *NL,
const char *Sep)
const {
737 if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
738 Out << Sep <<
"Iterator Positions :" << NL;
739 for (
const auto &Sym : SymbolMap) {
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;
779 Reg = Reg->getMostDerivedObjectRegion();
791 auto &SVB = State->getStateManager().getSValBuilder();
798 const auto comparison =
802 assert(isa<DefinedSVal>(comparison) &&
803 "Symbol comparison must be a `DefinedSVal`");
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");
821bool isBoundThroughLazyCompoundVal(
const Environment &Env,
823 for (
const auto &Binding : Env) {
825 if (LCVal->getRegion() == Reg)
837 if (Enter->getCallExpr() == Call)
853bool 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
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)
bool Call(InterpState &S, CodePtr &PC, const Function *Func)
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
@ C
Languages that the frontend can parse and compile.
const MemRegion * getContainer() const
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of)