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