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

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

[Sverre Hvammen Johansen]

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

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

[Jakub Narebski]

"Sverre Hvammen Johansen" <hvammen@gmail.com> writes:

> See the documentation for an explanation of this feature.

I think I get the idea now.

You want to generalize fast-forward merge, or what's equivalent make
fast-formard merge to be special case of head reduction.  This should
be written both in commit message and in documentation.  Do I
understand your goal correctly?

With head reduction comes three things:
 * the merge strategy used
 * recorded parents
 * generated merge commit message
The simplest way would be to use reduced head for all three things,
I think.

But I also think that this commit in series is the most controversial
one; is it realy needed for other commits?  I would put it then as the
last commit in series...
 
> +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.

Is it a correct solution, to use provided (specified) heads for
generation of merge commit message, but use reduced heads for
selecting merge strategy _and_ also as parents recorded in merge
commits?  Perhaps it is; but IMHO you should have written it in the
commit message, and defend this decision in commit message.

> +
> +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
> +------------

I think I would start with simpler example without 'topicC', of
reduction of octopus to two-parent ordinary merge.

> 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 "$@")

This was introduced by some of your earlier commits, isn't it?

[...]
-- 
Jakub Narebski
Poland
ShadeHawk on #git

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

[Sverre Hvammen Johansen]

On Fri, Apr 25, 2008 at 3:31 AM, Jakub Narebski <jnareb@gmail.com> wrote:
> "Sverre Hvammen Johansen" <hvammen@gmail.com> writes:
>
>  > See the documentation for an explanation of this feature.
>
>  I think I get the idea now.
>
>  You want to generalize fast-forward merge, or what's equivalent make
>  fast-formard merge to be special case of head reduction.  This should
>  be written both in commit message and in documentation.  Do I
>  understand your goal correctly?
>
>  With head reduction comes three things:
>   * the merge strategy used
>   * recorded parents
>   * generated merge commit message

The recorded parents and the generated merge commit message is the
same with or without this patch.  The only difference is the merge
strategy used.

>  The simplest way would be to use reduced head for all three things,
>  I think.

Actually, we can't do that.  A real merge always need to involve HEAD.
 In the case that HEAD is not included in the reduced parents we could
do a FF+merge, but that is a rather radical change that deserve its
own patch.

Changing the generated merge commit message is also a radical change.

I don't intend to write any patches for this for now.  Maybe later if
the series gets accepted.

>  But I also think that this commit in series is the most controversial
>  one; is it realy needed for other commits?  I would put it then as the
>  last commit in series...

I agree with you, but I don't intend to spend time on this now to
rewrite it again.  I am quite happy with how the series turned out.

>  > +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
>  > +------------
>
>  I think I would start with simpler example without 'topicC', of
>  reduction of octopus to two-parent ordinary merge.

I am not sure that we need to have this in the documentation at all.
I have asked for comments on this before but not received any
feedback.  This late, the documentation will have to be fixed in-tree,
if needed.

>  > 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 "$@")
>
>  This was introduced by some of your earlier commits, isn't it?

Yes,  [PATCH 3/5] Restructure git-merge.sh

-- 
Sverre Hvammen Johansen