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