[libcxx] Cast to the right `difference_type` in various algorithms

[fwolff]

Summary

Fixes PR#52151.

[• Quuxplusone]

https://en.cppreference.com/w/cpp/algorithm/ranges/find_end
http://eel.is/c++draft/alg.find.end

Notice that std::ranges::find_end is specifically specified to return an expression involving i + (last2 - first2) where i is an I1 — implying that I1 + D2 ought to be valid, even though ranges::find_end doesn't list that as a Constraint. So I'm inclined to say that the culprit here is the user's iterator type that is implicitly convertible to raw pointer; fix that, and you'll have a lot less grief as you move toward C++20.

If we pursue this PR, I think we should at least use an implicit conversion, not an explicit conversion; I trust _D1 d1 = __len2 - 1 to do-the-right-thing-or-error-out waaay more than I trust static_cast<_D1>(__len2 - 1).

Finally, this needs tests. I recommend copying the approach of libcxx/test/std/algorithms/robust_against_adl.pass.cpp: make two iterator types that play poorly together, as in the OP, and then test them against all the standard algorithms that take multiple iterator types. (This can be a compile-only test.)

[tcanens]

http://eel.is/c++draft/algorithms.requirements#13

[• Quuxplusone]

I've done my proposed testing approach in D113906. I suggest that you rebase after I've merged that, and/or just add it as a "Parent Revision" in Phabricator right now. Then, your testing strategy here can just be to uncomment all of the TODO FIXME'd lines in that test file.

[Mordante]

I also miss tests. In general when fixing a bug it would be nice to add tests based on the reported error.
In this case best follow @Quuxplusone's suggestion for the tests.

libcxx/include/__algorithm/find_end.h

101

Style nit: in general we don't use const variables in libc++.

[fwolff]

Fix the same problem in the other algorithms

[• Quuxplusone]

LGTM mod the one unnecessary diff, and indentation. (Don't trust clang-format; it likes to mess up libc++ style.)

libcxx/include/__algorithm/copy_n.h

60 ↗

(On Diff #387359)

Note for the record: This un-uglified name is technically OK because it's a library reserved name. We actually do the same trick in __make_heap below. If I hadn't seen that in __make_heap, I'd totally have objected to this. ;) But given the precedent, I think it's OK.

libcxx/include/__algorithm/make_heap.h

33 ↗

(On Diff #387359)

We shouldn't need to cast the 2 here — this is just plain old "integral minus integral" subtraction. We don't cast 1 on line 30, for example. So I recommend reverting this diff.

34 ↗

(On Diff #387359)

You've broken the indentation here (and various places, especially in sort.h). Please make sure to preserve the existing indentation style wherever you change code. (If it's 2-space, leave it 2-space; if it's 4-space, leave it 4-space; don't mix styles within the same function.)

[fwolff]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

I've tried to, but Arcanist wouldn't let me update this revision without the clang-format changes. Is there a special option I can use to suppress this?

[• Quuxplusone]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

I do think there's some arc option for that, but I don't use arc myself. I just use git show -U999 > foo.diff and then "Update Diff" in the right sidebar at the top of the page.

[fwolff]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

OK. I was unsure because the "Contributing to libc++" guide says that you have to use arc for submitting patches, but then I'll just do it via "Update Diff".

[fwolff]

@Quuxplusone I think I've addressed all of your comments now.

[• Quuxplusone]

LGTM once CI is green. You'll have to rebase on the updated D113906, or just wait until it's landed (which I hope can be soon, like, tomorrow).

[Mordante]

LGTM after addressing @Quuxplusone's comments.

If you need somebody to land the patch after it's finished, then please provide "Your name <email@domain>".

libcxx/include/__algorithm/find_end.h

101

To make reviewing easier, can you mark comments as done when you've addressed them?

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

For libc++ we really prefer arc else the CI isn't triggered. For arc you can use --nolint or press n at all suggestions arc makes.

[• Quuxplusone]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

or else the CI isn't triggered

I use plain old git diff -U999 + "Update Diff", and I'm not aware that my PRs ever fail to trigger CI. (The only thing to watch out for is sometimes if you update twice in very quick succession, the builder may get confused when it goes to pull a revision and the revision is already gone. But I assume arc would have the same problem.)

That said, yeah, arc --nolint was exactly the thing I was trying to think of.

[ldionne]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

I know at some point you at least had to make sure the right tags were added to the review, otherwise CI wouldn't get triggered. And arc diff made sure this happened, but I've seen cases where manually uploaded diffs didn't have the right tags.

It's been a while since I've seen this issue, to be fair.

[Mordante]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

That issue was why I switched from direct uploads to arc. I wasn't aware the issue has since been resolved.

[• Quuxplusone]

libcxx/include/__algorithm/make_heap.h

34 ↗

(On Diff #387359)

Aha. IIUC, I do this part manually too: when I upload a diff, Phab asks me questions like "what repository" ("llvm"-tab-complete: the GitHub monorepo) and "what project" ("libc++"-tab-complete) and "what reviewers" (typically "ldionne, mordante, libc++"). It would not surprise me if, when I didn't put in "libc++" for the project, it failed to trigger buildkite. But for me that's all just part of the process of uploading a diff.

[fwolff]

Rebased on rG4a8734deb7d5, so this is now ready, I think.

@Mordante Yes, I need someone to commit this for me. You can use the same name and email as in commit 738e7f1231949ec248c1d8d154783338215613d1. Thanks!

libcxx/include/__algorithm/find_end.h

while (true) {
     }
   }
 }
 
 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end(
     _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
     _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) {
+  typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1;
+  typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
   // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
-  typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2;
+  const _D2 __len2 = __last2 - __first2;
   if (__len2 == 0)
     return __last1;
-  typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1;
+  const _D1 __len1 = __last1 - __first1;
   if (__len1 < __len2)
     return __last1;
-  const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here
+  const _RandomAccessIterator1 __s =
+      __first1 + static_cast<_D1>(__len2 - 1); // End of pattern match can't go before here
   _RandomAccessIterator1 __l1 = __last1;
   _RandomAccessIterator2 __l2 = __last2;
   --__l2;
   while (true) {
     while (true) {
       if (__s == __l1)
         return __last1;
       if (__pred(*--__l1, *__l2))

libcxx/include/__algorithm/search.h

__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
   typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2;
   // Take advantage of knowing source and pattern lengths.  Stop short when source is smaller than pattern
   const _D2 __len2 = __last2 - __first2;
   if (__len2 == 0)
     return _VSTD::make_pair(__first1, __first1);
   const _D1 __len1 = __last1 - __first1;
   if (__len1 < __len2)
     return _VSTD::make_pair(__last1, __last1);
-  const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here
+  const _RandomAccessIterator1 __s =
+      __last1 - static_cast<_D1>(__len2 - 1); // Start of pattern match can't go beyond here
 
   while (true) {
     while (true) {
       if (__first1 == __s)
         return _VSTD::make_pair(__last1, __last1);
       if (__pred(*__first1, *__first2))
         break;
       ++__first1;
     }
 
     _RandomAccessIterator1 __m1 = __first1;
     _RandomAccessIterator2 __m2 = __first2;
     while (true) {
       if (++__m2 == __last2)
-        return _VSTD::make_pair(__first1, __first1 + __len2);
+        return _VSTD::make_pair(__first1, __first1 + static_cast<_D1>(__len2));
       ++__m1; // no need to check range on __m1 because __s guarantees we have enough source
       if (!__pred(*__m1, *__m2)) {
         ++__first1;
         break;
       }
     }
   }
 }