[BUG] Segfault with rev-list --bisect

[BUG] Segfault with rev-list --bisect

[Troy Moure]

Hi,

I've found a case where git rev-list --bisect segfaults reproducibly
(git version is 2.3.1). This is the commit topology (A2 is the first
parent of M):

I - A1 - A2
  \        \
    - B1 -- M  (HEAD)

And this is an example of a command that segfaults:

git rev-list --bisect --first-parent --parents HEAD --not HEAD~1

I tried a couple of variations quickly: It does not segfault if a
non-merge commit is made on top of M (so HEAD is no longer pointing
directly to M). It also does not segfault if 'HEAD~1' is changed to
'HEAD~2'.

Thanks,
Troy

Re: [BUG] Segfault with rev-list --bisect

[Jeff King]

On Tue, Mar 03, 2015 at 09:19:14AM -0500, Troy Moure wrote:

> I've found a case where git rev-list --bisect segfaults reproducibly
> (git version is 2.3.1). This is the commit topology (A2 is the first
> parent of M):
> 
> I - A1 - A2
>   \        \
>     - B1 -- M  (HEAD)

Thanks for finding a simple history which shows the problem. I recreated
this with:

    git init repo && cd repo &&
    echo I >I && git add I && git commit -m I &&
    echo A1 >A && git add A && git commit -m A1 &&
    echo A2 >A && git add A && git commit -m A2 &&
    git checkout -b side HEAD~2 &&
    echo B1 >B && git add B && git commit -m B1 &&
    git checkout master &&
    GIT_EDITOR=: git merge side

and was able to reproduce the segfault with:

    git rev-list --bisect --first-parent HEAD --not HEAD~1

(it drops --parents from your command, which is not relevant to the
segfault). The segfault itself happens because we try to access the
weight() of B1, even though we never called weight_set() on it.

And that, I think, is related to --first-parent. We do not set a weight
because B1 is not an interesting commit to us (it is accessible only as
a second parent). I am not too familiar with the bisect code, but it
looks like it is not really ready to handle --first-parent. There are
several spots where it enumerates the parent list, which is going to
examine parents other than the first.

Below is a fairly hacky patch to respect --first-parent through the
bisection code. Like I said, I'm not very familiar with this code, so I
basically just blindly limited any traversal of commit->parents. It does
solve this particular segfault, but I have no clue if it is fixing other
bugs introducing them. :) E.g., it's changing count_distance(), so
perhaps our bisection counts were all off with --first-parent, even when
it didn't segfault?

diff --git a/bisect.c b/bisect.c
index 8c6d843..c51f37a 100644
--- a/bisect.c
+++ b/bisect.c
@@ -31,7 +31,7 @@ static const char *argv_update_ref[] = {"update-ref", "--no-deref", "BISECT_HEAD
  * We care just barely enough to avoid recursing for
  * non-merge entries.
  */
-static int count_distance(struct commit_list *entry)
+static int count_distance(struct commit_list *entry, int max_parents)
 {
 	int nr = 0;
 
@@ -47,9 +47,10 @@ static int count_distance(struct commit_list *entry)
 		p = commit->parents;
 		entry = p;
 		if (p) {
+			int n = max_parents - 1;
 			p = p->next;
-			while (p) {
-				nr += count_distance(p);
+			while (p && n-- > 0) {
+				nr += count_distance(p, max_parents);
 				p = p->next;
 			}
 		}
@@ -79,12 +80,12 @@ 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, int max_parents)
 {
 	struct commit_list *p;
 	int count;
 
-	for (count = 0, p = commit->parents; p; p = p->next) {
+	for (count = 0, p = commit->parents; p && max_parents-- > 0; p = p->next) {
 		if (p->item->object.flags & UNINTERESTING)
 			continue;
 		count++;
@@ -117,7 +118,7 @@ static inline int halfway(struct commit_list *p, int nr)
 #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 *list, int max_parents)
 {
 	struct commit_list *p;
 
@@ -132,6 +133,7 @@ static void show_list(const char *debug, int counted, int nr,
 		char *buf = read_sha1_file(commit->object.sha1, &type, &size);
 		const char *subject_start;
 		int subject_len;
+		int n = max_parents;
 
 		fprintf(stderr, "%c%c%c ",
 			(flags & TREESAME) ? ' ' : 'T',
@@ -142,7 +144,7 @@ static void show_list(const char *debug, int counted, int nr,
 		else
 			fprintf(stderr, "---");
 		fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
-		for (pp = commit->parents; pp; pp = pp->next)
+		for (pp = commit->parents; pp && n-- > 0; pp = pp->next)
 			fprintf(stderr, " %.*s", 8,
 				sha1_to_hex(pp->item->object.sha1));
 
@@ -245,7 +247,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 max_parents)
 {
 	int n, counted;
 	struct commit_list *p;
@@ -257,7 +259,7 @@ 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, max_parents)) {
 		case 0:
 			if (!(flags & TREESAME)) {
 				weight_set(p, 1);
@@ -300,7 +302,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 			continue;
 		if (weight(p) != -2)
 			continue;
-		weight_set(p, count_distance(p));
+		weight_set(p, count_distance(p, max_parents));
 		clear_distance(list);
 
 		/* Does it happen to be at exactly half-way? */
@@ -315,10 +317,11 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 		for (p = list; p; p = p->next) {
 			struct commit_list *q;
 			unsigned flags = p->item->object.flags;
+			int n = max_parents;
 
 			if (0 <= weight(p))
 				continue;
-			for (q = p->item->parents; q; q = q->next) {
+			for (q = p->item->parents; q && n-- > 0; q = q->next) {
 				if (q->item->object.flags & UNINTERESTING)
 					continue;
 				if (0 <= weight(q))
@@ -357,11 +360,12 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
 
 struct commit_list *find_bisection(struct commit_list *list,
 					  int *reaches, int *all,
-					  int find_all)
+					  int find_all, int first_parent_only)
 {
 	int nr, on_list;
 	struct commit_list *p, *best, *next, *last;
 	int *weights;
+	int max_parents = first_parent_only ? 1 : INT_MAX;
 
 	show_list("bisection 2 entry", 0, 0, list);
 
@@ -390,7 +394,7 @@ struct commit_list *find_bisection(struct commit_list *list,
 	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, max_parents);
 	if (best) {
 		if (!find_all)
 			best->next = NULL;
@@ -916,7 +920,8 @@ int bisect_next_all(const char *prefix, int no_checkout)
 	bisect_common(&revs);
 
 	revs.commits = find_bisection(revs.commits, &reaches, &all,
-				       !!skipped_revs.nr);
+				       !!skipped_revs.nr,
+				       revs.first_parent_only);
 	revs.commits = managed_skipped(revs.commits, &tried);
 
 	if (!revs.commits) {
diff --git a/bisect.h b/bisect.h
index 2a6c831..03d04d1 100644
--- a/bisect.h
+++ b/bisect.h
@@ -3,7 +3,7 @@
 
 extern struct commit_list *find_bisection(struct commit_list *list,
 					  int *reaches, int *all,
-					  int find_all);
+					  int find_all, int first_parent_only);
 
 extern 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 ff84a82..3f531d6 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -380,7 +380,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 		int reaches = reaches, all = all;
 
 		revs.commits = find_bisection(revs.commits, &reaches, &all,
-					      bisect_find_all);
+					      bisect_find_all,
+					      revs.first_parent_only);
 
 		if (bisect_show_vars)
 			return show_bisect_vars(&info, reaches, all);

Re: [BUG] Segfault with rev-list --bisect

[Junio C Hamano]

Troy Moure <troy.moure@gmail.com> writes:

> git rev-list --bisect --first-parent --parents HEAD --not HEAD~1

Hmm, as "rev-list --bisect" is not end-user facing command (it is
purely an implementation detail for "git bisect") and we never call
it with --first-parent, I am not sure if it is worth labelling it as
a BUG.  Surely, the command can refuse to operate when it sees both
options given, but that would be a fairly low priority.

Of course, if you are planning to do "git bisect --first-parent", it
is one of the things that needs to be addressed, together with
counting the rounds and bisecting the linear set of commits on the
first-parent chain correctly.

Re: [BUG] Segfault with rev-list --bisect

[Troy Moure]

On Wed, Mar 4, 2015 at 6:44 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Troy Moure <troy.moure@gmail.com> writes:
>
>> git rev-list --bisect --first-parent --parents HEAD --not HEAD~1
>
> Hmm, as "rev-list --bisect" is not end-user facing command (it is
> purely an implementation detail for "git bisect") and we never call
> it with --first-parent, I am not sure if it is worth labelling it as
> a BUG.  Surely, the command can refuse to operate when it sees both
> options given, but that would be a fairly low priority.

Hrm, ok. I didn't realize "--bisect" is only intended to be used by git-bisect
(although I suppose the fact that it treats ref/bisect/* specially should have
been a hint). If uses of "--bisect" other than by git-bisect are considered
unsupported, IMO it would be good to say that in the documentation - right now
it looks like just another rev-list parameter. (I realize rev-list itself is
"plumbing", but that's not the same as "not user facing", is it?)

If you're curious, I ran into this because I am working on a script that can be
run repeatedly to process commits, and uses git notes to mark commits that have
been processed.  Parents are always processed before their children, so if a
commit has a note, it means all its ancestors also have notes. I want to
quickly find the set of commits that have not yet been processed. I am thinking
of finding the "boundary" commits (commits that have a note and at least one
child that does not) by using a binary search to find the boundary commit on
the first-parent chain, and then recursively doing the same thing starting from
each non-first parent of each merge commit between the boundary commit and the
starting point.

Upon further thought, it's probably better to just read the whole first-parent
chain and do the binary search in the script, since "git rev-list --bisect"
would have generate the chain each time it's called. But I'd already run into
the segfault, so I thought I'd report it.

Of course, I'd appreciate any thoughts or comments on the problem I'm trying to
solve as well.

Thanks,
Troy

[PATCH] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

rev-list --bisect is used by git bisect, but never together with
--first-parent. Because rev-list --bisect together with --first-parent
is not handled currently, and even leads to segfaults, refuse to use
both options together.

Signed-off-by: Kevin Daudt <me@ikke.info>
---
This is my first code patch, and thought this was a nice exercise.

 Documentation/rev-list-options.txt | 3 ++-
 builtin/rev-list.c                 | 3 +++
 t/t6000-rev-list-misc.sh           | 4 ++++
 3 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 4ed8587..05c3f6d 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -123,7 +123,8 @@ 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.
+	brought in to your history by such a merge. Cannot be
+	combined with --bisect.
 
 --not::
 	Reverses the meaning of the '{caret}' prefix (or lack thereof)
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index ff84a82..c271e15 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -291,6 +291,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (revs.bisect)
 		bisect_list = 1;
 
+	if(revs.first_parent_only && revs.bisect)
+		die(_("--first-parent is incompattible with --bisect"));
+
 	if (DIFF_OPT_TST(&revs.diffopt, QUICK))
 		info.flags |= REV_LIST_QUIET;
 	for (i = 1 ; i < argc; i++) {
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 2602086..1f58b46 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -96,4 +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_done
-- 
2.3.1.184.g97c12a8.dirty

Re: [PATCH] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

On Sat, Mar 07, 2015 at 10:31:16PM +0100, Kevin Daudt wrote:
> diff --git a/builtin/rev-list.c b/builtin/rev-list.c
> index ff84a82..c271e15 100644
> --- a/builtin/rev-list.c
> +++ b/builtin/rev-list.c
> @@ -291,6 +291,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
>  	if (revs.bisect)
>  		bisect_list = 1;
>  
> +	if(revs.first_parent_only && revs.bisect)

I should have added a space after the if.

> +		die(_("--first-parent is incompattible with --bisect"));
> +
>  	if (DIFF_OPT_TST(&revs.diffopt, QUICK))
>  		info.flags |= REV_LIST_QUIET;
>  	for (i = 1 ; i < argc; i++) {

Re: [PATCH] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

Kevin Daudt <me@ikke.info> writes:

> On Sat, Mar 07, 2015 at 10:31:16PM +0100, Kevin Daudt wrote:
>> diff --git a/builtin/rev-list.c b/builtin/rev-list.c
>> index ff84a82..c271e15 100644
>> --- a/builtin/rev-list.c
>> +++ b/builtin/rev-list.c
>> @@ -291,6 +291,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
>>  	if (revs.bisect)
>>  		bisect_list = 1;
>>  
>> +	if(revs.first_parent_only && revs.bisect)
>
> I should have added a space after the if.

Since you are practicing, let me say that a better way to do this is
to reroll the whole patch and have that comment after the three-dash
line.

That is, you respond to your message with a new patch that corrects
the above, and where you said "This is my first code patch, and
thought this was a nice exercise." in your first message, you would
say

  ---

   * changes from v1: corrected coding guideline violation that
     missed a SP between "if("

or something like that.

Thanks.

[PATCH v2] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

rev-list --bisect is used by git bisect, but never together with
--first-parent. Because rev-list --bisect together with --first-parent
is not handled currently, and even leads to segfaults, refuse to use
both options together.

Signed-off-by: Kevin Daudt <me@ikke.info>
Suggested-by: Junio C. Hamano <gitster@pobox.com>
---
* Changes from v1: Added the missing SP between "if(",
  as per the code guidelines

Thanks for the feedback.

 Documentation/rev-list-options.txt | 3 ++-
 builtin/rev-list.c                 | 3 +++
 t/t6000-rev-list-misc.sh           | 4 ++++
 3 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 4ed8587..05c3f6d 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -123,7 +123,8 @@ 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.
+	brought in to your history by such a merge. Cannot be
+	combined with --bisect.
 
 --not::
 	Reverses the meaning of the '{caret}' prefix (or lack thereof)
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index ff84a82..c271e15 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -291,6 +291,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (revs.bisect)
 		bisect_list = 1;
 
+	if(revs.first_parent_only && revs.bisect)
+		die(_("--first-parent is incompattible with --bisect"));
+
 	if (DIFF_OPT_TST(&revs.diffopt, QUICK))
 		info.flags |= REV_LIST_QUIET;
 	for (i = 1 ; i < argc; i++) {
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 2602086..1f58b46 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -96,4 +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_done
-- 
2.3.1.184.g97c12a8.dirty

[PATCH v3] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

rev-list --bisect is used by git bisect, but never together with
--first-parent. Because rev-list --bisect together with --first-parent
is not handled currently, and even leads to segfaults, refuse to use
both options together.

Signed-off-by: Kevin Daudt <me@ikke.info>
Suggested-by: Junio C. Hamano <gitster@pobox.com>
---
Sorry for the false fix reroll in v2, forgot to actually commit the change.

* Changes from v2: Added the missing SP between "if(",
  as per the code guidelines")" (Now with the actual change)

 Documentation/rev-list-options.txt | 3 ++-
 builtin/rev-list.c                 | 3 +++
 t/t6000-rev-list-misc.sh           | 4 ++++
 3 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 4ed8587..05c3f6d 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -123,7 +123,8 @@ 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.
+	brought in to your history by such a merge. Cannot be
+	combined with --bisect.
 
 --not::
 	Reverses the meaning of the '{caret}' prefix (or lack thereof)
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index ff84a82..f5da2a4 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -291,6 +291,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (revs.bisect)
 		bisect_list = 1;
 
+	if (revs.first_parent_only && revs.bisect)
+		die(_("--first-parent is incompattible with --bisect"));
+
 	if (DIFF_OPT_TST(&revs.diffopt, QUICK))
 		info.flags |= REV_LIST_QUIET;
 	for (i = 1 ; i < argc; i++) {
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 2602086..1f58b46 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -96,4 +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_done
-- 
2.3.1.184.g97c12a8.dirty

[PATCH v3] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

rev-list --bisect is used by git bisect, but never together with
--first-parent. Because rev-list --bisect together with --first-parent
is not handled currently, and even leads to segfaults, refuse to use
both options together.

Signed-off-by: Kevin Daudt <me@ikke.info>
Suggested-by: Junio C. Hamano <gitster@pobox.com>
---
Sorry for the false fix reroll in v2, forgot to actually commit the change.

* Changes from v2: Added the missing SP between "if(",
  as per the code guidelines")" (Now with the actual change)

 Documentation/rev-list-options.txt | 3 ++-
 builtin/rev-list.c                 | 3 +++
 t/t6000-rev-list-misc.sh           | 4 ++++
 3 files changed, 9 insertions(+), 1 deletion(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 4ed8587..05c3f6d 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -123,7 +123,8 @@ 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.
+	brought in to your history by such a merge. Cannot be
+	combined with --bisect.
 
 --not::
 	Reverses the meaning of the '{caret}' prefix (or lack thereof)
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index ff84a82..f5da2a4 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -291,6 +291,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (revs.bisect)
 		bisect_list = 1;
 
+	if (revs.first_parent_only && revs.bisect)
+		die(_("--first-parent is incompattible with --bisect"));
+
 	if (DIFF_OPT_TST(&revs.diffopt, QUICK))
 		info.flags |= REV_LIST_QUIET;
 	for (i = 1 ; i < argc; i++) {
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 2602086..1f58b46 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -96,4 +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_done
-- 
2.3.1.184.g97c12a8.dirty

Re: [PATCH v3] rev-list: refuse --first-parent combined with --bisect

[Eric Sunshine]

On Sun, Mar 8, 2015 at 11:03 AM, Kevin Daudt <me@ikke.info> wrote:
> rev-list --bisect is used by git bisect, but never together with
> --first-parent. Because rev-list --bisect together with --first-parent
> is not handled currently, and even leads to segfaults, refuse to use
> both options together.
>
> Signed-off-by: Kevin Daudt <me@ikke.info>
> Suggested-by: Junio C. Hamano <gitster@pobox.com>

It's customary for your sign-off to be last.

> ---
> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> index 4ed8587..05c3f6d 100644
> --- a/Documentation/rev-list-options.txt
> +++ b/Documentation/rev-list-options.txt
> @@ -123,7 +123,8 @@ 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.
> +       brought in to your history by such a merge. Cannot be
> +       combined with --bisect.

A couple questions:

Should the documentation for ---bisect be updated to mention this
restriction also?

Should this change be protected by a "ifndef::git-rev-list[]" as are
all other mentions of "bisect" in rev-list-options.txt?

>  --not::
>         Reverses the meaning of the '{caret}' prefix (or lack thereof)

Re: [PATCH v3] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

On Sun, Mar 08, 2015 at 05:58:24PM -0400, Eric Sunshine wrote:
> On Sun, Mar 8, 2015 at 11:03 AM, Kevin Daudt <me@ikke.info> wrote:
> > rev-list --bisect is used by git bisect, but never together with
> > --first-parent. Because rev-list --bisect together with --first-parent
> > is not handled currently, and even leads to segfaults, refuse to use
> > both options together.
> >
> > Signed-off-by: Kevin Daudt <me@ikke.info>
> > Suggested-by: Junio C. Hamano <gitster@pobox.com>
> 
> It's customary for your sign-off to be last.
> 

Ok, noted

> > ---
> > diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> > index 4ed8587..05c3f6d 100644
> > --- a/Documentation/rev-list-options.txt
> > +++ b/Documentation/rev-list-options.txt
> > @@ -123,7 +123,8 @@ 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.
> > +       brought in to your history by such a merge. Cannot be
> > +       combined with --bisect.
> 
> A couple questions:
> 
> Should the documentation for ---bisect be updated to mention this
> restriction also?

Was doubting whether that was necessary as --bisect can be seen as a
mode, and --first-parent modifying that mode. But it can make sense to
also add it to that section.

> 
> Should this change be protected by a "ifndef::git-rev-list[]" as are
> all other mentions of "bisect" in rev-list-options.txt?

Yes, I see why. git log also uses rev-list-options.txt and it has a
--bisect option that is unrelated to this one, so that comment doesn't
make sense for git log.

Will reroll this later.

[PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

rev-list --bisect is used by git bisect, but never together with
--first-parent. Because rev-list --bisect together with --first-parent
is not handled currently, and even leads to segfaults, refuse to use
both options together.

Suggested-by: Junio C. Hamano <gitster@pobox.com>
Helped-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Kevin Daudt <me@ikke.info>
---
Changes since v3:

* Added an ifdef::git-rev-list[] guard around the warning in the
  --first-parent section so that it only shows up in `man git-rev-list`
  and not in `man git log`

* Added the warning also to the --bisect section.

 Documentation/rev-list-options.txt | 4 ++++
 builtin/rev-list.c                 | 3 +++
 t/t6000-rev-list-misc.sh           | 4 ++++
 3 files changed, 11 insertions(+)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 4ed8587..a148672 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -124,6 +124,9 @@ parents) and `--max-parents=-1` (negative numbers denote no upper limit).
 	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.
+ifdef::git-rev-list[]
+	Cannot be combined with --bisect.
+endif::git-rev-list[]
 
 --not::
 	Reverses the meaning of the '{caret}' prefix (or lack thereof)
@@ -567,6 +570,7 @@ 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.
 
 --bisect-vars::
 	This calculates the same as `--bisect`, except that refs in
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index ff84a82..f5da2a4 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -291,6 +291,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (revs.bisect)
 		bisect_list = 1;
 
+	if (revs.first_parent_only && revs.bisect)
+		die(_("--first-parent is incompattible with --bisect"));
+
 	if (DIFF_OPT_TST(&revs.diffopt, QUICK))
 		info.flags |= REV_LIST_QUIET;
 	for (i = 1 ; i < argc; i++) {
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 2602086..1f58b46 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -96,4 +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_done
-- 
2.3.0

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

Kevin Daudt <me@ikke.info> writes:

> rev-list --bisect is used by git bisect, but never together with
> --first-parent. Because rev-list --bisect together with --first-parent
> is not handled currently, and even leads to segfaults, refuse to use
> both options together.
>
> Suggested-by: Junio C. Hamano <gitster@pobox.com>
> Helped-by: Eric Sunshine <sunshine@sunshineco.com>
> Signed-off-by: Kevin Daudt <me@ikke.info>
> ---
> Changes since v3:
>
> * Added an ifdef::git-rev-list[] guard around the warning in the
>   --first-parent section so that it only shows up in `man git-rev-list`
>   and not in `man git log`
>
> * Added the warning also to the --bisect section.

I wonder what "git log --first-parent --bisect A..B" should do,
though.

Wouldn't the rejection belong to revision.c::setup_revisions(),
where we reject combined use of (--reverse, --walk-reflogs) and
(--children, --parents), to apply this to all commands in the "log"
family that uses the revision walker machinery?

>
>  Documentation/rev-list-options.txt | 4 ++++
>  builtin/rev-list.c                 | 3 +++
>  t/t6000-rev-list-misc.sh           | 4 ++++
>  3 files changed, 11 insertions(+)
>
> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
> index 4ed8587..a148672 100644
> --- a/Documentation/rev-list-options.txt
> +++ b/Documentation/rev-list-options.txt
> @@ -124,6 +124,9 @@ parents) and `--max-parents=-1` (negative numbers denote no upper limit).
>  	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.
> +ifdef::git-rev-list[]
> +	Cannot be combined with --bisect.
> +endif::git-rev-list[]
>  
>  --not::
>  	Reverses the meaning of the '{caret}' prefix (or lack thereof)
> @@ -567,6 +570,7 @@ 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.
>  
>  --bisect-vars::
>  	This calculates the same as `--bisect`, except that refs in
> diff --git a/builtin/rev-list.c b/builtin/rev-list.c
> index ff84a82..f5da2a4 100644
> --- a/builtin/rev-list.c
> +++ b/builtin/rev-list.c
> @@ -291,6 +291,9 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
>  	if (revs.bisect)
>  		bisect_list = 1;
>  
> +	if (revs.first_parent_only && revs.bisect)
> +		die(_("--first-parent is incompattible with --bisect"));
> +
>  	if (DIFF_OPT_TST(&revs.diffopt, QUICK))
>  		info.flags |= REV_LIST_QUIET;
>  	for (i = 1 ; i < argc; i++) {
> diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
> index 2602086..1f58b46 100755
> --- a/t/t6000-rev-list-misc.sh
> +++ b/t/t6000-rev-list-misc.sh
> @@ -96,4 +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_done

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

On Tue, Mar 10, 2015 at 03:09:54PM -0700, Junio C Hamano wrote:
> Kevin Daudt <me@ikke.info> writes:
> 
> > rev-list --bisect is used by git bisect, but never together with
> > --first-parent. Because rev-list --bisect together with --first-parent
> > is not handled currently, and even leads to segfaults, refuse to use
> > both options together.
> >
> > Suggested-by: Junio C. Hamano <gitster@pobox.com>
> > Helped-by: Eric Sunshine <sunshine@sunshineco.com>
> > Signed-off-by: Kevin Daudt <me@ikke.info>
> > ---
> > Changes since v3:
> >
> > * Added an ifdef::git-rev-list[] guard around the warning in the
> >   --first-parent section so that it only shows up in `man git-rev-list`
> >   and not in `man git log`
> >
> > * Added the warning also to the --bisect section.
> 
> I wonder what "git log --first-parent --bisect A..B" should do,
> though.
> 
> Wouldn't the rejection belong to revision.c::setup_revisions(),
> where we reject combined use of (--reverse, --walk-reflogs) and
> (--children, --parents), to apply this to all commands in the "log"
> family that uses the revision walker machinery?
> 

git log --bisect seems to do something different then git rev-list
--bisect

>From git-log(1):

    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.

This seems to just add addition refs to the log command, which seems
unrelated to what rev-list --bisect does.

So I don't see why git log --bisect --first-parent should be prohibited
(unless this combination doesn't make sense on itself).

Kevin.

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

Kevin Daudt <me@ikke.info> writes:

> git log --bisect seems to do something different then git rev-list
> --bisect
>
> From git-log(1):
>
>     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.
>
> This seems to just add addition refs to the log command, which seems
> unrelated to what rev-list --bisect does.
>
> So I don't see why git log --bisect --first-parent should be prohibited
> (unless this combination doesn't make sense on itself).

Well, but think if your "unless" holds true or not yourself first
and then say "I do not think this combination doesn't make sense",
if you truly mean "I don't see why ... should be prohibited".

What does such a command line _mean_?  It tells us this:

    Define a set by having the "bad" ref as a positive end, and
    having all the "good" refs as negative (uninteresting) boundary.

That is a way to show commits that are reachable from the bad one
and excluding the ones that are reachable from any of the known-good
commits.  The area of the graph in the current bisection that
contains suspect commits.

Now, what does it mean to pull only the first-parent chain starting
from the bad one in such a set in the first place?  What does the
resulting set of commits mean?

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

On Tue, Mar 10, 2015 at 04:12:18PM -0700, Junio C Hamano wrote:
> Kevin Daudt <me@ikke.info> writes:
> 
> > git log --bisect seems to do something different then git rev-list
> > --bisect
> >
> > From git-log(1):
> >
> >     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.
> >
> > This seems to just add addition refs to the log command, which seems
> > unrelated to what rev-list --bisect does.
> >
> > So I don't see why git log --bisect --first-parent should be prohibited
> > (unless this combination doesn't make sense on itself).
> 
> Well, but think if your "unless" holds true or not yourself first
> and then say "I do not think this combination doesn't make sense",
> if you truly mean "I don't see why ... should be prohibited".
> 
> What does such a command line _mean_?  It tells us this:
> 
>     Define a set by having the "bad" ref as a positive end, and
>     having all the "good" refs as negative (uninteresting) boundary.
> 
> That is a way to show commits that are reachable from the bad one
> and excluding the ones that are reachable from any of the known-good
> commits.  The area of the graph in the current bisection that
> contains suspect commits.
> 
> Now, what does it mean to pull only the first-parent chain starting
> from the bad one in such a set in the first place?  What does the
> resulting set of commits mean?
> 
> 

In that case it will leave out any merged in branches.

I recalled reading something about this. Searching found me the GSoC
idea:

    When your project is strictly "new features are merged into trunk,
    never the other way around", it is handy to be able to first find a
    merge on the trunk that merged a topic to point fingers at when a
    bug appears, instead of having to drill down to the individual
    commit on the faulty side branch.

So there is definitely a use case for --bisect --first-parent, which
would show you those commits that would be part of the bisection.

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

Kevin Daudt <me@ikke.info> writes:

> On Tue, Mar 10, 2015 at 04:12:18PM -0700, Junio C Hamano wrote:
>
>> What does such a command line _mean_?  It tells us this:
>> 
>>     Define a set by having the "bad" ref as a positive end, and
>>     having all the "good" refs as negative (uninteresting) boundary.
>> 
>> That is a way to show commits that are reachable from the bad one
>> and excluding the ones that are reachable from any of the known-good
>> commits.  The area of the graph in the current bisection that
>> contains suspect commits.
>> 
>> Now, what does it mean to pull only the first-parent chain starting
>> from the bad one in such a set in the first place?  What does the
>> resulting set of commits mean?
>
> In that case it will leave out any merged in branches.

Needs a bit more thinking (hint: branches merged into *what*?).

> I recalled reading something about this. Searching found me the GSoC
> idea:
>
>     When your project is strictly "new features are merged into trunk,
>     never the other way around", it is handy to be able to first find a
>     merge on the trunk that merged a topic to point fingers at when a
>     bug appears, instead of having to drill down to the individual
>     commit on the faulty side branch.
>
> So there is definitely a use case for --bisect --first-parent, which
> would show you those commits that would be part of the bisection.

Step back and think why "git bisect --first-parent" is sometimes
desired in the first place.

It is because in the regular bisection, you will almost always end
up on a commit that is _not_ on the first-parent chain and asked to
check that commit at a random place on a side branch in the first
place. And you mark such a commit as "bad".

The thing is, traversing from that "bad" commit that is almost
always is on a side branch, following the first-parent chain, will
not be a useful history that "leaves out any merged in branches".

When "git bisect --first-parent" feature gets implemented, "do not
use --first-parent with --bisect" limitation has to be lifted
anyway, but until then, not allowing "--first-parent --bisect" for
"rev-list" but allowing it for "log" does not buy our users much.
The output does not give us a nice "show me which merges on the
trunk may have caused the breakage to be examined with the remainder
of this bisect session".

So, yes, there is a use case for "log --bisect --first-parent", once
there is a working "bisect --first-parent", but not until then, the
command is not useful, I would think.

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

On Wed, Mar 11, 2015 at 01:13:48PM -0700, Junio C Hamano wrote:
> Kevin Daudt <me@ikke.info> writes:
> 
> > On Tue, Mar 10, 2015 at 04:12:18PM -0700, Junio C Hamano wrote:
> >
> 
> Step back and think why "git bisect --first-parent" is sometimes
> desired in the first place.
> 
> It is because in the regular bisection, you will almost always end
> up on a commit that is _not_ on the first-parent chain and asked to
> check that commit at a random place on a side branch in the first
> place. And you mark such a commit as "bad".
> 
> The thing is, traversing from that "bad" commit that is almost
> always is on a side branch, following the first-parent chain, will
> not be a useful history that "leaves out any merged in branches".
> 
> When "git bisect --first-parent" feature gets implemented, "do not
> use --first-parent with --bisect" limitation has to be lifted
> anyway, but until then, not allowing "--first-parent --bisect" for
> "rev-list" but allowing it for "log" does not buy our users much.
> The output does not give us a nice "show me which merges on the
> trunk may have caused the breakage to be examined with the remainder
> of this bisect session".
> 
> So, yes, there is a use case for "log --bisect --first-parent", once
> there is a working "bisect --first-parent", but not until then, the
> command is not useful, I would think.

Thank you for you explanation. My confusion came from incorrectly
assuming refs/bisect/bad and refs/bisect/good-* were pointing to the
initially specified good and bad commits, in which case the combination
does make sense.

I was looking in the manpages for the meaning of the bisect refs, but
could only find something about refs/bisect/bad:

git-bisect(1):
> Eventually there will be no more revisions left to bisect, and you
> will have been left with the first bad kernel revision in
> "refs/bisect/bad

So this ref changes to the bad commit.

For refs/bisect/good-*, I could only find an example snippet:

> GOOD=$(git for-each-ref "--format=%(objectname)" refs/bisect/good-*)

But it's not really clear what * might be expanded to, nor what they
mean. I guess this could use some clarrification in the documentation.

Knowing this, I agree that the combination log --bisect --first-parent
doesn't make sense either.

I will send in a new patch.

Kevin

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

Kevin Daudt <me@ikke.info> writes:

> So this ref changes to the bad commit.
>
> For refs/bisect/good-*, I could only find an example snippet:
>
>> GOOD=$(git for-each-ref "--format=%(objectname)" refs/bisect/good-*)
>
> But it's not really clear what * might be expanded to, nor what they
> mean. I guess this could use some clarrification in the documentation.

Because the history is not linear in Git, bisection works by
shrinking a subgraph of the history DAG that contains "yet to be
tested, suspected to have introduced a badness" commits.  The
subgraph is defined as anything reachable from _the_ "bad" commit
(initially, the one you give to the command when you start) that are
not reachable from any of the "good" commits.

Suppose you started from this graph.  Time flows left to right as
usual.

  ---0---2---4---6---8---9
      \             /
       1---3---5---7

Then mark the initial good and bad commits as G and B.

  ---G---2---4---6---8---B
      \             /
       1---3---5---7

And imagine that you are asked to check 4, which turns out to be
good.  We do not _move_ G to 4; we mark 4 as good, while keeping
0 also as good.

  ---G---2---G---6---8---B
      \             /
       1---3---5---7

And if you are next asked to check 5, and mark it as good, the graph
will become like this:

  ---G---2---G---6---8---B
      \             /
       1---3---G---7

Of course, at this point, the subgraph of suspects are 6, 7, 8 and
9, and the subgraph no longer is affected by the fact that 0 is
good.  But it is crucial to keep 0 marked as good in the step before
this one, before you tested 5, as that is what allows us not having
to test any ancestors of 0 at all.

Now, one may wonder why we need multiple "good" commits but we do
not need multiple "bad" commits.  This comes from the nature of
"bisection", which is a tool to find a _single_ breakage [*1*], and
a fundamental assumption is that a breakage does not fix itself.

Hence, if you have a history that looks like this:


   G...1---2---3---4---6---8---B
                    \
                     5---7---B

it follows that 4 must also be "bad".  It used to be good long time
ago somewhere before 1, and somewhere along way on the history,
there was a single breakage event that we are hunting for.  That
single event cannot be 5, 6, 7 or 8 because breakage at say 5 would
not explain why the tip of the upper branch is broken---its breakage
has no way to propagate there.  The breakage must have happened at 4
or before that commit.

Which means that if you marked the child of 8 (the tip of the upper
branch) as bad, there is no reason for us to even look at the lower
branch.  As soon as you mark the tip of the upper branch "bad", the
bisection can become

   G...1---2---3---4---6---8---B

and without looking at the lower branch, it can find the single
breakage.


[Footnote]

*1* You may be hunting for a single _fix_, and flipping the meaning
    of "good" and "bad", say "It used to be broken but somewhere we
    seem to have fixed that bug.  Where did we do that?", marking
    the ones that still has the bug "good" and the ones that no
    longer has the bug "bad".  In that context, you would be looking
    for a single fix.  A more neutral term might be

    - we look for a single event that changes some state.

    - old state before that single event is spelled G O O D, but it
      is pronounced "not yet".

    - new state before that single event is spelled B A D, but it is
      pronounced "already".

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Philip Oakley]

From: "Junio C Hamano" <gitster@pobox.com>
> Kevin Daudt <me@ikke.info> writes:
>
>> So this ref changes to the bad commit.
>>
>> For refs/bisect/good-*, I could only find an example snippet:
>>
>>> GOOD=$(git for-each-ref "--format=%(objectname)" refs/bisect/good-*)
>>
>> But it's not really clear what * might be expanded to, nor what they
>> mean. I guess this could use some clarrification in the 
>> documentation.
>
> Because the history is not linear in Git, bisection works by
> shrinking a subgraph of the history DAG that contains "yet to be
> tested, suspected to have introduced a badness" commits.  The
> subgraph is defined as anything reachable from _the_ "bad" commit
> (initially, the one you give to the command when you start) that are
> not reachable from any of the "good" commits.
>
> Suppose you started from this graph.  Time flows left to right as
> usual.
>
>  ---0---2---4---6---8---9
>      \             /
>       1---3---5---7
>
> Then mark the initial good and bad commits as G and B.
>
>  ---G---2---4---6---8---B
>      \             /
>       1---3---5---7
>
> And imagine that you are asked to check 4, which turns out to be
> good.  We do not _move_ G to 4; we mark 4 as good, while keeping
> 0 also as good.
>
>  ---G---2---G---6---8---B
>      \             /
>       1---3---5---7
>
> And if you are next asked to check 5, and mark it as good, the graph
> will become like this:
>
>  ---G---2---G---6---8---B
>      \             /
>       1---3---G---7
>
> Of course, at this point, the subgraph of suspects are 6, 7, 8 and
> 9, and the subgraph no longer is affected by the fact that 0 is
> good.  But it is crucial to keep 0 marked as good in the step before
> this one, before you tested 5, as that is what allows us not having
> to test any ancestors of 0 at all.
>
> Now, one may wonder why we need multiple "good" commits but we do
> not need multiple "bad" commits.  This comes from the nature of
> "bisection", which is a tool to find a _single_ breakage [*1*], and
> a fundamental assumption is that a breakage does not fix itself.
>
> Hence, if you have a history that looks like this:
>
>
>   G...1---2---3---4---6---8---B
>                    \
>                     5---7---B
>
> it follows that 4 must also be "bad".  It used to be good long time
> ago somewhere before 1, and somewhere along way on the history,
> there was a single breakage event that we are hunting for.  That
> single event cannot be 5, 6, 7 or 8 because breakage at say 5 would
> not explain why the tip of the upper branch is broken---its breakage
> has no way to propagate there.  The breakage must have happened at 4
> or before that commit.

Is it not worth at least confirming the assertion that 4 is bad before
proceding, or at least an option to confirm that in complex scenarios
where the fault may be devious.
[the explicit explanation has been useful for me...]

>
> Which means that if you marked the child of 8 (the tip of the upper
> branch) as bad, there is no reason for us to even look at the lower
> branch.  As soon as you mark the tip of the upper branch "bad", the
> bisection can become
>
>   G...1---2---3---4---6---8---B
>
> and without looking at the lower branch, it can find the single
> breakage.
>
>
> [Footnote]
>
> *1* You may be hunting for a single _fix_, and flipping the meaning
>    of "good" and "bad", say "It used to be broken but somewhere we
>    seem to have fixed that bug.  Where did we do that?", marking
>    the ones that still has the bug "good" and the ones that no
>    longer has the bug "bad".  In that context, you would be looking
>    for a single fix.  A more neutral term might be
>
>    - we look for a single event that changes some state.
>
>    - old state before that single event is spelled G O O D, but it
>      is pronounced "not yet".
>
>    - new state before that single event is spelled B A D, but it is
>      pronounced "already".
> --
> 

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

"Philip Oakley" <philipoakley@iee.org> writes:

> From: "Junio C Hamano" <gitster@pobox.com>
>
>> Hence, if you have a history that looks like this:
>>
>>
>>   G...1---2---3---4---6---8---B
>>                    \
>>                     5---7---B
>>
>> it follows that 4 must also be "bad".  It used to be good long time
>> ago somewhere before 1, and somewhere along way on the history,
>> there was a single breakage event that we are hunting for.  That
>> single event cannot be 5, 6, 7 or 8 because breakage at say 5 would
>> not explain why the tip of the upper branch is broken---its breakage
>> has no way to propagate there.  The breakage must have happened at 4
>> or before that commit.
>
> Is it not worth at least confirming the assertion that 4 is bad before
> proceding, or at least an option to confirm that in complex scenarios
> where the fault may be devious.

That raises a somewhat interesting tangent.

Christian seems to be forever interested in bisect, so I'll add him
to the Cc list ;-)

There is no way to give multiple "bad" from the command line.  You
can say "git bisect start rev rev rev..." but that gives only one
bad and everything else is good.  And once you specify one of the
above two bad ones (say, the child of 8), then we will not even
offer the other one (i.e. the child of 7) as a candidate to be
tested.  So in that sense, "confirm that 4 is bad before proceeding"
is a moot point.

However, you can say "git bisect bad <rev>" (and "git bisect good
<rev>" for that matter) on a rev that is unrelated to what the
current bisection state is.  E.g. after you mark the child of 8 as
"bad", the bisected graph would become

   G...1---2---3---4---6---8---B

and you would be offered to test somewhere in the middle, say, 4.
But it is perfectly OK for you to respond with "git bisect bad 7",
if you know 7 is bad.

I _think_ the current code blindly overwrites the "bad" pointer,
making the bisection state into this graph if you do so.

   G...1---2---3---4
                    \
                     5---B

This is very suboptimal.  The side branch 4-to-7 could be much
longer than the original trunk 4-to-the-tip, in which case we would
have made the suspect space _larger_, not smaller.

We certainly should be able to take advantage of the fact that the
current "bad" commit (i.e. the child of 8) and the newly given "bad"
commit (i.e. 7) are both known to be bad and mark 4 as "bad" instead
when that happens, instead of doing the suboptimal thing the code
currently does.

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Christian Couder]

On Mon, Mar 16, 2015 at 10:05 PM, Junio C Hamano <gitster@pobox.com> wrote:
> "Philip Oakley" <philipoakley@iee.org> writes:
>
>> From: "Junio C Hamano" <gitster@pobox.com>
>>
>>> Hence, if you have a history that looks like this:
>>>
>>>
>>>   G...1---2---3---4---6---8---B
>>>                    \
>>>                     5---7---B
>>>
>>> it follows that 4 must also be "bad".  It used to be good long time
>>> ago somewhere before 1, and somewhere along way on the history,
>>> there was a single breakage event that we are hunting for.  That
>>> single event cannot be 5, 6, 7 or 8 because breakage at say 5 would
>>> not explain why the tip of the upper branch is broken---its breakage
>>> has no way to propagate there.  The breakage must have happened at 4
>>> or before that commit.
>>
>> Is it not worth at least confirming the assertion that 4 is bad before
>> proceding, or at least an option to confirm that in complex scenarios
>> where the fault may be devious.
>
> That raises a somewhat interesting tangent.
>
> Christian seems to be forever interested in bisect, so I'll add him
> to the Cc list ;-)
>
> There is no way to give multiple "bad" from the command line.  You
> can say "git bisect start rev rev rev..." but that gives only one
> bad and everything else is good.  And once you specify one of the
> above two bad ones (say, the child of 8), then we will not even
> offer the other one (i.e. the child of 7) as a candidate to be
> tested.  So in that sense, "confirm that 4 is bad before proceeding"
> is a moot point.
>
> However, you can say "git bisect bad <rev>" (and "git bisect good
> <rev>" for that matter) on a rev that is unrelated to what the
> current bisection state is.  E.g. after you mark the child of 8 as
> "bad", the bisected graph would become
>
>    G...1---2---3---4---6---8---B
>
> and you would be offered to test somewhere in the middle, say, 4.
> But it is perfectly OK for you to respond with "git bisect bad 7",
> if you know 7 is bad.
>
> I _think_ the current code blindly overwrites the "bad" pointer,
> making the bisection state into this graph if you do so.
>
>    G...1---2---3---4
>                     \
>                      5---B

Yes, we keep only one "bad" pointer.

> This is very suboptimal.  The side branch 4-to-7 could be much
> longer than the original trunk 4-to-the-tip, in which case we would
> have made the suspect space _larger_, not smaller.

Yes, but the user is supposed to not change the "bad" pointer for no
good reason. For example maybe a mistake was made and the first commit
marked as "bad" was not actually bad.

> We certainly should be able to take advantage of the fact that the
> current "bad" commit (i.e. the child of 8) and the newly given "bad"
> commit (i.e. 7) are both known to be bad and mark 4 as "bad" instead
> when that happens, instead of doing the suboptimal thing the code
> currently does.

Yeah, we could do that, but we would have to allow it only if a
special option is passed on the command line, for example:

git bisect bad --alternate <commitish>

and/or we could make "git bisect bad" accept any number of bad commitishs.

That could give additional bonus points to the GSoC student who would
implement it :-)

Thanks,
Christian.

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

Christian Couder <christian.couder@gmail.com> writes:

> On Mon, Mar 16, 2015 at 10:05 PM, Junio C Hamano <gitster@pobox.com> wrote:
>
>> However, you can say "git bisect bad <rev>" (and "git bisect good
>> <rev>" for that matter) on a rev that is unrelated to what the
>> current bisection state is.  E.g. after you mark the child of 8 as
>> "bad", the bisected graph would become
>>
>>    G...1---2---3---4---6---8---B
>>
>> and you would be offered to test somewhere in the middle, say, 4.
>> But it is perfectly OK for you to respond with "git bisect bad 7",
>> if you know 7 is bad.
>>
>> I _think_ the current code blindly overwrites the "bad" pointer,
>> making the bisection state into this graph if you do so.
>>
>>    G...1---2---3---4
>>                     \
>>                      5---B
>
> Yes, we keep only one "bad" pointer.
>
>> This is very suboptimal.  The side branch 4-to-7 could be much
>> longer than the original trunk 4-to-the-tip, in which case we would
>> have made the suspect space _larger_, not smaller.
>
> Yes, but the user is supposed to not change the "bad" pointer for no
> good reason.

That is irrelevant, no?  Nobody is questioning that the user is
supposed to judge if a commit is "good" or "bad" correctly.

And nobody sane is dreaming that "Git could do better and detect
user's mistakes when the user says 'bad' for a commit that is
actually 'good'"; if Git can do that, then it should be able to do
the bisect without any user input (including "bisect run") at all
;-).

>> We certainly should be able to take advantage of the fact that the
>> current "bad" commit (i.e. the child of 8) and the newly given "bad"
>> commit (i.e. 7) are both known to be bad and mark 4 as "bad" instead
>> when that happens, instead of doing the suboptimal thing the code
>> currently does.
>
> Yeah, we could do that, but we would have to allow it only if a
> special option is passed on the command line, for example:
> git bisect bad --alternate <commitish>

I am not quite sure if I am correctly getting what you meant to say,
but if you meant "only when --alternate is given, we should do the
merge-base thing; we should keep losing the current 'bad' and
replace it with the new one without the --alternate option", I would
see that as an exercise of a bad taste.

Because the merge-base thing is using both the current and the new
one, such a use is not "alternate" in the first place.

If the proposal were "with a new option, the user can say 'oh, I
made a mistake earlier and said that a commit that is not bad as
'bad'.  Let me replace the commit currently marked as 'bad' with
this one.", I would find it very sensible, actually.

I can see that such an operation can be called "alternate", but
"--fix" might be shorter-and-sweeter-and-to-the-point.

In the "normal" case, the commit we offer the user to check (and
respond with "git bisect bad" without any commit parameter) is
always an ancestor of the current 'bad', so the merge-base with
'bad' and the commit that was just checked would always be the
current commit.  Using the merge-base thing will be transparent to
the end users in the normal case, and when the user has off-line
knowledge that some other commit that is not an ancestor of the
current 'bad' commit is bad, the merge-base thing will give a better
behaviour than the current implementation that blindly replaces.

> and/or we could make "git bisect bad" accept any number of bad
> commitishs.

Yes, that is exactly what I meant.

The way I understand the Philip's point is that the user may have
a-priori knowledge that a breakage from the same cause appears in
both tips of these branches.  In such a case, we can start bisection
after marking the merge-base of two 'bad' commits, e.g. 4 in the
illustration in the message you are responding to, instead of
including 5, 6, and 8 in the suspect set.

You need to be careful, though.  An obvious pitfall is what you
should do when there is a criss-cross merge.

Thanks.

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Christian Couder]

On Tue, Mar 17, 2015 at 7:33 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Christian Couder <christian.couder@gmail.com> writes:
>
>> On Mon, Mar 16, 2015 at 10:05 PM, Junio C Hamano <gitster@pobox.com> wrote:
>>
>>> However, you can say "git bisect bad <rev>" (and "git bisect good
>>> <rev>" for that matter) on a rev that is unrelated to what the
>>> current bisection state is.  E.g. after you mark the child of 8 as
>>> "bad", the bisected graph would become
>>>
>>>    G...1---2---3---4---6---8---B
>>>
>>> and you would be offered to test somewhere in the middle, say, 4.
>>> But it is perfectly OK for you to respond with "git bisect bad 7",
>>> if you know 7 is bad.
>>>
>>> I _think_ the current code blindly overwrites the "bad" pointer,
>>> making the bisection state into this graph if you do so.
>>>
>>>    G...1---2---3---4
>>>                     \
>>>                      5---B
>>
>> Yes, we keep only one "bad" pointer.
>>
>>> This is very suboptimal.  The side branch 4-to-7 could be much
>>> longer than the original trunk 4-to-the-tip, in which case we would
>>> have made the suspect space _larger_, not smaller.
>>
>> Yes, but the user is supposed to not change the "bad" pointer for no
>> good reason.
>
> That is irrelevant, no?  Nobody is questioning that the user is
> supposed to judge if a commit is "good" or "bad" correctly.

So if there is already a bad commit and the user gives another
bad commit, that means that the user knows that it will replace the
existing bad commit with the new one and that it's done for this
purpose.

> And nobody sane is dreaming that "Git could do better and detect
> user's mistakes when the user says 'bad' for a commit that is
> actually 'good'"; if Git can do that, then it should be able to do
> the bisect without any user input (including "bisect run") at all
> ;-).
>
>>> We certainly should be able to take advantage of the fact that the
>>> current "bad" commit (i.e. the child of 8) and the newly given "bad"
>>> commit (i.e. 7) are both known to be bad and mark 4 as "bad" instead
>>> when that happens, instead of doing the suboptimal thing the code
>>> currently does.
>>
>> Yeah, we could do that, but we would have to allow it only if a
>> special option is passed on the command line, for example:
>> git bisect bad --alternate <commitish>
>
> I am not quite sure if I am correctly getting what you meant to say,
> but if you meant "only when --alternate is given, we should do the
> merge-base thing; we should keep losing the current 'bad' and
> replace it with the new one without the --alternate option", I would
> see that as an exercise of a bad taste.

What I wanted to say is that if we change "git bisect bad <commitish>",
so that now it means "add a new bad commit" instead of the previous
"replace the current bad commit, if any, with this one", then experienced
users might see that change as a regression in the user interface and
it might even break scripts.

That's why I suggested to use a new option to mean
"add a new bad commit", though --alternate might not be the best
name for this option.

> Because the merge-base thing is using both the current and the new
> one, such a use is not "alternate" in the first place.
>
> If the proposal were "with a new option, the user can say 'oh, I
> made a mistake earlier and said that a commit that is not bad as
> 'bad'.  Let me replace the commit currently marked as 'bad' with
> this one.", I would find it very sensible, actually.

What I find sensible is to not break the semantics of the current
interface.

> I can see that such an operation can be called "alternate", but
> "--fix" might be shorter-and-sweeter-and-to-the-point.
>
> In the "normal" case, the commit we offer the user to check (and
> respond with "git bisect bad" without any commit parameter) is
> always an ancestor of the current 'bad', so the merge-base with
> 'bad' and the commit that was just checked would always be the
> current commit.  Using the merge-base thing will be transparent to
> the end users in the normal case, and when the user has off-line
> knowledge that some other commit that is not an ancestor of the
> current 'bad' commit is bad, the merge-base thing will give a better
> behaviour than the current implementation that blindly replaces.

Yes, I agree that it could be an improvement to make it possible for the
user to specify another bad commit. I just think it should be done with
a new option if there is already a bad commit...

>> and/or we could make "git bisect bad" accept any number of bad
>> commitishs.

... or by allowing any number of bad commits after "git bisect bad".

> Yes, that is exactly what I meant.
>
> The way I understand the Philip's point is that the user may have
> a-priori knowledge that a breakage from the same cause appears in
> both tips of these branches.  In such a case, we can start bisection
> after marking the merge-base of two 'bad' commits, e.g. 4 in the
> illustration in the message you are responding to, instead of
> including 5, 6, and 8 in the suspect set.

Yeah, I agree that we can do better in this case.

> You need to be careful, though.  An obvious pitfall is what you
> should do when there is a criss-cross merge.

Yeah, it is not as simple as it might look like, neither for the interface
nor for the behavior.

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

Christian Couder <christian.couder@gmail.com> writes:

> On Tue, Mar 17, 2015 at 7:33 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Christian Couder <christian.couder@gmail.com> writes:
>>
>>> Yes, but the user is supposed to not change the "bad" pointer for no
>>> good reason.
>>
>> That is irrelevant, no?  Nobody is questioning that the user is
>> supposed to judge if a commit is "good" or "bad" correctly.
>
> So if there is already a bad commit and the user gives another
> bad commit, that means that the user knows that it will replace the
> existing bad commit with the new one and that it's done for this
> purpose.

ECANNOTQUITEPARSE.  The user may say "git bisect bad $that" and we
do not question $that is bad. Git does not know better than the
user.

But that does not mean Git does not know better than the user how
the current bad commit and $that commit are related.  The user is
not interested in "replacing" at all.  The user is telling just one
single fact, that is, "$that is bad".

>> I am not quite sure if I am correctly getting what you meant to say,
>> but if you meant "only when --alternate is given, we should do the
>> merge-base thing; we should keep losing the current 'bad' and
>> replace it with the new one without the --alternate option", I would
>> see that as an exercise of a bad taste.
>
> What I wanted to say is that if we change "git bisect bad <commitish>",
> so that now it means "add a new bad commit" instead of the previous
> "replace the current bad commit, if any, with this one", then experienced
> users might see that change as a regression in the user interface and
> it might even break scripts.

Huh?  

Step back a bit.  The place you need to start from is to admit the
fact that what "git bisect bad <committish>" currently does is
broken.

Try creating this history yourself

    a---b---c---d---e---f

and start bisection this way:

    $ git bisect start f c
    $ git bisect bad a

Immediately after the second command, "git bisect" moans

    Some good revs are not ancestor of the bad rev.
    git bisect cannot work properly in this case.
    Maybe you mistake good and bad revs?

when it notices that the good rev (i.e. 'c') is no longer an
ancestor of the 'bad', which now points at 'a'.

But that is because "git bisect bad" _blindly_ moved 'bad' that used
to point at 'f' to 'a', making a good rev (i.e. 'c') an ancestor of
the bad rev, without even bothering to check.

Now, if we fixed this bug and made the bisect_state function more
careful (namely, when accepting "bad", make sure it is not beyond
any existing "good", or barf like the above, _without_ moving the
bad pointer), the user interface and behaviour would be changed.  Is
that a regression?  No, it is a usability fix and a progress.

Simply put, bisect_state function can become more careful and
intelligent to help users.

I view this "user goes out of way to tell us a commit that is known
to be bad as bad, even though it is not what we offered to test and
is not an ancestor of the commit that currently marked as bad" case
the same way.  We by now hopefully understand that blindly replacing
the current 'bad' is suboptimal.  By teaching bisect_state to do the
"merge-base thing", we would be fixing that.

Why is it a regression?

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Christian Couder]

On Tue, Mar 17, 2015 at 9:46 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Christian Couder <christian.couder@gmail.com> writes:
>
>> On Tue, Mar 17, 2015 at 7:33 PM, Junio C Hamano <gitster@pobox.com> wrote:
>>> Christian Couder <christian.couder@gmail.com> writes:
>>>
>>>> Yes, but the user is supposed to not change the "bad" pointer for no
>>>> good reason.
>>>
>>> That is irrelevant, no?  Nobody is questioning that the user is
>>> supposed to judge if a commit is "good" or "bad" correctly.
>>
>> So if there is already a bad commit and the user gives another
>> bad commit, that means that the user knows that it will replace the
>> existing bad commit with the new one and that it's done for this
>> purpose.
>
> ECANNOTQUITEPARSE.  The user may say "git bisect bad $that" and we
> do not question $that is bad. Git does not know better than the
> user.
>
> But that does not mean Git does not know better than the user how
> the current bad commit and $that commit are related.  The user is
> not interested in "replacing" at all.  The user is telling just one
> single fact, that is, "$that is bad".

The user may make mistakes and try to fix them, like for example:

$ git checkout master
$ git bisect bad
$ git log --oneline --decorate --graph --all
# Ooops I was not on the right branch
$ git checkout dev
$ git bisect bad
$ git log --oneline --decorate --graph --all
# Everything looks ok now; the "bad" commit is what I expect
# I can properly continue bisecting using "git bisect good"...

In this case the user, who knows how git bisect works, expected that
the second "git bisect bad" would fix the previous mistake made using
the first "git bisect bad".

If we make "git bisect bad" behave in another way we may break an
advanced user's expectation.

>>> I am not quite sure if I am correctly getting what you meant to say,
>>> but if you meant "only when --alternate is given, we should do the
>>> merge-base thing; we should keep losing the current 'bad' and
>>> replace it with the new one without the --alternate option", I would
>>> see that as an exercise of a bad taste.
>>
>> What I wanted to say is that if we change "git bisect bad <commitish>",
>> so that now it means "add a new bad commit" instead of the previous
>> "replace the current bad commit, if any, with this one", then experienced
>> users might see that change as a regression in the user interface and
>> it might even break scripts.
>
> Huh?
>
> Step back a bit.  The place you need to start from is to admit the
> fact that what "git bisect bad <committish>" currently does is
> broken.
>
> Try creating this history yourself
>
>     a---b---c---d---e---f
>
> and start bisection this way:
>
>     $ git bisect start f c
>     $ git bisect bad a
>
> Immediately after the second command, "git bisect" moans
>
>     Some good revs are not ancestor of the bad rev.
>     git bisect cannot work properly in this case.
>     Maybe you mistake good and bad revs?
>
> when it notices that the good rev (i.e. 'c') is no longer an
> ancestor of the 'bad', which now points at 'a'.
>
> But that is because "git bisect bad" _blindly_ moved 'bad' that used
> to point at 'f' to 'a', making a good rev (i.e. 'c') an ancestor of
> the bad rev, without even bothering to check.

Yeah, "git bisect bad" currently does what it is asked and then
complains when it looks like a mistake has been made.

You might see that as a bug. I am seeing that more as "git bisect"
expecting users to know what they are doing.

For example an advanced user might have realized that the first "git
bisect start f c" was completely rubish for some reason, and the "git
bisect bad a" might be a first step to fix that. (The next step might
then be deleting the "good" pointer...)

> Now, if we fixed this bug and made the bisect_state function more
> careful (namely, when accepting "bad", make sure it is not beyond
> any existing "good", or barf like the above, _without_ moving the
> bad pointer), the user interface and behaviour would be changed.  Is
> that a regression?  No, it is a usability fix and a progress.

Yeah, you might see that as a usability fix and a progress.

> Simply put, bisect_state function can become more careful and
> intelligent to help users.

Yeah, we can try to help users more, but doing that we might annoy
some advanced users,  who are used to the current way "git bisect"
works, and perhaps break some scripts.

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Philip Oakley]

From: "Junio C Hamano" <gitster@pobox.com>
Sent: Tuesday, March 17, 2015 6:33 PM
> Christian Couder <christian.couder@gmail.com> writes:
>
>> On Mon, Mar 16, 2015 at 10:05 PM, Junio C Hamano <gitster@pobox.com> 
>> wrote:
>>
>>> However, you can say "git bisect bad <rev>" (and "git bisect good
>>> <rev>" for that matter) on a rev that is unrelated to what the
>>> current bisection state is.  E.g. after you mark the child of 8 as
>>> "bad", the bisected graph would become
>>>
>>>    G...1---2---3---4---6---8---B
>>>
>>> and you would be offered to test somewhere in the middle, say, 4.
>>> But it is perfectly OK for you to respond with "git bisect bad 7",
>>> if you know 7 is bad.
>>>
>>> I _think_ the current code blindly overwrites the "bad" pointer,
>>> making the bisection state into this graph if you do so.
>>>
>>>    G...1---2---3---4
>>>                     \
>>>                      5---B
>>
>> Yes, we keep only one "bad" pointer.
>>
>>> This is very suboptimal.  The side branch 4-to-7 could be much
>>> longer than the original trunk 4-to-the-tip, in which case we would
>>> have made the suspect space _larger_, not smaller.
>>
>> Yes, but the user is supposed to not change the "bad" pointer for no
>> good reason.
>
> That is irrelevant, no?  Nobody is questioning that the user is
> supposed to judge if a commit is "good" or "bad" correctly.
[...]
>> and/or we could make "git bisect bad" accept any number of bad
>> commitishs.
>
> Yes, that is exactly what I meant.
>
> The way I understand the Philip's point is that the user may have
> a-priori knowledge that a breakage from the same cause appears in
> both tips of these branches.

Just to clarify; my initial query followed on from the way Junio had 
described it with having two tips which were known bad. I hadn't been 
aware of how the bisect worked on a DAG, so I wanted to fully understand 
Junio's comment regarding the expectation of a clean jump to commit 4 
(i.e. shouldn't we test commit 4 before assuming it's actually bad).  I 
was quite happy with a bisect of a linear list, but was unsure about how 
Git dissected DAGs.

I can easily see cases in more complicated product branching where users 
report intermittent operation for various product variants (especially 
if modular) and one wants to seek out those commits that introduced the 
behavious (which is typically some racy condition - otherwise it would 
be deterministic).

Given Junio's explantion with the two bad commits (on different legs) 
I'd sort of assumed it could be both user given, or algorithmically 
determined as part of the bisect.

> In such a case, we can start bisection
> after marking the merge-base of two 'bad' commits, e.g. 4 in the
> illustration in the message you are responding to, instead of
> including 5, 6, and 8 in the suspect set.
>
> You need to be careful, though.  An obvious pitfall is what you
> should do when there is a criss-cross merge.

You end up with possibly two (or more) merges being marked as the source 
of the bad behaviour, especially when racy ;-)

>
> Thanks.
> --

Hope that helps.
Philip

Re: [PATCH v4] rev-list: refuse --first-parent combined with --bisect

[Scott Schmit]

[-- Attachment #1: Type: text/plain, Size: 2726 bytes --]

On Mon, Mar 16, 2015 at 11:53:08AM -0700, Junio C Hamano wrote:
> Because the history is not linear in Git, bisection works by
> shrinking a subgraph of the history DAG that contains "yet to be
> tested, suspected to have introduced a badness" commits.  The
> subgraph is defined as anything reachable from _the_ "bad" commit
> (initially, the one you give to the command when you start) that are
> not reachable from any of the "good" commits.
> 
> Suppose you started from this graph.  Time flows left to right as
> usual.
> 
>   ---0---2---4---6---8---9
>       \             /
>        1---3---5---7
> 
> Then mark the initial good and bad commits as G and B.
> 
>   ---G---2---4---6---8---B
>       \             /
>        1---3---5---7
> 
> And imagine that you are asked to check 4, which turns out to be
> good.  We do not _move_ G to 4; we mark 4 as good, while keeping
> 0 also as good.
> 
>   ---G---2---G---6---8---B
>       \             /
>        1---3---5---7
> 
> And if you are next asked to check 5, and mark it as good, the graph
> will become like this:
> 
>   ---G---2---G---6---8---B
>       \             /
>        1---3---G---7
> 
> Of course, at this point, the subgraph of suspects are 6, 7, 8 and
> 9, and the subgraph no longer is affected by the fact that 0 is
> good.  But it is crucial to keep 0 marked as good in the step before
> this one, before you tested 5, as that is what allows us not having
> to test any ancestors of 0 at all.
> 
> Now, one may wonder why we need multiple "good" commits but we do
> not need multiple "bad" commits.  This comes from the nature of
> "bisection", which is a tool to find a _single_ breakage [*1*], and
> a fundamental assumption is that a breakage does not fix itself.
> 
> Hence, if you have a history that looks like this:
> 
> 
>    G...1---2---3---4---6---8---B
>                     \
>                      5---7---B
> 
> it follows that 4 must also be "bad".  It used to be good long time
> ago somewhere before 1, and somewhere along way on the history,
> there was a single breakage event that we are hunting for.  That
> single event cannot be 5, 6, 7 or 8 because breakage at say 5 would
> not explain why the tip of the upper branch is broken---its breakage
> has no way to propagate there.  The breakage must have happened at 4
> or before that commit.

But what if 7 & 8 are the same patch, cherry-picked?  Or nearly the same
patch, but with some conflict resolution?

Couldn't that lead to the case that 4, 5, and 6 are good, while 7 & 8
are bad?  Or does that violate the "single breakage" rule in a way that
might be too subtle for some users?

-- 
Scott Schmit

[-- Attachment #2: smime.p7s --]
[-- Type: application/x-pkcs7-signature, Size: 3891 bytes --]

[PATCH v5] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

rev-list --bisect is used by git bisect, but never together with
--first-parent. Because rev-list --bisect together with --first-parent
is not handled currently, and even leads to segfaults, refuse to use
both options together.

Because this is not supported, it makes little sense to use git log
--bisect --first parent either, because refs/heads/bad is not limited to
the first parent chain.

Helped-by: Junio C. Hamano <gitster@pobox.com>
Helped-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Kevin Daudt <me@ikke.info>
---
Updates since v4:

* Not only refusing rev-list --bisect --first-parent, but also log --bisect --first-parent

 Documentation/rev-list-options.txt | 7 ++++---
 revision.c                         | 3 +++
 t/t6000-rev-list-misc.sh           | 4 ++++
 3 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 4ed8587..e2de789 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -123,7 +123,8 @@ 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.
+	brought in to your history by such a merge. Cannot be
+	combined with --bisect.
 
 --not::
 	Reverses the meaning of the '{caret}' prefix (or lack thereof)
@@ -185,7 +186,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.
+	line. Cannot be combined with --first-parent.
 endif::git-rev-list[]
 
 --stdin::
@@ -566,7 +567,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.
+one. Cannot be combined with --first-parent.
 
 --bisect-vars::
 	This calculates the same as `--bisect`, except that refs in
diff --git a/revision.c b/revision.c
index 66520c6..ed3f6e9 100644
--- a/revision.c
+++ b/revision.c
@@ -2342,6 +2342,9 @@ 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"));
+
 	return left;
 }
 
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index 2602086..1f58b46 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -96,4 +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_done
-- 
2.3.2

Re: [PATCH v5] rev-list: refuse --first-parent combined with --bisect

[Junio C Hamano]

Kevin Daudt <me@ikke.info> writes:

> rev-list --bisect is used by git bisect, but never together with
> --first-parent. Because rev-list --bisect together with --first-parent
> is not handled currently, and even leads to segfaults, refuse to use
> both options together.
>
> Because this is not supported, it makes little sense to use git log
> --bisect --first parent either, because refs/heads/bad is not limited to
> the first parent chain.
>
> Helped-by: Junio C. Hamano <gitster@pobox.com>
> Helped-by: Eric Sunshine <sunshine@sunshineco.com>
> Signed-off-by: Kevin Daudt <me@ikke.info>
> ---

Thanks; will queue.

Re: [PATCH v5] rev-list: refuse --first-parent combined with --bisect

[Kevin Daudt]

On Thu, Mar 19, 2015 at 03:43:57PM -0700, Junio C Hamano wrote:
> Kevin Daudt <me@ikke.info> writes:
> 
> > rev-list --bisect is used by git bisect, but never together with
> > --first-parent. Because rev-list --bisect together with --first-parent
> > is not handled currently, and even leads to segfaults, refuse to use
> > both options together.
> >
> > Because this is not supported, it makes little sense to use git log
> > --bisect --first parent either, because refs/heads/bad is not limited to
> > the first parent chain.
> >
> > Helped-by: Junio C. Hamano <gitster@pobox.com>
> > Helped-by: Eric Sunshine <sunshine@sunshineco.com>
> > Signed-off-by: Kevin Daudt <me@ikke.info>
> > ---
> 
> Thanks; will queue.

Thank you too, for your thorough explanation in this.