1//===- SymbolManager.h - Management of Symbolic Values ----------*- C++ -*-===//
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#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
15#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
16
17#include "clang/AST/Expr.h"
18#include "clang/AST/Type.h"
19#include "clang/Analysis/AnalysisDeclContext.h"
20#include "clang/Basic/LLVM.h"
21#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntPtr.h"
22#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
23#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
25#include "llvm/ADT/DenseMap.h"
26#include "llvm/ADT/DenseSet.h"
27#include "llvm/ADT/FoldingSet.h"
28#include "llvm/ADT/ImmutableSet.h"
29#include "llvm/ADT/iterator_range.h"
30#include "llvm/Support/Allocator.h"
31#include <cassert>
32
33namespace clang {
34
35class ASTContext;
36class Stmt;
37
38namespace ento {
39
40class BasicValueFactory;
41class StoreManager;
42
43///A symbol representing the value stored at a MemRegion.
44class SymbolRegionValue : public SymbolData {
45 const TypedValueRegion *R;
46
47 friend class SymExprAllocator;
48 SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
49 : SymbolData(ClassKind, sym), R(r) {
50 assert(r);
51 assert(isValidTypeForSymbol(r->getValueType()));
52 }
53
54public:
55 LLVM_ATTRIBUTE_RETURNS_NONNULL
56 const TypedValueRegion *getRegion() const { return R; }
57
58 static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
59 profile.AddInteger(I: (unsigned)ClassKind);
60 profile.AddPointer(Ptr: R);
61 }
62
63 void Profile(llvm::FoldingSetNodeID& profile) override {
64 Profile(profile, R);
65 }
66
67 StringRef getKindStr() const override;
68
69 void dumpToStream(raw_ostream &os) const override;
70 const MemRegion *getOriginRegion() const override { return getRegion(); }
71
72 QualType getType() const override;
73
74 // Implement isa<T> support.
75 static constexpr Kind ClassKind = SymbolRegionValueKind;
76 static bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
77 static constexpr bool classof(Kind K) { return K == ClassKind; }
78};
79
80/// A symbol representing the result of an expression in the case when we do
81/// not know anything about what the expression is.
82class SymbolConjured : public SymbolData {
83 ConstCFGElementRef Elem;
84 QualType T;
85 unsigned Count;
86 const LocationContext *LCtx;
87 const void *SymbolTag;
88
89 friend class SymExprAllocator;
90 SymbolConjured(SymbolID sym, ConstCFGElementRef elem,
91 const LocationContext *lctx, QualType t, unsigned count,
92 const void *symbolTag)
93 : SymbolData(ClassKind, sym), Elem(elem), T(t), Count(count), LCtx(lctx),
94 SymbolTag(symbolTag) {
95 assert(lctx);
96 assert(isValidTypeForSymbol(t));
97 }
98
99public:
100 ConstCFGElementRef getCFGElementRef() const { return Elem; }
101
102 // It might return null.
103 const Stmt *getStmt() const;
104
105 unsigned getCount() const { return Count; }
106 /// It might return null.
107 const void *getTag() const { return SymbolTag; }
108
109 QualType getType() const override;
110
111 StringRef getKindStr() const override;
112
113 void dumpToStream(raw_ostream &os) const override;
114
115 static void Profile(llvm::FoldingSetNodeID &profile, ConstCFGElementRef Elem,
116 const LocationContext *LCtx, QualType T, unsigned Count,
117 const void *SymbolTag) {
118 profile.AddInteger(I: (unsigned)ClassKind);
119 profile.Add(x: Elem);
120 profile.AddPointer(Ptr: LCtx);
121 profile.Add(x: T);
122 profile.AddInteger(I: Count);
123 profile.AddPointer(Ptr: SymbolTag);
124 }
125
126 void Profile(llvm::FoldingSetNodeID& profile) override {
127 Profile(profile, Elem, LCtx, T, Count, SymbolTag);
128 }
129
130 // Implement isa<T> support.
131 static constexpr Kind ClassKind = SymbolConjuredKind;
132 static bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
133 static constexpr bool classof(Kind K) { return K == ClassKind; }
134};
135
136/// A symbol representing the value of a MemRegion whose parent region has
137/// symbolic value.
138class SymbolDerived : public SymbolData {
139 SymbolRef parentSymbol;
140 const TypedValueRegion *R;
141
142 friend class SymExprAllocator;
143 SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
144 : SymbolData(ClassKind, sym), parentSymbol(parent), R(r) {
145 assert(parent);
146 assert(r);
147 assert(isValidTypeForSymbol(r->getValueType()));
148 }
149
150public:
151 LLVM_ATTRIBUTE_RETURNS_NONNULL
152 SymbolRef getParentSymbol() const { return parentSymbol; }
153 LLVM_ATTRIBUTE_RETURNS_NONNULL
154 const TypedValueRegion *getRegion() const { return R; }
155
156 QualType getType() const override;
157
158 StringRef getKindStr() const override;
159
160 void dumpToStream(raw_ostream &os) const override;
161 const MemRegion *getOriginRegion() const override { return getRegion(); }
162
163 static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
164 const TypedValueRegion *r) {
165 profile.AddInteger(I: (unsigned)ClassKind);
166 profile.AddPointer(Ptr: r);
167 profile.AddPointer(Ptr: parent);
168 }
169
170 void Profile(llvm::FoldingSetNodeID& profile) override {
171 Profile(profile, parent: parentSymbol, r: R);
172 }
173
174 // Implement isa<T> support.
175 static constexpr Kind ClassKind = SymbolDerivedKind;
176 static bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
177 static constexpr bool classof(Kind K) { return K == ClassKind; }
178};
179
180/// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
181/// Clients should not ask the SymbolManager for a region's extent. Always use
182/// SubRegion::getExtent instead -- the value returned may not be a symbol.
183class SymbolExtent : public SymbolData {
184 const SubRegion *R;
185
186 friend class SymExprAllocator;
187 SymbolExtent(SymbolID sym, const SubRegion *r)
188 : SymbolData(ClassKind, sym), R(r) {
189 assert(r);
190 }
191
192public:
193 LLVM_ATTRIBUTE_RETURNS_NONNULL
194 const SubRegion *getRegion() const { return R; }
195
196 QualType getType() const override;
197
198 StringRef getKindStr() const override;
199
200 void dumpToStream(raw_ostream &os) const override;
201
202 static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
203 profile.AddInteger(I: (unsigned)ClassKind);
204 profile.AddPointer(Ptr: R);
205 }
206
207 void Profile(llvm::FoldingSetNodeID& profile) override {
208 Profile(profile, R);
209 }
210
211 // Implement isa<T> support.
212 static constexpr Kind ClassKind = SymbolExtentKind;
213 static bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
214 static constexpr bool classof(Kind K) { return K == ClassKind; }
215};
216
217/// SymbolMetadata - Represents path-dependent metadata about a specific region.
218/// Metadata symbols remain live as long as they are marked as in use before
219/// dead-symbol sweeping AND their associated regions are still alive.
220/// Intended for use by checkers.
221class SymbolMetadata : public SymbolData {
222 const MemRegion* R;
223 const Stmt *S;
224 QualType T;
225 const LocationContext *LCtx;
226 /// Count can be used to differentiate regions corresponding to
227 /// different loop iterations, thus, making the symbol path-dependent.
228 unsigned Count;
229 const void *Tag;
230
231 friend class SymExprAllocator;
232 SymbolMetadata(SymbolID sym, const MemRegion *r, const Stmt *s, QualType t,
233 const LocationContext *LCtx, unsigned count, const void *tag)
234 : SymbolData(ClassKind, sym), R(r), S(s), T(t), LCtx(LCtx), Count(count),
235 Tag(tag) {
236 assert(r);
237 assert(s);
238 assert(isValidTypeForSymbol(t));
239 assert(LCtx);
240 assert(tag);
241 }
242
243 public:
244 LLVM_ATTRIBUTE_RETURNS_NONNULL
245 const MemRegion *getRegion() const { return R; }
246
247 LLVM_ATTRIBUTE_RETURNS_NONNULL
248 const Stmt *getStmt() const { return S; }
249
250 LLVM_ATTRIBUTE_RETURNS_NONNULL
251 const LocationContext *getLocationContext() const { return LCtx; }
252
253 unsigned getCount() const { return Count; }
254
255 LLVM_ATTRIBUTE_RETURNS_NONNULL
256 const void *getTag() const { return Tag; }
257
258 QualType getType() const override;
259
260 StringRef getKindStr() const override;
261
262 void dumpToStream(raw_ostream &os) const override;
263
264 static void Profile(llvm::FoldingSetNodeID &profile, const MemRegion *R,
265 const Stmt *S, QualType T, const LocationContext *LCtx,
266 unsigned Count, const void *Tag) {
267 profile.AddInteger(I: (unsigned)ClassKind);
268 profile.AddPointer(Ptr: R);
269 profile.AddPointer(Ptr: S);
270 profile.Add(x: T);
271 profile.AddPointer(Ptr: LCtx);
272 profile.AddInteger(I: Count);
273 profile.AddPointer(Ptr: Tag);
274 }
275
276 void Profile(llvm::FoldingSetNodeID& profile) override {
277 Profile(profile, R, S, T, LCtx, Count, Tag);
278 }
279
280 // Implement isa<T> support.
281 static constexpr Kind ClassKind = SymbolMetadataKind;
282 static bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
283 static constexpr bool classof(Kind K) { return K == ClassKind; }
284};
285
286/// Represents a cast expression.
287class SymbolCast : public SymExpr {
288 const SymExpr *Operand;
289
290 /// Type of the operand.
291 QualType FromTy;
292
293 /// The type of the result.
294 QualType ToTy;
295
296 friend class SymExprAllocator;
297 SymbolCast(SymbolID Sym, const SymExpr *In, QualType From, QualType To)
298 : SymExpr(ClassKind, Sym), Operand(In), FromTy(From), ToTy(To) {
299 assert(In);
300 assert(isValidTypeForSymbol(From));
301 // FIXME: GenericTaintChecker creates symbols of void type.
302 // Otherwise, 'To' should also be a valid type.
303 }
304
305public:
306 unsigned computeComplexity() const override {
307 if (Complexity == 0)
308 Complexity = 1 + Operand->computeComplexity();
309 return Complexity;
310 }
311
312 QualType getType() const override { return ToTy; }
313
314 LLVM_ATTRIBUTE_RETURNS_NONNULL
315 const SymExpr *getOperand() const { return Operand; }
316
317 void dumpToStream(raw_ostream &os) const override;
318
319 static void Profile(llvm::FoldingSetNodeID& ID,
320 const SymExpr *In, QualType From, QualType To) {
321 ID.AddInteger(I: (unsigned)ClassKind);
322 ID.AddPointer(Ptr: In);
323 ID.Add(x: From);
324 ID.Add(x: To);
325 }
326
327 void Profile(llvm::FoldingSetNodeID& ID) override {
328 Profile(ID, In: Operand, From: FromTy, To: ToTy);
329 }
330
331 // Implement isa<T> support.
332 static constexpr Kind ClassKind = SymbolCastKind;
333 static bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
334 static constexpr bool classof(Kind K) { return K == ClassKind; }
335};
336
337/// Represents a symbolic expression involving a unary operator.
338class UnarySymExpr : public SymExpr {
339 const SymExpr *Operand;
340 UnaryOperator::Opcode Op;
341 QualType T;
342
343 friend class SymExprAllocator;
344 UnarySymExpr(SymbolID Sym, const SymExpr *In, UnaryOperator::Opcode Op,
345 QualType T)
346 : SymExpr(ClassKind, Sym), Operand(In), Op(Op), T(T) {
347 // Note, some unary operators are modeled as a binary operator. E.g. ++x is
348 // modeled as x + 1.
349 assert((Op == UO_Minus || Op == UO_Not) && "non-supported unary expression");
350 // Unary expressions are results of arithmetic. Pointer arithmetic is not
351 // handled by unary expressions, but it is instead handled by applying
352 // sub-regions to regions.
353 assert(isValidTypeForSymbol(T) && "non-valid type for unary symbol");
354 assert(!Loc::isLocType(T) && "unary symbol should be nonloc");
355 }
356
357public:
358 unsigned computeComplexity() const override {
359 if (Complexity == 0)
360 Complexity = 1 + Operand->computeComplexity();
361 return Complexity;
362 }
363
364 const SymExpr *getOperand() const { return Operand; }
365 UnaryOperator::Opcode getOpcode() const { return Op; }
366 QualType getType() const override { return T; }
367
368 void dumpToStream(raw_ostream &os) const override;
369
370 static void Profile(llvm::FoldingSetNodeID &ID, const SymExpr *In,
371 UnaryOperator::Opcode Op, QualType T) {
372 ID.AddInteger(I: (unsigned)ClassKind);
373 ID.AddPointer(Ptr: In);
374 ID.AddInteger(I: Op);
375 ID.Add(x: T);
376 }
377
378 void Profile(llvm::FoldingSetNodeID &ID) override {
379 Profile(ID, In: Operand, Op, T);
380 }
381
382 // Implement isa<T> support.
383 static constexpr Kind ClassKind = UnarySymExprKind;
384 static bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
385 static constexpr bool classof(Kind K) { return K == ClassKind; }
386};
387
388/// Represents a symbolic expression involving a binary operator
389class BinarySymExpr : public SymExpr {
390 BinaryOperator::Opcode Op;
391 QualType T;
392
393protected:
394 BinarySymExpr(SymbolID Sym, Kind k, BinaryOperator::Opcode op, QualType t)
395 : SymExpr(k, Sym), Op(op), T(t) {
396 assert(classof(this));
397 // Binary expressions are results of arithmetic. Pointer arithmetic is not
398 // handled by binary expressions, but it is instead handled by applying
399 // sub-regions to regions.
400 assert(isValidTypeForSymbol(t) && !Loc::isLocType(t));
401 }
402
403public:
404 // FIXME: We probably need to make this out-of-line to avoid redundant
405 // generation of virtual functions.
406 QualType getType() const override { return T; }
407
408 BinaryOperator::Opcode getOpcode() const { return Op; }
409
410 // Implement isa<T> support.
411 static bool classof(const SymExpr *SE) { return classof(K: SE->getKind()); }
412 static constexpr bool classof(Kind K) {
413 return K >= BEGIN_BINARYSYMEXPRS && K <= END_BINARYSYMEXPRS;
414 }
415
416protected:
417 static unsigned computeOperandComplexity(const SymExpr *Value) {
418 return Value->computeComplexity();
419 }
420 static unsigned computeOperandComplexity(const llvm::APSInt &Value) {
421 return 1;
422 }
423
424 static const llvm::APSInt *getPointer(APSIntPtr Value) { return Value.get(); }
425 static const SymExpr *getPointer(const SymExpr *Value) { return Value; }
426
427 static void dumpToStreamImpl(raw_ostream &os, const SymExpr *Value);
428 static void dumpToStreamImpl(raw_ostream &os, const llvm::APSInt &Value);
429 static void dumpToStreamImpl(raw_ostream &os, BinaryOperator::Opcode op);
430};
431
432/// Template implementation for all binary symbolic expressions
433template <class LHSTYPE, class RHSTYPE, SymExpr::Kind ClassK>
434class BinarySymExprImpl : public BinarySymExpr {
435 LHSTYPE LHS;
436 RHSTYPE RHS;
437
438 friend class SymExprAllocator;
439 BinarySymExprImpl(SymbolID Sym, LHSTYPE lhs, BinaryOperator::Opcode op,
440 RHSTYPE rhs, QualType t)
441 : BinarySymExpr(Sym, ClassKind, op, t), LHS(lhs), RHS(rhs) {
442 assert(getPointer(lhs));
443 assert(getPointer(rhs));
444 }
445
446public:
447 void dumpToStream(raw_ostream &os) const override {
448 dumpToStreamImpl(os, LHS);
449 dumpToStreamImpl(os, getOpcode());
450 dumpToStreamImpl(os, RHS);
451 }
452
453 LHSTYPE getLHS() const { return LHS; }
454 RHSTYPE getRHS() const { return RHS; }
455
456 unsigned computeComplexity() const override {
457 if (Complexity == 0)
458 Complexity =
459 computeOperandComplexity(RHS) + computeOperandComplexity(LHS);
460 return Complexity;
461 }
462
463 static void Profile(llvm::FoldingSetNodeID &ID, LHSTYPE lhs,
464 BinaryOperator::Opcode op, RHSTYPE rhs, QualType t) {
465 ID.AddInteger(I: (unsigned)ClassKind);
466 ID.AddPointer(Ptr: getPointer(lhs));
467 ID.AddInteger(I: op);
468 ID.AddPointer(Ptr: getPointer(rhs));
469 ID.Add(x: t);
470 }
471
472 void Profile(llvm::FoldingSetNodeID &ID) override {
473 Profile(ID, LHS, getOpcode(), RHS, getType());
474 }
475
476 // Implement isa<T> support.
477 static constexpr Kind ClassKind = ClassK;
478 static bool classof(const SymExpr *SE) { return classof(SE->getKind()); }
479 static constexpr bool classof(Kind K) { return K == ClassKind; }
480};
481
482/// Represents a symbolic expression like 'x' + 3.
483using SymIntExpr = BinarySymExprImpl<const SymExpr *, APSIntPtr,
484 SymExpr::Kind::SymIntExprKind>;
485
486/// Represents a symbolic expression like 3 - 'x'.
487using IntSymExpr = BinarySymExprImpl<APSIntPtr, const SymExpr *,
488 SymExpr::Kind::IntSymExprKind>;
489
490/// Represents a symbolic expression like 'x' + 'y'.
491using SymSymExpr = BinarySymExprImpl<const SymExpr *, const SymExpr *,
492 SymExpr::Kind::SymSymExprKind>;
493
494class SymExprAllocator {
495 SymbolID NextSymbolID = 0;
496 llvm::BumpPtrAllocator &Alloc;
497
498public:
499 explicit SymExprAllocator(llvm::BumpPtrAllocator &Alloc) : Alloc(Alloc) {}
500
501 template <class SymT, typename... ArgsT> SymT *make(ArgsT &&...Args) {
502 return new (Alloc) SymT(nextID(), std::forward<ArgsT>(Args)...);
503 }
504
505private:
506 SymbolID nextID() { return NextSymbolID++; }
507};
508
509class SymbolManager {
510 using DataSetTy = llvm::FoldingSet<SymExpr>;
511 using SymbolDependTy =
512 llvm::DenseMap<SymbolRef, std::unique_ptr<SymbolRefSmallVectorTy>>;
513
514 DataSetTy DataSet;
515
516 /// Stores the extra dependencies between symbols: the data should be kept
517 /// alive as long as the key is live.
518 SymbolDependTy SymbolDependencies;
519
520 SymExprAllocator Alloc;
521 BasicValueFactory &BV;
522 ASTContext &Ctx;
523
524public:
525 SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
526 llvm::BumpPtrAllocator &bpalloc)
527 : SymbolDependencies(16), Alloc(bpalloc), BV(bv), Ctx(ctx) {}
528
529 static bool canSymbolicate(QualType T);
530
531 /// Create or retrieve a SymExpr of type \p SymExprT for the given arguments.
532 /// Use the arguments to check for an existing SymExpr and return it,
533 /// otherwise, create a new one and keep a pointer to it to avoid duplicates.
534 template <typename SymExprT, typename... Args>
535 const SymExprT *acquire(Args &&...args);
536
537 const SymbolConjured *conjureSymbol(ConstCFGElementRef Elem,
538 const LocationContext *LCtx, QualType T,
539 unsigned VisitCount,
540 const void *SymbolTag = nullptr) {
541
542 return acquire<SymbolConjured>(args&: Elem, args&: LCtx, args&: T, args&: VisitCount, args&: SymbolTag);
543 }
544
545 QualType getType(const SymExpr *SE) const {
546 return SE->getType();
547 }
548
549 /// Add artificial symbol dependency.
550 ///
551 /// The dependent symbol should stay alive as long as the primary is alive.
552 void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
553
554 const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
555
556 ASTContext &getContext() { return Ctx; }
557 BasicValueFactory &getBasicVals() { return BV; }
558};
559
560/// A class responsible for cleaning up unused symbols.
561class SymbolReaper {
562 enum SymbolStatus {
563 NotProcessed,
564 HaveMarkedDependents
565 };
566
567 using SymbolSetTy = llvm::DenseSet<SymbolRef>;
568 using SymbolMapTy = llvm::DenseMap<SymbolRef, SymbolStatus>;
569 using RegionSetTy = llvm::DenseSet<const MemRegion *>;
570
571 SymbolMapTy TheLiving;
572 SymbolSetTy MetadataInUse;
573
574 RegionSetTy LiveRegionRoots;
575 // The lazily copied regions are locations for which a program
576 // can access the value stored at that location, but not its address.
577 // These regions are constructed as a set of regions referred to by
578 // lazyCompoundVal.
579 RegionSetTy LazilyCopiedRegionRoots;
580
581 const StackFrameContext *LCtx;
582 const Stmt *Loc;
583 SymbolManager& SymMgr;
584 StoreRef reapedStore;
585 llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
586
587public:
588 /// Construct a reaper object, which removes everything which is not
589 /// live before we execute statement s in the given location context.
590 ///
591 /// If the statement is NULL, everything is this and parent contexts is
592 /// considered live.
593 /// If the stack frame context is NULL, everything on stack is considered
594 /// dead.
595 SymbolReaper(const StackFrameContext *Ctx, const Stmt *s,
596 SymbolManager &symmgr, StoreManager &storeMgr)
597 : LCtx(Ctx), Loc(s), SymMgr(symmgr), reapedStore(nullptr, storeMgr) {}
598
599 /// It might return null.
600 const LocationContext *getLocationContext() const { return LCtx; }
601
602 bool isLive(SymbolRef sym);
603 bool isLiveRegion(const MemRegion *region);
604 bool isLive(const Expr *ExprVal, const LocationContext *LCtx) const;
605 bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
606
607 /// Unconditionally marks a symbol as live.
608 ///
609 /// This should never be
610 /// used by checkers, only by the state infrastructure such as the store and
611 /// environment. Checkers should instead use metadata symbols and markInUse.
612 void markLive(SymbolRef sym);
613
614 /// Marks a symbol as important to a checker.
615 ///
616 /// For metadata symbols,
617 /// this will keep the symbol alive as long as its associated region is also
618 /// live. For other symbols, this has no effect; checkers are not permitted
619 /// to influence the life of other symbols. This should be used before any
620 /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
621 void markInUse(SymbolRef sym);
622
623 llvm::iterator_range<RegionSetTy::const_iterator> regions() const {
624 return LiveRegionRoots;
625 }
626
627 /// Returns whether or not a symbol has been confirmed dead.
628 ///
629 /// This should only be called once all marking of dead symbols has completed.
630 /// (For checkers, this means only in the checkDeadSymbols callback.)
631 bool isDead(SymbolRef sym) {
632 return !isLive(sym);
633 }
634
635 void markLive(const MemRegion *region);
636 void markLazilyCopied(const MemRegion *region);
637 void markElementIndicesLive(const MemRegion *region);
638
639 /// Set to the value of the symbolic store after
640 /// StoreManager::removeDeadBindings has been called.
641 void setReapedStore(StoreRef st) { reapedStore = st; }
642
643private:
644 bool isLazilyCopiedRegion(const MemRegion *region) const;
645 // A readable region is a region that live or lazily copied.
646 // Any symbols that refer to values in regions are alive if the region
647 // is readable.
648 bool isReadableRegion(const MemRegion *region);
649
650 /// Mark the symbols dependent on the input symbol as live.
651 void markDependentsLive(SymbolRef sym);
652};
653
654class SymbolVisitor {
655protected:
656 ~SymbolVisitor() = default;
657
658public:
659 SymbolVisitor() = default;
660 SymbolVisitor(const SymbolVisitor &) = default;
661 SymbolVisitor(SymbolVisitor &&) {}
662
663 // The copy and move assignment operator is defined as deleted pending further
664 // motivation.
665 SymbolVisitor &operator=(const SymbolVisitor &) = delete;
666 SymbolVisitor &operator=(SymbolVisitor &&) = delete;
667
668 /// A visitor method invoked by ProgramStateManager::scanReachableSymbols.
669 ///
670 /// The method returns \c true if symbols should continue be scanned and \c
671 /// false otherwise.
672 virtual bool VisitSymbol(SymbolRef sym) = 0;
673 virtual bool VisitMemRegion(const MemRegion *) { return true; }
674};
675
676template <typename T, typename... Args>
677const T *SymbolManager::acquire(Args &&...args) {
678 llvm::FoldingSetNodeID profile;
679 T::Profile(profile, args...);
680 void *InsertPos;
681 SymExpr *SD = DataSet.FindNodeOrInsertPos(ID: profile, InsertPos);
682 if (!SD) {
683 SD = Alloc.make<T>(std::forward<Args>(args)...);
684 DataSet.InsertNode(N: SD, InsertPos);
685 }
686 return cast<T>(SD);
687}
688
689} // namespace ento
690
691} // namespace clang
692
693// Override the default definition that would use pointer values of SymbolRefs
694// to order them, which is unstable due to ASLR.
695// Use the SymbolID instead which reflect the order in which the symbols were
696// allocated. This is usually stable across runs leading to the stability of
697// ConstraintMap and other containers using SymbolRef as keys.
698template <>
699struct llvm::ImutContainerInfo<clang::ento::SymbolRef>
700 : public ImutProfileInfo<clang::ento::SymbolRef> {
701 using value_type = clang::ento::SymbolRef;
702 using value_type_ref = clang::ento::SymbolRef;
703 using key_type = value_type;
704 using key_type_ref = value_type_ref;
705 using data_type = bool;
706 using data_type_ref = bool;
707
708 static key_type_ref KeyOfValue(value_type_ref D) { return D; }
709 static data_type_ref DataOfValue(value_type_ref) { return true; }
710
711 static bool isEqual(clang::ento::SymbolRef LHS, clang::ento::SymbolRef RHS) {
712 return LHS->getSymbolID() == RHS->getSymbolID();
713 }
714
715 static bool isLess(clang::ento::SymbolRef LHS, clang::ento::SymbolRef RHS) {
716 return LHS->getSymbolID() < RHS->getSymbolID();
717 }
718
719 // This might seem redundant, but it is required because of the way
720 // ImmutableSet is implemented through AVLTree:
721 // same as ImmutableMap, but with a non-informative "data".
722 static bool isDataEqual(data_type_ref, data_type_ref) { return true; }
723};
724
725#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
726

source code of clang/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h