Home | History | Annotate | Line # | Download | only in PathSensitive 
      1 //===- SymExpr.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 SymExpr and SymbolData.
     10 //
     11 //===----------------------------------------------------------------------===//
     12 
     13 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
     14 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
     15 
     16 #include "clang/AST/Type.h"
     17 #include "clang/Basic/LLVM.h"
     18 #include "llvm/ADT/FoldingSet.h"
     19 #include "llvm/ADT/SmallVector.h"
     20 #include <cassert>
     21 
     22 namespace clang {
     23 namespace ento {
     24 
     25 class MemRegion;
     26 
     27 /// 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   mutable unsigned Complexity = 0;
     52 
     53 public:
     54   virtual ~SymExpr() = default;
     55 
     56   Kind getKind() const { return K; }
     57 
     58   virtual void dump() const;
     59 
     60   virtual void dumpToStream(raw_ostream &os) const {}
     61 
     62   virtual QualType getType() const = 0;
     63   virtual void Profile(llvm::FoldingSetNodeID &profile) = 0;
     64 
     65   /// Iterator over symbols that the current symbol depends on.
     66   ///
     67   /// For SymbolData, it's the symbol itself; for expressions, it's the
     68   /// expression symbol and all the operands in it. Note, SymbolDerived is
     69   /// treated as SymbolData - the iterator will NOT visit the parent region.
     70   class symbol_iterator {
     71     SmallVector<const SymExpr *, 5> itr;
     72 
     73     void expand();
     74 
     75   public:
     76     symbol_iterator() = default;
     77     symbol_iterator(const SymExpr *SE);
     78 
     79     symbol_iterator &operator++();
     80     const SymExpr *operator*();
     81 
     82     bool operator==(const symbol_iterator &X) const;
     83     bool operator!=(const symbol_iterator &X) const;
     84   };
     85 
     86   symbol_iterator symbol_begin() const { return symbol_iterator(this); }
     87   static symbol_iterator symbol_end() { return symbol_iterator(); }
     88 
     89   virtual unsigned computeComplexity() const = 0;
     90 
     91   /// Find the region from which this symbol originates.
     92   ///
     93   /// Whenever the symbol was constructed to denote an unknown value of
     94   /// a certain memory region, return this region. This method
     95   /// allows checkers to make decisions depending on the origin of the symbol.
     96   /// Symbol classes for which the origin region is known include
     97   /// SymbolRegionValue which denotes the value of the region before
     98   /// the beginning of the analysis, and SymbolDerived which denotes the value
     99   /// of a certain memory region after its super region (a memory space or
    100   /// a larger record region) is default-bound with a certain symbol.
    101   virtual const MemRegion *getOriginRegion() const { return nullptr; }
    102 };
    103 
    104 inline raw_ostream &operator<<(raw_ostream &os,
    105                                const clang::ento::SymExpr *SE) {
    106   SE->dumpToStream(os);
    107   return os;
    108 }
    109 
    110 using SymbolRef = const SymExpr *;
    111 using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>;
    112 using SymbolID = unsigned;
    113 
    114 /// A symbol representing data which can be stored in a memory location
    115 /// (region).
    116 class SymbolData : public SymExpr {
    117   const SymbolID Sym;
    118 
    119   void anchor() override;
    120 
    121 protected:
    122   SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {
    123     assert(classof(this));
    124   }
    125 
    126 public:
    127   ~SymbolData() override = default;
    128 
    129   /// Get a string representation of the kind of the region.
    130   virtual StringRef getKindStr() const = 0;
    131 
    132   SymbolID getSymbolID() const { return Sym; }
    133 
    134   unsigned computeComplexity() const override {
    135     return 1;
    136   };
    137 
    138   // Implement isa<T> support.
    139   static inline bool classof(const SymExpr *SE) {
    140     Kind k = SE->getKind();
    141     return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
    142   }
    143 };
    144 
    145 } // namespace ento
    146 } // namespace clang
    147 
    148 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
    149