Skip to contentSkip to conversation

Implement --first-parent for git rev-list --bisect

PATCH In review Tiago Botelho 5 participants 12 messages Aug 28, 2018 – Sep 4, 2018

lore
Share & tools
lore
#0 lore raw

PATCH v6 1/1 Implement --first-parent for git rev-list --bisect

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.

---

This patch refactors **only** the tests according to the suggestions made by Junio in v5 more specifically https://public-inbox.org/git/[email protected]/.

The discussion between Junio, Christian and Johannes got pretty confusing in the sense that I am unsure if this is the actual problem I am supposed to solve in order to get the patch accepted, if it is not I will keep iterating on it until it is good enough to be merged

 bisect.c                   | 43 ++++++++++++++++++++++------------
 bisect.h                   |  1 +
 builtin/rev-list.c         |  3 +++
 revision.c                 |  3 ---
 t/t6002-rev-list-bisect.sh | 58 ++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 90 insertions(+), 18 deletions(-)
bisect.c +28 -15
index 4eafc8262..cb80f29c5 100644
@@ -82,15 +82,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 +118,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 +147,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 +272,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 +294,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 +324,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 +334,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 +356,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 +367,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 +382,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 +405,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 +972,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);
 
bisect.h +1 -0
index 1d40a33ad..e445567c2 100644
@@ -2,6 +2,7 @@
 #define BISECT_H
 
 #define BISECT_FIND_ALL		(1u<<0)
+#define BISECT_FIRST_PARENT    	(1u<<1)
 
 /*
  * Find bisection. If something is found, `reaches` will be the number of
builtin/rev-list.c +3 -0
index 8752f5bbe..66439e1b3 100644
@@ -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)
revision.c +0 -3
index 4e0e193e5..b9d063805 100644
@@ -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;
 
t/t6002-rev-list-bisect.sh +58 -0

62 lines not on this page · raw message

Signature · 1 line
2.16.3
#1 lore raw

Hi Tiago,

Quoted 3 lines · Tiago Botelho

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.

This message is still lacking the explanation I asked for, namely for the lines:

	@@ -329,6 +334,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))
Quoted 10 lines

---

This patch refactors **only** the tests according to the suggestions made by Junio in v5 more specifically https://public-inbox.org/git/[email protected]/.

The discussion between Junio, Christian and Johannes got pretty confusing in the sense that I am unsure if this is the actual problem I am supposed to solve in order to get the patch accepted, if it is not I will keep iterating on it until it is good enough to be merged

I would have preferred to reuse the already existing commits generated in the setup phase rather than generating yet another batch, and to not introduce an inconsistent way to present a commit graph (compare your diagram with the one in
https://github.com/git/git/blob/v2.18.0/t/t6002-rev-list-bisect.sh#L64-L90
i.e. *in the same file*), and I mentioned this at least twice before, but maybe it got lost (and I could imagine that Christian's insistence on pushing the patch through with as little changes as he can get away with does not help), but at least now the added tests look slightly more understandable than before (despite funny indentation and too-long lines), so I'll stop imitating a broken record at this point.

Ciao,
Johannes

Quoted 265 lines
 bisect.c                   | 43 ++++++++++++++++++++++------------
 bisect.h                   |  1 +
 builtin/rev-list.c         |  3 +++
 revision.c                 |  3 ---
 t/t6002-rev-list-bisect.sh | 58 ++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 90 insertions(+), 18 deletions(-)
bisect.c +28 -15
index 4eafc8262..cb80f29c5 100644
@@ -82,15 +82,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 +118,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 +147,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 +272,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 +294,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 +324,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 +334,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 +356,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 +367,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 +382,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 +405,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 +972,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);
 
bisect.h +1 -0
index 1d40a33ad..e445567c2 100644
@@ -2,6 +2,7 @@
 #define BISECT_H
 
 #define BISECT_FIND_ALL		(1u<<0)
+#define BISECT_FIRST_PARENT    	(1u<<1)
 
 /*
  * Find bisection. If something is found, `reaches` will be the number of
builtin/rev-list.c +3 -0
index 8752f5bbe..66439e1b3 100644
@@ -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)
revision.c +0 -3
index 4e0e193e5..b9d063805 100644
@@ -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;
 
t/t6002-rev-list-bisect.sh +58 -0
index a66140803..1bc297de5 100755
@@ -263,4 +263,62 @@ 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 - CC - EX
+
+test_expect_success 'setup' '
+  test_commit A &&
+  test_commit B &&
+  test_commit C &&
+  git reset --hard A &&
+  test_commit D &&
+  test_commit CC &&
+  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 CC)
+EOF
+
+test_output_expect_success "--first-parent" 'git rev-list --first-parent FX ^A' <<EOF
+$(git rev-parse FX)
+$(git rev-parse EX)
+$(git rev-parse CC)
+$(git rev-parse D)
+EOF
+
+test_output_expect_success "--bisect-vars --first-parent" 'git rev-list --bisect-vars --first-parent FX ^A' <<EOF
+bisect_rev='$(git rev-parse CC)'
+bisect_nr=1
+bisect_good=1
+bisect_bad=1
+bisect_all=4
+bisect_steps=1
+EOF
+
+test_expect_success "--bisect-all --first-parent" '
+cat >expect <<EOF &&
+$(git rev-parse CC) (dist=2)
+$(git rev-parse EX) (dist=1)
+$(git rev-parse D) (dist=1)
+$(git rev-parse FX) (dist=0)
+EOF
+
+# Make sure we have the same entries, nothing more, nothing less
+git rev-list --bisect-all --first-parent FX ^A >actual &&
+  sort actual >actual.sorted &&
+  sort expect >expect.sorted &&
+  test_cmp expect.sorted actual.sorted &&
+  # Make sure the entries are sorted in the dist order
+  sed -e "s/.*(dist=\([1-9]*[0-9]\)).*/\1/" actual >actual.dists &&
+  sort -r actual.dists >actual.dists.sorted &&
+  test_cmp actual.dists.sorted actual.dists
+'
+
 test_done
Signature · 1 line
2.16.3
#2 lore raw
Quoted 11 lines · Johannes Schindelin

Hi Tiago,

Quoted 3 lines · Tiago Botelho

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.

This message is still lacking the explanation I asked for, namely for the lines:

Quoted 12 lines
	@@ -329,6 +334,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))

I've just finished scanning the discussion thread on public-inbox for v5, v4, v3, v2 and the initial round of this series, but found your comments only on the tests. If you have a pointer that would be great; it also is OK to say what kind of explanation is needed for that addition again.

FWIW I too was puzzled about the correctness of the added logic above, especially the part that reads weight(q) before checking if it is not UNINTERESTING, but I covered it on a separate message.

Quoted 6 lines

I would have preferred to reuse the already existing commits generated in the setup phase rather than generating yet another batch, and to not introduce an inconsistent way to present a commit graph (compare your diagram with the one in
https://github.com/git/git/blob/v2.18.0/t/t6002-rev-list-bisect.sh#L64-L90
i.e. *in the same file*)

As I already said in the previous round, I do agree with these. That is, ...

Quoted 18 lines
Quoted 18 lines
t/t6002-rev-list-bisect.sh +10 -0
index a66140803..1bc297de5 100755
@@ -263,4 +263,62 @@ 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 - CC - EX
+
+test_expect_success 'setup' '
+  test_commit A &&
Quoted 8 lines

t/t6002-rev-list-bisect.sh test_expect_success 'rev-parse --bisect can default to good/bad refs' ' · line 283

Quoted 8 lines
t/t6002-rev-list-bisect.sh +8 -0
+  test_commit B &&
+  test_commit C &&
+  git reset --hard A &&
+  test_commit D &&
+  test_commit CC &&
+  test_commit EX &&
+  test_merge FX C
+'

... the above graph construction should not be necessary. An earlier part of t6002 would have already created a history of suitable shape to use for writing the following tests.

Quoted 44 lines
Quoted 44 lines
t/t6002-rev-list-bisect.sh +39 -0
+test_output_expect_success "--bisect --first-parent" 'git rev-list --bisect --first-parent FX ^A' <<EOF
+$(git rev-parse CC)
+EOF
+
+test_output_expect_success "--first-parent" 'git rev-list --first-parent FX ^A' <<EOF
+$(git rev-parse FX)
+$(git rev-parse EX)
+$(git rev-parse CC)
+$(git rev-parse D)
+EOF
+
+test_output_expect_success "--bisect-vars --first-parent" 'git rev-list --bisect-vars --first-parent FX ^A' <<EOF
+bisect_rev='$(git rev-parse CC)'
+bisect_nr=1
+bisect_good=1
+bisect_bad=1
+bisect_all=4
+bisect_steps=1
+EOF
+
+test_expect_success "--bisect-all --first-parent" '
+cat >expect <<EOF &&
+$(git rev-parse CC) (dist=2)
+$(git rev-parse EX) (dist=1)
+$(git rev-parse D) (dist=1)
+$(git rev-parse FX) (dist=0)
+EOF
+
+# Make sure we have the same entries, nothing more, nothing less
+git rev-list --bisect-all --first-parent FX ^A >actual &&
+  sort actual >actual.sorted &&
+  sort expect >expect.sorted &&
+  test_cmp expect.sorted actual.sorted &&
+  # Make sure the entries are sorted in the dist order
+  sed -e "s/.*(dist=\([1-9]*[0-9]\)).*/\1/" actual >actual.dists &&
+  sort -r actual.dists >actual.dists.sorted &&
+  test_cmp actual.dists.sorted actual.dists
+'
+
 test_done
Signature · 1 line
2.16.3
#3 lore raw
Quoted 13 lines · Junio C Hamano
Quoted 6 lines · Johannes Schindelin

I would have preferred to reuse the already existing commits generated in the setup phase rather than generating yet another batch, and to not introduce an inconsistent way to present a commit graph (compare your diagram with the one in
https://github.com/git/git/blob/v2.18.0/t/t6002-rev-list-bisect.sh#L64-L90
i.e. *in the same file*)

As I already said in the previous round, I do agree with these. That is, ...

Quoted 1 line
Quoted 1 line
Quoted 6 lines
Quoted 3 lines

Review

Quoted 3 lines
(quoted diff) +3 -0
+# We generate the following commit graph:
+#
+#   B ------ C

... the above graph construction should not be necessary. An earlier part of t6002 would have already created a history of suitable shape to use for writing the following tests.

Something like the following, perhaps? I have a feeling that use of test-output-expect-success is trying to be too cute without making the result easier to read, and also makes it harder to debug the test script when it does not work as expected (e.g. you need to see where the output from the actual command is stored by going to the definition of the shell function), and would have preferred to see these three tests written without it (and instead using explicit 'expect' vs 'actual' comparison), but at least the patch below shows what I meant when I suggested updating the tests to reuse the existing history (I do not speak for Johannes, but I am guessing we are on the same page on this one).

Thanks.

 t/t6002-rev-list-bisect.sh | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 46 insertions(+)
t/t6002-rev-list-bisect.sh +46 -0
index a661408038..d27d0087d6 100755
@@ -263,4 +263,50 @@ test_expect_success 'rev-parse --bisect can default to good/bad refs' '
 	test_cmp expect.sorted actual.sorted
 '
 
+# See the drawing near the top --- e4 is in the middle of the first parent chain
+printf "%s\n" e4 |
+test_output_expect_success '--bisect --first-parent' '
+	git rev-list --bisect --first-parent E ^F
+'
+
+printf "%s\n" E e1 e2 e3 e4 e5 e6 e7 e8 |
+test_output_expect_success "--first-parent" '
+	git rev-list --first-parent E ^F
+'
+
+test_output_expect_success '--bisect-vars --first-parent' '
+	git rev-list --bisect-vars --first-parent E ^F
+' <<-EOF
+	bisect_rev='e5'
+	bisect_nr=4
+	bisect_good=4
+	bisect_bad=3
+	bisect_all=9
+	bisect_steps=2
+EOF
+
+test_expect_success '--bisect-all --first-parent' '
+	cat >expect <<-EOF &&
+	$(git rev-parse tags/e5) (dist=4)
+	$(git rev-parse tags/e4) (dist=4)
+	$(git rev-parse tags/e6) (dist=3)
+	$(git rev-parse tags/e3) (dist=3)
+	$(git rev-parse tags/e7) (dist=2)
+	$(git rev-parse tags/e2) (dist=2)
+	$(git rev-parse tags/e8) (dist=1)
+	$(git rev-parse tags/e1) (dist=1)
+	$(git rev-parse tags/E) (dist=0)
+	EOF
+
+	# Make sure we have the same entries, nothing more, nothing less
+	git rev-list --bisect-all --first-parent E ^F >actual &&
+	sort actual >actual.sorted &&
+	sort expect >expect.sorted &&
+	test_cmp expect.sorted actual.sorted &&
+	# Make sure the entries are sorted in the dist order
+	sed -e "s/.*(dist=\([1-9]*[0-9]\)).*/\1/" actual >actual.dists &&
+	sort -r -n actual.dists >actual.dists.sorted &&
+	test_cmp actual.dists.sorted actual.dists
+'
+
 test_done
#4 lore raw
Quoted 1 line · Junio C Hamano

Something like the following, perhaps?

Having said all that.

t/t6002-rev-list-bisect.sh test_expect_success 'rev-parse --bisect can default to good/bad refs' ' · line 275

Quoted 10 lines
t/t6002-rev-list-bisect.sh +10 -0
+# See the drawing near the top --- e4 is in the middle of the first parent chain
+printf "%s\n" e4 |
+test_output_expect_success '--bisect --first-parent' '
+	git rev-list --bisect --first-parent E ^F
+'
+
+printf "%s\n" E e1 e2 e3 e4 e5 e6 e7 e8 |
+test_output_expect_success "--first-parent" '
+	git rev-list --first-parent E ^F
+'

The above two are probably not controversial.

t/t6002-rev-list-bisect.sh test_expect_success 'rev-parse --bisect can default to good/bad refs' ' · line 286

Quoted 10 lines
t/t6002-rev-list-bisect.sh +10 -0
+test_output_expect_success '--bisect-vars --first-parent' '
+	git rev-list --bisect-vars --first-parent E ^F
+' <<-EOF
+	bisect_rev='e5'
+	bisect_nr=4
+	bisect_good=4
+	bisect_bad=3
+	bisect_all=9
+	bisect_steps=2
+EOF

Perhaps this one isn't either.

Quoted 8 lines
t/t6002-rev-list-bisect.sh +8 -0
+test_expect_success '--bisect-all --first-parent' '
+	cat >expect <<-EOF &&
+	$(git rev-parse tags/e5) (dist=4)
+	$(git rev-parse tags/e4) (dist=4)
+	$(git rev-parse tags/e6) (dist=3)
+	$(git rev-parse tags/e3) (dist=3)
+	$(git rev-parse tags/e7) (dist=2)
+	$(git rev-parse tags/e2) (dist=2)

t/t6002-rev-list-bisect.sh test_expect_success 'rev-parse --bisect can default to good/bad refs' ' · line 305

Quoted 10 lines
t/t6002-rev-list-bisect.sh +10 -0
+	$(git rev-parse tags/e8) (dist=1)
+	$(git rev-parse tags/e1) (dist=1)
+	$(git rev-parse tags/E) (dist=0)
+	EOF
+
+	# Make sure we have the same entries, nothing more, nothing less
+	git rev-list --bisect-all --first-parent E ^F >actual &&
+	sort actual >actual.sorted &&
+	sort expect >expect.sorted &&
+	test_cmp expect.sorted actual.sorted &&

By sorting both, we attempt allow them to come out in any random order when sorting done by --bisect-all gets tiebroken differently between commits with the same dist value. As Johannes said, this is a bit too strict to insist that E *must* get dist 0, when the only thing we may care about are e2 and e7 get the same dist value, which is larger than the dist value given to E, etc. If we wanted to ease the over-strictness, we could omit " (dist=N)" from the 'expect' file, and then

	sed -e 's/ (dist=[0-9]*)$//' actual | sort >actual.sorted &&
	sort expect >expect.sorted &&
	test_cmp expect.sorted actual.sorted &&

to compare only the object names.

This over-strictness would have caught a bug in Git if we reverted this new feature (i.e. "rev-list --first-parent --bisect-all" does not refuse to work---it just does not do what we expect), which gives distance of -1 in the output (!). From that point of view, I think it is also OK for the test to be spelling the values out like the above.

t/t6002-rev-list-bisect.sh test_expect_success 'rev-parse --bisect can default to good/bad refs' ' · line 308

Quoted 3 lines
t/t6002-rev-list-bisect.sh +3 -0
+	# Make sure the entries are sorted in the dist order
+	sed -e "s/.*(dist=\([0-9]*\)).*/\1/" actual >actual.dists &&
+	sort -r -n actual.dists >actual.dists.sorted &&

I forgot to mention but I added "-n" here to make sure we numerically sort the list of distance values. Also you had a bogus regexp to catch digits inherited from "something like this" I showed in an older discussion (I think it is sufficient to say [0-9]* here).

The above makes sure that commits that have larger distance number are listed earlier in the output, and we do not care if which one of e4 or e5, both of which have distant number 4, is shown first---we'd be happy as long as all the ones at distance 4 are shown before the others at smaller distance number. So with this in place, I think we can omit the exact distance number from the earlier part of this test, but as I said, it would have caught the bug that produces a negative distance value in the output, so I am still on the fence, leaning a bit toward being stricter than necessary.

Quoted 4 lines
t/t6002-rev-list-bisect.sh +3 -0
+	test_cmp actual.dists.sorted actual.dists
+'
+
 test_done
#5 lore raw
In reply to Tiago Botelho
Quoted 15 lines · Tiago Botelho
bisect.c +1 -1
index 4eafc8262..cb80f29c5 100644
@@ -82,15 +82,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) {

bisect.c static inline void weight_set(struct commit_list *elem, int weight) · line 97

Quoted 10 lines
bisect.c +4 -3
-		if (p->item->object.flags & UNINTERESTING)
-			continue;
-		count++;
+		if (!(p->item->object.flags & UNINTERESTING))
+		    count++;
+		if (bisect_flags & BISECT_FIRST_PARENT)
+			break;
 	}
 	return count;
 }

We either say 0 ("the first parent is uninteresting") or 1 ("it is") under BISECT_FIRST_PARENT mode. OK.

bisect.c static void show_list(const char *debug, int counted, int nr,

Quoted 14 lines
bisect.c +2 -2
@@ -117,10 +118,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 +147,14 @@ static void show_list(const char *debug, int counted, int nr,

An unrelated tangent, but I think I just spotted a bug in the existing code on the line immediately before this hunk, which reads

		if (commit->util)
			fprintf(stderr, "%3d", weight(p));

I think this was a bug introduced at bb408ac9 ("bisect.c: use commit-slab for commit weight instead of commit->util", 2018-05-19) where the internal implementation of weight() was changed not to touch commit->util but instead to use a separate commit-slab storage

Looking at the code before that conversion, it seems that we were using ->util to store a pointer to an integer, so we had the ability to differenciate non-negative weight (i.e. weight already computed for the commit), negative weight (i.e. not computed yet, but will be), and commits to which the concept of weight is not applicable. When we went to the commit-slab with the change, we lost the ability to represent the third case. I am offhand not sure what the best remedy would be. Perhaps stuff a so-far unused value like -3 to the weight() and use weight(p) == -3 instead of the old !commit->util or something like that?

(Duy CC'ed to help checking my sanity on this point).

In any case, this is an existing bug in a debug helper, and the focus of this patch is not about fixing that bug, so you can and should leave it as-is, until this patch successfully adds the "bisection following only the first parent" feature.

bisect.c static void show_list(const char *debug, int counted, int nr, · line 157

Quoted 12 lines
bisect.c +5 -1
 		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;
+		}
+

I am not sure if we want to do this. This is a debugging aid that allows us to peek into the internal state of the commit history graph being worked on; don't we rather want to make sure that tips of merged side branches are not participating (e.g. commit->util that records "weight" is used differently between the first and other parent commits)?

Quoted 9 lines
bisect.c +1 -1
 		subject_len = find_commit_subject(buf, &subject_start);
 		if (subject_len)
 			fprintf(stderr, " %.*s", subject_len, subject_start);
@@ -267,13 +272,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)) {

bisect.c static struct commit_list *do_find_bisection(struct commit_list *list, · line 284

Quoted 10 lines
bisect.c +1 -1
 		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

Because count_interesting_parents() returns either 0 or 1 under BISECT_FIRST_PARENT mode, we will never set -2 in this switch() statement. We either paint the bottom boundary with the correct weight, or -1 (i.e. "its weight is one plus its first parent's weight" marker). OK.

Quoted 10 lines
bisect.c +1 -1
@@ -289,7 +294,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

bisect.c static struct commit_list *do_find_bisection(struct commit_list *list, · line 327

Quoted 5 lines
bisect.c +1 -1
@@ -319,7 +324,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);

The loop before this part (not shown) is about counting weight for merges the hard way, which does not apply to us under the new BISECT_FIRST_PARENT mode. IOW, "initialize" and "count_distance" should show exactly the same output from show_list().

bisect.c static struct commit_list *do_find_bisection(struct commit_list *list, · line 335

Quoted 5 lines
bisect.c +0 -0
 	while (counted < nr) {
 		for (p = list; p; p = p->next) {
@@ -329,6 +334,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			if (0 <= weight(p))
 				continue;

If we know the weight of 'p' already, then we are already done with it. In the normal code, that means we are done with all the merges, so the loop immediately below deals only with a single strand of pearls. However, under BISECT_FIRST_PARENT mode, that is different. Let's see.

bisect.c static struct commit_list *do_find_bisection(struct commit_list *list, · line 341

Quoted 6 lines
bisect.c +5 -0
 			for (q = p->item->parents; q; q = q->next) {
+				if ((bisect_flags & BISECT_FIRST_PARENT)) {
+					if (weight(q) < 0)
+						q = NULL;
+					break;
+				}

Under first-parent mode, we uncondtionally break out of the loop after inspecting the first parent, even if it is a merge. The code after this loop (outside the context) says

			if (!q)
				continue;

which is to say "we are not ready to set the weight of p based on the weight of q, because the latter is unknown". So that is done by setting q to NULL, which makes sort of sense.

bisect.c static struct commit_list *do_find_bisection(struct commit_list *list, · line 344

Quoted 4 lines
bisect.c +0 -0
 				if (q->item->object.flags & UNINTERESTING)
 					continue;
...
 				if (0 <= weight(q))

Post context of this hunk is "break;", meaning that if we find an interesting parent

What the above original tells us is that when we are doing a full bisection, we do not look at weight of uninteresting parent and continue. In that case we know p is not a merge so we will exit this for() loop with q set to NULL.

Shouldn't we keep that property even under BISECT_FIRST_PARENT mode? What I am wondering is the block added to the top of this for() loop.

Shouldn't it be more like this?

                                if ((bisect_flags & BISECT_FIRST_PARENT)) {
					if ((q->item->object.flags & UNINTERESTING) ||
					    (weight(q) < 0))
						q = NULL;
					break;
				}

I do not even recall if weight(q) is defined for an uninteresting q offhand; your patch requires weight(q) is defined and is negative for such a 'q' to be correct. Code would be more trivially correct with an explicit check for UNINTERESTING, I would think.

In any case, after finding a parent (or not finding, signalled by being NULL) whose weight is either the same or one less than our weight, we leave the above for() loop and then ...

bisect.c static struct commit_list *do_find_bisection(struct commit_list *list, · line 362

Quoted 9 lines
bisect.c +1 -1
@@ -346,7 +356,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));

... we set our weight based on its weight. OK.

The remainder of the change looked OK (I didn't look at the the test).

Thanks.

#6 lore raw
Quoted 13 lines · Junio C Hamano

Review static void show_list(const char *debug, int counted, int nr,

Quoted 1 line
(quoted diff) +0 -0
@@ -146,10 +147,14 @@ static void show_list(const char *debug, int counted, int nr,

An unrelated tangent, but I think I just spotted a bug in the existing code on the line immediately before this hunk, which reads

                if (commit->util)
                        fprintf(stderr, "%3d", weight(p));

I think this was a bug introduced at bb408ac9 ("bisect.c: use commit-slab for commit weight instead of commit->util", 2018-05-19) where the internal implementation of weight() was changed not to touch commit->util but instead to use a separate commit-slab storage

Quoted 10 lines

Looking at the code before that conversion, it seems that we were using ->util to store a pointer to an integer, so we had the ability to differenciate non-negative weight (i.e. weight already computed for the commit), negative weight (i.e. not computed yet, but will be), and commits to which the concept of weight is not applicable. When we went to the commit-slab with the change, we lost the ability to represent the third case. I am offhand not sure what the best remedy would be. Perhaps stuff a so-far unused value like -3 to the weight() and use weight(p) == -3 instead of the old !commit->util or something like that?

Hmm.. no? the commit-slab stores the pointer to the weight, not the weight itself, so we still have the ability to check the third case, I think.

Quoted 6 lines

(Duy CC'ed to help checking my sanity on this point).

In any case, this is an existing bug in a debug helper, and the focus of this patch is not about fixing that bug, so you can and should leave it as-is, until this patch successfully adds the "bisection following only the first parent" feature.

Yes. I'll post a patch soon to fix this "commit->util" leftover.

Signature · 1 line
Duy
#7 lore raw

PATCH 1/1 bisect.c: make show_list() build again

This function only compiles when DEBUG_BISECT is 1, which is often not the case. As a result there are two commits [1] [2] that break it but the breakages went unnoticed because the code did not compile by default. Update the function and include the new header file to make this function build again.

In order to stop this from happening again, the function is now compiled unconditionally but exits early unless DEBUG_BISECT is non-zero. A smart compiler generates no extra code (not even a function call). But even if it does not, this function does not seem to be in a hot path that the extra cost becomes a big problem.

[1] bb408ac95d (bisect.c: use commit-slab for commit weight instead of

    commit->util - 2018-05-19)

[2] cbd53a2193 (object-store: move object access functions to

    object-store.h - 2018-05-15)
---
 bisect.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)
bisect.c +5 -5
index e1275ba79e..e65f6821b8 100644
@@ -13,6 +13,7 @@
 #include "sha1-array.h"
 #include "argv-array.h"
 #include "commit-slab.h"
+#include "object-store.h"
 
 static struct oid_array good_revs;
 static struct oid_array skipped_revs;
@@ -120,14 +121,14 @@ static inline int halfway(struct commit_list *p, int nr)
 	}
 }
 
-#if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
-#else
 static void show_list(const char *debug, int counted, int nr,
 		      struct commit_list *list)
 {
 	struct commit_list *p;
 
+	if (!DEBUG_BISECT)
+		return;
+
 	fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
 
 	for (p = list; p; p = p->next) {
@@ -145,7 +146,7 @@ static void show_list(const char *debug, int counted, int nr,
 			(flags & TREESAME) ? ' ' : 'T',
 			(flags & UNINTERESTING) ? 'U' : ' ',
 			(flags & COUNTED) ? 'C' : ' ');
-		if (commit->util)
+		if (*commit_weight_at(&commit_weight, p->item))
 			fprintf(stderr, "%3d", weight(p));
 		else
 			fprintf(stderr, "---");
@@ -160,7 +161,6 @@ static void show_list(const char *debug, int counted, int nr,
 		fprintf(stderr, "\n");
 	}
 }
-#endif /* DEBUG_BISECT */
 
 static struct commit_list *best_bisection(struct commit_list *list, int nr)
 {
Signature · 1 line
2.19.0.rc0.337.ge906d732e7
#8 lore raw

Re: [PATCH] bisect.c: make show_list() build again

Quoted 3 lines · Nguyễn Thái Ngọc Duy

In order to stop this from happening again, the function is now compiled unconditionally but exits early unless DEBUG_BISECT is non-zero.

Thanks for going the extra mile and doing this!

I wonder if we should also try to make the show_list() function part of the trace_*() functions to make it even more regular. This can be a separate patch or topic though.

#9 lore raw

Re: [PATCH] bisect.c: make show_list() build again

Quoted 7 lines · Christian Couder
Quoted 3 lines · Nguyễn Thái Ngọc Duy

In order to stop this from happening again, the function is now compiled unconditionally but exits early unless DEBUG_BISECT is non-zero.

Quoted 5 lines

Thanks for going the extra mile and doing this!

I wonder if we should also try to make the show_list() function part of the trace_*() functions to make it even more regular. This can be a separate patch or topic though.

Yeah that's probably a good idea (though I'm not familiar with bisect.c enough to take that step).

Signature · 1 line
Duy
#10 lore raw

Re: [PATCH] bisect.c: make show_list() build again

Quoted 11 lines · Duy Nguyen
Quoted 6 lines · Christian Couder

Thanks for going the extra mile and doing this!

I wonder if we should also try to make the show_list() function part of the trace_*() functions to make it even more regular. This can be a separate patch or topic though.

Yeah that's probably a good idea (though I'm not familiar with bisect.c enough to take that step).

Maybe this could be a GSoC micro project or a left over bit.

#11 lore raw
In reply to Duy Nguyen
Quoted 3 lines · Duy Nguyen

Hmm.. no? the commit-slab stores the pointer to the weight, not the weight itself, so we still have the ability to check the third case, I think.

Good, thanks.