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 | 515 |
1 files changed, 0 insertions, 515 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 e8c8ab369..000000000 --- a/bundles/org.eclipse.compare/plugins/org.eclipse.compare/compare/org/eclipse/compare/structuremergeviewer/Differencer.java +++ /dev/null @@ -1,515 +0,0 @@ -/*
- * (c) Copyright IBM Corp. 2000, 2001.
- * All Rights Reserved.
- */
-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) {
- } finally {
- if (is1 != null) {
- try {
- is1.close();
- } catch(IOException ex) {
- }
- }
- if (is2 != null) {
- 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)
- 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
- * @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();
- String fmt= Utilities.getString("Differencer.progressFormat"); //$NON-NLS-1$
- String msg= MessageFormat.format(fmt, new String[] { name });
- progressMonitor.subTask(msg);
- //progressMonitor.worked(1);
- }
- }
-}
-
|