GRExprEngine.cpp

//=-- GRExprEngine.cpp - 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.
//
//===----------------------------------------------------------------------===//

#include "clang/AST/ParentMap.h"
#include "clang/Analysis/PathSensitive/GRExprEngine.h"
#include "clang/Analysis/PathSensitive/BugReporter.h"
#include "clang/Basic/SourceManager.h"
#include "llvm/Support/Streams.h"

#ifndef NDEBUG
#include "llvm/Support/GraphWriter.h"
#include <sstream>
#endif

using namespace clang;
using llvm::dyn_cast;
using llvm::cast;
using llvm::APSInt;

//===----------------------------------------------------------------------===//
// Engine construction and deletion.
//===----------------------------------------------------------------------===//

static inline Selector GetNullarySelector(const char* name, ASTContext& Ctx) {
  IdentifierInfo* II = &Ctx.Idents.get(name);
  return Ctx.Selectors.getSelector(0, &II);
}


GRExprEngine::GRExprEngine(CFG& cfg, Decl& CD, ASTContext& Ctx)
  : CoreEngine(cfg, CD, Ctx, *this), 
    G(CoreEngine.getGraph()),
    Parents(0),
    Liveness(G.getCFG()),
    Builder(NULL),
    StateMgr(G.getContext(), G.getAllocator()),
    BasicVals(StateMgr.getBasicValueFactory()),
    TF(NULL), // FIXME
    SymMgr(StateMgr.getSymbolManager()),
    CurrentStmt(NULL),
  NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL),
  RaiseSel(GetNullarySelector("raise", G.getContext())) {
  
  // Compute liveness information.
  Liveness.runOnCFG(G.getCFG());
  Liveness.runOnAllBlocks(G.getCFG(), NULL, true);
}

GRExprEngine::~GRExprEngine() {    
  for (BugTypeSet::iterator I = BugTypes.begin(), E = BugTypes.end(); I!=E; ++I)
    delete *I;
    
  for (SimpleChecksTy::iterator I = CallChecks.begin(), E = CallChecks.end();
       I != E; ++I)
    delete *I;
  
  for (SimpleChecksTy::iterator I=MsgExprChecks.begin(), E=MsgExprChecks.end();
       I != E; ++I)
    delete *I;  
  
  delete [] NSExceptionInstanceRaiseSelectors;
  
  delete Parents;
}

ParentMap& GRExprEngine::getParentMap() {
  if (!Parents) {
    Stmt* Body = getGraph().getCodeDecl().getCodeBody();
    Parents = new ParentMap(Body);  
  }
  
  return *Parents;
}

//===----------------------------------------------------------------------===//
// Utility methods.
//===----------------------------------------------------------------------===//

// SaveAndRestore - A utility class that uses RIIA to save and restore
//  the value of a variable.
template<typename T>
struct VISIBILITY_HIDDEN SaveAndRestore {
  SaveAndRestore(T& x) : X(x), old_value(x) {}
  ~SaveAndRestore() { X = old_value; }
  T get() { return old_value; }
  
  T& X;
  T old_value;
};

// SaveOr - Similar to SaveAndRestore.  Operates only on bools; the old
//  value of a variable is saved, and during the dstor the old value is
//  or'ed with the new value.
struct VISIBILITY_HIDDEN SaveOr {
  SaveOr(bool& x) : X(x), old_value(x) { x = false; }
  ~SaveOr() { X |= old_value; }
  
  bool& X;
  bool old_value;
};


void GRExprEngine::EmitWarnings(Diagnostic& Diag, PathDiagnosticClient* PD) {
  for (bug_type_iterator I = bug_types_begin(), E = bug_types_end(); I!=E; ++I){
    BugReporter BR(Diag, PD, getContext(), *this);
    (*I)->EmitWarnings(BR);
  }
  
  for (SimpleChecksTy::iterator I = CallChecks.begin(), E = CallChecks.end();
       I != E; ++I) {
    BugReporter BR(Diag, PD, getContext(), *this);
    (*I)->EmitWarnings(BR);
  }
  
  for (SimpleChecksTy::iterator I=MsgExprChecks.begin(), E=MsgExprChecks.end();
       I != E; ++I) {
    BugReporter BR(Diag, PD, getContext(), *this);
    (*I)->EmitWarnings(BR);
  }
}

void GRExprEngine::setTransferFunctions(GRTransferFuncs* tf) {
  TF = tf;
  TF->RegisterChecks(*this);
}

void GRExprEngine::AddCallCheck(GRSimpleAPICheck* A) {
  CallChecks.push_back(A);
}

void GRExprEngine::AddObjCMessageExprCheck(GRSimpleAPICheck* A) {
  MsgExprChecks.push_back(A);
}

ValueState* GRExprEngine::getInitialState() {

  // The LiveVariables information already has a compilation of all VarDecls
  // used in the function.  Iterate through this set, and "symbolicate"
  // any VarDecl whose value originally comes from outside the function.
  
  typedef LiveVariables::AnalysisDataTy LVDataTy;
  LVDataTy& D = Liveness.getAnalysisData();
  
  ValueState StateImpl = *StateMgr.getInitialState();
  
  for (LVDataTy::decl_iterator I=D.begin_decl(), E=D.end_decl(); I != E; ++I) {
    
    ScopedDecl *SD = const_cast<ScopedDecl*>(I->first);
    if (VarDecl* VD = dyn_cast<VarDecl>(SD)) {
      if (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD)) {
        RVal X = RVal::GetSymbolValue(SymMgr, VD);
        StateMgr.BindVar(StateImpl, VD, X);
      }
    } else if (ImplicitParamDecl *IPD = dyn_cast<ImplicitParamDecl>(SD)) {
        RVal X = RVal::GetSymbolValue(SymMgr, IPD);
        StateMgr.BindVar(StateImpl, IPD, X);
    }
      

  }
  
  return StateMgr.getPersistentState(StateImpl);
}      
      
ValueState* GRExprEngine::SetRVal(ValueState* St, Expr* Ex, RVal V) {

  bool isBlkExpr = false;
    
  if (Ex == CurrentStmt) {
    isBlkExpr = getCFG().isBlkExpr(Ex);
    
    if (!isBlkExpr)
      return St;
  }

  return StateMgr.SetRVal(St, Ex, V, isBlkExpr, true);
}

//===----------------------------------------------------------------------===//
// Top-level transfer function logic (Dispatcher).
//===----------------------------------------------------------------------===//

void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
  
  Builder = &builder;
  EntryNode = builder.getLastNode();
  CurrentStmt = S;