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