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


GRExprEngine::GRExprEngine(CFG& cfg, Decl& CD, ASTContext& Ctx)
  : CoreEngine(cfg, CD, Ctx, *this), 
    G(CoreEngine.getGraph()),
    Liveness(G.getCFG()),
    Builder(NULL),
    StateMgr(G.getContext(), G.getAllocator()),
    BasicVals(StateMgr.getBasicValueFactory()),
    TF(NULL), // FIXME
    SymMgr(StateMgr.getSymbolManager()),
    StmtEntryNode(NULL), CleanedState(NULL), CurrentStmt(NULL) {
  
  // 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;  
}

//===----------------------------------------------------------------------===//
// 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;
};

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) {
    
    VarDecl* VD = cast<VarDecl>(const_cast<ScopedDecl*>(I->first));
    
    if (VD->hasGlobalStorage() || isa<ParmVarDecl>(VD)) {
      RVal X = RVal::GetSymbolValue(SymMgr, VD);
      StateMgr.BindVar(StateImpl, VD, 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, false);
}

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

void GRExprEngine::ProcessStmt(Stmt* S, StmtNodeBuilder& builder) {
  
  Builder = &builder;
  StmtEntryNode = builder.getLastNode();
  CurrentStmt = S;
  NodeSet Dst;
  
  // Set up our simple checks.
  
  // FIXME: This can probably be installed directly in GRCoreEngine, obviating
  //  the need to do a copy every time we hit a block-level statement.
  
  if (!MsgExprChecks.empty())
    Builder->setObjCMsgExprAuditors((GRAuditor<ValueState>**) &MsgExprChecks[0],
         (GRAuditor<ValueState>**) (&MsgExprChecks[0] + MsgExprChecks.size()));
  
  
  if (!CallChecks.empty())
    Builder->setCallExprAuditors((GRAuditor<ValueState>**) &CallChecks[0],
         (GRAuditor<ValueState>**) (&CallChecks[0] + CallChecks.size()));
  
  // Create the cleaned state.
  
  CleanedState = StateMgr.RemoveDeadBindings(StmtEntryNode->getState(),
                                             CurrentStmt, Liveness);
  
  Builder->SetCleanedState(CleanedState);
  
  // Visit the statement.
  
  Visit(S, StmtEntryNode, Dst);
  
  // If no nodes were generated, generate a new node that has all the
  // dead mappings removed.
  
  if (Dst.size() == 1 && *Dst.begin() == StmtEntryNode && 
      !Builder->HasGeneratedNode)
    builder.generateNode(S, GetState(StmtEntryNode), StmtEntryNode);
  
  // NULL out these variables to cleanup.
  
  CurrentStmt = NULL;
  StmtEntryNode = NULL;
  Builder = NULL;
  CleanedState = NULL;
}