bundles/org.eclipse.compare.core/src/org/eclipse/compare/rangedifferencer/RangeComparatorLCS.java

/*******************************************************************************
 * Copyright (c) 2006, 2011 IBM Corporation and others.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.compare.rangedifferencer;

import java.util.ArrayList;
import java.util.List;

import org.eclipse.compare.internal.core.LCS;
import org.eclipse.compare.internal.core.Messages;
import org.eclipse.core.runtime.*;

/* package */ class RangeComparatorLCS extends LCS {

	private final IRangeComparator comparator1, comparator2;
	private int[][] lcs;

	public static RangeDifference[] findDifferences(AbstractRangeDifferenceFactory factory, IProgressMonitor pm, IRangeComparator left, IRangeComparator right) {
		RangeComparatorLCS lcs = new RangeComparatorLCS(left, right);
		SubMonitor monitor = SubMonitor.convert(pm, Messages.RangeComparatorLCS_0, 100);
		try {
			lcs.longestCommonSubsequence(monitor.newChild(95));
			return lcs.getDifferences(monitor.newChild(5), factory);
		} finally {
			if (pm != null)
				pm.done();
		}
	}

	public RangeComparatorLCS(IRangeComparator comparator1, IRangeComparator comparator2) {
		this.comparator1 = comparator1;
		this.comparator2 = comparator2;
	}

	@Override
	protected int getLength1() {
		return this.comparator1.getRangeCount();
	}

	@Override
	protected int getLength2() {
		return this.comparator2.getRangeCount();
	}

	@Override
	protected void initializeLcs(int lcsLength) {
		this.lcs = new int[2][lcsLength];
	}

	@Override
	protected boolean isRangeEqual(int i1, int i2) {
		return this.comparator1.rangesEqual(i1, this.comparator2, i2);
	}

	@Override
	protected void setLcs(int sl1, int sl2) {
		// Add one to the values so that 0 can mean that the slot is empty
		this.lcs[0][sl1] = sl1 + 1;
		this.lcs[1][sl1] = sl2 + 1;
	}

	public RangeDifference[] getDifferences(SubMonitor subMonitor, AbstractRangeDifferenceFactory factory) {
		try {
			List<RangeDifference> differences = new ArrayList<>();
			int length = getLength();
			if (length == 0) {
				differences.add(factory.createRangeDifference(RangeDifference.CHANGE, 0, this.comparator2.getRangeCount(), 0, this.comparator1.getRangeCount()));
			} else {
				subMonitor.beginTask(null, length);
				int index1, index2;
				index1 = index2 = 0;
				int l1, l2;
				int s1 = -1;
				int s2 = -1;
				while(index1 < this.lcs[0].length && index2 < this.lcs[1].length) {
					// Move both LCS lists to the next occupied slot
					while ((l1= this.lcs[0][index1]) == 0) {
						index1++;
						if (index1 >= this.lcs[0].length)
							break;
					}
					if (index1 >= this.lcs[0].length)
						break;
					while ((l2= this.lcs[1][index2]) == 0) {
						index2++;
						if (index2 >= this.lcs[1].length)
							break;
					}
					if (index2 >= this.lcs[1].length)
						break;
					// Convert the entry to an array index (see setLcs(int, int))
					int end1 = l1 - 1;
					int end2 = l2 - 1;
					if (s1 == -1 && (end1 != 0 || end2 != 0)) {
						// There is a diff at the beginning
						// TODO: We need to conform that this is the proper order
						differences.add(factory.createRangeDifference(RangeDifference.CHANGE, 0, end2, 0, end1));
					} else if (end1 != s1 + 1 || end2 != s2 + 1) {
						// A diff was found on one of the sides
						int leftStart = s1 + 1;
						int leftLength = end1 - leftStart;
						int rightStart = s2 + 1;
						int rightLength = end2 - rightStart;
						// TODO: We need to conform that this is the proper order
						differences.add(factory.createRangeDifference(RangeDifference.CHANGE, rightStart, rightLength, leftStart, leftLength));
					}
					s1 = end1;
					s2 = end2;
					index1++;
					index2++;
					worked(subMonitor, 1);
				}
				if (s1 != -1 && (s1 + 1 < this.comparator1.getRangeCount() || s2 + 1 < this.comparator2.getRangeCount())) {
					// TODO: we need to find the proper way of representing an append
					int leftStart = s1 < this.comparator1.getRangeCount() ? s1 + 1 : s1;
					int rightStart = s2 < this.comparator2.getRangeCount() ? s2 + 1 : s2;
					// TODO: We need to confirm that this is the proper order
					differences.add(factory.createRangeDifference(RangeDifference.CHANGE, rightStart, this.comparator2.getRangeCount() - (s2 + 1), leftStart, this.comparator1.getRangeCount() - (s1 + 1)));
				}

			}
			return differences.toArray(new RangeDifference[differences.size()]);
		} finally {
			subMonitor.done();
		}
	}

	private void worked(SubMonitor subMonitor, int work) {
		if (subMonitor.isCanceled())
			throw new OperationCanceledException();
		subMonitor.worked(work);
	}

	/**
	 * This method takes an LCS result interspersed with zeros (i.e. empty slots
	 * from the LCS algorithm), compacts it and shifts the LCS chunks as far towards
	 * the front as possible. This tends to produce good results most of the time.
	 *
	 * @param lcsSide A subsequence of original, presumably it is the LCS of it and
	 *            some other collection of lines
	 * @param length The number of non-empty (i.e non-zero) entries in LCS
	 * @param comparator The comparator used to generate the LCS
	 */
	private void compactAndShiftLCS(int[] lcsSide, int length,
			IRangeComparator comparator) {
		// If the LCS is empty, just return
		if (length == 0)
			return;
		// Skip any leading empty slots
		int j = 0;
		while (lcsSide[j] == 0) {
			j++;
		}
		// Put the first non-empty value in position 0
		lcsSide[0] = lcsSide[j];
		j++;
		// Push all non-empty values down into the first N slots (where N is the length)
		for (int i = 1; i < length; i++) {
			while (lcsSide[j] == 0) {
				j++;
			}
			// Push the difference down as far as possible by comparing the line at the
			// start of the diff with the line and the end and adjusting if they are the same
			int nextLine = lcsSide[i - 1] + 1;
			if (nextLine != lcsSide[j] && comparator.rangesEqual(nextLine - 1, comparator, lcsSide[j] - 1)) {
				lcsSide[i] = nextLine;
			} else {
				lcsSide[i] = lcsSide[j];
			}
			j++;
		}
		// Zero all slots after the length
		for (int i = length; i < lcsSide.length; i++) {
			lcsSide[i] = 0;
		}
	}

	@Override
	public void longestCommonSubsequence(SubMonitor subMonitor) {
		super.longestCommonSubsequence(subMonitor);
		if (this.lcs != null) { // The LCS can be null if one of the sides is empty
			compactAndShiftLCS(this.lcs[0], getLength(), this.comparator1);
			compactAndShiftLCS(this.lcs[1], getLength(), this.comparator2);
		}
	}
}