1   /**
2    * Copyright (c) 2000-2010 Liferay, Inc. All rights reserved.
3    *
4    * The contents of this file are subject to the terms of the Liferay Enterprise
5    * Subscription License ("License"). You may not use this file except in
6    * compliance with the License. You can obtain a copy of the License by
7    * contacting Liferay, Inc. See the License for the specific language governing
8    * permissions and limitations under the License, including but not limited to
9    * distribution rights of the Software.
10   *
11   *
12   *
13   */
14  
15  package com.liferay.portal.util;
16  
17  import com.liferay.portal.kernel.util.DiffResult;
18  import com.liferay.portal.kernel.util.FileUtil;
19  import com.liferay.portal.kernel.util.StringBundler;
20  import com.liferay.portal.kernel.util.StringPool;
21  
22  import java.io.Reader;
23  
24  import java.util.ArrayList;
25  import java.util.Iterator;
26  import java.util.List;
27  
28  import org.incava.util.diff.Diff;
29  import org.incava.util.diff.Difference;
30  
31  /**
32   * <a href="DiffImpl.java.html"><b><i>View Source</i></b></a>
33   *
34   * <p>
35   * This class can compare two different versions of a text. Source refers to the
36   * earliest version of the text and target refers to a modified version of
37   * source. Changes are considered either as a removal from the source or as an
38   * addition to the target. This class detects changes to an entire line and also
39   * detects changes within lines, such as, removal or addition of characters.
40   * Take a look at <code>DiffTest</code> to see the expected inputs and outputs.
41   * </p>
42   *
43   * @author Bruno Farache
44   */
45  public class DiffImpl implements com.liferay.portal.kernel.util.Diff {
46  
47      /**
48       * This is a diff method with default values.
49       *
50       * @return an array containing two lists of <code>DiffResults</code>, the
51       *         first element contains DiffResults related to changes in source
52       *         and the second element to changes in target
53       */
54      public List<DiffResult>[] diff(Reader source, Reader target) {
55          int margin = 2;
56  
57          return diff(
58              source, target, OPEN_INS, CLOSE_INS, OPEN_DEL, CLOSE_DEL, margin);
59      }
60  
61      /**
62       * The main entrance of this class. This method will compare the two texts,
63       * highlight the changes by enclosing them with markers and return a list of
64       * <code>DiffResults</code>.
65       *
66       * @return an array containing two lists of <code>DiffResults</code>, the
67       *         first element contains DiffResults related to changes in source
68       *         and the second element to changes in target
69       */
70      public List<DiffResult>[] diff(
71          Reader source, Reader target, String addedMarkerStart,
72          String addedMarkerEnd, String deletedMarkerStart,
73          String deletedMarkerEnd, int margin) {
74  
75          List<DiffResult> sourceResults = new ArrayList<DiffResult>();
76          List<DiffResult> targetResults = new ArrayList<DiffResult>();
77  
78          List<DiffResult>[] results = new List[] {sourceResults, targetResults};
79  
80          // Convert the texts to Lists where each element are lines of the texts.
81  
82          List<String> sourceStringList = FileUtil.toList(source);
83          List<String> targetStringList = FileUtil.toList(target);
84  
85          // Make a a Diff of these lines and iterate over their Differences.
86  
87          Diff diff = new Diff(sourceStringList, targetStringList);
88  
89          List<Difference> differences = diff.diff();
90  
91          Iterator<Difference> itr = differences.iterator();
92  
93          while (itr.hasNext()) {
94              Difference difference = itr.next();
95  
96              if (difference.getAddedEnd() == Difference.NONE) {
97  
98                  // Lines were deleted from source only.
99  
100                 _highlightLines(
101                     sourceStringList, deletedMarkerStart,
102                     deletedMarkerEnd, difference.getDeletedStart(),
103                     difference.getDeletedEnd());
104 
105                 margin = _calculateMargin(
106                     sourceResults, targetResults, difference.getDeletedStart(),
107                     difference.getAddedStart(), margin);
108 
109                 List<String> changedLines = _addMargins(
110                     sourceResults, sourceStringList,
111                     difference.getDeletedStart(), margin);
112 
113                 _addResults(
114                     sourceResults, sourceStringList, changedLines,
115                     difference.getDeletedStart(), difference.getDeletedEnd());
116 
117                 changedLines = _addMargins(
118                     targetResults, targetStringList, difference.getAddedStart(),
119                     margin);
120 
121                 int deletedLines =
122                     difference.getDeletedEnd() + 1 -
123                         difference.getDeletedStart();
124 
125                 for (int i = 0; i < deletedLines; i++) {
126                     changedLines.add(CONTEXT_LINE);
127                 }
128 
129                 DiffResult diffResult = new DiffResult(
130                     difference.getDeletedStart(), changedLines);
131 
132                 targetResults.add(diffResult);
133             }
134             else if (difference.getDeletedEnd() == Difference.NONE) {
135 
136                 // Lines were added to target only.
137 
138                 _highlightLines(
139                     targetStringList, addedMarkerStart, addedMarkerEnd,
140                     difference.getAddedStart(), difference.getAddedEnd());
141 
142                 margin = _calculateMargin(
143                     sourceResults, targetResults, difference.getDeletedStart(),
144                     difference.getAddedStart(), margin);
145 
146                 List<String> changedLines = _addMargins(
147                     sourceResults, sourceStringList,
148                     difference.getDeletedStart(), margin);
149 
150                 int addedLines =
151                     difference.getAddedEnd() + 1 - difference.getAddedStart();
152 
153                 for (int i = 0; i < addedLines; i++) {
154                     changedLines.add(CONTEXT_LINE);
155                 }
156 
157                 DiffResult diffResult = new DiffResult(
158                     difference.getAddedStart(), changedLines);
159 
160                 sourceResults.add(diffResult);
161 
162                 changedLines = _addMargins(
163                     targetResults, targetStringList, difference.getAddedStart(),
164                     margin);
165 
166                 _addResults(
167                     targetResults, targetStringList, changedLines,
168                     difference.getAddedStart(), difference.getAddedEnd());
169             }
170             else {
171 
172                 // Lines were deleted from source and added to target at the
173                 // same position. It needs to check for characters differences.
174 
175                 _checkCharDiffs(
176                     sourceResults, targetResults, sourceStringList,
177                     targetStringList, addedMarkerStart, addedMarkerEnd,
178                     deletedMarkerStart, deletedMarkerEnd, difference, margin);
179             }
180         }
181 
182         return results;
183     }
184 
185     private static List<String> _addMargins(
186         List<DiffResult> results, List<String> stringList, int startPos,
187         int margin) {
188 
189         List<String> changedLines = new ArrayList<String>();
190 
191         if (margin == 0 || startPos == 0) {
192             return changedLines;
193         }
194 
195         int i = startPos - margin;
196 
197         for (; i < 0; i++) {
198             changedLines.add(CONTEXT_LINE);
199         }
200 
201         for (; i < startPos; i++) {
202             if (i < stringList.size()) {
203                 changedLines.add(stringList.get(i));
204             }
205         }
206 
207         return changedLines;
208     }
209 
210     private static void _addResults(
211         List<DiffResult> results, List<String> stringList,
212         List<String> changedLines, int start, int end) {
213 
214         changedLines.addAll(stringList.subList(start, end + 1));
215 
216         DiffResult diffResult = new DiffResult(
217             start, changedLines);
218 
219         results.add(diffResult);
220     }
221 
222     private static int _calculateMargin(
223         List<DiffResult> sourceResults, List<DiffResult> targetResults,
224         int sourceBeginPos, int targetBeginPos, int margin) {
225 
226         int sourceMargin = _checkOverlapping(
227             sourceResults, sourceBeginPos, margin);
228         int targetMargin = _checkOverlapping(
229             targetResults, targetBeginPos, margin);
230 
231         if (sourceMargin < targetMargin) {
232             return sourceMargin;
233         }
234 
235         return targetMargin;
236     }
237 
238     private static void _checkCharDiffs(
239         List<DiffResult> sourceResults, List<DiffResult> targetResults,
240         List<String> sourceStringList, List<String> targetStringList,
241         String addedMarkerStart, String addedMarkerEnd,
242         String deletedMarkerStart, String deletedMarkerEnd,
243         Difference difference, int margin) {
244 
245         boolean aligned = false;
246 
247         int i = difference.getDeletedStart();
248         int j = difference.getAddedStart();
249 
250         // A line with changed characters may have its position shifted some
251         // lines above or below. These for loops will try to align these lines.
252         // While these lines are not aligned, highlight them as either additions
253         // or deletions.
254 
255         for (; i <= difference.getDeletedEnd(); i++) {
256             for (; j <= difference.getAddedEnd(); j++) {
257                 if (_lineDiff(
258                         sourceResults, targetResults, sourceStringList,
259                         targetStringList, addedMarkerStart, addedMarkerEnd,
260                         deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
261 
262                     aligned = true;
263 
264                     break;
265                 }
266                 else {
267                     _highlightLines(
268                         targetStringList, addedMarkerStart, addedMarkerEnd, j,
269                         j);
270 
271                     DiffResult targetResult = new DiffResult(
272                         j, targetStringList.subList(j, j + 1));
273 
274                     targetResults.add(targetResult);
275 
276                     sourceResults.add(new DiffResult(j, CONTEXT_LINE));
277                 }
278             }
279 
280             if (aligned) {
281                  break;
282             }
283             else {
284                 _highlightLines(
285                     sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
286                     i);
287 
288                 DiffResult sourceResult = new DiffResult(
289                     i, sourceStringList.subList(i, i + 1));
290 
291                 sourceResults.add(sourceResult);
292 
293                 targetResults.add(new DiffResult(i, CONTEXT_LINE));
294             }
295         }
296 
297         i = i + 1;
298         j = j + 1;
299 
300         // Lines are aligned, check for differences of the following lines.
301 
302         for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
303                 i++, j++) {
304 
305             _lineDiff(
306                 sourceResults, targetResults, sourceStringList,
307                 targetStringList, addedMarkerStart, addedMarkerEnd,
308                 deletedMarkerStart, deletedMarkerEnd, i, j, true);
309         }
310 
311         // After the for loop above, some lines might remained unchecked.
312         // They are considered as deletions or additions.
313 
314         for (; i <= difference.getDeletedEnd();i++) {
315             _highlightLines(
316                 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
317 
318             DiffResult sourceResult = new DiffResult(
319                 i, sourceStringList.subList(i, i + 1));
320 
321             sourceResults.add(sourceResult);
322 
323             targetResults.add(new DiffResult(i, CONTEXT_LINE));
324         }
325 
326         for (; j <= difference.getAddedEnd(); j++) {
327             _highlightLines(
328                 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
329 
330             DiffResult targetResult = new DiffResult(
331                 j, targetStringList.subList(j, j + 1));
332 
333             targetResults.add(targetResult);
334 
335             sourceResults.add(new DiffResult(j, CONTEXT_LINE));
336         }
337     }
338 
339     private static int _checkOverlapping(
340         List<DiffResult> results, int startPos, int margin) {
341 
342         if (results.size() == 0 || (startPos - margin) < 0) {
343             return margin;
344         }
345 
346         DiffResult lastDiff = results.get(results.size() - 1);
347 
348         if (lastDiff.getChangedLines().size() == 0) {
349             return margin;
350         }
351 
352         int lastChangedLine = (lastDiff.getLineNumber() - 1) +
353             lastDiff.getChangedLines().size();
354 
355         int currentChangedLine = startPos - margin;
356 
357         if ((lastDiff.getChangedLines().size() == 1) &&
358             (lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE))) {
359 
360             currentChangedLine = currentChangedLine + 1;
361         }
362 
363         if (currentChangedLine < lastChangedLine) {
364             return margin + currentChangedLine - lastChangedLine;
365         }
366 
367         return margin;
368     }
369 
370     private static void _highlightChars(
371         List<String> stringList, String markerStart, String markerEnd,
372         int startPos, int endPos) {
373 
374         String start = markerStart + stringList.get(startPos);
375 
376         stringList.set(startPos, start);
377 
378         String end = stringList.get(endPos) + markerEnd;
379 
380         stringList.set(endPos, end);
381     }
382 
383     private static void _highlightLines(
384         List<String> stringList, String markerStart, String markerEnd,
385         int startPos, int endPos) {
386 
387         for (int i = startPos; i <= endPos; i++) {
388             stringList.set(i, markerStart + stringList.get(i) + markerEnd);
389         }
390     }
391 
392     private static boolean _lineDiff(
393         List<DiffResult> sourceResults, List<DiffResult> targetResults,
394         List<String> sourceStringList, List<String> targetStringList,
395         String addedMarkerStart, String addedMarkerEnd,
396         String deletedMarkerStart, String deletedMarkerEnd,
397         int sourceChangedLine, int targetChangedLine, boolean aligned) {
398 
399         String source = sourceStringList.get(sourceChangedLine);
400         String target = targetStringList.get(targetChangedLine);
401 
402         // Convert the lines to lists where each element are chars of the lines.
403 
404         List<String> sourceList = _toList(source);
405         List<String> targetList = _toList(target);
406 
407         Diff diff = new Diff(sourceList, targetList);
408 
409         List<Difference> differences = diff.diff();
410 
411         Iterator<Difference> itr = differences.iterator();
412 
413         int deletedChars = 0;
414         int addedChars = 0;
415 
416         // The following while loop will calculate how many characters of
417         // the source line need to be changed to be equals to the target line.
418 
419         while (itr.hasNext() && !aligned) {
420             Difference difference = itr.next();
421 
422             if (difference.getDeletedEnd() != Difference.NONE) {
423                 deletedChars =
424                     deletedChars +
425                     (difference.getDeletedEnd() -
426                         difference.getDeletedStart() + 1);
427             }
428 
429             if (difference.getAddedEnd() != Difference.NONE) {
430                 addedChars =
431                     addedChars +
432                     (difference.getAddedEnd() - difference.getAddedStart() + 1);
433             }
434         }
435 
436         // If a lot of changes were needed (more than half of the source line
437         // length), consider this as not aligned yet.
438 
439         if ((deletedChars > (sourceList.size() / 2)) ||
440             (addedChars > sourceList.size() / 2)) {
441 
442             return false;
443         }
444 
445         itr = differences.iterator();
446 
447         boolean sourceChanged = false;
448         boolean targetChanged = false;
449 
450         // Iterate over Differences between chars of these lines.
451 
452         while (itr.hasNext()) {
453             Difference difference = itr.next();
454 
455             if (difference.getAddedEnd() == Difference.NONE) {
456 
457                 // Chars were deleted from source only.
458 
459                 _highlightChars(
460                     sourceList, deletedMarkerStart,
461                     deletedMarkerEnd, difference.getDeletedStart(),
462                     difference.getDeletedEnd());
463 
464                 sourceChanged = true;
465             }
466             else if (difference.getDeletedEnd() == Difference.NONE) {
467 
468                 // Chars were added to target only.
469 
470                 _highlightChars(
471                     targetList, addedMarkerStart, addedMarkerEnd,
472                     difference.getAddedStart(), difference.getAddedEnd());
473 
474                 targetChanged = true;
475             }
476             else {
477 
478                 // Chars were both deleted and added.
479 
480                 _highlightChars(
481                     sourceList, deletedMarkerStart,
482                     deletedMarkerEnd, difference.getDeletedStart(),
483                     difference.getDeletedEnd());
484 
485                 sourceChanged = true;
486 
487                 _highlightChars(
488                     targetList, addedMarkerStart, addedMarkerEnd,
489                     difference.getAddedStart(), difference.getAddedEnd());
490 
491                 targetChanged = true;
492             }
493         }
494 
495         if (sourceChanged) {
496             DiffResult sourceResult = new DiffResult(
497                 sourceChangedLine, _toString(sourceList));
498 
499             sourceResults.add(sourceResult);
500 
501             if (!targetChanged) {
502                 DiffResult targetResult = new DiffResult(
503                     targetChangedLine, target);
504 
505                 targetResults.add(targetResult);
506             }
507         }
508 
509         if (targetChanged) {
510             if (!sourceChanged) {
511                 DiffResult sourceResult = new DiffResult(
512                     sourceChangedLine, source);
513 
514                 sourceResults.add(sourceResult);
515             }
516 
517             DiffResult targetResult = new DiffResult(
518                 targetChangedLine, _toString(targetList));
519 
520             targetResults.add(targetResult);
521         }
522 
523         return true;
524     }
525 
526     private static List<String> _toList(String line) {
527         String[] stringArray = line.split(StringPool.BLANK);
528 
529         List<String> result = new ArrayList<String>();
530 
531         for (int i = 1; i < stringArray.length; i++) {
532             result.add(stringArray[i]);
533         }
534 
535         return result;
536     }
537 
538     private static String _toString(List<String> line) {
539         if (line.isEmpty()) {
540             return StringPool.BLANK;
541         }
542 
543         StringBundler sb = new StringBundler(line.size());
544 
545         Iterator<String> itr = line.iterator();
546 
547         while (itr.hasNext()) {
548             sb.append(itr.next());
549         }
550 
551         return sb.toString();
552     }
553 
554 }