History over-simplification

["Shawn O. Pearce" <spearce@spearce.org>]

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.