The C3 Blog¶

October 5, 2021
4 min read

Fixing "bugs" in our proposal

Originally from: https://c3.handmade.network/blog/p/8138-fixing_bugs_in_our_proposal

When we last left off we had our "attempt 3" which seemed like a promising candidate to research. We expected some problems and here are two:

What is the behaviour of when there is both "top down" casts and peer casts? This was never discussed. For example: x_u64 = a_i32 + b_u32. As we will see, making the wrong choice here will create overflow bugs.
When are constants folded? This matters since we only recursively applied casts the right-hand side is a binary expression. But does that check happen before or after constant folding? The proposal seems to imply it's after, but that would give weird semantics.

Top down casts & peer casts

Our "test" here is this expression:

int32_t a = ...;
uint32_t b = ...;
uint64_t c = a + b;

// Peer -> top down:
uint64_t c = (uint64_t)a + (uint64_t)(int32_t)(b)

For some surprising results, set b = 0x80000000U and a = 1 → c = 0xffffffff80000001ULL. Top down → peer gives us our expected c = 0x80000001ULL.

It's very important that the resolution works in this order:

Check that a and b are valid widening safe expressions (see previous article for definition).
Evaluate a and b in isolation, before actually evaluating the binary expression.
Cast both to uint64_t (note that this differs from peer resolution which would preserve the signedness)
Semantically check the binary expression.

This gives us uint64_t c = (uint64_t)a + (uint64_t)b which presumably is what we want.

Another thing we need to note though, is that only integer widening + signedness changes happen this way. For example something like ptrdiff_t x = ptr1 - ptr2 shouldn't start making casts on the pointers!

When constant folding happens

Constants folded are either constants or literals (assume int 32 bit, long 64 bit):

const int FOO = 1;
const int BAR = 2;
int y = ...;
int i = ...;
int j = ...;
long a1 = y + (i + j); // Error, needs explicit cast.
long a2 = y + (FOO + BAR); // Error?
long a3 = y + (1 + 2); // Error?

Just arguing for consistency would seem to require that semantics are the same for variables and constants, and by extension also literals. This might be a little disappointing, but consider if one would expect a to be -1, which would be the case if we would fold constants first:

long a = INT_MAX * 2 + 1;

With late folding the result becomes:

long a = INT_MAX * 2 + 1; // Error, needs explicit cast.
long a2 = INT_MAX * 2; // => 0xfffffffe
long a3 = INT_MAX + 1; // => 0x80000000

Which is probably as good as it gets.

Another case is when the left hand side unsigned. In this case we do not actually perform the top down widening, but instead have a general cast on the result:

uint b = INT_MAX * 2 + 1; // => 0xffffffff

Conclusion

So far so good, there is no showstopper here, but this serves as a reminder and example of how easy it is to forget implications.

Comments

Comment by Christoffer Lernö

When we last left off we had our "attempt 3" which seemed like a promising candidate to research. We expected some problems and here are two:

What is the behaviour of when there is both "top down" casts and peer casts? This was never discussed. For example: x_u64 = a_i32 + b_u32. As we will see, making the wrong choice here will create overflow bugs.
When are constants folded? This matters since we only recursively applied casts the right-hand side is a binary expression. But does that check happen before or after constant folding? The proposal seems to imply it's after, but that would give weird semantics.

Top down casts & peer casts

Our "test" here is this expression:

int32_t a = ...;
uint32_t b = ...;
uint64_t c = a + b;

// Peer -> top down:
uint64_t c = (uint64_t)a + (uint64_t)(int32_t)(b)

For some surprising results, set b = 0x80000000U and a = 1 → c = 0xffffffff80000001ULL. Top down → peer gives us our expected c = 0x80000001ULL.

It's very important that the resolution works in this order:

Check that a and b are valid widening safe expressions (see previous article for definition).
Evaluate a and b in isolation, before actually evaluating the binary expression.
Cast both to uint64_t (note that this differs from peer resolution which would preserve the signedness)
Semantically check the binary expression.

This gives us uint64_t c = (uint64_t)a + (uint64_t)b which presumably is what we want.

Another thing we need to note though, is that only integer widening + signedness changes happen this way. For example something like ptrdiff_t x = ptr1 - ptr2 shouldn't start making casts on the pointers!

When constant folding happens

Constants folded are either constants or literals (assume int 32 bit, long 64 bit):

const int FOO = 1;
const int BAR = 2;
int y = ...;
int i = ...;
int j = ...;
long a1 = y + (i + j); // Error, needs explicit cast.
long a2 = y + (FOO + BAR); // Error?
long a3 = y + (1 + 2); // Error?

Just arguing for consistency would seem to require that semantics are the same for variables and constants, and by extension also literals. This might be a little disappointing, but consider if one would expect a to be -1, which would be the case if we would fold constants first:

long a = INT_MAX * 2 + 1;

With late folding the result becomes:

long a = INT_MAX * 2 + 1; // Error, needs explicit cast.
long a2 = INT_MAX * 2; // => 0xfffffffe
long a3 = INT_MAX + 1; // => 0x80000000

Which is probably as good as it gets.

Another case is when the left hand side unsigned. In this case we do not actually perform the top down widening, but instead have a general cast on the result:

uint b = INT_MAX * 2 + 1; // => 0xffffffff

Conclusion

So far so good, there is no showstopper here, but this serves as a reminder and example of how easy it is to forget implications.

October 4, 2021
14 min read

Attempting new C3 type conversion semantics

Originally from: https://c3.handmade.network/blog/p/8134-attempting_new_c3_type_conversion_semantics

As a reminder, in the last article I listed the following strategies:

Strategies for widening

Early fold, late cast (deep traversal).
Left hand side widening & error on peer widening.
No implicit widening.
Peer resolution widening (C style).
Re-evaluation.
Top casting but error on subexpressions.
Common integer promotion (C style).
Pre-traversal evaluation.

Strategies for narrowing

Always allow (C style).
Narrowing on direct literal assignment only.
Original type is smaller or same as narrowed type. Literals always ok.
As (3) but literals are size checked.
No implicit narrowing.

Strategies for conversion of signed/unsigned

Prefer unsigned (C style).
Prefer signed.
Disallow completely.

To begin with, we'll try the "Early fold, late cast" for widening. This is essentially a modification on the peer resolution widening.

Attempt 1 - "Early fold, late cast"

Here we first fold all constants, then "peer promote" the types recursively downwards. How this differs from C is illustrated below:

int32_t y = foo();
int64_t x = bar();
double w = x + (y * 2);
// C semantics:
// double w = (double)(x + (int64_t)(y * 2));
// Early fold, late cast:
// double w = (double)(x + ((int64_t)y * (int64_t)2));

So far this looks pretty nice, but unfortunately the "early fold" part has less positive consequences:

int32_t y = foo();
int64_t x = bar();
int32_t max = INT32_MAX;
double w = x + (y + (INT32_MAX + 1));
double w2 = x + (y + (max + 1));
// Early fold, late cast:
// double w = (double)(x + ((int64_t)y + (int64_t)-2147483648));
// double w2 = (double)(x + ((int64_t)y 
//             + ((int64_t)max + (int64_t)1)));

The good thing about this wart is that it is at least locally observable - as long as it's clear from the source code what will be constant folded.

All in all, while slightly improving the semantics, we can't claim to have solved all the problems with peer resolution while the semantics got more complicated.

Attempt 2 "Re-evaluation"

This strategy is more theoretical than anything. With this strategy we attempt to first evaluate the maximum type, then re-evaluate everything by casting to this maximum type. It's possible to do this in multiple ways: deep copying the expression, two types of evaluation passes etc.

Our problematic example from attempt 1 works:

int32_t y = foo();
int64_t x = bar();
int32_t max = INT32_MAX;
double w = x + (y + (INT32_MAX + 1));
// => first pass type analysis: int64_t + (int32_t + (int + int))
// => max type in sub expression is int64_t
// => double w = (double)(x + ((int64_t)y 
//               + ((int64_t)INT_MAX + (int64_t)1)));

However, we somewhat surprisingly get code that are hard to reason about locally even in this case:

// elsewhere int64_t x = ... or int32_t x = ... 
int32_t y = foo();
double w = x + (y << 16);
// If x is int64_t:
// double w = (double)(x + ((int64_t)y << 16));
// If x is int32_t
// double w = (double)(x + (y << 16));

Here it's clear that we get different behaviour: in the case of int32_t the bits are shifted out, whereas for int64_t they are retained. There are better (but more complicated) examples to illustrate this, but it is proving that even with "ideal" semantics, we lose locality.

Rethinking "perfect"

Let's go back to the example we had with Java in the last article:

char d = 1;
char c = 1 + d; // Error
char c = (char)(1 + d); // Ok

In this case the first is ok, but the second isn't. The special case takes care of the most common use, but for anything non-trivial an explicit cast is needed.

What if we would say that this is okay:

int64_t x = foo();
int32_t y = bar();
double w = x + y

But this isn't:

int64_t x = foo();
int32_t y = bar();
double w = x + (y + y);
//             ^^^^^^^
// Error, can't implicitly promote complex expression
// of type int32_t to int64_t.

Basically we give up widening except for where we don't need to recurse deep into the sub-expressions. Let's try it out:

Attempt 3: Hybrid peer resolution and no implicit cast

We look at our first example.

int32_t y = foo();
int64_t x = bar();
double w = x + (y * 2); // Error

This is an error, but we can do two different things in order to make it work, depending on what behaviour we want:

// A
double w = x + (y * 2LL); // Promote y
// B
double w = x + (int64_t)(y * 2); // Promote y * 2

Yes, this some extra work, but also note that suddenly we have much better control over what the actual types are compared to the "perfect" promotion. Also note that changing the type of x cannot silently change semantics here.

The second example:

int32_t y = foo();
int64_t x = bar();
int32_t max = INT32_MAX;
double w = x + (y + (INT32_MAX + 1)); // Error

Again we get an error, and again there are multiple ways to remove this ambiguity. To promote the internal expression to use int64_t, we just have to nudge it a little bit:

double w = x + (y + (INT32_MAX + 1LL)); // Ok!

And of course if we want C behaviour, we simply put the cast outside:

double w = x + (int64_t)(y + (INT32_MAX + 1)); // Ok!

Note here how effective the type of the literal is in nudging the semantics in the correct direction!

Adding narrowing to "attempt 3"

For narrowing we have multiple options, the simplest is following the Java model, although it could be considered to be unnecessarily conservative.

The current C3 model uses a "original type / active type" model. This makes it hard do any checks, like accepting char c1 = c + 127 but rejecting char c1 = c + 256 on account of 256 overflowing char.

If this type checking system is altered, it should be possible to instead pass a "required max type" downwards. The difference is in practice only if literals that exceed the left-hand side are rejected.

For most other purposes they work, and seem fairly safe as they are a restricted variant of C semantics. There is already an implementation of this in C3 compiler.

Handling unsigned conversions

The current model in C3 allow free implicit conversions between signed and unsigned types of the same size. However, the result is the signed type rather than the unsigned.

However, naively promoting all types to signed doesn't work well:

ushort c = 2;
uint d = 0x80000000;
uint e = d / 2; // => c0000000 ????
// If it was e = (uint)((int)d / (int)2);

Consequently C3 tries to promote to the signedness of the underlying type:

uint e = d / 2; 
// e = d / (uint)2; 
// => 0x40000000

Given the lack of languages with this sort of promotion, there might very well be serious issues with it, but in such cases we could limit unsigned conversion to the cases where it's fairly safe. For now though, let's keep this behaviour until we have more solid examples of it creating serious issues.

Summarizing attempt 3:

We define a receiving type, which is the parameter type the expression is passed as a value to, or the variable type for in the case of an assignment. This receiving type may also be empty. Example: short a = foo + (b / c), in this case the type is short.
We define a widening safe expression as any expression except: add, sub, mult, div, rem, left/right shift, bit negate, negate, ternary, bit or/xor/and.
We define a widening allowed expression as a binary add, sub, mult, div where the sub expressions are widening safe expressions.
Doing a depth first traversal on sub expressions, the following occurs in order:
The type is checked.
If the type is an integer and has a smaller bit width than the minimum arithmetic integer width, then it is cast to the corresponding minimum integer with the same signedness.
If the expression is a binary add/sub/div/mod/mult/bit or/ bit xor/bit and then the following are applied in order.
If both sub expressions are integers but of different size, check the smaller sub expression. If the smaller sub expression is a widening safe expression insert a widening cast to the same size, with retained signedness. Otherwise, if the smaller sub expression is a widening allowed expression, insert a widening cast to the same size with retained signedness on the smaller expression's two sub expressions. Otherwise this is a type error.
If one sub expression is an unsigned integer, and the other is signed, and the signed is non-negative constant literal, then the literal sub expression is cast to type of the unsigned sub expression.
If one sub expression is unsigned and the other is signed, the unsigned is cast to the signed type.
If one sub expression is bool or integer, and the other is a floating point type, then the integer sub expression is cast to the
Using the receiving type, ignoring inserted implicit casts, recursively check sub expressions:
If the type is wider than the receiving type, and the sub expression is a literal which does not fit in the receiving type, this is a literal out of range error.
the receiving type, and the sub expression is a not a literal, and the sub expression's type is wider than the receiving type then this is an error.
If an explicit cast is encountered, set receiving type for sub expression checking to empty.

Wheew! That was a lot and fairly complex. We can sum it up a bit simpler:

Implicit narrowing only works if all sub expressions would fit in the target type.
Implicit widening will only be done on non-arithmetic expressions or simple +-/%* binary expressions. In the second case the widening is done on the sub expressions rather than the binary expression as a whole.
Integer literals can be implicitly cast to any type as long as it fits in the resulting type.

Conclusion

We tried three different semantics for implicit conversions using typed literals. A limited hybrid solution (our attempt 3) doesn't immediately break and consequently warrants some further investigation, but we're extremely far from saying that "this is good". Quite the opposite, we should treat as likely broken in multiple ways, where our task is to find out where.

We've already attempted various solutions, just to find corner cases with fairly awful semantics, even leaving aside implementation issues.

So it should be fairly clear that there are no perfect solutions, but only trade-offs to various degrees. (That said, some solutions are clearly worse than others)

It's also very clear that a healthy skepticism is needed towards one's designs and ideas. What looks excellent and clear today may tomorrow turn out to have fatal flaws. Backtracking and fixing flaws should be part of the design process and I believe it's important to keep an open mind, because as you research you might find that feature X which you thought was really good / really bad, is in fact the opposite.

When doing language design it's probably good to be mentally prepared to be wrong a lot.

(Also see the follow up, where we patch some of the problems!)

Comments

Comment by Christoffer Lernö

As a reminder, in the last article I listed the following strategies:

Strategies for widening

Early fold, late cast (deep traversal).
Left hand side widening & error on peer widening.
No implicit widening.
Peer resolution widening (C style).
Re-evaluation.
Top casting but error on subexpressions.
Common integer promotion (C style).
Pre-traversal evaluation.

Strategies for narrowing

Always allow (C style).
Narrowing on direct literal assignment only.
Original type is smaller or same as narrowed type. Literals always ok.
As (3) but literals are size checked.
No implicit narrowing.

Strategies for conversion of signed/unsigned

Prefer unsigned (C style).
Prefer signed.
Disallow completely.

To begin with, we'll try the "Early fold, late cast" for widening. This is essentially a modification on the peer resolution widening.

Attempt 1 - "Early fold, late cast"

Here we first fold all constants, then "peer promote" the types recursively downwards. How this differs from C is illustrated below:

int32_t y = foo();
int64_t x = bar();
double w = x + (y * 2);
// C semantics:
// double w = (double)(x + (int64_t)(y * 2));
// Early fold, late cast:
// double w = (double)(x + ((int64_t)y * (int64_t)2));

So far this looks pretty nice, but unfortunately the "early fold" part has less positive consequences:

int32_t y = foo();
int64_t x = bar();
int32_t max = INT32_MAX;
double w = x + (y + (INT32_MAX + 1));
double w2 = x + (y + (max + 1));
// Early fold, late cast:
// double w = (double)(x + ((int64_t)y + (int64_t)-2147483648));
// double w2 = (double)(x + ((int64_t)y 
//             + ((int64_t)max + (int64_t)1)));

The good thing about this wart is that it is at least locally observable - as long as it's clear from the source code what will be constant folded.

All in all, while slightly improving the semantics, we can't claim to have solved all the problems with peer resolution while the semantics got more complicated.

Attempt 2 "Re-evaluation"

This strategy is more theoretical than anything. With this strategy we attempt to first evaluate the maximum type, then re-evaluate everything by casting to this maximum type. It's possible to do this in multiple ways: deep copying the expression, two types of evaluation passes etc.

Our problematic example from attempt 1 works:

int32_t y = foo();
int64_t x = bar();
int32_t max = INT32_MAX;
double w = x + (y + (INT32_MAX + 1));
// => first pass type analysis: int64_t + (int32_t + (int + int))
// => max type in sub expression is int64_t
// => double w = (double)(x + ((int64_t)y 
//               + ((int64_t)INT_MAX + (int64_t)1)));

However, we somewhat surprisingly get code that are hard to reason about locally even in this case:

// elsewhere int64_t x = ... or int32_t x = ... 
int32_t y = foo();
double w = x + (y << 16);
// If x is int64_t:
// double w = (double)(x + ((int64_t)y << 16));
// If x is int32_t
// double w = (double)(x + (y << 16));

Here it's clear that we get different behaviour: in the case of int32_t the bits are shifted out, whereas for int64_t they are retained. There are better (but more complicated) examples to illustrate this, but it is proving that even with "ideal" semantics, we lose locality.

Rethinking "perfect"

Let's go back to the example we had with Java in the last article:

char d = 1;
char c = 1 + d; // Error
char c = (char)(1 + d); // Ok

In this case the first is ok, but the second isn't. The special case takes care of the most common use, but for anything non-trivial an explicit cast is needed.

What if we would say that this is okay:

int64_t x = foo();
int32_t y = bar();
double w = x + y

But this isn't:

int64_t x = foo();
int32_t y = bar();
double w = x + (y + y);
//             ^^^^^^^
// Error, can't implicitly promote complex expression
// of type int32_t to int64_t.

Basically we give up widening except for where we don't need to recurse deep into the sub-expressions. Let's try it out:

Attempt 3: Hybrid peer resolution and no implicit cast

We look at our first example.

int32_t y = foo();
int64_t x = bar();
double w = x + (y * 2); // Error

This is an error, but we can do two different things in order to make it work, depending on what behaviour we want:

// A
double w = x + (y * 2LL); // Promote y
// B
double w = x + (int64_t)(y * 2); // Promote y * 2

Yes, this some extra work, but also note that suddenly we have much better control over what the actual types are compared to the "perfect" promotion. Also note that changing the type of x cannot silently change semantics here.

The second example:

int32_t y = foo();
int64_t x = bar();
int32_t max = INT32_MAX;
double w = x + (y + (INT32_MAX + 1)); // Error

Again we get an error, and again there are multiple ways to remove this ambiguity. To promote the internal expression to use int64_t, we just have to nudge it a little bit:

double w = x + (y + (INT32_MAX + 1LL)); // Ok!

And of course if we want C behaviour, we simply put the cast outside:

double w = x + (int64_t)(y + (INT32_MAX + 1)); // Ok!

Note here how effective the type of the literal is in nudging the semantics in the correct direction!

Adding narrowing to "attempt 3"

For narrowing we have multiple options, the simplest is following the Java model, although it could be considered to be unnecessarily conservative.

The current C3 model uses a "original type / active type" model. This makes it hard do any checks, like accepting char c1 = c + 127 but rejecting char c1 = c + 256 on account of 256 overflowing char.

If this type checking system is altered, it should be possible to instead pass a "required max type" downwards. The difference is in practice only if literals that exceed the left-hand side are rejected.

For most other purposes they work, and seem fairly safe as they are a restricted variant of C semantics. There is already an implementation of this in C3 compiler.

Handling unsigned conversions

The current model in C3 allow free implicit conversions between signed and unsigned types of the same size. However, the result is the signed type rather than the unsigned.

However, naively promoting all types to signed doesn't work well:

ushort c = 2;
uint d = 0x80000000;
uint e = d / 2; // => c0000000 ????
// If it was e = (uint)((int)d / (int)2);

Consequently C3 tries to promote to the signedness of the underlying type:

uint e = d / 2; 
// e = d / (uint)2; 
// => 0x40000000

Given the lack of languages with this sort of promotion, there might very well be serious issues with it, but in such cases we could limit unsigned conversion to the cases where it's fairly safe. For now though, let's keep this behaviour until we have more solid examples of it creating serious issues.

Summarizing attempt 3:

We define a receiving type, which is the parameter type the expression is passed as a value to, or the variable type for in the case of an assignment. This receiving type may also be empty. Example: short a = foo + (b / c), in this case the type is short.
We define a widening safe expression as any expression except: add, sub, mult, div, rem, left/right shift, bit negate, negate, ternary, bit or/xor/and.
We define a widening allowed expression as a binary add, sub, mult, div where the sub expressions are widening safe expressions.
Doing a depth first traversal on sub expressions, the following occurs in order:
The type is checked.
If the type is an integer and has a smaller bit width than the minimum arithmetic integer width, then it is cast to the corresponding minimum integer with the same signedness.
If the expression is a binary add/sub/div/mod/mult/bit or/ bit xor/bit and then the following are applied in order.
If both sub expressions are integers but of different size, check the smaller sub expression. If the smaller sub expression is a widening safe expression insert a widening cast to the same size, with retained signedness. Otherwise, if the smaller sub expression is a widening allowed expression, insert a widening cast to the same size with retained signedness on the smaller expression's two sub expressions. Otherwise this is a type error.
If one sub expression is an unsigned integer, and the other is signed, and the signed is non-negative constant literal, then the literal sub expression is cast to type of the unsigned sub expression.
If one sub expression is unsigned and the other is signed, the unsigned is cast to the signed type.
If one sub expression is bool or integer, and the other is a floating point type, then the integer sub expression is cast to the
Using the receiving type, ignoring inserted implicit casts, recursively check sub expressions:
If the type is wider than the receiving type, and the sub expression is a literal which does not fit in the receiving type, this is a literal out of range error.
the receiving type, and the sub expression is a not a literal, and the sub expression's type is wider than the receiving type then this is an error.
If an explicit cast is encountered, set receiving type for sub expression checking to empty.

Wheew! That was a lot and fairly complex. We can sum it up a bit simpler:

Implicit narrowing only works if all sub expressions would fit in the target type.
Implicit widening will only be done on non-arithmetic expressions or simple +-/%* binary expressions. In the second case the widening is done on the sub expressions rather than the binary expression as a whole.
Integer literals can be implicitly cast to any type as long as it fits in the resulting type.

Conclusion

We tried three different semantics for implicit conversions using typed literals. A limited hybrid solution (our attempt 3) doesn't immediately break and consequently warrants some further investigation, but we're extremely far from saying that "this is good". Quite the opposite, we should treat as likely broken in multiple ways, where our task is to find out where.

We've already attempted various solutions, just to find corner cases with fairly awful semantics, even leaving aside implementation issues.

So it should be fairly clear that there are no perfect solutions, but only trade-offs to various degrees. (That said, some solutions are clearly worse than others)

It's also very clear that a healthy skepticism is needed towards one's designs and ideas. What looks excellent and clear today may tomorrow turn out to have fatal flaws. Backtracking and fixing flaws should be part of the design process and I believe it's important to keep an open mind, because as you research you might find that feature X which you thought was really good / really bad, is in fact the opposite.

When doing language design it's probably good to be mentally prepared to be wrong a lot.

(Also see the follow up, where we patch some of the problems!)

October 2, 2021
5 min read

How to break a + b + c

Originally from: https://c3.handmade.network/blog/p/8107-how_to_break_a__b__c

When one is deviating from language semantics, one sometimes accidentally break established, well-understood semantics. One of the worst design mistakes I did when working on C3 was to accidentally break associativity for addition.

Here is some code:

// File foo.h
typedef struct {
   unsigned short a;
   unsigned short b;
   unsigned short c; 
} Foo;

// File bar.c
unsigned int fooIt(Foo *foo)
{
   unsigned int x = a + b + c;
   return x;
}

// File baz.c
int calculate()
{
   Foo foo = { 200, 200, 200 };
   assert(fooIt(foo) == foo.b + foo.c + foo.a);
   return fooIt(foo);
}

I've written this with pure C syntax, but we're going to imagine deviating from C semantics.

In particular we're going to say:

if two operands in a binary expression (e.g. a + b) are of the same bit width n, the operation will be performed with wrapping semantics. So if we have two variables that are unsigned char and we add them, then the maximum value is 255. Similar with unsigned short will yield a maximum of 65535.
Implicit widening casts will be performed as long as they do not affect signedness.

In our example above fooIt(foo) will return 600 regardless whether we are using C or this new language with different semantics.

But let's say someone found this code to be memory inefficient. b and c should never be used with values over 255 (for one reason or the other). They alter the file foo.h in the following way, which passes compilation:

typedef struct {
   unsigned char a;
   unsigned char b;
   unsigned short c; 
} Foo;

You go to work and make changes and discover that suddenly your assert is trapping. You look at calculate and find no changes to that code. Similarly bar.c with fooIt. You find out that fooIt(foo) now returns 344, which makes no sense to you.

Finally the only candidate left is the change to Foo, but the data in Foo is the same and your assert is doing the same calculation as fooIt... or is it?

It turns out that with the non C semantics above, the computer will calculate unsigned int x = a + b + c in the following way:

a + b mod 2^8 => 144
144 + c mod 2^16 => 344

In your assert on the other hand, we swapped the order:

b + c mod 2^16 => 400
400 + a mod 2^16 => 600

The new semantic silently broke associativity and the compiler didn't warn us a single bit. This is a spooky action at a distance which you definitely don't want. Neither the writer of Foo, nor of fooIt, nor you could know that this would be a problem, it only breaks when the parts come together.

But "Wait!", you say, "There are many languages allowing this 'smaller than int size adds' addition by default, surely they can't all be broken?" – and you'd be right.

So what is the difference between our semantics and non-broken languages like Rust? If your guess is "implicit widening", then you're right.

And doesn't this seem strange? I mean it's not related to why the associativity breaks, but it's still the culprit. Because what happens if we don't have the widening?

Well fooIt would stop compiling for one:

unsigned int fooIt(Foo *foo)
{
   unsigned int x = a + b + c; 
   //               ^^^^^^^^^
   // Error: cannot add expression of type unsigned char
   // to expression of type unsigned short   
   return a;
}

And of course it would be known that changing Foo would be a possibly breaking change.

So what can be learned?

Designing new language semantics isn't trivial. Few consequences are easily recognizable at the beginning. One needs to be ready to drop semantics if they later turn out to have issues one didn't count on, even if they "work in most cases".

Comments

Comment by Christoffer Lernö

When one is deviating from language semantics, one sometimes accidentally break established, well-understood semantics. One of the worst design mistakes I did when working on C3 was to accidentally break associativity for addition.

Here is some code:

// File foo.h
typedef struct {
   unsigned short a;
   unsigned short b;
   unsigned short c; 
} Foo;

// File bar.c
unsigned int fooIt(Foo *foo)
{
   unsigned int x = a + b + c;
   return x;
}

// File baz.c
int calculate()
{
   Foo foo = { 200, 200, 200 };
   assert(fooIt(foo) == foo.b + foo.c + foo.a);
   return fooIt(foo);
}

I've written this with pure C syntax, but we're going to imagine deviating from C semantics.

In particular we're going to say:

if two operands in a binary expression (e.g. a + b) are of the same bit width n, the operation will be performed with wrapping semantics. So if we have two variables that are unsigned char and we add them, then the maximum value is 255. Similar with unsigned short will yield a maximum of 65535.
Implicit widening casts will be performed as long as they do not affect signedness.

In our example above fooIt(foo) will return 600 regardless whether we are using C or this new language with different semantics.

But let's say someone found this code to be memory inefficient. b and c should never be used with values over 255 (for one reason or the other). They alter the file foo.h in the following way, which passes compilation:

typedef struct {
   unsigned char a;
   unsigned char b;
   unsigned short c; 
} Foo;

You go to work and make changes and discover that suddenly your assert is trapping. You look at calculate and find no changes to that code. Similarly bar.c with fooIt. You find out that fooIt(foo) now returns 344, which makes no sense to you.

Finally the only candidate left is the change to Foo, but the data in Foo is the same and your assert is doing the same calculation as fooIt... or is it?

It turns out that with the non C semantics above, the computer will calculate unsigned int x = a + b + c in the following way:

a + b mod 2^8 => 144
144 + c mod 2^16 => 344

In your assert on the other hand, we swapped the order:

b + c mod 2^16 => 400
400 + a mod 2^16 => 600

The new semantic silently broke associativity and the compiler didn't warn us a single bit. This is a spooky action at a distance which you definitely don't want. Neither the writer of Foo, nor of fooIt, nor you could know that this would be a problem, it only breaks when the parts come together.

But "Wait!", you say, "There are many languages allowing this 'smaller than int size adds' addition by default, surely they can't all be broken?" – and you'd be right.

So what is the difference between our semantics and non-broken languages like Rust? If your guess is "implicit widening", then you're right.

And doesn't this seem strange? I mean it's not related to why the associativity breaks, but it's still the culprit. Because what happens if we don't have the widening?

Well fooIt would stop compiling for one:

unsigned int fooIt(Foo *foo)
{
   unsigned int x = a + b + c; 
   //               ^^^^^^^^^
   // Error: cannot add expression of type unsigned char
   // to expression of type unsigned short   
   return a;
}

And of course it would be known that changing Foo would be a possibly breaking change.

So what can be learned?

Designing new language semantics isn't trivial. Few consequences are easily recognizable at the beginning. One needs to be ready to drop semantics if they later turn out to have issues one didn't count on, even if they "work in most cases".

October 2, 2021
11 min read

Promotion strategies with typed literals

Originally from: https://c3.handmade.network/blog/p/8108-promotion_strategies_with_typed_literals

This is continuing the previous article on literals.

C3 is pervasively written to assume untyped literals, so what would the effect be if it changed to typed literals again?

Let's remind us of the rules for C3 with untyped literals:

All operands are widened to the minimum arithmetic type (typically a 32 bit int) if needed.
If the left-hand side is instead an integer of a larger width, all operands are instead widened to this type.
The end result may be implicitly narrowed only if all the operands were as small as the type to narrow to.

To exemplify:

short b = ...
char c = ...

// 1. Widening
$typeof(b + c) => int
// $typeof((int)(b) + (int)(c))

// 2. Left hand side widening
long z = b + c;
// => long z = (long)(b) + (long)(c);

// 3. Implicit narrowing.
short w = b + c;
// => short w = (short)((int)(b) + (int)(c))

Simple assignments

Let's start with simple assignments, where the lack of implicit narrowing tends to be a problem.

func void foo(short s) { ... }
func void ufoo(ushort us) { ... }
...

short s = 1234; // Allowed??
foo(1234); // Allowed??
ushort us = 65535; // Allowed??
ufoo(65535); // Allowed??

This is certainly something we would like to allow, so some additional rule is needed on top of just the literal types.

Binary expressions

We next turn to binary expressions:

short s = foo();
s = s + 1234; // Allowed??

This example is subtly different, because looking at the types there is no direct conversion. Keep in mind rule (3) which permits narrowing. It requires us to keep track of both the original and current type. The types are something like this short = (int was short) + (int was int). If we try to unify the binary expression, should the resulting type be "int was short" or "int was int"?

If we had s = s + 65535 we would strictly want "int was int" – which causes a type error, and then preferably "int was short" in the case with 1234. Is this possible?

In short: yes, although it does add special check for merging constants on every binary node. That said it has some very far-reaching consequences.

Peer resolution woes

In Zig, which only has implicit widening, this occurs in binary expressions. So if you had int + short the right-hand side would be promoted to int. For a single binary expression this makes sense, but what if you have this:

char c = bar();
char d = bar2();
short s = foo();
int a = c + d + s;

If we use the "peer resolution" approach, this would be resolved in this manner: int a = (int)((short)(c + d) + s). But if we reorder the terms, like int a = s + c + d, we get int a = (int)((s + (short)c) + (short)d) (assume additions are done using the resulting bit width of the sub expressions).

This means that in the original ordering we have mod-2^8 addition (or even undefined!) behaviour if the sum of c and d can't fit in a char, but with the first ordering there is no problem. Or in other words: we just lost associativity for addition!

That said, C has the same problem, but only when adding int with expressions which has types larger than int.

This example exhibits the same issue in C:

int32_t i = bar();
int32_t j = bar2();
int64_t k = foo();
int64_t a = i + j + k; 
// Evaluated as 
// int64_t a = (int64_t)(i + j) + k;

Previous to the 64-bit generation, the int was generally register sized in C, so doing larger-than-register-sized additions were rare and consequently less of a problem.

This prompted me to investigate a different approach for C3, using left side widening. On 64-bits, this would still be default 32-bit widening, but if the assigned typ was 64-bit, all operands would be widened to 64-bits instead, so as if it was written int64_t a = (int64_t)i + (int64_t)j + k. This is achieved by "pushing down" the left-hand type during semantic analysis (see rule 2).

The reason it must be pushed down during the pass, rather than doing it after evaluation, is that the type affects untyped literal evaluation and constant folding. Here is an example:

int32_t b = 1;
int64_t a = b + (b + ~0);

If we don't push down the type, then we need to use the closest thing, which either b - which has type int32_t - or just the default arithmetic promotion type, which is "int" in C.

// Use `int` to constant fold ~0 and 
// cast all to int64_t afterwards.
int64_t a = (int64_t)b + ((int64_t)b + (int64_t)(~(int)0));

// Use `int64_t` on 0 before constant folding:
int64_t a = (int64_t)b + ((int64_t)b + (~(int64_t)0));

We still have problems though, like in this case:

double d = 1.0 + (~0 + a);

If we the analysis in this order:

Analyse 1.0
Analyse 0
Analyse ~0
Analyse a
Analyse a + ~0
Analyse 1.0 + (a + ~0)
Analyse d = 1.0 + (a + ~0)

Then here we see that even though we know a to be int64_t we can't use that fact to type 0, because it is analysed after 0. And worse: the a might actually be an arbitrarily complex expression – something that you can't tell until you analysed it!

For that reason, even with untyped values, 0 is forced to default to int, with this result: double d = 1.0 + (double)((int64_t)~(int)0 + a)

Another example is shown below.

int64_t x = 0x7FFF_FFFF * 4;
int64_t y = x - 0x7FFF_FFFF * 2;
// y = 4294967294
double d = x - 0x7FFF_FFFF * 2; 
// d = 8589934590.0

Here due to no widening hint from a "double", the two expressions behave in a completely different manner.

Setting realistic goals

Ideally we would like semantics that eliminate unnecessary casts, and requires casts where cast semantics are intended. Since the compiler can't read our mind, we will need to at least sacrifice a little of one of those goals. In C, elimination of unnecessary casts are prioritized, although these days with the common set of warnings it is somewhat less true.

In addition to this, we would also like to make sure arithmetics happens with the bit width the user intended, and that code should be can be interpreted locally without having to know the details of variables defined far away – this is particularly important if the compiler does not detect mismatches.

Even more important is a simple programmer mental model for semantics: easy to understand semantics that are less convenient trumps convenient but complex semantics.

Strategies

In order to get started, let's list a bunch of possible strategies for widening and narrowing semantics.

Strategies for widening

Early fold, late cast (deep traversal).
Left hand side widening & error on peer widening.
No implicit widening.
Peer resolution widening (C style).
Re-evaluation.
Top casting but error on subexpressions.
Common integer promotion (C style).
Pre-traversal evaluation.

Strategies for narrowing

Always allow (C style).
Narrowing on direct literal assignment only.
Original type is smaller or same as narrowed type. Literals always ok.
As (3) but literals are size checked.
No implicit narrowing.

Strategies for conversion of signed/unsigned

Prefer unsigned (C style).
Prefer signed.
Disallow completely.

We should also note that there is no need to limit ourselves to a single strategy. For example, in Java char c = 1 + 1; is valid, but this isn't:

char d = 1;
char c = 1 + d;

Here the simple literal assignment is considered a special case where implicit conversion is allowed. In other words, we're seeing a combination of strategies.

Case study 1: "C rules"

C in general works well, except for the unsafe narrowings – until we reach "larger than int" sizes. In this case we get peer resolution widening, which produces bad results for sub expressions:

int a = 0x7FFFFFFF;
int64_t x = a + 1;
// => x = -2147483648

In general working with a combination of int and larger-than-int types work poorly with C.

Case study 2: "C + left side widening"

This is using the current C3 idea of using the left side type to increase the type implicitly widened to. Our C example works:

int a = 0x7FFFFFFF;
int64_t x = a + 1;
// => x = 2147483648 with left side widening

As previously mentioned, this breaks down when there is no left side type, which then defaults to C peer resolution widening.

int a = 0x7FFFFFFF;
int64_t b = 0;
double d = (double)((a + 1) + b);
// => x = -2147483648.0

In the next article I will walk through various new ideas for promotion semantics with analysis.

Comments

Comment by Christoffer Lernö

This is continuing the previous article on literals.

C3 is pervasively written to assume untyped literals, so what would the effect be if it changed to typed literals again?

Let's remind us of the rules for C3 with untyped literals:

All operands are widened to the minimum arithmetic type (typically a 32 bit int) if needed.
If the left-hand side is instead an integer of a larger width, all operands are instead widened to this type.
The end result may be implicitly narrowed only if all the operands were as small as the type to narrow to.

To exemplify:

short b = ...
char c = ...

// 1. Widening
$typeof(b + c) => int
// $typeof((int)(b) + (int)(c))

// 2. Left hand side widening
long z = b + c;
// => long z = (long)(b) + (long)(c);

// 3. Implicit narrowing.
short w = b + c;
// => short w = (short)((int)(b) + (int)(c))

Simple assignments

Let's start with simple assignments, where the lack of implicit narrowing tends to be a problem.

func void foo(short s) { ... }
func void ufoo(ushort us) { ... }
...

short s = 1234; // Allowed??
foo(1234); // Allowed??
ushort us = 65535; // Allowed??
ufoo(65535); // Allowed??

This is certainly something we would like to allow, so some additional rule is needed on top of just the literal types.

Binary expressions

We next turn to binary expressions:

short s = foo();
s = s + 1234; // Allowed??

This example is subtly different, because looking at the types there is no direct conversion. Keep in mind rule (3) which permits narrowing. It requires us to keep track of both the original and current type. The types are something like this short = (int was short) + (int was int). If we try to unify the binary expression, should the resulting type be "int was short" or "int was int"?

If we had s = s + 65535 we would strictly want "int was int" – which causes a type error, and then preferably "int was short" in the case with 1234. Is this possible?

In short: yes, although it does add special check for merging constants on every binary node. That said it has some very far-reaching consequences.

Peer resolution woes

In Zig, which only has implicit widening, this occurs in binary expressions. So if you had int + short the right-hand side would be promoted to int. For a single binary expression this makes sense, but what if you have this:

char c = bar();
char d = bar2();
short s = foo();
int a = c + d + s;

If we use the "peer resolution" approach, this would be resolved in this manner: int a = (int)((short)(c + d) + s). But if we reorder the terms, like int a = s + c + d, we get int a = (int)((s + (short)c) + (short)d) (assume additions are done using the resulting bit width of the sub expressions).

This means that in the original ordering we have mod-2^8 addition (or even undefined!) behaviour if the sum of c and d can't fit in a char, but with the first ordering there is no problem. Or in other words: we just lost associativity for addition!

That said, C has the same problem, but only when adding int with expressions which has types larger than int.

This example exhibits the same issue in C:

int32_t i = bar();
int32_t j = bar2();
int64_t k = foo();
int64_t a = i + j + k; 
// Evaluated as 
// int64_t a = (int64_t)(i + j) + k;

Previous to the 64-bit generation, the int was generally register sized in C, so doing larger-than-register-sized additions were rare and consequently less of a problem.

This prompted me to investigate a different approach for C3, using left side widening. On 64-bits, this would still be default 32-bit widening, but if the assigned typ was 64-bit, all operands would be widened to 64-bits instead, so as if it was written int64_t a = (int64_t)i + (int64_t)j + k. This is achieved by "pushing down" the left-hand type during semantic analysis (see rule 2).

The reason it must be pushed down during the pass, rather than doing it after evaluation, is that the type affects untyped literal evaluation and constant folding. Here is an example:

int32_t b = 1;
int64_t a = b + (b + ~0);

If we don't push down the type, then we need to use the closest thing, which either b - which has type int32_t - or just the default arithmetic promotion type, which is "int" in C.

// Use `int` to constant fold ~0 and 
// cast all to int64_t afterwards.
int64_t a = (int64_t)b + ((int64_t)b + (int64_t)(~(int)0));

// Use `int64_t` on 0 before constant folding:
int64_t a = (int64_t)b + ((int64_t)b + (~(int64_t)0));

We still have problems though, like in this case:

double d = 1.0 + (~0 + a);

If we the analysis in this order:

Analyse 1.0
Analyse 0
Analyse ~0
Analyse a
Analyse a + ~0
Analyse 1.0 + (a + ~0)
Analyse d = 1.0 + (a + ~0)

Then here we see that even though we know a to be int64_t we can't use that fact to type 0, because it is analysed after 0. And worse: the a might actually be an arbitrarily complex expression – something that you can't tell until you analysed it!

For that reason, even with untyped values, 0 is forced to default to int, with this result: double d = 1.0 + (double)((int64_t)~(int)0 + a)

Another example is shown below.

int64_t x = 0x7FFF_FFFF * 4;
int64_t y = x - 0x7FFF_FFFF * 2;
// y = 4294967294
double d = x - 0x7FFF_FFFF * 2; 
// d = 8589934590.0

Here due to no widening hint from a "double", the two expressions behave in a completely different manner.

Setting realistic goals

Ideally we would like semantics that eliminate unnecessary casts, and requires casts where cast semantics are intended. Since the compiler can't read our mind, we will need to at least sacrifice a little of one of those goals. In C, elimination of unnecessary casts are prioritized, although these days with the common set of warnings it is somewhat less true.

In addition to this, we would also like to make sure arithmetics happens with the bit width the user intended, and that code should be can be interpreted locally without having to know the details of variables defined far away – this is particularly important if the compiler does not detect mismatches.

Even more important is a simple programmer mental model for semantics: easy to understand semantics that are less convenient trumps convenient but complex semantics.

Strategies

In order to get started, let's list a bunch of possible strategies for widening and narrowing semantics.

Strategies for widening

Early fold, late cast (deep traversal).
Left hand side widening & error on peer widening.
No implicit widening.
Peer resolution widening (C style).
Re-evaluation.
Top casting but error on subexpressions.
Common integer promotion (C style).
Pre-traversal evaluation.

Strategies for narrowing

Always allow (C style).
Narrowing on direct literal assignment only.
Original type is smaller or same as narrowed type. Literals always ok.
As (3) but literals are size checked.
No implicit narrowing.

Strategies for conversion of signed/unsigned

Prefer unsigned (C style).
Prefer signed.
Disallow completely.

We should also note that there is no need to limit ourselves to a single strategy. For example, in Java char c = 1 + 1; is valid, but this isn't:

char d = 1;
char c = 1 + d;

Here the simple literal assignment is considered a special case where implicit conversion is allowed. In other words, we're seeing a combination of strategies.

Case study 1: "C rules"

C in general works well, except for the unsafe narrowings – until we reach "larger than int" sizes. In this case we get peer resolution widening, which produces bad results for sub expressions:

int a = 0x7FFFFFFF;
int64_t x = a + 1;
// => x = -2147483648

In general working with a combination of int and larger-than-int types work poorly with C.

Case study 2: "C + left side widening"

This is using the current C3 idea of using the left side type to increase the type implicitly widened to. Our C example works:

int a = 0x7FFFFFFF;
int64_t x = a + 1;
// => x = 2147483648 with left side widening

As previously mentioned, this breaks down when there is no left side type, which then defaults to C peer resolution widening.

int a = 0x7FFFFFFF;
int64_t b = 0;
double d = (double)((a + 1) + b);
// => x = -2147483648.0

In the next article I will walk through various new ideas for promotion semantics with analysis.

September 29, 2021
10 min read

The problem with untyped literals

Originally from: https://c3.handmade.network/blog/p/8100-the_problem_with_untyped_literals

A brief introduction

From Go to Swift, the idea of untyped literals – in particular numbers – have been popularized. This means that a number like 123 or 283718237218731239821738 doesn't have a type until it needs to fit into a variable or an expression, and at that time it's converted into the type needed.

Usually (but not always), this also allows the expression to hold numbers that exceed the type limit as long as it can be folded into the valid range. So 100000000000000 * 123 / 100000000000000 would be a valid 32-bit integer, even though some sub expressions would not fit, since the constant folded result is 123.

This is not merely to avoid adding type suffixes (as an example, in C or C++ we would need to explicitly add L or LL to represent 5000000000 since it would not fit in the default type, which (today) usually is a 32 bit int) – but it's also to avoid casts.

Go, Swift and Rust all have versions of untyped literals, and they're (not coincidentally) also always requiring casts between differently sized integer types. What this means is that in normal cases, something like short_var1 = short_var2 + 30 would otherwise require a cast to change 30 in our case to a short type rather than the default int. If C required casts for literals everywhere, this is what it would look like(!):

short foo = (short)1;
char c = (char)0;
short bar = foo + (short)3;
int baz = (int)bar + (int)c;

So to summarize: untyped literals help to reduce the need for casts, while also freeing the user from thinking too much about the exact type of the literals.

All is not simplicity

While this works well for the most part, there is an issue when no type can be inferred from the surroundings. A simple example is this:

bool bar = (foo() ? 1 : 2) == (bar() ? 2 : 1);

This looks a bit contrived, but there are actual cases where something like this arises. In the example there is no type to guide what runtime type 1 and 2 should have, and yet it needs to be an actual runtime type as this expression must be resolved at runtime.

So what do we do? There are three possibilities:

Make it an error.
Use a default type.
Derive a type from the values.

Each of those have advantages and disadvantages that pop up in different situations. It's worth pointing out that both Go and Swift picks variants of (2).

Hard mode: Add implicit type conversion

An important reason why Go has untyped literals is because it's lacking implicit type conversions. But having untyped literals looks like a good improvement on status quo, which is likely why it was picked up by Zig. I likewise found this an interesting solution for C3 and implemented it.

Unfortunately it turns out there are additional problems when having implicit type conversions. Here is an example:

short a = bar();
char c = foo();
// Where does widening occur here?
int d = a + 2 * (c + 3);

In the above example there are a lot of options. Let's start with how this was initially (naively) implemented in C3:

int d = (int)(a + (short)((char)2 * (c + (char)3)));

Regardless whether we have wrapping arithmetics or traps, this - which Zig terms "peer resolution" - is probably not what we want.

Let's remind us that in C we get:

int d = (int)a + ((int)2) * ((int)c + (int)3));

This illustrates the limitations in trying to infer type by looking at the other operand in a binary expression, the actual behaviour is likely not what you want.

Because Go or Rust would require explicit casts for such an expression, the obfuscation that occurs with implicit widening just don't apply. Trying to add a to the term to the right would be an error, and assigning the result of that to d would be an error as well.

This worrying behaviour with implicit conversions made me switch C3 to a very C-ish solution: the compiler would promote all operands to either int or the type of the left side assigned variable / parameter if that was wider.

int d = a + 2 * (c + 3); // As if =>
// int d = (int)a + ((int)2) * ((int)c + (int)3));
long f = a + 2 * (c + 3); // As if =>
// long f = (long)a + ((long)2) * ((long)c + (long)3));

This simplified the semantics for the user and it's not overly hard to understand which seemed to make it a somewhat acceptable tradeoff.

Macro problems

Unfortunately there are more places where untyped literals creates worries: Let's say you're writing a macro. The macro should take a value and store it into a temporary variable:

macro foo(x)
{
  $typeof(x) y = x;
  while (y-- > 0) do_something();
}

When we use this with a variable, everything's fine, but it breaks when we (quite reasonably) try to use it with a literal.

int z = 3;
@foo(z); // Works! 
@foo(3); // Error: tries to use an untyped literal

This is probably not what we wanted. Using numbers as arguments to macros is a common usecase and must work.

Our three "solutions" to this yield different semantics:

With (1) - making it an error, we basically need to have a cast every time. Writing @foo((int)(3)) is not particularly impressive and makes the language feel rather uncooked.

With (2) - using a default type, everything works as long as the untyped literal is small enough to fit the default type. But if it exceeds it then explicit casts are needed. Depending on the macro this may be common or rare. This is better than (1), but still not perfect.

(3) - picking a type depending on size seems to allow the greatest flexibility, here we could pick an int as default and long if it doesn't fit the int. This is actually also its weakness: should something that fit in an ulong use a signed 128 bit int, or should the value switch to unsigned? If the latter, should the progression be int → uint → long → ulong? If so then behaviour may change as the value goes from unsigned to signed and this quite hidden from the reader. And what if unsigned is what we expect but suddenly we get a signed by mistake? And if it just picks signed values, then for every time we need unsigned we need to make a cast?

For languages without implicit conversion, picking (2) will often go a long way: the default type will, if unexpected, cause compile time errors, which makes it fairly easy to spot.

Is untyped literals a good idea?

Running into these kinds of problems at least make me stop and reconsider my decisions: are untyped literals really a good idea?

I think that judging from the above, the drawbacks are significantly bigger for languages with implicit casts like Zig or C3. Once macros/generic functions are added to the mix this further complicates matters.

If we look at Go, then without generics it has neither of these problems. Therefore it seems to be a fairly clear win, especially since Go can leverage the typeless literals to remove casts.

In C3 on the other hand, the only gain is really to allow bigint compile time folding and avoiding literal suffixes. Other than that it is mostly complicating the language.

That seems to indicate that C3 might benefit from more traditional, typed, literals.

So in the next blog article I plan to look at what issues would arise from actually adding typed literals (there might be surprises!), and if they'd really solve any meaningful problems for C3.

Comments

Comment by Christoffer Lernö

A brief introduction

From Go to Swift, the idea of untyped literals – in particular numbers – have been popularized. This means that a number like 123 or 283718237218731239821738 doesn't have a type until it needs to fit into a variable or an expression, and at that time it's converted into the type needed.

Usually (but not always), this also allows the expression to hold numbers that exceed the type limit as long as it can be folded into the valid range. So 100000000000000 * 123 / 100000000000000 would be a valid 32-bit integer, even though some sub expressions would not fit, since the constant folded result is 123.

This is not merely to avoid adding type suffixes (as an example, in C or C++ we would need to explicitly add L or LL to represent 5000000000 since it would not fit in the default type, which (today) usually is a 32 bit int) – but it's also to avoid casts.

Go, Swift and Rust all have versions of untyped literals, and they're (not coincidentally) also always requiring casts between differently sized integer types. What this means is that in normal cases, something like short_var1 = short_var2 + 30 would otherwise require a cast to change 30 in our case to a short type rather than the default int. If C required casts for literals everywhere, this is what it would look like(!):

short foo = (short)1;
char c = (char)0;
short bar = foo + (short)3;
int baz = (int)bar + (int)c;

So to summarize: untyped literals help to reduce the need for casts, while also freeing the user from thinking too much about the exact type of the literals.

All is not simplicity

While this works well for the most part, there is an issue when no type can be inferred from the surroundings. A simple example is this:

bool bar = (foo() ? 1 : 2) == (bar() ? 2 : 1);

This looks a bit contrived, but there are actual cases where something like this arises. In the example there is no type to guide what runtime type 1 and 2 should have, and yet it needs to be an actual runtime type as this expression must be resolved at runtime.

So what do we do? There are three possibilities:

Make it an error.
Use a default type.
Derive a type from the values.

Each of those have advantages and disadvantages that pop up in different situations. It's worth pointing out that both Go and Swift picks variants of (2).

Hard mode: Add implicit type conversion

An important reason why Go has untyped literals is because it's lacking implicit type conversions. But having untyped literals looks like a good improvement on status quo, which is likely why it was picked up by Zig. I likewise found this an interesting solution for C3 and implemented it.

Unfortunately it turns out there are additional problems when having implicit type conversions. Here is an example:

short a = bar();
char c = foo();
// Where does widening occur here?
int d = a + 2 * (c + 3);

In the above example there are a lot of options. Let's start with how this was initially (naively) implemented in C3:

int d = (int)(a + (short)((char)2 * (c + (char)3)));

Regardless whether we have wrapping arithmetics or traps, this - which Zig terms "peer resolution" - is probably not what we want.

Let's remind us that in C we get:

int d = (int)a + ((int)2) * ((int)c + (int)3));

This illustrates the limitations in trying to infer type by looking at the other operand in a binary expression, the actual behaviour is likely not what you want.

Because Go or Rust would require explicit casts for such an expression, the obfuscation that occurs with implicit widening just don't apply. Trying to add a to the term to the right would be an error, and assigning the result of that to d would be an error as well.

This worrying behaviour with implicit conversions made me switch C3 to a very C-ish solution: the compiler would promote all operands to either int or the type of the left side assigned variable / parameter if that was wider.

int d = a + 2 * (c + 3); // As if =>
// int d = (int)a + ((int)2) * ((int)c + (int)3));
long f = a + 2 * (c + 3); // As if =>
// long f = (long)a + ((long)2) * ((long)c + (long)3));

This simplified the semantics for the user and it's not overly hard to understand which seemed to make it a somewhat acceptable tradeoff.

Macro problems

Unfortunately there are more places where untyped literals creates worries: Let's say you're writing a macro. The macro should take a value and store it into a temporary variable:

macro foo(x)
{
  $typeof(x) y = x;
  while (y-- > 0) do_something();
}

When we use this with a variable, everything's fine, but it breaks when we (quite reasonably) try to use it with a literal.

int z = 3;
@foo(z); // Works! 
@foo(3); // Error: tries to use an untyped literal

This is probably not what we wanted. Using numbers as arguments to macros is a common usecase and must work.

Our three "solutions" to this yield different semantics:

With (1) - making it an error, we basically need to have a cast every time. Writing @foo((int)(3)) is not particularly impressive and makes the language feel rather uncooked.

With (2) - using a default type, everything works as long as the untyped literal is small enough to fit the default type. But if it exceeds it then explicit casts are needed. Depending on the macro this may be common or rare. This is better than (1), but still not perfect.

(3) - picking a type depending on size seems to allow the greatest flexibility, here we could pick an int as default and long if it doesn't fit the int. This is actually also its weakness: should something that fit in an ulong use a signed 128 bit int, or should the value switch to unsigned? If the latter, should the progression be int → uint → long → ulong? If so then behaviour may change as the value goes from unsigned to signed and this quite hidden from the reader. And what if unsigned is what we expect but suddenly we get a signed by mistake? And if it just picks signed values, then for every time we need unsigned we need to make a cast?

For languages without implicit conversion, picking (2) will often go a long way: the default type will, if unexpected, cause compile time errors, which makes it fairly easy to spot.

Is untyped literals a good idea?

Running into these kinds of problems at least make me stop and reconsider my decisions: are untyped literals really a good idea?

I think that judging from the above, the drawbacks are significantly bigger for languages with implicit casts like Zig or C3. Once macros/generic functions are added to the mix this further complicates matters.

If we look at Go, then without generics it has neither of these problems. Therefore it seems to be a fairly clear win, especially since Go can leverage the typeless literals to remove casts.

In C3 on the other hand, the only gain is really to allow bigint compile time folding and avoiding literal suffixes. Other than that it is mostly complicating the language.

That seems to indicate that C3 might benefit from more traditional, typed, literals.

So in the next blog article I plan to look at what issues would arise from actually adding typed literals (there might be surprises!), and if they'd really solve any meaningful problems for C3.

June 23, 2021
6 min read

C3: Block comments and mega comments.

Originally from: https://c3.handmade.network/blog/p/7908-c3__block_comments_and_mega_comments.

For C3 I wanted to address the problem of commenting out code using block comments.

In a good overview, Dennie Van Tassel outlined four different types of comments:

Full line comments, this is exemplified by REM in BASIC: The line only contains the comment and it runs to the end of the line.
End-of-Line comments, in C/C++ that would be //
Block comments, '/* ... */' in C/C++
Mega comments, which in C/C++ can be emulated by using // on every line or using the preprocessor with #if 0 ... #endif

We can ignore the full line comments, they're completely covered by end-of-line comments, and C3 already has those and /* ... */ block comments.

However, the mega comments poses a problem. In C3 the analogue to #if 0 ... #endif is $if 0 ... $endif, but it would require the code inside to parse.

Since a typical case for using mega comments would actually be to copy a slab of C code inside of comments and then convert it piecemeal $if 0 doesn't work.

What about making /* ... */ nesting?

In an article from 2017 titled Block Comments are a Bad Idea Troels Henriksen argues that adding nesting to block comments does not really solve the problem and shows the following example from Haskell which uses {- ... -} for nested comments:

{-
s = "{-";
-}

In the above example the {- inside of the string inadvertently opens a new nested comment. He rejects the idea that the lexer (or even worse, *the parser*) should track strings inside of comments. Instead Henriksen argues for either using #if 0 or // on every line. While the latter is exactly what Zig picked, it relies too much on the text editor for my taste.

Looking at D, it introduces a new nested comment /+ ... +/. It acts just like /* ... */ except it is nested. Initially this was what I picked for C3.

However it has drawbacks:

It introduces another comment type that is only marginally different from the others.
It can have the s = "/+" problem just like "/*" – we just moved the problem.
For beginners coming from C it's not obvious that this comment type is available, so it may get under used.
It does not visually indicate that it should be used for mega comments rather than regular comments.

There's another point as well: #if 0 ... #endif can never have the s = "/*" issue by virtue of always starting and ending on its own line.

Doing some research I tried to determine if there was some "obvious" syntax that could convey the #if 0 ... #endif behaviour. I had a lot of examples (that I hated), like /--- ... ---/ /--> ... /<--- and even ideas of a heredoc style comment like /$FOO ... /$$FOO.

Ultimately I decided to pick /# ... #/ for these block comments, which acted like nested comments but were required to be on a new line which bypasses this problem:

/#
s = "/#"; <- not recognized
#/

But it turns out that this has issues of its own. What if you by accident write something like:

/#
int x;
int y = foo(); #/

or

foo() /#
int x;
#/

You need a good heuristic to figure out a nice error message for these. For example you could either always decide that /#foo is /# + foo or maybe it's only like that if the /# starts a line, otherwise it's interpreted as / + #foo (which can be valid C3).

But after playing around with this for a while, I had to say that the value from this seemed much less than I had hoped. Yes, it's distinct, but it has most of the problems with /+ ... +/ in terms of lack of familiarity. And if I'm honest with myself, I'm personally still mostly using /* ... */ over #if 0 ... #endif where I can.

So we've come full circle: nesting /* */ to distinct nesting block comments, to #if 0 ... #endif and now back to perhaps nesting /* ... */?

For now at least, C3 will add nesting to /* ... */ and remove /+ ... +/. This is an imperfect solution, but possibly also a reasonable trade off to keep the language familiar with features that pull their weight.

Comments

Comment by Christoffer Lernö

For C3 I wanted to address the problem of commenting out code using block comments.

In a good overview, Dennie Van Tassel outlined four different types of comments:

Full line comments, this is exemplified by REM in BASIC: The line only contains the comment and it runs to the end of the line.
End-of-Line comments, in C/C++ that would be //
Block comments, '/* ... */' in C/C++
Mega comments, which in C/C++ can be emulated by using // on every line or using the preprocessor with #if 0 ... #endif

We can ignore the full line comments, they're completely covered by end-of-line comments, and C3 already has those and /* ... */ block comments.

However, the mega comments poses a problem. In C3 the analogue to #if 0 ... #endif is $if 0 ... $endif, but it would require the code inside to parse.

Since a typical case for using mega comments would actually be to copy a slab of C code inside of comments and then convert it piecemeal $if 0 doesn't work.

What about making /* ... */ nesting?

In an article from 2017 titled Block Comments are a Bad Idea Troels Henriksen argues that adding nesting to block comments does not really solve the problem and shows the following example from Haskell which uses {- ... -} for nested comments:

{-
s = "{-";
-}

In the above example the {- inside of the string inadvertently opens a new nested comment. He rejects the idea that the lexer (or even worse, *the parser*) should track strings inside of comments. Instead Henriksen argues for either using #if 0 or // on every line. While the latter is exactly what Zig picked, it relies too much on the text editor for my taste.

Looking at D, it introduces a new nested comment /+ ... +/. It acts just like /* ... */ except it is nested. Initially this was what I picked for C3.

However it has drawbacks:

It introduces another comment type that is only marginally different from the others.
It can have the s = "/+" problem just like "/*" – we just moved the problem.
For beginners coming from C it's not obvious that this comment type is available, so it may get under used.
It does not visually indicate that it should be used for mega comments rather than regular comments.

There's another point as well: #if 0 ... #endif can never have the s = "/*" issue by virtue of always starting and ending on its own line.

Doing some research I tried to determine if there was some "obvious" syntax that could convey the #if 0 ... #endif behaviour. I had a lot of examples (that I hated), like /--- ... ---/ /--> ... /<--- and even ideas of a heredoc style comment like /$FOO ... /$$FOO.

Ultimately I decided to pick /# ... #/ for these block comments, which acted like nested comments but were required to be on a new line which bypasses this problem:

/#
s = "/#"; <- not recognized
#/

But it turns out that this has issues of its own. What if you by accident write something like:

/#
int x;
int y = foo(); #/

or

foo() /#
int x;
#/

You need a good heuristic to figure out a nice error message for these. For example you could either always decide that /#foo is /# + foo or maybe it's only like that if the /# starts a line, otherwise it's interpreted as / + #foo (which can be valid C3).

But after playing around with this for a while, I had to say that the value from this seemed much less than I had hoped. Yes, it's distinct, but it has most of the problems with /+ ... +/ in terms of lack of familiarity. And if I'm honest with myself, I'm personally still mostly using /* ... */ over #if 0 ... #endif where I can.

So we've come full circle: nesting /* */ to distinct nesting block comments, to #if 0 ... #endif and now back to perhaps nesting /* ... */?

For now at least, C3 will add nesting to /* ... */ and remove /+ ... +/. This is an imperfect solution, but possibly also a reasonable trade off to keep the language familiar with features that pull their weight.

March 3, 2021
11 min read

C3: Handling casts and overflows part 2

Originally from: https://c3.handmade.network/blog/p/7661-c3__handling_casts_and_overflows_part_2

Continuing from our previous article, let's look are some more possibilities and maybe find a solution.

An even more ambitious widening strategy

The previous idea with both a maximum and minimum promotion type didn't pan out, but what if we went much further?

We use the idea of a maxint which is a signed-only integer type that is wider than the widest ordinary type. If i128 is supported natively on the target, then the maxint is i256, if the max normal int type is long (defined as 64 bits in C3), the maxint becomes an i128.

We also have a minimum arithmetic integer type, which is usually will be the exact same as the size of C's int. The algorithm is then as following:

Determine the type of the left hand side. This is the target type. If the target type is unsigned, promote it to the next power-of-two type. E.g. uint -> long.
Check the leaf operands (variables, integer literals, casts, functions). If they exceed the target type this is a compile time error.
Promote the operands to at least the minimum arithmetic integer type.
If the resulting type is more narrow than the target type, promote to the target type.
Trap all operations.
Trap the truncation of the right hand side down to the actual type of the left hand side.

Our u64 = u64 + i32 works now, it is implicitly converted to something like u64 = safeCastWithTrap(addWithTrap(cast(u64 as i128), cast(i32 as i128)), ulong).

So far so good, but something like u64 = u64 + u64 will also need i128. This adds a certain level of safety at a potential cost of performance, even though usually a compiler will optimize away the use of the extra 64 bits for simpler expressions.

This looks promising, but what about wrapping behaviour? We can use the wrapping operators to resolve this using both sides against each other, so that in the case of u64 = i32 +% i16this becomes u64 = safeCastWithTrap(addWrap(i32, cast(i16 as i32)). We prevent implicit unsigned and signed mixing without explicit cast if we cannot convert to either operand: i16 +% u32 would for example be an error.

We allow u32 = i32. This converts into u32 = safeCastWithTrap(i32, u32).

Back to basics, no overflow trapping

Another venue of exploration is to simplify and go back to C. There are some simple changes one can make: implicit widening to use the left hand side, make signed integer overflow wrapping, require casts for mixed unsigned and signed arithmetics to make it more obvious.

We can allow implicit conversion if back from the automatically promoted type, so in the case of i16 = i16 + i16, using C arithmetic promotion rules the operands would for example to i32 before calculation. We can allow implicit truncation back in those cases, but perhaps require explicit casts in all other cases. So i16 = i16 + i32 would require some kind of cast. What simplifies things is that we only need a truncating cast here.

We can introduce trapping arithmetics as well as a trapping assign that requires both arguments already having the same type:

short x = 1;
char b = 16;
int y = 0x7FFF;
// x = x + y; // ERROR, must have explicit cast.
x = x + b;

// The following are not necessary but may be interesting:
x = b ~+ b; // This will trap in due to 16 * 16 > MAX_CHAR
// x = x ~+ b; // ERROR both operands must be the same
x ~= y + 1; // Will trap as the value would overflow
x ~= y; // Would work

Some evaluation

Let us evaluate the different examples using some examples. Here are some code examples that contain vulnerabilities:

func void readpgm(char* name, Pixmap* p)
{
  /* ... */
  pnm_readpaminit(fp, &inpam);
  p.x = inpam.width;
  p.y = inpam.height;
  // Possible overflow
  if (!(p.p = malloc(p.x * p.y)))
  {
    @report("Error at malloc");
  }
  for (int i = 0; i < inpam.height; i++)
  {
    pnm_readpamrow(&inpam, tuplerow);
    for (int j = 0; j < inpam.width; j++)
    {
      // Possible overflow
      p.p[i * inpam.width + j] = sample;
    }
  }
}

func void getComm(uint len, char* src)
{
  uint size;
  // Underflow if len < 2
  size = len - 2;
  // Overflow if size = UINT_MAX
  char* comm = malloc(size + 1);
  memcpy(comm, src, size);
}

func uint* decode_fh(uint* p, SvcFh* fhp)
{
  int size;
  fh_init(fhp, NFS3_FHSIZE);
  size = ntohl(*p++);
  if (size > NFS3_FHSIZE) return NULL;
  // size may be < 0, this converts into a huge size
  memcpy(&fhp.fh_handle.fh_base, p, size);
  fhp.fh_handle.fh_size = size;
  return p + XDR_QUADLEN(size);
}

With those examples presented, let's see how they work out using the two strategies:

The widening strategy

func void readpgm(char* name, Pixmap* p)
{
  /* ... */
  pnm_readpaminit(fp, &inpam);
  p.x = inpam.width;
  p.y = inpam.height;
  // Will trap in debug:
  if (!(p.p = malloc(p.x * p.y)))
  {
    @report("Error at malloc");
  }
  for (int i = 0; i < inpam.height; i++)
  {
    pnm_readpamrow(&inpam, tuplerow);
    for (int j = 0; j < inpam.width; j++)
    {
      // Will trap in debug;
      p.p[i * inpam.width + j] = sample;
    }
  }
}

func void getComm(uint len, char* src)
{
  uint size;
  // Will trap in debug
  size = len - 2;
  char* comm = malloc(size + 1);
  memcpy(comm, src, size);
}

func uint* decode_fh(uint* p, SvcFh* fhp)
{
  int size;
  fh_init(fhp, NFS3_FHSIZE);
  size = ntohl(*p++);
  if (size > NFS3_FHSIZE) return null;
  // Will trap in debug
  memcpy(&fhp.fh_handle.fh_base, p, size);
  fhp.fh_handle.fh_size = size;
  return p + XDR_QUADLEN(size);
}

The widening strategy clearly works perfectly in these examples, all overflows are correctly trapped with zero need for additional annotations. It "just works".

2s complement wrapping

func void readpgm(char* name, Pixmap* p)
{
  /* ... */
  pnm_readpaminit(fp, &inpam);
  p.x = inpam.width;
  p.y = inpam.height;
  // Unchecked, except for negative values, 
  // use "p.p = malloc(convert(p.x ~* p.y as usize))"
  // to trap in both release and debug
  if (!(p.p = malloc(convert(p.x + p.y as usize))))
  {
    @report("Error at malloc");
  }
  for (int i = 0; i < inpam.height; i++)
  {
    pnm_readpamrow(&inpam, tuplerow);
    for (int j = 0; j < inpam.width; j++)
    {
      // Unchecked, use "i ~* inpam.width ~+ j"
      // to trap in both release and debug
      // but the problem lies in the earlier malloc check.
      p.p[i * inpam.width + j] = sample;
    }
  }
}

func void getComm(uint len, char* src)
{
  uint size;
  // Not checked, use
  // len ~- 2 to trap in both release and debug
  // but it is more natural to check this with
  // preconditions, e.g. assert(len >= 2)
  // So trapping is probably the wrong decision
  size = len - 2;
  char* comm = malloc(size + 1);
  memcpy(comm, src, size);
}

func uint* decode_fh(uint* p, SvcFh* fhp)
{
  int size;
  fh_init(fhp, NFS3_FHSIZE);
  size = ntohl(*p++);
  if (size > NFS3_FHSIZE) return null;
  // Here we are forced to convert
  // it's natural to use a trapping conversion
  // that protects in both release and debug
  memcpy(&fhp.fh_handle.fh_base, p, convert(size as usize));
  fhp.fh_handle.fh_size = size;
  return p + XDR_QUADLEN(size);
}

In these cases we see that the widening strategy has a very clear advantage in detecting errors. This is not surprising, since it's exactly what it's built for. On the other hand the explicit trapping operators give us stronger protection where it's used and the type model is so much simpler.

That last argument is the strongest in favour of "wrapping". Although we in this particular example manage to demonstrate that "widening" works, it introduces a lot of machinery to add the traps and there are enough implicit checks that we can't prove for sure that the behaviour isn't without problems. And yes u32 = u32 + i32 will make implicit checks for overflow, but maybe that should be checked before the assignment? The traps are very useful during testing, but they're no replacement for code that correctly checks arguments. In C3's case there is already support for contracts which catches many of the errors above as long as the function are properly documented, so unlike other languages it already has a somewhat higher level of security.

Summary

I've presented two quite different models, each with its own advantages and disadvantages. Ultimately what decides what to use is not just the security concerns, but how well it fits with the language in general. Other features may interact in a surprising manner, so it's only after working with a model in practice one can see the real effects on the language as a whole.

Comments

Comment by Christoffer Lernö

Continuing from our previous article, let's look are some more possibilities and maybe find a solution.

An even more ambitious widening strategy

The previous idea with both a maximum and minimum promotion type didn't pan out, but what if we went much further?

We use the idea of a maxint which is a signed-only integer type that is wider than the widest ordinary type. If i128 is supported natively on the target, then the maxint is i256, if the max normal int type is long (defined as 64 bits in C3), the maxint becomes an i128.

We also have a minimum arithmetic integer type, which is usually will be the exact same as the size of C's int. The algorithm is then as following:

Determine the type of the left hand side. This is the target type. If the target type is unsigned, promote it to the next power-of-two type. E.g. uint -> long.
Check the leaf operands (variables, integer literals, casts, functions). If they exceed the target type this is a compile time error.
Promote the operands to at least the minimum arithmetic integer type.
If the resulting type is more narrow than the target type, promote to the target type.
Trap all operations.
Trap the truncation of the right hand side down to the actual type of the left hand side.

Our u64 = u64 + i32 works now, it is implicitly converted to something like u64 = safeCastWithTrap(addWithTrap(cast(u64 as i128), cast(i32 as i128)), ulong).

So far so good, but something like u64 = u64 + u64 will also need i128. This adds a certain level of safety at a potential cost of performance, even though usually a compiler will optimize away the use of the extra 64 bits for simpler expressions.

This looks promising, but what about wrapping behaviour? We can use the wrapping operators to resolve this using both sides against each other, so that in the case of u64 = i32 +% i16this becomes u64 = safeCastWithTrap(addWrap(i32, cast(i16 as i32)). We prevent implicit unsigned and signed mixing without explicit cast if we cannot convert to either operand: i16 +% u32 would for example be an error.

We allow u32 = i32. This converts into u32 = safeCastWithTrap(i32, u32).

Back to basics, no overflow trapping

Another venue of exploration is to simplify and go back to C. There are some simple changes one can make: implicit widening to use the left hand side, make signed integer overflow wrapping, require casts for mixed unsigned and signed arithmetics to make it more obvious.

We can allow implicit conversion if back from the automatically promoted type, so in the case of i16 = i16 + i16, using C arithmetic promotion rules the operands would for example to i32 before calculation. We can allow implicit truncation back in those cases, but perhaps require explicit casts in all other cases. So i16 = i16 + i32 would require some kind of cast. What simplifies things is that we only need a truncating cast here.

We can introduce trapping arithmetics as well as a trapping assign that requires both arguments already having the same type:

short x = 1;
char b = 16;
int y = 0x7FFF;
// x = x + y; // ERROR, must have explicit cast.
x = x + b;

// The following are not necessary but may be interesting:
x = b ~+ b; // This will trap in due to 16 * 16 > MAX_CHAR
// x = x ~+ b; // ERROR both operands must be the same
x ~= y + 1; // Will trap as the value would overflow
x ~= y; // Would work

Some evaluation

Let us evaluate the different examples using some examples. Here are some code examples that contain vulnerabilities:

func void readpgm(char* name, Pixmap* p)
{
  /* ... */
  pnm_readpaminit(fp, &inpam);
  p.x = inpam.width;
  p.y = inpam.height;
  // Possible overflow
  if (!(p.p = malloc(p.x * p.y)))
  {
    @report("Error at malloc");
  }
  for (int i = 0; i < inpam.height; i++)
  {
    pnm_readpamrow(&inpam, tuplerow);
    for (int j = 0; j < inpam.width; j++)
    {
      // Possible overflow
      p.p[i * inpam.width + j] = sample;
    }
  }
}

func void getComm(uint len, char* src)
{
  uint size;
  // Underflow if len < 2
  size = len - 2;
  // Overflow if size = UINT_MAX
  char* comm = malloc(size + 1);
  memcpy(comm, src, size);
}

func uint* decode_fh(uint* p, SvcFh* fhp)
{
  int size;
  fh_init(fhp, NFS3_FHSIZE);
  size = ntohl(*p++);
  if (size > NFS3_FHSIZE) return NULL;
  // size may be < 0, this converts into a huge size
  memcpy(&fhp.fh_handle.fh_base, p, size);
  fhp.fh_handle.fh_size = size;
  return p + XDR_QUADLEN(size);
}

With those examples presented, let's see how they work out using the two strategies:

The widening strategy

func void readpgm(char* name, Pixmap* p)
{
  /* ... */
  pnm_readpaminit(fp, &inpam);
  p.x = inpam.width;
  p.y = inpam.height;
  // Will trap in debug:
  if (!(p.p = malloc(p.x * p.y)))
  {
    @report("Error at malloc");
  }
  for (int i = 0; i < inpam.height; i++)
  {
    pnm_readpamrow(&inpam, tuplerow);
    for (int j = 0; j < inpam.width; j++)
    {
      // Will trap in debug;
      p.p[i * inpam.width + j] = sample;
    }
  }
}

func void getComm(uint len, char* src)
{
  uint size;
  // Will trap in debug
  size = len - 2;
  char* comm = malloc(size + 1);
  memcpy(comm, src, size);
}

func uint* decode_fh(uint* p, SvcFh* fhp)
{
  int size;
  fh_init(fhp, NFS3_FHSIZE);
  size = ntohl(*p++);
  if (size > NFS3_FHSIZE) return null;
  // Will trap in debug
  memcpy(&fhp.fh_handle.fh_base, p, size);
  fhp.fh_handle.fh_size = size;
  return p + XDR_QUADLEN(size);
}

The widening strategy clearly works perfectly in these examples, all overflows are correctly trapped with zero need for additional annotations. It "just works".

2s complement wrapping

func void readpgm(char* name, Pixmap* p)
{
  /* ... */
  pnm_readpaminit(fp, &inpam);
  p.x = inpam.width;
  p.y = inpam.height;
  // Unchecked, except for negative values, 
  // use "p.p = malloc(convert(p.x ~* p.y as usize))"
  // to trap in both release and debug
  if (!(p.p = malloc(convert(p.x + p.y as usize))))
  {
    @report("Error at malloc");
  }
  for (int i = 0; i < inpam.height; i++)
  {
    pnm_readpamrow(&inpam, tuplerow);
    for (int j = 0; j < inpam.width; j++)
    {
      // Unchecked, use "i ~* inpam.width ~+ j"
      // to trap in both release and debug
      // but the problem lies in the earlier malloc check.
      p.p[i * inpam.width + j] = sample;
    }
  }
}

func void getComm(uint len, char* src)
{
  uint size;
  // Not checked, use
  // len ~- 2 to trap in both release and debug
  // but it is more natural to check this with
  // preconditions, e.g. assert(len >= 2)
  // So trapping is probably the wrong decision
  size = len - 2;
  char* comm = malloc(size + 1);
  memcpy(comm, src, size);
}

func uint* decode_fh(uint* p, SvcFh* fhp)
{
  int size;
  fh_init(fhp, NFS3_FHSIZE);
  size = ntohl(*p++);
  if (size > NFS3_FHSIZE) return null;
  // Here we are forced to convert
  // it's natural to use a trapping conversion
  // that protects in both release and debug
  memcpy(&fhp.fh_handle.fh_base, p, convert(size as usize));
  fhp.fh_handle.fh_size = size;
  return p + XDR_QUADLEN(size);
}

In these cases we see that the widening strategy has a very clear advantage in detecting errors. This is not surprising, since it's exactly what it's built for. On the other hand the explicit trapping operators give us stronger protection where it's used and the type model is so much simpler.

That last argument is the strongest in favour of "wrapping". Although we in this particular example manage to demonstrate that "widening" works, it introduces a lot of machinery to add the traps and there are enough implicit checks that we can't prove for sure that the behaviour isn't without problems. And yes u32 = u32 + i32 will make implicit checks for overflow, but maybe that should be checked before the assignment? The traps are very useful during testing, but they're no replacement for code that correctly checks arguments. In C3's case there is already support for contracts which catches many of the errors above as long as the function are properly documented, so unlike other languages it already has a somewhat higher level of security.

Summary

I've presented two quite different models, each with its own advantages and disadvantages. Ultimately what decides what to use is not just the security concerns, but how well it fits with the language in general. Other features may interact in a surprising manner, so it's only after working with a model in practice one can see the real effects on the language as a whole.

March 2, 2021
3 min read

How to procrastinate while working hard

Originally from: https://c3.handmade.network/blog/p/7657-how_to_procrastinate_while_working_hard

Refactoring is an important part of programming. If you are maintaining a non-trivial code base you need to constantly remove cruft and improve on solutions otherwise the code will slowly rot.

Working with improving abstractions and code quality there is also a lure which is mostly ignored, which is over-engineering. The urge to add code that feels “magical” and just does things in an extremely elegant way. You can find examples in amazing C++ templates, or some awesomely elegant Swift code that might use some combination of operator overloading, generics and pattern matching. It might look cool, but over-engineering is dangerous.

It’s dangerous because you can spend days on that “perfect abstraction” which might be elegant on the surface — but your teammates will have a less pleasant time trying to figure out how to debug or extend it later on.

It’s dangerous because all that time you spent might make you reluctant to find easier solutions, or throw it away when it’s no longer needed.

It’s dangerous because that complexity disguised as abstraction is making your code less maintainable and also less easy to understand.

It’s dangerous because you might have thrown away bug free code and replaced it with something new and untested because you thought it might look more elegant.

But most of all it’s dangerous because it’s so damned satisfying to just find those beautiful abstractions. It’s so much fun that we forget how dangerous it is.

So when you feel the urge — remember restraint. The “magically cool things” your language can do are usually exactly those parts that you should stay clear of.

(Previously posted on dev.to)