[libc++] Introduce __is_pointer_in_range

[philnik]

Summary

This checks whether a pointer is within a range, even during constant evaluation. This allows running optimized code paths during constant evaluation, instead of falling back to the general-purpose implementation all the time. This is also a central place for comparing unrelated pointers, which is technically UB.

[philnik]

libcxx/include/__utility/is_pointer_in_range.h

48

Am I correct here that it's impossible to get aliasing pointers during constant evaluation that are not comparable normally?

[philnik]

Generate files

[Mordante]

Note I fixed a typo in the commit message.

Thanks for working on this, I think it's useful to have, but it requires a bit more work.

libcxx/include/CMakeLists.txt

833

I miss the module map entry.

libcxx/include/__config

1105

Can you add a link to the documentation of this attribute?

libcxx/include/__utility/is_pointer_in_range.h

34

Or are empty ranges prohibited?

Based on the code below it is indeed prohibited. If that is intended I really dislike the name of the function.
The function does not test whether the pointer is in the range, but whether the pointer is in the range and can be dereferenced.Maybe __is_pointer_in_dereferencable_range would be a better name.

42

I think we should document this is technically UB, but all supported compilers accept this.

51

Is this really safe on all supported platforms?

libcxx/test/libcxx/utilities/is_pointer_in_range.pass.cpp

38

I really like to see more test. This only compares pointers where _Tp and _Up are the same type. Since the code tests different pointer types I really would like to see tests for volatile pointers against non-volatile pointers. Test with object pointers against function pointers, data member pointer, member function pointers.

[philnik]

Address comments

libcxx/include/__config

1105

I don't really see the point here. All the clang attributes are described at https://clang.llvm.org/docs/AttributeReference.html. Having a link to the same page for every attribute we use seems redundant. We can add a link at the top of the file if you think that's useful.

libcxx/include/__utility/is_pointer_in_range.h

34

No, empty ranges are not prohibited. This just checks that it is valid to compare the two pointers. It doesn't actually check that __begin is smaller than __end. IOW __builtin_constant_p(ptr < ptr) is always true, since the expression is known to result in false (https://godbolt.org/z/EMfW7179r).

AFAIK a range is normally [begin, end), i.e. excluding the end pointer. Returning true for the end pointer would be inconsistent with any other function taking a range.

51

I think it should be. Do you have anything specific in mind?

libcxx/test/libcxx/utilities/is_pointer_in_range.pass.cpp

38

I don't think it makes sense to call __is_pointer_in_range with function pointers or member pointers, so I added static_asserts instead.

[Mordante]

libcxx/include/__config

1105

I think it would help readers to quickly find the documentation, instead of remember where the clang attributes are exactly available.

libcxx/include/__utility/is_pointer_in_range.h

34

Yes a range is [begin, end), and an empty for an empty range begin == end.
I'm happy with the fix.

51

You can compare integral types with different sizes, but you can't just cast pointers from one to another.

Concretely I wonder whether we violate alignment rules.
For example`_Tp == int`, _Up = signed char and __ptr = 0xFFF01. This will create a const int* at an odd numbered address. (This is valid on x86, but that platform has less alignment restrictions than other platforms.)

[philnik]

Address comments

libcxx/include/__utility/is_pointer_in_range.h

51

Yeah, I'm not sure. Casting all pointers to char should make it safe.

[ldionne]

libcxx/include/module.modulemap.in

1743–1744

By the way, I think this is highly relevant to the existing issue that std::less is supposed to be blessed to compare unrelated pointers, but we currently don't do anything special with it. I think we should have a single solution for both of those issues.

libcxx/include/string

1952

The new code is not equivalent to the old one. The old code does data() <= __p && __p <= data() + size(), the new code looks for data() <= __p && __p < data() + size() (notice <= vs <).

1957

I would handle the !is-less-than-comparable case here instead of in __is_pointer_in_range. __is_pointer_in_range is more general purpose, and it doesn't make sense for it to return false when trying to compare unrelated pointers -- instead it should be a compiler error to do so.

In other words, __is_pointer_in_range should be equivalent to first <= p < last, except blessed by the compiler -- nothing less, nothing more. If that expression would not be well formed, then __is_pointer_in_range should also not be well formed, and we shouldn't try to give it a value.

[philnik]

Address comments

[philnik]

Try to fix CI

[ldionne]

LGTM, but this needs to be rebased on the patch with the __less refactoring before going in.

libcxx/include/__utility/is_pointer_in_range.h

42–43

That way, we technically don't have to change anything but std::less in the future.

We could also use __less instead here, and make __less be the canonical place where we bless comparison of unrelated pointers. We would then also use __less from std::less. Let's do that part as a separate patch, it's actually a nice cleanup.

libcxx/include/string

1958

Here and below.

1971

For symmetry with above?

libcxx/test/libcxx/utilities/is_pointer_in_range.pass.cpp

35

Could we move this test to test_cv_quals?

[philnik]

Address comments

[philnik]

Rebased

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

libcxx/.clang-format

AttributeMacros: ['_LIBCPP_HIDE_FROM_ABI',
                   '_LIBCPP_EXCEPTION_ABI',
                   '_LIBCPP_ENUM_VIS',
                   '_LIBCPP_EXTERN_TEMPLATE_TYPE_VIS',
                   '_LIBCPP_INTERNAL_LINKAGE',
                   '_LIBCPP_EXCLUDE_FROM_EXPLICIT_INSTANTIATION',
                   '_LIBCPP_HIDE_FROM_ABI_AFTER_V1',
                   '_LIBCPP_INLINE_VISIBILITY',
                   '_LIBCPP_NOALIAS',
+                  '_LIBCPP_NO_SANITIZE',
                   '_LIBCPP_USING_IF_EXISTS',
                   '_LIBCPP_DEPRECATED',
                   '_LIBCPP_DEPRECATED_IN_CXX11',
                   '_LIBCPP_DEPRECATED_IN_CXX14',
                   '_LIBCPP_DEPRECATED_IN_CXX17',
                   '_LIBCPP_DEPRECATED_IN_CXX20',
                   '_LIBCPP_NODISCARD',
                   '_LIBCPP_NODISCARD_EXT',

libcxx/include/CMakeLists.txt

set(files
   __utility/cmp.h
   __utility/convert_to_integral.h
   __utility/declval.h
   __utility/exception_guard.h
   __utility/exchange.h
   __utility/forward.h
   __utility/forward_like.h
   __utility/in_place.h
   __utility/integer_sequence.h
+  __utility/is_pointer_in_range.h
   __utility/move.h
   __utility/pair.h
   __utility/piecewise_construct.h
   __utility/priority_tag.h
   __utility/rel_ops.h
   __utility/swap.h
   __utility/terminate_on_exception.h
   __utility/to_underlying.h

libcxx/include/__config

 #  define _LIBCPP_COMPILER_CLANG_BASED
 #  define _LIBCPP_CLANG_VER (__clang_major__ * 100 + __clang_minor__)
 #elif defined(__GNUC__)
 #  define _LIBCPP_COMPILER_GCC
 #endif
 
 #ifdef __cplusplus
 
+// The attributes supported by clang are documented at https://clang.llvm.org/docs/AttributeReference.html
+
 // _LIBCPP_VERSION represents the version of libc++, which matches the version of LLVM.
 // Given a LLVM release LLVM XX.YY.ZZ (e.g. LLVM 17.0.1 == 17.00.01), _LIBCPP_VERSION is
 // defined to XXYYZZ.
 #  define _LIBCPP_VERSION 170000
 
 #  define _LIBCPP_CONCAT_IMPL(_X, _Y) _X##_Y
 #  define _LIBCPP_CONCAT(_X, _Y) _LIBCPP_CONCAT_IMPL(_X, _Y)
 

 #  endif
 
 #  if __has_attribute(__preferred_name__)
 #    define _LIBCPP_PREFERRED_NAME(x) __attribute__((__preferred_name__(x)))
 #  else
 #    define _LIBCPP_PREFERRED_NAME(x)
 #  endif
 
+#  if __has_attribute(__no_sanitize__)
+#    define _LIBCPP_NO_SANITIZE(...) __attribute__((__no_sanitize__(__VA_ARGS__)))
+#  else
+#    define _LIBCPP_NO_SANITIZE(...)
+#  endif
+
 // We often repeat things just for handling wide characters in the library.
 // When wide characters are disabled, it can be useful to have a quick way of
 // disabling it without having to resort to #if-#endif, which has a larger
 // impact on readability.
 #  if defined(_LIBCPP_HAS_NO_WIDE_CHARACTERS)
 #    define _LIBCPP_IF_WIDE_CHARACTERS(...)
 #  else
 #    define _LIBCPP_IF_WIDE_CHARACTERS(...) __VA_ARGS__

libcxx/include/__utility/is_pointer_in_range.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___UTILITY_IS_POINTER_IN_RANGE_H
+#define _LIBCPP___UTILITY_IS_POINTER_IN_RANGE_H
+
+#include <__algorithm/comp.h>
+#include <__assert>
+#include <__config>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/integral_constant.h>
+#include <__type_traits/is_constant_evaluated.h>
+#include <__type_traits/is_function.h>
+#include <__type_traits/is_member_pointer.h>
+#include <__type_traits/void_t.h>
+#include <__utility/declval.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _Tp, class _Up>
+_LIBCPP_CONSTEXPR_SINCE_CXX14 _LIBCPP_HIDE_FROM_ABI _LIBCPP_NO_SANITIZE("address") bool __is_pointer_in_range(
+    const _Tp* __begin, const _Tp* __end, const _Up* __ptr) {
+  static_assert(!is_function<_Tp>::value && !is_function<_Up>::value,
+                "__is_pointer_in_range should not be called with function pointers");
+  static_assert(!is_member_pointer<_Tp>::value && !is_member_pointer<_Up>::value,
+                "__is_pointer_in_range should not be called with member pointers");
+
+  if (__libcpp_is_constant_evaluated()) {
+    _LIBCPP_ASSERT(__builtin_constant_p(__begin <= __end), "__begin and __end do not form a range");
+
+    // If this is not a constant during constant evaluation we know that __ptr is not part of the allocation where
+    // [__begin, __end) is.
+    if (!__builtin_constant_p(__begin <= __ptr && __ptr < __end))
+      return false;
+  }
+
+  // Checking this for unrelated pointers is technically UB, but no compiler optimizes based on it (currently).
+  return !__less<>()(__ptr, __begin) && __less<>()(__ptr, __end);
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___UTILITY_IS_POINTER_IN_RANGE_H

libcxx/include/module.modulemap.in

module unordered_set {
     export initializer_list
     export *
   }
   module utility {
     header "utility"
     export initializer_list
     export *
 
     module __utility {
       module as_const               { private header "__utility/as_const.h" }
       module auto_cast              {
         private header "__utility/auto_cast.h"
         export type_traits.decay
       }
       module cmp                    { private header "__utility/cmp.h" }
       module convert_to_integral    { private header "__utility/convert_to_integral.h" }
       module declval                { private header "__utility/declval.h" }
       module exception_guard        { private header "__utility/exception_guard.h" }
       module exchange               { private header "__utility/exchange.h" }
       module forward                { private header "__utility/forward.h" }
       module forward_like           { private header "__utility/forward_like.h" }
       module in_place               { private header "__utility/in_place.h" }
       module integer_sequence       { private header "__utility/integer_sequence.h" }
+      module is_pointer_in_range    { private header "__utility/is_pointer_in_range.h" }
       module move                   { private header "__utility/move.h" }
       module pair                   { private header "__utility/pair.h" }
       module pair_fwd               { private header "__fwd/pair.h" }
       module piecewise_construct    { private header "__utility/piecewise_construct.h" }
       module priority_tag           { private header "__utility/priority_tag.h" }
       module rel_ops                { private header "__utility/rel_ops.h" }
       module swap                   { private header "__utility/swap.h" }
       module terminate_on_exception { private header "__utility/terminate_on_exception.h" }

libcxx/include/string

 #include <__type_traits/is_convertible.h>
 #include <__type_traits/is_nothrow_default_constructible.h>
 #include <__type_traits/is_nothrow_move_assignable.h>
 #include <__type_traits/is_same.h>
 #include <__type_traits/is_standard_layout.h>
 #include <__type_traits/is_trivial.h>
 #include <__type_traits/noexcept_move_assign_container.h>
 #include <__type_traits/remove_cvref.h>
+#include <__type_traits/void_t.h>
 #include <__utility/auto_cast.h>
+#include <__utility/declval.h>
+#include <__utility/is_pointer_in_range.h>
 #include <__utility/move.h>
 #include <__utility/swap.h>
 #include <__utility/unreachable.h>
 #include <climits>
 #include <cstdint>
 #include <cstdio>  // EOF
 #include <cstring>
 #include <limits>

 template <class _CharT, class _Traits, class _Tp>
 struct __can_be_converted_to_string_view : public _BoolConstant<
       is_convertible<const _Tp&, basic_string_view<_CharT, _Traits> >::value &&
      !is_convertible<const _Tp&, const _CharT*>::value
     > {};
 
 struct __uninitialized_size_tag {};
 
+template <class _Tp, class _Up, class = void>
+struct __is_less_than_comparable : false_type {};
+
+template <class _Tp, class _Up>
+struct __is_less_than_comparable<_Tp, _Up, __void_t<decltype(std::declval<_Tp>() < std::declval<_Up>())> > : true_type {
+};
+
 template<class _CharT, class _Traits, class _Allocator>
 class basic_string
 {
 public:
     typedef basic_string                                 __self;
     typedef basic_string_view<_CharT, _Traits>           __self_view;
     typedef _Traits                                      traits_type;
     typedef _CharT                                       value_type;
basic_string& __null_terminate_at(value_type* __p, size_type __newsz) {
       __set_size(__newsz);
       __invalidate_iterators_past(__newsz);
       traits_type::assign(__p[__newsz], value_type());
       return *this;
     }
 
     _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __invalidate_iterators_past(size_type);
 
-    template<class _Tp>
-    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
-    bool __addr_in_range(_Tp&& __t) const {
-        // assume that the ranges overlap, because we can't check during constant evaluation
-        if (__libcpp_is_constant_evaluated())
-          return true;
-        const volatile void *__p = std::addressof(__t);
-        return data() <= __p && __p <= data() + size();
+    template <
+        class _Tp,
+        __enable_if_t<__is_less_than_comparable<const __remove_cvref_t<_Tp>*, const value_type*>::value, int> = 0>
+    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __addr_in_range(const _Tp& __v) const {
+      return std::__is_pointer_in_range(data(), data() + size() + 1, std::addressof(__v));
+    }
+
+    template <
+        class _Tp,
+        __enable_if_t<!__is_less_than_comparable<const __remove_cvref_t<_Tp>*, const value_type*>::value, int> = 0>
+    _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __addr_in_range(const _Tp& __v) const {
+                return false;
+
+      auto __t_ptr = reinterpret_cast<const char*>(std::addressof(__v));
+      return reinterpret_cast<const char*>(data()) <= __t_ptr &&
+             __t_ptr < reinterpret_cast<const char*>(data() + size() + 1);
     }
 
     _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
     void __throw_length_error() const {
         std::__throw_length_error("basic_string");
     }
 
     _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const value_type* __s, size_type __n2)
     _LIBCPP_ASSERT(__n2 == 0 || __s != nullptr, "string::replace received nullptr");
     size_type __sz = size();
     if (__pos > __sz)
         __throw_out_of_range();
     __n1 = std::min(__n1, __sz - __pos);
     size_type __cap = capacity();
     if (__cap - __sz + __n1 >= __n2)
     {
-        if (__libcpp_is_constant_evaluated()) {
-            __grow_by_and_replace(__cap, 0, __sz, __pos, __n1, __n2, __s);
-            return *this;
-        }
         value_type* __p = std::__to_address(__get_pointer());
         if (__n1 != __n2)
         {
             size_type __n_move = __sz - __pos - __n1;
             if (__n_move != 0)
             {
                 if (__n1 > __n2)
                 {
                     traits_type::move(__p + __pos, __s, __n2);
                     traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
                     return __null_terminate_at(__p, __sz + (__n2 - __n1));
                 }
-                if (__p + __pos < __s && __s < __p + __sz)
+                if (std::__is_pointer_in_range(__p + __pos + 1, __p + __sz, __s))
                 {
                     if (__p + __pos + __n1 <= __s)
                         __s += __n2 - __n1;
                     else // __p + __pos < __s < __p + __pos + __n1
                     {
                         traits_type::move(__p + __pos, __s, __n1);
                         __pos += __n1;
                         __s += __n2;

libcxx/test/libcxx/utilities/is_pointer_in_range.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// ADDITIONAL_COMPILE_FLAGS: -Wno-private-header
+
+#include <__utility/is_pointer_in_range.h>
+#include <cassert>
+
+#include "test_macros.h"
+
+template <class T, class U>
+TEST_CONSTEXPR_CXX14 void test_cv_quals() {
+  T i = 0;
+  U j = 0;
+  assert(!std::__is_pointer_in_range(&i, &i, &i));
+  assert(std::__is_pointer_in_range(&i, &i + 1, &i));
+  assert(!std::__is_pointer_in_range(&i, &i + 1, &j));
+
+#if TEST_STD_VER >= 20
+  {
+    T* arr1 = new int[4]{1, 2, 3, 4};
+    U* arr2 = new int[4]{5, 6, 7, 8};
+
+    assert(!std::__is_pointer_in_range(arr1, arr1 + 4, arr2));
+    assert(std::__is_pointer_in_range(arr1, arr1 + 4, arr1 + 3));
+    assert(!std::__is_pointer_in_range(arr1, arr1, arr1 + 3));
+
+    delete[] arr1;
+    delete[] arr2;
+  }
+#endif
+}
+
+TEST_CONSTEXPR_CXX14 bool test() {
+  test_cv_quals<int, int>();
+  test_cv_quals<const int, int>();
+  test_cv_quals<int, const int>();
+  test_cv_quals<const int, const int>();
+  test_cv_quals<volatile int, int>();
+  test_cv_quals<int, volatile int>();
+  test_cv_quals<volatile int, volatile int>();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+#if TEST_STD_VER >= 14
+  static_assert(test(), "");
+#endif
+
+  return 0;
+}