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

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

Am 05.10.2018 um 18:51 schrieb Jeff King:
> On Fri, Oct 05, 2018 at 12:59:02AM +0200, René Scharfe wrote:
> 
>> We could also do something like this to reduce the amount of manual
>> casting, but do we want to?  (Macro at the bottom, three semi-random
>> examples at the top.)
>> [...]
>> diff --git a/git-compat-util.h b/git-compat-util.h
>> index 5f2e90932f..f9e78d69a2 100644
>> --- a/git-compat-util.h
>> +++ b/git-compat-util.h
>> @@ -1066,6 +1066,18 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,
>>  		qsort(base, nmemb, size, compar);
>>  }
>>  
>> +#define DEFINE_SORT(name, elemtype, one, two, code)			\
>> +static int name##_compare(const void *one##_v_, const void *two##_v_)	\
>> +{									\
>> +	elemtype const *one = one##_v_;					\
>> +	elemtype const *two = two##_v_;					\
>> +	code;								\
>> +}									\
>> +static void name(elemtype *array, size_t n)				\
>> +{									\
>> +	QSORT(array, n, name##_compare);				\
>> +}
> 
> Interesting. When I saw the callers of this macro, I first thought you
> were just removing the casts from the comparison function, but the real
> value here is the matching QSORT() wrapper which provides the type
> safety.

Indeed.

> I'm not wild about declaring functions inside macros, just because it
> makes tools like ctags like useful (but I have certainly been guilty of
> it myself). I'd also worry that taking "code" as a macro parameter might
> not scale (what happens if the code has a comma in it?)

It works fine, as long as the comma is surrounded by parentheses, so
function calls with more than one parameter are fine without any change.

> I think we can address that last part by switching the definition order.
> Like:
> 
>   #define DEFINE_SORT(name, elemtype, one, two) \
>   static int name##_compare(const void *, const void *);                \
>   static void name(elemtype *array, size_t n)                           \
>   {                                                                     \
> 	QSORT(array, n, name##_compare);                                \
>   }                                                                     \
>   static int name##_compare(const void *one##_v_, const void *two##_v_) \
>   {                                                                     \
> 	elemtype const *one = one##_v_;					\
> 	elemtype const *two = two##_v_;					\
> 
> And then expecting the caller to do:
> 
>   DEFINE_SORT(foo, struct foo, a, b)
>      /* code goes here */
>   }
> 
> The unbalanced braces are nasty, though (and likely to screw up editor
> formatting, highlighting, etc).

Adding an extra pair of parentheses if needed is also not ideal, but has
less downsides, I think.

> I wonder if it would be possible to just declare the comparison function
> with its real types, and then teach QSORT() to do a type check. That
> would require typeof() at least, but it would be OK for the type-check
> to be available only to gcc/clang users, I think.
> 
> I'm not quite sure what that type-check would look like, but I was
> thinking something along the lines of (inside the QSORT macro):
> 
>   do {
>     /* this will yield a type mismatch if fed the wrong function */
>     int (*check)(const typeof(array), const typeof(array)) = compar;
>     sane_qsort(array, n, sizeof(*array), n);
>   } while (0)
> 
> I have no idea if that even comes close to compiling, though.

If the comparison function has proper types then we need to declare a
version with void pointer parameters as well to give to qsort(3).  I
think using cast function pointers is undefined.  Perhaps like this?

---
 bisect.c          | 11 +++++------
 commit-graph.c    |  8 ++++----
 commit-reach.c    | 12 +++++++-----
 git-compat-util.h | 14 ++++++++++++++
 4 files changed, 30 insertions(+), 15 deletions(-)

diff --git a/bisect.c b/bisect.c
index e8b17cf7e1..1fc6278c6b 100644
--- a/bisect.c
+++ b/bisect.c
@@ -192,17 +192,16 @@ struct commit_dist {
 	int distance;
 };
 
-static int compare_commit_dist(const void *a_, const void *b_)
+static int compare_commit_dist(const struct commit_dist *a,
+			       const struct commit_dist *b)
 {
-	struct commit_dist *a, *b;
-
-	a = (struct commit_dist *)a_;
-	b = (struct commit_dist *)b_;
 	if (a->distance != b->distance)
 		return b->distance - a->distance; /* desc sort */
 	return oidcmp(&a->commit->object.oid, &b->commit->object.oid);
 }
 
+DEFINE_SORT(sort_by_commit_dist, struct commit_dist *, compare_commit_dist)
+
 static struct commit_list *best_bisection_sorted(struct commit_list *list, int nr)
 {
 	struct commit_list *p;
@@ -223,7 +222,7 @@ static struct commit_list *best_bisection_sorted(struct commit_list *list, int n
 		array[cnt].distance = distance;
 		cnt++;
 	}
-	QSORT(array, cnt, compare_commit_dist);
+	sort_by_commit_dist(array, cnt);
 	for (p = list, i = 0; i < cnt; i++) {
 		struct object *obj = &(array[i].commit->object);
 
diff --git a/commit-graph.c b/commit-graph.c
index 7f4519ec3b..07d302fefd 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -550,13 +550,13 @@ static void write_graph_chunk_large_edges(struct hashfile *f,
 	}
 }
 
-static int commit_compare(const void *_a, const void *_b)
+static int commit_compare(const struct object_id *a, const struct object_id *b)
 {
-	const struct object_id *a = (const struct object_id *)_a;
-	const struct object_id *b = (const struct object_id *)_b;
 	return oidcmp(a, b);
 }
 
+DEFINE_SORT(sort_oids, struct object_id *, commit_compare)
+
 struct packed_commit_list {
 	struct commit **list;
 	int nr;
@@ -780,7 +780,7 @@ void write_commit_graph(const char *obj_dir,
 
 	close_reachable(&oids);
 
-	QSORT(oids.list, oids.nr, commit_compare);
+	sort_oids(oids.list, oids.nr);
 
 	count_distinct = 1;
 	for (i = 1; i < oids.nr; i++) {
diff --git a/commit-reach.c b/commit-reach.c
index 2f5e592d16..496c4201af 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -527,11 +527,11 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
 	return is_descendant_of(commit, list);
 }
 
-static int compare_commits_by_gen(const void *_a, const void *_b)
+static int compare_commits_by_gen(const struct commit * const *ap,
+				  const struct commit * const *bp)
 {
-	const struct commit *a = *(const struct commit * const *)_a;
-	const struct commit *b = *(const struct commit * const *)_b;
-
+	const struct commit *a = *ap;
+	const struct commit *b = *bp;
 	if (a->generation < b->generation)
 		return -1;
 	if (a->generation > b->generation)
@@ -539,6 +539,8 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
 	return 0;
 }
 
+DEFINE_SORT(sort_commits_by_gen, struct commit **, compare_commits_by_gen)
+
 int can_all_from_reach_with_flag(struct object_array *from,
 				 unsigned int with_flag,
 				 unsigned int assign_flag,
@@ -580,7 +582,7 @@ int can_all_from_reach_with_flag(struct object_array *from,
 		nr_commits++;
 	}
 
-	QSORT(list, nr_commits, compare_commits_by_gen);
+	sort_commits_by_gen(list, nr_commits);
 
 	for (i = 0; i < nr_commits; i++) {
 		/* DFS from list[i] */
diff --git a/git-compat-util.h b/git-compat-util.h
index 5f2e90932f..2462173790 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -1066,6 +1066,20 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,
 		qsort(base, nmemb, size, compar);
 }
 
+#define DEFINE_SORT(name, type, compare)				\
+static int compare##_void(const void *one, const void *two)		\
+{									\
+	return compare(one, two);					\
+}									\
+static void name(type base, size_t nmemb)				\
+{									\
+	const type dummy = NULL;					\
+	if (nmemb > 1)							\
+		qsort(base, nmemb, sizeof(base[0]), compare##_void);	\
+	else if (0)							\
+		compare(dummy, dummy);					\
+}
+
 #ifndef HAVE_ISO_QSORT_S
 int git_qsort_s(void *base, size_t nmemb, size_t size,
 		int (*compar)(const void *, const void *, void *), void *ctx);
-- 
2.19.0