This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by fwolff on Nov 14 2021, 4:56 PM.

Details

Summary

Fixes PR#52151.

Diff Detail

Event Timeline

fwolff requested review of this revision.Nov 14 2021, 4:56 PM
fwolff created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptNov 14 2021, 4:56 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Quuxplusone requested changes to this revision.Nov 14 2021, 5:22 PM
Quuxplusone added a subscriber: 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.)

This revision now requires changes to proceed.Nov 14 2021, 5:22 PM

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.

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 updated this revision to Diff 387359.Nov 15 2021, 12:34 PM
fwolff retitled this revision from [libcxx] Cast to the right `difference_type` in `std::search` and `std::find_end` to [libcxx] Cast to the right `difference_type` in various algorithms.

Fix the same problem in the other algorithms

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
63

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 added inline comments.Nov 15 2021, 1:38 PM
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?

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 marked an inline comment as done.Nov 15 2021, 1:46 PM
fwolff added inline comments.
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 updated this revision to Diff 387397.Nov 15 2021, 1:58 PM
fwolff marked an inline comment as done.

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

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).

ldionne accepted this revision.Nov 16 2021, 8:07 AM
This revision is now accepted and ready to land.Nov 16 2021, 8:07 AM
Mordante accepted this revision.Nov 16 2021, 12:04 PM

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.

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 added inline comments.Nov 16 2021, 1:00 PM
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 added inline comments.Nov 16 2021, 1:08 PM
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.

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 marked 2 inline comments as done.Nov 18 2021, 11:01 AM
fwolff updated this revision to Diff 388270.Nov 18 2021, 11:15 AM

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!