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