Coverage Report

Created: 2019-07-24 05:18

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