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

From: Junio C Hamano <gitster@pobox.com>
Date: Apr 15, 2016, 22:47 UTC
Message-ID: <xmqqtwj27alk.fsf@gitster.mtv.corp.google.com>
In-Reply-To: <1460294354-7031-20-git-send-email-s-beyer@gmx.net>

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.

Show 14 quoted lines

> 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

Show 12 quoted lines

> +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.