[PATCH v6] Implement --first-parent for git rev-list --bisect

[Tiago Botelho]

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

Signed-off-by: Tiago Botelho 
---

This patch refactors **only** the tests according to the suggestions made by 
Junio in v5
more specifically 
`https://public-inbox.org/git/xmqqa7rhi40f@gitster-ct.c.googlers.com/`.

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

 bisect.c   | 43 ++
 bisect.h   |  1 +
 builtin/rev-list.c |  3 +++
 revision.c |  3 ---
 t/t6002-rev-list-bisect.sh | 58 ++
 5 files changed, 90 insertions(+), 18 deletions(-)

diff --git a/bisect.c b/bisect.c
index 4eafc8262..cb80f29c5 100644
--- a/bisect.c
+++ b/bisect.c
@@ -82,15 +82,16 @@ static inline void weight_set(struct commit_list *elem, int 
weight)
*((int*)(elem->item->util)) = weight;
 }
 
-static int count_interesting_parents(struct commit *commit)
+static int count_interesting_parents(struct commit *commit, unsigned 
bisect_flags)
 {
struct commit_list *p;
int count;
 
for (count = 0, p = commit->parents; p; p = p->next) {
-   if (p->item->object.flags & UNINTERESTING)
-   continue;
-   count++;
+   if (!(p->item->object.flags & UNINTERESTING))
+   count++;
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
}
return count;
 }
@@ -117,10 +118,10 @@ static inline int halfway(struct commit_list *p, int nr)
 }
 
 #if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
+#define show_list(a,b,c,d,e) do { ; } while (0)
 #else
 static void show_list(const char *debug, int counted, int nr,
- struct commit_list *list)
+ struct commit_list *list, unsigned bisect_flags)
 {
struct commit_list *p;
 
@@ -146,10 +147,14 @@ static void show_list(const char *debug, int counted, int 
nr,
else
fprintf(stderr, "---");
fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
-   for (pp = commit->parents; pp; pp = pp->next)
+   for (pp = commit->parents; pp; pp = pp->next) {
fprintf(stderr, " %.*s", 8,
oid_to_hex(&pp->item->object.oid));
 
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
+   }
+
subject_len = find_commit_subject(buf, &subject_start);
if (subject_len)
fprintf(stderr, " %.*s", subject_len, subject_start);
@@ -267,13 +272,13 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
unsigned flags = commit->object.flags;
 
p->item->util = &weights[n++];
-   switch (count_interesting_parents(commit)) {
+   switch (count_interesting_parents(commit, bisect_flags)) {
case 0:
if (!(flags & TREESAME)) {
weight_set(p, 1);
counted++;
show_list("bisection 2 count one",
- counted, nr, list);
+ counted, nr, list, bisect_flags);
}
/*
 * otherwise, it is known not to reach any
@@ -289,7 +294,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
}
}
 
-   show_list("bisection 2 initialize", counted, nr, list);
+   show_list("bisection 2 initialize", counted, nr, list, bisect_flags);
 
/*
 * If you have only one parent in the resulting set
@@ -319,7 +324,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
counted++;
}
 
-   show_list("bisection 2 count_distance", counted, nr, list);
+   show_list("bisection 2 count_distance", counted, nr, list, 
bisect_flags);
 
while (counted < nr) {
for (p = list; p; p = p->next) {
@@ -329,6 +334,11 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
if (0 <= weight(p))
continue;
for (q = p->item->parents; q; q = q->n

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

[Tiago Botelho]

On Fri, 29 Jun 2018 at 12:21, Johannes Schindelin
 wrote:
>
> Hi Junio,
>
> On Thu, 28 Jun 2018, Junio C Hamano wrote:
>
> > What I meant by "many separte grep calls" was to contrast these two
> > approaches:
> >
> >  * Have one typical output spelled out as "expect", take an output
> >from an actual run into "actual", make them comparable and then
> >do a compare (which does not use grep; it uses sort in the
> >"making comparable" phase)
> >
> >  * Not have any typical output, take an output from an actual run,
> >and have _code_ that inspects the output encode the rule over the
> >output (e.g. "these must exist" is inspected with many grep
> >invocations)
> >
> > Two things the "output must have 9 entries, and these 9 must be
> > mentioned" we see at the beginning of this message does not verify
> > are (1) exact dist value given to each of these entries and (2) the
> > order in which these entries appear in the output.  The latter is
> > something we document, and the test should cover.  The former does
> > not have to be cast in stone (i.e. I do not think it does not make a
> > difference to label the edge commits with dist=1 or dist=0 as long
> > as everything is consistent), but if there is no strong reason to
> > keep it possible for us to later change how the numbers are assigned,
> > I am OK if the test cast it in stone.
> >
> > Another reason (other than "many separate invocation of grep") to
> > favor the former approach (i.e. use real-looking expected output,
> > munge it and the real output into comparable forms and then compare)
> > is that it is easier to see what aspect of the output we care (and
> > we do not care) about.
> >
> > It is harder to see the omission of exact dist value and ordering of
> > entries in the outpu in the latter approach, and more importantly,
> > know if the omission was deliberate (e.g. it was merely an example)
> > or a mere mistake.
> >
> > With "using a real-looking expected output, make it and the actual
> > output comparable and then compare" approach, the aspects in the
> > output we choose not to care about will show in the "make them
> > comparable" munging.  If we do not care the exact dist values, there
> > would be something like s/dist=[0-9]*/dist=X/ to mask the exact
> > value before making the two comparable to see that the expect and
> > the actual files have the same entries.  If we still do care about
> > the entries are ordered by the dist values, there would be something
> > that sorts the entries with the actual dist values before doing that
> > masking to ensure if the order is correct.
>
> The problem here is of course that you *cannot* set the exact output
> in stone, because of sorting instabilities.
>
> So you have to play tricks to sort (twice, with different keys) the
> expected output and the actual output, to verify that all the expected
> commits are listed (and only those) and to verify that they are ordered by
> the distance, in descending order.
>
> And this trick, while it still makes the test correct and stable and yadda
> yadda, *also* makes this trick a lot less readable than my version. And
> therefore makes it more difficult to verify that your test actually does
> what it is supposed to do.
>
> Ciao,
> Dscho

Hello,

first of all I would like to thank all the feedback provided in this patch it
has truly helped me progress on my first contribution to git.

After looking through Junio's and Johannes's suggestions I believe that
the *only* test we should add will be something like:

-- snip --
test_expect_success '--first-parent --bisect-all lists correct revs' '
git rev-list --first-parent --bisect-all F..E >revs &&
test_line_count = 9 revs &&
for rev in E e1 e2 e3 e4 e5 e6 e7 e8
do
  grep "^$(git rev-parse $rev) " revs ||
  {
echo "$rev not shown" >&2 &&
return 1
  }
done &&
sed -e "s/.*(dist=\([0-9]*\)).*/\1/" revs >actual.dists &&
sort -r actual.dists >actual.dists.sorted &&
test_cmp actual.dists.sorted actual.dists
'
-- snap --

The only change I had to make was use -r in sort to
revert the sorting in `sort` otherwise we get it in
ascending order but the revs are provided in descending order.

Kind regards,
Tiago

[RFC PATCH v5] Implement --first-parent for git rev-list --bisect

[Tiago Botelho]

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

Signed-off-by: Tiago Botelho 
---

This patch resolves every issue with the unit tests. 

The bug detected by Junio regarding do_find_bisection() propagating 
a weight of -1 over to the child nodes ended up not being an 
issue since it cannot happen in practice, there will always be at 
least one UNINTERESTING parent which will propagate either a weight 
of 0 or 1 throughout the child nodes.

 bisect.c   | 43 ++
 bisect.h   |  1 +
 builtin/rev-list.c |  3 +++
 revision.c |  3 ---
 t/t6002-rev-list-bisect.sh | 58 ++
 5 files changed, 90 insertions(+), 18 deletions(-)

diff --git a/bisect.c b/bisect.c
index 4eafc8262..cb80f29c5 100644
--- a/bisect.c
+++ b/bisect.c
@@ -82,15 +82,16 @@ static inline void weight_set(struct commit_list *elem, int 
weight)
*((int*)(elem->item->util)) = weight;
 }
 
-static int count_interesting_parents(struct commit *commit)
+static int count_interesting_parents(struct commit *commit, unsigned 
bisect_flags)
 {
struct commit_list *p;
int count;
 
for (count = 0, p = commit->parents; p; p = p->next) {
-   if (p->item->object.flags & UNINTERESTING)
-   continue;
-   count++;
+   if (!(p->item->object.flags & UNINTERESTING))
+   count++;
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
}
return count;
 }
@@ -117,10 +118,10 @@ static inline int halfway(struct commit_list *p, int nr)
 }
 
 #if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
+#define show_list(a,b,c,d,e) do { ; } while (0)
 #else
 static void show_list(const char *debug, int counted, int nr,
- struct commit_list *list)
+ struct commit_list *list, unsigned bisect_flags)
 {
struct commit_list *p;
 
@@ -146,10 +147,14 @@ static void show_list(const char *debug, int counted, int 
nr,
else
fprintf(stderr, "---");
fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
-   for (pp = commit->parents; pp; pp = pp->next)
+   for (pp = commit->parents; pp; pp = pp->next) {
fprintf(stderr, " %.*s", 8,
oid_to_hex(&pp->item->object.oid));
 
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
+   }
+
subject_len = find_commit_subject(buf, &subject_start);
if (subject_len)
fprintf(stderr, " %.*s", subject_len, subject_start);
@@ -267,13 +272,13 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
unsigned flags = commit->object.flags;
 
p->item->util = &weights[n++];
-   switch (count_interesting_parents(commit)) {
+   switch (count_interesting_parents(commit, bisect_flags)) {
case 0:
if (!(flags & TREESAME)) {
weight_set(p, 1);
counted++;
show_list("bisection 2 count one",
- counted, nr, list);
+ counted, nr, list, bisect_flags);
}
/*
 * otherwise, it is known not to reach any
@@ -289,7 +294,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
}
}
 
-   show_list("bisection 2 initialize", counted, nr, list);
+   show_list("bisection 2 initialize", counted, nr, list, bisect_flags);
 
/*
 * If you have only one parent in the resulting set
@@ -319,7 +324,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
counted++;
}
 
-   show_list("bisection 2 count_distance", counted, nr, list);
+   show_list("bisection 2 count_distance", counted, nr, list, 
bisect_flags);
 
while (counted < nr) {
for (p = list; p; p = p->next) {
@@ -329,6 +334,11 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
if (0 <= weight(p))
continue;
for (q = p->item->parents; q; q = q->next) {
+   if ((bis

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

[Tiago Botelho]

On 28 May 2018 at 15:25, Junio C Hamano  wrote:

> Tiago Botelho  writes:

> > This will enable users to implement bisecting on first parents
> > which can be useful for when the commits from a feature branch
> > that we want to merge are not always tested.
> >
> > Signed-off-by: Tiago Botelho 
> > ---
> >
> > This patch adds all Junio's suggestions, namely do_find_bisection()
being
> > broken when assigning q's weight to p if in first parent mode and q
being
> > not UNINTERESTING and its weight still not being known.
> >
> > The graph displayed in the unit tests was also changed from being
top-bottom
> > to be left-right in order to keep it consistent with graphs in other
tests.
> >
> >  bisect.c   | 45
++---
> >  bisect.h   |  3 ++-
> >  builtin/rev-list.c |  3 +++
> >  revision.c |  3 ---
> >  t/t6002-rev-list-bisect.sh | 37 +
> >  5 files changed, 72 insertions(+), 19 deletions(-)

> > diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
> > index a66140803..774d9a4fd 100755
> > --- a/t/t6002-rev-list-bisect.sh
> > +++ b/t/t6002-rev-list-bisect.sh
> > @@ -263,4 +263,41 @@ test_expect_success 'rev-parse --bisect can
default to good/bad refs' '
> > ...
> > +test_output_expect_success "--bisect-all --first-parent" 'git rev-list
--bisect-all --first-parent FX ^A' < > +$(git rev-parse EX) (dist=1)
> > +$(git rev-parse D) (dist=1)
> > +$(git rev-parse FX) (dist=0)
> > +EOF
> > +
> >  test_done

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

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

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

> diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
> index 969e4e9e52..981198ae6e 100755
> --- a/t/t6000-rev-list-misc.sh
> +++ b/t/t6000-rev-list-misc.sh
> @@ -96,8 +96,8 @@ test_expect_success 'rev-list can show index objects' '
>  test_cmp expect actual
>   '

> -test_expect_success '--bisect and --first-parent can not be combined' '
> -   test_must_fail git rev-list --bisect --first-parent HEAD
> +test_expect_success '--bisect and --first-parent can now be combined' '
> +   git rev-list --bisect --first-parent HEAD
>   '

>   test_expect_success '--header shows a NUL after each commit' '

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

[Tiago Botelho]

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

Signed-off-by: Tiago Botelho 
---

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

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

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

diff --git a/bisect.c b/bisect.c
index 4eafc8262..e58cb8d62 100644
--- a/bisect.c
+++ b/bisect.c
@@ -33,6 +33,8 @@ static const char *term_good;
  *
  * We care just barely enough to avoid recursing for
  * non-merge entries.
+ *
+ * Note: This function does not support the usage --first-parent.
  */
 static int count_distance(struct commit_list *entry)
 {
@@ -82,15 +84,16 @@ static inline void weight_set(struct commit_list *elem, int 
weight)
*((int*)(elem->item->util)) = weight;
 }
 
-static int count_interesting_parents(struct commit *commit)
+static int count_interesting_parents(struct commit *commit, unsigned 
bisect_flags)
 {
struct commit_list *p;
int count;
 
for (count = 0, p = commit->parents; p; p = p->next) {
-   if (p->item->object.flags & UNINTERESTING)
-   continue;
-   count++;
+   if (!(p->item->object.flags & UNINTERESTING))
+   count++;
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
}
return count;
 }
@@ -117,10 +120,10 @@ static inline int halfway(struct commit_list *p, int nr)
 }
 
 #if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
+#define show_list(a,b,c,d,e) do { ; } while (0)
 #else
 static void show_list(const char *debug, int counted, int nr,
- struct commit_list *list)
+ struct commit_list *list, unsigned bisect_flags)
 {
struct commit_list *p;
 
@@ -146,10 +149,14 @@ static void show_list(const char *debug, int counted, int 
nr,
else
fprintf(stderr, "---");
fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
-   for (pp = commit->parents; pp; pp = pp->next)
+   for (pp = commit->parents; pp; pp = pp->next) {
fprintf(stderr, " %.*s", 8,
oid_to_hex(&pp->item->object.oid));
 
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
+   }
+
subject_len = find_commit_subject(buf, &subject_start);
if (subject_len)
fprintf(stderr, " %.*s", subject_len, subject_start);
@@ -267,13 +274,13 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
unsigned flags = commit->object.flags;
 
p->item->util = &weights[n++];
-   switch (count_interesting_parents(commit)) {
+   switch (count_interesting_parents(commit, bisect_flags)) {
case 0:
if (!(flags & TREESAME)) {
weight_set(p, 1);
counted++;
show_list("bisection 2 count one",
- counted, nr, list);
+ counted, nr, list, bisect_flags);
}
/*
 * otherwise, it is known not to reach any
@@ -289,7 +296,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
}
}
 
-   show_list("bisection 2 initialize", counted, nr, list);
+   show_list("bisection 2 initialize", counted, nr, list, bisect_flags);
 
/*
 * If you have only one parent in the resulting set
@@ -319,7 +326,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
counted++;
}
 
-   show_list("bisection 2 count_distance", counted, nr, list);
+   show_list("bisection 2 count_distance", counted, nr, list, 
bisect_flags);
 
while (counted < nr) {
for (p = list; p; p = p->next) {
@@ -329,6 +336,11 @@ static struct commit_list *do_find_bisection(struct 
commit_list 

[RFC PATCH v3 1/2] Implement --first-parent for git rev-list --bisect

[Tiago Botelho]

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

Signed-off-by: Tiago Botelho 
---
 bisect.c   | 53 +++--
 bisect.h   |  3 ++-
 builtin/rev-list.c |  3 +++
 revision.c |  3 ---
 4 files changed, 36 insertions(+), 26 deletions(-)

diff --git a/bisect.c b/bisect.c
index 4eafc8262..f43713574 100644
--- a/bisect.c
+++ b/bisect.c
@@ -34,7 +34,7 @@ static const char *term_good;
  * 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, unsigned bisect_flags)
 {
int nr = 0;
 
@@ -49,10 +49,10 @@ static int count_distance(struct commit_list *entry)
commit->object.flags |= COUNTED;
p = commit->parents;
entry = p;
-   if (p) {
+   if (p && !(bisect_flags & BISECT_FIRST_PARENT)) {
p = p->next;
while (p) {
-   nr += count_distance(p);
+   nr += count_distance(p, bisect_flags);
p = p->next;
}
}
@@ -82,15 +82,16 @@ static inline void weight_set(struct commit_list *elem, int 
weight)
*((int*)(elem->item->util)) = weight;
 }
 
-static int count_interesting_parents(struct commit *commit)
+static int count_interesting_parents(struct commit *commit, unsigned 
bisect_flags)
 {
struct commit_list *p;
int count;
 
for (count = 0, p = commit->parents; p; p = p->next) {
-   if (p->item->object.flags & UNINTERESTING)
-   continue;
-   count++;
+   if (!(p->item->object.flags & UNINTERESTING))
+   count++;
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
}
return count;
 }
@@ -117,10 +118,10 @@ static inline int halfway(struct commit_list *p, int nr)
 }
 
 #if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
+#define show_list(a,b,c,d,e) do { ; } while (0)
 #else
 static void show_list(const char *debug, int counted, int nr,
- struct commit_list *list)
+ struct commit_list *list, unsigned bisect_flags)
 {
struct commit_list *p;
 
@@ -146,10 +147,14 @@ static void show_list(const char *debug, int counted, int 
nr,
else
fprintf(stderr, "---");
fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
-   for (pp = commit->parents; pp; pp = pp->next)
+   for (pp = commit->parents; pp; pp = pp->next) {
fprintf(stderr, " %.*s", 8,
oid_to_hex(&pp->item->object.oid));
 
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
+   }
+
subject_len = find_commit_subject(buf, &subject_start);
if (subject_len)
fprintf(stderr, " %.*s", subject_len, subject_start);
@@ -267,13 +272,13 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
unsigned flags = commit->object.flags;
 
p->item->util = &weights[n++];
-   switch (count_interesting_parents(commit)) {
+   switch (count_interesting_parents(commit, bisect_flags)) {
case 0:
if (!(flags & TREESAME)) {
weight_set(p, 1);
counted++;
show_list("bisection 2 count one",
- counted, nr, list);
+ counted, nr, list, bisect_flags);
}
/*
 * otherwise, it is known not to reach any
@@ -289,7 +294,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
}
}
 
-   show_list("bisection 2 initialize", counted, nr, list);
+   show_list("bisection 2 initialize", counted, nr, list, bisect_flags);
 
/*
 * If you have only one parent in the resulting set
@@ -310,7 +315,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, bisect_flags));
  

[RFC PATCH v3 2/2] Add tests for rev-list --bisect* --first-parent

[Tiago Botelho]

---
 t/t6002-rev-list-bisect.sh | 39 +++
 1 file changed, 39 insertions(+)

diff --git a/t/t6002-rev-list-bisect.sh b/t/t6002-rev-list-bisect.sh
index a66140803..977c82157 100755
--- a/t/t6002-rev-list-bisect.sh
+++ b/t/t6002-rev-list-bisect.sh
@@ -263,4 +263,43 @@ test_expect_success 'rev-parse --bisect can default to 
good/bad refs' '
test_cmp expect.sorted actual.sorted
 '
 
+# We generate the following commit graph:
+#
+# A
+#/ \
+#   D   B
+#   |   |
+#   EX  C
+#\  /
+# FX
+
+test_expect_success 'setup' '
+  test_commit A &&
+  test_commit B &&
+  test_commit C &&
+  git reset --hard A &&
+  test_commit D &&
+  test_commit EX &&
+  test_merge FX C
+'
+
+test_output_expect_success "--bisect --first-parent" 'git rev-list --bisect 
--first-parent FX ^A' <

[RFC PATCH v2] Implement --first-parent for git rev-list --bisect.

[Tiago Botelho]

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

Signed-off-by: Tiago Botelho 
---

This patch is based on pu so that it can be on top of hn/bisect-first-parent,
tests will still need to be developed for this functionality.

 bisect.c   | 53 +++--
 bisect.h   |  1 +
 builtin/rev-list.c |  3 +++
 3 files changed, 35 insertions(+), 22 deletions(-)

diff --git a/bisect.c b/bisect.c
index 4eafc8262..f43713574 100644
--- a/bisect.c
+++ b/bisect.c
@@ -34,7 +34,7 @@ static const char *term_good;
  * 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, unsigned bisect_flags)
 {
int nr = 0;
 
@@ -49,10 +49,10 @@ static int count_distance(struct commit_list *entry)
commit->object.flags |= COUNTED;
p = commit->parents;
entry = p;
-   if (p) {
+   if (p && !(bisect_flags & BISECT_FIRST_PARENT)) {
p = p->next;
while (p) {
-   nr += count_distance(p);
+   nr += count_distance(p, bisect_flags);
p = p->next;
}
}
@@ -82,15 +82,16 @@ static inline void weight_set(struct commit_list *elem, int 
weight)
*((int*)(elem->item->util)) = weight;
 }
 
-static int count_interesting_parents(struct commit *commit)
+static int count_interesting_parents(struct commit *commit, unsigned 
bisect_flags)
 {
struct commit_list *p;
int count;
 
for (count = 0, p = commit->parents; p; p = p->next) {
-   if (p->item->object.flags & UNINTERESTING)
-   continue;
-   count++;
+   if (!(p->item->object.flags & UNINTERESTING))
+   count++;
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
}
return count;
 }
@@ -117,10 +118,10 @@ static inline int halfway(struct commit_list *p, int nr)
 }
 
 #if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
+#define show_list(a,b,c,d,e) do { ; } while (0)
 #else
 static void show_list(const char *debug, int counted, int nr,
- struct commit_list *list)
+ struct commit_list *list, unsigned bisect_flags)
 {
struct commit_list *p;
 
@@ -146,10 +147,14 @@ static void show_list(const char *debug, int counted, int 
nr,
else
fprintf(stderr, "---");
fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
-   for (pp = commit->parents; pp; pp = pp->next)
+   for (pp = commit->parents; pp; pp = pp->next) {
fprintf(stderr, " %.*s", 8,
oid_to_hex(&pp->item->object.oid));
 
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
+   }
+
subject_len = find_commit_subject(buf, &subject_start);
if (subject_len)
fprintf(stderr, " %.*s", subject_len, subject_start);
@@ -267,13 +272,13 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
unsigned flags = commit->object.flags;
 
p->item->util = &weights[n++];
-   switch (count_interesting_parents(commit)) {
+   switch (count_interesting_parents(commit, bisect_flags)) {
case 0:
if (!(flags & TREESAME)) {
weight_set(p, 1);
counted++;
show_list("bisection 2 count one",
- counted, nr, list);
+ counted, nr, list, bisect_flags);
}
/*
 * otherwise, it is known not to reach any
@@ -289,7 +294,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
}
}
 
-   show_list("bisection 2 initialize", counted, nr, list);
+   show_list("bisection 2 initialize", counted, nr, list, bisect_flags);
 
/*
 * If you have only one parent in the resulting set
@@ -310,7 +315,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
continue;
if (weight(p) != -2)
continue;
-   weig

[PATCH] Implement --first-parent for git rev-list --bisect

[Tiago Botelho]

---
 bisect.c   | 53 +++--
 bisect.h   |  1 +
 builtin/rev-list.c |  3 +++
 3 files changed, 35 insertions(+), 22 deletions(-)

diff --git a/bisect.c b/bisect.c
index 4eafc8262..f43713574 100644
--- a/bisect.c
+++ b/bisect.c
@@ -34,7 +34,7 @@ static const char *term_good;
  * 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, unsigned bisect_flags)
 {
int nr = 0;
 
@@ -49,10 +49,10 @@ static int count_distance(struct commit_list *entry)
commit->object.flags |= COUNTED;
p = commit->parents;
entry = p;
-   if (p) {
+   if (p && !(bisect_flags & BISECT_FIRST_PARENT)) {
p = p->next;
while (p) {
-   nr += count_distance(p);
+   nr += count_distance(p, bisect_flags);
p = p->next;
}
}
@@ -82,15 +82,16 @@ static inline void weight_set(struct commit_list *elem, int 
weight)
*((int*)(elem->item->util)) = weight;
 }
 
-static int count_interesting_parents(struct commit *commit)
+static int count_interesting_parents(struct commit *commit, unsigned 
bisect_flags)
 {
struct commit_list *p;
int count;
 
for (count = 0, p = commit->parents; p; p = p->next) {
-   if (p->item->object.flags & UNINTERESTING)
-   continue;
-   count++;
+   if (!(p->item->object.flags & UNINTERESTING))
+   count++;
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
}
return count;
 }
@@ -117,10 +118,10 @@ static inline int halfway(struct commit_list *p, int nr)
 }
 
 #if !DEBUG_BISECT
-#define show_list(a,b,c,d) do { ; } while (0)
+#define show_list(a,b,c,d,e) do { ; } while (0)
 #else
 static void show_list(const char *debug, int counted, int nr,
- struct commit_list *list)
+ struct commit_list *list, unsigned bisect_flags)
 {
struct commit_list *p;
 
@@ -146,10 +147,14 @@ static void show_list(const char *debug, int counted, int 
nr,
else
fprintf(stderr, "---");
fprintf(stderr, " %.*s", 8, oid_to_hex(&commit->object.oid));
-   for (pp = commit->parents; pp; pp = pp->next)
+   for (pp = commit->parents; pp; pp = pp->next) {
fprintf(stderr, " %.*s", 8,
oid_to_hex(&pp->item->object.oid));
 
+   if (bisect_flags & BISECT_FIRST_PARENT)
+   break;
+   }
+
subject_len = find_commit_subject(buf, &subject_start);
if (subject_len)
fprintf(stderr, " %.*s", subject_len, subject_start);
@@ -267,13 +272,13 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
unsigned flags = commit->object.flags;
 
p->item->util = &weights[n++];
-   switch (count_interesting_parents(commit)) {
+   switch (count_interesting_parents(commit, bisect_flags)) {
case 0:
if (!(flags & TREESAME)) {
weight_set(p, 1);
counted++;
show_list("bisection 2 count one",
- counted, nr, list);
+ counted, nr, list, bisect_flags);
}
/*
 * otherwise, it is known not to reach any
@@ -289,7 +294,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
}
}
 
-   show_list("bisection 2 initialize", counted, nr, list);
+   show_list("bisection 2 initialize", counted, nr, list, bisect_flags);
 
/*
 * If you have only one parent in the resulting set
@@ -310,7 +315,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, bisect_flags));
clear_distance(list);
 
/* Does it happen to be at exactly half-way? */
@@ -319,7 +324,7 @@ static struct commit_list *do_find_bisection(struct 
commit_list *list,
counted++;
}
 
-   show_list("bisection 2 count_distance", counted, nr, list);
+   show_list("bisection 2 count_distance", counted, nr, list, 
bisect_flags);
 
while (counted < nr) {
fo

Re: [PATCH] Create '--merges-only' option for 'git bisect'

[Tiago Botelho]

On Mon, Apr 30, 2018 at 12:31 PM, Johannes Schindelin
 wrote:
> Hi Tiago,
>
>> > On Thu, 12 Apr 2018, Tiago Botelho wrote:
>> >
>> >> On Thu, Apr 12, 2018 at 9:58 AM, Christian Couder
>> >>  wrote:
>> >> > On Thu, Apr 12, 2018 at 9:49 AM, Harald Nordgren
>> >> >  wrote:
>> >> >> I think it looks similar. But if I'm reading that thread correctly
>> >> >> then there was never a patch created, right?
>> >> >
>> >> > (It is customary on this mailing list to reply after the sentences we
>> >> > reply to. We don't "top post".)
>> >> >
>> >> > On the GSoC idea pages (like https://git.github.io/SoC-2018-Ideas/) we
>> >> > have been suggesting "Implement git bisect --first-parent" and there
>> >> > are the following related links:
>> >> >
>> >> > https://public-inbox.org/git/2015030405.ga9...@peff.net/
>> >> > https://public-inbox.org/git/4d3cddf9.6080...@intel.com/
>> >> >
>> >> > Tiago in Cc also tried at a recent London hackathon to implement it
>> >> > and came up with the following:
>> >> >
>> >> > https://github.com/tiagonbotelho/git/pull/1/files
>> >> >
>> >> > I tried to help him by reworking his commit in the following branch:
>> >> >
>> >> > https://github.com/chriscool/git/commits/myfirstparent
>> >>
>> >> Thank you for the cc Christian, I’ve been quite busy and was not able
>> >> to work on the PR for quite some time.
>> >>
>> >> I intended to pick it back up again next week. If it is ok with
>> >> Harald I would love to finish the PR that I started, since it is
>> >> quite close to being finished (I think it was just specs missing if I
>> >> am not mistaken).
>
> It is now well after "next week". Are there any news? Or could you unblock
> Harald by stating that you won't come back to it any time soon (in
> particular since the PR is not quite as finished from my reading as you
> made it sound...)?
>
> Ciao,
> Johannes

I've been working on the feature for the past week
https://github.com/tiagonbotelho/git/commit/709e2e248ebfb1deab12fd7d3da4611002dfaf86#diff-118df990fd68a0929bca5441fea06fc7

I have some comments sent by Christian I plan on fixing this week

Thank you,

-- 
Tiago Botelho

Re: [PATCH] Create '--merges-only' option for 'git bisect'

[Tiago Botelho]

On Thu, Apr 12, 2018 at 12:53 PM, Johannes Schindelin
 wrote:
> Hi Tiago,
>
> On Thu, 12 Apr 2018, Tiago Botelho wrote:
>
>> On Thu, Apr 12, 2018 at 9:58 AM, Christian Couder
>>  wrote:
>> > On Thu, Apr 12, 2018 at 9:49 AM, Harald Nordgren
>> >  wrote:
>> >> I think it looks similar. But if I'm reading that thread correctly
>> >> then there was never a patch created, right?
>> >
>> > (It is customary on this mailing list to reply after the sentences we
>> > reply to. We don't "top post".)
>> >
>> > On the GSoC idea pages (like https://git.github.io/SoC-2018-Ideas/) we
>> > have been suggesting "Implement git bisect --first-parent" and there
>> > are the following related links:
>> >
>> > https://public-inbox.org/git/2015030405.ga9...@peff.net/
>> > https://public-inbox.org/git/4d3cddf9.6080...@intel.com/
>> >
>> > Tiago in Cc also tried at a recent London hackathon to implement it
>> > and came up with the following:
>> >
>> > https://github.com/tiagonbotelho/git/pull/1/files
>> >
>> > I tried to help him by reworking his commit in the following branch:
>> >
>> > https://github.com/chriscool/git/commits/myfirstparent
>>
>> Thank you for the cc Christian, I’ve been quite busy and was not able
>> to work on the PR for quite some time.
>>
>> I intended to pick it back up again next week. If it is ok with Harald
>> I would love to finish the PR that I started,
>> since it is quite close to being finished (I think it was just specs
>> missing if I am not mistaken).
>
> That looks promising. Just like I suggested to Harald in another reply
> [*1*] on this thread, you probably want to use `int flags` instead, and
> turn `find_all` into BISECT_FIND_ALL in a preparatory commit.
>
> Also, you will definitely want to add a test. Again, my reply to Harald
> [*1*] should give you a head start there... You will want to imitate the
> test case I outlined there, maybe something like:
>
> # A - B - C - F
> #   \   \   /   \
> # D - E - G - H
>
> [... 'setup' as in my mail to Harald ...]
>
> test_expect_success '--first-parent' '
> write_script find-e.sh <<-\EOF &&
> case "$(git show --format=%s -s)" in
> B|C|F) ;; # first parent lineage: okay
> *) git show -s --oneline HEAD >unexpected;;
> esac
> # detect whether we are "before" or "after" E
> test ! -f E.t
> EOF
>
> git bisect start --first-parent HEAD A &&
> git bisect run ./find-e.sh >actual &&
> test_path_is_missing unexpected &&
> grep "$(git rev-parse F) is the first bad commit" actual
> '
>
> Also, Tiago, reading through your patch (as on chriscool/git; do you have
> your own fork? That would make it much easier to collaborate with you by
> offering PRs), it looks more straight-forward than editing the commit_list
> after the fact and adding magic weights ;-)
>
> Except for one thing. I wonder why `bisect_next_all()` does not set
> revs.first_parent_only after calling `bisect_rev_setup()`? You would still
> need the changes in `count_distance()`, as it performs its own commit
> graph traversal, but there is no need to enumerate too many commits in the
> first place, right?
>
> Harald, maybe --merges-only can be implemented on top of --first-parent,
> with the `int flags` change I suggested?
>
> Ciao,
> Johannes
>
> Footnote *1*:
> https://public-inbox.org/git/nycvar.qro.7.76.6.1804121143120...@zvavag-6oxh6da.rhebcr.pbec.zvpebfbsg.pbz/

Hi Johannes,

Thank you for the pointers!

I do have my own fork, you can see it here:
https://github.com/tiagonbotelho/git/pull/1/commits
which applies the changes Chris made to my first draft of the solution.

I still have to add him as co-author of that commit.

Cheers,
Tiago Botelho

Re: [PATCH] Create '--merges-only' option for 'git bisect'

[Tiago Botelho]

On Thu, Apr 12, 2018 at 9:58 AM, Christian Couder
 wrote:
> On Thu, Apr 12, 2018 at 9:49 AM, Harald Nordgren
>  wrote:
>> I think it looks similar. But if I'm reading that thread correctly
>> then there was never a patch created, right?
>
> (It is customary on this mailing list to reply after the sentences we
> reply to. We don't "top post".)
>
> On the GSoC idea pages (like https://git.github.io/SoC-2018-Ideas/) we
> have been suggesting "Implement git bisect --first-parent" and there
> are the following related links:
>
> https://public-inbox.org/git/2015030405.ga9...@peff.net/
> https://public-inbox.org/git/4d3cddf9.6080...@intel.com/
>
> Tiago in Cc also tried at a recent London hackathon to implement it
> and came up with the following:
>
> https://github.com/tiagonbotelho/git/pull/1/files
>
> I tried to help him by reworking his commit in the following branch:
>
> https://github.com/chriscool/git/commits/myfirstparent

Thank you for the cc Christian, I’ve been quite busy and was not able
to work on the PR for quite some time.

I intended to pick it back up again next week. If it is ok with Harald
I would love to finish the PR that I started,
since it is quite close to being finished (I think it was just specs
missing if I am not mistaken).

Kind regards,

Tiago Botelho