bug#54532: [PATCH] sorting

[Eli Zaretskii <eliz@gnu.org>]

> From: Andrew Cohen <acohen@ust.hk>
> Date: Wed, 23 Mar 2022 07:59:11 +0800
> 
> The patch has 4 parts:
> 
> 1. Add a new `record_unwind_protect_ptr_mark` function for use with C data
>     structures that use the specpdl for clean-up but also contain possibly
>     unique references to Lisp objects. This is needed for the dynamic
>     memory management that the new algorithm uses.
> 2. The actual sorting change. This removes the old sorting routines and
>     puts the new implementation in a separate file, sort.c
> 3. A bunch of new unit tests.
> 4. An optimization that resolves the sorting comparison symbol into the
>     corresponding function before starting the sort.

Thanks, a few minor stylistic issues:

> +/* BINARYSORT() is a stable binary insertion sort used for sorting the
> +   list starting at LO and ending at HI.  On entry, LO <= START <= HI,
> +   and [LO, START) is already sorted (pass START == LO if you don't
> +   know!).  Even in case of error, the output slice will be some
> +   permutation of the input (nothing is lost or duplicated).  */

Our style of such comments is to phrase them as doc strings.  Which
means, among other things:

  . no need to name the function, since the comment is right in front
    of it;

  . the style should be imperative mood: "sort the list starting at LO
    and ending and HI using a stable binary insertion sort algorithm",
    etc.

One other nit: we dislike the FOO() style to mean that FOO is a
function.  That's because FOO() looks like a call to a function with
no arguments, which is not what you mean.  We use 'FOO' instead.  (Not
that you should need to refer to functions too much if you follow our
style conventions.)

Please fix your commentary that documents functions with the above
rules in mind.

> +static ptrdiff_t
> +count_run (merge_state *ms, Lisp_Object *lo, const Lisp_Object *hi, bool *descending)

This line is too long, please break it in two.

> +  eassume (lastofs == ofs);             /* Then a[ofs-1] < key <= a[ofs].  */
> +  return ofs;
> +}

Is this really eassume, or is eassert better here?