[libc++] mdspan: implement layout_right

[crtrott]

Summary

This commit implements layout_right in support of C++23 mdspan (https://wg21.link/p0009).
layout_right is a layout mapping policy whose index mapping corresponds to the memory layout of multidimensional C-arrays, and is thus also referred to as the C-layout.

Co-authored-by: Damien L-G <[e-mail]>

[crtrott]

Fix AIX build which has a global map_t symbol in a system header ...

[EricWF]

Great tests.

libcxx/include/__mdspan/layouts.h

34 ↗

(On Diff #525154)

I don't like adding commented or ifdefed out code like this.

Maybe just leave a comment declaration.

[crtrott]

libcxx/include/__mdspan/layouts.h

34 ↗

(On Diff #525154)

Yeah thats fine I can do that. Just gonna wait for a bit more feedback before submitting a revision.

[ldionne]

libcxx/include/__mdspan/extents.h

459

__is_index_in_extent

480

Either rename to _impl or inline it via a lambda below.

libcxx/include/__mdspan/layout_right_mapping.h

17 ↗

(On Diff #525154)

Let's make this __mdspan/layout_right.h since we're basically implementing the whole class here even though we have a "fwd decl" somewhere else.

28 ↗

(On Diff #525154)

Not necessary anymore?

46–47 ↗

(On Diff #525154)

Do you have a .verify.cpp test for this diagnostic?

I think you want something like:

//expected-error-re@*:* {{{{(static_assert|static assertion)}} failed {{.*}}MESSAGE}}

see libcxx/test/libcxx/algorithms/bad_iterator_traits.verify.cpp for example.

50–54 ↗

(On Diff #525154)

Note to self: those are tested (thanks!).

57 ↗

(On Diff #525154)

I don't think we need to make a copy here.

63–66 ↗

(On Diff #525154)

I think we could do this instead:

index_type __prod              = __ext.extent(0);
for (rank_type __r = 1; __r < extents_type::rank(); __r++) {
    bool __overflowed = __builtin_mul_overflow(__prod, __ext.extent(__r), &__prod);
    if (__overflowed)
        return false;
}

This would avoid the division.

78 ↗

(On Diff #525154)

Do you have a test for the noexcept-ness? Edit: Yes.

84 ↗

(On Diff #525154)

Do you have a test that checks that mapping is not constructible (using a type trait) if the extents are not constructible? This is important to make sure that you implemented this using requires (or enable_if) as opposed to it just being a hard error.

116 ↗

(On Diff #525154)

Can we move this private block to the end of the class? I usually don't mind implementation details in the middle of the class, but this one is quite large so it obscures the public API a bit too much.

150 ↗

(On Diff #525154)

Please make sure you have SFINAE (or better, concepts) tests for those requirements.

155 ↗

(On Diff #525154)

return [&]<size_t ..._Pos>(index_sequence<_Pos...>) {
  index_type __result = 0;
  ((result = __idx + __extents_.extent(_Pos) * __result))...; // exercise for the reader :-)
  return __result;
}(index_sequence_for<_Indices...>{});

170 ↗

(On Diff #525154)

This is always true, so can be removed.

176 ↗

(On Diff #525154)

And this isn't necessary anymore either.

180 ↗

(On Diff #525154)

Can you make sure you have a test that we SFINAE away when the ranks are different?

libcxx/include/__mdspan/layouts.h

17 ↗

(On Diff #525154)

Let's move this to libcxx/include/__fwd/mdspan_layouts.h. While those are technically not forward declarations, they're close enough.

48–55 ↗

(On Diff #525154)

+1 let's remove those until they are implemented, or make them a comment.

libcxx/test/std/containers/views/mdspan/layout_right/conversion.pass.cpp

1 ↗

(On Diff #525154)

Let's name this ctor.mapping.pass.cpp

libcxx/test/std/containers/views/mdspan/layout_right/ctor_default.pass.cpp

1 ↗

(On Diff #525154)

Let's use ctor.default.pass.cpp, it's more consistent with what we're doing recently.

libcxx/test/std/containers/views/mdspan/layout_right/ctor_extents.pass.cpp

1 ↗

(On Diff #525154)

ctor.extents.pass.cpp

libcxx/test/std/containers/views/mdspan/layout_right/properties.pass.cpp

37

Please use a classic constexpr test here -- I'd like to make sure that these can also be called at runtime.

For example, your test (as currently written) would pass if we did something like:

static constexpr bool is_always_unique() noexcept {
  if (!std::is_constant_evaluated())
    throw "ahah";
  return true;
}

[crtrott]

libcxx/include/__mdspan/layout_right_mapping.h

155 ↗

(On Diff #525154)

template<class ... _Indices>
constexpr index_type  operator() (_Indices ... __idx) const {
   return [&]<size_t ... _Pos>(index_sequence<_Pos...>) {
     index_type __res = 0;
     ((__res = static_cast<index_type>(__idx) + __extents_.extent(_Pos) * __res),...);
     return __res;
   }(make_index_sequence<sizeof...(_Indices)>());
 }

[Mordante]

Thanks for working on this! I didn't compare the code with the Standard. A few minor nits.

libcxx/docs/Status/Cxx23.rst

43

libcxx/include/__mdspan/extents.h

458

I prefer to use concepts where possible, in requires and if constexpr. But I really would like them in requires. I still have hopes compilers can create better diagnostics for concepts than type traits. Please look at other places too.

libcxx/include/__mdspan/layout_right_mapping.h

71 ↗

(On Diff #525154)

Can this be moved to the other static_assert in this class?

libcxx/include/__mdspan/layouts.h

17 ↗

(On Diff #525154)

I would strongly suggest to use the name libcxx/include/__fwd/mdspan.h instead. The reason is the module logic of D144994 would need a special case for mdspan_layouts.h but works out of the box with mdspan.h

[crtrott]

Addressing the comments on the first round of reviews.

[crtrott]

Fix screw up in diff

[Mordante]

I didn't look closely at the patch, but I noticed an omission.

libcxx/include/__fwd/mdspan.h

44

FYI I expect the CI to fail in C++ Module std. This should be fixed by uncommenting using std::layout_right in libcxx/modules/std/mdspan.cppm. Module support has been added recently.

[crtrott]

Fixing formatting.

[crtrott]

Still problems with generated output, I can't reproduce locally yet.

[ldionne]

LGTM with a few comments! Thanks!

libcxx/include/__mdspan/layout_right.h

108

This doesn't seem to be tested directly.

libcxx/test/std/containers/views/mdspan/layout_right/ctor.default.pass.cpp

34–35

You should either address this or remove the comment.

39

This would belong to the direct test for required_span_size() instead, for example.

libcxx/test/std/containers/views/mdspan/layout_right/ctor.mapping.pass.cpp

80

(maybe elsewhere if you copy-pasted, just grep)

libcxx/test/std/containers/views/mdspan/layout_right/index_operator.pass.cpp

32

Let's use libcxx/test/std/containers/views/mdspan/extents/ConvertibleToIntegral.h (which you can move to libcxx/test/std/containers/views/mdspan/ instead).

87–91

Let's test with a few 1-sized dimensions.

[ldionne]

libcxx/test/std/containers/views/mdspan/layout_right/ctor.mapping.pass.cpp

23

I don't think you're using anything from that header.

[crtrott]

Address last comments

[crtrott]

libcxx/include/__mdspan/layout_right_mapping.h

71 ↗

(On Diff #525154)

I think it would make it less readable. We need to test the first static_assert before we use the template parameter for dependent types, and the second static_assert impl requires those dependent types.

[ldionne]

LGTM with passing CI.

[crtrott]

With assertion enabled one of the tests we expanded in the last commit hit the default maximum step limit in consteval. I split the test now and run the large iteration case only in runtime mode, not in consteval.

[ldionne]

LGTM with nits.

libcxx/test/std/containers/views/mdspan/layout_right/required_span_size.pass.cpp

13–18

This is wrong.

26–34

[crtrott]

Fix wrong comment and test name for required_span_size

[ldionne]

libcxx/test/std/containers/views/mdspan/layout_right/required_span_size.pass.cpp

29

I think this comment can be removed.

[ldionne]

libcxx/test/std/containers/views/mdspan/layout_right/assert.stride.pass.cpp

2

This is a nitipck, but I noticed this upon applying the patch. You're missing the first line of the license comment.

Don't change anything, I'm editing upon committing. Just FYI.