Re: A note on merging conflicts..

Linus Torvalds [off-list ref] writes:

Now, the downside is that the above is both a pain to type, and we don't 
actually even save the MERGE_BASE as a head, so you actually have to 
compute it yourself. It's easy enough to do:

	git-merge-base HEAD MERGE_HEAD > .git/MERGE_BASE

will do it, but the fact is, we should make this even easier.

Heh, that's why I kept saying I want somebody to teach rev-list
a new notation, A...B, to mean $(merge-base A B)..B ;-).

In fact, after writing the above a few times, I really think there's a 
case for making a helper function that does exactly the above for us. 
Including all the "conflicting-filename" thing. It would be nice if

	git log -p --merge [[--] filenames...]

would basically expand to

	git log -p HEAD MERGE_HEAD
		^$(git-merge-base HEAD MERGE_HEAD)
		-- $(git-ls-files -u [filenames...])

so that I wouldn't have to type that by hand ever again, and doing a

	git log -p --merge drivers/

would automatically give me exactly that for all the unmerged files in 
drivers/.

Anybody want to try to make me happy, and learn some git internals at the 
same time?

I fall in the former category but as the current maintainer I
feel I should leave chance to do the latter to others first.  I
wouldn't call it "trivial" but it is not that hard -- I think I
can write it in my head (as Linus can).

On Fri, 30 Jun 2006, Junio C Hamano wrote:

Heh, that's why I kept saying I want somebody to teach rev-list
a new notation, A...B, to mean $(merge-base A B)..B ;-).

I actually don't think that expression makes any sense.

	$(merge-base A B)..B

as an expression only makes sense if there is a single point of forking, 
and no contact apart from that. In that case, what you suggest makes 
sense, because doing

	git diff A...B

is exactly what you want. 

HOWEVER. If there has been any other merges in between (but they aren't 
merge-bases because either branch _also_ did other things), your A...B
expression is meaningless, I think. To do a diff in that case, you really 
need to do my "merge+diff" thing, and no amount of "A...B" expressions on 
a commit relationship level can be meaningful.

Now, the expression

	A...B == B...A == A B --not $(git-merge-base --all A B)

is meaningful (and the one I want for merges), but it's largely useless 
for anything else. It just means "the set of all commits that aren't 
trivially in both" (it's not strictly a valid set operation, but it
approaches being an "xor" instead of a union or an intersection or a 
difference).

But the above isn't useful for "git diff" and friends any more, it's 
mainly just for merging.

			Linus

On Fri, 30 Jun 2006, Linus Torvalds wrote:

(it's not strictly a valid set operation, but it approaches being an 
"xor" instead of a union or an intersection or a difference).

Oh, I guess it _is_ perfectly valid. It's called a "symmetric difference" 
in set theory.

So from a set standpoint:

	Git op:			Set theory:

	git-rev-list a..b	// difference: B - A
	git-rev-list b..a	// difference: A - B

	git-rev-list a b	// union of A B (order doesn't matter)

	git-rev-list a...b	// symmetric difference A B (order doesn't matter)

	git-rev-list $(git-merge-base --all a b)
				// intersection of A and B

I think.

		Linus

On Fri, Jun 30, 2006 at 08:54:33PM -0700, Linus Torvalds wrote:

Now, the expression

	A...B == B...A == A B --not $(git-merge-base --all A B)

is meaningful (and the one I want for merges), but it's largely useless 
for anything else. It just means "the set of all commits that aren't 
trivially in both" (it's not strictly a valid set operation, but it
approaches being an "xor" instead of a union or an intersection or a 
difference).

You mean something like the following patch on top of the 'next' branch?
It also documents the --not switch because I needed it for the example.

TODO: There are still a few undocumented options left and setup_revisions()
is fat and ugly.  Any volunteers?  I'd clean it up if I only could
write comprehensible documentation and wasn't that lazy..

Signed-off-by: Rene Scharfe <redacted>

diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
index ad6d14c..ffbf0c9 100644
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt

@@ -15,6 +15,7 @@ SYNOPSIS
 	     [ \--sparse ]
 	     [ \--no-merges ]
 	     [ \--remove-empty ]
+	     [ \--not ]
 	     [ \--all ]
 	     [ \--topo-order ]
 	     [ \--parents ]

@@ -37,6 +38,14 @@ not in 'baz'".
 A special notation <commit1>..<commit2> can be used as a
 short-hand for {caret}<commit1> <commit2>.
 
+Another special notation is <commit1>...<commit2> which is useful for
+merges.  The resulting set of commits is the symmetric difference
+between the two operands.  The following two commands are equivalent:
+
+------------
+$ git-rev-list A B --not $(git-merge-base --all A B)
+$ git-rev-list A...B
+------------
 
 OPTIONS
 -------

@@ -93,6 +102,11 @@ OPTIONS
 --remove-empty::
 	Stop when a given path disappears from the tree.
 
+--not::
+	Reverses the meaning of the '{caret}' prefix (or lack
+	thereof) for all following revision specifiers, up to
+	the next `--not`.
+
 --all::
 	Pretend as if all the refs in `$GIT_DIR/refs/` are
 	listed on the command line as <commit>.

diff --git a/revision.c b/revision.c
index ae4ca82..d4224a1 100644
--- a/revision.c
+++ b/revision.c

@@ -766,6 +766,47 @@ int setup_revisions(int argc, const char
 			left++;
 			continue;
 		}
+		dotdot = strstr(arg, "...");
+		if (dotdot) {
+			unsigned char other_sha1[20];
+			const char *one = arg;
+			const char *two = dotdot + 3;
+			*dotdot = '\0';
+			if (dotdot == arg)
+				one = "HEAD";
+			if (!*two)
+				two = "HEAD";
+			if (!get_sha1(one, sha1) &&
+			    !get_sha1(two, other_sha1)) {
+				struct commit *a, *b;
+				struct commit_list *exclude;
+
+				a = lookup_commit_reference(sha1);
+				b = lookup_commit_reference(other_sha1);
+				if (!a || !b)
+					die("Invalid symmetric difference expression %s...%s", arg, two);
+
+				if (!seen_dashdash) {
+					*dotdot = '.';
+					verify_non_filename(revs->prefix, arg);
+
+				}
+				exclude = get_merge_bases(a, b);
+				while (exclude) {
+					struct object *object =
+						&exclude->item->object;
+					object->flags |= flags ^ UNINTERESTING;
+					add_pending_object(revs, object, sha1_to_hex(object->sha1));
+					exclude = exclude->next;
+				}
+				a->object.flags |= flags;
+				add_pending_object(revs, &a->object, one);
+				b->object.flags |= flags;
+				add_pending_object(revs, &b->object, two);
+				continue;
+			}
+			*dotdot = '.';
+		}
 		dotdot = strstr(arg, "..");
 		if (dotdot) {
 			unsigned char from_sha1[20];

Hi,

On Sat, 1 Jul 2006, Rene Scharfe wrote:

+				exclude = get_merge_bases(a, b);

Aaah! Junio, Linus, I see the light now.

Ciao,
Dscho

On Sat, 1 Jul 2006, Rene Scharfe wrote:

You mean something like the following patch on top of the 'next' branch?
It also documents the --not switch because I needed it for the example.

Yes. 

However, I think that 90% of the code for the ".." and "..." case are the 
same, as is largely the finding of it.

So why not just do this all inside the already existing

	dotdot = strstr(arg, "..");
	if (dotdot) {
		unsigned char other_sha1[20];
		const char *one = arg;
		const char *two = arg + 2;
		int symmetric = *two == '.';

		*dotdot = '\0';
		two += symmetric;

		if (one == arg)
			one = "HEAD";
		if (!*two)
			two = "HEAD";
		...

because the only difference is really at the very end.

Did you test that it looks correct too?

		Linus

On Sat, Jul 01, 2006 at 05:09:26PM +0200, Rene Scharfe wrote:

+Another special notation is <commit1>...<commit2> which is useful for
+merges.  The resulting set of commits is the symmetric difference
+between the two operands.  The following two commands are equivalent:

What's the logic behind naming the operator "..."?

Seems like asking for trouble to have two visually similar operators (".." and
"...") with different meanings, and "..." seems like kind of an arbitrary
choice anyway.

A symmetric difference is basically equivalent to an xor--would a carat ("^")
work?  Or could we just stick a word there instead of using some tricky
notation?

--b.

On Sat, Jul 01, 2006 at 09:25:43AM -0700, Linus Torvalds wrote:

On Sat, 1 Jul 2006, Rene Scharfe wrote:

quoted

You mean something like the following patch on top of the 'next' branch?
It also documents the --not switch because I needed it for the example.

Yes. 

However, I think that 90% of the code for the ".." and "..." case are the 
same, as is largely the finding of it.

So why not just do this all inside the already existing

	dotdot = strstr(arg, "..");
	if (dotdot) {
		unsigned char other_sha1[20];
		const char *one = arg;
		const char *two = arg + 2;
		int symmetric = *two == '.';

		*dotdot = '\0';
		two += symmetric;

		if (one == arg)
			one = "HEAD";
		if (!*two)
			two = "HEAD";
		...

because the only difference is really at the very end.

Hrm, I'm not sure this is really cleaner.  The two operators consist
of all dots only coincidentally, this is not functionally inherent.
So I think it's better to keep them apart.

Let's see..  [Time passes.  A patch materializes at six o'clock.]

With a little helper factored out this doesn't look as bad as I
imagined.  Maybe we can take it.  What do you think?

Did you test that it looks correct too?

Sort of; I checked that the two forms (with ... and $(git-merge-base))
gave the same results for 7b8cf0cf and 51d1e83f, that's all.  For a
proper test script we'd need to create a repo for which git-merge-base
can report multiple results.  I wasn't able to come up with the needed
commands without thinking and gave up for now.  Am working on it..

Signed-off-by: Rene Scharfe <redacted>

diff --git a/Documentation/git-rev-list.txt b/Documentation/git-rev-list.txt
index ad6d14c..6c370e1 100644
--- a/Documentation/git-rev-list.txt
+++ b/Documentation/git-rev-list.txt

@@ -15,6 +15,7 @@ SYNOPSIS
 	     [ \--sparse ]
 	     [ \--no-merges ]
 	     [ \--remove-empty ]
+	     [ \--not ]
 	     [ \--all ]
 	     [ \--topo-order ]
 	     [ \--parents ]

@@ -37,6 +38,14 @@ not in 'baz'".
 A special notation <commit1>..<commit2> can be used as a
 short-hand for {caret}<commit1> <commit2>.
 
+Another special notation is <commit1>...<commit2> which is useful for
+merges.  The resulting set of commits is the symmetric difference
+between the two operands.  The following two commands are equivalent:
+
+------------
+$ git-rev-list A B --not $(git-merge-base --all A B)
+$ git-rev-list A...B
+------------
 
 OPTIONS
 -------

@@ -93,6 +102,11 @@ OPTIONS
 --remove-empty::
 	Stop when a given path disappears from the tree.
 
+--not::
+	Reverses the meaning of the '{caret}' prefix (or lack
+	thereof) for all following revision specifiers, up to
+	the next `--not`.
+
 --all::
 	Pretend as if all the refs in `$GIT_DIR/refs/` are
 	listed on the command line as <commit>.

diff --git a/revision.c b/revision.c
index ae4ca82..bcedf66 100644
--- a/revision.c
+++ b/revision.c

@@ -536,6 +536,18 @@ void init_revisions(struct rev_info *rev
 	diff_setup(&revs->diffopt);
 }
 
+static void add_pending_commit_list(struct rev_info *revs,
+                                    struct commit_list *commit_list,
+                                    unsigned int flags)
+{
+	while (commit_list) {
+		struct object *object = &commit_list->item->object;
+		object->flags |= flags;
+		add_pending_object(revs, object, sha1_to_hex(object->sha1));
+		commit_list = commit_list->next;
+	}
+}
+
 /*
  * Parse revision information, filling in the "rev_info" structure,
  * and removing the used arguments from the argument list.

@@ -771,27 +783,45 @@ int setup_revisions(int argc, const char
 			unsigned char from_sha1[20];
 			const char *next = dotdot + 2;
 			const char *this = arg;
+			int symmetric = *next == '.';
+			unsigned int flags_exclude = flags ^ UNINTERESTING;
+
 			*dotdot = 0;
+			next += symmetric;
+
 			if (!*next)
 				next = "HEAD";
 			if (dotdot == arg)
 				this = "HEAD";
 			if (!get_sha1(this, from_sha1) &&
 			    !get_sha1(next, sha1)) {
-				struct object *exclude;
-				struct object *include;
-
-				exclude = get_reference(revs, this, from_sha1, flags ^ UNINTERESTING);
-				include = get_reference(revs, next, sha1, flags);
-				if (!exclude || !include)
-					die("Invalid revision range %s..%s", arg, next);
+				struct commit *a, *b;
+				struct commit_list *exclude;
+
+				a = lookup_commit_reference(from_sha1);
+				b = lookup_commit_reference(sha1);
+				if (!a || !b) {
+					die(symmetric ?
+					    "Invalid symmetric difference expression %s...%s" :
+					    "Invalid revision range %s..%s",
+					    arg, next);
+				}
 
 				if (!seen_dashdash) {
 					*dotdot = '.';
 					verify_non_filename(revs->prefix, arg);
 				}
-				add_pending_object(revs, exclude, this);
-				add_pending_object(revs, include, next);
+
+				if (symmetric) {
+					exclude = get_merge_bases(a, b);
+					add_pending_commit_list(revs, exclude,
+					                        flags_exclude);
+					a->object.flags |= flags;
+				} else
+					a->object.flags |= flags_exclude;
+				b->object.flags |= flags;
+				add_pending_object(revs, &a->object, this);
+				add_pending_object(revs, &b->object, next);
 				continue;
 			}
 			*dotdot = '.';

On Sat, 1 Jul 2006, J. Bruce Fields wrote:

What's the logic behind naming the operator "..."?

Well, if ".." is set difference, why not "..." for symmetric set 
difference.

The operations really _are_ related.

Also, the parse syntax and logic really is the same, even if Rene's patch 
didn't take advantage of that.

That said, it does have a real downside, and that's simply that it can 
take a long time to compute.

Somebody should also verify that there are no interesting interaction with 
the fact that we end up traversing the commit lists twice (no object flag 
interactions etc) with the new "get_merge_bases()"

		Linus

J. Bruce Fields wrote:

On Sat, Jul 01, 2006 at 05:09:26PM +0200, Rene Scharfe wrote:

quoted

+Another special notation is <commit1>...<commit2> which is useful for
+merges.  The resulting set of commits is the symmetric difference
+between the two operands.  The following two commands are equivalent:

What's the logic behind naming the operator "..."?

Seems like asking for trouble to have two visually similar operators (".." and
"...") with different meanings, and "..." seems like kind of an arbitrary
choice anyway.

Because A...B is extension of A..B for merges.

A symmetric difference is basically equivalent to an xor--would a carat ("^")
work?  Or could we just stick a word there instead of using some tricky
notation?

Caret is used twice, with different meaning. As prefix operator "^" means 
"exclude lineage of commit" (while commit without "^" in front means:
"include lineage of commit and commit itself"). BTW. why we don't use '!'
for that?

As postfix operator "^" means "dereference", i.e. parent in the case 
of commit; allows choosing a parent (commit^n) and listing all parents 
(commit^@). Using it as binary infix operator that would be I think 
too much. 

-- 
Jakub Narebski
Warsaw, Poland
ShadeHawk on #git

On Sat, 1 Jul 2006, Jakub Narebski wrote:

Caret is used twice, with different meaning. As prefix operator "^" means 
"exclude lineage of commit" (while commit without "^" in front means:
"include lineage of commit and commit itself"). BTW. why we don't use '!'
for that?

Using '!' is really nasty with most shells. Avoid, avoid, avoid.

It would be more sensible to use ~ (mathematical negation), but that also 
has magic meaning for shell at the beginning of a word..

			Linus

On Sat, 1 Jul 2006, Linus Torvalds wrote:

That said, it does have a real downside, and that's simply that it can 
take a long time to compute.

I think a...b can be computed by (in pseudocode, obviously):

 mark(a, 1);
 add(list, a);
 mark(b, 2);
 add(list, b);
 while (interesting(list)) {
   if (*list->marks != 3)
     output(*list);
   for (parent : *list->parents) {
     mark(parent, *list->marks);
     add(list, parent);
   }
 }

It's basically the original merge-bases code, from way back; the several 
flaws with it for computing a good merge base don't matter if you're just 
excluding the merge bases. If you look at the big examples in merge-base.c 
(pre-libification), it's obvious that what we want for a...b is everything 
marked 1 or 2, and the trickiness in that code is getting things correctly 
marked 3 versus 7, which doesn't matter here.

	-Daniel
*This .sig left intentionally blank*

On Sat, 1 Jul 2006, Daniel Barkalow wrote:

I think a...b can be computed by (in pseudocode, obviously):

Nope.

It's basically the original merge-bases code, from way back;

And it has basically the same bug.

It is possible to have

		a
	       / \
	      b   c
	      |\ /|
	      d e f
	       \|/
		g

and clearly "e" is the only valid merge-base of b and c.

HOWEVER. It's actually possible that we traverse d, f and g before we even 
look at 'e' (because somebody had a bogus date, and 'e' _looks_ old).

Remember: in a distributed system we have no global clock, so any graph 
traversal ordering we choose is by definition always arbitrary, even 
though we can obviously _try_ to choose one that is efficient in practice 
(ie the "sort the heap by date).

So that's why git-merge-base has all that extra "unnecessary" complexity. 
You cannot output anything at all until you've guaranteed that all pending 
objects are uninteresting.

				Linus

On Sat, 1 Jul 2006, Linus Torvalds wrote:

On Sat, 1 Jul 2006, Daniel Barkalow wrote:

quoted

I think a...b can be computed by (in pseudocode, obviously):

Nope.

quoted

It's basically the original merge-bases code, from way back;

And it has basically the same bug.

It is possible to have

		a
	       / \
	      b   c
	      |\ /|
	      d e f
	       \|/
		g

and clearly "e" is the only valid merge-base of b and c.

HOWEVER. It's actually possible that we traverse d, f and g before we even 
look at 'e' (because somebody had a bogus date, and 'e' _looks_ old).

But that wouldn't actually affect b...c, because we don't actually care 
that 'e' is the correct merge-base and 'g' is not, because "b c ^e ^g" is 
the same as "b c ^e".

Your point is correct, though; if we look at e before c, we could think 
that it's interesting when it isn't, so we have to wait until we've 
drained the list to output anything.

So that's why git-merge-base has all that extra "unnecessary" complexity. 
You cannot output anything at all until you've guaranteed that all pending 
objects are uninteresting.

That's not all the complexity in git-merge-base, though. There's a ton 
more that's about why e is right and g is wrong in your example, and we 
don't care about *that* part in b...c.

Actually, I think that it would work to have object flags "LEFT" and 
"RIGHT", mark b with left, mark c with right, and mark anything with both 
LEFT and RIGHT as UNINTERESTING as we go through the revisions. The 
time-ordering problem with symmetric difference isn't absent with regular 
difference, and, assuming that b..c works in the tricky cases, the same 
logic should handle symmetric difference.

	-Daniel
*This .sig left intentionally blank*

On Sat, 1 Jul 2006, Daniel Barkalow wrote:

Actually, I think that it would work to have object flags "LEFT" and 
"RIGHT", mark b with left, mark c with right, and mark anything with both 
LEFT and RIGHT as UNINTERESTING as we go through the revisions. The 
time-ordering problem with symmetric difference isn't absent with regular 
difference, and, assuming that b..c works in the tricky cases, the same 
logic should handle symmetric difference.

That is: (this only has the logic portion, and it's against master, so it 
isn't actually a really working patch or anything; also, it doesn't handle 
"--not a...b" correctly, whatever that should mean)

---

diff --git a/revision.c b/revision.c
index 6a6952c..c21d332 100644
--- a/revision.c
+++ b/revision.c

@@ -351,6 +351,9 @@ static void add_parents_to_list(struct r
 		return;
 	commit->object.flags |= ADDED;
 
+	if (commit->object.flags & LEFT && commit->objects.flags & RIGHT)
+		commit->object.flags |= UNINTERESTING;
+
 	/*
 	 * If the commit is uninteresting, don't try to
 	 * prune parents - we want the maximal uninteresting

@@ -781,8 +784,13 @@ int setup_revisions(int argc, const char
 				struct object *exclude;
 				struct object *include;
 
-				exclude = get_reference(revs, this, from_sha1, flags ^ UNINTERESTING);
-				include = get_reference(revs, next, sha1, flags);
+				if (symmetric) {
+					exclude = get_reference(revs, this, from_sha1, flags ^ UNINTERESTING);
+					include = get_reference(revs, next, sha1, flags);
+				} else {
+					exclude = get_reference(revs, this, from_sha1, flags | LEFT_HALF);
+					include = get_reference(revs, next, sha1, flags | RIGHT_HALF);
+				}
 				if (!exclude || !include)
 					die("Invalid revision range %s..%s", arg, next);
 

diff --git a/revision.h b/revision.h
index 7d85b0f..93421e6 100644
--- a/revision.h
+++ b/revision.h

@@ -9,6 +9,8 @@
 #define BOUNDARY	(1u<<5)
 #define BOUNDARY_SHOW	(1u<<6)
 #define ADDED		(1u<<7)	/* Parents already parsed and added? */
+#define LEFT_HALF	(1u<<8) /* Reachable from start of dotdotdot */
+#define RIGHT_HALF	(1u<<9) /* Reachable from end of dotdotdot */
 
 struct rev_info;
 struct log_info;

-- 
1.2.4

On Sat, 1 Jul 2006, Daniel Barkalow wrote:

But that wouldn't actually affect b...c, because we don't actually care 
that 'e' is the correct merge-base and 'g' is not, because "b c ^e ^g" is 
the same as "b c ^e".

You're right - in ths case we don't care about a minimal base commit set 
at all, it's fine to have too many.

I think your patch to do the LEFT/RIGHT thing in git-rev-list internally, 
instead of generating it as part of the command line, looks fine in 
theory. 

Except I think you need to set "revs->limited" for that case too (normally 
it gets set by "handle_commit()", and only if there is an UNINTERESTING 
commit: we'd need to add code to set it for LEFT/RIGHT commits too.

		Linus

On Sat, Jul 01, 2006 at 07:45:33PM -0400, Daniel Barkalow wrote:

That is: (this only has the logic portion, and it's against master, so it 
isn't actually a really working patch or anything; also, it doesn't handle 
"--not a...b" correctly, whatever that should mean)

[concept patch snipped]

You mean something like the patch below?  It seems to work, but in my
unscientific tests it's significant slower than the version based on
get_merge_bases() (0.17s vs 0.05s for
"git-rev-list 89719209...262a6ef7 66ae0c77...ced9456a").  Did I do
something wrong?

You had no mark_parents_left_right() in your patch.  I added it because
otherwise it wouldn't remove any common commits.  Was this supposed to
work some other way?

We still need an automatic test case, and a better benchmark.

diff --git a/revision.c b/revision.c
index ebee05a..8c494ee 100644
--- a/revision.c
+++ b/revision.c

@@ -339,6 +339,20 @@ static void try_to_simplify_commit(struc
 		commit->object.flags |= TREECHANGE;
 }
 
+static void mark_parents_left_right(struct commit *commit)
+{
+	unsigned int flags = commit->object.flags & (RIGHT_HALF | LEFT_HALF);
+	struct commit_list *parents = commit->parents;
+
+	while (parents) {
+		struct commit *p = parents->item;
+		p->object.flags |= flags;
+		if (p->parents)
+			mark_parents_left_right(p);
+		parents = parents->next;
+	}
+}
+
 static void add_parents_to_list(struct rev_info *revs, struct commit *commit, struct commit_list **list)
 {
 	struct commit_list *parent = commit->parents;

@@ -347,6 +361,13 @@ static void add_parents_to_list(struct r
 		return;
 	commit->object.flags |= ADDED;
 
+	if (commit->object.flags & (RIGHT_HALF | LEFT_HALF)) {
+		if (commit->object.flags & RIGHT_HALF &&
+		    commit->object.flags & LEFT_HALF)
+			commit->object.flags |= UNINTERESTING;
+		mark_parents_left_right(commit);
+	}
+
 	/*
 	 * If the commit is uninteresting, don't try to
 	 * prune parents - we want the maximal uninteresting

@@ -772,7 +793,10 @@ int setup_revisions(int argc, const char
 			unsigned char from_sha1[20];
 			const char *next = dotdot + 2;
 			const char *this = arg;
+			int symmetric = *next == '.';
+
 			*dotdot = 0;
+			next += symmetric;
 			if (!*next)
 				next = "HEAD";
 			if (dotdot == arg)

@@ -782,8 +806,13 @@ int setup_revisions(int argc, const char
 				struct object *exclude;
 				struct object *include;
 
-				exclude = get_reference(revs, this, from_sha1, flags ^ UNINTERESTING);
-				include = get_reference(revs, next, sha1, flags);
+				if (symmetric) {
+					exclude = get_reference(revs, this, from_sha1, flags | LEFT_HALF);
+					include = get_reference(revs, next, sha1, flags | RIGHT_HALF);
+				} else {
+					exclude = get_reference(revs, this, from_sha1, flags ^ UNINTERESTING);
+					include = get_reference(revs, next, sha1, flags);
+				}
 				if (!exclude || !include)
 					die("Invalid revision range %s..%s", arg, next);
 

diff --git a/revision.h b/revision.h
index c010a08..0090232 100644
--- a/revision.h
+++ b/revision.h

@@ -9,6 +9,8 @@ #define TMP_MARK	(1u<<4) /* for isolated
 #define BOUNDARY	(1u<<5)
 #define BOUNDARY_SHOW	(1u<<6)
 #define ADDED		(1u<<7)	/* Parents already parsed and added? */
+#define RIGHT_HALF	(1u<<8)
+#define LEFT_HALF	(1u<<9)
 
 struct rev_info;
 struct log_info;

On Sun, 2 Jul 2006, Rene Scharfe wrote:

On Sat, Jul 01, 2006 at 07:45:33PM -0400, Daniel Barkalow wrote:

quoted

That is: (this only has the logic portion, and it's against master, so it 
isn't actually a really working patch or anything; also, it doesn't handle 
"--not a...b" correctly, whatever that should mean)

[concept patch snipped]

You mean something like the patch below?  It seems to work, but in my
unscientific tests it's significant slower than the version based on
get_merge_bases() (0.17s vs 0.05s for
"git-rev-list 89719209...262a6ef7 66ae0c77...ced9456a").  Did I do
something wrong?

You had no mark_parents_left_right() in your patch.  I added it because
otherwise it wouldn't remove any common commits.  Was this supposed to
work some other way?

I'd been assuming that there was something that would propagate flags to 
parents in general in add_parents_to_list(). Of course, that doesn't make 
sense for arbitrary flags. It might be better to handle it there, and 
avoid traversing parent lists twice.

I'm surprised that it isn't faster than using get_merge_bases(); I'd 
expect it to be faster than the call to get_merge_bases(), let alone 
get_merge_bases() plus the processing of output candidates. It should be 
doing less work that get_merge_bases() ultimately does (since 
get_merge_bases() has to do the boundary calculation after doing 
practically everything that the left and right addition to revision.c 
does), so there's clearly something strange going on.

	-Daniel
*This .sig left intentionally blank*