git@vger.kernel.org list mirror (unofficial, one of many)
 help / color / mirror / code / Atom feed
From: Junio C Hamano <gitster@pobox.com>
To: "Aaron Lipman via GitGitGadget" <gitgitgadget@gmail.com>
Cc: git@vger.kernel.org, Aaron Lipman <alipman88@gmail.com>
Subject: Re: [PATCH 1/3] rev-list: allow bisect and first-parent flags
Date: Tue, 28 Jul 2020 13:23:54 -0700	[thread overview]
Message-ID: <xmqq4kpre6cl.fsf@gitster.c.googlers.com> (raw)
In-Reply-To: <25263842832eeb09769b55cec025978b5f361eca.1595951056.git.gitgitgadget@gmail.com> (Aaron Lipman via GitGitGadget's message of "Tue, 28 Jul 2020 15:44:14 +0000")

"Aaron Lipman via GitGitGadget" <gitgitgadget@gmail.com> writes:

> From: Aaron Lipman <alipman88@gmail.com>
>
> Add first_parent_only parameter to find_bisection(), removing the
> barrier that prevented combining the --bisect and --first-parent flags
> when using git rev-list
>
> Signed-off-by: Aaron Lipman <alipman88@gmail.com>
> Based-on-patch-by: Tiago Botelho <tiagonbotelho@hotmail.com>

In chronological order, please.

> diff --git a/bisect.c b/bisect.c
> index d5e830410f..762f68c8e9 100644
> --- a/bisect.c
> +++ b/bisect.c
> @@ -37,7 +37,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, int first_parent_only)
>  {
>  	int nr = 0;
>  
> @@ -52,10 +52,10 @@ static int count_distance(struct commit_list *entry)
>  		commit->object.flags |= COUNTED;
>  		p = commit->parents;
>  		entry = p;
> -		if (p) {
> +		if (p && !first_parent_only) {
>  			p = p->next;
>  			while (p) {
> -				nr += count_distance(p);
> +				nr += count_distance(p, first_parent_only);
>  				p = p->next;
>  			}
>  		}

If you are running a first-parent-only bisection, by default, each
commit in the "goodness not yet known" region is treated as a single
parent commit for the purpose of bisection.  As do_find_bisection()
avoids the cost of calling stupid-and-expensive count_distance() by
treating such a single-strand-of-pearls specially, wouldn't it be a
BUG() if this funtion is called under first_parent_only mode in the
first place?

> @@ -88,15 +88,16 @@ static inline void weight_set(struct commit_list *elem, int weight)
>  	**commit_weight_at(&commit_weight, elem->item) = weight;
>  }


> -static int count_interesting_parents(struct commit *commit)
> +static int count_interesting_parents(struct commit *commit, int first_parent_only)
>  {
>  	struct commit_list *p;
>  	int count;
>  
>  	for (count = 0, p = commit->parents; p; p = p->next) {
> -		if (p->item->object.flags & UNINTERESTING)
> -			continue;
> -		count++;
> +		if (!(p->item->object.flags & UNINTERESTING))
> +			count++;
> +		if (first_parent_only)
> +			break;
>  	}
>  	return count;
>  }

Any merge will be checked for interesting-ness of its first parent;
there is either zero or one interesting parent and no other case
under first-parent-only.  OK.

> @@ -259,7 +260,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
>   */
>  static struct commit_list *do_find_bisection(struct commit_list *list,
>  					     int nr, int *weights,
> -					     int find_all)
> +					     int find_all, int first_parent_only)
>  {
>  	int n, counted;
>  	struct commit_list *p;
> @@ -271,7 +272,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  		unsigned flags = commit->object.flags;
>  
>  		*commit_weight_at(&commit_weight, p->item) = &weights[n++];
> -		switch (count_interesting_parents(commit)) {
> +		switch (count_interesting_parents(commit, first_parent_only)) {
>  		case 0:
>  			if (!(flags & TREESAME)) {
>  				weight_set(p, 1);
> @@ -314,7 +315,7 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  			continue;
>  		if (weight(p) != -2)
>  			continue;

If count-interesting-parents can never be 2 or more, you will never
see weight(p) == -2 (see the switch statement in the previous hunk).

So it your first-parent-only mode allowed this continue not to
trigger, you have a BUG(), I think.

> -		weight_set(p, count_distance(p));
> +		weight_set(p, count_distance(p, first_parent_only));

Hence, you do not need to touch count_distance() at all, no?

> @@ -330,13 +331,21 @@ static struct commit_list *do_find_bisection(struct commit_list *list,
>  			struct commit_list *q;
>  			unsigned flags = p->item->object.flags;
>  
> +			/* if commit p has already been weighted, continue. */
>  			if (0 <= weight(p))
>  				continue;
> +
> +			/*
> +			 * otherwise, find the first interesting
> +			 * already-weighted parent of p and store as q.
> +			 */

Unnecessary changes above.

>  			for (q = p->item->parents; q; q = q->next) {
> -				if (q->item->object.flags & UNINTERESTING)
> -					continue;
> -				if (0 <= weight(q))
> +				if (!(q->item->object.flags & UNINTERESTING) && 0 <= weight(q)) {
> +					break;

Overlong line.  Fold it after "&&", like this:

				if (!(q->item->object.flags & UNINTERESTING) &&
				    0 <= weight(q)) {

What is this change about?

Ah, if the first parent is uninteresting, we do not want to
continue, but with the original loop, we may go on and check
q->next.  We just want to break out of the loop instead.

I strongly suspect that

			for (q = p->item->parents;
			     q;
			     q = first_parent_only ? NULL : q->next) {

without any change inside the loop is much easier to reason about.
We follow exactly the same logic as the usual case.  We just pretend
that all commits have only one single parent which is the first one.

Thanks.

  reply	other threads:[~2020-07-28 20:24 UTC|newest]

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

Reply instructions:

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

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

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

  List information: http://vger.kernel.org/majordomo-info.html

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

  git send-email \
    --in-reply-to=xmqq4kpre6cl.fsf@gitster.c.googlers.com \
    --to=gitster@pobox.com \
    --cc=alipman88@gmail.com \
    --cc=git@vger.kernel.org \
    --cc=gitgitgadget@gmail.com \
    --subject='Re: [PATCH 1/3] rev-list: allow bisect and first-parent flags' \
    /path/to/YOUR_REPLY

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

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

Code repositories for project(s) associated with this inbox:

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).