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