Coverage Report

Created: 2020-12-01 06:44

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ----------===//
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
//  This file defines a meta-engine for path-sensitive dataflow analysis that
10
//  is built on GREngine, but provides the boilerplate to execute transfer
11
//  functions and build the ExplodedGraph at the expression level.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
16
#include "PrettyStackTraceLocationContext.h"
17
#include "clang/AST/ASTContext.h"
18
#include "clang/AST/Decl.h"
19
#include "clang/AST/DeclBase.h"
20
#include "clang/AST/DeclCXX.h"
21
#include "clang/AST/DeclObjC.h"
22
#include "clang/AST/Expr.h"
23
#include "clang/AST/ExprCXX.h"
24
#include "clang/AST/ExprObjC.h"
25
#include "clang/AST/ParentMap.h"
26
#include "clang/AST/PrettyPrinter.h"
27
#include "clang/AST/Stmt.h"
28
#include "clang/AST/StmtCXX.h"
29
#include "clang/AST/StmtObjC.h"
30
#include "clang/AST/Type.h"
31
#include "clang/Analysis/AnalysisDeclContext.h"
32
#include "clang/Analysis/CFG.h"
33
#include "clang/Analysis/ConstructionContext.h"
34
#include "clang/Analysis/ProgramPoint.h"
35
#include "clang/Basic/IdentifierTable.h"
36
#include "clang/Basic/JsonSupport.h"
37
#include "clang/Basic/LLVM.h"
38
#include "clang/Basic/LangOptions.h"
39
#include "clang/Basic/PrettyStackTrace.h"
40
#include "clang/Basic/SourceLocation.h"
41
#include "clang/Basic/SourceManager.h"
42
#include "clang/Basic/Specifiers.h"
43
#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
44
#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
45
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
46
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
47
#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
48
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
49
#include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
50
#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
51
#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
52
#include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
53
#include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
54
#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
55
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
56
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
57
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
58
#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
59
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
60
#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
61
#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
62
#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
63
#include "llvm/ADT/APSInt.h"
64
#include "llvm/ADT/DenseMap.h"
65
#include "llvm/ADT/ImmutableMap.h"
66
#include "llvm/ADT/ImmutableSet.h"
67
#include "llvm/ADT/Optional.h"
68
#include "llvm/ADT/SmallVector.h"
69
#include "llvm/ADT/Statistic.h"
70
#include "llvm/Support/Casting.h"
71
#include "llvm/Support/Compiler.h"
72
#include "llvm/Support/DOTGraphTraits.h"
73
#include "llvm/Support/ErrorHandling.h"
74
#include "llvm/Support/GraphWriter.h"
75
#include "llvm/Support/SaveAndRestore.h"
76
#include "llvm/Support/raw_ostream.h"
77
#include <cassert>
78
#include <cstdint>
79
#include <memory>
80
#include <string>
81
#include <tuple>
82
#include <utility>
83
#include <vector>
84
85
using namespace clang;
86
using namespace ento;
87
88
#define DEBUG_TYPE "ExprEngine"
89
90
STATISTIC(NumRemoveDeadBindings,
91
            "The # of times RemoveDeadBindings is called");
92
STATISTIC(NumMaxBlockCountReached,
93
            "The # of aborted paths due to reaching the maximum block count in "
94
            "a top level function");
95
STATISTIC(NumMaxBlockCountReachedInInlined,
96
            "The # of aborted paths due to reaching the maximum block count in "
97
            "an inlined function");
98
STATISTIC(NumTimesRetriedWithoutInlining,
99
            "The # of times we re-evaluated a call without inlining");
100
101
//===----------------------------------------------------------------------===//
102
// Internal program state traits.
103
//===----------------------------------------------------------------------===//
104
105
namespace {
106
107
// When modeling a C++ constructor, for a variety of reasons we need to track
108
// the location of the object for the duration of its ConstructionContext.
109
// ObjectsUnderConstruction maps statements within the construction context
110
// to the object's location, so that on every such statement the location
111
// could have been retrieved.
112
113
/// ConstructedObjectKey is used for being able to find the path-sensitive
114
/// memory region of a freshly constructed object while modeling the AST node
115
/// that syntactically represents the object that is being constructed.
116
/// Semantics of such nodes may sometimes require access to the region that's
117
/// not otherwise present in the program state, or to the very fact that
118
/// the construction context was present and contained references to these
119
/// AST nodes.
120
class ConstructedObjectKey {
121
  typedef std::pair<ConstructionContextItem, const LocationContext *>
122
      ConstructedObjectKeyImpl;
123
124
  const ConstructedObjectKeyImpl Impl;
125
126
0
  const void *getAnyASTNodePtr() const {
127
0
    if (const Stmt *S = getItem().getStmtOrNull())
128
0
      return S;
129
0
    else
130
0
      return getItem().getCXXCtorInitializer();
131
0
  }
132
133
public:
134
  explicit ConstructedObjectKey(const ConstructionContextItem &Item,
135
                       const LocationContext *LC)
136
300k
      : Impl(Item, LC) {}
137
138
619
  const ConstructionContextItem &getItem() const { return Impl.first; }
139
63.9k
  const LocationContext *getLocationContext() const { return Impl.second; }
140
141
40
  ASTContext &getASTContext() const {
142
40
    return getLocationContext()->getDecl()->getASTContext();
143
40
  }
144
145
  void printJson(llvm::raw_ostream &Out, PrinterHelper *Helper,
146
40
                 PrintingPolicy &PP) const {
147
40
    const Stmt *S = getItem().getStmtOrNull();
148
40
    const CXXCtorInitializer *I = nullptr;
149
40
    if (!S)
150
5
      I = getItem().getCXXCtorInitializer();
151
152
40
    if (S)
153
35
      Out << "\"stmt_id\": " << S->getID(getASTContext());
154
5
    else
155
5
      Out << "\"init_id\": " << I->getID(getASTContext());
156
157
    // Kind
158
40
    Out << ", \"kind\": \"" << getItem().getKindAsString()
159
40
        << "\", \"argument_index\": ";
160
161
40
    if (getItem().getKind() == ConstructionContextItem::ArgumentKind)
162
0
      Out << getItem().getIndex();
163
40
    else
164
40
      Out << "null";
165
166
    // Pretty-print
167
40
    Out << ", \"pretty\": ";
168
169
40
    if (S) {
170
35
      S->printJson(Out, Helper, PP, /*AddQuotes=*/true);
171
5
    } else {
172
5
      Out << '\"' << I->getAnyMember()->getDeclName() << '\"';
173
5
    }
174
40
  }
175
176
103k
  void Profile(llvm::FoldingSetNodeID &ID) const {
177
103k
    ID.Add(Impl.first);
178
103k
    ID.AddPointer(Impl.second);
179
103k
  }
180
181
402k
  bool operator==(const ConstructedObjectKey &RHS) const {
182
402k
    return Impl == RHS.Impl;
183
402k
  }
184
185
219k
  bool operator<(const ConstructedObjectKey &RHS) const {
186
219k
    return Impl < RHS.Impl;
187
219k
  }
188
};
189
} // namespace
190
191
typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>
192
    ObjectsUnderConstructionMap;
193
REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction,
194
                                 ObjectsUnderConstructionMap)
195
196
//===----------------------------------------------------------------------===//
197
// Engine construction and deletion.
198
//===----------------------------------------------------------------------===//
199
200
static const char* TagProviderName = "ExprEngine";
201
202
ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU,
203
                       AnalysisManager &mgr,
204
                       SetOfConstDecls *VisitedCalleesIn,
205
                       FunctionSummariesTy *FS,
206
                       InliningModes HowToInlineIn)
207
    : CTU(CTU), AMgr(mgr),
208
      AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
209
      Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()),
210
      StateMgr(getContext(), mgr.getStoreManagerCreator(),
211
               mgr.getConstraintManagerCreator(), G.getAllocator(),
212
               this),
213
      SymMgr(StateMgr.getSymbolManager()),
214
      MRMgr(StateMgr.getRegionManager()),
215
      svalBuilder(StateMgr.getSValBuilder()),
216
      ObjCNoRet(mgr.getASTContext()),
217
      BR(mgr, *this),
218
      VisitedCallees(VisitedCalleesIn),
219
      HowToInline(HowToInlineIn)
220
13.7k
  {
221
13.7k
  unsigned TrimInterval = mgr.options.GraphTrimInterval;
222
13.7k
  if (TrimInterval != 0) {
223
    // Enable eager node reclamation when constructing the ExplodedGraph.
224
13.7k
    G.enableNodeReclamation(TrimInterval);
225
13.7k
  }
226
13.7k
}
227
228
//===----------------------------------------------------------------------===//
229
// Utility methods.
230
//===----------------------------------------------------------------------===//
231
232
13.6k
ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
233
13.6k
  ProgramStateRef state = StateMgr.getInitialState(InitLoc);
234
13.6k
  const Decl *D = InitLoc->getDecl();
235
236
  // Preconditions.
237
  // FIXME: It would be nice if we had a more general mechanism to add
238
  // such preconditions.  Some day.
239
13.6k
  do {
240
13.6k
    if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
241
      // Precondition: the first argument of 'main' is an integer guaranteed
242
      //  to be > 0.
243
12.4k
      const IdentifierInfo *II = FD->getIdentifier();
244
12.4k
      if (!II || 
!(11.1k
II->getName() == "main"11.1k
&&
FD->getNumParams() > 059
))
245
12.4k
        break;
246
247
5
      const ParmVarDecl *PD = FD->getParamDecl(0);
248
5
      QualType T = PD->getType();
249
5
      const auto *BT = dyn_cast<BuiltinType>(T);
250
5
      if (!BT || !BT->isInteger())
251
0
        break;
252
253
5
      const MemRegion *R = state->getRegion(PD, InitLoc);
254
5
      if (!R)
255
0
        break;
256
257
5
      SVal V = state->getSVal(loc::MemRegionVal(R));
258
5
      SVal Constraint_untested = evalBinOp(state, BO_GT, V,
259
5
                                           svalBuilder.makeZeroVal(T),
260
5
                                           svalBuilder.getConditionType());
261
262
5
      Optional<DefinedOrUnknownSVal> Constraint =
263
5
          Constraint_untested.getAs<DefinedOrUnknownSVal>();
264
265
5
      if (!Constraint)
266
0
        break;
267
268
5
      if (ProgramStateRef newState = state->assume(*Constraint, true))
269
5
        state = newState;
270
5
    }
271
1.24k
    break;
272
0
  }
273
0
  while (false);
274
275
1.01k
  if (const auto *
MD0
= dyn_cast<ObjCMethodDecl>(D)) {
276
    // Precondition: 'self' is always non-null upon entry to an Objective-C
277
    // method.
278
1.01k
    const ImplicitParamDecl *SelfD = MD->getSelfDecl();
279
1.01k
    const MemRegion *R = state->getRegion(SelfD, InitLoc);
280
1.01k
    SVal V = state->getSVal(loc::MemRegionVal(R));
281
282
1.01k
    if (Optional<Loc> LV = V.getAs<Loc>()) {
283
      // Assume that the pointer value in 'self' is non-null.
284
1.01k
      state = state->assume(*LV, true);
285
1.01k
      assert(state && "'self' cannot be null");
286
1.01k
    }
287
1.01k
  }
288
289
1.44k
  if (const auto *
MD0
= dyn_cast<CXXMethodDecl>(D)) {
290
1.44k
    if (!MD->isStatic()) {
291
      // Precondition: 'this' is always non-null upon entry to the
292
      // top-level function.  This is our starting assumption for
293
      // analyzing an "open" program.
294
1.43k
      const StackFrameContext *SFC = InitLoc->getStackFrame();
295
1.43k
      if (SFC->getParent() == nullptr) {
296
1.43k
        loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC);
297
1.43k
        SVal V = state->getSVal(L);
298
1.43k
        if (Optional<Loc> LV = V.getAs<Loc>()) {
299
1.43k
          state = state->assume(*LV, true);
300
1.43k
          assert(state && "'this' cannot be null");
301
1.43k
        }
302
1.43k
      }
303
1.43k
    }
304
1.44k
  }
305
306
13.6k
  return state;
307
13.6k
}
308
309
ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded(
310
    ProgramStateRef State, const LocationContext *LC,
311
    const Expr *InitWithAdjustments, const Expr *Result,
312
62.6k
    const SubRegion **OutRegionWithAdjustments) {
313
  // FIXME: This function is a hack that works around the quirky AST
314
  // we're often having with respect to C++ temporaries. If only we modelled
315
  // the actual execution order of statements properly in the CFG,
316
  // all the hassle with adjustments would not be necessary,
317
  // and perhaps the whole function would be removed.
318
62.6k
  SVal InitValWithAdjustments = State->getSVal(InitWithAdjustments, LC);
319
62.6k
  if (!Result) {
320
    // If we don't have an explicit result expression, we're in "if needed"
321
    // mode. Only create a region if the current value is a NonLoc.
322
53.6k
    if (!InitValWithAdjustments.getAs<NonLoc>()) {
323
53.5k
      if (OutRegionWithAdjustments)
324
41.4k
        *OutRegionWithAdjustments = nullptr;
325
53.5k
      return State;
326
53.5k
    }
327
48
    Result = InitWithAdjustments;
328
9.04k
  } else {
329
    // We need to create a region no matter what. For sanity, make sure we don't
330
    // try to stuff a Loc into a non-pointer temporary region.
331
9.04k
    assert(!InitValWithAdjustments.getAs<Loc>() ||
332
9.04k
           Loc::isLocType(Result->getType()) ||
333
9.04k
           Result->getType()->isMemberPointerType());
334
9.04k
  }
335
336
9.09k
  ProgramStateManager &StateMgr = State->getStateManager();
337
9.09k
  MemRegionManager &MRMgr = StateMgr.getRegionManager();
338
9.09k
  StoreManager &StoreMgr = StateMgr.getStoreManager();
339
340
  // MaterializeTemporaryExpr may appear out of place, after a few field and
341
  // base-class accesses have been made to the object, even though semantically
342
  // it is the whole object that gets materialized and lifetime-extended.
343
  //
344
  // For example:
345
  //
346
  //   `-MaterializeTemporaryExpr
347
  //     `-MemberExpr
348
  //       `-CXXTemporaryObjectExpr
349
  //
350
  // instead of the more natural
351
  //
352
  //   `-MemberExpr
353
  //     `-MaterializeTemporaryExpr
354
  //       `-CXXTemporaryObjectExpr
355
  //
356
  // Use the usual methods for obtaining the expression of the base object,
357
  // and record the adjustments that we need to make to obtain the sub-object
358
  // that the whole expression 'Ex' refers to. This trick is usual,
359
  // in the sense that CodeGen takes a similar route.
360
361
9.09k
  SmallVector<const Expr *, 2> CommaLHSs;
362
9.09k
  SmallVector<SubobjectAdjustment, 2> Adjustments;
363
364
9.09k
  const Expr *Init = InitWithAdjustments->skipRValueSubobjectAdjustments(
365
9.09k
      CommaLHSs, Adjustments);
366
367
  // Take the region for Init, i.e. for the whole object. If we do not remember
368
  // the region in which the object originally was constructed, come up with
369
  // a new temporary region out of thin air and copy the contents of the object
370
  // (which are currently present in the Environment, because Init is an rvalue)
371
  // into that region. This is not correct, but it is better than nothing.
372
9.09k
  const TypedValueRegion *TR = nullptr;
373
9.09k
  if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) {
374
9.00k
    if (Optional<SVal> V = getObjectUnderConstruction(State, MT, LC)) {
375
8.42k
      State = finishObjectConstruction(State, MT, LC);
376
8.42k
      State = State->BindExpr(Result, LC, *V);
377
8.42k
      return State;
378
577
    } else {
379
577
      StorageDuration SD = MT->getStorageDuration();
380
      // If this object is bound to a reference with static storage duration, we
381
      // put it in a different region to prevent "address leakage" warnings.
382
577
      if (SD == SD_Static || 
SD == SD_Thread576
) {
383
1
        TR = MRMgr.getCXXStaticTempObjectRegion(Init);
384
576
      } else {
385
576
        TR = MRMgr.getCXXTempObjectRegion(Init, LC);
386
576
      }
387
577
    }
388
86
  } else {
389
86
    TR = MRMgr.getCXXTempObjectRegion(Init, LC);
390
86
  }
391
392
663
  SVal Reg = loc::MemRegionVal(TR);
393
663
  SVal BaseReg = Reg;
394
395
  // Make the necessary adjustments to obtain the sub-object.
396
668
  for (auto I = Adjustments.rbegin(), E = Adjustments.rend(); I != E; 
++I5
) {
397
5
    const SubobjectAdjustment &Adj = *I;
398
5
    switch (Adj.Kind) {
399
1
    case SubobjectAdjustment::DerivedToBaseAdjustment:
400
1
      Reg = StoreMgr.evalDerivedToBase(Reg, Adj.DerivedToBase.BasePath);
401
1
      break;
402
4
    case SubobjectAdjustment::FieldAdjustment:
403
4
      Reg = StoreMgr.getLValueField(Adj.Field, Reg);
404
4
      break;
405
0
    case SubobjectAdjustment::MemberPointerAdjustment:
406
      // FIXME: Unimplemented.
407
0
      State = State->invalidateRegions(Reg, InitWithAdjustments,
408
0
                                       currBldrCtx->blockCount(), LC, true,
409
0
                                       nullptr, nullptr, nullptr);
410
0
      return State;
411
5
    }
412
5
  }
413
414
  // What remains is to copy the value of the object to the new region.
415
  // FIXME: In other words, what we should always do is copy value of the
416
  // Init expression (which corresponds to the bigger object) to the whole
417
  // temporary region TR. However, this value is often no longer present
418
  // in the Environment. If it has disappeared, we instead invalidate TR.
419
  // Still, what we can do is assign the value of expression Ex (which
420
  // corresponds to the sub-object) to the TR's sub-region Reg. At least,
421
  // values inside Reg would be correct.
422
663
  SVal InitVal = State->getSVal(Init, LC);
423
663
  if (InitVal.isUnknown()) {
424
202
    InitVal = getSValBuilder().conjureSymbolVal(Result, LC, Init->getType(),
425
202
                                                currBldrCtx->blockCount());
426
202
    State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
427
428
    // Then we'd need to take the value that certainly exists and bind it
429
    // over.
430
202
    if (InitValWithAdjustments.isUnknown()) {
431
      // Try to recover some path sensitivity in case we couldn't
432
      // compute the value.
433
202
      InitValWithAdjustments = getSValBuilder().conjureSymbolVal(
434
202
          Result, LC, InitWithAdjustments->getType(),
435
202
          currBldrCtx->blockCount());
436
202
    }
437
202
    State =
438
202
        State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false);
439
461
  } else {
440
461
    State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
441
461
  }
442
443
  // The result expression would now point to the correct sub-region of the
444
  // newly created temporary region. Do this last in order to getSVal of Init
445
  // correctly in case (Result == Init).
446
663
  if (Result->isGLValue()) {
447
615
    State = State->BindExpr(Result, LC, Reg);
448
48
  } else {
449
48
    State = State->BindExpr(Result, LC, InitValWithAdjustments);
450
48
  }
451
452
  // Notify checkers once for two bindLoc()s.
453
663
  State = processRegionChange(State, TR, LC);
454
455
663
  if (OutRegionWithAdjustments)
456
48
    *OutRegionWithAdjustments = cast<SubRegion>(Reg.getAsRegion());
457
663
  return State;
458
663
}
459
460
ProgramStateRef
461
ExprEngine::addObjectUnderConstruction(ProgramStateRef State,
462
                                       const ConstructionContextItem &Item,
463
38.3k
                                       const LocationContext *LC, SVal V) {
464
38.3k
  ConstructedObjectKey Key(Item, LC->getStackFrame());
465
  // FIXME: Currently the state might already contain the marker due to
466
  // incorrect handling of temporaries bound to default parameters.
467
38.3k
  assert(!State->get<ObjectsUnderConstruction>(Key) ||
468
38.3k
         Key.getItem().getKind() ==
469
38.3k
             ConstructionContextItem::TemporaryDestructorKind);
470
38.3k
  return State->set<ObjectsUnderConstruction>(Key, V);
471
38.3k
}
472
473
Optional<SVal>
474
ExprEngine::getObjectUnderConstruction(ProgramStateRef State,
475
                                       const ConstructionContextItem &Item,
476
221k
                                       const LocationContext *LC) {
477
221k
  ConstructedObjectKey Key(Item, LC->getStackFrame());
478
221k
  return Optional<SVal>::create(State->get<ObjectsUnderConstruction>(Key));
479
221k
}
480
481
ProgramStateRef
482
ExprEngine::finishObjectConstruction(ProgramStateRef State,
483
                                     const ConstructionContextItem &Item,
484
38.5k
                                     const LocationContext *LC) {
485
38.5k
  ConstructedObjectKey Key(Item, LC->getStackFrame());
486
38.5k
  assert(State->contains<ObjectsUnderConstruction>(Key));
487
38.5k
  return State->remove<ObjectsUnderConstruction>(Key);
488
38.5k
}
489
490
ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State,
491
                                            const CXXBindTemporaryExpr *BTE,
492
588
                                            const LocationContext *LC) {
493
588
  ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
494
  // FIXME: Currently the state might already contain the marker due to
495
  // incorrect handling of temporaries bound to default parameters.
496
588
  return State->set<ObjectsUnderConstruction>(Key, UnknownVal());
497
588
}
498
499
ProgramStateRef
500
ExprEngine::cleanupElidedDestructor(ProgramStateRef State,
501
                                    const CXXBindTemporaryExpr *BTE,
502
416
                                    const LocationContext *LC) {
503
416
  ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
504
416
  assert(State->contains<ObjectsUnderConstruction>(Key));
505
416
  return State->remove<ObjectsUnderConstruction>(Key);
506
416
}
507
508
bool ExprEngine::isDestructorElided(ProgramStateRef State,
509
                                    const CXXBindTemporaryExpr *BTE,
510
1.06k
                                    const LocationContext *LC) {
511
1.06k
  ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
512
1.06k
  return State->contains<ObjectsUnderConstruction>(Key);
513
1.06k
}
514
515
bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State,
516
                                               const LocationContext *FromLC,
517
63.0k
                                               const LocationContext *ToLC) {
518
63.0k
  const LocationContext *LC = FromLC;
519
126k
  while (LC != ToLC) {
520
63.0k
    assert(LC && "ToLC must be a parent of FromLC!");
521
63.0k
    for (auto I : State->get<ObjectsUnderConstruction>())
522
31.7k
      if (I.first.getLocationContext() == LC)
523
0
        return false;
524
525
63.0k
    LC = LC->getParent();
526
63.0k
  }
527
63.0k
  return true;
528
63.0k
}
529
530
531
//===----------------------------------------------------------------------===//
532
// Top-level transfer function logic (Dispatcher).
533
//===----------------------------------------------------------------------===//
534
535
/// evalAssume - Called by ConstraintManager. Used to call checker-specific
536
///  logic for handling assumptions on symbolic values.
537
ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
538
736k
                                              SVal cond, bool assumption) {
539
736k
  return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
540
736k
}
541
542
ProgramStateRef
543
ExprEngine::processRegionChanges(ProgramStateRef state,
544
                                 const InvalidatedSymbols *invalidated,
545
                                 ArrayRef<const MemRegion *> Explicits,
546
                                 ArrayRef<const MemRegion *> Regions,
547
                                 const LocationContext *LCtx,
548
130k
                                 const CallEvent *Call) {
549
130k
  return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
550
130k
                                                         Explicits, Regions,
551
130k
                                                         LCtx, Call);
552
130k
}
553
554
static void
555
printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State,
556
                                  const char *NL, const LocationContext *LCtx,
557
40
                                  unsigned int Space = 0, bool IsDot = false) {
558
40
  PrintingPolicy PP =
559
40
      LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy();
560
561
40
  ++Space;
562
40
  bool HasItem = false;
563
564
  // Store the last key.
565
40
  const ConstructedObjectKey *LastKey = nullptr;
566
56
  for (const auto &I : State->get<ObjectsUnderConstruction>()) {
567
56
    const ConstructedObjectKey &Key = I.first;
568
56
    if (Key.getLocationContext() != LCtx)
569
16
      continue;
570
571
40
    if (!HasItem) {
572
34
      Out << "[" << NL;
573
34
      HasItem = true;
574
34
    }
575
576
40
    LastKey = &Key;
577
40
  }
578
579
56
  for (const auto &I : State->get<ObjectsUnderConstruction>()) {
580
56
    const ConstructedObjectKey &Key = I.first;
581
56
    SVal Value = I.second;
582
56
    if (Key.getLocationContext() != LCtx)
583
16
      continue;
584
585
40
    Indent(Out, Space, IsDot) << "{ ";
586
40
    Key.printJson(Out, nullptr, PP);
587
40
    Out << ", \"value\": \"" << Value << "\" }";
588
589
40
    if (&Key != LastKey)
590
6
      Out << ',';
591
40
    Out << NL;
592
40
  }
593
594
40
  if (HasItem)
595
34
    Indent(Out, --Space, IsDot) << ']'; // End of "location_context".
596
6
  else {
597
6
    Out << "null ";
598
6
  }
599
40
}
600
601
void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State,
602
                           const LocationContext *LCtx, const char *NL,
603
126
                           unsigned int Space, bool IsDot) const {
604
126
  Indent(Out, Space, IsDot) << "\"constructing_objects\": ";
605
606
126
  if (LCtx && 
!State->get<ObjectsUnderConstruction>().isEmpty()100
) {
607
29
    ++Space;
608
29
    Out << '[' << NL;
609
40
    LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {
610
40
      printObjectsUnderConstructionJson(Out, State, NL, LC, Space, IsDot);
611
40
    });
612
613
29
    --Space;
614
29
    Indent(Out, Space, IsDot) << "]," << NL; // End of "constructing_objects".
615
97
  } else {
616
97
    Out << "null," << NL;
617
97
  }
618
619
126
  getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space,
620
126
                                                   IsDot);
621
126
}
622
623
13.6k
void ExprEngine::processEndWorklist() {
624
13.6k
  getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
625
13.6k
}
626
627
void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
628
974k
                                   unsigned StmtIdx, NodeBuilderContext *Ctx) {
629
974k
  PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
630
974k
  currStmtIdx = StmtIdx;
631
974k
  currBldrCtx = Ctx;
632
633
974k
  switch (E.getKind()) {
634
959k
    case CFGElement::Statement:
635
959k
    case CFGElement::Constructor:
636
959k
    case CFGElement::CXXRecordTypedCall:
637
959k
      ProcessStmt(E.castAs<CFGStmt>().getStmt(), Pred);
638
959k
      return;
639
11.6k
    case CFGElement::Initializer:
640
11.6k
      ProcessInitializer(E.castAs<CFGInitializer>(), Pred);
641
11.6k
      return;
642
1.03k
    case CFGElement::NewAllocator:
643
1.03k
      ProcessNewAllocator(E.castAs<CFGNewAllocator>().getAllocatorExpr(),
644
1.03k
                          Pred);
645
1.03k
      return;
646
1.93k
    case CFGElement::AutomaticObjectDtor:
647
1.93k
    case CFGElement::DeleteDtor:
648
1.93k
    case CFGElement::BaseDtor:
649
1.93k
    case CFGElement::MemberDtor:
650
1.93k
    case CFGElement::TemporaryDtor:
651
1.93k
      ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
652
1.93k
      return;
653
144
    case CFGElement::LoopExit:
654
144
      ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred);
655
144
      return;
656
0
    case CFGElement::LifetimeEnds:
657
0
    case CFGElement::ScopeBegin:
658
0
    case CFGElement::ScopeEnd:
659
0
      return;
660
974k
  }
661
974k
}
662
663
static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
664
                                     const Stmt *S,
665
                                     const ExplodedNode *Pred,
666
959k
                                     const LocationContext *LC) {
667
  // Are we never purging state values?
668
959k
  if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
669
739
    return false;
670
671
  // Is this the beginning of a basic block?
672
959k
  if (Pred->getLocation().getAs<BlockEntrance>())
673
108k
    return true;
674
675
  // Is this on a non-expression?
676
850k
  if (!isa<Expr>(S))
677
50.5k
    return true;
678
679
  // Run before processing a call.
680
800k
  if (CallEvent::isCallStmt(S))
681
101k
    return true;
682
683
  // Is this an expression that is consumed by another expression?  If so,
684
  // postpone cleaning out the state.
685
698k
  ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
686
698k
  return !PM.isConsumedExpr(cast<Expr>(S));
687
698k
}
688
689
void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
690
                            const Stmt *ReferenceStmt,
691
                            const LocationContext *LC,
692
                            const Stmt *DiagnosticStmt,
693
360k
                            ProgramPoint::Kind K) {
694
360k
  assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
695
360k
          ReferenceStmt == nullptr || isa<ReturnStmt>(ReferenceStmt))
696
360k
          && "PostStmt is not generally supported by the SymbolReaper yet");
697
360k
  assert(LC && "Must pass the current (or expiring) LocationContext");
698
699
360k
  if (!DiagnosticStmt) {
700
301k
    DiagnosticStmt = ReferenceStmt;
701
301k
    assert(DiagnosticStmt && "Required for clearing a LocationContext");
702
301k
  }
703
704
360k
  NumRemoveDeadBindings++;
705
360k
  ProgramStateRef CleanedState = Pred->getState();
706
707
  // LC is the location context being destroyed, but SymbolReaper wants a
708
  // location context that is still live. (If this is the top-level stack
709
  // frame, this will be null.)
710
360k
  if (!ReferenceStmt) {
711
52.5k
    assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
712
52.5k
           "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
713
52.5k
    LC = LC->getParent();
714
52.5k
  }
715
716
346k
  const StackFrameContext *SFC = LC ? LC->getStackFrame() : 
nullptr14.7k
;
717
360k
  SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
718
719
128k
  for (auto I : CleanedState->get<ObjectsUnderConstruction>()) {
720
128k
    if (SymbolRef Sym = I.second.getAsSymbol())
721
2.04k
      SymReaper.markLive(Sym);
722
128k
    if (const MemRegion *MR = I.second.getAsRegion())
723
116k
      SymReaper.markLive(MR);
724
128k
  }
725
726
360k
  getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
727
728
  // Create a state in which dead bindings are removed from the environment
729
  // and the store. TODO: The function should just return new env and store,
730
  // not a new state.
731
360k
  CleanedState = StateMgr.removeDeadBindingsFromEnvironmentAndStore(
732
360k
      CleanedState, SFC, SymReaper);
733
734
  // Process any special transfer function for dead symbols.
735
  // A tag to track convenience transitions, which can be removed at cleanup.
736
360k
  static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node");
737
  // Call checkers with the non-cleaned state so that they could query the
738
  // values of the soon to be dead symbols.
739
360k
  ExplodedNodeSet CheckedSet;
740
360k
  getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
741
360k
                                                DiagnosticStmt, *this, K);
742
743
  // For each node in CheckedSet, generate CleanedNodes that have the
744
  // environment, the store, and the constraints cleaned up but have the
745
  // user-supplied states as the predecessors.
746
360k
  StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
747
360k
  for (const auto I : CheckedSet) {
748
360k
    ProgramStateRef CheckerState = I->getState();
749
750
    // The constraint manager has not been cleaned up yet, so clean up now.
751
360k
    CheckerState =
752
360k
        getConstraintManager().removeDeadBindings(CheckerState, SymReaper);
753
754
360k
    assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
755
360k
           "Checkers are not allowed to modify the Environment as a part of "
756
360k
           "checkDeadSymbols processing.");
757
360k
    assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
758
360k
           "Checkers are not allowed to modify the Store as a part of "
759
360k
           "checkDeadSymbols processing.");
760
761
    // Create a state based on CleanedState with CheckerState GDM and
762
    // generate a transition to that state.
763
360k
    ProgramStateRef CleanedCheckerSt =
764
360k
        StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
765
360k
    Bldr.generateNode(DiagnosticStmt, I, CleanedCheckerSt, &cleanupTag, K);
766
360k
  }
767
360k
}
768
769
959k
void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) {
770
  // Reclaim any unnecessary nodes in the ExplodedGraph.
771
959k
  G.reclaimRecentlyAllocatedNodes();
772
773
959k
  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
774
959k
                                currStmt->getBeginLoc(),
775
959k
                                "Error evaluating statement");
776
777
  // Remove dead bindings and symbols.
778
959k
  ExplodedNodeSet CleanedStates;
779
959k
  if (shouldRemoveDeadBindings(AMgr, currStmt, Pred,
780
301k
                               Pred->getLocationContext())) {
781
301k
    removeDead(Pred, CleanedStates, currStmt,
782
301k
                                    Pred->getLocationContext());
783
301k
  } else
784
657k
    CleanedStates.Add(Pred);
785
786
  // Visit the statement.
787
959k
  ExplodedNodeSet Dst;
788
957k
  for (const auto I : CleanedStates) {
789
957k
    ExplodedNodeSet DstI;
790
    // Visit the statement.
791
957k
    Visit(currStmt, I, DstI);
792
957k
    Dst.insert(DstI);
793
957k
  }
794
795
  // Enqueue the new nodes onto the work list.
796
959k
  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
797
959k
}
798
799
144
void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) {
800
144
  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
801
144
                                S->getBeginLoc(),
802
144
                                "Error evaluating end of the loop");
803
144
  ExplodedNodeSet Dst;
804
144
  Dst.Add(Pred);
805
144
  NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
806
144
  ProgramStateRef NewState = Pred->getState();
807
808
144
  if(AMgr.options.ShouldUnrollLoops)
809
144
    NewState = processLoopEnd(S, NewState);
810
811
144
  LoopExit PP(S, Pred->getLocationContext());
812
144
  Bldr.generateNode(PP, NewState, Pred);
813
  // Enqueue the new nodes onto the work list.
814
144
  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
815
144
}
816
817
void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit,
818
11.6k
                                    ExplodedNode *Pred) {
819
11.6k
  const CXXCtorInitializer *BMI = CFGInit.getInitializer();
820
11.6k
  const Expr *Init = BMI->getInit()->IgnoreImplicit();
821
11.6k
  const LocationContext *LC = Pred->getLocationContext();
822
823
11.6k
  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
824
11.6k
                                BMI->getSourceLocation(),
825
11.6k
                                "Error evaluating initializer");
826
827
  // We don't clean up dead bindings here.
828
11.6k
  const auto *stackFrame = cast<StackFrameContext>(Pred->getLocationContext());
829
11.6k
  const auto *decl = cast<CXXConstructorDecl>(stackFrame->getDecl());
830
831
11.6k
  ProgramStateRef State = Pred->getState();
832
11.6k
  SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));
833
834
11.6k
  ExplodedNodeSet Tmp;
835
11.6k
  SVal FieldLoc;
836
837
  // Evaluate the initializer, if necessary
838
11.6k
  if (BMI->isAnyMemberInitializer()) {
839
    // Constructors build the object directly in the field,
840
    // but non-objects must be copied in from the initializer.
841
10.8k
    if (getObjectUnderConstruction(State, BMI, LC)) {
842
      // The field was directly constructed, so there is no need to bind.
843
      // But we still need to stop tracking the object under construction.
844
2.55k
      State = finishObjectConstruction(State, BMI, LC);
845
2.55k
      NodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
846
2.55k
      PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr);
847
2.55k
      Bldr.generateNode(PS, State, Pred);
848
8.31k
    } else {
849
8.31k
      const ValueDecl *Field;
850
8.31k
      if (BMI->isIndirectMemberInitializer()) {
851
4
        Field = BMI->getIndirectMember();
852
4
        FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);
853
8.31k
      } else {
854
8.31k
        Field = BMI->getMember();
855
8.31k
        FieldLoc = State->getLValue(BMI->getMember(), thisVal);
856
8.31k
      }
857
858
8.31k
      SVal InitVal;
859
8.31k
      if (Init->getType()->isArrayType()) {
860
        // Handle arrays of trivial type. We can represent this with a
861
        // primitive load/copy from the base array region.
862
43
        const ArraySubscriptExpr *ASE;
863
43
        while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))
864
0
          Init = ASE->getBase()->IgnoreImplicit();
865
866
43
        SVal LValue = State->getSVal(Init, stackFrame);
867
43
        if (!Field->getType()->isReferenceType())
868
39
          if (Optional<Loc> LValueLoc = LValue.getAs<Loc>())
869
8
            InitVal = State->getSVal(*LValueLoc);
870
871
        // If we fail to get the value for some reason, use a symbolic value.
872
43
        if (InitVal.isUnknownOrUndef()) {
873
35
          SValBuilder &SVB = getSValBuilder();
874
35
          InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame,
875
35
                                         Field->getType(),
876
35
                                         currBldrCtx->blockCount());
877
35
        }
878
8.27k
      } else {
879
8.27k
        InitVal = State->getSVal(BMI->getInit(), stackFrame);
880
8.27k
      }
881
882
8.31k
      PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
883
8.31k
      evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);
884
8.31k
    }
885
746
  } else {
886
746
    assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
887
746
    Tmp.insert(Pred);
888
    // We already did all the work when visiting the CXXConstructExpr.
889
746
  }
890
891
  // Construct PostInitializer nodes whether the state changed or not,
892
  // so that the diagnostics don't get confused.
893
11.6k
  PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
894
11.6k
  ExplodedNodeSet Dst;
895
11.6k
  NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
896
11.5k
  for (const auto I : Tmp) {
897
11.5k
    ProgramStateRef State = I->getState();
898
11.5k
    Bldr.generateNode(PP, State, I);
899
11.5k
  }
900
901
  // Enqueue the new nodes onto the work list.
902
11.6k
  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
903
11.6k
}
904
905
void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
906
1.93k
                                     ExplodedNode *Pred) {
907
1.93k
  ExplodedNodeSet Dst;
908
1.93k
  switch (D.getKind()) {
909
600
  case CFGElement::AutomaticObjectDtor:
910
600
    ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);
911
600
    break;
912
128
  case CFGElement::BaseDtor:
913
128
    ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst);
914
128
    break;
915
54
  case CFGElement::MemberDtor:
916
54
    ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst);
917
54
    break;
918
1.06k
  case CFGElement::TemporaryDtor:
919
1.06k
    ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst);
920
1.06k
    break;
921
91
  case CFGElement::DeleteDtor:
922
91
    ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst);
923
91
    break;
924
0
  default:
925
0
    llvm_unreachable("Unexpected dtor kind.");
926
1.93k
  }
927
928
  // Enqueue the new nodes onto the work list.
929
1.93k
  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
930
1.93k
}
931
932
void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE,
933
1.03k
                                     ExplodedNode *Pred) {
934
1.03k
  ExplodedNodeSet Dst;
935
1.03k
  AnalysisManager &AMgr = getAnalysisManager();
936
1.03k
  AnalyzerOptions &Opts = AMgr.options;
937
  // TODO: We're not evaluating allocators for all cases just yet as
938
  // we're not handling the return value correctly, which causes false
939
  // positives when the alpha.cplusplus.NewDeleteLeaks check is on.
940
1.03k
  if (Opts.MayInlineCXXAllocator)
941
1.02k
    VisitCXXNewAllocatorCall(NE, Pred, Dst);
942
7
  else {
943
7
    NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
944
7
    const LocationContext *LCtx = Pred->getLocationContext();
945
7
    PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx);
946
7
    Bldr.generateNode(PP, Pred->getState(), Pred);
947
7
  }
948
1.03k
  Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
949
1.03k
}
950
951
void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
952
                                         ExplodedNode *Pred,
953
600
                                         ExplodedNodeSet &Dst) {
954
600
  const VarDecl *varDecl = Dtor.getVarDecl();
955
600
  QualType varType = varDecl->getType();
956
957
600
  ProgramStateRef state = Pred->getState();
958
600
  SVal dest = state->getLValue(varDecl, Pred->getLocationContext());
959
600
  const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();
960
961
600
  if (varType->isReferenceType()) {
962
104
    const MemRegion *ValueRegion = state->getSVal(Region).getAsRegion();
963
104
    if (!ValueRegion) {
964
      // FIXME: This should not happen. The language guarantees a presence
965
      // of a valid initializer here, so the reference shall not be undefined.
966
      // It seems that we're calling destructors over variables that
967
      // were not initialized yet.
968
4
      return;
969
4
    }
970
100
    Region = ValueRegion->getBaseRegion();
971
100
    varType = cast<TypedValueRegion>(Region)->getValueType();
972
100
  }
973
974
  // FIXME: We need to run the same destructor on every element of the array.
975
  // This workaround will just run the first destructor (which will still
976
  // invalidate the entire array).
977
596
  EvalCallOptions CallOpts;
978
596
  Region = makeZeroElementRegion(state, loc::MemRegionVal(Region), varType,
979
596
                                 CallOpts.IsArrayCtorOrDtor).getAsRegion();
980
981
596
  VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(),
982
596
                     /*IsBase=*/false, Pred, Dst, CallOpts);
983
596
}
984
985
void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor,
986
                                   ExplodedNode *Pred,
987
91
                                   ExplodedNodeSet &Dst) {
988
91
  ProgramStateRef State = Pred->getState();
989
91
  const LocationContext *LCtx = Pred->getLocationContext();
990
91
  const CXXDeleteExpr *DE = Dtor.getDeleteExpr();
991
91
  const Stmt *Arg = DE->getArgument();
992
91
  QualType DTy = DE->getDestroyedType();
993
91
  SVal ArgVal = State->getSVal(Arg, LCtx);
994
995
  // If the argument to delete is known to be a null value,
996
  // don't run destructor.
997
91
  if (State->isNull(ArgVal).isConstrainedTrue()) {
998
9
    QualType BTy = getContext().getBaseElementType(DTy);
999
9
    const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl();
1000
9
    const CXXDestructorDecl *Dtor = RD->getDestructor();
1001
1002
9
    PostImplicitCall PP(Dtor, DE->getBeginLoc(), LCtx);
1003
9
    NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1004
9
    Bldr.generateNode(PP, Pred->getState(), Pred);
1005
9
    return;
1006
9
  }
1007
1008
82
  EvalCallOptions CallOpts;
1009
82
  const MemRegion *ArgR = ArgVal.getAsRegion();
1010
82
  if (DE->isArrayForm()) {
1011
    // FIXME: We need to run the same destructor on every element of the array.
1012
    // This workaround will just run the first destructor (which will still
1013
    // invalidate the entire array).
1014
12
    CallOpts.IsArrayCtorOrDtor = true;
1015
    // Yes, it may even be a multi-dimensional array.
1016
20
    while (const auto *AT = getContext().getAsArrayType(DTy))
1017
8
      DTy = AT->getElementType();
1018
12
    if (ArgR)
1019
12
      ArgR = getStoreManager().GetElementZeroRegion(cast<SubRegion>(ArgR), DTy);
1020
12
  }
1021
1022
82
  VisitCXXDestructor(DTy, ArgR, DE, /*IsBase=*/false, Pred, Dst, CallOpts);
1023
82
}
1024
1025
void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
1026
128
                                 ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1027
128
  const LocationContext *LCtx = Pred->getLocationContext();
1028
1029
128
  const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
1030
128
  Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,
1031
128
                                            LCtx->getStackFrame());
1032
128
  SVal ThisVal = Pred->getState()->getSVal(ThisPtr);
1033
1034
  // Create the base object region.
1035
128
  const CXXBaseSpecifier *Base = D.getBaseSpecifier();
1036
128
  QualType BaseTy = Base->getType();
1037
128
  SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy,
1038
128
                                                     Base->isVirtual());
1039
1040
128
  EvalCallOptions CallOpts;
1041
128
  VisitCXXDestructor(BaseTy, BaseVal.getAsRegion(), CurDtor->getBody(),
1042
128
                     /*IsBase=*/true, Pred, Dst, CallOpts);
1043
128
}
1044
1045
void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
1046
54
                                   ExplodedNode *Pred, ExplodedNodeSet &Dst) {
1047
54
  const FieldDecl *Member = D.getFieldDecl();
1048
54
  QualType T = Member->getType();
1049
54
  ProgramStateRef State = Pred->getState();
1050
54
  const LocationContext *LCtx = Pred->getLocationContext();
1051
1052
54
  const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
1053
54
  Loc ThisStorageLoc =
1054
54
      getSValBuilder().getCXXThis(CurDtor, LCtx->getStackFrame());
1055
54
  Loc ThisLoc = State->getSVal(ThisStorageLoc).castAs<Loc>();
1056
54
  SVal FieldVal = State->getLValue(Member, ThisLoc);
1057
1058
  // FIXME: We need to run the same destructor on every element of the array.
1059
  // This workaround will just run the first destructor (which will still
1060
  // invalidate the entire array).
1061
54
  EvalCallOptions CallOpts;
1062
54
  FieldVal = makeZeroElementRegion(State, FieldVal, T,
1063
54
                                   CallOpts.IsArrayCtorOrDtor);
1064
1065
54
  VisitCXXDestructor(T, FieldVal.getAsRegion(), CurDtor->getBody(),
1066
54
                     /*IsBase=*/false, Pred, Dst, CallOpts);
1067
54
}
1068
1069
void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
1070
                                      ExplodedNode *Pred,
1071
1.06k
                                      ExplodedNodeSet &Dst) {
1072
1.06k
  const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr();
1073
1.06k
  ProgramStateRef State = Pred->getState();
1074
1.06k
  const LocationContext *LC = Pred->getLocationContext();
1075
1.06k
  const MemRegion *MR = nullptr;
1076
1077
1.06k
  if (Optional<SVal> V =
1078
1.00k
          getObjectUnderConstruction(State, D.getBindTemporaryExpr(),
1079
1.00k
                                     Pred->getLocationContext())) {
1080
    // FIXME: Currently we insert temporary destructors for default parameters,
1081
    // but we don't insert the constructors, so the entry in
1082
    // ObjectsUnderConstruction may be missing.
1083
1.00k
    State = finishObjectConstruction(State, D.getBindTemporaryExpr(),
1084
1.00k
                                     Pred->getLocationContext());
1085
1.00k
    MR = V->getAsRegion();
1086
1.00k
  }
1087
1088
  // If copy elision has occurred, and the constructor corresponding to the
1089
  // destructor was elided, we need to skip the destructor as well.
1090
1.06k
  if (isDestructorElided(State, BTE, LC)) {
1091
416
    State = cleanupElidedDestructor(State, BTE, LC);
1092
416
    NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
1093
416
    PostImplicitCall PP(D.getDestructorDecl(getContext()),
1094
416
                        D.getBindTemporaryExpr()->getBeginLoc(),
1095
416
                        Pred->getLocationContext());
1096
416
    Bldr.generateNode(PP, State, Pred);
1097
416
    return;
1098
416
  }
1099
1100
645
  ExplodedNodeSet CleanDtorState;
1101
645
  StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx);
1102
645
  StmtBldr.generateNode(D.getBindTemporaryExpr(), Pred, State);
1103
1104
645
  QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType();
1105
  // FIXME: Currently CleanDtorState can be empty here due to temporaries being
1106
  // bound to default parameters.
1107
645
  assert(CleanDtorState.size() <= 1);
1108
645
  ExplodedNode *CleanPred =
1109
645
      CleanDtorState.empty() ? 
Pred0
: *CleanDtorState.begin();
1110
1111
645
  EvalCallOptions CallOpts;
1112
645
  CallOpts.IsTemporaryCtorOrDtor = true;
1113
645
  if (!MR) {
1114
    // If we have no MR, we still need to unwrap the array to avoid destroying
1115
    // the whole array at once. Regardless, we'd eventually need to model array
1116
    // destructors properly, element-by-element.
1117
70
    while (const ArrayType *AT = getContext().getAsArrayType(T)) {
1118
2
      T = AT->getElementType();
1119
2
      CallOpts.IsArrayCtorOrDtor = true;
1120
2
    }
1121
577
  } else {
1122
    // We'd eventually need to makeZeroElementRegion() trick here,
1123
    // but for now we don't have the respective construction contexts,
1124
    // so MR would always be null in this case. Do nothing for now.
1125
577
  }
1126
645
  VisitCXXDestructor(T, MR, D.getBindTemporaryExpr(),
1127
645
                     /*IsBase=*/false, CleanPred, Dst, CallOpts);
1128
645
}
1129
1130
void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
1131
                                               NodeBuilderContext &BldCtx,
1132
                                               ExplodedNode *Pred,
1133
                                               ExplodedNodeSet &Dst,
1134
                                               const CFGBlock *DstT,
1135
603
                                               const CFGBlock *DstF) {
1136
603
  BranchNodeBuilder TempDtorBuilder(Pred, Dst, BldCtx, DstT, DstF);
1137
603
  ProgramStateRef State = Pred->getState();
1138
603
  const LocationContext *LC = Pred->getLocationContext();
1139
603
  if (getObjectUnderConstruction(State, BTE, LC)) {
1140
400
    TempDtorBuilder.markInfeasible(false);
1141
400
    TempDtorBuilder.generateNode(State, true, Pred);
1142
203
  } else {
1143
203
    TempDtorBuilder.markInfeasible(true);
1144
203
    TempDtorBuilder.generateNode(State, false, Pred);
1145
203
  }
1146
603
}
1147
1148
void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,
1149
                                           ExplodedNodeSet &PreVisit,
1150
1.42k
                                           ExplodedNodeSet &Dst) {
1151
  // This is a fallback solution in case we didn't have a construction
1152
  // context when we were constructing the temporary. Otherwise the map should
1153
  // have been populated there.
1154
1.42k
  if (!getAnalysisManager().options.ShouldIncludeTemporaryDtorsInCFG) {
1155
    // In case we don't have temporary destructors in the CFG, do not mark
1156
    // the initialization - we would otherwise never clean it up.
1157
244
    Dst = PreVisit;
1158
244
    return;
1159
244
  }
1160
1.18k
  StmtNodeBuilder StmtBldr(PreVisit, Dst, *currBldrCtx);
1161
1.18k
  for (ExplodedNode *Node : PreVisit) {
1162
1.18k
    ProgramStateRef State = Node->getState();
1163
1.18k
    const LocationContext *LC = Node->getLocationContext();
1164
1.18k
    if (!getObjectUnderConstruction(State, BTE, LC)) {
1165
      // FIXME: Currently the state might also already contain the marker due to
1166
      // incorrect handling of temporaries bound to default parameters; for
1167
      // those, we currently skip the CXXBindTemporaryExpr but rely on adding
1168
      // temporary destructor nodes.
1169
577
      State = addObjectUnderConstruction(State, BTE, LC, UnknownVal());
1170
577
    }
1171
1.18k
    StmtBldr.generateNode(BTE, Node, State);
1172
1.18k
  }
1173
1.18k
}
1174
1175
ProgramStateRef ExprEngine::escapeValues(ProgramStateRef State,
1176
                                         ArrayRef<SVal> Vs,
1177
                                         PointerEscapeKind K,
1178
7.65k
                                         const CallEvent *Call) const {
1179
7.65k
  class CollectReachableSymbolsCallback final : public SymbolVisitor {
1180
7.65k
    InvalidatedSymbols &Symbols;
1181
1182
7.65k
  public:
1183
7.65k
    explicit CollectReachableSymbolsCallback(InvalidatedSymbols &Symbols)
1184
7.65k
        : Symbols(Symbols) {}
1185
1186
7.65k
    const InvalidatedSymbols &getSymbols() const { return Symbols; }
1187
1188
4.16k
    bool VisitSymbol(SymbolRef Sym) override {
1189
4.16k
      Symbols.insert(Sym);
1190
4.16k
      return true;
1191
4.16k
    }
1192
7.65k
  };
1193
7.65k
  InvalidatedSymbols Symbols;
1194
7.65k
  CollectReachableSymbolsCallback CallBack(Symbols);
1195
7.65k
  for (SVal V : Vs)
1196
7.78k
    State->scanReachableSymbols(V, CallBack);
1197
1198
7.65k
  return getCheckerManager().runCheckersForPointerEscape(
1199
7.65k
      State, CallBack.getSymbols(), Call, K, nullptr);
1200
7.65k
}
1201
1202
void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
1203
957k
                       ExplodedNodeSet &DstTop) {
1204
957k
  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
1205
957k
                                S->getBeginLoc(), "Error evaluating statement");
1206
957k
  ExplodedNodeSet Dst;
1207
957k
  StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
1208
1209
957k
  assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
1210
1211
957k
  switch (S->getStmtClass()) {
1212
    // C++, OpenMP and ARC stuff we don't support yet.
1213
1
    case Stmt::CXXDependentScopeMemberExprClass:
1214
1
    case Stmt::CXXTryStmtClass:
1215
1
    case Stmt::CXXTypeidExprClass:
1216
1
    case Stmt::CXXUuidofExprClass:
1217
1
    case Stmt::CXXFoldExprClass:
1218
1
    case Stmt::MSPropertyRefExprClass:
1219
1
    case Stmt::MSPropertySubscriptExprClass:
1220
1
    case Stmt::CXXUnresolvedConstructExprClass:
1221
1
    case Stmt::DependentScopeDeclRefExprClass:
1222
1
    case Stmt::ArrayTypeTraitExprClass:
1223
1
    case Stmt::ExpressionTraitExprClass:
1224
1
    case Stmt::UnresolvedLookupExprClass:
1225
1
    case Stmt::UnresolvedMemberExprClass:
1226
1
    case Stmt::TypoExprClass:
1227
1
    case Stmt::RecoveryExprClass:
1228
1
    case Stmt::CXXNoexceptExprClass:
1229
1
    case Stmt::PackExpansionExprClass:
1230
1
    case Stmt::SubstNonTypeTemplateParmPackExprClass:
1231
1
    case Stmt::FunctionParmPackExprClass:
1232
1
    case Stmt::CoroutineBodyStmtClass:
1233
1
    case Stmt::CoawaitExprClass:
1234
1
    case Stmt::DependentCoawaitExprClass:
1235
1
    case Stmt::CoreturnStmtClass:
1236
1
    case Stmt::CoyieldExprClass:
1237
1
    case Stmt::SEHTryStmtClass:
1238
1
    case Stmt::SEHExceptStmtClass:
1239
1
    case Stmt::SEHLeaveStmtClass:
1240
1
    case Stmt::SEHFinallyStmtClass:
1241
1
    case Stmt::OMPParallelDirectiveClass:
1242
1
    case Stmt::OMPSimdDirectiveClass:
1243
1
    case Stmt::OMPForDirectiveClass:
1244
1
    case Stmt::OMPForSimdDirectiveClass:
1245
1
    case Stmt::OMPSectionsDirectiveClass:
1246
1
    case Stmt::OMPSectionDirectiveClass:
1247
1
    case Stmt::OMPSingleDirectiveClass:
1248
1
    case Stmt::OMPMasterDirectiveClass:
1249
1
    case Stmt::OMPCriticalDirectiveClass:
1250
1
    case Stmt::OMPParallelForDirectiveClass:
1251
1
    case Stmt::OMPParallelForSimdDirectiveClass:
1252
1
    case Stmt::OMPParallelSectionsDirectiveClass:
1253
1
    case Stmt::OMPParallelMasterDirectiveClass:
1254
1
    case Stmt::OMPTaskDirectiveClass:
1255
1
    case Stmt::OMPTaskyieldDirectiveClass:
1256
1
    case Stmt::OMPBarrierDirectiveClass:
1257
1
    case Stmt::OMPTaskwaitDirectiveClass:
1258
1
    case Stmt::OMPTaskgroupDirectiveClass:
1259
1
    case Stmt::OMPFlushDirectiveClass:
1260
1
    case Stmt::OMPDepobjDirectiveClass:
1261
1
    case Stmt::OMPScanDirectiveClass:
1262
1
    case Stmt::OMPOrderedDirectiveClass:
1263
1
    case Stmt::OMPAtomicDirectiveClass:
1264
1
    case Stmt::OMPTargetDirectiveClass:
1265
1
    case Stmt::OMPTargetDataDirectiveClass:
1266
1
    case Stmt::OMPTargetEnterDataDirectiveClass:
1267
1
    case Stmt::OMPTargetExitDataDirectiveClass:
1268
1
    case Stmt::OMPTargetParallelDirectiveClass:
1269
1
    case Stmt::OMPTargetParallelForDirectiveClass:
1270
1
    case Stmt::OMPTargetUpdateDirectiveClass:
1271
1
    case Stmt::OMPTeamsDirectiveClass:
1272
1
    case Stmt::OMPCancellationPointDirectiveClass:
1273
1
    case Stmt::OMPCancelDirectiveClass:
1274
1
    case Stmt::OMPTaskLoopDirectiveClass:
1275
1
    case Stmt::OMPTaskLoopSimdDirectiveClass:
1276
1
    case Stmt::OMPMasterTaskLoopDirectiveClass:
1277
1
    case Stmt::OMPMasterTaskLoopSimdDirectiveClass:
1278
1
    case Stmt::OMPParallelMasterTaskLoopDirectiveClass:
1279
1
    case Stmt::OMPParallelMasterTaskLoopSimdDirectiveClass:
1280
1
    case Stmt::OMPDistributeDirectiveClass:
1281
1
    case Stmt::OMPDistributeParallelForDirectiveClass:
1282
1
    case Stmt::OMPDistributeParallelForSimdDirectiveClass:
1283
1
    case Stmt::OMPDistributeSimdDirectiveClass:
1284
1
    case Stmt::OMPTargetParallelForSimdDirectiveClass:
1285
1
    case Stmt::OMPTargetSimdDirectiveClass:
1286
1
    case Stmt::OMPTeamsDistributeDirectiveClass:
1287
1
    case Stmt::OMPTeamsDistributeSimdDirectiveClass:
1288
1
    case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:
1289
1
    case Stmt::OMPTeamsDistributeParallelForDirectiveClass:
1290
1
    case Stmt::OMPTargetTeamsDirectiveClass:
1291
1
    case Stmt::OMPTargetTeamsDistributeDirectiveClass:
1292
1
    case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:
1293
1
    case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:
1294
1
    case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:
1295
1
    case Stmt::CapturedStmtClass: {
1296
1
      const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
1297
1
      Engine.addAbortedBlock(node, currBldrCtx->getBlock());
1298
1
      break;
1299
1
    }
1300
1301
0
    case Stmt::ParenExprClass:
1302
0
      llvm_unreachable("ParenExprs already handled.");
1303
0
    case Stmt::GenericSelectionExprClass:
1304
0
      llvm_unreachable("GenericSelectionExprs already handled.");
1305
    // Cases that should never be evaluated simply because they shouldn't
1306
    // appear in the CFG.
1307
0
    case Stmt::BreakStmtClass:
1308
0
    case Stmt::CaseStmtClass:
1309
0
    case Stmt::CompoundStmtClass:
1310
0
    case Stmt::ContinueStmtClass:
1311
0
    case Stmt::CXXForRangeStmtClass:
1312
0
    case Stmt::DefaultStmtClass:
1313
0
    case Stmt::DoStmtClass:
1314
0
    case Stmt::ForStmtClass:
1315
0
    case Stmt::GotoStmtClass:
1316
0
    case Stmt::IfStmtClass:
1317
0
    case Stmt::IndirectGotoStmtClass:
1318
0
    case Stmt::LabelStmtClass:
1319
0
    case Stmt::NoStmtClass:
1320
0
    case Stmt::NullStmtClass:
1321
0
    case Stmt::SwitchStmtClass:
1322
0
    case Stmt::WhileStmtClass:
1323
0
    case Expr::MSDependentExistsStmtClass:
1324
0
      llvm_unreachable("Stmt should not be in analyzer evaluation loop");
1325
0
    case Stmt::ImplicitValueInitExprClass:
1326
      // These nodes are shared in the CFG and would case caching out.
1327
      // Moreover, no additional evaluation required for them, the
1328
      // analyzer can reconstruct these values from the AST.
1329
0
      llvm_unreachable("Should be pruned from CFG");
1330
1331
0
    case Stmt::ObjCSubscriptRefExprClass:
1332
0
    case Stmt::ObjCPropertyRefExprClass:
1333
0
      llvm_unreachable("These are handled by PseudoObjectExpr");
1334
1335
61
    case Stmt::GNUNullExprClass: {
1336
      // GNU __null is a pointer-width integer, not an actual pointer.
1337
61
      ProgramStateRef state = Pred->getState();
1338
61
      state = state->BindExpr(S, Pred->getLocationContext(),
1339
61
                              svalBuilder.makeIntValWithPtrWidth(0, false));
1340
61
      Bldr.generateNode(S, Pred, state);
1341
61
      break;
1342
0
    }
1343
1344
19
    case Stmt::ObjCAtSynchronizedStmtClass:
1345
19
      Bldr.takeNodes(Pred);
1346
19
      VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
1347
19
      Bldr.addNodes(Dst);
1348
19
      break;
1349
1350
0
    case Expr::ConstantExprClass:
1351
0
    case Stmt::ExprWithCleanupsClass:
1352
      // Handled due to fully linearised CFG.
1353
0
      break;
1354
1355
1.42k
    case Stmt::CXXBindTemporaryExprClass: {
1356
1.42k
      Bldr.takeNodes(Pred);
1357
1.42k
      ExplodedNodeSet PreVisit;
1358
1.42k
      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1359
1.42k
      ExplodedNodeSet Next;
1360
1.42k
      VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), PreVisit, Next);
1361
1.42k
      getCheckerManager().runCheckersForPostStmt(Dst, Next, S, *this);
1362
1.42k
      Bldr.addNodes(Dst);
1363
1.42k
      break;
1364
0
    }
1365
1366
    // Cases not handled yet; but will handle some day.
1367
63.8k
    case Stmt::DesignatedInitExprClass:
1368
63.8k
    case Stmt::DesignatedInitUpdateExprClass:
1369
63.8k
    case Stmt::ArrayInitLoopExprClass:
1370
63.8k
    case Stmt::ArrayInitIndexExprClass:
1371
63.8k
    case Stmt::ExtVectorElementExprClass:
1372
63.8k
    case Stmt::ImaginaryLiteralClass:
1373
63.8k
    case Stmt::ObjCAtCatchStmtClass:
1374
63.8k
    case Stmt::ObjCAtFinallyStmtClass:
1375
63.8k
    case Stmt::ObjCAtTryStmtClass:
1376
63.8k
    case Stmt::ObjCAutoreleasePoolStmtClass:
1377
63.8k
    case Stmt::ObjCEncodeExprClass:
1378
63.8k
    case Stmt::ObjCIsaExprClass:
1379
63.8k
    case Stmt::ObjCProtocolExprClass:
1380
63.8k
    case Stmt::ObjCSelectorExprClass:
1381
63.8k
    case Stmt::ParenListExprClass:
1382
63.8k
    case Stmt::ShuffleVectorExprClass:
1383
63.8k
    case Stmt::ConvertVectorExprClass:
1384
63.8k
    case Stmt::VAArgExprClass:
1385
63.8k
    case Stmt::CUDAKernelCallExprClass:
1386
63.8k
    case Stmt::OpaqueValueExprClass:
1387
63.8k
    case Stmt::AsTypeExprClass:
1388
63.8k
    case Stmt::ConceptSpecializationExprClass:
1389
63.8k
    case Stmt::CXXRewrittenBinaryOperatorClass:
1390
63.8k
    case Stmt::RequiresExprClass:
1391
      // Fall through.
1392
1393
    // Cases we intentionally don't evaluate, since they don't need
1394
    // to be explicitly evaluated.
1395
63.8k
    case Stmt::PredefinedExprClass:
1396
63.8k
    case Stmt::AddrLabelExprClass:
1397
63.8k
    case Stmt::AttributedStmtClass:
1398
63.8k
    case Stmt::IntegerLiteralClass:
1399
63.8k
    case Stmt::FixedPointLiteralClass:
1400
63.8k
    case Stmt::CharacterLiteralClass:
1401
63.8k
    case Stmt::CXXScalarValueInitExprClass:
1402
63.8k
    case Stmt::CXXBoolLiteralExprClass:
1403
63.8k
    case Stmt::ObjCBoolLiteralExprClass:
1404
63.8k
    case Stmt::ObjCAvailabilityCheckExprClass:
1405
63.8k
    case Stmt::FloatingLiteralClass:
1406
63.8k
    case Stmt::NoInitExprClass:
1407
63.8k
    case Stmt::SizeOfPackExprClass:
1408
63.8k
    case Stmt::StringLiteralClass:
1409
63.8k
    case Stmt::SourceLocExprClass:
1410
63.8k
    case Stmt::ObjCStringLiteralClass:
1411
63.8k
    case Stmt::CXXPseudoDestructorExprClass:
1412
63.8k
    case Stmt::SubstNonTypeTemplateParmExprClass:
1413
63.8k
    case Stmt::CXXNullPtrLiteralExprClass:
1414
63.8k
    case Stmt::OMPArraySectionExprClass:
1415
63.8k
    case Stmt::OMPArrayShapingExprClass:
1416
63.8k
    case Stmt::OMPIteratorExprClass:
1417
63.8k
    case Stmt::TypeTraitExprClass: {
1418
63.8k
      Bldr.takeNodes(Pred);
1419
63.8k
      ExplodedNodeSet preVisit;
1420
63.8k
      getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
1421
63.8k
      getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
1422
63.8k
      Bldr.addNodes(Dst);
1423
63.8k
      break;
1424
63.8k
    }
1425
1426
3.28k
    case Stmt::CXXDefaultArgExprClass:
1427
3.28k
    case Stmt::CXXDefaultInitExprClass: {
1428
3.28k
      Bldr.takeNodes(Pred);
1429
3.28k
      ExplodedNodeSet PreVisit;
1430
3.28k
      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1431
1432
3.28k
      ExplodedNodeSet Tmp;
1433
3.28k
      StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
1434
1435
3.28k
      const Expr *ArgE;
1436
3.28k
      if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S))
1437
3.08k
        ArgE = DefE->getExpr();
1438
199
      else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S))
1439
199
        ArgE = DefE->getExpr();
1440
199
      else
1441
0
        llvm_unreachable("unknown constant wrapper kind");
1442
1443
3.28k
      bool IsTemporary = false;
1444
3.28k
      if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) {
1445
38
        ArgE = MTE->getSubExpr();
1446
38
        IsTemporary = true;
1447
38
      }
1448
1449
3.28k
      Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE);
1450
3.28k
      if (!ConstantVal)
1451
1.50k
        ConstantVal = UnknownVal();
1452
1453
3.28k
      const LocationContext *LCtx = Pred->getLocationContext();
1454
3.28k
      for (const auto I : PreVisit) {
1455
3.28k
        ProgramStateRef State = I->getState();
1456
3.28k
        State = State->BindExpr(S, LCtx, *ConstantVal);
1457
3.28k
        if (IsTemporary)
1458
38
          State = createTemporaryRegionIfNeeded(State, LCtx,
1459
38
                                                cast<Expr>(S),
1460
38
                                                cast<Expr>(S));
1461
3.28k
        Bldr2.generateNode(S, I, State);
1462
3.28k
      }
1463
1464
3.28k
      getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
1465
3.28k
      Bldr.addNodes(Dst);
1466
3.28k
      break;
1467
3.28k
    }
1468
1469
    // Cases we evaluate as opaque expressions, conjuring a symbol.
1470
117
    case Stmt::CXXStdInitializerListExprClass:
1471
117
    case Expr::ObjCArrayLiteralClass:
1472
117
    case Expr::ObjCDictionaryLiteralClass:
1473
117
    case Expr::ObjCBoxedExprClass: {
1474
117
      Bldr.takeNodes(Pred);
1475
1476
117
      ExplodedNodeSet preVisit;
1477
117
      getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
1478
1479
117
      ExplodedNodeSet Tmp;
1480
117
      StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
1481
1482
117
      const auto *Ex = cast<Expr>(S);
1483
117
      QualType resultType = Ex->getType();
1484
1485
117
      for (const auto N : preVisit) {
1486
117
        const LocationContext *LCtx = N->getLocationContext();
1487
117
        SVal result = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx,
1488
117
                                                   resultType,
1489
117
                                                   currBldrCtx->blockCount());
1490
117
        ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result);
1491
1492
        // Escape pointers passed into the list, unless it's an ObjC boxed
1493
        // expression which is not a boxable C structure.
1494
117
        if (!(isa<ObjCBoxedExpr>(Ex) &&
1495
35
              !cast<ObjCBoxedExpr>(Ex)->getSubExpr()
1496
35
                                      ->getType()->isRecordType()))
1497
106
          
for (auto Child : Ex->children())84
{
1498
106
            assert(Child);
1499
106
            SVal Val = State->getSVal(Child, LCtx);
1500
106
            State = escapeValues(State, Val, PSK_EscapeOther);
1501
106
          }
1502
1503
117
        Bldr2.generateNode(S, N, State);
1504
117
      }
1505
1506
117
      getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
1507
117
      Bldr.addNodes(Dst);
1508
117
      break;
1509
117
    }
1510
1511
7.80k
    case Stmt::ArraySubscriptExprClass:
1512
7.80k
      Bldr.takeNodes(Pred);
1513
7.80k
      VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
1514
7.80k
      Bldr.addNodes(Dst);
1515
7.80k
      break;
1516
1517
0
    case Stmt::MatrixSubscriptExprClass:
1518
0
      llvm_unreachable("Support for MatrixSubscriptExpr is not implemented.");
1519
0
      break;
1520
1521
2
    case Stmt::GCCAsmStmtClass:
1522
2
      Bldr.takeNodes(Pred);
1523
2
      VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
1524
2
      Bldr.addNodes(Dst);
1525
2
      break;
1526
1527
0
    case Stmt::MSAsmStmtClass:
1528
0
      Bldr.takeNodes(Pred);
1529
0
      VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
1530
0
      Bldr.addNodes(Dst);
1531
0
      break;
1532
1533
380
    case Stmt::BlockExprClass:
1534
380
      Bldr.takeNodes(Pred);
1535
380
      VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
1536
380
      Bldr.addNodes(Dst);
1537
380
      break;
1538
1539
194
    case Stmt::LambdaExprClass:
1540
194
      if (AMgr.options.ShouldInlineLambdas) {
1541
193
        Bldr.takeNodes(Pred);
1542
193
        VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst);
1543
193
        Bldr.addNodes(Dst);
1544
1
      } else {
1545
1
        const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
1546
1
        Engine.addAbortedBlock(node, currBldrCtx->getBlock());
1547
1
      }
1548
194
      break;
1549
1550
73.2k
    case Stmt::BinaryOperatorClass: {
1551
73.2k
      const auto *B = cast<BinaryOperator>(S);
1552
73.2k
      if (B->isLogicalOp()) {
1553
1.18k
        Bldr.takeNodes(Pred);
1554
1.18k
        VisitLogicalExpr(B, Pred, Dst);
1555
1.18k
        Bldr.addNodes(Dst);
1556
1.18k
        break;
1557
1.18k
      }
1558
72.0k
      else if (B->getOpcode() == BO_Comma) {
1559
320
        ProgramStateRef state = Pred->getState();
1560
320
        Bldr.generateNode(B, Pred,
1561
320
                          state->BindExpr(B, Pred->getLocationContext(),
1562
320
                                          state->getSVal(B->getRHS(),
1563
320
                                                  Pred->getLocationContext())));
1564
320
        break;
1565
320
      }
1566
1567
71.7k
      Bldr.takeNodes(Pred);
1568
1569
71.7k
      if (AMgr.options.ShouldEagerlyAssume &&
1570
59.0k
          (B->isRelationalOp() || 
B->isEqualityOp()54.0k
)) {
1571
9.34k
        ExplodedNodeSet Tmp;
1572
9.34k
        VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
1573
9.34k
        evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
1574
9.34k
      }
1575
62.3k
      else
1576
62.3k
        VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
1577
1578
71.7k
      Bldr.addNodes(Dst);
1579
71.7k
      break;
1580
71.7k
    }
1581
1582
3.45k
    case Stmt::CXXOperatorCallExprClass: {
1583
3.45k
      const auto *OCE = cast<CXXOperatorCallExpr>(S);
1584
1585
      // For instance method operators, make sure the 'this' argument has a
1586
      // valid region.
1587
3.45k
      const Decl *Callee = OCE->getCalleeDecl();
1588
3.45k
      if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
1589
3.40k
        if (MD->isInstance()) {
1590
3.40k
          ProgramStateRef State = Pred->getState();
1591
3.40k
          const LocationContext *LCtx = Pred->getLocationContext();
1592
3.40k
          ProgramStateRef NewState =
1593
3.40k
            createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
1594
3.40k
          if (NewState != State) {
1595
0
            Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr,
1596
0
                                     ProgramPoint::PreStmtKind);
1597
            // Did we cache out?
1598
0
            if (!Pred)
1599
0
              break;
1600
3.45k
          }
1601
3.40k
        }
1602
3.40k
      }
1603
      // FALLTHROUGH
1604
3.45k
      LLVM_FALLTHROUGH;
1605
3.45k
    }
1606
1607
69.1k
    case Stmt::CallExprClass:
1608
69.1k
    case Stmt::CXXMemberCallExprClass:
1609
69.1k
    case Stmt::UserDefinedLiteralClass:
1610
69.1k
      Bldr.takeNodes(Pred);
1611
69.1k
      VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
1612
69.1k
      Bldr.addNodes(Dst);
1613
69.1k
      break;
1614
1615
0
    case Stmt::CXXCatchStmtClass:
1616
0
      Bldr.takeNodes(Pred);
1617
0
      VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
1618
0
      Bldr.addNodes(Dst);
1619
0
      break;
1620
1621
29.5k
    case Stmt::CXXTemporaryObjectExprClass:
1622
29.5k
    case Stmt::CXXConstructExprClass:
1623
29.5k
      Bldr.takeNodes(Pred);
1624
29.5k
      VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
1625
29.5k
      Bldr.addNodes(Dst);
1626
29.5k
      break;
1627
1628
5
    case Stmt::CXXInheritedCtorInitExprClass:
1629
5
      Bldr.takeNodes(Pred);
1630
5
      VisitCXXInheritedCtorInitExpr(cast<CXXInheritedCtorInitExpr>(S), Pred,
1631
5
                                    Dst);
1632
5
      Bldr.addNodes(Dst);
1633
5
      break;
1634
1635
1.02k
    case Stmt::CXXNewExprClass: {
1636
1.02k
      Bldr.takeNodes(Pred);
1637
1638
1.02k
      ExplodedNodeSet PreVisit;
1639
1.02k
      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1640
1641
1.02k
      ExplodedNodeSet PostVisit;
1642
1.02k
      for (const auto i : PreVisit)
1643
994
        VisitCXXNewExpr(cast<CXXNewExpr>(S), i, PostVisit);
1644
1645
1.02k
      getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
1646
1.02k
      Bldr.addNodes(Dst);
1647
1.02k
      break;
1648
29.5k
    }
1649
1650
436
    case Stmt::CXXDeleteExprClass: {
1651
436
      Bldr.takeNodes(Pred);
1652
436
      ExplodedNodeSet PreVisit;
1653
436
      const auto *CDE = cast<CXXDeleteExpr>(S);
1654
436
      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1655
436
      ExplodedNodeSet PostVisit;
1656
436
      getCheckerManager().runCheckersForPostStmt(PostVisit, PreVisit, S, *this);
1657
1658
436
      for (const auto i : PostVisit)
1659
436
        VisitCXXDeleteExpr(CDE, i, Dst);
1660
1661
436
      Bldr.addNodes(Dst);
1662
436
      break;
1663
29.5k
    }
1664
      // FIXME: ChooseExpr is really a constant.  We need to fix
1665
      //        the CFG do not model them as explicit control-flow.
1666
1667
0
    case Stmt::ChooseExprClass: { // __builtin_choose_expr
1668
0
      Bldr.takeNodes(Pred);
1669
0
      const auto *C = cast<ChooseExpr>(S);
1670
0
      VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
1671
0
      Bldr.addNodes(Dst);
1672
0
      break;
1673
29.5k
    }
1674
1675
1.02k
    case Stmt::CompoundAssignOperatorClass:
1676
1.02k
      Bldr.takeNodes(Pred);
1677
1.02k
      VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
1678
1.02k
      Bldr.addNodes(Dst);
1679
1.02k
      break;
1680
1681
65
    case Stmt::CompoundLiteralExprClass:
1682
65
      Bldr.takeNodes(Pred);
1683
65
      VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
1684
65
      Bldr.addNodes(Dst);
1685
65
      break;
1686
1687
904
    case Stmt::BinaryConditionalOperatorClass:
1688
904
    case Stmt::ConditionalOperatorClass: { // '?' operator
1689
904
      Bldr.takeNodes(Pred);
1690
904
      const auto *C = cast<AbstractConditionalOperator>(S);
1691
904
      VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
1692
904
      Bldr.addNodes(Dst);
1693
904
      break;
1694
904
    }
1695
1696
9.57k
    case Stmt::CXXThisExprClass:
1697
9.57k
      Bldr.takeNodes(Pred);
1698
9.57k
      VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
1699
9.57k
      Bldr.addNodes(Dst);
1700
9.57k
      break;
1701
1702
226k
    case Stmt::DeclRefExprClass: {
1703
226k
      Bldr.takeNodes(Pred);
1704
226k
      const auto *DE = cast<DeclRefExpr>(S);
1705
226k
      VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
1706
226k
      Bldr.addNodes(Dst);
1707
226k
      break;
1708
904
    }
1709
1710
31.3k
    case Stmt::DeclStmtClass:
1711
31.3k
      Bldr.takeNodes(Pred);
1712
31.3k
      VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
1713
31.3k
      Bldr.addNodes(Dst);
1714
31.3k
      break;
1715
1716
319k
    case Stmt::ImplicitCastExprClass:
1717
319k
    case Stmt::CStyleCastExprClass:
1718
319k
    case Stmt::CXXStaticCastExprClass:
1719
319k
    case Stmt::CXXDynamicCastExprClass:
1720
319k
    case Stmt::CXXReinterpretCastExprClass:
1721
319k
    case Stmt::CXXConstCastExprClass:
1722
319k
    case Stmt::CXXFunctionalCastExprClass:
1723
319k
    case Stmt::BuiltinBitCastExprClass:
1724
319k
    case Stmt::ObjCBridgedCastExprClass:
1725
319k
    case Stmt::CXXAddrspaceCastExprClass: {
1726
319k
      Bldr.takeNodes(Pred);
1727
319k
      const auto *C = cast<CastExpr>(S);
1728
319k
      ExplodedNodeSet dstExpr;
1729
319k
      VisitCast(C, C->getSubExpr(), Pred, dstExpr);
1730
1731
      // Handle the postvisit checks.
1732
319k
      getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
1733
319k
      Bldr.addNodes(Dst);
1734
319k
      break;
1735
319k
    }
1736
1737
9.00k
    case Expr::MaterializeTemporaryExprClass: {
1738
9.00k
      Bldr.takeNodes(Pred);
1739
9.00k
      const auto *MTE = cast<MaterializeTemporaryExpr>(S);
1740
9.00k
      ExplodedNodeSet dstPrevisit;
1741
9.00k
      getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);
1742
9.00k
      ExplodedNodeSet dstExpr;
1743
9.00k
      for (const auto i : dstPrevisit)
1744
9.00k
        CreateCXXTemporaryObject(MTE, i, dstExpr);
1745
9.00k
      getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);
1746
9.00k
      Bldr.addNodes(Dst);
1747
9.00k
      break;
1748
319k
    }
1749
1750
1.18k
    case Stmt::InitListExprClass:
1751
1.18k
      Bldr.takeNodes(Pred);
1752
1.18k
      VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
1753
1.18k
      Bldr.addNodes(Dst);
1754
1.18k
      break;
1755
1756
50.2k
    case Stmt::MemberExprClass:
1757
50.2k
      Bldr.takeNodes(Pred);
1758
50.2k
      VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
1759
50.2k
      Bldr.addNodes(Dst);
1760
50.2k
      break;
1761
1762
54
    case Stmt::AtomicExprClass:
1763
54
      Bldr.takeNodes(Pred);
1764
54
      VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst);
1765
54
      Bldr.addNodes(Dst);
1766
54
      break;
1767
1768
1.05k
    case Stmt::ObjCIvarRefExprClass:
1769
1.05k
      Bldr.takeNodes(Pred);
1770
1.05k
      VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
1771
1.05k
      Bldr.addNodes(Dst);
1772
1.05k
      break;
1773
1774
260
    case Stmt::ObjCForCollectionStmtClass:
1775
260
      Bldr.takeNodes(Pred);
1776
260
      VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
1777
260
      Bldr.addNodes(Dst);
1778
260
      break;
1779
1780
4.18k
    case Stmt::ObjCMessageExprClass:
1781
4.18k
      Bldr.takeNodes(Pred);
1782
4.18k
      VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
1783
4.18k
      Bldr.addNodes(Dst);
1784
4.18k
      break;
1785
1786
10
    case Stmt::ObjCAtThrowStmtClass:
1787
10
    case Stmt::CXXThrowExprClass:
1788
      // FIXME: This is not complete.  We basically treat @throw as
1789
      // an abort.
1790
10
      Bldr.generateSink(S, Pred, Pred->getState());
1791
10
      break;
1792
1793
22.5k
    case Stmt::ReturnStmtClass:
1794
22.5k
      Bldr.takeNodes(Pred);
1795
22.5k
      VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
1796
22.5k
      Bldr.addNodes(Dst);
1797
22.5k
      break;
1798
1799
21
    case Stmt::OffsetOfExprClass: {
1800
21
      Bldr.takeNodes(Pred);
1801
21
      ExplodedNodeSet PreVisit;
1802
21
      getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
1803
1804
21
      ExplodedNodeSet PostVisit;
1805
21
      for (const auto Node : PreVisit)
1806
21
        VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Node, PostVisit);
1807
1808
21
      getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
1809
21
      Bldr.addNodes(Dst);
1810
21
      break;
1811
10
    }
1812
1813
958
    case Stmt::UnaryExprOrTypeTraitExprClass:
1814
958
      Bldr.takeNodes(Pred);
1815
958
      VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
1816
958
                                    Pred, Dst);
1817
958
      Bldr.addNodes(Dst);
1818
958
      break;
1819
1820
55
    case Stmt::StmtExprClass: {
1821
55
      const auto *SE = cast<StmtExpr>(S);
1822
1823
55
      if (SE->getSubStmt()->body_empty()) {
1824
        // Empty statement expression.
1825
2
        assert(SE->getType() == getContext().VoidTy
1826
2
               && "Empty statement expression must have void type.");
1827
2
        break;
1828
2
      }
1829
1830
53
      if (const auto *LastExpr =
1831
53
              dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
1832
53
        ProgramStateRef state = Pred->getState();
1833
53
        Bldr.generateNode(SE, Pred,
1834
53
                          state->BindExpr(SE, Pred->getLocationContext(),
1835
53
                                          state->getSVal(LastExpr,
1836
53
                                                  Pred->getLocationContext())));
1837
53
      }
1838
53
      break;
1839
53
    }
1840
1841
28.3k
    case Stmt::UnaryOperatorClass: {
1842
28.3k
      Bldr.takeNodes(Pred);
1843
28.3k
      const auto *U = cast<UnaryOperator>(S);
1844
28.3k
      if (AMgr.options.ShouldEagerlyAssume && 
(U->getOpcode() == UO_LNot)24.0k
) {
1845
968
        ExplodedNodeSet Tmp;
1846
968
        VisitUnaryOperator(U, Pred, Tmp);
1847
968
        evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
1848
968
      }
1849
27.4k
      else
1850
27.4k
        VisitUnaryOperator(U, Pred, Dst);
1851
28.3k
      Bldr.addNodes(Dst);
1852
28.3k
      break;
1853
53
    }
1854
1855
362
    case Stmt::PseudoObjectExprClass: {
1856
362
      Bldr.takeNodes(Pred);
1857
362
      ProgramStateRef state = Pred->getState();
1858
362
      const auto *PE = cast<PseudoObjectExpr>(S);
1859
362
      if (const Expr *Result = PE->getResultExpr()) {
1860
362
        SVal V = state->getSVal(Result, Pred->getLocationContext());
1861
362
        Bldr.generateNode(S, Pred,
1862
362
                          state->BindExpr(S, Pred->getLocationContext(), V));
1863
362
      }
1864
0
      else
1865
0
        Bldr.generateNode(S, Pred,
1866
0
                          state->BindExpr(S, Pred->getLocationContext(),
1867
0
                                                   UnknownVal()));
1868
1869
362
      Bldr.addNodes(Dst);
1870
362
      break;
1871
53
    }
1872
1873
1
    case Expr::ObjCIndirectCopyRestoreExprClass: {
1874
      // ObjCIndirectCopyRestoreExpr implies passing a temporary for
1875
      // correctness of lifetime management.  Due to limited analysis
1876
      // of ARC, this is implemented as direct arg passing.
1877
1
      Bldr.takeNodes(Pred);
1878
1
      ProgramStateRef state = Pred->getState();
1879
1
      const auto *OIE = cast<ObjCIndirectCopyRestoreExpr>(S);
1880
1
      const Expr *E = OIE->getSubExpr();
1881
1
      SVal V = state->getSVal(E, Pred->getLocationContext());
1882
1
      Bldr.generateNode(S, Pred,
1883
1
              state->BindExpr(S, Pred->getLocationContext(), V));
1884
1
      Bldr.addNodes(Dst);
1885
1
      break;
1886
53
    }
1887
957k
  }
1888
957k
}
1889
1890
bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
1891
40
                                       const LocationContext *CalleeLC) {
1892
40
  const StackFrameContext *CalleeSF = CalleeLC->getStackFrame();
1893
40
  const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame();
1894
40
  assert(CalleeSF && CallerSF);
1895
40
  ExplodedNode *BeforeProcessingCall = nullptr;
1896
40
  const Stmt *CE = CalleeSF->getCallSite();
1897
1898
  // Find the first node before we started processing the call expression.
1899
28.1k
  while (N) {
1900
28.1k
    ProgramPoint L = N->getLocation();
1901
28.1k
    BeforeProcessingCall = N;
1902
28.1k
    N = N->pred_empty() ? 
nullptr0
: *(N->pred_begin());
1903
1904
    // Skip the nodes corresponding to the inlined code.
1905
28.1k
    if (L.getStackFrame() != CallerSF)
1906
28.0k
      continue;
1907
    // We reached the caller. Find the node right before we started
1908
    // processing the call.
1909
119
    if (L.isPurgeKind())
1910
39
      continue;
1911
80
    if (L.getAs<PreImplicitCall>())
1912
0
      continue;
1913
80
    if (L.getAs<CallEnter>())
1914
40
      continue;
1915
40
    if (Optional<StmtPoint> SP = L.getAs<StmtPoint>())
1916
40
      if (SP->getStmt() == CE)
1917
0
        continue;
1918
40
    break;
1919
40
  }
1920
1921
40
  if (!BeforeProcessingCall)
1922
0
    return false;
1923
1924
  // TODO: Clean up the unneeded nodes.
1925
1926
  // Build an Epsilon node from which we will restart the analyzes.
1927
  // Note that CE is permitted to be NULL!
1928
40
  ProgramPoint NewNodeLoc =
1929
40
               EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
1930
  // Add the special flag to GDM to signal retrying with no inlining.
1931
  // Note, changing the state ensures that we are not going to cache out.
1932
40
  ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
1933
40
  NewNodeState =
1934
40
    NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
1935
1936
  // Make the new node a successor of BeforeProcessingCall.
1937
40
  bool IsNew = false;
1938
40
  ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
1939
  // We cached out at this point. Caching out is common due to us backtracking
1940
  // from the inlined function, which might spawn several paths.
1941
40
  if (!IsNew)
1942
4
    return true;
1943
1944
36
  NewNode->addPredecessor(BeforeProcessingCall, G);
1945
1946
  // Add the new node to the work list.
1947
36
  Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
1948
36
                                  CalleeSF->getIndex());
1949
36
  NumTimesRetriedWithoutInlining++;
1950
36
  return true;
1951
36
}
1952
1953
/// Block entrance.  (Update counters).
1954
void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
1955
                                         NodeBuilderWithSinks &nodeBuilder,
1956
137k
                                         ExplodedNode *Pred) {
1957
137k
  PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
1958
  // If we reach a loop which has a known bound (and meets
1959
  // other constraints) then consider completely unrolling it.
1960
137k
  if(AMgr.options.ShouldUnrollLoops) {
1961
5.72k
    unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
1962
5.72k
    const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
1963
5.72k
    if (Term) {
1964
2.02k
      ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
1965
2.02k
                                                 Pred, maxBlockVisitOnPath);
1966
2.02k
      if (NewState != Pred->getState()) {
1967
189
        ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred);
1968
189
        if (!UpdatedNode)
1969
0
          return;
1970
189
        Pred = UpdatedNode;
1971
189
      }
1972
2.02k
    }
1973
    // Is we are inside an unrolled loop then no need the check the counters.
1974
5.72k
    if(isUnrolledState(Pred->getState()))
1975
4.36k
      return;
1976
132k
  }
1977
1978
  // If this block is terminated by a loop and it has already been visited the
1979
  // maximum number of times, widen the loop.
1980
132k
  unsigned int BlockCount = nodeBuilder.getContext().blockCount();
1981
132k
  if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
1982
3.83k
      AMgr.options.ShouldWidenLoops) {
1983
138
    const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
1984
138
    if (!(Term &&
1985
61
          (isa<ForStmt>(Term) || 
isa<WhileStmt>(Term)33
||
isa<DoStmt>(Term)14
)))
1986
87
      return;
1987
    // Widen.
1988
51
    const LocationContext *LCtx = Pred->getLocationContext();
1989
51
    ProgramStateRef WidenedState =
1990
51
        getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
1991
51
    nodeBuilder.generateNode(WidenedState, Pred);
1992
51
    return;
1993
51
  }
1994
1995
  // FIXME: Refactor this into a checker.
1996
132k
  if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
1997
1.16k
    static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
1998
1.16k
    const ExplodedNode *Sink =
1999
1.16k
                   nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
2000
2001
    // Check if we stopped at the top level function or not.
2002
    // Root node should have the location context of the top most function.
2003
1.16k
    const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
2004
1.16k
    const LocationContext *CalleeSF = CalleeLC->getStackFrame();
2005
1.16k
    const LocationContext *RootLC =
2006
1.16k
                        (*G.roots_begin())->getLocation().getLocationContext();
2007
1.16k
    if (RootLC->getStackFrame() != CalleeSF) {
2008
45
      Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
2009
2010
      // Re-run the call evaluation without inlining it, by storing the
2011
      // no-inlining policy in the state and enqueuing the new work item on
2012
      // the list. Replay should almost never fail. Use the stats to catch it
2013
      // if it does.
2014
45
      if ((!AMgr.options.NoRetryExhausted &&
2015
40
           replayWithoutInlining(Pred, CalleeLC)))
2016
40
        return;
2017
5
      NumMaxBlockCountReachedInInlined++;
2018
5
    } else
2019
1.11k
      NumMaxBlockCountReached++;
2020
2021
    // Make sink nodes as exhausted(for stats) only if retry failed.
2022
1.12k
    Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
2023
1.12k
  }
2024
132k
}
2025
2026
//===----------------------------------------------------------------------===//
2027
// Branch processing.
2028
//===----------------------------------------------------------------------===//
2029
2030
/// RecoverCastedSymbol - A helper function for ProcessBranch that is used
2031
/// to try to recover some path-sensitivity for casts of symbolic
2032
/// integers that promote their values (which are currently not tracked well).
2033
/// This function returns the SVal bound to Condition->IgnoreCasts if all the
2034
//  cast(s) did was sign-extend the original value.
2035
static SVal RecoverCastedSymbol(ProgramStateRef state,
2036
                                const Stmt *Condition,
2037
                                const LocationContext *LCtx,
2038
442
                                ASTContext &Ctx) {
2039
2040
442
  const auto *Ex = dyn_cast<Expr>(Condition);
2041
442
  if (!Ex)
2042
0
    return UnknownVal();
2043
2044
442
  uint64_t bits = 0;
2045
442
  bool bitsInit = false;
2046
2047
739
  while (const auto *CE = dyn_cast<CastExpr>(Ex)) {
2048
303
    QualType T = CE->getType();
2049
2050
303
    if (!T->isIntegralOrEnumerationType())
2051
6
      return UnknownVal();
2052
2053
297
    uint64_t newBits = Ctx.getTypeSize(T);
2054
297
    if (!bitsInit || 
newBits < bits1
) {
2055
296
      bitsInit = true;
2056
296
      bits = newBits;
2057
296
    }
2058
2059
297
    Ex = CE->getSubExpr();
2060
297
  }
2061
2062
  // We reached a non-cast.  Is it a symbolic value?
2063
436
  QualType T = Ex->getType();
2064
2065
436
  if (!bitsInit || 
!T->isIntegralOrEnumerationType()290
||
2066
290
      Ctx.getTypeSize(T) > bits)
2067
426
    return UnknownVal();
2068
2069
10
  return state->getSVal(Ex, LCtx);
2070
10
}
2071
2072
#ifndef NDEBUG
2073
10.0k
static const Stmt *getRightmostLeaf(const Stmt *Condition) {
2074
20.2k
  while (Condition) {
2075
20.2k
    const auto *BO = dyn_cast<BinaryOperator>(Condition);
2076
20.2k
    if (!BO || 
!BO->isLogicalOp()10.5k
) {
2077
10.0k
      return Condition;
2078
10.0k
    }
2079
10.1k
    Condition = BO->getRHS()->IgnoreParens();
2080
10.1k
  }
2081
0
  return nullptr;
2082
10.0k
}
2083
#endif
2084
2085
// Returns the condition the branch at the end of 'B' depends on and whose value
2086
// has been evaluated within 'B'.
2087
// In most cases, the terminator condition of 'B' will be evaluated fully in
2088
// the last statement of 'B'; in those cases, the resolved condition is the
2089
// given 'Condition'.
2090
// If the condition of the branch is a logical binary operator tree, the CFG is
2091
// optimized: in that case, we know that the expression formed by all but the
2092
// rightmost leaf of the logical binary operator tree must be true, and thus
2093
// the branch condition is at this point equivalent to the truth value of that
2094
// rightmost leaf; the CFG block thus only evaluates this rightmost leaf
2095
// expression in its final statement. As the full condition in that case was
2096
// not evaluated, and is thus not in the SVal cache, we need to use that leaf
2097
// expression to evaluate the truth value of the condition in the current state
2098
// space.
2099
static const Stmt *ResolveCondition(const Stmt *Condition,
2100
42.3k
                                    const CFGBlock *B) {
2101
42.3k
  if (const auto *Ex = dyn_cast<Expr>(Condition))
2102
41.9k
    Condition = Ex->IgnoreParens();
2103
2104
42.3k
  const auto *BO = dyn_cast<BinaryOperator>(Condition);
2105
42.3k
  if (!BO || 
!BO->isLogicalOp()21.7k
)
2106
32.2k
    return Condition;
2107
2108
10.0k
  assert(B->getTerminator().isStmtBranch() &&
2109
10.0k
         "Other kinds of branches are handled separately!");
2110
2111
  // For logical operations, we still have the case where some branches
2112
  // use the traditional "merge" approach and others sink the branch
2113
  // directly into the basic blocks representing the logical operation.
2114
  // We need to distinguish between those two cases here.
2115
2116
  // The invariants are still shifting, but it is possible that the
2117
  // last element in a CFGBlock is not a CFGStmt.  Look for the last
2118
  // CFGStmt as the value of the condition.
2119
10.0k
  CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
2120
10.0k
  for (; I != E; 
++I0
) {
2121
10.0k
    CFGElement Elem = *I;
2122
10.0k
    Optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
2123
10.0k
    if (!CS)
2124
0
      continue;
2125
10.0k
    const Stmt *LastStmt = CS->getStmt();
2126
10.0k
    assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition));
2127
10.0k
    return LastStmt;
2128
10.0k
  }
2129
10.0k
  
llvm_unreachable0
("could not resolve condition");
2130
10.0k
}
2131
2132
using ObjCForLctxPair =
2133
    std::pair<const ObjCForCollectionStmt *, const LocationContext *>;
2134
2135
REGISTER_MAP_WITH_PROGRAMSTATE(ObjCForHasMoreIterations, ObjCForLctxPair, bool)
2136
2137
ProgramStateRef ExprEngine::setWhetherHasMoreIteration(
2138
    ProgramStateRef State, const ObjCForCollectionStmt *O,
2139
517
    const LocationContext *LC, bool HasMoreIteraton) {
2140
517
  assert(!State->contains<ObjCForHasMoreIterations>({O, LC}));
2141
517
  return State->set<ObjCForHasMoreIterations>({O, LC}, HasMoreIteraton);
2142
517
}
2143
2144
ProgramStateRef
2145
ExprEngine::removeIterationState(ProgramStateRef State,
2146
                                 const ObjCForCollectionStmt *O,
2147
448
                                 const LocationContext *LC) {
2148
448
  assert(State->contains<ObjCForHasMoreIterations>({O, LC}));
2149
448
  return State->remove<ObjCForHasMoreIterations>({O, LC});
2150
448
}
2151
2152
bool ExprEngine::hasMoreIteration(ProgramStateRef State,
2153
                                  const ObjCForCollectionStmt *O,
2154
871
                                  const LocationContext *LC) {
2155
871
  assert(State->contains<ObjCForHasMoreIterations>({O, LC}));
2156
871
  return *State->get<ObjCForHasMoreIterations>({O, LC});
2157
871
}
2158
2159
/// Split the state on whether there are any more iterations left for this loop.
2160
/// Returns a (HasMoreIteration, HasNoMoreIteration) pair, or None when the
2161
/// acquisition of the loop condition value failed.
2162
static Optional<std::pair<ProgramStateRef, ProgramStateRef>>
2163
42.3k
assumeCondition(const Stmt *Condition, ExplodedNode *N) {
2164
42.3k
  ProgramStateRef State = N->getState();
2165
42.3k
  if (const auto *ObjCFor = dyn_cast<ObjCForCollectionStmt>(Condition)) {
2166
448
    bool HasMoreIteraton =
2167
448
        ExprEngine::hasMoreIteration(State, ObjCFor, N->getLocationContext());
2168
    // Checkers have already ran on branch conditions, so the current
2169
    // information as to whether the loop has more iteration becomes outdated
2170
    // after this point.
2171
448
    State = ExprEngine::removeIterationState(State, ObjCFor,
2172
448
                                             N->getLocationContext());
2173
448
    if (HasMoreIteraton)
2174
242
      return std::pair<ProgramStateRef, ProgramStateRef>{State, nullptr};
2175
206
    else
2176
206
      return std::pair<ProgramStateRef, ProgramStateRef>{nullptr, State};
2177
41.8k
  }
2178
41.8k
  SVal X = State->getSVal(Condition, N->getLocationContext());
2179
2180
41.8k
  if (X.isUnknownOrUndef()) {
2181
    // Give it a chance to recover from unknown.
2182
448
    if (const auto *Ex = dyn_cast<Expr>(Condition)) {
2183
448
      if (Ex->getType()->isIntegralOrEnumerationType()) {
2184
        // Try to recover some path-sensitivity.  Right now casts of symbolic
2185
        // integers that promote their values are currently not tracked well.
2186
        // If 'Condition' is such an expression, try and recover the
2187
        // underlying value and use that instead.
2188
442
        SVal recovered =
2189
442
            RecoverCastedSymbol(State, Condition, N->getLocationContext(),
2190
442
                                N->getState()->getStateManager().getContext());
2191
2192
442
        if (!recovered.isUnknown()) {
2193
10
          X = recovered;
2194
10
        }
2195
442
      }
2196
448
    }
2197
448
  }
2198
2199
  // If the condition is still unknown, give up.
2200
41.8k
  if (X.isUnknownOrUndef())
2201
438
    return None;
2202
2203
41.4k
  DefinedSVal V = X.castAs<DefinedSVal>();
2204
2205
41.4k
  ProgramStateRef StTrue, StFalse;
2206
41.4k
  return State->assume(V);
2207
41.4k
}
2208
2209
void ExprEngine::processBranch(const Stmt *Condition,
2210
                               NodeBuilderContext& BldCtx,
2211
                               ExplodedNode *Pred,
2212
                               ExplodedNodeSet &Dst,
2213
                               const CFGBlock *DstT,
2214
42.5k
                               const CFGBlock *DstF) {
2215
42.5k
  assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) &&
2216
42.5k
         "CXXBindTemporaryExprs are handled by processBindTemporary.");
2217
42.5k
  const LocationContext *LCtx = Pred->getLocationContext();
2218
42.5k
  PrettyStackTraceLocationContext StackCrashInfo(LCtx);
2219
42.5k
  currBldrCtx = &BldCtx;
2220
2221
  // Check for NULL conditions; e.g. "for(;;)"
2222
42.5k
  if (!Condition) {
2223
156
    BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
2224
156
    NullCondBldr.markInfeasible(false);
2225
156
    NullCondBldr.generateNode(Pred->getState(), true, Pred);
2226
156
    return;
2227
156
  }
2228
2229
42.3k
  if (const auto *Ex = dyn_cast<Expr>(Condition))
2230
41.9k
    Condition = Ex->IgnoreParens();
2231
2232
42.3k
  Condition = ResolveCondition(Condition, BldCtx.getBlock());
2233
42.3k
  PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
2234
42.3k
                                Condition->getBeginLoc(),
2235
42.3k
                                "Error evaluating branch");
2236
2237
42.3k
  ExplodedNodeSet CheckersOutSet;
2238
42.3k
  getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
2239
42.3k
                                                    Pred, *this);
2240
  // We generated only sinks.
2241
42.3k
  if (CheckersOutSet.empty())
2242
57
    return;
2243
2244
42.3k
  BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
2245
42.3k
  for (ExplodedNode *PredN : CheckersOutSet) {
2246
42.3k
    if (PredN->isSink())
2247
0
      continue;
2248
2249
42.3k
    ProgramStateRef PrevState = PredN->getState();
2250
2251
42.3k
    ProgramStateRef StTrue, StFalse;
2252
42.3k
    if (const auto KnownCondValueAssumption = assumeCondition(Condition, PredN))
2253
41.8k
      std::tie(StTrue, StFalse) = *KnownCondValueAssumption;
2254
438
    else {
2255
438
      assert(!isa<ObjCForCollectionStmt>(Condition));
2256
438
      builder.generateNode(PrevState, true, PredN);
2257
438
      builder.generateNode(PrevState, false, PredN);
2258
438
      continue;
2259
438
    }
2260
41.8k
    if (StTrue && 
StFalse35.7k
)
2261
41.8k
      assert(!isa<ObjCForCollectionStmt>(Condition));;
2262
2263
    // Process the true branch.
2264
41.8k
    if (builder.isFeasible(true)) {
2265
41.7k
      if (StTrue)
2266
35.7k
        builder.generateNode(StTrue, true, PredN);
2267
5.96k
      else
2268
5.96k
        builder.markInfeasible(true);
2269
41.7k
    }
2270
2271
    // Process the false branch.
2272
41.8k
    if (builder.isFeasible(false)) {
2273
40.9k
      if (StFalse)
2274
32.5k
        builder.generateNode(StFalse, false, PredN);
2275
8.38k
      else
2276
8.38k
        builder.markInfeasible(false);
2277
40.9k
    }
2278
41.8k
  }
2279
42.3k
  currBldrCtx = nullptr;
2280
42.3k
}
2281
2282
/// The GDM component containing the set of global variables which have been
2283
/// previously initialized with explicit initializers.
2284
REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
2285
                                 llvm::ImmutableSet<const VarDecl *>)
2286
2287
void ExprEngine::processStaticInitializer(const DeclStmt *DS,
2288
                                          NodeBuilderContext &BuilderCtx,
2289
                                          ExplodedNode *Pred,
2290
                                          ExplodedNodeSet &Dst,
2291
                                          const CFGBlock *DstT,
2292
199
                                          const CFGBlock *DstF) {
2293
199
  PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
2294
199
  currBldrCtx = &BuilderCtx;
2295
2296
199
  const auto *VD = cast<VarDecl>(DS->getSingleDecl());
2297
199
  ProgramStateRef state = Pred->getState();
2298
199
  bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
2299
199
  BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
2300
2301
199
  if (!initHasRun) {
2302
194
    state = state->add<InitializedGlobalsSet>(VD);
2303
194
  }
2304
2305
199
  builder.generateNode(state, initHasRun, Pred);
2306
199
  builder.markInfeasible(!initHasRun);
2307
2308
199
  currBldrCtx = nullptr;
2309
199
}
2310
2311
/// processIndirectGoto - Called by CoreEngine.  Used to generate successor
2312
///  nodes by processing the 'effects' of a computed goto jump.
2313
8
void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
2314
8
  ProgramStateRef state = builder.getState();
2315
8
  SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
2316
2317
  // Three possibilities:
2318
  //
2319
  //   (1) We know the computed label.
2320
  //   (2) The label is NULL (or some other constant), or Undefined.
2321
  //   (3) We have no clue about the label.  Dispatch to all targets.
2322
  //
2323
2324
8
  using iterator = IndirectGotoNodeBuilder::iterator;
2325
2326
8
  if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
2327
0
    const LabelDecl *L = LV->getLabel();
2328
2329
0
    for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
2330
0
      if (I.getLabel() == L) {
2331
0
        builder.generateNode(I, state);
2332
0
        return;
2333
0
      }
2334
0
    }
2335
2336
0
    llvm_unreachable("No block with label.");
2337
8
  }
2338
2339
8
  if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) {
2340
    // Dispatch to the first target and mark it as a sink.
2341
    //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
2342
    // FIXME: add checker visit.
2343
    //    UndefBranches.insert(N);
2344
0
    return;
2345
0
  }
2346
2347
  // This is really a catch-all.  We don't support symbolics yet.
2348
  // FIXME: Implement dispatch for symbolic pointers.
2349
2350
16
  
for (iterator I = builder.begin(), E = builder.end(); 8
I != E;
++I8
)
2351
8
    builder.generateNode(I, state);
2352
8
}
2353
2354
void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
2355
                                        ExplodedNode *Pred,
2356
                                        ExplodedNodeSet &Dst,
2357
47.4k
                                        const BlockEdge &L) {
2358
47.4k
  SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
2359
47.4k
  getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);
2360
47.4k
}
2361
2362
/// ProcessEndPath - Called by CoreEngine.  Used to generate end-of-path
2363
///  nodes when the control reaches the end of a function.
2364
void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
2365
                                      ExplodedNode *Pred,
2366
63.0k
                                      const ReturnStmt *RS) {
2367
63.0k
  ProgramStateRef State = Pred->getState();
2368
2369
63.0k
  if (!Pred->getStackFrame()->inTopFrame())
2370
41.2k
    State = finishArgumentConstruction(
2371
41.2k
        State, *getStateManager().getCallEventManager().getCaller(
2372
41.2k
                   Pred->getStackFrame(), Pred->getState()));
2373
2374
  // FIXME: We currently cannot assert that temporaries are clear, because
2375
  // lifetime extended temporaries are not always modelled correctly. In some
2376
  // cases when we materialize the temporary, we do
2377
  // createTemporaryRegionIfNeeded(), and the region changes, and also the
2378
  // respective destructor becomes automatic from temporary. So for now clean up
2379
  // the state manually before asserting. Ideally, this braced block of code
2380
  // should go away.
2381
63.0k
  {
2382
63.0k
    const LocationContext *FromLC = Pred->getLocationContext();
2383
63.0k
    const LocationContext *ToLC = FromLC->getStackFrame()->getParent();
2384
63.0k
    const LocationContext *LC = FromLC;
2385
126k
    while (LC != ToLC) {
2386
63.0k
      assert(LC && "ToLC must be a parent of FromLC!");
2387
63.0k
      for (auto I : State->get<ObjectsUnderConstruction>())
2388
32.0k
        if (I.first.getLocationContext() == LC) {
2389
          // The comment above only pardons us for not cleaning up a
2390
          // temporary destructor. If any other statements are found here,
2391
          // it must be a separate problem.
2392
359
          assert(I.first.getItem().getKind() ==
2393
359
                     ConstructionContextItem::TemporaryDestructorKind ||
2394
359
                 I.first.getItem().getKind() ==
2395
359
                     ConstructionContextItem::ElidedDestructorKind);
2396
359
          State = State->remove<ObjectsUnderConstruction>(I.first);
2397
359
        }
2398
63.0k
      LC = LC->getParent();
2399
63.0k
    }
2400
63.0k
  }
2401
2402
  // Perform the transition with cleanups.
2403
63.0k
  if (State != Pred->getState()) {
2404
1.68k
    ExplodedNodeSet PostCleanup;
2405
1.68k
    NodeBuilder Bldr(Pred, PostCleanup, BC);
2406
1.68k
    Pred = Bldr.generateNode(Pred->getLocation(), State, Pred);
2407
1.68k
    if (!Pred) {
2408
      // The node with clean temporaries already exists. We might have reached
2409
      // it on a path on which we initialize different temporaries.
2410
4
      return;
2411
4
    }
2412
63.0k
  }
2413
2414
63.0k
  assert(areAllObjectsFullyConstructed(Pred->getState(),
2415
63.0k
                                       Pred->getLocationContext(),
2416
63.0k
                                       Pred->getStackFrame()->getParent()));
2417
2418
63.0k
  PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
2419
2420
63.0k
  ExplodedNodeSet Dst;
2421
63.0k
  if (Pred->getLocationContext()->inTopFrame()) {
2422
    // Remove dead symbols.
2423
21.7k
    ExplodedNodeSet AfterRemovedDead;
2424
21.7k
    removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
2425
2426
    // Notify checkers.
2427
21.7k
    for (const auto I : AfterRemovedDead)
2428
20.6k
      getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS);
2429
41.2k
  } else {
2430
41.2k
    getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS);
2431
41.2k
  }
2432
2433
63.0k
  Engine.enqueueEndOfFunction(Dst, RS);
2434
63.0k
}
2435
2436
/// ProcessSwitch - Called by CoreEngine.  Used to generate successor
2437
///  nodes by processing the 'effects' of a switch statement.
2438
244
void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
2439
244
  using iterator = SwitchNodeBuilder::iterator;
2440
2441
244
  ProgramStateRef state = builder.getState();
2442
244
  const Expr *CondE = builder.getCondition();
2443
244
  SVal  CondV_untested = state->getSVal(CondE, builder.getLocationContext());
2444
2445
244
  if (CondV_untested.isUndef()) {
2446
    //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
2447
    // FIXME: add checker
2448
    //UndefBranches.insert(N);
2449
2450
0
    return;
2451
0
  }
2452
244
  DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
2453
2454
244
  ProgramStateRef DefaultSt = state;
2455
2456
244
  iterator I = builder.begin(), EI = builder.end();
2457
244
  bool defaultIsFeasible = I == EI;
2458
2459
713
  for ( ; I != EI; 
++I469
) {
2460
    // Successor may be pruned out during CFG construction.
2461
555
    if (!I.getBlock())
2462
2
      continue;
2463
2464
553
    const CaseStmt *Case = I.getCase();
2465
2466
    // Evaluate the LHS of the case value.
2467
553
    llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
2468
553
    assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType()));
2469
2470
    // Get the RHS of the case, if it exists.
2471
553
    llvm::APSInt V2;
2472
553
    if (const Expr *E = Case->getRHS())
2473
29
      V2 = E->EvaluateKnownConstInt(getContext());
2474
524
    else
2475
524
      V2 = V1;
2476
2477
553
    ProgramStateRef StateCase;
2478
553
    if (Optional<NonLoc> NL = CondV.getAs<NonLoc>())
2479
553
      std::tie(StateCase, DefaultSt) =
2480
553
          DefaultSt->assumeInclusiveRange(*NL, V1, V2);
2481
0
    else // UnknownVal
2482
0
      StateCase = DefaultSt;
2483
2484
553
    if (StateCase)
2485
410
      builder.generateCaseStmtNode(I, StateCase);
2486
2487
    // Now "assume" that the case doesn't match.  Add this state
2488
    // to the default state (if it is feasible).
2489
553
    if (DefaultSt)
2490
467
      defaultIsFeasible = true;
2491
86
    else {
2492
86
      defaultIsFeasible = false;
2493
86
      break;
2494
86
    }
2495
553
  }
2496
2497
244
  if (!defaultIsFeasible)
2498
86
    return;
2499
2500
  // If we have switch(enum value), the default branch is not
2501
  // feasible if all of the enum constants not covered by 'case:' statements
2502
  // are not feasible values for the switch condition.
2503
  //
2504
  // Note that this isn't as accurate as it could be.  Even if there isn't
2505
  // a case for a particular enum value as long as that enum value isn't
2506
  // feasible then it shouldn't be considered for making 'default:' reachable.
2507
158
  const SwitchStmt *SS = builder.getSwitch();
2508
158
  const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
2509
158
  if (CondExpr->getType()->getAs<EnumType>()) {
2510
11
    if (SS->isAllEnumCasesCovered())
2511
6
      return;
2512
152
  }
2513
2514
152
  builder.generateDefaultCaseNode(DefaultSt);
2515
152
}
2516
2517
//===----------------------------------------------------------------------===//
2518
// Transfer functions: Loads and stores.
2519
//===----------------------------------------------------------------------===//
2520
2521
void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
2522
                                        ExplodedNode *Pred,
2523
226k
                                        ExplodedNodeSet &Dst) {
2524
226k
  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
2525
2526
226k
  ProgramStateRef state = Pred->getState();
2527
226k
  const LocationContext *LCtx = Pred->getLocationContext();
2528
2529
226k
  if (const auto *VD = dyn_cast<VarDecl>(D)) {
2530
    // C permits "extern void v", and if you cast the address to a valid type,
2531
    // you can even do things with it. We simply pretend
2532
165k
    assert(Ex->isGLValue() || VD->getType()->isVoidType());
2533
165k
    const LocationContext *LocCtxt = Pred->getLocationContext();
2534
165k
    const Decl *D = LocCtxt->getDecl();
2535
165k
    const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D);
2536
165k
    const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex);
2537
165k
    Optional<std::pair<SVal, QualType>> VInfo;
2538
2539
165k
    if (AMgr.options.ShouldInlineLambdas && 
DeclRefEx165k
&&
2540
165k
        DeclRefEx->refersToEnclosingVariableOrCapture() && 
MD679
&&
2541
269
        MD->getParent()->isLambda()) {
2542
      // Lookup the field of the lambda.
2543
269
      const CXXRecordDecl *CXXRec = MD->getParent();
2544
269
      llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
2545
269
      FieldDecl *LambdaThisCaptureField;
2546
269
      CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
2547
2548
      // Sema follows a sequence of complex rules to determine whether the
2549
      // variable should be captured.
2550
269
      if (const FieldDecl *FD = LambdaCaptureFields[VD]) {
2551
261
        Loc CXXThis =
2552
261
            svalBuilder.getCXXThis(MD, LocCtxt->getStackFrame());
2553
261
        SVal CXXThisVal = state->getSVal(CXXThis);
2554
261
        VInfo = std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType());
2555
261
      }
2556
269
    }
2557
2558
165k
    if (!VInfo)
2559
165k
      VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType());
2560
2561
165k
    SVal V = VInfo->first;
2562
165k
    bool IsReference = VInfo->second->isReferenceType();
2563
2564
    // For references, the 'lvalue' is the pointer address stored in the
2565
    // reference region.
2566
165k
    if (IsReference) {
2567
24.4k
      if (const MemRegion *R = V.getAsRegion())
2568
24.4k
        V = state->getSVal(R);
2569
0
      else
2570
0
        V = UnknownVal();
2571
24.4k
    }
2572
2573
165k
    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
2574
165k
                      ProgramPoint::PostLValueKind);
2575
165k
    return;
2576
165k
  }
2577
60.4k
  if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) {
2578
262
    assert(!Ex->isGLValue());
2579
262
    SVal V = svalBuilder.makeIntVal(ED->getInitVal());
2580
262
    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
2581
262
    return;
2582
262
  }
2583
60.1k
  if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
2584
60.1k
    SVal V = svalBuilder.getFunctionPointer(FD);
2585
60.1k
    Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
2586
60.1k
                      ProgramPoint::PostLValueKind);
2587
60.1k
    return;
2588
60.1k
  }
2589
50
  if (isa<FieldDecl>(D) || 
isa<IndirectFieldDecl>(D)29
) {
2590
    // Delegate all work related to pointer to members to the surrounding
2591
    // operator&.
2592
32
    return;
2593
32
  }
2594
18
  if (isa<BindingDecl>(D)) {
2595
    // FIXME: proper support for bound declarations.
2596
    // For now, let's just prevent crashing.
2597
18
    return;
2598
18
  }
2599
2600
0
  llvm_unreachable("Support for this Decl not implemented.");
2601
0
}
2602
2603
/// VisitArraySubscriptExpr - Transfer function for array accesses
2604
void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A,
2605
                                             ExplodedNode *Pred,
2606
7.80k
                                             ExplodedNodeSet &Dst){
2607
7.80k
  const Expr *Base = A->getBase()->IgnoreParens();
2608
7.80k
  const Expr *Idx  = A->getIdx()->IgnoreParens();
2609
2610
7.80k
  ExplodedNodeSet CheckerPreStmt;
2611
7.80k
  getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this);
2612
2613
7.80k
  ExplodedNodeSet EvalSet;
2614
7.80k
  StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
2615
2616
7.80k
  bool IsVectorType = A->getBase()->getType()->isVectorType();
2617
2618
  // The "like" case is for situations where C standard prohibits the type to
2619
  // be an lvalue, e.g. taking the address of a subscript of an expression of
2620
  // type "void *".
2621
7.80k
  bool IsGLValueLike = A->isGLValue() ||
2622
6
    (A->getType().isCForbiddenLValueType() && 
!AMgr.getLangOpts().CPlusPlus4
);
2623
2624
7.79k
  for (auto *Node : CheckerPreStmt) {
2625
7.79k
    const LocationContext *LCtx = Node->getLocationContext();
2626
7.79k
    ProgramStateRef state = Node->getState();
2627
2628
7.79k
    if (IsGLValueLike) {
2629
7.79k
      QualType T = A->getType();
2630
2631
      // One of the forbidden LValue types! We still need to have sensible
2632
      // symbolic locations to represent this stuff. Note that arithmetic on
2633
      // void pointers is a GCC extension.
2634
7.79k
      if (T->isVoidType())
2635
4
        T = getContext().CharTy;
2636
2637
7.79k
      SVal V = state->getLValue(T,
2638
7.79k
                                state->getSVal(Idx, LCtx),
2639
7.79k
                                state->getSVal(Base, LCtx));
2640
7.79k
      Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr,
2641
7.79k
          ProgramPoint::PostLValueKind);
2642
2
    } else if (IsVectorType) {
2643
      // FIXME: non-glvalue vector reads are not modelled.
2644
2
      Bldr.generateNode(A, Node, state, nullptr);
2645
0
    } else {
2646
0
      llvm_unreachable("Array subscript should be an lValue when not \
2647
0
a vector and not a forbidden lvalue type");
2648
0
    }
2649
7.79k
  }
2650
2651
7.80k
  getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this);
2652
7.80k
}
2653
2654
/// VisitMemberExpr - Transfer function for member expressions.
2655
void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
2656
50.2k
                                 ExplodedNodeSet &Dst) {
2657
  // FIXME: Prechecks eventually go in ::Visit().
2658
50.2k
  ExplodedNodeSet CheckedSet;
2659
50.2k
  getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this);
2660
2661
50.2k
  ExplodedNodeSet EvalSet;
2662
50.2k
  ValueDecl *Member = M->getMemberDecl();
2663
2664
  // Handle static member variables and enum constants accessed via
2665
  // member syntax.
2666
50.2k
  if (isa<VarDecl>(Member) || 
isa<EnumConstantDecl>(Member)50.2k
) {
2667
7
    for (const auto I : CheckedSet)
2668
7
      VisitCommonDeclRefExpr(M, Member, I, EvalSet);
2669
50.2k
  } else {
2670
50.2k
    StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
2671
50.2k
    ExplodedNodeSet Tmp;
2672
2673
50.2k
    for (const auto I : CheckedSet) {
2674
50.2k
      ProgramStateRef state = I->getState();
2675
50.2k
      const LocationContext *LCtx = I->getLocationContext();
2676
50.2k
      Expr *BaseExpr = M->getBase();
2677
2678
      // Handle C++ method calls.
2679
50.2k
      if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) {
2680
8.68k
        if (MD->isInstance())
2681
8.68k
          state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
2682
2683
8.68k
        SVal MDVal = svalBuilder.getFunctionPointer(MD);
2684
8.68k
        state = state->BindExpr(M, LCtx, MDVal);
2685
2686
8.68k
        Bldr.generateNode(M, I, state);
2687
8.68k
        continue;
2688
8.68k
      }
2689
2690
      // Handle regular struct fields / member variables.
2691
41.5k
      const SubRegion *MR = nullptr;
2692
41.5k
      state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr,
2693
41.5k
                                            /*Result=*/nullptr,
2694
41.5k
                                            /*OutRegionWithAdjustments=*/&MR);
2695
41.5k
      SVal baseExprVal =
2696
41.4k
          MR ? 
loc::MemRegionVal(MR)48
: state->getSVal(BaseExpr, LCtx);
2697
2698
41.5k
      const auto *field = cast<FieldDecl>(Member);
2699
41.5k
      SVal L = state->getLValue(field, baseExprVal);
2700
2701
41.5k
      if (M->isGLValue() || 
M->getType()->isArrayType()48
) {
2702
        // We special-case rvalues of array type because the analyzer cannot
2703
        // reason about them, since we expect all regions to be wrapped in Locs.
2704
        // We instead treat these as lvalues and assume that they will decay to
2705
        // pointers as soon as they are used.
2706
41.4k
        if (!M->isGLValue()) {
2707
3
          assert(M->getType()->isArrayType());
2708
3
          const auto *PE =
2709
3
            dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M));
2710
3
          if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
2711
0
            llvm_unreachable("should always be wrapped in ArrayToPointerDecay");
2712
0
          }
2713
41.4k
        }
2714
2715
41.4k
        if (field->getType()->isReferenceType()) {
2716
354
          if (const MemRegion *R = L.getAsRegion())
2717
354
            L = state->getSVal(R);
2718
0
          else
2719
0
            L = UnknownVal();
2720
354
        }
2721
2722
41.4k
        Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr,
2723
41.4k
                          ProgramPoint::PostLValueKind);
2724
45
      } else {
2725
45
        Bldr.takeNodes(I);
2726
45
        evalLoad(Tmp, M, M, I, state, L);
2727
45
        Bldr.addNodes(Tmp);
2728
45
      }
2729
41.5k
    }
2730
50.2k
  }
2731
2732
50.2k
  getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this);
2733
50.2k
}
2734
2735
void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,
2736
54
                                 ExplodedNodeSet &Dst) {
2737
54
  ExplodedNodeSet AfterPreSet;
2738
54
  getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this);
2739
2740
  // For now, treat all the arguments to C11 atomics as escaping.
2741
  // FIXME: Ideally we should model the behavior of the atomics precisely here.
2742
2743
54
  ExplodedNodeSet AfterInvalidateSet;
2744
54
  StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);
2745
2746
54
  for (const auto I : AfterPreSet) {
2747
54
    ProgramStateRef State = I->getState();
2748
54
    const LocationContext *LCtx = I->getLocationContext();
2749
2750
54
    SmallVector<SVal, 8> ValuesToInvalidate;
2751
219
    for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; 
SI++165
) {
2752
165
      const Expr *SubExpr = AE->getSubExprs()[SI];
2753
165
      SVal SubExprVal = State->getSVal(SubExpr, LCtx);
2754
165
      ValuesToInvalidate.push_back(SubExprVal);
2755
165
    }
2756
2757
54
    State = State->invalidateRegions(ValuesToInvalidate, AE,
2758
54
                                    currBldrCtx->blockCount(),
2759
54
                                    LCtx,
2760
54
                                    /*CausedByPointerEscape*/true,
2761
54
                                    /*Symbols=*/nullptr);
2762
2763
54
    SVal ResultVal = UnknownVal();
2764
54
    State = State->BindExpr(AE, LCtx, ResultVal);
2765
54
    Bldr.generateNode(AE, I, State, nullptr,
2766
54
                      ProgramPoint::PostStmtKind);
2767
54
  }
2768
2769
54
  getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);
2770
54
}
2771
2772
// A value escapes in four possible cases:
2773
// (1) We are binding to something that is not a memory region.
2774
// (2) We are binding to a MemRegion that does not have stack storage.
2775
// (3) We are binding to a top-level parameter region with a non-trivial
2776
//     destructor. We won't see the destructor during analysis, but it's there.
2777
// (4) We are binding to a MemRegion with stack storage that the store
2778
//     does not understand.
2779
ProgramStateRef ExprEngine::processPointerEscapedOnBind(
2780
    ProgramStateRef State, ArrayRef<std::pair<SVal, SVal>> LocAndVals,
2781
    const LocationContext *LCtx, PointerEscapeKind Kind,
2782
112k
    const CallEvent *Call) {
2783
112k
  SmallVector<SVal, 8> Escaped;
2784
73.3k
  for (const std::pair<SVal, SVal> &LocAndVal : LocAndVals) {
2785
    // Cases (1) and (2).
2786
73.3k
    const MemRegion *MR = LocAndVal.first.getAsRegion();
2787
73.3k
    if (!MR || 
!MR->hasStackStorage()73.3k
) {
2788
5.69k
      Escaped.push_back(LocAndVal.second);
2789
5.69k
      continue;
2790
5.69k
    }
2791
2792
    // Case (3).
2793
67.6k
    if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion()))
2794
65.0k
      if (VR->hasStackParametersStorage() && 
VR->getStackFrame()->inTopFrame()14.5k
)
2795
3.79k
        if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
2796
21
          if (!RD->hasTrivialDestructor()) {
2797
4
            Escaped.push_back(LocAndVal.second);
2798
4
            continue;
2799
4
          }
2800
2801
    // Case (4): in order to test that, generate a new state with the binding
2802
    // added. If it is the same state, then it escapes (since the store cannot
2803
    // represent the binding).
2804
    // Do this only if we know that the store is not supposed to generate the
2805
    // same state.
2806
67.6k
    SVal StoredVal = State->getSVal(MR);
2807
67.6k
    if (StoredVal != LocAndVal.second)
2808
62.5k
      if (State ==
2809
62.5k
          (State->bindLoc(loc::MemRegionVal(MR), LocAndVal.second, LCtx)))
2810
83
        Escaped.push_back(LocAndVal.second);
2811
67.6k
  }
2812
2813
112k
  if (Escaped.empty())
2814
107k
    return State;
2815
2816
5.65k
  return escapeValues(State, Escaped, Kind, Call);
2817
5.65k
}
2818
2819
ProgramStateRef
2820
ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,
2821
69.0k
                                        SVal Val, const LocationContext *LCtx) {
2822
69.0k
  std::pair<SVal, SVal> LocAndVal(Loc, Val);
2823
69.0k
  return processPointerEscapedOnBind(State, LocAndVal, LCtx, PSK_EscapeOnBind,
2824
69.0k
                                     nullptr);
2825
69.0k
}
2826
2827
ProgramStateRef
2828
ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
2829
    const InvalidatedSymbols *Invalidated,
2830
    ArrayRef<const MemRegion *> ExplicitRegions,
2831
    const CallEvent *Call,
2832
31.8k
    RegionAndSymbolInvalidationTraits &ITraits) {
2833
31.8k
  if (!Invalidated || Invalidated->empty())
2834
5.06k
    return State;
2835
2836
26.8k
  if (!Call)
2837
234
    return getCheckerManager().runCheckersForPointerEscape(State,
2838
234
                                                           *Invalidated,
2839
234
                                                           nullptr,
2840
234
                                                           PSK_EscapeOther,
2841
234
                                                           &ITraits);
2842
2843
  // If the symbols were invalidated by a call, we want to find out which ones
2844
  // were invalidated directly due to being arguments to the call.
2845
26.5k
  InvalidatedSymbols SymbolsDirectlyInvalidated;
2846
27.9k
  for (const auto I : ExplicitRegions) {
2847
27.9k
    if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>())
2848
7.86k
      SymbolsDirectlyInvalidated.insert(R->getSymbol());
2849
27.9k
  }
2850
2851
26.5k
  InvalidatedSymbols SymbolsIndirectlyInvalidated;
2852
71.4k
  for (const auto &sym : *Invalidated) {
2853
71.4k
    if (SymbolsDirectlyInvalidated.count(sym))
2854
7.82k
      continue;
2855
63.6k
    SymbolsIndirectlyInvalidated.insert(sym);
2856
63.6k
  }
2857
2858
26.5k
  if (!SymbolsDirectlyInvalidated.empty())
2859
7.03k
    State = getCheckerManager().runCheckersForPointerEscape(State,
2860
7.03k
        SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits);
2861
2862
  // Notify about the symbols that get indirectly invalidated by the call.
2863
26.5k
  if (!SymbolsIndirectlyInvalidated.empty())
2864
24.7k
    State = getCheckerManager().runCheckersForPointerEscape(State,
2865
24.7k
        SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits);
2866
2867
26.5k
  return State;
2868
26.5k
}
2869
2870
/// evalBind - Handle the semantics of binding a value to a specific location.
2871
///  This method is used by evalStore and (soon) VisitDeclStmt, and others.
2872
void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
2873
                          ExplodedNode *Pred,
2874
                          SVal location, SVal Val,
2875
69.4k
                          bool atDeclInit, const ProgramPoint *PP) {
2876
69.4k
  const LocationContext *LC = Pred->getLocationContext();
2877
69.4k
  PostStmt PS(StoreE, LC);
2878
69.4k
  if (!PP)
2879
61.0k
    PP = &PS;
2880
2881
  // Do a previsit of the bind.
2882
69.4k
  ExplodedNodeSet CheckedSet;
2883
69.4k
  getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
2884
69.4k
                                         StoreE, *this, *PP);
2885
2886
69.4k
  StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
2887
2888
  // If the location is not a 'Loc', it will already be handled by
2889
  // the checkers.  There is nothing left to do.
2890
69.4k
  if (!location.getAs<Loc>()) {
2891
48
    const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr,
2892
48
                                     /*tag*/nullptr);
2893
48
    ProgramStateRef state = Pred->getState();
2894
48
    state = processPointerEscapedOnBind(state, location, Val, LC);
2895
48
    Bldr.generateNode(L, state, Pred);
2896
48
    return;
2897
48
  }
2898
2899
69.3k
  for (const auto PredI : CheckedSet) {
2900
69.0k
    ProgramStateRef state = PredI->getState();
2901
2902
69.0k
    state = processPointerEscapedOnBind(state, location, Val, LC);
2903
2904
    // When binding the value, pass on the hint that this is a initialization.
2905
    // For initializations, we do not need to inform clients of region
2906
    // changes.
2907
69.0k
    state = state->bindLoc(location.castAs<Loc>(),
2908
69.0k
                           Val, LC, /* notifyChanges = */ !atDeclInit);
2909
2910
69.0k
    const MemRegion *LocReg = nullptr;
2911
69.0k
    if (Optional<loc::MemRegionVal> LocRegVal =
2912
69.0k
            location.getAs<loc::MemRegionVal>()) {
2913
69.0k
      LocReg = LocRegVal->getRegion();
2914
69.0k
    }
2915
2916
69.0k
    const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr);
2917
69.0k
    Bldr.generateNode(L, state, PredI);
2918
69.0k
  }
2919
69.3k
}
2920
2921
/// evalStore - Handle the semantics of a store via an assignment.
2922
///  @param Dst The node set to store generated state nodes
2923
///  @param AssignE The assignment expression if the store happens in an
2924
///         assignment.
2925
///  @param LocationE The location expression that is stored to.
2926
///  @param state The current simulation state
2927
///  @param location The location to store the value
2928
///  @param Val The value to be stored
2929
void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
2930
                             const Expr *LocationE,
2931
                             ExplodedNode *Pred,
2932
                             ProgramStateRef state, SVal location, SVal Val,
2933
29.6k
                             const ProgramPointTag *tag) {
2934
  // Proceed with the store.  We use AssignE as the anchor for the PostStore
2935
  // ProgramPoint if it is non-NULL, and LocationE otherwise.
2936
29.6k
  const Expr *StoreE = AssignE ? AssignE : 
LocationE0
;
2937
2938
  // Evaluate the location (checks for bad dereferences).
2939
29.6k
  ExplodedNodeSet Tmp;
2940
29.6k
  evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false);
2941
2942
29.6k
  if (Tmp.empty())
2943
724
    return;
2944
2945
28.9k
  if (location.isUndef())
2946
0
    return;
2947
2948
28.9k
  for (const auto I : Tmp)
2949
28.9k
    evalBind(Dst, StoreE, I, location, Val, false);
2950
28.9k
}
2951
2952
void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
2953
                          const Expr *NodeEx,
2954
                          const Expr *BoundEx,
2955
                          ExplodedNode *Pred,
2956
                          ProgramStateRef state,
2957
                          SVal location,
2958
                          const ProgramPointTag *tag,
2959
147k
                          QualType LoadTy) {
2960
147k
  assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
2961
147k
  assert(NodeEx);
2962
147k
  assert(BoundEx);
2963
  // Evaluate the location (checks for bad dereferences).
2964
147k
  ExplodedNodeSet Tmp;
2965
147k
  evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true);
2966
147k
  if (Tmp.empty())
2967
269
    return;
2968
2969
147k
  StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
2970
147k
  if (location.isUndef())
2971
0
    return;
2972
2973
  // Proceed with the load.
2974
147k
  for (const auto I : Tmp) {
2975
147k
    state = I->getState();
2976
147k
    const LocationContext *LCtx = I->getLocationContext();
2977
2978
147k
    SVal V = UnknownVal();
2979
147k
    if (location.isValid()) {
2980
147k
      if (LoadTy.isNull())
2981
147k
        LoadTy = BoundEx->getType();
2982
147k
      V = state->getSVal(location.castAs<Loc>(), LoadTy);
2983
147k
    }
2984
2985
147k
    Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag,
2986
147k
                      ProgramPoint::PostLoadKind);
2987
147k
  }
2988
147k
}
2989
2990
void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
2991
                              const Stmt *NodeEx,
2992
                              const Stmt *BoundEx,
2993
                              ExplodedNode *Pred,
2994
                              ProgramStateRef state,
2995
                              SVal location,
2996
177k
                              bool isLoad) {
2997
177k
  StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
2998
  // Early checks for performance reason.
2999
177k
  if (location.isUnknown()) {
3000
168
    return;
3001
168
  }
3002
3003
177k
  ExplodedNodeSet Src;
3004
177k
  BldrTop.takeNodes(Pred);
3005
177k
  StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
3006
177k
  if (Pred->getState() != state) {
3007
    // Associate this new state with an ExplodedNode.
3008
    // FIXME: If I pass null tag, the graph is incorrect, e.g for
3009
    //   int *p;
3010
    //   p = 0;
3011
    //   *p = 0xDEADBEEF;
3012
    // "p = 0" is not noted as "Null pointer value stored to 'p'" but
3013
    // instead "int *p" is noted as
3014
    // "Variable 'p' initialized to a null pointer value"
3015
3016
29.5k
    static SimpleProgramPointTag tag(TagProviderName, "Location");
3017
29.5k
    Bldr.generateNode(NodeEx, Pred, state, &tag);
3018
29.5k
  }
3019
177k
  ExplodedNodeSet Tmp;
3020
177k
  getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
3021
177k
                                             NodeEx, BoundEx, *this);
3022
177k
  BldrTop.addNodes(Tmp);
3023
177k
}
3024
3025
std::pair<const ProgramPointTag *, const ProgramPointTag*>
3026
1.65M
ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
3027
1.65M
  static SimpleProgramPointTag
3028
1.65M
         eagerlyAssumeBinOpBifurcationTrue(TagProviderName,
3029
1.65M
                                           "Eagerly Assume True"),
3030
1.65M
         eagerlyAssumeBinOpBifurcationFalse(TagProviderName,
3031
1.65M
                                            "Eagerly Assume False");
3032
1.65M
  return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
3033
1.65M
                        &eagerlyAssumeBinOpBifurcationFalse);
3034
1.65M
}
3035
3036
void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
3037
                                                   ExplodedNodeSet &Src,
3038
10.3k
                                                   const Expr *Ex) {
3039
10.3k
  StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
3040
3041
10.3k
  for (const auto Pred : Src) {
3042
    // Test if the previous node was as the same expression.  This can happen
3043
    // when the expression fails to evaluate to anything meaningful and
3044
    // (as an optimization) we don't generate a node.
3045
10.3k
    ProgramPoint P = Pred->getLocation();
3046
10.3k
    if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
3047
0
      continue;
3048
0
    }
3049
3050
10.3k
    ProgramStateRef state = Pred->getState();
3051
10.3k
    SVal V = state->getSVal(Ex, Pred->getLocationContext());
3052
10.3k
    Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
3053
10.3k
    if (SEV && 
SEV->isExpression()4.93k
) {
3054
4.93k
      const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
3055
4.93k
        geteagerlyAssumeBinOpBifurcationTags();
3056
3057
4.93k
      ProgramStateRef StateTrue, StateFalse;
3058
4.93k
      std::tie(StateTrue, StateFalse) = state->assume(*SEV);
3059
3060
      // First assume that the condition is true.
3061
4.93k
      if (StateTrue) {
3062
4.15k
        SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
3063
4.15k
        StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
3064
4.15k
        Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
3065
4.15k
      }
3066
3067
      // Next, assume that the condition is false.
3068
4.93k
      if (StateFalse) {
3069
4.51k
        SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
3070
4.51k
        StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
3071
4.51k
        Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
3072
4.51k
      }
3073
4.93k
    }
3074
10.3k
  }
3075
10.3k
}
3076
3077
void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
3078
2
                                 ExplodedNodeSet &Dst) {
3079
2
  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3080
  // We have processed both the inputs and the outputs.  All of the outputs
3081
  // should evaluate to Locs.  Nuke all of their values.
3082
3083
  // FIXME: Some day in the future it would be nice to allow a "plug-in"
3084
  // which interprets the inline asm and stores proper results in the
3085
  // outputs.
3086
3087
2
  ProgramStateRef state = Pred->getState();
3088
3089
2
  for (const Expr *O : A->outputs()) {
3090
2
    SVal X = state->getSVal(O, Pred->getLocationContext());
3091
2
    assert(!X.getAs<NonLoc>());  // Should be an Lval, or unknown, undef.
3092
3093
2
    if (Optional<Loc> LV = X.getAs<Loc>())
3094
2
      state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext());
3095
2
  }
3096
3097
2
  Bldr.generateNode(A, Pred, state);
3098
2
}
3099
3100
void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
3101
0
                                ExplodedNodeSet &Dst) {
3102
0
  StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
3103
0
  Bldr.generateNode(A, Pred, Pred->getState());
3104
0
}
3105
3106
//===----------------------------------------------------------------------===//
3107
// Visualization.
3108
//===----------------------------------------------------------------------===//
3109
3110
#ifndef NDEBUG
3111
namespace llvm {
3112
3113
template<>
3114
struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits {
3115
18
  DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
3116
3117
216
  static bool nodeHasBugReport(const ExplodedNode *N) {
3118
216
    BugReporter &BR = static_cast<ExprEngine &>(
3119
216
      N->getState()->getStateManager().getOwningEngine()).getBugReporter();
3120
3121
216
    const auto EQClasses =
3122
216
        llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end());
3123
3124
48
    for (const auto &EQ : EQClasses) {
3125
48
      for (const auto &I : EQ.getReports()) {
3126
48
        const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get());
3127
48
        if (!PR)
3128
0
          continue;
3129
48
        const ExplodedNode *EN = PR->getErrorNode();
3130
48
        if (EN->getState() == N->getState() &&
3131
4
            EN->getLocation() == N->getLocation())
3132
2
          return true;
3133
48
      }
3134
48
    }
3135
214
    return false;
3136
216
  }
3137
3138
  /// \p PreCallback: callback before break.
3139
  /// \p PostCallback: callback after break.
3140
  /// \p Stop: stop iteration if returns {@code true}
3141
  /// \return Whether {@code Stop} ever returned {@code true}.
3142
  static bool traverseHiddenNodes(
3143
      const ExplodedNode *N,
3144
      llvm::function_ref<void(const ExplodedNode *)> PreCallback,
3145
      llvm::function_ref<void(const ExplodedNode *)> PostCallback,
3146
100
      llvm::function_ref<bool(const ExplodedNode *)> Stop) {
3147
216
    while (true) {
3148
216
      PreCallback(N);
3149
216
      if (Stop(N))
3150
0
        return true;
3151
3152
216
      if (N->succ_size() != 1 || 
!isNodeHidden(N->getFirstSucc())207
)
3153
100
        break;
3154
116
      PostCallback(N);
3155
3156
116
      N = N->getFirstSucc();
3157
116
    }
3158
100
    return false;
3159
100
  }
3160
3161
398
  static bool isNodeHidden(const ExplodedNode *N) {
3162
398
    return N->isTrivial();
3163
398
  }
3164
3165
100
  static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){
3166
100
    std::string Buf;
3167
100
    llvm::raw_string_ostream Out(Buf);
3168
3169
100
    const bool IsDot = true;
3170
100
    const unsigned int Space = 1;
3171
100
    ProgramStateRef State = N->getState();
3172
3173
100
    Out << "{ \"state_id\": " << State->getID()
3174
100
        << ",\\l";
3175
3176
100
    Indent(Out, Space, IsDot) << "\"program_points\": [\\l";
3177
3178
    // Dump program point for all the previously skipped nodes.
3179
100
    traverseHiddenNodes(
3180
100
        N,
3181
216
        [&](const ExplodedNode *OtherNode) {
3182
216
          Indent(Out, Space + 1, IsDot) << "{ ";
3183
216
          OtherNode->getLocation().printJson(Out, /*NL=*/"\\l");
3184
216
          Out << ", \"tag\": ";
3185
216
          if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())
3186
59
            Out << '\"' << Tag->getTagDescription() << "\"";
3187
157
          else
3188
157
            Out << "null";
3189
216
          Out << ", \"node_id\": " << OtherNode->getID() <<
3190
216
                 ", \"is_sink\": " << OtherNode->isSink() <<
3191
216
                 ", \"has_report\": " << nodeHasBugReport(OtherNode) << " }";
3192
216
        },
3193
        // Adds a comma and a new-line between each program point.
3194
116
        [&](const ExplodedNode *) { Out << ",\\l"; },
3195
216
        [&](const ExplodedNode *) { return false; });
3196
3197
100
    Out << "\\l"; // Adds a new-line to the last program point.
3198
100
    Indent(Out, Space, IsDot) << "],\\l";
3199
3200
100
    State->printDOT(Out, N->getLocationContext(), Space);
3201
3202
100
    Out << "\\l}\\l";
3203
100
    return Out.str();
3204
100
  }
3205
};
3206
3207
} // namespace llvm
3208
#endif
3209
3210
0
void ExprEngine::ViewGraph(bool trim) {
3211
0
#ifndef NDEBUG
3212
0
  std::string Filename = DumpGraph(trim);
3213
0
  llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
3214
#else
3215
  llvm::errs() << "Warning: viewing graph requires assertions" << "\n";
3216
#endif
3217
0
}
3218
3219
3220
0
void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) {
3221
0
#ifndef NDEBUG
3222
0
  std::string Filename = DumpGraph(Nodes);
3223
0
  llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
3224
#else
3225
  llvm::errs() << "Warning: viewing graph requires assertions" << "\n";
3226
#endif
3227
0
}
3228
3229
9
std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) {
3230
9
#ifndef NDEBUG
3231
9
  if (trim) {
3232
1
    std::vector<const ExplodedNode *> Src;
3233
3234
    // Iterate through the reports and get their nodes.
3235
1
    for (BugReporter::EQClasses_iterator
3236
2
           EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; 
++EI1
) {
3237
1
      const auto *R =
3238
1
          dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get());
3239
1
      if (!R)
3240
0
        continue;
3241
1
      const auto *N = const_cast<ExplodedNode *>(R->getErrorNode());
3242
1
      Src.push_back(N);
3243
1
    }
3244
1
    return DumpGraph(Src, Filename);
3245
8
  } else {
3246
8
    return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false,
3247
8
                            /*Title=*/"Exploded Graph",
3248
8
                            /*Filename=*/std::string(Filename));
3249
8
  }
3250
#else
3251
  llvm::errs() << "Warning: dumping graph requires assertions" << "\n";
3252
  return "";
3253
#endif
3254
9
}
3255
3256
std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode*> Nodes,
3257
1
                                  StringRef Filename) {
3258
1
#ifndef NDEBUG
3259
1
  std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes));
3260
3261
1
  if (!TrimmedG.get()) {
3262
0
    llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
3263
0
    return "";
3264
1
  } else {
3265
1
    return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine",
3266
1
                            /*ShortNames=*/false,
3267
1
                            /*Title=*/"Trimmed Exploded Graph",
3268
1
                            /*Filename=*/std::string(Filename));
3269
1
  }
3270
#else
3271
  llvm::errs() << "Warning: dumping graph requires assertions" << "\n";
3272
  return "";
3273
#endif
3274
1
}
3275
3276
65.2k
void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() {
3277
65.2k
  static int index = 0;
3278
65.2k
  return &index;
3279
65.2k
}
3280
3281
0
void ExprEngine::anchor() { }