<xtree>: _Tree move constructor incorrectly swaps

[AlexGuteniev]

Describe the bug
The move constructor for a std::set with a lambda comparator type fails to compile when it attempts to swap the non-move-assignable comparator.

Command-line test case

d:\Temp2>type repro.cpp
#include <set>
#include <type_traits>

static const auto cmp = [](auto const& a, auto const& b) { return a < b; };

auto f()
{
    std::set<int, std::remove_const_t<decltype(cmp)>> container{cmp};
    return container; // dead at this return.
}

int main()
{
}

d:\Temp2>cl /EHsc repro.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.27.29009.1 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

repro.cpp
c:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\utility(107): error C2280: '<lambda_076e960ca186bb46139689bab3007458> &<lambda_076e960ca186bb46139689bab3007458>::operator =(const <lambda_076e960ca186bb46139689bab3007458> &)': attempting to reference a deleted function
repro.cpp(4): note: see declaration of '<lambda_076e960ca186bb46139689bab3007458>::operator ='
repro.cpp(4): note: '<lambda_076e960ca186bb46139689bab3007458> &<lambda_076e960ca186bb46139689bab3007458>::operator =(const <lambda_076e960ca186bb46139689bab3007458> &)': function was explicitly deleted
c:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\utility(114): note: see reference to function template instantiation 'void std::swap<_Ty,0>(_Ty &,_Ty &) noexcept(false)' being compiled
        with
        [
            _Ty=<lambda_076e960ca186bb46139689bab3007458>
        ]
c:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\xtree(994): note: see reference to function template instantiation 'void std::_Swap_adl<<lambda_076e960ca186bb46139689bab3007458>>(_Ty &,_Ty &) noexcept(false)' being compiled
        with
        [
            _Ty=<lambda_076e960ca186bb46139689bab3007458>
        ]
c:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\xtree(990): note: while compiling class template member function 'void std::_Tree<std::_Tset_traits<_Kty,_Pr,_Alloc,false>>::_Swap_val(std::_Tree<std::_Tset_traits<_Kty,_Pr,_Alloc,false>> &)'
        with
        [
            _Kty=int,
            _Pr=<lambda_076e960ca186bb46139689bab3007458>,
            _Alloc=std::allocator<int>
        ]
c:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\xtree(911): note: see reference to function template instantiation 'void std::_Tree<std::_Tset_traits<_Kty,_Pr,_Alloc,false>>::_Swap_val(std::_Tree<std::_Tset_traits<_Kty,_Pr,_Alloc,false>> &)' being compiled
        with
        [
            _Kty=int,
            _Pr=<lambda_076e960ca186bb46139689bab3007458>,
            _Alloc=std::allocator<int>
        ]
c:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\set(54): note: see reference to class template instantiation 'std::_Tree<std::_Tset_traits<_Kty,_Pr,_Alloc,false>>' being compiled
        with
        [
            _Kty=int,
            _Pr=<lambda_076e960ca186bb46139689bab3007458>,
            _Alloc=std::allocator<int>
        ]
repro.cpp(8): note: see reference to class template instantiation 'std::set<int,<lambda_076e960ca186bb46139689bab3007458>,std::allocator<int>>' being compiled
c:\Program Files (x86)\Microsoft Visual Studio\2019\Preview\VC\Tools\MSVC\14.27.29009\include\utility(108): error C2280: '<lambda_076e960ca186bb46139689bab3007458> &<lambda_076e960ca186bb46139689bab3007458>::operator =(const <lambda_076e960ca186bb46139689bab3007458> &)': attempting to reference a deleted function
repro.cpp(4): note: see declaration of '<lambda_076e960ca186bb46139689bab3007458>::operator ='
repro.cpp(4): note: '<lambda_076e960ca186bb46139689bab3007458> &<lambda_076e960ca186bb46139689bab3007458>::operator =(const <lambda_076e960ca186bb46139689bab3007458> &)': function was explicitly deleted

Expected behavior
Should compile

STL version

Microsoft Visual Studio Professional 2019 Preview
Version 16.7.0 Preview 3.1

Additional context
Also tracked by DevCom-657074 and VSO-951679 / AB#951679

[StephanTLavavej]

My analysis from the MS-internal bug:

The issue appears to be that _Tree's move constructor is calling _Swap_val, which calls _Swap_adl on the comparators, but std::swap SFINAEs away because lambdas aren't move assignable.

I think this is a problem in _Tree's move constructor, which shouldn't be swapping comparators. Instead we should be copying, like _Hash does.

On second glance, it looks like that was the intention - we construct _Mypair(_One_then_variadic_args_t(), _Right.key_comp(), [...] and then call _Swap_val anyways! Ditto the move-allocator constructor. _Move_assign also copy-assigns the comparator, then calls _Swap_val anyways. Hmm.

We're missing test coverage in dev11_437519_container_requirements; we have a non-assignable comparator copy_constructible_compare but we aren't testing the move constructor with it.

This is not a regression; it has been broken for a long time.