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.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.util.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<DiffResult>();
087                    List<DiffResult> targetResults = new ArrayList<DiffResult>();
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                                            sourceResults, sourceStringList,
117                                            difference.getDeletedStart(), margin);
118    
119                                    _addResults(
120                                            sourceResults, sourceStringList, changedLines,
121                                            difference.getDeletedStart(), difference.getDeletedEnd());
122    
123                                    changedLines = _addMargins(
124                                            targetResults, targetStringList, difference.getAddedStart(),
125                                            margin);
126    
127                                    int deletedLines =
128                                            difference.getDeletedEnd() + 1 -
129                                                    difference.getDeletedStart();
130    
131                                    for (int i = 0; i < deletedLines; i++) {
132                                            changedLines.add(CONTEXT_LINE);
133                                    }
134    
135                                    DiffResult diffResult = new DiffResult(
136                                            difference.getDeletedStart(), changedLines);
137    
138                                    targetResults.add(diffResult);
139                            }
140                            else if (difference.getDeletedEnd() == Difference.NONE) {
141    
142                                    // Lines were added to target only.
143    
144                                    _highlightLines(
145                                            targetStringList, addedMarkerStart, addedMarkerEnd,
146                                            difference.getAddedStart(), difference.getAddedEnd());
147    
148                                    margin = _calculateMargin(
149                                            sourceResults, targetResults, difference.getDeletedStart(),
150                                            difference.getAddedStart(), margin);
151    
152                                    List<String> changedLines = _addMargins(
153                                            sourceResults, sourceStringList,
154                                            difference.getDeletedStart(), margin);
155    
156                                    int addedLines =
157                                            difference.getAddedEnd() + 1 - difference.getAddedStart();
158    
159                                    for (int i = 0; i < addedLines; i++) {
160                                            changedLines.add(CONTEXT_LINE);
161                                    }
162    
163                                    DiffResult diffResult = new DiffResult(
164                                            difference.getAddedStart(), changedLines);
165    
166                                    sourceResults.add(diffResult);
167    
168                                    changedLines = _addMargins(
169                                            targetResults, targetStringList, difference.getAddedStart(),
170                                            margin);
171    
172                                    _addResults(
173                                            targetResults, targetStringList, changedLines,
174                                            difference.getAddedStart(), difference.getAddedEnd());
175                            }
176                            else {
177    
178                                    // Lines were deleted from source and added to target at the
179                                    // same position. It needs to check for characters differences.
180    
181                                    _checkCharDiffs(
182                                            sourceResults, targetResults, sourceStringList,
183                                            targetStringList, addedMarkerStart, addedMarkerEnd,
184                                            deletedMarkerStart, deletedMarkerEnd, difference, margin);
185                            }
186                    }
187    
188                    return results;
189            }
190    
191            private static List<String> _addMargins(
192                    List<DiffResult> results, List<String> stringList, int startPos,
193                    int margin) {
194    
195                    List<String> changedLines = new ArrayList<String>();
196    
197                    if ((margin == 0) || (startPos == 0)) {
198                            return changedLines;
199                    }
200    
201                    int i = startPos - margin;
202    
203                    for (; i < 0; i++) {
204                            changedLines.add(CONTEXT_LINE);
205                    }
206    
207                    for (; i < startPos; i++) {
208                            if (i < stringList.size()) {
209                                    changedLines.add(stringList.get(i));
210                            }
211                    }
212    
213                    return changedLines;
214            }
215    
216            private static void _addResults(
217                    List<DiffResult> results, List<String> stringList,
218                    List<String> changedLines, int start, int end) {
219    
220                    changedLines.addAll(stringList.subList(start, end + 1));
221    
222                    DiffResult diffResult = new DiffResult(start, changedLines);
223    
224                    results.add(diffResult);
225            }
226    
227            private static int _calculateMargin(
228                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
229                    int sourceBeginPos, int targetBeginPos, int margin) {
230    
231                    int sourceMargin = _checkOverlapping(
232                            sourceResults, sourceBeginPos, margin);
233                    int targetMargin = _checkOverlapping(
234                            targetResults, targetBeginPos, margin);
235    
236                    if (sourceMargin < targetMargin) {
237                            return sourceMargin;
238                    }
239    
240                    return targetMargin;
241            }
242    
243            private static void _checkCharDiffs(
244                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
245                    List<String> sourceStringList, List<String> targetStringList,
246                    String addedMarkerStart, String addedMarkerEnd,
247                    String deletedMarkerStart, String deletedMarkerEnd,
248                    Difference difference, int margin) {
249    
250                    boolean aligned = false;
251    
252                    int i = difference.getDeletedStart();
253                    int j = difference.getAddedStart();
254    
255                    // A line with changed characters may have its position shifted some
256                    // lines above or below. These for loops will try to align these lines.
257                    // While these lines are not aligned, highlight them as either additions
258                    // or deletions.
259    
260                    for (; i <= difference.getDeletedEnd(); i++) {
261                            for (; j <= difference.getAddedEnd(); j++) {
262                                    if (!_isMaxLineLengthExceeded(
263                                                    sourceStringList.get(i), targetStringList.get(j)) &&
264                                            _lineDiff(
265                                                    sourceResults, targetResults, sourceStringList,
266                                                    targetStringList, addedMarkerStart, addedMarkerEnd,
267                                                    deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
268    
269                                            aligned = true;
270    
271                                            break;
272                                    }
273    
274                                    _highlightLines(
275                                            targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
276    
277                                    DiffResult targetResult = new DiffResult(
278                                            j, targetStringList.subList(j, j + 1));
279    
280                                    targetResults.add(targetResult);
281    
282                                    sourceResults.add(new DiffResult(j, CONTEXT_LINE));
283                            }
284    
285                            if (aligned) {
286                                    break;
287                            }
288    
289                            _highlightLines(
290                                    sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
291    
292                            DiffResult sourceResult = new DiffResult(
293                                    i, sourceStringList.subList(i, i + 1));
294    
295                            sourceResults.add(sourceResult);
296    
297                            targetResults.add(new DiffResult(i, CONTEXT_LINE));
298                    }
299    
300                    i = i + 1;
301                    j = j + 1;
302    
303                    // Lines are aligned, check for differences of the following lines.
304    
305                    for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
306                                    i++, j++) {
307    
308                            if (!_isMaxLineLengthExceeded(
309                                            sourceStringList.get(i), targetStringList.get(j))) {
310    
311                                    _lineDiff(
312                                            sourceResults, targetResults, sourceStringList,
313                                            targetStringList, addedMarkerStart, addedMarkerEnd,
314                                            deletedMarkerStart, deletedMarkerEnd, i, j, true);
315                            }
316                            else {
317                                    _highlightLines(
318                                            sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
319                                            i);
320    
321                                    DiffResult sourceResult = new DiffResult(
322                                            i, sourceStringList.subList(i, i + 1));
323    
324                                    sourceResults.add(sourceResult);
325    
326                                    targetResults.add(new DiffResult(i, CONTEXT_LINE));
327    
328                                    _highlightLines(
329                                            targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
330    
331                                    DiffResult targetResult = new DiffResult(
332                                            j, targetStringList.subList(j, j + 1));
333    
334                                    targetResults.add(targetResult);
335    
336                                    sourceResults.add(new DiffResult(j, CONTEXT_LINE));
337                            }
338                    }
339    
340                    // After the for loop above, some lines might remained unchecked. They
341                    // are considered as deletions or additions.
342    
343                    for (; i <= difference.getDeletedEnd(); i++) {
344                            _highlightLines(
345                                    sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
346    
347                            DiffResult sourceResult = new DiffResult(
348                                    i, sourceStringList.subList(i, i + 1));
349    
350                            sourceResults.add(sourceResult);
351    
352                            targetResults.add(new DiffResult(i, CONTEXT_LINE));
353                    }
354    
355                    for (; j <= difference.getAddedEnd(); j++) {
356                            _highlightLines(
357                                    targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
358    
359                            DiffResult targetResult = new DiffResult(
360                                    j, targetStringList.subList(j, j + 1));
361    
362                            targetResults.add(targetResult);
363    
364                            sourceResults.add(new DiffResult(j, CONTEXT_LINE));
365                    }
366            }
367    
368            private static int _checkOverlapping(
369                    List<DiffResult> results, int startPos, int margin) {
370    
371                    if ((results.size() == 0) || ((startPos - margin) < 0)) {
372                            return margin;
373                    }
374    
375                    DiffResult lastDiff = results.get(results.size() - 1);
376    
377                    if (lastDiff.getChangedLines().size() == 0) {
378                            return margin;
379                    }
380    
381                    int lastChangedLine =
382                            (lastDiff.getLineNumber() - 1) + lastDiff.getChangedLines().size();
383    
384                    int currentChangedLine = startPos - margin;
385    
386                    if ((lastDiff.getChangedLines().size() == 1) &&
387                            lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE)) {
388    
389                            currentChangedLine = currentChangedLine + 1;
390                    }
391    
392                    if (currentChangedLine < lastChangedLine) {
393                            return margin + currentChangedLine - lastChangedLine;
394                    }
395    
396                    return margin;
397            }
398    
399            private static void _highlightChars(
400                    List<String> stringList, String markerStart, String markerEnd,
401                    int startPos, int endPos) {
402    
403                    String start = markerStart + stringList.get(startPos);
404    
405                    stringList.set(startPos, start);
406    
407                    String end = stringList.get(endPos) + markerEnd;
408    
409                    stringList.set(endPos, end);
410            }
411    
412            private static void _highlightLines(
413                    List<String> stringList, String markerStart, String markerEnd,
414                    int startPos, int endPos) {
415    
416                    for (int i = startPos; i <= endPos; i++) {
417                            stringList.set(i, markerStart + stringList.get(i) + markerEnd);
418                    }
419            }
420    
421            private static boolean _isMaxLineLengthExceeded(
422                    String sourceString, String targetString) {
423    
424                    if ((sourceString.length() > _DIFF_MAX_LINE_LENGTH) ||
425                            (targetString.length() > _DIFF_MAX_LINE_LENGTH)) {
426    
427                            return true;
428                    }
429    
430                    return false;
431            }
432    
433            private static boolean _lineDiff(
434                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
435                    List<String> sourceStringList, List<String> targetStringList,
436                    String addedMarkerStart, String addedMarkerEnd,
437                    String deletedMarkerStart, String deletedMarkerEnd,
438                    int sourceChangedLine, int targetChangedLine, boolean aligned) {
439    
440                    String source = sourceStringList.get(sourceChangedLine);
441                    String target = targetStringList.get(targetChangedLine);
442    
443                    // Convert the lines to lists where each element are chars of the lines.
444    
445                    List<String> sourceList = _toList(source);
446                    List<String> targetList = _toList(target);
447    
448                    Diff diff = new Diff(sourceList, targetList);
449    
450                    List<Difference> differences = diff.diff();
451    
452                    int deletedChars = 0;
453                    int addedChars = 0;
454    
455                    // The following while loop will calculate how many characters of the
456                    // source line need to be changed to be equals to the target line.
457    
458                    if (!aligned) {
459                            for (Difference difference : differences) {
460                                    if (difference.getDeletedEnd() != Difference.NONE) {
461                                            deletedChars +=
462                                                    (difference.getDeletedEnd() -
463                                                            difference.getDeletedStart() + 1);
464                                    }
465    
466                                    if (difference.getAddedEnd() != Difference.NONE) {
467                                            addedChars +=
468                                                    (difference.getAddedEnd() - difference.getAddedStart() +
469                                                            1);
470                                    }
471                            }
472                    }
473    
474                    // If a lot of changes were needed (more than half of the source line
475                    // length), consider this as not aligned yet.
476    
477                    if ((deletedChars > (sourceList.size() / 2)) ||
478                            (addedChars > (sourceList.size() / 2))) {
479    
480                            return false;
481                    }
482    
483                    boolean sourceChanged = false;
484                    boolean targetChanged = false;
485    
486                    // Iterate over Differences between chars of these lines.
487    
488                    for (Difference difference : differences) {
489                            if (difference.getAddedEnd() == Difference.NONE) {
490    
491                                    // Chars were deleted from source only.
492    
493                                    _highlightChars(
494                                            sourceList, deletedMarkerStart, deletedMarkerEnd,
495                                            difference.getDeletedStart(), difference.getDeletedEnd());
496    
497                                    sourceChanged = true;
498                            }
499                            else if (difference.getDeletedEnd() == Difference.NONE) {
500    
501                                    // Chars were added to target only.
502    
503                                    _highlightChars(
504                                            targetList, addedMarkerStart, addedMarkerEnd,
505                                            difference.getAddedStart(), difference.getAddedEnd());
506    
507                                    targetChanged = true;
508                            }
509                            else {
510    
511                                    // Chars were both deleted and added.
512    
513                                    _highlightChars(
514                                            sourceList, deletedMarkerStart, deletedMarkerEnd,
515                                            difference.getDeletedStart(), difference.getDeletedEnd());
516    
517                                    sourceChanged = true;
518    
519                                    _highlightChars(
520                                            targetList, addedMarkerStart, addedMarkerEnd,
521                                            difference.getAddedStart(), difference.getAddedEnd());
522    
523                                    targetChanged = true;
524                            }
525                    }
526    
527                    if (sourceChanged) {
528                            DiffResult sourceResult = new DiffResult(
529                                    sourceChangedLine, _toString(sourceList));
530    
531                            sourceResults.add(sourceResult);
532    
533                            if (!targetChanged) {
534                                    DiffResult targetResult = new DiffResult(
535                                            targetChangedLine, target);
536    
537                                    targetResults.add(targetResult);
538                            }
539                    }
540    
541                    if (targetChanged) {
542                            if (!sourceChanged) {
543                                    DiffResult sourceResult = new DiffResult(
544                                            sourceChangedLine, source);
545    
546                                    sourceResults.add(sourceResult);
547                            }
548    
549                            DiffResult targetResult = new DiffResult(
550                                    targetChangedLine, _toString(targetList));
551    
552                            targetResults.add(targetResult);
553                    }
554    
555                    return true;
556            }
557    
558            private static List<String> _toList(String line) {
559                    String[] lineParts = line.split(StringPool.BLANK);
560    
561                    List<String> result = new ArrayList<String>();
562    
563                    for (int i = 1; i < lineParts.length; i++) {
564                            result.add(lineParts[i]);
565                    }
566    
567                    return result;
568            }
569    
570            private static String _toString(List<String> line) {
571                    if (line.isEmpty()) {
572                            return StringPool.BLANK;
573                    }
574    
575                    StringBundler sb = new StringBundler(line.size());
576    
577                    for (String linePart : line) {
578                            sb.append(linePart);
579                    }
580    
581                    return sb.toString();
582            }
583    
584            private static final int _DIFF_MAX_LINE_LENGTH = 5000;
585    
586    }