Possible bug in `required_span_size`

I've come across an issue which I don't completely understand but which feels like a bug in required_span_size. A working example is here: https://godbolt.org/z/Y8bcnGeEj

My understanding of required_span_size is that it allows a span to be constructed which contains all the referenceable data from an mdspan. So if I have an mdspan called m, its elements will all be contained in std::span(m.data_handle(), required_span_size()) and that the span will be minimal (i.e., just big enough to store the data without padding on the end). Is that the correct intention?

Here is a cut-down reproducer for the issue I see:

// Original mdspan across a 4x5 data block.
std::mdspan<float, std::extents<size_t, 4, 5>> m1(array);

// The bottom-right 2x2 matrix
auto m2 = submdspan(m1, std::pair(2, 4), std::pair(3, 5));

// Create a span from the submdspan. BUT, this span goes past the end of  `array` 
auto m2span = std::span(m2.data_handle(), m2.mapping().required_span_size());
// required_span_size() is bigger than m2.mapping()(1, 1) + 1

The final span is outside the bounds of the original parent data so it allows access to data it shouldn't be able to get at.

@danieltowner Thanks for posting! It looks like the implementation disagrees with the Standard, meaning that the implementation has a bug. I'll start by explaining what the Standard would compute here. Then, I'll find the implementation bug.

[mdspan.layout.reqmts] 12 describes required_span_size.

Returns: If the size of the multidimensional index space m.extents() is 0, then 0, else 1 plus the maximum value of m(i...) for all i.

In your example, m1.mapping() has stride(0) = 5 and stride(1) = 1. The starting offset of m2 is m1.mapping()(2, 3), which is 2 * 5 + 3 * 1 = 13. m2.mapping() has the same strides as m1. (Merge of P2642 affects the layout type, but not the strides.) Extents of m2 are (2, 2). Thus, m2.mapping().required_span_size() should be m2.mapping()(1, 1) + 1, which is 1 * 5 + 1 * 1 + 1 = 7. As your example shows, the implementation disagrees with this.

It looks like you're using the single-header version of mdspan. A brief experiment shows that m2's layout_type is layout_right_padded<5>. The implementation of required_span_size() thus looks like this.

  MDSPAN_INLINE_FUNCTION constexpr index_type
  required_span_size() const noexcept {
    if constexpr (extents_type::rank() == 0) {
      return 1;
    } else if constexpr (extents_type::rank() == 1) {
      return exts.extent(0);
    } else {
      index_type value = 1;
      for (rank_type r = 0; r < extent_to_pad_idx; ++r) {
        value *= exts.extent(r);
      }
      return value * padded_stride.value(0);
    }
  }

1 * 2 * 5 is 10, the value that you observed. This value is incorrect. The calculation that layout_stride::mapping::required_span_size does would be correct for this case. (See line 469 of layout_stride.hpp.)

The offending code starts at line 741 of layout_padded.hpp. We would also need to fix layout_left_padded::mapping::required_span_size.

kokkos / mdspan

Possible bug in `required_span_size` #362