001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.tools; 003 004//// Taken from http://www.bmsi.com/java/#diff 005 006// http://www.bmsi.com/java/DiffPrint.java could also be useful 007 008/* 009 * $Log: Diff.java,v $ 010 * Revision 1.15 2013/04/01 16:27:31 stuart 011 * Fix DiffPrint unified format with test cases. 012 * Begin porting some diff-2.7 features. 013 * 014 * Revision 1.14 2010/03/03 21:21:25 stuart 015 * Test new direct equivalence API 016 * 017 * Revision 1.13 2009/12/07 17:43:17 stuart 018 * Compute equivMax for int[] ctor 019 * 020 * Revision 1.12 2009/12/07 17:34:46 stuart 021 * Ctor with int[]. 022 * 023 * Revision 1.11 2009/11/15 01:11:54 stuart 024 * Diff doesn't need to be generic 025 * 026 * Revision 1.10 2009/11/15 00:54:03 stuart 027 * Update to Java 5 containers 028 * 029 * Revision 1.7 2009/01/19 03:05:26 stuart 030 * Fix StackOverflow bug with heuristic on reported by Jimmy Han. 031 * 032 * Revision 1.6 2003/03/06 22:51:32 stuart 033 * Convert to CVS 034 * 035 * Revision 1.5 2002/07/19 19:14:40 stuart 036 * fix reverseScript, make change ctor public, update docs 037 * 038 * Revision 1.4 2002/04/09 17:53:39 stuart 039 * More flexible interface for diff() function. 040 * 041 * Revision 1.3 2000/03/03 21:58:03 stuart 042 * move discard_confusing_lines and shift_boundaries to class file_data 043 * 044 * Revision 1.2 2000/03/02 16:37:38 stuart 045 * Add GPL and copyright 046 * 047 */ 048 049import java.util.HashMap; 050import java.util.Map; 051 052/** A class to compare vectors of objects. The result of comparison 053 is a list of <code>change</code> objects which form an 054 edit script. The objects compared are traditionally lines 055 of text from two files. Comparison options such as "ignore 056 whitespace" are implemented by modifying the <code>equals</code> 057 and <code>hashcode</code> methods for the objects compared. 058<p> 059 The basic algorithm is described in: <br> 060 "An O(ND) Difference Algorithm and its Variations", Eugene Myers, 061 Algorithmica Vol. 1 No. 2, 1986, p 251. 062<p> 063 This class outputs different results from GNU diff 1.15 on some 064 inputs. Our results are actually better (smaller change list, smaller 065 total size of changes), but it would be nice to know why. Perhaps 066 there is a memory overwrite bug in GNU diff 1.15. 067 068 @author Stuart D. Gathman, translated from GNU diff 1.15 069 Copyright (C) 2000 Business Management Systems, Inc. 070<p> 071 This program is free software; you can redistribute it and/or modify 072 it under the terms of the GNU General Public License as published by 073 the Free Software Foundation; either version 1, or (at your option) 074 any later version. 075<p> 076 This program is distributed in the hope that it will be useful, 077 but WITHOUT ANY WARRANTY; without even the implied warranty of 078 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 079 GNU General Public License for more details. 080<p> 081 You should have received a copy of the <a href=COPYING.txt> 082 GNU General Public License</a> 083 along with this program; if not, write to the Free Software 084 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 085 */ 086public class Diff { 087 088 /** Prepare to find differences between two arrays. Each element of 089 the arrays is translated to an "equivalence number" based on 090 the result of <code>equals</code>. The original Object arrays 091 are no longer needed for computing the differences. They will 092 be needed again later to print the results of the comparison as 093 an edit script, if desired. 094 * @param a first array 095 * @param b second array 096 */ 097 public Diff(Object[] a, Object[] b) { 098 Map<Object, Integer> h = new HashMap<>(a.length + b.length); 099 filevec = new FileData[] {new FileData(a, h), new FileData(b, h)}; 100 } 101 102 /** 1 more than the maximum equivalence value used for this or its 103 sibling file. */ 104 private int equivMax = 1; 105 106 /* Vectors being compared. */ 107 private int[] xvec; 108 private int[] yvec; 109 private int[] fdiag; /* Vector, indexed by diagonal, containing 110 the X coordinate of the point furthest 111 along the given diagonal in the forward 112 search of the edit matrix. */ 113 private int[] bdiag; /* Vector, indexed by diagonal, containing 114 the X coordinate of the point furthest 115 along the given diagonal in the backward 116 search of the edit matrix. */ 117 private int fdiagoff; 118 private int bdiagoff; 119 private final FileData[] filevec; 120 private int cost; 121 122 /** 123 * Find the midpoint of the shortest edit script for a specified 124 * portion of the two files. 125 * <p> 126 * We scan from the beginnings of the files, and simultaneously from the ends, 127 * doing a breadth-first search through the space of edit-sequence. 128 * When the two searches meet, we have found the midpoint of the shortest 129 * edit sequence. 130 * <p> 131 * The value returned is the number of the diagonal on which the midpoint lies. 132 * The diagonal number equals the number of inserted lines minus the number 133 * of deleted lines (counting only lines before the midpoint). 134 * The edit cost is stored into COST; this is the total number of 135 * lines inserted or deleted (counting only lines before the midpoint). 136 * <p> 137 * This function assumes that the first lines of the specified portions 138 * of the two files do not match, and likewise that the last lines do not 139 * match. The caller must trim matching lines from the beginning and end 140 * of the portions it is going to specify. 141 * <p> 142 * Note that if we return the "wrong" diagonal value, or if 143 * the value of bdiag at that diagonal is "wrong", 144 * the worst this can do is cause suboptimal diff output. 145 * It cannot cause incorrect diff output. 146 * @param xoff xoff 147 * @param xlim xlim 148 * @param yoff yoff 149 * @param ylim ylim 150 * @return midpoint of the shortest edit script 151 */ 152 private int diag(int xoff, int xlim, int yoff, int ylim) { 153 final int[] fd = fdiag; // Give the compiler a chance. 154 final int[] bd = bdiag; // Additional help for the compiler. 155 final int[] xv = xvec; // Still more help for the compiler. 156 final int[] yv = yvec; // And more and more . . . 157 final int dmin = xoff - ylim; // Minimum valid diagonal. 158 final int dmax = xlim - yoff; // Maximum valid diagonal. 159 final int fmid = xoff - yoff; // Center diagonal of top-down search. 160 final int bmid = xlim - ylim; // Center diagonal of bottom-up search. 161 // Limits of top-down search. 162 int fmin = fmid; 163 int fmax = fmid; 164 // Limits of bottom-up search. 165 int bmin = bmid; 166 int bmax = bmid; 167 // True if southeast corner is on an odd diagonal with respect to the northwest. 168 final boolean odd = (fmid - bmid & 1) != 0; 169 170 fd[fdiagoff + fmid] = xoff; 171 bd[bdiagoff + bmid] = xlim; 172 173 for (int c = 1;; ++c) { 174 int d; /* Active diagonal. */ 175 176 /* Extend the top-down search by an edit step in each diagonal. */ 177 if (fmin > dmin) { 178 fd[fdiagoff + --fmin - 1] = -1; 179 } else { 180 ++fmin; 181 } 182 if (fmax < dmax) { 183 fd[fdiagoff + ++fmax + 1] = -1; 184 } else { 185 --fmax; 186 } 187 for (d = fmax; d >= fmin; d -= 2) { 188 int x; 189 int y; 190 int tlo = fd[fdiagoff + d - 1]; 191 int thi = fd[fdiagoff + d + 1]; 192 193 if (tlo >= thi) { 194 x = tlo + 1; 195 } else { 196 x = thi; 197 } 198 y = x - d; 199 while (x < xlim && y < ylim && xv[x] == yv[y]) { 200 ++x; ++y; 201 } 202 fd[fdiagoff + d] = x; 203 if (odd && bmin <= d && d <= bmax && bd[bdiagoff + d] <= fd[fdiagoff + d]) { 204 cost = 2 * c - 1; 205 return d; 206 } 207 } 208 209 /* Similar extend the bottom-up search. */ 210 if (bmin > dmin) { 211 bd[bdiagoff + --bmin - 1] = Integer.MAX_VALUE; 212 } else { 213 ++bmin; 214 } 215 if (bmax < dmax) { 216 bd[bdiagoff + ++bmax + 1] = Integer.MAX_VALUE; 217 } else { 218 --bmax; 219 } 220 for (d = bmax; d >= bmin; d -= 2) { 221 int x; 222 int y; 223 final int tlo = bd[bdiagoff + d - 1]; 224 final int thi = bd[bdiagoff + d + 1]; 225 226 if (tlo < thi) { 227 x = tlo; 228 } else { 229 x = thi - 1; 230 } 231 y = x - d; 232 while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1]) { 233 --x; --y; 234 } 235 bd[bdiagoff + d] = x; 236 if (!odd && fmin <= d && d <= fmax && bd[bdiagoff + d] <= fd[fdiagoff + d]) { 237 cost = 2 * c; 238 return d; 239 } 240 } 241 } 242 } 243 244 /** 245 * Compare in detail contiguous subsequences of the two files 246 * which are known, as a whole, to match each other. 247 * <p> 248 * The results are recorded in the vectors filevec[N].changed_flag, by 249 * storing a 1 in the element for each line that is an insertion or deletion. 250 * <p> 251 * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. 252 * <p> 253 * Note that XLIM, YLIM are exclusive bounds. 254 * All line numbers are origin-0 and discarded lines are not counted. 255 * @param xoff xoff 256 * @param xlim xlim 257 * @param yoff yoff 258 * @param ylim ylim 259 */ 260 private void compareseq(int xoff, int xlim, int yoff, int ylim) { 261 /* Slide down the bottom initial diagonal. */ 262 while (xoff < xlim && yoff < ylim && xvec[xoff] == yvec[yoff]) { 263 ++xoff; ++yoff; 264 } 265 /* Slide up the top initial diagonal. */ 266 while (xlim > xoff && ylim > yoff && xvec[xlim - 1] == yvec[ylim - 1]) { 267 --xlim; --ylim; 268 } 269 270 /* Handle simple cases. */ 271 if (xoff == xlim) { 272 while (yoff < ylim) { 273 filevec[1].changedFlag[1+filevec[1].realindexes[yoff++]] = true; 274 } 275 } else if (yoff == ylim) { 276 while (xoff < xlim) { 277 filevec[0].changedFlag[1+filevec[0].realindexes[xoff++]] = true; 278 } 279 } else { 280 /* Find a point of correspondence in the middle of the files. */ 281 282 int d = diag(xoff, xlim, yoff, ylim); 283 int c = cost; 284 int b = bdiag[bdiagoff + d]; 285 286 if (c == 1) 287 /* This should be impossible, because it implies that 288 one of the two subsequences is empty, 289 and that case was handled above without calling `diag'. 290 Let's verify that this is true. */ 291 throw new IllegalArgumentException("Empty subsequence"); 292 else { 293 /* Use that point to split this problem into two subproblems. */ 294 compareseq(xoff, b, yoff, b - d); 295 /* This used to use f instead of b, 296 but that is incorrect! 297 It is not necessarily the case that diagonal d 298 has a snake from b to f. */ 299 compareseq(b, xlim, b - d, ylim); 300 } 301 } 302 } 303 304 /** Discard lines from one file that have no matches in the other file. 305 */ 306 private void discardConfusingLines() { 307 filevec[0].discardConfusingLines(filevec[1]); 308 filevec[1].discardConfusingLines(filevec[0]); 309 } 310 311 /** 312 * Adjust inserts/deletes of blank lines to join changes as much as possible. 313 */ 314 private void shiftBoundaries() { 315 filevec[0].shiftBoundaries(filevec[1]); 316 filevec[1].shiftBoundaries(filevec[0]); 317 } 318 319 /** 320 * Script builder. 321 * @since 10600 (functional interface) 322 */ 323 @FunctionalInterface 324 public interface ScriptBuilder { 325 /** 326 * Scan the tables of which lines are inserted and deleted, producing an edit script. 327 * @param changed0 true for lines in first file which do not match 2nd 328 * @param len0 number of lines in first file 329 * @param changed1 true for lines in 2nd file which do not match 1st 330 * @param len1 number of lines in 2nd file 331 * @return a linked list of changes - or null 332 * @since 10600 (renamed) 333 */ 334 Change buildScript( 335 boolean[] changed0, int len0, 336 boolean[] changed1, int len1 337 ); 338 } 339 340 /** 341 * Scan the tables of which lines are inserted and deleted, producing an edit script in reverse order. 342 */ 343 static class ReverseScript implements ScriptBuilder { 344 @Override 345 public Change buildScript( 346 final boolean[] changed0, int len0, 347 final boolean[] changed1, int len1) { 348 Change script = null; 349 int i0 = 0, i1 = 0; 350 while (i0 < len0 || i1 < len1) { 351 if (changed0[1+i0] || changed1[1+i1]) { 352 int line0 = i0; 353 int line1 = i1; 354 355 /* Find # lines changed here in each file. */ 356 while (changed0[1+i0]) { 357 ++i0; 358 } 359 while (changed1[1+i1]) { 360 ++i1; 361 } 362 363 /* Record this change. */ 364 script = new Change(line0, line1, i0 - line0, i1 - line1, script); 365 } 366 367 /* We have reached lines in the two files that match each other. */ 368 i0++; i1++; 369 } 370 371 return script; 372 } 373 } 374 375 static class ForwardScript implements ScriptBuilder { 376 /** Scan the tables of which lines are inserted and deleted, 377 producing an edit script in forward order. */ 378 @Override 379 public Change buildScript( 380 final boolean[] changed0, int len0, 381 final boolean[] changed1, int len1) { 382 Change script = null; 383 int i0 = len0, i1 = len1; 384 385 while (i0 >= 0 || i1 >= 0) { 386 if (changed0[i0] || changed1[i1]) { 387 int line0 = i0; 388 int line1 = i1; 389 390 /* Find # lines changed here in each file. */ 391 while (changed0[i0]) { 392 --i0; 393 } 394 while (changed1[i1]) { 395 --i1; 396 } 397 398 /* Record this change. */ 399 script = new Change(i0, i1, line0 - i0, line1 - i1, script); 400 } 401 402 /* We have reached lines in the two files that match each other. */ 403 i0--; i1--; 404 } 405 406 return script; 407 } 408 } 409 410 /** Standard Forward ScriptBuilder. */ 411 public static final ScriptBuilder forwardScript = new ForwardScript(); 412 /** Standard Reverse ScriptBuilder. */ 413 public static final ScriptBuilder reverseScript = new ReverseScript(); 414 415 /** 416 * Report the differences of two files. DEPTH is the current directory depth. 417 * @param reverse if {@code true} use {@link #reverseScript} else use {@link #forwardScript} 418 * @return the differences of two files 419 */ 420 public final Change diff2(final boolean reverse) { 421 return diff(reverse ? reverseScript : forwardScript); 422 } 423 424 /** 425 * Get the results of comparison as an edit script. The script 426 * is described by a list of changes. The standard ScriptBuilder 427 * implementations provide for forward and reverse edit scripts. 428 * Alternate implementations could, for instance, list common elements 429 * instead of differences. 430 * @param bld an object to build the script from change flags 431 * @return the head of a list of changes 432 */ 433 public Change diff(final ScriptBuilder bld) { 434 435 // Some lines are obviously insertions or deletions because they don't match anything. 436 // Detect them now, and avoid even thinking about them in the main comparison algorithm. 437 discardConfusingLines(); 438 439 // Now do the main comparison algorithm, considering just the undiscarded lines. 440 xvec = filevec[0].undiscarded; 441 yvec = filevec[1].undiscarded; 442 443 int diags = filevec[0].nondiscardedLines + filevec[1].nondiscardedLines + 3; 444 fdiag = new int[diags]; 445 fdiagoff = filevec[1].nondiscardedLines + 1; 446 bdiag = new int[diags]; 447 bdiagoff = filevec[1].nondiscardedLines + 1; 448 449 compareseq(0, filevec[0].nondiscardedLines, 450 0, filevec[1].nondiscardedLines); 451 fdiag = null; 452 bdiag = null; 453 454 // Modify the results slightly to make them prettier in cases where that can validly be done. 455 shiftBoundaries(); 456 457 // Get the results of comparison in the form of a chain of `struct change's -- an edit script. 458 return bld.buildScript( 459 filevec[0].changedFlag, 460 filevec[0].bufferedLines, 461 filevec[1].changedFlag, 462 filevec[1].bufferedLines 463 ); 464 } 465 466 /** The result of comparison is an "edit script": a chain of change objects. 467 Each change represents one place where some lines are deleted 468 and some are inserted. 469 470 LINE0 and LINE1 are the first affected lines in the two files (origin 0). 471 DELETED is the number of lines deleted here from file 0. 472 INSERTED is the number of lines inserted here in file 1. 473 474 If DELETED is 0 then LINE0 is the number of the line before 475 which the insertion was done; vice versa for INSERTED and LINE1. */ 476 477 public static class Change { 478 /** Previous or next edit command. */ 479 public Change link; 480 /** # lines of file 1 changed here. */ 481 public final int inserted; 482 /** # lines of file 0 changed here. */ 483 public final int deleted; 484 /** Line number of 1st deleted line. */ 485 public final int line0; 486 /** Line number of 1st inserted line. */ 487 public final int line1; 488 489 /** 490 * Cons an additional entry onto the front of an edit script OLD. 491 * LINE0 and LINE1 are the first affected lines in the two files (origin 0). 492 * DELETED is the number of lines deleted here from file 0. 493 * INSERTED is the number of lines inserted here in file 1. 494 * <p> 495 * If DELETED is 0 then LINE0 is the number of the line before 496 * which the insertion was done; vice versa for INSERTED and LINE1. 497 * @param line0 first affected lines in the two files (origin 0) 498 * @param line1 first affected lines in the two files (origin 0) 499 * @param deleted the number of lines deleted here from file 0 500 * @param inserted the number of lines inserted here in file 1 501 * @param old edit script 502 */ 503 public Change(int line0, int line1, int deleted, int inserted, Change old) { 504 this.line0 = line0; 505 this.line1 = line1; 506 this.inserted = inserted; 507 this.deleted = deleted; 508 this.link = old; 509 } 510 511 /** 512 * Returns the number of insertions and deletions of this change as well as 513 * (recursively) the changes linked via {@link #link}. 514 * @return recursive number of insertions and deletions 515 */ 516 public int getTotalNumberOfChanges() { 517 return inserted + deleted + (link != null ? link.getTotalNumberOfChanges() : 0); 518 } 519 520 @Override 521 public String toString() { 522 String s = String.format("%d -%d +%d %d", line0, deleted, inserted, line1); 523 return (link != null) ? s + '\n' + link : s; 524 } 525 } 526 527 /** 528 * Data on one input file being compared. 529 */ 530 class FileData { 531 532 /** Allocate changed array for the results of comparison. */ 533 void clear() { 534 // Allocate a flag for each line of each file, saying whether that line is an insertion or deletion. 535 // Allocate an extra element, always zero, at each end of each vector. 536 changedFlag = new boolean[bufferedLines + 2]; 537 } 538 539 /** 540 * Return equiv_count[I] as the number of lines in this file that fall in equivalence class I. 541 * @return the array of equivalence class counts. 542 */ 543 int[] equivCount() { 544 int[] equivCount = new int[equivMax]; 545 for (int i = 0; i < bufferedLines; ++i) { 546 ++equivCount[equivs[i]]; 547 } 548 return equivCount; 549 } 550 551 /** 552 * Discard lines that have no matches in another file. 553 * <p> 554 * A line which is discarded will not be considered by the actual comparison algorithm; 555 * it will be as if that line were not in the file. 556 * The file's `realindexes' table maps virtual line numbers 557 * (which don't count the discarded lines) into real line numbers; 558 * this is how the actual comparison algorithm produces results 559 * that are comprehensible when the discarded lines are counted. 560 * <p> 561 * When we discard a line, we also mark it as a deletion or insertion so that it will be printed in the output. 562 * @param f the other file 563 */ 564 void discardConfusingLines(FileData f) { 565 clear(); 566 // Set up table of which lines are going to be discarded. 567 final byte[] discarded = discardable(f.equivCount()); 568 569 // Don't really discard the provisional lines except when they occur in a run of discardables, 570 // with nonprovisionals at the beginning and end. 571 filterDiscards(discarded); 572 573 // Actually discard the lines. 574 discard(discarded); 575 } 576 577 /** 578 * Mark to be discarded each line that matches no line of another file. 579 * If a line matches many lines, mark it as provisionally discardable. 580 * @param counts The count of each equivalence number for the other file. 581 * @return 0=nondiscardable, 1=discardable or 2=provisionally discardable for each line 582 * @see #equivCount() 583 */ 584 private byte[] discardable(final int... counts) { 585 final int end = bufferedLines; 586 final byte[] discards = new byte[end]; 587 final int[] equivs = this.equivs; 588 int many = 5; 589 int tem = end / 64; 590 591 /* Multiply MANY by approximate square root of number of lines. 592 That is the threshold for provisionally discardable lines. */ 593 while ((tem = tem >> 2) > 0) { 594 many *= 2; 595 } 596 597 for (int i = 0; i < end; i++) { 598 int nmatch; 599 if (equivs[i] == 0) { 600 continue; 601 } 602 nmatch = counts[equivs[i]]; 603 if (nmatch == 0) { 604 discards[i] = 1; 605 } else if (nmatch > many) { 606 discards[i] = 2; 607 } 608 } 609 return discards; 610 } 611 612 /** 613 * Don't really discard the provisional lines except when they occur 614 * in a run of discardables, with nonprovisionals at the beginning and end. 615 * @param discards discards 616 */ 617 private void filterDiscards(final byte[] discards) { 618 final int end = bufferedLines; 619 620 for (int i = 0; i < end; i++) { 621 /* Cancel provisional discards not in middle of run of discards. */ 622 if (discards[i] == 2) { 623 discards[i] = 0; 624 } else if (discards[i] != 0) { 625 /* We have found a nonprovisional discard. */ 626 int j; 627 int length; 628 int provisional = 0; 629 630 /* Find end of this run of discardable lines. 631 Count how many are provisionally discardable. */ 632 for (j = i; j < end; j++) { 633 if (discards[j] == 0) { 634 break; 635 } 636 if (discards[j] == 2) { 637 ++provisional; 638 } 639 } 640 641 /* Cancel provisional discards at end, and shrink the run. */ 642 while (j > i && discards[j - 1] == 2) { 643 discards[--j] = 0; --provisional; 644 } 645 646 /* Now we have the length of a run of discardable lines 647 whose first and last are not provisional. */ 648 length = j - i; 649 650 /* If 1/4 of the lines in the run are provisional, 651 cancel discarding of all provisional lines in the run. */ 652 if (provisional * 4 > length) { 653 while (j > i) 654 if (discards[--j] == 2) { 655 discards[j] = 0; 656 } 657 } else { 658 int consec; 659 int minimum = 1; 660 int tem = length / 4; 661 662 /* MINIMUM is approximate square root of LENGTH/4. 663 A subrun of two or more provisionals can stand 664 when LENGTH is at least 16. 665 A subrun of 4 or more can stand when LENGTH >= 64. */ 666 while ((tem = tem >> 2) > 0) { 667 minimum *= 2; 668 } 669 minimum++; 670 671 /* Cancel any subrun of MINIMUM or more provisionals 672 within the larger run. */ 673 for (j = 0, consec = 0; j < length; j++) { 674 if (discards[i + j] != 2) { 675 consec = 0; 676 } else if (minimum == ++consec) { 677 /* Back up to start of subrun, to cancel it all. */ 678 j -= consec; 679 } else if (minimum < consec) { 680 discards[i + j] = 0; 681 } 682 } 683 684 /* Scan from beginning of run 685 until we find 3 or more nonprovisionals in a row 686 or until the first nonprovisional at least 8 lines in. 687 Until that point, cancel any provisionals. */ 688 for (j = 0, consec = 0; j < length; j++) { 689 if (j >= 8 && discards[i + j] == 1) { 690 break; 691 } 692 if (discards[i + j] == 2) { 693 consec = 0; discards[i + j] = 0; 694 } else if (discards[i + j] == 0) { 695 consec = 0; 696 } else { 697 consec++; 698 } 699 if (consec == 3) { 700 break; 701 } 702 } 703 704 /* I advances to the last line of the run. */ 705 i += length - 1; 706 707 /* Same thing, from end. */ 708 for (j = 0, consec = 0; j < length; j++) { 709 if (j >= 8 && discards[i - j] == 1) { 710 break; 711 } 712 if (discards[i - j] == 2) { 713 consec = 0; discards[i - j] = 0; 714 } else if (discards[i - j] == 0) { 715 consec = 0; 716 } else { 717 consec++; 718 } 719 if (consec == 3) { 720 break; 721 } 722 } 723 } 724 } 725 } 726 } 727 728 /** Actually discard the lines. 729 @param discards flags lines to be discarded 730 */ 731 private void discard(final byte[] discards) { 732 final int end = bufferedLines; 733 int j = 0; 734 for (int i = 0; i < end; ++i) { 735 if (discards[i] == 0) { 736 undiscarded[j] = equivs[i]; 737 realindexes[j++] = i; 738 } else { 739 changedFlag[1+i] = true; 740 } 741 } 742 nondiscardedLines = j; 743 } 744 745 FileData(int length) { 746 bufferedLines = length; 747 equivs = new int[length]; 748 undiscarded = new int[bufferedLines]; 749 realindexes = new int[bufferedLines]; 750 } 751 752 FileData(Object[] data, Map<Object, Integer> h) { 753 this(data.length); 754 // FIXME: diff 2.7 removes common prefix and common suffix 755 for (int i = 0; i < data.length; ++i) { 756 Integer ir = h.get(data[i]); 757 if (ir == null) { 758 equivs[i] = equivMax++; 759 h.put(data[i], equivs[i]); 760 } else { 761 equivs[i] = ir; 762 } 763 } 764 } 765 766 /** 767 * Adjust inserts/deletes of blank lines to join changes as much as possible. 768 * <p> 769 * We do something when a run of changed lines include a blank line at one end and have an excluded blank line at the other. 770 * We are free to choose which blank line is included. 771 * `compareseq' always chooses the one at the beginning, but usually it is cleaner to consider the following blank line 772 * to be the "change". The only exception is if the preceding blank line would join this change to other changes. 773 * @param f the file being compared against 774 */ 775 void shiftBoundaries(FileData f) { 776 final boolean[] changed = changedFlag; 777 final boolean[] otherChanged = f.changedFlag; 778 int i = 0; 779 int j = 0; 780 int iEnd = bufferedLines; 781 int preceding = -1; 782 int otherPreceding = -1; 783 784 for (;;) { 785 int start, end, otherStart; 786 787 /* Scan forwards to find beginning of another run of changes. 788 Also keep track of the corresponding point in the other file. */ 789 790 while (i < iEnd && !changed[1+i]) { 791 while (otherChanged[1+j++]) { 792 /* Non-corresponding lines in the other file 793 will count as the preceding batch of changes. */ 794 otherPreceding = j; 795 } 796 i++; 797 } 798 799 if (i == iEnd) { 800 break; 801 } 802 803 start = i; 804 otherStart = j; 805 806 boolean loop = true; 807 while (loop) { 808 /* Now find the end of this run of changes. */ 809 810 while (i < iEnd && changed[1+i]) { 811 i++; 812 } 813 end = i; 814 815 /* If the first changed line matches the following unchanged one, 816 and this run does not follow right after a previous run, 817 and there are no lines deleted from the other file here, 818 then classify the first changed line as unchanged 819 and the following line as changed in its place. */ 820 821 /* You might ask, how could this run follow right after another? 822 Only because the previous run was shifted here. */ 823 824 if (end != iEnd && equivs[start] == equivs[end] && !otherChanged[1+j] 825 && !((preceding >= 0 && start == preceding) || (otherPreceding >= 0 && otherStart == otherPreceding))) { 826 changed[1+end] = true; 827 changed[1+start++] = false; 828 ++i; 829 /* Since one line-that-matches is now before this run 830 instead of after, we must advance in the other file 831 to keep in synch. */ 832 ++j; 833 } else { 834 loop = false; 835 } 836 } 837 838 preceding = i; 839 otherPreceding = j; 840 } 841 } 842 843 /** Number of elements (lines) in this file. */ 844 private final int bufferedLines; 845 846 /** Vector, indexed by line number, containing an equivalence code for each line. 847 * It is this vector that is actually compared with that of another file to generate differences. */ 848 private final int[] equivs; 849 850 /** Vector, like the previous one except that the elements for discarded lines have been squeezed out. */ 851 private final int[] undiscarded; 852 853 /** Vector mapping virtual line numbers (not counting discarded lines) to real ones (counting those lines). 854 * Both are origin-0. */ 855 private final int[] realindexes; 856 857 /** Total number of nondiscarded lines. */ 858 private int nondiscardedLines; 859 860 /** Array, indexed by real origin-1 line number, containing true for a line that is an insertion or a deletion. 861 The results of comparison are stored here. */ 862 private boolean[] changedFlag; 863 } 864}