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

//===-- GRExprEngine.h - Path-Sensitive Expression-Level Dataflow ---*- 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 a meta-engine for path-sensitive dataflow analysis that
//  is built on GREngine, but provides the boilerplate to execute transfer
//  functions and build the ExplodedGraph at the expression level.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_GREXPRENGINE
#define LLVM_CLANG_ANALYSIS_GREXPRENGINE

#include "clang/Analysis/PathSensitive/GRCoreEngine.h"
#include "clang/Analysis/PathSensitive/ValueState.h"
#include "clang/Analysis/PathSensitive/GRSimpleAPICheck.h"
#include "clang/Analysis/PathSensitive/GRTransferFuncs.h"
#include "clang/AST/Type.h"

namespace clang {  
  
  class BugType;
  class PathDiagnosticClient;
  class Diagnostic;
  
class GRExprEngine {
  
public:
  typedef ValueState                  StateTy;
  typedef ExplodedGraph<StateTy>      GraphTy;
  typedef GraphTy::NodeTy             NodeTy;
  
  // Builders.
  typedef GRStmtNodeBuilder<StateTy>          StmtNodeBuilder;
  typedef GRBranchNodeBuilder<StateTy>        BranchNodeBuilder;
  typedef GRIndirectGotoNodeBuilder<StateTy>  IndirectGotoNodeBuilder;
  typedef GRSwitchNodeBuilder<StateTy>        SwitchNodeBuilder;
  typedef GREndPathNodeBuilder<StateTy>       EndPathNodeBuilder;
  typedef ExplodedNodeSet<StateTy>            NodeSet;
  
    
protected:
  GRCoreEngine<GRExprEngine> CoreEngine;
  
  /// G - the simulation graph.
  GraphTy& G;
  
  /// Liveness - live-variables information the ValueDecl* and block-level
  ///  Expr* in the CFG.  Used to prune out dead state.
  LiveVariables Liveness;
  
  /// DeadSymbols - A scratch set used to record the set of symbols that
  ///  were just marked dead by a call to ValueStateManager::RemoveDeadBindings.
  ValueStateManager::DeadSymbolsTy DeadSymbols;
  
  /// Builder - The current GRStmtNodeBuilder which is used when building the
  ///  nodes for a given statement.
  StmtNodeBuilder* Builder;
  
  /// StateMgr - Object that manages the data for all created states.
  ValueStateManager StateMgr;
  
  /// ValueMgr - Object that manages the data for all created RVals.
  BasicValueFactory& BasicVals;
  
  /// TF - Object that represents a bundle of transfer functions
  ///  for manipulating and creating RVals.
  GRTransferFuncs* TF;
  
  /// BugTypes - Objects used for reporting bugs.
  typedef std::vector<BugType*> BugTypeSet;
  BugTypeSet BugTypes;
  
  /// SymMgr - Object that manages the symbol information.
  SymbolManager& SymMgr;
  
  /// EntryNode - The immediate predecessor node.
  NodeTy* EntryNode;

  /// CleanedState - The state for EntryNode "cleaned" of all dead
  ///  variables and symbols (as determined by a liveness analysis).
  ValueState* CleanedState;  
  
  /// CurrentStmt - The current block-level statement.
  Stmt* CurrentStmt;
  
  // Obj-C Class Identifiers.
  IdentifierInfo* NSExceptionII;
  
  // Obj-C Selectors.
  Selector* NSExceptionInstanceRaiseSelectors;
  Selector RaiseSel;
  
  typedef llvm::SmallVector<GRSimpleAPICheck*,2> SimpleChecksTy;
  
  SimpleChecksTy CallChecks;
  SimpleChecksTy MsgExprChecks;
  
public:
  typedef llvm::SmallPtrSet<NodeTy*,2> UndefBranchesTy;  
  typedef llvm::SmallPtrSet<NodeTy*,2> UndefStoresTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> BadDerefTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> BadCallsTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> UndefReceiversTy;
  typedef llvm::DenseMap<NodeTy*, Expr*> UndefArgsTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> BadDividesTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> NoReturnCallsTy;  
  typedef llvm::SmallPtrSet<NodeTy*,2> UndefResultsTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> RetsStackAddrTy;
  
protected:

  /// RetsStackAddr - Nodes in the ExplodedGraph that result from returning
  ///  the address of a stack variable.
  RetsStackAddrTy RetsStackAddr;
  
  /// UndefBranches - Nodes in the ExplodedGraph that result from
  ///  taking a branch based on an undefined value.
  UndefBranchesTy UndefBranches;
  
  /// UndefStores - Sinks in the ExplodedGraph that result from
  ///  making a store to an undefined lvalue.
  UndefStoresTy UndefStores;
  
  /// NoReturnCalls - Sinks in the ExplodedGraph that result from
  //  calling a function with the attribute "noreturn".
  NoReturnCallsTy NoReturnCalls;
  
  /// ImplicitNullDeref - Nodes in the ExplodedGraph that result from
  ///  taking a dereference on a symbolic pointer that MAY be NULL.
  BadDerefTy ImplicitNullDeref;
    
  /// ExplicitNullDeref - Nodes in the ExplodedGraph that result from
  ///  taking a dereference on a symbolic pointer that MUST be NULL.
  BadDerefTy ExplicitNullDeref;
  
  /// UnitDeref - Nodes in the ExplodedGraph that result from
  ///  taking a dereference on an undefined value.
  BadDerefTy UndefDeref;

  /// ImplicitBadDivides - Nodes in the ExplodedGraph that result from 
  ///  evaluating a divide or modulo operation where the denominator
  ///  MAY be zero.
  BadDividesTy ImplicitBadDivides;
  
  /// ExplicitBadDivides - Nodes in the ExplodedGraph that result from 
  ///  evaluating a divide or modulo operation where the denominator
  ///  MUST be zero or undefined.
  BadDividesTy ExplicitBadDivides;
  
  /// UndefResults - Nodes in the ExplodedGraph where the operands are defined
  ///  by the result is not.  Excludes divide-by-zero errors.
  UndefResultsTy UndefResults;
  
  /// BadCalls - Nodes in the ExplodedGraph resulting from calls to function
  ///  pointers that are NULL (or other constants) or Undefined.
  BadCallsTy BadCalls;
  
  /// UndefReceiver - Nodes in the ExplodedGraph resulting from message
  ///  ObjC message expressions where the receiver is undefined (uninitialized).
  UndefReceiversTy UndefReceivers;
  
  /// UndefArg - Nodes in the ExplodedGraph resulting from calls to functions
  ///   where a pass-by-value argument has an undefined value.
  UndefArgsTy UndefArgs;
  
  /// MsgExprUndefArgs - Nodes in the ExplodedGraph resulting from
  ///   message expressions where a pass-by-value argument has an undefined
  ///  value.
  UndefArgsTy MsgExprUndefArgs;
  
public:
  GRExprEngine(CFG& cfg, Decl& CD, ASTContext& Ctx);
  ~GRExprEngine();
  
  void ExecuteWorkList(unsigned Steps = 150000) {
    CoreEngine.ExecuteWorkList(Steps);
  }
  
  /// getContext - Return the ASTContext associated with this analysis.
  ASTContext& getContext() const { return G.getContext(); }
  
  /// getCFG - Returns the CFG associated with this analysis.
  CFG& getCFG() { return G.getCFG(); }
  
  /// setTransferFunctions
  void setTransferFunctions(GRTransferFuncs* tf);

  void setTransferFunctions(GRTransferFuncs& tf) {
    setTransferFunctions(&tf);
  }
  
  /// ViewGraph - Visualize the ExplodedGraph created by executing the
  ///  simulation.
  void ViewGraph(bool trim = false);
  
  void ViewGraph(NodeTy** Beg, NodeTy** End);
  
  /// getLiveness - Returned computed live-variables information for the
  ///  analyzed function.  
  const LiveVariables& getLiveness() const { return Liveness; }  
  LiveVariables& getLiveness() { return Liveness; }
  
  /// getInitialState - Return the initial state used for the root vertex
  ///  in the ExplodedGraph.
  ValueState* getInitialState();
  
  GraphTy& getGraph() { return G; }
  const GraphTy& getGraph() const { return G; }
  
  typedef BugTypeSet::iterator bug_type_iterator;
  typedef BugTypeSet::const_iterator const_bug_type_iterator;
  
  bug_type_iterator bug_types_begin() { return BugTypes.begin(); }
  bug_type_iterator bug_types_end() { return BugTypes.end(); }

  const_bug_type_iterator bug_types_begin() const { return BugTypes.begin(); }
  const_bug_type_iterator bug_types_end() const { return BugTypes.end(); }
  
  void Register(BugType* B) {
    BugTypes.push_back(B);
  }
  
  void EmitWarnings(Diagnostic& Diag, PathDiagnosticClient* PD);  
  
  bool isRetStackAddr(const NodeTy* N) const {
    return N->isSink() && RetsStackAddr.count(const_cast<NodeTy*>(N)) != 0;
  }
  
  bool isUndefControlFlow(const NodeTy* N) const {
    return N->isSink() && UndefBranches.count(const_cast<NodeTy*>(N)) != 0;
  }