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