1
22
23 package com.liferay.portal.util;
24
25 import com.liferay.portal.kernel.util.DiffResult;
26 import com.liferay.portal.kernel.util.FileUtil;
27 import com.liferay.portal.kernel.util.StringPool;
28
29 import java.io.Reader;
30
31 import java.util.ArrayList;
32 import java.util.Iterator;
33 import java.util.List;
34
35 import org.incava.util.diff.Diff;
36 import org.incava.util.diff.Difference;
37
38
52 public class DiffImpl implements com.liferay.portal.kernel.util.Diff {
53
54
61 public List<DiffResult>[] diff(Reader source, Reader target) {
62 int margin = 2;
63
64 return diff(
65 source, target, OPEN_INS, CLOSE_INS, OPEN_DEL, CLOSE_DEL, margin);
66 }
67
68
77 public List<DiffResult>[] diff(
78 Reader source, Reader target, String addedMarkerStart,
79 String addedMarkerEnd, String deletedMarkerStart,
80 String deletedMarkerEnd, int margin) {
81
82 List<DiffResult> sourceResults = new ArrayList<DiffResult>();
83 List<DiffResult> targetResults = new ArrayList<DiffResult>();
84
85 List<DiffResult>[] results = new List[] {sourceResults, targetResults};
86
87
89 List<String> sourceStringList = FileUtil.toList(source);
90 List<String> targetStringList = FileUtil.toList(target);
91
92
94 Diff diff = new Diff(sourceStringList, targetStringList);
95
96 List<Difference> differences = diff.diff();
97
98 Iterator<Difference> itr = differences.iterator();
99
100 while (itr.hasNext()) {
101 Difference difference = itr.next();
102
103 if (difference.getAddedEnd() == Difference.NONE) {
104
105
107 _highlightLines(
108 sourceStringList, deletedMarkerStart,
109 deletedMarkerEnd, difference.getDeletedStart(),
110 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
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
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(
224 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
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
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
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
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
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
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
459 while (itr.hasNext()) {
460 Difference difference = itr.next();
461
462 if (difference.getAddedEnd() == Difference.NONE) {
463
464
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
477 _highlightChars(
478 targetList, addedMarkerStart, addedMarkerEnd,
479 difference.getAddedStart(), difference.getAddedEnd());
480
481 targetChanged = true;
482 }
483 else {
484
485
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 StringBuilder sb = new StringBuilder();
547
548 Iterator<String> itr = line.iterator();
549
550 while (itr.hasNext()) {
551 sb.append(itr.next());
552 }
553
554 return sb.toString();
555 }
556
557 }