/*
 * See the dyninst/COPYRIGHT file for copyright information.
 * 
 * We provide the Paradyn Tools (below described as "Paradyn")
 * on an AS IS basis, and do not warrant its validity or performance.
 * We reserve the right to update, modify, or discontinue this
 * software at any time.  We shall have no obligation to supply such
 * updates or modifications or any other form of support to you.
 * 
 * By your use of Paradyn, you understand and agree that we (or any
 * other person or entity with proprietary rights in Paradyn) are
 * under no obligation to provide either maintenance services,
 * update services, notices of latent defects, or correction of
 * defects for Paradyn.
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */
#include <set>
#include <vector>
#include <map>
#include <utility>
#include "dataflowAPI/h/Absloc.h"
#include "dataflowAPI/h/AbslocInterface.h"
#include "Instruction.h"

#include "dataflowAPI/h/stackanalysis.h"

#include "dataflowAPI/h/slicing.h"

#include "dynutil/h/Graph.h"
#include "instructionAPI/h/Instruction.h"
#include "instructionAPI/h/InstructionDecoder.h"

#include "debug_dataflow.h"

#include "parseAPI/h/CFG.h"
#include "parseAPI/h/CodeSource.h"
#include "parseAPI/h/CodeObject.h"

#include <boost/bind.hpp>

using namespace Dyninst;
using namespace InstructionAPI;
using namespace std;
using namespace ParseAPI;

bool containsCall(ParseAPI::Block *);
bool containsRet(ParseAPI::Block *);
ParseAPI::Function *getEntryFunc(ParseAPI::Block *);

/* An algorithm to generate a slice graph.
 
The slice graph is a directed graph that consists of nodes
corresponding to assignments from a set of inputs to an
output, where each input or output is an `abstract region'
(AbsRegion class) describing a register or a stack or heap
location. Edges in the slice graph indicate flow from the
output AbsRegion of the source node to an input AbsRegion of
the target node. Edges are typed with an AbsRegion
corresponding to the input region the flow describes; this
edge typing is necessary because two AbsRegions in different
assignments may be refer to equivalent locations without
being identical---consider, for example, the transformation
of stack locations across function calls in interprocedural
slices.

Implementation details:

The slicing algorithm searches either forward or backward
from an initial assignment in the CFG, with the search
termination controlled in part by a set of user-provided
predicates (indicating, e.g., whether to follow call edges).
At each step, the slicer maintains an `active' set of
AbsRegions for which we are searching for related
assignments (uses, in the forward case; definitions, in the
backward case); this set is updated as the search
progresses. The graph is linked up on the way "down" the
slice recursion.

To avoid redundantly revisiting "down-slice" instructions
due to forks in the CFG, AbsRegion assignments are cached as
the search completes recursion down a particular branch.
Because CFGs are loopy directeg graphs, however, this does
not lead to an optimimal search ordering; it is possible to
construct pathological cases in which down-slice edges are
visited multiple times due to novel AbsRegions arising on
different paths. The caching of down-slice AbsRegions only 
guarantees that a particular AbsRegion is only searched for
once along a given path---the loopy nature of the graph
prevents optimal search stragegies such as a topologically
sorted ordering that would be possible in a DAG. 

The algorithm goes more or less like this:

   A_0 <- initial assignment 
   F <- initialize frame from active AbsRegions in A_0
   // F contains `active' set of AbsRegions
   
   sliceInternalAux( F ) :
     
      // find assignments in the current instruction,
      // add them to the graph if appropriate, update
      // the active set:
      // active <- active \ killed U matches
      updateAndLink(F)
  
      // `successor' is direction-appropriate 
      foreach successor NF of F
         if visited(F->NF) // edge visited    
            
            // try to add assignments cached from down-slice
            updateAndLinkFromCache(NF)
            
            // remove AbsRegions that have been visited
            // along this edge from the active set
            removeBlocked(NF) 

            // active is empty unless this instruction
            // introduced new active regions (in
            // updateAndLinkFromCache)

         visited(F->NF) <- true
         // recurse
         sliceInternalAux( NF )
         // merge cached definitions, except those generated
         // in F
         cache[F] <- cache[F] U (cache[NF] \ defs[F]

   Clearly the `find successors' bit is quite complicated
   and involves user-defined predicates and various CFG
   traversal rules, updating of AbsRegions, etc. Refer to
   comments in the code for more details.
*/
Graph::Ptr
Slicer::sliceInternal(
    Direction dir,
    Predicates &p)
{
    Graph::Ptr ret;
    SliceNode::Ptr aP;
    SliceFrame initFrame;
    map<CacheEdge, set<AbsRegion> > visited;
    map<Address,DefCache> cache;
    
    ret = Graph::createGraph();

    // set up a slicing frame describing with the
    // relevant context
    constructInitialFrame(dir,initFrame);

    // note that the AbsRegion in this Element *does not matter*;
    // we just need the block, function and assignment
    aP = createNode(Element(b_,f_,a_->out(),a_));

    if(dir == forward) {
        slicing_printf("Inserting entry node %p/%s\n",
            aP.get(),aP->format().c_str());
    } else {
        slicing_printf("Inserting exit node %p/%s\n",
            aP.get(),aP->format().c_str());
    }

    // add to graph
    insertInitialNode(ret, dir, aP);

    slicing_printf("Starting recursive slicing\n");
    sliceInternalAux(ret,dir,p,initFrame,true,visited,cache);
    slicing_printf("Finished recursive slicing\n");

    cleanGraph(ret);
    return ret;
}

void
Slicer::sliceInternalAux(
    Graph::Ptr g,
    Direction dir,
    Predicates &p,
    SliceFrame &cand,
    bool skip,              // skip linking this frame; for bootstrapping
    map<CacheEdge,set<AbsRegion> > & visited,
    map<Address,DefCache> & cache)
{
    vector<SliceFrame> nextCands;
    DefCache mydefs;

    slicing_printf("\tslicing from %lx, currently watching %ld regions\n",
        cand.addr(),cand.active.size());

    // Find assignments at this point that affect the active
    // region set (if any) and link them into the graph; update
    // the active set. Returns `true' if any changes are made,
    // `false' otherwise.

    if (!skip) {
        updateAndLink(g,dir,cand,mydefs,p);
	    slicing_printf("\t\tfinished udpateAndLink, active.size: %ld\n",
                       cand.active.size());
	}

    if (cand.active.empty())
        return;

    // Find the next search candidates along the control
    // flow (for appropriate direction)
    bool success = getNextCandidates(dir,p,cand,nextCands);
    if (!success) {
        widenAll(g,dir,cand);
    }

    slicing_printf("\t\tgetNextCandidates returned %ld, success: %d\n",
                   nextCands.size(),success);

    for (unsigned i=0; i < nextCands.size(); ++i) {
        SliceFrame & f = nextCands[i];
        if (!f.valid) {
            widenAll(g,dir,cand);
            continue;
        }
        CacheEdge e(cand.addr(),f.addr());

        slicing_printf("\t\t candidate %d is at %lx, %ld active\n",
                       i,f.addr(),f.active.size());

        if (visited.find(e) != visited.end()) {
            // attempt to resolve the current active set
            // via cached values from down-slice, eliminating
            // those elements of the active set that can be
            // so resolved

            updateAndLinkFromCache(g,dir,f,cache[f.addr()]);
            removeBlocked(f,visited[e]);

            // the only way this is not true is if the current
            // search path has introduced new AbsRegions of interest
            if (f.active.empty()) {
                continue;
            }
        }

        markVisited(visited,e,f.active);

        // If the control flow search has run
        // off the rails somehow, widen;
        // otherwise search down this new path
        if(!f.valid || visited.size() > 50*g->size()) {
            widenAll(g,dir,cand);
	}
        else {

	  sliceInternalAux(g,dir,p,f,false,visited,cache);
	  
	  // absorb the down-slice cache into this node's cache
	  cache[cand.addr()].merge(cache[f.addr()]);
        }
    }
   
    // Replace any definitions from down-slice with
    // those created by this instruction
    //
    // XXX if this instruction has definitions that
    //     were not of interest when it was visited
    //     (empty mydefs for that absregion), then
    //     do not cache down-slice information; if
    //     a different path leads back to this node,
    //     we need to create the real definitions
    cache[cand.addr()].replace(mydefs);
}

void
Slicer::removeBlocked(
    SliceFrame & f,
    set<AbsRegion> const& block)
{
    SliceFrame::ActiveMap::iterator ait = f.active.begin();
    for( ; ait != f.active.end(); ) {
        if(block.find((*ait).first) != block.end()) {
            SliceFrame::ActiveMap::iterator del = ait;
            ++ait;
            f.active.erase(del);
        } else {
            ++ait;
        }
    }
}

void
Slicer::markVisited(
    map<CacheEdge, set<AbsRegion> > & visited,
    CacheEdge const& e,
    SliceFrame::ActiveMap const& active)
{
    set<AbsRegion> & v = visited[e];
    SliceFrame::ActiveMap::const_iterator ait = active.begin();
    for( ; ait != active.end(); ++ait) {
        v.insert((*ait).first);
    }
}

bool
Slicer::updateAndLink(
    Graph::Ptr g,
    Direction dir,
    SliceFrame & cand,
    DefCache & cache,
    Predicates &p)
{
    vector<Assignment::Ptr> assns;
    vector<bool> killed;
    vector<Element> matches;
    vector<Element> newactive;
    Instruction::Ptr insn;
    bool change = false;

    killed.resize(cand.active.size(),false);

    if(dir == forward)
        insn = cand.loc.current->first;
    else
        insn = cand.loc.rcurrent->first;

    convertInstruction(insn,cand.addr(),cand.loc.func, cand.loc.block, assns);
    for(unsigned i=0; i<assns.size(); ++i) {
        SliceFrame::ActiveMap::iterator ait = cand.active.begin();
        unsigned j=0;
        for( ; ait != cand.active.end(); ++ait,++j) {
            findMatch(g,dir,cand,(*ait).first,assns[i],matches,cache); 
            killed[j] = killed[j] || kills((*ait).first,assns[i]);
            change = change || killed[j];
        }
        // Record the *potential* of this instruction to interact
        // with all possible abstract regions
        cachePotential(dir,assns[i],cache);
    }

    if(!change && matches.empty()) // no change -- nothing killed, nothing added
        return false;

    // update of active set -- matches + anything not killed
    SliceFrame::ActiveMap::iterator ait = cand.active.begin();
    unsigned j=0;
    for( ; ait != cand.active.end(); ) {
        if(killed[j]) {
            SliceFrame::ActiveMap::iterator del = ait;
            ++ait;
            cand.active.erase(del);
        } else {
            ++ait;
        }
        ++j;
    }

    for(unsigned i=0;i<matches.size();++i) {
       // Check our predicates
       if (p.widenAtPoint(matches[i].ptr)) {
          widen(g, dir, matches[i]);
       }
       else if (p.endAtPoint(matches[i].ptr)) {
          // Do nothing...
       }
       else {
          cand.active[matches[i].reg].push_back(matches[i]);
       }
    }

    return true;
}

void
Slicer::updateAndLinkFromCache(
    Graph::Ptr g,
    Direction dir,
    SliceFrame & f, 
    DefCache & cache)
{
    SliceFrame::ActiveMap::iterator ait = f.active.begin();

    // if the abstract region of interest is in the defcache,
    // update it and link it

    for( ; ait != f.active.end(); ) {
        AbsRegion const& r = (*ait).first;
        if(!cache.defines(r)) {
            ++ait;
            continue;
        }

        // Link them up 
        vector<Element> const& eles = (*ait).second;
        set<Def> const& defs = cache.get(r);
        set<Def>::const_iterator dit = defs.begin();
        for( ; dit != defs.end(); ++dit) {
            for(unsigned i=0;i<eles.size();++i) {
                // don't create self-loops on assignments
                if (eles[i].ptr != (*dit).ele.ptr)
                    insertPair(g,dir,eles[i],(*dit).ele,(*dit).data);
            }
        }

        // Stop caring about this region
        SliceFrame::ActiveMap::iterator del = ait;
        ++ait;
        f.active.erase(del);
    }
}

void
Slicer::cachePotential(
    Direction dir,
    Assignment::Ptr assn,
    DefCache & cache)
{
    if(dir == forward) {
        vector<AbsRegion> const& inputs = assn->inputs();
        for(unsigned i=0;i<inputs.size();++i) {
            (void)cache.get(inputs[i]);
        }
    } else {
        (void)cache.get(assn->out());
    }
}

/*
 * Compare the assignment `assn' to the abstract region `cur'
 * and see whether they match, for the direction-appropriate
 * definition of "match". If so, generate new slice elements
 * and return them in the `match' vector, after linking them
 * to the elements associated with the region `cur'
 */
void
Slicer::findMatch(
    Graph::Ptr g,
    Direction dir,
    SliceFrame const& cand,
    AbsRegion const& reg,
    Assignment::Ptr assn,
    vector<Element> & matches,
    DefCache & cache)
{
    if(dir == forward) {
		slicing_cerr << "\t\tComparing candidate assignment " << assn->format() << " to input region " << reg.format() << endl;
        vector<AbsRegion> const& inputs = assn->inputs();
        bool hadmatch = false;
        for(unsigned i=0;i<inputs.size();++i) {
            if(reg.contains(inputs[i])) {
                hadmatch = true;    
				slicing_cerr << "\t\t\t Match!" << endl;
                // Link the assignments associated with this
                // abstract region (may be > 1)
                Element ne(cand.loc.block,cand.loc.func,reg,assn);
                    
                // Cache
                cache.get(reg).insert( Def(ne,inputs[i]) );
                
                vector<Element> const& eles = cand.active.find(reg)->second;
                for(unsigned j=0;j<eles.size();++j) {
                    insertPair(g,dir,eles[j],ne,inputs[i]);

                }
            }
        }
        if(hadmatch) {
            // In this case, we are now interested in
            // the outputs of the assignment
            matches.push_back(
                Element(cand.loc.block,cand.loc.func,assn->out(),assn));
        }
    } else {
        slicing_printf("\t\t\t\t\tComparing current %s to candidate %s\n",
            reg.format().c_str(),assn->out().format().c_str());
        if(reg.contains(assn->out())) {
            slicing_printf("\t\t\t\t\t\tMatch!\n");

            // Link the assignments associated with this
            // abstract region (may be > 1)
            Element ne(cand.loc.block,cand.loc.func,reg,assn);
            
            // Cache
            cache.get(reg).insert( Def(ne,reg) );
            slicing_printf("\t\t\t cached [%s] -> <%s,%s>\n",
               reg.format().c_str(),
                ne.ptr->format().c_str(),reg.format().c_str()); 

            vector<Element> const& eles = cand.active.find(reg)->second;
            for(unsigned i=0;i<eles.size();++i) {
                // N.B. using the AbsRegion from the Element, which
                //      may differ from the `reg' parameter to this
                //      method because of transformation though
                //      call or return edges. This `true' AbsRegion
                //      is used to associate two different AbsRegions
                //      during symbolic evaluation
                if (eles[i].ptr != ne.ptr)
                    insertPair(g,dir,eles[i],ne,eles[i].reg);
            }

            // In this case, we are now interested in the 
            // _inputs_ to the assignment
            vector<AbsRegion> const& inputs = assn->inputs();
            for(unsigned i=0; i< inputs.size(); ++i) {
                ne.reg = inputs[i];
                matches.push_back(ne);
            }
        }
    }
}


bool 
Slicer::getNextCandidates(
    Direction dir,
    Predicates & p,
    SliceFrame const& cand,
    vector<SliceFrame> & newCands)
{
    if(dir == forward) {
        return getSuccessors(p,cand,newCands);
    }
    else {
        return getPredecessors(p,cand,newCands);
    }
}

/*
 * Given the location (instruction) in `cand', find zero or more
 * control flow successors from this location and create new slicing
 * frames for them. Certain types of control flow require mutation of
 * the SliceFrame (modification of context, e.g.) AND mutate the 
 * abstract regions in the frame's `active' list (e.g. modifying
 * stack locations).
 */
bool
Slicer::getSuccessors(
    Predicates &p,
    SliceFrame const& cand,
    vector<SliceFrame> & newCands)
{
    InsnVec::iterator next = cand.loc.current;
    ++next;

    // Case 1: just one intra-block successor
    if(next != cand.loc.end) {
        SliceFrame nf = cand;
        nf.loc.current = next;
        assert(nf.loc.block);
        newCands.push_back(nf);

        slicing_printf("\t\t\t\t added intra-block successor\n");
        return true;
    }

    // Case 2: end of the block. Subcases are calls, returns, and other
    bool err = false;

    if(containsCall(cand.loc.block)) {
        slicing_printf("\t\t Handling call... ");
        SliceFrame nf = cand;

        // nf may be transformed
        if(handleCall(p,nf,err)) {
            slicing_printf("success, err: %d\n",err);
            assert(nf.loc.block);
            newCands.push_back(nf);
        } else {
            slicing_printf("failed, err: %d\n",err);
        }
    }
    else if(containsRet(cand.loc.block)) {
        slicing_printf("\t\t Handling return... ");
        SliceFrame nf = cand;
    
        // nf may be transformed
        if(handleReturn(p,nf,err)) {
            slicing_printf("success, err: %d\n",err);
            assert(nf.loc.block);
            newCands.push_back(nf);
        } else {
            slicing_printf("failed, err: %d\n",err);
        }
    }
    else {
        // Default intraprocedural control flow case; this
        // case may produce multiple new frames, but it
        // will not transform any of them (besides changing
        // the location)

        const Block::edgelist & targets = cand.loc.block->targets();
        Block::edgelist::const_iterator eit = targets.begin();
        for( ; eit != targets.end(); ++eit) {
            if((*eit)->sinkEdge()) {
                // will force widening
                newCands.push_back(SliceFrame(false));
            } 
            else {
                SliceFrame nf = cand;
                slicing_printf("\t\t Handling default edge type %d... ",
                    (*eit)->type());
                if(handleDefault(forward,p,*eit,nf,err)) {
                    slicing_printf("success, err: %d\n",err);
                    assert(nf.loc.block);
                    newCands.push_back(nf);
                } else {
                    slicing_printf("failed, err: %d\n",err);
                }
            }
        }
    }
    return !err;
}

void Slicer::handlePredecessorEdge(ParseAPI::Edge* e,
				   Predicates& p,
				   SliceFrame const& cand,
				   vector<SliceFrame> & newCands,
				   bool& err,
				   SliceFrame& nf)
{
  switch(e->type()) 
  {
  case CALL:
    slicing_printf("\t\t Handling call... ");
    if(handleCallBackward(p,cand,newCands,e,err)) {
      slicing_printf("succeess, err: %d\n",err);
    } else {
      slicing_printf("failed, err: %d\n",err);
    }
    break;
  case RET:
    slicing_printf("\t\t Handling return... ");
    nf = cand;
    if(handleReturnBackward(p,cand,nf,e,err)) {
      slicing_printf("succeess, err: %d\n",err);
    } else {
      slicing_printf("failed, err: %d\n",err);
    }
    break;
  default:
    nf = cand;
    slicing_printf("\t\t Handling default edge type %d... ",
		   e->type());
    if(handleDefault(backward,p,e,nf,err)) {
      slicing_printf("success, err: %d\n",err);
      newCands.push_back(nf);
    } else {
      slicing_printf("failed, err: %d\n",err);
    }
  }
}


  

/*
 * Same as successors, only backwards
 */
bool
Slicer::getPredecessors(
    Predicates &p,
    SliceFrame const& cand,
    vector<SliceFrame> & newCands)
{
    InsnVec::reverse_iterator prev = cand.loc.rcurrent;
    ++prev;

    // Case 1: intra-block
    if(prev != cand.loc.rend) {
        SliceFrame nf(cand.loc,cand.con);
        nf.loc.rcurrent = prev;

        // Slightly more complicated than the forward case; check
        // a predicate for each active abstract region to see whether
        // we should continue
        bool cont = false;
        SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
        for( ; ait != cand.active.end(); ++ait) {
            bool add = p.addPredecessor((*ait).first);
            if(add)
                nf.active.insert(*ait);
            cont = cont || add;
        }

        if(cont) {
            slicing_printf("\t\t\t\t Adding intra-block predecessor %lx\n",
                nf.loc.addr());
            slicing_printf("\t\t\t\t Current regions are:\n");
            if(slicing_debug_on()) {
                SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
                for( ; ait != cand.active.end(); ++ait) {
                    slicing_printf("\t\t\t\t%s\n",
                        (*ait).first.format().c_str());

			vector<Element> const& eles = (*ait).second;
			for(unsigned i=0;i<eles.size();++i) {
				slicing_printf("\t\t\t\t\t [%s] : %s\n",
					eles[i].reg.format().c_str(),eles[i].ptr->format().c_str());
			}
                }
            }
    
            newCands.push_back(nf);
        }
        return true;
    }

    // Case 2: inter-block
    bool err = false;
    SliceFrame nf;
    
    SingleContextOrInterproc epred(cand.loc.func, true, true);

    const Block::edgelist & sources = cand.loc.block->sources();
    std::for_each(boost::make_filter_iterator(epred, sources.begin(), sources.end()),
		  boost::make_filter_iterator(epred, sources.end(), sources.end()),
		  boost::bind<void>(&Slicer::handlePredecessorEdge,
				    this,
				    _1,
				    boost::ref(p),
				    boost::ref(cand),
				    boost::ref(newCands),
				    boost::ref(err),
				    boost::ref(nf)
				    ));
   
    return !err; 
}

/*
 * Process a call instruction, determining whether to follow the
 * call edge (with the help of the predicates) or the fallthrough
 * edge (coloquially referred to as `funlink' thanks to our 
 * departed Arizona alum --- much respect M.L.)
 */
bool
Slicer::handleCall(
    Predicates & p,
    SliceFrame & cur,
    bool & err)
{
    ParseAPI::Block * callee = NULL;
    ParseAPI::Edge * funlink = NULL;
    bool widen = false;

    const Block::edgelist & targets = cur.loc.block->targets();
    Block::edgelist::const_iterator eit = targets.begin();
    for( ; eit != targets.end(); ++eit) {
        ParseAPI::Edge * e = *eit;
        if (e->sinkEdge()) widen = true;
        else if(e->type() == CALL) {
            if (callee && callee != e->trg()) {
                // Oops
                widen = true;
            }
            callee = e->trg();
        } else if(e->type() == CALL_FT) {
           funlink = e;
        }
    }
    
    if(followCall(p, callee, cur)) {
       if (widen) {
          // Indirect call that they wanted us to follow, so widen.
          err = true;
          return true;
       }

       ParseAPI::Block * caller_block = cur.loc.block;
       
       cur.loc.block = callee;
       cur.loc.func = getEntryFunc(callee);
       getInsns(cur.loc);
       
       // Update the context of the slicing frame
       // and modify the abstract regions in its
       // active vector
       if(!handleCallDetails(cur,caller_block)) {
          err = true;
          return false;
       }
    }
    else {
        // Use the funlink
        if(!funlink) {
            // FIXME I am preserving a comment and semantics that
            // I do not understand here, again as of 06697df. Quote:

            // ???
            return false;
        }
        if(!handleDefault(forward,p,funlink,cur,err)) {
            err = true;
            return false;
        }
    }
    return true;
}

/*
 * Builds up a call stack and callee function, and ask
 * the predicate whether we should follow the call (or,
 * implicitly, follow its fallthrough edge instead).
 */
bool
Slicer::followCall(
    Predicates & p,
    ParseAPI::Block * target,
    SliceFrame & cur)
{
    // FIXME quote:
   // A NULL callee indicates an indirect call.
   // TODO on that one...
   
    ParseAPI::Function * callee = (target ? getEntryFunc(target) : NULL);
    
    // cons up a call stack
    stack< pair<ParseAPI::Function *, int> > callStack;
    for(Context::reverse_iterator calls = cur.con.rbegin();
        calls != cur.con.rend(); ++calls)
    {
        if(NULL != calls->func) {
            callStack.push(make_pair(calls->func,calls->stackDepth));
        }
    } 
    // Quote:
        // FIXME: assuming that this is not a PLT function, since I have no
        // idea at present.  -- BW, April 2010

    // Give the predicate an opportunity to accept this call for each
    // of the abstract regions in the active set
    //
    // XXX There is an interesting concern here. What if the predicate
    // would indicate `follow' for one active AbsRegion and `do not
    // follow' for another? What you'd want to do in that case is
    // fork into multiple SliceFrames for absregions that should go
    // one way or the other. This is something that could be done by
    // moving the handleCallDetails() call into this method and
    // modifying the nextCands vector here, as opposed to in
    // handleCall(). 
    // 
    // This issue needs review by a person involved in slicer design.
    // FIXME

    bool ret = false;

    SliceFrame::ActiveMap::iterator ait = cur.active.begin();
    for( ; ait != cur.active.end(); ++ait) {
        ret = ret || p.followCall(callee, callStack, (*ait).first);
    }
    
    return ret;
}

void 
Slicer::shiftAllAbsRegions(
    SliceFrame & cur,
    long stack_depth,
    ParseAPI::Function *callee)
{
    SliceFrame::ActiveMap newMap;

    // fix all of the abstract regions
    SliceFrame::ActiveMap::iterator ait = cur.active.begin();
    for( ; ait != cur.active.end(); ++ait) {
        AbsRegion const& reg = (*ait).first;

        // shortcut -- do nothing if no adjustment is necessary
        if(reg.absloc() == Absloc()) {
            // N.B. doing this the hard way (rather than map.insert()
            //      in case a previous or later iteration transforms
            //      a different AbsRegion to the same as (*ait).first
            vector<Element> & e = newMap[(*ait).first];
            e.insert(e.end(),(*ait).second.begin(),(*ait).second.end());
            continue;
        }

        // Adjust the mapping region, but do not adjust the regions of the
        // elements --- these are maintained to their old values for
        // annotating the slicing graph edges to facilitate substitution
        // in symbolic expansion
        AbsRegion newReg;
        shiftAbsRegion(reg,newReg,stack_depth,callee);

        // just copy the elements
        vector<Element> & e = newMap[newReg];
        e.insert(e.end(),(*ait).second.begin(),(*ait).second.end());
    }
    // and replace
    cur.active = newMap;    
}

/*
 * Adjust the slice frame's context and translates the abstract
 * regions in the active list from caller to callee
 */
bool
Slicer::handleCallDetails(
    SliceFrame & cur,
    ParseAPI::Block * caller_block)
{ 
    ParseAPI::Function * caller = cur.con.front().func;
    ParseAPI::Function * callee = cur.loc.func;

    long stack_depth = 0;
    if(!getStackDepth(caller, caller_block, caller_block->end(), stack_depth))
        return false;

    // Increment the context
    pushContext(cur.con, callee, caller_block, stack_depth);

    // Transform the active abstract regions
    shiftAllAbsRegions(cur,stack_depth,callee);

    return true;
}

/*
 * Properly adjusts the location & context of the slice frame and the
 * AbsRegions of its active elements
 */
bool 
Slicer::handleReturn(
    Predicates & /* p */,
    SliceFrame & cur,
    bool & err)
{
    // Sanity check -- when we pop (in handleReturnDetails),
    // it should not result in context being empty
    //
    // FIXME I duplicated this from the old version; I don't
    //       understand why this doesn't set err = false.
    if(cur.con.size() <= 1)
        return false;

    // Find successor
    ParseAPI::Block * retBlock = NULL;
    
    const Block::edgelist & targets = cur.loc.block->targets();
    Block::edgelist::const_iterator eit = targets.begin();
    for(; eit != targets.end(); ++eit) {
        if((*eit)->type() == CALL_FT) {
            retBlock = (*eit)->trg();
            if ((*eit)->sinkEdge()) {
                cerr << "Weird!" << endl;
            }
            break;
        }
    }
    if(!retBlock) {
        err = true;
        return false;
    }

    // Pops a context and adjusts the abstract regions in `active'
    handleReturnDetails(cur);

    // Fix location given new context
    cur.loc.func = cur.con.front().func;
    cur.loc.block = retBlock;
    getInsns(cur.loc);

    return true;
}

/*
 * Do the actual context popping and active AbsRegion translation
 */
void
Slicer::handleReturnDetails(
    SliceFrame & cur)
{
    long stack_depth = cur.con.front().stackDepth;
    popContext(cur.con);

    assert(!cur.con.empty());

    slicing_printf("\t%s, \n",
        (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
        cur.con.front().stackDepth);

    // Transform the active abstract regions
    shiftAllAbsRegions(cur,-1*stack_depth,cur.con.front().func);
}

bool
Slicer::handleDefault(
    Direction dir,
    Predicates & /*p*/,
    ParseAPI::Edge * e,
    SliceFrame & cur,
    bool & /* err */)
{
    if(dir == forward) {
        cur.loc.block = e->trg();
        getInsns(cur.loc);
    } else {
        cur.loc.block = e->src();
        getInsnsBackward(cur.loc);
    }
    return true;
}

/* ----------------- backwards slicing implementations ------------------ */

bool
Slicer::handleCallBackward(
    Predicates & p,
    SliceFrame const& cand,
    vector<SliceFrame> & newCands,
    ParseAPI::Edge * e,
    bool & /* err */)
{
    // We don't know which function the caller block belongs to,
    // so check each possibility against the predicate.
    //
    // XXX   this suffers the same problem as followCall in the forward
    //       case; the predicates test against only a single abstract
    //       region. What we do here is to build up mappings from
    //       function paths (that will be followed) to sets of abstract
    //       regions, then create SliceFrames with these sets.

    map<ParseAPI::Function *, SliceFrame::ActiveMap > fmap;

    SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
    for( ; ait != cand.active.end(); ++ait) {
        vector<ParseAPI::Function *> follow = 
            followCallBackward(p,cand,(*ait).first,e->src());
        for(unsigned j=0;j<follow.size();++j) {
            fmap[follow[j]].insert(*ait);
        }
    }

    map<ParseAPI::Function *, SliceFrame::ActiveMap >::iterator mit = 
        fmap.begin();
    for( ; mit != fmap.end(); ++mit) {
        ParseAPI::Function * f = (*mit).first;
        SliceFrame::ActiveMap & act = (*mit).second;
    
        SliceFrame nf(cand.loc,cand.con);
        nf.active = act;

        nf.con.push_back(ContextElement(f));
        nf.loc.block = e->src();
        nf.loc.func = f;

        // pop context & adjust AbsRegions
        if(!handleCallDetailsBackward(nf)) {
            // FIXME I have preserved this behavior (returning false if
            //       the current frame can't be adjusted). It seems to
            //       me that we ought to set err = true and continue
            //       processing the rest of the call edges.
            //
            //       This issue needs review by somebody knowledgeable
            //       about the slicer.
            return false;
        }

        getInsnsBackward(nf.loc);
        newCands.push_back(nf);
    } 
    return true;
}

/*
 * FIXME egregious copying
 */
vector<ParseAPI::Function *>
Slicer::followCallBackward(
    Predicates & p,
    SliceFrame const& cand,
    AbsRegion const& reg,
    ParseAPI::Block * caller_block)
{
    stack< pair<ParseAPI::Function *, int> > callStack;  
    for(Context::const_reverse_iterator calls = cand.con.rbegin();
        calls != cand.con.rend(); ++calls)
    {
        if(calls->func) {
            callStack.push(
               std::make_pair(calls->func, calls->stackDepth));
        }
    }
    return p.followCallBackward(caller_block, callStack, reg);
}

bool
Slicer::handleCallDetailsBackward(
    SliceFrame & cur)
{
    ParseAPI::Block * callBlock = cur.loc.block;
    ParseAPI::Function * caller = cur.loc.func;

    Address callBlockLastInsn = callBlock->lastInsnAddr();

    long stack_depth;
    if(!getStackDepth(caller, callBlock, callBlockLastInsn,stack_depth)) {
        return false;
    }

    popContext(cur.con);
    assert(!cur.con.empty());


    slicing_printf("\t%s, %d\n",
        (cur.con.front().func ? cur.con.front().func->name().c_str() : "NULL"),
        cur.con.front().stackDepth);

    // Transform the active abstract regions
    shiftAllAbsRegions(cur,-1*stack_depth,caller);

    return true;
}
    
bool
Slicer::handleReturnBackward(
    Predicates & p,
    SliceFrame const& cand,
    SliceFrame & newCand,
    ParseAPI::Edge * e,
    bool & err)
{
    ParseAPI::Block * callee = e->src();

    // cons up a call stack for the call associated
    // with this return and ask the predicates whether
    // they would have come down this call.
    //
    // FIXME the issue of predicates evaluating only a
    //       single abstract region applies here as well;
    //       see comments in handleCall and handleCallBackward

    if(followReturn(p,cand,callee)) {
        // XXX it is not clear to me why a null callee is an error here
        //     but not if followReturn returns false FIXME
        if(!callee) {
            err = true;
            return false;
        }

        newCand = cand;
        newCand.loc.block = callee;
        newCand.loc.func = getEntryFunc(callee);
        getInsnsBackward(newCand.loc);

        if(!handleReturnDetailsBackward(newCand,cand.loc.block)) {
            err = true;
            return false;
        }
        return true;
    }

    return false;
}

bool
Slicer::handleReturnDetailsBackward(
    SliceFrame & cur,
    ParseAPI::Block * caller_block)
{
    ParseAPI::Function * caller = cur.con.front().func;
    ParseAPI::Function * callee = cur.loc.func;

    long stack_depth;
    if(!getStackDepth(caller,caller_block, caller_block->end(),stack_depth)) {
        return false;
    }
    
    pushContext(cur.con, callee, caller_block, stack_depth);

    // Transform the active abstract regions
    shiftAllAbsRegions(cur,stack_depth,caller);

    return true; 
}

bool
Slicer::followReturn(
    Predicates & p,
    SliceFrame const& cand,
    ParseAPI::Block * source)
{
    ParseAPI::Function * callee = (source ? getEntryFunc(source) : NULL);
    
    stack< pair<ParseAPI::Function *, int> > callStack;
    for(Context::const_reverse_iterator calls = cand.con.rbegin();
        calls != cand.con.rend(); ++calls)
    {
        if(calls->func) {
            callStack.push(
               std::make_pair(calls->func, calls->stackDepth));
        }
    }

    bool ret = false;
    SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
    for( ; ait != cand.active.end(); ++ait) {
        ret = ret || p.followCall(callee,callStack,(*ait).first);
    }
    return ret;
}
    


/* ------------------------------------------- */

Address SliceNode::addr() const { 
  if (a_)
    return a_->addr();
  return 0;
}

bool containsCall(ParseAPI::Block *block) {
  // We contain a call if the out-edges include
  // either a CALL or a CALL_FT edge
  const Block::edgelist &targets = block->targets();
  Block::edgelist::const_iterator eit = targets.begin();
  for (; eit != targets.end(); ++eit) {
    ParseAPI::Edge *edge = *eit;
    if (edge->type() == CALL) return true;
  }
  return false;
}

bool containsRet(ParseAPI::Block *block) {
  // We contain a call if the out-edges include
  // either a CALL or a CALL_FT edge
  const Block::edgelist &targets = block->targets();
  Block::edgelist::const_iterator eit = targets.begin();
  for (; eit != targets.end(); ++eit) {
    ParseAPI::Edge *edge = *eit;
    if (edge->type() == RET) return true;
  }
  return false;
}

static void getInsnInstances(ParseAPI::Block *block,
		      Slicer::InsnVec &insns) {
  Offset off = block->start();
  const unsigned char *ptr = (const unsigned char *)block->region()->getPtrToInstruction(off);
  if (ptr == NULL) return;
  InstructionDecoder d(ptr, block->size(), block->obj()->cs()->getArch());
  while (off < block->end()) {
    insns.push_back(std::make_pair(d.decode(), off));
    off += insns.back().first->size();
  }
}

ParseAPI::Function *getEntryFunc(ParseAPI::Block *block) {
  return block->obj()->findFuncByEntry(block->region(), block->start());
}

// Constructor. Takes the initial point we slice from. 

// TODO: make this function-less interprocedural. That would throw the
// stack analysis for a loop, but is generally doable...
Slicer::Slicer(Assignment::Ptr a,
               ParseAPI::Block *block,
               ParseAPI::Function *func) : 
  a_(a),
  b_(block),
  f_(func),
  converter(true) {
  df_init_debug();
};

Graph::Ptr Slicer::forwardSlice(Predicates &predicates) {

	// delete cache state
  unique_edges_.clear(); 

  return sliceInternal(forward, predicates);
}

Graph::Ptr Slicer::backwardSlice(Predicates &predicates) {
  // delete cache state
  unique_edges_.clear(); 

  return sliceInternal(backward, predicates);
}

bool Slicer::getStackDepth(ParseAPI::Function *func, ParseAPI::Block *block, Address callAddr, long &height) {
  StackAnalysis sA(func);

  StackAnalysis::Height heightSA = sA.findSP(block, callAddr);

  // Ensure that analysis has been performed.

  assert(!heightSA.isTop());
  
  if (heightSA.isBottom()) {
    return false;
  }
  
  height = heightSA.height();
  
  // The height will include the effects of the call
  // Should check the region... 

  //slicing_cerr << "Get stack depth at " << std::hex << callAddr
  //<< std::dec << " " << (int) height << endl;

  return true;
}

void Slicer::pushContext(Context &context,
			 ParseAPI::Function *callee,
			 ParseAPI::Block *callBlock,
			 long stackDepth) {
  slicing_cerr << "pushContext with " << context.size() << " elements" << endl;
  assert(context.front().block == NULL);
  context.front().block = callBlock;

  slicing_cerr << "\t" 
	       << (context.front().func ? context.front().func->name() : "NULL")
	       << ", " 
	       << context.front().stackDepth 
	       << endl;

    context.push_front(ContextElement(callee, stackDepth));
};

void Slicer::popContext(Context &context) {
  context.pop_front();

  context.front().block = NULL;
}

void Slicer::shiftAbsRegion(AbsRegion const&callerReg,
			    AbsRegion &calleeReg,
			    long stack_depth,
			    ParseAPI::Function *callee) {
  if (callerReg.absloc() == Absloc()) {
    // Typed, so just keep the same type and call it a day
    calleeReg = callerReg;
    return;
  }
  else {
    assert(callerReg.type() == Absloc::Unknown);
    
    const Absloc &callerAloc = callerReg.absloc();
    if (callerAloc.type() != Absloc::Stack) {
      calleeReg = AbsRegion(callerAloc);
    }
    else {
      if (stack_depth == -1) {
        // Oops
	calleeReg = AbsRegion(Absloc::Stack);
	return;
      }
      else {
        //slicing_cerr << "*** Shifting caller absloc " << callerAloc.off()
        //<< " by stack depth " << stack_depth 
        //<< " and setting to function " << callee->name() << endl;
	calleeReg = AbsRegion(Absloc(callerAloc.off() - stack_depth,
				     0, // Entry point has region 0 by definition
				     callee));
      }
    }
  }
}

bool Slicer::kills(AbsRegion const&reg, Assignment::Ptr &assign) {
  // Did we find a definition of the same abstract region?
  // TBD: overlaps ins't quite the right thing here. "contained
  // by" would be better, but we need to get the AND/OR
  // of abslocs hammered out.

  if (assign->out().type() != Absloc::Unknown) {
    // A region assignment can never kill
    return false; 
  }

  return reg.contains(assign->out());
}

SliceNode::Ptr Slicer::createNode(Element const&elem) {
  if (created_.find(elem.ptr) != created_.end()) {
    return created_[elem.ptr];
  }
  SliceNode::Ptr newNode = SliceNode::create(elem.ptr, elem.block, elem.func);
  created_[elem.ptr] = newNode;
  return newNode;
}

std::string SliceNode::format() const {
  if (!a_) {
    return "<NULL>";
  }

  stringstream ret;
  ret << "(" << a_->format() << "@" <<
    f_->name() << ")";
  return ret.str();
}

void Slicer::convertInstruction(Instruction::Ptr insn,
				Address addr,
				ParseAPI::Function *func,
                                ParseAPI::Block *block,
				std::vector<Assignment::Ptr> &ret) {
  converter.convert(insn,
		    addr,
		    func,
                    block,
		    ret);
  return;
}

void Slicer::getInsns(Location &loc) {


  InsnCache::iterator iter = insnCache_.find(loc.block);
  if (iter == insnCache_.end()) {
    getInsnInstances(loc.block, insnCache_[loc.block]);
  }
  
  loc.current = insnCache_[loc.block].begin();
  loc.end = insnCache_[loc.block].end();
}

void Slicer::getInsnsBackward(Location &loc) {
    assert(loc.block->start() != (Address) -1); 
    InsnCache::iterator iter = insnCache_.find(loc.block);
    if (iter == insnCache_.end()) {
      getInsnInstances(loc.block, insnCache_[loc.block]);
    }

    loc.rcurrent = insnCache_[loc.block].rbegin();
    loc.rend = insnCache_[loc.block].rend();
}

void Slicer::insertPair(Graph::Ptr ret,
			Direction dir,
			Element const&source,
			Element const&target,
			AbsRegion const& data) 
{
  SliceNode::Ptr s = createNode(source);
  SliceNode::Ptr t = createNode(target);

  EdgeTuple et(s,t,data);
  if(unique_edges_.find(et) != unique_edges_.end()) {
    unique_edges_[et] += 1;
    return;
  }
  unique_edges_[et] = 1;  

  if (dir == forward) {
     SliceEdge::Ptr e = SliceEdge::create(s, t, data);
     ret->insertPair(s, t, e);
  } else {
     SliceEdge::Ptr e = SliceEdge::create(t, s, data);
     ret->insertPair(t, s, e);
  }
}

void
Slicer::widenAll(
    Graph::Ptr g,
    Direction dir,
    SliceFrame const& cand)
{
    SliceFrame::ActiveMap::const_iterator ait = cand.active.begin();
    for( ; ait != cand.active.end(); ++ait) {
        vector<Element> const& eles = (*ait).second;
        for(unsigned i=0;i<eles.size();++i)
            widen(g,dir,eles[i]);
    }
}

void Slicer::widen(Graph::Ptr ret,
		   Direction dir,
		   Element const&e) {
  if (dir == forward) {
    ret->insertPair(createNode(e),
		    widenNode());
    ret->insertExitNode(widenNode());
  }
  else {
    ret->insertPair(widenNode(), createNode(e));
    ret->insertEntryNode(widenNode());
  }
}

SliceNode::Ptr Slicer::widenNode() {
  if (widen_) {
    return widen_;
  }

  widen_ = SliceNode::create(Assignment::Ptr(),
			      NULL, NULL);
  return widen_;
}

void Slicer::markAsEndNode(Graph::Ptr ret, Direction dir, Element &e) {
  if (dir == forward) {    
    ret->insertExitNode(createNode(e));
  }
  else {
    ret->insertEntryNode(createNode(e));
  }
}

void Slicer::fastForward(Location &loc, Address
			 addr) {
  while ((loc.current != loc.end) &&
	 (loc.addr() < addr)) {
    loc.current++;
  }
  assert(loc.current != loc.end);
  assert(loc.addr() == addr);
}

void Slicer::fastBackward(Location &loc, Address addr) {
    while ((loc.rcurrent != loc.rend) &&
	 (loc.addr() > addr)) {
    loc.rcurrent++;
  }
    
  assert(loc.rcurrent != loc.rend);
  assert(loc.addr() == addr);  
}

void Slicer::cleanGraph(Graph::Ptr ret) {
  slicing_cerr << "Cleaning up the graph..." << endl;
  // Clean the graph up
  
  // TODO: make this more efficient by backwards traversing.
  // For now, I know that we're generating graphs with tons of
  // unnecessary flag sets (which are immediately killed) and so
  // we don't have long non-exiting chains, we have "fuzz"
  
  NodeIterator nbegin, nend;
  ret->allNodes(nbegin, nend);
  
  std::list<Node::Ptr> toDelete;
  unsigned numNodes = 0;
  for (; nbegin != nend; ++nbegin) {
	  expand_cerr << "NodeIterator in cleanGraph: " << (*nbegin)->format() << endl;
      numNodes++;
      SliceNode::Ptr foozle =
          boost::dynamic_pointer_cast<SliceNode>(*nbegin);
      //cerr << "Checking " << foozle << "/" << foozle->format() << endl;
      if ((*nbegin)->hasOutEdges()) {
          slicing_cerr << "\t has out edges, leaving in" << endl;
      
          // This cleans up case where we ended a backward slice
          // but never got to mark the node as an entry node
          if (!(*nbegin)->hasInEdges()) {
	          ret->markAsEntryNode(foozle);
          }
          continue;
      }
      if (ret->isExitNode(*nbegin)) {
          slicing_cerr << "\t is exit node, leaving in" << endl;
          // A very odd case - a graph of 1 node. Yay!
          if (!(*nbegin)->hasInEdges()) {
	          ret->markAsEntryNode(foozle);
          }
          continue;
      }
      slicing_cerr << "\t deleting" << endl;
      toDelete.push_back(*nbegin);
  }

  for (std::list<Node::Ptr>::iterator tmp =
	   toDelete.begin(); tmp != toDelete.end(); ++tmp) {
      ret->deleteNode(*tmp);
  }
  slicing_cerr << "\t Slice has " << numNodes << " nodes" << endl;
}

ParseAPI::Block *Slicer::getBlock(ParseAPI::Edge *e,
				   Direction dir) {
  return ((dir == forward) ? e->trg() : e->src());
}

bool Slicer::isWidenNode(Node::Ptr n) {
  SliceNode::Ptr foozle =
    boost::dynamic_pointer_cast<SliceNode>(n);
  if (!foozle) return false;
  if (!foozle->assign()) return true;
  return false;
}

void Slicer::insertInitialNode(GraphPtr ret, Direction dir, SliceNode::Ptr aP) {
  if (dir == forward) {
    // Entry node
    ret->insertEntryNode(aP);
  }
  else {
    ret->insertExitNode(aP);
  }
}
 
void Slicer::constructInitialFrame(
    Direction dir,
    SliceFrame & initFrame)
{
    initFrame.con.push_front(ContextElement(f_));
    initFrame.loc = Location(f_,b_);

    if(dir == forward) {
        Element oe(b_,f_,a_->out(),a_);
        initFrame.active[a_->out()].push_back(oe);
    } else {
        vector<AbsRegion> & inputs = a_->inputs();
        vector<AbsRegion>::iterator iit = inputs.begin();
        for ( ; iit != inputs.end(); ++iit) {
            Element ie(b_,f_,*iit,a_);
            initFrame.active[*iit].push_back(ie);
        }
    }

    if(dir == forward) {
        initFrame.loc.fwd = true;
        getInsns(initFrame.loc);
        fastForward(initFrame.loc, a_->addr());
    } else {
        initFrame.loc.fwd = false;
        getInsnsBackward(initFrame.loc);
        fastBackward(initFrame.loc, a_->addr());
    }
}

void
Slicer::DefCache::merge(Slicer::DefCache const& o)
{
    map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
    for( ; oit != o.defmap.end(); ++oit) {
        AbsRegion const& r = oit->first;
        set<Def> const& s = oit->second;
        defmap[r].insert(s.begin(),s.end());
    }
}

void
Slicer::DefCache::replace(Slicer::DefCache const& o)
{   
    // XXX if o.defmap[region] is empty set, remove that entry
    map<AbsRegion, set<Def> >::const_iterator oit = o.defmap.begin();
    for( ; oit != o.defmap.end(); ++oit) {
        if(!(*oit).second.empty())
            defmap[(*oit).first] = (*oit).second;
        else
            defmap.erase((*oit).first);
    }
}

void
Slicer::DefCache::print() const {
    map<AbsRegion, set<Def> >::const_iterator it = defmap.begin();
    for( ; it !=defmap.end(); ++it) {
        slicing_printf("\t\t%s ->\n",(*it).first.format().c_str());
        set<Def> const& defs = (*it).second;
        set<Def>::const_iterator dit = defs.begin();
        for( ; dit != defs.end(); ++dit) {
            slicing_printf("\t\t\t<%s,%s>\n",
                (*dit).ele.ptr->format().c_str(),
                (*dit).data.format().c_str());
        }
    }
}
