graphql-java · andimarek · Apr 18, 2023 · Apr 6, 2023 · Apr 6, 2023 · Apr 11, 2023
diff --git a/src/main/java/graphql/schema/diffing/DiffImpl.java b/src/main/java/graphql/schema/diffing/DiffImpl.java
diff --git a/src/main/java/graphql/schema/diffing/EditorialCostForMapping.java b/src/main/java/graphql/schema/diffing/EditorialCostForMapping.java
@@ -2,19 +2,39 @@
 
 import graphql.Internal;
 
+import java.util.ArrayList;
+import java.util.LinkedHashSet;
 import java.util.List;
+import java.util.Set;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.Predicate;
 
 @Internal
 public class EditorialCostForMapping {
+    /**
+     * @see #baseEditorialCostForMapping(Mapping, SchemaGraph, SchemaGraph, List)
+     */
+    public static int baseEditorialCostForMapping(Mapping mapping, // can be a partial mapping
+                                                  SchemaGraph sourceGraph, // the whole graph
+                                                  SchemaGraph targetGraph // the whole graph
+    ) {
+        return baseEditorialCostForMapping(mapping, sourceGraph, targetGraph, new ArrayList<>());
+    }
 
     /**
-     * a mapping introduces a subgraph consisting of all vertices and all edges between these vertices
+     * Gets the "editorial cost for mapping" for the base mapping.
+     * <p>
+     * Use this is as base cost when invoking
+     * {@link #editorialCostForMapping(int, Mapping, SchemaGraph, SchemaGraph)}
+     * as it heavily speeds up performance.
      */
-    public static int editorialCostForMapping(Mapping mapping, // can be a partial mapping
-                                              SchemaGraph sourceGraph, // the whole graph
-                                              SchemaGraph targetGraph, // the whole graph
-                                              List<EditOperation> editOperationsResult) {
+    public static int baseEditorialCostForMapping(Mapping mapping, // can be a partial mapping
+                                                  SchemaGraph sourceGraph, // the whole graph
+                                                  SchemaGraph targetGraph, // the whole graph
+                                                  List<EditOperation> editOperationsResult) {
         int cost = 0;
+
+
         for (int i = 0; i < mapping.size(); i++) {
             Vertex sourceVertex = mapping.getSource(i);
             Vertex targetVertex = mapping.getTarget(i);
@@ -31,9 +51,9 @@ public static int editorialCostForMapping(Mapping mapping, // can be a partial m
                 cost++;
             }
         }
-        List<Edge> edges = sourceGraph.getEdges();
+
         // edge deletion or relabeling
-        for (Edge sourceEdge : edges) {
+        for (Edge sourceEdge : sourceGraph.getEdges()) {
             // only edges relevant to the subgraph
             if (!mapping.containsSource(sourceEdge.getFrom()) || !mapping.containsSource(sourceEdge.getTo())) {
                 continue;
@@ -50,7 +70,6 @@ public static int editorialCostForMapping(Mapping mapping, // can be a partial m
             }
         }
 
-        //TODO: iterates over all edges in the target Graph
         for (Edge targetEdge : targetGraph.getEdges()) {
             // only subgraph edges
             if (!mapping.containsTarget(targetEdge.getFrom()) || !mapping.containsTarget(targetEdge.getTo())) {
@@ -63,8 +82,87 @@ public static int editorialCostForMapping(Mapping mapping, // can be a partial m
                 cost++;
             }
         }
+
         return cost;
     }
 
+    /**
+     * Calculates the "editorial cost for mapping" for the non-fixed targets in a {@link Mapping}.
+     * <p>
+     * The {@code baseCost} argument should be the cost for the fixed mapping from
+     * {@link #baseEditorialCostForMapping(Mapping, SchemaGraph, SchemaGraph)}.
+     * <p>
+     * The sum of the non-fixed costs and the fixed costs is total editorial cost for mapping.
+     */
+    public static int editorialCostForMapping(int baseCost,
+                                              Mapping mapping, // can be a partial mapping
+                                              SchemaGraph sourceGraph, // the whole graph
+                                              SchemaGraph targetGraph // the whole graph
+    ) {
+        AtomicInteger cost = new AtomicInteger(baseCost);
+
+        Set<Edge> seenEdges = new LinkedHashSet<>();
 
+        // Tells us whether the edge should be visited. We need to avoid counting edges more than once
+        Predicate<Edge> visitEdge = (data) -> {
+            if (seenEdges.contains(data)) {
+                return false;
+            } else {
+                seenEdges.add(data);
+                return true;
+            }
+        };
+
+        // Look through
+        mapping.forEachNonFixedSourceAndTarget((sourceVertex, targetVertex) -> {
+            // Vertex changing (relabeling)
+            boolean equalNodes = sourceVertex.getType().equals(targetVertex.getType()) && sourceVertex.getProperties().equals(targetVertex.getProperties());
+
+            if (!equalNodes) {
+                cost.getAndIncrement();
+            }
+
+            for (Edge sourceEdge : sourceGraph.getAdjacentEdgesAndInverseNonCopy(sourceVertex)) {
+                if (!visitEdge.test(sourceEdge)) {
+                    continue;
+                }
+
+                // only edges relevant to the subgraph
+                if (!mapping.containsSource(sourceEdge.getFrom()) || !mapping.containsSource(sourceEdge.getTo())) {
+                    continue;
+                }
+
+                Vertex targetFrom = mapping.getTarget(sourceEdge.getFrom());
+                Vertex targetTo = mapping.getTarget(sourceEdge.getTo());
+                Edge targetEdge = targetGraph.getEdge(targetFrom, targetTo);
+
+                if (targetEdge == null) {
+                    cost.getAndIncrement();
+                } else if (!sourceEdge.getLabel().equals(targetEdge.getLabel())) {
+                    cost.getAndIncrement();
+                }
+            }
+
+            for (Edge targetEdge : targetGraph.getAdjacentEdgesAndInverseNonCopy(targetVertex)) {
+                if (!visitEdge.test(targetEdge)) {
+                    continue;
+                }
+
+                // only edges relevant to the subgraph
+                if (!mapping.containsTarget(targetEdge.getFrom()) || !mapping.containsTarget(targetEdge.getTo())) {
+                    continue;
+                }
+
+                Vertex sourceFrom = mapping.getSource(targetEdge.getFrom());
+                Vertex sourceTo = mapping.getSource(targetEdge.getTo());
+                Edge sourceEdge = sourceGraph.getEdge(sourceFrom, sourceTo);
+
+                if (sourceEdge == null) {
+                    cost.getAndIncrement();
+                }
+            }
+        });
+
+        return cost.get();
+    }
 }
diff --git a/src/main/java/graphql/schema/diffing/Mapping.java b/src/main/java/graphql/schema/diffing/Mapping.java
@@ -5,8 +5,10 @@
 import graphql.Internal;
 
 import java.util.ArrayList;
+import java.util.Collections;
 import java.util.List;
-import java.util.Objects;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
 
 /**
  * A mapping (in the math sense) from a list of vertices to another list of
@@ -16,53 +18,88 @@
  */
 @Internal
 public class Mapping {
-    private BiMap<Vertex, Vertex> map = HashBiMap.create();
-    private List<Vertex> sourceList = new ArrayList<>();
-    private List<Vertex> targetList = new ArrayList<>();
 
-    private Mapping(BiMap<Vertex, Vertex> map, List<Vertex> sourceList, List<Vertex> targetList) {
+
+    private final BiMap<Vertex, Vertex> fixedMappings;
+    private final List<Vertex> fixedSourceList;
+    private final List<Vertex> fixedTargetList;
+
+    private final BiMap<Vertex, Vertex> map;
+    private final List<Vertex> sourceList;
+    private final List<Vertex> targetList;
+
+    private Mapping(BiMap<Vertex, Vertex> fixedMappings,
+                    List<Vertex> fixedSourceList,
+                    List<Vertex> fixedTargetList,
+                    BiMap<Vertex, Vertex> map,
+                    List<Vertex> sourceList,
+                    List<Vertex> targetList) {
+        this.fixedMappings = fixedMappings;
+        this.fixedSourceList = fixedSourceList;
+        this.fixedTargetList = fixedTargetList;
         this.map = map;
         this.sourceList = sourceList;
         this.targetList = targetList;
     }
 
-    public Mapping() {
+    public static Mapping newMapping(BiMap<Vertex, Vertex> fixedMappings, List<Vertex> fixedSourceList, List<Vertex> fixedTargetList) {
+        return new Mapping(fixedMappings, fixedSourceList, fixedTargetList, HashBiMap.create(), Collections.emptyList(), Collections.emptyList());
 
     }
 
     public Vertex getSource(Vertex target) {
+        if (fixedMappings.containsValue(target)) {
+            return fixedMappings.inverse().get(target);
+        }
         return map.inverse().get(target);
     }
 
     public Vertex getTarget(Vertex source) {
+        if (fixedMappings.containsKey(source)) {
+            return fixedMappings.get(source);
+        }
         return map.get(source);
     }
 
     public Vertex getSource(int i) {
-        return sourceList.get(i);
+        if (i < fixedSourceList.size()) {
+            return fixedSourceList.get(i);
+        }
+        return sourceList.get(i - fixedSourceList.size());
     }
 
     public Vertex getTarget(int i) {
-        return targetList.get(i);
-    }
-
-    public List<Vertex> getTargets() {
-        return targetList;
-    }
-
-    public List<Vertex> getSources() {
-        return sourceList;
+        if (i < fixedTargetList.size()) {
+            return fixedTargetList.get(i);
+        }
+        return targetList.get(i - fixedTargetList.size());
     }
 
     public boolean containsSource(Vertex sourceVertex) {
+        if (fixedMappings.containsKey(sourceVertex)) {
+            return true;
+        }
         return map.containsKey(sourceVertex);
     }
 
     public boolean containsTarget(Vertex targetVertex) {
+        if (fixedMappings.containsValue(targetVertex)) {
+            return true;
+        }
         return map.containsValue(targetVertex);
     }
 
+
+    public boolean contains(Vertex vertex, boolean sourceOrTarget) {
+        return sourceOrTarget ? containsSource(vertex) : containsTarget(vertex);
+    }
+
+
     public int size() {
+        return fixedMappings.size() + map.size();
+    }
+
+    public int nonFixedSize() {
         return map.size();
     }
 
@@ -77,14 +114,14 @@ public Mapping removeLastElement() {
         newMap.remove(this.sourceList.get(this.sourceList.size() - 1));
         List<Vertex> newSourceList = new ArrayList<>(this.sourceList.subList(0, this.sourceList.size() - 1));
         List<Vertex> newTargetList = new ArrayList<>(this.targetList.subList(0, this.targetList.size() - 1));
-        return new Mapping(newMap, newSourceList, newTargetList);
+        return new Mapping(fixedMappings, fixedSourceList, fixedTargetList, newMap, newSourceList, newTargetList);
     }
 
     public Mapping copy() {
         HashBiMap<Vertex, Vertex> newMap = HashBiMap.create(map);
         List<Vertex> newSourceList = new ArrayList<>(this.sourceList);
         List<Vertex> newTargetList = new ArrayList<>(this.targetList);
-        return new Mapping(newMap, newSourceList, newTargetList);
+        return new Mapping(fixedMappings, fixedSourceList, fixedTargetList, newMap, newSourceList, newTargetList);
     }
 
     public Mapping extendMapping(Vertex source, Vertex target) {
@@ -94,27 +131,25 @@ public Mapping extendMapping(Vertex source, Vertex target) {
         newSourceList.add(source);
         List<Vertex> newTargetList = new ArrayList<>(this.targetList);
         newTargetList.add(target);
-        return new Mapping(newMap, newSourceList, newTargetList);
+        return new Mapping(fixedMappings, fixedSourceList, fixedTargetList, newMap, newSourceList, newTargetList);
     }
 
-    public BiMap<Vertex, Vertex> getMap() {
-        return map;
+    public void forEachTarget(Consumer<? super Vertex> action) {
+        for (Vertex t : fixedTargetList) {
+            action.accept(t);
+        }
+        for (Vertex t : targetList) {
+            action.accept(t);
+        }
     }
 
-    @Override
-    public boolean equals(Object o) {
-        if (this == o) {
-            return true;
-        }
-        if (o == null || getClass() != o.getClass()) {
-            return false;
+    public void forEachNonFixedTarget(Consumer<? super Vertex> action) {
+        for (Vertex t : targetList) {
+            action.accept(t);
         }
-        Mapping mapping = (Mapping) o;
-        return Objects.equals(map, mapping.map);
     }
 
-    @Override
-    public int hashCode() {
-        return Objects.hash(map);
+    public void forEachNonFixedSourceAndTarget(BiConsumer<? super Vertex, ? super Vertex> consumer) {
+        map.forEach(consumer);
     }
 }