Git Mailing List Archive on lore.kernel.org
 help / color / Atom feed
From: Aaron Lipman <alipman88@gmail.com>
To: git@vger.kernel.org
Cc: Aaron Lipman <alipman88@gmail.com>
Subject: [PATCH v3 1/4] rev-list: allow bisect and first-parent flags
Date: Sat,  1 Aug 2020 13:58:37 -0400
Message-ID: <20200801175840.1877-2-alipman88@gmail.com> (raw)
In-Reply-To: <20200801175840.1877-1-alipman88@gmail.com>

Add first_parent_only parameter to find_bisection(), removing the
barrier that prevented combining the --bisect and --first-parent flags
when using git rev-list

Based-on-patch-by: Tiago Botelho <tiagonbotelho@hotmail.com>
Signed-off-by: Aaron Lipman <alipman88@gmail.com>
---
 Documentation/rev-list-options.txt |  7 ++---
 bisect.c                           | 28 ++++++++++++-------
 bisect.h                           |  2 +-
 builtin/rev-list.c                 |  2 +-
 revision.c                         |  3 --
 t/t6000-rev-list-misc.sh           |  4 +--
 t/t6002-rev-list-bisect.sh         | 45 ++++++++++++++++++++++++++++++
 7 files changed, 70 insertions(+), 21 deletions(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index b01b2b6773..d3117ce51b 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -128,8 +128,7 @@ parents) and `--max-parents=-1` (negative numbers denote no upper limit).
 	because merges into a topic branch tend to be only about
 	adjusting to updated upstream from time to time, and
 	this option allows you to ignore the individual commits
-	brought in to your history by such a merge. Cannot be
-	combined with --bisect.
+	brought in to your history by such a merge.
 
 --not::
 	Reverses the meaning of the '{caret}' prefix (or lack thereof)
@@ -207,7 +206,7 @@ ifndef::git-rev-list[]
 	Pretend as if the bad bisection ref `refs/bisect/bad`
 	was listed and as if it was followed by `--not` and the good
 	bisection refs `refs/bisect/good-*` on the command
-	line. Cannot be combined with --first-parent.
+	line.
 endif::git-rev-list[]
 
 --stdin::
@@ -743,7 +742,7 @@ outputs 'midpoint', the output of the two commands
 would be of roughly the same length.  Finding the change which
 introduces a regression is thus reduced to a binary search: repeatedly
 generate and test new 'midpoint's until the commit chain is of length
-one. Cannot be combined with --first-parent.
+one.
 
 --bisect-vars::
 	This calculates the same as `--bisect`, except that refs in
diff --git a/bisect.c b/bisect.c
index d5e830410f..a11fdb1473 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, int first_parent_only)
 {
 	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 (first_parent_only)
+			break;
 	}
 	return count;
 }
@@ -259,7 +260,7 @@ 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)
+					     int find_all, int first_parent_only)
 {
 	int n, counted;
 	struct commit_list *p;
@@ -271,7 +272,7 @@ 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, first_parent_only)) {
 		case 0:
 			if (!(flags & TREESAME)) {
 				weight_set(p, 1);
@@ -314,6 +315,8 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			continue;
 		if (weight(p) != -2)
 			continue;
+		if (first_parent_only)
+			BUG("shouldn't be calling count-distance in fp mode");
 		weight_set(p, count_distance(p));
 		clear_distance(list);
 
@@ -332,7 +335,10 @@ 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) {
+
+			for (q = p->item->parents;
+			     q;
+			     q = first_parent_only ? NULL : q->next) {
 				if (q->item->object.flags & UNINTERESTING)
 					continue;
 				if (0 <= weight(q))
@@ -370,7 +376,7 @@ 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, int find_all, int first_parent_only)
 {
 	int nr, on_list;
 	struct commit_list *list, *p, *best, *next, *last;
@@ -406,7 +412,7 @@ void find_bisection(struct commit_list **commit_list, int *reaches,
 	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, find_all, first_parent_only);
 	if (best) {
 		if (!find_all) {
 			list->item = best->item;
@@ -991,6 +997,7 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix, int
 	enum bisect_error res = BISECT_OK;
 	struct object_id *bisect_rev;
 	char *steps_msg;
+	int first_parent_only = 0; /* TODO: pass --first-parent flag from git bisect start */
 
 	read_bisect_terms(&term_bad, &term_good);
 	if (read_bisect_refs())
@@ -1001,11 +1008,12 @@ enum bisect_error bisect_next_all(struct repository *r, const char *prefix, int
 		return res;
 
 	bisect_rev_setup(r, &revs, prefix, "%s", "^%s", 1);
+	revs.first_parent_only = first_parent_only;
 	revs.limited = 1;
 
 	bisect_common(&revs);
 
-	find_bisection(&revs.commits, &reaches, &all, !!skipped_revs.nr);
+	find_bisection(&revs.commits, &reaches, &all, !!skipped_revs.nr, first_parent_only);
 	revs.commits = managed_skipped(revs.commits, &tried);
 
 	if (!revs.commits) {
diff --git a/bisect.h b/bisect.h
index 8bad8d8391..a63af0505f 100644
--- a/bisect.h
+++ b/bisect.h
@@ -12,7 +12,7 @@ struct repository;
  * best commit, as chosen by `find_all`.
  */
 void find_bisection(struct commit_list **list, int *reaches, int *all,
-		    int find_all);
+		    int find_all, int first_parent_only);
 
 struct commit_list *filter_skipped(struct commit_list *list,
 				   struct commit_list **tried,
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index f520111eda..d1a14596b2 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -638,7 +638,7 @@ 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);
+		find_bisection(&revs.commits, &reaches, &all, bisect_find_all, revs.first_parent_only);
 
 		if (bisect_show_vars)
 			return show_bisect_vars(&info, reaches, all);
diff --git a/revision.c b/revision.c
index 6aa7f4f567..f0ad2603c1 100644
--- a/revision.c
+++ b/revision.c
@@ -2869,9 +2869,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 3dc1ad8f71..26e3533562 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -125,8 +125,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..7fc0f75ca5 100755
--- a/t/t6002-rev-list-bisect.sh
+++ b/t/t6002-rev-list-bisect.sh
@@ -263,4 +263,49 @@ test_expect_success 'rev-parse --bisect can default to good/bad refs' '
 	test_cmp expect.sorted actual.sorted
 '
 
+test_output_expect_success "--bisect --first-parent" 'git rev-list --bisect --first-parent E ^F' <<EOF
+e4
+EOF
+
+test_output_expect_success "--first-parent" 'git rev-list --first-parent E ^F' <<EOF
+E
+e1
+e2
+e3
+e4
+e5
+e6
+e7
+e8
+EOF
+
+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.unsorted <<EOF &&
+$(git rev-parse E) (tag: E, dist=0)
+$(git rev-parse e1) (tag: e1, dist=1)
+$(git rev-parse e2) (tag: e2, dist=2)
+$(git rev-parse e3) (tag: e3, dist=3)
+$(git rev-parse e4) (tag: e4, dist=4)
+$(git rev-parse e5) (tag: e5, dist=4)
+$(git rev-parse e6) (tag: e6, dist=3)
+$(git rev-parse e7) (tag: e7, dist=2)
+$(git rev-parse e8) (tag: e8, dist=1)
+EOF
+
+# expect results to be ordered by distance (descending),
+# commit hash (ascending)
+sort -k4,4r -k1,1 expect.unsorted > expect &&
+git rev-list --bisect-all --first-parent E ^F > actual &&
+test_cmp actual expect
+'
+
 test_done
-- 
2.24.3 (Apple Git-128)


  reply index

Thread overview: 42+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-07-28 15:44 [PATCH 0/3] Introduce --first-parent flag for git bisect Aaron Lipman via GitGitGadget
2020-07-28 15:44 ` [PATCH 1/3] rev-list: allow bisect and first-parent flags Aaron Lipman via GitGitGadget
2020-07-28 20:23   ` Junio C Hamano
2020-07-28 21:53     ` Junio C Hamano
2020-07-28 15:44 ` [PATCH 2/3] bisect: introduce first-parent flag Aaron Lipman via GitGitGadget
2020-07-28 15:44 ` [PATCH 3/3] bisect: combine args passed to find_bisection() Aaron Lipman via GitGitGadget
2020-07-30  0:27 ` [PATCH v2 0/3] Introduce --first-parent flag for git bisect Aaron Lipman
2020-07-30  0:27   ` [PATCH v2 1/3] rev-list: allow bisect and first-parent flags Aaron Lipman
2020-07-30  0:27   ` [PATCH v2 2/3] bisect: introduce first-parent flag Aaron Lipman
2020-07-30  4:17     ` Junio C Hamano
2020-07-30  0:27   ` [PATCH v2 3/3] bisect: combine args passed to find_bisection() Aaron Lipman
2020-07-30  4:32     ` Junio C Hamano
2020-07-30  0:48   ` [PATCH v2 0/3] Introduce --first-parent flag for git bisect Junio C Hamano
2020-08-01 17:58   ` [PATCH v3 0/4] " Aaron Lipman
2020-08-01 17:58     ` Aaron Lipman [this message]
2020-08-01 17:58     ` [PATCH v3 2/4] bisect: introduce first-parent flag Aaron Lipman
2020-08-01 17:58     ` [PATCH v3 3/4] bisect: combine args passed to find_bisection() Aaron Lipman
2020-08-01 19:30       ` Martin Ågren
2020-08-01 17:58     ` [PATCH v3 4/4] bisect: consistent style for git bisect run tests Aaron Lipman
2020-08-01 19:27       ` Martin Ågren
2020-08-01 19:06     ` [PATCH v3 0/4] Introduce --first-parent flag for git bisect Junio C Hamano
2020-08-04 22:01     ` [PATCH v4 0/5] " Aaron Lipman
2020-08-04 22:01       ` [PATCH v4 1/5] t6030: modernize "git bisect run" tests Aaron Lipman
2020-08-05  6:11         ` Christian Couder
2020-08-04 22:01       ` [PATCH v4 2/5] rev-list: allow bisect and first-parent flags Aaron Lipman
2020-08-05  0:38         ` Eric Sunshine
2020-08-04 22:01       ` [PATCH v4 3/5] cmd_bisect__helper: defer parsing no-checkout flag Aaron Lipman
2020-08-04 22:01       ` [PATCH v4 4/5] bisect: introduce first-parent flag Aaron Lipman
2020-08-04 22:01       ` [PATCH v4 5/5] bisect: combine args passed to find_bisection() Aaron Lipman
2020-08-04 22:19       ` [PATCH v4 0/5] Introduce --first-parent flag for git bisect Junio C Hamano
2020-08-05  5:55       ` Christian Couder
2020-08-07 21:05         ` Junio C Hamano
2020-08-07 21:17           ` Eric Sunshine
2020-08-07 22:07             ` Junio C Hamano
2020-08-07 22:20               ` Eric Sunshine
2020-08-05  6:18       ` Martin Ågren
2020-08-07 21:58       ` [PATCH v5 " Aaron Lipman
2020-08-07 21:58         ` [PATCH v5 1/5] t6030: modernize "git bisect run" tests Aaron Lipman
2020-08-07 21:58         ` [PATCH v5 2/5] rev-list: allow bisect and first-parent flags Aaron Lipman
2020-08-07 21:58         ` [PATCH v5 3/5] cmd_bisect__helper: defer parsing no-checkout flag Aaron Lipman
2020-08-07 21:58         ` [PATCH v5 4/5] bisect: introduce first-parent flag Aaron Lipman
2020-08-07 21:58         ` [PATCH v5 5/5] bisect: combine args passed to find_bisection() Aaron Lipman

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200801175840.1877-2-alipman88@gmail.com \
    --to=alipman88@gmail.com \
    --cc=git@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Git Mailing List Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/git/0 git/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 git git/ https://lore.kernel.org/git \
		git@vger.kernel.org
	public-inbox-index git

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.git


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git