1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
|
6 |
|
|
7 |
|
|
8 |
|
|
9 |
|
|
10 |
|
|
11 |
|
|
12 |
|
|
13 |
|
|
14 |
|
|
15 |
|
|
16 |
|
|
17 |
|
|
18 |
|
|
19 |
|
|
20 |
|
package org.xwiki.diff.internal; |
21 |
|
|
22 |
|
import java.util.ArrayList; |
23 |
|
import java.util.Collections; |
24 |
|
import java.util.List; |
25 |
|
|
26 |
|
import javax.inject.Singleton; |
27 |
|
|
28 |
|
import org.xwiki.component.annotation.Component; |
29 |
|
import org.xwiki.diff.Delta; |
30 |
|
import org.xwiki.diff.Delta.Type; |
31 |
|
import org.xwiki.diff.DiffConfiguration; |
32 |
|
import org.xwiki.diff.DiffException; |
33 |
|
import org.xwiki.diff.DiffManager; |
34 |
|
import org.xwiki.diff.DiffResult; |
35 |
|
import org.xwiki.diff.MergeConfiguration; |
36 |
|
import org.xwiki.diff.MergeConfiguration.Version; |
37 |
|
import org.xwiki.diff.MergeException; |
38 |
|
import org.xwiki.diff.MergeResult; |
39 |
|
import org.xwiki.diff.Patch; |
40 |
|
|
41 |
|
import difflib.DiffUtils; |
42 |
|
|
43 |
|
|
44 |
|
@link |
45 |
|
|
46 |
|
@version |
47 |
|
|
48 |
|
@Component |
49 |
|
@Singleton |
|
|
| 79.4% |
Uncovered Elements: 52 (253) |
Complexity: 71 |
Complexity Density: 0.43 |
|
50 |
|
public class DefaultDiffManager implements DiffManager |
51 |
|
{ |
|
|
| 100% |
Uncovered Elements: 0 (18) |
Complexity: 7 |
Complexity Density: 0.58 |
|
52 |
107 |
@Override... |
53 |
|
public <E> DiffResult<E> diff(List<E> previous, List<E> next, DiffConfiguration<E> diff) throws DiffException |
54 |
|
{ |
55 |
107 |
DefaultDiffResult<E> result = new DefaultDiffResult<E>(previous, next); |
56 |
|
|
57 |
|
|
58 |
107 |
Patch<E> patch; |
59 |
107 |
if (previous == null || previous.isEmpty()) { |
60 |
8 |
patch = new DefaultPatch<E>(); |
61 |
8 |
if (next != null && !next.isEmpty()) { |
62 |
3 |
patch.add(new InsertDelta<E>(new DefaultChunk<E>(0, Collections.<E>emptyList()), new DefaultChunk<E>( |
63 |
|
0, next))); |
64 |
|
} |
65 |
99 |
} else if (next == null || next.isEmpty()) { |
66 |
5 |
patch = new DefaultPatch<E>(); |
67 |
5 |
patch.add(new DeleteDelta<E>(new DefaultChunk<E>(0, previous), new DefaultChunk<E>(0, Collections |
68 |
|
.<E>emptyList()))); |
69 |
|
} else { |
70 |
94 |
patch = new DefaultPatch<E>(DiffUtils.diff(previous, next)); |
71 |
|
} |
72 |
|
|
73 |
107 |
result.setPatch(patch); |
74 |
|
|
75 |
107 |
return result; |
76 |
|
} |
77 |
|
|
|
|
| 86.7% |
Uncovered Elements: 6 (45) |
Complexity: 10 |
Complexity Density: 0.32 |
|
78 |
31 |
@Override... |
79 |
|
public <E> MergeResult<E> merge(List<E> commonAncestor, List<E> next, List<E> current, |
80 |
|
MergeConfiguration<E> configuration) throws MergeException |
81 |
|
{ |
82 |
31 |
DefaultMergeResult<E> mergeResult = new DefaultMergeResult<E>(commonAncestor, next, current); |
83 |
|
|
84 |
|
|
85 |
|
|
86 |
31 |
DiffResult<E> diffNextResult; |
87 |
31 |
try { |
88 |
31 |
diffNextResult = diff(commonAncestor, next, null); |
89 |
|
} catch (DiffException e) { |
90 |
0 |
throw new MergeException("Faile to diff between common ancestor and next version", e); |
91 |
|
} |
92 |
31 |
mergeResult.getLog().addAll(diffNextResult.getLog()); |
93 |
|
|
94 |
31 |
Patch<E> patchNext = diffNextResult.getPatch(); |
95 |
|
|
96 |
|
|
97 |
|
|
98 |
31 |
if (patchNext.isEmpty()) { |
99 |
|
|
100 |
1 |
return mergeResult; |
101 |
|
} |
102 |
|
|
103 |
|
|
104 |
|
|
105 |
30 |
if (current.isEmpty()) { |
106 |
|
|
107 |
1 |
if (commonAncestor.isEmpty()) { |
108 |
0 |
mergeResult.setMerged(next); |
109 |
1 |
} else if (next.isEmpty()) { |
110 |
|
|
111 |
0 |
mergeResult.getLog().warn("The modification was already applied"); |
112 |
|
} else { |
113 |
|
|
114 |
1 |
mergeResult.getLog().error("The current value is empty"); |
115 |
|
} |
116 |
|
} else { |
117 |
|
|
118 |
29 |
DiffResult<E> diffCurrentResult; |
119 |
29 |
try { |
120 |
29 |
diffCurrentResult = diff(commonAncestor, current, null); |
121 |
|
} catch (DiffException e) { |
122 |
0 |
throw new MergeException("Faile to diff between common ancestor and current version", e); |
123 |
|
} |
124 |
29 |
mergeResult.getLog().addAll(diffCurrentResult.getLog()); |
125 |
|
|
126 |
29 |
Patch<E> patchCurrent = diffCurrentResult.getPatch(); |
127 |
|
|
128 |
29 |
if (patchCurrent.isEmpty()) { |
129 |
5 |
mergeResult.setMerged(next); |
130 |
24 |
} else if (isFullyModified(commonAncestor, patchCurrent)) { |
131 |
|
|
132 |
|
|
133 |
|
|
134 |
5 |
if (!current.equals(next)) { |
135 |
4 |
Delta<E> deltaNext = nextElement(patchNext); |
136 |
4 |
Delta<E> deltaCurrent = nextElement(patchCurrent); |
137 |
4 |
logConflict(mergeResult, deltaCurrent, deltaNext); |
138 |
|
} |
139 |
5 |
mergeResult.setMerged(fallback(commonAncestor, next, current, configuration)); |
140 |
|
} else { |
141 |
19 |
merge(mergeResult, commonAncestor, patchNext, patchCurrent, configuration); |
142 |
|
} |
143 |
|
} |
144 |
|
|
145 |
30 |
return mergeResult; |
146 |
|
} |
147 |
|
|
|
|
| 53.8% |
Uncovered Elements: 6 (13) |
Complexity: 4 |
Complexity Density: 0.36 |
|
148 |
5 |
private <E> List<E> fallback(List<E> commonAncestor, List<E> next, List<E> current,... |
149 |
|
MergeConfiguration<E> configuration) |
150 |
|
{ |
151 |
5 |
Version fallbackVersion; |
152 |
5 |
if (configuration != null) { |
153 |
0 |
fallbackVersion = configuration.getFallbackOnConflict(); |
154 |
|
} else { |
155 |
5 |
fallbackVersion = Version.CURRENT; |
156 |
|
} |
157 |
|
|
158 |
5 |
switch (fallbackVersion) { |
159 |
0 |
case NEXT: |
160 |
0 |
return next; |
161 |
0 |
case PREVIOUS: |
162 |
0 |
return commonAncestor; |
163 |
5 |
default: |
164 |
5 |
return current; |
165 |
|
} |
166 |
|
} |
167 |
|
|
|
|
| 0% |
Uncovered Elements: 25 (25) |
Complexity: 6 |
Complexity Density: 0.32 |
|
168 |
0 |
private <E> int fallback(List<E> commonAncestor, Delta<E> deltaNext, Delta<E> deltaCurrent, List<E> merged,... |
169 |
|
int currentIndex, MergeConfiguration<E> configuration) |
170 |
|
{ |
171 |
0 |
int newIndex = currentIndex; |
172 |
|
|
173 |
0 |
Version fallbackVersion; |
174 |
0 |
if (configuration != null) { |
175 |
0 |
fallbackVersion = configuration.getFallbackOnConflict(); |
176 |
|
} else { |
177 |
0 |
fallbackVersion = Version.CURRENT; |
178 |
|
} |
179 |
|
|
180 |
0 |
switch (fallbackVersion) { |
181 |
0 |
case NEXT: |
182 |
0 |
newIndex = apply(deltaNext, merged, currentIndex); |
183 |
0 |
break; |
184 |
0 |
case PREVIOUS: |
185 |
0 |
for (; newIndex < deltaNext.getPrevious().getIndex(); ++newIndex) { |
186 |
0 |
merged.add(commonAncestor.get(newIndex)); |
187 |
|
} |
188 |
0 |
for (; newIndex < deltaCurrent.getPrevious().getIndex(); ++newIndex) { |
189 |
0 |
merged.add(commonAncestor.get(newIndex)); |
190 |
|
} |
191 |
0 |
break; |
192 |
0 |
default: |
193 |
|
|
194 |
0 |
newIndex = apply(deltaCurrent, merged, currentIndex); |
195 |
0 |
break; |
196 |
|
} |
197 |
|
|
198 |
0 |
return newIndex; |
199 |
|
} |
200 |
|
|
201 |
|
|
202 |
|
@param |
203 |
|
@param |
204 |
|
@param |
205 |
|
@param |
206 |
|
@param |
207 |
|
@param |
208 |
|
@throws |
209 |
|
|
|
|
| 91.6% |
Uncovered Elements: 8 (95) |
Complexity: 28 |
Complexity Density: 0.49 |
|
210 |
19 |
private <E> void merge(DefaultMergeResult<E> mergeResult, List<E> commonAncestor, Patch<E> patchNext,... |
211 |
|
Patch<E> patchCurrent, MergeConfiguration<E> configuration) throws MergeException |
212 |
|
{ |
213 |
|
|
214 |
19 |
List<E> merged = new ArrayList<E>(); |
215 |
|
|
216 |
19 |
mergeResult.setMerged(merged); |
217 |
|
|
218 |
19 |
Delta<E> deltaNext = nextElement(patchNext); |
219 |
19 |
Delta<E> deltaCurrent = nextElement(patchCurrent); |
220 |
|
|
221 |
|
|
222 |
19 |
if (deltaCurrent.getType() == Type.INSERT && deltaCurrent.getPrevious().getIndex() == 0 |
223 |
|
&& deltaNext.getType() == Type.INSERT && deltaNext.getPrevious().getIndex() == 0) { |
224 |
4 |
merged.addAll(or(deltaCurrent.getNext().getElements(), deltaNext.getNext().getElements())); |
225 |
4 |
deltaCurrent = nextElement(patchCurrent); |
226 |
4 |
deltaNext = nextElement(patchNext); |
227 |
|
} else { |
228 |
15 |
if (deltaCurrent.getType() == Type.INSERT && deltaCurrent.getPrevious().getIndex() == 0) { |
229 |
2 |
merged.addAll(deltaCurrent.getNext().getElements()); |
230 |
2 |
deltaCurrent = nextElement(patchCurrent); |
231 |
|
} |
232 |
|
|
233 |
15 |
if (deltaNext.getType() == Type.INSERT && deltaNext.getPrevious().getIndex() == 0) { |
234 |
2 |
merged.addAll(deltaNext.getNext().getElements()); |
235 |
2 |
deltaNext = nextElement(patchNext); |
236 |
|
} |
237 |
|
} |
238 |
|
|
239 |
|
|
240 |
19 |
int index = 0; |
241 |
65 |
for (; index < commonAncestor.size(); ++index) { |
242 |
46 |
if (isPreviousIndex(deltaCurrent, index)) { |
243 |
|
|
244 |
9 |
if (isPreviousIndex(deltaNext, index)) { |
245 |
|
|
246 |
6 |
if (deltaNext.equals(deltaCurrent)) { |
247 |
|
|
248 |
2 |
index = apply(deltaCurrent, merged, index); |
249 |
2 |
if (deltaCurrent.getType() == Type.INSERT) { |
250 |
0 |
merged.add(commonAncestor.get(index)); |
251 |
|
} |
252 |
4 |
} else if (deltaCurrent.getType() == Type.INSERT) { |
253 |
3 |
if (deltaNext.getType() == Type.INSERT) { |
254 |
|
|
255 |
3 |
logConflict(mergeResult, deltaCurrent, deltaNext); |
256 |
|
|
257 |
3 |
merged.addAll(or(deltaNext.getNext().getElements(), deltaCurrent.getNext().getElements())); |
258 |
3 |
merged.add(commonAncestor.get(index)); |
259 |
|
} else { |
260 |
0 |
index = apply(deltaCurrent, merged, index); |
261 |
0 |
index = apply(deltaNext, merged, index); |
262 |
|
} |
263 |
1 |
} else if (deltaNext.getType() == Type.INSERT) { |
264 |
1 |
index = apply(deltaNext, merged, index); |
265 |
1 |
index = apply(deltaCurrent, merged, index); |
266 |
|
} else { |
267 |
|
|
268 |
0 |
logConflict(mergeResult, deltaCurrent, deltaNext); |
269 |
|
|
270 |
0 |
index = fallback(commonAncestor, deltaNext, deltaCurrent, merged, index, configuration); |
271 |
|
} |
272 |
|
|
273 |
6 |
deltaNext = nextElement(patchNext); |
274 |
|
} else { |
275 |
3 |
index = apply(deltaCurrent, merged, index); |
276 |
3 |
if (deltaCurrent.getType() == Type.INSERT) { |
277 |
1 |
merged.add(commonAncestor.get(index)); |
278 |
|
} |
279 |
|
|
280 |
3 |
if (deltaNext != null |
281 |
|
&& deltaNext.getPrevious().getIndex() <= deltaCurrent.getPrevious().getLastIndex()) { |
282 |
|
|
283 |
2 |
logConflict(mergeResult, deltaCurrent, deltaNext); |
284 |
2 |
deltaNext = nextElement(patchNext); |
285 |
|
} |
286 |
|
} |
287 |
|
|
288 |
9 |
deltaCurrent = nextElement(patchCurrent); |
289 |
37 |
} else if (isPreviousIndex(deltaNext, index)) { |
290 |
|
|
291 |
3 |
index = apply(deltaNext, merged, index); |
292 |
3 |
if (deltaNext.getType() == Type.INSERT) { |
293 |
1 |
merged.add(commonAncestor.get(index)); |
294 |
|
} |
295 |
|
|
296 |
3 |
if (deltaCurrent != null |
297 |
|
&& deltaCurrent.getPrevious().getIndex() <= deltaNext.getPrevious().getLastIndex()) { |
298 |
|
|
299 |
2 |
logConflict(mergeResult, deltaCurrent, deltaNext); |
300 |
2 |
deltaCurrent = nextElement(patchCurrent); |
301 |
|
} |
302 |
|
|
303 |
3 |
deltaNext = nextElement(patchNext); |
304 |
|
} else { |
305 |
34 |
merged.add(commonAncestor.get(index)); |
306 |
|
} |
307 |
|
} |
308 |
|
|
309 |
|
|
310 |
19 |
if (deltaCurrent != null) { |
311 |
6 |
merged.addAll(deltaCurrent.getNext().getElements()); |
312 |
|
|
313 |
6 |
if (deltaNext != null && !deltaCurrent.equals(deltaNext)) { |
314 |
1 |
merged.addAll(deltaNext.getNext().getElements()); |
315 |
|
} |
316 |
13 |
} else if (deltaNext != null) { |
317 |
4 |
merged.addAll(deltaNext.getNext().getElements()); |
318 |
|
} |
319 |
|
} |
320 |
|
|
|
|
| 96% |
Uncovered Elements: 1 (25) |
Complexity: 6 |
Complexity Density: 0.35 |
|
321 |
7 |
private <E> List<E> or(List<E> previous, List<E> next) throws MergeException... |
322 |
|
{ |
323 |
7 |
DiffResult<E> diffCurrentResult; |
324 |
7 |
try { |
325 |
7 |
diffCurrentResult = diff(previous, next, null); |
326 |
|
} catch (DiffException e) { |
327 |
0 |
throw new MergeException("Faile to diff between two versions", e); |
328 |
|
} |
329 |
|
|
330 |
7 |
List<E> result = new ArrayList<E>(previous.size() + next.size()); |
331 |
7 |
int index = 0; |
332 |
7 |
for (Delta<E> delta : diffCurrentResult.getPatch()) { |
333 |
7 |
if (delta.getPrevious().getIndex() > index) { |
334 |
3 |
result.addAll(previous.subList(index, delta.getPrevious().getIndex())); |
335 |
|
} |
336 |
|
|
337 |
7 |
if (delta.getType() != Type.INSERT) { |
338 |
4 |
result.addAll(delta.getPrevious().getElements()); |
339 |
|
} |
340 |
7 |
if (delta.getType() != Type.DELETE) { |
341 |
4 |
result.addAll(delta.getNext().getElements()); |
342 |
|
} |
343 |
|
|
344 |
7 |
index = delta.getPrevious().getLastIndex() + 1; |
345 |
|
} |
346 |
|
|
347 |
7 |
if (previous.size() > index) { |
348 |
5 |
result.addAll(previous.subList(index, previous.size())); |
349 |
|
} |
350 |
|
|
351 |
7 |
return result; |
352 |
|
} |
353 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (1) |
Complexity: 1 |
Complexity Density: 1 |
|
354 |
11 |
private <E> void logConflict(DefaultMergeResult<E> mergeResult, Delta<E> deltaCurrent, Delta<E> deltaNext)... |
355 |
|
{ |
356 |
11 |
mergeResult.getLog().error("Conflict between [{}] and [{}]", deltaCurrent, deltaNext); |
357 |
|
} |
358 |
|
|
|
|
| 66.7% |
Uncovered Elements: 5 (15) |
Complexity: 4 |
Complexity Density: 0.27 |
|
359 |
10 |
private <E> int apply(Delta<E> delta, List<E> merged, int currentIndex)... |
360 |
|
{ |
361 |
10 |
int index = currentIndex; |
362 |
|
|
363 |
10 |
switch (delta.getType()) { |
364 |
0 |
case DELETE: |
365 |
0 |
index = delta.getPrevious().getLastIndex(); |
366 |
0 |
break; |
367 |
3 |
case INSERT: |
368 |
3 |
merged.addAll(delta.getNext().getElements()); |
369 |
3 |
break; |
370 |
7 |
case CHANGE: |
371 |
7 |
merged.addAll(delta.getNext().getElements()); |
372 |
7 |
index = delta.getPrevious().getLastIndex(); |
373 |
7 |
break; |
374 |
0 |
default: |
375 |
0 |
break; |
376 |
|
} |
377 |
|
|
378 |
10 |
return index; |
379 |
|
} |
380 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (3) |
Complexity: 3 |
Complexity Density: 3 |
|
381 |
80 |
private <E> E nextElement(List<E> list)... |
382 |
|
{ |
383 |
80 |
return list != null && !list.isEmpty() ? list.remove(0) : null; |
384 |
|
} |
385 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (1) |
Complexity: 1 |
Complexity Density: 1 |
|
386 |
92 |
private <E> boolean isPreviousIndex(Delta<E> delta, int index)... |
387 |
|
{ |
388 |
92 |
return delta != null && delta.getPrevious().getIndex() == index; |
389 |
|
} |
390 |
|
|
391 |
|
|
392 |
|
|
393 |
|
|
394 |
|
@param |
395 |
|
@param |
396 |
|
@param |
397 |
|
@return |
398 |
|
|
|
|
| 100% |
Uncovered Elements: 0 (1) |
Complexity: 1 |
Complexity Density: 1 |
|
399 |
24 |
private <E> boolean isFullyModified(List commonAncestor, Patch<E> patchCurrent) {... |
400 |
24 |
return patchCurrent.size() == 1 && commonAncestor.size() == patchCurrent.get(0).getPrevious().size(); |
401 |
|
} |
402 |
|
} |