compiler: split Decl into Nav and Cau

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 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 <jacobly0@users.noreply.github.com>
Co-authored-by: Jakub Konka <kubkon@jakubkonka.com>

1 files changed, 71 insertions, 132 deletions

diff --git a/src/codegen.zig b/src/codegen.zig
index 50688151ed..f2fa60fdf8 100644
--- a/src/codegen.zig
+++ b/src/codegen.zig
@@ -17,7 +17,7 @@ const ErrorMsg = Zcu.ErrorMsg;
 const InternPool = @import("InternPool.zig");
 const Liveness = @import("Liveness.zig");
 const Zcu = @import("Zcu.zig");
-const Target = std.Target;
+
 const Type = @import("Type.zig");
 const Value = @import("Value.zig");
 const Zir = std.zig.Zir;
@@ -26,7 +26,7 @@ const dev = @import("dev.zig");
 
 pub const Result = union(enum) {
     /// The `code` parameter passed to `generateSymbol` has the value ok.
-    ok: void,
+    ok,
 
     /// There was a codegen error.
     fail: *ErrorMsg,
@@ -39,7 +39,7 @@ pub const CodeGenError = error{
 };
 
 pub const DebugInfoOutput = union(enum) {
-    dwarf: *link.File.Dwarf.DeclState,
+    dwarf: *link.File.Dwarf.NavState,
     plan9: *link.File.Plan9.DebugInfoOutput,
     none,
 };
@@ -73,9 +73,7 @@ pub fn generateFunction(
 ) CodeGenError!Result {
     const zcu = pt.zcu;
     const func = zcu.funcInfo(func_index);
-    const decl = zcu.declPtr(func.owner_decl);
-    const namespace = zcu.namespacePtr(decl.src_namespace);
-    const target = namespace.fileScope(zcu).mod.resolved_target.result;
+    const target = zcu.navFileScope(func.owner_nav).mod.resolved_target.result;
     switch (target_util.zigBackend(target, false)) {
         else => unreachable,
         inline .stage2_aarch64,
@@ -100,10 +98,8 @@ pub fn generateLazyFunction(
     debug_output: DebugInfoOutput,
 ) CodeGenError!Result {
     const zcu = pt.zcu;
-    const decl_index = lazy_sym.ty.getOwnerDecl(zcu);
-    const decl = zcu.declPtr(decl_index);
-    const namespace = zcu.namespacePtr(decl.src_namespace);
-    const target = namespace.fileScope(zcu).mod.resolved_target.result;
+    const file = Type.fromInterned(lazy_sym.ty).typeDeclInstAllowGeneratedTag(zcu).?.resolveFull(&zcu.intern_pool).file;
+    const target = zcu.fileByIndex(file).mod.resolved_target.result;
     switch (target_util.zigBackend(target, false)) {
         else => unreachable,
         inline .stage2_x86_64,
@@ -115,7 +111,7 @@ pub fn generateLazyFunction(
     }
 }
 
-fn writeFloat(comptime F: type, f: F, target: Target, endian: std.builtin.Endian, code: []u8) void {
+fn writeFloat(comptime F: type, f: F, target: std.Target, endian: std.builtin.Endian, code: []u8) void {
     _ = target;
     const bits = @typeInfo(F).Float.bits;
     const Int = @Type(.{ .Int = .{ .signedness = .unsigned, .bits = bits } });
@@ -147,7 +143,7 @@ pub fn generateLazySymbol(
 
     log.debug("generateLazySymbol: kind = {s}, ty = {}", .{
         @tagName(lazy_sym.kind),
-        lazy_sym.ty.fmt(pt),
+        Type.fromInterned(lazy_sym.ty).fmt(pt),
     });
 
     if (lazy_sym.kind == .code) {
@@ -155,7 +151,7 @@ pub fn generateLazySymbol(
         return generateLazyFunction(bin_file, pt, src_loc, lazy_sym, code, debug_output);
     }
 
-    if (lazy_sym.ty.isAnyError(pt.zcu)) {
+    if (lazy_sym.ty == .anyerror_type) {
         alignment.* = .@"4";
         const err_names = ip.global_error_set.getNamesFromMainThread();
         mem.writeInt(u32, try code.addManyAsArray(4), @intCast(err_names.len), endian);
@@ -171,9 +167,10 @@ pub fn generateLazySymbol(
         }
         mem.writeInt(u32, code.items[offset..][0..4], @intCast(code.items.len), endian);
         return Result.ok;
-    } else if (lazy_sym.ty.zigTypeTag(pt.zcu) == .Enum) {
+    } else if (Type.fromInterned(lazy_sym.ty).zigTypeTag(pt.zcu) == .Enum) {
         alignment.* = .@"1";
-        const tag_names = lazy_sym.ty.enumFields(pt.zcu);
+        const enum_ty = Type.fromInterned(lazy_sym.ty);
+        const tag_names = enum_ty.enumFields(pt.zcu);
         for (0..tag_names.len) |tag_index| {
             const tag_name = tag_names.get(ip)[tag_index].toSlice(ip);
             try code.ensureUnusedCapacity(tag_name.len + 1);
@@ -185,7 +182,7 @@ pub fn generateLazySymbol(
         gpa,
         src_loc,
         "TODO implement generateLazySymbol for {s} {}",
-        .{ @tagName(lazy_sym.kind), lazy_sym.ty.fmt(pt) },
+        .{ @tagName(lazy_sym.kind), Type.fromInterned(lazy_sym.ty).fmt(pt) },
     ) };
 }
 
@@ -251,7 +248,7 @@ pub fn generateSymbol(
             }),
         },
         .variable,
-        .extern_func,
+        .@"extern",
         .func,
         .enum_literal,
         .empty_enum_value,
@@ -651,8 +648,8 @@ fn lowerPtr(
     const ptr = zcu.intern_pool.indexToKey(ptr_val).ptr;
     const offset: u64 = prev_offset + ptr.byte_offset;
     return switch (ptr.base_addr) {
-        .decl => |decl| try lowerDeclRef(bin_file, pt, src_loc, decl, code, debug_output, reloc_info, offset),
-        .anon_decl => |ad| try lowerAnonDeclRef(bin_file, pt, src_loc, ad, code, debug_output, reloc_info, offset),
+        .nav => |nav| try lowerNavRef(bin_file, pt, src_loc, nav, code, debug_output, reloc_info, offset),
+        .uav => |uav| try lowerUavRef(bin_file, pt, src_loc, uav, code, debug_output, reloc_info, offset),
         .int => try generateSymbol(bin_file, pt, src_loc, try pt.intValue(Type.usize, offset), code, debug_output, reloc_info),
         .eu_payload => |eu_ptr| try lowerPtr(
             bin_file,
@@ -705,11 +702,11 @@ const RelocInfo = struct {
     parent_atom_index: u32,
 };
 
-fn lowerAnonDeclRef(
+fn lowerUavRef(
     lf: *link.File,
     pt: Zcu.PerThread,
     src_loc: Zcu.LazySrcLoc,
-    anon_decl: InternPool.Key.Ptr.BaseAddr.AnonDecl,
+    uav: InternPool.Key.Ptr.BaseAddr.Uav,
     code: *std.ArrayList(u8),
     debug_output: DebugInfoOutput,
     reloc_info: RelocInfo,
@@ -720,23 +717,23 @@ fn lowerAnonDeclRef(
     const target = lf.comp.root_mod.resolved_target.result;
 
     const ptr_width_bytes = @divExact(target.ptrBitWidth(), 8);
-    const decl_val = anon_decl.val;
-    const decl_ty = Type.fromInterned(ip.typeOf(decl_val));
-    log.debug("lowerAnonDecl: ty = {}", .{decl_ty.fmt(pt)});
-    const is_fn_body = decl_ty.zigTypeTag(pt.zcu) == .Fn;
-    if (!is_fn_body and !decl_ty.hasRuntimeBits(pt)) {
+    const uav_val = uav.val;
+    const uav_ty = Type.fromInterned(ip.typeOf(uav_val));
+    log.debug("lowerUavRef: ty = {}", .{uav_ty.fmt(pt)});
+    const is_fn_body = uav_ty.zigTypeTag(pt.zcu) == .Fn;
+    if (!is_fn_body and !uav_ty.hasRuntimeBits(pt)) {
         try code.appendNTimes(0xaa, ptr_width_bytes);
         return Result.ok;
     }
 
-    const decl_align = ip.indexToKey(anon_decl.orig_ty).ptr_type.flags.alignment;
-    const res = try lf.lowerAnonDecl(pt, decl_val, decl_align, src_loc);
+    const uav_align = ip.indexToKey(uav.orig_ty).ptr_type.flags.alignment;
+    const res = try lf.lowerUav(pt, uav_val, uav_align, src_loc);
     switch (res) {
-        .ok => {},
+        .mcv => {},
         .fail => |em| return .{ .fail = em },
     }
 
-    const vaddr = try lf.getAnonDeclVAddr(decl_val, .{
+    const vaddr = try lf.getUavVAddr(uav_val, .{
         .parent_atom_index = reloc_info.parent_atom_index,
         .offset = code.items.len,
         .addend = @intCast(offset),
@@ -752,11 +749,11 @@ fn lowerAnonDeclRef(
     return Result.ok;
 }
 
-fn lowerDeclRef(
+fn lowerNavRef(
     lf: *link.File,
     pt: Zcu.PerThread,
     src_loc: Zcu.LazySrcLoc,
-    decl_index: InternPool.DeclIndex,
+    nav_index: InternPool.Nav.Index,
     code: *std.ArrayList(u8),
     debug_output: DebugInfoOutput,
     reloc_info: RelocInfo,
@@ -765,18 +762,18 @@ fn lowerDeclRef(
     _ = src_loc;
     _ = debug_output;
     const zcu = pt.zcu;
-    const decl = zcu.declPtr(decl_index);
-    const namespace = zcu.namespacePtr(decl.src_namespace);
-    const target = namespace.fileScope(zcu).mod.resolved_target.result;
+    const ip = &zcu.intern_pool;
+    const target = zcu.navFileScope(nav_index).mod.resolved_target.result;
 
     const ptr_width = target.ptrBitWidth();
-    const is_fn_body = decl.typeOf(zcu).zigTypeTag(zcu) == .Fn;
-    if (!is_fn_body and !decl.typeOf(zcu).hasRuntimeBits(pt)) {
+    const nav_ty = Type.fromInterned(ip.getNav(nav_index).typeOf(ip));
+    const is_fn_body = nav_ty.zigTypeTag(zcu) == .Fn;
+    if (!is_fn_body and !nav_ty.hasRuntimeBits(pt)) {
         try code.appendNTimes(0xaa, @divExact(ptr_width, 8));
         return Result.ok;
     }
 
-    const vaddr = try lf.getDeclVAddr(pt, decl_index, .{
+    const vaddr = try lf.getNavVAddr(pt, nav_index, .{
         .parent_atom_index = reloc_info.parent_atom_index,
         .offset = code.items.len,
         .addend = @intCast(offset),
@@ -848,34 +845,21 @@ pub const GenResult = union(enum) {
     }
 };
 
-fn genDeclRef(
+fn genNavRef(
     lf: *link.File,
     pt: Zcu.PerThread,
     src_loc: Zcu.LazySrcLoc,
     val: Value,
-    ptr_decl_index: InternPool.DeclIndex,
+    ref_nav_index: InternPool.Nav.Index,
+    target: std.Target,
 ) CodeGenError!GenResult {
     const zcu = pt.zcu;
     const ip = &zcu.intern_pool;
     const ty = val.typeOf(zcu);
-    log.debug("genDeclRef: val = {}", .{val.fmtValue(pt)});
-
-    const ptr_decl = zcu.declPtr(ptr_decl_index);
-    const namespace = zcu.namespacePtr(ptr_decl.src_namespace);
-    const target = namespace.fileScope(zcu).mod.resolved_target.result;
-
-    const ptr_bits = target.ptrBitWidth();
-    const ptr_bytes: u64 = @divExact(ptr_bits, 8);
-
-    const decl_index = switch (ip.indexToKey(ptr_decl.val.toIntern())) {
-        .func => |func| func.owner_decl,
-        .extern_func => |extern_func| extern_func.decl,
-        else => ptr_decl_index,
-    };
-    const decl = zcu.declPtr(decl_index);
+    log.debug("genNavRef: val = {}", .{val.fmtValue(pt)});
 
-    if (!decl.typeOf(zcu).isFnOrHasRuntimeBitsIgnoreComptime(pt)) {
-        const imm: u64 = switch (ptr_bytes) {
+    if (!ty.isFnOrHasRuntimeBitsIgnoreComptime(pt)) {
+        const imm: u64 = switch (@divExact(target.ptrBitWidth(), 8)) {
             1 => 0xaa,
             2 => 0xaaaa,
             4 => 0xaaaaaaaa,
@@ -900,96 +884,56 @@ fn genDeclRef(
         }
     }
 
-    const decl_namespace = zcu.namespacePtr(decl.src_namespace);
-    const single_threaded = decl_namespace.fileScope(zcu).mod.single_threaded;
-    const is_threadlocal = val.isPtrToThreadLocal(zcu) and !single_threaded;
-    const is_extern = decl.isExtern(zcu);
-
-    if (lf.cast(link.File.Elf)) |elf_file| {
+    const nav_index, const is_extern, const lib_name, const is_threadlocal = switch (ip.indexToKey(zcu.navValue(ref_nav_index).toIntern())) {
+        .func => |func| .{ func.owner_nav, false, .none, false },
+        .variable => |variable| .{ variable.owner_nav, false, variable.lib_name, variable.is_threadlocal },
+        .@"extern" => |@"extern"| .{ @"extern".owner_nav, true, @"extern".lib_name, @"extern".is_threadlocal },
+        else => .{ ref_nav_index, false, .none, false },
+    };
+    const single_threaded = zcu.navFileScope(nav_index).mod.single_threaded;
+    const name = ip.getNav(nav_index).name;
+    if (lf.cast(.elf)) |elf_file| {
         const zo = elf_file.zigObjectPtr().?;
         if (is_extern) {
-            const name = decl.name.toSlice(ip);
             // TODO audit this
-            const lib_name = if (decl.getOwnedVariable(zcu)) |ov| ov.lib_name.toSlice(ip) else null;
-            const sym_index = try elf_file.getGlobalSymbol(name, lib_name);
+            const sym_index = try elf_file.getGlobalSymbol(name.toSlice(ip), lib_name.toSlice(ip));
             zo.symbol(sym_index).flags.needs_got = true;
             return GenResult.mcv(.{ .load_symbol = sym_index });
         }
-        const sym_index = try zo.getOrCreateMetadataForDecl(elf_file, decl_index);
-        if (is_threadlocal) {
+        const sym_index = try zo.getOrCreateMetadataForNav(elf_file, nav_index);
+        if (!single_threaded and is_threadlocal) {
             return GenResult.mcv(.{ .load_tlv = sym_index });
         }
         return GenResult.mcv(.{ .load_symbol = sym_index });
-    } else if (lf.cast(link.File.MachO)) |macho_file| {
+    } else if (lf.cast(.macho)) |macho_file| {
         const zo = macho_file.getZigObject().?;
         if (is_extern) {
-            const name = decl.name.toSlice(ip);
-            const lib_name = if (decl.getOwnedVariable(zcu)) |ov| ov.lib_name.toSlice(ip) else null;
-            const sym_index = try macho_file.getGlobalSymbol(name, lib_name);
+            const sym_index = try macho_file.getGlobalSymbol(name.toSlice(ip), lib_name.toSlice(ip));
             zo.symbols.items[sym_index].setSectionFlags(.{ .needs_got = true });
             return GenResult.mcv(.{ .load_symbol = sym_index });
         }
-        const sym_index = try zo.getOrCreateMetadataForDecl(macho_file, decl_index);
+        const sym_index = try zo.getOrCreateMetadataForNav(macho_file, nav_index);
         const sym = zo.symbols.items[sym_index];
-        if (is_threadlocal) {
+        if (!single_threaded and is_threadlocal) {
             return GenResult.mcv(.{ .load_tlv = sym.nlist_idx });
         }
         return GenResult.mcv(.{ .load_symbol = sym.nlist_idx });
-    } else if (lf.cast(link.File.Coff)) |coff_file| {
+    } else if (lf.cast(.coff)) |coff_file| {
         if (is_extern) {
-            const name = decl.name.toSlice(ip);
             // TODO audit this
-            const lib_name = if (decl.getOwnedVariable(zcu)) |ov| ov.lib_name.toSlice(ip) else null;
-            const global_index = try coff_file.getGlobalSymbol(name, lib_name);
+            const global_index = try coff_file.getGlobalSymbol(name.toSlice(ip), lib_name.toSlice(ip));
             try coff_file.need_got_table.put(gpa, global_index, {}); // needs GOT
             return GenResult.mcv(.{ .load_got = link.File.Coff.global_symbol_bit | global_index });
         }
-        const atom_index = try coff_file.getOrCreateAtomForDecl(decl_index);
+        const atom_index = try coff_file.getOrCreateAtomForNav(nav_index);
         const sym_index = coff_file.getAtom(atom_index).getSymbolIndex().?;
         return GenResult.mcv(.{ .load_got = sym_index });
-    } else if (lf.cast(link.File.Plan9)) |p9| {
-        const atom_index = try p9.seeDecl(decl_index);
+    } else if (lf.cast(.plan9)) |p9| {
+        const atom_index = try p9.seeNav(pt, nav_index);
         const atom = p9.getAtom(atom_index);
         return GenResult.mcv(.{ .memory = atom.getOffsetTableAddress(p9) });
     } else {
-        return GenResult.fail(gpa, src_loc, "TODO genDeclRef for target {}", .{target});
-    }
-}
-
-fn genUnnamedConst(
-    lf: *link.File,
-    pt: Zcu.PerThread,
-    src_loc: Zcu.LazySrcLoc,
-    val: Value,
-    owner_decl_index: InternPool.DeclIndex,
-) CodeGenError!GenResult {
-    const gpa = lf.comp.gpa;
-    log.debug("genUnnamedConst: val = {}", .{val.fmtValue(pt)});
-
-    const local_sym_index = lf.lowerUnnamedConst(pt, val, owner_decl_index) catch |err| {
-        return GenResult.fail(gpa, src_loc, "lowering unnamed constant failed: {s}", .{@errorName(err)});
-    };
-    switch (lf.tag) {
-        .elf => {
-            return GenResult.mcv(.{ .load_symbol = local_sym_index });
-        },
-        .macho => {
-            const macho_file = lf.cast(link.File.MachO).?;
-            const local = macho_file.getZigObject().?.symbols.items[local_sym_index];
-            return GenResult.mcv(.{ .load_symbol = local.nlist_idx });
-        },
-        .coff => {
-            return GenResult.mcv(.{ .load_direct = local_sym_index });
-        },
-        .plan9 => {
-            const atom_index = local_sym_index; // plan9 returns the atom_index
-            return GenResult.mcv(.{ .load_direct = atom_index });
-        },
-
-        .c => return GenResult.fail(gpa, src_loc, "TODO genUnnamedConst for -ofmt=c", .{}),
-        .wasm => return GenResult.fail(gpa, src_loc, "TODO genUnnamedConst for wasm", .{}),
-        .spirv => return GenResult.fail(gpa, src_loc, "TODO genUnnamedConst for spirv", .{}),
-        .nvptx => return GenResult.fail(gpa, src_loc, "TODO genUnnamedConst for nvptx", .{}),
+        return GenResult.fail(gpa, src_loc, "TODO genNavRef for target {}", .{target});
     }
 }
 
@@ -998,7 +942,7 @@ pub fn genTypedValue(
     pt: Zcu.PerThread,
     src_loc: Zcu.LazySrcLoc,
     val: Value,
-    owner_decl_index: InternPool.DeclIndex,
+    target: std.Target,
 ) CodeGenError!GenResult {
     const zcu = pt.zcu;
     const ip = &zcu.intern_pool;
@@ -1010,14 +954,9 @@ pub fn genTypedValue(
         return GenResult.mcv(.undef);
     }
 
-    const owner_decl = zcu.declPtr(owner_decl_index);
-    const namespace = zcu.namespacePtr(owner_decl.src_namespace);
-    const target = namespace.fileScope(zcu).mod.resolved_target.result;
-    const ptr_bits = target.ptrBitWidth();
-
     if (!ty.isSlice(zcu)) switch (ip.indexToKey(val.toIntern())) {
         .ptr => |ptr| if (ptr.byte_offset == 0) switch (ptr.base_addr) {
-            .decl => |decl| return genDeclRef(lf, pt, src_loc, val, decl),
+            .nav => |nav| return genNavRef(lf, pt, src_loc, val, nav, target),
             else => {},
         },
         else => {},
@@ -1042,7 +981,7 @@ pub fn genTypedValue(
         },
         .Int => {
             const info = ty.intInfo(zcu);
-            if (info.bits <= ptr_bits) {
+            if (info.bits <= target.ptrBitWidth()) {
                 const unsigned: u64 = switch (info.signedness) {
                     .signed => @bitCast(val.toSignedInt(pt)),
                     .unsigned => val.toUnsignedInt(pt),
@@ -1060,7 +999,7 @@ pub fn genTypedValue(
                     pt,
                     src_loc,
                     val.optionalValue(zcu) orelse return GenResult.mcv(.{ .immediate = 0 }),
-                    owner_decl_index,
+                    target,
                 );
             } else if (ty.abiSize(pt) == 1) {
                 return GenResult.mcv(.{ .immediate = @intFromBool(!val.isNull(zcu)) });
@@ -1073,7 +1012,7 @@ pub fn genTypedValue(
                 pt,
                 src_loc,
                 Value.fromInterned(enum_tag.int),
-                owner_decl_index,
+                target,
             );
         },
         .ErrorSet => {
@@ -1096,14 +1035,14 @@ pub fn genTypedValue(
                             .ty = err_type.toIntern(),
                             .name = err_name,
                         } })),
-                        owner_decl_index,
+                        target,
                     ),
                     .payload => return genTypedValue(
                         lf,
                         pt,
                         src_loc,
                         try pt.intValue(err_int_ty, 0),
-                        owner_decl_index,
+                        target,
                     ),
                 }
             }
@@ -1121,7 +1060,7 @@ pub fn genTypedValue(
         else => {},
     }
 
-    return genUnnamedConst(lf, pt, src_loc, val, owner_decl_index);
+    return lf.lowerUav(pt, val.toIntern(), .none, src_loc);
 }
 
 pub fn errUnionPayloadOffset(payload_ty: Type, pt: Zcu.PerThread) u64 {