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.Iterator;
025    import java.util.List;
026    
027    import org.incava.util.diff.Diff;
028    import org.incava.util.diff.Difference;
029    
030    /**
031     * <p>
032     * This class can compare two different versions of a text. Source refers to the
033     * earliest version of the text and target refers to a modified version of
034     * source. Changes are considered either as a removal from the source or as an
035     * addition to the target. This class detects changes to an entire line and also
036     * detects changes within lines, such as, removal or addition of characters.
037     * Take a look at <code>DiffTest</code> to see the expected inputs and outputs.
038     * </p>
039     *
040     * @author     Bruno Farache
041     * @deprecated Moved to {@link com.liferay.portal.kernel.util.DiffUtil}
042     */
043    public class DiffUtil {
044    
045            public static final String CLOSE_DEL = "</del>";
046    
047            public static final String CLOSE_INS = "</ins>";
048    
049            public static final String CONTEXT_LINE = "#context#line#";
050    
051            public static final String OPEN_DEL = "<del>";
052    
053            public static final String OPEN_INS = "<ins>";
054    
055            /**
056             * This is a diff method with default values.
057             *
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             * @return an array containing two lists of <code>DiffResults</code>, the
075             *         first element contains DiffResults related to changes in source
076             *         and the second element to changes in target
077             */
078            public static List<DiffResult>[] diff(
079                    Reader source, Reader target, String addedMarkerStart,
080                    String addedMarkerEnd, String deletedMarkerStart,
081                    String deletedMarkerEnd, int margin) {
082    
083                    List<DiffResult> sourceResults = new ArrayList<DiffResult>();
084                    List<DiffResult> targetResults = new ArrayList<DiffResult>();
085    
086                    List<DiffResult>[] results = new List[] {sourceResults, targetResults};
087    
088                    // Convert the texts to Lists where each element are lines of the texts.
089    
090                    List<String> sourceStringList = FileUtil.toList(source);
091                    List<String> targetStringList = FileUtil.toList(target);
092    
093                    // Make a a Diff of these lines and iterate over their Differences.
094    
095                    Diff diff = new Diff(sourceStringList, targetStringList);
096    
097                    List<Difference> differences = diff.diff();
098    
099                    Iterator<Difference> itr = differences.iterator();
100    
101                    while (itr.hasNext()) {
102                            Difference difference = itr.next();
103    
104                            if (difference.getAddedEnd() == Difference.NONE) {
105    
106                                    // Lines were deleted from source only.
107    
108                                    _highlightLines(
109                                            sourceStringList, deletedMarkerStart, deletedMarkerEnd,
110                                            difference.getDeletedStart(), difference.getDeletedEnd());
111    
112                                    margin = _calculateMargin(
113                                            sourceResults, targetResults, difference.getDeletedStart(),
114                                            difference.getAddedStart(), margin);
115    
116                                    List<String> changedLines = _addMargins(
117                                            sourceResults, sourceStringList,
118                                            difference.getDeletedStart(), margin);
119    
120                                    _addResults(
121                                            sourceResults, sourceStringList, changedLines,
122                                            difference.getDeletedStart(), difference.getDeletedEnd());
123    
124                                    changedLines = _addMargins(
125                                            targetResults, targetStringList, difference.getAddedStart(),
126                                            margin);
127    
128                                    int deletedLines =
129                                            difference.getDeletedEnd() + 1 -
130                                                    difference.getDeletedStart();
131    
132                                    for (int i = 0; i < deletedLines; i++) {
133                                            changedLines.add(CONTEXT_LINE);
134                                    }
135    
136                                    DiffResult diffResult = new DiffResult(
137                                            difference.getDeletedStart(), changedLines);
138    
139                                    targetResults.add(diffResult);
140                            }
141                            else if (difference.getDeletedEnd() == Difference.NONE) {
142    
143                                    // Lines were added to target only.
144    
145                                    _highlightLines(
146                                            targetStringList, addedMarkerStart, addedMarkerEnd,
147                                            difference.getAddedStart(), difference.getAddedEnd());
148    
149                                    margin = _calculateMargin(
150                                            sourceResults, targetResults, difference.getDeletedStart(),
151                                            difference.getAddedStart(), margin);
152    
153                                    List<String> changedLines = _addMargins(
154                                            sourceResults, sourceStringList,
155                                            difference.getDeletedStart(), margin);
156    
157                                    int addedLines =
158                                            difference.getAddedEnd() + 1 - difference.getAddedStart();
159    
160                                    for (int i = 0; i < addedLines; i++) {
161                                            changedLines.add(CONTEXT_LINE);
162                                    }
163    
164                                    DiffResult diffResult = new DiffResult(
165                                            difference.getAddedStart(), changedLines);
166    
167                                    sourceResults.add(diffResult);
168    
169                                    changedLines = _addMargins(
170                                            targetResults, targetStringList, difference.getAddedStart(),
171                                            margin);
172    
173                                    _addResults(
174                                            targetResults, targetStringList, changedLines,
175                                            difference.getAddedStart(), difference.getAddedEnd());
176                            }
177                            else {
178    
179                                    // Lines were deleted from source and added to target at the
180                                    // same position. It needs to check for characters differences.
181    
182                                    _checkCharDiffs(
183                                            sourceResults, targetResults, sourceStringList,
184                                            targetStringList, addedMarkerStart, addedMarkerEnd,
185                                            deletedMarkerStart, deletedMarkerEnd, difference, margin);
186                            }
187                    }
188    
189                    return results;
190            }
191    
192            private static List<String> _addMargins(
193                    List<DiffResult> results, List<String> stringList, int startPos,
194                    int margin) {
195    
196                    List<String> changedLines = new ArrayList<String>();
197    
198                    if (margin == 0 || startPos == 0) {
199                            return changedLines;
200                    }
201    
202                    int i = startPos - margin;
203    
204                    for (; i < 0; i++) {
205                            changedLines.add(CONTEXT_LINE);
206                    }
207    
208                    for (; i < startPos; i++) {
209                            if (i < stringList.size()) {
210                                    changedLines.add(stringList.get(i));
211                            }
212                    }
213    
214                    return changedLines;
215            }
216    
217            private static void _addResults(
218                    List<DiffResult> results, List<String> stringList,
219                    List<String> changedLines, int start, int end) {
220    
221                    changedLines.addAll(stringList.subList(start, end + 1));
222    
223                    DiffResult diffResult = new DiffResult(start, changedLines);
224    
225                    results.add(diffResult);
226            }
227    
228            private static int _calculateMargin(
229                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
230                    int sourceBeginPos, int targetBeginPos, int margin) {
231    
232                    int sourceMargin = _checkOverlapping(
233                            sourceResults, sourceBeginPos, margin);
234                    int targetMargin = _checkOverlapping(
235                            targetResults, targetBeginPos, margin);
236    
237                    if (sourceMargin < targetMargin) {
238                            return sourceMargin;
239                    }
240    
241                    return targetMargin;
242            }
243    
244            private static void _checkCharDiffs(
245                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
246                    List<String> sourceStringList, List<String> targetStringList,
247                    String addedMarkerStart, String addedMarkerEnd,
248                    String deletedMarkerStart, String deletedMarkerEnd,
249                    Difference difference, int margin) {
250    
251                    boolean aligned = false;
252    
253                    int i = difference.getDeletedStart();
254                    int j = difference.getAddedStart();
255    
256                    // A line with changed characters may have its position shifted some
257                    // lines above or below. These for loops will try to align these lines.
258                    // While these lines are not aligned, highlight them as either additions
259                    // or deletions.
260    
261                    for (; i <= difference.getDeletedEnd(); i++) {
262                            for (; j <= difference.getAddedEnd(); j++) {
263                                    if (_lineDiff(
264                                                    sourceResults, targetResults, sourceStringList,
265                                                    targetStringList, addedMarkerStart, addedMarkerEnd,
266                                                    deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
267    
268                                            aligned = true;
269    
270                                            break;
271                                    }
272                                    else {
273                                            _highlightLines(
274                                                    targetStringList, addedMarkerStart, addedMarkerEnd, j,
275                                                    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    
286                            if (aligned) {
287                                     break;
288                            }
289                            else {
290                                    _highlightLines(
291                                            sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
292                                            i);
293    
294                                    DiffResult sourceResult = new DiffResult(
295                                            i, sourceStringList.subList(i, i + 1));
296    
297                                    sourceResults.add(sourceResult);
298    
299                                    targetResults.add(new DiffResult(i, CONTEXT_LINE));
300                            }
301                    }
302    
303                    i = i + 1;
304                    j = j + 1;
305    
306                    // Lines are aligned, check for differences of the following lines.
307    
308                    for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
309                                    i++, j++) {
310    
311                            _lineDiff(
312                                    sourceResults, targetResults, sourceStringList,
313                                    targetStringList, addedMarkerStart, addedMarkerEnd,
314                                    deletedMarkerStart, deletedMarkerEnd, i, j, true);
315                    }
316    
317                    // After the for loop above, some lines might remained unchecked.
318                    // They are considered as deletions or additions.
319    
320                    for (; i <= difference.getDeletedEnd();i++) {
321                            _highlightLines(
322                                    sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
323    
324                            DiffResult sourceResult = new DiffResult(
325                                    i, sourceStringList.subList(i, i + 1));
326    
327                            sourceResults.add(sourceResult);
328    
329                            targetResults.add(new DiffResult(i, CONTEXT_LINE));
330                    }
331    
332                    for (; j <= difference.getAddedEnd(); j++) {
333                            _highlightLines(
334                                    targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
335    
336                            DiffResult targetResult = new DiffResult(
337                                    j, targetStringList.subList(j, j + 1));
338    
339                            targetResults.add(targetResult);
340    
341                            sourceResults.add(new DiffResult(j, CONTEXT_LINE));
342                    }
343            }
344    
345            private static int _checkOverlapping(
346                    List<DiffResult> results, int startPos, int margin) {
347    
348                    if (results.size() == 0 || (startPos - margin) < 0) {
349                            return margin;
350                    }
351    
352                    DiffResult lastDiff = results.get(results.size() - 1);
353    
354                    if (lastDiff.getChangedLines().size() == 0) {
355                            return margin;
356                    }
357    
358                    int lastChangedLine = (lastDiff.getLineNumber() - 1) +
359                            lastDiff.getChangedLines().size();
360    
361                    int currentChangedLine = startPos - margin;
362    
363                    if ((lastDiff.getChangedLines().size() == 1) &&
364                            (lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE))) {
365    
366                            currentChangedLine = currentChangedLine + 1;
367                    }
368    
369                    if (currentChangedLine < lastChangedLine) {
370                            return margin + currentChangedLine - lastChangedLine;
371                    }
372    
373                    return margin;
374            }
375    
376            private static void _highlightChars(
377                    List<String> stringList, String markerStart, String markerEnd,
378                    int startPos, int endPos) {
379    
380                    String start = markerStart + stringList.get(startPos);
381    
382                    stringList.set(startPos, start);
383    
384                    String end = stringList.get(endPos) + markerEnd;
385    
386                    stringList.set(endPos, end);
387            }
388    
389            private static void _highlightLines(
390                    List<String> stringList, String markerStart, String markerEnd,
391                    int startPos, int endPos) {
392    
393                    for (int i = startPos; i <= endPos; i++) {
394                            stringList.set(i, markerStart + stringList.get(i) + markerEnd);
395                    }
396            }
397    
398            private static boolean _lineDiff(
399                    List<DiffResult> sourceResults, List<DiffResult> targetResults,
400                    List<String> sourceStringList, List<String> targetStringList,
401                    String addedMarkerStart, String addedMarkerEnd,
402                    String deletedMarkerStart, String deletedMarkerEnd,
403                    int sourceChangedLine, int targetChangedLine, boolean aligned) {
404    
405                    String source = sourceStringList.get(sourceChangedLine);
406                    String target = targetStringList.get(targetChangedLine);
407    
408                    // Convert the lines to lists where each element are chars of the lines.
409    
410                    List<String> sourceList = _toList(source);
411                    List<String> targetList = _toList(target);
412    
413                    Diff diff = new Diff(sourceList, targetList);
414    
415                    List<Difference> differences = diff.diff();
416    
417                    Iterator<Difference> itr = differences.iterator();
418    
419                    int deletedChars = 0;
420                    int addedChars = 0;
421    
422                    // The following while loop will calculate how many characters of
423                    // the source line need to be changed to be equals to the target line.
424    
425                    while (itr.hasNext() && !aligned) {
426                            Difference difference = itr.next();
427    
428                            if (difference.getDeletedEnd() != Difference.NONE) {
429                                    deletedChars =
430                                            deletedChars +
431                                            (difference.getDeletedEnd() -
432                                                    difference.getDeletedStart() + 1);
433                            }
434    
435                            if (difference.getAddedEnd() != Difference.NONE) {
436                                    addedChars =
437                                            addedChars +
438                                            (difference.getAddedEnd() - difference.getAddedStart() + 1);
439                            }
440                    }
441    
442                    // If a lot of changes were needed (more than half of the source line
443                    // length), consider this as not aligned yet.
444    
445                    if ((deletedChars > (sourceList.size() / 2)) ||
446                            (addedChars > sourceList.size() / 2)) {
447    
448                            return false;
449                    }
450    
451                    itr = differences.iterator();
452    
453                    boolean sourceChanged = false;
454                    boolean targetChanged = false;
455    
456                    // Iterate over Differences between chars of these lines.
457    
458                    while (itr.hasNext()) {
459                            Difference difference = itr.next();
460    
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[] stringArray = line.split(StringPool.BLANK);
532    
533                    List<String> result = new ArrayList<String>();
534    
535                    for (int i = 1; i < stringArray.length; i++) {
536                            result.add(stringArray[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                    Iterator<String> itr = line.iterator();
550    
551                    while (itr.hasNext()) {
552                            sb.append(itr.next());
553                    }
554    
555                    return sb.toString();
556            }
557    
558    }