This is an archive of the discontinued LLVM Phabricator instance.

[libcxx] adds `cpp17-.*iterator` concepts for iterator_traits
ClosedPublic

Authored by cjdb on Apr 3 2021, 10:33 PM.

Details

Summary

The iterator_traits patch became too large for a concise review, so
the "bloat" —as it were— was moved into this patch. Also tests most
C++[98,17] iterator types to confirm backwards compatibility is
successful (regex iterators are intentionally not present, but directory
iterators are due to a peculiar error encountered while patching
iterator_traits).

Depends on D99461.

Diff Detail

Event Timeline

cjdb requested review of this revision.Apr 3 2021, 10:33 PM
cjdb created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptApr 3 2021, 10:34 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
cjdb updated this revision to Diff 335204.Apr 4 2021, 11:08 PM

rebases to activate CI

cjdb updated this revision to Diff 335414.Apr 5 2021, 11:48 PM

adds guards around the filesystem stuff

cjdb updated this revision to Diff 335718.Apr 6 2021, 9:54 PM

rebases to activate CI

tcanens added a subscriber: tcanens.Apr 7 2021, 6:34 PM
tcanens added inline comments.
libcxx/include/iterator
660

LWG3420?

cjdb updated this revision to Diff 335985.Apr 7 2021, 8:02 PM
cjdb marked an inline comment as done.

applies LWG3420 and (hopefully) fixes locale build failure

cjdb updated this revision to Diff 336694.Apr 11 2021, 2:35 PM

rebases to activate CI

Please mark LWG3420 as complete in the status. Haven't looked at the tests yet.

libcxx/include/iterator
541

I don't see any tests for iter_reference_t. I know it's used in the other implementations so no need to test it heavily, but a simple test file would probably be good.

652

How about _LIBCPP_HAS_NO_RANGES?

706

Why do we need __j too?

712

This could just be __i - __i which is what it says in the standard anyway.

zoecarver added inline comments.Apr 13 2021, 12:05 PM
libcxx/test/libcxx/iterators/iterator.requirements/iterator.assoc.types/iterator.traits/legacy_bidirectional_iterator.compile.pass.cpp
159

This should only have one template. Otherwise it's going to think int is the hash type ;)

libcxx/test/libcxx/iterators/iterator.requirements/iterator.assoc.types/iterator.traits/legacy_forward_iterator.compile.pass.cpp
70

Why isn't this a __legacy_forward_iterator?

151

Same comment. And for unordered_multiset. Also why not test (const_) local_iterator for both while you're at it?

ldionne added inline comments.Apr 14 2021, 1:56 PM
libcxx/include/iterator
532

I was surprised to see that we can't simply write typename _Tp&. I'm not sure what part of the concepts spec disallows it, do you know?

Would it make sense to rename this to __referenceable? Then below we would have

concept __dereferenceable = requires(_Tp& __t) {
  { *__t } -> __referenceable;
};

which I think is nicely consistent.

CaseyCarter added inline comments.Apr 14 2021, 2:40 PM
libcxx/include/iterator
532

I was surprised to see that we can't simply write typename _Tp&. I'm not sure what part of the concepts spec disallows it, do you know?

So was I! The _type-requirement_ grammar is "_type-requirement_: typename _nested-name-specifier<sub>opt</sub>_ _type-name_ ;", which doesn't allow any kind of adornments. From a very high level I suppose this makes sense - _Tp& is a type, but not the _name_ of a type - but it does mean that some things we expect to work don't.

There's probably material here for a 1-2 page paper to propose a change.

706

IIRC one of them should be mutable for the LHS of the assignment operators, and the other const for all other uses.

Once you've updated the line length for clang-format, please run the tests through clang-format a second time to remove the excess line-breaking and get them readable again.

libcxx/include/iterator
532

Re __can_reference versus __referenceable: This is matching the (current) draft wording in http://eel.is/c++draft/iterator.synopsis#concept:can-reference so I think it's defensible.

zoecarver added inline comments.Apr 14 2021, 2:57 PM
libcxx/include/iterator
532

I agree, __referenceable does sound better. But I think it's not outweighed by the benefit of having this code more or less match the standard wording verbatim.

cjdb marked 12 inline comments as done.Apr 14 2021, 8:38 PM
cjdb added inline comments.
libcxx/include/iterator
532

That name can be editorially changed (probably with LWG's permission), so I'm okay with choosing the name that makes more sense.

541

Oops, done.

706

Looks like it's legacy wording now?

libcxx/test/libcxx/iterators/iterator.requirements/iterator.assoc.types/iterator.traits/legacy_bidirectional_iterator.compile.pass.cpp
159

Done, everywhere :-)

libcxx/test/libcxx/iterators/iterator.requirements/iterator.assoc.types/iterator.traits/legacy_forward_iterator.compile.pass.cpp
70

Diagnostics report that it's not equality_comparable.

151

TIL about local_iterator.

cjdb updated this revision to Diff 337623.Apr 14 2021, 9:07 PM
cjdb marked 6 inline comments as done.

applies feedback

zoecarver accepted this revision as: zoecarver.Apr 14 2021, 9:38 PM

Thanks for the updates!

ldionne accepted this revision.Apr 15 2021, 9:41 AM

For each legacy iterator concept, would it be possible to create an archetype in the tests with the strict minimum requirements and check that it models the concept?

LGTM with CI passing and those tests added, unless you explain why they shouldn't be added.

libcxx/include/iterator
532

FWIW I would have been fine with keeping __can_reference after being told that it's what's used in the Standard. I'm fine either way, basically, feel free to do as you think is best.

This revision is now accepted and ready to land.Apr 15 2021, 9:41 AM
ldionne added inline comments.Apr 15 2021, 9:42 AM
libcxx/include/iterator
532

Oh, and thanks for the explanation here @CaseyCarter !

cjdb updated this revision to Diff 337804.Apr 15 2021, 9:52 AM

rebases to activate CI

ldionne added inline comments.Apr 15 2021, 11:23 AM
libcxx/include/iterator
659

@CaseyCarter Is it intended that the exposition-only concepts defined in http://eel.is/c++draft/iterator.traits#2 are not a literal translation of tables like http://eel.is/c++draft/iterator.cpp17#tab:iterator?

For example, the exposition-only concept cpp17-iterator adds the requirement { *i++ } -> can-reference, whereas the Cpp17Iterator concept does not contain that requirement.

There are similar differences in the other iterator concepts too, like operator-> being in the table but not in the exposition-only concept.

cjdb updated this revision to Diff 337862.Apr 15 2021, 12:07 PM
cjdb retitled this revision from [libcxx] adds `cpp17-.*iterator` concepts (as `__legacy_.*iterator`) to [libcxx] adds `cpp17-.*iterator` concepts for iterator_traits.
cjdb edited the summary of this revision. (Show Details)

adds archetype cpp17-iterators for testing

Per offline discussion, these have been renamed to __iterator_traits_detail::__cpp17_*_iterator to avoid confusion with the (subtly different) named requirements Cpp17*Iterator found in [iterator.cpp17].

cjdb updated this revision to Diff 337878.Apr 15 2021, 12:49 PM

rebases to activate CI

CaseyCarter added inline comments.Apr 15 2021, 1:03 PM
libcxx/include/iterator
659

@CaseyCarter Is it intended that the exposition-only concepts defined in http://eel.is/c++draft/iterator.traits#2 are not a literal translation of tables like http://eel.is/c++draft/iterator.cpp17#tab:iterator?

Yes. It is intended.

For example, the exposition-only concept cpp17-iterator adds the requirement { *i++ } -> can-reference, whereas the Cpp17Iterator concept does not contain that requirement.

True, but both Cpp17InputIterator and Cpp17OutputIterator effectively require something stronger that refines this requirement. I _think_ this was just a convenient shortcut,

There are similar differences in the other iterator concepts too, like operator-> being in the table but not in the exposition-only concept.

There's no way to express the -> requirement with concepts, since we don't generally know the member names (if any) of the value type. This is also why we dropped -> from the iterator concepts: generic code can't use -> because it doesn't know what it can put on the right-hand side.