stage2: improve handling of 0-bit types and arrays

 * Make `alloc` AIR instructions call `resolveTypeLayout`.
 * `Sema.zirResolveInferredAlloc` now calls `requireRuntimeBlock` in the
   case that it operates on a non-comptime instruction.
 * `Type.abiSize` and `Type.abiAlignment` now return 0 for `void`
 * Sema: implement `resolveTypeFields` for unions.
 * LLVM Backend: support `ptr_elem_ptr` when the element type is 0-bit.
 * Type: improve `abiAlignment` implementation for structs to properly
   handle fields with non-default alignment.
 * Value: implement hashing array, vector, and structs.

4 files changed, 165 insertions, 87 deletions

diff --git a/src/Sema.zig b/src/Sema.zig
index d0c4bbec75..9353bb3dbf 100644
--- a/src/Sema.zig
+++ b/src/Sema.zig
@@ -2035,6 +2035,7 @@ fn zirAllocExtended(
         .@"addrspace" = target_util.defaultAddressSpace(sema.mod.getTarget(), .local),
     });
     try sema.requireRuntimeBlock(block, src);
+    try sema.resolveTypeLayout(block, src, var_ty);
     return block.addTy(.alloc, ptr_type);
 }
 
@@ -2044,8 +2045,8 @@ fn zirAllocComptime(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileErr
 
     const inst_data = sema.code.instructions.items(.data)[inst].un_node;
     const ty_src: LazySrcLoc = .{ .node_offset_var_decl_ty = inst_data.src_node };
-    const var_type = try sema.resolveType(block, ty_src, inst_data.operand);
-    return sema.analyzeComptimeAlloc(block, var_type);
+    const var_ty = try sema.resolveType(block, ty_src, inst_data.operand);
+    return sema.analyzeComptimeAlloc(block, var_ty);
 }
 
 fn zirAllocInferredComptime(sema: *Sema, inst: Zir.Inst.Index) CompileError!Air.Inst.Ref {
@@ -2065,15 +2066,16 @@ fn zirAlloc(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Air.I
     const inst_data = sema.code.instructions.items(.data)[inst].un_node;
     const ty_src: LazySrcLoc = .{ .node_offset_var_decl_ty = inst_data.src_node };
     const var_decl_src = inst_data.src();
-    const var_type = try sema.resolveType(block, ty_src, inst_data.operand);
+    const var_ty = try sema.resolveType(block, ty_src, inst_data.operand);
     if (block.is_comptime) {
-        return sema.analyzeComptimeAlloc(block, var_type);
+        return sema.analyzeComptimeAlloc(block, var_ty);
     }
     const ptr_type = try Type.ptr(sema.arena, .{
-        .pointee_type = var_type,
+        .pointee_type = var_ty,
         .@"addrspace" = target_util.defaultAddressSpace(sema.mod.getTarget(), .local),
     });
     try sema.requireRuntimeBlock(block, var_decl_src);
+    try sema.resolveTypeLayout(block, ty_src, var_ty);
     return block.addTy(.alloc, ptr_type);
 }
 
@@ -2084,16 +2086,17 @@ fn zirAllocMut(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Ai
     const inst_data = sema.code.instructions.items(.data)[inst].un_node;
     const var_decl_src = inst_data.src();
     const ty_src: LazySrcLoc = .{ .node_offset_var_decl_ty = inst_data.src_node };
-    const var_type = try sema.resolveType(block, ty_src, inst_data.operand);
+    const var_ty = try sema.resolveType(block, ty_src, inst_data.operand);
     if (block.is_comptime) {
-        return sema.analyzeComptimeAlloc(block, var_type);
+        return sema.analyzeComptimeAlloc(block, var_ty);
     }
-    try sema.validateVarType(block, ty_src, var_type, false);
+    try sema.validateVarType(block, ty_src, var_ty, false);
     const ptr_type = try Type.ptr(sema.arena, .{
-        .pointee_type = var_type,
+        .pointee_type = var_ty,
         .@"addrspace" = target_util.defaultAddressSpace(sema.mod.getTarget(), .local),
     });
     try sema.requireRuntimeBlock(block, var_decl_src);
+    try sema.resolveTypeLayout(block, ty_src, var_ty);
     return block.addTy(.alloc, ptr_type);
 }
 
@@ -2135,6 +2138,7 @@ fn zirResolveInferredAlloc(sema: *Sema, block: *Block, inst: Zir.Inst.Index) Com
     defer tracy.end();
 
     const inst_data = sema.code.instructions.items(.data)[inst].un_node;
+    const src = inst_data.src();
     const ty_src: LazySrcLoc = .{ .node_offset_var_decl_ty = inst_data.src_node };
     const ptr = sema.resolveInst(inst_data.operand);
     const ptr_inst = Air.refToIndex(ptr).?;
@@ -2146,46 +2150,53 @@ fn zirResolveInferredAlloc(sema: *Sema, block: *Block, inst: Zir.Inst.Index) Com
         .inferred_alloc_mut => true,
         else => unreachable,
     };
+    const target = sema.mod.getTarget();
 
-    if (ptr_val.castTag(.inferred_alloc_comptime)) |iac| {
-        const decl = iac.data;
-        try sema.mod.declareDeclDependency(sema.owner_decl, decl);
+    switch (ptr_val.tag()) {
+        .inferred_alloc_comptime => {
+            const iac = ptr_val.castTag(.inferred_alloc_comptime).?;
+            const decl = iac.data;
+            try sema.mod.declareDeclDependency(sema.owner_decl, decl);
+
+            const final_elem_ty = try decl.ty.copy(sema.arena);
+            const final_ptr_ty = try Type.ptr(sema.arena, .{
+                .pointee_type = final_elem_ty,
+                .@"addrspace" = target_util.defaultAddressSpace(target, .local),
+            });
+            const final_ptr_ty_inst = try sema.addType(final_ptr_ty);
+            sema.air_instructions.items(.data)[ptr_inst].ty_pl.ty = final_ptr_ty_inst;
 
-        const final_elem_ty = try decl.ty.copy(sema.arena);
-        const final_ptr_ty = try Type.ptr(sema.arena, .{
-            .pointee_type = final_elem_ty,
-            .@"addrspace" = target_util.defaultAddressSpace(sema.mod.getTarget(), .local),
-        });
-        const final_ptr_ty_inst = try sema.addType(final_ptr_ty);
-        sema.air_instructions.items(.data)[ptr_inst].ty_pl.ty = final_ptr_ty_inst;
+            if (var_is_mut) {
+                sema.air_values.items[value_index] = try Value.Tag.decl_ref_mut.create(sema.arena, .{
+                    .decl = decl,
+                    .runtime_index = block.runtime_index,
+                });
+            } else {
+                sema.air_values.items[value_index] = try Value.Tag.decl_ref.create(sema.arena, decl);
+            }
+        },
+        .inferred_alloc => {
+            const inferred_alloc = ptr_val.castTag(.inferred_alloc).?;
+            const peer_inst_list = inferred_alloc.data.stored_inst_list.items;
+            const final_elem_ty = try sema.resolvePeerTypes(block, ty_src, peer_inst_list, .none);
 
-        if (var_is_mut) {
-            sema.air_values.items[value_index] = try Value.Tag.decl_ref_mut.create(sema.arena, .{
-                .decl = decl,
-                .runtime_index = block.runtime_index,
-            });
-        } else {
-            sema.air_values.items[value_index] = try Value.Tag.decl_ref.create(sema.arena, decl);
-        }
-        return;
-    }
+            try sema.requireRuntimeBlock(block, src);
+            try sema.resolveTypeLayout(block, ty_src, final_elem_ty);
 
-    if (ptr_val.castTag(.inferred_alloc)) |inferred_alloc| {
-        const peer_inst_list = inferred_alloc.data.stored_inst_list.items;
-        const final_elem_ty = try sema.resolvePeerTypes(block, ty_src, peer_inst_list, .none);
-        if (var_is_mut) {
-            try sema.validateVarType(block, ty_src, final_elem_ty, false);
-        }
-        // Change it to a normal alloc.
-        const final_ptr_ty = try Type.ptr(sema.arena, .{
-            .pointee_type = final_elem_ty,
-            .@"addrspace" = target_util.defaultAddressSpace(sema.mod.getTarget(), .local),
-        });
-        sema.air_instructions.set(ptr_inst, .{
-            .tag = .alloc,
-            .data = .{ .ty = final_ptr_ty },
-        });
-        return;
+            if (var_is_mut) {
+                try sema.validateVarType(block, ty_src, final_elem_ty, false);
+            }
+            // Change it to a normal alloc.
+            const final_ptr_ty = try Type.ptr(sema.arena, .{
+                .pointee_type = final_elem_ty,
+                .@"addrspace" = target_util.defaultAddressSpace(target, .local),
+            });
+            sema.air_instructions.set(ptr_inst, .{
+                .tag = .alloc,
+                .data = .{ .ty = final_ptr_ty },
+            });
+        },
+        else => unreachable,
     }
 }
 
@@ -8844,6 +8855,7 @@ fn zirArrayInit(
     };
 
     try sema.requireRuntimeBlock(block, runtime_src);
+    try sema.resolveTypeLayout(block, src, elem_ty);
 
     const alloc_ty = try Type.ptr(sema.arena, .{
         .pointee_type = array_ty,
@@ -10194,6 +10206,7 @@ fn validateVarType(
         .Enum,
         .Frame,
         .AnyFrame,
+        .Void,
         => return,
 
         .BoundFn,
@@ -10202,7 +10215,6 @@ fn validateVarType(
         .EnumLiteral,
         .NoReturn,
         .Type,
-        .Void,
         .Undefined,
         .Null,
         => break,
@@ -12585,6 +12597,22 @@ pub fn resolveTypeLayout(
             }
             struct_obj.status = .have_layout;
         },
+        .Union => {
+            const resolved_ty = try sema.resolveTypeFields(block, src, ty);
+            const union_obj = resolved_ty.cast(Type.Payload.Union).?.data;
+            switch (union_obj.status) {
+                .none, .have_field_types => {},
+                .field_types_wip, .layout_wip => {
+                    return sema.fail(block, src, "union {} depends on itself", .{ty});
+                },
+                .have_layout => return,
+            }
+            union_obj.status = .layout_wip;
+            for (union_obj.fields.values()) |field| {
+                try sema.resolveTypeLayout(block, src, field.ty);
+            }
+            union_obj.status = .have_layout;
+        },
         else => {},
     }
 }
diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig
index d7dbeade15..d4ee13c32d 100644
--- a/src/codegen/llvm.zig
+++ b/src/codegen/llvm.zig
@@ -1863,14 +1863,16 @@ pub const FuncGen = struct {
     }
 
     fn airPtrElemPtr(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value {
-        if (self.liveness.isUnused(inst))
-            return null;
+        if (self.liveness.isUnused(inst)) return null;
 
         const ty_pl = self.air.instructions.items(.data)[inst].ty_pl;
         const bin_op = self.air.extraData(Air.Bin, ty_pl.payload).data;
+        const lhs_ty = self.air.typeOf(bin_op.lhs);
+        if (!lhs_ty.hasCodeGenBits()) return null;
+
         const base_ptr = try self.resolveInst(bin_op.lhs);
         const rhs = try self.resolveInst(bin_op.rhs);
-        if (self.air.typeOf(bin_op.lhs).isSinglePointer()) {
+        if (lhs_ty.isSinglePointer()) {
             // If this is a single-item pointer to an array, we need another index in the GEP.
             const indices: [2]*const llvm.Value = .{ self.context.intType(32).constNull(), rhs };
             return self.builder.buildInBoundsGEP(base_ptr, &indices, indices.len, "");
diff --git a/src/type.zig b/src/type.zig
index 055b32a048..dbab79820c 100644
--- a/src/type.zig
+++ b/src/type.zig
@@ -1579,7 +1579,7 @@ pub const Type = extern union {
         };
     }
 
-    /// Asserts that hasCodeGenBits() is true.
+    /// Returns 0 for 0-bit types.
     pub fn abiAlignment(self: Type, target: Target) u32 {
         return switch (self.tag()) {
             .u1,
@@ -1667,6 +1667,7 @@ pub const Type = extern union {
 
             .int_signed, .int_unsigned => {
                 const bits: u16 = self.cast(Payload.Bits).?.data;
+                if (bits == 0) return 0;
                 if (bits <= 8) return 1;
                 if (bits <= 16) return 2;
                 if (bits <= 32) return 4;
@@ -1699,23 +1700,27 @@ pub const Type = extern union {
             },
 
             .@"struct" => {
-                // TODO take into account field alignment
-                // also make this possible to fail, and lazy
-                // I think we need to move all the functions from type.zig which can
-                // fail into Sema.
-                // Probably will need to introduce multi-stage struct resolution just
-                // like we have in stage1.
-                const struct_obj = self.castTag(.@"struct").?.data;
-                var biggest: u32 = 0;
-                for (struct_obj.fields.values()) |field| {
+                const fields = self.structFields();
+                if (self.castTag(.@"struct")) |payload| {
+                    const struct_obj = payload.data;
+                    assert(struct_obj.status == .have_layout);
+                    const is_packed = struct_obj.layout == .Packed;
+                    if (is_packed) @panic("TODO packed structs");
+                }
+                var big_align: u32 = 0;
+                for (fields.values()) |field| {
                     if (!field.ty.hasCodeGenBits()) continue;
-                    const field_align = field.ty.abiAlignment(target);
-                    if (field_align > biggest) {
-                        return field_align;
-                    }
+
+                    const field_align = a: {
+                        if (field.abi_align.tag() == .abi_align_default) {
+                            break :a field.ty.abiAlignment(target);
+                        } else {
+                            break :a @intCast(u32, field.abi_align.toUnsignedInt());
+                        }
+                    };
+                    big_align = @maximum(big_align, field_align);
                 }
-                assert(biggest != 0);
-                return biggest;
+                return big_align;
             },
             .enum_full, .enum_nonexhaustive, .enum_simple, .enum_numbered => {
                 var buffer: Payload.Bits = undefined;
@@ -1726,8 +1731,12 @@ pub const Type = extern union {
             .@"union" => return self.castTag(.@"union").?.data.abiAlignment(target, false),
             .union_tagged => return self.castTag(.union_tagged).?.data.abiAlignment(target, true),
 
-            .c_void,
+            .empty_struct,
             .void,
+            => return 0,
+
+            .empty_struct_literal,
+            .c_void,
             .type,
             .comptime_int,
             .comptime_float,
@@ -1735,8 +1744,6 @@ pub const Type = extern union {
             .@"null",
             .@"undefined",
             .enum_literal,
-            .empty_struct,
-            .empty_struct_literal,
             .inferred_alloc_const,
             .inferred_alloc_mut,
             .@"opaque",
@@ -1758,7 +1765,6 @@ pub const Type = extern union {
             .fn_ccc_void_no_args => unreachable, // represents machine code; not a pointer
             .function => unreachable, // represents machine code; not a pointer
             .c_void => unreachable,
-            .void => unreachable,
             .type => unreachable,
             .comptime_int => unreachable,
             .comptime_float => unreachable,
@@ -1767,7 +1773,6 @@ pub const Type = extern union {
             .@"undefined" => unreachable,
             .enum_literal => unreachable,
             .single_const_pointer_to_comptime_int => unreachable,
-            .empty_struct => unreachable,
             .empty_struct_literal => unreachable,
             .inferred_alloc_const => unreachable,
             .inferred_alloc_mut => unreachable,
@@ -1777,14 +1782,19 @@ pub const Type = extern union {
             .type_info => unreachable,
             .bound_fn => unreachable,
 
+            .empty_struct, .void => 0,
+
             .@"struct" => {
-                const s = self.castTag(.@"struct").?.data;
-                assert(s.status == .have_layout);
-                const is_packed = s.layout == .Packed;
-                if (is_packed) @panic("TODO packed structs");
+                const fields = self.structFields();
+                if (self.castTag(.@"struct")) |payload| {
+                    const struct_obj = payload.data;
+                    assert(struct_obj.status == .have_layout);
+                    const is_packed = struct_obj.layout == .Packed;
+                    if (is_packed) @panic("TODO packed structs");
+                }
                 var size: u64 = 0;
                 var big_align: u32 = 0;
-                for (s.fields.values()) |field| {
+                for (fields.values()) |field| {
                     if (!field.ty.hasCodeGenBits()) continue;
 
                     const field_align = a: {
@@ -1829,7 +1839,7 @@ pub const Type = extern union {
             .array_u8_sentinel_0 => self.castTag(.array_u8_sentinel_0).?.data + 1,
             .array, .vector => {
                 const payload = self.cast(Payload.Array).?.data;
-                const elem_size = std.math.max(payload.elem_type.abiAlignment(target), payload.elem_type.abiSize(target));
+                const elem_size = @maximum(payload.elem_type.abiAlignment(target), payload.elem_type.abiSize(target));
                 return payload.len * elem_size;
             },
             .array_sentinel => {
@@ -3331,6 +3341,7 @@ pub const Type = extern union {
 
     pub fn structFields(ty: Type) Module.Struct.Fields {
         switch (ty.tag()) {
+            .empty_struct => return .{},
             .@"struct" => {
                 const struct_obj = ty.castTag(.@"struct").?.data;
                 return struct_obj.fields;
@@ -3345,6 +3356,7 @@ pub const Type = extern union {
                 const struct_obj = ty.castTag(.@"struct").?.data;
                 return struct_obj.fields.count();
             },
+            .empty_struct => return 0,
             else => unreachable,
         }
     }
diff --git a/src/value.zig b/src/value.zig
index 7996fcd976..f5477baf21 100644
--- a/src/value.zig
+++ b/src/value.zig
@@ -1399,6 +1399,7 @@ pub const Value = extern union {
 
         switch (zig_ty_tag) {
             .BoundFn => unreachable, // TODO remove this from the language
+            .Opaque => unreachable, // Cannot hash opaque types
 
             .Void,
             .NoReturn,
@@ -1451,10 +1452,22 @@ pub const Value = extern union {
                 else => unreachable,
             },
             .Array, .Vector => {
-                @panic("TODO implement hashing array/vector values");
+                const len = ty.arrayLen();
+                const elem_ty = ty.childType();
+                var index: usize = 0;
+                var elem_value_buf: ElemValueBuffer = undefined;
+                while (index < len) : (index += 1) {
+                    const elem_val = val.elemValueBuffer(index, &elem_value_buf);
+                    elem_val.hash(elem_ty, hasher);
+                }
             },
             .Struct => {
-                @panic("TODO implement hashing struct values");
+                const fields = ty.structFields().values();
+                if (fields.len == 0) return;
+                const field_values = val.castTag(.@"struct").?.data;
+                for (field_values) |field_val, i| {
+                    field_val.hash(fields[i].ty, hasher);
+                }
             },
             .Optional => {
                 if (val.castTag(.opt_payload)) |payload| {
@@ -1486,7 +1499,7 @@ pub const Value = extern union {
                 }
             },
             .Union => {
-                const union_obj = val.castTag(.@"union").?.data;
+                const union_obj = val.cast(Payload.Union).?.data;
                 if (ty.unionTagType()) |tag_ty| {
                     union_obj.tag.hash(tag_ty, hasher);
                 }
@@ -1496,9 +1509,6 @@ pub const Value = extern union {
             .Fn => {
                 @panic("TODO implement hashing function values");
             },
-            .Opaque => {
-                @panic("TODO implement hashing opaque values");
-            },
             .Frame => {
                 @panic("TODO implement hashing frame values");
             },
@@ -1633,7 +1643,22 @@ pub const Value = extern union {
 
     /// Asserts the value is a single-item pointer to an array, or an array,
     /// or an unknown-length pointer, and returns the element value at the index.
-    pub fn elemValue(val: Value, arena: *Allocator, index: usize) error{OutOfMemory}!Value {
+    pub fn elemValue(val: Value, arena: *Allocator, index: usize) !Value {
+        return elemValueAdvanced(val, index, arena, undefined);
+    }
+
+    pub const ElemValueBuffer = Payload.U64;
+
+    pub fn elemValueBuffer(val: Value, index: usize, buffer: *ElemValueBuffer) Value {
+        return elemValueAdvanced(val, index, null, buffer) catch unreachable;
+    }
+
+    pub fn elemValueAdvanced(
+        val: Value,
+        index: usize,
+        arena: ?*Allocator,
+        buffer: *ElemValueBuffer,
+    ) error{OutOfMemory}!Value {
         switch (val.tag()) {
             .empty_array => unreachable, // out of bounds array index
             .empty_struct_value => unreachable, // out of bounds array index
@@ -1643,16 +1668,27 @@ pub const Value = extern union {
                 return val.castTag(.empty_array_sentinel).?.data;
             },
 
-            .bytes => return Tag.int_u64.create(arena, val.castTag(.bytes).?.data[index]),
+            .bytes => {
+                const byte = val.castTag(.bytes).?.data[index];
+                if (arena) |a| {
+                    return Tag.int_u64.create(a, byte);
+                } else {
+                    buffer.* = .{
+                        .base = .{ .tag = .int_u64 },
+                        .data = byte,
+                    };
+                    return initPayload(&buffer.base);
+                }
+            },
 
             // No matter the index; all the elements are the same!
             .repeated => return val.castTag(.repeated).?.data,
 
             .array => return val.castTag(.array).?.data[index],
-            .slice => return val.castTag(.slice).?.data.ptr.elemValue(arena, index),
+            .slice => return val.castTag(.slice).?.data.ptr.elemValueAdvanced(index, arena, buffer),
 
-            .decl_ref => return val.castTag(.decl_ref).?.data.val.elemValue(arena, index),
-            .decl_ref_mut => return val.castTag(.decl_ref_mut).?.data.decl.val.elemValue(arena, index),
+            .decl_ref => return val.castTag(.decl_ref).?.data.val.elemValueAdvanced(index, arena, buffer),
+            .decl_ref_mut => return val.castTag(.decl_ref_mut).?.data.decl.val.elemValueAdvanced(index, arena, buffer),
 
             else => unreachable,
         }