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