Subject: Re: git fast-export | git fast-import doesn't work

From: Alexander Gavrilov <[email-masked]>
Date: Sun, 7 Dec 2008 14:25:52 +0300

On Wednesday 26 November 2008 20:08:54 Johannes Schindelin wrote:
> On Wed, 26 Nov 2008, Michael J Gruber wrote:
> > Looking at the source I suspect that fast-export fails to denote 
> > parenthood in the case of yet unmarked parents (last for-loop of 
> > handle_commit() in builtin_fast_export.c). But I don't really know that 
> > code at all.
> 
> I strongly doubt so.  Noticed the use of has_unshown_parent(commit) in 
> both cases before calling handle_commit()?
> 
> In any case, here is a script that I wrote _long_ time ago, to be able to 
> reconstruct history from the output of "git rev-list --all --parents".  
> Maybe this helps you in reconstructing something that is handled 
> incorrectly by fast-export | fast-import, but is lighter than a full-blown 
> repository.

Today I had time to investigate this problem, and found:

1) The root of the problem is that fast-export really wants to walk
    revisions in topological order, but actually receives them in date
    order. While it is usually a good guess at topology, this repository
    contains some children that are older than their parent commits,
    e.g. see dd22c7d51a4debf18a3b2e35c61a1fec0175e4e0

2) It tries to fix minor deviations by checking the SHOWN flag.
   However, it still breaks in two ways:

  a) SHOWN is apparently set by simply walking the commits, so
      if the parent was earlier encountered on a different branch of
      the DAG, it will be handled as already shown. Basically, this
      check is only good to determine if we reached the end of the
      chain, and should start to backtrack.

  b) If I modify the code to use a completely separate flag, it still
      doesn't work, because the commits are placed on the stack in
      the wrong order, so handle_tail gets stuck, and fails to unwind
      it completely.

So, apparently, the only way to fix it is to require topological order:

diff --git a/builtin-fast-export.c b/builtin-fast-export.c
index 7d5d57a..d9261fa 100644
--- a/builtin-fast-export.c
+++ b/builtin-fast-export.c
@@ -490,6 +490,7 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
        git_config(git_default_config, NULL);

        init_revisions(&revs, prefix);
+       revs.topo_order = 1; /* force topological ordering */
        argc = setup_revisions(argc, argv, &revs, NULL);
        argc = parse_options(argc, argv, options, fast_export_usage, 0);
        if (argc > 1)

(It is also possible to specify --topo-order on the command line)

As for the failure to import the output of fast-export with copy detection,
it is a natural consequence of a messed up order of commits, because
copy and move commands depend on the original file being there.

The attachment contains a (proper) export of a simplified sample of the
structure around dd22c7d51a4d, which clearly reproduces the problem
because all of the timestamps were made identical as a side effect of
simplification. By crafting timestamps it is probably possible to minimize
it even further.

Alexander