[libcxx] makes `iterator_traits` C++20-aware

[ldionne]

Summary

• moves C++17 iterator_traits
• adds iterator_traits specialisation that supports all expected member aliases except for pointer
• adds iterator_traits specialisations for iterators that meet the legacy iterator requirements but might lack multiple member aliases
• makes pointer iterator_traits specialisation require objects

Depends on D99854.

[Mordante]

libcxx/include/iterator

860

Does this hunk affect the synopsis?

880

For clarity "If I has" -> "If I has".

889

Will __primary_template be used in a later patch?

899

Please update the synopsis.

903

I rather remove the underscores in _`cpp17-input-iterator`_,". I don't think they add clarity. The same for the other places where you used these concepts.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.pass.cpp

16 ↗

(On Diff #335133)

I would like some tests using the contiguous_iterator_tag see whether it acts as a random_access_iterator_tag.

183 ↗

(On Diff #335133)

std::same_as compares the same type.

226 ↗

(On Diff #335133)

Would it be nice to test whether the test fails when missing_iterator_category is provided but not a typename? E.g.
int missing_iterator_category
And similar for the tests below?

[cjdb]

applies @Mordante's feedback

[cjdb]

libcxx/include/iterator

860

Apparently not. Our synopsis for iterator_traits is far more in-depth than [iterator.synopsis], so I'm not sure if we want to go the extra mile and add it. If anything, I'd prefer to delete some of our header's synopsis to match the standard.

889

Yes (next patch), but it also is a part of the standard to make this the primary template :-)

903

Sure, this isn't Markdown anyway.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.pass.cpp

16 ↗

(On Diff #335133)

Is that in scope for this test? I need a bit of convincing :-)

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[tcanens]

libcxx/include/iterator

883

I think all of these cases need to be routed through a base class template from which iterator_traits derives. "Primary template" means "primary template"; if I specialize iterator_traits for my types, it must not create an ambiguity with these specializations, even if I write my specialization like

template<class I>
    requires is_my_iterator<I>
struct std::iterator_traits<I>{
    // ...
};

[cjdb]

moves iterator_traits into __iterator_traits as per @tcanens' feedback
hopefully gets CI working

[cjdb]

rebases to activate CI

[Mordante]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.pass.cpp

16 ↗

(On Diff #335133)

The contiguous_­iterator is part of the cxx20 iterators, so seems like a good reason to test it here. If not, where do you want to test it?

183 ↗

(On Diff #335133)

I still see the same types ;-)

[zoecarver]

The logic LGTM.

libcxx/include/iterator

890

Can you define this before iterator_traits? I feel like there's needless complexity here.

901

This also needs a few updated: value_type should now remove cv, adds iterator_concept , adds a const specialization. Are you making those changes in another patch?

913

Again, is there any reason we can't define these before we use them?

1029

Can you put a comment // !defined... here too?

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

83

I feel like both this and get_pointer are doing the thing where you write the same implementation twice and test that they do the same thing. IMHO that's not a great way to write tests.

108

Side note: the functions don't actually return anything useful. All the testing is done when the function is instantiated. So, why is this nodiscard? Wouldn't instantiating this function template inside a function be the same as instantiating it inside a static_assert?

126

This indentation seems a bit odd, is this what clang format spit out? Either way, can you un-indent?

163

This test I really like because I can read it and immediately see that it's doing the right thing. You say, "here is the input" and "here is the non-computed literal output."

252

Nice. This is a good idea to test :)

290

I have no idea what the consensus here was... are we still doing compile.passp.cpp tests or no? If no, then we should make this a "normal" .pass test.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp

103

Nit: // _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_HAS_NO_CONCEPTS)

[zoecarver]

libcxx/include/iterator

890

This is a sort of general note for the whole patch. I think it's best to define things and then use them. I don't really see any benefit to declaring them, using them, then defining them. And it makes it harder to read/understand, increases code size, complexity, compile time, etc.

[cjdb]

libcxx/include/iterator

901

value_type should now remove cv,

Already applied (see below).

adds iterator_concept

Already applied (see below).

adds a const specialization

I don't see this in [iterator.traits]?

913

C++ best practice is to define things as close as possible to their first point of use. The other specialisations don't need these, and IMO shouldn't be able to see them.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

83

This was the best I could come up with. If you're able to think of a different way to get this information, I'm all ears.

290

Consensus was to keep .compile.pass.cpp and for them to no longer have main.

[zoecarver]

libcxx/include/iterator

901

Already applied (see below).

Even better :)

I don't see this in [iterator.traits]?

Ah, I said the wrong thing. I meant it removes the const specialization. And I guess we never had that specialization, so nothing to be done.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

83

I think thinking about it as "getting this information" is not the right way to think about it in the context of a test. The test's job isn't to get that information. It's to verify that the implementation knows how to get that information.

This will require writing this test a bit differently, so maybe before implementing my suggestion (if you're amenable to it), we should check with others (cc @ldionne and @Quuxplusone).

What if you wrote check_wrapper_traits as

template <class I, class Wrapper, class Category, class Pointer, class Reference>
constexpr bool check_wrapper_traits() {
  // ...
  static_assert(std::same_as<typename Traits::reference, Reference>);
  static_assert(std::same_as<typename Traits::pointer, Pointer>);
}

In this example, you'd have to launder Pointer and Reference through the other helper templates, so maybe it's not ideal, but I hope you get what I'm saying (if not, I'll explain more clearly).

Basically, what I'm suggesting is that you give the test the literal expect value that you (as the human) figure out by looking at the standard. Just like what's done in check_with_legacy_iterator.

290

Great. I like this idea a lot. Keeping the time it takes to run the tests down :)

[• Quuxplusone]

libcxx/include/iterator

890

Big +1 to what @zoecarver said. More code = more bugs; but even more importantly, complicated code = complicated bugs. Let's make this code as simple as possible. That means as few forward declarations as possible: instead, define entities in the "logical order" so that we build up linearly from the simple details to the big-picture top-level users, with as little "mixing" of levels as possible.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

83

@zoecarver: I spent a while and wrote up how I'd test all the codepaths here — by following the case-by-case enumeration laid out on cppreference. Here it is:

https://godbolt.org/z/qqKeM3do9

Basically, we expect a special case for pointers; and then we have the simple cases for "all five user-provided" and "four of the five user-provided"; and then we get into all the LegacyFooIterator concepts; and finally we have the fallback to LegacyIterator a.k.a. output-iterator. All of these tests pass with libstdc++ and with MSVC, so I'd hope they pass with libc++'s implementation as well.

I didn't get around to writing the tests for static_assert(isnt_an_iterator_v<T>). I'd probably put those tests in a separate .cpp file, because they'd look very different.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/legacy_iterator_wrappers.h

108–110 ↗

(On Diff #336695)

This function shouldn't need a body, any more than the other member functions do.
(It's also weird that you're building up these "layered" overload sets of member and friend functions; e.g. a legacy_random_access_iterator will be implicitly convertible to a legacy_iterator whose operator++ has a different return type from the original. Personally I wouldn't use inheritance for this kind of thing; I'd do what "test_iterators.h" does and write completely minimal "archetypes" with no metaprogramming at all. Any chance we could convince you to pursue that minimal direction?)

(EDIT: I've done this now. Here's my suggested tests: https://godbolt.org/z/qqKeM3do9 )

[zoecarver]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

83

I like these tests a lot. I think this is a perfect example of how we should be testing these things (IMHO). All the cases are covered, and yet, they are super simple and easily verifiable. When I look at something like:

using PT = std::iterator_traits<int*>;
static_assert(std::same_as<PT::iterator_category, std::random_access_iterator_tag>);
static_assert(std::same_as<PT::value_type, int>);
static_assert(std::same_as<PT::difference_type, std::ptrdiff_t>);
static_assert(std::same_as<PT::reference, int&>);
static_assert(std::same_as<PT::pointer, int*>);
static_assert(std::same_as<PT::iterator_concept, std::contiguous_iterator_tag>);

it is immediately clear a) what is being tested, and b) if the test is correct. If you have something computed, like:

static_assert(std::same_as<typename Traits::reference,
                           typename get_reference<I, Wrapper>::type>);

It isn't as clear what iterator is being tested, but more importantly, it isn't clear that the test is correct. I have to go through all the logic of who is calling this function, what the I and Wrapper types are, and then what the implementation logic for get_reference is. All of those are error prone and not really necessary. For tests we shouldn't be testing that the implementation does the same thing as X, we should be testing that the implementation does the right thing.

I would be in support of using those tests instead (or maybe in addition to some of the existing tests). Please update some of the iterator names, though (such as A and B to be more descriptive).

[cjdb]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

83

Sure, I can adopt it.

by following the case-by-case enumeration laid out on cppreference.

I'm going to have to write this from scratch (or at least thoroughly verify it), because this wasn't derived from the standard draft. I have no way of knowing if (a) cppreference is up-to-date, and (b) if it's correct.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/legacy_iterator_wrappers.h

108–110 ↗

(On Diff #336695)

Any chance we could convince you to pursue that minimal direction?

Yes, per my comment above. Give me a day or so to work through it please.

[cjdb]

rebases to activate CI

[ldionne]

I like that you're commenting with the bullets, it makes it easy to follow. Generally LGTM with a few issues, but I think we're pretty close already.

libcxx/include/iterator

872

I find that introducing this __has_member_reference intermediate concept increases complexity a bit without adding much. I think it would be fine to just use requires { typename _Ip::reference; } in the two places where it is used. Same for __has_member_iterator_category.

894

For the primary template, pointer should be (http://eel.is/c++draft/iterator.traits#3.1):

If the qualified-id I​::​pointer is valid and denotes a type, then iterator_­traits<I>​::​pointer names that type; otherwise, it names void.

We shouldn't check for operator->(), so using __iterator_traits_member_pointer<_Ip> (which checks for operator->()) doesn't sound correct to me. We should also add a test that catches that: define a type T from which we could deduce iterator_traits<T>::pointer using operator->() but not otherwise, and confirm that iterator_traits<T>::pointer is void. Before fixing this comment, the result would have been whatever's deduced by operator->.

930–940

That way __has_arrow makes sense on its own.

[cjdb]

rebases so @zoecarver can commandeer without issue

[zoecarver]

rebases so @zoecarver can commandeer without issue

Worked like a charm. Thanks!

[zoecarver]

libcxx/include/iterator

894

Yes, @ldionne you're right. Here's an example (from Arthur's godbolt) which catches this:

struct NoPointerMember {
  struct iterator_category {};
  struct value_type {};
  struct difference_type {};
  struct reference {};
  value_type* operator->() const;  // ignored, because B is not a LegacyInputIterator
};
static_assert(std::same_as<NoPointerMemberTraits::pointer, void>);

On both MSVC and GCC this compiles just fine, but we (currently) think the pointer type should be value_type*.

[zoecarver]

Adds Arthur's (modified) tests. I have not started to apply the other review comments yet.

[zoecarver]

• Base diff on correct commit.

[cjdb]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

73

TODO?

279

I think these are a duplication of what's in test/libcxx/iterators/iterator.requirements/iterator.assoc.types/iterator.traits/iterator_traits_cpp17_iterators.h. Could you please confirm?

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp

103

This should be !defined(_LIBCPP_HAS_NO_RANGES) now (I didn't get around to fixing it up).

libcxx/test/std/iterators/iterator.primitives/iterator.traits/legacy_iterator_wrappers.h

1 ↗

(On Diff #337936)

Do we still need this file?

[zoecarver]

...while I update the rest of the comments. (Should have done this last night, sorry.)

[zoecarver]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

73

To remind me to fix the pointer thing. No longer needed. Thanks.

279

Yes, they're very similar. I think the only real difference is the difference_type. This one has a weird difference type, which I think is good because it shows that it's getting it from the correct place.

That being said, this is a fairly small object, and I think it's beneficial to the reader to have the short test next to the short object. It makes it easy to see exactly what the input and output it without having to look for something or think too hard. But that's just my opinion, maybe others feel differently.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp

103

Actually, I don't think so. This is in the std/ directory. If it was in the libc++ directory, I would agree. But ideally these are "generic" standard library tests. They wouldn't rely on any of our implementation details.

[zoecarver]

• Add a few more tests.
• Fix inline comments.
• Re structure impl.
• Remove "-_" characters.

[zoecarver]

• (Again) base on correct commit.

Sorry for the extra email trafic.

[zoecarver]

• Apply Louis' comment about has_arrow

[zoecarver]

Okay, this is now ready for re-review!

[cjdb]

Please also add tests to ensure that all standard library iterators are compatible with iterator_traits. It would be a shame if we introduced a regression.

libcxx/include/iterator

702–707

I know I wrote this, but it'd be better if we used nested requires expressions so the requirements can be congruently ordered with the wording.

719–722

I'd prefer that we forward declare __iterator_traits and then define it under [iterator.traits]/3.3. That's what we did for [[ https://reviews.llvm.org/D96657#inline-913994 | common_reference ]], and I think that helped improve readability. Similarly elsewhere.

753

To distinguish this from member_pointer_or_void we should rename to member_pointer_or_arrow_or_void

810

Typo (scan the comments for other typos such as iteratortraits too).

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

28–38

libcxx/test/std/iterators/iterator.primitives/iterator.traits/pointer.pass.cpp already covers this case.

40–49

libcxx/test/std/iterators/iterator.primitives/iterator.traits/const_pointer.pass.cpp has 5/6 of these tests. Please move the iterator_concept case there.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/volatile_pointer.pass.cpp and libcxx/test/std/iterators/iterator.primitives/iterator.traits/const_volatile_pointer.pass.cpp will need updates too.

50

It'd be great if you could section off each subset of tests with the paragraph numbers they correspond to.

50–58

I think these should be std::same_as<VectorIteratorTraits::member, std::vector<int>::iterator::member>. I don't particularly care about the concrete types they resolve to, but I do care that they match the members of said iterator.

I also notice there's no test for whether or not vector iterators have iterator_concept.

109

Please indicate why. It took me a moment to realise this is expected.

127

Please also add tests for the minimalistic iterator archetypes in test/libcxx/iterators/iterator.requirements/iterator.assoc.types/iterator.traits/iterator_traits_cpp17_iterators.h.

154

I think we should assert that each of these types actually meet/don't meet the cpp17-*-iterator requirements we expect them to. Also, @ldionne asked that the concepts be renamed to __iterator_traits_detail::cpp17_*_iterator, so I think we should reflect that update here.

245

I think declaring the operator as deleted would be a good idea.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp

103

In that case, please switch to feature-test macros.

[• Quuxplusone]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

50–58

I do care what they resolve to. Leave them as-is, i.e., static_assert(std::same_as<VectorIteratorTraits::value_type, int>); is the best way to write it. (Although, if you want to name the typedef VIT to save on column-width and thus fix that one ugly linebreak, that'd be a good idea.)

245

No, the point of this test is that the operator is missing (not in overload resolution at all). Anyway, this way is shorter, which is good.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp

103

I guess the real question is, why is this test here at all? Maybe it should move to a different test file, which REQUIRES: c++03 || c++11 || c++14 || c++17.

[zoecarver]

libcxx/include/iterator

719–722

IMHO forward declaring types when we don't have to introduces a lot of complexity and makes the implementation much more difficult to read. Especially if I'm looking for the definition of something later.

I wasn't a reviewer on that patch, but if I were I would have pushed for a different implementation, or at least different names. I find it super confusing to have __common_ref forward declared and then used before being defined. Not to mention the presence of the following names __common_reference_sub_bullet{1,2,3} and __common_ref_{C,D}. When future me is trying to find the implementation of something in libc++, I'd rather not have to do the archeology to decode such names, and having them be forward declared, make it that much more difficult to find the actual implementation.

(Side note: I think we should really discourage naming thing after bullets in the standard. Those change fairly frequently, and the names of things in libc++ hardly ever change. Not only does it make things harder to read/understand, but will likely become incorrect soon.)

However, I agree that this could be made more readable. WDYT about removing __iterator_traits (I don't see any reason we can't just implement iterator_traits directly), and moving all the "implementation details" above so that we can just have one specialization after another. I know this still means we have to put the final "Otherwise" first, but I don't think that adds any complexity, it's the natural way to implement something (I'm sure when creating concepts the committee didn't expect everyone to define the "default" case last using a forward declared class).

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

50–58

I also notice there's no test for whether or not vector iterators have iterator_concept.

I'll add some tests.

I do care what they resolve to. Leave them as-is, i.e., static_assert(std::same_as<VectorIteratorTraits::value_type, int>); is the best way to write it.

I agree. I think it makes more sense to use the concrete types.

(Although, if you want to name the typedef VIT to save on column-width and thus fix that one ugly linebreak, that'd be a good idea.)

I thought clang format wasn't going to generate line breaks anymore...

[zoecarver]

libcxx/include/iterator

702–707

Not sure I follow. Do you want me to make this two requires expressions, or do you want me to add __has_member_{difference_type,value_type}?

[cjdb]

libcxx/include/iterator

719–722

WDYT about removing __iterator_traits (I don't see any reason we can't just implement iterator_traits directly), and moving all the "implementation details" above so that we can just have one specialization after another.

@tcanens made a comment early on in this patch's review pointing out that the primary template mustn't conflict with others' specialisations.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

50–58

I do care what they resolve to. Leave them as-is, i.e., static_assert(std::same_as<VectorIteratorTraits::value_type, int>); is the best way to write it.

I agree. I think it makes more sense to use the concrete types.

In that case, keep them, and please add the tests I've requested. It's important that VectorIteratorTraits::member is std::vector<int>::iterator::member.

(Although, if you want to name the typedef VIT to save on column-width and thus fix that one ugly linebreak, that'd be a good idea.)

I thought clang format wasn't going to generate line breaks anymore...

Cryptic names hurt readability far more than benign whitespace.

[cjdb]

libcxx/include/iterator

702–707

requires {
  typename _Ip::value_type;
  typename _Ip::difference_type;
  requires __has_member_reference<_Ip>; // this is a nested-requires-expression
  requires __has_member_iterator_category<_Ip>;
};

However, you did point out that the ordering of wording is subject to change, so perhaps this is a moot point to discuss.

[cjdb]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

245

In that case the type should be renamed to indicate this. "Missing" is ambiguous.

[zoecarver]

libcxx/include/iterator

810

Ah, phab can't display \x{AD}. Great. (Not that we should really be using this character anyway...)

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

127

I'll test iterator_traits_cpp17_iterator, iterator_traits_cpp17_input_iterator, iterator_traits_cpp17_forward_iterator. I think everything else is accounted for.

154

Sorry, I'm not sure I understand exactly what you're asking for here. Could you elaborate? Do you want me to update LegacyInputNoValueType and put it in a namespace?

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp

103

I guess the real question is, why is this test here at all? Maybe it should move to a different test file, which REQUIRES: c++03 || c++11 || c++14 || c++17.

This seems pretty in line with the other tests in this file. I could argue that we don't need this test to begin with, or that we should be testing this another way, but I won't, because I'm not sure it matters too much :)

In that case, please switch to feature-test macros.

Well, we haven't yet added the __cpp_lib_ranges macro. Was there another macro you were thinking of? I think it's fine to just use _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_HAS_NO_CONCEPTS) because those are already used all over the test suite. To be honest, we could probably use _LIBCPP_HAS_NO_RANGES as well. I was just trying to limit the number of libc++-specific macros we use in "non-libc++" tests.

[cjdb]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

154

Renaming to s/Legacy/IteratorTraitsCpp17/ should do the trick.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp

103

Was there another macro you were thinking of?

Specifically TEST_STD_VER <= 17 || !defined(__cpp_lib_concepts). That eliminates the implementation-detail names in userspace altogether :)

[zoecarver]

• Apply review comments
• Format
• Move around iterator_traits impl so that all __iterator_traits specializations are in a row.

[zoecarver]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

154

I don't want to start bike shedding the name, but some of these names get fairly long. I'd really prefer to use "Legacy" especially in the tests. @ldionne wdyt?

[zoecarver]

• Remove internal macros from tests.

[cjdb]

I've pinged comments that I think either have been missed or warrant discussion if you disagree with my commentary.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

28–38

Ping.

40–49

Ping.

50

Ping.

115

Please don't forget std::vector<bool>::iterator and const_iterators (I'll turn a blind eye toward all containers' reverse_iterator members if std::reverse_iterator is tested).

125–132

Please don't forget the multis and local_iterators.

134–146

Please don't forget std::reverse_iterator, the filesystem iterators, and the regex iterators.

[ldionne]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

154

Just to clarify, I asked that the __cpp17_xxx_iterator helper concepts be moved to a namespace after we determined that they were not the same as the Cpp17XXXIterator concepts in the Standard, so as to avoid making them easy to mistake with those concepts.

I don't understand why/how that affects the naming of iterators in the tests. As a result, LegacyXXXIterator like done below currently seems acceptable to me.

[cjdb]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

154

WFM, I just wanted to bring light to it.

[zoecarver]

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

28–38

Removed.

40–49

I think this is done, no? I just haven't removed the tests from here as well.

50

I haven't done this yet. This will take some time. I just uploaded a new diff without this change, you can review the rest of the diff, and I'll upload this part when I'm done.

[zoecarver]

• Add all c++ stdlib iterators.
• * Apply remaining review comments.

[ldionne]

This LGTM from my perspective. I think we can go back and polish some of the naming (honestly I think names like member_pointer_or_arrow_or_void are difficult to read and reason about), however I don't want to hold up this important review which blocks several dependencies from making progress because of that.

This LGTM and I think we should ship this as-is unless a reviewer has strong concerns that have not been alleviated yet.

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

50

IMO, I'm not sure the cost/benefit ratio is sufficient to do it. At least it's definitely not blocking.

[zoecarver]

• Add a test for regex_token_iterator.

[zoecarver]

I will be committing when the CI passes.

[zoecarver]

• Remove test for iterator_traits<void*> pre-C++17. void can't be referenced so this was failing with a hard error.

[ldionne]

Commandeering to fix CI.

[ldionne]

Try to fix CI.

libcxx/include/iterator

 #include <concepts>
 
 namespace std
 {
 template<class> struct incrementable_traits;       // since C++20
 template<class> struct indirectly_readable_traits; // since C++20
 
 template<class Iterator>
-struct iterator_traits
-{
-    typedef typename Iterator::difference_type difference_type;
-    typedef typename Iterator::value_type value_type;
-    typedef typename Iterator::pointer pointer;
-    typedef typename Iterator::reference reference;
-    typedef typename Iterator::iterator_category iterator_category;
-};
+struct iterator_traits;
 
 template<class T>
-struct iterator_traits<T*>
-{
-    typedef ptrdiff_t difference_type;
-    typedef T value_type;
-    typedef T* pointer;
-    typedef T& reference;
-    typedef random_access_iterator_tag iterator_category;
-};
+  requires is_object_v<T>                    // since C++20
+struct iterator_traits<T*>;
 
 template<dereferenceable T>
   using iter_reference_t = decltype(*declval<T&>());
 
 template<class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
 struct iterator
 {

 private:
     struct __two {char __lx; char __lxx;};
     template <class _Up> static __two __test(...);
     template <class _Up> static char __test(typename _Up::iterator_concept* = nullptr);
 public:
     static const bool value = sizeof(__test<_Tp>(nullptr)) == 1;
 };
 
-template <class _Iter, bool> struct __iterator_traits_impl {};
-
-template <class _Iter>
-struct __iterator_traits_impl<_Iter, true>
-{
-    typedef typename _Iter::difference_type   difference_type;
-    typedef typename _Iter::value_type        value_type;
-    typedef typename _Iter::pointer           pointer;
-    typedef typename _Iter::reference         reference;
-    typedef typename _Iter::iterator_category iterator_category;
-};
-
 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
 // The `cpp17-*-iterator` exposition-only concepts are easily confused with the Cpp17*Iterator tables,
 // so they've been banished to a namespace that makes it obvious they have a niche use-case.
 namespace __iterator_traits_detail {
 template<class _Ip>
 concept __cpp17_iterator =
   requires(_Ip __i) {
requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) {
     { __i -= __n } -> same_as<_Ip&>;
     { __i +  __n } -> same_as<_Ip>;
     { __n +  __i } -> same_as<_Ip>;
     { __i -  __n } -> same_as<_Ip>;
     { __i -  __i } -> same_as<decltype(__n)>;
     {  __i[__n]  } -> convertible_to<iter_reference_t<_Ip>>;
   };
 } // namespace __iterator_traits_detail
-#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+template<class _Ip>
+concept __has_member_reference = requires { typename _Ip::reference; };
+
+template<class _Ip>
+concept __has_member_pointer = requires { typename _Ip::pointer; };
+
+template<class _Ip>
+concept __has_member_iterator_category = requires { typename _Ip::iterator_category; };
+
+template<class _Ip>
+concept __specifies_members =
+  __has_member_reference<_Ip> &&
+  __has_member_iterator_category<_Ip> &&
+  requires {
+    typename _Ip::difference_type;
+    typename _Ip::value_type;
+  };
+
+template<class>
+struct __iterator_traits_member_pointer_or_void {
+  using type = void;
+};
+
+template<__has_member_pointer _Tp>
+struct __iterator_traits_member_pointer_or_void<_Tp> {
+  using type = typename _Tp::pointer;
+};
+
+// [iterator.traits]/3.4
+// Otherwise, `iterator_traits<I>` has no members by any of the above names.
+template<class>
+struct __iterator_traits {};
+
+// [iterator.traits]/3.1
+// If `I` has valid ([temp.deduct]) member types `difference­type`, `value­type`, `reference`, and
+// `iterator­category`, then `iterator­traits<I>` has the following publicly accessible members:
+template<__specifies_members _Ip>
+struct __iterator_traits<_Ip> {
+  using iterator_category  = typename _Ip::iterator_category;
+  using value_type         = typename _Ip::value_type;
+  using difference_type    = typename _Ip::difference_type;
+  using pointer            = typename __iterator_traits_member_pointer_or_void<_Ip>::type;
+  using reference          = typename _Ip::reference;
+};
+
+// TODO: do we need __iterator_traits_detail?
+template<class _Tp>
+concept __cpp17_iterator_missing_members =
+  !__specifies_members<_Tp> &&
+  __iterator_traits_detail::__cpp17_iterator<_Tp>;
+
+template<class _Tp>
+concept __cpp17_input_iterator_missing_members =
+  __cpp17_iterator_missing_members<_Tp> &&
+  __iterator_traits_detail::__cpp17_input_iterator<_Tp>;
+
+// Otherwise, `pointer` names `void`.
+template<class>
+struct __iterator_traits_member_pointer { using type = void; };
+
+// [iterator.traits]/3.2.1
+// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type.
+template<__has_member_pointer _Ip>
+struct __iterator_traits_member_pointer<_Ip> { using type = typename _Ip::pointer; };
+
+// Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that
+// type.
+template<class _Ip>
+concept __has_arrow =
+  !__has_member_pointer<_Ip> &&
+  requires(_Ip& __i) {
+    __i.operator->();
+  };
+
+template<__has_arrow _Ip>
+struct __iterator_traits_member_pointer<_Ip> {
+  using type = decltype(declval<_Ip&>().operator->());
+};
+
+// Otherwise, `reference` names `iter­reference­t<I>`.
+template<class _Ip>
+struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; };
+
+// [iterator.traits]/3.2.2
+// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type.
+template<__has_member_reference _Ip>
+struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; };
+
+// [iterator.traits]/3.2.3.4
+// input_iterator_tag
+template<class _Ip>
+struct __deduce_iterator_category {
+  using type = input_iterator_tag;
+};
+
+// [iterator.traits]/3.2.3.1
+// `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise
+template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip>
+struct __deduce_iterator_category<_Ip> {
+  using type = random_access_iterator_tag;
+};
+
+// [iterator.traits]/3.2.3.2
+// `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise
+template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>
+struct __deduce_iterator_category<_Ip> {
+  using type = bidirectional_iterator_tag;
+};
+
+// [iterator.traits]/3.2.3.3
+// `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise
+template<__iterator_traits_detail::__cpp17_forward_iterator _Ip>
+struct __deduce_iterator_category<_Ip> {
+  using type = forward_iterator_tag;
+};
+
+template<class _Ip>
+struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {};
+
+// [iterator.traits]/3.2.3
+// If the qualified-id `I::iterator­category` is valid and denotes a type, `iterator­category` names
+// that type.
+template<__has_member_iterator_category _Ip>
+struct __iterator_traits_iterator_category<_Ip> {
+  using type = typename _Ip::iterator_category;
+};
+
+// [iterator.traits]/3.2
+// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`,
+// `iterator­traits<I>` has the following publicly accessible members:
+template<__cpp17_input_iterator_missing_members _Ip>
+struct __iterator_traits<_Ip> {
+  using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type;
+  using value_type        = typename indirectly_readable_traits<_Ip>::value_type;
+  using difference_type   = typename incrementable_traits<_Ip>::difference_type;
+  using pointer           = typename __iterator_traits_member_pointer<_Ip>::type;
+  using reference         = typename __iterator_traits_member_reference<_Ip>::type;
+};
+
+// otherwise, it names void.
+template<class>
+struct __iterator_traits_difference_type { using type = void; };
+
+// If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then
+// `difference_type` names that type;
+template<class _Ip>
+requires requires { typename incrementable_traits<_Ip>::difference_type; }
+struct __iterator_traits_difference_type<_Ip> {
+  using type = typename incrementable_traits<_Ip>::difference_type;
+};
+
+// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then
+// `iterator_traits<I>` has the following publicly accessible members:
+template<__cpp17_iterator_missing_members _Ip>
+struct __iterator_traits<_Ip> {
+  using iterator_category = output_iterator_tag;
+  using value_type        = void;
+  using difference_type   = typename __iterator_traits_difference_type<_Ip>::type;
+  using pointer           = void;
+  using reference         = void;
+};
+
+template<class _Ip>
+struct iterator_traits : __iterator_traits<_Ip> {
+  using __primary_template = iterator_traits;
+};
+
+#else // !defined(_LIBCPP_HAS_NO_RANGES)
 
 template <class _Iter, bool> struct __iterator_traits {};
 
+template <class _Iter, bool> struct __iterator_traits_impl {};
+
+template <class _Iter>
+struct __iterator_traits_impl<_Iter, true>
+{
+    typedef typename _Iter::difference_type   difference_type;
+    typedef typename _Iter::value_type        value_type;
+    typedef typename _Iter::pointer           pointer;
+    typedef typename _Iter::reference         reference;
+    typedef typename _Iter::iterator_category iterator_category;
+};
+
 template <class _Iter>
 struct __iterator_traits<_Iter, true>
     :  __iterator_traits_impl
       <
         _Iter,
         is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
         is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value
       >
 {};
 
 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
 //    exists.  Else iterator_traits<Iterator> will be an empty class.  This is a
 //    conforming extension which allows some programs to compile and behave as
 //    the client expects instead of failing at compile time.
 
 template <class _Iter>
 struct _LIBCPP_TEMPLATE_VIS iterator_traits
     : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
 
   using __primary_template = iterator_traits;
 };
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 template<class _Tp>
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+requires is_object_v<_Tp>
+#endif
 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*>
 {
     typedef ptrdiff_t difference_type;
     typedef typename remove_cv<_Tp>::type value_type;
     typedef _Tp* pointer;
     typedef _Tp& reference;
     typedef random_access_iterator_tag iterator_category;
 #if _LIBCPP_STD_VER > 17
     typedef contiguous_iterator_tag    iterator_concept;
 #endif
 };
 
 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
 struct __has_iterator_category_convertible_to
     : _BoolConstant<is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
 {};
 
 template <class _Tp, class _Up>
 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
 
 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
 struct __has_iterator_concept_convertible_to
     : _BoolConstant<is_convertible<typename _Tp::iterator_concept, _Up>::value>
 {};
 
 template <class _Tp, class _Up>
 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
 
 template <class _Tp>
 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
 
 template <class _Tp>
 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
 
 // __is_cpp17_contiguous_iterator determines if an iterator is contiguous,
 // either because it advertises itself as such (in C++20) or because it
 // is a pointer type or a known trivial wrapper around a pointer type,
 // such as __wrap_iter<T*>.
 //
 #if _LIBCPP_STD_VER > 17
 template <class _Tp>
 struct __is_cpp17_contiguous_iterator : _Or<

 {
    __i += __n;
 }
 
 template <class _InputIter, class _Distance>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 void advance(_InputIter& __i, _Distance __orig_n)
 {
     _LIBCPP_ASSERT(__orig_n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
                    "Attempt to advance(it, n) with negative n on a non-bidirectional iterator");
     typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
     _IntegralSize __n = __orig_n;
     _VSTD::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
 }
 
 template <class _InputIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14

libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// template<class T>
+// struct iterator_traits;
+
+#include <iterator>
+#include <string>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class Traits>
+constexpr bool has_iterator_concept_v = requires {
+  typename Traits::iterator_concept;
+};
+
+using PointerIteratorTraits = std::iterator_traits<int*>;
+static_assert(std::same_as<PointerIteratorTraits::iterator_category,
+                           std::random_access_iterator_tag>);
+static_assert(std::same_as<PointerIteratorTraits::value_type, int>);
+static_assert(
+    std::same_as<PointerIteratorTraits::difference_type, std::ptrdiff_t>);
+static_assert(std::same_as<PointerIteratorTraits::reference, int&>);
+static_assert(std::same_as<PointerIteratorTraits::pointer, int*>);
+static_assert(std::same_as<PointerIteratorTraits::iterator_concept,
+                           std::contiguous_iterator_tag>);
+
+using ConstPointerIteratorTraits = std::iterator_traits<const int*>;
+static_assert(std::same_as<ConstPointerIteratorTraits::iterator_category,
+                           std::random_access_iterator_tag>);
+static_assert(std::same_as<ConstPointerIteratorTraits::value_type, int>);
+static_assert(
+    std::same_as<ConstPointerIteratorTraits::difference_type, std::ptrdiff_t>);
+static_assert(std::same_as<ConstPointerIteratorTraits::reference, const int&>);
+static_assert(std::same_as<ConstPointerIteratorTraits::pointer, const int*>);
+static_assert(std::same_as<ConstPointerIteratorTraits::iterator_concept,
+                           std::contiguous_iterator_tag>);
+
+using VectorIteratorTraits = std::iterator_traits<std::vector<int>::iterator>;
+static_assert(std::same_as<VectorIteratorTraits::iterator_category,
+                           std::random_access_iterator_tag>);
+static_assert(std::same_as<VectorIteratorTraits::value_type, int>);
+static_assert(
+    std::same_as<VectorIteratorTraits::difference_type, std::ptrdiff_t>);
+static_assert(std::same_as<VectorIteratorTraits::reference, int&>);
+static_assert(std::same_as<VectorIteratorTraits::pointer, int*>);
+
+using StringIteratorTraits = std::iterator_traits<std::string::iterator>;
+static_assert(std::same_as<StringIteratorTraits::iterator_category,
+                           std::random_access_iterator_tag>);
+static_assert(std::same_as<StringIteratorTraits::value_type, char>);
+static_assert(
+    std::same_as<StringIteratorTraits::difference_type, std::ptrdiff_t>);
+static_assert(std::same_as<StringIteratorTraits::reference, char&>);
+static_assert(std::same_as<StringIteratorTraits::pointer, char*>);
+
+struct AllMembers {
+  struct iterator_category {};
+  struct value_type {};
+  struct difference_type {};
+  struct reference {};
+  struct pointer {};
+};
+using AllMembersTraits = std::iterator_traits<AllMembers>;
+static_assert(std::same_as<AllMembersTraits::iterator_category,
+                           AllMembers::iterator_category>);
+static_assert(
+    std::same_as<AllMembersTraits::value_type, AllMembers::value_type>);
+static_assert(std::same_as<AllMembersTraits::difference_type,
+                           AllMembers::difference_type>);
+static_assert(std::same_as<AllMembersTraits::reference, AllMembers::reference>);
+static_assert(std::same_as<AllMembersTraits::pointer, AllMembers::pointer>);
+static_assert(!has_iterator_concept_v<AllMembersTraits>);
+
+struct NoPointerMember {
+  struct iterator_category {};
+  struct value_type {};
+  struct difference_type {};
+  struct reference {};
+  // ignored, because NoPointerMember is not a LegacyInputIterator:
+  value_type* operator->() const;
+};
+using NoPointerMemberTraits = std::iterator_traits<NoPointerMember>;
+static_assert(std::same_as<NoPointerMemberTraits::iterator_category,
+                           NoPointerMember::iterator_category>);
+static_assert(std::same_as<NoPointerMemberTraits::value_type,
+                           NoPointerMember::value_type>);
+static_assert(std::same_as<NoPointerMemberTraits::difference_type,
+                           NoPointerMember::difference_type>);
+static_assert(
+    std::same_as<NoPointerMemberTraits::reference, NoPointerMember::reference>);
+static_assert(std::same_as<NoPointerMemberTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<NoPointerMemberTraits>);
+
+struct IterConcept {
+  struct iterator_category {};
+  struct iterator_concept {}; // ignored
+  struct value_type {};
+  struct difference_type {};
+  struct reference {};
+  struct pointer {};
+};
+using IterConceptTraits = std::iterator_traits<IterConcept>;
+static_assert(std::same_as<IterConceptTraits::iterator_category,
+                           IterConcept::iterator_category>);
+static_assert(
+    std::same_as<IterConceptTraits::value_type, IterConcept::value_type>);
+static_assert(std::same_as<IterConceptTraits::difference_type,
+                           IterConcept::difference_type>);
+static_assert(
+    std::same_as<IterConceptTraits::reference, IterConcept::reference>);
+static_assert(std::same_as<IterConceptTraits::pointer, IterConcept::pointer>);
+static_assert(!has_iterator_concept_v<IterConceptTraits>);
+
+struct LegacyInput {
+  struct iterator_category {};
+  struct value_type {};
+  struct reference {
+    operator value_type() const;
+  };
+
+  friend bool operator==(LegacyInput, LegacyInput);
+  reference operator*() const;
+  LegacyInput& operator++();
+  LegacyInput operator++(int);
+};
+template <>
+struct std::incrementable_traits<LegacyInput> {
+  using difference_type = short;
+};
+using LegacyInputTraits = std::iterator_traits<LegacyInput>;
+static_assert(std::same_as<LegacyInputTraits::iterator_category,
+                           LegacyInput::iterator_category>);
+static_assert(
+    std::same_as<LegacyInputTraits::value_type, LegacyInput::value_type>);
+static_assert(std::same_as<LegacyInputTraits::difference_type, short>);
+static_assert(
+    std::same_as<LegacyInputTraits::reference, LegacyInput::reference>);
+static_assert(std::same_as<LegacyInputTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<LegacyInputTraits>);
+
+struct LegacyInputNoValueType {
+  struct not_value_type {};
+  using difference_type = int; // or any signed integral type
+  struct reference {
+    operator not_value_type() const;
+  };
+
+  friend bool operator==(LegacyInputNoValueType, LegacyInputNoValueType);
+  reference operator*() const;
+  LegacyInputNoValueType& operator++();
+  LegacyInputNoValueType operator++(int);
+};
+template <>
+struct std::indirectly_readable_traits<LegacyInputNoValueType> {
+  using value_type = LegacyInputNoValueType::not_value_type;
+};
+using LegacyInputNoValueTypeTraits =
+    std::iterator_traits<LegacyInputNoValueType>;
+static_assert(std::same_as<LegacyInputNoValueTypeTraits::iterator_category,
+                           std::input_iterator_tag>);
+static_assert(std::same_as<LegacyInputNoValueTypeTraits::value_type,
+                           LegacyInputNoValueType::not_value_type>);
+static_assert(std::same_as<LegacyInputNoValueTypeTraits::difference_type, int>);
+static_assert(std::same_as<LegacyInputNoValueTypeTraits::reference,
+                           LegacyInputNoValueType::reference>);
+static_assert(std::same_as<LegacyInputNoValueTypeTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<LegacyInputNoValueTypeTraits>);
+
+struct LegacyForward {
+  struct not_value_type {};
+
+  friend bool operator==(LegacyForward, LegacyForward);
+  const not_value_type& operator*() const;
+  LegacyForward& operator++();
+  LegacyForward operator++(int);
+};
+template <>
+struct std::indirectly_readable_traits<LegacyForward> {
+  using value_type = LegacyForward::not_value_type;
+};
+template <>
+struct std::incrementable_traits<LegacyForward> {
+  using difference_type = short; // or any signed integral type
+};
+using LegacyForwardTraits = std::iterator_traits<LegacyForward>;
+static_assert(std::same_as<LegacyForwardTraits::iterator_category,
+                           std::forward_iterator_tag>);
+static_assert(std::same_as<LegacyForwardTraits::value_type,
+                           LegacyForward::not_value_type>);
+static_assert(std::same_as<LegacyForwardTraits::difference_type, short>);
+static_assert(std::same_as<LegacyForwardTraits::reference,
+                           const LegacyForward::not_value_type&>);
+static_assert(std::same_as<LegacyForwardTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<LegacyForwardTraits>);
+
+struct LegacyBidirectional {
+  struct value_type {};
+
+  friend bool operator==(LegacyBidirectional, LegacyBidirectional);
+  const value_type& operator*() const;
+  LegacyBidirectional& operator++();
+  LegacyBidirectional operator++(int);
+  LegacyBidirectional& operator--();
+  LegacyBidirectional operator--(int);
+  friend short operator-(LegacyBidirectional, LegacyBidirectional);
+};
+using LegacyBidirectionalTraits = std::iterator_traits<LegacyBidirectional>;
+static_assert(std::same_as<LegacyBidirectionalTraits::iterator_category,
+                           std::bidirectional_iterator_tag>);
+static_assert(std::same_as<LegacyBidirectionalTraits::value_type,
+                           LegacyBidirectional::value_type>);
+static_assert(std::same_as<LegacyBidirectionalTraits::difference_type, short>);
+static_assert(std::same_as<LegacyBidirectionalTraits::reference,
+                           const LegacyBidirectional::value_type&>);
+static_assert(std::same_as<LegacyBidirectionalTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<LegacyBidirectionalTraits>);
+
+// Almost a random access iterator except it is missing operator-(It, It).
+struct MissingMinusIterIter {
+  struct value_type {};
+
+  friend auto operator<=>(MissingMinusIterIter, MissingMinusIterIter) = default;
+  const value_type& operator*() const;
+  const value_type& operator[](long) const;
+  MissingMinusIterIter& operator++();
+  MissingMinusIterIter operator++(int);
+  MissingMinusIterIter& operator--();
+  MissingMinusIterIter operator--(int);
+  MissingMinusIterIter& operator+=(long);
+  MissingMinusIterIter& operator-=(long);
+
+  // Providing difference_type does not fully compensate for missing operator-(It, It).
+  friend MissingMinusIterIter operator-(MissingMinusIterIter, int);
+  friend MissingMinusIterIter operator+(MissingMinusIterIter, int);
+  friend MissingMinusIterIter operator+(int, MissingMinusIterIter);
+};
+template <>
+struct std::incrementable_traits<MissingMinusIterIter> {
+  using difference_type = short;
+};
+using MissingMinusIterIterTraits = std::iterator_traits<MissingMinusIterIter>;
+static_assert(std::same_as<MissingMinusIterIterTraits::iterator_category,
+                           std::bidirectional_iterator_tag>);
+static_assert(std::same_as<MissingMinusIterIterTraits::value_type,
+                           MissingMinusIterIter::value_type>);
+static_assert(std::same_as<MissingMinusIterIterTraits::difference_type, short>);
+static_assert(std::same_as<MissingMinusIterIterTraits::reference,
+                           const MissingMinusIterIter::value_type&>);
+static_assert(std::same_as<MissingMinusIterIterTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<MissingMinusIterIterTraits>);
+
+struct WrongSubscriptReturnType {
+  struct value_type {};
+
+  friend auto operator<=>(WrongSubscriptReturnType,
+                          WrongSubscriptReturnType) = default;
+  // The type of it[n] is not convertible to the type of *it; therefore, this is not random-access.
+  value_type& operator*() const;
+  const value_type& operator[](long) const;
+  WrongSubscriptReturnType& operator++();
+  WrongSubscriptReturnType operator++(int);
+  WrongSubscriptReturnType& operator--();
+  WrongSubscriptReturnType operator--(int);
+  WrongSubscriptReturnType& operator+=(long);
+  WrongSubscriptReturnType& operator-=(long);
+  friend short operator-(WrongSubscriptReturnType, WrongSubscriptReturnType);
+  friend WrongSubscriptReturnType operator-(WrongSubscriptReturnType, int);
+  friend WrongSubscriptReturnType operator+(WrongSubscriptReturnType, int);
+  friend WrongSubscriptReturnType operator+(int, WrongSubscriptReturnType);
+};
+using WrongSubscriptReturnTypeTraits =
+    std::iterator_traits<WrongSubscriptReturnType>;
+static_assert(std::same_as<WrongSubscriptReturnTypeTraits::iterator_category,
+                           std::bidirectional_iterator_tag>);
+static_assert(std::same_as<WrongSubscriptReturnTypeTraits::value_type,
+                           WrongSubscriptReturnType::value_type>);
+static_assert(
+    std::same_as<WrongSubscriptReturnTypeTraits::difference_type, short>);
+static_assert(std::same_as<WrongSubscriptReturnTypeTraits::reference,
+                           WrongSubscriptReturnType::value_type&>);
+static_assert(std::same_as<WrongSubscriptReturnTypeTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<WrongSubscriptReturnTypeTraits>);
+
+struct LegacyRandomAccess {
+  struct value_type {};
+
+  friend bool operator==(LegacyRandomAccess, LegacyRandomAccess);
+  friend bool operator<(LegacyRandomAccess, LegacyRandomAccess);
+  friend bool operator<=(LegacyRandomAccess, LegacyRandomAccess);
+  friend bool operator>(LegacyRandomAccess, LegacyRandomAccess);
+  friend bool operator>=(LegacyRandomAccess, LegacyRandomAccess);
+  const value_type& operator*() const;
+  const value_type& operator[](long) const;
+  LegacyRandomAccess& operator++();
+  LegacyRandomAccess operator++(int);
+  LegacyRandomAccess& operator--();
+  LegacyRandomAccess operator--(int);
+  LegacyRandomAccess& operator+=(long);
+  LegacyRandomAccess& operator-=(long);
+  friend short operator-(LegacyRandomAccess, LegacyRandomAccess);
+  friend LegacyRandomAccess operator-(LegacyRandomAccess, int);
+  friend LegacyRandomAccess operator+(LegacyRandomAccess, int);
+  friend LegacyRandomAccess operator+(int, LegacyRandomAccess);
+};
+using LegacyRandomAccessTraits = std::iterator_traits<LegacyRandomAccess>;
+static_assert(std::same_as<LegacyRandomAccessTraits::iterator_category,
+                           std::random_access_iterator_tag>);
+static_assert(std::same_as<LegacyRandomAccessTraits::value_type,
+                           LegacyRandomAccess::value_type>);
+static_assert(std::same_as<LegacyRandomAccessTraits::difference_type, short>);
+static_assert(std::same_as<LegacyRandomAccessTraits::reference,
+                           const LegacyRandomAccess::value_type&>);
+static_assert(std::same_as<LegacyRandomAccessTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<LegacyRandomAccessTraits>);
+
+struct LegacyRandomAccessSpaceship {
+  struct not_value_type {};
+  struct ReferenceConvertible {
+    operator not_value_type&() const;
+  };
+
+  friend auto operator<=>(LegacyRandomAccessSpaceship,
+                          LegacyRandomAccessSpaceship) = default;
+  not_value_type& operator*() const;
+  ReferenceConvertible operator[](long) const;
+  LegacyRandomAccessSpaceship& operator++();
+  LegacyRandomAccessSpaceship operator++(int);
+  LegacyRandomAccessSpaceship& operator--();
+  LegacyRandomAccessSpaceship operator--(int);
+  LegacyRandomAccessSpaceship& operator+=(long);
+  LegacyRandomAccessSpaceship& operator-=(long);
+  friend short operator-(LegacyRandomAccessSpaceship,
+                         LegacyRandomAccessSpaceship);
+  friend LegacyRandomAccessSpaceship operator-(LegacyRandomAccessSpaceship,
+                                               int);
+  friend LegacyRandomAccessSpaceship operator+(LegacyRandomAccessSpaceship,
+                                               int);
+  friend LegacyRandomAccessSpaceship operator+(int,
+                                               LegacyRandomAccessSpaceship);
+};
+template <>
+struct std::indirectly_readable_traits<LegacyRandomAccessSpaceship> {
+  using value_type = LegacyRandomAccessSpaceship::not_value_type;
+};
+template <>
+struct std::incrementable_traits<LegacyRandomAccessSpaceship> {
+  using difference_type = short; // or any signed integral type
+};
+using LegacyRandomAccessSpaceshipTraits =
+    std::iterator_traits<LegacyRandomAccessSpaceship>;
+static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::iterator_category,
+                           std::random_access_iterator_tag>);
+static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::value_type,
+                           LegacyRandomAccessSpaceship::not_value_type>);
+static_assert(
+    std::same_as<LegacyRandomAccessSpaceshipTraits::difference_type, short>);
+static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::reference,
+                           LegacyRandomAccessSpaceship::not_value_type&>);
+static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<LegacyRandomAccessSpaceshipTraits>);
+
+// For output iterators, value_type, difference_type, and reference may be void.
+struct BareLegacyOutput {
+  struct Empty {};
+  Empty operator*() const;
+  BareLegacyOutput& operator++();
+  BareLegacyOutput operator++(int);
+};
+using BareLegacyOutputTraits = std::iterator_traits<BareLegacyOutput>;
+static_assert(std::same_as<BareLegacyOutputTraits::iterator_category,
+                           std::output_iterator_tag>);
+static_assert(std::same_as<BareLegacyOutputTraits::value_type, void>);
+static_assert(std::same_as<BareLegacyOutputTraits::difference_type, void>);
+static_assert(std::same_as<BareLegacyOutputTraits::reference, void>);
+static_assert(std::same_as<BareLegacyOutputTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<BareLegacyOutputTraits>);
+
+// The operator- means we get difference_type.
+struct LegacyOutputWithMinus {
+  struct Empty {};
+  Empty operator*() const;
+  LegacyOutputWithMinus& operator++();
+  LegacyOutputWithMinus operator++(int);
+  friend short operator-(LegacyOutputWithMinus, LegacyOutputWithMinus);
+  // Lacking operator==, this is a LegacyIterator but not a LegacyInputIterator.
+};
+using LegacyOutputWithMinusTraits = std::iterator_traits<LegacyOutputWithMinus>;
+static_assert(std::same_as<LegacyOutputWithMinusTraits::iterator_category,
+                           std::output_iterator_tag>);
+static_assert(std::same_as<LegacyOutputWithMinusTraits::value_type, void>);
+static_assert(
+    std::same_as<LegacyOutputWithMinusTraits::difference_type, short>);
+static_assert(std::same_as<LegacyOutputWithMinusTraits::reference, void>);
+static_assert(std::same_as<LegacyOutputWithMinusTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<LegacyOutputWithMinusTraits>);
+
+struct LegacyOutputWithMemberTypes {
+  struct value_type {}; // ignored
+  struct reference {};  // ignored
+  using difference_type = long;
+
+  friend bool operator==(LegacyOutputWithMemberTypes,
+                         LegacyOutputWithMemberTypes);
+  reference operator*() const;
+  LegacyOutputWithMemberTypes& operator++();
+  LegacyOutputWithMemberTypes operator++(int);
+  friend short operator-(LegacyOutputWithMemberTypes,
+                         LegacyOutputWithMemberTypes); // ignored
+  // Since (*it) is not convertible to value_type, this is not a LegacyInputIterator.
+};
+using LegacyOutputWithMemberTypesTraits =
+    std::iterator_traits<LegacyOutputWithMemberTypes>;
+static_assert(std::same_as<LegacyOutputWithMemberTypesTraits::iterator_category,
+                           std::output_iterator_tag>);
+static_assert(
+    std::same_as<LegacyOutputWithMemberTypesTraits::value_type, void>);
+static_assert(
+    std::same_as<LegacyOutputWithMemberTypesTraits::difference_type, long>);
+static_assert(std::same_as<LegacyOutputWithMemberTypesTraits::reference, void>);
+static_assert(std::same_as<LegacyOutputWithMemberTypesTraits::pointer, void>);
+static_assert(!has_iterator_concept_v<LegacyOutputWithMemberTypesTraits>);
+
+struct LegacyRandomAccessSpecialized {
+  struct not_value_type {};
+
+  friend auto operator<=>(LegacyRandomAccessSpecialized,
+                          LegacyRandomAccessSpecialized) = default;
+  not_value_type& operator*() const;
+  not_value_type& operator[](long) const;
+  LegacyRandomAccessSpecialized& operator++();
+  LegacyRandomAccessSpecialized operator++(int);
+  LegacyRandomAccessSpecialized& operator--();
+  LegacyRandomAccessSpecialized operator--(int);
+  LegacyRandomAccessSpecialized& operator+=(long);
+  LegacyRandomAccessSpecialized& operator-=(long);
+  friend long operator-(LegacyRandomAccessSpecialized,
+                        LegacyRandomAccessSpecialized);
+  friend LegacyRandomAccessSpecialized operator-(LegacyRandomAccessSpecialized,
+                                                 int);
+  friend LegacyRandomAccessSpecialized operator+(LegacyRandomAccessSpecialized,
+                                                 int);
+  friend LegacyRandomAccessSpecialized operator+(int,
+                                                 LegacyRandomAccessSpecialized);
+};
+template <class I>
+requires std::same_as<
+    I, LegacyRandomAccessSpecialized> struct std::iterator_traits<I> {
+  using iterator_category = std::output_iterator_tag;
+  using value_type = short;
+  using difference_type = short;
+  using reference = short&;
+  using pointer = short*;
+};
+using LegacyRandomAccessSpecializedTraits =
+    std::iterator_traits<LegacyRandomAccessSpecialized>;
+static_assert(
+    std::same_as<LegacyRandomAccessSpecializedTraits::iterator_category,
+                 std::output_iterator_tag>);
+static_assert(
+    std::same_as<LegacyRandomAccessSpecializedTraits::value_type, short>);
+static_assert(
+    std::same_as<LegacyRandomAccessSpecializedTraits::difference_type, short>);
+static_assert(
+    std::same_as<LegacyRandomAccessSpecializedTraits::reference, short&>);
+static_assert(
+    std::same_as<LegacyRandomAccessSpecializedTraits::pointer, short*>);
+static_assert(!has_iterator_concept_v<LegacyRandomAccessSpecializedTraits>);
+
+using InputTestItereatorTraits = std::iterator_traits<input_iterator<int*> >;
+static_assert(std::same_as<InputTestItereatorTraits::iterator_category,
+                           std::input_iterator_tag>);
+static_assert(std::same_as<InputTestItereatorTraits::value_type, int>);
+static_assert(std::same_as<InputTestItereatorTraits::difference_type, long>);
+static_assert(std::same_as<InputTestItereatorTraits::reference, int&>);
+static_assert(std::same_as<InputTestItereatorTraits::pointer, int*>);
+static_assert(!has_iterator_concept_v<InputTestItereatorTraits>);
+
+using OutputTestItereatorTraits = std::iterator_traits<output_iterator<int*> >;
+static_assert(std::same_as<OutputTestItereatorTraits::iterator_category,
+                           std::output_iterator_tag>);
+static_assert(std::same_as<OutputTestItereatorTraits::value_type, void>);
+static_assert(std::same_as<OutputTestItereatorTraits::difference_type, long>);
+static_assert(std::same_as<OutputTestItereatorTraits::reference, int&>);
+static_assert(std::same_as<OutputTestItereatorTraits::pointer, int*>);
+static_assert(!has_iterator_concept_v<OutputTestItereatorTraits>);
+
+using ForwardTestIteratorTraits = std::iterator_traits<forward_iterator<int*> >;
+static_assert(std::same_as<ForwardTestIteratorTraits::iterator_category,
+                           std::forward_iterator_tag>);
+static_assert(std::same_as<ForwardTestIteratorTraits::value_type, int>);
+static_assert(std::same_as<ForwardTestIteratorTraits::difference_type, long>);
+static_assert(std::same_as<ForwardTestIteratorTraits::reference, int&>);
+static_assert(std::same_as<ForwardTestIteratorTraits::pointer, int*>);
+static_assert(!has_iterator_concept_v<ForwardTestIteratorTraits>);
+
+using BidirectionalTestIteratorTraits =
+    std::iterator_traits<bidirectional_iterator<int*> >;
+static_assert(std::same_as<BidirectionalTestIteratorTraits::iterator_category,
+                           std::bidirectional_iterator_tag>);
+static_assert(std::same_as<BidirectionalTestIteratorTraits::value_type, int>);
+static_assert(
+    std::same_as<BidirectionalTestIteratorTraits::difference_type, long>);
+static_assert(std::same_as<BidirectionalTestIteratorTraits::reference, int&>);
+static_assert(std::same_as<BidirectionalTestIteratorTraits::pointer, int*>);
+static_assert(!has_iterator_concept_v<BidirectionalTestIteratorTraits>);
+
+using RandomAccessTestIteratorTraits =
+    std::iterator_traits<random_access_iterator<int*> >;
+static_assert(std::same_as<RandomAccessTestIteratorTraits::iterator_category,
+                           std::random_access_iterator_tag>);
+static_assert(std::same_as<RandomAccessTestIteratorTraits::value_type, int>);
+static_assert(
+    std::same_as<RandomAccessTestIteratorTraits::difference_type, long>);
+static_assert(std::same_as<RandomAccessTestIteratorTraits::reference, int&>);
+static_assert(std::same_as<RandomAccessTestIteratorTraits::pointer, int*>);
+static_assert(!has_iterator_concept_v<RandomAccessTestIteratorTraits>);
+
+using ContiguousTestIteratorTraits =
+    std::iterator_traits<contiguous_iterator<int*> >;
+static_assert(std::same_as<ContiguousTestIteratorTraits::iterator_category,
+                           std::contiguous_iterator_tag>);
+static_assert(std::same_as<ContiguousTestIteratorTraits::value_type, int>);
+static_assert(
+    std::same_as<ContiguousTestIteratorTraits::difference_type, long>);
+static_assert(std::same_as<ContiguousTestIteratorTraits::reference, int&>);
+static_assert(std::same_as<ContiguousTestIteratorTraits::pointer, int*>);
+static_assert(!has_iterator_concept_v<ContiguousTestIteratorTraits>);

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.fail.cpp

int main(int, char**)
     {
     typedef std::iterator_traits<NotAnIteratorNoValue> T;
     typedef T::difference_type   DT; // expected-error-re {{no type named 'difference_type' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::value_type        VT; // expected-error-re {{no type named 'value_type' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::pointer           PT; // expected-error-re {{no type named 'pointer' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::reference         RT; // expected-error-re {{no type named 'reference' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::iterator_category CT; // expected-error-re {{no type named 'iterator_category' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     }
-
+#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_HAS_NO_CONCEPTS)
     {
     typedef std::iterator_traits<NotAnIteratorNoPointer> T;
     typedef T::difference_type   DT; // expected-error-re {{no type named 'difference_type' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::value_type        VT; // expected-error-re {{no type named 'value_type' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::pointer           PT; // expected-error-re {{no type named 'pointer' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::reference         RT; // expected-error-re {{no type named 'reference' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::iterator_category CT; // expected-error-re {{no type named 'iterator_category' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     }
-
+#endif // _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_HAS_NO_CONCEPTS)
     {
     typedef std::iterator_traits<NotAnIteratorNoReference> T;
     typedef T::difference_type   DT; // expected-error-re {{no type named 'difference_type' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::value_type        VT; // expected-error-re {{no type named 'value_type' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::pointer           PT; // expected-error-re {{no type named 'pointer' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::reference         RT; // expected-error-re {{no type named 'reference' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     typedef T::iterator_category CT; // expected-error-re {{no type named 'iterator_category' in 'std:{{.*}}:iterator_traits<{{.+}}>}}
     }

libcxx/test/std/iterators/iterator.primitives/iterator.traits/empty.pass.cpp

 public:
     static const bool value = sizeof(test<T>(0)) == 1;
 };
 
 int main(int, char**)
 {
     typedef std::iterator_traits<not_an_iterator> It;
     static_assert(!(has_value_type<It>::value), "");
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
+    static_assert(!(has_value_type<std::iterator_traits<void*> >::value));
+#endif
 
     return 0;
 }