clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp

   1 //===-- ContainerModeling.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 modeling-checker for modeling STL container-like containers.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/AST/DeclTemplate.h"
  14 #include "clang/Driver/DriverDiagnostic.h"
  15 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  17 #include "clang/StaticAnalyzer/Core/Checker.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  21 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
  22
  23 #include "Iterator.h"
  24
  25 #include <utility>
  26
  27 using namespace clang;
  28 using namespace ento;
  29 using namespace iterator;
  30
  31 namespace {
  32
  33 class ContainerModeling
  34   : public Checker<check::PostCall, check::LiveSymbols, check::DeadSymbols> {
  35
  36   void handleBegin(CheckerContext &C, const Expr *CE, SVal RetVal,
  37                    SVal Cont) const;
  38   void handleEnd(CheckerContext &C, const Expr *CE, SVal RetVal,
  39                  SVal Cont) const;
  40   void handleAssignment(CheckerContext &C, SVal Cont, const Expr *CE = nullptr,
  41                         SVal OldCont = UndefinedVal()) const;
  42   void handleAssign(CheckerContext &C, SVal Cont, const Expr *ContE) const;
  43   void handleClear(CheckerContext &C, SVal Cont, const Expr *ContE) const;
  44   void handlePushBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
  45   void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
  46   void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
  47   void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
  48   void handleInsert(CheckerContext &C, SVal Cont, SVal Iter) const;
  49   void handleErase(CheckerContext &C, SVal Cont, SVal Iter) const;
  50   void handleErase(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2) const;
  51   void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter) const;
  52   void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter1,
  53                         SVal Iter2) const;
  54   const NoteTag *getChangeTag(CheckerContext &C, StringRef Text,
  55                               const MemRegion *ContReg,
  56                               const Expr *ContE) const;
  57   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
  58                   const char *Sep) const override;
  59
  60 public:
  61   ContainerModeling() = default;
  62
  63   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
  64   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
  65   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
  66
  67   using NoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
  68                                                   const Expr *) const;
  69   using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
  70                                                    SVal) const;
  71   using TwoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal,
  72                                                    SVal) const;
  73
  74   CallDescriptionMap<NoItParamFn> NoIterParamFunctions = {
  75       {{{"clear"}, 0}, &ContainerModeling::handleClear},
  76       {{{"assign"}, 2}, &ContainerModeling::handleAssign},
  77       {{{"push_back"}, 1}, &ContainerModeling::handlePushBack},
  78       {{{"emplace_back"}, 1}, &ContainerModeling::handlePushBack},
  79       {{{"pop_back"}, 0}, &ContainerModeling::handlePopBack},
  80       {{{"push_front"}, 1}, &ContainerModeling::handlePushFront},
  81       {{{"emplace_front"}, 1}, &ContainerModeling::handlePushFront},
  82       {{{"pop_front"}, 0}, &ContainerModeling::handlePopFront},
  83   };
  84
  85   CallDescriptionMap<OneItParamFn> OneIterParamFunctions = {
  86       {{{"insert"}, 2}, &ContainerModeling::handleInsert},
  87       {{{"emplace"}, 2}, &ContainerModeling::handleInsert},
  88       {{{"erase"}, 1}, &ContainerModeling::handleErase},
  89       {{{"erase_after"}, 1}, &ContainerModeling::handleEraseAfter},
  90   };
  91
  92   CallDescriptionMap<TwoItParamFn> TwoIterParamFunctions = {
  93       {{{"erase"}, 2}, &ContainerModeling::handleErase},
  94       {{{"erase_after"}, 2}, &ContainerModeling::handleEraseAfter},
  95   };
  96 };
  97
  98 bool isBeginCall(const FunctionDecl *Func);
  99 bool isEndCall(const FunctionDecl *Func);
 100 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
 101 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
 102 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
 103 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
 104 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
 105 ProgramStateRef createContainerBegin(ProgramStateRef State,
 106                                      const MemRegion *Cont, const Expr *E,
 107                                      QualType T, const LocationContext *LCtx,
 108                                      unsigned BlockCount);
 109 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
 110                                    const Expr *E, QualType T,
 111                                    const LocationContext *LCtx,
 112                                    unsigned BlockCount);
 113 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
 114                                  const ContainerData &CData);
 115 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
 116                                                const MemRegion *Cont);
 117 ProgramStateRef
 118 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
 119                                      const MemRegion *Cont, SymbolRef Offset,
 120                                      BinaryOperator::Opcode Opc);
 121 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
 122                                             SymbolRef Offset,
 123                                             BinaryOperator::Opcode Opc);
 124 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
 125                                             SymbolRef Offset1,
 126                                             BinaryOperator::Opcode Opc1,
 127                                             SymbolRef Offset2,
 128                                             BinaryOperator::Opcode Opc2);
 129 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
 130                                              const MemRegion *Cont,
 131                                              const MemRegion *NewCont);
 132 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
 133                                                    const MemRegion *Cont,
 134                                                    const MemRegion *NewCont,
 135                                                    SymbolRef Offset,
 136                                                    BinaryOperator::Opcode Opc);
 137 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
 138     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
 139     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
 140 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
 141                         SymbolRef OldSym, SymbolRef NewSym);
 142 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
 143
 144 } // namespace
 145
 146 void ContainerModeling::checkPostCall(const CallEvent &Call,
 147                                      CheckerContext &C) const {
 148   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 149   if (!Func)
 150     return;
 151
 152   if (Func->isOverloadedOperator()) {
 153     const auto Op = Func->getOverloadedOperator();
 154     if (Op == OO_Equal) {
 155       // Overloaded 'operator=' must be a non-static member function.
 156       const auto *InstCall = cast<CXXInstanceCall>(&Call);
 157       if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) {
 158         handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
 159                      Call.getArgSVal(0));
 160         return;
 161       }
 162
 163       handleAssignment(C, InstCall->getCXXThisVal());
 164       return;
 165     }
 166   } else {
 167     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
 168       const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call);
 169       if (Handler0) {
 170         (this->**Handler0)(C, InstCall->getCXXThisVal(),
 171                            InstCall->getCXXThisExpr());
 172         return;
 173       }
 174
 175       const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call);
 176       if (Handler1) {
 177         (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
 178         return;
 179       }
 180
 181       const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call);
 182       if (Handler2) {
 183         (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0),
 184                            Call.getArgSVal(1));
 185         return;
 186       }
 187
 188       const auto *OrigExpr = Call.getOriginExpr();
 189       if (!OrigExpr)
 190         return;
 191
 192       if (isBeginCall(Func)) {
 193         handleBegin(C, OrigExpr, Call.getReturnValue(),
 194                     InstCall->getCXXThisVal());
 195         return;
 196       }
 197
 198       if (isEndCall(Func)) {
 199         handleEnd(C, OrigExpr, Call.getReturnValue(),
 200                   InstCall->getCXXThisVal());
 201         return;
 202       }
 203     }
 204   }
 205 }
 206
 207 void ContainerModeling::checkLiveSymbols(ProgramStateRef State,
 208                                          SymbolReaper &SR) const {
 209   // Keep symbolic expressions of container begins and ends alive
 210   auto ContMap = State->get<ContainerMap>();
 211   for (const auto &Cont : ContMap) {
 212     const auto CData = Cont.second;
 213     if (CData.getBegin()) {
 214       SR.markLive(CData.getBegin());
 215       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
 216         SR.markLive(SIE->getLHS());
 217     }
 218     if (CData.getEnd()) {
 219       SR.markLive(CData.getEnd());
 220       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
 221         SR.markLive(SIE->getLHS());
 222     }
 223   }
 224 }
 225
 226 void ContainerModeling::checkDeadSymbols(SymbolReaper &SR,
 227                                          CheckerContext &C) const {
 228   // Cleanup
 229   auto State = C.getState();
 230
 231   auto ContMap = State->get<ContainerMap>();
 232   for (const auto &Cont : ContMap) {
 233     if (!SR.isLiveRegion(Cont.first)) {
 234       // We must keep the container data while it has live iterators to be able
 235       // to compare them to the begin and the end of the container.
 236       if (!hasLiveIterators(State, Cont.first)) {
 237         State = State->remove<ContainerMap>(Cont.first);
 238       }
 239     }
 240   }
 241
 242   C.addTransition(State);
 243 }
 244
 245 void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE,
 246                                    SVal RetVal, SVal Cont) const {
 247   const auto *ContReg = Cont.getAsRegion();
 248   if (!ContReg)
 249     return;
 250
 251   ContReg = ContReg->getMostDerivedObjectRegion();
 252
 253   // If the container already has a begin symbol then use it. Otherwise first
 254   // create a new one.
 255   auto State = C.getState();
 256   auto BeginSym = getContainerBegin(State, ContReg);
 257   if (!BeginSym) {
 258     State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
 259                                  C.getLocationContext(), C.blockCount());
 260     BeginSym = getContainerBegin(State, ContReg);
 261   }
 262   State = setIteratorPosition(State, RetVal,
 263                               IteratorPosition::getPosition(ContReg, BeginSym));
 264   C.addTransition(State);
 265 }
 266
 267 void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE,
 268                                  SVal RetVal, SVal Cont) const {
 269   const auto *ContReg = Cont.getAsRegion();
 270   if (!ContReg)
 271     return;
 272
 273   ContReg = ContReg->getMostDerivedObjectRegion();
 274
 275   // If the container already has an end symbol then use it. Otherwise first
 276   // create a new one.
 277   auto State = C.getState();
 278   auto EndSym = getContainerEnd(State, ContReg);
 279   if (!EndSym) {
 280     State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
 281                                C.getLocationContext(), C.blockCount());
 282     EndSym = getContainerEnd(State, ContReg);
 283   }
 284   State = setIteratorPosition(State, RetVal,
 285                               IteratorPosition::getPosition(ContReg, EndSym));
 286   C.addTransition(State);
 287 }
 288
 289 void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont,
 290                                          const Expr *CE, SVal OldCont) const {
 291   const auto *ContReg = Cont.getAsRegion();
 292   if (!ContReg)
 293     return;
 294
 295   ContReg = ContReg->getMostDerivedObjectRegion();
 296
 297   // Assignment of a new value to a container always invalidates all its
 298   // iterators
 299   auto State = C.getState();
 300   const auto CData = getContainerData(State, ContReg);
 301   if (CData) {
 302     State = invalidateAllIteratorPositions(State, ContReg);
 303   }
 304
 305   // In case of move, iterators of the old container (except the past-end
 306   // iterators) remain valid but refer to the new container
 307   if (!OldCont.isUndef()) {
 308     const auto *OldContReg = OldCont.getAsRegion();
 309     if (OldContReg) {
 310       OldContReg = OldContReg->getMostDerivedObjectRegion();
 311       const auto OldCData = getContainerData(State, OldContReg);
 312       if (OldCData) {
 313         if (const auto OldEndSym = OldCData->getEnd()) {
 314           // If we already assigned an "end" symbol to the old container, then
 315           // first reassign all iterator positions to the new container which
 316           // are not past the container (thus not greater or equal to the
 317           // current "end" symbol).
 318           State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
 319                                                      OldEndSym, BO_GE);
 320           auto &SymMgr = C.getSymbolManager();
 321           auto &SVB = C.getSValBuilder();
 322           // Then generate and assign a new "end" symbol for the new container.
 323           auto NewEndSym =
 324               SymMgr.conjureSymbol(CE, C.getLocationContext(),
 325                                    C.getASTContext().LongTy, C.blockCount());
 326           State = assumeNoOverflow(State, NewEndSym, 4);
 327           if (CData) {
 328             State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
 329           } else {
 330             State = setContainerData(State, ContReg,
 331                                      ContainerData::fromEnd(NewEndSym));
 332           }
 333           // Finally, replace the old "end" symbol in the already reassigned
 334           // iterator positions with the new "end" symbol.
 335           State = rebaseSymbolInIteratorPositionsIf(
 336               State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
 337         } else {
 338           // There was no "end" symbol assigned yet to the old container,
 339           // so reassign all iterator positions to the new container.
 340           State = reassignAllIteratorPositions(State, OldContReg, ContReg);
 341         }
 342         if (const auto OldBeginSym = OldCData->getBegin()) {
 343           // If we already assigned a "begin" symbol to the old container, then
 344           // assign it to the new container and remove it from the old one.
 345           if (CData) {
 346             State =
 347                 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
 348           } else {
 349             State = setContainerData(State, ContReg,
 350                                      ContainerData::fromBegin(OldBeginSym));
 351           }
 352           State =
 353               setContainerData(State, OldContReg, OldCData->newBegin(nullptr));
 354         }
 355       } else {
 356         // There was neither "begin" nor "end" symbol assigned yet to the old
 357         // container, so reassign all iterator positions to the new container.
 358         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
 359       }
 360     }
 361   }
 362   C.addTransition(State);
 363 }
 364
 365 void ContainerModeling::handleAssign(CheckerContext &C, SVal Cont,
 366                                      const Expr *ContE) const {
 367   const auto *ContReg = Cont.getAsRegion();
 368   if (!ContReg)
 369     return;
 370
 371   ContReg = ContReg->getMostDerivedObjectRegion();
 372
 373   // The assign() operation invalidates all the iterators
 374   auto State = C.getState();
 375   State = invalidateAllIteratorPositions(State, ContReg);
 376   C.addTransition(State);
 377 }
 378
 379 void ContainerModeling::handleClear(CheckerContext &C, SVal Cont,
 380                                     const Expr *ContE) const {
 381   const auto *ContReg = Cont.getAsRegion();
 382   if (!ContReg)
 383     return;
 384
 385   ContReg = ContReg->getMostDerivedObjectRegion();
 386
 387   // The clear() operation invalidates all the iterators, except the past-end
 388   // iterators of list-like containers
 389   auto State = C.getState();
 390   if (!hasSubscriptOperator(State, ContReg) ||
 391       !backModifiable(State, ContReg)) {
 392     const auto CData = getContainerData(State, ContReg);
 393     if (CData) {
 394       if (const auto EndSym = CData->getEnd()) {
 395         State =
 396             invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
 397         C.addTransition(State);
 398         return;
 399       }
 400     }
 401   }
 402   const NoteTag *ChangeTag =
 403     getChangeTag(C, "became empty", ContReg, ContE);
 404   State = invalidateAllIteratorPositions(State, ContReg);
 405   C.addTransition(State, ChangeTag);
 406 }
 407
 408 void ContainerModeling::handlePushBack(CheckerContext &C, SVal Cont,
 409                                        const Expr *ContE) const {
 410   const auto *ContReg = Cont.getAsRegion();
 411   if (!ContReg)
 412     return;
 413
 414   ContReg = ContReg->getMostDerivedObjectRegion();
 415
 416   // For deque-like containers invalidate all iterator positions
 417   auto State = C.getState();
 418   if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
 419     State = invalidateAllIteratorPositions(State, ContReg);
 420     C.addTransition(State);
 421     return;
 422   }
 423
 424   const auto CData = getContainerData(State, ContReg);
 425   if (!CData)
 426     return;
 427
 428   // For vector-like containers invalidate the past-end iterator positions
 429   if (const auto EndSym = CData->getEnd()) {
 430     if (hasSubscriptOperator(State, ContReg)) {
 431       State = invalidateIteratorPositions(State, EndSym, BO_GE);
 432     }
 433     auto &SymMgr = C.getSymbolManager();
 434     auto &BVF = SymMgr.getBasicVals();
 435     auto &SVB = C.getSValBuilder();
 436     const auto newEndSym =
 437       SVB.evalBinOp(State, BO_Add,
 438                     nonloc::SymbolVal(EndSym),
 439                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 440                     SymMgr.getType(EndSym)).getAsSymbol();
 441     const NoteTag *ChangeTag =
 442       getChangeTag(C, "extended to the back by 1 position", ContReg, ContE);
 443     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
 444     C.addTransition(State, ChangeTag);
 445   }
 446 }
 447
 448 void ContainerModeling::handlePopBack(CheckerContext &C, SVal Cont,
 449                                       const Expr *ContE) const {
 450   const auto *ContReg = Cont.getAsRegion();
 451   if (!ContReg)
 452     return;
 453
 454   ContReg = ContReg->getMostDerivedObjectRegion();
 455
 456   auto State = C.getState();
 457   const auto CData = getContainerData(State, ContReg);
 458   if (!CData)
 459     return;
 460
 461   if (const auto EndSym = CData->getEnd()) {
 462     auto &SymMgr = C.getSymbolManager();
 463     auto &BVF = SymMgr.getBasicVals();
 464     auto &SVB = C.getSValBuilder();
 465     const auto BackSym =
 466       SVB.evalBinOp(State, BO_Sub,
 467                     nonloc::SymbolVal(EndSym),
 468                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 469                     SymMgr.getType(EndSym)).getAsSymbol();
 470     const NoteTag *ChangeTag =
 471       getChangeTag(C, "shrank from the back by 1 position", ContReg, ContE);
 472     // For vector-like and deque-like containers invalidate the last and the
 473     // past-end iterator positions. For list-like containers only invalidate
 474     // the last position
 475     if (hasSubscriptOperator(State, ContReg) &&
 476         backModifiable(State, ContReg)) {
 477       State = invalidateIteratorPositions(State, BackSym, BO_GE);
 478       State = setContainerData(State, ContReg, CData->newEnd(nullptr));
 479     } else {
 480       State = invalidateIteratorPositions(State, BackSym, BO_EQ);
 481     }
 482     auto newEndSym = BackSym;
 483     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
 484     C.addTransition(State, ChangeTag);
 485   }
 486 }
 487
 488 void ContainerModeling::handlePushFront(CheckerContext &C, SVal Cont,
 489                                         const Expr *ContE) const {
 490   const auto *ContReg = Cont.getAsRegion();
 491   if (!ContReg)
 492     return;
 493
 494   ContReg = ContReg->getMostDerivedObjectRegion();
 495
 496   // For deque-like containers invalidate all iterator positions
 497   auto State = C.getState();
 498   if (hasSubscriptOperator(State, ContReg)) {
 499     State = invalidateAllIteratorPositions(State, ContReg);
 500     C.addTransition(State);
 501   } else {
 502     const auto CData = getContainerData(State, ContReg);
 503     if (!CData)
 504       return;
 505
 506     if (const auto BeginSym = CData->getBegin()) {
 507       auto &SymMgr = C.getSymbolManager();
 508       auto &BVF = SymMgr.getBasicVals();
 509       auto &SVB = C.getSValBuilder();
 510       const auto newBeginSym =
 511         SVB.evalBinOp(State, BO_Sub,
 512                       nonloc::SymbolVal(BeginSym),
 513                       nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 514                       SymMgr.getType(BeginSym)).getAsSymbol();
 515       const NoteTag *ChangeTag =
 516         getChangeTag(C, "extended to the front by 1 position", ContReg, ContE);
 517       State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
 518       C.addTransition(State, ChangeTag);
 519     }
 520   }
 521 }
 522
 523 void ContainerModeling::handlePopFront(CheckerContext &C, SVal Cont,
 524                                        const Expr *ContE) const {
 525   const auto *ContReg = Cont.getAsRegion();
 526   if (!ContReg)
 527     return;
 528
 529   ContReg = ContReg->getMostDerivedObjectRegion();
 530
 531   auto State = C.getState();
 532   const auto CData = getContainerData(State, ContReg);
 533   if (!CData)
 534     return;
 535
 536   // For deque-like containers invalidate all iterator positions. For list-like
 537   // iterators only invalidate the first position
 538   if (const auto BeginSym = CData->getBegin()) {
 539     if (hasSubscriptOperator(State, ContReg)) {
 540       State = invalidateIteratorPositions(State, BeginSym, BO_LE);
 541     } else {
 542       State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
 543     }
 544     auto &SymMgr = C.getSymbolManager();
 545     auto &BVF = SymMgr.getBasicVals();
 546     auto &SVB = C.getSValBuilder();
 547     const auto newBeginSym =
 548       SVB.evalBinOp(State, BO_Add,
 549                     nonloc::SymbolVal(BeginSym),
 550                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 551                     SymMgr.getType(BeginSym)).getAsSymbol();
 552     const NoteTag *ChangeTag =
 553       getChangeTag(C, "shrank from the front by 1 position", ContReg, ContE);
 554     State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
 555     C.addTransition(State, ChangeTag);
 556   }
 557 }
 558
 559 void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont,
 560                                      SVal Iter) const {
 561   const auto *ContReg = Cont.getAsRegion();
 562   if (!ContReg)
 563     return;
 564
 565   ContReg = ContReg->getMostDerivedObjectRegion();
 566
 567   auto State = C.getState();
 568   const auto *Pos = getIteratorPosition(State, Iter);
 569   if (!Pos)
 570     return;
 571
 572   // For deque-like containers invalidate all iterator positions. For
 573   // vector-like containers invalidate iterator positions after the insertion.
 574   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
 575     if (frontModifiable(State, ContReg)) {
 576       State = invalidateAllIteratorPositions(State, ContReg);
 577     } else {
 578       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
 579     }
 580     if (const auto *CData = getContainerData(State, ContReg)) {
 581       if (const auto EndSym = CData->getEnd()) {
 582         State = invalidateIteratorPositions(State, EndSym, BO_GE);
 583         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
 584       }
 585     }
 586     C.addTransition(State);
 587   }
 588 }
 589
 590 void ContainerModeling::handleErase(CheckerContext &C, SVal Cont,
 591                                     SVal Iter) const {
 592   const auto *ContReg = Cont.getAsRegion();
 593   if (!ContReg)
 594     return;
 595
 596   ContReg = ContReg->getMostDerivedObjectRegion();
 597
 598   auto State = C.getState();
 599   const auto *Pos = getIteratorPosition(State, Iter);
 600   if (!Pos)
 601     return;
 602
 603   // For deque-like containers invalidate all iterator positions. For
 604   // vector-like containers invalidate iterator positions at and after the
 605   // deletion. For list-like containers only invalidate the deleted position.
 606   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
 607     if (frontModifiable(State, ContReg)) {
 608       State = invalidateAllIteratorPositions(State, ContReg);
 609     } else {
 610       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
 611     }
 612     if (const auto *CData = getContainerData(State, ContReg)) {
 613       if (const auto EndSym = CData->getEnd()) {
 614         State = invalidateIteratorPositions(State, EndSym, BO_GE);
 615         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
 616       }
 617     }
 618   } else {
 619     State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
 620   }
 621   C.addTransition(State);
 622 }
 623
 624 void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter1,
 625                                     SVal Iter2) const {
 626   const auto *ContReg = Cont.getAsRegion();
 627   if (!ContReg)
 628     return;
 629
 630   ContReg = ContReg->getMostDerivedObjectRegion();
 631   auto State = C.getState();
 632   const auto *Pos1 = getIteratorPosition(State, Iter1);
 633   const auto *Pos2 = getIteratorPosition(State, Iter2);
 634   if (!Pos1 || !Pos2)
 635     return;
 636
 637   // For deque-like containers invalidate all iterator positions. For
 638   // vector-like containers invalidate iterator positions at and after the
 639   // deletion range. For list-like containers only invalidate the deleted
 640   // position range [first..last].
 641   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
 642     if (frontModifiable(State, ContReg)) {
 643       State = invalidateAllIteratorPositions(State, ContReg);
 644     } else {
 645       State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
 646     }
 647     if (const auto *CData = getContainerData(State, ContReg)) {
 648       if (const auto EndSym = CData->getEnd()) {
 649         State = invalidateIteratorPositions(State, EndSym, BO_GE);
 650         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
 651       }
 652     }
 653   } else {
 654     State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
 655                                         Pos2->getOffset(), BO_LT);
 656   }
 657   C.addTransition(State);
 658 }
 659
 660 void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
 661                                         SVal Iter) const {
 662   auto State = C.getState();
 663   const auto *Pos = getIteratorPosition(State, Iter);
 664   if (!Pos)
 665     return;
 666
 667   // Invalidate the deleted iterator position, which is the position of the
 668   // parameter plus one.
 669   auto &SymMgr = C.getSymbolManager();
 670   auto &BVF = SymMgr.getBasicVals();
 671   auto &SVB = C.getSValBuilder();
 672   const auto NextSym =
 673     SVB.evalBinOp(State, BO_Add,
 674                   nonloc::SymbolVal(Pos->getOffset()),
 675                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
 676                   SymMgr.getType(Pos->getOffset())).getAsSymbol();
 677   State = invalidateIteratorPositions(State, NextSym, BO_EQ);
 678   C.addTransition(State);
 679 }
 680
 681 void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
 682                                          SVal Iter1, SVal Iter2) const {
 683   auto State = C.getState();
 684   const auto *Pos1 = getIteratorPosition(State, Iter1);
 685   const auto *Pos2 = getIteratorPosition(State, Iter2);
 686   if (!Pos1 || !Pos2)
 687     return;
 688
 689   // Invalidate the deleted iterator position range (first..last)
 690   State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
 691                                       Pos2->getOffset(), BO_LT);
 692   C.addTransition(State);
 693 }
 694
 695 const NoteTag *ContainerModeling::getChangeTag(CheckerContext &C,
 696                                                StringRef Text,
 697                                                const MemRegion *ContReg,
 698                                                const Expr *ContE) const {
 699   StringRef Name;
 700   // First try to get the name of the variable from the region
 701   if (const auto *DR = dyn_cast<DeclRegion>(ContReg)) {
 702     Name = DR->getDecl()->getName();
 703   // If the region is not a `DeclRegion` then use the expression instead
 704   } else if (const auto *DRE =
 705              dyn_cast<DeclRefExpr>(ContE->IgnoreParenCasts())) {
 706     Name = DRE->getDecl()->getName();
 707   }
 708
 709   return C.getNoteTag(
 710       [Text, Name, ContReg](PathSensitiveBugReport &BR) -> std::string {
 711         if (!BR.isInteresting(ContReg))
 712           return "";
 713
 714         SmallString<256> Msg;
 715         llvm::raw_svector_ostream Out(Msg);
 716         Out << "Container " << (!Name.empty() ? ("'" + Name.str() + "' ") : "" )
 717             << Text;
 718         return std::string(Out.str());
 719       });
 720 }
 721
 722 void ContainerModeling::printState(raw_ostream &Out, ProgramStateRef State,
 723                                   const char *NL, const char *Sep) const {
 724   auto ContMap = State->get<ContainerMap>();
 725
 726   if (!ContMap.isEmpty()) {
 727     Out << Sep << "Container Data :" << NL;
 728     for (const auto &Cont : ContMap) {
 729       Cont.first->dumpToStream(Out);
 730       Out << " : [ ";
 731       const auto CData = Cont.second;
 732       if (CData.getBegin())
 733         CData.getBegin()->dumpToStream(Out);
 734       else
 735         Out << "<Unknown>";
 736       Out << " .. ";
 737       if (CData.getEnd())
 738         CData.getEnd()->dumpToStream(Out);
 739       else
 740         Out << "<Unknown>";
 741       Out << " ]";
 742     }
 743   }
 744 }
 745
 746 namespace {
 747
 748 bool isBeginCall(const FunctionDecl *Func) {
 749   const auto *IdInfo = Func->getIdentifier();
 750   if (!IdInfo)
 751     return false;
 752   return IdInfo->getName().ends_with_insensitive("begin");
 753 }
 754
 755 bool isEndCall(const FunctionDecl *Func) {
 756   const auto *IdInfo = Func->getIdentifier();
 757   if (!IdInfo)
 758     return false;
 759   return IdInfo->getName().ends_with_insensitive("end");
 760 }
 761
 762 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
 763                                       const MemRegion *Reg) {
 764   auto TI = getDynamicTypeInfo(State, Reg);
 765   if (!TI.isValid())
 766     return nullptr;
 767
 768   auto Type = TI.getType();
 769   if (const auto *RefT = Type->getAs<ReferenceType>()) {
 770     Type = RefT->getPointeeType();
 771   }
 772
 773   return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
 774 }
 775
 776 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
 777   const auto *CRD = getCXXRecordDecl(State, Reg);
 778   if (!CRD)
 779     return false;
 780
 781   for (const auto *Method : CRD->methods()) {
 782     if (!Method->isOverloadedOperator())
 783       continue;
 784     const auto OPK = Method->getOverloadedOperator();
 785     if (OPK == OO_Subscript) {
 786       return true;
 787     }
 788   }
 789   return false;
 790 }
 791
 792 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
 793   const auto *CRD = getCXXRecordDecl(State, Reg);
 794   if (!CRD)
 795     return false;
 796
 797   for (const auto *Method : CRD->methods()) {
 798     if (!Method->getDeclName().isIdentifier())
 799       continue;
 800     if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
 801       return true;
 802     }
 803   }
 804   return false;
 805 }
 806
 807 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
 808   const auto *CRD = getCXXRecordDecl(State, Reg);
 809   if (!CRD)
 810     return false;
 811
 812   for (const auto *Method : CRD->methods()) {
 813     if (!Method->getDeclName().isIdentifier())
 814       continue;
 815     if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
 816       return true;
 817     }
 818   }
 819   return false;
 820 }
 821
 822 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
 823   const auto *CDataPtr = getContainerData(State, Cont);
 824   if (!CDataPtr)
 825     return nullptr;
 826
 827   return CDataPtr->getBegin();
 828 }
 829
 830 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
 831   const auto *CDataPtr = getContainerData(State, Cont);
 832   if (!CDataPtr)
 833     return nullptr;
 834
 835   return CDataPtr->getEnd();
 836 }
 837
 838 ProgramStateRef createContainerBegin(ProgramStateRef State,
 839                                      const MemRegion *Cont, const Expr *E,
 840                                      QualType T, const LocationContext *LCtx,
 841                                      unsigned BlockCount) {
 842   // Only create if it does not exist
 843   const auto *CDataPtr = getContainerData(State, Cont);
 844   if (CDataPtr && CDataPtr->getBegin())
 845     return State;
 846
 847   auto &SymMgr = State->getSymbolManager();
 848   const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
 849                                                    "begin");
 850   State = assumeNoOverflow(State, Sym, 4);
 851
 852   if (CDataPtr) {
 853     const auto CData = CDataPtr->newBegin(Sym);
 854     return setContainerData(State, Cont, CData);
 855   }
 856
 857   const auto CData = ContainerData::fromBegin(Sym);
 858   return setContainerData(State, Cont, CData);
 859 }
 860
 861 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
 862                                    const Expr *E, QualType T,
 863                                    const LocationContext *LCtx,
 864                                    unsigned BlockCount) {
 865   // Only create if it does not exist
 866   const auto *CDataPtr = getContainerData(State, Cont);
 867   if (CDataPtr && CDataPtr->getEnd())
 868     return State;
 869
 870   auto &SymMgr = State->getSymbolManager();
 871   const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
 872                                                   "end");
 873   State = assumeNoOverflow(State, Sym, 4);
 874
 875   if (CDataPtr) {
 876     const auto CData = CDataPtr->newEnd(Sym);
 877     return setContainerData(State, Cont, CData);
 878   }
 879
 880   const auto CData = ContainerData::fromEnd(Sym);
 881   return setContainerData(State, Cont, CData);
 882 }
 883
 884 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
 885                                  const ContainerData &CData) {
 886   return State->set<ContainerMap>(Cont, CData);
 887 }
 888
 889 template <typename Condition, typename Process>
 890 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
 891                                          Process Proc) {
 892   auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
 893   auto RegionMap = State->get<IteratorRegionMap>();
 894   bool Changed = false;
 895   for (const auto &Reg : RegionMap) {
 896     if (Cond(Reg.second)) {
 897       RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
 898       Changed = true;
 899     }
 900   }
 901
 902   if (Changed)
 903     State = State->set<IteratorRegionMap>(RegionMap);
 904
 905   auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
 906   auto SymbolMap = State->get<IteratorSymbolMap>();
 907   Changed = false;
 908   for (const auto &Sym : SymbolMap) {
 909     if (Cond(Sym.second)) {
 910       SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
 911       Changed = true;
 912     }
 913   }
 914
 915   if (Changed)
 916     State = State->set<IteratorSymbolMap>(SymbolMap);
 917
 918   return State;
 919 }
 920
 921 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
 922                                                const MemRegion *Cont) {
 923   auto MatchCont = [&](const IteratorPosition &Pos) {
 924     return Pos.getContainer() == Cont;
 925   };
 926   auto Invalidate = [&](const IteratorPosition &Pos) {
 927     return Pos.invalidate();
 928   };
 929   return processIteratorPositions(State, MatchCont, Invalidate);
 930 }
 931
 932 ProgramStateRef
 933 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
 934                                      const MemRegion *Cont, SymbolRef Offset,
 935                                      BinaryOperator::Opcode Opc) {
 936   auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
 937     return Pos.getContainer() == Cont &&
 938            !compare(State, Pos.getOffset(), Offset, Opc);
 939   };
 940   auto Invalidate = [&](const IteratorPosition &Pos) {
 941     return Pos.invalidate();
 942   };
 943   return processIteratorPositions(State, MatchContAndCompare, Invalidate);
 944 }
 945
 946 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
 947                                             SymbolRef Offset,
 948                                             BinaryOperator::Opcode Opc) {
 949   auto Compare = [&](const IteratorPosition &Pos) {
 950     return compare(State, Pos.getOffset(), Offset, Opc);
 951   };
 952   auto Invalidate = [&](const IteratorPosition &Pos) {
 953     return Pos.invalidate();
 954   };
 955   return processIteratorPositions(State, Compare, Invalidate);
 956 }
 957
 958 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
 959                                             SymbolRef Offset1,
 960                                             BinaryOperator::Opcode Opc1,
 961                                             SymbolRef Offset2,
 962                                             BinaryOperator::Opcode Opc2) {
 963   auto Compare = [&](const IteratorPosition &Pos) {
 964     return compare(State, Pos.getOffset(), Offset1, Opc1) &&
 965            compare(State, Pos.getOffset(), Offset2, Opc2);
 966   };
 967   auto Invalidate = [&](const IteratorPosition &Pos) {
 968     return Pos.invalidate();
 969   };
 970   return processIteratorPositions(State, Compare, Invalidate);
 971 }
 972
 973 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
 974                                              const MemRegion *Cont,
 975                                              const MemRegion *NewCont) {
 976   auto MatchCont = [&](const IteratorPosition &Pos) {
 977     return Pos.getContainer() == Cont;
 978   };
 979   auto ReAssign = [&](const IteratorPosition &Pos) {
 980     return Pos.reAssign(NewCont);
 981   };
 982   return processIteratorPositions(State, MatchCont, ReAssign);
 983 }
 984
 985 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
 986                                                    const MemRegion *Cont,
 987                                                    const MemRegion *NewCont,
 988                                                    SymbolRef Offset,
 989                                                    BinaryOperator::Opcode Opc) {
 990   auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
 991     return Pos.getContainer() == Cont &&
 992     !compare(State, Pos.getOffset(), Offset, Opc);
 993   };
 994   auto ReAssign = [&](const IteratorPosition &Pos) {
 995     return Pos.reAssign(NewCont);
 996   };
 997   return processIteratorPositions(State, MatchContAndCompare, ReAssign);
 998 }
 999
1000 // This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
1001 // `OldSym - Int` to `NewSym - Int` and  `OldSym` to `NewSym` in any iterator
1002 // position offsets where `CondSym` is true.
1003 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
1004     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
1005     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
1006   auto LessThanEnd = [&](const IteratorPosition &Pos) {
1007     return compare(State, Pos.getOffset(), CondSym, Opc);
1008   };
1009   auto RebaseSymbol = [&](const IteratorPosition &Pos) {
1010     return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
1011                                    NewSym));
1012   };
1013   return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
1014 }
1015
1016 // This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
1017 // `OldExpr - Int` to `NewExpr - Int` and  `OldExpr` to `NewExpr` in expression
1018 // `OrigExpr`.
1019 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
1020                        SymbolRef OrigExpr, SymbolRef OldExpr,
1021                        SymbolRef NewSym) {
1022   auto &SymMgr = SVB.getSymbolManager();
1023   auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
1024                               nonloc::SymbolVal(OldExpr),
1025                               SymMgr.getType(OrigExpr));
1026
1027   const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
1028   if (!DiffInt)
1029     return OrigExpr;
1030
1031   return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
1032                          SymMgr.getType(OrigExpr)).getAsSymbol();
1033 }
1034
1035 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
1036   auto RegionMap = State->get<IteratorRegionMap>();
1037   for (const auto &Reg : RegionMap) {
1038     if (Reg.second.getContainer() == Cont)
1039       return true;
1040   }
1041
1042   auto SymbolMap = State->get<IteratorSymbolMap>();
1043   for (const auto &Sym : SymbolMap) {
1044     if (Sym.second.getContainer() == Cont)
1045       return true;
1046   }
1047
1048   return false;
1049 }
1050
1051 } // namespace
1052
1053 void ento::registerContainerModeling(CheckerManager &mgr) {
1054   mgr.registerChecker<ContainerModeling>();
1055 }
1056
1057 bool ento::shouldRegisterContainerModeling(const CheckerManager &mgr) {
1058   if (!mgr.getLangOpts().CPlusPlus)
1059     return false;
1060
1061   if (!mgr.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation) {
1062     mgr.getASTContext().getDiagnostics().Report(
1063         diag::err_analyzer_checker_incompatible_analyzer_option)
1064       << "aggressive-binary-operation-simplification" << "false";
1065     return false;
1066   }
1067
1068   return true;
1069 }