001
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
043 public class DiffImpl implements com.liferay.portal.kernel.util.Diff {
044
045
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
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
079
080 List<String> sourceStringList = FileUtil.toList(source);
081 List<String> targetStringList = FileUtil.toList(target);
082
083
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
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
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
171
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
248
249
250
251
252 for (; i <= difference.getDeletedEnd(); i++) {
253 for (; j <= difference.getAddedEnd(); j++) {
254 if (!_isMaxLineLengthExceeded(
255 sourceStringList.get(i), targetStringList.get(j)) &&
256 _lineDiff(
257 sourceResults, targetResults, sourceStringList,
258 targetStringList, addedMarkerStart, addedMarkerEnd,
259 deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
260
261 aligned = true;
262
263 break;
264 }
265
266 _highlightLines(
267 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
268
269 DiffResult targetResult = new DiffResult(
270 j, targetStringList.subList(j, j + 1));
271
272 targetResults.add(targetResult);
273
274 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
275 }
276
277 if (aligned) {
278 break;
279 }
280
281 _highlightLines(
282 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
283
284 DiffResult sourceResult = new DiffResult(
285 i, sourceStringList.subList(i, i + 1));
286
287 sourceResults.add(sourceResult);
288
289 targetResults.add(new DiffResult(i, CONTEXT_LINE));
290 }
291
292 i = i + 1;
293 j = j + 1;
294
295
296
297 for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
298 i++, j++) {
299
300 if (!_isMaxLineLengthExceeded(
301 sourceStringList.get(i), targetStringList.get(j))) {
302
303 _lineDiff(
304 sourceResults, targetResults, sourceStringList,
305 targetStringList, addedMarkerStart, addedMarkerEnd,
306 deletedMarkerStart, deletedMarkerEnd, i, j, true);
307 }
308 else {
309 _highlightLines(
310 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
311 i);
312
313 DiffResult sourceResult = new DiffResult(
314 i, sourceStringList.subList(i, i + 1));
315
316 sourceResults.add(sourceResult);
317
318 targetResults.add(new DiffResult(i, CONTEXT_LINE));
319
320 _highlightLines(
321 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
322
323 DiffResult targetResult = new DiffResult(
324 j, targetStringList.subList(j, j + 1));
325
326 targetResults.add(targetResult);
327
328 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
329 }
330 }
331
332
333
334
335 for (; i <= difference.getDeletedEnd();i++) {
336 _highlightLines(
337 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
338
339 DiffResult sourceResult = new DiffResult(
340 i, sourceStringList.subList(i, i + 1));
341
342 sourceResults.add(sourceResult);
343
344 targetResults.add(new DiffResult(i, CONTEXT_LINE));
345 }
346
347 for (; j <= difference.getAddedEnd(); j++) {
348 _highlightLines(
349 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
350
351 DiffResult targetResult = new DiffResult(
352 j, targetStringList.subList(j, j + 1));
353
354 targetResults.add(targetResult);
355
356 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
357 }
358 }
359
360 private static int _checkOverlapping(
361 List<DiffResult> results, int startPos, int margin) {
362
363 if (results.size() == 0 || (startPos - margin) < 0) {
364 return margin;
365 }
366
367 DiffResult lastDiff = results.get(results.size() - 1);
368
369 if (lastDiff.getChangedLines().size() == 0) {
370 return margin;
371 }
372
373 int lastChangedLine = (lastDiff.getLineNumber() - 1) +
374 lastDiff.getChangedLines().size();
375
376 int currentChangedLine = startPos - margin;
377
378 if ((lastDiff.getChangedLines().size() == 1) &&
379 (lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE))) {
380
381 currentChangedLine = currentChangedLine + 1;
382 }
383
384 if (currentChangedLine < lastChangedLine) {
385 return margin + currentChangedLine - lastChangedLine;
386 }
387
388 return margin;
389 }
390
391 private static boolean _isMaxLineLengthExceeded(
392 String sourceString, String targetString) {
393
394 if ((sourceString.length() > _DIFF_MAX_LINE_LENGTH) ||
395 (targetString.length() > _DIFF_MAX_LINE_LENGTH)) {
396
397 return true;
398 }
399
400 return false;
401 }
402
403 private static void _highlightChars(
404 List<String> stringList, String markerStart, String markerEnd,
405 int startPos, int endPos) {
406
407 String start = markerStart + stringList.get(startPos);
408
409 stringList.set(startPos, start);
410
411 String end = stringList.get(endPos) + markerEnd;
412
413 stringList.set(endPos, end);
414 }
415
416 private static void _highlightLines(
417 List<String> stringList, String markerStart, String markerEnd,
418 int startPos, int endPos) {
419
420 for (int i = startPos; i <= endPos; i++) {
421 stringList.set(i, markerStart + stringList.get(i) + markerEnd);
422 }
423 }
424
425 private static boolean _lineDiff(
426 List<DiffResult> sourceResults, List<DiffResult> targetResults,
427 List<String> sourceStringList, List<String> targetStringList,
428 String addedMarkerStart, String addedMarkerEnd,
429 String deletedMarkerStart, String deletedMarkerEnd,
430 int sourceChangedLine, int targetChangedLine, boolean aligned) {
431
432 String source = sourceStringList.get(sourceChangedLine);
433 String target = targetStringList.get(targetChangedLine);
434
435
436
437 List<String> sourceList = _toList(source);
438 List<String> targetList = _toList(target);
439
440 Diff diff = new Diff(sourceList, targetList);
441
442 List<Difference> differences = diff.diff();
443
444 Iterator<Difference> itr = differences.iterator();
445
446 int deletedChars = 0;
447 int addedChars = 0;
448
449
450
451
452 while (itr.hasNext() && !aligned) {
453 Difference difference = itr.next();
454
455 if (difference.getDeletedEnd() != Difference.NONE) {
456 deletedChars =
457 deletedChars +
458 (difference.getDeletedEnd() -
459 difference.getDeletedStart() + 1);
460 }
461
462 if (difference.getAddedEnd() != Difference.NONE) {
463 addedChars =
464 addedChars +
465 (difference.getAddedEnd() - difference.getAddedStart() + 1);
466 }
467 }
468
469
470
471
472 if ((deletedChars > (sourceList.size() / 2)) ||
473 (addedChars > sourceList.size() / 2)) {
474
475 return false;
476 }
477
478 itr = differences.iterator();
479
480 boolean sourceChanged = false;
481 boolean targetChanged = false;
482
483
484
485 while (itr.hasNext()) {
486 Difference difference = itr.next();
487
488 if (difference.getAddedEnd() == Difference.NONE) {
489
490
491
492 _highlightChars(
493 sourceList, deletedMarkerStart,
494 deletedMarkerEnd, difference.getDeletedStart(),
495 difference.getDeletedEnd());
496
497 sourceChanged = true;
498 }
499 else if (difference.getDeletedEnd() == Difference.NONE) {
500
501
502
503 _highlightChars(
504 targetList, addedMarkerStart, addedMarkerEnd,
505 difference.getAddedStart(), difference.getAddedEnd());
506
507 targetChanged = true;
508 }
509 else {
510
511
512
513 _highlightChars(
514 sourceList, deletedMarkerStart,
515 deletedMarkerEnd, difference.getDeletedStart(),
516 difference.getDeletedEnd());
517
518 sourceChanged = true;
519
520 _highlightChars(
521 targetList, addedMarkerStart, addedMarkerEnd,
522 difference.getAddedStart(), difference.getAddedEnd());
523
524 targetChanged = true;
525 }
526 }
527
528 if (sourceChanged) {
529 DiffResult sourceResult = new DiffResult(
530 sourceChangedLine, _toString(sourceList));
531
532 sourceResults.add(sourceResult);
533
534 if (!targetChanged) {
535 DiffResult targetResult = new DiffResult(
536 targetChangedLine, target);
537
538 targetResults.add(targetResult);
539 }
540 }
541
542 if (targetChanged) {
543 if (!sourceChanged) {
544 DiffResult sourceResult = new DiffResult(
545 sourceChangedLine, source);
546
547 sourceResults.add(sourceResult);
548 }
549
550 DiffResult targetResult = new DiffResult(
551 targetChangedLine, _toString(targetList));
552
553 targetResults.add(targetResult);
554 }
555
556 return true;
557 }
558
559 private static List<String> _toList(String line) {
560 String[] stringArray = line.split(StringPool.BLANK);
561
562 List<String> result = new ArrayList<String>();
563
564 for (int i = 1; i < stringArray.length; i++) {
565 result.add(stringArray[i]);
566 }
567
568 return result;
569 }
570
571 private static String _toString(List<String> line) {
572 if (line.isEmpty()) {
573 return StringPool.BLANK;
574 }
575
576 StringBundler sb = new StringBundler(line.size());
577
578 Iterator<String> itr = line.iterator();
579
580 while (itr.hasNext()) {
581 sb.append(itr.next());
582 }
583
584 return sb.toString();
585 }
586
587 private static int _DIFF_MAX_LINE_LENGTH = 5000;
588
589 }