[PATCH 1/2] rev-list: implement --bisect-all

[PATCH 1/2] rev-list: implement --bisect-all

[Christian Couder]

This is Junio's patch with some stuff to make --bisect-all
compatible with --bisect-vars.

This option makes it possible to see all the potential
bisection points. The best ones are displayed first.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 builtin-rev-list.c |   98 +++++++++++++++++++++++++++++++++++++++++++++-------
 log-tree.c         |    2 +-
 log-tree.h         |    1 +
 3 files changed, 87 insertions(+), 14 deletions(-)

diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 33726b8..0943b76 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -9,6 +9,7 @@
 #include "revision.h"
 #include "list-objects.h"
 #include "builtin.h"
+#include "log-tree.h"
 
 /* bits #0-15 in revision.h */
 
@@ -39,6 +40,7 @@ static const char rev_list_usage[] =
 "  special purpose:\n"
 "    --bisect\n"
 "    --bisect-vars"
+"    --bisect-all"
 ;
 
 static struct rev_info revs;
@@ -74,6 +76,7 @@ static void show_commit(struct commit *commit)
 			parents = parents->next;
 		}
 	}
+	show_decorations(commit);
 	if (revs.commit_format == CMIT_FMT_ONELINE)
 		putchar(' ');
 	else
@@ -278,6 +281,57 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)
 	return best;
 }
 
+struct commit_dist {
+	struct commit *commit;
+	int distance;
+};
+
+static int compare_commit_dist(const void *a_, const void *b_)
+{
+	struct commit_dist *a, *b;
+
+	a = (struct commit_dist *)a_;
+	b = (struct commit_dist *)b_;
+	if (a->distance != b->distance)
+		return b->distance - a->distance; /* desc sort */
+	return hashcmp(a->commit->object.sha1, b->commit->object.sha1);
+}
+
+static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
+{
+	struct commit_list *p;
+	struct commit_dist *array = xcalloc(nr, sizeof(*array));
+	int cnt, i;
+
+	for (p = list, cnt = 0; p; p = p->next) {
+		int distance;
+		unsigned flags = p->item->object.flags;
+
+		if (revs.prune_fn && !(flags & TREECHANGE))
+			continue;
+		distance = weight(p);
+		if (nr - distance < distance)
+			distance = nr - distance;
+		array[cnt].commit = p->item;
+		array[cnt].distance = distance;
+		cnt++;
+	}
+	qsort(array, cnt, sizeof(*array), compare_commit_dist);
+	for (p = list, i = 0; i < cnt; i++) {
+		struct name_decoration *r = xmalloc(sizeof(*r) + 100);
+		struct object *obj = &(array[i].commit->object);
+
+		sprintf(r->name, "dist=%d", array[i].distance);
+		r->next = add_decoration(&name_decoration, obj, r);
+		p->item = array[i].commit;
+		p = p->next;
+	}
+	if (p)
+		p->next = NULL;
+	free(array);
+	return list;
+}
+
 /*
  * zero or positive weight is the number of interesting commits it can
  * reach, including itself.  Especially, weight = 0 means it does not
@@ -292,7 +346,8 @@ static struct commit_list *best_bisection(struct commit_list *list, int nr)
  * or positive distance.
  */
 static struct commit_list *do_find_bisection(struct commit_list *list,
-					     int nr, int *weights)
+					     int nr, int *weights,
+					     int find_all)
 {
 	int n, counted;
 	struct commit_list *p;
@@ -351,7 +406,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		clear_distance(list);
 
 		/* Does it happen to be at exactly half-way? */
-		if (halfway(p, nr))
+		if (!find_all && halfway(p, nr))
 			return p;
 		counted++;
 	}
@@ -389,19 +444,22 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 				weight_set(p, weight(q));
 
 			/* Does it happen to be at exactly half-way? */
-			if (halfway(p, nr))
+			if (!find_all && halfway(p, nr))
 				return p;
 		}
 	}
 
 	show_list("bisection 2 counted all", counted, nr, list);
 
-	/* Then find the best one */
-	return best_bisection(list, nr);
+	if (!find_all)
+		return best_bisection(list, nr);
+	else
+		return best_bisection_sorted(list, nr);
 }
 
 static struct commit_list *find_bisection(struct commit_list *list,
-					  int *reaches, int *all)
+					  int *reaches, int *all,
+					  int find_all)
 {
 	int nr, on_list;
 	struct commit_list *p, *best, *next, *last;
@@ -434,14 +492,13 @@ static struct commit_list *find_bisection(struct commit_list *list,
 	weights = xcalloc(on_list, sizeof(*weights));
 
 	/* Do the real work of finding bisection commit. */
-	best = do_find_bisection(list, nr, weights);
-
+	best = do_find_bisection(list, nr, weights, find_all);
 	if (best) {
-		best->next = NULL;
+		if (!find_all)
+			best->next = NULL;
 		*reaches = weight(best);
 	}
 	free(weights);
-
 	return best;
 }
 
@@ -468,6 +525,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	int i;
 	int read_from_stdin = 0;
 	int bisect_show_vars = 0;
+	int bisect_find_all = 0;
 
 	git_config(git_default_config);
 	init_revisions(&revs, prefix);
@@ -490,6 +548,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			bisect_list = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--bisect-all")) {
+			bisect_list = 1;
+			bisect_find_all = 1;
+			continue;
+		}
 		if (!strcmp(arg, "--bisect-vars")) {
 			bisect_list = 1;
 			bisect_show_vars = 1;
@@ -536,9 +599,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (bisect_list) {
 		int reaches = reaches, all = all;
 
-		revs.commits = find_bisection(revs.commits, &reaches, &all);
+		revs.commits = find_bisection(revs.commits, &reaches, &all,
+					      bisect_find_all);
 		if (bisect_show_vars) {
 			int cnt;
+			char hex[41];
 			if (!revs.commits)
 				return 1;
 			/*
@@ -550,15 +615,22 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			 * A bisect set of size N has (N-1) commits further
 			 * to test, as we already know one bad one.
 			 */
-			cnt = all-reaches;
+			cnt = all - reaches;
 			if (cnt < reaches)
 				cnt = reaches;
+			strcpy(hex, sha1_to_hex(revs.commits->item->object.sha1));
+
+			if (bisect_find_all) {
+				traverse_commit_list(&revs, show_commit, show_object);
+				printf("------\n");
+			}
+
 			printf("bisect_rev=%s\n"
 			       "bisect_nr=%d\n"
 			       "bisect_good=%d\n"
 			       "bisect_bad=%d\n"
 			       "bisect_all=%d\n",
-			       sha1_to_hex(revs.commits->item->object.sha1),
+			       hex,
 			       cnt - 1,
 			       all - reaches - 1,
 			       reaches - 1,
diff --git a/log-tree.c b/log-tree.c
index 2319154..f766758 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -15,7 +15,7 @@ static void show_parents(struct commit *commit, int abbrev)
 	}
 }
 
-static void show_decorations(struct commit *commit)
+void show_decorations(struct commit *commit)
 {
 	const char *prefix;
 	struct name_decoration *decoration;
diff --git a/log-tree.h b/log-tree.h
index e82b56a..b33f7cd 100644
--- a/log-tree.h
+++ b/log-tree.h
@@ -12,5 +12,6 @@ int log_tree_diff_flush(struct rev_info *);
 int log_tree_commit(struct rev_info *, struct commit *);
 int log_tree_opt_parse(struct rev_info *, const char **, int);
 void show_log(struct rev_info *opt, const char *sep);
+void show_decorations(struct commit *commit);
 
 #endif
-- 
1.5.3.4.208.g996ad

Re: [PATCH 1/2] rev-list: implement --bisect-all

[Johannes Schindelin]

Hi,

On Mon, 8 Oct 2007, Christian Couder wrote:

> This option makes it possible to see all the potential bisection points. 
> The best ones are displayed first.

Would it not be better to pass --bisect-vars a list of commits that we do 
not want to see?  It could then mark them as "DUNNO", and still just 
output a single commit.

IMHO such a logic does not belong into a shell script, but into the C 
core.

Ciao,
Dscho

Re: [PATCH 1/2] rev-list: implement --bisect-all

[Christian Couder]

Hi Dscho,

Le lundi 8 octobre 2007, Johannes Schindelin a écrit :
> Hi,
>
> On Mon, 8 Oct 2007, Christian Couder wrote:
> > This option makes it possible to see all the potential bisection
> > points. The best ones are displayed first.
>
> Would it not be better to pass --bisect-vars a list of commits that we do
> not want to see?  It could then mark them as "DUNNO", and still just
> output a single commit.

The problem is that after --bisect-vars we already pass some "good" and then 
a bad commit. So we have to use another flag like --bisect-dunno and put 
the dunno commits after this one.

Then there is the problem that revision.c reorders arguments and doesn't 
know about "--bisect-*" flags. It is also used by a lot of other commands.

After struggling with revision.c for some time, I thought it would be 
simpler and safer to come up first with something in shell.

Also please note that in some cases we cannot just output a single commit, 
because we just dunno which commit is the first bad one.

> IMHO such a logic does not belong into a shell script, but into the C
> core.

There is a lot of the bisect logic implemented in git-bisect.sh already. The 
long term plan is to rewrite it in C, but I am not sure that the "dunno" 
logic should be the first part of it to be done in C.

Also I thought it was still fine to prototype new features in shell.

Best regards,
Christian.

Re: [PATCH 1/2] rev-list: implement --bisect-all

[Johannes Schindelin]

Hi,

On Mon, 8 Oct 2007, Christian Couder wrote:

> > IMHO such a logic does not belong into a shell script, but into the C 
> > core.
> 
> There is a lot of the bisect logic implemented in git-bisect.sh already. 
> The long term plan is to rewrite it in C,

Oh?  Did I miss something?

> but I am not sure that the "dunno" logic should be the first part of it 
> to be done in C.

The thing is, git-bisect is porcelain-ish.  And by having a lot of the 
functionality there, which is not really porcelain, but plumbing, you 
prevent other porcelains, such as git-gui or qgit, from using that 
function.

Which is bad.

Ciao,
Dscho

Re: [PATCH 1/2] rev-list: implement --bisect-all

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> On Mon, 8 Oct 2007, Christian Couder wrote:
>
>> but I am not sure that the "dunno" logic should be the first part of it 
>> to be done in C.
>
> The thing is, git-bisect is porcelain-ish.  And by having a lot of the 
> functionality there, which is not really porcelain, but plumbing, you 
> prevent other porcelains, such as git-gui or qgit, from using that 
> function.
>
> Which is bad.

Still, it is good to prototype in the script while figuring out
what the desired behaviour is, I would say.

What I was hoping to see when I posted --bisect-all suggestion
was a bit different from what Christian did, by the way.

In addition to the bisect/skip-* that are filtered at the shell
level, if you feed the list of commits that cannot be tested to
the bisection plumbing, you can affect the way the resulting
list from the --bisect-all is sorted.

Suppose you have this (B is bad, G is good):

           o---.........---o---Y---o---o---B
          /                       /
     G---o---.........---o---Z---X

and one round of bisection picked X.  You find it untestable,
and Y and Z both bisects the remaining set equally well.  In
such a case, the current code sorts the resulting set, with Y
and Z next to each other (because they are both closest to the
midway), and the Porcelain filters out X which is better than Y
or Z.  You may end up picking Z.

Often, when X is not testable, neither is Z.  We would be better
off to avoid checking a commit close to what are known to be
untestable while there are other commits that are equally close
to the midway.

So instead of sorting the list solely based on the mid-ness like
the current code does (i.e. compare_commit_dist()), we can tweak
commits' mid-ness value (i.e. best_bisection_sorted() computes
it in distance variable) by penalizing it with the closeness of
the commit to known untestable commits.

Naively, "closeness" of commit Z to commit X can be defined as
something simple as "rev-list Z...X | wc -l".  The smaller the
number, the closer the commits.