[PATCH 4/5] Head reduction before selecting merge strategy

["Sverre Hvammen Johansen" <hvammen@gmail.com>]

See the documentation for an explanation of this feature.

Signed-off-by: Sverre Hvammen Johansen <hvammen@gmail.com>
---
 Documentation/git-merge.txt |   43 ++++++++++++++++++++++++++++++++++++-
 git-merge.sh                |   50 ++++++++++++++++++++++++-------------------
 2 files changed, 70 insertions(+), 23 deletions(-)

diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
index 2af33d8..f6bc96f 100644
--- a/Documentation/git-merge.txt
+++ b/Documentation/git-merge.txt
@@ -36,7 +36,7 @@ include::merge-options.txt[]
 <remote>::
        Other branch head merged into our branch.  You need at
        least one <remote>.  Specifying more than one <remote>
-       obviously means you are trying an Octopus.
+       usually means you are trying an Octopus.


 include::fast-forward-options.txt[]
@@ -133,6 +133,47 @@ merge (which is typically a fraction of the whole
tree), you can
 have local modifications in your working tree as long as they do
 not overlap with what the merge updates.

+If more than one commit are specified on the command line, git will
+try to reduce the number of commits used (reduced parents) by
+eliminating commits than can be reached from other commits.  The
+commit message will reflect the commits specified on the command line
+but the merge strategy will be selected based on the reduced parents
+including `HEAD`.  The reduced parents are the parents recorded in the
+merge commit object.
+
+The following shows master and three topic branches.  topicB is based
+on topicA, topicA is previously branched off from master, and topicC
+is based on the tip of the master branch:
+
+------------
+                    o---o---o  topicB
+                   /
+          o---o---o  topicA
+         /
+    o---o---o---o---o---o  master
+                         \
+                          o---o  topicC
+------------
+
+Merging topicA, B and C to the master branch will select the merge
+strategy based on the three branches master, topicB, and topicC
+(topicA is eliminated since it can be reached from topicB).  topicB
+and topicC are the reduced parents and are therefore the only
+parents recorded in the merge commit object:
+
+------------
+         $ git checkout master
+         $ git merge topicA topicB topicC
+
+                    o---o---o  topicB
+                   /         \
+          o---o---o  topicA   \
+         /                     \
+    o---o---o---o---o---o       o  master
+                         \     /
+                          o---o  topicC
+------------
+
 When there are conflicts, these things happen:

 1. `HEAD` stays the same.
diff --git a/git-merge.sh b/git-merge.sh
index 7c34b6c..7c70c56 100755
--- a/git-merge.sh
+++ b/git-merge.sh
@@ -337,11 +337,16 @@ set x $remoteheads ; shift

 find_reduced_parents "$@"

-actual_parents=$(git rev-parse "$@")
+# ff_head may be included here or later in actual parents
+if test -n "$reduced_parents"
+then
+       test $head = $ff_head ||
+               reduced_parents="$ff_head$LF$reduced_parents"
+fi

 case "$use_strategies" in
 '')
-       case "$actual_parents" in
+       case "$reduced_parents" in
        ?*"$LF"?*)
                var="`git config --get pull.octopus`"
                if test -n "$var"
@@ -406,17 +411,23 @@ then
                finish "$new_head" "$msg" || exit
                dropsave
                exit 0
+       else
+               reduced_parents="$ff_head"
+               ff_head=$head
        fi
+else
+       test $head != $ff_head -a $fast_forward = never &&
+               reduced_parents="$ff_head$LF$reduced_parents"
 fi

-case "$actual_parents" in
+case "$reduced_parents" in
 ?*"$LF"?*)
-       # We have more than one actual parent
-       common=$(git show-branch --merge-base $head $actual_parents)
+       # We have more than one reduced parent
+       common=$(git show-branch --merge-base $head $reduced_parents)
        ;;
 *)
-       # We have exactly one actual parent
-       test "$common" != not_queried || common=$(git merge-base --all
$head $actual_parents)
+       # We have exactly one reduced parent
+       test "$common" != not_queried || common=$(git merge-base --all
$head $reduced_parents)
        case "$common" in
        ?*"$LF"?*)
                # We are not doing octopus and not fast forward.  Need a
@@ -429,13 +440,13 @@ case "$actual_parents" in
                        # See if it is really trivial.
                        git var GIT_COMMITTER_IDENT >/dev/null || exit
                        echo "Trying really trivial in-index merge..."
-                       if git read-tree --trivial -m -u -v $common
$head $actual_parents &&
+                       if git read-tree --trivial -m -u -v $common
$head $reduced_parents &&
                                result_tree=$(git write-tree)
                        then
                                echo "Wonderful."
                                result_commit=$(
                                        printf '%s\n' "$merge_msg" |
-                                       git commit-tree $result_tree
-p HEAD -p $actual_parents
+                                       git commit-tree $result_tree
-p HEAD -p $reduced_parents
                                ) || exit
                                finish "$result_commit" "In-index merge"
                                dropsave
@@ -484,7 +495,7 @@ do
     # Remember which strategy left the state in the working tree
     wt_strategy=$strategy

-    git-merge-$strategy $common -- "$head_arg" $actual_parents
+    git-merge-$strategy $common -- "$head_arg" $reduced_parents
     exit=$?
     if test "$no_commit" = t && test "$exit" = 0
     then
@@ -520,17 +531,12 @@ done
 # auto resolved the merge cleanly.
 if test '' != "$result_tree"
 then
-    if test $fast_forward = allow
-    then
-        parents=$(git show-branch --independent "$head" "$@")
-    else
-        parents=$(git rev-parse "$head" "$@")
-    fi
-    parents=$(echo "$parents" | sed -e 's/^/-p /')
-    result_commit=$(printf '%s\n' "$merge_msg" | git commit-tree
$result_tree $parents) || exit
-    finish "$result_commit" "Merge made by $wt_strategy."
-    dropsave
-    exit 0
+       test $head = $ff_head && reduced_parents="$head$LF$reduced_parents"
+       parents=$(echo "$reduced_parents" | sed -e 's/^/-p /')
+       result_commit=$(printf '%s\n' "$merge_msg" | git commit-tree
$result_tree $parents) || exit
+       finish "$result_commit" "Merge made by $wt_strategy."
+       dropsave
+       exit 0
 fi

 # Pick the result from the best strategy and have the user fix it up.
@@ -554,7 +560,7 @@ case "$best_strategy" in
        echo "Rewinding the tree to pristine..."
        restorestate
        echo "Using the $best_strategy to prepare resolving by hand."
-       git-merge-$best_strategy $common -- "$head_arg" $actual_parents
+       git-merge-$best_strategy $common -- "$head_arg" $reduced_parents
        ;;
 esac

-- 
Sverre Hvammen Johansen