/*
* (c) Copyright IBM Corp. 2000, 2001.
* All Rights Reserved.
*/
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
*/
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
*/
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
*/
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
*/
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= (RangeDifference) 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;
}
}
