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

Re: [RFC/PATCH 3/4] 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                |   76 +++++++++++++++++++++++++++++--------------
 2 files changed, 93 insertions(+), 26 deletions(-)

diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
index 2af33d8..e94d26b 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 for the merge, git will try to
+reduce the number of commits (real parents) by eliminating commits
+than can be reached from other commits.  The commit message will
+reflect the actual commits specified but the merge strategy will be
+selected based on the real parents, but always including `HEAD`.  The
+real parents (only including `HEAD` if it is real) 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 current `HEAD` of master:
+
+------------
+                    o---o---o  topicB
+                   /
+          o---o---o  topicA
+         /
+    o---o---o---o---o---o  master
+                         \
+                          o---o  topicC
+------------
+
+A merger of master with topicA, topicB, and topicC 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 only real 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 2acd2cc..5398606 100755
--- a/git-merge.sh
+++ b/git-merge.sh
@@ -209,24 +209,41 @@ parse_config () {

 # Find real parents
 # Set the following variables as followd:
-#   real_parents: The parents specified on the command line
+#   real_parents: The real parents except fast forward of head
 #   common:       All common ancestors or not_queried
 #   ff_head:      Fast forward of head
 find_real_parents () {
-       real_parents=$(git rev-parse "$@")
-       real_parents=${real_parents#$LF}
-       if test $# = 1
+       if test $fast_forward = never
        then
-               common=$(git merge-base --all $head "$@")
-               if test "$common" = $head
+               real_parents=$(git rev-parse "$@")
+               ff_head=$head
+               common=not_queried
+       else
+               if test $# = 1
                then
-                       ff_head=$1
+                       common=$(git merge-base --all $head "$1")
+                       if test "$common" = $head
+                       then
+                               real_parents=
+                               ff_head=$1
+                       elif test "$common" = "$1"
+                       then
+                               real_parents=
+                               ff_head=$head
+                       else
+                               real_parents=$1
+                               ff_head=$head
+
+                       fi
                else
-                       ff_head=$head
+                       real_parents=$(git show-branch --independent $head "$@")
+                       # Here we may actually lie about which bransh
is ff of head.
+                       # This will preserve the order the user gave.
+                       ff_head=${real_parents%%$LF*}
+                       real_parents=${real_parents#$ff_head}
+                       real_parents=${real_parents#$LF}
+                       common=not_queried
                fi
-       else
-               common=not_queried
-               ff_head=$head
        fi
 }

@@ -319,6 +336,12 @@ set x $remoteheads ; shift

 find_real_parents "$@"

+if test -n "$real_parents"
+then
+       test $head = $ff_head ||
+               real_parents="$ff_head$LF$real_parents"
+fi
+
 case "$use_strategies" in
 '')
        case "$real_parents" in
@@ -366,13 +389,13 @@ done

 echo "$head" >"$GIT_DIR/ORIG_HEAD"

-if true
+if test -z "$real_parents"
 then
-       if test $head = $ff_head -a "$common" = "$real_parents"
+       if test $head = $ff_head
        then
                finish_up_to_date "Already up-to-date."
                exit 0
-       elif test $fast_forward != never -a $ff_head = "$real_parents"
+       elif test $fast_forward != never
        then
                echo "Updating $(git rev-parse --short $head)..$(git
rev-parse --short $ff_head)"
                git update-index --refresh 2>/dev/null
@@ -386,6 +409,14 @@ then
                finish "$new_head" "$msg" || exit
                dropsave
                exit 0
+       else
+               real_parents="$ff_head"
+               ff_head=$head
+       fi
+else
+       if test $head != $ff_head -a $fast_forward = never
+       then
+               real_parents="$ff_head$LF$real_parents"
        fi
 fi

@@ -500,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 && real_parents="$head$LF$real_parents"
+       parents=$(echo "$real_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.

-- 
Sverre Hvammen Johansen

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

[Jakub Narebski]

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

> See the documentation for an explanation of this feature.

That's good that the feature is documented. But I'd like to see 1.)
why this feature is implemented, and perhaps also 2.) how this feature
is implemented (for example: uses find_real_parents() function.
 
> +If more than one commit are specified for the merge, git will try to
> +reduce the number of commits (real parents) by eliminating commits
> +than can be reached from other commits.  The commit message will
> +reflect the actual commits specified but the merge strategy will be
> +selected based on the real parents, but always including `HEAD`.  The
> +real parents (only including `HEAD` if it is real) are the parents
> +recorded in the merge commit object.

By "real" you mean "reduced" set of commits to merge?  This is not
clear enough, IMHO.

You would have to defend that recording reduced set of parents is a
good idea (is it always done, or does --ff=never has side-effect of
recording _specified_ parents for a merge?).

-- 
Jakub Narebski
Poland
ShadeHawk on #git

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

[Junio C Hamano]

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

> @@ -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 for the merge, git will try to
> +reduce the number of commits (real parents) by eliminating commits
> +than can be reached from other commits...

In 3/4 you defined "real parents" as "the commits specified to be merged
from the command line", and you are picking only the independent ones out
of "real parents" to change the set of parents used for the merge
operation.  What is the reduced set called?

> +...  The commit message will
> +reflect the actual commits specified but the merge strategy will be
> +selected based on the real parents, but always including `HEAD`....

Now your terminology gets the other way around and reduced ones are called
"real" and the earlier "real parents" are now called "actual".

I think "real" vs "actual" is an invitation for "which is which"
confusion.  How about calling them "given" vs "reduced"?

Anyway, "the commit log message talks about the commits specified by the
end user, but the command outsmarts the user and does something different".

> +... The
> +real parents (only including `HEAD` if it is real) are the parents
> +recorded in the merge commit object.

Specifically, "does something different" above is "does not record some of
the commits given by the end user as parent commit of the resulting
merge".  Hence the name of the operation: "head reduction".

While I suspect that it would make sense to simplify parents, I do not
see why the seemingly deliberate discrepancy between what is recorded as
the parents (i.e. "reduced parents" on "parent " lines of the resulting
merge) and what the log message talks about (i.e. "given parents" you feed
to fmt-merge-msg) is a good idea.  Isn't it more consistent and easier to
explain to the users if they match?  Also it might be arguable that this
head reduction should be an optional feature.

> +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 current `HEAD` of master:

We do not say "HEAD of branch".  HEAD spelled in all capital always means
"that pointer thing directly under $GIT_DIR that typically talks about
which branch we are on but sometimes can be detached to name a commit
directly."  Call it the "tip of the master branch".

> +------------
> +                    o---o---o  topicB
> +                   /
> +          o---o---o  topicA
> +         /
> +    o---o---o---o---o---o  master
> +                         \
> +                          o---o  topicC
> +------------
> +
> +A merger of master with topicA, topicB, and topicC will select the

"Merging topicA, B and C to the master branch will select" may be easier
to understand.

> +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 only real parents and are therefore the only
> +parents recorded in the merge commit object:

> +------------
> +         % git checkout master
> +         % git merge topicA topicB topicC

Please do not use C-shell in our examples.

> +
> +                    o---o---o  topicB
> +                   /         \
> +          o---o---o  topicA   \
> +         /                     \
> +    o---o---o---o---o---o       o  master
> +                         \     /
> +                          o---o  topicC
> +------------

I suspect this would be a _very_ unexpected behaviour to untrained eyes
and would be a source of confusion.  You were on 'master' and merged many
things into it, but the resulting commit does not have 'master' as its
first parent.  So far, ORIG_HEAD would always have matched HEAD^1 unless
you fast-forwarded.  This alone may be a reason enough that this behaviour
can never be the default.

> diff --git a/git-merge.sh b/git-merge.sh
> index 2acd2cc..5398606 100755
> --- a/git-merge.sh
> +++ b/git-merge.sh
> @@ -209,24 +209,41 @@ parse_config () {
> ...
> +                       # This will preserve the order the user gave.
> +                       ff_head=${real_parents%%$LF*}

"%%$LF*"?  Heh, that's clever.

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

[Sverre Hvammen Johansen]

On Wed, Mar 26, 2008 at 9:17 AM, Junio C Hamano <gitster@pobox.com> wrote:
>  In 3/4 you defined "real parents" as "the commits specified to be merged
>  from the command line", and you are picking only the independent ones out
>  of "real parents" to change the set of parents used for the merge
>  operation.  What is the reduced set called?

I was not happy about the split.  2/4 does not make much sense until
you read 3/4, and when you read 3/4 you are confused by 2/4.  Is it OK
that I squash these together again?

>  I think "real" vs "actual" is an invitation for "which is which"
>  confusion.  How about calling them "given" vs "reduced"?

Agree.  But reduced may not be reduced if --ff=never is specified.

>  Anyway, "the commit log message talks about the commits specified by the
>  end user, but the command outsmarts the user and does something different".

This is also the current behavior of git and I don't think anyone have
complained about it until now that we realize how git is actually
doing this.  We want the history to be as simple as possible when
presented in gitk, but the commit message should record what the user
asked for.   The commit message is used for later refferense.  The
commit message will usually only contain branch names which may or may
not make sense when we later look back the history.  That two branches
happen to point to the same commit or one is a fast forward of the
other is just a coincident.  I believe this is how most users want it
and I don't intend to change the log message.

>  > +... The
>
> > +real parents (only including `HEAD` if it is real) are the parents
>  > +recorded in the merge commit object.
>
>  Specifically, "does something different" above is "does not record some of
>  the commits given by the end user as parent commit of the resulting
>  merge".  Hence the name of the operation: "head reduction".
>
>  While I suspect that it would make sense to simplify parents, I do not
>  see why the seemingly deliberate discrepancy between what is recorded as
>  the parents (i.e. "reduced parents" on "parent " lines of the resulting
>  merge) and what the log message talks about (i.e. "given parents" you feed
>  to fmt-merge-msg) is a good idea.  Isn't it more consistent and easier to
>  explain to the users if they match?  Also it might be arguable that this
>  head reduction should be an optional feature.

If you use --ff=never it is turned off.

>  I suspect this would be a _very_ unexpected behaviour to untrained eyes
>  and would be a source of confusion.  You were on 'master' and merged many
>  things into it, but the resulting commit does not have 'master' as its
>  first parent.  So far, ORIG_HEAD would always have matched HEAD^1 unless
>  you fast-forwarded.  This alone may be a reason enough that this behaviour
>  can never be the default.

I am not sure we need to explain this in the manual.  What do you think?

This behavior is also the current behavior of git.  I don't think we
should care.  When we fast-forward, HEAD^1 may not match ORIG_HEAD
anyway.

-- 
Sverre Hvammen Johansen