Coverage Report

Created: 2019-07-24 05:18

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