Debug mode for unordered_set. I believe this to be fairly complete for

unordered_set, however it is not complete yet for unordered_multiset,
unordered_map or unordered_multimap.  There has been a lot of work done
for these other three containers, however that work was done just to
keep all of the tests passing.

You can try this out with -D_LIBCPP_DEBUG2.  You will have to link to a
libc++.dylib that has been compiled with src/debug.cpp.  So far, vector
(but not vector<bool>), list, and unordered_set are treated.  I hope to
get the other three unordered containers up fairly quickly now that
unordered_set is done.

The flag _LIBCPP_DEBUG2 will eventually be changed to _LIBCPP_DEBUG, but
not today.  This is my second effort at getting debug mode going for
libc++, and I'm not quite yet ready to throw all of the work under the
first attempt away.

The basic design is that all of the debug information is kept in a
central database, instead of in the containers.  This has been done as
an attempt to have debug mode and non-debug mode be ABI compatible with
each other.  There are some circumstances where if you construct a
container in an environment without debug mode and pass it into debug
mode, the checking will get confused and let you know with a readable
error message.  Passing containers the other way: from debug mode out to
a non-debugging mode container should be 100% safe (at least that is the
goal).

git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@186991 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 160 insertions, 2 deletions

diff --git a/include/unordered_set b/include/unordered_set
index 119251dc3..8be36df6d 100644
--- a/include/unordered_set
+++ b/include/unordered_set
@@ -324,6 +324,8 @@ public:
     typedef _Alloc                                                     allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
+    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
+                  "Invalid allocator::value_type");
 
 private:
     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
@@ -344,7 +346,11 @@ public:
     _LIBCPP_INLINE_VISIBILITY
     unordered_set()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
-        {} // = default;
+        {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+            __get_db()->__insert_c(this);
+#endif
+        }
     explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
                            const key_equal& __eql = key_equal());
     unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
@@ -422,8 +428,18 @@ public:
             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
     template <class... _Args>
         _LIBCPP_INLINE_VISIBILITY
+#if _LIBCPP_DEBUG_LEVEL >= 2
+        iterator emplace_hint(const_iterator __p, _Args&&... __args)
+        {
+            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
+                "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
+                " referring to this unordered_set");
+            return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
+        }
+#else
         iterator emplace_hint(const_iterator, _Args&&... __args)
             {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
+#endif
 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, bool> insert(const value_type& __x)
@@ -434,12 +450,32 @@ public:
         {return __table_.__insert_unique(_VSTD::move(__x));}
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
     _LIBCPP_INLINE_VISIBILITY
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    iterator insert(const_iterator __p, const value_type& __x)
+        {
+            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
+                "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
+                " referring to this unordered_set");
+            return insert(__x).first;
+        }
+#else
     iterator insert(const_iterator, const value_type& __x)
         {return insert(__x).first;}
+#endif
 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
     _LIBCPP_INLINE_VISIBILITY
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    iterator insert(const_iterator __p, value_type&& __x)
+        {
+            _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
+                "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
+                " referring to this unordered_set");
+            return insert(_VSTD::move(__x)).first;
+        }
+#else
     iterator insert(const_iterator, value_type&& __x)
         {return insert(_VSTD::move(__x)).first;}
+#endif
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
     template <class _InputIterator>
         void insert(_InputIterator __first, _InputIterator __last);
@@ -515,6 +551,20 @@ public:
     void rehash(size_type __n) {__table_.rehash(__n);}
     _LIBCPP_INLINE_VISIBILITY
     void reserve(size_type __n) {__table_.reserve(__n);}
+
+#if _LIBCPP_DEBUG_LEVEL >= 2
+
+    bool __dereferenceable(const const_iterator* __i) const
+        {return __table_.__dereferenceable(__i);}
+    bool __decrementable(const const_iterator* __i) const
+        {return __table_.__decrementable(__i);}
+    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
+        {return __table_.__addable(__i, __n);}
+    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
+        {return __table_.__addable(__i, __n);}
+
+#endif  // _LIBCPP_DEBUG_LEVEL >= 2
+
 };
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
@@ -522,6 +572,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
 }
 
@@ -530,6 +583,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
 }
 
@@ -538,6 +594,9 @@ template <class _InputIterator>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         _InputIterator __first, _InputIterator __last)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     insert(__first, __last);
 }
 
@@ -548,6 +607,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__first, __last);
 }
@@ -559,6 +621,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__first, __last);
 }
@@ -569,6 +634,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const allocator_type& __a)
     : __table_(__a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
@@ -576,6 +644,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const unordered_set& __u)
     : __table_(__u.__table_)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
@@ -585,6 +656,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const unordered_set& __u, const allocator_type& __a)
     : __table_(__u.__table_, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
@@ -598,6 +672,10 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
     : __table_(_VSTD::move(__u.__table_))
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+    __get_db()->swap(this, &__u);
+#endif
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
@@ -605,12 +683,19 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         unordered_set&& __u, const allocator_type& __a)
     : __table_(_VSTD::move(__u.__table_), __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     if (__a != __u.get_allocator())
     {
         iterator __i = __u.begin();
         while (__u.size() != 0)
             __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
     }
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    else
+        __get_db()->swap(this, &__u);
+#endif
 }
 
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -621,6 +706,9 @@ template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         initializer_list<value_type> __il)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     insert(__il.begin(), __il.end());
 }
 
@@ -630,6 +718,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__il.begin(), __il.end());
 }
@@ -640,6 +731,9 @@ unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
         const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__il.begin(), __il.end());
 }
@@ -736,6 +830,8 @@ public:
     typedef _Alloc                                                     allocator_type;
     typedef value_type&                                                reference;
     typedef const value_type&                                          const_reference;
+    static_assert((is_same<value_type, typename allocator_type::value_type>::value),
+                  "Invalid allocator::value_type");
 
 private:
     typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
@@ -756,7 +852,11 @@ public:
     _LIBCPP_INLINE_VISIBILITY
     unordered_multiset()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
-        {} // = default
+        {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+            __get_db()->__insert_c(this);
+#endif
+        }
     explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
                                 const key_equal& __eql = key_equal());
     unordered_multiset(size_type __n, const hasher& __hf,
@@ -925,6 +1025,20 @@ public:
     void rehash(size_type __n) {__table_.rehash(__n);}
     _LIBCPP_INLINE_VISIBILITY
     void reserve(size_type __n) {__table_.reserve(__n);}
+
+#if _LIBCPP_DEBUG_LEVEL >= 2
+
+    bool __dereferenceable(const const_iterator* __i) const
+        {return __table_.__dereferenceable(__i);}
+    bool __decrementable(const const_iterator* __i) const
+        {return __table_.__decrementable(__i);}
+    bool __addable(const const_iterator* __i, ptrdiff_t __n) const
+        {return __table_.__addable(__i, __n);}
+    bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
+        {return __table_.__addable(__i, __n);}
+
+#endif  // _LIBCPP_DEBUG_LEVEL >= 2
+
 };
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
@@ -932,6 +1046,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         size_type __n, const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
 }
 
@@ -941,6 +1058,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
 }
 
@@ -949,6 +1069,9 @@ template <class _InputIterator>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         _InputIterator __first, _InputIterator __last)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     insert(__first, __last);
 }
 
@@ -959,6 +1082,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const hasher& __hf, const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__first, __last);
 }
@@ -970,6 +1096,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__first, __last);
 }
@@ -980,6 +1109,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const allocator_type& __a)
     : __table_(__a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
@@ -987,6 +1119,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const unordered_multiset& __u)
     : __table_(__u.__table_)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
@@ -996,6 +1131,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const unordered_multiset& __u, const allocator_type& __a)
     : __table_(__u.__table_, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__u.bucket_count());
     insert(__u.begin(), __u.end());
 }
@@ -1009,6 +1147,10 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
     _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
     : __table_(_VSTD::move(__u.__table_))
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+    __get_db()->swap(this, &__u);
+#endif
 }
 
 template <class _Value, class _Hash, class _Pred, class _Alloc>
@@ -1016,12 +1158,19 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         unordered_multiset&& __u, const allocator_type& __a)
     : __table_(_VSTD::move(__u.__table_), __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     if (__a != __u.get_allocator())
     {
         iterator __i = __u.begin();
         while (__u.size() != 0)
             __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
     }
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    else
+        __get_db()->swap(this, &__u);
+#endif
 }
 
 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
@@ -1032,6 +1181,9 @@ template <class _Value, class _Hash, class _Pred, class _Alloc>
 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         initializer_list<value_type> __il)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     insert(__il.begin(), __il.end());
 }
 
@@ -1041,6 +1193,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const key_equal& __eql)
     : __table_(__hf, __eql)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__il.begin(), __il.end());
 }
@@ -1051,6 +1206,9 @@ unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
         const key_equal& __eql, const allocator_type& __a)
     : __table_(__hf, __eql, __a)
 {
+#if _LIBCPP_DEBUG_LEVEL >= 2
+    __get_db()->__insert_c(this);
+#endif
     __table_.rehash(__n);
     insert(__il.begin(), __il.end());
 }