include/clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h

   1 //===- SymExpr.h - Management of Symbolic Values ----------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 //  This file defines SymExpr and SymbolData.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
  15 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
  16
  17 #include "clang/AST/Type.h"
  18 #include "clang/Basic/LLVM.h"
  19 #include "llvm/ADT/FoldingSet.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include <cassert>
  22
  23 namespace clang {
  24 namespace ento {
  25
  26 class MemRegion;
  27
  28 /// Symbolic value. These values used to capture symbolic execution of
  29 /// the program.
  30 class SymExpr : public llvm::FoldingSetNode {
  31   virtual void anchor();
  32
  33 public:
  34   enum Kind {
  35 #define SYMBOL(Id, Parent) Id##Kind,
  36 #define SYMBOL_RANGE(Id, First, Last) BEGIN_##Id = First, END_##Id = Last,
  37 #include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
  38   };
  39
  40 private:
  41   Kind K;
  42
  43 protected:
  44   SymExpr(Kind k) : K(k) {}
  45
  46   static bool isValidTypeForSymbol(QualType T) {
  47     // FIXME: Depending on whether we choose to deprecate structural symbols,
  48     // this may become much stricter.
  49     return !T.isNull() && !T->isVoidType();
  50   }
  51
  52   mutable unsigned Complexity = 0;
  53
  54 public:
  55   virtual ~SymExpr() = default;
  56
  57   Kind getKind() const { return K; }
  58
  59   virtual void dump() const;
  60
  61   virtual void dumpToStream(raw_ostream &os) const {}
  62
  63   virtual QualType getType() const = 0;
  64   virtual void Profile(llvm::FoldingSetNodeID &profile) = 0;
  65
  66   /// Iterator over symbols that the current symbol depends on.
  67   ///
  68   /// For SymbolData, it's the symbol itself; for expressions, it's the
  69   /// expression symbol and all the operands in it. Note, SymbolDerived is
  70   /// treated as SymbolData - the iterator will NOT visit the parent region.
  71   class symbol_iterator {
  72     SmallVector<const SymExpr *, 5> itr;
  73
  74     void expand();
  75
  76   public:
  77     symbol_iterator() = default;
  78     symbol_iterator(const SymExpr *SE);
  79
  80     symbol_iterator &operator++();
  81     const SymExpr *operator*();
  82
  83     bool operator==(const symbol_iterator &X) const;
  84     bool operator!=(const symbol_iterator &X) const;
  85   };
  86
  87   symbol_iterator symbol_begin() const { return symbol_iterator(this); }
  88   static symbol_iterator symbol_end() { return symbol_iterator(); }
  89
  90   virtual unsigned computeComplexity() const = 0;
  91
  92   /// Find the region from which this symbol originates.
  93   ///
  94   /// Whenever the symbol was constructed to denote an unknown value of
  95   /// a certain memory region, return this region. This method
  96   /// allows checkers to make decisions depending on the origin of the symbol.
  97   /// Symbol classes for which the origin region is known include
  98   /// SymbolRegionValue which denotes the value of the region before
  99   /// the beginning of the analysis, and SymbolDerived which denotes the value
 100   /// of a certain memory region after its super region (a memory space or
 101   /// a larger record region) is default-bound with a certain symbol.
 102   virtual const MemRegion *getOriginRegion() const { return nullptr; }
 103 };
 104
 105 inline raw_ostream &operator<<(raw_ostream &os,
 106                                const clang::ento::SymExpr *SE) {
 107   SE->dumpToStream(os);
 108   return os;
 109 }
 110
 111 using SymbolRef = const SymExpr *;
 112 using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>;
 113 using SymbolID = unsigned;
 114
 115 /// A symbol representing data which can be stored in a memory location
 116 /// (region).
 117 class SymbolData : public SymExpr {
 118   const SymbolID Sym;
 119
 120   void anchor() override;
 121
 122 protected:
 123   SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {
 124     assert(classof(this));
 125   }
 126
 127 public:
 128   ~SymbolData() override = default;
 129
 130   SymbolID getSymbolID() const { return Sym; }
 131
 132   unsigned computeComplexity() const override {
 133     return 1;
 134   };
 135
 136   // Implement isa<T> support.
 137   static inline bool classof(const SymExpr *SE) {
 138     Kind k = SE->getKind();
 139     return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
 140   }
 141 };
 142
 143 } // namespace ento
 144 } // namespace clang
 145
 146 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H