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.List;
026
027 import org.incava.util.diff.Diff;
028 import org.incava.util.diff.Difference;
029
030
040 public class DiffImpl implements com.liferay.portal.kernel.util.Diff {
041
042
051 @Override
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
080 @Override
081 public List<DiffResult>[] diff(
082 Reader source, Reader target, String addedMarkerStart,
083 String addedMarkerEnd, String deletedMarkerStart,
084 String deletedMarkerEnd, int margin) {
085
086 List<DiffResult> sourceResults = new ArrayList<DiffResult>();
087 List<DiffResult> targetResults = new ArrayList<DiffResult>();
088
089 List<DiffResult>[] results = new List[] {sourceResults, targetResults};
090
091
092
093 List<String> sourceStringList = FileUtil.toList(source);
094 List<String> targetStringList = FileUtil.toList(target);
095
096
097
098 Diff diff = new Diff(sourceStringList, targetStringList);
099
100 List<Difference> differences = diff.diff();
101
102 for (Difference difference : differences) {
103 if (difference.getAddedEnd() == Difference.NONE) {
104
105
106
107 _highlightLines(
108 sourceStringList, deletedMarkerStart, deletedMarkerEnd,
109 difference.getDeletedStart(), difference.getDeletedEnd());
110
111 margin = _calculateMargin(
112 sourceResults, targetResults, difference.getDeletedStart(),
113 difference.getAddedStart(), margin);
114
115 List<String> changedLines = _addMargins(
116 sourceResults, sourceStringList,
117 difference.getDeletedStart(), margin);
118
119 _addResults(
120 sourceResults, sourceStringList, changedLines,
121 difference.getDeletedStart(), difference.getDeletedEnd());
122
123 changedLines = _addMargins(
124 targetResults, targetStringList, difference.getAddedStart(),
125 margin);
126
127 int deletedLines =
128 difference.getDeletedEnd() + 1 -
129 difference.getDeletedStart();
130
131 for (int i = 0; i < deletedLines; i++) {
132 changedLines.add(CONTEXT_LINE);
133 }
134
135 DiffResult diffResult = new DiffResult(
136 difference.getDeletedStart(), changedLines);
137
138 targetResults.add(diffResult);
139 }
140 else if (difference.getDeletedEnd() == Difference.NONE) {
141
142
143
144 _highlightLines(
145 targetStringList, addedMarkerStart, addedMarkerEnd,
146 difference.getAddedStart(), difference.getAddedEnd());
147
148 margin = _calculateMargin(
149 sourceResults, targetResults, difference.getDeletedStart(),
150 difference.getAddedStart(), margin);
151
152 List<String> changedLines = _addMargins(
153 sourceResults, sourceStringList,
154 difference.getDeletedStart(), margin);
155
156 int addedLines =
157 difference.getAddedEnd() + 1 - difference.getAddedStart();
158
159 for (int i = 0; i < addedLines; i++) {
160 changedLines.add(CONTEXT_LINE);
161 }
162
163 DiffResult diffResult = new DiffResult(
164 difference.getAddedStart(), changedLines);
165
166 sourceResults.add(diffResult);
167
168 changedLines = _addMargins(
169 targetResults, targetStringList, difference.getAddedStart(),
170 margin);
171
172 _addResults(
173 targetResults, targetStringList, changedLines,
174 difference.getAddedStart(), difference.getAddedEnd());
175 }
176 else {
177
178
179
180
181 _checkCharDiffs(
182 sourceResults, targetResults, sourceStringList,
183 targetStringList, addedMarkerStart, addedMarkerEnd,
184 deletedMarkerStart, deletedMarkerEnd, difference, margin);
185 }
186 }
187
188 return results;
189 }
190
191 private static List<String> _addMargins(
192 List<DiffResult> results, List<String> stringList, int startPos,
193 int margin) {
194
195 List<String> changedLines = new ArrayList<String>();
196
197 if ((margin == 0) || (startPos == 0)) {
198 return changedLines;
199 }
200
201 int i = startPos - margin;
202
203 for (; i < 0; i++) {
204 changedLines.add(CONTEXT_LINE);
205 }
206
207 for (; i < startPos; i++) {
208 if (i < stringList.size()) {
209 changedLines.add(stringList.get(i));
210 }
211 }
212
213 return changedLines;
214 }
215
216 private static void _addResults(
217 List<DiffResult> results, List<String> stringList,
218 List<String> changedLines, int start, int end) {
219
220 changedLines.addAll(stringList.subList(start, end + 1));
221
222 DiffResult diffResult = new DiffResult(start, changedLines);
223
224 results.add(diffResult);
225 }
226
227 private static int _calculateMargin(
228 List<DiffResult> sourceResults, List<DiffResult> targetResults,
229 int sourceBeginPos, int targetBeginPos, int margin) {
230
231 int sourceMargin = _checkOverlapping(
232 sourceResults, sourceBeginPos, margin);
233 int targetMargin = _checkOverlapping(
234 targetResults, targetBeginPos, margin);
235
236 if (sourceMargin < targetMargin) {
237 return sourceMargin;
238 }
239
240 return targetMargin;
241 }
242
243 private static void _checkCharDiffs(
244 List<DiffResult> sourceResults, List<DiffResult> targetResults,
245 List<String> sourceStringList, List<String> targetStringList,
246 String addedMarkerStart, String addedMarkerEnd,
247 String deletedMarkerStart, String deletedMarkerEnd,
248 Difference difference, int margin) {
249
250 boolean aligned = false;
251
252 int i = difference.getDeletedStart();
253 int j = difference.getAddedStart();
254
255
256
257
258
259
260 for (; i <= difference.getDeletedEnd(); i++) {
261 for (; j <= difference.getAddedEnd(); j++) {
262 if (!_isMaxLineLengthExceeded(
263 sourceStringList.get(i), targetStringList.get(j)) &&
264 _lineDiff(
265 sourceResults, targetResults, sourceStringList,
266 targetStringList, addedMarkerStart, addedMarkerEnd,
267 deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
268
269 aligned = true;
270
271 break;
272 }
273
274 _highlightLines(
275 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
276
277 DiffResult targetResult = new DiffResult(
278 j, targetStringList.subList(j, j + 1));
279
280 targetResults.add(targetResult);
281
282 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
283 }
284
285 if (aligned) {
286 break;
287 }
288
289 _highlightLines(
290 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
291
292 DiffResult sourceResult = new DiffResult(
293 i, sourceStringList.subList(i, i + 1));
294
295 sourceResults.add(sourceResult);
296
297 targetResults.add(new DiffResult(i, CONTEXT_LINE));
298 }
299
300 i = i + 1;
301 j = j + 1;
302
303
304
305 for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
306 i++, j++) {
307
308 if (!_isMaxLineLengthExceeded(
309 sourceStringList.get(i), targetStringList.get(j))) {
310
311 _lineDiff(
312 sourceResults, targetResults, sourceStringList,
313 targetStringList, addedMarkerStart, addedMarkerEnd,
314 deletedMarkerStart, deletedMarkerEnd, i, j, true);
315 }
316 else {
317 _highlightLines(
318 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
319 i);
320
321 DiffResult sourceResult = new DiffResult(
322 i, sourceStringList.subList(i, i + 1));
323
324 sourceResults.add(sourceResult);
325
326 targetResults.add(new DiffResult(i, CONTEXT_LINE));
327
328 _highlightLines(
329 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
330
331 DiffResult targetResult = new DiffResult(
332 j, targetStringList.subList(j, j + 1));
333
334 targetResults.add(targetResult);
335
336 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
337 }
338 }
339
340
341
342
343 for (; i <= difference.getDeletedEnd(); i++) {
344 _highlightLines(
345 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
346
347 DiffResult sourceResult = new DiffResult(
348 i, sourceStringList.subList(i, i + 1));
349
350 sourceResults.add(sourceResult);
351
352 targetResults.add(new DiffResult(i, CONTEXT_LINE));
353 }
354
355 for (; j <= difference.getAddedEnd(); j++) {
356 _highlightLines(
357 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
358
359 DiffResult targetResult = new DiffResult(
360 j, targetStringList.subList(j, j + 1));
361
362 targetResults.add(targetResult);
363
364 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
365 }
366 }
367
368 private static int _checkOverlapping(
369 List<DiffResult> results, int startPos, int margin) {
370
371 if ((results.size() == 0) || ((startPos - margin) < 0)) {
372 return margin;
373 }
374
375 DiffResult lastDiff = results.get(results.size() - 1);
376
377 if (lastDiff.getChangedLines().size() == 0) {
378 return margin;
379 }
380
381 int lastChangedLine =
382 (lastDiff.getLineNumber() - 1) + lastDiff.getChangedLines().size();
383
384 int currentChangedLine = startPos - margin;
385
386 if ((lastDiff.getChangedLines().size() == 1) &&
387 lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE)) {
388
389 currentChangedLine = currentChangedLine + 1;
390 }
391
392 if (currentChangedLine < lastChangedLine) {
393 return margin + currentChangedLine - lastChangedLine;
394 }
395
396 return margin;
397 }
398
399 private static void _highlightChars(
400 List<String> stringList, String markerStart, String markerEnd,
401 int startPos, int endPos) {
402
403 String start = markerStart + stringList.get(startPos);
404
405 stringList.set(startPos, start);
406
407 String end = stringList.get(endPos) + markerEnd;
408
409 stringList.set(endPos, end);
410 }
411
412 private static void _highlightLines(
413 List<String> stringList, String markerStart, String markerEnd,
414 int startPos, int endPos) {
415
416 for (int i = startPos; i <= endPos; i++) {
417 stringList.set(i, markerStart + stringList.get(i) + markerEnd);
418 }
419 }
420
421 private static boolean _isMaxLineLengthExceeded(
422 String sourceString, String targetString) {
423
424 if ((sourceString.length() > _DIFF_MAX_LINE_LENGTH) ||
425 (targetString.length() > _DIFF_MAX_LINE_LENGTH)) {
426
427 return true;
428 }
429
430 return false;
431 }
432
433 private static boolean _lineDiff(
434 List<DiffResult> sourceResults, List<DiffResult> targetResults,
435 List<String> sourceStringList, List<String> targetStringList,
436 String addedMarkerStart, String addedMarkerEnd,
437 String deletedMarkerStart, String deletedMarkerEnd,
438 int sourceChangedLine, int targetChangedLine, boolean aligned) {
439
440 String source = sourceStringList.get(sourceChangedLine);
441 String target = targetStringList.get(targetChangedLine);
442
443
444
445 List<String> sourceList = _toList(source);
446 List<String> targetList = _toList(target);
447
448 Diff diff = new Diff(sourceList, targetList);
449
450 List<Difference> differences = diff.diff();
451
452 int deletedChars = 0;
453 int addedChars = 0;
454
455
456
457
458 if (!aligned) {
459 for (Difference difference : differences) {
460 if (difference.getDeletedEnd() != Difference.NONE) {
461 deletedChars +=
462 (difference.getDeletedEnd() -
463 difference.getDeletedStart() + 1);
464 }
465
466 if (difference.getAddedEnd() != Difference.NONE) {
467 addedChars +=
468 (difference.getAddedEnd() - difference.getAddedStart() +
469 1);
470 }
471 }
472 }
473
474
475
476
477 if ((deletedChars > (sourceList.size() / 2)) ||
478 (addedChars > (sourceList.size() / 2))) {
479
480 return false;
481 }
482
483 boolean sourceChanged = false;
484 boolean targetChanged = false;
485
486
487
488 for (Difference difference : differences) {
489 if (difference.getAddedEnd() == Difference.NONE) {
490
491
492
493 _highlightChars(
494 sourceList, deletedMarkerStart, deletedMarkerEnd,
495 difference.getDeletedStart(), 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, deletedMarkerEnd,
515 difference.getDeletedStart(), difference.getDeletedEnd());
516
517 sourceChanged = true;
518
519 _highlightChars(
520 targetList, addedMarkerStart, addedMarkerEnd,
521 difference.getAddedStart(), difference.getAddedEnd());
522
523 targetChanged = true;
524 }
525 }
526
527 if (sourceChanged) {
528 DiffResult sourceResult = new DiffResult(
529 sourceChangedLine, _toString(sourceList));
530
531 sourceResults.add(sourceResult);
532
533 if (!targetChanged) {
534 DiffResult targetResult = new DiffResult(
535 targetChangedLine, target);
536
537 targetResults.add(targetResult);
538 }
539 }
540
541 if (targetChanged) {
542 if (!sourceChanged) {
543 DiffResult sourceResult = new DiffResult(
544 sourceChangedLine, source);
545
546 sourceResults.add(sourceResult);
547 }
548
549 DiffResult targetResult = new DiffResult(
550 targetChangedLine, _toString(targetList));
551
552 targetResults.add(targetResult);
553 }
554
555 return true;
556 }
557
558 private static List<String> _toList(String line) {
559 String[] lineParts = line.split(StringPool.BLANK);
560
561 List<String> result = new ArrayList<String>();
562
563 for (int i = 1; i < lineParts.length; i++) {
564 result.add(lineParts[i]);
565 }
566
567 return result;
568 }
569
570 private static String _toString(List<String> line) {
571 if (line.isEmpty()) {
572 return StringPool.BLANK;
573 }
574
575 StringBundler sb = new StringBundler(line.size());
576
577 for (String linePart : line) {
578 sb.append(linePart);
579 }
580
581 return sb.toString();
582 }
583
584 private static final int _DIFF_MAX_LINE_LENGTH = 5000;
585
586 }