[libc++] Remove problematic ADL in container implementations.

[dlj]

Summary

Some container operations require ADL. For example, std::advance is
required to use specific operators, which will participate in ADL.

However, implementation details which rely on SFINAE should be careful not to
inadvertently invoke ADL. Otherwise, the SFINAE lookup will (incorrectly)
consider namespaces other than std::. This is particularly problematic with
incomplete types, since the set of associated namespaces for a class includes
the body of the class (which may contain inline friend function overloads). If a
type is incomplete, its body cannot be added to the set of associated
namespaces; this results in an error.

The changes in this patch mostly appear to be omissions. Several of the changes
are for SFINAE overloads with internal names (in some cases, there are other
uses which are already correctly qualified). In a few cases, the implementation
details of iterators are directly to avoid invoking ADL (this seems unfortunate;
but on balance, better than failing when type erasure is otherwise plausible).

[rsmith]

Looks good to me, but I'd like EricWF to also review.

include/deque

1167–1169

The other changes all look like obvious improvements to me. This one is a little more subtle, but if we want types like deque<Holder<Incomplete> *> to be destructible, I think we need to do something equivalent to this.

[EricWF]

include/__split_buffer

279

The changes adding _VSTD:: LGTM.

include/deque

1167–1169

That's really yucky! I'm OK with this, but I really don't like it.

Fundamentally this can't work, at least not generically. When the allocator produces a fancy pointer type, the operator lookups need to be performed using ADL.

In this specific case, we control the iterator type, but this isn't always true. for example like in __split_buffer, which uses the allocators pointer type as an iterator.

@dlj I updated your test case to demonstrate the fancy-pointer problem: https://gist.github.com/EricWF/b465fc475f55561ba972b6dd87e7e7ea

So I think we have a couple choices:

(1) Do nothing, since we can't universally support the behavior, so we shouldn't attempt to support any form of this behavior.
(2) Fix only the non-fancy pointer case (which is what this patch does).
(3) Attempt to fix *all* cases, including the fancy-pointer ones. This won't be possible, but perhaps certain containers can tolerate incomplete fancy pointers?

Personally I'm leaning towards (1), since we can't claim to support the use case, at least not universally. If we select (1) we should probably encode the restriction formally in standardese.

include/memory

1349–1351

Wouldn't the declval calls also need qualification?

[• Quuxplusone]

include/memory

1349–1351

(Sorry I'm jumping in before I know the full backstory here.) I would expect that the "declval" call doesn't need qualification because its argument-list is empty. ADL doesn't apply to template arguments AFAIK.
(Test case proving it to myself: https://wandbox.org/permlink/i0YarAfjOYKOhLFP )

Now, IMHO, __has_construct_test also doesn't need guarding against ADL, because it contains a double underscore and is thus firmly in the library's namespace. If the user has declared an ADL-findable entity my::__has_construct_test, they're already in undefined behavior land and you don't need to uglify libc++'s code just to coddle such users.

And, IMO, to the extent that ADL *does* work on the old code here, that's a feature, not a bug. As the implementor of some weird fancy pointer or iterator type, I might *like* having the power to hook into libc++'s customization points here. Of course I wouldn't try to hook into __has_construct_test, but __to_raw_pointer feels more likely. (At my current low level of understanding, that is.)

[EricWF]

include/memory

1349–1351

If the user has declared an ADL-findable entity my::__has_construct_test, they're already in undefined behavior land

The problem isn't that it will find a my::__has_construct_test, but that the simple act of looking requires completed types, otherwise an error is generated. Example

[dlj]

include/deque

1167–1169

So I think there are at least a couple of issues here, but first I want to get clarification on this point:

Do nothing, since we can't universally support the behavior, so we shouldn't attempt to support any form of this behavior.

To me, this sounds like it could be equivalent to the statement "someone might do a bad job of implementing type-erasure for fancy pointers, so we should never attempt to preserve type erasure of any pointers." Now, that statement seems tenuous at best (and a straw man on a slippery slope otherwise), so I'm guessing that's not quite what you meant. ;-)

That said, it does sort of make sense to ignore deque for now, so I'll drop it from the patch; but for other containers, I don't really see the argument.

As for #3: I'm able to make (most of) your gist pass for everything but deque... calls to _VSTD::__to_raw_pointer are enough to avoid ADL around operators, although a few other changes are needed, too. That probably makes sense to do as a follow-up.

As for deque in particular, I think there may just be some missing functions on the __deque_iterator, but it probably warrants a closer look before adding to the interface.

include/memory

1349–1351

Hmm, no I don't think so... declval<_Alloc> is a "declaration of a function at block scope" (because it's a template specialization), so it does not participate in ADL.

I believe the difference with e.g. __has_construct_test is that the other calls name a function template, which is not specialized (and so isn't a function declaration) until it wins the ADL.

I'm a little bit hazy on exactly the semantics, though, so Richard can correct me if I've gotten it substantially wrong. :-)

1349–1351

Double-underscore names don't actually change the lookup rules, so (as Eric points out) isn't really related to the issue I'm addressing here.

As for extension points... __to_raw_pointer is essentially a selector for the correct expression syntax to get the pointed-to node, somewhat analogous to how std::pointer_traits selects an "unwrapped" pointee type. (In this case, an "extension point" already exists: you can use a custom allocator with fancy pointers... have a look at Eric's comments in include/deque for a good example of how you might write one.)

[dlj]

• Remove deque from the test for now.

[dlj]

• Remove deque from the test for now.

[EricWF]

include/deque

1167–1169

To me, this sounds like it could be equivalent to the statement "someone might do a bad job of implementing type-erasure for fancy pointers, so we should never attempt to preserve type erasure of any pointers." Now, that statement seems tenuous at best (and a straw man on a slippery slope otherwise), so I'm guessing that's not quite what you meant. ;-)

I'm not sure it's even possible to type-erase fancy pointers in a way your suggesting. Fundamentally I think they need to carry around the pointee type. So this problem isn't so easily explained away or made the fault of the user. Or am I missing something?

The library is allowed, and in this case required, to perform operator lookup via ADL. full stop. That's how the STL is expected to interact with user types. Even after fixing the accidental ADL caused by __foo functions, we haven't and can't "fix" the rest. So now the question becomes "How far should libc++ go to avoid legal ADL lookup when it's possible"?

Whatever we decide, we are agreeing to "support" (or not support) a set of behavior, and I have a complex about claiming to "support" bizarre use cases like this. To support something we need to be able to (1) articulate exactly what behavior is supported, and (2) that the behavior won't regress.

I don't think we can provide guarantee (2) since future changes may require the use of ADL lookup in a way we can't avoid, for example in the same way that __split_buffer does. So that's a strike against the possibility of claiming "support".

One possibility is "The default constructor and destructor of containers X, Y, Z do not perform ADL lookup (Constructors A, B, C do not support this behavior) ". Admittedly it was easier than I thought to fix __hash_table and __tree, but __split_buffer is still a problem, which means that both deque and vector won't work.

Since we can't fix all of the containers, and the ones we can fix may need to break again in the future, I don't think we can arrive at a meaningful statement of support. Therefore, I think a good argument needs to be made as to why it's important to "fix" the particular cases we can.

[EricWF]

@dlj I went ahead and committed the fixes to std::allocator_traits in r313324, because I think we agree those are bugs, and I didn't want this discussion to hold up that fix. I hope you don't mind.

[dlj]

In D37538#871515, @EricWF wrote:

@dlj I went ahead and committed the fixes to std::allocator_traits in r313324, because I think we agree those are bugs, and I didn't want this discussion to hold up that fix. I hope you don't mind.

Nope, not a problem.

[rsmith]

dlj and I discussed this offline somewhat, and dlj made the interesting point that using ADL *at all* within the implementation of the standard library brings with it the risk that your implementation will not function correctly if a user-declared operator could be at least as good a match as your intended callee.

As an example, consider: https://godbolt.org/g/rgFTME -- as far as I can see, that code follows all the rules for safe and correct use of the C++ standard library. And yet it does not compile with either libc++ or libstdc++, because both internally use ADL to find the operator!= for vector::iterator within their implementation of vector::erase. Any ADL call seems likely to suffer from this problem; moreover, you can observe that vector<Foo>::iterator fails to even satisfy the input iterator requirements, because a != b is not a valid expression for iterators a and b.

I think the above example is actually demonstrating a bug in the standard: such user code is unreasonable and it's not sensible to expect the standard library to cope with it.

[• Quuxplusone]

Everything in this PR is obsolete and/or fixed at this point, except for the change to <deque>, which as Eric said, fixes the lower-hanging fruit but sadly can't "ADL-proof" it completely.
(Grepping for "ADL" in the git history of libcxx/include/ will turn up a lot of patches from me and from Logan Smith, on the subject of ADL-proofing.)
I suggest that this PR could be closed at this point.

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_raw_pointer(__begin_++));
+        __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(__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_raw_pointer(--__end_));
+        __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__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;

include/deque

#endif
     __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)
-        __alloc_traits::destroy(__a, _VSTD::addressof(*__i));
+    for (iterator __i = begin(), __e = end(); __i.__ptr_ != __e.__ptr_; __i.operator++())
+        __alloc_traits::destroy(__a, _VSTD::addressof(__i.operator*()));
     size() = 0;
     while (__map_.size() > 2)
     {
         __alloc_traits::deallocate(__a, __map_.front(), __block_size);
         __map_.pop_front();
     }
     switch (__map_.size())
     {
     case 1:

include/memory

 template <class _Alloc, class _Pointer, class ..._Args>
 false_type
 __has_construct_test(const _Alloc& __a, _Pointer&& __p, _Args&& ...__args);
 
 template <class _Alloc, class _Pointer, class ..._Args>
 struct __has_construct
     : integral_constant<bool,
         is_same<
-            decltype(__has_construct_test(declval<_Alloc>(),
+            decltype(_VSTD::__has_construct_test(declval<_Alloc>(),
                                                  declval<_Pointer>(),
                                                  declval<_Args>()...)),
             true_type>::value>
 {
 };
 
 template <class _Alloc, class _Pointer>
 auto
 __has_destroy_test(_Alloc&& __a, _Pointer&& __p)
     -> decltype(__a.destroy(__p), true_type());
 
 template <class _Alloc, class _Pointer>
 auto
 __has_destroy_test(const _Alloc& __a, _Pointer&& __p)
     -> false_type;
 
 template <class _Alloc, class _Pointer>
 struct __has_destroy
     : integral_constant<bool,
         is_same<
-            decltype(__has_destroy_test(declval<_Alloc>(),
+            decltype(_VSTD::__has_destroy_test(declval<_Alloc>(),
                                                declval<_Pointer>())),
             true_type>::value>
 {
 };
 
 template <class _Alloc>
 auto
 __has_max_size_test(_Alloc&& __a)
     -> decltype(__a.max_size(), true_type());
 
 template <class _Alloc>
 auto
 __has_max_size_test(const volatile _Alloc& __a)
     -> false_type;
 
 template <class _Alloc>
 struct __has_max_size
     : integral_constant<bool,
         is_same<
-            decltype(__has_max_size_test(declval<_Alloc&>())),
+            decltype(_VSTD::__has_max_size_test(declval<_Alloc&>())),
             true_type>::value>
 {
 };
 
 template <class _Alloc>
 auto
 __has_select_on_container_copy_construction_test(_Alloc&& __a)
     -> decltype(__a.select_on_container_copy_construction(), true_type());
 
 template <class _Alloc>
 auto
 __has_select_on_container_copy_construction_test(const volatile _Alloc& __a)
     -> false_type;
 
 template <class _Alloc>
 struct __has_select_on_container_copy_construction
     : integral_constant<bool,
         is_same<
-            decltype(__has_select_on_container_copy_construction_test(declval<_Alloc&>())),
+            decltype(_VSTD::__has_select_on_container_copy_construction_test(declval<_Alloc&>())),
             true_type>::value>
 {
 };
 
 #else  // _LIBCPP_CXX03_LANG
 
 #ifndef _LIBCPP_HAS_NO_VARIADICS
 
template <class _Tp, class _A0, class _A1, class _A2>
             {
                 ::new ((void*)__p) _Tp(__a0, __a1, __a2);
             }
 #endif  // _LIBCPP_HAS_NO_VARIADICS
 
     template <class _Tp>
         _LIBCPP_INLINE_VISIBILITY
         static void destroy(allocator_type& __a, _Tp* __p)
-            {__destroy(__has_destroy<allocator_type, _Tp*>(), __a, __p);}
+            {__destroy(_VSTD::__has_destroy<allocator_type, _Tp*>(), __a, __p);}
 
     _LIBCPP_INLINE_VISIBILITY
     static size_type max_size(const allocator_type& __a) _NOEXCEPT
         {return __max_size(__has_max_size<const allocator_type>(), __a);}
 
     _LIBCPP_INLINE_VISIBILITY
     static allocator_type
         select_on_container_copy_construction(const allocator_type& __a)

test/std/containers/containers.general/construct_destruct.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <array>
+#include <cassert>
+#include <forward_list>
+#include <list>
+#include <map>
+#include <queue>
+#include <set>
+#include <stack>
+#include <type_traits>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+// Holder<ns::T> is a do-nothing wrapper around a value of the given type.
+//
+// Since unqualified name lookup and operator overload lookup participate in
+// ADL, the dependent type ns::T contributes to the overload set considered by
+// ADL. In other words, ADL will consider all associated namespaces: this
+// includes not only N, but also any inline friend functions declared by ns::T.
+//
+// The purpose of this test is to ensure that simply constructing or destroying
+// a container does not invoke ADL which would be problematic for unknown types.
+// By using the type 'Holder<ns::T> *' as a container value, we can avoid the
+// obvious problems with unknown types: a pointer is trivial, and its size is
+// known. However, any ADL which includes ns::T as an associated namesapce will
+// fail.
+//
+// For example:
+//
+//   namespace ns {
+//     class T {
+//       // 13.5.7 [over.inc]:
+//       friend std::list<T *>::const_iterator
+//       operator++(std::list<T *>::const_iterator it) {
+//         return /* ... */;
+//       }
+//     };
+//   }
+//
+// The C++ standard stipulates that some functions, such as std::advance, use
+// overloaded operators (in C++14: 24.4.4 [iterator.operations]). The
+// implication is that calls to such a function are dependent on knowing the
+// overload set of operators in all associated namespaces; under ADL, this
+// includes the private friend function in the example above.
+//
+// However, for some operations, such as construction and destruction, no such
+// ADL is required. This can be important, for example, when using the Pimpl
+// pattern:
+//
+//   // Defined in a header file:
+//   class InterfaceList {
+//     // Defined in a .cpp file:
+//     class Impl;
+//     vector<Impl*> impls;
+//   public:
+//     ~InterfaceList();
+//   };
+//
+template <class T>
+class Holder { T value; };
+
+namespace ns { class Fwd; }
+
+// TestSequencePtr and TestMappingPtr ensure that a given container type can be
+// default-constructed and destroyed with an incomplete value pointer type.
+template <template <class...> class Container>
+void TestSequencePtr() {
+  using X = Container<Holder<ns::Fwd>*>;
+  {
+    X u;
+    assert(u.empty());
+  }
+  {
+    auto u = X();
+    assert(u.empty());
+  }
+}
+
+template <template <class...> class Container>
+void TestMappingPtr() {
+  {
+    using X = Container<int, Holder<ns::Fwd>*>;
+    X u1;
+    assert(u1.empty());
+    auto u2 = X();
+    assert(u2.empty());
+  }
+  {
+    using X = Container<Holder<ns::Fwd>*, int>;
+    X u1;
+    assert(u1.empty());
+    auto u2 = X();
+    assert(u2.empty());
+  }
+}
+
+int main()
+{
+  // Sequence containers:
+  {
+    std::array<Holder<ns::Fwd>*, 1> a;
+    (void)a;
+  }
+  TestSequencePtr<std::forward_list>();
+  TestSequencePtr<std::list>();
+  TestSequencePtr<std::vector>();
+
+  // Associative containers, non-mapping:
+  TestSequencePtr<std::set>();
+  TestSequencePtr<std::unordered_set>();
+
+  // Associative containers, mapping:
+  TestMappingPtr<std::map>();
+  TestMappingPtr<std::unordered_map>();
+
+  // Container adapters:
+  TestSequencePtr<std::queue>();
+  TestSequencePtr<std::stack>();
+}