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