Core/PathSensitive/SymExpr.h

0001 //===- SymExpr.h - Management of Symbolic Values ----------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 //  This file defines SymExpr and SymbolData.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
0014 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H
0015
0016 #include "clang/AST/Type.h"
0017 #include "clang/Basic/LLVM.h"
0018 #include "llvm/ADT/FoldingSet.h"
0019 #include "llvm/ADT/SmallVector.h"
0020 #include "llvm/ADT/iterator_range.h"
0021 #include <cassert>
0022
0023 namespace clang {
0024 namespace ento {
0025
0026 class MemRegion;
0027
0028 using SymbolID = unsigned;
0029
0030 /// Symbolic value. These values used to capture symbolic execution of
0031 /// the program.
0032 class SymExpr : public llvm::FoldingSetNode {
0033   virtual void anchor();
0034
0035 public:
0036   enum Kind {
0037 #define SYMBOL(Id, Parent) Id##Kind,
0038 #define SYMBOL_RANGE(Id, First, Last) BEGIN_##Id = First, END_##Id = Last,
0039 #include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def"
0040   };
0041
0042 private:
0043   Kind K;
0044   /// A unique identifier for this symbol.
0045   ///
0046   /// It is useful for SymbolData to easily differentiate multiple symbols, but
0047   /// also for "ephemeral" symbols, such as binary operations, because this id
0048   /// can be used for arranging constraints or equivalence classes instead of
0049   /// unstable pointer values.
0050   ///
0051   /// Note, however, that it can't be used in Profile because SymbolManager
0052   /// needs to compute Profile before allocating SymExpr.
0053   const SymbolID Sym;
0054
0055 protected:
0056   SymExpr(Kind k, SymbolID Sym) : K(k), Sym(Sym) {}
0057
0058   static bool isValidTypeForSymbol(QualType T) {
0059     // FIXME: Depending on whether we choose to deprecate structural symbols,
0060     // this may become much stricter.
0061     return !T.isNull() && !T->isVoidType();
0062   }
0063
0064   mutable unsigned Complexity = 0;
0065
0066 public:
0067   virtual ~SymExpr() = default;
0068
0069   Kind getKind() const { return K; }
0070
0071   /// Get a unique identifier for this symbol.
0072   /// The ID is unique across all SymExprs in a SymbolManager.
0073   /// They reflect the allocation order of these SymExprs,
0074   /// and are likely stable across runs.
0075   /// Used as a key in SymbolRef containers and as part of identity
0076   /// for SymbolData, e.g. SymbolConjured with ID = 7 is "conj_$7".
0077   SymbolID getSymbolID() const { return Sym; }
0078
0079   virtual void dump() const;
0080
0081   virtual void dumpToStream(raw_ostream &os) const {}
0082
0083   virtual QualType getType() const = 0;
0084   virtual void Profile(llvm::FoldingSetNodeID &profile) = 0;
0085
0086   /// Iterator over symbols that the current symbol depends on.
0087   ///
0088   /// For SymbolData, it's the symbol itself; for expressions, it's the
0089   /// expression symbol and all the operands in it. Note, SymbolDerived is
0090   /// treated as SymbolData - the iterator will NOT visit the parent region.
0091   class symbol_iterator {
0092     SmallVector<const SymExpr *, 5> itr;
0093
0094     void expand();
0095
0096   public:
0097     symbol_iterator() = default;
0098     symbol_iterator(const SymExpr *SE);
0099
0100     symbol_iterator &operator++();
0101     const SymExpr *operator*();
0102
0103     bool operator==(const symbol_iterator &X) const;
0104     bool operator!=(const symbol_iterator &X) const;
0105   };
0106
0107   llvm::iterator_range<symbol_iterator> symbols() const {
0108     return llvm::make_range(symbol_iterator(this), symbol_iterator());
0109   }
0110
0111   virtual unsigned computeComplexity() const = 0;
0112
0113   /// Find the region from which this symbol originates.
0114   ///
0115   /// Whenever the symbol was constructed to denote an unknown value of
0116   /// a certain memory region, return this region. This method
0117   /// allows checkers to make decisions depending on the origin of the symbol.
0118   /// Symbol classes for which the origin region is known include
0119   /// SymbolRegionValue which denotes the value of the region before
0120   /// the beginning of the analysis, and SymbolDerived which denotes the value
0121   /// of a certain memory region after its super region (a memory space or
0122   /// a larger record region) is default-bound with a certain symbol.
0123   /// It might return null.
0124   virtual const MemRegion *getOriginRegion() const { return nullptr; }
0125 };
0126
0127 inline raw_ostream &operator<<(raw_ostream &os,
0128                                const clang::ento::SymExpr *SE) {
0129   SE->dumpToStream(os);
0130   return os;
0131 }
0132
0133 using SymbolRef = const SymExpr *;
0134 using SymbolRefSmallVectorTy = SmallVector<SymbolRef, 2>;
0135
0136 /// A symbol representing data which can be stored in a memory location
0137 /// (region).
0138 class SymbolData : public SymExpr {
0139   void anchor() override;
0140
0141 protected:
0142   SymbolData(Kind k, SymbolID sym) : SymExpr(k, sym) { assert(classof(this)); }
0143
0144 public:
0145   ~SymbolData() override = default;
0146
0147   /// Get a string representation of the kind of the region.
0148   virtual StringRef getKindStr() const = 0;
0149
0150   unsigned computeComplexity() const override {
0151     return 1;
0152   };
0153
0154   // Implement isa<T> support.
0155   static inline bool classof(const SymExpr *SE) {
0156     Kind k = SE->getKind();
0157     return k >= BEGIN_SYMBOLS && k <= END_SYMBOLS;
0158   }
0159 };
0160
0161 } // namespace ento
0162 } // namespace clang
0163
0164 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_SYMEXPR_H