Change zig int promotion / cast rules

[lerno]

Some background and comparisons can be found in the following blog articles: On arithmetics and overflow, Overflow trapping in practice.

Current rules in Zig using peer resolution + assigned type has issues. One is that occasionally the type of a literal cannot be resolved, but also the peer resolution gives unexpected results. This proposal does affect the mod arithmetics as well, since they become less useful.

The main idea of the proposal is make all integer arithmetics act as if it was done with bigint, but trap / UB if the conversion any truncation occurs.

EDIT I've updated the algorithm quite a bit, although the overall behaviour (as stated above) should be the same.
EDIT2 Added blog articles as references.

To explain the algorithm, we need to define the following:

1. The target type, this is the type that the variable or parameter has that we assign the expression to. It may be empty.
2. The resulting type, this is the type we are performing calculations using.

In addition to this we define a base arithmetics bit width (BABW), which typically is 32 or 64 which is the platform dependent minimum type that is efficient to perform calculations on and a max arithmetics bit width (MABW) which is the corresponding maximum efficient type.

The following occurs:

1. For each operand, recursively resolve the type passing down the target type. E.g. analysing i16 b = (a + b) * c we first analyse, a, then b, then a + b and c, then (a + b) * c. In each of these we pass along the i16 type.
2. If casting expression is reached, the target type is set to empty when recursively processing its sub expression.
3. For each operand, if it has a fixed type size and it is greater than the target type then this is a compile type error. E.g. i16 s = 1 + @as(i16, 1) would be an error as the right sub expression is of type i32, which is wider than i16.
4. Looking at the operands, find the smallest power of 2 integer type that can represent the ranges of both operands, that is at least the same as BABW. For instance if BABW = 32, then i16 + i31 => i32 i32 + u32 => i64 i8 + u16 => i32 u8 + u16 => u32. This is the resulting type. If the required width would exceed MABW, then this is a compile time error.
5. If the width of the resulting type is smaller than the bit width of the target type, change the bit width of the resulting type to be the same as the target type. E.g. u64 = i8 + u16 => resulting type is i64.
6. Perform the calculation, with overflow being trapped (debug mode) or considered undefined behaviour (release mode).
7. If the resulting type is of different signedness from the target type, cast the result to the target type. If under/overflow would occur, then this is trapped (debug mode) or considered undefined behaviour (release mode).

Examples:

var x: u8 = 0xFF;
var b: i16 = 0x7FFF;

var z: i32 = x + b + 3;
// Same as today's:
var z: i32 = @as(i32, x) + @as(i32, b) + @as(i32, 3);
// Note that we take advantage of the fact that overflow is UB/Trap

var sz: i16 = x + b + 3;
// Same as today's:
var sz: i16 = @truncate(i16, @as(i32, x) + @as(i32, b) + @as(i32, 3));

var sz2: i16 = @as(i16, x + b + 3);
// Same as today's:
var sz2: i16 = x +% @as(i16, b) +% 3;

Some more complex examples:

var a: i32 = 1;
var b: u8 = 3;
var c: i16 = 4;
var e: u32 = 5;
var f: i64 = 6;

var g: i32 = a + (b * a) / (c * f); // Error, requires explicit cast due to f > i32
var h: i32 = a + (b * c);
// Same as today's
var h: i32 = a + (@as(i32, b) * @as(i32, c));
// Uses overflow UB for + and *

var i: i32 = b + (a * e);
// Same as today's
var i: i32 = @intCast(@as(i64, b) + (@as(i64, a), @as(i64, e)));
// Uses overflow UB for + and *, then truncate to check it is in range.

var j: i32 = e - 10;
// Same as today's
var i: i32 = @intCast(e - @as(u32, 10);
// Note that an extra rule can be inserted to instead make this:
var i: i32 = @intCast(@as(i64, e) - @as(i64, 10));

As an optional extra rule we can say that given an expression with a high type A and a low type B, doing & with a constant of bit size N will reduce the size of the low type to N:

var a: i16 = 12345;
var b: u8 = a & 0xFF;
var c: u1 = a & 0x01;

Note that #7416 also touches on some aspects of this.

[lerno]

WeI want to add that if there is interest in this feature, it's possible to describe the above algorithm in a much simpler manner. But if there is scant interest I won't bother.

To reiterate, the behaviour is basically "behave as if the calculation is done with infinite bit width everywhere then truncate with runtime trap/UB if truncation is not lossless, and issue a compile time error if the target type is smaller than one or more of the original types of the operands"

[kyle-github]

Thanks for the synopsis, @lerno.

It looks like point 9 and your second example are in conflict. The target type in your second example is i32 but you are not showing a trap. Did you mean to have this the other way? That there is no automatic coercion to a smaller type and that should trap?

Doesn't the the overall size depend on the operation? I.e. addition can only add a bit (assuming the operands are the same signedness), but multiplication can add the bit lengths together. For instance, multiplying two i8 can give a result that needs to be in i16 if you want it without loss. Subtraction and division follow similar logic.

I am a little concerned already that there is a lot of automatic coercion going on and that violates the Zen of Zig.

I thought the rules were roughly:

1. if the operands differ in signedness, promote the unsigned operand to a signed operand one bit larger. I.e. u9 gets promoted to i10. Otherwise they stay the same signedness and size.
2. The result must match the signedness of the promoted operands from step 1.
3. If the operation is add, the result must be at least the bit width of the largest operand plus one.
4. If the operation is multiplication, the result must be at least the bit width of a sum of the bit widths of the converted operands.

Etc.

[lerno]

@kyle-github I think I need to clarify a bit. Basically any arithmetic operation would in itself trap/UB, so essentially we have two places we trap: (1) in the narrowing (2) in the operation itself. This is why there is no need to do the widening you do in 3/4.

I've updated the algorithm above significantly. Hopefully it's more clear now.

[matu3ba]

@lerno Briefly mentioning how c-types (should) behave would make the picture more complete. Looking forward to the update.

[lerno]

I would like to amend the proposal with a simpler model:

1. Target type is the LHS, or if the LHS is an unsigned value, the LHS bitwidth + 1 as signed value.
2. Check all leaf operands so that the type has a smaller or same bit width as the target type. Anything else is a compile time error.
3. All lead operands are promoted to at least BABW.
4. All unsigned operands are promoted to bitwidth + 1 as signed value.
5. Promote both operands to the maximum bit width.
6. Perform all operations with trapping semantics.
7. Use a trapping cast to the original LHS

An open question is how casts interact with this. Behaviour in the "complex examples" are same for the above algorithm.

Downside here is that something like u64 + i64 would be promoted to i65 and use > 64 bit arithmetics. In practice, as long as the compiler can prove that only the lower bits are used it can use 64 bit arithmetics. So u64 + i64 is fine, but i64 / (u64 + i64) would need to use i128 instructions.

Because the algorithm uses u64 -> i128 to prevent intermediary value overflow, we have similar issues with pure u64. So u64 / (u64 + u64) would unfortunately use i128 as well.

[matu3ba]

All lead operands are promoted to at least BABW.

What does BABW mean?

Promote both operands to the maximum bit widt

Promote both all operands to the maximum bit widt? Or for each computation? I guess you mean all operands of all operations on the RHS.

An open question is how casts interact with this.

Explicit casts are usually very undescriptive/implicit about behavior (take C++ with 4 different casts and more methods to cast pointers up or down). Rust thinks how to move completely away from them and most languages try to, because the behavior is bad for code review.
Explicit casts can for example define 1.truncation of values and 2.conversion between types and you want both to be very explicit and not cluttered in an arithmetic expression.

Because the algorithm uses u64 -> i128 to prevent intermediary value overflow, we have similar issues with pure u64. So u64 / (u64 + u64) would unfortunately use i128 as well.

u64 + u64 can overflow on u64, so only the base "is wasted". Can you think of a better example? Maybe u64 / u64 / u64 or u64 - u32 - u16 - u8 (anything shrinking the possible target value set in each operation)?

1. It would be very helpful to also be open about the performance costs of trapping and using bigger types and why for example Rust decided against it.
2. Rust suggested something like this to set them in a painless way, but this is relative verbose.
   Would you then suggest to use the default of checked(...) in release-safe and unchecked(...) in release-fast?
3. I feel like a more painless way to annotate the safe and the fast behavior for expressions statements would be more exact (think of
   var x operator for safe x + y; and var x operator for fast x + y;),
   because file-, function-, or scope-level clutters the file (the programmer may know and annotate invariants on dynamic program states).

[lerno]

@matu3ba I define BABW as the lowest bit width to perform calculations, typically 32 bits on 32/64 bit targets. 16 bits on 16 bit targets.

Promote both operands to the maximum bit widt? Or for each computation? I guess you mean all operands of all operations on the RHS.

Yes, the left hand side. The change is depth first, casting the leaves will naturally propagate the change upwards. Given a + (b * c) we promote a, b and c. This will naturally ensure that (b * c) is also at least as wide etc.

Explicit casts are usually very undescriptive/implicit about behavior

An example I often take is: uint32var = uint32var + int16update. There is no way to cast int16update to get the correct behaviour in the face of unsigned overflow. There is either: (1) bitcasting, then doing a +% but this bypasses underflow protection (2) extension to signed 64 bits and then a trapping narrowing cast on the result of the add. The latter is the secure one, but I suspect few will use it. Casts often look like people spent some time thinking about them, that is not necessarily true. In C, explicit casting of what actually is implicit casts anyway will mostly give the correct behaviour (comparisons being a notable exception), but that's not necessarily true in other schemes.

It would be very helpful to also be open about the performance costs of trapping and using bigger types and why for example Rust decided against it.

I've read through the correspondence on the Rust mailing-list around 2014. There were many different ideas at the time. I didn't see any proposal for using a bigger type. The cost of trapping was discussed a lot, and ideally many would have preferred traps on both release and debug, but fear of bad performance seemed to have weighted most heavily. There is the "As-if infinitely ranged integer" model (also known as the AIR model) which potentially allowed trapping with delayed checks, so that the performance cost would only be in the range of 6%. However, since this was an academic paper with unclear ramifications, their tight deadline (they were going to 1.0 before the end of the year) made them dismiss this solution.

Some argued for wrapping semantics, but with special trapping overflow operators, but not enough people liked that idea.

[lerno]

In regards to checked(foo + bar) vs foo ~+ bar, I think the first is easier to write, but has more difficulties in terms of transforming a more complex expression.

However I also want to stress that the problem is not just about trapping, but also that unsigned integer overflow has very significant footguns. (1) +/- is no longer associative nor commutative (2) it is very complicated to safely combine unsigned and signed numbers.

This problem becomes more problematic when there is explicit widening:

The below would be valid Zig:

someU32 = someU8 * someU16 + someU32;

But for Rust the widening must be explicit:

someU32 = u32::from(u16::from(someU8) * someU16) + someU32;

Here it's easier to see where potential overflows can occur. Since I need to cast anyway, it's simpler to do:

someU32 = u32::from(someU8) * u32::from(someU16) + someU32;

Which doesn't run into the same risk of overflow. Because the casts are explicit, the unsigned overflow trapping isn't as dangerous. Because the widening is implicit in Zig, it's even less clear where we run into chances of overflow.

[matu3ba]

@lerno Footguns are always bad and not being able to specify local expression behavior with as minimal amount of keypresses and visual clutter is too.

What about defining compiler intrinsics like

someU32 = @op_to_lhs(someU8 * someU16 + someU32);
someU32 = @safe(someU8 * someU16 + someU32);
someU32 = @fast(someU8 * someU16 + someU32);

or adapting grammar like

someU32 =cast_lhs someU8 * someU16 + someU32;
someU32 =safe someU8 * someU16 + someU32;
someU32 =fast someU8 * someU16 + someU32;

or shorter

someU32 =c someU8 * someU16 + someU32;
someU32 =s someU8 * someU16 + someU32;
someU32 =f someU8 * someU16 + someU32;

?

I think the default-semantic of = etc on arithmetic expresssions could be described as fast or am I also wrong on this?

[lerno]

Although you could do this I @matu3ba I think the problem is deeper and is about a more fundamental stance on implicit widening and trapping.

In order to make code secure and bug free the language should try to make the correct way the obvious solution. If we consider the simple u32 = u32 + i16 how do we guide the user to the safe version of that? It's good if there is some language mechanism that just works 95% of all cases and makes the user aware of the remaining 5%.