1//===- SymbolManager.h - Management of Symbolic Values --------------------===//
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 SymbolManager, a class that manages symbolic values
10// created for use by ExprEngine and related classes.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
15#include "clang/AST/ASTContext.h"
16#include "clang/AST/Expr.h"
17#include "clang/Analysis/Analyses/LiveVariables.h"
18#include "clang/Analysis/AnalysisDeclContext.h"
19#include "clang/Basic/LLVM.h"
20#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
24#include "llvm/Support/Compiler.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/raw_ostream.h"
27#include <cassert>
28
29using namespace clang;
30using namespace ento;
31
32void SymExpr::anchor() {}
33
34StringRef SymbolConjured::getKindStr() const { return "conj_$"; }
35StringRef SymbolDerived::getKindStr() const { return "derived_$"; }
36StringRef SymbolExtent::getKindStr() const { return "extent_$"; }
37StringRef SymbolMetadata::getKindStr() const { return "meta_$"; }
38StringRef SymbolRegionValue::getKindStr() const { return "reg_$"; }
39
40LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(os&: llvm::errs()); }
41
42void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) {
43 OS << '(';
44 Sym->dumpToStream(os&: OS);
45 OS << ')';
46}
47
48void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
49 const llvm::APSInt &Value) {
50 if (Value.isUnsigned())
51 OS << Value.getZExtValue();
52 else
53 OS << Value.getSExtValue();
54 if (Value.isUnsigned())
55 OS << 'U';
56}
57
58void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
59 BinaryOperator::Opcode Op) {
60 OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' ';
61}
62
63void SymbolCast::dumpToStream(raw_ostream &os) const {
64 os << '(' << ToTy << ") (";
65 Operand->dumpToStream(os);
66 os << ')';
67}
68
69void UnarySymExpr::dumpToStream(raw_ostream &os) const {
70 os << UnaryOperator::getOpcodeStr(Op);
71 bool Binary = isa<BinarySymExpr>(Val: Operand);
72 if (Binary)
73 os << '(';
74 Operand->dumpToStream(os);
75 if (Binary)
76 os << ')';
77}
78
79const Stmt *SymbolConjured::getStmt() const {
80 // Sometimes the CFG element is invalid, avoid dereferencing it.
81 if (Elem.getParent() == nullptr ||
82 Elem.getIndexInBlock() >= Elem.getParent()->size())
83 return nullptr;
84 switch (Elem->getKind()) {
85 case CFGElement::Initializer:
86 if (const auto *Init = Elem->castAs<CFGInitializer>().getInitializer()) {
87 return Init->getInit();
88 }
89 return nullptr;
90 case CFGElement::ScopeBegin:
91 return Elem->castAs<CFGScopeBegin>().getTriggerStmt();
92 case CFGElement::ScopeEnd:
93 return Elem->castAs<CFGScopeEnd>().getTriggerStmt();
94 case CFGElement::NewAllocator:
95 return Elem->castAs<CFGNewAllocator>().getAllocatorExpr();
96 case CFGElement::LifetimeEnds:
97 return Elem->castAs<CFGLifetimeEnds>().getTriggerStmt();
98 case CFGElement::LoopExit:
99 return Elem->castAs<CFGLoopExit>().getLoopStmt();
100 case CFGElement::Statement:
101 return Elem->castAs<CFGStmt>().getStmt();
102 case CFGElement::Constructor:
103 return Elem->castAs<CFGConstructor>().getStmt();
104 case CFGElement::CXXRecordTypedCall:
105 return Elem->castAs<CFGCXXRecordTypedCall>().getStmt();
106 case CFGElement::AutomaticObjectDtor:
107 return Elem->castAs<CFGAutomaticObjDtor>().getTriggerStmt();
108 case CFGElement::DeleteDtor:
109 return Elem->castAs<CFGDeleteDtor>().getDeleteExpr();
110 case CFGElement::BaseDtor:
111 return nullptr;
112 case CFGElement::MemberDtor:
113 return nullptr;
114 case CFGElement::TemporaryDtor:
115 return Elem->castAs<CFGTemporaryDtor>().getBindTemporaryExpr();
116 case CFGElement::CleanupFunction:
117 return nullptr;
118 }
119 return nullptr;
120}
121
122void SymbolConjured::dumpToStream(raw_ostream &os) const {
123 os << getKindStr() << getSymbolID() << '{' << T << ", LC" << LCtx->getID();
124 if (auto *S = getStmt())
125 os << ", S" << S->getID(Context: LCtx->getDecl()->getASTContext());
126 else
127 os << ", no stmt";
128 os << ", #" << Count << '}';
129}
130
131void SymbolDerived::dumpToStream(raw_ostream &os) const {
132 os << getKindStr() << getSymbolID() << '{' << getParentSymbol() << ','
133 << getRegion() << '}';
134}
135
136void SymbolExtent::dumpToStream(raw_ostream &os) const {
137 os << getKindStr() << getSymbolID() << '{' << getRegion() << '}';
138}
139
140void SymbolMetadata::dumpToStream(raw_ostream &os) const {
141 os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' << T << '}';
142}
143
144void SymbolData::anchor() {}
145
146void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
147 os << getKindStr() << getSymbolID() << '<' << getType() << ' ' << R << '>';
148}
149
150bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
151 return itr == X.itr;
152}
153
154bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
155 return itr != X.itr;
156}
157
158SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
159 itr.push_back(Elt: SE);
160}
161
162SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
163 assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
164 expand();
165 return *this;
166}
167
168SymbolRef SymExpr::symbol_iterator::operator*() {
169 assert(!itr.empty() && "attempting to dereference an 'end' iterator");
170 return itr.back();
171}
172
173void SymExpr::symbol_iterator::expand() {
174 const SymExpr *SE = itr.pop_back_val();
175
176 switch (SE->getKind()) {
177 case SymExpr::SymbolRegionValueKind:
178 case SymExpr::SymbolConjuredKind:
179 case SymExpr::SymbolDerivedKind:
180 case SymExpr::SymbolExtentKind:
181 case SymExpr::SymbolMetadataKind:
182 return;
183 case SymExpr::SymbolCastKind:
184 itr.push_back(Elt: cast<SymbolCast>(Val: SE)->getOperand());
185 return;
186 case SymExpr::UnarySymExprKind:
187 itr.push_back(Elt: cast<UnarySymExpr>(Val: SE)->getOperand());
188 return;
189 case SymExpr::SymIntExprKind:
190 itr.push_back(Elt: cast<SymIntExpr>(Val: SE)->getLHS());
191 return;
192 case SymExpr::IntSymExprKind:
193 itr.push_back(Elt: cast<IntSymExpr>(Val: SE)->getRHS());
194 return;
195 case SymExpr::SymSymExprKind: {
196 const auto *x = cast<SymSymExpr>(Val: SE);
197 itr.push_back(Elt: x->getLHS());
198 itr.push_back(Elt: x->getRHS());
199 return;
200 }
201 }
202 llvm_unreachable("unhandled expansion case");
203}
204
205QualType SymbolConjured::getType() const {
206 return T;
207}
208
209QualType SymbolDerived::getType() const {
210 return R->getValueType();
211}
212
213QualType SymbolExtent::getType() const {
214 ASTContext &Ctx = R->getMemRegionManager().getContext();
215 return Ctx.getSizeType();
216}
217
218QualType SymbolMetadata::getType() const {
219 return T;
220}
221
222QualType SymbolRegionValue::getType() const {
223 return R->getValueType();
224}
225
226bool SymbolManager::canSymbolicate(QualType T) {
227 T = T.getCanonicalType();
228
229 if (Loc::isLocType(T))
230 return true;
231
232 if (T->isIntegralOrEnumerationType())
233 return true;
234
235 if (T->isRecordType() && !T->isUnionType())
236 return true;
237
238 return false;
239}
240
241void SymbolManager::addSymbolDependency(const SymbolRef Primary,
242 const SymbolRef Dependent) {
243 auto &dependencies = SymbolDependencies[Primary];
244 if (!dependencies) {
245 dependencies = std::make_unique<SymbolRefSmallVectorTy>();
246 }
247 dependencies->push_back(Elt: Dependent);
248}
249
250const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
251 const SymbolRef Primary) {
252 SymbolDependTy::const_iterator I = SymbolDependencies.find(Val: Primary);
253 if (I == SymbolDependencies.end())
254 return nullptr;
255 return I->second.get();
256}
257
258void SymbolReaper::markDependentsLive(SymbolRef sym) {
259 // Do not mark dependents more then once.
260 SymbolMapTy::iterator LI = TheLiving.find(Val: sym);
261 assert(LI != TheLiving.end() && "The primary symbol is not live.");
262 if (LI->second == HaveMarkedDependents)
263 return;
264 LI->second = HaveMarkedDependents;
265
266 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(Primary: sym)) {
267 for (const auto I : *Deps) {
268 if (TheLiving.contains(Val: I))
269 continue;
270 markLive(sym: I);
271 }
272 }
273}
274
275void SymbolReaper::markLive(SymbolRef sym) {
276 TheLiving[sym] = NotProcessed;
277 markDependentsLive(sym);
278}
279
280void SymbolReaper::markLive(const MemRegion *region) {
281 LiveRegionRoots.insert(V: region->getBaseRegion());
282 markElementIndicesLive(region);
283}
284
285void SymbolReaper::markLazilyCopied(const clang::ento::MemRegion *region) {
286 LazilyCopiedRegionRoots.insert(V: region->getBaseRegion());
287}
288
289void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
290 for (auto SR = dyn_cast<SubRegion>(Val: region); SR;
291 SR = dyn_cast<SubRegion>(Val: SR->getSuperRegion())) {
292 if (const auto ER = dyn_cast<ElementRegion>(Val: SR)) {
293 SVal Idx = ER->getIndex();
294 for (SymbolRef Sym : Idx.symbols())
295 markLive(sym: Sym);
296 }
297 }
298}
299
300void SymbolReaper::markInUse(SymbolRef sym) {
301 if (isa<SymbolMetadata>(Val: sym))
302 MetadataInUse.insert(V: sym);
303}
304
305bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
306 // TODO: For now, liveness of a memory region is equivalent to liveness of its
307 // base region. In fact we can do a bit better: say, if a particular FieldDecl
308 // is not used later in the path, we can diagnose a leak of a value within
309 // that field earlier than, say, the variable that contains the field dies.
310 MR = MR->getBaseRegion();
311 if (LiveRegionRoots.count(V: MR))
312 return true;
313
314 if (const auto *SR = dyn_cast<SymbolicRegion>(Val: MR))
315 return isLive(sym: SR->getSymbol());
316
317 if (const auto *VR = dyn_cast<VarRegion>(Val: MR))
318 return isLive(VR, includeStoreBindings: true);
319
320 // FIXME: This is a gross over-approximation. What we really need is a way to
321 // tell if anything still refers to this region. Unlike SymbolicRegions,
322 // AllocaRegions don't have associated symbols, though, so we don't actually
323 // have a way to track their liveness.
324 return isa<AllocaRegion, CXXThisRegion, MemSpaceRegion, CodeTextRegion>(Val: MR);
325}
326
327bool SymbolReaper::isLazilyCopiedRegion(const MemRegion *MR) const {
328 // TODO: See comment in isLiveRegion.
329 return LazilyCopiedRegionRoots.count(V: MR->getBaseRegion());
330}
331
332bool SymbolReaper::isReadableRegion(const MemRegion *MR) {
333 return isLiveRegion(MR) || isLazilyCopiedRegion(MR);
334}
335
336bool SymbolReaper::isLive(SymbolRef sym) {
337 if (TheLiving.count(Val: sym)) {
338 markDependentsLive(sym);
339 return true;
340 }
341
342 bool KnownLive;
343
344 switch (sym->getKind()) {
345 case SymExpr::SymbolRegionValueKind:
346 KnownLive = isReadableRegion(MR: cast<SymbolRegionValue>(Val: sym)->getRegion());
347 break;
348 case SymExpr::SymbolConjuredKind:
349 KnownLive = false;
350 break;
351 case SymExpr::SymbolDerivedKind:
352 KnownLive = isLive(sym: cast<SymbolDerived>(Val: sym)->getParentSymbol());
353 break;
354 case SymExpr::SymbolExtentKind:
355 KnownLive = isLiveRegion(MR: cast<SymbolExtent>(Val: sym)->getRegion());
356 break;
357 case SymExpr::SymbolMetadataKind:
358 KnownLive = MetadataInUse.count(V: sym) &&
359 isLiveRegion(MR: cast<SymbolMetadata>(Val: sym)->getRegion());
360 if (KnownLive)
361 MetadataInUse.erase(V: sym);
362 break;
363 case SymExpr::SymIntExprKind:
364 KnownLive = isLive(sym: cast<SymIntExpr>(Val: sym)->getLHS());
365 break;
366 case SymExpr::IntSymExprKind:
367 KnownLive = isLive(sym: cast<IntSymExpr>(Val: sym)->getRHS());
368 break;
369 case SymExpr::SymSymExprKind:
370 KnownLive = isLive(sym: cast<SymSymExpr>(Val: sym)->getLHS()) &&
371 isLive(sym: cast<SymSymExpr>(Val: sym)->getRHS());
372 break;
373 case SymExpr::SymbolCastKind:
374 KnownLive = isLive(sym: cast<SymbolCast>(Val: sym)->getOperand());
375 break;
376 case SymExpr::UnarySymExprKind:
377 KnownLive = isLive(sym: cast<UnarySymExpr>(Val: sym)->getOperand());
378 break;
379 }
380
381 if (KnownLive)
382 markLive(sym);
383
384 return KnownLive;
385}
386
387bool
388SymbolReaper::isLive(const Expr *ExprVal, const LocationContext *ELCtx) const {
389 if (LCtx == nullptr)
390 return false;
391
392 if (LCtx != ELCtx) {
393 // If the reaper's location context is a parent of the expression's
394 // location context, then the expression value is now "out of scope".
395 if (LCtx->isParentOf(LC: ELCtx))
396 return false;
397 return true;
398 }
399
400 // If no statement is provided, everything in this and parent contexts is
401 // live.
402 if (!Loc)
403 return true;
404
405 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, Val: ExprVal);
406}
407
408bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
409 const StackFrameContext *VarContext = VR->getStackFrame();
410
411 if (!VarContext)
412 return true;
413
414 if (!LCtx)
415 return false;
416 const StackFrameContext *CurrentContext = LCtx->getStackFrame();
417
418 if (VarContext == CurrentContext) {
419 // If no statement is provided, everything is live.
420 if (!Loc)
421 return true;
422
423 // Anonymous parameters of an inheriting constructor are live for the entire
424 // duration of the constructor.
425 if (isa<CXXInheritedCtorInitExpr>(Val: Loc))
426 return true;
427
428 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(S: Loc, D: VR->getDecl()))
429 return true;
430
431 if (!includeStoreBindings)
432 return false;
433
434 unsigned &cachedQuery =
435 const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
436
437 if (cachedQuery) {
438 return cachedQuery == 1;
439 }
440
441 // Query the store to see if the region occurs in any live bindings.
442 if (Store store = reapedStore.getStore()) {
443 bool hasRegion =
444 reapedStore.getStoreManager().includedInBindings(store, region: VR);
445 cachedQuery = hasRegion ? 1 : 2;
446 return hasRegion;
447 }
448
449 return false;
450 }
451
452 return VarContext->isParentOf(LC: CurrentContext);
453}
454