git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 2/5] add object-cache infrastructure

From
Jeff King <peff@peff.net>
Date
Jul 12, 2011, 21:36 UTC
Message-ID
<20110712213607.GA12447@sigill.intra.peff.net>
In-Reply-To
<20110712210716.GB17322@toss.lan>
On Tue, Jul 12, 2011 at 11:07:16PM +0200, Clemens Buchacher wrote:
Show 10 quoted lines
> On Tue, Jul 12, 2011 at 03:45:40PM -0400, Jeff King wrote:
> >
> > It has been a long time since I've looked at darcs, but from my
> > recollection, it will only work with specific patch types. That is, it
> > works if B and C are commutative. For text patches that touch the same
> > area, that is not the case. But if "B" were a token-renaming patch, for
> > example, I think it might work.
> 
> If they were commutative, we would not have a problem in git
> either.

Except that git doesn't support many commutative special forms, like token-renaming patches.

Show 10 quoted lines
> > Anyway, that is not really relevant to git. I think we decided long ago
> > that being simple and stupid about the content changes (i.e., blob A
> > became blob B) is better in general, even when there are a few corner
> > cases that might have been better off the other way.
> 
> Yes, but that only applies to git merge. When we talk about
> rebasing we are looking at individual patches rather than a single
> global merge. For rebase I think "patch algebra" is very relevant,
> and we have already implemented a simple patch algebra with
> patch-id's.

I can buy that argument, but I think most of the benefit in darcs comes from annotating your patch as "this is just renaming 'foo' to 'bar'" and other special patch types. Because the algebraic properties of those types is more interesting. And what we really don't want in git is having to put the burden on users of making those annotations (not just because it's annoying to do, but because when the annotation doesn't match what's in the blobs, the results would be extremely confusing).

But if you are proposing that we could do run-time detection on those sorts of patch properties and use the result in making a better rebase, I don't think that's a bad idea (though I do wonder if the amount of code will be worth it).

Again, it has been a long time since I've looked at darcs, and I was never a serious user of it, so everything I say above may be utterly wrong.

Show 9 quoted lines
> > I'd be curious to see an example worked out. In my experience, even if
> > something like patch-ids don't match, it's not a big deal for the hunks
> > that do match, because when we get to the actual content merge, we will
> > realize that both sides made the same change to that hunk.  So it's not
> > like you are getting unrelated conflicts; whatever small part of the
> > diff made the patch-id different will be the part where you get the
> > conflict, and the should merge cleanly.
> 
> I am reading that last part as "they should not merge cleanly".

Sorry, it was supposed to be "...and the rest should merge cleanly". But I think you got my meaning.

Show 12 quoted lines
> Exactly. The case I am talking about is where the patch-id's are
> different but there are no conflicts. I have worked out an example
> for git and darcs. Below are two scripts to demonstrate. In the
> example, the patch-id is different because upstream changes the
> patch in a way that does not conflict with the original patch. It
> simply adds another change that goes into a different hunk. Git
> fails to merge cleanly because the patch-id's are different. It
> presents the user with an awkward conflict that looks like a
> revert. Darcs, on the other hand, merges cleanly. It recognizes the
> fact that all changes from the original patch are contained
> upstream and do not conflict with the upstream version. The fact
> that more changes are added on top does not bother darcs.
Ah, OK, I see. Let me try to amend what I said earlier to make sure.

In the normal case of applying patch B on top of patch A, it doesn't matter if we use per-hunk patch-ids or normal patch-ids. Because even if we decide to actually go through with the merge of B on top of A, any hunks that _would have_ had their per-hunk patch-ids match will merge cleanly.

But in the real world, it is about applying patch Z on top of patches A..Y, where Z has similar hunks to patch N. And then it _does_ make a difference, because it is about skipping hunks from Z that are already in N, but will end up applied on top of Y. And what's in Y and what's in N may be quite different.

Does that sound right?
Show 14 quoted lines
> Now, one might argue that this is a corner case. But it's actually
> very common. In the example, the patch-id changes because of an
> extra change in a different text area. That is indeed unlikely.
> However, the same problem will occur in a much more common case.
> Let's say we have a patch with 10 hunks. The patch is applied
> upstream, with only one difference in one of the hunks.
> Subsequently, text areas affected by any of the other hunks change
> upstream. When the original patch is rebased on top of that, it
> will conflict with the one hunk that was changed in the upstream
> version of that patch. And that's ok. Git should not decide which
> version is correct. But in addition to that conflict there will
> also be conflicts for all the other hunks, which the upstream patch
> did _not_ modify. And all of those conflicts will look like
> reverts.
Right, that makes sense to me now.
-Peff
Previous: Clemens BuchacherNext: Clemens Buchacher
Message 18 of 35 in “generation numbers for faster traversals”
  1. 0/5 generation numbers for faster traversalsJeff King, Jul 11, 2011
  2. 1/5 decorate: allow storing values instead of pointersJeff King, Jul 11, 2011
  3. Jeff KingJul 11, 2011
  4. Junio C HamanoJul 11, 2011
  5. Jeff KingJul 11, 2011
  6. 2/5 add object-cache infrastructureJeff King, Jul 11, 2011
  7. Jeff KingJul 11, 2011
  8. Shawn PearceJul 11, 2011
  9. Junio C HamanoJul 11, 2011
  10. Jeff KingJul 11, 2011
  11. Junio C HamanoJul 11, 2011
  12. Junio C HamanoJul 11, 2011
  13. Jeff KingJul 12, 2011
  14. Clemens BuchacherJul 12, 2011
  15. Jeff KingJul 12, 2011
  16. Clemens BuchacherJul 12, 2011
  17. Clemens BuchacherJul 12, 2011
  18. Jeff KingJul 12, 2011
  19. Clemens BuchacherJul 14, 2011
  20. Illia BobyrJul 14, 2011
  21. John SzakmeisterJul 13, 2011
  22. Illia BobyrJul 12, 2011
  23. Jeff KingJul 12, 2011
  24. Illia BobyrJul 12, 2011
  25. Miles BaderJul 12, 2011
  26. Jakub NarebskiJul 12, 2011
  27. Jeff KingJul 12, 2011
  28. Junio C HamanoJul 12, 2011
  29. Jeff KingJul 13, 2011
  30. Junio C HamanoJul 13, 2011
  31. 3/5 commit: add commit_generation functionJeff King, Jul 11, 2011
  32. Clemens BuchacherJul 11, 2011
  33. Jeff KingJul 11, 2011
  34. 4/5 pretty: support %G to show the generation number of a commitJeff King, Jul 11, 2011
  35. 5/5 limit "contains" traversals based on commit generationJeff King, Jul 11, 2011

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.