git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH 1/3] rev-list: allow bisect and first-parent flags

From
Junio C Hamano <gitster@pobox.com>
Date
Jul 28, 2020, 20:23 UTC
Message-ID
<xmqq4kpre6cl.fsf@gitster.c.googlers.com>
In-Reply-To
<25263842832eeb09769b55cec025978b5f361eca.1595951056.git.gitgitgadget@gmail.com>
"Aaron Lipman via GitGitGadget" <gitgitgadget@gmail.com> writes:
Show 8 quoted lines
> 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.
Show 26 quoted lines
> 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;
>  }
Show 17 quoted lines
> -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.

Show 22 quoted lines
> @@ -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?
Show 12 quoted lines
> @@ -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.
Show 6 quoted lines
>  			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.
Previous: Aaron Lipman via GitGitGadgetNext: Junio C Hamano
Message 3 of 42 in “Introduce --first-parent flag for git bisect”
  1. 0/3 Introduce --first-parent flag for git bisectAaron Lipman via GitGitGadget, Jul 28, 2020
  2. 1/3 rev-list: allow bisect and first-parent flagsAaron Lipman via GitGitGadget, Jul 28, 2020
  3. Junio C HamanoJul 28, 2020
  4. Junio C HamanoJul 28, 2020
  5. 2/3 bisect: introduce first-parent flagAaron Lipman via GitGitGadget, Jul 28, 2020
  6. 3/3 bisect: combine args passed to find_bisection()Aaron Lipman via GitGitGadget, Jul 28, 2020
  7. 0/3 Introduce --first-parent flag for git bisectAaron Lipman, Jul 30, 2020
  8. 1/3 rev-list: allow bisect and first-parent flagsAaron Lipman, Jul 30, 2020
  9. 2/3 bisect: introduce first-parent flagAaron Lipman, Jul 30, 2020
  10. Junio C HamanoJul 30, 2020
  11. 3/3 bisect: combine args passed to find_bisection()Aaron Lipman, Jul 30, 2020
  12. Junio C HamanoJul 30, 2020
  13. Junio C HamanoJul 30, 2020
  14. 0/4 Introduce --first-parent flag for git bisectAaron Lipman, Aug 1, 2020
  15. 1/4 rev-list: allow bisect and first-parent flagsAaron Lipman, Aug 1, 2020
  16. 3/4 bisect: combine args passed to find_bisection()Aaron Lipman, Aug 1, 2020
  17. Martin ÅgrenAug 1, 2020
  18. 4/4 bisect: consistent style for git bisect run testsAaron Lipman, Aug 1, 2020
  19. Martin ÅgrenAug 1, 2020
  20. 2/4 bisect: introduce first-parent flagAaron Lipman, Aug 1, 2020
  21. Junio C HamanoAug 1, 2020
  22. 0/5 Introduce --first-parent flag for git bisectAaron Lipman, Aug 4, 2020
  23. 1/5 t6030: modernize "git bisect run" testsAaron Lipman, Aug 4, 2020
  24. Christian CouderAug 5, 2020
  25. 2/5 rev-list: allow bisect and first-parent flagsAaron Lipman, Aug 4, 2020
  26. Eric SunshineAug 5, 2020
  27. 3/5 cmd_bisect__helper: defer parsing no-checkout flagAaron Lipman, Aug 4, 2020
  28. 4/5 bisect: introduce first-parent flagAaron Lipman, Aug 4, 2020
  29. 5/5 bisect: combine args passed to find_bisection()Aaron Lipman, Aug 4, 2020
  30. Junio C HamanoAug 4, 2020
  31. Christian CouderAug 5, 2020
  32. Junio C HamanoAug 7, 2020
  33. Eric SunshineAug 7, 2020
  34. Junio C HamanoAug 7, 2020
  35. Eric SunshineAug 7, 2020
  36. Martin ÅgrenAug 5, 2020
  37. 0/5 Introduce --first-parent flag for git bisectAaron Lipman, Aug 7, 2020
  38. 1/5 t6030: modernize "git bisect run" testsAaron Lipman, Aug 7, 2020
  39. 2/5 rev-list: allow bisect and first-parent flagsAaron Lipman, Aug 7, 2020
  40. 3/5 cmd_bisect__helper: defer parsing no-checkout flagAaron Lipman, Aug 7, 2020
  41. 5/5 bisect: combine args passed to find_bisection()Aaron Lipman, Aug 7, 2020
  42. 4/5 bisect: introduce first-parent flagAaron Lipman, Aug 7, 2020

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.