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/Checker.h"
70#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
71#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
72#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
73#include "llvm/ADT/STLExtras.h"
74
75#include "Iterator.h"
76
77#include <utility>
78
79using namespace clang;
80using namespace ento;
81using namespace iterator;
82
83namespace {
84
85class 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 &,
92 ConstCFGElementRef, SVal, SVal,
93 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,
102 ConstCFGElementRef Elem, SVal RetVal, SVal LVal,
103 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, ConstCFGElementRef Elem,
112 OverloadedOperatorKind Op, SVal RetVal,
113 SVal Iterator, SVal Amount) const;
114 void handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,
115 ConstCFGElementRef Elem, OverloadedOperatorKind OK,
116 SVal Offset) const;
117 void handleAdvance(CheckerContext &C, ConstCFGElementRef Elem, SVal RetVal,
118 SVal Iter, SVal Amount) const;
119 void handlePrev(CheckerContext &C, ConstCFGElementRef Elem, SVal RetVal,
120 SVal Iter, SVal Amount) const;
121 void handleNext(CheckerContext &C, ConstCFGElementRef Elem, SVal RetVal,
122 SVal Iter, SVal Amount) const;
123 void assignToContainer(CheckerContext &C, ConstCFGElementRef Elem,
124 SVal RetVal, const MemRegion *Cont) const;
125 bool noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const;
126 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
127 const char *Sep) const override;
128
129 // std::advance, std::prev & std::next
130 CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {
131 // template<class InputIt, class Distance>
132 // void advance(InputIt& it, Distance n);
133 {{CDM::SimpleFunc, {"std", "advance"}, 2},
134 &IteratorModeling::handleAdvance},
135
136 // template<class BidirIt>
137 // BidirIt prev(
138 // BidirIt it,
139 // typename std::iterator_traits<BidirIt>::difference_type n = 1);
140 {{CDM::SimpleFunc, {"std", "prev"}, 2}, &IteratorModeling::handlePrev},
141
142 // template<class ForwardIt>
143 // ForwardIt next(
144 // ForwardIt it,
145 // typename std::iterator_traits<ForwardIt>::difference_type n = 1);
146 {{CDM::SimpleFunc, {"std", "next"}, 2}, &IteratorModeling::handleNext},
147 };
148
149public:
150 IteratorModeling() = default;
151
152 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
153 void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
154 void checkPostStmt(const UnaryOperator *UO, CheckerContext &C) const;
155 void checkPostStmt(const BinaryOperator *BO, CheckerContext &C) const;
156 void checkPostStmt(const MaterializeTemporaryExpr *MTE,
157 CheckerContext &C) const;
158 void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
159 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
160};
161
162bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
163bool isSimpleComparisonOperator(BinaryOperatorKind OK);
164ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val);
165ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
166 SymbolRef Sym2, bool Equal);
167bool isBoundThroughLazyCompoundVal(const Environment &Env,
168 const MemRegion *Reg);
169const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);
170
171} // namespace
172
173void IteratorModeling::checkPostCall(const CallEvent &Call,
174 CheckerContext &C) const {
175 // Record new iterator positions and iterator position changes
176 const auto *Func = dyn_cast_or_null<FunctionDecl>(Val: Call.getDecl());
177 if (!Func)
178 return;
179
180 if (Func->isOverloadedOperator()) {
181 const auto Op = Func->getOverloadedOperator();
182 handleOverloadedOperator(C, Call, Op);
183 return;
184 }
185
186 const auto *OrigExpr = Call.getOriginExpr();
187 if (!OrigExpr)
188 return;
189
190 const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(Call);
191 if (Handler) {
192 handleAdvanceLikeFunction(C, Call, OrigExpr, Handler);
193 return;
194 }
195
196 if (!isIteratorType(Type: Call.getResultType()))
197 return;
198
199 auto State = C.getState();
200
201 // Already bound to container?
202 if (getIteratorPosition(State, Val: Call.getReturnValue()))
203 return;
204
205 // Copy-like and move constructors
206 if (isa<CXXConstructorCall>(Val: &Call) && Call.getNumArgs() == 1) {
207 if (const auto *Pos = getIteratorPosition(State, Val: Call.getArgSVal(Index: 0))) {
208 State = setIteratorPosition(State, Val: Call.getReturnValue(), Pos: *Pos);
209 if (cast<CXXConstructorDecl>(Val: Func)->isMoveConstructor()) {
210 State = removeIteratorPosition(State, Val: Call.getArgSVal(Index: 0));
211 }
212 C.addTransition(State);
213 return;
214 }
215 }
216
217 // Assumption: if return value is an iterator which is not yet bound to a
218 // container, then look for the first iterator argument of the
219 // same type as the return value and bind the return value to
220 // the same container. This approach works for STL algorithms.
221 // FIXME: Add a more conservative mode
222 for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
223 if (isIteratorType(Type: Call.getArgExpr(Index: i)->getType()) &&
224 Call.getArgExpr(Index: i)->getType().getNonReferenceType().getDesugaredType(
225 Context: C.getASTContext()).getTypePtr() ==
226 Call.getResultType().getDesugaredType(Context: C.getASTContext()).getTypePtr()) {
227 if (const auto *Pos = getIteratorPosition(State, Val: Call.getArgSVal(Index: i))) {
228 assignToContainer(C, Elem: Call.getCFGElementRef(), RetVal: Call.getReturnValue(),
229 Cont: Pos->getContainer());
230 return;
231 }
232 }
233 }
234}
235
236void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
237 CheckerContext &C) const {
238 auto State = C.getState();
239 const auto *Pos = getIteratorPosition(State, Val);
240 if (Pos) {
241 State = setIteratorPosition(State, Val: Loc, Pos: *Pos);
242 C.addTransition(State);
243 } else {
244 const auto *OldPos = getIteratorPosition(State, Val: Loc);
245 if (OldPos) {
246 State = removeIteratorPosition(State, Val: Loc);
247 C.addTransition(State);
248 }
249 }
250}
251
252void IteratorModeling::checkPostStmt(const UnaryOperator *UO,
253 CheckerContext &C) const {
254 UnaryOperatorKind OK = UO->getOpcode();
255 if (!isIncrementOperator(OK) && !isDecrementOperator(OK))
256 return;
257
258 auto &SVB = C.getSValBuilder();
259 handlePtrIncrOrDecr(C, Iterator: UO->getSubExpr(), Elem: C.getCFGElementRef(),
260 OK: isIncrementOperator(OK) ? OO_Plus : OO_Minus,
261 Offset: SVB.makeArrayIndex(idx: 1));
262}
263
264void IteratorModeling::checkPostStmt(const BinaryOperator *BO,
265 CheckerContext &C) const {
266 const ProgramStateRef State = C.getState();
267 const BinaryOperatorKind OK = BO->getOpcode();
268 const Expr *const LHS = BO->getLHS();
269 const Expr *const RHS = BO->getRHS();
270 const SVal LVal = State->getSVal(LHS, C.getLocationContext());
271 const SVal RVal = State->getSVal(RHS, C.getLocationContext());
272
273 if (isSimpleComparisonOperator(OK: BO->getOpcode())) {
274 SVal Result = State->getSVal(BO, C.getLocationContext());
275 handleComparison(C, BO, C.getCFGElementRef(), Result, LVal, RVal,
276 BinaryOperator::getOverloadedOperator(Opc: OK));
277 } else if (isRandomIncrOrDecrOperator(OK)) {
278 // In case of operator+ the iterator can be either on the LHS (eg.: it + 1),
279 // or on the RHS (eg.: 1 + it). Both cases are modeled.
280 const bool IsIterOnLHS = BO->getLHS()->getType()->isPointerType();
281 const Expr *const &IterExpr = IsIterOnLHS ? LHS : RHS;
282 const Expr *const &AmountExpr = IsIterOnLHS ? RHS : LHS;
283
284 // The non-iterator side must have an integral or enumeration type.
285 if (!AmountExpr->getType()->isIntegralOrEnumerationType())
286 return;
287 SVal AmountVal = IsIterOnLHS ? RVal : LVal;
288 handlePtrIncrOrDecr(C, Iterator: IterExpr, Elem: C.getCFGElementRef(),
289 OK: BinaryOperator::getOverloadedOperator(Opc: OK), Offset: AmountVal);
290 }
291}
292
293void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
294 CheckerContext &C) const {
295 /* Transfer iterator state to temporary objects */
296 auto State = C.getState();
297 const auto *Pos = getIteratorPosition(State, Val: C.getSVal(MTE->getSubExpr()));
298 if (!Pos)
299 return;
300 State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
301 C.addTransition(State);
302}
303
304void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
305 SymbolReaper &SR) const {
306 // Keep symbolic expressions of iterator positions alive
307 auto RegionMap = State->get<IteratorRegionMap>();
308 for (const IteratorPosition &Pos : llvm::make_second_range(c&: RegionMap)) {
309 for (SymbolRef Sym : Pos.getOffset()->symbols())
310 if (isa<SymbolData>(Val: Sym))
311 SR.markLive(sym: Sym);
312 }
313
314 auto SymbolMap = State->get<IteratorSymbolMap>();
315 for (const IteratorPosition &Pos : llvm::make_second_range(c&: SymbolMap)) {
316 for (SymbolRef Sym : Pos.getOffset()->symbols())
317 if (isa<SymbolData>(Val: Sym))
318 SR.markLive(sym: Sym);
319 }
320}
321
322void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
323 CheckerContext &C) const {
324 // Cleanup
325 auto State = C.getState();
326
327 auto RegionMap = State->get<IteratorRegionMap>();
328 for (const auto &Reg : RegionMap) {
329 if (!SR.isLiveRegion(region: Reg.first)) {
330 // The region behind the `LazyCompoundVal` is often cleaned up before
331 // the `LazyCompoundVal` itself. If there are iterator positions keyed
332 // by these regions their cleanup must be deferred.
333 if (!isBoundThroughLazyCompoundVal(Env: State->getEnvironment(), Reg: Reg.first)) {
334 State = State->remove<IteratorRegionMap>(K: Reg.first);
335 }
336 }
337 }
338
339 auto SymbolMap = State->get<IteratorSymbolMap>();
340 for (const auto &Sym : SymbolMap) {
341 if (!SR.isLive(sym: Sym.first)) {
342 State = State->remove<IteratorSymbolMap>(K: Sym.first);
343 }
344 }
345
346 C.addTransition(State);
347}
348
349void
350IteratorModeling::handleOverloadedOperator(CheckerContext &C,
351 const CallEvent &Call,
352 OverloadedOperatorKind Op) const {
353 if (isSimpleComparisonOperator(OK: Op)) {
354 const auto *OrigExpr = Call.getOriginExpr();
355 const auto Elem = Call.getCFGElementRef();
356 if (!OrigExpr)
357 return;
358
359 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(Val: &Call)) {
360 handleComparison(C, CE: OrigExpr, Elem, RetVal: Call.getReturnValue(),
361 LVal: InstCall->getCXXThisVal(), RVal: Call.getArgSVal(Index: 0), Op);
362 return;
363 }
364
365 handleComparison(C, CE: OrigExpr, Elem, RetVal: Call.getReturnValue(),
366 LVal: Call.getArgSVal(Index: 0), RVal: Call.getArgSVal(Index: 1), Op);
367 return;
368 } else if (isRandomIncrOrDecrOperator(OK: Op)) {
369 const auto *OrigExpr = Call.getOriginExpr();
370 const auto Elem = Call.getCFGElementRef();
371 if (!OrigExpr)
372 return;
373
374 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(Val: &Call)) {
375 if (Call.getNumArgs() >= 1 &&
376 Call.getArgExpr(Index: 0)->getType()->isIntegralOrEnumerationType()) {
377 handleRandomIncrOrDecr(C, Elem, Op, RetVal: Call.getReturnValue(),
378 Iterator: InstCall->getCXXThisVal(), Amount: Call.getArgSVal(Index: 0));
379 return;
380 }
381 } else if (Call.getNumArgs() >= 2) {
382 const Expr *FirstArg = Call.getArgExpr(Index: 0);
383 const Expr *SecondArg = Call.getArgExpr(Index: 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(Index: 0);
393 const SVal SecondArg = Call.getArgSVal(Index: 1);
394 SVal Iterator = IsIterFirst ? FirstArg : SecondArg;
395 SVal Amount = IsIterFirst ? SecondArg : FirstArg;
396
397 handleRandomIncrOrDecr(C, Elem, Op, RetVal: Call.getReturnValue(), Iterator,
398 Amount);
399 return;
400 }
401 }
402 } else if (isIncrementOperator(OK: Op)) {
403 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(Val: &Call)) {
404 handleIncrement(C, RetVal: Call.getReturnValue(), Iter: InstCall->getCXXThisVal(),
405 Postfix: Call.getNumArgs());
406 return;
407 }
408
409 handleIncrement(C, RetVal: Call.getReturnValue(), Iter: Call.getArgSVal(Index: 0),
410 Postfix: Call.getNumArgs());
411 return;
412 } else if (isDecrementOperator(OK: Op)) {
413 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(Val: &Call)) {
414 handleDecrement(C, RetVal: Call.getReturnValue(), Iter: InstCall->getCXXThisVal(),
415 Postfix: Call.getNumArgs());
416 return;
417 }
418
419 handleDecrement(C, RetVal: Call.getReturnValue(), Iter: Call.getArgSVal(Index: 0),
420 Postfix: Call.getNumArgs());
421 return;
422 }
423}
424
425void
426IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,
427 const CallEvent &Call,
428 const Expr *OrigExpr,
429 const AdvanceFn *Handler) const {
430 if (!C.wasInlined) {
431 (this->**Handler)(C, Call.getCFGElementRef(), Call.getReturnValue(),
432 Call.getArgSVal(Index: 0), Call.getArgSVal(Index: 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>(Val: Call.getDecl())->getIdentifier();
439 if (IdInfo) {
440 if (IdInfo->getName() == "advance") {
441 if (noChangeInAdvance(C, Iter: Call.getArgSVal(Index: 0), CE: OrigExpr)) {
442 (this->**Handler)(C, Call.getCFGElementRef(), Call.getReturnValue(),
443 Call.getArgSVal(Index: 0), Call.getArgSVal(Index: 1));
444 }
445 }
446 }
447}
448
449void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
450 ConstCFGElementRef Elem, SVal RetVal,
451 SVal LVal, 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, Val: LVal);
459 const auto *RPos = getIteratorPosition(State, Val: 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(Elem, LCtx: C.getLocationContext(),
475 T: C.getASTContext().LongTy, VisitCount: C.blockCount());
476 State = assumeNoOverflow(State, Sym, Scale: 4);
477 }
478
479 if (!LPos) {
480 State = setIteratorPosition(State, Val: LVal,
481 Pos: IteratorPosition::getPosition(C: Cont, Of: Sym));
482 LPos = getIteratorPosition(State, Val: LVal);
483 } else if (!RPos) {
484 State = setIteratorPosition(State, Val: RVal,
485 Pos: IteratorPosition::getPosition(C: Cont, Of: Sym));
486 RPos = getIteratorPosition(State, Val: 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 Elem, LCtx, T: C.getASTContext().BoolTy, VisitCount: C.blockCount()));
502 State = State->BindExpr(CE, LCtx, RetVal);
503 }
504
505 processComparison(C, State, Sym1: LPos->getOffset(), Sym2: RPos->getOffset(), RetVal, Op);
506}
507
508void IteratorModeling::processComparison(CheckerContext &C,
509 ProgramStateRef State, SymbolRef Sym1,
510 SymbolRef Sym2, SVal RetVal,
511 OverloadedOperatorKind Op) const {
512 if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
513 if ((State = relateSymbols(State, Sym1, Sym2,
514 Equal: (Op == OO_EqualEqual) ==
515 (TruthVal->getValue()->getBoolValue())))) {
516 C.addTransition(State);
517 } else {
518 C.generateSink(State, Pred: 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, Equal: Op == OO_EqualEqual)) {
528 StateTrue = StateTrue->assume(Cond: *ConditionVal, Assumption: true);
529 C.addTransition(State: StateTrue);
530 }
531
532 if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Equal: Op != OO_EqualEqual)) {
533 StateFalse = StateFalse->assume(Cond: *ConditionVal, Assumption: false);
534 C.addTransition(State: StateFalse);
535 }
536}
537
538void IteratorModeling::handleIncrement(CheckerContext &C, SVal RetVal,
539 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, Val: Iter);
546 if (!Pos)
547 return;
548
549 auto NewState =
550 advancePosition(State, Iter, Op: OO_Plus,
551 Distance: nonloc::ConcreteInt(BVF.getValue(X: llvm::APSInt::get(X: 1))));
552 assert(NewState &&
553 "Advancing position by concrete int should always be successful");
554
555 const auto *NewPos = getIteratorPosition(State: NewState, Val: Iter);
556 assert(NewPos &&
557 "Iterator should have position after successful advancement");
558
559 State = setIteratorPosition(State, Val: Iter, Pos: *NewPos);
560 State = setIteratorPosition(State, Val: RetVal, Pos: Postfix ? *Pos : *NewPos);
561 C.addTransition(State);
562}
563
564void IteratorModeling::handleDecrement(CheckerContext &C, SVal RetVal,
565 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, Val: Iter);
572 if (!Pos)
573 return;
574
575 auto NewState =
576 advancePosition(State, Iter, Op: OO_Minus,
577 Distance: nonloc::ConcreteInt(BVF.getValue(X: llvm::APSInt::get(X: 1))));
578 assert(NewState &&
579 "Advancing position by concrete int should always be successful");
580
581 const auto *NewPos = getIteratorPosition(State: NewState, Val: Iter);
582 assert(NewPos &&
583 "Iterator should have position after successful advancement");
584
585 State = setIteratorPosition(State, Val: Iter, Pos: *NewPos);
586 State = setIteratorPosition(State, Val: RetVal, Pos: Postfix ? *Pos : *NewPos);
587 C.addTransition(State);
588}
589
590void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C,
591 ConstCFGElementRef Elem,
592 OverloadedOperatorKind Op,
593 SVal RetVal, SVal Iterator,
594 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, Val: 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(LV: *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, Iter: Iterator, Op, Distance: *Value);
617 if (AdvancedState) {
618 const auto *NewPos = getIteratorPosition(State: AdvancedState, Val: Iterator);
619 assert(NewPos &&
620 "Iterator should have position after successful advancement");
621
622 State = setIteratorPosition(State, Val: TgtVal, Pos: *NewPos);
623 C.addTransition(State);
624 } else {
625 assignToContainer(C, Elem, RetVal: TgtVal, Cont: Pos->getContainer());
626 }
627}
628
629void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
630 const Expr *Iterator,
631 ConstCFGElementRef Elem,
632 OverloadedOperatorKind OK,
633 SVal Offset) const {
634 if (!isa<DefinedSVal>(Val: Offset))
635 return;
636
637 QualType PtrType = Iterator->getType();
638 if (!PtrType->isPointerType())
639 return;
640 QualType ElementType = PtrType->getPointeeType();
641
642 ProgramStateRef State = C.getState();
643 SVal OldVal = State->getSVal(Iterator, C.getLocationContext());
644
645 const IteratorPosition *OldPos = getIteratorPosition(State, Val: OldVal);
646 if (!OldPos)
647 return;
648
649 SVal NewVal;
650 if (OK == OO_Plus || OK == OO_PlusEqual) {
651 NewVal = State->getLValue(ElementType, Idx: Offset, Base: OldVal);
652 } else {
653 auto &SVB = C.getSValBuilder();
654 SVal NegatedOffset = SVB.evalMinus(val: Offset.castAs<NonLoc>());
655 NewVal = State->getLValue(ElementType, Idx: NegatedOffset, Base: OldVal);
656 }
657
658 // `AdvancedState` is a state where the position of `Old` is advanced. We
659 // only need this state to retrieve the new position, but we do not want
660 // ever to change the position of `OldVal`.
661 auto AdvancedState = advancePosition(State, Iter: OldVal, Op: OK, Distance: Offset);
662 if (AdvancedState) {
663 const IteratorPosition *NewPos = getIteratorPosition(AdvancedState, OldVal);
664 assert(NewPos &&
665 "Iterator should have position after successful advancement");
666
667 ProgramStateRef NewState = setIteratorPosition(State, Val: NewVal, Pos: *NewPos);
668 C.addTransition(State: NewState);
669 } else {
670 assignToContainer(C, Elem, RetVal: NewVal, Cont: OldPos->getContainer());
671 }
672}
673
674void IteratorModeling::handleAdvance(CheckerContext &C, ConstCFGElementRef Elem,
675 SVal RetVal, SVal Iter,
676 SVal Amount) const {
677 handleRandomIncrOrDecr(C, Elem, Op: OO_PlusEqual, RetVal, Iterator: Iter, Amount);
678}
679
680void IteratorModeling::handlePrev(CheckerContext &C, ConstCFGElementRef Elem,
681 SVal RetVal, SVal Iter, SVal Amount) const {
682 handleRandomIncrOrDecr(C, Elem, Op: OO_Minus, RetVal, Iterator: Iter, Amount);
683}
684
685void IteratorModeling::handleNext(CheckerContext &C, ConstCFGElementRef Elem,
686 SVal RetVal, SVal Iter, SVal Amount) const {
687 handleRandomIncrOrDecr(C, Elem, Op: OO_Plus, RetVal, Iterator: Iter, Amount);
688}
689
690void IteratorModeling::assignToContainer(CheckerContext &C,
691 ConstCFGElementRef Elem, SVal RetVal,
692 const MemRegion *Cont) const {
693 Cont = Cont->getMostDerivedObjectRegion();
694
695 auto State = C.getState();
696 const auto *LCtx = C.getLocationContext();
697 State =
698 createIteratorPosition(State, Val: RetVal, Cont, Elem, LCtx, blockCount: C.blockCount());
699
700 C.addTransition(State);
701}
702
703bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,
704 const Expr *CE) const {
705 // Compare the iterator position before and after the call. (To be called
706 // from `checkPostCall()`.)
707 const auto StateAfter = C.getState();
708
709 const auto *PosAfter = getIteratorPosition(State: StateAfter, Val: Iter);
710 // If we have no position after the call of `std::advance`, then we are not
711 // interested. (Modeling of an inlined `std::advance()` should not remove the
712 // position in any case.)
713 if (!PosAfter)
714 return false;
715
716 const ExplodedNode *N = findCallEnter(Node: C.getPredecessor(), Call: CE);
717 assert(N && "Any call should have a `CallEnter` node.");
718
719 const auto StateBefore = N->getState();
720 const auto *PosBefore = getIteratorPosition(State: StateBefore, Val: Iter);
721 // FIXME: `std::advance()` should not create a new iterator position but
722 // change existing ones. However, in case of iterators implemented as
723 // pointers the handling of parameters in `std::advance()`-like
724 // functions is still incomplete which may result in cases where
725 // the new position is assigned to the wrong pointer. This causes
726 // crash if we use an assertion here.
727 if (!PosBefore)
728 return false;
729
730 return PosBefore->getOffset() == PosAfter->getOffset();
731}
732
733void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
734 const char *NL, const char *Sep) const {
735 auto SymbolMap = State->get<IteratorSymbolMap>();
736 auto RegionMap = State->get<IteratorRegionMap>();
737 // Use a counter to add newlines before every line except the first one.
738 unsigned Count = 0;
739
740 if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
741 Out << Sep << "Iterator Positions :" << NL;
742 for (const auto &Sym : SymbolMap) {
743 if (Count++)
744 Out << NL;
745
746 Sym.first->dumpToStream(os&: Out);
747 Out << " : ";
748 const auto Pos = Sym.second;
749 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
750 Pos.getContainer()->dumpToStream(os&: Out);
751 Out<<" ; Offset == ";
752 Pos.getOffset()->dumpToStream(os&: Out);
753 }
754
755 for (const auto &Reg : RegionMap) {
756 if (Count++)
757 Out << NL;
758
759 Reg.first->dumpToStream(os&: Out);
760 Out << " : ";
761 const auto Pos = Reg.second;
762 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
763 Pos.getContainer()->dumpToStream(os&: Out);
764 Out<<" ; Offset == ";
765 Pos.getOffset()->dumpToStream(os&: Out);
766 }
767 }
768}
769
770namespace {
771
772bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
773 return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
774}
775
776bool isSimpleComparisonOperator(BinaryOperatorKind OK) {
777 return OK == BO_EQ || OK == BO_NE;
778}
779
780ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val) {
781 if (auto Reg = Val.getAsRegion()) {
782 Reg = Reg->getMostDerivedObjectRegion();
783 return State->remove<IteratorRegionMap>(K: Reg);
784 } else if (const auto Sym = Val.getAsSymbol()) {
785 return State->remove<IteratorSymbolMap>(K: Sym);
786 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
787 return State->remove<IteratorRegionMap>(K: LCVal->getRegion());
788 }
789 return nullptr;
790}
791
792ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
793 SymbolRef Sym2, bool Equal) {
794 auto &SVB = State->getStateManager().getSValBuilder();
795
796 // FIXME: This code should be reworked as follows:
797 // 1. Subtract the operands using evalBinOp().
798 // 2. Assume that the result doesn't overflow.
799 // 3. Compare the result to 0.
800 // 4. Assume the result of the comparison.
801 const auto comparison =
802 SVB.evalBinOp(state: State, op: BO_EQ, lhs: nonloc::SymbolVal(Sym1),
803 rhs: nonloc::SymbolVal(Sym2), type: SVB.getConditionType());
804
805 assert(isa<DefinedSVal>(comparison) &&
806 "Symbol comparison must be a `DefinedSVal`");
807
808 auto NewState = State->assume(Cond: comparison.castAs<DefinedSVal>(), Assumption: Equal);
809 if (!NewState)
810 return nullptr;
811
812 if (const auto CompSym = comparison.getAsSymbol()) {
813 assert(isa<SymIntExpr>(CompSym) &&
814 "Symbol comparison must be a `SymIntExpr`");
815 assert(BinaryOperator::isComparisonOp(
816 cast<SymIntExpr>(CompSym)->getOpcode()) &&
817 "Symbol comparison must be a comparison");
818 return assumeNoOverflow(State: NewState, Sym: cast<SymIntExpr>(Val: CompSym)->getLHS(), Scale: 2);
819 }
820
821 return NewState;
822}
823
824bool isBoundThroughLazyCompoundVal(const Environment &Env,
825 const MemRegion *Reg) {
826 for (const auto &Binding : Env) {
827 if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
828 if (LCVal->getRegion() == Reg)
829 return true;
830 }
831 }
832
833 return false;
834}
835
836const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) {
837 while (Node) {
838 ProgramPoint PP = Node->getLocation();
839 if (auto Enter = PP.getAs<CallEnter>()) {
840 if (Enter->getCallExpr() == Call)
841 break;
842 }
843
844 Node = Node->getFirstPred();
845 }
846
847 return Node;
848}
849
850} // namespace
851
852void ento::registerIteratorModeling(CheckerManager &mgr) {
853 mgr.registerChecker<IteratorModeling>();
854}
855
856bool ento::shouldRegisterIteratorModeling(const CheckerManager &mgr) {
857 return true;
858}
859

source code of clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp