Commit e9e3a29946
Changed files (10)
src/Module.zig
@@ -61,6 +61,11 @@ export_owners: std.AutoArrayHashMapUnmanaged(*Decl, []*Export) = .{},
/// Keys are fully resolved file paths. This table owns the keys and values.
import_table: std.StringArrayHashMapUnmanaged(*Scope.File) = .{},
+/// The set of all the generic function instantiations. This is used so that when a generic
+/// function is called twice with the same comptime parameter arguments, both calls dispatch
+/// to the same function.
+monomorphed_funcs: MonomorphedFuncsSet = .{},
+
/// We optimize memory usage for a compilation with no compile errors by storing the
/// error messages and mapping outside of `Decl`.
/// The ErrorMsg memory is owned by the decl, using Module's general purpose allocator.
@@ -114,6 +119,44 @@ emit_h: ?*GlobalEmitH,
test_functions: std.AutoArrayHashMapUnmanaged(*Decl, void) = .{},
+const MonomorphedFuncsSet = std.HashMapUnmanaged(
+ *Fn,
+ void,
+ MonomorphedFuncsContext,
+ std.hash_map.default_max_load_percentage,
+);
+
+const MonomorphedFuncsContext = struct {
+ pub fn eql(ctx: @This(), a: *Fn, b: *Fn) bool {
+ _ = ctx;
+ return a == b;
+ }
+
+ /// Must match `Sema.GenericCallAdapter.hash`.
+ pub fn hash(ctx: @This(), key: *Fn) u64 {
+ _ = ctx;
+ var hasher = std.hash.Wyhash.init(0);
+
+ // The generic function Decl is guaranteed to be the first dependency
+ // of each of its instantiations.
+ const generic_owner_decl = key.owner_decl.dependencies.keys()[0];
+ const generic_func = generic_owner_decl.val.castTag(.function).?.data;
+ std.hash.autoHash(&hasher, @ptrToInt(generic_func));
+
+ // This logic must be kept in sync with the logic in `analyzeCall` that
+ // computes the hash.
+ const comptime_args = key.comptime_args.?;
+ const generic_ty_info = generic_owner_decl.ty.fnInfo();
+ for (generic_ty_info.param_types) |param_ty, i| {
+ if (generic_ty_info.paramIsComptime(i) and param_ty.tag() != .generic_poison) {
+ comptime_args[i].val.hash(param_ty, &hasher);
+ }
+ }
+
+ return hasher.final();
+ }
+};
+
/// A `Module` has zero or one of these depending on whether `-femit-h` is enabled.
pub const GlobalEmitH = struct {
/// Where to put the output.
@@ -2205,6 +2248,7 @@ pub fn deinit(mod: *Module) void {
mod.error_name_list.deinit(gpa);
mod.test_functions.deinit(gpa);
+ mod.monomorphed_funcs.deinit(gpa);
}
fn freeExportList(gpa: *Allocator, export_list: []*Export) void {
src/Sema.zig
@@ -46,6 +46,12 @@ comptime_args: []TypedValue = &.{},
/// don't accidentally apply it to a function prototype which is used in the
/// type expression of a generic function parameter.
comptime_args_fn_inst: Zir.Inst.Index = 0,
+/// When `comptime_args` is provided, this field is also provided. It was used as
+/// the key in the `monomorphed_funcs` set. The `func` instruction is supposed
+/// to use this instead of allocating a fresh one. This avoids an unnecessary
+/// extra hash table lookup in the `monomorphed_funcs` set.
+/// Sema will set this to null when it takes ownership.
+preallocated_new_func: ?*Module.Fn = null,
const std = @import("std");
const mem = std.mem;
@@ -2354,6 +2360,40 @@ fn zirCall(
return sema.analyzeCall(block, func, func_src, call_src, modifier, ensure_result_used, resolved_args);
}
+const GenericCallAdapter = struct {
+ generic_fn: *Module.Fn,
+ precomputed_hash: u64,
+ func_ty_info: Type.Payload.Function.Data,
+ comptime_vals: []const Value,
+
+ pub fn eql(ctx: @This(), adapted_key: void, other_key: *Module.Fn) bool {
+ _ = adapted_key;
+ // The generic function Decl is guaranteed to be the first dependency
+ // of each of its instantiations.
+ const generic_owner_decl = other_key.owner_decl.dependencies.keys()[0];
+ if (ctx.generic_fn.owner_decl != generic_owner_decl) return false;
+
+ // This logic must be kept in sync with the logic in `analyzeCall` that
+ // computes the hash.
+ const other_comptime_args = other_key.comptime_args.?;
+ for (ctx.func_ty_info.param_types) |param_ty, i| {
+ if (ctx.func_ty_info.paramIsComptime(i) and param_ty.tag() != .generic_poison) {
+ if (!ctx.comptime_vals[i].eql(other_comptime_args[i].val, param_ty)) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+ /// The implementation of the hash is in semantic analysis of function calls, so
+ /// that any errors when computing the hash can be properly reported.
+ pub fn hash(ctx: @This(), adapted_key: void) u64 {
+ _ = adapted_key;
+ return ctx.precomputed_hash;
+ }
+};
+
fn analyzeCall(
sema: *Sema,
block: *Scope.Block,
@@ -2524,193 +2564,192 @@ fn analyzeCall(
// Check the Module's generic function map with an adapted context, so that we
// can match against `uncasted_args` rather than doing the work below to create a
// generic Scope only to junk it if it matches an existing instantiation.
- // TODO
-
const namespace = module_fn.owner_decl.namespace;
const fn_zir = namespace.file_scope.zir;
const fn_info = fn_zir.getFnInfo(module_fn.zir_body_inst);
const zir_tags = fn_zir.instructions.items(.tag);
- const new_func = new_func: {
- try namespace.anon_decls.ensureUnusedCapacity(gpa, 1);
-
- // Create a Decl for the new function.
- const new_decl = try mod.allocateNewDecl(namespace, module_fn.owner_decl.src_node);
- // TODO better names for generic function instantiations
- const name_index = mod.getNextAnonNameIndex();
- new_decl.name = try std.fmt.allocPrintZ(gpa, "{s}__anon_{d}", .{
- module_fn.owner_decl.name, name_index,
- });
- new_decl.src_line = module_fn.owner_decl.src_line;
- new_decl.is_pub = module_fn.owner_decl.is_pub;
- new_decl.is_exported = module_fn.owner_decl.is_exported;
- new_decl.has_align = module_fn.owner_decl.has_align;
- new_decl.has_linksection = module_fn.owner_decl.has_linksection;
- new_decl.zir_decl_index = module_fn.owner_decl.zir_decl_index;
- new_decl.alive = true; // This Decl is called at runtime.
- new_decl.has_tv = true;
- new_decl.owns_tv = true;
- new_decl.analysis = .in_progress;
- new_decl.generation = mod.generation;
-
- namespace.anon_decls.putAssumeCapacityNoClobber(new_decl, {});
-
- var new_decl_arena = std.heap.ArenaAllocator.init(sema.gpa);
- errdefer new_decl_arena.deinit();
-
- // Re-run the block that creates the function, with the comptime parameters
- // pre-populated inside `inst_map`. This causes `param_comptime` and
- // `param_anytype_comptime` ZIR instructions to be ignored, resulting in a
- // new, monomorphized function, with the comptime parameters elided.
- var child_sema: Sema = .{
- .mod = mod,
- .gpa = gpa,
- .arena = sema.arena,
- .code = fn_zir,
- .owner_decl = new_decl,
- .namespace = namespace,
- .func = null,
- .owner_func = null,
- .comptime_args = try new_decl_arena.allocator.alloc(TypedValue, uncasted_args.len),
- .comptime_args_fn_inst = module_fn.zir_body_inst,
- };
- defer child_sema.deinit();
-
- var child_block: Scope.Block = .{
- .parent = null,
- .sema = &child_sema,
- .src_decl = new_decl,
- .instructions = .{},
- .inlining = null,
- .is_comptime = true,
- };
- defer {
- child_block.instructions.deinit(gpa);
- child_block.params.deinit(gpa);
- }
-
- try child_sema.inst_map.ensureUnusedCapacity(gpa, @intCast(u32, uncasted_args.len));
- var arg_i: usize = 0;
- for (fn_info.param_body) |inst| {
- const is_comptime = switch (zir_tags[inst]) {
- .param_comptime, .param_anytype_comptime => true,
- .param, .param_anytype => false,
- else => continue,
- };
- // TODO: pass .unneeded to resolveConstValue and then if we get
- // error.NeededSourceLocation resolve the arg source location and
- // try again.
- const arg_src = call_src;
- const arg = uncasted_args[arg_i];
- if (try sema.resolveMaybeUndefVal(block, arg_src, arg)) |arg_val| {
- const child_arg = try child_sema.addConstant(sema.typeOf(arg), arg_val);
- child_sema.inst_map.putAssumeCapacityNoClobber(inst, child_arg);
- } else if (is_comptime) {
- return sema.failWithNeededComptime(block, arg_src);
+ const new_module_func = new_func: {
+ // This hash must match `Module.MonomorphedFuncsContext.hash`.
+ // For parameters explicitly marked comptime and simple parameter type expressions,
+ // we know whether a parameter is elided from a monomorphed function, and can
+ // use it in the hash here. However, for parameter type expressions that are not
+ // explicitly marked comptime and rely on previous parameter comptime values, we
+ // don't find out until after generating a monomorphed function whether the parameter
+ // type ended up being a "must-be-comptime-known" type.
+ var hasher = std.hash.Wyhash.init(0);
+ std.hash.autoHash(&hasher, @ptrToInt(module_fn));
+
+ const comptime_vals = try sema.arena.alloc(Value, func_ty_info.param_types.len);
+
+ for (func_ty_info.param_types) |param_ty, i| {
+ const is_comptime = func_ty_info.paramIsComptime(i);
+ if (is_comptime and param_ty.tag() != .generic_poison) {
+ const arg_src = call_src; // TODO better source location
+ const casted_arg = try sema.coerce(block, param_ty, uncasted_args[i], arg_src);
+ if (try sema.resolveMaybeUndefVal(block, arg_src, casted_arg)) |arg_val| {
+ arg_val.hash(param_ty, &hasher);
+ comptime_vals[i] = arg_val;
+ } else {
+ return sema.failWithNeededComptime(block, arg_src);
+ }
}
- arg_i += 1;
}
- const new_func_inst = try child_sema.resolveBody(&child_block, fn_info.param_body);
- const new_func_val = try child_sema.resolveConstValue(&child_block, .unneeded, new_func_inst);
- const new_func = new_func_val.castTag(.function).?.data;
-
- arg_i = 0;
- for (fn_info.param_body) |inst| {
- switch (zir_tags[inst]) {
- .param_comptime, .param_anytype_comptime, .param, .param_anytype => {},
- else => continue,
- }
- const arg = child_sema.inst_map.get(inst).?;
- const arg_val = (child_sema.resolveMaybeUndefValAllowVariables(&child_block, .unneeded, arg) catch unreachable).?;
- if (arg_val.tag() == .generic_poison) {
- child_sema.comptime_args[arg_i] = .{
- .ty = Type.initTag(.noreturn),
- .val = Value.initTag(.unreachable_value),
- };
- } else {
- child_sema.comptime_args[arg_i] = .{
- .ty = try child_sema.typeOf(arg).copy(&new_decl_arena.allocator),
- .val = try arg_val.copy(&new_decl_arena.allocator),
- };
- }
-
- arg_i += 1;
+ const adapter: GenericCallAdapter = .{
+ .generic_fn = module_fn,
+ .precomputed_hash = hasher.final(),
+ .func_ty_info = func_ty_info,
+ .comptime_vals = comptime_vals,
+ };
+ const gop = try mod.monomorphed_funcs.getOrPutAdapted(gpa, {}, adapter);
+ if (gop.found_existing) {
+ const callee_func = gop.key_ptr.*;
+ break :res try sema.finishGenericCall(
+ block,
+ call_src,
+ callee_func,
+ func_src,
+ uncasted_args,
+ fn_info,
+ zir_tags,
+ );
}
+ gop.key_ptr.* = try gpa.create(Module.Fn);
+ break :new_func gop.key_ptr.*;
+ };
- // Populate the Decl ty/val with the function and its type.
- new_decl.ty = try child_sema.typeOf(new_func_inst).copy(&new_decl_arena.allocator);
- new_decl.val = try Value.Tag.function.create(&new_decl_arena.allocator, new_func);
- new_decl.analysis = .complete;
+ try namespace.anon_decls.ensureUnusedCapacity(gpa, 1);
- // Queue up a `codegen_func` work item for the new Fn. The `comptime_args` field
- // will be populated, ensuring it will have `analyzeBody` called with the ZIR
- // parameters mapped appropriately.
- try mod.comp.bin_file.allocateDeclIndexes(new_decl);
- try mod.comp.work_queue.writeItem(.{ .codegen_func = new_func });
+ // Create a Decl for the new function.
+ const new_decl = try mod.allocateNewDecl(namespace, module_fn.owner_decl.src_node);
+ // TODO better names for generic function instantiations
+ const name_index = mod.getNextAnonNameIndex();
+ new_decl.name = try std.fmt.allocPrintZ(gpa, "{s}__anon_{d}", .{
+ module_fn.owner_decl.name, name_index,
+ });
+ new_decl.src_line = module_fn.owner_decl.src_line;
+ new_decl.is_pub = module_fn.owner_decl.is_pub;
+ new_decl.is_exported = module_fn.owner_decl.is_exported;
+ new_decl.has_align = module_fn.owner_decl.has_align;
+ new_decl.has_linksection = module_fn.owner_decl.has_linksection;
+ new_decl.zir_decl_index = module_fn.owner_decl.zir_decl_index;
+ new_decl.alive = true; // This Decl is called at runtime.
+ new_decl.has_tv = true;
+ new_decl.owns_tv = true;
+ new_decl.analysis = .in_progress;
+ new_decl.generation = mod.generation;
+
+ namespace.anon_decls.putAssumeCapacityNoClobber(new_decl, {});
+
+ var new_decl_arena = std.heap.ArenaAllocator.init(sema.gpa);
+ errdefer new_decl_arena.deinit();
+
+ // Re-run the block that creates the function, with the comptime parameters
+ // pre-populated inside `inst_map`. This causes `param_comptime` and
+ // `param_anytype_comptime` ZIR instructions to be ignored, resulting in a
+ // new, monomorphized function, with the comptime parameters elided.
+ var child_sema: Sema = .{
+ .mod = mod,
+ .gpa = gpa,
+ .arena = sema.arena,
+ .code = fn_zir,
+ .owner_decl = new_decl,
+ .namespace = namespace,
+ .func = null,
+ .owner_func = null,
+ .comptime_args = try new_decl_arena.allocator.alloc(TypedValue, uncasted_args.len),
+ .comptime_args_fn_inst = module_fn.zir_body_inst,
+ .preallocated_new_func = new_module_func,
+ };
+ defer child_sema.deinit();
- try new_decl.finalizeNewArena(&new_decl_arena);
- break :new_func try sema.analyzeDeclVal(block, func_src, new_decl);
+ var child_block: Scope.Block = .{
+ .parent = null,
+ .sema = &child_sema,
+ .src_decl = new_decl,
+ .instructions = .{},
+ .inlining = null,
+ .is_comptime = true,
};
+ defer {
+ child_block.instructions.deinit(gpa);
+ child_block.params.deinit(gpa);
+ }
- // Save it into the Module's generic function map.
- // TODO
+ try child_sema.inst_map.ensureUnusedCapacity(gpa, @intCast(u32, uncasted_args.len));
+ var arg_i: usize = 0;
+ for (fn_info.param_body) |inst| {
+ const is_comptime = switch (zir_tags[inst]) {
+ .param_comptime, .param_anytype_comptime => true,
+ .param, .param_anytype => false,
+ else => continue,
+ } or func_ty_info.paramIsComptime(arg_i);
+ const arg_src = call_src; // TODO: better source location
+ const arg = uncasted_args[arg_i];
+ if (try sema.resolveMaybeUndefVal(block, arg_src, arg)) |arg_val| {
+ const child_arg = try child_sema.addConstant(sema.typeOf(arg), arg_val);
+ child_sema.inst_map.putAssumeCapacityNoClobber(inst, child_arg);
+ } else if (is_comptime) {
+ return sema.failWithNeededComptime(block, arg_src);
+ }
+ arg_i += 1;
+ }
+ const new_func_inst = try child_sema.resolveBody(&child_block, fn_info.param_body);
+ const new_func_val = try child_sema.resolveConstValue(&child_block, .unneeded, new_func_inst);
+ const new_func = new_func_val.castTag(.function).?.data;
+ assert(new_func == new_module_func);
- // Make a runtime call to the new function, making sure to omit the comptime args.
- try sema.requireRuntimeBlock(block, call_src);
- const new_func_val = sema.resolveConstValue(block, .unneeded, new_func) catch unreachable;
- const new_module_func = new_func_val.castTag(.function).?.data;
- const comptime_args = new_module_func.comptime_args.?;
- const runtime_args_len = count: {
- var count: u32 = 0;
- var arg_i: usize = 0;
- for (fn_info.param_body) |inst| {
- switch (zir_tags[inst]) {
- .param_comptime, .param_anytype_comptime, .param, .param_anytype => {
- if (comptime_args[arg_i].val.tag() == .unreachable_value) {
- count += 1;
- }
- arg_i += 1;
- },
- else => continue,
- }
+ arg_i = 0;
+ for (fn_info.param_body) |inst| {
+ switch (zir_tags[inst]) {
+ .param_comptime, .param_anytype_comptime, .param, .param_anytype => {},
+ else => continue,
}
- break :count count;
- };
- const runtime_args = try sema.arena.alloc(Air.Inst.Ref, runtime_args_len);
- {
- const new_fn_ty = new_module_func.owner_decl.ty;
- var runtime_i: u32 = 0;
- var total_i: u32 = 0;
- for (fn_info.param_body) |inst| {
- switch (zir_tags[inst]) {
- .param_comptime, .param_anytype_comptime, .param, .param_anytype => {},
- else => continue,
- }
- const is_runtime = comptime_args[total_i].val.tag() == .unreachable_value;
- if (is_runtime) {
- const param_ty = new_fn_ty.fnParamType(runtime_i);
- const arg_src = call_src; // TODO: better source location
- const uncasted_arg = uncasted_args[total_i];
- const casted_arg = try sema.coerce(block, param_ty, uncasted_arg, arg_src);
- runtime_args[runtime_i] = casted_arg;
- runtime_i += 1;
- }
- total_i += 1;
+ const arg = child_sema.inst_map.get(inst).?;
+ const arg_val = (child_sema.resolveMaybeUndefValAllowVariables(&child_block, .unneeded, arg) catch unreachable).?;
+
+ if (arg_val.tag() == .generic_poison) {
+ child_sema.comptime_args[arg_i] = .{
+ .ty = Type.initTag(.noreturn),
+ .val = Value.initTag(.unreachable_value),
+ };
+ } else {
+ child_sema.comptime_args[arg_i] = .{
+ .ty = try child_sema.typeOf(arg).copy(&new_decl_arena.allocator),
+ .val = try arg_val.copy(&new_decl_arena.allocator),
+ };
}
+
+ arg_i += 1;
}
- try sema.air_extra.ensureUnusedCapacity(gpa, @typeInfo(Air.Call).Struct.fields.len +
- runtime_args_len);
- const func_inst = try block.addInst(.{
- .tag = .call,
- .data = .{ .pl_op = .{
- .operand = new_func,
- .payload = sema.addExtraAssumeCapacity(Air.Call{
- .args_len = runtime_args_len,
- }),
- } },
- });
- sema.appendRefsAssumeCapacity(runtime_args);
- break :res func_inst;
+
+ // Populate the Decl ty/val with the function and its type.
+ new_decl.ty = try child_sema.typeOf(new_func_inst).copy(&new_decl_arena.allocator);
+ new_decl.val = try Value.Tag.function.create(&new_decl_arena.allocator, new_func);
+ new_decl.analysis = .complete;
+
+ // Queue up a `codegen_func` work item for the new Fn. The `comptime_args` field
+ // will be populated, ensuring it will have `analyzeBody` called with the ZIR
+ // parameters mapped appropriately.
+ try mod.comp.bin_file.allocateDeclIndexes(new_decl);
+ try mod.comp.work_queue.writeItem(.{ .codegen_func = new_func });
+
+ try new_decl.finalizeNewArena(&new_decl_arena);
+
+ // The generic function Decl is guaranteed to be the first dependency
+ // of each of its instantiations.
+ assert(new_decl.dependencies.keys().len == 0);
+ try mod.declareDeclDependency(new_decl, module_fn.owner_decl);
+
+ break :res try sema.finishGenericCall(
+ block,
+ call_src,
+ new_module_func,
+ func_src,
+ uncasted_args,
+ fn_info,
+ zir_tags,
+ );
} else res: {
const args = try sema.arena.alloc(Air.Inst.Ref, uncasted_args.len);
for (uncasted_args) |uncasted_arg, i| {
@@ -2745,6 +2784,75 @@ fn analyzeCall(
return result;
}
+fn finishGenericCall(
+ sema: *Sema,
+ block: *Scope.Block,
+ call_src: LazySrcLoc,
+ callee: *Module.Fn,
+ func_src: LazySrcLoc,
+ uncasted_args: []const Air.Inst.Ref,
+ fn_info: Zir.FnInfo,
+ zir_tags: []const Zir.Inst.Tag,
+) CompileError!Air.Inst.Ref {
+ const callee_inst = try sema.analyzeDeclVal(block, func_src, callee.owner_decl);
+
+ // Make a runtime call to the new function, making sure to omit the comptime args.
+ try sema.requireRuntimeBlock(block, call_src);
+
+ const comptime_args = callee.comptime_args.?;
+ const runtime_args_len = count: {
+ var count: u32 = 0;
+ var arg_i: usize = 0;
+ for (fn_info.param_body) |inst| {
+ switch (zir_tags[inst]) {
+ .param_comptime, .param_anytype_comptime, .param, .param_anytype => {
+ if (comptime_args[arg_i].val.tag() == .unreachable_value) {
+ count += 1;
+ }
+ arg_i += 1;
+ },
+ else => continue,
+ }
+ }
+ break :count count;
+ };
+ const runtime_args = try sema.arena.alloc(Air.Inst.Ref, runtime_args_len);
+ {
+ const new_fn_ty = callee.owner_decl.ty;
+ var runtime_i: u32 = 0;
+ var total_i: u32 = 0;
+ for (fn_info.param_body) |inst| {
+ switch (zir_tags[inst]) {
+ .param_comptime, .param_anytype_comptime, .param, .param_anytype => {},
+ else => continue,
+ }
+ const is_runtime = comptime_args[total_i].val.tag() == .unreachable_value;
+ if (is_runtime) {
+ const param_ty = new_fn_ty.fnParamType(runtime_i);
+ const arg_src = call_src; // TODO: better source location
+ const uncasted_arg = uncasted_args[total_i];
+ const casted_arg = try sema.coerce(block, param_ty, uncasted_arg, arg_src);
+ runtime_args[runtime_i] = casted_arg;
+ runtime_i += 1;
+ }
+ total_i += 1;
+ }
+ }
+ try sema.air_extra.ensureUnusedCapacity(sema.gpa, @typeInfo(Air.Call).Struct.fields.len +
+ runtime_args_len);
+ const func_inst = try block.addInst(.{
+ .tag = .call,
+ .data = .{ .pl_op = .{
+ .operand = callee_inst,
+ .payload = sema.addExtraAssumeCapacity(Air.Call{
+ .args_len = runtime_args_len,
+ }),
+ } },
+ });
+ sema.appendRefsAssumeCapacity(runtime_args);
+ return func_inst;
+}
+
fn zirIntType(sema: *Sema, block: *Scope.Block, inst: Zir.Inst.Index) CompileError!Air.Inst.Ref {
_ = block;
const tracy = trace(@src());
@@ -3419,7 +3527,15 @@ fn funcCommon(
const mod = sema.mod;
- const new_func = if (body_inst == 0) undefined else try sema.gpa.create(Module.Fn);
+ const new_func: *Module.Fn = new_func: {
+ if (body_inst == 0) break :new_func undefined;
+ if (sema.comptime_args_fn_inst == body_inst) {
+ const new_func = sema.preallocated_new_func.?;
+ sema.preallocated_new_func = null; // take ownership
+ break :new_func new_func;
+ }
+ break :new_func try sema.gpa.create(Module.Fn);
+ };
errdefer if (body_inst != 0) sema.gpa.destroy(new_func);
const fn_ty: Type = fn_ty: {
@@ -3620,7 +3736,7 @@ fn zirParam(
try block.params.append(sema.gpa, .{
.ty = param_ty,
- .is_comptime = is_comptime,
+ .is_comptime = is_comptime or param_ty.requiresComptime(),
});
const result = try sema.addConstant(param_ty, Value.initTag(.generic_poison));
try sema.inst_map.putNoClobber(sema.gpa, inst, result);
src/type.zig
@@ -549,8 +549,13 @@ pub const Type = extern union {
pub fn hash(self: Type) u64 {
var hasher = std.hash.Wyhash.init(0);
+ self.hashWithHasher(&hasher);
+ return hasher.final();
+ }
+
+ pub fn hashWithHasher(self: Type, hasher: *std.hash.Wyhash) void {
const zig_type_tag = self.zigTypeTag();
- std.hash.autoHash(&hasher, zig_type_tag);
+ std.hash.autoHash(hasher, zig_type_tag);
switch (zig_type_tag) {
.Type,
.Void,
@@ -568,34 +573,34 @@ pub const Type = extern union {
.Int => {
// Detect that e.g. u64 != usize, even if the bits match on a particular target.
if (self.isNamedInt()) {
- std.hash.autoHash(&hasher, self.tag());
+ std.hash.autoHash(hasher, self.tag());
} else {
// Remaining cases are arbitrary sized integers.
// The target will not be branched upon, because we handled target-dependent cases above.
const info = self.intInfo(@as(Target, undefined));
- std.hash.autoHash(&hasher, info.signedness);
- std.hash.autoHash(&hasher, info.bits);
+ std.hash.autoHash(hasher, info.signedness);
+ std.hash.autoHash(hasher, info.bits);
}
},
.Array, .Vector => {
- std.hash.autoHash(&hasher, self.arrayLen());
- std.hash.autoHash(&hasher, self.elemType().hash());
+ std.hash.autoHash(hasher, self.arrayLen());
+ std.hash.autoHash(hasher, self.elemType().hash());
// TODO hash array sentinel
},
.Fn => {
- std.hash.autoHash(&hasher, self.fnReturnType().hash());
- std.hash.autoHash(&hasher, self.fnCallingConvention());
+ std.hash.autoHash(hasher, self.fnReturnType().hash());
+ std.hash.autoHash(hasher, self.fnCallingConvention());
const params_len = self.fnParamLen();
- std.hash.autoHash(&hasher, params_len);
+ std.hash.autoHash(hasher, params_len);
var i: usize = 0;
while (i < params_len) : (i += 1) {
- std.hash.autoHash(&hasher, self.fnParamType(i).hash());
+ std.hash.autoHash(hasher, self.fnParamType(i).hash());
}
- std.hash.autoHash(&hasher, self.fnIsVarArgs());
+ std.hash.autoHash(hasher, self.fnIsVarArgs());
},
.Optional => {
var buf: Payload.ElemType = undefined;
- std.hash.autoHash(&hasher, self.optionalChild(&buf).hash());
+ std.hash.autoHash(hasher, self.optionalChild(&buf).hash());
},
.Float,
.Struct,
@@ -612,7 +617,6 @@ pub const Type = extern union {
// TODO implement more type hashing
},
}
- return hasher.final();
}
pub const HashContext64 = struct {
@@ -3373,7 +3377,7 @@ pub const Type = extern union {
data: Data,
// TODO look into optimizing this memory to take fewer bytes
- const Data = struct {
+ pub const Data = struct {
param_types: []Type,
comptime_params: [*]bool,
return_type: Type,
@@ -3381,7 +3385,7 @@ pub const Type = extern union {
is_var_args: bool,
is_generic: bool,
- fn paramIsComptime(self: @This(), i: usize) bool {
+ pub fn paramIsComptime(self: @This(), i: usize) bool {
if (!self.is_generic) return false;
assert(i < self.param_types.len);
return self.comptime_params[i];
src/value.zig
@@ -1117,12 +1117,82 @@ pub const Value = extern union {
return order(a, b).compare(.eq);
}
+ pub fn hash(val: Value, ty: Type, hasher: *std.hash.Wyhash) void {
+ switch (ty.zigTypeTag()) {
+ .BoundFn => unreachable, // TODO remove this from the language
+
+ .Void,
+ .NoReturn,
+ .Undefined,
+ .Null,
+ => {},
+
+ .Type => {
+ var buf: ToTypeBuffer = undefined;
+ return val.toType(&buf).hashWithHasher(hasher);
+ },
+ .Bool => {
+ std.hash.autoHash(hasher, val.toBool());
+ },
+ .Int, .ComptimeInt => {
+ var space: BigIntSpace = undefined;
+ const big = val.toBigInt(&space);
+ std.hash.autoHash(hasher, big.positive);
+ for (big.limbs) |limb| {
+ std.hash.autoHash(hasher, limb);
+ }
+ },
+ .Float, .ComptimeFloat => {
+ @panic("TODO implement hashing float values");
+ },
+ .Pointer => {
+ @panic("TODO implement hashing pointer values");
+ },
+ .Array, .Vector => {
+ @panic("TODO implement hashing array/vector values");
+ },
+ .Struct => {
+ @panic("TODO implement hashing struct values");
+ },
+ .Optional => {
+ @panic("TODO implement hashing optional values");
+ },
+ .ErrorUnion => {
+ @panic("TODO implement hashing error union values");
+ },
+ .ErrorSet => {
+ @panic("TODO implement hashing error set values");
+ },
+ .Enum => {
+ @panic("TODO implement hashing enum values");
+ },
+ .Union => {
+ @panic("TODO implement hashing union values");
+ },
+ .Fn => {
+ @panic("TODO implement hashing function values");
+ },
+ .Opaque => {
+ @panic("TODO implement hashing opaque values");
+ },
+ .Frame => {
+ @panic("TODO implement hashing frame values");
+ },
+ .AnyFrame => {
+ @panic("TODO implement hashing anyframe values");
+ },
+ .EnumLiteral => {
+ @panic("TODO implement hashing enum literal values");
+ },
+ }
+ }
+
pub const ArrayHashContext = struct {
ty: Type,
- pub fn hash(self: @This(), v: Value) u32 {
+ pub fn hash(self: @This(), val: Value) u32 {
const other_context: HashContext = .{ .ty = self.ty };
- return @truncate(u32, other_context.hash(v));
+ return @truncate(u32, other_context.hash(val));
}
pub fn eql(self: @This(), a: Value, b: Value) bool {
return a.eql(b, self.ty);
@@ -1132,76 +1202,9 @@ pub const Value = extern union {
pub const HashContext = struct {
ty: Type,
- pub fn hash(self: @This(), v: Value) u64 {
+ pub fn hash(self: @This(), val: Value) u64 {
var hasher = std.hash.Wyhash.init(0);
-
- switch (self.ty.zigTypeTag()) {
- .BoundFn => unreachable, // TODO remove this from the language
-
- .Void,
- .NoReturn,
- .Undefined,
- .Null,
- => {},
-
- .Type => {
- var buf: ToTypeBuffer = undefined;
- return v.toType(&buf).hash();
- },
- .Bool => {
- std.hash.autoHash(&hasher, v.toBool());
- },
- .Int, .ComptimeInt => {
- var space: BigIntSpace = undefined;
- const big = v.toBigInt(&space);
- std.hash.autoHash(&hasher, big.positive);
- for (big.limbs) |limb| {
- std.hash.autoHash(&hasher, limb);
- }
- },
- .Float, .ComptimeFloat => {
- @panic("TODO implement hashing float values");
- },
- .Pointer => {
- @panic("TODO implement hashing pointer values");
- },
- .Array, .Vector => {
- @panic("TODO implement hashing array/vector values");
- },
- .Struct => {
- @panic("TODO implement hashing struct values");
- },
- .Optional => {
- @panic("TODO implement hashing optional values");
- },
- .ErrorUnion => {
- @panic("TODO implement hashing error union values");
- },
- .ErrorSet => {
- @panic("TODO implement hashing error set values");
- },
- .Enum => {
- @panic("TODO implement hashing enum values");
- },
- .Union => {
- @panic("TODO implement hashing union values");
- },
- .Fn => {
- @panic("TODO implement hashing function values");
- },
- .Opaque => {
- @panic("TODO implement hashing opaque values");
- },
- .Frame => {
- @panic("TODO implement hashing frame values");
- },
- .AnyFrame => {
- @panic("TODO implement hashing anyframe values");
- },
- .EnumLiteral => {
- @panic("TODO implement hashing enum literal values");
- },
- }
+ val.hash(self.ty, &hasher);
return hasher.final();
}
src/Zir.zig
@@ -4930,11 +4930,13 @@ fn findDeclsBody(
}
}
-pub fn getFnInfo(zir: Zir, fn_inst: Inst.Index) struct {
+pub const FnInfo = struct {
param_body: []const Inst.Index,
body: []const Inst.Index,
total_params_len: u32,
-} {
+};
+
+pub fn getFnInfo(zir: Zir, fn_inst: Inst.Index) FnInfo {
const tags = zir.instructions.items(.tag);
const datas = zir.instructions.items(.data);
const info: struct {
test/behavior/basic.zig
@@ -92,3 +92,73 @@ fn first4KeysOfHomeRow() []const u8 {
test "return string from function" {
try expect(mem.eql(u8, first4KeysOfHomeRow(), "aoeu"));
}
+
+test "hex escape" {
+ try expect(mem.eql(u8, "\x68\x65\x6c\x6c\x6f", "hello"));
+}
+
+test "multiline string" {
+ const s1 =
+ \\one
+ \\two)
+ \\three
+ ;
+ const s2 = "one\ntwo)\nthree";
+ try expect(mem.eql(u8, s1, s2));
+}
+
+test "multiline string comments at start" {
+ const s1 =
+ //\\one
+ \\two)
+ \\three
+ ;
+ const s2 = "two)\nthree";
+ try expect(mem.eql(u8, s1, s2));
+}
+
+test "multiline string comments at end" {
+ const s1 =
+ \\one
+ \\two)
+ //\\three
+ ;
+ const s2 = "one\ntwo)";
+ try expect(mem.eql(u8, s1, s2));
+}
+
+test "multiline string comments in middle" {
+ const s1 =
+ \\one
+ //\\two)
+ \\three
+ ;
+ const s2 = "one\nthree";
+ try expect(mem.eql(u8, s1, s2));
+}
+
+test "multiline string comments at multiple places" {
+ const s1 =
+ \\one
+ //\\two
+ \\three
+ //\\four
+ \\five
+ ;
+ const s2 = "one\nthree\nfive";
+ try expect(mem.eql(u8, s1, s2));
+}
+
+test "call result of if else expression" {
+ try expect(mem.eql(u8, f2(true), "a"));
+ try expect(mem.eql(u8, f2(false), "b"));
+}
+fn f2(x: bool) []const u8 {
+ return (if (x) fA else fB)();
+}
+fn fA() []const u8 {
+ return "a";
+}
+fn fB() []const u8 {
+ return "b";
+}
test/behavior/generics.zig
@@ -3,167 +3,14 @@ const testing = std.testing;
const expect = testing.expect;
const expectEqual = testing.expectEqual;
-test "simple generic fn" {
- try expect(max(i32, 3, -1) == 3);
- try expect(max(f32, 0.123, 0.456) == 0.456);
- try expect(add(2, 3) == 5);
+test "one param, explicit comptime" {
+ var x: usize = 0;
+ x += checkSize(i32);
+ x += checkSize(bool);
+ x += checkSize(bool);
+ try expect(x == 6);
}
-fn max(comptime T: type, a: T, b: T) T {
- return if (a > b) a else b;
-}
-
-fn add(comptime a: i32, b: i32) i32 {
- return (comptime a) + b;
-}
-
-const the_max = max(u32, 1234, 5678);
-test "compile time generic eval" {
- try expect(the_max == 5678);
-}
-
-fn gimmeTheBigOne(a: u32, b: u32) u32 {
- return max(u32, a, b);
-}
-
-fn shouldCallSameInstance(a: u32, b: u32) u32 {
- return max(u32, a, b);
-}
-
-fn sameButWithFloats(a: f64, b: f64) f64 {
- return max(f64, a, b);
-}
-
-test "fn with comptime args" {
- try expect(gimmeTheBigOne(1234, 5678) == 5678);
- try expect(shouldCallSameInstance(34, 12) == 34);
- try expect(sameButWithFloats(0.43, 0.49) == 0.49);
-}
-
-test "var params" {
- try expect(max_i32(12, 34) == 34);
- try expect(max_f64(1.2, 3.4) == 3.4);
-}
-
-test {
- comptime try expect(max_i32(12, 34) == 34);
- comptime try expect(max_f64(1.2, 3.4) == 3.4);
-}
-
-fn max_var(a: anytype, b: anytype) @TypeOf(a + b) {
- return if (a > b) a else b;
-}
-
-fn max_i32(a: i32, b: i32) i32 {
- return max_var(a, b);
-}
-
-fn max_f64(a: f64, b: f64) f64 {
- return max_var(a, b);
-}
-
-pub fn List(comptime T: type) type {
- return SmallList(T, 8);
-}
-
-pub fn SmallList(comptime T: type, comptime STATIC_SIZE: usize) type {
- return struct {
- items: []T,
- length: usize,
- prealloc_items: [STATIC_SIZE]T,
- };
-}
-
-test "function with return type type" {
- var list: List(i32) = undefined;
- var list2: List(i32) = undefined;
- list.length = 10;
- list2.length = 10;
- try expect(list.prealloc_items.len == 8);
- try expect(list2.prealloc_items.len == 8);
-}
-
-test "generic struct" {
- var a1 = GenNode(i32){
- .value = 13,
- .next = null,
- };
- var b1 = GenNode(bool){
- .value = true,
- .next = null,
- };
- try expect(a1.value == 13);
- try expect(a1.value == a1.getVal());
- try expect(b1.getVal());
-}
-fn GenNode(comptime T: type) type {
- return struct {
- value: T,
- next: ?*GenNode(T),
- fn getVal(n: *const GenNode(T)) T {
- return n.value;
- }
- };
-}
-
-test "const decls in struct" {
- try expect(GenericDataThing(3).count_plus_one == 4);
-}
-fn GenericDataThing(comptime count: isize) type {
- return struct {
- const count_plus_one = count + 1;
- };
-}
-
-test "use generic param in generic param" {
- try expect(aGenericFn(i32, 3, 4) == 7);
-}
-fn aGenericFn(comptime T: type, comptime a: T, b: T) T {
- return a + b;
-}
-
-test "generic fn with implicit cast" {
- try expect(getFirstByte(u8, &[_]u8{13}) == 13);
- try expect(getFirstByte(u16, &[_]u16{
- 0,
- 13,
- }) == 0);
-}
-fn getByte(ptr: ?*const u8) u8 {
- return ptr.?.*;
-}
-fn getFirstByte(comptime T: type, mem: []const T) u8 {
- return getByte(@ptrCast(*const u8, &mem[0]));
-}
-
-const foos = [_]fn (anytype) bool{
- foo1,
- foo2,
-};
-
-fn foo1(arg: anytype) bool {
- return arg;
-}
-fn foo2(arg: anytype) bool {
- return !arg;
-}
-
-test "array of generic fns" {
- try expect(foos[0](true));
- try expect(!foos[1](true));
-}
-
-test "generic fn keeps non-generic parameter types" {
- const A = 128;
-
- const S = struct {
- fn f(comptime T: type, s: []T) !void {
- try expect(A != @typeInfo(@TypeOf(s)).Pointer.alignment);
- }
- };
-
- // The compiler monomorphizes `S.f` for `T=u8` on its first use, check that
- // `x` type not affect `s` parameter type.
- var x: [16]u8 align(A) = undefined;
- try S.f(u8, &x);
+fn checkSize(comptime T: type) usize {
+ return @sizeOf(T);
}
test/behavior/generics_stage1.zig
@@ -0,0 +1,169 @@
+const std = @import("std");
+const testing = std.testing;
+const expect = testing.expect;
+const expectEqual = testing.expectEqual;
+
+test "simple generic fn" {
+ try expect(max(i32, 3, -1) == 3);
+ try expect(max(f32, 0.123, 0.456) == 0.456);
+ try expect(add(2, 3) == 5);
+}
+
+fn max(comptime T: type, a: T, b: T) T {
+ return if (a > b) a else b;
+}
+
+fn add(comptime a: i32, b: i32) i32 {
+ return (comptime a) + b;
+}
+
+const the_max = max(u32, 1234, 5678);
+test "compile time generic eval" {
+ try expect(the_max == 5678);
+}
+
+fn gimmeTheBigOne(a: u32, b: u32) u32 {
+ return max(u32, a, b);
+}
+
+fn shouldCallSameInstance(a: u32, b: u32) u32 {
+ return max(u32, a, b);
+}
+
+fn sameButWithFloats(a: f64, b: f64) f64 {
+ return max(f64, a, b);
+}
+
+test "fn with comptime args" {
+ try expect(gimmeTheBigOne(1234, 5678) == 5678);
+ try expect(shouldCallSameInstance(34, 12) == 34);
+ try expect(sameButWithFloats(0.43, 0.49) == 0.49);
+}
+
+test "var params" {
+ try expect(max_i32(12, 34) == 34);
+ try expect(max_f64(1.2, 3.4) == 3.4);
+}
+
+test {
+ comptime try expect(max_i32(12, 34) == 34);
+ comptime try expect(max_f64(1.2, 3.4) == 3.4);
+}
+
+fn max_var(a: anytype, b: anytype) @TypeOf(a + b) {
+ return if (a > b) a else b;
+}
+
+fn max_i32(a: i32, b: i32) i32 {
+ return max_var(a, b);
+}
+
+fn max_f64(a: f64, b: f64) f64 {
+ return max_var(a, b);
+}
+
+pub fn List(comptime T: type) type {
+ return SmallList(T, 8);
+}
+
+pub fn SmallList(comptime T: type, comptime STATIC_SIZE: usize) type {
+ return struct {
+ items: []T,
+ length: usize,
+ prealloc_items: [STATIC_SIZE]T,
+ };
+}
+
+test "function with return type type" {
+ var list: List(i32) = undefined;
+ var list2: List(i32) = undefined;
+ list.length = 10;
+ list2.length = 10;
+ try expect(list.prealloc_items.len == 8);
+ try expect(list2.prealloc_items.len == 8);
+}
+
+test "generic struct" {
+ var a1 = GenNode(i32){
+ .value = 13,
+ .next = null,
+ };
+ var b1 = GenNode(bool){
+ .value = true,
+ .next = null,
+ };
+ try expect(a1.value == 13);
+ try expect(a1.value == a1.getVal());
+ try expect(b1.getVal());
+}
+fn GenNode(comptime T: type) type {
+ return struct {
+ value: T,
+ next: ?*GenNode(T),
+ fn getVal(n: *const GenNode(T)) T {
+ return n.value;
+ }
+ };
+}
+
+test "const decls in struct" {
+ try expect(GenericDataThing(3).count_plus_one == 4);
+}
+fn GenericDataThing(comptime count: isize) type {
+ return struct {
+ const count_plus_one = count + 1;
+ };
+}
+
+test "use generic param in generic param" {
+ try expect(aGenericFn(i32, 3, 4) == 7);
+}
+fn aGenericFn(comptime T: type, comptime a: T, b: T) T {
+ return a + b;
+}
+
+test "generic fn with implicit cast" {
+ try expect(getFirstByte(u8, &[_]u8{13}) == 13);
+ try expect(getFirstByte(u16, &[_]u16{
+ 0,
+ 13,
+ }) == 0);
+}
+fn getByte(ptr: ?*const u8) u8 {
+ return ptr.?.*;
+}
+fn getFirstByte(comptime T: type, mem: []const T) u8 {
+ return getByte(@ptrCast(*const u8, &mem[0]));
+}
+
+const foos = [_]fn (anytype) bool{
+ foo1,
+ foo2,
+};
+
+fn foo1(arg: anytype) bool {
+ return arg;
+}
+fn foo2(arg: anytype) bool {
+ return !arg;
+}
+
+test "array of generic fns" {
+ try expect(foos[0](true));
+ try expect(!foos[1](true));
+}
+
+test "generic fn keeps non-generic parameter types" {
+ const A = 128;
+
+ const S = struct {
+ fn f(comptime T: type, s: []T) !void {
+ try expect(A != @typeInfo(@TypeOf(s)).Pointer.alignment);
+ }
+ };
+
+ // The compiler monomorphizes `S.f` for `T=u8` on its first use, check that
+ // `x` type not affect `s` parameter type.
+ var x: [16]u8 align(A) = undefined;
+ try S.f(u8, &x);
+}
test/behavior/misc.zig
@@ -40,10 +40,6 @@ test "constant equal function pointers" {
fn emptyFn() void {}
-test "hex escape" {
- try expect(mem.eql(u8, "\x68\x65\x6c\x6c\x6f", "hello"));
-}
-
test "string concatenation" {
try expect(mem.eql(u8, "OK" ++ " IT " ++ "WORKED", "OK IT WORKED"));
}
@@ -62,59 +58,7 @@ test "string escapes" {
try expectEqualStrings("\u{1234}\u{069}\u{1}", "\xe1\x88\xb4\x69\x01");
}
-test "multiline string" {
- const s1 =
- \\one
- \\two)
- \\three
- ;
- const s2 = "one\ntwo)\nthree";
- try expect(mem.eql(u8, s1, s2));
-}
-
-test "multiline string comments at start" {
- const s1 =
- //\\one
- \\two)
- \\three
- ;
- const s2 = "two)\nthree";
- try expect(mem.eql(u8, s1, s2));
-}
-
-test "multiline string comments at end" {
- const s1 =
- \\one
- \\two)
- //\\three
- ;
- const s2 = "one\ntwo)";
- try expect(mem.eql(u8, s1, s2));
-}
-
-test "multiline string comments in middle" {
- const s1 =
- \\one
- //\\two)
- \\three
- ;
- const s2 = "one\nthree";
- try expect(mem.eql(u8, s1, s2));
-}
-
-test "multiline string comments at multiple places" {
- const s1 =
- \\one
- //\\two
- \\three
- //\\four
- \\five
- ;
- const s2 = "one\nthree\nfive";
- try expect(mem.eql(u8, s1, s2));
-}
-
-test "multiline C string" {
+test "multiline string literal is null terminated" {
const s1 =
\\one
\\two)
@@ -169,20 +113,6 @@ fn outer() i64 {
return inner();
}
-test "call result of if else expression" {
- try expect(mem.eql(u8, f2(true), "a"));
- try expect(mem.eql(u8, f2(false), "b"));
-}
-fn f2(x: bool) []const u8 {
- return (if (x) fA else fB)();
-}
-fn fA() []const u8 {
- return "a";
-}
-fn fB() []const u8 {
- return "b";
-}
-
test "constant enum initialization with differing sizes" {
try test3_1(test3_foo);
try test3_2(test3_bar);
test/behavior.zig
@@ -4,6 +4,7 @@ test {
// Tests that pass for both.
_ = @import("behavior/bool.zig");
_ = @import("behavior/basic.zig");
+ _ = @import("behavior/generics.zig");
if (!builtin.zig_is_stage2) {
// Tests that only pass for stage1.
@@ -94,7 +95,7 @@ test {
_ = @import("behavior/fn_in_struct_in_comptime.zig");
_ = @import("behavior/fn_delegation.zig");
_ = @import("behavior/for.zig");
- _ = @import("behavior/generics.zig");
+ _ = @import("behavior/generics_stage1.zig");
_ = @import("behavior/hasdecl.zig");
_ = @import("behavior/hasfield.zig");
_ = @import("behavior/if.zig");