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