001: /*******************************************************************************
002: * Copyright (c) 2000, 2007 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.compare.rangedifferencer;
011:
012: import java.util.ArrayList;
013: import java.util.List;
014:
015: import org.eclipse.compare.internal.CompareMessages;
016: import org.eclipse.compare.internal.LCSSettings;
017: import org.eclipse.core.runtime.Assert;
018: import org.eclipse.core.runtime.IProgressMonitor;
019: import org.eclipse.core.runtime.SubMonitor;
020:
021: /**
022: * A <code>RangeDifferencer</code> finds the differences between two or three <code>IRangeComparator</code>s.
023: * <p>
024: * To use the differencer, clients provide an <code>IRangeComparator</code>
025: * that breaks their input data into a sequence of comparable entities. The differencer
026: * returns the differences among these sequences as an array of <code>RangeDifference</code> objects
027: * (<code>findDifferences</code> methods).
028: * Every <code>RangeDifference</code> represents a single kind of difference
029: * and the corresponding ranges of the underlying comparable entities in the
030: * left, right, and optionally ancestor sides.
031: * <p>
032: * Alternatively, the <code>findRanges</code> methods not only return objects for
033: * the differing ranges but for non-differing ranges too.
034: * <p>
035: * The algorithm used is an objectified version of one described in:
036: * <it>A File Comparison Program,</it> by Webb Miller and Eugene W. Myers,
037: * Software Practice and Experience, Vol. 15, Nov. 1985.
038: *
039: * @see IRangeComparator
040: * @see RangeDifference
041: */
042: public final class RangeDifferencer {
043:
044: private static final RangeDifference[] EMPTY_RESULT = new RangeDifference[0];
045:
046: /* (non Javadoc)
047: * Cannot be instantiated!
048: */
049: private RangeDifferencer() {
050: // nothing to do
051: }
052:
053: /**
054: * Finds the differences between two <code>IRangeComparator</code>s.
055: * The differences are returned as an array of <code>RangeDifference</code>s.
056: * If no differences are detected an empty array is returned.
057: *
058: * @param left the left range comparator
059: * @param right the right range comparator
060: * @return an array of range differences, or an empty array if no differences were found
061: */
062: public static RangeDifference[] findDifferences(
063: LCSSettings settings, IRangeComparator left,
064: IRangeComparator right) {
065: return findDifferences((IProgressMonitor) null, settings, left,
066: right);
067: }
068:
069: /**
070: * Finds the differences between two <code>IRangeComparator</code>s.
071: * The differences are returned as an array of <code>RangeDifference</code>s.
072: * If no differences are detected an empty array is returned.
073: *
074: * @param left the left range comparator
075: * @param right the right range comparator
076: * @return an array of range differences, or an empty array if no differences were found
077: */
078: public static RangeDifference[] findDifferences(
079: IRangeComparator left, IRangeComparator right) {
080: return findDifferences((IProgressMonitor) null,
081: new LCSSettings(), left, right);
082: }
083:
084: /**
085: * Finds the differences between two <code>IRangeComparator</code>s.
086: * The differences are returned as an array of <code>RangeDifference</code>s.
087: * If no differences are detected an empty array is returned.
088: *
089: * @param pm if not <code>null</code> used to report progress
090: * @param left the left range comparator
091: * @param right the right range comparator
092: * @return an array of range differences, or an empty array if no differences were found
093: * @since 2.0
094: */
095: public static RangeDifference[] findDifferences(
096: IProgressMonitor pm, LCSSettings settings,
097: IRangeComparator left, IRangeComparator right) {
098: if (!settings.isUseGreedyMethod()) {
099: return OldDifferencer.findDifferences(pm, left, right);
100: }
101: return RangeComparatorLCS.findDifferences(pm, settings, left,
102: right);
103: }
104:
105: /**
106: * Finds the differences among three <code>IRangeComparator</code>s.
107: * The differences are returned as a list of <code>RangeDifference</code>s.
108: * If no differences are detected an empty list is returned.
109: * If the ancestor range comparator is <code>null</code>, a two-way
110: * comparison is performed.
111: *
112: * @param ancestor the ancestor range comparator or <code>null</code>
113: * @param left the left range comparator
114: * @param right the right range comparator
115: * @return an array of range differences, or an empty array if no differences were found
116: */
117: public static RangeDifference[] findDifferences(
118: LCSSettings settings, IRangeComparator ancestor,
119: IRangeComparator left, IRangeComparator right) {
120: return findDifferences(null, settings, ancestor, left, right);
121: }
122:
123: /**
124: * Finds the differences among three <code>IRangeComparator</code>s.
125: * The differences are returned as a list of <code>RangeDifference</code>s.
126: * If no differences are detected an empty list is returned.
127: * If the ancestor range comparator is <code>null</code>, a two-way
128: * comparison is performed.
129: *
130: * @param pm if not <code>null</code> used to report progress
131: * @param ancestor the ancestor range comparator or <code>null</code>
132: * @param left the left range comparator
133: * @param right the right range comparator
134: * @return an array of range differences, or an empty array if no differences were found
135: * @since 2.0
136: */
137: public static RangeDifference[] findDifferences(
138: IProgressMonitor pm, LCSSettings settings,
139: IRangeComparator ancestor, IRangeComparator left,
140: IRangeComparator right) {
141: try {
142: if (ancestor == null)
143: return findDifferences(pm, settings, left, right);
144: SubMonitor monitor = SubMonitor.convert(pm,
145: CompareMessages.RangeComparatorLCS_0, 100);
146: RangeDifference[] leftAncestorScript = null;
147: RangeDifference[] rightAncestorScript = findDifferences(
148: monitor.newChild(50), settings, ancestor, right);
149: if (rightAncestorScript != null) {
150: monitor.setWorkRemaining(100);
151: leftAncestorScript = findDifferences(monitor
152: .newChild(50), settings, ancestor, left);
153: }
154: if (rightAncestorScript == null
155: || leftAncestorScript == null)
156: return null;
157:
158: DifferencesIterator myIter = new DifferencesIterator(
159: rightAncestorScript);
160: DifferencesIterator yourIter = new DifferencesIterator(
161: leftAncestorScript);
162:
163: List diff3 = new ArrayList();
164: diff3.add(new RangeDifference(RangeDifference.ERROR)); // add a sentinel
165:
166: int changeRangeStart = 0;
167: int changeRangeEnd = 0;
168: //
169: // Combine the two two-way edit scripts into one
170: //
171: monitor.setWorkRemaining(rightAncestorScript.length
172: + leftAncestorScript.length);
173: while (myIter.fDifference != null
174: || yourIter.fDifference != null) {
175:
176: DifferencesIterator startThread;
177: myIter.removeAll();
178: yourIter.removeAll();
179: //
180: // take the next diff that is closer to the start
181: //
182: if (myIter.fDifference == null)
183: startThread = yourIter;
184: else if (yourIter.fDifference == null)
185: startThread = myIter;
186: else { // not at end of both scripts take the lowest range
187: if (myIter.fDifference.fLeftStart <= yourIter.fDifference.fLeftStart) // 2 -> common (Ancestor) change range
188: startThread = myIter;
189: else
190: startThread = yourIter;
191: }
192: changeRangeStart = startThread.fDifference.fLeftStart;
193: changeRangeEnd = startThread.fDifference.leftEnd();
194:
195: startThread.next();
196: monitor.worked(1);
197: //
198: // check for overlapping changes with other thread
199: // merge overlapping changes with this range
200: //
201: DifferencesIterator other = startThread.other(myIter,
202: yourIter);
203: while (other.fDifference != null
204: && other.fDifference.fLeftStart <= changeRangeEnd) {
205: int newMax = other.fDifference.leftEnd();
206: other.next();
207: monitor.worked(1);
208: if (newMax >= changeRangeEnd) {
209: changeRangeEnd = newMax;
210: other = other.other(myIter, yourIter);
211: }
212: }
213: diff3.add(createRangeDifference3(myIter, yourIter,
214: diff3, right, left, changeRangeStart,
215: changeRangeEnd));
216: }
217:
218: // remove sentinel
219: diff3.remove(0);
220: return (RangeDifference[]) diff3.toArray(EMPTY_RESULT);
221: } finally {
222: if (pm != null)
223: pm.done();
224: }
225: }
226:
227: /**
228: * Finds the differences among two <code>IRangeComparator</code>s.
229: * In contrast to <code>findDifferences</code>, the result
230: * contains <code>RangeDifference</code> elements for non-differing ranges too.
231: *
232: * @param left the left range comparator
233: * @param right the right range comparator
234: * @return an array of range differences
235: */
236: public static RangeDifference[] findRanges(LCSSettings settings,
237: IRangeComparator left, IRangeComparator right) {
238: return findRanges((IProgressMonitor) null, settings, left,
239: right);
240: }
241:
242: /**
243: * Finds the differences among two <code>IRangeComparator</code>s.
244: * In contrast to <code>findDifferences</code>, the result
245: * contains <code>RangeDifference</code> elements for non-differing ranges too.
246: *
247: * @param pm if not <code>null</code> used to report progress
248: * @param left the left range comparator
249: * @param right the right range comparator
250: * @return an array of range differences
251: * @since 2.0
252: */
253: public static RangeDifference[] findRanges(IProgressMonitor pm,
254: LCSSettings settings, IRangeComparator left,
255: IRangeComparator right) {
256: RangeDifference[] in = findDifferences(pm, settings, left,
257: right);
258: List out = new ArrayList();
259:
260: RangeDifference rd;
261:
262: int mstart = 0;
263: int ystart = 0;
264:
265: for (int i = 0; i < in.length; i++) {
266: RangeDifference es = in[i];
267:
268: rd = new RangeDifference(RangeDifference.NOCHANGE, mstart,
269: es.rightStart() - mstart, ystart, es.leftStart()
270: - ystart);
271: if (rd.maxLength() != 0)
272: out.add(rd);
273:
274: out.add(es);
275:
276: mstart = es.rightEnd();
277: ystart = es.leftEnd();
278: }
279: rd = new RangeDifference(RangeDifference.NOCHANGE, mstart,
280: right.getRangeCount() - mstart, ystart, left
281: .getRangeCount()
282: - ystart);
283: if (rd.maxLength() > 0)
284: out.add(rd);
285:
286: return (RangeDifference[]) out.toArray(EMPTY_RESULT);
287: }
288:
289: /**
290: * Finds the differences among three <code>IRangeComparator</code>s.
291: * In contrast to <code>findDifferences</code>, the result
292: * contains <code>RangeDifference</code> elements for non-differing ranges too.
293: * If the ancestor range comparator is <code>null</code>, a two-way
294: * comparison is performed.
295: *
296: * @param ancestor the ancestor range comparator or <code>null</code>
297: * @param left the left range comparator
298: * @param right the right range comparator
299: * @return an array of range differences
300: */
301: public static RangeDifference[] findRanges(LCSSettings settings,
302: IRangeComparator ancestor, IRangeComparator left,
303: IRangeComparator right) {
304: return findRanges(null, settings, ancestor, left, right);
305: }
306:
307: /**
308: * Finds the differences among three <code>IRangeComparator</code>s.
309: * In contrast to <code>findDifferences</code>, the result
310: * contains <code>RangeDifference</code> elements for non-differing ranges too.
311: * If the ancestor range comparator is <code>null</code>, a two-way
312: * comparison is performed.
313: *
314: * @param pm if not <code>null</code> used to report progress
315: * @param ancestor the ancestor range comparator or <code>null</code>
316: * @param left the left range comparator
317: * @param right the right range comparator
318: * @return an array of range differences
319: * @since 2.0
320: */
321: public static RangeDifference[] findRanges(IProgressMonitor pm,
322: LCSSettings settings, IRangeComparator ancestor,
323: IRangeComparator left, IRangeComparator right) {
324:
325: if (ancestor == null)
326: return findRanges(pm, settings, left, right);
327:
328: RangeDifference[] in = findDifferences(pm, settings, ancestor,
329: left, right);
330: List out = new ArrayList();
331:
332: RangeDifference rd;
333:
334: int mstart = 0;
335: int ystart = 0;
336: int astart = 0;
337:
338: for (int i = 0; i < in.length; i++) {
339: RangeDifference es = in[i];
340:
341: rd = new RangeDifference(RangeDifference.NOCHANGE, mstart,
342: es.rightStart() - mstart, ystart, es.leftStart()
343: - ystart, astart, es.ancestorStart()
344: - astart);
345: if (rd.maxLength() > 0)
346: out.add(rd);
347:
348: out.add(es);
349:
350: mstart = es.rightEnd();
351: ystart = es.leftEnd();
352: astart = es.ancestorEnd();
353: }
354: rd = new RangeDifference(RangeDifference.NOCHANGE, mstart,
355: right.getRangeCount() - mstart, ystart, left
356: .getRangeCount()
357: - ystart, astart, ancestor.getRangeCount()
358: - astart);
359: if (rd.maxLength() > 0)
360: out.add(rd);
361:
362: return (RangeDifference[]) out.toArray(EMPTY_RESULT);
363: }
364:
365: //---- private methods
366:
367: /*
368: * Creates a <code>RangeDifference3</code> given the
369: * state of two DifferenceIterators.
370: */
371: private static RangeDifference createRangeDifference3(
372: DifferencesIterator myIter, DifferencesIterator yourIter,
373: List diff3, IRangeComparator right, IRangeComparator left,
374: int changeRangeStart, int changeRangeEnd) {
375:
376: int rightStart, rightEnd;
377: int leftStart, leftEnd;
378: int kind = RangeDifference.ERROR;
379: RangeDifference last = (RangeDifference) diff3
380: .get(diff3.size() - 1);
381:
382: Assert
383: .isTrue((myIter.getCount() != 0 || yourIter.getCount() != 0)); // At least one range array must be non-empty
384: //
385: // find corresponding lines to fChangeRangeStart/End in right and left
386: //
387: if (myIter.getCount() == 0) { // only left changed
388: rightStart = changeRangeStart - last.ancestorEnd()
389: + last.rightEnd();
390: rightEnd = changeRangeEnd - last.ancestorEnd()
391: + last.rightEnd();
392: kind = RangeDifference.LEFT;
393: } else {
394: RangeDifference f = (RangeDifference) myIter.fRange.get(0);
395: RangeDifference l = (RangeDifference) myIter.fRange
396: .get(myIter.fRange.size() - 1);
397: rightStart = changeRangeStart - f.fLeftStart
398: + f.fRightStart;
399: rightEnd = changeRangeEnd - l.leftEnd() + l.rightEnd();
400: }
401:
402: if (yourIter.getCount() == 0) { // only right changed
403: leftStart = changeRangeStart - last.ancestorEnd()
404: + last.leftEnd();
405: leftEnd = changeRangeEnd - last.ancestorEnd()
406: + last.leftEnd();
407: kind = RangeDifference.RIGHT;
408: } else {
409: RangeDifference f = (RangeDifference) yourIter.fRange
410: .get(0);
411: RangeDifference l = (RangeDifference) yourIter.fRange
412: .get(yourIter.fRange.size() - 1);
413: leftStart = changeRangeStart - f.fLeftStart + f.fRightStart;
414: leftEnd = changeRangeEnd - l.leftEnd() + l.rightEnd();
415: }
416:
417: if (kind == RangeDifference.ERROR) { // overlapping change (conflict) -> compare the changed ranges
418: if (rangeSpansEqual(right, rightStart, rightEnd
419: - rightStart, left, leftStart, leftEnd - leftStart))
420: kind = RangeDifference.ANCESTOR;
421: else
422: kind = RangeDifference.CONFLICT;
423: }
424: return new RangeDifference(kind, rightStart, rightEnd
425: - rightStart, leftStart, leftEnd - leftStart,
426: changeRangeStart, changeRangeEnd - changeRangeStart);
427: }
428:
429: /*
430: * Tests whether <code>right</code> and <code>left</code> changed in the same way
431: */
432: private static boolean rangeSpansEqual(IRangeComparator right,
433: int rightStart, int rightLen, IRangeComparator left,
434: int leftStart, int leftLen) {
435: if (rightLen == leftLen) {
436: int i = 0;
437: for (i = 0; i < rightLen; i++) {
438: if (!rangesEqual(right, rightStart + i, left, leftStart
439: + i))
440: break;
441: }
442: if (i == rightLen)
443: return true;
444: }
445: return false;
446: }
447:
448: /*
449: * Tests if two ranges are equal
450: */
451: private static boolean rangesEqual(IRangeComparator a, int ai,
452: IRangeComparator b, int bi) {
453: return a.rangesEqual(ai, b, bi);
454: }
455: }
|