Git Mailing List Archive on lore.kernel.org
 help / color / 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
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 index

Thread overview: 42+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-07-28 15:44 [PATCH 0/3] Introduce --first-parent flag for git bisect Aaron Lipman via GitGitGadget
2020-07-28 15:44 ` [PATCH 1/3] rev-list: allow bisect and first-parent flags Aaron Lipman via GitGitGadget
2020-07-28 20:23   ` Junio C Hamano [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

* 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 \
    /path/to/YOUR_REPLY

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

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

Git Mailing List Archive on lore.kernel.org

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

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

Example config snippet for mirrors

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


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