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

[Marshall Clow via Phabricator via cfe-commits]

mclow.lists added inline comments.



Comment at: include/__tree:1400
 __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.

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



https://reviews.llvm.org/D28131



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Eric Fiselier via Phabricator via cfe-commits]

EricWF accepted this revision.
EricWF added a reviewer: EricWF.
EricWF added a comment.
This revision is now accepted and ready to land.

In https://reviews.llvm.org/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.


https://reviews.llvm.org/D28131



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Vedant Kumar via Phabricator via cfe-commits]

vsk added a comment.

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?


https://reviews.llvm.org/D28131



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

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

[Eric Fiselier via Phabricator via cfe-commits]

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 
 _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 
-_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 __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 
-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 
@@ -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 =