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