| /******************************************************************************* |
| * Copyright (c) 2000, 2003 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Common Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/cpl-v10.html |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| *******************************************************************************/ |
| package org.eclipse.compare.structuremergeviewer; |
| |
| import java.io.*; |
| import java.util.*; |
| import java.text.MessageFormat; |
| |
| import org.eclipse.jface.util.Assert; |
| |
| import org.eclipse.core.runtime.CoreException; |
| import org.eclipse.core.runtime.IProgressMonitor; |
| import org.eclipse.core.runtime.OperationCanceledException; |
| |
| import org.eclipse.compare.*; |
| import org.eclipse.compare.internal.Utilities; |
| |
| |
| /** |
| * A generic two-way or three-way differencing engine. |
| * <p> |
| * The engine is used by calling one of the <code>findDifferences</code> methods and passing |
| * in the objects to compare. |
| * The engine calls the following methods on the input objects to perform the compare: |
| * <UL> |
| * <LI><code>getChildren</code>: for enumerating the children of an object (if any), |
| * <LI><code>contentsEqual</code>: for comparing the content of leaf objects, that is, objects without children, |
| * <LI><code>visit</code>: for every pair of compared object the compare result is passed in. |
| * </UL> |
| * Clients may use as is, or subclass to provide a custom implementation for the three hooks. |
| * However the default implementation already deals with the typical case: |
| * <UL> |
| * <LI><code>getChildren</code>: tries to apply the <code>IStructureComparator</code> |
| * interface to enumerate the children, |
| * <LI><code>contentsEqual</code>: tries to apply the <code>IStreamContentAccessor</code> interface |
| * to perform a byte-wise content comparison, |
| * <LI><code>visit</code>: creates a <code>DiffNode</code> for any detected difference between the compared objects and |
| * links it under a parent node effectively creating a tree of differences. |
| * </UL> |
| * The different kind of changes detected by the engine are decoded as follows: |
| * In the two-way case only NO_CHANGE, ADDITION, DELETION, and CHANGE are used. |
| * In the three-way case these constants are bitwise ORed with one of directional constants |
| * LEFT, RIGHT, and CONFLICTING. |
| */ |
| public class Differencer { |
| |
| // The kind of differences. |
| /** |
| * Difference constant (value 0) indicating no difference. |
| */ |
| public static final int NO_CHANGE= 0; |
| /** |
| * Difference constant (value 1) indicating one side was added. |
| */ |
| public static final int ADDITION= 1; |
| /** |
| * Difference constant (value 2) indicating one side was removed. |
| */ |
| public static final int DELETION= 2; |
| /** |
| * Difference constant (value 3) indicating side changed. |
| */ |
| public static final int CHANGE= 3; |
| |
| /** |
| * Bit mask (value 3) for extracting the kind of difference. |
| */ |
| public static final int CHANGE_TYPE_MASK= 3; |
| |
| // The direction of a three-way change. |
| /** |
| * Three-way change constant (value 4) indicating a change on left side. |
| */ |
| public static final int LEFT= 4; |
| |
| /** |
| * Three-way change constant (value 8) indicating a change on right side. |
| */ |
| public static final int RIGHT= 8; |
| |
| /** |
| * Three-way change constant (value 12) indicating a change on left and |
| * right sides. |
| */ |
| public static final int CONFLICTING= 12; |
| |
| /** |
| * Bit mask (value 12) for extracting the direction of a three-way change. |
| */ |
| public static final int DIRECTION_MASK= 12; |
| |
| /** |
| * Constant (value 16) indicating a change on left and |
| * right side (with respect to ancestor) but left and right are identical. |
| */ |
| public static final int PSEUDO_CONFLICT= 16; |
| |
| |
| static class Node { |
| List fChildren; |
| int fCode; |
| Object fAncestor; |
| Object fLeft; |
| Object fRight; |
| |
| Node() { |
| } |
| Node(Node parent, Object ancestor, Object left, Object right) { |
| parent.add(this); |
| fAncestor= ancestor; |
| fLeft= left; |
| fRight= right; |
| } |
| void add(Node child) { |
| if (fChildren == null) |
| fChildren= new ArrayList(); |
| fChildren.add(child); |
| } |
| Object visit(Differencer d, Object parent, int level) { |
| if (fCode == NO_CHANGE) |
| return null; |
| //dump(level); |
| Object data= d.visit(parent, fCode, fAncestor, fLeft, fRight); |
| if (fChildren != null) { |
| Iterator i= fChildren.iterator(); |
| while (i.hasNext()) { |
| Node n= (Node) i.next(); |
| n.visit(d, data, level+1); |
| } |
| } |
| return data; |
| } |
| // private void dump(int level) { |
| // String name= null; |
| // if (fAncestor instanceof ITypedElement) |
| // name= ((ITypedElement)fAncestor).getName(); |
| // if (name == null && fLeft instanceof ITypedElement) |
| // name= ((ITypedElement)fLeft).getName(); |
| // if (name == null && fRight instanceof ITypedElement) |
| // name= ((ITypedElement)fRight).getName(); |
| // if (name == null) |
| // name= "???"; //$NON-NLS-1$ |
| // |
| // for (int i= 0; i < level; i++) |
| // System.out.print(" "); //$NON-NLS-1$ |
| // |
| // System.out.println(getDiffType(fCode) + name); |
| // } |
| |
| // private String getDiffType(int code) { |
| // String dir= " "; //$NON-NLS-1$ |
| // switch (code & DIRECTION_MASK) { |
| // case LEFT: |
| // dir= ">"; //$NON-NLS-1$ |
| // break; |
| // case RIGHT: |
| // dir= "<"; //$NON-NLS-1$ |
| // break; |
| // case CONFLICTING: |
| // dir= "!"; //$NON-NLS-1$ |
| // break; |
| // } |
| // String change= "="; //$NON-NLS-1$ |
| // switch (code & CHANGE_TYPE_MASK) { |
| // case ADDITION: |
| // change= "+"; //$NON-NLS-1$ |
| // break; |
| // case DELETION: |
| // change= "-"; //$NON-NLS-1$ |
| // break; |
| // case CHANGE: |
| // change= "#"; //$NON-NLS-1$ |
| // break; |
| // } |
| // return dir + change + " "; //$NON-NLS-1$ |
| // } |
| } |
| |
| /** |
| * Creates a new differencing engine. |
| */ |
| public Differencer() { |
| } |
| |
| /** |
| * Starts the differencing engine on the three input objects. If threeWay is <code>true</code> a |
| * three-way comparison is performed, otherwise a two-way compare (in the latter case the ancestor argument is ignored). |
| * The progress monitor is passed to the method <code>updateProgress</code> which is called for every node or |
| * leaf compare. The method returns the object that was returned from the top-most call to method <code>visit</code>. |
| * At most two of the ancestor, left, and right parameters are allowed to be <code>null</code>. |
| * |
| * @param threeWay if <code>true</code> a three-way comparison is performed, otherwise a two-way compare |
| * @param pm a progress monitor which is passed to method <code>updateProgress</code> |
| * @param data a client data that is passed to the top-level call to <code>visit</code> |
| * @param ancestor the ancestor object of the compare (may be <code>null</code>) |
| * @param left the left object of the compare |
| * @param right the right object of the compare |
| * @return the object returned from the top most call to method <code>visit</code>, |
| * possibly <code>null</code> |
| */ |
| public Object findDifferences(boolean threeWay, IProgressMonitor pm, Object data, Object ancestor, Object left, Object right) { |
| |
| Node root= new Node(); |
| |
| int code= traverse(threeWay, root, pm, threeWay ? ancestor : null, left, right); |
| |
| if (code != NO_CHANGE) { |
| List l= root.fChildren; |
| if (l.size() > 0) { |
| Node first= (Node)l.get(0); |
| return first.visit(this, data, 0); |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Traverse tree in postorder. |
| */ |
| private int traverse(boolean threeWay, Node parent, IProgressMonitor pm, Object ancestor, Object left, Object right) { |
| |
| Object[] ancestorChildren= getChildren(ancestor); |
| Object[] rightChildren= getChildren(right); |
| Object[] leftChildren= getChildren(left); |
| |
| int code= NO_CHANGE; |
| |
| Node node= new Node(parent, ancestor, left, right); |
| |
| boolean content= true; // we reset this if we have at least one child |
| |
| if (((threeWay && ancestorChildren != null) || !threeWay) |
| && rightChildren != null && leftChildren != null) { |
| // we only recurse down if no leg is null |
| // a node |
| |
| Set allSet= new HashSet(20); |
| Map ancestorSet= null; |
| Map rightSet= null; |
| Map leftSet= null; |
| |
| if (ancestorChildren != null) { |
| ancestorSet= new HashMap(10); |
| for (int i= 0; i < ancestorChildren.length; i++) { |
| Object ancestorChild= ancestorChildren[i]; |
| ancestorSet.put(ancestorChild, ancestorChild); |
| allSet.add(ancestorChild); |
| } |
| } |
| |
| if (rightChildren != null) { |
| rightSet= new HashMap(10); |
| for (int i= 0; i < rightChildren.length; i++) { |
| Object rightChild= rightChildren[i]; |
| rightSet.put(rightChild, rightChild); |
| allSet.add(rightChild); |
| } |
| } |
| |
| if (leftChildren != null) { |
| leftSet= new HashMap(10); |
| for (int i= 0; i < leftChildren.length; i++) { |
| Object leftChild= leftChildren[i]; |
| leftSet.put(leftChild, leftChild); |
| allSet.add(leftChild); |
| } |
| } |
| |
| Iterator e= allSet.iterator(); |
| while (e.hasNext()) { |
| Object keyChild= e.next(); |
| |
| content= false; |
| |
| if (pm != null) { |
| |
| if (pm.isCanceled()) |
| throw new OperationCanceledException(); |
| |
| updateProgress(pm, keyChild); |
| } |
| |
| Object ancestorChild= ancestorSet != null ? ancestorSet.get(keyChild) : null; |
| Object leftChild= leftSet != null ? leftSet.get(keyChild) : null; |
| Object rightChild= rightSet != null ? rightSet.get(keyChild) : null; |
| |
| int c= traverse(threeWay, node, pm, ancestorChild, leftChild, rightChild); |
| |
| if ((c & CHANGE_TYPE_MASK) != NO_CHANGE) { |
| code|= CHANGE; // deletions and additions of child result in a change of the container |
| code|= (c & DIRECTION_MASK); // incoming & outgoing are just ored |
| } |
| } |
| } |
| |
| if (content) // a leaf |
| code= compare(threeWay, ancestor, left, right); |
| |
| node.fCode= code; |
| |
| return code; |
| } |
| |
| /** |
| * Called for every node or leaf comparison. |
| * The differencing engine passes in the input objects of the compare and the result of the compare. |
| * The data object is the value returned from a call to the <code>visit</code> method on the parent input. |
| * It can be considered the "parent" reference and is useful when building a tree. |
| * <p> |
| * The <code>Differencer</code> implementation returns a new |
| * <code>DiffNode</code> which is initialized with the corresponding values. |
| * Subclasses may override. |
| * |
| * @param data object returned from parent call to <code>visit</code>, |
| * possibly <code>null</code> |
| * @param result the result of the compare operation performed on the three inputs |
| * @param ancestor the compare ancestor of the left and right inputs |
| * @param left the left input to the compare |
| * @param right the right input to the compare |
| * @return the result, possibly <code>null</code> |
| */ |
| protected Object visit(Object data, int result, Object ancestor, Object left, Object right) { |
| return new DiffNode((IDiffContainer) data, result, (ITypedElement)ancestor, (ITypedElement)left, (ITypedElement)right); |
| } |
| |
| /** |
| * Performs a 2-way or 3-way compare of the given leaf elements and returns an integer |
| * describing the kind of difference. |
| */ |
| private int compare(boolean threeway, Object ancestor, Object left, Object right) { |
| |
| int description= NO_CHANGE; |
| |
| if (threeway) { |
| if (ancestor == null) { |
| if (left == null) { |
| if (right == null) { |
| Assert.isTrue(false); |
| // shouldn't happen |
| } else { |
| description= RIGHT | ADDITION; |
| } |
| } else { |
| if (right == null) { |
| description= LEFT | ADDITION; |
| } else { |
| description= CONFLICTING | ADDITION; |
| if (contentsEqual(left, right)) |
| description|= PSEUDO_CONFLICT; |
| } |
| } |
| } else { |
| if (left == null) { |
| if (right == null) { |
| description= CONFLICTING | DELETION | PSEUDO_CONFLICT; |
| } else { |
| if (contentsEqual(ancestor, right)) |
| description= LEFT | DELETION; |
| else |
| description= CONFLICTING | CHANGE; |
| } |
| } else { |
| if (right == null) { |
| if (contentsEqual(ancestor, left)) |
| description= RIGHT | DELETION; |
| else |
| description= CONFLICTING | CHANGE; |
| } else { |
| boolean ay= contentsEqual(ancestor, left); |
| boolean am= contentsEqual(ancestor, right); |
| |
| if (ay && am) |
| ; |
| else if (ay && !am) { |
| description= RIGHT | CHANGE; |
| } else if (!ay && am) { |
| description= LEFT | CHANGE; |
| } else { |
| description= CONFLICTING | CHANGE; |
| if (contentsEqual(left, right)) |
| description|= PSEUDO_CONFLICT; |
| } |
| } |
| } |
| } |
| } else { // two way compare ignores ancestor |
| if (left == null) { |
| if (right == null) { |
| Assert.isTrue(false); |
| // shouldn't happen |
| } else { |
| description= ADDITION; |
| } |
| } else { |
| if (right == null) { |
| description= DELETION; |
| } else { |
| if (! contentsEqual(left, right)) |
| description= CHANGE; |
| } |
| } |
| } |
| |
| return description; |
| } |
| |
| /** |
| * Performs a content compare on the two given inputs. |
| * <p> |
| * The <code>Differencer</code> implementation |
| * returns <code>true</code> if both inputs implement <code>IStreamContentAccessor</code> |
| * and their byte contents is identical. Subclasses may override to implement |
| * a different content compare on the given inputs. |
| * </p> |
| * |
| * @param input1 first input to contents compare |
| * @param input2 second input to contents compare |
| * @return <code>true</code> if content is equal |
| */ |
| protected boolean contentsEqual(Object input1, Object input2) { |
| |
| if (input1 == input2) |
| return true; |
| |
| InputStream is1= getStream(input1); |
| InputStream is2= getStream(input2); |
| |
| if (is1 == null && is2 == null) // no byte contents |
| return true; |
| |
| try { |
| if (is1 == null || is2 == null) // only one has contents |
| return false; |
| |
| while (true) { |
| int c1= is1.read(); |
| int c2= is2.read(); |
| if (c1 == -1 && c2 == -1) |
| return true; |
| if (c1 != c2) |
| break; |
| |
| } |
| } catch (IOException ex) { |
| // NeedWork |
| } finally { |
| if (is1 != null) { |
| try { |
| is1.close(); |
| } catch(IOException ex) { |
| // silently ignored |
| } |
| } |
| if (is2 != null) { |
| try { |
| is2.close(); |
| } catch(IOException ex) { |
| // silently ignored |
| } |
| } |
| } |
| return false; |
| } |
| |
| /** |
| * Tries to return an InputStream for the given object. |
| * Returns <code>null</code> if the object not an IStreamContentAccessor |
| * or an error occured. |
| */ |
| private InputStream getStream(Object o) { |
| if (o instanceof IStreamContentAccessor) { |
| try { |
| return ((IStreamContentAccessor)o).getContents(); |
| } catch(CoreException ex) { |
| // NeedWork |
| } |
| } |
| return null; |
| } |
| |
| /** |
| * Returns the children of the given input or <code>null</code> if there are no children. |
| * <p> |
| * The <code>Differencer</code> implementation checks whether the input |
| * implements the <code>IStructureComparator</code> interface. If yes it is used |
| * to return an array containing all children. Otherwise <code>null</code> is returned. |
| * Subclasses may override to implement a different strategy to enumerate children. |
| * </p> |
| * |
| * @param input the object for which to return children |
| */ |
| protected Object[] getChildren(Object input) { |
| if (input instanceof IStructureComparator) |
| return ((IStructureComparator)input).getChildren(); |
| return null; |
| } |
| |
| /** |
| * Called for every leaf or node compare to update progress information. |
| * <p> |
| * The <code>Differencer</code> implementation shows the name of the input object |
| * as a subtask. Subclasses may override. |
| * </p> |
| * |
| * @param progressMonitor the progress monitor for reporting progress |
| * @param node the currently processed non-<code>null</code> node |
| */ |
| protected void updateProgress(IProgressMonitor progressMonitor, Object node) { |
| if (node instanceof ITypedElement) { |
| String name= ((ITypedElement)node).getName(); |
| String fmt= Utilities.getString("Differencer.progressFormat"); //$NON-NLS-1$ |
| String msg= MessageFormat.format(fmt, new String[] { name }); |
| progressMonitor.subTask(msg); |
| //progressMonitor.worked(1); |
| } |
| } |
| } |
| |