threads / rfc / 12869

patch, 4 partsRe: [RFC/PATCH 3/4] Head reduction before selecting merge strategy

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

## tl;dr

4 messages between Mar 26, 2008 and Mar 27, 2008. Diffs are folded; open one to read it.

replies: 3people: 3as markdown or json

Sverre Hvammen Johansen· Mar 26, 2008, 03:58 UTC · lore
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(-)
Show changes to 2 files +93 −26

Documentation/git-merge.txt, git-merge.sh

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
Jakub Narebski· Mar 26, 2008, 12:50 UTC · re: Sverre Hvammen Johansen · lore
"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.
 
Show 7 quoted lines
> +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
Junio C Hamano· Mar 26, 2008, 16:17 UTC · re: Sverre Hvammen Johansen · lore
"Sverre Hvammen Johansen" <hvammen@gmail.com> writes:
Show 8 quoted lines
> @@ -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".

Show 11 quoted lines
> +------------
> +                    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.
Show 9 quoted lines
> +
> +                    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.

Show 8 quoted lines
> 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.
Sverre Hvammen Johansen· Mar 27, 2008, 03:10 UTC · re: Junio C Hamano · lore
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.

Show 16 quoted lines
>  > +... 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.
Show 6 quoted lines
>  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

← back to recent threads