Please help provide clarity on git rebase internals

Please help provide clarity on git rebase internals

[Colin Yates]

Hi all,

TLDR; I am seeing merge conflicts when rebasing even though applying
them to HEAD of target branch should work. Can you please upgrade my
understanding so I understand.

My understanding is that rebasing branch B onto branch A unrolls all
of branch B's commits and then "reduces" them onto the HEAD of branch
A.

For example, I took featureA branch from develop three days ago.
develop subsequently had commits #d1, #d2 and #d3. featureA also had
#f1 and #f2 and in terms of time they are all intermingled.

My understanding of rebase is that after issuing "git fetch; git
rebase origin/develop" in featureA branch a git log should show #f2,
#f1, #d3, #d2, #d1.

I am seeing this, but sometimes I see something I can't explain and
that is a merge conflict as if git was doing a merge rather than a
rebase.

For example, let's imagine that #f1 removed fileA, some time later #d1
added a line to that file. If I was doing a merge then of course this
should be a conflict, however applying #f1 to develop HEAD should work
even if fileA has changed (i.e. #f1 removes the updated fileA).

As it is I am frequently running into merge conflicts in this manner
when it *appears* git is applying a patch from featureA onto develop
_as it was then the patch was made_.

I am also seeing merge conflicts that occur between commits in the
develop branch itself as well, which I assumed would be effectively
read-only.

In terms of functional programming I thought rebase was a pure reduce
of a sequence of patches from featureA branch onto HEAD.

I have no idea what git is doing internally, and if I am confident of
anything it is almost certainly that the bug is in my understanding
:).

What am I missing?

Thanks,

Col

Re: Please help provide clarity on git rebase internals

[Johannes Sixt]

Am 08.09.2014 13:25, schrieb Colin Yates:
> For example, let's imagine that #f1 removed fileA, some time later #d1

Assumption: #d1 is in the branch you call "develop HEAD".

> added a line to that file. If I was doing a merge then of course this
> should be a conflict, however applying #f1 to develop HEAD should work
> even if fileA has changed (i.e. #f1 removes the updated fileA).

No. You should get the very same conflict, because the content that #f1
removed is not identical to the content on develop HEAD anymore.

With rebase you generally get the same conflicts as if you did a merge.
But since rebase applies changes only piece-wise, you get the conflicts
also only piece-wise. (Sometimes you can be lucky that you get no
conflicts due to the nature of changes, sometimes you can also have bad
luck and see more conflicts.)

-- Hannes

Re: Please help provide clarity on git rebase internals

[Fabian Ruch]

Hi Colin,

On 09/08/2014 01:25 PM, Colin Yates wrote:
> My understanding is that rebasing branch B onto branch A unrolls all
> of branch B's commits and then "reduces" them onto the HEAD of branch
> A.
> 
> For example, I took featureA branch from develop three days ago.
> develop subsequently had commits #d1, #d2 and #d3. featureA also had
> #f1 and #f2 and in terms of time they are all intermingled.
> 
> My understanding of rebase is that after issuing "git fetch; git
> rebase origin/develop" in featureA branch a git log should show #f2,
> #f1, #d3, #d2, #d1.

Almost, it will show #f2', #f1', #d3, #d2, #d1. The commits #f1 and #f2
must be recreated because the changes they introduce are being applied
to a different base, that is a different tree. The result of rebasing
#f1 and #f2 will be a tree different from the one at the tip of branch
'featureA'.

> I am seeing this, but sometimes I see something I can't explain and
> that is a merge conflict as if git was doing a merge rather than a
> rebase.

A rebase is a series of patch applications to a base different from the
one they were created in relation to. If a patch context is different in
the new base, the patch cannot be applied by simply replacing '-' lines
with '+' lines and a merge of changes is required. That merge can fail
itself and we see merge conflicts. It's no contradiction that a merge
(of changes) is happening even though git is not doing a merge (of
branches).

> For example, let's imagine that #f1 removed fileA, some time later #d1
> added a line to that file. If I was doing a merge then of course this
> should be a conflict, however applying #f1 to develop HEAD should work
> even if fileA has changed (i.e. #f1 removes the updated fileA).

The commit #f1 does not just record the deletion of the file named
'fileA' but also a patch that removes every single line in that file.
Another way to view the behaviour of 'git rm' is that the command does
not remove names from the tree but objects that are given by both a name
and a content. The replay of #f1 on top of #d3 conflicts because the
patch cannot be applied, the content does not match respectively.

> As it is I am frequently running into merge conflicts in this manner
> when it *appears* git is applying a patch from featureA onto develop
> _as it was then the patch was made_.

I'm not sure if I'm understanding correctly, but I'd say it doesn't just
appear that way. First, git-rebase takes the patch that represents the
changes between develop@{3 days ago} and #f1 and applies it to #d3. The
result is commit #f1'. Then it applies the differences between #f1 and
#f2 to #f1', which in turn results in #f2'.

> I am also seeing merge conflicts that occur between commits in the
> develop branch itself as well, which I assumed would be effectively
> read-only.

You're right, the branch 'develop' shouldn't be touched at all if you
run 'git rebase develop' on branch 'featureA'. Do you mean "between
commits in the *featureA* branch itself" instead, i.e. it is unexpected
if the replay of #f2 fails after the replay of #f1 succeeded?

> In terms of functional programming I thought rebase was a pure reduce
> of a sequence of patches from featureA branch onto HEAD.

I like how you're viewing 'rebase' as, I guess, a right fold with the
base as the initial element and 'apply'/'cherry-pick' as the operator,
but I'm not sure what we can learn from this representation. Is it true
that there is an emphasis on "pure" here suggesting that this is where
the functional interpretation fails?

Cheers,
   Fabian