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