/*
    *
    */
   package org.softevo.jdynpur.eval;
   
   import java.io.BufferedInputStream;
   import java.io.DataInputStream;
   import java.io.EOFException;
   import java.io.File;
  import java.io.FileInputStream;
  import java.io.IOException;
  import java.io.Serializable;
  import java.text.DecimalFormat;
  import java.text.NumberFormat;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.Stack;
  import java.util.Vector;
  
  import java.lang.jdynpur.Tracer;
  
  import org.apache.commons.io.input.CountingInputStream;
  import org.softevo.util.ObjectIdMapper;
  import org.softevo.util.asm.FieldIdentifier;
  import org.softevo.util.asm.MethodIdentifier;
  import org.softevo.util.asm.MethodIdentifierMapGenerator;
  
  /**
   * This class implements dynamic purity analysis of an execution trace file. The
   * main idea of the analysis is as follows:
   * <ul>
   * <li>For every method, calculate the set of modified and the set of created
   * objects.</li>
   * <li>At the end of each method, add the set of created objects to the created
   * objects of the calling method. </li>
   * <li>At the end of each method, check whether any object not created during
   * the execution of the method was modified. If this is the case, the execution
   * was impure, otherwise pure.
   * </ul>
   * 
   * @author dallmeier
   */
  public class PurityTraceAnalyser {
  
  	/**
  	 * The name of the trace file to be analyzed.
  	 */
  	protected String fileName = null;
  
  	/**
  	 * Name of the file where results are saved.
  	 */
  	protected String resultsFileName = null;
  
  	/**
  	 * Identifier map used for this trace.
  	 */
  	protected MethodIdentifierMapGenerator identifierMap = null;
  
  	/**
  	 * The set of method ids known to be impure.
  	 */
  	protected HashMap<Integer, HashSet<String>> impureMethodIds = null;
  	
  	/**
  	 * The set of method ids that might be pure.
  	 */
  	protected HashMap<Integer, HashSet<String>> pureMethodIds = null;
  
  	/**
  	 * The set of executed methods.
  	 */
  	protected HashMap<Integer, HashSet<String>> executedMethodIds = null;
  
  	/**
  	 * The set of methods known to modify the object they were invoked on.
  	 */
  	protected HashMap<Integer, HashSet<String>> methodsModifyingThisObject = null;
  
  	/**
  	 * The set of <code>MethodIdentifiers</code> known to be pure.
  	 */
  	protected HashMap<MethodIdentifier, HashSet<String>> pureMethodIdentifiers = null;
  
  	/**
  	 * The set of <code>MethodIdentifiers</code> modifying a this object.
  	 */
  	protected HashMap<MethodIdentifier, HashSet<String>> thisModifyingMethodIdentifiers = null;
  
  	/**
  	 * The set of <code>MethodIdentifiers</code> known to be impure.
  	 */
  	protected HashMap<MethodIdentifier, HashSet<String>> impureMethodIdentifiers = null;
  
  	/**
  	 * The set of executed <code>MethodIdentifiers</code>.
  	 */
 	protected HashMap<MethodIdentifier, HashSet<String>> executedMethodIdentifiers = null;
 
 	/**
 	 * A map of thread ids to a stack of object identifiers created in a method.
 	 */
 	protected HashMap<Integer, Stack<HashSet<Integer>>> threadIdToCreatedObjectSetStackMap = null;
 
 	protected HashMap<Integer, Stack<HashMap<Integer, Integer>>> threadIdToParameterSetStackMap = null;
 
 	protected ObjectIdMapper<FieldIdentifier> fieldIdentifierMap = null;
 
 	/**
 	 * A map of thread ids to a stack of object identifiers modified in a method.
 	 */
 	protected HashMap<Integer, Stack<HashSet<Integer>>> threadIdToModifiedObjectSetStackMap = null;
 
 	/**
 	 * A map of thread ids to a method call stack.
 	 */
 	protected HashMap<Integer, Stack<Integer>> threadIdToMethodCallStackMap = null;
 
 	/**
 	 * A map of thread ids to a stack of this object identifiers for active
 	 * non-static methods.
 	 */
 	protected HashMap<Integer, Stack<Integer>> threadIdToThisStackMap = null;
 
 	/**
 	 * A map of thread ids to a stack of this type for active
 	 * non-static methods.
 	 */
 	protected HashMap<Integer, Stack<String>> threadIdToThisTypeMap = null;
 
 	protected HashMap<MethodIdentifier, ParameterMutabilityInformation> parameterMutabilityInformation = null;
 
 	protected Vector<Long> mutabilityChangeEntries = null;
 	
 	protected Vector<Long> purityChangeEntries = null;
 
 	protected PurityResults results = null;
 	
 	/**
 	 * Flag for verbose output.
 	 */
 	protected boolean verbose = false;
 
 	/**
 	 * Flag if pure method identifiers should be printed to
 	 * <code>System.out</code> .
 	 */
 	protected boolean printResults = false;
 
 	/**
 	 * Flag if results shall be saved.
 	 */
 	protected boolean saveResults = false;
 
 	/**
 	 * Flag indicating if API methods should be excluded from the result data
 	 * structures.
 	 */
 	protected boolean excludeAPIMethodsFromResults = true;
 
 	/**
 	 * Flag indicating if the effects of static initializers should be ignored. If
 	 * you are not sure about this flag, set it to true.
 	 */
 	protected boolean ignoreEffectsOfStaticInitializers = true;
 
 	private HashMap<Integer, HashMap<Integer, Integer>> heap;
 
 	private boolean analyseParameterMutability;
 
 	private long loopCounter;
 	
 	/**
 	 * Creates a new purity analyser for a trace file.
 	 * 
 	 * @param fileName
 	 *          the name of the trace
 	 * @param identifierMap
 	 *          the identifier map generated together with the trace
 	 */
 	public PurityTraceAnalyser(String fileName, String resultsFileName,
 	                           boolean saveResults, boolean analyseParameterMutability) {
 		this.fileName = fileName;
 		this.resultsFileName = resultsFileName;
 		this.saveResults = saveResults;
 		this.excludeAPIMethodsFromResults = Boolean.FALSE;
 		this.analyseParameterMutability = analyseParameterMutability;
 		this.identifierMap = new MethodIdentifierMapGenerator();
 		this.fieldIdentifierMap = new ObjectIdMapper<FieldIdentifier>();
 		impureMethodIds = new HashMap<Integer, HashSet<String>>();
 		pureMethodIds = new HashMap<Integer, HashSet<String>>();
 		executedMethodIds = new HashMap<Integer, HashSet<String>>();
 		methodsModifyingThisObject = new HashMap<Integer, HashSet<String>>();
 		threadIdToMethodCallStackMap = new HashMap<Integer, Stack<Integer>>();
 		threadIdToCreatedObjectSetStackMap = new HashMap<Integer, Stack<HashSet<Integer>>>();
 		threadIdToModifiedObjectSetStackMap = new HashMap<Integer, Stack<HashSet<Integer>>>();
 		threadIdToThisStackMap = new HashMap<Integer, Stack<Integer>>();
 		threadIdToThisTypeMap = new HashMap<Integer, Stack<String>>();
 	  mutabilityChangeEntries = new Vector<Long>();
 	  purityChangeEntries = new Vector<Long>();
 		if (analyseParameterMutability) {
 		  threadIdToParameterSetStackMap = new HashMap<Integer, Stack<HashMap<Integer,Integer>>>();
 		  parameterMutabilityInformation = new HashMap<MethodIdentifier, ParameterMutabilityInformation>();
 		  heap = new HashMap<Integer, HashMap<Integer,Integer>>(10000);
 		}
 	}
 
 	/**
 	 * Starts analysis of the trace.
 	 * 
 	 * @param verbose
 	 *          flag if output shall be verbose
 	 * @param printResults
 	 *          flag if results should be printed to <code>System.out</code>
 	 * @throws IOException
 	 *           if an exception occurs reading from the trace
 	 */
 	public void analyse(boolean verbose, boolean printResults) throws IOException {
 		DataInputStream dataInputStream;
 		int eventType;
 		int value, value2, threadId;
 		String className;
 
 		System.out.println("Analyzing trace " + fileName);
 		this.verbose = verbose;
 		this.printResults = printResults;
 		File traceFile = new File(fileName);
 		long fileSize = traceFile.length();
 		CountingInputStream countingInputStream = new CountingInputStream(new BufferedInputStream(new FileInputStream(traceFile)));
 		dataInputStream = new DataInputStream(countingInputStream);
 		NumberFormat formatter = new DecimalFormat("00");
 		String percentageString = null;
 		loopCounter = 0;
 		while (loopCounter >= 0) {
 			loopCounter++;
 			if (loopCounter > 0 && loopCounter % 100000 == 0) {
 				double percentageDone = countingInputStream.getCount()*100d/(fileSize*1.0d);
 				String newPercentageString = formatter.format(percentageDone);
 				if (percentageString != null && !newPercentageString.equals(percentageString)) {
 				  System.out.println(percentageString + "% done.");
 				}
 				percentageString = newPercentageString;
 			}
 			try {
 				eventType = dataInputStream.readInt();
 				if (eventType != Tracer.EV_METHODID && eventType != Tracer.EV_FIELDID) {
 					threadId = dataInputStream.readInt();
 					value = dataInputStream.readInt();
 					switch (eventType) {
 					case Tracer.EV_FIELDWRITE:
 						handleFieldWrite(value, threadId);
 						break;
 					case Tracer.EV_DYNAMICMETHODEND:
 						if (identifierMap.getMethodIdentifier(value) == null) {
 							System.out.println("Ignoring method end " + value + " for thread " + threadId);
 						} else {
 							handleDynamicMethodEnd(value, threadId);
 						}
 						break;
 					case Tracer.EV_STATICMETHODEND:
 						handleStaticMethodEnd(value, threadId);
 						break;
 					case Tracer.EV_STATICMETHODSTART:
 						handleStaticMethodStart(value, threadId);
 						break;
 					case Tracer.EV_DYNAMICMETHODSTART:
 						value2 = dataInputStream.readInt();
 						className = dataInputStream.readUTF().replace('.', '/');
 						handleDynamicMethodStart(value, value2, threadId, className);
 						break;
 					case Tracer.EV_OBJECTCREATION:
 						handleObjectCreation(value, threadId);
 						break;
 					case Tracer.EV_STATICFIELDWRITE:
 						handleStaticFieldWrite(threadId);
 						break;
 					case Tracer.EV_ARRAYCREATED:
 						handleArrayCreation(value, threadId);
 						break;
 					case Tracer.EV_ARRAYMODIFIED:
 						handleArrayModification(value, threadId);
 						break;
 					case Tracer.EV_PARAMETER: {
 						int objectId = dataInputStream.readInt();
 						if (analyseParameterMutability) {
 						  handleParameter(value, threadId, objectId);
 						}
 						break;
 					}
 					case Tracer.EV_OBJECTFIELDWRITE: {
 						int fieldId = value;
 						int changedObjectId = dataInputStream.readInt();
 						int newValueObjectId = dataInputStream.readInt();
 						handleObjectFieldWrite(fieldId, threadId, changedObjectId, newValueObjectId);
 						break;
 					}
 					case Tracer.EV_OBJECTARRAYMODIFIED: {
 						int changedObjectId = value;
 						int arrayIndex = dataInputStream.readInt();
 						int newObjectId = dataInputStream.readInt();
 						handleObjectArrayModification(threadId, changedObjectId, arrayIndex, newObjectId);
 						break;
 					}
 					default:
 						throw new RuntimeException("Illegal trace event code " + eventType);
 					}
 				} else {
 					if (eventType == Tracer.EV_METHODID) {
 						int methodId = dataInputStream.readInt();
 						int access = dataInputStream.readInt();
 						String methodName = dataInputStream.readUTF();
 						MethodIdentifier identifier = MethodIdentifier.parseFromIdentifier(methodName, access);
 						identifierMap.add(methodId, identifier);
 					} else if (eventType == Tracer.EV_FIELDID) {
 						int fieldId = dataInputStream.readInt();
 						String fieldIdentifier = dataInputStream.readUTF();
 						FieldIdentifier identifier = FieldIdentifier.parseIdentifierFromString(fieldIdentifier);
 						fieldIdentifierMap.put(fieldId, identifier);
 					}
 				}
 			} catch (EOFException eof) {
 				dataInputStream.close();
 				handleTraceEnd();
 				break;
 			}
 		}
 		System.out.println(formatter.format(100d) + "% done.");
 		System.out.println();
 	}
 
 	private HashMap<Integer, Integer> getOrCreateMapForObject(int objectId) {
 		HashMap<Integer, Integer> result = heap.get(objectId);
 		if (result == null) {
 			result = new HashMap<Integer, Integer>();
 			heap.put(objectId, result);
 		}
 		return result;
 	}
 	
 	protected HashSet<Integer> getTransitiveStateForObject(int objectId) {
 		HashSet<Integer> result = new HashSet<Integer>(100);
 		addStateRecursively(objectId, result);
 		return result;
 	}
 	
 	private void addStateRecursively(int objectId, HashSet<Integer> result) {
 		if (!result.contains(objectId)) {
 			result.add(objectId);
 		  HashMap<Integer, Integer> state = heap.get(objectId);
 		  if (state != null) {
 			  for (Integer childObjectId: state.values()) {
 				  addStateRecursively(childObjectId, result);
 			  }
 		  }
 		}
 	}
 
 	protected void handleObjectArrayModification(int threadId, int changedObjectId,
 																							int arrayIndex, int newObjectId) {
 		handleObjectFieldWrite(arrayIndex, threadId, changedObjectId, newObjectId);
 	}
 
 	protected void handleObjectFieldWrite(int fieldId, int threadId,
 																			int changedObjectId, int newValueObjectId) {
 		if (analyseParameterMutability) {
 		  HashMap<Integer, Integer> objectFields = getOrCreateMapForObject(changedObjectId);
 		  objectFields.put(fieldId, newValueObjectId);
 		}
 		getModifiedObjectSetStack(threadId).peek().add(changedObjectId);
 	}
 
 	protected void handleParameter(int index, int threadId, int objectId) {
 		Stack<HashMap<Integer, Integer>> parameters = getParameterSetStack(threadId);
 		assert (parameters.size() > 0) : "No parameter set found.";
 		parameters.peek().put(index, objectId);
 	}
 
 	protected Stack<String> getThisTypeStack(int threadId) {
 		Stack<String> result;
 
 		result = threadIdToThisTypeMap.get(threadId);
 		if (result == null) {
 			result = new Stack<String>();
 			threadIdToThisTypeMap.put(threadId, result);
 		}
 		return result;
 	}
 
 	/**
 	 * Gets the this object stack for a given thread.
 	 * 
 	 * @param threadId
 	 *          the id of the thread
 	 * @return the stack
 	 */
 	protected Stack<Integer> getThisObjectStack(int threadId) {
 		Stack<Integer> result;
 
 		result = threadIdToThisStackMap.get(threadId);
 		if (result == null) {
 			result = new Stack<Integer>();
 			threadIdToThisStackMap.put(threadId, result);
 		}
 		return result;
 	}
 
 	/**
 	 * Gets the method call stack for a given thread.
 	 * 
 	 * @param threadId
 	 *          the id of the thread
 	 * @return the stack
 	 */
 	protected Stack<Integer> getMethodCallStack(int threadId) {
 		Stack<Integer> result;
 
 		result = threadIdToMethodCallStackMap.get(threadId);
 		if (result == null) {
 			result = new Stack<Integer>();
 			threadIdToMethodCallStackMap.put(threadId, result);
 		}
 		return result;
 	}
 
 	/**
 	 * Gets the created object set stack for a given thread.
 	 * 
 	 * @param threadId
 	 *          the id of the thread
 	 * @return the stack
 	 */
 	protected Stack<HashSet<Integer>> getCreatedObjectSetStack(int threadId) {
 		Stack<HashSet<Integer>> result;
 
 		result = threadIdToCreatedObjectSetStackMap.get(threadId);
 		if (result == null) {
 			result = new Stack<HashSet<Integer>>();
 			threadIdToCreatedObjectSetStackMap.put(threadId, result);
 		}
 		return result;
 	}
 
 	/**
 	 * Gets the modified object set stack for a given thread.
 	 * 
 	 * @param threadId
 	 *          the id of the thread
 	 * @return the stack
 	 */
 	protected Stack<HashSet<Integer>> getModifiedObjectSetStack(int threadId) {
 		Stack<HashSet<Integer>> result;
 
 		result = threadIdToModifiedObjectSetStackMap.get(threadId);
 		if (result == null) {
 			result = new Stack<HashSet<Integer>>();
 			threadIdToModifiedObjectSetStackMap.put(threadId, result);
 		}
 		return result;
 	}
 
 	protected Stack<HashMap<Integer,Integer>> getParameterSetStack(int threadId) {
 		Stack<HashMap<Integer, Integer>> result;
 
 		result = threadIdToParameterSetStackMap.get(threadId);
 		if (result == null) {
 			result = new Stack<HashMap<Integer, Integer>>();
 			threadIdToParameterSetStackMap.put(threadId, result);
 		}
 		return result;
 	}
 
 	/**
 	 * This method checks if the integer passed identifies a user or an API
 	 * method. Identification of API methods is done by class name.
 	 * 
 	 * @param methodId
 	 *          the method identifier
 	 */
 	protected boolean isAPIMethod(int methodId) {
 		MethodIdentifier identifier;
 
 		identifier = identifierMap.getMethodIdentifier(methodId);
 		if (identifier.getClassName().startsWith("java") || identifier.getClassName().startsWith("sun")) {
 			return true;
 		} else {
 			return false;
 		}
 	}
 
 	protected HashMap<MethodIdentifier, HashSet<String>> convertMap(HashMap<Integer, HashSet<String>> map) {
 		HashMap<MethodIdentifier, HashSet<String>> result;
 		Iterator<Integer> iterator;
 		int methodId;
 
 		result = new HashMap<MethodIdentifier, HashSet<String>>();
 		iterator = map.keySet().iterator();
 		while (iterator.hasNext()) {
 			methodId = iterator.next();
 			if (!excludeAPIMethodsFromResults || !isAPIMethod(methodId)) {
 				result.put(identifierMap.getMethodIdentifier(methodId), map.get(methodId));
 			}
 		}
 		return result;
 	}
 	
 	boolean debug = false;
 	/**
 	 * This method is called upon end of the trace. It fills the result
 	 * datastructures and prints information to <code>System.out</code> if the
 	 * <code>printResults</code> flag is set.
 	 */
 	protected void handleTraceEnd() {
 		Iterator<Integer> iterator;
 		Iterator<String> methodNameIterator;
 		Vector<String> pureMethodNames;
 		int methodId;
 
 		iterator = executedMethodIds.keySet().iterator();
 		pureMethodNames = new Vector<String>(executedMethodIds.size());
 		pureMethodIdentifiers = new HashMap<MethodIdentifier, HashSet<String>>();
 		impureMethodIdentifiers = convertMap(impureMethodIds);
 		thisModifyingMethodIdentifiers = convertMap(methodsModifyingThisObject);
 		executedMethodIdentifiers = convertMap(executedMethodIds);
 		while (iterator.hasNext()) {
 			methodId = iterator.next();
 			if (!impureMethodIds.containsKey(methodId)) {
 				pureMethodNames.add(identifierMap.getMethodIdentifier(methodId).toString());
 
 				if (!excludeAPIMethodsFromResults || !isAPIMethod(methodId)) {
 					pureMethodIdentifiers.put(identifierMap.getMethodIdentifier(methodId), 
 					                          executedMethodIds.get(methodId));
 				}
 			}
 		}
 		if (printResults) {
 			Collections.sort(pureMethodNames);
 			methodNameIterator = pureMethodNames.iterator();
 			System.out.println("Pure methods:");
 			while (methodNameIterator.hasNext()) {
 				System.out.println(methodNameIterator.next());
 			}
 			System.out.println("Number of pure methods: " + pureMethodNames.size());
 			System.out.println("Number of executed methods: " + executedMethodIds.size());
 		}
 		System.out.println("Saving results to " + resultsFileName);
 		results = new PurityResults(pureMethodIdentifiers, impureMethodIdentifiers, thisModifyingMethodIdentifiers,
 		                            executedMethodIdentifiers, parameterMutabilityInformation);
 		if (debug) {
 			System.out.println("Debugging");
 			for (MethodIdentifier identifier : pureMethodIdentifiers.keySet()) {
 				assert (!impureMethodIdentifiers.containsKey(identifier)) : "Identifier "  + identifier + " both impure and pure.";
 				assert (executedMethodIdentifiers.containsKey(identifier)) : "Pure method identifier "  + identifier + " not executed.";
 			}
 			for (MethodIdentifier identifier : impureMethodIdentifiers.keySet()) {
 				assert (!pureMethodIdentifiers.containsKey(identifier)) : "Identifier "  + identifier + " both impure and pure.";
 				assert (executedMethodIdentifiers.containsKey(identifier)) : "Impure method identifier "  + identifier + " not executed.";
 			}
 		}
 		if (saveResults) {
 			try {
 				results.saveXML(resultsFileName);
 			} catch (Exception exception) {
 				System.out.println("An exception occured saving results.");
 				exception.printStackTrace(System.out);
 			}
 		}
 	}
 
 	/**
 	 * Called to handle an array creation event.
 	 * 
 	 * @param objectId
 	 *          the id of the new array
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleArrayCreation(int objectId, int threadId) {
 		if (verbose) {
 			System.out.println("Array created with id " + objectId + " in thread " + threadId + ".");
 		}
 		getCreatedObjectSetStack(threadId).peek().add(objectId);
 	}
 
 	/**
 	 * Called to handle an array modification event.
 	 * 
 	 * @param objectId
 	 *          the id of the modified array
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleArrayModification(int objectId, int threadId) {
 		if (verbose) {
 			System.out.println("Array " + objectId + " modified in thread " + threadId + ".");
 		}
 		getModifiedObjectSetStack(threadId).peek().add(objectId);
 	}
 
 	/**
 	 * Called to handle a static field write event.
 	 * 
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleStaticFieldWrite(int threadId) {
 		MethodIdentifier methodIdentifier;
 
 		if (verbose) {
 			System.out.println("Static field written in thread " + threadId + ".");
 		}
 		methodIdentifier = identifierMap.getMethodIdentifier(getMethodCallStack(threadId).peek());
 		if (ignoreEffectsOfStaticInitializers && methodIdentifier.getMethodName().equals("<clinit>")) {
 			if (verbose) {
 				System.out.println("Ignoring static field write in <clinit> of class " + methodIdentifier.getClassName());
 			}
 		} else {
 			getModifiedObjectSetStack(threadId).peek().add(Tracer.STATIC);
 		}
 	}
 
 	/**
 	 * Called to handle a field write event.
 	 * 
 	 * @param threadId
 	 *          the thread id
 	 * @param objectId
 	 *          id of the modified object
 	 */
 	protected void handleFieldWrite(int objectId, int threadId) {
 		if (verbose) {
 			System.out.println("Field written in object " + objectId + " in thread " + threadId + ".");
 		}
 		getModifiedObjectSetStack(threadId).peek().add(objectId);
 	}
 
 	/**
 	 * Handles object creation event.
 	 * 
 	 * @param objectId
 	 *          the id of the new object
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleObjectCreation(int objectId, int threadId) {
 		if (verbose) {
 			System.out.println("Object created with id " + objectId + " in thread " + threadId + ".");
 		}
 		getCreatedObjectSetStack(threadId).peek().add(objectId);
 	}
 
 	protected void addToHashMap(HashMap<Integer, HashSet<String>> map, int methodId, String className) {
 		HashSet<String> types;
 
 		types = map.get(methodId);
 		if (types == null) {
 			types = new HashSet<String>();
 			map.put(methodId, types);
 		}
 		if (className != null) {
 			types.add(className);
 		}
 	}
 
 	/**
 	 * Handles a method start event. This method creates all neccessary
 	 * datastructures to analyze execution of the method.
 	 * 
 	 * @param methodId
 	 *          the id of the method invoked
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleMethodStart(int methodId, int threadId, String className) {
 		if (verbose) {
 			System.out.println("Method " + identifierMap.getMethodIdentifier(methodId) + " in thread " + threadId
 			                   + " started.");
 		}
 		if (className != null) {
 			addToHashMap(executedMethodIds, methodId, className);
 		} else {
 			System.out.println("Class name for executed method " + methodId + " is null.");
 		}
 		getMethodCallStack(threadId).push(methodId);
 		getCreatedObjectSetStack(threadId).push(new HashSet<Integer>());
 		getModifiedObjectSetStack(threadId).push(new HashSet<Integer>());
 		if (analyseParameterMutability) {
 		  getParameterSetStack(threadId).push(new HashMap<Integer, Integer>());
 		}
 	}
 
 	/**
 	 * Handles start of a dynamic method. In addition to calling
 	 * <code>handleMethodStart</code>, this method also modifieds the
 	 * <code>thisObjectStack</code>.
 	 * 
 	 * @param methodId
 	 *          the method identifier
 	 * @param thisObjectId
 	 *          the identifier of the this object
 	 * @param threadId
 	 *          the id of the thread
 	 */
 	protected void handleDynamicMethodStart(int methodId, int thisObjectId, 
 	                                        int threadId, String className) {
 		getThisObjectStack(threadId).push(thisObjectId);
 		getThisTypeStack(threadId).push(className);
 		handleMethodStart(methodId, threadId, className);
 	}
 
 	/**
 	 * Handles start of a static method. This method only calls
 	 * <code>handleMethodStart</code>
 	 * 
 	 * @param methodId
 	 *          the identifier of the method
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleStaticMethodStart(int methodId, int threadId) {
 		MethodIdentifier identifier = identifierMap.getMethodIdentifier(methodId);
 		handleMethodStart(methodId, threadId, identifier.getClassName());
 	}
 
 	/**
 	 * Handles end of a static method. This method only calls
 	 * <code>handleMethodEnd</code>.
 	 * 
 	 * @param methodId
 	 *          the id of the method
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleStaticMethodEnd(int methodId, int threadId) {
 		handleMethodEnd(methodId, threadId, null);
 	}
 
 	/**
 	 * Handles end of a dynamic method. In addition to calling
 	 * <code>handleMethodEnd</code>, this method also modifies the
 	 * <code>thisObjectStack</code>
 	 * 
 	 * @param methodId
 	 *          the id of the method
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleDynamicMethodEnd(int methodId, int threadId) {
 		HashSet<Integer> modifiedObjects;
 		int thisObjectId;
 		String className;
 
 		if (verbose) {
 			System.out.println("Dynamic method " + identifierMap.getMethodIdentifier(methodId) + " (" + methodId
 			                   + ") in thread " + threadId + " finished.");
 		}
 		modifiedObjects = getModifiedObjectSetStack(threadId).peek();
 		thisObjectId = getThisObjectStack(threadId).pop();
 		className = getThisTypeStack(threadId).pop();
 		if (modifiedObjects.contains(thisObjectId)) {
 			addToHashMap(methodsModifyingThisObject, methodId, className);
 		}
 		handleMethodEnd(methodId, threadId, className);
 	}
 
 	/**
 	 * Handles method end events. This method evaluates the set of modified and
 	 * created objects and classifies methods as impure.
 	 * 
 	 * @param methodId
 	 *          the id of the method
 	 * @param threadId
 	 *          the thread id
 	 */
 	protected void handleMethodEnd(int methodId, int threadId, String className) {
 		if (verbose) {
 			System.out.println("Method " + identifierMap.getMethodIdentifier(methodId) + " in thread " + threadId
 			                   + " finished.");
 		}
 		int activeMethodId = getMethodCallStack(threadId).pop();
 		HashSet<Integer> createdObjects = getCreatedObjectSetStack(threadId).pop();
 		HashSet<Integer> modifiedObjects = getModifiedObjectSetStack(threadId).pop();
 		if (methodId != activeMethodId) {
 			System.out.println("Method Start/End mismatch for thread " + threadId);
 			System.out
 			.println("Method that finished: " + identifierMap.getMethodIdentifier(methodId) + " (" + methodId + ")");
 			System.out.println("Method that should have finished: " + identifierMap.getMethodIdentifier(activeMethodId)
 			                   + " (" + activeMethodId + ")");
 		}
 		if (className == null) {
 			MethodIdentifier identifier = identifierMap.getMethodIdentifier(methodId);
 			className = identifier.getClassName();
 		}
 		// this assumes that all objects created in a sub method
 		// may escape
 		if (getCreatedObjectSetStack(threadId).size() > 0) {
 			getCreatedObjectSetStack(threadId).peek().addAll(createdObjects);
 		}
 		if (getModifiedObjectSetStack(threadId).size() > 0) {
 			getModifiedObjectSetStack(threadId).peek().addAll(modifiedObjects);
 		}
 		if (!createdObjects.containsAll(modifiedObjects)) {
 			addToHashMap(impureMethodIds, activeMethodId, className);
 			if (pureMethodIds.containsKey(methodId)) {
 				pureMethodIds.remove(activeMethodId);
 				purityChangeEntries.add(loopCounter);
 			}
 		} else {
 			if (!impureMethodIds.containsKey(activeMethodId)) {
 			  addToHashMap(pureMethodIds, activeMethodId, className);
 			}
 		}
 		if (analyseParameterMutability) {
 		  HashMap<Integer, Integer> parameters = getParameterSetStack(threadId).pop();
 		  processParameterModification(parameters, modifiedObjects, methodId, className);
 		}
 	}
 
 	protected void processParameterModification(HashMap<Integer, Integer> parameters, HashSet<Integer> modifiedObjects, 
 	                                            int methodId, String className) {
 		HashSet<Integer> unmodifiedParameters = new HashSet<Integer>(parameters.size());
 		for (int parameterIndex : parameters.keySet()) {
 			int objectId = parameters.get(parameterIndex);
 			if ((objectId != Tracer.NULL)) {
 				HashSet<Integer> transitiveState = getTransitiveStateForObject(objectId);
 				boolean isUnmodified = true;
 				for (Integer stateObjectId : transitiveState) {
 					if (modifiedObjects.contains(stateObjectId)) {
 						isUnmodified = false;
 						break;
 					}
 				}
 				if (isUnmodified) {
 					unmodifiedParameters.add(parameterIndex);
 				}
 			} else {
 				unmodifiedParameters.add(parameterIndex);
 				
 			}
 		}
 		MethodIdentifier identifier = identifierMap.getMethodIdentifier(methodId);
 		ParameterMutabilityInformation information = parameterMutabilityInformation.get(identifier);
 		int oldNumberOfUnmodifiedParameters = -1;
 		if (information == null) {
 			information = new ParameterMutabilityInformation(identifier);
 			parameterMutabilityInformation.put(identifier, information);
 		} else {
 			oldNumberOfUnmodifiedParameters = information.getUnmodifiedParameters().size();
 		}
 		information.updateUnmodifiedParameters(className, unmodifiedParameters);
 		for (Integer parameterIndex : parameters.keySet()) {
 			information.addParameter(parameterIndex);
 		}
 		if (oldNumberOfUnmodifiedParameters != -1) {
 			int newNumberOfUnmodifiedParameters = information.getUnmodifiedParameters().size();
 			assert (newNumberOfUnmodifiedParameters <= oldNumberOfUnmodifiedParameters) : "Illegal increase in number of unmodified parameters @" + loopCounter + " .";
 			if (newNumberOfUnmodifiedParameters < oldNumberOfUnmodifiedParameters) {
 				mutabilityChangeEntries.add(loopCounter);
 			}
 		}
 	}
 	
 	/**
 	 * Launches purity trace analysis. This method expects the name of the trace
 	 * file and the name of the identifier map file.
 	 * 
 	 * @param args
 	 *          command line arguments
 	 */
 	public static void main(String[] args) throws IOException {
 		PurityTraceAnalyser traceAnalyser;
 
 		if (args.length != 3) {
 			System.out
 			.println("Usage: java org.softevo.jdynpur.PurityTraceAnalyser <traceFileName> <resultsFileName> <analyseParameterMutability>");
 		} else {
 			Boolean analyseParameterMutability = new Boolean(args[2]);
 			if (analyseParameterMutability) {
 				System.out.println("Parameter Mutability Analysis is turned on.");
 			} else {
 				System.out.println("Parameter Mutability Analysis is turned off.");
 			}
 			traceAnalyser = new PurityTraceAnalyser(args[0], args[1], true, analyseParameterMutability);
 			traceAnalyser.analyse(false, true);
 		}
 	}
 
 	/**
 	 * Gets the set of impure methods.
 	 */
 	public HashMap<MethodIdentifier, HashSet<String>> getImpureMethodIdentifiers() {
 		return impureMethodIdentifiers;
 	}
 
 	/**
 	 * Gets the set of pure methods.
 	 */
 	public HashMap<MethodIdentifier, HashSet<String>> getPureMethodIdentifiers() {
 		return pureMethodIdentifiers;
 	}
 
 	/**
 	 * Gets the set of executed methods.
 	 */
 	public HashMap<MethodIdentifier, HashSet<String>> getThisModifyingMethodIdentifiers() {
 		return thisModifyingMethodIdentifiers;
 	}
 
 	/**
 	 * Gets the set of executed methods.
 	 */
 	public HashMap<MethodIdentifier, HashSet<String>> getExecutedMethodIdentifiers() {
 		return executedMethodIdentifiers;
 	}
 
 
 	public static class ParameterMutabilityInformation implements Serializable {
 
 		private static final long serialVersionUID = 3550107163836583142L;
 
 		private MethodIdentifier methodIdentifier;
 
 		private HashMap<String, HashSet<Integer>> runtimeClassNameToUnmodifiedParametersMap;
 
 		private HashSet<Integer> parameters;
 
 		public ParameterMutabilityInformation(MethodIdentifier methodIdentifier) {
 			this.methodIdentifier = methodIdentifier;
 			this.runtimeClassNameToUnmodifiedParametersMap = new  HashMap<String, HashSet<Integer>>();
 			this.parameters = new HashSet<Integer>();
 		}
 
 		public MethodIdentifier getMethodIdentifier() {
 			return methodIdentifier;
 		}
 
 		public HashSet<Integer> getModifiedParameters() {
 			HashSet<Integer> unmodifiedParameters = getUnmodifiedParameters();
 			HashSet<Integer> result = new HashSet<Integer>(parameters);
 			result.removeAll(unmodifiedParameters);
 			return result;
 		}
 		
 		public HashSet<Integer> getUnmodifiedParameters() {
 			HashSet<Integer> result = new HashSet<Integer>();
 			for (int parameterId : parameters) {
 				boolean addParameterToResult = true;
 				for (String runtimeClass : runtimeClassNameToUnmodifiedParametersMap.keySet()) {
 					if (!runtimeClassNameToUnmodifiedParametersMap.get(runtimeClass).contains(parameterId)) {
 						addParameterToResult = false;
 					}
 				}
 				if (addParameterToResult) {
 					result.add(parameterId);
 				}
 			}
 			return result;
 		}
 		
 		public void updateUnmodifiedParameters(String runtimeClassName, HashSet<Integer> unmodifiedParameters) {
 			HashSet<Integer> oldUnmodifiedParameters = runtimeClassNameToUnmodifiedParametersMap.get(runtimeClassName);
 			if (oldUnmodifiedParameters == null) {
 				runtimeClassNameToUnmodifiedParametersMap.put(runtimeClassName, (HashSet<Integer>) unmodifiedParameters.clone());
 			} else {
 				HashSet<Integer> parametersToDelete = new HashSet<Integer>();
 				for (Integer unmodifiedParameter : oldUnmodifiedParameters) {
 					if (!unmodifiedParameters.contains(unmodifiedParameter)) {
 						parametersToDelete.add(unmodifiedParameter);
 					}
 				}	
 				for (Integer parameter : parametersToDelete) {
 					oldUnmodifiedParameters.remove(parameter);
 				}
 			}
 
 		}
 
 		public void addParameter(int parameterIndex) {
 			parameters.add(parameterIndex);
 		}
 
 		public HashSet<Integer> getParameters() {
 			return parameters;
 		}
 
 		public HashMap<String, HashSet<Integer>> getRuntimeClassNameToUnmodifiedParametersMap() {
 			return runtimeClassNameToUnmodifiedParametersMap;
 		}
 
 	}
 
 	public PurityResults getResults() {
 		return results;
 	}
 	
 	public HashMap<MethodIdentifier, ParameterMutabilityInformation> getParameterMutabilityInformation() {
 		return parameterMutabilityInformation;
 	}
 }