[512089] Introduce RegionHelper to modelize MappingRegion

6 files changed, 450 insertions, 405 deletions

diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtm2qvts/MappingAnalysis.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtm2qvts/MappingAnalysis.java
index 84e45a721..727a97648 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtm2qvts/MappingAnalysis.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtm2qvts/MappingAnalysis.java
@@ -544,8 +544,9 @@ public class MappingAnalysis implements Nameable
 		analyzeComplexPredicates();
 		analyzeContainments();
 		//
-		Iterable<@NonNull Node> headNodes = RegionUtil.getHeadNodes(mappingRegion);
-		mappingRegion.computeUtilities(headNodes);
+		RegionHelper regionHelper = new RegionHelper(mappingRegion);
+		List<@NonNull Node> headNodes = regionHelper.initHeadNodes();
+		regionHelper.computeUtilities(headNodes);
 	}
 
 	/**
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtm2qvts/RegionHelper.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtm2qvts/RegionHelper.java
new file mode 100644
index 000000000..ba4d4b17e
--- /dev/null
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtm2qvts/RegionHelper.java
@@ -0,0 +1,433 @@
+/*******************************************************************************
+ * Copyright (c) 2015, 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.qvtm2qvts;
+
+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.utilities.NameUtil;
+import org.eclipse.qvtd.pivot.qvtschedule.Edge;
+import org.eclipse.qvtd.pivot.qvtschedule.MappingRegion;
+import org.eclipse.qvtd.pivot.qvtschedule.NavigableEdge;
+import org.eclipse.qvtd.pivot.qvtschedule.Node;
+import org.eclipse.qvtd.pivot.qvtschedule.impl.MappingRegionImpl;
+import org.eclipse.qvtd.pivot.qvtschedule.utilities.QVTscheduleConstants;
+import org.eclipse.qvtd.pivot.qvtschedule.utilities.QVTscheduleUtil;
+
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+
+public class RegionHelper
+{
+	public static void initHeadNodes(@NonNull MappingRegion mappingRegion) {
+		RegionHelper regionHelper = new RegionHelper(mappingRegion);
+		regionHelper.initHeadNodes();
+	}
+
+	protected final @NonNull MappingRegion mappingRegion;
+
+	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> stronglyMatchedNodes = null;
+	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> unconditionalNodes = null;
+	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> conditionalNodes = null;
+	//	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> dependencyNodes = null;
+	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> deadNodes = null;
+
+	public RegionHelper(@NonNull MappingRegion mappingRegion) {
+		this.mappingRegion = mappingRegion;
+	}
+
+	private boolean canBeStronglyMatched(@NonNull Node node) {
+		if (node.isExplicitNull()) {
+			return true;
+		}
+		if (node.isPattern()) {
+			return true;
+		}
+		return false;
+	}
+
+	private boolean canBeUnconditional(@NonNull Node node) {
+		if (node.isExplicitNull()) {
+			return true;
+		}
+		if (node.isIterator()) {
+			return false;
+		}
+		if (node.isOperation()) {
+			return true;
+		}
+		if (node.isPattern()) {
+			return true;
+		}
+		return false;
+	}
+
+	/**
+	 * Any node with an edge to an unconditional node that is not itself unconditional must be conditional.
+	 */
+	private @NonNull Set<@NonNull Node> computeConditionalNodes(@NonNull Set<@NonNull Node> unconditionalNodes) {
+		Set<@NonNull Node> conditionalNodes = new HashSet<>();
+		Set<@NonNull Node> moreNodes = unconditionalNodes;
+		while (moreNodes.size() > 0) {
+			Set<@NonNull Node> moreMoreNodes = new HashSet<>();
+			for (@NonNull Node node : moreNodes) {
+				for (@NonNull Edge incomingEdge : QVTscheduleUtil.getIncomingEdges(node)) {
+					Node sourceNode = incomingEdge.getEdgeSource();
+					if (!unconditionalNodes.contains(sourceNode) && conditionalNodes.add(sourceNode)) {
+						moreMoreNodes.add(sourceNode);
+					}
+				}
+				for (@NonNull Edge outgoingEdge : QVTscheduleUtil.getOutgoingEdges(node)) {
+					Node targetNode = outgoingEdge.getEdgeTarget();
+					if (!unconditionalNodes.contains(targetNode) && conditionalNodes.add(targetNode)) {
+						moreMoreNodes.add(targetNode);
+					}
+				}
+			}
+			if (moreMoreNodes.size() <= 0) {
+				break;
+			}
+			moreNodes = moreMoreNodes;
+		}
+		this.conditionalNodes = new ArrayList<>(conditionalNodes);
+		Collections.sort(this.conditionalNodes, NameUtil.NAMEABLE_COMPARATOR);
+		return conditionalNodes;
+	}
+
+	/**
+	 * Any dependency node transitively connected to a deopendency head contributes to the dependency nodes.
+	 *
+	private @NonNull Set<@NonNull Node> computeDependencyNodes(@NonNull Iterable <@NonNull Node> headNodes) {
+		Set<@NonNull Node> dependencyNodes = new HashSet<>();
+		Iterable<@NonNull Node> moreNodes = headNodes;
+		while (!Iterables.isEmpty(moreNodes)) {
+			Set<@NonNull Node> moreMoreNodes = new HashSet<>();
+			for (@NonNull Node node : moreNodes) {
+				if (node.isDependency() && dependencyNodes.add(node)) {
+					for (@NonNull NavigableEdge edge : node.getNavigationEdges()) {
+						Node targetNode = edge.getTarget();
+						moreMoreNodes.add(targetNode);
+					}
+				}
+			}
+			if (moreMoreNodes.size() <= 0) {
+				break;
+			}
+			moreNodes = moreMoreNodes;
+		}
+		this.dependencyNodes = new ArrayList<>(dependencyNodes);
+		Collections.sort(this.dependencyNodes, NameUtil.NAMEABLE_COMPARATOR);
+		return dependencyNodes;
+	} */
+
+	protected @NonNull List<@NonNull Node> computeHeadNodes(@NonNull MappingRegion mappingRegion) {
+		//
+		//	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 hazards from the source-to-target / target-source asymmetry.
+		//
+		List<@NonNull Node> navigableNodes = new ArrayList<>();
+		for (@NonNull Node node : QVTscheduleUtil.getOwnedNodes(mappingRegion)) {
+			if (node.isPattern() && node.isMatched() && node.isClass() && !node.isExplicitNull() && !node.isOperation()) {	// Excludes, null, attributes, constants, operations
+				if (node.isLoaded() || node.isPredicated() || node.isSpeculated()) {
+					navigableNodes.add(node);
+				}
+			}
+		}
+		//
+		//	Compute the Set of all source nodes from which each target can be reached by transitive to-one navigation.
+		//
+		Map<@NonNull Node, @NonNull Set<@NonNull Node>> targetFromSourceClosure = new HashMap<>();
+		for (@NonNull Node targetNode : navigableNodes) {
+			targetFromSourceClosure.put(targetNode, Sets.newHashSet(targetNode));
+		}
+		for (@NonNull Node sourceNode : navigableNodes) {
+			//			assert !navigableNode.isDataType();									// FIXME avoid even considering these nodes
+			//			assert !navigableNode.isSpeculation();								// FIXME avoid even considering these nodes
+			//			assert !navigableNode.isRealized();									// FIXME avoid even considering these nodes
+			//			Type type = navigableNode.getCompleteClass().getPrimaryClass();
+			//			assert !(type instanceof CollectionType);
+			//				System.err.println("No head created for CollectionType " + type + " in " + this);
+			//				continue;
+			//			}
+			//			Set<@NonNull Node> sourceClosure = new HashSet<>();
+			//			targetFromSourceClosure.put(navigableNode, targetClosure);
+			//			targetClosure.add(navigableNode);
+			for (@NonNull Edge navigationEdge : sourceNode.getNavigationEdges()) {
+				if (!navigationEdge.isRealized()) {
+					Node targetNode = navigationEdge.getEdgeTarget();
+					if (targetNode.isMatched() && targetNode.isClass() && !targetNode.isExplicitNull()) {
+						Set<@NonNull Node> sourceClosure = targetFromSourceClosure.get(targetNode);
+						if (sourceClosure != null) {
+							sourceClosure.add(sourceNode);
+						}
+					}
+				}
+			}
+			//			for (@NonNull Edge computationEdge : navigableNode.getComputationEdges()) {
+			//				targetClosure.add(computationEdge.getSource());
+			//			}
+		}
+		//
+		//	Ripple the local target-from-source closure to compute the overall target-from-source closure.
+		//
+		boolean isChanged = true;
+		while (isChanged) {
+			isChanged = false;
+			for (@NonNull Node targetNode : navigableNodes) {
+				Set<@NonNull Node> sourceClosure = targetFromSourceClosure.get(targetNode);
+				assert sourceClosure != null;
+				for (@NonNull Node sourceNode : new ArrayList<>(sourceClosure)) {
+					Set<@NonNull Node> sourceSourceClosure = targetFromSourceClosure.get(sourceNode);
+					assert sourceSourceClosure != null;
+					if (sourceClosure.addAll(sourceSourceClosure)) {
+						isChanged = true;
+					}
+				}
+			}
+		}
+		//
+		//	Compute the inverse Set of all source nodes from which a particular target node can be reached by transitive to-one navigation.
+		//
+		final Map<@NonNull Node, @NonNull Set<@NonNull Node>> source2targetClosure = new HashMap<>();
+		for (@NonNull Node sourceNode : navigableNodes) {
+			source2targetClosure.put(sourceNode, Sets.newHashSet(sourceNode));
+		}
+		for (@NonNull Node targetNode : targetFromSourceClosure.keySet()) {
+			Set<@NonNull Node> sourceClosure = targetFromSourceClosure.get(targetNode);
+			assert sourceClosure != null;
+			for (@NonNull Node sourceNode : sourceClosure) {
+				Set<@NonNull Node> targetClosure = source2targetClosure.get(sourceNode);
+				assert targetClosure != null;
+				targetClosure.add(targetNode);
+			}
+		}
+		//
+		//	Sort the guardNodes into least reachable first order enabling the heads to be identified
+		//	by successive removal from the start of the list.
+		//
+		List<@NonNull Node> headLessNodes = new ArrayList<>();
+		Iterables.addAll(headLessNodes, targetFromSourceClosure.keySet());
+		Collections.sort(headLessNodes, new QVTscheduleUtil.HeadComparator(targetFromSourceClosure));
+		//
+		//	Loop to keep removing distinct inputs until all guard nodes are reachable from some head.
+		//
+		List<@NonNull Node> headNodes = new ArrayList<>();
+		while (!headLessNodes.isEmpty()) {
+			Node headNode = headLessNodes.remove(0);
+			assert headNode != null;
+			@SuppressWarnings("unused") Set<@NonNull Node> debugSourceClosure = targetFromSourceClosure.get(headNode);
+			Set<@NonNull Node> targetClosure = source2targetClosure.get(headNode);
+			assert targetClosure != null;
+			for (@NonNull Node node : targetClosure) {
+				if (node != headNode) {
+					node.resetHead();
+				}
+				else {
+					headNode.setHead();
+				}
+				headLessNodes.remove(node);
+			}
+			targetClosure.remove(headNode);
+			assert !headNodes.contains(headNode);
+			headNodes.add(headNode);
+		}
+		//
+		//	Check head node consistency
+		//
+		Set<@NonNull Node> debugHeadNodes = new HashSet<>();
+		for (@NonNull Node node : QVTscheduleUtil.getOwnedNodes(mappingRegion)) {
+			if (node.isTrue() || node.isDependency()) {
+				debugHeadNodes.add(node);
+				node.setHead();
+				assert !headNodes.contains(node);
+				headNodes.add(node);
+			}
+			else if (node.isHead()) {
+				debugHeadNodes.add(node);
+			}
+		}
+		assert debugHeadNodes.equals(new HashSet<>(headNodes));
+		//
+		return headNodes;
+	}
+
+	private @NonNull Set<@NonNull Node> computeStronglyMatchedNodes(@NonNull Iterable<@NonNull Node> headNodes) {
+		Set<@NonNull Node> stronglyMatchedNodes = new HashSet<>();
+		for (@NonNull Node headNode : headNodes) {
+			if (!headNode.isDependency() && !headNode.isTrue()) {
+				stronglyMatchedNodes.add(headNode);
+			}
+		}
+		Set<@NonNull Node> moreStronglyMatchedNodes = new HashSet<>(stronglyMatchedNodes);
+		while (moreStronglyMatchedNodes.size() > 0) {
+			Set<@NonNull Node> moreMoreNodes = new HashSet<>();
+			for (@NonNull Node sourceNode : moreStronglyMatchedNodes) {
+				for (@NonNull NavigableEdge edge : sourceNode.getNavigationEdges()) {
+					Node targetNode = edge.getEdgeTarget();
+					if (canBeStronglyMatched(targetNode)) {
+						if (targetNode.isExplicitNull() || edge.getProperty().isIsRequired()) {
+							if (stronglyMatchedNodes.add(targetNode)) {
+								moreMoreNodes.add(targetNode);
+							}
+						}
+					}
+				}
+			}
+			if (moreMoreNodes.size() <= 0) {
+				break;
+			}
+			moreStronglyMatchedNodes = moreMoreNodes;
+		}
+		this.stronglyMatchedNodes = new ArrayList<>(stronglyMatchedNodes);
+		Collections.sort(this.stronglyMatchedNodes, NameUtil.NAMEABLE_COMPARATOR);
+		return stronglyMatchedNodes;
+	}
+
+	private @NonNull Set<@NonNull Node> computeUnconditionalNodes(@NonNull Iterable<@NonNull Node> headNodes) {
+		@NonNull Set<@NonNull Node> unconditionalNodes = Sets.newHashSet(headNodes);
+		Iterables.addAll(unconditionalNodes, mappingRegion.getNewNodes());
+		for (@NonNull NavigableEdge edge : mappingRegion.getRealizedNavigationEdges()) {
+			if (!edge.isSecondary()) {
+				Node sourceNode = edge.getEdgeSource();
+				assert canBeUnconditional(sourceNode);
+				unconditionalNodes.add(sourceNode);
+				Node targetNode = edge.getEdgeTarget();
+				assert canBeUnconditional(targetNode);
+				unconditionalNodes.add(targetNode);
+			}
+		}
+		Set<@NonNull Node> moreUnconditionalNodes = new HashSet<>(unconditionalNodes);
+		while (moreUnconditionalNodes.size() > 0) {
+			Set<@NonNull Node> moreMoreNodes = new HashSet<>();
+			for (@NonNull Node node : moreUnconditionalNodes) {
+				for (@NonNull Edge incomingEdge : QVTscheduleUtil.getIncomingEdges(node)) {
+					Node sourceNode = incomingEdge.getEdgeSource();
+					if (!canBeUnconditional(sourceNode)) {}
+					else if (incomingEdge.isComputation()) {
+						if (!isConditionalEdge(incomingEdge)) {
+							if (unconditionalNodes.add(sourceNode)) {
+								moreMoreNodes.add(sourceNode);
+							}
+						}
+						// if is <<then>>
+						// gather <<then>> visibilities
+						// gather <<else>> visibilities
+						// intersection <<then>>/<<else>> is unconditional
+					}
+					else if (incomingEdge.isNavigation()) {		// Unconditional target has unconditional source
+						if (unconditionalNodes.add(sourceNode)) {
+							moreMoreNodes.add(sourceNode);
+						}
+					}
+					else {
+						System.out.println("Unsupported incoming edge in " + this + " : " + incomingEdge);
+					}
+				}
+				for (@NonNull Edge outgoingEdge : QVTscheduleUtil.getOutgoingEdges(node)) {
+					Node targetNode = outgoingEdge.getEdgeTarget();
+					if (!canBeUnconditional(targetNode)) {}
+					else if (outgoingEdge.isComputation()) {}
+					else if (outgoingEdge.isNavigation()) {
+						if (targetNode.isExplicitNull()) {
+							if (unconditionalNodes.add(targetNode)) {
+								moreMoreNodes.add(targetNode);
+							}
+						}
+						else if (node.isRequired() && ((NavigableEdge)outgoingEdge).getProperty().isIsRequired()) {
+							if (unconditionalNodes.add(targetNode)) {
+								moreMoreNodes.add(targetNode);
+							}
+						}
+					}
+					else {
+						System.out.println("Unsupported outgoing edge in " + this + " : " + outgoingEdge);
+					}
+				}
+			}
+			if (moreMoreNodes.size() <= 0) {
+				break;
+			}
+			moreUnconditionalNodes = moreMoreNodes;
+		}
+		this.unconditionalNodes = new ArrayList<>(unconditionalNodes);
+		Collections.sort(this.unconditionalNodes, NameUtil.NAMEABLE_COMPARATOR);
+		return unconditionalNodes;
+	}
+
+	protected void computeUtilities(@NonNull Iterable<@NonNull Node> headNodes) {		// FIXME remove assertions after 1-Jan-2017
+		Set<@NonNull Node> stronglyMatchedNodes = computeStronglyMatchedNodes(headNodes);
+		Set<@NonNull Node> unconditionalNodes = computeUnconditionalNodes(headNodes);
+		Set<@NonNull Node> conditionalNodes = computeConditionalNodes(unconditionalNodes);
+		//		Set<@NonNull Node> dependencyNodes = computeDependencyNodes(headNodes);
+		Set<@NonNull Node> deadNodes = null;
+		//
+		for (@NonNull Node node : QVTscheduleUtil.getOwnedNodes(mappingRegion)) {
+			if (stronglyMatchedNodes.contains(node)) {
+				node.setUtility(Node.Utility.STRONGLY_MATCHED);
+				assert unconditionalNodes.contains(node);
+				//				assert !dependencyNodes.contains(node);
+			}
+			else if (unconditionalNodes.contains(node) && !node.isDependency()) {
+				node.setUtility(Node.Utility.WEAKLY_MATCHED);
+				//				assert !dependencyNodes.contains(node);
+			}
+			else if (conditionalNodes.contains(node)) {
+				node.setUtility(Node.Utility.CONDITIONAL);
+				//				assert !dependencyNodes.contains(node);
+			}
+			else if (node.isDependency()) {
+				node.setUtility(Node.Utility.DEPENDENCY);
+			}
+			else {
+				System.err.println("Dead node in " + this + " : " + node);
+				if (deadNodes == null) {
+					deadNodes = new HashSet<>();
+				}
+				deadNodes.add(node);
+				node.setUtility(Node.Utility.DEAD);
+				toString();
+			}
+		}
+		if (deadNodes != null) {
+			this.deadNodes = new ArrayList<>(deadNodes);
+			Collections.sort(this.deadNodes, NameUtil.NAMEABLE_COMPARATOR);
+		}
+		/*		for (@NonNull Node node : getNodes()) {
+			boolean isMatched = node.isMatched();
+			boolean isUnconditional = node.isUnconditional();
+			boolean isRequired = node.isRequired();
+			boolean isPattern = node.isPattern();
+			if (isMatched != (isUnconditional && isPattern)) {
+				System.out.println("Inconsistently isMatched in " + this + " : " + node);
+			}
+		} */
+	}
+
+	public @NonNull List<@NonNull Node> initHeadNodes() {
+		List<@NonNull Node> headNodes = computeHeadNodes(mappingRegion);
+		((MappingRegionImpl)mappingRegion).getHeadNodes2().addAll(headNodes);
+		return headNodes;
+	}
+
+	private boolean isConditionalEdge(@NonNull Edge edge) {
+		String edgeName = edge.getName();
+		return QVTscheduleConstants.IF_THEN_NAME.equals(edgeName)
+				|| QVTscheduleConstants.IF_ELSE_NAME.equals(edgeName)
+				|| QVTscheduleConstants.LOOP_BODY_NAME.equals(edgeName);
+	}
+}
\ 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
index 10e46fff3..a50e4fde3 100644
--- 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
@@ -20,12 +20,12 @@ import java.util.Set;
 
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.ocl.pivot.utilities.ClassUtil;
+import org.eclipse.qvtd.compiler.internal.qvtm2qvts.RegionHelper;
 import org.eclipse.qvtd.compiler.internal.qvtm2qvts.RegionUtil;
 import org.eclipse.qvtd.pivot.qvtschedule.Edge;
 import org.eclipse.qvtd.pivot.qvtschedule.MappingRegion;
 import org.eclipse.qvtd.pivot.qvtschedule.Node;
 import org.eclipse.qvtd.pivot.qvtschedule.Region;
-
 import com.google.common.collect.Iterables;
 
 /**
@@ -176,6 +176,7 @@ abstract class RegionMerger // implements Region
 		MappingRegion newRegion = createNewRegion(newName);
 		createNewNodes(newRegion);
 		createNewEdges();
+		RegionHelper.initHeadNodes(newRegion);
 		return newRegion;
 	}
 
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/partitioner/AbstractPartition.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/partitioner/AbstractPartition.java
index 2ae9b7595..fede86b38 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/partitioner/AbstractPartition.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/partitioner/AbstractPartition.java
@@ -19,6 +19,7 @@ import java.util.Set;
 
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.qvtd.compiler.internal.qvtm2qvts.RegionHelper;
 import org.eclipse.qvtd.compiler.internal.qvtm2qvts.RegionUtil;
 import org.eclipse.qvtd.compiler.internal.qvts2qvti.AbstractForestBuilder;
 import org.eclipse.qvtd.compiler.internal.utilities.CompilerUtil;
@@ -27,7 +28,6 @@ import org.eclipse.qvtd.pivot.qvtschedule.MicroMappingRegion;
 import org.eclipse.qvtd.pivot.qvtschedule.NavigableEdge;
 import org.eclipse.qvtd.pivot.qvtschedule.Node;
 import org.eclipse.qvtd.pivot.qvtschedule.Role;
-
 import com.google.common.collect.Lists;
 import com.google.common.collect.Sets;
 
@@ -154,7 +154,7 @@ abstract class AbstractPartition
 	public @NonNull MicroMappingRegion createMicroMappingRegion(@NonNull String namePrefix, @NonNull String symbolSuffix) {
 		PartitioningVisitor partitioningVisitor = PartitioningVisitor.createPartialRegion(partitioner.getRegion(), namePrefix, symbolSuffix, this);
 		MicroMappingRegion microMappingRegion = partitioningVisitor.getRegion();
-		microMappingRegion.getHeadNodes();
+		RegionHelper.initHeadNodes(microMappingRegion);
 		check(microMappingRegion);
 		return microMappingRegion;
 	}
diff --git a/plugins/org.eclipse.qvtd.pivot.qvtschedule/emf-gen/org/eclipse/qvtd/pivot/qvtschedule/impl/BasicMappingRegionImpl.java b/plugins/org.eclipse.qvtd.pivot.qvtschedule/emf-gen/org/eclipse/qvtd/pivot/qvtschedule/impl/BasicMappingRegionImpl.java
index 6e9f529e1..92c3a517a 100644
--- a/plugins/org.eclipse.qvtd.pivot.qvtschedule/emf-gen/org/eclipse/qvtd/pivot/qvtschedule/impl/BasicMappingRegionImpl.java
+++ b/plugins/org.eclipse.qvtd.pivot.qvtschedule/emf-gen/org/eclipse/qvtd/pivot/qvtschedule/impl/BasicMappingRegionImpl.java
@@ -170,11 +170,6 @@ public class BasicMappingRegionImpl extends MappingRegionImpl implements BasicMa
 		variable2node.put(variable, node);
 	}
 
-	@Override
-	public void computeUtilities(@NonNull Iterable<@NonNull Node> headNodes) {
-		super.computeUtilities(headNodes);
-	}
-
 	/**
 	 * <!-- begin-user-doc -->
 	 * <!-- end-user-doc -->
diff --git a/plugins/org.eclipse.qvtd.pivot.qvtschedule/emf-gen/org/eclipse/qvtd/pivot/qvtschedule/impl/MappingRegionImpl.java b/plugins/org.eclipse.qvtd.pivot.qvtschedule/emf-gen/org/eclipse/qvtd/pivot/qvtschedule/impl/MappingRegionImpl.java
index e74ef3123..b23401ef0 100644
--- a/plugins/org.eclipse.qvtd.pivot.qvtschedule/emf-gen/org/eclipse/qvtd/pivot/qvtschedule/impl/MappingRegionImpl.java
+++ b/plugins/org.eclipse.qvtd.pivot.qvtschedule/emf-gen/org/eclipse/qvtd/pivot/qvtschedule/impl/MappingRegionImpl.java
@@ -15,26 +15,13 @@
 package org.eclipse.qvtd.pivot.qvtschedule.impl;
 
 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.emf.ecore.EClass;
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.jdt.annotation.Nullable;
-import org.eclipse.ocl.pivot.utilities.NameUtil;
-import org.eclipse.qvtd.pivot.qvtschedule.Edge;
 import org.eclipse.qvtd.pivot.qvtschedule.MappingRegion;
-import org.eclipse.qvtd.pivot.qvtschedule.NavigableEdge;
 import org.eclipse.qvtd.pivot.qvtschedule.Node;
 import org.eclipse.qvtd.pivot.qvtschedule.QVTschedulePackage;
-import org.eclipse.qvtd.pivot.qvtschedule.utilities.QVTscheduleConstants;
-import org.eclipse.qvtd.pivot.qvtschedule.utilities.QVTscheduleUtil;
-import com.google.common.collect.Iterables;
-import com.google.common.collect.Sets;
 
 /**
  * <!-- begin-user-doc -->
@@ -67,11 +54,6 @@ public abstract class MappingRegionImpl extends RegionImpl implements MappingReg
 	 * The subsets of guardVariables from which all guardVariables are to-one navigable.
 	 */
 	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> headNodes = null;
-	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> stronglyMatchedNodes = null;
-	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> unconditionalNodes = null;
-	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> conditionalNodes = null;
-	//	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> dependencyNodes = null;
-	private /*@LazyNonNull*/ @Nullable List<@NonNull Node> deadNodes = null;
 
 	/*	@Override
 	public void addEdge(@NonNull Edge edge) {
@@ -82,11 +64,11 @@ public abstract class MappingRegionImpl extends RegionImpl implements MappingReg
 		super.addEdge(edge);
 	} */
 
-	protected void addHeadNode(@NonNull Node headNode) {
+	/*	protected void addHeadNode(@NonNull Node headNode) {
 		assert basicGetSymbolName() == null;
 		if (headNodes != null) { assert !headNodes.contains(headNode); }
 		getHeadNodes().add(headNode);
-	}
+	} */
 
 	/*	@Override
 	public void addNode(@NonNull Node node) {
@@ -97,373 +79,6 @@ public abstract class MappingRegionImpl extends RegionImpl implements MappingReg
 		super.addNode(node);
 	} */
 
-	private boolean canBeStronglyMatched(@NonNull Node node) {
-		if (node.isExplicitNull()) {
-			return true;
-		}
-		if (node.isPattern()) {
-			return true;
-		}
-		return false;
-	}
-
-	private boolean canBeUnconditional(@NonNull Node node) {
-		if (node.isExplicitNull()) {
-			return true;
-		}
-		if (node.isIterator()) {
-			return false;
-		}
-		if (node.isOperation()) {
-			return true;
-		}
-		if (node.isPattern()) {
-			return true;
-		}
-		return false;
-	}
-
-	/**
-	 * Any node with an edge to an unconditional node that is not itself unconditional must be conditional.
-	 */
-	private @NonNull Set<@NonNull Node> computeConditionalNodes(@NonNull Set<@NonNull Node> unconditionalNodes) {
-		Set<@NonNull Node> conditionalNodes = new HashSet<>();
-		Set<@NonNull Node> moreNodes = unconditionalNodes;
-		while (moreNodes.size() > 0) {
-			Set<@NonNull Node> moreMoreNodes = new HashSet<>();
-			for (@NonNull Node node : moreNodes) {
-				for (@NonNull Edge incomingEdge : QVTscheduleUtil.getIncomingEdges(node)) {
-					Node sourceNode = incomingEdge.getEdgeSource();
-					if (!unconditionalNodes.contains(sourceNode) && conditionalNodes.add(sourceNode)) {
-						moreMoreNodes.add(sourceNode);
-					}
-				}
-				for (@NonNull Edge outgoingEdge : QVTscheduleUtil.getOutgoingEdges(node)) {
-					Node targetNode = outgoingEdge.getEdgeTarget();
-					if (!unconditionalNodes.contains(targetNode) && conditionalNodes.add(targetNode)) {
-						moreMoreNodes.add(targetNode);
-					}
-				}
-			}
-			if (moreMoreNodes.size() <= 0) {
-				break;
-			}
-			moreNodes = moreMoreNodes;
-		}
-		this.conditionalNodes = new ArrayList<>(conditionalNodes);
-		Collections.sort(this.conditionalNodes, NameUtil.NAMEABLE_COMPARATOR);
-		return conditionalNodes;
-	}
-
-	/**
-	 * Any dependency node transitively connected to a deopendency head contributes to the dependency nodes.
-	 *
-	private @NonNull Set<@NonNull Node> computeDependencyNodes(@NonNull Iterable <@NonNull Node> headNodes) {
-		Set<@NonNull Node> dependencyNodes = new HashSet<>();
-		Iterable<@NonNull Node> moreNodes = headNodes;
-		while (!Iterables.isEmpty(moreNodes)) {
-			Set<@NonNull Node> moreMoreNodes = new HashSet<>();
-			for (@NonNull Node node : moreNodes) {
-				if (node.isDependency() && dependencyNodes.add(node)) {
-					for (@NonNull NavigableEdge edge : node.getNavigationEdges()) {
-						Node targetNode = edge.getTarget();
-						moreMoreNodes.add(targetNode);
-					}
-				}
-			}
-			if (moreMoreNodes.size() <= 0) {
-				break;
-			}
-			moreNodes = moreMoreNodes;
-		}
-		this.dependencyNodes = new ArrayList<>(dependencyNodes);
-		Collections.sort(this.dependencyNodes, NameUtil.NAMEABLE_COMPARATOR);
-		return dependencyNodes;
-	} */
-
-	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 hazards from the source-to-target / target-source asymmetry.
-		//
-		List<@NonNull Node> navigableNodes = new ArrayList<>();
-		for (@NonNull Node node : QVTscheduleUtil.getOwnedNodes(this)) {
-			if (node.isPattern() && node.isMatched() && node.isClass() && !node.isExplicitNull() && !node.isOperation()) {	// Excludes, null, attributes, constants, operations
-				if (node.isLoaded() || node.isPredicated() || node.isSpeculated()) {
-					navigableNodes.add(node);
-				}
-			}
-		}
-		//
-		//	Compute the Set of all source nodes from which each target can be reached by transitive to-one navigation.
-		//
-		Map<@NonNull Node, @NonNull Set<@NonNull Node>> targetFromSourceClosure = new HashMap<>();
-		for (@NonNull Node targetNode : navigableNodes) {
-			targetFromSourceClosure.put(targetNode, Sets.newHashSet(targetNode));
-		}
-		for (@NonNull Node sourceNode : navigableNodes) {
-			//			assert !navigableNode.isDataType();									// FIXME avoid even considering these nodes
-			//			assert !navigableNode.isSpeculation();								// FIXME avoid even considering these nodes
-			//			assert !navigableNode.isRealized();									// FIXME avoid even considering these nodes
-			//			Type type = navigableNode.getCompleteClass().getPrimaryClass();
-			//			assert !(type instanceof CollectionType);
-			//				System.err.println("No head created for CollectionType " + type + " in " + this);
-			//				continue;
-			//			}
-			//			Set<@NonNull Node> sourceClosure = new HashSet<>();
-			//			targetFromSourceClosure.put(navigableNode, targetClosure);
-			//			targetClosure.add(navigableNode);
-			for (@NonNull Edge navigationEdge : sourceNode.getNavigationEdges()) {
-				if (!navigationEdge.isRealized()) {
-					Node targetNode = navigationEdge.getEdgeTarget();
-					if (targetNode.isMatched() && targetNode.isClass() && !targetNode.isExplicitNull()) {
-						Set<@NonNull Node> sourceClosure = targetFromSourceClosure.get(targetNode);
-						if (sourceClosure != null) {
-							sourceClosure.add(sourceNode);
-						}
-					}
-				}
-			}
-			//			for (@NonNull Edge computationEdge : navigableNode.getComputationEdges()) {
-			//				targetClosure.add(computationEdge.getSource());
-			//			}
-		}
-		//
-		//	Ripple the local target-from-source closure to compute the overall target-from-source closure.
-		//
-		boolean isChanged = true;
-		while (isChanged) {
-			isChanged = false;
-			for (@NonNull Node targetNode : navigableNodes) {
-				Set<@NonNull Node> sourceClosure = targetFromSourceClosure.get(targetNode);
-				assert sourceClosure != null;
-				for (@NonNull Node sourceNode : new ArrayList<>(sourceClosure)) {
-					Set<@NonNull Node> sourceSourceClosure = targetFromSourceClosure.get(sourceNode);
-					assert sourceSourceClosure != null;
-					if (sourceClosure.addAll(sourceSourceClosure)) {
-						isChanged = true;
-					}
-				}
-			}
-		}
-		//
-		//	Compute the inverse Set of all source nodes from which a particular target node can be reached by transitive to-one navigation.
-		//
-		final Map<@NonNull Node, @NonNull Set<@NonNull Node>> source2targetClosure = new HashMap<>();
-		for (@NonNull Node sourceNode : navigableNodes) {
-			source2targetClosure.put(sourceNode, Sets.newHashSet(sourceNode));
-		}
-		for (@NonNull Node targetNode : targetFromSourceClosure.keySet()) {
-			Set<@NonNull Node> sourceClosure = targetFromSourceClosure.get(targetNode);
-			assert sourceClosure != null;
-			for (@NonNull Node sourceNode : sourceClosure) {
-				Set<@NonNull Node> targetClosure = source2targetClosure.get(sourceNode);
-				assert targetClosure != null;
-				targetClosure.add(targetNode);
-			}
-		}
-		//
-		//	Sort the guardNodes into least reachable first order enabling the heads to be identified
-		//	by successive removal from the start of the list.
-		//
-		List<@NonNull Node> headLessNodes = new ArrayList<>();
-		Iterables.addAll(headLessNodes, targetFromSourceClosure.keySet());
-		Collections.sort(headLessNodes, new QVTscheduleUtil.HeadComparator(targetFromSourceClosure));
-		//
-		//	Loop to keep removing distinct inputs until all guard nodes are reachable from some head.
-		//
-		List<@NonNull Node> headNodes = new ArrayList<>();
-		while (!headLessNodes.isEmpty()) {
-			Node headNode = headLessNodes.remove(0);
-			assert headNode != null;
-			@SuppressWarnings("unused") Set<@NonNull Node> debugSourceClosure = targetFromSourceClosure.get(headNode);
-			Set<@NonNull Node> targetClosure = source2targetClosure.get(headNode);
-			assert targetClosure != null;
-			for (@NonNull Node node : targetClosure) {
-				if (node != headNode) {
-					node.resetHead();
-				}
-				else {
-					headNode.setHead();
-				}
-				headLessNodes.remove(node);
-			}
-			targetClosure.remove(headNode);
-			assert !headNodes.contains(headNode);
-			headNodes.add(headNode);
-		}
-		//
-		//	Check head node consistency
-		//
-		Set<@NonNull Node> debugHeadNodes = new HashSet<>();
-		for (@NonNull Node node : QVTscheduleUtil.getOwnedNodes(this)) {
-			if (node.isTrue() || node.isDependency()) {
-				debugHeadNodes.add(node);
-				node.setHead();
-				assert !headNodes.contains(node);
-				headNodes.add(node);
-			}
-			else if (node.isHead()) {
-				debugHeadNodes.add(node);
-			}
-		}
-		assert debugHeadNodes.equals(new HashSet<>(headNodes));
-		//
-		return headNodes;
-	}
-
-	private @NonNull Set<@NonNull Node> computeStronglyMatchedNodes(@NonNull Iterable<@NonNull Node> headNodes) {
-		Set<@NonNull Node> stronglyMatchedNodes = new HashSet<>();
-		for (@NonNull Node headNode : headNodes) {
-			if (!headNode.isDependency() && !headNode.isTrue()) {
-				stronglyMatchedNodes.add(headNode);
-			}
-		}
-		Set<@NonNull Node> moreStronglyMatchedNodes = new HashSet<>(stronglyMatchedNodes);
-		while (moreStronglyMatchedNodes.size() > 0) {
-			Set<@NonNull Node> moreMoreNodes = new HashSet<>();
-			for (@NonNull Node sourceNode : moreStronglyMatchedNodes) {
-				for (@NonNull NavigableEdge edge : sourceNode.getNavigationEdges()) {
-					Node targetNode = edge.getEdgeTarget();
-					if (canBeStronglyMatched(targetNode)) {
-						if (targetNode.isExplicitNull() || edge.getProperty().isIsRequired()) {
-							if (stronglyMatchedNodes.add(targetNode)) {
-								moreMoreNodes.add(targetNode);
-							}
-						}
-					}
-				}
-			}
-			if (moreMoreNodes.size() <= 0) {
-				break;
-			}
-			moreStronglyMatchedNodes = moreMoreNodes;
-		}
-		this.stronglyMatchedNodes = new ArrayList<>(stronglyMatchedNodes);
-		Collections.sort(this.stronglyMatchedNodes, NameUtil.NAMEABLE_COMPARATOR);
-		return stronglyMatchedNodes;
-	}
-
-	private @NonNull Set<@NonNull Node> computeUnconditionalNodes(@NonNull Iterable<@NonNull Node> headNodes) {
-		@NonNull Set<@NonNull Node> unconditionalNodes = Sets.newHashSet(headNodes);
-		Iterables.addAll(unconditionalNodes, getNewNodes());
-		for (@NonNull NavigableEdge edge : getRealizedNavigationEdges()) {
-			if (!edge.isSecondary()) {
-				Node sourceNode = edge.getEdgeSource();
-				assert canBeUnconditional(sourceNode);
-				unconditionalNodes.add(sourceNode);
-				Node targetNode = edge.getEdgeTarget();
-				assert canBeUnconditional(targetNode);
-				unconditionalNodes.add(targetNode);
-			}
-		}
-		Set<@NonNull Node> moreUnconditionalNodes = new HashSet<>(unconditionalNodes);
-		while (moreUnconditionalNodes.size() > 0) {
-			Set<@NonNull Node> moreMoreNodes = new HashSet<>();
-			for (@NonNull Node node : moreUnconditionalNodes) {
-				for (@NonNull Edge incomingEdge : QVTscheduleUtil.getIncomingEdges(node)) {
-					Node sourceNode = incomingEdge.getEdgeSource();
-					if (!canBeUnconditional(sourceNode)) {}
-					else if (incomingEdge.isComputation()) {
-						if (!isConditionalEdge(incomingEdge)) {
-							if (unconditionalNodes.add(sourceNode)) {
-								moreMoreNodes.add(sourceNode);
-							}
-						}
-						// if is <<then>>
-						// gather <<then>> visibilities
-						// gather <<else>> visibilities
-						// intersection <<then>>/<<else>> is unconditional
-					}
-					else if (incomingEdge.isNavigation()) {		// Unconditional target has unconditional source
-						if (unconditionalNodes.add(sourceNode)) {
-							moreMoreNodes.add(sourceNode);
-						}
-					}
-					else {
-						System.out.println("Unsupported incoming edge in " + this + " : " + incomingEdge);
-					}
-				}
-				for (@NonNull Edge outgoingEdge : QVTscheduleUtil.getOutgoingEdges(node)) {
-					Node targetNode = outgoingEdge.getEdgeTarget();
-					if (!canBeUnconditional(targetNode)) {}
-					else if (outgoingEdge.isComputation()) {}
-					else if (outgoingEdge.isNavigation()) {
-						if (targetNode.isExplicitNull()) {
-							if (unconditionalNodes.add(targetNode)) {
-								moreMoreNodes.add(targetNode);
-							}
-						}
-						else if (node.isRequired() && ((NavigableEdge)outgoingEdge).getProperty().isIsRequired()) {
-							if (unconditionalNodes.add(targetNode)) {
-								moreMoreNodes.add(targetNode);
-							}
-						}
-					}
-					else {
-						System.out.println("Unsupported outgoing edge in " + this + " : " + outgoingEdge);
-					}
-				}
-			}
-			if (moreMoreNodes.size() <= 0) {
-				break;
-			}
-			moreUnconditionalNodes = moreMoreNodes;
-		}
-		this.unconditionalNodes = new ArrayList<>(unconditionalNodes);
-		Collections.sort(this.unconditionalNodes, NameUtil.NAMEABLE_COMPARATOR);
-		return unconditionalNodes;
-	}
-
-	protected void computeUtilities(@NonNull Iterable<@NonNull Node> headNodes) {		// FIXME remove assertions after 1-Jan-2017
-		Set<@NonNull Node> stronglyMatchedNodes = computeStronglyMatchedNodes(headNodes);
-		Set<@NonNull Node> unconditionalNodes = computeUnconditionalNodes(headNodes);
-		Set<@NonNull Node> conditionalNodes = computeConditionalNodes(unconditionalNodes);
-		//		Set<@NonNull Node> dependencyNodes = computeDependencyNodes(headNodes);
-		Set<@NonNull Node> deadNodes = null;
-		//
-		for (@NonNull Node node : QVTscheduleUtil.getOwnedNodes(this)) {
-			if (stronglyMatchedNodes.contains(node)) {
-				node.setUtility(Node.Utility.STRONGLY_MATCHED);
-				assert unconditionalNodes.contains(node);
-				//				assert !dependencyNodes.contains(node);
-			}
-			else if (unconditionalNodes.contains(node) && !node.isDependency()) {
-				node.setUtility(Node.Utility.WEAKLY_MATCHED);
-				//				assert !dependencyNodes.contains(node);
-			}
-			else if (conditionalNodes.contains(node)) {
-				node.setUtility(Node.Utility.CONDITIONAL);
-				//				assert !dependencyNodes.contains(node);
-			}
-			else if (node.isDependency()) {
-				node.setUtility(Node.Utility.DEPENDENCY);
-			}
-			else {
-				System.err.println("Dead node in " + this + " : " + node);
-				if (deadNodes == null) {
-					deadNodes = new HashSet<>();
-				}
-				deadNodes.add(node);
-				node.setUtility(Node.Utility.DEAD);
-				toString();
-			}
-		}
-		if (deadNodes != null) {
-			this.deadNodes = new ArrayList<>(deadNodes);
-			Collections.sort(this.deadNodes, NameUtil.NAMEABLE_COMPARATOR);
-		}
-		/*		for (@NonNull Node node : getNodes()) {
-			boolean isMatched = node.isMatched();
-			boolean isUnconditional = node.isUnconditional();
-			boolean isRequired = node.isRequired();
-			boolean isPattern = node.isPattern();
-			if (isMatched != (isUnconditional && isPattern)) {
-				System.out.println("Inconsistently isMatched in " + this + " : " + node);
-			}
-		} */
-	}
-
 	@Override
 	public @NonNull String getColor() {
 		return "green";
@@ -472,17 +87,17 @@ public abstract class MappingRegionImpl extends RegionImpl implements MappingReg
 	@Override
 	public final @NonNull List<Node> getHeadNodes() {
 		List<@NonNull Node> headNodes2 = headNodes;
-		if (headNodes2 == null) {
-			headNodes = headNodes2 = computeHeadNodes();
-		}
+		assert headNodes2 != null;
+		//			headNodes = headNodes2 = new ArrayList<>(); //computeHeadNodes();
+		//		}
 		return headNodes2;
 	}
 
-	private boolean isConditionalEdge(@NonNull Edge edge) {
-		String edgeName = edge.getName();
-		return QVTscheduleConstants.IF_THEN_NAME.equals(edgeName)
-				|| QVTscheduleConstants.IF_ELSE_NAME.equals(edgeName)
-				|| QVTscheduleConstants.LOOP_BODY_NAME.equals(edgeName);
+	public final @NonNull List<Node> getHeadNodes2() {
+		List<@NonNull Node> headNodes2 = headNodes;
+		assert headNodes2 == null;
+		headNodes = headNodes2 = new ArrayList<>();
+		return headNodes2;
 	}
 
 	@Override