| /******************************************************************************* |
| * Copyright (c) 2000, 2003 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Common Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/cpl-v10.html |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| *******************************************************************************/ |
| package org.eclipse.compare.rangedifferencer; |
| |
| import java.util.*; |
| |
| import org.eclipse.jface.util.Assert; |
| |
| import org.eclipse.core.runtime.IProgressMonitor; |
| |
| /** |
| * A <code>RangeDifferencer</code> finds the differences between two or three <code>IRangeComparator</code>s. |
| * <p> |
| * To use the differencer, clients provide an <code>IRangeComparator</code> |
| * that breaks their input data into a sequence of comparable entities. The differencer |
| * returns the differences among these sequences as an array of <code>RangeDifference</code> objects |
| * (<code>findDifferences</code> methods). |
| * Every <code>RangeDifference</code> represents a single kind of difference |
| * and the corresponding ranges of the underlying comparable entities in the |
| * left, right, and optionally ancestor sides. |
| * <p> |
| * Alternatively, the <code>findRanges</code> methods not only return objects for |
| * the differing ranges but for non-differing ranges too. |
| * <p> |
| * The algorithm used is an objectified version of one described in: |
| * <it>A File Comparison Program,</it> by Webb Miller and Eugene W. Myers, |
| * Software Practice and Experience, Vol. 15, Nov. 1985. |
| * |
| * @see IRangeComparator |
| * @see RangeDifference |
| */ |
| public final class RangeDifferencer { |
| |
| private static final RangeDifference[] EMPTY_RESULT= new RangeDifference[0]; |
| |
| /* (non Javadoc) |
| * Non instantiatiable! |
| */ |
| private RangeDifferencer() { |
| } |
| |
| /** |
| * Finds the differences between two <code>IRangeComparator</code>s. |
| * The differences are returned as an array of <code>RangeDifference</code>s. |
| * If no differences are detected an empty array is returned. |
| * |
| * @param left the left range comparator |
| * @param right the right range comparator |
| * @return an array of range differences, or an empty array if no differences were found |
| */ |
| public static RangeDifference[] findDifferences(IRangeComparator left, IRangeComparator right) { |
| return findDifferences((IProgressMonitor)null, left, right); |
| } |
| |
| /** |
| * Finds the differences between two <code>IRangeComparator</code>s. |
| * The differences are returned as an array of <code>RangeDifference</code>s. |
| * If no differences are detected an empty array is returned. |
| * |
| * @param pm if not <code>null</code> used to report progress |
| * @param left the left range comparator |
| * @param right the right range comparator |
| * @return an array of range differences, or an empty array if no differences were found |
| * @since 2.0 |
| */ |
| public static RangeDifference[] findDifferences(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) { |
| |
| // assert that both IRangeComparators are of the same class |
| Assert.isTrue(right.getClass().equals(left.getClass())); |
| |
| int rightSize= right.getRangeCount(); |
| int leftSize= left.getRangeCount(); |
| // |
| // Differences matrix: |
| // only the last d of each diagonal is stored, i.e., lastDiagonal[k] = row of d |
| // |
| int diagLen= 2 * Math.max(rightSize, leftSize); // bound on the size of edit script |
| int maxDiagonal= diagLen; |
| int lastDiagonal[]= new int[diagLen + 1]; // the row containing the last d |
| // on diagonal k (lastDiagonal[k] = row) |
| int origin= diagLen / 2; // origin of diagonal 0 |
| |
| // script corresponding to d[k] |
| LinkedRangeDifference script[]= new LinkedRangeDifference[diagLen + 1]; |
| int row, col; |
| |
| // find common prefix |
| for (row= 0; row < rightSize && row < leftSize && rangesEqual(right, row, left, row) == true; ++row) |
| ; |
| |
| lastDiagonal[origin]= row; |
| script[origin]= null; |
| int lower= (row == rightSize) ? origin + 1 : origin - 1; |
| int upper= (row == leftSize) ? origin - 1 : origin + 1; |
| |
| if (lower > upper) |
| return EMPTY_RESULT; |
| |
| //System.out.println("findDifferences: " + maxDiagonal + " " + lower + " " + upper); |
| |
| // for each value of the edit distance |
| for (int d= 1; d <= maxDiagonal; ++d) { // d is the current edit distance |
| |
| if (pm != null) |
| pm.worked(1); |
| |
| if (right.skipRangeComparison(d, maxDiagonal, left)) |
| return EMPTY_RESULT; // should be something we already found |
| |
| // for each relevant diagonal (-d, -d+2 ..., d-2, d) |
| for (int k= lower; k <= upper; k += 2) { // k is the current diagonal |
| LinkedRangeDifference edit; |
| |
| if (pm != null && pm.isCanceled()) |
| return EMPTY_RESULT; |
| |
| if (k == origin - d || k != origin + d && lastDiagonal[k + 1] >= lastDiagonal[k - 1]) { |
| // |
| // move down |
| // |
| row= lastDiagonal[k + 1] + 1; |
| edit= new LinkedRangeDifference(script[k + 1], LinkedRangeDifference.DELETE); |
| } else { |
| // |
| // move right |
| // |
| row= lastDiagonal[k - 1]; |
| edit= new LinkedRangeDifference(script[k - 1], LinkedRangeDifference.INSERT); |
| } |
| col= row + k - origin; |
| edit.fRightStart= row; |
| edit.fLeftStart= col; |
| Assert.isTrue(k >= 0 && k <= maxDiagonal); |
| script[k]= edit; |
| |
| // slide down the diagonal as far as possible |
| while (row < rightSize && col < leftSize && rangesEqual(right, row, left, col) == true) { |
| ++row; |
| ++col; |
| } |
| |
| Assert.isTrue(k >= 0 && k <= maxDiagonal); // Unreasonable value for diagonal index |
| lastDiagonal[k]= row; |
| |
| if (row == rightSize && col == leftSize) { |
| //showScript(script[k], right, left); |
| return createDifferencesRanges(script[k]); |
| } |
| if (row == rightSize) |
| lower= k + 2; |
| if (col == leftSize) |
| upper= k - 2; |
| } |
| --lower; |
| ++upper; |
| } |
| // too many differences |
| Assert.isTrue(false); |
| return null; |
| } |
| |
| /** |
| * Finds the differences among three <code>IRangeComparator</code>s. |
| * The differences are returned as a list of <code>RangeDifference</code>s. |
| * If no differences are detected an empty list is returned. |
| * If the ancestor range comparator is <code>null</code>, a two-way |
| * comparison is performed. |
| * |
| * @param ancestor the ancestor range comparator or <code>null</code> |
| * @param left the left range comparator |
| * @param right the right range comparator |
| * @return an array of range differences, or an empty array if no differences were found |
| */ |
| public static RangeDifference[] findDifferences(IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) { |
| return findDifferences(null, ancestor, left, right); |
| } |
| |
| /** |
| * Finds the differences among three <code>IRangeComparator</code>s. |
| * The differences are returned as a list of <code>RangeDifference</code>s. |
| * If no differences are detected an empty list is returned. |
| * If the ancestor range comparator is <code>null</code>, a two-way |
| * comparison is performed. |
| * |
| * @param pm if not <code>null</code> used to report progress |
| * @param ancestor the ancestor range comparator or <code>null</code> |
| * @param left the left range comparator |
| * @param right the right range comparator |
| * @return an array of range differences, or an empty array if no differences were found |
| * @since 2.0 |
| */ |
| public static RangeDifference[] findDifferences(IProgressMonitor pm, IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) { |
| |
| if (ancestor == null) |
| return findDifferences(pm, left, right); |
| |
| RangeDifference[] leftAncestorScript= null; |
| RangeDifference[] rightAncestorScript= findDifferences(pm, ancestor, right); |
| if (rightAncestorScript != null) |
| leftAncestorScript= findDifferences(pm, ancestor, left); |
| if (rightAncestorScript == null || leftAncestorScript == null) |
| return null; |
| |
| DifferencesIterator myIter= new DifferencesIterator(rightAncestorScript); |
| DifferencesIterator yourIter= new DifferencesIterator(leftAncestorScript); |
| |
| List diff3= new ArrayList(); |
| diff3.add(new RangeDifference(RangeDifference.ERROR)); // add a sentinel |
| |
| int changeRangeStart= 0; |
| int changeRangeEnd= 0; |
| // |
| // Combine the two two-way edit scripts into one |
| // |
| while (myIter.fDifference != null || yourIter.fDifference != null) { |
| |
| DifferencesIterator startThread; |
| myIter.removeAll(); |
| yourIter.removeAll(); |
| // |
| // take the next diff that is closer to the start |
| // |
| if (myIter.fDifference == null) |
| startThread= yourIter; |
| else if (yourIter.fDifference == null) |
| startThread= myIter; |
| else { // not at end of both scripts take the lowest range |
| if (myIter.fDifference.fLeftStart <= yourIter.fDifference.fLeftStart) // 2 -> common (Ancestor) change range |
| startThread= myIter; |
| else |
| startThread= yourIter; |
| } |
| changeRangeStart= startThread.fDifference.fLeftStart; |
| changeRangeEnd= startThread.fDifference.leftEnd(); |
| |
| startThread.next(); |
| // |
| // check for overlapping changes with other thread |
| // merge overlapping changes with this range |
| // |
| DifferencesIterator other= startThread.other(myIter, yourIter); |
| while (other.fDifference != null && other.fDifference.fLeftStart <= changeRangeEnd) { |
| int newMax= other.fDifference.leftEnd(); |
| other.next(); |
| if (newMax >= changeRangeEnd) { |
| changeRangeEnd= newMax; |
| other= other.other(myIter, yourIter); |
| } |
| } |
| diff3.add(createRangeDifference3(myIter, yourIter, diff3, right, left, changeRangeStart, changeRangeEnd)); |
| } |
| |
| // remove sentinel |
| diff3.remove(0); |
| return (RangeDifference[]) diff3.toArray(EMPTY_RESULT); |
| } |
| |
| /** |
| * Finds the differences among two <code>IRangeComparator</code>s. |
| * In contrast to <code>findDifferences</code>, the result |
| * contains <code>RangeDifference</code> elements for non-differing ranges too. |
| * |
| * @param left the left range comparator |
| * @param right the right range comparator |
| * @return an array of range differences |
| */ |
| public static RangeDifference[] findRanges(IRangeComparator left, IRangeComparator right) { |
| return findRanges((IProgressMonitor)null, left, right); |
| } |
| |
| /** |
| * Finds the differences among two <code>IRangeComparator</code>s. |
| * In contrast to <code>findDifferences</code>, the result |
| * contains <code>RangeDifference</code> elements for non-differing ranges too. |
| * |
| * @param pm if not <code>null</code> used to report progress |
| * @param left the left range comparator |
| * @param right the right range comparator |
| * @return an array of range differences |
| * @since 2.0 |
| */ |
| public static RangeDifference[] findRanges(IProgressMonitor pm, IRangeComparator left, IRangeComparator right) { |
| RangeDifference[] in= findDifferences(pm, left, right); |
| List out= new ArrayList(); |
| |
| RangeDifference rd; |
| |
| int mstart= 0; |
| int ystart= 0; |
| |
| for (int i= 0; i < in.length; i++) { |
| RangeDifference es= in[i]; |
| |
| rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart); |
| if (rd.maxLength() != 0) |
| out.add(rd); |
| |
| out.add(es); |
| |
| mstart= es.rightEnd(); |
| ystart= es.leftEnd(); |
| } |
| rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart); |
| if (rd.maxLength() > 0) |
| out.add(rd); |
| |
| return (RangeDifference[]) out.toArray(EMPTY_RESULT); |
| } |
| |
| /** |
| * Finds the differences among three <code>IRangeComparator</code>s. |
| * In contrast to <code>findDifferences</code>, the result |
| * contains <code>RangeDifference</code> elements for non-differing ranges too. |
| * If the ancestor range comparator is <code>null</code>, a two-way |
| * comparison is performed. |
| * |
| * @param pm if not <code>null</code> used to report progress |
| * @param ancestor the ancestor range comparator or <code>null</code> |
| * @param left the left range comparator |
| * @param right the right range comparator |
| * @return an array of range differences |
| */ |
| public static RangeDifference[] findRanges(IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) { |
| return findRanges(null, ancestor, left, right); |
| } |
| |
| /** |
| * Finds the differences among three <code>IRangeComparator</code>s. |
| * In contrast to <code>findDifferences</code>, the result |
| * contains <code>RangeDifference</code> elements for non-differing ranges too. |
| * If the ancestor range comparator is <code>null</code>, a two-way |
| * comparison is performed. |
| * |
| * @param pm if not <code>null</code> used to report progress |
| * @param ancestor the ancestor range comparator or <code>null</code> |
| * @param left the left range comparator |
| * @param right the right range comparator |
| * @return an array of range differences |
| * @since 2.0 |
| */ |
| public static RangeDifference[] findRanges(IProgressMonitor pm, IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) { |
| |
| if (ancestor == null) |
| return findRanges(pm, left, right); |
| |
| RangeDifference[] in= findDifferences(pm, ancestor, left, right); |
| List out= new ArrayList(); |
| |
| RangeDifference rd; |
| |
| int mstart= 0; |
| int ystart= 0; |
| int astart= 0; |
| |
| for (int i= 0; i < in.length; i++) { |
| RangeDifference es= in[i]; |
| |
| rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, es.rightStart() - mstart, ystart, es.leftStart() - ystart, astart, es.ancestorStart() - astart); |
| if (rd.maxLength() > 0) |
| out.add(rd); |
| |
| out.add(es); |
| |
| mstart= es.rightEnd(); |
| ystart= es.leftEnd(); |
| astart= es.ancestorEnd(); |
| } |
| rd= new RangeDifference(RangeDifference.NOCHANGE, mstart, right.getRangeCount() - mstart, ystart, left.getRangeCount() - ystart, astart, ancestor.getRangeCount() - astart); |
| if (rd.maxLength() > 0) |
| out.add(rd); |
| |
| return (RangeDifference[]) out.toArray(EMPTY_RESULT); |
| } |
| |
| //---- private methods |
| |
| /** |
| * Creates a Vector of DifferencesRanges out of the LinkedRangeDifference. |
| * It coalesces adjacent changes. |
| * In addition, indices are changed such that the ranges are 1) open, i.e, |
| * the end of the range is not included, and 2) are zero based. |
| */ |
| private static RangeDifference[] createDifferencesRanges(LinkedRangeDifference start) { |
| |
| LinkedRangeDifference ep= reverseDifferences(start); |
| ArrayList result= new ArrayList(); |
| RangeDifference es= null; |
| |
| while (ep != null) { |
| es= new RangeDifference(RangeDifference.CHANGE); |
| |
| if (ep.isInsert()) { |
| es.fRightStart= ep.fRightStart + 1; |
| es.fLeftStart= ep.fLeftStart; |
| RangeDifference b= ep; |
| do { |
| ep= ep.getNext(); |
| es.fLeftLength++; |
| } while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart); |
| } else { |
| es.fRightStart= ep.fRightStart; |
| es.fLeftStart= ep.fLeftStart; |
| |
| RangeDifference a= ep; |
| // |
| // deleted lines |
| // |
| do { |
| a= ep; |
| ep= ep.getNext(); |
| es.fRightLength++; |
| } while (ep != null && ep.isDelete() && ep.fRightStart == a.fRightStart + 1); |
| |
| boolean change= (ep != null && ep.isInsert() && ep.fRightStart == a.fRightStart); |
| |
| if (change) { |
| RangeDifference b= ep; |
| // |
| // replacement lines |
| // |
| do { |
| ep= ep.getNext(); |
| es.fLeftLength++; |
| } while (ep != null && ep.isInsert() && ep.fRightStart == b.fRightStart); |
| } else { |
| es.fLeftLength= 0; |
| } |
| es.fLeftStart++; // meaning of range changes from "insert after", to "replace with" |
| |
| } |
| // |
| // the script commands are 1 based, subtract one to make them zero based |
| // |
| es.fRightStart--; |
| es.fLeftStart--; |
| result.add(es); |
| } |
| return (RangeDifference[]) result.toArray(EMPTY_RESULT); |
| } |
| |
| /** |
| * Creates a <code>RangeDifference3</code> given the |
| * state of two DifferenceIterators. |
| */ |
| private static RangeDifference createRangeDifference3( |
| DifferencesIterator myIter, |
| DifferencesIterator yourIter, |
| List diff3, |
| IRangeComparator right, |
| IRangeComparator left, |
| int changeRangeStart, |
| int changeRangeEnd) { |
| |
| int rightStart, rightEnd; |
| int leftStart, leftEnd; |
| int kind= RangeDifference.ERROR; |
| RangeDifference last= (RangeDifference) diff3.get(diff3.size() - 1); |
| |
| Assert.isTrue((myIter.getCount() != 0 || yourIter.getCount() != 0)); // At least one range array must be non-empty |
| // |
| // find corresponding lines to fChangeRangeStart/End in right and left |
| // |
| if (myIter.getCount() == 0) { // only left changed |
| rightStart= changeRangeStart - last.ancestorEnd() + last.rightEnd(); |
| rightEnd= changeRangeEnd - last.ancestorEnd() + last.rightEnd(); |
| kind= RangeDifference.LEFT; |
| } else { |
| RangeDifference f= (RangeDifference) myIter.fRange.get(0); |
| RangeDifference l= (RangeDifference) myIter.fRange.get(myIter.fRange.size() - 1); |
| rightStart= changeRangeStart - f.fLeftStart + f.fRightStart; |
| rightEnd= changeRangeEnd - l.leftEnd() + l.rightEnd(); |
| } |
| |
| if (yourIter.getCount() == 0) { // only right changed |
| leftStart= changeRangeStart - last.ancestorEnd() + last.leftEnd(); |
| leftEnd= changeRangeEnd - last.ancestorEnd() + last.leftEnd(); |
| kind= RangeDifference.RIGHT; |
| } else { |
| RangeDifference f= (RangeDifference) yourIter.fRange.get(0); |
| RangeDifference l= (RangeDifference) yourIter.fRange.get(yourIter.fRange.size() - 1); |
| leftStart= changeRangeStart - f.fLeftStart + f.fRightStart; |
| leftEnd= changeRangeEnd - l.leftEnd() + l.rightEnd(); |
| } |
| |
| if (kind == RangeDifference.ERROR) { // overlapping change (conflict) -> compare the changed ranges |
| if (rangeSpansEqual(right, rightStart, rightEnd - rightStart, left, leftStart, leftEnd - leftStart)) |
| kind= RangeDifference.ANCESTOR; |
| else |
| kind= RangeDifference.CONFLICT; |
| } |
| return new RangeDifference(kind, rightStart, rightEnd - rightStart, leftStart, leftEnd - leftStart, changeRangeStart, changeRangeEnd - changeRangeStart); |
| } |
| |
| /** |
| * Tests if two ranges are equal |
| */ |
| private static boolean rangesEqual(IRangeComparator a, int ai, IRangeComparator b, int bi) { |
| return a.rangesEqual(ai, b, bi); |
| } |
| |
| /** |
| * Tests whether <code>right</code> and <code>left</left> changed in the same way |
| */ |
| private static boolean rangeSpansEqual(IRangeComparator right, int rightStart, int rightLen, IRangeComparator left, int leftStart, int leftLen) { |
| if (rightLen == leftLen) { |
| int i= 0; |
| for (i= 0; i < rightLen; i++) { |
| if (!rangesEqual(right, rightStart + i, left, leftStart + i)) |
| break; |
| } |
| if (i == rightLen) |
| return true; |
| } |
| return false; |
| } |
| |
| /** |
| * Reverses the range differences |
| */ |
| private static LinkedRangeDifference reverseDifferences(LinkedRangeDifference start) { |
| LinkedRangeDifference ep, behind, ahead; |
| |
| ahead= start; |
| ep= null; |
| while (ahead != null) { |
| behind= ep; |
| ep= ahead; |
| ahead= ahead.getNext(); |
| ep.setNext(behind); |
| } |
| return ep; |
| } |
| } |
| |