git-fast-export bug, commits emmitted in incorrect order causing parent data to be lost from commits turning essentially linear repo into "islands"

Hi,

Ive been working with git-fast-export a bit recently and Ive hit a bug that is causing some trouble.

Essentially it seems that one of our repos git-fast-export fails to emit the proper 'from' information for several commits in the repo. These commits are emitted first without parent data even though their parents ARE emitted later.

The code responsible for skipping the parent info is in

builtin-fast-export.c around line 402:

        for (i = 0, p = commit->parents; p; p = p->next) {
                int mark = get_object_mark(&p->item->object);
                if (!mark)
                        continue;
                if (i == 0)
                        printf("from :%d\n", mark);
                else
                        printf("merge :%d\n", mark);
                i++;
        }

If i modify this loop to warn when skipping a parent I get a warning for each of the "broken" commits. Apparently because they are emitted before their parents the parents have no "mark" assigned to them (via decoration) and thus are skipped in this emit process. This would make sense for emitting a limited number of patches, but makes no sense when the --all option is used. Ive tried to investigate further but i got lost in a twisty maze of routines in revision.c, which apparently is responsible for building a list of items to emit in the correct order.

However i think it is notable that both gitk and git log seem quite able to deal with things properly, thus i find it a bit strange that fast-export would get it wrong.

Unfortunately I have no idea how to create a minimal repo that illustrates this problem.

Im currently on git version 1.5.6.rc2.29.g3ba9 (latest version from last night), however this problem shows itself on 1.5.4.3 as well, as well as an earlier version whose exact number i no longer know.

Other evidence that might be useful

	git log --pretty=format:"%H:%P" 

shows that every commit but one (the root) has parents. And gitk renders the original repo fine. The repo can be cloned and etc, without trouble. The problem seems to be strictly related to fast-export.

Im not on list so please cc me on any replies. 

Thanks a lot! Yves

Yves Orton schrieb:

Does it make a difference if you pass --topo-order to git fast-export? (But I don't know for certain that this is even legal.)

-- Hannes

On Thu, 2008-06-12 at 13:53 +0200, Johannes Sixt wrote:

Yes it does make a difference. A big difference. That would be the workaround I really needed. At least currently thats the way it looks, i havent thoroughly tested the result yet but it certainly looks right.

Perhaps this should be enabled by default to avoid the problem i encountered? At least until whatever the cause of the root problem is identified and fixed.

Thanks a lot. ++ to you.

Cheers, yves

On Thu, 2008-06-12 at 14:04 +0200, Yves Orton wrote:

I should add that with this switch enabled the output order is correct, HOWEVER the mark number of the first commit is unchanged from the original. However the parent relationships are correctly restored and the resulting repo has the correct SHA1 stamps. So it looks like the original traversal order is wrong somehow, and that --topo-order fixes it up after the fact.

But for my immediate needs this is the solution I needed. Again many thanks.

BTW, for the record this was needed because we are trying to merge multiple git repos into a single new git repo with each original repo mapped into a subdirectory of the new repo, and with commit trees merged in more or less the correct order (by date applied more or less). IOW we dont want to have multiple "root commits" that are later merged.

We want a more or less linear repo as the result. This bug with fast-export was the main showstopper in our efforts. However, I can imagine that this is a problem that many people will want to solve. It would be nice if there was an easier way to do it that what we currently are doing (merging and munging multiple fast-export streams into a single fast-import process). While at this point its probably academic any suggestions as to the Best Way to do this would be very much welcome.

Cheers and thanks to all you git developers for a great tool! Yves

Yves Orton schrieb:

Try --date-order instead. It might work better for your task, and it still offers a topologically correct order.

-- Hannes

Yves Orton venit, vidit, dixit 12.06.2008 14:16:

I've done something like this, "stitching" the history of different repos together in order to produce one repo, with each of the constituents in a subdir. What I did was an adaption of

http://www.kernel.org/pub/software/scm/git/docs/howto/using-merge-subtree.html

but as a multistep version:

1. Create an empty repo
2. Add your to-be-stitched repos as remotes, say A B C
3. Create an empty commit
4. "git merge -s ours --no-commit a b c", where a b c are the root 
commits of A B C
5. "git read-tree --prefix=dir-A/ -u a" and analogously for b c
6. "git commit", use the common commit message of those commits

Note that git refuses the merge (4.) into an empty (headless) repo, which is why you need 3. There may be smarter ways. If you don't care about recording the commits as (octopus) merges you can skip 3. and 4. (4. just records merge info in the index).

Then, repeat:
3'. remove dir-A etc. (I think I used git-rm, I'm sorry I can't recall).
4. as above (if you want to record as merge)
5. as above
6. as above

If not all of A B C appear in every step then make sure to remove only the ones (in 3'.) which you'll update in 5. You have to remove the dir because read-tree wants it like that.

I used this for stitching 5 or 6 repos with a short history together, so I repeated these steps manually rather than scripting it; all I needed was a list of SHA1s listing which commits from A B C etc. corresponded to the same "step" in the combined repo.

Cheers Michael

On Thu, Jun 12, 2008 at 02:52:40PM +0200, Michael J Gruber wrote:

What we did with Yves was a script doing the following:
- run git fast-export --all (and --topo-order now) on all the repositories
  we wanted to merge and read blocks from them
- pass through all non-commit blocks (munging paths to put the content of
  each repo in its own directory and renumbering marks to avoid clashes)
- keep a list of the next commit sent by fast-export for each repo
- select the oldest commit, and send it through, after stitching in the
  right place (the point being to determine the "right place")

Actually, what we are trying to do is produce a single DAG from 2 or more DAGs, while making sure that each "internal DAG" is the same. (I'm pretty sure this is all trivial stuff for graph mathematicians)

Imagine we merged repositories A, B and C in a new repo D, if we replace all nodes from D coming from B and C by vertexes, we will end up with the original A graph.

We defined the "right place" as so: when having selected the next commit to add to our new graph, each of its new parents is defined by "the last alien child of the original parent" (or the original parent itself).

For example, if our new repository being built looks like:

 --A7--A8--B4--B5--A9--B7
            \
             --B6

In this case, A9 was originally attached to A8, but to avoid unnecessary branching in the new repo, we didn't attach it to A8, but to B5 (last alien child of A8, descending the tree in a leftmost manner).

No A node will ever be attached to B6. The next A node originally attached to A8 will be attached to B5 again, and one originally attached to A9 will be attached to B7. Like this:

                 --A10
                /
 --A7--A8--B4--B5--A9--B7--A11
            \
             --B6

Now, if we remove all B nodes, we get this:

         --A10
        /
 --A7--A8--A9--A11

which is the original A graph.

Finding the "last alien child" works fine with merges, too.

Of course, some commits from A might end up on an unrelated branch of B, but all B branches are irrelevant to A anyway! :-)