introduce "lazy values" concept to fix false positive dependency loops

[andrewrk]

This is a proposal to solve these issues:

• C code generates depends on itself false positive #1310
• "depends on itself" false positive #624
• error: <function const> depends on itself #1144

Also, importantly it fixes this hack which is in master branch:

zig/src/analyze.cpp

Lines 2249 to 2258 in 85edf55

	// TODO If we have no type_entry for the field, we've already failed to
	// compile the program correctly. This stage1 compiler needs a deeper
	// reworking to make this correct, or we can ignore the problem
	// and make sure it is fixed in stage2. This workaround is for when
	// there is a false positive of a dependency loop, of alignment depending
	// on itself. When this false positive happens we assume a pointer-aligned
	// field, which is usually fine but could be incorrectly over-aligned or
	// even under-aligned. See https://github.com/ziglang/zig/issues/1512
	} else if (field->type_entry == nullptr) {
	this_field_align = g->builtin_types.entry_usize->abi_align;

I prototyped this in 3dc8448 and it seemed to be a reasonable solution, but I removed it in d3f2fe2 because it was part of a larger branch (see #2135) and I needed to constrain the scope of the branch.

Here's the fundamental problem:

const Node = struct {
    payload: i32,
    children: []align(@alignOf(Node)) Node,
};
test "" {
    var x: Node = undefined;
}

This activates the hack mentioned above. The problem is that when analyzing the fields of the Node struct, even just to find out if it is a zero bit type or not, zig has to evaluate the expression []align(@alignOf(Node)) Node. This creates the Zig IR:

Entry_0:
  #1  | (unknown)   | 1 | &Node
  #2  | (unknown)   | 1 | #1.*
  #3  | (unknown)   | 1 | @alignOf(#2)
  #4  | (unknown)   | 1 | &Node
  #5  | (unknown)   | 1 | #4.*
  #6  | (unknown)   | 2 | []#5
  #7  | (unknown)   | - | @addImplicitReturnType(#6)
  #8  | noreturn    | - | return #6

Which then has to be evaluated to a type. The important thing to note here is that it must evaluate @alignOf(Node). But this IR is being evaluated in the context of even just trying to figure out if Node is zero bits, let alone the next step of determining its alignment. This is where the dependency loop comes from.

The hack in master branch gives up and assumes pointer sized alignment, which isn't sound reasoning, but just happens to be usually correct by accident.

This proposal would make the above Zig IR resolve into a "lazy value" without having to actually compute @alignOf(Node) into a numerical value. To give the idea of how it works:

• @alignOf(Node) turns into the lazy value #3 = {LazyAlignOf, Node}.
• []align(#3) Node turns into the lazy value #6 = {LazySliceType, align=#3, Node}.
• This value is returned from the Zig IR. So we have computed a result of []align(@alignOf(Node)) Node without knowing the numerical value of @alignOf(Node) yet.
• At any point a lazy value can be forced to resolve. This will produce a normal comptime value. This would emit a dependency loop error if there is one.
• However we can ask certain questions of lazy values without forcing them to resolve yet. For example, the original code that is trying to resolve whether Node is a zero bit type or not, it can ask, is the lazy value #6 zero bits or not? And the logic for asking this question can look at the lazy value, and see that it is a LazySliceType. Without having to fully resolve the value, it already knows the answer is "no", because slices are never zero bits (there is always the length). So, resolve_struct_zero_bits is able to complete, without a dependency loop.

This proposal is potentially also related to #157 - builtin function to tell you the stack size of a function. Zig wouldn't be able to give a numerical value for this, but it would still be a comptime known value, and should still be able to be used in arrays and other contexts. This could be a lazy value - potentially someone could even add a comptime integer to this value, and in code generation zig would be able to emit LLVM with the correct value, even though during normal comptime code execution the actual numerical value would not be available yet.

One question that comes up with this proposal is this example:

const Node = struct {
    next: *Node,
};
test "" {
    var x: Node = undefined;
}

Should Node be a zero bit type or not? I think the answer should be "no", but it's tricky to describe exactly why.

Zig's current answer to this question is problematic, which is "if I'm already trying to determine if a struct has zero bits, and the answer to that depends on whether or not it is zero bits, then the answer is no." With lazy values implemented, it would be helpful to have a more precise definition of when a struct has zero bits or not.

[eira-fransham]

I'm having this problem in a toy jump threading interpreter - I want a pointer to a function that takes a pointer to a function etc. Maybe have all comptime values be non-strict since they can't have side-effects anyway?

[andrewrk]

Done with the merge of #3115

[emekoi]

related issues:

• Union with type that has optional field causes segfault in compiler #1995
• segfault when compiling struct with optional list of self #1735
• support two structs with recursive optional references #2746
• nullable type compiler error #1805
• Recursive function definitions do not compile while equivalent structs do. #1114
• Objective-C Headers cause dependency loop #2846
• Unable to resolve const ptr to function #2352
• Printing a File struct fails on Linux #2584
• ability to obtain return type of generic function when it has no dependencies #846
• Getting @typeInfo of a struct inside that struct causes Zig to segfault #2968
• Dependency loop in freetype2 headers #2202