P3852R3: constexpr is_pointer_within memory area

does the pointer points to my allocator?

Most typical use-case is to ask "I have a pointer, does it belong to one of my allocations?"

struct allocator {
	struct block_type {
		const T * first;
		const T * last;
		
		const T * begin() const {
			return first;
		}
		const T * end() const {
			return last;
		}
	};
	std::vector<block_type> blocks;
	constexpr bool belongs_to_me(const T * ptr) const {
		// assuming valid pointer
		for (const auto & block: blocks) {
			// BEFORE: unspecified in a runtime execution or not a constant expression
			//         if `ptr` points to different top-level object than `block.ptr`
			if (block.begin() <= ptr && ptr < block.end()) return true;
			
			// BEFORE but author knows the standard: no longer unspecified (now it is implementation defined) but still not a constant expression
			if (std::less_equal<>(block.begin(), ptr) && std::less<>(ptr, block.end())) return true;
			
			// BEFORE but author needs it to work in constant evaluation and she pays the price
			if consteval {
			  if (std::less_equal<>(block.begin(), ptr) && std::less<>(ptr, block.end())) return true;
			} else {
			  // whops, doesn't work for subobjects of `obj` !!!
			  for (const T & obj: block) if (std::addressof(obj) == ptr) return true;
			}
			
			// AFTER: false if `ptr` is not pointing to same top-level object as `block.ptr`
			if (is_pointer_within(ptr, block.begin(), block.end())) return true;
		}
		return false;
	}
}

This example shows we don't need to define total ordering of memory, but we just need to have answer "if these pointers are related, how they compare". This paper doesn't propose function bool pointers_related(const void *, const void *) which won't be implementable without additional cost in runtime. And because defining total ordering is also not a possible option, as some architectures wouldn't be able to be conforming, this proposal proposes this function which combines these questions together in one simple low-level functionality.

why not consteval only pointers_related?

Jan argued in mailing list, to provide this (not proposed) function to be consteval only and have it to be magic as is_within_lifetime. I disagree with it, because I don't want to force user to write if consteval in user code. Actually my design criterium for all constexpr functionality is to avoid such need at all. The typical code user would need to write would be:

constexpr bool user_is_pointer_within(const void * ptr, const void * first, const void * last) {
	if consteval {
		assert(is_pointer_related(first, last));
		if (!is_pointer_related(ptr, first) || !is_pointer_related(ptr, last)) {
			return false;
		}
	}
	return first <= ptr && ptr < last;
}

Which is basically the proposed functionality of this paper, but without additional benefits of informing optimizer about the relationship between ptr and the memory range. With the same footgun in shape of the past-the-end iterator (if we allow it) and it won't provide any protection in runtime (a static analysis tools, can use the information about the standard library functionality proposed here easily.)

defining total ordering is not feasible

Currently result of a comparison of two unrelated pointers is not specified in the language (according [expr.rel], but you can use std::less<T *> in the library [comparisons] for an implementation specified ordering). This proposal gives you ability to express a different thing than ordering: is something related AND belongs inside? That's in my experience more useful than global total ordering.

But what if you really want the total ordering for pointers? After all most of architectures are like that. For example CHERI is different.

can we make std::less<T *> work in constant evaluator

(Some) constant evaluators doesn't use real pointers for interpreted pointers, in order to being able to detect crimes against abstract machine and UB, (at least in clang) they consider of identifier of top-level object and provenance path. Unrelated objects there are just that ... unrelated symbols.

Hence std::less<T *> can't give us answer as there is no answer about relationship. But for proposed functionality the answer exists.

static analysis and contracts

With this proposal we can specify relationship belongs inside to be usable for contracts and static analysis tools. For example we will be able to specify post contract "returned reference belongs to span you provided" without UB or implementation specific behavior.

constexpr std::hive

For another example, std::hive's member function get_iterator(T *) -> iterator checkes all allocated blocks if provided pointer is in range, and then uses the right block's first member to calculate object's index to construct hive's iterator.

To make this constexpr we must have a way how to check without possibility of a failure to constant evaluate.

What can happen?

Following table explores existing options and proposed variants, and why the exclusive is_pointer_within with precondition to disallow a past-the-end pointers is picked:

Why not just provide check for related pointers?

This is easy to implemented for constant evaluation, but not for runtime code. I think providing such functionality would provide false sense of security and lead to misuse, therefore I'm not proposing it.

Why not span?

We don't have std::span<const void> and we p pointer can be pointing (or not pointing) to a subject of different type than the range (in case it would be typed) and this would lead to unnecessary template instantiation.

Also requiring span will limit this functionality only for known types. At least the ptr argument must be always void, as the storage type is often known (not in case of malloc, where we can't do pointer aritmetic and get ptr + size, which can be problem in constexpr where we don't have malloc yet or allocators), but the pointer type ptr can be multiple things interacting with same range.

Why it's [first, last) and not inclusive range?

It would be impossible to check for intersection of two ranges sitting next to each other. If there is demand for such functionality there is a possibility for bool is_related_and_equal(const void * a, const void * b);

Take following example:

std::array<int, 20> buffer;

enum class relation {
	unrelated,
	first_half,
	second_half,
};

constexpr relation belongs_to_first_half(const int * ptr) {
	const int * first = buffer.data();
	const int * first_mid = buffer.data() + (buffer.size() / 2);
	const int * last = buffer.data() + buffer.size();
	if (is_pointer_within(ptr, first, first_mid)) { // problem: surprising inclusion of [first,first_mid]
		return relation::first_half;
	} else if (is_pointer_within(ptr, first_mid, last)) {
		return relation::second_half;
	} else {
		return relation::unrelated;
	}
}

If user pass ptr pointing to &buffer[10] which is in second half, it will get answer relation::first_half. And user will be forced to write something like buffer.data() + (buffer.size() / 2) - 1 and this can be very error-prone as every off-by-one error, whole library is using [first, last) this function should too.

And if you really want to check if ptr is past-the-end pointer to a range, you can safely do ptr == last which will give you true or false without failure to constant evaluate.

This signature seems error prone

I know, I was thinking if it should first, last, pointer, but without span<const void> or providing something like struct memory_range { const void * start; const void * end; }; we will end up with three pointers anyway.

For me the most obvious order is to put them in expected order which will is the one which will return true, anything else would be confusing and users will be wondering if it was first, last, pointer or pointer, first, last, and will end up googling it, trying to open first link to CPlusPlus.com, noticing they are opening it, and quickly go back to open C++ Reference instead and still ends up waiting for fonts to load.

Symmetry with clamp

Originally I had it first, ptr, last, but was told we have std::clamp(ptr, first, last), so I'm mirroring existing signature. I don't want users to franctically google how it is supposed to be.

std::less<T *>

Library specified implementation specific strict total ordering for std::less<T *>, but this is not a case for constant evaluated code.

Weird or segmented architectures

On some platforms it's possible that the comparison return false positive, if somehow pointers points at the same memory but in different segments. This is already happening when someone tries to implement this with std::less<T *> and it's not a problem in practice as such architectures are rare (16-bit x86 mode, ESA/390, z/Architecture).

Passing the past-the-end pointer as first argument

In first revision I had following example which assumed I can pass the past-the-end pointer as first argument. If we allow it, we can do this:

constexpr bool intersect(std::span<const T> lhs, std::span<const T> rhs) noexcept {
	const auto * a = lhs.data();
  const auto * b = lhs.data() + lhs.size();
  const auto * x = rhs.data();
  const auto * y = rhs.data() + rhs.size();
	// following code assumes we can pass past-the-end pointer as first argument
  return std::is_pointer_within(x, a, b) 
      || std::is_pointer_within(y, a, b)
      || std::is_pointer_within(a, x, y)
      || std::is_pointer_within(b, x, y);
}

void transfer(std::span<const T> source, std::span<T> target) 
  pre(not intersect(source, target) && source.size() == target.size()) 
{
  std::copy(source.begin(), source.end(), target.begin());
}

constexpr bool intersect(std::span<const T> lhs, std::span<const T> rhs) noexcept {
	const auto * a = lhs.data();
  const auto * b = lhs.data() + lhs.size();
  const auto * x = rhs.data();
  const auto * y = rhs.data() + rhs.size();
	// works with exclusive version and doesn't need to support past-the-end pointers
  return std::is_pointer_within(x, a, b) 
      || std::is_pointer_within(a, x, y);
}

constexpr bool test(int offset) {
	std::array<char, 32> a = {...};
	std::array<char, 32> b = {...};
	// following line returns different result during runtime/constant evaluation
	// if we allow passing past-the-end pointer
	return std::is_pointer_within(a.data() + a.size(), b.data(), b.data() + b.size());
}

Why the implementation doesn't check for the precondition?

Library preconditions often are not check, and this is the same case, as sometimes it's impossible to check, but still is better to say "if you pass past-the-end pointer, it won't work".

Alternative way how to get almost the same result

In cases where we have an array (or a set) of items, and wants to check if the item is inside array, I can just check against every single one for equality which is properly defined (unless one of the pointers is past-the-end pointer).

template <typename T> constexpr bool is_pointer_within(std::span<const T> array, const T * p) {
	// doesn't check past-end pointer
	return std::ranges::any_of(array, [=](const T & obj) { return std::addressof(obj) == p; });
}

Is this okay? It's not, it's O(n). Any such operation shouldn't be this slow. Also it doesn't allow us to check if subject is in the range as a subject, so the functionality is actually different.

And the major usability problem is, it doesn't work with subobjects with non-zero offset.

Feature test macro

#define __cpp_lib_is_pointer_within 2026??L // freestanding, also in <memory>