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 | 511 |
1 files changed, 511 insertions, 0 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 new file mode 100644 index 000000000..01ea51cc9 --- /dev/null +++ b/bundles/org.eclipse.compare/plugins/org.eclipse.compare/compare/org/eclipse/compare/structuremergeviewer/Differencer.java @@ -0,0 +1,511 @@ +/*
+ * Licensed Materials - Property of IBM,
+ * WebSphere Studio Workbench
+ * (c) Copyright IBM Corp 2000, 2001
+ */
+package org.eclipse.compare.structuremergeviewer;
+
+import java.io.*;
+import java.util.*;
+
+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.*;
+
+
+/**
+ * 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= "???";
+
+ for (int i= 0; i < level; i++)
+ System.out.print(" ");
+
+ System.out.println(getDiffType(fCode) + name);
+ }
+ private String getDiffType(int code) {
+ String dir= " ";
+ switch (code & DIRECTION_MASK) {
+ case LEFT:
+ dir= ">";
+ break;
+ case RIGHT:
+ dir= "<";
+ break;
+ case CONFLICTING:
+ dir= "!";
+ break;
+ }
+ String change= "=";
+ switch (code & CHANGE_TYPE_MASK) {
+ case ADDITION:
+ change= "+";
+ break;
+ case DELETION:
+ change= "-";
+ break;
+ case CHANGE:
+ change= "#";
+ break;
+ }
+ return dir + change + " ";
+ }
+ }
+
+ /**
+ * 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("Compare cancelled");
+
+ 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;
+
+ if (is1 == null || is2 == null) // only one has contents
+ return false;
+
+ try {
+ while (true) {
+ int c1= is1.read();
+ int c2= is2.read();
+ if (c1 == -1 && c2 == -1)
+ return true;
+ if (c1 != c2)
+ break;
+
+ }
+ } catch (IOException ex) {
+ } finally {
+ try {
+ is1.close();
+ } catch(IOException ex) {
+ }
+ try {
+ is2.close();
+ } catch(IOException ex) {
+ }
+ }
+ 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) {
+ }
+ }
+ 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) {
+ Object[] children= ((IStructureComparator)input).getChildren();
+ if (children != null && children.length > 0)
+ return children;
+ }
+ 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
+ * @name input a non-<code>null</code> input object
+ */
+ protected void updateProgress(IProgressMonitor progressMonitor, Object node) {
+ if (node instanceof ITypedElement) {
+ String name= ((ITypedElement)node).getName();
+ progressMonitor.subTask("Comparing " + name);
+ //progressMonitor.worked(1);
+ }
+ }
+}
+
|