| /* |
| * Copyright (c) 1998, 2015, 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 NEW_PREFIX = "NEW_"; |
| 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(); |
| |
| if (nodeFrom == null || nodeTo == null) { |
| System.out.println("Unexpected edge : " + from + " -> " + to); |
| } else { |
| InputEdge newEdge = new InputEdge(fromIndex, toIndex, nodeFrom.getId(), nodeTo.getId(), e.getLabel(), e.getType()); |
| 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(); |
| |
| if (nodeFrom == null || nodeTo == null) { |
| System.out.println("Unexpected edge : " + from + " -> " + to); |
| } else { |
| InputEdge newEdge = new InputEdge(fromIndex, toIndex, nodeFrom.getId(), nodeTo.getId(), e.getLabel(), e.getType()); |
| 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(NEW_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(NEW_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); |
| } |
| } |