1 //===- Environment.cpp - Map from Stmt* to Locations/Values ---------------===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defined the Environment and EnvironmentManager classes.
11 //===----------------------------------------------------------------------===//
13 #include "clang/StaticAnalyzer/Core/PathSensitive/Environment.h"
14 #include "clang/AST/Expr.h"
15 #include "clang/AST/ExprCXX.h"
16 #include "clang/AST/PrettyPrinter.h"
17 #include "clang/AST/Stmt.h"
18 #include "clang/AST/StmtObjC.h"
19 #include "clang/Analysis/AnalysisDeclContext.h"
20 #include "clang/Basic/JsonSupport.h"
21 #include "clang/Basic/LLVM.h"
22 #include "clang/Basic/LangOptions.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
26 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
27 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
28 #include "llvm/ADT/ImmutableMap.h"
29 #include "llvm/ADT/SmallPtrSet.h"
30 #include "llvm/Support/Casting.h"
31 #include "llvm/Support/ErrorHandling.h"
32 #include "llvm/Support/raw_ostream.h"
35 using namespace clang
;
38 static const Expr
*ignoreTransparentExprs(const Expr
*E
) {
39 E
= E
->IgnoreParens();
41 switch (E
->getStmtClass()) {
42 case Stmt::OpaqueValueExprClass
:
43 if (const Expr
*SE
= cast
<OpaqueValueExpr
>(E
)->getSourceExpr()) {
48 case Stmt::ExprWithCleanupsClass
:
49 E
= cast
<ExprWithCleanups
>(E
)->getSubExpr();
51 case Stmt::ConstantExprClass
:
52 E
= cast
<ConstantExpr
>(E
)->getSubExpr();
54 case Stmt::CXXBindTemporaryExprClass
:
55 E
= cast
<CXXBindTemporaryExpr
>(E
)->getSubExpr();
57 case Stmt::SubstNonTypeTemplateParmExprClass
:
58 E
= cast
<SubstNonTypeTemplateParmExpr
>(E
)->getReplacement();
61 // This is the base case: we can't look through more than we already have.
65 return ignoreTransparentExprs(E
);
68 static const Stmt
*ignoreTransparentExprs(const Stmt
*S
) {
69 if (const auto *E
= dyn_cast
<Expr
>(S
))
70 return ignoreTransparentExprs(E
);
74 EnvironmentEntry::EnvironmentEntry(const Stmt
*S
, const LocationContext
*L
)
75 : std::pair
<const Stmt
*,
76 const StackFrameContext
*>(ignoreTransparentExprs(S
),
77 L
? L
->getStackFrame()
80 SVal
Environment::lookupExpr(const EnvironmentEntry
&E
) const {
81 const SVal
* X
= ExprBindings
.lookup(E
);
89 SVal
Environment::getSVal(const EnvironmentEntry
&Entry
,
90 SValBuilder
& svalBuilder
) const {
91 const Stmt
*S
= Entry
.getStmt();
92 assert(!isa
<ObjCForCollectionStmt
>(S
) &&
93 "Use ExprEngine::hasMoreIteration()!");
94 assert((isa
<Expr
, ReturnStmt
>(S
)) &&
95 "Environment can only argue about Exprs, since only they express "
96 "a value! Any non-expression statement stored in Environment is a "
98 const LocationContext
*LCtx
= Entry
.getLocationContext();
100 switch (S
->getStmtClass()) {
101 case Stmt::CXXBindTemporaryExprClass
:
102 case Stmt::ExprWithCleanupsClass
:
103 case Stmt::GenericSelectionExprClass
:
104 case Stmt::ConstantExprClass
:
105 case Stmt::ParenExprClass
:
106 case Stmt::SubstNonTypeTemplateParmExprClass
:
107 llvm_unreachable("Should have been handled by ignoreTransparentExprs");
109 case Stmt::AddrLabelExprClass
:
110 case Stmt::CharacterLiteralClass
:
111 case Stmt::CXXBoolLiteralExprClass
:
112 case Stmt::CXXScalarValueInitExprClass
:
113 case Stmt::ImplicitValueInitExprClass
:
114 case Stmt::IntegerLiteralClass
:
115 case Stmt::ObjCBoolLiteralExprClass
:
116 case Stmt::CXXNullPtrLiteralExprClass
:
117 case Stmt::ObjCStringLiteralClass
:
118 case Stmt::StringLiteralClass
:
119 case Stmt::TypeTraitExprClass
:
120 case Stmt::SizeOfPackExprClass
:
121 case Stmt::PredefinedExprClass
:
122 // Known constants; defer to SValBuilder.
123 return *svalBuilder
.getConstantVal(cast
<Expr
>(S
));
125 case Stmt::ReturnStmtClass
: {
126 const auto *RS
= cast
<ReturnStmt
>(S
);
127 if (const Expr
*RE
= RS
->getRetValue())
128 return getSVal(EnvironmentEntry(RE
, LCtx
), svalBuilder
);
129 return UndefinedVal();
132 // Handle all other Stmt* using a lookup.
134 return lookupExpr(EnvironmentEntry(S
, LCtx
));
138 Environment
EnvironmentManager::bindExpr(Environment Env
,
139 const EnvironmentEntry
&E
,
144 return Environment(F
.remove(Env
.ExprBindings
, E
));
148 return Environment(F
.add(Env
.ExprBindings
, E
, V
));
153 class MarkLiveCallback final
: public SymbolVisitor
{
154 SymbolReaper
&SymReaper
;
157 MarkLiveCallback(SymbolReaper
&symreaper
) : SymReaper(symreaper
) {}
159 bool VisitSymbol(SymbolRef sym
) override
{
160 SymReaper
.markLive(sym
);
164 bool VisitMemRegion(const MemRegion
*R
) override
{
165 SymReaper
.markLive(R
);
172 // removeDeadBindings:
173 // - Remove subexpression bindings.
174 // - Remove dead block expression bindings.
175 // - Keep live block expression bindings:
176 // - Mark their reachable symbols live in SymbolReaper,
177 // see ScanReachableSymbols.
178 // - Mark the region in DRoots if the binding is a loc::MemRegionVal.
180 EnvironmentManager::removeDeadBindings(Environment Env
,
181 SymbolReaper
&SymReaper
,
182 ProgramStateRef ST
) {
183 // We construct a new Environment object entirely, as this is cheaper than
184 // individually removing all the subexpression bindings (which will greatly
185 // outnumber block-level expression bindings).
186 Environment NewEnv
= getInitialEnvironment();
188 MarkLiveCallback
CB(SymReaper
);
189 ScanReachableSymbols
RSScaner(ST
, CB
);
191 llvm::ImmutableMapRef
<EnvironmentEntry
, SVal
>
192 EBMapRef(NewEnv
.ExprBindings
.getRootWithoutRetain(),
195 // Iterate over the block-expr bindings.
196 for (Environment::iterator I
= Env
.begin(), End
= Env
.end(); I
!= End
; ++I
) {
197 const EnvironmentEntry
&BlkExpr
= I
.getKey();
198 SVal X
= I
.getData();
200 const Expr
*E
= dyn_cast
<Expr
>(BlkExpr
.getStmt());
204 if (SymReaper
.isLive(E
, BlkExpr
.getLocationContext())) {
205 // Copy the binding to the new map.
206 EBMapRef
= EBMapRef
.add(BlkExpr
, X
);
208 // Mark all symbols in the block expr's value live.
213 NewEnv
.ExprBindings
= EBMapRef
.asImmutableMap();
217 void Environment::printJson(raw_ostream
&Out
, const ASTContext
&Ctx
,
218 const LocationContext
*LCtx
, const char *NL
,
219 unsigned int Space
, bool IsDot
) const {
220 Indent(Out
, Space
, IsDot
) << "\"environment\": ";
222 if (ExprBindings
.isEmpty()) {
223 Out
<< "null," << NL
;
229 // Find the freshest location context.
230 llvm::SmallPtrSet
<const LocationContext
*, 16> FoundContexts
;
231 for (const auto &I
: *this) {
232 const LocationContext
*LC
= I
.first
.getLocationContext();
233 if (FoundContexts
.count(LC
) == 0) {
234 // This context is fresher than all other contexts so far.
236 for (const LocationContext
*LCI
= LC
; LCI
; LCI
= LCI
->getParent())
237 FoundContexts
.insert(LCI
);
244 Out
<< "{ \"pointer\": \"" << (const void *)LCtx
->getStackFrame()
245 << "\", \"items\": [" << NL
;
246 PrintingPolicy PP
= Ctx
.getPrintingPolicy();
248 LCtx
->printJson(Out
, NL
, Space
, IsDot
, [&](const LocationContext
*LC
) {
250 bool HasItem
= false;
251 unsigned int InnerSpace
= Space
+ 1;
253 // Store the last ExprBinding which we will print.
254 BindingsTy::iterator LastI
= ExprBindings
.end();
255 for (BindingsTy::iterator I
= ExprBindings
.begin(); I
!= ExprBindings
.end();
257 if (I
->first
.getLocationContext() != LC
)
265 const Stmt
*S
= I
->first
.getStmt();
267 assert(S
!= nullptr && "Expected non-null Stmt");
272 for (BindingsTy::iterator I
= ExprBindings
.begin(); I
!= ExprBindings
.end();
274 if (I
->first
.getLocationContext() != LC
)
277 const Stmt
*S
= I
->first
.getStmt();
278 Indent(Out
, InnerSpace
, IsDot
)
279 << "{ \"stmt_id\": " << S
->getID(Ctx
) << ", \"kind\": \""
280 << S
->getStmtClassName() << "\", \"pretty\": ";
281 S
->printJson(Out
, nullptr, PP
, /*AddQuotes=*/true);
283 Out
<< ", \"value\": ";
284 I
->second
.printJson(Out
, /*AddQuotes=*/true);
294 Indent(Out
, --InnerSpace
, IsDot
) << ']';
299 Indent(Out
, --Space
, IsDot
) << "]}," << NL
;