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