Behavior for numeric overflows/underflows/etc in algorithms

[inexorabletash]

Some spec algorithms steps perform math that could overflow/underflow in implementations that do the arithmetic using particular types, such as uint32_t. This has been raised in #610 (comment) and #582 (comment) and probably elsewhere.

There are a handful of nuances here:

• This issue isn't talking about places where there are input parameter constraints that can't be satisfied by Web IDL types, e.g. a floating point parameter must be greater than zero, or where one parameter must be greater than another, etc. Those need explicit steps.
• This issue isn't talking about implementation-specific limits on operator behavior, e.g. maximum number of tensor dimensions, etc.
• This issue is talking about places where intermediate value could overflow, just because the implementation is doing the math in a specific space e.g. using 32- or 64-bit intermediate values, because 128-bit values aren't supported or have poor performance.
• This issue is maybe talking about places where the final value of a calculation has limitations imposed by constraints in other parts of the platform, e.g. running into 2^32, 2^53, 2^64 or other specified limits for objects (Arrays, ArrayBuffers, etc). Some of those limitations have relaxed over time (e.g. maximum ArrayBuffer size).

https://source.chromium.org/chromium/chromium/src/+/main:components/ml/webnn/graph_validation_utils.cc;l=36 is an implementation example where a filter size is constrained to be a uint32 even though larger values could be supported (I think?)

I checked with some other spec experts. Approaches really vary depending on the spec's domain.

Most specs implicitly follow the guidance from Infra which says this on algorithm limits:

A document using the Infra Standard generally should not enforce specific limits on algorithm inputs with regards to their size, resource usage, or equivalent. This allows for competition among user agents and avoids constraining the potential computing needs of the future.

This seems like good practice to follow. On the other hand, some of the more fundamental specs (e.g. ECMA-262 - the JavaScript definition) need to specify in great detail how calculations are performed and deal with all of the fun edge cases. This is done with incredibly detailed algorithms and the use of helpers such as ℝ() (for converting to reals) and 𝔽() (for converting to doubles), along with consistent spec notation like ! (asserting that an expression will not throw) and ? (signaling that an expression may throw, and exceptions should propagate)

I think that for WebNN we have a range of options, and we may change our approach over time - e.g. start off without trying to capture this fine level of detail, but then introduce more rigor over time. Some options:

• Do nothing - when this comes up in implementation or spec work, link to this issue.
• Add a generic statement to the spec referencing the Infra note.
• Introduce helpers and/or shorthand like ECMA-262's but for checked math, e.g. 𝕌32(...) meaning "if the result of this calculation doesn't fit into a uint32, then throw an exception. Bikeshed supports text macros to make authoring this easier.
• Introduce steps much like the implementation that explicitly validate intermediate values of operations, calling out the limits and throwing exceptions.

I'd lean towards the lightweight former options, for now at least, but with these notes:

• Noting cases where this applies by commenting on this issue will help track them.
• When implementing algorithms, distinguishing between implementation-imposed limitations and logical limitations can be very subtle.
• There's a valid argument to over-specify and later relax, vs. under-specifying and later discovering interop issues.

[inexorabletash]

Process-wise, I'd propose that we hear from the editors and WG here, pick an approach we're happy with for now, then close this issue knowing that we might revisit later.

CC: @fdwr @huningxin @zolkis

[zolkis]

Add a generic statement to the spec referencing the Infra note.

This certainly makes sense.

Introduce helpers and/or shorthand like ECMA-262's but for checked math, e.g. 𝕌32(...) meaning "if the result of this calculation doesn't fit into a uint32, then throw an exception. Bikeshed supports text macros to make authoring this easier.

Not yet sure about this. But interop is a primary concern, so all means helping (but not overspecifying) it should be considered.

I'd lean towards the lightweight former options, for now at least, but with these notes:

Agreed with the notes, except I'd think more about the third note (and how to make those detectable with interop tests).

[inexorabletash]

Some examples of intermediate values that might overflow:

• gru and gruCell, their steps compare a dimension with 3 * hiddenSize that might be a invalid unsigned long.
• lstm and lstmCell, their steps compare a dimension with 4 * hiddenSize that might be a invalid unsigned long.

[inexorabletash]

Quick update here - @huningxin put together a spreadsheet enumerating places where the Chromium prototype does "checked math" to catch overflows (etc) and generates exceptions which aren't captured in the spec. The plan was to propose spec changes to capture those; once complete this issue can be closed.