Java > Open Source Codes > org > eclipse > compare > structuremergeviewer > Differencer


1 /*******************************************************************************
2  * Copyright (c) 2000, 2007 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.compare.structuremergeviewer;
12
13 import java.io.*;
14 import java.util.ArrayList ;
15 import java.util.HashMap ;
16 import java.util.HashSet ;
17 import java.util.Iterator ;
18 import java.util.List ;
19 import java.util.Map ;
20 import java.util.Set ;
21 import com.ibm.icu.text.MessageFormat;
22
23 import org.eclipse.jface.util.Assert;
24
25 import org.eclipse.core.runtime.CoreException;
26 import org.eclipse.core.runtime.IProgressMonitor;
27 import org.eclipse.core.runtime.OperationCanceledException;
28
29 import org.eclipse.compare.*;
30 import org.eclipse.compare.internal.Utilities;
31
32
33 /**
34  * A generic two-way or three-way differencing engine.
35  * <p>
36  * The engine is used by calling one of the <code>findDifferences</code> methods and passing
37  * in the objects to compare.
38  * The engine calls the following methods on the input objects to perform the compare:
39  * <UL>
40  * <LI><code>getChildren</code>: for enumerating the children of an object (if any),
41  * <LI><code>contentsEqual</code>: for comparing the content of leaf objects, that is, objects without children,
42  * <LI><code>visit</code>: for every pair of compared object the compare result is passed in.
43  * </UL>
44  * Clients may use as is, or subclass to provide a custom implementation for the three hooks.
45  * However the default implementation already deals with the typical case:
46  * <UL>
47  * <LI><code>getChildren</code>: tries to apply the <code>IStructureComparator</code>
48  * interface to enumerate the children,
49  * <LI><code>contentsEqual</code>: tries to apply the <code>IStreamContentAccessor</code> interface
50  * to perform a byte-wise content comparison,
51  * <LI><code>visit</code>: creates a <code>DiffNode</code> for any detected difference between the compared objects and
52  * links it under a parent node effectively creating a tree of differences.
53  * </UL>
54  * The different kind of changes detected by the engine are decoded as follows:
55  * In the two-way case only NO_CHANGE, ADDITION, DELETION, and CHANGE are used.
56  * In the three-way case these constants are bitwise ORed with one of directional constants
57  * LEFT, RIGHT, and CONFLICTING.
58  */
59 public class Differencer {
60     
61     // The kind of differences.
62 /**
63      * Difference constant (value 0) indicating no difference.
64      */
65     public static final int NO_CHANGE= 0;
66     /**
67      * Difference constant (value 1) indicating one side was added.
68      */
69     public static final int ADDITION= 1;
70     /**
71      * Difference constant (value 2) indicating one side was removed.
72      */
73     public static final int DELETION= 2;
74     /**
75      * Difference constant (value 3) indicating side changed.
76      */
77     public static final int CHANGE= 3;
78
79     /**
80      * Bit mask (value 3) for extracting the kind of difference.
81      */
82     public static final int CHANGE_TYPE_MASK= 3;
83
84     // The direction of a three-way change.
85 /**
86      * Three-way change constant (value 4) indicating a change on left side.
87      */
88     public static final int LEFT= 4;
89     
90     /**
91      * Three-way change constant (value 8) indicating a change on right side.
92      */
93     public static final int RIGHT= 8;
94     
95     /**
96      * Three-way change constant (value 12) indicating a change on left and
97      * right sides.
98      */
99     public static final int CONFLICTING= 12;
100
101     /**
102      * Bit mask (value 12) for extracting the direction of a three-way change.
103      */
104     public static final int DIRECTION_MASK= 12;
105
106     /**
107      * Constant (value 16) indicating a change on left and
108      * right side (with respect to ancestor) but left and right are identical.
109      */
110     public static final int PSEUDO_CONFLICT= 16;
111
112     
113     static class Node {
114         List fChildren;
115         int fCode;
116         Object fAncestor;
117         Object fLeft;
118         Object fRight;
119         
120         Node() {
121             // nothing to do
122 }
123         Node(Node parent, Object ancestor, Object left, Object right) {
124             parent.add(this);
125             fAncestor= ancestor;
126             fLeft= left;
127             fRight= right;
128         }
129         void add(Node child) {
130             if (fChildren == null)
131                 fChildren= new ArrayList ();
132             fChildren.add(child);
133         }
134         Object visit(Differencer d, Object parent, int level) {
135             if (fCode == NO_CHANGE)
136                 return null;
137             //dump(level);
138 Object data= d.visit(parent, fCode, fAncestor, fLeft, fRight);
139             if (fChildren != null) {
140                 Iterator i= fChildren.iterator();
141                 while (i.hasNext()) {
142                     Node n= (Node) i.next();
143                     n.visit(d, data, level+1);
144                 }
145             }
146             return data;
147         }
148 // private void dump(int level) {
149 // String name= null;
150 // if (fAncestor instanceof ITypedElement)
151 // name= ((ITypedElement)fAncestor).getName();
152 // if (name == null && fLeft instanceof ITypedElement)
153 // name= ((ITypedElement)fLeft).getName();
154 // if (name == null && fRight instanceof ITypedElement)
155 // name= ((ITypedElement)fRight).getName();
156 // if (name == null)
157 // name= "???"; //$NON-NLS-1$
158 //
159 // for (int i= 0; i < level; i++)
160 // System.out.print(" "); //$NON-NLS-1$
161 //
162 // System.out.println(getDiffType(fCode) + name);
163 // }
164
165 // private String getDiffType(int code) {
166 // String dir= " "; //$NON-NLS-1$
167 // switch (code & DIRECTION_MASK) {
168 // case LEFT:
169 // dir= ">"; //$NON-NLS-1$
170 // break;
171 // case RIGHT:
172 // dir= "<"; //$NON-NLS-1$
173 // break;
174 // case CONFLICTING:
175 // dir= "!"; //$NON-NLS-1$
176 // break;
177 // }
178 // String change= "="; //$NON-NLS-1$
179 // switch (code & CHANGE_TYPE_MASK) {
180 // case ADDITION:
181 // change= "+"; //$NON-NLS-1$
182 // break;
183 // case DELETION:
184 // change= "-"; //$NON-NLS-1$
185 // break;
186 // case CHANGE:
187 // change= "#"; //$NON-NLS-1$
188 // break;
189 // }
190 // return dir + change + " "; //$NON-NLS-1$
191 // }
192 }
193     
194     /**
195      * Creates a new differencing engine.
196      */
197     public Differencer() {
198         // nothing to do
199 }
200     
201     /**
202      * Starts the differencing engine on the three input objects. If threeWay is <code>true</code> a
203      * three-way comparison is performed, otherwise a two-way compare (in the latter case the ancestor argument is ignored).
204      * The progress monitor is passed to the method <code>updateProgress</code> which is called for every node or
205      * leaf compare. The method returns the object that was returned from the top-most call to method <code>visit</code>.
206      * At most two of the ancestor, left, and right parameters are allowed to be <code>null</code>.
207      *
208      * @param threeWay if <code>true</code> a three-way comparison is performed, otherwise a two-way compare
209      * @param pm a progress monitor which is passed to method <code>updateProgress</code>
210      * @param data a client data that is passed to the top-level call to <code>visit</code>
211      * @param ancestor the ancestor object of the compare (may be <code>null</code>)
212      * @param left the left object of the compare
213      * @param right the right object of the compare
214      * @return the object returned from the top most call to method <code>visit</code>,
215      * possibly <code>null</code>
216      */
217     public Object findDifferences(boolean threeWay, IProgressMonitor pm, Object data, Object ancestor, Object left, Object right) {
218         
219         Node root= new Node();
220         
221         int code= traverse(threeWay, root, pm, threeWay ? ancestor : null, left, right);
222                 
223         if (code != NO_CHANGE) {
224             List l= root.fChildren;
225             if (l.size() > 0) {
226                 Node first= (Node)l.get(0);
227                 return first.visit(this, data, 0);
228             }
229         }
230         return null;
231     }
232     
233     /*
234      * Traverse tree in postorder.
235      */
236     private int traverse(boolean threeWay, Node parent, IProgressMonitor pm, Object ancestor, Object left, Object right) {
237                 
238         Object [] ancestorChildren= getChildren(ancestor);
239         Object [] rightChildren= getChildren(right);
240         Object [] leftChildren= getChildren(left);
241         
242         int code= NO_CHANGE;
243         
244         Node node= new Node(parent, ancestor, left, right);
245             
246         boolean content= true; // we reset this if we have at least one child
247
248         if (((threeWay && ancestorChildren != null) || !threeWay)
249                      && rightChildren != null && leftChildren != null) {
250             // we only recurse down if no leg is null
251 // a node
252
253             Set allSet= new HashSet (20);
254             Map ancestorSet= null;
255             Map rightSet= null;
256             Map leftSet= null;
257                         
258             if (ancestorChildren != null) {
259                 ancestorSet= new HashMap (10);
260                 for (int i= 0; i < ancestorChildren.length; i++) {
261                     Object ancestorChild= ancestorChildren[i];
262                     ancestorSet.put(ancestorChild, ancestorChild);
263                     allSet.add(ancestorChild);
264                 }
265             }
266
267             if (rightChildren != null) {
268                 rightSet= new HashMap (10);
269                 for (int i= 0; i < rightChildren.length; i++) {
270                     Object rightChild= rightChildren[i];
271                     rightSet.put(rightChild, rightChild);
272                     allSet.add(rightChild);
273                 }
274             }
275
276             if (leftChildren != null) {
277                 leftSet= new HashMap (10);
278                 for (int i= 0; i < leftChildren.length; i++) {
279                     Object leftChild= leftChildren[i];
280                     leftSet.put(leftChild, leftChild);
281                     allSet.add(leftChild);
282                 }
283             }
284                         
285             Iterator e= allSet.iterator();
286             while (e.hasNext()) {
287                 Object keyChild= e.next();
288                 
289                 if (pm != null) {
290                     
291                     if (pm.isCanceled())
292                         throw new OperationCanceledException();
293                         
294                     updateProgress(pm, keyChild);
295                 }
296                 
297                 Object ancestorChild= ancestorSet != null ? ancestorSet.get(keyChild) : null;
298                 Object leftChild= leftSet != null ? leftSet.get(keyChild) : null;
299                 Object rightChild= rightSet != null ? rightSet.get(keyChild) : null;
300                 
301                 int c= traverse(threeWay, node, pm, ancestorChild, leftChild, rightChild);
302             
303                 if ((c & CHANGE_TYPE_MASK) != NO_CHANGE) {
304                     code|= CHANGE; // deletions and additions of child result in a change of the container
305 code|= (c & DIRECTION_MASK); // incoming & outgoing are just ored
306 content= false;
307                 }
308             }
309         }
310
311         if (content) // a leaf
312 code= compare(threeWay, ancestor, left, right);
313                                 
314         node.fCode= code;
315                             
316         return code;
317     }
318     
319     /**
320      * Called for every node or leaf comparison.
321      * The differencing engine passes in the input objects of the compare and the result of the compare.
322      * The data object is the value returned from a call to the <code>visit</code> method on the parent input.
323      * It can be considered the "parent" reference and is useful when building a tree.
324      * <p>
325      * The <code>Differencer</code> implementation returns a new
326      * <code>DiffNode</code> which is initialized with the corresponding values.
327      * Subclasses may override.
328      *
329      * @param data object returned from parent call to <code>visit</code>,
330      * possibly <code>null</code>
331      * @param result the result of the compare operation performed on the three inputs
332      * @param ancestor the compare ancestor of the left and right inputs
333      * @param left the left input to the compare
334      * @param right the right input to the compare
335      * @return the result, possibly <code>null</code>
336      */
337     protected Object visit(Object data, int result, Object ancestor, Object left, Object right) {
338         return new DiffNode((IDiffContainer) data, result, (ITypedElement)ancestor, (ITypedElement)left, (ITypedElement)right);
339     }
340     
341     /*
342      * Performs a 2-way or 3-way compare of the given leaf elements and returns an integer
343      * describing the kind of difference.
344      */
345     private int compare(boolean threeway, Object ancestor, Object left, Object right) {
346         
347         int description= NO_CHANGE;
348         
349         if (threeway) {
350             if (ancestor == null) {
351                 if (left == null) {
352                     if (right == null) {
353                         Assert.isTrue(false);
354                         // shouldn't happen
355 } else {
356                         description= RIGHT | ADDITION;
357                     }
358                 } else {
359                     if (right == null) {
360                         description= LEFT | ADDITION;
361                     } else {
362                         description= CONFLICTING | ADDITION;
363                         if (contentsEqual(left, right))
364                             description|= PSEUDO_CONFLICT;
365                     }
366                 }
367             } else {
368                 if (left == null) {
369                     if (right == null) {
370                         description= CONFLICTING | DELETION | PSEUDO_CONFLICT;
371                     } else {
372                         if (contentsEqual(ancestor, right))
373                             description= LEFT | DELETION;
374                         else
375                             description= CONFLICTING | CHANGE;
376                     }
377                 } else {
378                     if (right == null) {
379                         if (contentsEqual(ancestor, left))
380                             description= RIGHT | DELETION;
381                         else
382                             description= CONFLICTING | CHANGE;
383                     } else {
384                         boolean ay= contentsEqual(ancestor, left);
385                         boolean am= contentsEqual(ancestor, right);
386                         
387                         if (ay && am) {
388                             // empty
389 } else if (ay && !am) {
390                             description= RIGHT | CHANGE;
391                         } else if (!ay && am) {
392                             description= LEFT | CHANGE;
393                         } else {
394                             description= CONFLICTING | CHANGE;
395                             if (contentsEqual(left, right))
396                                 description|= PSEUDO_CONFLICT;
397                         }
398                     }
399                 }
400             }
401         } else { // two way compare ignores ancestor
402 if (left == null) {
403                 if (right == null) {
404                     Assert.isTrue(false);
405                     // shouldn't happen
406 } else {
407                     description= ADDITION;
408                 }
409             } else {
410                 if (right == null) {
411                     description= DELETION;
412                 } else {
413                     if (! contentsEqual(left, right))
414                         description= CHANGE;
415                 }
416             }
417         }
418                             
419         return description;
420     }
421         
422     /**
423      * Performs a content compare on the two given inputs.
424      * <p>
425      * The <code>Differencer</code> implementation
426      * returns <code>true</code> if both inputs implement <code>IStreamContentAccessor</code>
427      * and their byte contents is identical. Subclasses may override to implement
428      * a different content compare on the given inputs.
429      * </p>
430      *
431      * @param input1 first input to contents compare
432      * @param input2 second input to contents compare
433      * @return <code>true</code> if content is equal
434      */
435     protected boolean contentsEqual(Object input1, Object input2) {
436         
437         if (input1 == input2)
438             return true;
439             
440         InputStream is1= getStream(input1);
441         InputStream is2= getStream(input2);
442         
443         if (is1 == null && is2 == null) // no byte contents
444 return true;
445         
446         try {
447             if (is1 == null || is2 == null) // only one has contents
448 return false;
449             
450             while (true) {
451                 int c1= is1.read();
452                 int c2= is2.read();
453                 if (c1 == -1 && c2 == -1)
454                     return true;
455                 if (c1 != c2)
456                     break;
457                 
458             }
459         } catch (IOException ex) {
460             // NeedWork
461 } finally {
462             if (is1 != null) {
463                 try {
464                     is1.close();
465                 } catch(IOException ex) {
466                     // silently ignored
467 }
468             }
469             if (is2 != null) {
470                 try {
471                     is2.close();
472                 } catch(IOException ex) {
473                     // silently ignored
474 }
475             }
476         }
477         return false;
478     }
479     
480     /*
481      * Tries to return an InputStream for the given object.
482      * Returns <code>null</code> if the object not an IStreamContentAccessor
483      * or an error occurred.
484      */
485     private InputStream getStream(Object o) {
486         if (o instanceof IStreamContentAccessor) {
487             try {
488                 return ((IStreamContentAccessor)o).getContents();
489             } catch(CoreException ex) {
490                 // NeedWork
491 }
492         }
493         return null;
494     }
495     
496     /**
497      * Returns the children of the given input or <code>null</code> if there are no children.
498      * <p>
499      * The <code>Differencer</code> implementation checks whether the input
500      * implements the <code>IStructureComparator</code> interface. If yes it is used
501      * to return an array containing all children. Otherwise <code>null</code> is returned.
502      * Subclasses may override to implement a different strategy to enumerate children.
503      * </p>
504      *
505      * @param input the object for which to return children
506      * @return the children of the given input or <code>null</code> if there are no children.
507      */
508     protected Object [] getChildren(Object input) {
509         if (input instanceof IStructureComparator)
510             return ((IStructureComparator)input).getChildren();
511         return null;
512     }
513     
514     /**
515      * Called for every leaf or node compare to update progress information.
516      * <p>
517      * The <code>Differencer</code> implementation shows the name of the input object
518      * as a subtask. Subclasses may override.
519      * </p>
520      *
521      * @param progressMonitor the progress monitor for reporting progress
522      * @param node the currently processed non-<code>null</code> node
523      */
524     protected void updateProgress(IProgressMonitor progressMonitor, Object node) {
525         if (node instanceof ITypedElement) {
526             String name= ((ITypedElement)node).getName();
527             String fmt= Utilities.getString("Differencer.progressFormat"); //$NON-NLS-1$
528 String msg= MessageFormat.format(fmt, new String [] { name });
529             progressMonitor.subTask(msg);
530             //progressMonitor.worked(1);
531 }
532     }
533 }
534
535

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags