This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Fix std::lower_bound with C++20-hostile iterators
ClosedPublic

Authored by philnik on Jun 11 2022, 1:00 PM.

Diff Detail

Event Timeline

philnik created this revision.Jun 11 2022, 1:00 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 11 2022, 1:00 PM
Herald added a subscriber: mgorny. · View Herald Transcript
philnik requested review of this revision.Jun 11 2022, 1:00 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik updated this revision to Diff 436228.Jun 12 2022, 8:44 AM
  • Generate files
EricWF requested changes to this revision.Jun 12 2022, 8:56 AM

Is this missing module map changes?

This needs a test that fails prior to the fix. Otherwise this looks good once the inline comments are addressed.

libcxx/include/__algorithm/generic_algorithm_helper.h
19
  • Inside namespace std please.
  • Scoped enum please. Implicit conversions are evil.
  • Pin the underlying type to prevent -fshort-enums from changing it.
libcxx/include/__iterator/advance.h
200

Same comment about this #ifdef as I left on __distance.

libcxx/include/__iterator/distance.h
13

I would love a more descriptive name for this header.

109

Can we lose this #ifdef, since I assume we are not passing _Ranges when we don't have complete ranges?
And if we are passing _Ranges we shouldn't be silently falling back to std::

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp
25

Can we write this without concepts so we can test it in all the dialects it affects?

Also, I don't think this tests anything. It's my understanding that concepts can't detect failures outside of the immediate context. So because the call itself is well formed, this test will always pass.

This revision now requires changes to proceed.Jun 12 2022, 8:56 AM
EricWF added inline comments.Jun 12 2022, 8:57 AM
libcxx/test/support/test_iterators.h
831

You'll probably need to stub out these functions so we can write a actual runtime test, since the compile time tests can't catch the breakage we're fixing here.

philnik updated this revision to Diff 436235.Jun 12 2022, 9:57 AM
philnik marked 3 inline comments as done.
  • Address comments
libcxx/include/__iterator/distance.h
13

Do you have a good suggestion? I think namespace is a lot worse than what I've got currently.

109

ranges::distance has to exist for if constexpr to be happy. I've added a static_assert(__ns == _Namespace::_Std).

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp
25

What exactly do you mean? C++20 is the only dialect where it is interesting AFAICT. Otherwise we always call std::advance and std::distance anyways.

For HasLowerBound to be true the instantiation of std::lower_bound has to be valid. So if HasLowerBound is true int main() { std::lower_bound(iter, sent, 0); } has to compile.

EricWF requested changes to this revision.Jun 12 2022, 10:53 AM

This LGTM, as a temporary fix; once we test it.

I'm going to request further changes, but this is a OK intermediate state, so we don't have to address them before landing this.
Thank you for you diligent work fixing this on the weekend.


Given the mess with C++03 and strong enumerations types, I'm believe we should move to using a policy object like

struct RangesIterOps {
  static It advance(...);
  static diff_t distance(...);
};
struct StdIterOps {
  static It advance(...);
  static diff_t distance(...);
};

I think it has the added benefits of:

  • Making it clear exactly what set of functions are overloaded for std iterators and ranges iterators. (it's the set of functions provided by the policy object, rather than a subset of functions discoverable only by reading every single iterator/ranges headers to see which are overloaded).
  • Removing the need for almost every single compile time branch (both #ifdef and if constexpr.) currently used by __ranges_distance and __ranges_advance. And every single compile time branch in libc++ is a bug manifest, or at least a future bug that will manifest; at least that's been my experience).
  • It removes the need for the __ranges_foo overloads entirely. Because it's not obvious to the reader that __distance is std::distance, and __ranges_distance is a dispatcher that may call ranges::distance or std::distance. In fact, __ranges_distance seems easily mistakable for the ranges::distance implementation.
  • It further isolates us from differences in behavior, for example like iterator_traits<_Iter>::difference_type being different than std::iter_distance_t<Iter> and similar.
libcxx/include/__algorithm/generic_algorithm_helper.h
10

I'm going to complain about the header name again.

One of the primary reasons I've been given for splitting up the headers is that "it makes it easier to know where an implementation actually lives", but "generic_algorithm_helper.h" doesn't indicate to me that it contains the _Namespace utility.

22

Or struct _Namespace { enum : bool { _Std, _Ranges }; };. Having the symbol have two entirely different meanings has a mean code smell.

libcxx/include/__iterator/distance.h
108

Is it the case that iterator_traits<_Iter>::difference_type is always the same type as std::iter_distance_t<_Iter>? It's not obvious that it is a requirement.

109

Ah, that makes sense.

This further pushes me towards the idea that a IteratorOperations policy object is the right way to go.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp
25

That's not correct. Concepts only consider the validity of the call expression, not everything that would be instantiated. (Because it can't back of of an instantiation once it's started instantiating, since there could be side effects and the like). So it doesn't consider the body of lower bound.

This test passes without your fix. See https://godbolt.org/z/5hfv8njeo

So we need a test that actually runs and produces an output to be sure we've fully instantiated everything.

This revision now requires changes to proceed.Jun 12 2022, 10:53 AM
EricWF added inline comments.Jun 12 2022, 11:14 AM
libcxx/include/__algorithm/generic_algorithm_helper.h
22

That said, I don't really care to see this addressed at the moment. So just ignore me.

philnik updated this revision to Diff 436240.Jun 12 2022, 12:03 PM
philnik marked 8 inline comments as done.
  • Address comments
EricWF accepted this revision.Jun 12 2022, 12:17 PM

Thank you!

libcxx/include/__algorithm/iterator_operations.h
24 ↗(On Diff #436240)

That's beautiful as we avoid any additional instantiations!

This revision is now accepted and ready to land.Jun 12 2022, 12:17 PM
EricWF added inline comments.Jun 12 2022, 12:19 PM
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp
74

I feel like the fact that this doesn't produce a linker error is a happy coincidence rather than a required behavior.

philnik updated this revision to Diff 436249.Jun 12 2022, 2:15 PM
  • Generate files
philnik updated this revision to Diff 436254.Jun 12 2022, 2:45 PM
  • Try to fix CI
libcxx/include/__iterator/distance.h
108

I'm not sure. Might be another bug. I'm switching to a policy-based solution, so this shouldn't be a problem.

philnik updated this revision to Diff 436259.Jun 12 2022, 3:28 PM
  • Next try
philnik updated this revision to Diff 436288.Jun 13 2022, 1:18 AM
  • And another one
philnik updated this revision to Diff 436294.Jun 13 2022, 1:43 AM
  • Add stubs
This revision was landed with ongoing or failed builds.Jun 13 2022, 3:19 AM
This revision was automatically updated to reflect the committed changes.
ldionne added inline comments.Jun 13 2022, 8:39 AM
libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/lower_bound.pass.cpp
77

We need to add this test for equal_range, upper_bound and other STL-classic algorithms that we fixed with this patch.