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 checker for using iterators outside their range (past end). Usage
10 // means here dereferencing, incrementing etc.
11 //
12 //===----------------------------------------------------------------------===//
13 //
14 // In the code, iterator can be represented as a:
15 // * type-I: typedef-ed pointer. Operations over such iterator, such as
16 // comparisons or increments, are modeled straightforwardly by the
17 // analyzer.
18 // * type-II: structure with its method bodies available. Operations over such
19 // iterator are inlined by the analyzer, and results of modeling
20 // these operations are exposing implementation details of the
21 // iterators, which is not necessarily helping.
22 // * type-III: completely opaque structure. Operations over such iterator are
23 // modeled conservatively, producing conjured symbols everywhere.
24 //
25 // To handle all these types in a common way we introduce a structure called
26 // IteratorPosition which is an abstraction of the position the iterator
27 // represents using symbolic expressions. The checker handles all the
28 // operations on this structure.
29 //
30 // Additionally, depending on the circumstances, operators of types II and III
31 // can be represented as:
32 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
33 // from conservatively evaluated methods such as
34 // `.begin()`.
35 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
36 // variables or temporaries, when the iterator object is
37 // currently treated as an lvalue.
38 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
39 // iterator object is treated as an rvalue taken of a
40 // particular lvalue, eg. a copy of "type-a" iterator
41 // object, or an iterator that existed before the
42 // analysis has started.
43 //
44 // To handle any of these three different representations stored in an SVal we
45 // use setter and getters functions which separate the three cases. To store
46 // them we use a pointer union of symbol and memory region.
47 //
48 // The checker works the following way: We record the begin and the
49 // past-end iterator for all containers whenever their `.begin()` and `.end()`
50 // are called. Since the Constraint Manager cannot handle such SVals we need
51 // to take over its role. We post-check equality and non-equality comparisons
52 // and record that the two sides are equal if we are in the 'equal' branch
53 // (true-branch for `==` and false-branch for `!=`).
54 //
55 // In case of type-I or type-II iterators we get a concrete integer as a result
56 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
57 // this latter case we record the symbol and reload it in evalAssume() and do
58 // the propagation there. We also handle (maybe double) negated comparisons
59 // which are represented in the form of (x == 0 or x != 0) where x is the
60 // comparison itself.
61 //
62 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
63 // we only use expressions of the format S, S+n or S-n for iterator positions
64 // where S is a conjured symbol and n is an unsigned concrete integer. When
65 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
66 // a constraint which we later retrieve when doing an actual comparison.
67
68 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
69 #include "clang/AST/DeclTemplate.h"
70 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
71 #include "clang/StaticAnalyzer/Core/Checker.h"
72 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
73 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
74 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
75
76 #include "Iterator.h"
77
78 #include <utility>
79
80 using namespace clang;
81 using namespace ento;
82 using namespace iterator;
83
84 namespace {
85
86 class IteratorModeling
87 : public Checker<check::PostCall, check::PostStmt<MaterializeTemporaryExpr>,
88 check::Bind, check::LiveSymbols, check::DeadSymbols> {
89
90 void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal,
91 const SVal &LVal, const SVal &RVal,
92 OverloadedOperatorKind Op) const;
93 void processComparison(CheckerContext &C, ProgramStateRef State,
94 SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
95 OverloadedOperatorKind Op) const;
96 void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
97 bool Postfix) const;
98 void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
99 bool Postfix) const;
100 void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
101 OverloadedOperatorKind Op, const SVal &RetVal,
102 const SVal &LHS, const SVal &RHS) const;
103 void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
104 const SVal &Cont) const;
105 void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
106 const SVal &Cont) const;
107 void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
108 const MemRegion *Cont) const;
109 void handleAssign(CheckerContext &C, const SVal &Cont,
110 const Expr *CE = nullptr,
111 const SVal &OldCont = UndefinedVal()) const;
112 void handleClear(CheckerContext &C, const SVal &Cont) const;
113 void handlePushBack(CheckerContext &C, const SVal &Cont) const;
114 void handlePopBack(CheckerContext &C, const SVal &Cont) const;
115 void handlePushFront(CheckerContext &C, const SVal &Cont) const;
116 void handlePopFront(CheckerContext &C, const SVal &Cont) const;
117 void handleInsert(CheckerContext &C, const SVal &Iter) const;
118 void handleErase(CheckerContext &C, const SVal &Iter) const;
119 void handleErase(CheckerContext &C, const SVal &Iter1,
120 const SVal &Iter2) const;
121 void handleEraseAfter(CheckerContext &C, const SVal &Iter) const;
122 void handleEraseAfter(CheckerContext &C, const SVal &Iter1,
123 const SVal &Iter2) const;
124 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
125 const char *Sep) const override;
126
127 public:
IteratorModeling()128 IteratorModeling() {}
129
130 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
131 void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
132 void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
133 void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
134 void checkPostStmt(const MaterializeTemporaryExpr *MTE,
135 CheckerContext &C) const;
136 void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
137 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
138 };
139
140 bool isBeginCall(const FunctionDecl *Func);
141 bool isEndCall(const FunctionDecl *Func);
142 bool isAssignCall(const FunctionDecl *Func);
143 bool isClearCall(const FunctionDecl *Func);
144 bool isPushBackCall(const FunctionDecl *Func);
145 bool isEmplaceBackCall(const FunctionDecl *Func);
146 bool isPopBackCall(const FunctionDecl *Func);
147 bool isPushFrontCall(const FunctionDecl *Func);
148 bool isEmplaceFrontCall(const FunctionDecl *Func);
149 bool isPopFrontCall(const FunctionDecl *Func);
150 bool isAssignmentOperator(OverloadedOperatorKind OK);
151 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
152 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
153 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
154 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
155 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
156 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
157 ProgramStateRef createContainerBegin(ProgramStateRef State,
158 const MemRegion *Cont, const Expr *E,
159 QualType T, const LocationContext *LCtx,
160 unsigned BlockCount);
161 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
162 const Expr *E, QualType T,
163 const LocationContext *LCtx,
164 unsigned BlockCount);
165 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
166 const ContainerData &CData);
167 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
168 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
169 long Scale);
170 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
171 const MemRegion *Cont);
172 ProgramStateRef
173 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
174 const MemRegion *Cont, SymbolRef Offset,
175 BinaryOperator::Opcode Opc);
176 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
177 SymbolRef Offset,
178 BinaryOperator::Opcode Opc);
179 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
180 SymbolRef Offset1,
181 BinaryOperator::Opcode Opc1,
182 SymbolRef Offset2,
183 BinaryOperator::Opcode Opc2);
184 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
185 const MemRegion *Cont,
186 const MemRegion *NewCont);
187 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
188 const MemRegion *Cont,
189 const MemRegion *NewCont,
190 SymbolRef Offset,
191 BinaryOperator::Opcode Opc);
192 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
193 ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
194 SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
195 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
196 SymbolRef Sym2, bool Equal);
197 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
198 SymbolRef OldSym, SymbolRef NewSym);
199 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
200 bool isBoundThroughLazyCompoundVal(const Environment &Env,
201 const MemRegion *Reg);
202
203 } // namespace
204
checkPostCall(const CallEvent & Call,CheckerContext & C) const205 void IteratorModeling::checkPostCall(const CallEvent &Call,
206 CheckerContext &C) const {
207 // Record new iterator positions and iterator position changes
208 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
209 if (!Func)
210 return;
211
212 if (Func->isOverloadedOperator()) {
213 const auto Op = Func->getOverloadedOperator();
214 if (isAssignmentOperator(Op)) {
215 // Overloaded 'operator=' must be a non-static member function.
216 const auto *InstCall = cast<CXXInstanceCall>(&Call);
217 if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) {
218 handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
219 Call.getArgSVal(0));
220 return;
221 }
222
223 handleAssign(C, InstCall->getCXXThisVal());
224 return;
225 } else if (isSimpleComparisonOperator(Op)) {
226 const auto *OrigExpr = Call.getOriginExpr();
227 if (!OrigExpr)
228 return;
229
230 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
231 handleComparison(C, OrigExpr, Call.getReturnValue(),
232 InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
233 return;
234 }
235
236 handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
237 Call.getArgSVal(1), Op);
238 return;
239 } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
240 const auto *OrigExpr = Call.getOriginExpr();
241 if (!OrigExpr)
242 return;
243
244 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
245 if (Call.getNumArgs() >= 1 &&
246 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
247 handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(),
248 Call.getReturnValue(),
249 InstCall->getCXXThisVal(), Call.getArgSVal(0));
250 return;
251 }
252 } else {
253 if (Call.getNumArgs() >= 2 &&
254 Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
255 handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(),
256 Call.getReturnValue(), Call.getArgSVal(0),
257 Call.getArgSVal(1));
258 return;
259 }
260 }
261 } else if (isIncrementOperator(Func->getOverloadedOperator())) {
262 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
263 handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
264 Call.getNumArgs());
265 return;
266 }
267
268 handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
269 Call.getNumArgs());
270 return;
271 } else if (isDecrementOperator(Func->getOverloadedOperator())) {
272 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
273 handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
274 Call.getNumArgs());
275 return;
276 }
277
278 handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
279 Call.getNumArgs());
280 return;
281 }
282 } else {
283 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
284 if (isAssignCall(Func)) {
285 handleAssign(C, InstCall->getCXXThisVal());
286 return;
287 }
288
289 if (isClearCall(Func)) {
290 handleClear(C, InstCall->getCXXThisVal());
291 return;
292 }
293
294 if (isPushBackCall(Func) || isEmplaceBackCall(Func)) {
295 handlePushBack(C, InstCall->getCXXThisVal());
296 return;
297 }
298
299 if (isPopBackCall(Func)) {
300 handlePopBack(C, InstCall->getCXXThisVal());
301 return;
302 }
303
304 if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) {
305 handlePushFront(C, InstCall->getCXXThisVal());
306 return;
307 }
308
309 if (isPopFrontCall(Func)) {
310 handlePopFront(C, InstCall->getCXXThisVal());
311 return;
312 }
313
314 if (isInsertCall(Func) || isEmplaceCall(Func)) {
315 handleInsert(C, Call.getArgSVal(0));
316 return;
317 }
318
319 if (isEraseCall(Func)) {
320 if (Call.getNumArgs() == 1) {
321 handleErase(C, Call.getArgSVal(0));
322 return;
323 }
324
325 if (Call.getNumArgs() == 2) {
326 handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1));
327 return;
328 }
329 }
330
331 if (isEraseAfterCall(Func)) {
332 if (Call.getNumArgs() == 1) {
333 handleEraseAfter(C, Call.getArgSVal(0));
334 return;
335 }
336
337 if (Call.getNumArgs() == 2) {
338 handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1));
339 return;
340 }
341 }
342 }
343
344 const auto *OrigExpr = Call.getOriginExpr();
345 if (!OrigExpr)
346 return;
347
348 if (!isIteratorType(Call.getResultType()))
349 return;
350
351 auto State = C.getState();
352
353 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
354 if (isBeginCall(Func)) {
355 handleBegin(C, OrigExpr, Call.getReturnValue(),
356 InstCall->getCXXThisVal());
357 return;
358 }
359
360 if (isEndCall(Func)) {
361 handleEnd(C, OrigExpr, Call.getReturnValue(),
362 InstCall->getCXXThisVal());
363 return;
364 }
365 }
366
367 // Already bound to container?
368 if (getIteratorPosition(State, Call.getReturnValue()))
369 return;
370
371 // Copy-like and move constructors
372 if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
373 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
374 State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
375 if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
376 State = removeIteratorPosition(State, Call.getArgSVal(0));
377 }
378 C.addTransition(State);
379 return;
380 }
381 }
382
383 // Assumption: if return value is an iterator which is not yet bound to a
384 // container, then look for the first iterator argument, and
385 // bind the return value to the same container. This approach
386 // works for STL algorithms.
387 // FIXME: Add a more conservative mode
388 for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
389 if (isIteratorType(Call.getArgExpr(i)->getType())) {
390 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
391 assignToContainer(C, OrigExpr, Call.getReturnValue(),
392 Pos->getContainer());
393 return;
394 }
395 }
396 }
397 }
398 }
399
checkBind(SVal Loc,SVal Val,const Stmt * S,CheckerContext & C) const400 void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
401 CheckerContext &C) const {
402 auto State = C.getState();
403 const auto *Pos = getIteratorPosition(State, Val);
404 if (Pos) {
405 State = setIteratorPosition(State, Loc, *Pos);
406 C.addTransition(State);
407 } else {
408 const auto *OldPos = getIteratorPosition(State, Loc);
409 if (OldPos) {
410 State = removeIteratorPosition(State, Loc);
411 C.addTransition(State);
412 }
413 }
414 }
415
checkPostStmt(const MaterializeTemporaryExpr * MTE,CheckerContext & C) const416 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
417 CheckerContext &C) const {
418 /* Transfer iterator state to temporary objects */
419 auto State = C.getState();
420 const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
421 if (!Pos)
422 return;
423 State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
424 C.addTransition(State);
425 }
426
checkLiveSymbols(ProgramStateRef State,SymbolReaper & SR) const427 void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
428 SymbolReaper &SR) const {
429 // Keep symbolic expressions of iterator positions, container begins and ends
430 // alive
431 auto RegionMap = State->get<IteratorRegionMap>();
432 for (const auto &Reg : RegionMap) {
433 const auto Offset = Reg.second.getOffset();
434 for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
435 if (isa<SymbolData>(*i))
436 SR.markLive(*i);
437 }
438
439 auto SymbolMap = State->get<IteratorSymbolMap>();
440 for (const auto &Sym : SymbolMap) {
441 const auto Offset = Sym.second.getOffset();
442 for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
443 if (isa<SymbolData>(*i))
444 SR.markLive(*i);
445 }
446
447 auto ContMap = State->get<ContainerMap>();
448 for (const auto &Cont : ContMap) {
449 const auto CData = Cont.second;
450 if (CData.getBegin()) {
451 SR.markLive(CData.getBegin());
452 if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
453 SR.markLive(SIE->getLHS());
454 }
455 if (CData.getEnd()) {
456 SR.markLive(CData.getEnd());
457 if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
458 SR.markLive(SIE->getLHS());
459 }
460 }
461 }
462
checkDeadSymbols(SymbolReaper & SR,CheckerContext & C) const463 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
464 CheckerContext &C) const {
465 // Cleanup
466 auto State = C.getState();
467
468 auto RegionMap = State->get<IteratorRegionMap>();
469 for (const auto &Reg : RegionMap) {
470 if (!SR.isLiveRegion(Reg.first)) {
471 // The region behind the `LazyCompoundVal` is often cleaned up before
472 // the `LazyCompoundVal` itself. If there are iterator positions keyed
473 // by these regions their cleanup must be deferred.
474 if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
475 State = State->remove<IteratorRegionMap>(Reg.first);
476 }
477 }
478 }
479
480 auto SymbolMap = State->get<IteratorSymbolMap>();
481 for (const auto &Sym : SymbolMap) {
482 if (!SR.isLive(Sym.first)) {
483 State = State->remove<IteratorSymbolMap>(Sym.first);
484 }
485 }
486
487 auto ContMap = State->get<ContainerMap>();
488 for (const auto &Cont : ContMap) {
489 if (!SR.isLiveRegion(Cont.first)) {
490 // We must keep the container data while it has live iterators to be able
491 // to compare them to the begin and the end of the container.
492 if (!hasLiveIterators(State, Cont.first)) {
493 State = State->remove<ContainerMap>(Cont.first);
494 }
495 }
496 }
497
498 C.addTransition(State);
499 }
500
handleComparison(CheckerContext & C,const Expr * CE,SVal RetVal,const SVal & LVal,const SVal & RVal,OverloadedOperatorKind Op) const501 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
502 SVal RetVal, const SVal &LVal,
503 const SVal &RVal,
504 OverloadedOperatorKind Op) const {
505 // Record the operands and the operator of the comparison for the next
506 // evalAssume, if the result is a symbolic expression. If it is a concrete
507 // value (only one branch is possible), then transfer the state between
508 // the operands according to the operator and the result
509 auto State = C.getState();
510 const auto *LPos = getIteratorPosition(State, LVal);
511 const auto *RPos = getIteratorPosition(State, RVal);
512 const MemRegion *Cont = nullptr;
513 if (LPos) {
514 Cont = LPos->getContainer();
515 } else if (RPos) {
516 Cont = RPos->getContainer();
517 }
518 if (!Cont)
519 return;
520
521 // At least one of the iterators have recorded positions. If one of them has
522 // not then create a new symbol for the offset.
523 SymbolRef Sym;
524 if (!LPos || !RPos) {
525 auto &SymMgr = C.getSymbolManager();
526 Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
527 C.getASTContext().LongTy, C.blockCount());
528 State = assumeNoOverflow(State, Sym, 4);
529 }
530
531 if (!LPos) {
532 State = setIteratorPosition(State, LVal,
533 IteratorPosition::getPosition(Cont, Sym));
534 LPos = getIteratorPosition(State, LVal);
535 } else if (!RPos) {
536 State = setIteratorPosition(State, RVal,
537 IteratorPosition::getPosition(Cont, Sym));
538 RPos = getIteratorPosition(State, RVal);
539 }
540
541 // We cannot make assumpotions on `UnknownVal`. Let us conjure a symbol
542 // instead.
543 if (RetVal.isUnknown()) {
544 auto &SymMgr = C.getSymbolManager();
545 auto *LCtx = C.getLocationContext();
546 RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
547 CE, LCtx, C.getASTContext().BoolTy, C.blockCount()));
548 State = State->BindExpr(CE, LCtx, RetVal);
549 }
550
551 processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
552 }
553
processComparison(CheckerContext & C,ProgramStateRef State,SymbolRef Sym1,SymbolRef Sym2,const SVal & RetVal,OverloadedOperatorKind Op) const554 void IteratorModeling::processComparison(CheckerContext &C,
555 ProgramStateRef State, SymbolRef Sym1,
556 SymbolRef Sym2, const SVal &RetVal,
557 OverloadedOperatorKind Op) const {
558 if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
559 if ((State = relateSymbols(State, Sym1, Sym2,
560 (Op == OO_EqualEqual) ==
561 (TruthVal->getValue() != 0)))) {
562 C.addTransition(State);
563 } else {
564 C.generateSink(State, C.getPredecessor());
565 }
566 return;
567 }
568
569 const auto ConditionVal = RetVal.getAs<DefinedSVal>();
570 if (!ConditionVal)
571 return;
572
573 if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
574 StateTrue = StateTrue->assume(*ConditionVal, true);
575 C.addTransition(StateTrue);
576 }
577
578 if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
579 StateFalse = StateFalse->assume(*ConditionVal, false);
580 C.addTransition(StateFalse);
581 }
582 }
583
handleIncrement(CheckerContext & C,const SVal & RetVal,const SVal & Iter,bool Postfix) const584 void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal,
585 const SVal &Iter, bool Postfix) const {
586 // Increment the symbolic expressions which represents the position of the
587 // iterator
588 auto State = C.getState();
589 auto &BVF = C.getSymbolManager().getBasicVals();
590
591 const auto *Pos = getIteratorPosition(State, Iter);
592 if (!Pos)
593 return;
594
595 auto NewState =
596 advancePosition(State, Iter, OO_Plus,
597 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
598 assert(NewState &&
599 "Advancing position by concrete int should always be successful");
600
601 const auto *NewPos = getIteratorPosition(NewState, Iter);
602 assert(NewPos &&
603 "Iterator should have position after successful advancement");
604
605 State = setIteratorPosition(State, Iter, *NewPos);
606 State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
607 C.addTransition(State);
608 }
609
handleDecrement(CheckerContext & C,const SVal & RetVal,const SVal & Iter,bool Postfix) const610 void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal,
611 const SVal &Iter, bool Postfix) const {
612 // Decrement the symbolic expressions which represents the position of the
613 // iterator
614 auto State = C.getState();
615 auto &BVF = C.getSymbolManager().getBasicVals();
616
617 const auto *Pos = getIteratorPosition(State, Iter);
618 if (!Pos)
619 return;
620
621 auto NewState =
622 advancePosition(State, Iter, OO_Minus,
623 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
624 assert(NewState &&
625 "Advancing position by concrete int should always be successful");
626
627 const auto *NewPos = getIteratorPosition(NewState, Iter);
628 assert(NewPos &&
629 "Iterator should have position after successful advancement");
630
631 State = setIteratorPosition(State, Iter, *NewPos);
632 State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
633 C.addTransition(State);
634 }
635
handleRandomIncrOrDecr(CheckerContext & C,const Expr * CE,OverloadedOperatorKind Op,const SVal & RetVal,const SVal & LHS,const SVal & RHS) const636 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C,
637 const Expr *CE,
638 OverloadedOperatorKind Op,
639 const SVal &RetVal,
640 const SVal &LHS,
641 const SVal &RHS) const {
642 // Increment or decrement the symbolic expressions which represents the
643 // position of the iterator
644 auto State = C.getState();
645
646 const auto *Pos = getIteratorPosition(State, LHS);
647 if (!Pos)
648 return;
649
650 const auto *value = &RHS;
651 if (auto loc = RHS.getAs<Loc>()) {
652 const auto val = State->getRawSVal(*loc);
653 value = &val;
654 }
655
656 auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
657
658 auto NewState =
659 advancePosition(State, LHS, Op, *value);
660 if (NewState) {
661 const auto *NewPos = getIteratorPosition(NewState, LHS);
662 assert(NewPos &&
663 "Iterator should have position after successful advancement");
664
665 State = setIteratorPosition(NewState, TgtVal, *NewPos);
666 C.addTransition(State);
667 } else {
668 assignToContainer(C, CE, TgtVal, Pos->getContainer());
669 }
670 }
671
handleBegin(CheckerContext & C,const Expr * CE,const SVal & RetVal,const SVal & Cont) const672 void IteratorModeling::handleBegin(CheckerContext &C, const Expr *CE,
673 const SVal &RetVal, const SVal &Cont) const {
674 const auto *ContReg = Cont.getAsRegion();
675 if (!ContReg)
676 return;
677
678 ContReg = ContReg->getMostDerivedObjectRegion();
679
680 // If the container already has a begin symbol then use it. Otherwise first
681 // create a new one.
682 auto State = C.getState();
683 auto BeginSym = getContainerBegin(State, ContReg);
684 if (!BeginSym) {
685 State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
686 C.getLocationContext(), C.blockCount());
687 BeginSym = getContainerBegin(State, ContReg);
688 }
689 State = setIteratorPosition(State, RetVal,
690 IteratorPosition::getPosition(ContReg, BeginSym));
691 C.addTransition(State);
692 }
693
handleEnd(CheckerContext & C,const Expr * CE,const SVal & RetVal,const SVal & Cont) const694 void IteratorModeling::handleEnd(CheckerContext &C, const Expr *CE,
695 const SVal &RetVal, const SVal &Cont) const {
696 const auto *ContReg = Cont.getAsRegion();
697 if (!ContReg)
698 return;
699
700 ContReg = ContReg->getMostDerivedObjectRegion();
701
702 // If the container already has an end symbol then use it. Otherwise first
703 // create a new one.
704 auto State = C.getState();
705 auto EndSym = getContainerEnd(State, ContReg);
706 if (!EndSym) {
707 State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
708 C.getLocationContext(), C.blockCount());
709 EndSym = getContainerEnd(State, ContReg);
710 }
711 State = setIteratorPosition(State, RetVal,
712 IteratorPosition::getPosition(ContReg, EndSym));
713 C.addTransition(State);
714 }
715
assignToContainer(CheckerContext & C,const Expr * CE,const SVal & RetVal,const MemRegion * Cont) const716 void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
717 const SVal &RetVal,
718 const MemRegion *Cont) const {
719 Cont = Cont->getMostDerivedObjectRegion();
720
721 auto State = C.getState();
722 auto &SymMgr = C.getSymbolManager();
723 auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
724 C.getASTContext().LongTy, C.blockCount());
725 State = assumeNoOverflow(State, Sym, 4);
726 State = setIteratorPosition(State, RetVal,
727 IteratorPosition::getPosition(Cont, Sym));
728 C.addTransition(State);
729 }
730
handleAssign(CheckerContext & C,const SVal & Cont,const Expr * CE,const SVal & OldCont) const731 void IteratorModeling::handleAssign(CheckerContext &C, const SVal &Cont,
732 const Expr *CE, const SVal &OldCont) const {
733 const auto *ContReg = Cont.getAsRegion();
734 if (!ContReg)
735 return;
736
737 ContReg = ContReg->getMostDerivedObjectRegion();
738
739 // Assignment of a new value to a container always invalidates all its
740 // iterators
741 auto State = C.getState();
742 const auto CData = getContainerData(State, ContReg);
743 if (CData) {
744 State = invalidateAllIteratorPositions(State, ContReg);
745 }
746
747 // In case of move, iterators of the old container (except the past-end
748 // iterators) remain valid but refer to the new container
749 if (!OldCont.isUndef()) {
750 const auto *OldContReg = OldCont.getAsRegion();
751 if (OldContReg) {
752 OldContReg = OldContReg->getMostDerivedObjectRegion();
753 const auto OldCData = getContainerData(State, OldContReg);
754 if (OldCData) {
755 if (const auto OldEndSym = OldCData->getEnd()) {
756 // If we already assigned an "end" symbol to the old container, then
757 // first reassign all iterator positions to the new container which
758 // are not past the container (thus not greater or equal to the
759 // current "end" symbol).
760 State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
761 OldEndSym, BO_GE);
762 auto &SymMgr = C.getSymbolManager();
763 auto &SVB = C.getSValBuilder();
764 // Then generate and assign a new "end" symbol for the new container.
765 auto NewEndSym =
766 SymMgr.conjureSymbol(CE, C.getLocationContext(),
767 C.getASTContext().LongTy, C.blockCount());
768 State = assumeNoOverflow(State, NewEndSym, 4);
769 if (CData) {
770 State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
771 } else {
772 State = setContainerData(State, ContReg,
773 ContainerData::fromEnd(NewEndSym));
774 }
775 // Finally, replace the old "end" symbol in the already reassigned
776 // iterator positions with the new "end" symbol.
777 State = rebaseSymbolInIteratorPositionsIf(
778 State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
779 } else {
780 // There was no "end" symbol assigned yet to the old container,
781 // so reassign all iterator positions to the new container.
782 State = reassignAllIteratorPositions(State, OldContReg, ContReg);
783 }
784 if (const auto OldBeginSym = OldCData->getBegin()) {
785 // If we already assigned a "begin" symbol to the old container, then
786 // assign it to the new container and remove it from the old one.
787 if (CData) {
788 State =
789 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
790 } else {
791 State = setContainerData(State, ContReg,
792 ContainerData::fromBegin(OldBeginSym));
793 }
794 State =
795 setContainerData(State, OldContReg, OldCData->newEnd(nullptr));
796 }
797 } else {
798 // There was neither "begin" nor "end" symbol assigned yet to the old
799 // container, so reassign all iterator positions to the new container.
800 State = reassignAllIteratorPositions(State, OldContReg, ContReg);
801 }
802 }
803 }
804 C.addTransition(State);
805 }
806
handleClear(CheckerContext & C,const SVal & Cont) const807 void IteratorModeling::handleClear(CheckerContext &C, const SVal &Cont) const {
808 const auto *ContReg = Cont.getAsRegion();
809 if (!ContReg)
810 return;
811
812 ContReg = ContReg->getMostDerivedObjectRegion();
813
814 // The clear() operation invalidates all the iterators, except the past-end
815 // iterators of list-like containers
816 auto State = C.getState();
817 if (!hasSubscriptOperator(State, ContReg) ||
818 !backModifiable(State, ContReg)) {
819 const auto CData = getContainerData(State, ContReg);
820 if (CData) {
821 if (const auto EndSym = CData->getEnd()) {
822 State =
823 invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
824 C.addTransition(State);
825 return;
826 }
827 }
828 }
829 State = invalidateAllIteratorPositions(State, ContReg);
830 C.addTransition(State);
831 }
832
handlePushBack(CheckerContext & C,const SVal & Cont) const833 void IteratorModeling::handlePushBack(CheckerContext &C,
834 const SVal &Cont) const {
835 const auto *ContReg = Cont.getAsRegion();
836 if (!ContReg)
837 return;
838
839 ContReg = ContReg->getMostDerivedObjectRegion();
840
841 // For deque-like containers invalidate all iterator positions
842 auto State = C.getState();
843 if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
844 State = invalidateAllIteratorPositions(State, ContReg);
845 C.addTransition(State);
846 return;
847 }
848
849 const auto CData = getContainerData(State, ContReg);
850 if (!CData)
851 return;
852
853 // For vector-like containers invalidate the past-end iterator positions
854 if (const auto EndSym = CData->getEnd()) {
855 if (hasSubscriptOperator(State, ContReg)) {
856 State = invalidateIteratorPositions(State, EndSym, BO_GE);
857 }
858 auto &SymMgr = C.getSymbolManager();
859 auto &BVF = SymMgr.getBasicVals();
860 auto &SVB = C.getSValBuilder();
861 const auto newEndSym =
862 SVB.evalBinOp(State, BO_Add,
863 nonloc::SymbolVal(EndSym),
864 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
865 SymMgr.getType(EndSym)).getAsSymbol();
866 State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
867 }
868 C.addTransition(State);
869 }
870
handlePopBack(CheckerContext & C,const SVal & Cont) const871 void IteratorModeling::handlePopBack(CheckerContext &C,
872 const SVal &Cont) const {
873 const auto *ContReg = Cont.getAsRegion();
874 if (!ContReg)
875 return;
876
877 ContReg = ContReg->getMostDerivedObjectRegion();
878
879 auto State = C.getState();
880 const auto CData = getContainerData(State, ContReg);
881 if (!CData)
882 return;
883
884 if (const auto EndSym = CData->getEnd()) {
885 auto &SymMgr = C.getSymbolManager();
886 auto &BVF = SymMgr.getBasicVals();
887 auto &SVB = C.getSValBuilder();
888 const auto BackSym =
889 SVB.evalBinOp(State, BO_Sub,
890 nonloc::SymbolVal(EndSym),
891 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
892 SymMgr.getType(EndSym)).getAsSymbol();
893 // For vector-like and deque-like containers invalidate the last and the
894 // past-end iterator positions. For list-like containers only invalidate
895 // the last position
896 if (hasSubscriptOperator(State, ContReg) &&
897 backModifiable(State, ContReg)) {
898 State = invalidateIteratorPositions(State, BackSym, BO_GE);
899 State = setContainerData(State, ContReg, CData->newEnd(nullptr));
900 } else {
901 State = invalidateIteratorPositions(State, BackSym, BO_EQ);
902 }
903 auto newEndSym = BackSym;
904 State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
905 C.addTransition(State);
906 }
907 }
908
handlePushFront(CheckerContext & C,const SVal & Cont) const909 void IteratorModeling::handlePushFront(CheckerContext &C,
910 const SVal &Cont) const {
911 const auto *ContReg = Cont.getAsRegion();
912 if (!ContReg)
913 return;
914
915 ContReg = ContReg->getMostDerivedObjectRegion();
916
917 // For deque-like containers invalidate all iterator positions
918 auto State = C.getState();
919 if (hasSubscriptOperator(State, ContReg)) {
920 State = invalidateAllIteratorPositions(State, ContReg);
921 C.addTransition(State);
922 } else {
923 const auto CData = getContainerData(State, ContReg);
924 if (!CData)
925 return;
926
927 if (const auto BeginSym = CData->getBegin()) {
928 auto &SymMgr = C.getSymbolManager();
929 auto &BVF = SymMgr.getBasicVals();
930 auto &SVB = C.getSValBuilder();
931 const auto newBeginSym =
932 SVB.evalBinOp(State, BO_Sub,
933 nonloc::SymbolVal(BeginSym),
934 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
935 SymMgr.getType(BeginSym)).getAsSymbol();
936 State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
937 C.addTransition(State);
938 }
939 }
940 }
941
handlePopFront(CheckerContext & C,const SVal & Cont) const942 void IteratorModeling::handlePopFront(CheckerContext &C,
943 const SVal &Cont) const {
944 const auto *ContReg = Cont.getAsRegion();
945 if (!ContReg)
946 return;
947
948 ContReg = ContReg->getMostDerivedObjectRegion();
949
950 auto State = C.getState();
951 const auto CData = getContainerData(State, ContReg);
952 if (!CData)
953 return;
954
955 // For deque-like containers invalidate all iterator positions. For list-like
956 // iterators only invalidate the first position
957 if (const auto BeginSym = CData->getBegin()) {
958 if (hasSubscriptOperator(State, ContReg)) {
959 State = invalidateIteratorPositions(State, BeginSym, BO_LE);
960 } else {
961 State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
962 }
963 auto &SymMgr = C.getSymbolManager();
964 auto &BVF = SymMgr.getBasicVals();
965 auto &SVB = C.getSValBuilder();
966 const auto newBeginSym =
967 SVB.evalBinOp(State, BO_Add,
968 nonloc::SymbolVal(BeginSym),
969 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
970 SymMgr.getType(BeginSym)).getAsSymbol();
971 State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
972 C.addTransition(State);
973 }
974 }
975
handleInsert(CheckerContext & C,const SVal & Iter) const976 void IteratorModeling::handleInsert(CheckerContext &C, const SVal &Iter) const {
977 auto State = C.getState();
978 const auto *Pos = getIteratorPosition(State, Iter);
979 if (!Pos)
980 return;
981
982 // For deque-like containers invalidate all iterator positions. For
983 // vector-like containers invalidate iterator positions after the insertion.
984 const auto *Cont = Pos->getContainer();
985 if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
986 if (frontModifiable(State, Cont)) {
987 State = invalidateAllIteratorPositions(State, Cont);
988 } else {
989 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
990 }
991 if (const auto *CData = getContainerData(State, Cont)) {
992 if (const auto EndSym = CData->getEnd()) {
993 State = invalidateIteratorPositions(State, EndSym, BO_GE);
994 State = setContainerData(State, Cont, CData->newEnd(nullptr));
995 }
996 }
997 C.addTransition(State);
998 }
999 }
1000
handleErase(CheckerContext & C,const SVal & Iter) const1001 void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter) const {
1002 auto State = C.getState();
1003 const auto *Pos = getIteratorPosition(State, Iter);
1004 if (!Pos)
1005 return;
1006
1007 // For deque-like containers invalidate all iterator positions. For
1008 // vector-like containers invalidate iterator positions at and after the
1009 // deletion. For list-like containers only invalidate the deleted position.
1010 const auto *Cont = Pos->getContainer();
1011 if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1012 if (frontModifiable(State, Cont)) {
1013 State = invalidateAllIteratorPositions(State, Cont);
1014 } else {
1015 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1016 }
1017 if (const auto *CData = getContainerData(State, Cont)) {
1018 if (const auto EndSym = CData->getEnd()) {
1019 State = invalidateIteratorPositions(State, EndSym, BO_GE);
1020 State = setContainerData(State, Cont, CData->newEnd(nullptr));
1021 }
1022 }
1023 } else {
1024 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
1025 }
1026 C.addTransition(State);
1027 }
1028
handleErase(CheckerContext & C,const SVal & Iter1,const SVal & Iter2) const1029 void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter1,
1030 const SVal &Iter2) const {
1031 auto State = C.getState();
1032 const auto *Pos1 = getIteratorPosition(State, Iter1);
1033 const auto *Pos2 = getIteratorPosition(State, Iter2);
1034 if (!Pos1 || !Pos2)
1035 return;
1036
1037 // For deque-like containers invalidate all iterator positions. For
1038 // vector-like containers invalidate iterator positions at and after the
1039 // deletion range. For list-like containers only invalidate the deleted
1040 // position range [first..last].
1041 const auto *Cont = Pos1->getContainer();
1042 if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1043 if (frontModifiable(State, Cont)) {
1044 State = invalidateAllIteratorPositions(State, Cont);
1045 } else {
1046 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
1047 }
1048 if (const auto *CData = getContainerData(State, Cont)) {
1049 if (const auto EndSym = CData->getEnd()) {
1050 State = invalidateIteratorPositions(State, EndSym, BO_GE);
1051 State = setContainerData(State, Cont, CData->newEnd(nullptr));
1052 }
1053 }
1054 } else {
1055 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
1056 Pos2->getOffset(), BO_LT);
1057 }
1058 C.addTransition(State);
1059 }
1060
handleEraseAfter(CheckerContext & C,const SVal & Iter) const1061 void IteratorModeling::handleEraseAfter(CheckerContext &C,
1062 const SVal &Iter) const {
1063 auto State = C.getState();
1064 const auto *Pos = getIteratorPosition(State, Iter);
1065 if (!Pos)
1066 return;
1067
1068 // Invalidate the deleted iterator position, which is the position of the
1069 // parameter plus one.
1070 auto &SymMgr = C.getSymbolManager();
1071 auto &BVF = SymMgr.getBasicVals();
1072 auto &SVB = C.getSValBuilder();
1073 const auto NextSym =
1074 SVB.evalBinOp(State, BO_Add,
1075 nonloc::SymbolVal(Pos->getOffset()),
1076 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1077 SymMgr.getType(Pos->getOffset())).getAsSymbol();
1078 State = invalidateIteratorPositions(State, NextSym, BO_EQ);
1079 C.addTransition(State);
1080 }
1081
handleEraseAfter(CheckerContext & C,const SVal & Iter1,const SVal & Iter2) const1082 void IteratorModeling::handleEraseAfter(CheckerContext &C, const SVal &Iter1,
1083 const SVal &Iter2) const {
1084 auto State = C.getState();
1085 const auto *Pos1 = getIteratorPosition(State, Iter1);
1086 const auto *Pos2 = getIteratorPosition(State, Iter2);
1087 if (!Pos1 || !Pos2)
1088 return;
1089
1090 // Invalidate the deleted iterator position range (first..last)
1091 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
1092 Pos2->getOffset(), BO_LT);
1093 C.addTransition(State);
1094 }
1095
printState(raw_ostream & Out,ProgramStateRef State,const char * NL,const char * Sep) const1096 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
1097 const char *NL, const char *Sep) const {
1098
1099 auto ContMap = State->get<ContainerMap>();
1100
1101 if (!ContMap.isEmpty()) {
1102 Out << Sep << "Container Data :" << NL;
1103 for (const auto &Cont : ContMap) {
1104 Cont.first->dumpToStream(Out);
1105 Out << " : [ ";
1106 const auto CData = Cont.second;
1107 if (CData.getBegin())
1108 CData.getBegin()->dumpToStream(Out);
1109 else
1110 Out << "<Unknown>";
1111 Out << " .. ";
1112 if (CData.getEnd())
1113 CData.getEnd()->dumpToStream(Out);
1114 else
1115 Out << "<Unknown>";
1116 Out << " ]" << NL;
1117 }
1118 }
1119
1120 auto SymbolMap = State->get<IteratorSymbolMap>();
1121 auto RegionMap = State->get<IteratorRegionMap>();
1122
1123 if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
1124 Out << Sep << "Iterator Positions :" << NL;
1125 for (const auto &Sym : SymbolMap) {
1126 Sym.first->dumpToStream(Out);
1127 Out << " : ";
1128 const auto Pos = Sym.second;
1129 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
1130 Pos.getContainer()->dumpToStream(Out);
1131 Out<<" ; Offset == ";
1132 Pos.getOffset()->dumpToStream(Out);
1133 }
1134
1135 for (const auto &Reg : RegionMap) {
1136 Reg.first->dumpToStream(Out);
1137 Out << " : ";
1138 const auto Pos = Reg.second;
1139 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
1140 Pos.getContainer()->dumpToStream(Out);
1141 Out<<" ; Offset == ";
1142 Pos.getOffset()->dumpToStream(Out);
1143 }
1144 }
1145 }
1146
1147
1148 namespace {
1149
1150 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1151 const MemRegion *Reg);
1152
isBeginCall(const FunctionDecl * Func)1153 bool isBeginCall(const FunctionDecl *Func) {
1154 const auto *IdInfo = Func->getIdentifier();
1155 if (!IdInfo)
1156 return false;
1157 return IdInfo->getName().endswith_lower("begin");
1158 }
1159
isEndCall(const FunctionDecl * Func)1160 bool isEndCall(const FunctionDecl *Func) {
1161 const auto *IdInfo = Func->getIdentifier();
1162 if (!IdInfo)
1163 return false;
1164 return IdInfo->getName().endswith_lower("end");
1165 }
1166
isAssignCall(const FunctionDecl * Func)1167 bool isAssignCall(const FunctionDecl *Func) {
1168 const auto *IdInfo = Func->getIdentifier();
1169 if (!IdInfo)
1170 return false;
1171 if (Func->getNumParams() > 2)
1172 return false;
1173 return IdInfo->getName() == "assign";
1174 }
1175
isClearCall(const FunctionDecl * Func)1176 bool isClearCall(const FunctionDecl *Func) {
1177 const auto *IdInfo = Func->getIdentifier();
1178 if (!IdInfo)
1179 return false;
1180 if (Func->getNumParams() > 0)
1181 return false;
1182 return IdInfo->getName() == "clear";
1183 }
1184
isPushBackCall(const FunctionDecl * Func)1185 bool isPushBackCall(const FunctionDecl *Func) {
1186 const auto *IdInfo = Func->getIdentifier();
1187 if (!IdInfo)
1188 return false;
1189 if (Func->getNumParams() != 1)
1190 return false;
1191 return IdInfo->getName() == "push_back";
1192 }
1193
isEmplaceBackCall(const FunctionDecl * Func)1194 bool isEmplaceBackCall(const FunctionDecl *Func) {
1195 const auto *IdInfo = Func->getIdentifier();
1196 if (!IdInfo)
1197 return false;
1198 if (Func->getNumParams() < 1)
1199 return false;
1200 return IdInfo->getName() == "emplace_back";
1201 }
1202
isPopBackCall(const FunctionDecl * Func)1203 bool isPopBackCall(const FunctionDecl *Func) {
1204 const auto *IdInfo = Func->getIdentifier();
1205 if (!IdInfo)
1206 return false;
1207 if (Func->getNumParams() > 0)
1208 return false;
1209 return IdInfo->getName() == "pop_back";
1210 }
1211
isPushFrontCall(const FunctionDecl * Func)1212 bool isPushFrontCall(const FunctionDecl *Func) {
1213 const auto *IdInfo = Func->getIdentifier();
1214 if (!IdInfo)
1215 return false;
1216 if (Func->getNumParams() != 1)
1217 return false;
1218 return IdInfo->getName() == "push_front";
1219 }
1220
isEmplaceFrontCall(const FunctionDecl * Func)1221 bool isEmplaceFrontCall(const FunctionDecl *Func) {
1222 const auto *IdInfo = Func->getIdentifier();
1223 if (!IdInfo)
1224 return false;
1225 if (Func->getNumParams() < 1)
1226 return false;
1227 return IdInfo->getName() == "emplace_front";
1228 }
1229
isPopFrontCall(const FunctionDecl * Func)1230 bool isPopFrontCall(const FunctionDecl *Func) {
1231 const auto *IdInfo = Func->getIdentifier();
1232 if (!IdInfo)
1233 return false;
1234 if (Func->getNumParams() > 0)
1235 return false;
1236 return IdInfo->getName() == "pop_front";
1237 }
1238
isAssignmentOperator(OverloadedOperatorKind OK)1239 bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
1240
isSimpleComparisonOperator(OverloadedOperatorKind OK)1241 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
1242 return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
1243 }
1244
hasSubscriptOperator(ProgramStateRef State,const MemRegion * Reg)1245 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
1246 const auto *CRD = getCXXRecordDecl(State, Reg);
1247 if (!CRD)
1248 return false;
1249
1250 for (const auto *Method : CRD->methods()) {
1251 if (!Method->isOverloadedOperator())
1252 continue;
1253 const auto OPK = Method->getOverloadedOperator();
1254 if (OPK == OO_Subscript) {
1255 return true;
1256 }
1257 }
1258 return false;
1259 }
1260
frontModifiable(ProgramStateRef State,const MemRegion * Reg)1261 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
1262 const auto *CRD = getCXXRecordDecl(State, Reg);
1263 if (!CRD)
1264 return false;
1265
1266 for (const auto *Method : CRD->methods()) {
1267 if (!Method->getDeclName().isIdentifier())
1268 continue;
1269 if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
1270 return true;
1271 }
1272 }
1273 return false;
1274 }
1275
backModifiable(ProgramStateRef State,const MemRegion * Reg)1276 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
1277 const auto *CRD = getCXXRecordDecl(State, Reg);
1278 if (!CRD)
1279 return false;
1280
1281 for (const auto *Method : CRD->methods()) {
1282 if (!Method->getDeclName().isIdentifier())
1283 continue;
1284 if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
1285 return true;
1286 }
1287 }
1288 return false;
1289 }
1290
getCXXRecordDecl(ProgramStateRef State,const MemRegion * Reg)1291 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1292 const MemRegion *Reg) {
1293 auto TI = getDynamicTypeInfo(State, Reg);
1294 if (!TI.isValid())
1295 return nullptr;
1296
1297 auto Type = TI.getType();
1298 if (const auto *RefT = Type->getAs<ReferenceType>()) {
1299 Type = RefT->getPointeeType();
1300 }
1301
1302 return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
1303 }
1304
getContainerBegin(ProgramStateRef State,const MemRegion * Cont)1305 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
1306 const auto *CDataPtr = getContainerData(State, Cont);
1307 if (!CDataPtr)
1308 return nullptr;
1309
1310 return CDataPtr->getBegin();
1311 }
1312
getContainerEnd(ProgramStateRef State,const MemRegion * Cont)1313 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
1314 const auto *CDataPtr = getContainerData(State, Cont);
1315 if (!CDataPtr)
1316 return nullptr;
1317
1318 return CDataPtr->getEnd();
1319 }
1320
createContainerBegin(ProgramStateRef State,const MemRegion * Cont,const Expr * E,QualType T,const LocationContext * LCtx,unsigned BlockCount)1321 ProgramStateRef createContainerBegin(ProgramStateRef State,
1322 const MemRegion *Cont, const Expr *E,
1323 QualType T, const LocationContext *LCtx,
1324 unsigned BlockCount) {
1325 // Only create if it does not exist
1326 const auto *CDataPtr = getContainerData(State, Cont);
1327 if (CDataPtr && CDataPtr->getBegin())
1328 return State;
1329
1330 auto &SymMgr = State->getSymbolManager();
1331 const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
1332 "begin");
1333 State = assumeNoOverflow(State, Sym, 4);
1334
1335 if (CDataPtr) {
1336 const auto CData = CDataPtr->newBegin(Sym);
1337 return setContainerData(State, Cont, CData);
1338 }
1339
1340 const auto CData = ContainerData::fromBegin(Sym);
1341 return setContainerData(State, Cont, CData);
1342 }
1343
createContainerEnd(ProgramStateRef State,const MemRegion * Cont,const Expr * E,QualType T,const LocationContext * LCtx,unsigned BlockCount)1344 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
1345 const Expr *E, QualType T,
1346 const LocationContext *LCtx,
1347 unsigned BlockCount) {
1348 // Only create if it does not exist
1349 const auto *CDataPtr = getContainerData(State, Cont);
1350 if (CDataPtr && CDataPtr->getEnd())
1351 return State;
1352
1353 auto &SymMgr = State->getSymbolManager();
1354 const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
1355 "end");
1356 State = assumeNoOverflow(State, Sym, 4);
1357
1358 if (CDataPtr) {
1359 const auto CData = CDataPtr->newEnd(Sym);
1360 return setContainerData(State, Cont, CData);
1361 }
1362
1363 const auto CData = ContainerData::fromEnd(Sym);
1364 return setContainerData(State, Cont, CData);
1365 }
1366
setContainerData(ProgramStateRef State,const MemRegion * Cont,const ContainerData & CData)1367 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
1368 const ContainerData &CData) {
1369 return State->set<ContainerMap>(Cont, CData);
1370 }
1371
removeIteratorPosition(ProgramStateRef State,const SVal & Val)1372 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
1373 if (auto Reg = Val.getAsRegion()) {
1374 Reg = Reg->getMostDerivedObjectRegion();
1375 return State->remove<IteratorRegionMap>(Reg);
1376 } else if (const auto Sym = Val.getAsSymbol()) {
1377 return State->remove<IteratorSymbolMap>(Sym);
1378 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1379 return State->remove<IteratorRegionMap>(LCVal->getRegion());
1380 }
1381 return nullptr;
1382 }
1383
1384 // This function tells the analyzer's engine that symbols produced by our
1385 // checker, most notably iterator positions, are relatively small.
1386 // A distance between items in the container should not be very large.
1387 // By assuming that it is within around 1/8 of the address space,
1388 // we can help the analyzer perform operations on these symbols
1389 // without being afraid of integer overflows.
1390 // FIXME: Should we provide it as an API, so that all checkers could use it?
assumeNoOverflow(ProgramStateRef State,SymbolRef Sym,long Scale)1391 ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
1392 long Scale) {
1393 SValBuilder &SVB = State->getStateManager().getSValBuilder();
1394 BasicValueFactory &BV = SVB.getBasicValueFactory();
1395
1396 QualType T = Sym->getType();
1397 assert(T->isSignedIntegerOrEnumerationType());
1398 APSIntType AT = BV.getAPSIntType(T);
1399
1400 ProgramStateRef NewState = State;
1401
1402 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
1403 SVal IsCappedFromAbove =
1404 SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
1405 nonloc::ConcreteInt(Max), SVB.getConditionType());
1406 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
1407 NewState = NewState->assume(*DV, true);
1408 if (!NewState)
1409 return State;
1410 }
1411
1412 llvm::APSInt Min = -Max;
1413 SVal IsCappedFromBelow =
1414 SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
1415 nonloc::ConcreteInt(Min), SVB.getConditionType());
1416 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
1417 NewState = NewState->assume(*DV, true);
1418 if (!NewState)
1419 return State;
1420 }
1421
1422 return NewState;
1423 }
1424
relateSymbols(ProgramStateRef State,SymbolRef Sym1,SymbolRef Sym2,bool Equal)1425 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
1426 SymbolRef Sym2, bool Equal) {
1427 auto &SVB = State->getStateManager().getSValBuilder();
1428
1429 // FIXME: This code should be reworked as follows:
1430 // 1. Subtract the operands using evalBinOp().
1431 // 2. Assume that the result doesn't overflow.
1432 // 3. Compare the result to 0.
1433 // 4. Assume the result of the comparison.
1434 const auto comparison =
1435 SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
1436 nonloc::SymbolVal(Sym2), SVB.getConditionType());
1437
1438 assert(comparison.getAs<DefinedSVal>() &&
1439 "Symbol comparison must be a `DefinedSVal`");
1440
1441 auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
1442 if (!NewState)
1443 return nullptr;
1444
1445 if (const auto CompSym = comparison.getAsSymbol()) {
1446 assert(isa<SymIntExpr>(CompSym) &&
1447 "Symbol comparison must be a `SymIntExpr`");
1448 assert(BinaryOperator::isComparisonOp(
1449 cast<SymIntExpr>(CompSym)->getOpcode()) &&
1450 "Symbol comparison must be a comparison");
1451 return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
1452 }
1453
1454 return NewState;
1455 }
1456
hasLiveIterators(ProgramStateRef State,const MemRegion * Cont)1457 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
1458 auto RegionMap = State->get<IteratorRegionMap>();
1459 for (const auto &Reg : RegionMap) {
1460 if (Reg.second.getContainer() == Cont)
1461 return true;
1462 }
1463
1464 auto SymbolMap = State->get<IteratorSymbolMap>();
1465 for (const auto &Sym : SymbolMap) {
1466 if (Sym.second.getContainer() == Cont)
1467 return true;
1468 }
1469
1470 return false;
1471 }
1472
isBoundThroughLazyCompoundVal(const Environment & Env,const MemRegion * Reg)1473 bool isBoundThroughLazyCompoundVal(const Environment &Env,
1474 const MemRegion *Reg) {
1475 for (const auto &Binding : Env) {
1476 if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
1477 if (LCVal->getRegion() == Reg)
1478 return true;
1479 }
1480 }
1481
1482 return false;
1483 }
1484
1485 template <typename Condition, typename Process>
processIteratorPositions(ProgramStateRef State,Condition Cond,Process Proc)1486 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
1487 Process Proc) {
1488 auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
1489 auto RegionMap = State->get<IteratorRegionMap>();
1490 bool Changed = false;
1491 for (const auto &Reg : RegionMap) {
1492 if (Cond(Reg.second)) {
1493 RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
1494 Changed = true;
1495 }
1496 }
1497
1498 if (Changed)
1499 State = State->set<IteratorRegionMap>(RegionMap);
1500
1501 auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
1502 auto SymbolMap = State->get<IteratorSymbolMap>();
1503 Changed = false;
1504 for (const auto &Sym : SymbolMap) {
1505 if (Cond(Sym.second)) {
1506 SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
1507 Changed = true;
1508 }
1509 }
1510
1511 if (Changed)
1512 State = State->set<IteratorSymbolMap>(SymbolMap);
1513
1514 return State;
1515 }
1516
invalidateAllIteratorPositions(ProgramStateRef State,const MemRegion * Cont)1517 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
1518 const MemRegion *Cont) {
1519 auto MatchCont = [&](const IteratorPosition &Pos) {
1520 return Pos.getContainer() == Cont;
1521 };
1522 auto Invalidate = [&](const IteratorPosition &Pos) {
1523 return Pos.invalidate();
1524 };
1525 return processIteratorPositions(State, MatchCont, Invalidate);
1526 }
1527
1528 ProgramStateRef
invalidateAllIteratorPositionsExcept(ProgramStateRef State,const MemRegion * Cont,SymbolRef Offset,BinaryOperator::Opcode Opc)1529 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
1530 const MemRegion *Cont, SymbolRef Offset,
1531 BinaryOperator::Opcode Opc) {
1532 auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
1533 return Pos.getContainer() == Cont &&
1534 !compare(State, Pos.getOffset(), Offset, Opc);
1535 };
1536 auto Invalidate = [&](const IteratorPosition &Pos) {
1537 return Pos.invalidate();
1538 };
1539 return processIteratorPositions(State, MatchContAndCompare, Invalidate);
1540 }
1541
invalidateIteratorPositions(ProgramStateRef State,SymbolRef Offset,BinaryOperator::Opcode Opc)1542 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
1543 SymbolRef Offset,
1544 BinaryOperator::Opcode Opc) {
1545 auto Compare = [&](const IteratorPosition &Pos) {
1546 return compare(State, Pos.getOffset(), Offset, Opc);
1547 };
1548 auto Invalidate = [&](const IteratorPosition &Pos) {
1549 return Pos.invalidate();
1550 };
1551 return processIteratorPositions(State, Compare, Invalidate);
1552 }
1553
invalidateIteratorPositions(ProgramStateRef State,SymbolRef Offset1,BinaryOperator::Opcode Opc1,SymbolRef Offset2,BinaryOperator::Opcode Opc2)1554 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
1555 SymbolRef Offset1,
1556 BinaryOperator::Opcode Opc1,
1557 SymbolRef Offset2,
1558 BinaryOperator::Opcode Opc2) {
1559 auto Compare = [&](const IteratorPosition &Pos) {
1560 return compare(State, Pos.getOffset(), Offset1, Opc1) &&
1561 compare(State, Pos.getOffset(), Offset2, Opc2);
1562 };
1563 auto Invalidate = [&](const IteratorPosition &Pos) {
1564 return Pos.invalidate();
1565 };
1566 return processIteratorPositions(State, Compare, Invalidate);
1567 }
1568
reassignAllIteratorPositions(ProgramStateRef State,const MemRegion * Cont,const MemRegion * NewCont)1569 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
1570 const MemRegion *Cont,
1571 const MemRegion *NewCont) {
1572 auto MatchCont = [&](const IteratorPosition &Pos) {
1573 return Pos.getContainer() == Cont;
1574 };
1575 auto ReAssign = [&](const IteratorPosition &Pos) {
1576 return Pos.reAssign(NewCont);
1577 };
1578 return processIteratorPositions(State, MatchCont, ReAssign);
1579 }
1580
reassignAllIteratorPositionsUnless(ProgramStateRef State,const MemRegion * Cont,const MemRegion * NewCont,SymbolRef Offset,BinaryOperator::Opcode Opc)1581 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
1582 const MemRegion *Cont,
1583 const MemRegion *NewCont,
1584 SymbolRef Offset,
1585 BinaryOperator::Opcode Opc) {
1586 auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
1587 return Pos.getContainer() == Cont &&
1588 !compare(State, Pos.getOffset(), Offset, Opc);
1589 };
1590 auto ReAssign = [&](const IteratorPosition &Pos) {
1591 return Pos.reAssign(NewCont);
1592 };
1593 return processIteratorPositions(State, MatchContAndCompare, ReAssign);
1594 }
1595
1596 // This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
1597 // `OldSym - Int` to `NewSym - Int` and `OldSym` to `NewSym` in any iterator
1598 // position offsets where `CondSym` is true.
rebaseSymbolInIteratorPositionsIf(ProgramStateRef State,SValBuilder & SVB,SymbolRef OldSym,SymbolRef NewSym,SymbolRef CondSym,BinaryOperator::Opcode Opc)1599 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
1600 ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
1601 SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
1602 auto LessThanEnd = [&](const IteratorPosition &Pos) {
1603 return compare(State, Pos.getOffset(), CondSym, Opc);
1604 };
1605 auto RebaseSymbol = [&](const IteratorPosition &Pos) {
1606 return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
1607 NewSym));
1608 };
1609 return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
1610 }
1611
1612 // This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
1613 // `OldExpr - Int` to `NewExpr - Int` and `OldExpr` to `NewExpr` in expression
1614 // `OrigExpr`.
rebaseSymbol(ProgramStateRef State,SValBuilder & SVB,SymbolRef OrigExpr,SymbolRef OldExpr,SymbolRef NewSym)1615 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
1616 SymbolRef OrigExpr, SymbolRef OldExpr,
1617 SymbolRef NewSym) {
1618 auto &SymMgr = SVB.getSymbolManager();
1619 auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
1620 nonloc::SymbolVal(OldExpr),
1621 SymMgr.getType(OrigExpr));
1622
1623 const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
1624 if (!DiffInt)
1625 return OrigExpr;
1626
1627 return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
1628 SymMgr.getType(OrigExpr)).getAsSymbol();
1629 }
1630
1631 } // namespace
1632
registerIteratorModeling(CheckerManager & mgr)1633 void ento::registerIteratorModeling(CheckerManager &mgr) {
1634 mgr.registerChecker<IteratorModeling>();
1635 }
1636
shouldRegisterIteratorModeling(const LangOptions & LO)1637 bool ento::shouldRegisterIteratorModeling(const LangOptions &LO) {
1638 return true;
1639 }
1640