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 case CFGElement::FullExprCleanup:
119 return nullptr;
120 }
121 return nullptr;
122}
123
124void SymbolConjured::dumpToStream(raw_ostream &os) const {
125 os << getKindStr() << getSymbolID() << '{' << T << ", LC" << LCtx->getID();
126 if (auto *S = getStmt())
127 os << ", S" << S->getID(Context: LCtx->getDecl()->getASTContext());
128 else
129 os << ", no stmt";
130 os << ", #" << Count << '}';
131}
132
133void SymbolDerived::dumpToStream(raw_ostream &os) const {
134 os << getKindStr() << getSymbolID() << '{' << getParentSymbol() << ','
135 << getRegion() << '}';
136}
137
138void SymbolExtent::dumpToStream(raw_ostream &os) const {
139 os << getKindStr() << getSymbolID() << '{' << getRegion() << '}';
140}
141
142void SymbolMetadata::dumpToStream(raw_ostream &os) const {
143 os << getKindStr() << getSymbolID() << '{' << getRegion() << ',' << T << '}';
144}
145
146void SymbolData::anchor() {}
147
148void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
149 os << getKindStr() << getSymbolID() << '<' << getType() << ' ' << R << '>';
150}
151
152bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
153 return itr == X.itr;
154}
155
156bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
157 return itr != X.itr;
158}
159
160SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
161 itr.push_back(Elt: SE);
162}
163
164SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
165 assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
166 expand();
167 return *this;
168}
169
170SymbolRef SymExpr::symbol_iterator::operator*() {
171 assert(!itr.empty() && "attempting to dereference an 'end' iterator");
172 return itr.back();
173}
174
175void SymExpr::symbol_iterator::expand() {
176 const SymExpr *SE = itr.pop_back_val();
177
178 switch (SE->getKind()) {
179 case SymExpr::SymbolRegionValueKind:
180 case SymExpr::SymbolConjuredKind:
181 case SymExpr::SymbolDerivedKind:
182 case SymExpr::SymbolExtentKind:
183 case SymExpr::SymbolMetadataKind:
184 return;
185 case SymExpr::SymbolCastKind:
186 itr.push_back(Elt: cast<SymbolCast>(Val: SE)->getOperand());
187 return;
188 case SymExpr::UnarySymExprKind:
189 itr.push_back(Elt: cast<UnarySymExpr>(Val: SE)->getOperand());
190 return;
191 case SymExpr::SymIntExprKind:
192 itr.push_back(Elt: cast<SymIntExpr>(Val: SE)->getLHS());
193 return;
194 case SymExpr::IntSymExprKind:
195 itr.push_back(Elt: cast<IntSymExpr>(Val: SE)->getRHS());
196 return;
197 case SymExpr::SymSymExprKind: {
198 const auto *x = cast<SymSymExpr>(Val: SE);
199 itr.push_back(Elt: x->getLHS());
200 itr.push_back(Elt: x->getRHS());
201 return;
202 }
203 }
204 llvm_unreachable("unhandled expansion case");
205}
206
207QualType SymbolConjured::getType() const {
208 return T;
209}
210
211QualType SymbolDerived::getType() const {
212 return R->getValueType();
213}
214
215QualType SymbolExtent::getType() const {
216 ASTContext &Ctx = R->getMemRegionManager().getContext();
217 return Ctx.getSizeType();
218}
219
220QualType SymbolMetadata::getType() const {
221 return T;
222}
223
224QualType SymbolRegionValue::getType() const {
225 return R->getValueType();
226}
227
228bool SymbolManager::canSymbolicate(QualType T) {
229 T = T.getCanonicalType();
230
231 if (Loc::isLocType(T))
232 return true;
233
234 if (T->isIntegralOrEnumerationType())
235 return true;
236
237 if (T->isRecordType() && !T->isUnionType())
238 return true;
239
240 return false;
241}
242
243void SymbolManager::addSymbolDependency(const SymbolRef Primary,
244 const SymbolRef Dependent) {
245 auto &dependencies = SymbolDependencies[Primary];
246 if (!dependencies) {
247 dependencies = std::make_unique<SymbolRefSmallVectorTy>();
248 }
249 dependencies->push_back(Elt: Dependent);
250}
251
252const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
253 const SymbolRef Primary) {
254 SymbolDependTy::const_iterator I = SymbolDependencies.find(Val: Primary);
255 if (I == SymbolDependencies.end())
256 return nullptr;
257 return I->second.get();
258}
259
260void SymbolReaper::markDependentsLive(SymbolRef sym) {
261 // Do not mark dependents more then once.
262 SymbolMapTy::iterator LI = TheLiving.find(Val: sym);
263 assert(LI != TheLiving.end() && "The primary symbol is not live.");
264 if (LI->second == HaveMarkedDependents)
265 return;
266 LI->second = HaveMarkedDependents;
267
268 if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(Primary: sym)) {
269 for (const auto I : *Deps) {
270 if (TheLiving.contains(Val: I))
271 continue;
272 markLive(sym: I);
273 }
274 }
275}
276
277void SymbolReaper::markLive(SymbolRef sym) {
278 TheLiving[sym] = NotProcessed;
279 markDependentsLive(sym);
280}
281
282void SymbolReaper::markLive(const MemRegion *region) {
283 LiveRegionRoots.insert(V: region->getBaseRegion());
284 markElementIndicesLive(region);
285}
286
287void SymbolReaper::markLazilyCopied(const clang::ento::MemRegion *region) {
288 LazilyCopiedRegionRoots.insert(V: region->getBaseRegion());
289}
290
291void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
292 for (auto SR = dyn_cast<SubRegion>(Val: region); SR;
293 SR = dyn_cast<SubRegion>(Val: SR->getSuperRegion())) {
294 if (const auto ER = dyn_cast<ElementRegion>(Val: SR)) {
295 SVal Idx = ER->getIndex();
296 for (SymbolRef Sym : Idx.symbols())
297 markLive(sym: Sym);
298 }
299 }
300}
301
302void SymbolReaper::markInUse(SymbolRef sym) {
303 if (isa<SymbolMetadata>(Val: sym))
304 MetadataInUse.insert(V: sym);
305}
306
307bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
308 // TODO: For now, liveness of a memory region is equivalent to liveness of its
309 // base region. In fact we can do a bit better: say, if a particular FieldDecl
310 // is not used later in the path, we can diagnose a leak of a value within
311 // that field earlier than, say, the variable that contains the field dies.
312 MR = MR->getBaseRegion();
313 if (LiveRegionRoots.count(V: MR))
314 return true;
315
316 if (const auto *SR = dyn_cast<SymbolicRegion>(Val: MR))
317 return isLive(sym: SR->getSymbol());
318
319 if (const auto *VR = dyn_cast<VarRegion>(Val: MR))
320 return isLive(VR, includeStoreBindings: true);
321
322 // FIXME: This is a gross over-approximation. What we really need is a way to
323 // tell if anything still refers to this region. Unlike SymbolicRegions,
324 // AllocaRegions don't have associated symbols, though, so we don't actually
325 // have a way to track their liveness.
326 return isa<AllocaRegion, CXXThisRegion, MemSpaceRegion, CodeTextRegion>(Val: MR);
327}
328
329bool SymbolReaper::isLazilyCopiedRegion(const MemRegion *MR) const {
330 // TODO: See comment in isLiveRegion.
331 return LazilyCopiedRegionRoots.count(V: MR->getBaseRegion());
332}
333
334bool SymbolReaper::isReadableRegion(const MemRegion *MR) {
335 return isLiveRegion(MR) || isLazilyCopiedRegion(MR);
336}
337
338bool SymbolReaper::isLive(SymbolRef sym) {
339 if (TheLiving.count(Val: sym)) {
340 markDependentsLive(sym);
341 return true;
342 }
343
344 bool KnownLive;
345
346 switch (sym->getKind()) {
347 case SymExpr::SymbolRegionValueKind:
348 KnownLive = isReadableRegion(MR: cast<SymbolRegionValue>(Val: sym)->getRegion());
349 break;
350 case SymExpr::SymbolConjuredKind:
351 KnownLive = false;
352 break;
353 case SymExpr::SymbolDerivedKind:
354 KnownLive = isLive(sym: cast<SymbolDerived>(Val: sym)->getParentSymbol());
355 break;
356 case SymExpr::SymbolExtentKind:
357 KnownLive = isLiveRegion(MR: cast<SymbolExtent>(Val: sym)->getRegion());
358 break;
359 case SymExpr::SymbolMetadataKind:
360 KnownLive = MetadataInUse.count(V: sym) &&
361 isLiveRegion(MR: cast<SymbolMetadata>(Val: sym)->getRegion());
362 if (KnownLive)
363 MetadataInUse.erase(V: sym);
364 break;
365 case SymExpr::SymIntExprKind:
366 KnownLive = isLive(sym: cast<SymIntExpr>(Val: sym)->getLHS());
367 break;
368 case SymExpr::IntSymExprKind:
369 KnownLive = isLive(sym: cast<IntSymExpr>(Val: sym)->getRHS());
370 break;
371 case SymExpr::SymSymExprKind:
372 KnownLive = isLive(sym: cast<SymSymExpr>(Val: sym)->getLHS()) &&
373 isLive(sym: cast<SymSymExpr>(Val: sym)->getRHS());
374 break;
375 case SymExpr::SymbolCastKind:
376 KnownLive = isLive(sym: cast<SymbolCast>(Val: sym)->getOperand());
377 break;
378 case SymExpr::UnarySymExprKind:
379 KnownLive = isLive(sym: cast<UnarySymExpr>(Val: sym)->getOperand());
380 break;
381 }
382
383 if (KnownLive)
384 markLive(sym);
385
386 return KnownLive;
387}
388
389bool
390SymbolReaper::isLive(const Expr *ExprVal, const LocationContext *ELCtx) const {
391 if (LCtx == nullptr)
392 return false;
393
394 if (LCtx != ELCtx) {
395 // If the reaper's location context is a parent of the expression's
396 // location context, then the expression value is now "out of scope".
397 if (LCtx->isParentOf(LC: ELCtx))
398 return false;
399 return true;
400 }
401
402 // If no statement is provided, everything in this and parent contexts is
403 // live.
404 if (!Loc)
405 return true;
406
407 return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, Val: ExprVal);
408}
409
410bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
411 const StackFrameContext *VarContext = VR->getStackFrame();
412
413 if (!VarContext)
414 return true;
415
416 if (!LCtx)
417 return false;
418 const StackFrameContext *CurrentContext = LCtx->getStackFrame();
419
420 if (VarContext == CurrentContext) {
421 // If no statement is provided, everything is live.
422 if (!Loc)
423 return true;
424
425 // Anonymous parameters of an inheriting constructor are live for the entire
426 // duration of the constructor.
427 if (isa<CXXInheritedCtorInitExpr>(Val: Loc))
428 return true;
429
430 if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(S: Loc, D: VR->getDecl()))
431 return true;
432
433 if (!includeStoreBindings)
434 return false;
435
436 unsigned &cachedQuery =
437 const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
438
439 if (cachedQuery) {
440 return cachedQuery == 1;
441 }
442
443 // Query the store to see if the region occurs in any live bindings.
444 if (Store store = reapedStore.getStore()) {
445 bool hasRegion =
446 reapedStore.getStoreManager().includedInBindings(store, region: VR);
447 cachedQuery = hasRegion ? 1 : 2;
448 return hasRegion;
449 }
450
451 return false;
452 }
453
454 return VarContext->isParentOf(LC: CurrentContext);
455}
456