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

From: René Scharfe <l.s.r@web.de>
Date: Nov 18, 2020, 17:47 UTC
Message-ID: <c236ca17-0f9e-a900-8a50-f467eaf6b485@web.de>
In-Reply-To: <20201118065437.GA16996@coredump.intra.peff.net>

Am 18.11.20 um 07:54 schrieb Jeff King:

Show 12 quoted lines

> On Tue, Nov 17, 2020 at 06:16:05PM -0800, Jonathan Nieder wrote:
>
>> Since this came up in [1], I took a glance at this.
>>
>> I also think it looks reasonable, though it's possible to do better if
>> we're willing to (1) cast between pointers to function with different
>> signatures, which is portable in practice but I don't believe the C
>> standard speaks to and (2) conditionally make use of gcc extensions,
>> for typechecking.
>
> The C standard definitely is not OK with calling a function through a
> wrong declaration or cast. I won't find chapter and verse

http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf is a draft for C99, and says under 6.3 Conversions, 6.3.2.3 Pointers, paragraph 8:

   If a converted pointer is used to call a function whose type is not
   compatible with the pointed-to type, the behavior is undefined.

Show 18 quoted lines

> Now in practice you're probably fine as long as the number and sizes of
> the parameters are the same between the function definition and what the
> caller casts to. And so if we're talking about casting individual
> parameters between a void parameter and another pointer, that would
> usually be fine (in practice; the standard only says that void can store
> the type of anything, so it _could_ be larger than some other pointers.
> I don't know of any modern systems where this is true, though).
>
> Which is all a roundabout way of saying that yes, I think this kind of
> cast is probably OK in practice.
>
> I _think_ the ccan type-checking macro you pointed to would catch this
> sufficiently on systems with typeof() that it would also protect systems
> with different calling conventions. But I admit it's pretty dense.
>
> So I dunno. The nice thing is that this puts the ugliness all inside of
> QSORT(), which becomes magically type-safe. But it involves importing a
> lot of tricky bits under the hood.

A generic and type-safe QSORT would be nice, but if it calls a function via a converted pointer then it's technically relying on undefined behavior unless I misunderstand the standard. I prefer occasional mistakes (that are caught by ASan or USan or when the sort order actually matters) to guaranteed undefined behavior that happens to work, until it doesn't.

> The downside of René's patch is that it hides the declaration of the
> comparison function (and the typesafe wrapper) inside a macro. But the
> resulting code is (IMHO) pretty easy to comprehend.

I tried some more variants back then, before I dropped the ball eventually when RL distracted me. I think my favorite one was a DEFINE_SORT macro that took the name of a typed comparison function -- the code looks more like normal C.

Handling arrays of pointers was a bit tricky, and I had to introduce DEFINE_PTR_SORT and DEFINE_CONST_PTR_SORT for them, but they allowed to use the same comparison functions -- they consistently took element pointers. Just one rule to follow, and the compiler would yell when a mismatched macro was used.

And at that point it occurred to me that comparison functions would ideally take two elements, not pointers. All the pointer mangling could be done in generated code. GCC and Clang inline it appropriately, so this convenience would be free -- but other compilers don't, and that would make sorting more expensive on those platforms. Dead end.

The last one I looked at was a dumbed-down version, but I think this requires some weird comparison function signatures in some cases (patch below, basically untested).

I can understand now why monomorphization approaches like https://github.com/attractivechaos/klib/blob/master/ksort.h seem attractive (no pun intended)..

René

---
 git-compat-util.h | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/git-compat-util.h b/git-compat-util.h
index adfea06897..8d871a8e33 100644
--- a/git-compat-util.h
+++ b/git-compat-util.h
@@ -1124,6 +1124,23 @@ int git_qsort_s(void *base, size_t nmemb, size_t size,
 		BUG("qsort_s() failed");			\
 } while (0)

+#define DECLARE_COMPARE(scope, compar)					\
+scope int compar##__void(const void *, const void *)
+
+#define DEFINE_COMPARE(scope, compar)					\
+scope int compar##__void(const void *a_void_ptr,			\
+			 const void *b_void_ptr)			\
+{									\
+	return compar(a_void_ptr, b_void_ptr);				\
+}									\
+DECLARE_COMPARE(scope, compar)
+
+#define GET_COMPARE(base, compar)					\
+(0 && compar((base), (base)) ? NULL : compar##__void)
+
+#define SORT_ARRAY(base, n, compar)					\
+QSORT((base), (n), GET_COMPARE((base), compar))
+
 #ifndef REG_STARTEND
 #error "Git requires REG_STARTEND support. Compile with NO_REGEX=NeedsStartEnd"
 #endif
--
2.29.2