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