Java > Open Source Codes > org > eclipse > jdt > internal > debug > core > hcr > Differencer


1 /*******************************************************************************
2  * Copyright (c) 2000, 2003 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Common Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/cpl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.jdt.internal.debug.core.hcr;
12
13  
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
22 import org.eclipse.core.runtime.IProgressMonitor;
23 import org.eclipse.core.runtime.OperationCanceledException;
24
25 /**
26  * A generic two-way or three-way differencing engine.
27  * <p>
28  * The engine is used by calling one of the <code>findDifferences</code> methods and passing
29  * in the objects to compare.
30  * The engine calls the following methods on the input objects to perform the compare:
31  * <UL>
32  * <LI><code>getChildren</code>: for enumerating the children of an object (if any),
33  * <LI><code>contentsEqual</code>: for comparing the content of leaf objects, that is, objects without children,
34  * <LI><code>visit</code>: for every pair of compared object the compare result is passed in.
35  * </UL>
36  * Clients may use as is, or subclass to provide a custom implementation for the three hooks.
37  * However the default implementation already deals with the typical case:
38  * <UL>
39  * <LI><code>getChildren</code>: tries to apply the <code>IStructureComparator</code>
40  * interface to enumerate the children,
41  * <LI><code>contentsEqual</code>: tries to apply the <code>IStreamContentAccessor</code> interface
42  * to perform a byte-wise content comparison,
43  * <LI><code>visit</code>: creates a <code>DiffNode</code> for any detected difference between the compared objects and
44  * links it under a parent node effectively creating a tree of differences.
45  * </UL>
46  * The different kind of changes detected by the engine are decoded as follows:
47  * In the two-way case only NO_CHANGE, ADDITION, DELETION, and CHANGE are used.
48  * In the three-way case these constants are bitwise ORed with one of directional constants
49  * LEFT, RIGHT, and CONFLICTING.
50  */
51 abstract class Differencer {
52     
53     // The kind of differences.
54 /**
55      * Difference constant (value 0) indicating no difference.
56      */
57     public static final int NO_CHANGE= 0;
58     /**
59      * Difference constant (value 1) indicating one side was added.
60      */
61     public static final int ADDITION= 1;
62     /**
63      * Difference constant (value 2) indicating one side was removed.
64      */
65     public static final int DELETION= 2;
66     /**
67      * Difference constant (value 3) indicating side changed.
68      */
69     public static final int CHANGE= 3;
70
71     /**
72      * Bit mask (value 3) for extracting the kind of difference.
73      */
74     public static final int CHANGE_TYPE_MASK= 3;
75
76     // The direction of a three-way change.
77 /**
78      * Three-way change constant (value 4) indicating a change on left side.
79      */
80     public static final int LEFT= 4;
81     
82     /**
83      * Three-way change constant (value 8) indicating a change on right side.
84      */
85     public static final int RIGHT= 8;
86     
87     /**
88      * Three-way change constant (value 12) indicating a change on left and
89      * right sides.
90      */
91     public static final int CONFLICTING= 12;
92
93     /**
94      * Bit mask (value 12) for extracting the direction of a three-way change.
95      */
96     public static final int DIRECTION_MASK= 12;
97
98     /**
99      * Constant (value 16) indicating a change on left and
100      * right side (with respect to ancestor) but left and right are identical.
101      */
102     public static final int PSEUDO_CONFLICT= 16;
103
104     
105     static class Node {
106         List fChildren;
107         int fCode;
108         Object fAncestor;
109         Object fLeft;
110         Object fRight;
111         
112         Node() {
113         }
114         Node(Node parent, Object ancestor, Object left, Object right) {
115             parent.add(this);
116             fAncestor= ancestor;
117             fLeft= left;
118             fRight= right;
119         }
120         void add(Node child) {
121             if (fChildren == null)
122                 fChildren= new ArrayList ();
123             fChildren.add(child);
124         }
125         Object visit(Differencer d, Object parent, int level) {
126             if (fCode == NO_CHANGE)
127                 return null;
128             //dump(level);
129 Object data= d.visit(parent, fCode, fAncestor, fLeft, fRight);
130             if (fChildren != null) {
131                 Iterator i= fChildren.iterator();
132                 while (i.hasNext()) {
133                     Node n= (Node) i.next();
134                     n.visit(d, data, level+1);
135                 }
136             }
137             return data;
138         }
139     }
140     
141     /**
142      * Creates a new differencing engine.
143      */
144     public Differencer() {
145     }
146     
147     /**
148      * Starts the differencing engine on the three input objects. If threeWay is <code>true</code> a
149      * three-way comparison is performed, otherwise a two-way compare (in the latter case the ancestor argument is ignored).
150      * The progress monitor is passed to the method <code>updateProgress</code> which is called for every node or
151      * leaf compare. The method returns the object that was returned from the top-most call to method <code>visit</code>.
152      * At most two of the ancestor, left, and right parameters are allowed to be <code>null</code>.
153      *
154      * @param threeWay if <code>true</code> a three-way comparison is performed, otherwise a two-way compare
155      * @param pm a progress monitor which is passed to method <code>updateProgress</code>
156      * @param data a client data that is passed to the top-level call to <code>visit</code>
157      * @param ancestor the ancestor object of the compare (may be <code>null</code>)
158      * @param left the left object of the compare
159      * @param right the right object of the compare
160      * @return the object returned from the top most call to method <code>visit</code>,
161      * possibly <code>null</code>
162      */
163     public Object findDifferences(boolean threeWay, IProgressMonitor pm, Object data, Object ancestor, Object left, Object right) {
164         
165         Node root= new Node();
166         
167         int code= traverse(threeWay, root, pm, threeWay ? ancestor : null, left, right);
168                 
169         if (code != NO_CHANGE) {
170             List l= root.fChildren;
171             if (l.size() > 0) {
172                 Node first= (Node)l.get(0);
173                 return first.visit(this, data, 0);
174             }
175         }
176         return null;
177     }
178     
179     /**
180      * Traverse tree in postorder.
181      */
182     private int traverse(boolean threeWay, Node parent, IProgressMonitor pm, Object ancestor, Object left, Object right) {
183                 
184         Object [] ancestorChildren= getChildren(ancestor);
185         Object [] rightChildren= getChildren(right);
186         Object [] leftChildren= getChildren(left);
187         
188         int code= NO_CHANGE;
189         
190         Node node= new Node(parent, ancestor, left, right);
191             
192         boolean content= true; // we reset this if we have at least one child
193
194         if (((threeWay && ancestorChildren != null) || !threeWay)
195                      && rightChildren != null && leftChildren != null) {
196             // we only recurse down if no leg is null
197 // a node
198
199             Set allSet= new HashSet (20);
200             Map ancestorSet= null;
201             Map rightSet= null;
202             Map leftSet= null;
203                         
204             if (ancestorChildren != null) {
205                 ancestorSet= new HashMap (10);
206                 for (int i= 0; i < ancestorChildren.length; i++) {
207                     Object ancestorChild= ancestorChildren[i];
208                     ancestorSet.put(ancestorChild, ancestorChild);
209                     allSet.add(ancestorChild);
210                 }
211             }
212
213             if (rightChildren != null) {
214                 rightSet= new HashMap (10);
215                 for (int i= 0; i < rightChildren.length; i++) {
216                     Object rightChild= rightChildren[i];
217                     rightSet.put(rightChild, rightChild);
218                     allSet.add(rightChild);
219                 }
220             }
221
222             if (leftChildren != null) {
223                 leftSet= new HashMap (10);
224                 for (int i= 0; i < leftChildren.length; i++) {
225                     Object leftChild= leftChildren[i];
226                     leftSet.put(leftChild, leftChild);
227                     allSet.add(leftChild);
228                 }
229             }
230                         
231             Iterator e= allSet.iterator();
232             while (e.hasNext()) {
233                 Object keyChild= e.next();
234                 
235                 content= false;
236                 
237                 if (pm != null) {
238                     
239                     if (pm.isCanceled())
240                         throw new OperationCanceledException();
241                 }
242                 
243                 Object ancestorChild= ancestorSet != null ? ancestorSet.get(keyChild) : null;
244                 Object leftChild= leftSet != null ? leftSet.get(keyChild) : null;
245                 Object rightChild= rightSet != null ? rightSet.get(keyChild) : null;
246                 
247                 int c= traverse(threeWay, node, pm, ancestorChild, leftChild, rightChild);
248             
249                 if ((c & CHANGE_TYPE_MASK) != NO_CHANGE) {
250                     code|= CHANGE; // deletions and additions of child result in a change of the container
251 code|= (c & DIRECTION_MASK); // incoming & outgoing are just ored
252 }
253             }
254         }
255
256         if (content) // a leaf
257 code= compare(threeWay, ancestor, left, right);
258                                 
259         node.fCode= code;
260                             
261         return code;
262     }
263     
264     /**
265      * Called for every node or leaf comparison.
266      * The differencing engine passes in the input objects of the compare and the result of the compare.
267      * The data object is the value returned from a call to the <code>visit</code> method on the parent input.
268      * It can be considered the "parent" reference and is useful when building a tree.
269      * <p>
270      * The <code>Differencer</code> implementation returns a new
271      * <code>DiffNode</code> which is initialized with the corresponding values.
272      * Subclasses may override.
273      *
274      * @param data object returned from parent call to <code>visit</code>,
275      * possibly <code>null</code>
276      * @param result the result of the compare operation performed on the three inputs
277      * @param ancestor the compare ancestor of the left and right inputs
278      * @param left the left input to the compare
279      * @param right the right input to the compare
280      * @return the result, possibly <code>null</code>
281      */
282     abstract protected Object visit(Object data, int result, Object ancestor, Object left, Object right);
283     
284     /**
285      * Performs a 2-way or 3-way compare of the given leaf elements and returns an integer
286      * describing the kind of difference.
287      */
288     private int compare(boolean threeway, Object ancestor, Object left, Object right) {
289         
290         int description= NO_CHANGE;
291         
292         if (threeway) {
293             if (ancestor == null) {
294                 if (left == null) {
295                     if (right == null) {
296                         //Assert.isTrue(false);
297 // shouldn't happen
298 } else {
299                         description= RIGHT | ADDITION;
300                     }
301                 } else {
302                     if (right == null) {
303                         description= LEFT | ADDITION;
304                     } else {
305                         description= CONFLICTING | ADDITION;
306                         if (contentsEqual(left, right))
307                             description|= PSEUDO_CONFLICT;
308                     }
309                 }
310             } else {
311                 if (left == null) {
312                     if (right == null) {
313                         description= CONFLICTING | DELETION | PSEUDO_CONFLICT;
314                     } else {
315                         if (contentsEqual(ancestor, right))
316                             description= LEFT | DELETION;
317                         else
318                             description= CONFLICTING | CHANGE;
319                     }
320                 } else {
321                     if (right == null) {
322                         if (contentsEqual(ancestor, left))
323                             description= RIGHT | DELETION;
324                         else
325                             description= CONFLICTING | CHANGE;
326                     } else {
327                         boolean ay= contentsEqual(ancestor, left);
328                         boolean am= contentsEqual(ancestor, right);
329                         
330                         if (ay && am)
331                             ;
332                         else if (ay && !am) {
333                             description= RIGHT | CHANGE;
334                         } else if (!ay && am) {
335                             description= LEFT | CHANGE;
336                         } else {
337                             description= CONFLICTING | CHANGE;
338                             if (contentsEqual(left, right))
339                                 description|= PSEUDO_CONFLICT;
340                         }
341                     }
342                 }
343             }
344         } else { // two way compare ignores ancestor
345 if (left == null) {
346                 if (right == null) {
347                     //Assert.isTrue(false);
348 // shouldn't happen
349 } else {
350                     description= ADDITION;
351                 }
352             } else {
353                 if (right == null) {
354                     description= DELETION;
355                 } else {
356                     if (! contentsEqual(left, right))
357                         description= CHANGE;
358                 }
359             }
360         }
361                             
362         return description;
363     }
364         
365     /**
366      * Performs a content compare on the two given inputs.
367      * <p>
368      * The <code>Differencer</code> implementation
369      * returns <code>true</code> if both inputs implement <code>IStreamContentAccessor</code>
370      * and their byte contents is identical. Subclasses may override to implement
371      * a different content compare on the given inputs.
372      * </p>
373      *
374      * @param input1 first input to contents compare
375      * @param input2 second input to contents compare
376      * @return <code>true</code> if content is equal
377      */
378     abstract protected boolean contentsEqual(Object input1, Object input2);
379         
380     /**
381      * Returns the children of the given input or <code>null</code> if there are no children.
382      * <p>
383      * The <code>Differencer</code> implementation checks whether the input
384      * implements the <code>IStructureComparator</code> interface. If yes it is used
385      * to return an array containing all children. Otherwise <code>null</code> is returned.
386      * Subclasses may override to implement a different strategy to enumerate children.
387      * </p>
388      *
389      * @param input the object for which to return children
390      */
391     abstract protected Object [] getChildren(Object input);
392 }
393
394

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags