Re: Patch (apply) vs. Pull

[Linus Torvalds <torvalds@osdl.org>]

On Thu, 23 Jun 2005, Daniel Barkalow wrote:
>
> 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