path: root/include/clang/Analysis/PathSensitive/MemRegion.h

//== MemRegion.h - Abstract memory regions for static analysis --*- C++ -*--==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file defines MemRegion and its subclasses.  MemRegion defines a
//  partially-typed abstraction of memory useful for path-sensitive dataflow
//  analyses.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_MEMREGION_H
#define LLVM_CLANG_ANALYSIS_MEMREGION_H

#include "clang/AST/Decl.h"
#include "clang/AST/DeclObjC.h"
#include "clang/Analysis/PathSensitive/SymbolManager.h"
#include "clang/Analysis/PathSensitive/SVals.h"
#include "clang/AST/ASTContext.h"
#include "llvm/Support/Casting.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/ImmutableList.h"
#include "llvm/ADT/ImmutableMap.h"
#include "llvm/Support/Allocator.h"
#include <string>

namespace llvm { class raw_ostream; }

namespace clang {
 
class MemRegionManager;
  
      
/// MemRegion - The root abstract class for all memory regions.
class MemRegion : public llvm::FoldingSetNode {
public:
  enum Kind { MemSpaceRegionKind, SymbolicRegionKind,
              AllocaRegionKind,
              // Typed regions.
              BEG_TYPED_REGIONS,
               CompoundLiteralRegionKind,
               StringRegionKind, ElementRegionKind,
               AnonTypedRegionKind,
               AnonPointeeRegionKind,
               // Decl Regions.
                 BEG_DECL_REGIONS,
                  VarRegionKind, FieldRegionKind,
                  ObjCIvarRegionKind, ObjCObjectRegionKind,
                 END_DECL_REGIONS,
              END_TYPED_REGIONS };  
private:
  const Kind kind;
  
protected:
  MemRegion(Kind k) : kind(k) {}
  virtual ~MemRegion();

public:
  // virtual MemExtent getExtent(MemRegionManager& mrm) const = 0;
  virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0;
  
  std::string getString() const;

  virtual void print(llvm::raw_ostream& os) const;  
  
  Kind getKind() const { return kind; }  

  static bool classof(const MemRegion*) { return true; }
};
  
/// MemSpaceRegion - A memory region that represents and "memory space";
///  for example, the set of global variables, the stack frame, etc.
class MemSpaceRegion : public MemRegion {
  friend class MemRegionManager;
  MemSpaceRegion() : MemRegion(MemSpaceRegionKind) {}
  
public:
  //RegionExtent getExtent() const { return UndefinedExtent(); }

  void Profile(llvm::FoldingSetNodeID& ID) const;

  static bool classof(const MemRegion* R) {
    return R->getKind() == MemSpaceRegionKind;
  }
};

/// SubRegion - A region that subsets another larger region.  Most regions
///  are subclasses of SubRegion.
class SubRegion : public MemRegion {
protected:
  const MemRegion* superRegion;  
  SubRegion(const MemRegion* sReg, Kind k) : MemRegion(k), superRegion(sReg) {}
  
public:
  const MemRegion* getSuperRegion() const {
    return superRegion;
  }

  bool isSubRegionOf(const MemRegion* R) const;

  static bool classof(const MemRegion* R) {
    return R->getKind() > SymbolicRegionKind;
  }
};
  
/// AllocaRegion - A region that represents an untyped blob of bytes created
///  by a call to 'alloca'.
class AllocaRegion : public SubRegion {
  friend class MemRegionManager;
protected:
  unsigned Cnt; // Block counter.  Used to distinguish different pieces of
                // memory allocated by alloca at the same call site.
  const Expr* Ex;

  AllocaRegion(const Expr* ex, unsigned cnt, const MemRegion* superRegion)
    : SubRegion(superRegion, AllocaRegionKind), Cnt(cnt), Ex(ex) {}
  
public:
  
  const Expr* getExpr() const { return Ex; }
  
  void Profile(llvm::FoldingSetNodeID& ID) const;

  static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Expr* Ex,
                            unsigned Cnt);
  
  void print(llvm::raw_ostream& os) const;
  
  static bool classof(const MemRegion* R) {
    return R->getKind() == AllocaRegionKind;
  }
};    
  
/// SymbolicRegion - A special, "non-concrete" region. Unlike other region
///  clases, SymbolicRegion represents a region that serves as an alias for
///  either a real region, a NULL pointer, etc.  It essentially is used to
///  map the concept of symbolic values into the domain of regions.  Symbolic
///  regions do not need to be typed.
class SymbolicRegion : public MemRegion {
protected:
  const SymbolRef sym;

public:
  SymbolicRegion(const SymbolRef s) : MemRegion(SymbolicRegionKind), sym(s) {}
    
  SymbolRef getSymbol() const {
    return sym;
  }
    
  void Profile(llvm::FoldingSetNodeID& ID) const;
  static void ProfileRegion(llvm::FoldingSetNodeID& ID, SymbolRef sym);
  
  void print(llvm::raw_ostream& os) const;
  
  static bool classof(const MemRegion* R) {
    return R->getKind() == SymbolicRegionKind;
  }
};  

/// TypedRegion - An abstract class representing regions that are typed.
class TypedRegion : public SubRegion {
protected:
  TypedRegion(const MemRegion* sReg, Kind k) : SubRegion(sReg, k) {}
  
public:
  virtual QualType getRValueType(ASTContext &C) const = 0;
  
  virtual QualType getLValueType(ASTContext& C) const {
    // FIXME: We can possibly optimize this later to cache this value.
    return C.getPointerType(getRValueType(C));
  }

  static bool classof(const MemRegion* R) {
    unsigned k = R->getKind();
    return k > BEG_TYPED_REGIONS && k < END_TYPED_REGIONS;
  }
};

/// StringRegion - Region associated with a StringLiteral.
class StringRegion : public TypedRegion {
  friend class MemRegionManager;
  const StringLiteral* Str;
protected:

  StringRegion(const StringLiteral* str, MemRegion* sreg)
    : TypedRegion(sreg, StringRegionKind), Str(str) {}

  static void ProfileRegion(llvm::FoldingSetNodeID& ID,
                            const StringLiteral* Str,
                            const MemRegion* superRegion);

public:

  const StringLiteral* getStringLiteral() const { return Str; }
    
  QualType getRValueType(ASTContext& C) const;

  void Profile(llvm::FoldingSetNodeID& ID) const {
    ProfileRegion(ID, Str, superRegion);
  }

  void print(llvm::raw_ostream& os) const;

  static bool classof(const MemRegion* R) {
    return R->getKind() == StringRegionKind;
  }
};

class AnonTypedRegion : public TypedRegion {
  friend class MemRegionManager;

  QualType T;

  AnonTypedRegion(QualType t, const MemRegion* sreg)
    : TypedRegion(sreg, AnonTypedRegionKind), T(t) {}

  static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType T, 
                            const MemRegion* superRegion);

public:

  void print(llvm::raw_ostream& os) const;
  
  QualType getRValueType(ASTContext&) const {
    return T;
  }

  void Profile(llvm::FoldingSetNodeID& ID) const {
    ProfileRegion(ID, T, superRegion);
  }

  static bool classof(const MemRegion* R) {
    return R->getKind() == AnonTypedRegionKind;
  }
};
  

/// CompoundLiteralRegion - A memory region representing a com