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