Page MenuHomePhabricator

[libc++] Rewrite the tuple constructors to be strictly Standards conforming
ClosedPublic

Authored by ldionne on Feb 11 2021, 9:40 AM.

Details

Summary

This nasty patch rewrites the tuple constructors to match those defined
by the Standard. We were previously providing several extensions in those
constructors - those extensions are removed by this patch.

The issue with those extensions is that we've had numerous bugs filed
against us over the years for problems essentially caused by them. As a
result, people are unable to use tuple in ways that are blessed by the
Standard, all that for the perceived benefit of providing them extensions
that they never asked for.

Since this is an API break, I communicated it in the release notes.
I do not foresee major issues with this break because I don't think the
extensions are too widely relied upon, but we can ship it and see if we
get complaints before the next LLVM release - that will give us some
amount of information regarding how much use these extensions have.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
zoecarver added inline comments.Feb 11 2021, 10:19 PM
libcxx/include/tuple
590

This works for me:

template<class ...U>
    static const size_t u_types_constraints =
        sizeof...(U) == sizeof...(T) &&
        sizeof...(U) >= 1 &&
        !is_same<Tuple, U...>::value;

template<class ...U, class = _EnableIf<u_types_constraints<U...> > >
    Tuple(U&&...) { }

FWIW, I don't understand what the "extension" is here, nor what "mis-behaved user constructors" we're worried about. But I haven't cared enough to remove that line and re-run the unit tests to find out.

I also am curious about what this means. I thought it was just to ensure that we picked the right overload (so that this doesn't look like a move constructor when _Up = tuple).

803

Wait... why do we have _Dummy types here? Why can't this just be:

template <class U1, class U2>
static const size_t __enable_copy_from_pair = sizeof...(_Tp) == 2 && 
    is_constructible<_FirstType <_Tp...>, const U1&>::value &&
    is_constructible<_SecondType<_Tp...>, const U2&>::value;
zoecarver added inline comments.Feb 11 2021, 10:26 PM
libcxx/include/tuple
938

First, why do we need the void types? We've already checked that there are at least two elements, and this should be a short-circuiting operator.

Second, I think type alias types should be counted as dependent types as long as they're substituted with template type arguments. So, what Arthur proposed should work. But I can play around with this patch a bit more locally tomorrow and try to get it working.

zoecarver added inline comments.Feb 12 2021, 11:36 AM
libcxx/include/tuple
590

Follow up: I got this working here. I like this approach much better because we instantiate less than half the types, so it should be much better for compile time.

Side note: I spent way too long banging my head against the wall trying to figure out why we can only zip parameter packs in type aliases (and not static vars). It turns out there's an issue for this open: 1844. Basically, various compilers read "immediate context" differently, so sometimes we get a hard error and sometimes we get a substitution failure. Here's a Godbolt to demonstrate the problem.

Quuxplusone added inline comments.Feb 12 2021, 1:44 PM
libcxx/include/tuple
590

@zoecarver: Your Godbolt (https://godbolt.org/z/erqqGT ) makes perfect sense to me. Here's a "reduced" (but still icky) version: https://godbolt.org/z/x6c67o
If you have a type alias that says "Yy is the type you get by zipping these packs," and the packs can't be zipped, well, that's SFINAE-friendly. If you have a static constexpr bool whose initializer says "Xx is true if zipping these packs gives you foo, or false if zipping these packs gives you bar," and the packs can't be zipped, well, that's not SFINAE-friendly (not an "immediate context," if I've got my standardese right).

938

why do we need the void types?

Because when sizeof...(_Tp) == 1, then _SecondType<_Tp...> is ill-formed — which would make the entire type-expression

_EnableIf<
    _And<
        _Lazy<_EnableMoveFromPair, _Up1, _Up2>,
        _Not<_Lazy<_And, // explicit check
            is_convertible<_Up1, _FirstType<_Tp..., void> >,
            is_convertible<_Up2, _SecondType<_Tp..., void> >
        > >
    >::value
, int>

immediately ill-formed — which would make this constructor template drop out of overload resolution whenever sizeof...(_Tp) == 1. Hmm, I guess that's totally OK in this case!

The key thing to watch out for in all this metaprogramming ickiness is that regardless of short-circuiting evaluation of truth values, the compiler is still going to be instantiating the types that we name in the expression, such as _FirstType<_Tp..., void>. I guess that's exactly what _Lazy is for, though; and so if _SecondType<_Tp...> didn't suffice, the next thing we should try is not _SecondType<_Tp..., void> but rather _Lazy<_SecondType, _Tp...>.

ldionne updated this revision to Diff 323801.Feb 15 2021, 11:01 AM
ldionne marked 15 inline comments as done.

Address review comments, fix compilation on GCC and other minor simplifications to the SFINAE.

I addressed all comments with a direct suggestion. For other comments on using various patterns for doing SFINAE, I actually reworked everything to make GCC happy.

You'll notice that we now never call a metafunction with the incorrect number of arguments. GCC does not seem to handle SFINAE failures for mismatched parameter pack lengths correctly, so I had to use this approach.

I still need to investigate a test failure in C++11 and C++14 mode - the behavior after this patch matches the libstdc++ behavior, so I think the test was wrong, but I need to understand it better.

libcxx/include/tuple
481

Does Clang trunk provide explicit(bool) as an extension in C++ < 20 modes? If so, then I suggest we come back once we drop support for older Clangs and remove the duplication.

Otherwise, if Clang doesn't support explicit(bool) in pre-C++20 mode, we will never be able to remove this duplication because we still have to implement the explicit/implicit constructors for tuple pre-C++20 (it was applied as a LWG issue IIRC).

590

FWIW, I don't understand what the "extension" is here, nor what "mis-behaved user constructors" we're worried about.

It refers to the test in libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/PR23256_constrain_UTypes_ctor.pass.cpp. That test fails if you remove that line.

We're on the same page regarding the SFINAE behavior for variable templates vs template aliases, but I don't think it's relevant to the issue directly at hand.

The issue here is that we want the overload to be enabled when sizeof...(_Up) > 1. But when that's the case, is_same will cause a SFINAE error because we'll try to instantiate it with too many template arguments. Basically, in order to get rid of _IsThisTuple, we'd have to write something like this instead:

_And<_BoolConstant<sizeof...(_Up) == 1>, _Lazy<is_same, uncvref_t<_Up>..., tuple> >

I don't think that's better, but WDYT?

803

Because when sizeof...(_Tp) < 2, the "expression" _FirstType<_Tp...> is a hard error. That "expression" is "evaluated" when the tuple template is instantiated, not when we instantiate the template alias.

938

the next thing we should try is not _SecondType<_Tp..., void> but rather _Lazy<_SecondType, _Tp...>.

That doesn't work, because _SecondType is an alias that expands to the type itself. So _Lazy would end up inheriting from that type, which isn't what we want.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/UTypes.pass.cpp
40

Thanks, much better indeed!

Also, I just realized that we can use fold expressions here (on all supported compilers even in C++03 mode). I bet that would be faster/cleaner than instantiating all the _Ands.

libcxx/include/tuple
590

But when that's the case, is_same will cause a SFINAE error because we'll try to instantiate it with too many template arguments.

I think this is the point of confusion. This is also why we are able to use a static variable. Because tuple is not a parameter pack, so there are never too many template arguments.

However, in the diff I liked to, Arthur made a really good point, which is that using a static variable might not be faster here if we have to uncvref_t all of the Us.

So, I'm happy to ship this version. (Though, there is a small part of my brain saying, "I wonder if it would be faster to use a static variable and _IsThisTuple?")

758

I think there should be an (is_constructible_v<T, U&&> && ...) check.

zoecarver added inline comments.Feb 16 2021, 1:26 PM
libcxx/include/tuple
481

Yes. If there were a world where libc++ only supported Clang V10 and GCC V9, I think this could work really well.

Also, I just realized that we can use fold expressions here (on all supported compilers even in C++03 mode). I bet that would be faster/cleaner than instantiating all the _Ands.

So we can't actually use fold expressions because they don't short-circuit instantiations. A fold expression like trait<args>::value && ... gets expanded to trait<arg0>::value && trait<arg1>::value && trait<arg2>::value && <etc>. While the evaluation of the boolean is short-circuited, the instantiation of trait<argn>::value is not, which is what we're trying to do here. As a result, if for example trait<arg2>::value causes a hard error, it will be instantiated even if trait<arg0>::value instantiates fine and evaluates to false. Does that make sense?

Also, I just realized that we can use fold expressions here (on all supported compilers even in C++03 mode). I bet that would be faster/cleaner than instantiating all the _Ands.

So we can't actually use fold expressions because they don't short-circuit instantiations. A fold expression like trait<args>::value && ... gets expanded to trait<arg0>::value && trait<arg1>::value && trait<arg2>::value && <etc>. While the evaluation of the boolean is short-circuited, the instantiation of trait<argn>::value is not, which is what we're trying to do here. As a result, if for example trait<arg2>::value causes a hard error, it will be instantiated even if trait<arg0>::value instantiates fine and evaluates to false. Does that make sense?

Hmm. I understand what you're saying, but I think that's only the case if it's a static var. If it's actually part of the type (i.e., it's used to specialize a _BoolConstant), I think it works the same way. Here's an example.

[...]

Hmm. I understand what you're saying, but I think that's only the case if it's a static var. If it's actually part of the type (i.e., it's used to specialize a _BoolConstant), I think it works the same way. Here's an example.

Your example is broken - it SFINAEs out because you're zipping parameter packs of different lengths. See https://godbolt.org/z/qna759.

Nope, but that's fixed by the parent patch https://reviews.llvm.org/D50106.

Quuxplusone added inline comments.Feb 17 2021, 3:18 PM
libcxx/include/tuple
590

I would like to continue down this rabbit-hole, but I think we're all talking past each other at this point.

  • There's the question of pack expansions, like where it's legit to put is_same<tuple, Up...> and where not.
  • There's the question of eager vs lazy instantiation, like where it's legit to put (is_convertible<Tp, Up>::value && ...) and where _And<is_convertible<Tp, Up>...> (this is https://bugs.llvm.org/show_bug.cgi?id=23256 as I understand it).
  • There's some desire to minimize instantiations, for speed. But there's also an explicit goal to avoid certain completions of is_convertible<T,U> because PR23256.
  • There's maybe other questions.

(Perhaps _And<_Not<x>...> could be replaced by _NoneOf<x...>, if our toolbox were expanded to include an implementation of _NoneOf.)

I'd like to see either of these next steps:

  • @ldionne to just land this thing already, or
  • @ldionne to identify a single measurable goal, e.g. "let's figure out how to remove the identifier _IsThisTuple while still passing the tests in this patch," which we can then resume rabbit-holing on (but via suggesting actual patches that pass all the tests locally, not just brainstorming untested ideas).
libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/deduct.pass.cpp
16

What about gcc-8?
And does this patch change something that breaks gcc-9 and gcc-10, or is it more like "we never tested it and I just now noticed that it's broken"? Maybe this belongs in a severable commit.

Your example is broken - it SFINAEs out because you're zipping parameter packs of different lengths. See https://godbolt.org/z/qna759.

Oh, I thought you were saying that it wouldn't work because zipping parameter packs of different sizes would be a hard error. Anyway, I think I see what you're saying now. Thanks for the Godbolt link.


I think @Quuxplusone makes a good point. And for what it's worth, I'd be fine with this patch landing in its current state. I think we should attempt to remove extra template instantiations, but this can also be done after the fact and AFAICT this is already better than main (or at least easier to grok).

I think I'd land this patch as-is and then try to identify some instantiations we want to remove and do that. Arthur, thanks for taking us back on track :-).

I'll need to figure out what the issue is with the remaining tests that fail in C++11 and C++14. Then I'll land this patch internally at Apple in a test build and see if there's any breakage. If that all works, I'll land this here.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/deduct.pass.cpp
16

I forgot to add gcc-8, I'll do that.

This patch causes GCC 10 to segfault when CTAD is used.

ldionne updated this revision to Diff 333379.Mar 25 2021, 11:46 AM

Rebase onto main

I was trying to close the loop on this and got down to the following behaving differently in C++11/14 and C++17/20: https://godbolt.org/z/6x75njn7v

#include <cstdio>

template <class ...T>
struct tuple {
  tuple() { }
  template <class ...U>
  tuple(tuple<U...>&&) { std::printf("construction\n"); }
};

struct Foo { };

struct Derived : tuple<int> {
  template<class U>
  operator tuple<U>() && { std::printf("conversion\n"); return {}; }
};

int main(int, char**) {
  tuple<Foo> bar(Derived{});
}

It looks like in C++11 and 14, we prefer the constructor, whereas in C++17 and above, we prefer the conversion. Both GCC and Clang have the same behavior. So I'm going to tweak the tests accordingly.

ldionne updated this revision to Diff 334794.Apr 1 2021, 12:26 PM

Fix tests in C++11 and C++14

ldionne accepted this revision as: Restricted Project.Apr 1 2021, 12:31 PM

I will ship this if CI passes, as discussed with the reviewers.

zoecarver accepted this revision.Apr 1 2021, 12:33 PM

⛵️it!

This revision is now accepted and ready to land.Apr 1 2021, 12:33 PM
EricWF added a comment.Apr 1 2021, 1:08 PM

I'm a bit worried about some of the tests that were deleted. Not the ones for extensions, but some of the ones added to prevent regressions with SFINAE.

I would like to look into why they now fail.

EricWF requested changes to this revision.Apr 1 2021, 1:08 PM
This revision now requires changes to proceed.Apr 1 2021, 1:08 PM

Here is one regression I've found so far:

https://godbolt.org/z/sahqsqarb

ldionne updated this revision to Diff 335636.Apr 6 2021, 12:53 PM

Fix bug with eager default constructor

Here is one regression I've found so far:

https://godbolt.org/z/sahqsqarb

Thanks for the find. Did you find anything else?

I'm a bit worried about some of the tests that were deleted. Not the ones for extensions, but some of the ones added to prevent regressions with SFINAE.

Which specific tests are you worried about? I looked and I think the only ones I removed were related to libc++ extensions which do not exist after this patch.

There's another bug with SFINAE depth increases that's blowing up at Google.
I suspect we can get that back.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/test_lazy_sfinae.pass.cpp
22

Why were these tests deleted?

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/tuple_array_template_depth.pass.cpp
1

Why was this file deleted?

ldionne marked 2 inline comments as done.Apr 7 2021, 10:23 AM

There's another bug with SFINAE depth increases that's blowing up at Google.
I suspect we can get that back.

Can you post a reproducer? I'll be happy to fix it.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/test_lazy_sfinae.pass.cpp
39

That class was never used AFAICT.

57–66

This test requires libc++'s reduced arity initialization, as the comment says. That extension was removed.

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/tuple_array_template_depth.pass.cpp
1

Because the extension that allows constructing a tuple from an array was removed (as noted in the release notes).

ldionne marked an inline comment as done.Apr 12 2021, 2:49 PM

There's another bug with SFINAE depth increases that's blowing up at Google.
I suspect we can get that back.

Can you post a reproducer? I'll be happy to fix it.

I'll commit this on Wednesday unless I have more information. I don't want to break your internal users, but I'd like to get moving with this patch since it has good chances of being difficult to rebase, so keeping it around for a while is quite risky.

ldionne accepted this revision as: Restricted Project.Fri, Apr 23, 9:45 AM
This revision was not accepted when it landed; it landed in state Needs Review.Fri, Apr 23, 9:46 AM
This revision was automatically updated to reflect the committed changes.
miyuki added a subscriber: miyuki.Wed, Apr 28, 6:36 AM

Hi. It looks like this change broke the following code:

#include <tuple>

void test() {
    using pair_t = std::pair<int, char>;
    constexpr std::tuple<long, long> t(pair_t(0, 'a'));
}
<source>:5:38: error: constexpr variable 't' must be initialized by a constant expression
    constexpr std::tuple<long, long> t(pair_t(0, 'a'));
                                     ^~~~~~~~~~~~~~~~~
<source>:5:38: note: non-constexpr constructor 'tuple<int, char, _And, 0>' cannot be used in a constant expression
/opt/compiler-explorer/clang-trunk-20210428/bin/../include/c++/v1/tuple:900:5: note: declared here
    tuple(pair<_Up1, _Up2>&& __p)
    ^
1 error generated.
Compiler returned: 1

https://godbolt.org/z/6sd9TTMrq

Could you please have a look into it?

jgorbe added a subscriber: jgorbe.Thu, Apr 29, 11:09 AM

We're seeing some issues with this patch manifested as complicated tuple expressions that hit compiler limits with template depth. A bit of a synthetic example, but here it is: https://godbolt.org/z/TzvzWhYYs

template <size_t... I>
void MakeFoo(std::index_sequence<I...>) {
  auto tup = std::make_tuple(I...);
  (void)tup;
}

void Broken() {
  // At trunk, when this is >= 508, we see:
  // fatal error: recursive template instantiation exceeded maximum depth of
  // 1024

  auto seq = std::make_index_sequence<508>{};
  MakeFoo(seq);
}

Prior to this patch, the breaking point is at 1021. Interestingly though, this didn't reproduce in the latest clang/llvm 12 release on godbolt. I did a second bisection to D50106 as the point where std::make_index_sequence<1021>{} newly fails.

In general this removes a bunch of carefully constructed SFINAE meant to improve compile times.
I'll look into getting that back.

libcxx/include/tuple
878

Why can't we use alias templates rather than instantiating a big type here?

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/PR31384.pass.cpp
52

What's going on here? Why are there different answers depending on the dialect?

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/tuple_array_template_depth.pass.cpp
1

This tested template depth. And this patch broke large tuples. It should have been rewritten in some other form.

We need to reallow big tuples and add another test.

1

It's worth noting that this was a conforming extension. Because array supports the tuple-like protocol. I'm disappointed this was removed.

I'm working to see if I can fix forward the template depth and constexpr
issues, but I would appreciate some help from @ldionne as the original
author.

I'm working to see if I can fix forward the template depth and constexpr
issues, but I would appreciate some help from @ldionne as the original
author.

I'm working on the constexpr issue right now. I only just saw this.

In general this removes a bunch of carefully constructed SFINAE meant to improve compile times.

The SFINAE in this patch is also meant to instantiate as few templates as possible when it can. After looking into it, I think the problem is that our implementation of _And is a bit naive, it shouldn't recurse as much. I'm pretty sure that'll solve the problem.

libcxx/include/tuple
878

Cause we're hiding the instantiation of the _And behind the struct instantiation, such that when e.g. _BoolConstant<sizeof...(_Tp) == 2> is false below, we don't instantiate anything. Mentioning a template specialization is cheap when you don't actually instantiate it.

This is the fix for the constexpr issue:

commit 3b8ab30ed526b15c3f82c61bb9476606db6f1630
Author: Louis Dionne <ldionne.2@gmail.com>
Date:   Fri Apr 30 15:52:26 2021 -0400

    [libc++] Fix constexpr-ness of std::tuple's constructor

    Mentioned in https://reviews.llvm.org/D96523.

I'm also going to overhaul all the tests as a follow-up, but I wanted to get the fix out the door ASAP.

Now I'll look into the recursion depth issue.

Another issue we're seeing is interactions between std::any and gmock -- I'll see if I can reduce it to something w/o the gmock dependency.

class X {
  // D96523 fixes this:
  // MOCK_METHOD(void, Func1, (const std::any&));
  // D96523 breaks this:
  MOCK_METHOD(void, Func2, (const std::any&, int));
};

(or: https://www.godbolt.org/z/454e8Mznx)

I don't know yet if this is an issue with libc++ or a misuse of libc++ by gtest.

ldionne added a comment.EditedFri, Apr 30, 1:30 PM

This should fix the instantiation depth issue: https://reviews.llvm.org/D101661

@rupprecht Please ping me once you've reduced to something that doesn't involve Gmock and I'll look into it.

This should fix the instantiation depth issue: https://reviews.llvm.org/D101661

@rupprecht Please ping me once you've reduced to something that doesn't involve Gmock and I'll look into it.

#include <any>
#include <tuple>

template <typename a>
class b {
  b(a);
};

template <typename>
struct c;
template <typename m, typename... d>
struct c<m(d...)> {
  using e = std::tuple<b<d>...>;
};

template <typename>
class f;

template <typename g>
class h {
  typename c<g>::e i;
};

template <typename m, typename... d>
struct f<m(d...)> {
  h<m(d...)> n();
};

class j {
  void k() { l.n(); }
  // Note: D96523 breaks this:
  f<void(std::any, int)> l;
  // Note: D96523 fixes this:
  // f<void(std::any)> l;
};

https://www.godbolt.org/z/4W8b1G7Yd

Thanks a lot for the reduction. Here it is further reduced without libc++'s std::tuple or std::any: https://www.godbolt.org/z/5r7schPMK

If you add the static_assert, the error goes away. That is very suspicious to me. I know how to "fix" it from the standard library side, but it seems like we should take that to Clang folks too. WDYT?

The bug with std::any should be addressed by https://reviews.llvm.org/D101770. As I said, I think it's a compiler bug, but https://reviews.llvm.org/D101770 should work around it.

I think we're all good now. The template depth fix in 84f0bb619507caf7c4809400138dae1da578282a actually exposed a long standing clang bug which needed another fix in 6bbfa0fd408e81055c360c2e059554dd76fd7f09. Thanks for the quick followups!