[507096] Rewrite EarlyMerger using Edge/Node/RegionMergerasanchez/thesis

10 files changed, 813 insertions, 441 deletions

diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractMappingRegion.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractMappingRegion.java
index 8438bb6c9..eda7efca3 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractMappingRegion.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractMappingRegion.java
@@ -256,7 +256,7 @@ public abstract class AbstractMappingRegion extends AbstractRegion implements Ma
 	protected @NonNull List<@NonNull Node> computeHeadNodes() {
 		//
 		//	A head node is reachable from very few nodes, typically just itself, occasionally from a small group of mutually bidirectional nodes,
-		//	so we search for the least reachable nodes taking care to avoid hazrads from the source-to-target / target-source asymmetry.
+		//	so we search for the least reachable nodes taking care to avoid hazards from the source-to-target / target-source asymmetry.
 		//
 		List<@NonNull Node> navigableNodes = new ArrayList<>();
 		for (@NonNull Node node : getNodes()) {
@@ -290,8 +290,9 @@ public abstract class AbstractMappingRegion extends AbstractRegion implements Ma
 					Node targetNode = navigationEdge.getTarget();
 					if (targetNode.isMatched() && targetNode.isClass() && !targetNode.isExplicitNull()) {
 						Set<@NonNull Node> sourceClosure = targetFromSourceClosure.get(targetNode);
-						assert sourceClosure != null;
-						sourceClosure.add(sourceNode);
+						if (sourceClosure != null) {
+							sourceClosure.add(sourceNode);
+						}
 					}
 				}
 			}
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/MicroMappingRegion.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/MicroMappingRegion.java
index e9a3ba3ee..c951526f6 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/MicroMappingRegion.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/MicroMappingRegion.java
@@ -25,6 +25,7 @@ public class MicroMappingRegion extends AbstractMappingRegion
 
 	public MicroMappingRegion(@NonNull MappingRegion mappingRegion, @NonNull String prefix, @NonNull String suffix) {
 		super(mappingRegion.getMultiRegion());
+		assert !(mappingRegion instanceof MicroMappingRegion);
 		this.mappingRegion = mappingRegion;
 		this.prefix = prefix;
 		this.suffix = suffix;
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/QVTp2QVTs.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/QVTp2QVTs.java
index f9757089d..eb3fc08ff 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/QVTp2QVTs.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/QVTp2QVTs.java
@@ -141,14 +141,14 @@ public class QVTp2QVTs extends SchedulerConstants
 				mappingRegion.writeDebugGraphs(null);
 			}
 		}
-		List<@NonNull BasicMappingRegion> orderedRegions = new ArrayList<>();
+		List<@NonNull MappingRegion> orderedRegions = new ArrayList<>();
 		for (@NonNull Mapping mapping : orderedMappings) {
 			BasicMappingRegion mappingRegion = mapping2mappingRegion.get(mapping);
 			assert mappingRegion != null;
 			orderedRegions.add(mappingRegion);
 			//			mappingRegion.resolveRecursion();
 		}
-		List<@NonNull Region> activeRegions = new ArrayList<>(EarlyMerger.earlyRegionMerge(orderedRegions));
+		List<@NonNull Region> activeRegions = new ArrayList<>(EarlyMerger.merge(orderedRegions));
 		//		for (@NonNull Region activeRegion : activeRegions) {
 		//			((AbstractRegion)activeRegion).resolveRecursion();
 		//		}
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RegionMerger.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RegionMerger.java
deleted file mode 100644
index 7dbc4f660..000000000
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RegionMerger.java
+++ /dev/null
@@ -1,269 +0,0 @@
-/*******************************************************************************
- * Copyright (c) 2016 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.qvtp2qvts;
-
-import java.util.ArrayList;
-import java.util.Collections;
-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.Property;
-import org.eclipse.ocl.pivot.TypedElement;
-import org.eclipse.ocl.pivot.utilities.ClassUtil;
-import org.eclipse.qvtd.compiler.internal.qvtp2qvts.impl.VariableNodeImpl;
-
-public class RegionMerger extends AbstractVisitor<@Nullable Visitable>
-{
-	public static @NonNull MappingRegion createMergedRegion(@NonNull MappingRegion primaryRegion, @NonNull MappingRegion secondaryRegion, @NonNull Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode) {
-		RegionMerger regionMerger = new RegionMerger(primaryRegion, secondaryRegion, secondaryNode2primaryNode);
-		Visitable mergedRegion = secondaryRegion.accept(regionMerger);
-		assert mergedRegion != null;
-		return (MappingRegion) mergedRegion;
-	}
-
-	protected final @NonNull MappingRegion primaryRegion;
-	protected final @NonNull MappingRegion secondaryRegion;
-	protected final @NonNull Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode;
-	protected final @NonNull MappingRegion mergedRegion;
-	protected final @NonNull Map<@NonNull Node, @NonNull Node> oldNode2mergedNode = new HashMap<>();
-	protected final @NonNull Map<@NonNull Edge, @NonNull List<@NonNull Edge>> oldEdge2oldEdges = new HashMap<>();
-	private final @NonNull Map<@NonNull Edge, @NonNull Edge> debugOldEdge2mergedEdge = new HashMap<>();
-
-	protected RegionMerger(@NonNull MappingRegion primaryRegion, @NonNull MappingRegion secondaryRegion, @NonNull Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode) {
-		this.primaryRegion = primaryRegion;
-		this.secondaryRegion = secondaryRegion;
-		this.secondaryNode2primaryNode = secondaryNode2primaryNode;
-		List<@NonNull String> names = new ArrayList<>();
-		names.add(ClassUtil.nonNullState(primaryRegion.getName()));
-		names.add(ClassUtil.nonNullState(secondaryRegion.getName()));
-		Collections.sort(names);
-		StringBuilder s = new StringBuilder();
-		//		s.append(getClass().getSimpleName());
-		for (String name : names) {
-			if (s.length() > 0) {
-				s.append("\\n");
-			}
-			s.append(name);
-		}
-		this.mergedRegion = new NamedMappingRegion(primaryRegion.getMultiRegion(), s.toString());
-	}
-
-	protected void accumulateEdge(@NonNull Map<@NonNull Node, @NonNull Map<@NonNull Node, @NonNull List<@NonNull List<@NonNull Edge>>>> mergedSourceNode2mergedTargetNode2listOfOldEdges, @NonNull Edge oldEdge) {
-		//		List<@NonNull Edge> oldOldEdges2 = oldEdge2oldEdges.get(oldEdge);
-		//		assert oldOldEdges2 == null;
-		Node mergedSourceNode = oldNode2mergedNode.get(oldEdge.getSource());
-		Node mergedTargetNode = oldNode2mergedNode.get(oldEdge.getTarget());
-		assert (mergedSourceNode != null) && (mergedTargetNode != null);
-		Map<@NonNull Node, @NonNull List<@NonNull List<@NonNull Edge>>> mergedTargetNode2listOfOldEdges = mergedSourceNode2mergedTargetNode2listOfOldEdges.get(mergedSourceNode);
-		if (mergedTargetNode2listOfOldEdges == null) {
-			mergedTargetNode2listOfOldEdges = new HashMap<>();
-			mergedSourceNode2mergedTargetNode2listOfOldEdges.put(mergedSourceNode, mergedTargetNode2listOfOldEdges);
-		}
-		List<@NonNull List<@NonNull Edge>> listOfOldEdges = mergedTargetNode2listOfOldEdges.get(mergedTargetNode);
-		if (listOfOldEdges == null) {
-			listOfOldEdges = new ArrayList<>();
-			mergedTargetNode2listOfOldEdges.put(mergedTargetNode, listOfOldEdges);
-		}
-		List<@NonNull Edge> matchingOldEdges = null;
-		for (@NonNull List<@NonNull Edge> oldEdges : listOfOldEdges) {
-			if (sameEdge(oldEdge, oldEdges)) {
-				matchingOldEdges = oldEdges;
-				break;
-			}
-		}
-		if (matchingOldEdges == null) {
-			matchingOldEdges = new ArrayList<>();
-			listOfOldEdges.add(matchingOldEdges);
-		}
-		matchingOldEdges.add(oldEdge);
-		List<@NonNull Edge> oldOldEdges = oldEdge2oldEdges.put(oldEdge, matchingOldEdges);
-		assert oldOldEdges == null;
-	}
-
-	private void checkEdges(@NonNull Region oldRegion) {
-		for (@NonNull Edge oldEdge : oldRegion.getEdges()) {
-			assert oldEdge.getRegion() == oldRegion;
-			if (!oldEdge.isRecursion() && !oldEdge.isSecondary()) {		// FIXME Remove this irregularity
-				List<@NonNull Edge> oldEdges = oldEdge2oldEdges.get(oldEdge);
-				assert oldEdges != null;
-				assert oldEdges.contains(oldEdge);
-				Edge mergedEdge = debugOldEdge2mergedEdge.get(oldEdge);
-				assert mergedEdge != null;
-				assert mergedEdge.getRegion() == mergedRegion;
-			}
-		}
-	}
-
-	private void checkNodes(@NonNull Region oldRegion) {
-		for (@NonNull Node oldNode : oldRegion.getNodes()) {
-			assert oldNode.getRegion() == oldRegion;
-			Node mergedNode = oldNode2mergedNode.get(oldNode);
-			assert mergedNode != null;
-			assert mergedNode.getRegion() == mergedRegion;
-		}
-	}
-
-	protected void createMergedEdge(@NonNull Iterable<@NonNull Edge> oldEdges) {
-		Edge mergedEdge = null;
-		for (@NonNull Edge oldEdge : oldEdges) {
-			mergedEdge = (Edge)oldEdge.accept(this);
-			break;
-		}
-		if (mergedEdge != null) {
-			for (@NonNull Edge oldEdge : oldEdges) {
-				debugOldEdge2mergedEdge.put(oldEdge, mergedEdge);
-			}
-		}
-	}
-
-	private boolean sameEdge(@NonNull Edge newEdge, @NonNull Iterable<@NonNull Edge> oldEdges) {
-		if (newEdge instanceof NavigableEdge) {
-			Property newProperty = ((NavigableEdge)newEdge).getProperty();
-			for (@NonNull Edge oldEdge : oldEdges) {
-				if (oldEdge instanceof NavigableEdge) {
-					Property oldProperty = ((NavigableEdge)oldEdge).getProperty();
-					if (oldProperty == newProperty) {
-						return true;
-					}
-				}
-			}
-		}
-		else {
-			Class<? extends @NonNull Edge> newClass = newEdge.getClass();
-			for (@NonNull Edge oldEdge : oldEdges) {
-				Class<? extends @NonNull Edge> oldClass = oldEdge.getClass();
-				if (oldClass == newClass) {
-					return true;
-				}
-			}
-		}
-		return false;
-	}
-
-	@Override
-	public @NonNull Visitable visitEdge(@NonNull Edge edge) {
-		Node mergedSourceNode = oldNode2mergedNode.get(edge.getSource());
-		Node mergedTargetNode = oldNode2mergedNode.get(edge.getTarget());
-		assert (mergedSourceNode != null) && (mergedTargetNode != null);
-		EdgeRole edgeRole = null;
-		List<@NonNull Edge> oldEdges = oldEdge2oldEdges.get(edge);
-		assert oldEdges != null;
-		for (@NonNull Edge oldEdge : oldEdges) {
-			EdgeRole edgeRole2 = oldEdge.getEdgeRole();
-			edgeRole = edgeRole != null ? RegionUtil.mergeToMoreKnownPhase(edgeRole, edgeRole2) : edgeRole2;
-		}
-		assert edgeRole != null;
-		return edge.createEdge(edgeRole, mergedSourceNode, mergedTargetNode);
-	}
-
-	@Override
-	public @NonNull MappingRegion visitMappingRegion(@NonNull MappingRegion mappingRegion) {
-		Set<@NonNull Node> toBeMergedNodes = new HashSet<>(primaryRegion.getNodes());
-		toBeMergedNodes.removeAll(secondaryNode2primaryNode.values());
-		toBeMergedNodes.addAll(secondaryRegion.getNodes());
-		for (@NonNull Node toBeMergedNode : toBeMergedNodes) {
-			toBeMergedNode.accept(this);
-		}
-		//
-		//
-		//
-		Map<@NonNull Node, @NonNull Map<@NonNull Node, @NonNull List<@NonNull List<@NonNull Edge>>>> mergedSourceNode2mergedTargetNode2listOfOldEdges = new HashMap<>();
-		for (@NonNull Edge oldEdge : primaryRegion.getEdges()) {
-			if (!oldEdge.isRecursion()) {		// FIXME Remove this irregularity
-				accumulateEdge(mergedSourceNode2mergedTargetNode2listOfOldEdges, oldEdge);
-			}
-		}
-		for (@NonNull Edge oldEdge : secondaryRegion.getEdges()) {
-			if (!oldEdge.isRecursion()) {		// FIXME Remove this irregularity
-				accumulateEdge(mergedSourceNode2mergedTargetNode2listOfOldEdges, oldEdge);
-			}
-		}
-		for (@NonNull Map<@NonNull Node, @NonNull List<@NonNull List<@NonNull Edge>>> mergedTargetNode2listOfOldEdges : mergedSourceNode2mergedTargetNode2listOfOldEdges.values()) {
-			for (@NonNull List<@NonNull List<@NonNull Edge>> listOfOldEdges : mergedTargetNode2listOfOldEdges.values()) {
-				assert listOfOldEdges != null;
-				for (@NonNull List<@NonNull Edge> oldEdges : listOfOldEdges) {
-					createMergedEdge(oldEdges);
-				}
-			}
-		}
-		checkNodes(primaryRegion);
-		checkNodes(secondaryRegion);
-		checkEdges(primaryRegion);
-		checkEdges(secondaryRegion);
-		return mergedRegion;
-	}
-
-	@Override
-	public @Nullable Visitable visitNavigableEdge(@NonNull NavigableEdge navigationEdge) {
-		if (navigationEdge.isSecondary()) {
-			return null;
-		}
-		Node mergedSourceNode = oldNode2mergedNode.get(navigationEdge.getSource());
-		Node mergedTargetNode = oldNode2mergedNode.get(navigationEdge.getTarget());
-		assert (mergedSourceNode != null) && (mergedTargetNode != null);
-		EdgeRole edgeRole = null;
-		List<@NonNull Edge> oldEdges = oldEdge2oldEdges.get(navigationEdge);
-		assert oldEdges != null;
-		for (@NonNull Edge oldEdge : oldEdges) {
-			EdgeRole edgeRole2 = oldEdge.getEdgeRole();
-			edgeRole = edgeRole != null ? RegionUtil.mergeToMoreKnownPhase(edgeRole, edgeRole2) : edgeRole2;
-		}
-		assert edgeRole != null;
-		return navigationEdge.createEdge(edgeRole, mergedSourceNode, mergedTargetNode);
-	}
-
-	@Override
-	public @NonNull Node visitNode(@NonNull Node node) {
-		NodeRole nodeRole = node.getNodeRole();
-		Node primaryNode = secondaryNode2primaryNode.get(node);
-		if (primaryNode != null) {
-			nodeRole = nodeRole.merge(primaryNode.getNodeRole());
-		}
-		Node mergedNode = node.createNode(nodeRole, mergedRegion);
-		oldNode2mergedNode.put(node, mergedNode);
-		for (@NonNull TypedElement typedElement : node.getTypedElements()) {
-			mergedNode.addTypedElement(typedElement);
-		}
-		if (primaryNode != null) {
-			oldNode2mergedNode.put(primaryNode, mergedNode);
-			for (@NonNull TypedElement typedElement : primaryNode.getTypedElements()) {
-				mergedNode.addTypedElement(typedElement);
-			}
-		}
-		return mergedNode;
-	}
-
-	@Override
-	public @NonNull Node visitVariableNode(@NonNull VariableNodeImpl variableNode) {
-		NodeRole nodeRole = variableNode.getNodeRole();
-		Node primaryNode = secondaryNode2primaryNode.get(variableNode);
-		if (primaryNode != null) {
-			nodeRole = nodeRole.merge(primaryNode.getNodeRole());
-		}
-		Node mergedNode = variableNode.createNode(nodeRole, mergedRegion);
-		oldNode2mergedNode.put(variableNode, mergedNode);
-		for (@NonNull TypedElement typedElement : variableNode.getTypedElements()) {
-			mergedNode.addTypedElement(typedElement);
-		}
-		if (primaryNode != null) {
-			oldNode2mergedNode.put(primaryNode, mergedNode);
-			for (@NonNull TypedElement typedElement : primaryNode.getTypedElements()) {
-				mergedNode.addTypedElement(typedElement);
-			}
-		}
-		return mergedNode;
-	}
-}
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RegionUtil.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RegionUtil.java
index 06a157673..898d5171e 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RegionUtil.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RegionUtil.java
@@ -365,19 +365,19 @@ public class RegionUtil
 	}
 
 	public static @NonNull Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> getCompleteClass2Nodes(@NonNull Region region) {
-		Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2node = new HashMap<>();
+		Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2nodes = new HashMap<>();
 		for (@NonNull Node node : region.getNodes()) {
 			CompleteClass completeClass = node.getCompleteClass();
-			List<@NonNull Node> mergedNodes = completeClass2node.get(completeClass);
+			List<@NonNull Node> mergedNodes = completeClass2nodes.get(completeClass);
 			if (mergedNodes == null) {
 				mergedNodes = new ArrayList<>();
-				completeClass2node.put(completeClass, mergedNodes);
+				completeClass2nodes.put(completeClass, mergedNodes);
 			}
 			if (!mergedNodes.contains(node)) {
 				mergedNodes.add(node);
 			}
 		}
-		return completeClass2node;
+		return completeClass2nodes;
 	}
 
 	public static Role.@NonNull Phase getOperationNodePhase(@NonNull Region region, @NonNull TypedElement typedElement, @NonNull Node... argNodes) {
@@ -576,4 +576,22 @@ public class RegionUtil
 		}
 		throw new UnsupportedOperationException();
 	}
+
+	public static Node.@NonNull Utility mergeToStrongerUtility(Node.@NonNull Utility nodeUtility1, Node.@NonNull Utility nodeUtility2) {
+		if ((nodeUtility1 == Node.Utility.STRONGLY_MATCHED) || (nodeUtility2 == Node.Utility.STRONGLY_MATCHED)) {
+			return Node.Utility.STRONGLY_MATCHED;
+		}
+		else if ((nodeUtility1 == Node.Utility.WEAKLY_MATCHED) || (nodeUtility2 == Node.Utility.WEAKLY_MATCHED)) {
+			return Node.Utility.WEAKLY_MATCHED;
+		}
+		else if ((nodeUtility1 == Node.Utility.CONDITIONAL) || (nodeUtility2 == Node.Utility.CONDITIONAL)) {
+			return Node.Utility.CONDITIONAL;
+		}
+		else if ((nodeUtility1 == Node.Utility.DEPENDENCY) || (nodeUtility2 == Node.Utility.DEPENDENCY)) {
+			return Node.Utility.DEPENDENCY;
+		}
+		else {
+			return Node.Utility.DEAD;
+		}
+	}
 }
\ No newline at end of file
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EarlyMerger.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EarlyMerger.java
index e7154fa2d..67486f568 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EarlyMerger.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EarlyMerger.java
@@ -21,28 +21,53 @@ import java.util.Set;
 
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.ocl.pivot.CollectionType;
 import org.eclipse.ocl.pivot.CompleteClass;
 import org.eclipse.ocl.pivot.Property;
+import org.eclipse.ocl.pivot.Type;
+import org.eclipse.ocl.pivot.TypedElement;
 import org.eclipse.ocl.pivot.utilities.ClassUtil;
 import org.eclipse.ocl.pivot.utilities.NameUtil;
-import org.eclipse.qvtd.compiler.internal.qvtp2qvts.BasicMappingRegion;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Edge;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MappingRegion;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.NavigableEdge;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Node;
-import org.eclipse.qvtd.compiler.internal.qvtp2qvts.NodeRole;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.QVTp2QVTs;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Region;
-import org.eclipse.qvtd.compiler.internal.qvtp2qvts.RegionMerger;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.RegionUtil;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.analysis.ClassDatumAnalysis;
 import org.eclipse.qvtd.compiler.internal.qvts2qvts.Region2Depth;
 
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
 
+/**
+ * EarlyMerger replaces one list of MappingRegions by another in which each set of regions that can be merged
+ * without knowledge of the schedule is replaced by an equivalent merged region.
+ */
 public class EarlyMerger
 {
-	public static @Nullable Map<@NonNull Node, @NonNull Node> canMerge(@NonNull Region primaryRegion, @NonNull Region secondaryRegion, @NonNull Region2Depth region2depths, boolean isLateMerge) {
+	/**
+	 * Replace those inputRegions that may be merged by merged regions.
+	 *
+	 * inputRegions should be naturally ordered to ensure that non-recursive dependencies are inherently satisfied.
+	 *
+	 * Returns the inputRegions after replacement of merges.
+	 */
+	public static @NonNull List<@NonNull MappingRegion> merge(@NonNull Iterable<@NonNull MappingRegion> inputRegions) {
+		EarlyMerger earlyMerger = new EarlyMerger(inputRegions);
+		return earlyMerger.merge();
+	}
+
+	protected final @NonNull LinkedHashSet<@NonNull MappingRegion> residualInputRegions;
+	protected final @NonNull List<@NonNull MappingRegion> outputRegions = new ArrayList<>();
+	protected final @NonNull Region2Depth region2depths = new Region2Depth();
+
+	protected EarlyMerger(@NonNull Iterable<@NonNull MappingRegion> inputRegions) {
+		this.residualInputRegions = Sets.newLinkedHashSet(inputRegions);
+	}
+
+	protected @Nullable Map<@NonNull Node, @NonNull Node> canMerge(@NonNull Region primaryRegion, @NonNull Region secondaryRegion, @NonNull Region2Depth region2depths, boolean isLateMerge) {
 		Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = null;
 		Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2nodes = RegionUtil.getCompleteClass2Nodes(primaryRegion);
 		//
@@ -61,9 +86,6 @@ public class EarlyMerger
 				return null;
 			}
 			secondaryNode2primaryNode = new HashMap<>();
-			if ("if".equals(secondaryHeadNode.getName())) {
-				secondaryHeadNode.getName();
-			}
 			secondaryNode2primaryNode.put(secondaryHeadNode, primaryHeadNode);
 		}
 		if (secondaryNode2primaryNode == null) {
@@ -94,9 +116,6 @@ public class EarlyMerger
 					for (@NonNull Node primaryNode : primary2secondary.keySet()) {
 						Node equivalentNode = primary2secondary.get(primaryNode);
 						assert equivalentNode != null;
-						if ("if".equals(equivalentNode.getName())) {
-							equivalentNode.getName();
-						}
 						secondaryNode2primaryNode.put(equivalentNode, primaryNode);
 					}
 					break;
@@ -108,7 +127,7 @@ public class EarlyMerger
 		}
 		return secondaryNode2primaryNode;
 	}
-	private static boolean canMergeInternal(@NonNull Region secondaryRegion, @NonNull Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode, @NonNull Region2Depth region2depths, boolean isLateMerge) {
+	protected boolean canMergeInternal(@NonNull Region secondaryRegion, @NonNull Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode, @NonNull Region2Depth region2depths, boolean isLateMerge) {
 		Set<@NonNull Node> secondaryNodes = new HashSet<>(secondaryNode2primaryNode.keySet());
 		List<@NonNull Node> secondaryNodesList = new ArrayList<>(secondaryNodes);
 		for (int i = 0; i < secondaryNodesList.size(); i++) {
@@ -120,12 +139,12 @@ public class EarlyMerger
 				}
 			}
 			for (@NonNull NavigableEdge secondaryEdge : secondarySourceNode.getNavigationEdges()) {
-				Node secondaryTargetNode = secondaryEdge.getTarget();
+				Node secondaryTargetNode = RegionUtil.getCastTarget(secondaryEdge.getTarget());
 				Node primaryTargetNode = null;
 				if (primarySourceNode != null) {
 					Edge primaryEdge = primarySourceNode.getNavigationEdge(secondaryEdge.getProperty());
 					if (primaryEdge != null) {
-						primaryTargetNode = primaryEdge.getTarget();
+						primaryTargetNode = RegionUtil.getCastTarget(primaryEdge.getTarget());
 						//						primaryTargetNode = primaryTargetNode.getCastEquivalentNode();
 						//						secondaryTargetNode = secondaryTargetNode.getCastEquivalentNode();
 						if (primaryTargetNode.getCompleteClass() != secondaryTargetNode.getCompleteClass()) {		// FIXME conforms
@@ -149,9 +168,6 @@ public class EarlyMerger
 				if (primaryTargetNode != null) {
 					Node primaryTargetNode2 = secondaryNode2primaryNode.get(secondaryTargetNode);
 					if (primaryTargetNode2 == null) {
-						if ("if".equals(secondaryTargetNode.getName())) {
-							secondaryTargetNode.getName();
-						}
 						secondaryNode2primaryNode.put(secondaryTargetNode, primaryTargetNode);
 					}
 				}
@@ -224,130 +240,64 @@ public class EarlyMerger
 	}
 
 	/**
-	 * Replace those orderedRegions that may be aggregated as part of a GuardedRegion decision tree by GuardedRegions.
-	 * orderedRegions should be naturally ordered to ensure that non-recursive dependencies are inherently satisfied.
-	 *
-	 * Returns the orderedRegions plus the new aggregates less those aggregated.
-	 */
-	public static @NonNull List<@NonNull MappingRegion> earlyRegionMerge(@NonNull List<@NonNull BasicMappingRegion> orderedRegions) {
-		Region2Depth region2depths = new Region2Depth();
-		List<@NonNull MappingRegion> outputRegions = new ArrayList<>();
-		LinkedHashSet<@NonNull MappingRegion> residualInputRegions = new LinkedHashSet<>(orderedRegions);	// order preserving fast random removal
-		while (!residualInputRegions.isEmpty()) {
-			@NonNull MappingRegion candidateRegion = residualInputRegions.iterator().next();
-			boolean isMerged = false;
-			if (isEarlyMergePrimaryCandidate(candidateRegion)) {
-				List<@NonNull MappingRegion> secondaryRegions = selectSecondaryRegions(candidateRegion);
-				if (secondaryRegions != null) {
-					MappingRegion mergedRegion = candidateRegion;
-					for (@NonNull MappingRegion secondaryRegion : secondaryRegions) {
-						assert secondaryRegion != null;
-						if (residualInputRegions.contains(secondaryRegion)) {
-							Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = EarlyMerger.canMerge(mergedRegion, secondaryRegion, region2depths, false);
-							if (secondaryNode2primaryNode != null) {
-								boolean isSharedHead = isSharedHead(mergedRegion, secondaryRegion);
-								if (!isSharedHead || (EarlyMerger.canMerge(secondaryRegion, mergedRegion, region2depths, false) != null)) {
-									residualInputRegions.remove(mergedRegion);
-									residualInputRegions.remove(secondaryRegion);
-									mergedRegion = RegionMerger.createMergedRegion(mergedRegion, secondaryRegion, secondaryNode2primaryNode);
-									region2depths.addRegion(mergedRegion);
-								}
-							}
-						}
-					}
-					if (mergedRegion != candidateRegion) {
-						//						mergedRegion.resolveRecursion();
-						if (QVTp2QVTs.DEBUG_GRAPHS.isActive()) {
-							mergedRegion.writeDebugGraphs("2-merged");
-						}
-						//						GuardedRegion guardedRegion = createGuardedRegion(mergedRegion, mergeableRegions);
-						//						outputRegions.add(guardedRegion);
-						outputRegions.add(mergedRegion);
-						isMerged = true;
-					}
-				}
-			}
-			if (!isMerged) {
-				outputRegions.add(candidateRegion);
-			}
-			residualInputRegions.remove(candidateRegion);
-		}
-		return outputRegions;
-	}
-
-	/**
-	 * Return the nodes with region at which a suitably matching head of another region might be merged.
+	 * Return the nodes within region at which a suitably matching head of another region might be merged.
 	 * The nodes must be bi-directionally one to one to respect 1:N trace node relationships.
 	 */
-	protected static @NonNull Iterable<@NonNull Node> getMergeableNodes(@NonNull MappingRegion region) {
-		Set<@NonNull Node> mergeableNodes = new HashSet<>();
+	protected @NonNull Iterable<@NonNull Node> getHostNodes(@NonNull MappingRegion region) {
+		Set<@NonNull Node> hostNodes = new HashSet<>();
 		for (@NonNull Node node : region.getHeadNodes()) {
-			getMergeableNodes(mergeableNodes, node);
-		}
-		return mergeableNodes;
-	}
-	private static void getMergeableNodes(@NonNull Set<@NonNull Node> mergeableNodes, @NonNull Node node) {
-		if (isMergeable(node) && mergeableNodes.add(node)) {
-			for (@NonNull NavigableEdge edge : node.getNavigationEdges()) {
-				if (edge.getOppositeEdge() != null) {
-					getMergeableNodes(mergeableNodes, edge.getTarget());
-				}
-			}
+			getHostNodesAccumulator(hostNodes, node);
 		}
+		return hostNodes;
 	}
-	private static boolean isMergeable(@NonNull Node node) {	// FIXME this is legacy creep
-		NodeRole nodeRole = node.getNodeRole();
-		if (nodeRole.isRealized() || nodeRole.isSpeculation()) {
-			return false;
-		}
-		if (!node.isClass()) {
-			return false;
+
+	protected void getHostNodesAccumulator(@NonNull Set<@NonNull Node> hostNodes, @NonNull Node node) {
+		//		if (node.isNew()) {
+		//			return;
+		//		}
+		if (!node.isClass()) {		// Simplify - this obviates many of the below
+			return;
 		}
 		if (node.isExplicitNull()) {
-			return true;
+			return;
 		}
 		if (node.isOperation()) {
-			return true;
+			return;
+		}
+		if (!node.isRequired()) {
+			return;
 		}
 		if (node.isTrue()) {
-			return true;
+			return;
 		}
-		if (node.isPattern()) {
-			return true;
+		if (!node.isPattern()) {
+			return;
 		}
-		return false;
-	}
-
-	/**
-	 * The primary region in a GuardedRegion must be single-headed. It may be multiply-produced, e.g. recursed.
-	 */
-	private static boolean isEarlyMergePrimaryCandidate(@NonNull Region mappingRegion) {
-		List<@NonNull Node> headNodes = mappingRegion.getHeadNodes();
-		return headNodes.size() == 1;
-	}
-
-	/**
-	 * The secondary region in a GuardedRegion must be single-headed and at least one its head nodes must be a class in use within
-	 * the primary region. It may be multiply-produced, e.g. recursed.
-	 */
-	private static boolean isEarlyMergeSecondaryCandidate(@NonNull Region primaryRegion,
-			@NonNull Region secondaryRegion, @NonNull Set<ClassDatumAnalysis> toOneReachableClasses) {
-		List<@NonNull Node> secondaryHeadNodes = secondaryRegion.getHeadNodes();
-		if (secondaryHeadNodes.size() == 1) {
-			Node classNode = secondaryHeadNodes.get(0);
-			ClassDatumAnalysis classDatumAnalysis = classNode.getClassDatumAnalysis();
-			if (toOneReachableClasses.contains(classDatumAnalysis)) {
-				return true;
+		if (!hostNodes.add(node)) {
+			return;
+		}
+		for (@NonNull NavigableEdge edge : node.getNavigationEdges()) {
+			if (/*!edge.isSecondary() &&*/ edge.isUnconditional()) {		// ?? why isSecondary ?? why not isLoaded ??
+				Property property = edge.getProperty();
+				if (edge.isNew()) {
+					if (isToZeroOrOne(property) && isToZeroOrOne(property.getOpposite())) {
+						getHostNodesAccumulator(hostNodes, edge.getTarget());
+					}
+				}
+				else {
+					if (isToOne(property) && isToOne(property.getOpposite())) {
+						getHostNodesAccumulator(hostNodes, edge.getTarget());
+					}
+				}
 			}
 		}
-		return false;
 	}
 
 	/**
 	 * Return true if the operation nodes for primaryNode and secondaryNode are equivalent
 	 * assigning equivalences to equivalentNodes.
 	 */
-	private static boolean isEquivalent(@NonNull Node primaryNode, @NonNull Node secondaryNode, @NonNull Map<@NonNull Node, @NonNull Node> primary2secondary) {
+	protected boolean isEquivalent(@NonNull Node primaryNode, @NonNull Node secondaryNode, @NonNull Map<@NonNull Node, @NonNull Node> primary2secondary) {
 		Node node = primary2secondary.get(primaryNode);
 		if (node != null) {
 			return node == secondaryNode;
@@ -380,12 +330,37 @@ public class EarlyMerger
 	}
 
 	/**
+	 * The primary region of a merge must be single-headed. It may be multiply-produced, e.g. recursed.
+	 *
+	 * FIXME Is there any need for this restriction.
+	 */
+	protected boolean isPrimaryCandidate(@NonNull Region mappingRegion) {
+		List<@NonNull Node> headNodes = mappingRegion.getHeadNodes();
+		return headNodes.size() == 1;
+	}
+
+	/**
+	 * The secondary region of a merge must be single-headed and its head node must correspond to
+	 * a non-null unconditional class within the primary region. It may be multiply-produced, e.g. recursed.
+	 */
+	protected boolean isSecondaryCandidate(@NonNull Region primaryRegion,
+			@NonNull Region secondaryRegion, @NonNull Set<@NonNull ClassDatumAnalysis> toOneReachableClasses) {
+		List<@NonNull Node> secondaryHeadNodes = secondaryRegion.getHeadNodes();
+		if (secondaryHeadNodes.size() != 1) {
+			return false;
+		}
+		Node classNode = secondaryHeadNodes.get(0);
+		ClassDatumAnalysis classDatumAnalysis = classNode.getClassDatumAnalysis();
+		return toOneReachableClasses.contains(classDatumAnalysis);
+	}
+
+	/**
 	 * Return true if any primaryRegion head coincides with a secondaryRegion head.
 	 */
-	private static boolean isSharedHead(@NonNull Region primaryRegion, @NonNull Region secondaryRegion) {
-		for (Node primaryHead : primaryRegion.getHeadNodes()) {
+	protected boolean isSharedHead(@NonNull Region primaryRegion, @NonNull Region secondaryRegion) {
+		for (@NonNull Node primaryHead : primaryRegion.getHeadNodes()) {
 			ClassDatumAnalysis primaryClassDatumAnalysis = primaryHead.getClassDatumAnalysis();
-			for (Node secondaryHead : secondaryRegion.getHeadNodes()) {
+			for (@NonNull Node secondaryHead : secondaryRegion.getHeadNodes()) {
 				if (primaryClassDatumAnalysis == secondaryHead.getClassDatumAnalysis()) {
 					return true;
 				}
@@ -394,10 +369,94 @@ public class EarlyMerger
 		return false;
 	}
 
+	private boolean isToOne(@Nullable TypedElement typedElement) {
+		if (typedElement == null) {
+			return false;
+		}
+		if (!typedElement.isIsRequired()) {
+			return false;
+		}
+		Type type = typedElement.getType();
+		if (type instanceof CollectionType) {
+			return false;
+		}
+		else {
+			return true;
+		}
+	}
+
+	private boolean isToZeroOrOne(@Nullable TypedElement typedElement) {
+		if (typedElement == null) {
+			return false;
+		}
+		Type type = typedElement.getType();
+		if (type instanceof CollectionType) {
+			return false;
+		}
+		else {
+			return true;
+		}
+	}
+
+	/**
+	 * Replace those orderedRegions that may be aggregated as part of a GuardedRegion decision tree by GuardedRegions.
+	 * orderedRegions should be naturally ordered to ensure that non-recursive dependencies are inherently satisfied.
+	 *
+	 * Returns the orderedRegions plus the new aggregates less those aggregated.
+	 */
+	protected @NonNull List<@NonNull MappingRegion> merge() {
+		while (!residualInputRegions.isEmpty()) {		// Subject to nested removal
+			@NonNull MappingRegion candidateRegion = residualInputRegions.iterator().next();
+			MappingRegion mergedRegion = null;
+			if (isPrimaryCandidate(candidateRegion)) {
+				Iterable<@NonNull MappingRegion> secondaryRegions = selectSecondaryRegions(candidateRegion);
+				if (secondaryRegions != null) {
+					mergedRegion = merge(candidateRegion, secondaryRegions);
+				}
+			}
+			if (mergedRegion == null) {
+				outputRegions.add(candidateRegion);
+			}
+			else {
+				outputRegions.add(mergedRegion);
+				if (QVTp2QVTs.DEBUG_GRAPHS.isActive()) {
+					mergedRegion.writeDebugGraphs("2-merged");
+				}
+			}
+			residualInputRegions.remove(candidateRegion);
+		}
+		return outputRegions;
+	}
+
+	protected @Nullable MappingRegion merge(@NonNull MappingRegion candidateRegion, @NonNull Iterable<@NonNull MappingRegion> secondaryRegions) {
+		MappingRegion primaryRegion = candidateRegion;
+		MappingRegion mergedRegion = null;
+		for (@NonNull MappingRegion secondaryRegion : secondaryRegions) {
+			if (residualInputRegions.contains(secondaryRegion)) {
+				Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = canMerge(primaryRegion, secondaryRegion, region2depths, false);
+				if (secondaryNode2primaryNode != null) {
+					boolean isSharedHead = isSharedHead(primaryRegion, secondaryRegion);
+					if (!isSharedHead || (canMerge(secondaryRegion, primaryRegion, region2depths, false) != null)) {
+						residualInputRegions.remove(mergedRegion);
+						residualInputRegions.remove(secondaryRegion);
+						RegionMerger regionMerger = new RegionMerger(primaryRegion);
+						regionMerger.addSecondaryRegion(secondaryRegion, secondaryNode2primaryNode);
+						regionMerger.prune();
+						mergedRegion = regionMerger.create();
+						regionMerger.check(mergedRegion);
+						region2depths.addRegion(mergedRegion);
+						primaryRegion = mergedRegion;
+					}
+				}
+			}
+		}
+		return mergedRegion;
+	}
+
 	/**
 	 * Chose the headNode from a group of peer nodes that has the most non-implicit properties targeting its peers.
 	 */
-	protected static @NonNull Node selectBestHeadNode(@NonNull List<@NonNull Node> headNodes) {
+	protected @NonNull Node selectBestHeadNode(@NonNull List<@NonNull Node> headNodes) {
 		int size = headNodes.size();
 		assert size >= 1;
 		if (size == 1) {
@@ -429,7 +488,7 @@ public class EarlyMerger
 		return bestHeadNode;
 	}
 
-	private static @Nullable Node selectMergedHeadNode(@NonNull Node headNode, @NonNull List<@NonNull Node> mergedNodes) {
+	protected @Nullable Node selectMergedHeadNode(@NonNull Node headNode, @NonNull List<@NonNull Node> mergedNodes) {
 		if (mergedNodes.size() == 1) {
 			Node mergedNode = selectBestHeadNode(mergedNodes);
 			if (mergedNode.isIterator()) {
@@ -466,54 +525,38 @@ public class EarlyMerger
 	/**
 	 * Return a list of single-headed to-one navigable regions whose head is transitively to-one reachable from the primaryRegion's head.
 	 */
-	private static @Nullable List<@NonNull MappingRegion> selectSecondaryRegions(@NonNull MappingRegion primaryRegion) {
+	protected @Nullable Iterable<@NonNull MappingRegion> selectSecondaryRegions(@NonNull MappingRegion primaryRegion) {
 		//
-		//	All regions that consume one of the primary nodes.
+		//	Find the classes that could be consumed by a secondary region head, and the number
+		//	of possible consuming contexts.
 		//
-		Set<@NonNull MappingRegion> allConsumingRegions = new HashSet<>();
-		allConsumingRegions.add(primaryRegion);
+		Map<@NonNull ClassDatumAnalysis, @NonNull Integer> hostClass2count = new HashMap<>();
+		for (@NonNull Node hostNode : getHostNodes(primaryRegion)) {
+			ClassDatumAnalysis hostClassDatumAnalysis = hostNode.getClassDatumAnalysis();
+			Integer count = hostClass2count.get(hostClassDatumAnalysis);
+			hostClass2count.put(hostClassDatumAnalysis, count != null ? count+1 : 1);
+		}
 		//
-		//	All classes reachable from the primary head.
+		//	Find the secondary regions for single possibility host classes.
 		//
-		Set<org.eclipse.qvtd.compiler.internal.qvtp2qvts.analysis.ClassDatumAnalysis> toOneReachableClasses = new HashSet<>();
-		List<@NonNull MappingRegion> secondaryRegions = null;
-		List<@NonNull MappingRegion> allConsumingRegionsList = new ArrayList<>(allConsumingRegions);	// CME-proof iterable List shadowing a mutating Set
-		for (int i = 0; i < allConsumingRegionsList.size(); i++) {
-			@NonNull MappingRegion secondaryRegion = allConsumingRegionsList.get(i);
-			if ((i == 0) || isEarlyMergeSecondaryCandidate(primaryRegion, secondaryRegion, toOneReachableClasses)) {
-				if (i > 0) {
-					if (secondaryRegions == null) {
-						secondaryRegions = new ArrayList<>();
-					}
-					secondaryRegions.add(secondaryRegion);
-				}
-				for (@NonNull Node predicatedNode : getMergeableNodes(secondaryRegion)) {
-					if (predicatedNode.isClass()) {							// Ignore nulls, attributes
-						ClassDatumAnalysis predicatedClassDatumAnalysis = predicatedNode.getClassDatumAnalysis();
-						if (toOneReachableClasses.add(predicatedClassDatumAnalysis)) {
-							for (@NonNull MappingRegion consumingRegion : predicatedClassDatumAnalysis.getConsumingRegions()) {
-								if (allConsumingRegions.add(consumingRegion)) {
-									allConsumingRegionsList.add(consumingRegion);
-								}
-							}
-						}
-					}
-				}
-				for (@NonNull Node newNode : secondaryRegion.getNewNodes()) {
-					if (newNode.isClass()) {							// Ignore nulls, attributes
-						ClassDatumAnalysis consumingClassDatumAnalysis = newNode.getClassDatumAnalysis();
-						if (toOneReachableClasses.add(consumingClassDatumAnalysis)) {
-							for (@NonNull MappingRegion consumingRegion : consumingClassDatumAnalysis.getConsumingRegions()) {
-								if (allConsumingRegions.add(consumingRegion)) {
-									allConsumingRegionsList.add(consumingRegion);
-								}
+		Set<@NonNull MappingRegion> secondaryRegions = new HashSet<>();
+		for (Map.Entry<@NonNull ClassDatumAnalysis, @NonNull Integer> entry : hostClass2count.entrySet()) {
+			if (entry.getValue() == 1) {
+				ClassDatumAnalysis primaryClassDatumAnalysis = entry.getKey();
+				for (@NonNull MappingRegion secondaryRegion : primaryClassDatumAnalysis.getConsumingRegions()) {
+					if (secondaryRegion != primaryRegion) {
+						for (@NonNull Node secondaryHeadNode : secondaryRegion.getHeadNodes()) {
+							if (secondaryHeadNode.getClassDatumAnalysis() == primaryClassDatumAnalysis) {
+								secondaryRegions.add(secondaryRegion);
+								break;
 							}
 						}
 					}
 				}
 			}
 		}
-		assert allConsumingRegionsList.size() == allConsumingRegions.size();					// Check same changes to CME-proof shadow
-		return secondaryRegions;
+		List<@NonNull MappingRegion> sortedSecondaryRegions = new ArrayList<>(secondaryRegions);
+		Collections.sort(sortedSecondaryRegions,NameUtil.NAMEABLE_COMPARATOR);
+		return sortedSecondaryRegions;
 	}
 }
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EdgeMerger.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EdgeMerger.java
new file mode 100644
index 000000000..a6e738ce4
--- /dev/null
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EdgeMerger.java
@@ -0,0 +1,143 @@
+/*******************************************************************************
+ * Copyright (c) 2016 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.List;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.ocl.pivot.Property;
+import org.eclipse.ocl.pivot.utilities.ClassUtil;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Edge;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.EdgeRole;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.NavigableEdge;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Node;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.RegionUtil;
+
+/**
+ * An EdgeMerger gathers the contributions for an edge in a merged region and supports
+ * optimization of the to be created merged region.
+ */
+class EdgeMerger
+{
+	protected final @NonNull RegionMerger regionMerger;
+	protected final @NonNull NodeMerger mergedSourceNodeMerger;
+	protected final @NonNull NodeMerger mergedTargetNodeMerger;
+	protected final @NonNull List<@NonNull Edge> oldEdges = new ArrayList<>();
+	private @NonNull EdgeRole edgeRole;
+	private @Nullable Edge newEdge = null;
+
+	public EdgeMerger(@NonNull RegionMerger regionMerger, @NonNull Edge oldEdge) {
+		assert !oldEdge.isSecondary();
+		this.regionMerger = regionMerger;
+		mergedSourceNodeMerger = regionMerger.getNodeMerger(oldEdge.getSource());
+		mergedTargetNodeMerger = regionMerger.getNodeMerger(oldEdge.getTarget());
+		oldEdges.add(oldEdge);
+		edgeRole = oldEdge.getEdgeRole();
+		regionMerger.mapOldEdge(oldEdge, this);
+		mergedSourceNodeMerger.addOutgoingEdgeMerger(this, mergedTargetNodeMerger);
+		mergedTargetNodeMerger.addIncomingEdgeMerger(this, mergedSourceNodeMerger);
+	}
+
+	public void addOldEdge(@NonNull Edge oldEdge) {
+		assert !oldEdge.isSecondary();
+		assert !oldEdges.contains(oldEdge);
+		oldEdges.add(oldEdge);
+		edgeRole = RegionUtil.mergeToMoreKnownPhase(edgeRole, oldEdge.getEdgeRole());
+		regionMerger.mapOldEdge(oldEdge, this);
+	}
+
+	public @Nullable Edge createNewEdge(@NonNull Node sourceNodeMerger, @NonNull Node targetNodeMerger) {
+		Edge newEdge2 = newEdge;
+		assert newEdge2 == null;
+		for (@NonNull Edge oldEdge : oldEdges) {
+			newEdge2 = newEdge = oldEdge.createEdge(edgeRole, sourceNodeMerger, targetNodeMerger);
+			break;
+		}
+		if (newEdge2 == null) {
+			return null;
+		}
+		return newEdge2;
+	}
+
+	public void destroy() {
+		mergedSourceNodeMerger.removeOutgoingEdgeMerger(this, mergedTargetNodeMerger);
+		mergedTargetNodeMerger.removeIncomingEdgeMerger(this, mergedSourceNodeMerger);
+		for (@NonNull Edge oldEdge : oldEdges) {
+			regionMerger.unmapOldEdge(oldEdge, this);
+		}
+	}
+
+	public @NonNull Edge getNewEdge() {
+		return ClassUtil.nonNullState(newEdge);
+	}
+
+	public @NonNull Iterable<@NonNull Edge> getOldEdges() {
+		return oldEdges;
+	}
+
+	public @NonNull Node getOldSource() {
+		return oldEdges.get(0).getSource();
+	}
+
+	public @NonNull Node getOldTarget() {
+		return oldEdges.get(0).getTarget();
+	}
+
+	public @NonNull NodeMerger getSource() {
+		return mergedSourceNodeMerger;
+	}
+
+	public @NonNull NodeMerger getTarget() {
+		return mergedTargetNodeMerger;
+	}
+
+	private boolean isCast() {
+		return oldEdges.get(0).isCast();
+	}
+
+	public boolean isFoldable() {
+		return isCast() && mergedTargetNodeMerger.isNew() && !mergedSourceNodeMerger.isNew();
+	}
+
+	/**
+	 * Return an oldEdge that is the same as newEdge or null if none.
+	 */
+	public @Nullable Edge sameEdge(@NonNull Edge newEdge) {
+		if (newEdge instanceof NavigableEdge) {
+			Property newProperty = ((NavigableEdge)newEdge).getProperty();
+			for (@NonNull Edge oldEdge : oldEdges) {
+				if (oldEdge instanceof NavigableEdge) {
+					Property oldProperty = ((NavigableEdge)oldEdge).getProperty();
+					if (oldProperty == newProperty) {
+						return oldEdge;
+					}
+				}
+			}
+		}
+		else {
+			Class<? extends @NonNull Edge> newClass = newEdge.getClass();
+			for (@NonNull Edge oldEdge : oldEdges) {
+				Class<? extends @NonNull Edge> oldClass = oldEdge.getClass();
+				if (oldClass == newClass) {
+					return oldEdge;
+				}
+			}
+		}
+		return null;
+	}
+
+	@Override
+	public String toString() {
+		return newEdge != null? newEdge.toString() : oldEdges.get(0).toString();
+	}
+}
\ No newline at end of file
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/NodeMerger.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/NodeMerger.java
new file mode 100644
index 000000000..7481172a8
--- /dev/null
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/NodeMerger.java
@@ -0,0 +1,161 @@
+/*******************************************************************************
+ * Copyright (c) 2016 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.List;
+import java.util.Map;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.ocl.pivot.TypedElement;
+import org.eclipse.ocl.pivot.utilities.ClassUtil;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MappingRegion;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Node;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.NodeRole;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.RegionUtil;
+
+/**
+ * A NodeMerger gathers the contributions for a node in a merged region and supports
+ * optimization of the to be created merged region.
+ */
+class NodeMerger
+{
+	protected final @NonNull RegionMerger regionMerger;
+	protected final @NonNull List<@NonNull Node> oldNodes = new ArrayList<>();
+	private @NonNull NodeRole nodeRole;
+	private Node.@NonNull Utility nodeUtility;
+	private @NonNull Map<@NonNull NodeMerger, @NonNull List<@NonNull EdgeMerger>> sourceNodeMerger2edgeMergers = new HashMap<>();
+	private @NonNull Map<@NonNull NodeMerger, @NonNull List<@NonNull EdgeMerger>> targetNodeMerger2edgeMergers = new HashMap<>();
+	private @Nullable Node newNode = null;
+
+	public NodeMerger(@NonNull RegionMerger regionMerger, @NonNull Node oldNode) {
+		this.regionMerger = regionMerger;
+		oldNodes.add(oldNode);
+		nodeRole = oldNode.getNodeRole();
+		nodeUtility = oldNode.getUtility();
+		regionMerger.mapOldNode(oldNode, this);
+	}
+
+	public void addIncomingEdgeMerger(@NonNull EdgeMerger edgeMerger, @NonNull NodeMerger sourceNodeMerger) {
+		List<@NonNull EdgeMerger> edgeMergers = getIncomingEdgeMergers(sourceNodeMerger);
+		assert !edgeMergers.contains(edgeMerger);
+		edgeMergers.add(edgeMerger);
+	}
+
+	public void addOutgoingEdgeMerger(@NonNull EdgeMerger edgeMerger, @NonNull NodeMerger targetNodeMerger) {
+		List<@NonNull EdgeMerger> edgeMergers = getOutgoingEdgeMergers(targetNodeMerger);
+		assert !edgeMergers.contains(edgeMerger);
+		edgeMergers.add(edgeMerger);
+	}
+
+	public void addOldNode(@NonNull Node oldNode) {
+		assert !oldNodes.contains(oldNode);
+		oldNodes.add(oldNode);
+		nodeRole = RegionUtil.mergeToMoreKnownPhase(nodeRole, oldNode.getNodeRole());
+		nodeUtility = RegionUtil.mergeToStrongerUtility(nodeUtility, oldNode.getUtility());
+		regionMerger.mapOldNode(oldNode, this);
+	}
+
+	public @Nullable Node createNewNode(@NonNull MappingRegion newRegion) {
+		Node newNode2 = newNode;
+		assert newNode2 == null;
+		for (@NonNull Node oldNode : oldNodes) {
+			newNode2 = newNode = oldNode.createNode(nodeRole, newRegion);
+			newNode2.setUtility(nodeUtility);
+			break;
+		}
+		if (newNode2 == null) {
+			return null;
+		}
+		for (@NonNull Node oldNode : oldNodes) {
+			//				oldNode2mergedNode.put(oldNode, mergedNode);
+			for (@NonNull TypedElement typedElement : oldNode.getTypedElements()) {
+				newNode2.addTypedElement(typedElement);
+			}
+		}
+		return newNode2;
+	}
+
+	public void destroy() {
+		for (@NonNull List<@NonNull EdgeMerger> incomingEdgeMergers : sourceNodeMerger2edgeMergers.values()) {
+			for (int i = incomingEdgeMergers.size(); --i >= 0; ) {		// Down count to avoid CME
+				incomingEdgeMergers.get(i).destroy();
+			}
+		}
+		for (@NonNull List<@NonNull EdgeMerger> outgoingEdgeMergers : targetNodeMerger2edgeMergers.values()) {
+			for (int i = outgoingEdgeMergers.size(); --i >= 0; ) {		// Down count to avoid CME
+				outgoingEdgeMergers.get(i).destroy();
+			}
+		}
+		for (@NonNull Node oldNode : oldNodes) {
+			regionMerger.unmapOldNode(oldNode, this);
+		}
+	}
+
+	public void gatherFoldableEdges(@NonNull List<@NonNull EdgeMerger> foldableEdgeMergers) {
+		for (@NonNull List<@NonNull EdgeMerger> outgoingEdgeMergers : targetNodeMerger2edgeMergers.values()) {
+			for (@NonNull EdgeMerger edgeMerger : outgoingEdgeMergers) {
+				if (edgeMerger.isFoldable()) {
+					foldableEdgeMergers.add(edgeMerger);
+				}
+			}
+		}
+	}
+
+	public @NonNull List<@NonNull EdgeMerger> getIncomingEdgeMergers(@NonNull NodeMerger sourceNodeMerger) {
+		List<@NonNull EdgeMerger> edgeMergers = sourceNodeMerger2edgeMergers.get(sourceNodeMerger);
+		if (edgeMergers == null) {
+			edgeMergers = new ArrayList<>();
+			sourceNodeMerger2edgeMergers.put(sourceNodeMerger, edgeMergers);
+		}
+		return edgeMergers;
+	}
+
+	public @NonNull Node getNewNode() {
+		return ClassUtil.nonNullState(newNode);
+	}
+
+	public @NonNull Iterable<@NonNull Node> getOldNodes() {
+		return oldNodes;
+	}
+
+	public @NonNull List<@NonNull EdgeMerger> getOutgoingEdgeMergers(@NonNull NodeMerger targetNodeMerger) {
+		List<@NonNull EdgeMerger> edgeMergers = targetNodeMerger2edgeMergers.get(targetNodeMerger);
+		if (edgeMergers == null) {
+			edgeMergers = new ArrayList<>();
+			targetNodeMerger2edgeMergers.put(targetNodeMerger, edgeMergers);
+		}
+		return edgeMergers;
+	}
+
+	public boolean isNew() {
+		return nodeRole.isNew();
+	}
+
+	public void removeIncomingEdgeMerger(@NonNull EdgeMerger edgeMerger, @NonNull NodeMerger sourceNodeMerger) {
+		List<@NonNull EdgeMerger> edgeMergers = getIncomingEdgeMergers(sourceNodeMerger);
+		boolean wasRemoved = edgeMergers.remove(edgeMerger);
+		assert wasRemoved;
+	}
+
+	public void removeOutgoingEdgeMerger(@NonNull EdgeMerger edgeMerger, @NonNull NodeMerger targetNodeMerger) {
+		List<@NonNull EdgeMerger> edgeMergers = getOutgoingEdgeMergers(targetNodeMerger);
+		boolean wasRemoved = edgeMergers.remove(edgeMerger);
+		assert wasRemoved;
+	}
+
+	@Override
+	public @NonNull String toString() {
+		return newNode != null? newNode.toString() : oldNodes.get(0).toString();
+	}
+}
\ No newline at end of file
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/RegionMerger.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/RegionMerger.java
new file mode 100644
index 000000000..e922f628f
--- /dev/null
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/RegionMerger.java
@@ -0,0 +1,271 @@
+/*******************************************************************************
+ * Copyright (c) 2016 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.Collections;
+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.ocl.pivot.utilities.ClassUtil;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Edge;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MappingRegion;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MicroMappingRegion;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.NamedMappingRegion;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Node;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Region;
+
+import com.google.common.collect.Iterables;
+
+/**
+ * RegionMerger provides the ability to merge one or more secondary regions into a primary region to
+ * create a new merged region.
+ *
+ * RegionMerger is used by classes such as EarlyMerger and LateMerger that orchestrate what may be merged safely.
+ */
+class RegionMerger // implements Region
+{
+	/**
+	 * The primary original region contributing to the merged region.
+	 */
+	protected final @NonNull MappingRegion primaryRegion;
+
+	/**
+	 * Additional secondary region contributing to the merged region.
+	 */
+	protected final @NonNull List<@NonNull MappingRegion> secondaryRegions = new ArrayList<>();
+
+	/**
+	 * Nodes to be merged from a secondary region mapped to a corresponding primary region node.
+	 */
+	protected final @NonNull Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = new HashMap<>();
+
+	/**
+	 * Mapping from each primary and secondary region node to the corresponding merged node.
+	 */
+	protected final @NonNull Map<@NonNull Node, @NonNull NodeMerger> oldNode2nodeMerger = new HashMap<>();
+
+	/**
+	 * Mapping from each primary and secondary region edge to the corresponding merged edge.
+	 */
+	private final @NonNull Map<@NonNull Edge, @NonNull EdgeMerger> oldEdge2edgeMerger = new HashMap<>();
+
+	/**
+	 * The original edges that are not represented in the result.
+	 */
+	private /*@LazyNonNull*/ Set<@NonNull Edge> debugPrunedEdges = null;
+
+	protected RegionMerger(@NonNull MappingRegion primaryRegion) {
+		this.primaryRegion = primaryRegion;
+		assert !(primaryRegion instanceof MicroMappingRegion);
+		//
+		for (@NonNull Node primaryNode : primaryRegion.getNodes()) {
+			new NodeMerger(this, primaryNode);
+		}
+		//
+		for (@NonNull Edge primaryEdge : primaryRegion.getEdges()) {
+			if (!primaryEdge.isSecondary()) {
+				new EdgeMerger(this, primaryEdge);
+			}
+		}
+	}
+
+	private void addPrunedEdge(@NonNull Edge prunedEdge) {
+		Set<@NonNull Edge> debugPrunedEdges2 = debugPrunedEdges;
+		if (debugPrunedEdges2 == null) {
+			debugPrunedEdges2 = debugPrunedEdges = new HashSet<>();
+		}
+		boolean wasAdded = debugPrunedEdges2.add(prunedEdge);
+		assert wasAdded;
+	}
+
+	protected void addSecondaryEdge(@NonNull Edge secondaryEdge) {
+		NodeMerger sourceNodeMerger = getNodeMerger(secondaryEdge.getSource());
+		NodeMerger targetNodeMerger = getNodeMerger(secondaryEdge.getTarget());
+		if (sourceNodeMerger != targetNodeMerger) {
+			boolean isMerged = false;
+			for (@NonNull EdgeMerger edgeMerger : sourceNodeMerger.getOutgoingEdgeMergers(targetNodeMerger)) {
+				if (edgeMerger.sameEdge(secondaryEdge) != null) {
+					edgeMerger.addOldEdge(secondaryEdge);
+					isMerged = true;
+					break;
+				}
+			}
+			if (!isMerged) {
+				new EdgeMerger(this, secondaryEdge);
+			}
+		}
+		else {
+			addPrunedEdge(secondaryEdge);
+		}
+	}
+
+	public void addSecondaryRegion(@NonNull MappingRegion secondaryRegion, @NonNull Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode) {
+		assert !(secondaryRegion instanceof MicroMappingRegion);
+		assert !secondaryRegions.contains(secondaryRegion);
+		secondaryRegions.add(secondaryRegion);
+		this.secondaryNode2primaryNode.putAll(secondaryNode2primaryNode);
+		//
+		for (@NonNull Node secondaryNode : secondaryRegion.getNodes()) {
+			Node primaryNode = secondaryNode2primaryNode.get(secondaryNode);
+			if (primaryNode != null) {
+				NodeMerger nodeMerger = oldNode2nodeMerger.get(primaryNode);
+				assert nodeMerger != null;
+				nodeMerger.addOldNode(secondaryNode);
+			}
+			else {
+				new NodeMerger(this, secondaryNode);
+			}
+		}
+		//
+		for (@NonNull Edge secondaryEdge : secondaryRegion.getEdges()) {
+			if (!secondaryEdge.isSecondary()) {
+				addSecondaryEdge(secondaryEdge);
+			}
+		}
+	}
+
+	public void check(@NonNull MappingRegion newRegion) {
+		checkNodes(newRegion, primaryRegion);
+		for (@NonNull Region secondaryRegion : secondaryRegions) {
+			checkNodes(newRegion, secondaryRegion);
+		}
+		checkEdges(newRegion, primaryRegion);
+		for (@NonNull Region secondaryRegion : secondaryRegions) {
+			checkEdges(newRegion, secondaryRegion);
+		}
+	}
+
+	protected void checkEdges(@NonNull MappingRegion newRegion, @NonNull Region oldRegion) {
+		for (@NonNull Edge oldEdge : oldRegion.getEdges()) {
+			assert oldEdge.getRegion() == oldRegion;
+			if (!oldEdge.isRecursion() && !oldEdge.isSecondary()) {		// FIXME Remove this irregularity
+				EdgeMerger edgeMerger = oldEdge2edgeMerger.get(oldEdge);
+				if (edgeMerger != null) {
+					assert Iterables.contains(edgeMerger.getOldEdges(), oldEdge);
+					assert edgeMerger.getNewEdge().getRegion() == newRegion;
+				}
+				else {
+					assert debugPrunedEdges.contains(oldEdge);
+				}
+			}
+		}
+	}
+
+	protected void checkNodes(@NonNull MappingRegion newRegion, @NonNull Region oldRegion) {
+		for (@NonNull Node oldNode : oldRegion.getNodes()) {
+			assert oldNode.getRegion() == oldRegion;
+			Node nodeMerger = getNodeMerger(oldNode).getNewNode();
+			assert nodeMerger.getRegion() == newRegion;
+		}
+	}
+
+	public @NonNull MappingRegion create() {
+		@NonNull String newName = createNewName();
+		MappingRegion newRegion = createNewRegion(newName);
+		createNewNodes(newRegion);
+		createNewEdges();
+		return newRegion;
+	}
+
+	protected @NonNull String createNewName() {
+		List<@NonNull String> names = new ArrayList<>();
+		names.add(primaryRegion.getName());
+		for (@NonNull MappingRegion secondaryRegion : secondaryRegions) {
+			names.add(secondaryRegion.getName());
+		}
+		Collections.sort(names);
+		StringBuilder s = new StringBuilder();
+		for (@NonNull String name : names) {
+			if (s.length() > 0) {
+				s.append("\\n");
+			}
+			s.append(name);
+		}
+		return s.toString();
+	}
+
+	protected void createNewEdges() {
+		for (@NonNull EdgeMerger edgeMerger : new HashSet<>(oldEdge2edgeMerger.values())) {
+			Node sourceNodeMerger = getNodeMerger(edgeMerger.getOldSource()).getNewNode();
+			Node targetNodeMerger = getNodeMerger(edgeMerger.getOldTarget()).getNewNode();
+			edgeMerger.createNewEdge(sourceNodeMerger, targetNodeMerger);
+		}
+	}
+
+	protected void createNewNodes(@NonNull MappingRegion newRegion) {
+		for (@NonNull NodeMerger nodeMerger : new HashSet<>(oldNode2nodeMerger.values())) {
+			nodeMerger.createNewNode(newRegion);
+		}
+	}
+
+	protected @NonNull MappingRegion createNewRegion(@NonNull String newName) {
+		return new NamedMappingRegion(primaryRegion.getMultiRegion(), newName);
+	}
+
+	protected @NonNull EdgeMerger getEdgeMerger(@NonNull Edge oldEdge) {
+		return ClassUtil.nonNullState(oldEdge2edgeMerger.get(oldEdge));
+	}
+
+	protected @NonNull NodeMerger getNodeMerger(@NonNull Node oldNode) {
+		return ClassUtil.nonNullState(oldNode2nodeMerger.get(oldNode));
+	}
+
+	protected void mapOldEdge(@NonNull Edge oldEdge, @NonNull EdgeMerger edgeMerger) {
+		EdgeMerger oldMergedEdge = oldEdge2edgeMerger.put(oldEdge, edgeMerger);
+		assert oldMergedEdge == null;
+	}
+
+	protected void mapOldNode(@NonNull Node oldNode, @NonNull NodeMerger nodeMerger) {
+		NodeMerger oldMergedNode = oldNode2nodeMerger.put(oldNode, nodeMerger);
+		assert oldMergedNode == null;
+	}
+
+	public void prune() {
+		List<@NonNull EdgeMerger> foldableEdgeMergers = new ArrayList<>();
+		for (@NonNull NodeMerger nodeMerger : new HashSet<>(oldNode2nodeMerger.values())) {
+			nodeMerger.gatherFoldableEdges(foldableEdgeMergers);
+		}
+		for (@NonNull EdgeMerger foldableEdgeMerger : foldableEdgeMergers) {
+			NodeMerger sourceNodeMerger = foldableEdgeMerger.getSource();
+			NodeMerger targetNodeMerger = foldableEdgeMerger.getTarget();
+			sourceNodeMerger.destroy();
+			for (@NonNull Node oldNode : sourceNodeMerger.getOldNodes()) {
+				targetNodeMerger.addOldNode(oldNode);
+				for (@NonNull Edge oldEdge : oldNode.getIncomingEdges()) {
+					addSecondaryEdge(oldEdge);
+				}
+				for (@NonNull Edge oldEdge : oldNode.getOutgoingEdges()) {
+					addSecondaryEdge(oldEdge);
+				}
+			}
+		}
+	}
+
+	@Override
+	public String toString() {
+		return createNewName();
+	}
+
+	protected void unmapOldEdge(@NonNull Edge oldEdge, @NonNull EdgeMerger edgeMerger) {
+		EdgeMerger oldEdgeMerger = oldEdge2edgeMerger.remove(oldEdge);
+		assert oldEdgeMerger == edgeMerger;
+	}
+
+	protected void unmapOldNode(@NonNull Node oldNode, @NonNull NodeMerger nodeMerger) {
+		NodeMerger oldNodeMerger = oldNode2nodeMerger.remove(oldNode);
+		assert oldNodeMerger == nodeMerger;
+	}
+}
diff --git a/plugins/org.eclipse.qvtd.pivot.qvtbase/annotations/com/google/common/collect/Sets.eea b/plugins/org.eclipse.qvtd.pivot.qvtbase/annotations/com/google/common/collect/Sets.eea
index cf083f768..a93c33d6a 100644
--- a/plugins/org.eclipse.qvtd.pivot.qvtbase/annotations/com/google/common/collect/Sets.eea
+++ b/plugins/org.eclipse.qvtd.pivot.qvtbase/annotations/com/google/common/collect/Sets.eea
@@ -5,3 +5,6 @@ newHashSet
 newHashSet
  <E:Ljava/lang/Object;>([TE;)Ljava/util/HashSet<TE;>;
  <E:Ljava/lang/Object;>([TE;)L1java/util/HashSet<TE;>;
+newLinkedHashSet
+ <E:Ljava/lang/Object;>(Ljava/lang/Iterable<+TE;>;)Ljava/util/LinkedHashSet<TE;>;
+ <E:Ljava/lang/Object;>(Ljava/lang/Iterable<+TE;>;)L1java/util/LinkedHashSet<TE;>;