xref: /llvm-project/clang/lib/StaticAnalyzer/Core/SymbolManager.cpp (revision b9bca883c970d36f408db80df21838c713c326db) 
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/AST/StmtObjC.h"
18 #include "clang/Analysis/Analyses/LiveVariables.h"
19 #include "clang/Analysis/AnalysisDeclContext.h"
20 #include "clang/Basic/LLVM.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
23 #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
24 #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
25 #include "llvm/ADT/FoldingSet.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/Support/Casting.h"
28 #include "llvm/Support/Compiler.h"
29 #include "llvm/Support/ErrorHandling.h"
30 #include "llvm/Support/raw_ostream.h"
31 #include <cassert>
32 
33 using namespace clang;
34 using namespace ento;
35 
36 void SymExpr::anchor() {}
37 
38 LLVM_DUMP_METHOD void SymExpr::dump() const { dumpToStream(llvm::errs()); }
39 
40 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS, const SymExpr *Sym) {
41   OS << '(';
42   Sym->dumpToStream(OS);
43   OS << ')';
44 }
45 
46 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
47                                      const llvm::APSInt &Value) {
48   if (Value.isUnsigned())
49     OS << Value.getZExtValue();
50   else
51     OS << Value.getSExtValue();
52   if (Value.isUnsigned())
53     OS << 'U';
54 }
55 
56 void BinarySymExpr::dumpToStreamImpl(raw_ostream &OS,
57                                      BinaryOperator::Opcode Op) {
58   OS << ' ' << BinaryOperator::getOpcodeStr(Op) << ' ';
59 }
60 
61 void SymbolCast::dumpToStream(raw_ostream &os) const {
62   os << '(' << ToTy.getAsString() << ") (";
63   Operand->dumpToStream(os);
64   os << ')';
65 }
66 
67 void SymbolConjured::dumpToStream(raw_ostream &os) const {
68   os << "conj_$" << getSymbolID() << '{' << T.getAsString() << ", LC"
69      << LCtx->getID();
70   if (S)
71     os << ", S" << S->getID(LCtx->getDecl()->getASTContext());
72   else
73     os << ", no stmt";
74   os << ", #" << Count << '}';
75 }
76 
77 void SymbolDerived::dumpToStream(raw_ostream &os) const {
78   os << "derived_$" << getSymbolID() << '{'
79      << getParentSymbol() << ',' << getRegion() << '}';
80 }
81 
82 void SymbolExtent::dumpToStream(raw_ostream &os) const {
83   os << "extent_$" << getSymbolID() << '{' << getRegion() << '}';
84 }
85 
86 void SymbolMetadata::dumpToStream(raw_ostream &os) const {
87   os << "meta_$" << getSymbolID() << '{'
88      << getRegion() << ',' << T.getAsString() << '}';
89 }
90 
91 void SymbolData::anchor() {}
92 
93 void SymbolRegionValue::dumpToStream(raw_ostream &os) const {
94   os << "reg_$" << getSymbolID()
95      << '<' << getType().getAsString() << ' ' << R << '>';
96 }
97 
98 bool SymExpr::symbol_iterator::operator==(const symbol_iterator &X) const {
99   return itr == X.itr;
100 }
101 
102 bool SymExpr::symbol_iterator::operator!=(const symbol_iterator &X) const {
103   return itr != X.itr;
104 }
105 
106 SymExpr::symbol_iterator::symbol_iterator(const SymExpr *SE) {
107   itr.push_back(SE);
108 }
109 
110 SymExpr::symbol_iterator &SymExpr::symbol_iterator::operator++() {
111   assert(!itr.empty() && "attempting to iterate on an 'end' iterator");
112   expand();
113   return *this;
114 }
115 
116 SymbolRef SymExpr::symbol_iterator::operator*() {
117   assert(!itr.empty() && "attempting to dereference an 'end' iterator");
118   return itr.back();
119 }
120 
121 void SymExpr::symbol_iterator::expand() {
122   const SymExpr *SE = itr.pop_back_val();
123 
124   switch (SE->getKind()) {
125     case SymExpr::SymbolRegionValueKind:
126     case SymExpr::SymbolConjuredKind:
127     case SymExpr::SymbolDerivedKind:
128     case SymExpr::SymbolExtentKind:
129     case SymExpr::SymbolMetadataKind:
130       return;
131     case SymExpr::SymbolCastKind:
132       itr.push_back(cast<SymbolCast>(SE)->getOperand());
133       return;
134     case SymExpr::SymIntExprKind:
135       itr.push_back(cast<SymIntExpr>(SE)->getLHS());
136       return;
137     case SymExpr::IntSymExprKind:
138       itr.push_back(cast<IntSymExpr>(SE)->getRHS());
139       return;
140     case SymExpr::SymSymExprKind: {
141       const auto *x = cast<SymSymExpr>(SE);
142       itr.push_back(x->getLHS());
143       itr.push_back(x->getRHS());
144       return;
145     }
146   }
147   llvm_unreachable("unhandled expansion case");
148 }
149 
150 const SymbolRegionValue*
151 SymbolManager::getRegionValueSymbol(const TypedValueRegion* R) {
152   llvm::FoldingSetNodeID profile;
153   SymbolRegionValue::Profile(profile, R);
154   void *InsertPos;
155   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
156   if (!SD) {
157     SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>();
158     new (SD) SymbolRegionValue(SymbolCounter, R);
159     DataSet.InsertNode(SD, InsertPos);
160     ++SymbolCounter;
161   }
162 
163   return cast<SymbolRegionValue>(SD);
164 }
165 
166 const SymbolConjured* SymbolManager::conjureSymbol(const Stmt *E,
167                                                    const LocationContext *LCtx,
168                                                    QualType T,
169                                                    unsigned Count,
170                                                    const void *SymbolTag) {
171   llvm::FoldingSetNodeID profile;
172   SymbolConjured::Profile(profile, E, T, Count, LCtx, SymbolTag);
173   void *InsertPos;
174   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
175   if (!SD) {
176     SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>();
177     new (SD) SymbolConjured(SymbolCounter, E, LCtx, T, Count, SymbolTag);
178     DataSet.InsertNode(SD, InsertPos);
179     ++SymbolCounter;
180   }
181 
182   return cast<SymbolConjured>(SD);
183 }
184 
185 const SymbolDerived*
186 SymbolManager::getDerivedSymbol(SymbolRef parentSymbol,
187                                 const TypedValueRegion *R) {
188   llvm::FoldingSetNodeID profile;
189   SymbolDerived::Profile(profile, parentSymbol, R);
190   void *InsertPos;
191   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
192   if (!SD) {
193     SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>();
194     new (SD) SymbolDerived(SymbolCounter, parentSymbol, R);
195     DataSet.InsertNode(SD, InsertPos);
196     ++SymbolCounter;
197   }
198 
199   return cast<SymbolDerived>(SD);
200 }
201 
202 const SymbolExtent*
203 SymbolManager::getExtentSymbol(const SubRegion *R) {
204   llvm::FoldingSetNodeID profile;
205   SymbolExtent::Profile(profile, R);
206   void *InsertPos;
207   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
208   if (!SD) {
209     SD = (SymExpr*) BPAlloc.Allocate<SymbolExtent>();
210     new (SD) SymbolExtent(SymbolCounter, R);
211     DataSet.InsertNode(SD, InsertPos);
212     ++SymbolCounter;
213   }
214 
215   return cast<SymbolExtent>(SD);
216 }
217 
218 const SymbolMetadata *
219 SymbolManager::getMetadataSymbol(const MemRegion* R, const Stmt *S, QualType T,
220                                  const LocationContext *LCtx,
221                                  unsigned Count, const void *SymbolTag) {
222   llvm::FoldingSetNodeID profile;
223   SymbolMetadata::Profile(profile, R, S, T, LCtx, Count, SymbolTag);
224   void *InsertPos;
225   SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
226   if (!SD) {
227     SD = (SymExpr*) BPAlloc.Allocate<SymbolMetadata>();
228     new (SD) SymbolMetadata(SymbolCounter, R, S, T, LCtx, Count, SymbolTag);
229     DataSet.InsertNode(SD, InsertPos);
230     ++SymbolCounter;
231   }
232 
233   return cast<SymbolMetadata>(SD);
234 }
235 
236 const SymbolCast*
237 SymbolManager::getCastSymbol(const SymExpr *Op,
238                              QualType From, QualType To) {
239   llvm::FoldingSetNodeID ID;
240   SymbolCast::Profile(ID, Op, From, To);
241   void *InsertPos;
242   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
243   if (!data) {
244     data = (SymbolCast*) BPAlloc.Allocate<SymbolCast>();
245     new (data) SymbolCast(Op, From, To);
246     DataSet.InsertNode(data, InsertPos);
247   }
248 
249   return cast<SymbolCast>(data);
250 }
251 
252 const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs,
253                                                BinaryOperator::Opcode op,
254                                                const llvm::APSInt& v,
255                                                QualType t) {
256   llvm::FoldingSetNodeID ID;
257   SymIntExpr::Profile(ID, lhs, op, v, t);
258   void *InsertPos;
259   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
260 
261   if (!data) {
262     data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>();
263     new (data) SymIntExpr(lhs, op, v, t);
264     DataSet.InsertNode(data, InsertPos);
265   }
266 
267   return cast<SymIntExpr>(data);
268 }
269 
270 const IntSymExpr *SymbolManager::getIntSymExpr(const llvm::APSInt& lhs,
271                                                BinaryOperator::Opcode op,
272                                                const SymExpr *rhs,
273                                                QualType t) {
274   llvm::FoldingSetNodeID ID;
275   IntSymExpr::Profile(ID, lhs, op, rhs, t);
276   void *InsertPos;
277   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
278 
279   if (!data) {
280     data = (IntSymExpr*) BPAlloc.Allocate<IntSymExpr>();
281     new (data) IntSymExpr(lhs, op, rhs, t);
282     DataSet.InsertNode(data, InsertPos);
283   }
284 
285   return cast<IntSymExpr>(data);
286 }
287 
288 const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs,
289                                                BinaryOperator::Opcode op,
290                                                const SymExpr *rhs,
291                                                QualType t) {
292   llvm::FoldingSetNodeID ID;
293   SymSymExpr::Profile(ID, lhs, op, rhs, t);
294   void *InsertPos;
295   SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
296 
297   if (!data) {
298     data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>();
299     new (data) SymSymExpr(lhs, op, rhs, t);
300     DataSet.InsertNode(data, InsertPos);
301   }
302 
303   return cast<SymSymExpr>(data);
304 }
305 
306 QualType SymbolConjured::getType() const {
307   return T;
308 }
309 
310 QualType SymbolDerived::getType() const {
311   return R->getValueType();
312 }
313 
314 QualType SymbolExtent::getType() const {
315   ASTContext &Ctx = R->getMemRegionManager().getContext();
316   return Ctx.getSizeType();
317 }
318 
319 QualType SymbolMetadata::getType() const {
320   return T;
321 }
322 
323 QualType SymbolRegionValue::getType() const {
324   return R->getValueType();
325 }
326 
327 bool SymbolManager::canSymbolicate(QualType T) {
328   T = T.getCanonicalType();
329 
330   if (Loc::isLocType(T))
331     return true;
332 
333   if (T->isIntegralOrEnumerationType())
334     return true;
335 
336   if (T->isRecordType() && !T->isUnionType())
337     return true;
338 
339   return false;
340 }
341 
342 void SymbolManager::addSymbolDependency(const SymbolRef Primary,
343                                         const SymbolRef Dependent) {
344   auto &dependencies = SymbolDependencies[Primary];
345   if (!dependencies) {
346     dependencies = std::make_unique<SymbolRefSmallVectorTy>();
347   }
348   dependencies->push_back(Dependent);
349 }
350 
351 const SymbolRefSmallVectorTy *SymbolManager::getDependentSymbols(
352                                                      const SymbolRef Primary) {
353   SymbolDependTy::const_iterator I = SymbolDependencies.find(Primary);
354   if (I == SymbolDependencies.end())
355     return nullptr;
356   return I->second.get();
357 }
358 
359 void SymbolReaper::markDependentsLive(SymbolRef sym) {
360   // Do not mark dependents more then once.
361   SymbolMapTy::iterator LI = TheLiving.find(sym);
362   assert(LI != TheLiving.end() && "The primary symbol is not live.");
363   if (LI->second == HaveMarkedDependents)
364     return;
365   LI->second = HaveMarkedDependents;
366 
367   if (const SymbolRefSmallVectorTy *Deps = SymMgr.getDependentSymbols(sym)) {
368     for (const auto I : *Deps) {
369       if (TheLiving.find(I) != TheLiving.end())
370         continue;
371       markLive(I);
372     }
373   }
374 }
375 
376 void SymbolReaper::markLive(SymbolRef sym) {
377   TheLiving[sym] = NotProcessed;
378   markDependentsLive(sym);
379 }
380 
381 void SymbolReaper::markLive(const MemRegion *region) {
382   RegionRoots.insert(region->getBaseRegion());
383   markElementIndicesLive(region);
384 }
385 
386 void SymbolReaper::markElementIndicesLive(const MemRegion *region) {
387   for (auto SR = dyn_cast<SubRegion>(region); SR;
388        SR = dyn_cast<SubRegion>(SR->getSuperRegion())) {
389     if (const auto ER = dyn_cast<ElementRegion>(SR)) {
390       SVal Idx = ER->getIndex();
391       for (auto SI = Idx.symbol_begin(), SE = Idx.symbol_end(); SI != SE; ++SI)
392         markLive(*SI);
393     }
394   }
395 }
396 
397 void SymbolReaper::markInUse(SymbolRef sym) {
398   if (isa<SymbolMetadata>(sym))
399     MetadataInUse.insert(sym);
400 }
401 
402 bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
403   // TODO: For now, liveness of a memory region is equivalent to liveness of its
404   // base region. In fact we can do a bit better: say, if a particular FieldDecl
405   // is not used later in the path, we can diagnose a leak of a value within
406   // that field earlier than, say, the variable that contains the field dies.
407   MR = MR->getBaseRegion();
408 
409   if (RegionRoots.count(MR))
410     return true;
411 
412   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
413     return isLive(SR->getSymbol());
414 
415   if (const auto *VR = dyn_cast<VarRegion>(MR))
416     return isLive(VR, true);
417 
418   // FIXME: This is a gross over-approximation. What we really need is a way to
419   // tell if anything still refers to this region. Unlike SymbolicRegions,
420   // AllocaRegions don't have associated symbols, though, so we don't actually
421   // have a way to track their liveness.
422   if (isa<AllocaRegion>(MR))
423     return true;
424 
425   if (isa<CXXThisRegion>(MR))
426     return true;
427 
428   if (isa<MemSpaceRegion>(MR))
429     return true;
430 
431   if (isa<CodeTextRegion>(MR))
432     return true;
433 
434   return false;
435 }
436 
437 bool SymbolReaper::isLive(SymbolRef sym) {
438   if (TheLiving.count(sym)) {
439     markDependentsLive(sym);
440     return true;
441   }
442 
443   bool KnownLive;
444 
445   switch (sym->getKind()) {
446   case SymExpr::SymbolRegionValueKind:
447     KnownLive = isLiveRegion(cast<SymbolRegionValue>(sym)->getRegion());
448     break;
449   case SymExpr::SymbolConjuredKind:
450     KnownLive = false;
451     break;
452   case SymExpr::SymbolDerivedKind:
453     KnownLive = isLive(cast<SymbolDerived>(sym)->getParentSymbol());
454     break;
455   case SymExpr::SymbolExtentKind:
456     KnownLive = isLiveRegion(cast<SymbolExtent>(sym)->getRegion());
457     break;
458   case SymExpr::SymbolMetadataKind:
459     KnownLive = MetadataInUse.count(sym) &&
460                 isLiveRegion(cast<SymbolMetadata>(sym)->getRegion());
461     if (KnownLive)
462       MetadataInUse.erase(sym);
463     break;
464   case SymExpr::SymIntExprKind:
465     KnownLive = isLive(cast<SymIntExpr>(sym)->getLHS());
466     break;
467   case SymExpr::IntSymExprKind:
468     KnownLive = isLive(cast<IntSymExpr>(sym)->getRHS());
469     break;
470   case SymExpr::SymSymExprKind:
471     KnownLive = isLive(cast<SymSymExpr>(sym)->getLHS()) &&
472                 isLive(cast<SymSymExpr>(sym)->getRHS());
473     break;
474   case SymExpr::SymbolCastKind:
475     KnownLive = isLive(cast<SymbolCast>(sym)->getOperand());
476     break;
477   }
478 
479   if (KnownLive)
480     markLive(sym);
481 
482   return KnownLive;
483 }
484 
485 bool
486 SymbolReaper::isLive(const Stmt *ExprVal, const LocationContext *ELCtx) const {
487   if (LCtx == nullptr)
488     return false;
489 
490   if (LCtx != ELCtx) {
491     // If the reaper's location context is a parent of the expression's
492     // location context, then the expression value is now "out of scope".
493     if (LCtx->isParentOf(ELCtx))
494       return false;
495     return true;
496   }
497 
498   // If no statement is provided, everything in this and parent contexts is
499   // live.
500   if (!Loc)
501     return true;
502 
503   return LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, ExprVal);
504 }
505 
506 bool SymbolReaper::isLive(const VarRegion *VR, bool includeStoreBindings) const{
507   const StackFrameContext *VarContext = VR->getStackFrame();
508 
509   if (!VarContext)
510     return true;
511 
512   if (!LCtx)
513     return false;
514   const StackFrameContext *CurrentContext = LCtx->getStackFrame();
515 
516   if (VarContext == CurrentContext) {
517     // If no statement is provided, everything is live.
518     if (!Loc)
519       return true;
520 
521     // Anonymous parameters of an inheriting constructor are live for the entire
522     // duration of the constructor.
523     if (isa<CXXInheritedCtorInitExpr>(Loc))
524       return true;
525 
526     if (LCtx->getAnalysis<RelaxedLiveVariables>()->isLive(Loc, VR->getDecl()))
527       return true;
528 
529     if (!includeStoreBindings)
530       return false;
531 
532     unsigned &cachedQuery =
533       const_cast<SymbolReaper *>(this)->includedRegionCache[VR];
534 
535     if (cachedQuery) {
536       return cachedQuery == 1;
537     }
538 
539     // Query the store to see if the region occurs in any live bindings.
540     if (Store store = reapedStore.getStore()) {
541       bool hasRegion =
542         reapedStore.getStoreManager().includedInBindings(store, VR);
543       cachedQuery = hasRegion ? 1 : 2;
544       return hasRegion;
545     }
546 
547     return false;
548   }
549 
550   return VarContext->isParentOf(CurrentContext);
551 }
552