www/variance-adjusted-patching.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   2 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
   3 <html xmlns="http://www.w3.org/1999/xhtml">
   4 <head>
   5 <style type="text/css"> /* <![CDATA[ */
   6   @import "branding/css/tigris.css";
   7   @import "branding/css/inst.css";
   8   /* ]]> */</style>
   9 <link rel="stylesheet" type="text/css" media="print"
  10   href="branding/css/print.css"/>
  11 <script type="text/javascript" src="branding/scripts/tigris.js"></script>
  12 <title>Variance-Adjusted Patching for Divergent Texts</title>
  13 </head>
  14
  15 <body>
  16 <div class="app">
  17
  18 <h2>Variance-Adjusted Patching for Divergent Texts</h2>
  19 <p>Karl&nbsp;Fogel&nbsp;<tt>&lt;kfogel@collab.net&gt;</tt></p>
  20
  21 <p>Date of First Publication: 22 May, 2001</p>
  22
  23 <p>$LastChangedDate$<br />
  24 Canonical URL: <a href="http://svn.collab.net/repos/svn/trunk/www/variance-adjusted-patching.html">http://svn.collab.net/repos/svn/trunk/www/variance-adjusted-patching.html</a></p>
  25
  26 <hr />  <!-- ====================================================== -->
  27
  28 <p>
  29 Version control systems that use traditional context diff / unidiff
  30 format for branch merging tend to fail spuriously in high variance
  31 situations.  A "high variance" situation is one where the branch text
  32 differs from the source text by more than roughly 5-10%, counting
  33 lines changed, deleted, and added against the source.  This appendix
  34 describes a technique called "variance-adjusted patching", by which
  35 such applications can be made to succeed, when a common ancestor of
  36 the source and destination texts is available.
  37 </p>
  38
  39 <p>
  40 The problem with straight patch application is that it depends on the
  41 affected text hunks and their context not having changed significantly
  42 since source.  They may "float", that is, text may have been inserted
  43 or deleted around them, thus changing their locations in the target
  44 file.  But they themselves may not have changed, except for whitespace
  45 adjustments or other trivial (i.e., automatically ignorable)
  46 modifications.  If they have changed, the patch application will fail.
  47 </p>
  48
  49 <p>
  50 Variance adjustment is the process of transforming a patch to account
  51 for differences that have arisen in the target text since the patch
  52 was generated, so that the new patch will be applicable to the new
  53 target text and yet still have the "same" effect as the old patch.  It
  54 is, in essence, patching a patch.  For example, suppose a branch B
  55 diverges from a trunk T, and an engineer wants to merge the change
  56 from revision T:18 to T:19 into B:10, creating B:11.  If B:10 is too
  57 dissimilar to T:18, the merge may fail due to textual conflicts, even
  58 though there is no logical conflict.  Variance adjustment is about
  59 changing the diff T:18-T:19 so that it applies cleanly to B:10.
  60 </p>
  61
  62 <p>
  63 This is possible because for any given line that a patch hunk expects
  64 to see in the target text (e.g., in a context diff, these would be the
  65 context lines, plus the "before" version of affected lines), the
  66 version control system can know that line's history in both source
  67 and target, if there is a common ancestor to examine.  The process is
  68 very similar to the calculations done by "<tt>cvs&nbsp;annotate</tt>".
  69 Informally speaking, one of the following is true for each such line,
  70 ignoring floating due to out-of-bounds insertion and deletion:
  71 </p>
  72
  73    <ol style="list-style-type: lower-alphs">
  74       <li><p><b>The line exists unchanged in both source and target</b></p>
  75       <p>If the line is still present in target and source, that means it
  76       has not been removed from either since the common ancestor, or
  77       if it was removed, it has been restored.  Nothing need be done
  78       to the diff.</p>
  79       </li>
  80       <li><p><b>The line has been changed in source but not in target</b></p>
  81       <p>In the diff hunk, the line should be changed to reflect the
  82       target's version of the line, so that the diff will be
  83       applicable to the target.</p>
  84       <p>
  85       <i>When we say that the line "has been changed", it just means
  86       that a different line appears where this line once appeared.
  87       Whether this is because the line has been edited, or because a
  88       new line has been inserted in target, does not matter.  (Another
  89       way to say it is that it need not matter whether the old version
  90       of the line still appears somewhere nearby in target.)  The
  91       important thing is that new text appears where the hunk is
  92       expecting old text, and that we have a way to change the hunk to
  93       expect the new text instead.</i></p>
  94       </li>
  95       <li><p><b>The line has been changed in target but not in source</b></p>
  96       <p>Same as above: in the diff hunk, the line should be changed to
  97       reflect the target's version of the line, so that the diff will
  98       be applicable to the target.  If this seems counterintuitive,
  99       drink the Kool-Aid and read again.</p>
 100       </li>
 101       <li><p><b>The line does not exist in target</b></p>
 102       <p>This could be for one of two reasons:</p>
 103            <ol>
 104            <li>the line is new in source, having been added after
 105                target branched, or</li>
 106            <li>the line was removed from target after the branch
 107                happened</li>
 108            </ol>
 109       <p>Either way, the line needs to be changed to the "corresponding"
 110       line in the target text -- that is, the line that, in target,
 111       now occupies the place of the obsolete expected line.  The
 112       version control system has enough information to determine
 113       which of the two cases above applies, and can use that to
 114       decide which of the lines currently in target is the best
 115       candidate to substitute for the missing line.</p>
 116       </li>
 117    </ol>
 118
 119 <p>
 120 Note that the case of the line not existing in source is impossible:
 121 if it doesn't exist in the current source, it certainly can't appear
 122 in the expected-text portions of the diff.
 123 </p>
 124
 125 <p>
 126 Although the patch program can adjust for floating at application
 127 time, the version control system can also adjust the line numbers in
 128 hunks to compensate for any insertions or deletions that have
 129 happened, in either source or target, outside the areas covered by the
 130 hunks.  This can result in a patch that applies perfectly, without any
 131 offset adjustment, to the target as it is known to the revision
 132 control system.  Of course, uncommitted local edits to the target
 133 cannot be compensated for in the diff -- we must still rely on the
 134 patch program's own offset adjustment and fuzz factor to handle those.
 135 </p>
 136
 137 <p>
 138 The above rules are an informal explanation of how variance adjustment
 139 works.  Below, the algorithm is described somewhat more formally, to
 140 show how the version control system would do variance adjustment in
 141 any situation.  Note that the algorithm is actually <i>too</i>
 142 powerful -- if taken to its logical limits, it can generate patches
 143 that apply cleanly even when the user would almost certainly prefer a
 144 conflict.  Thus it's necessary to offer an adjustment selectivity
 145 level; a good default selectivity would probably allow compensation
 146 for context variance, but not for variance in expected target lines.
 147 Anyway, the complete, unselective algorithm is described below, as it
 148 should be obvious where to attach the selectivity knobs if desired.
 149 </p>
 150
 151 <p>
 152 <strong>The Variance Adjustment Algorithm.</strong>
 153 </p>
 154
 155 <p>
 156 Some terminology:
 157 </p>
 158
 159    <dl>
 160       <dt><i>insertion</i></dt>
 161       <dd>A new line that has been added in either source or
 162       target since the common ancestor.</dd>
 163       <dt><i>deletion</i></dt>
 164       <dd>A line that has been deleted from either source or target
 165       since the common ancestor.</dd>
 166       <dt><i>edit</i></dt>
 167       <dd>A line that has been changed in either source or target
 168       since the common ancestor.</dd>
 169       <dt><i>out-range</i></dt>
 170       <dd>An event that happened to either source or target since the
 171       common ancestor, but to a line that is not covered in any of
 172       the diff hunks in the patch undergoing variance adjustment.  For
 173       example, an <i>out-range insertion</i> means a line was added in
 174       some region not directly touched by any of the hunks in the
 175       patch; an <i>out-range deletion</i> means a line was deleted
 176       from some region not in any hunk.</dd>
 177       <dt><i>in-range</i></dt>
 178       <dd>An event that happened to either source or target since the
 179       common ancestor, to a line covered in one of the diff hunks in
 180       the patch undergoing variance adjustment.  For example, an
 181       <i>in-range insertion</i> means a line was added in a region
 182       affected by one of the hunks; an <i>in-range deletion</i> means
 183       a line that was deleted from some region affected by a hunk.</dd>
 184       <dt><i>context</i></dt>
 185       <dd>A line included in a hunk for context only -- such lines are
 186       not affected by the patch.</dd>
 187       <dt><i>destination line, affected line</i></dt>
 188       <dd>(Used interchangeably).  A line that is actually affected by
 189       a patch.  For lines being edited or deleted, the line is already
 190       present in the target text; for lines being added, the line will
 191       only be present after the patch is applied.  In all cases it is
 192       present in a hunk in the patch.</dd>
 193    </dl>
 194
 195 <p>
 196 Description of the scenario:
 197 </p>
 198
 199 <p>
 200 Although there is no requirement that there be a "trunk"/"branch"
 201 relationship between the two lines, we will use that terminology below
 202 to make the description easier to understand.  In reality, there are
 203 simply two lines of development with a common ancestory.
 204 </p>
 205
 206 <p>
 207 Assume that branch B is rooted in trunk T at T:8; thus,
 208 T:8&nbsp;==&nbsp;B:1.  The youngest trunk revision is T:20, and the
 209 youngest branch revision is B:15.  A user with working copy on branch
 210 B wants to merge in the change T:19-T:20.  For brevity, we will call
 211 this change P, for "patch".  (We may speak, without loss of
 212 generality, as if only one file is being patched, as the same
 213 algorithm holds for every file involved in the merge.)
 214 </p>
 215
 216 <p>
 217 There are two problems that prevent the direct application of the
 218 unadjusted P to B:15.  P, being based on source text T:19,
 219 </p>
 220
 221    <ol>
 222    <li>contains certain changes not present in B:15, namely, changes T:9
 223    through T:19.
 224    </li>
 225    <li>does not contain certain changes present in B:15, namely,
 226    changes B:2 through B:15.</li>
 227    </ol>
 228
 229 <p>
 230 To adjust P, we first walk over the diff T:8-T:19, adjusting hunks as
 231 we go.  Each line in T:8-T:19 falls into one of the following
 232 categories:
 233 </p>
 234
 235    <ol>
 236    <li><i>Out-range added line</i>: decrement the line numbers in
 237        every hunk in P that comes after the addition.  This undoes the
 238        effect of the add, since the add never happened in B.</li>
 239    <li><i>Out-range deleted line</i>: increment the line numbers in
 240        every hunk in P that comes after the deletion.  This undoes the
 241        effect of the deletion, since the deletion never happened in
 242        B.</li>
 243    <li><i>Out-range edited line</i>: do nothing.  Out-range edits
 244        are irrelevant to P.</li>
 245    <li><i>Added line in context range in P</i>: remove the
 246        corresponding line from the context, optionally replacing it
 247        with new context <i>based on that region in B:15</i>, and
 248        adjust line numbers and mappings appropriately.</li>
 249    <li><i>Added line in affected text range in P</i>: this is a
 250        dependency problem -- part of the change T:18-T:19 depends on
 251        changes introduced to T after B branched.  There are several
 252        possible behaviors, depending on what the user wants.  One is
 253        to generate an informative error, stating that T:18-T:19
 254        depends on some other change (T:N-T:M, where N&gt;=8, M&lt;=18, and
 255        M-N&nbsp;==&nbsp;1); the exact revisions can be discovered
 256        automatically using the same process as "cvs annotate", though
 257        it may take some time to do so.  Another option is to include
 258        the change in P, as an insertion of the "after" version of the
 259        text, and adjust line numbers and mappings accordingly.  (And
 260        if all this isn't sounding a lot like a directory merge
 261        algorithm, try drinking more of the Kool-Aid.)  A third option
 262        is to include it as an insertion, but with metadata (such as
 263        CVS-style conflict markers) indicating that the line attempting
 264        to be patched does not exist in B.</li>
 265    <li><i>Deleted line that is in-range in P</i>: request another
 266        universe -- this situation can't happen in ours.</li>
 267    <li><i>In-range edited line</i>: reverse that edit in the "before"
 268        version of the corresponding line in the appropriate hunk in
 269        P, to obtain the version of the line that will be found in
 270        B when P is applied.</li>
 271    </ol>
 272
 273 <p>
 274 Now walk over the diff B:1-B:15, further adjusting P:
 275 </p>
 276
 277    <ol>
 278    <li><i>Out-range added line</i>: increment the line numbers in
 279        every hunk in P that comes after the addition.</li>
 280    <li><i>Out-range deleted line</i>: decrement the line numbers in
 281        every hunk in P that comes after the deletion.</li>
 282    <li><i>Out-range edited line</i>: do nothing.  Out-range edits
 283        are irrelevant to P.</li>
 284    <li><i>Added line in context range in P</i>: add that line to both
 285        sides of the context in the appropriate hunk, adjust line
 286        numbers in that hunk and all following hunks.</li>
 287    <li><i>Added line in affected text range in P</i>: add that line to
 288        the context in P and adjust numbers appropriately.</li>
 289    <li><i>Deleted line in-range in P</i>: dependency problem; see
 290        "<i>Added line in affected text range in P</i>" in the first
 291        pass above.</li>
 292    <li><i>In-range edited line</i>: apply that edit to the "before"
 293        version of the corresponding line in the appropriate hunk in
 294        P.</li>
 295    </ol>
 296
 297 <p>
 298 Now P is ready to apply to B:15, and even has enough context to apply
 299 over local edits.
 300 </p>
 301
 302 <p>
 303 Some of the steps in both loops can be compressed.  For example, when
 304 the number of added and deleted lines in a hunk is balanced, line
 305 number adjustment in later hunks is unnecessary; and balance can be
 306 quickly detected by inspecting only the line numbers of the hunk in
 307 question.
 308 </p>
 309
 310 <p>
 311 The algorithm handles inherent conflicts flexibly without losing
 312 information.  An "inherent" conflict is one where changes in T:8-T:19
 313 overlap with changes in B:1-B:15.  They can be either papered over by
 314 adjusting context and "before" lines as enthusiastically as possible;
 315 reported as errors, with dependency information included; or both
 316 sides of the overlap can be handed to the user, surrounded by
 317 CVS-style conflict markers.  Or if conflict markers are not the
 318 desired interface, the patch can hold the conflict in some other
 319 metadata markup (using the patch format comment space), and other
 320 tools can report on and help resolve it.
 321 </p>
 322
 323 <p>
 324 Let's take a brief look at what adjustment does to some patches.
 325 Here's a simple case, arising from an attempt to port an individual
 326 change from trunk to branch.  On trunk T, revision 1 looks like this:
 327 </p>
 328
 329 <pre>
 330 int main (int argc, char **argv)
 331 {
 332   /* line minus-five of context */
 333   /* line minus-four of context */
 334   /* line minus-three of context */
 335   /* line minus-two of context */
 336   /* line minus-one of context */
 337   printf ("Hello, world!\n");
 338   /* line plus-one of context */
 339   /* line plus-two of context */
 340   /* line plus-three of context */
 341   /* line plus-four of context */
 342   /* line plus-five of context */
 343 }
 344 </pre>
 345
 346 <p>
 347 A branch B also exists, rooted in the trunk at revision T:1.  On
 348 branch B, we commit a change to the context (we replace the words with
 349 numbers), so that B:2 looks like this:
 350 </p>
 351
 352 <pre>
 353 int main (int argc, char **argv)
 354 {
 355   /* line -5 of context */
 356   /* line -4 of context */
 357   /* line -3 of context */
 358   /* line -2 of context */
 359   /* line -1 of context */
 360   printf ("Hello, world!\n");
 361   /* line +1 of context */
 362   /* line +2 of context */
 363   /* line +3 of context */
 364   /* line +4 of context */
 365   /* line +5 of context */
 366 }
 367 </pre>
 368
 369 <p>
 370 Meanwhile on the trunk, we change only the middle line, so that T:2 is
 371 committed as:
 372 </p>
 373
 374 <pre>
 375 int main (int argc, char **argv)
 376 {
 377   /* line minus-five of context */
 378   /* line minus-four of context */
 379   /* line minus-three of context */
 380   /* line minus-two of context */
 381   /* line minus-one of context */
 382   printf ("Good-bye, cruel world!\n");
 383   /* line plus-one of context */
 384   /* line plus-two of context */
 385   /* line plus-three of context */
 386   /* line plus-four of context */
 387   /* line plus-five of context */
 388 }
 389 </pre>
 390
 391 <p>
 392 Using a traditional context-based approach, an attempt to patch B:2
 393 with the difference T:1-&gt;T:2 will fail, with a reject file if
 394 vanilla `<tt>patch</tt>' was used, or with conflict markers if
 395 `<tt>rcsmerge</tt>' was used:
 396 </p>
 397
 398 <pre>
 399 $ cvs up -j 1.1 -j 1.2 foo.c
 400 ### Purists will note that -j HEAD would have been sufficient; however, ###
 401 ### two -j's more clearly reflects the intent of the example.           ###
 402 RCS file: /usr/local/cvs/vap0/foo.c,v
 403 retrieving revision 1.1
 404 retrieving revision 1.2
 405 Merging differences between 1.1 and 1.2 into foo.c
 406 rcsmerge: warning: conflicts during merge
 407 $ cat foo.c
 408 int main (int argc, char **argv)
 409 {
 410 &lt;&lt;&lt;&lt;&lt;&lt;&lt; foo.c
 411   /* line -5 of context */
 412   /* line -4 of context */
 413   /* line -3 of context */
 414   /* line -2 of context */
 415   /* line -1 of context */
 416   printf ("Hello, world!\n");
 417   /* line +1 of context */
 418   /* line +2 of context */
 419   /* line +3 of context */
 420   /* line +4 of context */
 421   /* line +5 of context */
 422 =======
 423   /* line minus-five of context */
 424   /* line minus-four of context */
 425   /* line minus-three of context */
 426   /* line minus-two of context */
 427   /* line minus-one of context */
 428   printf ("Good-bye, cruel world!\n");
 429   /* line plus-one of context */
 430   /* line plus-two of context */
 431   /* line plus-three of context */
 432   /* line plus-four of context */
 433   /* line plus-five of context */
 434 &gt;&gt;&gt;&gt;&gt;&gt;&gt; 1.2
 435 }
 436 </pre>
 437
 438 <p>
 439 Because the context has changed, the change to the middle line cannot
 440 be found.  If we adjust the patch T:1-&gt;T:2, it would look like
 441 this:
 442 </p>
 443
 444 <pre>
 445 *** foo.c       2001/05/18 08:15:28     1.1
 446 --- foo.c       2001/05/18 08:20:59     1.2
 447 ***************
 448 *** 5,11 ****
 449     /* line -3 of context */
 450     /* line -2 of context */
 451     /* line -1 of context */
 452 !   printf ("Hello, world!\n");
 453     /* line +1 of context */
 454     /* line +2 of context */
 455     /* line +3 of context */
 456 --- 5,11 ----
 457     /* line -3 of context */
 458     /* line -2 of context */
 459     /* line -1 of context */
 460 !   printf ("Goodbye, cruel world!\n");
 461     /* line +1 of context */
 462     /* line +2 of context */
 463     /* line +3 of context */
 464 </pre>
 465
 466 <p>
 467 and would now apply perfectly to B:2, even though this diff never
 468 existed between any two committed revisions.
 469 </p>
 470
 471 <p>
 472 Let's try a slightly more complex case, starting with the same T:1 and
 473 B:1:
 474 </p>
 475
 476 <pre>
 477 int main (int argc, char **argv)
 478 {
 479   /* line minus-five of context */
 480   /* line minus-four of context */
 481   /* line minus-three of context */
 482   /* line minus-two of context */
 483   /* line minus-one of context */
 484   printf ("Hello, world!\n");
 485   /* line plus-one of context */
 486   /* line plus-two of context */
 487   /* line plus-three of context */
 488   /* line plus-four of context */
 489   /* line plus-five of context */
 490 }
 491 </pre>
 492
 493 <p>
 494 T:2 has some inserted lines near the top:
 495 </p>
 496
 497 <pre>
 498 #include &lt;stdio.h&gt;
 499
 500 int main (int argc, char **argv)
 501 {
 502   /* line minus-five of context */
 503   /* line minus-four of context */
 504   /* line minus-three of context */
 505   /* line minus-two of context */
 506   /* line minus-one of context */
 507   printf ("Hello, world!\n");
 508   /* line plus-one of context */
 509   /* line plus-two of context */
 510   /* line plus-three of context */
 511   /* line plus-four of context */
 512   /* line plus-five of context */
 513 }
 514 </pre>
 515
 516 <p>
 517 And then another change was committed on the trunk, editing the middle
 518 line, so that T:3 looks like this:
 519 </p>
 520
 521 <pre>
 522 #include &lt;stdio.h&gt;
 523
 524 int main (int argc, char **argv)
 525 {
 526   /* line minus-five of context */
 527   /* line minus-four of context */
 528   /* line minus-three of context */
 529   /* line minus-two of context */
 530   /* line minus-one of context */
 531   printf ("Good-bye, cruel world!\n");
 532   /* line plus-one of context */
 533   /* line plus-two of context */
 534   /* line plus-three of context */
 535   /* line plus-four of context */
 536   /* line plus-five of context */
 537 }
 538 </pre>
 539
 540 <p>
 541 Meanwhile, one complex change has been committed on the branch, so B:2
 542 looks like this:
 543 </p>
 544
 545 <pre>
 546 int main (int argc, char **argv)
 547 {
 548   /* line minus-five of context */
 549   /* line minus-four of context */
 550   /* line minus-three of context */
 551   /* line -1 of context */
 552   printf ("Hello, world!\n");
 553   /* newly inserted line of context */
 554   /* line plus-one of context */
 555   /* line plus-two of context */
 556   /* line plus-three of context */
 557   /* line plus-four of context */
 558   /* line plus-five of context */
 559 }
 560 </pre>
 561
 562 <p>
 563 Line minus-two of context was removed, line minus-one was changed to
 564 "-1", and a new line of context was inserted farther down.  Now the
 565 branch developer wants to merge in the change T:2-T:3.  Unadjusted,
 566 the patch looks like this:
 567 </p>
 568
 569 <pre>
 570 Index: foo.c
 571 ===================================================================
 572 RCS file: /usr/local/cvs/vap1/foo.c,v
 573 retrieving revision 1.2
 574 retrieving revision 1.3
 575 diff -c -r1.2 -r1.3
 576 *** foo.c       2001/05/22 21:17:14     1.2
 577 --- foo.c       2001/05/22 21:19:42     1.3
 578 ***************
 579 *** 7,13 ****
 580     /* line minus-three of context */
 581     /* line minus-two of context */
 582     /* line minus-one of context */
 583 !   printf ("Hello, world!\n");
 584     /* line plus-one of context */
 585     /* line plus-two of context */
 586     /* line plus-three of context */
 587 --- 7,13 ----
 588     /* line minus-three of context */
 589     /* line minus-two of context */
 590     /* line minus-one of context */
 591 !   printf ("Good-bye, cruel world!\n");
 592     /* line plus-one of context */
 593     /* line plus-two of context */
 594     /* line plus-three of context */
 595 </pre>
 596
 597 <p>
 598 Following the adjustment algorithm, it looks like this:
 599 </p>
 600
 601 <pre>
 602 Index: foo.c
 603 ===================================================================
 604 RCS file: /usr/local/cvs/vap1/foo.c,v
 605 retrieving revision 1.2
 606 retrieving revision 1.3
 607 diff -c -r1.2 -r1.3
 608 *** foo.c       2001/05/22 21:17:14     1.2
 609 --- foo.c       2001/05/22 21:19:42     1.3
 610 ***************
 611 *** 5,11 ****
 612     /* line minus-four of context */
 613     /* line minus-three of context */
 614     /* line -1 of context */
 615 !   printf ("Hello, world!\n");
 616     /* newly inserted line of context */
 617     /* line plus-one of context */
 618     /* line plus-two of context */
 619 --- 5,11 ----
 620     /* line minus-four of context */
 621     /* line minus-three of context */
 622     /* line -1 of context */
 623 !   printf ("Good-bye, cruel world!\n");
 624     /* newly inserted line of context */
 625     /* line plus-one of context */
 626     /* line plus-two of context */
 627 </pre>
 628
 629 <p>
 630 Note how the line numbers have been adjusted to compensate for the
 631 absence of change T:1-T:2 (since the patch we're applying only
 632 concerns T:2-T:3), and the context has been changed to include the
 633 difference B:1-B:2.
 634 </p>
 635
 636 <p>
 637 Again, this patch never existed between any two revisions, but it
 638 applies cleanly to B:2.
 639 </p>
 640
 641 <p>
 642 The cost of the adjustment algorithm is proportional to the size of
 643 the diff from branch point to trunk head plus the diff from branch
 644 point to branch head, plus the size (for time, number of hunks) in the
 645 diff being adjusted.  This is comparable to the cost of using
 646 reverse-delta storage in the first place.  Also, the user consuming
 647 the final patch does not need access to all the intermediate changes
 648 -- she only needs permissions on the endpoints of the diff, the common
 649 ancestor of the two lines, and the revision to which the patch is
 650 being applied.  Intermediate revisions need not be accessible by the
 651 user.
 652 </p>
 653
 654 <p>
 655 Through variance-adjusted patching, any repository that stores
 656 successive revisions can apply patches even between highly divergent
 657 branches, as long as there is a common ancestor.
 658 </p>
 659
 660 <h4>Addendum</h4>
 661
 662 <p>For clarity, I have used line-based diffs to describe the process
 663 of variance adjustment.  The algorithm applies equally well, of
 664 course, to other kinds of diffs, including arbitrary binary diffs.  In
 665 fact,
 666 <a href="http://www.red-bean.com/pipermail/changesets/2003-April/000097.html"
 667 >Dr. William Uther wrote</a>:</p>
 668
 669 <blockquote>
 670 <p>
 671 <em>I actually gave an example of a binary version of the VAP algorithm on
 672 the svn-dev list a while back.  It used VAP at the byte level, instead
 673 of at the line level.  It was similar to your suggested VAP algorithm
 674 in that you could adjust the 'soft-conflict' zone around the changes.
 675 </em>
 676 </p>
 677 </blockquote>
 678
 679 <p>The message he's referring to appears to be this one:</p>
 680
 681 <pre>
 682    <a href="http://subversion.tigris.org/servlets/ReadMsg?list=dev&amp;msgId=162878">http://subversion.tigris.org/servlets/ReadMsg?list=dev&amp;msgId=162878</a>
 683    From: William Uther
 684    To: dev@subversion.tigris.org
 685    Subject: Re: Merging
 686    Date: Sat, 16 Feb 2002 21:19:43 -0500
 687    Message-ID: &lt;B8947D6F.787C%will=subversion@cs.cmu.edu&gt;
 688    In-Reply-To: &lt;51C7002B020CD411824E009027C469F782259A@cldxch01.hifn.com&gt;
 689 </pre>
 690
 691 <p>I mention this here in order to help anyone using this algorithm as
 692 prior art in a patent challenge.  I doubt I was the first person to
 693 describe variance-adjusted patching, but at the very least we can know
 694 that the method was described as of 22 May 2001&nbsp;&mdash;&nbsp;and
 695 that both I and someone else "proficient in the art" (William Uther)
 696 thought its applicability to binary diffs to be pretty obvious.</p>
 697
 698 </div>
 699 </body>
 700 </html>