001    /**
002     * Copyright (c) 2000-2013 Liferay, Inc. All rights reserved.
003     *
004     * This library is free software; you can redistribute it and/or modify it under
005     * the terms of the GNU Lesser General Public License as published by the Free
006     * Software Foundation; either version 2.1 of the License, or (at your option)
007     * any later version.
008     *
009     * This library is distributed in the hope that it will be useful, but WITHOUT
010     * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
011     * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
012     * details.
013     */
014    
015    package com.liferay.portal.util;
016    
017    import com.liferay.portal.kernel.util.DiffResult;
018    import com.liferay.portal.kernel.util.FileUtil;
019    import com.liferay.portal.kernel.util.StringBundler;
020    import com.liferay.portal.kernel.util.StringPool;
021    
022    import java.io.Reader;
023    
024    import java.util.ArrayList;
025    import java.util.Iterator;
026    import java.util.List;
027    
028    import org.incava.util.diff.Diff;
029    import org.incava.util.diff.Difference;
030    
031    /**
032     * <p>
033     * This class can compare two different versions of a text. Source refers to the
034     * earliest version of the text and target refers to a modified version of
035     * source. Changes are considered either as a removal from the source or as an
036     * addition to the target. This class detects changes to an entire line and also
037     * detects changes within lines, such as, removal or addition of characters.
038     * Take a look at <code>DiffTest</code> to see the expected inputs and outputs.
039     * </p>
040     *
041     * @author Bruno Farache
042     */
043    public class DiffImpl implements com.liferay.portal.kernel.util.Diff {
044    
045            /**
046             * This is a diff method with default values.
047             *
048             * @param  source the source text
049             * @param  target the modified version of the source text
050             * @return an array containing two lists of <code>DiffResults</code>, the
051             *         first element contains DiffResults related to changes in source
052             *         and the second element to changes in target
053             */
054            @Override
055            public List<DiffResult>[] diff(Reader source, Reader target) {
056                    int margin = 2;
057    
058                    return diff(
059                            source, target, OPEN_INS, CLOSE_INS, OPEN_DEL, CLOSE_DEL, margin);
060            }
061    
062            /**
063             * The main entrance of this class. This method will compare the two texts,
064             * highlight the changes by enclosing them with markers and return a list of
065             * <code>DiffResults</code>.
066             *
067             * @param  source the source text
068             * @param  target the modified version of the source text
069             * @param  addedMarkerStart the marker to indicate the start of text added
070             *         to the source
071             * @param  addedMarkerEnd the marker to indicate the end of text added to
072             *         the source
073             * @param  deletedMarkerStart the marker to indicate the start of text
074             *         deleted from the source
075             * @param  deletedMarkerEnd the marker to indicate the end of text deleted
076             *         from the source
077             * @param  margin the vertical margin to use in displaying differences
078             *         between changed line changes
079             * @return an array containing two lists of <code>DiffResults</code>, the
080             *         first element contains DiffResults related to changes in source
081             *         and the second element to changes in target
082             */
083            @Override
084            public List<DiffResult>[] diff(
085                    Reader source, Reader target, String addedMarkerStart,
086                    String addedMarkerEnd, String deletedMarkerStart,
087                    String deletedMarkerEnd, int margin) {
088    
089                    List<DiffResult> sourceResults = new ArrayList<DiffResult>();
090                    List<DiffResult> targetResults = new ArrayList<DiffResult>();
091    
092                    List<DiffResult>[] results = new List[] {sourceResults, targetResults};
093    
094                    // Convert the texts to Lists where each element are lines of the texts.
095    
096                    List<String> sourceStringList = FileUtil.toList(source);
097                    List<String> targetStringList = FileUtil.toList(target);
098    
099                    // Make a a Diff of these lines and iterate over their Differences.
100    
101                    Diff diff = new Diff(sourceStringList, targetStringList);
102    
103                    List<Difference> differences = diff.diff();
104    
105                    Iterator<Difference> itr = differences.iterator();
106    
107                    while (itr.hasNext()) {
108                            Difference difference = itr.next();
109    
110                            if (difference.getAddedEnd() == Difference.NONE) {
111    
112                                    // Lines were deleted from source only.
113    
114                                    _highlightLines(
115                                            sourceStringList, deletedMarkerStart, deletedMarkerEnd,
116                                            difference.getDeletedStart(), difference.getDeletedEnd());
117    
118                                    margin = _calculateMargin(
119                                            sourceResults, targetResults, difference.getDeletedStart(),
120                                            difference.getAddedStart(), margin);
121    
122                                    List<String> changedLines = _addMargins(
123                                            sourceResults, sourceStringList,
124                                            difference.getDeletedStart(), margin);
125    
126                                    _addResults(
127                                            sourceResults, sourceStringList, changedLines,
128                                            difference.getDeletedStart(), difference.getDeletedEnd());
129    
130                                    changedLines = _addMargins(
131                                            targetResults, targetStringList, difference.getAddedStart(),
132                                            margin);
133    
134                                    int deletedLines =
135                                            difference.getDeletedEnd() + 1 -
136                                                    difference.getDeletedStart();
137    
138                                    for (int i = 0; i < deletedLines; i++) {
139                                            changedLines.add(CONTEXT_LINE);
140                                    }
141    
142                                    DiffResult diffResult = new DiffResult(
143                                            difference.getDeletedStart(), changedLines);
144    
145                                    targetResults.add(diffResult);
146                            }
147                            else if (difference.getDeletedEnd() == Difference.NONE) {
148    
149                                    // Lines were added to target only.
150    
151                                    _highlightLines(
152                                            targetStringList, addedMarkerStart, addedMarkerEnd,
153                                            difference.getAddedStart(), difference.getAddedEnd());
154    
155                                    margin = _calculateMargin(
156                                            sourceResults, targetResults, difference.getDeletedStart(),
157                                            difference.getAddedStart(), margin);
158    
159                                    List<String> changedLines = _addMargins(
160                                            sourceResults, sourceStringList,
161                                            difference.getDeletedStart(), margin);
162    
163                                    int addedLines =
164                                            difference.getAddedEnd() + 1 - difference.getAddedStart();
165    
166                                    for (int i = 0; i < addedLines; i++) {
167                                            changedLines.add(CONTEXT_LINE);
168                                    }
169    
170                                    DiffResult diffResult = new DiffResult(
171                                            difference.getAddedStart(), changedLines);
172    
173                                    sourceResults.add(diffResult);
174    
175                                    changedLines = _addMargins(
176                                            targetResults, targetStringList, difference.getAddedStart(),
177                                            margin);
178    
179                                    _addResults(
180                                            targetResults, targetStringList, changedLines,
181                                            difference.getAddedStart(), difference.getAddedEnd());
182                            }
183                            else {
184    
185                                    // Lines were deleted from source and added to target at the
186                                    // same position. It needs to check for characters differences.
187    
188                                    _checkCharDiffs(
189                                            sourceResults, targetResults, sourceStringList,
190                                            targetStringList, addedMarkerStart, addedMarkerEnd,
191                                            deletedMarkerStart, deletedMarkerEnd, difference, margin);
192                            }
193                    }
194    
195                    return results;
196            }
197    
198            private static List<String> _addMargins(
199                    List<DiffResult> results, List<String> stringList, int startPos,
200                    int margin) {
201    
202                    List<String> changedLines = new ArrayList<String>();
203    
204                    if ((margin == 0) || (startPos == 0)) {
205                            return changedLines;
206                    }
207    
208                    int i = startPos - margin;
209    
210                    for (; i < 0; i++) {
211                            changedLines.add(CONTEXT_LINE);
212                    }
213    
214                    for (; i < startPos; i++) {
215                            if (i < stringList.size()) {
216                                    changedLines.add(stringList.get(i));
217                            }
218                    }
219    
220                    return changedLines;
221            }
222    
223            private static void _addResults(
224                    List<DiffResult> results, List<String> stringList,
225                    List<String> changedLines, int start, int end) {
226    
227                    changedLines.addAll(stringList.subList(start, end + 1));
228    
229                    DiffResult diffResult = new DiffResult(start, changedLines);
230    
231                    results.add(diffResult);
232            }
233    
234            private static int _calculateMargin(
235                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
236                    int sourceBeginPos, int targetBeginPos, int margin) {
237    
238                    int sourceMargin = _checkOverlapping(
239                            sourceResults, sourceBeginPos, margin);
240                    int targetMargin = _checkOverlapping(
241                            targetResults, targetBeginPos, margin);
242    
243                    if (sourceMargin < targetMargin) {
244                            return sourceMargin;
245                    }
246    
247                    return targetMargin;
248            }
249    
250            private static void _checkCharDiffs(
251                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
252                    List<String> sourceStringList, List<String> targetStringList,
253                    String addedMarkerStart, String addedMarkerEnd,
254                    String deletedMarkerStart, String deletedMarkerEnd,
255                    Difference difference, int margin) {
256    
257                    boolean aligned = false;
258    
259                    int i = difference.getDeletedStart();
260                    int j = difference.getAddedStart();
261    
262                    // A line with changed characters may have its position shifted some
263                    // lines above or below. These for loops will try to align these lines.
264                    // While these lines are not aligned, highlight them as either additions
265                    // or deletions.
266    
267                    for (; i <= difference.getDeletedEnd(); i++) {
268                            for (; j <= difference.getAddedEnd(); j++) {
269                                    if (!_isMaxLineLengthExceeded(
270                                                    sourceStringList.get(i), targetStringList.get(j)) &&
271                                            _lineDiff(
272                                                    sourceResults, targetResults, sourceStringList,
273                                                    targetStringList, addedMarkerStart, addedMarkerEnd,
274                                                    deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
275    
276                                            aligned = true;
277    
278                                            break;
279                                    }
280    
281                                    _highlightLines(
282                                            targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
283    
284                                    DiffResult targetResult = new DiffResult(
285                                            j, targetStringList.subList(j, j + 1));
286    
287                                    targetResults.add(targetResult);
288    
289                                    sourceResults.add(new DiffResult(j, CONTEXT_LINE));
290                            }
291    
292                            if (aligned) {
293                                    break;
294                            }
295    
296                            _highlightLines(
297                                    sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, 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                    i = i + 1;
308                    j = j + 1;
309    
310                    // Lines are aligned, check for differences of the following lines.
311    
312                    for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
313                                    i++, j++) {
314    
315                            if (!_isMaxLineLengthExceeded(
316                                            sourceStringList.get(i), targetStringList.get(j))) {
317    
318                                    _lineDiff(
319                                            sourceResults, targetResults, sourceStringList,
320                                            targetStringList, addedMarkerStart, addedMarkerEnd,
321                                            deletedMarkerStart, deletedMarkerEnd, i, j, true);
322                            }
323                            else {
324                                    _highlightLines(
325                                            sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
326                                            i);
327    
328                                    DiffResult sourceResult = new DiffResult(
329                                            i, sourceStringList.subList(i, i + 1));
330    
331                                    sourceResults.add(sourceResult);
332    
333                                    targetResults.add(new DiffResult(i, CONTEXT_LINE));
334    
335                                    _highlightLines(
336                                            targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
337    
338                                    DiffResult targetResult = new DiffResult(
339                                            j, targetStringList.subList(j, j + 1));
340    
341                                    targetResults.add(targetResult);
342    
343                                    sourceResults.add(new DiffResult(j, CONTEXT_LINE));
344                            }
345                    }
346    
347                    // After the for loop above, some lines might remained unchecked. They
348                    // are considered as deletions or additions.
349    
350                    for (; i <= difference.getDeletedEnd(); i++) {
351                            _highlightLines(
352                                    sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
353    
354                            DiffResult sourceResult = new DiffResult(
355                                    i, sourceStringList.subList(i, i + 1));
356    
357                            sourceResults.add(sourceResult);
358    
359                            targetResults.add(new DiffResult(i, CONTEXT_LINE));
360                    }
361    
362                    for (; j <= difference.getAddedEnd(); j++) {
363                            _highlightLines(
364                                    targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
365    
366                            DiffResult targetResult = new DiffResult(
367                                    j, targetStringList.subList(j, j + 1));
368    
369                            targetResults.add(targetResult);
370    
371                            sourceResults.add(new DiffResult(j, CONTEXT_LINE));
372                    }
373            }
374    
375            private static int _checkOverlapping(
376                    List<DiffResult> results, int startPos, int margin) {
377    
378                    if ((results.size() == 0) || ((startPos - margin) < 0)) {
379                            return margin;
380                    }
381    
382                    DiffResult lastDiff = results.get(results.size() - 1);
383    
384                    if (lastDiff.getChangedLines().size() == 0) {
385                            return margin;
386                    }
387    
388                    int lastChangedLine =
389                            (lastDiff.getLineNumber() - 1) +
390                                    lastDiff.getChangedLines().size();
391    
392                    int currentChangedLine = startPos - margin;
393    
394                    if ((lastDiff.getChangedLines().size() == 1) &&
395                            lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE)) {
396    
397                            currentChangedLine = currentChangedLine + 1;
398                    }
399    
400                    if (currentChangedLine < lastChangedLine) {
401                            return margin + currentChangedLine - lastChangedLine;
402                    }
403    
404                    return margin;
405            }
406    
407            private static void _highlightChars(
408                    List<String> stringList, String markerStart, String markerEnd,
409                    int startPos, int endPos) {
410    
411                    String start = markerStart + stringList.get(startPos);
412    
413                    stringList.set(startPos, start);
414    
415                    String end = stringList.get(endPos) + markerEnd;
416    
417                    stringList.set(endPos, end);
418            }
419    
420            private static void _highlightLines(
421                    List<String> stringList, String markerStart, String markerEnd,
422                    int startPos, int endPos) {
423    
424                    for (int i = startPos; i <= endPos; i++) {
425                            stringList.set(i, markerStart + stringList.get(i) + markerEnd);
426                    }
427            }
428    
429            private static boolean _isMaxLineLengthExceeded(
430                    String sourceString, String targetString) {
431    
432                    if ((sourceString.length() > _DIFF_MAX_LINE_LENGTH) ||
433                            (targetString.length() > _DIFF_MAX_LINE_LENGTH)) {
434    
435                            return true;
436                    }
437    
438                    return false;
439            }
440    
441            private static boolean _lineDiff(
442                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
443                    List<String> sourceStringList, List<String> targetStringList,
444                    String addedMarkerStart, String addedMarkerEnd,
445                    String deletedMarkerStart, String deletedMarkerEnd,
446                    int sourceChangedLine, int targetChangedLine, boolean aligned) {
447    
448                    String source = sourceStringList.get(sourceChangedLine);
449                    String target = targetStringList.get(targetChangedLine);
450    
451                    // Convert the lines to lists where each element are chars of the lines.
452    
453                    List<String> sourceList = _toList(source);
454                    List<String> targetList = _toList(target);
455    
456                    Diff diff = new Diff(sourceList, targetList);
457    
458                    List<Difference> differences = diff.diff();
459    
460                    Iterator<Difference> itr = differences.iterator();
461    
462                    int deletedChars = 0;
463                    int addedChars = 0;
464    
465                    // The following while loop will calculate how many characters of the
466                    // source line need to be changed to be equals to the target line.
467    
468                    while (itr.hasNext() && !aligned) {
469                            Difference difference = itr.next();
470    
471                            if (difference.getDeletedEnd() != Difference.NONE) {
472                                    deletedChars =
473                                            deletedChars +
474                                            (difference.getDeletedEnd() -
475                                                    difference.getDeletedStart() + 1);
476                            }
477    
478                            if (difference.getAddedEnd() != Difference.NONE) {
479                                    addedChars =
480                                            addedChars +
481                                            (difference.getAddedEnd() - difference.getAddedStart() + 1);
482                            }
483                    }
484    
485                    // If a lot of changes were needed (more than half of the source line
486                    // length), consider this as not aligned yet.
487    
488                    if ((deletedChars > (sourceList.size() / 2)) ||
489                            (addedChars > (sourceList.size() / 2))) {
490    
491                            return false;
492                    }
493    
494                    itr = differences.iterator();
495    
496                    boolean sourceChanged = false;
497                    boolean targetChanged = false;
498    
499                    // Iterate over Differences between chars of these lines.
500    
501                    while (itr.hasNext()) {
502                            Difference difference = itr.next();
503    
504                            if (difference.getAddedEnd() == Difference.NONE) {
505    
506                                    // Chars were deleted from source only.
507    
508                                    _highlightChars(
509                                            sourceList, deletedMarkerStart, deletedMarkerEnd,
510                                            difference.getDeletedStart(), difference.getDeletedEnd());
511    
512                                    sourceChanged = true;
513                            }
514                            else if (difference.getDeletedEnd() == Difference.NONE) {
515    
516                                    // Chars were added to target only.
517    
518                                    _highlightChars(
519                                            targetList, addedMarkerStart, addedMarkerEnd,
520                                            difference.getAddedStart(), difference.getAddedEnd());
521    
522                                    targetChanged = true;
523                            }
524                            else {
525    
526                                    // Chars were both deleted and added.
527    
528                                    _highlightChars(
529                                            sourceList, deletedMarkerStart, deletedMarkerEnd,
530                                            difference.getDeletedStart(), difference.getDeletedEnd());
531    
532                                    sourceChanged = true;
533    
534                                    _highlightChars(
535                                            targetList, addedMarkerStart, addedMarkerEnd,
536                                            difference.getAddedStart(), difference.getAddedEnd());
537    
538                                    targetChanged = true;
539                            }
540                    }
541    
542                    if (sourceChanged) {
543                            DiffResult sourceResult = new DiffResult(
544                                    sourceChangedLine, _toString(sourceList));
545    
546                            sourceResults.add(sourceResult);
547    
548                            if (!targetChanged) {
549                                    DiffResult targetResult = new DiffResult(
550                                            targetChangedLine, target);
551    
552                                    targetResults.add(targetResult);
553                            }
554                    }
555    
556                    if (targetChanged) {
557                            if (!sourceChanged) {
558                                    DiffResult sourceResult = new DiffResult(
559                                            sourceChangedLine, source);
560    
561                                    sourceResults.add(sourceResult);
562                            }
563    
564                            DiffResult targetResult = new DiffResult(
565                                    targetChangedLine, _toString(targetList));
566    
567                            targetResults.add(targetResult);
568                    }
569    
570                    return true;
571            }
572    
573            private static List<String> _toList(String line) {
574                    String[] stringArray = line.split(StringPool.BLANK);
575    
576                    List<String> result = new ArrayList<String>();
577    
578                    for (int i = 1; i < stringArray.length; i++) {
579                            result.add(stringArray[i]);
580                    }
581    
582                    return result;
583            }
584    
585            private static String _toString(List<String> line) {
586                    if (line.isEmpty()) {
587                            return StringPool.BLANK;
588                    }
589    
590                    StringBundler sb = new StringBundler(line.size());
591    
592                    Iterator<String> itr = line.iterator();
593    
594                    while (itr.hasNext()) {
595                            sb.append(itr.next());
596                    }
597    
598                    return sb.toString();
599            }
600    
601            private static final int _DIFF_MAX_LINE_LENGTH = 5000;
602    
603    }