[libc++][ranges] Implement ranges::uninitialized_default_construct{,_n}.

[var-const]

Summary

Defined in [specialized.algorithms](wg21.link/specialized.algorithms).

Also:

• refactor the existing non-range implementation so that most of it can be shared between the range-based and non-range-based algorithms;
• remove an existing test for the non-range version of uninitialized_default_construct{,_n} that likely triggered undefined behavior (it read the values of built-ins after default-initializing them, essentially reading uninitialized memory).

[var-const]

Use the actual patch number on the ranges' status page.

[var-const]

Remove extraneous parentheses.

[var-const]

Formatting

[var-const]

Remove accidentally copied

[var-const]

Formatting

[var-const]

Annotate test file

libcxx/include/__memory/uninitialized_algorithms.h

126

This should be a backward-compatible change -- the C++17 public function still checks that the passed parameters have the same type.

126

This function now always returns the iterator to accommodate all callers. I presume this can be easily optimized away for the callers that don't use the result.

132

Note: this cast is simpler than the [voidify](http://eel.is/c++draft/specialized.algorithms#general-4) function that the Standard mandates. Should I fix this, or is there a reason why a simple cast to void* is sufficient here?

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct.pass.cpp

16–18

Is it necessary to list out all the constraints here, or would just ForwardIterator ranges::uninitialized_default_construct(ForwardIterator first, Sentinel last) (or even just ranges::uninitialized_default_construct) suffice?

148

These tests are heavily inspired by libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/uninitialized_default_construct.pass.cpp.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct_n.pass.cpp

4

I think it would make sense to merge this file with the version taking iterator+sentinel / range because the tests are very similar and it would help cut down the boilerplate.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/uninitialized_default_construct.pass.cpp

26

It was unused.

[• Quuxplusone]

Other than inline namespace __cpo and some of my comments on the tests, this looks basically good to me.

libcxx/include/__memory/ranges_uninitialized_algorithms.h

9

I'm still weakly inclined to split this up into ranges_uninitialized_default_construct.h, ranges_uninitialized_value_construct.h, ranges_uninitialized_copy.h, ranges_uninitialized_move.h, ranges_uninitialized_fill.h.

I imagine it's OK to have ranges::foo and ranges::foo_n in the same header, since the Standard actually does the same thing with its subsection naming (e.g. both ranges::uninitialized_fill and ranges::uninitialized_fill_n are located in https://eel.is/c++draft/uninitialized.fill ). We have two bad options here: smushing all ten niebloids into 1 header of 175 lines, or spreading them out into 5 headers of 80 lines each.

I'm weakly in favor of "5 headers" but I guess "1 header of 175 lines total" doesn't sound too bad when I put it that way.

33

I believe this __function_like business has caused weird Modules errors before (hence the workarounds you'll see in a few places in the modulemap). It's not needed for conformance, so I would strongly prefer you simply omit it — "Keep It Simple."
Likewise I would personally omit the final cruft (it disables the EBO but otherwise has no effect except taking longer to read), but it's not going to cause weird Modules errors, so I don't care as much about whether or not we add final. :)

52

Line 47: please T&& t, not T &&t
Lines 39, 46, 64: please indent the requires-clause two spaces

54–55

Here and line 73, please inline namespace __cpo { ~~~ }. (See https://quuxplusone.github.io/blog/2021/12/07/namespace-cpo/ for my rationale, which boils down to "consistency.")

69

This is actually specced as

return uninitialized_default_construct(counted_iterator(first, n), default_sentinel).base();

but is the difference observable? I can't think of a reason it would be, so I'm fine with this as you've written it.

libcxx/include/__memory/uninitialized_algorithms.h

132

I can't think of any reason a simple cast to void* would be insufficient. I'd leave it simple until-and-unless someone comes up with a positive reason and gives us a regression test case. Otherwise, you'll complexify the code and someone six months from now will ask why it can't be simpler.

libcxx/include/memory

235

Here and above: lowercase // since C++20

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct.pass.cpp

16–18

Personally, I'd err on the side of "just cut and paste what the Standard's synopsis says," which I believe is exactly what you've done here.

However, if you had just written // ranges::uninitialized_default_construct, I personally wouldn't have bothered to complain about it, either. :)

62–72

Let's also do some non-common ranges. I suggest these three tests in place of lines 68–71:

std::ranges::uninitialized_default_construct(std::ranges::empty<Counted>);  // [basically the same as your 68–69, but gives nullptr for begin and end instead of as_array]
assert(Counted::current_objects == 0);
assert(Counted::total_objects == 0);

auto it = forward_iterator<Counted*>(as_array);
auto r = std::ranges::subrange(it, sentinel_wrapper<forward_iterator<Counted*>>(it));
std::ranges::uninitialized_default_construct(r.begin(), r.end());
assert(Counted::current_objects == 0);
assert(Counted::total_objects == 0);

std::ranges::uninitialized_default_construct(r);
assert(Counted::current_objects == 0);
assert(Counted::total_objects == 0);

Ditto throughout: please make sure to test non-common ranges, because that's really the major feature you're actually adding here (e.g. that's why you had to modify the non-ranges version of the algorithm).

104–117

I'm pretty sure this is UB. array[0] is trivially destructible, so it's cool that you're skipping its destructor before creating a new int object at that location; but then you're reading the value of that new int object, and you haven't actually given it a value (default-constructing a primitive type doesn't set its value). So line 107 is UB.
Just remove this whole function. Even if it weren't UB, I'm not clear on what it's trying to test.

(and yeah, I say the same thing about test_value_initialized() from uninitialized_default_construct.pass.cpp)

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/special_function.compile.pass.cpp

24–55 ↗

(On Diff #392634)

This seems like overkill. (Certainly adl_forward_iterator needn't be a template! And you see why inheriting from things-that-aren't-meant-for-inheritance is a bad idea.)
I recommend replacing this whole thing with two lines, which can go in their respective .pass.cpp files:

static_assert(std::is_class_v<decltype(std::ranges::uninitialized_default_construct)>);
static_assert(std::is_class_v<decltype(std::ranges::uninitialized_default_construct_n)>);

I recommend adding a bonus test case for their SFINAE, as well:

struct NotDefaultCtable { NotDefaultCtable(int); };
static_assert(!std::is_invocable_v<decltype(std::ranges::uninitialized_default_construct), NotDefaultCtable*, NotDefaultCtable*>);
static_assert(!std::is_invocable_v<decltype(std::ranges::uninitialized_default_construct_n), NotDefaultCtable*, int>);

[• Quuxplusone]

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct_n.pass.cpp

4

FWIW, that seems like a reasonable rationale to me, but it does go against our general rule of "separate test files for separate functionalities." And the boilerplate isn't costing us much.

28

I forgot to mention, I'm not a big fan of this alias (I'd rather see std::ranges:: everywhere), but if you must pick a name for the alias, then this is 100% the best name. It prevents me from git grep -l std::ranges::foo, but at least I can still git grep -l ranges::foo if I suspect this trick has been played. :)

[ldionne]

Overall LGTM with some comments. Thanks a lot, this is awesome and I love the direction we are taking for these algorithms.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct.pass.cpp

11

Need to add libcpp-has-no-incomplete-ranges.

12

We don't support it anymore, none of our tests mention this anymore unless I'm mistaken.

61

I've expressed this preference in other patches (not yours), but IMO it's better to use a comment to describe what we're testing, since it allows using plain english instead of trying to cram as much meaning as possible into a few identifiers (a function name). I would suggest:

void test() {
  // comment1
  {
    ...
  }

  // comment2
  {
    ...
  }

#ifndef TEST_HAS_NO_EXCEPTIONS
  {
    ...
  }
#endif
}

63

Non-binding, just a suggestion. I generally find it easier to glance at code when types are explicit since I don't have to parse and understand the expression used to initialize the variable in order to know its type. In this case it's arguably simple since it's a reinterpret_cast, but still.

Generally, I take auto as meaning: "you don't care about the specific type of the variable since it results from something more complex (like an expression template or a views::foo(...) call), so don't even try". When I see that, I basically assume that the precise type of the variable isn't important, only the properties of that type are. Here this isn't the case.

148–153

[ldionne]

libcxx/include/__memory/ranges_uninitialized_algorithms.h

9

I am mostly neutral on this, however I don't believe the different algorithms are going to have significantly different header dependencies. In that case, I think it might be simpler to just cram them into the same header -- after all they are closely related.

Like I said, no strong opinion here anyway.

33

About final -- we have [[no_unique_address]] now so EBO shouldn't be an issue.

Regarding modules issues, basically it means you're going to need to export it from your private submodule, like so:

module ranges_uninitialized_algorithms {
    private header "__memory/ranges_uninitialized_algorithms.h"
    export __function_like
}

FWIW, I think there is some utility to removing things like addressability from our niebloids, the complexity around modules is just a bit annoying but it's still worth doing. Just my .02, this isn't anything close to "over my dead body".

libcxx/include/__memory/uninitialized_algorithms.h

132

When @Quuxplusone originally removed __voidify in D93153, I was fine with it. I just did some additional research and I suspect it might have been wrong: https://githubmemory.com/repo/microsoft/STL/issues/1780

I think we should figure out what the situation is and either confirm that we're conforming, or fix all the places where we use (void*)x but the standard says __voidify(x).

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct.pass.cpp

16–18

The only caveat to using // ranges::uninitialized_default_construct is that it's good to see the different overloads being tested. I really dislike seeing a test file that doesn't clearly say whether it tests all overloads of a function or not. In C++, different overloads often have different properties, and so they are really different functions entirely. They just happen to share the same "base name".

TLDR: IMO the current approach (copy-paste synopsis) is the best.

104–117

I actually buy @Quuxplusone 's reasoning as well.

Initially I thought we were verifying that we called the default constructor for trivially default constructible types, which does nothing (and hence doesn't overwrite the value). But I agree this looks like UB as well based on your reasoning.

IIUC, what we're *actually* trying to test here is that we are not calling any constructors. One way to do this would be to add a .sh.cpp test using FileCheck where we check the LLVM bitcode output, like they often do in Clang. I think it would be awesome to have that infrastructure available, however at the moment FileCheck isn't available while running the libc++ tests.

So IMO the pragmatic thing to do right now is to remove the test.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/special_function.compile.pass.cpp

24–55 ↗

(On Diff #392634)

[Using static_assert(std::is_class_v<...>)]

Interesting trick! It's true that if it's a class type, then ADL for sure won't trigger, so we'd have the same coverage. However, implementations are technically allowed to use functions (it would presumably be implemented with some sort of attribute) to inhibit ADL, so this would have to be LIBCPP_STATIC_ASSERT because std::is_class_v would be libc++ specific.

I don't have a strong opinion about this, but I agree this is pretty attractive from a simplicity perspective.

[• Quuxplusone]

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/special_function.compile.pass.cpp

24–55 ↗

(On Diff #392634)

implementations are technically allowed to use functions

Sure, technically, but until literally anyone does even a proof of concept patch to literally any compiler in the world to permit that, I think we can discount the possibility. ;) (This is closely adjacent to my logic against __function_like, btw. Everyone knows that niebloids are objects-not-functions; there's no engineering benefit gained by pretending things aren't as they are, and meanwhile there are engineering costs.)

[• Quuxplusone]

libcxx/include/__memory/uninitialized_algorithms.h

132

(Argh, I keep forgetting to reply to things on the first go-round. Sorry.)
IIUC, STL's comment there indicates that we should add a test case for const iterators, e.g.

auto cit = forward_iterator<const Counted*>(as_array);
auto r = std::ranges::subrange(cit, sentinel_wrapper<forward_iterator<const Counted*>>(cit + 2));
std::ranges::uninitialized_default_construct(r.begin(), r.end());
assert(Counted::current_objects == 2);
assert(Counted::total_objects == 2);

That's missing test coverage today, but AFAIK it's not an argument against the simple cast to (void*). C-style casts are allowed to cast away constness.

[var-const]

• Address feedback;
• Create Buffer class in tests.

[var-const]

Note: I have refactored the repetitive initialization code into a helper Buffer class that I hope can be reused across similar tests.

libcxx/include/__memory/ranges_uninitialized_algorithms.h

9

I'm slightly in favor of keeping these in a single file because they're closely related and I personally find it easier to read when related things are all in one place. I don't have a strong objection to separating these, though.

What I can do is to keep everything in a single file for the initial implementation and then have an NFC commit to split them. I hope at that point it would be clearer which approach is more readable here, and we can decide whether to merge or revert that patch.

33

I think the idea here is to make sure no users can end up accidentally depending on any properties that aren't explicitly guaranteed by the Standard (and yes, their code would be in error in that case, but it's still a possible problem that would require somebody to spend time fixing it, and we can prevent that problem from happening in the implementation). It does go beyond what is strictly necessary for conformance, but arguably it can result in slightly better experience for the users. Moreover, removing __function_like in the future should be a non-breaking change (I don't think ABI is a concern here, though I can easily be wrong on this), whereas going the other way round could realistically break somebody.

Also, we already have precedent in some of the iterator algorithms (e.g. advance and next). This isn't a particularly strong argument because there are very few instances, so changing them is quite simple. Basically, we would just need to make sure we are consistent.

52

Done, thanks!

54–55

Thanks! Very helpful article.

69

Sorry, I should have called it out in my comments. Yes, I did this deliberately because I couldn't think of a case where the two forms wouldn't be equivalent, and delegating directly to the internal helper _n function seemed simpler than creating a wrapped iterator then delegating to the other helper.

libcxx/include/__memory/uninitialized_algorithms.h

132

Added the test.

It looks like until C++20, the Standard defined voidify as performing a simple static_cast<void*> cast, but that would fail if the given type is cv-qualified because static_cast can't cast away cv qualifiers. The new definition works around it by doing two casts, a static_cast followed by a const_cast. However, it does seem like a simple C-style cast can achieve the same effect. I checked that the C-style cast succeeds when used with const iterators whereas the old static_cast<void*> approach fails as expected.

I still feel like we should have a dedicated __voidify function (that can use the C-style cast). For one, it would allow defining (and documenting) our approach in one place. It would also follow the way things are laid out in the Standard more closely, which I think is a nice bonus.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct.pass.cpp

11

Thanks!

12

Done. I think I copied it from an unsubmitted patch which presumably was written at a time when GCC 10 was still supported.

61

Done.

62–72

Added counted_iterator, views::counted and reverse_view. If you have any other suggestions, please let me know.

63

Thank you for explaining your rationale. The main reason I generally prefer using auto when doing casts is that auto can be taken to mean "use the exact same type as returned by the expression" (omitting nuances about constness and references for the purposes of this discussion). In other words, auto guarantees that no implicit conversion can take place, which could be relevant in a case like:

struct Base { ... };
struct Derived : Base { ... };

Base* p = reinterpret_cast<Derived*>(buffer); // Implicitly converted from `Derived` to `Base`
auto* p = reinterpret_cast<Derived*>(buffer); // Reader can be sure no implicit conversion can take place

While this isn't relevant here, this usage of auto arguably simplifies things for the reader by removing one case to watch out for (if used consistently).

Having said that, I see the value of your point as well. I was somewhat on the fence, so I decided to use consistency as a tie-breaker. A simple grep shows a single case of using auto with casts in the existing code; most existing casts specify the type directly. For this reason, I decided to go with your suggestion; after all, the benefits of either approach are mostly relevant only if they are followed consistently.

EDIT: after writing this, I refactored this code so that it became a member function and this is no longer applicable.

104–117

Thanks! Removed it here and in uninitialized_default_construct{,_n}.pass.cpp.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct_n.pass.cpp

28

Removed the alias. I took it from some existing code for consistency, but I don't have a strong preference.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/special_function.compile.pass.cpp

24–55 ↗

(On Diff #392634)

This approach is definitely very attractive due to its simplicity. These ADL tests are verbose, apply to every single range algorithm and can't really be simplified much (AFAICT). On the other hand, the current approach has the advantage of testing the effects whereas the new approach tests the implementation.

All in all, I'm inclined to go with the simpler approach because the boilerplate savings it provides are very significant. Thanks for suggesting this!

As you suggested, I moved these checks to the existing test files. I have also used LIBCPP_STATIC_ASSERT, though I don't feel super strongly about it (from a practical point of view, I presume it's true that no existing implementation uses or has any particular reason to use a different implementation method).

I've also added a TODO to rewrite the existing tests using the new approach.

[var-const]

Run libcxx-generate-files.

[ldionne]

Ship it. I suggest going back to add __voidify in the places that need it in a separate patch. It should be possible to figure out the places that need it by grepping for voidify in the standard.

libcxx/include/__memory/uninitialized_algorithms.h

132

FWIW, I suspect the difference might be that a C-style cast can't appear inside a constexpr context (because it ends up reinterpret_casting).
+1 for adding back __voidify -- we should probably make this one _LIBCPP_ALWAYS_INLINE to improve the debugging experience.

[var-const]

Small fixes, should fix the CI.

libcxx/include/__memory/uninitialized_algorithms.h

132

I'm not sure if having a C-style cast affects constexpr in this case. From my experiments, it looks like the compiler allows C-style casts as long as the cast doesn't actually perform a reinterpret_cast:

template <typename T>
constexpr void* voidify1(T& from) {
  // This works fine
  return const_cast<void*>(static_cast<const volatile void*>(&from));
}

template <typename T>
constexpr void* voidify2(T& from) {
  // This also works fine, presumably because it ends up
  // doing a `static_cast` followed by a `const_cast`
  return (void*)&from;
}

template <typename T>
constexpr void* voidify3(T& from) {
  struct Bar{};
  Bar* from2 = (Bar*)&from;
  // This doesn't work because converting to `Bar` can only
  // be done via a `reinterpret_cast`
  return (void*)from2;
}

I still feel like having a dedicated __voidify function. Whichever approach we end up deciding upon, it should be in one place where it's easy to document and easy to change.

[• Quuxplusone]

libcxx/include/__memory/uninitialized_algorithms.h

132

Right, reinterpret-casts are illegal in constexpr, but C-style-casts-that-are-not-reinterpret-casts are still perfectly legal.

I'm sticking to my rationale for not reintroducing __voidify: The more unnecessarily complicated you make the code, the more churn it kicks up, as people with different opinions repeatedly (over the course of several years) remove the complexity (because simplicity is good) and reintroduce the complexity (because ???). Simple is the local minimum, if we just have a general policy of "no additional complexity unless it serves a purpose."

My hypothesis for why the Standard uses voidify is that maybe they have a policy against ever using C-style casts (which means they need to use two new-style casts here, to mimic a fraction of its power). But that also seems far-fetched. Does the history of the cplusplus/draft repo give any hints?

[var-const]

libcxx/include/__memory/uninitialized_algorithms.h

132

To be clear, I don't necessarily propose changing the implementation. What I currently have in mind is something like:

template <typename T>
void* __voidify(T& from) {
  // Note: the C-style cast can remove cv-qualifiers, achieving the
  // same result as the sample implementation of `voidify` in the
  // Standard in a simpler manner.
  return (void*)_VSTD::addressof(from);
}

...

for (; __idx != __last; ++__idx)
        ::new (__voidify(*__idx)) _ValueType;

I see several advantages:

• avoids duplication, which prevents potential divergence;
• follows the Standard more closely -- it's obvious to the reader that we do implement voidify (with the current implementation, I was at first wondering if the implementation preceded the time voidify was added to the Standard and not updated);
• explains our implementation choice in a single place -- this should particularly help prevent any potential confusion and discussions in the future (or at the very least, the discussions would start having the necessary context so that people don't have to spend time wondering why it's implemented the way it is).

[var-const]

Fix the CI, add export __function_like to module.modulemap.

[var-const]

Fix the CI, pt.2.

[var-const]

Rebase on main.

[var-const]

Fix CI (?) and rebase on main.

[• Quuxplusone]

libcxx/include/__memory/ranges_uninitialized_algorithms.h

24

Please include the granular <__concepts/foo.h> headers here [er, in a-z order above], not all of <concepts>.

38

This should be as in the blog post too:

namespace __uninitialized_default_construct {
struct __fn {
};
} // namespace __uninitialized_default_construct

AIUI, this keeps the CPO's own type from ADL'ing into the std::ranges namespace; e.g. foobar(std::ranges::uninitialized_default_construct) should not consider std::ranges::foobar a candidate even if std::ranges::foobar is not a CPO itself.
Also, of course, consistency (Chesterton's Fence, the economist's hundred-dollar bill): if it were safe to omit the namespace, we'd certainly want to do it everywhere, not just here.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp

91

Yay. :) IMHO a more helpful pattern for this comment would just be
// TODO: make consistent with std/iterato...compile.pass.cpp
and name one of the files that you consider to be correct. Then, even someone-not-you should be able to deduce exactly what this comment is asking them to do.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/uninitialized_default_construct.pass.cpp

90

Btw, please commit this removal in a separate commit, and/or make sure there's something in your commit message about how we believe this was UB and that's why it's gone now.

[var-const]

Review feedback

[var-const]

libcxx/include/__memory/ranges_uninitialized_algorithms.h

38

Done (I added an _ns suffix to the namespace name to make sure it's different from the name of the helper functions). Do we actually need a separate namespace for each CPO, though?

By the way, can you please elaborate on how this could be a problem, given that the type of the CPO is an underscore-prefixed internal type?

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp

91

I don't feel too strongly about this, but in general I'm a little wary about comments that (effectively) contain links to other code -- the linked code can change and the comment becomes stale (e.g. if in the future these checks were to be moved to a single file).

Perhaps it would be even better to combine both approaches (explain the intent _and_ link an example), but given that I plan to fix this in the next few days, it seems like overkill to me.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/uninitialized_default_construct.pass.cpp

90

Updated the commit message.

[ldionne]

libcxx/include/__memory/ranges_uninitialized_algorithms.h

38

I *think* we could instead have a single namespace named something like __cpo_detail and then instead name our helpers __uninitialized_default_construct_fn. We could explore that in a separate PR, but for the time being let's be consistent.

40

This should be called __fn so that it shows up consistently to other CPOs in compiler diagnostics.

[• Quuxplusone]

libcxx/include/__memory/ranges_uninitialized_algorithms.h

33

(FWIW, I'd still prefer not to expand the sphere of influence of __function_like in this PR; but we're all on the same page that it's going to be trivial to remove later. I hope this is also taken as another bit of evidence that having multiple competing conventions sucks, and that consistency saves brain cells.)

38

(I added an _ns suffix to the namespace name to make sure it's different from the name of the helper functions).

(1) please don't add that suffix; (2) what helper functions do you mean? Are you talking about std::__uninitialized_default_construct? It's not std::ranges::__uninitialized_default_construct, so we don't need to worry about this namespace colliding with it. Again, we have an established convention already and you're being asked to copy it so that we have one convention used everywhere, instead of multiple conventions.

We could (in a separate PR) change libc++'s convention to use names like std::ranges::__cpo_detail::__uninitialized_default_construct_fn instead of std::ranges::__uninitialized_default_construct::__fn, but that benefits us literally nothing AFAICT and costs us a few bytes per symbol name (which translates to potentially lots of .o file size on disk).

can you please elaborate on how this could be a problem

https://godbolt.org/z/4c16P3YGK

[var-const]

Review feedback

libcxx/include/__memory/ranges_uninitialized_algorithms.h

38

Removed the suffix.

Are you talking about std::__uninitialized_default_construct? It's not std::ranges::__uninitialized_default_construct, so we don't need to worry about this namespace colliding with it.

Yes, I mean (potential) confusion for the reader, not for the compiler. Changed to follow the convention.

https://godbolt.org/z/4c16P3YGK

Thanks! When I first thought about it, I presumed that RandomFunction would have to be __RandomFunction in our case, but now I see that it's not necessarily true.

40

Done, thanks. Also added a TODO to change the other few places which don't follow the convention.

[• Quuxplusone]

Looks good to me at this point!

libcxx/include/__iterator/advance.h

72

And put it in the __advance namespace, and put advance into inline namespace __cpo; and remove __function_like. :) If you're volunteering for this, I will be thrilled to review it. :)

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp

91

Ack; OK if you leave this TODO comment as-is.
For the record, though, re "the linked code can change and the comment becomes stale": the benefit of wording the comment as "make consistent with [linked code]" is that even if the linked code does change, the comment remains correct! (Unless the linked code changes to match this code. ;)) A comment like "Here we should take approach X" might rot (if tomorrow we standardize on approach Y), but "Here we should be consistent and take the same approach as our neighbor" is evergreen.

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct.pass.cpp

211–212

Nit: Using the name capacity here instead of size is weird (compare to vector.size/capacity); but also can we just say 5 to sidestep the whole issue? (Applies throughout, I guess.)

219–222

FWIW, if you want, and if you rename Buffer.cbegin/cend to begin const/end const so that Buffer becomes more range-ish, then this can just be

std::ranges::uninitialized_default_construct(std::as_const(buf));

[var-const]

Address feedback, try to fix the CI.

libcxx/include/__iterator/advance.h

72

Thanks, I plan to do this cleanup before the end of the week.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp

91

Sorry, I should have elaborated a bit more -- the kind of change I was thinking about is if the linked code was moved around (e.g. imagine in the future the code that checks CPO object properties is consolidated in a single file -- then the reader won't find anything in the test file that is "linked" here and would have to go dig through history to figure out what the comment was referring to).

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct.pass.cpp

211–212

Created a constant instead.

Regarding the naming issue: my initial thought was that what capacity returns essentially is just raw capacity, not size. The buffer allocates enough space for N elements, but it doesn't keep track of how many elements are actually created, which is what I would expect size to return.

OTOH, size in the vector sense arguably is inapplicable for Buffer because Buffer allows random access to all the N elements -- e.g. for a 5-element buffer, it's valid to have elements [1] and [3] initialized and everything else uninitialized, and there isn't really a way to capture that information as size.

Now that I think of it, it seems like std::array is a better model for Buffer than vector, and array uses size, not capacity.

219–222

Thanks! I'll experiment with this in the follow-up I'm working on.

libcxx/docs/Status/RangesPaper.csv

 Section,Description,Dependencies,Assignee,Complete
 [tuple.helper],Update <tuple> includes.,None,Unassigned,Not started
 `[range.cmp] <http://wg21.link/range.cmp>`_,"| `ranges::equal_to <https://llvm.org/D100429>`_
 | `ranges::not_equal_to <https://llvm.org/D100429>`_
 | `ranges::less <https://llvm.org/D100429>`_
 | `ranges::greater <https://llvm.org/D100429>`_
 | `ranges::less_equal <https://llvm.org/D100429>`_
 | `ranges::greater_equal <https://llvm.org/D100429>`_",None,Zoe Carver,✅
 `[readable.traits] <http://wg21.link/readable.traits>`_,"| `indirectly_readable_traits <https://llvm.org/D99461>`_
 | `iter_value_t <https://llvm.org/D99863>`_",None,Christopher Di Bella,✅
 `[incrementable.traits] <http://wg21.link/incrementable.traits>`_,"| `incrementable_traits <https://llvm.org/D99141>`_
 | `iter_difference_t <https://llvm.org/D99863>`_",,Christopher Di Bella,✅
 `[iterator.traits] <http://wg21.link/iterator.traits>`_,`Updates to iterator_traits <https://llvm.org/D99855>`_,"| indirectly_readable_traits
 | incrementable_traits",Christopher Di Bella,✅
-`[special.mem.concepts] <http://wg21.link/special.mem.concepts>`_,"| *no-throw-input-iterator*
-| *no-throw-sentinel-for*
-| *no-throw-input-range*
-| *no-throw-forward-iterator*
-| *no-throw-forward-range*","| [iterator.concepts]
+`[special.mem.concepts] <http://wg21.link/special.mem.concepts>`_,"| *nothrow-input-iterator*
+| *nothrow-sentinel-for*
+| *nothrow-input-range*
+| *nothrow-forward-iterator*
+| *nothrow-forward-range*","| [iterator.concepts]
 | [range.refinements]",Konstantin Varlamov,✅
-`[specialized.algorithms] <http://wg21.link/specialized.algorithms>`_,"| ranges::uninitialized_default_construct
-| ranges::uninitialized_default_construct_n
+`[specialized.algorithms] <http://wg21.link/specialized.algorithms>`_,"| `ranges::uninitialized_default_construct <https://llvm.org/D115315>`
+| `ranges::uninitialized_default_construct_n <https://llvm.org/D115315>`
 | ranges::uninitialized_value_construct
 | ranges::uninitialized_value_construct_n
 | ranges::uninitialized_copy
 | ranges::uninitialized_copy_n
 | ranges::uninitialized_move
 | ranges::uninitialized_move_n
 | ranges::uninitialized_fill
 | ranges::uninitialized_fill_n
 | ranges::construct_at
 | ranges::destroy
 | ranges::destroy_at
-| ranges::destroy_n",[special.mem.concepts],Konstantin Varlamov,Not started
+| ranges::destroy_n",[special.mem.concepts],Konstantin Varlamov,In progress
 [strings],Adds begin/end and updates const_iterator.,[iterator.concepts],Unassigned,Not started
 [views.span],Same as [strings],[iterator.concepts],Unassigned,Not started
 `[iterator.cust.move] <http://wg21.link/iterator.cust.move>`_,`ranges::iter_move <https://llvm.org/D99873>`_,,Zoe Carver,✅
 `[iterator.cust.swap] <http://wg21.link/iterator.cust.swap>`_,`ranges::iter_swap <https://llvm.org/D102809>`_,iter_value_t,Zoe Carver,✅
 `[iterator.concepts] <http://wg21.link/iterator.concepts>`_,"| `indirectly_readable <https://llvm.org/D100073>`_
 | `indirectly_writable <https://llvm.org/D100073>`_
 | `weakly_incrementable <https://llvm.org/D100080>`_
 | `incrementable <https://llvm.org/D100080>`_

libcxx/include/CMakeLists.txt

set(files
   __memory/allocator_arg_t.h
   __memory/allocator_traits.h
   __memory/allocator.h
   __memory/auto_ptr.h
   __memory/compressed_pair.h
   __memory/concepts.h
   __memory/construct_at.h
   __memory/pointer_traits.h
+  __memory/ranges_uninitialized_algorithms.h
   __memory/raw_storage_iterator.h
   __memory/shared_ptr.h
   __memory/temporary_buffer.h
   __memory/uninitialized_algorithms.h
   __memory/unique_ptr.h
   __memory/uses_allocator.h
   __mutex_base
   __numeric/accumulate.h

libcxx/include/__iterator/advance.h

_LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
                  "Attempt to advance(it, n) with negative n on a non-bidirectional iterator");
   _VSTD::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
 }
 
 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
 namespace ranges {
 // [range.iter.op.advance]
+// TODO(varconst): rename `__advance_fn` to `__fn`.
 struct __advance_fn final : private __function_like {
 private:
   template <class _Tp>
   _LIBCPP_HIDE_FROM_ABI
   static constexpr _Tp __magnitude_geq(_Tp __a, _Tp __b) noexcept {
     return __a < 0 ? (__a <= __b) : (__a >= __b);
   }
 

libcxx/include/__iterator/next.h

inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 
   _VSTD::advance(__x, __n);
   return __x;
 }
 
 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
 namespace ranges {
+// TODO(varconst): rename `__next_fn` to `__fn`.
 struct __next_fn final : private __function_like {
   _LIBCPP_HIDE_FROM_ABI
   constexpr explicit __next_fn(__tag __x) noexcept : __function_like(__x) {}
 
   template <input_or_output_iterator _Ip>
   _LIBCPP_HIDE_FROM_ABI
   constexpr _Ip operator()(_Ip __x) const {
     ++__x;

libcxx/include/__iterator/prev.h

_LIBCPP_ASSERT(__n <= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
                  "Attempt to prev(it, n) with a positive n on a non-bidirectional iterator");
   _VSTD::advance(__x, -__n);
   return __x;
 }
 
 #if !defined(_LIBCPP_HAS_NO_RANGES)
 
 namespace ranges {
+// TODO(varconst): rename `__prev_fn` to `__fn`.
 struct __prev_fn final : private __function_like {
   _LIBCPP_HIDE_FROM_ABI
   constexpr explicit __prev_fn(__tag __x) noexcept : __function_like(__x) {}
 
   template <bidirectional_iterator _Ip>
   _LIBCPP_HIDE_FROM_ABI
   constexpr _Ip operator()(_Ip __x) const {
     --__x;

libcxx/include/__memory/ranges_uninitialized_algorithms.h

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// 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___MEMORY_RANGES_UNINITIALIZED_ALGORITHMS_H
+#define _LIBCPP___MEMORY_RANGES_UNINITIALIZED_ALGORITHMS_H
+
+#include <__concepts/constructible.h>
+#include <__config>
+#include <__function_like.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/readable_traits.h>
+#include <__memory/concepts.h>
+#include <__memory/uninitialized_algorithms.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <type_traits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+namespace ranges {
+
+// uninitialized_default_construct
+
+namespace __uninitialized_default_construct {
+
+struct __fn final : private __function_like {
+
+  constexpr explicit __fn(__tag __x) noexcept : __function_like(__x) {}
+
+  template <__nothrow_forward_iterator _ForwardIterator,
+            __nothrow_sentinel_for<_ForwardIterator> _Sentinel>
+    requires default_initializable<iter_value_t<_ForwardIterator>>
+  _ForwardIterator operator()(_ForwardIterator __first, _Sentinel __last) const {
+    using _ValueType = remove_reference_t<iter_reference_t<_ForwardIterator>>;
+    return _VSTD::__uninitialized_default_construct<_ValueType>(__first, __last);
+  }
+
+  template <__nothrow_forward_range _ForwardRange>
+    requires default_initializable<range_value_t<_ForwardRange>>
+  borrowed_iterator_t<_ForwardRange> operator()(_ForwardRange&& __range) const {
+    return (*this)(ranges::begin(__range), ranges::end(__range));
+  }
+
+};
+
+} // namespace __uninitialized_default_construct_ns
+
+inline namespace __cpo {
+inline constexpr auto uninitialized_default_construct =
+    __uninitialized_default_construct::__fn(__function_like::__tag());
+} // namespace __cpo
+
+// uninitialized_default_construct_n
+
+namespace __uninitialized_default_construct_n {
+
+struct __fn final : private __function_like {
+
+  constexpr explicit __fn(__tag __x) noexcept :
+      __function_like(__x) {}
+
+  template <__nothrow_forward_iterator _ForwardIterator>
+    requires default_initializable<iter_value_t<_ForwardIterator>>
+  _ForwardIterator operator()(_ForwardIterator __first,
+                              iter_difference_t<_ForwardIterator> __n) const {
+    using _ValueType = remove_reference_t<iter_reference_t<_ForwardIterator>>;
+    return _VSTD::__uninitialized_default_construct_n<_ValueType>(__first, __n);
+  }
+
+};
+
+} // namespace __uninitialized_default_construct_n_ns
+
+inline namespace __cpo {
+inline constexpr auto uninitialized_default_construct_n =
+    __uninitialized_default_construct_n::__fn(__function_like::__tag());
+} // namespace __cpo
+
+} // namespace ranges
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___MEMORY_RANGES_UNINITIALIZED_ALGORITHMS_H

libcxx/include/__memory/uninitialized_algorithms.h

catch (...)
         throw;
     }
 #endif
     return __f;
 }
 
 #if _LIBCPP_STD_VER > 14
 
-template <class _ForwardIterator>
-inline _LIBCPP_INLINE_VISIBILITY
-void uninitialized_default_construct(_ForwardIterator __first, _ForwardIterator __last) {
-    using _Vt = typename iterator_traits<_ForwardIterator>::value_type;
+// uninitialized_default_construct
+
+template <class _ValueType, class _ForwardIterator, class _Sentinel>
+inline _LIBCPP_HIDE_FROM_ABI
+_ForwardIterator __uninitialized_default_construct(_ForwardIterator __first, _Sentinel __last) {
     auto __idx = __first;
 #ifndef _LIBCPP_NO_EXCEPTIONS
     try {
 #endif
     for (; __idx != __last; ++__idx)
-        ::new ((void*)_VSTD::addressof(*__idx)) _Vt;
+        ::new ((void*)_VSTD::addressof(*__idx)) _ValueType;
 #ifndef _LIBCPP_NO_EXCEPTIONS
     } catch (...) {
         _VSTD::destroy(__first, __idx);
         throw;
     }
 #endif
+
+    return __idx;
 }
 
-template <class _ForwardIterator, class _Size>
+template <class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
-_ForwardIterator uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {
-    using _Vt = typename iterator_traits<_ForwardIterator>::value_type;
+void uninitialized_default_construct(_ForwardIterator __first, _ForwardIterator __last) {
+    using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
+    (void)_VSTD::__uninitialized_default_construct<_ValueType>(__first, __last);
+}
+
+// uninitialized_default_construct_n
+
+template <class _ValueType, class _ForwardIterator, class _Size>
+inline _LIBCPP_HIDE_FROM_ABI
+_ForwardIterator __uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {
     auto __idx = __first;
 #ifndef _LIBCPP_NO_EXCEPTIONS
     try {
 #endif
     for (; __n > 0; ++__idx, (void) --__n)
-        ::new ((void*)_VSTD::addressof(*__idx)) _Vt;
-    return __idx;
+        ::new ((void*)_VSTD::addressof(*__idx)) _ValueType;
 #ifndef _LIBCPP_NO_EXCEPTIONS
     } catch (...) {
         _VSTD::destroy(__first, __idx);
         throw;
     }
 #endif
+
+    return __idx;
 }
 
+template <class _ForwardIterator, class _Size>
+inline _LIBCPP_INLINE_VISIBILITY
+_ForwardIterator uninitialized_default_construct_n(_ForwardIterator __first, _Size __n) {
+    using _ValueType = typename iterator_traits<_ForwardIterator>::value_type;
+    return _VSTD::__uninitialized_default_construct_n<_ValueType>(__first, __n);
+}
 
 template <class _ForwardIterator>
 inline _LIBCPP_INLINE_VISIBILITY
 void uninitialized_value_construct(_ForwardIterator __first, _ForwardIterator __last) {
     using _Vt = typename iterator_traits<_ForwardIterator>::value_type;
     auto __idx = __first;
 #ifndef _LIBCPP_NO_EXCEPTIONS
     try {

libcxx/include/memory

  void uninitialized_value_construct(ForwardIterator first, ForwardIterator last);
 
 template <class ForwardIterator, class Size>
  ForwardIterator uninitialized_value_construct_n(ForwardIterator first, Size n);
 
 template <class ForwardIterator>
  void uninitialized_default_construct(ForwardIterator first, ForwardIterator last);
 
+template <nothrow-forward-iterator ForwardIterator, nothrow-sentinel-for<ForwardIterator> Sentinel>
+  requires default_initializable<iter_value_t<ForwardIterator>>
+ ForwardIterator ranges::uninitialized_default_construct(ForwardIterator first, Sentinel last); // since C++20
+
+template <nothrow-forward-range ForwardRange>
+  requires default_initializable<range_value_t<ForwardRange>>
+ borrowed_iterator_t<ForwardRange> ranges::uninitialized_default_construct(ForwardRange&& r); // since C++20
+
 template <class ForwardIterator, class Size>
  ForwardIterator uninitialized_default_construct_n(ForwardIterator first, Size n);
 
+template <nothrow-forward-iterator ForwardIterator>
+  requires default_initializable<iter_value_t<ForwardIterator>>
+ ForwardIterator ranges::uninitialized_default_construct_n(ForwardIterator first, iter_difference_t<ForwardIterator> n); // since C++20
+
 template <class Y> struct auto_ptr_ref {};      // deprecated in C++11, removed in C++17
 
 template<class X>
 class auto_ptr                                  // deprecated in C++11, removed in C++17
 {
 public:
     typedef X element_type;
 

 #include <__memory/allocation_guard.h>
 #include <__memory/allocator.h>
 #include <__memory/allocator_arg_t.h>
 #include <__memory/allocator_traits.h>
 #include <__memory/compressed_pair.h>
 #include <__memory/concepts.h>
 #include <__memory/construct_at.h>
 #include <__memory/pointer_traits.h>
+#include <__memory/ranges_uninitialized_algorithms.h>
 #include <__memory/raw_storage_iterator.h>
 #include <__memory/shared_ptr.h>
 #include <__memory/temporary_buffer.h>
 #include <__memory/uninitialized_algorithms.h>
 #include <__memory/unique_ptr.h>
 #include <__memory/uses_allocator.h>
 #include <compare>
 #include <cstddef>

libcxx/include/module.modulemap

module map {
     export initializer_list
     export *
   }
   module memory {
     header "memory"
     export *
 
     module __memory {
-      module addressof                { private header "__memory/addressof.h" }
-      module allocation_guard         { private header "__memory/allocation_guard.h" }
-      module allocator                { private header "__memory/allocator.h" }
-      module allocator_arg_t          { private header "__memory/allocator_arg_t.h" }
-      module allocator_traits         { private header "__memory/allocator_traits.h" }
-      module auto_ptr                 { private header "__memory/auto_ptr.h" }
-      module compressed_pair          { private header "__memory/compressed_pair.h" }
-      module concepts                 { private header "__memory/concepts.h" }
-      module construct_at             { private header "__memory/construct_at.h" }
-      module pointer_traits           { private header "__memory/pointer_traits.h" }
-      module raw_storage_iterator     { private header "__memory/raw_storage_iterator.h" }
-      module shared_ptr               { private header "__memory/shared_ptr.h" }
-      module temporary_buffer         { private header "__memory/temporary_buffer.h" }
-      module uninitialized_algorithms { private header "__memory/uninitialized_algorithms.h" }
-      module unique_ptr               { private header "__memory/unique_ptr.h" }
-      module uses_allocator           { private header "__memory/uses_allocator.h" }
+      module addressof                       { private header "__memory/addressof.h" }
+      module allocation_guard                { private header "__memory/allocation_guard.h" }
+      module allocator                       { private header "__memory/allocator.h" }
+      module allocator_arg_t                 { private header "__memory/allocator_arg_t.h" }
+      module allocator_traits                { private header "__memory/allocator_traits.h" }
+      module auto_ptr                        { private header "__memory/auto_ptr.h" }
+      module compressed_pair                 { private header "__memory/compressed_pair.h" }
+      module concepts                        { private header "__memory/concepts.h" }
+      module construct_at                    { private header "__memory/construct_at.h" }
+      module pointer_traits                  { private header "__memory/pointer_traits.h" }
+      module ranges_uninitialized_algorithms {
+        private header "__memory/ranges_uninitialized_algorithms.h"
+        export __function_like
+      }
+      module raw_storage_iterator            { private header "__memory/raw_storage_iterator.h" }
+      module shared_ptr                      { private header "__memory/shared_ptr.h" }
+      module temporary_buffer                { private header "__memory/temporary_buffer.h" }
+      module uninitialized_algorithms        { private header "__memory/uninitialized_algorithms.h" }
+      module unique_ptr                      { private header "__memory/unique_ptr.h" }
+      module uses_allocator                  { private header "__memory/uses_allocator.h" }
     }
   }
   module mutex {
     header "mutex"
     export *
   }
   module new {
     header "new"
module __ranges {
       module all                    {
         private header "__ranges/all.h"
         export functional.__functional.compose
         export functional.__functional.perfect_forward
       }
       module common_view            { private header "__ranges/common_view.h" }
       module concepts               { private header "__ranges/concepts.h" }
       module copyable_box           { private header "__ranges/copyable_box.h" }
-      module counted                { private header "__ranges/counted.h" }
+      module counted                {
+        private header "__ranges/counted.h"
+        export span
+      }
       module dangling               { private header "__ranges/dangling.h" }
       module data                   { private header "__ranges/data.h" }
       module drop_view              { private header "__ranges/drop_view.h" }
       module empty                  { private header "__ranges/empty.h" }
       module empty_view             { private header "__ranges/empty_view.h" }
       module enable_borrowed_range  { private header "__ranges/enable_borrowed_range.h" }
       module enable_view            { private header "__ranges/enable_view.h" }
       module iota_view              { private header "__ranges/iota_view.h" }

libcxx/test/libcxx/diagnostics/detail.headers/memory/ranges_uninitialized_algorithms.module.verify.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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__memory/ranges_uninitialized_algorithms.h'}}
+#include <__memory/ranges_uninitialized_algorithms.h>

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/special_function.compile.pass.cpp

 }
 
 template <class I>
 void advance(forward_iterator<I>&, std::ptrdiff_t, forward_iterator<I>) {
   static_assert(std::same_as<I, I*>);
 }
 } // namespace test
 
+// TODO(varconst): simply check that `advance` is a variable and not a function.
 // When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
 // function call ([expr.call]), they inhibit argument-dependent name lookup.
 void adl_inhibition() {
   test::forward_iterator<int*> x;
 
   using std::ranges::advance;
   advance(x, 0);
   advance(x, x);
   advance(x, 0, x);
 }

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp

 }
 
 template <class I>
 void next(forward_iterator<I>, std::ptrdiff_t, forward_iterator<I>) {
   static_assert(std::same_as<I, I*>);
 }
 } // namespace test
 
+// TODO(varconst): simply check that `next` is a variable and not a function.
 // When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
 // function call ([expr.call]), they inhibit argument-dependent name lookup.
 void adl_inhibition() {
   test::forward_iterator<int*> x;
 
   using std::ranges::next;
 
   (void)next(x);
   (void)next(x, 5);
   (void)next(x, x);
   (void)next(x, 6, x);
 }

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/special_function.compile.pass.cpp

 }
 
 template <class I>
 void prev(bidirectional_iterator<I>, std::ptrdiff_t, bidirectional_iterator<I>) {
   static_assert(std::same_as<I, I*>);
 }
 } // namespace test
 
+// TODO(varconst): simply check that `prev` is a variable and not a function.
 // When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
 // function call ([expr.call]), they inhibit argument-dependent name lookup.
 void adl_inhibition() {
   test::bidirectional_iterator<int*> x;
 
   using std::ranges::prev;
 
   (void)prev(x);
   (void)prev(x, 5);
   (void)prev(x, 6, x);
 }

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts, libcpp-has-no-incomplete-ranges
+
+// <memory>
+
+// template <nothrow-forward-iterator ForwardIterator, nothrow-sentinel-for<ForwardIterator> Sentinel>
+//   requires default_initializable<iter_value_t<ForwardIterator>>
+// ForwardIterator ranges::uninitialized_default_construct(ForwardIterator first, Sentinel last);
+//
+// template <nothrow-forward-range ForwardRange>
+//   requires default_initializable<range_value_t<ForwardRange>>
+// borrowed_iterator_t<ForwardRange> ranges::uninitialized_default_construct(ForwardRange&& range);
+
+#include <cassert>
+#include <iterator>
+#include <memory>
+#include <ranges>
+#include <type_traits>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+struct Counted {
+  static int current_objects;
+  static int total_objects;
+  static int throw_on;
+
+  explicit Counted() {
+    if (throw_on == total_objects) {
+      TEST_THROW(1);
+    }
+
+    ++current_objects;
+    ++total_objects;
+  }
+
+  ~Counted() { --current_objects; }
+
+  static void reset() {
+    current_objects = total_objects = 0;
+    throw_on = -1;
+  }
+
+  Counted(Counted const&) = delete;
+  friend void operator&(Counted) = delete;
+};
+int Counted::current_objects = 0;
+int Counted::total_objects = 0;
+int Counted::throw_on = -1;
+
+template <typename T, int N>
+struct Buffer {
+  alignas(T) char buffer[sizeof(T) * N] = {};
+
+  T* begin() { return reinterpret_cast<T*>(buffer); }
+  T* end() { return begin() + N; }
+  const T* cbegin() const { return reinterpret_cast<const T*>(buffer); }
+  const T* cend() const { return cbegin() + N; }
+};
+
+// Because this is a variable and not a function, it's guaranteed that ADL won't be used. However,
+// implementations are allowed to use a different mechanism to achieve this effect, so this check is
+// libc++-specific.
+LIBCPP_STATIC_ASSERT(std::is_class_v<decltype(std::ranges::uninitialized_default_construct)>);
+
+struct NotDefaultCtrable { NotDefaultCtrable() = delete; };
+static_assert(!std::is_invocable_v<decltype(std::ranges::uninitialized_default_construct),
+    NotDefaultCtrable*, NotDefaultCtrable*>);
+
+int main(int, char**) {
+  // An empty range -- no default constructors should be invoked.
+  {
+    Buffer<Counted, 1> buf;
+
+    std::ranges::uninitialized_default_construct(buf.begin(), buf.begin());
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == 0);
+
+    std::ranges::uninitialized_default_construct(std::ranges::empty_view<Counted>());
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == 0);
+
+    forward_iterator<Counted*> it(buf.begin());
+    auto range = std::ranges::subrange(it, sentinel_wrapper<forward_iterator<Counted*>>(it));
+    std::ranges::uninitialized_default_construct(range.begin(), range.end());
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == 0);
+
+    std::ranges::uninitialized_default_construct(range);
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == 0);
+  }
+
+  // A range containing several objects, (iter, sentinel) overload.
+  {
+    constexpr int N = 5;
+    Buffer<Counted, 5> buf;
+
+    std::ranges::uninitialized_default_construct(buf.begin(), buf.end());
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+
+    std::destroy(buf.begin(), buf.end());
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == N);
+    Counted::reset();
+  }
+
+  // A range containing several objects, (range) overload.
+  {
+    constexpr int N = 5;
+    Buffer<Counted, N> buf;
+
+    auto range = std::ranges::subrange(buf.begin(), buf.end());
+    std::ranges::uninitialized_default_construct(range);
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+
+    std::destroy(buf.begin(), buf.end());
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == N);
+    Counted::reset();
+  }
+
+  // Using `counted_iterator`.
+  {
+    constexpr int N = 3;
+    Buffer<Counted, 5> buf;
+
+    std::ranges::uninitialized_default_construct(
+        std::counted_iterator(buf.begin(), N), std::default_sentinel);
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+
+    std::destroy(buf.begin(), buf.begin() + N);
+    Counted::reset();
+  }
+
+  // Using `views::counted`.
+  {
+    constexpr int N = 3;
+    Buffer<Counted, 5> buf;
+
+    auto counted_range = std::views::counted(buf.begin(), N);
+    std::ranges::uninitialized_default_construct(counted_range);
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+
+    std::destroy(buf.begin(), buf.begin() + N);
+    Counted::reset();
+  }
+
+  // Using `reverse_view`.
+  {
+    constexpr int N = 3;
+    Buffer<Counted, 5> buf;
+
+    auto range = std::ranges::subrange(buf.begin(), buf.begin() + N);
+    std::ranges::uninitialized_default_construct(std::ranges::reverse_view(range));
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+
+    std::destroy(buf.begin(), buf.begin() + N);
+    Counted::reset();
+  }
+
+  // An exception is thrown while objects are being created -- the existing objects should stay
+  // valid. (iterator, sentinel) overload.
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  {
+    Buffer<Counted, 5> buf;
+
+    Counted::throw_on = 3; // When constructing the fourth object (counting from one).
+    try {
+      std::ranges::uninitialized_default_construct(buf.begin(), buf.end());
+    } catch(...) {}
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == 3);
+    std::destroy(buf.begin(), buf.begin() + Counted::total_objects);
+    Counted::reset();
+  }
+
+  // An exception is thrown while objects are being created -- the existing objects should stay
+  // valid. (range) overload.
+  {
+    Buffer<Counted, 5> buf;
+
+    Counted::throw_on = 3; // When constructing the fourth object.
+    try {
+      auto range = std::ranges::subrange(buf.begin(), buf.end());
+      std::ranges::uninitialized_default_construct(range);
+    } catch(...) {}
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == 3);
+    std::destroy(buf.begin(), buf.begin() + Counted::total_objects);
+    Counted::reset();
+  }
+#endif  // TEST_HAS_NO_EXCEPTIONS
+
+  // Works with const iterators, (iter, sentinel) overload.
+  {
+    constexpr int N = 5;
+    Buffer<Counted, N> buf;
+
+    std::ranges::uninitialized_default_construct(buf.cbegin(), buf.cend());
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+    std::destroy(buf.begin(), buf.end());
+    Counted::reset();
+  }
+
+  // Works with const iterators, (range) overload.
+  {
+    constexpr int N = 5;
+    Buffer<Counted, N> buf;
+    auto range = std::ranges::subrange(buf.cbegin(), buf.cend());
+
+    std::ranges::uninitialized_default_construct(range);
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+    std::destroy(buf.begin(), buf.end());
+    Counted::reset();
+  }
+
+  return 0;
+}

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/ranges_uninitialized_default_construct_n.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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts, libcpp-has-no-incomplete-ranges
+
+// <memory>
+
+// template <nothrow-forward-iterator ForwardIterator>
+//   requires default_initializable<iter_value_t<ForwardIterator>>
+// ForwardIterator ranges::uninitialized_default_construct_n(ForwardIterator first,
+//     iter_difference_t<ForwardIterator> n);
+
+#include <cassert>
+#include <memory>
+#include <ranges>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+struct Counted {
+  static int current_objects;
+  static int total_objects;
+  static int throw_on;
+
+  explicit Counted() {
+    if (throw_on == total_objects) {
+      TEST_THROW(1);
+    }
+
+    ++current_objects;
+    ++total_objects;
+  }
+
+  ~Counted() { --current_objects; }
+
+  static void reset() {
+    current_objects = total_objects = 0;
+    throw_on = -1;
+  }
+
+  Counted(Counted const&) = delete;
+  friend void operator&(Counted) = delete;
+};
+int Counted::current_objects = 0;
+int Counted::total_objects = 0;
+int Counted::throw_on = -1;
+
+template <typename T, int N>
+struct Buffer {
+  alignas(T) char buffer[sizeof(T) * N] = {};
+
+  T* begin() { return reinterpret_cast<T*>(buffer); }
+  T* end() { return begin() + N; }
+  const T* cbegin() const { return reinterpret_cast<const T*>(buffer); }
+  const T* cend() const { return cbegin() + N; }
+};
+
+// Because this is a variable and not a function, it's guaranteed that ADL won't be used. However,
+// implementations are allowed to use a different mechanism to achieve this effect, so this check is
+// libc++-specific.
+LIBCPP_STATIC_ASSERT(std::is_class_v<decltype(std::ranges::uninitialized_default_construct_n)>);
+
+struct NotDefaultCtrable { NotDefaultCtrable() = delete; };
+static_assert(!std::is_invocable_v<decltype(std::ranges::uninitialized_default_construct_n),
+    NotDefaultCtrable*, int>);
+
+int main(int, char**) {
+  // An empty range -- no default constructors should be invoked.
+  {
+    Buffer<Counted, 1> buf;
+
+    std::ranges::uninitialized_default_construct_n(buf.begin(), 0);
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == 0);
+  }
+
+  // A range containing several objects.
+  {
+    constexpr int N = 5;
+    Buffer<Counted, N> buf;
+
+    std::ranges::uninitialized_default_construct_n(buf.begin(), N);
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+
+    std::destroy(buf.begin(), buf.end());
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == N);
+    Counted::reset();
+  }
+
+  // An exception is thrown while objects are being created -- the existing objects should stay
+  // valid.
+#ifndef TEST_HAS_NO_EXCEPTIONS
+  {
+    constexpr int N = 5;
+    Buffer<Counted, N> buf;
+
+    Counted::throw_on = 3; // When constructing the fourth object (counting from one).
+    try {
+      std::ranges::uninitialized_default_construct_n(buf.begin(), N);
+    } catch(...) {}
+    assert(Counted::current_objects == 0);
+    assert(Counted::total_objects == 3);
+    std::destroy(buf.begin(), buf.begin() + Counted::total_objects);
+    Counted::reset();
+  }
+#endif  // TEST_HAS_NO_EXCEPTIONS
+
+  // Works with const iterators.
+  {
+    constexpr int N = 5;
+    Buffer<Counted, N> buf;
+
+    std::ranges::uninitialized_default_construct_n(buf.cbegin(), N);
+    assert(Counted::current_objects == N);
+    assert(Counted::total_objects == N);
+    std::destroy(buf.begin(), buf.end());
+    Counted::reset();
+  }
+
+  return 0;
+}

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/uninitialized_default_construct.pass.cpp

 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
 struct Counted {
   static int count;
   static int constructed;
-  static void reset() { count = constructed =  0; }
   explicit Counted() { ++count; ++constructed; }
   Counted(Counted const&) { assert(false); }
   ~Counted() { --count; }
   friend void operator&(Counted) = delete;
 };
 int Counted::count = 0;
 int Counted::constructed = 0;
 
 
 struct ThrowsCounted {
   static int count;
   static int constructed;
   static int throw_after;
-  static void reset() { throw_after = count = constructed =  0; }
   explicit ThrowsCounted() {
       ++constructed;
       if (throw_after > 0 && --throw_after == 0) {
           TEST_THROW(1);
       }
       ++count;
   }
   ThrowsCounted(ThrowsCounted const&) { assert(false); }
#ifndef TEST_HAS_NO_EXCEPTIONS
     alignas(ThrowsCounted) char pool[sizeof(ThrowsCounted)*N] = {};
     ThrowsCounted* p = (ThrowsCounted*)pool;
     try {
         ThrowsCounted::throw_after = 4;
         std::uninitialized_default_construct(It(p), It(p+N));
         assert(false);
     } catch (...) {}
     assert(ThrowsCounted::count == 0);
-    assert(ThrowsCounted::constructed == 4); // forth construction throws
+    assert(ThrowsCounted::constructed == 4); // Fourth construction throws
 #endif
 }
 
 void test_counted()
 {
     using It = forward_iterator<Counted*>;
     const int N = 5;
     alignas(Counted) char pool[sizeof(Counted)*N] = {};
     Counted* p = (Counted*)pool;
     std::uninitialized_default_construct(It(p), It(p+1));
     assert(Counted::count == 1);
     assert(Counted::constructed == 1);
     std::uninitialized_default_construct(It(p+1), It(p+N));
     assert(Counted::count == 5);
     assert(Counted::constructed == 5);
     std::destroy(p, p+N);
     assert(Counted::count == 0);
 }
 
-void test_value_initialized()
-{
-    using It = forward_iterator<int*>;
-    const int N = 5;
-    int pool[N] = {-1, -1, -1, -1, -1};
-    int* p = pool;
-    std::uninitialized_default_construct(It(p), It(p+1));
-    assert(pool[0] == -1);
-    assert(pool[1] == -1);
-    std::uninitialized_default_construct(It(p+1), It(p+N));
-    assert(pool[1] == -1);
-    assert(pool[2] == -1);
-    assert(pool[3] == -1);
-    assert(pool[4] == -1);
-}
-
 int main(int, char**)
 {
     test_counted();
-    test_value_initialized();
     test_ctor_throws();
 
   return 0;
 }

libcxx/test/std/utilities/memory/specialized.algorithms/uninitialized.construct.default/uninitialized_default_construct_n.pass.cpp

void test_counted()
     e = std::uninitialized_default_construct_n(It(p+1), 4);
     assert(e == It(p+N));
     assert(Counted::count == 5);
     assert(Counted::constructed == 5);
     std::destroy(p, p+N);
     assert(Counted::count == 0);
 }
 
-void test_value_initialized()
-{
-    using It = forward_iterator<int*>;
-    const int N = 5;
-    int pool[N] = {-1, -1, -1, -1, -1};
-    int* p = pool;
-    auto e = std::uninitialized_default_construct_n(It(p), 1);
-    assert(e == It(p+1));
-    assert(pool[0] == -1);
-    assert(pool[1] == -1);
-    e = std::uninitialized_default_construct_n(It(p+1), 4);
-    assert(e == It(p+N));
-    assert(pool[1] == -1);
-    assert(pool[2] == -1);
-    assert(pool[3] == -1);
-    assert(pool[4] == -1);
-}
-
-
 int main(int, char**)
 {
     test_counted();
-    test_value_initialized();
     test_ctor_throws();
 
   return 0;
 }