@need 3200

@node Star Topology Branching and Merging
@chapter Star Topology Branching and Merging

@geindex star topology branching and merging

@geindex branching and merging, star topology



A common way to use branches is to form a star topology.  At the
center is a @geindex trunk
@dfn{trunk} or "primary development path".  A number of
branches form a "star" around the trunk.  There might be one branch
for each developer or sub-team; one branch for each large task; one
branch for each change reviewer; one branch for each category of
tasks, etc.  Here's a (fictional) example of using a star topology to
work on various aspects of @code{GNU emacs}:

@example
@group
      emacs--display               emacs--intl
        (for hacking on              (for lisp-level character-set
         display features)            support)
                    \             /
                     \           /    
@end group
@group
                      emacs--main (the trunk)
@end group
@group
                     /           \
                    /             \
            emacs--bugs          emacs--guile
              (for simple bug      (for preparing to use
                fixes)                  Guile Scheme)
@end group
@group
@end group
@end example

When using a star topology, developers make changes on the branches,
merging those changes into @code{emacs-main} at significant milestones.
Periodically, they merge the collected changes on @code{emacs-main} back to
the development branches.  The trunk is the official development
sources.  Work takes place on the branches, and the developers use the
trunk to stay in-sync.


This results in a situation where each branch has merged with
@code{emacs-main} multiple times, and @code{emacs-main} with each branch several
times.  In such situations, simple @code{update} and @code{replay} are
inadequate for performing merges.


This chapter illustrates the problem with using @code{update} and @code{replay}
for merging in a star topology, explains the solution in general
terms, and finally presents @code{star-merge}, a command that implements
the solution.

@need 3200

@section The Star Topology Merge Problem

Consider the trunk and one of its branches after several revisions and
merges on each:

@example
@group
        emacs--main                     emacs--display
        -----------                     --------------
             A-0  --------------------> B-0 (a tag)
             A-1                        B-1
             A-2          ,-----------> B-2 (merge w/ A-1..3)
@end group
@group
             A-3  --------              B-3
@end group
@group
             A-4          ,------------ B-4
  (merge w/  A-5  <-------              B-5
   B-0..4)   A-6          ,-----------> B-6 (merge w/ A-4..7)
             A-7  --------              B-7
             A-8                        B-8
@end group
@group
@end group
@end example

Now, suppose we have a working directory that was checked-out from
@code{A-8} and perhaps contains local modifications.  Our goal is to merge
@code{B-8} with that working directory, giving a revision that is up-to-date
with both branches and that includes any local changes.

@example
@group
        % larch update --in-place --dir WD emacs--display
@end group
@group
@end group
@end example

@noindent
modifies WD such that:

@example
@group
        WD := delta(B-4, WD) [B-8]
@end group
@group
@end group
@end example

Well, what has changed in @code{WD} since @code{B-4}?  @code{B-4} was up-to-date up
to @code{A-3}, but @code{WD} contains additional changes from @code{A-4..A-8} -- all
of those changes are included in the delta computed by @code{update}.


@code{update} applies that delta to @code{B-8}.  Unfortunately, @code{B-8} already
includes the changes in @code{A-4..7} -- so conflicts are guaranteed.


We can't use @code{replay} either:

@example
@group
        % larch replay --in-place --dir WD emacs-display
@end group
@group
@end group
@end example

@noindent
tries to apply all the patches missing from @code{B}.  For @code{WD}, those
patches are @code{B-5..B-8}.  Unfortunately, patch @code{B-6} includes all the
changes from @code{A-4..7} (perhaps with additional changes or conflict
resolutions).  @code{WD} already has all of those same changes, so again,
conflicts are guaranteed.




@need 3200

@section Solving the Star Topology Merge Problem

In the case of the example above, there are three reasonable ways to
solve the merge problem, depending on the relative precedence we want
to give the two development paths and the working directory.


If we want to give precedence to the changes already in the working
directory, we can perform the merge by computing:

@example
@group
        WD := delta (A-7, B-8) [WD]
@end group
@group
@end group
@end example

If we want to give precedence to the changes in @code{emacs--display}, we
can perform the merge by computing:

@example
@group
        WD := delta (A-7, WD) [B-8]
@end group
@group
@end group
@end example

Finally, we might want to merge in two steps: first merging
@code{emacs--display} with @code{A-8} (giving precedence to @code{emacs--display}),
then adding the local changes of @code{WD} to that:

@example
@group
        tmp :=  delta (A-7, B-8) [A-8]
        WD := delta (A, WD) [tmp]
@end group
@group
@end group
@end example

There are in fact six different ways of precedence-ordering the two
branches and @code{WD} however one of the above solutions works for each
of the six possibilities.


Three different solutions are needed if @code{WD} was checked out from
@code{emacs--display} and our goal is to merge in changes from
@code{emacs--main.}  These are:

@example
@group
        1:      WD := delta (A-7, A-8) [WD]
@end group
@group
@end group
@end example
@example
@group
        2:      tmp := delta (A-7, A-8) [B-8]
                WD := delta (B-8, WD) [tmp]
@end group
@group
@end group
@end example
@example
@group
        3:      WD := delta (A-7, WD) [A-8] 
                (this is an ordinary `update')
@end group
@group
@end group
@end example

In the two two-step solutions, legitimate conflicts can occur while
building the @code{tmp} tree: its necessary to resolve such conflicts by
hand before performing the second step.


Suitably abstracted, those six merge techniques are sufficient to
solve all star topology merging problems with a choice of branch and
local change precedence without generating any spurious merge
conflicts.




@need 3200

@section The star-merge Command

@geindex star-merge



The @code{star-merge} command figures out how to solve a star topology
merge problem and performs the merge.  Its syntax is:

@example
@group
        % larch star-merge [--in-place] A B C [output-dir]
@end group
@group
@end group
@end example

@noindent
where @code{A}, @code{B}, and @code{C} are the names of two branches and a working
directory (in any order).  (If your working directory name can be
mistaken for a branch name, and most of them can, you should prefix
the directory name with @code{./}).


With the @code{--in-place} option, the working directory is directly
modified or else completely replaced with the result.  Otherwise, the
merge is stored in a new directory (@code{output-dir}).


The order of arguments determines the precedence of changes.  @code{A}, @code{B}
and @code{C} have a comman ancestor revision -- call it @code{X}.  The order of
arguments means (conceptually): start with revision @code{X}, add the
changes from @code{A}, then the changes from @code{B}, then the changes from
@code{C}.  The specific ordering of changes determines, when there are
conflicts, which branch's code is automatically encorporated, and
which is left as @code{.rej} files.


If the merge requires two steps, and conflicts occur in the first
step, @code{star-merge} will stop after the first step leaving the output
directory in an intermediate state.  After fixing the conflicts, you
can complete such a merge with:

@example
@group
        % larch star-merge --finish [directory]
@end group
@group
@end group
@end example

@strong{NOTE:}  In the current release, there is a limitation on star merge.
Suppose that @code{B} is a branch of @code{A} and that @code{B} and @code{A} have never
been previously merged.  In order to merge them, you must use a
working directory checked out from @code{B} (the branch version) not from
@code{A} (the branched-from version).  This restriction will be removed in
the next release.







