[PATCH] Introduce filter_independent() in commit.c

This is similar to git-show-branch --independent: It filters out commits
which are reachable from any other item from the input list.

Signed-off-by: Miklos Vajna <redacted>
---

On Thu, Jun 19, 2008 at 08:03:58PM -0700, Junio C Hamano [off-list ref] wrote:

quoted

+   for (i = heads; i; i = i->next)
+           if (!(i->item->object.flags & RESULT))
+                   pptr = &commit_list_insert(i->item, pptr)->next;

Hmm.  How well was this function tested?

As Dscho pointed out in an other mail there was no testcase for it, I
wrote one and it pointed out what you said: it was buggy.

Because RESULT is an implementation detail of merge_bases(), I do not
think we would want to expose it outside of it.

The new version does not have this problem, either.

More worryingly, the flag is supposed to be cleaned from the objects
after get_merge_bases() returns.  I am not sure what you'll learn by
looking at the flag here.

Yes, you are right. In fact the idea to use get_octopus_merge_bases()
was wrong, since it does not do what we need.

Here is an example:

	A - B
	  \ C
	  \ D
	  \ E - F

In this case get_octopus_merge_bases() will return only A, which is what
it should do, but we need E in filter_indepenent() as well.

Below is what I pushed to my working branch.

This version now passes the test that was failed for the previous one.

 commit.c |   32 ++++++++++++++++++++++++++++++++
 commit.h |    1 +
 2 files changed, 33 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index 6052ca3..17e18d7 100644
--- a/commit.c
+++ b/commit.c

@@ -705,3 +705,35 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)
 	free_commit_list(bases);
 	return ret;
 }
+
+struct commit_list *filter_independent(unsigned char *head,
+	struct commit_list *heads)
+{
+	struct commit_list *b, *i, *j, *k, *bases = NULL, *ret = NULL;
+	struct commit_list **pptr = &ret;
+
+	commit_list_insert(lookup_commit(head), &heads);
+
+	for (i = heads; i; i = i->next) {
+		for (j = heads; j; j = j->next) {
+			if (i == j)
+				continue;
+			b = get_merge_bases(i->item, j->item, 1);
+			for (k = b; k; k = k->next)
+				commit_list_insert(k->item, &bases);
+		}
+	}
+
+	for (i = heads; i; i = i->next) {
+		int found = 0;
+		for (b = bases; b; b = b->next) {
+			if (!hashcmp(i->item->object.sha1, b->item->object.sha1)) {
+				found = 1;
+				break;
+			}
+		}
+		if (!found)
+			pptr = &commit_list_insert(i->item, pptr)->next;
+	}
+	return ret;
+}

diff --git a/commit.h b/commit.h
index dcec7fb..0aef7e4 100644
--- a/commit.h
+++ b/commit.h

@@ -131,6 +131,7 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads,
 		int depth, int shallow_flag, int not_shallow_flag);
 
 int in_merge_bases(struct commit *, struct commit **, int);
+struct commit_list *filter_independent(unsigned char *head, struct commit_list *heads);
 
 extern int interactive_add(int argc, const char **argv, const char *prefix);
 extern int rerere(void);

-- 
1.5.6