Branch Tree Version Control
***************************

Pastwatch stores the repository in the form of a Branch Tree. This chapter describes the concepts behind branch trees and how users interact with branch trees in Pastwatch.

Version Inheritance and Branches
================================

The branch tree consists of nodes and edges.  Each node in the branch tree represents a version of the project.  Each version has a version address and a version tag.

Each time a project member commits changes to the project files, Pastwatch appends a new leaf version to the branch tree.  The new leaf version points back to the version it was derived from.  These pointers are parent pointers and they are the edges in the branch tree. Here is a simplified illustration of a branch tree:

In this example, version A is the first version of the project files.  A project member committed some changes, so Pastwatch appended version B.  Later, versions C and D were committed to the repository.

The path from one leaf node to the root is called a branch.  In this example, the leaf is version D and the root is version A.  Version D is the most recent version in the branch, so it is called the branch head or just head.  Each branch has a branch tag, which is an English description of the branch. The branch tag for the default branch is init.  Pastwatch names each branch by its head, so the example is called Branch D.

To see a more detailed description of the branch tree, you can read the output from the past history command:

     1    % past history
     2    pastwatch: Using branch: init
     3    pastwatch: Using branch head: +xABp8t+6z57+HOk9m2GGXhrsrE
     4    branch: head: yipal@sweat:4, tag: init
     5    ----------------------------
     6    Version: yipal@sweat:4 (+xABp8t+6z57+HOk9m2GGXhrsrE)
     7    date: 06/10/05 13:32:59
     8    add the main function
     9    ----------------------------
     10   Version: yipal@sweat:3 (lo-KJ2RsZxLwjvAVdBtP7Xagn1k)
     11   date: 06/10/05 13:25:44
     12   Add description of project in README
     13   ----------------------------
     14   Version: yipal@sweat:2 (kWkDyn7n00lRaUqMYmhelBDLBh8)
     15   date: 06/10/05 13:24:34
     16   Initial Import
     17   ----------------------------
     18   Version: (+0-rOo6g6U26yI6Jgymv5KDGEfY)
     19   date: 06/10/05 13:21:10
     20   *** empty log message ***

past history reports information about a particular branch in the branch tree.  The first few lines of output report some details about the branch being inspected.  Line 2 reports that Pastwatch is reading from branch init.  Line 4 reports that the head of branch init is a version tagged with: yipal@sweat:4.

The rest of the output is divided into multiple sections.  Each section describes one version in the branch.  Lines 6-8 describe the most recent version.  This version has the version tag yipal@sweat:4 and the version address: +xABp8t+6z57+HOk9m2GGXhrsrE.  The version was created at 13:32:59 on 06/10/05.  The user comment for the commit is: "add the main function".  The next three sections describe the other versions in the branch in reverse chronological order.

Tracking Branches
-----------------

Each Pastwatch working copy is derived from a base branch tree version.  We say that the working copy is tracking the branch that contains the base version.

Each time the user updates his working copy, Pastwatch retrieves any new versions that extend the branch being tracked.  Pastwatch applies the changes to the working copy and then changes the base version to the new branch head.

Each time the user commits a version to the branch tree, the new version is appended to the working copy's base version.  Pastwatch tries to update the working directory before appending the new version.

Forks
=====

Branch tree versions each point back to their parent.  If two versions point to the same parent, then we say the branch forked into two different branches (because there are two different heads).  The following figure illustrates a fork:

In the example, both versions C and E are descendants from the same parent version B.  The branch tree now contains two branches: branch D and branch E.

A version in one branch will not contain changes from another branch because it is not a descendant of the other version.  In the example above, Versions C and D do not contain the revisions committed in version E.  Likewise, version E does not contain the changes made in versions C and D.

The past latest command will report a project's active branches. In this example, it reports:

          % past latest
          pastwatch: Using branch: init
          pastwatch: Using branch head: +xABp8t+6z57+HOk9m2GGXhrsrE
          branch "init": head is +xABp8t+6z57+HOk9m2GGXhrsrE
          branch "yipal@sweat:bugfixes": head is WKzv-UdmbCxv1Tv0dfQ+JPig-xY

This branch tree has two branches.  One has the default branch tag init and the other has the branch tag yipal@sweat:bugfixes.  To see more about the yipal@sweat:bugfixes branch, we can run past history on it:

          % past -b yipal@sweat:bugfixes history
          pastwatch: Using branch head: WKzv-UdmbCxv1Tv0dfQ+JPig-xY
          branch: head: yipal@sweat:5, tag: yipal@sweat:bugfixes
          ----------------------------
          Version: yipal@sweat:5 (WKzv-UdmbCxv1Tv0dfQ+JPig-xY)
          date: 06/13/05 09:12:52
          Create a separate branch for fixes
          ----------------------------
          Version: yipal@sweat:2 (kWkDyn7n00lRaUqMYmhelBDLBh8)
          date: 06/10/05 13:24:34
          Initial Import
          ----------------------------
          Version: (+0-rOo6g6U26yI6Jgymv5KDGEfY)
          date: 06/10/05 13:21:10
          *** empty log message ***

This output shows that yipal@sweat:bugfixes forks from the init branch at version yipal@sweat:2.  The head of yipal@sweat:bugfixes is yipal@sweat:5.

Tracking a Different Branch
---------------------------

Pastwatch will track the init branch by default.  To make Pastwatch track a different branch, a user must call past -b <branch_specifier> update.  This command tells Pastwatch to track the branch specified by <branch_specifier>.  This command is sticky, so Pastwatch will continue to use <branch_specifier> until the user explicitly changes it again.

          % past -b yipal@sweat:bugfixes update
          pastwatch: Using branch yipal@sweat:bugfixes
          pastwatch: Using branch head WKzv-UdmbCxv1Tv0dfQ+JPig-xY
          pastwatch: updating .
          Merging changes into main.c
          P main.c
          Merging changes into README
          P README
          pastwatch: updating util

Explicit Branches
=================

One or more project members can explicitly create a fork to isolate their work from the other members.  An example use for forking is code maintenance.  In the following example, the project releases version 1.0 of its software and the main developers start work on the version 2.0 in the main development branch.  A separate team of maintenance developers create a separate branch for fixing bugs in version 1.0.  The maintenance developers work in the maintenance branch which does not interfere with the main development branch.  Here is an illustration showing the main branch and the separate maintenance branch:

Creating an Explicit Branch
---------------------------

To create an explicit branch, use the past branch command with the -B option.  The full command is:

          past branch -m <msg> -B -f <from_version> -B <new_branch_tag>

This command will create an new explicit fork in the branch tree.  The branch will be a descendant of from_version and will have the branch tag new_branch_tag.  To create the example branch in Section 5.2 a project member would call:

          % past branch -B -f yipal@sweat:2 -b bugfixes -m "Create a separate branch for fixes"
          pastwatch: Using branch: init
          pastwatch: Using branch head: kWkDyn7n00lRaUqMYmhelBDLBh8
          pastwatch: committing
          pastwatch: new snapshot: 1qBut86jDe-1eFN3dzwqgsxZ8O8, 0 deltas. For commit record: 6xMF+UwdAjxWeFJnYEYH5Ht3Hvk

Pastwatch will ignore the explicit branch unless a project member explicitly tells Pastwatch to track the branch.  The past branch command will not change which branch any user is tracking, including the project member that creates the branch.  If a user wants to track the new branch, he must explicitly switch to the new branch using the past -b <branch_specifier> update command.

Implicit Branches
=================

A branch tree can also implicitly fork if a project member commits a new version to a stale copy of the branch tree.  This may occur because Pastwatch will allow a user to commit a new version to their local branch tree replica while he is disconnected from the other project members.  If two users each commit a new version to their branch tree replicas without sharing the new versions with each other, the new versions will have the same parent.  Here is what Pastwatch will report if the user (Bob) commits while disconnected:

          bob% past commit -m "Write a printer function"
          pastwatch: Using branch: init
          pastwatch: cannot connect to any DHT host
          pastwatch: Using branch head: +xABp8t+6z57+HOk9m2GGXhrsrE
          pastwatch: cached pubkey block is more recent, no need to fetch
          pastwatch: dht insert failed (20): kqTffWr-E6ZPpyfLVP7L8neuolQ, sync later
          pastwatch: cached pubkey block is more recent, no need to fetch
          pastwatch: checking for updates and conflicts
          pastwatch: updating .
          M main.c
          pastwatch: committing in .
          Committing main.c
          pastwatch: dht insert failed (20): UjP61-nDKDK6pw4EiXyTQOuljsE, sync later
          pastwatch: committing
          pastwatch: dht insert failed (20): ZF1tN6VOS17BFq7fqvq0WFaxJIc, sync later
          pastwatch: dht insert failed (20): kqTffWr-E6ZPpyfLVP7L8neuolQ, sync later
          pastwatch: new snapshot: L7JR2fwwhzadAFd8Zf4XEOLcAlw, 1 deltas.  For commit record: ZF1tN6VOS17BFq7fqvq0WFaxJIc

After Bob reconnects to the network, he needs to synchronize his replica with Aqua using the past sync command:

          bob% past sync
          pastwatch: cached pubkey block is more recent, no need to fetch
          pastwatch: stale pk kqTffWr-E6ZPpyfLVP7L8neuolQ
          pastwatch: ZF1tN6VOS17BFq7fqvq0WFaxJIc: not in DHT
          pastwatch: 0Q8GJrKI2arWmFRTSmJRM42EvLQ is in a known log
          pastwatch: inserting ZF1tN6VOS17BFq7fqvq0WFaxJIc's blocks
          pastwatch: delta inserted: gQMF6e6BfC7EuC8Et817FV67XAE
          pastwatch: copying pk kqTffWr-E6ZPpyfLVP7L8neuolQ

The following illustration depicts what happens if Alice commits version C and Bob commits version D, while Bob is disconnected from the network (a).

Now, when Alice updates her working copy, she will discover that both versions C and D have the same parent.  The merged replicas are shown in (b).  The new branches also share the same branch tag: init.  Pastwatch reports the branch like this:

          alice% past up
          pastwatch: Using branch: init
          pastwatch: Using branch head: 378KIM3-xP9jl7+lyrU0Hzu0oSE
          pastwatch: Branch "init" has forked.  You must specify a branch head to track with the -b option.
          pastwatch: cannot find a branch to use. current branches are (B):
          pastwatch: branch "init": head is 378KIM3-xP9jl7+lyrU0Hzu0oSE
          pastwatch: branch "init": head is ZF1tN6VOS17BFq7fqvq0WFaxJIc

At first glance, implicit forks may appear confusing because they allow project members to commit changes even though the changes might not be visible to the other members immediately.  This seems confusing because there is no latest version of the project files.  Instead, there could be multiple branches that each have a different latest version.

Actually, implicit branches already exist in other versioning systems such as CVS.  In CVS, each project member essentially creates a fork in their working directory whenever they change their working copy.  The branch is then reconciled into the main branch when the user commits the changes.

Pastwatch differs because it records these forks.  When a project member commits a change while disconnected from Aqua, he records his changes to a local branch.  If the member synchronizes with Aqua before another member places a new version into Aqua, Pastwatch will automatically append the local branch to the main branch.

Tracking with Implicit Branches
-------------------------------

If a Pastwatch user is tracking a branch and the branch forks implicitly, then Pastwatch will notify the user that the fork appeared during the user's next past update.  Pastwatch will ask the user to specify one branch to track.

Pastwatch notifies users when a fork occurs so that the users can promptly reconcile the fork if they want to.  If the users do not want to reconcile the fork, they can use pastwatch with the  -i option to ignore implicit branches that do not affect the branch Pastwatch is tracking.

Fork Reconciliation
===================

Leaving a fork in the branch tree will allow the project files to follow two potentially different development paths.  This is desirable for explicit branches but is not desirable when project members want to jointly work on the project files.

To reconcile two branches into a single branch, a project member must add the changes from the first branch into the second branch, and then terminate the first branch.  The result is a single branch that contains the changes from both branches.

In many cases, Pastwatch can automatically incorporate the changes from one branch into the other.  This way, the user only needs to issue a few simple past commands to reconcile the branches.  If the two branches contain changes that conflict directly, the user will need to resolve the conflicts manually.

A project member reconciles two branches (378KIM3-xP9jl7+lyrU0Hzu0oSE and ZF1tN6VOS17BFq7fqvq0WFaxJIc) by first updating her working copy to the head of her branch (378KIM3-xP9jl7+lyrU0Hzu0oSE).  She then calls past -b <my_branch> merge -t <other_branch> to merge the changes from the other branch into her working copy:

          alice% past -b ZF1tN6VOS17BFq7fqvq0WFaxJIc history
          pastwatch: Using branch head: ZF1tN6VOS17BFq7fqvq0WFaxJIc
          branch: head: bob@workstation:2, tag: init
          ----------------------------
          Version: bob@workstation:2 (ZF1tN6VOS17BFq7fqvq0WFaxJIc)
          date: 06/13/05 13:30:27
          Write a printer function
          ----------------------------
          Version: alice@laptop:2 (0Q8GJrKI2arWmFRTSmJRM42EvLQ)
          date: 06/13/05 13:17:41
          Initial import
          ----------------------------
          Version: (cYFMmHCr8Ocugifc+UkumAp+K30)
          date: 06/13/05 13:13:32
          *** empty log message ***

          alice% past -b 378KIM3-xP9jl7+lyrU0Hzu0oSE merge -t bob@workstation:2
          pastwatch: Using branch head 378KIM3-xP9jl7+lyrU0Hzu0oSE
          pastwatch: updating .
          Merging changes into main.c
          M main.c: different from alice@laptop:3

There there were conflicts between Alice's and Bob's changes, she would resolve those conflicts now.  After the merge, Alice's working copy contains the changes from Bob's branch.

          alice% past -b 378KIM3-xP9jl7+lyrU0Hzu0oSE diff main.c
          pastwatch: Using branch head: 378KIM3-xP9jl7+lyrU0Hzu0oSE
          File: main.c
          ===============================================
          diff -t alice@laptop:3 main.c
          2a3,6
          >
          > void print(char* s) {
          >   printf("%s", s);
          > }

Alice can then commit Bob's changes to branch 378KIM3-xP9jl7+lyrU0Hzu0oSE

          alice% past -b 378KIM3-xP9jl7+lyrU0Hzu0oSE commit -m "Merge changes from bob@workstation:2"
          pastwatch: Using branch head: 378KIM3-xP9jl7+lyrU0Hzu0oSE
          pastwatch: checking for updates and conflicts
          pastwatch: updating .
          M main.c
          pastwatch: committing in .
          Committing main.c
          pastwatch: committing
          pastwatch: new snapshot: 6B-zLsJi1PXNjJW-Mlhz1lABoGU, 1 deltas

Finally, Alice can terminate branch ZF1tN6VOS17BFq7fqvq0WFaxJIc with past branch -k so that Pastwatch can ignore it during future operations.

          past -b ZF1tN6VOS17BFq7fqvq0WFaxJIc branch -k -m "Terminate this branch because bob@workstation:2 was merged into branch init."
          pastwatch: Using branch head ZF1tN6VOS17BFq7fqvq0WFaxJIc
          pastwatch: committing
          pastwatch: new snapshot: VU97iwlRqSDgMPoHifQDV-pcCj8, 0 deltas

          alice% past latest
          pastwatch: Using branch: init
          pastwatch: Using branch head 0E-pvcJtOeVc88UVYBSuJfVLJMk
          branch "init": head is 0E-pvcJtOeVc88UVYBSuJfVLJMk

The following figure shows how the branches are reconciled in the branch tree:

Concurrent Reconciliation
-------------------------

It is possible that multiple members will try to reconcile the same fork at the exact same time.  In this case, the concurrent reconciliation will eliminate the original fork, but will result in a new fork.  A project member will then need to reconcile the new fork.