why c can get away with incomplete arrays being a "real type" but hare can't

this is an array declaration in c:

int foo[4];

here it is with an initializer:

int foo[4] = { 1, 2, 3, 4 };

if you have an initializer, you can omit the length in the brackets, to allow the length to be inferred:

int foo[] = { 1, 2, 3, 4 };

this is an array declaration in hare:

let foo: [4]int = [1, 2, 3, 4];

hare allows you to do the same thing, by replacing the number with an underscore:

let foo: [_]int = [1, 2, 3, 4];

in hare terminology, [_]T is a context-defined array type. for a long time, these were allowed anywhere other types were allowed, and so they were the source of a lot of bugs. in the next release (or right now on master), this has been changed: [_]T is now only allowed in the grammar for declarations and bindings. that is, [_]T is no longer a "real" type, as it never should've been to begin with.

in the future we may allow [_]T to appear in more places. for example, we may allow multidimensional context-defined arrays ([_][_]T), nested context-defined arrays (*[_]T), or allowing them to appear in places like cast expressions ([1, 2, 3]: [_]u8). which of these (if any) are allowed in the future remains to be seen, but they'll need to be treated as special cases, because again, [_]T isn't a real type.

however, in c, T [] is a "real" type; it's not a syntax thing. that's kinda odd, right? why don't incomplete array types (as they're called in c) cause bugs? why can't hare just copy what c does?

in this post, i'll show that hare can't copy c here, because hare's type system is fundamentally different from c's (at least in this regard). c's incomplete arrays behave very differently from hare's context-defined arrays.

what does c do?

c has a notion of incomplete types. incomplete arrays are one such example, but another example is forward declarations of structs and unions:

struct foo; // `struct foo` is an incomplete type
struct foo { int x; }; // now the type is completed

as a special case, void is an incomplete type which can't be completed.

incomplete types don't have a known size, so you can't allocate any storage for a declaration with such a type:

struct foo;
struct foo bar; // error: struct foo is incomplete
void x; // error: void is incomplete

however, they can be completed later in the translation unit. consider these declarations in file scope:

char x[];
char x[3];

char [] and char [3] are distinct types, but they're compatible types. so when x is redeclared, its type is changed to the composite type, which in this case is char [3]. here's some more examples:

char y[3];
char y[]; // no change: y's type is `char [3]`

// this also applies across other declarators
// pointer to function (pointer to array) returning pointer to array
int (*(*x)(int (*)[3]))[];
int (*(*x)(int (*)[]))[3];
// x's type is adjusted to `int (*(*)(int (*)[3]))[3]`

incomplete arrays have a special case though: if the initializer is a compound literal or a string literal, then the binding's type is adjusted to a complete array type after the declaration is completed. so in this declaration:

int foo[] = { 1, 2, 3, 4 };

foo's type is int [4], not int []. here, check this out:

size_t x[] = {
	// error: x's type is int [], so you can't take its size
	sizeof(x)
};
return sizeof(x); // ok: x's type is now `int [4]`

one other special case is that, if a declaration of an incomplete array has external linkage, for the purpose of allocating storage it's treated as though it had exactly one element:

char x[]; // allocates 1 byte of storage, as if it were `char [1]`

gcc and clang will both warn about this though. even though it's standard and well-defined behavior, it's kinda unintuitive that this doesn't error out.

but yeah, incomplete arrays are pretty much stand-ins for arrays without a known size. the initializer special case exists because, well, if you're initializing it, then the size is known, so the type is adjusted for you. but that's just a special case. there's other valid places you may use an incomplete array type:

extern char x[]; // externally defined array with unknown length
typedef char (*T)[]; // pointer to incomplete array

one notable thing here is that int [][] is not valid, because you can't have an array of an incomplete type! so when inferring the length of a multidimensional array, only the outermost array length can be inferred.

what does hare do?

when declaring an array with a context-defined length, its length is inferred before the binding is inserted into scope. the binding's type is an array with the inferred length:

let x: [_]int = [1, 2, 3, 4];
// x's type is [4]int

unlike in c, bindings aren't inserted into scope until after their initializer is complete, so x can't be accessed within its own initializer.

and... that's it!

here's why we can't copy c

hare doesn't have incomplete types, nor do we have any equivalent for "compatible" or "composite" types, so we can't piggyback off of c's semantics. context-defined arrays truly are a special case, so they don't cleanly fit into hare's type system. we'd need to add special type deduction semantics just for context-defined arrays in order to mimick c's behavior.

it's worth noting that c's incomplete arrays are much more similar to hare's unbounded arrays than to context-defined arrays. the initializer special case means that incomplete arrays can be used to infer the type of a declaration, but that's just a special case. unlike c, which combines array length inference and unbounded arrays into the same type, hare has a dedicated unbounded array type:

let x: *[*]int = &foo; // pointer to unbounded array

so the earlier extern char x[] c example would look like this in hare:

let x: [*]c::char;

(note that hare doesn't have an extern keyword; top-level declarations without an initializer have the same behavior as c's extern.)

here's another example. here's a declaration in c:

struct foo {
	int x;
	char y[];
};

and here it is in hare:

type foo = struct {
	x: int,
	y: [*]u8,
};

both c and hare have a special case for flexible arrays as the last member of a struct. they actually have slightly different behavior (in hare the type has undefined size and can't be stack allocated, but in c the last field is just ignored for a lot of operations), but that's out of scope of this post. i'll probably write about it sometime in the future though ;)

VLAs

in addition to array types with known constant size and incomplete arrays, c also has variable-length arrays, or VLAs.

int x[n]; // size isn't known at compile-time, but it's still a complete type!

these are relevant because there's actually two kinds of VLAs: VLAs with a specified (known) size, and VLAs with an unspecified size, which are denoted with [*]. the latter are only allowed in the type of a parameter in a function type or declaration (but notably not a function definition; I'll explain why in a sec), or, as of c2y, in a _Generic case.

// parameter `x` is a pointer to a VLA with unspecified size
int f(int (*x)[*]);

don't get confused: these share the same syntax as hare's unbounded arrays, but they're completely unrelated.

VLAs with unspecified size are notable because, unlike incomplete arrays, they're always complete types, meaning that they can be used as the element type of another array type. so, under certain circumstances, it actually is possible in c to denote an array of an array with unknown (actually "unspecified" but whatever) size, by once again taking advantage of type compatibility (composite type) rules:

void f(int (*)[*][*]);
void f(int (*)[*][3]);
void f(int (*)[3][*]);
// f's type is `void (int (*)[3][3])`

// since c2y: x is initialized to 1 if foo is a two-dimensional
// array of int, regardless of the array lengths or whether or
// not they're complete.
int x = _Generic(foo,
	int [*][*]: 1,
	default: 0);

// this isn't possible anywhere else
int x[1][*]; // error: [*] disallowed, both in file scope *and* block scope

and yes, i did just fully unironically wrote the type int (*)[*][*]. c's syntax is very funny.

once again, this is a consequence of c's type compatibility rules, so it can't be directly applied to hare.

in case you're curious why the hell these actually exist: in function definitions, VLA lengths are evaluated before the function is run, but in function types and declarations, they aren't ever evaluated. in fact, in function types and declarations (function prototype scope), all VLAs are adjusted to [*]. [*] is just a way to denote a VLA without needing to unnecessarily specify its size, like if you're in a header file and the parameters don't have names, for example. then they later "borrowed" the syntax for _Generic, because like why not i guess

conclusion

context-defined arrays in hare are very dissimilar to c's incomplete arrays, hence why c can get away with them being regular types while they used to cause so many problems for us in hare. c's incomplete arrays are a weird hybrid between unbounded arrays and context-defined arrays, but are more similar to unbounded arrays in most cases.