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