[libcxx][ranges] Adds `common_iterator`.

[zoecarver]

• Diff on correct commit.

[zoecarver]

libcxx/include/__iterator/common_iterator.h

100

Note: all of these constexprs aren't required by the standard, but I'm filing an lwg issue for it.

[zoecarver]

Remove unneeded comment.

[cjdb]

libcxx/include/__iterator/common_iterator.h

100

Please link the issue in this PR before submitting (it doesn't need to be in the patch itself).

[zoecarver]

Update the status document.

[cjdb]

libcxx/include/__iterator/common_iterator.h

42–44

Default sentinel deserves its own (tiny) patch.

[tcanens]

libcxx/include/__iterator/common_iterator.h

53

This isn't going to work if either of them has a non-trivial special member function.

The exposition-only variant really solved a lot of problems in the specification that this will need to solve again.

[zoecarver]

• I think I adressed all the review comments that apply from the other two views. (If not, sorry, let me know and I'll fix them here too.)
• I'm going to update common_iterator to use variant. Because it's not yet constexpr, I'm just going to comment out the static_assert in all the tests. This makes us support closer to the standard anyway. Note: I have not done this yet because it requries fixing a dependency cycle between iterator -> array -> variant -> iterator.

[zoecarver]

libcxx/test/std/iterators/predef.iterators/iterators.common/members.pass.cpp

1 ↗

(On Diff #356841)

Oops, I can delete this now that it's tested elsewhere.

libcxx/test/support/test_iterators.h

165

I think this will be a very helpful type to have now that we need to test the default constructibility of all our views/iterators.

[ldionne]

libcxx/include/__iterator/common_iterator.h

34–42

Reminder that this should be using std::variant.

100

I think we should not make them constexpr until the LWG issue has been accepted and resolved. I strongly suspect the reason why they are not constexpr is that the type is expected to use variant, which isn't constexpr yet. You can structure the tests so that constexpr is easy to test when we add it, but please don't add it in the implementation yet.

116

http://eel.is/c++draft/iterators.common#common.iter.nav-5 says:

Otherwise, if requires (I& i) { { *i++ } -> can-reference; } is true or constructible_­from<iter_­value_­t<I>, iter_­reference_­t<I>> && move_­constructible<iter_­value_­t<I>> is false, equivalent to: return get<I>(v_)++;

We're missing && move_constructible<...> here?

119

This should be __postfix_proxy __p(**this); (double-dereference to get the value pointed-to by the iterator).

It also means you have a hole in your coverage since your tests were passing, i.e. this branch of the if constexpr was never exercised. Please make sure all branches of the if constexpr are exercised (here and in operator-> above too).

libcxx/test/std/iterators/predef.iterators/iterators.common/arrow.pass.cpp

27

Here and for operator++(int), I'd like you to explicitly call out which part is testing each sub-bullet in the spec (which maps to the if constexpr in the implementation).

libcxx/test/std/iterators/predef.iterators/iterators.common/assign.pass.cpp

31

You have a typo in sentienl_type.

libcxx/test/support/test_iterators.h

165

I agree, but I would instead call it something like non_default_constructible_iterator. Or whatever you prefer, but I think it's important for the name to reflect the fact that it's an iterator.

171

Shouldn't this be std::iterator_traits<It>::iterator_category? Actually, we could perhaps do this instead:

template<class It>
struct std::iterator_traits<no_default_constructor<It>> : std::iterator_traits<It> { };

Then, could we simply drop all the typedefs in no_default_constructor?

[zoecarver]

libcxx/include/__iterator/common_iterator.h

116

Good catch. It looks like this was recently changed.

119

Yes.. you're right. I thought that value_iterator was testing this, but apparently not.

I guess the type I need here is one where i is a __referenceable iterator and ++i is a __referenceable iterator, but i++ is void or something? Arg. OK.

libcxx/test/support/test_iterators.h

171

No, because we only provide members such that this is a forward iterator. For example, this is used mostly with pointer types. If we did what you're suggesting these would report that they were contiguous_iterators, but they are not (they're not even bidirectional).

[• Quuxplusone]

libcxx/test/support/test_iterators.h

171

Turn this inside out.

template<class T>
class NonDefCtablePtr {
    T *p_;
public:
    using iterator_category = std::random_access_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    [...]
    constexpr NonDefCtablePtr(T *p) : p_(p) {}
    constexpr T& operator*() const { return *p_; }
    [...]
    friend constexpr T *base(NonDefCtablePtr p) { return p.p_; }
};

and then in your test cases, use

#include "test_iterator.h"

test<bidirectional_iterator<int*>>();  // bidirectional, default-constructible
test<bidirectional_iterator<NonDefCtablePtr<int>>>();  // bidirectional, non-default-constructible

That is, we already have the iterator wrapper types in order to "downgrade" int* to forward/bidirectional/random-access level. So your NonDefCtable type should not "downgrade." It should just be contiguous, and then if someone wants a downgraded version, they can wrap it in one of the downgrade wrappers.

[zoecarver]

libcxx/include/__iterator/common_iterator.h

116

OK I added a test, but I'd like someone to verify it's correct. See my other comment.

[zoecarver]

Apply review comments.

[zoecarver]

Rebase.

[zoecarver]

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

88

@tcanens and others, is this correct? It seems like this goes against the other logic here (isn't the whole point to make sure that operator++ always returns a referencable type)?

[tcanens]

libcxx/include/__iterator/common_iterator.h

41

Missing move here.

54

Missing forward here.

71

variant does not have heterogeneous conversions of this sort.

77

Likewise.

80–83

It's undefined if it is holding the wrong type, so the check-and-throw get performs is unnecessary (and hurts performance). There should be a way to avoid such checks.

124

__y's sentinel type is _S2, not _Sent. Ditto below.

There seems to be a lack of test coverage here.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

88

Yes, common_iterator does its best to return something from postfix ++ that meets the C++17 input iterator requirements.

But hitting this case means that it doesn't know a way to produce anything meaningful, so it just gives up.

libcxx/test/support/test_iterators.h

171

Something that's not default constructible can't be anything more than input.

[zoecarver]

libcxx/include/__iterator/common_iterator.h

54

Why not move this one too?

libcxx/test/support/test_iterators.h

171

Not doing this because of Tim's comment. This is now an input iterator.

[zoecarver]

Apply Tim's comments and add a few more tests.

Thanks Tim!

[zoecarver]

Rebase.

[tcanens]

libcxx/include/__iterator/common_iterator.h

54

They are really both forwards; the difference is that operator->'s proxy only gets used when iter_reference_t<I> isn't a reference, so that forward ends up being a move.

[ldionne]

Comments per the over-the-shoulder review we just did.

libcxx/include/__iterator/common_iterator.h

32–39

This should be defined in <variant>.

Also, I would word the comment differently (because assertions are disabled in most builds):

__unchecked_get is the same as std::get, except, it is UB to use it with the wrong type [...]

93

I'm pretty sure this shouldn't even compile since we're passing the runtime __other.__hold_.index() as a non-type template argument, which expects a constant expression. This means that this isn't tested.

I can think of two ways of implementing this. First (pseudo-code):

__hold_([]() -> variant<_Iter, _Sent> {
  if (__other.__hold_.index() == 0) return {in_place_index<0>, __other.__hold_};
  else                                               return {in_place_index<1>, __other.__hold_};
  _LIBCPP_UNREACHABLE();
}())

The second way would be to use variant<monostate, _Iter, _Sent> and to "default-construct" the monostate when entering this constructor, and then do the if-else dance above in the constructor body. Otherwise, we'll have to default-construct one of the variant alternatives, which we don't want to do (BTW it would be awesome if you could add a test for that).

Pinging @mpark in case he has better ideas.

98

Could we add _LIBCPP_ASSERT(!__other.__hold_­.valueless_­by_­exception()) here since it's a precondition in the spec? Also in the other places where it applies.

100

This should be std::get<index>(__hold_) = std::get<index>(__other.__hold_);.

102

This is going to have the same problem as above, it won't compile. That means there's also a hole in our test coverage.

[ldionne]

libcxx/include/__iterator/common_iterator.h

106

Maybe add _LIBCPP_ASSERT(_VSTD::holds_­alternative<_Iter>(__hold_))?

115

Could you break that { onto a different line? It's kind of hard to see where the requires end and the function body begins.

146

Can we hoist the value of xxxx.index() into local variables? (here and below)

157

Please make sure you test all the branches below (here and in the other functions below too).

203–205

This would fit nicely on a single line IMO.

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

57

This doesn't look right. According to the spec (http://eel.is/c++draft/iterators.common#common.iter.types-1.3), this should either be the type of operator->() or void, but never Iter const&. This means you most likely have a bug in the implementation.

Also, please add a test where pointer ends up being void.

[zoecarver]

libcxx/include/__iterator/common_iterator.h

157

Added a few tests. Have verified all paths are taken.

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

57

This doesn't look right. According to the spec (http://eel.is/c++draft/iterators.common#common.iter.types-1.3), this should either be the type of operator->() or void, but never Iter const&. This means you most likely have a bug in the implementation.

Turns out this is actually correct. This is supposed to be the return type of common_iterator's operator->(). And if _Iter has an operator->() then it's supposed to simply return get<Iter>(v). (However, I'd argue that should maybe return get<Iter>(v).operator->(), if you agree, maybe I'll file an LWG issue.)

Sound good now? This threw me off too :P

57

Also, please add a test where pointer ends up being void.

Done.

[zoecarver]

Apply Louis' comments.

libcxx/include/__iterator/common_iterator.h

221

@cjdb thanks for helping me figure this one out :)

[tcanens]

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

57

This doesn't look right. According to the spec (http://eel.is/c++draft/iterators.common#common.iter.types-1.3), this should either be the type of operator->() or void, but never Iter const&. This means you most likely have a bug in the implementation.

Turns out this is actually correct. This is supposed to be the return type of common_iterator's operator->(). And if _Iter has an operator->() then it's supposed to simply return get<Iter>(v). (However, I'd argue that should maybe return get<Iter>(v).operator->(), if you agree, maybe I'll file an LWG issue.)

Producing decltype(a.operator->()) matches http://eel.is/c++draft/iterator.traits#1.sentence-3 but not the actual wording in http://eel.is/c++draft/iterators.common#common.iter.types-1.3 which says that it is the type of a.operator->(), aka remove_reference_t<decltype(a.operator->())>. What's the intent here @CaseyCarter?

[tcanens]

libcxx/include/__iterator/common_iterator.h

98

These should look at __other_idx - this assignment is valid even if *this is valueless.

273–275

This conditional_t seems unnecessary?

[ldionne]

libcxx/include/__iterator/common_iterator.h

79

This should be in the lambda above for it to trigger before we try to access __other.__hold_ unchecked.

93

I think you want _VSTD::__unchecked_get here and elsewhere.

98

Can you add a test where you assign to a common_iterator with a valueless_by_exception() variant?

108

As discussed live: we can use a better message here.

170

How is this behavior really what we want? IIUC, that means that if you compare two common_iterators that both contain different iterators (say It1 and It2) that are not comparable to each other, the common_iterators will compare equal to each other even if It1 and It2 are "pointing" to entirely different elements. Am I misunderstanding something here, or that's an incredibly subtle (and broken) behavior to have at runtime? @tcanens Can you shed some light on this?

In all cases, we need a test where we exercise that.

[zoecarver]

libcxx/include/__iterator/common_iterator.h

41

Add a comment: "iter_reference_t" is never a reference here because if it is we catch it in the if constexpr branch above where this one is called.

108

This should say something like "common_iterator not holding an iterator (holding a sentinel) must hold iterator."

170

We should assert these aren't both zero, even though it's non-conforming, people will thank us.

[tcanens]

libcxx/include/__iterator/common_iterator.h

170

This is meant for C++20 input iterators that aren't comparable with each other. Because incrementing an input iterator invalidates all copies, you can't have two valid iterators pointing to different elements in the same range.

We should assert these aren't both zero, even though it's non-conforming, people will thank us.

Please don't. i == i had better work.

[CaseyCarter]

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.pass.cpp

57

http://eel.is/c++draft/iterator.traits#1.sentence-3 is authoritative; http://eel.is/c++draft/iterators.common#common.iter.types-1.3 should be corrected to agree. Presumably the writer of the latter paragraph was under the impression that a.operator->() is always a prvalue.

[zoecarver]

libcxx/include/__iterator/common_iterator.h

170

This is meant for C++20 input iterators that aren't comparable with each other. Because incrementing an input iterator invalidates all copies, you can't have two valid iterators pointing to different elements in the same range.

Shouldn't this assert (or require) that these are input iterators then?

Please don't. i == i had better work.

But this is not i == i, it's x == y. What you're saying makes sense for input iterators, but what about forward iterators, or even contiguous iterators?

(Thanks for all the help with interpreting the standard's wording here, by the way.)

[tcanens]

libcxx/include/__iterator/common_iterator.h

170

common_iterator is a C++17 compatibility shim. I don't think this is worse than returning true when both are sentinels - two sentinels can mean completely different things, even if they have the same type.

[zoecarver]

libcxx/include/__iterator/common_iterator.h

170

common_iterator is a C++17 compatibility shim. I don't think this is worse than returning true when both are sentinels - two sentinels can mean completely different things, even if they have the same type.

The difference is sentinels must always be the end of the range. I can get behind saying "this must always be true because the sentinels must always be the end of the same range which must be the same element." The part I'm having trouble with is it's OK to have two different forward iterators that point to the same range in different places. Those should return false when compared (or somehow generate an error or UB).

[zoecarver]

Apply remaining few review comments :)

libcxx/include/__iterator/common_iterator.h

170

In all cases, we need a test where we exercise that.

Tested in both assign.pass.cpp (line 35, 50, 68, 74) and eq.pass.cpp (line 78, 88, 89).

[• Quuxplusone]

libcxx/include/__iterator/common_iterator.h

170

I'd prefer to see an explicit static_assert here:

static_assert(!equality_comparable_with<_Iter, _I2>);
return true;

I think this assertion would sufficiently explain why we aren't checking i1 == i2 here — it's because we physically can't. Also, the assertion serves as an important backstop against subsumption bugs. The absolute worst thing that could happen here is that the constraint on line 179 bit-rots under maintenance and we end up executing this code for iterators that are comparable.

174

_VSTD::__unchecked_get<0>(__x.__hold_) == _VSTD::__unchecked_get<1>(__y.__hold_)

I don't trust __unchecked_get<_Iter> to do the right thing when _Sent is cvref-qualified _Iter or vice versa (or they're in some other subtle corner-case way related to each other). Integer indices, on the other hand, are nice and solid and trustworthy. Also, cppreference documents that the code should use get<i> and get<j>, not get<I> and get<S2>; it's just barely possible that there might be a technical reason for that.

[tcanens]

libcxx/include/__iterator/common_iterator.h

170

forward iterators are required to be comparable, so it would go to the other overload.

[cjdb]

libcxx/include/__iterator/common_iterator.h

170

But this is not i == i, it's x == y. What you're saying makes sense for input iterators, but what about forward iterators, or even contiguous iterators?

This is the overload that's chosen when we evaluate i == i, so Tim's got a point. I'm also not sure what the assertion would achieve? Are you trying to prevent i == i?

[cjdb]

Thanks for working on such an ugly type. In addition to my inline comments, please add

• a module map entry
• iterator conformance tests

libcxx/include/__iterator/common_iterator.h

36

Can we define __proxy and __postfix_proxy out-of-line please?

64

This should be private. Also, hold is not a particularly descriptive name to me.

108

How about "Dereferencing a common_iterator is only possible if it is holding an iterator, but this one is holding a sentinel."?

123–125

Can we get this into a named object please? Perhaps __common_iterator_has_arrow?

154–156

Please name this.

273–275

Seconded. Please use _If, if you can.

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.pass.cpp

87

Please prefix "postfix" to this sentence.

libcxx/test/support/test_iterators.h

165

I think this functionality should instead be reflected in cpp20_input_iterator (and in a separate patch, if it breaks any code).

[zoecarver]

libcxx/include/__iterator/common_iterator.h

170

I'm talking about two completely unrelated iterators, for example, this:

auto iter1 = random_access_iterator<int*>(buffer + 1);
auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);

auto iter2 = forward_iterator<int*>(buffer + 4);
auto commonIter2 = std::common_iterator<decltype(iter2), sentinel_type<int*>>(iter2);

assert(commonIter1 == commonIter2);

(An actual test case ^)

If above is UB, it's not clear to me where that is stated. Even so, if it is UB for some reason, I think it would be great to add an assertion. And if it's well defined, well that seems terrible (and my preference would be to create an LWG issue and still add an assertion or something, because that's definitely a but, but maybe others disagree).

[tcanens]

libcxx/include/__iterator/common_iterator.h

170

So pathological mix-up scenarios where you compare completely unrelated things? It's hard to think of a non-contrived example where that matters.

I don't really care about this case either way; I'm just not convinced that it's worth the trouble (coming up with something that doesn't damage valid uses can be tricky).

@CaseyCarter thoughts?

[CaseyCarter]

libcxx/include/__iterator/common_iterator.h

170

It's hard to care about this. The domain of equality for forward_iterators is iterators obtained from the same range, so generic code can't perform this comparison. To do so in concrete code - when you know the result is useless - would be silly. In other words: if you think this is weird, then don't do it.

Conversely, if you want comparison of common_iterator<I1, S> and common_iterator<I2, S> to be sensible you can always make I1 and I2 model equality_comparable.

[zoecarver]

Apply Chris' review comments.

[zoecarver]

libcxx/include/__iterator/common_iterator.h

36

Why?

64

Because of the friend issues we discussed with transform_view on #libcxx we unfortunately can't have this be private.

123

@tcanens Another potential LWG issue: shouldn't this be is_pointer_v<_Iter> || requires(const _Iter& __i) { __i.operator->(); }? If not, do we need to have the is_pointer condition below? Can it ever be hit?

123–125

I don't want to add another "has arrow" concept that means something different from __has_arrow. Depending on my comment above, we might be able to use that here, though.

170

I guess it's pathological, but it would also be pathological to even compare any iterators (read: not sentinels) that use this overload. Basically, you're saying "you should only compare iterators here that are equal." In which case, why does this overload even need to work with iterators (read: not sentinels)?

We have two cases: 1) someone is using this correctly. They have two iterators that are equal. This returns true.

2. Someone is using this incorrectly. They have two iterators that are not equal.

You're saying the second case isn't worth worrying about because it would be pathological. This implies that no one should ever call this function without knowing if their iterators are equal beforehand. This begs the question: why do they even need to call this function in the first place? If they know their iterators are equal, it's pointless to compare them.

I think we should add a precondition or something that says i or j is 1. And I'd like to add that as an assertion here.

174

I'm not opposed to using indexes, but a concrete example would be nice, to show that there's actually a problem. I find using types much more readable, so I'd want a solid reason not to do it.

libcxx/test/support/test_iterators.h

165

Common iterator requires that we're copyable, so we really need this type. But I'm fully supportive of making cpp20_input_iterator non-default-constructible in a separate patch.

[tcanens]

libcxx/include/__iterator/common_iterator.h

123

is_reference_v<iter_reference_t<_I2>> should be enough to catch pointers.

170

Basically, you're saying "you should only compare iterators here that are equal." In which case, why does this overload even need to work with iterators (read: not sentinels)?

Because perfectly valid generic code written to C++17 iterator requirements may want to do this, perhaps because it makes the code simpler. Breaking valid code makes common_iterator unfit for its only purpose.

This is like "why does array<T, 0> has a front() when it's always UB to call it"? Well, because generic code may want to do so from a dynamically unreachable context.

I think we should add a precondition or something that says i or j is 1. And I'd like to add that as an assertion here.

That's a non-starter as far as I'm concerned.

[cjdb]

libcxx/include/__iterator/common_iterator.h

36

I find class-in-class definitions to clutter the outer-class definition. For the record, it's still common_iterator<_Iter, _Sent>::__proxy.

170

Basically, you're saying "you should only compare iterators here that are equal." In which case, why does this overload even need to work with iterators (read: not sentinels)?

Because perfectly valid generic code written to C++17 iterator requirements may want to do this, perhaps because it makes the code simpler. Breaking valid code makes common_iterator unfit for its only purpose.

This is like "why does array<T, 0> has a front() when it's always UB to call it"? Well, because generic code may want to do so from a dynamically unreachable context.

That it's UB means an implementation can assert that N != 0.

I think we should add a precondition or something that says i or j is 1. And I'd like to add that as an assertion here.

That's a non-starter as far as I'm concerned.

Could you please elaborate on why you think this is a non-starter? Having said that, I keep bouncing on my opinion for this matter whenever new evidence is put forward.

[ldionne]

libcxx/include/__iterator/common_iterator.h

170

@CaseyCarter said:

It's hard to care about this. The domain of equality for forward_iterators is iterators obtained from the same range, so generic code can't perform this comparison.

Ok. So basically, we never expect this overload to be called with It1 and It2 being forward_iterators, and this should only be called for input_iterators? In that case, I don't understand what's preventing us from adding a constraint !forward_iterator<It1> && !forward_iterator<It2> -- it's really cheap to do that, and we'd catch this pathological case at compile-time instead of having really strange behavior at runtime. And this will still work for all input_iterators, which is the only intended use case for this comparison operator if I followed correctly. Do you agree?

@zoecarver Whatever we end up doing here, I agree with Arthur's suggestion to add an assertion like static_assert(!equality_comparable_with<_Iter, _I2>); before returning true.

[tcanens]

libcxx/include/__iterator/common_iterator.h

170

Basically, you're saying "you should only compare iterators here that are equal." In which case, why does this overload even need to work with iterators (read: not sentinels)?

Because perfectly valid generic code written to C++17 iterator requirements may want to do this, perhaps because it makes the code simpler. Breaking valid code makes common_iterator unfit for its only purpose.

This is like "why does array<T, 0> has a front() when it's always UB to call it"? Well, because generic code may want to do so from a dynamically unreachable context.

That it's UB means an implementation can assert that N != 0.

At runtime, not at compile time. "It's always UB when called" doesn't justify = delete; or removal or static_assert in the body, because reasonable code can do if (not a.empty()) { do_something(a.front()); }.

Similarly here, just because the only meaningful comparison for iterators must return true doesn't justify making the comparison undefined.

I think we should add a precondition or something that says i or j is 1. And I'd like to add that as an assertion here.

That's a non-starter as far as I'm concerned.

Could you please elaborate on why you think this is a non-starter? Having said that, I keep bouncing on my opinion for this matter whenever new evidence is put forward.

Comparing a non-singular common_iterator with itself, or a copy of itself, must be valid. Making perfectly valid uses undefined at runtime just to catch pathological cases that are unlikely to ever arise in practice is totally backwards.

I'm open to something like what Louis suggested.

[zoecarver]

At runtime, not at compile time.
[...]
I'm open to something like what Louis suggested.

To clarify, I'm suggesting that we add a runtime assertion that does some combination of i == 1 || j == 1 || (!forward_iterator<It1> && !forward_iterator<It2>).

[ldionne]

I'm not seeing any blocking issues anymore, and it looks reasonable to me. I think we should file the LWG issue for operator== and ship it. Other reviewers, please chime in if you have feedback you really want to see addressed before this is shipped, otherwise @zoecarver feel free to ship this after the weekend or so (to give time for people to see this).

(needs CI)

libcxx/include/__iterator/common_iterator.h

170

@zoecarver Let's implement it per the spec for now and file a LWG issue with a proposed resolution like this:

template<class _I2, sentinel_for<_Iter> _S2>
    requires sentinel_for<_Sent, _I2> && 
             !equality_comparable_with<_Iter, _I2> && // I think this is required to avoid an ambiguity with the other overload
             !forward_iterator<_Iter> &&
             !forward_iterator<_I2>
friend bool operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y);

Either this is accepted by LWG and we fix it before we've had time to ship it anyways, or it's not and in that case we'll be conforming (and hopefully LWG explains why they think this isn't a good resolution). Are you willing to file it?

[zoecarver]

Rebase.

[zoecarver]

Rebase (again).

[zoecarver]

Fix modules issues (hopefully).

[cjdb]

libcxx/include/variant

209

Please sort the list of includes.

libcxx/docs/Status/RangesPaper.csv

 | `ranges::next <https://llvm.org/D102563>`_
 | `ranges::prev <https://llvm.org/D102564>`_",[iterator.concepts],Christopher Di Bella,In progress
 [predef.iterators],Updates to predefined iterators.,"| [iterator.concepts]
 | [iterator.cust.swap]
 | [iterator.cust.move]",Unassigned,Not started
 [move.sentinel],,[predef.iterators],Unassigned,Not started
 [common.iterator],,"| [iterator.concepts]
 | [iterator.cust.swap]
-| [iterator.cust.move]",Zoe Carver,Not started
+| [iterator.cust.move]",Zoe Carver,`D103335 <https://llvm.org/D103335>`_,✅
 [default.sentinels],std::default_sentinel_t.,No dependencies,Unassigned,Not started
 [counted.iterator],,"| [iterator.concepts]
 | [iterator.cust.swap]
 | [iterator.cust.move]
 | [default.sentinels]",Unassigned,Not started
 [stream.iterators],,[default.sentinels],Unassigned,Not started
 `[range.access] <http://wg21.link/range.access>`_,"| `ranges::begin <https://llvm.org/D100255>`_
 | `ranges::end <https://llvm.org/D100255>`_

libcxx/include/CMakeLists.txt

set(files
   __functional/unary_function.h
   __functional/unary_negate.h
   __functional/unwrap_ref.h
   __functional/weak_result_type.h
   __hash_table
   __iterator/access.h
   __iterator/advance.h
   __iterator/back_insert_iterator.h
+  __iterator/common_iterator.h
   __iterator/concepts.h
   __iterator/data.h
   __iterator/default_sentinel.h
   __iterator/distance.h
   __iterator/empty.h
   __iterator/erase_if_container.h
   __iterator/front_insert_iterator.h
   __iterator/incrementable_traits.h
set(files
   __libcpp_version
   __locale
   __memory/addressof.h
   __memory/allocation_guard.h
   __memory/allocator_arg_t.h
   __memory/allocator_traits.h
   __memory/allocator.h
   __memory/auto_ptr.h
+  __memory/builtin_new_allocator.h
   __memory/compressed_pair.h
   __memory/construct_at.h
+  __memory/destruct_n.h
   __memory/pointer_safety.h
   __memory/pointer_traits.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

libcxx/include/__algorithm/equal.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___ALGORITHM_EQUAL_H
 #define _LIBCPP___ALGORITHM_EQUAL_H
 
 #include <__config>
 #include <__algorithm/comp.h>
+#include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
-#include <iterator> // FIXME: replace with <__iterator/distance.h> when it lands
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/equal_range.h

 #define _LIBCPP___ALGORITHM_EQUAL_RANGE_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/half_positive.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/upper_bound.h>
-#include <iterator>
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/inplace_merge.h

 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/comp.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/min.h>
 #include <__algorithm/move.h>
 #include <__algorithm/rotate.h>
 #include <__algorithm/upper_bound.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/reverse_iterator.h>
+#include <__memory/destruct_n.h>
+#include <__memory/temporary_buffer.h>
+#include <__memory/unique_ptr.h>
 #include <__utility/swap.h>
-#include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/is_permutation.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___ALGORITHM_IS_PERMUTATION_H
 #define _LIBCPP___ALGORITHM_IS_PERMUTATION_H
 
 #include <__algorithm/comp.h>
 #include <__config>
+#include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
-#include <iterator> // FIXME: replace with <__iterator/distance.h> when it lands
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/lower_bound.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___ALGORITHM_LOWER_BOUND_H
 #define _LIBCPP___ALGORITHM_LOWER_BOUND_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__iterator/advance.h>
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/partition_point.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___ALGORITHM_PARTITION_POINT_H
 #define _LIBCPP___ALGORITHM_PARTITION_POINT_H
 
 #include <__config>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/rotate.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___ALGORITHM_ROTATE_H
 #define _LIBCPP___ALGORITHM_ROTATE_H
 
 #include <__algorithm/move.h>
 #include <__algorithm/move_backward.h>
 #include <__algorithm/swap_ranges.h>
 #include <__config>
+#include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
 #include <__iterator/prev.h>
 #include <__utility/swap.h>
-#include <iterator>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/rotate_copy.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___ALGORITHM_ROTATE_COPY_H
 #define _LIBCPP___ALGORITHM_ROTATE_COPY_H
 
 #include <__config>
 #include <__algorithm/copy.h>
-#include <iterator>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/__algorithm/sample.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___ALGORITHM_SAMPLE_H
 #define _LIBCPP___ALGORITHM_SAMPLE_H
 
 #include <__config>
 #include <__algorithm/min.h>
+#include <__iterator/distance.h>
 #include <__random/uniform_int_distribution.h>
-#include <iterator>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/sort.h

 #define _LIBCPP___ALGORITHM_SORT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/min_element.h>
 #include <__algorithm/partial_sort.h>
 #include <__algorithm/unwrap_iter.h>
+#include <__memory/destruct_n.h>
+#include <__memory/unique_ptr.h>
 #include <__utility/swap.h>
-#include <memory>
 #include <type_traits> // swap
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/__algorithm/stable_partition.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___ALGORITHM_STABLE_PARTITION_H
 #define _LIBCPP___ALGORITHM_STABLE_PARTITION_H
 
 #include <__config>
 #include <__algorithm/rotate.h>
 #include <__iterator/iterator_traits.h>
+#include <__memory/destruct_n.h>
+#include <__memory/unique_ptr.h>
 #include <__utility/swap.h>
-#include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__algorithm/stable_sort.h

 #define _LIBCPP___ALGORITHM_STABLE_SORT_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/inplace_merge.h>
 #include <__algorithm/sort.h>
 #include <__iterator/iterator_traits.h>
+#include <__memory/destruct_n.h>
+#include <__memory/unique_ptr.h>
 #include <__utility/swap.h>
-#include <memory>
 #include <type_traits> // swap
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/__algorithm/unwrap_iter.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___ALGORITHM_UNWRAP_ITER_H
 #define _LIBCPP___ALGORITHM_UNWRAP_ITER_H
 
 #include <__config>
-#include <iterator>
+#include <__iterator/iterator_traits.h>
 #include <__memory/pointer_traits.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS

libcxx/include/__algorithm/upper_bound.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___ALGORITHM_UPPER_BOUND_H
 #define _LIBCPP___ALGORITHM_UPPER_BOUND_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__iterator/distance.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

libcxx/include/__functional/function.h

 #define _LIBCPP___FUNCTIONAL_FUNCTION_H
 
 #include <__config>
 #include <__functional/binary_function.h>
 #include <__functional/invoke.h>
 #include <__functional/unary_function.h>
 #include <__iterator/iterator_traits.h>
 #include <__memory/allocator_traits.h>
+#include <__memory/builtin_new_allocator.h>
 #include <__memory/compressed_pair.h>
 #include <__memory/shared_ptr.h>
 #include <exception>
-#include <memory> // TODO: replace with <__memory/__builtin_new_allocator.h>
 #include <type_traits>
 #include <utility>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD

libcxx/include/__iterator/common_iterator.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___ITERATOR_COMMON_ITERATOR_H
+#define _LIBCPP___ITERATOR_COMMON_ITERATOR_H
+
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/iter_swap.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/readable_traits.h>
+#include <variant>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
+  requires (!same_as<_Iter, _Sent> && copyable<_Iter>)
+class common_iterator {
+  variant<_Iter, _Sent> __hold;
+
+  class __proxy {
+    friend common_iterator;
+
+    iter_value_t<_Iter> __value;
+    constexpr __proxy(iter_reference_t<_Iter>&& __x)
+      : __value(__x) {}
+
+  public:
+    const iter_value_t<_Iter>* operator->() const {
+      return _VSTD::addressof(__value);
+    }
+  };
+
+  class __postfix_proxy {
+    friend common_iterator;
+
+    iter_value_t<_Iter> __value;
+    constexpr __postfix_proxy(iter_reference_t<_Iter>&& __x)
+      : __value(__x) {}
+
+  public:
+    const iter_value_t<_Iter>& operator*() const {
+      return __value;
+    }
+  };
+
+public:
+  common_iterator() requires default_initializable<_Iter> = default;
+
+  constexpr common_iterator(_Iter __i) : __hold(in_place_type<_Iter>, _VSTD::move(__i)) {}
+  constexpr common_iterator(_Sent __s) : __hold(in_place_type<_Sent>, _VSTD::move(__s)) {}
+
+  template<class _I2, class _S2>
+    requires convertible_to<const _I2, _Iter> && convertible_to<const _S2&, _Sent>
+  constexpr common_iterator(const common_iterator<_I2, _S2>& __other)
+    : __hold(__other.__hold) {}
+
+  template<class _I2, class _S2>
+    requires convertible_to<const _I2, _Iter> && convertible_to<const _S2&, _Sent> &&
+             assignable_from<const _I2, _Iter> && assignable_from<const _S2&, _Sent>
+  common_iterator& operator=(const common_iterator<_I2, _S2>& __other) {
+    __hold = __other.__hold;
+  }
+
+  decltype(auto) operator*() { return *_VSTD::get<_Iter>(__hold); }
+  decltype(auto) operator*() const
+    requires __dereferenceable<const _Iter>
+  { return *_VSTD::get<_Iter>(__hold); }
+
+  decltype(auto) operator->() const
+    requires indirectly_readable<const _Iter> &&
+    (requires(const _Iter& __i) { __i.operator->(); } ||
+     is_reference_v<iter_reference_t<_Iter>> ||
+     constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>) {
+    if constexpr (is_pointer_v<_Iter> || requires(const _Iter& __i) { __i.operator->(); })    {
+      return _VSTD::get<_Iter>(__hold);
+    } else if constexpr (is_reference_v<iter_reference_t<_Iter>>) {
+      auto&& __tmp = *_VSTD::get<_Iter>(__hold);
+      return _VSTD::addressof(__tmp);
+    } else {
+      return __proxy(*_VSTD::get<_Iter>(__hold));
+    }
+  }
+
+  common_iterator& operator++() { ++_VSTD::get<_Iter>(__hold); return *this; }
+  decltype(auto) operator++(int) {
+    if constexpr (forward_iterator<_Iter>) {
+      auto __tmp = *this;
+      ++*this;
+      return __tmp;
+    } else if constexpr (requires (_Iter& __i) { { *__i++ } -> __referenceable; } ||
+                         !(constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>> &&
+                           move_constructible<iter_value_t<_Iter>>)) {
+      return _VSTD::get<_Iter>(__hold)++;
+    } else {
+      __postfix_proxy __p(**this);
+      ++*this;
+      return __p;
+    }
+  }
+
+  template<class _I2, sentinel_for<_Iter> _S2>
+    requires sentinel_for<_Sent, _I2>
+  friend bool operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
+    if (__x.__hold.index() == __y.__hold.index())
+      return true;
+
+    if (__x.__hold.index() == 0)
+      return _VSTD::get<_Iter>(__x.__hold) == _VSTD::get<_Sent>(__y.__hold);
+
+    return _VSTD::get<_Sent>(__x.__hold) == _VSTD::get<_Iter>(__y.__hold);
+  }
+
+  template<class _I2, sentinel_for<_Iter> _S2>
+    requires sentinel_for<_Sent, _I2> && equality_comparable_with<_Iter, _I2>
+  friend bool operator==(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
+    if (__x.__hold.index() == 1 && __y.__hold.index() == 1)
+      return true;
+
+    if (__x.__hold.index() == 0 && __y.__hold.index() == 0)
+      return  _VSTD::get<_Iter>(__x.__hold) ==  _VSTD::get<_Iter>(__y.__hold);
+
+    if (__x.__hold.index() == 0)
+      return  _VSTD::get<_Iter>(__x.__hold) == _VSTD::get<_Sent>(__y.__hold);
+
+    return _VSTD::get<_Sent>(__x.__hold) ==  _VSTD::get<_Iter>(__y.__hold);
+  }
+
+  template<sized_sentinel_for<_Iter> _I2, sized_sentinel_for<_Iter> _S2>
+    requires sized_sentinel_for<_Sent, _I2>
+  friend iter_difference_t<_I2> operator-(const common_iterator& __x, const common_iterator<_I2, _S2>& __y) {
+    if (__x.__hold.index() == 1 && __y.__hold.index() == 1)
+      return 0;
+
+    if (__x.__hold.index() == 0 && __y.__hold.index() == 0)
+      return  _VSTD::get<_Iter>(__x.__hold) - _VSTD::get<_Iter>(__y.__hold);
+
+    if (__x.__hold.index() == 0)
+      return  _VSTD::get<_Iter>(__x.__hold) - _VSTD::get<_Sent>(__y.__hold);
+
+    return _VSTD::get<_Sent>(__x.__hold) -  _VSTD::get<_Iter>(__y.__hold);
+  }
+
+  friend iter_rvalue_reference_t<_Iter> iter_move(const common_iterator& __i)
+    noexcept(noexcept(ranges::iter_move(declval<const _Iter&>())))
+      requires input_iterator<_Iter>
+  { return ranges::iter_move( _VSTD::get<_Iter>(__i.__hold)); }
+
+  template<indirectly_swappable<_Iter> _I2, class _S2>
+  friend void iter_swap(const common_iterator& __x, const common_iterator<_I2, _S2>& __y)
+      noexcept(noexcept(ranges::iter_swap(declval<const _Iter&>(), declval<const _I2&>())))
+  { return ranges::iter_swap( _VSTD::get<_Iter>(__x.__hold),  _VSTD::get<_Iter>(__y.__hold)); }
+};
+
+template<class _Iter, class _Sent>
+struct incrementable_traits<common_iterator<_Iter, _Sent>> {
+  using difference_type = iter_difference_t<_Iter>;
+};
+
+template<class _Iter>
+concept __denotes_forward_iter =
+  requires {
+    typename iterator_traits<_Iter>::iterator_category;
+  } &&
+  derived_from<typename iterator_traits<_Iter>::iterator_category, forward_iterator_tag>;
+
+template<class _Iter, class _Sent>
+concept __common_iter_has_ptr_op = requires(const common_iterator<_Iter, _Sent> __a) {
+  __a.operator->();
+};
+
+template<class _Iter, class _Sent>
+struct iterator_traits<common_iterator<_Iter, _Sent>> {
+  using iterator_concept = conditional_t<forward_iterator<_Iter>,
+                                         forward_iterator_tag,
+                                         input_iterator_tag>;
+  using iterator_category = conditional_t<__denotes_forward_iter<_Iter>,
+                                          forward_iterator_tag,
+                                          input_iterator_tag>;
+  using pointer = conditional_t<__common_iter_has_ptr_op<_Iter, _Sent>,
+                                decltype(declval<const common_iterator<_Iter, _Sent>>().operator->()),
+                                void>;
+  using value_type = iter_value_t<_Iter>;
+  using difference_type = iter_difference_t<_Iter>;
+  using reference = iter_reference_t<_Iter>;
+};
+
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ITERATOR_COMMON_ITERATOR_H

libcxx/include/__memory/builtin_new_allocator.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_BUILTIN_NEW_ALLOCATOR_H
+#define _LIBCPP___MEMORY_BUILTIN_NEW_ALLOCATOR_H
+
+#include <__config>
+#include <__memory/unique_ptr.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// __builtin_new_allocator -- A non-templated helper for allocating and
+// deallocating memory using __builtin_operator_new and
+// __builtin_operator_delete. It should be used in preference to
+// `std::allocator<T>` to avoid additional instantiations.
+struct __builtin_new_allocator {
+  struct __builtin_new_deleter {
+    typedef void* pointer_type;
+
+    _LIBCPP_CONSTEXPR explicit __builtin_new_deleter(size_t __size, size_t __align)
+        : __size_(__size), __align_(__align) {}
+
+    void operator()(void* p) const _NOEXCEPT {
+        _VSTD::__libcpp_deallocate(p, __size_, __align_);
+    }
+
+   private:
+    size_t __size_;
+    size_t __align_;
+  };
+
+  typedef unique_ptr<void, __builtin_new_deleter> __holder_t;
+
+  static __holder_t __allocate_bytes(size_t __s, size_t __align) {
+      return __holder_t(_VSTD::__libcpp_allocate(__s, __align),
+                     __builtin_new_deleter(__s, __align));
+  }
+
+  static void __deallocate_bytes(void* __p, size_t __s,
+                                 size_t __align) _NOEXCEPT {
+      _VSTD::__libcpp_deallocate(__p, __s, __align);
+  }
+
+  template <class _Tp>
+  _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
+  static __holder_t __allocate_type(size_t __n) {
+      return __allocate_bytes(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
+  }
+
+  template <class _Tp>
+  _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
+  static void __deallocate_type(void* __p, size_t __n) _NOEXCEPT {
+      __deallocate_bytes(__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
+  }
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___MEMORY_BUILTIN_NEW_ALLOCATOR_H

libcxx/include/__memory/destruct_n.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_DESTRUCT_N_H
+#define _LIBCPP___MEMORY_DESTRUCT_N_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+struct __destruct_n
+{
+private:
+    size_t __size_;
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void __process(_Tp* __p, false_type) _NOEXCEPT
+        {for (size_t __i = 0; __i < __size_; ++__i, ++__p) __p->~_Tp();}
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void __process(_Tp*, true_type) _NOEXCEPT
+        {}
+
+    _LIBCPP_INLINE_VISIBILITY void __incr(false_type) _NOEXCEPT
+        {++__size_;}
+    _LIBCPP_INLINE_VISIBILITY void __incr(true_type) _NOEXCEPT
+        {}
+
+    _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, false_type) _NOEXCEPT
+        {__size_ = __s;}
+    _LIBCPP_INLINE_VISIBILITY void __set(size_t, true_type) _NOEXCEPT
+        {}
+public:
+    _LIBCPP_INLINE_VISIBILITY explicit __destruct_n(size_t __s) _NOEXCEPT
+        : __size_(__s) {}
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void __incr() _NOEXCEPT
+        {__incr(integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, _Tp*) _NOEXCEPT
+        {__set(__s, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
+
+    template <class _Tp>
+    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) _NOEXCEPT
+        {__process(__p, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___MEMORY_DESTRUCT_N_H

libcxx/include/__split_buffer

 // -*- C++ -*-
 #ifndef _LIBCPP_SPLIT_BUFFER
 #define _LIBCPP_SPLIT_BUFFER
 
 #include <__config>
 #include <__utility/forward.h>
 #include <algorithm>
+#include <memory>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>

libcxx/include/algorithm

 
 #include <__config>
 #include <__debug>
 #include <__bits> // __libcpp_clz
 #include <cstddef>
 #include <cstring>
 #include <functional>
 #include <initializer_list>
-#include <utility> // needed to provide swap_ranges.
-#include <memory>
 #include <iterator>
 #include <memory>
 #include <type_traits>
 #include <utility> // swap_ranges
 #include <version>
 
 #include <__algorithm/adjacent_find.h>
 #include <__algorithm/all_of.h>

libcxx/include/iterator

 
 template<class In, class Out>
   concept indirectly_movable_storable = see below;         // since C++20
 
 // [alg.req.ind.swap], concept indirectly_swappable
 template<class I1, class I2 = I1>
   concept indirectly_swappable = see below;                // since C++20
 
+template<input_or_output_iterator I, sentinel_for<I> S>
+  requires (!same_as<I, S> && copyable<I>)
+class common_iterator;                                     // since C++20
+
 template<class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
 struct iterator                                            // deprecated in C++17
 {
     typedef T         value_type;
     typedef Distance  difference_type;
     typedef Pointer   pointer;
     typedef Reference reference;

 */
 
 #include <__config>
 #include <__debug>
 #include <__functional_base>
 #include <__iterator/access.h>
 #include <__iterator/advance.h>
 #include <__iterator/back_insert_iterator.h>
+#include <__iterator/common_iterator.h>
 #include <__iterator/concepts.h>
 #include <__iterator/data.h>
 #include <__iterator/default_sentinel.h>
 #include <__iterator/distance.h>
 #include <__iterator/empty.h>
 #include <__iterator/erase_if_container.h>
 #include <__iterator/front_insert_iterator.h>
 #include <__iterator/incrementable_traits.h>

libcxx/include/memory

 
 #include <__config>
 #include <__functional_base>
 #include <__memory/addressof.h>
 #include <__memory/allocation_guard.h>
 #include <__memory/allocator.h>
 #include <__memory/allocator_arg_t.h>
 #include <__memory/allocator_traits.h>
+#include <__memory/builtin_new_allocator.h>
 #include <__memory/compressed_pair.h>
 #include <__memory/construct_at.h>
+#include <__memory/destruct_n.h>
 #include <__memory/pointer_safety.h>
 #include <__memory/pointer_traits.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>

 _LIBCPP_INLINE_VISIBILITY
 void __construct_backward_with_exception_guarantees(_Alloc&, _Tp* __begin1, _Tp* __end1, _Tp*& __end2) {
     ptrdiff_t _Np = __end1 - __begin1;
     __end2 -= _Np;
     if (_Np > 0)
         _VSTD::memcpy(__end2, __begin1, _Np * sizeof(_Tp));
 }
 
-struct __destruct_n
-{
-private:
-    size_t __size_;
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void __process(_Tp* __p, false_type) _NOEXCEPT
-        {for (size_t __i = 0; __i < __size_; ++__i, ++__p) __p->~_Tp();}
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void __process(_Tp*, true_type) _NOEXCEPT
-        {}
-
-    _LIBCPP_INLINE_VISIBILITY void __incr(false_type) _NOEXCEPT
-        {++__size_;}
-    _LIBCPP_INLINE_VISIBILITY void __incr(true_type) _NOEXCEPT
-        {}
-
-    _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, false_type) _NOEXCEPT
-        {__size_ = __s;}
-    _LIBCPP_INLINE_VISIBILITY void __set(size_t, true_type) _NOEXCEPT
-        {}
-public:
-    _LIBCPP_INLINE_VISIBILITY explicit __destruct_n(size_t __s) _NOEXCEPT
-        : __size_(__s) {}
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void __incr() _NOEXCEPT
-        {__incr(integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void __set(size_t __s, _Tp*) _NOEXCEPT
-        {__set(__s, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
-
-    template <class _Tp>
-    _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) _NOEXCEPT
-        {__process(__p, integral_constant<bool, is_trivially_destructible<_Tp>::value>());}
-};
-
 _LIBCPP_FUNC_VIS void* align(size_t __align, size_t __sz, void*& __ptr, size_t& __space);
 
 // --- Helper for container swap --
 template <typename _Alloc>
 _LIBCPP_INLINE_VISIBILITY
 void __swap_allocator(_Alloc & __a1, _Alloc & __a2, true_type)
 #if _LIBCPP_STD_VER >= 14
     _NOEXCEPT

 
 template<typename _Alloc>
 struct __is_allocator<_Alloc,
        typename __void_t<typename _Alloc::value_type>::type,
        typename __void_t<decltype(declval<_Alloc&>().allocate(size_t(0)))>::type
      >
    : true_type {};
 
-// __builtin_new_allocator -- A non-templated helper for allocating and
-// deallocating memory using __builtin_operator_new and
-// __builtin_operator_delete. It should be used in preference to
-// `std::allocator<T>` to avoid additional instantiations.
-struct __builtin_new_allocator {
-  struct __builtin_new_deleter {
-    typedef void* pointer_type;
-
-    _LIBCPP_CONSTEXPR explicit __builtin_new_deleter(size_t __size, size_t __align)
-        : __size_(__size), __align_(__align) {}
-
-    void operator()(void* p) const _NOEXCEPT {
-        _VSTD::__libcpp_deallocate(p, __size_, __align_);
-    }
-
-   private:
-    size_t __size_;
-    size_t __align_;
-  };
-
-  typedef unique_ptr<void, __builtin_new_deleter> __holder_t;
-
-  static __holder_t __allocate_bytes(size_t __s, size_t __align) {
-      return __holder_t(_VSTD::__libcpp_allocate(__s, __align),
-                     __builtin_new_deleter(__s, __align));
-  }
-
-  static void __deallocate_bytes(void* __p, size_t __s,
-                                 size_t __align) _NOEXCEPT {
-      _VSTD::__libcpp_deallocate(__p, __s, __align);
-  }
-
-  template <class _Tp>
-  _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
-  static __holder_t __allocate_type(size_t __n) {
-      return __allocate_bytes(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
-  }
-
-  template <class _Tp>
-  _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
-  static void __deallocate_type(void* __p, size_t __n) _NOEXCEPT {
-      __deallocate_bytes(__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
-  }
-};
-
-
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
 #   include <__pstl_memory>
 #endif
 
 #endif // _LIBCPP_MEMORY

libcxx/include/module.modulemap

module memory {
 
     module __memory {
       module addressof                { header "__memory/addressof.h"                }
       module allocation_guard         { header "__memory/allocation_guard.h"         }
       module allocator                { header "__memory/allocator.h"                }
       module allocator_arg_t          { header "__memory/allocator_arg_t.h"          }
       module allocator_traits         { header "__memory/allocator_traits.h"         }
       module auto_ptr                 { header "__memory/auto_ptr.h"                 }
+      module builtin_new_allocator    { header "__memory/builtin_new_allocator.h"    }
       module compressed_pair          { header "__memory/compressed_pair.h"          }
       module construct_at             { header "__memory/construct_at.h"             }
+      module destruct_n               { header "__memory/destruct_n.h"               }
       module pointer_safety           { header "__memory/pointer_safety.h"           }
       module pointer_traits           { header "__memory/pointer_traits.h"           }
       module raw_storage_iterator     { header "__memory/raw_storage_iterator.h"     }
       module shared_ptr               { header "__memory/shared_ptr.h"               }
       module temporary_buffer         { header "__memory/temporary_buffer.h"         }
       module uninitialized_algorithms { header "__memory/uninitialized_algorithms.h" }
       module unique_ptr               { header "__memory/unique_ptr.h"               }
     }

libcxx/include/valarray

 template <class T> unspecified1 end(valarray<T>& v);
 template <class T> unspecified2 end(const valarray<T>& v);
 
 }  // std
 
 */
 
 #include <__config>
+#include <__memory/uninitialized_algorithms.h>
 #include <algorithm>
 #include <cmath>
 #include <cstddef>
 #include <functional>
 #include <initializer_list>
 #include <new>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

libcxx/include/variant

 
 #include <__availability>
 #include <__config>
 #include <__utility/forward.h>
 #include <__variant/monostate.h>
 #include <__tuple>
 #include <compare>
 #include <exception>
-#include <functional>
+#include <__functional/hash.h>
 #include <initializer_list>
 #include <limits>
 #include <new>
 #include <tuple>
 #include <type_traits>
 #include <utility>
 #include <version>
 

libcxx/include/vector

 
 */
 
 #include <__config>
 #include <__bit_reference>
 #include <__debug>
 #include <__functional_base>
 #include <__iterator/wrap_iter.h>
+#include <__iterator/move_iterator.h>
 #include <__split_buffer>
 #include <__utility/forward.h>
 #include <algorithm>
 #include <climits>
 #include <compare>
 #include <cstring>
 #include <initializer_list>
 #include <iosfwd> // for forward declaration of vector

libcxx/test/std/iterators/predef.iterators/iterators.common/arrow.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
+// UNSUPPORTED: gcc-10
+
+// decltype(auto) operator->() const
+//   requires see below;
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  // Case 2: http://eel.is/c++draft/iterators.common#common.iter.access-5.2
+  {
+    auto iter1 = simple_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(commonIter1.operator->() == buffer);
+    assert(commonIter2.operator->() == buffer);
+  }
+
+  // Case 3: http://eel.is/c++draft/iterators.common#common.iter.access-5.3
+  {
+    auto iter1 = value_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(*commonIter1.operator->().operator->() == 1);
+    assert(*commonIter2.operator->().operator->() == 1);
+  }
+
+  // Case 3: http://eel.is/c++draft/iterators.common#common.iter.access-5.3
+  {
+    auto iter1 = void_plus_plus_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(*commonIter1.operator->().operator->() == 1);
+    assert(*commonIter2.operator->().operator->() == 1);
+  }
+
+  // Case 1: http://eel.is/c++draft/iterators.common#common.iter.access-5.1
+  {
+    auto iter1 = cpp17_input_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(commonIter1.operator->().base() == buffer);
+    assert(commonIter2.operator->().base() == buffer);
+  }
+
+  // Case 1: http://eel.is/c++draft/iterators.common#common.iter.access-5.1
+  {
+    auto iter1 = forward_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(commonIter1.operator->().base() == buffer);
+    assert(commonIter2.operator->().base() == buffer);
+  }
+
+  // Case 1: http://eel.is/c++draft/iterators.common#common.iter.access-5.1
+  {
+    auto iter1 = random_access_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(commonIter1.operator->().base() == buffer);
+    assert(commonIter2.operator->().base() == buffer);
+  }
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/assign.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
+// UNSUPPORTED: gcc-10
+
+// template<class I2, class S2>
+//   requires convertible_to<const I2&, I> && convertible_to<const S2&, S> &&
+//            assignable_from<I&, const I2&> && assignable_from<S&, const S2&>
+//     common_iterator& operator=(const common_iterator<I2, S2>& x);
+
+#include <iterator>
+#include <ranges>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  {
+    auto iter1 = cpp17_input_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(cpp17_input_iterator<int*>(buffer + 1));
+
+    assert(*commonIter1 == 1);
+    assert(*commonIter2 == 2);
+    assert(commonIter1 != commonIter2);
+
+    commonIter1 = commonIter2;
+
+    assert(*commonIter1 == 2);
+    assert(*commonIter2 == 2);
+    assert(commonIter1 == commonIter2);
+  }
+  {
+    auto iter1 = forward_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(forward_iterator<int*>(buffer + 1));
+
+    assert(*commonIter1 == 1);
+    assert(*commonIter2 == 2);
+    assert(commonIter1 != commonIter2);
+
+    commonIter1 = commonIter2;
+
+    assert(*commonIter1 == 2);
+    assert(*commonIter2 == 2);
+    assert(commonIter1 == commonIter2);
+  }
+  {
+    auto iter1 = random_access_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1 + 1);
+    auto commonSent2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 7});
+
+    assert(*commonIter1 == 1);
+    assert(*commonIter2 == 2);
+    assert(commonIter1 != commonIter2);
+
+    commonIter1 = commonIter2;
+
+    assert(*commonIter1 == 2);
+    assert(*commonIter2 == 2);
+    assert(commonIter1 == commonIter2);
+
+    assert(std::ranges::next(commonIter1, 6) != commonSent1);
+    assert(std::ranges::next(commonIter1, 6) == commonSent2);
+
+    commonSent1 = commonSent2;
+
+    assert(std::ranges::next(commonIter1, 6) == commonSent1);
+    assert(std::ranges::next(commonIter1, 6) == commonSent2);
+  }
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/ctor.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
+// UNSUPPORTED: gcc-10
+
+// constexpr common_iterator() requires default_initializable<I> = default;
+// constexpr common_iterator(I i);
+// constexpr common_iterator(S s);
+// template<class I2, class S2>
+//   requires convertible_to<const I2&, I> && convertible_to<const S2&, S>
+//     constexpr common_iterator(const common_iterator<I2, S2>& x);
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+struct ConvertibleToForwardIter {
+  int *ptr;
+
+  constexpr operator forward_iterator<int*>() { return forward_iterator<int*>(ptr); }
+};
+
+template<class I, class S>
+concept ValidCommonIterator = requires {
+  typename std::common_iterator<I, S>;
+};
+
+template<class I, class S, class I2>
+concept ConvCtorEnabled = requires(I2 ci) {
+  std::common_iterator<I, S>(ci);
+};
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  static_assert( std::is_default_constructible_v<std::common_iterator<int*, sentinel_type<int*>>>);
+  static_assert(!std::is_default_constructible_v<std::common_iterator<non_default_constructible_iterator<int*>, sentinel_type<int*>>>);
+
+  // Not copyable:
+  static_assert(!ValidCommonIterator<cpp20_input_iterator<int*>, sentinel_type<int*>>);
+  // Same iter and sent:
+  static_assert(!ValidCommonIterator<cpp17_input_iterator<int*>, cpp17_input_iterator<int*>>);
+
+  {
+    auto iter1 = cpp17_input_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*iter1 == 1);
+    assert(*commonIter1 == 1);
+    assert(commonIter1 != commonSent1);
+  }
+  {
+    auto iter1 = forward_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*iter1 == 1);
+    assert(*commonIter1 == 1);
+    assert(commonIter1 != commonSent1);
+  }
+  {
+    auto iter1 = random_access_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*iter1 == 1);
+    assert(*commonIter1 == 1);
+    assert(commonIter1 != commonSent1);
+  }
+
+  // Conversion constructor:
+  {
+    ConvertibleToForwardIter conv{buffer};
+    auto commonIter = std::common_iterator<forward_iterator<int*>, sentinel_type<int*>>(conv);
+    assert(*commonIter == 1);
+
+    static_assert(ConvCtorEnabled<forward_iterator<int*>, sentinel_type<int*>, ConvertibleToForwardIter>);
+    static_assert(!ConvCtorEnabled<forward_iterator<int*>, sentinel_type<int*>, random_access_iterator<int*>>);
+  }
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/deref.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
+// UNSUPPORTED: gcc-10
+
+// decltype(auto) operator*();
+// decltype(auto) operator*() const
+//   requires dereferenceable<const I>;
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  {
+    auto iter1 = simple_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto iter2 = simple_iterator<int*>(buffer);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(*iter1 == 1);
+    assert(*commonIter1 == 1);
+
+    assert(*iter2 == 1);
+    assert(*commonIter2 == 1);
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+  }
+  {
+    auto iter1 = value_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto iter2 = value_iterator<int*>(buffer);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(*iter1 == 1);
+    assert(*commonIter1 == 1);
+
+    assert(*iter2 == 1);
+    assert(*commonIter2 == 1);
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+  }
+  {
+    auto iter1 = cpp17_input_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto iter2 = cpp17_input_iterator<int*>(buffer);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(*iter1 == 1);
+    assert(*commonIter1 == 1);
+
+    assert(*iter2 == 1);
+    assert(*commonIter2 == 1);
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+  }
+  {
+    auto iter1 = forward_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto iter2 = forward_iterator<int*>(buffer);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(*iter1 == 1);
+    assert(*commonIter1 == 1);
+
+    assert(*iter2 == 1);
+    assert(*commonIter2 == 1);
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+  }
+  {
+    auto iter1 = random_access_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto iter2 = random_access_iterator<int*>(buffer);
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+
+    assert(*iter1 == 1);
+    assert(*commonIter1 == 1);
+
+    assert(*iter2 == 1);
+    assert(*commonIter2 == 1);
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+  }
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/eq.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
+// UNSUPPORTED: gcc-10
+
+// template<class I2, sentinel_for<I> S2>
+//   requires sentinel_for<S, I2>
+// friend bool operator==(
+//   const common_iterator& x, const common_iterator<I2, S2>& y);
+// template<class I2, sentinel_for<I> S2>
+//   requires sentinel_for<S, I2> && equality_comparable_with<I, I2>
+// friend bool operator==(
+//   const common_iterator& x, const common_iterator<I2, S2>& y);
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  {
+    auto iter1 = simple_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonSent2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(commonIter1 != commonSent1);
+    assert(commonIter2 != commonSent2);
+
+    for (auto i = 1; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+  {
+    auto iter1 = value_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonSent2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(commonIter1 != commonSent1);
+    assert(commonIter2 != commonSent2);
+
+    for (auto i = 1; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+  {
+    auto iter1 = cpp17_input_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonSent2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(commonIter1 != commonSent1);
+    assert(commonIter2 != commonSent2);
+
+    for (auto i = 1; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+  {
+    auto iter1 = forward_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonSent2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(commonIter1 != commonSent1);
+    assert(commonIter2 != commonSent2);
+
+    for (auto i = 1; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+  {
+    auto iter1 = random_access_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    const auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    const auto commonSent2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(commonIter1 != commonSent1);
+    assert(commonIter2 != commonSent2);
+
+    for (auto i = 1; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/iter_move.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
+// UNSUPPORTED: gcc-10
+
+// friend iter_rvalue_reference_t<I> iter_move(const common_iterator& i)
+//   noexcept(noexcept(ranges::iter_move(declval<const I&>())))
+//     requires input_iterator<I>;
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  {
+    auto iter1 = cpp17_input_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    assert(std::ranges::iter_move(commonIter1) == 1);
+    ASSERT_SAME_TYPE(decltype(std::ranges::iter_move(commonIter1)), int&&);
+  }
+  {
+    auto iter1 = forward_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    assert(std::ranges::iter_move(commonIter1) == 1);
+    ASSERT_SAME_TYPE(decltype(std::ranges::iter_move(commonIter1)), int&&);
+  }
+  {
+    auto iter1 = random_access_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    assert(std::ranges::iter_move(commonIter1) == 1);
+    ASSERT_SAME_TYPE(decltype(std::ranges::iter_move(commonIter1)), int&&);
+  }
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/iter_swap.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
+// UNSUPPORTED: gcc-10
+
+// template<indirectly_swappable<I> I2, class S2>
+//   friend void iter_swap(const common_iterator& x, const common_iterator<I2, S2>& y)
+//     noexcept(noexcept(ranges::iter_swap(declval<const I&>(), declval<const I2&>())));
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  {
+    auto iter1 = cpp17_input_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    for (auto i = 0; i < 4; ++i) ++commonIter2;
+    assert(*commonIter2 == 5);
+    std::ranges::iter_swap(commonIter1, commonIter2);
+    assert(*commonIter1 == 5);
+    assert(*commonIter2 == 1);
+    std::ranges::iter_swap(commonIter2, commonIter1);
+  }
+  {
+    auto iter1 = forward_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    for (auto i = 0; i < 4; ++i) ++commonIter2;
+    assert(*commonIter2 == 5);
+    std::ranges::iter_swap(commonIter1, commonIter2);
+    assert(*commonIter1 == 5);
+    assert(*commonIter2 == 1);
+    std::ranges::iter_swap(commonIter2, commonIter1);
+  }
+  {
+    auto iter1 = random_access_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonIter2 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    for (auto i = 0; i < 4; ++i) ++commonIter2;
+    assert(*commonIter2 == 5);
+    std::ranges::iter_swap(commonIter1, commonIter2);
+    assert(*commonIter1 == 5);
+    assert(*commonIter2 == 1);
+    std::ranges::iter_swap(commonIter2, commonIter1);
+  }
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/iterator_traits.compile.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
+// UNSUPPORTED: gcc-10
+
+// template<input_iterator I, class S>
+//   struct iterator_traits<common_iterator<I, S>>;
+
+#include <iterator>
+
+#include "test_macros.h"
+#include "types.h"
+
+void test() {
+  {
+    using Iter = simple_iterator<int*>;
+    using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
+    using IterTraits = std::iterator_traits<CommonIter>;
+
+    static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
+    static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);
+    static_assert(std::same_as<IterTraits::value_type, int>);
+    static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
+    static_assert(std::same_as<IterTraits::pointer, int*>);
+    static_assert(std::same_as<IterTraits::reference, int&>);
+  }
+  {
+    using Iter = value_iterator<int*>;
+    using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
+    using IterTraits = std::iterator_traits<CommonIter>;
+
+    static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
+    static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);
+    static_assert(std::same_as<IterTraits::value_type, int>);
+    static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
+    // Note: IterTraits::pointer == __proxy.
+    static_assert(!std::same_as<IterTraits::pointer, int*>);
+    static_assert(std::same_as<IterTraits::reference, int>);
+  }
+  {
+    using Iter = cpp17_input_iterator<int*>;
+    using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
+    using IterTraits = std::iterator_traits<CommonIter>;
+
+    static_assert(std::same_as<IterTraits::iterator_concept, std::input_iterator_tag>);
+    static_assert(std::same_as<IterTraits::iterator_category, std::input_iterator_tag>);
+    static_assert(std::same_as<IterTraits::value_type, int>);
+    static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
+    static_assert(std::same_as<IterTraits::pointer, const Iter&>); // TODO: is this right?
+    static_assert(std::same_as<IterTraits::reference, int&>);
+  }
+  {
+    using Iter = forward_iterator<int*>;
+    using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
+    using IterTraits = std::iterator_traits<CommonIter>;
+
+    static_assert(std::same_as<IterTraits::iterator_concept, std::forward_iterator_tag>);
+    static_assert(std::same_as<IterTraits::iterator_category, std::forward_iterator_tag>);
+    static_assert(std::same_as<IterTraits::value_type, int>);
+    static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
+    static_assert(std::same_as<IterTraits::pointer, const Iter&>);
+    static_assert(std::same_as<IterTraits::reference, int&>);
+  }
+  {
+    using Iter = random_access_iterator<int*>;
+    using CommonIter = std::common_iterator<Iter, sentinel_type<int*>>;
+    using IterTraits = std::iterator_traits<CommonIter>;
+
+    static_assert(std::same_as<IterTraits::iterator_concept, std::forward_iterator_tag>);
+    static_assert(std::same_as<IterTraits::iterator_category, std::forward_iterator_tag>);
+    static_assert(std::same_as<IterTraits::value_type, int>);
+    static_assert(std::same_as<IterTraits::difference_type, std::ptrdiff_t>);
+    static_assert(std::same_as<IterTraits::pointer, const Iter&>);
+    static_assert(std::same_as<IterTraits::reference, int&>);
+  }
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/minus.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
+// UNSUPPORTED: gcc-10
+
+// template<sized_sentinel_for<I> I2, sized_sentinel_for<I> S2>
+//   requires sized_sentinel_for<S, I2>
+// friend iter_difference_t<I2> operator-(
+//   const common_iterator& x, const common_iterator<I2, S2>& y);
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  auto iter1 = random_access_iterator<int*>(buffer);
+  auto commonIter1 = std::common_iterator<decltype(iter1), sized_sentinel_type<int*>>(iter1);
+  auto commonSent1 = std::common_iterator<decltype(iter1), sized_sentinel_type<int*>>(sized_sentinel_type<int*>{buffer + 8});
+  assert(commonIter1 - commonSent1 == -8);
+  assert(commonSent1 - commonIter1 == 8);
+  assert(commonIter1 - commonIter1 == 0);
+  assert(commonSent1 - commonSent1 == 0);
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/plus_plus.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
+// UNSUPPORTED: gcc-10
+
+// common_iterator& operator++();
+// decltype(auto) operator++(int);
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "types.h"
+
+struct Incomplete;
+
+void test() {
+  int buffer[8] = {1, 2, 3, 4, 5, 6, 7, 8};
+
+  // Reference: http://eel.is/c++draft/iterators.common#common.iter.nav-5
+  // Case 2: can-reference
+  {
+    auto iter1 = simple_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+
+  // Case 2: can-reference
+  {
+    auto iter1 = value_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+
+  // Case 3: postfix-proxy
+  {
+    auto iter1 = void_plus_plus_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+
+  // Case 2: where this is not referencable or move constructible
+  {
+    auto iter1 = value_type_not_move_constructible_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    commonIter1++;
+    // Note: operator++ returns void.
+    // assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*commonIter1 == i);
+      commonIter1++;
+    }
+    assert(commonIter1 == commonSent1);
+  }
+
+  // Case 2: can-reference
+  {
+    auto iter1 = cpp17_input_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+
+  // Case 1: forward_iterator
+  {
+    auto iter1 = forward_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+
+  // Case 1: forward_iterator
+  {
+    auto iter1 = random_access_iterator<int*>(buffer);
+    auto commonIter1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(iter1);
+    auto commonSent1 = std::common_iterator<decltype(iter1), sentinel_type<int*>>(sentinel_type<int*>{buffer + 8});
+
+    assert(*(commonIter1++) == 1);
+    assert(*commonIter1 == 2);
+    assert(*(++commonIter1) == 3);
+    assert(*commonIter1 == 3);
+
+    for (auto i = 3; commonIter1 != commonSent1; ++i) {
+      assert(*(commonIter1++) == i);
+    }
+    assert(commonIter1 == commonSent1);
+  }
+}
+
+int main(int, char**) {
+  test();
+
+  return 0;
+}

libcxx/test/std/iterators/predef.iterators/iterators.common/types.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 TEST_STD_RANGES_ITERATORS_PREDEF_ITERATORS_ITERATORS_COMMON_TYPES_H
+#define TEST_STD_RANGES_ITERATORS_PREDEF_ITERATORS_ITERATORS_COMMON_TYPES_H
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class It>
+class simple_iterator
+{
+    It it_;
+
+public:
+    typedef          std::input_iterator_tag                   iterator_category;
+    typedef typename std::iterator_traits<It>::value_type      value_type;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    typedef It                                                 pointer;
+    typedef typename std::iterator_traits<It>::reference       reference;
+
+    constexpr It base() const {return it_;}
+
+    simple_iterator() = default;
+    explicit constexpr simple_iterator(It it) : it_(it) {}
+
+    constexpr reference operator*() const {return *it_;}
+
+    constexpr simple_iterator& operator++() {++it_; return *this;}
+    constexpr simple_iterator operator++(int)
+        {simple_iterator tmp(*this); ++(*this); return tmp;}
+};
+
+template <class It>
+class value_iterator
+{
+    It it_;
+
+public:
+    typedef          std::input_iterator_tag                   iterator_category;
+    typedef typename std::iterator_traits<It>::value_type      value_type;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    typedef It                                                 pointer;
+    typedef typename std::iterator_traits<It>::reference       reference;
+
+    constexpr It base() const {return it_;}
+
+    value_iterator() = default;
+    explicit constexpr value_iterator(It it) : it_(it) {}
+
+    constexpr value_type operator*() const {return std::move(*it_);}
+
+    constexpr value_iterator& operator++() {++it_; return *this;}
+    constexpr value_iterator operator++(int)
+        {value_iterator tmp(*this); ++(*this); return tmp;}
+};
+
+template <class It>
+class void_plus_plus_iterator
+{
+    It it_;
+
+public:
+    typedef          std::input_iterator_tag                   iterator_category;
+    typedef typename std::iterator_traits<It>::value_type      value_type;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    typedef It                                                 pointer;
+    typedef typename std::iterator_traits<It>::reference       reference;
+
+    constexpr It base() const {return it_;}
+
+    void_plus_plus_iterator() = default;
+    explicit constexpr void_plus_plus_iterator(It it) : it_(it) {}
+
+    constexpr value_type operator*() const {return std::move(*it_);}
+
+    constexpr void_plus_plus_iterator& operator++() {++it_; return *this;}
+    constexpr void operator++(int) {++(*this);}
+};
+
+// Not referenceable, constructible, and not move constructible.
+template <class It>
+class value_type_not_move_constructible_iterator
+{
+    It it_;
+
+public:
+    template<class T>
+    struct hold {
+      T value_;
+      hold(T v) : value_(v) {}
+      hold(const hold&) = delete;
+      hold(hold&&) = delete;
+    };
+
+    typedef          std::input_iterator_tag                   iterator_category;
+    typedef typename std::iterator_traits<It>::value_type      underlying_value_type;
+    typedef hold<underlying_value_type>                        value_type;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    typedef It                                                 pointer;
+    typedef typename std::iterator_traits<It>::reference       reference;
+
+    constexpr It base() const {return it_;}
+
+    value_type_not_move_constructible_iterator() = default;
+    explicit constexpr value_type_not_move_constructible_iterator(It it) : it_(it) {}
+
+    constexpr underlying_value_type operator*() const {return std::move(*it_);}
+
+    constexpr value_type_not_move_constructible_iterator& operator++() {++it_; return *this;}
+    constexpr void operator++(int) {++(*this);}
+};
+
+template<class T>
+struct sentinel_type {
+  T base;
+
+  template<class U>
+  friend constexpr bool operator==(const sentinel_type& lhs, const U& rhs) { return lhs.base == rhs.base(); }
+  template<class U>
+  friend constexpr bool operator==(const U& lhs, const sentinel_type& rhs) { return lhs.base() == rhs.base; }
+};
+
+template<class T>
+struct sized_sentinel_type {
+  T base;
+
+  template<class U>
+  friend constexpr bool operator==(const sized_sentinel_type& lhs, const U& rhs) { return lhs.base - rhs.base(); }
+  template<class U>
+  friend constexpr bool operator==(const U& lhs, const sized_sentinel_type& rhs) { return lhs.base() - rhs.base; }
+  template<class U>
+  friend constexpr auto operator- (const sized_sentinel_type& lhs, const U& rhs) { return lhs.base - rhs.base(); }
+  template<class U>
+  friend constexpr auto operator- (const U& lhs, const sized_sentinel_type& rhs) { return lhs.base() - rhs.base; }
+};
+
+#endif // TEST_STD_RANGES_ITERATORS_PREDEF_ITERATORS_ITERATORS_COMMON_TYPES_H

libcxx/test/support/test_iterators.h

 inline
 bool TEST_CONSTEXPR_CXX14
 operator!=(const forward_iterator<T>& x, const forward_iterator<U>& y)
 {
     return !(x == y);
 }
 
 template <class It>
+class non_default_constructible_iterator
+{
+    It it_;
+
+    template <class U> friend class non_default_constructible_iterator;
+public:
+    typedef          std::forward_iterator_tag                 iterator_category;
+    typedef typename std::iterator_traits<It>::value_type      value_type;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    typedef It                                                 pointer;
+    typedef typename std::iterator_traits<It>::reference       reference;
+
+    TEST_CONSTEXPR_CXX14 It base() const {return it_;}
+
+    non_default_constructible_iterator() = delete;
+
+    explicit TEST_CONSTEXPR_CXX14 non_default_constructible_iterator(It it) : it_(it) {}
+    template <class U>
+        TEST_CONSTEXPR_CXX14 non_default_constructible_iterator(const non_default_constructible_iterator<U>& u) :it_(u.it_) {}
+
+    TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
+    TEST_CONSTEXPR_CXX14 pointer operator->() const {return it_;}
+
+    TEST_CONSTEXPR_CXX14 non_default_constructible_iterator& operator++() {++it_; return *this;}
+    TEST_CONSTEXPR_CXX14 non_default_constructible_iterator operator++(int)
+        {non_default_constructible_iterator tmp(*this); ++(*this); return tmp;}
+
+    friend TEST_CONSTEXPR_CXX14 bool operator==(const non_default_constructible_iterator& x, const non_default_constructible_iterator& y)
+        {return x.it_ == y.it_;}
+    friend TEST_CONSTEXPR_CXX14 bool operator!=(const non_default_constructible_iterator& x, const non_default_constructible_iterator& y)
+        {return !(x == y);}
+
+    template <class T>
+    void operator,(T const &) DELETE_FUNCTION;
+};
+
+template <class T, class U>
+inline
+bool TEST_CONSTEXPR_CXX14
+operator==(const non_default_constructible_iterator<T>& x, const non_default_constructible_iterator<U>& y)
+{
+    return x.base() == y.base();
+}
+
+template <class T, class U>
+inline
+bool TEST_CONSTEXPR_CXX14
+operator!=(const non_default_constructible_iterator<T>& x, const non_default_constructible_iterator<U>& y)
+{
+    return !(x == y);
+}
+
+template <class It>
 class bidirectional_iterator
 {
     It it_;
 
     template <class U> friend class bidirectional_iterator;
 public:
     typedef          std::bidirectional_iterator_tag           iterator_category;
     typedef typename std::iterator_traits<It>::value_type      value_type;