[libcxx] Fix PR31402: map::__find_equal_key has undefined behavior.

[EricWF]

Summary

This patch fixes llvm.org/PR31402 by replacing map::__find_equal_key with __tree::__find_equal, which has already addressed the same undefined behavior.

Unfortunately I haven't been able to write a test case which causes the UBSAN diagnostic mentioned in the bug report. I can write tests which exercise the UB but for some reason they do not cause UBSAN to fail. Any help writing a test case would be appreciated.

[vsk]

LGTM. I'm not sure what to do for a test. Have you tried checking the IR for the affected object file in tablegen at '-O2 -fsanitize=undefined'? If there's an unconditional call to the ubsan handler, maybe the tablegen source could be used to find a small reproducer?

[EricWF]

In D28131#632516, @vsk wrote:

LGTM. I'm not sure what to do for a test. Have you tried checking the IR for the affected object file in tablegen at '-O2 -fsanitize=undefined'? If there's an unconditional call to the ubsan handler, maybe the tablegen source could be used to find a small reproducer?

Good idea. I'll have to try that, however I'll try to write a test post-commit.

[mclow.lists]

include/__tree

1400

Didn't we address this in http://wg21.link/LWG2542 ?

include/__tree

 private:
     __node_base_pointer&
         __find_leaf_low(__parent_pointer& __parent, const key_type& __v);
     __node_base_pointer&
         __find_leaf_high(__parent_pointer& __parent, const key_type& __v);
     __node_base_pointer&
         __find_leaf(const_iterator __hint,
                     __parent_pointer& __parent, const key_type& __v);
+    // FIXME: Make this function const qualified. Unfortunetly doing so
+    // breaks existing code which uses non-const callable comparators.
     template <class _Key>
     __node_base_pointer&
         __find_equal(__parent_pointer& __parent, const _Key& __v);
     template <class _Key>
+    _LIBCPP_INLINE_VISIBILITY __node_base_pointer&
+    __find_equal(__parent_pointer& __parent, const _Key& __v) const {
+      return const_cast<__tree*>(this)->__find_equal(__parent, __v);
+    }
+    template <class _Key>
     __node_base_pointer&
         __find_equal(const_iterator __hint, __parent_pointer& __parent,
                      __node_base_pointer& __dummy,
                      const _Key& __v);
 
 #ifndef _LIBCPP_CXX03_LANG
     template <class ..._Args>
     __node_holder __construct_node(_Args&& ...__args);

include/map

public:
     bool operator()(const _Key& __x, const _CP& __y) const
         {return comp(__x, __y.__cc.first);}
     void swap(__map_value_compare&__y)
         _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
     {
         using _VSTD::swap;
         swap(comp, __y.comp);
     }
-    
 #if _LIBCPP_STD_VER > 11
     template <typename _K2>
     _LIBCPP_INLINE_VISIBILITY
     typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
     operator () ( const _K2& __x, const _CP& __y ) const
         {return comp (__x, __y.__cc.first);}
 
     template <typename _K2>
__map_iterator operator--(int)
         __map_iterator __t(*this);
         --(*this);
         return __t;
     }
 
     friend _LIBCPP_INLINE_VISIBILITY
     bool operator==(const __map_iterator& __x, const __map_iterator& __y)
         {return __x.__i_ == __y.__i_;}
-    friend 
+    friend
     _LIBCPP_INLINE_VISIBILITY
     bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
         {return __x.__i_ != __y.__i_;}
 
     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
     template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
 };
_LIBCPP_INLINE_VISIBILITY
             const key_compare& __comp, const allocator_type& __a)
         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
         {
             insert(__f, __l);
         }
 
 #if _LIBCPP_STD_VER > 11
     template <class _InputIterator>
-    _LIBCPP_INLINE_VISIBILITY 
+    _LIBCPP_INLINE_VISIBILITY
     map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
         : map(__f, __l, key_compare(), __a) {}
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     map(const map& __m)
         : __tree_(__m.__tree_)
         {
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
     _LIBCPP_INLINE_VISIBILITY
     map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
         {
             insert(__il.begin(), __il.end());
         }
 
 #if _LIBCPP_STD_VER > 11
-    _LIBCPP_INLINE_VISIBILITY 
+    _LIBCPP_INLINE_VISIBILITY
     map(initializer_list<value_type> __il, const allocator_type& __a)
         : map(__il, key_compare(), __a) {}
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     map& operator=(initializer_list<value_type> __il)
         {
             __tree_.__assign_unique(__il.begin(), __il.end());
#if _LIBCPP_STD_VER > 11
     equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
 #endif
 
 private:
     typedef typename __base::__node                    __node;
     typedef typename __base::__node_allocator          __node_allocator;
     typedef typename __base::__node_pointer            __node_pointer;
     typedef typename __base::__node_base_pointer       __node_base_pointer;
+    typedef typename __base::__parent_pointer          __parent_pointer;
 
     typedef __map_node_destructor<__node_allocator> _Dp;
     typedef unique_ptr<__node, _Dp> __node_holder;
 
 #ifdef _LIBCPP_CXX03_LANG
     __node_holder __construct_node_with_key(const key_type& __k);
 #endif
-
-    __node_base_pointer const&
-    __find_equal_key(__node_base_pointer& __parent, const key_type& __k) const;
-
-    _LIBCPP_INLINE_VISIBILITY
-    __node_base_pointer&
-    __find_equal_key(__node_base_pointer& __parent, const key_type& __k) {
-        map const* __const_this = this;
-        return const_cast<__node_base_pointer&>(
-            __const_this->__find_equal_key(__parent, __k));
-    }
 };
 
 
-// Find __k
-// Set __parent to parent of null leaf and
-//    return reference to null leaf iv __k does not exist.
-// If __k exists, set parent to node of __k and return reference to node of __k
-template <class _Key, class _Tp, class _Compare, class _Allocator>
-typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer const&
-map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
-                                                       const key_type& __k) const
-{
-    __node_pointer __nd = __tree_.__root();
-    if (__nd != nullptr)
-    {
-        while (true)
-        {
-            if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
-            {
-                if (__nd->__left_ != nullptr)
-                    __nd = static_cast<__node_pointer>(__nd->__left_);
-                else
-                {
-                    __parent = static_cast<__node_base_pointer>(__nd);
-                    return __parent->__left_;
-                }
-            }
-            else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
-            {
-                if (__nd->__right_ != nullptr)
-                    __nd = static_cast<__node_pointer>(__nd->__right_);
-                else
-                {
-                    __parent = static_cast<__node_base_pointer>(__nd);
-                    return __parent->__right_;
-                }
-            }
-            else
-            {
-                __parent = static_cast<__node_base_pointer>(__nd);
-                return __parent;
-            }
-        }
-    }
-    __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
-    return __parent->__left_;
-}
-
 #ifndef _LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
     : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
 {
     if (__a != __m.get_allocator())
     {
map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
     __h.get_deleter().__second_constructed = true;
     return _LIBCPP_EXPLICIT_MOVE(__h);  // explicitly moved for C++03
 }
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
 {
-    __node_base_pointer __parent;
-    __node_base_pointer& __child = __find_equal_key(__parent, __k);
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
     __node_pointer __r = static_cast<__node_pointer>(__child);
     if (__child == nullptr)
     {
         __node_holder __h = __construct_node_with_key(__k);
         __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
         __r = __h.release();
     }
     return __r->__value_.__cc.second;

 }
 
 #endif  // !_LIBCPP_CXX03_LANG
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
 {
-    __node_base_pointer __parent;
-    __node_base_pointer& __child = __find_equal_key(__parent, __k);
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
 #ifndef _LIBCPP_NO_EXCEPTIONS
     if (__child == nullptr)
         throw out_of_range("map::at:  key not found");
 #endif  // _LIBCPP_NO_EXCEPTIONS
     return static_cast<__node_pointer>(__child)->__value_.__cc.second;
 }
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
 const _Tp&
 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
 {
-    __node_base_pointer __parent;
-    __node_base_pointer __child = __find_equal_key(__parent, __k);
+    __parent_pointer __parent;
+    __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
 #ifndef _LIBCPP_NO_EXCEPTIONS
     if (__child == nullptr)
         throw out_of_range("map::at:  key not found");
 #endif  // _LIBCPP_NO_EXCEPTIONS
     return static_cast<__node_pointer>(__child)->__value_.__cc.second;
 }
 
 
template <class _InputIterator>
             const key_compare& __comp, const allocator_type& __a)
         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
         {
             insert(__f, __l);
         }
 
 #if _LIBCPP_STD_VER > 11
     template <class _InputIterator>
-    _LIBCPP_INLINE_VISIBILITY 
+    _LIBCPP_INLINE_VISIBILITY
     multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
         : multimap(__f, __l, key_compare(), __a) {}
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     multimap(const multimap& __m)
         : __tree_(__m.__tree_.value_comp(),
           __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
     _LIBCPP_INLINE_VISIBILITY
     multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
         {
             insert(__il.begin(), __il.end());
         }
 
 #if _LIBCPP_STD_VER > 11
-    _LIBCPP_INLINE_VISIBILITY 
+    _LIBCPP_INLINE_VISIBILITY
     multimap(initializer_list<value_type> __il, const allocator_type& __a)
         : multimap(__il, key_compare(), __a) {}
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     multimap& operator=(initializer_list<value_type> __il)
         {
             __tree_.__assign_multi(__il.begin(), __il.end());