www/merge-tracking/design.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>Merge Tracking Design</title>
  13
  14 <style type="text/css">
  15 .question { color: grey; }
  16 .answer   { }
  17 </style>
  18 </head>
  19
  20 <body>
  21 <div class="h1">
  22 <h1>Merge Tracking Design</h1>
  23
  24 <p style="color: red">*** UNDER CONSTRUCTION ***</p>
  25
  26 <p>Subversion's <a href="index.html">merge tracking</a> uses a layered
  27 design, with the user-visible operations based primarily on the
  28 information from the <a href="#merge-history">merge history</a>.</p>
  29
  30 <ul>
  31   <li><a href="#merge-history">Merge History</a></li>
  32   <li><a href="#data-structures">Data Structures</a></li>
  33   <li>Merge Operations (TODO)</li>
  34   <li><a href="#audit-operations">Audit Operations</a></li>
  35   <li>Other Operations (TODO)</li>
  36 </ul>
  37
  38 <div class="h2" id="merge-history">
  39 <h2>Merge History</h2>
  40
  41 <p>Or, <em>Tracking What Revisions Have Been Merged Where</em>
  42 provides the information used by Subversion's merge tracking-related
  43 capabilities (history sensitive merging, etc.).  The design is based
  44 on Dan Berlin's <a
  45 href="http://svn.haxx.se/dev/archive-2006-04/0916.shtml">proposal</a>
  46 <small>(Message-Id:
  47 &lt;1146242044.23718.1.camel@dberlin0-corp.corp.google.com&gt;)</small>
  48 and subsequent edits.</p>
  49
  50 <div class="h3">
  51 <h3>Goals</h3>
  52
  53 <p>The goal of the Merge History portion of the design is to track the
  54 information needed by the operations outlined by the majority of the
  55 <a href="requirements.html">use cases</a> (e.g. the revision numbers
  56 being merged by a merge operation), and keeping this information in
  57 the right places as various operations (<code>copy</code>,
  58 <code>delete</code>, <code>add</code>, etc.) are performed.  This
  59 portion of the design does <em>not</em> encompass the operations
  60 themselves.</p>
  61
  62 <p>The goals:</p>
  63
  64 <ul>
  65   <li>To be able to track this down to what files in a working copy
  66   and be able to determine what files have had what revisions merged
  67   into them.</li>
  68
  69   <li>To not need to contact the server more than we already do now to
  70   determine which revisions have been merged in a file or directory
  71   (e.g. some contact is acceptable, asking the server about each file is
  72   not).</li>
  73
  74   <li>To be able to edit merge information in a human-readable form.</li>
  75
  76   <li>For the information to be stored in a space efficient manner,
  77   and to be able to determine the revisions merged into a given
  78   file/director in a time efficient manner.</li>
  79
  80   <li>Still getting a conservatively correct answer (not worse than
  81   what we have now) when no merge info is available.</li>
  82
  83   <li>To be able to collect, transmit, and keep this information up to
  84   date as much as possible on the client side.</li>
  85
  86   <li>To be able to index this information in the future order to
  87   answer queries.</li>
  88 </ul>
  89
  90 <p>Non-goals for <em>the 1.5 design</em> include:</p>
  91
  92 <ul>
  93   <li>Doing actual <a href="func-spec.html#as-merge">history sensitive
  94   merging</a>.  Subversion does not yet have sufficient support for
  95   creation of fully accurate changeset graphs, which are necessary to
  96   handle cyclic merging (e.g. of so-called "reflected"
  97   revisions, also known as repeated bi-directional mergeing).  For
  98   details on this problem (caused by lack of tracking of multiple
  99   parents for a change), see <a
 100   href="http://subversion.tigris.org/servlets/ReadMsg?listName=dev&amp;msgNo=127537"
 101   >this discussion thread</a>, and especially <a
 102   href="http://subversion.tigris.org/servlets/ReadMsg?listName=dev&amp;msgNo=127570"
 103   >this follow-up</a>.</li>
 104
 105   <li>Curing cancer (aka being all things to all people).</li>
 106 </ul>
 107
 108 </div>  <!-- goals -->
 109
 110 <div class="h3" id="storage">
 111 <h3>Information Storage</h3>
 112
 113 <p>The first question that many people ask is "where should we store
 114 the merge information?" (what we store will be covered next).  A merge
 115 history property, named <code>SVN_PROP_MERGEINFO</code>
 116 (e.g. <code>svn:mergeinfo</code>) stored in directory and file
 117 properties.  Each will store the <em>full</em>, <em>complete</em> list
 118 of current merged-in changes, as far as it knows.  This ensures that
 119 the merge algorithm and other consumers do not have to walk back
 120 through old revisions in order to compute a complete list of merge
 121 information for a path.</p>
 122
 123 <p>Directly merged into the item means changes from any merge that
 124 have affected this path, which includes merges into parents,
 125 grandparents, etc., that had some affect on the path.</p>
 126
 127 <p>Doing this storage of complete information at each point makes
 128 manual editing safe, because the changes to a path's merge info are
 129 localized to that path.</p>
 130
 131 <p>However, as a space optimization, if the information on a
 132 sub-directory or file is exactly the same as the merge information for
 133 its parent directory, it <em>may</em> be elided in favor of that
 134 parent information.  This eliding may is done on the fly, but could
 135 also be done during a postpass (e.g. a <code>svnadmin
 136 mergeinfo-optimize</code>).  Eliding information means that an
 137 implementation may have to walk parent directories in order to gather
 138 information about merge info (however, this may have been necessary
 139 anyways).  It is expected that directory trees are not that deep, and
 140 the lookup of merge info properties quick enough (due to indexing,
 141 etc.), to make this eliding not affect performance too much.</p>
 142
 143 <p>Eliding will never affect the semantics of merge information, as it
 144 should only be performed in the case when it was exactly the same, and
 145 if it was exactly the same, it could not have had an effect on the
 146 merge results.</p>
 147
 148 <p>Any path may have merge info attached to it.</p>
 149
 150 <p>The way we choose which path's merge info to use in case of
 151 conflicts involves a simple system of inheritance <a
 152 href="#merge-history-footnotes">[1]</a>, where the "most specific"
 153 place wins.  This means that if the property is set on a file, that
 154 completely overrides the directory level properties for the directory
 155 containing the file.  Non-inheritable merge info can be set on
 156 directories, signifying that the merge info applies only to the
 157 directory but not its children.</p>
 158
 159 <p>The way we choose which to store to depends on how much and where
 160 you merge, and will be covered in the semantics.</p>
 161
 162 <p>The reasoning for this system is to avoid having to either copy
 163 info everywhere, or crawl everywhere, in order to determine which
 164 revisions have been applied.  At the same time, we want to be space
 165 and time efficient, so we can't just store the entire revision list
 166 everywhere.</p>
 167
 168 <p>As for what is stored:</p>
 169
 170 <p>A survey of the community shows a slight preference for a human
 171 editable storage format along the lines of how
 172 <code>svnmerge.py</code> stores its merge info (e.g. path name and
 173 list of revisions).  Binary storage of such information would buy, on
 174 average, a 2-3 byte decrease per revision/range in size over ASCII <a
 175 href="#merge-history-footnotes">[2]</a>, while making it not directly
 176 human-readable/editable.</p>
 177
 178 <p>The revisions we have merged <em>into</em> something are
 179 represented as a path, a colon, and then a comma separated revision
 180 list, containing one or more revision or revision ranges.  Revision
 181 range end and beginning points are separated by "-".</p>
 182
 183 <div class="h4" id="merge-info-grammar">
 184 <h4>Grammar</h4>
 185 <table>
 186 <tr>
 187   <th align="left">Token</th>
 188   <th align="left">Definition</th>
 189 </tr>
 190 <tr>
 191   <td>revisionrange</td>
 192   <td>REVISION "-" REVISION</td>
 193 </tr>
 194 <tr>
 195   <td>revisioneelement</td>
 196   <td>(revisionrange | REVISION)"*"?</td>
 197 </tr>
 198 <tr>
 199   <td>rangelist</td>
 200   <td>revisioneelement (COMMA revisioneelement)*</td>
 201 </tr>
 202 <tr>
 203   <td>revisionline</td>
 204   <td>PATHNAME COLON rangelist</td>
 205 </tr>
 206 <tr>
 207   <td>top</td>
 208   <td>revisionline (NEWLINE revisionline)*</td>
 209 </tr>
 210 </table>
 211 </div>  <!-- merge-info-grammar -->
 212
 213 <p>This merge history ("top"), existing on a path specifies all the
 214 changes that have ever been merged into this object (file, dir or
 215 repo) within this repository.  It specifies the sources of the merges,
 216 (and thus two or more pathnames may be required to represent one
 217 source object at different revisions due to renaming).</p>
 218
 219 <p>The optional "*" following a revisionelement token signifies a
 220 non-inheritable revision/revision range.</p>
 221
 222 <p>This list will <em>not</em> be stored in a canonicalized minimal
 223 form for a path (e.g. it may contain single revision numbers that
 224 could fall into ranges).  This is chiefly because the benefit of such
 225 a canonical format -- which is slightly easier for visual
 226 <em>comparison</em>, but not indexing -- is outweighed by the fact
 227 that generating a canonical form may require groveling through a lot
 228 of information to determine what that minimal canonical form is.  In
 229 particular, it may be that the revision list "5,7,9" is, in minimal
 230 canonical form, "5-9", because 6 and 8 do not have any affect on the
 231 path name that 5 and 9 are from.  Canonicalization could be done as a
 232 server side post pass because the information is stored in
 233 properties.</p>
 234
 235 <p>Note that this revision format will not scale on its own if you
 236 have a list of million revisions.  None will easily.  However, because
 237 it is stored in properties, one can change the WC and FS backends to
 238 simply do something different with this single property if they wanted
 239 to.  Given the rates of change of various very active repositories,
 240 this will not be a problem we need to solve for many many years.</p>
 241
 242 <p>The payload of <code>SVN_PROP_MERGEINFO</code> will be duplicated
 243 in an index separate from the FS which is created during
 244 <code>svnadmin create</code>, or on-demand for a pre-existing
 245 repository which has started using Subversion 1.5.  This index will
 246 support fast querying, be populated during a merge or <code>svnadmin
 247 load</code>, and cough up its contents as needed during API calls.
 248 The contents of <code>SVN_PROP_MERGEINFO</code> is stored redundantly
 249 in index (to the FS).  Dan Berlin has prototyped a simple index using
 250 sqlite3.  David James later proposed a more normalized schema design,
 251 some of the features of which may become useful for implementing Merge
 252 Tracking functionality in a more performant manner.</p>
 253
 254 </div>  <!-- storage -->
 255
 256
 257 <div class="h3">
 258 <h3>Information Updating</h3>
 259
 260 <p>Each operation you can perform may update or copy the merge info
 261 associated with a path.</p>
 262
 263 <p><code>svn add</code>:  No change to merge info.</p>
 264
 265 <p><code>svn delete</code>: No direct change to merge info
 266 (indirectly, because the props go away, so does the merge info for the
 267 file).</p>
 268
 269 <p><code>svn copy</code>: Makes a full copy of any explicit merge info
 270 from the source path to the destination path.  Also adds "implied"
 271 merge info from the source path.</p>
 272
 273 <p><code>svn rename</code>: Same as <code>svn copy</code>.</p>
 274
 275 <p><code>svn merge</code>: Adds or subtracts to the merge info,
 276 according to the following:</p>
 277
 278 <ul>
 279   <li>Where to store the info:
 280   <ol>
 281     <li>If the merge target is a single file, the merge info goes to
 282     the property <code>SVN_PROP_MERGEINFO</code> set on that file.</li>
 283
 284     <li>If the merge target is a directory, the merge info goes to the
 285     property <code>SVN_PROP_MERGEINFO</code> set on the shallowest
 286     directory of the merge (e.g. the topmost directory affected by the
 287     merge) that will require different info than the info already set
 288     on other directories.</li>
 289   </ol>
 290
 291   The last clause of rule 2 is only meant to handle cherry picking and
 292   multiple merges.  In the case that people repeatedly merge the same
 293   tree into the same tree, the information will end up only on the
 294   shallowest directory of the merge.  If changes are selectively
 295   applied (e.g. all changes are applied to every directory but one),
 296   the information will be on the shallowest common ancestor of all
 297   those directories, <em>as well</em> as information being placed on
 298   the directory where the changes are not applied, so that it will
 299   override the information from that shallow directory. See cherry
 300   picking example for more details.  Besides selective application,
 301   apply changes that affect some directory, and then applying
 302   different changes to subdirectories of that directory, will also
 303   produce merge info on multiple directories in a given path.
 304   </li>
 305
 306   <li>What info is stored:
 307   <ol>
 308     <li>If you are merging in reverse, revisions are subtracted from
 309     the revision lines, but we never write out anti-revisions.  Thus,
 310     if you subtract all the merged revisions, you just get an empty
 311     list, and if you do a reverse merge from there, you still get an
 312     empty list.</li>
 313
 314     <li>If you are merging forward, the revision(s) you are merging is
 315     added to the range list in sorted order (such that all revisions
 316     and revision ranges in the list are monotonically increasing from
 317     left to right).</li>
 318
 319     <li>The path (known as PATHNAME in the grammar) used as the key to
 320     determine which revision line to change is the sub-directory path
 321     being merged from, relative to the repo root, with the repo URL
 322     stripped from it.</li>
 323   </ol>
 324
 325   In the case that we are merging changes that themselves contain
 326   merge info, the merge info properties must be merged.  The effect of
 327   this is that indirect merge info becomes direct merge info as it is
 328   integrated as part of the merge info now set on the property.  The
 329   way this merge is performed is to merge the revision lists for each
 330   identical pathname, and to copy the rest.  Blocking of merges and
 331   how this affects this information is not covered in this design.
 332   The indirect info merging is *in addition* to specifying the merge
 333   that we are now doing.  See the repeated merge with indirect info
 334   example for an example.
 335   </li>
 336 </ul>
 337
 338 <p>Thus a merge of revisions 1-9 from
 339 http://example.com/repos-root/trunk would produce "/trunk:1-9"</p>
 340
 341 <p>Cross-repo merging is a bridge we can cross if we ever get there :).</p>
 342
 343 </div>  <!-- h3 -->
 344
 345
 346 <div class="h3">
 347 <h3>Examples</h3>
 348
 349 <div class="h4">
 350 <h4>Repeated merge</h4>
 351
 352 <p>(I have assumed no renames here, and that all directories were
 353 added in rev 1, for simplicity.  The pathname will never change, this
 354 should not cause any issues that need examples.)</p>
 355
 356 <p>Assume trunk has 9 revisions, 1-9.</p>
 357
 358 <p>A merge of /trunk into /branches/release will produce the merge
 359 info "/trunk: 1-9".</p>
 360
 361 <p>Assume trunk now has 6 additional revisions, 14-18.</p>
 362
 363 <p>A merge of /trunk into /branches/release should only merge 14-18
 364 and produce the merge info "/trunk: 1-9,14-18".  This merge info will
 365 be placed on /branches/release.</p>
 366
 367 <p>(Note the canonical minimal form of the above would be 1-18, as
 368 9-14 do not affect that path.  This is also an acceptable answer, as
 369 is any variant that represents the same information.)</p>
 370
 371 </div>  <!-- h4 -->
 372
 373 <div class="h4">
 374 <h4>Repeated merge with indirect info</h4>
 375
 376 <p>Assume the repository is in the state it would be after the
 377 "Repeated merge" example.  Assume additionally, we now have a branch
 378 /branches/next-release, with revisions 20-24 on it.</p>
 379
 380 <p>We wish to merge /branches/release into /branches/next-release.</p>
 381
 382 <p>A merge of /branches/release into /branches/next-release will produce
 383 the merge info:</p>
 384 <pre>
 385 "/branches/release: 1-24
 386  /trunk:1-9,14-18"
 387 </pre>
 388
 389 <p>This merge info will be placed on /branches/next-release.</p>
 390
 391 <p>Note that the merge information about merges *to* /branches/release
 392 has been added to our merge info.</p>
 393
 394 <p>A future merge of /trunk into /branches/next-release, assuming no
 395 new revisions on /trunk, will merge nothing.</p>
 396
 397 </div>  <!-- h4 -->
 398
 399 <div class="h4">
 400 <h4>Cherry picking a change to a file</h4>
 401
 402 <p>Assume the repository is in the state it would be after the
 403 "Repeated merge with indirect info" example.</p>
 404
 405 <p>Assume we have revision 25 on /trunk, which affects /trunk/foo.c
 406 and /trunk/foo/bar/bar.c</p>
 407
 408 <p>We wish to merge the portion of change affecting /trunk/foo.c</p>
 409
 410 <p>A merge of revision 25 of /trunk/foo.c into /branches/release/foo.c
 411 will produce the merge info:</p>
 412 <pre>
 413 "/trunk/foo.c:1-9,14-18,25".
 414 This merge information will be placed on /branches/release/foo.c
 415 </pre>
 416
 417 <p>All other merge information will still be intact on
 418 /branches/release (ie there is information on /branches/release's
 419 directory).</p>
 420
 421 <p>(The cherry picking one directory case is the same as file, with
 422 files replaced with directories, hence i have not gone through the
 423 example).</p>
 424
 425 </div>  <!-- h4 -->
 426
 427 <div class="h4">
 428 <h4>Merging changes into parents and then merging changes into
 429 children</h4>
 430
 431 <p>Assume the repository is in the state it would be after the
 432 "Repeated merge with indirect info" example.  Assume we have revision
 433 25 on /trunk, which affects /trunk/foo Assume we have revision 26 on
 434 /trunk, which affects /trunk/foo/baz We wish to merge revision 25 into
 435 /branches/release/foo, and merge revision 26 into
 436 /branches/release/foo/baz.</p>
 437
 438 <p>A merge of revision 25 of /trunk/foo into /branches/release/foo will
 439 produce the merge info:</p>
 440 <pre>"/trunk:1-9,14-18,25"
 441 </pre>
 442
 443 <p>This merge information will be placed on /branches/release/foo</p>
 444
 445 <p>A merge of revision 26 of /trunk/foo/baz into
 446 /branches/release/foo/baz will produce the merge info:</p>
 447 <pre>"/trunk:1-9,14-18,26".
 448 </pre>
 449
 450 <p>This merge information will be placed on
 451 /branches/release/foo/baz.</p>
 452
 453 <p>Note that if you instead merge revision 26 of /trunk/foo into
 454 /branches/release/foo, you will get the same effect, but the merge
 455 info will be:</p>
 456 <pre>"/trunk:1-9,14-18,25-26".
 457 </pre>
 458
 459 <p>This merge information will be placed on /branches/releases/foo</p>
 460
 461 <p>Both are different "spellings" of the same merge information, and
 462 future merges should produce the same result with either merge info
 463 (one is of course, more space efficient, and transformation of one to
 464 the other could be done on the fly or as a postpass, if desired).</p>
 465
 466 <p>All other merge information will still be intact on
 467 /branches/release (e.g. there is information on /branches/release's
 468 directory).</p>
 469
 470 </div>  <!-- h4 -->
 471
 472 </div>  <!-- h3 -->
 473
 474
 475 <div class="h3" id="merge-history-faq">
 476 <h3>FAQ</h3>
 477
 478 <p class="question">What happens if someone commits a merge with a
 479 non-merge tracking client?</p>
 480
 481 <p class="answer">It simply means the next time you merge, you may
 482 receive conflicts that you would have received if you were using a
 483 non-history-sensitive client.</p>
 484
 485 <p class="question">What happens if the merge history is not there?</p>
 486
 487 <p class="answer">The same thing that happens if the merge history is
 488 not there now.</p>
 489
 490 <p class="question">Are there many different "spellings" of the same
 491 merge info?</p>
 492
 493 <p class="answer">Yes.  Depending on the URLs and target you specify
 494 for merges, I believe it is possible to end up with merge info in
 495 different places, or with slightly different revision lines that have
 496 the same semantic effect (e.g. info like /trunk:1-9 vs
 497 /trunk:1-8\n/trunk/bar:9 when revision 9 on /trunk only
 498 affected /trunk/bar), so you can end up with merge info in different
 499 places, even though the semantic result will be the same in all
 500 cases.</p>
 501
 502 <p class="question">Can we do history sensitive WC-to-WC merges
 503 without contacting the server?</p>
 504
 505 <p class="answer">No. But you probably couldn't anyway without
 506 <em>all</em> repo merge data stored locally.</p>
 507
 508 <p class="question">What happens if a user edits merge history
 509 incorrectly?</p>
 510
 511 <p class="answer">They get the results specified by their merge
 512 history.</p>
 513
 514 <p class="question">What happens if a user manually edits a file and
 515 unmerges a revision (e.g. not using a "reverse merge" command), but
 516 doesn't update the merge info to match?</p>
 517
 518 <p class="answer">The merge info will believe the change has still
 519 been merged.  This is a similar effect to performing a <a
 520 href="requirements.html#manual-merge">manual merge</a>.</p>
 521
 522 <p class="question">What happens if I <code>svn
 523 move</code>/<code>rename</code> a directory, and then merge it
 524 somewhere?</p>
 525
 526 <p class="answer">This doesn't change history, only the future, thus
 527 we will simply add the merge info for that directory as if it was a
 528 new directory.  We will not do something like attempt to modify all
 529 merge info to specify the new directory, as that would be wrong.</p>
 530
 531 <p class="question">I don't think only that copying info on <code>svn
 532 copy</code> is correct.  What if you copy a dir with merge info into a
 533 dir where the dir has merge info -- won't it get the info wrong
 534 now?</p>
 535
 536 <div class="answer">
 537 <p>No.  Let's say you have:</p>
 538
 539 <pre>
 540 a/foo (merge info: /trunk:5-9
 541 a/branches/bar (merge info: /trunk:1-4)
 542 </pre>
 543
 544 <p>If you copy a/foo into a/branches/bar, we now have:</p>
 545
 546 <pre>
 547 a/branches/bar (merge info: /trunk:1-4)
 548 a/branches/bar/foo (merge info: /trunk:5-9)
 549 </pre>
 550
 551 <p>This is strictly correct.  The only changes which have been merged
 552 into a/branches/bar/foo, are still 5-9.  The only changes which have
 553 been merged into /branches/bar are 1-4.  No merges have been performed
 554 by your copy, only copies have been performed.  If you perform a merge
 555 of revisions 1-9 into bar, the results one would expect that the
 556 history sensitive merge algorithm will skip revisions 5-9 for
 557 a/branches/bar/foo, and skip revisions 1-4 for a/branches/bar.  The
 558 above information gives the algorithm the information necessary to do
 559 this.
 560
 561 So if you want to argue svn copy has the wrong merge info semantics,
 562 it's not because of the above, AFAIK :)</p>
 563 </div>
 564
 565 </div>  <!-- merge-history-faq -->
 566
 567 <div class="h3" id="merge-history-footnotes">
 568 <h3>Footnotes</h3>
 569
 570 <ol>
 571   <li>This is not going to be a full blown design for property
 572   inheritance, nor should this design depend on such a system being
 573   implemented.</li>
 574
 575   <li>Assuming 4 byte revision numbers, and repos with revisions
 576   numbering in the hundreds of thousands.  You could do slightly
 577   better by variable length encoding of integers, but even that will
 578   generally be 4 bytes for hundreds of thousands of revs.  Thus, we
 579   have strings like "102341" vs 4 byte numbers, meaning you save about
 580   2 bytes for a 4 byte integer.  Range lists in binary would need a
 581   distinguisher from single revisions, adding a single bit to both
 582   (meaning you'd get 31 bit integers), and thus, would require 8 bytes
 583   per range vs 12 bytes per range.  While 30% is normally nothing to
 584   sneeze at space wise, it's also not significantly more efficient in
 585   time, as most of the time will not be spent parsing revision lists,
 586   but doing something with them. The space efficiency therefore does
 587   not seem to justify the cost you pay in not making them easily
 588   editable.</li>
 589 </ol>
 590
 591 </div>  <!-- merge-history-footnotes -->
 592
 593 </div>  <!-- merge-history -->
 594
 595 <div class="h2" id="data-structures">
 596 <h2>Data Structures</h2>
 597
 598 <p>Merge Tracking is implemented using a few simple data
 599 structures.</p>
 600
 601 <dl>
 602   <dt>merge info</dt>
 603   <dd>An <code>apr_hash_t</code> mapping merge source paths to a range
 604   list.</dd>
 605
 606   <dt>range list</dt>
 607   <dd>An <code>apr_array_header_t</code> containing
 608   <code>svn_merge_range_t *</code> elements.</dd>
 609
 610   <dt><code>svn_merge_range_t</code></dt>
 611   <dd>A revision range, modelled using a <code>start</code> and
 612   <code>end</code> <code>svn_revnum_t</code>, which are identical if
 613   the range consists of only a single revision.</dd>
 614 </dl>
 615
 616 </div>  <!-- data-structures -->
 617
 618 <div class="h2" id="conflict-resolution">
 619 <h2>Conflict Resolution</h2>
 620
 621 <p>The <a href="func-spec.html#conflict-resolution">functional
 622 specification</a> and the <a href="../svn_1.5_releasenotes.html">1.5
 623 release notes</a> detail the command-line client behavior and conflict
 624 resolution API.</p>
 625
 626 </div>  <!-- conflict-resolution -->
 627
 628 <div class="h2" id="audit-operations">
 629 <h2>Audit Operations</h2>
 630
 631 <p>As outlined in the
 632 <a href="requirements.html#auditing">requirements and use cases</a>, merge
 633 tracking auditting is the ability to report information about merge
 634 operations.  It consists of three sections:</p>
 635
 636 <ul>
 637   <li>Changeset Merge Availability (TODO)</li>
 638
 639   <li>Find Changeset (TODO)</li>
 640
 641   <li><a href="#commutative-reporting">Commutative Author and Revision
 642   Reporting</a></li>
 643 </ul>
 644
 645 <div class="h3" id="commutative-reporting">
 646 <h3>Commutative Author and Revision Reporting</h3>
 647
 648 <p>Most of the logic for reporting will live in <code>libsvn_repos</code>, with
 649 appropriate changes to the API and additional parameters exposed to the client
 650 through the RA layer.  We are looking at an API which takes one or more paths
 651 and a revision (range?), and returns the merge info which was added or removed
 652 in that revision.  For the 'blame' case, we may also need to include some type
 653 of line number parameter, the handling of which is going to get ugly, since our
 654 FS isn't based on a weave.</p>
 655
 656 <p>Existing functions of interest are <code>svn_repos_fs_get_mergeinfo()</code>
 657 and <code>svn_fs_merge_info__get_mergeinfo()</code>.</p>
 658
 659 <div class="h4" id="audit-log">
 660 <h4><code>svn log</code> Implementation</h4>
 661
 662 <p>Prior to merge tracking, log messages had a linear relationship to one
 663 another.  That is, the only information gleaned from the order in which a
 664 message was returned was where the revision number of that message fell in
 665 relation to the revision numbers of messages preceding and succeeding it.</p>
 666
 667 <p>The introduction of merge tracking changes that paradigm.  Log messages
 668 for independent revisions are still linearly related as before, but log
 669 messages for merging revisions now have children.  These children are log
 670 messages for the revisions which have been merged, and they may in turn
 671 also have children.</p>
 672
 673 <p>The result is a tree structure which the repository layer builds as it
 674 collects log message information.  This tree structure then gets serialized
 675 and marshaled back to the client, which can then rebuilt the tree if needed.
 676 Additionally, less information needs to be explicitly given, as the tree
 677 structure itself implies revision relationships.
 678 </p>
 679
 680 <p>We currently use the <code>svn_log_message_receiver_t</code> interface
 681 to return log messages between application layers.  To enable communication
 682 of the tree structure, we add another parameter, <code>child_count</code>.
 683 When <code>child_count</code> is zero, the node is a leaf node.  When
 684 <code>child_count</code> is greater than zero, the node is an interior node,
 685 with the given number of children.  These children may also have children and
 686 indicate such by their own <code>child_count</code> parameters.  Children
 687 are returned in-band through the receiver interface immediately following their
 688 parents.  Consumers of this API can be aware of the number of children and
 689 rebuild the tree, or pass the values farther up the application stack.  In
 690 effect, this method implements a preorder traversal of the log message tree.</p>
 691
 692 <p>(For convenience, we may want to consolidate all the data parameters of
 693 <code>svn_log_message_receiver_t</code> into a single structure.)</p>
 694
 695 <p>A revision, R, is considered a <em>merging revision</em> if the mergeinfo
 696 for any path for which the log was requested changed between R and R-1.  The
 697 difference in the mergeinfo, both added revisions and removed revisions,
 698 between R and R-1 indicates the revisions which are children of R.</p>
 699
 700 <p>The exception for this is the case of a copy which is the creation of a
 701 branch.  When a branch is created, the mergeinfo for R-1 is empty, and the
 702 mergeinfo for R is 1:R-1.  In this case, the revision should not be considered
 703 a merging revision, and none of the revisions R:R-1 should be shown as R's
 704 children.</p>
 705
 706 </div>  <!-- audit-log -->
 707
 708 <div class="h4" id="audit-blame">
 709 <h4><code>svn blame</code> Implementation</h4>
 710
 711 <p>Even though the command line client doesn't consume both the original
 712 author and revision and the merging author and revision, the blame API should
 713 provide both for use by other clients.</p>
 714
 715 </div>  <!-- audit-blame -->
 716
 717 </div>  <!-- commutative-reporting -->
 718
 719 </div>  <!-- audit-operations -->
 720
 721 <p>$Date$</p>
 722
 723 </div>  <!-- h1 -->
 724 </body>
 725 </html>