[RFC] cherry-pick using multiple parents to implement -x

I've been converting some old CVS repositories to git, and as it turns
out, these repositories consist of a number of main branches of the same
project that were created at several points in time (the stable release
branches), and the branches contain numerous backports (and a few
forward ports) between each other.

I.e. the branches split off each other at various points in time, and
evolved independently ever since (except for the numerous backports).

Now, the backports can be implemented using a mere "git cherry-pick -x",
but that creates this silly text references to the original commits.
I'd rather use something that gitk can visualise.

So I tried to use the parents of the commit to reference the origin(s).
I.e. the first parent links to the linear history on a given branch, but
the second (and possibly more) parents point to the cherry-picked
back-ported commit from another branch.  This graft-constructed
repository is then fed to filter-branch to make it permanent.
To view it try: git://pike-git.lysator.liu.se/pikex

This works quite well and shows the following results:
- gitk shows proper grafts.
- gitk properly shows a zero-diff between the new commit and the
  commits we cherry-picked from.
- It even works perfectly when picking from multiple parents.
- gitk is confused in its display of tags preceding and following this
  commit (depending on the situation it mixes up the branches).

Obviously the reason it works rather well is because git can actually
distinguish between a merge and a backport because of the way the
contents of the trees change.

The questions now are:
- Would there be good reason not to record the backport/forwardport
  relationship in the additional parents of a commit?
- Since most of the git machinery (git diff, and gitk, most notably)
  seem to work just fine when using parents for that purpose, would it
  be acceptable to create a patch to cherry-pick to support an option to
  record the backport/forwardport relationship in the second (or more)
  parent field(s)?
- And depending on an affirmative on the previous question, would it be
  acceptable to teach the gitk preceding/following tag listing to deal
  with these backport/forwardports ?
-- 
Sincerely,
           Stephen R. van den Berg.

"The future is here, it's just not widely distributed yet." -- William Gibson

On Sun, Sep 07, 2008 at 12:34:15PM +0200, Stephen R. van den Berg wrote:

The questions now are:
- Would there be good reason not to record the backport/forwardport
  relationship in the additional parents of a commit?

Parents mean something different than just a link. If A is a parent of
B, then that implies that at point B, we considered all of the history
leading up to B (including A), and arrived at a certain tree state.

But cherry-picking means we looked at just A and used it to find a
certain tree-state. It says nothing about anything that came _before_ A.

So imagine this history:

A--B--C <-- master
 \
  D--E--F <-- side branch

Now let's say we want to cherry-pick E. If we mark the cherry-picked
commit as a parent, we get:

A--B--C--E' <-- master
 \      /
  D----E--F <-- side branch

Now let's say we want to merge the branches. What's our merge base?
Without your proposal, it is A, but now it is actually E. So doing a
three-way merge between E' and F with base E, it will look like our
master branch _removed_ the change from D which is still present in F.
And in a 3-way merge if one side removes something but the other side
leaves it untouched, then the result removes it.

So the merge result is bogus, as it is missing D.

I'm including a quick script below which creates this situation (it may
need tweaking to run on your system, but hopefully you get the point).

-Peff

-- >8 --
#!/bin/sh -ex

rm -rf repo

change() {
  perl -pi -e '/^'$1'$/ and $_ .= "changed $_"' words &&
  git commit -a -m $1 &&
  git tag $1
}

mkdir repo && cd repo && git init
cp /usr/share/dict/words . && git add words && git commit -m initial
change A
change B
change C
git checkout -b other A
change D
change E
change F
git checkout master
git cherry-pick -n E
tree=`git write-tree`
commit=`echo cherry pick | git commit-tree $tree -p HEAD^ -p E`
git update-ref HEAD $commit

Jeff King wrote:

On Sun, Sep 07, 2008 at 12:34:15PM +0200, Stephen R. van den Berg wrote:

quoted

The questions now are:
- Would there be good reason not to record the backport/forwardport
  relationship in the additional parents of a commit?

Parents mean something different than just a link. If A is a parent of
B, then that implies that at point B, we considered all of the history
leading up to B (including A), and arrived at a certain tree state.

That implication is not a technical one, but merely a convention in the
mind of the git-user.  Relevant, of course, but maybe we can accomodate
both uses.

But cherry-picking means we looked at just A and used it to find a
certain tree-state. It says nothing about anything that came _before_ A.

Correct.

Now let's say we want to cherry-pick E. If we mark the cherry-picked
commit as a parent, we get:

A--B--C--E' <-- master
\      /
 D----E--F <-- side branch

Now let's say we want to merge the branches. What's our merge base?
Without your proposal, it is A, but now it is actually E. So doing a
three-way merge between E' and F with base E, it will look like our
master branch _removed_ the change from D which is still present in F.
And in a 3-way merge if one side removes something but the other side
leaves it untouched, then the result removes it.

So the merge result is bogus, as it is missing D.

True.  However...

What if the merge-base determination code is modified to behave as
if --first-parent is specified while searching for the merge-base?
In that case it *will* find A as the merge-base, even in the presence of
"sideportlinks".

Does that resolve all technical issues?
-- 
Sincerely,
           Stephen R. van den Berg.

"The future is here, it's just not widely distributed yet." -- William Gibson

On Sun, Sep 07, 2008 at 09:56:26PM +0200, Stephen R. van den Berg wrote:

quoted

Parents mean something different than just a link. If A is a parent of
B, then that implies that at point B, we considered all of the history
leading up to B (including A), and arrived at a certain tree state.

That implication is not a technical one, but merely a convention in the
mind of the git-user.  Relevant, of course, but maybe we can accomodate
both uses.

I'm not sure I agree. I believe that property is part of the definition
of the commit DAG as originally conceived (but somebody like Linus could
say more). Obviously there is no formal definition, but I already
pointed out one thing that will break in that instance. I don't know if
there are others.

What if the merge-base determination code is modified to behave as
if --first-parent is specified while searching for the merge-base?
In that case it *will* find A as the merge-base, even in the presence of
"sideportlinks".

But then it will fail to find legitimate merge bases. So yes, you _can_
come up with a merge algorithm that handles this situation. But is it
then up to the user to say "Oh, this parent link means something else.
Use this other algorithm"? In that case, it really seems we are abusing
the "parent" link and it would be more appropriate to have some _other_
type of link.

Though I think if you look through the archives, people have argued
against having any git-level link to cherry-picked commits. The history
leading up to that cherry-pick is not necessarily of interest (though I
think you are proposing that it be optional to create such a link via
-x).

Does that resolve all technical issues?

I really don't know. I think you are proposing changing a core
assumption of the data structure, so I wouldn't be too surprised if
there is other code that relies on it.

You can use the script I posted in my last email as a basis for a
cherry-pick that does what you want (cherry-pick -n, write-tree,
commit-tree, update-ref). You might try a few experiments with that.

-Peff

Jeff King wrote:

On Sun, Sep 07, 2008 at 09:56:26PM +0200, Stephen R. van den Berg wrote:

quoted

That implication is not a technical one, but merely a convention in the
mind of the git-user.  Relevant, of course, but maybe we can accomodate
both uses.

I'm not sure I agree. I believe that property is part of the definition
of the commit DAG as originally conceived (but somebody like Linus could
say more). Obviously there is no formal definition, but I already
pointed out one thing that will break in that instance. I don't know if
there are others.

Yes, of course.  But even then, it's merely a formal definition, the
thing I'm after now is if there is any code that actually relies on that
formal definition.  That would be the code to review and perhaps adapt
in order to make it support the sideport-parents without hurting the old
definition.

quoted

What if the merge-base determination code is modified to behave as
if --first-parent is specified while searching for the merge-base?
In that case it *will* find A as the merge-base, even in the presence of
"sideportlinks".

But then it will fail to find legitimate merge bases. So yes, you _can_

Will it?  Can you give me one example where it would find the wrong one?

come up with a merge algorithm that handles this situation. But is it
then up to the user to say "Oh, this parent link means something else.
Use this other algorithm"?

That, of course, is unacceptable.  It either is seemless and supports
both uses transparently, or it has to be done (if at all) using a separate
link (not one of the normal parents) indeed.

In that case, it really seems we are abusing
the "parent" link and it would be more appropriate to have some _other_
type of link.

Quite.

Though I think if you look through the archives, people have argued
against having any git-level link to cherry-picked commits. The history
leading up to that cherry-pick is not necessarily of interest (though I
think you are proposing that it be optional to create such a link via
-x).

Optional, indeed, and sometimes quite useful.

quoted

Does that resolve all technical issues?

I really don't know. I think you are proposing changing a core
assumption of the data structure, so I wouldn't be too surprised if
there is other code that relies on it.

You can use the script I posted in my last email as a basis for a
cherry-pick that does what you want (cherry-pick -n, write-tree,
commit-tree, update-ref). You might try a few experiments with that.

I will, thanks.
-- 
Sincerely,
           Stephen R. van den Berg.

"The future is here, it's just not widely distributed yet." -- William Gibson

On Sun, Sep 07, 2008 at 10:22:02PM +0200, Stephen R. van den Berg wrote:

quoted

But then it will fail to find legitimate merge bases. So yes, you _can_

Will it?  Can you give me one example where it would find the wrong one?

How about the example I gave already? The first merge-base is E, but
that is not correct for the merge I gave. So you propose an algorithm
which will find A. But now imagine the exact some topology, but there
was no cherry-pick; instead, E' is actually a merge. Wouldn't E be the
right merge-base then?

And yes, of course the _content_ of the trees in E' will be different in
those two cases. But the shape of the history graph will be the same,
and that is the only thing that goes into finding a merge base.

-Peff

Jeff King wrote:

On Sun, Sep 07, 2008 at 10:22:02PM +0200, Stephen R. van den Berg wrote:

quoted

quoted

But then it will fail to find legitimate merge bases. So yes, you _can_

quoted

Will it?  Can you give me one example where it would find the wrong one?

How about the example I gave already? The first merge-base is E, but
that is not correct for the merge I gave. So you propose an algorithm
which will find A. But now imagine the exact some topology, but there
was no cherry-pick; instead, E' is actually a merge. Wouldn't E be the
right merge-base then?

Indeed.  Q.E.D.
I'll drop the idea with the parentlinks.
-- 
Sincerely,
           Stephen R. van den Berg.
The Horkheimer Effect: "The odds of it being cloudy are directly proportional
to the importance of an astronomical event."