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.
