Proposal: namespace type equivalence based on AST node + captures

[mlugg]

Background

In status quo Zig, namespace types are unique. Whenever a struct { ... }, union { ... }, enum { ... }, or opaque { ... } is encountered, a new type - distinct from all others - is created. Broadly speaking, this is a reasonable design, but it has some unfortunate consequences.

Firstly, it can result in overinstantiation. Consider the following code:

fn f(comptime T: type, x: struct { y: T }) void {
    _ = x;
}
test {
    f(u32, .{ .y = 1 });
    f(u32, .{ .y = 1 });
}

Here, we would naturally expect that there is only one instantion of f, and that it is called twice. However, since f is a generic function, all generic parameter types are evaluated at every call site. That means the parameter type for the first call to f is a structurally equivalent but distinct type to the second call, because the struct { y: T } declaration is evaluated separately each time. This can result in significant over-instantiation if code is written like this.

Secondly, this feature means that comptime call memoization has an impact on language semantics, and must therefore be codified into the language specification. This can be seen by considering the following trivial code:

fn Empty() type {
    return struct {};
}
comptime {
    if (Empty() != Empty()) unreachable; // assertion failure
}

It is important that this assertion passes, since this is fundamental to Zig's system of generics; and with memoization (status quo), it does pass. However, if calls were not memoized, the assertion would fail, as each call to Empty would create a distinct type. Having memoization impact language semantics complicates the specification, particularly since we can't memoize function calls whose arguments contain references to comptime-mutable memory (since such memory may be mutated by the function).

Lastly, this design has unfortunate consequences for incremental compilation. Consider the following code:

fn g() void {
    _ = struct {};
    _ = struct {};
}

When performing an incremental update of g, we wish to correlate each struct declaration in this code with the declarations in the previous code. However, there isn't an easy way of doing that at the minute. We could do it based on AST node, but if these structs are created by a function call, the AST node might be the same, making the types distinct, and then there truly is no easy way for the compiler to figure out how to correlate these.

Proposal

Define namespace types (struct etc) to be equivalent to any types defined at the same AST node with the same set of captures. Note that to do this, lazy capture values must be resolved, so this is a potentially breaking change.

Captures are the only way a type with the same AST node can structurally differ; capturing values derived from generic arguments may allow field types / init values / etc to differ between evaluations of one source declaration. However, if we include these captures in the "key" for the equivalence relation, we get a consistent definition of equivalent struct types. This solves all of the problems listed above:

• Generic calls will still re-evaluate their parameter types, but they will resolve to the same type if the captured field type T matches, so the same instantiation will be used.
• If Empty were not memoized, it would return the same type (there are no captures), so memoization is no longer required to be a part of the language specification.
• During an incremental update, the compiler can find an existing instantiation based on ZIR instruction index (already tracked by the TrackedInst abstraction) and captured values, and update it as needed.

This proposal has been accepted by @andrewrk for now, but of course is open for reconsideration if it raises issues. However, I can't think of any potential problems; as far as I can tell, this proposal should be a strict win for language simplicity, binary sizes, and compilation speed.

[andrewrk]

Thanks for the writeup. Looking at this with fresh eyes, I'm confident to move forward with it.

[rohlem]

I don't see any real issue with this proposal, the only unfortunate side-effect I wanted to have pointed out somewhere is that by using the AST node as key, inline expansions (mainly inline for loops, inline else cases and the bodies of inline fn), which only appear in AST once AFAIK, no longer act exactly the same as when unrolled by hand:

const E = enum{a, b};
fn foo(comptime e: E) type { //foo(.a) != foo(.b) will still hold under new semantics
 return switch(e) {
  .a => opaque {},
  .b => opaque {},
 };
}
fn bar(comptime e: E) type { //new semantics will make bar(.a) == bar(.b), unless e is used within it
 return switch(e) {
  inline else => opaque {},
 };
}

It would be possible to tweak the definition (inserting another synthetic key) to retain this equivalence,
but it's probably not worth complicating the implementation just for this regularity edge-case.

[mlugg]

Yeah, if you need to generate distinct opaques without methods like that for some reason you could just do a comptime { _ = differentiating_val; } within them. Definitely a good point though!

[InKryption]

Yeah, if you need to generate distinct opaques without methods like that for some reason you could just do a comptime { _ = differentiating_val; } within them. Definitely a good point though!

Something like this I'm assuming? (for posterity)

fn Bar(comptime e: E) type {
    return opaque {
        comptime {
            _ = e;
        }
    };
}

[mlugg]

Yup, exactly. You don't need to really think about the technicalities of captures; you just ask yourself "would this struct have different semantics / a different meaning across these two instantiations?"

[Jarred-Sumner]

I wonder if this will end up reducing binary size

[mlugg]

An open question heree: how does this interact with reification (@Type)? In my mind, the obvious thing is that two reified types are to be equivalent if they:

• Are created at the same AST node
• Are the same "kind" of type (struct vs union vs etc)
• Have matching attributes, field types, default values, etc
  • Note that this does require resolving lazy default field values, so is again a breaking change

So, for instance, in the following, Foo(A) == Foo(B) despite A != B:

const A = struct { x: u32 };
const B = struct { y: u32 };
fn Foo(comptime T: type) type {
    // Equivalent to `struct { x: usize = @sizeOf(T) }`, which would *not* be equivalent for distinct T
    // However, `const sz = @sizeOf(T); return struct { x: usize = sz };` would be
    return @Type(.{ .Struct = .{
        .layout = .Auto,
        .fields = &.{.{
            .name = "x",
            .type = usize,
            .default_value = @sizeOf(T),
            .is_comptime = false,
            .alignment = 0,
        }},
        .decls = &.{},
        .is_tuple = false,
    } });
}

This is what I'm going to go with for now, but of course, this is open to discussion (I'm interested to hear your thoughts @andrewrk).