/**
 * <copyright>
 * Copyright (c) 2010-2014 Henshin developers. All rights reserved. 
 * This program and the accompanying materials are made available 
 * under the terms of the Eclipse Public License v1.0 which 
 * accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 * </copyright>
 */
package org.eclipse.emf.henshin.interpreter.util;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

import org.eclipse.emf.common.util.EList;
import org.eclipse.emf.ecore.EAttribute;
import org.eclipse.emf.ecore.EClass;
import org.eclipse.emf.ecore.EObject;
import org.eclipse.emf.ecore.EPackage;
import org.eclipse.emf.ecore.EReference;
import org.eclipse.emf.ecore.impl.DynamicEObjectImpl;
import org.eclipse.emf.ecore.resource.Resource;
import org.eclipse.emf.ecore.util.EcoreUtil;
import org.eclipse.emf.henshin.interpreter.ApplicationMonitor;
import org.eclipse.emf.henshin.interpreter.Assignment;
import org.eclipse.emf.henshin.interpreter.EGraph;
import org.eclipse.emf.henshin.interpreter.Engine;
import org.eclipse.emf.henshin.interpreter.Match;
import org.eclipse.emf.henshin.interpreter.RuleApplication;
import org.eclipse.emf.henshin.interpreter.UnitApplication;
import org.eclipse.emf.henshin.interpreter.impl.AssignmentImpl;
import org.eclipse.emf.henshin.interpreter.impl.EGraphImpl;
import org.eclipse.emf.henshin.interpreter.impl.UnitApplicationImpl;
import org.eclipse.emf.henshin.model.Module;
import org.eclipse.emf.henshin.model.Node;
import org.eclipse.emf.henshin.model.Parameter;
import org.eclipse.emf.henshin.model.ParameterKind;
import org.eclipse.emf.henshin.model.Rule;
import org.eclipse.emf.henshin.model.Unit;

/**
 * Common utility methods for the Henshin interpreter.
 * 
 * @author Christian Krause, Svetlana Arifulina
 */
public class InterpreterUtil {

	/**
	 * Class Loader implementation that can delegate the class loading to multiple additional class loaders. <br>
	 * <b>WARNING: This class loader delegates only the methods {@link #loadClass(String)}!</b>
	 * 
	 * @author Christian Krause
	 *
	 */
	public static class DelegatingClassLoader extends ClassLoader {

		/**
		 * Array of additional class loaders.
		 */
		private ClassLoader[] additionalClassLoaders;

		/**
		 * Default constructor.
		 * 
		 * @param parent Parent class loader.
		 * @param additionalClassLoaders Additional class loaders.
		 */
		public DelegatingClassLoader(ClassLoader parent, ClassLoader... additionalClassLoaders) {
			super(parent);
			this.additionalClassLoaders = additionalClassLoaders;
		}

		/*
		 * (non-Javadoc)
		 * 
		 * @see java.lang.ClassLoader#loadClass(java.lang.String)
		 */
		@Override
		public Class<?> loadClass(String name) throws ClassNotFoundException {
			Class<?> clazz;
			try {
				clazz = super.loadClass(name);
			} catch (ClassNotFoundException e) {
				clazz = null;
			}
			if (clazz == null) {
				for (ClassLoader other : additionalClassLoaders) {
					try {
						clazz = other.loadClass(name);
						break;
					} catch (ClassNotFoundException e) {
						clazz = null;
					}
				}
			}
			if (clazz == null) {
				throw new ClassNotFoundException();
			}
			return clazz;
		}

	}

	/**
	 * Find all matches for a rule.
	 * 
	 * @param engine Engine.
	 * @param rule Rule to be matched.
	 * @param graph Target graph.
	 * @param partialMatch Partial match or <code>null</code>.
	 * @return List of found matches.
	 */
	public static List<Match> findAllMatches(Engine engine, Rule rule, EGraph graph, Match partialMatch) {
		List<Match> matches = new ArrayList<Match>();
		for (Match match : engine.findMatches(rule, graph, partialMatch)) {
			matches.add(match);
		}
		return matches;
	}

	/**
	 * Find all matches of all rules in a module. This does not consider submodules.
	 * 
	 * @param engine Engine to be used.
	 * @param module Module to be used.
	 * @param graph Target graph.
	 * @return List of matches.
	 */
	public static List<Match> findAllMatches(Engine engine, Module module, EGraph graph) {
		List<Match> matches = new ArrayList<Match>();
		for (Unit unit : module.getUnits()) {
			if (unit instanceof Rule) {
				matches.addAll(findAllMatches(engine, (Rule) unit, graph, null));
			}
		}
		return matches;
	}

	/**
	 * This method calculates a complete match for rules of the given model transformation with a given model. If a
	 * complete match does not exist, the method calculates a partial match, if it exists. For that a rule is reduced
	 * till a complete match for a reduced rule is found. For reduced rules having the same size, all matches are
	 * searched. If a match is found for a reduced rule, this rule is not reduced further.
	 * 
	 * @param engine Engine to be used.
	 * @param module Module to be used.
	 * @param graph Target graph.
	 * @return List of matches (both complete and partial per rule)
	 */
	public static List<Match> findMaximalPartialMatches(Engine engine, Module module, EGraph graph) {
		List<Match> matches = new ArrayList<Match>();
		int reductionDepth = 2;

		for (Unit unit : module.getUnits()) {
			if (unit instanceof Rule) {
				List<Match> newMatches = new ArrayList<Match>();

				// Check for a complete match
				newMatches = findAllMatches(engine, (Rule) unit, graph, null);

				// If there are no complete matches, check for partial matches
				if (newMatches.isEmpty()) {
					newMatches = findPartialMatchesPerRule((Rule) unit, engine, graph, reductionDepth);
				}

				// If any partial matches were found then remove empty and
				// duplicate matches, which arise during the rule reduction
				if (!newMatches.isEmpty()) {
					matches.addAll(removeEmptyAndDuplicatedMatches(newMatches));

				}
			}
		}

		return matches;
	}
	

	/**
	 * This method calculates a complete match for rules of the given model transformation with a given model. If a
	 * complete match does not exist, the method calculates a partial match, if it exists. For that a rule is reduced
	 * till a complete match for a reduced rule is found. For reduced rules having the same size, all matches are
	 * searched. If a match is found for a reduced rule, this rule is not reduced further.
	 * 
	 * @param engine Engine to be used.
	 * @param module Module to be used.
	 * @param graph Target graph.
	 * @return List of matches (both complete and partial per rule)
	 */
	public static Match findMaximalPartialMatch(Engine engine, Module module, EGraph graph) {
//		List<Match> matches = new ArrayList<Match>();
		int reductionDepth = 2;

		for (Unit unit : module.getUnits()) {
			if (unit instanceof Rule) {
					Match match = findPartialMatchPerRule((Rule) unit, engine, graph, reductionDepth);

					if (match != null)
						return match;
				// If any partial matches were found then remove empty and
				// duplicate matches, which arise during the rule reduction
//				if (!newMatches.isEmpty()) {
//					matches.addAll(removeEmptyAndDuplicatedMatches(newMatches));
//
//				}
			}
		}

		return null;
	}


	/**
	 * This method is similar to the method findMasimalPartialMatches but outputs a report instead of a list of matches.
	 * 
	 * This method calculates a complete match for rules of the given model transformation with a given model. If a
	 * complete match does not exist, the method calculates a partial match, if it exists. For that a rule is reduced
	 * till a complete match for a reduced rule is found. For reduced rules having the same size, all matches are
	 * searched. If a match is found for a reduced rule, this rule is not reduced further. If partial matches are found,
	 * then a report object is created based on the list of found partial matches.
	 * 
	 * @param engine Engine to be used.
	 * @param module Module to be used.
	 * @param graph Target graph.
	 * @return List of matches (both complete and partial per rule)
	 */
	public static PartialMatchReport findAndReportMaximalPartialMatches(Engine engine, Module module, EGraph graph) {
		List<Match> matches = new ArrayList<Match>();
		PartialMatchReport partialMatchReport = new PartialMatchReport(module, matches);
		int reductionDepth = 2;
		
		for (Unit unit : module.getUnits()) {
			if (unit instanceof Rule) {

				List<Match> newMatches = new ArrayList<Match>();

				// Check for a complete match
				newMatches = findAllMatches(engine, (Rule) unit, graph, null);

				// Check whether disabling of the dangling edges check would
				// lead to a match
				if (newMatches.isEmpty()) {
					// Check for partial matches
					newMatches = findPartialMatchesPerRule((Rule) unit, engine, graph, reductionDepth);
				}

				if (!newMatches.isEmpty()) {
					newMatches = removeEmptyAndDuplicatedMatches(newMatches);
				}

				partialMatchReport.collectPartialMatchInfos((Rule) unit, newMatches);
				matches.addAll(newMatches);
			}
		}

		return partialMatchReport;

	}



	/**
	 * Method for removing empty and duplicated matches, which appear during the rule reduction.
	 * 
	 * @param matches Matches to reduce
	 * @return A reduced list of matches without duplicates and empty entries
	 */
	private static List<Match> removeEmptyAndDuplicatedMatches(List<Match> matches) {
		List<Match> resultingMatches = new ArrayList<Match>();

		// When computing partial matches, matches with no matching elements are
		// sometimes added into the resulting list of matches. Here these
		// matches are deleted from the list.
		for (Match match : matches) {
			if (!match.getNodeTargets().isEmpty()) {
				boolean addMatch = true;
				// Ignore duplicates
				for (Match resultingMatch : resultingMatches) {
					if (match.getNodeTargets().containsAll(resultingMatch.getNodeTargets())
							& resultingMatch.getNodeTargets().containsAll(match.getNodeTargets())) {
						addMatch = false;
						break;
					}
				}
				if (addMatch) {
					resultingMatches.add(match);
				}
			}
		}

		return resultingMatches;
	}


	/**
	 * Establishes that the set of multi-matches for the given multi-rule
	 * is overlap-free, i.e., no object in the input model is a node target
	 * of more than one multi-match.
	 * 
	 * @param match match with a list of multi-matches for the given multi-rule
	 * @param multiRule multi-rule 
	 * @return A reduced list of matches without duplicate target nodes
	 */
	public static List<Match> removeOverlappingMultiMatches(Match match, Rule multiRule) {
		List<Match> remainingMatches = new ArrayList<Match>();

		for (Match m : match.getMultiMatches(multiRule)) {
			boolean addMatch = true;
			for (Match resultingMatch : remainingMatches) {

				// Compare node targets
				for (EObject eo : resultingMatch.getNodeTargets()) {
					if (m.getNodeTargets().contains(eo)) {
						addMatch = false;
						break;
					}
				}
				if (!addMatch) {
					break;
				}
			}
			if (addMatch) {
				remainingMatches.add(m);
			}
		}

		return remainingMatches;
	}
	
	/**
	 * This method finds a partial match per rule from the given module or for an already reduced rule.
	 * 
	 * @param rule Rule to find partial matches for.
	 * @param engine Engine to be used.
	 * @param graph Target graph.
	 * @return The list of partial matches.
	 */
	private static List<Match> findPartialMatchesPerRule(Rule rule, Engine engine, EGraph graph, int reductionDepth) {
		List<Match> matches = new ArrayList<Match>();
		
		if (reductionDepth > 0) {
			// Reduce the rule and get as a result a list of rules, each having 1 node less and the input rule
			List<Rule> newRules = reduceRule(rule);
			reductionDepth--;
			
			// Find matches for the reduced rules
			for (Rule newRule : newRules) {
				matches.addAll(findAllMatches(engine, newRule, graph, null));
			}

			// If no matches for the reduced rules were found, call the method recursively for these reduced rules
			// Always goes down to reduction depth 0
			if (reductionDepth > 0 && matches.isEmpty()) {
				for (Rule newRule : newRules) {
					matches.addAll(findPartialMatchesPerRule(newRule, engine, graph, reductionDepth));
				}
				reductionDepth--;
			}
		}

		// if a rule has only 1 node than no reduction possible and null is
		// returned
		return matches;
	}


	/**
	 * This method finds a partial match per rule from the given module or for an already reduced rule.
	 * 
	 * @param rule Rule to find partial matches for.
	 * @param engine Engine to be used.
	 * @param graph Target graph.
	 * @return The list of partial matches.
	 */
	private static Match findPartialMatchPerRule(Rule rule, Engine engine, EGraph graph, int reductionDepth) {
		if (reductionDepth > 0) {
			// Reduce the rule and get as a result a list of rules, each having 1 node less and the input rule
			List<Rule> newRules = reduceRule(rule);
			reductionDepth--;
			
			// Find matches for the reduced rules
			for (Rule newRule : newRules) {
				Iterator<Match> it = engine.findMatches(rule, graph, null).iterator();
				if (it.hasNext())
					return it.next();
			}

			// If no matches for the reduced rules were found, call the method recursively for these reduced rules
			// Always goes down to reduction depth 0
			if (reductionDepth > 0) {
				for (Rule newRule : newRules) {
					Match match = findPartialMatchPerRule(newRule, engine, graph, reductionDepth);
					if (match != null)
						return match;
				}
				reductionDepth--;
			}
		}

		return null;
	}

	
	/**
	 * Reduce the input rule and output a list of rules, in which each rule is exactly 1 node smaller than the input
	 * rule. The size of the list equals to the number of nodes of the input rule.
	 * 
	 * @param rule Rule to reduce.
	 * @return List of reduced rules.
	 */
	private static List<Rule> reduceRule(Rule rule) {
		// If the input rule has N nodes in the LHS, then output a set of N
		// rules, in which each rule is exactly 1 node less that the input rule
		// has (the size of each rule in the set is N-1)
		List<Rule> newRules = new ArrayList<Rule>();
		EList<Node> nodes = rule.getLhs().getNodes();

		// Copy all the nodes from the input rule in the N rules of the output
		// set
		for (int i = 0; i < nodes.size(); i++) {
			// Create a new reduced rule by copying the original one
			Rule newRule = EcoreUtil.copy(rule);
			// Remove the current node from the reduced rule
			newRule.getLhs().removeNode(newRule.getLhs().getNodes().get(i));
			// Add the new rule to the list of new rules
			newRules.add(newRule);
		}

		return newRules;
	}

	/**
	 * Execute the given unit application and throws an {@link AssertionError} if it could not be successfully applied
	 * (if {@link UnitApplication#execute(ApplicationMonitor)} returns <code>false</code>). This is just a convenience
	 * method.
	 * 
	 * @param application A unit application.
	 */
	public static void executeOrDie(UnitApplication application) {
		if (!application.execute(null)) {
			if (application instanceof RuleApplication) {
				throw new AssertionError("Error executing rule '" + application.getUnit().getName() + "'");
			} else {
				throw new AssertionError("Error executing unit '" + application.getUnit().getName() + "'");
			}
		}
	}

	/**
	 * Apply a unit to the contents of a resource. This automatically creates an {@link EGraph} and updates the contents
	 * of the resource.
	 * 
	 * @param unit Unit to be applied.
	 * @param engine Engine to be used.
	 * @param resource Resource containing the model to be transformed.
	 * @return <code>true</code> if the unit was successfully applied.
	 */
	public static boolean applyToResource(Unit unit, Engine engine, Resource resource) {
		return applyToResource(new AssignmentImpl(unit), engine, resource, null);
	}

	/**
	 * Apply a unit to the contents of a resource. This automatically creates an {@link EGraph} and updates the contents
	 * of the resource.
	 * 
	 * @param assignment Assignment to be used.
	 * @param engine Engine to be used.
	 * @param resource Resource containing the model to be transformed.
	 * @param monitor Monitor to collect performance data
	 * @return <code>true</code> if the unit was successfully applied.
	 */
	public static boolean applyToResource(Assignment assignment, Engine engine, Resource resource,
			ApplicationMonitor monitor) {

		// Create the graph and the unit application:
		EGraph graph = new EGraphImpl(resource);
		UnitApplication application = new UnitApplicationImpl(engine, graph, assignment.getUnit(), assignment);

		// Remember the old root objects:
		Set<EObject> oldRoots = new HashSet<EObject>();
		oldRoots.addAll(graph.getRoots());

		// Apply the unit:
		boolean result = application.execute(monitor);

		// Sync root objects:
		List<EObject> roots = graph.getRoots();
		Iterator<EObject> it = resource.getContents().iterator();
		while (it.hasNext()) {
			if (!roots.contains(it.next())) {
				it.remove();
			}
		}
		for (EObject root : roots) {
			if (!oldRoots.contains(root)) {
				resource.getContents().add(root);
			}
		}
		return result;

	}

	/**
	 * Check whether two {@link EGraph}s are isomorphic.
	 * 
	 * @param graph1 First graph.
	 * @param graph2 Second graph.
	 * @return <code>true</code> if they are isomorphic.
	 */
	public static boolean areIsomorphic(EGraph graph1, EGraph graph2) {
		return new EGraphIsomorphyChecker(graph1, null).isIsomorphicTo(graph2, null);
	}

	/**
	 * Check whether the contents of two resources are isomorphic.
	 * 
	 * @param resource1 First resource.
	 * @param resource2 Second resource.
	 * @return <code>true</code> if they are isomorphic.
	 */
	public static boolean areIsomorphic(Resource resource1, Resource resource2) {
		return areIsomorphic(new EGraphImpl(resource1), new EGraphImpl(resource2));
	}

	/**
	 * Count the number of edges/links in a graph.
	 * 
	 * @param graph An {@link EGraph}
	 * @return Number of edges/links in that graph.
	 */
	public static int countEdges(EGraph graph) {
		int links = 0;
		for (EObject object : graph) {
			for (EReference ref : object.eClass().getEAllReferences()) {
				if (ref.isMany()) {
					links += ((EList<?>) object.eGet(ref)).size();
				} else {
					if (object.eGet(ref) != null)
						links++;
				}
			}
		}
		return links;
	}

	/**
	 * Get a string representation of an object.
	 * 
	 * @param object An object.
	 * @return A readable string representation.
	 */
	public static String objectToString(Object object) {
		if (object instanceof String) {
			return "'" + object + "'";

		}
		if (object instanceof DynamicEObjectImpl) {
			EClass eclass = ((DynamicEObjectImpl) object).eClass();
			if (eclass != null) {
				String type = eclass.getName();
				EPackage epackage = eclass.getEPackage();
				while (epackage != null) {
					type = epackage.getName() + "." + type;
					epackage = epackage.getESuperPackage();
				}
				String args = "";
				for (EAttribute att : eclass.getEAllAttributes()) {
					args = args + ", " + att.getName() + "=" + objectToString(((DynamicEObjectImpl) object).eGet(att));
				}

				return type + "@" + Integer.toHexString(object.hashCode()) + " (dynamic" + args + ")";
			}
		}
		return String.valueOf(object); // object could be null
	}
	
	/**
	 * Finds a single {@link Match} for a {@link Rule}.
	 * 
	 * @param engine The {@link Engine}.
	 * @param rule Rule to be matched.
	 * @param graph Target graph.
	 * @param partialMatch Partial match or <code>null</code>.
	 * @return a {@link Match} or <code>null</code>.
	 */
	public Match findSingleMatch(Engine engine, Rule rule, EGraph graph, Match partialMatch){
		Match match = null;
		Iterable<Match> iterable =  engine.findMatches(rule, graph, partialMatch);
		try {
			match = iterable.iterator().next();
		} catch (NoSuchElementException e) {
			// no matches.
		}
		return match;
	}
	
	/**
	 * Check whether the {@link Rule} is applicable on the {@link EGraph}.
	 * 
	 * @param engine The {@link Engine}.
	 * @param rule Rule to be matched.
	 * @param graph Target graph.
	 * @param partialMatch Partial match or <code>null</code>.
	 * @return <code>true</code> if the <code>rule<code> is applicable on the <code>graph<code>.
	 */
	public boolean isApplicable(Engine engine, Rule rule, EGraph graph, Match partialMatch){
		Match match = this.findSingleMatch(engine, rule, graph, partialMatch);
		return (match != null) ? true : false;
	}

	/**
	 * Check whether all {@link Parameter} of {@link ParameterKind} IN and INOUT of the {@link Unit} are set.
	 *
	 * @param parameters All {@link Parameter} of the unit.
	 * @param unitName The name of the {@link Unit}.
	 * @param assignment The current {@link Assignment} of the {@link UnitApplication}.
	 */
	public static void areNecessaryParametersSet(Iterable<Parameter> parameters, String unitName,
			Assignment assignment) throws IllegalStateException {
		for (Parameter param : parameters) {
			ParameterKind kind = param.getKind();
			if((kind == ParameterKind.INOUT || kind == ParameterKind.IN) &&
					(assignment == null || assignment.getParameterValue(param) == null)) {
				throw new IllegalStateException(unitName + ": " + kind + " Parameter " + param.getName() + " not set");
			}
		}
	}
}
