Skip to main content
aboutsummaryrefslogtreecommitdiffstats
blob: 7949b3a039a65429af0516c9fbe3339f1543107f (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
/*******************************************************************************
 * 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);
		}
	}
}

Back to the top