[libc++] Add a few _LIBCPP_ASSERTs in __tree

[ldionne]

Summary

Several helper functions specify preconditions as comments, but we never
check them. I ran across a bug report (without a reproducer) in this code,
and I thought that having these assertions in place would make it easier
to troubleshoot.

[philnik]

I think I would remove the comments, since the preconditions are now documented in code.

libcxx/include/__tree

345–346

Could you also add that precondition?

[ldionne]

Address comments.

libcxx/include/__tree

345–346

I'll do that, but I'll add it as a _LIBCPP_DEBUG_ASSERT, since checking that invariant requires recursively visiting the whole tree AFAICT. _LIBCPP_ASSERT assertions should be cheap and should not impact complexity.

[philnik]

LGTM assuming CI passes.

libcxx/include/__tree

345–346

Sounds good.

libcxx/include/__tree

__tree_invariant(_NodePtr __root)
     // root must be black
     if (!__root->__is_black_)
         return false;
     // do normal node checks
     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
 {
+    _LIBCPP_ASSERT(__x != nullptr, "Root node shouldn't be null");
     while (__x->__left_ != nullptr)
         __x = __x->__left_;
     return __x;
 }
 
 // Returns:  pointer to the right-most node under __x.
-// Precondition:  __x != nullptr.
 template <class _NodePtr>
 inline _LIBCPP_INLINE_VISIBILITY
 _NodePtr
 __tree_max(_NodePtr __x) _NOEXCEPT
 {
+    _LIBCPP_ASSERT(__x != nullptr, "Root node shouldn't be null");
     while (__x->__right_ != nullptr)
         __x = __x->__right_;
     return __x;
 }
 
 // Returns:  pointer to the next in-order node after __x.
-// Precondition:  __x != nullptr.
 template <class _NodePtr>
 _NodePtr
 __tree_next(_NodePtr __x) _NOEXCEPT
 {
+    _LIBCPP_ASSERT(__x != nullptr, "node shouldn't be null");
     if (__x->__right_ != nullptr)
         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
 {
+    _LIBCPP_ASSERT(__x != nullptr, "node shouldn't be null");
     if (__x->__right_ != nullptr)
         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
 {
+    _LIBCPP_ASSERT(__x != nullptr, "node shouldn't be null");
     if (__x->__left_ != nullptr)
         return _VSTD::__tree_max(__x->__left_);
     _NodePtr __xx = static_cast<_NodePtr>(__x);
     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
 __tree_leaf(_NodePtr __x) _NOEXCEPT
 {
+    _LIBCPP_ASSERT(__x != nullptr, "node shouldn't be null");
     while (true)
     {
         if (__x->__left_ != nullptr)
         {
             __x = __x->__left_;
             continue;
         }
         if (__x->__right_ != nullptr)
         {
             __x = __x->__right_;
             continue;
         }
         break;
     }
     return __x;
 }
 
 // Effects:  Makes __x->__right_ the subtree root with __x as its left child
 //           while preserving in-order order.
-// Precondition:  __x->__right_ != nullptr
 template <class _NodePtr>
 void
 __tree_left_rotate(_NodePtr __x) _NOEXCEPT
 {
+    _LIBCPP_ASSERT(__x != nullptr, "node shouldn't be null");
+    _LIBCPP_ASSERT(__x->__right_ != nullptr, "node should have a right child");
     _NodePtr __y = __x->__right_;
     __x->__right_ = __y->__left_;
     if (__x->__right_ != nullptr)
         __x->__right_->__set_parent(__x);
     __y->__parent_ = __x->__parent_;
     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
 {
+    _LIBCPP_ASSERT(__x != nullptr, "node shouldn't be null");
+    _LIBCPP_ASSERT(__x->__left_ != nullptr, "node should have a left child");
     _NodePtr __y = __x->__left_;
     __x->__left_ = __y->__right_;
     if (__x->__left_ != nullptr)
         __x->__left_->__set_parent(__x);
     __y->__parent_ = __x->__parent_;
     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.
+// Precondition:  __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
 {
+    _LIBCPP_ASSERT(__root != nullptr, "Root of the tree shouldn't be null");
+    _LIBCPP_ASSERT(__x != nullptr, "Can't attach null node to a leaf");
     __x->__is_black_ = __x == __root;
     while (__x != __root && !__x->__parent_unsafe()->__is_black_)
     {
         // __x->__parent_ != __root because __x->__parent_->__is_black == false
         if (_VSTD::__tree_is_left_child(__x->__parent_unsafe()))
         {
             _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;
             if (__y != nullptr && !__y->__is_black_)
while (__x != __root && !__x->__parent_unsafe()->__is_black_)
                 __x = __x->__parent_unsafe();
                 __x->__is_black_ = false;
                 _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.
+// Precondition:  __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
 {
+    _LIBCPP_ASSERT(__root != nullptr, "Root node should not be null");
+    _LIBCPP_ASSERT(__z != nullptr, "The node to remove should not be null");
+    _LIBCPP_DEBUG_ASSERT(__tree_invariant(__root), "The tree invariants should hold");
     // __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 : _VSTD::__tree_next(__z);
     // __x is __y's possibly null single child
     _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;