This is probably a lot of somewhat redundant code, but I added it here as a 'test' use which provides a boilerplate to replace the routines with a more efficient special-case indirect sort in a future PR. As a "bonus" it allows us to at least temporarily do the allocation this PR was intended for

Nice! I'll let@seberg evaluate whether this API needs adjustments to fit in with the broader DType API but at a first glance it looks reasonable to me, especially if the common case with no specializations can be done with less boilerplate.

That said - there definitely are specialized string sorting implementations we could be using here.

This is good, the thing that I would like to change is thePyArray_(Arg)SortFunc itself, so that it gets a context and auxdata instead of the "array". And this function would getNpyAuxData *out_auxdata in also.
(Although, maybe for sorting this is less interesting as it is not as common to sort many arrays in one.)

The unfortunate thing is that you need to wrap the existing functions if you do this or have a second path for the old function.

I am also considering if we should have a return-2 or so to indicate that the sort-kind is not supported (no error set), to allow NumPy to fall back to a different one.
(But I am not sure we need it, it is useful only for somtehing like mergesort/stablesort, explicitly.)
@charris may have a thought on that.

Looking into passing context now! It looks like a good idea, will try to implement. Thanks.

This change would be really nice; unfortunately both thePyArray_CompareFunc and the sort functions use thePyArrayObject right now, which we probably (!) shouldn't get from the context.

If I'm thinking right, we can define a new type such asPyArray_SortCompareFunc that uses the descr instead of the arrayand makenew sort functions that do not use the array somehow (as we can no longer interchange theSortCompareFunc and theCompareFunc!), but we would still probably need the old functions to use with the older compare functions; I think the duplication will be quite complicated.

At the same time, this would be a missed opportunity to have the newCompareFunc type if we do deprecate laterand want to go down this route...

There are two possible approaches here:

1. We deal with it in the sort function, and just have to different calls depending on whether it is an old or new sort function.
2. You ignore the fact that an array is currently passed (effectively). We do that in some other places as well, due to how terrible it is.
   That is, we wrap it into a dummy object for which basically the only valid field isarr->descr (and maybearr->flags, don't recall). (Seeget_dummy_stack_array, yes this is terrible and even reviewers stumble over it, but...)
   If you do that, you can write a short function that wraps the old call into a function taking the new one.

I did the second for ufuncs (not sure if that was the easier!), so I suspect the first is likely the simplest here.

Allowing to set a compare function, seems like a nice idea (also to have a simple default).

It would be nice to move that into a default slot function. I.e. rather than setting it forStringDType here, auto-fill the slot with the function that tries to use theSortCompareFunc (If that slot is undefined, we can keep the slot filled withNULL).
That also removes the second check later.

About thisSortCompareFunc, it may make sense to keep it "light-weight" (i.e. a single function even if that may not be ideal if you have to inspect thedtype to do the comparisons -- for example structured has to do this).

But I would like to think about what we need to sort things like NaNs if possible. Unfortunately, I am not immediately sure, i.e.<=> in C++ can return a partial order, which means that:

• For us probably an "error" is a valid return (right now we can't propagate errors!).
• "unordered" is a valid return, although I am not sure how to deal with it. If we have "compare(a, b) == unordered" (i.e. one or both are NaN), we don't yet know how to swap them. That may be possible to resolve withcompare(b, b) andcompare(a, a).
  But the only way I am quite sure how to resolve possible reversed sorting, etc. might be to haveunordered_left,unordered_both,unordered_right.

Or we should keep it roughly as is, and accept that this function doesn't exist for all dtypes... A neat thing about having a clear order with "unordered" is that we could also use it from the comparison (u)funcs.

I'll try the first approach I think! I think it will help isolate the new API in a way that makes deprecation easier later too. I will also do this default logic for both compare and sort compare funcs.

As for allowing partial order: yes that could break the symmetry, I suppose. But it could be useful to make sorting more precise in the long run too, and so "unordered" does seem a better way to allow for those kinds of extensions. And then we can use this machinery as the go-to for anywhere comparison decisions need to be made as you said.

New stuff in the public API needs new API docs as well as a release note describing the new features.

Maybe also as a proof-of-concept, it looks like both quaddtype and mpfdtype in numpy-user-dtypes implement sorting - would you be willing to update them to use the new API in a PR to numpy-user-dtypes that depends on this PR to numpy? That should give you a feeling for whether this API is helpful for someone writing a new user dtype. It'll also be a form of documentation - we don't have great docs for writing user dtypes besides the examples in numpy-user-dtypes.

Also what should we do about the flags that got added before we made the dtype API public, e.g.NPY_DT_PyArray_ArrFuncs_compare? I guess we can deprecate them although I don't know how hard it would be to generate deprecation warnings if those are used.

It's easy to generate a deprecation warning during registration (a bit tedious maybe, as you need explicit check).

Sure, I'll add API docs and a release note, and willing to make a PR to numpy-user-dtypes! Will look into that.

Just to be clear,NPY_DT_PyArray_ArrFuncs_compare is still needed right? We can move it to a new slot rather than an arrayfunc but it's going to be different from the sort comparison for now if I'm thinking right (as it is user-facing rather than used in the sorting). Do we need to do this another way?

We can't change slot numbers (unless they are guarded as private)! So the numbers are fixed (until they have not been used for a bit at least).
So yeah, I think we should keep it the old slot for now, maybe easier to make the deprecation a follow up.[^depr]

So, we just have to live with the numbering we got, I half thought I asked for an offset for theNPY_DT_PyArray_ArrFuncs slots, but maybe I didn't bother.
(It's not a big issue, the only thing is the convenience ifslot numbers == slot offset so you don't need to translate it.)

[^depr] I think this is as simple as asking users to compile with the new NumPy, and then addingPyArray_RUNTIME_VERSION, but this PR is complicated enough due to API decisions for the new loops, etc.

So, we just have to live with the numbering we got, I half thought I asked for an offset for the NPY_DT_PyArray_ArrFuncs slots, but maybe I didn't bother.

There is an offset,_NPY_DT_ARRFUNCS_OFFSET:

Nice! I'll let@seberg evaluate whether this API needs adjustments to fit in with the broader DType API but at a first glance it looks reasonable to me, especially if the common case with no specializations can be done with less boilerplate.

That said - there definitely are specialized string sorting implementations we could be using here.

I'd call thisPyArray_GetSortCompareFunction

Yes, made this change. Thanks

I think this was added by mistake?

Yes, sorry!

maybe a note that the old arrfuncs slots may be deprecated in the future.

Added, thanks!

can you re-order these so the slots that were already in the struct keep their old values? I don't know offhand if changing this order is problematic but it seems more consistent to not change the old values even if it's fine.

Yes, done!

You did not actually add them to the public C-API. Which is totally fine, though.

(I might start with adding aSortBuffer() function or so.)

There are two possible approaches here:

1. We deal with it in the sort function, and just have to different calls depending on whether it is an old or new sort function.
2. You ignore the fact that an array is currently passed (effectively). We do that in some other places as well, due to how terrible it is.
   That is, we wrap it into a dummy object for which basically the only valid field isarr->descr (and maybearr->flags, don't recall). (Seeget_dummy_stack_array, yes this is terrible and even reviewers stumble over it, but...)
   If you do that, you can write a short function that wraps the old call into a function taking the new one.

I did the second for ufuncs (not sure if that was the easier!), so I suspect the first is likely the simplest here.

Allowing to set a compare function, seems like a nice idea (also to have a simple default).

It would be nice to move that into a default slot function. I.e. rather than setting it forStringDType here, auto-fill the slot with the function that tries to use theSortCompareFunc (If that slot is undefined, we can keep the slot filled withNULL).
That also removes the second check later.

About thisSortCompareFunc, it may make sense to keep it "light-weight" (i.e. a single function even if that may not be ideal if you have to inspect thedtype to do the comparisons -- for example structured has to do this).

But I would like to think about what we need to sort things like NaNs if possible. Unfortunately, I am not immediately sure, i.e.<=> in C++ can return a partial order, which means that:

• For us probably an "error" is a valid return (right now we can't propagate errors!).
• "unordered" is a valid return, although I am not sure how to deal with it. If we have "compare(a, b) == unordered" (i.e. one or both are NaN), we don't yet know how to swap them. That may be possible to resolve withcompare(b, b) andcompare(a, a).
  But the only way I am quite sure how to resolve possible reversed sorting, etc. might be to haveunordered_left,unordered_both,unordered_right.

Or we should keep it roughly as is, and accept that this function doesn't exist for all dtypes... A neat thing about having a clear order with "unordered" is that we could also use it from the comparison (u)funcs.

This needs to set an error (TypeError or DTypeTypeError, which is defined somewhere I think.)

(An error here will make sense after you move the fallback logic into a default slot filling. Or you could have the default slot raise an error, that is also completely fine.)

The naming is a bit weird here, but I didn't want to disturb the original type as it's used a lot. I think theSortCompareFunc should still be a unique type so will do that (even if only a clone of this type).