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 package org.eclipse.jgit.merge;
45
46 import java.util.ArrayList;
47 import java.util.Iterator;
48 import java.util.List;
49
50 import org.eclipse.jgit.diff.DiffAlgorithm;
51 import org.eclipse.jgit.diff.Edit;
52 import org.eclipse.jgit.diff.EditList;
53 import org.eclipse.jgit.diff.HistogramDiff;
54 import org.eclipse.jgit.diff.Sequence;
55 import org.eclipse.jgit.diff.SequenceComparator;
56 import org.eclipse.jgit.merge.MergeChunk.ConflictState;
57
58
59
60
61
62 public final class MergeAlgorithm {
63 private final DiffAlgorithm diffAlg;
64
65
66
67
68
69 public MergeAlgorithm() {
70 this(new HistogramDiff());
71 }
72
73
74
75
76
77
78
79 public MergeAlgorithm(DiffAlgorithm diff) {
80 this.diffAlg = diff;
81 }
82
83
84
85 private final static Edit END_EDIT = new Edit(Integer.MAX_VALUE,
86 Integer.MAX_VALUE);
87
88
89
90
91
92
93
94
95
96
97
98
99 public <S extends Sequence> MergeResult<S> merge(
100 SequenceComparator<S> cmp, S base, S ours, S theirs) {
101 List<S> sequences = new ArrayList<S>(3);
102 sequences.add(base);
103 sequences.add(ours);
104 sequences.add(theirs);
105 MergeResult<S> result = new MergeResult<S>(sequences);
106
107 if (ours.size() == 0) {
108 if (theirs.size() != 0) {
109 EditList theirsEdits = diffAlg.diff(cmp, base, theirs);
110 if (!theirsEdits.isEmpty()) {
111
112
113 result.add(1, 0, 0, ConflictState.FIRST_CONFLICTING_RANGE);
114 result.add(2, 0, theirs.size(),
115 ConflictState.NEXT_CONFLICTING_RANGE);
116 } else
117
118 result.add(1, 0, 0, ConflictState.NO_CONFLICT);
119 } else
120
121 result.add(1, 0, 0, ConflictState.NO_CONFLICT);
122 return result;
123 } else if (theirs.size() == 0) {
124 EditList oursEdits = diffAlg.diff(cmp, base, ours);
125 if (!oursEdits.isEmpty()) {
126
127
128 result.add(1, 0, ours.size(),
129 ConflictState.FIRST_CONFLICTING_RANGE);
130 result.add(2, 0, 0, ConflictState.NEXT_CONFLICTING_RANGE);
131 } else
132
133 result.add(2, 0, 0, ConflictState.NO_CONFLICT);
134 return result;
135 }
136
137 EditList oursEdits = diffAlg.diff(cmp, base, ours);
138 Iterator<Edit> baseToOurs = oursEdits.iterator();
139 EditList theirsEdits = diffAlg.diff(cmp, base, theirs);
140 Iterator<Edit> baseToTheirs = theirsEdits.iterator();
141 int current = 0;
142
143 Edit oursEdit = nextEdit(baseToOurs);
144 Edit theirsEdit = nextEdit(baseToTheirs);
145
146
147
148
149 while (theirsEdit != END_EDIT || oursEdit != END_EDIT) {
150 if (oursEdit.getEndA() < theirsEdit.getBeginA()) {
151
152
153
154 if (current != oursEdit.getBeginA()) {
155 result.add(0, current, oursEdit.getBeginA(),
156 ConflictState.NO_CONFLICT);
157 }
158 result.add(1, oursEdit.getBeginB(), oursEdit.getEndB(),
159 ConflictState.NO_CONFLICT);
160 current = oursEdit.getEndA();
161 oursEdit = nextEdit(baseToOurs);
162 } else if (theirsEdit.getEndA() < oursEdit.getBeginA()) {
163
164
165
166 if (current != theirsEdit.getBeginA()) {
167 result.add(0, current, theirsEdit.getBeginA(),
168 ConflictState.NO_CONFLICT);
169 }
170 result.add(2, theirsEdit.getBeginB(), theirsEdit.getEndB(),
171 ConflictState.NO_CONFLICT);
172 current = theirsEdit.getEndA();
173 theirsEdit = nextEdit(baseToTheirs);
174 } else {
175
176
177
178 if (oursEdit.getBeginA() != current
179 && theirsEdit.getBeginA() != current) {
180 result.add(0, current, Math.min(oursEdit.getBeginA(),
181 theirsEdit.getBeginA()), ConflictState.NO_CONFLICT);
182 }
183
184
185
186 int oursBeginB = oursEdit.getBeginB();
187 int theirsBeginB = theirsEdit.getBeginB();
188
189 if (oursEdit.getBeginA() < theirsEdit.getBeginA()) {
190 theirsBeginB -= theirsEdit.getBeginA()
191 - oursEdit.getBeginA();
192 } else {
193 oursBeginB -= oursEdit.getBeginA() - theirsEdit.getBeginA();
194 }
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223 Edit nextOursEdit = nextEdit(baseToOurs);
224 Edit nextTheirsEdit = nextEdit(baseToTheirs);
225 for (;;) {
226 if (oursEdit.getEndA() >= nextTheirsEdit.getBeginA()) {
227 theirsEdit = nextTheirsEdit;
228 nextTheirsEdit = nextEdit(baseToTheirs);
229 } else if (theirsEdit.getEndA() >= nextOursEdit.getBeginA()) {
230 oursEdit = nextOursEdit;
231 nextOursEdit = nextEdit(baseToOurs);
232 } else {
233 break;
234 }
235 }
236
237
238 int oursEndB = oursEdit.getEndB();
239 int theirsEndB = theirsEdit.getEndB();
240 if (oursEdit.getEndA() < theirsEdit.getEndA()) {
241 oursEndB += theirsEdit.getEndA() - oursEdit.getEndA();
242 } else {
243 theirsEndB += oursEdit.getEndA() - theirsEdit.getEndA();
244 }
245
246
247
248
249
250
251
252
253
254
255
256 int minBSize = oursEndB - oursBeginB;
257 int BSizeDelta = minBSize - (theirsEndB - theirsBeginB);
258 if (BSizeDelta > 0)
259 minBSize -= BSizeDelta;
260
261 int commonPrefix = 0;
262 while (commonPrefix < minBSize
263 && cmp.equals(ours, oursBeginB + commonPrefix, theirs,
264 theirsBeginB + commonPrefix))
265 commonPrefix++;
266 minBSize -= commonPrefix;
267 int commonSuffix = 0;
268 while (commonSuffix < minBSize
269 && cmp.equals(ours, oursEndB - commonSuffix - 1, theirs,
270 theirsEndB - commonSuffix - 1))
271 commonSuffix++;
272 minBSize -= commonSuffix;
273
274
275 if (commonPrefix > 0)
276 result.add(1, oursBeginB, oursBeginB + commonPrefix,
277 ConflictState.NO_CONFLICT);
278
279
280 if (minBSize > 0 || BSizeDelta != 0) {
281 result.add(1, oursBeginB + commonPrefix, oursEndB
282 - commonSuffix,
283 ConflictState.FIRST_CONFLICTING_RANGE);
284 result.add(2, theirsBeginB + commonPrefix, theirsEndB
285 - commonSuffix,
286 ConflictState.NEXT_CONFLICTING_RANGE);
287 }
288
289
290 if (commonSuffix > 0)
291 result.add(1, oursEndB - commonSuffix, oursEndB,
292 ConflictState.NO_CONFLICT);
293
294 current = Math.max(oursEdit.getEndA(), theirsEdit.getEndA());
295 oursEdit = nextOursEdit;
296 theirsEdit = nextTheirsEdit;
297 }
298 }
299
300
301 if (current < base.size()) {
302 result.add(0, current, base.size(), ConflictState.NO_CONFLICT);
303 }
304 return result;
305 }
306
307
308
309
310
311
312
313
314
315
316
317 private static Edit nextEdit(Iterator<Edit> it) {
318 return (it.hasNext() ? it.next() : END_EDIT);
319 }
320 }