[PATCH 07/10] rev-list: call new "filter_skip" function

[PATCH 07/10] rev-list: call new "filter_skip" function

[Christian Couder]

This patch implements a new "filter_skip" function in C in
"bisect.c" that will later replace the existing implementation in
shell in "git-bisect.sh".

An array is used to store the skipped commits. But the array is
not yet fed anything.

Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
---
 bisect.c           |   65 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 bisect.h           |    6 ++++-
 builtin-rev-list.c |   30 ++++++++++++++++++++----
 3 files changed, 95 insertions(+), 6 deletions(-)

diff --git a/bisect.c b/bisect.c
index 27def7d..39189f2 100644
--- a/bisect.c
+++ b/bisect.c
@@ -4,6 +4,11 @@
 #include "revision.h"
 #include "bisect.h"
 
+
+static unsigned char (*skipped_sha1)[20];
+static int skipped_sha1_nr;
+static int skipped_sha1_alloc;
+
 /* bits #0-15 in revision.h */
 
 #define COUNTED		(1u<<16)
@@ -386,3 +391,63 @@ struct commit_list *find_bisection(struct commit_list *list,
 	return best;
 }
 
+static int skipcmp(const void *a, const void *b)
+{
+	return hashcmp(a, b);
+}
+
+static void prepare_skipped(void)
+{
+	qsort(skipped_sha1, skipped_sha1_nr, sizeof(*skipped_sha1), skipcmp);
+}
+
+static int lookup_skipped(unsigned char *sha1)
+{
+	int lo, hi;
+	lo = 0;
+	hi = skipped_sha1_nr;
+	while (lo < hi) {
+		int mi = (lo + hi) / 2;
+		int cmp = hashcmp(sha1, skipped_sha1[mi]);
+		if (!cmp)
+			return mi;
+		if (cmp < 0)
+			hi = mi;
+		else
+			lo = mi + 1;
+	}
+	return -lo - 1;
+}
+
+struct commit_list *filter_skipped(struct commit_list *list,
+				   struct commit_list **tried,
+				   int show_all)
+{
+	struct commit_list *filtered = NULL, **f = &filtered;
+
+	*tried = NULL;
+
+	if (!skipped_sha1_nr)
+		return list;
+
+	prepare_skipped();
+
+	while (list) {
+		struct commit_list *next = list->next;
+		list->next = NULL;
+		if (0 <= lookup_skipped(list->item->object.sha1)) {
+			/* Move current to tried list */
+			*tried = list;
+			tried = &list->next;
+		} else {
+			if (!show_all)
+				return list;
+			/* Move current to filtered list */
+			*f = list;
+			f = &list->next;
+		}
+		list = next;
+	}
+
+	return filtered;
+}
diff --git a/bisect.h b/bisect.h
index 31c99fe..2489630 100644
--- a/bisect.h
+++ b/bisect.h
@@ -5,7 +5,11 @@ extern struct commit_list *find_bisection(struct commit_list *list,
 					  int *reaches, int *all,
 					  int find_all);
 
+extern struct commit_list *filter_skipped(struct commit_list *list,
+					  struct commit_list **tried,
+					  int show_all);
+
 extern int show_bisect_vars(struct rev_info *revs, int reaches, int all,
-			    int show_all);
+			    int show_all, int show_tried);
 
 #endif
diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index cdb0f9d..925d643 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -226,14 +226,28 @@ static int estimate_bisect_steps(int all)
 	return (e < 3 * x) ? n : n - 1;
 }
 
-int show_bisect_vars(struct rev_info *revs, int reaches, int all, int show_all)
+static void show_tried_revs(struct commit_list *tried)
+{
+	printf("bisect_tried='");
+	for (;tried; tried = tried->next) {
+		char *format = tried->next ? "%s|" : "%s";
+		printf(format, sha1_to_hex(tried->item->object.sha1));
+	}
+	printf("'\n");
+}
+
+int show_bisect_vars(struct rev_info *revs, int reaches, int all,
+		     int show_all, int show_tried)
 {
 	int cnt;
-	char hex[41];
+	char hex[41] = "";
+	struct commit_list *tried;
 
-	if (!revs->commits)
+	if (!revs->commits && !show_tried)
 		return 1;
 
+	revs->commits = filter_skipped(revs->commits, &tried, show_all);
+
 	/*
 	 * revs->commits can reach "reaches" commits among
 	 * "all" commits.  If it is good, then there are
@@ -247,13 +261,16 @@ int show_bisect_vars(struct rev_info *revs, int reaches, int all, int show_all)
 	if (cnt < reaches)
 		cnt = reaches;
 
-	strcpy(hex, sha1_to_hex(revs->commits->item->object.sha1));
+	if (revs->commits)
+		strcpy(hex, sha1_to_hex(revs->commits->item->object.sha1));
 
 	if (show_all) {
 		traverse_commit_list(revs, show_commit, show_object);
 		printf("------\n");
 	}
 
+	if (show_tried)
+		show_tried_revs(tried);
 	printf("bisect_rev=%s\n"
 	       "bisect_nr=%d\n"
 	       "bisect_good=%d\n"
@@ -278,6 +295,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	int bisect_list = 0;
 	int bisect_show_vars = 0;
 	int bisect_find_all = 0;
+	int bisect_show_all = 0;
 	int quiet = 0;
 
 	git_config(git_default_config, NULL);
@@ -305,6 +323,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 		if (!strcmp(arg, "--bisect-all")) {
 			bisect_list = 1;
 			bisect_find_all = 1;
+			bisect_show_all = 1;
 			revs.show_decorations = 1;
 			continue;
 		}
@@ -357,9 +376,10 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 
 		revs.commits = find_bisection(revs.commits, &reaches, &all,
 					      bisect_find_all);
+
 		if (bisect_show_vars)
 			return show_bisect_vars(&revs, reaches, all,
-						bisect_find_all);
+						bisect_show_all, 0);
 	}
 
 	traverse_commit_list(&revs,
-- 
1.6.2.1.317.g3d804

Re: [PATCH 07/10] rev-list: call new "filter_skip" function

[Junio C Hamano]

Christian Couder <chriscool@tuxfamily.org> writes:

> This patch implements a new "filter_skip" function in C in
> "bisect.c" that will later replace the existing implementation in
> shell in "git-bisect.sh".
>
> An array is used to store the skipped commits. But the array is
> not yet fed anything.
>
> Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
> ---
>  bisect.c           |   65 ++++++++++++++++++++++++++++++++++++++++++++++++++++
>  bisect.h           |    6 ++++-
>  builtin-rev-list.c |   30 ++++++++++++++++++++----
>  3 files changed, 95 insertions(+), 6 deletions(-)
>
> diff --git a/bisect.c b/bisect.c
> index 27def7d..39189f2 100644
> --- a/bisect.c
> +++ b/bisect.c
> @@ -4,6 +4,11 @@
>  #include "revision.h"
>  #include "bisect.h"
>  
> +
> +static unsigned char (*skipped_sha1)[20];
> +static int skipped_sha1_nr;
> +static int skipped_sha1_alloc;
> +
>  /* bits #0-15 in revision.h */
>  
>  #define COUNTED		(1u<<16)
> @@ -386,3 +391,63 @@ struct commit_list *find_bisection(struct commit_list *list,
>  	return best;
>  }
>  
> +static int skipcmp(const void *a, const void *b)
> +{
> +	return hashcmp(a, b);
> +}

I've learned to suspect without reading a qsort() callback that does not
derefence its arguments.  Is this doing the right thing?

> +
> +static void prepare_skipped(void)
> +{
> +	qsort(skipped_sha1, skipped_sha1_nr, sizeof(*skipped_sha1), skipcmp);
> +}
> +
> +static int lookup_skipped(unsigned char *sha1)
> +{
> +	int lo, hi;
> +	lo = 0;
> +	hi = skipped_sha1_nr;
> +	while (lo < hi) {
> +		int mi = (lo + hi) / 2;
> +		int cmp = hashcmp(sha1, skipped_sha1[mi]);
> +		if (!cmp)
> +			return mi;
> +		if (cmp < 0)
> +			hi = mi;
> +		else
> +			lo = mi + 1;
> +	}
> +	return -lo - 1;
> +}

Re: [PATCH 07/10] rev-list: call new "filter_skip" function

[Christian Couder]

Le jeudi 26 mars 2009, Junio C Hamano a écrit :
> Christian Couder <chriscool@tuxfamily.org> writes:
> > This patch implements a new "filter_skip" function in C in
> > "bisect.c" that will later replace the existing implementation in
> > shell in "git-bisect.sh".
> >
> > An array is used to store the skipped commits. But the array is
> > not yet fed anything.
> >
> > Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
> > ---
> >  bisect.c           |   65
> > ++++++++++++++++++++++++++++++++++++++++++++++++++++ bisect.h          
> > |    6 ++++-
> >  builtin-rev-list.c |   30 ++++++++++++++++++++----
> >  3 files changed, 95 insertions(+), 6 deletions(-)
> >
> > diff --git a/bisect.c b/bisect.c
> > index 27def7d..39189f2 100644
> > --- a/bisect.c
> > +++ b/bisect.c
> > @@ -4,6 +4,11 @@
> >  #include "revision.h"
> >  #include "bisect.h"
> >
> > +
> > +static unsigned char (*skipped_sha1)[20];
> > +static int skipped_sha1_nr;
> > +static int skipped_sha1_alloc;
> > +
> >  /* bits #0-15 in revision.h */
> >
> >  #define COUNTED		(1u<<16)
> > @@ -386,3 +391,63 @@ struct commit_list *find_bisection(struct
> > commit_list *list, return best;
> >  }
> >
> > +static int skipcmp(const void *a, const void *b)
> > +{
> > +	return hashcmp(a, b);
> > +}
>
> I've learned to suspect without reading a qsort() callback that does not
> derefence its arguments.  Is this doing the right thing?

I think so.

Here is a gdb session that seems to show that it's ok:

---------------------------------------------------
...
$ git bisect skip
There are only 'skip'ped commit left to test.
The first bad commit could be any of:
3de952f2416b6084f557ec417709eac740c6818c
7b7f204a749c3125d5224ed61ea2ae1187ad046f
32a594a3fdac2d57cf6d02987e30eec68511498c
We cannot bisect more!
$
$ gdb git
GNU gdb 6.6-debian
Copyright (C) 2006 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain 
conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu"...
Using host libthread_db library "/lib/libthread_db.so.1".
(gdb) b skipcmp
Breakpoint 1 at 0x46edfd: file bisect.c, line 457.
(gdb) run bisect--helper --next-vars
Starting program: /home/christian/git/bin/git bisect--helper --next-vars
[Thread debugging using libthread_db enabled]
[New Thread 47665987240336 (LWP 9703)]
[Switching to Thread 47665987240336 (LWP 9703)]

Breakpoint 1, skipcmp (a=0x77a800, b=0x77a814) at bisect.c:457
457             return hashcmp(a, b);
(gdb) p skipped_sha1
$1 = (unsigned char (*)[20]) 0x77a800
(gdb) p a - b
$2 = -20
(gdb) p sha1_to_hex(a)
$3 = 0x771256 "3de952f2416b6084f557ec417709eac740c6818c"
(gdb) p sha1_to_hex(b)
$4 = 0x7711c0 "7b7f204a749c3125d5224ed61ea2ae1187ad046f"
(gdb)    
---------------------------------------------------

Do you think I should add a comment and/or perhaps cast a and b into "const 
unsigned char *"?

Thanks,
Christian.

Re: [PATCH 07/10] rev-list: call new "filter_skip" function

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1955 bytes --]

Hi,

On Mon, 30 Mar 2009, Christian Couder wrote:

> Le jeudi 26 mars 2009, Junio C Hamano a écrit :
> > Christian Couder <chriscool@tuxfamily.org> writes:
> > > This patch implements a new "filter_skip" function in C in
> > > "bisect.c" that will later replace the existing implementation in
> > > shell in "git-bisect.sh".
> > >
> > > An array is used to store the skipped commits. But the array is
> > > not yet fed anything.
> > >
> > > Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
> > > ---
> > >  bisect.c           |   65
> > > ++++++++++++++++++++++++++++++++++++++++++++++++++++ bisect.h          
> > > |    6 ++++-
> > >  builtin-rev-list.c |   30 ++++++++++++++++++++----
> > >  3 files changed, 95 insertions(+), 6 deletions(-)
> > >
> > > diff --git a/bisect.c b/bisect.c
> > > index 27def7d..39189f2 100644
> > > --- a/bisect.c
> > > +++ b/bisect.c
> > > @@ -4,6 +4,11 @@
> > >  #include "revision.h"
> > >  #include "bisect.h"
> > >
> > > +
> > > +static unsigned char (*skipped_sha1)[20];
> > > +static int skipped_sha1_nr;
> > > +static int skipped_sha1_alloc;
> > > +
> > >  /* bits #0-15 in revision.h */
> > >
> > >  #define COUNTED		(1u<<16)
> > > @@ -386,3 +391,63 @@ struct commit_list *find_bisection(struct
> > > commit_list *list, return best;
> > >  }
> > >
> > > +static int skipcmp(const void *a, const void *b)
> > > +{
> > > +	return hashcmp(a, b);
> > > +}
> >
> > I've learned to suspect without reading a qsort() callback that does not
> > derefence its arguments.  Is this doing the right thing?
> 
> I think so.

I suspect something much worse: you are trying to build a list of sha1s of 
commits that need to be skipped, later to look up every commit via 
binary search.

But it has been proven a lot of times that using a hash set is superior to 
that approach, and even better: we already have the framework in place in 
the form of struct decorate.

Ciao,
Dscho "who is too busy to review patches ATM"

Re: [PATCH 07/10] rev-list: call new "filter_skip" function

[Christian Couder]

Hi,

Le lundi 30 mars 2009, Johannes Schindelin a écrit :
> Hi,
>
> On Mon, 30 Mar 2009, Christian Couder wrote:
> > Le jeudi 26 mars 2009, Junio C Hamano a écrit :
> > >
> > > I've learned to suspect without reading a qsort() callback that does
> > > not derefence its arguments.  Is this doing the right thing?
> >
> > I think so.
>
> I suspect something much worse: you are trying to build a list of sha1s
> of commits that need to be skipped, later to look up every commit via
> binary search.
>
> But it has been proven a lot of times that using a hash set is superior
> to that approach, and even better: we already have the framework in place
> in the form of struct decorate.

I had a look, and "struct decorate" can be used to store objects, but I want 
to store only sha1s.

Regards,
Christian.

Re: [PATCH 07/10] rev-list: call new "filter_skip" function

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1398 bytes --]

Hi,

On Tue, 31 Mar 2009, Christian Couder wrote:

> Le lundi 30 mars 2009, Johannes Schindelin a écrit :
>
> > On Mon, 30 Mar 2009, Christian Couder wrote:
> > > Le jeudi 26 mars 2009, Junio C Hamano a écrit :
> > > >
> > > > I've learned to suspect without reading a qsort() callback that 
> > > > does not derefence its arguments.  Is this doing the right thing?
> > >
> > > I think so.
> >
> > I suspect something much worse: you are trying to build a list of 
> > sha1s of commits that need to be skipped, later to look up every 
> > commit via binary search.
> >
> > But it has been proven a lot of times that using a hash set is 
> > superior to that approach, and even better: we already have the 
> > framework in place in the form of struct decorate.
> 
> I had a look, and "struct decorate" can be used to store objects, but I 
> want to store only sha1s.

No, you want to _look up_ sha1s.  And struct decorate is not about storing 
objects, but to attach things to objects.  From decorate.h:

	struct object_decoration {
	        const struct object *base;
	        void *decoration;
	};

So, if you just do

	struct decoration all_the_sha1s;

	...

		add_decoration(&all_the_sha1s, &commit->object, sha1);

you can look up the sha1 much more efficiently than with binary searches 
like this:

		unsigned char *sha1 = lookup_decoration(&all_the_sha1s,
			&commit->object);

Ciao,
Dscho

Re: [PATCH 07/10] rev-list: call new "filter_skip" function

[Christian Couder]

Le mardi 31 mars 2009, Johannes Schindelin a écrit :
> Hi,
>
> On Tue, 31 Mar 2009, Christian Couder wrote:
> > Le lundi 30 mars 2009, Johannes Schindelin a écrit :
> > > On Mon, 30 Mar 2009, Christian Couder wrote:
> > > > Le jeudi 26 mars 2009, Junio C Hamano a écrit :
> > > > > I've learned to suspect without reading a qsort() callback that
> > > > > does not derefence its arguments.  Is this doing the right thing?
> > > >
> > > > I think so.
> > >
> > > I suspect something much worse: you are trying to build a list of
> > > sha1s of commits that need to be skipped, later to look up every
> > > commit via binary search.
> > >
> > > But it has been proven a lot of times that using a hash set is
> > > superior to that approach, and even better: we already have the
> > > framework in place in the form of struct decorate.
> >
> > I had a look, and "struct decorate" can be used to store objects, but I
> > want to store only sha1s.
>
> No, you want to _look up_ sha1s.  And struct decorate is not about
> storing objects, but to attach things to objects. 

The problem is that I don't have any object to attach things to when I read 
the bisect skip refs. I just need to store the sha1 from the skip refs in 
some sha1 container.

Here is the related code:

static int register_ref(const char *refname, const unsigned char *sha1,
			int flags, void *cb_data)
{
	if (!strcmp(refname, "bad")) {
		...
	} else if (!prefixcmp(refname, "good-")) {
		...
	} else if (!prefixcmp(refname, "skip-")) {
		ALLOC_GROW(skipped_sha1, skipped_sha1_nr + 1,
			   skipped_sha1_alloc);
		hashcpy(skipped_sha1[skipped_sha1_nr++], sha1);
	}

	return 0;
}

static int read_bisect_refs(void)
{
	return for_each_bisect_ref(register_ref, NULL);
}

Best regards,
Christian.

Re: [PATCH 07/10] rev-list: call new "filter_skip" function

[Johannes Schindelin]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1751 bytes --]

Hi,

On Wed, 1 Apr 2009, Christian Couder wrote:

> Le mardi 31 mars 2009, Johannes Schindelin a écrit :
> > Hi,
> >
> > On Tue, 31 Mar 2009, Christian Couder wrote:
> > > Le lundi 30 mars 2009, Johannes Schindelin a écrit :
> > > > On Mon, 30 Mar 2009, Christian Couder wrote:
> > > > > Le jeudi 26 mars 2009, Junio C Hamano a écrit :
> > > > > > I've learned to suspect without reading a qsort() callback that
> > > > > > does not derefence its arguments.  Is this doing the right thing?
> > > > >
> > > > > I think so.
> > > >
> > > > I suspect something much worse: you are trying to build a list of
> > > > sha1s of commits that need to be skipped, later to look up every
> > > > commit via binary search.
> > > >
> > > > But it has been proven a lot of times that using a hash set is
> > > > superior to that approach, and even better: we already have the
> > > > framework in place in the form of struct decorate.
> > >
> > > I had a look, and "struct decorate" can be used to store objects, but I
> > > want to store only sha1s.
> >
> > No, you want to _look up_ sha1s.  And struct decorate is not about
> > storing objects, but to attach things to objects. 
> 
> The problem is that I don't have any object to attach things to when I 
> read the bisect skip refs. I just need to store the sha1 from the skip 
> refs in some sha1 container.

I see, so you do not want to parse the commits just to register them as 
skipped.

Fair enough.

But I still think that a hashmap/set would be better suited.

In any case, it should be refactored into something usable in all of 
libgit.a.  You are basically duplicating the grafts code in commit.c, 
sharing that shortcoming that your code would be static again, not 
encouraging reusage.

Ciao,
Dscho

Re: [PATCH 07/10] rev-list: call new "filter_skip" function

[Christian Couder]

Hi,

Le mercredi 1 avril 2009, Johannes Schindelin a écrit :
> Hi,
>
> On Wed, 1 Apr 2009, Christian Couder wrote:
> > Le mardi 31 mars 2009, Johannes Schindelin a écrit :
> > > Hi,
> > >
> > > On Tue, 31 Mar 2009, Christian Couder wrote:
> > > > Le lundi 30 mars 2009, Johannes Schindelin a écrit :
> > > No, you want to _look up_ sha1s.  And struct decorate is not about
> > > storing objects, but to attach things to objects.
> >
> > The problem is that I don't have any object to attach things to when I
> > read the bisect skip refs. I just need to store the sha1 from the skip
> > refs in some sha1 container.
>
> I see, so you do not want to parse the commits just to register them as
> skipped.
>
> Fair enough.
>
> But I still think that a hashmap/set would be better suited.
>
> In any case, it should be refactored into something usable in all of
> libgit.a.  You are basically duplicating the grafts code in commit.c,
> sharing that shortcoming that your code would be static again, not
> encouraging reusage.

I agree that binary search functions and related code should be refactored. 
That's why I added the "Refactor binary search functions" task to the 
Janitor wiki page (http://git.or.cz/gitwiki/Janitor) a few weeks ago.

I will have a look at that, and perhaps, after that, I will try to make 
things less static, but I think these are some old problems in the code 
base, so new developments should not be hostage of them.

Best reagrds,
Christian.