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(start, changedLines);
225
226 results.add(diffResult);
227 }
228
229 private static int _calculateMargin(
230 List<DiffResult> sourceResults, List<DiffResult> targetResults,
231 int sourceBeginPos, int targetBeginPos, int margin) {
232
233 int sourceMargin = _checkOverlapping(
234 sourceResults, sourceBeginPos, margin);
235 int targetMargin = _checkOverlapping(
236 targetResults, targetBeginPos, margin);
237
238 if (sourceMargin < targetMargin) {
239 return sourceMargin;
240 }
241
242 return targetMargin;
243 }
244
245 private static void _checkCharDiffs(
246 List<DiffResult> sourceResults, List<DiffResult> targetResults,
247 List<String> sourceStringList, List<String> targetStringList,
248 String addedMarkerStart, String addedMarkerEnd,
249 String deletedMarkerStart, String deletedMarkerEnd,
250 Difference difference, int margin) {
251
252 boolean aligned = false;
253
254 int i = difference.getDeletedStart();
255 int j = difference.getAddedStart();
256
257
258
259
260
261
262 for (; i <= difference.getDeletedEnd(); i++) {
263 for (; j <= difference.getAddedEnd(); j++) {
264 if (_lineDiff(
265 sourceResults, targetResults, sourceStringList,
266 targetStringList, addedMarkerStart, addedMarkerEnd,
267 deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
268
269 aligned = true;
270
271 break;
272 }
273 else {
274 _highlightLines(
275 targetStringList, addedMarkerStart, addedMarkerEnd, j,
276 j);
277
278 DiffResult targetResult = new DiffResult(
279 j, targetStringList.subList(j, j + 1));
280
281 targetResults.add(targetResult);
282
283 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
284 }
285 }
286
287 if (aligned) {
288 break;
289 }
290 else {
291 _highlightLines(
292 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
293 i);
294
295 DiffResult sourceResult = new DiffResult(
296 i, sourceStringList.subList(i, i + 1));
297
298 sourceResults.add(sourceResult);
299
300 targetResults.add(new DiffResult(i, CONTEXT_LINE));
301 }
302 }
303
304 i = i + 1;
305 j = j + 1;
306
307
308
309 for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
310 i++, j++) {
311
312 _lineDiff(
313 sourceResults, targetResults, sourceStringList,
314 targetStringList, addedMarkerStart, addedMarkerEnd,
315 deletedMarkerStart, deletedMarkerEnd, i, j, true);
316 }
317
318
319
320
321 for (; i <= difference.getDeletedEnd();i++) {
322 _highlightLines(
323 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
324
325 DiffResult sourceResult = new DiffResult(
326 i, sourceStringList.subList(i, i + 1));
327
328 sourceResults.add(sourceResult);
329
330 targetResults.add(new DiffResult(i, CONTEXT_LINE));
331 }
332
333 for (; j <= difference.getAddedEnd(); j++) {
334 _highlightLines(
335 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
336
337 DiffResult targetResult = new DiffResult(
338 j, targetStringList.subList(j, j + 1));
339
340 targetResults.add(targetResult);
341
342 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
343 }
344 }
345
346 private static int _checkOverlapping(
347 List<DiffResult> results, int startPos, int margin) {
348
349 if (results.size() == 0 || (startPos - margin) < 0) {
350 return margin;
351 }
352
353 DiffResult lastDiff = results.get(results.size() - 1);
354
355 if (lastDiff.getChangedLines().size() == 0) {
356 return margin;
357 }
358
359 int lastChangedLine = (lastDiff.getLineNumber() - 1) +
360 lastDiff.getChangedLines().size();
361
362 int currentChangedLine = startPos - margin;
363
364 if ((lastDiff.getChangedLines().size() == 1) &&
365 (lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE))) {
366
367 currentChangedLine = currentChangedLine + 1;
368 }
369
370 if (currentChangedLine < lastChangedLine) {
371 return margin + currentChangedLine - lastChangedLine;
372 }
373
374 return margin;
375 }
376
377 private static void _highlightChars(
378 List<String> stringList, String markerStart, String markerEnd,
379 int startPos, int endPos) {
380
381 String start = markerStart + stringList.get(startPos);
382
383 stringList.set(startPos, start);
384
385 String end = stringList.get(endPos) + markerEnd;
386
387 stringList.set(endPos, end);
388 }
389
390 private static void _highlightLines(
391 List<String> stringList, String markerStart, String markerEnd,
392 int startPos, int endPos) {
393
394 for (int i = startPos; i <= endPos; i++) {
395 stringList.set(i, markerStart + stringList.get(i) + markerEnd);
396 }
397 }
398
399 private static boolean _lineDiff(
400 List<DiffResult> sourceResults, List<DiffResult> targetResults,
401 List<String> sourceStringList, List<String> targetStringList,
402 String addedMarkerStart, String addedMarkerEnd,
403 String deletedMarkerStart, String deletedMarkerEnd,
404 int sourceChangedLine, int targetChangedLine, boolean aligned) {
405
406 String source = sourceStringList.get(sourceChangedLine);
407 String target = targetStringList.get(targetChangedLine);
408
409
410
411 List<String> sourceList = _toList(source);
412 List<String> targetList = _toList(target);
413
414 Diff diff = new Diff(sourceList, targetList);
415
416 List<Difference> differences = diff.diff();
417
418 Iterator<Difference> itr = differences.iterator();
419
420 int deletedChars = 0;
421 int addedChars = 0;
422
423
424
425
426 while (itr.hasNext() && !aligned) {
427 Difference difference = itr.next();
428
429 if (difference.getDeletedEnd() != Difference.NONE) {
430 deletedChars =
431 deletedChars +
432 (difference.getDeletedEnd() -
433 difference.getDeletedStart() + 1);
434 }
435
436 if (difference.getAddedEnd() != Difference.NONE) {
437 addedChars =
438 addedChars +
439 (difference.getAddedEnd() - difference.getAddedStart() + 1);
440 }
441 }
442
443
444
445
446 if ((deletedChars > (sourceList.size() / 2)) ||
447 (addedChars > sourceList.size() / 2)) {
448
449 return false;
450 }
451
452 itr = differences.iterator();
453
454 boolean sourceChanged = false;
455 boolean targetChanged = false;
456
457
458
459 while (itr.hasNext()) {
460 Difference difference = itr.next();
461
462 if (difference.getAddedEnd() == Difference.NONE) {
463
464
465
466 _highlightChars(
467 sourceList, deletedMarkerStart,
468 deletedMarkerEnd, difference.getDeletedStart(),
469 difference.getDeletedEnd());
470
471 sourceChanged = true;
472 }
473 else if (difference.getDeletedEnd() == Difference.NONE) {
474
475
476
477 _highlightChars(
478 targetList, addedMarkerStart, addedMarkerEnd,
479 difference.getAddedStart(), difference.getAddedEnd());
480
481 targetChanged = true;
482 }
483 else {
484
485
486
487 _highlightChars(
488 sourceList, deletedMarkerStart,
489 deletedMarkerEnd, difference.getDeletedStart(),
490 difference.getDeletedEnd());
491
492 sourceChanged = true;
493
494 _highlightChars(
495 targetList, addedMarkerStart, addedMarkerEnd,
496 difference.getAddedStart(), difference.getAddedEnd());
497
498 targetChanged = true;
499 }
500 }
501
502 if (sourceChanged) {
503 DiffResult sourceResult = new DiffResult(
504 sourceChangedLine, _toString(sourceList));
505
506 sourceResults.add(sourceResult);
507
508 if (!targetChanged) {
509 DiffResult targetResult = new DiffResult(
510 targetChangedLine, target);
511
512 targetResults.add(targetResult);
513 }
514 }
515
516 if (targetChanged) {
517 if (!sourceChanged) {
518 DiffResult sourceResult = new DiffResult(
519 sourceChangedLine, source);
520
521 sourceResults.add(sourceResult);
522 }
523
524 DiffResult targetResult = new DiffResult(
525 targetChangedLine, _toString(targetList));
526
527 targetResults.add(targetResult);
528 }
529
530 return true;
531 }
532
533 private static List<String> _toList(String line) {
534 String[] stringArray = line.split(StringPool.BLANK);
535
536 List<String> result = new ArrayList<String>();
537
538 for (int i = 1; i < stringArray.length; i++) {
539 result.add(stringArray[i]);
540 }
541
542 return result;
543 }
544
545 private static String _toString(List<String> line) {
546 if (line.isEmpty()) {
547 return StringPool.BLANK;
548 }
549
550 StringBundler sb = new StringBundler(line.size());
551
552 Iterator<String> itr = line.iterator();
553
554 while (itr.hasNext()) {
555 sb.append(itr.next());
556 }
557
558 return sb.toString();
559 }
560
561 }