clang  15.0.0git
IteratorModeling.cpp
Go to the documentation of this file.
1 //===-- IteratorModeling.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 iterator-like iterators.
10 //
11 //===----------------------------------------------------------------------===//
12 //
13 // In the code, iterator can be represented as a:
14 // * type-I: typedef-ed pointer. Operations over such iterator, such as
15 // comparisons or increments, are modeled straightforwardly by the
16 // analyzer.
17 // * type-II: structure with its method bodies available. Operations over such
18 // iterator are inlined by the analyzer, and results of modeling
19 // these operations are exposing implementation details of the
20 // iterators, which is not necessarily helping.
21 // * type-III: completely opaque structure. Operations over such iterator are
22 // modeled conservatively, producing conjured symbols everywhere.
23 //
24 // To handle all these types in a common way we introduce a structure called
25 // IteratorPosition which is an abstraction of the position the iterator
26 // represents using symbolic expressions. The checker handles all the
27 // operations on this structure.
28 //
29 // Additionally, depending on the circumstances, operators of types II and III
30 // can be represented as:
31 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
32 // from conservatively evaluated methods such as
33 // `.begin()`.
34 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
35 // variables or temporaries, when the iterator object is
36 // currently treated as an lvalue.
37 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
38 // iterator object is treated as an rvalue taken of a
39 // particular lvalue, eg. a copy of "type-a" iterator
40 // object, or an iterator that existed before the
41 // analysis has started.
42 //
43 // To handle any of these three different representations stored in an SVal we
44 // use setter and getters functions which separate the three cases. To store
45 // them we use a pointer union of symbol and memory region.
46 //
47 // The checker works the following way: We record the begin and the
48 // past-end iterator for all containers whenever their `.begin()` and `.end()`
49 // are called. Since the Constraint Manager cannot handle such SVals we need
50 // to take over its role. We post-check equality and non-equality comparisons
51 // and record that the two sides are equal if we are in the 'equal' branch
52 // (true-branch for `==` and false-branch for `!=`).
53 //
54 // In case of type-I or type-II iterators we get a concrete integer as a result
55 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
56 // this latter case we record the symbol and reload it in evalAssume() and do
57 // the propagation there. We also handle (maybe double) negated comparisons
58 // which are represented in the form of (x == 0 or x != 0) where x is the
59 // comparison itself.
60 //
61 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
62 // we only use expressions of the format S, S+n or S-n for iterator positions
63 // where S is a conjured symbol and n is an unsigned concrete integer. When
64 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
65 // a constraint which we later retrieve when doing an actual comparison.
66 
67 #include "clang/AST/DeclTemplate.h"
75 
76 #include "Iterator.h"
77 
78 #include <utility>
79 
80 using namespace clang;
81 using namespace ento;
82 using namespace iterator;
83 
84 namespace {
85 
86 class IteratorModeling
87  : public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
88  check::PostStmt<BinaryOperator>,
89  check::PostStmt<MaterializeTemporaryExpr>,
90  check::Bind, check::LiveSymbols, check::DeadSymbols> {
91 
92  using AdvanceFn = void (IteratorModeling::*)(CheckerContext &, const Expr *,
93  SVal, SVal, SVal) const;
94 
95  void handleOverloadedOperator(CheckerContext &C, const CallEvent &Call,
96  OverloadedOperatorKind Op) const;
97  void handleAdvanceLikeFunction(CheckerContext &C, const CallEvent &Call,
98  const Expr *OrigExpr,
99  const AdvanceFn *Handler) const;
100 
101  void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal,
102  const SVal &LVal, const SVal &RVal,
103  OverloadedOperatorKind Op) const;
104  void processComparison(CheckerContext &C, ProgramStateRef State,
105  SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
106  OverloadedOperatorKind Op) const;
107  void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
108  bool Postfix) const;
109  void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
110  bool Postfix) const;
111  void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
112  OverloadedOperatorKind Op, const SVal &RetVal,
113  const SVal &Iterator, const SVal &Amount) const;
114  void handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,
115  OverloadedOperatorKind OK, SVal Offset) const;
116  void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
117  SVal Amount) const;
118  void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
119  SVal Amount) const;
120  void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
121  SVal Amount) const;
122  void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
123  const MemRegion *Cont) const;
124  bool noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const;
125  void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
126  const char *Sep) const override;
127 
128  // std::advance, std::prev & std::next
129  CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {
130  // template<class InputIt, class Distance>
131  // void advance(InputIt& it, Distance n);
132  {{{"std", "advance"}, 2}, &IteratorModeling::handleAdvance},
133 
134  // template<class BidirIt>
135  // BidirIt prev(
136  // BidirIt it,
137  // typename std::iterator_traits<BidirIt>::difference_type n = 1);
138  {{{"std", "prev"}, 2}, &IteratorModeling::handlePrev},
139 
140  // template<class ForwardIt>
141  // ForwardIt next(
142  // ForwardIt it,
143  // typename std::iterator_traits<ForwardIt>::difference_type n = 1);
144  {{{"std", "next"}, 2}, &IteratorModeling::handleNext},
145  };
146 
147 public:
148  IteratorModeling() = default;
149 
150  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
151  void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
152  void checkPostStmt(const UnaryOperator *UO, CheckerContext &C) const;
153  void checkPostStmt(const BinaryOperator *BO, CheckerContext &C) const;
154  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
155  CheckerContext &C) const;
156  void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
157  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
158 };
159 
160 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
161 bool isSimpleComparisonOperator(BinaryOperatorKind OK);
162 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
163 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
164  SymbolRef Sym2, bool Equal);
165 bool isBoundThroughLazyCompoundVal(const Environment &Env,
166  const MemRegion *Reg);
167 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);
168 
169 } // namespace
170 
171 void IteratorModeling::checkPostCall(const CallEvent &Call,
172  CheckerContext &C) const {
173  // Record new iterator positions and iterator position changes
174  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
175  if (!Func)
176  return;
177 
178  if (Func->isOverloadedOperator()) {
179  const auto Op = Func->getOverloadedOperator();
180  handleOverloadedOperator(C, Call, Op);
181  return;
182  }
183 
184  const auto *OrigExpr = Call.getOriginExpr();
185  if (!OrigExpr)
186  return;
187 
188  const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(Call);
189  if (Handler) {
190  handleAdvanceLikeFunction(C, Call, OrigExpr, Handler);
191  return;
192  }
193 
194  if (!isIteratorType(Call.getResultType()))
195  return;
196 
197  auto State = C.getState();
198 
199  // Already bound to container?
200  if (getIteratorPosition(State, Call.getReturnValue()))
201  return;
202 
203  // Copy-like and move constructors
204  if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
205  if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
206  State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
207  if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
208  State = removeIteratorPosition(State, Call.getArgSVal(0));
209  }
210  C.addTransition(State);
211  return;
212  }
213  }
214 
215  // Assumption: if return value is an iterator which is not yet bound to a
216  // container, then look for the first iterator argument of the
217  // same type as the return value and bind the return value to
218  // the same container. This approach works for STL algorithms.
219  // FIXME: Add a more conservative mode
220  for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
221  if (isIteratorType(Call.getArgExpr(i)->getType()) &&
222  Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType(
223  C.getASTContext()).getTypePtr() ==
224  Call.getResultType().getDesugaredType(C.getASTContext()).getTypePtr()) {
225  if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
226  assignToContainer(C, OrigExpr, Call.getReturnValue(),
227  Pos->getContainer());
228  return;
229  }
230  }
231  }
232 }
233 
234 void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
235  CheckerContext &C) const {
236  auto State = C.getState();
237  const auto *Pos = getIteratorPosition(State, Val);
238  if (Pos) {
239  State = setIteratorPosition(State, Loc, *Pos);
240  C.addTransition(State);
241  } else {
242  const auto *OldPos = getIteratorPosition(State, Loc);
243  if (OldPos) {
244  State = removeIteratorPosition(State, Loc);
245  C.addTransition(State);
246  }
247  }
248 }
249 
250 void IteratorModeling::checkPostStmt(const UnaryOperator *UO,
251  CheckerContext &C) const {
252  UnaryOperatorKind OK = UO->getOpcode();
253  if (!isIncrementOperator(OK) && !isDecrementOperator(OK))
254  return;
255 
256  auto &SVB = C.getSValBuilder();
257  handlePtrIncrOrDecr(C, UO->getSubExpr(),
258  isIncrementOperator(OK) ? OO_Plus : OO_Minus,
259  SVB.makeArrayIndex(1));
260 }
261 
262 void IteratorModeling::checkPostStmt(const BinaryOperator *BO,
263  CheckerContext &C) const {
264  const ProgramStateRef State = C.getState();
265  const BinaryOperatorKind OK = BO->getOpcode();
266  const Expr *const LHS = BO->getLHS();
267  const Expr *const RHS = BO->getRHS();
268  const SVal LVal = State->getSVal(LHS, C.getLocationContext());
269  const SVal RVal = State->getSVal(RHS, C.getLocationContext());
270 
271  if (isSimpleComparisonOperator(BO->getOpcode())) {
272  SVal Result = State->getSVal(BO, C.getLocationContext());
273  handleComparison(C, BO, Result, LVal, RVal,
275  } else if (isRandomIncrOrDecrOperator(OK)) {
276  // In case of operator+ the iterator can be either on the LHS (eg.: it + 1),
277  // or on the RHS (eg.: 1 + it). Both cases are modeled.
278  const bool IsIterOnLHS = BO->getLHS()->getType()->isPointerType();
279  const Expr *const &IterExpr = IsIterOnLHS ? LHS : RHS;
280  const Expr *const &AmountExpr = IsIterOnLHS ? RHS : LHS;
281 
282  // The non-iterator side must have an integral or enumeration type.
283  if (!AmountExpr->getType()->isIntegralOrEnumerationType())
284  return;
285  const SVal &AmountVal = IsIterOnLHS ? RVal : LVal;
286  handlePtrIncrOrDecr(C, IterExpr, BinaryOperator::getOverloadedOperator(OK),
287  AmountVal);
288  }
289 }
290 
291 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
292  CheckerContext &C) const {
293  /* Transfer iterator state to temporary objects */
294  auto State = C.getState();
295  const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
296  if (!Pos)
297  return;
298  State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
299  C.addTransition(State);
300 }
301 
302 void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
303  SymbolReaper &SR) const {
304  // Keep symbolic expressions of iterator positions alive
305  auto RegionMap = State->get<IteratorRegionMap>();
306  for (const auto &Reg : RegionMap) {
307  const auto Offset = Reg.second.getOffset();
308  for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
309  if (isa<SymbolData>(*i))
310  SR.markLive(*i);
311  }
312 
313  auto SymbolMap = State->get<IteratorSymbolMap>();
314  for (const auto &Sym : SymbolMap) {
315  const auto Offset = Sym.second.getOffset();
316  for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
317  if (isa<SymbolData>(*i))
318  SR.markLive(*i);
319  }
320 
321 }
322 
323 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
324  CheckerContext &C) const {
325  // Cleanup
326  auto State = C.getState();
327 
328  auto RegionMap = State->get<IteratorRegionMap>();
329  for (const auto &Reg : RegionMap) {
330  if (!SR.isLiveRegion(Reg.first)) {
331  // The region behind the `LazyCompoundVal` is often cleaned up before
332  // the `LazyCompoundVal` itself. If there are iterator positions keyed
333  // by these regions their cleanup must be deferred.
334  if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
335  State = State->remove<IteratorRegionMap>(Reg.first);
336  }
337  }
338  }
339 
340  auto SymbolMap = State->get<IteratorSymbolMap>();
341  for (const auto &Sym : SymbolMap) {
342  if (!SR.isLive(Sym.first)) {
343  State = State->remove<IteratorSymbolMap>(Sym.first);
344  }
345  }
346 
347  C.addTransition(State);
348 }
349 
350 void
351 IteratorModeling::handleOverloadedOperator(CheckerContext &C,
352  const CallEvent &Call,
353  OverloadedOperatorKind Op) const {
354  if (isSimpleComparisonOperator(Op)) {
355  const auto *OrigExpr = Call.getOriginExpr();
356  if (!OrigExpr)
357  return;
358 
359  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
360  handleComparison(C, OrigExpr, Call.getReturnValue(),
361  InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
362  return;
363  }
364 
365  handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
366  Call.getArgSVal(1), Op);
367  return;
368  } else if (isRandomIncrOrDecrOperator(Op)) {
369  const auto *OrigExpr = Call.getOriginExpr();
370  if (!OrigExpr)
371  return;
372 
373  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
374  if (Call.getNumArgs() >= 1 &&
375  Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
376  handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
377  InstCall->getCXXThisVal(), Call.getArgSVal(0));
378  return;
379  }
380  } else if (Call.getNumArgs() >= 2) {
381  const Expr *FirstArg = Call.getArgExpr(0);
382  const Expr *SecondArg = Call.getArgExpr(1);
383  const QualType FirstType = FirstArg->getType();
384  const QualType SecondType = SecondArg->getType();
385 
386  if (FirstType->isIntegralOrEnumerationType() ||
387  SecondType->isIntegralOrEnumerationType()) {
388  // In case of operator+ the iterator can be either on the LHS (eg.:
389  // it + 1), or on the RHS (eg.: 1 + it). Both cases are modeled.
390  const bool IsIterFirst = FirstType->isStructureOrClassType();
391  const SVal FirstArg = Call.getArgSVal(0);
392  const SVal SecondArg = Call.getArgSVal(1);
393  const SVal &Iterator = IsIterFirst ? FirstArg : SecondArg;
394  const SVal &Amount = IsIterFirst ? SecondArg : FirstArg;
395 
396  handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
397  Iterator, Amount);
398  return;
399  }
400  }
401  } else if (isIncrementOperator(Op)) {
402  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
403  handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
404  Call.getNumArgs());
405  return;
406  }
407 
408  handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
409  Call.getNumArgs());
410  return;
411  } else if (isDecrementOperator(Op)) {
412  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
413  handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
414  Call.getNumArgs());
415  return;
416  }
417 
418  handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
419  Call.getNumArgs());
420  return;
421  }
422 }
423 
424 void
425 IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,
426  const CallEvent &Call,
427  const Expr *OrigExpr,
428  const AdvanceFn *Handler) const {
429  if (!C.wasInlined) {
430  (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
431  Call.getArgSVal(0), Call.getArgSVal(1));
432  return;
433  }
434 
435  // If std::advance() was inlined, but a non-standard function it calls inside
436  // was not, then we have to model it explicitly
437  const auto *IdInfo = cast<FunctionDecl>(Call.getDecl())->getIdentifier();
438  if (IdInfo) {
439  if (IdInfo->getName() == "advance") {
440  if (noChangeInAdvance(C, Call.getArgSVal(0), OrigExpr)) {
441  (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
442  Call.getArgSVal(0), Call.getArgSVal(1));
443  }
444  }
445  }
446 }
447 
448 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
449  SVal RetVal, const SVal &LVal,
450  const SVal &RVal,
451  OverloadedOperatorKind Op) const {
452  // Record the operands and the operator of the comparison for the next
453  // evalAssume, if the result is a symbolic expression. If it is a concrete
454  // value (only one branch is possible), then transfer the state between
455  // the operands according to the operator and the result
456  auto State = C.getState();
457  const auto *LPos = getIteratorPosition(State, LVal);
458  const auto *RPos = getIteratorPosition(State, RVal);
459  const MemRegion *Cont = nullptr;
460  if (LPos) {
461  Cont = LPos->getContainer();
462  } else if (RPos) {
463  Cont = RPos->getContainer();
464  }
465  if (!Cont)
466  return;
467 
468  // At least one of the iterators has recorded positions. If one of them does
469  // not then create a new symbol for the offset.
470  SymbolRef Sym;
471  if (!LPos || !RPos) {
472  auto &SymMgr = C.getSymbolManager();
473  Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
474  C.getASTContext().LongTy, C.blockCount());
475  State = assumeNoOverflow(State, Sym, 4);
476  }
477 
478  if (!LPos) {
480  IteratorPosition::getPosition(Cont, Sym));
481  LPos = getIteratorPosition(State, LVal);
482  } else if (!RPos) {
484  IteratorPosition::getPosition(Cont, Sym));
485  RPos = getIteratorPosition(State, RVal);
486  }
487 
488  // If the value for which we just tried to set a new iterator position is
489  // an `SVal`for which no iterator position can be set then the setting was
490  // unsuccessful. We cannot handle the comparison in this case.
491  if (!LPos || !RPos)
492  return;
493 
494  // We cannot make assumptions on `UnknownVal`. Let us conjure a symbol
495  // instead.
496  if (RetVal.isUnknown()) {
497  auto &SymMgr = C.getSymbolManager();
498  auto *LCtx = C.getLocationContext();
499  RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
500  CE, LCtx, C.getASTContext().BoolTy, C.blockCount()));
501  State = State->BindExpr(CE, LCtx, RetVal);
502  }
503 
504  processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
505 }
506 
507 void IteratorModeling::processComparison(CheckerContext &C,
509  SymbolRef Sym2, const SVal &RetVal,
510  OverloadedOperatorKind Op) const {
511  if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
512  if ((State = relateSymbols(State, Sym1, Sym2,
513  (Op == OO_EqualEqual) ==
514  (TruthVal->getValue() != 0)))) {
515  C.addTransition(State);
516  } else {
517  C.generateSink(State, C.getPredecessor());
518  }
519  return;
520  }
521 
522  const auto ConditionVal = RetVal.getAs<DefinedSVal>();
523  if (!ConditionVal)
524  return;
525 
526  if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
527  StateTrue = StateTrue->assume(*ConditionVal, true);
528  C.addTransition(StateTrue);
529  }
530 
531  if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
532  StateFalse = StateFalse->assume(*ConditionVal, false);
533  C.addTransition(StateFalse);
534  }
535 }
536 
537 void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal,
538  const SVal &Iter, bool Postfix) const {
539  // Increment the symbolic expressions which represents the position of the
540  // iterator
541  auto State = C.getState();
542  auto &BVF = C.getSymbolManager().getBasicVals();
543 
544  const auto *Pos = getIteratorPosition(State, Iter);
545  if (!Pos)
546  return;
547 
548  auto NewState =
549  advancePosition(State, Iter, OO_Plus,
550  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
551  assert(NewState &&
552  "Advancing position by concrete int should always be successful");
553 
554  const auto *NewPos = getIteratorPosition(NewState, Iter);
555  assert(NewPos &&
556  "Iterator should have position after successful advancement");
557 
558  State = setIteratorPosition(State, Iter, *NewPos);
559  State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
560  C.addTransition(State);
561 }
562 
563 void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal,
564  const SVal &Iter, bool Postfix) const {
565  // Decrement the symbolic expressions which represents the position of the
566  // iterator
567  auto State = C.getState();
568  auto &BVF = C.getSymbolManager().getBasicVals();
569 
570  const auto *Pos = getIteratorPosition(State, Iter);
571  if (!Pos)
572  return;
573 
574  auto NewState =
575  advancePosition(State, Iter, OO_Minus,
576  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
577  assert(NewState &&
578  "Advancing position by concrete int should always be successful");
579 
580  const auto *NewPos = getIteratorPosition(NewState, Iter);
581  assert(NewPos &&
582  "Iterator should have position after successful advancement");
583 
584  State = setIteratorPosition(State, Iter, *NewPos);
585  State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
586  C.addTransition(State);
587 }
588 
589 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
591  const SVal &RetVal,
592  const SVal &Iterator,
593  const SVal &Amount) const {
594  // Increment or decrement the symbolic expressions which represents the
595  // position of the iterator
596  auto State = C.getState();
597 
598  const auto *Pos = getIteratorPosition(State, Iterator);
599  if (!Pos)
600  return;
601 
602  const auto *Value = &Amount;
603  SVal Val;
604  if (auto LocAmount = Amount.getAs<Loc>()) {
605  Val = State->getRawSVal(*LocAmount);
606  Value = &Val;
607  }
608 
609  const auto &TgtVal =
610  (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iterator : RetVal;
611 
612  // `AdvancedState` is a state where the position of `LHS` is advanced. We
613  // only need this state to retrieve the new position, but we do not want
614  // to change the position of `LHS` (in every case).
615  auto AdvancedState = advancePosition(State, Iterator, Op, *Value);
616  if (AdvancedState) {
617  const auto *NewPos = getIteratorPosition(AdvancedState, Iterator);
618  assert(NewPos &&
619  "Iterator should have position after successful advancement");
620 
621  State = setIteratorPosition(State, TgtVal, *NewPos);
622  C.addTransition(State);
623  } else {
624  assignToContainer(C, CE, TgtVal, Pos->getContainer());
625  }
626 }
627 
628 void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
629  const Expr *Iterator,
631  SVal Offset) const {
632  if (!isa<DefinedSVal>(Offset))
633  return;
634 
635  QualType PtrType = Iterator->getType();
636  if (!PtrType->isPointerType())
637  return;
638  QualType ElementType = PtrType->getPointeeType();
639 
640  ProgramStateRef State = C.getState();
641  SVal OldVal = State->getSVal(Iterator, C.getLocationContext());
642 
643  const IteratorPosition *OldPos = getIteratorPosition(State, OldVal);
644  if (!OldPos)
645  return;
646 
647  SVal NewVal;
648  if (OK == OO_Plus || OK == OO_PlusEqual) {
649  NewVal = State->getLValue(ElementType, Offset, OldVal);
650  } else {
651  auto &SVB = C.getSValBuilder();
652  SVal NegatedOffset = SVB.evalMinus(Offset.castAs<NonLoc>());
653  NewVal = State->getLValue(ElementType, NegatedOffset, OldVal);
654  }
655 
656  // `AdvancedState` is a state where the position of `Old` is advanced. We
657  // only need this state to retrieve the new position, but we do not want
658  // ever to change the position of `OldVal`.
659  auto AdvancedState = advancePosition(State, OldVal, OK, Offset);
660  if (AdvancedState) {
661  const IteratorPosition *NewPos = getIteratorPosition(AdvancedState, OldVal);
662  assert(NewPos &&
663  "Iterator should have position after successful advancement");
664 
665  ProgramStateRef NewState = setIteratorPosition(State, NewVal, *NewPos);
666  C.addTransition(NewState);
667  } else {
668  assignToContainer(C, Iterator, NewVal, OldPos->getContainer());
669  }
670 }
671 
672 void IteratorModeling::handleAdvance(CheckerContext &C, const Expr *CE,
673  SVal RetVal, SVal Iter,
674  SVal Amount) const {
675  handleRandomIncrOrDecr(C, CE, OO_PlusEqual, RetVal, Iter, Amount);
676 }
677 
678 void IteratorModeling::handlePrev(CheckerContext &C, const Expr *CE,
679  SVal RetVal, SVal Iter, SVal Amount) const {
680  handleRandomIncrOrDecr(C, CE, OO_Minus, RetVal, Iter, Amount);
681 }
682 
683 void IteratorModeling::handleNext(CheckerContext &C, const Expr *CE,
684  SVal RetVal, SVal Iter, SVal Amount) const {
685  handleRandomIncrOrDecr(C, CE, OO_Plus, RetVal, Iter, Amount);
686 }
687 
688 void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
689  const SVal &RetVal,
690  const MemRegion *Cont) const {
691  Cont = Cont->getMostDerivedObjectRegion();
692 
693  auto State = C.getState();
694  const auto *LCtx = C.getLocationContext();
695  State = createIteratorPosition(State, RetVal, Cont, CE, LCtx, C.blockCount());
696 
697  C.addTransition(State);
698 }
699 
700 bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,
701  const Expr *CE) const {
702  // Compare the iterator position before and after the call. (To be called
703  // from `checkPostCall()`.)
704  const auto StateAfter = C.getState();
705 
706  const auto *PosAfter = getIteratorPosition(StateAfter, Iter);
707  // If we have no position after the call of `std::advance`, then we are not
708  // interested. (Modeling of an inlined `std::advance()` should not remove the
709  // position in any case.)
710  if (!PosAfter)
711  return false;
712 
713  const ExplodedNode *N = findCallEnter(C.getPredecessor(), CE);
714  assert(N && "Any call should have a `CallEnter` node.");
715 
716  const auto StateBefore = N->getState();
717  const auto *PosBefore = getIteratorPosition(StateBefore, Iter);
718  // FIXME: `std::advance()` should not create a new iterator position but
719  // change existing ones. However, in case of iterators implemented as
720  // pointers the handling of parameters in `std::advance()`-like
721  // functions is still incomplete which may result in cases where
722  // the new position is assigned to the wrong pointer. This causes
723  // crash if we use an assertion here.
724  if (!PosBefore)
725  return false;
726 
727  return PosBefore->getOffset() == PosAfter->getOffset();
728 }
729 
730 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
731  const char *NL, const char *Sep) const {
732  auto SymbolMap = State->get<IteratorSymbolMap>();
733  auto RegionMap = State->get<IteratorRegionMap>();
734  // Use a counter to add newlines before every line except the first one.
735  unsigned Count = 0;
736 
737  if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
738  Out << Sep << "Iterator Positions :" << NL;
739  for (const auto &Sym : SymbolMap) {
740  if (Count++)
741  Out << NL;
742 
743  Sym.first->dumpToStream(Out);
744  Out << " : ";
745  const auto Pos = Sym.second;
746  Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
747  Pos.getContainer()->dumpToStream(Out);
748  Out<<" ; Offset == ";
749  Pos.getOffset()->dumpToStream(Out);
750  }
751 
752  for (const auto &Reg : RegionMap) {
753  if (Count++)
754  Out << NL;
755 
756  Reg.first->dumpToStream(Out);
757  Out << " : ";
758  const auto Pos = Reg.second;
759  Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
760  Pos.getContainer()->dumpToStream(Out);
761  Out<<" ; Offset == ";
762  Pos.getOffset()->dumpToStream(Out);
763  }
764  }
765 }
766 
767 namespace {
768 
769 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
770  return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
771 }
772 
773 bool isSimpleComparisonOperator(BinaryOperatorKind OK) {
774  return OK == BO_EQ || OK == BO_NE;
775 }
776 
777 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
778  if (auto Reg = Val.getAsRegion()) {
779  Reg = Reg->getMostDerivedObjectRegion();
780  return State->remove<IteratorRegionMap>(Reg);
781  } else if (const auto Sym = Val.getAsSymbol()) {
782  return State->remove<IteratorSymbolMap>(Sym);
783  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
784  return State->remove<IteratorRegionMap>(LCVal->getRegion());
785  }
786  return nullptr;
787 }
788 
789 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
790  SymbolRef Sym2, bool Equal) {
791  auto &SVB = State->getStateManager().getSValBuilder();
792 
793  // FIXME: This code should be reworked as follows:
794  // 1. Subtract the operands using evalBinOp().
795  // 2. Assume that the result doesn't overflow.
796  // 3. Compare the result to 0.
797  // 4. Assume the result of the comparison.
798  const auto comparison =
799  SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
800  nonloc::SymbolVal(Sym2), SVB.getConditionType());
801 
802  assert(isa<DefinedSVal>(comparison) &&
803  "Symbol comparison must be a `DefinedSVal`");
804 
805  auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
806  if (!NewState)
807  return nullptr;
808 
809  if (const auto CompSym = comparison.getAsSymbol()) {
810  assert(isa<SymIntExpr>(CompSym) &&
811  "Symbol comparison must be a `SymIntExpr`");
813  cast<SymIntExpr>(CompSym)->getOpcode()) &&
814  "Symbol comparison must be a comparison");
815  return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
816  }
817 
818  return NewState;
819 }
820 
821 bool isBoundThroughLazyCompoundVal(const Environment &Env,
822  const MemRegion *Reg) {
823  for (const auto &Binding : Env) {
824  if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
825  if (LCVal->getRegion() == Reg)
826  return true;
827  }
828  }
829 
830  return false;
831 }
832 
833 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) {
834  while (Node) {
835  ProgramPoint PP = Node->getLocation();
836  if (auto Enter = PP.getAs<CallEnter>()) {
837  if (Enter->getCallExpr() == Call)
838  break;
839  }
840 
841  Node = Node->getFirstPred();
842  }
843 
844  return Node;
845 }
846 
847 } // namespace
848 
849 void ento::registerIteratorModeling(CheckerManager &mgr) {
850  mgr.registerChecker<IteratorModeling>();
851 }
852 
853 bool ento::shouldRegisterIteratorModeling(const CheckerManager &mgr) {
854  return true;
855 }
CallDescription.h
clang::MaterializeTemporaryExpr::getSubExpr
Expr * getSubExpr() const
Retrieve the temporary-generating subexpression whose value will be materialized into a glvalue.
Definition: ExprCXX.h:4496
clang::ento::iterator::isIteratorType
bool isIteratorType(const QualType &Type)
Definition: Iterator.cpp:19
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:731
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:55
clang::ento::SymbolRef
const SymExpr * SymbolRef
Definition: SymExpr.h:111
clang::UnaryOperator
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2163
clang::index::SymbolRole::Call
@ Call
clang::BinaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:3851
CallEvent.h
Offset
unsigned Offset
Definition: Format.cpp:2574
clang::ento::iterator::createIteratorPosition
ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, const MemRegion *Cont, const Stmt *S, const LocationContext *LCtx, unsigned blockCount)
Definition: Iterator.cpp:210
BuiltinCheckerRegistration.h
DeclTemplate.h
Node
DynTypedNode Node
Definition: ASTMatchFinder.cpp:68
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3807
clang::ento::iterator::assumeNoOverflow
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale)
Definition: Iterator.cpp:265
clang::MaterializeTemporaryExpr
Represents a prvalue temporary that is written into memory so that a reference can bind to it.
Definition: ExprCXX.h:4479
clang::ProgramPoint::getAs
Optional< T > getAs() const
Convert to the specified ProgramPoint type, returning None if this ProgramPoint is not of the desired...
Definition: ProgramPoint.h:150
clang::ento::iterator::getIteratorPosition
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
Definition: Iterator.cpp:184
clang::ento::iterator::isIncrementOperator
bool isIncrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:153
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::ento::iterator::IteratorPosition::getPosition
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of)
Definition: Iterator.h:50
clang::OverloadedOperatorKind
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
Definition: OperatorKinds.h:21
clang::Type::isPointerType
bool isPointerType() const
Definition: Type.h:6807
BugType.h
clang::BinaryOperator::getLHS
Expr * getLHS() const
Definition: Expr.h:3856
Iterator.h
Value
Value
Definition: UninitializedValues.cpp:102
clang::BinaryOperator::isComparisonOp
bool isComparisonOp() const
Definition: Expr.h:3907
State
LineState State
Definition: UnwrappedLineFormatter.cpp:1126
clang::UnaryOperatorKind
UnaryOperatorKind
Definition: OperationKinds.h:30
clang::BinaryOperatorKind
BinaryOperatorKind
Definition: OperationKinds.h:25
CheckerContext.h
clang::Type::isStructureOrClassType
bool isStructureOrClassType() const
Definition: Type.cpp:581
Checker.h
clang::UnaryOperator::getSubExpr
Expr * getSubExpr() const
Definition: Expr.h:2210
clang
Definition: CalledOnceCheck.h:17
clang::ento::iterator::isRandomIncrOrDecrOperator
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:169
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:70
clang::UnaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:2205
clang::BinaryOperator::getRHS
Expr * getRHS() const
Definition: Expr.h:3858
clang::Expr::getType
QualType getType() const
Definition: Expr.h:141
clang::BinaryOperator::getOverloadedOperator
static OverloadedOperatorKind getOverloadedOperator(Opcode Opc)
Retrieve the overloaded operator kind that corresponds to the given binary opcode.
Definition: Expr.cpp:2087
clang::ento::iterator::setIteratorPosition
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, const IteratorPosition &Pos)
Definition: Iterator.cpp:197
clang::CallEnter
Represents a point when we begin processing an inlined call.
Definition: ProgramPoint.h:629
clang::ento::iterator::isDecrementOperator
bool isDecrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:161
DynamicType.h
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::ProgramPoint
Definition: ProgramPoint.h:58
clang::Type::isIntegralOrEnumerationType
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:7199
clang::ento::iterator::advancePosition
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance)
Definition: Iterator.cpp:224