On Mon, May 26, 2025 at 11:35 AM Luc Grosheintz <luc.groshei...@gmail.com> wrote:
> > > 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. > I think at this point we should perform stride computation in std::size_t. Because accessors are defined to accept size_t, the required_span_size() cannot be greater than maximum of size_t, and that limits our product of extents. > > 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 > >
