This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Introduce __is_pointer_in_range
ClosedPublic

Authored by philnik on Feb 4 2023, 2:54 PM.

Details

Reviewers
ldionne
Mordante
var-const
Group Reviewers
Restricted Project
Commits
rG7949ee0d4f10: [libc++] Introduce __is_pointer_in_range
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.

Diff Detail

Event Timeline

philnik created this revision.Feb 4 2023, 2:54 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 4 2023, 2:54 PM
philnik requested review of this revision.Feb 4 2023, 2:54 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 4 2023, 2:54 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik added inline comments.Feb 4 2023, 2:56 PM
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 updated this revision to Diff 494871.Feb 5 2023, 1:21 AM

Generate files

Mordante edited the summary of this revision. (Show Details)Feb 5 2023, 3:49 AM

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
716

I miss the module map entry.

libcxx/include/__config
1093

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 updated this revision to Diff 496142.Feb 9 2023, 8:24 AM
philnik marked 3 inline comments as done.

Address comments

libcxx/include/__config
1093

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 added inline comments.Feb 11 2023, 6:02 AM
libcxx/include/__config
1093

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 updated this revision to Diff 497246.Feb 14 2023, 2:09 AM
philnik marked 5 inline comments as done.

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 requested changes to this revision.Feb 27 2023, 9:05 AM
ldionne added inline comments.
libcxx/include/module.modulemap.in
1585

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
1974

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.

1978

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 <).

This revision now requires changes to proceed.Feb 27 2023, 9:05 AM
philnik updated this revision to Diff 501134.Feb 28 2023, 7:32 AM
philnik marked 2 inline comments as done.

Address comments

philnik updated this revision to Diff 501228.Feb 28 2023, 10:53 AM

Try to fix CI

ldionne accepted this revision.Mar 2 2023, 8:33 AM

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
1975

Here and below.

1988

For symmetry with above?

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

Could we move this test to test_cv_quals?

This revision is now accepted and ready to land.Mar 2 2023, 8:33 AM
philnik updated this revision to Diff 527646.Jun 1 2023, 3:18 PM
philnik marked 5 inline comments as done.

Address comments

philnik updated this revision to Diff 529093.Jun 6 2023, 4:59 PM

Try to fix CI

philnik updated this revision to Diff 529322.Jun 7 2023, 8:37 AM

Try to fix CI

philnik updated this revision to Diff 529326.Jun 7 2023, 8:54 AM

Try to fix CI

This revision was automatically updated to reflect the committed changes.