wip EarlyRegionMergerewillink/486722

9 files changed, 281 insertions, 200 deletions

diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractScheduledRegion.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractScheduledRegion.java
index b4bc62b22..cdd2c49a1 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractScheduledRegion.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractScheduledRegion.java
@@ -22,6 +22,7 @@ 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.qvts2qvti.QVTs2QVTiVisitor;
 import org.eclipse.qvtd.compiler.internal.utilities.SymbolNameBuilder;
 import org.eclipse.qvtd.pivot.qvtbase.TypedModel;
@@ -36,7 +37,7 @@ public abstract class AbstractScheduledRegion extends AbstractRegion implements
 	/**
 	 * All regions within this scheduled region.
 	 */
-	private final @NonNull List<@NonNull Region> regions = new ArrayList<@NonNull Region>();
+	private /*@LazyNonNull*/ List<@NonNull Region> regions = null;
 
 	/**
 	 * All the connections defined in this region, but not those in nested regions.
@@ -365,7 +366,7 @@ public abstract class AbstractScheduledRegion extends AbstractRegion implements
 
 	@Override
 	public @NonNull List<@NonNull Region> getRegions() {
-		return regions;
+		return ClassUtil.nonNullState(regions);
 	}
 
 	@Override
@@ -420,6 +421,13 @@ public abstract class AbstractScheduledRegion extends AbstractRegion implements
 		removeConnection(connection);
 	}
 
+	protected void setRegions(@NonNull Iterable<@NonNull Region> regions) {
+		this.regions = new ArrayList<>();
+		for (@NonNull Region region : regions) {
+			region.setInvokingRegion(this);
+			this.regions.add(region);
+		}
+	}
 
 	/**
 	 * After cycles have been removed, split looped connection variables to isolate the unlooping base case, from the/each looping case.
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/MultiRegion.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/MultiRegion.java
index 4dac9cd88..82ec174e6 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/MultiRegion.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/MultiRegion.java
@@ -11,12 +11,12 @@
 package org.eclipse.qvtd.compiler.internal.qvtp2qvts;
 
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.List;
 
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.ocl.pivot.OperationCallExp;
 import org.eclipse.ocl.pivot.StandardLibrary;
+import org.eclipse.ocl.pivot.utilities.ClassUtil;
 import org.eclipse.qvtd.pivot.schedule.AbstractAction;
 
 import com.google.common.collect.Iterables;
@@ -35,8 +35,8 @@ public class MultiRegion
 	//	private final @NonNull Map<Type, Property> type2castProperty = new HashMap<>();
 
 	private final @NonNull List<@NonNull Region> allRegions = new ArrayList<>();
-
-	private @NonNull List<@NonNull Region> activeRegions = Collections.emptyList();
+	//	private @NonNull List<@NonNull Region> activeRegions = Collections.emptyList();
+	private /*@LazyNonNull*/ List<@NonNull SimpleMappingRegion> orderedRegions = null;
 
 	public MultiRegion(@NonNull QVTp2QVTs qvtp2qvts) {
 		this.qvtp2qvts = qvtp2qvts;
@@ -54,9 +54,9 @@ public class MultiRegion
 		return qvtp2qvts.analyzeOperation(this, operationCallExp);
 	}
 
-	public @NonNull List<@NonNull Region> getActiveRegions() {
-		return activeRegions;
-	}
+	//	public @NonNull List<@NonNull Region> getActiveRegions() {
+	//		return activeRegions;
+	//	}
 
 	/*	public @NonNull Property getCastProperty(@NonNull Type type) {
 		Property castProperty = type2castProperty.get(type);
@@ -77,6 +77,10 @@ public class MultiRegion
 		return Iterables.filter(allRegions, OperationRegion.class);
 	}
 
+	public @NonNull List<@NonNull SimpleMappingRegion> getOrderedRegions() {
+		return ClassUtil.nonNullState(orderedRegions);
+	}
+
 	//	public @NonNull List<@NonNull Region> getRegions() {
 	//		return allRegions;
 	//	}
@@ -116,7 +120,11 @@ public class MultiRegion
 	//		return activeRegions.remove(region);
 	//	}
 
-	public void setActiveRegions(@NonNull Iterable<@NonNull Region> activeRegions) {	// FIXME eliminate
-		this.activeRegions = Lists.newArrayList(activeRegions);
+	//	public void setActiveRegions(@NonNull Iterable<@NonNull Region> activeRegions) {	// FIXME eliminate
+	//		this.activeRegions = Lists.newArrayList(activeRegions);
+	//	}
+
+	public void setOrderedRegions(@NonNull Iterable<@NonNull SimpleMappingRegion> orderedRegions) {	// FIXME eliminate
+		this.orderedRegions = Lists.newArrayList(orderedRegions);
 	}
 }
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 0ee4753cf..622b05f24 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
@@ -14,14 +14,9 @@ import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.HashMap;
-import java.util.HashSet;
-import java.util.LinkedHashSet;
 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.ExpressionInOCL;
 import org.eclipse.ocl.pivot.LanguageExpression;
 import org.eclipse.ocl.pivot.OCLExpression;
@@ -34,7 +29,6 @@ import org.eclipse.ocl.pivot.utilities.NameUtil;
 import org.eclipse.ocl.pivot.utilities.ParserException;
 import org.eclipse.ocl.pivot.utilities.TracingOption;
 import org.eclipse.qvtd.compiler.CompilerConstants;
-import org.eclipse.qvtd.compiler.internal.qvts2qvts.Region2Depth;
 import org.eclipse.qvtd.pivot.qvtbase.utilities.QVTbaseUtil;
 import org.eclipse.qvtd.pivot.schedule.AbstractAction;
 import org.eclipse.qvtd.pivot.schedule.ClassDatum;
@@ -121,165 +115,12 @@ public class QVTp2QVTs extends SchedulerConstants
 		return new ClassDatumAnalysis(this, classDatum);
 	}
 
-	/**
-	 * 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 @NonNull List<@NonNull Region> earlyRegionMerge(@NonNull List<@NonNull SimpleMappingRegion> orderedRegions) {
-		Region2Depth region2depths = new Region2Depth();
-		List<@NonNull Region> outputRegions = new ArrayList<@NonNull Region>();
-		LinkedHashSet<@NonNull SimpleMappingRegion> residualInputRegions = new LinkedHashSet<@NonNull SimpleMappingRegion>(orderedRegions);	// order preserving fast random removal
-		while (!residualInputRegions.isEmpty()) {
-			@NonNull Region candidateRegion = residualInputRegions.iterator().next();
-			boolean isMerged = false;
-			if (isEarlyMergePrimaryCandidate(candidateRegion)) {
-				List<@NonNull Region> secondaryRegions = selectSecondaryRegions(candidateRegion);
-				if (secondaryRegions != null) {
-					Region primaryRegion = candidateRegion;
-					MergedMappingRegion mergedRegion = null;
-					for (@NonNull Region secondaryRegion : secondaryRegions) {
-						assert secondaryRegion != null;
-						if (residualInputRegions.contains(secondaryRegion)) {
-							Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = primaryRegion.canMerge(secondaryRegion, region2depths, false);
-							if (secondaryNode2primaryNode != null) {
-								boolean isSharedHead = isSharedHead(primaryRegion, secondaryRegion);
-								if (!isSharedHead || (secondaryRegion.canMerge(primaryRegion, region2depths, false) != null)) {
-									if (mergedRegion == null) {
-										mergedRegion = new MergedMappingRegion((MergeableRegion)primaryRegion);
-										residualInputRegions.remove(primaryRegion);
-										primaryRegion = mergedRegion;
-									}
-									mergedRegion.mergeRegion(secondaryRegion, secondaryNode2primaryNode);
-									residualInputRegions.remove(secondaryRegion);
-									region2depths.addRegion(mergedRegion);
-								}
-							}
-						}
-					}
-					if (mergedRegion != null) {
-						//						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;
-	}
-
 	public @NonNull SimpleMappingRegion getMappingRegion(@NonNull AbstractAction action) {
 		SimpleMappingRegion mappingRegion = action2mappingRegion.get(action);
 		assert mappingRegion != null;
 		return mappingRegion;
 	}
 
-	/**
-	 * The primary region in a GuardedRegion must be single-headed. It may be multiply-produced, e.g. recursed.
-	 */
-	private 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 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;
-			}
-		}
-		return false;
-	}
-
-	/**
-	 * Return true if any primaryRegion head coincides with a secondaryRegion head.
-	 */
-	private boolean isSharedHead(@NonNull Region primaryRegion, @NonNull Region secondaryRegion) {
-		for (Node primaryHead : primaryRegion.getHeadNodes()) {
-			ClassDatumAnalysis primaryClassDatumAnalysis = primaryHead.getClassDatumAnalysis();
-			for (Node secondaryHead : secondaryRegion.getHeadNodes()) {
-				if (primaryClassDatumAnalysis == secondaryHead.getClassDatumAnalysis()) {
-					return true;
-				}
-			}
-		}
-		return false;
-	}
-
-	/**
-	 * Return a list of single-headed to-one navigable regions whose head is transitively to-one reachable from the primaryRegion's head.
-	 */
-	private @Nullable List<@NonNull Region> selectSecondaryRegions(@NonNull Region primaryRegion) {
-		//
-		//	All regions that consume one of the primary nodes.
-		//
-		Set<@NonNull Region> allConsumingRegions = new HashSet<@NonNull Region>();
-		allConsumingRegions.add(primaryRegion);
-		//
-		//	All classes reachable from the primary head.
-		//
-		Set<@NonNull ClassDatumAnalysis> toOneReachableClasses = new HashSet<@NonNull ClassDatumAnalysis>();
-		List<@NonNull Region> secondaryRegions = null;
-		List<@NonNull Region> allConsumingRegionsList = new ArrayList<@NonNull Region>(allConsumingRegions);	// CME-proof iterable List shadowing a mutating Set
-		for (int i = 0; i < allConsumingRegionsList.size(); i++) {
-			@NonNull Region secondaryRegion = allConsumingRegionsList.get(i);
-			if ((i == 0) || isEarlyMergeSecondaryCandidate(primaryRegion, secondaryRegion, toOneReachableClasses)) {
-				if (i > 0) {
-					if (secondaryRegions == null) {
-						secondaryRegions = new ArrayList<@NonNull Region>();
-					}
-					secondaryRegions.add(secondaryRegion);
-				}
-				for (@NonNull Node predicatedNode : secondaryRegion.getMatchableNodes()) {
-					if (predicatedNode.isClassNode()) {							// Ignore nulls, attributes
-						ClassDatumAnalysis predicatedClassDatumAnalysis = predicatedNode.getClassDatumAnalysis();
-						if (toOneReachableClasses.add(predicatedClassDatumAnalysis)) {
-							for (@NonNull Region consumingRegion : predicatedClassDatumAnalysis.getConsumingRegions()) {
-								if (allConsumingRegions.add(consumingRegion)) {
-									allConsumingRegionsList.add(consumingRegion);
-								}
-							}
-						}
-					}
-				}
-				if (secondaryRegion instanceof SimpleMappingRegion) {
-					for (@NonNull Node assignedNode : ((SimpleMappingRegion)secondaryRegion).getComputedNodes()) {
-						if (assignedNode.isClassNode()) {							// Ignore nulls, attributes
-							ClassDatumAnalysis consumingClassDatumAnalysis = assignedNode.getClassDatumAnalysis();
-							if (toOneReachableClasses.add(consumingClassDatumAnalysis)) {
-								for (@NonNull Region consumingRegion : consumingClassDatumAnalysis.getConsumingRegions()) {
-									if (allConsumingRegions.add(consumingRegion)) {
-										allConsumingRegionsList.add(consumingRegion);
-									}
-								}
-							}
-						}
-					}
-				}
-			}
-		}
-		assert allConsumingRegionsList.size() == allConsumingRegions.size();					// Check same changes to CME-proof shadow
-		return secondaryRegions;
-	}
-
 	public @NonNull MultiRegion transform() throws IOException {
 		MultiRegion multiRegion = new MultiRegion(this);
 		//
@@ -311,11 +152,7 @@ public class QVTp2QVTs extends SchedulerConstants
 			orderedRegions.add(mappingRegion);
 			mappingRegion.resolveRecursion();
 		}
-		List<@NonNull Region> activeRegions = new ArrayList<@NonNull Region>(earlyRegionMerge(orderedRegions));
-		for (@NonNull OperationRegion operationRegion : multiRegion.getOperationRegions()) {
-			activeRegions.add(operationRegion);
-		}
-		multiRegion.setActiveRegions(activeRegions);
+		multiRegion.setOrderedRegions(orderedRegions);
 		return multiRegion;
 	}
 }
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RootScheduledRegion.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RootScheduledRegion.java
index b9f2b2ae6..2673229ea 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RootScheduledRegion.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/RootScheduledRegion.java
@@ -715,7 +715,8 @@ public class RootScheduledRegion extends AbstractScheduledRegion
 		return rootContainmentRegion;
 	}
 
-	public void createSchedule() {
+	public void createSchedule(@NonNull Iterable<@NonNull Region> regions) {
+		setRegions(regions);
 		//
 		//	Identify the input models.
 		//
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/QVTs2QVTs.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/QVTs2QVTs.java
index 4bcf0889a..dac399e7e 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/QVTs2QVTs.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/QVTs2QVTs.java
@@ -21,9 +21,12 @@ import org.eclipse.qvtd.compiler.internal.qvtp2qvts.ScheduledRegion;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.SimpleMappingRegion;
 import org.eclipse.qvtd.compiler.CompilerConstants;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MultiRegion;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.OperationRegion;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.QVTp2QVTs;
+import org.eclipse.qvtd.compiler.internal.qvts2qvts.merger.EarlyRegionMerger;
 import org.eclipse.qvtd.compiler.internal.qvts2qvts.splitter.Split;
 import org.eclipse.qvtd.compiler.internal.qvts2qvts.splitter.Splitter;
+import org.eclipse.qvtd.compiler.internal.utilities.CompilerUtil;
 import org.eclipse.qvtd.pivot.qvtimperative.evaluation.QVTiEnvironmentFactory;
 import org.eclipse.qvtd.pivot.qvtimperative.utilities.QVTimperativeHelper;
 
@@ -49,14 +52,14 @@ public class QVTs2QVTs extends QVTimperativeHelper
 		this.rootName = rootName;
 	}
 
-	public @NonNull RootScheduledRegion createRootRegion(@NonNull List<@NonNull Region> allRegions) {
+	public @NonNull RootScheduledRegion createRootRegion(@NonNull Iterable<@NonNull Region> allRegions) {
 		RootScheduledRegion rootRegion = null;
-		for (@NonNull Region region : new ArrayList<@NonNull Region>(allRegions)) {
+		for (@NonNull Region region : Lists.newArrayList(allRegions)) {
 			if (region.getInvokingRegion() == null) {
 				if (rootRegion == null) {
 					rootRegion = new RootScheduledRegion(region.getMultiRegion(), rootName);
 				}
-				rootRegion.addRegion(region);
+				//				rootRegion.addRegion(region);
 			}
 		}
 		assert rootRegion != null;
@@ -99,23 +102,52 @@ public class QVTs2QVTs extends QVTimperativeHelper
 		}
 	}
 
-	protected void splitMultiHeadedRegions(@NonNull RootScheduledRegion rootRegion) {
-		for (@NonNull Region region : Lists.newArrayList(rootRegion.getRegions())) {
+	/**
+	 * Merge any mappings that are locally compatible. // FIXME do/done in QVTm2QVTp
+	 * Returns a pruned list of mappings.
+	 */
+	protected @NonNull Iterable<@NonNull Region> earlyRegionMerge(@NonNull MultiRegion multiRegion, @NonNull List<@NonNull SimpleMappingRegion> orderedRegions) {
+		EarlyRegionMerger earlyRegionMerger = new EarlyRegionMerger(this);
+		List<@NonNull Region> earlyMergedRegions = new ArrayList<@NonNull Region>(earlyRegionMerger.earlyRegionMerge(orderedRegions));
+		for (@NonNull OperationRegion operationRegion : multiRegion.getOperationRegions()) {
+			earlyMergedRegions.add(operationRegion);
+		}
+		return earlyMergedRegions;
+	}
+
+	protected @NonNull Iterable<@NonNull Region> splitMultiHeadedRegions(@NonNull RootScheduledRegion rootRegion, @NonNull Iterable<@NonNull Region> inputRegions) {
+		List<@NonNull Region> outputRegions = new ArrayList<>();
+		for (@NonNull Region region : inputRegions) {
 			if (region instanceof SimpleMappingRegion) {
-				Splitter splitter = new Splitter((@NonNull SimpleMappingRegion) region);
+				Splitter splitter = new Splitter((SimpleMappingRegion) region);
 				Split split = splitter.split();
 				if (split != null) {
-					split.install(rootRegion);
+					CompilerUtil.addAll(outputRegions, split.install(rootRegion));
 				}
+				else {
+					outputRegions.add(region);
+				}
+			}
+			else {
+				outputRegions.add(region);
 			}
 		}
+		return outputRegions;
 	}
 
 	public @NonNull RootScheduledRegion transform(@NonNull MultiRegion multiRegion) {
-		List<@NonNull Region> activeRegions = multiRegion.getActiveRegions();
-		RootScheduledRegion rootRegion = createRootRegion(activeRegions);
-		splitMultiHeadedRegions(rootRegion);
-		rootRegion.createSchedule();
+		List<@NonNull SimpleMappingRegion> orderedRegions = multiRegion.getOrderedRegions();
+		//
+		//	Merge mappings that are trivially compatible.
+		//
+		Iterable<@NonNull Region> earlyMergedRegions = earlyRegionMerge(multiRegion, orderedRegions);
+		RootScheduledRegion rootRegion = createRootRegion(earlyMergedRegions);
+		//
+		//	Merge mappings that are trivially compatible.
+		//
+		Iterable<@NonNull Region> splitHeadRegions = splitMultiHeadedRegions(rootRegion, earlyMergedRegions);
+		//
+		rootRegion.createSchedule(splitHeadRegions);
 		createSchedule(rootRegion);
 		return rootRegion;
 	}
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EarlyRegionMerger.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EarlyRegionMerger.java
new file mode 100644
index 000000000..47197f7b9
--- /dev/null
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EarlyRegionMerger.java
@@ -0,0 +1,192 @@
+/*******************************************************************************
+ * 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.HashSet;
+import java.util.LinkedHashSet;
+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.qvtd.compiler.internal.qvtp2qvts.ClassDatumAnalysis;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MergeableRegion;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MergedMappingRegion;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Node;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.QVTp2QVTs;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Region;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.SimpleMappingRegion;
+import org.eclipse.qvtd.compiler.internal.qvts2qvts.QVTs2QVTs;
+import org.eclipse.qvtd.compiler.internal.qvts2qvts.Region2Depth;
+
+public class EarlyRegionMerger
+{
+	protected final @NonNull QVTs2QVTs qvts2qvts;
+
+	public EarlyRegionMerger(@NonNull QVTs2QVTs qvts2qvts) {
+		this.qvts2qvts = qvts2qvts;
+	}
+
+	/**
+	 * 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 @NonNull List<@NonNull Region> earlyRegionMerge(@NonNull List<@NonNull SimpleMappingRegion> orderedRegions) {
+		Region2Depth region2depths = new Region2Depth();
+		List<@NonNull Region> outputRegions = new ArrayList<@NonNull Region>();
+		LinkedHashSet<@NonNull SimpleMappingRegion> residualInputRegions = new LinkedHashSet<@NonNull SimpleMappingRegion>(orderedRegions);	// order preserving fast random removal
+		while (!residualInputRegions.isEmpty()) {
+			@NonNull Region candidateRegion = residualInputRegions.iterator().next();
+			boolean isMerged = false;
+			if (isEarlyMergePrimaryCandidate(candidateRegion)) {
+				List<@NonNull Region> secondaryRegions = selectSecondaryRegions(candidateRegion);
+				if (secondaryRegions != null) {
+					Region primaryRegion = candidateRegion;
+					MergedMappingRegion mergedRegion = null;
+					for (@NonNull Region secondaryRegion : secondaryRegions) {
+						assert secondaryRegion != null;
+						if (residualInputRegions.contains(secondaryRegion)) {
+							Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = primaryRegion.canMerge(secondaryRegion, region2depths, false);
+							if (secondaryNode2primaryNode != null) {
+								boolean isSharedHead = isSharedHead(primaryRegion, secondaryRegion);
+								if (!isSharedHead || (secondaryRegion.canMerge(primaryRegion, region2depths, false) != null)) {
+									if (mergedRegion == null) {
+										mergedRegion = new MergedMappingRegion((MergeableRegion)primaryRegion);
+										residualInputRegions.remove(primaryRegion);
+										primaryRegion = mergedRegion;
+									}
+									mergedRegion.mergeRegion(secondaryRegion, secondaryNode2primaryNode);
+									residualInputRegions.remove(secondaryRegion);
+									region2depths.addRegion(mergedRegion);
+								}
+							}
+						}
+					}
+					if (mergedRegion != null) {
+						//						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;
+	}
+
+	/**
+	 * The primary region in a GuardedRegion must be single-headed. It may be multiply-produced, e.g. recursed.
+	 */
+	private 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 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;
+			}
+		}
+		return false;
+	}
+
+	/**
+	 * Return true if any primaryRegion head coincides with a secondaryRegion head.
+	 */
+	private boolean isSharedHead(@NonNull Region primaryRegion, @NonNull Region secondaryRegion) {
+		for (Node primaryHead : primaryRegion.getHeadNodes()) {
+			ClassDatumAnalysis primaryClassDatumAnalysis = primaryHead.getClassDatumAnalysis();
+			for (Node secondaryHead : secondaryRegion.getHeadNodes()) {
+				if (primaryClassDatumAnalysis == secondaryHead.getClassDatumAnalysis()) {
+					return true;
+				}
+			}
+		}
+		return false;
+	}
+
+	/**
+	 * Return a list of single-headed to-one navigable regions whose head is transitively to-one reachable from the primaryRegion's head.
+	 */
+	private @Nullable List<@NonNull Region> selectSecondaryRegions(@NonNull Region primaryRegion) {
+		//
+		//	All regions that consume one of the primary nodes.
+		//
+		Set<@NonNull Region> allConsumingRegions = new HashSet<@NonNull Region>();
+		allConsumingRegions.add(primaryRegion);
+		//
+		//	All classes reachable from the primary head.
+		//
+		Set<@NonNull ClassDatumAnalysis> toOneReachableClasses = new HashSet<@NonNull ClassDatumAnalysis>();
+		List<@NonNull Region> secondaryRegions = null;
+		List<@NonNull Region> allConsumingRegionsList = new ArrayList<@NonNull Region>(allConsumingRegions);	// CME-proof iterable List shadowing a mutating Set
+		for (int i = 0; i < allConsumingRegionsList.size(); i++) {
+			@NonNull Region secondaryRegion = allConsumingRegionsList.get(i);
+			if ((i == 0) || isEarlyMergeSecondaryCandidate(primaryRegion, secondaryRegion, toOneReachableClasses)) {
+				if (i > 0) {
+					if (secondaryRegions == null) {
+						secondaryRegions = new ArrayList<@NonNull Region>();
+					}
+					secondaryRegions.add(secondaryRegion);
+				}
+				for (@NonNull Node predicatedNode : secondaryRegion.getMatchableNodes()) {
+					if (predicatedNode.isClassNode()) {							// Ignore nulls, attributes
+						ClassDatumAnalysis predicatedClassDatumAnalysis = predicatedNode.getClassDatumAnalysis();
+						if (toOneReachableClasses.add(predicatedClassDatumAnalysis)) {
+							for (@NonNull Region consumingRegion : predicatedClassDatumAnalysis.getConsumingRegions()) {
+								if (allConsumingRegions.add(consumingRegion)) {
+									allConsumingRegionsList.add(consumingRegion);
+								}
+							}
+						}
+					}
+				}
+				if (secondaryRegion instanceof SimpleMappingRegion) {
+					for (@NonNull Node assignedNode : ((SimpleMappingRegion)secondaryRegion).getComputedNodes()) {
+						if (assignedNode.isClassNode()) {							// Ignore nulls, attributes
+							ClassDatumAnalysis consumingClassDatumAnalysis = assignedNode.getClassDatumAnalysis();
+							if (toOneReachableClasses.add(consumingClassDatumAnalysis)) {
+								for (@NonNull Region consumingRegion : consumingClassDatumAnalysis.getConsumingRegions()) {
+									if (allConsumingRegions.add(consumingRegion)) {
+										allConsumingRegionsList.add(consumingRegion);
+									}
+								}
+							}
+						}
+					}
+				}
+			}
+		}
+		assert allConsumingRegionsList.size() == allConsumingRegions.size();					// Check same changes to CME-proof shadow
+		return secondaryRegions;
+	}
+}
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/splitter/Split.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/splitter/Split.java
index 6c97d0772..0e30b83d2 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/splitter/Split.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/splitter/Split.java
@@ -20,7 +20,6 @@ import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.jdt.annotation.Nullable;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.AbstractRegion;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Edge;
-import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MultiRegion;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Node;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.QVTp2QVTs;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Region;
@@ -113,8 +112,9 @@ public class Split
 		}
 	}
 
-	public void install(@NonNull RootScheduledRegion rootRegion) {
-		MultiRegion multiRegion = rootRegion.getMultiRegion();
+	public @NonNull Iterable<@NonNull Region> install(@NonNull RootScheduledRegion rootRegion) {
+		List<@NonNull Region> splitRegions = new ArrayList<>();
+		//
 		Map<@NonNull Node, @NonNull Node> oldSourceNode2newSourceNode = new HashMap<>();
 		Region oldRegion = splitter.getRegion();
 		//		Iterable<@NonNull Node> newHeadNodes = stages.get(0).getHeadNodes();
@@ -125,7 +125,7 @@ public class Split
 		//			}
 		//		}
 		int stageNumber = 0;
-		Iterator<@NonNull Stage> stageIterator = stages.iterator();;
+		Iterator<@NonNull Stage> stageIterator = stages.iterator();
 		//
 		//	HeadStage
 		//
@@ -133,8 +133,7 @@ public class Split
 		assert nextStage instanceof HeadStage;
 		SplitterVisitor visitor = new HeadSplitterVisitor(rootRegion, nextStage, ++stageNumber, oldSourceNode2newSourceNode);
 		AbstractRegion stageRegion = visitor.createRegion(oldRegion);
-		//		multiRegion.addActiveRegion(stageRegion);
-		rootRegion.addRegion(stageRegion);
+		splitRegions.add(stageRegion);
 
 		nextStage = stageIterator.hasNext() ? stageIterator.next() : null;
 		//
@@ -154,8 +153,7 @@ public class Split
 		while (nextStage instanceof HeadedStage) {
 			visitor = new LoopSplitterVisitor(rootRegion, nextStage, ++stageNumber, oldSourceNode2newSourceNode);
 			stageRegion = visitor.createRegion(oldRegion);
-			//			multiRegion.addActiveRegion(stageRegion);
-			rootRegion.addRegion(stageRegion);
+			splitRegions.add(stageRegion);
 			nextStage = stageIterator.hasNext() ? stageIterator.next() : null;
 			//
 			//	non-hazardous LoopStages fold into HeadStage
@@ -175,14 +173,14 @@ public class Split
 		assert nextStage instanceof BodyStage;
 		visitor = new BodySplitterVisitor(rootRegion, nextStage, ++stageNumber, oldSourceNode2newSourceNode);
 		stageRegion = visitor.createRegion(oldRegion);
-		//		multiRegion.addActiveRegion(stageRegion);
-		rootRegion.addRegion(stageRegion);
+		splitRegions.add(stageRegion);
 		if (QVTp2QVTs.DEBUG_GRAPHS.isActive()) {
 			stageRegion.writeDebugGraphs("4-stage");
 		}
 		assert !stageIterator.hasNext();
 		//		multiRegion.removeActiveRegion(oldRegion);
-		rootRegion.removeRegion(stageRegion);
+		//
+		return splitRegions;
 	}
 
 	@Override
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/splitter/SplitterVisitor.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/splitter/SplitterVisitor.java
index 5480b3888..99e11800a 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/splitter/SplitterVisitor.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/splitter/SplitterVisitor.java
@@ -26,7 +26,6 @@ import org.eclipse.qvtd.compiler.internal.qvtp2qvts.BasicSimpleEdge;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.ClassDatumAnalysis;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Edge;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.EdgeRole;
-import org.eclipse.qvtd.compiler.internal.qvtp2qvts.MultiRegion;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Node;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.NodeConnection;
 import org.eclipse.qvtd.compiler.internal.qvtp2qvts.NodeRole;
@@ -45,7 +44,7 @@ import org.eclipse.qvtd.compiler.internal.utilities.SymbolNameBuilder;
 public class SplitterVisitor extends AbstractVisitor<@Nullable Visitable>
 {
 	protected final @NonNull RootScheduledRegion rootRegion;
-	protected final @NonNull MultiRegion multiRegion;
+	//	protected final @NonNull MultiRegion multiRegion;
 	protected final @NonNull Stage stage;
 	protected final int stageNumber;
 	protected final @NonNull Map<@NonNull Node, @NonNull Node> oldSourceNode2newSourceNode;
@@ -53,7 +52,7 @@ public class SplitterVisitor extends AbstractVisitor<@Nullable Visitable>
 
 	public SplitterVisitor(@NonNull RootScheduledRegion rootRegion, @NonNull Stage stage, int stageNumber, @NonNull Map<@NonNull Node, @NonNull Node> oldSourceNode2newSourceNode) {
 		this.rootRegion = rootRegion;
-		this.multiRegion = rootRegion.getMultiRegion();
+		//		this.multiRegion = rootRegion.getMultiRegion();
 		this.stage = stage;
 		this.stageNumber = stageNumber;
 		this.oldSourceNode2newSourceNode = oldSourceNode2newSourceNode;
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/utilities/CompilerUtil.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/utilities/CompilerUtil.java
index 88bdd9a7c..d21075d51 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/utilities/CompilerUtil.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/utilities/CompilerUtil.java
@@ -66,6 +66,12 @@ public class CompilerUtil
 
 	}
 
+	public static <T> void addAll(@NonNull Collection<T> addTo, @NonNull Iterable<T> elementsToAdd) {
+		for (T element : elementsToAdd) {
+			addTo.add(element);
+		}
+	}
+
 	public static void assertNoDiagnosticErrors(String message, XtextResource xtextResource) {
 		List<Diagnostic> diagnostics = xtextResource.validateConcreteSyntax();
 		if (diagnostics.size() > 0) {