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