860 lines · cpp
1//===-- IteratorModeling.cpp --------------------------------------*- C++ -*--//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Defines a modeling-checker for modeling STL iterator-like iterators.10//11//===----------------------------------------------------------------------===//12//13// In the code, iterator can be represented as a:14// * type-I: typedef-ed pointer. Operations over such iterator, such as15// comparisons or increments, are modeled straightforwardly by the16// analyzer.17// * type-II: structure with its method bodies available. Operations over such18// iterator are inlined by the analyzer, and results of modeling19// these operations are exposing implementation details of the20// iterators, which is not necessarily helping.21// * type-III: completely opaque structure. Operations over such iterator are22// modeled conservatively, producing conjured symbols everywhere.23//24// To handle all these types in a common way we introduce a structure called25// IteratorPosition which is an abstraction of the position the iterator26// represents using symbolic expressions. The checker handles all the27// operations on this structure.28//29// Additionally, depending on the circumstances, operators of types II and III30// can be represented as:31// * type-IIa, type-IIIa: conjured structure symbols - when returned by value32// from conservatively evaluated methods such as33// `.begin()`.34// * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as35// variables or temporaries, when the iterator object is36// currently treated as an lvalue.37// * type-IIc, type-IIIc: compound values of iterator-typed objects, when the38// iterator object is treated as an rvalue taken of a39// particular lvalue, eg. a copy of "type-a" iterator40// object, or an iterator that existed before the41// analysis has started.42//43// To handle any of these three different representations stored in an SVal we44// use setter and getters functions which separate the three cases. To store45// them we use a pointer union of symbol and memory region.46//47// The checker works the following way: We record the begin and the48// past-end iterator for all containers whenever their `.begin()` and `.end()`49// are called. Since the Constraint Manager cannot handle such SVals we need50// to take over its role. We post-check equality and non-equality comparisons51// and record that the two sides are equal if we are in the 'equal' branch52// (true-branch for `==` and false-branch for `!=`).53//54// In case of type-I or type-II iterators we get a concrete integer as a result55// of the comparison (1 or 0) but in case of type-III we only get a Symbol. In56// this latter case we record the symbol and reload it in evalAssume() and do57// the propagation there. We also handle (maybe double) negated comparisons58// which are represented in the form of (x == 0 or x != 0) where x is the59// comparison itself.60//61// Since `SimpleConstraintManager` cannot handle complex symbolic expressions62// we only use expressions of the format S, S+n or S-n for iterator positions63// where S is a conjured symbol and n is an unsigned concrete integer. When64// making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as65// a constraint which we later retrieve when doing an actual comparison.66 67#include "clang/AST/DeclTemplate.h"68#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"69#include "clang/StaticAnalyzer/Core/Checker.h"70#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"71#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"72#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"73#include "llvm/ADT/STLExtras.h"74 75#include "Iterator.h"76 77#include <utility>78 79using namespace clang;80using namespace ento;81using namespace iterator;82 83namespace {84 85class IteratorModeling86 : public Checker<check::PostCall, check::PostStmt<UnaryOperator>,87 check::PostStmt<BinaryOperator>,88 check::PostStmt<MaterializeTemporaryExpr>,89 check::Bind, check::LiveSymbols, check::DeadSymbols> {90 91 using AdvanceFn = void (IteratorModeling::*)(CheckerContext &,92 ConstCFGElementRef, SVal, SVal,93 SVal) const;94 95 void handleOverloadedOperator(CheckerContext &C, const CallEvent &Call,96 OverloadedOperatorKind Op) const;97 void handleAdvanceLikeFunction(CheckerContext &C, const CallEvent &Call,98 const Expr *OrigExpr,99 const AdvanceFn *Handler) const;100 101 void handleComparison(CheckerContext &C, const Expr *CE,102 ConstCFGElementRef Elem, SVal RetVal, SVal LVal,103 SVal RVal, OverloadedOperatorKind Op) const;104 void processComparison(CheckerContext &C, ProgramStateRef State,105 SymbolRef Sym1, SymbolRef Sym2, SVal RetVal,106 OverloadedOperatorKind Op) const;107 void handleIncrement(CheckerContext &C, SVal RetVal, SVal Iter,108 bool Postfix) const;109 void handleDecrement(CheckerContext &C, SVal RetVal, SVal Iter,110 bool Postfix) const;111 void handleRandomIncrOrDecr(CheckerContext &C, ConstCFGElementRef Elem,112 OverloadedOperatorKind Op, SVal RetVal,113 SVal Iterator, SVal Amount) const;114 void handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,115 ConstCFGElementRef Elem, OverloadedOperatorKind OK,116 SVal Offset) const;117 void handleAdvance(CheckerContext &C, ConstCFGElementRef Elem, SVal RetVal,118 SVal Iter, SVal Amount) const;119 void handlePrev(CheckerContext &C, ConstCFGElementRef Elem, SVal RetVal,120 SVal Iter, SVal Amount) const;121 void handleNext(CheckerContext &C, ConstCFGElementRef Elem, SVal RetVal,122 SVal Iter, SVal Amount) const;123 void assignToContainer(CheckerContext &C, ConstCFGElementRef Elem,124 SVal RetVal, const MemRegion *Cont) const;125 bool noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const;126 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,127 const char *Sep) const override;128 129 // std::advance, std::prev & std::next130 CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {131 // template<class InputIt, class Distance>132 // void advance(InputIt& it, Distance n);133 {{CDM::SimpleFunc, {"std", "advance"}, 2},134 &IteratorModeling::handleAdvance},135 136 // template<class BidirIt>137 // BidirIt prev(138 // BidirIt it,139 // typename std::iterator_traits<BidirIt>::difference_type n = 1);140 {{CDM::SimpleFunc, {"std", "prev"}, 2}, &IteratorModeling::handlePrev},141 142 // template<class ForwardIt>143 // ForwardIt next(144 // ForwardIt it,145 // typename std::iterator_traits<ForwardIt>::difference_type n = 1);146 {{CDM::SimpleFunc, {"std", "next"}, 2}, &IteratorModeling::handleNext},147 };148 149public:150 IteratorModeling() = default;151 152 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;153 void checkBind(SVal Loc, SVal Val, const Stmt *S, bool AtDeclInit,154 CheckerContext &C) const;155 void checkPostStmt(const UnaryOperator *UO, CheckerContext &C) const;156 void checkPostStmt(const BinaryOperator *BO, CheckerContext &C) const;157 void checkPostStmt(const MaterializeTemporaryExpr *MTE,158 CheckerContext &C) const;159 void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;160 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;161};162 163bool isSimpleComparisonOperator(OverloadedOperatorKind OK);164bool isSimpleComparisonOperator(BinaryOperatorKind OK);165ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val);166ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,167 SymbolRef Sym2, bool Equal);168bool isBoundThroughLazyCompoundVal(const Environment &Env,169 const MemRegion *Reg);170const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);171 172} // namespace173 174void IteratorModeling::checkPostCall(const CallEvent &Call,175 CheckerContext &C) const {176 // Record new iterator positions and iterator position changes177 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());178 if (!Func)179 return;180 181 if (Func->isOverloadedOperator()) {182 const auto Op = Func->getOverloadedOperator();183 handleOverloadedOperator(C, Call, Op);184 return;185 }186 187 const auto *OrigExpr = Call.getOriginExpr();188 if (!OrigExpr)189 return;190 191 const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(Call);192 if (Handler) {193 handleAdvanceLikeFunction(C, Call, OrigExpr, Handler);194 return;195 }196 197 if (!isIteratorType(Call.getResultType()))198 return;199 200 auto State = C.getState();201 202 // Already bound to container?203 if (getIteratorPosition(State, Call.getReturnValue()))204 return;205 206 // Copy-like and move constructors207 if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {208 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {209 State = setIteratorPosition(State, Call.getReturnValue(), *Pos);210 if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {211 State = removeIteratorPosition(State, Call.getArgSVal(0));212 }213 C.addTransition(State);214 return;215 }216 }217 218 // Assumption: if return value is an iterator which is not yet bound to a219 // container, then look for the first iterator argument of the220 // same type as the return value and bind the return value to221 // the same container. This approach works for STL algorithms.222 // FIXME: Add a more conservative mode223 for (unsigned i = 0; i < Call.getNumArgs(); ++i) {224 if (isIteratorType(Call.getArgExpr(i)->getType()) &&225 Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType(226 C.getASTContext()).getTypePtr() ==227 Call.getResultType().getDesugaredType(C.getASTContext()).getTypePtr()) {228 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {229 assignToContainer(C, Call.getCFGElementRef(), Call.getReturnValue(),230 Pos->getContainer());231 return;232 }233 }234 }235}236 237void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,238 bool AtDeclInit, CheckerContext &C) const {239 auto State = C.getState();240 const auto *Pos = getIteratorPosition(State, Val);241 if (Pos) {242 State = setIteratorPosition(State, Loc, *Pos);243 C.addTransition(State);244 } else {245 const auto *OldPos = getIteratorPosition(State, Loc);246 if (OldPos) {247 State = removeIteratorPosition(State, Loc);248 C.addTransition(State);249 }250 }251}252 253void IteratorModeling::checkPostStmt(const UnaryOperator *UO,254 CheckerContext &C) const {255 UnaryOperatorKind OK = UO->getOpcode();256 if (!isIncrementOperator(OK) && !isDecrementOperator(OK))257 return;258 259 auto &SVB = C.getSValBuilder();260 handlePtrIncrOrDecr(C, UO->getSubExpr(), C.getCFGElementRef(),261 isIncrementOperator(OK) ? OO_Plus : OO_Minus,262 SVB.makeArrayIndex(1));263}264 265void IteratorModeling::checkPostStmt(const BinaryOperator *BO,266 CheckerContext &C) const {267 const ProgramStateRef State = C.getState();268 const BinaryOperatorKind OK = BO->getOpcode();269 const Expr *const LHS = BO->getLHS();270 const Expr *const RHS = BO->getRHS();271 const SVal LVal = State->getSVal(LHS, C.getLocationContext());272 const SVal RVal = State->getSVal(RHS, C.getLocationContext());273 274 if (isSimpleComparisonOperator(BO->getOpcode())) {275 SVal Result = State->getSVal(BO, C.getLocationContext());276 handleComparison(C, BO, C.getCFGElementRef(), Result, LVal, RVal,277 BinaryOperator::getOverloadedOperator(OK));278 } else if (isRandomIncrOrDecrOperator(OK)) {279 // In case of operator+ the iterator can be either on the LHS (eg.: it + 1),280 // or on the RHS (eg.: 1 + it). Both cases are modeled.281 const bool IsIterOnLHS = BO->getLHS()->getType()->isPointerType();282 const Expr *const &IterExpr = IsIterOnLHS ? LHS : RHS;283 const Expr *const &AmountExpr = IsIterOnLHS ? RHS : LHS;284 285 // The non-iterator side must have an integral or enumeration type.286 if (!AmountExpr->getType()->isIntegralOrEnumerationType())287 return;288 SVal AmountVal = IsIterOnLHS ? RVal : LVal;289 handlePtrIncrOrDecr(C, IterExpr, C.getCFGElementRef(),290 BinaryOperator::getOverloadedOperator(OK), AmountVal);291 }292}293 294void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,295 CheckerContext &C) const {296 /* Transfer iterator state to temporary objects */297 auto State = C.getState();298 const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));299 if (!Pos)300 return;301 State = setIteratorPosition(State, C.getSVal(MTE), *Pos);302 C.addTransition(State);303}304 305void IteratorModeling::checkLiveSymbols(ProgramStateRef State,306 SymbolReaper &SR) const {307 // Keep symbolic expressions of iterator positions alive308 auto RegionMap = State->get<IteratorRegionMap>();309 for (const IteratorPosition &Pos : llvm::make_second_range(RegionMap)) {310 for (SymbolRef Sym : Pos.getOffset()->symbols())311 if (isa<SymbolData>(Sym))312 SR.markLive(Sym);313 }314 315 auto SymbolMap = State->get<IteratorSymbolMap>();316 for (const IteratorPosition &Pos : llvm::make_second_range(SymbolMap)) {317 for (SymbolRef Sym : Pos.getOffset()->symbols())318 if (isa<SymbolData>(Sym))319 SR.markLive(Sym);320 }321}322 323void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,324 CheckerContext &C) const {325 // Cleanup326 auto State = C.getState();327 328 auto RegionMap = State->get<IteratorRegionMap>();329 for (const auto &Reg : RegionMap) {330 if (!SR.isLiveRegion(Reg.first)) {331 // The region behind the `LazyCompoundVal` is often cleaned up before332 // the `LazyCompoundVal` itself. If there are iterator positions keyed333 // by these regions their cleanup must be deferred.334 if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {335 State = State->remove<IteratorRegionMap>(Reg.first);336 }337 }338 }339 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);344 }345 }346 347 C.addTransition(State);348}349 350void351IteratorModeling::handleOverloadedOperator(CheckerContext &C,352 const CallEvent &Call,353 OverloadedOperatorKind Op) const {354 if (isSimpleComparisonOperator(Op)) {355 const auto *OrigExpr = Call.getOriginExpr();356 const auto Elem = Call.getCFGElementRef();357 if (!OrigExpr)358 return;359 360 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {361 handleComparison(C, OrigExpr, Elem, Call.getReturnValue(),362 InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);363 return;364 }365 366 handleComparison(C, OrigExpr, Elem, Call.getReturnValue(),367 Call.getArgSVal(0), Call.getArgSVal(1), Op);368 return;369 } else if (isRandomIncrOrDecrOperator(Op)) {370 const auto *OrigExpr = Call.getOriginExpr();371 const auto Elem = Call.getCFGElementRef();372 if (!OrigExpr)373 return;374 375 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {376 if (Call.getNumArgs() >= 1 &&377 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {378 handleRandomIncrOrDecr(C, Elem, Op, Call.getReturnValue(),379 InstCall->getCXXThisVal(), Call.getArgSVal(0));380 return;381 }382 } else if (Call.getNumArgs() >= 2) {383 const Expr *FirstArg = Call.getArgExpr(0);384 const Expr *SecondArg = Call.getArgExpr(1);385 const QualType FirstType = FirstArg->getType();386 const QualType SecondType = SecondArg->getType();387 388 if (FirstType->isIntegralOrEnumerationType() ||389 SecondType->isIntegralOrEnumerationType()) {390 // In case of operator+ the iterator can be either on the LHS (eg.:391 // it + 1), or on the RHS (eg.: 1 + it). Both cases are modeled.392 const bool IsIterFirst = FirstType->isStructureOrClassType();393 const SVal FirstArg = Call.getArgSVal(0);394 const SVal SecondArg = Call.getArgSVal(1);395 SVal Iterator = IsIterFirst ? FirstArg : SecondArg;396 SVal Amount = IsIterFirst ? SecondArg : FirstArg;397 398 handleRandomIncrOrDecr(C, Elem, Op, Call.getReturnValue(), Iterator,399 Amount);400 return;401 }402 }403 } else if (isIncrementOperator(Op)) {404 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {405 handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),406 Call.getNumArgs());407 return;408 }409 410 handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),411 Call.getNumArgs());412 return;413 } else if (isDecrementOperator(Op)) {414 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {415 handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),416 Call.getNumArgs());417 return;418 }419 420 handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),421 Call.getNumArgs());422 return;423 }424}425 426void427IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,428 const CallEvent &Call,429 const Expr *OrigExpr,430 const AdvanceFn *Handler) const {431 if (!C.wasInlined) {432 (this->**Handler)(C, Call.getCFGElementRef(), Call.getReturnValue(),433 Call.getArgSVal(0), Call.getArgSVal(1));434 return;435 }436 437 // If std::advance() was inlined, but a non-standard function it calls inside438 // was not, then we have to model it explicitly439 const auto *IdInfo = cast<FunctionDecl>(Call.getDecl())->getIdentifier();440 if (IdInfo) {441 if (IdInfo->getName() == "advance") {442 if (noChangeInAdvance(C, Call.getArgSVal(0), OrigExpr)) {443 (this->**Handler)(C, Call.getCFGElementRef(), Call.getReturnValue(),444 Call.getArgSVal(0), Call.getArgSVal(1));445 }446 }447 }448}449 450void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,451 ConstCFGElementRef Elem, SVal RetVal,452 SVal LVal, SVal RVal,453 OverloadedOperatorKind Op) const {454 // Record the operands and the operator of the comparison for the next455 // evalAssume, if the result is a symbolic expression. If it is a concrete456 // value (only one branch is possible), then transfer the state between457 // the operands according to the operator and the result458 auto State = C.getState();459 const auto *LPos = getIteratorPosition(State, LVal);460 const auto *RPos = getIteratorPosition(State, RVal);461 const MemRegion *Cont = nullptr;462 if (LPos) {463 Cont = LPos->getContainer();464 } else if (RPos) {465 Cont = RPos->getContainer();466 }467 if (!Cont)468 return;469 470 // At least one of the iterators has recorded positions. If one of them does471 // not then create a new symbol for the offset.472 SymbolRef Sym;473 if (!LPos || !RPos) {474 auto &SymMgr = C.getSymbolManager();475 Sym = SymMgr.conjureSymbol(Elem, C.getLocationContext(),476 C.getASTContext().LongTy, C.blockCount());477 State = assumeNoOverflow(State, Sym, 4);478 }479 480 if (!LPos) {481 State = setIteratorPosition(State, LVal,482 IteratorPosition::getPosition(Cont, Sym));483 LPos = getIteratorPosition(State, LVal);484 } else if (!RPos) {485 State = setIteratorPosition(State, RVal,486 IteratorPosition::getPosition(Cont, Sym));487 RPos = getIteratorPosition(State, RVal);488 }489 490 // If the value for which we just tried to set a new iterator position is491 // an `SVal`for which no iterator position can be set then the setting was492 // unsuccessful. We cannot handle the comparison in this case.493 if (!LPos || !RPos)494 return;495 496 // We cannot make assumptions on `UnknownVal`. Let us conjure a symbol497 // instead.498 if (RetVal.isUnknown()) {499 auto &SymMgr = C.getSymbolManager();500 auto *LCtx = C.getLocationContext();501 RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(502 Elem, LCtx, C.getASTContext().BoolTy, C.blockCount()));503 State = State->BindExpr(CE, LCtx, RetVal);504 }505 506 processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);507}508 509void IteratorModeling::processComparison(CheckerContext &C,510 ProgramStateRef State, SymbolRef Sym1,511 SymbolRef Sym2, SVal RetVal,512 OverloadedOperatorKind Op) const {513 if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {514 if ((State = relateSymbols(State, Sym1, Sym2,515 (Op == OO_EqualEqual) ==516 (TruthVal->getValue()->getBoolValue())))) {517 C.addTransition(State);518 } else {519 C.generateSink(State, C.getPredecessor());520 }521 return;522 }523 524 const auto ConditionVal = RetVal.getAs<DefinedSVal>();525 if (!ConditionVal)526 return;527 528 if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {529 StateTrue = StateTrue->assume(*ConditionVal, true);530 C.addTransition(StateTrue);531 }532 533 if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {534 StateFalse = StateFalse->assume(*ConditionVal, false);535 C.addTransition(StateFalse);536 }537}538 539void IteratorModeling::handleIncrement(CheckerContext &C, SVal RetVal,540 SVal Iter, bool Postfix) const {541 // Increment the symbolic expressions which represents the position of the542 // iterator543 auto State = C.getState();544 auto &BVF = C.getSymbolManager().getBasicVals();545 546 const auto *Pos = getIteratorPosition(State, Iter);547 if (!Pos)548 return;549 550 auto NewState =551 advancePosition(State, Iter, OO_Plus,552 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));553 assert(NewState &&554 "Advancing position by concrete int should always be successful");555 556 const auto *NewPos = getIteratorPosition(NewState, Iter);557 assert(NewPos &&558 "Iterator should have position after successful advancement");559 560 State = setIteratorPosition(State, Iter, *NewPos);561 State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);562 C.addTransition(State);563}564 565void IteratorModeling::handleDecrement(CheckerContext &C, SVal RetVal,566 SVal Iter, bool Postfix) const {567 // Decrement the symbolic expressions which represents the position of the568 // iterator569 auto State = C.getState();570 auto &BVF = C.getSymbolManager().getBasicVals();571 572 const auto *Pos = getIteratorPosition(State, Iter);573 if (!Pos)574 return;575 576 auto NewState =577 advancePosition(State, Iter, OO_Minus,578 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));579 assert(NewState &&580 "Advancing position by concrete int should always be successful");581 582 const auto *NewPos = getIteratorPosition(NewState, Iter);583 assert(NewPos &&584 "Iterator should have position after successful advancement");585 586 State = setIteratorPosition(State, Iter, *NewPos);587 State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);588 C.addTransition(State);589}590 591void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C,592 ConstCFGElementRef Elem,593 OverloadedOperatorKind Op,594 SVal RetVal, SVal Iterator,595 SVal Amount) const {596 // Increment or decrement the symbolic expressions which represents the597 // position of the iterator598 auto State = C.getState();599 600 const auto *Pos = getIteratorPosition(State, Iterator);601 if (!Pos)602 return;603 604 const auto *Value = &Amount;605 SVal Val;606 if (auto LocAmount = Amount.getAs<Loc>()) {607 Val = State->getRawSVal(*LocAmount);608 Value = &Val;609 }610 611 const auto &TgtVal =612 (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iterator : RetVal;613 614 // `AdvancedState` is a state where the position of `LHS` is advanced. We615 // only need this state to retrieve the new position, but we do not want616 // to change the position of `LHS` (in every case).617 auto AdvancedState = advancePosition(State, Iterator, Op, *Value);618 if (AdvancedState) {619 const auto *NewPos = getIteratorPosition(AdvancedState, Iterator);620 assert(NewPos &&621 "Iterator should have position after successful advancement");622 623 State = setIteratorPosition(State, TgtVal, *NewPos);624 C.addTransition(State);625 } else {626 assignToContainer(C, Elem, TgtVal, Pos->getContainer());627 }628}629 630void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,631 const Expr *Iterator,632 ConstCFGElementRef Elem,633 OverloadedOperatorKind OK,634 SVal Offset) const {635 if (!isa<DefinedSVal>(Offset))636 return;637 638 QualType PtrType = Iterator->getType();639 if (!PtrType->isPointerType())640 return;641 QualType ElementType = PtrType->getPointeeType();642 643 ProgramStateRef State = C.getState();644 SVal OldVal = State->getSVal(Iterator, C.getLocationContext());645 646 const IteratorPosition *OldPos = getIteratorPosition(State, OldVal);647 if (!OldPos)648 return;649 650 SVal NewVal;651 if (OK == OO_Plus || OK == OO_PlusEqual) {652 NewVal = State->getLValue(ElementType, Offset, OldVal);653 } else {654 auto &SVB = C.getSValBuilder();655 SVal NegatedOffset = SVB.evalMinus(Offset.castAs<NonLoc>());656 NewVal = State->getLValue(ElementType, NegatedOffset, OldVal);657 }658 659 // `AdvancedState` is a state where the position of `Old` is advanced. We660 // only need this state to retrieve the new position, but we do not want661 // ever to change the position of `OldVal`.662 auto AdvancedState = advancePosition(State, OldVal, OK, Offset);663 if (AdvancedState) {664 const IteratorPosition *NewPos = getIteratorPosition(AdvancedState, OldVal);665 assert(NewPos &&666 "Iterator should have position after successful advancement");667 668 ProgramStateRef NewState = setIteratorPosition(State, NewVal, *NewPos);669 C.addTransition(NewState);670 } else {671 assignToContainer(C, Elem, NewVal, OldPos->getContainer());672 }673}674 675void IteratorModeling::handleAdvance(CheckerContext &C, ConstCFGElementRef Elem,676 SVal RetVal, SVal Iter,677 SVal Amount) const {678 handleRandomIncrOrDecr(C, Elem, OO_PlusEqual, RetVal, Iter, Amount);679}680 681void IteratorModeling::handlePrev(CheckerContext &C, ConstCFGElementRef Elem,682 SVal RetVal, SVal Iter, SVal Amount) const {683 handleRandomIncrOrDecr(C, Elem, OO_Minus, RetVal, Iter, Amount);684}685 686void IteratorModeling::handleNext(CheckerContext &C, ConstCFGElementRef Elem,687 SVal RetVal, SVal Iter, SVal Amount) const {688 handleRandomIncrOrDecr(C, Elem, OO_Plus, RetVal, Iter, Amount);689}690 691void IteratorModeling::assignToContainer(CheckerContext &C,692 ConstCFGElementRef Elem, SVal RetVal,693 const MemRegion *Cont) const {694 Cont = Cont->getMostDerivedObjectRegion();695 696 auto State = C.getState();697 const auto *LCtx = C.getLocationContext();698 State =699 createIteratorPosition(State, RetVal, Cont, Elem, LCtx, C.blockCount());700 701 C.addTransition(State);702}703 704bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,705 const Expr *CE) const {706 // Compare the iterator position before and after the call. (To be called707 // from `checkPostCall()`.)708 const auto StateAfter = C.getState();709 710 const auto *PosAfter = getIteratorPosition(StateAfter, Iter);711 // If we have no position after the call of `std::advance`, then we are not712 // interested. (Modeling of an inlined `std::advance()` should not remove the713 // position in any case.)714 if (!PosAfter)715 return false;716 717 const ExplodedNode *N = findCallEnter(C.getPredecessor(), CE);718 assert(N && "Any call should have a `CallEnter` node.");719 720 const auto StateBefore = N->getState();721 const auto *PosBefore = getIteratorPosition(StateBefore, Iter);722 // FIXME: `std::advance()` should not create a new iterator position but723 // change existing ones. However, in case of iterators implemented as724 // pointers the handling of parameters in `std::advance()`-like725 // functions is still incomplete which may result in cases where726 // the new position is assigned to the wrong pointer. This causes727 // crash if we use an assertion here.728 if (!PosBefore)729 return false;730 731 return PosBefore->getOffset() == PosAfter->getOffset();732}733 734void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,735 const char *NL, const char *Sep) const {736 auto SymbolMap = State->get<IteratorSymbolMap>();737 auto RegionMap = State->get<IteratorRegionMap>();738 // Use a counter to add newlines before every line except the first one.739 unsigned Count = 0;740 741 if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {742 Out << Sep << "Iterator Positions :" << NL;743 for (const auto &Sym : SymbolMap) {744 if (Count++)745 Out << NL;746 747 Sym.first->dumpToStream(Out);748 Out << " : ";749 const auto Pos = Sym.second;750 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";751 Pos.getContainer()->dumpToStream(Out);752 Out<<" ; Offset == ";753 Pos.getOffset()->dumpToStream(Out);754 }755 756 for (const auto &Reg : RegionMap) {757 if (Count++)758 Out << NL;759 760 Reg.first->dumpToStream(Out);761 Out << " : ";762 const auto Pos = Reg.second;763 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";764 Pos.getContainer()->dumpToStream(Out);765 Out<<" ; Offset == ";766 Pos.getOffset()->dumpToStream(Out);767 }768 }769}770 771namespace {772 773bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {774 return OK == OO_EqualEqual || OK == OO_ExclaimEqual;775}776 777bool isSimpleComparisonOperator(BinaryOperatorKind OK) {778 return OK == BO_EQ || OK == BO_NE;779}780 781ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val) {782 if (auto Reg = Val.getAsRegion()) {783 Reg = Reg->getMostDerivedObjectRegion();784 return State->remove<IteratorRegionMap>(Reg);785 } else if (const auto Sym = Val.getAsSymbol()) {786 return State->remove<IteratorSymbolMap>(Sym);787 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {788 return State->remove<IteratorRegionMap>(LCVal->getRegion());789 }790 return nullptr;791}792 793ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,794 SymbolRef Sym2, bool Equal) {795 auto &SVB = State->getStateManager().getSValBuilder();796 797 // FIXME: This code should be reworked as follows:798 // 1. Subtract the operands using evalBinOp().799 // 2. Assume that the result doesn't overflow.800 // 3. Compare the result to 0.801 // 4. Assume the result of the comparison.802 const auto comparison =803 SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),804 nonloc::SymbolVal(Sym2), SVB.getConditionType());805 806 assert(isa<DefinedSVal>(comparison) &&807 "Symbol comparison must be a `DefinedSVal`");808 809 auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);810 if (!NewState)811 return nullptr;812 813 if (const auto CompSym = comparison.getAsSymbol()) {814 assert(isa<SymIntExpr>(CompSym) &&815 "Symbol comparison must be a `SymIntExpr`");816 assert(BinaryOperator::isComparisonOp(817 cast<SymIntExpr>(CompSym)->getOpcode()) &&818 "Symbol comparison must be a comparison");819 return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);820 }821 822 return NewState;823}824 825bool isBoundThroughLazyCompoundVal(const Environment &Env,826 const MemRegion *Reg) {827 for (const auto &Binding : Env) {828 if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {829 if (LCVal->getRegion() == Reg)830 return true;831 }832 }833 834 return false;835}836 837const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) {838 while (Node) {839 ProgramPoint PP = Node->getLocation();840 if (auto Enter = PP.getAs<CallEnter>()) {841 if (Enter->getCallExpr() == Call)842 break;843 }844 845 Node = Node->getFirstPred();846 }847 848 return Node;849}850 851} // namespace852 853void ento::registerIteratorModeling(CheckerManager &mgr) {854 mgr.registerChecker<IteratorModeling>();855}856 857bool ento::shouldRegisterIteratorModeling(const CheckerManager &mgr) {858 return true;859}860