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