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

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Nov 18, 2020, 02:16 UTC
Message-ID: <20201118021605.GB360414@google.com>
In-Reply-To: <20181017083340.GB31932@sigill.intra.peff.net>

Hi,

Jeff King wrote:

> On Sun, Oct 14, 2018 at 04:29:06PM +0200, René Scharfe wrote:

Show 25 quoted lines

>> Anyway, drove the generative approach a bit further, and came up with
>> the new DEFINE_SORT below.  I'm unsure about the name; perhaps it should
>> be called DEFINE_SORT_BY_COMPARE_FUNCTION_BODY, but that's a bit long.
>> It handles casts and const attributes behind the scenes and avoids
>> repetition, but looks a bit weird, as it is placed where a function
>> signature would go.
>>
>> Apart from that the macro is simple and doesn't use any tricks or
>> added checks.  It just sets up boilerplate functions to offer type-safe
>> sorting.
>>
>> diffcore-rename.c and refs/packed-backend.c receive special treatment in
>> the patch because their compare functions are used outside of sorting as
>> well.  I made them take typed pointers nevertheless and used them from
>> DEFINE_SORT; the wrapper generated by that macro is supposed to be
>> private.  Given that such reuse is rare and I think we don't need a way
>> to make it public.
>>
>> What do y'all think about this direction?
>
> I think it's the best we're likely to do, and is an improvement on the
> status quo.
>
> The patch looks overall sane to me. I think DEFINE_SORT() is a fine
> name.

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.

For example, CCAN's asort[2] does typechecking on the arrays passed in and the callback cookie parameter to qsort_r, with no extra boilerplate or run-time overhead involved[3].

(The core of that macro is ccan's typesafe_cb_cast[4]:

  /* CC0 (Public domain) - see LICENSE file for details */

  #if HAVE_TYPEOF && HAVE_BUILTIN_CHOOSE_EXPR && HAVE_BUILTIN_TYPES_COMPATIBLE_P
  /**
   * typesafe_cb_cast - only cast an expression if it matches a given type
   * @desttype: the type to cast to
   * @oktype: the type we allow
   * @expr: the expression to cast
   *
   * This macro is used to create functions which allow multiple types.
   * The result of this macro is used somewhere that a @desttype type is
   * expected: if @expr is exactly of type @oktype, then it will be
   * cast to @desttype type, otherwise left alone.
   *
   * This macro can be used in static initializers.
   *
   * This is merely useful for warnings: if the compiler does not
   * support the primitives required for typesafe_cb_cast(), it becomes an
   * unconditional cast, and the @oktype argument is not used.  In
   * particular, this means that @oktype can be a type which uses the
   * "typeof": it will not be evaluated if typeof is not supported.
   *
   * Example:
   *      // We can take either an unsigned long or a void *.
   *      void _set_some_value(void *val);
   *      #define set_some_value(e)                       \
   *              _set_some_value(typesafe_cb_cast(void *, unsigned long, (e)))
   */
  #define typesafe_cb_cast(desttype, oktype, expr)                        \
          __builtin_choose_expr(                                          \
                  __builtin_types_compatible_p(__typeof__(0?(expr):(expr)), \
                                               oktype),                   \
                  (desttype)(expr), (expr))
  #else
  #define typesafe_cb_cast(desttype, oktype, expr) ((desttype)(expr))
  #endif
)

Thanks, Jonathan

[1] https://lore.kernel.org/git/20201117223011.GA642234@coredump.intra.peff.net/ [2] https://git.ozlabs.org/?p=ccan;a=blob;f=ccan/asort/asort.h;hb=HEAD [3] https://ccodearchive.net/info/asort.html [4] https://git.ozlabs.org/?p=ccan;a=blob;f=ccan/typesafe_cb/typesafe_cb.h;hb=HEAD