--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/visualizer/Difference/src/com/sun/hotspot/igv/difference/Difference.java	Tue Feb 07 22:41:09 2012 +0100
@@ -0,0 +1,381 @@
+/*
+ * Copyright (c) 1998, 2008, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.sun.hotspot.igv.difference;
+
+import com.sun.hotspot.igv.data.Properties;
+import com.sun.hotspot.igv.data.*;
+import com.sun.hotspot.igv.data.services.Scheduler;
+import java.util.*;
+import org.openide.util.Lookup;
+
+/**
+ *
+ * @author Thomas Wuerthinger
+ */
+public class Difference {
+
+    public static final String PROPERTY_STATE = "state";
+    public static final String VALUE_NEW = "new";
+    public static final String VALUE_CHANGED = "changed";
+    public static final String VALUE_SAME = "same";
+    public static final String VALUE_DELETED = "deleted";
+    public static final String OLD_PREFIX = "OLD_";
+    public static final String MAIN_PROPERTY = "name";
+    public static final double LIMIT = 100.0;
+    public static final String[] IGNORE_PROPERTIES = new String[]{"idx", "debug_idx"};
+
+    public static InputGraph createDiffGraph(InputGraph a, InputGraph b) {
+        if (a.getGroup() == b.getGroup()) {
+            return createDiffSameGroup(a, b);
+        } else {
+            return createDiff(a, b);
+        }
+    }
+
+    private static InputGraph createDiffSameGroup(InputGraph a, InputGraph b) {
+        Map<Integer, InputNode> keyMapB = new HashMap<>(b.getNodes().size());
+        for (InputNode n : b.getNodes()) {
+            Integer key = n.getId();
+            assert !keyMapB.containsKey(key);
+            keyMapB.put(key, n);
+        }
+
+        Set<NodePair> pairs = new HashSet<>();
+
+        for (InputNode n : a.getNodes()) {
+            Integer key = n.getId();
+
+
+            if (keyMapB.containsKey(key)) {
+                InputNode nB = keyMapB.get(key);
+                pairs.add(new NodePair(n, nB));
+            }
+        }
+
+        return createDiff(a, b, pairs);
+    }
+
+    private static void ensureScheduled(InputGraph a) {
+        if (a.getBlocks().isEmpty()) {
+            Scheduler s = Lookup.getDefault().lookup(Scheduler.class);
+            a.clearBlocks();
+            s.schedule(a);
+            a.ensureNodesInBlocks();
+        }
+    }
+
+    private static InputGraph createDiff(InputGraph a, InputGraph b, Set<NodePair> pairs) {
+        ensureScheduled(a);
+        ensureScheduled(b);
+
+        Group g = new Group(null);
+        g.setMethod(a.getGroup().getMethod());
+        if (a.getGroup() == b.getGroup()) {
+            g.getProperties().add(a.getGroup().getProperties());
+        } else {
+            // copy properties that have the same value in both groups
+            Properties bps = b.getGroup().getProperties();
+            for (Property p : a.getGroup().getProperties()) {
+                String value = p.getValue();
+                if (value != null && value.equals(bps.get(p.getName()))) {
+                    g.getProperties().setProperty(p.getName(), value);
+                }
+            }
+        }
+        g.getProperties().setProperty("name", "Difference");
+        InputGraph graph = new InputGraph(a.getName() + ", " + b.getName());
+        g.addElement(graph);
+
+        Map<InputBlock, InputBlock> blocksMap = new HashMap<>();
+        for (InputBlock blk : a.getBlocks()) {
+            InputBlock diffblk = graph.addBlock(blk.getName());
+            blocksMap.put(blk, diffblk);
+        }
+        for (InputBlock blk : b.getBlocks()) {
+            InputBlock diffblk = graph.getBlock(blk.getName());
+            if (diffblk == null) {
+                diffblk = graph.addBlock(blk.getName());
+            }
+            blocksMap.put(blk, diffblk);
+        }
+
+        // Difference between block edges
+        Set<Pair<String, String>> aEdges = new HashSet<>();
+        for (InputBlockEdge edge : a.getBlockEdges()) {
+            aEdges.add(new Pair<>(edge.getFrom().getName(), edge.getTo().getName()));
+        }
+        for (InputBlockEdge bEdge : b.getBlockEdges()) {
+            InputBlock from = bEdge.getFrom();
+            InputBlock to = bEdge.getTo();
+            Pair<String, String> pair = new Pair<>(from.getName(), to.getName());
+            if (aEdges.contains(pair)) {
+                // same
+                graph.addBlockEdge(blocksMap.get(from), blocksMap.get(to));
+                aEdges.remove(pair);
+            } else {
+                // added
+                InputBlockEdge edge = graph.addBlockEdge(blocksMap.get(from), blocksMap.get(to));
+                edge.setState(InputBlockEdge.State.NEW);
+            }
+        }
+        for (Pair<String, String> deleted : aEdges) {
+            // removed
+            InputBlock from = graph.getBlock(deleted.getLeft());
+            InputBlock to = graph.getBlock(deleted.getRight());
+            InputBlockEdge edge = graph.addBlockEdge(from, to);
+            edge.setState(InputBlockEdge.State.DELETED);
+        }
+
+        Set<InputNode> nodesA = new HashSet<>(a.getNodes());
+        Set<InputNode> nodesB = new HashSet<>(b.getNodes());
+
+        Map<InputNode, InputNode> inputNodeMap = new HashMap<>(pairs.size());
+        for (NodePair p : pairs) {
+            InputNode n = p.getLeft();
+            assert nodesA.contains(n);
+            InputNode nB = p.getRight();
+            assert nodesB.contains(nB);
+
+            nodesA.remove(n);
+            nodesB.remove(nB);
+            InputNode n2 = new InputNode(n);
+            inputNodeMap.put(n, n2);
+            inputNodeMap.put(nB, n2);
+            graph.addNode(n2);
+            InputBlock block = blocksMap.get(a.getBlock(n));
+            block.addNode(n2.getId());
+            markAsChanged(n2, n, nB);
+        }
+
+        for (InputNode n : nodesA) {
+            InputNode n2 = new InputNode(n);
+            graph.addNode(n2);
+            InputBlock block = blocksMap.get(a.getBlock(n));
+            block.addNode(n2.getId());
+            markAsDeleted(n2);
+            inputNodeMap.put(n, n2);
+        }
+
+        int curIndex = 0;
+        for (InputNode n : nodesB) {
+            InputNode n2 = new InputNode(n);
+
+            // Find new ID for node of b, does not change the id property
+            while (graph.getNode(curIndex) != null) {
+                curIndex++;
+            }
+
+            n2.setId(curIndex);
+            graph.addNode(n2);
+            InputBlock block = blocksMap.get(b.getBlock(n));
+            block.addNode(n2.getId());
+            markAsNew(n2);
+            inputNodeMap.put(n, n2);
+        }
+
+        Collection<InputEdge> edgesA = a.getEdges();
+        Collection<InputEdge> edgesB = b.getEdges();
+
+        Set<InputEdge> newEdges = new HashSet<>();
+
+        for (InputEdge e : edgesA) {
+            int from = e.getFrom();
+            int to = e.getTo();
+            InputNode nodeFrom = inputNodeMap.get(a.getNode(from));
+            InputNode nodeTo = inputNodeMap.get(a.getNode(to));
+            char fromIndex = e.getFromIndex();
+            char toIndex = e.getToIndex();
+
+            InputEdge newEdge = new InputEdge(fromIndex, toIndex, nodeFrom.getId(), nodeTo.getId());
+            if (!newEdges.contains(newEdge)) {
+                markAsDeleted(newEdge);
+                newEdges.add(newEdge);
+                graph.addEdge(newEdge);
+            }
+        }
+
+        for (InputEdge e : edgesB) {
+            int from = e.getFrom();
+            int to = e.getTo();
+            InputNode nodeFrom = inputNodeMap.get(b.getNode(from));
+            InputNode nodeTo = inputNodeMap.get(b.getNode(to));
+            char fromIndex = e.getFromIndex();
+            char toIndex = e.getToIndex();
+
+            InputEdge newEdge = new InputEdge(fromIndex, toIndex, nodeFrom.getId(), nodeTo.getId());
+            if (!newEdges.contains(newEdge)) {
+                markAsNew(newEdge);
+                newEdges.add(newEdge);
+                graph.addEdge(newEdge);
+            } else {
+                newEdges.remove(newEdge);
+                graph.removeEdge(newEdge);
+                markAsSame(newEdge);
+                newEdges.add(newEdge);
+                graph.addEdge(newEdge);
+            }
+        }
+
+        return graph;
+    }
+
+    private static class NodePair extends Pair<InputNode, InputNode> {
+
+
+        public NodePair(InputNode n1, InputNode n2) {
+            super(n1, n2);
+        }
+
+        public double getValue() {
+
+            double result = 0.0;
+            for (Property p : getLeft().getProperties()) {
+                double faktor = 1.0;
+                for (String forbidden : IGNORE_PROPERTIES) {
+                    if (p.getName().equals(forbidden)) {
+                        faktor = 0.1;
+                        break;
+                    }
+                }
+                String p2 = getRight().getProperties().get(p.getName());
+                result += evaluate(p.getValue(), p2) * faktor;
+            }
+
+            return result;
+        }
+
+        private double evaluate(String p, String p2) {
+            if (p2 == null) {
+                return 1.0;
+            }
+            if (p.equals(p2)) {
+                return 0.0;
+            } else {
+                return (double) (Math.abs(p.length() - p2.length())) / p.length() + 0.5;
+            }
+        }
+    }
+
+    private static InputGraph createDiff(InputGraph a, InputGraph b) {
+
+        Set<InputNode> matched = new HashSet<>();
+
+        Set<NodePair> pairs = new HashSet<>();
+        for (InputNode n : a.getNodes()) {
+            String s = n.getProperties().get(MAIN_PROPERTY);
+            if (s == null) {
+                s = "";
+            }
+            for (InputNode n2 : b.getNodes()) {
+                String s2 = n2.getProperties().get(MAIN_PROPERTY);
+                if (s2 == null) {
+                    s2 = "";
+                }
+
+                if (s.equals(s2)) {
+                    NodePair p = new NodePair(n, n2);
+                    pairs.add(p);
+                }
+            }
+        }
+
+        Set<NodePair> selectedPairs = new HashSet<>();
+        while (pairs.size() > 0) {
+
+            double min = Double.MAX_VALUE;
+            NodePair minPair = null;
+            for (NodePair p : pairs) {
+                double cur = p.getValue();
+                if (cur < min) {
+                    minPair = p;
+                    min = cur;
+                }
+            }
+
+            if (min > LIMIT) {
+                break;
+            } else {
+                selectedPairs.add(minPair);
+
+                Set<NodePair> toRemove = new HashSet<>();
+                for (NodePair p : pairs) {
+                    if (p.getLeft() == minPair.getLeft() || p.getRight() == minPair.getRight()) {
+                        toRemove.add(p);
+                    }
+                }
+                pairs.removeAll(toRemove);
+            }
+        }
+
+        return createDiff(a, b, selectedPairs);
+    }
+
+    private static void markAsNew(InputEdge e) {
+        e.setState(InputEdge.State.NEW);
+    }
+
+    private static void markAsDeleted(InputEdge e) {
+        e.setState(InputEdge.State.DELETED);
+
+    }
+
+    private static void markAsSame(InputEdge e) {
+        e.setState(InputEdge.State.SAME);
+    }
+
+    private static void markAsChanged(InputNode n, InputNode firstNode, InputNode otherNode) {
+
+        boolean difference = false;
+        for (Property p : otherNode.getProperties()) {
+            String s = firstNode.getProperties().get(p.getName());
+            if (!p.getValue().equals(s)) {
+                difference = true;
+                n.getProperties().setProperty(OLD_PREFIX + p.getName(), p.getValue());
+            }
+        }
+
+        for (Property p : firstNode.getProperties()) {
+            String s = otherNode.getProperties().get(p.getName());
+            if (s == null && p.getValue().length() > 0) {
+                difference = true;
+                n.getProperties().setProperty(OLD_PREFIX + p.getName(), "");
+            }
+        }
+
+        if (difference) {
+            n.getProperties().setProperty(PROPERTY_STATE, VALUE_CHANGED);
+        } else {
+            n.getProperties().setProperty(PROPERTY_STATE, VALUE_SAME);
+        }
+    }
+
+    private static void markAsDeleted(InputNode n) {
+        n.getProperties().setProperty(PROPERTY_STATE, VALUE_DELETED);
+    }
+
+    private static void markAsNew(InputNode n) {
+        n.getProperties().setProperty(PROPERTY_STATE, VALUE_NEW);
+    }
+}