ability for global variables to be initialized with address of each other #131

andrewrk · 2016-03-01T03:18:03Z

const std = @import("std");
const expect = std.testing.expect;

const Node = struct {
    next: *Node,
};

const a: Node = .{ .next = &b };
const b: Node = .{ .next = &a };

test "example" {
    expect(a.next == &b);
    expect(b.next == &a);
}

Currently, this test case produces the following results:

test.zig:8:1: error: dependency loop detected
const a: Node = .{ .next = &b };
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
referenced by:
    a: test.zig:8:29
    b: test.zig:9:29
    remaining reference traces hidden; use '-freference-trace' to see all reference traces

The text was updated successfully, but these errors were encountered:

This is a workaround for a limitation of the stage1 zig compiler See: ziglang/zig#131

This commit changes how declarations (`const`, `fn`, `usingnamespace`, etc) are represented in ZIR. Previously, these were represented in the container type's extra data (e.g. as trailing data on a `struct_decl`). However, this introduced the complexity of the ZIR mapping logic having to also correlate some ZIR extra data indices. That isn't really a problem today, but it's tricky for the introduction of `TrackedInst` in the commit following this one. Instead, these type declarations now simply contain a trailing list of ZIR indices to `declaration` instructions, which directly encode all data related to the declaration (including containing the declaration's body). Additionally, the ZIR for `align` etc have been split out into their own bodies. This is not strictly necessary, but it's much simpler to understand for an insignificant cost in bytes, and will simplify the resolution of ziglang#131 (where we may need to evaluate the pointer type, including align etc, without immediately evaluating the value body).

The type `Zcu.Decl` in the compiler is problematic: over time it has gained many responsibilities. Every source declaration, container type, generic instantiation, and `@extern` has a `Decl`. The functions of these `Decl`s are in some cases entirely disjoint. After careful analysis, I determined that the two main responsibilities of `Decl` are as follows: * A `Decl` acts as the "subject" of semantic analysis at comptime. A single unit of analysis is either a runtime function body, or a `Decl`. It registers incremental dependencies, tracks analysis errors, etc. * A `Decl` acts as a "global variable": a pointer to it is consistent, and it may be lowered to a specific symbol by the codegen backend. This commit eliminates `Decl` and introduces new types to model these responsibilities: `Cau` (Comptime Analysis Unit) and `Nav` (Named Addressable Value). Every source declaration, and every container type requiring resolution (so *not* including `opaque`), has a `Cau`. For a source declaration, this `Cau` performs the resolution of its value. (When ziglang#131 is implemented, it is unsolved whether type and value resolution will share a `Cau` or have two distinct `Cau`s.) For a type, this `Cau` is the context in which type resolution occurs. Every non-`comptime` source declaration, every generic instantiation, and every distinct `extern` has a `Nav`. These are sent to codegen/link: the backends by definition do not care about `Cau`s. This commit has some minor technically-breaking changes surrounding `usingnamespace`. I don't think they'll impact anyone, since the changes are fixes around semantics which were previously inconsistent (the behavior changed depending on hashmap iteration order!). Aside from that, this changeset has no user-facing changes. Instead, it is an internal refactor which makes it easier to correctly model the responsibilities of different objects, particularly regarding incremental compilation. The performance impact should be negligible, but I will take measurements before merging this work into `master`.

The type `Zcu.Decl` in the compiler is problematic: over time it has gained many responsibilities. Every source declaration, container type, generic instantiation, and `@extern` has a `Decl`. The functions of these `Decl`s are in some cases entirely disjoint. After careful analysis, I determined that the two main responsibilities of `Decl` are as follows: * A `Decl` acts as the "subject" of semantic analysis at comptime. A single unit of analysis is either a runtime function body, or a `Decl`. It registers incremental dependencies, tracks analysis errors, etc. * A `Decl` acts as a "global variable": a pointer to it is consistent, and it may be lowered to a specific symbol by the codegen backend. This commit eliminates `Decl` and introduces new types to model these responsibilities: `Cau` (Comptime Analysis Unit) and `Nav` (Named Addressable Value). Every source declaration, and every container type requiring resolution (so *not* including `opaque`), has a `Cau`. For a source declaration, this `Cau` performs the resolution of its value. (When #131 is implemented, it is unsolved whether type and value resolution will share a `Cau` or have two distinct `Cau`s.) For a type, this `Cau` is the context in which type resolution occurs. Every non-`comptime` source declaration, every generic instantiation, and every distinct `extern` has a `Nav`. These are sent to codegen/link: the backends by definition do not care about `Cau`s. This commit has some minor technically-breaking changes surrounding `usingnamespace`. I don't think they'll impact anyone, since the changes are fixes around semantics which were previously inconsistent (the behavior changed depending on hashmap iteration order!). Aside from that, this changeset has no user-facing changes. Instead, it is an internal refactor which makes it easier to correctly model the responsibilities of different objects, particularly regarding incremental compilation. The performance impact should be negligible, but I will take measurements before merging this work into `master`.

The type `Zcu.Decl` in the compiler is problematic: over time it has gained many responsibilities. Every source declaration, container type, generic instantiation, and `@extern` has a `Decl`. The functions of these `Decl`s are in some cases entirely disjoint. After careful analysis, I determined that the two main responsibilities of `Decl` are as follows: * A `Decl` acts as the "subject" of semantic analysis at comptime. A single unit of analysis is either a runtime function body, or a `Decl`. It registers incremental dependencies, tracks analysis errors, etc. * A `Decl` acts as a "global variable": a pointer to it is consistent, and it may be lowered to a specific symbol by the codegen backend. This commit eliminates `Decl` and introduces new types to model these responsibilities: `Cau` (Comptime Analysis Unit) and `Nav` (Named Addressable Value). Every source declaration, and every container type requiring resolution (so *not* including `opaque`), has a `Cau`. For a source declaration, this `Cau` performs the resolution of its value. (When ziglang#131 is implemented, it is unsolved whether type and value resolution will share a `Cau` or have two distinct `Cau`s.) For a type, this `Cau` is the context in which type resolution occurs. Every non-`comptime` source declaration, every generic instantiation, and every distinct `extern` has a `Nav`. These are sent to codegen/link: the backends by definition do not care about `Cau`s. This commit has some minor technically-breaking changes surrounding `usingnamespace`. I don't think they'll impact anyone, since the changes are fixes around semantics which were previously inconsistent (the behavior changed depending on hashmap iteration order!). Aside from that, this changeset has no user-facing changes. Instead, it is an internal refactor which makes it easier to correctly model the responsibilities of different objects, particularly regarding incremental compilation. The performance impact should be negligible, but I will take measurements before merging this work into `master`.

The type `Zcu.Decl` in the compiler is problematic: over time it has gained many responsibilities. Every source declaration, container type, generic instantiation, and `@extern` has a `Decl`. The functions of these `Decl`s are in some cases entirely disjoint. After careful analysis, I determined that the two main responsibilities of `Decl` are as follows: * A `Decl` acts as the "subject" of semantic analysis at comptime. A single unit of analysis is either a runtime function body, or a `Decl`. It registers incremental dependencies, tracks analysis errors, etc. * A `Decl` acts as a "global variable": a pointer to it is consistent, and it may be lowered to a specific symbol by the codegen backend. This commit eliminates `Decl` and introduces new types to model these responsibilities: `Cau` (Comptime Analysis Unit) and `Nav` (Named Addressable Value). Every source declaration, and every container type requiring resolution (so *not* including `opaque`), has a `Cau`. For a source declaration, this `Cau` performs the resolution of its value. (When ziglang#131 is implemented, it is unsolved whether type and value resolution will share a `Cau` or have two distinct `Cau`s.) For a type, this `Cau` is the context in which type resolution occurs. Every non-`comptime` source declaration, every generic instantiation, and every distinct `extern` has a `Nav`. These are sent to codegen/link: the backends by definition do not care about `Cau`s. This commit has some minor technically-breaking changes surrounding `usingnamespace`. I don't think they'll impact anyone, since the changes are fixes around semantics which were previously inconsistent (the behavior changed depending on hashmap iteration order!). Aside from that, this changeset has no significant user-facing changes. Instead, it is an internal refactor which makes it easier to correctly model the responsibilities of different objects, particularly regarding incremental compilation. The performance impact should be negligible, but I will take measurements before merging this work into `master`. Co-authored-by: Jacob Young <[email protected]> Co-authored-by: Jakub Konka <[email protected]>

The new representation is often more compact. It is also more straightforward to understand: for instance, `extern` is represented on the `declaration` instruction itself rather than using a special instruction. The same applies to `var`, making both of these far more compact. This commit also separates the type and value bodies of a `declaration` instruction. This is a prerequisite for ziglang#131. In general, `declaration` now directly encodes details of the syntax form used, and the embedded ZIR bodies are for actual expressions. The only exception to this is functions, where ZIR is effectively designed as if we had ziglang#1717. `extern fn` declarations are modeled as `extern const` with a function type, and normal `fn` definitions are modeled as `const` with a `func{,_fancy,_inferred}` instruction. This may change in the future, but improving on this was out of scope for this commit.

The `Cau` abstraction originated from noting that one of the two primary roles of the legacy `Decl` type was to be the subject of comptime semantic analysis. However, the data stored in `Cau` has always had some level of redundancy. While preparing for ziglang#131, I went to remove that redundany, and realised that `Cau` now had exactly one field: `owner`. This led me to conclude that `Cau` is, in fact, an unnecessary level of abstraction over what are in reality *fundamentally different* kinds of analysis unit (`AnalUnit`). Types, `Nav` vals, and `comptime` declarations are all analyzed in different ways, and trying to treat them as the same thing is counterproductive! So, these 3 cases are now different alternatives in `AnalUnit`. To avoid stealing bits from `InternPool`-based IDs, which are already a little starved for bits due to the sharding datastructures, `AnalUnit` is expanded to 64 bits (30 of which are currently unused). This doesn't impact memory usage too much by default, because we don't store `AnalUnit`s all too often; however, we do store them a lot under `-fincremental`, so a non-trivial bump to peak RSS can be observed there. This will be improved in the future when I made `InternPool.DepEntry` less memory-inefficient. `Zcu.PerThread.ensureCauAnalyzed` is split into 3 functions, for each of the 3 new types of `AnalUnit`. The new logic is much easier to understand, because it avoids conflating the logic of these fundamentally different cases.

This commit separates semantic analysis of the annotated type vs value of a global declaration, therefore allowing recursive and mutually recursive values to be declared. Every `Nav` which undergoes analysis now has *two* corresponding `AnalUnit`s: `.{ .nav_val = n }` and `.{ .nav_ty = n }`. The `nav_val` unit is responsible for *fully resolving* the `Nav`: determining its value, linksection, addrspace, etc. The `nav_ty` unit, on the other hand, resolves only the information necessary to construct a *pointer* to the `Nav`: its type, addrspace, etc. (It does also analyze its linksection, but that could be moved to `nav_val` I think; it doesn't make any difference). Analyzing a `nav_ty` for a declaration with no type annotation will just mark a dependency on the `nav_val`, analyze it, and finish. Conversely, analyzing a `nav_val` for a declaration *with* a type annotation will first mark a dependency on the `nav_ty` and analyze it, using this as the result type when evaluating the value body. The `nav_val` and `nav_ty` units always have references to one another: so, if a `Nav`'s type is referenced, its value implicitly is too, and vice versa. However, these dependencies are trivial, so, to save memory, are only known implicitly by logic in `resolveReferences`. In general, analyzing ZIR `decl_val` will only analyze `nav_ty` of the corresponding `Nav`. There are two exceptions to this. If the declaration is an `extern` declaration, then we immediately ensure the `Nav` value is resolved (which doesn't actually require any more analysis, since such a declaration has no value body anyway). Additionally, if the resolved type has type tag `.@"fn"`, we again immediately resolve the `Nav` value. The latter restriction is in place for two reasons: * Functions are special, in that their externs are allowed to trivially alias; i.e. with a declaration `extern fn foo(...)`, you can write `const bar = foo;`. This is not allowed for non-function externs, and it means that function types are the only place where it is possible for a declaration `Nav` to have a `.@"extern"` value without actually being declared `extern`. We need to identify this situation immediately so that the `decl_ref` can create a pointer to the *real* extern `Nav`, not this alias. * In certain situations, such as taking a pointer to a `Nav`, Sema needs to queue analysis of a runtime function if the value is a function. To do this, the function value needs to be known, so we need to resolve the value immediately upon `&foo` where `foo` is a function. This restriction is simple to codify into the eventual language specification, and doesn't limit the utility of this feature in practice. A consequence of this commit is that codegen and linking logic needs to be more careful when looking at `Nav`s. In general: * When `updateNav` or `updateFunc` is called, it is safe to assume that the `Nav` being updated (the owner `Nav` for `updateFunc`) is fully resolved. * Any `Nav` whose value is/will be an `@"extern"` or a function is fully resolved; see `Nav.getExtern` for a helper for a common case here. * Any other `Nav` may only have its type resolved. This didn't seem to be too tricky to satisfy in any of the existing codegen/linker backends. Resolves: ziglang#131

The `Cau` abstraction originated from noting that one of the two primary roles of the legacy `Decl` type was to be the subject of comptime semantic analysis. However, the data stored in `Cau` has always had some level of redundancy. While preparing for ziglang#131, I went to remove that redundany, and realised that `Cau` now had exactly one field: `owner`. This led me to conclude that `Cau` is, in fact, an unnecessary level of abstraction over what are in reality *fundamentally different* kinds of analysis unit (`AnalUnit`). Types, `Nav` vals, and `comptime` declarations are all analyzed in different ways, and trying to treat them as the same thing is counterproductive! So, these 3 cases are now different alternatives in `AnalUnit`. To avoid stealing bits from `InternPool`-based IDs, which are already a little starved for bits due to the sharding datastructures, `AnalUnit` is expanded to 64 bits (30 of which are currently unused). This doesn't impact memory usage too much by default, because we don't store `AnalUnit`s all too often; however, we do store them a lot under `-fincremental`, so a non-trivial bump to peak RSS can be observed there. This will be improved in the future when I made `InternPool.DepEntry` less memory-inefficient. `Zcu.PerThread.ensureCauAnalyzed` is split into 3 functions, for each of the 3 new types of `AnalUnit`. The new logic is much easier to understand, because it avoids conflating the logic of these fundamentally different cases.

andrewrk added the enhancement Solving this issue will likely involve adding new logic or components to the codebase. label Mar 1, 2016

andrewrk modified the milestone: 0.1.0 May 7, 2016

andrewrk modified the milestones: 0.1.0, 0.2.0 Apr 20, 2017

andrewrk modified the milestones: 0.2.0, 0.3.0 Oct 20, 2017

andrewrk modified the milestones: 0.3.0, 0.4.0 Feb 28, 2018

andrewrk modified the milestones: 0.4.0, 0.5.0 Feb 2, 2019

andrewrk modified the milestones: 0.5.0, 0.6.0 Aug 27, 2019

andrewrk modified the milestones: 0.6.0, 0.7.0 Dec 9, 2019

andrewrk modified the milestones: 0.7.0, 0.8.0 Oct 9, 2020

andrewrk added the frontend Tokenization, parsing, AstGen, Sema, and Liveness. label Oct 9, 2020

ifreund added a commit to ifreund/zig-wayland that referenced this issue Oct 11, 2020

Link libwayland generated interface structs

66d50b6

This is a workaround for a limitation of the stage1 zig compiler See: ziglang/zig#131

andrewrk modified the milestones: 0.8.0, 0.9.0 Jun 4, 2021

andrewrk modified the milestones: 0.9.0, 0.10.0 Nov 21, 2021

andrewrk modified the milestones: 0.10.0, 0.11.0 Apr 17, 2022

kdchambers mentioned this issue Dec 17, 2022

sysaudio: rewrite in zig hexops/mach#641

Merged

1 task

praschke mentioned this issue Feb 2, 2023

false dependency loop with recursive declaration addresses #14517

Closed

travisstaloch mentioned this issue Feb 5, 2023

generated zig code produces dependency loop errors for recursive types travisstaloch/protobuf-zig#1

Open

3 tasks

Vexu mentioned this issue Jul 14, 2023

Arrays init: error: dependency loop detected #16407

Closed

andrewrk modified the milestones: 0.13.0, 0.12.0 Jul 20, 2023

dimdin mentioned this issue Feb 25, 2024

Unexpected type dependency loop when declaring a function pointer to a function that returns its own type. #18664

Open

mlugg mentioned this issue Mar 24, 2024

compiler: implement analysis-local comptime-mutable memory #19414

Merged

mlugg mentioned this issue Aug 6, 2024

compiler: split Decl into Nav and Cau #20964

Merged

mlugg mentioned this issue Dec 7, 2024

Proposal: remove Peer Type Resolution from the language #22182

Open

andrewrk mentioned this issue Dec 15, 2024

compiler: remove doc comments from Zir #22245

Merged

mlugg mentioned this issue Dec 23, 2024

compiler: analyze type and value of global declarations separately #22303

Merged

mlugg closed this as completed in 3afda43 Dec 25, 2024

Fri3dNstuff mentioned this issue Dec 25, 2024

erroneous dependency loop for globals self/mutually referencing the addresses of fields #22314

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ability for global variables to be initialized with address of each other #131

ability for global variables to be initialized with address of each other #131

andrewrk commented Mar 1, 2016 •

edited

Loading

ability for global variables to be initialized with address of each other #131

ability for global variables to be initialized with address of each other #131

Comments

andrewrk commented Mar 1, 2016 • edited Loading

andrewrk commented Mar 1, 2016 •

edited

Loading