[libc++] fix std::sort(T**, T**)

[bfg]

Summary

previously, invocations of std::sort(T, T) casted the arguments to
(size_t *). this breaks sorting on systems for which pointers don't fit
in a size_t. change the cast to (uintptr_t *) and add a test.

[bfg]

There were linter-suggested indentation changes but I decided to match the file's existing style.

[arichardson]

This is required for CHERI, where we use 128-bit pointers (well actually 129 bits, since we also have a hidden validity bit).
For us size_t/ptrdiff_t are still 64 bits, but uintptr_t is 128-bits, so we need to do this sort using uintptr_t.

I'm not sure if any other architectures are affected by this (32-bit ABIs on 64-bit CPU such as x32 and MIPS n32 seem to use 32 bits for everything), but it's required for us and getting this change upstreamed would be rather helpful.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp

138–144

[mclow.lists]

It would be nice if the test had a reference to the bug report.

[ldionne]

LGTM, but please take @arichardson 's suggestions. Requesting changes until those suggestions are applied.

libcxx/include/algorithm

4165

It looks like the correct thing to do regardless of the architecture. Semantically, what we want to do is sort the elements in [first, last) as if they were integers, but size_t is not guaranteed to be able to hold a pointer. uintptr_t (or intptr_t) are the types for that.

So I agree with this change.

[ldionne]

Oh, and I agree with Marshall -- if there's a bug report for this, please link it from the test and mention it in the commit message.

[arichardson]

In D92190#2418963, @ldionne wrote:

Oh, and I agree with Marshall -- if there's a bug report for this, please link it from the test and mention it in the commit message.

I just looked at our bugtrackers and I don't think we ever filed this as an issue. The problem was noticed when running jsc (the command line tool from WebKit to run JavaScript code).
In memory our pointers (CHERI capabilities) looks like pairs of "64-bit address+64 bits of metadata (permissions+bounds)", so after calling std::sort we ended up with an array containing just the addresses of the pointers, followed by the sorted virtual addresses.

[bfg]

incorporate test suggsetions

[ldionne]

CI isn't passing in C++03 mode.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp

138–143

[bfg]

make changes c++03 friendly

[curdeius]

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp

138

It would be standard C++ this way not requiring any extensions (dynamic array), nope?

[ldionne]

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp

138

You're right. @bfg please do what Marek suggests or what I suggested. It doesn't matter to me, as long as we're standard c++03.

[bfg]

Make the constant array size static for actual C++03 conformance. Thanks all for feedback.

[ldionne]

LGTM. If you need someone to commit this for you, please provide Author Name <email@domain>. Thanks!

[bfg]

Yes please: Brett Gutstein <[e-mail]>.

[• Quuxplusone]

Aw, I wish I had seen this to bikeshed over it — it's relevant to my interests! (Finishing P0879 constexpr algorithms which includes sort; the nightmare minefield that is comparing pointers https://quuxplusone.github.io/blog/2019/01/20/std-less-nightmare/)

• Casting T** to any-kind-of-int* isn't something you can do constexprly, is it?
• Does this sort overload exist purely to avoid instantiating std::less<T*>? why is that so important? (git blame offers no help; this codepath dates back to Howard's initial import.)
• Could this sort overload simply delegate to _VSTD::sort(first, last, __less<void*>()), to avoid the constexpr-unfriendly part? (That is, don't type-pun the actual elements; force an implicit conversion to void* before each comparison.)
• If we did that, of course we'd want to add void* to the list of types for which sort's helper functions are explicitly instantiated in "algorithm.cpp". Hmm, I wonder if char8_t, char16_t, etc. should already be there...

Anyway, no action required AFAIconcerned; I'm just thinking out loud and trying not to go too far down the rabbit-hole yet. This will clearly be revisited for real at some point, as part of P0879 constexpr sort.

[ldionne]

In D92190#2435062, @Quuxplusone wrote:

Aw, I wish I had seen this to bikeshed over it — it's relevant to my interests! (Finishing P0879 constexpr algorithms which includes sort; the nightmare minefield that is comparing pointers https://quuxplusone.github.io/blog/2019/01/20/std-less-nightmare/)

• Casting T** to any-kind-of-int* isn't something you can do constexprly, is it?

No, since it's a reinterpret_cast in essence.

• Does this sort overload exist purely to avoid instantiating std::less<T*>? why is that so important? (git blame offers no help; this codepath dates back to Howard's initial import.)

My hunch is that it's a manual attempt to perform outlining, i.e. to avoid instantiating the same std::sort code over and over again for different pointer types when they are performing essentially the same task on objects that have the same representation. I could be wrong, I'm just guessing.

• Could this sort overload simply delegate to _VSTD::sort(first, last, __less<void*>()), to avoid the constexpr-unfriendly part? (That is, don't type-pun the actual elements; force an implicit conversion to void* before each comparison.)

If that results in worse generated code, then we'll have a difficult tradeoff to make. But if not, then I agree we could do that. Or we could drop the outlining attempt altogether. It all depends on whether writing sort that way actually provides a benefit with modern compilers or not, I think. We'd have to check.

Pinging @howard.hinnant in case he remembers what was the reason for writing sort that way.

[howard.hinnant]

I agree that the change from size_t to uintptr_t is the right thing to do here. I don't recall exactly why I didn't use uintptr_t in the first place. It may have simply been an oversight. Or it may have been that uintptr_t wasn't in my toolbox at the time.

[ldionne]

libcxx/include/algorithm

4163

@howard.hinnant

Sorry I wasn't clear when I pinged you earlier -- but do you recall why you wrote this specialization of std::sort for ranges containing pointers? Was it to avoid instantiating the actual sort algorithm on various T* types and save on code size?

[howard.hinnant]

Oh, yes, I believe that was it. Just a code size optimization.

[ldionne]

In D92190#2440545, @howard.hinnant wrote:

Oh, yes, I believe that was it. Just a code size optimization.

Thanks a lot, that confirms my hunch.

So @Quuxplusone feel free to investigate ways to remove or modify this, now that you know the original intent. We shouldn't take a code size regression for constexpr, though (I'm sure there's a bunch of ways we can make that work).

libcxx/include/algorithm

 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
     _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 template <class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 sort(_Tp** __first, _Tp** __last)
 {
-    _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());
+    _VSTD::sort((uintptr_t*)__first, (uintptr_t*)__last, __less<uintptr_t>());
 }
 
 template <class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 sort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last)
 {
     _VSTD::sort(__first.base(), __last.base());

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/sort.pass.cpp

test_larger_sorts(int N)
     test_larger_sorts(N, N/2-1);
     test_larger_sorts(N, N/2);
     test_larger_sorts(N, N/2+1);
     test_larger_sorts(N, N-2);
     test_larger_sorts(N, N-1);
     test_larger_sorts(N, N);
 }
 
+void
+test_pointer_sort()
+{
+    static const int array_size = 10;
+    const int v[array_size] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+    const int *pv[array_size];
+    for (int i = 0; i < array_size; i++) {
+      pv[i] = &v[array_size - 1 - i];
+    }
+    std::sort(pv, pv + array_size);
+    assert(*pv[0] == v[0]);
+    assert(*pv[1] == v[1]);
+    assert(*pv[array_size - 1] == v[array_size - 1]);
+}
+
 int main(int, char**)
 {
     // test null range
     int d = 0;
     std::sort(&d, &d);
     // exhaustively test all possibilities up to length 8
     test_sort_<1>();
     test_sort_<2>();
     test_sort_<3>();
     test_sort_<4>();
     test_sort_<5>();
     test_sort_<6>();
     test_sort_<7>();
     test_sort_<8>();
 
     test_larger_sorts(256);
     test_larger_sorts(257);
     test_larger_sorts(499);
     test_larger_sorts(500);
     test_larger_sorts(997);
     test_larger_sorts(1000);
     test_larger_sorts(1009);
 
+    test_pointer_sort();
+
   return 0;
 }