Page MenuHomePhabricator

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

Authored by zoecarver on Sat, Apr 3, 10:41 PM.

Details

Reviewers
ldionne
EricWF
Mordante
cjdb
Group Reviewers
Restricted Project
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.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Herald added a reviewer: Restricted Project. · View Herald TranscriptSat, Apr 3, 10:41 PM
cjdb updated this revision to Diff 335133.Sat, Apr 3, 10:43 PM

removes zero-width joiners

I really like the mixing to the Standard's wording with the code, makes it a lot easier to follow and review!

libcxx/include/iterator
691

Does this hunk affect the synopsis?

711

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

720

Will __primary_template be used in a later patch?

734

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.

912

Please update the synopsis.

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 updated this revision to Diff 335174.Sun, Apr 4, 2:19 PM
cjdb marked 5 inline comments as done.

applies @Mordante's feedback

cjdb added inline comments.Sun, Apr 4, 4:39 PM
libcxx/include/iterator
691

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.

720

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

734

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 updated this revision to Diff 335206.Sun, Apr 4, 11:17 PM

rebases to activate CI

cjdb updated this revision to Diff 335720.Tue, Apr 6, 10:01 PM

rebases to activate CI

tcanens added a subscriber: tcanens.Wed, Apr 7, 6:51 PM
tcanens added inline comments.
libcxx/include/iterator
714

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 updated this revision to Diff 335990.Wed, Apr 7, 8:58 PM

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

cjdb updated this revision to Diff 336695.Sun, Apr 11, 2:35 PM
cjdb marked an inline comment as done.

rebases to activate CI

Mordante added inline comments.Tue, Apr 13, 11:07 AM
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 ;-)

The logic LGTM.

libcxx/include/iterator
721

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

744

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

860

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

914

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?

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 added inline comments.Tue, Apr 13, 2:01 PM
libcxx/include/iterator
721

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 added inline comments.Tue, Apr 13, 2:15 PM
libcxx/include/iterator
744

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.

914

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]?

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 added inline comments.
libcxx/include/iterator
914

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 added inline comments.Tue, Apr 13, 4:16 PM
libcxx/include/iterator
721

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
109–111

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 added inline comments.Wed, Apr 14, 12:23 PM
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 added inline comments.Wed, Apr 14, 12:52 PM
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
109–111

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 updated this revision to Diff 337805.Thu, Apr 15, 9:53 AM

rebases to activate CI

ldionne requested changes to this revision.Thu, Apr 15, 11:57 AM

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
703

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.

725

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

761–771

That way __has_arrow makes sense on its own.

This revision now requires changes to proceed.Thu, Apr 15, 11:57 AM
zoecarver commandeered this revision.Thu, Apr 15, 2:48 PM
zoecarver edited reviewers, added: cjdb; removed: zoecarver.
cjdb commandeered this revision.Thu, Apr 15, 2:53 PM
cjdb edited reviewers, added: zoecarver; removed: cjdb.
cjdb updated this revision to Diff 337913.Thu, Apr 15, 2:54 PM

rebases so @zoecarver can commandeer without issue

zoecarver commandeered this revision.Thu, Apr 15, 2:55 PM
zoecarver edited reviewers, added: cjdb; removed: zoecarver.

rebases so @zoecarver can commandeer without issue

Worked like a charm. Thanks!

zoecarver added inline comments.Thu, Apr 15, 3:57 PM
libcxx/include/iterator
725

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 updated this revision to Diff 337934.Thu, Apr 15, 4:23 PM

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

zoecarver updated this revision to Diff 337936.Thu, Apr 15, 4:25 PM
  • Base diff on correct commit.
cjdb added inline comments.Thu, Apr 15, 4:56 PM
libcxx/test/std/iterators/iterator.primitives/iterator.traits/cxx20_iterator_traits.compile.pass.cpp
72

TODO?

278

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

Do we still need this file?