clang  6.0.0svn
IteratorChecker.cpp
Go to the documentation of this file.
1 //===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Defines a checker for using iterators outside their range (past end). Usage
11 // means here dereferencing, incrementing etc.
12 //
13 //===----------------------------------------------------------------------===//
14 //
15 // In the code, iterator can be represented as a:
16 // * type-I: typedef-ed pointer. Operations over such iterator, such as
17 // comparisons or increments, are modeled straightforwardly by the
18 // analyzer.
19 // * type-II: structure with its method bodies available. Operations over such
20 // iterator are inlined by the analyzer, and results of modeling
21 // these operations are exposing implementation details of the
22 // iterators, which is not necessarily helping.
23 // * type-III: completely opaque structure. Operations over such iterator are
24 // modeled conservatively, producing conjured symbols everywhere.
25 //
26 // To handle all these types in a common way we introduce a structure called
27 // IteratorPosition which is an abstraction of the position the iterator
28 // represents using symbolic expressions. The checker handles all the
29 // operations on this structure.
30 //
31 // Additionally, depending on the circumstances, operators of types II and III
32 // can be represented as:
33 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
34 // from conservatively evaluated methods such as
35 // `.begin()`.
36 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
37 // variables or temporaries, when the iterator object is
38 // currently treated as an lvalue.
39 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
40 // iterator object is treated as an rvalue taken of a
41 // particular lvalue, eg. a copy of "type-a" iterator
42 // object, or an iterator that existed before the
43 // analysis has started.
44 //
45 // To handle any of these three different representations stored in an SVal we
46 // use setter and getters functions which separate the three cases. To store
47 // them we use a pointer union of symbol and memory region.
48 //
49 // The checker works the following way: We record the past-end iterator for
50 // all containers whenever their `.end()` is called. Since the Constraint
51 // Manager cannot handle SVals we need to take over its role. We post-check
52 // equality and non-equality comparisons and propagate the position of the
53 // iterator to the other side of the comparison if it is past-end and we are in
54 // the 'equal' branch (true-branch for `==` and false-branch for `!=`).
55 //
56 // In case of type-I or type-II iterators we get a concrete integer as a result
57 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
58 // this latter case we record the symbol and reload it in evalAssume() and do
59 // the propagation there. We also handle (maybe double) negated comparisons
60 // which are represented in the form of (x == 0 or x !=0 ) where x is the
61 // comparison itself.
62 
63 #include "ClangSACheckers.h"
68 
69 using namespace clang;
70 using namespace ento;
71 
72 namespace {
73 
74 // Abstract position of an iterator. This helps to handle all three kinds
75 // of operators in a common way by using a symbolic position.
76 struct IteratorPosition {
77 private:
78 
79  // Container the iterator belongs to
80  const MemRegion *Cont;
81 
82  // Abstract offset
84 
85  IteratorPosition(const MemRegion *C, SymbolRef Of)
86  : Cont(C), Offset(Of) {}
87 
88 public:
89  const MemRegion *getContainer() const { return Cont; }
90  SymbolRef getOffset() const { return Offset; }
91 
92  static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
93  return IteratorPosition(C, Of);
94  }
95 
96  IteratorPosition setTo(SymbolRef NewOf) const {
97  return IteratorPosition(Cont, NewOf);
98  }
99 
100  bool operator==(const IteratorPosition &X) const {
101  return Cont == X.Cont && Offset == X.Offset;
102  }
103 
104  bool operator!=(const IteratorPosition &X) const {
105  return Cont != X.Cont || Offset != X.Offset;
106  }
107 
108  void Profile(llvm::FoldingSetNodeID &ID) const {
109  ID.AddPointer(Cont);
110  ID.Add(Offset);
111  }
112 };
113 
114 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
115 
116 // Structure to record the symbolic end position of a container
117 struct ContainerData {
118 private:
119  SymbolRef End;
120 
121  ContainerData(SymbolRef E) : End(E) {}
122 
123 public:
124  static ContainerData fromEnd(SymbolRef E) {
125  return ContainerData(E);
126  }
127 
128  SymbolRef getEnd() const { return End; }
129 
130  ContainerData newEnd(SymbolRef E) const { return ContainerData(E); }
131 
132  bool operator==(const ContainerData &X) const {
133  return End == X.End;
134  }
135 
136  bool operator!=(const ContainerData &X) const {
137  return End != X.End;
138  }
139 
140  void Profile(llvm::FoldingSetNodeID &ID) const {
141  ID.Add(End);
142  }
143 };
144 
145 // Structure fo recording iterator comparisons. We needed to retrieve the
146 // original comparison expression in assumptions.
147 struct IteratorComparison {
148 private:
149  RegionOrSymbol Left, Right;
150  bool Equality;
151 
152 public:
153  IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
154  : Left(L), Right(R), Equality(Eq) {}
155 
156  RegionOrSymbol getLeft() const { return Left; }
157  RegionOrSymbol getRight() const { return Right; }
158  bool isEquality() const { return Equality; }
159  bool operator==(const IteratorComparison &X) const {
160  return Left == X.Left && Right == X.Right && Equality == X.Equality;
161  }
162  bool operator!=(const IteratorComparison &X) const {
163  return Left != X.Left || Right != X.Right || Equality != X.Equality;
164  }
165  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
166 };
167 
168 class IteratorChecker
169  : public Checker<check::PreCall, check::PostCall,
170  check::PostStmt<MaterializeTemporaryExpr>,
171  check::DeadSymbols,
172  eval::Assume> {
173 
174  std::unique_ptr<BugType> OutOfRangeBugType;
175 
176  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
177  const SVal &RVal, OverloadedOperatorKind Op) const;
178  void verifyDereference(CheckerContext &C, const SVal &Val) const;
179  void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
180  const SVal &Cont) const;
181  void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
182  const MemRegion *Cont) const;
183  void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
184  CheckerContext &C, ExplodedNode *ErrNode) const;
185 
186 public:
187  IteratorChecker();
188 
189  enum CheckKind {
190  CK_IteratorRangeChecker,
191  CK_NumCheckKinds
192  };
193 
194  DefaultBool ChecksEnabled[CK_NumCheckKinds];
195  CheckName CheckNames[CK_NumCheckKinds];
196 
197  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
198  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
199  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
200  CheckerContext &C) const;
201  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
202  ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
203  bool Assumption) const;
204 };
205 } // namespace
206 
207 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
208 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
209  IteratorPosition)
210 
211 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
212 
213 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
215 
216 namespace {
217 
218 bool isIteratorType(const QualType &Type);
219 bool isIterator(const CXXRecordDecl *CRD);
220 bool isEndCall(const FunctionDecl *Func);
224 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
226  RegionOrSymbol LVal,
227  RegionOrSymbol RVal, bool Equal);
229  const SymExpr *Condition, const SVal &LVal,
230  const SVal &RVal, bool Eq);
232  const SymExpr *Condition);
235  const SymbolRef Sym);
236 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
237  const SVal &Val);
238 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
239  RegionOrSymbol RegOrSym);
241  const IteratorPosition &Pos);
243  RegionOrSymbol RegOrSym,
244  const IteratorPosition &Pos);
247  RegionOrSymbol RegOrSym,
248  const IteratorPosition &Pos, bool Equal);
250  const IteratorPosition &Pos1,
251  const IteratorPosition &Pos2,
252  bool Equal);
253 const ContainerData *getContainerData(ProgramStateRef State,
254  const MemRegion *Cont);
256  const ContainerData &CData);
257 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
258 } // namespace
259 
260 IteratorChecker::IteratorChecker() {
261  OutOfRangeBugType.reset(
262  new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
263  OutOfRangeBugType->setSuppressOnSink(true);
264 }
265 
266 void IteratorChecker::checkPreCall(const CallEvent &Call,
267  CheckerContext &C) const {
268  // Check for out of range access
269  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
270  if (!Func)
271  return;
272 
273  if (Func->isOverloadedOperator()) {
274  if (ChecksEnabled[CK_IteratorRangeChecker] &&
275  isDereferenceOperator(Func->getOverloadedOperator())) {
276  // Check for dereference of out-of-range iterators
277  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
278  verifyDereference(C, InstCall->getCXXThisVal());
279  } else {
280  verifyDereference(C, Call.getArgSVal(0));
281  }
282  }
283  }
284 }
285 
286 void IteratorChecker::checkPostCall(const CallEvent &Call,
287  CheckerContext &C) const {
288  // Record new iterator positions and iterator position changes
289  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
290  if (!Func)
291  return;
292 
293  if (Func->isOverloadedOperator()) {
294  const auto Op = Func->getOverloadedOperator();
295  if (isSimpleComparisonOperator(Op)) {
296  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
297  handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
298  Call.getArgSVal(0), Op);
299  } else {
300  handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
301  Call.getArgSVal(1), Op);
302  }
303  }
304  } else {
305  const auto *OrigExpr = Call.getOriginExpr();
306  if (!OrigExpr)
307  return;
308 
309  if (!isIteratorType(Call.getResultType()))
310  return;
311 
312  auto State = C.getState();
313  // Already bound to container?
315  return;
316 
317  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
318  if (isEndCall(Func)) {
319  handleEnd(C, OrigExpr, Call.getReturnValue(),
320  InstCall->getCXXThisVal());
321  return;
322  }
323  }
324 
325  // Copy-like and move constructors
326  if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
327  if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
329  if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
331  }
332  C.addTransition(State);
333  return;
334  }
335  }
336 
337  // Assumption: if return value is an iterator which is not yet bound to a
338  // container, then look for the first iterator argument, and
339  // bind the return value to the same container. This approach
340  // works for STL algorithms.
341  // FIXME: Add a more conservative mode
342  for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
343  if (isIteratorType(Call.getArgExpr(i)->getType())) {
344  if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
345  assignToContainer(C, OrigExpr, Call.getReturnValue(),
346  Pos->getContainer());
347  return;
348  }
349  }
350  }
351  }
352 }
353 
354 void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
355  CheckerContext &C) const {
356  /* Transfer iterator state to temporary objects */
357  auto State = C.getState();
358  const auto *LCtx = C.getLocationContext();
359  const auto *Pos =
360  getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx));
361  if (!Pos)
362  return;
363  State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos);
364  C.addTransition(State);
365 }
366 
367 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
368  CheckerContext &C) const {
369  // Cleanup
370  auto State = C.getState();
371 
372  auto RegionMap = State->get<IteratorRegionMap>();
373  for (const auto Reg : RegionMap) {
374  if (!SR.isLiveRegion(Reg.first)) {
375  State = State->remove<IteratorRegionMap>(Reg.first);
376  }
377  }
378 
379  auto SymbolMap = State->get<IteratorSymbolMap>();
380  for (const auto Sym : SymbolMap) {
381  if (!SR.isLive(Sym.first)) {
382  State = State->remove<IteratorSymbolMap>(Sym.first);
383  }
384  }
385 
386  auto ContMap = State->get<ContainerMap>();
387  for (const auto Cont : ContMap) {
388  if (!SR.isLiveRegion(Cont.first)) {
389  State = State->remove<ContainerMap>(Cont.first);
390  }
391  }
392 
393  auto ComparisonMap = State->get<IteratorComparisonMap>();
394  for (const auto Comp : ComparisonMap) {
395  if (!SR.isLive(Comp.first)) {
396  State = State->remove<IteratorComparisonMap>(Comp.first);
397  }
398  }
399 }
400 
401 ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
402  bool Assumption) const {
403  // Load recorded comparison and transfer iterator state between sides
404  // according to comparison operator and assumption
405  const auto *SE = Cond.getAsSymExpr();
406  if (!SE)
407  return State;
408 
409  auto Opc = getOpcode(SE);
410  if (Opc != BO_EQ && Opc != BO_NE)
411  return State;
412 
413  bool Negated = false;
414  const auto *Comp = loadComparison(State, SE);
415  if (!Comp) {
416  // Try negated comparison, which is a SymExpr to 0 integer comparison
417  const auto *SIE = dyn_cast<SymIntExpr>(SE);
418  if (!SIE)
419  return State;
420 
421  if (SIE->getRHS() != 0)
422  return State;
423 
424  SE = SIE->getLHS();
425  Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
426  Opc = getOpcode(SE);
427  if (Opc != BO_EQ && Opc != BO_NE)
428  return State;
429 
430  Comp = loadComparison(State, SE);
431  if (!Comp)
432  return State;
433  }
434 
435  return processComparison(State, Comp->getLeft(), Comp->getRight(),
436  (Comp->isEquality() == Assumption) != Negated);
437 }
438 
439 void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
440  const SVal &LVal, const SVal &RVal,
441  OverloadedOperatorKind Op) const {
442  // Record the operands and the operator of the comparison for the next
443  // evalAssume, if the result is a symbolic expression. If it is a concrete
444  // value (only one branch is possible), then transfer the state between
445  // the operands according to the operator and the result
446  auto State = C.getState();
447  if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
448  const auto *LPos = getIteratorPosition(State, LVal);
449  const auto *RPos = getIteratorPosition(State, RVal);
450  if (!LPos && !RPos)
451  return;
452  State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
453  C.addTransition(State);
454  } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
455  if ((State = processComparison(
456  State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
457  (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
458  C.addTransition(State);
459  } else {
460  C.generateSink(State, C.getPredecessor());
461  }
462  }
463 }
464 
465 void IteratorChecker::verifyDereference(CheckerContext &C,
466  const SVal &Val) const {
467  auto State = C.getState();
468  const auto *Pos = getIteratorPosition(State, Val);
469  if (Pos && isOutOfRange(State, *Pos)) {
470  // If I do not put a tag here, some range tests will fail
471  static CheckerProgramPointTag Tag("IteratorRangeChecker",
472  "IteratorOutOfRange");
473  auto *N = C.generateNonFatalErrorNode(State, &Tag);
474  if (!N) {
475  return;
476  }
477  reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
478  }
479 }
480 
481 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
482  const SVal &RetVal, const SVal &Cont) const {
483  const auto *ContReg = Cont.getAsRegion();
484  if (!ContReg)
485  return;
486 
487  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
488  ContReg = CBOR->getSuperRegion();
489  }
490 
491  // If the container already has an end symbol then use it. Otherwise first
492  // create a new one.
493  auto State = C.getState();
494  auto EndSym = getContainerEnd(State, ContReg);
495  if (!EndSym) {
496  auto &SymMgr = C.getSymbolManager();
497  EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
498  C.getASTContext().LongTy, C.blockCount());
499  State = createContainerEnd(State, ContReg, EndSym);
500  }
501  State = setIteratorPosition(State, RetVal,
502  IteratorPosition::getPosition(ContReg, EndSym));
503  C.addTransition(State);
504 }
505 
506 void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
507  const SVal &RetVal,
508  const MemRegion *Cont) const {
509  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
510  Cont = CBOR->getSuperRegion();
511  }
512 
513  auto State = C.getState();
514  auto &SymMgr = C.getSymbolManager();
515  auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
516  C.getASTContext().LongTy, C.blockCount());
517  State = setIteratorPosition(State, RetVal,
518  IteratorPosition::getPosition(Cont, Sym));
519  C.addTransition(State);
520 }
521 
522 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
523  const SVal &Val, CheckerContext &C,
524  ExplodedNode *ErrNode) const {
525  auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
526  R->markInteresting(Val);
527  C.emitReport(std::move(R));
528 }
529 
530 namespace {
531 
532 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
533 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
535 
536 bool isIteratorType(const QualType &Type) {
537  if (Type->isPointerType())
538  return true;
539 
540  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
541  return isIterator(CRD);
542 }
543 
544 bool isIterator(const CXXRecordDecl *CRD) {
545  if (!CRD)
546  return false;
547 
548  const auto Name = CRD->getName();
549  if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
550  Name.endswith_lower("it")))
551  return false;
552 
553  bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
554  HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
555  for (const auto *Method : CRD->methods()) {
556  if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
557  if (Ctor->isCopyConstructor()) {
558  HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
559  }
560  continue;
561  }
562  if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
563  HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
564  continue;
565  }
566  if (Method->isCopyAssignmentOperator()) {
567  HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
568  continue;
569  }
570  if (!Method->isOverloadedOperator())
571  continue;
572  const auto OPK = Method->getOverloadedOperator();
573  if (OPK == OO_PlusPlus) {
574  HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
575  HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
576  continue;
577  }
578  if (OPK == OO_Star) {
579  HasDerefOp = (Method->getNumParams() == 0);
580  continue;
581  }
582  }
583 
584  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
585  HasPostIncrOp && HasDerefOp;
586 }
587 
588 bool isEndCall(const FunctionDecl *Func) {
589  const auto *IdInfo = Func->getIdentifier();
590  if (!IdInfo)
591  return false;
592  return IdInfo->getName().endswith_lower("end");
593 }
594 
596  return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
597 }
598 
600  return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
601  OK == OO_Subscript;
602 }
603 
605  if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
606  return BSE->getOpcode();
607  } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
608  const auto *COE = dyn_cast<CXXOperatorCallExpr>(SC->getStmt());
609  if (!COE)
610  return BO_Comma; // Extremal value, neither EQ nor NE
611  if (COE->getOperator() == OO_EqualEqual) {
612  return BO_EQ;
613  } else if (COE->getOperator() == OO_ExclaimEqual) {
614  return BO_NE;
615  }
616  return BO_Comma; // Extremal value, neither EQ nor NE
617  }
618  return BO_Comma; // Extremal value, neither EQ nor NE
619 }
620 
621 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
622  if (const auto Reg = Val.getAsRegion()) {
623  return Reg;
624  } else if (const auto Sym = Val.getAsSymbol()) {
625  return Sym;
626  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
627  return LCVal->getRegion();
628  }
629  return RegionOrSymbol();
630 }
631 
633  RegionOrSymbol LVal,
634  RegionOrSymbol RVal, bool Equal) {
635  const auto *LPos = getIteratorPosition(State, LVal);
636  const auto *RPos = getIteratorPosition(State, RVal);
637  if (LPos && !RPos) {
638  State = adjustIteratorPosition(State, RVal, *LPos, Equal);
639  } else if (!LPos && RPos) {
640  State = adjustIteratorPosition(State, LVal, *RPos, Equal);
641  } else if (LPos && RPos) {
642  State = relateIteratorPositions(State, *LPos, *RPos, Equal);
643  }
644  return State;
645 }
646 
648  const SymExpr *Condition, const SVal &LVal,
649  const SVal &RVal, bool Eq) {
650  const auto Left = getRegionOrSymbol(LVal);
651  const auto Right = getRegionOrSymbol(RVal);
652  if (!Left || !Right)
653  return State;
654  return State->set<IteratorComparisonMap>(Condition,
655  IteratorComparison(Left, Right, Eq));
656 }
657 
659  const SymExpr *Condition) {
660  return State->get<IteratorComparisonMap>(Condition);
661 }
662 
664  const auto *CDataPtr = getContainerData(State, Cont);
665  if (!CDataPtr)
666  return nullptr;
667 
668  return CDataPtr->getEnd();
669 }
670 
672  const SymbolRef Sym) {
673  // Only create if it does not exist
674  const auto *CDataPtr = getContainerData(State, Cont);
675  if (CDataPtr) {
676  if (CDataPtr->getEnd()) {
677  return State;
678  } else {
679  const auto CData = CDataPtr->newEnd(Sym);
680  return setContainerData(State, Cont, CData);
681  }
682  } else {
683  const auto CData = ContainerData::fromEnd(Sym);
684  return setContainerData(State, Cont, CData);
685  }
686 }
687 
688 const ContainerData *getContainerData(ProgramStateRef State,
689  const MemRegion *Cont) {
690  return State->get<ContainerMap>(Cont);
691 }
692 
694  const ContainerData &CData) {
695  return State->set<ContainerMap>(Cont, CData);
696 }
697 
698 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
699  const SVal &Val) {
700  if (const auto Reg = Val.getAsRegion()) {
701  return State->get<IteratorRegionMap>(Reg);
702  } else if (const auto Sym = Val.getAsSymbol()) {
703  return State->get<IteratorSymbolMap>(Sym);
704  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
705  return State->get<IteratorRegionMap>(LCVal->getRegion());
706  }
707  return nullptr;
708 }
709 
710 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
711  RegionOrSymbol RegOrSym) {
712  if (RegOrSym.is<const MemRegion *>()) {
713  return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
714  } else if (RegOrSym.is<SymbolRef>()) {
715  return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
716  }
717  return nullptr;
718 }
719 
721  const IteratorPosition &Pos) {
722  if (const auto Reg = Val.getAsRegion()) {
723  return State->set<IteratorRegionMap>(Reg, Pos);
724  } else if (const auto Sym = Val.getAsSymbol()) {
725  return State->set<IteratorSymbolMap>(Sym, Pos);
726  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
727  return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
728  }
729  return nullptr;
730 }
731 
733  RegionOrSymbol RegOrSym,
734  const IteratorPosition &Pos) {
735  if (RegOrSym.is<const MemRegion *>()) {
736  return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
737  Pos);
738  } else if (RegOrSym.is<SymbolRef>()) {
739  return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
740  }
741  return nullptr;
742 }
743 
745  if (const auto Reg = Val.getAsRegion()) {
746  return State->remove<IteratorRegionMap>(Reg);
747  } else if (const auto Sym = Val.getAsSymbol()) {
748  return State->remove<IteratorSymbolMap>(Sym);
749  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
750  return State->remove<IteratorRegionMap>(LCVal->getRegion());
751  }
752  return nullptr;
753 }
754 
756  RegionOrSymbol RegOrSym,
757  const IteratorPosition &Pos,
758  bool Equal) {
759  if (Equal) {
760  return setIteratorPosition(State, RegOrSym, Pos);
761  } else {
762  return State;
763  }
764 }
765 
767  const IteratorPosition &Pos1,
768  const IteratorPosition &Pos2,
769  bool Equal) {
770  // Try to compare them and get a defined value
771  auto &SVB = State->getStateManager().getSValBuilder();
772  const auto comparison =
773  SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
774  nonloc::SymbolVal(Pos2.getOffset()), SVB.getConditionType())
775  .getAs<DefinedSVal>();
776  if (comparison) {
777  return State->assume(*comparison, Equal);
778  }
779 
780  return State;
781 }
782 
783 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
784  const auto *Cont = Pos.getContainer();
785  const auto *CData = getContainerData(State, Cont);
786  if (!CData)
787  return false;
788 
789  // Out of range means less than the begin symbol or greater or equal to the
790  // end symbol.
791 
792  const auto End = CData->getEnd();
793  if (End) {
794  if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
795  return true;
796  }
797  }
798 
799  return false;
800 }
801 
802 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
803  return compare(State, Sym1, Sym2, BO_GE);
804 }
805 
806 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
808  auto &SMgr = State->getStateManager();
809  auto &SVB = SMgr.getSValBuilder();
810 
811  const auto comparison =
812  SVB.evalBinOp(State, Opc, nonloc::SymbolVal(Sym1),
813  nonloc::SymbolVal(Sym2), SVB.getConditionType())
814  .getAs<DefinedSVal>();
815 
816  if(comparison) {
817  return !!State->assume(*comparison, true);
818  }
819 
820  return false;
821 }
822 
823 } // namespace
824 
825 #define REGISTER_CHECKER(name) \
826  void ento::register##name(CheckerManager &Mgr) { \
827  auto *checker = Mgr.registerChecker<IteratorChecker>(); \
828  checker->ChecksEnabled[IteratorChecker::CK_##name] = true; \
829  checker->CheckNames[IteratorChecker::CK_##name] = \
830  Mgr.getCurrentCheckName(); \
831  }
832 
833 REGISTER_CHECKER(IteratorRangeChecker)
A call to an overloaded operator written using operator syntax.
Definition: ExprCXX.h:78
const ProgramStateRef processComparison(ProgramStateRef State, RegionOrSymbol LVal, RegionOrSymbol RVal, bool Equal)
FunctionDecl - An instance of this class is created to represent a function declaration or definition...
Definition: Decl.h:1698
A (possibly-)qualified type.
Definition: Type.h:653
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:79
SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont)
bool isSimpleComparisonOperator(OverloadedOperatorKind OK)
bool operator==(CanQual< T > x, CanQual< U > y)
REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *, IteratorPosition) REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap
A helper class which wraps a boolean value set to false by default.
Definition: Checker.h:551
ExplodedNode * addTransition(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generates a new transition in the program state graph (ExplodedGraph).
The base class of the type hierarchy.
Definition: Type.h:1353
CanQualType LongTy
Definition: ASTContext.h:1004
bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos)
Represents a prvalue temporary that is written into memory so that a reference can bind to it...
Definition: ExprCXX.h:4035
Value representing integer constant.
Definition: SVals.h:353
const Expr * getOriginExpr() const
Returns the expression whose value will be the result of this call.
Definition: CallEvent.h:225
ExplodedNode * getPredecessor()
Returns the previous node in the exploded graph, which includes the state of the program before the c...
Symbolic value.
Definition: SymExpr.h:29
IdentifierInfo * getIdentifier() const
getIdentifier - Get the identifier that names this declaration, if there is one.
Definition: Decl.h:265
Expr * GetTemporaryExpr() const
Retrieve the temporary-generating subexpression whose value will be materialized into a glvalue...
Definition: ExprCXX.h:4076
LineState State
ProgramStateRef adjustIteratorPosition(ProgramStateRef State, RegionOrSymbol RegOrSym, const IteratorPosition &Pos, bool Equal)
virtual const Expr * getArgExpr(unsigned Index) const
Returns the expression associated with a given argument.
Definition: CallEvent.h:275
const SymExpr * getAsSymbolicExpression() const
getAsSymbolicExpression - If this Sval wraps a symbolic expression then return that expression...
Definition: SVals.cpp:126
BinaryOperatorKind
uint32_t Offset
Definition: CacheTokens.cpp:43
bool isLiveRegion(const MemRegion *region)
SVal getReturnValue() const
Returns the return value of the call.
Definition: CallEvent.cpp:242
Represents a symbolic expression like &#39;x&#39; + 3.
bool isEndCall(const FunctionDecl *Func)
const Type * getUnqualifiedDesugaredType() const
Return the specified type with any "sugar" removed from the type, removing any typedefs, typeofs, etc., as well as any qualifiers.
Definition: Type.cpp:379
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition: SVals.cpp:116
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition: Type.cpp:1590
const IteratorPosition * getIteratorPosition(ProgramStateRef State, RegionOrSymbol RegOrSym)
const RegionTy * getAs() const
Definition: MemRegion.h:1174
Expr - This represents one expression.
Definition: Expr.h:106
SourceLocation End
static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y)
bool isDereferenceOperator(OverloadedOperatorKind OK)
SymbolManager & getSymbolManager()
ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, const SymbolRef Sym)
QualType getType() const
Definition: Expr.h:128
virtual const Decl * getDecl() const
Returns the declaration of the function or method that will be called.
Definition: CallEvent.h:205
ExplodedNode * generateNonFatalErrorNode(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generate a transition to a node that will be used to report an error.
Optional< T > getAs() const
Convert to the specified SVal type, returning None if this SVal is not of the desired type...
Definition: SVals.h:100
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
void emitReport(std::unique_ptr< BugReport > R)
Emit the diagnostics report.
ExplodedNode * generateSink(ProgramStateRef State, ExplodedNode *Pred, const ProgramPointTag *Tag=nullptr)
Generate a sink node.
ProgramStateRef setIteratorPosition(ProgramStateRef State, RegionOrSymbol RegOrSym, const IteratorPosition &Pos)
const MemRegion * getAsRegion() const
Definition: SVals.cpp:140
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:63
A class responsible for cleaning up unused symbols.
ProgramStateRef relateIteratorPositions(ProgramStateRef State, const IteratorPosition &Pos1, const IteratorPosition &Pos2, bool Equal)
const IteratorComparison * loadComparison(ProgramStateRef State, const SymExpr *Condition)
unsigned blockCount() const
Returns the number of times the current block has been visited along the analyzed path...
StringRef getName() const
Return the actual identifier string.
Dataflow Directional Tag Classes.
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
Definition: OperatorKinds.h:22
#define REGISTER_CHECKER(name)
BinaryOperator::Opcode getOpcode(const SymExpr *SE)
Represents symbolic expression.
Definition: SVals.h:327
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:140
const SymbolConjured * conjureSymbol(const Stmt *E, const LocationContext *LCtx, QualType T, unsigned VisitCount, const void *SymbolTag=nullptr)
bool isIteratorType(const QualType &Type)
ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val)
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, const ContainerData &CData)
const ProgramStateRef & getState() const
const ProgramStateRef saveComparison(ProgramStateRef State, const SymExpr *Condition, const SVal &LVal, const SVal &RVal, bool Eq)
const SymExpr * getAsSymExpr() const
Definition: SVals.cpp:133
QualType getResultType() const
Returns the result type, adjusted for references.
Definition: CallEvent.cpp:31
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13010
Represents a C++ struct/union/class.
Definition: DeclCXX.h:299
const RegionOrSymbol getRegionOrSymbol(const SVal &Val)
bool operator!=(CanQual< T > x, CanQual< U > y)
virtual unsigned getNumArgs() const =0
Returns the number of arguments (explicit and implicit).
StringRef getName() const
getName - Get the name of identifier for this declaration as a StringRef.
Definition: Decl.h:270
bool isPointerType() const
Definition: Type.h:5944
virtual SVal getArgSVal(unsigned Index) const
Returns the value of a given argument at the time of the call.
Definition: CallEvent.cpp:228
Tag that can use a checker name as a message provider (see SimpleProgramPointTag).
Definition: Checker.h:493
const LocationContext * getLocationContext() const
bool isIterator(const CXXRecordDecl *CRD)
bool isLive(SymbolRef sym)
method_range methods() const
Definition: DeclCXX.h:815