"git rebase" loses the additional changes in "evil" merges

"git rebase" loses the additional changes in "evil" merges

[Dale R. Worley]

(git version 1.7.7.6)

I've been learning how to use Git.  While exploring "git rebase", I've
discovered that if the branch being rebased contains an "evil" merge,
that is, a merge which contains changes that are in addition to the
changes in any of the parent commits, the rebase operation will
silenty lose those additional changes.

I believe that this is a serious bug.

The problem is not that Git does not propagate the additional changes
(although I'd like it to do so), the problem is that the rebase
*silently loses* changes in the code.  It would be acceptable if Git
detected the evil merge, notified me of it, and forced me to manually
re-do it in order to finish the rebase.

Throughout the Git design (as in other SCMs), care has been taken to
not lose changes that the user has introduced.  In this situation,
that principle is violated.

I have a script that demonstrates this failure, if that would be
useful for testing purposes.

Dale

Re: "git rebase" loses the additional changes in "evil" merges

[Junio C Hamano]

worley@alum.mit.edu (Dale R. Worley) writes:

> (git version 1.7.7.6)
>
> I've been learning how to use Git.  While exploring "git rebase", I've
> discovered that if the branch being rebased contains an "evil" merge,
> that is, a merge which contains changes that are in addition to the
> changes in any of the parent commits, the rebase operation will
> silenty lose those additional changes.

I think this is to be expected for "git rebase", as it does not even
look at merges.  It is a way to find non-merge commits that haven't
been applied yet, and apply them to the upstream to create a new
linear history.

Re: "git rebase" loses the additional changes in "evil" merges

[Thomas Rast]

Junio C Hamano <gitster@pobox.com> writes:

> worley@alum.mit.edu (Dale R. Worley) writes:
>
>> (git version 1.7.7.6)
>>
>> I've been learning how to use Git.  While exploring "git rebase", I've
>> discovered that if the branch being rebased contains an "evil" merge,
>> that is, a merge which contains changes that are in addition to the
>> changes in any of the parent commits, the rebase operation will
>> silenty lose those additional changes.
>
> I think this is to be expected for "git rebase", as it does not even
> look at merges.  It is a way to find non-merge commits that haven't
> been applied yet, and apply them to the upstream to create a new
> linear history.

I can see the problem with --preserve-merges though.  It will actually
just *redo* the merge; the name is wrong in the sense that it undertakes
nothing to preserve whatever evilness was in it.

I suppose in theory it could first redo the merge on the original
parents, and diff against the existing merge; that would be the evilness
component.  Then it could attempt to apply the same evilness on the new
merge.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch

Re: "git rebase" loses the additional changes in "evil" merges

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> Junio C Hamano <gitster@pobox.com> writes:
>
>> worley@alum.mit.edu (Dale R. Worley) writes:
>>
>>> (git version 1.7.7.6)
>>>
>>> I've been learning how to use Git.  While exploring "git rebase", I've
>>> discovered that if the branch being rebased contains an "evil" merge,
>>> that is, a merge which contains changes that are in addition to the
>>> changes in any of the parent commits, the rebase operation will
>>> silenty lose those additional changes.
>>
>> I think this is to be expected for "git rebase", as it does not even
>> look at merges.  It is a way to find non-merge commits that haven't
>> been applied yet, and apply them to the upstream to create a new
>> linear history.
>
> I can see the problem with --preserve-merges though.  It will actually
> just *redo* the merge; the name is wrong in the sense that it undertakes
> nothing to preserve whatever evilness was in it.

With or without evil, preserve-merges have other issues to make me
not to trust it. Which side branches to take literally (i.e. just
merge again) vs which side branches to also rebase (i.e. rebuild the
history and then merge).

It was suggested to make it apply the first-parent diff and record
the result, I think.  If that were an acceptable approach (I didn't
think about it through myself, though), that would automatically
cover the evil-merge case as well.

Re: "git rebase" loses the additional changes in "evil" merges

[Dale Worley]

> From: Junio C Hamano <gitster@pobox.com>
> 
> I think this is to be expected for "git rebase", as it does not even
> look at merges.  It is a way to find non-merge commits that haven't
> been applied yet, and apply them to the upstream to create a new
> linear history.

I disagree. "git rebase" is not characterized as a way to "find
non-merge commits that haven't been applied yet", but rather (as
described in the git-rebase manual page):
 
    git-rebase - Forward-port local commits to the updated upstream head

    All changes made by commits in the current branch but that are not
    in <upstream> are saved to a temporary area. [...]  The commits
    that were previously saved into the temporary area are then
    reapplied to the current branch, one by one, in order.

Now if you read far enough down the page, I'm sure it warns about
merge commits.  But the stated basic *intention* is to replicate the
existing branch, re-rooted at a new place on the upstream branch.

The current implementation fails this intention by losing changes made
in merges.  It fails this intention in a *dangerous* way by causing
changes to be lost without warning.

Dale

Re: "git rebase" loses the additional changes in "evil" merges

[Junio C Hamano]

Dale Worley <worley@c-66-31-108-177.hsd1.ma.comcast.net> writes:

>> From: Junio C Hamano <gitster@pobox.com>
>> 
>> I think this is to be expected for "git rebase", as it does not even
>> look at merges.  It is a way to find non-merge commits that haven't
>> been applied yet, and apply them to the upstream to create a new
>> linear history.
>
> I disagree. "git rebase" is not characterized as ...

The intention has always been "I have these patches, some were
applied upstream already, now what do I have left?".

You do realize that you are disagreeing with somebody who designed
the original "git rebase" (before the --preserve-merges was added),
do you?

Re: "git rebase" loses the additional changes in "evil" merges

[Philip Oakley]

From: "Junio C Hamano" <gitster@pobox.com>
Sent: Tuesday, March 05, 2013 9:35 PM
> Dale Worley <worley@c-66-31-108-177.hsd1.ma.comcast.net> writes:
>
>>> From: Junio C Hamano <gitster@pobox.com>
>>>
>>> I think this is to be expected for "git rebase", as it does not even
>>> look at merges.  It is a way to find non-merge commits that haven't
>>> been applied yet, and apply them to the upstream to create a new
>>> linear history.
>>
>> I disagree. "git rebase" is not characterized as ...
>
> The intention has always been "I have these patches, some were
> applied upstream already, now what do I have left?".

Given that many folk appear to trip up with their rebase mindset, does
this suggest that a few tweaks to the manual may be in order to stop
such misunderstandings?

Perhaps:
    git-rebase - Forward-port local commits, not in upstream,
     to the updated upstream head

and to avoid "hidden" asides, add a few more paragraph breaks into the
description texts, and perhaps bring the "Note that any commits in HEAD
which introduce the same textual changes as a commit in HEAD..<upstream>
are omitted" sentence nearer the start.

That is, don't let folks get a too simplistic view of rebase, missing 
its
hidden powers.

>
> You do realize that you are disagreeing with somebody who designed
> the original "git rebase" (before the --preserve-merges was added),
> do you?

However the broader userbase brings with it a better class of fool ;-)

Re: "git rebase" loses the additional changes in "evil" merges

[Junio C Hamano]

"Philip Oakley" <philipoakley@iee.org> writes:

> Given that many folk appear to trip up with their rebase mindset, does
> this suggest that a few tweaks to the manual may be in order to stop
> such misunderstandings?

Perhaps.

What I want rebase to do

[Dale R. Worley]

This is how I see what rebase should do:

The simple case for rebase starts from

               P---Q---R---S master
                    \
                     A---B---C topic

Then "git checkout topic ; git rebase master" will change it to

               P---Q---R---S master
                            \
                             A'--B'--C' topic

A' is created by a three-way merge that can be symbolized

        Q-->S
        |   |
        v   v
        A-->A'

That is, Q, applying the changes from Q to A and the changes from Q to
S, becomes A'.

After that

        A-->A'
        |   |
        v   v
        B-->B'
        |   |
        v   v
        C-->C'

A more complex case is when there is a merge from an external source

               P---Q---R---S master
                    \
                     A---M---C topic
                        /
                    ---X

We want to produce

               P---Q---R---S master
                            \
                             A'--M'--C' topic
                                /
                            ---X

So we have to merge

        Q-->S
        |   |
        v   v
        A-->A'
        |   |
        v   v
        M-->M'
        |   |
        v   v
        C-->C'

Any "evil" changes in M will be in the changes A->M (along with the
changes introduced from X), and so they will be reincorporated in
A'->M'.  M' lists A' and X as its parents.  (And not M!)

If there is an internal merge in the topic branch, things look like
this

               P---Q---R---S master
                    \
                     \   B
                      \ / \
                       A   M---D topic
                        \ /
                         C

and we want to produce this

               P---Q---R---S master
                            \
                             \    B'
                              \  /  \
                               A'    M'--D' topic
                                 \  /
                                  C'

Which can be done with these merges


        Q-->S
        |   |
        v   v
        A-->A'        A-->A'
        |   |         |   | 
        v   v         v   v 
        B-->B'        C-->C'

There are two choices for constructing M' (which ought to produce the
same results under ordinary circumstances)

        B-->B'        C-->C'
        |   |         |   | 
        v   v         v   v 
        M-->M'        M-->M'

and finally

        M-->M'
        |   |
        v   v
        D-->D'

Dale

Re: What I want rebase to do

[Thomas Rast]

worley@alum.mit.edu (Dale R. Worley) writes:
[...snip...]

Isn't that just a very long-winded way of restating what Junio said
earlier:

> > It was suggested to make it apply the first-parent diff and record
> > the result, I think.  If that were an acceptable approach (I didn't
> > think about it through myself, though), that would automatically
> > cover the evil-merge case as well.

You can fake that with something like

git rev-list --first-parent --reverse RANGE_TO_REBASE |
while read rev; do
    if git rev-parse $rev^2 >/dev/null 2>&1; then
        git cherry-pick -n -m1 $rev
        git rev-parse $rev^2 >.git/MERGE_HEAD
        git commit -C$rev
    else
        git cherry-pick $rev
    fi
done

Only tested very lightly.  Dealing with octopii, conflicts and actually
preserving the commit's attributes is left as an exercise to the
reader[1].

I still think that the _right_ solution is first redoing the merge on
its original parents and then seeing how the actual merge differs from
that.  --preserve-merges has bigger issues though, like Junio said.

Perhaps a new option to git-rebase could trigger the above behavior for
merges, who knows.  (It could be called --first-parent.)


[1]  If you don't get the sarcasm: that would amount to reinventing
large parts of git-rebase.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch

Re: What I want rebase to do

[Johannes Sixt]

Am 3/7/2013 9:48, schrieb Thomas Rast:
> worley@alum.mit.edu (Dale R. Worley) writes:
> [...snip...]
> 
> Isn't that just a very long-winded way of restating what Junio said
> earlier:
> 
>>> It was suggested to make it apply the first-parent diff and record
>>> the result, I think.  If that were an acceptable approach (I didn't
>>> think about it through myself, though), that would automatically
>>> cover the evil-merge case as well.
> 
> You can fake that with something like
> 
> git rev-list --first-parent --reverse RANGE_TO_REBASE |
> while read rev; do
>     if git rev-parse $rev^2 >/dev/null 2>&1; then
>         git cherry-pick -n -m1 $rev
>         git rev-parse $rev^2 >.git/MERGE_HEAD
>         git commit -C$rev
>     else
>         git cherry-pick $rev
>     fi
> done
> 
> Only tested very lightly.  Dealing with octopii, conflicts and actually
> preserving the commit's attributes is left as an exercise to the
> reader[1].

I proposed this long ago, but by modifying preserve-merges rather than
with a new option (--first-parent):
http://thread.gmane.org/gmane.comp.version-control.git/198125

It works very well. I'm using it frequently in the field.

-- Hannes

Re: What I want rebase to do

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> I still think that the _right_ solution is first redoing the merge on
> its original parents and then seeing how the actual merge differs from
> that.

I think that is what was suggested in

    http://article.gmane.org/gmane.comp.version-control.git/198316

> Perhaps a new option to git-rebase could trigger the above behavior for
> merges, who knows.  (It could be called --first-parent.)

Yeah, I think that is what the old thread concluded to be the way to
move forward:

    http://thread.gmane.org/gmane.comp.version-control.git/198125

I'll throw it in to the "leftover bits".

    http://git-blame.blogspot.com/2013/02/more-leftover-bits.html

Re: What I want rebase to do

[Dale R. Worley]

> From: Thomas Rast <trast@student.ethz.ch>
> 
> worley@alum.mit.edu (Dale R. Worley) writes:
> [...snip...]
> 
> Isn't that just a very long-winded way of restating what Junio said
> earlier:
> 
> > > It was suggested to make it apply the first-parent diff and record
> > > the result, I think.  If that were an acceptable approach (I didn't
> > > think about it through myself, though), that would automatically
> > > cover the evil-merge case as well.

Well, I believe what I said was a fleshed-out way of saying what I
*think* Junio said, but...

> You can fake that with something like
> 
> git rev-list --first-parent --reverse RANGE_TO_REBASE |
> while read rev; do
>     if git rev-parse $rev^2 >/dev/null 2>&1; then
>         git cherry-pick -n -m1 $rev
>         git rev-parse $rev^2 >.git/MERGE_HEAD
>         git commit -C$rev
>     else
>         git cherry-pick $rev
>     fi
> done

This code doesn't do that.  I don't want something that rebases a
single thread of the current branch, I want something that rebases
*all* the commits between the head commit and the merge base.  Which
is what is illustrated in my message.

> [1]  If you don't get the sarcasm: that would amount to reinventing
> large parts of git-rebase.

Yes, that is the point of the exercise.

I've done a proof-of-concept implementation of what I want to see,
calling it git-rebase--merge-safe.  But I'm new here and likely that
is a pretty crude solution.  I suspect that a real implementation
could be done by inserting this logic into the framework of
git-filter-tree.  Following is git-rebase--merge-safe, and the script
I use to test it (and explore rebase problems).

Dale
----------------------------------------------------------------------
git-rebase--merge-safe

#!/bin/bash

. git-sh-setup

prec=4

set -ex

# Ensure the work tree is clean.
require_clean_work_tree "rebase" "Please commit or stash them."

onto_name=$1        
onto=$(git rev-parse --verify "${onto_name}^0") ||
    die "Does not point to a valid commit: $1"

head_name=$( git symbolic-ref HEAD )
orig_head=$(git rev-parse --verify $head_name) ||
    exit 1

echo onto=$onto
echo head_name=$head_name
echo orig_head=$orig_head

# Get the merge base, which is the root of the branch that we are rebasing.
# (For now, ignore the question of whether there is more than one merge base.)
mb=$(git merge-base "$onto" "$orig_head")
echo mb=$mb

# Get the list of commits to rebase, which is everything between $mb and
# $orig_head.
# Note that $mb is not included.
revisions=`git rev-list --reverse --ancestry-path $mb..$orig_head`
echo revisions=$revisions

# Set up the list mapping the commits on the original branch to the commits
# on the branch we are creating.
# Its format is ",old-hash1/new-hash1,old-hash2/new-hash2,...,".
# The initial value maps $mb to $onto.
map=",$mb/$onto,"

# Export these so git commit can see them.
export GIT_AUTHOR_NAME GIT_AUTHOR_EMAIL GIT_AUTHOR_DATE

# Process each commit in forward topological order.
for cmt in $revisions
do
    # Examine the commit to extract information we will need to reconstruct it.
    # First parent of the commit that has a mapping, i.e., is part of the
    # branch (and has thus been rebuilt already.
    first_mapped_parent=
    # The new commit that was made of $first_mapped_parent.
    first_mapped_parent_mapped=
    # List of -p options naming the parent commits, or their new commits if they
    # are in the branch.
    parents=
   # Dissect the old commit's data.
    # Output the commit data into FD 3.
    exec 3< <( git cat-file commit $cmt )

    while read keyword rest <&3
    do
	case $keyword in
	    tree)
		# Ignored
		;;
	    parent)
		# See if the parent is mapped, i.e., is in the
		# original branch.
		if [[ "$map" == *,$rest/* ]]
		then
		    # This parent has been mapped.  Get the new commit.
		    parent_mapped=${map#*,$rest/}
		    parent_mapped=${parent_mapped%%,*}
		    if test -z "$first_mapped_parent"
		    then
			first_mapped_parent=$rest
			first_mapped_parent_mapped=$parent_mapped
		    fi
		else
		    # This parent has not been mapped.
		    parent_mapped=$rest
		fi
		# $parent_mapped is a parent of the new commit.
		parents="$parents -p $parent_mapped"
		;;
	    author)
		# Extract the information about the author.
		GIT_AUTHOR_NAME="${rest%% <*}"
		GIT_AUTHOR_EMAIL="${rest##* <}"
		GIT_AUTHOR_EMAIL="${GIT_AUTHOR_EMAIL%%> *}"
		GIT_AUTHOR_DATE="${rest##*> }"
		;;
	    committer)
		# Ignored:  The new commit will have this use's name
		# as committer.
		;;
	    '')
		# End of fixed fields, remainder is the commit comment.
		# Leave contents of FD 3 queued to be read later by
		# git commit-tree.
		break
		;;
	    *)
		# Ignore all other keywords.
		;;
	esac
    done

    echo GIT_AUTHOR_NAME="$GIT_AUTHOR_NAME"
    echo GIT_AUTHOR_EMAIL="$GIT_AUTHOR_EMAIL"
    echo GIT_AUTHOR_DATE="$GIT_AUTHOR_DATE"
    echo parents="$parents"
    echo first_mapped_parent=$first_mapped_parent
    echo first_mapped_parent_mapped=$first_mapped_parent_mapped

    test -n "$first_mapped_parent" || exit 1

    # Do the three-way merge.
    # Empty the tree so git read-tree will merge into it.
    git read-tree --empty
    git read-tree -m --aggressive \
	$first_mapped_parent $cmt $first_mapped_parent_mapped
    git merge-index git-merge-one-file -a

    # Construct the file tree for the new commit.
    tree=$( git write-tree )

    # Create the new commit
    # Note that FD 3 contains the remainder of the commit description
    # from the git cat-file above.
    new_commit=$( git commit-tree $tree $parents <&3 )
    echo new_commit=$new_commit

    # Add the new commit to the map.
    map="$map$cmt/$new_commit,"

done

echo Final commit is $new_commit

# Update the branch pointers.
git update-ref ORIG_HEAD $orig_head
git update-ref $head_name $new_commit

# Go to the new head of the branch.
git checkout ${head_name#refs/heads/}
----------------------------------------------------------------------
script.fixed

set -e

# Create a temporary directory and go into it.
DIR=temp.$$
mkdir $DIR
cd $DIR

# Create a Git repository.
git init

# Create a file containing the lines 1 to 10.
seq 1 10 >file
git add file
git commit -m 'Commit A'

# Start the dev branch at commit A.
git branch dev HEAD

# Add lines 1.5, 2.5, and 3.5 in a series of commits on master.

# This sed command adds a line 1.5 before the line 2.
sed --in-place -e '/^2$/i1.5' file
git commit -a -m 'Commit B'

sed --in-place -e '/^3$/i2.5' file
git commit -a -m 'Commit C'

sed --in-place -e '/^4$/i3.5' file
git commit -a -m 'Commit D'

# Show the commit structure of master.
#git log --graph --oneline master
#git log --graph -p master
echo 'On master:'
cat file

# Go to the dev branch and create commits with a non-trivial merge.
git checkout dev

sed --in-place -e '/^5$/i4.5' file
git commit -a -m 'Commit P'

git branch dev1 HEAD

sed --in-place -e '/^6$/i5.5' file
git commit -a -m 'Commit Q'

git checkout dev1

sed --in-place -e '/^7$/i6.5' file
git commit -a -m 'Commit R'

git checkout dev

# Merge commits Q and R, but add the additional line 7.5 (to simulate
# fixes that were needed to resolve the merge).

git merge --no-commit dev1
sed --in-place -e '/^8$/i7.5' file
git commit -a -m 'Commit S'

sed --in-place -e '/^9$/i8.5' file
git commit -a -m 'Commit T'

# Show the commit structure of dev.
#git log --graph --oneline dev
# *** Note that the diffs do not show the line 7.5 added in commit S.
#git log --graph -p dev
echo 'On dev:'
cat file

# Show the branch structure.
git show-branch --sha1-name
git log --all --oneline --graph

# Rebase the dev branch to the tip of master using our hack script.
git checkout dev
git branch -f rebase dev
git checkout rebase
PATH=/usr/libexec/git-core:$PATH
../git-rebase--merge-safe master

# Show the commit structure.
git log --graph --oneline
# *** Note that the line 7.5 added in commit S isn't carried into the new branch.
git log --graph -p

echo 'After rebasing:'
cat file
----------------------------------------------------------------------
[EOF]