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