Re: Patch (apply) vs. Pull

From: Linus Torvalds <torvalds@osdl.org>
Date: Jun 23, 2005, 22:20 UTC
Message-ID: <Pine.LNX.4.58.0506231510370.11175@ppc970.osdl.org>
In-Reply-To: <Pine.LNX.4.21.0506231522080.30848-100000@iabervon.org>

On Thu, 23 Jun 2005, Daniel Barkalow wrote:

Show 10 quoted lines

>
> On Thu, 23 Jun 2005, Linus Torvalds wrote:
> > 
> > Right, that would mean that we don't control the hash generation at both 
> > points, and would make it fundamentally harder. But since the whole point 
> > is that we should be able to generate the ID _without_ it actually being 
> > stored away anywhere, this hash approach should work fine.
> 
> ("We" in this case being the developer checking whether the patch went in,
> not the maintainer)

Yes.

> We'll need to see if the performance is okay this way, both in terms of
> time spent searching for the patch you're checking on and in terms of
> recognizing the patch as being the same. No point in designing anything
> more complex until we determine if we can't just recognize it already.

Actually, this is a _very_ efficient check to do, because I'm just incredibly smart.

What you do is to download the current git tree (give it a while to mirror out, actually), and you get a magic "git-patch-id" program.

Now, the reason this is very efficient is magical. Let's say that you have my tree as branch "linus", and you have your own tree (branch "daniel"), and you want to see what commits are in both (but are not the _same_ commit - you just wonder if they have the same diff). That's a big clue that you should drop your copy, because I applied it as a diff.

What you do is simply:

	git-whatchanged -p linus..daniel | git-patch-id | sort > daniel-patch-id
	git-whatchanged -p daniel..linus | git-patch-id | sort > linus-patch-id
	join -j 1 linus-patch-id daniel-patch-id

and you're done. You've just created a list of commits that have the same patch ID (and it will list the patch ID _and_ the two commit ID's, just to be really nice about it).

It's all totally linear in number of patches involved (yeah, the "sort" is obviously reall NlogN, and technically the git-rev-list between the two trees _could_ be more than linear, but in practice they are very cheap and very close to linear anyway).

It's also obviously totally untested, but hey, I always write perfect code, so what could _possibly_ go wrong..

		Linus