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

source code of clang/lib/StaticAnalyzer/Core/ExprEngine.cpp