1   /**
2    * Copyright (c) 2000-2009 Liferay, Inc. All rights reserved.
3    *
4    *
5    *
6    *
7    * The contents of this file are subject to the terms of the Liferay Enterprise
8    * Subscription License ("License"). You may not use this file except in
9    * compliance with the License. You can obtain a copy of the License by
10   * contacting Liferay, Inc. See the License for the specific language governing
11   * permissions and limitations under the License, including but not limited to
12   * distribution rights of the Software.
13   *
14   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19   * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20   * SOFTWARE.
21   */
22  
23  package com.liferay.portal.util;
24  
25  import com.liferay.portal.kernel.util.DiffResult;
26  import com.liferay.portal.kernel.util.FileUtil;
27  import com.liferay.portal.kernel.util.StringPool;
28  
29  import java.io.Reader;
30  
31  import java.util.ArrayList;
32  import java.util.Iterator;
33  import java.util.List;
34  
35  import org.incava.util.diff.Diff;
36  import org.incava.util.diff.Difference;
37  
38  /**
39   * <a href="DiffImpl.java.html"><b><i>View Source</i></b></a>
40   *
41   * <p>
42   * This class can compare two different versions of a text. Source refers to the
43   * earliest version of the text and target refers to a modified version of
44   * source. Changes are considered either as a removal from the source or as an
45   * addition to the target. This class detects changes to an entire line and also
46   * detects changes within lines, such as, removal or addition of characters.
47   * Take a look at <code>DiffTest</code> to see the expected inputs and outputs.
48   * </p>
49   *
50   * @author Bruno Farache
51   */
52  public class DiffImpl implements com.liferay.portal.kernel.util.Diff {
53  
54      /**
55       * This is a diff method with default values.
56       *
57       * @return an array containing two lists of <code>DiffResults</code>, the
58       *         first element contains DiffResults related to changes in source
59       *         and the second element to changes in target
60       */
61      public List<DiffResult>[] diff(Reader source, Reader target) {
62          int margin = 2;
63  
64          return diff(
65              source, target, OPEN_INS, CLOSE_INS, OPEN_DEL, CLOSE_DEL, margin);
66      }
67  
68      /**
69       * The main entrance of this class. This method will compare the two texts,
70       * highlight the changes by enclosing them with markers and return a list of
71       * <code>DiffResults</code>.
72       *
73       * @return an array containing two lists of <code>DiffResults</code>, the
74       *         first element contains DiffResults related to changes in source
75       *         and the second element to changes in target
76       */
77      public List<DiffResult>[] diff(
78          Reader source, Reader target, String addedMarkerStart,
79          String addedMarkerEnd, String deletedMarkerStart,
80          String deletedMarkerEnd, int margin) {
81  
82          List<DiffResult> sourceResults = new ArrayList<DiffResult>();
83          List<DiffResult> targetResults = new ArrayList<DiffResult>();
84  
85          List<DiffResult>[] results = new List[] {sourceResults, targetResults};
86  
87          // Convert the texts to Lists where each element are lines of the texts.
88  
89          List<String> sourceStringList = FileUtil.toList(source);
90          List<String> targetStringList = FileUtil.toList(target);
91  
92          // Make a a Diff of these lines and iterate over their Differences.
93  
94          Diff diff = new Diff(sourceStringList, targetStringList);
95  
96          List<Difference> differences = diff.diff();
97  
98          Iterator<Difference> itr = differences.iterator();
99  
100         while (itr.hasNext()) {
101             Difference difference = itr.next();
102 
103             if (difference.getAddedEnd() == Difference.NONE) {
104 
105                 // Lines were deleted from source only.
106 
107                 _highlightLines(
108                     sourceStringList, deletedMarkerStart,
109                     deletedMarkerEnd, difference.getDeletedStart(),
110                     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(
224             start, changedLines);
225 
226         results.add(diffResult);
227     }
228 
229     private static int _calculateMargin(
230         List<DiffResult> sourceResults, List<DiffResult> targetResults,
231         int sourceBeginPos, int targetBeginPos, int margin) {
232 
233         int sourceMargin = _checkOverlapping(
234             sourceResults, sourceBeginPos, margin);
235         int targetMargin = _checkOverlapping(
236             targetResults, targetBeginPos, margin);
237 
238         if (sourceMargin < targetMargin) {
239             return sourceMargin;
240         }
241 
242         return targetMargin;
243     }
244 
245     private static void _checkCharDiffs(
246         List<DiffResult> sourceResults, List<DiffResult> targetResults,
247         List<String> sourceStringList, List<String> targetStringList,
248         String addedMarkerStart, String addedMarkerEnd,
249         String deletedMarkerStart, String deletedMarkerEnd,
250         Difference difference, int margin) {
251 
252         boolean aligned = false;
253 
254         int i = difference.getDeletedStart();
255         int j = difference.getAddedStart();
256 
257         // A line with changed characters may have its position shifted some
258         // lines above or below. These for loops will try to align these lines.
259         // While these lines are not aligned, highlight them as either additions
260         // or deletions.
261 
262         for (; i <= difference.getDeletedEnd(); i++) {
263             for (; j <= difference.getAddedEnd(); j++) {
264                 if (_lineDiff(
265                         sourceResults, targetResults, sourceStringList,
266                         targetStringList, addedMarkerStart, addedMarkerEnd,
267                         deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
268 
269                     aligned = true;
270 
271                     break;
272                 }
273                 else {
274                     _highlightLines(
275                         targetStringList, addedMarkerStart, addedMarkerEnd, j,
276                         j);
277 
278                     DiffResult targetResult = new DiffResult(
279                         j, targetStringList.subList(j, j + 1));
280 
281                     targetResults.add(targetResult);
282 
283                     sourceResults.add(new DiffResult(j, CONTEXT_LINE));
284                 }
285             }
286 
287             if (aligned) {
288                  break;
289             }
290             else {
291                 _highlightLines(
292                     sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
293                     i);
294 
295                 DiffResult sourceResult = new DiffResult(
296                     i, sourceStringList.subList(i, i + 1));
297 
298                 sourceResults.add(sourceResult);
299 
300                 targetResults.add(new DiffResult(i, CONTEXT_LINE));
301             }
302         }
303 
304         i = i + 1;
305         j = j + 1;
306 
307         // Lines are aligned, check for differences of the following lines.
308 
309         for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
310                 i++, j++) {
311 
312             _lineDiff(
313                 sourceResults, targetResults, sourceStringList,
314                 targetStringList, addedMarkerStart, addedMarkerEnd,
315                 deletedMarkerStart, deletedMarkerEnd, i, j, true);
316         }
317 
318         // After the for loop above, some lines might remained unchecked.
319         // They are considered as deletions or additions.
320 
321         for (; i <= difference.getDeletedEnd();i++) {
322             _highlightLines(
323                 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
324 
325             DiffResult sourceResult = new DiffResult(
326                 i, sourceStringList.subList(i, i + 1));
327 
328             sourceResults.add(sourceResult);
329 
330             targetResults.add(new DiffResult(i, CONTEXT_LINE));
331         }
332 
333         for (; j <= difference.getAddedEnd(); j++) {
334             _highlightLines(
335                 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
336 
337             DiffResult targetResult = new DiffResult(
338                 j, targetStringList.subList(j, j + 1));
339 
340             targetResults.add(targetResult);
341 
342             sourceResults.add(new DiffResult(j, CONTEXT_LINE));
343         }
344     }
345 
346     private static int _checkOverlapping(
347         List<DiffResult> results, int startPos, int margin) {
348 
349         if (results.size() == 0 || (startPos - margin) < 0) {
350             return margin;
351         }
352 
353         DiffResult lastDiff = results.get(results.size() - 1);
354 
355         if (lastDiff.getChangedLines().size() == 0) {
356             return margin;
357         }
358 
359         int lastChangedLine = (lastDiff.getLineNumber() - 1) +
360             lastDiff.getChangedLines().size();
361 
362         int currentChangedLine = startPos - margin;
363 
364         if ((lastDiff.getChangedLines().size() == 1) &&
365             (lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE))) {
366 
367             currentChangedLine = currentChangedLine + 1;
368         }
369 
370         if (currentChangedLine < lastChangedLine) {
371             return margin + currentChangedLine - lastChangedLine;
372         }
373 
374         return margin;
375     }
376 
377     private static void _highlightChars(
378         List<String> stringList, String markerStart, String markerEnd,
379         int startPos, int endPos) {
380 
381         String start = markerStart + stringList.get(startPos);
382 
383         stringList.set(startPos, start);
384 
385         String end = stringList.get(endPos) + markerEnd;
386 
387         stringList.set(endPos, end);
388     }
389 
390     private static void _highlightLines(
391         List<String> stringList, String markerStart, String markerEnd,
392         int startPos, int endPos) {
393 
394         for (int i = startPos; i <= endPos; i++) {
395             stringList.set(i, markerStart + stringList.get(i) + markerEnd);
396         }
397     }
398 
399     private static boolean _lineDiff(
400         List<DiffResult> sourceResults, List<DiffResult> targetResults,
401         List<String> sourceStringList, List<String> targetStringList,
402         String addedMarkerStart, String addedMarkerEnd,
403         String deletedMarkerStart, String deletedMarkerEnd,
404         int sourceChangedLine, int targetChangedLine, boolean aligned) {
405 
406         String source = sourceStringList.get(sourceChangedLine);
407         String target = targetStringList.get(targetChangedLine);
408 
409         // Convert the lines to lists where each element are chars of the lines.
410 
411         List<String> sourceList = _toList(source);
412         List<String> targetList = _toList(target);
413 
414         Diff diff = new Diff(sourceList, targetList);
415 
416         List<Difference> differences = diff.diff();
417 
418         Iterator<Difference> itr = differences.iterator();
419 
420         int deletedChars = 0;
421         int addedChars = 0;
422 
423         // The following while loop will calculate how many characters of
424         // the source line need to be changed to be equals to the target line.
425 
426         while (itr.hasNext() && !aligned) {
427             Difference difference = itr.next();
428 
429             if (difference.getDeletedEnd() != Difference.NONE) {
430                 deletedChars =
431                     deletedChars +
432                     (difference.getDeletedEnd() -
433                         difference.getDeletedStart() + 1);
434             }
435 
436             if (difference.getAddedEnd() != Difference.NONE) {
437                 addedChars =
438                     addedChars +
439                     (difference.getAddedEnd() - difference.getAddedStart() + 1);
440             }
441         }
442 
443         // If a lot of changes were needed (more than half of the source line
444         // length), consider this as not aligned yet.
445 
446         if ((deletedChars > (sourceList.size() / 2)) ||
447             (addedChars > sourceList.size() / 2)) {
448 
449             return false;
450         }
451 
452         itr = differences.iterator();
453 
454         boolean sourceChanged = false;
455         boolean targetChanged = false;
456 
457         // Iterate over Differences between chars of these lines.
458 
459         while (itr.hasNext()) {
460             Difference difference = itr.next();
461 
462             if (difference.getAddedEnd() == Difference.NONE) {
463 
464                 // Chars were deleted from source only.
465 
466                 _highlightChars(
467                     sourceList, deletedMarkerStart,
468                     deletedMarkerEnd, difference.getDeletedStart(),
469                     difference.getDeletedEnd());
470 
471                 sourceChanged = true;
472             }
473             else if (difference.getDeletedEnd() == Difference.NONE) {
474 
475                 // Chars were added to target only.
476 
477                 _highlightChars(
478                     targetList, addedMarkerStart, addedMarkerEnd,
479                     difference.getAddedStart(), difference.getAddedEnd());
480 
481                 targetChanged = true;
482             }
483             else {
484 
485                 // Chars were both deleted and added.
486 
487                 _highlightChars(
488                     sourceList, deletedMarkerStart,
489                     deletedMarkerEnd, difference.getDeletedStart(),
490                     difference.getDeletedEnd());
491 
492                 sourceChanged = true;
493 
494                 _highlightChars(
495                     targetList, addedMarkerStart, addedMarkerEnd,
496                     difference.getAddedStart(), difference.getAddedEnd());
497 
498                 targetChanged = true;
499             }
500         }
501 
502         if (sourceChanged) {
503             DiffResult sourceResult = new DiffResult(
504                 sourceChangedLine, _toString(sourceList));
505 
506             sourceResults.add(sourceResult);
507 
508             if (!targetChanged) {
509                 DiffResult targetResult = new DiffResult(
510                     targetChangedLine, target);
511 
512                 targetResults.add(targetResult);
513             }
514         }
515 
516         if (targetChanged) {
517             if (!sourceChanged) {
518                 DiffResult sourceResult = new DiffResult(
519                     sourceChangedLine, source);
520 
521                 sourceResults.add(sourceResult);
522             }
523 
524             DiffResult targetResult = new DiffResult(
525                 targetChangedLine, _toString(targetList));
526 
527             targetResults.add(targetResult);
528         }
529 
530         return true;
531     }
532 
533     private static List<String> _toList(String line) {
534         String[] stringArray = line.split(StringPool.BLANK);
535 
536         List<String> result = new ArrayList<String>();
537 
538         for (int i = 1; i < stringArray.length; i++) {
539             result.add(stringArray[i]);
540         }
541 
542         return result;
543     }
544 
545     private static String _toString(List<String> line) {
546         StringBuilder sb = new StringBuilder();
547 
548         Iterator<String> itr = line.iterator();
549 
550         while (itr.hasNext()) {
551             sb.append(itr.next());
552         }
553 
554         return sb.toString();
555     }
556 
557 }