/**
 * Copyright (c) 2005 by Kevin Bierhoff
 */
package edu.cmu.cs.l3.canon;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.Vector;

import edu.cmu.cs.l3.tree.IRCJump;
import edu.cmu.cs.l3.tree.IRJump;
import edu.cmu.cs.l3.tree.IRStatement;

/**
 * @author Kevin
 *
 */
public class BlockFlowGraph {

	protected Vector blocks;
	
	/** String (block label) to set of ints (predecessor block numbers) */
	protected HashMap preds;
	
	/** String (block label) to set of ints (successor block numbers) */
	protected HashMap succs;
	
	/** String (block label) to block number */
	protected HashMap labelsToBlocks;
	
	/** Numbers of blocks that jump to unknown targets */
	protected HashSet exitingBlocks;

	/**
	 * Creates the flow graph for a given set of blocks.
	 * @param blocks
	 */
	public BlockFlowGraph(Vector blocks) {
		super();
		this.blocks = blocks;

		initFlowGraph();
	}
	
	/**
	 * Returns the predecessors as a set of Integers (indices of blocks). <b>Do not change that set!</b>
	 * @param b
	 * @return The predecessors as a set of Integers 
	 */
	public Set getPreds(Block b) {
		Set result = (Set) preds.get(b.getLabel().toString());
		if(result == null) {
		    //System.out.println("No predecessors for block with label " + b.getLabel().toString());
			result = new HashSet();
		}
		return result;
	}
	
	/**
	 * Returns the successors as a set of Integers (indices of blocks). <b>Do not change that set!</b>
	 * @param b
	 * @return The successors as a set of Integers. 
	 */
	public Set getSuccs(Block b) {
		Set result = (Set) succs.get(b.getLabel().toString());
		if(result == null) {
		    //System.out.println("No successors for block with label " + b.getLabel().toString());
			result = new HashSet();
		}
		return result;
	}
	
	/**
	 * Returns the index of a block with a given label.
	 * @param label
	 * @return The index of a block with a given label.
	 */
	public int getBlockIndex(String label) {
		Integer result = (Integer) labelsToBlocks.get(label);
		if(result == null) return -1;
		return result.intValue();
	}
	
	/**
	 * Returns the index of a block.
	 * @param b
	 * @return The index of a block.
	 */
	public int getBlockIndex(Block b) {
		return getBlockIndex(b.getLabel().toString());
	}
	
	/**
	 * This operation will eliminate any unreachable blocks in the flow graph.
	 * The flow graph will be recomputed in case any blocks could be removed.
	 * @return <code>True</code> if any blocks were removed, <code>false</code> otherwise.
	 */
	public boolean eliminateUnreachableBlocks() {
		boolean result;
		
		HashSet seen = new HashSet();
		reachBlock(getBlock(0), seen);
		result = blocks.retainAll(seen);
		if(result) recompute();
		return result;
	}
	
	/** Helper for {@link #eliminateUnreachableBlocks()}. */
	private void reachBlock(Block b, Set seen) {
		if(seen.contains(b)) return;
		seen.add(b);
		for(Iterator it = getSuccs(b).iterator(); it.hasNext(); ) {
			Block cur = getBlock((Integer) it.next());
			reachBlock(cur, seen);
		}
	}
	
	/**
	 * Returns the block with a given index.
	 * @param index
	 * @return The block with the given index.
	 */
	public Block getBlock(int index) {
		return (Block) blocks.get(index);
	}
	
	/**
	 * Returns the number of blocks in the graph.
	 * @return The number of blocks in the graph.
	 */
	public int getBlockCount() {
		return blocks.size();
	}
	
	/**
	 * Returns the block with a given index.
	 * @param index
	 * @return The block with the given index.
	 */
	protected Block getBlock(Integer index) {
		return getBlock(index.intValue());
	}
	
	/**
	 * Determines whether the block with the given index can exit the function (the given set of blocks)
	 * @param index Index of a known block.
	 * @return <code>True</code> if the given block can jump to an unknown block, <code>false</code> otherwise.
	 */
	public boolean canExit(int index) {
		return exitingBlocks.contains(new Integer(index));
	}
	
	/**
	 * Determines whether the given block will invariably leave the function (given set of blocks).
	 * @param b A block.
	 * @return <code>True</code> if all jumps from the block go to unknown blocks, <code>false</code> otherwise.
	 */
	public boolean mustExit(Block b) {
		return canExit(getBlockIndex(b)) && getSuccs(b).isEmpty();
	}
	
	/**
	 * Returns the exiting blocks.
	 * @return The exiting blocks.
	 */
	public Set getExitingBlocks() {
		return exitingBlocks;
	}
	
	/**
	 * Call this method to recompute the flow graph. Override this method <b>and call the inherited
	 * implementation</b> if you have any data structures that depend of the flow graph.
	 */
	protected void recompute() {
		initFlowGraph();
	}
	
	/**
	 * This method recomputes the flow graph.
	 */
	protected void initFlowGraph() {
		labelsToBlocks = new HashMap();
		preds = new HashMap();
		succs = new HashMap();
		exitingBlocks = new HashSet();
		
	    // set up labelsToBlocks
		for(int i = 0; i < blocks.size(); i++) {
		    Block block = ((Block)blocks.get(i));
		    labelsToBlocks.put(block.getLabel().toString(), new Integer(i));
		}
		
		for(int i = 0; i < blocks.size(); i++) {
		    Block block = ((Block)blocks.get(i));

		    IRStatement tempJump = block.getJump();
		    if(tempJump instanceof IRJump) {
				IRJump jump = (IRJump) tempJump;
				String targetName = jump.getTarget().toString();
				
				// update predecessors
				Set bpreds = (Set)preds.get(targetName);
				if(bpreds == null) {
				    bpreds = new HashSet();
				    preds.put(targetName, bpreds);
				}
				bpreds.add(new Integer(i));
				
				// set successors (once and for all)
				Set bsuccs = new HashSet();
				if(labelsToBlocks.get(targetName) != null)
					// jumps to known block --> set that block as successor
					bsuccs.add(labelsToBlocks.get(targetName));
				else
					// jumps to unknown target --> exit
					exitingBlocks.add(new Integer(i));
				succs.put(block.getLabel().toString(), bsuccs);
		    } 
		    else if(tempJump instanceof IRCJump) {
				IRCJump jump = (IRCJump) tempJump;

				//true label
				Set bpreds = (Set)preds.get(jump.getTrueLabel().toString());
				if(bpreds == null) {
				    bpreds = new HashSet();
				    preds.put(jump.getTrueLabel().toString(), bpreds);
				}
				bpreds.add(new Integer(i));
				
				//false label
				bpreds = (Set)preds.get(jump.getFalseLabel().toString());
				if(bpreds == null) {
				    bpreds = new HashSet();
				    preds.put(jump.getFalseLabel().toString(), bpreds);
				}
				bpreds.add(new Integer(i));

				// set successors 
				Set bsuccs = new HashSet();
				
				Integer index = (Integer) labelsToBlocks.get(jump.getTrueLabel().toString());
				if(index != null)
					// jumps to known block --> set that block as successor
					bsuccs.add(index);
				else
					// jumps to unknown target --> exit
					exitingBlocks.add(new Integer(i));

				index = (Integer) labelsToBlocks.get(jump.getFalseLabel().toString());
				if(index != null) 
					// jumps to known block --> set that block as successor
					bsuccs.add(index);
				else
					// jumps to unknown target --> exit
					exitingBlocks.add(new Integer(i));
				
				succs.put(block.getLabel().toString(), bsuccs);
		    }
		    
		}
		
	}

}
