001
014
015 package com.liferay.portal.diff;
016
017 import com.liferay.portal.kernel.diff.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.diff.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.isEmpty() || ((startPos - margin) < 0)) {
372 return margin;
373 }
374
375 DiffResult lastDiff = results.get(results.size() - 1);
376
377 List<String> changedLines = lastDiff.getChangedLines();
378
379 if (changedLines.isEmpty()) {
380 return margin;
381 }
382
383 int lastChangedLine =
384 (lastDiff.getLineNumber() - 1) + changedLines.size();
385
386 int currentChangedLine = startPos - margin;
387
388 if ((changedLines.size() == 1) &&
389 changedLines.get(0).equals(CONTEXT_LINE)) {
390
391 currentChangedLine = currentChangedLine + 1;
392 }
393
394 if (currentChangedLine < lastChangedLine) {
395 return margin + currentChangedLine - lastChangedLine;
396 }
397
398 return margin;
399 }
400
401 private static void _highlightChars(
402 List<String> stringList, String markerStart, String markerEnd,
403 int startPos, int endPos) {
404
405 String start = markerStart + stringList.get(startPos);
406
407 stringList.set(startPos, start);
408
409 String end = stringList.get(endPos) + markerEnd;
410
411 stringList.set(endPos, end);
412 }
413
414 private static void _highlightLines(
415 List<String> stringList, String markerStart, String markerEnd,
416 int startPos, int endPos) {
417
418 for (int i = startPos; i <= endPos; i++) {
419 stringList.set(i, markerStart + stringList.get(i) + markerEnd);
420 }
421 }
422
423 private static boolean _isMaxLineLengthExceeded(
424 String sourceString, String targetString) {
425
426 if ((sourceString.length() > _DIFF_MAX_LINE_LENGTH) ||
427 (targetString.length() > _DIFF_MAX_LINE_LENGTH)) {
428
429 return true;
430 }
431
432 return false;
433 }
434
435 private static boolean _lineDiff(
436 List<DiffResult> sourceResults, List<DiffResult> targetResults,
437 List<String> sourceStringList, List<String> targetStringList,
438 String addedMarkerStart, String addedMarkerEnd,
439 String deletedMarkerStart, String deletedMarkerEnd,
440 int sourceChangedLine, int targetChangedLine, boolean aligned) {
441
442 String source = sourceStringList.get(sourceChangedLine);
443 String target = targetStringList.get(targetChangedLine);
444
445
446
447 List<String> sourceList = _toList(source);
448 List<String> targetList = _toList(target);
449
450 Diff diff = new Diff(sourceList, targetList);
451
452 List<Difference> differences = diff.diff();
453
454 int deletedChars = 0;
455 int addedChars = 0;
456
457
458
459
460 if (!aligned) {
461 for (Difference difference : differences) {
462 if (difference.getDeletedEnd() != Difference.NONE) {
463 deletedChars +=
464 (difference.getDeletedEnd() -
465 difference.getDeletedStart() + 1);
466 }
467
468 if (difference.getAddedEnd() != Difference.NONE) {
469 addedChars +=
470 (difference.getAddedEnd() - difference.getAddedStart() +
471 1);
472 }
473 }
474 }
475
476
477
478
479 if ((deletedChars > (sourceList.size() / 2)) ||
480 (addedChars > (sourceList.size() / 2))) {
481
482 return false;
483 }
484
485 boolean sourceChanged = false;
486 boolean targetChanged = false;
487
488
489
490 for (Difference difference : differences) {
491 if (difference.getAddedEnd() == Difference.NONE) {
492
493
494
495 _highlightChars(
496 sourceList, deletedMarkerStart, deletedMarkerEnd,
497 difference.getDeletedStart(), difference.getDeletedEnd());
498
499 sourceChanged = true;
500 }
501 else if (difference.getDeletedEnd() == Difference.NONE) {
502
503
504
505 _highlightChars(
506 targetList, addedMarkerStart, addedMarkerEnd,
507 difference.getAddedStart(), difference.getAddedEnd());
508
509 targetChanged = true;
510 }
511 else {
512
513
514
515 _highlightChars(
516 sourceList, deletedMarkerStart, deletedMarkerEnd,
517 difference.getDeletedStart(), difference.getDeletedEnd());
518
519 sourceChanged = true;
520
521 _highlightChars(
522 targetList, addedMarkerStart, addedMarkerEnd,
523 difference.getAddedStart(), difference.getAddedEnd());
524
525 targetChanged = true;
526 }
527 }
528
529 if (sourceChanged) {
530 DiffResult sourceResult = new DiffResult(
531 sourceChangedLine, _toString(sourceList));
532
533 sourceResults.add(sourceResult);
534
535 if (!targetChanged) {
536 DiffResult targetResult = new DiffResult(
537 targetChangedLine, target);
538
539 targetResults.add(targetResult);
540 }
541 }
542
543 if (targetChanged) {
544 if (!sourceChanged) {
545 DiffResult sourceResult = new DiffResult(
546 sourceChangedLine, source);
547
548 sourceResults.add(sourceResult);
549 }
550
551 DiffResult targetResult = new DiffResult(
552 targetChangedLine, _toString(targetList));
553
554 targetResults.add(targetResult);
555 }
556
557 return true;
558 }
559
560 private static List<String> _toList(String line) {
561 String[] lineParts = line.split(StringPool.BLANK);
562
563 List<String> result = new ArrayList<String>();
564
565 for (int i = 1; i < lineParts.length; i++) {
566 result.add(lineParts[i]);
567 }
568
569 return result;
570 }
571
572 private static String _toString(List<String> line) {
573 if (line.isEmpty()) {
574 return StringPool.BLANK;
575 }
576
577 StringBundler sb = new StringBundler(line.size());
578
579 for (String linePart : line) {
580 sb.append(linePart);
581 }
582
583 return sb.toString();
584 }
585
586 private static final int _DIFF_MAX_LINE_LENGTH = 5000;
587
588 }