[PATCH v3 0/9] Implement layouts from mdspan.

[Luc Grosheintz]

On 5/22/25 15:21, Tomasz Kaminski wrote:
> 
> For the stride and product computation, we should perform them in
> Extent::size_type, not index_type.
> The latter may be signed, and we may hit UB in multiplying non-zero
> extents, before reaching the zero.
> 

Then I observe the following issues:

1. When computing products, the integer promotion rules can interfere.
For simplicity let's assume that int is a 32 bit integer. Then the
relevant case is `uint16_t` (or unsigned short). Which is unsigned; and
therefore overflow shouldn't be UB. I observe that the expression

   prod *= n;

will overflow as `int` (for large enough `n`). I believe that during the
computation of `prod * n` both sides are promoted to int (because the
range of uint16_t is contained in the range of `int`) and then
overflows, e.g. for n = 2**16-1.

Note that many other small, both signed and unsigned, integers
semantically also overflow, but it's neither UB that's detected by
-fsanitize=undefined, nor a compiler error. Likely because the
"overflow" happens during conversion, which (in C++23) is uniquely
defined in [conv.integral], i.e. not UB.

draft: https://eel.is/c++draft/conv.integral
N4950: 7.3.9 on p. 101

The solution I've come up is to not use `size_type` but
   make_unsigned_t<decltype(index_type{} * index_type{})>

Please let me know if there's a better solution to forcing unsigned
math.

Godbolt: https://godbolt.org/z/PnvaYT7vd

2. Let's assume we compute `__extents_prod` safely, e.g. by doing all
math as unsigned integers. There's several places we need to be careful:

   2.1. layout_{right,left}::stride, these still compute products, that
   overflow and might not be multiplied by `0` to make the answer
   unambiguous. For an empty extent, any number is a valid stride. Hence,
   this only requires that we don't run into UB.

   2.2. The default ctor of layout_stride computes the layout_right
   strides on the fly. We can use __unsigned_prod to keep computing the
   extents in linear time. The only requirement I'm aware of is that the
   strides are the same as those for layout_right (but the actual value
   in not defined directly).

   2.3 layout_stride::required_span_size, the current implementation
   first scans for zeros; and only if there are none does it proceed with
   computing the required span size in index_type. This is safe, because
   the all terms in the sum are non-negative and the mandate states that
   the total is a representable number. Hence, all the involved terms are
   representable too.

3. For those interested in what the other two implementions do: both
fail in some subset of the corner cases.

Godbolt: https://godbolt.org/z/vEYxEvMWs