IteratorChecker.cpp source code [clang_source_code/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp]

1	//===-- IteratorChecker.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/DynamicTypeMap.h"
75
76	#include <utility>
77
78	using namespace clang;
79	using namespace ento;
80
81	namespace {
82
83	// Abstract position of an iterator. This helps to handle all three kinds
84	// of operators in a common way by using a symbolic position.
85	struct IteratorPosition {
86	private:
87
88	// Container the iterator belongs to
89	const MemRegion *Cont;
90
91	// Whether iterator is valid
92	const bool Valid;
93
94	// Abstract offset
95	const SymbolRef Offset;
96
97	IteratorPosition(const MemRegion *C, bool V, SymbolRef Of)
98	: Cont(C), Valid(V), Offset(Of) {}
99
100	public:
101	const MemRegion *getContainer() const { return Cont; }
102	bool isValid() const { return Valid; }
103	SymbolRef getOffset() const { return Offset; }
104
105	IteratorPosition invalidate() const {
106	return IteratorPosition(Cont, false, Offset);
107	}
108
109	static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
110	return IteratorPosition(C, true, Of);
111	}
112
113	IteratorPosition setTo(SymbolRef NewOf) const {
114	return IteratorPosition(Cont, Valid, NewOf);
115	}
116
117	IteratorPosition reAssign(const MemRegion *NewCont) const {
118	return IteratorPosition(NewCont, Valid, Offset);
119	}
120
121	bool operator==(const IteratorPosition &X) const {
122	return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
123	}
124
125	bool operator!=(const IteratorPosition &X) const {
126	return Cont != X.Cont \|\| Valid != X.Valid \|\| Offset != X.Offset;
127	}
128
129	void Profile(llvm::FoldingSetNodeID &ID) const {
130	ID.AddPointer(Cont);
131	ID.AddInteger(Valid);
132	ID.Add(Offset);
133	}
134	};
135
136	typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
137
138	// Structure to record the symbolic begin and end position of a container
139	struct ContainerData {
140	private:
141	const SymbolRef Begin, End;
142
143	ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
144
145	public:
146	static ContainerData fromBegin(SymbolRef B) {
147	return ContainerData(B, nullptr);
148	}
149
150	static ContainerData fromEnd(SymbolRef E) {
151	return ContainerData(nullptr, E);
152	}
153
154	SymbolRef getBegin() const { return Begin; }
155	SymbolRef getEnd() const { return End; }
156
157	ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
158
159	ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
160
161	bool operator==(const ContainerData &X) const {
162	return Begin == X.Begin && End == X.End;
163	}
164
165	bool operator!=(const ContainerData &X) const {
166	return Begin != X.Begin \|\| End != X.End;
167	}
168
169	void Profile(llvm::FoldingSetNodeID &ID) const {
170	ID.Add(Begin);
171	ID.Add(End);
172	}
173	};
174
175	// Structure fo recording iterator comparisons. We needed to retrieve the
176	// original comparison expression in assumptions.
177	struct IteratorComparison {
178	private:
179	RegionOrSymbol Left, Right;
180	bool Equality;
181
182	public:
183	IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
184	: Left(L), Right(R), Equality(Eq) {}
185
186	RegionOrSymbol getLeft() const { return Left; }
187	RegionOrSymbol getRight() const { return Right; }
188	bool isEquality() const { return Equality; }
189	bool operator==(const IteratorComparison &X) const {
190	return Left == X.Left && Right == X.Right && Equality == X.Equality;
191	}
192	bool operator!=(const IteratorComparison &X) const {
193	return Left != X.Left \|\| Right != X.Right \|\| Equality != X.Equality;
194	}
195	void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
196	};
197
198	class IteratorChecker
199	: public Checker<check::PreCall, check::PostCall,
200	check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
201	check::LiveSymbols, check::DeadSymbols,
202	eval::Assume> {
203
204	std::unique_ptr<BugType> OutOfRangeBugType;
205	std::unique_ptr<BugType> MismatchedBugType;
206	std::unique_ptr<BugType> InvalidatedBugType;
207
208	void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
209	const SVal &RVal, OverloadedOperatorKind Op) const;
210	void verifyAccess(CheckerContext &C, const SVal &Val) const;
211	void verifyDereference(CheckerContext &C, const SVal &Val) const;
212	void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
213	bool Postfix) const;
214	void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
215	bool Postfix) const;
216	void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
217	const SVal &RetVal, const SVal &LHS,
218	const SVal &RHS) const;
219	void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
220	const SVal &Cont) const;
221	void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
222	const SVal &Cont) const;
223	void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
224	const MemRegion *Cont) const;
225	void handleAssign(CheckerContext &C, const SVal &Cont,
226	const Expr *CE = nullptr,
227	const SVal &OldCont = UndefinedVal()) const;
228	void handleClear(CheckerContext &C, const SVal &Cont) const;
229	void handlePushBack(CheckerContext &C, const SVal &Cont) const;
230	void handlePopBack(CheckerContext &C, const SVal &Cont) const;
231	void handlePushFront(CheckerContext &C, const SVal &Cont) const;
232	void handlePopFront(CheckerContext &C, const SVal &Cont) const;
233	void handleInsert(CheckerContext &C, const SVal &Iter) const;
234	void handleErase(CheckerContext &C, const SVal &Iter) const;
235	void handleErase(CheckerContext &C, const SVal &Iter1,
236	const SVal &Iter2) const;
237	void handleEraseAfter(CheckerContext &C, const SVal &Iter) const;
238	void handleEraseAfter(CheckerContext &C, const SVal &Iter1,
239	const SVal &Iter2) const;
240	void verifyIncrement(CheckerContext &C, const SVal &Iter) const;
241	void verifyDecrement(CheckerContext &C, const SVal &Iter) const;
242	void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
243	const SVal &LHS, const SVal &RHS) const;
244	void verifyMatch(CheckerContext &C, const SVal &Iter,
245	const MemRegion *Cont) const;
246	void verifyMatch(CheckerContext &C, const SVal &Iter1,
247	const SVal &Iter2) const;
248	IteratorPosition advancePosition(CheckerContext &C, OverloadedOperatorKind Op,
249	const IteratorPosition &Pos,
250	const SVal &Distance) const;
251	void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
252	CheckerContext &C, ExplodedNode *ErrNode) const;
253	void reportMismatchedBug(const StringRef &Message, const SVal &Val1,
254	const SVal &Val2, CheckerContext &C,
255	ExplodedNode *ErrNode) const;
256	void reportMismatchedBug(const StringRef &Message, const SVal &Val,
257	const MemRegion *Reg, CheckerContext &C,
258	ExplodedNode *ErrNode) const;
259	void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
260	CheckerContext &C, ExplodedNode *ErrNode) const;
261
262	public:
263	IteratorChecker();
264
265	enum CheckKind {
266	CK_IteratorRangeChecker,
267	CK_MismatchedIteratorChecker,
268	CK_InvalidatedIteratorChecker,
269	CK_NumCheckKinds
270	};
271
272	DefaultBool ChecksEnabled[CK_NumCheckKinds];
273	CheckName CheckNames[CK_NumCheckKinds];
274
275	void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
276	void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
277	void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
278	void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
279	void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
280	void checkPostStmt(const MaterializeTemporaryExpr *MTE,
281	CheckerContext &C) const;
282	void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
283	void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
284	ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
285	bool Assumption) const;
286	};
287	} // namespace
288
289	REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
290	REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
291	IteratorPosition)
292
293	REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
294
295	REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
296	IteratorComparison)
297
298	namespace {
299
300	bool isIteratorType(const QualType &Type);
301	bool isIterator(const CXXRecordDecl *CRD);
302	bool isComparisonOperator(OverloadedOperatorKind OK);
303	bool isBeginCall(const FunctionDecl *Func);
304	bool isEndCall(const FunctionDecl *Func);
305	bool isAssignCall(const FunctionDecl *Func);
306	bool isClearCall(const FunctionDecl *Func);
307	bool isPushBackCall(const FunctionDecl *Func);
308	bool isEmplaceBackCall(const FunctionDecl *Func);
309	bool isPopBackCall(const FunctionDecl *Func);
310	bool isPushFrontCall(const FunctionDecl *Func);
311	bool isEmplaceFrontCall(const FunctionDecl *Func);
312	bool isPopFrontCall(const FunctionDecl *Func);
313	bool isInsertCall(const FunctionDecl *Func);
314	bool isEraseCall(const FunctionDecl *Func);
315	bool isEraseAfterCall(const FunctionDecl *Func);
316	bool isEmplaceCall(const FunctionDecl *Func);
317	bool isAssignmentOperator(OverloadedOperatorKind OK);
318	bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
319	bool isAccessOperator(OverloadedOperatorKind OK);
320	bool isDereferenceOperator(OverloadedOperatorKind OK);
321	bool isIncrementOperator(OverloadedOperatorKind OK);
322	bool isDecrementOperator(OverloadedOperatorKind OK);
323	bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
324	bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
325	bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
326	bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
327	BinaryOperator::Opcode getOpcode(const SymExpr *SE);
328	const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
329	const ProgramStateRef processComparison(ProgramStateRef State,
330	RegionOrSymbol LVal,
331	RegionOrSymbol RVal, bool Equal);
332	const ProgramStateRef saveComparison(ProgramStateRef State,
333	const SymExpr *Condition, const SVal &LVal,
334	const SVal &RVal, bool Eq);
335	const IteratorComparison *loadComparison(ProgramStateRef State,
336	const SymExpr *Condition);
337	SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
338	SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
339	ProgramStateRef createContainerBegin(ProgramStateRef State,
340	const MemRegion *Cont,
341	const SymbolRef Sym);
342	ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
343	const SymbolRef Sym);
344	const IteratorPosition *getIteratorPosition(ProgramStateRef State,
345	const SVal &Val);
346	const IteratorPosition *getIteratorPosition(ProgramStateRef State,
347	RegionOrSymbol RegOrSym);
348	ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
349	const IteratorPosition &Pos);
350	ProgramStateRef setIteratorPosition(ProgramStateRef State,
351	RegionOrSymbol RegOrSym,
352	const IteratorPosition &Pos);
353	ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
354	ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
355	RegionOrSymbol RegOrSym,
356	const IteratorPosition &Pos, bool Equal);
357	ProgramStateRef relateIteratorPositions(ProgramStateRef State,
358	const IteratorPosition &Pos1,
359	const IteratorPosition &Pos2,
360	bool Equal);
361	ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
362	const MemRegion *Cont);
363	ProgramStateRef
364	invalidateAllIteratorPositionsExcept(ProgramStateRef State,
365	const MemRegion *Cont, SymbolRef Offset,
366	BinaryOperator::Opcode Opc);
367	ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
368	SymbolRef Offset,
369	BinaryOperator::Opcode Opc);
370	ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
371	SymbolRef Offset1,
372	BinaryOperator::Opcode Opc1,
373	SymbolRef Offset2,
374	BinaryOperator::Opcode Opc2);
375	ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
376	const MemRegion *Cont,
377	const MemRegion *NewCont);
378	ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
379	const MemRegion *Cont,
380	const MemRegion *NewCont,
381	SymbolRef Offset,
382	BinaryOperator::Opcode Opc);
383	ProgramStateRef rebaseSymbolInIteratorPositionsIf(
384	ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
385	SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
386	const ContainerData *getContainerData(ProgramStateRef State,
387	const MemRegion *Cont);
388	ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
389	const ContainerData &CData);
390	bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
391	bool isBoundThroughLazyCompoundVal(const Environment &Env,
392	const MemRegion *Reg);
393	bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
394	bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
395	bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
396	bool isZero(ProgramStateRef State, const NonLoc &Val);
397	} // namespace
398
399	IteratorChecker::IteratorChecker() {
400	OutOfRangeBugType.reset(
401	new BugType(this, "Iterator out of range", "Misuse of STL APIs",
402	/SuppressOnSink=/true));
403	MismatchedBugType.reset(
404	new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
405	/SuppressOnSink=/true));
406	InvalidatedBugType.reset(
407	new BugType(this, "Iterator invalidated", "Misuse of STL APIs",
408	/SuppressOnSink=/true));
409	}
410
411	void IteratorChecker::checkPreCall(const CallEvent &Call,
412	CheckerContext &C) const {
413	// Check for out of range access or access of invalidated position and
414	// iterator mismatches
415	const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
416	if (!Func)
417	return;
418
419	if (Func->isOverloadedOperator()) {
420	if (ChecksEnabled[CK_InvalidatedIteratorChecker] &&
421	isAccessOperator(Func->getOverloadedOperator())) {
422	// Check for any kind of access of invalidated iterator positions
423	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
424	verifyAccess(C, InstCall->getCXXThisVal());
425	} else {
426	verifyAccess(C, Call.getArgSVal(0));
427	}
428	}
429	if (ChecksEnabled[CK_IteratorRangeChecker]) {
430	if (isIncrementOperator(Func->getOverloadedOperator())) {
431	// Check for out-of-range incrementions
432	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
433	verifyIncrement(C, InstCall->getCXXThisVal());
434	} else {
435	if (Call.getNumArgs() >= 1) {
436	verifyIncrement(C, Call.getArgSVal(0));
437	}
438	}
439	} else if (isDecrementOperator(Func->getOverloadedOperator())) {
440	// Check for out-of-range decrementions
441	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
442	verifyDecrement(C, InstCall->getCXXThisVal());
443	} else {
444	if (Call.getNumArgs() >= 1) {
445	verifyDecrement(C, Call.getArgSVal(0));
446	}
447	}
448	} else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
449	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
450	// Check for out-of-range incrementions and decrementions
451	if (Call.getNumArgs() >= 1) {
452	verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
453	InstCall->getCXXThisVal(),
454	Call.getArgSVal(0));
455	}
456	} else {
457	if (Call.getNumArgs() >= 2) {
458	verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
459	Call.getArgSVal(0), Call.getArgSVal(1));
460	}
461	}
462	} else if (isDereferenceOperator(Func->getOverloadedOperator())) {
463	// Check for dereference of out-of-range iterators
464	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
465	verifyDereference(C, InstCall->getCXXThisVal());
466	} else {
467	verifyDereference(C, Call.getArgSVal(0));
468	}
469	}
470	} else if (ChecksEnabled[CK_MismatchedIteratorChecker] &&
471	isComparisonOperator(Func->getOverloadedOperator())) {
472	// Check for comparisons of iterators of different containers
473	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
474	if (Call.getNumArgs() < 1)
475	return;
476
477	if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) \|\|
478	!isIteratorType(Call.getArgExpr(0)->getType()))
479	return;
480
481	verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
482	} else {
483	if (Call.getNumArgs() < 2)
484	return;
485
486	if (!isIteratorType(Call.getArgExpr(0)->getType()) \|\|
487	!isIteratorType(Call.getArgExpr(1)->getType()))
488	return;
489
490	verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
491	}
492	}
493	} else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
494	if (!ChecksEnabled[CK_MismatchedIteratorChecker])
495	return;
496
497	const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
498	if (!ContReg)
499	return;
500	// Check for erase, insert and emplace using iterator of another container
501	if (isEraseCall(Func) \|\| isEraseAfterCall(Func)) {
502	verifyMatch(C, Call.getArgSVal(0),
503	InstCall->getCXXThisVal().getAsRegion());
504	if (Call.getNumArgs() == 2) {
505	verifyMatch(C, Call.getArgSVal(1),
506	InstCall->getCXXThisVal().getAsRegion());
507	}
508	} else if (isInsertCall(Func)) {
509	verifyMatch(C, Call.getArgSVal(0),
510	InstCall->getCXXThisVal().getAsRegion());
511	if (Call.getNumArgs() == 3 &&
512	isIteratorType(Call.getArgExpr(1)->getType()) &&
513	isIteratorType(Call.getArgExpr(2)->getType())) {
514	verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
515	}
516	} else if (isEmplaceCall(Func)) {
517	verifyMatch(C, Call.getArgSVal(0),
518	InstCall->getCXXThisVal().getAsRegion());
519	}
520	} else if (isa<CXXConstructorCall>(&Call)) {
521	// Check match of first-last iterator pair in a constructor of a container
522	if (Call.getNumArgs() < 2)
523	return;
524
525	const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
526	if (Ctr->getNumParams() < 2)
527	return;
528
529	if (Ctr->getParamDecl(0)->getName() != "first" \|\|
530	Ctr->getParamDecl(1)->getName() != "last")
531	return;
532
533	if (!isIteratorType(Call.getArgExpr(0)->getType()) \|\|
534	!isIteratorType(Call.getArgExpr(1)->getType()))
535	return;
536
537	verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
538	} else {
539	// The main purpose of iterators is to abstract away from different
540	// containers and provide a (maybe limited) uniform access to them.
541	// This implies that any correctly written template function that
542	// works on multiple containers using iterators takes different
543	// template parameters for different containers. So we can safely
544	// assume that passing iterators of different containers as arguments
545	// whose type replaces the same template parameter is a bug.
546	//
547	// Example:
548	// template<typename I1, typename I2>
549	// void f(I1 first1, I1 last1, I2 first2, I2 last2);
550	//
551	// In this case the first two arguments to f() must be iterators must belong
552	// to the same container and the last to also to the same container but
553	// not necessarily to the same as the first two.
554
555	if (!ChecksEnabled[CK_MismatchedIteratorChecker])
556	return;
557
558	const auto *Templ = Func->getPrimaryTemplate();
559	if (!Templ)
560	return;
561
562	const auto *TParams = Templ->getTemplateParameters();
563	const auto *TArgs = Func->getTemplateSpecializationArgs();
564
565	// Iterate over all the template parameters
566	for (size_t I = 0; I < TParams->size(); ++I) {
567	const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
568	if (!TPDecl)
569	continue;
570
571	if (TPDecl->isParameterPack())
572	continue;
573
574	const auto TAType = TArgs->get(I).getAsType();
575	if (!isIteratorType(TAType))
576	continue;
577
578	SVal LHS = UndefinedVal();
579
580	// For every template parameter which is an iterator type in the
581	// instantiation look for all functions' parameters' type by it and
582	// check whether they belong to the same container
583	for (auto J = 0U; J < Func->getNumParams(); ++J) {
584	const auto *Param = Func->getParamDecl(J);
585	const auto *ParamType =
586	Param->getType()->getAs<SubstTemplateTypeParmType>();
587	if (!ParamType \|\|
588	ParamType->getReplacedParameter()->getDecl() != TPDecl)
589	continue;
590	if (LHS.isUndef()) {
591	LHS = Call.getArgSVal(J);
592	} else {
593	verifyMatch(C, LHS, Call.getArgSVal(J));
594	}
595	}
596	}
597	}
598	}
599
600	void IteratorChecker::checkPostCall(const CallEvent &Call,
601	CheckerContext &C) const {
602	// Record new iterator positions and iterator position changes
603	const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
604	if (!Func)
605	return;
606
607	if (Func->isOverloadedOperator()) {
608	const auto Op = Func->getOverloadedOperator();
609	if (isAssignmentOperator(Op)) {
610	const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call);
611	if (Func->getParamDecl(0)->getType()->isRValueReferenceType()) {
612	handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
613	Call.getArgSVal(0));
614	} else {
615	handleAssign(C, InstCall->getCXXThisVal());
616	}
617	} else if (isSimpleComparisonOperator(Op)) {
618	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
619	handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
620	Call.getArgSVal(0), Op);
621	} else {
622	handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
623	Call.getArgSVal(1), Op);
624	}
625	} else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
626	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
627	if (Call.getNumArgs() >= 1) {
628	handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
629	Call.getReturnValue(),
630	InstCall->getCXXThisVal(), Call.getArgSVal(0));
631	}
632	} else {
633	if (Call.getNumArgs() >= 2) {
634	handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
635	Call.getReturnValue(), Call.getArgSVal(0),
636	Call.getArgSVal(1));
637	}
638	}
639	} else if (isIncrementOperator(Func->getOverloadedOperator())) {
640	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
641	handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
642	Call.getNumArgs());
643	} else {
644	handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
645	Call.getNumArgs());
646	}
647	} else if (isDecrementOperator(Func->getOverloadedOperator())) {
648	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
649	handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
650	Call.getNumArgs());
651	} else {
652	handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
653	Call.getNumArgs());
654	}
655	}
656	} else {
657	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
658	if (isAssignCall(Func)) {
659	handleAssign(C, InstCall->getCXXThisVal());
660	} else if (isClearCall(Func)) {
661	handleClear(C, InstCall->getCXXThisVal());
662	} else if (isPushBackCall(Func) \|\| isEmplaceBackCall(Func)) {
663	handlePushBack(C, InstCall->getCXXThisVal());
664	} else if (isPopBackCall(Func)) {
665	handlePopBack(C, InstCall->getCXXThisVal());
666	} else if (isPushFrontCall(Func) \|\| isEmplaceFrontCall(Func)) {
667	handlePushFront(C, InstCall->getCXXThisVal());
668	} else if (isPopFrontCall(Func)) {
669	handlePopFront(C, InstCall->getCXXThisVal());
670	} else if (isInsertCall(Func) \|\| isEmplaceCall(Func)) {
671	handleInsert(C, Call.getArgSVal(0));
672	} else if (isEraseCall(Func)) {
673	if (Call.getNumArgs() == 1) {
674	handleErase(C, Call.getArgSVal(0));
675	} else if (Call.getNumArgs() == 2) {
676	handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1));
677	}
678	} else if (isEraseAfterCall(Func)) {
679	if (Call.getNumArgs() == 1) {
680	handleEraseAfter(C, Call.getArgSVal(0));
681	} else if (Call.getNumArgs() == 2) {
682	handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1));
683	}
684	}
685	}
686
687	const auto *OrigExpr = Call.getOriginExpr();
688	if (!OrigExpr)
689	return;
690
691	if (!isIteratorType(Call.getResultType()))
692	return;
693
694	auto State = C.getState();
695
696	if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
697	if (isBeginCall(Func)) {
698	handleBegin(C, OrigExpr, Call.getReturnValue(),
699	InstCall->getCXXThisVal());
700	return;
701	}
702	if (isEndCall(Func)) {
703	handleEnd(C, OrigExpr, Call.getReturnValue(),
704	InstCall->getCXXThisVal());
705	return;
706	}
707	}
708
709	// Already bound to container?
710	if (getIteratorPosition(State, Call.getReturnValue()))
711	return;
712
713	// Copy-like and move constructors
714	if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
715	if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
716	State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
717	if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
718	State = removeIteratorPosition(State, Call.getArgSVal(0));
719	}
720	C.addTransition(State);
721	return;
722	}
723	}
724
725	// Assumption: if return value is an iterator which is not yet bound to a
726	// container, then look for the first iterator argument, and
727	// bind the return value to the same container. This approach
728	// works for STL algorithms.
729	// FIXME: Add a more conservative mode
730	for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
731	if (isIteratorType(Call.getArgExpr(i)->getType())) {
732	if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
733	assignToContainer(C, OrigExpr, Call.getReturnValue(),
734	Pos->getContainer());
735	return;
736	}
737	}
738	}
739	}
740	}
741
742	void IteratorChecker::checkBind(SVal Loc, SVal Val, const Stmt *S,
743	CheckerContext &C) const {
744	auto State = C.getState();
745	const auto *Pos = getIteratorPosition(State, Val);
746	if (Pos) {
747	State = setIteratorPosition(State, Loc, *Pos);
748	C.addTransition(State);
749	} else {
750	const auto *OldPos = getIteratorPosition(State, Loc);
751	if (OldPos) {
752	State = removeIteratorPosition(State, Loc);
753	C.addTransition(State);
754	}
755	}
756	}
757
758	void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
759	CheckerContext &C) const {
760	/* Transfer iterator state to temporary objects */
761	auto State = C.getState();
762	const auto *Pos =
763	getIteratorPosition(State, C.getSVal(MTE->GetTemporaryExpr()));
764	if (!Pos)
765	return;
766	State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
767	C.addTransition(State);
768	}
769
770	void IteratorChecker::checkLiveSymbols(ProgramStateRef State,
771	SymbolReaper &SR) const {
772	// Keep symbolic expressions of iterator positions, container begins and ends
773	// alive
774	auto RegionMap = State->get<IteratorRegionMap>();
775	for (const auto Reg : RegionMap) {
776	const auto Offset = Reg.second.getOffset();
777	for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
778	if (isa<SymbolData>(*i))
779	SR.markLive(*i);
780	}
781
782	auto SymbolMap = State->get<IteratorSymbolMap>();
783	for (const auto Sym : SymbolMap) {
784	const auto Offset = Sym.second.getOffset();
785	for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
786	if (isa<SymbolData>(*i))
787	SR.markLive(*i);
788	}
789
790	auto ContMap = State->get<ContainerMap>();
791	for (const auto Cont : ContMap) {
792	const auto CData = Cont.second;
793	if (CData.getBegin()) {
794	SR.markLive(CData.getBegin());
795	if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
796	SR.markLive(SIE->getLHS());
797	}
798	if (CData.getEnd()) {
799	SR.markLive(CData.getEnd());
800	if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
801	SR.markLive(SIE->getLHS());
802	}
803	}
804	}
805
806	void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
807	CheckerContext &C) const {
808	// Cleanup
809	auto State = C.getState();
810
811	auto RegionMap = State->get<IteratorRegionMap>();
812	for (const auto Reg : RegionMap) {
813	if (!SR.isLiveRegion(Reg.first)) {
814	// The region behind the `LazyCompoundVal` is often cleaned up before
815	// the `LazyCompoundVal` itself. If there are iterator positions keyed
816	// by these regions their cleanup must be deferred.
817	if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
818	State = State->remove<IteratorRegionMap>(Reg.first);
819	}
820	}
821	}
822
823	auto SymbolMap = State->get<IteratorSymbolMap>();
824	for (const auto Sym : SymbolMap) {
825	if (!SR.isLive(Sym.first)) {
826	State = State->remove<IteratorSymbolMap>(Sym.first);
827	}
828	}
829
830	auto ContMap = State->get<ContainerMap>();
831	for (const auto Cont : ContMap) {
832	if (!SR.isLiveRegion(Cont.first)) {
833	// We must keep the container data while it has live iterators to be able
834	// to compare them to the begin and the end of the container.
835	if (!hasLiveIterators(State, Cont.first)) {
836	State = State->remove<ContainerMap>(Cont.first);
837	}
838	}
839	}
840
841	auto ComparisonMap = State->get<IteratorComparisonMap>();
842	for (const auto Comp : ComparisonMap) {
843	if (!SR.isLive(Comp.first)) {
844	State = State->remove<IteratorComparisonMap>(Comp.first);
845	}
846	}
847
848	C.addTransition(State);
849	}
850
851	ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
852	bool Assumption) const {
853	// Load recorded comparison and transfer iterator state between sides
854	// according to comparison operator and assumption
855	const auto *SE = Cond.getAsSymExpr();
856	if (!SE)
857	return State;
858
859	auto Opc = getOpcode(SE);
860	if (Opc != BO_EQ && Opc != BO_NE)
861	return State;
862
863	bool Negated = false;
864	const auto *Comp = loadComparison(State, SE);
865	if (!Comp) {
866	// Try negated comparison, which is a SymExpr to 0 integer comparison
867	const auto *SIE = dyn_cast<SymIntExpr>(SE);
868	if (!SIE)
869	return State;
870
871	if (SIE->getRHS() != 0)
872	return State;
873
874	SE = SIE->getLHS();
875	Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
876	Opc = getOpcode(SE);
877	if (Opc != BO_EQ && Opc != BO_NE)
878	return State;
879
880	Comp = loadComparison(State, SE);
881	if (!Comp)
882	return State;
883	}
884
885	return processComparison(State, Comp->getLeft(), Comp->getRight(),
886	(Comp->isEquality() == Assumption) != Negated);
887	}
888
889	void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
890	const SVal &LVal, const SVal &RVal,
891	OverloadedOperatorKind Op) const {
892	// Record the operands and the operator of the comparison for the next
893	// evalAssume, if the result is a symbolic expression. If it is a concrete
894	// value (only one branch is possible), then transfer the state between
895	// the operands according to the operator and the result
896	auto State = C.getState();
897	if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
898	const auto *LPos = getIteratorPosition(State, LVal);
899	const auto *RPos = getIteratorPosition(State, RVal);
900	if (!LPos && !RPos)
901	return;
902	State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
903	C.addTransition(State);
904	} else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
905	if ((State = processComparison(
906	State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
907	(Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
908	C.addTransition(State);
909	} else {
910	C.generateSink(State, C.getPredecessor());
911	}
912	}
913	}
914
915	void IteratorChecker::verifyDereference(CheckerContext &C,
916	const SVal &Val) const {
917	auto State = C.getState();
918	const auto *Pos = getIteratorPosition(State, Val);
919	if (Pos && isPastTheEnd(State, *Pos)) {
920	auto *N = C.generateNonFatalErrorNode(State);
921	if (!N)
922	return;
923	reportOutOfRangeBug("Past-the-end iterator dereferenced.", Val, C, N);
924	return;
925	}
926	}
927
928	void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
929	auto State = C.getState();
930	const auto *Pos = getIteratorPosition(State, Val);
931	if (Pos && !Pos->isValid()) {
932	auto *N = C.generateNonFatalErrorNode(State);
933	if (!N) {
934	return;
935	}
936	reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
937	}
938	}
939
940	void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
941	const SVal &Iter, bool Postfix) const {
942	// Increment the symbolic expressions which represents the position of the
943	// iterator
944	auto State = C.getState();
945	const auto *Pos = getIteratorPosition(State, Iter);
946	if (Pos) {
947	auto &SymMgr = C.getSymbolManager();
948	auto &BVF = SymMgr.getBasicVals();
949	const auto NewPos =
950	advancePosition(C, OO_Plus, *Pos,
951	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
952	State = setIteratorPosition(State, Iter, NewPos);
953	State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
954	C.addTransition(State);
955	}
956	}
957
958	void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal,
959	const SVal &Iter, bool Postfix) const {
960	// Decrement the symbolic expressions which represents the position of the
961	// iterator
962	auto State = C.getState();
963	const auto *Pos = getIteratorPosition(State, Iter);
964	if (Pos) {
965	auto &SymMgr = C.getSymbolManager();
966	auto &BVF = SymMgr.getBasicVals();
967	const auto NewPos =
968	advancePosition(C, OO_Minus, *Pos,
969	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
970	State = setIteratorPosition(State, Iter, NewPos);
971	State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
972	C.addTransition(State);
973	}
974	}
975
976	// This function tells the analyzer's engine that symbols produced by our
977	// checker, most notably iterator positions, are relatively small.
978	// A distance between items in the container should not be very large.
979	// By assuming that it is within around 1/8 of the address space,
980	// we can help the analyzer perform operations on these symbols
981	// without being afraid of integer overflows.
982	// FIXME: Should we provide it as an API, so that all checkers could use it?
983	static ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
984	long Scale) {
985	SValBuilder &SVB = State->getStateManager().getSValBuilder();
986	BasicValueFactory &BV = SVB.getBasicValueFactory();
987
988	QualType T = Sym->getType();
989	isSignedIntegerOrEnumerationType()", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 989, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(T->isSignedIntegerOrEnumerationType());
990	APSIntType AT = BV.getAPSIntType(T);
991
992	ProgramStateRef NewState = State;
993
994	llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
995	SVal IsCappedFromAbove =
996	SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
997	nonloc::ConcreteInt(Max), SVB.getConditionType());
998	if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
999	NewState = NewState->assume(*DV, true);
1000	if (!NewState)
1001	return State;
1002	}
1003
1004	llvm::APSInt Min = -Max;
1005	SVal IsCappedFromBelow =
1006	SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
1007	nonloc::ConcreteInt(Min), SVB.getConditionType());
1008	if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
1009	NewState = NewState->assume(*DV, true);
1010	if (!NewState)
1011	return State;
1012	}
1013
1014	return NewState;
1015	}
1016
1017	void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C,
1018	OverloadedOperatorKind Op,
1019	const SVal &RetVal,
1020	const SVal &LHS,
1021	const SVal &RHS) const {
1022	// Increment or decrement the symbolic expressions which represents the
1023	// position of the iterator
1024	auto State = C.getState();
1025	const auto *Pos = getIteratorPosition(State, LHS);
1026	if (!Pos)
1027	return;
1028
1029	const auto *value = &RHS;
1030	if (auto loc = RHS.getAs<Loc>()) {
1031	const auto val = State->getRawSVal(*loc);
1032	value = &val;
1033	}
1034
1035	auto &TgtVal = (Op == OO_PlusEqual \|\| Op == OO_MinusEqual) ? LHS : RetVal;
1036	State =
1037	setIteratorPosition(State, TgtVal, advancePosition(C, Op, Pos, value));
1038	C.addTransition(State);
1039	}
1040
1041	void IteratorChecker::verifyIncrement(CheckerContext &C,
1042	const SVal &Iter) const {
1043	auto &BVF = C.getSValBuilder().getBasicValueFactory();
1044	verifyRandomIncrOrDecr(C, OO_Plus, Iter,
1045	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
1046	}
1047
1048	void IteratorChecker::verifyDecrement(CheckerContext &C,
1049	const SVal &Iter) const {
1050	auto &BVF = C.getSValBuilder().getBasicValueFactory();
1051	verifyRandomIncrOrDecr(C, OO_Minus, Iter,
1052	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
1053	}
1054
1055	void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
1056	OverloadedOperatorKind Op,
1057	const SVal &LHS,
1058	const SVal &RHS) const {
1059	auto State = C.getState();
1060
1061	// If the iterator is initially inside its range, then the operation is valid
1062	const auto *Pos = getIteratorPosition(State, LHS);
1063	if (!Pos)
1064	return;
1065
1066	auto Value = RHS;
1067	if (auto ValAsLoc = RHS.getAs<Loc>()) {
1068	Value = State->getRawSVal(*ValAsLoc);
1069	}
1070
1071	if (Value.isUnknown())
1072	return;
1073
1074	// Incremention or decremention by 0 is never a bug.
1075	if (isZero(State, Value.castAs<NonLoc>()))
1076	return;
1077
1078	// The result may be the past-end iterator of the container, but any other
1079	// out of range position is undefined behaviour
1080	if (isAheadOfRange(State, advancePosition(C, Op, *Pos, Value))) {
1081	auto *N = C.generateNonFatalErrorNode(State);
1082	if (!N)
1083	return;
1084	reportOutOfRangeBug("Iterator decremented ahead of its valid range.", LHS,
1085	C, N);
1086	}
1087	if (isBehindPastTheEnd(State, advancePosition(C, Op, *Pos, Value))) {
1088	auto *N = C.generateNonFatalErrorNode(State);
1089	if (!N)
1090	return;
1091	reportOutOfRangeBug("Iterator incremented behind the past-the-end "
1092	"iterator.", LHS, C, N);
1093	}
1094	}
1095
1096	void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
1097	const MemRegion *Cont) const {
1098	// Verify match between a container and the container of an iterator
1099	Cont = Cont->getMostDerivedObjectRegion();
1100
1101	if (const auto *ContSym = Cont->getSymbolicBase()) {
1102	if (isa<SymbolConjured>(ContSym->getSymbol()))
1103	return;
1104	}
1105
1106	auto State = C.getState();
1107	const auto *Pos = getIteratorPosition(State, Iter);
1108	if (!Pos)
1109	return;
1110
1111	const auto *IterCont = Pos->getContainer();
1112
1113	// Skip symbolic regions based on conjured symbols. Two conjured symbols
1114	// may or may not be the same. For example, the same function can return
1115	// the same or a different container but we get different conjured symbols
1116	// for each call. This may cause false positives so omit them from the check.
1117	if (const auto *ContSym = IterCont->getSymbolicBase()) {
1118	if (isa<SymbolConjured>(ContSym->getSymbol()))
1119	return;
1120	}
1121
1122	if (IterCont != Cont) {
1123	auto *N = C.generateNonFatalErrorNode(State);
1124	if (!N) {
1125	return;
1126	}
1127	reportMismatchedBug("Container accessed using foreign iterator argument.",
1128	Iter, Cont, C, N);
1129	}
1130	}
1131
1132	void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1,
1133	const SVal &Iter2) const {
1134	// Verify match between the containers of two iterators
1135	auto State = C.getState();
1136	const auto *Pos1 = getIteratorPosition(State, Iter1);
1137	if (!Pos1)
1138	return;
1139
1140	const auto *IterCont1 = Pos1->getContainer();
1141
1142	// Skip symbolic regions based on conjured symbols. Two conjured symbols
1143	// may or may not be the same. For example, the same function can return
1144	// the same or a different container but we get different conjured symbols
1145	// for each call. This may cause false positives so omit them from the check.
1146	if (const auto *ContSym = IterCont1->getSymbolicBase()) {
1147	if (isa<SymbolConjured>(ContSym->getSymbol()))
1148	return;
1149	}
1150
1151	const auto *Pos2 = getIteratorPosition(State, Iter2);
1152	if (!Pos2)
1153	return;
1154
1155	const auto *IterCont2 = Pos2->getContainer();
1156	if (const auto *ContSym = IterCont2->getSymbolicBase()) {
1157	if (isa<SymbolConjured>(ContSym->getSymbol()))
1158	return;
1159	}
1160
1161	if (IterCont1 != IterCont2) {
1162	auto *N = C.generateNonFatalErrorNode(State);
1163	if (!N)
1164	return;
1165	reportMismatchedBug("Iterators of different containers used where the "
1166	"same container is expected.", Iter1, Iter2, C, N);
1167	}
1168	}
1169
1170	void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
1171	const SVal &RetVal, const SVal &Cont) const {
1172	const auto *ContReg = Cont.getAsRegion();
1173	if (!ContReg)
1174	return;
1175
1176	ContReg = ContReg->getMostDerivedObjectRegion();
1177
1178	// If the container already has a begin symbol then use it. Otherwise first
1179	// create a new one.
1180	auto State = C.getState();
1181	auto BeginSym = getContainerBegin(State, ContReg);
1182	if (!BeginSym) {
1183	auto &SymMgr = C.getSymbolManager();
1184	BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1185	C.getASTContext().LongTy, C.blockCount());
1186	State = assumeNoOverflow(State, BeginSym, 4);
1187	State = createContainerBegin(State, ContReg, BeginSym);
1188	}
1189	State = setIteratorPosition(State, RetVal,
1190	IteratorPosition::getPosition(ContReg, BeginSym));
1191	C.addTransition(State);
1192	}
1193
1194	void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
1195	const SVal &RetVal, const SVal &Cont) const {
1196	const auto *ContReg = Cont.getAsRegion();
1197	if (!ContReg)
1198	return;
1199
1200	ContReg = ContReg->getMostDerivedObjectRegion();
1201
1202	// If the container already has an end symbol then use it. Otherwise first
1203	// create a new one.
1204	auto State = C.getState();
1205	auto EndSym = getContainerEnd(State, ContReg);
1206	if (!EndSym) {
1207	auto &SymMgr = C.getSymbolManager();
1208	EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1209	C.getASTContext().LongTy, C.blockCount());
1210	State = assumeNoOverflow(State, EndSym, 4);
1211	State = createContainerEnd(State, ContReg, EndSym);
1212	}
1213	State = setIteratorPosition(State, RetVal,
1214	IteratorPosition::getPosition(ContReg, EndSym));
1215	C.addTransition(State);
1216	}
1217
1218	void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
1219	const SVal &RetVal,
1220	const MemRegion *Cont) const {
1221	Cont = Cont->getMostDerivedObjectRegion();
1222
1223	auto State = C.getState();
1224	auto &SymMgr = C.getSymbolManager();
1225	auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1226	C.getASTContext().LongTy, C.blockCount());
1227	State = assumeNoOverflow(State, Sym, 4);
1228	State = setIteratorPosition(State, RetVal,
1229	IteratorPosition::getPosition(Cont, Sym));
1230	C.addTransition(State);
1231	}
1232
1233	void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont,
1234	const Expr *CE, const SVal &OldCont) const {
1235	const auto *ContReg = Cont.getAsRegion();
1236	if (!ContReg)
1237	return;
1238
1239	ContReg = ContReg->getMostDerivedObjectRegion();
1240
1241	// Assignment of a new value to a container always invalidates all its
1242	// iterators
1243	auto State = C.getState();
1244	const auto CData = getContainerData(State, ContReg);
1245	if (CData) {
1246	State = invalidateAllIteratorPositions(State, ContReg);
1247	}
1248
1249	// In case of move, iterators of the old container (except the past-end
1250	// iterators) remain valid but refer to the new container
1251	if (!OldCont.isUndef()) {
1252	const auto *OldContReg = OldCont.getAsRegion();
1253	if (OldContReg) {
1254	OldContReg = OldContReg->getMostDerivedObjectRegion();
1255	const auto OldCData = getContainerData(State, OldContReg);
1256	if (OldCData) {
1257	if (const auto OldEndSym = OldCData->getEnd()) {
1258	// If we already assigned an "end" symbol to the old container, then
1259	// first reassign all iterator positions to the new container which
1260	// are not past the container (thus not greater or equal to the
1261	// current "end" symbol).
1262	State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
1263	OldEndSym, BO_GE);
1264	auto &SymMgr = C.getSymbolManager();
1265	auto &SVB = C.getSValBuilder();
1266	// Then generate and assign a new "end" symbol for the new container.
1267	auto NewEndSym =
1268	SymMgr.conjureSymbol(CE, C.getLocationContext(),
1269	C.getASTContext().LongTy, C.blockCount());
1270	State = assumeNoOverflow(State, NewEndSym, 4);
1271	if (CData) {
1272	State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
1273	} else {
1274	State = setContainerData(State, ContReg,
1275	ContainerData::fromEnd(NewEndSym));
1276	}
1277	// Finally, replace the old "end" symbol in the already reassigned
1278	// iterator positions with the new "end" symbol.
1279	State = rebaseSymbolInIteratorPositionsIf(
1280	State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
1281	} else {
1282	// There was no "end" symbol assigned yet to the old container,
1283	// so reassign all iterator positions to the new container.
1284	State = reassignAllIteratorPositions(State, OldContReg, ContReg);
1285	}
1286	if (const auto OldBeginSym = OldCData->getBegin()) {
1287	// If we already assigned a "begin" symbol to the old container, then
1288	// assign it to the new container and remove it from the old one.
1289	if (CData) {
1290	State =
1291	setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
1292	} else {
1293	State = setContainerData(State, ContReg,
1294	ContainerData::fromBegin(OldBeginSym));
1295	}
1296	State =
1297	setContainerData(State, OldContReg, OldCData->newEnd(nullptr));
1298	}
1299	} else {
1300	// There was neither "begin" nor "end" symbol assigned yet to the old
1301	// container, so reassign all iterator positions to the new container.
1302	State = reassignAllIteratorPositions(State, OldContReg, ContReg);
1303	}
1304	}
1305	}
1306	C.addTransition(State);
1307	}
1308
1309	void IteratorChecker::handleClear(CheckerContext &C, const SVal &Cont) const {
1310	const auto *ContReg = Cont.getAsRegion();
1311	if (!ContReg)
1312	return;
1313
1314	ContReg = ContReg->getMostDerivedObjectRegion();
1315
1316	// The clear() operation invalidates all the iterators, except the past-end
1317	// iterators of list-like containers
1318	auto State = C.getState();
1319	if (!hasSubscriptOperator(State, ContReg) \|\|
1320	!backModifiable(State, ContReg)) {
1321	const auto CData = getContainerData(State, ContReg);
1322	if (CData) {
1323	if (const auto EndSym = CData->getEnd()) {
1324	State =
1325	invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
1326	C.addTransition(State);
1327	return;
1328	}
1329	}
1330	}
1331	State = invalidateAllIteratorPositions(State, ContReg);
1332	C.addTransition(State);
1333	}
1334
1335	void IteratorChecker::handlePushBack(CheckerContext &C,
1336	const SVal &Cont) const {
1337	const auto *ContReg = Cont.getAsRegion();
1338	if (!ContReg)
1339	return;
1340
1341	ContReg = ContReg->getMostDerivedObjectRegion();
1342
1343	// For deque-like containers invalidate all iterator positions
1344	auto State = C.getState();
1345	if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
1346	State = invalidateAllIteratorPositions(State, ContReg);
1347	C.addTransition(State);
1348	return;
1349	}
1350
1351	const auto CData = getContainerData(State, ContReg);
1352	if (!CData)
1353	return;
1354
1355	// For vector-like containers invalidate the past-end iterator positions
1356	if (const auto EndSym = CData->getEnd()) {
1357	if (hasSubscriptOperator(State, ContReg)) {
1358	State = invalidateIteratorPositions(State, EndSym, BO_GE);
1359	}
1360	auto &SymMgr = C.getSymbolManager();
1361	auto &BVF = SymMgr.getBasicVals();
1362	auto &SVB = C.getSValBuilder();
1363	const auto newEndSym =
1364	SVB.evalBinOp(State, BO_Add,
1365	nonloc::SymbolVal(EndSym),
1366	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1367	SymMgr.getType(EndSym)).getAsSymbol();
1368	State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
1369	}
1370	C.addTransition(State);
1371	}
1372
1373	void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const {
1374	const auto *ContReg = Cont.getAsRegion();
1375	if (!ContReg)
1376	return;
1377
1378	ContReg = ContReg->getMostDerivedObjectRegion();
1379
1380	auto State = C.getState();
1381	const auto CData = getContainerData(State, ContReg);
1382	if (!CData)
1383	return;
1384
1385	if (const auto EndSym = CData->getEnd()) {
1386	auto &SymMgr = C.getSymbolManager();
1387	auto &BVF = SymMgr.getBasicVals();
1388	auto &SVB = C.getSValBuilder();
1389	const auto BackSym =
1390	SVB.evalBinOp(State, BO_Sub,
1391	nonloc::SymbolVal(EndSym),
1392	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1393	SymMgr.getType(EndSym)).getAsSymbol();
1394	// For vector-like and deque-like containers invalidate the last and the
1395	// past-end iterator positions. For list-like containers only invalidate
1396	// the last position
1397	if (hasSubscriptOperator(State, ContReg) &&
1398	backModifiable(State, ContReg)) {
1399	State = invalidateIteratorPositions(State, BackSym, BO_GE);
1400	State = setContainerData(State, ContReg, CData->newEnd(nullptr));
1401	} else {
1402	State = invalidateIteratorPositions(State, BackSym, BO_EQ);
1403	}
1404	auto newEndSym = BackSym;
1405	State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
1406	C.addTransition(State);
1407	}
1408	}
1409
1410	void IteratorChecker::handlePushFront(CheckerContext &C,
1411	const SVal &Cont) const {
1412	const auto *ContReg = Cont.getAsRegion();
1413	if (!ContReg)
1414	return;
1415
1416	ContReg = ContReg->getMostDerivedObjectRegion();
1417
1418	// For deque-like containers invalidate all iterator positions
1419	auto State = C.getState();
1420	if (hasSubscriptOperator(State, ContReg)) {
1421	State = invalidateAllIteratorPositions(State, ContReg);
1422	C.addTransition(State);
1423	} else {
1424	const auto CData = getContainerData(State, ContReg);
1425	if (!CData)
1426	return;
1427
1428	if (const auto BeginSym = CData->getBegin()) {
1429	auto &SymMgr = C.getSymbolManager();
1430	auto &BVF = SymMgr.getBasicVals();
1431	auto &SVB = C.getSValBuilder();
1432	const auto newBeginSym =
1433	SVB.evalBinOp(State, BO_Sub,
1434	nonloc::SymbolVal(BeginSym),
1435	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1436	SymMgr.getType(BeginSym)).getAsSymbol();
1437	State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
1438	C.addTransition(State);
1439	}
1440	}
1441	}
1442
1443	void IteratorChecker::handlePopFront(CheckerContext &C,
1444	const SVal &Cont) const {
1445	const auto *ContReg = Cont.getAsRegion();
1446	if (!ContReg)
1447	return;
1448
1449	ContReg = ContReg->getMostDerivedObjectRegion();
1450
1451	auto State = C.getState();
1452	const auto CData = getContainerData(State, ContReg);
1453	if (!CData)
1454	return;
1455
1456	// For deque-like containers invalidate all iterator positions. For list-like
1457	// iterators only invalidate the first position
1458	if (const auto BeginSym = CData->getBegin()) {
1459	if (hasSubscriptOperator(State, ContReg)) {
1460	State = invalidateIteratorPositions(State, BeginSym, BO_LE);
1461	} else {
1462	State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
1463	}
1464	auto &SymMgr = C.getSymbolManager();
1465	auto &BVF = SymMgr.getBasicVals();
1466	auto &SVB = C.getSValBuilder();
1467	const auto newBeginSym =
1468	SVB.evalBinOp(State, BO_Add,
1469	nonloc::SymbolVal(BeginSym),
1470	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1471	SymMgr.getType(BeginSym)).getAsSymbol();
1472	State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
1473	C.addTransition(State);
1474	}
1475	}
1476
1477	void IteratorChecker::handleInsert(CheckerContext &C, const SVal &Iter) const {
1478	auto State = C.getState();
1479	const auto *Pos = getIteratorPosition(State, Iter);
1480	if (!Pos)
1481	return;
1482
1483	// For deque-like containers invalidate all iterator positions. For
1484	// vector-like containers invalidate iterator positions after the insertion.
1485	const auto *Cont = Pos->getContainer();
1486	if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1487	if (frontModifiable(State, Cont)) {
1488	State = invalidateAllIteratorPositions(State, Cont);
1489	} else {
1490	State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1491	}
1492	if (const auto *CData = getContainerData(State, Cont)) {
1493	if (const auto EndSym = CData->getEnd()) {
1494	State = invalidateIteratorPositions(State, EndSym, BO_GE);
1495	State = setContainerData(State, Cont, CData->newEnd(nullptr));
1496	}
1497	}
1498	C.addTransition(State);
1499	}
1500	}
1501
1502	void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter) const {
1503	auto State = C.getState();
1504	const auto *Pos = getIteratorPosition(State, Iter);
1505	if (!Pos)
1506	return;
1507
1508	// For deque-like containers invalidate all iterator positions. For
1509	// vector-like containers invalidate iterator positions at and after the
1510	// deletion. For list-like containers only invalidate the deleted position.
1511	const auto *Cont = Pos->getContainer();
1512	if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1513	if (frontModifiable(State, Cont)) {
1514	State = invalidateAllIteratorPositions(State, Cont);
1515	} else {
1516	State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1517	}
1518	if (const auto *CData = getContainerData(State, Cont)) {
1519	if (const auto EndSym = CData->getEnd()) {
1520	State = invalidateIteratorPositions(State, EndSym, BO_GE);
1521	State = setContainerData(State, Cont, CData->newEnd(nullptr));
1522	}
1523	}
1524	} else {
1525	State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
1526	}
1527	C.addTransition(State);
1528	}
1529
1530	void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter1,
1531	const SVal &Iter2) const {
1532	auto State = C.getState();
1533	const auto *Pos1 = getIteratorPosition(State, Iter1);
1534	const auto *Pos2 = getIteratorPosition(State, Iter2);
1535	if (!Pos1 \|\| !Pos2)
1536	return;
1537
1538	// For deque-like containers invalidate all iterator positions. For
1539	// vector-like containers invalidate iterator positions at and after the
1540	// deletion range. For list-like containers only invalidate the deleted
1541	// position range [first..last].
1542	const auto *Cont = Pos1->getContainer();
1543	if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1544	if (frontModifiable(State, Cont)) {
1545	State = invalidateAllIteratorPositions(State, Cont);
1546	} else {
1547	State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
1548	}
1549	if (const auto *CData = getContainerData(State, Cont)) {
1550	if (const auto EndSym = CData->getEnd()) {
1551	State = invalidateIteratorPositions(State, EndSym, BO_GE);
1552	State = setContainerData(State, Cont, CData->newEnd(nullptr));
1553	}
1554	}
1555	} else {
1556	State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
1557	Pos2->getOffset(), BO_LT);
1558	}
1559	C.addTransition(State);
1560	}
1561
1562	void IteratorChecker::handleEraseAfter(CheckerContext &C,
1563	const SVal &Iter) const {
1564	auto State = C.getState();
1565	const auto *Pos = getIteratorPosition(State, Iter);
1566	if (!Pos)
1567	return;
1568
1569	// Invalidate the deleted iterator position, which is the position of the
1570	// parameter plus one.
1571	auto &SymMgr = C.getSymbolManager();
1572	auto &BVF = SymMgr.getBasicVals();
1573	auto &SVB = C.getSValBuilder();
1574	const auto NextSym =
1575	SVB.evalBinOp(State, BO_Add,
1576	nonloc::SymbolVal(Pos->getOffset()),
1577	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1578	SymMgr.getType(Pos->getOffset())).getAsSymbol();
1579	State = invalidateIteratorPositions(State, NextSym, BO_EQ);
1580	C.addTransition(State);
1581	}
1582
1583	void IteratorChecker::handleEraseAfter(CheckerContext &C, const SVal &Iter1,
1584	const SVal &Iter2) const {
1585	auto State = C.getState();
1586	const auto *Pos1 = getIteratorPosition(State, Iter1);
1587	const auto *Pos2 = getIteratorPosition(State, Iter2);
1588	if (!Pos1 \|\| !Pos2)
1589	return;
1590
1591	// Invalidate the deleted iterator position range (first..last)
1592	State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
1593	Pos2->getOffset(), BO_LT);
1594	C.addTransition(State);
1595	}
1596
1597	IteratorPosition IteratorChecker::advancePosition(CheckerContext &C,
1598	OverloadedOperatorKind Op,
1599	const IteratorPosition &Pos,
1600	const SVal &Distance) const {
1601	auto State = C.getState();
1602	auto &SymMgr = C.getSymbolManager();
1603	auto &SVB = C.getSValBuilder();
1604
1605	(0) . __assert_fail ("(Op == OO_Plus \|\| Op == OO_PlusEqual \|\| Op == OO_Minus \|\| Op == OO_MinusEqual) && \"Advance operator must be one of +, -, += and -=.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 1607, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert ((Op == OO_Plus \|\| Op == OO_PlusEqual \|\|
1606	(0) . __assert_fail ("(Op == OO_Plus \|\| Op == OO_PlusEqual \|\| Op == OO_Minus \|\| Op == OO_MinusEqual) && \"Advance operator must be one of +, -, += and -=.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 1607, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> Op == OO_Minus \|\| Op == OO_MinusEqual) &&
1607	(0) . __assert_fail ("(Op == OO_Plus \|\| Op == OO_PlusEqual \|\| Op == OO_Minus \|\| Op == OO_MinusEqual) && \"Advance operator must be one of +, -, += and -=.\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 1607, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Advance operator must be one of +, -, += and -=.");
1608	auto BinOp = (Op == OO_Plus \|\| Op == OO_PlusEqual) ? BO_Add : BO_Sub;
1609	if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) {
1610	// For concrete integers we can calculate the new position
1611	return Pos.setTo(SVB.evalBinOp(State, BinOp,
1612	nonloc::SymbolVal(Pos.getOffset()), *IntDist,
1613	SymMgr.getType(Pos.getOffset()))
1614	.getAsSymbol());
1615	} else {
1616	// For other symbols create a new symbol to keep expressions simple
1617	const auto &LCtx = C.getLocationContext();
1618	const auto NewPosSym = SymMgr.conjureSymbol(nullptr, LCtx,
1619	SymMgr.getType(Pos.getOffset()),
1620	C.blockCount());
1621	State = assumeNoOverflow(State, NewPosSym, 4);
1622	return Pos.setTo(NewPosSym);
1623	}
1624	}
1625
1626	void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
1627	const SVal &Val, CheckerContext &C,
1628	ExplodedNode *ErrNode) const {
1629	auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
1630	R->markInteresting(Val);
1631	C.emitReport(std::move(R));
1632	}
1633
1634	void IteratorChecker::reportMismatchedBug(const StringRef &Message,
1635	const SVal &Val1, const SVal &Val2,
1636	CheckerContext &C,
1637	ExplodedNode *ErrNode) const {
1638	auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
1639	R->markInteresting(Val1);
1640	R->markInteresting(Val2);
1641	C.emitReport(std::move(R));
1642	}
1643
1644	void IteratorChecker::reportMismatchedBug(const StringRef &Message,
1645	const SVal &Val, const MemRegion *Reg,
1646	CheckerContext &C,
1647	ExplodedNode *ErrNode) const {
1648	auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
1649	R->markInteresting(Val);
1650	R->markInteresting(Reg);
1651	C.emitReport(std::move(R));
1652	}
1653
1654	void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
1655	const SVal &Val, CheckerContext &C,
1656	ExplodedNode *ErrNode) const {
1657	auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
1658	R->markInteresting(Val);
1659	C.emitReport(std::move(R));
1660	}
1661
1662	namespace {
1663
1664	bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
1665	bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
1666	bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
1667	bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
1668	BinaryOperator::Opcode Opc);
1669	bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
1670	BinaryOperator::Opcode Opc);
1671	const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1672	const MemRegion *Reg);
1673	SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
1674	SymbolRef OldSym, SymbolRef NewSym);
1675
1676	bool isIteratorType(const QualType &Type) {
1677	if (Type->isPointerType())
1678	return true;
1679
1680	const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
1681	return isIterator(CRD);
1682	}
1683
1684	bool isIterator(const CXXRecordDecl *CRD) {
1685	if (!CRD)
1686	return false;
1687
1688	const auto Name = CRD->getName();
1689	if (!(Name.endswith_lower("iterator") \|\| Name.endswith_lower("iter") \|\|
1690	Name.endswith_lower("it")))
1691	return false;
1692
1693	bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
1694	HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
1695	for (const auto *Method : CRD->methods()) {
1696	if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
1697	if (Ctor->isCopyConstructor()) {
1698	HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
1699	}
1700	continue;
1701	}
1702	if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
1703	HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
1704	continue;
1705	}
1706	if (Method->isCopyAssignmentOperator()) {
1707	HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
1708	continue;
1709	}
1710	if (!Method->isOverloadedOperator())
1711	continue;
1712	const auto OPK = Method->getOverloadedOperator();
1713	if (OPK == OO_PlusPlus) {
1714	HasPreIncrOp = HasPreIncrOp \|\| (Method->getNumParams() == 0);
1715	HasPostIncrOp = HasPostIncrOp \|\| (Method->getNumParams() == 1);
1716	continue;
1717	}
1718	if (OPK == OO_Star) {
1719	HasDerefOp = (Method->getNumParams() == 0);
1720	continue;
1721	}
1722	}
1723
1724	return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
1725	HasPostIncrOp && HasDerefOp;
1726	}
1727
1728	bool isComparisonOperator(OverloadedOperatorKind OK) {
1729	return OK == OO_EqualEqual \|\| OK == OO_ExclaimEqual \|\| OK == OO_Less \|\|
1730	OK == OO_LessEqual \|\| OK == OO_Greater \|\| OK == OO_GreaterEqual;
1731	}
1732
1733	bool isBeginCall(const FunctionDecl *Func) {
1734	const auto *IdInfo = Func->getIdentifier();
1735	if (!IdInfo)
1736	return false;
1737	return IdInfo->getName().endswith_lower("begin");
1738	}
1739
1740	bool isEndCall(const FunctionDecl *Func) {
1741	const auto *IdInfo = Func->getIdentifier();
1742	if (!IdInfo)
1743	return false;
1744	return IdInfo->getName().endswith_lower("end");
1745	}
1746
1747	bool isAssignCall(const FunctionDecl *Func) {
1748	const auto *IdInfo = Func->getIdentifier();
1749	if (!IdInfo)
1750	return false;
1751	if (Func->getNumParams() > 2)
1752	return false;
1753	return IdInfo->getName() == "assign";
1754	}
1755
1756	bool isClearCall(const FunctionDecl *Func) {
1757	const auto *IdInfo = Func->getIdentifier();
1758	if (!IdInfo)
1759	return false;
1760	if (Func->getNumParams() > 0)
1761	return false;
1762	return IdInfo->getName() == "clear";
1763	}
1764
1765	bool isPushBackCall(const FunctionDecl *Func) {
1766	const auto *IdInfo = Func->getIdentifier();
1767	if (!IdInfo)
1768	return false;
1769	if (Func->getNumParams() != 1)
1770	return false;
1771	return IdInfo->getName() == "push_back";
1772	}
1773
1774	bool isEmplaceBackCall(const FunctionDecl *Func) {
1775	const auto *IdInfo = Func->getIdentifier();
1776	if (!IdInfo)
1777	return false;
1778	if (Func->getNumParams() < 1)
1779	return false;
1780	return IdInfo->getName() == "emplace_back";
1781	}
1782
1783	bool isPopBackCall(const FunctionDecl *Func) {
1784	const auto *IdInfo = Func->getIdentifier();
1785	if (!IdInfo)
1786	return false;
1787	if (Func->getNumParams() > 0)
1788	return false;
1789	return IdInfo->getName() == "pop_back";
1790	}
1791
1792	bool isPushFrontCall(const FunctionDecl *Func) {
1793	const auto *IdInfo = Func->getIdentifier();
1794	if (!IdInfo)
1795	return false;
1796	if (Func->getNumParams() != 1)
1797	return false;
1798	return IdInfo->getName() == "push_front";
1799	}
1800
1801	bool isEmplaceFrontCall(const FunctionDecl *Func) {
1802	const auto *IdInfo = Func->getIdentifier();
1803	if (!IdInfo)
1804	return false;
1805	if (Func->getNumParams() < 1)
1806	return false;
1807	return IdInfo->getName() == "emplace_front";
1808	}
1809
1810	bool isPopFrontCall(const FunctionDecl *Func) {
1811	const auto *IdInfo = Func->getIdentifier();
1812	if (!IdInfo)
1813	return false;
1814	if (Func->getNumParams() > 0)
1815	return false;
1816	return IdInfo->getName() == "pop_front";
1817	}
1818
1819	bool isInsertCall(const FunctionDecl *Func) {
1820	const auto *IdInfo = Func->getIdentifier();
1821	if (!IdInfo)
1822	return false;
1823	if (Func->getNumParams() < 2 \|\| Func->getNumParams() > 3)
1824	return false;
1825	if (!isIteratorType(Func->getParamDecl(0)->getType()))
1826	return false;
1827	return IdInfo->getName() == "insert";
1828	}
1829
1830	bool isEmplaceCall(const FunctionDecl *Func) {
1831	const auto *IdInfo = Func->getIdentifier();
1832	if (!IdInfo)
1833	return false;
1834	if (Func->getNumParams() < 2)
1835	return false;
1836	if (!isIteratorType(Func->getParamDecl(0)->getType()))
1837	return false;
1838	return IdInfo->getName() == "emplace";
1839	}
1840
1841	bool isEraseCall(const FunctionDecl *Func) {
1842	const auto *IdInfo = Func->getIdentifier();
1843	if (!IdInfo)
1844	return false;
1845	if (Func->getNumParams() < 1 \|\| Func->getNumParams() > 2)
1846	return false;
1847	if (!isIteratorType(Func->getParamDecl(0)->getType()))
1848	return false;
1849	if (Func->getNumParams() == 2 &&
1850	!isIteratorType(Func->getParamDecl(1)->getType()))
1851	return false;
1852	return IdInfo->getName() == "erase";
1853	}
1854
1855	bool isEraseAfterCall(const FunctionDecl *Func) {
1856	const auto *IdInfo = Func->getIdentifier();
1857	if (!IdInfo)
1858	return false;
1859	if (Func->getNumParams() < 1 \|\| Func->getNumParams() > 2)
1860	return false;
1861	if (!isIteratorType(Func->getParamDecl(0)->getType()))
1862	return false;
1863	if (Func->getNumParams() == 2 &&
1864	!isIteratorType(Func->getParamDecl(1)->getType()))
1865	return false;
1866	return IdInfo->getName() == "erase_after";
1867	}
1868
1869	bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
1870
1871	bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
1872	return OK == OO_EqualEqual \|\| OK == OO_ExclaimEqual;
1873	}
1874
1875	bool isAccessOperator(OverloadedOperatorKind OK) {
1876	return isDereferenceOperator(OK) \|\| isIncrementOperator(OK) \|\|
1877	isDecrementOperator(OK) \|\| isRandomIncrOrDecrOperator(OK);
1878	}
1879
1880	bool isDereferenceOperator(OverloadedOperatorKind OK) {
1881	return OK == OO_Star \|\| OK == OO_Arrow \|\| OK == OO_ArrowStar \|\|
1882	OK == OO_Subscript;
1883	}
1884
1885	bool isIncrementOperator(OverloadedOperatorKind OK) {
1886	return OK == OO_PlusPlus;
1887	}
1888
1889	bool isDecrementOperator(OverloadedOperatorKind OK) {
1890	return OK == OO_MinusMinus;
1891	}
1892
1893	bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
1894	return OK == OO_Plus \|\| OK == OO_PlusEqual \|\| OK == OO_Minus \|\|
1895	OK == OO_MinusEqual;
1896	}
1897
1898	BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
1899	if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
1900	return BSE->getOpcode();
1901	} else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
1902	const auto *COE = dyn_cast_or_null<CXXOperatorCallExpr>(SC->getStmt());
1903	if (!COE)
1904	return BO_Comma; // Extremal value, neither EQ nor NE
1905	if (COE->getOperator() == OO_EqualEqual) {
1906	return BO_EQ;
1907	} else if (COE->getOperator() == OO_ExclaimEqual) {
1908	return BO_NE;
1909	}
1910	return BO_Comma; // Extremal value, neither EQ nor NE
1911	}
1912	return BO_Comma; // Extremal value, neither EQ nor NE
1913	}
1914
1915	bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
1916	const auto *CRD = getCXXRecordDecl(State, Reg);
1917	if (!CRD)
1918	return false;
1919
1920	for (const auto *Method : CRD->methods()) {
1921	if (!Method->isOverloadedOperator())
1922	continue;
1923	const auto OPK = Method->getOverloadedOperator();
1924	if (OPK == OO_Subscript) {
1925	return true;
1926	}
1927	}
1928	return false;
1929	}
1930
1931	bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
1932	const auto *CRD = getCXXRecordDecl(State, Reg);
1933	if (!CRD)
1934	return false;
1935
1936	for (const auto *Method : CRD->methods()) {
1937	if (!Method->getDeclName().isIdentifier())
1938	continue;
1939	if (Method->getName() == "push_front" \|\| Method->getName() == "pop_front") {
1940	return true;
1941	}
1942	}
1943	return false;
1944	}
1945
1946	bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
1947	const auto *CRD = getCXXRecordDecl(State, Reg);
1948	if (!CRD)
1949	return false;
1950
1951	for (const auto *Method : CRD->methods()) {
1952	if (!Method->getDeclName().isIdentifier())
1953	continue;
1954	if (Method->getName() == "push_back" \|\| Method->getName() == "pop_back") {
1955	return true;
1956	}
1957	}
1958	return false;
1959	}
1960
1961	const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1962	const MemRegion *Reg) {
1963	auto TI = getDynamicTypeInfo(State, Reg);
1964	if (!TI.isValid())
1965	return nullptr;
1966
1967	auto Type = TI.getType();
1968	if (const auto *RefT = Type->getAs<ReferenceType>()) {
1969	Type = RefT->getPointeeType();
1970	}
1971
1972	return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
1973	}
1974
1975	const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
1976	if (const auto Reg = Val.getAsRegion()) {
1977	return Reg;
1978	} else if (const auto Sym = Val.getAsSymbol()) {
1979	return Sym;
1980	} else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1981	return LCVal->getRegion();
1982	}
1983	return RegionOrSymbol();
1984	}
1985
1986	const ProgramStateRef processComparison(ProgramStateRef State,
1987	RegionOrSymbol LVal,
1988	RegionOrSymbol RVal, bool Equal) {
1989	const auto *LPos = getIteratorPosition(State, LVal);
1990	const auto *RPos = getIteratorPosition(State, RVal);
1991	if (LPos && !RPos) {
1992	State = adjustIteratorPosition(State, RVal, *LPos, Equal);
1993	} else if (!LPos && RPos) {
1994	State = adjustIteratorPosition(State, LVal, *RPos, Equal);
1995	} else if (LPos && RPos) {
1996	State = relateIteratorPositions(State, LPos, RPos, Equal);
1997	}
1998	return State;
1999	}
2000
2001	const ProgramStateRef saveComparison(ProgramStateRef State,
2002	const SymExpr *Condition, const SVal &LVal,
2003	const SVal &RVal, bool Eq) {
2004	const auto Left = getRegionOrSymbol(LVal);
2005	const auto Right = getRegionOrSymbol(RVal);
2006	if (!Left \|\| !Right)
2007	return State;
2008	return State->set<IteratorComparisonMap>(Condition,
2009	IteratorComparison(Left, Right, Eq));
2010	}
2011
2012	const IteratorComparison *loadComparison(ProgramStateRef State,
2013	const SymExpr *Condition) {
2014	return State->get<IteratorComparisonMap>(Condition);
2015	}
2016
2017	SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
2018	const auto *CDataPtr = getContainerData(State, Cont);
2019	if (!CDataPtr)
2020	return nullptr;
2021
2022	return CDataPtr->getBegin();
2023	}
2024
2025	SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
2026	const auto *CDataPtr = getContainerData(State, Cont);
2027	if (!CDataPtr)
2028	return nullptr;
2029
2030	return CDataPtr->getEnd();
2031	}
2032
2033	ProgramStateRef createContainerBegin(ProgramStateRef State,
2034	const MemRegion *Cont,
2035	const SymbolRef Sym) {
2036	// Only create if it does not exist
2037	const auto *CDataPtr = getContainerData(State, Cont);
2038	if (CDataPtr) {
2039	if (CDataPtr->getBegin()) {
2040	return State;
2041	}
2042	const auto CData = CDataPtr->newBegin(Sym);
2043	return setContainerData(State, Cont, CData);
2044	}
2045	const auto CData = ContainerData::fromBegin(Sym);
2046	return setContainerData(State, Cont, CData);
2047	}
2048
2049	ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
2050	const SymbolRef Sym) {
2051	// Only create if it does not exist
2052	const auto *CDataPtr = getContainerData(State, Cont);
2053	if (CDataPtr) {
2054	if (CDataPtr->getEnd()) {
2055	return State;
2056	}
2057	const auto CData = CDataPtr->newEnd(Sym);
2058	return setContainerData(State, Cont, CData);
2059	}
2060	const auto CData = ContainerData::fromEnd(Sym);
2061	return setContainerData(State, Cont, CData);
2062	}
2063
2064	const ContainerData *getContainerData(ProgramStateRef State,
2065	const MemRegion *Cont) {
2066	return State->get<ContainerMap>(Cont);
2067	}
2068
2069	ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
2070	const ContainerData &CData) {
2071	return State->set<ContainerMap>(Cont, CData);
2072	}
2073
2074	const IteratorPosition *getIteratorPosition(ProgramStateRef State,
2075	const SVal &Val) {
2076	if (auto Reg = Val.getAsRegion()) {
2077	Reg = Reg->getMostDerivedObjectRegion();
2078	return State->get<IteratorRegionMap>(Reg);
2079	} else if (const auto Sym = Val.getAsSymbol()) {
2080	return State->get<IteratorSymbolMap>(Sym);
2081	} else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2082	return State->get<IteratorRegionMap>(LCVal->getRegion());
2083	}
2084	return nullptr;
2085	}
2086
2087	const IteratorPosition *getIteratorPosition(ProgramStateRef State,
2088	RegionOrSymbol RegOrSym) {
2089	if (RegOrSym.is<const MemRegion *>()) {
2090	auto Reg = RegOrSym.get<const MemRegion *>()->getMostDerivedObjectRegion();
2091	return State->get<IteratorRegionMap>(Reg);
2092	} else if (RegOrSym.is<SymbolRef>()) {
2093	return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
2094	}
2095	return nullptr;
2096	}
2097
2098	ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
2099	const IteratorPosition &Pos) {
2100	if (auto Reg = Val.getAsRegion()) {
2101	Reg = Reg->getMostDerivedObjectRegion();
2102	return State->set<IteratorRegionMap>(Reg, Pos);
2103	} else if (const auto Sym = Val.getAsSymbol()) {
2104	return State->set<IteratorSymbolMap>(Sym, Pos);
2105	} else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2106	return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
2107	}
2108	return nullptr;
2109	}
2110
2111	ProgramStateRef setIteratorPosition(ProgramStateRef State,
2112	RegionOrSymbol RegOrSym,
2113	const IteratorPosition &Pos) {
2114	if (RegOrSym.is<const MemRegion *>()) {
2115	auto Reg = RegOrSym.get<const MemRegion *>()->getMostDerivedObjectRegion();
2116	return State->set<IteratorRegionMap>(Reg, Pos);
2117	} else if (RegOrSym.is<SymbolRef>()) {
2118	return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
2119	}
2120	return nullptr;
2121	}
2122
2123	ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
2124	if (auto Reg = Val.getAsRegion()) {
2125	Reg = Reg->getMostDerivedObjectRegion();
2126	return State->remove<IteratorRegionMap>(Reg);
2127	} else if (const auto Sym = Val.getAsSymbol()) {
2128	return State->remove<IteratorSymbolMap>(Sym);
2129	} else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2130	return State->remove<IteratorRegionMap>(LCVal->getRegion());
2131	}
2132	return nullptr;
2133	}
2134
2135	ProgramStateRef adjustIteratorPosition(ProgramStateRef State,
2136	RegionOrSymbol RegOrSym,
2137	const IteratorPosition &Pos,
2138	bool Equal) {
2139	if (Equal) {
2140	return setIteratorPosition(State, RegOrSym, Pos);
2141	} else {
2142	return State;
2143	}
2144	}
2145
2146	ProgramStateRef relateIteratorPositions(ProgramStateRef State,
2147	const IteratorPosition &Pos1,
2148	const IteratorPosition &Pos2,
2149	bool Equal) {
2150	auto &SVB = State->getStateManager().getSValBuilder();
2151
2152	// FIXME: This code should be reworked as follows:
2153	// 1. Subtract the operands using evalBinOp().
2154	// 2. Assume that the result doesn't overflow.
2155	// 3. Compare the result to 0.
2156	// 4. Assume the result of the comparison.
2157	const auto comparison =
2158	SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
2159	nonloc::SymbolVal(Pos2.getOffset()),
2160	SVB.getConditionType());
2161
2162	(0) . __assert_fail ("comparison.getAs() && \"Symbol comparison must be a `DefinedSVal`\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2163, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(comparison.getAs<DefinedSVal>() &&
2163	(0) . __assert_fail ("comparison.getAs() && \"Symbol comparison must be a `DefinedSVal`\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2163, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Symbol comparison must be a `DefinedSVal`");
2164
2165	auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
2166	if (const auto CompSym = comparison.getAsSymbol()) {
2167	(0) . __assert_fail ("isa(CompSym) && \"Symbol comparison must be a `SymIntExpr`\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2168, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(isa<SymIntExpr>(CompSym) &&
2168	(0) . __assert_fail ("isa(CompSym) && \"Symbol comparison must be a `SymIntExpr`\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2168, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Symbol comparison must be a `SymIntExpr`");
2169	(0) . __assert_fail ("BinaryOperator..isComparisonOp( cast(CompSym)->getOpcode()) && \"Symbol comparison must be a comparison\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2171, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(BinaryOperator::isComparisonOp(
2170	(0) . __assert_fail ("BinaryOperator..isComparisonOp( cast(CompSym)->getOpcode()) && \"Symbol comparison must be a comparison\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2171, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> cast<SymIntExpr>(CompSym)->getOpcode()) &&
2171	(0) . __assert_fail ("BinaryOperator..isComparisonOp( cast(CompSym)->getOpcode()) && \"Symbol comparison must be a comparison\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2171, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Symbol comparison must be a comparison");
2172	return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
2173	}
2174
2175	return NewState;
2176	}
2177
2178	bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
2179	auto RegionMap = State->get<IteratorRegionMap>();
2180	for (const auto Reg : RegionMap) {
2181	if (Reg.second.getContainer() == Cont)
2182	return true;
2183	}
2184
2185	auto SymbolMap = State->get<IteratorSymbolMap>();
2186	for (const auto Sym : SymbolMap) {
2187	if (Sym.second.getContainer() == Cont)
2188	return true;
2189	}
2190
2191	return false;
2192	}
2193
2194	bool isBoundThroughLazyCompoundVal(const Environment &Env,
2195	const MemRegion *Reg) {
2196	for (const auto Binding: Env) {
2197	if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
2198	if (LCVal->getRegion() == Reg)
2199	return true;
2200	}
2201	}
2202
2203	return false;
2204	}
2205
2206	template <typename Condition, typename Process>
2207	ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
2208	Process Proc) {
2209	auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
2210	auto RegionMap = State->get<IteratorRegionMap>();
2211	bool Changed = false;
2212	for (const auto Reg : RegionMap) {
2213	if (Cond(Reg.second)) {
2214	RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
2215	Changed = true;
2216	}
2217	}
2218
2219	if (Changed)
2220	State = State->set<IteratorRegionMap>(RegionMap);
2221
2222	auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
2223	auto SymbolMap = State->get<IteratorSymbolMap>();
2224	Changed = false;
2225	for (const auto Sym : SymbolMap) {
2226	if (Cond(Sym.second)) {
2227	SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
2228	Changed = true;
2229	}
2230	}
2231
2232	if (Changed)
2233	State = State->set<IteratorSymbolMap>(SymbolMap);
2234
2235	return State;
2236	}
2237
2238	ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
2239	const MemRegion *Cont) {
2240	auto MatchCont = [&](const IteratorPosition &Pos) {
2241	return Pos.getContainer() == Cont;
2242	};
2243	auto Invalidate = [&](const IteratorPosition &Pos) {
2244	return Pos.invalidate();
2245	};
2246	return processIteratorPositions(State, MatchCont, Invalidate);
2247	}
2248
2249	ProgramStateRef
2250	invalidateAllIteratorPositionsExcept(ProgramStateRef State,
2251	const MemRegion *Cont, SymbolRef Offset,
2252	BinaryOperator::Opcode Opc) {
2253	auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
2254	return Pos.getContainer() == Cont &&
2255	!compare(State, Pos.getOffset(), Offset, Opc);
2256	};
2257	auto Invalidate = [&](const IteratorPosition &Pos) {
2258	return Pos.invalidate();
2259	};
2260	return processIteratorPositions(State, MatchContAndCompare, Invalidate);
2261	}
2262
2263	ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
2264	SymbolRef Offset,
2265	BinaryOperator::Opcode Opc) {
2266	auto Compare = [&](const IteratorPosition &Pos) {
2267	return compare(State, Pos.getOffset(), Offset, Opc);
2268	};
2269	auto Invalidate = [&](const IteratorPosition &Pos) {
2270	return Pos.invalidate();
2271	};
2272	return processIteratorPositions(State, Compare, Invalidate);
2273	}
2274
2275	ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
2276	SymbolRef Offset1,
2277	BinaryOperator::Opcode Opc1,
2278	SymbolRef Offset2,
2279	BinaryOperator::Opcode Opc2) {
2280	auto Compare = [&](const IteratorPosition &Pos) {
2281	return compare(State, Pos.getOffset(), Offset1, Opc1) &&
2282	compare(State, Pos.getOffset(), Offset2, Opc2);
2283	};
2284	auto Invalidate = [&](const IteratorPosition &Pos) {
2285	return Pos.invalidate();
2286	};
2287	return processIteratorPositions(State, Compare, Invalidate);
2288	}
2289
2290	ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
2291	const MemRegion *Cont,
2292	const MemRegion *NewCont) {
2293	auto MatchCont = [&](const IteratorPosition &Pos) {
2294	return Pos.getContainer() == Cont;
2295	};
2296	auto ReAssign = [&](const IteratorPosition &Pos) {
2297	return Pos.reAssign(NewCont);
2298	};
2299	return processIteratorPositions(State, MatchCont, ReAssign);
2300	}
2301
2302	ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
2303	const MemRegion *Cont,
2304	const MemRegion *NewCont,
2305	SymbolRef Offset,
2306	BinaryOperator::Opcode Opc) {
2307	auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
2308	return Pos.getContainer() == Cont &&
2309	!compare(State, Pos.getOffset(), Offset, Opc);
2310	};
2311	auto ReAssign = [&](const IteratorPosition &Pos) {
2312	return Pos.reAssign(NewCont);
2313	};
2314	return processIteratorPositions(State, MatchContAndCompare, ReAssign);
2315	}
2316
2317	// This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
2318	// `OldSym - Int` to `NewSym - Int` and `OldSym` to `NewSym` in any iterator
2319	// position offsets where `CondSym` is true.
2320	ProgramStateRef rebaseSymbolInIteratorPositionsIf(
2321	ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
2322	SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
2323	auto LessThanEnd = [&](const IteratorPosition &Pos) {
2324	return compare(State, Pos.getOffset(), CondSym, Opc);
2325	};
2326	auto RebaseSymbol = [&](const IteratorPosition &Pos) {
2327	return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
2328	NewSym));
2329	};
2330	return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
2331	}
2332
2333	// This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
2334	// `OldExpr - Int` to `NewExpr - Int` and `OldExpr` to `NewExpr` in expression
2335	// `OrigExpr`.
2336	SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
2337	SymbolRef OrigExpr, SymbolRef OldExpr,
2338	SymbolRef NewSym) {
2339	auto &SymMgr = SVB.getSymbolManager();
2340	auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
2341	nonloc::SymbolVal(OldExpr),
2342	SymMgr.getType(OrigExpr));
2343
2344	const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
2345	if (!DiffInt)
2346	return OrigExpr;
2347
2348	return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
2349	SymMgr.getType(OrigExpr)).getAsSymbol();
2350	}
2351
2352	bool isZero(ProgramStateRef State, const NonLoc &Val) {
2353	auto &BVF = State->getBasicVals();
2354	return compare(State, Val,
2355	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
2356	BO_EQ);
2357	}
2358
2359	bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
2360	const auto *Cont = Pos.getContainer();
2361	const auto *CData = getContainerData(State, Cont);
2362	if (!CData)
2363	return false;
2364
2365	const auto End = CData->getEnd();
2366	if (End) {
2367	if (isEqual(State, Pos.getOffset(), End)) {
2368	return true;
2369	}
2370	}
2371
2372	return false;
2373	}
2374
2375	bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
2376	const auto *Cont = Pos.getContainer();
2377	const auto *CData = getContainerData(State, Cont);
2378	if (!CData)
2379	return false;
2380
2381	const auto Beg = CData->getBegin();
2382	if (Beg) {
2383	if (isLess(State, Pos.getOffset(), Beg)) {
2384	return true;
2385	}
2386	}
2387
2388	return false;
2389	}
2390
2391	bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
2392	const auto *Cont = Pos.getContainer();
2393	const auto *CData = getContainerData(State, Cont);
2394	if (!CData)
2395	return false;
2396
2397	const auto End = CData->getEnd();
2398	if (End) {
2399	if (isGreater(State, Pos.getOffset(), End)) {
2400	return true;
2401	}
2402	}
2403
2404	return false;
2405	}
2406
2407	bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
2408	return compare(State, Sym1, Sym2, BO_LT);
2409	}
2410
2411	bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
2412	return compare(State, Sym1, Sym2, BO_GT);
2413	}
2414
2415	bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
2416	return compare(State, Sym1, Sym2, BO_EQ);
2417	}
2418
2419	bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
2420	BinaryOperator::Opcode Opc) {
2421	return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
2422	}
2423
2424	bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
2425	BinaryOperator::Opcode Opc) {
2426	auto &SVB = State->getStateManager().getSValBuilder();
2427
2428	const auto comparison =
2429	SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
2430
2431	(0) . __assert_fail ("comparison.getAs() && \"Symbol comparison must be a `DefinedSVal`\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2432, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true">assert(comparison.getAs<DefinedSVal>() &&
2432	(0) . __assert_fail ("comparison.getAs() && \"Symbol comparison must be a `DefinedSVal`\"", "/home/seafit/code_projects/clang_source/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp", 2432, __PRETTY_FUNCTION__))" file_link="../../../../include/assert.h.html#88" macro="true"> "Symbol comparison must be a `DefinedSVal`");
2433
2434	return !State->assume(comparison.castAs<DefinedSVal>(), false);
2435	}
2436
2437	} // namespace
2438
2439	void ento::registerIteratorModeling(CheckerManager &mgr) {
2440	mgr.registerChecker<IteratorChecker>();
2441	}
2442
2443	bool ento::shouldRegisterIteratorModeling(const LangOptions &LO) {
2444	return true;
2445	}
2446
2447	#define REGISTER_CHECKER(name) \
2448	void ento::register##name(CheckerManager &Mgr) { \
2449	auto *checker = Mgr.getChecker<IteratorChecker>(); \
2450	checker->ChecksEnabled[IteratorChecker::CK_##name] = true; \
2451	checker->CheckNames[IteratorChecker::CK_##name] = \
2452	Mgr.getCurrentCheckName(); \
2453	} \
2454	\
2455	bool ento::shouldRegister##name(const LangOptions &LO) { \
2456	return true; \
2457	}
2458
2459	REGISTER_CHECKER(IteratorRangeChecker)
2460	REGISTER_CHECKER(MismatchedIteratorChecker)
2461	REGISTER_CHECKER(InvalidatedIteratorChecker)
2462

Clang Project