4 ms·

I must be misunderstanding... If you are in the situation B -- X1 -- X2 -- X3 -- Head \ Y1 -- Y2 -- Cherry then Y2 can't be a merge-base for t

I must be misunderstanding... If you are in the situation B -- X1 -- X2 -- X3 -- Head \ Y1 -- Y2 -- Cherry then Y2 can't be a merge-base for the difference between Head and Cherry, the merge-base is B, that's a graph property and not an input. (You can even calculate it with `git merge-base`.) Right? And saying that "Y2 and Cherry are the patch" doesn't help my brain much. Now just thinking out loud I think there's something there... I know from Darcs that basically there is a mathematically precise thing to do here with two merges, so basically since "merge" is just "inverse, apply_patch, commute, drop_commit" and "cherry_pick" is just "commute, drop_commit, merge", you have a first merge being of the tree, B -- Y1 -- Y2 -- inv(Y2) -- inv(Y1) -- M \ / Cherry ----------------/ and then we squash and discard Y1 and Y2's metadata, B -- Cherry' patch := diff(M, B) Cherry' := commit(patch, [B], Cherry.metadata) and then we have something suitable to merge directly. It doesn't sound like Git does that though?

deleted 3y ago
[deleted]
oasisaimlessly 3y ago
The output of 'git merge-base' is the base (of the 3-way diff) used when doing a normal merge. That's all. Other (non-merge) operations like cherry-pick and revert use a different base commit. If you squint, you can view these operations as a merge with an abnormally-chosen base commit, which is the whole point here. The issue is just one of nomenclature; just because the '3way_merge(v1, base, v2)` algorithm is being used doesn't mean that a merge (with 'base = merge_base(v1, v2)') is being performed.
dan-robertson 3y ago
Yeah, normally for 3-way merges you want the kind of graph relationship you suggest (that the base is the most recent common ancestor for the two versions you want to merge) I think two questions you should ask are: 1) what does it mean to ‘apply a patch’ where the patch is the diff from X to Y but you are applying to a different revision from X. 2) what even is a patch in git? Darcs thinks in terms of patches but git, despite showing you lots of diffs is really only thinking in terms of snapshots. The answer to question 2 is that patches in git are diffs between revisions and, in particular between the parent of a commit and the revision of the commit itself. The answer to (1) is that ‘apply a patch’ in git is actually just a 3-way merge. If you write patches as arrows between revisions then the 3-way merge of two patches P, Q from a shared base is applying one patch to the tip of the other: P B ~~~~~~~~> X \ \ \ Q \ Q’ \ \ ~~~> Y ~~~> M Here M is the 3-way merge of X and Y at base B and Q’, and the diff from X to M is the patch Q applied at X. For a normal merge, you make X and Y parents of M. Git merely generalises this to cases where B is not the parent of X: you imagine a patch going from the base of the one implied by the commit you want to cherry-pick (I.e. the parent of the commit) all the way to the place where you want to base it on. This time, you are only doing the 3-way merge to compute the tip of your patch, you already know the base (it’s the place where you are applying the patch) and instead of producing a merge commit, you produce a commit with all the data from the old one before the cherry-pick except that you set the base to the place you cherry-pick onto. In darcs theory of patches terminology, you commute the cherry-pick patch backwards (ie going from (?->B)(B->Y1)(Y1->Y2)(Y2->Cherry) to (?->B)(B->Cherry’)(Cherry’->Y1’)(Y1’->Y2’)), somehow inject it before the B->X1 patch, and then commute it forwards to sit after X3->Head. One question to ask is whether this magic 3-way merge to apply patches works in these cases. And the answer is yes, it works about as well as regular 3-way merges, so you can get merge conflicts as well as some varieties of incorrect results (cf the Darcs docs about this)
andrewla 3y ago
My understanding of the article is that for the purposes of the cherry-pick, it "pretends" that the parent of Y2 is the base of the merge. Contrary to what the post says, git only cares about contents, not patches or diffs. The effect of this operation is that it compares what it would take to go from Y1 -> X3 with what it would take to go from Y1 -> Y2 -- it doesn't care about the path. If Y1 added a new function, for example, then when computing the three-way diff it would say "well, clearly in the X3 side of the merge that function was removed". This is astonishingly clever. If conflict-free, it will have all the content from X3 and all the changes from Y1->Y2, but none of the changes from B->Y1. Once again git has blown my mind.
- crdrost 3y ago
  Ah OK, I think I am getting it now. So 3-way-merge just takes three inputs, "base, left, right", it says diff(base, left), diff(base, right), merge those two diffs together into one bigger diff. If you were to actually ask, "how do I get from Y2 to Head?" the answer commit-wise would require some conceptual rollbacks, the resulting conceptual commit-tree looking like B -- Y1 -- Y2 -- inv(Y2) -- inv(Y1) -- X1 -- X2 -- X3 -- Head \ Cherry but, because 3-way-merge is a crude heuristic, it doesn't actually commute Cherry through inv(Y2), inv(Y1), X1, X2, X3, and Head the way that, say, a `git rebase` would. It just doesn't have to. And in terms of what I was writing above, what I was missing was that the two merges can be coalesced into one merge. The most mind-blowing thing about this is that if you did a real rebase it'd actually protect against the problems with associativity that 3-way-merge has, by forcing you to commute through each individual intermediate patch. Like, you don't need Darcs or Pijul if you'll just write some wrapper scripts around Git.
  - pmeunier 3y ago
    > the problems with associativity that 3-way-merge has, by forcing you to commute through each individual intermediate patch. Like, you don't need Darcs or Pijul if you'll just write some wrapper scripts around Git. Careful here, associativity is a completely different property from commutativity. Also, Pijul doesn't "commute through each individual intermediate patch" at all, its algorithmic complexity is actually lower than Git's.
Quekid5 3y ago
Git cherry-picking (rebasing, etc) is about applying patches to things. Those patches are based on snapshots and thus you can say "Apply the Y2..Cherry" diff to Head without a second thought. There's no "history" to where Y2 or Cherry came from. If the patch applies, it applies. Any problems due to that are to be resolved later. It might be instructive to read up on rebase --onto and what that can do. Cherry pick is just a special case of that... mostly.

deleted 3y ago

[deleted]

oasisaimlessly 3y ago

The output of 'git merge-base' is the base (of the 3-way diff) used when doing a normal merge. That's all. Other (non-merge) operations like cherry-pick and revert use a different base commit. If you squint, you can view these operations as a merge with an abnormally-chosen base commit, which is the whole point here. The issue is just one of nomenclature; just because the '3way_merge(v1, base, v2)` algorithm is being used doesn't mean that a merge (with 'base = merge_base(v1, v2)') is being performed.

dan-robertson 3y ago

Yeah, normally for 3-way merges you want the kind of graph relationship you suggest (that the base is the most recent common ancestor for the two versions you want to merge) I think two questions you should ask are: 1) what does it mean to ‘apply a patch’ where the patch is the diff from X to Y but you are applying to a different revision from X. 2) what even is a patch in git? Darcs thinks in terms of patches but git, despite showing you lots of diffs is really only thinking in terms of snapshots. The answer to question 2 is that patches in git are diffs between revisions and, in particular between the parent of a commit and the revision of the commit itself. The answer to (1) is that ‘apply a patch’ in git is actually just a 3-way merge. If you write patches as arrows between revisions then the 3-way merge of two patches P, Q from a shared base is applying one patch to the tip of the other: P B ~~~~~~~~> X \ \ \ Q \ Q’ \ \ ~~~> Y ~~~> M Here M is the 3-way merge of X and Y at base B and Q’, and the diff from X to M is the patch Q applied at X. For a normal merge, you make X and Y parents of M. Git merely generalises this to cases where B is not the parent of X: you imagine a patch going from the base of the one implied by the commit you want to cherry-pick (I.e. the parent of the commit) all the way to the place where you want to base it on. This time, you are only doing the 3-way merge to compute the tip of your patch, you already know the base (it’s the place where you are applying the patch) and instead of producing a merge commit, you produce a commit with all the data from the old one before the cherry-pick except that you set the base to the place you cherry-pick onto. In darcs theory of patches terminology, you commute the cherry-pick patch backwards (ie going from (?->B)(B->Y1)(Y1->Y2)(Y2->Cherry) to (?->B)(B->Cherry’)(Cherry’->Y1’)(Y1’->Y2’)), somehow inject it before the B->X1 patch, and then commute it forwards to sit after X3->Head. One question to ask is whether this magic 3-way merge to apply patches works in these cases. And the answer is yes, it works about as well as regular 3-way merges, so you can get merge conflicts as well as some varieties of incorrect results (cf the Darcs docs about this)

andrewla 3y ago

My understanding of the article is that for the purposes of the cherry-pick, it "pretends" that the parent of Y2 is the base of the merge. Contrary to what the post says, git only cares about contents, not patches or diffs. The effect of this operation is that it compares what it would take to go from Y1 -> X3 with what it would take to go from Y1 -> Y2 -- it doesn't care about the path. If Y1 added a new function, for example, then when computing the three-way diff it would say "well, clearly in the X3 side of the merge that function was removed". This is astonishingly clever. If conflict-free, it will have all the content from X3 and all the changes from Y1->Y2, but none of the changes from B->Y1. Once again git has blown my mind.

crdrost 3y ago
Ah OK, I think I am getting it now. So 3-way-merge just takes three inputs, "base, left, right", it says diff(base, left), diff(base, right), merge those two diffs together into one bigger diff. If you were to actually ask, "how do I get from Y2 to Head?" the answer commit-wise would require some conceptual rollbacks, the resulting conceptual commit-tree looking like B -- Y1 -- Y2 -- inv(Y2) -- inv(Y1) -- X1 -- X2 -- X3 -- Head \ Cherry but, because 3-way-merge is a crude heuristic, it doesn't actually commute Cherry through inv(Y2), inv(Y1), X1, X2, X3, and Head the way that, say, a `git rebase` would. It just doesn't have to. And in terms of what I was writing above, what I was missing was that the two merges can be coalesced into one merge. The most mind-blowing thing about this is that if you did a real rebase it'd actually protect against the problems with associativity that 3-way-merge has, by forcing you to commute through each individual intermediate patch. Like, you don't need Darcs or Pijul if you'll just write some wrapper scripts around Git.
- pmeunier 3y ago
  > the problems with associativity that 3-way-merge has, by forcing you to commute through each individual intermediate patch. Like, you don't need Darcs or Pijul if you'll just write some wrapper scripts around Git. Careful here, associativity is a completely different property from commutativity. Also, Pijul doesn't "commute through each individual intermediate patch" at all, its algorithmic complexity is actually lower than Git's.

Quekid5 3y ago

Git cherry-picking (rebasing, etc) is about applying patches to things. Those patches are based on snapshots and thus you can say "Apply the Y2..Cherry" diff to Head without a second thought. There's no "history" to where Y2 or Cherry came from. If the patch applies, it applies. Any problems due to that are to be resolved later. It might be instructive to read up on rebase --onto and what that can do. Cherry pick is just a special case of that... mostly.