include/clang/StaticAnalyzer/EntoSA/PathSensitive/SymbolManager.h

   1 //== SymbolManager.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 SymbolManager, a class that manages symbolic values
  11 //  created for use by ExprEngine and related classes.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CLANG_GR_SYMMGR_H
  16 #define LLVM_CLANG_GR_SYMMGR_H
  17
  18 #include "clang/AST/Decl.h"
  19 #include "clang/AST/Expr.h"
  20 #include "clang/Analysis/AnalysisContext.h"
  21 #include "llvm/Support/DataTypes.h"
  22 #include "llvm/ADT/FoldingSet.h"
  23 #include "llvm/ADT/DenseSet.h"
  24
  25 namespace llvm {
  26 class BumpPtrAllocator;
  27 class raw_ostream;
  28 }
  29
  30 namespace clang {
  31   class ASTContext;
  32   class StackFrameContext;
  33
  34 namespace ento {
  35   class BasicValueFactory;
  36   class MemRegion;
  37   class SubRegion;
  38   class TypedRegion;
  39   class VarRegion;
  40
  41 class SymExpr : public llvm::FoldingSetNode {
  42 public:
  43   enum Kind { BEGIN_SYMBOLS,
  44               RegionValueKind, ConjuredKind, DerivedKind, ExtentKind,
  45               MetadataKind,
  46               END_SYMBOLS,
  47               SymIntKind, SymSymKind };
  48 private:
  49   Kind K;
  50
  51 protected:
  52   SymExpr(Kind k) : K(k) {}
  53
  54 public:
  55   virtual ~SymExpr() {}
  56
  57   Kind getKind() const { return K; }
  58
  59   void dump() const;
  60
  61   virtual void dumpToStream(llvm::raw_ostream &os) const = 0;
  62
  63   virtual QualType getType(ASTContext&) const = 0;
  64   virtual void Profile(llvm::FoldingSetNodeID& profile) = 0;
  65
  66   // Implement isa<T> support.
  67   static inline bool classof(const SymExpr*) { return true; }
  68 };
  69
  70 typedef unsigned SymbolID;
  71
  72 class SymbolData : public SymExpr {
  73 private:
  74   const SymbolID Sym;
  75
  76 protected:
  77   SymbolData(Kind k, SymbolID sym) : SymExpr(k), Sym(sym) {}
  78
  79 public:
  80   virtual ~SymbolData() {}
  81
  82   SymbolID getSymbolID() const { return Sym; }
  83
  84   // Implement isa<T> support.
  85   static inline bool classof(const SymExpr* SE) {
  86     Kind k = SE->getKind();
  87     return k > BEGIN_SYMBOLS && k < END_SYMBOLS;
  88   }
  89 };
  90
  91 typedef const SymbolData* SymbolRef;
  92
  93 // A symbol representing the value of a MemRegion.
  94 class SymbolRegionValue : public SymbolData {
  95   const TypedRegion *R;
  96
  97 public:
  98   SymbolRegionValue(SymbolID sym, const TypedRegion *r)
  99     : SymbolData(RegionValueKind, sym), R(r) {}
 100
 101   const TypedRegion* getRegion() const { return R; }
 102
 103   static void Profile(llvm::FoldingSetNodeID& profile, const TypedRegion* R) {
 104     profile.AddInteger((unsigned) RegionValueKind);
 105     profile.AddPointer(R);
 106   }
 107
 108   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 109     Profile(profile, R);
 110   }
 111
 112   void dumpToStream(llvm::raw_ostream &os) const;
 113
 114   QualType getType(ASTContext&) const;
 115
 116   // Implement isa<T> support.
 117   static inline bool classof(const SymExpr* SE) {
 118     return SE->getKind() == RegionValueKind;
 119   }
 120 };
 121
 122 // A symbol representing the result of an expression.
 123 class SymbolConjured : public SymbolData {
 124   const Stmt* S;
 125   QualType T;
 126   unsigned Count;
 127   const void* SymbolTag;
 128
 129 public:
 130   SymbolConjured(SymbolID sym, const Stmt* s, QualType t, unsigned count,
 131                  const void* symbolTag)
 132     : SymbolData(ConjuredKind, sym), S(s), T(t), Count(count),
 133       SymbolTag(symbolTag) {}
 134
 135   const Stmt* getStmt() const { return S; }
 136   unsigned getCount() const { return Count; }
 137   const void* getTag() const { return SymbolTag; }
 138
 139   QualType getType(ASTContext&) const;
 140
 141   void dumpToStream(llvm::raw_ostream &os) const;
 142
 143   static void Profile(llvm::FoldingSetNodeID& profile, const Stmt* S,
 144                       QualType T, unsigned Count, const void* SymbolTag) {
 145     profile.AddInteger((unsigned) ConjuredKind);
 146     profile.AddPointer(S);
 147     profile.Add(T);
 148     profile.AddInteger(Count);
 149     profile.AddPointer(SymbolTag);
 150   }
 151
 152   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 153     Profile(profile, S, T, Count, SymbolTag);
 154   }
 155
 156   // Implement isa<T> support.
 157   static inline bool classof(const SymExpr* SE) {
 158     return SE->getKind() == ConjuredKind;
 159   }
 160 };
 161
 162 // A symbol representing the value of a MemRegion whose parent region has
 163 // symbolic value.
 164 class SymbolDerived : public SymbolData {
 165   SymbolRef parentSymbol;
 166   const TypedRegion *R;
 167
 168 public:
 169   SymbolDerived(SymbolID sym, SymbolRef parent, const TypedRegion *r)
 170     : SymbolData(DerivedKind, sym), parentSymbol(parent), R(r) {}
 171
 172   SymbolRef getParentSymbol() const { return parentSymbol; }
 173   const TypedRegion *getRegion() const { return R; }
 174
 175   QualType getType(ASTContext&) const;
 176
 177   void dumpToStream(llvm::raw_ostream &os) const;
 178
 179   static void Profile(llvm::FoldingSetNodeID& profile, SymbolRef parent,
 180                       const TypedRegion *r) {
 181     profile.AddInteger((unsigned) DerivedKind);
 182     profile.AddPointer(r);
 183     profile.AddPointer(parent);
 184   }
 185
 186   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 187     Profile(profile, parentSymbol, R);
 188   }
 189
 190   // Implement isa<T> support.
 191   static inline bool classof(const SymExpr* SE) {
 192     return SE->getKind() == DerivedKind;
 193   }
 194 };
 195
 196 /// SymbolExtent - Represents the extent (size in bytes) of a bounded region.
 197 ///  Clients should not ask the SymbolManager for a region's extent. Always use
 198 ///  SubRegion::getExtent instead -- the value returned may not be a symbol.
 199 class SymbolExtent : public SymbolData {
 200   const SubRegion *R;
 201
 202 public:
 203   SymbolExtent(SymbolID sym, const SubRegion *r)
 204   : SymbolData(ExtentKind, sym), R(r) {}
 205
 206   const SubRegion *getRegion() const { return R; }
 207
 208   QualType getType(ASTContext&) const;
 209
 210   void dumpToStream(llvm::raw_ostream &os) const;
 211
 212   static void Profile(llvm::FoldingSetNodeID& profile, const SubRegion *R) {
 213     profile.AddInteger((unsigned) ExtentKind);
 214     profile.AddPointer(R);
 215   }
 216
 217   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 218     Profile(profile, R);
 219   }
 220
 221   // Implement isa<T> support.
 222   static inline bool classof(const SymExpr* SE) {
 223     return SE->getKind() == ExtentKind;
 224   }
 225 };
 226
 227 /// SymbolMetadata - Represents path-dependent metadata about a specific region.
 228 ///  Metadata symbols remain live as long as they are marked as in use before
 229 ///  dead-symbol sweeping AND their associated regions are still alive.
 230 ///  Intended for use by checkers.
 231 class SymbolMetadata : public SymbolData {
 232   const MemRegion* R;
 233   const Stmt* S;
 234   QualType T;
 235   unsigned Count;
 236   const void* Tag;
 237 public:
 238   SymbolMetadata(SymbolID sym, const MemRegion* r, const Stmt* s, QualType t,
 239                  unsigned count, const void* tag)
 240   : SymbolData(MetadataKind, sym), R(r), S(s), T(t), Count(count), Tag(tag) {}
 241
 242   const MemRegion *getRegion() const { return R; }
 243   const Stmt* getStmt() const { return S; }
 244   unsigned getCount() const { return Count; }
 245   const void* getTag() const { return Tag; }
 246
 247   QualType getType(ASTContext&) const;
 248
 249   void dumpToStream(llvm::raw_ostream &os) const;
 250
 251   static void Profile(llvm::FoldingSetNodeID& profile, const MemRegion *R,
 252                       const Stmt *S, QualType T, unsigned Count,
 253                       const void *Tag) {
 254     profile.AddInteger((unsigned) MetadataKind);
 255     profile.AddPointer(R);
 256     profile.AddPointer(S);
 257     profile.Add(T);
 258     profile.AddInteger(Count);
 259     profile.AddPointer(Tag);
 260   }
 261
 262   virtual void Profile(llvm::FoldingSetNodeID& profile) {
 263     Profile(profile, R, S, T, Count, Tag);
 264   }
 265
 266   // Implement isa<T> support.
 267   static inline bool classof(const SymExpr* SE) {
 268     return SE->getKind() == MetadataKind;
 269   }
 270 };
 271
 272 // SymIntExpr - Represents symbolic expression like 'x' + 3.
 273 class SymIntExpr : public SymExpr {
 274   const SymExpr *LHS;
 275   BinaryOperator::Opcode Op;
 276   const llvm::APSInt& RHS;
 277   QualType T;
 278
 279 public:
 280   SymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 281              const llvm::APSInt& rhs, QualType t)
 282     : SymExpr(SymIntKind), LHS(lhs), Op(op), RHS(rhs), T(t) {}
 283
 284   // FIXME: We probably need to make this out-of-line to avoid redundant
 285   // generation of virtual functions.
 286   QualType getType(ASTContext& C) const { return T; }
 287
 288   BinaryOperator::Opcode getOpcode() const { return Op; }
 289
 290   void dumpToStream(llvm::raw_ostream &os) const;
 291
 292   const SymExpr *getLHS() const { return LHS; }
 293   const llvm::APSInt &getRHS() const { return RHS; }
 294
 295   static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
 296                       BinaryOperator::Opcode op, const llvm::APSInt& rhs,
 297                       QualType t) {
 298     ID.AddInteger((unsigned) SymIntKind);
 299     ID.AddPointer(lhs);
 300     ID.AddInteger(op);
 301     ID.AddPointer(&rhs);
 302     ID.Add(t);
 303   }
 304
 305   void Profile(llvm::FoldingSetNodeID& ID) {
 306     Profile(ID, LHS, Op, RHS, T);
 307   }
 308
 309   // Implement isa<T> support.
 310   static inline bool classof(const SymExpr* SE) {
 311     return SE->getKind() == SymIntKind;
 312   }
 313 };
 314
 315 // SymSymExpr - Represents symbolic expression like 'x' + 'y'.
 316 class SymSymExpr : public SymExpr {
 317   const SymExpr *LHS;
 318   BinaryOperator::Opcode Op;
 319   const SymExpr *RHS;
 320   QualType T;
 321
 322 public:
 323   SymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op, const SymExpr *rhs,
 324              QualType t)
 325     : SymExpr(SymSymKind), LHS(lhs), Op(op), RHS(rhs), T(t) {}
 326
 327   BinaryOperator::Opcode getOpcode() const { return Op; }
 328   const SymExpr *getLHS() const { return LHS; }
 329   const SymExpr *getRHS() const { return RHS; }
 330
 331   // FIXME: We probably need to make this out-of-line to avoid redundant
 332   // generation of virtual functions.
 333   QualType getType(ASTContext& C) const { return T; }
 334
 335   void dumpToStream(llvm::raw_ostream &os) const;
 336
 337   static void Profile(llvm::FoldingSetNodeID& ID, const SymExpr *lhs,
 338                     BinaryOperator::Opcode op, const SymExpr *rhs, QualType t) {
 339     ID.AddInteger((unsigned) SymSymKind);
 340     ID.AddPointer(lhs);
 341     ID.AddInteger(op);
 342     ID.AddPointer(rhs);
 343     ID.Add(t);
 344   }
 345
 346   void Profile(llvm::FoldingSetNodeID& ID) {
 347     Profile(ID, LHS, Op, RHS, T);
 348   }
 349
 350   // Implement isa<T> support.
 351   static inline bool classof(const SymExpr* SE) {
 352     return SE->getKind() == SymSymKind;
 353   }
 354 };
 355
 356 class SymbolManager {
 357   typedef llvm::FoldingSet<SymExpr> DataSetTy;
 358   DataSetTy DataSet;
 359   unsigned SymbolCounter;
 360   llvm::BumpPtrAllocator& BPAlloc;
 361   BasicValueFactory &BV;
 362   ASTContext& Ctx;
 363
 364 public:
 365   SymbolManager(ASTContext& ctx, BasicValueFactory &bv,
 366                 llvm::BumpPtrAllocator& bpalloc)
 367     : SymbolCounter(0), BPAlloc(bpalloc), BV(bv), Ctx(ctx) {}
 368
 369   ~SymbolManager();
 370
 371   static bool canSymbolicate(QualType T);
 372
 373   /// Make a unique symbol for MemRegion R according to its kind.
 374   const SymbolRegionValue* getRegionValueSymbol(const TypedRegion* R);
 375
 376   const SymbolConjured* getConjuredSymbol(const Stmt* E, QualType T,
 377                                           unsigned VisitCount,
 378                                           const void* SymbolTag = 0);
 379
 380   const SymbolConjured* getConjuredSymbol(const Expr* E, unsigned VisitCount,
 381                                           const void* SymbolTag = 0) {
 382     return getConjuredSymbol(E, E->getType(), VisitCount, SymbolTag);
 383   }
 384
 385   const SymbolDerived *getDerivedSymbol(SymbolRef parentSymbol,
 386                                         const TypedRegion *R);
 387
 388   const SymbolExtent *getExtentSymbol(const SubRegion *R);
 389
 390   const SymbolMetadata* getMetadataSymbol(const MemRegion* R, const Stmt* S,
 391                                           QualType T, unsigned VisitCount,
 392                                           const void* SymbolTag = 0);
 393
 394   const SymIntExpr *getSymIntExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 395                                   const llvm::APSInt& rhs, QualType t);
 396
 397   const SymIntExpr *getSymIntExpr(const SymExpr &lhs, BinaryOperator::Opcode op,
 398                                   const llvm::APSInt& rhs, QualType t) {
 399     return getSymIntExpr(&lhs, op, rhs, t);
 400   }
 401
 402   const SymSymExpr *getSymSymExpr(const SymExpr *lhs, BinaryOperator::Opcode op,
 403                                   const SymExpr *rhs, QualType t);
 404
 405   QualType getType(const SymExpr *SE) const {
 406     return SE->getType(Ctx);
 407   }
 408
 409   ASTContext &getContext() { return Ctx; }
 410   BasicValueFactory &getBasicVals() { return BV; }
 411 };
 412
 413 class SymbolReaper {
 414   typedef llvm::DenseSet<SymbolRef> SetTy;
 415
 416   SetTy TheLiving;
 417   SetTy MetadataInUse;
 418   SetTy TheDead;
 419   const LocationContext *LCtx;
 420   const Stmt *Loc;
 421   SymbolManager& SymMgr;
 422
 423 public:
 424   SymbolReaper(const LocationContext *ctx, const Stmt *s, SymbolManager& symmgr)
 425    : LCtx(ctx), Loc(s), SymMgr(symmgr) {}
 426
 427   ~SymbolReaper() {}
 428
 429   const LocationContext *getLocationContext() const { return LCtx; }
 430   const Stmt *getCurrentStatement() const { return Loc; }
 431
 432   bool isLive(SymbolRef sym);
 433   bool isLive(const Stmt *ExprVal) const;
 434   bool isLive(const VarRegion *VR) const;
 435
 436   // markLive - Unconditionally marks a symbol as live. This should never be
 437   //  used by checkers, only by the state infrastructure such as the store and
 438   //  environment. Checkers should instead use metadata symbols and markInUse.
 439   void markLive(SymbolRef sym);
 440
 441   // markInUse - Marks a symbol as important to a checker. For metadata symbols,
 442   //  this will keep the symbol alive as long as its associated region is also
 443   //  live. For other symbols, this has no effect; checkers are not permitted
 444   //  to influence the life of other symbols. This should be used before any
 445   //  symbol marking has occurred, i.e. in the MarkLiveSymbols callback.
 446   void markInUse(SymbolRef sym);
 447
 448   // maybeDead - If a symbol is known to be live, marks the symbol as live.
 449   //  Otherwise, if the symbol cannot be proven live, it is marked as dead.
 450   //  Returns true if the symbol is dead, false if live.
 451   bool maybeDead(SymbolRef sym);
 452
 453   typedef SetTy::const_iterator dead_iterator;
 454   dead_iterator dead_begin() const { return TheDead.begin(); }
 455   dead_iterator dead_end() const { return TheDead.end(); }
 456
 457   bool hasDeadSymbols() const {
 458     return !TheDead.empty();
 459   }
 460
 461   /// isDead - Returns whether or not a symbol has been confirmed dead. This
 462   ///  should only be called once all marking of dead symbols has completed.
 463   ///  (For checkers, this means only in the evalDeadSymbols callback.)
 464   bool isDead(SymbolRef sym) const {
 465     return TheDead.count(sym);
 466   }
 467 };
 468
 469 class SymbolVisitor {
 470 public:
 471   // VisitSymbol - A visitor method invoked by
 472   //  GRStateManager::scanReachableSymbols.  The method returns \c true if
 473   //  symbols should continue be scanned and \c false otherwise.
 474   virtual bool VisitSymbol(SymbolRef sym) = 0;
 475   virtual ~SymbolVisitor();
 476 };
 477
 478 } // end GR namespace
 479
 480 } // end clang namespace
 481
 482 namespace llvm {
 483 static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os,
 484                                             const clang::ento::SymExpr *SE) {
 485   SE->dumpToStream(os);
 486   return os;
 487 }
 488 } // end llvm namespace
 489 #endif