diff options
Diffstat (limited to 'bundles/org.eclipse.compare/plugins/org.eclipse.compare/compare/org/eclipse/compare/structuremergeviewer/Differencer.java')
-rw-r--r-- | bundles/org.eclipse.compare/plugins/org.eclipse.compare/compare/org/eclipse/compare/structuremergeviewer/Differencer.java | 526 |
1 files changed, 0 insertions, 526 deletions
diff --git a/bundles/org.eclipse.compare/plugins/org.eclipse.compare/compare/org/eclipse/compare/structuremergeviewer/Differencer.java b/bundles/org.eclipse.compare/plugins/org.eclipse.compare/compare/org/eclipse/compare/structuremergeviewer/Differencer.java deleted file mode 100644 index 047bb2c3d..000000000 --- a/bundles/org.eclipse.compare/plugins/org.eclipse.compare/compare/org/eclipse/compare/structuremergeviewer/Differencer.java +++ /dev/null @@ -1,526 +0,0 @@ -/******************************************************************************* - * Copyright (c) 2000, 2004 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); - } - } -} - |