subversion-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache subversion Wiki <comm...@subversion.apache.org>
Subject [Subversion Wiki] Update of "SymmetricMerge" by JulianFoad
Date Mon, 16 Apr 2012 16:53:21 GMT
Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Subversion Wiki" for change notification.

The "SymmetricMerge" page has been changed by JulianFoad:
http://wiki.apache.org/subversion/SymmetricMerge?action=diff&rev1=83&rev2=84

Comment:
Fill in Symmetric Merge Algorithm

  
  We call the result a ''symmetric merge'' algorithm.
  
- == The Symmetric Merge Algorithm ==
  In V1.7 we have ''sync'' which looks for a base on the source branch, and ''reintegrate''
which looks for a base on the target branch.  What we need is a single algorithm that finds
the most recent base, on either branch.  Like the V1.7 ''reintegrate'', it needs to choose
a base for the 3-way merge, and potentially a different base (this one always on the source
branch) for the mergeinfo to be recorded.
  
  Considering the final merge in the "sync after reintegrate" graph (repeated from above),
we have:
@@ -244, +243 @@

  
  End of longest continuous prefix of source branch is A1, so that's the mergeinfo base to
use.
  
- To express it as an algorithm:
+ == Symmetric Merge Algorithm ==
+ This algorithm provides a symmetric merge with skipping of source revisions that have already
been cherry-picked to the target branch.
+ 
+  1. Find the latest rev of A synced to B and of B synced to A.
+  1. Choose a base.
+  1. Identify cherry-picks.
+  1. Break into 3-way merges, skipping the cherry-picks.
+  1. Perform the 3-way merges and mergeinfo addition.
+ 
+ In more detail.
  
   1. Find the latest revision of A synced to B and the latest revision of B synced to A.
+ 
-   * This means, for the A to B direction, the youngest revision 'rN' on A at which all revisions
of A, up to and including rN, are now recorded as having been merged into B.  And "now recorded"
means recorded in the version of B that is being used as the merge target.  Usually the result
corresponds to the most recent merge into B from A, but not necessarily, because later revisions
from A might previously have been cherry-picked into B.
+   * This means, for the A to B direction, the youngest revision 'rN' on A at which all revisions
of A, up to and including rN, are now recorded as having been merged into B. And "now recorded"
means recorded in the version of B that is being used as the merge target. Usually the result
corresponds to the most recent merge into B from A, but not necessarily, because later revisions
from A might previously have been cherry-picked into B.
+ 
-   * We consider only direct A <-> B mergeinfo.  (Consideration of a merge graph extending
to other branches is future work. Since we record mergeinfo transitively, considering only
direct A<->B mergeinfo already suffices for some 3-branch scenarios too, but not all
such scenarios.)
+   * We consider only direct A <-> B mergeinfo. (Consideration of a merge graph extending
to other branches is future work. Since we record mergeinfo transitively, considering only
direct A<->B mergeinfo already suffices for some 3-branch scenarios too, but not all
such scenarios.)
+  {{{
+     In:
+         A_tip: pathrev
+         B_wc:  wc-abspath
+         (Note: B is a WC "actual" tree including any local mods.)
+ 
+     Out:
+         A_base: pathrev
+         B_base: pathrev
+         (Note: B_base can't possibly be B if B has local mods.)
+ 
+     Implementation:
+         Currently:
+             find_base_on_source()
+             find_base_on_target()
+         TODO: fill in the details here and re-visit the implementation.
+ }}}
+ 
-  1. Choose a base.
+  2. Choose a base.
+ 
    * Choose the latest revision of A synced to B or the latest revision of B synced to A.
+ 
    * Each candidate base is a common ancestor of the source and target, if ancestry means
following either the direct line of descent or the arrows that indicate complete merges.
+ 
    * Choose the 'more recent' one in some sense -- be it time of commit, or number of changes
since then, or some other measure.
+ 
    * [TODO] In what cases do the selection methods give different results? Only after a criss-cross
merge?
+  {{{
+     In:
+         A_base: pathrev
+         B_base: pathrev
+ 
+     Out:
+         base: pathrev
+ 
+     Implementation:
+         Currently, in find_symmetric_merge():
+             (A_base->rev > B_base->rev) ? A_base : B_base
+ }}}
+ 
-  1. Identify cherry-picks.
+  3. Identify cherry-picks.
+ 
    * Find changes along the source side of the merge that are already 'in' the target.
+ 
-   * Look for merges in both directions (from current source to current target ("forward")
and from current target to current source ("backward").  For each merge:
+   * Look for merges in both directions (from current source to current target ("forward")
and from current target to current source ("backward")). For each merge:
+ 
+     * Break down the merge into its component logical changes.
+ 
-    * If a merge consists entirely of logical changes that are not in the target, or consists
entirely of logical changes that are in the target, treat it as a unit -- a cherry pick.
+     * If the merge consists entirely of logical changes that are not in the target, or consists
entirely of logical changes that are in the target, treat it as a unit -- a cherry pick.
+ 
-    * Otherwise, fall back to the user: report to the user which logical changes that merge
includes, and suggest that the user run more specific merges that pull only the subset of
logical changes they want.
+     * Otherwise, fall back to the user: report to the user which logical changes that merge
includes, and suggest that the user run more specific merges that pull only the subset of
logical changes they want.
+ 
+  3a. Create an (implicit or explicit) list of indivisible changes
+      along each side of the merge, since the BASE.
+  {{{
+     For example:
+ 
+           Source side           Target side
+           B@10:A@15             B@10:B@11  (B@10 is BASE)
+           A@15:A@20             B@11:B@12
+           ...                   ...
+           A@26:A@27             B@29:B@30
+                                 B@30:B_wc  (B@30 is B_wc's origin)
+ 
+     In:
+         base
+         A_tip
+         B_wc
+ 
+     Out:
+         A_changes: a list of (URL1@REV1 : URL2@REV2) pairs?
+                 Or, more compactly, BASE plus a list of REVs
+                 that index into the branch history?
+         B_changes: the same
+ 
+     Note: The first change in one of the lists might be a cross-branch
+         change (from 'BASE' on the target branch to 'MID' on the source
+         branch), whereas all subsequent changes are changes along a
+         branch.
+ 
+     Note: The B_changes output needs to be able to represent B_wc as
+         its end point, implicitly or explicitly.
+ 
+     Note: These lists need to reference changes in such a way that we
+         can fetch and examine the changes, at least in terms of their
+         mergeinfo and whether they're operative.
+ 
+     TODO: Should the outputs identify each individual change (revision)
+         as operative or inoperative, or is it acceptable to output
+         revisions (or ranges of revs) that are not all known to be
+         operative?
+ }}}
+ 
+  3b. Discover the changes from A that have been merged to B since BASE.
+  {{{
+     In:
+         A_changes
+         B_changes
+ 
+     Out:
+         A_changes_to_skip: a subset of A_changes
+         A_changes_to_warn: a subset of A_changes
+ 
+     Implementation phase 1:
+ 
+     This detects direct cherry-picks in the same direction as the
+     present merge, which is all that Subversion 1.7 supports.
+ 
+     Fetch mergeinfo on B_wc; note any changes from A that are recorded
+     as merged to B (since BASE, and directly) as "already on B".
+ 
+     Implementation phase 2:
+ 
+     This adds detection of cherry-picks in the opposite direction,
+     which is new functionality.
+ 
+     For each change in A_changes:
+         Fetch the mergeinfo change.
+         If the mergeinfo did change (it represents a merge into A):
+         If that merge was a direct merge from B, and from nowhere
+         else, add this A change onto A_changes_to_skip.  If that is,
+         instead, a merge from both B and other sources, then add this
+         A change onto A_changes_to_warn.
+ 
+     Add this to the phase 1 results for A->B.
+ 
+     Note: If the first change is a BASE:MID cross-branch change, it
+     must first be turned into the equivalent series of source-side
+     changes, which is a non-trivial exercise.
+ 
+     Implementation phase 3:
+ 
+     This detects both direct and indirect (that is, via a third
+     branch) cherry-pick merges, in both directions.  This is more
+     complex, and a simple implementation of it may run slowly in
+     some scenarios.
+ 
+     For each change in A_changes:
+         Fetch the mergeinfo change.
+         If the mergeinfo did change (it represents a merge into A),
+         break down that merge into its component logical changes,
+         else take this change on A as the logical change to test.
+         See if those logical changes are already on B.
+         If all of those logical changes are on B, add this A change
+         onto A_changes_to_skip; if some of them are on B, add this
+         A change onto A_changes_to_warn.
+ }}}
+ 
-  1. Break into 3-way merges, skipping the cherry-picks.
+  4. Break into 3-way merges, skipping the cherry-picks.
+  {{{
+     Implementation:
-  1. Mergeinfo addition.
-   * The first 3-way merge might have its base on the target branch.
-   * If base is on source branch, a normal mergeinfo addition.
-   * If base is on target branch, mergeinfo += "all source revs up to N".
-   * [[danielsh: should the last two steps be: for (each 3-way-merge) { perform the merge;
add corresponding mergeinfo; } --- that is, add the mergeinfo for each of the 3-way-merges
as soon as that merge is done, rather than (or in addition to) adding the collective mergeinfo
at the end?]]
  
- == Symmetric Merge with Cherry-Picks ==
- Next,  we need to account for cherry-picks.  If there are cherry-picks from  the source
[...], we look for the end of the first gap.  [TODO...]
+         # Define a merge as (base, tip, target).
+ 
+         merges = [(BASE, A_tip, B_wc)]
+         for change in A_changes_to_skip:
+             m = find change.rev in merges
+             replace [m] with [
+                 (m.base, change-1, m.target),
+                 (change, m.tip, m.target) ]
+             # elide either or both of those if they are no-ops
+ }}}
+ 
+  5. Perform the 3-way merges and mergeinfo addition.
+  {{{
+     Implementation:
+ 
+         for m in merges:
+             three_way_merge(m.base, m.tip, m.target)
+             if m.base is on A:
+                 do a normal mergeinfo addition
+             else:
+                 mergeinfo += (all source revs from YCA(?) up to m.tip)
+ }}}
  
  == Symmetric Merge with Criss-Cross Merge ==
  The following kind of merge history is known as a 'criss-cross' merge.

Mime
View raw message