1 files changed, 650 insertions, 0 deletions
diff --git a/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h b/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
new file mode 100644
index 00000000..d212e23d
--- /dev/null
+++ b/clang-r353983/include/clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h
@@ -0,0 +1,650 @@
+//===- SymbolManager.h - Management of Symbolic Values ----------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines SymbolManager, a class that manages symbolic values
+//  created for use by ExprEngine and related classes.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
+#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H
+
+#include "clang/AST/Expr.h"
+#include "clang/AST/Type.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/StoreRef.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/Support/Allocator.h"
+#include <cassert>
+
+namespace clang {
+
+class ASTContext;
+class Stmt;
+
+namespace ento {
+
+class BasicValueFactory;
+class StoreManager;
+
+///A symbol representing the value stored at a MemRegion.
+class SymbolRegionValue : public SymbolData {
+  const TypedValueRegion *R;
+
+public:
+  SymbolRegionValue(SymbolID sym, const TypedValueRegion *r)
+      : SymbolData(SymbolRegionValueKind, sym), R(r) {
+    assert(r);
+    assert(isValidTypeForSymbol(r->getValueType()));
+  }
+
+  const TypedValueRegion* getRegion() const { return R; }
+
+  static void Profile(llvm::FoldingSetNodeID& profile, const TypedValueRegion* R) {
+    profile.AddInteger((unsigned) SymbolRegionValueKind);
+    profile.AddPointer(R);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& profile) override {
+    Profile(profile, R);
+  }
+
+  void dumpToStream(raw_ostream &os) const override;
+  const MemRegion *getOriginRegion() const override { return getRegion(); }
+
+  QualType getType() const override;
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == SymbolRegionValueKind;
+  }
+};
+
+/// A symbol representing the result of an expression in the case when we do
+/// not know anything about what the expression is.
+class SymbolConjured : public SymbolData {
+  const Stmt *S;
+  QualType T;
+  unsigned Count;
+  const LocationContext *LCtx;
+  const void *SymbolTag;
+
+public:
+  SymbolConjured(SymbolID sym, const Stmt *s, const LocationContext *lctx,
+                 QualType t, unsigned count, const void *symbolTag)
+      : SymbolData(SymbolConjuredKind, sym), S(s), T(t), Count(count),
+        LCtx(lctx), SymbolTag(symbolTag) {
+    // FIXME: 's' might be a nullptr if we're conducting invalidation
+    // that was caused by a destructor call on a temporary object,
+    // which has no statement associated with it.
+    // Due to this, we might be creating the same invalidation symbol for
+    // two different invalidation passes (for two different temporaries).
+    assert(lctx);
+    assert(isValidTypeForSymbol(t));
+  }
+
+  const Stmt *getStmt() const { return S; }
+  unsigned getCount() const { return Count; }
+  const void *getTag() const { return SymbolTag; }
+
+  QualType getType() const override;
+
+  void dumpToStream(raw_ostream &os) const override;
+
+  static void Profile(llvm::FoldingSetNodeID& profile, const Stmt *S,
+                      QualType T, unsigned Count, const LocationContext *LCtx,
+                      const void *SymbolTag) {
+    profile.AddInteger((unsigned) SymbolConjuredKind);
+    profile.AddPointer(S);
+    profile.AddPointer(LCtx);
+    profile.Add(T);
+    profile.AddInteger(Count);
+    profile.AddPointer(SymbolTag);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& profile) override {
+    Profile(profile, S, T, Count, LCtx, SymbolTag);
+  }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == SymbolConjuredKind;
+  }
+};
+
+/// A symbol representing the value of a MemRegion whose parent region has
+/// symbolic value.
+class SymbolDerived : public SymbolData {
+  SymbolRef parentSymbol;
+  const TypedValueRegion *R;
+
+public:
+  SymbolDerived(SymbolID sym, SymbolRef parent, const TypedValueRegion *r)
+      : SymbolData(SymbolDerivedKind, sym), parentSymbol(parent), R(r) {
+    assert(parent);
+    assert(r);
+    assert(isValidTypeForSymbol(r->getValueType()));
+  }
+
+  SymbolRef getParentSymbol() const { return parentSymbol; }
+  const TypedValueRegion *getRegion() const { return R; }
+
+  QualType getType() const override;
+
+  void dumpToStream(raw_ostream &os) const override;
+  const MemRegion *getOriginRegion() const override { return getRegion(); }
+
+  static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
+                      const TypedValueRegion *r) {
+    profile.AddInteger((unsigned) SymbolDerivedKind);
+    profile.AddPointer(r);
+    profile.AddPointer(parent);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& profile) override {
+    Profile(profile, parentSymbol, R);
+  }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == SymbolDerivedKind;
+  }
+};
+
+/// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
+///  Clients should not ask the SymbolManager for a region's extent. Always use
+///  SubRegion::getExtent instead -- the value returned may not be a symbol.
+class SymbolExtent : public SymbolData {
+  const SubRegion *R;
+
+public:
+  SymbolExtent(SymbolID sym, const SubRegion *r)
+      : SymbolData(SymbolExtentKind, sym), R(r) {
+    assert(r);
+  }
+
+  const SubRegion *getRegion() const { return R; }
+
+  QualType getType() const override;
+
+  void dumpToStream(raw_ostream &os) const override;
+
+  static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
+    profile.AddInteger((unsigned) SymbolExtentKind);
+    profile.AddPointer(R);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& profile) override {
+    Profile(profile, R);
+  }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == SymbolExtentKind;
+  }
+};
+
+/// SymbolMetadata - Represents path-dependent metadata about a specific region.
+///  Metadata symbols remain live as long as they are marked as in use before
+///  dead-symbol sweeping AND their associated regions are still alive.
+///  Intended for use by checkers.
+class SymbolMetadata : public SymbolData {
+  const MemRegion* R;
+  const Stmt *S;
+  QualType T;
+  const LocationContext *LCtx;
+  unsigned Count;
+  const void *Tag;
+
+public:
+  SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt *s, QualType t,
+                 const LocationContext *LCtx, unsigned count, const void *tag)
+      : SymbolData(SymbolMetadataKind, sym), R(r), S(s), T(t), LCtx(LCtx),
+        Count(count), Tag(tag) {
+      assert(r);
+      assert(s);
+      assert(isValidTypeForSymbol(t));
+      assert(LCtx);
+      assert(tag);
+    }
+
+  const MemRegion *getRegion() const { return R; }
+  const Stmt *getStmt() const { return S; }
+  const LocationContext *getLocationContext() const { return LCtx; }
+  unsigned getCount() const { return Count; }
+  const void *getTag() const { return Tag; }
+
+  QualType getType() const override;
+
+  void dumpToStream(raw_ostream &os) const override;
+
+  static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
+                      const Stmt *S, QualType T, const LocationContext *LCtx,
+                      unsigned Count, const void *Tag) {
+    profile.AddInteger((unsigned) SymbolMetadataKind);
+    profile.AddPointer(R);
+    profile.AddPointer(S);
+    profile.Add(T);
+    profile.AddPointer(LCtx);
+    profile.AddInteger(Count);
+    profile.AddPointer(Tag);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& profile) override {
+    Profile(profile, R, S, T, LCtx, Count, Tag);
+  }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == SymbolMetadataKind;
+  }
+};
+
+/// Represents a cast expression.
+class SymbolCast : public SymExpr {
+  const SymExpr *Operand;
+
+  /// Type of the operand.
+  QualType FromTy;
+
+  /// The type of the result.
+  QualType ToTy;
+
+public:
+  SymbolCast(const SymExpr *In, QualType From, QualType To)
+      : SymExpr(SymbolCastKind), Operand(In), FromTy(From), ToTy(To) {
+    assert(In);
+    assert(isValidTypeForSymbol(From));
+    // FIXME: GenericTaintChecker creates symbols of void type.
+    // Otherwise, 'To' should also be a valid type.
+  }
+
+  unsigned computeComplexity() const override {
+    if (Complexity == 0)
+      Complexity = 1 + Operand->computeComplexity();
+    return Complexity;
+  }
+
+  QualType getType() const override { return ToTy; }
+
+  const SymExpr *getOperand() const { return Operand; }
+
+  void dumpToStream(raw_ostream &os) const override;
+
+  static void Profile(llvm::FoldingSetNodeID& ID,
+                      const SymExpr *In, QualType From, QualType To) {
+    ID.AddInteger((unsigned) SymbolCastKind);
+    ID.AddPointer(In);
+    ID.Add(From);
+    ID.Add(To);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& ID) override {
+    Profile(ID, Operand, FromTy, ToTy);
+  }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == SymbolCastKind;
+  }
+};
+
+/// Represents a symbolic expression involving a binary operator
+class BinarySymExpr : public SymExpr {
+  BinaryOperator::Opcode Op;
+  QualType T;
+
+protected:
+  BinarySymExpr(Kind k, BinaryOperator::Opcode op, QualType t)
+      : SymExpr(k), Op(op), T(t) {
+    assert(classof(this));
+    // Binary expressions are results of arithmetic. Pointer arithmetic is not
+    // handled by binary expressions, but it is instead handled by applying
+    // sub-regions to regions.
+    assert(isValidTypeForSymbol(t) && !Loc::isLocType(t));
+  }
+
+public:
+  // FIXME: We probably need to make this out-of-line to avoid redundant
+  // generation of virtual functions.
+  QualType getType() const override { return T; }
+
+  BinaryOperator::Opcode getOpcode() const { return Op; }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    Kind k = SE->getKind();
+    return k >= BEGIN_BINARYSYMEXPRS && k <= END_BINARYSYMEXPRS;
+  }
+};
+
+/// Represents a symbolic expression like 'x' + 3.
+class SymIntExpr : public BinarySymExpr {
+  const SymExpr *LHS;
+  const llvm::APSInt& RHS;
+
+public:
+  SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
+             const llvm::APSInt &rhs, QualType t)
+      : BinarySymExpr(SymIntExprKind, op, t), LHS(lhs), RHS(rhs) {
+    assert(lhs);
+  }
+
+  void dumpToStream(raw_ostream &os) const override;
+
+  const SymExpr *getLHS() const { return LHS; }
+  const llvm::APSInt &getRHS() const { return RHS; }
+
+  unsigned computeComplexity() const override {
+    if (Complexity == 0)
+      Complexity = 1 + LHS->computeComplexity();
+    return Complexity;
+  }
+
+  static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
+                      BinaryOperator::Opcode op, const llvm::APSInt& rhs,
+                      QualType t) {
+    ID.AddInteger((unsigned) SymIntExprKind);
+    ID.AddPointer(lhs);
+    ID.AddInteger(op);
+    ID.AddPointer(&rhs);
+    ID.Add(t);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& ID) override {
+    Profile(ID, LHS, getOpcode(), RHS, getType());
+  }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == SymIntExprKind;
+  }
+};
+
+/// Represents a symbolic expression like 3 - 'x'.
+class IntSymExpr : public BinarySymExpr {
+  const llvm::APSInt& LHS;
+  const SymExpr *RHS;
+
+public:
+  IntSymExpr(const llvm::APSInt &lhs, BinaryOperator::Opcode op,
+             const SymExpr *rhs, QualType t)
+      : BinarySymExpr(IntSymExprKind, op, t), LHS(lhs), RHS(rhs) {
+    assert(rhs);
+  }
+
+  void dumpToStream(raw_ostream &os) const override;
+
+  const SymExpr *getRHS() const { return RHS; }
+  const llvm::APSInt &getLHS() const { return LHS; }
+
+  unsigned computeComplexity() const override {
+    if (Complexity == 0)
+      Complexity = 1 + RHS->computeComplexity();
+    return Complexity;
+  }
+
+  static void Profile(llvm::FoldingSetNodeID& ID, const llvm::APSInt& lhs,
+                      BinaryOperator::Opcode op, const SymExpr *rhs,
+                      QualType t) {
+    ID.AddInteger((unsigned) IntSymExprKind);
+    ID.AddPointer(&lhs);
+    ID.AddInteger(op);
+    ID.AddPointer(rhs);
+    ID.Add(t);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& ID) override {
+    Profile(ID, LHS, getOpcode(), RHS, getType());
+  }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == IntSymExprKind;
+  }
+};
+
+/// Represents a symbolic expression like 'x' + 'y'.
+class SymSymExpr : public BinarySymExpr {
+  const SymExpr *LHS;
+  const SymExpr *RHS;
+
+public:
+  SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
+             QualType t)
+      : BinarySymExpr(SymSymExprKind, op, t), LHS(lhs), RHS(rhs) {
+    assert(lhs);
+    assert(rhs);
+  }
+
+  const SymExpr *getLHS() const { return LHS; }
+  const SymExpr *getRHS() const { return RHS; }
+
+  void dumpToStream(raw_ostream &os) const override;
+
+  unsigned computeComplexity() const override {
+    if (Complexity == 0)
+      Complexity = RHS->computeComplexity() + LHS->computeComplexity();
+    return Complexity;
+  }
+
+  static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
+                    BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
+    ID.AddInteger((unsigned) SymSymExprKind);
+    ID.AddPointer(lhs);
+    ID.AddInteger(op);
+    ID.AddPointer(rhs);
+    ID.Add(t);
+  }
+
+  void Profile(llvm::FoldingSetNodeID& ID) override {
+    Profile(ID, LHS, getOpcode(), RHS, getType());
+  }
+
+  // Implement isa<T> support.
+  static bool classof(const SymExpr *SE) {
+    return SE->getKind() == SymSymExprKind;
+  }
+};
+
+class SymbolManager {
+  using DataSetTy = llvm::FoldingSet<SymExpr>;
+  using SymbolDependTy = llvm::DenseMap<SymbolRef, SymbolRefSmallVectorTy *>;
+
+  DataSetTy DataSet;
+
+  /// Stores the extra dependencies between symbols: the data should be kept
+  /// alive as long as the key is live.
+  SymbolDependTy SymbolDependencies;
+
+  unsigned SymbolCounter = 0;
+  llvm::BumpPtrAllocator& BPAlloc;
+  BasicValueFactory &BV;
+  ASTContext &Ctx;
+
+public:
+  SymbolManager(ASTContext &ctx, BasicValueFactory &bv,
+                llvm::BumpPtrAllocator& bpalloc)
+      : SymbolDependencies(16), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
+  ~SymbolManager();
+
+  static bool canSymbolicate(QualType T);
+
+  /// Make a unique symbol for MemRegion R according to its kind.
+  const SymbolRegionValue* getRegionValueSymbol(const TypedValueRegion* R);
+
+  const SymbolConjured* conjureSymbol(const Stmt *E,
+                                      const LocationContext *LCtx,
+                                      QualType T,
+                                      unsigned VisitCount,
+                                      const void *SymbolTag = nullptr);
+
+  const SymbolConjured* conjureSymbol(const Expr *E,
+                                      const LocationContext *LCtx,
+                                      unsigned VisitCount,
+                                      const void *SymbolTag = nullptr) {
+    return conjureSymbol(E, LCtx, E->getType(), VisitCount, SymbolTag);
+  }
+
+  const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
+                                        const TypedValueRegion *R);
+
+  const SymbolExtent *getExtentSymbol(const SubRegion *R);
+
+  /// Creates a metadata symbol associated with a specific region.
+  ///
+  /// VisitCount can be used to differentiate regions corresponding to
+  /// different loop iterations, thus, making the symbol path-dependent.
+  const SymbolMetadata *getMetadataSymbol(const MemRegion *R, const Stmt *S,
+                                          QualType T,
+                                          const LocationContext *LCtx,
+                                          unsigned VisitCount,
+                                          const void *SymbolTag = nullptr);
+
+  const SymbolCast* getCastSymbol(const SymExpr *Operand,
+                                  QualType From, QualType To);
+
+  const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
+                                  const llvm::APSInt& rhs, QualType t);
+
+  const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
+                                  const llvm::APSInt& rhs, QualType t) {
+    return getSymIntExpr(&lhs, op, rhs, t);
+  }
+
+  const IntSymExpr *getIntSymExpr(const llvm::APSInt& lhs,
+                                  BinaryOperator::Opcode op,
+                                  const SymExpr *rhs, QualType t);
+
+  const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
+                                  const SymExpr *rhs, QualType t);
+
+  QualType getType(const SymExpr *SE) const {
+    return SE->getType();
+  }
+
+  /// Add artificial symbol dependency.
+  ///
+  /// The dependent symbol should stay alive as long as the primary is alive.
+  void addSymbolDependency(const SymbolRef Primary, const SymbolRef Dependent);
+
+  const SymbolRefSmallVectorTy *getDependentSymbols(const SymbolRef Primary);
+
+  ASTContext &getContext() { return Ctx; }
+  BasicValueFactory &getBasicVals() { return BV; }
+};
+
+/// A class responsible for cleaning up unused symbols.
+class SymbolReaper {
+  enum SymbolStatus {
+    NotProcessed,
+    HaveMarkedDependents
+  };
+
+  using SymbolSetTy = llvm::DenseSet<SymbolRef>;
+  using SymbolMapTy = llvm::DenseMap<SymbolRef, SymbolStatus>;
+  using RegionSetTy = llvm::DenseSet<const MemRegion *>;
+
+  SymbolMapTy TheLiving;
+  SymbolSetTy MetadataInUse;
+
+  RegionSetTy RegionRoots;
+
+  const StackFrameContext *LCtx;
+  const Stmt *Loc;
+  SymbolManager& SymMgr;
+  StoreRef reapedStore;
+  llvm::DenseMap<const MemRegion *, unsigned> includedRegionCache;
+
+public:
+  /// Construct a reaper object, which removes everything which is not
+  /// live before we execute statement s in the given location context.
+  ///
+  /// If the statement is NULL, everything is this and parent contexts is
+  /// considered live.
+  /// If the stack frame context is NULL, everything on stack is considered
+  /// dead.
+  SymbolReaper(const StackFrameContext *Ctx, const Stmt *s,
+               SymbolManager &symmgr, StoreManager &storeMgr)
+      : LCtx(Ctx), Loc(s), SymMgr(symmgr), reapedStore(nullptr, storeMgr) {}
+
+  const LocationContext *getLocationContext() const { return LCtx; }
+
+  bool isLive(SymbolRef sym);
+  bool isLiveRegion(const MemRegion *region);
+  bool isLive(const Stmt *ExprVal, const LocationContext *LCtx) const;
+  bool isLive(const VarRegion *VR, bool includeStoreBindings = false) const;
+
+  /// Unconditionally marks a symbol as live.
+  ///
+  /// This should never be
+  /// used by checkers, only by the state infrastructure such as the store and
+  /// environment. Checkers should instead use metadata symbols and markInUse.
+  void markLive(SymbolRef sym);
+
+  /// Marks a symbol as important to a checker.
+  ///
+  /// For metadata symbols,
+  /// this will keep the symbol alive as long as its associated region is also
+  /// live. For other symbols, this has no effect; checkers are not permitted
+  /// to influence the life of other symbols. This should be used before any
+  /// symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
+  void markInUse(SymbolRef sym);
+
+  using region_iterator = RegionSetTy::const_iterator;
+
+  region_iterator region_begin() const { return RegionRoots.begin(); }
+  region_iterator region_end() const { return RegionRoots.end(); }
+
+  /// Returns whether or not a symbol has been confirmed dead.
+  ///
+  /// This should only be called once all marking of dead symbols has completed.
+  /// (For checkers, this means only in the checkDeadSymbols callback.)
+  bool isDead(SymbolRef sym) {
+    return !isLive(sym);
+  }
+
+  void markLive(const MemRegion *region);
+  void markElementIndicesLive(const MemRegion *region);
+
+  /// Set to the value of the symbolic store after
+  /// StoreManager::removeDeadBindings has been called.
+  void setReapedStore(StoreRef st) { reapedStore = st; }
+
+private:
+  /// Mark the symbols dependent on the input symbol as live.
+  void markDependentsLive(SymbolRef sym);
+};
+
+class SymbolVisitor {
+protected:
+  ~SymbolVisitor() = default;
+
+public:
+  SymbolVisitor() = default;
+  SymbolVisitor(const SymbolVisitor &) = default;
+  SymbolVisitor(SymbolVisitor &&) {}
+
+  /// A visitor method invoked by ProgramStateManager::scanReachableSymbols.
+  ///
+  /// The method returns \c true if symbols should continue be scanned and \c
+  /// false otherwise.
+  virtual bool VisitSymbol(SymbolRef sym) = 0;
+  virtual bool VisitMemRegion(const MemRegion *) { return true; }
+};
+
+} // namespace ento
+
+} // namespace clang
+
+#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMBOLMANAGER_H