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