11.7 Version Trees

In the simplest versioning systems, the set of versions is just an ordered list, representing a linear line of descent where each version has at most one predecessor and at most one successor. Many more advanced versioning systems allow more complicated relationships.

11.7.1 Forking

Normally, when two users edit a document and don't want to overwrite each other's changes, they use locks to serialize their changes. This way only one user can make changes at a time. When that user releases the lock, the other user can see all the changes made so far and begin from that point. However, that's not the only way to manage multiple users changing a file.

Imagine that Alice is officially working on a document, but Bob wants to create an unofficial draft of the document. Bob needs to make several versions before his unofficial draft is ready to be considered as an alternative to the official version. Bob wants to check in his versions without affecting Alice. Versioning lets both Alice and Bob make their changes independently and save changes from either user as separate versions.

The next step to make this simultaneous-change model really useful is to keep the versions created by Alice and Bob distinguishable. This process is called forking. Rather than mingle all versions together in a single listing, the versioning repository identifies two lines of versions. Each user can create subsequent versions on his or her own line. It's easy for Carl to view both lines and understand where the two sets of changes started and how each version fits into the picture. Carl can even contribute to Bob's unofficial draft and check in those changes for Bob to see, still without affecting Alice's work.

Forking is often represented spatially. A single user's changes to a document are pictured in the version history in one dimension, a linear series of versions created over time. When several users are working on the document independently, the version history is represented in two dimensions as a version tree containing at least one fork. Now a version has one predecessor but may have multiple successors.

The version tree in Figure 11-8 shows one fork. Each arrow between resources shows the successor at the head of the arrow and the predecessor at the tail. The root version (v1) has two successors, v2 and v3. Bob created this fork to work on his draft material in v3. Carl added to the fork in v4, rather than the main line of work. This doesn't prevent Alice from adding new versions to the main line of work at any time.

Figure 11-8. Version tree with fork.

Some versioning systems encourage forking. Whenever two users make independent unmerged changes to the same resource, a fork is automatically created in the version tree. The fork makes it clear that the changes are not integrated with each other, rather than make it appear as if the second change was intended as a replacement for the first change. Other versioning systems discourage forking by making the client specifically request that a fork be created. The flexibility of DeltaV allows both kinds of systems with the fork-ok property.

Figure 11-8 shows two forks identified by the name of the user who edited the versions in each fork. It happens that Bob made changes on one fork and Alice on the other. It's also possible for Bob to want to make changes on the fork created by Alice, and vice versa. Therefore, although forks are often associated with multiple users working separately on their own forks, that's not always the case. In fact, it's possible for a single user to intentionally create a fork on a single-author document. A user might do this to keep track of two independent sets of changes. For example, when publishing a chapter of a book, an author might fork the version tree. Then the author can fix minor typos in the "published" fork of the version tree, and she can make major changes to the fork dedicated to a complete rewrite.

11.7.2 Creating Forks

In DeltaV, a fork is present whenever a version has more than one successor. The client causes this to happen by creating more than one new version that points to the same predecessor version, and when the server cleans up the relationships between versions, one version ends up with more than one successor. There are several ways to fork with the functionality defined so far and even more ways to fork when working resources and workspaces are thrown in.

Using UPDATE

A client can create a fork by checking out any version that already has a successor and checking it in again. This can be done by checking out a resource whose target version is a version that has a successor:

1. UPDATE the VCR to point to a version that already has a successor.

2. Make sure checkout-fork and checkin-fork are allowed on that version (see Section 11.7.5).

3. CHECKOUT the VCR. If checkout-fork was discouraged, include the fork-ok element in the CHECKOUT request body.

4. CHECKIN the VCR. If checkin-fork was discouraged, include the fork-ok element in the CHECKIN request body.

Editing Predecessor-Set

A client can also create a fork by using PROPPATCH to change the predecessor-set of a checked-out VCR such that the predecessor-set names a version that already has a successor. This is one way a user could decide after checking out that the resource ought to have a certain predecessor no matter which version was checked out.

1. CHECKOUT the VCR.

2. PROPPATCH the predecessor-set property on the VCR. To create a fork, give the property value the URL for a version that already has a successor.

3. CHECKIN the VCR. If checkin-fork is discouraged in the version identified in Step 2, include the fork-ok element in the CHECKIN request body.

11.7.3 Avoiding Forks

If checkout-fork is allowed but checkin-fork is forbidden, the client should be able to check out the resource whether or not the target version has a successor and may even be able to check in later as long as the checkin doesn't create a fork. The client can attempt to prevent the fork by fixing up the predecessor-set property of the checked-out resource so that the only predecessor is a version that has no successors (the latest version).

11.7.4 Simple Merge

Once forks exist, it's very likely that users will want to merge forks. Bob and Carl show their draft to Alice, and Alice decides it's got good ideas. Alice manually incorporates those changes into the official draft and creates v5. To show to all users that the content has been merged, it would be nice for the version tree to show that v5 was created with two predecessors, v2 and v4. A new user can then understand quickly that the latest content merges two lines of work (see Figure 11-9).

Figure 11-9. Version tree with merge.

A client can merge two forks by causing a version to be created that has two predecessors. The two predecessor versions need not be on different forks before the merge, but that's the usual case. The client can do this by combining the content of the two predecessors in a checked-out resource, setting the predecessor-set of the checked-out resource to contain both predecessors, and checking it in. It may be necessary to ask the user to approve the merge of content or to choose which content to use in the merge result.

If the server allows a checkin where the predecessor-set has multiple values, it must change the successor-set of each predecessor so that all the relationships are consistent. The effective result of this operation is a merge in the version tree, or the combination of two or more forks into one.

DeltaV was created with complex version trees in mind by default. A server can't advertise that it has only linear version trees; therefore, clients must assume forks and merges can exist in any version tree.

Note that DeltaV also has a method called MERGE, described in Section 12.4. The mechanism just shown does not use the MERGE method, yet it accomplishes a merge. The MERGE method does the same thing simultaneously for multiple files, and this chapter does not cover multiple-file scenarios.

11.7.5 Are Forks Permitted?

Before seeing how to create a fork, the client may check the checkin-fork and checkout-fork properties to see if the server will permit the fork. These properties are required on every version and can be empty or contain the values forbidden or discouraged. If one of these properties is empty, it means the related action is allowed. If checkout-fork is allowed, then a client may check out a version that already has a successor or is already checked out. If checkin-fork is allowed, the client may do a checkin, which would create a fork.

The discouraged value means that the server will not allow forks to be created accidentally. The client must submit a CHECKIN request with an XML body. The body must contain the fork-ok element inside a root element named checkout. This request forces the server to accept the checkin and create a fork.

The properties are also required on every checked-out resource, but here they mean something slightly different: They determine the values of checkout-fork and checkin-fork to be set on the new version that will be created after checkin.

Many server implementation choices are possible with these two properties and three values because the values can vary from resource to resource. These are a few of the most obvious and most consistent scenarios:

• To prevent forks entirely, the server should make sure that the checkout-fork and checkin-fork properties both have a value of forbidden on all versions. Both properties are protected. Note that this also prevents multiple checkouts.

• To prevent forks but allow multiple checkouts (working resources, which we'll see in Section 11.8), the server can make checkout-fork allow any checkout but make checkin-fork always forbidden. The predecessor-set property should be writable on checked-out resources. The client must can edit predecessor-set to ensure that the version created on CHECKIN will have as predecessor a version that does not already have a successor.

• To support forks (and multiple checkouts) completely, the server should make sure that the value for both checkout-fork and checkin-fork is empty or discouraged on all versions.

The client may even be allowed to change the value on a checked-out resource, which should cause the server to enforce the user's chosen behavior. However, the client can't tell if checkin-fork and checkout-fork are writable on a resource without trying that specific resource. The server could make the properties writable on checked-out resources but not on an existing version. The DeltaV specification implies that these properties may be writable, but some existing servers do not support forks and have implemented these properties as unwritable everywhere.