content: package edu.cmu.hcii.whyline.analysis;
  
  import java.util.*;
  
  import edu.cmu.hcii.whyline.bytecode.*;
  import edu.cmu.hcii.whyline.trace.Trace;
  import gnu.trove.TLongHashSet;
  
  /**
   * @author Andrew J. Ko
   *
   */
  public final class ValueSourceAnalyzer {
  
  	private static int DEBUG = 0;
  	
  	private static class InstructionTypesPair {
  		
  		private final Instruction inst;
  		private final ValueSource potentialValue;
  
  		public InstructionTypesPair(Instruction inst, ValueSource potentialValue) {
  			
  			this.inst = inst;
  			this.potentialValue = potentialValue;
  			
  			assert inst != null;
  			
  		}
  		
  		public int hashCode() { return inst.hashCode() + (potentialValue.type == null ? 0 : potentialValue.type.hashCode()); }
  		public boolean equals(Object o) { return o instanceof InstructionTypesPair && ((InstructionTypesPair)o).inst == inst && ((InstructionTypesPair)o).potentialValue.equals(potentialValue); }
  		
  	}
  	
  	private static void debug(int tabs, String message) {
  
  		if(DEBUG == 0) return;
  		
  		int depth = Thread.currentThread().getStackTrace().length - 14;
  		for(int i = 0; i < depth; i++) System.out.print("   ");
  		System.out.print("|");
  		for(int i = 0; i < tabs; i++) System.out.print("   ");
  		System.out.println("" + message);
  		
  	}
  	
  	private Cancelable cancelable;
  	private final Trace trace;
  	private final Instruction firstInstruction;
  	private final int argumentNumber;
  	private final Stack<Instruction> path = new Stack<Instruction>();
  
  	private int loops = 0;
  	private int depth = 0;
  	
  	private static final HashMap<InstructionTypesPair, Set<ValueSource>> cache = new HashMap<InstructionTypesPair, Set<ValueSource>>();
  
  	public static Set<ValueSource> getPotentialValues(Trace trace, Instruction instruction, int argumentNumber, Cancelable cancelable) { 
  		
  		return (new ValueSourceAnalyzer(trace, instruction, argumentNumber, cancelable)).getPotentialValues(); 
  		
  	}
  	
  	// Sorts by buckets containing instructions producing equal valued values (constants as their string representation, globals 
  	// as their qualified name, and computations in a bucket called "")
  	public static Map<String,Set<ValueSource>> getSourcesByValue(Trace trace, Instruction instruction, int argumentNumber, Cancelable cancelable) { 
  		
  		Set<ValueSource> vals = (new ValueSourceAnalyzer(trace, instruction, argumentNumber, cancelable)).getPotentialValues();
  		if(cancelable != null && cancelable.wasCanceled()) return null;
  		return sortSources(vals); 
  		
  	}
  		
  	private ValueSourceAnalyzer(Trace trace, Instruction instruction, int argumentNumber, Cancelable cancelable) {
  		
  		this.trace = trace;
  		this.cancelable = cancelable;
  		this.firstInstruction = instruction;
  		this.argumentNumber = argumentNumber;
  		
  	}
  
  	private boolean wasCanceled(InstructionTypesPair pair) {
  
  		if(cancelable != null && cancelable.wasCanceled()) {
  			if(pair != null) cache.remove(pair);
  			return true;
  		}
  		else return false;
  		
  	}
  	
  	private static void addValueSourceSet(java.util.IdentityHashMap<Set<ValueSource>,Object> setsAdded, Set<ValueSource> values, Set<ValueSource> newValues) {
  
  		if(!setsAdded.containsKey(newValues)) {
  			setsAdded.put(newValues, null);
  			values.addAll(newValues);
  		}
  		
  	}
  	
  	private Set<ValueSource> getPotentialValues() {
  
  		HashSet<ValueSource> all = new HashSet<ValueSource>();
  
  		// Check each potential producer of the argument, in case there are multiple possible paths.
  		StackDependencies.Producers producers = firstInstruction.getProducersOfArgument(argumentNumber);
  		for(int i = 0; i < producers.getNumberOfProducers(); i++) {
  
  			// Send type of the producer's class, unless its in a static method.
  			Instruction producer = producers.getProducer(i);
  			if(producer != null) {
  				Set<ValueSource> values = findValuesProducedBy(producer, new ValueSource(producer.getMethod().isStatic() ? null : producer.getClassfile().getInternalName()));
  				if(wasCanceled(null)) return null;
  				all.addAll(values);
  			}
  
  		}
  		
  		return all;
  		
  	}
  	
  	private Set<ValueSource> findValuesProducedBy(Instruction producer, ValueSource typeOfThis) {
  		
  		if(wasCanceled(null)) return null;
  
  		InstructionTypesPair pair = new InstructionTypesPair(producer, typeOfThis);
  		
  		if(cache.containsKey(pair))
  			return cache.get(pair);
  
  		Set<ValueSource> values = new HashSet<ValueSource>(3);
  		java.util.IdentityHashMap<Set<ValueSource>,Object> valueSetsAdded = new java.util.IdentityHashMap<Set<ValueSource>,Object>(3);
  
  		// Remember this right away to avoid infinite recursion.
  		cache.put(pair, values);
  
  		// Why skip locals? Because we need the path generated by this to be the same path generated by DynamicValueSource.java
  		if(!(producer instanceof GetLocal)) path.push(producer);
  		
  		// If its a constant or an allocation, we count it as a value.
  		if(producer instanceof PushConstant || producer instanceof Instantiation) {
  			
  			// Remember the "this" type context
  			values.add(new ValueSource(producer, typeOfThis, path));
  
  		}
  		// If its getting a field...
  		else if(producer instanceof GETFIELD || producer instanceof GETSTATIC) {
  			
  			FieldInfo field = trace.resolveFieldReference(((FieldrefContainer)producer).getFieldref());
  			if(field != null) {
  
  				// And its a final static variable, just point to the get static instead of its definition. It'll be more informative.
  				if(producer instanceof GETSTATIC && field.isFinal()) {
  
  					values.add(new ValueSource(producer, typeOfThis, path));
  					
  				}
  				// Otherwise, check all producers of all definitions of the field.
  				else {
  				
  					// Find all the values that come from field or global assignments.
  					int arg = producer instanceof GETFIELD ? 1 : 0;
  					for(Definition put : field.getDefinitions()) {
  
  						path.push(put);
  						
  						StackDependencies.Producers producers = put.getProducersOfArgument(arg);
  						for(int i = 0; i < producers.getNumberOfProducers(); i++) {
  							Instruction prod = producers.getProducer(i);
  							if(prod != null) {
  								Set<ValueSource> vals = findValuesProducedBy(prod, typeOfThis);
  								if(wasCanceled(pair)) return null;
  								addValueSourceSet(valueSetsAdded, values, vals);
  							}
  						}
  						
  						path.pop();
  						
  					}
  			
  				}
  			
  			}
  
  		}
  		// If its getting a local
  		else if(producer instanceof GetLocal) {
  
  			// Find all the places in the method where its defined.
  			List<SetLocal> assignments = producer.getCode().getLocalDependencies().getPotentialDefinitionsOfGetLocal((GetLocal)producer);
  			
  			int localID = ((GetLocal)producer).getLocalID();
  
  			// Is it "this"? Stop here and just add the class of this value.
  			if(producer.getMethod().isVirtual() && localID == 0) {
  
  				values.add(new ValueSource(producer, typeOfThis, path));
  				
  			}
  			// Is it a method argument?
  			else if(assignments.isEmpty() && localID < producer.getMethod().getLocalIDOfFirstNonArgument()) {
  
  				int argumentNumber = producer.getMethod().getArgumentNumberOfLocalID(((GetLocal)producer).getLocalID());
  
  				// Find out who calls this method.
  				Set<Invoke> callers = producer.getMethod().getPreciseCallers(trace, cancelable);
  				if(wasCanceled(pair)) return null;
  				
  				Classfile classOfThis = typeOfThis.type == null ? null : trace.getClassfileByName(typeOfThis.type);
  
  				// Go through each caller and find it what it might pass in for this argument.
  				for(Invoke caller : callers) {
  					
  					// If this invocation could call this method, then analyze its argument producers.
  					if(caller.couldCallOn(typeOfThis, trace)) {
  						StackDependencies.Producers producers = caller.getProducersOfArgument(argumentNumber);
  						for(int i = 0; i < producers.getNumberOfProducers(); i++) {
  							Instruction prod = producers.getProducer(i);
  							if(prod != null) {
  								Set<ValueSource> vals = findValuesProducedBy(prod, new ValueSource(caller.getClassfile().getInternalName())); 
  								if(wasCanceled(pair)) return null;
  								addValueSourceSet(valueSetsAdded, values, vals);
  							}
  						}
  					}
  
  				}
  
  				// If we didn't find any values for this method parameter, we need to fabricate one here based on the parameter's type.
  				if(values.isEmpty())
  					values.add(new ValueSource(producer, typeOfThis, path));
  				
  			}
  			// If its just a regular old local, check the producers of all of its assignments.
  			else {
  
  				for(SetLocal assignment : assignments) {
  					path.push(assignment);
  					StackDependencies.Producers producers = assignment.getProducersOfArgument(0);
  					for(int i = 0; i < producers.getNumberOfProducers(); i++) {
  						Instruction prod = producers.getProducer(i);
  						if(prod != null) {
  							Set<ValueSource> vals = findValuesProducedBy(prod, typeOfThis); 
  							if(wasCanceled(pair)) return null;
  							addValueSourceSet(valueSetsAdded, values, vals);
  						}
  					}
  					path.pop();					
  				}
  				
  			}
  			
  		}
  		// If its getting an array value...
  		else if(producer instanceof GetArrayValue) {
  
  			// Get the potential values of the array (what might allocate this array).
  			Set<ValueSource> arrayValues = (new ValueSourceAnalyzer(trace, producer, 0, cancelable)).getPotentialValues();
  			if(wasCanceled(pair)) return null;
  						
  			// Now that we have all the possible allocations for the array, what are the possible values
  			// for the array elements? We use the context for each array value for each get value.
  			for(ValueSource arrayValue : arrayValues) {
  
  				Set<SetArrayValue> assignments = gatherElementAssignments(arrayValue.instruction);
  				if(wasCanceled(pair)) return null;
  
  				if(assignments != null) {
  					for(SetArrayValue assignment : assignments){
  						StackDependencies.Producers producers = assignment.getProducersOfArgument(2);
  						for(int i = 0; i < producers.getNumberOfProducers(); i++) {
  							Instruction prod = producers.getProducer(i);
  							if(prod != null) {
  								Set<ValueSource> vals = findValuesProducedBy(prod, arrayValue.typeProducedIn); 
  								if(wasCanceled(pair)) return null;
  								addValueSourceSet(valueSetsAdded, values, vals);
  							}
  						}
  					}
  				}
  								
  			}
  			
  		}
  		// If the producer is the return value of a method call...
  		else if(producer instanceof Invoke) {
  
  			// What methods might this invocation call?
  			MethodInfo[] methods = ((Invoke)producer).getPreciseMethodsCalled(trace, cancelable);
  			if(wasCanceled(pair)) return null;
  
  			// If we couldn't find any, use the return type of the method (PotentialValue() will find it)
  			if(methods.length == 0) {
  
  				// If we couldn't find any methods, just make a type using the return type.
  				values.add(new ValueSource(producer, typeOfThis, path));
  				
  			}
  			// Otherwise...
  			else {
  
  				// Check the producer of each return statement in each method for values.
  				for(MethodInfo method : methods) {
  	
  					ValueSource value = ((Invoke)producer).getPotentialValueFor(method);
  					if(value == null) 
  						if(method.isStatic()) value = new ValueSource(QualifiedClassName.NULL);
  						else value = new ValueSource(method.getClassfile().getInternalName());
  					
  					for(AbstractReturn ret : method.getReturns()) {
  						path.push(ret);
  						StackDependencies.Producers producers = ret.getProducersOfArgument(0);
  						for(int i = 0; i < producers.getNumberOfProducers(); i++) {
  							Instruction prod = producers.getProducer(i);
  							if(prod != null) {
  								Set<ValueSource> vals = findValuesProducedBy(prod, value); 
  								if(wasCanceled(pair)) return null;
  								addValueSourceSet(valueSetsAdded, values, vals);
  							}
  						}
  						path.pop();
  					}
  	
  				}
  				
  			}
  						
  		}
  		// Just follow the producers of the duplication
  		else if(producer instanceof StackManipulation) {
  			
  			StackDependencies.Producers producers = producer.getProducersOfArgument(0);
  			for(int i = 0; i < producers.getNumberOfProducers(); i++) {
  				Instruction prod = producers.getProducer(i);
  				if(prod != null) {
  					Set<ValueSource> vals = findValuesProducedBy(prod, typeOfThis); 
  					if(wasCanceled(pair)) return null;
  					addValueSourceSet(valueSetsAdded, values, vals);
  				}
  			}
  			
  		}
  		// If its computation, stop here.
  		else if(producer instanceof Computation) {
  			
  			values.add(new ValueSource(producer, typeOfThis, path));
  			
  		}
  		else assert false : "We should have never made it here with " + producer;
  		
  		// Now, given all the values we find, which will successfully come through the type cast, if any?
  		if(producer.getNext() instanceof CHECKCAST) {
  
  			// Get what type the cast checks for.
  			QualifiedClassName cast = ((CHECKCAST)producer.getNext()).getTypeCast();
  			Classfile castClassfile = trace.getClassfileByName(cast);
  
  			// For each possible value, is it possible?
  			Iterator<ValueSource> iterator = values.iterator();
  			while(iterator.hasNext()) {
  				
  				ValueSource value = iterator.next();
  
  				// We perform the cast if we allow through a less specific type.
  				boolean performCast = false;
  				boolean castOkay = false;
  
  				// Check each possible type for the value.
  				if(value.type != null) {
  
  					// If they're the same type, allow it through.
  					if(value.type == cast)
  						castOkay = true;
  					else {
  
  						Classfile typeClassfile = trace.getClassfileByName(value.type);
  
  						// If we don't know anything about the types, we kind of just have to let the value through. There are too many that are legal to not.
  						// Yes, this will let some illegal classes through. But they will eventually be filtered out for callers at least, because we won't be able
  						// to resolve any methods on classes we haven't loaded.
  						if(castClassfile == null)
  							castOkay = true;
  						// If the cast type is a type of the value's type, then its okay, and we need to cast the value's type to be the more specific cast type.
  						else if(castClassfile.isExtendsOrImplements(value.type)) {
  							castOkay = true;
  							performCast = true;
  						}
  
  						// If we don't know the type's class or it's a type of the cast type, then allow it through.
  						if(typeClassfile == null)
  							castOkay = true;
  						else if(typeClassfile.isExtendsOrImplements(cast))
  							castOkay = true;
  						
  					}
  					
  					// The only situation in which we don't allow it through is when the neither type subclasses or implements the other.
  					
  				}
  
  				// This replaces the less specific type with the more specific cast type.
  				if(performCast)
  					value.type = cast;
  
  				// If the cast was illegal, remove it.
  				if(!castOkay)
  					iterator.remove();
  				
  			}
  			
  		}
  		
  		// Why skip locals? Because we need the path generated by this to be the same path generated by DynamicValueSource.java
  		if(!(producer instanceof GetLocal)) path.pop();
  		
  		return values;
  		
  	}
  	
  	private static HashMap<Instruction, Set<SetArrayValue>> elementAssignmentsCache = new HashMap<Instruction, Set<SetArrayValue>>(1000);
  		
  	// Find all uses of the array produced by the given instruction, gathering set array value instructions along the way.
  	private Set<SetArrayValue> gatherElementAssignments(Instruction arrayProducer) {
  	
  		Set<SetArrayValue> assignments = elementAssignmentsCache.get(arrayProducer);
  		if(assignments == null) {
  			assignments = new HashSet<SetArrayValue>(2);
  			elementAssignmentsCache.put(arrayProducer, assignments);
  		}
  		else return assignments;
  		
  		// Some of these are legal, such as ACONST_NULL instructions, but sometimes we get boolean and string constants. Weird.
  		if(arrayProducer instanceof PushConstant)
  			return null;
  		
  		TLongHashSet visited = new TLongHashSet();
  		
  		ArrayList<Instruction> instructionsToVisit = new ArrayList<Instruction>();
  		ArrayList<Instruction> newInstructionsToVisit = new ArrayList<Instruction>();
  
  		instructionsToVisit.add(arrayProducer);
  		
  		while(instructionsToVisit.size() > 0) {
  
  			for(Instruction instructionToVisit : instructionsToVisit) {
  				
  				if(wasCanceled(null)) {
  					elementAssignmentsCache.remove(arrayProducer);
  					return null;
  				}
  
  				long id = System.identityHashCode(instructionToVisit);
  				if(visited.contains(id)) continue;
  				visited.add(id);
  
  				for(Instruction consumer : instructionToVisit.getConsumers()) {
  
  					if(consumer instanceof SetArrayValue) {
  						
  						// If this producers the array for the instruction, then yay!
  						if(consumer.getArgumentNumberOfProducer(instructionToVisit) == 0)
  							assignments.add((SetArrayValue) consumer);
  						// Otherwise, it produces the value for the instruction, for a multidimensional array.
  						
  					}
  					else if(consumer instanceof SetLocal) {
  		
  						for(Use use : consumer.getCode().getLocalDependencies().getPotentialUsesOfLocalIDAtOrAfter(consumer, ((SetLocal)consumer).getLocalID()))
  							newInstructionsToVisit.add(use);
  						
  					}
  					else if(consumer instanceof PUTFIELD || consumer instanceof PUTSTATIC) {
  		
  						FieldInfo field = trace.resolveFieldReference(((FieldrefContainer)consumer).getFieldref());
  						if(field != null)
  							for(Use use : field.getUses())
  								newInstructionsToVisit.add(use);
  						
  					}
  					else if(consumer instanceof Invoke) {
  						
  						// What might this be called on?
  						MethodInfo[] methods = ((Invoke)consumer).getPreciseMethodsCalled(trace, cancelable);
  						if(wasCanceled(null)) {
  							elementAssignmentsCache.remove(arrayProducer);
  							return null;
  						}
  						for(MethodInfo method : methods) {
  							if(method.getCode() != null)
  								for(Use use : method.getCode().getLocalDependencies().getPotentialUsesOfArgument(consumer.getArgumentNumberOfProducer(instructionToVisit)))
  									newInstructionsToVisit.add(use);
  						}
  						
  					}
  					else if(consumer instanceof AbstractReturn) {
  						
  						Set<Invoke> callers = consumer.getMethod().getPreciseCallers(trace, cancelable);
  						if(wasCanceled(null)) {
  							elementAssignmentsCache.remove(arrayProducer);
  							return null;
  						}
  						for(Invoke caller : callers)
  							newInstructionsToVisit.add(caller);
  						
  					}
  					// We care not about all other types of array consumers.
  					else {}
  		
  				}
  				
  			}
  			
  			instructionsToVisit.clear();
  			ArrayList<Instruction> temp = newInstructionsToVisit;
  			newInstructionsToVisit = instructionsToVisit;
  			instructionsToVisit = temp;
  					
  		}
  						
  		return assignments;
  		
  	}
  	
  	private static Map<String, Set<ValueSource>> sortSources(Set<ValueSource> values) {
  		
  		Map<String, Set<ValueSource>> sourcesByValue = new Hashtable<String, Set<ValueSource>>(values.size());
  		
  		for(ValueSource value : values) {
  
  			Instruction source = value.instruction;
  			
  			if(source instanceof PushConstant) {
  
  				String valueLabel = "" + ((PushConstant<?>)source).getConstant();
  				getSortSet(valueLabel, sourcesByValue).add(value);
  				
  			}
  			else if(source instanceof GETSTATIC) {
  				
  				FieldrefInfo field = ((GETSTATIC)source).getFieldref();
  				String valueLabel = "" + field.getClassname().getSimpleName() + "." + field.getName();
  				getSortSet(valueLabel, sourcesByValue).add(value);
  				
  			}
  			else {
  				
  				getSortSet("", sourcesByValue).add(value);				
  				
  			}
  			
  		}
  		
  		return sourcesByValue;
  		
  	}
  
  	private static Set<ValueSource> getSortSet(String value, Map<String, Set<ValueSource>> table) {
  		
  		Set<ValueSource> set = table.get(value);
  		if(set == null) {
  			
  			set = new HashSet<ValueSource>();
  			table.put(value, set);			
  			
  		}
  		return set;		
  		
  	}
  
  }