1. Project Clover database Sat Feb 2 2019 06:45:20 CET
  2. Package org.xwiki.diff.internal

File DefaultDiffManager.java

 

Coverage histogram

../../../../img/srcFileCovDistChart9.png
41% 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 38
0.849802485%
 

Contributing tests

This file is covered by 58 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  232 toggle @Override
53    public <E> DiffResult<E> diff(List<E> previous, List<E> next, DiffConfiguration<E> diff) throws DiffException
54    {
55  232 DefaultDiffResult<E> result = new DefaultDiffResult<E>(previous, next);
56   
57    // DiffUtils#diff does not support null
58  232 Patch<E> patch;
59  232 if (previous == null || previous.isEmpty()) {
60  93 patch = new DefaultPatch<E>();
61  93 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  139 } 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  134 patch = new DefaultPatch<E>(DiffUtils.diff(previous, next));
71    }
72   
73  232 result.setPatch(patch);
74   
75  232 return result;
76    }
77   
 
78  131 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  131 DefaultMergeResult<E> mergeResult = new DefaultMergeResult<E>(commonAncestor, next, current);
83   
84    // Get diff between common ancestor and next version
85   
86  131 DiffResult<E> diffNextResult;
87  131 try {
88  131 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  131 mergeResult.getLog().addAll(diffNextResult.getLog());
93   
94  131 Patch<E> patchNext = diffNextResult.getPatch();
95   
96    // If there is no modification stop there
97   
98  131 if (patchNext.isEmpty()) {
99    // No change so nothing to do
100  91 return mergeResult;
101    }
102   
103    // Check current version
104   
105  40 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  39 DiffResult<E> diffCurrentResult;
119  39 try {
120  39 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  39 mergeResult.getLog().addAll(diffCurrentResult.getLog());
125   
126  39 Patch<E> patchCurrent = diffCurrentResult.getPatch();
127   
128  39 if (patchCurrent.isEmpty()) {
129  9 mergeResult.setMerged(next);
130  30 } 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  9 if (!current.equals(next)) {
135  6 Delta<E> deltaNext = nextElement(patchNext);
136  6 Delta<E> deltaCurrent = nextElement(patchCurrent);
137  6 logConflict(mergeResult, deltaCurrent, deltaNext);
138    }
139  9 mergeResult.setMerged(fallback(commonAncestor, next, current, configuration));
140    } else {
141  21 merge(mergeResult, commonAncestor, patchNext, patchCurrent, configuration);
142    }
143    }
144   
145  40 return mergeResult;
146    }
147   
 
148  9 toggle private <E> List<E> fallback(List<E> commonAncestor, List<E> next, List<E> current,
149    MergeConfiguration<E> configuration)
150    {
151  9 Version fallbackVersion;
152  9 if (configuration != null) {
153  0 fallbackVersion = configuration.getFallbackOnConflict();
154    } else {
155  9 fallbackVersion = Version.CURRENT;
156    }
157   
158  9 switch (fallbackVersion) {
159  0 case NEXT:
160  0 return next;
161  0 case PREVIOUS:
162  0 return commonAncestor;
163  9 default:
164  9 return current;
165    }
166    }
167   
 
168  1 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  1 int newIndex = currentIndex;
172   
173  1 Version fallbackVersion;
174  1 if (configuration != null) {
175  0 fallbackVersion = configuration.getFallbackOnConflict();
176    } else {
177  1 fallbackVersion = Version.CURRENT;
178    }
179   
180  1 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  1 default:
193    // CURRENT is the default
194  1 newIndex = apply(deltaCurrent, merged, currentIndex);
195  1 break;
196    }
197   
198  1 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  21 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  21 List<E> merged = new ArrayList<E>();
215   
216  21 mergeResult.setMerged(merged);
217   
218  21 Delta<E> deltaNext = nextElement(patchNext);
219  21 Delta<E> deltaCurrent = nextElement(patchCurrent);
220   
221    // Before common ancestor
222  21 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  17 if (deltaCurrent.getType() == Type.INSERT && deltaCurrent.getPrevious().getIndex() == 0) {
229  3 merged.addAll(deltaCurrent.getNext().getElements());
230  3 deltaCurrent = nextElement(patchCurrent);
231    }
232   
233  17 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  21 int index = 0;
241  77 for (; index < commonAncestor.size(); ++index) {
242  56 if (isPreviousIndex(deltaCurrent, index)) {
243    // Modification in current
244  12 if (isPreviousIndex(deltaNext, index)) {
245    // Modifications in both current and next at the same index
246  8 if (deltaNext.equals(deltaCurrent)) {
247    // Choose current
248  3 index = apply(deltaCurrent, merged, index);
249  3 if (deltaCurrent.getType() == Type.INSERT) {
250  0 merged.add(commonAncestor.get(index));
251    }
252  5 } 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  2 } 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  1 logConflict(mergeResult, deltaCurrent, deltaNext);
269   
270  1 index = fallback(commonAncestor, deltaNext, deltaCurrent, merged, index, configuration);
271    }
272   
273  8 deltaNext = nextElement(patchNext);
274    } else {
275  4 index = apply(deltaCurrent, merged, index);
276  4 if (deltaCurrent.getType() == Type.INSERT) {
277  1 merged.add(commonAncestor.get(index));
278    }
279   
280  4 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  12 deltaCurrent = nextElement(patchCurrent);
289  44 } else if (isPreviousIndex(deltaNext, index)) {
290    // Modification in next
291  4 index = apply(deltaNext, merged, index);
292  4 if (deltaNext.getType() == Type.INSERT) {
293  2 merged.add(commonAncestor.get(index));
294    }
295   
296  4 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  4 deltaNext = nextElement(patchNext);
304    } else {
305  40 merged.add(commonAncestor.get(index));
306    }
307    }
308   
309    // After common ancestor
310  21 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  15 } else if (deltaNext != null) {
317  5 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  14 toggle private <E> void logConflict(DefaultMergeResult<E> mergeResult, Delta<E> deltaCurrent, Delta<E> deltaNext)
355    {
356  14 mergeResult.getLog().error("Conflict between [{}] and [{}]", deltaCurrent, deltaNext);
357    }
358   
 
359  14 toggle private <E> int apply(Delta<E> delta, List<E> merged, int currentIndex)
360    {
361  14 int index = currentIndex;
362   
363  14 switch (delta.getType()) {
364  0 case DELETE:
365  0 index = delta.getPrevious().getLastIndex();
366  0 break;
367  4 case INSERT:
368  4 merged.addAll(delta.getNext().getElements());
369  4 break;
370  10 case CHANGE:
371  10 merged.addAll(delta.getNext().getElements());
372  10 index = delta.getPrevious().getLastIndex();
373  10 break;
374  0 default:
375  0 break;
376    }
377   
378  14 return index;
379    }
380   
 
381  95 toggle private <E> E nextElement(List<E> list)
382    {
383  95 return list != null && !list.isEmpty() ? list.remove(0) : null;
384    }
385   
 
386  112 toggle private <E> boolean isPreviousIndex(Delta<E> delta, int index)
387    {
388  112 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  30 toggle private <E> boolean isFullyModified(List commonAncestor, Patch<E> patchCurrent) {
400  30 return patchCurrent.size() == 1 && commonAncestor.size() == patchCurrent.get(0).getPrevious().size();
401    }
402    }