This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::clamp`
ClosedPublic

Authored by var-const on May 23 2022, 4:33 AM.

Details

Reviewers
ldionne
Mordante
philnik
Group Reviewers
Restricted Project
Commits
rGa203acb9dd72: [libc++][ranges] Implement `ranges::clamp`

Diff Detail

Event Timeline

philnik created this revision.May 23 2022, 4:33 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 23 2022, 4:33 AM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.May 23 2022, 4:33 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 23 2022, 4:33 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const added inline comments.May 23 2022, 8:27 PM
libcxx/docs/Status/RangesAlgorithms.csv
29–30

Please don't forget to update the link before merging.

libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp
24

Can you also check SFINAE with indirect_­strict_­weak_­order?

33

Ultranit: maybe use different values in different test cases? I know it sounds funny but I'm slightly concerned that return 20; would pass most if not all the tests. :) It might also make it a bit more obvious which value is being returned (high/low/original) when the same value of 20 doesn't have different meanings in different test cases.

39

Can you also check with a comparator that returns something convertible to bool?

41

Can you also add test cases like (10, 10, 20) and (10, 20, 20), i.e., when value is equal to one of the bounds but not the other?

var-const commandeered this revision.Jul 30 2022, 2:47 AM
var-const edited reviewers, added: philnik; removed: var-const.
var-const updated this revision to Diff 448797.Jul 30 2022, 2:53 AM

Rebase on main.

var-const retitled this revision from [libc++] Implement ranges::clamp to [libc++][ranges] Implement `ranges::clamp`.Jul 30 2022, 2:53 AM
jloser added a subscriber: jloser.Jul 30 2022, 5:44 AM
jloser added inline comments.
libcxx/include/algorithm
290

Please don't forget to remove this merge conflict marker.

var-const updated this revision to Diff 448813.Jul 30 2022, 2:38 PM

Remove conflict marker.

var-const marked an inline comment as done.Jul 30 2022, 2:38 PM
var-const added inline comments.
libcxx/include/algorithm
290

Thanks!

var-const updated this revision to Diff 448819.Jul 30 2022, 4:06 PM
var-const marked an inline comment as done.
  • Fix a bug where the result of applying a projection could lose its value category and add a test;
  • fix incorrect assertion checking that low <= high and add an assertion test for it;
  • add SFINAE tests;
  • add ranges::clamp to the relevant robust test suites;
  • address the existing feedback.
var-const updated this revision to Diff 448843.Jul 31 2022, 2:00 AM

Fix the CI and rebase.

var-const updated this revision to Diff 448902.Jul 31 2022, 6:47 PM

Fix the CI.

var-const updated this revision to Diff 448933.Aug 1 2022, 12:30 AM

Remove accidental.

var-const updated this revision to Diff 449177.Aug 1 2022, 8:31 PM

Fix the CI.

ldionne accepted this revision.Aug 2 2022, 3:25 PM

LGTM with CI fixed and my comments applied.

libcxx/include/__algorithm/ranges_clamp.h
43

Can we add a test with a predicate that returns something explicitly convertible to bool? This should only be supported in the Ranges version.

46–52

Based on our discussion just now, your value category test is correct, however this optimization is wrong because it can lead to double-moves.

It would be possible to catch this with:

// large values to avoid SSO
int val = 100000000000000000000000000000000;
int low = 200000000000000000000000000000000;
int high = 300000000000000000000000000000000;
auto proj = [](int i) { return std::to_string(i); }; // important: returns a temporary
auto comp = [](std::string lhs, std::string rhs) { // important: moves out of rvalue arguments
    return std::atoi(lhs.c_str()) < std::atoi(rhs.c_str());
};
std::ranges::clamp(val, low, high, comp, proj);

Something like this should trigger a double-move. Probably easier to test with a Tracked value of some sort.

Also, after adding the test, can you make sure that your current implementation does fail?

libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp
10

I would XFAIL this on apple-clang-13. That's the CI issue.

This revision is now accepted and ready to land.Aug 2 2022, 3:25 PM
var-const updated this revision to Diff 449593.Aug 3 2022, 1:53 AM
var-const marked 3 inline comments as done.

Address feedback

var-const updated this revision to Diff 449594.Aug 3 2022, 1:54 AM

Rebase on main.

libcxx/include/__algorithm/ranges_clamp.h
43

Hmm, it looks like the algorithm constraints actually prevent a return type that's only explicitly (and not implicitly) convertible to bool:

  • the algorithm requires indirect_strict_weak_order for _Comp;
  • indirect_strict_weak_order requires strict_weak_order;
  • strict_weak_order requires relation;
  • relation requires boolean-testable;
  • boolean-testable requires boolean-testable-impl;
  • boolean-testable-impl requires std::convertible_to<T, bool>;
  • std::convertible_to<T, bool> requires *both* an explicit and an implicit conversion.

If I'm reading this correctly, the indirect_strict_weak_order constraint prevents the comparator that returns a type explicitly convertible to bool. If so, the bool casts in the definition of clamp in the standard appear redundant (at least for the range algorithm -- since the same wording is used for the classic algorithm as well, perhaps it's there because of it?). What do you think -- perhaps I'm missing something?

46–52

Added a new test case and verified it fails for the original version (I used a simple struct that checks for double-moving).

libcxx/test/std/algorithms/alg.sorting/alg.clamp/ranges.clamp.pass.cpp
10

Right -- it looks like this has already come up before in test/std/ranges/range.adaptors/range.filter/pred.pass.cpp which has the following comment:

// Older Clangs don't properly deduce decltype(auto) with a concept constraint
var-const updated this revision to Diff 449827.Aug 3 2022, 4:35 PM

Fix the CI.

This revision was automatically updated to reflect the committed changes.