Re: Fake linear history in a deterministic manner.

On Mon, 13 Feb 2006, Martin Langhoff wrote:

Use topo-order.

merge-order is much more expensive to calculate, and doesn't even exist if NO_OPENSSL is set.

Anyway, while linearization in general is impossible, I'd suggest a few heuristics:

 - you obviously must remember the head of the previous linearization. Any 
   tree choices you made in the past are not something you can change any 
   more for cvs export.

   This may sound obvious, but the fact is, especially if you do the cvs 
   export frequently, and the main maintainer updates the tree in a timely 
   manner, it will limit your choices a LOT. In fact, most of the time 
   you'll have no choice at all: you will have an unambiguous "TRUNK" that 
   is defined by the fact that there is only one linear path from the 
   previous export-head to the current HEAD.

In short, most of the time you won't have any issues in a stable system. You'll see a true "fork in the road" choice only when the maintainer hasn't pushed his tree to the thing you export in a while, long enough that no CVS exporting has taken place over a whole parallel cycle. It's probably rare.

So the main issue of "which child to choose" becomes one of the initial export, and then just occasionally thereafter. And in that case, there's really just one obvious algorithm:

 - simply enumerate the possible paths (not that hard - it's just 
   enumerating a tree once you've generated the graph in memory with child 
   and parent pointers), and just selecting the one with the "longest 
   weighted path".

I say "weighted path", because you might want to consider different commits to have different weights. For example, you might want to consider merge commits to be less interesting (so weight them as 0.5 commits) in order to get as many "real" commits as possible. And you might consider commits made by a certain person to be "more TRUNKish", and give them a weight of 2, so that you'll be more likely to follow the "maintainer view" over any other linearized history.

No other algorithm seems very sane. 

		Linus