Hacker’s guide to cvs-fast-export

This program was originally written as a one-off hack by Keith Packard in early 2006, when he was working on migrating the X repositories from CVS to git, and was not originally intended to survive that conversion. It was called parsecvs then. It called git tools directly to create translated repositories.

The code was briefly maintained by Bart Massey before passing to Eric S. Raymond in late 2012. ESR wrote the fast-export output stage and renamed the program to reflect its new function.

Most of ESR’s original contributions are in export.c, which is why that code is in a somewhat different style than the rest of the codebase. ESR also split the original commit structure into cvs_commit and git_commit as a space optimization, rescued the rather decrepit code for generating graphviz visualizations, and hacked the parser code to be fully re-entrant.

A few other people have contributed significant improvements since, mainly performance tweaks. Most notably: Jens Bethkowsky <jens.bethkowsky@rwth-aachen.de> added a red-black-tree implementation to speed up symbol search; Aidan Hobson Sayers <aidanhs@cantab.net> replaced an O(n**3) sort with an O(n log n) sort; David Leonard <david.leonard@opengear.com> sped up compute_parent_links() and wrote several other significant optimizations. Laurence Hygate <loz@flower.powernet.co.uk> wrote many sort and hash optimizations. Alan Barrett wrote the improved progress meter. Tom Enterline sped up snapshot generation.

Significant portions of this code remain a trackless jungle of complex algorithms with poorly documented assumptions. Only Keith ever completely understood it, and he does no longer. Others have been able to modify it mainly by isolating pieces that they could comprehend without having to grok the whole.

To understand this program, you need to understand the problem it solves: lifting CVS repositories to git-compatible fast-import streams.

What makes this problem difficult is that CVS records deltas (and tags) per-file, but what we want for the fast-import representation is changesets - that is, coherent groups of per-file deltas that capture multiple per-file changes made with the same intention at the same time. The fundamental thing cvs-fast-export does is identify cliques of per-file deltas that should be coalesced into changesets.

To do this, it relies on the fact that the CVS command-line tools fake supporting changesets by replicating the comment that the user supplied to cvs commit into every individual file delta that the commit creates.

Under relatively recent implementations, CVS also embeds a common (and unique) commit-ID field in each file delta of the group. These cliques can be unambiguously identified. Groups recorded by older implementations that don’t generate commit-IDs must be identified by the fact that they have the same change comment, author, and change date.

Actually, commit-date comparison has to be fuzzy because each file commit is actually done as a separate operation and may not complete in the same clock second as the previous one (this is why cvs-fast-export has the -w option). Timestamp matching is further complicated by clock-skew effects; for historical reasons, deltas are committed with a timestamp generated on the client side rather than the server. Thus, clock drift between different client machines can cause some odd effects, including child revisions with dates before their parents.

But timestamp issues are actually the least part of the problem. A much bigger issue is per-file branch structures and tags that aren’t conformable with each other. The CVS tools have few safeguards against creating such, and it is easy to end up with a situation where file-delta cliques can be resolved but the right way to build them into a DAG of parent-child links is unclear or ill-defined. Inconsistent or incomplete tagging can cause interpretation problems as well.

Now you should read "RCS/CVS LIMITATIONS" in the cvs-fast-export(1) manual page.

Below is a simple example of conformable branch structure involving two files.

In this diagram, down is the arrow of time. Each box on the left-hand side represents a CVS file delta, each box on the right a changeset. In each box the top line is a list of files modified and the bottom line a change comment. The branch labels at the bottom are HEAD for the main branch in each CVS file and master for the main branch in the gitspace DAG.

Here’s an elaboration of that example, a conformant pair of CVS masters with branching:

Note that the branch point and branch ID (the three-part label on the branch) for alternate are different in the two CVS masters, so cvs-fast-export cannot rely on them matching to figure out the topology.

It also has to deal wth this case correctly:

That is, after any branch there may be a delta that doesn’t make a changeset with any delta on matching branches.

The previous diagrams elide some important details, which is how tags and branches are actually represented in CVS. First: there are no per-changeset tags, only per-file ones. When CVS fakes tagging a changeset, what it actually does is add the same tag symbol to every file master in the changeset.

(Various kinds of operator error and/or CVS bug can cause the creation of incomplete tagged sets, which don’t annotate every master in existence at tag creation time. These are a headache for any conversion tool. cvs-fast-export deals with them by creating tagged branchlets containing exactly one commit.)

Named CVS branches are represented by adding a "sticky tag" to every file in the branch. In the above examples, the branch beginning with 1.2.1.1 would have been created with a command sequence like this done while 1.2 is checked out:

The magic sticky value for the first (1.2.1.x) branch is 1.2.0.1. If a second, 1.2.2.x branch were created, its magic sticky tag would have the value 1.2.0.2. The sticky tag is treated as a name for its corresponding branch, whatever the tip revision happens to be.

Vendor branches are a poorly-documented feature which has been a source of great confusion for programs attempting to convert or data-mine CVS repositories. This section describes the assumptions cvs-fast-export uses in dealing with them in painstaking detail, because it is not unlikely they will be a continuing source of correctness issues.

In "CVS II: Parallelizing Software Development" (1990) Brian Berliner, one of the principal CVS developers, write a major section 2.2 titled "Tracking Third-Party Source Distributions". It begins:

The following diagram reproduces the topology of Berliner’s figure 2 using the same conventions as the diagrams in the previous section (these revisions have no change comments):

(The intended meaning of the arrow from "HEAD" to the vendor branch label 1.1.1 is not explained in the paper.)

Berliner continues:

Berliner continues:

Berliner concludes:

Note that the paper does not actually describe how CVS should behave if the 1.2 revision were absent from this diagram.

Historically, cvs-fast-export's behavior with respect to vendor branches (from when it was parsecvs) was described by the following comment due to Keith Packard:

"Vendor branches" (1.1.x) are created by importing sources from an external source. In X.org, this was from XFree86 and DRI. When these trees are imported, cvs sets the default branch in each ,v file to point along this branch. This means that tags made between the time the vendor branch is imported and when a new revision is committed to the head branch are placed on the vendor branch In addition, any files without such a delta appear to adopt the vendor branch as head. We fix this by merging these two branches together as if they were the same."

All that is consistent with the Berliner paper except, crucially, the last sentence (" merging these two branches together as if they were the same"). Consider the following revision diagram, which corresponds to Changelog,v in the oldhead test repository:

The actual oldhead repo has revisions up to 1.8 on the master branch and 1.1.1.3, but this subgraph illustrates the problem. Under the merge rule, the tip content will be that of 1.1.1.2 than 1.2. This does not match CVS’s observed behavior.

The behavior now implemented is to find the highest-numbered (thus, presumbably, the most recent) vendor branch, point the "master" named reference at it, and then splice the existing master branch to the end of that vendor branch.

This program operates in three stages. The first (analysis) digests a collection of RCS masters into a collection of linked lists and structures representing per-file revision trees. The second (resolution) massages the revision trees into a DAG (directed acyclic graph) of changesets. The third stage (export) emits a report on the DAG structure, either a fast-export stream expressing it or DOT code for a visualization that can be rendered by graphviz.

The main sequence of the code is, unsurprisingly, in the main() portion of the file main.c.

This program is rife with tricky data structures. If you want to modify it, the first thing you should do is read the definitions in cvs.h.

The trickiest part is that the rev_list structure is used polymorphically in such a way that it’s not easy to tell what the semantics of a rev_list * are. Early in processing it tends to point at the branch-head head list for a single CVS master. Later it can link to the digested form of an entire CVS repo (e.g. a linked list of rev_list objects each encapsulating a CVS master’s content). Still later it can link to a tree of gitspace commit objects.

In an attempt to make the code more readable, cvs.h defines three typedefs, one for each of these uses. The rest of this section uses those.

The first stage turns each CVS file into a cvs_repo * - a linked list of rev_ref objects, each of which represents a named CVS branch head. The rev_ref objects in turn point at chains of cvs_commit objects, each representing a CVS delta.

During the resolution phase, the branch structures associated with individual files are transformed into a single git_repo * representing a repository-state DAG. At this point, the commit pointers change semantics to refer to git_commit objects; a certain amount of type punning is involved.

The export code walks the resulting single git_repo linked list generating a report from it.

A notable feature of the git_commit structures is that the code goes to great lengths to space-optimize (pack) the representation of file paths in the commit at the point when it is synthesized (this is required in order to hold down the program’s working-set size on large repositories). After packing, paths are represented by structure trees that coalesce common path prefixes.

The refcount field in the commit structure counts the number of branch heads from which the commit can be reached by an ancestry chain.

There’s a comment in collate_to_changesets() that says "Yes, this is currently very inefficient". That is a probable hotspot.

The fact that nobody really understands the resolution algorithm is worrying. It means nobody has much hope of fixing it where it breaks.

There is a rare but fatal problem which manifests as a crash with the message "branch cycle error". It reflects an undiagnosed problem in the aforementioned resolution error.

Vendor-branch handling - revcvs.c:cvs_master_patch_vendor_branch() - is subject to problems in various ill-defined edge cases.

Various mysterious error messages need to be documented. Basically, if it’s not in the list on cvs-fast-export.adoc, it needs to be.

When modifying this code, run the regression tests (make check) early and often. It is very easy to break even with apparently innocuous changes. You will want to have cppcheck, pylint, and shellcheck installed for full code validation.

If you find a bug and fix it, please try to create a toy repo exhibiting the problem - or, better yet, a minimal set of operations to reproduce it. Then add that to the regression tests.

Likewise, when adding a feature, add a test for it as well.

If you figure out something about the code that isn’t documented here - or, especially, if it’s documented wrongly - please include an explanation with your patch.