1. Project Clover database Tue Dec 20 2016 21:24:09 CET
  2. Package org.xwiki.diff.internal

File DefaultDiffManager.java

 

Coverage histogram

../../../../img/srcFileCovDistChart9.png
38% of files have more coverage

Code metrics

70
147
9
1
357
254
64
0.44
16.33
9
7.11

Classes

Class Line # Actions
DefaultDiffManager 50 147 0% 64 34
0.849557585%
 

Contributing tests

This file is covered by 59 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: fb41c247815507409093107c6ef9c3f6c21dd870 $
47    */
48    @Component
49    @Singleton
 
50    public class DefaultDiffManager implements DiffManager
51    {
 
52  310 toggle @Override
53    public <E> DiffResult<E> diff(List<E> previous, List<E> next, DiffConfiguration<E> diff) throws DiffException
54    {
55  310 DefaultDiffResult<E> result = new DefaultDiffResult<E>(previous, next);
56   
57    // DiffUtils#diff does not support null
58  310 Patch<E> patch;
59  310 if (previous == null || previous.isEmpty()) {
60  142 patch = new DefaultPatch<E>();
61  142 if (next != null && !next.isEmpty()) {
62  19 patch.add(new InsertDelta<E>(new DefaultChunk<E>(0, Collections.<E>emptyList()), new DefaultChunk<E>(
63    0, next)));
64    }
65  168 } else if (next == null || next.isEmpty()) {
66  7 patch = new DefaultPatch<E>();
67  7 patch.add(new DeleteDelta<E>(new DefaultChunk<E>(0, previous), new DefaultChunk<E>(0, Collections
68    .<E>emptyList())));
69    } else {
70  161 patch = new DefaultPatch<E>(DiffUtils.diff(previous, next));
71    }
72   
73  310 result.setPatch(patch);
74   
75  310 return result;
76    }
77   
 
78  198 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  198 DefaultMergeResult<E> mergeResult = new DefaultMergeResult<E>(commonAncestor, next, current);
83   
84    // Get diff between common ancestor and next version
85   
86  198 DiffResult<E> diffNextResult;
87  198 try {
88  198 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  198 mergeResult.getLog().addAll(diffNextResult.getLog());
93   
94  198 Patch<E> patchNext = diffNextResult.getPatch();
95   
96    // If there is no modification stop there
97   
98  198 if (patchNext.isEmpty()) {
99    // No change so nothing to do
100  140 return mergeResult;
101    }
102   
103    // Check current version
104   
105  58 if (current.isEmpty()) {
106    // Empty current version
107  8 if (commonAncestor.isEmpty()) {
108  8 mergeResult.setMerged(next);
109  0 } 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  0 mergeResult.getLog().error("The current value is empty");
115    }
116    } else {
117    // Get diff between common ancestor and current version
118  50 DiffResult<E> diffCurrentResult;
119  50 try {
120  50 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  50 mergeResult.getLog().addAll(diffCurrentResult.getLog());
125   
126  50 Patch<E> patchCurrent = diffCurrentResult.getPatch();
127   
128  50 if (patchCurrent.isEmpty()) {
129  21 mergeResult.setMerged(next);
130    } else {
131  29 merge(mergeResult, commonAncestor, patchNext, patchCurrent, configuration);
132    }
133    }
134   
135  58 return mergeResult;
136    }
137   
 
138  6 toggle private <E> int fallback(List<E> commonAncestor, Delta<E> deltaNext, Delta<E> deltaCurrent, List<E> merged,
139    int currentIndex, MergeConfiguration<E> configuration)
140    {
141  6 int newIndex = currentIndex;
142   
143  6 Version fallbackVersion;
144  6 if (configuration != null) {
145  0 fallbackVersion = configuration.getFallbackOnConflict();
146    } else {
147  6 fallbackVersion = Version.CURRENT;
148    }
149   
150  6 switch (fallbackVersion) {
151  0 case NEXT:
152  0 newIndex = apply(deltaNext, merged, currentIndex);
153  0 break;
154  0 case PREVIOUS:
155  0 for (; newIndex < deltaNext.getPrevious().getIndex(); ++newIndex) {
156  0 merged.add(commonAncestor.get(newIndex));
157    }
158  0 for (; newIndex < deltaCurrent.getPrevious().getIndex(); ++newIndex) {
159  0 merged.add(commonAncestor.get(newIndex));
160    }
161  0 break;
162  6 default:
163    // CURRENT is the default
164  6 newIndex = apply(deltaCurrent, merged, currentIndex);
165  6 break;
166    }
167   
168  6 return newIndex;
169    }
170   
171    /**
172    * @param <E> the type of compared elements
173    * @param mergeResult the result of the merge
174    * @param commonAncestor the common ancestor of the two versions of the content to compare
175    * @param patchNext the diff between common ancestor and next version
176    * @param patchCurrent the diff between common ancestor and current version
177    * @param configuration the configuration of the merge behavior
178    * @throws MergeException failed to merge
179    */
 
180  29 toggle private <E> void merge(DefaultMergeResult<E> mergeResult, List<E> commonAncestor, Patch<E> patchNext,
181    Patch<E> patchCurrent, MergeConfiguration<E> configuration) throws MergeException
182    {
183    // Merge the two diffs
184  29 List<E> merged = new ArrayList<E>();
185   
186  29 mergeResult.setMerged(merged);
187   
188  29 Delta<E> deltaNext = nextElement(patchNext);
189  29 Delta<E> deltaCurrent = nextElement(patchCurrent);
190   
191    // Before common ancestor
192  29 if (deltaCurrent.getType() == Type.INSERT && deltaCurrent.getPrevious().getIndex() == 0
193    && deltaNext.getType() == Type.INSERT && deltaNext.getPrevious().getIndex() == 0) {
194  4 merged.addAll(or(deltaCurrent.getNext().getElements(), deltaNext.getNext().getElements()));
195  4 deltaCurrent = nextElement(patchCurrent);
196  4 deltaNext = nextElement(patchNext);
197    } else {
198  25 if (deltaCurrent.getType() == Type.INSERT && deltaCurrent.getPrevious().getIndex() == 0) {
199  3 merged.addAll(deltaCurrent.getNext().getElements());
200  3 deltaCurrent = nextElement(patchCurrent);
201    }
202   
203  25 if (deltaNext.getType() == Type.INSERT && deltaNext.getPrevious().getIndex() == 0) {
204  2 merged.addAll(deltaNext.getNext().getElements());
205  2 deltaNext = nextElement(patchNext);
206    }
207    }
208   
209    // In common ancestor
210  29 int index = 0;
211  89 for (; index < commonAncestor.size(); ++index) {
212  60 if (isPreviousIndex(deltaCurrent, index)) {
213    // Modification in current
214  20 if (isPreviousIndex(deltaNext, index)) {
215    // Modifications in both current and next at the same index
216  16 if (deltaNext.equals(deltaCurrent)) {
217    // Choose current
218  6 index = apply(deltaCurrent, merged, index);
219  6 if (deltaCurrent.getType() == Type.INSERT) {
220  0 merged.add(commonAncestor.get(index));
221    }
222  10 } else if (deltaCurrent.getType() == Type.INSERT) {
223  3 if (deltaNext.getType() == Type.INSERT) {
224  3 merged.addAll(or(deltaNext.getNext().getElements(), deltaCurrent.getNext().getElements()));
225  3 merged.add(commonAncestor.get(index));
226    } else {
227  0 index = apply(deltaCurrent, merged, index);
228  0 index = apply(deltaNext, merged, index);
229    }
230  7 } else if (deltaNext.getType() == Type.INSERT) {
231  1 index = apply(deltaNext, merged, index);
232  1 index = apply(deltaCurrent, merged, index);
233    } else {
234    // Conflict
235  6 logConflict(mergeResult, deltaCurrent, deltaNext);
236   
237  6 index = fallback(commonAncestor, deltaNext, deltaCurrent, merged, index, configuration);
238    }
239   
240  16 deltaNext = nextElement(patchNext);
241    } else {
242  4 index = apply(deltaCurrent, merged, index);
243  4 if (deltaCurrent.getType() == Type.INSERT) {
244  1 merged.add(commonAncestor.get(index));
245    }
246   
247  4 if (deltaNext != null
248    && deltaNext.getPrevious().getIndex() <= deltaCurrent.getPrevious().getLastIndex()) {
249    // Conflict
250  2 logConflict(mergeResult, deltaCurrent, deltaNext);
251  2 deltaNext = nextElement(patchNext);
252    }
253    }
254   
255  20 deltaCurrent = nextElement(patchCurrent);
256  40 } else if (isPreviousIndex(deltaNext, index)) {
257    // Modification in next
258  4 index = apply(deltaNext, merged, index);
259  4 if (deltaNext.getType() == Type.INSERT) {
260  2 merged.add(commonAncestor.get(index));
261    }
262   
263  4 if (deltaCurrent != null
264    && deltaCurrent.getPrevious().getIndex() <= deltaNext.getPrevious().getLastIndex()) {
265    // Conflict
266  2 logConflict(mergeResult, deltaCurrent, deltaNext);
267  2 deltaCurrent = nextElement(patchCurrent);
268    }
269   
270  4 deltaNext = nextElement(patchNext);
271    } else {
272  36 merged.add(commonAncestor.get(index));
273    }
274    }
275   
276    // After common ancestor
277  29 if (deltaCurrent != null) {
278  6 merged.addAll(deltaCurrent.getNext().getElements());
279   
280  6 if (deltaNext != null && !deltaCurrent.equals(deltaNext)) {
281  1 merged.addAll(deltaNext.getNext().getElements());
282    }
283  23 } else if (deltaNext != null) {
284  5 merged.addAll(deltaNext.getNext().getElements());
285    }
286    }
287   
 
288  7 toggle private <E> List<E> or(List<E> previous, List<E> next) throws MergeException
289    {
290  7 DiffResult<E> diffCurrentResult;
291  7 try {
292  7 diffCurrentResult = diff(previous, next, null);
293    } catch (DiffException e) {
294  0 throw new MergeException("Faile to diff between two versions", e);
295    }
296   
297  7 List<E> result = new ArrayList<E>(previous.size() + next.size());
298  7 int index = 0;
299  7 for (Delta<E> delta : diffCurrentResult.getPatch()) {
300  7 if (delta.getPrevious().getIndex() > index) {
301  3 result.addAll(previous.subList(index, delta.getPrevious().getIndex()));
302    }
303   
304  7 if (delta.getType() != Type.INSERT) {
305  4 result.addAll(delta.getPrevious().getElements());
306    }
307  7 if (delta.getType() != Type.DELETE) {
308  4 result.addAll(delta.getNext().getElements());
309    }
310   
311  7 index = delta.getPrevious().getLastIndex() + 1;
312    }
313   
314  7 if (previous.size() > index) {
315  3 result.addAll(previous.subList(index, previous.size()));
316    }
317   
318  7 return result;
319    }
320   
 
321  10 toggle private <E> void logConflict(DefaultMergeResult<E> mergeResult, Delta<E> deltaCurrent, Delta<E> deltaNext)
322    {
323  10 mergeResult.getLog().error("Conflict between [{}] and [{}]", deltaCurrent, deltaNext);
324    }
325   
 
326  22 toggle private <E> int apply(Delta<E> delta, List<E> merged, int currentIndex)
327    {
328  22 int index = currentIndex;
329   
330  22 switch (delta.getType()) {
331  0 case DELETE:
332  0 index = delta.getPrevious().getLastIndex();
333  0 break;
334  4 case INSERT:
335  4 merged.addAll(delta.getNext().getElements());
336  4 break;
337  18 case CHANGE:
338  18 merged.addAll(delta.getNext().getElements());
339  18 index = delta.getPrevious().getLastIndex();
340  18 break;
341  0 default:
342  0 break;
343    }
344   
345  22 return index;
346    }
347   
 
348  115 toggle private <E> E nextElement(List<E> list)
349    {
350  115 return list != null && !list.isEmpty() ? list.remove(0) : null;
351    }
352   
 
353  120 toggle private <E> boolean isPreviousIndex(Delta<E> delta, int index)
354    {
355  120 return delta != null && delta.getPrevious().getIndex() == index;
356    }
357    }