The Hackerlab at `regexps.com`

## Star Topology Branching and Merging

up: arch next: Writing Log Entries for Merges prev: Patch Logs and ChangeLogs

A common way to use branches is to form a star topology. At the center is a 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 `GNU emacs` :

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

When using a star topology, developers make changes on the branches, merging those changes into `emacs-main` at significant milestones. Periodically, they merge the collected changes on `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 `emacs-main` multiple times, and `emacs-main` with each branch several times. In such situations, simple `update` and `replay` are inadequate for performing merges.

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

### The Star Topology Merge Problem

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

            emacs--main                     emacs--display
            -----------                     --------------
                 A-0  --------------------> B-0 (a tag)
                 A-1                        B-1
                 A-2          ,-----------> B-2 (merge w/ A-1..3)
                 A-3  --------              B-3
                 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

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

            % larch update --in-place --dir WD emacs--display

modifies WD such that:

            WD := delta(B-4, WD) [B-8]

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

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

We can't use `replay` either:

            % larch replay --in-place --dir WD emacs-display

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

### 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:

            WD := delta (A-7, B-8) [WD]

If we want to give precedence to the changes in `emacs--display` , we can perform the merge by computing:

            WD := delta (A-7, WD) [B-8]

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

            tmp :=  delta (A-7, B-8) [A-8]
            WD := delta (A, WD) [tmp]

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

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

            1:      WD := delta (A-7, A-8) [WD]

            2:      tmp := delta (A-7, A-8) [B-8]
                    WD := delta (B-8, WD) [tmp]

            3:      WD := delta (A-7, WD) [A-8]
                    (this is an ordinary `update')

In the two two-step solutions, legitimate conflicts can occur while building the `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.

### The star-merge Command

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

            % larch star-merge [--in-place] A B C [output-dir]

where `A` , `B` , and `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 `./` ).

With the `--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 (`output-dir` ).

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

If the merge requires two steps, and conflicts occur in the first step, `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:

            % larch star-merge --finish [directory]

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

arch: The arch Revision Control System
The Hackerlab at `regexps.com`