/*******************************************************************************
 * Copyright (c) 2016, 2017 Willink Transformations and others.
 * 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
 *
 * Contributors:
 *   E.D.Willink - Initial API and implementation
 *******************************************************************************/
package org.eclipse.qvtd.compiler.internal.qvts2qvts.merger;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.jdt.annotation.Nullable;
import org.eclipse.ocl.pivot.CompleteClass;
import org.eclipse.ocl.pivot.Property;
import org.eclipse.ocl.pivot.utilities.ClassUtil;
import org.eclipse.qvtd.compiler.internal.qvtm2qvts.RegionUtil;
import org.eclipse.qvtd.pivot.qvtschedule.BasicMappingRegion;
import org.eclipse.qvtd.pivot.qvtschedule.Edge;
import org.eclipse.qvtd.pivot.qvtschedule.MappingRegion;
import org.eclipse.qvtd.pivot.qvtschedule.NavigableEdge;
import org.eclipse.qvtd.pivot.qvtschedule.Node;

import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

class Correlator
{
	public static @Nullable Correlator correlate(@NonNull MappingRegion secondaryRegion, @NonNull MappingRegion primaryRegion, @NonNull CorrelationStrategy strategy, @Nullable Map<@NonNull Node, @NonNull Node> primaryNode2secondaryNode) {
		if (secondaryRegion instanceof BasicMappingRegion) {
			if (((BasicMappingRegion)secondaryRegion).getReferredMapping().isIsAbstract()) {
				return null;
			}
		}
		if (primaryRegion instanceof BasicMappingRegion) {
			if (((BasicMappingRegion)primaryRegion).getReferredMapping().isIsAbstract()) {
				return null;
			}
		}
		Correlator correlator = new Correlator(primaryRegion, secondaryRegion, strategy, primaryNode2secondaryNode);
		return correlator.correlate() ? correlator : null;
	}

	private static interface CorrelationStrategy
	{
		boolean navigableEdgesMatch(@NonNull NavigableEdge secondaryEdge, @Nullable NavigableEdge primaryEdge);
		//		boolean navigableIntermediateNodesMatch(@NonNull Node secondaryNode, @NonNull Node primaryNode);
		//		boolean navigableNodeMaybeUnmatched(@NonNull Node secondaryNode);
		boolean navigableNodesMatch(@NonNull Node secondaryNode, @Nullable Node primaryNode);
	}

	static abstract class AbstractCorrelationStrategy implements CorrelationStrategy
	{
		protected final boolean debugFailures = AbstractMerger.FAILURE.isActive();

		@Override
		public boolean navigableEdgesMatch(@NonNull NavigableEdge secondaryEdge, @Nullable NavigableEdge primaryEdge) {
			return true;
		}

		@Override
		public boolean navigableNodesMatch(@NonNull Node secondaryNode, @Nullable Node primaryNode) {
			if (primaryNode == null) {
				if (secondaryNode.isPredicated()) {
					if (debugFailures) {
						AbstractMerger.FAILURE.println("Missing predicated match for : " + secondaryNode);
					}
					return false;
				}
				return true;
			}
			else {
				assert secondaryNode.isExplicitNull() == primaryNode.isExplicitNull();
				return true;
			}
		}

		//		@Override
		//		public boolean navigableIntermediateNodesMatch(@NonNull Node secondaryNode, @NonNull Node primaryNode) {
		//			if (secondaryNode.isExplicitNull() != primaryNode.isExplicitNull()) {
		//				return false;
		//			}
		//			return true;
		//		}
	}

	protected final @NonNull MappingRegion primaryRegion;
	protected final @NonNull MappingRegion secondaryRegion;
	protected final @NonNull CorrelationStrategy strategy;
	protected final @NonNull Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = new HashMap<>();
	protected final @NonNull Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2primaryNodes;
	protected final boolean debugFailures = AbstractMerger.FAILURE.isActive();

	protected Correlator(@NonNull MappingRegion primaryRegion, @NonNull MappingRegion secondaryRegion, @NonNull CorrelationStrategy strategy, @Nullable Map<@NonNull Node, @NonNull Node> primaryNode2secondaryNode) {
		this.primaryRegion = primaryRegion;
		this.secondaryRegion = secondaryRegion;
		this.strategy = strategy;
		this.completeClass2primaryNodes = RegionUtil.getCompleteClass2Nodes(primaryRegion);
		if (primaryNode2secondaryNode != null) {
			for (Map.Entry<@NonNull Node, @NonNull Node> entry : primaryNode2secondaryNode.entrySet()) {
				secondaryNode2primaryNode.put(entry.getValue(), entry.getKey());
			}
		}
	}

	protected boolean correlate() {
		//
		//	Find the unambiguous head-node matches
		//
		if (!correlateHeadNodes()) {
			return false;
		}
		//
		//	Accumulate the transitive navigation from the head nodes. All common navigation edges must have compatible node types.
		//
		if (!correlateNavigablePredicates()) { // FIXME this may be more efficient but it's a pig to debug, rewrite as intersection then no-extra-predicates
			return false;
		}
		Set<@NonNull Node> navigableNodes = secondaryNode2primaryNode.keySet();
		//
		//	Accumulate the transitive computation to the true nodes. All common computation edges must have compatible node types.
		//
		if (!correlateComputedPredicates()) {
			return false;
		}
		//
		//	Accumulate the remaining node pairings from computations enriching the navigable nodes.
		//
		correlateResidualComputations(navigableNodes);
		return true;
	}

	/**
	 * Return true if the tree of computation nodes for firstNode and secondNode are equivalent
	 * assigning equivalences to first2second.
	 */
	protected boolean correlateComputation(@NonNull Node firstNode, @NonNull Node secondNode, @NonNull Map<@NonNull Node, @NonNull Node> first2second) {
		Node node = first2second.get(firstNode);
		if (node != null) {
			return node == secondNode;
		}
		if (firstNode.getNodeRole() != secondNode.getNodeRole()) {
			return false;
		}
		if (!ClassUtil.safeEquals(firstNode.getName(), secondNode.getName())) {		// FIXME stronger e.g. referredOperation
			return false;
		}
		Map<@NonNull Node, @NonNull Node> nestedFirst2second = new HashMap<>(first2second);
		nestedFirst2second.put(firstNode, secondNode);
		List<@NonNull Edge> residualSecondArgumentEdges = Lists.newArrayList(secondNode.getArgumentEdges());
		for (@NonNull Edge firstEdge : firstNode.getArgumentEdges()) {
			boolean gotIt = false;
			for (@NonNull Edge secondEdge : residualSecondArgumentEdges) {
				if (ClassUtil.safeEquals(firstEdge.getName(), secondEdge.getName())) {
					if (!correlateComputation(firstEdge.getEdgeSource(), secondEdge.getEdgeSource(), nestedFirst2second)) {
						return false;
					}
					gotIt = true;
					residualSecondArgumentEdges.remove(secondEdge);
					break;
				}
			}
			if (!gotIt) {
				return false;
			}
		}
		first2second.putAll(nestedFirst2second);
		return true;
	}

	/**
	 *	Return true if all the computed (TrueNode) predicates exactly match between primaryRegion and secondRegion,
	 *	updating secondaryNode2primaryNode accordingly.
	 */
	protected boolean correlateComputedPredicates() {
		Iterable<@NonNull Node> primaryTrueNodes = primaryRegion.getTrueNodes();
		Iterable<@NonNull Node> secondaryTrueNodes = secondaryRegion.getTrueNodes();
		int primaryTrueSize = Iterables.size(primaryTrueNodes);
		if (primaryTrueSize != Iterables.size(secondaryTrueNodes)) {
			return false;
		}
		if (primaryTrueSize == 0) {
			return true;
		}
		Map<@NonNull Node, @NonNull Node> primary2secondary = new HashMap<>();
		if (primaryTrueSize == 1) {
			Node primaryTrueNode = primaryTrueNodes.iterator().next();
			Node secondaryTrueNode = secondaryTrueNodes.iterator().next();
			if (!correlateComputation(primaryTrueNode, secondaryTrueNode, primary2secondary)) {
				return false;
			}
		}
		else {
			Set<@NonNull Node> residualSecondaryTrueNodes = Sets.newHashSet(secondaryTrueNodes);
			for (@NonNull Node primaryTrueNode : primaryTrueNodes) {
				boolean gotIt = false;
				for (@NonNull Node secondaryTrueNode : residualSecondaryTrueNodes) {
					Map<@NonNull Node, @NonNull Node> primary2secondary2 = new HashMap<>();
					if (correlateComputation(primaryTrueNode, secondaryTrueNode, primary2secondary2)) {	// FIXME use hashes
						gotIt = true;
						primary2secondary.putAll(primary2secondary2);
						residualSecondaryTrueNodes.remove(secondaryTrueNode);
						break;
					}
				}
				if (!gotIt) {
					return false;
				}
			}
		}
		for (@NonNull Node primaryNode : primary2secondary.keySet()) {
			Node equivalentNode = primary2secondary.get(primaryNode);
			assert equivalentNode != null;
			secondaryNode2primaryNode.put(equivalentNode, primaryNode);
		}
		return true;
	}

	protected boolean correlateHeadNodes() {
		List<Node> secondaryHeadNodes = secondaryRegion.getHeadNodes();
		if (secondaryHeadNodes.size() != 1) {			// FIXME Surely consistent multiple heads are ok?
			if (debugFailures) {
				AbstractMerger.FAILURE.println("More than 1 secondary head nodes: " + secondaryHeadNodes.size());
			}
			return false;
		}
		Node secondaryHeadNode = secondaryHeadNodes.get(0);
		CompleteClass completeClass = secondaryHeadNode.getCompleteClass();
		List<@NonNull Node> primaryNodes = completeClass2primaryNodes.get(completeClass);
		if ((primaryNodes == null) || (primaryNodes.size() == 0)) {
			if (debugFailures) {
				AbstractMerger.FAILURE.println("No primary nodes of type: " + completeClass);
			}
			return false;
		}
		Node primaryHeadNode = secondaryNode2primaryNode.get(secondaryHeadNode);
		if (primaryHeadNode == null) {
			primaryHeadNode = selectMergedHeadNode(secondaryHeadNode, primaryNodes);
			if (primaryHeadNode == null) {
				primaryHeadNode = selectMergedHeadNode(secondaryHeadNode, primaryNodes);		// FIXME debugging
				if (debugFailures) {
					AbstractMerger.FAILURE.println("No primary head node to match: " + secondaryHeadNode);
				}
				return false;
			}
			secondaryNode2primaryNode.put(secondaryHeadNode, primaryHeadNode);
		}
		if (primaryNodes.size() > 1) {
			for (@NonNull Node primaryNode : primaryNodes) {
				if ((primaryNode != primaryHeadNode) && !primaryNode.isLoaded()) {
					if (debugFailures) {		// FIXME multiple matching not-speculated might be ok
						AbstractMerger.FAILURE.println("Multiple primary nodes of type: " + completeClass);
					}
					return false;
				}
			}
		}
		return true;
	}

	protected boolean correlateNavigablePredicates() {
		//
		//	Loop over a growing worklist of secondary nodes.
		//
		Set<@NonNull Node> secondaryNodes = new HashSet<>(secondaryNode2primaryNode.keySet());
		List<@NonNull Node> secondaryNodesWorkList = new ArrayList<>(secondaryNodes);
		for (int i = 0; i < secondaryNodesWorkList.size(); i++) {
			@NonNull Node secondarySourceNode = secondaryNodesWorkList.get(i);
			@Nullable Node primarySourceNode = secondaryNode2primaryNode.get(secondarySourceNode);
			if (!strategy.navigableNodesMatch(secondarySourceNode, primarySourceNode)) {
				return false;
			}
			for (@NonNull NavigableEdge uncastSecondaryEdge : secondarySourceNode.getNavigationEdges()) {
				Node uncastSecondaryTargetNode = uncastSecondaryEdge.getEdgeTarget();
				Iterable<@NonNull Node> secondaryTargetNodes = RegionUtil.getCastTargets(uncastSecondaryTargetNode, true);
				if (primarySourceNode != null) {
					NavigableEdge uncastPrimaryEdge = primarySourceNode.getNavigationEdge(RegionUtil.getProperty(uncastSecondaryEdge));	// Skip isSecondary properties
					if (!strategy.navigableEdgesMatch(uncastSecondaryEdge, uncastPrimaryEdge)) {
						return false;
					}
					if (uncastPrimaryEdge != null) {
						Node uncastPrimaryTargetNode = uncastPrimaryEdge.getEdgeTarget();
						if (uncastSecondaryTargetNode.isExplicitNull() != uncastPrimaryTargetNode.isExplicitNull()) {
							if (debugFailures) {
								AbstractMerger.FAILURE.println("Inconsistent ExplicitNull: " + uncastSecondaryTargetNode);
							}
							return false;
						}
						Map<@NonNull CompleteClass, @NonNull Node> completeClass2primaryTargetNodes = new HashMap<>();
						for (@NonNull Node primaryTargetNode : RegionUtil.getCastTargets(uncastPrimaryTargetNode, true)) {
							CompleteClass targetCompleteClass = primaryTargetNode.getCompleteClass();
							Node oldNode = completeClass2primaryTargetNodes.put(targetCompleteClass, primaryTargetNode);
							if (oldNode != null) {
								if (debugFailures) {
									AbstractMerger.FAILURE.println("Inconsistent paths to: " + targetCompleteClass);
								}
								return false;		// FIXME should have an earlier cast rationalizer
							}
						}
						for (@NonNull Node secondaryTargetNode : secondaryTargetNodes) {
							CompleteClass targetCompleteClass = secondaryTargetNode.getCompleteClass();
							Node primaryTargetNode = completeClass2primaryTargetNodes.remove(targetCompleteClass);
							if (primaryTargetNode == null) {
								if (debugFailures) {
									AbstractMerger.FAILURE.println("Inconsistent types at: " + primaryTargetNode + ", " + secondaryTargetNode);
								}
								return false;		// FIXME Inconsistent navigation is too complex
							}
							else {
								Node primaryTargetNode2 = secondaryNode2primaryNode.get(secondaryTargetNode);
								if (primaryTargetNode2 == null) {
									secondaryNode2primaryNode.put(secondaryTargetNode, primaryTargetNode);
								}
								else if (primaryTargetNode != primaryTargetNode2) {
									if (debugFailures) {
										AbstractMerger.FAILURE.println("Inconsistent paths to: " + primaryTargetNode + ", " + primaryTargetNode2);
									}
									return false;		// FIXME Inconsistent navigation is too complex
								}
							}
						}
					}
				}
				for (@NonNull Node secondaryTargetNode : secondaryTargetNodes) {
					if (secondaryNodes.add(secondaryTargetNode)) {
						secondaryNodesWorkList.add(secondaryTargetNode);
					}
				}
			}
		}
		return true;
	}

	protected void correlateResidualComputations(@NonNull Iterable<@NonNull Node> secondaryNodes) {
		for (@NonNull Node secondaryNode : secondaryNodes) {
			Node primaryNode = secondaryNode2primaryNode.get(secondaryNode);
			assert primaryNode != null;
			Map<@NonNull Node, @NonNull Node> secondary2primary2 = new HashMap<>();
			if (correlateComputation(secondaryNode, primaryNode, secondary2primary2)) {	// FIXME use hashes
				secondaryNode2primaryNode.putAll(secondary2primary2);
			}
		}
	}

	public @NonNull Map<@NonNull Node, @NonNull Node> getNode2Node() {
		return secondaryNode2primaryNode;
	}

	/**
	 * Chose the headNode from a group of peer nodes that has the most non-implicit properties targeting its peers.
	 *
	protected @NonNull Node selectBestHeadNode(@NonNull List<@NonNull Node> headNodes) {
		int size = headNodes.size();
		assert size >= 1;
		if (size == 1) {
			return headNodes.get(0);
		}
		Node bestHeadNode = null;
		int bestNonImplicits = -1;
		List<@NonNull Node> sortedHeadNodes = new ArrayList<>(headNodes);
		Collections.sort(sortedHeadNodes, NameUtil.NAMEABLE_COMPARATOR);		// Stabilize order
		for (@NonNull Node thisHeadNode : sortedHeadNodes) {
			int nonImplicits = 0;
			for (@NonNull Node thatHeadNode : sortedHeadNodes) {
				for (@NonNull NavigableEdge edge : thisHeadNode.getNavigationEdges()) {
					if (edge.getTarget() == thatHeadNode) {
						Property property = edge.getProperty();
						if (!property.isIsImplicit()) {
							nonImplicits++;
							break;
						}
					}
				}
			}
			if (nonImplicits > bestNonImplicits) {
				bestHeadNode = thisHeadNode;
				bestNonImplicits = nonImplicits;
			}
		}
		assert bestHeadNode != null;
		return bestHeadNode;
	} */

	protected @Nullable Node selectMergedHeadNode(@NonNull Node headNode, @NonNull List<@NonNull Node> mergedNodes) {
		if (mergedNodes.size() == 1) {
			Node mergedNode = mergedNodes.get(0);//selectBestHeadNode(mergedNodes);
			//			if (mergedNode.isIterator()) {
			//				return null;
			//			}
			return mergedNode;
		}
		if (mergedNodes.size() == 0) {
			return null;
		}
		Iterable<NavigableEdge> predicateEdges = headNode.getPredicateEdges();
		for (@NonNull Node mergedNode : mergedNodes) {
			boolean ok = !mergedNode.isIterator();
			if (ok) {
				for (@NonNull NavigableEdge predicateEdge : predicateEdges) {
					Property property = RegionUtil.getProperty(predicateEdge);
					Node navigation = mergedNode.getNavigationTarget(property);
					if (navigation == null) {
						ok = false;
						break;
					}
				}
			}
			if (ok) {						// FIXME stronger checking
				return mergedNode;
			}
		}
		return null;
	}
}