← Back to branch summary

~svn/ubuntu/raring/subversion/ppa

« back to all changes in this revision

Viewing changes to www/variance-adjusted-patching.html

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-12-05 01:26:14 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051205012614-qom4xfypgtsqc2xq
Tags: 1.2.3dfsg1-3ubuntu1
Merge with the final Debian release of 1.2.3dfsg1-3, bringing in
fixes to the clean target, better documentation of the libdb4.3
upgrade and build fixes to work with swig1.3_1.3.27.

Show diffs side-by-side

added added

removed removed

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