Nested template argument deduction for class templates not working

Asked 15/2, 2017 at 8:33 Answered 15/2, 2017 at 12:44

Solved c++templates c++17 class-template template-argument-deduction

In this Q&A I wrote a little wrapper class that provides reverse iterator access to a range, relying on the c++1z language feature template argument deduction for class templates (p0091r3, p0512r0)

#include <iostream>
#include <iterator>
#include <vector>

template<class Rng>
class Reverse
{
    Rng const& rng;    
public:    
    Reverse(Rng const& r) noexcept
    : 
        rng(r)
    {}

    auto begin() const noexcept { using std::end; return std::make_reverse_iterator(end(rng)); }
    auto end()   const noexcept { using std::begin; return std::make_reverse_iterator(begin(rng)); }
};

int main()
{
    std::vector<int> my_stack;
    my_stack.push_back(1);
    my_stack.push_back(2);
    my_stack.puhs_back(3);

    // prints 3,2,1
    for (auto const& elem : Reverse(my_stack)) {
        std::cout << elem << ',';    
    }
}

However, doing a nested application of Reverse does not yield the original iteration order

// still prints 3,2,1 instead of 1,2,3
for (auto const& elem : Reverse(Reverse(my_stack))) {
    std::cout << elem << ',';    
}

Live Example (same output for g++ 7.0 SVN and clang 5.0 SVN)

The culprit seems to be the template argument deduction for class templates because the usual wrapper function does allow for correct nesting

template<class Rng>
auto MakeReverse(Rng const& rng) { return Reverse<Rng>(rng); }

// prints 1,2,3
for (auto const& elem : MakeReverse(MakeReverse(my_stack))) {
    std::cout << elem << ',';    
}

Live Example (same output for g++ and clang)

Question: is nested template argument deduction for class templates supposed to work only "one level" deep, or is this a bug in the current implementations of both g++ and clang?

Vincennes answered 15/2, 2017 at 8:33 Comment(15)

Neither. Your code contains UB because of dangling reference. – Bulldoze 15/2, 2017 at 8:45

@Bulldoze I don't think so, my_stack is a named variable, and the reference is stored inside the Reverse object, so what is dangling here? – Vincennes 15/2, 2017 at 8:47

But Reverse(my_stack) is not a named varible, and you store a reference to it inside Reverse(Reverse(my_stack)). – Bulldoze 15/2, 2017 at 8:49

Maybe you can fix it by adding a move constructor that copies begin() and end() from the range. – Elvia 15/2, 2017 at 8:55

I think this is similar to std::tuple t(std::tuple(1)); -- should t be tuple<tuple<int>> or a copy of tuple<int>(1) ? (I think the latter) – Musquash 15/2, 2017 at 9:4

How does it even compile without specifying the template arguments in the contructor – like you did in the function? If I use Reverse<Reverse<std::vector<int>>>(Reverse<std::vector<int>>(my_stack)) instead, I get a runtime error; probably bescause of dangling reference. – Reade 15/2, 2017 at 9:9

@Reade this is a c++1z feature, works also e.g. for std::pair so that you don't have to use the make_pair function helper – Vincennes 15/2, 2017 at 9:11

@Vincennes thanks, didn't noticed the tag and haven't used the new standard yet. – Reade 15/2, 2017 at 9:14

@Bulldoze but I store it inside the class using const& so that should bind the temporary, right? – Vincennes 15/2, 2017 at 9:14

@Vincennes it doesn't bind directly to that reference, so it's UB in the second snippet, and probably ok in the first, where move construction is used, but overall it's not the cause of the behavior – Musquash 15/2, 2017 at 9:19

@PiotrSkotnicki simply storing the rng member by value doesn't fix this – Vincennes 15/2, 2017 at 9:26

The contructor of the outer Reverse is a copy constructor and therefore uses the same template argument. – Reade 15/2, 2017 at 9:26

@Vincennes yes, as I said, UB is not the root cause of the behavior you spot, the thing is that Reverse(Reverse(my_stack)) or even Reverse(Reverse(Reverse(Reverse(my_stack)))) is still a copy of a single Reverse(my_stack) – Musquash 15/2, 2017 at 9:27

@Vincennes yes, as I checked, std::tuple t(std::tuple(1)); yields std::tuple<int>, not std::tuple<std::tuple<int>>, which I think is correct behavior, but I have no reference to prove this – Musquash 15/2, 2017 at 9:34

@PiotrSkotnicki OK, that makes sense, but it's still surprising. I guess range wrappers still need helper functions – Vincennes 15/2, 2017 at 9:35

Piotr's answer correctly explains what is happening - the move constructor is a better match than your constructor template.

But (h/t T.C. as usual) there's a better fix than just writing a factory anyway: you can add an explicit deduction guide to handle the wrapping:

template <class R>
Reverse(Reverse<R> ) -> Reverse<Reverse<R>>;

The point of this is to override the copy deduction candidate, thanks to the newly added preference in [over.match.best] for this:

Given these definitions, a viable function F1 is defined to be a better function than another viable function F2 if [...] F1 is generated from a deduction-guide (13.3.1.8) and F2 is not.

Hence, we'd have four generated functions, borrowing again from Piotr's naming:

template <typename Rng>
Reverse<Rng> foo(const Rng& r);             // #1

template <typename Rng>
Reverse<Rng> foo(const Reverse<Rng>& r);    // #2

template <typename Rng>
Reverse<Rng> foo(Reverse<Rng>&& r);         // #3

template <typename Rng>
Reverse<Reverse<Rng>> foo(Reverse<Rng> r);  // #4 - same-ish as #2/3, but deduction guide

Before, #3 was preferred as being more specialized. Now, #4 is preferred as being a deduction guide. So, we can still write:

for (auto const& elem : Reverse(Reverse(my_stack))) {
    std::cout << elem << ',';    
}

and that works.

Disenthrone answered 15/2, 2017 at 12:44 Comment(7)

Under the current wording, you want R, not R const &, otherwise #3 wins because its ICS is better (binding rvalue ref to an rvalue). Clang seems to intentionally do this part differently. – Faxon 15/2, 2017 at 15:19

Would this force all copies to actually reverse the container again? – Monti 15/2, 2017 at 18:6

@DavidStone I don't understand the question. – Disenthrone 15/2, 2017 at 18:16

@Disenthrone thanks, nice to get a grip on these new deduction guides. I wonder though, if this is the new SFINAE where you really have to think very carefully about all the overloads in play and that you have to give a by-value constructor a deduction guide to get around rvalue matches. It would be much more intuitive (say what you mean principle) if one were able to give a const& deduction guide. – Vincennes 15/2, 2017 at 19:27

@Vincennes I am worried with the added complexity :-/ It's certainly nice for std::lock_guard, but... – Disenthrone 15/2, 2017 at 19:41

This no longer seems to work with clang 6 and above or any gcc :( minimal example – Ankylose 14/12, 2018 at 19:33

@Ankylose That's because it was always wrong!! OOPS. Now it's correct. The copy deduction candidate is more specialized than the guide I had before (and more specialized comes before deduction-guide in the list of precedence) – Disenthrone 14/12, 2018 at 20:58

This may be explained in [over.match.class.deduct]/p1:

A set of functions and function templates is formed comprising:

For each constructor of the class template designated by the template-name, a function template with the following properties:

The template parameters are the template parameters of the class template followed by the template parameters (including default template arguments) of the constructor, if any.

The types of the function parameters are those of the constructor.

The return type is the class template specialization designated by the template-name and template arguments corresponding to the template parameters obtained from the class template.

My understanding is that the compiler invents the following two functions (two - including a copy constructor that is implicitly generated for this class):

template <typename Rng>
Reverse<Rng> foo(const Rng& r);           // #1

template <typename Rng>
Reverse<Rng> foo(const Reverse<Rng>& r);  // #2

and then tries to select the best overload based on the call:

foo(Reverse<std::vector<int>>(my_stack));

which resolves to #2 because this one is more specialized. The conclusion is that:

Reverse(Reverse(my_stack))

involves a copy constructor to construct the outer Reverse instance.

Musquash answered 15/2, 2017 at 10:12 Comment(10)

I may be totally wrong, please correct me, I'm curious too. – Musquash 15/2, 2017 at 10:12

I think you're right, +1. Real question is - is this the intended behavior of the feature, or no? It's certainly surprising. – Disenthrone 15/2, 2017 at 12:48

Basically correct, except that it's the move constructor. @Disenthrone "surprising" how? – Faxon 15/2, 2017 at 13:46

@Faxon I can't really articulate it. It both makes sense that it's a move, and doesn't. And the fact that ultimately we have to write a factory anyway to do the right thing, when half the point of the proposal was obviating the need for factories, is unfortunate. – Disenthrone 15/2, 2017 at 13:54

@Disenthrone You have to choose one way or the other, and it seems to me that the current choice leads to fewer surprises than the alternative. Also, you don't need a factory; an explicit guide will do. – Faxon 15/2, 2017 at 13:59

@Faxon What would that explicit guide look like? – Disenthrone 15/2, 2017 at 14:2

@Disenthrone template<class R> Reverse(R) -> Reverse<R>; should do it. – Faxon 15/2, 2017 at 14:3

@Disenthrone ...so? The point is to get the tie broken the other way around. – Faxon 15/2, 2017 at 14:32

@Faxon Ah. I just tested the code in gcc and it did the same thing - they apparently don't implement that rule yet. Thanks. – Disenthrone 15/2, 2017 at 14:41

The "intended behavior" is mostly that optional<int> o(1); optional p(o); should not produce optional<optional<int>>. – Belk 18/9, 2017 at 6:56