This is an archive of the discontinued LLVM Phabricator instance.

[libcxx][test] `unordered_meow` iterators are not portably non-bidi
ClosedPublic

Authored by CaseyCarter on Jan 14 2022, 4:52 PM.

Details

Summary

MSVCSTL's are actually bidirectional.

Diff Detail

Event Timeline

CaseyCarter requested review of this revision.Jan 14 2022, 4:52 PM
CaseyCarter created this revision.
Herald added 1 blocking reviewer(s): Restricted Project. · View Herald TranscriptJan 14 2022, 4:52 PM
Quuxplusone requested changes to this revision.Jan 16 2022, 11:31 AM
Quuxplusone added a subscriber: Quuxplusone.

We should pick one mechanism (#ifdef _MSVC_STL_VERSION or LIBCPP_STATIC_ASSERT) and stick to it. But LGTM besides that.

libcxx/test/std/containers/unord/unord.map/iterator_concept_conformance.compile.pass.cpp
30–31

Throughout: I think we should eliminate all tests for !{sized_,}sentinel_for<X, Y> where X and Y are unrelated types. Basically this file should become

static_assert(std::forward_iterator<iterator>);
LIBCPP_STATIC_ASSERT(!std::bidirectional_iterator<iterator>);
static_assert(!std::indirectly_writable<iterator, value_type>);
static_assert(std::sentinel_for<iterator, iterator>);
static_assert(std::sentinel_for<iterator, const_iterator>);
static_assert(!std::sized_sentinel_for<iterator, iterator>);
static_assert(!std::sized_sentinel_for<iterator, const_iterator>);
static_assert(std::indirectly_movable<iterator, std::pair<int, int>*>);
static_assert(!std::indirectly_movable_storable<iterator, std::pair<int, int>*>);
static_assert(!std::indirectly_swappable<iterator, iterator>);

static_assert(std::forward_iterator<const_iterator>);
LIBCPP_STATIC_ASSERT(!std::bidirectional_iterator<const_iterator>);
static_assert(!std::indirectly_writable<const_iterator, value_type>);
static_assert(std::sentinel_for<const_iterator, iterator>);
static_assert(std::sentinel_for<const_iterator, const_iterator>);
static_assert(!std::sized_sentinel_for<const_iterator, iterator>);
static_assert(!std::sized_sentinel_for<const_iterator, const_iterator>);
static_assert(std::indirectly_movable<const_iterator, std::pair<int, int>*>);
static_assert(!std::indirectly_movable_storable<const_iterator, std::pair<int, int>*>);
static_assert(!std::indirectly_swappable<const_iterator, const_iterator>);

and then the same set of assertions but with s/iterator/local_iterator/g. Ditto in the other test files.

libcxx/test/std/containers/unord/unord.set/iterator_concept_conformance.compile.pass.cpp
27–32

We should take the same approach here as in the other test files you're touching.

This revision now requires changes to proceed.Jan 16 2022, 11:31 AM

Address review comments.

CaseyCarter marked 2 inline comments as done.Jan 17 2022, 9:19 PM
Quuxplusone added inline comments.
libcxx/test/std/containers/unord/unord.multimap/iterator_concept_conformance.compile.pass.cpp
66–67

Pre-existing: I suspect that the intent was to use value_type* here, not std::pair<int, int>* (and likewise value_type* in place of int* in the unordered_set tests). No action required, but if you want to fix it, go for it. (I don't think the change should affect the results of these static_asserts.)

ldionne accepted this revision.Jan 18 2022, 7:23 AM
This revision is now accepted and ready to land.Jan 18 2022, 7:23 AM
CaseyCarter added inline comments.Jan 18 2022, 11:43 AM
libcxx/test/std/containers/unord/unord.multimap/iterator_concept_conformance.compile.pass.cpp
66–67

value_type is pair<const int, int>. *declval<pair<const int, int>*>() = ranges::iter_move(some_iterator) is never going to be a valid expression, so all of these indirectly_movable{_storable,} tests would yield false. That said, I'm not sure what value these provide - it may make sense to remove them in a followup.

libcxx/test/std/containers/unord/unord.multimap/iterator_concept_conformance.compile.pass.cpp
66–67

Ah, indirectly_movable_storable (https://en.cppreference.com/w/cpp/iterator/indirectly_movable_storable) is much less sane than I had assumed. ;) I had pictured basically what you might call "indirectly_assignable_from."

The operative element in reality is that it checks std::assignable_from<std::iter_value_t<In>&, std::iter_rvalue_reference_t<In>> for the source iterator. So std::indirectly_movable_storable<unordered_map<K,V>::iterator, X> == false for all X, because std::assignable_from<unordered_map<K,V>::value_type, X> == false for all X.
So yeah, I see no value in these, and will submit a PR to remove them.

(This also suggests that the original STL chose map::value_type poorly — since set<int>::value_type is int not const int, then map<int,int>::value_type should have been pair<int,int> not pair<const int,int>. But that's water long under the bridge.)

CaseyCarter added inline comments.Jan 18 2022, 12:46 PM
libcxx/test/std/containers/unord/unord.multimap/iterator_concept_conformance.compile.pass.cpp
66–67

The intuition is "indirectly_copyable<I, O> requires *o = *i. indirectly_movable requires *o = ranges::iter_move(i). The _storable refinements require that transfer to be valid both directly, and indirectly through a variable of I's value_type via both construction and assignment.

And yes, map::value_type would be different today. There wasn't much they could have done differently in 1998 if they wanted to forbid changing map keys via iterator references - remember that Cpp17ForwardIterator must have a reference type of value_type& or const value_type&.