Developer blog: niallo

There has been quite a bit of interest from the user community in the OpenCVS project over the past while, and I have been thinking about writing some sort of blog entry on the subject for some time. I guess Marco's incessant blogging has finally gotten to me and inspired me to try to write something myself!

First of all, a little bit of history. RCS was first developed in the early 1980s by Walter Tichy at Purdue University, so its over 20 years old. RCS operates on individual files. If you're not already acquainted with how the RCS tools work, take a look at the rcsintro(1) manual page. There is also a 1985 paper RCS - A System for Version Control which has further information. To anybody with CVS experience, RCS may seem strangely familiar. CVS as we know it pretty much arrived on the scene around 1990. Rather than dealing with individual files, CVS operates on a directory of RCS files. This is why an RCS implementation lies at the heart of OpenCVS, and why we are using the OpenCVS code to write a replacement for GNU RCS, too (OpenRCS). This paper (PDF) from 1990 describes the implementation of CVS and its status at that time.

Essentially, the RCS file format (all those files with a ,v extension), is ASCII based and made up of three section. The first of these is the admin secion, which contains information about locks, symbolic names, etc. E.g.:

head 1.3;
access;
symbols;
locks
        niallo:1.3; strict;
comment @# @;

Following this section comes the deltas. Each entry in this section basically describes a particular revision of the file being tracked. It contains the date and time of the revision, the author, the state, sometimes branch information and a pointer to the previous revision. E.g.:

1.3
date    2006.02.27.17.07.13;    author niallo;  state Exp;
branches;
next    1.2;

1.2
date    2006.02.27.17.06.38;    author niallo;  state Exp;
branches;
next    1.1;

Finally, there is the deltatext section. These contain the data corresponding to the file contents and associated commit log message at each revision. Typically, the HEAD deltatext (usually the first appearing in the file) is the complete contents of the file. All previous deltatexts contain diffs against this deltatext in a sort of reverse ed(1) format. E.g.:

d1 1
a1 1
$Id$
d3 1

This deltatext demonstrates the two operations patches perform: delete, and addition. "d1 1" translates to "at line one, delete one line worth of text". Conversely, "a1 1" following by its line of data translates to "at line one, insert the following single line of text".

In order to retrieve a particular revision, you typically first retrieve the HEAD revision, then calculate the final data by reverse-applying the diffs in the deltatexts up to the desired revision.

Well, that's it for my short introduction to the RCS file format. Hopefully, this should illustrate why certain things can be tricky or slow in CVS/RCS, namely:

• Dealing with binary files.
• Retrieving an arbitrary revision requires parsing all previous deltas and deltatexts, thus it is not at all a random access operation.