1. Project Clover database Mon Aug 5 2019 23:32:56 UTC
  2. Package org.xwiki.diff.internal

File DefaultDiffManager.java

 

Coverage histogram

../../../../img/srcFileCovDistChart8.png
42% of files have more coverage

Code metrics

76
166
11
1
402
283
71
0.43
15.09
11
6.45

Classes

Class Line # Actions
DefaultDiffManager 50 166 0% 71 52
0.794466479.4%
 

Contributing tests

This file is covered by 34 tests. .

Source view

1    /*
2    * See the NOTICE file distributed with this work for additional
3    * information regarding copyright ownership.
4    *
5    * This is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU Lesser General Public License as
7    * published by the Free Software Foundation; either version 2.1 of
8    * the License, or (at your option) any later version.
9    *
10    * This software is distributed in the hope that it will be useful,
11    * but WITHOUT ANY WARRANTY; without even the implied warranty of
12    * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13    * Lesser General Public License for more details.
14    *
15    * You should have received a copy of the GNU Lesser General Public
16    * License along with this software; if not, write to the Free
17    * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
18    * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
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    * Default implementation of {@link DiffManager}.
45    *
46    * @version $Id: 4373f1af04086578915e3044658df4073e8b46a8 $
47    */
48    @Component
49    @Singleton
 
50    public class DefaultDiffManager implements DiffManager
51    {
 
52  107 toggle @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    // DiffUtils#diff does not support null
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   
 
78  31 toggle @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    // Get diff between common ancestor and next version
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    // If there is no modification stop there
97   
98  31 if (patchNext.isEmpty()) {
99    // No change so nothing to do
100  1 return mergeResult;
101    }
102   
103    // Check current version
104   
105  30 if (current.isEmpty()) {
106    // Empty current version
107  1 if (commonAncestor.isEmpty()) {
108  0 mergeResult.setMerged(next);
109  1 } else if (next.isEmpty()) {
110    // The new modification was already applied
111  0 mergeResult.getLog().warn("The modification was already applied");
112    } else {
113    // The current version has been replaced by an empty string
114  1 mergeResult.getLog().error("The current value is empty");
115    }
116    } else {
117    // Get diff between common ancestor and current version
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    // If current is completely modified compared to the common ancestor we assume any change in next is
132    // a conflict
133    // ... except if the current content is identical to the next one!
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   
 
148  5 toggle 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   
 
168  0 toggle 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    // CURRENT is the default
194  0 newIndex = apply(deltaCurrent, merged, currentIndex);
195  0 break;
196    }
197   
198  0 return newIndex;
199    }
200   
201    /**
202    * @param <E> the type of compared elements
203    * @param mergeResult the result of the merge
204    * @param commonAncestor the common ancestor of the two versions of the content to compare
205    * @param patchNext the diff between common ancestor and next version
206    * @param patchCurrent the diff between common ancestor and current version
207    * @param configuration the configuration of the merge behavior
208    * @throws MergeException failed to merge
209    */
 
210  19 toggle private <E> void merge(DefaultMergeResult<E> mergeResult, List<E> commonAncestor, Patch<E> patchNext,
211    Patch<E> patchCurrent, MergeConfiguration<E> configuration) throws MergeException
212    {
213    // Merge the two diffs
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    // Before common ancestor
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    // In common ancestor
240  19 int index = 0;
241  65 for (; index < commonAncestor.size(); ++index) {
242  46 if (isPreviousIndex(deltaCurrent, index)) {
243    // Modification in current
244  9 if (isPreviousIndex(deltaNext, index)) {
245    // Modifications in both current and next at the same index
246  6 if (deltaNext.equals(deltaCurrent)) {
247    // Choose current
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    // Conflict
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    // Conflict
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    // Conflict
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    // Modification in next
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    // Conflict
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    // After common ancestor
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   
 
321  7 toggle 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   
 
354  11 toggle 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   
 
359  10 toggle 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   
 
381  80 toggle private <E> E nextElement(List<E> list)
382    {
383  80 return list != null && !list.isEmpty() ? list.remove(0) : null;
384    }
385   
 
386  92 toggle private <E> boolean isPreviousIndex(Delta<E> delta, int index)
387    {
388  92 return delta != null && delta.getPrevious().getIndex() == index;
389    }
390   
391    /**
392    * Check if the content is completely different between the ancestor and the current version
393    *
394    * @param <E> the type of compared elements
395    * @param commonAncestor previous version
396    * @param patchCurrent patch to the current version
397    * @return either or not the user has changed everything
398    */
 
399  24 toggle private <E> boolean isFullyModified(List commonAncestor, Patch<E> patchCurrent) {
400  24 return patchCurrent.size() == 1 && commonAncestor.size() == patchCurrent.get(0).getPrevious().size();
401    }
402    }