EricWF created this revision. EricWF added reviewers: mclow.lists, vsk. EricWF added a subscriber: cfe-commits.
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. https://reviews.llvm.org/D28131 Files: include/__tree include/map
Index: include/map =================================================================== --- include/map +++ include/map @@ -533,7 +533,7 @@ using _VSTD::swap; swap(comp, __y.comp); } - + #if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY @@ -730,7 +730,7 @@ 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_;} @@ -895,7 +895,7 @@ #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 @@ -961,7 +961,7 @@ } #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 @@ -1297,72 +1297,17 @@ 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> @@ -1400,8 +1345,8 @@ _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) { @@ -1440,8 +1385,8 @@ _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"); @@ -1453,8 +1398,8 @@ 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"); @@ -1621,7 +1566,7 @@ #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 @@ -1688,7 +1633,7 @@ } #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 Index: include/__tree =================================================================== --- include/__tree +++ include/__tree @@ -1397,10 +1397,17 @@ __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,
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits