threads / rfc / 48582

RFC v4Implement --first-parent for git rev-list --bisect

Subject: [RFC PATCH v4] Implement --first-parent for git rev-list --bisect

## tl;dr

5 messages between May 28, 2018 and May 28, 2018. Diffs are folded; open one to read it.

replies: 4people: 2as markdown or json

Tiago Botelho· May 28, 2018, 09:20 UTC · lore

This will enable users to implement bisecting on first parents which can be useful for when the commits from a feature branch that we want to merge are not always tested.

Signed-off-by: Tiago Botelho <tiagonbotelho@hotmail.com>
---

This patch adds all Junio's suggestions, namely do_find_bisection() being broken when assigning q's weight to p if in first parent mode and q being not UNINTERESTING and its weight still not being known.

The graph displayed in the unit tests was also changed from being top-bottom to be left-right in order to keep it consistent with graphs in other tests.

 bisect.c                   | 45 ++++++++++++++++++++++++++++++---------------
 bisect.h                   |  3 ++-
 builtin/rev-list.c         |  3 +++
 revision.c                 |  3 ---
 t/t6002-rev-list-bisect.sh | 37 +++++++++++++++++++++++++++++++++++++
 5 files changed, 72 insertions(+), 19 deletions(-)
Show changes to 5 files +72 −19

bisect.c, bisect.h, builtin/rev-list.c, revision.c, t/t6002-rev-list-bisect.sh

diff --git a/bisect.c b/bisect.c
index 4eafc8262..e58cb8d62 100644
--- a/bisect.c
+++ b/bisect.c
@@ -33,6 +33,8 @@ static const char *term_good;
  *
  * We care just barely enough to avoid recursing for
  * non-merge entries.
+ *
+ * Note: This function does not support the usage --first-parent.
  */
 static int count_distance(struct commit_list *entry)
 {
@@ -82,15 +84,16 @@ static inline void weight_set(struct commit_list *elem, int weight)
 	*((int*)(elem->item->util)) = weight;
 }
 
-static int count_interesting_parents(struct commit *commit)
+static int count_interesting_parents(struct commit *commit, unsigned bisect_flags)
 {
 	struct commit_list *p;
 	int count;
 
 	for (count = 0, p = commit->parents; p; p = p->next) {
-		if (p->item->object.flags & UNINTERESTING)
-			continue;
-		count++;
+		if (!(p->item->object.flags & UNINTERESTING))
+		    count++;
+		if (bisect_flags & BISECT_FIRST_PARENT)
+			break;
 	}
 	return count;
 }
@@ -117,10 +120,10 @@ static inline int halfway(struct commit_list *p, int nr)
 }
 
 #if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
+#define show_list(a,b,c,d,e) do { ; } while (0)
 #else
 static void show_list(const char *debug, int counted, int nr,
-		      struct commit_list *list)
+		      struct commit_list *list, unsigned bisect_flags)
 {
 	struct commit_list *p;
 
@@ -146,10 +149,14 @@ static void show_list(const char *debug, int counted, int nr,
 		else
 			fprintf(stderr, "---");
 		fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
-		for (pp = commit->parents; pp; pp = pp->next)
+		for (pp = commit->parents; pp; pp = pp->next) {
 			fprintf(stderr, " %.*s", 8,
 				oid_to_hex(&pp->item->object.oid));
 
+			if (bisect_flags & BISECT_FIRST_PARENT)
+				break;
+		}
+
 		subject_len = find_commit_subject(buf, &subject_start);
 		if (subject_len)
 			fprintf(stderr, " %.*s", subject_len, subject_start);
@@ -267,13 +274,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		unsigned flags = commit->object.flags;
 
 		p->item->util = &weights[n++];
-		switch (count_interesting_parents(commit)) {
+		switch (count_interesting_parents(commit, bisect_flags)) {
 		case 0:
 			if (!(flags & TREESAME)) {
 				weight_set(p, 1);
 				counted++;
 				show_list("bisection 2 count one",
-					  counted, nr, list);
+					  counted, nr, list, bisect_flags);
 			}
 			/*
 			 * otherwise, it is known not to reach any
@@ -289,7 +296,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		}
 	}
 
-	show_list("bisection 2 initialize", counted, nr, list);
+	show_list("bisection 2 initialize", counted, nr, list, bisect_flags);
 
 	/*
 	 * If you have only one parent in the resulting set
@@ -319,7 +326,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		counted++;
 	}
 
-	show_list("bisection 2 count_distance", counted, nr, list);
+	show_list("bisection 2 count_distance", counted, nr, list, bisect_flags);
 
 	while (counted < nr) {
 		for (p = list; p; p = p->next) {
@@ -329,6 +336,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			if (0 <= weight(p))
 				continue;
 			for (q = p->item->parents; q; q = q->next) {
+				if ((bisect_flags & BISECT_FIRST_PARENT)) {
+					if (weight(q) < 0)
+						q = NULL;
+					break;
+				}
 				if (q->item->object.flags & UNINTERESTING)
 					continue;
 				if (0 <= weight(q))
@@ -346,7 +358,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 				weight_set(p, weight(q)+1);
 				counted++;
 				show_list("bisection 2 count one",
-					  counted, nr, list);
+					  counted, nr, list, bisect_flags);
 			}
 			else
 				weight_set(p, weight(q));
@@ -357,7 +369,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		}
 	}
 
-	show_list("bisection 2 counted all", counted, nr, list);
+	show_list("bisection 2 counted all", counted, nr, list, bisect_flags);
 
 	if (!find_all)
 		return best_bisection(list, nr);
@@ -372,7 +384,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	struct commit_list *list, *p, *best, *next, *last;
 	int *weights;
 
-	show_list("bisection 2 entry", 0, 0, *commit_list);
+	show_list("bisection 2 entry", 0, 0, *commit_list, bisect_flags);
 
 	/*
 	 * Count the number of total and tree-changing items on the
@@ -395,7 +407,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 		on_list++;
 	}
 	list = last;
-	show_list("bisection 2 sorted", 0, nr, list);
+	show_list("bisection 2 sorted", 0, nr, list, bisect_flags);
 
 	*all = nr;
 	weights = xcalloc(on_list, sizeof(*weights));
@@ -962,6 +974,9 @@ int bisect_next_all(const char *prefix, int no_checkout)
 	if (skipped_revs.nr)
 		bisect_flags |= BISECT_FIND_ALL;
 
+	if (revs.first_parent_only)
+		bisect_flags |= BISECT_FIRST_PARENT;
+
 	find_bisection(&revs.commits, &reaches, &all, bisect_flags);
 	revs.commits = managed_skipped(revs.commits, &tried);
 
diff --git a/bisect.h b/bisect.h
index 1d40a33ad..dfb7faeec 100644
--- a/bisect.h
+++ b/bisect.h
@@ -1,7 +1,8 @@
 #ifndef BISECT_H
 #define BISECT_H
 
-#define BISECT_FIND_ALL		(1u<<0)
+#define BISECT_FIND_ALL 	(1u<<0)
+#define BISECT_FIRST_PARENT 	(1u<<1)
 
 /*
  * Find bisection. If something is found, `reaches` will be the number of
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index 8752f5bbe..66439e1b3 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -538,6 +538,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (bisect_list) {
 		int reaches, all;
 
+		if (revs.first_parent_only)
+			bisect_flags |= BISECT_FIRST_PARENT;
+
 		find_bisection(&revs.commits, &reaches, &all, bisect_flags);
 
 		if (bisect_show_vars)
diff --git a/revision.c b/revision.c
index 4e0e193e5..b9d063805 100644
--- a/revision.c
+++ b/revision.c
@@ -2474,9 +2474,6 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 	if (!revs->reflog_info && revs->grep_filter.use_reflog_filter)
 		die("cannot use --grep-reflog without --walk-reflogs");
 
-	if (revs->first_parent_only && revs->bisect)
-		die(_("--first-parent is incompatible with --bisect"));
-
 	if (revs->expand_tabs_in_log < 0)
 		revs->expand_tabs_in_log = revs->expand_tabs_in_log_default;
 
diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
index a66140803..774d9a4fd 100755
--- a/t/t6002-rev-list-bisect.sh
+++ b/t/t6002-rev-list-bisect.sh
@@ -263,4 +263,41 @@ test_expect_success 'rev-parse --bisect can default to good/bad refs' '
 	test_cmp expect.sorted actual.sorted
 '
 
+# We generate the following commit graph:
+#
+#   B - C
+#  /      \
+# A        FX
+#  \      /
+#   D - EX
+
+test_expect_success 'setup' '
+  test_commit A &&
+  test_commit B &&
+  test_commit C &&
+  git reset --hard A &&
+  test_commit D &&
+  test_commit EX &&
+  test_merge FX C
+'
+
+test_output_expect_success "--bisect --first-parent" 'git rev-list --bisect --first-parent FX ^A' <<EOF
+$(git rev-parse EX)
+EOF
+
+test_output_expect_success "--bisect-vars --first-parent" 'git rev-list --bisect-vars --first-parent FX ^A' <<EOF
+bisect_rev='$(git rev-parse EX)'
+bisect_nr=1
+bisect_good=0
+bisect_bad=1
+bisect_all=3
+bisect_steps=1
+EOF
+
+test_output_expect_success "--bisect-all --first-parent" 'git rev-list --bisect-all --first-parent FX ^A' <<EOF
+$(git rev-parse EX) (dist=1)
+$(git rev-parse D) (dist=1)
+$(git rev-parse FX) (dist=0)
+EOF
+
 test_done

-- 
2.16.3
Junio C Hamano· May 28, 2018, 13:25 UTC · re: Tiago Botelho · lore

Re: [RFC PATCH v4] Implement --first-parent for git rev-list --bisect

Tiago Botelho <tiagonbotelho@gmail.com> writes:
Show 11 quoted lines
> diff --git a/bisect.c b/bisect.c
> index 4eafc8262..e58cb8d62 100644
> --- a/bisect.c
> +++ b/bisect.c
> @@ -33,6 +33,8 @@ static const char *term_good;
>   *
>   * We care just barely enough to avoid recursing for
>   * non-merge entries.
> + *
> + * Note: This function does not support the usage --first-parent.
>   */

Hmph, is this because we know --first-parent codepath currently does not call this function, so we do not bother to prepare this function to be called from --first-parent codepath?

I am not saying that we must prepare this function to be callable with --first-parent; if I have to wonder why the above comment is there and what it is trying to say, I suspect most other readers would, too, so...

Show 45 quoted lines
> diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
> index a66140803..774d9a4fd 100755
> --- a/t/t6002-rev-list-bisect.sh
> +++ b/t/t6002-rev-list-bisect.sh
> @@ -263,4 +263,41 @@ test_expect_success 'rev-parse --bisect can default to good/bad refs' '
>  	test_cmp expect.sorted actual.sorted
>  '
>  
> +# We generate the following commit graph:
> +#
> +#   B - C
> +#  /      \
> +# A        FX
> +#  \      /
> +#   D - EX
> +
> +test_expect_success 'setup' '
> +  test_commit A &&
> +  test_commit B &&
> +  test_commit C &&
> +  git reset --hard A &&
> +  test_commit D &&
> +  test_commit EX &&
> +  test_merge FX C
> +'
> +
> +test_output_expect_success "--bisect --first-parent" 'git rev-list --bisect --first-parent FX ^A' <<EOF
> +$(git rev-parse EX)
> +EOF
> +
> +test_output_expect_success "--bisect-vars --first-parent" 'git rev-list --bisect-vars --first-parent FX ^A' <<EOF
> +bisect_rev='$(git rev-parse EX)'
> +bisect_nr=1
> +bisect_good=0
> +bisect_bad=1
> +bisect_all=3
> +bisect_steps=1
> +EOF
> +
> +test_output_expect_success "--bisect-all --first-parent" 'git rev-list --bisect-all --first-parent FX ^A' <<EOF
> +$(git rev-parse EX) (dist=1)
> +$(git rev-parse D) (dist=1)
> +$(git rev-parse FX) (dist=0)
> +EOF
> +

These are all good basic tests, but can you come up with a test that demonstrates breakage in the previous round that has been fixed in this version of the patch?

Thanks.
Junio C Hamano· May 28, 2018, 14:25 UTC · re: Tiago Botelho · lore

Re: [RFC PATCH v4] Implement --first-parent for git rev-list --bisect

Tiago Botelho <tiagonbotelho@gmail.com> writes:
Show 20 quoted lines
> This will enable users to implement bisecting on first parents
> which can be useful for when the commits from a feature branch
> that we want to merge are not always tested.
>
> Signed-off-by: Tiago Botelho <tiagonbotelho@hotmail.com>
> ---
>
> This patch adds all Junio's suggestions, namely do_find_bisection() being
> broken when assigning q's weight to p if in first parent mode and q being
> not UNINTERESTING and its weight still not being known.
>
> The graph displayed in the unit tests was also changed from being top-bottom
> to be left-right in order to keep it consistent with graphs in other tests.
>
>  bisect.c                   | 45 ++++++++++++++++++++++++++++++---------------
>  bisect.h                   |  3 ++-
>  builtin/rev-list.c         |  3 +++
>  revision.c                 |  3 ---
>  t/t6002-rev-list-bisect.sh | 37 +++++++++++++++++++++++++++++++++++++
>  5 files changed, 72 insertions(+), 19 deletions(-)
Show 13 quoted lines
> diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
> index a66140803..774d9a4fd 100755
> --- a/t/t6002-rev-list-bisect.sh
> +++ b/t/t6002-rev-list-bisect.sh
> @@ -263,4 +263,41 @@ test_expect_success 'rev-parse --bisect can default to good/bad refs' '
> ...
> +test_output_expect_success "--bisect-all --first-parent" 'git rev-list --bisect-all --first-parent FX ^A' <<EOF
> +$(git rev-parse EX) (dist=1)
> +$(git rev-parse D) (dist=1)
> +$(git rev-parse FX) (dist=0)
> +EOF
> +
>  test_done

Running this test number of times gives me spurious errors. Is the order of these output lines unstable? How do we "sort" these bisect-all results? If we are not sorting and the output depends on happenstance, then probably we would need to compare the expected and actual output after sorting. Or if the output depends on something under our control (e.g. they are related to topology and relative commit timestamp), we probably should try to control that "something" tighter so that we can rely on the order of the lines in the "expect" file.

It also appears that we have "--bisect and --first-parent do not work well together" in t6000, which also needs to be updated. I needed the following squashed into this patch to make "make test" pass.

Show changes to t/t6000-rev-list-misc.sh +2 −2
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 969e4e9e52..981198ae6e 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -96,8 +96,8 @@ test_expect_success 'rev-list can show index objects' '
 	test_cmp expect actual
 '
 
-test_expect_success '--bisect and --first-parent can not be combined' '
-	test_must_fail git rev-list --bisect --first-parent HEAD
+test_expect_success '--bisect and --first-parent can now be combined' '
+	git rev-list --bisect --first-parent HEAD
 '
 
 test_expect_success '--header shows a NUL after each commit' '
Tiago Botelho· May 28, 2018, 16:49 UTC · re: Junio C Hamano · lore

Re: [RFC PATCH v4] Implement --first-parent for git rev-list --bisect

On 28 May 2018 at 15:25, Junio C Hamano <gitster@pobox.com> wrote:
> Tiago Botelho <tiagonbotelho@gmail.com> writes:
Show 8 quoted lines
> > This will enable users to implement bisecting on first parents
> > which can be useful for when the commits from a feature branch
> > that we want to merge are not always tested.
> >
> > Signed-off-by: Tiago Botelho <tiagonbotelho@hotmail.com>
> > ---
> >
> > This patch adds all Junio's suggestions, namely do_find_bisection()
being
> > broken when assigning q's weight to p if in first parent mode and q
being
> > not UNINTERESTING and its weight still not being known.
> >
> > The graph displayed in the unit tests was also changed from being
top-bottom
> > to be left-right in order to keep it consistent with graphs in other
tests.
> >
> >  bisect.c                   | 45
++++++++++++++++++++++++++++++---------------
Show 5 quoted lines
> >  bisect.h                   |  3 ++-
> >  builtin/rev-list.c         |  3 +++
> >  revision.c                 |  3 ---
> >  t/t6002-rev-list-bisect.sh | 37 +++++++++++++++++++++++++++++++++++++
> >  5 files changed, 72 insertions(+), 19 deletions(-)
Show 5 quoted lines
> > diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
> > index a66140803..774d9a4fd 100755
> > --- a/t/t6002-rev-list-bisect.sh
> > +++ b/t/t6002-rev-list-bisect.sh
> > @@ -263,4 +263,41 @@ test_expect_success 'rev-parse --bisect can
default to good/bad refs' '
> > ...
> > +test_output_expect_success "--bisect-all --first-parent" 'git rev-list
--bisect-all --first-parent FX ^A' <<EOF
Show 6 quoted lines
> > +$(git rev-parse EX) (dist=1)
> > +$(git rev-parse D) (dist=1)
> > +$(git rev-parse FX) (dist=0)
> > +EOF
> > +
> >  test_done
Show 9 quoted lines
> Running this test number of times gives me spurious errors.  Is the
> order of these output lines unstable?  How do we "sort" these
> bisect-all results?  If we are not sorting and the output depends on
> happenstance, then probably we would need to compare the expected
> and actual output after sorting.  Or if the output depends on
> something under our control (e.g. they are related to topology and
> relative commit timestamp), we probably should try to control that
> "something" tighter so that we can rely on the order of the lines in
> the "expect" file.

The reason why the tests were failing was because the above "old" tests did not make use of test_commit which in turn would make the sha of each commit be different and as a result give unexpected outputs at times. If I move them to the top of that file the tests will pass every time, would that be ok?

> It also appears that we have "--bisect and --first-parent do not
> work well together" in t6000, which also needs to be updated.  I
> needed the following squashed into this patch to make "make test"
> pass.
Show 7 quoted lines
> diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
> index 969e4e9e52..981198ae6e 100755
> --- a/t/t6000-rev-list-misc.sh
> +++ b/t/t6000-rev-list-misc.sh
> @@ -96,8 +96,8 @@ test_expect_success 'rev-list can show index objects' '
>          test_cmp expect actual
>   '
Show 5 quoted lines
> -test_expect_success '--bisect and --first-parent can not be combined' '
> -       test_must_fail git rev-list --bisect --first-parent HEAD
> +test_expect_success '--bisect and --first-parent can now be combined' '
> +       git rev-list --bisect --first-parent HEAD
>   '
>   test_expect_success '--header shows a NUL after each commit' '
Junio C Hamano· May 28, 2018, 21:51 UTC · re: Tiago Botelho · lore

Re: [RFC PATCH v4] Implement --first-parent for git rev-list --bisect

Tiago Botelho <tiagonbotelho@gmail.com> writes:
Show 16 quoted lines
>> Running this test number of times gives me spurious errors.  Is the
>> order of these output lines unstable?  How do we "sort" these
>> bisect-all results?  If we are not sorting and the output depends on
>> happenstance, then probably we would need to compare the expected
>> and actual output after sorting.  Or if the output depends on
>> something under our control (e.g. they are related to topology and
>> relative commit timestamp), we probably should try to control that
>> "something" tighter so that we can rely on the order of the lines in
>> the "expect" file.
>
> The reason why the tests were failing was because the above "old" tests
> did not make use of test_commit which in turn would make the sha of each
> commit be different and as a result give unexpected outputs at times.
> If I move them to the top of that file the tests will pass every time,
> would that
> be ok?

That means if somebody else needs to add other tests before the location you are planning to move your tests, your tests would suddenly start failing, no? That does not sound like a particularly robust solution to me.

← back to recent threads