[libc++] std::less and cxa_demangle.cpp

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

> 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

Sorry, apparently this is my C background showing! It looks like
whereas C11 says the relational operators applied to pointers of
different array elements is undefined, C++11 is more forgiving and
says it's only unspecified.

Still, it seems like the standard imposes no total ordering constraint
on pointer comparisons. E.g., my understanding is this program to be
allowed to output 1:

    #include <iostream>
    int main() {
        int a, b;
        std::cout << ((&a >= &b) && (&b >= &a)) << std::endl;
    }

whereas this program must output 0:

    #include <iostream>
    #include <functional>
    int main() {
        std::greater_equal<int *> gteq;
        int a, b;
        std::cout << (gteq(&a, &b) && gteq(&b, &a)) << std::endl;
    }

I don't think this is purely theoretical either. For example, I think
it would be reasonable for a compiler to decide to optimize "p >= &q"
to just true (given "T *p;" and "T q;"), because the only defined
results are "true" and "unspecified". An optimization like this could
easily result in the first program above outputting "1" on standard
computers.

I think this would be very similar to the compiler optimizations
discussed in http://lwn.net/Articles/278137/.

I've given this some more thought. I've also reviewed what other std:: implementations are doing, and have done over the past 15 or so years.

When clang decides to break every implementation of std::less I'm aware of (and I'm not saying that won't happen), I'll revisit this issue. Until then, this direction is needlessly complicated, and not high enough on my priority list to devote more time to.

That being said, I do not want to discourage you. I very much value the contributions you have made to libc++ and libc++abi. Indeed I just scanned the CREDITS.TXT of both of those projects and was surprised to not find your name in either. I believe you are responsible for some bug fixes in both. Please consider contributing a patch to both of these files.

Thanks,
Howard