Coverage Report

Created: 2022-01-18 06:27

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- ContainerModeling.cpp -------------------------------------*- C++ -*--//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// Defines a modeling-checker for modeling STL container-like containers.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "clang/AST/DeclTemplate.h"
14
#include "clang/Driver/DriverDiagnostic.h"
15
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17
#include "clang/StaticAnalyzer/Core/Checker.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
19
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
20
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
21
#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
22
23
#include "Iterator.h"
24
25
#include <utility>
26
27
using namespace clang;
28
using namespace ento;
29
using namespace iterator;
30
31
namespace {
32
33
class ContainerModeling
34
  : public Checker<check::PostCall, check::LiveSymbols, check::DeadSymbols> {
35
36
  void handleBegin(CheckerContext &C, const Expr *CE, SVal RetVal,
37
                   SVal Cont) const;
38
  void handleEnd(CheckerContext &C, const Expr *CE, SVal RetVal,
39
                 SVal Cont) const;
40
  void handleAssignment(CheckerContext &C, SVal Cont, const Expr *CE = nullptr,
41
                        SVal OldCont = UndefinedVal()) const;
42
  void handleAssign(CheckerContext &C, SVal Cont, const Expr *ContE) const;
43
  void handleClear(CheckerContext &C, SVal Cont, const Expr *ContE) const;
44
  void handlePushBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
45
  void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
46
  void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
47
  void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
48
  void handleInsert(CheckerContext &C, SVal Cont, SVal Iter) const;
49
  void handleErase(CheckerContext &C, SVal Cont, SVal Iter) const;
50
  void handleErase(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2) const;
51
  void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter) const;
52
  void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter1,
53
                        SVal Iter2) const;
54
  const NoteTag *getChangeTag(CheckerContext &C, StringRef Text,
55
                              const MemRegion *ContReg,
56
                              const Expr *ContE) const;
57
  void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
58
                  const char *Sep) const override;
59
60
public:
61
21
  ContainerModeling() = default;
62
63
  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
64
  void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
65
  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
66
67
  using NoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
68
                                                  const Expr *) const;
69
  using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
70
                                                   SVal) const;
71
  using TwoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal,
72
                                                   SVal) const;
73
74
  CallDescriptionMap<NoItParamFn> NoIterParamFunctions = {
75
      {{"clear", 0}, &ContainerModeling::handleClear},
76
      {{"assign", 2}, &ContainerModeling::handleAssign},
77
      {{"push_back", 1}, &ContainerModeling::handlePushBack},
78
      {{"emplace_back", 1}, &ContainerModeling::handlePushBack},
79
      {{"pop_back", 0}, &ContainerModeling::handlePopBack},
80
      {{"push_front", 1}, &ContainerModeling::handlePushFront},
81
      {{"emplace_front", 1}, &ContainerModeling::handlePushFront},
82
      {{"pop_front", 0}, &ContainerModeling::handlePopFront},
83
  };
84
85
  CallDescriptionMap<OneItParamFn> OneIterParamFunctions = {
86
      {{"insert", 2}, &ContainerModeling::handleInsert},
87
      {{"emplace", 2}, &ContainerModeling::handleInsert},
88
      {{"erase", 1}, &ContainerModeling::handleErase},
89
      {{"erase_after", 1}, &ContainerModeling::handleEraseAfter},
90
  };
91
92
  CallDescriptionMap<TwoItParamFn> TwoIterParamFunctions = {
93
      {{"erase", 2}, &ContainerModeling::handleErase},
94
      {{"erase_after", 2}, &ContainerModeling::handleEraseAfter},
95
  };
96
};
97
98
bool isBeginCall(const FunctionDecl *Func);
99
bool isEndCall(const FunctionDecl *Func);
100
bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
101
bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
102
bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
103
SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
104
SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
105
ProgramStateRef createContainerBegin(ProgramStateRef State,
106
                                     const MemRegion *Cont, const Expr *E,
107
                                     QualType T, const LocationContext *LCtx,
108
                                     unsigned BlockCount);
109
ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
110
                                   const Expr *E, QualType T,
111
                                   const LocationContext *LCtx,
112
                                   unsigned BlockCount);
113
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
114
                                 const ContainerData &CData);
115
ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
116
                                               const MemRegion *Cont);
117
ProgramStateRef
118
invalidateAllIteratorPositionsExcept(ProgramStateRef State,
119
                                     const MemRegion *Cont, SymbolRef Offset,
120
                                     BinaryOperator::Opcode Opc);
121
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
122
                                            SymbolRef Offset,
123
                                            BinaryOperator::Opcode Opc);
124
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
125
                                            SymbolRef Offset1,
126
                                            BinaryOperator::Opcode Opc1,
127
                                            SymbolRef Offset2,
128
                                            BinaryOperator::Opcode Opc2);
129
ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
130
                                             const MemRegion *Cont,
131
                                             const MemRegion *NewCont);
132
ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
133
                                                   const MemRegion *Cont,
134
                                                   const MemRegion *NewCont,
135
                                                   SymbolRef Offset,
136
                                                   BinaryOperator::Opcode Opc);
137
ProgramStateRef rebaseSymbolInIteratorPositionsIf(
138
    ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
139
    SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
140
SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
141
                        SymbolRef OldSym, SymbolRef NewSym);
142
bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
143
144
} // namespace
145
146
void ContainerModeling::checkPostCall(const CallEvent &Call,
147
17.4k
                                     CheckerContext &C) const {
148
17.4k
  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
149
17.4k
  if (!Func)
150
0
    return;
151
152
17.4k
  if (Func->isOverloadedOperator()) {
153
1.29k
    const auto Op = Func->getOverloadedOperator();
154
1.29k
    if (Op == OO_Equal) {
155
      // Overloaded 'operator=' must be a non-static member function.
156
51
      const auto *InstCall = cast<CXXInstanceCall>(&Call);
157
51
      if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) {
158
27
        handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
159
27
                     Call.getArgSVal(0));
160
27
        return;
161
27
      }
162
163
24
      handleAssignment(C, InstCall->getCXXThisVal());
164
24
      return;
165
51
    }
166
16.1k
  } else {
167
16.1k
    if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
168
3.28k
      const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call);
169
3.28k
      if (Handler0) {
170
187
        (this->**Handler0)(C, InstCall->getCXXThisVal(),
171
187
                           InstCall->getCXXThisExpr());
172
187
        return;
173
187
      }
174
175
3.09k
      const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call);
176
3.09k
      if (Handler1) {
177
326
        (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
178
326
        return;
179
326
      }
180
181
2.76k
      const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call);
182
2.76k
      if (Handler2) {
183
8
        (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0),
184
8
                           Call.getArgSVal(1));
185
8
        return;
186
8
      }
187
188
2.76k
      const auto *OrigExpr = Call.getOriginExpr();
189
2.76k
      if (!OrigExpr)
190
31
        return;
191
192
2.73k
      if (isBeginCall(Func)) {
193
1.41k
        handleBegin(C, OrigExpr, Call.getReturnValue(),
194
1.41k
                    InstCall->getCXXThisVal());
195
1.41k
        return;
196
1.41k
      }
197
198
1.31k
      if (isEndCall(Func)) {
199
1.19k
        handleEnd(C, OrigExpr, Call.getReturnValue(),
200
1.19k
                  InstCall->getCXXThisVal());
201
1.19k
        return;
202
1.19k
      }
203
1.31k
    }
204
16.1k
  }
205
17.4k
}
206
207
void ContainerModeling::checkLiveSymbols(ProgramStateRef State,
208
40.0k
                                         SymbolReaper &SR) const {
209
  // Keep symbolic expressions of container begins and ends alive
210
40.0k
  auto ContMap = State->get<ContainerMap>();
211
40.0k
  for (const auto &Cont : ContMap) {
212
34.0k
    const auto CData = Cont.second;
213
34.0k
    if (CData.getBegin()) {
214
30.4k
      SR.markLive(CData.getBegin());
215
30.4k
      if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
216
450
        SR.markLive(SIE->getLHS());
217
30.4k
    }
218
34.0k
    if (CData.getEnd()) {
219
16.9k
      SR.markLive(CData.getEnd());
220
16.9k
      if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
221
518
        SR.markLive(SIE->getLHS());
222
16.9k
    }
223
34.0k
  }
224
40.0k
}
225
226
void ContainerModeling::checkDeadSymbols(SymbolReaper &SR,
227
40.0k
                                         CheckerContext &C) const {
228
  // Cleanup
229
40.0k
  auto State = C.getState();
230
  
231
40.0k
  auto ContMap = State->get<ContainerMap>();
232
40.0k
  for (const auto &Cont : ContMap) {
233
34.0k
    if (!SR.isLiveRegion(Cont.first)) {
234
      // We must keep the container data while it has live iterators to be able
235
      // to compare them to the begin and the end of the container.
236
10.9k
      if (!hasLiveIterators(State, Cont.first)) {
237
990
        State = State->remove<ContainerMap>(Cont.first);
238
990
      }
239
10.9k
    }
240
34.0k
  }
241
242
40.0k
  C.addTransition(State);
243
40.0k
}
244
245
void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE,
246
1.41k
                                   SVal RetVal, SVal Cont) const {
247
1.41k
  const auto *ContReg = Cont.getAsRegion();
248
1.41k
  if (!ContReg)
249
0
    return;
250
251
1.41k
  ContReg = ContReg->getMostDerivedObjectRegion();
252
253
  // If the container already has a begin symbol then use it. Otherwise first
254
  // create a new one.
255
1.41k
  auto State = C.getState();
256
1.41k
  auto BeginSym = getContainerBegin(State, ContReg);
257
1.41k
  if (!BeginSym) {
258
1.12k
    State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
259
1.12k
                                 C.getLocationContext(), C.blockCount());
260
1.12k
    BeginSym = getContainerBegin(State, ContReg);
261
1.12k
  }
262
1.41k
  State = setIteratorPosition(State, RetVal,
263
1.41k
                              IteratorPosition::getPosition(ContReg, BeginSym));
264
1.41k
  C.addTransition(State);
265
1.41k
}
266
267
void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE,
268
1.19k
                                 SVal RetVal, SVal Cont) const {
269
1.19k
  const auto *ContReg = Cont.getAsRegion();
270
1.19k
  if (!ContReg)
271
0
    return;
272
273
1.19k
  ContReg = ContReg->getMostDerivedObjectRegion();
274
275
  // If the container already has an end symbol then use it. Otherwise first
276
  // create a new one.
277
1.19k
  auto State = C.getState();
278
1.19k
  auto EndSym = getContainerEnd(State, ContReg);
279
1.19k
  if (!EndSym) {
280
857
    State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
281
857
                               C.getLocationContext(), C.blockCount());
282
857
    EndSym = getContainerEnd(State, ContReg);
283
857
  }
284
1.19k
  State = setIteratorPosition(State, RetVal,
285
1.19k
                              IteratorPosition::getPosition(ContReg, EndSym));
286
1.19k
  C.addTransition(State);
287
1.19k
}
288
289
void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont,
290
51
                                         const Expr *CE, SVal OldCont) const {
291
51
  const auto *ContReg = Cont.getAsRegion();
292
51
  if (!ContReg)
293
0
    return;
294
295
51
  ContReg = ContReg->getMostDerivedObjectRegion();
296
297
  // Assignment of a new value to a container always invalidates all its
298
  // iterators
299
51
  auto State = C.getState();
300
51
  const auto CData = getContainerData(State, ContReg);
301
51
  if (CData) {
302
51
    State = invalidateAllIteratorPositions(State, ContReg);
303
51
  }
304
305
  // In case of move, iterators of the old container (except the past-end
306
  // iterators) remain valid but refer to the new container
307
51
  if (!OldCont.isUndef()) {
308
27
    const auto *OldContReg = OldCont.getAsRegion();
309
27
    if (OldContReg) {
310
27
      OldContReg = OldContReg->getMostDerivedObjectRegion();
311
27
      const auto OldCData = getContainerData(State, OldContReg);
312
27
      if (OldCData) {
313
27
        if (const auto OldEndSym = OldCData->getEnd()) {
314
          // If we already assigned an "end" symbol to the old container, then
315
          // first reassign all iterator positions to the new container which
316
          // are not past the container (thus not greater or equal to the
317
          // current "end" symbol).
318
27
          State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
319
27
                                                     OldEndSym, BO_GE);
320
27
          auto &SymMgr = C.getSymbolManager();
321
27
          auto &SVB = C.getSValBuilder();
322
          // Then generate and assign a new "end" symbol for the new container.
323
27
          auto NewEndSym =
324
27
              SymMgr.conjureSymbol(CE, C.getLocationContext(),
325
27
                                   C.getASTContext().LongTy, C.blockCount());
326
27
          State = assumeNoOverflow(State, NewEndSym, 4);
327
27
          if (CData) {
328
27
            State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
329
27
          } else {
330
0
            State = setContainerData(State, ContReg,
331
0
                                     ContainerData::fromEnd(NewEndSym));
332
0
          }
333
          // Finally, replace the old "end" symbol in the already reassigned
334
          // iterator positions with the new "end" symbol.
335
27
          State = rebaseSymbolInIteratorPositionsIf(
336
27
              State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
337
27
        } else {
338
          // There was no "end" symbol assigned yet to the old container,
339
          // so reassign all iterator positions to the new container.
340
0
          State = reassignAllIteratorPositions(State, OldContReg, ContReg);
341
0
        }
342
27
        if (const auto OldBeginSym = OldCData->getBegin()) {
343
          // If we already assigned a "begin" symbol to the old container, then
344
          // assign it to the new container and remove it from the old one.
345
27
          if (CData) {
346
27
            State =
347
27
                setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
348
27
          } else {
349
0
            State = setContainerData(State, ContReg,
350
0
                                     ContainerData::fromBegin(OldBeginSym));
351
0
          }
352
27
          State =
353
27
              setContainerData(State, OldContReg, OldCData->newBegin(nullptr));
354
27
        }
355
27
      } else {
356
        // There was neither "begin" nor "end" symbol assigned yet to the old
357
        // container, so reassign all iterator positions to the new container.
358
0
        State = reassignAllIteratorPositions(State, OldContReg, ContReg);
359
0
      }
360
27
    }
361
27
  }
362
51
  C.addTransition(State);
363
51
}
364
365
void ContainerModeling::handleAssign(CheckerContext &C, SVal Cont,
366
24
                                     const Expr *ContE) const {
367
24
  const auto *ContReg = Cont.getAsRegion();
368
24
  if (!ContReg)
369
0
    return;
370
371
24
  ContReg = ContReg->getMostDerivedObjectRegion();
372
373
  // The assign() operation invalidates all the iterators
374
24
  auto State = C.getState();
375
24
  State = invalidateAllIteratorPositions(State, ContReg);
376
24
  C.addTransition(State);
377
24
}
378
379
void ContainerModeling::handleClear(CheckerContext &C, SVal Cont,
380
26
                                    const Expr *ContE) const {
381
26
  const auto *ContReg = Cont.getAsRegion();
382
26
  if (!ContReg)
383
0
    return;
384
385
26
  ContReg = ContReg->getMostDerivedObjectRegion();
386
387
  // The clear() operation invalidates all the iterators, except the past-end
388
  // iterators of list-like containers
389
26
  auto State = C.getState();
390
26
  if (!hasSubscriptOperator(State, ContReg) ||
391
26
      
!backModifiable(State, ContReg)12
) {
392
14
    const auto CData = getContainerData(State, ContReg);
393
14
    if (CData) {
394
14
      if (const auto EndSym = CData->getEnd()) {
395
12
        State =
396
12
            invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
397
12
        C.addTransition(State);
398
12
        return;
399
12
      }
400
14
    }
401
14
  }
402
14
  const NoteTag *ChangeTag =
403
14
    getChangeTag(C, "became empty", ContReg, ContE);
404
14
  State = invalidateAllIteratorPositions(State, ContReg);
405
14
  C.addTransition(State, ChangeTag);
406
14
}
407
408
void ContainerModeling::handlePushBack(CheckerContext &C, SVal Cont,
409
51
                                       const Expr *ContE) const {
410
51
  const auto *ContReg = Cont.getAsRegion();
411
51
  if (!ContReg)
412
0
    return;
413
414
51
  ContReg = ContReg->getMostDerivedObjectRegion();
415
416
  // For deque-like containers invalidate all iterator positions
417
51
  auto State = C.getState();
418
51
  if (hasSubscriptOperator(State, ContReg) && 
frontModifiable(State, ContReg)36
) {
419
12
    State = invalidateAllIteratorPositions(State, ContReg);
420
12
    C.addTransition(State);
421
12
    return;
422
12
  }
423
424
39
  const auto CData = getContainerData(State, ContReg);
425
39
  if (!CData)
426
0
    return;
427
428
  // For vector-like containers invalidate the past-end iterator positions
429
39
  if (const auto EndSym = CData->getEnd()) {
430
39
    if (hasSubscriptOperator(State, ContReg)) {
431
24
      State = invalidateIteratorPositions(State, EndSym, BO_GE);
432
24
    }
433
39
    auto &SymMgr = C.getSymbolManager();
434
39
    auto &BVF = SymMgr.getBasicVals();
435
39
    auto &SVB = C.getSValBuilder();
436
39
    const auto newEndSym =
437
39
      SVB.evalBinOp(State, BO_Add,
438
39
                    nonloc::SymbolVal(EndSym),
439
39
                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
440
39
                    SymMgr.getType(EndSym)).getAsSymbol();
441
39
    const NoteTag *ChangeTag =
442
39
      getChangeTag(C, "extended to the back by 1 position", ContReg, ContE);
443
39
    State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
444
39
    C.addTransition(State, ChangeTag);
445
39
  }
446
39
}
447
448
void ContainerModeling::handlePopBack(CheckerContext &C, SVal Cont,
449
23
                                      const Expr *ContE) const {
450
23
  const auto *ContReg = Cont.getAsRegion();
451
23
  if (!ContReg)
452
0
    return;
453
454
23
  ContReg = ContReg->getMostDerivedObjectRegion();
455
456
23
  auto State = C.getState();
457
23
  const auto CData = getContainerData(State, ContReg);
458
23
  if (!CData)
459
0
    return;
460
461
23
  if (const auto EndSym = CData->getEnd()) {
462
23
    auto &SymMgr = C.getSymbolManager();
463
23
    auto &BVF = SymMgr.getBasicVals();
464
23
    auto &SVB = C.getSValBuilder();
465
23
    const auto BackSym =
466
23
      SVB.evalBinOp(State, BO_Sub,
467
23
                    nonloc::SymbolVal(EndSym),
468
23
                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
469
23
                    SymMgr.getType(EndSym)).getAsSymbol();
470
23
    const NoteTag *ChangeTag =
471
23
      getChangeTag(C, "shrank from the back by 1 position", ContReg, ContE);
472
    // For vector-like and deque-like containers invalidate the last and the
473
    // past-end iterator positions. For list-like containers only invalidate
474
    // the last position
475
23
    if (hasSubscriptOperator(State, ContReg) &&
476
23
        
backModifiable(State, ContReg)17
) {
477
17
      State = invalidateIteratorPositions(State, BackSym, BO_GE);
478
17
      State = setContainerData(State, ContReg, CData->newEnd(nullptr));
479
17
    } else {
480
6
      State = invalidateIteratorPositions(State, BackSym, BO_EQ);
481
6
    }
482
23
    auto newEndSym = BackSym;
483
23
    State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
484
23
    C.addTransition(State, ChangeTag);
485
23
  }
486
23
}
487
488
void ContainerModeling::handlePushFront(CheckerContext &C, SVal Cont,
489
42
                                        const Expr *ContE) const {
490
42
  const auto *ContReg = Cont.getAsRegion();
491
42
  if (!ContReg)
492
0
    return;
493
494
42
  ContReg = ContReg->getMostDerivedObjectRegion();
495
496
  // For deque-like containers invalidate all iterator positions
497
42
  auto State = C.getState();
498
42
  if (hasSubscriptOperator(State, ContReg)) {
499
12
    State = invalidateAllIteratorPositions(State, ContReg);
500
12
    C.addTransition(State);
501
30
  } else {
502
30
    const auto CData = getContainerData(State, ContReg);
503
30
    if (!CData)
504
0
      return;
505
506
30
    if (const auto BeginSym = CData->getBegin()) {
507
30
      auto &SymMgr = C.getSymbolManager();
508
30
      auto &BVF = SymMgr.getBasicVals();
509
30
      auto &SVB = C.getSValBuilder();
510
30
      const auto newBeginSym =
511
30
        SVB.evalBinOp(State, BO_Sub,
512
30
                      nonloc::SymbolVal(BeginSym),
513
30
                      nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
514
30
                      SymMgr.getType(BeginSym)).getAsSymbol();
515
30
      const NoteTag *ChangeTag =
516
30
        getChangeTag(C, "extended to the front by 1 position", ContReg, ContE);
517
30
      State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
518
30
      C.addTransition(State, ChangeTag);
519
30
    }
520
30
  }
521
42
}
522
523
void ContainerModeling::handlePopFront(CheckerContext &C, SVal Cont,
524
21
                                       const Expr *ContE) const {
525
21
  const auto *ContReg = Cont.getAsRegion();
526
21
  if (!ContReg)
527
0
    return;
528
529
21
  ContReg = ContReg->getMostDerivedObjectRegion();
530
531
21
  auto State = C.getState();
532
21
  const auto CData = getContainerData(State, ContReg);
533
21
  if (!CData)
534
0
    return;
535
536
  // For deque-like containers invalidate all iterator positions. For list-like
537
  // iterators only invalidate the first position
538
21
  if (const auto BeginSym = CData->getBegin()) {
539
21
    if (hasSubscriptOperator(State, ContReg)) {
540
6
      State = invalidateIteratorPositions(State, BeginSym, BO_LE);
541
15
    } else {
542
15
      State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
543
15
    }
544
21
    auto &SymMgr = C.getSymbolManager();
545
21
    auto &BVF = SymMgr.getBasicVals();
546
21
    auto &SVB = C.getSValBuilder();
547
21
    const auto newBeginSym =
548
21
      SVB.evalBinOp(State, BO_Add,
549
21
                    nonloc::SymbolVal(BeginSym),
550
21
                    nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
551
21
                    SymMgr.getType(BeginSym)).getAsSymbol();
552
21
    const NoteTag *ChangeTag =
553
21
      getChangeTag(C, "shrank from the front by 1 position", ContReg, ContE);
554
21
    State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
555
21
    C.addTransition(State, ChangeTag);
556
21
  }
557
21
}
558
559
void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont,
560
194
                                     SVal Iter) const {
561
194
  const auto *ContReg = Cont.getAsRegion();
562
194
  if (!ContReg)
563
0
    return;
564
565
194
  ContReg = ContReg->getMostDerivedObjectRegion();
566
567
194
  auto State = C.getState();
568
194
  const auto *Pos = getIteratorPosition(State, Iter);
569
194
  if (!Pos)
570
0
    return;
571
572
  // For deque-like containers invalidate all iterator positions. For
573
  // vector-like containers invalidate iterator positions after the insertion.
574
194
  if (hasSubscriptOperator(State, ContReg) && 
backModifiable(State, ContReg)134
) {
575
134
    if (frontModifiable(State, ContReg)) {
576
60
      State = invalidateAllIteratorPositions(State, ContReg);
577
74
    } else {
578
74
      State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
579
74
    }
580
134
    if (const auto *CData = getContainerData(State, ContReg)) {
581
128
      if (const auto EndSym = CData->getEnd()) {
582
122
        State = invalidateIteratorPositions(State, EndSym, BO_GE);
583
122
        State = setContainerData(State, ContReg, CData->newEnd(nullptr));
584
122
      }
585
128
    }
586
134
    C.addTransition(State);
587
134
  }
588
194
}
589
590
void ContainerModeling::handleErase(CheckerContext &C, SVal Cont,
591
120
                                    SVal Iter) const {
592
120
  const auto *ContReg = Cont.getAsRegion();
593
120
  if (!ContReg)
594
0
    return;
595
596
120
  ContReg = ContReg->getMostDerivedObjectRegion();
597
598
120
  auto State = C.getState();
599
120
  const auto *Pos = getIteratorPosition(State, Iter);
600
120
  if (!Pos)
601
0
    return;
602
603
  // For deque-like containers invalidate all iterator positions. For
604
  // vector-like containers invalidate iterator positions at and after the
605
  // deletion. For list-like containers only invalidate the deleted position.
606
120
  if (hasSubscriptOperator(State, ContReg) && 
backModifiable(State, ContReg)96
) {
607
96
    if (frontModifiable(State, ContReg)) {
608
24
      State = invalidateAllIteratorPositions(State, ContReg);
609
72
    } else {
610
72
      State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
611
72
    }
612
96
    if (const auto *CData = getContainerData(State, ContReg)) {
613
92
      if (const auto EndSym = CData->getEnd()) {
614
48
        State = invalidateIteratorPositions(State, EndSym, BO_GE);
615
48
        State = setContainerData(State, ContReg, CData->newEnd(nullptr));
616
48
      }
617
92
    }
618
96
  } else {
619
24
    State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
620
24
  }
621
120
  C.addTransition(State);
622
120
}
623
624
void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter1,
625
8
                                    SVal Iter2) const {
626
8
  const auto *ContReg = Cont.getAsRegion();
627
8
  if (!ContReg)
628
0
    return;
629
630
8
  ContReg = ContReg->getMostDerivedObjectRegion();
631
8
  auto State = C.getState();
632
8
  const auto *Pos1 = getIteratorPosition(State, Iter1);
633
8
  const auto *Pos2 = getIteratorPosition(State, Iter2);
634
8
  if (!Pos1 || !Pos2)
635
0
    return;
636
637
  // For deque-like containers invalidate all iterator positions. For
638
  // vector-like containers invalidate iterator positions at and after the
639
  // deletion range. For list-like containers only invalidate the deleted
640
  // position range [first..last].
641
8
  if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
642
8
    if (frontModifiable(State, ContReg)) {
643
0
      State = invalidateAllIteratorPositions(State, ContReg);
644
8
    } else {
645
8
      State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
646
8
    }
647
8
    if (const auto *CData = getContainerData(State, ContReg)) {
648
8
      if (const auto EndSym = CData->getEnd()) {
649
4
        State = invalidateIteratorPositions(State, EndSym, BO_GE);
650
4
        State = setContainerData(State, ContReg, CData->newEnd(nullptr));
651
4
      }
652
8
    }
653
8
  } else {
654
0
    State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
655
0
                                        Pos2->getOffset(), BO_LT);
656
0
  }
657
8
  C.addTransition(State);
658
8
}
659
660
void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
661
12
                                        SVal Iter) const {
662
12
  auto State = C.getState();
663
12
  const auto *Pos = getIteratorPosition(State, Iter);
664
12
  if (!Pos)
665
0
    return;
666
667
  // Invalidate the deleted iterator position, which is the position of the
668
  // parameter plus one.
669
12
  auto &SymMgr = C.getSymbolManager();
670
12
  auto &BVF = SymMgr.getBasicVals();
671
12
  auto &SVB = C.getSValBuilder();
672
12
  const auto NextSym =
673
12
    SVB.evalBinOp(State, BO_Add,
674
12
                  nonloc::SymbolVal(Pos->getOffset()),
675
12
                  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
676
12
                  SymMgr.getType(Pos->getOffset())).getAsSymbol();
677
12
  State = invalidateIteratorPositions(State, NextSym, BO_EQ);
678
12
  C.addTransition(State);
679
12
}
680
681
void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
682
0
                                         SVal Iter1, SVal Iter2) const {
683
0
  auto State = C.getState();
684
0
  const auto *Pos1 = getIteratorPosition(State, Iter1);
685
0
  const auto *Pos2 = getIteratorPosition(State, Iter2);
686
0
  if (!Pos1 || !Pos2)
687
0
    return;
688
689
  // Invalidate the deleted iterator position range (first..last)
690
0
  State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
691
0
                                      Pos2->getOffset(), BO_LT);
692
0
  C.addTransition(State);
693
0
}
694
695
const NoteTag *ContainerModeling::getChangeTag(CheckerContext &C,
696
                                               StringRef Text,
697
                                               const MemRegion *ContReg,
698
127
                                               const Expr *ContE) const {
699
127
  StringRef Name;
700
  // First try to get the name of the variable from the region
701
127
  if (const auto *DR = dyn_cast<DeclRegion>(ContReg)) {
702
5
    Name = DR->getDecl()->getName();
703
  // If the region is not a `DeclRegion` then use the expression instead
704
122
  } else if (const auto *DRE =
705
122
             dyn_cast<DeclRefExpr>(ContE->IgnoreParenCasts())) {
706
122
    Name = DRE->getDecl()->getName();
707
122
  }
708
709
127
  return C.getNoteTag(
710
460
      [Text, Name, ContReg](PathSensitiveBugReport &BR) -> std::string {
711
460
        if (!BR.isInteresting(ContReg))
712
430
          return "";
713
714
30
        SmallString<256> Msg;
715
30
        llvm::raw_svector_ostream Out(Msg);
716
30
        Out << "Container " << (!Name.empty() ? ("'" + Name.str() + "' ") : 
""0
)
717
30
            << Text;
718
30
        return std::string(Out.str());
719
460
      });
720
127
}
721
722
void ContainerModeling::printState(raw_ostream &Out, ProgramStateRef State,
723
36
                                  const char *NL, const char *Sep) const {
724
36
  auto ContMap = State->get<ContainerMap>();
725
726
36
  if (!ContMap.isEmpty()) {
727
36
    Out << Sep << "Container Data :" << NL;
728
36
    for (const auto &Cont : ContMap) {
729
36
      Cont.first->dumpToStream(Out);
730
36
      Out << " : [ ";
731
36
      const auto CData = Cont.second;
732
36
      if (CData.getBegin())
733
36
        CData.getBegin()->dumpToStream(Out);
734
0
      else
735
0
        Out << "<Unknown>";
736
36
      Out << " .. ";
737
36
      if (CData.getEnd())
738
18
        CData.getEnd()->dumpToStream(Out);
739
18
      else
740
18
        Out << "<Unknown>";
741
36
      Out << " ]";
742
36
    }
743
36
  }
744
36
}
745
746
namespace {
747
748
2.73k
bool isBeginCall(const FunctionDecl *Func) {
749
2.73k
  const auto *IdInfo = Func->getIdentifier();
750
2.73k
  if (!IdInfo)
751
0
    return false;
752
2.73k
  return IdInfo->getName().endswith_insensitive("begin");
753
2.73k
}
754
755
1.31k
bool isEndCall(const FunctionDecl *Func) {
756
1.31k
  const auto *IdInfo = Func->getIdentifier();
757
1.31k
  if (!IdInfo)
758
0
    return false;
759
1.31k
  return IdInfo->getName().endswith_insensitive("end");
760
1.31k
}
761
762
const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
763
1.06k
                                      const MemRegion *Reg) {
764
1.06k
  auto TI = getDynamicTypeInfo(State, Reg);
765
1.06k
  if (!TI.isValid())
766
0
    return nullptr;
767
768
1.06k
  auto Type = TI.getType();
769
1.06k
  if (const auto *RefT = Type->getAs<ReferenceType>()) {
770
1.05k
    Type = RefT->getPointeeType();
771
1.05k
  }
772
773
1.06k
  return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
774
1.06k
}
775
776
524
bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
777
524
  const auto *CRD = getCXXRecordDecl(State, Reg);
778
524
  if (!CRD)
779
8
    return false;
780
781
12.6k
  
for (const auto *Method : CRD->methods())516
{
782
12.6k
    if (!Method->isOverloadedOperator())
783
10.8k
      continue;
784
1.83k
    const auto OPK = Method->getOverloadedOperator();
785
1.83k
    if (OPK == OO_Subscript) {
786
345
      return true;
787
345
    }
788
1.83k
  }
789
171
  return false;
790
516
}
791
792
274
bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
793
274
  const auto *CRD = getCXXRecordDecl(State, Reg);
794
274
  if (!CRD)
795
0
    return false;
796
797
6.59k
  
for (const auto *Method : CRD->methods())274
{
798
6.59k
    if (!Method->getDeclName().isIdentifier())
799
2.11k
      continue;
800
4.48k
    if (Method->getName() == "push_front" || 
Method->getName() == "pop_front"4.38k
) {
801
96
      return true;
802
96
    }
803
4.48k
  }
804
178
  return false;
805
274
}
806
807
267
bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
808
267
  const auto *CRD = getCXXRecordDecl(State, Reg);
809
267
  if (!CRD)
810
0
    return false;
811
812
3.04k
  
for (const auto *Method : CRD->methods())267
{
813
3.04k
    if (!Method->getDeclName().isIdentifier())
814
1.74k
      continue;
815
1.29k
    if (Method->getName() == "push_back" || 
Method->getName() == "pop_back"1.02k
) {
816
267
      return true;
817
267
    }
818
1.29k
  }
819
0
  return false;
820
267
}
821
822
2.53k
SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
823
2.53k
  const auto *CDataPtr = getContainerData(State, Cont);
824
2.53k
  if (!CDataPtr)
825
1.12k
    return nullptr;
826
827
1.41k
  return CDataPtr->getBegin();
828
2.53k
}
829
830
2.05k
SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
831
2.05k
  const auto *CDataPtr = getContainerData(State, Cont);
832
2.05k
  if (!CDataPtr)
833
270
    return nullptr;
834
835
1.78k
  return CDataPtr->getEnd();
836
2.05k
}
837
838
ProgramStateRef createContainerBegin(ProgramStateRef State,
839
                                     const MemRegion *Cont, const Expr *E,
840
                                     QualType T, const LocationContext *LCtx,
841
1.12k
                                     unsigned BlockCount) {
842
  // Only create if it does not exist
843
1.12k
  const auto *CDataPtr = getContainerData(State, Cont);
844
1.12k
  if (CDataPtr && 
CDataPtr->getBegin()4
)
845
0
    return State;
846
847
1.12k
  auto &SymMgr = State->getSymbolManager();
848
1.12k
  const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
849
1.12k
                                                   "begin");
850
1.12k
  State = assumeNoOverflow(State, Sym, 4);
851
852
1.12k
  if (CDataPtr) {
853
4
    const auto CData = CDataPtr->newBegin(Sym);
854
4
    return setContainerData(State, Cont, CData);
855
4
  }
856
857
1.12k
  const auto CData = ContainerData::fromBegin(Sym);
858
1.12k
  return setContainerData(State, Cont, CData);
859
1.12k
}
860
861
ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
862
                                   const Expr *E, QualType T,
863
                                   const LocationContext *LCtx,
864
857
                                   unsigned BlockCount) {
865
  // Only create if it does not exist
866
857
  const auto *CDataPtr = getContainerData(State, Cont);
867
857
  if (CDataPtr && 
CDataPtr->getEnd()587
)
868
0
    return State;
869
870
857
  auto &SymMgr = State->getSymbolManager();
871
857
  const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
872
857
                                                  "end");
873
857
  State = assumeNoOverflow(State, Sym, 4);
874
875
857
  if (CDataPtr) {
876
587
    const auto CData = CDataPtr->newEnd(Sym);
877
587
    return setContainerData(State, Cont, CData);
878
587
  }
879
880
270
  const auto CData = ContainerData::fromEnd(Sym);
881
270
  return setContainerData(State, Cont, CData);
882
857
}
883
884
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
885
2.36k
                                 const ContainerData &CData) {
886
2.36k
  return State->set<ContainerMap>(Cont, CData);
887
2.36k
}
888
889
template <typename Condition, typename Process>
890
ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
891
695
                                         Process Proc) {
892
695
  auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
893
695
  auto RegionMap = State->get<IteratorRegionMap>();
894
695
  bool Changed = false;
895
2.17k
  for (const auto &Reg : RegionMap) {
896
2.17k
    if (Cond(Reg.second)) {
897
1.19k
      RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
898
1.19k
      Changed = true;
899
1.19k
    }
900
2.17k
  }
901
902
695
  if (Changed)
903
660
    State = State->set<IteratorRegionMap>(RegionMap);
904
905
695
  auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
906
695
  auto SymbolMap = State->get<IteratorSymbolMap>();
907
695
  Changed = false;
908
695
  for (const auto &Sym : SymbolMap) {
909
0
    if (Cond(Sym.second)) {
910
0
      SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
911
0
      Changed = true;
912
0
    }
913
0
  }
914
915
695
  if (Changed)
916
0
    State = State->set<IteratorSymbolMap>(SymbolMap);
917
918
695
  return State;
919
695
}
ContainerModeling.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)::$_3, (anonymous namespace)::invalidateAllIteratorPositionsExcept(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_4>(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)::$_3, (anonymous namespace)::invalidateAllIteratorPositionsExcept(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_4)
Line
Count
Source
891
12
                                         Process Proc) {
892
12
  auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
893
12
  auto RegionMap = State->get<IteratorRegionMap>();
894
12
  bool Changed = false;
895
12
  for (const auto &Reg : RegionMap) {
896
12
    if (Cond(Reg.second)) {
897
12
      RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
898
12
      Changed = true;
899
12
    }
900
12
  }
901
902
12
  if (Changed)
903
12
    State = State->set<IteratorRegionMap>(RegionMap);
904
905
12
  auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
906
12
  auto SymbolMap = State->get<IteratorSymbolMap>();
907
12
  Changed = false;
908
12
  for (const auto &Sym : SymbolMap) {
909
0
    if (Cond(Sym.second)) {
910
0
      SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
911
0
      Changed = true;
912
0
    }
913
0
  }
914
915
12
  if (Changed)
916
0
    State = State->set<IteratorSymbolMap>(SymbolMap);
917
918
12
  return State;
919
12
}
ContainerModeling.cpp:llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const> (anonymous namespace)::processIteratorPositions<(anonymous namespace)::invalidateAllIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*)::$_1, (anonymous namespace)::invalidateAllIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*)::$_2>(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, (anonymous namespace)::invalidateAllIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*)::$_1, (anonymous namespace)::invalidateAllIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*)::$_2)
Line
Count
Source
891
197
                                         Process Proc) {
892
197
  auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
893
197
  auto RegionMap = State->get<IteratorRegionMap>();
894
197
  bool Changed = false;
895
572
  for (const auto &Reg : RegionMap) {
896
572
    if (Cond(Reg.second)) {
897
506
      RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
898
506
      Changed = true;
899
506
    }
900
572
  }
901
902
197
  if (Changed)
903
194
    State = State->set<IteratorRegionMap>(RegionMap);
904
905
197
  auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
906
197
  auto SymbolMap = State->get<IteratorSymbolMap>();
907
197
  Changed = false;
908
197
  for (const auto &Sym : SymbolMap) {
909
0
    if (Cond(Sym.second)) {
910
0
      SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
911
0
      Changed = true;
912
0
    }
913
0
  }
914
915
197
  if (Changed)
916
0
    State = State->set<IteratorSymbolMap>(SymbolMap);
917
918
197
  return State;
919
197
}
ContainerModeling.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)::$_5, (anonymous namespace)::invalidateIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_6>(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, (anonymous namespace)::invalidateIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_5, (anonymous namespace)::invalidateIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_6)
Line
Count
Source
891
432
                                         Process Proc) {
892
432
  auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
893
432
  auto RegionMap = State->get<IteratorRegionMap>();
894
432
  bool Changed = false;
895
1.41k
  for (const auto &Reg : RegionMap) {
896
1.41k
    if (Cond(Reg.second)) {
897
620
      RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
898
620
      Changed = true;
899
620
    }
900
1.41k
  }
901
902
432
  if (Changed)
903
412
    State = State->set<IteratorRegionMap>(RegionMap);
904
905
432
  auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
906
432
  auto SymbolMap = State->get<IteratorSymbolMap>();
907
432
  Changed = false;
908
432
  for (const auto &Sym : SymbolMap) {
909
0
    if (Cond(Sym.second)) {
910
0
      SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
911
0
      Changed = true;
912
0
    }
913
0
  }
914
915
432
  if (Changed)
916
0
    State = State->set<IteratorSymbolMap>(SymbolMap);
917
918
432
  return State;
919
432
}
Unexecuted instantiation: ContainerModeling.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)::$_7, (anonymous namespace)::invalidateIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, clang::BinaryOperatorKind, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_8>(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)::$_7, (anonymous namespace)::invalidateIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::SymExpr const*, clang::BinaryOperatorKind, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_8)
ContainerModeling.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)::$_11, (anonymous namespace)::reassignAllIteratorPositionsUnless(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*, clang::ento::MemRegion const*, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_12>(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)::$_11, (anonymous namespace)::reassignAllIteratorPositionsUnless(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*, clang::ento::MemRegion const*, clang::ento::SymExpr const*, clang::BinaryOperatorKind)::$_12)
Line
Count
Source
891
27
                                         Process Proc) {
892
27
  auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
893
27
  auto RegionMap = State->get<IteratorRegionMap>();
894
27
  bool Changed = false;
895
90
  for (const auto &Reg : RegionMap) {
896
90
    if (Cond(Reg.second)) {
897
42
      RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
898
42
      Changed = true;
899
42
    }
900
90
  }
901
902
27
  if (Changed)
903
24
    State = State->set<IteratorRegionMap>(RegionMap);
904
905
27
  auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
906
27
  auto SymbolMap = State->get<IteratorSymbolMap>();
907
27
  Changed = false;
908
27
  for (const auto &Sym : SymbolMap) {
909
0
    if (Cond(Sym.second)) {
910
0
      SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
911
0
      Changed = true;
912
0
    }
913
0
  }
914
915
27
  if (Changed)
916
0
    State = State->set<IteratorSymbolMap>(SymbolMap);
917
918
27
  return State;
919
27
}
ContainerModeling.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)::$_13, (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)::$_14>(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)::$_13, (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)::$_14)
Line
Count
Source
891
27
                                         Process Proc) {
892
27
  auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
893
27
  auto RegionMap = State->get<IteratorRegionMap>();
894
27
  bool Changed = false;
895
90
  for (const auto &Reg : RegionMap) {
896
90
    if (Cond(Reg.second)) {
897
18
      RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
898
18
      Changed = true;
899
18
    }
900
90
  }
901
902
27
  if (Changed)
903
18
    State = State->set<IteratorRegionMap>(RegionMap);
904
905
27
  auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
906
27
  auto SymbolMap = State->get<IteratorSymbolMap>();
907
27
  Changed = false;
908
27
  for (const auto &Sym : SymbolMap) {
909
0
    if (Cond(Sym.second)) {
910
0
      SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
911
0
      Changed = true;
912
0
    }
913
0
  }
914
915
27
  if (Changed)
916
0
    State = State->set<IteratorSymbolMap>(SymbolMap);
917
918
27
  return State;
919
27
}
Unexecuted instantiation: ContainerModeling.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*)::$_9, (anonymous namespace)::reassignAllIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*, clang::ento::MemRegion const*)::$_10>(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, (anonymous namespace)::reassignAllIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*, clang::ento::MemRegion const*)::$_9, (anonymous namespace)::reassignAllIteratorPositions(llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::MemRegion const*, clang::ento::MemRegion const*)::$_10)
920
921
ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
922
197
                                               const MemRegion *Cont) {
923
572
  auto MatchCont = [&](const IteratorPosition &Pos) {
924
572
    return Pos.getContainer() == Cont;
925
572
  };
926
506
  auto Invalidate = [&](const IteratorPosition &Pos) {
927
506
    return Pos.invalidate();
928
506
  };
929
197
  return processIteratorPositions(State, MatchCont, Invalidate);
930
197
}
931
932
ProgramStateRef
933
invalidateAllIteratorPositionsExcept(ProgramStateRef State,
934
                                     const MemRegion *Cont, SymbolRef Offset,
935
12
                                     BinaryOperator::Opcode Opc) {
936
12
  auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
937
12
    return Pos.getContainer() == Cont &&
938
12
           !compare(State, Pos.getOffset(), Offset, Opc);
939
12
  };
940
12
  auto Invalidate = [&](const IteratorPosition &Pos) {
941
12
    return Pos.invalidate();
942
12
  };
943
12
  return processIteratorPositions(State, MatchContAndCompare, Invalidate);
944
12
}
945
946
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
947
                                            SymbolRef Offset,
948
432
                                            BinaryOperator::Opcode Opc) {
949
1.41k
  auto Compare = [&](const IteratorPosition &Pos) {
950
1.41k
    return compare(State, Pos.getOffset(), Offset, Opc);
951
1.41k
  };
952
620
  auto Invalidate = [&](const IteratorPosition &Pos) {
953
620
    return Pos.invalidate();
954
620
  };
955
432
  return processIteratorPositions(State, Compare, Invalidate);
956
432
}
957
958
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
959
                                            SymbolRef Offset1,
960
                                            BinaryOperator::Opcode Opc1,
961
                                            SymbolRef Offset2,
962
0
                                            BinaryOperator::Opcode Opc2) {
963
0
  auto Compare = [&](const IteratorPosition &Pos) {
964
0
    return compare(State, Pos.getOffset(), Offset1, Opc1) &&
965
0
           compare(State, Pos.getOffset(), Offset2, Opc2);
966
0
  };
967
0
  auto Invalidate = [&](const IteratorPosition &Pos) {
968
0
    return Pos.invalidate();
969
0
  };
970
0
  return processIteratorPositions(State, Compare, Invalidate);
971
0
}
972
973
ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
974
                                             const MemRegion *Cont,
975
0
                                             const MemRegion *NewCont) {
976
0
  auto MatchCont = [&](const IteratorPosition &Pos) {
977
0
    return Pos.getContainer() == Cont;
978
0
  };
979
0
  auto ReAssign = [&](const IteratorPosition &Pos) {
980
0
    return Pos.reAssign(NewCont);
981
0
  };
982
0
  return processIteratorPositions(State, MatchCont, ReAssign);
983
0
}
984
985
ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
986
                                                   const MemRegion *Cont,
987
                                                   const MemRegion *NewCont,
988
                                                   SymbolRef Offset,
989
27
                                                   BinaryOperator::Opcode Opc) {
990
90
  auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
991
90
    return Pos.getContainer() == Cont &&
992
90
    
!compare(State, Pos.getOffset(), Offset, Opc)66
;
993
90
  };
994
42
  auto ReAssign = [&](const IteratorPosition &Pos) {
995
42
    return Pos.reAssign(NewCont);
996
42
  };
997
27
  return processIteratorPositions(State, MatchContAndCompare, ReAssign);
998
27
}
999
1000
// This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
1001
// `OldSym - Int` to `NewSym - Int` and  `OldSym` to `NewSym` in any iterator
1002
// position offsets where `CondSym` is true.
1003
ProgramStateRef rebaseSymbolInIteratorPositionsIf(
1004
    ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
1005
27
    SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
1006
90
  auto LessThanEnd = [&](const IteratorPosition &Pos) {
1007
90
    return compare(State, Pos.getOffset(), CondSym, Opc);
1008
90
  };
1009
27
  auto RebaseSymbol = [&](const IteratorPosition &Pos) {
1010
18
    return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
1011
18
                                   NewSym));
1012
18
  };
1013
27
  return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
1014
27
}
1015
1016
// This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
1017
// `OldExpr - Int` to `NewExpr - Int` and  `OldExpr` to `NewExpr` in expression
1018
// `OrigExpr`.
1019
SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
1020
                       SymbolRef OrigExpr, SymbolRef OldExpr,
1021
18
                       SymbolRef NewSym) {
1022
18
  auto &SymMgr = SVB.getSymbolManager();
1023
18
  auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
1024
18
                              nonloc::SymbolVal(OldExpr), 
1025
18
                              SymMgr.getType(OrigExpr));
1026
1027
18
  const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
1028
18
  if (!DiffInt)
1029
0
    return OrigExpr;
1030
1031
18
  return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
1032
18
                         SymMgr.getType(OrigExpr)).getAsSymbol();
1033
18
}
1034
1035
10.9k
bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
1036
10.9k
  auto RegionMap = State->get<IteratorRegionMap>();
1037
11.2k
  for (const auto &Reg : RegionMap) {
1038
11.2k
    if (Reg.second.getContainer() == Cont)
1039
9.96k
      return true;
1040
11.2k
  }
1041
1042
994
  auto SymbolMap = State->get<IteratorSymbolMap>();
1043
994
  for (const auto &Sym : SymbolMap) {
1044
30
    if (Sym.second.getContainer() == Cont)
1045
4
      return true;
1046
30
  }
1047
1048
990
  return false;
1049
994
}
1050
1051
} // namespace
1052
1053
21
void ento::registerContainerModeling(CheckerManager &mgr) {
1054
21
  mgr.registerChecker<ContainerModeling>();
1055
21
}
1056
1057
74
bool ento::shouldRegisterContainerModeling(const CheckerManager &mgr) {
1058
74
  if (!mgr.getLangOpts().CPlusPlus)
1059
2
    return false;
1060
1061
72
  if (!mgr.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation) {
1062
4
    mgr.getASTContext().getDiagnostics().Report(
1063
4
        diag::err_analyzer_checker_incompatible_analyzer_option)
1064
4
      << "aggressive-binary-operation-simplification" << "false";
1065
4
    return false;
1066
4
  }
1067
1068
68
  return true;
1069
72
}