/*
 * Copyright 2009 Wishnu Prasetya.
 *
 * This file is part of T2.
 * T2 is free software; you can redistribute it and/or modify it under
 * the terms of the GNU General Public License (GPL) as published by the
 * Free Software Foundation; either version 3 of the License, or any
 * later version.
 * 
 * T2 is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 *
 * A copy of the GNU General Public License can be found in T2 distribution.
 * If it is missing, see http://www.gnu.org/licenses.
 */

package Sequenic.T2ext.CoverageEngine;

import java.lang.reflect.Method;
import java.util.*;
import java.io.*;
import java.util.concurrent.*;

import Sequenic.T2.*;
import Sequenic.T2.Seq.*;
import Sequenic.T2ext.Analyzer.*;
import Sequenic.T2ext.Instrumenter.*;

/**
 * This class is an implementation of the BaseEngine.
 * 
 * <p>
 * It provides a coverage engine implementing a semi-exhaustive search strategy.
 * This search algorithm can be shared by new subclasses, but a subclass will
 * then have an opportunity to e.g. more cleverly define the search domains.
 * With respect to search domains, this engine will just provide simplistic
 * approach for constructing them; a subclass should refine it.
 * 
 * <p>
 * The algorithm works as follows.
 * 
 * <p>
 * Let "sigma" be our target path. This is the path to cover. This engine will
 * first look at the provided coverage report to find a T2-test-trace "tau" that
 * produces an execution whose coverage distance to sigma is minimum. Let "z" be
 * the METARUN step in tau, that produces that closest execution meant above.
 * Note that this z can also be tau's creation step.
 * 
 * <p>
 * Tau is then copied to form a "base-trace"; this base-trace is a template from
 * which we will generate new traces to try out. The base-trace is first
 * "prepared". This engine does it by dropping all steps AFTER the best step,
 * because they are considered to be less important towards covering the target
 * path.
 * 
 * <p>
 * A subclass can override the method "prepareBaseTrace" to implement a
 * different preparation strategy.
 * 
 * <p>
 * We define the "parameters" of the base-trace to be its REF and CONST steps.
 * The general idea of this engine is to variate these parameters to hope to
 * cover sigma. However, varying all parameters will explode our search space.
 * So there is a method "setupParamsFrame" that will decide which parameters to
 * vary; these will be put in a set called "parameters frame".
 * 
 * <p>
 * This engine's selection strategy is as follows. Roughly said, select
 * k-parameters of the step "z" above, and those of previous steps if "z" has
 * too few parameters to fill-in k. Parameters of previous steps that do not
 * change the state of target object will be skipped.
 * 
 * <p>
 * A subclass may override setupParamsFrame to provide a different strategy of
 * parameters selection.
 * 
 * <p>
 * Next, we define for each parameter in the parameters-frame, what its (finite)
 * domain is. We will then vary this parameter over this domain. For each
 * parameter "p" in the parameter frame, we associate a "domain". This is set by
 * the method "setupDomains".
 * 
 * <p>
 * This engine will constructs the domains of CONST parameters using T2's
 * BaseDomainSmall. Parameters of REF-type will actually not be varied.
 * 
 * <p>
 * A subclass should override this method "setupDomains" to implement different
 * domains.
 * 
 * <p>
 * In the main loop we simply vary every parameter over its domain. For every
 * combination, a new trace is produced, executed, and its coverage is measured.
 * If sigma is covered, we are done. Else we keep track which trace delivers the
 * minimum distance to sigma. The main loop is also capped to a certain number
 * of combinations, so that we don't iterate too long (the search space can
 * indeed be huge). Furthermore, randomization is added so that the order in
 * which we draw values from each domain is random; so that we are not biased
 * towards certain patterns of combinations.
 * 
 * @author Wishnu Prasetya
 * 
 */

public class SemiExhaustiveEngine extends BaseEngine {

	/**
	 * Just the same target path, represented as the list of its node-ids.
	 */
	LinkedList<Integer> targetpathX;

	/**
	 * A copy of the test-trace that most closely covers the target path.
	 */
	Trace orgClosestTrace = null;

	/**
	 * This is the index of the particular step in orgClosestTrace that most
	 * closely covers the target path. If the index is negative, then the
	 * creation step is meant.
	 */
	Integer indexOfBestStep = null;

	/**
	 * The coverage distance of orgClosestTrace wrt to the targetpath.
	 */
	int orgDistance;

	/**
	 * The best observed execution path (generated by best-step above) that most
	 * closely comes to the target path.
	 */
	List<Integer> bestObservedPath = null;

	/**
	 * A base-trace forms the template-trace from which this engine produces new
	 * traces. The idea is to produce new traces by varying certain parameters
	 * of the base-trace.
	 * 
	 * <p>
	 * The base-trace is obtained by cloning orgClosestTrace, and dropping all
	 * steps AFTER the best-step in orgClosestTrace (because they presumed to be
	 * less relevant towards covering the target-path).
	 */
	Trace basetrace = null;

	/**
	 * This points to the step in the basetrace that most closely covers the
	 * target path. This should be a copy of the best step pointed to by
	 * indexOfBestStep.
	 */
	METARUN bestStep = null;

	/**
	 * The run-ID of the execution that most closely cover the target path.
	 */
	private Long runId;

	/**
	 * The maximum number of steps in the search. Each step correspond to the
	 * binding of a relevant parameter in the basetrace with a value from its
	 * domain. This is to prevent the search from running too long.
	 * 
	 * Default is 50000.
	 */
	public int MaxSteps = 50000;

	boolean debug = false;

	/**
	 * This defines our "parameters horizon". Suppose that this is K.
	 * 
	 * Out of all parameters in the parameters frame, only the first K
	 * parameters will be varied. This is used to limit the search space.
	 */
	int maxParamsHorizon = 5;

	/**
	 * The parameters-frame. This will be sorted in reverse order, such that the
	 * first parameters are those of the last step of the base trace.
	 */
	List<MkValStep> paramsFrame;

	/**
	 * Suppose the value of this field is K. This implies that only up-to K last
	 * parameters in paramsFrame will be variated. This is a mechanism to
	 * restrict the search space. The default is 5.
	 */
	int paramsFrameScope = 5;

	/**
	 * This maintains a mapping from each parameter in the parameters-frame to
	 * its finite domain.
	 */
	Map<MkValStep, List> domainTable;

	Random rnd = new Random();

	/**
	 * This will provide additional information about the target trace.
	 */
	T2TraceInspection traceInspection;

	public SemiExhaustiveEngine() {
		super();
	}

	/**
	 * Constructor; note the series of quite complex setups we need to do.
	 */
	public SemiExhaustiveEngine(T2TraceFileCoverageResult covReport_,
			T2TraceFileCoverageAnalyzer t2covAnalyzer_,
			LinkedList<Node> targetpath_) {

		super(covReport_, t2covAnalyzer_, targetpath_);

		// Setups; don't change the order:

		targetpathX = new LinkedList<Integer>();
		for (Node N : targetpath)
			targetpathX.add(N.getId());

		setupRunId();
		if (runId != null) {
			setupT2Trace();
			setupOrgDistance();
			prepareBaseTrace();
			traceInspection = new T2TraceInspection(basetrace, t2covAnalyzer
					.getC(), t2covAnalyzer.getPool(), t2covAnalyzer
					.getClassinvs());
			setupParamsFrame();
			setupDomains();
		}
	}

	/**
	 * Pre-cond: targetpath is a valid path and is not covered yet!
	 * 
	 * This recovers the runId of the execution-path that most closely covers
	 * the target-path.
	 */
	private void setupRunId() {
		assert targetpath != null;
		/*
		 * System.out.println(">>> Path to cover: ") ; for (Node N : targetpath)
		 * { System.out.print(N.getId() + " --> ") ; }
		 * System.out.print("EXIT,  of method " + CFG.getMethod()) ;
		 */
		CoverageResult coverage = covReport.totCoverage.get(CFG);
		// get the runID of the closest directly covering path
		runId = coverage.directlyClosestPaths.get(targetpath);
		/*
		 * if (runId==null) { throw new
		 * Error("Cannot find a T2-trace that covers the target path.") ; }
		 */
	}

	/**
	 * This calculates orgClosestTrace, set basetrace, bestStep etc.
	 */
	private void setupT2Trace() {
		// get the trace and step that deliver this runID:
		orgClosestTrace = (Trace) cloneObj(covReport.getTrace(runId));

		bestObservedPath = covReport.observedpaths.get(runId).getNodes();

		if (orgClosestTrace == null) {
			throw new Error(
					"Cannot find a T2-trace that covers the target path.");
		}

		indexOfBestStep = covReport.getStepIndex(runId);
		basetrace = (Trace) cloneObj(orgClosestTrace);

		// best step turns out to be the creation step:
		if (indexOfBestStep == 0)
			bestStep = basetrace.creation;
		else
			bestStep = basetrace.trace.get(indexOfBestStep - 1);
	}

	private Serializable cloneObj(Serializable t) {
		Serializable clone = null;
		try {
			clone = (Serializable) Sequenic.T2.Obj.Cloner.clone(t);
		} catch (Exception e) {
			throw new Error("Problem with cloning base-trace.", e);
		}
		return clone;
	}

	/**
	 * This method will prepare the base-trace before we vary it to generate new
	 * traces. This engine will drop all steps that comes AFTER the best step.
	 * The motivation is that we want to focus on improving the best step, and
	 * doing this by varying its parameters, or parameters of the steps that
	 * precede it. The steps after the best steps are therefore considered less
	 * important.
	 * 
	 * <p>
	 * Override this method in a subclass to implement a different preparation
	 * strategy.
	 */
	protected void prepareBaseTrace() {
		if (indexOfBestStep == 0) {
			basetrace.trace.clear();
		} else {
			// Drop the sufix after the bestStep; they are not relevant anymore.
			while (!basetrace.trace.isEmpty()
					&& basetrace.trace.getLast() != bestStep)
				basetrace.trace.removeLast();
		}
	}

	/**
	 * Calculate the distance of orgClosestTrace to the target path.
	 */
	private void setupOrgDistance() {
		Sensor.ejectObservations();
		assert ReportersPool.NULLreporter != null;
		executeT2Trace(orgClosestTrace);
		CoverageResult result = t2covAnalyzer.calculateCoverage().totCoverage
				.get(CFG);
		// now calculate the distance:
		Long runid = result.directlyClosestPaths.get(targetpath);
		ObservedPath execpath = Sensor.getObservedPaths().get(runid);
		orgDistance = distCalculator.directCoveragePathDistance(execpath
				.getNodes(), targetpathX);
	}

	/**
	 * This will setup the parameters frame over the base-trace. Note this
	 * presumes that basetrace has been made so that its best step is its last
	 * one.
	 * 
	 * <p>
	 * The parameters have to be sorted in reverse order.
	 * 
	 * <p>
	 * REF-type params will be excluded. Currently only integer-like CONST
	 * params are included.
	 * 
	 * <p>
	 * Override this to implement different strategy to select parameters.
	 */
	protected void setupParamsFrame() {
		paramsFrame = new LinkedList<MkValStep>();
		List<MkValStep> params = traceInspection.getParams(0, basetrace.trace
				.size() + 1, true);
		// Reverse the order of params, and put them in paramsFrame:
		int n = params.size();
		while (0 < n) {
			n--;
			MkValStep P = params.get(n);
			if (P instanceof CONST && isPrimitiveCONST((CONST) P)) {
				paramsFrame.add(P);
			}
		}
	}

	static public Class typeOfCONST(CONST C) {
		if (C.val != null)
			return C.val.getClass();
		return C.C;
	}

	private boolean isIntegerLikeCONST(CONST CONST) {
		Class C = typeOfCONST(CONST);
		return (C == Integer.class) || (C == Integer.TYPE)
				|| (C == Short.class) || (C == Short.TYPE) || (C == Byte.class)
				|| (C == Byte.TYPE) || (C == Long.class) || (C == Long.TYPE);
	}

	private boolean isPrimitiveCONST(CONST CONST) {
		Class C = typeOfCONST(CONST);
		return isIntegerLikeCONST(CONST) || (C == Boolean.class)
				|| (C == Boolean.TYPE) || (C == String.class)
				|| (C == Character.class) || (C == Character.TYPE);
	}

	/**
	 * Construct the domain of each parameter in the parameters-frame. We'll
	 * just pull of the domain from the BaseDomainSmall.
	 * 
	 * <p>
	 * Override this to implement different domains.
	 */
	protected void setupDomains() {

		domainTable = new HashMap<MkValStep, List>();
		BaseDomainSmall BDS = new BaseDomainSmall();
		for (MkValStep P : paramsFrame) {
			CONST CONST = (CONST) P;
			Class C = typeOfCONST(CONST);
			List domain = new LinkedList();
			if (isIntegerLikeCONST(CONST)) {
				for (int i = -3; i < BDS.getRange() - 3; i++) {
					if (C == Integer.class || C == Integer.TYPE)
						domain.add(new Integer(i));
					if (C == Long.class || C == Long.TYPE)
						domain.add(new Long(i));
					if (C == Short.class || C == Short.TYPE)
						domain.add(new Short((short) i));
					if (C == Byte.class || C == Byte.TYPE)
						domain.add(new Byte((byte) i));
				}
			}
			// Just for testing:
			// if (C == Integer.class) domain.add(new Integer(13)) ;
			if (C == Boolean.class || C == Boolean.TYPE) {
				domain.add(new Boolean(true));
				domain.add(new Boolean(false));
			}
			if (C == Character.class || C == Character.TYPE) {
				char[] chars = BDS.getCharsupply();
				for (int i = 0; i < chars.length; i++)
					domain.add(new Character(chars[i]));
			}
			if (C == String.class) {
				String[] strings = BDS.getStringsupply();
				for (int i = 0; i < strings.length; i++)
					domain.add(new String(strings[i]));
			}
			domainTable.put(P, domain);
		}
	}

	/**
	 * Just returning the domain of the given parameter.
	 */
	protected List getDomain(MkValStep param) {
		return domainTable.get(param);
	}

	/**
	 * The main method; for generating new traces.
	 */
	@Override
	public LinkedList<Pair<Trace, Integer>> generateTraces() {

		if (debug) {
			if (runId == null)
				System.out.println(">>> Can't find a base execution path.");
			else {
				System.out.println("\n>>> #basetrace: "
						+ basetrace.trace.size());
				System.out.println("Best observed execution path: ");
				for (Integer N : bestObservedPath) {
					System.out.print(N + " --> ");
				}
				System.out.print("EXIT  ");

				System.out.println(">>> beststep: " + bestStep);
				System.out.println(">>> basetrace:");
				simplePrintTrace(basetrace);
				System.out.println(">>> #paramsFrame: " + paramsFrame.size());
				for (MkValStep P : paramsFrame) {
					System.out.print("Param " + P + " domain: ");
					List domain = domainTable.get(P);
					for (Object o : domain)
						System.out.print(o + ", ");
					System.out.println("");
				}
			}
		}

		newTraces.clear();
		// No execution could be found:
		if (runId == null)
			return newTraces;
		// Else search:
		bestTraceFoundSofar = null;
		bestDistanceSoFar = orgDistance;
		search(0, MaxSteps);
		if (bestTraceFoundSofar != null)
			newTraces.add(new Pair(bestTraceFoundSofar, bestDistanceSoFar));

		return newTraces;
	}

	private Trace bestTraceFoundSofar;
	private int bestDistanceSoFar;
	private PathDistanceCalculator distCalculator = new PathDistanceCalculator();

	/**
	 * The worker of generateTraces.
	 * 
	 * This will try all combinations of the constants on each position in
	 * paramsFrame. You can pass a quota to break off the search when the quota
	 * becomes 0.
	 */
	private int search(int k, int quotaleft) {

		// Break off if we have no computation quota left:
		if (quotaleft == 0)
			return 0;

		// base case, then we have generated a full permutation;
		// perform the trace, and calculate coverage:
		if (k >= Math.min(maxParamsHorizon, paramsFrame.size())) {
			Sensor.ejectObservations();
			executeT2Trace(basetrace);
			CFGBunchFile CFGs = t2covAnalyzer.getCOVanalyzer().getCFGs();
			CoverageAnalyzer analz = new CoverageAnalyzer(CFGs);
			CoverageResult result = analz.calculateMethodCoverage(CFG);
			// result.simplePrint(Sensor.getObservedPaths()) ;
			// the target path is directly covered!
			if (result.directlyCoveredPaths.contains(targetpath)) {
				bestTraceFoundSofar = (Trace) cloneObj(basetrace);
				bestDistanceSoFar = 0;
				if (debug) {
					System.out.println(">>> Target path FOUND!");
				}
				// return 0 to prevent further recursion elsewhere:
				return 0;
			}
			// else calculate the distance:
			Long runid = result.directlyClosestPaths.get(targetpath);
			// assert runid != null ;
			ObservedPath execpath = Sensor.getObservedPaths().get(runid);
			// assert execpath != null ;
			int dist = distCalculator.directCoveragePathDistance(execpath
					.getNodes(), targetpathX);
			if (dist < bestDistanceSoFar)
				bestTraceFoundSofar = (Trace) cloneObj(basetrace);
			return quotaleft - 1;
		}
		// else recursion:
		// Get the next parameters to variate:
		MkValStep P = paramsFrame.get(k);
		CONST C = (CONST) P;
		// Retrieve the domain for this parameter:
		List domain = getDomain(P);
		// Now quantify over the domain, and continue recursion:
		// We also randomize the order with which the values in the domain are
		// picked:
		int qleft = quotaleft;
		int[] choices = generateRandomPermutation(domain.size());
		for (int i = 0; i < choices.length; i++) {
			C.val = domain.get(choices[i]);
			qleft--;
			qleft = search(k + 1, qleft);
			if (qleft <= 0)
				break;
		}
		return qleft;
	}

	/**
	 * Will generate a random permutation of numbers in [0..size).
	 */
	int[] generateRandomPermutation(int size) {
		int[] res = new int[size];
		ArrayList<Integer> a = new ArrayList<Integer>(size);
		for (int i = 0; i < size; i++)
			a.add(i);
		for (int i = 0; i < size; i++) {
			int k = rnd.nextInt(size - i);
			res[i] = a.remove(k);
		}
		return res;
	}

	static public void simplePrintTrace(Trace tr) {
		System.out.println("   [0] " + tr.creation);
		int i = 1;
		for (TraceStep S : tr.trace) {
			System.out.println("   [" + i + "] " + S);
			i++ ;
		}
	}

	static public void main(String[] args) {
		Engine_10 E = new Engine_10();
		int[] perm = E.generateRandomPermutation(10);
		System.out.print(">>> ");
		for (int i = 0; i < perm.length; i++)
			System.out.print(perm[i] + " , ");
	}

}