Request for code review: cvs-fast-export

Sometimes reading code is really difficult, even when it’s good code. I have a challenge for all you hackers out there…

cvs-fast-export translates CVS repositories into a git-fast-export stream. It does a remarkably good job, considering that (a) the problem is hard and grotty, with weird edge cases, and (b) the codebase is small and written in C, which is not the optimal language for this sort of thing.

It does a remarkably good job because Keith Packard wrote most of it, and Keith is a brilliant systems hacker (he codesigned X and wrote large parts of it). I wrote most of the parts Keith didn’t, and while I like to think my contribution is solid it doesn’t approach his in algorithmic density.

Algorithmic density has a downside. There are significant parts of Keith’s code I don’t understand. Sadly, Keith no longer understands them either. This is a problem, because there are a bunch of individually small issues which (I think) add up to: the core code needs work. Right now, neither I nor anyone else has the knowledge required to do that work.

I’ve just spent most of a week trying to acquire and document that knowledge. The result is a file called “hacking.asc” in the cvs-fast-export repository. It documents what I’ve been able to figure out about the code. It also lists unanswered questions. But it is incomplete.

It won’t be complete until someone can read it and know how to intelligently modify the heart of the program – a function called rev_list_merge() that does the hard part of merging cliques of CVS per-file commits into a changeset DAG.

The good news is that I’ve managed to figure out and document almost everything else. A week ago, the code for analyzing CVS masters into in-core data objects was trackless jungle. Now, pretty much any reasonably competent C systems programmer could read hacking.txt and the comments and grasp what’s going on.

More remains to be done, though, and I’ve hit a wall. The problem needs a fresh perspective, ideally more than one. Accordingly, I’m requesting help. If you want a real challenge in comprehending C code written by a master programmer – a work of genius, seriously – dive in.

https://gitorious.org/cvs-fast-export/

There’s the repository link. Get the code; it’s not huge, only 10KLOC, but it’s fiendishly clever. Read it. See what you can figure out that isn’t already documented. Discuss it with me. I guarantee you’ll find it an impressive learning experience – I have, and I’ve been writing C for 30 years.

This challenge is recommended for intermediate to advanced C systems programmers, especially those with an interest in the technicalia of version-control systems.

27 comments

  1. I know c, but at a pitiful level by your standards.

    However, many years ago I found a bug in a COBOL program – when I didn’t know COBOL. (Still don’t,)

    So maybe I’ll take a run at it.

  2. I find the random mix of whitespaces and tabs in the codebase a bit vexing … funny how fast one get spoiled by tools like go fmt!

  3. It looks to me like ‘seen’ just counts the number of heads each commit is reachable from, and commits with ‘tail’ set are where you would want to stop during a recursive traversal to avoid visiting commits more than once.

    1. >It looks to me like ‘seen’ just counts the number of heads each commit is reachable from

      I came to this conclusion a few hours ago and was about to document it when I was interrupted for dinner. :-)

      >commits with ‘tail’ set are where you would want to stop during a recursive traversal to avoid visiting commits more than once.

      That sounds plausible. I’ll reread with that in mind.

  4. The ‘tagged’ bit is set on commits referenced directly by a tag or head… but it was only used in dump_get_rev_parent, which you removed a few days ago.

    1. >The ‘tagged’ bit is set on commits referenced directly by a tag or head… but it was only used in dump_get_rev_parent, which you removed a few days ago.

      Good catch.

  5. I’m having a lot of trouble with the test suite. It seems cvs is dropping commits on the floor during repo generation.

    1. >I’m having a lot of trouble with the test suite. It seems cvs is dropping commits on the floor during repo generation.

      That’s disturbing. What version of CVS are you using? Mine is GNU CVS 1.12.13.

  6. Hmm, I’m not sure if you have an opinion on it per se, but I’m kind of wondering if you would be open to converting the program to CWEB? One where the algorithms are described in high-level English right next to the code itself.

    Not just helping those disecting the code in the first place to write such documentation, but it could easily help future maintainers and such.

  7. Run through ctags and doxygen… Call list looks lovely.

    Looks like topological sort (my favorite graph algorithm) and loop detection (well, no loops, but branches that merge). Happens in “rev_ref_tsort”, calls it “tsort”.

    I’m a big fan of topo sort, so I’ll have to look more into this when not at my day job.

    1. >I’m a big fan of topo sort, so I’ll have to look more into this when not at my day job.

      Do that. I recognized the topo sort, but I don’t know why it’s being applied here and would like to document that.

  8. Have you considered running some kind of indenter like gnu indent or astyle?

    I’m looking at the source on gitorious, and I can grok the code but it is extra hard when everything is 4 or 5 spaces in. I’ll have to clone, then run everything to clean it up.

    Really, it makes sections like this (which I think is one of the critical ones) hard:

    for (l = head; l; l = l->next) {
    for (lh = l->heads; lh; lh = lh->next) {
    h = rev_find_head(rl, lh->ref_name);
    if (!h)
    rev_list_add_head(rl, NULL, lh->ref_name, lh->degree);
    else if (lh->degree > h->degree)
    h->degree = lh->degree;
    }
    if (++n % 100 == 0)
    progress_jump(n);
    }

    I recently found a critical (zap filesystem) bug which was merely a “dangling else” that if anyone had run it through the pretty printer would have found if their eyes paused over it.

  9. >tz, it is indented fine, it just has tabs mixed with spaces.

    I might suggest that the two parts of that sentence are contradictory…

  10. >> tz, it is indented fine, it just has tabs mixed with spaces.

    > I might suggest that the two parts of that sentence are contradictory…

    Well, it probably depends on what “tabs mixed with spaces” means. In my opinion using tabs to indent, but spaces for align (e.g. on “=”) is perfectly fine — it has the advantage that code looks the same independent on tab width, but not everybody likes space-after-tab.

  11. I generally prefer spaces only. However, when looking at / modifying other peoples’ code, I don’t demand they conform to my standard. In this case, it appears that tabs at 8 are used, and spaces fill in the indent less than 8 spaces. When i’ve used tabs in the past, I uses a tabspacing that matched my indent. However, an indent of 4 and tabspacing of 8 has a long history. It’s not optimal IMO, but a default tabspacing of 8 is pretty standard, and to ignore that is silly.

  12. I viewed it on gitorious.com – I didn’t try downloading it, and gitorious doesn’t indicate spaces v.s. tabs. But if the gitorious view is broken, it is a bit much to ask me to try to figure out whatever whitespace nuances are going on so I might have a chance of fixing things.

    If you accidentally set vim or whatever you are using so it just happens to do things right, it might show the proper indentation. I set ts=4 because I don’t want things to require I stretch my window to the edge of my 4K display.

    I’ve set things so it always saves with spaces, not tabs, indents properly automatically, does unix line-endings, etc. on my editor. Check-ins often have the option of cleaning before sending up to the repo.

    If gitorious thinks ” ABC” is the same as “^iABC” and displays it the same, it might have a problem.

  13. Algorithmic density has a downside. There are significant parts of Keith’s code I don’t understand. Sadly, Keith no longer understands them either.

    Been there, done that (though doubtless not as densely or nicely as Keith did).

    (“How did this ever work?” being one of my favorite comments on my own old code… which used to work, though God knows how.)

    Lines of code are cheap compared to comprehensibility, and so are comments.

    If it’s too algorithmically dense to comment usefully, it’s too dense to understand when you come back in six months, and you just made write-only code.

    Future You will be happy you didn’t do that.

  14. @Sigivald:
    >Been there, done that (though doubtless not as densely or nicely as Keith did).

    Worse, I’ve been there, done that with x86 assembly code. I gave myself a good, hard kick in the shins for that.

  15. > What version of CVS are you using?

    CVS 1.12.12.

    You’ve been hit too. Take a look at basic.tst and basic.chk. Notice that basic.chk is missing the last 7 commits. I predict you’ll find that basic.repo is also missing those commits. A rebuild might fix it, or it might not.

    (The other .chk files look OK to me though.)

    1. >Take a look at basic.tst and basic.chk. Notice that basic.chk is missing the last 7 commits.

      It’s deterministic, whatever it is. Otherwise I’d get a random set of test failures every time I rebuilt the repo.

      I’ll look into it tomorrow.

    2. >Notice that basic.chk is missing the last 7 commits.

      Fixed. The CVS CLI tools are a bit race-prone; all I had to do was up the pre-commit delay from 1 to 2 seconds.

Leave a comment

Your email address will not be published. Required fields are marked *