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