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