Page MenuHomePhabricator

Implement P0433: deduction guides for <map>
ClosedPublic

Authored by Quuxplusone on Feb 23 2019, 6:41 PM.

Details

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
mclow.lists added inline comments.Feb 25 2019, 11:51 AM
test/std/containers/associative/map/map.cons/deduct.pass.cpp
46 ↗(On Diff #188067)

We have a macro called ASSERT_SAME_TYPE. You get it by including test_macros.h. Easier to read than std::is_same_v<...

mclow.lists added inline comments.Feb 25 2019, 11:53 AM
test/std/containers/associative/map/map.cons/deduct.fail.cpp
39 ↗(On Diff #188067)

It would be good if there were comments here explaining why this should fail.
Alternately, you could rename A -> NotAnAllocator

mclow.lists added inline comments.Feb 25 2019, 11:57 AM
test/std/containers/associative/map/map.cons/deduct.fail.cpp
44 ↗(On Diff #188067)

Please say why you expect these tests to fail.
Don't make a reader dig through the requirements to see if they're correct.
Take a look at "queue/queue.cons/deduct.fail.cpp", for example.

Use ASSERT_SAME_TYPE.
Better comments in .fail.cpp.
Fix some whitespace in my comments.

@mclow.lists ping!

Quuxplusone marked 4 inline comments as done.Feb 27 2019, 9:45 PM
Quuxplusone added inline comments.
include/iterator
541 ↗(On Diff #188676)

Incidentally, I have no opinion on whether this #ifndef is appropriate. It shouldn't break anything to define these aliases unconditionally, except that then I'd probably have to switch the usings to typedefs.

Remove an unused struct NotAnAllocator from the tests. NFC.

Quuxplusone retitled this revision from Implement deduction guides for <map> to Implement P0433: deduction guides for <map>.Mar 4 2019, 7:24 PM
Quuxplusone edited the summary of this revision. (Show Details)
ldionne added inline comments.Apr 30 2019, 1:28 PM
include/map
1474 ↗(On Diff #189182)

So those enable_ifs are required to avoid colliding with the map(initializer_list<pair<_Key, _Tp>>, _Allocator) deduction guide, correct?

Quuxplusone marked an inline comment as done.Apr 30 2019, 2:01 PM
Quuxplusone added inline comments.
include/map
1474 ↗(On Diff #189182)

Yes, that's right. They correspond directly with the SFINAE requirements in
http://eel.is/c++draft/container.adaptors.general#4

Here's a bunch of minor stylistic and comment nits.

I'm irked by the bit typedef typename __identity<_Allocator>::type allocator_type; in the definition of map/multimap.
What problem is that solving?

test/std/containers/associative/multimap/multimap.cons/deduct.fail.cpp
60 ↗(On Diff #189182)

What's going on here?
Does this test need to be uncommented? or removed?

65 ↗(On Diff #189182)

Missing motivation for this bit.

test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp
39 ↗(On Diff #189182)

All though this test, you have a mixture of pair<int, long> and pair<const int, long>. Are these changes relevant? If you need them for the equals calls, you can define a custom comparison:

template <class T1, class T2>
struct pair_eq
{
	bool operator()(const std::pair<      T1,       T2> &rhs, const std::pair<      T1,       T2> &lhs) const
	{ return lhs.first == rhs.first && lhs.second == rhs.second; }

	bool operator()(const std::pair<const T1, const T2> &rhs, const std::pair<const T1, const T2> &lhs) const
	{ return lhs.first == rhs.first && lhs.second == rhs.second; }

	bool operator()(const std::pair<      T1, const T2> &rhs, const std::pair<const T1, const T2> &lhs) const
	{ return lhs.first == rhs.first && lhs.second == rhs.second; }

	bool operator()(const std::pair<const T1, const T2> &rhs, const std::pair<      T1, const T2> &lhs) const
	{ return lhs.first == rhs.first && lhs.second == rhs.second; }
};

and then call
assert(std::equal(m.begin(), m.end(), std::begin(expected_m), std::end(expected_m, pair_eq<int, long>{})));

I'm not 100% sure that this is a win, but it might be.

40 ↗(On Diff #189182)

Alternately, you could define a couple of typedefs:

using P = std::pair<int, long>;
using PC = std::pair<const int, long>;
45 ↗(On Diff #189182)

This should be const, too. (I know that you don't ever change this, but ...)

77 ↗(On Diff #189182)

A comment here "braces instead of parens" would help a lot.

91 ↗(On Diff #189182)

typedef using P = std::pair<int, long>; would make this clearer.
Along with std::multimap m{ P{1,1L}, P{2,2L}, P{1,1L}, P{INT_MAX,1L}, P{3,1L} };

111 ↗(On Diff #189182)

Why is this not P expected_m[] = ...?

Quuxplusone marked 5 inline comments as done.May 3 2019, 1:08 PM

I'm irked by the typedef typename __identity<_Allocator>::type allocator_type; in the definition of map/multimap. What problem is that solving?

Unfortunately, if you don't place a "deduction firewall" between allocator_type and _Allocator, then the deduction guides implicitly generated from the unconstrained constructors of map/multimap that take an allocator_type parameter will happily match and deduce e.g. _Allocator=std::less<int>, which then blows up with a hard error trying to instantiate allocator_traits<std::less<int>>. We need to place that firewall in order to nerf the implicitly generated deduction guides, so that our explicit deduction guides can take priority.

Easy experiment: remove the firewall and compile the new test files. If I'm not mistaken, you'll see horrible error messages.

test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp
40 ↗(On Diff #189182)

This sounds good.
Yes, I believe I needed to use exactly value_type so that the equals would work.
Will change to use those two typedefs and const PC expected_m[] = ....

91 ↗(On Diff #189182)

Hmm. I seem to recall that I specifically didn't want to nail down what kind of pair was being CTAD'ed — the idea was to keep this specific code (a CTAD multimap of pair{x,y}s) working even if the CTAD guides on either multimap or pair are changed in the future. Other tests would handle "a CTAD multimap of pair<A,B>(x,y)s" and "a CTAD multimap of {x,y}s."
Except that I don't see those tests here! So I guess using the concrete type pair<A,B> (or just P) would be okay.

I am unsure whether multimap{ pair{a,b}, pair{c,d} } can ever produce a different type from multimap{ pair<A,B>{a,b}, pair<A,B>{c,d} }. I am pretty sure that those can produce a different type from multimap{ {a,b}, {c,d} }.

111 ↗(On Diff #189182)

Will change to const PC expected_m[] = ....
(I think originally I introduced typedef P only for use in allocator<P>, because those lines were getting too long. So it wasn't used consistently everywhere — just in the allocator types.)

Quuxplusone marked 8 inline comments as done.May 3 2019, 2:09 PM
Quuxplusone added inline comments.
test/std/containers/associative/multimap/multimap.cons/deduct.fail.cpp
60 ↗(On Diff #189182)

The reason it's commented out is that the error message that's actually printed is a hard error from inside include/map and I don't know how to write an expected-error line for that. Is that possible? Here's the error as printed:

File $ROOT/llvm/projects/libcxx/include/map Line 1671: static_assert failed due to requirement 'is_same<std::__1::pair<int, long>, std::__1::pair<const int, long> >::value' "Allocator::value_type must be same type as value_type"
test/std/containers/associative/multimap/multimap.cons/deduct.pass.cpp
91 ↗(On Diff #189182)

I found the "CTAD multimap of {x,y}s" in deduct.fail.cpp. :)

Review comments on the unit tests.
Also, it looks like my initial upload didn't actually include the LWG3025 fix? The fix involves the remove_const that's now in most of the deduction guides (and a new test file to test the change).

Quuxplusone marked an inline comment as done.May 4 2019, 9:03 AM
Quuxplusone added inline comments.
test/std/containers/associative/multimap/multimap.cons/deduct_const.pass.cpp
123 ↗(On Diff #198084)

BTW, if you told me to remove these last two tests (which test std::multimap<const int&, long>), I would do so.
I don't know whether libc++ is supporting reference types here by unhappy accident (i.e. you should just add static_assert(is_object_v<_Key> && is_object_v<_Tp>) and be done with it), or by happy accident (i.e. you would be scared to add that static_assert at this point but I should remove these two tests anyway), or on purpose (i.e. I should keep these two tests).

Note that std::map cannot support a reference-typed _Key because then try_emplace would give multiple declaration errors: const _Key& and _Key&& would be the same type.

ldionne added inline comments.May 14 2019, 1:58 PM
include/map
1474 ↗(On Diff #189182)

Those requirements are for container adapters -- do we have similar requirements for map and set?

Quuxplusone marked an inline comment as done.May 14 2019, 2:13 PM
Quuxplusone added inline comments.
include/map
1474 ↗(On Diff #189182)

Oops, you're absolutely right. Yes we do; the requirements for map and set are in
http://eel.is/c++draft/associative.reqmts#15 (which is what I should have said above instead of http://eel.is/c++draft/container.adaptors.general#4).

This looks good to me, with a few nits.

include/map
2132 ↗(On Diff #198084)

You're very consistent here with qualifying remove_const, and nothing else. Why?

test/std/containers/associative/map/map.cons/deduct.fail.cpp
62 ↗(On Diff #198084)

Why is this test commented out?

test/std/containers/associative/map/map.cons/deduct.pass.cpp
87 ↗(On Diff #198084)

This works? I would think that it should not. We rebind the allocator internally into something else, but we should probably reject this. [But not in this patch]

test/std/containers/associative/multimap/multimap.cons/deduct.fail.cpp
60 ↗(On Diff #189182)

See test/std/algorithms/alg.modifying.operations/alg.random.sample/sample.fail.cpp for an example.
Basically, you would write:

// expected-error-re@ map:* {{static_assert failed{{( due to requirement '.*')?}} "Allocator::value_type must be same type as value_type"}}
mclow.lists added inline comments.May 28 2019, 10:04 AM
test/std/containers/associative/multimap/multimap.cons/deduct_const.pass.cpp
123 ↗(On Diff #198084)

I'll look into this.

ldionne accepted this revision.May 28 2019, 10:18 AM

I remember looking at this and I was fine with it. LGTM if @mclow.lists is fine with it.

This revision is now accepted and ready to land.May 28 2019, 10:18 AM
Quuxplusone marked 8 inline comments as done.May 29 2019, 9:04 AM
Quuxplusone added inline comments.
include/map
2132 ↗(On Diff #198084)

No reason. Removed.

test/std/containers/associative/map/map.cons/deduct.pass.cpp
87 ↗(On Diff #198084)

This is me getting a jump start on P1518 Stop overconstraining allocators in container deduction guides.

Since

std::map<int, long> m(source, std::allocator<int>());

works (without CTAD), Mike Spertus (as of February) and I believe that

std::map m(source, std::allocator<int>());

should work with CTAD as well.

Quuxplusone marked an inline comment as done.

Addressed the latest review comments.

Almost there - and I'm on the hook for comments on the reference stuff.

test/std/containers/associative/map/map.cons/deduct.pass.cpp
87 ↗(On Diff #198084)

I don't believe that either should work.

std::vector<long, std::allocator<int>> m;
doesn't work, nor does:

long l[] = {1L };
std::vector v(std::begin(l), std::end(l), std::allocator<int>());

The fact that it works today for map and set is due to insufficient checking in libc++

mclow.lists added inline comments.May 29 2019, 11:03 AM
test/std/containers/associative/multimap/multimap.cons/deduct_const.pass.cpp
123 ↗(On Diff #198084)

I would say drop these two tests. We don't have any other map tests that use reference keys.

Quuxplusone marked 3 inline comments as done.May 29 2019, 12:09 PM
Quuxplusone added inline comments.
test/std/containers/associative/map/map.cons/deduct.pass.cpp
87 ↗(On Diff #198084)

std::vector<long, std::allocator<int>> m; is not expected to work, because it avoids CTAD and explicitly instantiates vector with bad template parameters.

std::vector v(std::begin(l), std::end(l), std::allocator<int>()) is not expected to work either (although there's a slightly stronger case for allowing it to work), because the value type of the iterator is different from the value type of the-allocator-which-is-deduced-by-CTAD. (Since the allocator is deduced, there's arguably a case for CTAD to trust the allocator's value_type and ignore the irrelevant value type of the iterator. That is, arguably, CTAD could do the same thing that std::vector<int, std::allocator<int>> v(std::begin(l), std::end(l), std::allocator<int>()) does.)

But in std::vector w(source, std::allocator<int>()), CTAD knows we're using the allocator-aware copy constructor of vector. That constructor deduces the allocator type from the first parameter — the vector it's making a copy of — not from the second parameter. The only requirement is that the passed-in allocator argument should be implicitly convertible to the deduced allocator type. Which in this case, it is.

I'm willing to #if 0 out this test for now, but I am also willing to keep debating it until you see the P1518 light. ;)

test/std/containers/associative/multimap/multimap.cons/deduct_const.pass.cpp
123 ↗(On Diff #198084)

Will do.

Quuxplusone marked an inline comment as done.

Address review comments. (Remove the two tests involving a multimap-of-reference-type.)

mclow.lists added inline comments.May 30 2019, 7:01 AM
test/std/containers/associative/map/map.cons/deduct.pass.cpp
87 ↗(On Diff #198084)

I think we're discussing different things here.

I'm talking about the general container requirements, the very first line in Table 62, which says:

Mandates: allocator_­type::value_­type is the same as X::value_­type.

As far as I can tell, P1518 doesn't change that at all.

Quuxplusone marked 4 inline comments as done.May 30 2019, 5:44 PM
Quuxplusone added inline comments.
test/std/containers/associative/map/map.cons/deduct.pass.cpp
87 ↗(On Diff #198084)

I think you think we're discussing different things, but we're not. ;)
Here's the test in question:

std::map<int, long> source;
std::map m(source, std::allocator<int>());
ASSERT_SAME_TYPE(decltype(m), decltype(source));

I claim (equivalently, P1518 claims) that the variable definition on line 2 creates a variable m of type std::map<int, long>. This is "obvious" because it is calling the allocator-aware constructor map(const map&, allocator). We're using CTAD here, but we could just as well put the deduced template arguments back in place:

std::map<int, long> m(source, std::allocator<int>());

This is fine. The second constructor argument, the one that provides a "value" for the new map's allocator, is implicitly converted from std::allocator<int> to std::map<int, long>::allocator_type.

You might say "Shouldn't the second parameter's type be forced to exactly match std::map<int, long>::allocator_type?" but no, that's not how it works without CTAD, so it's not how it should work with CTAD either. In particular, we would like the following to work:

std::pmr::map<int, long> source;
std::map m(source, std::pmr::new_delete_resource());
ASSERT_SAME_TYPE(decltype(m), decltype(source));

    // C++2a only: requires CTAD to see through typedefs
std::pmr::map m2(source, std::pmr::new_delete_resource());
ASSERT_SAME_TYPE(decltype(m2), decltype(source));

That can only work (AFAIK) if you don't allow CTAD to "get confused" by the actual argument type of that second argument. All we require is that the actual argument should be something convertible to allocator_type (which would be the requirement in the absence of CTAD).

mclow.lists added inline comments.Jun 6 2019, 6:37 AM
test/std/containers/associative/map/map.cons/deduct.pass.cpp
87 ↗(On Diff #198084)

I'm willing to #if 0 out this test for now, but I am also willing to keep debating it until you see the P1518 light. ;)

I think that we should remove this test, commit the rest of this patch, and then continue this debate if/when P1518 lands. Tests that are commented out are always a question for the reader: "Why is this test commented out?"

Use the original decltype(source)::allocator_type instead of std::allocator<int> in the allocator-aware-copy-constructor test. So we don't insist on P1518R0 support (yet).

Quuxplusone marked 3 inline comments as done.Jun 6 2019, 8:25 AM

@mclow.lists: I think everything's resolved and this is ready for you (or someone; not me) to land. Once it's landed, I assume the next step will be to resume review on D58582 (set) and/or D58590 (unordered_map).

test/std/containers/associative/map/map.cons/deduct.pass.cpp
87 ↗(On Diff #198084)

Okay. Not removed, but modified to use the exact allocator_type, which we both agree should work regardless.

mclow.lists closed this revision.Jun 10 2019, 2:25 PM

Committed as revision 362986

mgorny added a subscriber: mgorny.Jun 17 2019, 9:29 AM

Marshall, std/containers/associative/map/map.cons/deduct_const.pass.cpp test seems to be reliably failing from commit one on both Gentoo Linux and NetBSD. Could you please look at the classical example of totally cryptic C++ error? ;-)

http://lab.llvm.org:8011/builders/netbsd-amd64/builds/20/steps/run%20unit%20tests/logs/FAIL%3A%20libc%2B%2B%3A%3Adeduct_const.pass.cpp

Quuxplusone updated this revision to Diff 205408.EditedJun 18 2019, 11:56 AM
Quuxplusone marked an inline comment as done.
  • Add an __identity<T>::type "firewall" on the comparator type as well as on the allocator type. (This fixes the Gentoo/NetBSD test failure. Essentially, my patch had been accidentally relying on a clang bug which caused the implicit deduction guides to be totally ignored in this case. When the clang bug got fixed, my patch broke. Adding the "firewall" fixes my patch AFAICT.)
  • Use enable_if_t and remove_const_t instead of the longer C++11-friendly names. I assume that since the deduction guides are compiled only in C++17 library mode, they are allowed to rely on C++14-and-later library features. However, I can put it back the way it was if someone disagrees with my assumption.
Quuxplusone reopened this revision.Jun 18 2019, 11:56 AM
This revision is now accepted and ready to land.Jun 18 2019, 11:56 AM
ldionne accepted this revision.Jun 18 2019, 12:02 PM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptJun 20 2019, 12:29 PM