[libc++] ADL-proof <vector> by adding _VSTD:: qualification on calls.

[• Quuxplusone]

Summary

This is cleanup after d9a4f936d05.
Relevant blog post: https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/

[ldionne]

Please commit once CI passes. Thanks!

[• Quuxplusone]

Sorry, @ldionne, I've got a better test now, and more proposed _VSTDs!

I hacked my local "test_allocator.h" to use this "AdlTrap" trick, and discovered a few more places where ADL calls were being made. I don't propose to commit the test_allocator stuff, because a container using such an allocator breaks all ADL calls, including simple stuff like vec1 == vec2. But it was a fun experiment!

I have this as three commits locally; should I land them as three commits, or as one commit?

commit 57f653ea4d12d97d3a352df253425763da803486 (HEAD -> add-vstd)
Author: Arthur O'Dwyer <[e-mail]>
Date:   Wed Nov 18 09:00:56 2020 -0500

    [libc++] Add some more missing _VSTD:: to <vector>, with a regression test.
    
    This is cleanup after d9a4f936d05.
    
    Note that a vector whose allocator runs afoul of the unqualified code here, will
    likely also run afoul of simple things like `v1 == v2` (which is also an ADL call).
    
    Relevant blog post: https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/
    
    Differential Revision: https://reviews.llvm.org/D91708

commit 53b5db385145ba924db3a0d5d41758e22c288f46
Author: Arthur O'Dwyer <[e-mail]>
Date:   Wed Nov 18 18:39:14 2020 -0500

    [libc++] Add _VSTD:: qualification to __swap_allocator.
    
    Relevant blog post: https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/
    
    Differential Revision: https://reviews.llvm.org/D91708

commit 915d293f0fd6a73dd8daa90b7df5f66d81b54ddd
Author: Arthur O'Dwyer <[e-mail]>
Date:   Wed Nov 18 18:54:38 2020 -0500

    [libc++] Add _VSTD:: qualification consistently to __to_address.
    
    Relevant blog post: https://quuxplusone.github.io/blog/2019/09/26/uglification-doesnt-stop-adl/
    
    Differential Revision: https://reviews.llvm.org/D91708

[ldionne]

In D91708#2404126, @Quuxplusone wrote:

Sorry, @ldionne, I've got a better test now, and more proposed _VSTDs!

I hacked my local "test_allocator.h" to use this "AdlTrap" trick, and discovered a few more places where ADL calls were being made. I don't propose to commit the test_allocator stuff, because a container using such an allocator breaks all ADL calls, including simple stuff like vec1 == vec2. But it was a fun experiment!

I have this as three commits locally; should I land them as three commits, or as one commit?

As you wish. If it were me I might squash them since they are strongly related, but it's as you see fit.

[• Quuxplusone]

My change to __swap_allocators was bad. Define the helper templates before the template that uses them. (Before, two-phase lookup was letting us get away with the unqualified call. With the qualified call, buildbots were not happy.)

[• Quuxplusone]

In my new test, v.swap(w) is not expected to work before C++14, because before C++14, there was some metaprogramming to make vector<T>::swap noexcept if-and-only-if the allocator was nothrow-swappable, which required looking up an ADL swap for the allocator type, which hit my ADL trap.

In C++14, vector<T>::swap is always noexcept, and so we don't have to look up an ADL swap (unless the allocator is POCS, which my test's MyAlloc is not), and therefore the test passes.

I admit that there is a plausible argument to be made that my new test is too "whitebox" and "overconstrained" and shouldn't even be checked in.

[• Quuxplusone]

Disable the new test for C++03. It was either that, or add a max_size() member function to MyAlloc.

[• Quuxplusone]

I see now that when Harbormaster says "Harbormaster completed remote builds in B79288: Diff 306093." with a little green checkmark next to it, that little green checkmark does not mean that the remote build actually succeeded and passed all the tests! It means that the (possibly failing) build results are available to view.

[ldionne]

Indeed. This is the thing you want to be looking at:

[• Quuxplusone]

Re-updating the patch, as now I'm super paranoid about seeing the tests pass. No (intended) changes since the last update. I'll watch for the buildkite run to be green and then land this.

libcxx/include/__hash_table

_LIBCPP_ASSERT(__node_traits::propagate_on_container_swap::value ||
                    "list::swap: Either propagate_on_container_swap must be true"
                    " or the allocators must compare equal");
     {
     __node_pointer_pointer __npp = __bucket_list_.release();
     __bucket_list_.reset(__u.__bucket_list_.release());
     __u.__bucket_list_.reset(__npp);
     }
     _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
-    __swap_allocator(__bucket_list_.get_deleter().__alloc(),
+    _VSTD::__swap_allocator(__bucket_list_.get_deleter().__alloc(),
              __u.__bucket_list_.get_deleter().__alloc());
-    __swap_allocator(__node_alloc(), __u.__node_alloc());
+    _VSTD::__swap_allocator(__node_alloc(), __u.__node_alloc());
     _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
     __p2_.swap(__u.__p2_);
     __p3_.swap(__u.__p3_);
     if (size() > 0)
         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
             __p1_.first().__ptr();
     if (__u.size() > 0)
         __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =

libcxx/include/__split_buffer

 }
 
 template <class _Tp, class _Allocator>
 inline
 void
 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type)
 {
     while (__begin_ != __new_begin)
-        __alloc_traits::destroy(__alloc(), __to_address(__begin_++));
+        __alloc_traits::destroy(__alloc(), _VSTD::__to_address(__begin_++));
 }
 
 template <class _Tp, class _Allocator>
 inline
 void
 __split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type)
 {
     __begin_ = __new_begin;
 }
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT
 {
     while (__new_last != __end_)
-        __alloc_traits::destroy(__alloc(), __to_address(--__end_));
+        __alloc_traits::destroy(__alloc(), _VSTD::__to_address(--__end_));
 }
 
 template <class _Tp, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 __split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT
 {
     __end_ = __new_last;

 __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x)
         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value||
                    __is_nothrow_swappable<__alloc_rr>::value)
 {
     _VSTD::swap(__first_, __x.__first_);
     _VSTD::swap(__begin_, __x.__begin_);
     _VSTD::swap(__end_, __x.__end_);
     _VSTD::swap(__end_cap(), __x.__end_cap());
-    __swap_allocator(__alloc(), __x.__alloc());
+    _VSTD::__swap_allocator(__alloc(), __x.__alloc());
 }
 
 template <class _Tp, class _Allocator>
 void
 __split_buffer<_Tp, _Allocator>::reserve(size_type __n)
 {
     if (__n < capacity())
     {

libcxx/include/__tree

#if _LIBCPP_STD_VER <= 11
             )
 #else
         _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value)
 #endif
 {
     using _VSTD::swap;
     swap(__begin_node_, __t.__begin_node_);
     swap(__pair1_.first(), __t.__pair1_.first());
-    __swap_allocator(__node_alloc(), __t.__node_alloc());
+    _VSTD::__swap_allocator(__node_alloc(), __t.__node_alloc());
     __pair3_.swap(__t.__pair3_);
     if (size() == 0)
         __begin_node() = __end_node();
     else
         __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node());
     if (__t.size() == 0)
         __t.__begin_node() = __t.__end_node();
     else

libcxx/include/deque

 #else
         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
                     __is_nothrow_swappable<allocator_type>::value)
 #endif
 {
     __map_.swap(__c.__map_);
     _VSTD::swap(__start_, __c.__start_);
     _VSTD::swap(size(), __c.size());
-    __swap_allocator(__alloc(), __c.__alloc());
+    _VSTD::__swap_allocator(__alloc(), __c.__alloc());
 }
 
 template <class _Tp, class _Allocator>
 void
 __deque_base<_Tp, _Allocator>::clear() _NOEXCEPT
 {
     allocator_type& __a = __alloc();
     for (iterator __i = begin(), __e = end(); __i != __e; ++__i)
deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l,
     allocator_type& __a = __base::__alloc();
     size_type __back_capacity = __back_spare();
     if (__n > __back_capacity)
         __add_back_capacity(__n - __back_capacity);
     // __n <= __back_capacity
     for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
       _ConstructTransaction __tx(this, __br);
       for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) {
-        __alloc_traits::construct(__a, std::__to_address(__tx.__pos_), *__f);
+        __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), *__f);
       }
     }
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__append(size_type __n)
 {
     allocator_type& __a = __base::__alloc();
     size_type __back_capacity = __back_spare();
     if (__n > __back_capacity)
         __add_back_capacity(__n - __back_capacity);
     // __n <= __back_capacity
     for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
       _ConstructTransaction __tx(this, __br);
       for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
-        __alloc_traits::construct(__a, std::__to_address(__tx.__pos_));
+        __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_));
       }
     }
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v)
 {
     allocator_type& __a = __base::__alloc();
     size_type __back_capacity = __back_spare();
     if (__n > __back_capacity)
         __add_back_capacity(__n - __back_capacity);
     // __n <= __back_capacity
     for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) {
       _ConstructTransaction __tx(this, __br);
       for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
-        __alloc_traits::construct(__a, std::__to_address(__tx.__pos_), __v);
+        __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), __v);
       }
     }
 
 }
 
 // Create front capacity for one block of elements.
 // Strong guarantee.  Either do it or don't touch anything.
 template <class _Tp, class _Allocator>
#endif  // _LIBCPP_NO_EXCEPTIONS
     }
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::pop_front()
 {
     allocator_type& __a = __base::__alloc();
-    __alloc_traits::destroy(__a, __to_address(*(__base::__map_.begin() +
+    __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() +
                                                     __base::__start_ / __base::__block_size) +
                                                     __base::__start_ % __base::__block_size));
     --__base::size();
     ++__base::__start_;
     __maybe_remove_front_spare();
 }
 
 template <class _Tp, class _Allocator>
 void
 deque<_Tp, _Allocator>::pop_back()
 {
     _LIBCPP_ASSERT(!empty(), "deque::pop_back called for empty deque");
     allocator_type& __a = __base::__alloc();
     size_type __p = __base::size() + __base::__start_ - 1;
-    __alloc_traits::destroy(__a, __to_address(*(__base::__map_.begin() +
+    __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() +
                                                     __p / __base::__block_size) +
                                                     __p % __base::__block_size));
     --__base::size();
     __maybe_remove_back_spare();
 }
 
 // move assign [__f, __l) to [__r, __r + (__l-__f)).
 // If __vt points into [__f, __l), then subtract (__f - __r) from __vt.

libcxx/include/forward_list

 __forward_list_base<_Tp, _Alloc>::swap(__forward_list_base& __x)
 #if _LIBCPP_STD_VER >= 14
         _NOEXCEPT
 #else
         _NOEXCEPT_(!__node_traits::propagate_on_container_move_assignment::value ||
                     __is_nothrow_swappable<__node_allocator>::value)
 #endif
 {
-    __swap_allocator(__alloc(), __x.__alloc(),
+    _VSTD::__swap_allocator(__alloc(), __x.__alloc(),
             integral_constant<bool, __node_traits::propagate_on_container_swap::value>());
     using _VSTD::swap;
     swap(__before_begin()->__next_, __x.__before_begin()->__next_);
 }
 
 template <class _Tp, class _Alloc>
 void
 __forward_list_base<_Tp, _Alloc>::clear() _NOEXCEPT

libcxx/include/list

#else
                     __is_nothrow_swappable<allocator_type>::value)
 #endif
 {
     _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
                    this->__node_alloc() == __c.__node_alloc(),
                    "list::swap: Either propagate_on_container_swap must be true"
                    " or the allocators must compare equal");
     using _VSTD::swap;
-    __swap_allocator(__node_alloc(), __c.__node_alloc());
+    _VSTD::__swap_allocator(__node_alloc(), __c.__node_alloc());
     swap(__sz(), __c.__sz());
     swap(__end_, __c.__end_);
     if (__sz() == 0)
         __end_.__next_ = __end_.__prev_ = __end_as_link();
     else
         __end_.__prev_->__next_ = __end_.__next_->__prev_ = __end_as_link();
     if (__c.__sz() == 0)
         __c.__end_.__next_ = __c.__end_.__prev_ = __c.__end_as_link();

libcxx/include/memory

 {
     return static_cast<_Tp*>(__undeclare_reachable(__p));
 }
 
 _LIBCPP_FUNC_VIS void* align(size_t __align, size_t __sz, void*& __ptr, size_t& __space);
 
 // --- Helper for container swap --
 template <typename _Alloc>
-inline _LIBCPP_INLINE_VISIBILITY
-void __swap_allocator(_Alloc & __a1, _Alloc & __a2)
+_LIBCPP_INLINE_VISIBILITY
+void __swap_allocator(_Alloc & __a1, _Alloc & __a2, true_type)
 #if _LIBCPP_STD_VER >= 14
     _NOEXCEPT
 #else
     _NOEXCEPT_(__is_nothrow_swappable<_Alloc>::value)
 #endif
 {
-    __swap_allocator(__a1, __a2,
-      integral_constant<bool, _VSTD::allocator_traits<_Alloc>::propagate_on_container_swap::value>());
+    using _VSTD::swap;
+    swap(__a1, __a2);
 }
 
 template <typename _Alloc>
-_LIBCPP_INLINE_VISIBILITY
-void __swap_allocator(_Alloc & __a1, _Alloc & __a2, true_type)
+inline _LIBCPP_INLINE_VISIBILITY
+void __swap_allocator(_Alloc &, _Alloc &, false_type) _NOEXCEPT {}
+
+template <typename _Alloc>
+inline _LIBCPP_INLINE_VISIBILITY
+void __swap_allocator(_Alloc & __a1, _Alloc & __a2)
 #if _LIBCPP_STD_VER >= 14
     _NOEXCEPT
 #else
     _NOEXCEPT_(__is_nothrow_swappable<_Alloc>::value)
 #endif
 {
-    using _VSTD::swap;
-    swap(__a1, __a2);
+    _VSTD::__swap_allocator(__a1, __a2,
+      integral_constant<bool, _VSTD::allocator_traits<_Alloc>::propagate_on_container_swap::value>());
 }
 
-template <typename _Alloc>
-inline _LIBCPP_INLINE_VISIBILITY
-void __swap_allocator(_Alloc &, _Alloc &, false_type) _NOEXCEPT {}
-
 template <typename _Alloc, typename _Traits=allocator_traits<_Alloc> >
 struct __noexcept_move_assign_container : public integral_constant<bool,
     _Traits::propagate_on_container_move_assignment::value
 #if _LIBCPP_STD_VER > 14
         || _Traits::is_always_equal::value
 #else
         && is_nothrow_move_assignable<_Alloc>::value
 #endif

libcxx/include/string

if (!__str.__is_long())
         __get_db()->__invalidate_all(&__str);
     __get_db()->swap(this, &__str);
 #endif
     _LIBCPP_ASSERT(
         __alloc_traits::propagate_on_container_swap::value ||
         __alloc_traits::is_always_equal::value ||
         __alloc() == __str.__alloc(), "swapping non-equal allocators");
     _VSTD::swap(__r_.first(), __str.__r_.first());
-    __swap_allocator(__alloc(), __str.__alloc());
+    _VSTD::__swap_allocator(__alloc(), __str.__alloc());
 }
 
 // find
 
 template <class _Traits>
 struct _LIBCPP_HIDDEN __traits_eq
 {
     typedef typename _Traits::char_type char_type;

libcxx/include/vector

 #endif
 
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
 {
 
     __annotate_delete();
-    __construct_backward_with_exception_guarantees(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
+    _VSTD::__construct_backward_with_exception_guarantees(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
     _VSTD::swap(this->__begin_, __v.__begin_);
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
     __v.__first_ = __v.__begin_;
     __annotate_new(size());
     __invalidate_all_iterators();
 }
 
 template <class _Tp, class _Allocator>
 typename vector<_Tp, _Allocator>::pointer
 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
 {
     __annotate_delete();
     pointer __r = __v.__begin_;
-    __construct_backward_with_exception_guarantees(this->__alloc(), this->__begin_, __p, __v.__begin_);
-    __construct_forward_with_exception_guarantees(this->__alloc(), __p, this->__end_, __v.__end_);
+    _VSTD::__construct_backward_with_exception_guarantees(this->__alloc(), this->__begin_, __p, __v.__begin_);
+    _VSTD::__construct_forward_with_exception_guarantees(this->__alloc(), __p, this->__end_, __v.__end_);
     _VSTD::swap(this->__begin_, __v.__begin_);
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
     __v.__first_ = __v.__begin_;
     __annotate_new(size());
     __invalidate_all_iterators();
     return __r;
 }

 typename enable_if
 <
     __is_cpp17_forward_iterator<_ForwardIterator>::value,
     void
 >::type
 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
 {
     _ConstructTransaction __tx(*this, __n);
-    __construct_range_forward(this->__alloc(), __first, __last, __tx.__pos_);
+    _VSTD::__construct_range_forward(this->__alloc(), __first, __last, __tx.__pos_);
 }
 
 //  Default constructs __n objects starting at __end_
 //  throws if construction throws
 //  Postcondition:  size() == size() + __n
 //  Exception safety: strong.
 template <class _Tp, class _Allocator>
 void

 {
     _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
                    this->__alloc() == __x.__alloc(),
                    "vector::swap: Either propagate_on_container_swap must be true"
                    " or the allocators must compare equal");
     _VSTD::swap(this->__begin_, __x.__begin_);
     _VSTD::swap(this->__end_, __x.__end_);
     _VSTD::swap(this->__end_cap(), __x.__end_cap());
-    __swap_allocator(this->__alloc(), __x.__alloc(),
+    _VSTD::__swap_allocator(this->__alloc(), __x.__alloc(),
         integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>());
 #if _LIBCPP_DEBUG_LEVEL == 2
     __get_db()->swap(this, &__x);
 #endif
 }
 
 template <class _Tp, class _Allocator>
 bool

 #else
     _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
                 __is_nothrow_swappable<allocator_type>::value)
 #endif
 {
     _VSTD::swap(this->__begin_, __x.__begin_);
     _VSTD::swap(this->__size_, __x.__size_);
     _VSTD::swap(this->__cap(), __x.__cap());
-    __swap_allocator(this->__alloc(), __x.__alloc(),
+    _VSTD::__swap_allocator(this->__alloc(), __x.__alloc(),
         integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
 }
 
 template <class _Allocator>
 void
 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
 {
     size_type __cs = size();

libcxx/test/libcxx/containers/sequences/vector/robust_against_adl.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03
+
+// <vector>
+
+#include <vector>
+
+#include "test_macros.h"
+
+struct Incomplete;
+template<class T> struct Holder { T t; };
+
+template<class T, class AdlTrap = Holder<Incomplete>>
+struct MyAlloc {
+    using value_type = T;
+    T *allocate(int n) { return std::allocator<T>().allocate(n); }
+    void deallocate(T *p, int n) { return std::allocator<T>().deallocate(p, n); }
+};
+
+int main(int, char**)
+{
+    std::vector<int, MyAlloc<int>> v;
+    std::vector<int, MyAlloc<int>> w;
+    v.push_back(1);
+    v.insert(v.end(), 2);
+    v.insert(v.end(), w.begin(), w.end());
+    v.pop_back();
+    v.erase(v.begin());
+    v.erase(v.begin(), v.end());
+#if TEST_STD_VER >= 14
+    v.swap(w);
+#endif
+    return 0;
+}