Zig 2214 lines
// Flash eval — the compile-time evaluator: the value/type pool (the Pool)
// and the walking pass that folds constants over it (the Evaluator).
//
// The Pool is the substrate: one flat interned store holding types *and*
// values, addressed by `Vid`. A type is a value whose type is `type`, so a
// folded constant, a builtin type name, and a generic's type argument all live
// in the same space and compare by integer equality — two equal compile-time
// entities always intern to the same Vid, so equality never walks a structure
// twice.
//
// The Evaluator walks the program after the binding checks and evaluates
// every `const` initializer it can. Evaluation is three-valued: a *known*
// value (interned), a *definite error* (a collected diagnostic — a division
// or remainder by a known zero, or a malformed generic application, which the
// downstream compiler would also reject), or *`unknown`* — the deliberate
// silent state for everything outside the evaluator's current reach (floats,
// `#`-builtins, comptime mutation, field access, …), which stays checked
// downstream exactly as before. The standing contract: the evaluator never
// diagnoses anything the downstream compiler would accept — when in doubt it
// degrades to `unknown` (an `i128`-overflowing fold degrades rather than
// misreport, because compile-time integers downstream are
// arbitrary-precision) — and it never changes what is emitted (lowering does
// not consult this module).
//
// Generic applications are checked natively. A top-level `fn` with a
// `comptime` parameter or a `type` return is a *generic declaration*; every
// application of one — `Name(args…)` in type position (a parameter, return,
// binding, or field annotation) or as a value-position call — is checked for
// argument arity and, where the parameter's declared type resolves at file
// scope, for argument kind: a `type`-typed parameter wants a type argument,
// a concretely typed one wants a value. A parameter whose type cannot be
// resolved (it names another parameter, an import, or a cycle) is unchecked,
// and an argument evaluating to `unknown` is never wrong — the three-valued
// contract extends to applications. A well-formed application over fully
// known arguments is then *instantiated*: the `(owner, arguments)` pair is
// interned as its own pool key — interning is the instantiate-once
// memoization — and when the generic's body is a single `return` of a
// container definition or a type expression, the instance's result type is
// evaluated with the parameters bound to the argument values. A returned
// container definition is nominal *per instance* (the instance key is the
// type, so `List(u8)` and `List(u16)` are distinct types and `List(u8)`
// twice is one); any other body shape — or a result that is not a type —
// leaves the instance `unknown`, still arity/kind-checked. A depth cap and
// an instantiation budget guard runaway recursion with targeted diagnostics.
//
// Identity rules:
// * well-known entries (the builtin simple types, `true`/`false`, the void
// value, `unknown`) occupy fixed leading indices — they exist in every
// pool, before any dynamic entry, so their Vids are compile-time constants;
// * composite types (optional, the pointer/slice/array families, error
// union, function type, tuple) are *structural*: keyed on their child
// Vids, so `?u8` interns once no matter how often it is spelled;
// * declared `struct`/`enum`/`union` types are *nominal*: identity is the
// defining AST node, unique per declaration. This leans on the AST being
// arena-stable for the whole compile — node addresses never move — which
// holds because the pool only reads the AST, never rewrites it;
// * generic instances are keyed on `(owner declaration, argument Vids)`,
// so the same application memoizes and distinct arguments split identity.
//
// Values carry small payloads: `int` is an `i128` (a fold that needs more
// degrades to `unknown` rather than misfold), `string` is a slice of the
// original source buffer (the ast.zig zero-copy invariant extends here), and
// `unknown` is the deliberate third state — "not evaluated at compile time" —
// that downstream checks treat as silence, never as an error.
//
// Dedup is a linear scan over the flat store (getOrPut by walking existing
// entries). Deliberate: the pool needs no hash map, the store is append-only,
// and Flash-program scale keeps the scan cheap; a faster index can replace the
// scan later without changing a caller.
//
// The pool is checking machinery only: lowering never consults it, so the
// emitted Zig is byte-for-byte independent of anything interned here.
const std = @import("std");
const ast = @import("ast.zig");
const Oom = error{OutOfMemory};
// A pool index — the identity of one interned type or value. The named tags
// are the well-known entries every pool is seeded with, in declaration order
// from index 0; dynamic entries follow. Two Vids are the same type/value
// exactly when they are the same integer.
pub const Vid = enum(u32) {
// the builtin simple types
type_bool,
type_void,
type_type,
type_noreturn,
type_anyopaque,
type_comptime_int,
type_comptime_float,
type_usize,
type_isize,
type_u8,
type_u16,
type_u32,
type_u64,
type_u128,
type_i8,
type_i16,
type_i32,
type_i64,
type_i128,
type_f16,
type_f32,
type_f64,
type_f80,
type_f128,
// the well-known values
true_value,
false_value,
void_value,
unknown,
_,
};
// The number of well-known entries — the index where dynamic interning starts.
pub const static_count = @typeInfo(Vid).@"enum".fields.len;
// A simple (word-named, non-composite) builtin type with no parameters of its
// own. The sized integer types are not here — they are `int_type` keys, so an
// arbitrary width (`u7`) interns through the same shape as a well-known one.
pub const Simple = enum {
bool,
void,
type,
noreturn,
anyopaque,
comptime_int,
comptime_float,
usize,
isize,
f16,
f32,
f64,
f80,
f128,
};
// A sized integer type `uN` / `iN`. The common widths are pre-seeded as
// well-known entries; any other width interns dynamically with the same key.
pub const IntType = struct {
signedness: std.builtin.Signedness,
bits: u16,
};
// How many items a pointer addresses — the `*T` / `[*]T` / `[]T` split.
pub const PtrSize = enum { one, many, slice };
// A pointer-family type: single-item pointers, many-item pointers, and slices
// share one key, distinguished by `size`. `sentinel`, when set, is the Vid of
// the terminator *value* (`[:0]u8`'s zero); `is_mut`/`is_volatile` mirror the
// surface qualifiers (const pointee is the default, so it is the false state).
pub const Ptr = struct {
size: PtrSize,
is_mut: bool = false,
is_volatile: bool = false,
sentinel: ?Vid = null,
elem: Vid,
};
// A fixed-length array type `[N]T` / `[N:s]T`. `len` is the Vid of the length
// *value* (an interned int), keeping the key structural on children like every
// other composite. An inferred-length `[_]T` never reaches the pool — its
// concrete type is not known until the initializer is, and an unevaluated one
// stays `unknown`.
pub const ArrayType = struct {
len: Vid,
sentinel: ?Vid = null,
elem: Vid,
};
// An error-union type `E!T` / `!T`. `set` is the error-set type's Vid, or null
// for the inferred-set form (whose set only the declaring function knows).
pub const ErrorUnion = struct {
set: ?Vid,
payload: Vid,
};
// A function type `fn(P, …) R`. Parameter types in source order; a missing
// return type is normalized to `void` by the caller, never encoded as absence
// here, so spelling variants of the same type cannot make distinct keys.
pub const FnType = struct {
params: []const Vid,
ret: Vid,
};
// A declared container type — the nominal identity. The payload is the
// address of the defining AST node: each `struct { … }` / `enum { … }` /
// `union { … }` / `error { … }` expression is one node, so two textually
// identical declarations are two distinct types, exactly as declared
// types behave (an error set's node is its whole Expr — the variant
// carries only the member names, which have no address of their own).
pub const Container = union(enum) {
struct_type: *const ast.StructDef,
enum_type: *const ast.EnumDef,
union_type: *const ast.UnionDef,
error_set_type: *const ast.Expr,
};
// A generic instance — a recognized generic applied to fully known
// compile-time arguments. Identity is the owning declaration plus the
// argument Vids, so interning an application *is* the instantiate-once
// memoization: the same generic over the same arguments is the same Vid.
// For a generic whose body returns a container definition, this Vid is
// itself the instance's nominal type — distinct arguments make distinct
// types, exactly as instantiated generics behave downstream.
pub const Instance = struct {
owner: *const ast.FnDecl,
args: []const Vid,
};
// The full shape of one interned entry — what a Vid resolves back to. Types
// first, then values; `unknown` is both the not-a-compile-time-constant value
// and the not-resolved type, one deliberate third state for both spaces.
pub const Key = union(enum) {
// types
simple: Simple,
int_type: IntType,
optional: Vid, // ?T — the child type's Vid
ptr: Ptr,
array: ArrayType,
error_union: ErrorUnion,
fn_type: FnType,
tuple: []const Vid, // (A, B) — element types in order
container: Container,
instance: Instance, // a generic application — `List(u8)` — as a type of its own
// values
int: i128,
bool_value: bool,
string: []const u8, // a slice of the original source buffer
void_value,
unknown,
};
// The interned store. Append-only: a Vid handed out stays valid for the
// pool's lifetime, and `get` is a plain index.
pub const Pool = struct {
arena: std.mem.Allocator,
items: std.ArrayList(Key),
// A fresh pool, seeded with the well-known entries so the named Vid tags
// are valid immediately and `intern` finds them like any other entry.
pub fn init(arena: std.mem.Allocator) Oom!Pool {
var pool = Pool{ .arena = arena, .items = .empty };
inline for (@typeInfo(Vid).@"enum".fields) |f| {
try pool.items.append(arena, staticKey(@enumFromInt(f.value)));
}
return pool;
}
// The getOrPut: return the Vid of an entry equal to `key`, interning it
// first when absent. A linear front-to-back scan over the flat store — no
// hash map (see the header). Slice-carrying keys are duped into the pool's
// arena on insert, so a caller may pass a temporary.
pub fn intern(self: *Pool, key: Key) Oom!Vid {
for (self.items.items, 0..) |existing, i| {
if (keyEql(existing, key)) return @enumFromInt(i);
}
const owned: Key = switch (key) {
.fn_type => |f| .{ .fn_type = .{
.params = try self.arena.dupe(Vid, f.params),
.ret = f.ret,
} },
.tuple => |elems| .{ .tuple = try self.arena.dupe(Vid, elems) },
.instance => |inst| .{ .instance = .{
.owner = inst.owner,
.args = try self.arena.dupe(Vid, inst.args),
} },
else => key,
};
try self.items.append(self.arena, owned);
return @enumFromInt(self.items.items.len - 1);
}
// Resolve a Vid back to its key. Every Vid this pool handed out is a
// valid index; anything else is a caller bug.
pub fn get(self: *const Pool, vid: Vid) Key {
return self.items.items[@intFromEnum(vid)];
}
// The number of interned entries (the well-known seed included).
pub fn count(self: *const Pool) usize {
return self.items.items.len;
}
};
// The key a well-known Vid is seeded with. Total over the named tags; the
// seeding loop in `init` walks them in declaration order, so tag N lands at
// index N by construction.
fn staticKey(vid: Vid) Key {
return switch (vid) {
.type_bool => .{ .simple = .bool },
.type_void => .{ .simple = .void },
.type_type => .{ .simple = .type },
.type_noreturn => .{ .simple = .noreturn },
.type_anyopaque => .{ .simple = .anyopaque },
.type_comptime_int => .{ .simple = .comptime_int },
.type_comptime_float => .{ .simple = .comptime_float },
.type_usize => .{ .simple = .usize },
.type_isize => .{ .simple = .isize },
.type_u8 => .{ .int_type = .{ .signedness = .unsigned, .bits = 8 } },
.type_u16 => .{ .int_type = .{ .signedness = .unsigned, .bits = 16 } },
.type_u32 => .{ .int_type = .{ .signedness = .unsigned, .bits = 32 } },
.type_u64 => .{ .int_type = .{ .signedness = .unsigned, .bits = 64 } },
.type_u128 => .{ .int_type = .{ .signedness = .unsigned, .bits = 128 } },
.type_i8 => .{ .int_type = .{ .signedness = .signed, .bits = 8 } },
.type_i16 => .{ .int_type = .{ .signedness = .signed, .bits = 16 } },
.type_i32 => .{ .int_type = .{ .signedness = .signed, .bits = 32 } },
.type_i64 => .{ .int_type = .{ .signedness = .signed, .bits = 64 } },
.type_i128 => .{ .int_type = .{ .signedness = .signed, .bits = 128 } },
.type_f16 => .{ .simple = .f16 },
.type_f32 => .{ .simple = .f32 },
.type_f64 => .{ .simple = .f64 },
.type_f80 => .{ .simple = .f80 },
.type_f128 => .{ .simple = .f128 },
.true_value => .{ .bool_value = true },
.false_value => .{ .bool_value = false },
.void_value => .void_value,
.unknown => .unknown,
_ => unreachable, // dynamic Vids are interned, never seeded
};
}
// Structural key equality — the dedup predicate `intern` scans with. Strings
// compare by content (two spellings of the same literal are one value);
// containers compare by node address (the nominal rule); slice-carrying keys
// compare element-wise.
fn keyEql(a: Key, b: Key) bool {
if (@as(std.meta.Tag(Key), a) != @as(std.meta.Tag(Key), b)) return false;
return switch (a) {
.simple => |s| s == b.simple,
.int_type => |t| t.signedness == b.int_type.signedness and t.bits == b.int_type.bits,
.optional => |child| child == b.optional,
.ptr => |p| std.meta.eql(p, b.ptr),
.array => |arr| std.meta.eql(arr, b.array),
.error_union => |eu| std.meta.eql(eu, b.error_union),
.fn_type => |f| f.ret == b.fn_type.ret and std.mem.eql(Vid, f.params, b.fn_type.params),
.tuple => |elems| std.mem.eql(Vid, elems, b.tuple),
.container => |c| std.meta.eql(c, b.container),
.instance => |inst| inst.owner == b.instance.owner and std.mem.eql(Vid, inst.args, b.instance.args),
.int => |v| v == b.int,
.bool_value => |v| v == b.bool_value,
.string => |s| std.mem.eql(u8, s, b.string),
.void_value, .unknown => true,
};
}
// The Vid of a builtin type *name* (`u8`, `bool`, `comptime_int`, `f32`,
// `u7`, …), or null when the name is no builtin. The word-named builtins
// resolve to their well-known entries; a sized integer name parses its width,
// so an uncommon `u7` interns dynamically through the same key the seeded
// widths use.
pub fn builtinType(pool: *Pool, name: []const u8) Oom!?Vid {
if (std.meta.stringToEnum(Simple, name)) |s| return try pool.intern(.{ .simple = s });
if (name.len >= 2 and (name[0] == 'u' or name[0] == 'i')) {
const bits = std.fmt.parseInt(u16, name[1..], 10) catch return null;
return try pool.intern(.{ .int_type = .{
.signedness = if (name[0] == 'u') .unsigned else .signed,
.bits = bits,
} });
}
return null;
}
// A collected evaluator diagnostic — the same shape sema collects (anchor =
// a slice into the source buffer; see sema.zig), kept as this module's own
// type so the evaluator depends on the AST alone. The caller copies entries
// into its own list.
pub const Diag = struct {
anchor: []const u8,
msg: []const u8,
note_anchor: ?[]const u8 = null,
note_msg: ?[]const u8 = null,
};
// One name whose compile-time value is known (or known to be `unknown`).
const EnvEntry = struct {
name: []const u8,
value: Vid,
};
// One evaluated generic instance: the interned instance key and the result
// type its body evaluated to (`unknown` where out of reach). Kept beside the
// pool rather than in it — a result is an attribute of an instance, not part
// of its identity.
const InstanceResult = struct {
instance: Vid,
result: Vid,
};
// The instantiation nesting bound — past it a recursive generic is reported
// and degrades to `unknown` (the downstream compiler has its own quota).
const max_inst_depth = 64;
// What one generic parameter accepts, resolved from its declared type at
// file scope. `wants_type` is a parameter whose type is `type` itself
// (directly or through an alias); `wants_value` one whose type resolved to
// any other concrete type; `unchecked` everything unresolvable — a type
// naming another parameter, an import, a resolution cycle — which stays
// silent per the three-valued contract.
const ParamKind = enum { wants_type, wants_value, unchecked };
// One recognized generic declaration: a top-level `fn` with a `comptime`
// parameter or a `type` return. Parameter kinds are resolved lazily (a
// parameter's type may alias a constant declared further down the file) and
// memoized once the file scope is complete; `resolving` guards against a
// parameter-type cycle re-entering its own resolution.
const Generic = struct {
name: []const u8,
decl: *const ast.FnDecl,
kinds: ?[]const ParamKind = null,
resolving: bool = false,
};
// The walking pass. It mirrors sema's scope discipline — one flat stack of
// frames, file level at the bottom — but records *values*, not bindings:
// only an immutable binding lands in the environment (a `var` is evaluated
// for definite errors, never recorded — mutation tracking is out of reach).
// Lookups that miss resolve to `unknown`, never to a diagnostic; the binding
// errors are sema's, not the evaluator's.
pub const Evaluator = struct {
arena: std.mem.Allocator,
pool: *Pool,
diags: std.ArrayList(Diag),
env: std.ArrayList(EnvEntry),
frame_base: usize = 0,
// The recognized generic declarations, collected before any evaluation so
// a constant's initializer can apply a generic declared later in the file.
generics: std.ArrayList(Generic),
// How many leading env entries are file-scope constants so far — the only
// names parameter-kind resolution may see (a body's locals are the
// caller's scope, never the declaration's).
file_limit: usize = 0,
// Set once the file-scope pass is complete: parameter kinds resolved from
// here on are final and may be memoized.
kinds_final: bool = false,
// When set, `lookup` sees only the first `lookup_limit` env entries —
// parameter-kind resolution restricting itself to the file scope.
lookup_limit: ?usize = null,
// When set, `report` drops diagnostics — parameter-kind resolution walks
// type expressions whose definite errors the regular walk already owns.
quiet: bool = false,
// The memoized instance results, one entry per interned instance key
// (linear scan, like every other lookup here).
instance_results: std.ArrayList(InstanceResult),
// The active instantiation nesting depth, bounded by `max_inst_depth`.
inst_depth: usize = 0,
// How many instances this run has evaluated (memoized hits are free) and
// the cap — a field so a test can lower it. The branch-quota analog.
inst_count: usize = 0,
inst_budget: usize = 1000,
budget_reported: bool = false,
pub fn init(arena: std.mem.Allocator, pool: *Pool) Evaluator {
return .{ .arena = arena, .pool = pool, .diags = .empty, .env = .empty, .generics = .empty, .instance_results = .empty };
}
// Evaluate a whole program. Generic declarations are collected first, so
// every later application resolves its owner. Top-level constants are
// then evaluated and recorded in file order — a reference to a constant
// declared *later* in the file is not yet evaluated and degrades to
// `unknown` (silent; the downstream compiler evaluates lazily and accepts
// it) — and finally every function, test, and comptime-block body is
// walked for the local constants and definite errors inside it.
pub fn run(self: *Evaluator, program: ast.Program) Oom!void {
for (program.items) |*item| switch (item.*) {
.fn_decl => {
const f = &item.fn_decl;
if (isGenericDecl(f)) try self.generics.append(self.arena, .{ .name = f.name, .decl = f });
},
else => {},
};
for (program.items) |*item| switch (item.*) {
.const_decl => {
const d = &item.const_decl;
if (d.type) |*t| _ = try self.internTypeRef(t);
const v = try self.evalExpr(&d.value);
if (!d.is_mut) try self.env.append(self.arena, .{ .name = d.name, .value = v });
self.file_limit = self.env.items.len;
},
else => {},
};
// The file scope is complete — resolve and memoize every generic's
// parameter kinds before the body walks (whose local frames must
// never leak into a declaration's resolution).
self.kinds_final = true;
for (self.generics.items) |*g| _ = try self.kindsFor(g);
for (program.items) |*item| switch (item.*) {
.fn_decl => try self.evalFn(&item.fn_decl),
.comptime_block => |stmts| try self.evalBlock(stmts),
.test_decl => |t| try self.evalBlock(t.body),
else => {},
};
}
// The value recorded for `name`, innermost frame first, or null. Public
// surface for the callers that resolve a folded constant by name.
pub fn lookup(self: *const Evaluator, name: []const u8) ?Vid {
var i = self.lookup_limit orelse self.env.items.len;
while (i > 0) {
i -= 1;
if (std.mem.eql(u8, self.env.items[i].name, name)) return self.env.items[i].value;
}
return null;
}
fn report(self: *Evaluator, anchor: []const u8, msg: []const u8) Oom!void {
if (self.quiet) return;
try self.diags.append(self.arena, .{ .anchor = anchor, .msg = msg });
}
// A nested statement list in its own frame, popped on exit — sibling
// blocks may reuse a constant's name (sema enforces the rules; the
// evaluator only mirrors the visibility).
fn evalBlock(self: *Evaluator, stmts: []const ast.Stmt) Oom!void {
const saved = self.frame_base;
self.frame_base = self.env.items.len;
defer {
self.env.items.len = self.frame_base;
self.frame_base = saved;
}
for (stmts) |*s| try self.evalStmt(s);
}
fn evalStmt(self: *Evaluator, s: *const ast.Stmt) Oom!void {
switch (s.*) {
.bind => {
const b = &s.bind;
if (b.type) |*t| _ = try self.internTypeRef(t);
const v = try self.evalExpr(&b.value);
if (!b.is_mut) try self.env.append(self.arena, .{ .name = b.name, .value = v });
},
.destructure => _ = try self.evalExpr(&s.destructure.value),
.assign => _ = try self.evalExpr(&s.assign.value),
.destructure_assign => _ = try self.evalExpr(&s.destructure_assign.value),
.discard => _ = try self.evalExpr(&s.discard),
.expr => _ = try self.evalExpr(&s.expr),
// A known condition prunes the dead arm, exactly as the
// downstream compiler does (a definite error in an unreached
// branch is not an error there, so it must not be one here).
.if_stmt => {
const iff = &s.if_stmt;
const cond = try self.evalExpr(&iff.cond);
if (cond != .false_value) try self.evalBlock(iff.body);
if (cond != .true_value) {
if (iff.else_body) |eb| try self.evalBlock(eb);
}
},
.while_stmt => {
const w = &s.while_stmt;
const cond = try self.evalExpr(&w.cond);
if (cond != .false_value) try self.evalBlock(w.body);
if (w.else_body) |eb| try self.evalBlock(eb);
},
.for_stmt => {
const fr = &s.for_stmt;
_ = try self.evalExpr(&fr.iter);
if (fr.range_hi) |*hi| _ = try self.evalExpr(hi);
try self.evalBlock(fr.body);
if (fr.else_body) |eb| try self.evalBlock(eb);
},
.defer_stmt => |inner| try self.evalStmt(inner),
.errdefer_stmt => |inner| try self.evalStmt(inner),
.defer_block => |stmts| try self.evalBlock(stmts),
.errdefer_block => |stmts| try self.evalBlock(stmts),
}
}
// Evaluate one expression to a Vid. Takes a pointer into the AST (never
// a copy): a container definition's identity is its node address, so the
// expression must be the arena-resident original.
fn evalExpr(self: *Evaluator, e: *const ast.Expr) Oom!Vid {
switch (e.*) {
.int => |lex| {
const n = std.fmt.parseInt(i128, lex, 0) catch return .unknown;
return self.pool.intern(.{ .int = n });
},
.string => |lex| return self.pool.intern(.{ .string = lex }),
.value_word => |w| {
if (std.mem.eql(u8, w, "true")) return .true_value;
if (std.mem.eql(u8, w, "false")) return .false_value;
return .unknown;
},
.ident => |name| {
if (self.lookup(name)) |v| return v;
return (try builtinType(self.pool, name)) orelse .unknown;
},
.group => |g| return self.evalExpr(g),
.unary => return self.evalUnary(&e.unary),
.binary => return self.evalBinary(e),
// A known condition selects one arm and the other is never
// evaluated (dead-branch pruning, as downstream); an unknown
// condition evaluates both for their definite errors.
.if_expr => {
const iff = &e.if_expr;
const cond = try self.evalExpr(iff.cond);
if (cond == .true_value) return self.evalExpr(iff.then);
if (cond == .false_value) return self.evalExpr(iff.else_);
_ = try self.evalExpr(iff.then);
_ = try self.evalExpr(iff.else_);
return .unknown;
},
.type_lit => |t| return self.internTypeRef(t),
// A container definition is its own (nominal) type — and its
// field types, associated constants, and method bodies are walked
// here, so a definite error inside one is found wherever the
// container is defined.
.struct_def => {
for (e.struct_def.fields) |*fld| _ = try self.internTypeRef(&fld.type);
try self.evalContainerDecls(e.struct_def.decls);
return self.pool.intern(.{ .container = .{ .struct_type = &e.struct_def } });
},
.enum_def => {
try self.evalContainerDecls(e.enum_def.decls);
return self.pool.intern(.{ .container = .{ .enum_type = &e.enum_def } });
},
.union_def => {
for (e.union_def.variants) |*v| if (v.payload) |*t| {
_ = try self.internTypeRef(t);
};
try self.evalContainerDecls(e.union_def.decls);
return self.pool.intern(.{ .container = .{ .union_type = &e.union_def } });
},
// Everything below is outside the evaluator's reach — the result
// is `unknown` — but subexpressions are still walked, so a
// definite error inside an argument or operand is found.
.member => |m| {
_ = try self.evalExpr(m.base);
return .unknown;
},
// A call's result is out of reach unless the callee is a known
// generic declaration — then the call is an application site:
// checked for arity and argument kinds, and a well-formed one
// instantiated to the type it denotes (the arguments are
// evaluated either way, so their definite errors are found).
.call => |c| {
_ = try self.evalExpr(c.callee);
if (self.genericCallee(c.callee)) |g| {
return self.checkApplication(firstLexeme(c.callee) orelse g.name, g, c.args);
}
for (c.args) |*a| _ = try self.evalExpr(a);
return .unknown;
},
.builtin_call => |b| {
for (b.args) |*a| _ = try self.evalExpr(a);
return .unknown;
},
.index => |ix| {
_ = try self.evalExpr(ix.base);
_ = try self.evalExpr(ix.index);
return .unknown;
},
.slice => |sl| {
_ = try self.evalExpr(sl.base);
_ = try self.evalExpr(sl.lo);
if (sl.hi) |hi| _ = try self.evalExpr(hi);
if (sl.sentinel) |sen| _ = try self.evalExpr(sen);
return .unknown;
},
.deref => |d| {
_ = try self.evalExpr(d);
return .unknown;
},
.optional_unwrap => |u| {
_ = try self.evalExpr(u);
return .unknown;
},
.try_expr => |t| {
_ = try self.evalExpr(t);
return .unknown;
},
.catch_expr => |c| {
_ = try self.evalExpr(c.lhs);
_ = try self.evalExpr(c.handler);
return .unknown;
},
.switch_expr => |sw| {
_ = try self.evalExpr(sw.subject);
return .unknown;
},
.struct_lit => |fields| {
for (fields) |*f| _ = try self.evalExpr(&f.value);
return .unknown;
},
.typed_lit => |tl| {
_ = try self.evalExpr(tl.type);
for (tl.fields) |*f| _ = try self.evalExpr(&f.value);
return .unknown;
},
.block_expr => |blk| {
try self.evalBlock(blk.body);
return .unknown;
},
.brk => |b| {
if (b.value) |v| _ = try self.evalExpr(v);
return .unknown;
},
.ret => |maybe| {
if (maybe) |vals| for (vals) |*v| {
_ = try self.evalExpr(v);
};
return .unknown;
},
// An error-set definition is its own (nominal) type, like the
// containers above — interned so a type-position misuse of it
// (say, under `||`) is recognizable as a type.
.error_set => return self.pool.intern(.{ .container = .{ .error_set_type = e } }),
.float, .multiline_str, .char, .enum_lit, .error_lit, .asm_expr, .cont => return .unknown,
}
}
// The associated declarations of a container body: each constant's
// type annotation is walked and its initializer evaluated (definite
// errors found, value not recorded — an associated constant is
// referenced through its container, which is out of reach), and each
// method is walked like a top-level function.
fn evalContainerDecls(self: *Evaluator, decls: []const ast.ContainerDecl) Oom!void {
for (decls) |*decl| switch (decl.*) {
.constant => {
if (decl.constant.type) |*t| _ = try self.internTypeRef(t);
_ = try self.evalExpr(&decl.constant.value);
},
.method => try self.evalFn(&decl.method),
.use_import => {},
};
}
// A function's signature and body. The parameter and return types are
// walked first (generic applications and definite errors in an
// annotation are found here), then the body in its own frame with every
// named parameter recorded as `unknown` — a parameter's name must
// resolve to silence, never to an unrelated file-scope constant or a
// same-named generic.
fn evalFn(self: *Evaluator, f: *const ast.FnDecl) Oom!void {
for (f.params) |*p| _ = try self.internTypeRef(&p.type);
if (f.ret) |*r| _ = try self.internTypeRef(r);
const body = f.body orelse return;
const saved = self.frame_base;
self.frame_base = self.env.items.len;
defer {
self.env.items.len = self.frame_base;
self.frame_base = saved;
}
for (f.params) |p| if (p.name) |n| {
try self.env.append(self.arena, .{ .name = n, .value = .unknown });
};
for (body) |*st| try self.evalStmt(st);
}
// The generic a value-position call applies: the callee is a bare,
// unbound identifier naming a recognized generic declaration. A name
// bound in the environment — a parameter, a local, a folded constant —
// is never the file-level generic.
fn genericCallee(self: *Evaluator, callee: *const ast.Expr) ?*Generic {
switch (callee.*) {
.ident => |name| {
if (self.lookup(name) != null) return null;
return self.findGeneric(name);
},
else => return null,
}
}
fn findGeneric(self: *Evaluator, name: []const u8) ?*Generic {
for (self.generics.items) |*g| {
if (std.mem.eql(u8, g.name, name)) return g;
}
return null;
}
// The parameter kinds of a generic, resolved from the declared parameter
// types. Resolution is quiet (the regular annotation walk owns any
// definite error inside these types) and sees only the file scope (a
// declaration's types never resolve against a caller's locals). Before
// the file scope is complete the result is recomputed per call and not
// memoized — an alias a parameter type needs may not be recorded yet.
// Null means the entry is already being resolved (a parameter-type
// cycle); the caller skips kind checks, arity still holds.
fn kindsFor(self: *Evaluator, g: *Generic) Oom!?[]const ParamKind {
if (g.kinds) |k| return k;
if (g.resolving) return null;
g.resolving = true;
const saved_quiet = self.quiet;
const saved_limit = self.lookup_limit;
self.quiet = true;
self.lookup_limit = self.file_limit;
defer {
g.resolving = false;
self.quiet = saved_quiet;
self.lookup_limit = saved_limit;
}
const kinds = try self.arena.alloc(ParamKind, g.decl.params.len);
for (g.decl.params, 0..) |*p, i| {
const v = try self.internTypeRef(&p.type);
kinds[i] = if (v == .type_type)
.wants_type
else if (v == .unknown)
.unchecked
else
.wants_value;
}
if (self.kinds_final) g.kinds = kinds;
return kinds;
}
// Check one generic application — `Name(args…)` in type or value
// position — for arity and per-argument kind, then instantiate a
// well-formed one to the type it denotes. The arguments are evaluated
// here either way, so a definite error inside one is found even when
// the application itself is malformed; a malformed application is
// never instantiated.
fn checkApplication(self: *Evaluator, anchor: []const u8, g: *Generic, args: []const ast.Expr) Oom!Vid {
if (args.len != g.decl.params.len) {
try self.report(anchor, try std.fmt.allocPrint(
self.arena,
"generic '{s}' expects {d} argument{s}, found {d}",
.{ g.name, g.decl.params.len, plural(g.decl.params.len), args.len },
));
for (args) |*a| _ = try self.evalExpr(a);
return .unknown;
}
const kinds = try self.kindsFor(g);
const arg_vids = try self.arena.alloc(Vid, args.len);
var well_kinded = true;
for (args, 0..) |*a, i| {
const v = try self.evalExpr(a);
arg_vids[i] = v;
const ks = kinds orelse continue;
const arg_anchor = firstLexeme(a) orelse anchor;
switch (ks[i]) {
.wants_type => if (isKnownValue(self.pool.get(v))) {
well_kinded = false;
try self.report(arg_anchor, try std.fmt.allocPrint(
self.arena,
"argument {d} to generic '{s}' expects a type, found a value",
.{ i + 1, g.name },
));
},
.wants_value => if (self.isType(v)) {
well_kinded = false;
try self.report(arg_anchor, try std.fmt.allocPrint(
self.arena,
"argument {d} to generic '{s}' expects a value, found a type",
.{ i + 1, g.name },
));
},
.unchecked => {},
}
}
if (!well_kinded) return .unknown;
return self.instantiate(anchor, g, arg_vids);
}
// Instantiate a well-formed application over fully known arguments. The
// `(owner, args)` pair interns as an instance key — interning IS the
// memoization, so re-applying the same arguments costs one lookup — and
// the result type is evaluated only when the body is a single `return`:
// a returned container definition's type is the instance Vid itself
// (distinct arguments are distinct nominal types, as downstream — the
// definition node alone would collapse every argument list onto one
// type), a returned type expression evaluates with the parameters bound
// to the argument values, and anything else — any other body shape, a
// result that is not a type — stays `unknown`.
fn instantiate(self: *Evaluator, anchor: []const u8, g: *Generic, arg_vids: []const Vid) Oom!Vid {
const body = g.decl.body orelse return .unknown;
const ret_expr = singleReturnExpr(body) orelse return .unknown;
for (arg_vids) |v| if (v == .unknown) return .unknown;
const iv = try self.pool.intern(.{ .instance = .{ .owner = g.decl, .args = arg_vids } });
if (self.instanceResult(iv)) |r| return r;
// The depth and budget diagnostics bypass `quiet`: an instance
// evaluates once (memoized), possibly during quiet parameter-kind
// resolution, so no later loud walk would re-find them.
if (self.inst_depth >= max_inst_depth) {
try self.diags.append(self.arena, .{ .anchor = anchor, .msg = try std.fmt.allocPrint(
self.arena,
"generic '{s}' exceeds the instantiation depth limit ({d})",
.{ g.name, max_inst_depth },
) });
try self.recordInstance(iv, .unknown);
return .unknown;
}
if (self.inst_count >= self.inst_budget) {
if (!self.budget_reported) {
self.budget_reported = true;
try self.diags.append(self.arena, .{ .anchor = anchor, .msg = try std.fmt.allocPrint(
self.arena,
"generic '{s}' exceeds the instantiation budget ({d})",
.{ g.name, self.inst_budget },
) });
}
try self.recordInstance(iv, .unknown);
return .unknown;
}
self.inst_count += 1;
const result: Vid = switch (ret_expr.*) {
.struct_def, .enum_def, .union_def => iv,
else => blk: {
// The instance frame sits directly on the file scope:
// `lookup_limit` lifts so the bound parameters (appended
// past any caller frame) are visible, and the body
// evaluates quiet — every definite error spelled in it is
// owned by the loud body walk, and errors that exist only
// under substituted arguments stay out of this slice's
// boundary. A caller's locals are technically in view, but
// a generic body referencing a caller-local name is already
// a binding error, so that space is unreachable in accepted
// programs.
const saved_base = self.frame_base;
const saved_limit = self.lookup_limit;
const saved_quiet = self.quiet;
self.frame_base = self.env.items.len;
self.lookup_limit = null;
self.quiet = true;
self.inst_depth += 1;
defer {
self.inst_depth -= 1;
self.env.items.len = self.frame_base;
self.frame_base = saved_base;
self.lookup_limit = saved_limit;
self.quiet = saved_quiet;
}
for (g.decl.params, 0..) |p, i| if (p.name) |n| {
try self.env.append(self.arena, .{ .name = n, .value = arg_vids[i] });
};
const r = try self.evalExpr(ret_expr);
break :blk if (self.isType(r)) r else .unknown;
},
};
try self.recordInstance(iv, result);
return result;
}
// The memoized result of an interned instance, or null when it has not
// been evaluated yet.
fn instanceResult(self: *const Evaluator, iv: Vid) ?Vid {
for (self.instance_results.items) |entry| {
if (entry.instance == iv) return entry.result;
}
return null;
}
// Record an instance's result once; a re-entrant instantiation (the
// depth-capped recursion unwinding) finds the first record and skips.
fn recordInstance(self: *Evaluator, iv: Vid, result: Vid) Oom!void {
if (self.instanceResult(iv) != null) return;
try self.instance_results.append(self.arena, .{ .instance = iv, .result = result });
}
fn evalUnary(self: *Evaluator, u: *const ast.Unary) Oom!Vid {
const v = try self.evalExpr(u.operand);
if (std.mem.eql(u8, u.op, "!")) {
if (v == .true_value) return .false_value;
if (v == .false_value) return .true_value;
return .unknown;
}
if (std.mem.eql(u8, u.op, "-")) {
const n = self.knownInt(v) orelse return .unknown;
if (n == std.math.minInt(i128)) return .unknown; // -(min) overflows
return self.pool.intern(.{ .int = -n });
}
// `~` needs the operand's bit width (a typed constant the evaluator
// does not track) and `&` is an address — both out of reach.
return .unknown;
}
fn evalBinary(self: *Evaluator, e: *const ast.Expr) Oom!Vid {
const b = &e.binary;
const op = b.op;
const lv = try self.evalExpr(b.lhs);
const rv = try self.evalExpr(b.rhs);
// The one definite error: dividing by a *known* zero is rejected
// downstream no matter what the numerator is, so it is safe — and
// useful — to report it at the Flash source line.
if (std.mem.eql(u8, op, "/") or std.mem.eql(u8, op, "%")) {
if (self.knownInt(rv)) |d| if (d == 0) {
if (firstLexeme(e)) |anchor| try self.report(anchor, "division by zero");
return .unknown;
};
}
// `||` is boolean or — Flash has no error-set merge. A type operand
// (an error set, most likely) would otherwise lower to invalid Zig
// with no Flash-side diagnostic, so it is rejected here by name.
if (std.mem.eql(u8, op, "||") and (self.isType(lv) or self.isType(rv))) {
// An inline `error{…}` operand has no leftmost lexeme; the
// operator itself anchors the report then.
try self.report(firstLexeme(e) orelse op, "'||' is boolean or and cannot merge error sets — declare the combined error set explicitly");
return .unknown;
}
// Boolean logic. The left side decides where it can (`false && _`,
// `true || _`); otherwise both sides must be known.
if (std.mem.eql(u8, op, "&&")) {
if (lv == .false_value) return .false_value;
if (lv == .true_value and (rv == .true_value or rv == .false_value)) return rv;
return .unknown;
}
if (std.mem.eql(u8, op, "||")) {
if (lv == .true_value) return .true_value;
if (lv == .false_value and (rv == .true_value or rv == .false_value)) return rv;
return .unknown;
}
// Bool equality (`==` / `!=` on two known bools).
if (knownBool(lv) != null and knownBool(rv) != null) {
const equal = lv == rv;
if (std.mem.eql(u8, op, "==")) return boolVid(equal);
if (std.mem.eql(u8, op, "!=")) return boolVid(!equal);
return .unknown;
}
// Integer arithmetic, comparison, and bitwise folding.
const a = self.knownInt(lv) orelse return .unknown;
const c = self.knownInt(rv) orelse return .unknown;
return self.foldInts(op, a, c);
}
// Fold `a op c` over known i128 operands. Any result the i128 cannot
// hold — and any shape the downstream compiler treats specially (signed
// division rounding, oversized shifts) — degrades to `unknown`.
fn foldInts(self: *Evaluator, op: []const u8, a: i128, c: i128) Oom!Vid {
if (std.mem.eql(u8, op, "+")) {
const r = @addWithOverflow(a, c);
return if (r[1] != 0) .unknown else self.pool.intern(.{ .int = r[0] });
}
if (std.mem.eql(u8, op, "-")) {
const r = @subWithOverflow(a, c);
return if (r[1] != 0) .unknown else self.pool.intern(.{ .int = r[0] });
}
if (std.mem.eql(u8, op, "*")) {
const r = @mulWithOverflow(a, c);
return if (r[1] != 0) .unknown else self.pool.intern(.{ .int = r[0] });
}
// Plain `/` and `%` on a negative operand have rounding rules the
// downstream compiler gates behind dedicated builtins — degrade
// rather than guess (the known-zero divisor was already handled).
if (std.mem.eql(u8, op, "/")) {
if (a < 0 or c <= 0) return .unknown;
return self.pool.intern(.{ .int = @divTrunc(a, c) });
}
if (std.mem.eql(u8, op, "%")) {
if (a < 0 or c <= 0) return .unknown;
return self.pool.intern(.{ .int = @rem(a, c) });
}
if (std.mem.eql(u8, op, "&")) return self.pool.intern(.{ .int = a & c });
if (std.mem.eql(u8, op, "|")) return self.pool.intern(.{ .int = a | c });
if (std.mem.eql(u8, op, "^")) return self.pool.intern(.{ .int = a ^ c });
if (std.mem.eql(u8, op, "<<")) {
// A compile-time integer may legally shift past 127 downstream
// (arbitrary precision); past the i128 it degrades here.
if (c < 0 or c > 127) return .unknown;
const r = @shlWithOverflow(a, @as(u7, @intCast(c)));
return if (r[1] != 0) .unknown else self.pool.intern(.{ .int = r[0] });
}
if (std.mem.eql(u8, op, ">>")) {
if (c < 0 or c > 127) return .unknown;
return self.pool.intern(.{ .int = a >> @as(u7, @intCast(c)) });
}
if (std.mem.eql(u8, op, "==")) return boolVid(a == c);
if (std.mem.eql(u8, op, "!=")) return boolVid(a != c);
if (std.mem.eql(u8, op, "<")) return boolVid(a < c);
if (std.mem.eql(u8, op, "<=")) return boolVid(a <= c);
if (std.mem.eql(u8, op, ">")) return boolVid(a > c);
if (std.mem.eql(u8, op, ">=")) return boolVid(a >= c);
return .unknown; // `orelse` and anything new
}
// Intern the type a TypeRef denotes, or `unknown` where a child is out
// of reach. A dotted name roots in an import (out of reach); a bare name
// is a recorded constant holding a type, or a builtin.
fn internTypeRef(self: *Evaluator, t: *const ast.TypeRef) Oom!Vid {
switch (t.*) {
.name => |n| {
if (std.mem.indexOfScalar(u8, n, '.') != null) return .unknown;
if (self.lookup(n)) |v| {
return if (self.isType(v)) v else .unknown;
}
return (try builtinType(self.pool, n)) orelse .unknown;
},
.optional => |inner| {
const child = try self.internTypeRef(inner);
if (child == .unknown) return .unknown;
return self.pool.intern(.{ .optional = child });
},
.slice => |inner| return self.internPtr(inner, .slice, false, false, null),
.slice_mut => |inner| return self.internPtr(inner, .slice, true, false, null),
.many_ptr => |inner| return self.internPtr(inner, .many, false, false, null),
.many_ptr_mut => |inner| return self.internPtr(inner, .many, true, false, null),
.many_ptr_volatile => |inner| return self.internPtr(inner, .many, false, true, null),
.many_ptr_mut_volatile => |inner| return self.internPtr(inner, .many, true, true, null),
.ptr => |inner| return self.internPtr(inner, .one, false, false, null),
.ptr_mut => |inner| return self.internPtr(inner, .one, true, false, null),
.ptr_volatile => |inner| return self.internPtr(inner, .one, false, true, null),
.ptr_mut_volatile => |inner| return self.internPtr(inner, .one, true, true, null),
.slice_sentinel => |sp| return self.internSentinelPtr(sp, .slice, false),
.slice_sentinel_mut => |sp| return self.internSentinelPtr(sp, .slice, true),
.many_ptr_sentinel => |sp| return self.internSentinelPtr(sp, .many, false),
.many_ptr_sentinel_mut => |sp| return self.internSentinelPtr(sp, .many, true),
.array => |arr| {
const len = try self.evalExpr(arr.len);
if (self.knownInt(len) == null) return .unknown;
const elem = try self.internTypeRef(arr.elem);
if (elem == .unknown) return .unknown;
return self.pool.intern(.{ .array = .{ .len = len, .elem = elem } });
},
.array_sentinel => |arr| {
const len = try self.evalExpr(arr.len);
if (self.knownInt(len) == null) return .unknown;
const sen = try self.evalExpr(arr.sentinel);
if (sen == .unknown) return .unknown;
const elem = try self.internTypeRef(arr.elem);
if (elem == .unknown) return .unknown;
return self.pool.intern(.{ .array = .{ .len = len, .sentinel = sen, .elem = elem } });
},
// An inferred length is not a concrete type until its
// initializer is — out of reach.
.array_inferred, .array_inferred_sentinel => return .unknown,
.errunion => |eu| {
const set: ?Vid = if (eu.set) |s| blk: {
const sv = try self.internTypeRef(s);
if (sv == .unknown) return .unknown;
break :blk sv;
} else null;
const payload = try self.internTypeRef(eu.payload);
if (payload == .unknown) return .unknown;
return self.pool.intern(.{ .error_union = .{ .set = set, .payload = payload } });
},
.fn_type => |ft| {
const params = try self.arena.alloc(Vid, ft.params.len);
for (ft.params, 0..) |*p, i| {
params[i] = try self.internTypeRef(p);
if (params[i] == .unknown) return .unknown;
}
const ret: Vid = if (ft.ret) |r| blk: {
const rv = try self.internTypeRef(r);
if (rv == .unknown) return .unknown;
break :blk rv;
} else .type_void;
return self.pool.intern(.{ .fn_type = .{ .params = params, .ret = ret } });
},
// A generic application in type position is checked when its
// name is a known, unshadowed generic, and a well-formed one
// denotes its instance type (or `unknown` where instantiation
// is out of reach); a dotted name roots in an import.
.generic => |g| {
if (std.mem.indexOfScalar(u8, g.name, '.') == null and self.lookup(g.name) == null) {
if (self.findGeneric(g.name)) |gen| {
return self.checkApplication(g.name, gen, g.args);
}
}
for (g.args) |*a| _ = try self.evalExpr(a);
return .unknown;
},
.tuple => |elems| {
const vids = try self.arena.alloc(Vid, elems.len);
for (elems, 0..) |*el, i| {
vids[i] = try self.internTypeRef(el);
if (vids[i] == .unknown) return .unknown;
}
return self.pool.intern(.{ .tuple = vids });
},
}
}
fn internPtr(self: *Evaluator, inner: *const ast.TypeRef, size: PtrSize, is_mut: bool, is_volatile: bool, sentinel: ?Vid) Oom!Vid {
const elem = try self.internTypeRef(inner);
if (elem == .unknown) return .unknown;
return self.pool.intern(.{ .ptr = .{
.size = size,
.is_mut = is_mut,
.is_volatile = is_volatile,
.sentinel = sentinel,
.elem = elem,
} });
}
fn internSentinelPtr(self: *Evaluator, sp: ast.SentinelPtr, size: PtrSize, is_mut: bool) Oom!Vid {
const sen = try self.evalExpr(sp.sentinel);
if (sen == .unknown) return .unknown;
return self.internPtr(sp.elem, size, is_mut, false, sen);
}
fn knownInt(self: *const Evaluator, v: Vid) ?i128 {
return switch (self.pool.get(v)) {
.int => |n| n,
else => null,
};
}
fn isType(self: *const Evaluator, v: Vid) bool {
return switch (self.pool.get(v)) {
.simple, .int_type, .optional, .ptr, .array, .error_union, .fn_type, .tuple, .container, .instance => true,
.int, .bool_value, .string, .void_value, .unknown => false,
};
}
};
// Is this declaration generic — applicable as `Name(args…)`? A `comptime`
// parameter or a `type` return marks it; everything else is an ordinary
// function whose call sites are out of this module's reach.
fn isGenericDecl(f: *const ast.FnDecl) bool {
for (f.params) |p| {
if (p.is_comptime) return true;
}
if (f.ret) |r| switch (r) {
.name => |n| if (std.mem.eql(u8, n, "type")) return true,
else => {},
};
return false;
}
// The expression a single-`return` function body returns, or null for any
// other body shape — the only shape whose instance result type is evaluated
// (a multi-value return is a tuple of values, never a type).
fn singleReturnExpr(body: []const ast.Stmt) ?*const ast.Expr {
if (body.len != 1) return null;
if (body[0] != .expr) return null;
const e = &body[0].expr;
if (e.* != .ret) return null;
const vals = e.ret orelse return null;
if (vals.len != 1) return null;
return &vals[0];
}
// Is this a *known* non-type value — the shapes a `type` parameter
// definitely rejects? `unknown` is neither a value nor a type here.
fn isKnownValue(k: Key) bool {
return switch (k) {
.int, .bool_value, .string, .void_value => true,
else => false,
};
}
fn plural(n: usize) []const u8 {
return if (n == 1) "" else "s";
}
fn knownBool(v: Vid) ?bool {
return switch (v) {
.true_value => true,
.false_value => false,
else => null,
};
}
fn boolVid(b: bool) Vid {
return if (b) .true_value else .false_value;
}
// The leftmost source slice of an expression — its diagnostic anchor (the
// same descent sema's anchoring uses). Null when no single stored slice
// exists; the caller then skips the diagnostic rather than anchor it nowhere.
fn firstLexeme(x: *const ast.Expr) ?[]const u8 {
return switch (x.*) {
.int, .float, .string, .char, .ident, .value_word, .enum_lit, .error_lit => |s| s,
.member => |m| firstLexeme(m.base),
.deref => |d| firstLexeme(d),
.optional_unwrap => |u| firstLexeme(u),
.index => |ix| firstLexeme(ix.base),
.slice => |s| firstLexeme(s.base),
.call => |c| firstLexeme(c.callee),
.binary => |b| firstLexeme(b.lhs),
.unary => |u| u.op,
.group => |g| firstLexeme(g),
.try_expr => |t| firstLexeme(t),
.typed_lit => |tl| firstLexeme(tl.type),
else => null,
};
}
// --- tests ---------------------------------------------------------------
const testing = std.testing;
fn testPool(a: *std.heap.ArenaAllocator) Oom!Pool {
return Pool.init(a.allocator());
}
test "well-known entries sit at their named indices and round-trip" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
// The seed fills exactly the static range.
try testing.expectEqual(static_count, pool.count());
// get() at a named Vid yields its key …
try testing.expectEqual(Key{ .simple = .bool }, pool.get(.type_bool));
try testing.expectEqual(Key{ .simple = .comptime_int }, pool.get(.type_comptime_int));
try testing.expectEqual(
Key{ .int_type = .{ .signedness = .unsigned, .bits = 8 } },
pool.get(.type_u8),
);
try testing.expectEqual(Key{ .bool_value = true }, pool.get(.true_value));
try testing.expectEqual(Key.void_value, pool.get(.void_value));
try testing.expectEqual(Key.unknown, pool.get(.unknown));
// … and interning that key finds the static entry, never a duplicate.
try testing.expectEqual(Vid.type_u8, try pool.intern(.{ .int_type = .{ .signedness = .unsigned, .bits = 8 } }));
try testing.expectEqual(Vid.type_i64, try pool.intern(.{ .int_type = .{ .signedness = .signed, .bits = 64 } }));
try testing.expectEqual(Vid.type_void, try pool.intern(.{ .simple = .void }));
try testing.expectEqual(Vid.false_value, try pool.intern(.{ .bool_value = false }));
try testing.expectEqual(Vid.unknown, try pool.intern(.unknown));
try testing.expectEqual(static_count, pool.count());
}
test "an uncommon integer width interns dynamically and dedups" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
const u7_key: Key = .{ .int_type = .{ .signedness = .unsigned, .bits = 7 } };
const first = try pool.intern(u7_key);
try testing.expect(@intFromEnum(first) >= static_count);
try testing.expectEqual(first, try pool.intern(u7_key));
// Same width, other signedness is a distinct type.
const signed_7 = try pool.intern(.{ .int_type = .{ .signedness = .signed, .bits = 7 } });
try testing.expect(first != signed_7);
}
test "the same composite type interned twice is the same Vid" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
// ?u8 — once.
const opt_u8 = try pool.intern(.{ .optional = .type_u8 });
try testing.expectEqual(opt_u8, try pool.intern(.{ .optional = .type_u8 }));
// []u8 / *u32 — each once, however often spelled.
const slice_u8 = try pool.intern(.{ .ptr = .{ .size = .slice, .elem = .type_u8 } });
try testing.expectEqual(slice_u8, try pool.intern(.{ .ptr = .{ .size = .slice, .elem = .type_u8 } }));
const ptr_u32 = try pool.intern(.{ .ptr = .{ .size = .one, .elem = .type_u32 } });
try testing.expectEqual(ptr_u32, try pool.intern(.{ .ptr = .{ .size = .one, .elem = .type_u32 } }));
// Nesting composes on child Vids: ?[]u8 dedups through its child.
const opt_slice = try pool.intern(.{ .optional = slice_u8 });
try testing.expectEqual(opt_slice, try pool.intern(.{ .optional = slice_u8 }));
}
test "distinct composite types get distinct Vids" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
const opt_u8 = try pool.intern(.{ .optional = .type_u8 });
const opt_u16 = try pool.intern(.{ .optional = .type_u16 });
try testing.expect(opt_u8 != opt_u16);
// []u8 vs []mut u8 vs [*]u8 — qualifier and size each split identity.
const slice_const = try pool.intern(.{ .ptr = .{ .size = .slice, .elem = .type_u8 } });
const slice_mut = try pool.intern(.{ .ptr = .{ .size = .slice, .is_mut = true, .elem = .type_u8 } });
const many = try pool.intern(.{ .ptr = .{ .size = .many, .elem = .type_u8 } });
try testing.expect(slice_const != slice_mut);
try testing.expect(slice_const != many);
// [:0]u8 vs []u8 — a sentinel splits identity.
const zero = try pool.intern(.{ .int = 0 });
const slice_z = try pool.intern(.{ .ptr = .{ .size = .slice, .sentinel = zero, .elem = .type_u8 } });
try testing.expect(slice_z != slice_const);
try testing.expectEqual(slice_z, try pool.intern(.{ .ptr = .{ .size = .slice, .sentinel = zero, .elem = .type_u8 } }));
}
test "array types are structural over the length value" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
const four = try pool.intern(.{ .int = 4 });
const eight = try pool.intern(.{ .int = 8 });
const arr4 = try pool.intern(.{ .array = .{ .len = four, .elem = .type_u8 } });
const arr8 = try pool.intern(.{ .array = .{ .len = eight, .elem = .type_u8 } });
try testing.expect(arr4 != arr8);
try testing.expectEqual(arr4, try pool.intern(.{ .array = .{ .len = four, .elem = .type_u8 } }));
}
test "error-union and function types dedup; an inferred set is its own identity" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
// !void (inferred set) vs E!void — distinct; each dedups.
const inferred = try pool.intern(.{ .error_union = .{ .set = null, .payload = .type_void } });
try testing.expectEqual(inferred, try pool.intern(.{ .error_union = .{ .set = null, .payload = .type_void } }));
const some_set = try pool.intern(.unknown); // a stand-in set Vid is enough for identity
const explicit = try pool.intern(.{ .error_union = .{ .set = some_set, .payload = .type_void } });
try testing.expect(inferred != explicit);
// fn(u8) u8 dedups even when the caller's parameter slice is a temporary.
var params = [_]Vid{.type_u8};
const f1 = try pool.intern(.{ .fn_type = .{ .params = ¶ms, .ret = .type_u8 } });
params[0] = .type_u16; // clobber the caller's buffer …
var params2 = [_]Vid{.type_u8};
const f2 = try pool.intern(.{ .fn_type = .{ .params = ¶ms2, .ret = .type_u8 } });
try testing.expectEqual(f1, f2); // … the pool kept its own copy
const f3 = try pool.intern(.{ .fn_type = .{ .params = ¶ms, .ret = .type_u8 } });
try testing.expect(f1 != f3); // fn(u16) u8 is a different type
}
test "tuple types dedup element-wise and differ by arity and order" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
const ab = try pool.intern(.{ .tuple = &.{ .type_u8, .type_bool } });
try testing.expectEqual(ab, try pool.intern(.{ .tuple = &.{ .type_u8, .type_bool } }));
const ba = try pool.intern(.{ .tuple = &.{ .type_bool, .type_u8 } });
const abc = try pool.intern(.{ .tuple = &.{ .type_u8, .type_bool, .type_void } });
try testing.expect(ab != ba);
try testing.expect(ab != abc);
}
test "container identity is nominal — the defining node, not the shape" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
// Two textually identical (here: both empty) struct definitions are two
// distinct nodes, hence two distinct types; the same node twice is one.
// The nodes are arena-allocated, as the parser allocates real ones —
// stack/const locals could share storage and fake a collision.
const node_a = try a.allocator().create(ast.StructDef);
node_a.* = .{ .fields = &.{}, .decls = &.{} };
const node_b = try a.allocator().create(ast.StructDef);
node_b.* = .{ .fields = &.{}, .decls = &.{} };
const t_a = try pool.intern(.{ .container = .{ .struct_type = node_a } });
const t_b = try pool.intern(.{ .container = .{ .struct_type = node_b } });
try testing.expect(t_a != t_b);
try testing.expectEqual(t_a, try pool.intern(.{ .container = .{ .struct_type = node_a } }));
// The container kind is part of identity, independent of the address.
const e = try a.allocator().create(ast.EnumDef);
e.* = .{ .tag_type = null, .variants = &.{}, .decls = &.{} };
const t_e = try pool.intern(.{ .container = .{ .enum_type = e } });
try testing.expectEqual(t_e, try pool.intern(.{ .container = .{ .enum_type = e } }));
try testing.expect(t_e != t_a);
}
test "int values dedup by value; strings by content" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
const n42 = try pool.intern(.{ .int = 42 });
try testing.expectEqual(n42, try pool.intern(.{ .int = 42 }));
const n43 = try pool.intern(.{ .int = 43 });
try testing.expect(n42 != n43);
const neg = try pool.intern(.{ .int = -42 });
try testing.expect(n42 != neg);
// Two equal strings at different addresses are one value.
const src1 = "hello";
const src2 = [_]u8{ 'h', 'e', 'l', 'l', 'o' };
const s1 = try pool.intern(.{ .string = src1 });
const s2 = try pool.intern(.{ .string = &src2 });
try testing.expectEqual(s1, s2);
const s3 = try pool.intern(.{ .string = "world" });
try testing.expect(s1 != s3);
}
test "a dynamic entry round-trips through get" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try testPool(&a);
const opt = try pool.intern(.{ .optional = .type_bool });
switch (pool.get(opt)) {
.optional => |child| try testing.expectEqual(Vid.type_bool, child),
else => return error.WrongKeyShape,
}
const n = try pool.intern(.{ .int = 7 });
switch (pool.get(n)) {
.int => |v| try testing.expectEqual(@as(i128, 7), v),
else => return error.WrongKeyShape,
}
}
// --- evaluator tests ------------------------------------------------------
const Parser = @import("parser.zig").Parser;
// Parse `src` and run the evaluator over it; the pool and evaluator are
// arena-backed by `a` and inspectable afterwards.
fn evalSrc(a: *std.heap.ArenaAllocator, pool: *Pool, src: []const u8) !Evaluator {
const arena = a.allocator();
var p = Parser.init(arena, src);
const program = try p.parseProgram();
var ev = Evaluator.init(arena, pool);
try ev.run(program);
return ev;
}
// Assert the file-scope constant `name` folded to the integer `expected`.
fn expectConstInt(src: []const u8, name: []const u8, expected: i128) !void {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool, src);
const v = ev.lookup(name) orelse return error.ConstNotRecorded;
switch (pool.get(v)) {
.int => |n| try testing.expectEqual(expected, n),
else => return error.NotAnInt,
}
}
// Assert the file-scope constant `name` evaluated to exactly `expected`.
fn expectConstVid(src: []const u8, name: []const u8, expected: Vid) !void {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool, src);
const v = ev.lookup(name) orelse return error.ConstNotRecorded;
try testing.expectEqual(expected, v);
}
// Assert evaluation of `src` produced no diagnostics.
fn expectEvalClean(src: []const u8) !void {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool, src);
if (ev.diags.items.len != 0) {
std.debug.print("expected a clean evaluation, got {d} diagnostic(s):\n", .{ev.diags.items.len});
for (ev.diags.items) |d| std.debug.print(" {s}\n", .{d.msg});
return error.UnexpectedDiag;
}
}
// Assert evaluation of `src` produced exactly `n` diagnostics whose message
// contains `frag`.
fn expectEvalDiags(src: []const u8, frag: []const u8, n: usize) !void {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool, src);
var hits: usize = 0;
for (ev.diags.items) |d| {
if (std.mem.indexOf(u8, d.msg, frag) != null) hits += 1;
}
try testing.expectEqual(n, hits);
}
test "integer literals and arithmetic fold" {
try expectConstInt("const N = 1 + 2 * 3", "N", 7);
try expectConstInt("const H = 0xFF", "H", 255);
try expectConstInt("const B = 0b101", "B", 5);
try expectConstInt("const Neg = -42", "Neg", -42);
try expectConstInt("const G = (1 + 2) * 3", "G", 9);
try expectConstInt("const Q = 7 / 2", "Q", 3);
try expectConstInt("const R = 7 % 2", "R", 1);
}
test "a reference to an already-evaluated constant folds through" {
try expectConstInt(
\\const A = 2
\\const B = A * 21
, "B", 42);
}
test "a forward reference degrades to unknown, silently" {
const src =
\\const B = A * 21
\\const A = 2
;
try expectConstVid(src, "B", .unknown);
try expectEvalClean(src);
}
test "comparisons and boolean logic fold" {
try expectConstVid("const T = 1 < 2", "T", .true_value);
try expectConstVid("const F = 3 == 4", "F", .false_value);
try expectConstVid("const N = !true", "N", .false_value);
try expectConstVid("const A = true && false", "A", .false_value);
try expectConstVid("const O = false || true", "O", .true_value);
try expectConstVid("const E = true == true", "E", .true_value);
// The left side decides where it can, even with an unknown right side.
try expectConstVid(
\\fn f(x bool) bool {
\\ return x
\\}
\\const D = false && f(true)
, "D", .false_value);
}
test "bitwise operators and shifts fold" {
try expectConstInt("const M = 0xF0 | 0x0F", "M", 255);
try expectConstInt("const A = 0xFF & 0x0F", "A", 15);
try expectConstInt("const X = 0xFF ^ 0x0F", "X", 0xF0);
try expectConstInt("const S = 1 << 10", "S", 1024);
try expectConstInt("const D = 256 >> 4", "D", 16);
}
test "string constants intern by content" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool,
\\const A = "flash"
\\const B = "flash"
\\const C = "other"
);
const va = ev.lookup("A") orelse return error.ConstNotRecorded;
const vb = ev.lookup("B") orelse return error.ConstNotRecorded;
const vc = ev.lookup("C") orelse return error.ConstNotRecorded;
try testing.expectEqual(va, vb);
try testing.expect(va != vc);
}
test "builtin type names and type aliases evaluate to type Vids" {
try expectConstVid("const T = u8", "T", .type_u8);
try expectConstVid("const B = bool", "B", .type_bool);
// An alias of an alias lands on the same Vid.
try expectConstVid(
\\const T = u8
\\const U = T
, "U", .type_u8);
}
test "composite type expressions intern structurally through aliases" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool,
\\const T = u8
\\const O1 = ?u8
\\const O2 = ?T
\\const S = []u8
\\const F = *fn(u8) u8
);
// `?u8` and `?T` (T = u8) are the same type — one Vid.
const o1 = ev.lookup("O1") orelse return error.ConstNotRecorded;
const o2 = ev.lookup("O2") orelse return error.ConstNotRecorded;
try testing.expectEqual(o1, o2);
switch (pool.get(o1)) {
.optional => |child| try testing.expectEqual(Vid.type_u8, child),
else => return error.WrongKeyShape,
}
// `[]u8` is the slice key on u8.
const s = ev.lookup("S") orelse return error.ConstNotRecorded;
switch (pool.get(s)) {
.ptr => |p| {
try testing.expectEqual(PtrSize.slice, p.size);
try testing.expectEqual(Vid.type_u8, p.elem);
},
else => return error.WrongKeyShape,
}
// `*fn(u8) u8` is a one-pointer to the fn type.
const f = ev.lookup("F") orelse return error.ConstNotRecorded;
switch (pool.get(f)) {
.ptr => |p| switch (pool.get(p.elem)) {
.fn_type => |ft| {
try testing.expectEqual(@as(usize, 1), ft.params.len);
try testing.expectEqual(Vid.type_u8, ft.ret);
},
else => return error.WrongKeyShape,
},
else => return error.WrongKeyShape,
}
}
test "a container definition evaluates to a nominal type" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool,
\\const W = struct {
\\ fd i32,
\\}
\\const K = enum { a, b }
);
const w = ev.lookup("W") orelse return error.ConstNotRecorded;
switch (pool.get(w)) {
.container => |c| switch (c) {
.struct_type => {},
else => return error.WrongContainerKind,
},
else => return error.WrongKeyShape,
}
const k = ev.lookup("K") orelse return error.ConstNotRecorded;
try testing.expect(w != k);
}
test "a known if-expression condition selects one arm and prunes the other" {
// The taken arm folds; the dead arm holds a division by zero that must
// NOT be diagnosed — downstream never analyzes it either.
const src = "const X = if (true) 1 else 2 / 0";
try expectConstInt(src, "X", 1);
try expectEvalClean(src);
// With an unknown condition both arms are evaluated, so the definite
// error in either arm IS found.
try expectEvalDiags(
\\fn f(c bool) usize {
\\ x := if (c) 1 else 2 / 0
\\ return x
\\}
, "division by zero", 1);
}
test "division and remainder by a known zero are definite errors" {
try expectEvalDiags("const D = 1 / 0", "division by zero", 1);
try expectEvalDiags("const M = 5 % 0", "division by zero", 1);
// A known-zero divisor under an unknown numerator is still definite.
try expectEvalDiags(
\\fn f(n usize) usize {
\\ return n / 0
\\}
, "division by zero", 1);
// A var's initializer is evaluated for definite errors too.
try expectEvalDiags("var V = 1 / 0", "division by zero", 1);
}
test "'||' on type operands is a definite error" {
// The motivating shape: two named error sets, merged Zig-style.
try expectEvalDiags(
\\const AError = error{Bad}
\\const BError = error{Worse}
\\const Both = AError || BError
, "cannot merge error sets", 1);
// Inline error-set literals and any other type operand are the same
// mistake; one side being a type is enough.
try expectEvalDiags("const Both = error{A} || error{B}", "cannot merge error sets", 1);
try expectEvalDiags("const T = u8 || u16", "cannot merge error sets", 1);
// Boolean `||` is untouched.
try expectEvalClean("const B = true || false");
}
test "an error-set definition evaluates to a nominal type" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool,
\\const AError = error{Bad}
\\const BError = error{Bad}
);
const ae = ev.lookup("AError") orelse return error.ConstNotRecorded;
switch (pool.get(ae)) {
.container => |c| switch (c) {
.error_set_type => {},
else => return error.WrongContainerKind,
},
else => return error.WrongKeyShape,
}
// Identity is the defining node: a textually identical set is a
// distinct type, exactly as containers behave.
const be = ev.lookup("BError") orelse return error.ConstNotRecorded;
try testing.expect(ae != be);
}
test "out-of-reach folds degrade to unknown without a diagnostic" {
// i128 overflow — downstream comptime ints are arbitrary-precision, so
// this is a boundary, never an error.
const overflow = "const Big = 170141183460469231731687303715884105727 + 1";
try expectConstVid(overflow, "Big", .unknown);
try expectEvalClean(overflow);
// Signed division rounding is gated behind dedicated builtins downstream.
try expectEvalClean("const Q = -7 / 2");
try expectConstVid("const Q = -7 / 2", "Q", .unknown);
// Floats, #-builtins, and member access are out of boundary.
try expectConstVid("const F = 1.5", "F", .unknown);
try expectEvalClean("const F = 1.5");
try expectConstVid("const C = #sizeOf(u8)", "C", .unknown);
try expectEvalClean("const C = #sizeOf(u8)");
// An oversized shift is legal on downstream comptime ints — degrade.
try expectConstVid("const S = 1 << 200", "S", .unknown);
try expectEvalClean("const S = 1 << 200");
}
test "definite errors inside bodies and containers are found" {
// A local constant inside a function body.
try expectEvalDiags(
\\fn f() usize {
\\ d := 1 / 0
\\ return d
\\}
, "division by zero", 1);
// Inside a defer and a known-true if body.
try expectEvalDiags(
\\fn f() {
\\ if true {
\\ _ = 1 / 0
\\ }
\\}
, "division by zero", 1);
// A known-FALSE if statement prunes its body, as downstream does.
try expectEvalClean(
\\fn f() {
\\ if false {
\\ _ = 1 / 0
\\ }
\\}
);
// A container-associated constant and a method body are both walked.
try expectEvalDiags(
\\const W = struct {
\\ fd i32,
\\
\\ const Z = 1 / 0
\\
\\ fn m(self W) usize {
\\ return 2 / 0
\\ }
\\}
, "division by zero", 2);
}
test "a generic application with wrong arity is a definite error" {
// In value position …
try expectEvalDiags(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\const B = Box(u8, u8)
, "generic 'Box' expects 1 argument, found 2", 1);
// … and in type position, through a parameter annotation.
try expectEvalDiags(
\\fn Pair(comptime A type, comptime B type) type {
\\ return A
\\}
\\fn f(x Pair(u8)) void {
\\ _ = x
\\}
, "generic 'Pair' expects 2 arguments, found 1", 1);
}
test "a generic declared later in the file is checked at an earlier application" {
try expectEvalDiags(
\\const B = Box(u8, u8)
\\fn Box(comptime T type) type {
\\ return T
\\}
, "expects 1 argument, found 2", 1);
}
test "a type parameter wants a type argument; a value parameter wants a value" {
try expectEvalDiags(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\const B = Box(5)
, "argument 1 to generic 'Box' expects a type, found a value", 1);
try expectEvalDiags(
\\fn Ring(comptime n usize) type {
\\ return u8
\\}
\\const R = Ring(u8)
, "argument 1 to generic 'Ring' expects a value, found a type", 1);
}
test "a parameter kind resolves through a file-scope type alias" {
// `MyT` aliases `type` itself, so `T` wants a type argument.
try expectEvalDiags(
\\const MyT = type
\\fn G(comptime T MyT) type {
\\ return T
\\}
\\const B = G(5)
, "expects a type, found a value", 1);
}
test "well-formed generic applications stay silent" {
try expectEvalClean(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\fn Ring(comptime n usize) type {
\\ return u8
\\}
\\const B = Box(u8)
\\const C = Box([]u8)
\\const R = Ring(64)
\\
\\fn f(x Box(u8)) Box(u8) {
\\ return x
\\}
\\
\\const S = struct {
\\ b Box(u8),
\\}
);
}
test "unknown arguments and unresolvable parameter kinds stay silent" {
// A runtime argument is out of reach — never wrong.
try expectEvalClean(
\\fn Ring(comptime n usize) type {
\\ return u8
\\}
\\fn f(n usize) void {
\\ const R = Ring(n)
\\ _ = R
\\}
);
// A parameter whose type names another parameter is unresolvable —
// unchecked, so a value rides where the downstream compiler decides.
try expectEvalClean(
\\fn Wrap(comptime T type, x T) type {
\\ return T
\\}
\\const W = Wrap(u8, 5)
);
// Parameter-type resolution cycles never recurse: the re-entered
// resolution degrades to unchecked. Instantiation then breaks the
// benign half of the cycle — `A(u8)` evaluates to `u8`, so B's
// parameter kind resolves after all, and the type argument in A's own
// signature is a definite kind error (rejected downstream too) —
// reported once, by the loud signature walk.
try expectEvalDiags(
\\fn A(comptime x B(u8)) type {
\\ return u8
\\}
\\fn B(comptime x A(u8)) type {
\\ return u8
\\}
\\const C = A(5)
, "argument 1 to generic 'B' expects a value, found a type", 1);
}
test "out-of-scope applications are not checked" {
// A locally bound name is not the file-level generic (the binding checks
// own the shadowing rules; this walk only mirrors the visibility).
try expectEvalClean(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\fn f(Box fn(u8) u8) u8 {
\\ return Box(1)
\\}
);
// A dotted (imported) generic name is out of reach.
try expectEvalClean(
\\use pkg
\\
\\fn f(x pkg.List(u8, u8, u8)) void {
\\ _ = x
\\}
);
// An ordinary function's call arity is not this walk's business.
try expectEvalClean(
\\fn add(a u8, b u8) u8 {
\\ return a + b
\\}
\\const S = add(1)
);
}
test "generic applications in annotations are checked" {
// A binding's type annotation …
try expectEvalDiags(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\fn f() void {
\\ var x Box(u8, u8) = undefined
\\ _ = x
\\}
, "expects 1 argument, found 2", 1);
// … a container field's type …
try expectEvalDiags(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\const S = struct {
\\ b Box(u8, u8),
\\}
, "expects 1 argument, found 2", 1);
// … and a return type.
try expectEvalDiags(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\fn f() Box(5) {
\\ return undefined
\\}
, "expects a type, found a value", 1);
}
test "a definite error inside an application's argument is still found" {
try expectEvalDiags(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\const B = Box(1 / 0, u8)
, "division by zero", 1);
}
test "the same generic over the same arguments is one instance; distinct arguments split" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool,
\\fn List(comptime T type) type {
\\ return struct {
\\ item T,
\\ }
\\}
\\const A = List(u8)
\\const B = List(u8)
\\const C = List(u16)
);
const va = ev.lookup("A") orelse return error.ConstNotRecorded;
const vb = ev.lookup("B") orelse return error.ConstNotRecorded;
const vc = ev.lookup("C") orelse return error.ConstNotRecorded;
try testing.expectEqual(va, vb);
try testing.expect(va != vc);
// The instance is a nominal type of its own — the instance key, not the
// body's container node (which would collapse every argument list).
switch (pool.get(va)) {
.instance => |inst| try testing.expectEqual(@as(usize, 1), inst.args.len),
else => return error.WrongKeyShape,
}
}
test "a type-expression body evaluates to the instance's result type" {
// `return T` denotes the argument itself.
try expectConstVid(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\const B = Box(u8)
, "B", .type_u8);
// Parameters bind positionally.
try expectConstVid(
\\fn Pick(comptime A type, comptime B type) type {
\\ return B
\\}
\\const P = Pick(u8, bool)
, "P", .type_bool);
// `return ?T` lands on the same structural Vid as a spelled `?u8`.
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool,
\\fn Opt(comptime T type) type {
\\ return ?T
\\}
\\const A = Opt(u8)
\\const B = ?u8
);
const va = ev.lookup("A") orelse return error.ConstNotRecorded;
const vb = ev.lookup("B") orelse return error.ConstNotRecorded;
try testing.expectEqual(vb, va);
}
test "an instance type is a known type to later kind checks" {
// `B` folds to the type `Box(u8)` denotes, so passing it where a value
// parameter is declared is now a definite kind error.
try expectEvalDiags(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\fn Ring(comptime n usize) type {
\\ return u8
\\}
\\const B = Box(u8)
\\const R = Ring(B)
, "argument 1 to generic 'Ring' expects a value, found a type", 1);
// A container instance rides as a type argument.
try expectEvalClean(
\\fn List(comptime T type) type {
\\ return struct {
\\ item T,
\\ }
\\}
\\fn Box(comptime T type) type {
\\ return T
\\}
\\const L = List(u8)
\\const B = Box(L)
);
}
test "bodies that are not a single return stay unknown, silently" {
// Two statements.
const two =
\\fn Two(comptime T type) type {
\\ const U = T
\\ return U
\\}
\\const A = Two(u8)
;
try expectConstVid(two, "A", .unknown);
try expectEvalClean(two);
// A single return of a non-type result degrades too — no type-mismatch
// diagnostics here, that stays downstream's call.
const val =
\\fn N(comptime T type) type {
\\ return 5
\\}
\\const A = N(u8)
;
try expectConstVid(val, "A", .unknown);
try expectEvalClean(val);
}
test "an unknown argument is never instantiated" {
// A forward reference is unknown at the application — the instance is
// not interned, the result stays unknown, nothing is reported.
const src =
\\const B = Box(Later)
\\const Later = u8
\\fn Box(comptime T type) type {
\\ return T
\\}
;
try expectConstVid(src, "B", .unknown);
try expectEvalClean(src);
}
test "an alias of a generic is a boundary, not an application site" {
// `L` is env-bound (to unknown), so `L(u8)` is no application — silent.
const src =
\\fn List(comptime T type) type {
\\ return struct {
\\ item T,
\\ }
\\}
\\const L = List
\\const X = L(u8)
;
try expectConstVid(src, "X", .unknown);
try expectEvalClean(src);
}
test "recursive instantiation is capped with one targeted diagnostic" {
// Direct self-application — the same key re-enters until the cap.
try expectEvalDiags(
\\fn A(comptime T type) type {
\\ return A(T)
\\}
\\const X = A(u8)
, "generic 'A' exceeds the instantiation depth limit (64)", 1);
// Growing-argument recursion makes a fresh key per level — also capped.
try expectEvalDiags(
\\fn G(comptime T type) type {
\\ return G(?T)
\\}
\\const X = G(u8)
, "generic 'G' exceeds the instantiation depth limit (64)", 1);
}
test "the instantiation budget caps a run; memoized hits are free" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
const arena = a.allocator();
// Three distinct instances against a budget of two — the third is over.
var pool = try Pool.init(arena);
var p = Parser.init(arena,
\\fn Box(comptime T type) type {
\\ return T
\\}
\\const A = Box(u8)
\\const B = Box(u16)
\\const C = Box(u32)
);
var ev = Evaluator.init(arena, &pool);
ev.inst_budget = 2;
try ev.run(try p.parseProgram());
try testing.expectEqual(@as(usize, 1), ev.diags.items.len);
try testing.expect(std.mem.indexOf(u8, ev.diags.items[0].msg, "exceeds the instantiation budget (2)") != null);
// The same application three times costs one instantiation — well
// inside the same budget, and every alias lands on the same result.
var pool2 = try Pool.init(arena);
var p2 = Parser.init(arena,
\\fn Box(comptime T type) type {
\\ return T
\\}
\\const A = Box(u8)
\\const B = Box(u8)
\\const C = Box(u8)
);
var ev2 = Evaluator.init(arena, &pool2);
ev2.inst_budget = 2;
try ev2.run(try p2.parseProgram());
try testing.expectEqual(@as(usize, 0), ev2.diags.items.len);
try testing.expectEqual(ev2.lookup("A"), ev2.lookup("C"));
}
test "a definite error written in a generic's body reports once despite instantiation" {
// The loud body walk owns the diagnostic; the (quiet) instance
// evaluation of `A(u8)` must not duplicate it.
try expectEvalDiags(
\\fn Box(comptime T type) type {
\\ return T
\\}
\\fn A(comptime T type) type {
\\ return Box(T, T)
\\}
\\const X = A(u8)
, "expects 1 argument, found 2", 1);
}
test "local constants fold and stay scoped to their block" {
var a = std.heap.ArenaAllocator.init(testing.allocator);
defer a.deinit();
var pool = try Pool.init(a.allocator());
const ev = try evalSrc(&a, &pool,
\\fn f() usize {
\\ const k = 6 * 7
\\ return k
\\}
);
// The function frame was popped after the walk — nothing leaks to the
// file scope.
try testing.expectEqual(@as(?Vid, null), ev.lookup("k"));
try expectEvalClean(
\\fn f() usize {
\\ const k = 6 * 7
\\ return k
\\}
);
}