[libc++] Split various components out of <memory>

[• Quuxplusone]

Here are the dependency graphs before and after this patch.
At the introduction of the new grapher script, pre- D99309: https://i.imgur.com/wIGKMXG.png (10031 x 1602 pixels, 141 nodes)
Main, pre-this-patch: https://i.imgur.com/CDUSXcr.png (10360 x 1845 pixels, 141 nodes)
After this patch: https://i.imgur.com/7mll7PC.png (11243 x 2636 pixels, 150 nodes)

libcxx/include/__memory/gc.h

10–11 ↗

(On Diff #336856)

I suggest (well, I continue to suggest that you not do any of this refactoring, but...) that you name this file pointer_safety.h, since gc.h is (A) terse and (B) obscure. pointer_safety.h would have the benefit of matching a name in the standard (so it's greppable), and also connoting how arcane this stuff is meant to be. gc.h sounds like it might be talking about shared_ptr or something.

libcxx/include/__memory/uninitialized.h

10–11 ↗

(On Diff #336856)

uninitialized_algorithms.h

libcxx/include/__memory/unique_ptr.h

16 ↗

(On Diff #336856)

This is a very surprising edge, since ultimately we want to remove auto_ptr altogether. Can you try to remove it? (At the very least, comment why it's here.)

[ldionne]

Fix failing tests, rename headers as suggested by reviewers.

[ldionne]

In D100318#2683513, @Quuxplusone wrote:

Here are the dependency graphs before and after this patch.
At the introduction of the new grapher script, pre- D99309: https://i.imgur.com/wIGKMXG.png (10031 x 1602 pixels, 141 nodes)
Main, pre-this-patch: https://i.imgur.com/CDUSXcr.png (10360 x 1845 pixels, 141 nodes)
After this patch: https://i.imgur.com/7mll7PC.png (11243 x 2636 pixels, 150 nodes)

I disagree with the way you calculate complexity. Yes, the graph has more nodes and edges. But each file now contains a set of logically-related things, and is much smaller. As a human, I spend time reading files with code in it, not looking at graphs. The graph is useful as a tool, but it's not measure of success in itself.

libcxx/include/__memory/gc.h

10–11 ↗

(On Diff #336856)

I agree with pointer_safety.h, that's a much better name. Thanks.

libcxx/include/__memory/uninitialized.h

10–11 ↗

(On Diff #336856)

Better indeed, thanks.

libcxx/include/__memory/unique_ptr.h

16 ↗

(On Diff #336856)

After the move is done, I will go back and make this dependent on the standard version and whether auto_ptr is force-enabled. I didn't want to change any code as part of these commits.

[• Quuxplusone]

I disagree with the way you calculate complexity. Yes, the graph has more nodes and edges. But each file now contains a set of logically-related things, and is much smaller. As a human, I spend time reading files with code in it, not looking at graphs.

Me too! ;) When I'm reading that code, though, I tend to stumble over two measures of complexity:
(1) How hard do I have to look to find the source file that actually contains the thing I'm working on? (Once the right file is open, I can jump to the right line quickly; but I don't use an IDE that can jump me to the right file quickly.)
(2) How tightly entangled is this source file with other source files? (How many other files do I need to read in order to fully understand the code in this file?)
These two measures of complexity map directly onto "number of nodes in the graph" and "number of edges in the graph."
I do think minimizing edges is generally more important than minimizing nodes (and of course it's most important to keep the number of cycles at 0). Minimizing the diameter of the graph (the number of levels of abstraction you have to dig through to work on the code) is also relevant, if maybe less important than the other measures listed here.

libcxx/include/__memory/unique_ptr.h

16 ↗

(On Diff #336856)

Ah, I get it now — the culprit is literally the constructor unique_ptr(auto_ptr<Y>&&), which is removed only in C++20. Okay (although I'd still prefer to see the code comment // std::auto_ptr for clarity).

[ldionne]

Workaround failures on Clang 10

[ldionne]

@DavidSpickett Would it be possible to upgrade the ARM bots to Clang 11? They are currently running Clang 10, which is still supported for now, however it is missing 05eedf1f5b44, which makes some tests fail: https://buildkite.com/llvm-project/libcxx-ci/builds/2462#d220f5f2-25ed-498b-88e3-0013c0b5e3a1.

[DavidSpickett]

Arm bots are now on clang 11.1.0.

[ldionne]

In D100318#2685374, @DavidSpickett wrote:

Arm bots are now on clang 11.1.0.

Thanks for the prompt reply!

libcxx/include/CMakeLists.txt

set(files
   __functional_base_03
   __hash_table
   __libcpp_version
   __locale
   __memory/allocator.h
   __memory/allocator_traits.h
   __memory/auto_ptr.h
   __memory/base.h
+  __memory/compressed_pair.h
   __memory/pointer_traits.h
   __memory/temporary_buffer.h
   __memory/utilities.h
   __mutex_base
   __node_handle
   __nullptr
   __split_buffer
   __sso_allocator

libcxx/include/__memory/compressed_pair.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___MEMORY_COMPRESSED_PAIR_H
+#define _LIBCPP___MEMORY_COMPRESSED_PAIR_H
+
+#include <__config>
+#include <tuple> // needed in c++03 for some constructors
+#include <type_traits>
+#include <utility>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// Tag used to default initialize one or both of the pair's elements.
+struct __default_init_tag {};
+struct __value_init_tag {};
+
+template <class _Tp, int _Idx,
+          bool _CanBeEmptyBase =
+              is_empty<_Tp>::value && !__libcpp_is_final<_Tp>::value>
+struct __compressed_pair_elem {
+  typedef _Tp _ParamT;
+  typedef _Tp& reference;
+  typedef const _Tp& const_reference;
+
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+  __compressed_pair_elem(__default_init_tag) {}
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+  __compressed_pair_elem(__value_init_tag) : __value_() {}
+
+  template <class _Up, class = typename enable_if<
+      !is_same<__compressed_pair_elem, typename decay<_Up>::type>::value
+  >::type>
+  _LIBCPP_INLINE_VISIBILITY
+  _LIBCPP_CONSTEXPR explicit
+  __compressed_pair_elem(_Up&& __u)
+      : __value_(_VSTD::forward<_Up>(__u))
+    {
+    }
+
+
+#ifndef _LIBCPP_CXX03_LANG
+  template <class... _Args, size_t... _Indexes>
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
+  __compressed_pair_elem(piecewise_construct_t, tuple<_Args...> __args,
+                         __tuple_indices<_Indexes...>)
+      : __value_(_VSTD::forward<_Args>(_VSTD::get<_Indexes>(__args))...) {}
+#endif
+
+
+  _LIBCPP_INLINE_VISIBILITY reference __get() _NOEXCEPT { return __value_; }
+  _LIBCPP_INLINE_VISIBILITY
+  const_reference __get() const _NOEXCEPT { return __value_; }
+
+private:
+  _Tp __value_;
+};
+
+template <class _Tp, int _Idx>
+struct __compressed_pair_elem<_Tp, _Idx, true> : private _Tp {
+  typedef _Tp _ParamT;
+  typedef _Tp& reference;
+  typedef const _Tp& const_reference;
+  typedef _Tp __value_type;
+
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR __compressed_pair_elem() = default;
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+  __compressed_pair_elem(__default_init_tag) {}
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+  __compressed_pair_elem(__value_init_tag) : __value_type() {}
+
+  template <class _Up, class = typename enable_if<
+        !is_same<__compressed_pair_elem, typename decay<_Up>::type>::value
+  >::type>
+  _LIBCPP_INLINE_VISIBILITY
+  _LIBCPP_CONSTEXPR explicit
+  __compressed_pair_elem(_Up&& __u)
+      : __value_type(_VSTD::forward<_Up>(__u))
+  {}
+
+#ifndef _LIBCPP_CXX03_LANG
+  template <class... _Args, size_t... _Indexes>
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
+  __compressed_pair_elem(piecewise_construct_t, tuple<_Args...> __args,
+                         __tuple_indices<_Indexes...>)
+      : __value_type(_VSTD::forward<_Args>(_VSTD::get<_Indexes>(__args))...) {}
+#endif
+
+  _LIBCPP_INLINE_VISIBILITY reference __get() _NOEXCEPT { return *this; }
+  _LIBCPP_INLINE_VISIBILITY
+  const_reference __get() const _NOEXCEPT { return *this; }
+};
+
+template <class _T1, class _T2>
+class __compressed_pair : private __compressed_pair_elem<_T1, 0>,
+                          private __compressed_pair_elem<_T2, 1> {
+public:
+  // NOTE: This static assert should never fire because __compressed_pair
+  // is *almost never* used in a scenario where it's possible for T1 == T2.
+  // (The exception is std::function where it is possible that the function
+  //  object and the allocator have the same type).
+  static_assert((!is_same<_T1, _T2>::value),
+    "__compressed_pair cannot be instantiated when T1 and T2 are the same type; "
+    "The current implementation is NOT ABI-compatible with the previous "
+    "implementation for this configuration");
+
+    typedef _LIBCPP_NODEBUG_TYPE __compressed_pair_elem<_T1, 0> _Base1;
+    typedef _LIBCPP_NODEBUG_TYPE __compressed_pair_elem<_T2, 1> _Base2;
+
+    template <bool _Dummy = true,
+      class = typename enable_if<
+          __dependent_type<is_default_constructible<_T1>, _Dummy>::value &&
+          __dependent_type<is_default_constructible<_T2>, _Dummy>::value
+      >::type
+  >
+  _LIBCPP_INLINE_VISIBILITY
+  _LIBCPP_CONSTEXPR __compressed_pair() : _Base1(__value_init_tag()), _Base2(__value_init_tag()) {}
+
+  template <class _U1, class _U2>
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+  __compressed_pair(_U1&& __t1, _U2&& __t2)
+      : _Base1(_VSTD::forward<_U1>(__t1)), _Base2(_VSTD::forward<_U2>(__t2)) {}
+
+#ifndef _LIBCPP_CXX03_LANG
+  template <class... _Args1, class... _Args2>
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
+  __compressed_pair(piecewise_construct_t __pc, tuple<_Args1...> __first_args,
+                    tuple<_Args2...> __second_args)
+      : _Base1(__pc, _VSTD::move(__first_args),
+               typename __make_tuple_indices<sizeof...(_Args1)>::type()),
+        _Base2(__pc, _VSTD::move(__second_args),
+               typename __make_tuple_indices<sizeof...(_Args2)>::type()) {}
+#endif
+
+  _LIBCPP_INLINE_VISIBILITY
+  typename _Base1::reference first() _NOEXCEPT {
+    return static_cast<_Base1&>(*this).__get();
+  }
+
+  _LIBCPP_INLINE_VISIBILITY
+  typename _Base1::const_reference first() const _NOEXCEPT {
+    return static_cast<_Base1 const&>(*this).__get();
+  }
+
+  _LIBCPP_INLINE_VISIBILITY
+  typename _Base2::reference second() _NOEXCEPT {
+    return static_cast<_Base2&>(*this).__get();
+  }
+
+  _LIBCPP_INLINE_VISIBILITY
+  typename _Base2::const_reference second() const _NOEXCEPT {
+    return static_cast<_Base2 const&>(*this).__get();
+  }
+
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+  static _Base1* __get_first_base(__compressed_pair* __pair) _NOEXCEPT {
+    return static_cast<_Base1*>(__pair);
+  }
+  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
+  static _Base2* __get_second_base(__compressed_pair* __pair) _NOEXCEPT {
+    return static_cast<_Base2*>(__pair);
+  }
+
+  _LIBCPP_INLINE_VISIBILITY
+  void swap(__compressed_pair& __x)
+    _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
+               __is_nothrow_swappable<_T2>::value)
+  {
+    using _VSTD::swap;
+    swap(first(), __x.first());
+    swap(second(), __x.second());
+  }
+};
+
+template <class _T1, class _T2>
+inline _LIBCPP_INLINE_VISIBILITY
+void swap(__compressed_pair<_T1, _T2>& __x, __compressed_pair<_T1, _T2>& __y)
+    _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
+               __is_nothrow_swappable<_T2>::value) {
+  __x.swap(__y);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif  // _LIBCPP___MEMORY_COMPRESSED_PAIR_H

libcxx/include/memory

 #include <iosfwd>
 #include <tuple>
 #include <stdexcept>
 #include <cstring>
 #include <__memory/allocator.h>
 #include <__memory/allocator_traits.h>
 #include <__memory/auto_ptr.h>
 #include <__memory/base.h>
+#include <__memory/compressed_pair.h>
 #include <__memory/pointer_traits.h>
 #include <__memory/temporary_buffer.h>
 #include <__memory/utilities.h>
 #if !defined(_LIBCPP_HAS_NO_ATOMIC_HEADER)
 #  include <atomic>
 #endif
 #include <version>
 
#endif
     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator& operator++() {++__x_; return *this;}
     _LIBCPP_INLINE_VISIBILITY raw_storage_iterator  operator++(int)
         {raw_storage_iterator __t(*this); ++__x_; return __t;}
 #if _LIBCPP_STD_VER >= 14
     _LIBCPP_INLINE_VISIBILITY _OutputIterator base() const { return __x_; }
 #endif
 };
 
-// Tag used to default initialize one or both of the pair's elements.
-struct __default_init_tag {};
-struct __value_init_tag {};
-
-template <class _Tp, int _Idx,
-          bool _CanBeEmptyBase =
-              is_empty<_Tp>::value && !__libcpp_is_final<_Tp>::value>
-struct __compressed_pair_elem {
-  typedef _Tp _ParamT;
-  typedef _Tp& reference;
-  typedef const _Tp& const_reference;
-
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-  __compressed_pair_elem(__default_init_tag) {}
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-  __compressed_pair_elem(__value_init_tag) : __value_() {}
-
-  template <class _Up, class = typename enable_if<
-      !is_same<__compressed_pair_elem, typename decay<_Up>::type>::value
-  >::type>
-  _LIBCPP_INLINE_VISIBILITY
-  _LIBCPP_CONSTEXPR explicit
-  __compressed_pair_elem(_Up&& __u)
-      : __value_(_VSTD::forward<_Up>(__u))
-    {
-    }
-
-
-#ifndef _LIBCPP_CXX03_LANG
-  template <class... _Args, size_t... _Indexes>
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
-  __compressed_pair_elem(piecewise_construct_t, tuple<_Args...> __args,
-                         __tuple_indices<_Indexes...>)
-      : __value_(_VSTD::forward<_Args>(_VSTD::get<_Indexes>(__args))...) {}
-#endif
-
-
-  _LIBCPP_INLINE_VISIBILITY reference __get() _NOEXCEPT { return __value_; }
-  _LIBCPP_INLINE_VISIBILITY
-  const_reference __get() const _NOEXCEPT { return __value_; }
-
-private:
-  _Tp __value_;
-};
-
-template <class _Tp, int _Idx>
-struct __compressed_pair_elem<_Tp, _Idx, true> : private _Tp {
-  typedef _Tp _ParamT;
-  typedef _Tp& reference;
-  typedef const _Tp& const_reference;
-  typedef _Tp __value_type;
-
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR __compressed_pair_elem() = default;
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-  __compressed_pair_elem(__default_init_tag) {}
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-  __compressed_pair_elem(__value_init_tag) : __value_type() {}
-
-  template <class _Up, class = typename enable_if<
-        !is_same<__compressed_pair_elem, typename decay<_Up>::type>::value
-  >::type>
-  _LIBCPP_INLINE_VISIBILITY
-  _LIBCPP_CONSTEXPR explicit
-  __compressed_pair_elem(_Up&& __u)
-      : __value_type(_VSTD::forward<_Up>(__u))
-  {}
-
-#ifndef _LIBCPP_CXX03_LANG
-  template <class... _Args, size_t... _Indexes>
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
-  __compressed_pair_elem(piecewise_construct_t, tuple<_Args...> __args,
-                         __tuple_indices<_Indexes...>)
-      : __value_type(_VSTD::forward<_Args>(_VSTD::get<_Indexes>(__args))...) {}
-#endif
-
-  _LIBCPP_INLINE_VISIBILITY reference __get() _NOEXCEPT { return *this; }
-  _LIBCPP_INLINE_VISIBILITY
-  const_reference __get() const _NOEXCEPT { return *this; }
-};
-
-template <class _T1, class _T2>
-class __compressed_pair : private __compressed_pair_elem<_T1, 0>,
-                          private __compressed_pair_elem<_T2, 1> {
-public:
-  // NOTE: This static assert should never fire because __compressed_pair
-  // is *almost never* used in a scenario where it's possible for T1 == T2.
-  // (The exception is std::function where it is possible that the function
-  //  object and the allocator have the same type).
-  static_assert((!is_same<_T1, _T2>::value),
-    "__compressed_pair cannot be instantiated when T1 and T2 are the same type; "
-    "The current implementation is NOT ABI-compatible with the previous "
-    "implementation for this configuration");
-
-    typedef _LIBCPP_NODEBUG_TYPE __compressed_pair_elem<_T1, 0> _Base1;
-    typedef _LIBCPP_NODEBUG_TYPE __compressed_pair_elem<_T2, 1> _Base2;
-
-    template <bool _Dummy = true,
-      class = typename enable_if<
-          __dependent_type<is_default_constructible<_T1>, _Dummy>::value &&
-          __dependent_type<is_default_constructible<_T2>, _Dummy>::value
-      >::type
-  >
-  _LIBCPP_INLINE_VISIBILITY
-  _LIBCPP_CONSTEXPR __compressed_pair() : _Base1(__value_init_tag()), _Base2(__value_init_tag()) {}
-
-  template <class _U1, class _U2>
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-  __compressed_pair(_U1&& __t1, _U2&& __t2)
-      : _Base1(_VSTD::forward<_U1>(__t1)), _Base2(_VSTD::forward<_U2>(__t2)) {}
-
-#ifndef _LIBCPP_CXX03_LANG
-  template <class... _Args1, class... _Args2>
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
-  __compressed_pair(piecewise_construct_t __pc, tuple<_Args1...> __first_args,
-                    tuple<_Args2...> __second_args)
-      : _Base1(__pc, _VSTD::move(__first_args),
-               typename __make_tuple_indices<sizeof...(_Args1)>::type()),
-        _Base2(__pc, _VSTD::move(__second_args),
-               typename __make_tuple_indices<sizeof...(_Args2)>::type()) {}
-#endif
-
-  _LIBCPP_INLINE_VISIBILITY
-  typename _Base1::reference first() _NOEXCEPT {
-    return static_cast<_Base1&>(*this).__get();
-  }
-
-  _LIBCPP_INLINE_VISIBILITY
-  typename _Base1::const_reference first() const _NOEXCEPT {
-    return static_cast<_Base1 const&>(*this).__get();
-  }
-
-  _LIBCPP_INLINE_VISIBILITY
-  typename _Base2::reference second() _NOEXCEPT {
-    return static_cast<_Base2&>(*this).__get();
-  }
-
-  _LIBCPP_INLINE_VISIBILITY
-  typename _Base2::const_reference second() const _NOEXCEPT {
-    return static_cast<_Base2 const&>(*this).__get();
-  }
-
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-  static _Base1* __get_first_base(__compressed_pair* __pair) _NOEXCEPT {
-    return static_cast<_Base1*>(__pair);
-  }
-  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR
-  static _Base2* __get_second_base(__compressed_pair* __pair) _NOEXCEPT {
-    return static_cast<_Base2*>(__pair);
-  }
-
-  _LIBCPP_INLINE_VISIBILITY
-  void swap(__compressed_pair& __x)
-    _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
-               __is_nothrow_swappable<_T2>::value)
-  {
-    using _VSTD::swap;
-    swap(first(), __x.first());
-    swap(second(), __x.second());
-  }
-};
-
-template <class _T1, class _T2>
-inline _LIBCPP_INLINE_VISIBILITY
-void swap(__compressed_pair<_T1, _T2>& __x, __compressed_pair<_T1, _T2>& __y)
-    _NOEXCEPT_(__is_nothrow_swappable<_T1>::value &&
-               __is_nothrow_swappable<_T2>::value) {
-  __x.swap(__y);
-}
-
 // default_delete
 
 template <class _Tp>
 struct _LIBCPP_TEMPLATE_VIS default_delete {
     static_assert(!is_function<_Tp>::value,
                   "default_delete cannot be instantiated for function types");
 #ifndef _LIBCPP_CXX03_LANG
   _LIBCPP_INLINE_VISIBILITY constexpr default_delete() _NOEXCEPT = default;