Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

["René Scharfe" <l.s.r@web.de>]

Am 28.06.2018 um 14:31 schrieb Derrick Stolee via GitGitGadget:
> diff --git a/commit-reach.c b/commit-reach.c
> index c58e50fbb..ac132c8e4 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -513,65 +513,88 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
>  	return is_descendant_of(commit, list);
>  }
>  
> -int reachable(struct commit *from, int with_flag, int assign_flag,
> -	      time_t min_commit_date)
> +static int compare_commits_by_gen(const void *_a, const void *_b)
>  {
> -	struct prio_queue work = { compare_commits_by_commit_date };
> +	const struct commit *a = (const struct commit *)_a;
> +	const struct commit *b = (const struct commit *)_b;

This cast is bogus.  QSORT gets handed a struct commit **, i.e. an array
of pointers, and qsort(1) passes references to those pointers to the
compare function, and not the pointer values.

As a result it's unlikely that the array is sorted in the intended
order.  Given that, a silly question: Is sorting even necessary here?

Anyway, the patch below should fix it.

>  
> -	prio_queue_put(&work, from);
> -	while (work.nr) {
> -		struct commit_list *list;
> -		struct commit *commit = prio_queue_get(&work);
> -
> -		if (commit->object.flags & with_flag) {
> -			from->object.flags |= assign_flag;
> -			break;
> -		}
> -		if (!commit->object.parsed)
> -			parse_object(the_repository, &commit->object.oid);
> -		if (commit->object.flags & REACHABLE)
> -			continue;
> -		commit->object.flags |= REACHABLE;
> -		if (commit->date < min_commit_date)
> -			continue;
> -		for (list = commit->parents; list; list = list->next) {
> -			struct commit *parent = list->item;
> -			if (!(parent->object.flags & REACHABLE))
> -				prio_queue_put(&work, parent);
> -		}
> -	}
> -	from->object.flags |= REACHABLE;
> -	clear_commit_marks(from, REACHABLE);
> -	clear_prio_queue(&work);
> -	return (from->object.flags & assign_flag);
> +	if (a->generation < b->generation)
> +		return -1;
> +	if (a->generation > b->generation)
> +		return 1;
> +	return 0;
>  }
>  
>  int can_all_from_reach_with_flag(struct object_array *from,
>  				 int with_flag, int assign_flag,
> -				 time_t min_commit_date)
> +				 time_t min_commit_date,
> +				 uint32_t min_generation)
>  {
> +	struct commit **list = NULL;
>  	int i;
> +	int result = 1;
>  
> +	ALLOC_ARRAY(list, from->nr);
>  	for (i = 0; i < from->nr; i++) {
> -		struct object *from_one = from->objects[i].item;
> +		list[i] = (struct commit *)from->objects[i].item;
>  
> -		if (from_one->flags & assign_flag)
> -			continue;
> -		from_one = deref_tag(the_repository, from_one, "a from object", 0);
> -		if (!from_one || from_one->type != OBJ_COMMIT) {
> -			/* no way to tell if this is reachable by
> -			 * looking at the ancestry chain alone, so
> -			 * leave a note to ourselves not to worry about
> -			 * this object anymore.
> -			 */
> -			from->objects[i].item->flags |= assign_flag;
> -			continue;
> -		}
> -		if (!reachable((struct commit *)from_one, with_flag, assign_flag,
> -			       min_commit_date))
> +		parse_commit(list[i]);
> +
> +		if (list[i]->generation < min_generation)
>  			return 0;
>  	}
> -	return 1;
> +
> +	QSORT(list, from->nr, compare_commits_by_gen);

-- >8 --
Subject: [PATCH] commit-reach: fix cast in compare_commits_by_gen()

The elements of the array to be sorted are commit pointers, so the
comparison function gets handed references to these pointers, not
pointers to commit objects.  Cast to the right type and dereference
once to correctly get the commit reference.

Found using Clang's ASan and t5500.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
Has this patch a performance impact?

 commit-reach.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 00e5ceee6f..2f5e592d16 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -529,8 +529,8 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
 
 static int compare_commits_by_gen(const void *_a, const void *_b)
 {
-	const struct commit *a = (const struct commit *)_a;
-	const struct commit *b = (const struct commit *)_b;
+	const struct commit *a = *(const struct commit * const *)_a;
+	const struct commit *b = *(const struct commit * const *)_b;
 
 	if (a->generation < b->generation)
 		return -1;
-- 
2.19.0