revision traversal: show full history with merge simplification

The --full-history traversal keeps all merges in addition to non-merge
commits that touch paths in the given pathspec.  This is useful to view
both sides of a merge in a topology like this:

        A---M---o
       /   /
   ---O---B

even when A and B makes identical change to the given paths.  The revision
traversal without --full-history aims to come up with the simplest history
to explain the final state of the tree, and one of the side branches can
be pruned away.

The behaviour to keep all merges however is inconvenient if neither A nor
B touches the paths we are interested in.  --full-history reduces the
topology to:

   ---O---M---o

in such a case, without removing M.

This adds a post processing phase on top of --full-history traversal to
remove needless merges from the resulting history.

The idea is to compute, for each commit in the "full history" result set,
the commit that should replace it in the simplified history.  The commit
to replace it in the final history is determined as follows:

 * In any case, we first figure out the replacement commits of parents of
   the commit we are looking at.  The commit we are looking at is
   rewritten as if the replacement commits of its original parents are its
   parents.  While doing so, we reduce the redundant parents from the
   rewritten parent list by not just removing the identical ones, but also
   removing a parent that is an ancestor of another parent.

 * After the above parent simplification, if the commit is a root commit,
   an UNINTERESTING commit, a merge commit, or modifies the paths we are
   interested in, then the replacement commit of the commit is itself.  In
   other words, such a commit is not dropped from the final result.

The first point above essentially means that the history is rewritten in
the bottom up direction.  We can rewrite the parent list of a commit only
after we know how all of its parents are rewritten.  This means that the
processing needs to happen on the full history (i.e. after limit_list()).

Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 8 insertions, 2 deletions

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 3aa38097e..ee6822a85 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -193,12 +193,18 @@ endif::git-rev-list[]
 
 --full-history::
 
-	Show also parts of history irrelevant to current state of a given
-	path. This turns off history simplification, which removed merges
+	Show also parts of history irrelevant to current state of given
+	paths. This turns off history simplification, which removed merges
 	which didn't change anything at all at some child. It will still actually
 	simplify away merges that didn't change anything at all into either
 	child.
 
+--simplify-merges::
+
+	Simplify away commits that did not change the given paths, similar
+	to `--full-history`, and further remove merges none of whose
+	parent history changes the given paths.
+
 --no-merges::
 
 	Do not print commits with more than one parent.