1
14
15 package com.liferay.util.diff;
16
17 import com.liferay.portal.kernel.util.FileUtil;
18 import com.liferay.portal.kernel.util.StringBundler;
19 import com.liferay.portal.kernel.util.StringPool;
20
21 import java.io.Reader;
22
23 import java.util.ArrayList;
24 import java.util.Iterator;
25 import java.util.List;
26
27 import org.incava.util.diff.Diff;
28 import org.incava.util.diff.Difference;
29
30
46 public class DiffUtil {
47
48 public static final String OPEN_INS = "<ins>";
49
50 public static final String CLOSE_INS = "</ins>";
51
52 public static final String OPEN_DEL = "<del>";
53
54 public static final String CLOSE_DEL = "</del>";
55
56 public static final String CONTEXT_LINE = "#context#line#";
57
58
65 public static List<DiffResult>[] diff(Reader source, Reader target) {
66 int margin = 2;
67
68 return diff(
69 source, target, OPEN_INS, CLOSE_INS, OPEN_DEL, CLOSE_DEL, margin);
70 }
71
72
81 public static List<DiffResult>[] diff(
82 Reader source, Reader target, String addedMarkerStart,
83 String addedMarkerEnd, String deletedMarkerStart,
84 String deletedMarkerEnd, int margin) {
85
86 List<DiffResult> sourceResults = new ArrayList<DiffResult>();
87 List<DiffResult> targetResults = new ArrayList<DiffResult>();
88
89 List<DiffResult>[] results = new List[] {sourceResults, targetResults};
90
91
93 List<String> sourceStringList = FileUtil.toList(source);
94 List<String> targetStringList = FileUtil.toList(target);
95
96
98 Diff diff = new Diff(sourceStringList, targetStringList);
99
100 List<Difference> differences = diff.diff();
101
102 Iterator<Difference> itr = differences.iterator();
103
104 while (itr.hasNext()) {
105 Difference difference = itr.next();
106
107 if (difference.getAddedEnd() == Difference.NONE) {
108
109
111 _highlightLines(
112 sourceStringList, deletedMarkerStart,
113 deletedMarkerEnd, difference.getDeletedStart(),
114 difference.getDeletedEnd());
115
116 margin = _calculateMargin(
117 sourceResults, targetResults, difference.getDeletedStart(),
118 difference.getAddedStart(), margin);
119
120 List<String> changedLines = _addMargins(
121 sourceResults, sourceStringList,
122 difference.getDeletedStart(), margin);
123
124 _addResults(
125 sourceResults, sourceStringList, changedLines,
126 difference.getDeletedStart(), difference.getDeletedEnd());
127
128 changedLines = _addMargins(
129 targetResults, targetStringList, difference.getAddedStart(),
130 margin);
131
132 int deletedLines =
133 difference.getDeletedEnd() + 1 -
134 difference.getDeletedStart();
135
136 for (int i = 0; i < deletedLines; i++) {
137 changedLines.add(CONTEXT_LINE);
138 }
139
140 DiffResult diffResult = new DiffResult(
141 difference.getDeletedStart(), changedLines);
142
143 targetResults.add(diffResult);
144 }
145 else if (difference.getDeletedEnd() == Difference.NONE) {
146
147
149 _highlightLines(
150 targetStringList, addedMarkerStart, addedMarkerEnd,
151 difference.getAddedStart(), difference.getAddedEnd());
152
153 margin = _calculateMargin(
154 sourceResults, targetResults, difference.getDeletedStart(),
155 difference.getAddedStart(), margin);
156
157 List<String> changedLines = _addMargins(
158 sourceResults, sourceStringList,
159 difference.getDeletedStart(), margin);
160
161 int addedLines =
162 difference.getAddedEnd() + 1 - difference.getAddedStart();
163
164 for (int i = 0; i < addedLines; i++) {
165 changedLines.add(CONTEXT_LINE);
166 }
167
168 DiffResult diffResult = new DiffResult(
169 difference.getAddedStart(), changedLines);
170
171 sourceResults.add(diffResult);
172
173 changedLines = _addMargins(
174 targetResults, targetStringList, difference.getAddedStart(),
175 margin);
176
177 _addResults(
178 targetResults, targetStringList, changedLines,
179 difference.getAddedStart(), difference.getAddedEnd());
180 }
181 else {
182
183
186 _checkCharDiffs(
187 sourceResults, targetResults, sourceStringList,
188 targetStringList, addedMarkerStart, addedMarkerEnd,
189 deletedMarkerStart, deletedMarkerEnd, difference, margin);
190 }
191 }
192
193 return results;
194 }
195
196 private static List<String> _addMargins(
197 List<DiffResult> results, List<String> stringList, int startPos,
198 int margin) {
199
200 List<String> changedLines = new ArrayList<String>();
201
202 if (margin == 0 || startPos == 0) {
203 return changedLines;
204 }
205
206 int i = startPos - margin;
207
208 for (; i < 0; i++) {
209 changedLines.add(CONTEXT_LINE);
210 }
211
212 for (; i < startPos; i++) {
213 if (i < stringList.size()) {
214 changedLines.add(stringList.get(i));
215 }
216 }
217
218 return changedLines;
219 }
220
221 private static void _addResults(
222 List<DiffResult> results, List<String> stringList,
223 List<String> changedLines, int start, int end) {
224
225 changedLines.addAll(stringList.subList(start, end + 1));
226
227 DiffResult diffResult = new DiffResult(
228 start, changedLines);
229
230 results.add(diffResult);
231 }
232
233 private static int _calculateMargin(
234 List<DiffResult> sourceResults, List<DiffResult> targetResults,
235 int sourceBeginPos, int targetBeginPos, int margin) {
236
237 int sourceMargin = _checkOverlapping(
238 sourceResults, sourceBeginPos, margin);
239 int targetMargin = _checkOverlapping(
240 targetResults, targetBeginPos, margin);
241
242 if (sourceMargin < targetMargin) {
243 return sourceMargin;
244 }
245
246 return targetMargin;
247 }
248
249 private static void _checkCharDiffs(
250 List<DiffResult> sourceResults, List<DiffResult> targetResults,
251 List<String> sourceStringList, List<String> targetStringList,
252 String addedMarkerStart, String addedMarkerEnd,
253 String deletedMarkerStart, String deletedMarkerEnd,
254 Difference difference, int margin) {
255
256 boolean aligned = false;
257
258 int i = difference.getDeletedStart();
259 int j = difference.getAddedStart();
260
261
266 for (; i <= difference.getDeletedEnd(); i++) {
267 for (; j <= difference.getAddedEnd(); j++) {
268 if (_lineDiff(
269 sourceResults, targetResults, sourceStringList,
270 targetStringList, addedMarkerStart, addedMarkerEnd,
271 deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
272
273 aligned = true;
274
275 break;
276 }
277 else {
278 _highlightLines(
279 targetStringList, addedMarkerStart, addedMarkerEnd, j,
280 j);
281
282 DiffResult targetResult = new DiffResult(
283 j, targetStringList.subList(j, j + 1));
284
285 targetResults.add(targetResult);
286
287 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
288 }
289 }
290
291 if (aligned) {
292 break;
293 }
294 else {
295 _highlightLines(
296 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
297 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
308 i = i + 1;
309 j = j + 1;
310
311
313 for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
314 i++, j++) {
315
316 _lineDiff(
317 sourceResults, targetResults, sourceStringList,
318 targetStringList, addedMarkerStart, addedMarkerEnd,
319 deletedMarkerStart, deletedMarkerEnd, i, j, true);
320 }
321
322
325 for (; i <= difference.getDeletedEnd();i++) {
326 _highlightLines(
327 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
328
329 DiffResult sourceResult = new DiffResult(
330 i, sourceStringList.subList(i, i + 1));
331
332 sourceResults.add(sourceResult);
333
334 targetResults.add(new DiffResult(i, CONTEXT_LINE));
335 }
336
337 for (; j <= difference.getAddedEnd(); j++) {
338 _highlightLines(
339 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
340
341 DiffResult targetResult = new DiffResult(
342 j, targetStringList.subList(j, j + 1));
343
344 targetResults.add(targetResult);
345
346 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
347 }
348 }
349
350 private static int _checkOverlapping(
351 List<DiffResult> results, int startPos, int margin) {
352
353 if (results.size() == 0 || (startPos - margin) < 0) {
354 return margin;
355 }
356
357 DiffResult lastDiff = results.get(results.size() - 1);
358
359 if (lastDiff.getChangedLines().size() == 0) {
360 return margin;
361 }
362
363 int lastChangedLine = (lastDiff.getLineNumber() - 1) +
364 lastDiff.getChangedLines().size();
365
366 int currentChangedLine = startPos - margin;
367
368 if ((lastDiff.getChangedLines().size() == 1) &&
369 (lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE))) {
370
371 currentChangedLine = currentChangedLine + 1;
372 }
373
374 if (currentChangedLine < lastChangedLine) {
375 return margin + currentChangedLine - lastChangedLine;
376 }
377
378 return margin;
379 }
380
381 private static void _highlightChars(
382 List<String> stringList, String markerStart, String markerEnd,
383 int startPos, int endPos) {
384
385 String start = markerStart + stringList.get(startPos);
386
387 stringList.set(startPos, start);
388
389 String end = stringList.get(endPos) + markerEnd;
390
391 stringList.set(endPos, end);
392 }
393
394 private static void _highlightLines(
395 List<String> stringList, String markerStart, String markerEnd,
396 int startPos, int endPos) {
397
398 for (int i = startPos; i <= endPos; i++) {
399 stringList.set(i, markerStart + stringList.get(i) + markerEnd);
400 }
401 }
402
403 private static boolean _lineDiff(
404 List<DiffResult> sourceResults, List<DiffResult> targetResults,
405 List<String> sourceStringList, List<String> targetStringList,
406 String addedMarkerStart, String addedMarkerEnd,
407 String deletedMarkerStart, String deletedMarkerEnd,
408 int sourceChangedLine, int targetChangedLine, boolean aligned) {
409
410 String source = sourceStringList.get(sourceChangedLine);
411 String target = targetStringList.get(targetChangedLine);
412
413
415 List<String> sourceList = _toList(source);
416 List<String> targetList = _toList(target);
417
418 Diff diff = new Diff(sourceList, targetList);
419
420 List<Difference> differences = diff.diff();
421
422 Iterator<Difference> itr = differences.iterator();
423
424 int deletedChars = 0;
425 int addedChars = 0;
426
427
430 while (itr.hasNext() && !aligned) {
431 Difference difference = itr.next();
432
433 if (difference.getDeletedEnd() != Difference.NONE) {
434 deletedChars =
435 deletedChars +
436 (difference.getDeletedEnd() -
437 difference.getDeletedStart() + 1);
438 }
439
440 if (difference.getAddedEnd() != Difference.NONE) {
441 addedChars =
442 addedChars +
443 (difference.getAddedEnd() - difference.getAddedStart() + 1);
444 }
445 }
446
447
450 if ((deletedChars > (sourceList.size() / 2)) ||
451 (addedChars > sourceList.size() / 2)) {
452
453 return false;
454 }
455
456 itr = differences.iterator();
457
458 boolean sourceChanged = false;
459 boolean targetChanged = false;
460
461
463 while (itr.hasNext()) {
464 Difference difference = itr.next();
465
466 if (difference.getAddedEnd() == Difference.NONE) {
467
468
470 _highlightChars(
471 sourceList, deletedMarkerStart,
472 deletedMarkerEnd, difference.getDeletedStart(),
473 difference.getDeletedEnd());
474
475 sourceChanged = true;
476 }
477 else if (difference.getDeletedEnd() == Difference.NONE) {
478
479
481 _highlightChars(
482 targetList, addedMarkerStart, addedMarkerEnd,
483 difference.getAddedStart(), difference.getAddedEnd());
484
485 targetChanged = true;
486 }
487 else {
488
489
491 _highlightChars(
492 sourceList, deletedMarkerStart,
493 deletedMarkerEnd, difference.getDeletedStart(),
494 difference.getDeletedEnd());
495
496 sourceChanged = true;
497
498 _highlightChars(
499 targetList, addedMarkerStart, addedMarkerEnd,
500 difference.getAddedStart(), difference.getAddedEnd());
501
502 targetChanged = true;
503 }
504 }
505
506 if (sourceChanged) {
507 DiffResult sourceResult = new DiffResult(
508 sourceChangedLine, _toString(sourceList));
509
510 sourceResults.add(sourceResult);
511
512 if (!targetChanged) {
513 DiffResult targetResult = new DiffResult(
514 targetChangedLine, target);
515
516 targetResults.add(targetResult);
517 }
518 }
519
520 if (targetChanged) {
521 if (!sourceChanged) {
522 DiffResult sourceResult = new DiffResult(
523 sourceChangedLine, source);
524
525 sourceResults.add(sourceResult);
526 }
527
528 DiffResult targetResult = new DiffResult(
529 targetChangedLine, _toString(targetList));
530
531 targetResults.add(targetResult);
532 }
533
534 return true;
535 }
536
537 private static List<String> _toList(String line) {
538 String[] stringArray = line.split(StringPool.BLANK);
539
540 List<String> result = new ArrayList<String>();
541
542 for (int i = 1; i < stringArray.length; i++) {
543 result.add(stringArray[i]);
544 }
545
546 return result;
547 }
548
549 private static String _toString(List<String> line) {
550 if (line.isEmpty()) {
551 return StringPool.BLANK;
552 }
553
554 StringBundler sb = new StringBundler(line.size());
555
556 Iterator<String> itr = line.iterator();
557
558 while (itr.hasNext()) {
559 sb.append(itr.next());
560 }
561
562 return sb.toString();
563 }
564
565 }