Re: [PATCH v2 19/21] bisect: use a bottom-up traversal to find relevant weights

[Junio C Hamano <gitster@pobox.com>]

Stephan Beyer <s-beyer@gmx.net> writes:

> The idea is to reverse the DAG and perform a traversal
> starting on all sources of the reversed DAG.

Please clarify what you mean by "sources" here.  Those who read log
message in Git context would know that you mean the commit graph by
"DAG", and "reversed DAG" means "having reverse linkage that lets
you find children given a parent", so "DAG" does not need such a
clarification.

> We walk from the bottom commits, incrementing the weight while
> walking on a part of the graph that is single strand of pearls,
> or doing the "count the reachable ones the hard way" using
> compute_weight() when we hit a merge commit.

Makes sense.  So instead of "all sources", you can say "perform a
traversal starting from the bottom commits, going from parent to its
children".

> A traversal ends when the computed weight is falling or halfway.
> This way, commits with too high weight to be relevant are never
> visited (and their weights are never computed).

Yup, beautiful.

> diff --git a/bisect.c b/bisect.c
> index c6bad43..9487ba9 100644
> --- a/bisect.c
> +++ b/bisect.c
> @@ -30,6 +30,9 @@ static unsigned marker;
>  struct node_data {
>  	int weight;
>  	unsigned marked;
> +	unsigned parents;
> +	unsigned visited : 1;
> +	struct commit_list *children;
>  };
>  
>  #define DEBUG_BISECT 0

> +static inline void commit_list_insert_unique(struct commit *item,
> +				      struct commit_list **list)
> +{
> +	if (!*list || item < (*list)->item) /* empty list or item will be first */
> +		commit_list_insert(item, list);
> +	else if (item != (*list)->item) { /* item will not be first or not inserted */
> +		struct commit_list *p = *list;
> +		for (; p->next && p->next->item < item; p = p->next);
> +		if (!p->next || item != p->next->item) /* not already inserted */
> +			commit_list_insert(item, &p->next);
> +	}
> +}

Hmmmmmmmmmmmmmmmmmmmmmmmmmmmm.

When you have two commits, struct commit *one, and struct commit
*two, is it safe to do a pointer comparison for ordering?

I know it would work in practice, but I am worried about language
lawyers (and possibly static analysis tools) barking at this code.