[PATCH v7 1/1] Implement rev-list --bisect* --first-parent

[workingjubilee@gmail.com]

From: Jubilee Young <workingjubilee@gmail.com>

Not all repository maintainers expect every commit to pass tests, only
testing the merge commits. Currently bisection assumes every commit is
of interest. The highly-requested --bisect --first-parent feature imbues
git with the same indifference to minutiae when the option is set, so
that it casually riffles through commits, throwing aside mountains of
irrelevant data when looking for a breaking change. Further refinement
of where breaks occurred can be gained by bisecting over the merge's
range.

Note, bisecting on --first-parent becomes part of findall's previously
existing pass-through as an "option state" flag.

In order to limit possible obfuscation of bisect operations resulting
from the addition of new flags, some extra documentation was folded in
to the patch.

Signed-off-by: Jubilee Young <workingjubilee@gmail.com>
Based-on-patch-by: Tiago Botelho <tiagonbotelho@hotmail.com>
Based-on-patch-by: Harald Nordgren <haraldnordgren@gmail.com>
---
 bisect.c                   | 56 ++++++++++++++++++++++++++------------
 bisect.h                   | 17 ++++++++++--
 builtin/rev-list.c         |  9 ++++--
 revision.c                 |  3 --
 t/t6000-rev-list-misc.sh   |  4 +--
 t/t6002-rev-list-bisect.sh | 54 ++++++++++++++++++++++++++++++++++++
 6 files changed, 116 insertions(+), 27 deletions(-)

diff --git a/bisect.c b/bisect.c
index e81c91d02c..54129a796b 100644
--- a/bisect.c
+++ b/bisect.c
@@ -88,15 +88,16 @@ static inline void weight_set(struct commit_list *elem, int weight)
 	**commit_weight_at(&commit_weight, elem->item) = 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;
 }
@@ -123,7 +124,7 @@ static inline int halfway(struct commit_list *p, int nr)
 }
 
 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;
 
@@ -259,10 +260,12 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
  */
 static struct commit_list *do_find_bisection(struct commit_list *list,
 					     int nr, int *weights,
-					     int find_all)
+					     unsigned bisect_flags)
 {
 	int n, counted;
 	struct commit_list *p;
+	unsigned first_parent = bisect_flags & BISECT_FIRST_PARENT;
+	unsigned find_all = bisect_flags & BISECT_FIND_ALL;
 
 	counted = 0;
 
@@ -271,13 +274,13 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		unsigned flags = commit->object.flags;
 
 		*commit_weight_at(&commit_weight, p->item) = &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
@@ -293,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
@@ -323,7 +326,8 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		counted++;
 	}
 
-	show_list("bisection 2 count_distance", counted, nr, list);
+	/* should match bisection 2 initialize when BISECT_FIRST_PARENT */
+	show_list("bisection 2 count_distance", counted, nr, list, bisect_flags);
 
 	while (counted < nr) {
 		for (p = list; p; p = p->next) {
@@ -333,6 +337,17 @@ 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) {
+				/*
+				 * first_parent can skip parent nodes, but only when
+				 * confirmed as being of no interest.
+				 */
+				if (first_parent) {
+					if ((q->item->object.flags & UNINTERESTING) ||
+						(weight(q) < 0)) {
+						q = NULL;
+					}
+					break;
+				}
 				if (q->item->object.flags & UNINTERESTING)
 					continue;
 				if (0 <= weight(q))
@@ -350,7 +365,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));
@@ -361,7 +376,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);
@@ -370,13 +385,14 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 }
 
 void find_bisection(struct commit_list **commit_list, int *reaches,
-		    int *all, int find_all)
+		    int *all, unsigned bisect_flags)
 {
 	int nr, on_list;
 	struct commit_list *list, *p, *best, *next, *last;
 	int *weights;
+	unsigned find_all = bisect_flags & BISECT_FIND_ALL;
 
-	show_list("bisection 2 entry", 0, 0, *commit_list);
+	show_list("bisection 2 entry", 0, 0, *commit_list, bisect_flags);
 	init_commit_weight(&commit_weight);
 
 	/*
@@ -400,13 +416,13 @@ 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));
 
 	/* Do the real work of finding bisection commit. */
-	best = do_find_bisection(list, nr, weights, find_all);
+	best = do_find_bisection(list, nr, weights, bisect_flags);
 	if (best) {
 		if (!find_all) {
 			list->item = best->item;
@@ -950,6 +966,7 @@ int bisect_next_all(struct repository *r, const char *prefix, int no_checkout)
 	struct rev_info revs;
 	struct commit_list *tried;
 	int reaches = 0, all = 0, nr, steps;
+	unsigned bisect_flags = 0;
 	struct object_id *bisect_rev;
 	char *steps_msg;
 
@@ -964,7 +981,12 @@ int bisect_next_all(struct repository *r, const char *prefix, int no_checkout)
 
 	bisect_common(&revs);
 
-	find_bisection(&revs.commits, &reaches, &all, !!skipped_revs.nr);
+	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);
 
 	if (!revs.commits) {
diff --git a/bisect.h b/bisect.h
index 4e69a11ea8..518be01999 100644
--- a/bisect.h
+++ b/bisect.h
@@ -3,16 +3,18 @@
 
 struct commit_list;
 struct repository;
+#define BISECT_FIND_ALL	(1U<<0)
+#define BISECT_FIRST_PARENT	(1U<<1)
 
 /*
  * Find bisection. If something is found, `reaches` will be the number of
  * commits that the best commit reaches. `all` will be the count of
  * non-SAMETREE commits. If nothing is found, `list` will be NULL.
  * Otherwise, it will be either all non-SAMETREE commits or the single
- * best commit, as chosen by `find_all`.
+ * best commit, as chosen by the flag `BISECT_FIND_ALL`.
  */
 void find_bisection(struct commit_list **list, int *reaches, int *all,
-		    int find_all);
+		    unsigned bisect_flags);
 
 struct commit_list *filter_skipped(struct commit_list *list,
 				   struct commit_list **tried,
@@ -31,6 +33,17 @@ struct rev_list_info {
 	const char *header_prefix;
 };
 
+/*
+ * Coordinates a bisection by examining input made available so far,
+ * setting up internal variables, and then bisecting with them.
+ * no_checkout directs this to only update BISECT_HEAD refs.
+ *
+ * Exit code 10 on successful bisection, so caller should exit with 0.
+ * Exit code 4 when no commits were found to bisect through.
+ * Exit code 1 MAY result from skipping the commit it would report.
+ *
+ * Otherwise, returns a call to command handlers which choose an exit.
+ */
 int bisect_next_all(struct repository *r,
 		    const char *prefix,
 		    int no_checkout);
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index e28d62ec64..759a182ec6 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -374,8 +374,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	int i;
 	int bisect_list = 0;
 	int bisect_show_vars = 0;
-	int bisect_find_all = 0;
 	int use_bitmap_index = 0;
+	unsigned bisect_flags = 0;
 	const char *show_progress = NULL;
 
 	if (argc == 2 && !strcmp(argv[1], "-h"))
@@ -443,7 +443,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_flags |= BISECT_FIND_ALL;
 			info.flags |= BISECT_SHOW_ALL;
 			revs.show_decorations = 1;
 			continue;
@@ -565,7 +565,10 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (bisect_list) {
 		int reaches, all;
 
-		find_bisection(&revs.commits, &reaches, &all, bisect_find_all);
+		if (revs.first_parent_only)
+			bisect_flags |= BISECT_FIRST_PARENT;
+
+		find_bisection(&revs.commits, &reaches, &all, bisect_flags);
 
 		if (bisect_show_vars)
 			return show_bisect_vars(&info, reaches, all);
diff --git a/revision.c b/revision.c
index 0e39b2b8a5..c6f0a9f213 100644
--- a/revision.c
+++ b/revision.c
@@ -2716,9 +2716,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->line_level_traverse &&
 	    (revs->diffopt.output_format & ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT)))
 		die(_("-L does not yet support diff formats besides -p and -s"));
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index b8cf82349b..95949e4ff1 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -122,8 +122,8 @@ test_expect_success 'rev-list can negate 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 be combined' '
+	git rev-list --bisect --first-parent HEAD
 '
 
 test_expect_success '--header shows a NUL after each commit' '
diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
index a661408038..6caf2af650 100755
--- a/t/t6002-rev-list-bisect.sh
+++ b/t/t6002-rev-list-bisect.sh
@@ -263,4 +263,58 @@ test_expect_success 'rev-parse --bisect can default to good/bad refs' '
 	test_cmp expect.sorted actual.sorted
 '
 
+# --first-parent tests
+
+# --bisect --first-parent should pluck out the middle.
+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 returns correct order' '
+	git rev-list --bisect-all --first-parent E ^F >actual &&
+
+	# 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 &&
+	test_cmp actual.dists.sorted actual.dists
+'
+
+# NEEDSWORK: this test could afford being hardened against other
+# changes in the same file.
+test_expect_success '--bisect-all --first-parent compares correctly' '
+	cat >expect <<-EOF &&
+	$(git rev-parse tags/e5) (tag: e5, dist=4)
+	$(git rev-parse tags/e4) (tag: e4, dist=4)
+	$(git rev-parse tags/e6) (tag: e6, dist=3)
+	$(git rev-parse tags/e3) (tag: e3, dist=3)
+	$(git rev-parse tags/e7) (tag: e7, dist=2)
+	$(git rev-parse tags/e2) (tag: e2, dist=2)
+	$(git rev-parse tags/e8) (tag: e8, dist=1)
+	$(git rev-parse tags/e1) (tag: e1, dist=1)
+	$(git rev-parse tags/E) (tag: E, dist=0)
+EOF
+
+git rev-list --bisect-all --first-parent E ^F >actual &&
+	sort actual >actual.sorted &&
+	sort expect >expect.sorted &&
+	test_cmp expect.sorted actual.sorted
+'
+
 test_done
-- 
2.24.0.1.gdc0fb1c0fe