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