Coverage Report

Created: 2022-01-18 06:27

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