Re: [gentoo-scm] Re: [gentoo-dev] CVS -> git, list of where non-infra folk can contribute

[Rich Freeman]

On Tue, Oct 2, 2012 at 5:39 PM, Peter Stuge <peter@×××××.se> wrote:
> Rich Freeman wrote:
>> That means that instead of descending the entire tree for every
>> commit you only actually descend the branches that have changes
>> on each commit, which in most cases will just be a single branch
>> anyway.
>
> What tree is that? If you're talking about the git DAG that doesn't
> make sense to me at all. :\

See my earlier email in the archives.  My proposal for validating the
conversion is to go through both repositories and generate a list for
all files in the repo (active and deleted) which contains:
path/file, hash, date/time, author, commit comment

Then comparing them should be easy.

For git the conceptual way to do this is to take each commit and walk
its tree and generate a dump of all the files in the tree with the
info above.  Do this for each commit in one big list, sort the list by
file and date/time, and then delete all but the first line in cases
where consecutive lines have the same hash.

However, this involves walking the entire tree for every commit, which
is a lot of unnecessary work since in any commit little has actually
changed.

So, instead you pass through the list in stages.  The first stage
involves walking the linear list of commits (fortunately no branching
here), and dumping a list like the one above except instead of
path/file you have trees.

At each subsequent step the algorithm is:
1.  Read a line.
2.  If it is a blob, output the same line.
3.  If it is a tree, read the tree and output one line for each of its
contents, with all the info but the path/file and hash remaining the
same as what was on the line that was read.  Be sure to insert the
current directory into the path for each line.
4.  Goto step 1 until the entire file is read.
5.  Sort the output by file and then date/time.  Delete all but the
first line for any cases where consecutive lines have the same hash.

Each time you do this you descend the entire tree by one step,
discarding cases where from commit to commit a section of the tree
contained no changes.  It is important to be careful with the sorting
because if a tree changed from A to B back to A you don't want to lose
one of the As, since it would have a unique time/reason/author/etc.

You then repeat the entire process until you go through the entire
file and there are no trees left.  Then after the sort/trim step you
have a complete history per-file for the entire repository.

I need to look at the case for cvs next.  However, I think cvs
basically stores the history per-file anyway, so that is probably just
a matter of walking the entire repository once and dumping the data in
the same format.

Where I use the word "line" above that could be xml, a serialized
array of some sort, or whatever.  It probably would be best to not
just do this in a text file to avoid issues with delimiters, unicode,
etc.  However, if there were a delimiter we could be certain is
nowhere in the repository a text file would work fine.

That algorithm should work fine in parallel - just chop up the list
and have each worker do its list.  The sort/trim step does have to be
universal, but as long as you sort the whole list and chop it up on
file boundaries you could actually distribute the trim part.  It
really does seem like a Map/Reduce from the perspective of the list,
but the workers need access to the git repository to "parse" the list
and I'm not sure that Hadoop/etc lets you do this easily.  The map
function is essentially a simple function that happens to have a 2GB
"lookup table" inside.

Rich