The merge from hell...

The merge from hell...

[Linus Torvalds]

Ok,
 I've been holding off on having octopus merges in the kernel tree, but I 
just merged an ACPI update that had used one of them, and I didn't really 
see any real reason not to take it.

That octopus commit has got _twelve_ parents.

It's commit 9fdb62af92c741addbea15545f214a6e89460865, and passing it to 
git-diff-tree with the "--cc" option seems to do the largely the right 
thing (although arguably, since one of the parents always matches the end 
result in all the files, it shouldn't have shown anything at all, so I 
think it could do with some tweaking).

git-diff-tree takes almost three seconds to get its result, though.

However, if git-diff-tree is a bit slow, then gitk gets _really_ upset 
when you click on it. Apparently the colorized multi-way diff just breaks 
down into some O(2**n) hell.

I'm sure it's making progress, it's just very slow, and gitk is 
essentially unusable on that commit (gitk also gets visually confused by 
the fact that it forces a wider set of history than gitk expects, since it 
can't prune it down with the arrow notation).

[ Ahh. gitk just came back. After a _loong_ time thinking, and having run
  out of different colors, but looking otherwise fairly nice ;]

So think of it as a correctness/scalability test.

I haven't tried qgit or gitview on it, but am cc'ing Marco and Aneesh in 
case they want to hone their octopus skills on it.

Btw, I think you're better off parsing the "git-diff-tree --cc" output 
than doing it yourself like gitk does, now that core git has support for 
things like that.

			Linus

Re: The merge from hell...

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

>  I've been holding off on having octopus merges in the kernel tree, but I 
> just merged an ACPI update that had used one of them, and I didn't really 
> see any real reason not to take it.
>
> That octopus commit has got _twelve_ parents.

Len must have been smoking something really good.  Even I would
not attempt to do such an octopus and expect to keep my sanity,
but why not? ;-)

> It's commit 9fdb62af92c741addbea15545f214a6e89460865, and passing it to 
> git-diff-tree with the "--cc" option seems to do the largely the right 
> thing (although arguably, since one of the parents always matches the end 
> result in all the files, it shouldn't have shown anything at all, so I 
> think it could do with some tweaking).

Hmph.  Do you mean a hunk like this?

diff --cc kernel/sys.c
@@@@@@@@@@@@@ +33,7 @@@@@@@@@@@@@

            #include <linux/compat.h>
            #include <linux/syscalls.h>
   + +++    #include <linux/kprobes.h>

            #include <asm/uaccess.h>
            #include <asm/io.h>

Currently I cull hunks that have changes from only one parent,
or when the changes are the same from all but one parent.  This
hunk does not match either criteria.

Instead I could cull all hunks that have either "all whitespace"
or "plus and minus in the same set of columns" hunks.  If I did
so, this would become uninteresting:

diff --cc arch/ia64/pci/pci.c
@@@@@@@@@@@@@ +709,7 @@@@@@@@@@@@@
             */
            int ia64_pci_legacy_write(struct pci_dev *bus, u16...
            {
  ------ -  	int ret = 0;
  ++++++ +  	int ret = size;
            
            	switch (size) {
            	case 1:

But this is still interesting:

@@@@@@@@@@@@@ +308,35 @@@@@@@@@@@@@
            			goto end;
            		}
            	}
  --        	cx->usage++;
  --        
            
     +++    #ifdef CONFIG_HOTPLUG_CPU
     +++    	/*


> git-diff-tree takes almost three seconds to get its result, though.

One trivial thing I should be able to do to speed things up is
to reuse previous diff with other parents.  For example, that
commit does this to kernel/sys.c from its 12 parents.

:100644 100644 d09cac2... 0929c69... M  kernel/sys.c
:100644 100644 eecf845... 0929c69... M  kernel/sys.c
:100644 100644 c3b1874... 0929c69... M  kernel/sys.c
:100644 100644 bce933e... 0929c69... M  kernel/sys.c
:100644 100644 eecf845... 0929c69... M  kernel/sys.c
:100644 100644 bce933e... 0929c69... M  kernel/sys.c
:100644 100644 bce933e... 0929c69... M  kernel/sys.c
:100644 100644 bce933e... 0929c69... M  kernel/sys.c
:100644 100644 eecf845... 0929c69... M  kernel/sys.c
:100644 100644 eecf845... 0929c69... M  kernel/sys.c
:100644 100644 eecf845... 0929c69... M  kernel/sys.c
:100644 100644 eecf845... 0929c69... M  kernel/sys.c

Running "sort -u" on these would leave only 4 lines.

I did not expect anybody to be _that_ sick (eh, pardon my
language) to do a 12-way octpus, so I did not consider this
optimization possibility, but I should be doing only 4 diffs to
format -c for this commit.  Currently I do 12.

> So think of it as a correctness/scalability test.

Heh.  I like this one as a practice.  Thanks!

Re: The merge from hell...

[Marco Costalba]

On 2/2/06, Linus Torvalds <torvalds@osdl.org> wrote:
>

> Btw, I think you're better off parsing the "git-diff-tree --cc" output
> than doing it yourself like gitk does, now that core git has support for
> things like that.
>

Currently the public git repo version of qgit uses "git-diff-tree -c"
for merges, It's not a problem to change qgit to use --cc option
instead. But I would like to use just one kind of option to filter
merges files.

So I would like to hear some feedback on using --cc vs -c.

Marco

Re: The merge from hell...

[Linus Torvalds]

On Wed, 1 Feb 2006, Junio C Hamano wrote:
> 
> > It's commit 9fdb62af92c741addbea15545f214a6e89460865, and passing it to 
> > git-diff-tree with the "--cc" option seems to do the largely the right 
> > thing (although arguably, since one of the parents always matches the end 
> > result in all the files, it shouldn't have shown anything at all, so I 
> > think it could do with some tweaking).
> 
> Hmph.  Do you mean a hunk like this?
> 
> diff --cc kernel/sys.c
> @@@@@@@@@@@@@ +33,7 @@@@@@@@@@@@@
> 
>             #include <linux/compat.h>
>             #include <linux/syscalls.h>
>    + +++    #include <linux/kprobes.h>
> 
>             #include <asm/uaccess.h>
>             #include <asm/io.h>

Yes.

> Currently I cull hunks that have changes from only one parent,
> or when the changes are the same from all but one parent.  This
> hunk does not match either criteria.

Correct. I think "git-diff-tree --cc" actually works as you advertized, 
but that we should change the rules. More akin to

 - if there are only two versions of a hunk, and one of those versions 
   ended up in the result, the hunk is considered successfully merged
   and should be ignored under "--cc"

Under that rule, the kernel/sys.c hunk you specify is indeed 
uninteresting, because there are only two versions: the version that 
didn't have the addition, and the version that did.

> or "plus and minus in the same set of columns" hunks.  If I did
> so, this would become uninteresting:
> 
> diff --cc arch/ia64/pci/pci.c
> @@@@@@@@@@@@@ +709,7 @@@@@@@@@@@@@
>              */
>             int ia64_pci_legacy_write(struct pci_dev *bus, u16...
>             {
>   ------ -  	int ret = 0;
>   ++++++ +  	int ret = size;
>             
>             	switch (size) {
>             	case 1:

Yes. Again, only two versions. Either it was "ret = 0" or it was "ret = 
size". No other version existed in any branch or in the end result, so 
there really were only two versions, and one of them ended up being the 
end result.

> But this is still interesting:
> 
> @@@@@@@@@@@@@ +308,35 @@@@@@@@@@@@@
>             			goto end;
>             		}
>             	}
>   --        	cx->usage++;
>   --        
>             
>      +++    #ifdef CONFIG_HOTPLUG_CPU
>      +++    	/*

Not under my suggested "two version" rule.

The above has _three_ versions: the one with no changes, the one with 
"cx->usage++" removed and the one with "#ifdef CONFIG_HOTPLUG_CPU" added.

So under the two-version rule, the last one would still be interesting.

> > git-diff-tree takes almost three seconds to get its result, though.
> 
> One trivial thing I should be able to do to speed things up is
> to reuse previous diff with other parents.

Yes. In this example, it would apparently cut down the work by a third for 
that file, although it migt make it harder to calculate the proper "-/+" 
patterns..

> I did not expect anybody to be _that_ sick (eh, pardon my
> language) to do a 12-way octpus, so I did not consider this
> optimization possibility, but I should be doing only 4 diffs to
> format -c for this commit.  Currently I do 12.

I agree, I wouldn't have considered that 12-way merge sane either, but 
hey, it worked, and our octopus merge rules are simple enough that I guess 
there's not really any downside to it.

And I was actually happy to have "git-diff-tree --cc" to look at it, and 
that "gitk" eventually gave results that looked decent. I didn't go 
through it all that closely, but the ones I _looked_ at looked fine, and 
it was mighty pleasant to have the tools to look more closely.

So thanks for "--cc" yet again.

> > So think of it as a correctness/scalability test.
> 
> Heh.  I like this one as a practice.  Thanks!

Thank Len. He may have done it as a way to avoid having extra merges, 
since I complained about those last time ;)

		Linus

Re: The merge from hell...

[Linus Torvalds]

On Wed, 1 Feb 2006, Linus Torvalds wrote:
> 
> Not under my suggested "two version" rule.

That "Not" is just me being stupid. I'm agreeing with you, not 
disagreeing, I just misread your mail.

I _think_ your version of the rule ("pluses and minuses in all the same 
columns") ends up being exactly the same as my rule ("only two different 
versions").

		Linus

Re: The merge from hell...

[Linus Torvalds]

On Thu, 2 Feb 2006, Marco Costalba wrote:
> 
> Currently the public git repo version of qgit uses "git-diff-tree -c"
> for merges, It's not a problem to change qgit to use --cc option
> instead. But I would like to use just one kind of option to filter
> merges files.

I think using "-c" rather than "--cc" is fine, and if it makes parsing 
easier..

The "--cc" option should show less "noise", an dI'm actually arguing that 
it should show even less than it does now (for when the branches agreed 
with each other, and there was no actual conflict, which is what I think 
is more useful), but I don't think "-c" is _wrong_ either.

Using "-c" is a strange kind of "show all differences in a file that had 
file-level merges" while at least to me "--cc" is meant to be more of a 
"show all actual file-level CONFLICTS where the merge actually did 
something different"

		Linus

Re: The merge from hell...

[Aneesh Kumar]

On 2/2/06, Linus Torvalds <torvalds@osdl.org> wrote:
>
>
> On Thu, 2 Feb 2006, Marco Costalba wrote:
> >
> > Currently the public git repo version of qgit uses "git-diff-tree -c"
> > for merges, It's not a problem to change qgit to use --cc option
> > instead. But I would like to use just one kind of option to filter
> > merges files.
>
> I think using "-c" rather than "--cc" is fine, and if it makes parsing
> easier..
>
> The "--cc" option should show less "noise", an dI'm actually arguing that
> it should show even less than it does now (for when the branches agreed
> with each other, and there was no actual conflict, which is what I think
> is more useful), but I don't think "-c" is _wrong_ either.
>
> Using "-c" is a strange kind of "show all differences in a file that had
> file-level merges" while at least to me "--cc" is meant to be more of a
> "show all actual file-level CONFLICTS where the merge actually did
> something different"


Ok i tried using --cc. But then as per the man page if the
optimization makes the all the hunks disapper then commit log is not
show unless -m is used. Is there a way to get the commit log printed.
BTW using -m didn't show any difference even though man page said
about some difference

-aneesh

Re: The merge from hell...

[Linus Torvalds]

On Wed, 1 Feb 2006, Linus Torvalds wrote:
> 
> I _think_ your version of the rule ("pluses and minuses in all the same 
> columns") ends up being exactly the same as my rule ("only two different 
> versions").

Actually, I take that back.

My version of the rule was not just that there were only two versions: the 
merge _result_ had to match one of the versions in one of the branches 
too.

That's important. It's important because you _can_ actually have a merge 
where both branches have the exact same content, but some evil merger 
ended up editing just the merge result.

So there are literally just two versions, but one of the versions _only_ 
exists in the merge result. Such a thing must always be considered a 
conflict, since basically the merge result is obviously "interesting".

That requirement can still be rewritten as a slight variation of your 
version, I think: "the pluses and minuses are all in the same columns, and 
the final column has to match one other column"

Maybe I'm not thinking clearly. Somebody else should double-check my 
thinking. My brain is tired, and I'm going to bed.

			Linus

Re: The merge from hell...

[Junio C Hamano]

Aneesh Kumar <aneesh.kumar@gmail.com> writes:

> Ok i tried using --cc. But then as per the man page if the
> optimization makes the all the hunks disapper then commit log is not
> show unless -m is used. Is there a way to get the commit log printed.

Yes, there is a way.  I need to fix a bug ;-).

This patch was done on top of the other two patches I sent
earlier tonight, but should apply on top of master even if you
have not applied the other two.

--

diff --git a/combine-diff.c b/combine-diff.c
index 44931b2..45f1822 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -675,6 +675,8 @@ int diff_tree_combined_merge(const unsig
 					       show_empty_merge))
 				header = NULL;
 		}
+		if (header)
+			puts(header);
 	}
 
 	/* Clean things up */

Re: The merge from hell...

[Linus Torvalds]

On Thu, 2 Feb 2006, Aneesh Kumar wrote:
> 
> Ok i tried using --cc. But then as per the man page if the
> optimization makes the all the hunks disapper then commit log is not
> show unless -m is used.

Ahh. You're mis-using git-diff-tree.

git-diff-tree will _never_ show the commit log if the diff ends up being 
empty. That can actually happen even for a regular commit, because we had 
some early bugs that allowed them.

See commit 69d37960b578be0a69383bd71d06c1fcfb86e8b9, for example. Notice 
how

	git-diff-tree --pretty 69d37960

is entirely silent, even though 

	git log 69d37960

clearly shows that the commit exists. I screwed up a commit, and 
effectively applied an empty patch (this was before git-apply would 
notice, and consider it an error - something I fixed very soon 
afterwards ;^).

> Is there a way to get the commit log printed.

Yes. What you should do is to do

	git-rev-list --parents --pretty

which gives the revision _log_ in pretty format. 

The difference between "git-rev-list --pretty" and "git-diff-tree 
--pretty" is really exactly that "git-rev-list" lists every revision, 
while git-diff-tree only lists revisions that _differ_ in the trees.

This, btw, is also really the main difference between doing a "git log" 
and doing a "git whatchanged". A "git log" shows all revisions (and uses 
"git-rev-list --pretty"). While "git whatchanged" shows what _changed_ 
(and uses "git-diff-tree --pretty").

For a revision tool like gitview, you want to use "git-rev-list --pretty".

[ SIDE NOTE! Actually, there's another format that you may find easier to 
  parse automatically: "git-rev-list --header". It uses the raw format, 
  and adds a NUL character between each rev. That makes things like the 
  date etc trivial to parse, and it's also slightly easier to see the end 
  of a commit message vs just a normal end-of-line. 

  So "gitk", for example, really parses the output of

	git-rev-list --header --topo-order --parents

  to generate the revision list. The "--topo-order" part guarantees that 
  all children will always be shown before any parents. ]

Hope that clarifies the issue.

		Linus

Re: The merge from hell...

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> On Thu, 2 Feb 2006, Aneesh Kumar wrote:
>> 
>> Ok i tried using --cc. But then as per the man page if the
>> optimization makes the all the hunks disapper then commit log is not
>> show unless -m is used.
>
> Ahh. You're mis-using git-diff-tree.
>
> git-diff-tree will _never_ show the commit log if the diff ends up being 
> empty.

True, I should fix the documentation.

It _might_ make sense for certain users like gitk and gitview if
we had a single tool that gives --pretty and its diff even if
the diff is empty.  Having said that, the flag --cc -m is too
specific.  If some uses want to see the commit log even for an
empty diff, that flag should not be something only --cc honors.

RE: The merge from hell...

[Brown, Len]

 
>Thank Len. He may have done it as a way to avoid having extra merges, 
>since I complained about those last time ;)

Seems I'm batting 1000 for entertainment value
over my last two kernel patch pushes:-)

The previous one I took abuse for unwittingly cluttering
history with "extra" merges.  The thread went on
and on, but buried in there were some interesting
observations on work flow, and somebody
asserted that the "cleanest" way to cherry pick
the topic branches onto the release branch was
with a multi-branch merge.

As git merge seemed to advertise support for it w/o
me needing to learn a new command, I tried it out
and it seemed to work fine -- including a nice colorful
diagram in gitk:-)

I can do 16 next time, or 22, or none -- or you can have
git merge under the covers do this via iteration instead
of all at once -- that's up to you guys.  My topic branches
tend to be disjoint topics with little expected overlap;
so grabbing a bunch of them when they're fully "cooked"
in -mm and plunking them down in one merge is actually
an example of history matching reality.

cheers,
-Len

RE: The merge from hell...

[Linus Torvalds]

On Thu, 2 Feb 2006, Brown, Len wrote:
> 
> I can do 16 next time, or 22, or none

Actually, you can't do 22:

	/*
	 * Having more than two parents is not strange at all, and this is
	 * how multi-way merges are represented.
	 */
	#define MAXPARENT (16)

(commit-tree.c).

Now, admittedly you should literally need no more than to change that 
#define and recompile, but at least by default, git-write-tree won't 
accept more than 16 parents.

The 12-way merge was a bit over the top, but it worked. I'd suggest not 
beign quite _that_ aggressive in the future, though, but it's not a big 
deal.

One thing I'd ask for: would it be possible to have more descriptive 
branch names than just numbers? Even if you want to track it by bugzilla 
entry number, how about calling it "bugzilla-12345" instead? 

I can make the educated guess that it's the bugzilla.kernel.org tracking 
number, but still.. I think it would make the changelog more readable and 
understandable to outsiders.

		Linus

RE: The merge from hell...

[Brown, Len]

>The 12-way merge was a bit over the top, but it worked. I'd 
>suggest not being quite _that_ aggressive in the future,
>though, but it's not a big deal.

I favor "assertive" over "aggressive" --
I assert that the tools I use must work as advertised;-)

> #define MAXPARENT (16)

How about setting this #define to the number
that you're comfortable with?  Then folks like me --
who wouldn't dream of checking code into Linux with a hopped-up git --
will simply obey the limit that comes with the tool?

>One thing I'd ask for: would it be possible to have more descriptive 
>branch names than just numbers? Even if you want to track it 
>by bugzilla entry number, how about calling it "bugzilla-12345" instead? 

bugzilla-#### -- no problem -- will do.

thanks,
-Len

ps. 
In the back of my head I was worried about using plain
numbers when I saw somebody refer to "shorthand SHA1".
Hopefully this is an idle worry and it is not possible
for the tool to confuse a numeric branch name with a SHA1 id.

RE: The merge from hell...

[Linus Torvalds]

On Fri, 3 Feb 2006, Brown, Len wrote:
>
> In the back of my head I was worried about using plain
> numbers when I saw somebody refer to "shorthand SHA1".
> Hopefully this is an idle worry and it is not possible
> for the tool to confuse a numeric branch name with a SHA1 id.

It _is_ possible, but the rule is that references will be resolved first. 

If you mis-type a reference and it could be construed as a short hex SHA1 
ID (it needs to have more than 5 characters in it to trigger, though), the 
auto-completion of SHA1 ID's could bite you, though.

It's pretty unlikely, of course. But it's one reason to try to avoid using 
ref names that are numeric.

		Linus

Re: The merge from hell...

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> The 12-way merge was a bit over the top, but it worked. I'd suggest not 
> beign quite _that_ aggressive in the future, though, but it's not a big 
> deal.

Heh, I was quietly planning to raise the limit, or lift it
altogether ;-).

I find Len's explanation that those topics cooked independently
and happened to mature at about the same time an excellent
excuse to record this as an Octopus, and with that usage there
is no inherent reason, other than making the diff completely
unreadable, to limit the number of parents.  But I tend to agree
that the current 16 is a sane limit in practice.

That reminds me of another practical limit I've known but did
nothing about for quite some time (you may not even remember
doing that parser anymore).  This does not work for Len's merge:

	$ git rev-parse --verify funmerge^10

You could do a 16-way merge but 12-way is already hitting
usability limit, depending on what you would want to do with
them.  For example, you cannot easily decompose the topic
branches out of that merge, like this:

	$ git checkout -b redo-3549 funmerge^2     ;# works
        $ git checkout -b redo-pnpacpi funmerge^12 ;# doesn't

> One thing I'd ask for: would it be possible to have more descriptive 
> branch names than just numbers? Even if you want to track it by bugzilla 
> entry number, how about calling it "bugzilla-12345" instead? 

When kernel people (not just Len) talk about a "bugzilla ID",
does that ID always come from the same namespace, or do some
subsystems have their own bugzilla?

Re: The merge from hell...

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> On Fri, 3 Feb 2006, Brown, Len wrote:
>>
>> In the back of my head I was worried about using plain
>> numbers when I saw somebody refer to "shorthand SHA1".
>> Hopefully this is an idle worry and it is not possible
>> for the tool to confuse a numeric branch name with a SHA1 id.
>
> It _is_ possible, but the rule is that references will be resolved first. 

I have to admit that I had this broken for a while.  The
breakage was when you have the same numeric branch name _and_
tagname, then ref resolution was skipped and short SHA1 was
taken.  It _might_ have bitten somebody in real life until I
fixed it.  But I believe this is fixed now.

> It's pretty unlikely, of course. But it's one reason to try to avoid using 
> ref names that are numeric.

Or even non numeric ones, like "deadbeef".

Re: The merge from hell...

[linux]

While we're stress-testing the ystem, does anyone feel like fixing
git-rev-parse 9fdb62af92c741addbea15545f214a6e89460865^10 ?

The following is my attempt, but it doesn't seem sufficient...

$ ~/git/git-rev-parse 9fdb62af92c741addbea15545f214a6e89460865^{1,2,3,4,5,6,7,8,9,10,11,12}
3ee68c4af3fd7228c1be63254b9f884614f9ebb2
876c184b31dc73cc3f38c5b86dee55d091a56769
729b4d4ce1982c52040bbf22d6711cdf8db07ad8
cf82478840188f8c8494c1d7a668a8ae170d0e07
dacd9b80355525be0e3c519687868410e304ad1c
63c94b68ec30847a6e2b36651703f41066f91480
35f652b5ef4ef145ac5514f6302b3f4cebfbbad4
1a38416cea8ac801ae8f261074721f35317613dc
4a90c7e86202f46fa9af011bdbcdf36e355d1721
fatal: '9fdb62af92c741addbea15545f214a6e89460865^10': No such file or directory

(Placed in the public domain; go nuts.)

diff --git a/sha1_name.c b/sha1_name.c
index ba0747c..adf49d2 100644
--- a/sha1_name.c
+++ b/sha1_name.c
@@ -388,52 +388,33 @@ static int peel_onion(const char *name, 
 
 static int get_sha1_1(const char *name, int len, unsigned char *sha1)
 {
-	int parent, ret;
-	const char *cp;
-
-	/* foo^[0-9] or foo^ (== foo^1); we do not do more than 9 parents. */
-	if (len > 2 && name[len-2] == '^' &&
-	    name[len-1] >= '0' && name[len-1] <= '9') {
-		parent = name[len-1] - '0';
-		len -= 2;
-	}
-	else if (len > 1 && name[len-1] == '^') {
-		parent = 1;
-		len--;
-	} else
-		parent = -1;
-
-	if (parent >= 0)
-		return get_parent(name, len, sha1, parent);
-
-	/* "name~3" is "name^^^",
-	 * "name~12" is "name^^^^^^^^^^^^", and
-	 * "name~" and "name~0" are name -- not "name^0"!
-	 */
-	parent = 0;
-	for (cp = name + len - 1; name <= cp; cp--) {
-		int ch = *cp;
-		if ('0' <= ch && ch <= '9')
-			continue;
-		if (ch != '~')
-			parent = -1;
-		break;
+	int parent = 0, pow10 = 1;
+	const char *cp = name + len;
+	char ch = 0;	/* In case len == 0 */
+
+	/* Parse trailing number and check for ^5 or ~5 */
+	while (cp > name && (ch = *--cp) >= '0' && ch <= '9') {
+		parent += ch - '0' * pow10;
+		pow10 *= 10;
 	}
-	if (!parent && *cp == '~') {
-		int len1 = cp - name;
-		cp++;
-		while (cp < name + len)
-			parent = parent * 10 + *cp++ - '0';
-		return get_nth_ancestor(name, len1, sha1, parent);
+
+	/* Handle foo^[0-9]* case */
+	if (ch == '^') {
+		/* foo^ means foo^1, first parent */
+		if (cp + 1 == name)
+			parent = 1;
+		return get_parent(name, cp - name, sha1, parent);
 	}
+	/* Handle foo~[0-9]* case.  name~ = name~0 = name (not name^0!) */
+	if (ch == '~')
+		return get_nth_ancestor(name, cp - name, sha1, parent);
 
-	ret = peel_onion(name, len, sha1);
-	if (!ret)
+	if (!peel_onion(name, len, sha1))
 		return 0;
 
-	ret = get_sha1_basic(name, len, sha1);
-	if (!ret)
+	if (!get_sha1_basic(name, len, sha1))
 		return 0;
+
 	return get_short_sha1(name, len, sha1, 0);
 }
 

Re: The merge from hell...

[Dave Jones]

On Thu, Feb 02, 2006 at 10:28:43PM -0800, Junio C Hamano wrote:

 > > One thing I'd ask for: would it be possible to have more descriptive 
 > > branch names than just numbers? Even if you want to track it by bugzilla 
 > > entry number, how about calling it "bugzilla-12345" instead? 
 > 
 > When kernel people (not just Len) talk about a "bugzilla ID",
 > does that ID always come from the same namespace, or do some
 > subsystems have their own bugzilla?

Not only do some subsystems have their own bugtracker (ALSA for eg),
but referring to 'bugzilla' alone is meaningless, as it could
mean bugme.osdl.org, bugzilla.redhat.com, bugzilla.novell.com,
bugzilla.ubuntu.com etc etc, all of which are a prime source of
juicy kernel bugs.

		Dave

RE: The merge from hell...

[Brown, Len]

>On Thu, Feb 02, 2006 at 10:28:43PM -0800, Junio C Hamano wrote:
>
> > > One thing I'd ask for: would it be possible to have more 
>descriptive 
> > > branch names than just numbers? Even if you want to track 
>it by bugzilla 
> > > entry number, how about calling it "bugzilla-12345" instead? 
> > 
> > When kernel people (not just Len) talk about a "bugzilla ID",
> > does that ID always come from the same namespace, or do some
> > subsystems have their own bugzilla?
>
>Not only do some subsystems have their own bugtracker (ALSA for eg),
>but referring to 'bugzilla' alone is meaningless, as it could
>mean bugme.osdl.org, bugzilla.redhat.com, bugzilla.novell.com,
>bugzilla.ubuntu.com etc etc, all of which are a prime source of
>juicy kernel bugs.

Naming the branch is just eye-candy for the merge comment.
My topic branch labels in refs/my-branch never get to kernel.org, so you're
not going to see the pretty green tags on topic branches branches that I see.

I include the full-URL of the bug report in the original commit comments
for those who are interested.  I think this it the important place to put it,
and in practice I've found it to be extremely useful.

-Len

Re: The merge from hell...

[Junio C Hamano]

"Brown, Len" <len.brown@intel.com> writes:

> Naming the branch is just eye-candy for the merge comment.
> My topic branch labels in refs/my-branch never get to kernel.org, so you're
> not going to see the pretty green tags on topic branches branches that I see.
>
> I include the full-URL of the bug report in the original commit comments
> for those who are interested.  I think this it the important place to put it,
> and in practice I've found it to be extremely useful.

Both excellent points.

If I may digress,...

It appears most of the topic branches in that merge have only
one commit since they forked from trunk (the development track
led to the first parent of that merge), but some seem to have
more than one commits.

It might make sense if we have a tool support to pre-format the
merge messages like this, given set of branch names:

    [ACPI] Merge 3549, 4320, 4485, 4588, 4980, 5483, 5651, acpica, asus, fops and pnpacpi branches into release

    3549: [ACPI] Disable C2/C3 for _all_ IBM R40e Laptops
    4320: [ACPI] fix reboot upon suspend-to-disk
    4485: [ACPI] handle BIOS with implicit C1 in _CST
    4588: [ACPI] fix acpi_os_wait_sempahore() finite timeout case (AE_TIME warning)
    4980 (5 commits): [ACPI] build EC driver on IA64
    5483 (3 commits): [ACPI] fix acpi_cpufreq.c build warrning
    5651: [ACPI] SMP S3 resume: evaluate _WAK after INIT
    acpica (23 commits): [ACPI] ACPICA 20060113
    asus (3 commits): [ACPI_ASUS] fix asus module param description
    fops (2 commits): [ACPI] make two processor functions static
    pnpacpi (3 commits): [PNPACPI] clean excluded_id_list[]

Here I am counting the number of commits on each topic since it
last diverged from trunk (`merge-base release branch`), and
showing the latest commit of the topic.

We could even go further and have "per branch annotation" that
lets you do something like this:

	$ git checkout -b 3549 \
          --description 'http://bugzilla.kernel.org/show_bug.cgi?id=3549'
	$ work work
        $ git commit
	... work on other topics in similar way ...
        ... later, on the 'release' branch ...
        $ git pull . 3549 4320 4485...

With that, we could give a default merge message formatted like this:

    Merge 3549, 4320, 4485, 4588, 4980, 5483, 5651, acpica, asus, fops and pnpacpi branches into release

    3549: http://bugzilla.kernel.org/show_bug.cgi?id=3549
     [ACPI] Disable C2/C3 for _all_ IBM R40e Laptops

    4320: http://bugzilla.kernel.org/show_bug.cgi?id=4320
     [ACPI] fix reboot upon suspend-to-disk

    5483: http://bugzilla.kernel.org/show_bug.cgi?id=5483
     [ACPI] fix acpi_cpufreq.c build warrning
     [ACPI] IA64 ZX1 buildfix for _PDC patch
     [ACPI] Avoid BIOS inflicted crashes by evaluating _PDC only once

    pnpacpi: work on PNP-ACPI issues
     [PNPACPI] clean excluded_id_list[]
     [PNPACPI] Ignore devices that have no resources
     [ACPI] enable PNPACPI support for resource types used by HP serial ports

This last digression might be too much, though.  It may be
something that is better computed by 'git log' while reviewing
history, except that the description of each branch cannot be
given that way.

Re: The merge from hell...

[Linus Torvalds]

On Fri, 3 Feb 2006, Junio C Hamano wrote:
> 
> It might make sense if we have a tool support to pre-format the
> merge messages like this, given set of branch names:
> 
>     [ACPI] Merge 3549, 4320, 4485, 4588, 4980, 5483, 5651, acpica, asus, fops and pnpacpi branches into release
> 
>     3549: [ACPI] Disable C2/C3 for _all_ IBM R40e Laptops
>     4320: [ACPI] fix reboot upon suspend-to-disk
>     4485: [ACPI] handle BIOS with implicit C1 in _CST
..

Well, this is actually not all that different from what gitk will show you 
(since I added the commit "explanation" names with my increadible 
copy-paste skills to it).

Just look in the details window in gitk on that merge, and that's pretty 
much exactly what you'll see, except you'll also have the nice clickable 
hyperlink features ;)

Yeah, it doesn't show the branch names _and_ it shows the commit that you 
merged into too, so it looks like

  Parent: 3ee68.. ([SPARC64]: Use compat_sys_futimesat in 32-bit syscall table.)
  Parent: 876c1.. ([ACPI] Disable C2/C3 for _all_ IBM R40e Laptops)
  Parent: 729b4.. ([ACPI] fix reboot upon suspend-to-disk)
  Parent: cf824.. ([ACPI] handle BIOS with implicit C1 in _CST)

but it's actually pretty readable there.

		Linus

[PATCH] fmt-merge-msg: show summary of what is merged.

[Junio C Hamano]

Linus Torvalds <torvalds@osdl.org> writes:

> Yeah, it doesn't show the branch names _and_ it shows the commit that you 
> merged into too, so it looks like
>
>   Parent: 3ee68.. ([SPARC64]: Use compat_sys_futimesat in 32-bit syscall table.)
>   Parent: 876c1.. ([ACPI] Disable C2/C3 for _all_ IBM R40e Laptops)
>   Parent: 729b4.. ([ACPI] fix reboot upon suspend-to-disk)
>   Parent: cf824.. ([ACPI] handle BIOS with implicit C1 in _CST)
>
> but it's actually pretty readable there.

Fair enough.  I myself do not use gitk that often than I use
'git log'.  Something like this patch is what I've been thinking
of doing (it actually works rather nicely if you try to recreate
Len's merge).

-- >8 --
This was prompted by Len's 12-way octopus.  In addition to
the branch names, populate the log message with one-line
description from actual commits that are being merged.

This is experimental.  You need to have 'merge.summary'
in the configuration file to enable it:

	$ git repo-config merge.summary yes

Signed-off-by: Junio C Hamano <junkio@cox.net>

---

 git-fmt-merge-msg.perl |   79 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 77 insertions(+), 2 deletions(-)

b145e0d7a5fc728c00925b55c8a2c2a97788536b
diff --git a/git-fmt-merge-msg.perl b/git-fmt-merge-msg.perl
index 778388e..9ac3c87 100755
--- a/git-fmt-merge-msg.perl
+++ b/git-fmt-merge-msg.perl
@@ -27,10 +27,47 @@ sub andjoin {
 	return ($m);
 }
 
+sub repoconfig {
+	my $fh;
+	my $val;
+	eval {
+		open $fh, '-|', 'git-repo-config', '--get', 'merge.summary'
+		    or die "$!";
+		($val) = <$fh>;
+		close $fh;
+	};
+	return $val;
+}
+
+sub mergebase {
+	my ($other) = @_;
+	my $fh;
+	open $fh, '-|', 'git-merge-base', '--all', 'HEAD', $other or die "$!";
+	my (@mb) = map { chomp; $_ } <$fh>;
+	close $fh or die "$!";
+	return @mb;
+}
+
+sub shortlog {
+	my ($tip, $limit, @base) = @_;
+	my ($fh, @result);
+	open $fh, '-|', ('git-log', "--max-count=$limit", '--topo-order',
+			 '--pretty=oneline', $tip, map { "^$_" } @base)
+	    or die "$!";
+	while (<$fh>) {
+		s/^[0-9a-f]{40}\s+//;
+		push @result, $_;
+	}
+	close $fh or die "$!";
+	return @result;
+}
+
+my @origin = ();
 while (<>) {
-	my ($bname, $tname, $gname, $src);
+	my ($bname, $tname, $gname, $src, $sha1, $origin);
 	chomp;
-	s/^[0-9a-f]*	//;
+	s/^([0-9a-f]*)	//;
+	$sha1 = $1;
 	next if (/^not-for-merge/);
 	s/^	//;
 	if (s/ of (.*)$//) {
@@ -52,19 +89,30 @@ while (<>) {
 		};
 	}
 	if (/^branch (.*)$/) {
+		$origin = $1;
 		push @{$src{$src}{BRANCH}}, $1;
 		$src{$src}{HEAD_STATUS} |= 2;
 	}
 	elsif (/^tag (.*)$/) {
+		$origin = $_;
 		push @{$src{$src}{TAG}}, $1;
 		$src{$src}{HEAD_STATUS} |= 2;
 	}
 	elsif (/^HEAD$/) {
+		$origin = $src;
 		$src{$src}{HEAD_STATUS} |= 1;
 	}
 	else {
 		push @{$src{$src}{GENERIC}}, $_;
 		$src{$src}{HEAD_STATUS} |= 2;
+		$origin = $src;
+	}
+	if ($src eq '.' || $src eq $origin) {
+		$origin =~ s/^'(.*)'$/$1/;
+		push @origin, [$sha1, "$origin"];
+	}
+	else {
+		push @origin, [$sha1, "$origin of $src"];
 	}
 }
 
@@ -93,3 +141,30 @@ for my $src (@src) {
 	push @msg, $this;
 }
 print "Merge ", join("; ", @msg), "\n";
+
+if (!repoconfig) {
+	exit(0);
+}
+
+# We limit the merge message to the latst 20 or so per each branch.
+my $limit = 20;
+
+for (@origin) {
+	my ($sha1, $name) = @$_;
+	my @mb = mergebase($sha1);
+	my @log = shortlog($sha1, $limit, @mb);
+	if ($limit + 1 <= @log) {
+		print "\n* $name: (" . scalar(@log) . " commits)\n";
+	}
+	else {
+		print "\n* $name:\n";
+	}
+	my $cnt = 0;
+	for my $log (@log) {
+		if ($limit < ++$cnt) {
+			print "  ...\n";
+			last;
+		}
+		print "  $log";
+	}
+}
-- 
1.1.6.ge2129

Re: The merge from hell...

[Paul Mackerras]

Junio C Hamano writes:

> Linus Torvalds <torvalds@osdl.org> writes:
> > That octopus commit has got _twelve_ parents.

Making it a dodecapus, or something? :)

> But this is still interesting:
> 
> @@@@@@@@@@@@@ +308,35 @@@@@@@@@@@@@
>             			goto end;
>             		}
>             	}
>   --        	cx->usage++;
>   --        
>             
>      +++    #ifdef CONFIG_HOTPLUG_CPU
>      +++    	/*

Why is that interesting?  It seems to me that two independent changes
were made that just happened to be within a couple of lines of each
other, but didn't interact.  The reason that one change appears in two
branches, and the other in 3, is I think just related to where the
branches start from.  So IMHO this hunk isn't interesting.

Paul.

Re: The merge from hell...

[Junio C Hamano]

Paul Mackerras <paulus@samba.org> writes:

> Why is that interesting?  It seems to me that two independent changes
> were made that just happened to be within a couple of lines of each
> other, but didn't interact.

I agree th hunk in that particular case is not that interesting.

Things are not black and white but you have to draw a line
somewhere.  "Happend to be within a couple of lines" is where we
currently draw that line (it is called "context").

Re: The merge from hell...

[Linus Torvalds]

On Sat, 4 Feb 2006, Paul Mackerras wrote:
> 
> > But this is still interesting:
> > 
> > @@@@@@@@@@@@@ +308,35 @@@@@@@@@@@@@
> >             			goto end;
> >             		}
> >             	}
> >   --        	cx->usage++;
> >   --        
> >             
> >      +++    #ifdef CONFIG_HOTPLUG_CPU
> >      +++    	/*
> 
> Why is that interesting?  It seems to me that two independent changes
> were made that just happened to be within a couple of lines of each
> other, but didn't interact.

Correct. It's "interesting" only because the context of three lines 
overlapped. So _technically_ it's not that interesting.

> The reason that one change appears in two branches, and the other in 3, 
> is I think just related to where the branches start from.  So IMHO this 
> hunk isn't interesting.

I actually think that whenever there are edits this close (even if they 
aren't strictly overlapping) they actually _are_ interesting. Even if it 
merged automatically, you may well want to know that the automated merge 
did something like this.

Doing a 

	git-rev-list --parents HEAD |
		egrep '^.{90}' |
		cut -d' ' -f1 | 
		git-diff-tree --pretty --cc --stdin
		| less -S

on the kernel is actually interesting. It's interesting because it shows 
that out of 1391 merges, in the kernel, only _19_ actually had these close 
calls. Some - but certainly not all - of them actually did need manual 
fixup.

So I actually prefer the "show close misses" case. But I guess we could 
have a "-cN" line to tell how many lines of context to use..

		Linus

Re: The merge from hell...

[Linus Torvalds]

On Sat, 4 Feb 2006, Linus Torvalds wrote:
> 
> Doing a 
> 
> 	git-rev-list --parents HEAD |
> 		egrep '^.{90}' |
> 		cut -d' ' -f1 | 
> 		git-diff-tree --pretty --cc --stdin
> 		| less -S
> 
> on the kernel is actually interesting. It's interesting because it shows 
> that out of 1391 merges, in the kernel, only _19_ actually had these close 
> calls. Some - but certainly not all - of them actually did need manual 
> fixup.

There are some doubly interesting lessons when I looked closer.

In particular, some merges that needed manual fixups do _not_ show up. I 
found that surprising, at first. I expected that if I had to fix something 
manually, it would obviously show up in the "--cc" output.

Not so.  In fact, the one I looked closer at didn't show up even in the 
"long" version, aka "-c".

The reason? A lot of the manual fixups end up selecting one version or the 
other - the clash is because two people fixes the same bug slightly 
differently, and the manual merge will end up just selecting one of them. 
So then even "-c" won't show it, because it will notice that the whole 
file was actually the same as one of the branches merged.

That may be a bit non-intuitive (maybe it shouldn't be, and it was just me 
who didn't think about it the right way when I was initially surprised), 
but it was definitely the right thing (both from a merge standpoint _and_ 
from a "what happened" standpoint) in the cases I looked at. The merge may 
have been manual, but the end _result_ was trivial, and thus isn't shown.

So even after looking at it more, and searching for "interesting" cases 
from the other side, I really like the current git-diff-tree --cc output. 
It sometimes shows you things you wouldn't expect, and it sometimes 
doesn't show you things you'd expect to show up, but in both cases it 
shows/avoids the _right_ things.

However, the point that a "diff" itself isn't totally unambigious is well 
taken. You're right that the very first hunk of the 12-way merge is really 
not interesting.

However, looking at the other cases, it seems to not really be a huge 
problem - that seems to be the only case in the whole kernel - and the 
git-diff-tree algorithm may show an unnecessary hunk once in a blue moon, 
but that's better than having the heuristics fail the other way around (ie 
not showing a hunk).

That's what the gitk problem was, btw (showing too little, not too much). 
Current gitk fails on this trivial case:

	mkdir test-merge
	cd test-merge/
	git-init-db 

	#
	# Initial silly contents
	#
	echo "Hello" > hello
	echo "Hi" > hi
	git add hello hi
	git commit -m "Initial"

	#
	# Create another branch
	#
	git branch other

	#
	# Edit the contents on the master branch,
	# commit it.
	#
	echo "Hello there" > hello
	git commit -m "first change" hello

	#
	# Edit/commit the other differently
	#
	git checkout other
	echo "Hello differently" > hello
	git commit -m "second change" hello

	#
	# Try to merge - this will fail
	#
	git checkout master
	git merge "Clashing merge" HEAD other

	#
	# Do an evil merge conflict that also edits a 
	# nonconflicting file
	#
	echo "Hello third version" > hello
	echo "Hidden hi change" > hi 
	git commit -m "Evil merge conflict" hello hi

At this point, "git-diff-tree --cc HEAD" shows exactly the right thing, 
but "gitk" doesn't show anything at all for that merge (it shows the 
"hello" file in the file pane, but no diff at all, and certainly not the 
"hi" file which it _should_ show).

		Linus

Re: The merge from hell...

[Linus Torvalds]

On Thu, 2 Feb 2006, Junio C Hamano wrote:
>
> Linus Torvalds <torvalds@osdl.org> writes:
> >
> > Ahh. You're mis-using git-diff-tree.
> >
> > git-diff-tree will _never_ show the commit log if the diff ends up being 
> > empty.
> 
> True, I should fix the documentation.
> 
> It _might_ make sense for certain users like gitk and gitview if
> we had a single tool that gives --pretty and its diff even if
> the diff is empty.  Having said that, the flag --cc -m is too
> specific.  If some uses want to see the commit log even for an
> empty diff, that flag should not be something only --cc honors.

Here's an "--always" flag that does that.

		Linus

---
diff --git a/diff-tree.c b/diff-tree.c
index 6593a69..2df23c6 100644
--- a/diff-tree.c
+++ b/diff-tree.c
@@ -10,6 +10,7 @@ static int show_empty_combined = 0;
 static int combine_merges = 0;
 static int dense_combined_merges = 0;
 static int read_stdin = 0;
+static int always_show_header = 0;
 
 static const char *header = NULL;
 static const char *header_prefix = "";
@@ -93,6 +94,10 @@ static const char *generate_header(const
 	offset += pretty_print_commit(commit_format, commit, len,
 				      this_header + offset,
 				      sizeof(this_header) - offset, abbrev);
+	if (always_show_header) {
+		puts(this_header);
+		return NULL;
+	}
 	return this_header;
 }
 
@@ -262,6 +267,10 @@ int main(int argc, const char **argv)
 			no_commit_id = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--always")) {
+			always_show_header = 1;
+			continue;
+		}
 		usage(diff_tree_usage);
 	}
 	if (diff_options.output_format == DIFF_FORMAT_PATCH)