clang  7.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 begin and the
50 // past-end iterator for all containers whenever their `.begin()` and `.end()`
51 // are called. Since the Constraint Manager cannot handle such SVals we need
52 // to take over its role. We post-check equality and non-equality comparisons
53 // and record that the two sides are equal if we are in the 'equal' branch
54 // (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 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
64 // we only use expressions of the format S, S+n or S-n for iterator positions
65 // where S is a conjured symbol and n is an unsigned concrete integer. When
66 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
67 // a constraint which we later retrieve when doing an actual comparison.
68 
69 #include "ClangSACheckers.h"
74 
75 using namespace clang;
76 using namespace ento;
77 
78 namespace {
79 
80 // Abstract position of an iterator. This helps to handle all three kinds
81 // of operators in a common way by using a symbolic position.
82 struct IteratorPosition {
83 private:
84 
85  // Container the iterator belongs to
86  const MemRegion *Cont;
87 
88  // Abstract offset
89  const SymbolRef Offset;
90 
91  IteratorPosition(const MemRegion *C, SymbolRef Of)
92  : Cont(C), Offset(Of) {}
93 
94 public:
95  const MemRegion *getContainer() const { return Cont; }
96  SymbolRef getOffset() const { return Offset; }
97 
98  static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
99  return IteratorPosition(C, Of);
100  }
101 
102  IteratorPosition setTo(SymbolRef NewOf) const {
103  return IteratorPosition(Cont, NewOf);
104  }
105 
106  bool operator==(const IteratorPosition &X) const {
107  return Cont == X.Cont && Offset == X.Offset;
108  }
109 
110  bool operator!=(const IteratorPosition &X) const {
111  return Cont != X.Cont || Offset != X.Offset;
112  }
113 
114  void Profile(llvm::FoldingSetNodeID &ID) const {
115  ID.AddPointer(Cont);
116  ID.Add(Offset);
117  }
118 };
119 
120 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
121 
122 // Structure to record the symbolic begin and end position of a container
123 struct ContainerData {
124 private:
125  const SymbolRef Begin, End;
126 
127  ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
128 
129 public:
130  static ContainerData fromBegin(SymbolRef B) {
131  return ContainerData(B, nullptr);
132  }
133 
134  static ContainerData fromEnd(SymbolRef E) {
135  return ContainerData(nullptr, E);
136  }
137 
138  SymbolRef getBegin() const { return Begin; }
139  SymbolRef getEnd() const { return End; }
140 
141  ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
142 
143  ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
144 
145  bool operator==(const ContainerData &X) const {
146  return Begin == X.Begin && End == X.End;
147  }
148 
149  bool operator!=(const ContainerData &X) const {
150  return Begin != X.Begin || End != X.End;
151  }
152 
153  void Profile(llvm::FoldingSetNodeID &ID) const {
154  ID.Add(Begin);
155  ID.Add(End);
156  }
157 };
158 
159 // Structure fo recording iterator comparisons. We needed to retrieve the
160 // original comparison expression in assumptions.
161 struct IteratorComparison {
162 private:
163  RegionOrSymbol Left, Right;
164  bool Equality;
165 
166 public:
167  IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
168  : Left(L), Right(R), Equality(Eq) {}
169 
170  RegionOrSymbol getLeft() const { return Left; }
171  RegionOrSymbol getRight() const { return Right; }
172  bool isEquality() const { return Equality; }
173  bool operator==(const IteratorComparison &X) const {
174  return Left == X.Left && Right == X.Right && Equality == X.Equality;
175  }
176  bool operator!=(const IteratorComparison &X) const {
177  return Left != X.Left || Right != X.Right || Equality != X.Equality;
178  }
179  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
180 };
181 
182 class IteratorChecker
183  : public Checker<check::PreCall, check::PostCall,
184  check::PreStmt<CXXOperatorCallExpr>,
185  check::PostStmt<MaterializeTemporaryExpr>,
186  check::LiveSymbols, check::DeadSymbols,
187  eval::Assume> {
188 
189  std::unique_ptr<BugType> OutOfRangeBugType;
190 
191  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
192  const SVal &RVal, OverloadedOperatorKind Op) const;
193  void verifyDereference(CheckerContext &C, const SVal &Val) const;
194  void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
195  bool Postfix) const;
196  void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
197  bool Postfix) const;
198  void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
199  const SVal &RetVal, const SVal &LHS,
200  const SVal &RHS) const;
201  void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
202  const SVal &Cont) const;
203  void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
204  const SVal &Cont) const;
205  void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
206  const MemRegion *Cont) const;
207  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
208  const SVal &RetVal, const SVal &LHS,
209  const SVal &RHS) const;
210  void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
211  CheckerContext &C, ExplodedNode *ErrNode) const;
212 
213 public:
214  IteratorChecker();
215 
216  enum CheckKind {
217  CK_IteratorRangeChecker,
218  CK_NumCheckKinds
219  };
220 
221  DefaultBool ChecksEnabled[CK_NumCheckKinds];
222  CheckName CheckNames[CK_NumCheckKinds];
223 
224  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
225  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
226  void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const;
227  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
228  CheckerContext &C) const;
229  void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
230  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
231  ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
232  bool Assumption) const;
233 };
234 } // namespace
235 
236 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
237 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
238  IteratorPosition)
239 
240 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
241 
242 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
244 
245 namespace {
246 
247 bool isIteratorType(const QualType &Type);
248 bool isIterator(const CXXRecordDecl *CRD);
249 bool isBeginCall(const FunctionDecl *Func);
250 bool isEndCall(const FunctionDecl *Func);
257 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
259  RegionOrSymbol LVal,
260  RegionOrSymbol RVal, bool Equal);
262  const SymExpr *Condition, const SVal &LVal,
263  const SVal &RVal, bool Eq);
265  const SymExpr *Condition);
269  const MemRegion *Cont,
270  const SymbolRef Sym);
272  const SymbolRef Sym);
273 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
274  const SVal &Val);
275 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
276  RegionOrSymbol RegOrSym);
278  const IteratorPosition &Pos);
280  RegionOrSymbol RegOrSym,
281  const IteratorPosition &Pos);
284  RegionOrSymbol RegOrSym,
285  const IteratorPosition &Pos, bool Equal);
287  const IteratorPosition &Pos1,
288  const IteratorPosition &Pos2,
289  bool Equal);
290 const ContainerData *getContainerData(ProgramStateRef State,
291  const MemRegion *Cont);
293  const ContainerData &CData);
294 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
295 bool isZero(ProgramStateRef State, const NonLoc &Val);
296 } // namespace
297 
298 IteratorChecker::IteratorChecker() {
299  OutOfRangeBugType.reset(
300  new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
301  OutOfRangeBugType->setSuppressOnSink(true);
302 }
303 
304 void IteratorChecker::checkPreCall(const CallEvent &Call,
305  CheckerContext &C) const {
306  // Check for out of range access
307  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
308  if (!Func)
309  return;
310 
311  if (Func->isOverloadedOperator()) {
312  if (ChecksEnabled[CK_IteratorRangeChecker] &&
313  isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
314  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
315  // Check for out-of-range incrementions and decrementions
316  if (Call.getNumArgs() >= 1) {
317  verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
318  Call.getReturnValue(),
319  InstCall->getCXXThisVal(), Call.getArgSVal(0));
320  }
321  } else {
322  if (Call.getNumArgs() >= 2) {
323  verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
324  Call.getReturnValue(), Call.getArgSVal(0),
325  Call.getArgSVal(1));
326  }
327  }
328  } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
329  isDereferenceOperator(Func->getOverloadedOperator())) {
330  // Check for dereference of out-of-range iterators
331  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
332  verifyDereference(C, InstCall->getCXXThisVal());
333  } else {
334  verifyDereference(C, Call.getArgSVal(0));
335  }
336  }
337  }
338 }
339 
340 void IteratorChecker::checkPostCall(const CallEvent &Call,
341  CheckerContext &C) const {
342  // Record new iterator positions and iterator position changes
343  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
344  if (!Func)
345  return;
346 
347  if (Func->isOverloadedOperator()) {
348  const auto Op = Func->getOverloadedOperator();
349  if (isSimpleComparisonOperator(Op)) {
350  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
351  handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
352  Call.getArgSVal(0), Op);
353  } else {
354  handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
355  Call.getArgSVal(1), Op);
356  }
357  } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
358  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
359  if (Call.getNumArgs() >= 1) {
360  handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
361  Call.getReturnValue(),
362  InstCall->getCXXThisVal(), Call.getArgSVal(0));
363  }
364  } else {
365  if (Call.getNumArgs() >= 2) {
366  handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
367  Call.getReturnValue(), Call.getArgSVal(0),
368  Call.getArgSVal(1));
369  }
370  }
371  } else if (isIncrementOperator(Func->getOverloadedOperator())) {
372  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
373  handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
374  Call.getNumArgs());
375  } else {
376  handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
377  Call.getNumArgs());
378  }
379  } else if (isDecrementOperator(Func->getOverloadedOperator())) {
380  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
381  handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
382  Call.getNumArgs());
383  } else {
384  handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
385  Call.getNumArgs());
386  }
387  }
388  } else {
389  const auto *OrigExpr = Call.getOriginExpr();
390  if (!OrigExpr)
391  return;
392 
393  if (!isIteratorType(Call.getResultType()))
394  return;
395 
396  auto State = C.getState();
397  // Already bound to container?
399  return;
400 
401  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
402  if (isBeginCall(Func)) {
403  handleBegin(C, OrigExpr, Call.getReturnValue(),
404  InstCall->getCXXThisVal());
405  return;
406  }
407  if (isEndCall(Func)) {
408  handleEnd(C, OrigExpr, Call.getReturnValue(),
409  InstCall->getCXXThisVal());
410  return;
411  }
412  }
413 
414  // Copy-like and move constructors
415  if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
416  if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
418  if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
420  }
421  C.addTransition(State);
422  return;
423  }
424  }
425 
426  // Assumption: if return value is an iterator which is not yet bound to a
427  // container, then look for the first iterator argument, and
428  // bind the return value to the same container. This approach
429  // works for STL algorithms.
430  // FIXME: Add a more conservative mode
431  for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
432  if (isIteratorType(Call.getArgExpr(i)->getType())) {
433  if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
434  assignToContainer(C, OrigExpr, Call.getReturnValue(),
435  Pos->getContainer());
436  return;
437  }
438  }
439  }
440  }
441 }
442 
443 void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE,
444  CheckerContext &C) const {
445  const auto *ThisExpr = COCE->getArg(0);
446 
447  auto State = C.getState();
448  const auto *LCtx = C.getLocationContext();
449 
450  const auto CurrentThis = State->getSVal(ThisExpr, LCtx);
451  if (const auto *Reg = CurrentThis.getAsRegion()) {
452  if (!Reg->getAs<CXXTempObjectRegion>())
453  return;
454  const auto OldState = C.getPredecessor()->getFirstPred()->getState();
455  const auto OldThis = OldState->getSVal(ThisExpr, LCtx);
456  // FIXME: This solution is unreliable. It may happen that another checker
457  // subscribes to the pre-statement check of `CXXOperatorCallExpr`
458  // and adds a transition before us. The proper fix is to make the
459  // CFG provide a `ConstructionContext` for the `CXXOperatorCallExpr`,
460  // which would turn the corresponding `CFGStmt` element into a
461  // `CFGCXXRecordTypedCall` element, which will allow `ExprEngine` to
462  // foresee that the `begin()`/`end()` call constructs the object
463  // directly in the temporary region that `CXXOperatorCallExpr` takes
464  // as its implicit object argument.
465  const auto *Pos = getIteratorPosition(OldState, OldThis);
466  if (!Pos)
467  return;
468  State = setIteratorPosition(State, CurrentThis, *Pos);
469  C.addTransition(State);
470  }
471 }
472 
473 void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
474  CheckerContext &C) const {
475  /* Transfer iterator state to temporary objects */
476  auto State = C.getState();
477  const auto *Pos =
479  if (!Pos)
480  return;
481  State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
482  C.addTransition(State);
483 }
484 
485 void IteratorChecker::checkLiveSymbols(ProgramStateRef State,
486  SymbolReaper &SR) const {
487  // Keep symbolic expressions of iterator positions, container begins and ends
488  // alive
489  auto RegionMap = State->get<IteratorRegionMap>();
490  for (const auto Reg : RegionMap) {
491  const auto Offset = Reg.second.getOffset();
492  for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
493  if (isa<SymbolData>(*i))
494  SR.markLive(*i);
495  }
496 
497  auto SymbolMap = State->get<IteratorSymbolMap>();
498  for (const auto Sym : SymbolMap) {
499  const auto Offset = Sym.second.getOffset();
500  for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
501  if (isa<SymbolData>(*i))
502  SR.markLive(*i);
503  }
504 
505  auto ContMap = State->get<ContainerMap>();
506  for (const auto Cont : ContMap) {
507  const auto CData = Cont.second;
508  if (CData.getBegin()) {
509  SR.markLive(CData.getBegin());
510  }
511  if (CData.getEnd()) {
512  SR.markLive(CData.getEnd());
513  }
514  }
515 }
516 
517 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
518  CheckerContext &C) const {
519  // Cleanup
520  auto State = C.getState();
521 
522  auto RegionMap = State->get<IteratorRegionMap>();
523  for (const auto Reg : RegionMap) {
524  if (!SR.isLiveRegion(Reg.first)) {
525  State = State->remove<IteratorRegionMap>(Reg.first);
526  }
527  }
528 
529  auto SymbolMap = State->get<IteratorSymbolMap>();
530  for (const auto Sym : SymbolMap) {
531  if (!SR.isLive(Sym.first)) {
532  State = State->remove<IteratorSymbolMap>(Sym.first);
533  }
534  }
535 
536  auto ContMap = State->get<ContainerMap>();
537  for (const auto Cont : ContMap) {
538  if (!SR.isLiveRegion(Cont.first)) {
539  State = State->remove<ContainerMap>(Cont.first);
540  }
541  }
542 
543  auto ComparisonMap = State->get<IteratorComparisonMap>();
544  for (const auto Comp : ComparisonMap) {
545  if (!SR.isLive(Comp.first)) {
546  State = State->remove<IteratorComparisonMap>(Comp.first);
547  }
548  }
549 }
550 
551 ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
552  bool Assumption) const {
553  // Load recorded comparison and transfer iterator state between sides
554  // according to comparison operator and assumption
555  const auto *SE = Cond.getAsSymExpr();
556  if (!SE)
557  return State;
558 
559  auto Opc = getOpcode(SE);
560  if (Opc != BO_EQ && Opc != BO_NE)
561  return State;
562 
563  bool Negated = false;
564  const auto *Comp = loadComparison(State, SE);
565  if (!Comp) {
566  // Try negated comparison, which is a SymExpr to 0 integer comparison
567  const auto *SIE = dyn_cast<SymIntExpr>(SE);
568  if (!SIE)
569  return State;
570 
571  if (SIE->getRHS() != 0)
572  return State;
573 
574  SE = SIE->getLHS();
575  Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
576  Opc = getOpcode(SE);
577  if (Opc != BO_EQ && Opc != BO_NE)
578  return State;
579 
580  Comp = loadComparison(State, SE);
581  if (!Comp)
582  return State;
583  }
584 
585  return processComparison(State, Comp->getLeft(), Comp->getRight(),
586  (Comp->isEquality() == Assumption) != Negated);
587 }
588 
589 void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
590  const SVal &LVal, const SVal &RVal,
591  OverloadedOperatorKind Op) const {
592  // Record the operands and the operator of the comparison for the next
593  // evalAssume, if the result is a symbolic expression. If it is a concrete
594  // value (only one branch is possible), then transfer the state between
595  // the operands according to the operator and the result
596  auto State = C.getState();
597  if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
598  const auto *LPos = getIteratorPosition(State, LVal);
599  const auto *RPos = getIteratorPosition(State, RVal);
600  if (!LPos && !RPos)
601  return;
602  State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
603  C.addTransition(State);
604  } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
605  if ((State = processComparison(
606  State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
607  (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
608  C.addTransition(State);
609  } else {
610  C.generateSink(State, C.getPredecessor());
611  }
612  }
613 }
614 
615 void IteratorChecker::verifyDereference(CheckerContext &C,
616  const SVal &Val) const {
617  auto State = C.getState();
618  const auto *Pos = getIteratorPosition(State, Val);
619  if (Pos && isOutOfRange(State, *Pos)) {
620  // If I do not put a tag here, some range tests will fail
621  static CheckerProgramPointTag Tag("IteratorRangeChecker",
622  "IteratorOutOfRange");
623  auto *N = C.generateNonFatalErrorNode(State, &Tag);
624  if (!N)
625  return;
626  reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
627  }
628 }
629 
630 void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
631  const SVal &Iter, bool Postfix) const {
632  // Increment the symbolic expressions which represents the position of the
633  // iterator
634  auto State = C.getState();
635  const auto *Pos = getIteratorPosition(State, Iter);
636  if (Pos) {
637  auto &SymMgr = C.getSymbolManager();
638  auto &BVF = SymMgr.getBasicVals();
639  auto &SVB = C.getSValBuilder();
640  const auto OldOffset = Pos->getOffset();
641  auto NewOffset =
642  SVB.evalBinOp(State, BO_Add,
643  nonloc::SymbolVal(OldOffset),
644  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
645  SymMgr.getType(OldOffset)).getAsSymbol();
646  auto NewPos = Pos->setTo(NewOffset);
647  State = setIteratorPosition(State, Iter, NewPos);
648  State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
649  C.addTransition(State);
650  }
651 }
652 
653 void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal,
654  const SVal &Iter, bool Postfix) const {
655  // Decrement the symbolic expressions which represents the position of the
656  // iterator
657  auto State = C.getState();
658  const auto *Pos = getIteratorPosition(State, Iter);
659  if (Pos) {
660  auto &SymMgr = C.getSymbolManager();
661  auto &BVF = SymMgr.getBasicVals();
662  auto &SVB = C.getSValBuilder();
663  const auto OldOffset = Pos->getOffset();
664  auto NewOffset =
665  SVB.evalBinOp(State, BO_Sub,
666  nonloc::SymbolVal(OldOffset),
667  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
668  SymMgr.getType(OldOffset)).getAsSymbol();
669  auto NewPos = Pos->setTo(NewOffset);
670  State = setIteratorPosition(State, Iter, NewPos);
671  State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
672  C.addTransition(State);
673  }
674 }
675 
676 // This function tells the analyzer's engine that symbols produced by our
677 // checker, most notably iterator positions, are relatively small.
678 // A distance between items in the container should not be very large.
679 // By assuming that it is within around 1/8 of the address space,
680 // we can help the analyzer perform operations on these symbols
681 // without being afraid of integer overflows.
682 // FIXME: Should we provide it as an API, so that all checkers could use it?
684  long Scale) {
685  SValBuilder &SVB = State->getStateManager().getSValBuilder();
687 
688  QualType T = Sym->getType();
690  APSIntType AT = BV.getAPSIntType(T);
691 
692  ProgramStateRef NewState = State;
693 
694  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
695  SVal IsCappedFromAbove =
696  SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
698  if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
699  NewState = NewState->assume(*DV, true);
700  if (!NewState)
701  return State;
702  }
703 
704  llvm::APSInt Min = -Max;
705  SVal IsCappedFromBelow =
706  SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
708  if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
709  NewState = NewState->assume(*DV, true);
710  if (!NewState)
711  return State;
712  }
713 
714  return NewState;
715 }
716 
717 void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C,
719  const SVal &RetVal,
720  const SVal &LHS,
721  const SVal &RHS) const {
722  // Increment or decrement the symbolic expressions which represents the
723  // position of the iterator
724  auto State = C.getState();
725  const auto *Pos = getIteratorPosition(State, LHS);
726  if (!Pos)
727  return;
728 
729  const auto *value = &RHS;
730  if (auto loc = RHS.getAs<Loc>()) {
731  const auto val = State->getRawSVal(*loc);
732  value = &val;
733  }
734 
735  auto &SymMgr = C.getSymbolManager();
736  auto &SVB = C.getSValBuilder();
737  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
738  const auto OldOffset = Pos->getOffset();
739  SymbolRef NewOffset;
740  if (const auto intValue = value->getAs<nonloc::ConcreteInt>()) {
741  // For concrete integers we can calculate the new position
742  NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
743  *intValue,
744  SymMgr.getType(OldOffset)).getAsSymbol();
745  } else {
746  // For other symbols create a new symbol to keep expressions simple
747  const auto &LCtx = C.getLocationContext();
748  NewOffset = SymMgr.conjureSymbol(nullptr, LCtx, SymMgr.getType(OldOffset),
749  C.blockCount());
750  State = assumeNoOverflow(State, NewOffset, 4);
751  }
752  auto NewPos = Pos->setTo(NewOffset);
753  auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
754  State = setIteratorPosition(State, TgtVal, NewPos);
755  C.addTransition(State);
756 }
757 
758 void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
760  const SVal &RetVal,
761  const SVal &LHS,
762  const SVal &RHS) const {
763  auto State = C.getState();
764 
765  // If the iterator is initially inside its range, then the operation is valid
766  const auto *Pos = getIteratorPosition(State, LHS);
767  if (!Pos || !isOutOfRange(State, *Pos))
768  return;
769 
770  auto value = RHS;
771  if (auto loc = RHS.getAs<Loc>()) {
772  value = State->getRawSVal(*loc);
773  }
774 
775  // Incremention or decremention by 0 is never bug
776  if (isZero(State, value.castAs<NonLoc>()))
777  return;
778 
779  auto &SymMgr = C.getSymbolManager();
780  auto &SVB = C.getSValBuilder();
781  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
782  const auto OldOffset = Pos->getOffset();
783  const auto intValue = value.getAs<nonloc::ConcreteInt>();
784  if (!intValue)
785  return;
786 
787  auto NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
788  *intValue,
789  SymMgr.getType(OldOffset)).getAsSymbol();
790  auto NewPos = Pos->setTo(NewOffset);
791 
792  // If out of range, the only valid operation is to step into the range
793  if (isOutOfRange(State, NewPos)) {
794  auto *N = C.generateNonFatalErrorNode(State);
795  if (!N)
796  return;
797  reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
798  }
799 }
800 
801 void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
802  const SVal &RetVal, const SVal &Cont) const {
803  const auto *ContReg = Cont.getAsRegion();
804  if (!ContReg)
805  return;
806 
807  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
808  ContReg = CBOR->getSuperRegion();
809  }
810 
811  // If the container already has a begin symbol then use it. Otherwise first
812  // create a new one.
813  auto State = C.getState();
814  auto BeginSym = getContainerBegin(State, ContReg);
815  if (!BeginSym) {
816  auto &SymMgr = C.getSymbolManager();
817  BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
818  C.getASTContext().LongTy, C.blockCount());
819  State = assumeNoOverflow(State, BeginSym, 4);
820  State = createContainerBegin(State, ContReg, BeginSym);
821  }
822  State = setIteratorPosition(State, RetVal,
823  IteratorPosition::getPosition(ContReg, BeginSym));
824  C.addTransition(State);
825 }
826 
827 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
828  const SVal &RetVal, const SVal &Cont) const {
829  const auto *ContReg = Cont.getAsRegion();
830  if (!ContReg)
831  return;
832 
833  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
834  ContReg = CBOR->getSuperRegion();
835  }
836 
837  // If the container already has an end symbol then use it. Otherwise first
838  // create a new one.
839  auto State = C.getState();
840  auto EndSym = getContainerEnd(State, ContReg);
841  if (!EndSym) {
842  auto &SymMgr = C.getSymbolManager();
843  EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
844  C.getASTContext().LongTy, C.blockCount());
845  State = assumeNoOverflow(State, EndSym, 4);
846  State = createContainerEnd(State, ContReg, EndSym);
847  }
848  State = setIteratorPosition(State, RetVal,
849  IteratorPosition::getPosition(ContReg, EndSym));
850  C.addTransition(State);
851 }
852 
853 void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
854  const SVal &RetVal,
855  const MemRegion *Cont) const {
856  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
857  Cont = CBOR->getSuperRegion();
858  }
859 
860  auto State = C.getState();
861  auto &SymMgr = C.getSymbolManager();
862  auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
863  C.getASTContext().LongTy, C.blockCount());
864  State = assumeNoOverflow(State, Sym, 4);
865  State = setIteratorPosition(State, RetVal,
866  IteratorPosition::getPosition(Cont, Sym));
867  C.addTransition(State);
868 }
869 
870 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
871  const SVal &Val, CheckerContext &C,
872  ExplodedNode *ErrNode) const {
873  auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
874  R->markInteresting(Val);
875  C.emitReport(std::move(R));
876 }
877 
878 namespace {
879 
880 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
881 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
882 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
884 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
886 
887 bool isIteratorType(const QualType &Type) {
888  if (Type->isPointerType())
889  return true;
890 
891  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
892  return isIterator(CRD);
893 }
894 
895 bool isIterator(const CXXRecordDecl *CRD) {
896  if (!CRD)
897  return false;
898 
899  const auto Name = CRD->getName();
900  if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
901  Name.endswith_lower("it")))
902  return false;
903 
904  bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
905  HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
906  for (const auto *Method : CRD->methods()) {
907  if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
908  if (Ctor->isCopyConstructor()) {
909  HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
910  }
911  continue;
912  }
913  if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
914  HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
915  continue;
916  }
917  if (Method->isCopyAssignmentOperator()) {
918  HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
919  continue;
920  }
921  if (!Method->isOverloadedOperator())
922  continue;
923  const auto OPK = Method->getOverloadedOperator();
924  if (OPK == OO_PlusPlus) {
925  HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
926  HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
927  continue;
928  }
929  if (OPK == OO_Star) {
930  HasDerefOp = (Method->getNumParams() == 0);
931  continue;
932  }
933  }
934 
935  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
936  HasPostIncrOp && HasDerefOp;
937 }
938 
939 bool isBeginCall(const FunctionDecl *Func) {
940  const auto *IdInfo = Func->getIdentifier();
941  if (!IdInfo)
942  return false;
943  return IdInfo->getName().endswith_lower("begin");
944 }
945 
946 bool isEndCall(const FunctionDecl *Func) {
947  const auto *IdInfo = Func->getIdentifier();
948  if (!IdInfo)
949  return false;
950  return IdInfo->getName().endswith_lower("end");
951 }
952 
954  return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
955 }
956 
958  return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
959  OK == OO_Subscript;
960 }
961 
963  return OK == OO_PlusPlus;
964 }
965 
967  return OK == OO_MinusMinus;
968 }
969 
971  return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
972  OK == OO_MinusEqual;
973 }
974 
976  if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
977  return BSE->getOpcode();
978  } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
979  const auto *COE = dyn_cast_or_null<CXXOperatorCallExpr>(SC->getStmt());
980  if (!COE)
981  return BO_Comma; // Extremal value, neither EQ nor NE
982  if (COE->getOperator() == OO_EqualEqual) {
983  return BO_EQ;
984  } else if (COE->getOperator() == OO_ExclaimEqual) {
985  return BO_NE;
986  }
987  return BO_Comma; // Extremal value, neither EQ nor NE
988  }
989  return BO_Comma; // Extremal value, neither EQ nor NE
990 }
991 
992 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
993  if (const auto Reg = Val.getAsRegion()) {
994  return Reg;
995  } else if (const auto Sym = Val.getAsSymbol()) {
996  return Sym;
997  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
998  return LCVal->getRegion();
999  }
1000  return RegionOrSymbol();
1001 }
1002 
1004  RegionOrSymbol LVal,
1005  RegionOrSymbol RVal, bool Equal) {
1006  const auto *LPos = getIteratorPosition(State, LVal);
1007  const auto *RPos = getIteratorPosition(State, RVal);
1008  if (LPos && !RPos) {
1009  State = adjustIteratorPosition(State, RVal, *LPos, Equal);
1010  } else if (!LPos && RPos) {
1011  State = adjustIteratorPosition(State, LVal, *RPos, Equal);
1012  } else if (LPos && RPos) {
1013  State = relateIteratorPositions(State, *LPos, *RPos, Equal);
1014  }
1015  return State;
1016 }
1017 
1019  const SymExpr *Condition, const SVal &LVal,
1020  const SVal &RVal, bool Eq) {
1021  const auto Left = getRegionOrSymbol(LVal);
1022  const auto Right = getRegionOrSymbol(RVal);
1023  if (!Left || !Right)
1024  return State;
1025  return State->set<IteratorComparisonMap>(Condition,
1026  IteratorComparison(Left, Right, Eq));
1027 }
1028 
1030  const SymExpr *Condition) {
1031  return State->get<IteratorComparisonMap>(Condition);
1032 }
1033 
1035  const auto *CDataPtr = getContainerData(State, Cont);
1036  if (!CDataPtr)
1037  return nullptr;
1038 
1039  return CDataPtr->getBegin();
1040 }
1041 
1042 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
1043  const auto *CDataPtr = getContainerData(State, Cont);
1044  if (!CDataPtr)
1045  return nullptr;
1046 
1047  return CDataPtr->getEnd();
1048 }
1049 
1051  const MemRegion *Cont,
1052  const SymbolRef Sym) {
1053  // Only create if it does not exist
1054  const auto *CDataPtr = getContainerData(State, Cont);
1055  if (CDataPtr) {
1056  if (CDataPtr->getBegin()) {
1057  return State;
1058  }
1059  const auto CData = CDataPtr->newBegin(Sym);
1060  return setContainerData(State, Cont, CData);
1061  }
1062  const auto CData = ContainerData::fromBegin(Sym);
1063  return setContainerData(State, Cont, CData);
1064 }
1065 
1067  const SymbolRef Sym) {
1068  // Only create if it does not exist
1069  const auto *CDataPtr = getContainerData(State, Cont);
1070  if (CDataPtr) {
1071  if (CDataPtr->getEnd()) {
1072  return State;
1073  }
1074  const auto CData = CDataPtr->newEnd(Sym);
1075  return setContainerData(State, Cont, CData);
1076  }
1077  const auto CData = ContainerData::fromEnd(Sym);
1078  return setContainerData(State, Cont, CData);
1079 }
1080 
1081 const ContainerData *getContainerData(ProgramStateRef State,
1082  const MemRegion *Cont) {
1083  return State->get<ContainerMap>(Cont);
1084 }
1085 
1087  const ContainerData &CData) {
1088  return State->set<ContainerMap>(Cont, CData);
1089 }
1090 
1091 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
1092  const SVal &Val) {
1093  if (const auto Reg = Val.getAsRegion()) {
1094  return State->get<IteratorRegionMap>(Reg);
1095  } else if (const auto Sym = Val.getAsSymbol()) {
1096  return State->get<IteratorSymbolMap>(Sym);
1097  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1098  return State->get<IteratorRegionMap>(LCVal->getRegion());
1099  }
1100  return nullptr;
1101 }
1102 
1103 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
1104  RegionOrSymbol RegOrSym) {
1105  if (RegOrSym.is<const MemRegion *>()) {
1106  return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
1107  } else if (RegOrSym.is<SymbolRef>()) {
1108  return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
1109  }
1110  return nullptr;
1111 }
1112 
1114  const IteratorPosition &Pos) {
1115  if (const auto Reg = Val.getAsRegion()) {
1116  return State->set<IteratorRegionMap>(Reg, Pos);
1117  } else if (const auto Sym = Val.getAsSymbol()) {
1118  return State->set<IteratorSymbolMap>(Sym, Pos);
1119  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1120  return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
1121  }
1122  return nullptr;
1123 }
1124 
1126  RegionOrSymbol RegOrSym,
1127  const IteratorPosition &Pos) {
1128  if (RegOrSym.is<const MemRegion *>()) {
1129  return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
1130  Pos);
1131  } else if (RegOrSym.is<SymbolRef>()) {
1132  return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
1133  }
1134  return nullptr;
1135 }
1136 
1138  if (const auto Reg = Val.getAsRegion()) {
1139  return State->remove<IteratorRegionMap>(Reg);
1140  } else if (const auto Sym = Val.getAsSymbol()) {
1141  return State->remove<IteratorSymbolMap>(Sym);
1142  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1143  return State->remove<IteratorRegionMap>(LCVal->getRegion());
1144  }
1145  return nullptr;
1146 }
1147 
1149  RegionOrSymbol RegOrSym,
1150  const IteratorPosition &Pos,
1151  bool Equal) {
1152  if (Equal) {
1153  return setIteratorPosition(State, RegOrSym, Pos);
1154  } else {
1155  return State;
1156  }
1157 }
1158 
1160  const IteratorPosition &Pos1,
1161  const IteratorPosition &Pos2,
1162  bool Equal) {
1163  auto &SVB = State->getStateManager().getSValBuilder();
1164 
1165  // FIXME: This code should be reworked as follows:
1166  // 1. Subtract the operands using evalBinOp().
1167  // 2. Assume that the result doesn't overflow.
1168  // 3. Compare the result to 0.
1169  // 4. Assume the result of the comparison.
1170  const auto comparison =
1171  SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
1172  nonloc::SymbolVal(Pos2.getOffset()),
1173  SVB.getConditionType());
1174 
1175  assert(comparison.getAs<DefinedSVal>() &&
1176  "Symbol comparison must be a `DefinedSVal`");
1177 
1178  auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
1179  if (const auto CompSym = comparison.getAsSymbol()) {
1180  assert(isa<SymIntExpr>(CompSym) &&
1181  "Symbol comparison must be a `SymIntExpr`");
1183  cast<SymIntExpr>(CompSym)->getOpcode()) &&
1184  "Symbol comparison must be a comparison");
1185  return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
1186  }
1187 
1188  return NewState;
1189 }
1190 
1191 bool isZero(ProgramStateRef State, const NonLoc &Val) {
1192  auto &BVF = State->getBasicVals();
1193  return compare(State, Val,
1194  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
1195  BO_EQ);
1196 }
1197 
1198 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
1199  const auto *Cont = Pos.getContainer();
1200  const auto *CData = getContainerData(State, Cont);
1201  if (!CData)
1202  return false;
1203 
1204  // Out of range means less than the begin symbol or greater or equal to the
1205  // end symbol.
1206 
1207  const auto Beg = CData->getBegin();
1208  if (Beg) {
1209  if (isLess(State, Pos.getOffset(), Beg)) {
1210  return true;
1211  }
1212  }
1213 
1214  const auto End = CData->getEnd();
1215  if (End) {
1216  if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
1217  return true;
1218  }
1219  }
1220 
1221  return false;
1222 }
1223 
1224 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
1225  return compare(State, Sym1, Sym2, BO_LT);
1226 }
1227 
1228 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
1229  return compare(State, Sym1, Sym2, BO_GE);
1230 }
1231 
1232 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
1233  BinaryOperator::Opcode Opc) {
1234  return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
1235 }
1236 
1237 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
1238  BinaryOperator::Opcode Opc) {
1239  auto &SVB = State->getStateManager().getSValBuilder();
1240 
1241  const auto comparison =
1242  SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
1243 
1244  assert(comparison.getAs<DefinedSVal>() &&
1245  "Symbol comparison must be a `DefinedSVal`");
1246 
1247  return !State->assume(comparison.castAs<DefinedSVal>(), false);
1248 }
1249 
1250 } // namespace
1251 
1252 #define REGISTER_CHECKER(name) \
1253  void ento::register##name(CheckerManager &Mgr) { \
1254  auto *checker = Mgr.registerChecker<IteratorChecker>(); \
1255  checker->ChecksEnabled[IteratorChecker::CK_##name] = true; \
1256  checker->CheckNames[IteratorChecker::CK_##name] = \
1257  Mgr.getCurrentCheckName(); \
1258  }
1259 
1260 REGISTER_CHECKER(IteratorRangeChecker)
1261 
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)
Represents a function declaration or definition.
Definition: Decl.h:1714
A (possibly-)qualified type.
Definition: Type.h:655
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
void markLive(SymbolRef sym)
Unconditionally marks a symbol as live.
SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont)
Expr * getArg(unsigned Arg)
getArg - Return the specified argument.
Definition: Expr.h:2352
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:567
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:1428
CanQualType LongTy
Definition: ASTContext.h:1007
bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos)
const ProgramStateRef & getState() const
bool isZero(ProgramStateRef State, const NonLoc &Val)
Represents a prvalue temporary that is written into memory so that a reference can bind to it...
Definition: ExprCXX.h:4040
Value representing integer constant.
Definition: SVals.h:377
const Expr * getOriginExpr() const
Returns the expression whose value will be the result of this call.
Definition: CallEvent.h:248
BasicValueFactory & getBasicVals()
ExplodedNode * getPredecessor()
Returns the previous node in the exploded graph, which includes the state of the program before the c...
SVal getSVal(const Stmt *S) const
Get the value of arbitrary expressions at this point in the path.
Symbolic value.
Definition: SymExpr.h:30
IdentifierInfo * getIdentifier() const
Get the identifier that names this declaration, if there is one.
Definition: Decl.h:269
Expr * GetTemporaryExpr() const
Retrieve the temporary-generating subexpression whose value will be materialized into a glvalue...
Definition: ExprCXX.h:4081
LineState State
symbol_iterator symbol_begin() const
Definition: SymExpr.h:85
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:298
const SymExpr * getAsSymbolicExpression() const
getAsSymbolicExpression - If this Sval wraps a symbolic expression then return that expression...
Definition: SVals.cpp:137
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:282
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:20
Represents a symbolic expression like &#39;x&#39; + 3.
bool isEndCall(const FunctionDecl *Func)
ExplodedNode * getFirstPred()
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:411
virtual QualType getType() const =0
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition: SVals.cpp:127
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition: Type.cpp:1621
const IteratorPosition * getIteratorPosition(ProgramStateRef State, RegionOrSymbol RegOrSym)
const RegionTy * getAs() const
Definition: MemRegion.h:1180
Expr - This represents one expression.
Definition: Expr.h:106
SourceLocation End
static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y)
bool isDereferenceOperator(OverloadedOperatorKind OK)
QualType getConditionType() const
Definition: SValBuilder.h:161
SourceLocation Begin
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:228
SVal evalBinOp(ProgramStateRef state, BinaryOperator::Opcode op, SVal lhs, SVal rhs, QualType type)
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:112
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
bool isComparisonOp() const
Definition: Expr.h:3160
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:151
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:76
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:1854
SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont)
A class responsible for cleaning up unused symbols.
bool isDecrementOperator(OverloadedOperatorKind OK)
ProgramStateRef relateIteratorPositions(ProgramStateRef State, const IteratorPosition &Pos1, const IteratorPosition &Pos2, bool Equal)
const IteratorComparison * loadComparison(ProgramStateRef State, const SymExpr *Condition)
virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy)=0
Create a new value which represents a binary expression with two non- location operands.
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)
static symbol_iterator symbol_end()
Definition: SymExpr.h:86
BinaryOperator::Opcode getOpcode(const SymExpr *SE)
Represents symbolic expression that isn&#39;t a location.
Definition: SVals.h:347
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:164
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)
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, const ContainerData &CData)
BasicValueFactory & getBasicValueFactory()
Definition: SValBuilder.h:169
const ProgramStateRef & getState() const
SVal evalBinOp(SValBuilder &svalBuilder, BinaryOperator::Opcode Op, const ConcreteInt &R) const
Definition: SVals.cpp:238
const ProgramStateRef saveComparison(ProgramStateRef State, const SymExpr *Condition, const SVal &LVal, const SVal &RVal, bool Eq)
const SymExpr * getAsSymExpr() const
Definition: SVals.cpp:144
QualType getResultType() const
Returns the result type, adjusted for references.
Definition: CallEvent.cpp:69
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13451
Represents a C++ struct/union/class.
Definition: DeclCXX.h:300
bool isBeginCall(const FunctionDecl *Func)
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).
SValBuilder & getSValBuilder()
StringRef getName() const
Get the name of identifier for this declaration as a StringRef.
Definition: Decl.h:275
ProgramStateRef createContainerBegin(ProgramStateRef State, const MemRegion *Cont, const SymbolRef Sym)
bool isPointerType() const
Definition: Type.h:6106
bool isIncrementOperator(OverloadedOperatorKind OK)
virtual SVal getArgSVal(unsigned Index) const
Returns the value of a given argument at the time of the call.
Definition: CallEvent.cpp:268
Tag that can use a checker name as a message provider (see SimpleProgramPointTag).
Definition: Checker.h:509
const LocationContext * getLocationContext() const
bool isIterator(const CXXRecordDecl *CRD)
static ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale)
bool isLive(SymbolRef sym)
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
method_range methods() const
Definition: DeclCXX.h:865