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