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