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 CLOSE_DEL = "</del>";
046
047 public static final String CLOSE_INS = "</ins>";
048
049 public static final String CONTEXT_LINE = "#context#line#";
050
051 public static final String OPEN_DEL = "<del>";
052
053 public static final String OPEN_INS = "<ins>";
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, deletedMarkerEnd,
110 difference.getDeletedStart(), difference.getDeletedEnd());
111
112 margin = _calculateMargin(
113 sourceResults, targetResults, difference.getDeletedStart(),
114 difference.getAddedStart(), margin);
115
116 List<String> changedLines = _addMargins(
117 sourceResults, sourceStringList,
118 difference.getDeletedStart(), margin);
119
120 _addResults(
121 sourceResults, sourceStringList, changedLines,
122 difference.getDeletedStart(), difference.getDeletedEnd());
123
124 changedLines = _addMargins(
125 targetResults, targetStringList, difference.getAddedStart(),
126 margin);
127
128 int deletedLines =
129 difference.getDeletedEnd() + 1 -
130 difference.getDeletedStart();
131
132 for (int i = 0; i < deletedLines; i++) {
133 changedLines.add(CONTEXT_LINE);
134 }
135
136 DiffResult diffResult = new DiffResult(
137 difference.getDeletedStart(), changedLines);
138
139 targetResults.add(diffResult);
140 }
141 else if (difference.getDeletedEnd() == Difference.NONE) {
142
143
144
145 _highlightLines(
146 targetStringList, addedMarkerStart, addedMarkerEnd,
147 difference.getAddedStart(), difference.getAddedEnd());
148
149 margin = _calculateMargin(
150 sourceResults, targetResults, difference.getDeletedStart(),
151 difference.getAddedStart(), margin);
152
153 List<String> changedLines = _addMargins(
154 sourceResults, sourceStringList,
155 difference.getDeletedStart(), margin);
156
157 int addedLines =
158 difference.getAddedEnd() + 1 - difference.getAddedStart();
159
160 for (int i = 0; i < addedLines; i++) {
161 changedLines.add(CONTEXT_LINE);
162 }
163
164 DiffResult diffResult = new DiffResult(
165 difference.getAddedStart(), changedLines);
166
167 sourceResults.add(diffResult);
168
169 changedLines = _addMargins(
170 targetResults, targetStringList, difference.getAddedStart(),
171 margin);
172
173 _addResults(
174 targetResults, targetStringList, changedLines,
175 difference.getAddedStart(), difference.getAddedEnd());
176 }
177 else {
178
179
180
181
182 _checkCharDiffs(
183 sourceResults, targetResults, sourceStringList,
184 targetStringList, addedMarkerStart, addedMarkerEnd,
185 deletedMarkerStart, deletedMarkerEnd, difference, margin);
186 }
187 }
188
189 return results;
190 }
191
192 private static List<String> _addMargins(
193 List<DiffResult> results, List<String> stringList, int startPos,
194 int margin) {
195
196 List<String> changedLines = new ArrayList<String>();
197
198 if (margin == 0 || startPos == 0) {
199 return changedLines;
200 }
201
202 int i = startPos - margin;
203
204 for (; i < 0; i++) {
205 changedLines.add(CONTEXT_LINE);
206 }
207
208 for (; i < startPos; i++) {
209 if (i < stringList.size()) {
210 changedLines.add(stringList.get(i));
211 }
212 }
213
214 return changedLines;
215 }
216
217 private static void _addResults(
218 List<DiffResult> results, List<String> stringList,
219 List<String> changedLines, int start, int end) {
220
221 changedLines.addAll(stringList.subList(start, end + 1));
222
223 DiffResult diffResult = new DiffResult(start, changedLines);
224
225 results.add(diffResult);
226 }
227
228 private static int _calculateMargin(
229 List<DiffResult> sourceResults, List<DiffResult> targetResults,
230 int sourceBeginPos, int targetBeginPos, int margin) {
231
232 int sourceMargin = _checkOverlapping(
233 sourceResults, sourceBeginPos, margin);
234 int targetMargin = _checkOverlapping(
235 targetResults, targetBeginPos, margin);
236
237 if (sourceMargin < targetMargin) {
238 return sourceMargin;
239 }
240
241 return targetMargin;
242 }
243
244 private static void _checkCharDiffs(
245 List<DiffResult> sourceResults, List<DiffResult> targetResults,
246 List<String> sourceStringList, List<String> targetStringList,
247 String addedMarkerStart, String addedMarkerEnd,
248 String deletedMarkerStart, String deletedMarkerEnd,
249 Difference difference, int margin) {
250
251 boolean aligned = false;
252
253 int i = difference.getDeletedStart();
254 int j = difference.getAddedStart();
255
256
257
258
259
260
261 for (; i <= difference.getDeletedEnd(); i++) {
262 for (; j <= difference.getAddedEnd(); j++) {
263 if (_lineDiff(
264 sourceResults, targetResults, sourceStringList,
265 targetStringList, addedMarkerStart, addedMarkerEnd,
266 deletedMarkerStart, deletedMarkerEnd, i, j, false)) {
267
268 aligned = true;
269
270 break;
271 }
272 else {
273 _highlightLines(
274 targetStringList, addedMarkerStart, addedMarkerEnd, j,
275 j);
276
277 DiffResult targetResult = new DiffResult(
278 j, targetStringList.subList(j, j + 1));
279
280 targetResults.add(targetResult);
281
282 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
283 }
284 }
285
286 if (aligned) {
287 break;
288 }
289 else {
290 _highlightLines(
291 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i,
292 i);
293
294 DiffResult sourceResult = new DiffResult(
295 i, sourceStringList.subList(i, i + 1));
296
297 sourceResults.add(sourceResult);
298
299 targetResults.add(new DiffResult(i, CONTEXT_LINE));
300 }
301 }
302
303 i = i + 1;
304 j = j + 1;
305
306
307
308 for (; i <= difference.getDeletedEnd() && j <= difference.getAddedEnd();
309 i++, j++) {
310
311 _lineDiff(
312 sourceResults, targetResults, sourceStringList,
313 targetStringList, addedMarkerStart, addedMarkerEnd,
314 deletedMarkerStart, deletedMarkerEnd, i, j, true);
315 }
316
317
318
319
320 for (; i <= difference.getDeletedEnd();i++) {
321 _highlightLines(
322 sourceStringList, deletedMarkerStart, deletedMarkerEnd, i, i);
323
324 DiffResult sourceResult = new DiffResult(
325 i, sourceStringList.subList(i, i + 1));
326
327 sourceResults.add(sourceResult);
328
329 targetResults.add(new DiffResult(i, CONTEXT_LINE));
330 }
331
332 for (; j <= difference.getAddedEnd(); j++) {
333 _highlightLines(
334 targetStringList, addedMarkerStart, addedMarkerEnd, j, j);
335
336 DiffResult targetResult = new DiffResult(
337 j, targetStringList.subList(j, j + 1));
338
339 targetResults.add(targetResult);
340
341 sourceResults.add(new DiffResult(j, CONTEXT_LINE));
342 }
343 }
344
345 private static int _checkOverlapping(
346 List<DiffResult> results, int startPos, int margin) {
347
348 if (results.size() == 0 || (startPos - margin) < 0) {
349 return margin;
350 }
351
352 DiffResult lastDiff = results.get(results.size() - 1);
353
354 if (lastDiff.getChangedLines().size() == 0) {
355 return margin;
356 }
357
358 int lastChangedLine = (lastDiff.getLineNumber() - 1) +
359 lastDiff.getChangedLines().size();
360
361 int currentChangedLine = startPos - margin;
362
363 if ((lastDiff.getChangedLines().size() == 1) &&
364 (lastDiff.getChangedLines().get(0).equals(CONTEXT_LINE))) {
365
366 currentChangedLine = currentChangedLine + 1;
367 }
368
369 if (currentChangedLine < lastChangedLine) {
370 return margin + currentChangedLine - lastChangedLine;
371 }
372
373 return margin;
374 }
375
376 private static void _highlightChars(
377 List<String> stringList, String markerStart, String markerEnd,
378 int startPos, int endPos) {
379
380 String start = markerStart + stringList.get(startPos);
381
382 stringList.set(startPos, start);
383
384 String end = stringList.get(endPos) + markerEnd;
385
386 stringList.set(endPos, end);
387 }
388
389 private static void _highlightLines(
390 List<String> stringList, String markerStart, String markerEnd,
391 int startPos, int endPos) {
392
393 for (int i = startPos; i <= endPos; i++) {
394 stringList.set(i, markerStart + stringList.get(i) + markerEnd);
395 }
396 }
397
398 private static boolean _lineDiff(
399 List<DiffResult> sourceResults, List<DiffResult> targetResults,
400 List<String> sourceStringList, List<String> targetStringList,
401 String addedMarkerStart, String addedMarkerEnd,
402 String deletedMarkerStart, String deletedMarkerEnd,
403 int sourceChangedLine, int targetChangedLine, boolean aligned) {
404
405 String source = sourceStringList.get(sourceChangedLine);
406 String target = targetStringList.get(targetChangedLine);
407
408
409
410 List<String> sourceList = _toList(source);
411 List<String> targetList = _toList(target);
412
413 Diff diff = new Diff(sourceList, targetList);
414
415 List<Difference> differences = diff.diff();
416
417 Iterator<Difference> itr = differences.iterator();
418
419 int deletedChars = 0;
420 int addedChars = 0;
421
422
423
424
425 while (itr.hasNext() && !aligned) {
426 Difference difference = itr.next();
427
428 if (difference.getDeletedEnd() != Difference.NONE) {
429 deletedChars =
430 deletedChars +
431 (difference.getDeletedEnd() -
432 difference.getDeletedStart() + 1);
433 }
434
435 if (difference.getAddedEnd() != Difference.NONE) {
436 addedChars =
437 addedChars +
438 (difference.getAddedEnd() - difference.getAddedStart() + 1);
439 }
440 }
441
442
443
444
445 if ((deletedChars > (sourceList.size() / 2)) ||
446 (addedChars > sourceList.size() / 2)) {
447
448 return false;
449 }
450
451 itr = differences.iterator();
452
453 boolean sourceChanged = false;
454 boolean targetChanged = false;
455
456
457
458 while (itr.hasNext()) {
459 Difference difference = itr.next();
460
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[] stringArray = line.split(StringPool.BLANK);
532
533 List<String> result = new ArrayList<String>();
534
535 for (int i = 1; i < stringArray.length; i++) {
536 result.add(stringArray[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 Iterator<String> itr = line.iterator();
550
551 while (itr.hasNext()) {
552 sb.append(itr.next());
553 }
554
555 return sb.toString();
556 }
557
558 }