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

[• Quuxplusone]

Summary

This affects only vectors with weird/malicious allocators, the same corner case covered in D91708, but for vector<bool> this time.

Also ADL-proof <__tree>, which affects only sets and maps with weird/malicious allocators where the ADL trap is in the fancy pointer type.

Also drive-by _VSTD:: qualification in the guts of std::bind, std::packaged_task, std::condition_variable.

I think this is likely the last of my ADL-proofing patches for a while; I know I've left some harmless (primitive-type-only) helpers in <locale> and <charconv>, but basically everything is ADL-proofed that can be, now, AFAIK. After this I'll probably spend a little time looking at constexpr algorithms again.

libcxx/include/__bit_reference

 }
 
 template <class _Cp, bool _IsConst, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<_Cp, _IsConst>
 find(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
 {
     if (static_cast<bool>(__value_))
-        return __find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
-    return __find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
+        return _VSTD::__find_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
+    return _VSTD::__find_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
 }
 
 // count
 
 template <class _Cp, bool _IsConst>
 typename __bit_iterator<_Cp, _IsConst>::difference_type
 __count_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n)
 {

 }
 
 template <class _Cp, bool _IsConst, class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY
 typename __bit_iterator<_Cp, _IsConst>::difference_type
 count(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value_)
 {
     if (static_cast<bool>(__value_))
-        return __count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
-    return __count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
+        return _VSTD::__count_bool_true(__first, static_cast<typename _Cp::size_type>(__last - __first));
+    return _VSTD::__count_bool_false(__first, static_cast<typename _Cp::size_type>(__last - __first));
 }
 
 // fill_n
 
 template <class _Cp>
 void
 __fill_n_false(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n)
 {

 template <class _Cp>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 fill_n(__bit_iterator<_Cp, false> __first, typename _Cp::size_type __n, bool __value_)
 {
     if (__n > 0)
     {
         if (__value_)
-            __fill_n_true(__first, __n);
+            _VSTD::__fill_n_true(__first, __n);
         else
-            __fill_n_false(__first, __n);
+            _VSTD::__fill_n_false(__first, __n);
     }
 }
 
 // fill
 
 template <class _Cp>
 inline _LIBCPP_INLINE_VISIBILITY
 void

 }
 
 template <class _Cp, bool _IsConst>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<_Cp, false>
 copy(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
 {
     if (__first.__ctz_ == __result.__ctz_)
-        return __copy_aligned(__first, __last, __result);
-    return __copy_unaligned(__first, __last, __result);
+        return _VSTD::__copy_aligned(__first, __last, __result);
+    return _VSTD::__copy_unaligned(__first, __last, __result);
 }
 
 // copy_backward
 
 template <class _Cp, bool _IsConst>
 __bit_iterator<_Cp, false>
 __copy_backward_aligned(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last,
                                                      __bit_iterator<_Cp, false> __result)

 }
 
 template <class _Cp, bool _IsConst>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<_Cp, false>
 copy_backward(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)
 {
     if (__last.__ctz_ == __result.__ctz_)
-        return __copy_backward_aligned(__first, __last, __result);
-    return __copy_backward_unaligned(__first, __last, __result);
+        return _VSTD::__copy_backward_aligned(__first, __last, __result);
+    return _VSTD::__copy_backward_unaligned(__first, __last, __result);
 }
 
 // move
 
 template <class _Cp, bool _IsConst>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<_Cp, false>
 move(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, __bit_iterator<_Cp, false> __result)

 
 template <class __C1, class __C2>
 inline _LIBCPP_INLINE_VISIBILITY
 __bit_iterator<__C2, false>
 swap_ranges(__bit_iterator<__C1, false> __first1, __bit_iterator<__C1, false> __last1,
             __bit_iterator<__C2, false> __first2)
 {
     if (__first1.__ctz_ == __first2.__ctz_)
-        return __swap_ranges_aligned(__first1, __last1, __first2);
-    return __swap_ranges_unaligned(__first1, __last1, __first2);
+        return _VSTD::__swap_ranges_aligned(__first1, __last1, __first2);
+    return _VSTD::__swap_ranges_unaligned(__first1, __last1, __first2);
 }
 
 // rotate
 
 template <class _Cp>
 struct __bit_array
 {
     typedef typename _Cp::difference_type difference_type;

 }
 
 template <class _Cp, bool _IC1, bool _IC2>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 equal(__bit_iterator<_Cp, _IC1> __first1, __bit_iterator<_Cp, _IC1> __last1, __bit_iterator<_Cp, _IC2> __first2)
 {
     if (__first1.__ctz_ == __first2.__ctz_)
-        return __equal_aligned(__first1, __last1, __first2);
-    return __equal_unaligned(__first1, __last1, __first2);
+        return _VSTD::__equal_aligned(__first1, __last1, __first2);
+    return _VSTD::__equal_unaligned(__first1, __last1, __first2);
 }
 
 template <class _Cp, bool _IsConst,
           typename _Cp::__storage_type>
 class __bit_iterator
 {
 public:
     typedef typename _Cp::difference_type                                                          difference_type;

libcxx/include/__mutex_base

 {
     using namespace chrono;
     using __clock_tp_ns = time_point<_Clock, nanoseconds>;
 
     typename _Clock::time_point __now = _Clock::now();
     if (__t <= __now)
         return cv_status::timeout;
 
-    __clock_tp_ns __t_ns = __clock_tp_ns(__safe_nanosecond_cast(__t.time_since_epoch()));
+    __clock_tp_ns __t_ns = __clock_tp_ns(_VSTD::__safe_nanosecond_cast(__t.time_since_epoch()));
 
     __do_timed_wait(__lk, __t_ns);
     return _Clock::now() < __t ? cv_status::no_timeout : cv_status::timeout;
 }
 
 template <class _Clock, class _Duration, class _Predicate>
 bool
 condition_variable::wait_until(unique_lock<mutex>& __lk,
condition_variable::wait_for(unique_lock<mutex>& __lk,
     using namespace chrono;
     if (__d <= __d.zero())
         return cv_status::timeout;
     using __ns_rep = nanoseconds::rep;
     steady_clock::time_point __c_now = steady_clock::now();
 
 #if defined(_LIBCPP_HAS_COND_CLOCKWAIT)
     using __clock_tp_ns = time_point<steady_clock, nanoseconds>;
-    __ns_rep __now_count_ns = __safe_nanosecond_cast(__c_now.time_since_epoch()).count();
+    __ns_rep __now_count_ns = _VSTD::__safe_nanosecond_cast(__c_now.time_since_epoch()).count();
 #else
     using __clock_tp_ns = time_point<system_clock, nanoseconds>;
-    __ns_rep __now_count_ns = __safe_nanosecond_cast(system_clock::now().time_since_epoch()).count();
+    __ns_rep __now_count_ns = _VSTD::__safe_nanosecond_cast(system_clock::now().time_since_epoch()).count();
 #endif
 
-    __ns_rep __d_ns_count = __safe_nanosecond_cast(__d).count();
+    __ns_rep __d_ns_count = _VSTD::__safe_nanosecond_cast(__d).count();
 
     if (__now_count_ns > numeric_limits<__ns_rep>::max() - __d_ns_count) {
         __do_timed_wait(__lk, __clock_tp_ns::max());
     } else {
         __do_timed_wait(__lk, __clock_tp_ns(nanoseconds(__now_count_ns + __d_ns_count)));
     }
 
     return steady_clock::now() - __c_now < __d ? cv_status::no_timeout :

libcxx/include/__tree

__tree_sub_invariant(_NodePtr __x)
     // If this is red, neither child can be red
     if (!__x->__is_black_)
     {
         if (__x->__left_ && !__x->__left_->__is_black_)
             return 0;
         if (__x->__right_ && !__x->__right_->__is_black_)
             return 0;
     }
-    unsigned __h = __tree_sub_invariant(__x->__left_);
+    unsigned __h = _VSTD::__tree_sub_invariant(__x->__left_);
     if (__h == 0)
         return 0;  // invalid left subtree
-    if (__h != __tree_sub_invariant(__x->__right_))
+    if (__h != _VSTD::__tree_sub_invariant(__x->__right_))
         return 0;  // invalid or different height right subtree
     return __h + __x->__is_black_;  // return black height of this node
 }
 
 // Determines if the red black tree rooted at __root is a proper red black tree.
 //    __root == nullptr is a proper tree.  Returns true is __root is a proper
 //    red black tree, else returns false.
 template <class _NodePtr>
 bool
 __tree_invariant(_NodePtr __root)
 {
     if (__root == nullptr)
         return true;
     // check __x->__parent_ consistency
     if (__root->__parent_ == nullptr)
         return false;
-    if (!__tree_is_left_child(__root))
+    if (!_VSTD::__tree_is_left_child(__root))
         return false;
     // root must be black
     if (!__root->__is_black_)
         return false;
     // do normal node checks
-    return __tree_sub_invariant(__root) != 0;
+    return _VSTD::__tree_sub_invariant(__root) != 0;
 }
 
 // Returns:  pointer to the left-most node under __x.
 // Precondition:  __x != nullptr.
 template <class _NodePtr>
 inline _LIBCPP_INLINE_VISIBILITY
 _NodePtr
 __tree_min(_NodePtr __x) _NOEXCEPT

 
 // Returns:  pointer to the next in-order node after __x.
 // Precondition:  __x != nullptr.
 template <class _NodePtr>
 _NodePtr
 __tree_next(_NodePtr __x) _NOEXCEPT
 {
     if (__x->__right_ != nullptr)
-        return __tree_min(__x->__right_);
-    while (!__tree_is_left_child(__x))
+        return _VSTD::__tree_min(__x->__right_);
+    while (!_VSTD::__tree_is_left_child(__x))
         __x = __x->__parent_unsafe();
     return __x->__parent_unsafe();
 }
 
 template <class _EndNodePtr, class _NodePtr>
 inline _LIBCPP_INLINE_VISIBILITY
 _EndNodePtr
 __tree_next_iter(_NodePtr __x) _NOEXCEPT
 {
     if (__x->__right_ != nullptr)
-        return static_cast<_EndNodePtr>(__tree_min(__x->__right_));
-    while (!__tree_is_left_child(__x))
+        return static_cast<_EndNodePtr>(_VSTD::__tree_min(__x->__right_));
+    while (!_VSTD::__tree_is_left_child(__x))
         __x = __x->__parent_unsafe();
     return static_cast<_EndNodePtr>(__x->__parent_);
 }
 
 // Returns:  pointer to the previous in-order node before __x.
 // Precondition:  __x != nullptr.
 // Note: __x may be the end node.
 template <class _NodePtr, class _EndNodePtr>
 inline _LIBCPP_INLINE_VISIBILITY
 _NodePtr
 __tree_prev_iter(_EndNodePtr __x) _NOEXCEPT
 {
     if (__x->__left_ != nullptr)
-        return __tree_max(__x->__left_);
+        return _VSTD::__tree_max(__x->__left_);
     _NodePtr __xx = static_cast<_NodePtr>(__x);
-    while (__tree_is_left_child(__xx))
+    while (_VSTD::__tree_is_left_child(__xx))
         __xx = __xx->__parent_unsafe();
     return __xx->__parent_unsafe();
 }
 
 // Returns:  pointer to a node which has no children
 // Precondition:  __x != nullptr.
 template <class _NodePtr>
 _NodePtr

 void
 __tree_left_rotate(_NodePtr __x) _NOEXCEPT
 {
     _NodePtr __y = __x->__right_;
     __x->__right_ = __y->__left_;
     if (__x->__right_ != nullptr)
         __x->__right_->__set_parent(__x);
     __y->__parent_ = __x->__parent_;
-    if (__tree_is_left_child(__x))
+    if (_VSTD::__tree_is_left_child(__x))
         __x->__parent_->__left_ = __y;
     else
         __x->__parent_unsafe()->__right_ = __y;
     __y->__left_ = __x;
     __x->__set_parent(__y);
 }
 
 // Effects:  Makes __x->__left_ the subtree root with __x as its right child
 //           while preserving in-order order.
 // Precondition:  __x->__left_ != nullptr
 template <class _NodePtr>
 void
 __tree_right_rotate(_NodePtr __x) _NOEXCEPT
 {
     _NodePtr __y = __x->__left_;
     __x->__left_ = __y->__right_;
     if (__x->__left_ != nullptr)
         __x->__left_->__set_parent(__x);
     __y->__parent_ = __x->__parent_;
-    if (__tree_is_left_child(__x))
+    if (_VSTD::__tree_is_left_child(__x))
         __x->__parent_->__left_ = __y;
     else
         __x->__parent_unsafe()->__right_ = __y;
     __y->__right_ = __x;
     __x->__set_parent(__y);
 }
 
 // Effects:  Rebalances __root after attaching __x to a leaf.
 // Precondition:  __root != nulptr && __x != nullptr.
 //                __x has no children.
 //                __x == __root or == a direct or indirect child of __root.
 //                If __x were to be unlinked from __root (setting __root to
 //                  nullptr if __root == __x), __tree_invariant(__root) == true.
 // Postcondition: __tree_invariant(end_node->__left_) == true.  end_node->__left_
 //                may be different than the value passed in as __root.
 template <class _NodePtr>
 void
 __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
 {
     __x->__is_black_ = __x == __root;
     while (__x != __root && !__x->__parent_unsafe()->__is_black_)
     {
         // __x->__parent_ != __root because __x->__parent_->__is_black == false
-        if (__tree_is_left_child(__x->__parent_unsafe()))
+        if (_VSTD::__tree_is_left_child(__x->__parent_unsafe()))
         {
             _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;
             if (__y != nullptr && !__y->__is_black_)
             {
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = true;
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = __x == __root;
                 __y->__is_black_ = true;
             }
             else
             {
-                if (!__tree_is_left_child(__x))
+                if (!_VSTD::__tree_is_left_child(__x))
                 {
                     __x = __x->__parent_unsafe();
-                    __tree_left_rotate(__x);
+                    _VSTD::__tree_left_rotate(__x);
                 }
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = true;
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = false;
-                __tree_right_rotate(__x);
+                _VSTD::__tree_right_rotate(__x);
                 break;
             }
         }
         else
         {
             _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;
             if (__y != nullptr && !__y->__is_black_)
             {
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = true;
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = __x == __root;
                 __y->__is_black_ = true;
             }
             else
             {
-                if (__tree_is_left_child(__x))
+                if (_VSTD::__tree_is_left_child(__x))
                 {
                     __x = __x->__parent_unsafe();
-                    __tree_right_rotate(__x);
+                    _VSTD::__tree_right_rotate(__x);
                 }
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = true;
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = false;
-                __tree_left_rotate(__x);
+                _VSTD::__tree_left_rotate(__x);
                 break;
             }
         }
     }
 }
 
 // Precondition:  __root != nullptr && __z != nullptr.
 //                __tree_invariant(__root) == true.
 //                __z == __root or == a direct or indirect child of __root.
 // Effects:  unlinks __z from the tree rooted at __root, rebalancing as needed.
 // Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_
 //                nor any of its children refer to __z.  end_node->__left_
 //                may be different than the value passed in as __root.
 template <class _NodePtr>
 void
 __tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT
 {
     // __z will be removed from the tree.  Client still needs to destruct/deallocate it
     // __y is either __z, or if __z has two children, __tree_next(__z).
     // __y will have at most one child.
     // __y will be the initial hole in the tree (make the hole at a leaf)
     _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ?
-                    __z : __tree_next(__z);
+                    __z : _VSTD::__tree_next(__z);
     // __x is __y's possibly null single child
     _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;
     // __w is __x's possibly null uncle (will become __x's sibling)
     _NodePtr __w = nullptr;
     // link __x to __y's parent, and find __w
     if (__x != nullptr)
         __x->__parent_ = __y->__parent_;
-    if (__tree_is_left_child(__y))
+    if (_VSTD::__tree_is_left_child(__y))
     {
         __y->__parent_->__left_ = __x;
         if (__y != __root)
             __w = __y->__parent_unsafe()->__right_;
         else
             __root = __x;  // __w == nullptr
     }
     else
     {
         __y->__parent_unsafe()->__right_ = __x;
         // __y can't be root if it is a right child
         __w = __y->__parent_->__left_;
     }
     bool __removed_black = __y->__is_black_;
     // If we didn't remove __z, do so now by splicing in __y for __z,
     //    but copy __z's color.  This does not impact __x or __w.
     if (__y != __z)
     {
         // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
         __y->__parent_ = __z->__parent_;
-        if (__tree_is_left_child(__z))
+        if (_VSTD::__tree_is_left_child(__z))
             __y->__parent_->__left_ = __y;
         else
             __y->__parent_unsafe()->__right_ = __y;
         __y->__left_ = __z->__left_;
         __y->__left_->__set_parent(__y);
         __y->__right_ = __z->__right_;
         if (__y->__right_ != nullptr)
             __y->__right_->__set_parent(__y);
if (__removed_black && __root != nullptr)
         {
             //  Else __x isn't root, and is "doubly black", even though it may
             //     be null.  __w can not be null here, else the parent would
             //     see a black height >= 2 on the __x side and a black height
             //     of 1 on the __w side (__w must be a non-null black or a red
             //     with a non-null black child).
             while (true)
             {
-                if (!__tree_is_left_child(__w))  // if x is left child
+                if (!_VSTD::__tree_is_left_child(__w))  // if x is left child
                 {
                     if (!__w->__is_black_)
                     {
                         __w->__is_black_ = true;
                         __w->__parent_unsafe()->__is_black_ = false;
-                        __tree_left_rotate(__w->__parent_unsafe());
+                        _VSTD::__tree_left_rotate(__w->__parent_unsafe());
                         // __x is still valid
                         // reset __root only if necessary
                         if (__root == __w->__left_)
                             __root = __w;
                         // reset sibling, and it still can't be null
                         __w = __w->__left_->__right_;
                     }
                     // __w->__is_black_ is now true, __w may have null children
                     if ((__w->__left_  == nullptr || __w->__left_->__is_black_) &&
                         (__w->__right_ == nullptr || __w->__right_->__is_black_))
                     {
                         __w->__is_black_ = false;
                         __x = __w->__parent_unsafe();
                         // __x can no longer be null
                         if (__x == __root || !__x->__is_black_)
                         {
                             __x->__is_black_ = true;
                             break;
                         }
                         // reset sibling, and it still can't be null
-                        __w = __tree_is_left_child(__x) ?
+                        __w = _VSTD::__tree_is_left_child(__x) ?
                                     __x->__parent_unsafe()->__right_ :
                                     __x->__parent_->__left_;
                         // continue;
                     }
                     else  // __w has a red child
                     {
                         if (__w->__right_ == nullptr || __w->__right_->__is_black_)
                         {
                             // __w left child is non-null and red
                             __w->__left_->__is_black_ = true;
                             __w->__is_black_ = false;
-                            __tree_right_rotate(__w);
+                            _VSTD::__tree_right_rotate(__w);
                             // __w is known not to be root, so root hasn't changed
                             // reset sibling, and it still can't be null
                             __w = __w->__parent_unsafe();
                         }
                         // __w has a right red child, left child may be null
                         __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
                         __w->__parent_unsafe()->__is_black_ = true;
                         __w->__right_->__is_black_ = true;
-                        __tree_left_rotate(__w->__parent_unsafe());
+                        _VSTD::__tree_left_rotate(__w->__parent_unsafe());
                         break;
                     }
                 }
                 else
                 {
                     if (!__w->__is_black_)
                     {
                         __w->__is_black_ = true;
                         __w->__parent_unsafe()->__is_black_ = false;
-                        __tree_right_rotate(__w->__parent_unsafe());
+                        _VSTD::__tree_right_rotate(__w->__parent_unsafe());
                         // __x is still valid
                         // reset __root only if necessary
                         if (__root == __w->__right_)
                             __root = __w;
                         // reset sibling, and it still can't be null
                         __w = __w->__right_->__left_;
                     }
                     // __w->__is_black_ is now true, __w may have null children
                     if ((__w->__left_  == nullptr || __w->__left_->__is_black_) &&
                         (__w->__right_ == nullptr || __w->__right_->__is_black_))
                     {
                         __w->__is_black_ = false;
                         __x = __w->__parent_unsafe();
                         // __x can no longer be null
                         if (!__x->__is_black_ || __x == __root)
                         {
                             __x->__is_black_ = true;
                             break;
                         }
                         // reset sibling, and it still can't be null
-                        __w = __tree_is_left_child(__x) ?
+                        __w = _VSTD::__tree_is_left_child(__x) ?
                                     __x->__parent_unsafe()->__right_ :
                                     __x->__parent_->__left_;
                         // continue;
                     }
                     else  // __w has a red child
                     {
                         if (__w->__left_ == nullptr || __w->__left_->__is_black_)
                         {
                             // __w right child is non-null and red
                             __w->__right_->__is_black_ = true;
                             __w->__is_black_ = false;
-                            __tree_left_rotate(__w);
+                            _VSTD::__tree_left_rotate(__w);
                             // __w is known not to be root, so root hasn't changed
                             // reset sibling, and it still can't be null
                             __w = __w->__parent_unsafe();
                         }
                         // __w has a left red child, right child may be null
                         __w->__is_black_ = __w->__parent_unsafe()->__is_black_;
                         __w->__parent_unsafe()->__is_black_ = true;
                         __w->__left_->__is_black_ = true;
-                        __tree_right_rotate(__w->__parent_unsafe());
+                        _VSTD::__tree_right_rotate(__w->__parent_unsafe());
                         break;
                     }
                 }
             }
         }
     }
 }
 
#endif
     _LIBCPP_INLINE_VISIBILITY reference operator*() const
         {return __get_np()->__value_;}
     _LIBCPP_INLINE_VISIBILITY pointer operator->() const
         {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_iterator& operator++() {
       __ptr_ = static_cast<__iter_pointer>(
-          __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
+          _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
       return *this;
     }
     _LIBCPP_INLINE_VISIBILITY
     __tree_iterator operator++(int)
         {__tree_iterator __t(*this); ++(*this); return __t;}
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_iterator& operator--() {
-      __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>(
+      __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>(
           static_cast<__end_node_pointer>(__ptr_)));
       return *this;
     }
     _LIBCPP_INLINE_VISIBILITY
     __tree_iterator operator--(int)
         {__tree_iterator __t(*this); --(*this); return __t;}
 
     friend _LIBCPP_INLINE_VISIBILITY
public:
     _LIBCPP_INLINE_VISIBILITY reference operator*() const
         {return __get_np()->__value_;}
     _LIBCPP_INLINE_VISIBILITY pointer operator->() const
         {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);}
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator& operator++() {
       __ptr_ = static_cast<__iter_pointer>(
-          __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
+          _VSTD::__tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_)));
       return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator operator++(int)
         {__tree_const_iterator __t(*this); ++(*this); return __t;}
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator& operator--() {
-      __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>(
+      __ptr_ = static_cast<__iter_pointer>(_VSTD::__tree_prev_iter<__node_base_pointer>(
           static_cast<__end_node_pointer>(__ptr_)));
       return *this;
     }
 
     _LIBCPP_INLINE_VISIBILITY
     __tree_const_iterator operator--(int)
         {__tree_const_iterator __t(*this); --(*this); return __t;}
 

 //    __cache->right_ == nullptr
 //    This is no longer a red-black tree
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::__node_pointer
 __tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT
 {
     if (__cache->__parent_ == nullptr)
         return nullptr;
-    if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
+    if (_VSTD::__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
     {
         __cache->__parent_->__left_ = nullptr;
         __cache = static_cast<__node_pointer>(__cache->__parent_);
         if (__cache->__right_ == nullptr)
             return __cache;
-        return static_cast<__node_pointer>(__tree_leaf(__cache->__right_));
+        return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__right_));
     }
     // __cache is right child
     __cache->__parent_unsafe()->__right_ = nullptr;
     __cache = static_cast<__node_pointer>(__cache->__parent_);
     if (__cache->__left_ == nullptr)
         return __cache;
-    return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));
+    return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__left_));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>&
 __tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
 {
     if (this != &__t)
     {

 {
     __new_node->__left_   = nullptr;
     __new_node->__right_  = nullptr;
     __new_node->__parent_ = __parent;
     // __new_node->__is_black_ is initialized in __tree_balance_after_insert
     __child = __new_node;
     if (__begin_node()->__left_ != nullptr)
         __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);
-    __tree_balance_after_insert(__end_node()->__left_, __child);
+    _VSTD::__tree_balance_after_insert(__end_node()->__left_, __child);
     ++size();
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key, class... _Args>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>
 __tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
 {

 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT
 {
     iterator __r(__ptr);
     ++__r;
     if (__begin_node() == __ptr)
         __begin_node() = __r.__ptr_;
     --size();
-    __tree_remove(__end_node()->__left_,
+    _VSTD::__tree_remove(__end_node()->__left_,
                          static_cast<__node_base_pointer>(__ptr));
     return __r;
 }
 
 #if _LIBCPP_STD_VER > 14
 template <class _Tp, class _Compare, class _Allocator>
 template <class _NodeHandle, class _InsertReturnType>
 _LIBCPP_INLINE_VISIBILITY
 _InsertReturnType
while (__rt != nullptr)
             __rt = static_cast<__node_pointer>(__rt->__left_);
         }
         else if (value_comp()(__rt->__value_, __k))
             __rt = static_cast<__node_pointer>(__rt->__right_);
         else
             return _Pp(iterator(__rt),
                       iterator(
                           __rt->__right_ != nullptr ?
-                              static_cast<__iter_pointer>(__tree_min(__rt->__right_))
+                              static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_))
                             : __result));
     }
     return _Pp(iterator(__result), iterator(__result));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator,
while (__rt != nullptr)
             __rt = static_cast<__node_pointer>(__rt->__left_);
         }
         else if (value_comp()(__rt->__value_, __k))
             __rt = static_cast<__node_pointer>(__rt->__right_);
         else
             return _Pp(const_iterator(__rt),
                       const_iterator(
                           __rt->__right_ != nullptr ?
-                              static_cast<__iter_pointer>(__tree_min(__rt->__right_))
+                              static_cast<__iter_pointer>(_VSTD::__tree_min(__rt->__right_))
                             : __result));
     }
     return _Pp(const_iterator(__result), const_iterator(__result));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 pair<typename __tree<_Tp, _Compare, _Allocator>::iterator,
__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
     if (__begin_node() == __p.__ptr_)
     {
         if (__np->__right_ != nullptr)
             __begin_node() = static_cast<__iter_pointer>(__np->__right_);
         else
             __begin_node() = static_cast<__iter_pointer>(__np->__parent_);
     }
     --size();
-    __tree_remove(__end_node()->__left_,
+    _VSTD::__tree_remove(__end_node()->__left_,
                          static_cast<__node_base_pointer>(__np));
     return __node_holder(__np, _Dp(__node_alloc(), true));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 swap(__tree<_Tp, _Compare, _Allocator>& __x,
      __tree<_Tp, _Compare, _Allocator>& __y)

libcxx/include/array

 _LIBCPP_INLINE_VISIBILITY constexpr array<remove_cv_t<_Tp>, _Size>
 to_array(_Tp (&__arr)[_Size]) noexcept(is_nothrow_constructible_v<_Tp, _Tp&>) {
   static_assert(
       !is_array_v<_Tp>,
       "[array.creation]/1: to_array does not accept multidimensional arrays.");
   static_assert(
       is_constructible_v<_Tp, _Tp&>,
       "[array.creation]/1: to_array requires copy constructible elements.");
-  return __to_array_lvalue_impl(__arr, make_index_sequence<_Size>());
+  return _VSTD::__to_array_lvalue_impl(__arr, make_index_sequence<_Size>());
 }
 
 template <typename _Tp, size_t _Size>
 _LIBCPP_INLINE_VISIBILITY constexpr array<remove_cv_t<_Tp>, _Size>
 to_array(_Tp(&&__arr)[_Size]) noexcept(is_nothrow_move_constructible_v<_Tp>) {
   static_assert(
       !is_array_v<_Tp>,
       "[array.creation]/4: to_array does not accept multidimensional arrays.");
   static_assert(
       is_move_constructible_v<_Tp>,
       "[array.creation]/4: to_array requires move constructible elements.");
-  return __to_array_rvalue_impl(_VSTD::move(__arr),
+  return _VSTD::__to_array_rvalue_impl(_VSTD::move(__arr),
                                        make_index_sequence<_Size>());
 }
 
 #endif // _LIBCPP_STD_VER > 17
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif  // _LIBCPP_ARRAY

libcxx/include/bitset

bitset<_Size>::to_string(char __zero, char __one) const
     return to_string<char, char_traits<char>, allocator<char> >(__zero, __one);
 }
 
 template <size_t _Size>
 inline
 size_t
 bitset<_Size>::count() const _NOEXCEPT
 {
-    return static_cast<size_t>(__count_bool_true(base::__make_iter(0), _Size));
+    return static_cast<size_t>(_VSTD::__count_bool_true(base::__make_iter(0), _Size));
 }
 
 template <size_t _Size>
 inline
 bool
 bitset<_Size>::operator==(const bitset& __rhs) const _NOEXCEPT
 {
     return _VSTD::equal(base::__make_iter(0), base::__make_iter(_Size), __rhs.__make_iter(0));

libcxx/include/functional

 typename _EnableIf
 <
     is_bind_expression<_Ti>::value,
     __invoke_of<_Ti&, _Uj...>
 >::type
 __mu(_Ti& __ti, tuple<_Uj...>& __uj)
 {
     typedef typename __make_tuple_indices<sizeof...(_Uj)>::type __indices;
-    return  __mu_expand(__ti, __uj, __indices());
+    return _VSTD::__mu_expand(__ti, __uj, __indices());
 }
 
 template <bool IsPh, class _Ti, class _Uj>
 struct __mu_return2 {};
 
 template <class _Ti, class _Uj>
 struct __mu_return2<true, _Ti, _Uj>
 {

libcxx/include/future

     __f_.~__compressed_pair<_Fp, _Alloc>();
     __a.deallocate(_PTraits::pointer_to(*this), 1);
 }
 
 template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
 _Rp
 __packaged_task_func<_Fp, _Alloc, _Rp(_ArgTypes...)>::operator()(_ArgTypes&& ... __arg)
 {
-    return __invoke(__f_.first(), _VSTD::forward<_ArgTypes>(__arg)...);
+    return _VSTD::__invoke(__f_.first(), _VSTD::forward<_ArgTypes>(__arg)...);
 }
 
 template <class _Callable> class __packaged_task_function;
 
 template<class _Rp, class ..._ArgTypes>
 class _LIBCPP_AVAILABILITY_FUTURE __packaged_task_function<_Rp(_ArgTypes...)>
 {
     typedef __packaged_task_base<_Rp(_ArgTypes...)> __base;

         typedef typename __make_tuple_indices<1+sizeof...(_Args), 1>::type _Index;
         return __execute(_Index());
     }
 private:
     template <size_t ..._Indices>
     _Rp
     __execute(__tuple_indices<_Indices...>)
     {
-        return __invoke(_VSTD::move(_VSTD::get<0>(__f_)), _VSTD::move(_VSTD::get<_Indices>(__f_))...);
+        return _VSTD::__invoke(_VSTD::move(_VSTD::get<0>(__f_)), _VSTD::move(_VSTD::get<_Indices>(__f_))...);
     }
 };
 
 inline _LIBCPP_INLINE_VISIBILITY bool __does_policy_contain(launch __policy, launch __value )
 { return (int(__policy) & int(__value)) != 0; }
 
 template <class _Fp, class... _Args>
 _LIBCPP_NODISCARD_AFTER_CXX17
 future<typename __invoke_of<typename decay<_Fp>::type, typename decay<_Args>::type...>::type>
 async(launch __policy, _Fp&& __f, _Args&&... __args)
 {
     typedef __async_func<typename decay<_Fp>::type, typename decay<_Args>::type...> _BF;
     typedef typename _BF::_Rp _Rp;
 
 #ifndef _LIBCPP_NO_EXCEPTIONS
     try
     {
 #endif
         if (__does_policy_contain(__policy, launch::async))
-        return _VSTD::__make_async_assoc_state<_Rp>(_BF(__decay_copy(_VSTD::forward<_Fp>(__f)),
-                                                     __decay_copy(_VSTD::forward<_Args>(__args))...));
+        return _VSTD::__make_async_assoc_state<_Rp>(_BF(_VSTD::__decay_copy(_VSTD::forward<_Fp>(__f)),
+                                                     _VSTD::__decay_copy(_VSTD::forward<_Args>(__args))...));
 #ifndef _LIBCPP_NO_EXCEPTIONS
     }
     catch ( ... ) { if (__policy == launch::async) throw ; }
 #endif
 
     if (__does_policy_contain(__policy, launch::deferred))
-        return _VSTD::__make_deferred_assoc_state<_Rp>(_BF(__decay_copy(_VSTD::forward<_Fp>(__f)),
-                                                        __decay_copy(_VSTD::forward<_Args>(__args))...));
+        return _VSTD::__make_deferred_assoc_state<_Rp>(_BF(_VSTD::__decay_copy(_VSTD::forward<_Fp>(__f)),
+                                                        _VSTD::__decay_copy(_VSTD::forward<_Args>(__args))...));
     return future<_Rp>{};
 }
 
 template <class _Fp, class... _Args>
 _LIBCPP_NODISCARD_AFTER_CXX17 inline _LIBCPP_INLINE_VISIBILITY
 future<typename __invoke_of<typename decay<_Fp>::type, typename decay<_Args>::type...>::type>
 async(_Fp&& __f, _Args&&... __args)
 {

libcxx/include/iomanip

__quoted_output ( basic_ostream<_CharT, _Traits> &__os,
     __str.push_back(__delim);
     for ( ; __first != __last; ++ __first )
     {
         if (_Traits::eq (*__first, __escape) || _Traits::eq (*__first, __delim))
             __str.push_back(__escape);
         __str.push_back(*__first);
     }
     __str.push_back(__delim);
-    return __put_character_sequence(__os, __str.data(), __str.size());
+    return _VSTD::__put_character_sequence(__os, __str.data(), __str.size());
 }
 
 template <class _CharT, class _Traits, class _String>
 basic_istream<_CharT, _Traits> &
 __quoted_input ( basic_istream<_CharT, _Traits> &__is, _String & __string, _CharT __delim, _CharT __escape )
 {
     __string.clear ();
     _CharT __c;

libcxx/include/mutex

void operator()()
         __execute(_Index());
     }
 
 private:
     template <size_t ..._Indices>
     _LIBCPP_INLINE_VISIBILITY
     void __execute(__tuple_indices<_Indices...>)
     {
-        __invoke(_VSTD::get<0>(_VSTD::move(__f_)), _VSTD::get<_Indices>(_VSTD::move(__f_))...);
+        _VSTD::__invoke(_VSTD::get<0>(_VSTD::move(__f_)), _VSTD::get<_Indices>(_VSTD::move(__f_))...);
     }
 };
 
 #else
 
 template <class _Fp>
 class __call_once_param
 {

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

 #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;
+    MyAlloc() = default;
+    template<class U> MyAlloc(const MyAlloc<U>&) {}
     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<bool, MyAlloc<bool>> vb;
+    std::vector<bool, MyAlloc<bool>> wb(100);
+
     std::vector<int, MyAlloc<int>> v;
-    std::vector<int, MyAlloc<int>> w;
+    std::vector<int, MyAlloc<int>> w(100);
     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;
 }