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