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

[zoecarver]

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

72 ↗

(On Diff #337936)

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

278 ↗

(On Diff #337936)

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

723–728

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.

740–743

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.

774

To distinguish this from member_pointer_or_void we should rename to member_pointer_or_arrow_or_void

831

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

27–37 ↗

(On Diff #338203)

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

39–48 ↗

(On Diff #338203)

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.

49 ↗

(On Diff #338203)

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

49–57 ↗

(On Diff #338203)

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.

108 ↗

(On Diff #338203)

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

126 ↗

(On Diff #338203)

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.

153 ↗

(On Diff #338203)

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.

244 ↗

(On Diff #338203)

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

49–57 ↗

(On Diff #338203)

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

244 ↗

(On Diff #338203)

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

740–743

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

49–57 ↗

(On Diff #338203)

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

723–728

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

740–743

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

49–57 ↗

(On Diff #338203)

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

723–728

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

244 ↗

(On Diff #338203)

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

[zoecarver]

libcxx/include/iterator

831

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

126 ↗

(On Diff #338203)

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

153 ↗

(On Diff #338203)

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

153 ↗

(On Diff #338203)

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

153 ↗

(On Diff #338203)

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

114 ↗

(On Diff #338607)

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

124–131 ↗

(On Diff #338607)

Please don't forget the multis and local_iterators.

133–145 ↗

(On Diff #338607)

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

27–37 ↗

(On Diff #338203)

Ping.

39–48 ↗

(On Diff #338203)

Ping.

49 ↗

(On Diff #338203)

Ping.

[ldionne]

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

153 ↗

(On Diff #338203)

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

153 ↗

(On Diff #338203)

WFM, I just wanted to bring light to it.

[zoecarver]

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

27–37 ↗

(On Diff #338203)

Removed.

39–48 ↗

(On Diff #338203)

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

49 ↗

(On Diff #338203)

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

49 ↗

(On Diff #338203)

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.