[cfe-dev] [libc++] std::less and cxa_demangle.cpp

[Matthew Dempsky]

[+cfe-dev, since I think this might interest some Clang developers/C++
standards sticklers]

On Mon, Jun 17, 2013 at 04:29:36PM -0400, Howard Hinnant wrote:
> On Jun 17, 2013, at 4:02 PM, Matthew Dempsky <matthew at dempsky.org> wrote:
> > 5. The C++ standard only defines relational operators for pointers to
> > elements of the same array, so arena::pointer_in_buffer() triggers
> > undefined behavior whenever it's used to test a pointer allocated by
> > malloc().  The best solution to this that I know of is to do the
> > comparisons on integers instead, and hope that the compiler does
> > implement an "unsurprising" pointer-to-integer mapping as encouraged
> > (but not required) by the standard.
> 
> It isn't undefined behavior if I use std::less ([comparisons]/p14),
> and I'm taking advantage of the fact that on all platforms being
> targeted, std::less<T*> is implemented with nothing more complicated
> than pointer comparison.

Hm, true, the standard does guarantee std::less imposes a total
ordering on pointers, though I don't believe that forbids orderings
that interleave pointers to distinct arrays.  E.g., it seems perfectly
standards conforming (but "surprising") for this program to output 1:

    #include <functional>
    #include <iostream>
    int main() {
        std::less<char *> lt;
        char x, y;
        std::cout << (lt(&x, &y) && lt(&y, &x + 1)) << std::endl;
    }

So I think this actually reveals a bug in libc++'s implementation of
std::less, etc.  They need partial specializations for pointer types
to properly guarantee a total ordering, otherwise the above code
triggers undefined behavior with libc++'s current definitions due to
the pointer comparisons between &y and &x (and between &y and &x + 1).


We should then also utilize std::less_equal in cxa_demangle.cpp
instead of directly comparing pointers.  If we wanted to go further,
in arena::allocate() we could assert that the pointer returned by
std::malloc() does not satisfy pointer_in_buffer().


Index: libcxx/include/__functional_base
===================================================================
--- libcxx/include/__functional_base	(revision 184100)
+++ libcxx/include/__functional_base	(working copy)
@@ -12,6 +12,7 @@
 #define _LIBCPP_FUNCTIONAL_BASE
 
 #include <__config>
+#include <cstdint>  // for uintptr_t
 #include <type_traits>
 #include <typeinfo>
 #include <exception>
@@ -57,6 +58,13 @@
         {return __x < __y;}
 };
 
+template <class _Tp>
+struct _LIBCPP_TYPE_VIS less<_Tp*> : binary_function<_Tp*, _Tp*, bool>
+{
+    _LIBCPP_INLINE_VISIBILITY bool operator()(_Tp* const& __x, _Tp* const& __y) const
+        {return reinterpret_cast<std::uintptr_t>(__x) < reinterpret_cast<std::uintptr_t>(__y);}
+};
+
 #ifdef _LIBCPP_HAS_NO_VARIADICS
 
 #include <__functional_base_03>
Index: libcxx/include/functional
===================================================================
--- libcxx/include/functional	(revision 184100)
+++ libcxx/include/functional	(working copy)
@@ -536,6 +536,13 @@
         {return __x > __y;}
 };
 
+template <class _Tp>
+struct _LIBCPP_TYPE_VIS greater<_Tp*> : binary_function<_Tp*, _Tp*, bool>
+{
+    _LIBCPP_INLINE_VISIBILITY bool operator()(_Tp* const& __x, _Tp* const& __y) const
+        {return reinterpret_cast<std::uintptr_t>(__x) > reinterpret_cast<std::uintptr_t>(__y);}
+};
+
 // less in <__functional_base>
 
 template <class _Tp>
@@ -546,6 +553,13 @@
 };
 
 template <class _Tp>
+struct _LIBCPP_TYPE_VIS greater_equal<_Tp*> : binary_function<_Tp*, _Tp*, bool>
+{
+    _LIBCPP_INLINE_VISIBILITY bool operator()(_Tp* const& __x, _Tp* const& __y) const
+        {return reinterpret_cast<std::uintptr_t>(__x) >= reinterpret_cast<std::uintptr_t>(__y);}
+};
+
+template <class _Tp>
 struct _LIBCPP_TYPE_VIS less_equal : binary_function<_Tp, _Tp, bool>
 {
     _LIBCPP_INLINE_VISIBILITY bool operator()(const _Tp& __x, const _Tp& __y) const
@@ -553,6 +567,13 @@
 };
 
 template <class _Tp>
+struct _LIBCPP_TYPE_VIS less_equal<_Tp*> : binary_function<_Tp*, _Tp*, bool>
+{
+    _LIBCPP_INLINE_VISIBILITY bool operator()(_Tp* const & __x, _Tp* const & __y) const
+        {return reinterpret_cast<std::uintptr_t>(__x) <= reinterpret_cast<std::uintptr_t>(__y);}
+};
+
+template <class _Tp>
 struct _LIBCPP_TYPE_VIS logical_and : binary_function<_Tp, _Tp, bool>
 {
     _LIBCPP_INLINE_VISIBILITY bool operator()(const _Tp& __x, const _Tp& __y) const
Index: libcxxabi/src/cxa_demangle.cpp
===================================================================
--- libcxxabi/src/cxa_demangle.cpp	(revision 184120)
+++ libcxxabi/src/cxa_demangle.cpp	(working copy)
@@ -14,6 +14,7 @@
 #include <algorithm>
 #include <string>
 #include <numeric>
+#include <functional>
 #include <cstdlib>
 #include <cstring>
 #include <cctype>
@@ -4222,7 +4223,11 @@
 
     bool
     pointer_in_buffer(char* p) noexcept
-        {return buf_ <= p && p <= buf_ + N;}
+    {
+        // We assume an "unsurprising" total order on pointers here.
+        std::less_equal<const char*> lteq;
+        return lteq(buf_, p) && lteq(p, buf_ + N);
+    }
 
 public:
     arena() noexcept : ptr_(buf_) {}