[507096] Migrate Region merge functionality to EarlyMerger
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractRegion.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractRegion.java
index 45eacb0..14b5c5b 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractRegion.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/AbstractRegion.java
@@ -28,12 +28,10 @@
import org.eclipse.ocl.pivot.TypedElement;
import org.eclipse.ocl.pivot.VariableDeclaration;
import org.eclipse.ocl.pivot.utilities.ClassUtil;
-import org.eclipse.ocl.pivot.utilities.NameUtil;
import org.eclipse.ocl.pivot.utilities.StringUtil;
import org.eclipse.qvtd.compiler.CompilerProblem;
import org.eclipse.qvtd.compiler.internal.qvtp2qvts.analysis.ClassDatumAnalysis;
import org.eclipse.qvtd.compiler.internal.qvts2qvti.QVTs2QVTiVisitor;
-import org.eclipse.qvtd.compiler.internal.qvts2qvts.Region2Depth;
import org.eclipse.qvtd.compiler.internal.utilities.SymbolNameBuilder;
import org.eclipse.qvtd.compiler.internal.utilities.ToDOT;
import org.eclipse.qvtd.pivot.qvtbase.TypedModel;
@@ -536,188 +534,6 @@
}
@Override
- public @Nullable Map<@NonNull Node, @NonNull Node> canMerge(@NonNull Region secondaryRegion, @NonNull Region2Depth region2depths, boolean isLateMerge) {
- Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = null;
- Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2node = getCompleteClass2Node();
- //
- // Find the unambiguous head-node matches
- //
- List<@NonNull Node> secondaryHeadNodes = secondaryRegion.getHeadNodes();
- if (secondaryHeadNodes.size() != 1) {
- return null;
- }
- Node secondaryHeadNode = secondaryHeadNodes.get(0);
- CompleteClass completeClass = secondaryHeadNode.getCompleteClass();
- List<@NonNull Node> primaryNodes = completeClass2node.get(completeClass);
- if (primaryNodes != null) {
- Node primaryHeadNode = selectMergedHeadNode(secondaryHeadNode, primaryNodes);
- if (primaryHeadNode == null) {
- return null;
- }
- secondaryNode2primaryNode = new HashMap<>();
- if ("if".equals(secondaryHeadNode.getName())) {
- secondaryHeadNode.getName();
- }
- secondaryNode2primaryNode.put(secondaryHeadNode, primaryHeadNode);
- }
- if (secondaryNode2primaryNode == null) {
- return null;
- }
- //
- // Validate the transitive navigation from the head nodes. All common navigation edges must have compatible node types.
- //
- if (!canMergeInternal(secondaryRegion, secondaryNode2primaryNode, region2depths, isLateMerge)) {
- return null;
- }
- //FIXME Must be symmetrically mergeable; do tests before creating MergedRegion
- //
- // Validate the true node predicate compatibility
- //
- Iterable<@NonNull Node> primaryTrueNodes = this.getTrueNodes();
- Iterable<@NonNull Node> secondaryTrueNodes = secondaryRegion.getTrueNodes();
- if (Iterables.size(primaryTrueNodes) != Iterables.size(secondaryTrueNodes)) {
- return null;
- }
- for (@NonNull Node primaryTrueNode : primaryTrueNodes) {
- boolean gotIt = false;
- for (@NonNull Node secondaryTrueNode : secondaryTrueNodes) {
- assert secondaryTrueNode != null;
- Map<@NonNull Node, @NonNull Node> primary2secondary = new HashMap<>();
- if (isEquivalent(primaryTrueNode, secondaryTrueNode, primary2secondary)) { // FIXME use hashes
- gotIt = true;
- 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;
- }
- }
- if (!gotIt) {
- return null;
- }
- }
- return secondaryNode2primaryNode;
- }
- private 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++) {
- @NonNull Node secondarySourceNode = secondaryNodesList.get(i);
- Node primarySourceNode = secondaryNode2primaryNode.get(secondarySourceNode);
- if (primarySourceNode == null) {
- if (secondarySourceNode.isPredicated()) {
- return false;
- }
- }
- for (@NonNull NavigableEdge secondaryEdge : secondarySourceNode.getNavigationEdges()) {
- Node secondaryTargetNode = secondaryEdge.getTarget();
- Node primaryTargetNode = null;
- if (primarySourceNode != null) {
- Edge primaryEdge = primarySourceNode.getNavigationEdge(secondaryEdge.getProperty());
- if (primaryEdge != null) {
- primaryTargetNode = primaryEdge.getTarget();
- // primaryTargetNode = primaryTargetNode.getCastEquivalentNode();
- // secondaryTargetNode = secondaryTargetNode.getCastEquivalentNode();
- if (primaryTargetNode.getCompleteClass() != secondaryTargetNode.getCompleteClass()) { // FIXME conforms
- return false;
- }
- if (primaryTargetNode.isExplicitNull() != secondaryTargetNode.isExplicitNull()) { // FIXME conforms
- return false;
- }
- }
- else {
- if (secondaryEdge.isPredicated()) {
- if (!isLateMerge) { // FIXME must locate in ancestry; if present can merge, if not cannot
- return false;
- }
- for (@SuppressWarnings("unused") Node secondaryOriginNode : secondaryTargetNode.getUsedBindingSources()) {
- return false;
- }
- }
- }
- }
- if (primaryTargetNode != null) {
- Node primaryTargetNode2 = secondaryNode2primaryNode.get(secondaryTargetNode);
- if (primaryTargetNode2 == null) {
- if ("if".equals(secondaryTargetNode.getName())) {
- secondaryTargetNode.getName();
- }
- secondaryNode2primaryNode.put(secondaryTargetNode, primaryTargetNode);
- }
- }
- assert secondaryTargetNode != null;
- if (secondaryNodes.add(secondaryTargetNode)) {
- // if (mergedTargetNode != null) {
- // if (!secondaryTargetNode.isAttributeNode()) {
- secondaryNodesList.add(secondaryTargetNode);
- // }
- }
-
- }
- if (!isLateMerge && (primarySourceNode != null)) {
- for (@NonNull Edge secondaryEdge : secondarySourceNode.getComputationEdges()) {
- Node secondaryTargetNode = secondaryEdge.getTarget();
- Node primaryTargetNode = null;
- for (@NonNull Edge primaryEdge : primarySourceNode.getComputationEdges()) {
- if (ClassUtil.safeEquals(primaryEdge.getName(), secondaryEdge.getName())) {
- primaryTargetNode = primaryEdge.getTarget();
- if (isEquivalent(secondaryTargetNode, primaryTargetNode, secondaryNode2primaryNode)) {
- secondaryNodesList.add(secondaryTargetNode);
- }
- }
- }
- }
- }
- /*
-
- }
- if (secondaryEdge instanceof NavigationEdge) {
- Edge primaryEdge = primarySourceNode.getNavigationEdge(((NavigationEdge)secondaryEdge).getProperty());
- if (primaryEdge != null) {
- primaryTargetNode = primaryEdge.getTarget();
-// primaryTargetNode = primaryTargetNode.getCastEquivalentNode();
-// secondaryTargetNode = secondaryTargetNode.getCastEquivalentNode();
- if (primaryTargetNode.getCompleteClass() != secondaryTargetNode.getCompleteClass()) { // FIXME conforms
- return false;
- }
- }
- else {
- if (secondaryEdge.isPredicated()) {
- if (!isLateMerge) { // FIXME must locate in ancestry; if present can merge, if not cannot
- return false;
- }
- for (@SuppressWarnings("null")@NonNull Node secondaryOriginNode : secondaryTargetNode.getUsedBindingSources()) {
- if (!region2depths.isAfter(secondaryOriginNode, this)) {
- return false;
- }
- }
- }
- }
- }
- else {} // FIXME???
- }
- if (primaryTargetNode != null) {
- Node primaryTargetNode2 = secondaryNode2primaryNode.get(secondaryTargetNode);
- if (primaryTargetNode2 == null) {
- secondaryNode2primaryNode.put(secondaryTargetNode, primaryTargetNode);
- }
- if (secondaryNodes.add(secondaryTargetNode)) {
- // if (mergedTargetNode != null) {
- if (!secondaryTargetNode.isAttributeNode()) {
- secondaryNodesList.add(secondaryTargetNode);
- }
- }
- }
- } */
- }
- return true;
- }
-
- @Override
public void checkIncomingConnections() {
/* for (@NonNull Node node : getNodes()) {
NodeConnection incomingConnection = node.getIncomingConnection();
@@ -1599,22 +1415,6 @@
return "blue";
}
- private @NonNull Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> getCompleteClass2Node() {
- Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2node = new HashMap<>();
- for (@NonNull Node node : getNodes()) {
- CompleteClass completeClass = node.getCompleteClass();
- List<@NonNull Node> mergedNodes = completeClass2node.get(completeClass);
- if (mergedNodes == null) {
- mergedNodes = new ArrayList<>();
- completeClass2node.put(completeClass, mergedNodes);
- }
- if (!mergedNodes.contains(node)) {
- mergedNodes.add(node);
- }
- }
- return completeClass2node;
- }
-
@Override
public final @NonNull Iterable<@NonNull Node> getComposedNodes() {
return Iterables.filter(nodes, IsComposedNodePredicate.INSTANCE);
@@ -2093,42 +1893,6 @@
return false;
}
- /**
- * Return true if the operation nodes for primaryNode and secondaryNode are equivalent
- * assigning equivalences to equivalentNodes.
- */
- private 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;
- }
- if (primaryNode.getNodeRole() != secondaryNode.getNodeRole()) {
- return false;
- }
- if (!ClassUtil.safeEquals(primaryNode.getName(), secondaryNode.getName())) { // FIXME stronger e.g. referredOperation
- return false;
- }
- HashMap<@NonNull Node, @NonNull Node> nestedPrimary2secondary = new HashMap<>(primary2secondary);
- nestedPrimary2secondary.put(primaryNode, secondaryNode);
- for (@NonNull Edge primaryEdge : primaryNode.getArgumentEdges()) {
- boolean gotIt = false;
- for (@NonNull Edge secondaryEdge : secondaryNode.getArgumentEdges()) {
- if (ClassUtil.safeEquals(primaryEdge.getName(), secondaryEdge.getName())) {
- if (!isEquivalent(primaryEdge.getSource(), secondaryEdge.getSource(), nestedPrimary2secondary)) {
- return false;
- }
- gotIt = true;
- break;
- }
- }
- if (!gotIt) {
- return false;
- }
- }
- primary2secondary.putAll(nestedPrimary2secondary);
- return true;
- }
-
@Override
public boolean isOperationRegion() {
return false;
@@ -2288,11 +2052,11 @@
}
public void resolveRecursion() {
- Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2node = getCompleteClass2Node();
+ Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2nodes = RegionUtil.getCompleteClass2Nodes(this);
List<@NonNull Node> headNodes = getHeadNodes();
if (headNodes.size() == 1) { // FIXME multi-heads
Node headNode = headNodes.get(0);
- List<@NonNull Node> nodeList = completeClass2node.get(headNode.getCompleteClass());
+ List<@NonNull Node> nodeList = completeClass2nodes.get(headNode.getCompleteClass());
assert nodeList != null;
if (nodeList.size() > 1) {
for (@NonNull Node node : nodeList) {
@@ -2313,75 +2077,6 @@
}
}
- /**
- * Chose the headNode from a group of peer nodes that has the most non-implicit properties targeting its peers.
- */
- protected @NonNull Node selectBestHeadNode(@NonNull List<@NonNull Node> headNodes) {
- int size = headNodes.size();
- assert size >= 1;
- if (size == 1) {
- return headNodes.get(0);
- }
- Node bestHeadNode = null;
- int bestNonImplicits = -1;
- List<@NonNull Node> sortedHeadNodes = new ArrayList<>(headNodes);
- Collections.sort(sortedHeadNodes, NameUtil.NAMEABLE_COMPARATOR); // Stabilize order
- for (@NonNull Node thisHeadNode : sortedHeadNodes) {
- int nonImplicits = 0;
- for (@NonNull Node thatHeadNode : sortedHeadNodes) {
- for (@NonNull NavigableEdge edge : thisHeadNode.getNavigationEdges()) {
- if (edge.getTarget() == thatHeadNode) {
- Property property = edge.getProperty();
- if (!property.isIsImplicit()) {
- nonImplicits++;
- break;
- }
- }
- }
- }
- if (nonImplicits > bestNonImplicits) {
- bestHeadNode = thisHeadNode;
- bestNonImplicits = nonImplicits;
- }
- }
- assert bestHeadNode != null;
- return bestHeadNode;
- }
-
- private @Nullable Node selectMergedHeadNode(@NonNull Node headNode, @NonNull List<@NonNull Node> mergedNodes) {
- if (mergedNodes.size() == 1) {
- Node mergedNode = selectBestHeadNode(mergedNodes);
- if (mergedNode.isIterator()) {
- return null;
- }
- return mergedNode;
- }
- if (mergedNodes.size() == 0) {
- return null;
- }
- Iterable<NavigableEdge> predicateEdges = headNode.getPredicateEdges();
- // if (predicateEdges == null) {
- // return null;
- // }
- for (@NonNull Node mergedNode : mergedNodes) {
- boolean ok = !mergedNode.isIterator();
- if (ok) {
- for (@NonNull NavigableEdge predicateEdge : predicateEdges) {
- Property property = predicateEdge.getProperty();
- Node navigation = mergedNode.getNavigationTarget(property);
- if (navigation == null) {
- ok = false;
- break;
- }
- }
- }
- if (ok) { // FIXME stronger checking
- return mergedNode;
- }
- }
- return null;
- }
-
@Override
public void setInvokingRegion(@NonNull ScheduledRegion invokingRegion) {
this.invokingRegion = invokingRegion;
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 3a79bae..0678cd6 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
@@ -37,6 +37,7 @@
import org.eclipse.qvtd.compiler.ProblemHandler;
import org.eclipse.qvtd.compiler.internal.qvtp2qvts.analysis.ClassDatumAnalysis;
import org.eclipse.qvtd.compiler.internal.qvts2qvts.Region2Depth;
+import org.eclipse.qvtd.compiler.internal.qvts2qvts.merger.EarlyMerger;
import org.eclipse.qvtd.pivot.qvtbase.Transformation;
import org.eclipse.qvtd.pivot.qvtcore.Mapping;
import org.eclipse.qvtd.pivot.schedule.ClassDatum;
@@ -140,10 +141,10 @@
for (@NonNull MappingRegion secondaryRegion : secondaryRegions) {
assert secondaryRegion != null;
if (residualInputRegions.contains(secondaryRegion)) {
- Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = mergedRegion.canMerge(secondaryRegion, region2depths, false);
+ Map<@NonNull Node, @NonNull Node> secondaryNode2primaryNode = EarlyMerger.canMerge(mergedRegion, secondaryRegion, region2depths, false);
if (secondaryNode2primaryNode != null) {
boolean isSharedHead = isSharedHead(mergedRegion, secondaryRegion);
- if (!isSharedHead || (secondaryRegion.canMerge(mergedRegion, region2depths, false) != null)) {
+ if (!isSharedHead || (EarlyMerger.canMerge(secondaryRegion, mergedRegion, region2depths, false) != null)) {
residualInputRegions.remove(mergedRegion);
residualInputRegions.remove(secondaryRegion);
mergedRegion = RegionMerger.createMergedRegion(mergedRegion, secondaryRegion, secondaryNode2primaryNode);
diff --git a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/Region.java b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/Region.java
index 489668d..2b9b85c 100644
--- a/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/Region.java
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvtp2qvts/Region.java
@@ -21,7 +21,6 @@
import org.eclipse.ocl.pivot.VariableDeclaration;
import org.eclipse.ocl.pivot.utilities.Nameable;
import org.eclipse.qvtd.compiler.internal.qvtp2qvts.analysis.ClassDatumAnalysis;
-import org.eclipse.qvtd.compiler.internal.qvts2qvts.Region2Depth;
import org.eclipse.qvtd.pivot.qvtbase.TypedModel;
import org.eclipse.qvtd.pivot.qvtbase.graphs.GraphStringBuilder;
import org.eclipse.qvtd.pivot.qvtbase.graphs.GraphStringBuilder.GraphNode;
@@ -38,7 +37,6 @@
void addVariableNode(@NonNull VariableDeclaration variable, @NonNull Node node);
void buildPredicatedNavigationEdgesIndex(@NonNull Map<@NonNull TypedModel, @NonNull Map<@NonNull Property, @NonNull List<@NonNull NavigableEdge>>> typedModel2property2predicatedEdges);
void buildRealizedNavigationEdgesIndex(@NonNull Map<@NonNull TypedModel, @NonNull Map<@NonNull Property, @NonNull List<@NonNull NavigableEdge>>> typedModel2property2realizedEdges);
- @Nullable Map<@NonNull Node, @NonNull Node> canMerge(@NonNull Region secondaryRegion, @NonNull Region2Depth region2depths, boolean isLateMerge);
void checkIncomingConnections();
void computeCheckedOrEnforcedEdges(@NonNull Map<@NonNull TypedModel, @NonNull Map<@NonNull Property, @NonNull List<@NonNull NavigableEdge>>> typedModel2property2predicatedEdges,
@NonNull Map<@NonNull TypedModel, @NonNull Map<@NonNull Property, @NonNull List<@NonNull NavigableEdge>>> typedModel2property2realizedEdges);
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 99f50ab..06a1576 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
@@ -10,6 +10,11 @@
*******************************************************************************/
package org.eclipse.qvtd.compiler.internal.qvtp2qvts;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
import org.eclipse.emf.ecore.EObject;
import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.jdt.annotation.Nullable;
@@ -359,6 +364,22 @@
}
}
+ public static @NonNull Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> getCompleteClass2Nodes(@NonNull Region region) {
+ Map<@NonNull CompleteClass, @NonNull List<@NonNull Node>> completeClass2node = new HashMap<>();
+ for (@NonNull Node node : region.getNodes()) {
+ CompleteClass completeClass = node.getCompleteClass();
+ List<@NonNull Node> mergedNodes = completeClass2node.get(completeClass);
+ if (mergedNodes == null) {
+ mergedNodes = new ArrayList<>();
+ completeClass2node.put(completeClass, mergedNodes);
+ }
+ if (!mergedNodes.contains(node)) {
+ mergedNodes.add(node);
+ }
+ }
+ return completeClass2node;
+ }
+
public static Role.@NonNull Phase getOperationNodePhase(@NonNull Region region, @NonNull TypedElement typedElement, @NonNull Node... argNodes) {
boolean isLoaded = false;
boolean isPredicated = false;
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
new file mode 100644
index 0000000..5bf9ae9
--- /dev/null
+++ b/plugins/org.eclipse.qvtd.compiler/src/org/eclipse/qvtd/compiler/internal/qvts2qvts/merger/EarlyMerger.java
@@ -0,0 +1,323 @@
+/*******************************************************************************
+ * 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.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.ocl.pivot.utilities.NameUtil;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Edge;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.NavigableEdge;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Node;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.Region;
+import org.eclipse.qvtd.compiler.internal.qvtp2qvts.RegionUtil;
+import org.eclipse.qvtd.compiler.internal.qvts2qvts.Region2Depth;
+
+import com.google.common.collect.Iterables;
+
+public class EarlyMerger
+{
+ public static @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);
+ //
+ // Find the unambiguous head-node matches
+ //
+ List<@NonNull Node> secondaryHeadNodes = secondaryRegion.getHeadNodes();
+ if (secondaryHeadNodes.size() != 1) {
+ return null;
+ }
+ Node secondaryHeadNode = secondaryHeadNodes.get(0);
+ CompleteClass completeClass = secondaryHeadNode.getCompleteClass();
+ List<@NonNull Node> primaryNodes = completeClass2nodes.get(completeClass);
+ if (primaryNodes != null) {
+ Node primaryHeadNode = selectMergedHeadNode(secondaryHeadNode, primaryNodes);
+ if (primaryHeadNode == null) {
+ return null;
+ }
+ secondaryNode2primaryNode = new HashMap<>();
+ if ("if".equals(secondaryHeadNode.getName())) {
+ secondaryHeadNode.getName();
+ }
+ secondaryNode2primaryNode.put(secondaryHeadNode, primaryHeadNode);
+ }
+ if (secondaryNode2primaryNode == null) {
+ return null;
+ }
+ //
+ // Validate the transitive navigation from the head nodes. All common navigation edges must have compatible node types.
+ //
+ if (!canMergeInternal(secondaryRegion, secondaryNode2primaryNode, region2depths, isLateMerge)) {
+ return null;
+ }
+ //FIXME Must be symmetrically mergeable; do tests before creating MergedRegion
+ //
+ // Validate the true node predicate compatibility
+ //
+ Iterable<@NonNull Node> primaryTrueNodes = primaryRegion.getTrueNodes();
+ Iterable<@NonNull Node> secondaryTrueNodes = secondaryRegion.getTrueNodes();
+ if (Iterables.size(primaryTrueNodes) != Iterables.size(secondaryTrueNodes)) {
+ return null;
+ }
+ for (@NonNull Node primaryTrueNode : primaryTrueNodes) {
+ boolean gotIt = false;
+ for (@NonNull Node secondaryTrueNode : secondaryTrueNodes) {
+ assert secondaryTrueNode != null;
+ Map<@NonNull Node, @NonNull Node> primary2secondary = new HashMap<>();
+ if (isEquivalent(primaryTrueNode, secondaryTrueNode, primary2secondary)) { // FIXME use hashes
+ gotIt = true;
+ 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;
+ }
+ }
+ if (!gotIt) {
+ return null;
+ }
+ }
+ return secondaryNode2primaryNode;
+ }
+ private static 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++) {
+ @NonNull Node secondarySourceNode = secondaryNodesList.get(i);
+ Node primarySourceNode = secondaryNode2primaryNode.get(secondarySourceNode);
+ if (primarySourceNode == null) {
+ if (secondarySourceNode.isPredicated()) {
+ return false;
+ }
+ }
+ for (@NonNull NavigableEdge secondaryEdge : secondarySourceNode.getNavigationEdges()) {
+ Node secondaryTargetNode = secondaryEdge.getTarget();
+ Node primaryTargetNode = null;
+ if (primarySourceNode != null) {
+ Edge primaryEdge = primarySourceNode.getNavigationEdge(secondaryEdge.getProperty());
+ if (primaryEdge != null) {
+ primaryTargetNode = primaryEdge.getTarget();
+ // primaryTargetNode = primaryTargetNode.getCastEquivalentNode();
+ // secondaryTargetNode = secondaryTargetNode.getCastEquivalentNode();
+ if (primaryTargetNode.getCompleteClass() != secondaryTargetNode.getCompleteClass()) { // FIXME conforms
+ return false;
+ }
+ if (primaryTargetNode.isExplicitNull() != secondaryTargetNode.isExplicitNull()) { // FIXME conforms
+ return false;
+ }
+ }
+ else {
+ if (secondaryEdge.isPredicated()) {
+ if (!isLateMerge) { // FIXME must locate in ancestry; if present can merge, if not cannot
+ return false;
+ }
+ for (@SuppressWarnings("unused") Node secondaryOriginNode : secondaryTargetNode.getUsedBindingSources()) {
+ return false;
+ }
+ }
+ }
+ }
+ if (primaryTargetNode != null) {
+ Node primaryTargetNode2 = secondaryNode2primaryNode.get(secondaryTargetNode);
+ if (primaryTargetNode2 == null) {
+ if ("if".equals(secondaryTargetNode.getName())) {
+ secondaryTargetNode.getName();
+ }
+ secondaryNode2primaryNode.put(secondaryTargetNode, primaryTargetNode);
+ }
+ }
+ assert secondaryTargetNode != null;
+ if (secondaryNodes.add(secondaryTargetNode)) {
+ // if (mergedTargetNode != null) {
+ // if (!secondaryTargetNode.isAttributeNode()) {
+ secondaryNodesList.add(secondaryTargetNode);
+ // }
+ }
+
+ }
+ if (!isLateMerge && (primarySourceNode != null)) {
+ for (@NonNull Edge secondaryEdge : secondarySourceNode.getComputationEdges()) {
+ Node secondaryTargetNode = secondaryEdge.getTarget();
+ Node primaryTargetNode = null;
+ for (@NonNull Edge primaryEdge : primarySourceNode.getComputationEdges()) {
+ if (ClassUtil.safeEquals(primaryEdge.getName(), secondaryEdge.getName())) {
+ primaryTargetNode = primaryEdge.getTarget();
+ if (isEquivalent(secondaryTargetNode, primaryTargetNode, secondaryNode2primaryNode)) {
+ secondaryNodesList.add(secondaryTargetNode);
+ }
+ }
+ }
+ }
+ }
+ /*
+
+ }
+ if (secondaryEdge instanceof NavigationEdge) {
+ Edge primaryEdge = primarySourceNode.getNavigationEdge(((NavigationEdge)secondaryEdge).getProperty());
+ if (primaryEdge != null) {
+ primaryTargetNode = primaryEdge.getTarget();
+// primaryTargetNode = primaryTargetNode.getCastEquivalentNode();
+// secondaryTargetNode = secondaryTargetNode.getCastEquivalentNode();
+ if (primaryTargetNode.getCompleteClass() != secondaryTargetNode.getCompleteClass()) { // FIXME conforms
+ return false;
+ }
+ }
+ else {
+ if (secondaryEdge.isPredicated()) {
+ if (!isLateMerge) { // FIXME must locate in ancestry; if present can merge, if not cannot
+ return false;
+ }
+ for (@SuppressWarnings("null")@NonNull Node secondaryOriginNode : secondaryTargetNode.getUsedBindingSources()) {
+ if (!region2depths.isAfter(secondaryOriginNode, this)) {
+ return false;
+ }
+ }
+ }
+ }
+ }
+ else {} // FIXME???
+ }
+ if (primaryTargetNode != null) {
+ Node primaryTargetNode2 = secondaryNode2primaryNode.get(secondaryTargetNode);
+ if (primaryTargetNode2 == null) {
+ secondaryNode2primaryNode.put(secondaryTargetNode, primaryTargetNode);
+ }
+ if (secondaryNodes.add(secondaryTargetNode)) {
+ // if (mergedTargetNode != null) {
+ if (!secondaryTargetNode.isAttributeNode()) {
+ secondaryNodesList.add(secondaryTargetNode);
+ }
+ }
+ }
+ } */
+ }
+ return true;
+ }
+
+ /**
+ * 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) {
+ Node node = primary2secondary.get(primaryNode);
+ if (node != null) {
+ return node == secondaryNode;
+ }
+ if (primaryNode.getNodeRole() != secondaryNode.getNodeRole()) {
+ return false;
+ }
+ if (!ClassUtil.safeEquals(primaryNode.getName(), secondaryNode.getName())) { // FIXME stronger e.g. referredOperation
+ return false;
+ }
+ HashMap<@NonNull Node, @NonNull Node> nestedPrimary2secondary = new HashMap<>(primary2secondary);
+ nestedPrimary2secondary.put(primaryNode, secondaryNode);
+ for (@NonNull Edge primaryEdge : primaryNode.getArgumentEdges()) {
+ boolean gotIt = false;
+ for (@NonNull Edge secondaryEdge : secondaryNode.getArgumentEdges()) {
+ if (ClassUtil.safeEquals(primaryEdge.getName(), secondaryEdge.getName())) {
+ if (!isEquivalent(primaryEdge.getSource(), secondaryEdge.getSource(), nestedPrimary2secondary)) {
+ return false;
+ }
+ gotIt = true;
+ break;
+ }
+ }
+ if (!gotIt) {
+ return false;
+ }
+ }
+ primary2secondary.putAll(nestedPrimary2secondary);
+ return true;
+ }
+
+ /**
+ * 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) {
+ int size = headNodes.size();
+ assert size >= 1;
+ if (size == 1) {
+ return headNodes.get(0);
+ }
+ Node bestHeadNode = null;
+ int bestNonImplicits = -1;
+ List<@NonNull Node> sortedHeadNodes = new ArrayList<>(headNodes);
+ Collections.sort(sortedHeadNodes, NameUtil.NAMEABLE_COMPARATOR); // Stabilize order
+ for (@NonNull Node thisHeadNode : sortedHeadNodes) {
+ int nonImplicits = 0;
+ for (@NonNull Node thatHeadNode : sortedHeadNodes) {
+ for (@NonNull NavigableEdge edge : thisHeadNode.getNavigationEdges()) {
+ if (edge.getTarget() == thatHeadNode) {
+ Property property = edge.getProperty();
+ if (!property.isIsImplicit()) {
+ nonImplicits++;
+ break;
+ }
+ }
+ }
+ }
+ if (nonImplicits > bestNonImplicits) {
+ bestHeadNode = thisHeadNode;
+ bestNonImplicits = nonImplicits;
+ }
+ }
+ assert bestHeadNode != null;
+ return bestHeadNode;
+ }
+
+ private static @Nullable Node selectMergedHeadNode(@NonNull Node headNode, @NonNull List<@NonNull Node> mergedNodes) {
+ if (mergedNodes.size() == 1) {
+ Node mergedNode = selectBestHeadNode(mergedNodes);
+ if (mergedNode.isIterator()) {
+ return null;
+ }
+ return mergedNode;
+ }
+ if (mergedNodes.size() == 0) {
+ return null;
+ }
+ Iterable<NavigableEdge> predicateEdges = headNode.getPredicateEdges();
+ // if (predicateEdges == null) {
+ // return null;
+ // }
+ for (@NonNull Node mergedNode : mergedNodes) {
+ boolean ok = !mergedNode.isIterator();
+ if (ok) {
+ for (@NonNull NavigableEdge predicateEdge : predicateEdges) {
+ Property property = predicateEdge.getProperty();
+ Node navigation = mergedNode.getNavigationTarget(property);
+ if (navigation == null) {
+ ok = false;
+ break;
+ }
+ }
+ }
+ if (ok) { // FIXME stronger checking
+ return mergedNode;
+ }
+ }
+ return null;
+ }
+}