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