/** For each local, approximate the max depth it appears at.
 *
 * Roughly steal the approach from dava.toolkits.base.finders.CycleFinder
 * to find loops in a JimpleBody. As opposed to Dava, we're *not* trying to be
 * precise.
 *
 * Blah.
 *
 * @author Kacper Wysocki
 */

package soot.toolkits.scalar;
import soot.*;
import soot.util.*;
import java.util.*;
import soot.tagkit.*;
import soot.options.*;
import soot.toolkits.graph.*;

public class NestDepth{
	/** For each unit, find the nesting depth.
	 * Also, store the max depth for this local, and the total weight.
	 * Arguably, the latter has no business being in the NestDepth class, but
	 * it saves me from spinning through the body once more.
	 */
	HashMap unitToDepth, localToDepth, localToWeight;

	public NestDepth(Body b){
		nestDepths(new BetterMutableGraph(new ExceptionalUnitGraph(b)), b);
	}
	public NestDepth(UnitGraph cfg){
		nestDepths(new BetterMutableGraph(cfg), cfg.getBody());
	}

	private void nestDepths(BetterMutableGraph cfg, Body b){
		int depth = 0;
		if(Options.v().verbose()){
			G.v().out.println(
				"[NestDepth]Processing method " +
				b.getMethod().getName());
		}
		Chain units = b.getUnits();
		unitToDepth = new HashMap(units.size()*2 + 1);
		localToDepth = new HashMap(b.getLocals().size()*2 + 1);
		localToWeight= new HashMap(b.getLocals().size()*2 + 1);
		// init everything to depth 0
		Iterator uit = units.iterator();
		while(uit.hasNext()){
			unitToDepth.put(uit.next(), new Integer(depth));
		}
		uit = b.getLocals().iterator();
		while(uit.hasNext()){
			Object u= uit.next();
			localToDepth.put(u, new Integer(depth));
			localToWeight.put(u, new Integer(0));
		}

		// for all nestings
		List components = BetterMutableGraph.scComponents(cfg);
		while(!components.isEmpty()){
			depth++;
			IterableSet nodes = new IterableSet();
			// for all strongly connected components
			Iterator cit = components.iterator();
			while(cit.hasNext()){
				nodes.clear();
				nodes.addAll((List) cit.next());
				// anything appearing in this component should have this depth
				uit = nodes.iterator();
				while(uit.hasNext()){
					Unit u = (Unit) uit.next();
					int olddepth = 0;
					olddepth = ((Integer)unitToDepth.get(u)).intValue();
					unitToDepth.put(u,new Integer(depth>olddepth?depth:olddepth));
					Iterator udit = u.getUseAndDefBoxes().iterator();
					while(udit.hasNext()){
						Value v = ((ValueBox)udit.next()).getValue();
						if(v instanceof Local){
							olddepth = ((Integer)localToDepth.get(v)).intValue();
							localToDepth.put(u,new Integer(depth>olddepth?depth:olddepth));
							int weight = ((Integer)localToWeight.get(v)).intValue();
							weight += Math.pow(10,depth); // Chaitin says 10^depth, Chow says depth.
							localToWeight.put(v,new Integer(weight));
						}
					}
				}
				// remove the entry points for this component
				Iterator epit = getEntryPoints(nodes,cfg).iterator();
				while(epit.hasNext()){
					cfg.removeNode(epit.next());
				}
			}
			components = BetterMutableGraph.scComponents(cfg);
		}
	}

	public int depthOfUnit(Unit u){
		/*
		if(unitToDepth == null)
			throw new RuntimeException(
					"No mapping of units to depths for this body." +
					"Has the analysis been run on this body yet?");
		*/
		Integer depth = (Integer)unitToDepth.get(u);
		if(depth == null)
			throw new RuntimeException(
					"This unit has no depth!");
		return depth.intValue();
	}

	public int depthOfLocal(Local l){
		Integer depth = (Integer)localToDepth.get(l);
		if(depth == null)
			throw new RuntimeException(
					"This local has no depth!");
		return depth.intValue();
	}

	public int weightOfLocal(Local l){
		return ((Integer)localToWeight.get(l)).intValue();
	}

	/** Find the entry points of a strongly connected component.
	 * See dava for origins */
	private static IterableSet getEntryPoints(
			IterableSet nodeList, DirectedGraph cfg
			){
		IterableSet entryPoints = new IterableSet();
		Iterator it = nodeList.iterator();
		while (it.hasNext()) {
			Object u = it.next();
			Iterator pit = cfg.getPredsOf(u).iterator();
			while (pit.hasNext()) {
				Object po = pit.next();
				if (!nodeList.contains(po)) {
					entryPoints.add(u);
					break;
				}
			}
		}
		return entryPoints;
	}


		/** Find the entry edges of a strongly connected component. */
	private static IterableSet getEntryEdges(
			IterableSet nodeList, DirectedGraph cfg
			){
		IterableSet entryEdges = new IterableSet();
		Iterator it = nodeList.iterator();
		while (it.hasNext()) {
			Unit u = (Unit) it.next();
			Iterator pit = cfg.getPredsOf(u).iterator();
			while (pit.hasNext()) {
				Object po = pit.next();
				if (!nodeList.contains(po)) {
					NodePair np = new NodePair(u,(Unit)po);
					entryEdges.add(np);
					if(Options.v().verbose()){
						G.v().out.println("Adding edge");
					}
				}
			}
		}
		return entryEdges;
	}
}
/* a node pair, commonly called an edge */
class NodePair {
	Unit out,in;
	NodePair(Unit from, Unit to){
		this.out = from;
		this.in = to;
	}
}

class NestDepthDriver extends BodyTransformer {
	public static void main(String[] args){
		Pack jtp = soot.PackManager.v().getPack("jtp");
		jtp.add(new Transform("jtp.nd", new NestDepthDriver()));
		soot.Main.main(args);
	}

	protected void internalTransform(Body b, String phase, Map opts){
		NestDepth nd = new NestDepth(b);
		Iterator bit = b.getUnits().iterator();
		while(bit.hasNext()){
			Unit u = (Unit) bit.next();
			Integer depthI = (Integer)nd.unitToDepth.get(u);
			if(u instanceof IdentityUnit)
				continue;
			if(depthI==null)
				throw new RuntimeException("Unit (" + u + ") has no depth!");
			u.addTag(
				new IntegerConstantValueTag(depthI.intValue()));
			//System.out.println("Tagging (" +u + ") with depth " + depth);
		}
	}
}