threads / discuss / 9977

History over-simplification

Subject: History over-simplification

## tl;dr

3 messages between Sep 23, 2007 and Sep 26, 2007.

replies: 2people: 2as markdown or json

Shawn O. Pearce· Sep 23, 2007, 04:46 UTC · lore

This is an interesting problem for me. We had a bad merge in the repository that produced this particular gitk graph:

  http://www.spearce.org/2007/07/ugly-gitk.gif

The project maintainer tried to locate the commits that altered a given file with `gitk -- path` and found only one commit (the introduction of the path) but expected to at least find a modification from a side branch. What he was looking for specifically was the merge (or revert) that threw away that side branch's change as the change wasn't supposed to have been reverted/lost.

He knew what the commit from the side branch was (the author of it still had a branch pointing at the commit). But try finding the proper child commit in gitk without a path limiter in that graph I link to above. If you don't remember what a mess it is, click through briefly to refresh your memory. The path limiter is really required here to boil the graph down to something a human can reason with.

Adding in --full-history *almost* gave us the data he needed. It did find the modification on the side branch but it couldn't point to the child commit which reverted the path. It turns out the bad change was an octopus merge commit done incorrectly. Yes, really. Don't bother telling me how bad octopus merges are. This problem happens in a two parent merge as well.

Below is a test which shows the problem. Without the associated patch to revision.c we cannot find the ours merge that trashed the side branch's change. In this toy repository its no big deal to find the ours merge and figure out what happened. In the production repository we were looking at above its impossible without support from Git.

I don't really like the patch to revision.c because it winds up showing trivial merges too. What I really want is to have the "--full-history" option include a merge if either of the following is true:

 a) The resulting path does not match _any_ of the parents.  We
    already handle this case correctly in revision.c and correctly
    show the "evil" merge.

 b) The resulting path matches one of the parents but not one of
    the others.  In such a case the merge should still be output if
    a 3-way read-tree would not have chosen this result by default.

The problem is computing b) from within the revision walker. You can't compute the merge bases while inside the inner loop of the revision walker itself, its already busy and the flags are already in-use on all objects. Worse commit parents are being rewritten in ways that may break merge base computation. Oh, and lets not even talk about how expensive that merge base computation is if we were to perform it on every merge. :-\

Thoughts?

diff --git a/revision.c b/revision.c
index 33d092c..aca62a6 100644
--- a/revision.c
+++ b/revision.c
@@ -365,7 +365,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 		}
 		die("bad tree compare for commit %s", sha1_to_hex(commit->object.sha1));
 	}
-	if (tree_changed && !tree_same)
+	if (tree_changed && (!tree_same || !revs->simplify_history))
 		commit->object.flags |= TREECHANGE;
 }
 
diff --git a/t/t6008-rev-list-toosimple.sh b/t/t6008-rev-list-toosimple.sh
new file mode 100755
index 0000000..696b057
--- /dev/null
+++ b/t/t6008-rev-list-toosimple.sh
@@ -0,0 +1,41 @@
+#!/bin/sh
+
+test_description='test git-rev-list history over simplification'
+. ./test-lib.sh
+
+test_expect_success setup '
+	echo BASE >content &&
+	git add content &&
+	git commit -m BASE &&
+	base=$(git rev-parse --verify HEAD) &&
+
+	test_tick &&
+	git checkout -b side &&
+	echo SIDE >content &&
+	git commit -m SIDE content &&
+	side=$(git rev-parse --verify HEAD) &&
+
+	test_tick &&
+	git checkout master &&
+	echo OTHER >other &&
+	git add other &&
+	git commit -m OTHER &&
+
+	test_tick &&
+	git merge -s ours side &&
+	keep=$(git rev-parse --verify HEAD) &&
+	test OTHER = $(git cat-file blob HEAD:other) &&
+	test BASE = $(git cat-file blob HEAD:content)
+'
+
+cat >expect <<EOF
+$keep
+$base
+$side
+EOF
+test_expect_success 'revert merge in history' '
+	git rev-list --full-history HEAD -- content >actual &&
+	git diff expect actual
+'
+
+test_done

-- 
Shawn.

Junio C Hamano· Sep 25, 2007, 22:42 UTC · re: Shawn O. Pearce · lore

Re: History over-simplification

"Shawn O. Pearce" <spearce@spearce.org> writes:

Show 12 quoted lines

> I don't really like the patch to revision.c because it winds up
> showing trivial merges too.  What I really want is to have the
> "--full-history" option include a merge if either of the following
> is true:
>
>  a) The resulting path does not match _any_ of the parents.  We
>     already handle this case correctly in revision.c and correctly
>     show the "evil" merge.
>
>  b) The resulting path matches one of the parents but not one of
>     the others.  In such a case the merge should still be output if
>     a 3-way read-tree would not have chosen this result by default.

I am not sure (b) is useful in general. Merging two branches that fix the same issue but in different ways (think: 'maint' and 'master' have different infrastructure and a fix initially made on 'master' was backported to 'maint', and then later 'maint' needed to be merged to 'master' to carry forward other fixes) is a norm, and in such cases taking the version from the merged-to branch is almost always what happens.

Also it sounds to me by "if read-tree would not have chosen this result by default" you mean this feature would not just need to run merge-base but also recursive merge-base synthesis, and also recreate the structural merge (aka "rename detection") there as well. Even if (b) is useful, it sounds like a very expensive option, and the current merge-recursive code is structured in such a way to be easily reused for this purpose.

Shawn O. Pearce· Sep 26, 2007, 15:55 UTC · re: Junio C Hamano · lore

Re: History over-simplification

Junio C Hamano <gitster@pobox.com> wrote:

Show 22 quoted lines

> "Shawn O. Pearce" <spearce@spearce.org> writes:
> 
> > I don't really like the patch to revision.c because it winds up
> > showing trivial merges too.  What I really want is to have the
> > "--full-history" option include a merge if either of the following
> > is true:
> >
> >  a) The resulting path does not match _any_ of the parents.  We
> >     already handle this case correctly in revision.c and correctly
> >     show the "evil" merge.
> >
> >  b) The resulting path matches one of the parents but not one of
> >     the others.  In such a case the merge should still be output if
> >     a 3-way read-tree would not have chosen this result by default.
> 
> I am not sure (b) is useful in general.  Merging two branches
> that fix the same issue but in different ways (think: 'maint'
> and 'master' have different infrastructure and a fix initially
> made on 'master' was backported to 'maint', and then later
> 'maint' needed to be merged to 'master' to carry forward other
> fixes) is a norm, and in such cases taking the version from the
> merged-to branch is almost always what happens.

(b) is useful, even in the case you just described. Try doing the above backport today. Run `git log maint -- foo.c` and find the backported commit B. Now try to see if that commit is in master in foo.c with `git log master -- foo.c`. B won't appear as the merge of maint into master chose master's revision and maint's history is pruned away.

Now if the backported change was logically the same but was rewritten considerably it might take you a while to figure out why a merge discarded the change B. The merge commit might actually describe why in its message, but you can't find that particular merge commit today, even with --full-history. Not without my one-line patch.

Unfortunately my one-line patch causes all of the merges that the
path is involved in to be output.  That can be quite a lot of them.

Show 7 quoted lines

> Also it sounds to me by "if read-tree would not have chosen this
> result by default" you mean this feature would not just need to
> run merge-base but also recursive merge-base synthesis, and also
> recreate the structural merge (aka "rename detection") there as
> well.  Even if (b) is useful, it sounds like a very expensive
> option, and the current merge-recursive code is structured in
> such a way to be easily reused for this purpose.

I think you meant here that it is *not* structured in a way to be easily reused for this purpose. That code relies heavily on the index to allow it to create that synthetic merge base. Making it callable from within the revision walker would not be a small change.

But as you say, running merge-recursive here would be a very expensive option. Which is why I was saying the 3-way read-tree result as that is cheaper to compute. However the read-tree result can be different from the merge-recursive result (think renames) and yet both are still "trivial" resolutions that the user was never involved in.

Of course other kinds of trivial merges (where changes from the two branches are in the same file but far enough part it can be easily merged as a 3-way file merge) appear to the path limiter as though they were an evil merge, and such merges are output.

So maybe having --full-history output all merges that affected that path really is the right choice.

-- 
Shawn.