[PROPOSAL] Merging Improved

Hi,

Attached is a pdf file with examples. I'll refer to them
in this email. Doing the same diagrams in ascii art can be
done, but it isn't pretty ;).

For the sake of this discussion I'm ignoring cherry picking
for now. I will mention something in the bookkeeping section,
but am not going into details on how to use that information
as of yet.

The goal of this proposal is to come up with a scheme that will
make the:

  svn merge URL .

syntax do something usefull. That is, merge the changes between
URL and WC URL, since you last ran this command, into your working
copy.

For sake of simplicity I'm leaving the handling of tree deltas out
of this proposal. This being resemblant to textual merging to
a degree.

-------
Merging will rely heavily on variance adjusting. Prior discussions
have questioned it's safety, but that is beyond the scope of this
proposal. Lets assume we allow the user enough rope to macrame
a castle with in which they can then hang themselves.

When merging from one branch to another, we need 4 files:

  1) the working copy, from now on referred to as Modified(M}.
  2) the latest version of a branch, from now referred to as Latest(L).
  3) the most recently merged revision(MRMR) of said branch.
  4) the most recent common ancestor(MRCA) of L and M.

After a merge we end up with an altered working copy(WC).

When MRCA is absent we currently need to punt since we need
to figure out how to handle that case.

When MRCA == MRMR (or MRMR is absent), we can use our current
internal merge. This will be (mostly) equivalent to
diff3 -mE M MRCA L. I'll refer to this function as diff3 in the
examples.

When MRCA != MRMR, we use variance adjusted merging. This is based
on an algorithm described at:

  http://subversion.tigris.org/variance-adjusted-patching.html

Basically you obtain a diff between MRMR and L, adjust that using
the diffs between MRCA and MRMR, and MRCA and M, then apply it
to M. This has been implemented in the internal diff library
as diff4 (untested). I'll refer to this function as diff4 in
the examples.

On each merge we need to do some bookkeeping (which we will rely
on to do merges aswell). All bookkeeping operations are on the
[TBD: svn:merged-from ?] property of each merged file in the WC.

Each line in this property will have the following syntax:

  [REPOSITORY-UUID::]PATH@REVISION[:REVISION]

The REPOSITORY-UUID is to be left out when it is the same as the
one M belongs to. The REVISION:REVISION syntax is to accomodate
for cherry picking.

There will be no two lines in svn:merged of the
[REPOSITORY-UUID::]PATH@REVISION syntax where the [REPOSITORY-UUID::]PATH
parts are the same. This line will be called the MRMR line.

There will be no lines in svn:merged where the [REPOSITORY-UUID::]PATH
is the same and the REVISION is < as REVISION in the MRMR line.

There will also be no lines in svn:merged where PATH is equal to
the path of M in the repository.

Given these rules it is always possible to determine the MRMR, it will
retain full merge history (since properties are versioned) and the size
of the property contents will not grow unbounded.

Note that the MRCA was already recoverable since this information is
recorded on copy.

Now what should 'svn merge BRANCH' do? In my opinion it should try
to apply the changes between BRANCH@MRMR (or MRCA when MRMR is absent)
and BRANCH@HEAD to my working copy.

------
The examples are easy to read. The rounded rectangles represent a
revision. The vertical line they're in present their path. Arrows
represent transitions to the next revision. The grey blocks are the
merged-from properties. We make the assumption that the working
copies are unmodified prior to a merge so that it always is the
same as the revision is was checked out as. Furthermore we assume
that the working copy is committed after the merge.

Example 1.

Note that Branch1 is copied from Trunk at revision 17, therefor:
MRCA = Trunk@17 == Branch1@18. Since there are no more copies in this
example this will remain the same for the entire example.

M1. MRCA = Trunk@17 = Branch@18
     MRMR is absent
     M = Branch@19
     L = Trunk@20
     WC = Branch@21

This results in WC = diff3(M, MRCA, L). A line is added to svn:merged-from
of WC:

  Trunk@20.

M2. MRCA = Trunk@17 = Branch@18
     MRMR = Trunk@20
     M = Branch1@21
     L = Trunk@23
     WC = Branch1@24

This results in WC = diff4(M, MRCA, L, MRMR). The line in svn:merged-from
of WC is updated to:

  Trunk@23

M3. MRCA = Trunk@17 = Branch@18
     MRMR is absent
     M = Trunk@23
     L = Branch1@25
     WC = Trunk@26

This results in WC = diff3(M, MRCA, L). Note that this shouldn't be a
problem since diff3 is perfectly capable of identifying common changes
(the ones merged from Trunk to Branch earlier), and these should therefor
not render any conflicts. The svn:merged-from property from L is merged
into the one on WC, after which all 'Trunk' lines will be removed
(rendering it empty). Then the following line is added:

  Branch1@25

I'll leave the second and third example for tomorrow, since I'm out of
time for today.

Hopefully this was an interesting read. Not truly a well written
proposal, but there you go.

Sander

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org