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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Defines a checker for using iterators outside their range (past end). Usage 10 // means here dereferencing, incrementing etc. 11 // 12 //===----------------------------------------------------------------------===// 13 // 14 // In the code, iterator can be represented as a: 15 // * type-I: typedef-ed pointer. Operations over such iterator, such as 16 // comparisons or increments, are modeled straightforwardly by the 17 // analyzer. 18 // * type-II: structure with its method bodies available. Operations over such 19 // iterator are inlined by the analyzer, and results of modeling 20 // these operations are exposing implementation details of the 21 // iterators, which is not necessarily helping. 22 // * type-III: completely opaque structure. Operations over such iterator are 23 // modeled conservatively, producing conjured symbols everywhere. 24 // 25 // To handle all these types in a common way we introduce a structure called 26 // IteratorPosition which is an abstraction of the position the iterator 27 // represents using symbolic expressions. The checker handles all the 28 // operations on this structure. 29 // 30 // Additionally, depending on the circumstances, operators of types II and III 31 // can be represented as: 32 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value 33 // from conservatively evaluated methods such as 34 // `.begin()`. 35 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as 36 // variables or temporaries, when the iterator object is 37 // currently treated as an lvalue. 38 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the 39 // iterator object is treated as an rvalue taken of a 40 // particular lvalue, eg. a copy of "type-a" iterator 41 // object, or an iterator that existed before the 42 // analysis has started. 43 // 44 // To handle any of these three different representations stored in an SVal we 45 // use setter and getters functions which separate the three cases. To store 46 // them we use a pointer union of symbol and memory region. 47 // 48 // The checker works the following way: We record the begin and the 49 // past-end iterator for all containers whenever their `.begin()` and `.end()` 50 // are called. Since the Constraint Manager cannot handle such SVals we need 51 // to take over its role. We post-check equality and non-equality comparisons 52 // and record that the two sides are equal if we are in the 'equal' branch 53 // (true-branch for `==` and false-branch for `!=`). 54 // 55 // In case of type-I or type-II iterators we get a concrete integer as a result 56 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In 57 // this latter case we record the symbol and reload it in evalAssume() and do 58 // the propagation there. We also handle (maybe double) negated comparisons 59 // which are represented in the form of (x == 0 or x != 0) where x is the 60 // comparison itself. 61 // 62 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions 63 // we only use expressions of the format S, S+n or S-n for iterator positions 64 // where S is a conjured symbol and n is an unsigned concrete integer. When 65 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as 66 // a constraint which we later retrieve when doing an actual comparison. 67 68 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" 69 #include "clang/AST/DeclTemplate.h" 70 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 71 #include "clang/StaticAnalyzer/Core/Checker.h" 72 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 73 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 74 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" 75 76 #include "Iterator.h" 77 78 #include <utility> 79 80 using namespace clang; 81 using namespace ento; 82 using namespace iterator; 83 84 namespace { 85 86 class IteratorModeling 87 : public Checker<check::PostCall, check::PostStmt<MaterializeTemporaryExpr>, 88 check::Bind, check::LiveSymbols, check::DeadSymbols> { 89 90 void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal, 91 const SVal &LVal, const SVal &RVal, 92 OverloadedOperatorKind Op) const; 93 void processComparison(CheckerContext &C, ProgramStateRef State, 94 SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal, 95 OverloadedOperatorKind Op) const; 96 void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, 97 bool Postfix) const; 98 void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, 99 bool Postfix) const; 100 void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE, 101 OverloadedOperatorKind Op, const SVal &RetVal, 102 const SVal &LHS, const SVal &RHS) const; 103 void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal, 104 const SVal &Cont) const; 105 void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal, 106 const SVal &Cont) const; 107 void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, 108 const MemRegion *Cont) const; 109 void handleAssign(CheckerContext &C, const SVal &Cont, 110 const Expr *CE = nullptr, 111 const SVal &OldCont = UndefinedVal()) const; 112 void handleClear(CheckerContext &C, const SVal &Cont) const; 113 void handlePushBack(CheckerContext &C, const SVal &Cont) const; 114 void handlePopBack(CheckerContext &C, const SVal &Cont) const; 115 void handlePushFront(CheckerContext &C, const SVal &Cont) const; 116 void handlePopFront(CheckerContext &C, const SVal &Cont) const; 117 void handleInsert(CheckerContext &C, const SVal &Iter) const; 118 void handleErase(CheckerContext &C, const SVal &Iter) const; 119 void handleErase(CheckerContext &C, const SVal &Iter1, 120 const SVal &Iter2) const; 121 void handleEraseAfter(CheckerContext &C, const SVal &Iter) const; 122 void handleEraseAfter(CheckerContext &C, const SVal &Iter1, 123 const SVal &Iter2) const; 124 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, 125 const char *Sep) const override; 126 127 public: 128 IteratorModeling() {} 129 130 void checkPostCall(const CallEvent &Call, CheckerContext &C) const; 131 void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const; 132 void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const; 133 void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const; 134 void checkPostStmt(const MaterializeTemporaryExpr *MTE, 135 CheckerContext &C) const; 136 void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; 137 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; 138 }; 139 140 bool isBeginCall(const FunctionDecl *Func); 141 bool isEndCall(const FunctionDecl *Func); 142 bool isAssignCall(const FunctionDecl *Func); 143 bool isClearCall(const FunctionDecl *Func); 144 bool isPushBackCall(const FunctionDecl *Func); 145 bool isEmplaceBackCall(const FunctionDecl *Func); 146 bool isPopBackCall(const FunctionDecl *Func); 147 bool isPushFrontCall(const FunctionDecl *Func); 148 bool isEmplaceFrontCall(const FunctionDecl *Func); 149 bool isPopFrontCall(const FunctionDecl *Func); 150 bool isAssignmentOperator(OverloadedOperatorKind OK); 151 bool isSimpleComparisonOperator(OverloadedOperatorKind OK); 152 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg); 153 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg); 154 bool backModifiable(ProgramStateRef State, const MemRegion *Reg); 155 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont); 156 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont); 157 ProgramStateRef createContainerBegin(ProgramStateRef State, 158 const MemRegion *Cont, const Expr *E, 159 QualType T, const LocationContext *LCtx, 160 unsigned BlockCount); 161 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, 162 const Expr *E, QualType T, 163 const LocationContext *LCtx, 164 unsigned BlockCount); 165 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, 166 const ContainerData &CData); 167 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val); 168 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, 169 long Scale); 170 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, 171 const MemRegion *Cont); 172 ProgramStateRef 173 invalidateAllIteratorPositionsExcept(ProgramStateRef State, 174 const MemRegion *Cont, SymbolRef Offset, 175 BinaryOperator::Opcode Opc); 176 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, 177 SymbolRef Offset, 178 BinaryOperator::Opcode Opc); 179 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, 180 SymbolRef Offset1, 181 BinaryOperator::Opcode Opc1, 182 SymbolRef Offset2, 183 BinaryOperator::Opcode Opc2); 184 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, 185 const MemRegion *Cont, 186 const MemRegion *NewCont); 187 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, 188 const MemRegion *Cont, 189 const MemRegion *NewCont, 190 SymbolRef Offset, 191 BinaryOperator::Opcode Opc); 192 ProgramStateRef rebaseSymbolInIteratorPositionsIf( 193 ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, 194 SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc); 195 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, 196 SymbolRef Sym2, bool Equal); 197 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr, 198 SymbolRef OldSym, SymbolRef NewSym); 199 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont); 200 bool isBoundThroughLazyCompoundVal(const Environment &Env, 201 const MemRegion *Reg); 202 203 } // namespace 204 205 void IteratorModeling::checkPostCall(const CallEvent &Call, 206 CheckerContext &C) const { 207 // Record new iterator positions and iterator position changes 208 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); 209 if (!Func) 210 return; 211 212 if (Func->isOverloadedOperator()) { 213 const auto Op = Func->getOverloadedOperator(); 214 if (isAssignmentOperator(Op)) { 215 // Overloaded 'operator=' must be a non-static member function. 216 const auto *InstCall = cast<CXXInstanceCall>(&Call); 217 if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) { 218 handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), 219 Call.getArgSVal(0)); 220 return; 221 } 222 223 handleAssign(C, InstCall->getCXXThisVal()); 224 return; 225 } else if (isSimpleComparisonOperator(Op)) { 226 const auto *OrigExpr = Call.getOriginExpr(); 227 if (!OrigExpr) 228 return; 229 230 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 231 handleComparison(C, OrigExpr, Call.getReturnValue(), 232 InstCall->getCXXThisVal(), Call.getArgSVal(0), Op); 233 return; 234 } 235 236 handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0), 237 Call.getArgSVal(1), Op); 238 return; 239 } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { 240 const auto *OrigExpr = Call.getOriginExpr(); 241 if (!OrigExpr) 242 return; 243 244 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 245 if (Call.getNumArgs() >= 1 && 246 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { 247 handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(), 248 Call.getReturnValue(), 249 InstCall->getCXXThisVal(), Call.getArgSVal(0)); 250 return; 251 } 252 } else { 253 if (Call.getNumArgs() >= 2 && 254 Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { 255 handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(), 256 Call.getReturnValue(), Call.getArgSVal(0), 257 Call.getArgSVal(1)); 258 return; 259 } 260 } 261 } else if (isIncrementOperator(Func->getOverloadedOperator())) { 262 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 263 handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), 264 Call.getNumArgs()); 265 return; 266 } 267 268 handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0), 269 Call.getNumArgs()); 270 return; 271 } else if (isDecrementOperator(Func->getOverloadedOperator())) { 272 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 273 handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), 274 Call.getNumArgs()); 275 return; 276 } 277 278 handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0), 279 Call.getNumArgs()); 280 return; 281 } 282 } else { 283 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 284 if (isAssignCall(Func)) { 285 handleAssign(C, InstCall->getCXXThisVal()); 286 return; 287 } 288 289 if (isClearCall(Func)) { 290 handleClear(C, InstCall->getCXXThisVal()); 291 return; 292 } 293 294 if (isPushBackCall(Func) || isEmplaceBackCall(Func)) { 295 handlePushBack(C, InstCall->getCXXThisVal()); 296 return; 297 } 298 299 if (isPopBackCall(Func)) { 300 handlePopBack(C, InstCall->getCXXThisVal()); 301 return; 302 } 303 304 if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) { 305 handlePushFront(C, InstCall->getCXXThisVal()); 306 return; 307 } 308 309 if (isPopFrontCall(Func)) { 310 handlePopFront(C, InstCall->getCXXThisVal()); 311 return; 312 } 313 314 if (isInsertCall(Func) || isEmplaceCall(Func)) { 315 handleInsert(C, Call.getArgSVal(0)); 316 return; 317 } 318 319 if (isEraseCall(Func)) { 320 if (Call.getNumArgs() == 1) { 321 handleErase(C, Call.getArgSVal(0)); 322 return; 323 } 324 325 if (Call.getNumArgs() == 2) { 326 handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1)); 327 return; 328 } 329 } 330 331 if (isEraseAfterCall(Func)) { 332 if (Call.getNumArgs() == 1) { 333 handleEraseAfter(C, Call.getArgSVal(0)); 334 return; 335 } 336 337 if (Call.getNumArgs() == 2) { 338 handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1)); 339 return; 340 } 341 } 342 } 343 344 const auto *OrigExpr = Call.getOriginExpr(); 345 if (!OrigExpr) 346 return; 347 348 if (!isIteratorType(Call.getResultType())) 349 return; 350 351 auto State = C.getState(); 352 353 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 354 if (isBeginCall(Func)) { 355 handleBegin(C, OrigExpr, Call.getReturnValue(), 356 InstCall->getCXXThisVal()); 357 return; 358 } 359 360 if (isEndCall(Func)) { 361 handleEnd(C, OrigExpr, Call.getReturnValue(), 362 InstCall->getCXXThisVal()); 363 return; 364 } 365 } 366 367 // Already bound to container? 368 if (getIteratorPosition(State, Call.getReturnValue())) 369 return; 370 371 // Copy-like and move constructors 372 if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) { 373 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) { 374 State = setIteratorPosition(State, Call.getReturnValue(), *Pos); 375 if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) { 376 State = removeIteratorPosition(State, Call.getArgSVal(0)); 377 } 378 C.addTransition(State); 379 return; 380 } 381 } 382 383 // Assumption: if return value is an iterator which is not yet bound to a 384 // container, then look for the first iterator argument, and 385 // bind the return value to the same container. This approach 386 // works for STL algorithms. 387 // FIXME: Add a more conservative mode 388 for (unsigned i = 0; i < Call.getNumArgs(); ++i) { 389 if (isIteratorType(Call.getArgExpr(i)->getType())) { 390 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) { 391 assignToContainer(C, OrigExpr, Call.getReturnValue(), 392 Pos->getContainer()); 393 return; 394 } 395 } 396 } 397 } 398 } 399 400 void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S, 401 CheckerContext &C) const { 402 auto State = C.getState(); 403 const auto *Pos = getIteratorPosition(State, Val); 404 if (Pos) { 405 State = setIteratorPosition(State, Loc, *Pos); 406 C.addTransition(State); 407 } else { 408 const auto *OldPos = getIteratorPosition(State, Loc); 409 if (OldPos) { 410 State = removeIteratorPosition(State, Loc); 411 C.addTransition(State); 412 } 413 } 414 } 415 416 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE, 417 CheckerContext &C) const { 418 /* Transfer iterator state to temporary objects */ 419 auto State = C.getState(); 420 const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr())); 421 if (!Pos) 422 return; 423 State = setIteratorPosition(State, C.getSVal(MTE), *Pos); 424 C.addTransition(State); 425 } 426 427 void IteratorModeling::checkLiveSymbols(ProgramStateRef State, 428 SymbolReaper &SR) const { 429 // Keep symbolic expressions of iterator positions, container begins and ends 430 // alive 431 auto RegionMap = State->get<IteratorRegionMap>(); 432 for (const auto &Reg : RegionMap) { 433 const auto Offset = Reg.second.getOffset(); 434 for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i) 435 if (isa<SymbolData>(*i)) 436 SR.markLive(*i); 437 } 438 439 auto SymbolMap = State->get<IteratorSymbolMap>(); 440 for (const auto &Sym : SymbolMap) { 441 const auto Offset = Sym.second.getOffset(); 442 for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i) 443 if (isa<SymbolData>(*i)) 444 SR.markLive(*i); 445 } 446 447 auto ContMap = State->get<ContainerMap>(); 448 for (const auto &Cont : ContMap) { 449 const auto CData = Cont.second; 450 if (CData.getBegin()) { 451 SR.markLive(CData.getBegin()); 452 if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin())) 453 SR.markLive(SIE->getLHS()); 454 } 455 if (CData.getEnd()) { 456 SR.markLive(CData.getEnd()); 457 if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd())) 458 SR.markLive(SIE->getLHS()); 459 } 460 } 461 } 462 463 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR, 464 CheckerContext &C) const { 465 // Cleanup 466 auto State = C.getState(); 467 468 auto RegionMap = State->get<IteratorRegionMap>(); 469 for (const auto &Reg : RegionMap) { 470 if (!SR.isLiveRegion(Reg.first)) { 471 // The region behind the `LazyCompoundVal` is often cleaned up before 472 // the `LazyCompoundVal` itself. If there are iterator positions keyed 473 // by these regions their cleanup must be deferred. 474 if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) { 475 State = State->remove<IteratorRegionMap>(Reg.first); 476 } 477 } 478 } 479 480 auto SymbolMap = State->get<IteratorSymbolMap>(); 481 for (const auto &Sym : SymbolMap) { 482 if (!SR.isLive(Sym.first)) { 483 State = State->remove<IteratorSymbolMap>(Sym.first); 484 } 485 } 486 487 auto ContMap = State->get<ContainerMap>(); 488 for (const auto &Cont : ContMap) { 489 if (!SR.isLiveRegion(Cont.first)) { 490 // We must keep the container data while it has live iterators to be able 491 // to compare them to the begin and the end of the container. 492 if (!hasLiveIterators(State, Cont.first)) { 493 State = State->remove<ContainerMap>(Cont.first); 494 } 495 } 496 } 497 498 C.addTransition(State); 499 } 500 501 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE, 502 SVal RetVal, const SVal &LVal, 503 const SVal &RVal, 504 OverloadedOperatorKind Op) const { 505 // Record the operands and the operator of the comparison for the next 506 // evalAssume, if the result is a symbolic expression. If it is a concrete 507 // value (only one branch is possible), then transfer the state between 508 // the operands according to the operator and the result 509 auto State = C.getState(); 510 const auto *LPos = getIteratorPosition(State, LVal); 511 const auto *RPos = getIteratorPosition(State, RVal); 512 const MemRegion *Cont = nullptr; 513 if (LPos) { 514 Cont = LPos->getContainer(); 515 } else if (RPos) { 516 Cont = RPos->getContainer(); 517 } 518 if (!Cont) 519 return; 520 521 // At least one of the iterators have recorded positions. If one of them has 522 // not then create a new symbol for the offset. 523 SymbolRef Sym; 524 if (!LPos || !RPos) { 525 auto &SymMgr = C.getSymbolManager(); 526 Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), 527 C.getASTContext().LongTy, C.blockCount()); 528 State = assumeNoOverflow(State, Sym, 4); 529 } 530 531 if (!LPos) { 532 State = setIteratorPosition(State, LVal, 533 IteratorPosition::getPosition(Cont, Sym)); 534 LPos = getIteratorPosition(State, LVal); 535 } else if (!RPos) { 536 State = setIteratorPosition(State, RVal, 537 IteratorPosition::getPosition(Cont, Sym)); 538 RPos = getIteratorPosition(State, RVal); 539 } 540 541 // We cannot make assumpotions on `UnknownVal`. Let us conjure a symbol 542 // instead. 543 if (RetVal.isUnknown()) { 544 auto &SymMgr = C.getSymbolManager(); 545 auto *LCtx = C.getLocationContext(); 546 RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol( 547 CE, LCtx, C.getASTContext().BoolTy, C.blockCount())); 548 State = State->BindExpr(CE, LCtx, RetVal); 549 } 550 551 processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op); 552 } 553 554 void IteratorModeling::processComparison(CheckerContext &C, 555 ProgramStateRef State, SymbolRef Sym1, 556 SymbolRef Sym2, const SVal &RetVal, 557 OverloadedOperatorKind Op) const { 558 if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) { 559 if ((State = relateSymbols(State, Sym1, Sym2, 560 (Op == OO_EqualEqual) == 561 (TruthVal->getValue() != 0)))) { 562 C.addTransition(State); 563 } else { 564 C.generateSink(State, C.getPredecessor()); 565 } 566 return; 567 } 568 569 const auto ConditionVal = RetVal.getAs<DefinedSVal>(); 570 if (!ConditionVal) 571 return; 572 573 if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) { 574 StateTrue = StateTrue->assume(*ConditionVal, true); 575 C.addTransition(StateTrue); 576 } 577 578 if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) { 579 StateFalse = StateFalse->assume(*ConditionVal, false); 580 C.addTransition(StateFalse); 581 } 582 } 583 584 void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal, 585 const SVal &Iter, bool Postfix) const { 586 // Increment the symbolic expressions which represents the position of the 587 // iterator 588 auto State = C.getState(); 589 auto &BVF = C.getSymbolManager().getBasicVals(); 590 591 const auto *Pos = getIteratorPosition(State, Iter); 592 if (!Pos) 593 return; 594 595 auto NewState = 596 advancePosition(State, Iter, OO_Plus, 597 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); 598 assert(NewState && 599 "Advancing position by concrete int should always be successful"); 600 601 const auto *NewPos = getIteratorPosition(NewState, Iter); 602 assert(NewPos && 603 "Iterator should have position after successful advancement"); 604 605 State = setIteratorPosition(State, Iter, *NewPos); 606 State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos); 607 C.addTransition(State); 608 } 609 610 void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal, 611 const SVal &Iter, bool Postfix) const { 612 // Decrement the symbolic expressions which represents the position of the 613 // iterator 614 auto State = C.getState(); 615 auto &BVF = C.getSymbolManager().getBasicVals(); 616 617 const auto *Pos = getIteratorPosition(State, Iter); 618 if (!Pos) 619 return; 620 621 auto NewState = 622 advancePosition(State, Iter, OO_Minus, 623 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); 624 assert(NewState && 625 "Advancing position by concrete int should always be successful"); 626 627 const auto *NewPos = getIteratorPosition(NewState, Iter); 628 assert(NewPos && 629 "Iterator should have position after successful advancement"); 630 631 State = setIteratorPosition(State, Iter, *NewPos); 632 State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos); 633 C.addTransition(State); 634 } 635 636 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, 637 const Expr *CE, 638 OverloadedOperatorKind Op, 639 const SVal &RetVal, 640 const SVal &LHS, 641 const SVal &RHS) const { 642 // Increment or decrement the symbolic expressions which represents the 643 // position of the iterator 644 auto State = C.getState(); 645 646 const auto *Pos = getIteratorPosition(State, LHS); 647 if (!Pos) 648 return; 649 650 const auto *value = &RHS; 651 if (auto loc = RHS.getAs<Loc>()) { 652 const auto val = State->getRawSVal(*loc); 653 value = &val; 654 } 655 656 auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal; 657 658 auto NewState = 659 advancePosition(State, LHS, Op, *value); 660 if (NewState) { 661 const auto *NewPos = getIteratorPosition(NewState, LHS); 662 assert(NewPos && 663 "Iterator should have position after successful advancement"); 664 665 State = setIteratorPosition(NewState, TgtVal, *NewPos); 666 C.addTransition(State); 667 } else { 668 assignToContainer(C, CE, TgtVal, Pos->getContainer()); 669 } 670 } 671 672 void IteratorModeling::handleBegin(CheckerContext &C, const Expr *CE, 673 const SVal &RetVal, const SVal &Cont) const { 674 const auto *ContReg = Cont.getAsRegion(); 675 if (!ContReg) 676 return; 677 678 ContReg = ContReg->getMostDerivedObjectRegion(); 679 680 // If the container already has a begin symbol then use it. Otherwise first 681 // create a new one. 682 auto State = C.getState(); 683 auto BeginSym = getContainerBegin(State, ContReg); 684 if (!BeginSym) { 685 State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy, 686 C.getLocationContext(), C.blockCount()); 687 BeginSym = getContainerBegin(State, ContReg); 688 } 689 State = setIteratorPosition(State, RetVal, 690 IteratorPosition::getPosition(ContReg, BeginSym)); 691 C.addTransition(State); 692 } 693 694 void IteratorModeling::handleEnd(CheckerContext &C, const Expr *CE, 695 const SVal &RetVal, const SVal &Cont) const { 696 const auto *ContReg = Cont.getAsRegion(); 697 if (!ContReg) 698 return; 699 700 ContReg = ContReg->getMostDerivedObjectRegion(); 701 702 // If the container already has an end symbol then use it. Otherwise first 703 // create a new one. 704 auto State = C.getState(); 705 auto EndSym = getContainerEnd(State, ContReg); 706 if (!EndSym) { 707 State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy, 708 C.getLocationContext(), C.blockCount()); 709 EndSym = getContainerEnd(State, ContReg); 710 } 711 State = setIteratorPosition(State, RetVal, 712 IteratorPosition::getPosition(ContReg, EndSym)); 713 C.addTransition(State); 714 } 715 716 void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE, 717 const SVal &RetVal, 718 const MemRegion *Cont) const { 719 Cont = Cont->getMostDerivedObjectRegion(); 720 721 auto State = C.getState(); 722 auto &SymMgr = C.getSymbolManager(); 723 auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), 724 C.getASTContext().LongTy, C.blockCount()); 725 State = assumeNoOverflow(State, Sym, 4); 726 State = setIteratorPosition(State, RetVal, 727 IteratorPosition::getPosition(Cont, Sym)); 728 C.addTransition(State); 729 } 730 731 void IteratorModeling::handleAssign(CheckerContext &C, const SVal &Cont, 732 const Expr *CE, const SVal &OldCont) const { 733 const auto *ContReg = Cont.getAsRegion(); 734 if (!ContReg) 735 return; 736 737 ContReg = ContReg->getMostDerivedObjectRegion(); 738 739 // Assignment of a new value to a container always invalidates all its 740 // iterators 741 auto State = C.getState(); 742 const auto CData = getContainerData(State, ContReg); 743 if (CData) { 744 State = invalidateAllIteratorPositions(State, ContReg); 745 } 746 747 // In case of move, iterators of the old container (except the past-end 748 // iterators) remain valid but refer to the new container 749 if (!OldCont.isUndef()) { 750 const auto *OldContReg = OldCont.getAsRegion(); 751 if (OldContReg) { 752 OldContReg = OldContReg->getMostDerivedObjectRegion(); 753 const auto OldCData = getContainerData(State, OldContReg); 754 if (OldCData) { 755 if (const auto OldEndSym = OldCData->getEnd()) { 756 // If we already assigned an "end" symbol to the old container, then 757 // first reassign all iterator positions to the new container which 758 // are not past the container (thus not greater or equal to the 759 // current "end" symbol). 760 State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg, 761 OldEndSym, BO_GE); 762 auto &SymMgr = C.getSymbolManager(); 763 auto &SVB = C.getSValBuilder(); 764 // Then generate and assign a new "end" symbol for the new container. 765 auto NewEndSym = 766 SymMgr.conjureSymbol(CE, C.getLocationContext(), 767 C.getASTContext().LongTy, C.blockCount()); 768 State = assumeNoOverflow(State, NewEndSym, 4); 769 if (CData) { 770 State = setContainerData(State, ContReg, CData->newEnd(NewEndSym)); 771 } else { 772 State = setContainerData(State, ContReg, 773 ContainerData::fromEnd(NewEndSym)); 774 } 775 // Finally, replace the old "end" symbol in the already reassigned 776 // iterator positions with the new "end" symbol. 777 State = rebaseSymbolInIteratorPositionsIf( 778 State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT); 779 } else { 780 // There was no "end" symbol assigned yet to the old container, 781 // so reassign all iterator positions to the new container. 782 State = reassignAllIteratorPositions(State, OldContReg, ContReg); 783 } 784 if (const auto OldBeginSym = OldCData->getBegin()) { 785 // If we already assigned a "begin" symbol to the old container, then 786 // assign it to the new container and remove it from the old one. 787 if (CData) { 788 State = 789 setContainerData(State, ContReg, CData->newBegin(OldBeginSym)); 790 } else { 791 State = setContainerData(State, ContReg, 792 ContainerData::fromBegin(OldBeginSym)); 793 } 794 State = 795 setContainerData(State, OldContReg, OldCData->newEnd(nullptr)); 796 } 797 } else { 798 // There was neither "begin" nor "end" symbol assigned yet to the old 799 // container, so reassign all iterator positions to the new container. 800 State = reassignAllIteratorPositions(State, OldContReg, ContReg); 801 } 802 } 803 } 804 C.addTransition(State); 805 } 806 807 void IteratorModeling::handleClear(CheckerContext &C, const SVal &Cont) const { 808 const auto *ContReg = Cont.getAsRegion(); 809 if (!ContReg) 810 return; 811 812 ContReg = ContReg->getMostDerivedObjectRegion(); 813 814 // The clear() operation invalidates all the iterators, except the past-end 815 // iterators of list-like containers 816 auto State = C.getState(); 817 if (!hasSubscriptOperator(State, ContReg) || 818 !backModifiable(State, ContReg)) { 819 const auto CData = getContainerData(State, ContReg); 820 if (CData) { 821 if (const auto EndSym = CData->getEnd()) { 822 State = 823 invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE); 824 C.addTransition(State); 825 return; 826 } 827 } 828 } 829 State = invalidateAllIteratorPositions(State, ContReg); 830 C.addTransition(State); 831 } 832 833 void IteratorModeling::handlePushBack(CheckerContext &C, 834 const SVal &Cont) const { 835 const auto *ContReg = Cont.getAsRegion(); 836 if (!ContReg) 837 return; 838 839 ContReg = ContReg->getMostDerivedObjectRegion(); 840 841 // For deque-like containers invalidate all iterator positions 842 auto State = C.getState(); 843 if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) { 844 State = invalidateAllIteratorPositions(State, ContReg); 845 C.addTransition(State); 846 return; 847 } 848 849 const auto CData = getContainerData(State, ContReg); 850 if (!CData) 851 return; 852 853 // For vector-like containers invalidate the past-end iterator positions 854 if (const auto EndSym = CData->getEnd()) { 855 if (hasSubscriptOperator(State, ContReg)) { 856 State = invalidateIteratorPositions(State, EndSym, BO_GE); 857 } 858 auto &SymMgr = C.getSymbolManager(); 859 auto &BVF = SymMgr.getBasicVals(); 860 auto &SVB = C.getSValBuilder(); 861 const auto newEndSym = 862 SVB.evalBinOp(State, BO_Add, 863 nonloc::SymbolVal(EndSym), 864 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), 865 SymMgr.getType(EndSym)).getAsSymbol(); 866 State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); 867 } 868 C.addTransition(State); 869 } 870 871 void IteratorModeling::handlePopBack(CheckerContext &C, 872 const SVal &Cont) const { 873 const auto *ContReg = Cont.getAsRegion(); 874 if (!ContReg) 875 return; 876 877 ContReg = ContReg->getMostDerivedObjectRegion(); 878 879 auto State = C.getState(); 880 const auto CData = getContainerData(State, ContReg); 881 if (!CData) 882 return; 883 884 if (const auto EndSym = CData->getEnd()) { 885 auto &SymMgr = C.getSymbolManager(); 886 auto &BVF = SymMgr.getBasicVals(); 887 auto &SVB = C.getSValBuilder(); 888 const auto BackSym = 889 SVB.evalBinOp(State, BO_Sub, 890 nonloc::SymbolVal(EndSym), 891 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), 892 SymMgr.getType(EndSym)).getAsSymbol(); 893 // For vector-like and deque-like containers invalidate the last and the 894 // past-end iterator positions. For list-like containers only invalidate 895 // the last position 896 if (hasSubscriptOperator(State, ContReg) && 897 backModifiable(State, ContReg)) { 898 State = invalidateIteratorPositions(State, BackSym, BO_GE); 899 State = setContainerData(State, ContReg, CData->newEnd(nullptr)); 900 } else { 901 State = invalidateIteratorPositions(State, BackSym, BO_EQ); 902 } 903 auto newEndSym = BackSym; 904 State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); 905 C.addTransition(State); 906 } 907 } 908 909 void IteratorModeling::handlePushFront(CheckerContext &C, 910 const SVal &Cont) const { 911 const auto *ContReg = Cont.getAsRegion(); 912 if (!ContReg) 913 return; 914 915 ContReg = ContReg->getMostDerivedObjectRegion(); 916 917 // For deque-like containers invalidate all iterator positions 918 auto State = C.getState(); 919 if (hasSubscriptOperator(State, ContReg)) { 920 State = invalidateAllIteratorPositions(State, ContReg); 921 C.addTransition(State); 922 } else { 923 const auto CData = getContainerData(State, ContReg); 924 if (!CData) 925 return; 926 927 if (const auto BeginSym = CData->getBegin()) { 928 auto &SymMgr = C.getSymbolManager(); 929 auto &BVF = SymMgr.getBasicVals(); 930 auto &SVB = C.getSValBuilder(); 931 const auto newBeginSym = 932 SVB.evalBinOp(State, BO_Sub, 933 nonloc::SymbolVal(BeginSym), 934 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), 935 SymMgr.getType(BeginSym)).getAsSymbol(); 936 State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); 937 C.addTransition(State); 938 } 939 } 940 } 941 942 void IteratorModeling::handlePopFront(CheckerContext &C, 943 const SVal &Cont) const { 944 const auto *ContReg = Cont.getAsRegion(); 945 if (!ContReg) 946 return; 947 948 ContReg = ContReg->getMostDerivedObjectRegion(); 949 950 auto State = C.getState(); 951 const auto CData = getContainerData(State, ContReg); 952 if (!CData) 953 return; 954 955 // For deque-like containers invalidate all iterator positions. For list-like 956 // iterators only invalidate the first position 957 if (const auto BeginSym = CData->getBegin()) { 958 if (hasSubscriptOperator(State, ContReg)) { 959 State = invalidateIteratorPositions(State, BeginSym, BO_LE); 960 } else { 961 State = invalidateIteratorPositions(State, BeginSym, BO_EQ); 962 } 963 auto &SymMgr = C.getSymbolManager(); 964 auto &BVF = SymMgr.getBasicVals(); 965 auto &SVB = C.getSValBuilder(); 966 const auto newBeginSym = 967 SVB.evalBinOp(State, BO_Add, 968 nonloc::SymbolVal(BeginSym), 969 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), 970 SymMgr.getType(BeginSym)).getAsSymbol(); 971 State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); 972 C.addTransition(State); 973 } 974 } 975 976 void IteratorModeling::handleInsert(CheckerContext &C, const SVal &Iter) const { 977 auto State = C.getState(); 978 const auto *Pos = getIteratorPosition(State, Iter); 979 if (!Pos) 980 return; 981 982 // For deque-like containers invalidate all iterator positions. For 983 // vector-like containers invalidate iterator positions after the insertion. 984 const auto *Cont = Pos->getContainer(); 985 if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { 986 if (frontModifiable(State, Cont)) { 987 State = invalidateAllIteratorPositions(State, Cont); 988 } else { 989 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); 990 } 991 if (const auto *CData = getContainerData(State, Cont)) { 992 if (const auto EndSym = CData->getEnd()) { 993 State = invalidateIteratorPositions(State, EndSym, BO_GE); 994 State = setContainerData(State, Cont, CData->newEnd(nullptr)); 995 } 996 } 997 C.addTransition(State); 998 } 999 } 1000 1001 void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter) const { 1002 auto State = C.getState(); 1003 const auto *Pos = getIteratorPosition(State, Iter); 1004 if (!Pos) 1005 return; 1006 1007 // For deque-like containers invalidate all iterator positions. For 1008 // vector-like containers invalidate iterator positions at and after the 1009 // deletion. For list-like containers only invalidate the deleted position. 1010 const auto *Cont = Pos->getContainer(); 1011 if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { 1012 if (frontModifiable(State, Cont)) { 1013 State = invalidateAllIteratorPositions(State, Cont); 1014 } else { 1015 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); 1016 } 1017 if (const auto *CData = getContainerData(State, Cont)) { 1018 if (const auto EndSym = CData->getEnd()) { 1019 State = invalidateIteratorPositions(State, EndSym, BO_GE); 1020 State = setContainerData(State, Cont, CData->newEnd(nullptr)); 1021 } 1022 } 1023 } else { 1024 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ); 1025 } 1026 C.addTransition(State); 1027 } 1028 1029 void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter1, 1030 const SVal &Iter2) const { 1031 auto State = C.getState(); 1032 const auto *Pos1 = getIteratorPosition(State, Iter1); 1033 const auto *Pos2 = getIteratorPosition(State, Iter2); 1034 if (!Pos1 || !Pos2) 1035 return; 1036 1037 // For deque-like containers invalidate all iterator positions. For 1038 // vector-like containers invalidate iterator positions at and after the 1039 // deletion range. For list-like containers only invalidate the deleted 1040 // position range [first..last]. 1041 const auto *Cont = Pos1->getContainer(); 1042 if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { 1043 if (frontModifiable(State, Cont)) { 1044 State = invalidateAllIteratorPositions(State, Cont); 1045 } else { 1046 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE); 1047 } 1048 if (const auto *CData = getContainerData(State, Cont)) { 1049 if (const auto EndSym = CData->getEnd()) { 1050 State = invalidateIteratorPositions(State, EndSym, BO_GE); 1051 State = setContainerData(State, Cont, CData->newEnd(nullptr)); 1052 } 1053 } 1054 } else { 1055 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE, 1056 Pos2->getOffset(), BO_LT); 1057 } 1058 C.addTransition(State); 1059 } 1060 1061 void IteratorModeling::handleEraseAfter(CheckerContext &C, 1062 const SVal &Iter) const { 1063 auto State = C.getState(); 1064 const auto *Pos = getIteratorPosition(State, Iter); 1065 if (!Pos) 1066 return; 1067 1068 // Invalidate the deleted iterator position, which is the position of the 1069 // parameter plus one. 1070 auto &SymMgr = C.getSymbolManager(); 1071 auto &BVF = SymMgr.getBasicVals(); 1072 auto &SVB = C.getSValBuilder(); 1073 const auto NextSym = 1074 SVB.evalBinOp(State, BO_Add, 1075 nonloc::SymbolVal(Pos->getOffset()), 1076 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), 1077 SymMgr.getType(Pos->getOffset())).getAsSymbol(); 1078 State = invalidateIteratorPositions(State, NextSym, BO_EQ); 1079 C.addTransition(State); 1080 } 1081 1082 void IteratorModeling::handleEraseAfter(CheckerContext &C, const SVal &Iter1, 1083 const SVal &Iter2) const { 1084 auto State = C.getState(); 1085 const auto *Pos1 = getIteratorPosition(State, Iter1); 1086 const auto *Pos2 = getIteratorPosition(State, Iter2); 1087 if (!Pos1 || !Pos2) 1088 return; 1089 1090 // Invalidate the deleted iterator position range (first..last) 1091 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT, 1092 Pos2->getOffset(), BO_LT); 1093 C.addTransition(State); 1094 } 1095 1096 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State, 1097 const char *NL, const char *Sep) const { 1098 1099 auto ContMap = State->get<ContainerMap>(); 1100 1101 if (!ContMap.isEmpty()) { 1102 Out << Sep << "Container Data :" << NL; 1103 for (const auto &Cont : ContMap) { 1104 Cont.first->dumpToStream(Out); 1105 Out << " : [ "; 1106 const auto CData = Cont.second; 1107 if (CData.getBegin()) 1108 CData.getBegin()->dumpToStream(Out); 1109 else 1110 Out << "<Unknown>"; 1111 Out << " .. "; 1112 if (CData.getEnd()) 1113 CData.getEnd()->dumpToStream(Out); 1114 else 1115 Out << "<Unknown>"; 1116 Out << " ]" << NL; 1117 } 1118 } 1119 1120 auto SymbolMap = State->get<IteratorSymbolMap>(); 1121 auto RegionMap = State->get<IteratorRegionMap>(); 1122 1123 if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) { 1124 Out << Sep << "Iterator Positions :" << NL; 1125 for (const auto &Sym : SymbolMap) { 1126 Sym.first->dumpToStream(Out); 1127 Out << " : "; 1128 const auto Pos = Sym.second; 1129 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == "; 1130 Pos.getContainer()->dumpToStream(Out); 1131 Out<<" ; Offset == "; 1132 Pos.getOffset()->dumpToStream(Out); 1133 } 1134 1135 for (const auto &Reg : RegionMap) { 1136 Reg.first->dumpToStream(Out); 1137 Out << " : "; 1138 const auto Pos = Reg.second; 1139 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == "; 1140 Pos.getContainer()->dumpToStream(Out); 1141 Out<<" ; Offset == "; 1142 Pos.getOffset()->dumpToStream(Out); 1143 } 1144 } 1145 } 1146 1147 1148 namespace { 1149 1150 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, 1151 const MemRegion *Reg); 1152 1153 bool isBeginCall(const FunctionDecl *Func) { 1154 const auto *IdInfo = Func->getIdentifier(); 1155 if (!IdInfo) 1156 return false; 1157 return IdInfo->getName().endswith_lower("begin"); 1158 } 1159 1160 bool isEndCall(const FunctionDecl *Func) { 1161 const auto *IdInfo = Func->getIdentifier(); 1162 if (!IdInfo) 1163 return false; 1164 return IdInfo->getName().endswith_lower("end"); 1165 } 1166 1167 bool isAssignCall(const FunctionDecl *Func) { 1168 const auto *IdInfo = Func->getIdentifier(); 1169 if (!IdInfo) 1170 return false; 1171 if (Func->getNumParams() > 2) 1172 return false; 1173 return IdInfo->getName() == "assign"; 1174 } 1175 1176 bool isClearCall(const FunctionDecl *Func) { 1177 const auto *IdInfo = Func->getIdentifier(); 1178 if (!IdInfo) 1179 return false; 1180 if (Func->getNumParams() > 0) 1181 return false; 1182 return IdInfo->getName() == "clear"; 1183 } 1184 1185 bool isPushBackCall(const FunctionDecl *Func) { 1186 const auto *IdInfo = Func->getIdentifier(); 1187 if (!IdInfo) 1188 return false; 1189 if (Func->getNumParams() != 1) 1190 return false; 1191 return IdInfo->getName() == "push_back"; 1192 } 1193 1194 bool isEmplaceBackCall(const FunctionDecl *Func) { 1195 const auto *IdInfo = Func->getIdentifier(); 1196 if (!IdInfo) 1197 return false; 1198 if (Func->getNumParams() < 1) 1199 return false; 1200 return IdInfo->getName() == "emplace_back"; 1201 } 1202 1203 bool isPopBackCall(const FunctionDecl *Func) { 1204 const auto *IdInfo = Func->getIdentifier(); 1205 if (!IdInfo) 1206 return false; 1207 if (Func->getNumParams() > 0) 1208 return false; 1209 return IdInfo->getName() == "pop_back"; 1210 } 1211 1212 bool isPushFrontCall(const FunctionDecl *Func) { 1213 const auto *IdInfo = Func->getIdentifier(); 1214 if (!IdInfo) 1215 return false; 1216 if (Func->getNumParams() != 1) 1217 return false; 1218 return IdInfo->getName() == "push_front"; 1219 } 1220 1221 bool isEmplaceFrontCall(const FunctionDecl *Func) { 1222 const auto *IdInfo = Func->getIdentifier(); 1223 if (!IdInfo) 1224 return false; 1225 if (Func->getNumParams() < 1) 1226 return false; 1227 return IdInfo->getName() == "emplace_front"; 1228 } 1229 1230 bool isPopFrontCall(const FunctionDecl *Func) { 1231 const auto *IdInfo = Func->getIdentifier(); 1232 if (!IdInfo) 1233 return false; 1234 if (Func->getNumParams() > 0) 1235 return false; 1236 return IdInfo->getName() == "pop_front"; 1237 } 1238 1239 bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } 1240 1241 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { 1242 return OK == OO_EqualEqual || OK == OO_ExclaimEqual; 1243 } 1244 1245 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) { 1246 const auto *CRD = getCXXRecordDecl(State, Reg); 1247 if (!CRD) 1248 return false; 1249 1250 for (const auto *Method : CRD->methods()) { 1251 if (!Method->isOverloadedOperator()) 1252 continue; 1253 const auto OPK = Method->getOverloadedOperator(); 1254 if (OPK == OO_Subscript) { 1255 return true; 1256 } 1257 } 1258 return false; 1259 } 1260 1261 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) { 1262 const auto *CRD = getCXXRecordDecl(State, Reg); 1263 if (!CRD) 1264 return false; 1265 1266 for (const auto *Method : CRD->methods()) { 1267 if (!Method->getDeclName().isIdentifier()) 1268 continue; 1269 if (Method->getName() == "push_front" || Method->getName() == "pop_front") { 1270 return true; 1271 } 1272 } 1273 return false; 1274 } 1275 1276 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) { 1277 const auto *CRD = getCXXRecordDecl(State, Reg); 1278 if (!CRD) 1279 return false; 1280 1281 for (const auto *Method : CRD->methods()) { 1282 if (!Method->getDeclName().isIdentifier()) 1283 continue; 1284 if (Method->getName() == "push_back" || Method->getName() == "pop_back") { 1285 return true; 1286 } 1287 } 1288 return false; 1289 } 1290 1291 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, 1292 const MemRegion *Reg) { 1293 auto TI = getDynamicTypeInfo(State, Reg); 1294 if (!TI.isValid()) 1295 return nullptr; 1296 1297 auto Type = TI.getType(); 1298 if (const auto *RefT = Type->getAs<ReferenceType>()) { 1299 Type = RefT->getPointeeType(); 1300 } 1301 1302 return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); 1303 } 1304 1305 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) { 1306 const auto *CDataPtr = getContainerData(State, Cont); 1307 if (!CDataPtr) 1308 return nullptr; 1309 1310 return CDataPtr->getBegin(); 1311 } 1312 1313 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) { 1314 const auto *CDataPtr = getContainerData(State, Cont); 1315 if (!CDataPtr) 1316 return nullptr; 1317 1318 return CDataPtr->getEnd(); 1319 } 1320 1321 ProgramStateRef createContainerBegin(ProgramStateRef State, 1322 const MemRegion *Cont, const Expr *E, 1323 QualType T, const LocationContext *LCtx, 1324 unsigned BlockCount) { 1325 // Only create if it does not exist 1326 const auto *CDataPtr = getContainerData(State, Cont); 1327 if (CDataPtr && CDataPtr->getBegin()) 1328 return State; 1329 1330 auto &SymMgr = State->getSymbolManager(); 1331 const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount, 1332 "begin"); 1333 State = assumeNoOverflow(State, Sym, 4); 1334 1335 if (CDataPtr) { 1336 const auto CData = CDataPtr->newBegin(Sym); 1337 return setContainerData(State, Cont, CData); 1338 } 1339 1340 const auto CData = ContainerData::fromBegin(Sym); 1341 return setContainerData(State, Cont, CData); 1342 } 1343 1344 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, 1345 const Expr *E, QualType T, 1346 const LocationContext *LCtx, 1347 unsigned BlockCount) { 1348 // Only create if it does not exist 1349 const auto *CDataPtr = getContainerData(State, Cont); 1350 if (CDataPtr && CDataPtr->getEnd()) 1351 return State; 1352 1353 auto &SymMgr = State->getSymbolManager(); 1354 const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount, 1355 "end"); 1356 State = assumeNoOverflow(State, Sym, 4); 1357 1358 if (CDataPtr) { 1359 const auto CData = CDataPtr->newEnd(Sym); 1360 return setContainerData(State, Cont, CData); 1361 } 1362 1363 const auto CData = ContainerData::fromEnd(Sym); 1364 return setContainerData(State, Cont, CData); 1365 } 1366 1367 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, 1368 const ContainerData &CData) { 1369 return State->set<ContainerMap>(Cont, CData); 1370 } 1371 1372 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) { 1373 if (auto Reg = Val.getAsRegion()) { 1374 Reg = Reg->getMostDerivedObjectRegion(); 1375 return State->remove<IteratorRegionMap>(Reg); 1376 } else if (const auto Sym = Val.getAsSymbol()) { 1377 return State->remove<IteratorSymbolMap>(Sym); 1378 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { 1379 return State->remove<IteratorRegionMap>(LCVal->getRegion()); 1380 } 1381 return nullptr; 1382 } 1383 1384 // This function tells the analyzer's engine that symbols produced by our 1385 // checker, most notably iterator positions, are relatively small. 1386 // A distance between items in the container should not be very large. 1387 // By assuming that it is within around 1/8 of the address space, 1388 // we can help the analyzer perform operations on these symbols 1389 // without being afraid of integer overflows. 1390 // FIXME: Should we provide it as an API, so that all checkers could use it? 1391 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, 1392 long Scale) { 1393 SValBuilder &SVB = State->getStateManager().getSValBuilder(); 1394 BasicValueFactory &BV = SVB.getBasicValueFactory(); 1395 1396 QualType T = Sym->getType(); 1397 assert(T->isSignedIntegerOrEnumerationType()); 1398 APSIntType AT = BV.getAPSIntType(T); 1399 1400 ProgramStateRef NewState = State; 1401 1402 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); 1403 SVal IsCappedFromAbove = 1404 SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), 1405 nonloc::ConcreteInt(Max), SVB.getConditionType()); 1406 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) { 1407 NewState = NewState->assume(*DV, true); 1408 if (!NewState) 1409 return State; 1410 } 1411 1412 llvm::APSInt Min = -Max; 1413 SVal IsCappedFromBelow = 1414 SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), 1415 nonloc::ConcreteInt(Min), SVB.getConditionType()); 1416 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) { 1417 NewState = NewState->assume(*DV, true); 1418 if (!NewState) 1419 return State; 1420 } 1421 1422 return NewState; 1423 } 1424 1425 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, 1426 SymbolRef Sym2, bool Equal) { 1427 auto &SVB = State->getStateManager().getSValBuilder(); 1428 1429 // FIXME: This code should be reworked as follows: 1430 // 1. Subtract the operands using evalBinOp(). 1431 // 2. Assume that the result doesn't overflow. 1432 // 3. Compare the result to 0. 1433 // 4. Assume the result of the comparison. 1434 const auto comparison = 1435 SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1), 1436 nonloc::SymbolVal(Sym2), SVB.getConditionType()); 1437 1438 assert(comparison.getAs<DefinedSVal>() && 1439 "Symbol comparison must be a `DefinedSVal`"); 1440 1441 auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal); 1442 if (!NewState) 1443 return nullptr; 1444 1445 if (const auto CompSym = comparison.getAsSymbol()) { 1446 assert(isa<SymIntExpr>(CompSym) && 1447 "Symbol comparison must be a `SymIntExpr`"); 1448 assert(BinaryOperator::isComparisonOp( 1449 cast<SymIntExpr>(CompSym)->getOpcode()) && 1450 "Symbol comparison must be a comparison"); 1451 return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2); 1452 } 1453 1454 return NewState; 1455 } 1456 1457 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) { 1458 auto RegionMap = State->get<IteratorRegionMap>(); 1459 for (const auto &Reg : RegionMap) { 1460 if (Reg.second.getContainer() == Cont) 1461 return true; 1462 } 1463 1464 auto SymbolMap = State->get<IteratorSymbolMap>(); 1465 for (const auto &Sym : SymbolMap) { 1466 if (Sym.second.getContainer() == Cont) 1467 return true; 1468 } 1469 1470 return false; 1471 } 1472 1473 bool isBoundThroughLazyCompoundVal(const Environment &Env, 1474 const MemRegion *Reg) { 1475 for (const auto &Binding : Env) { 1476 if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) { 1477 if (LCVal->getRegion() == Reg) 1478 return true; 1479 } 1480 } 1481 1482 return false; 1483 } 1484 1485 template <typename Condition, typename Process> 1486 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, 1487 Process Proc) { 1488 auto &RegionMapFactory = State->get_context<IteratorRegionMap>(); 1489 auto RegionMap = State->get<IteratorRegionMap>(); 1490 bool Changed = false; 1491 for (const auto &Reg : RegionMap) { 1492 if (Cond(Reg.second)) { 1493 RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second)); 1494 Changed = true; 1495 } 1496 } 1497 1498 if (Changed) 1499 State = State->set<IteratorRegionMap>(RegionMap); 1500 1501 auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>(); 1502 auto SymbolMap = State->get<IteratorSymbolMap>(); 1503 Changed = false; 1504 for (const auto &Sym : SymbolMap) { 1505 if (Cond(Sym.second)) { 1506 SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second)); 1507 Changed = true; 1508 } 1509 } 1510 1511 if (Changed) 1512 State = State->set<IteratorSymbolMap>(SymbolMap); 1513 1514 return State; 1515 } 1516 1517 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, 1518 const MemRegion *Cont) { 1519 auto MatchCont = [&](const IteratorPosition &Pos) { 1520 return Pos.getContainer() == Cont; 1521 }; 1522 auto Invalidate = [&](const IteratorPosition &Pos) { 1523 return Pos.invalidate(); 1524 }; 1525 return processIteratorPositions(State, MatchCont, Invalidate); 1526 } 1527 1528 ProgramStateRef 1529 invalidateAllIteratorPositionsExcept(ProgramStateRef State, 1530 const MemRegion *Cont, SymbolRef Offset, 1531 BinaryOperator::Opcode Opc) { 1532 auto MatchContAndCompare = [&](const IteratorPosition &Pos) { 1533 return Pos.getContainer() == Cont && 1534 !compare(State, Pos.getOffset(), Offset, Opc); 1535 }; 1536 auto Invalidate = [&](const IteratorPosition &Pos) { 1537 return Pos.invalidate(); 1538 }; 1539 return processIteratorPositions(State, MatchContAndCompare, Invalidate); 1540 } 1541 1542 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, 1543 SymbolRef Offset, 1544 BinaryOperator::Opcode Opc) { 1545 auto Compare = [&](const IteratorPosition &Pos) { 1546 return compare(State, Pos.getOffset(), Offset, Opc); 1547 }; 1548 auto Invalidate = [&](const IteratorPosition &Pos) { 1549 return Pos.invalidate(); 1550 }; 1551 return processIteratorPositions(State, Compare, Invalidate); 1552 } 1553 1554 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, 1555 SymbolRef Offset1, 1556 BinaryOperator::Opcode Opc1, 1557 SymbolRef Offset2, 1558 BinaryOperator::Opcode Opc2) { 1559 auto Compare = [&](const IteratorPosition &Pos) { 1560 return compare(State, Pos.getOffset(), Offset1, Opc1) && 1561 compare(State, Pos.getOffset(), Offset2, Opc2); 1562 }; 1563 auto Invalidate = [&](const IteratorPosition &Pos) { 1564 return Pos.invalidate(); 1565 }; 1566 return processIteratorPositions(State, Compare, Invalidate); 1567 } 1568 1569 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, 1570 const MemRegion *Cont, 1571 const MemRegion *NewCont) { 1572 auto MatchCont = [&](const IteratorPosition &Pos) { 1573 return Pos.getContainer() == Cont; 1574 }; 1575 auto ReAssign = [&](const IteratorPosition &Pos) { 1576 return Pos.reAssign(NewCont); 1577 }; 1578 return processIteratorPositions(State, MatchCont, ReAssign); 1579 } 1580 1581 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, 1582 const MemRegion *Cont, 1583 const MemRegion *NewCont, 1584 SymbolRef Offset, 1585 BinaryOperator::Opcode Opc) { 1586 auto MatchContAndCompare = [&](const IteratorPosition &Pos) { 1587 return Pos.getContainer() == Cont && 1588 !compare(State, Pos.getOffset(), Offset, Opc); 1589 }; 1590 auto ReAssign = [&](const IteratorPosition &Pos) { 1591 return Pos.reAssign(NewCont); 1592 }; 1593 return processIteratorPositions(State, MatchContAndCompare, ReAssign); 1594 } 1595 1596 // This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`, 1597 // `OldSym - Int` to `NewSym - Int` and `OldSym` to `NewSym` in any iterator 1598 // position offsets where `CondSym` is true. 1599 ProgramStateRef rebaseSymbolInIteratorPositionsIf( 1600 ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, 1601 SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) { 1602 auto LessThanEnd = [&](const IteratorPosition &Pos) { 1603 return compare(State, Pos.getOffset(), CondSym, Opc); 1604 }; 1605 auto RebaseSymbol = [&](const IteratorPosition &Pos) { 1606 return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym, 1607 NewSym)); 1608 }; 1609 return processIteratorPositions(State, LessThanEnd, RebaseSymbol); 1610 } 1611 1612 // This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`, 1613 // `OldExpr - Int` to `NewExpr - Int` and `OldExpr` to `NewExpr` in expression 1614 // `OrigExpr`. 1615 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, 1616 SymbolRef OrigExpr, SymbolRef OldExpr, 1617 SymbolRef NewSym) { 1618 auto &SymMgr = SVB.getSymbolManager(); 1619 auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr), 1620 nonloc::SymbolVal(OldExpr), 1621 SymMgr.getType(OrigExpr)); 1622 1623 const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>(); 1624 if (!DiffInt) 1625 return OrigExpr; 1626 1627 return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym), 1628 SymMgr.getType(OrigExpr)).getAsSymbol(); 1629 } 1630 1631 } // namespace 1632 1633 void ento::registerIteratorModeling(CheckerManager &mgr) { 1634 mgr.registerChecker<IteratorModeling>(); 1635 } 1636 1637 bool ento::shouldRegisterIteratorModeling(const LangOptions &LO) { 1638 return true; 1639 } 1640