package Sequenic.T2ext.Selection;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

import Sequenic.Graph.Vertex;
import Sequenic.T2ext.Instrumenter.CFG;
import Sequenic.T2ext.Instrumenter.Node;

/**
 * This class is Deprecated, the Ball Partial algorithm is broken.
 * A working implementation of the Rothermel-Harrold algorithm is in its own class, RothermelHarrold.
 * A working implementation of the Ball Partial algorithm can be obtained through InterclassGraph.
 * 
 * Contains two algorithms for producing sets of dangerous edges, Rothermel-Harrold and Ball's partial reachability algorithm. 
 * If an algorithm returns null, that means all tests that cover the method need to be selected.
 * 
 * This class is not thread safe. 
 * We suggest wrapping instances in ThreadLocal when necessary.
 * 
 * @author Jeiel Schalkwijk
 *
 */
@Deprecated
public class DifferenceAnalyzer {
	
	private final boolean useBallPartial;
		
	/* If useBallPartial is false, then the Rothermel-Harrold algorithm is used,
	 * otherwise Ball's partial reachability algorithm is used.
	 */
	private DifferenceAnalyzer(boolean useBallPartial) {
		this.useBallPartial = useBallPartial;
	}
			
	/** 
	 * Returns a set of dangerous edges in the original method CFG.
	 * All tests traversing these edges must be selected.
	 * 
	 * If the startNodes of the CFG are not lexically equivalent it returns null 
	 * and all tests that cover the method need to be selected.
	 * 
	 */
	public ISelector getDangerousEdges(CFG orig, CFG mod)
	{
		Node origStart = orig.getStartNode();
		Node modStart = mod.getStartNode();
				
		if(!origStart.lexEquivalent(modStart)) 
		{
			// NOTE: The visit methods should only be called on lexically equivalent node pairs.
			// Also, if the start nodes are different, then all paths are modification-traversing.
			return ISelector.ALWAYS;
		}
		
		//Clear markings and dangerous edges from previous run
		markings.clear();
		dangerousEdges.clear();
				
		if(useBallPartial) 
		{
			//Invoke the BallPartial algorithm to fill the list of dangerous edges.
			visitBallPartial(origStart,modStart, true);
			
			// If the starting node pair is not in Vaccept, then all paths are modification-traversing.
			if(!inAccept(origStart,modStart)) 
				return ISelector.ALWAYS;		
			
			// If the pair is in Vaccept just return dangerousEdges, same as RH.
			
		} else { 
	
    		//Invoke the RH algorithm to fill the list of dangerous edges.
    		visitRH(origStart,modStart, true);
		}
				
		return getPathSelector(modStart.getId());
	}	
	
	
	/**
	 * This is the Rothermel-Harrold algorithm, it performs a DFS walk of the CFG.
	 * 
	 * NOTE: Pre-condition to calling visitRH:
	 * 1) For every outgoing edge in orig, there is a similarly labeled outgoing edge in mod
	 * 
	 * This pre-condition can be satisfied by ensuring that:
	 * 1) compare is only invoked if orig is lexically equivalent to mod, AND
	 * 2) Two lexically equivalent nodes have the same set of outgoing labels.
	 */
	private void visitRH(Node orig, Node mod, boolean startNodes) 
	{
		mark(orig,mod,MARK_VISITED);
		
		for(Entry<String, Vertex> kv : orig.childEdges().entrySet()) 
		{
			Node origChild = (Node) kv.getValue();
			Node modChild  = (Node) mod.getChild(kv.getKey());
			
			if(!isVisited(origChild, modChild)) 
			{
				//If a pair of nodes are not yet visited then they are either:				
				if(origChild.lexEquivalent(modChild)) {
					
					// (1) Lexically equivalent, just not yet visited
					// So we visit them.
					visitRH(origChild,modChild, false);
					
					//Also relabel if children don't have same id
					relabelIfNeeded(orig.getId() ,origChild.getId(), modChild.getId());
	
				} else {
					
					// (2) Lexically different, i.e. we have discovered a modified entity in the CFG.
					// The paths that follow are traversal will be modification-traversing.
					// So we mark the corresponding edge in the original CFG as dangerous.
					markDangerous(orig,origChild);
				}
			}
		}
	}
	
	
	
	/** 
	 * An implementation of Thomas Ball's partial reachability algorithm.
	 * This algorithm subsumes the Rothermel-Harrold algorithm, but has the same complexity.
	 * 
	 * The difference in short:
	 * If C is not equivalent with C', then R-H will mark (N,C) as dangerous.
	 * I.e. all reachable edges directly leading to a modified entity are dangerous.
	 * 
	 * BallPartial will only mark an edge (N,C) as dangerous if there is a sibling edge (N,D) that 
	 * is not dangerous.
	 * In absence of such a sibling we can conclude that all paths covering N will ultimately 
	 * lead to a modified entity and hence we do not need to mark (N,C) as dangerous, even though it is.
	 * 
	 * Instead we can mark the edge leading to N, i.e. (X,N), as dangerous. 
	 * But only, of course, if there is a sibling edge (X,M) which is not dangerous.  
	 * 
	 * BallPartial subsumes R-H: Any execution path that covers an edge that is BP-dangerous 
	 * must necessarily also cover an edge that is R-H-dangerous.
	 * 
	 * Moreover, as Ball proves, a path that covers an R-H-dangerous path, but not a BP-dangerous path
	 * is not modification-traversing. I.e. BallPartial is more precise.
	 * 
	 * However R-H is already very precise. It will only select non-modification-traversing tests
	 * under pathological (and rare in practice) conditions, specifically the multiply-visited-node condition.
	 * 
	 */
	private void visitBallPartial(Node orig, Node mod, boolean startNodes) 
	{	
		if(orig.children().isEmpty()) 
		{
			// Base case: Lexically equivalent nodes without children are in Vaccept.
			mark(orig, mod, MARK_ACCEPT);
			System.out.println("accept: "+orig.getId()+" - "+mod.getId());
			return;
		}
		
		mark(orig, mod, MARK_VISITED);
		System.out.println("visited: "+orig.getId()+" - "+mod.getId());
		
		Set<Node> childrenNotInAccept = new HashSet<Node>();
		
		for(Entry<String, Vertex> kv : orig.childEdges().entrySet()) 
		{
			Node origChild = (Node) kv.getValue();
			Node modChild  = (Node) mod.getChild(kv.getKey());
			
			if(!isVisited(origChild, modChild) && origChild.lexEquivalent(modChild)) {
				System.out.println("!isVisited: "+origChild.getId()+" - "+modChild.getId());
				//Visit lexically equivalent node pairs
				visitBallPartial(origChild,modChild, false);
			} else {
				System.out.println("isVisited: "+origChild.getId()+" - "+modChild.getId());
			}
			
			if(inAccept(origChild, modChild)) 
			{
				System.out.println("inAccept: "+origChild.getId()+" - "+modChild.getId());
				
				//Inductive case: A node with a child in Vaccept is also in Vaccept.
				updateMarkingToAccept(orig,mod);
				
				//Only relabel edges from Vaccept to Vaccept
				// Do not relabel edges leaving Vaccept: those are dangerous
				// Do not relabel edges outside Vaccept: an earlier edge on the path must be dangerous
				relabelIfNeeded(orig.getId() ,origChild.getId(), modChild.getId());
			} else {
				System.out.println("!inAccept: "+origChild.getId()+" - "+modChild.getId());
				//The child is not in Vaccept
				childrenNotInAccept.add(origChild);
			}			
		}
		
		if(inAccept(orig,mod)) 
		{	
			//Because this node is in Vaccept the edges to children not in Vaccept are dangerous.
			// (By definition, edges from a node in Vaccept to a node not in Vaccept are dangerous.)
			for (Node n : childrenNotInAccept) {
				System.out.println("dangerous: "+orig.getId()+" : "+n.getId());
				markDangerous(orig,n);
			}
		}
	}
	

		
	/** This marks the node _Mark as visited by the node _Visited
	 */	
	private void mark(Node _Mark, Node _Visited, Object marking) 
	{
		/*			 
		 * Multiply visited nodes are those marked as visited by multiple nodes.
		 * These are rare: _Mark will most likely only ever be marked as visited 
		 * by a single node (the one currently referenced as _Visited).
		 * 
		 * In the common case there will be no previous marking.
		 * m will be null and we will use the cheap singletonMap.
		 */
		Map<Node,Object> m = markings.put(_Mark, Collections.singletonMap(_Visited, marking));
		
		//The uncommon case
		if(m!=null) 
		{
			if(m.size()==1)  //m is still an immutable singleton map, so make it mutable.
				m = new HashMap<Node, Object>(m);
			m.put(_Visited, marking);
			markings.put(_Mark, m);
		}
	}

	
	
	/** Returns true if node _Mark is marked as visited by _Visited
	 */
	private boolean isVisited(Node _Mark, Node _Visited) 
	{
		Map<Node,Object> m = markings.get(_Mark);
		return m!=null
			&& m.containsKey(_Visited);
	}
	


	/*=============================
	 *  WHEN IS A NODE IN Vaccept?
	 *=============================
	 * 
	 * Whether a node C is in Vaccept or not will depend on which node C' it is being compared to.
	 * So we cannot say whether a node is in Vaccept or not, only whether a NODE PAIR is in Vaccept.
	 * 
	 * Consider a multiply visited node C with no children that is visited by C' and X':
	 * If it is lex. equiv. to C', but not to X', then in the intersection graph
	 * (C,C') will be an accept node, but (C,X') will be a reject node.
	 * 
	 * Now consider two different unmodified parent nodes N and M, each with a single child.
	 * Suppose that in the original CFG they are both parents of C, 
	 * but in the modified CFG N is the parent of C' and M the parent of X'.
	 * 
	 * (N,C') is in Vaccept, but (M,X') is not.
	 */

	
	/** Puts (orig,mod) in Vaccept, see Ball's paper for more information.
	 * 
	 * Intuitively: (orig,mod) is in Vaccept if and only if a non-modification traversing path
	 * that visits orig in the original CFG is possible by visiting mod in the modified CFG.
	 * 
	 * If orig and mod are not lexically equivalent, then (orig,mod) is not in Vaccept.
	 * If none of the children of (orig,mod) are in Vaccept, then neither is (orig,mod).  
	 */
	private void updateMarkingToAccept(Node orig, Node mod) 
	{
		/* Note this method presumes that orig has already been marked as visited by mod using 
		 * markVisited, so markings.get(orig) is a Set containing the mapping 
		 * 'mod: MARK_VISITED' or 'mod: MARK_ACCEPT'.
		 */
		Map<Node,Object> m = markings.get(orig);
		if(m.get(mod)==MARK_VISITED) {
			if(m.size()==1) //m is the immutable singletonMap containing mod: MARK_VISITED.
				markings.put(orig,Collections.singletonMap(mod, MARK_ACCEPT));
			else 
				m.put(mod, MARK_ACCEPT);
		} //else m.get(mod)==MARK_ACCEPT, so do nothing.
	}

		
	/** Returns true if (orig,mod) has been put in Vaccept. 
	 */
	private boolean inAccept(Node orig, Node mod) 
	{
		Map<Node,Object> m = markings.get(orig);
		return m != null
			&& m.get(mod) == MARK_ACCEPT;
	}		

	/* Usage of markings: 
	 *     markings.get(N).containsKey(M) ---> N is M-visited
	 *     markings.get(N).get(M) != null ---> (N,M) in Vaccept
	 */
	private final Map<Node,Map<Node,Object>> markings = new HashMap<Node, Map<Node,Object>>();
			
	private static final Object MARK_VISITED = null;
	private final Object MARK_ACCEPT = this;	

	private Map<Object,Integer> relabel = new HashMap<Object, Integer>();
	private final ArrayList<Object> dangerousEdges = new ArrayList<Object>();
	
	/** Mark the edge from src to target as being dangerous.
	 */
	private void markDangerous(Node src, Node target)
	{
		dangerousEdges.add( hashCodeEqObj(
								(src.getId() << 16 ) | target.getId()));
	}
	
	private void relabelIfNeeded(int orig, int origChild, int modChild)
	{
		if(origChild!=modChild) 
		{
			Object key = hashCodeEqObj( (orig << 16 ) | origChild);
			
			//Can not relabel the same edge to two different modChilds
			//In this case retesting is needed, even if the path is not modification-traversing
			if(relabel.containsKey(key) && relabel.get(key).intValue()!=modChild) {
				modChild = -1;
			}
			relabel.put(key, modChild);
		}
			
	}

	
	private ISelector getPathSelector(int modStartId) {
		throw new Error("Not implemented, deprecated, use RothermelHarrold or InterclassGraph");
		
//		Map<Object, Integer> relabel = this.relabel;
//		if(relabel.isEmpty())
//			relabel = Collections.emptyMap();
//		else 
//			this.relabel = new HashMap<Object, Integer>();
//		switch (dangerousEdges.size()) {
//		case 0:
//			return newPathSelector( Collections.emptySet(), relabel, modStartId );
//		case 1:
//			return newPathSelector( Collections.singleton( dangerousEdges.get(0)), relabel, modStartId );
//		default:
//			return newPathSelector( new HashSet<Object>(dangerousEdges), relabel, modStartId );
//		}
	}
	
//	private static final PathSelector newPathSelector(final Set<Object> dangerousEdges, 
//													  final Map<Object,Integer> relabel,
//													  final int modStartId) {
//		return new PathSelector() {
//			
//			public boolean selectPath(int[] path)
//			{
//				if(path.length>1) 
//					for(int i = 1; i<path.length; i++)
//						if(isDangerous( (path[i-1] << 16) | path[i]  ))
//							return true;
//				
//				//if path.length <2 or none of the edges was dangerous
//				return false;
//			}
//			
//			public int[] selectAndUpdate(int[] path)
//			{
//				switch (path.length) {
//				case 0:
//					return path;
//				case 1:
//					return path[0]==modStartId ? path : new int[] {modStartId};
//				default:
//					if(relabel.isEmpty())
//						return selectPath(path) ? null : path;
//					
//					int[] newPath = new int[path.length];
//					System.arraycopy(path, 0, newPath, 0, path.length);
//					int e = path[0];
//					if(e!=modStartId) 
//					{
//						newPath[0] = modStartId;
//						path = newPath;
//					}
//					for(int i = 1; i<newPath.length; i++) 
//					{
//						e = (e << 16) | newPath[i];
//						if(isDangerous(e))
//							return null;
//						else if(relabel.containsKey(this)) 
//						{
//							newPath[i] = relabel.get(this).intValue();
//							path = newPath;
//							if(newPath[i]==-1) { 
//								//-1: when relabeling not possible, e.g. one node in orig replaced by two nodes in mod.
////								return null; 
//							}
//						}	
//					}
//					return path;
//				}
// 
//			}
//			
//			/* Some trickery to avoid creating a new object for each edge.
//			 * This allows us to simply use set.contains(this) repeatedly with this object,
//			 * by using the property of newHashCodeEqObject objects that: equal hashCodes -> equality.
//			 */
//			private 								int edge;
//			public int hashCode(){ 					return edge;				}
//			public boolean equals(Object obj){		return edge==obj.hashCode();}
//			
//			private boolean isDangerous(int edge) { this.edge = edge; 
//													return dangerousEdges.contains(this); }
//			
//			public String toString(){ return "Dangerous Edges: "+dangerousEdges.toString()+" relabel: "+relabel.toString(); }
//		};
//	}
	
	/**
	 * This will return a new Object with the given hashCode.
	 * The equals method is overriden so that it will return true 
	 * when compared to any Object with the same hashCode.
	 * 
	 * Note that the contract of equals will only be satisfied if the other object
	 * also overrides equals in the same manner.
	 * 
	 * I.e. a.equals(b) if and only if b.equals(a), thus the other object must have a 
	 * similarly defined equals method.
	 * 
	 * @author Jeiel Schalkwijk
	 *
	 */
	private static final Object hashCodeEqObj(final int hashCode) {
		return new Object() {
			public int hashCode(){ 					return hashCode;				}
			public boolean equals(Object obj){		return hashCode==obj.hashCode();}
			
			public String toString(){				return "("+(hashCode >>> 16)+","+(hashCode & 65535)+")"; }
		};
	}
	
	
		
}