clover's git

ix

1	//! Semantic Analysis converts `Hir` to `Air` by stepping over every instruction
2	//! and evaluating comptime values or emitting runtime instructions.
3	//!
4	//! Designed as a nonrecursive state machine, `Sema` can be paused when an
5	//! unfinished dependency is encountered, allowing the thread to work on other
6	//! analysis jobs.
7
8	comp: *Comp,
9	ip: *InternPool,
10	gpa: Allocator,
11	arena_state: std.heap.ArenaAllocator,
12	/// The thing being analyzed.
13	/// When this is .decl, we are producing a `Value`
14	owner: AnalysisUnit,
15
16	generate_safety_checks: bool = true,
17
18	/// The namespace index that is used for declaration lookups
19	ns_index: Namespace.Index,
20	/// Non-owning copy
21	hir: Hir,
22	/// The file that .hir is from
23	file: *File,
24
25	/// All errors and warnings from this decl
26	report: Report.Builder,
27	/// Map of `Hir` instructions to their resulting `Air` Ref
28	inst_map: InstMap,
29
30	/// `null` when not analyzing function bodies
31	func: ?Function,
32
33	frame: Frame,
34	frame_stack: DynamicArray(Frame),
35
36	/// List of `*Sema` that is waiting on this analysis to complete.
37	/// Backed by `comp.gpa`
38	blocked_semas: DynamicArray(*Sema),
39
40	/// Scratch memory for temporary allocations.
41	/// Block contents are appended for marks.
42	scratch: core.U32Stack,
43
44	/// To validate that a pointer to `Sema` is not corrupted.
45	magic: Magic align(1),
46
47	instruction_step_lock: std.debug.SafetyLock,
48
49	pub const Error = error{
50	/// The analysis of this branch or declaration has failed.
51	/// At least one error will exist in `.report`
52	AnalysisFail,
53	/// There is a dependency on another declaration that we are waiting on.
54	Interrupt,
55	/// Must invoke garbage collection?
56	TooManyValues,
57	OutOfMemory,
58	};
59
60	pub fn init(
61	s: *Sema,
62	comp: *Comp,
63	file: *File,
64	hir: Hir,
65	owner: AnalysisUnit,
66	ns_index: Namespace.Index,
67	arena_state: std.heap.ArenaAllocator,
68	) Allocator.Error!void {
69	const t = tracer.trace(@src());
70	defer t.end();
71
72	assert(comp.intern_pool.items.len > 0); // did not initialize intern pool
73	_ = comp.intern_pool.items.bytes[0]; // segfault if intern pool is undefined memory
74
75	s.* = .{
76	.comp = comp,
77	.ip = &comp.intern_pool,
78	.gpa = comp.gpa,
79
80	.arena_state = arena_state,
81	.owner = owner,
82	.ns_index = ns_index,
83	.hir = hir,
84	.file = file,
85
86	.report = .init(comp.gpa),
87	.inst_map = undefined,
88	.func = switch (owner.kind) {
89	.decl => null,
90	.func => .empty,
91	},
92	.frame = undefined,
93	.frame_stack = .empty,
94	.blocked_semas = .empty,
95	.scratch = .empty,
96	.magic = .valid,
97	.instruction_step_lock = .{},
98	};
99
100	const first_instruction, const count = switch (owner.unwrap()) {
101	.decl => |decl| data: {
102	const decl_inst = s.ip.declPtr(decl).teg_decl_index.resolve(s.ip);
103	const teg_decl: Hir.Decl = hir.instPayload(.declaration, decl_inst);
104	break :data .{ decl_inst, teg_decl.instruction_count };
105	},
106	.func => |value| data: {
107	const func_inst = value.toKey(s.ip).func.teg_body_inst.get(s.ip);
108	const func: Hir.Func = hir.instPayload(.func, func_inst.inst);
109	break :data .{ func.body, func.instruction_count };
110	},
111	};
112
113	s.inst_map = try .init(s.arena(), first_instruction, count);
114
115	const block_index = switch (owner.unwrap()) {
116	.decl => switch (s.hir.declData(first_instruction).body.decode()) {
117	.index => |index| index,
118	.value => unreachable, // Sema must not be created for a static value
119	},
120	.func => first_instruction,
121	};
122	s.frame = Frame.initFromBlock(
123	s,
124	block_index,
125	switch (owner.kind) {
126	.decl => .compile_time,
127	.func => .run_time,
128	},
129	.none,
130	);
131
132	if (owner.kind == .func) {
133	assert(try s.addIndexUntracked(.block, undefined) == .main_block);
134	}
135	}
136
137	/// Does not free the allocated pointer itself. Releases the arena to be used for another analysis.
138	pub fn deinit(sema: *Sema, arena_reset_mode: std.heap.ArenaAllocator.ResetMode) std.heap.ArenaAllocator {
139	defer sema.* = undefined;
140	assert(sema.magic == .valid);
141
142	sema.report.deinit();
143	sema.blocked_semas.deinit(sema.gpa);
144
145	if (sema.func) |*func| {
146	func.deinit(sema.gpa);
147	}
148
149	_ = sema.arena_state.reset(arena_reset_mode);
150	return sema.arena_state;
151	}
152
153	const AnalysisMode = enum {
154	/// Runtime operands are allowed, and emit Air instructions on `sema.func`.
155	run_time,
156	/// Any attempt to emit instructions turn into analysis errors, the result
157	/// is guanteed to be a `Value`.
158	///
159	/// Compile time analysis can result in a function who's body executes at
160	/// run time, but that body is not queued for analysis until .run_time
161	/// analysis requires the function.
162	compile_time,
163	};
164
165	const Frame = struct {
166	ip: [*]const Hir.Inst.Index,
167	instructions_left: if (runtime_safety) usize else void,
168
169	mode: AnalysisMode,
170	block_index: Hir.Inst.Index,
171	mark_index: u32,
172	data: Data,
173
174	const Data = union {
175	pub const none: Data = .{ .undefined = {} };
176
177	undefined: void,
178	conditional: Conditional,
179	func: Func,
180	};
181
182	const Conditional = enum {
183	comptime_condition,
184	runtime_yes,
185	runtime_no,
186	};
187
188	const Func = union(enum) {
189	return_type,
190	argument: u16,
191	};
192
193	fn initFromBlock(s: *Sema, block_index: Hir.Inst.Index, mode: AnalysisMode, data: Data) Frame {
194	switch (s.hir.instTag(block_index)) {
195	else => unreachable, // not a block
196	.block, .@"comptime" => {},
197	}
198	const list = s.hir.instEncodedData(block_index)
199	.decodeUnsafe(Hir.PlNode(Hir.IndexList), s.hir.instTag(block_index))
200	.extra_index.get(&s.hir)
201	.slice(&s.hir);
202	return .{
203	.ip = list[0..].ptr,
204	.instructions_left = if (runtime_safety) list.len,
205	.block_index = block_index,
206	.data = data,
207	.mode = mode,
208	.mark_index = @intCast(s.scratch.mark().index),
209	};
210	}
211
212	fn currentIndex(frame: *const Frame) Hir.Inst.Index {
213	// validate the pointer is correct
214	if (runtime_safety) {
215	const s: *const Sema = @fieldParentPtr("frame", frame);
216	assert(s.magic == .valid);
217	const extra = s.hir.extra.list.items;
218	assert(@intFromPtr(frame.ip) > @intFromPtr(extra.ptr) and
219	@intFromPtr(frame.ip) <= @intFromPtr(&extra.ptr[extra.len - 1]));
220	}
221
222	return frame.ip[0];
223	}
224
225	fn currentTag(frame: *const Frame) Hir.Tag {
226	const s: *const Sema = @fieldParentPtr("frame", frame);
227	assert(s.magic == .valid);
228	return s.hir.instTag(frame.currentIndex());
229	}
230
231	fn currentData(frame: *const Frame, comptime tag: Hir.Tag) tag.Data() {
232	const s: *const Sema = @fieldParentPtr("frame", frame);
233	assert(s.magic == .valid);
234	return s.hir.instData(tag, frame.currentIndex());
235	}
236
237	fn currentPayload(frame: *const Frame, comptime tag: Hir.Tag) tag.Data().T {
238	const s: *const Sema = @fieldParentPtr("frame", frame);
239	assert(s.magic == .valid);
240	return s.hir.instPayload(tag, frame.currentIndex());
241	}
242
243	fn advance(frame: *Frame) void {
244	if (runtime_safety) {
245	frame.instructions_left -= 1;
246	assert(frame.instructions_left > 0); // block is missing a break/did not stop at break
247	}
248	frame.ip += 1;
249	}
250	};
251
252	const Function = struct {
253	instructions: std.MultiArrayList(Air.Inst),
254	extra: store.ExtraStore(.air, .@"var"),
255
256	pub const empty: Function = .{
257	.instructions = .{},
258	.extra = .empty,
259	};
260
261	pub fn finalize(func: *Function, gpa: Allocator) !Air {
262	defer func.* = .empty;
263	const air: Air = .{
264	.insts = func.instructions.slice(),
265	.extra = try func.extra.toOwnedStore(gpa),
266	};
267	return air;
268	}
269
270	pub fn deinit(func: *Function, gpa: Allocator) void {
271	defer func.* = undefined;
272	func.instructions.deinit(gpa);
273	func.extra.deinit(gpa);
274	}
275	};
276
277	/// Instead of using a HashMap, all of the information is pre-allocated, and
278	/// lookups are done by subtracing the base index. This is only possible because
279	/// all instructions are adjacent, and a declaration knows exactly how many
280	/// instructions it has.
281	const InstMap = struct {
282	items: []Air.Inst.Ref.Optional,
283	start: Hir.Inst.Index,
284	debug_traces: if (runtime_safety) []StoredTrace else void,
285
286	pub fn init(allocator: Allocator, inst_start: Hir.Inst.Index, inst_len: u32) !InstMap {
287	const insts = try allocator.alloc(Air.Inst.Ref.Optional, inst_len);
288	errdefer allocator.free(insts);
289
290	const debug_traces = if (runtime_safety)
291	try allocator.alloc(StoredTrace, inst_len);
292	errdefer if (runtime_safety)
293	allocator.free(debug_traces);
294
295	@memset(insts[0..], .none);
296	return .{
297	.items = insts,
298	.start = inst_start,
299	.debug_traces = debug_traces,
300	};
301	}
302
303	pub fn deinit(map: *InstMap, allocator: Allocator) void {
304	allocator.free(map.items);
305	if (runtime_safety)
306	allocator.free(map.debug_traces);
307	map.* = undefined;
308	}
309
310	pub fn getOrNull(map: *const InstMap, teg_code: Hir.Inst.Index) ?Air.Inst.Ref {
311	const source_i = @intFromEnum(teg_code);
312	const start_i = @intFromEnum(map.start);
313	if (assertFailed(source_i >= start_i and source_i <= start_i + map.items.len)) {
314	std.debug.panic("attempt fetching instruction %{d} which is out of range of %{d}-%{d}", .{
315	source_i,
316	start_i,
317	start_i + map.items.len,
318	});
319	}
320	return map.items[source_i - start_i].unwrap();
321	}
322
323	pub fn get(map: *const InstMap, teg_code: Hir.Inst.Index) Air.Inst.Ref {
324	return map.getOrNull(teg_code) orelse {
325	if (runtime_safety) {
326	std.debug.panic("did not analyze %{d}", .{@intFromEnum(teg_code)});
327	}
328	unreachable; // did not analyze index
329	};
330	}
331
332	pub fn add(map: *InstMap, from: Hir.Inst.Index, to: Air.Inst.Ref) void {
333	const source_i = @intFromEnum(from);
334	const start_i = @intFromEnum(map.start);
335	if (assertFailed(source_i >= start_i and source_i <= start_i + map.items.len)) {
336	std.debug.panic("attempt mapping instruction %{d} which is out of range of %{d}-%{d}", .{
337	source_i,
338	start_i,
339	start_i + map.items.len,
340	});
341	}
342	const index = source_i - start_i;
343	if (assertFailed(map.getOrNull(from) == null)) {
344	const s: *const Sema = @fieldParentPtr("inst_map", map);
345	std.debug.print("Original was added here:\n", .{});
346	std.debug.dumpStackTrace(map.debug_traces[index].trace());
347	std.debug.panic("%{d} is already mapped (to {})", .{
348	@intFromEnum(from),
349	map.get(from).dump(s.ip),
350	});
351	}
352	map.items[index] = to.toOptional();
353	if (runtime_safety)
354	map.debug_traces[index] = StoredTrace.capture(@returnAddress());
355	}
356	};
357
358	fn markInst(s: *Sema, inst: Air.Inst.Index) void {
359	const flags: *Air.Flags = &s.func.?.instructions.items(.flags)[@intFromEnum(inst)];
360	flags.uses = flags.uses.increment();
361	}
362
363	const LivenessMark = enum {
364	/// The value retrieved will not be used as the operand for another
365	/// instruction.
366	no_mark,
367	/// A Ref must be marked if it's value is used as the operand for another
368	/// Air instruction. This informs the Js backend if an expression must
369	/// generate a temporary variable.
370	marked,
371	};
372
373	fn getRef(s: *Sema, teg_ref: Hir.Inst.Ref, mark: LivenessMark) Air.Inst.Ref {
374	switch (teg_ref.decode()) {
375	.value => |value| return value.toAir(),
376	.index => |index| {
377	const air = s.inst_map.get(index);
378
379	if (mark == .marked) {
380	switch (air.decode()) {
381	.index => |i| s.markInst(i),
382	else => {},
383	}
384	}
385
386	return air;
387	},
388	}
389	}
390
391	fn getValue(s: *Sema, src: LazyNode, teg_ref: Hir.Inst.Ref) !Value {
392	switch (teg_ref.decode()) {
393	.value => |value| return value,
394	.index => |index| {
395	return s.inst_map.get(index).value() orelse
396	return s.fail(.not_comptime_known, .{ .src = src });
397	},
398	}
399	}
400
401	fn getCoercedValue(s: *Sema, src: LazyNode, teg_ref: Hir.Inst.Ref, ty: Type) !Value {
402	const any = try s.getValue(src, teg_ref);
403	return try s.coerceValue(src, any, ty);
404	}
405
406	fn getCoercedRef(s: *Sema, src: LazyNode, teg_ref: Hir.Inst.Ref, ty: Type, mark: LivenessMark) !Air.Inst.Ref {
407	const any = s.getRef(teg_ref, mark);
408	return try s.coerceRef(src, any, ty);
409	}
410
411	fn getType(s: *Sema, src: LazyNode, teg_ref: Hir.Inst.Ref) !Type {
412	return (try s.getCoercedValue(src, teg_ref, .type)).toTypeUnsafe(s.ip);
413	}
414
415	pub fn run(s: *Sema) Error!void {
416	while (true) if (try s.step()) |result| {
417	switch (s.owner.unwrap()) {
418	.decl => |decl_index| {
419	const decl = s.ip.declPtr(decl_index);
420	decl.raw_value = result.value() orelse unreachable;
421	decl.analysis = .complete;
422	},
423	.func => |value| {
424	const type_of_result = s.typeOfRef(result);
425	const air = try s.func.?.finalize(s.gpa);
426	try s.comp.jobs.writeItem(.{ .codegen_func = .{
427	.value = value,
428	.air = air,
429	} });
430
431	// If needed, update the function with its resolved return type
432	const ty = value.typeOf(s.ip);
433	const proto = ty.toUnresolvedFunctionPrototype(s.ip) orelse
434	unreachable; // must be a function type
435
436	if (proto.return_type == null) {
437	const new_type = try s.makeType(.{ .function_type = .{
438	.param_types = proto.param_types,
439	.return_type = type_of_result,
440	} });
441	value.toKey(s.ip).func.updateType(s.ip, new_type);
442	}
443	},
444	}
445	return;
446	};
447	}
448
449	pub fn step(s: *Sema) Error!?Air.Inst.Ref {
450	s.instruction_step_lock.lock(); // Semantic analysis must not be recursive
451	defer s.instruction_step_lock.unlock();
452
453	s.debug("step %{d}", .{@intFromEnum(s.frame.currentIndex())});
454
455	switch (s.frame.currentTag()) {
456	inline else => |tag| {
457	const start_index = s.frame.currentIndex();
458	const result = try s.stepInner(tag);
459	switch (InstructionKind.fromTag(tag)) {
460	.result => {
461	s.debug("-> {}", .{result.dump(s.ip)});
462
463	s.inst_map.add(s.frame.ip[0], result);
464	s.frame.advance();
465	},
466	.void => {
467	s.frame.advance();
468	},
469	.control_flow => {
470	// the instruction pointer has been moved already
471	assert(s.frame.currentIndex() != start_index); // control flow loop
472	},
473	.pop_control_flow => switch (result) {
474	.@"continue" => {
475	// the instruction pointer has been moved already
476	assert(s.frame.currentIndex() != start_index); // control flow loop
477	},
478	.stop => return s.inst_map.get(s.frame.block_index),
479	},
480	}
481	},
482	}
483
484	return null;
485	}
486
487	const InstructionKind = enum {
488	result,
489	void,
490	control_flow,
491	pop_control_flow,
492
493	pub inline fn fromTag(tag: Hir.Tag) InstructionKind {
494	return switch (tag) {
495	// these push new frames, and frame end will assign its value
496	.@"comptime",
497	.@"if",
498	.assert,
499	.block,
500	.func,
501	=> .control_flow,
502
503	// break is used to pop a frame, which has the
504	// possibility to end analysis
505	.@"break",
506	=> .pop_control_flow,
507
508	// these are statements which do not evaluate to anything (void)
509	.discard,
510	.ensure_void,
511	=> .void,
512
513	// all other instructions are single-visit, returning a value
514	else => .result,
515	};
516	}
517
518	pub fn Result(kind: InstructionKind) type {
519	return switch (kind) {
520	.result => Air.Inst.Ref,
521	.void, .control_flow => void,
522	.pop_control_flow => PopControlFlowState,
523	};
524	}
525	};
526
527	const PopControlFlowState = enum { stop, @"continue" };
528
529	fn stepInner(s: *Sema, comptime tag: Hir.Tag) Error!InstructionKind.fromTag(tag).Result() {
530	switch (tag) {
531	.block,
532	=> unreachable, // frame must already be pushed
533
534	.declaration,
535	.variable_declaration,
536	.test_declaration,
537	=> unreachable, // declarations are not analzed by Sema
538
539	.param => {
540	const param: Hir.DataNode = s.frame.currentData(.param);
541	assert(s.frame.mode == .run_time); // never emitted in a comptime block
542	assert(s.owner.kind == .func); // only emitted in function body
543	const proto = s.owner.unwrap().func.toKey(s.ip).func.ty.toUnresolvedFunctionPrototype(s.ip).?;
544	switch (param.data) {
545	std.math.maxInt(u32) => {
546	const return_type = proto.return_type orelse unreachable; // never emitted for inferred return types
547	return return_type.value().toAir();
548	},
549	else => return s.addRef(.arg, .{
550	.type = proto.param_types.at(s.ip, param.data),
551	.arg_number = param.data,
552	}),
553	}
554	},
555	.string => {
556	const string: Hir.SlicedString = s.frame.currentPayload(.string);
557	return s.makeValueAir(.{ .string = string.slice(s.hir.string_bytes) });
558	},
559	.number => {
560	const number: store.Float = s.frame.currentPayload(.number);
561	return s.makeValueAir(.{ .comptime_float = number.decode() });
562	},
563	.add,
564	.sub,
565	.mul,
566	.div,
567	.lt,
568	.gt,
569	.eq,
570	=> {
571	const bin: Hir.Bin = s.frame.currentPayload(tag);
572	const op = @field(BinaryOp, @tagName(tag));
573
574	const lhs = s.getRef(bin.lhs, .marked);
575	const left_ty = s.typeOfRef(lhs);
576
577	const rhs = s.getRef(bin.rhs, .marked);
578	const right_ty = s.typeOfRef(rhs);
579
580	const ty = try s.binTypeResolution(
581	s.frame.currentIndex(),
582	op,
583	left_ty,
584	right_ty,
585	);
586
587	const left = try s.coerceRef(s.lazyNode(.lhs), lhs, ty);
588	const right = try s.coerceRef(s.lazyNode(.rhs), rhs, ty);
589
590	if (left.kind == .value and right.kind == .value) {
591	return (try s.comptimeBin(
592	op,
593	left.decode().value,
594	right.decode().value,
595	)).toAir();
596	}
597
598	try s.ensureAtRuntime(s.lazyNode(.main_node));
599
600	return s.addRef(tag.airTag(), .{
601	.lhs = left,
602	.rhs = right,
603	});
604	},
605	.negate => {
606	const un: Hir.RefNode = s.frame.currentData(.negate);
607
608	const operand = s.getRef(un.operand, .marked);
609
610	const ty = s.typeOfRef(operand);
611	switch (ty) {
612	.numeric_literal, .int32, .float => {},
613	else => return s.fail(.un_op_mismatch, .{
614	.src = s.lazyNode(.operand),
615	.ty = ty,
616	}),
617	}
618
619	if (operand.value()) |value| {
620	return s.makeValueAir(.{
621	.comptime_float = -value.toFloat(s.ip).?,
622	});
623	}
624
625	try s.ensureAtRuntime(s.lazyNode(.operand));
626
627	return s.addRef(.negate, .{ .operand = operand });
628	},
629	.bool_not => {
630	const un: Hir.RefNode = s.frame.currentData(.bool_not);
631
632	const operand = try s.getCoercedRef(s.lazyNode(.operand), un.operand, .bool, .marked);
633
634	if (operand.value()) |value| {
635	return switch (value) {
636	.bool_false => Value.bool_true.toAir(),
637	.bool_true => Value.bool_false.toAir(),
638	else => unreachable,
639	};
640	}
641
642	try s.ensureAtRuntime(s.lazyNode(.operand));
643
644	return s.addRef(.bool_not, .{ .operand = operand });
645	},
646	.struct_decl => {
647	const node: Hir.StructDecl = s.frame.currentPayload(.struct_decl);
648
649	const scratch = try s.scratch.reserveMulti(
650	s.arena(),
651	.{ .keys = NullTerminatedString, .types = Type },
652	.{ node.field_len, node.field_len },
653	);
654	defer scratch.deinit();
655
656	// Fill the first half with keys
657	for (scratch.items(.keys), node.keys(&s.hir)) |*dest, src| {
658	dest.* = try s.ip.getOrPutString(s.gpa, src.slice(s.hir.string_bytes), .no_embedded_nulls);
659	}
660
661	// Fill the second half with coerced values.
662	for (node.types(&s.hir), 0..) |ty, i| {
663	scratch.at(.types, i).* = try s.getType(s.lazyNode(.argument(@intCast(i))), ty);
664	}
665
666	return try s.makeValueAir(.{ .struct_type = .{
667	.field_keys = try s.ip.extra.appendSlice(s.gpa, scratch.items(.keys)),
668	.field_types = try s.ip.extra.appendSlice(s.gpa, scratch.items(.types)),
669	} });
670	},
671	.discard => {
672	const operand = s.getRef(s.frame.currentData(.discard).operand, .no_mark);
673	const t = s.typeOfRef(operand);
674	if (t == .void) {
675	std.debug.print("oh no, we have a useless _ = void;\n", .{});
676	}
677	},
678	// TODO: these are disabled since calling opaque functions will return an opaque,
679	// which should be discarded, but these are going to be muted for now until some
680	// common apis are available in the standard library
681	.ensure_void => {
682	const operand = s.getRef(s.frame.currentData(.ensure_void).operand, .no_mark);
683	_ = s.typeOfRef(operand);
684	},
685	.@"extern" => {
686	const operand_ref = s.frame.currentData(.@"extern").operand;
687	const operand = try s.getCoercedValue(s.lazyNode(.operand), operand_ref, .string);
688	const str = operand.asString(s.ip).tryToNullTerminatedString(s.ip, s.gpa) catch {
689	@panic("TODO: support strings with null here");
690	};
691	return try s.makeValueAir(.{ .external_value = .{
692	.key = try s.ip.extra.appendSlice(
693	s.gpa,
694	@as([]const NullTerminatedString, &.{str}),
695	),
696	} });
697	},
698	.field => {
699	const field: Hir.Bin = s.frame.currentPayload(.field);
700	const lhs = s.getRef(field.lhs, .marked);
701	const lhs_type = s.typeOfRef(lhs);
702
703	if (lhs_type == .@"opaque") {
704	if (lhs.value()) |value| {
705	if (value.valueTag(s.ip) == .external_value) {
706	const rhs = try s.getCoercedValue(s.lazyNode(.rhs), field.rhs, .string);
707	const field_key = rhs.asString(s.ip).tryToNullTerminatedString(s.ip, s.gpa) catch {
708	@panic("TODO: support null in these strings");
709	};
710
711	const previous_key = value.toKey(s.ip).external_value.key;
712
713	const new_key = try std.mem.concat(s.arena(), NullTerminatedString, &.{
714	previous_key.get(s.ip),
715	&.{field_key},
716	});
717	defer s.arena().free(new_key);
718
719	return s.makeValueAir(.{ .external_value = .{
720	.key = try s.ip.extra.appendSlice(s.gpa, new_key),
721	} });
722	}
723	}
724
725	try s.ensureAtRuntime(s.lazyNode(.lhs));
726	return s.addRef(.field_opaque, .{
727	.lhs = lhs,
728	.rhs = s.getRef(field.rhs, .marked),
729	});
730	} else if (lhs_type.toArrayType(s.ip) != null) {
731	return try s.fieldAccessArray(lhs, lhs_type, field.rhs);
732	} else if (lhs_type.toStructType(s.ip)) |struct_type| {
733	return try s.fieldAccessStruct(lhs, lhs_type, struct_type, field.rhs);
734	} else if (lhs_type.toTupleType(s.ip)) |tuple_type| {
735	return try s.fieldAccessTuple(lhs, lhs_type, tuple_type, field.rhs);
736	}
737
738	return s.fail(.field_invalid_type, .{
739	.ty = lhs_type,
740	.src = s.lazyNode(.rhs),
741	});
742	},
743	.call => {
744	const call: Hir.Call = s.frame.currentPayload(.call);
745	const base = s.getRef(call.base, .marked);
746	const base_type = s.typeOfRef(base);
747
748	try s.ensureAtRuntime(s.lazyNode(.main_node)); // todo: comptime calls
749
750	const scratch = try s.arena().alloc(Air.Inst.Ref, call.args.len);
751	defer s.arena().free(scratch);
752	if (base_type != .@"opaque") {
753	const proto = try s.resolveFunctionPrototype(base, base_type) orelse {
754	return s.fail(.call_non_function, .{
755	.call = s.lazyNode(.operand),
756	.ty = base_type,
757	});
758	};
759
760	if (proto.param_types.len != call.args.len) {
761	// TODO: also attempt to coerce some of the params to reveal more errors.
762	return s.fail(.call_mismatch_args, .{
763	.call = s.lazyNode(.operand),
764	.actual = @intCast(call.args.len),
765	.expected = @intCast(proto.param_types.len),
766	});
767	}
768
769	// validate function args
770	for (
771	proto.param_types.get(s.ip),
772	call.args.slice(&s.hir),
773	0..,
774	) |param, arg, i| {
775	const ref = s.getRef(arg, .marked);
776	const coerced = try s.coerceRef(
777	s.lazyNode(.argument(@intCast(i))),
778	ref,
779	param,
780	);
781	scratch[i] = coerced;
782	}
783	} else {
784	for (call.args.slice(&s.hir), 0..) |arg, i| {
785	const ref = try s.ensureValueDefinedRepresentation(
786	s.lazyNode(.argument(@intCast(i))),
787	s.getRef(arg, .marked),
788	);
789	scratch[i] = ref;
790	}
791	}
792
793	const start = s.func.?.extra.list.items.len;
794	try s.func.?.extra.list.appendSlice(s.gpa, @ptrCast(scratch));
795
796	return s.addRef(.call, .{
797	.base = base,
798	.call_data = try s.func.?.extra.append(s.gpa, Air.Call.Data, .{
799	.args = .{
800	.start = @intCast(start),
801	.len = @intCast(scratch.len),
802	},
803	}),
804	});
805	},
806	.array_init => {
807	const node: Hir.ArrayInit = s.frame.currentPayload(.array_init);
808
809	assert(node.list.len > 0 or node.type_hint.unwrap() != null);
810
811	const scratch = try s.scratch.reserve(s.arena(), Air.Inst.Ref, node.list.len);
812	defer scratch.deinit();
813
814	var item_type: ?Type = if (node.type_hint.unwrap()) |ty| inferred_type: {
815	const parent_type = try s.getType(s.lazyNode(.operand), ty);
816	const array_data: InternPool.Key.ArrayType = parent_type.toArrayType(s.ip) orelse
817	// Allow the coercion to fail later.
818	break :inferred_type null;
819	break :inferred_type array_data.item_type;
820	} else null;
821
822	var is_constant = true;
823
824	for (node.list.slice(&s.hir), 0..) |item_teg_ref, i| {
825	const item = s.getRef(item_teg_ref, .marked);
826	const coerced = if (item_type) |ty|
827	try s.coerceRef(s.lazyNode(.argument(@intCast(i))), item, ty)
828	else brk: {
829	item_type = s.typeOfRef(item);
830	break :brk item;
831	};
832
833	if (coerced.kind == .index) is_constant = false;
834
835	scratch.at(i).* = coerced;
836	}
837
838	const ty = try s.makeType(.{ .array_type = .{
839	.item_type = item_type orelse unreachable,
840	} });
841
842	if (is_constant) {
843	// Convert all items in storage into a Value type
844	const result_storage = scratch.sliceReinterpret(Value);
845	for (scratch.slice(), scratch.sliceReinterpret(Value)) |ref, *value| {
846	value.* = ref.decode().value;
847	}
848	return try s.makeValueAir(.{
849	.array_value = .{
850	.type = ty,
851	// TODO: do not clone memory here
852	.items = try s.ip.extra.appendSlice(s.gpa, result_storage),
853	},
854	});
855	} else {
856	// Create a runtime array instantiation
857	try s.ensureAtRuntime(s.lazyNode(.main_node));
858	return try s.addRef(.array_init, .{
859	.ty = ty,
860	.list = try s.func.?.extra.append(
861	s.gpa,
862	Air.RefList,
863	try s.func.?.extra.appendSlice(s.gpa, scratch.slice()),
864	),
865	});
866	}
867	},
868
869	.memory => {
870	const data = s.frame.currentData(.memory);
871
872	try s.ensureAtRuntime(s.lazyNode(.main_node));
873
874	const initial_value = s.getRef(data.operand, .marked);
875
876	const runtime_known = try s.ensureRefRuntime(s.lazyNode(.operand), initial_value);
877
878	return try s.addRef(.memory, .{
879	.init = runtime_known,
880	.ty = s.typeOfRef(initial_value),
881	});
882	},
883	.store => {
884	const data: Hir.Store = s.frame.currentPayload(.store);
885	assert(s.hir.instTag(data.memory) == .memory); // corrupt store instruction
886
887	try s.ensureAtRuntime(s.lazyNode(.main_node)); // TODO
888
889	const location = s.inst_map.get(data.memory).index() orelse
890	unreachable; // memory must map to a Air ref
891	s.markInst(location);
892
893	const operand = try s.getCoercedRef(
894	s.lazyNode(.rhs),
895	data.operand,
896	s.typeOfRef(location.toRef()),
897	.marked,
898	);
899
900	return try s.addRef(.store, .{
901	.memory = location,
902	.operand = operand,
903	});
904	},
905
906	.js_new => {
907	const call: Hir.JsNew = s.frame.currentPayload(.js_new);
908
909	try s.ensureAtRuntime(s.lazyNode(.main_node));
910
911	const base = s.getRef(call.base, .marked);
912
913	const scratch = try s.arena().alloc(Air.Inst.Ref, call.args.len);
914	defer s.arena().free(scratch);
915	for (call.args.slice(&s.hir), 0..) |arg, i| {
916	const ref = try s.ensureValueDefinedRepresentation(
917	s.lazyNode(.argument(@intCast(i))),
918	s.getRef(arg, .marked),
919	);
920	scratch[i] = ref;
921	}
922
923	const start = s.func.?.extra.list.items.len;
924	try s.func.?.extra.list.appendSlice(s.gpa, @ptrCast(scratch));
925
926	return s.addRef(.js_new, .{
927	.base = base,
928	.call_data = try s.func.?.extra.append(s.gpa, Air.Call.Data, .{ .args = .{
929	.start = @intCast(start),
930	.len = @intCast(scratch.len),
931	} }),
932	});
933	},
934
935	.assert => {
936	const operand = s.frame.currentData(.assert).operand;
937	switch (operand.decode()) {
938	.value => |val| {
939	const coerced = try s.coerceValue(s.lazyNode(.operand), val, .bool);
940	if (coerced == .bool_false) {
941	return s.fail(.user_assertion_basic, .{ .src = s.lazyNode(.operand) });
942	}
943	s.frame.advance();
944	return;
945	},
946	.index => |index| {
947	const mode = s.frame.mode;
948	try s.pushFrame();
949	s.frame = Frame.initFromBlock(s, index, mode, .none);
950	},
951	}
952	},
953
954	.@"comptime" => {
955	const index = s.frame.currentIndex();
956	try s.pushFrame();
957	s.frame = Frame.initFromBlock(s, index, .compile_time, .none);
958	},
959
960	.func => {
961	const data: Hir.Func = s.frame.currentPayload(.func);
962	const reserve = try s.scratch.reserveMulti(
963	s.arena(),
964	FunctionReserve.reserve_types,
965	.{ data.params.len, data.captures.len },
966	);
967	if (data.captures.len > 0) @panic("TODO: captures");
968
969	var handled_reserve: std.debug.SafetyLock = .{};
970	handled_reserve.lock();
971	defer handled_reserve.assertUnlocked();
972	errdefer handled_reserve.unlock();
973
974	for (data.params.slice(&s.hir), 0..) |param, i| {
975	const src = s.lazyNode(.argument(@intCast(i)));
976
977	const known = param.unwrap() orelse @panic("TODO: inferred param sets");
978	switch (known.decode()) {
979	.value => |val| {
980	const ty = (try s.coerceValue(src, val, .type)).toTypeUnsafe(s.ip);
981	if (!ty.hasPossibleRepresentation(s.ip)) {
982	return s.fail(.param_comptime_only, .{
983	.src = src,
984	.type = ty,
985	});
986	}
987	reserve.items(.params)[i] = ty;
988	},
989	.index => |block| {
990	const mode = s.frame.mode;
991	try s.pushFrame();
992	s.frame = Frame.initFromBlock(s, block, mode, .{ .func = .{ .argument = @intCast(i) } });
993	s.frame.mark_index = reserve.index();
994	handled_reserve.unlock();
995	return;
996	},
997	}
998	}
999
1000	const return_type = ret: {
1001	switch ((data.return_type.unwrap() orelse break :ret null).decode()) {
1002	.value => |val| {
1003	const ty = (try s.coerceValue(s.lazyNode(.return_type), val, .type)).toTypeUnsafe(s.ip);
1004	if (!ty.hasPossibleRepresentation(s.ip)) {
1005	return s.fail(.runtime_incompatible_type, .{
1006	.src = s.lazyNode(.return_type),
1007	.type = ty,
1008	});
1009	}
1010	break :ret ty;
1011	},
1012	.index => |block| {
1013	const mode = s.frame.mode;
1014	try s.pushFrame();
1015	s.frame = Frame.initFromBlock(s, block, mode, .{ .func = .return_type });
1016	s.frame.mark_index = reserve.index();
1017	handled_reserve.unlock();
1018	return;
1019	},
1020	}
1021	};
1022
1023	try s.postVisitFunctionPrototype(reserve, return_type);
1024	handled_reserve.unlock();
1025	},
1026
1027	.@"break" => {
1028	const brk: Hir.Break = s.frame.currentPayload(.@"break");
1029	const operand = s.getRef(brk.operand, .marked);
1030
1031	if (s.frame.block_index != brk.block) @panic("TODO");
1032
1033	const mark = core.U32Stack.Mark{ .stack = &s.scratch, .index = s.frame.mark_index };
1034
1035	if (s.frame_stack.items.len == 0) {
1036	if (s.func) |*func| {
1037	const proto = s.owner.unwrap().func.typeOf(s.ip).toUnresolvedFunctionPrototype(s.ip) orelse
1038	unreachable; // must be a function
1039	const coerced = if (proto.return_type) |return_coercion|
1040	try s.coerceRef(s.lazyNode(.operand), operand, return_coercion)
1041	else
1042	try s.ensureRefRuntime(s.lazyNode(.operand), operand);
1043	s.inst_map.add(s.frame.block_index, coerced);
1044
1045	const indexes = mark.slice(u32);
1046	try func.extra.list.ensureUnusedCapacity(s.gpa, indexes.len + 1);
1047	const start = func.extra.list.items.len;
1048	func.extra.list.appendSliceAssumeCapacity(indexes);
1049	func.extra.list.appendAssumeCapacity(@intFromEnum(try s.addIndexUntracked(.@"break", .{
1050	.block = .main_block,
1051	.value = coerced,
1052	})));
1053	func.instructions.items(.data)[0] = .encode(.block, .{
1054	.start = @intCast(start),
1055	.len = @intCast(indexes.len + 1),
1056	});
1057	} else {
1058	s.inst_map.add(s.frame.block_index, operand);
1059	}
1060
1061	return .stop;
1062	}
1063
1064	const data = s.frame.data;
1065	s.popFrame();
1066
1067	switch (s.frame.currentTag()) {
1068	.@"comptime" => {
1069	s.inst_map.add(s.frame.currentIndex(), operand);
1070	s.frame.advance();
1071	},
1072	.assert => {
1073	const coerced = try s.coerceRef(s.lazyNode(.operand), operand, .bool);
1074	switch (coerced.decode()) {
1075	.value => |val| switch (val) {
1076	.bool_true => {}, // pass
1077	.bool_false => {
1078	// Scan for the pattern:
1079	// %n = assert(%n-3 = block [
1080	// ...
1081	// %n-4 = eq(...)
1082	// %n-2 = coercion(%bool_type, ...)
1083	// %n-1 = break(%x, %n-2)
1084	// ])
1085	const cmp_index: Hir.Inst.Index = @enumFromInt(@intFromEnum(s.frame.currentIndex()) - 4);
1086	switch (s.hir.instTag(cmp_index)) {
1087	.eq,
1088	.ne,
1089	.lt,
1090	.le,
1091	.gt,
1092	.ge,
1093	=> {
1094	const cmp_inst = s.hir.instDataUnsafe(Hir.PlNode(Hir.Bin), cmp_index);
1095	const cmp_pl: Hir.Bin = cmp_inst.extra_index.get(&s.hir);
1096	return s.fail(.user_assertion_bin, .{
1097	.src = s.lazyNode(.operand),
1098	.left = switch (s.getRef(cmp_pl.lhs, .no_mark).decode()) {
1099	.value => |v| v,
1100	.index => @panic("TODO"),
1101	},
1102	.right = switch (s.getRef(cmp_pl.rhs, .no_mark).decode()) {
1103	.value => |v| v,
1104	.index => @panic("TODO"),
1105	},
1106	});
1107	},
1108	else => {},
1109	}
1110	return s.fail(.user_assertion_basic, .{ .src = s.lazyNode(.operand) });
1111	},
1112	else => unreachable,
1113	},
1114	.index => {
1115	@panic("TODO");
1116	},
1117	}
1118	s.frame.advance();
1119	},
1120	.@"if" => {
1121	const if_data: Hir.If = s.frame.currentPayload(.@"if");
1122
1123	switch (data.conditional) {
1124	.comptime_condition => {
1125	s.inst_map.add(s.frame.currentIndex(), operand);
1126	s.frame.advance();
1127	return .@"continue";
1128	},
1129	.runtime_yes => {
1130	try s.emitRuntimeBranchForIf(if_data.yes.decode().index, operand, mark);
1131	mark.deinit();
1132
1133	switch (if_data.no.decode()) {
1134	.value => {
1135	// There is no instruction to jump to
1136	},
1137	.index => |block| {
1138	const mode = s.frame.mode;
1139	try s.pushFrame();
1140	s.frame = Frame.initFromBlock(s, block, mode, .{
1141	.conditional = .runtime_no,
1142	});
1143	return .@"continue";
1144	},
1145	}
1146	},
1147	.runtime_no => {
1148	try s.emitRuntimeBranchForIf(if_data.no.decode().index, operand, mark);
1149	mark.deinit();
1150	},
1151	}
1152
1153	assert(s.frame.mode == .run_time);
1154
1155	var yes = s.getRef(if_data.yes, .no_mark);
1156	var no = s.getRef(if_data.no, .no_mark);
1157
1158	if (yes.value()) |val| yes = (try s.ensureValueRuntime(s.lazyNode(.lhs), val)).toAir();
1159	if (no.value()) |val| no = (try s.ensureValueRuntime(s.lazyNode(.rhs), val)).toAir();
1160
1161	if (yes.value() == no.value()) {
1162	s.inst_map.add(s.frame.currentIndex(), yes);
1163	s.frame.advance();
1164	return .@"continue";
1165	}
1166
1167	const union_type = s.peerTypeResolution(&.{ s.typeOfRef(yes), s.typeOfRef(no) });
1168
1169	const yes_coerced = try s.coerceBranch(s.lazyNode(.lhs), yes, union_type);
1170	const no_coerced = try s.coerceBranch(s.lazyNode(.rhs), no, union_type);
1171
1172	s.inst_map.add(s.frame.currentIndex(), try s.addRef(.@"if", .{
1173	.cond = s.getRef(if_data.cond, .no_mark),
1174	.data = try s.func.?.extra.append(s.gpa, Air.If.Data, .{
1175	.yes = yes_coerced,
1176	.no = no_coerced,
1177	.union_ty = union_type,
1178	}),
1179	}));
1180	s.frame.advance();
1181	},
1182	.func => {
1183	const func_data: Hir.Func = s.frame.currentPayload(.func);
1184
1185	const reserve: FunctionReserve = .fromIndex(
1186	&s.scratch,
1187	mark.index,
1188	.{ func_data.params.len, func_data.captures.len },
1189	);
1190
1191	const return_type = switch (data.func) {
1192	.argument => |arg_num| ret: {
1193	s.inst_map.add(
1194	func_data.params.slice(&s.hir)[arg_num].unwrap().?.decode().index,
1195	operand,
1196	);
1197
1198	for (
1199	func_data.params.slice(&s.hir)[arg_num + 1 ..],
1200	arg_num + 1..,
1201	) |param, i| {
1202	const known = param.unwrap() orelse @panic("TODO: inferred param sets");
1203	switch (known.decode()) {
1204	.value => |val| {
1205	const ty = (try s.coerceValue(s.lazyNode(.argument(@intCast(i))), val, .type)).toTypeUnsafe(s.ip);
1206	if (!ty.hasPossibleRepresentation(s.ip)) {
1207	return s.fail(.param_comptime_only, .{
1208	.src = s.lazyNode(.argument(@intCast(i))),
1209	.type = ty,
1210	});
1211	}
1212	},
1213	.index => |block| {
1214	const mode = s.frame.mode;
1215	try s.pushFrame();
1216	s.frame = Frame.initFromBlock(s, block, mode, .{ .func = .{ .argument = @intCast(i) } });
1217	return .@"continue";
1218	},
1219	}
1220	}
1221
1222	switch ((func_data.return_type.unwrap() orelse break :ret null).decode()) {
1223	.value => |val| {
1224	const ty = (try s.coerceValue(s.lazyNode(.return_type), val, .type)).toTypeUnsafe(s.ip);
1225	if (!ty.hasPossibleRepresentation(s.ip)) {
1226	return s.fail(.runtime_incompatible_type, .{
1227	.src = s.lazyNode(.return_type),
1228	.type = ty,
1229	});
1230	}
1231	break :ret ty;
1232	},
1233	.index => |block| {
1234	const mode = s.frame.mode;
1235	try s.pushFrame();
1236	s.frame = Frame.initFromBlock(s, block, mode, .{ .func = .return_type });
1237	s.frame.mark_index = reserve.index();
1238	return .@"continue";
1239	},
1240	}
1241	},
1242	.return_type => ret: {
1243	const val = operand.value() orelse unreachable; // must be comptime
1244	const ty = (try s.coerceValue(s.lazyNode(.return_type), val, .type)).toTypeUnsafe(s.ip);
1245	if (!ty.hasPossibleRepresentation(s.ip)) {
1246	return s.fail(.runtime_incompatible_type, .{
1247	.src = s.lazyNode(.return_type),
1248	.type = ty,
1249	});
1250	}
1251	break :ret ty;
1252	},
1253	};
1254
1255	for (func_data.params.slice(&s.hir), reserve.items(.params)) |param, *dst| {
1256	dst.* = (switch (param.unwrap().?.decode()) {
1257	.value => |value| value,
1258	.index => |index| s.inst_map.get(index).decode().value,
1259	}).toTypeUnsafe(s.ip);
1260	}
1261
1262	try s.postVisitFunctionPrototype(reserve, return_type);
1263	return .@"continue";
1264	},
1265	else => |t| std.debug.panic("TODO: post-visit .{s}", .{@tagName(t)}),
1266	}
1267
1268	return .@"continue";
1269	},
1270
1271	.load_decl => {
1272	const request: Hir.StrNode = s.frame.currentData(.load_decl);
1273	const decl_name = try s.ip.getOrPutString(
1274	s.gpa,
1275	request.string.slice(s.hir.string_bytes),
1276	.no_embedded_nulls,
1277	);
1278	const decl_index = s.lookupDecl(decl_name);
1279	return (try s.getDecl(decl_index)).toAir();
1280	},
1281
1282	.coercion => {
1283	const as: Hir.Coercion = s.frame.currentPayload(.coercion);
1284	const coerce_to = try s.getType(s.lazyNode(.operand), as.type);
1285	return try s.getCoercedRef(s.lazyNode(.operand), as.operand, coerce_to, .marked);
1286	},
1287
1288	.compile_error => {
1289	const node: Hir.RefNode = s.frame.currentData(.compile_error);
1290	const value = try s.getCoercedValue(s.lazyNode(.operand), node.operand, .string);
1291	const str = value.asString(s.ip).toSlice(s.ip);
1292	return s.fail(.user_compile_error, .{
1293	.src = s.lazyNode(.main_node),
1294	.msg = try s.report.addString(str),
1295	});
1296	},
1297
1298	.@"if" => {
1299	const data: Hir.If = s.frame.currentPayload(.@"if");
1300
1301	const condition = try s.getCoercedRef(s.lazyNode(.operand), data.cond, .bool, .marked);
1302	switch (condition.decode()) {
1303	.value => |value| {
1304	// if the condition is known at compile time, Sema
1305	// will not analyze the branch not taken.
1306	assert(value == .bool_true or value == .bool_false);
1307	const branch = if (value == .bool_true) data.yes else data.no;
1308	switch (branch.decode()) {
1309	.value => |v| {
1310	// There is no instruction to jump to
1311	s.inst_map.add(s.frame.currentIndex(), v.toAir());
1312	s.frame.advance();
1313	},
1314	.index => |block| {
1315	const mode = s.frame.mode;
1316	try s.pushFrame();
1317	s.frame = Frame.initFromBlock(s, block, mode, .{
1318	.conditional = .comptime_condition,
1319	});
1320	},
1321	}
1322	},
1323	.index => {
1324	try s.ensureAtRuntime(s.lazyNode(.operand));
1325
1326	var yn: [2]Value = undefined;
1327	inline for (
1328	.{ data.yes, data.no },
1329	.{ .runtime_yes, .runtime_no },
1330	&yn,
1331	) |teg_ref, state, *out| {
1332	switch (teg_ref.decode()) {
1333	.value => |v| {
1334	// There is no instruction to jump to
1335	out.* = v;
1336	},
1337	.index => |block| {
1338	const mode = s.frame.mode;
1339	try s.pushFrame();
1340	s.frame = Frame.initFromBlock(s, block, mode, .{ .conditional = state });
1341	return;
1342	},
1343	}
1344	}
1345
1346	// When both branches are values, Sema has nowhere
1347	// to jump to, so only one Air instruction is emitted
1348	yn[0] = try s.ensureValueRuntime(s.lazyNode(.lhs), yn[0]);
1349	yn[1] = try s.ensureValueRuntime(s.lazyNode(.lhs), yn[1]);
1350
1351	const union_type = s.peerTypeResolution(&.{ yn[0].typeOf(s.ip), yn[1].typeOf(s.ip) });
1352
1353	const yes_coerced = try s.coerceValue(s.lazyNode(.lhs), yn[0], union_type);
1354	const no_coerced = try s.coerceValue(s.lazyNode(.rhs), yn[1], union_type);
1355
1356	if (yes_coerced == no_coerced) {
1357	s.inst_map.add(s.frame.currentIndex(), yes_coerced.toAir());
1358	s.frame.advance();
1359	return;
1360	}
1361
1362	s.inst_map.add(s.frame.currentIndex(), try s.addRef(.@"if", .{
1363	.cond = condition,
1364	.data = try s.func.?.extra.append(s.gpa, Air.If.Data, .{
1365	.yes = yes_coerced.toAir(),
1366	.no = no_coerced.toAir(),
1367	.union_ty = union_type,
1368	}),
1369	}));
1370	s.frame.advance();
1371	},
1372	}
1373	},
1374
1375	.struct_init => {
1376	const node: Hir.StructInit = s.frame.currentPayload(.struct_init);
1377
1378	// Ensure we have a valid struct to operate on
1379	const ty = try s.getType(s.lazyNode(.operand), node.base_type);
1380	const struct_type = ty.toStructType(s.ip) orelse {
1381	return s.fail(.struct_init_invalid_type, .{
1382	.src = s.lazyNode(.operand),
1383	.ty = ty,
1384	});
1385	};
1386
1387	var has_errors = false;
1388	var is_constant = true;
1389
1390	const scratch = try s.scratch.reserve(
1391	s.arena(),
1392	Air.Inst.Ref.Optional,
1393	struct_type.field_types.len,
1394	);
1395	defer scratch.deinit();
1396	@memset(scratch.slice(), .none);
1397
1398	// The ordering of `storage` is defined by the struct's type, which
1399	// may be different than the instantiation. The fields are visited in
1400	// order of the instantiation.
1401	for (node.keys(&s.hir), node.inits(&s.hir), 0..) |init_key, init_value, i| {
1402	const found_index = index: for (struct_type.field_keys.get(s.ip), 0..) |decl_key, j| {
1403	if (decl_key.eqlSlice(init_key.slice(s.hir.string_bytes), s.ip))
1404	break :index j;
1405	} else {
1406	has_errors = true;
1407	try s.addError(.struct_init_unknown_field, .{
1408	.ty = ty,
1409	.src = s.lazyNode(.argument(@intCast(i))),
1410	});
1411	continue;
1412	};
1413	if (scratch.at(found_index).* != .none) {
1414	has_errors = true;
1415	try s.addError(.struct_init_duplicate_field, .{
1416	.ty = ty,
1417	.src = s.lazyNode(.argument(@intCast(i))),
1418	});
1419	continue;
1420	}
1421	const coerced = s.getCoercedRef(
1422	s.lazyNode(.argument(@intCast(i))),
1423	init_value,
1424	struct_type.field_types.at(s.ip, found_index),
1425	.marked,
1426	) catch |e| switch (e) {
1427	error.AnalysisFail => {
1428	// Instead of bailing out with `try`, all fields will be analyzed
1429	has_errors = true;
1430	// Mark something non-null so that duplicate field errors are emitted.
1431	scratch.at(found_index).* = comptime Value.void.toAir().toOptional();
1432	continue;
1433	},
1434	else => return e,
1435	};
1436	if (coerced.kind == .index) is_constant = false;
1437	scratch.at(found_index).* = coerced.toOptional();
1438	}
1439
1440	const storage = scratch.slice();
1441	var i: usize = 0;
1442	while (mem.indexOfScalarPos(Air.Inst.Ref.Optional, storage, i, .none)) |index| {
1443	try s.addError(.struct_init_missing_field, .{
1444	.ty = ty,
1445	.field = @intCast(index),
1446	.src = s.lazyNode(.main_node),
1447	});
1448	i = index + 1;
1449	}
1450	if (i != 0) has_errors = true;
1451
1452	if (has_errors)
1453	return Error.AnalysisFail;
1454
1455	// Now that there are definitely no missing fields, it is safe to
1456	// interpret `scratch` as `Air.Inst.Ref`
1457
1458	if (is_constant) {
1459	const result_storage = scratch.sliceReinterpret(Value);
1460	for (scratch.slice(), result_storage) |ref, *value| {
1461	// `ref` and `value` alias; this coercion is performed in-place
1462	value.* = (ref.unwrap() orelse unreachable).decode().value;
1463	}
1464	return try s.makeValueAir(.{ .struct_value = .{
1465	.ty = ty,
1466	.field_values = try s.ip.extra.appendSlice(s.gpa, result_storage),
1467	} });
1468	} else {
1469	try s.ensureAtRuntime(s.lazyNode(.main_node));
1470
1471	const value_index = try s.func.?.extra.appendSlice(s.gpa, scratch.slice());
1472	return try s.addRef(.struct_init, .{
1473	.ty = ty,
1474	.field_values = value_index.start,
1475	});
1476	}
1477	},
1478
1479	.array_type => {
1480	const un: Hir.RefNode = s.frame.currentData(.array_type);
1481	const operand = try s.getType(s.lazyNode(.operand), un.operand);
1482	return s.makeValueAir(.{ .array_type = .{ .item_type = operand } });
1483	},
1484
1485	.tuple_type => {
1486	const data: Hir.TupleType = s.frame.currentPayload(.tuple_type);
1487
1488	const scratch = try s.scratch.reserve(s.arena(), Type, data.items.len);
1489	defer scratch.deinit();
1490
1491	for (data.items.slice(&s.hir), scratch.slice(), 0..) |src, *dst, i| {
1492	dst.* = try s.getType(s.lazyNode(.argument(@intCast(i))), src);
1493	}
1494
1495	return s.makeValueAir(.{ .tuple_type = .{
1496	.items = try s.ip.extra.appendSlice(s.gpa, scratch.slice()),
1497	} });
1498	},
1499
1500	.tuple_init => {
1501	const data: Hir.TupleInit = s.frame.currentPayload(.tuple_init);
1502
1503	_ = data.type_hint; // TODO: use type hint
1504
1505	const scratch = try s.scratch.reserve(s.arena(), Air.Inst.Ref, data.items.len);
1506	defer scratch.deinit();
1507
1508	var is_const = true;
1509	for (data.items.slice(&s.hir), scratch.slice()) |src, *dst| {
1510	const result = s.getRef(src, .marked);
1511	dst.* = result;
1512	if (result.kind == .index) is_const = false;
1513	}
1514
1515	if (!is_const) {
1516	try s.ensureAtRuntime(s.lazyNode(.main_node));
1517
1518	for (scratch.slice(), 0..) |*ref, i| {
1519	ref.* = try s.ensureRefRuntime(s.lazyNode(.argument(@intCast(i))), ref.*);
1520	}
1521	}
1522
1523	const ty = ty: {
1524	const type_scratch = try s.scratch.reserve(s.arena(), Type, data.items.len);
1525	defer type_scratch.deinit();
1526
1527	for (scratch.slice(), type_scratch.slice()) |val, *ty| {
1528	ty.* = s.typeOfRef(val);
1529	}
1530
1531	break :ty try s.makeType(.{
1532	.tuple_type = .{
1533	// TODO: memory leak
1534	.items = try s.ip.extra.appendSlice(s.gpa, type_scratch.slice()),
1535	},
1536	});
1537	};
1538
1539	if (is_const) {
1540	const result_storage = scratch.sliceReinterpret(Value);
1541	for (scratch.slice(), result_storage) |ref, *value| {
1542	// `ref` and `value` alias; this coercion is performed in-place
1543	value.* = ref.decode().value;
1544	}
1545
1546	return try s.makeValueAir(.{
1547	.tuple_value = .{
1548	// TODO: memory leak
1549	.items = try s.ip.extra.appendSlice(s.gpa, result_storage),
1550	.type = ty,
1551	},
1552	});
1553	} else {
1554	const value_index = try s.func.?.extra.appendSlice(s.gpa, scratch.slice());
1555	return try s.addRef(.struct_init, .{
1556	.field_values = value_index.start,
1557	.ty = ty,
1558	});
1559	}
1560	},
1561
1562	.result_type_argument => {
1563	const result: Hir.ResultTypeArgument = s.frame.currentData(.result_type_argument);
1564
1565	const operand = s.getRef(result.call_base, .no_mark);
1566	const ty = s.typeOfRef(operand);
1567
1568	const func: InternPool.Key.FunctionType = ty.toUnresolvedFunctionPrototype(s.ip) orelse
1569	return Value.opaque_type.toAir();
1570
1571	if (result.argument >= func.param_types.len)
1572	return Value.opaque_type.toAir();
1573
1574	return func.param_types.at(s.ip, result.argument).value().toAir();
1575	},
1576
1577	.result_type_array_value => {
1578	const result: Hir.ResultTypeArrayValue = s.frame.currentData(.result_type_array_value);
1579
1580	const operand = try s.getValue(s.lazyNode(.main_node), result.type);
1581	const ty = operand.toType(s.ip) orelse
1582	return Value.opaque_type.toAir();
1583
1584	const array_type = ty.toArrayType(s.ip) orelse
1585	return Value.opaque_type.toAir();
1586
1587	return array_type.item_type.value().toAir();
1588	},
1589
1590	.result_type_tuple_field => {
1591	const result: Hir.ResultTypeTupleField = s.frame.currentData(.result_type_tuple_field);
1592
1593	const operand = try s.getValue(s.lazyNode(.main_node), result.type);
1594	const ty = operand.toType(s.ip) orelse
1595	return Value.opaque_type.toAir();
1596
1597	_ = ty;
1598
1599	@panic("TODO: tuple result type resolution");
1600	},
1601
1602	.result_type_struct_field => {
1603	const result: Hir.ResultTypeStructField = s.frame.currentData(.result_type_struct_field);
1604
1605	const operand = try s.getValue(s.lazyNode(.main_node), result.type);
1606	const ty = operand.toType(s.ip) orelse
1607	return Value.opaque_type.toAir();
1608
1609	const struct_type = ty.toStructType(s.ip) orelse
1610	return Value.opaque_type.toAir();
1611
1612	const to_match = result.field.slice(s.hir.string_bytes);
1613	for (struct_type.field_keys.get(s.ip), struct_type.field_types.get(s.ip)) |k, v| {
1614	if (k.eqlSlice(to_match, s.ip)) {
1615	return v.value().toAir();
1616	}
1617	}
1618
1619	return Value.opaque_type.toAir();
1620	},
1621
1622	else => |unhandled_tag| std.debug.panic("TODO: analyze instruction .{s}", .{@tagName(unhandled_tag)}),
1623	}
1624	}
1625
1626	fn emitRuntimeBranchForIf(
1627	s: *Sema,
1628	from: Hir.Inst.Index,
1629	result_value: Air.Inst.Ref,
1630	mark: core.U32Stack.Mark,
1631	) !void {
1632	s.inst_map.add(
1633	from,
1634	if (mark.len() == 0 and result_value.kind == .value) brk: {
1635	break :brk result_value;
1636	} else (try s.createRuntimeBlock(mark, result_value)).toRef(),
1637	);
1638	mark.deinit();
1639	}
1640
1641	fn createRuntimeBlock(s: *Sema, mark: core.U32Stack.Mark, result: ?Air.Inst.Ref) !Air.Inst.Index {
1642	assert(mark.len() > 0);
1643	assert(s.frame.mode == .run_time);
1644
1645	const func = &s.func.?;
1646	const idx = func.extra.list.items.len;
1647
1648	if (core.runtime_safety) {
1649	const ty = s.tempAir().typeOfIndex(mark.slice(Air.Inst.Index)[0], s.ip);
1650	if (result != null) {
1651	assert(ty != .never); // control flow already ended
1652	} else {
1653	assert(ty == .never); // does not stop control flow
1654	}
1655	}
1656
1657	const block_instructions = mark.slice(u32);
1658	try func.extra.list.ensureUnusedCapacity(s.gpa, block_instructions.len);
1659	const block = try s.addIndexUntracked(.block, .{
1660	.start = @intCast(idx),
1661	.len = @intCast(block_instructions.len + @intFromBool(result != null)),
1662	});
1663	func.extra.list.appendSliceAssumeCapacity(block_instructions);
1664	if (result) |value| {
1665	const brk_instruction = try s.addIndexUntracked(.@"break", .{
1666	.block = block,
1667	.value = value,
1668	});
1669	func.extra.list.appendAssumeCapacity(@intFromEnum(brk_instruction));
1670	}
1671	return block;
1672	}
1673
1674	const BinaryOp = enum {
1675	add,
1676	sub,
1677	mul,
1678	div,
1679	lt,
1680	gt,
1681	eq,
1682	};
1683
1684	fn binTypeResolution(s: *Sema, src: Hir.Inst.Index, op: BinaryOp, lhs: Type, rhs: Type) !Type {
1685	if (lhs == .@"opaque") {
1686	return if (rhs == .numeric_literal) .float else rhs;
1687	}
1688	if (rhs == .@"opaque") {
1689	return if (lhs == .numeric_literal) .float else lhs;
1690	}
1691
1692	switch (lhs) {
1693	.string => if (op == .add) switch (rhs) {
1694	.string => return .string,
1695	else => {},
1696	},
1697	.numeric_literal => switch (rhs) {
1698	.int32,
1699	.float,
1700	.numeric_literal,
1701	=> return rhs,
1702	else => {},
1703	},
1704	.int32 => switch (rhs) {
1705	.int32 => return .int32,
1706	.numeric_literal => return .int32,
1707	else => {},
1708	},
1709	.float => switch (rhs) {
1710	.int32 => return .float,
1711	.numeric_literal => return .float,
1712	.float => return .float,
1713	else => {},
1714	},
1715	else => {},
1716	}
1717
1718	return s.fail(.bin_op_mismatch, .{
1719	.src = src.op(.main_node).lazyNode(s.techDebtDeclIndex()),
1720	.lhs = lhs,
1721	.rhs = rhs,
1722	});
1723	}
1724
1725	fn comptimeBin(s: *Sema, op: BinaryOp, lhs: Value, rhs: Value) !Value {
1726	const left_ty = lhs.typeOf(s.ip);
1727	assert(rhs.typeOf(s.ip) == left_ty);
1728
1729	switch (op) {
1730	.add => switch (left_ty) {
1731	.numeric_literal, .float => {
1732	const l = lhs.toFloat(s.ip) orelse
1733	unreachable; // must be coerced
1734	const r = rhs.toFloat(s.ip) orelse
1735	unreachable; // must be coerced
1736
1737	const result = l + r;
1738
1739	return try s.makeValue(if (left_ty == .numeric_literal)
1740	.{ .comptime_float = result }
1741	else
1742	.{ .float = result });
1743	},
1744	.int32 => {
1745	const l = lhs.toInt32(s.ip) orelse
1746	unreachable; // must be coerced
1747	const r = rhs.toInt32(s.ip) orelse
1748	unreachable; // must be coerced
1749
1750	const result = std.math.add(i32, l, r) catch
1751	@panic("TODO: out of range");
1752
1753	return try s.makeValue(.{ .int32 = result });
1754	},
1755	.string => {
1756	const l = lhs.asString(s.ip).toSlice(s.ip);
1757	const r = rhs.asString(s.ip).toSlice(s.ip);
1758	var sfa = std.heap.stackFallback(4096, s.arena());
1759	const alloc = sfa.get();
1760	const joined = try std.mem.concat(alloc, u8, &.{ l, r });
1761	defer alloc.free(joined);
1762	return try s.makeValue(.{ .string = joined });
1763	},
1764	else => unreachable,
1765	},
1766	inline .sub, .mul, .div => |tag| switch (left_ty) {
1767	.numeric_literal, .float => {
1768	const l = lhs.toFloat(s.ip) orelse
1769	unreachable; // must be coerced
1770	const r = rhs.toFloat(s.ip) orelse
1771	unreachable; // must be coerced
1772
1773	const result = switch (tag) {
1774	.sub => l - r,
1775	.mul => l * r,
1776	.div => l / r,
1777	else => @compileError(unreachable),
1778	};
1779
1780	return try s.makeValue(if (left_ty == .numeric_literal)
1781	.{ .comptime_float = result }
1782	else
1783	.{ .float = result });
1784	},
1785	.int32 => {
1786	const l = lhs.toInt32(s.ip) orelse
1787	unreachable; // must be coerced
1788	const r = rhs.toInt32(s.ip) orelse
1789	unreachable; // must be coerced
1790
1791	const result = switch (tag) {
1792	.sub => std.math.sub(i32, l, r),
1793	.mul => std.math.mul(i32, l, r),
1794	.div => return try s.makeValue(.{ .float = @as(f64, @floatFromInt(l)) / @as(f64, @floatFromInt(r)) }),
1795	else => @compileError(unreachable),
1796	} catch @panic("TODO: out of range");
1797
1798	return try s.makeValue(.{ .int32 = result });
1799	},
1800	else => unreachable,
1801	},
1802	inline .lt, .gt => |tag| {
1803	const l = lhs.toFloat(s.ip) orelse
1804	unreachable; // must be coerced
1805	const r = rhs.toFloat(s.ip) orelse
1806	unreachable; // must be coerced
1807
1808	const result = switch (tag) {
1809	.lt => l < r,
1810	.gt => l > r,
1811	else => @compileError(unreachable),
1812	};
1813	return if (result) .bool_true else .bool_false;
1814	},
1815	.eq => {
1816	const result = lhs == rhs;
1817	return if (result) .bool_true else .bool_false;
1818	},
1819	}
1820	}
1821
1822	/// Coerce `value` runtime ref to `coerce_type`, and emit an error at `src`'s location
1823	fn coerceRef(s: *Sema, src: LazyNode, ref: Air.Inst.Ref, to: Type) !Air.Inst.Ref {
1824	const t = tracer.traceFmt(@src(), "{} to {}", .{ ref.dump(s.ip), to.dump(s.ip) });
1825	defer t.end();
1826
1827	const from = s.typeOfRef(ref);
1828	if (from == to) {
1829	return ref;
1830	}
1831	if (from == .@"opaque") {
1832	return ref;
1833	}
1834	const index = switch (ref.decode()) {
1835	.value => |v| return (try s.coerceValue(src, v, to)).toAir(),
1836	.index => |index| index,
1837	};
1838	if (s.frame.mode == .compile_time) {
1839	return s.fail(.not_comptime_known, .{ .src = src });
1840	}
1841	switch (to) {
1842	.@"opaque" => {
1843	//
1844	},
1845	.bool => {
1846	//
1847	},
1848	.int32 => switch (from) {
1849	.int32 => unreachable, // same type handled
1850	.numeric_literal => unreachable, // must be comptime known
1851	else => {},
1852	},
1853	.float => switch (from) {
1854	.float => unreachable, // same type handled
1855	.int32 => return index.toRef(),
1856	else => {},
1857	},
1858	.string => {
1859	//
1860	},
1861	.never => {
1862	//
1863	},
1864	.type => {
1865	//
1866	},
1867	.numeric_literal => {
1868	@panic("TODO: error message for not known at compile time");
1869	},
1870	.void => {
1871	//
1872	},
1873	else => {},
1874	}
1875	return s.coercionError(src, from, to);
1876	}
1877
1878	/// Same as `coerceRef` but on a compile-time known value
1879	fn coerceValue(s: *Sema, src: LazyNode, value: Value, to: Type) Error!Value {
1880	const from = value.typeOf(s.ip);
1881
1882	from.assertValid(s.ip);
1883	to.assertValid(s.ip);
1884
1885	if (from == to) {
1886	return value;
1887	}
1888
1889	switch (to) {
1890	.@"opaque" => {
1891	return try s.makeValue(.{ .opaque_value = value });
1892	},
1893	.bool => {
1894	// TODO:
1895	},
1896	.int32 => switch (from) {
1897	.int32 => unreachable, // same type handled
1898	.numeric_literal, .float => switch (value.toKey(s.ip)) {
1899	.comptime_float, .float => |val| {
1900	if (!core.inInt32Range(val)) {
1901	return s.fail(.comptime_float_to_int, .{
1902	.val = val,
1903	.src = src,
1904	});
1905	}
1906
1907	return try s.makeValue(.{
1908	.int32 = @intFromFloat(val),
1909	});
1910	},
1911	else => unreachable, // not a numeric literal
1912	},
1913	else => return s.coercionError(src, from, to),
1914	},
1915	.float => switch (from) {
1916	.float => unreachable, // same type handled
1917	.numeric_literal => if (value.toFloat(s.ip)) |val|
1918	return try s.makeValue(.{
1919	.float = val,
1920	}),
1921	else => {},
1922	},
1923	.string => {
1924	// TODO:
1925	},
1926	.never => {
1927	// nothing coerces to `never`
1928	},
1929	.numeric_literal => {
1930	if (value.toFloat(s.ip)) |float| {
1931	return try s.makeValue(.{
1932	.comptime_float = float,
1933	});
1934	}
1935	},
1936	.type => {
1937	if (value == .void) return .void;
1938
1939	// non-types do not coerce to types
1940	},
1941	.void => if (value == .void) return .void,
1942	else => {
1943	if (to.toArrayType(s.ip)) |to_array_type| {
1944	if (value.valueTag(s.ip) == .array_value) {
1945	return s.coerceArrayValue(src, value, to_array_type.item_type);
1946	}
1947	}
1948	if (to.toTupleType(s.ip)) |to_tuple_type| {
1949	if (value.valueTag(s.ip) == .tuple_value) {
1950	return s.coerceTupleValue(src, value, from, to, to_tuple_type);
1951	}
1952	}
1953	},
1954	}
1955	return s.coercionError(src, from, to);
1956	}
1957
1958	fn coerceBranch(s: *Sema, src: LazyNode, ref: Air.Inst.Ref, to: Type) !Air.Inst.Ref {
1959	return switch (ref.decode()) {
1960	.index => |block| {
1961	if (s.typeOfIndex(block) != to) return ref;
1962	// @panic("TODO");
1963	return ref;
1964	},
1965	.value => |value| (try s.coerceValue(src, value, to)).toAir(),
1966	};
1967	}
1968
1969	fn ensureValueRuntime(s: *Sema, src: LazyNode, value: Value) Error!Value {
1970	const ty = value.typeOf(s.ip);
1971	return switch (ty) {
1972	// Allowed at runtime
1973	.bool,
1974	.float,
1975	.int32,
1976	.string,
1977	.void,
1978	.empty_tuple,
1979	=> value,
1980	.numeric_literal => {
1981	const float = value.toFloat(s.ip) orelse unreachable;
1982
1983	if (core.inInt32Range(float)) {
1984	try s.report.warn(.numeric_int_var_ambiguity, .{
1985	.src = src,
1986	});
1987	}
1988
1989	return try s.makeValue(.{
1990	.float = float,
1991	});
1992	},
1993	.numeric_literal_array => {
1994	try s.report.warn(.numeric_int_array_var_ambiguity, .{
1995	.src = src,
1996	});
1997	return try s.coerceArrayValue(src, value, .float);
1998	},
1999	.never_array => {
2000	if (value.valueData(s.ip, .array_value).get(s.ip).items_len != 0) {
2001	return s.fail(.runtime_incompatible_type, .{
2002	.src = src,
2003	.type = ty,
2004	});
2005	}
2006	return value;
2007	},
2008	.type,
2009	.never,
2010	=> return s.fail(.runtime_incompatible_type, .{
2011	.src = src,
2012	.type = ty,
2013	}),
2014	.@"opaque" => @panic("TODO: represent comptime-known opaques better"),
2015	_ => {
2016	if (!ty.hasPossibleRepresentation(s.ip)) {
2017	return s.fail(.runtime_incompatible_type, .{
2018	.src = src,
2019	.type = ty,
2020	});
2021	}
2022
2023	// When a function is used as a runtime operand, it needs to
2024	// have a resolved return type, so that calling it later is
2025	// able to know what it returns.
2026	_ = try s.resolveFunctionPrototype(value.toAir(), ty);
2027
2028	return value;
2029	},
2030	};
2031	}
2032
2033	fn ensureRefRuntime(s: *Sema, src: LazyNode, ref: Air.Inst.Ref) Error!Air.Inst.Ref {
2034	switch (ref.decode()) {
2035	.value => |v| return (try s.ensureValueRuntime(src, v)).toAir(),
2036	.index => {
2037	const ty = s.typeOfRef(ref);
2038	if (!ty.hasPossibleRepresentation(s.ip)) {
2039	return s.fail(.runtime_incompatible_type, .{
2040	.src = src,
2041	.type = ty,
2042	});
2043	}
2044	return ref;
2045	},
2046	}
2047	}
2048
2049	fn ensureValueDefinedRepresentation(s: *Sema, src: LazyNode, ref: Air.Inst.Ref) Error!Air.Inst.Ref {
2050	const runtime = try s.ensureRefRuntime(src, ref);
2051	const ty = s.typeOfRef(runtime);
2052	if (!ty.hasDefinedRepresentation(s.ip)) {
2053	return s.fail(.type_no_defined_representation, .{
2054	.src = src,
2055	.type = ty,
2056	});
2057	}
2058	return runtime;
2059	}
2060
2061	fn peerTypeResolution(s: *Sema, types: []const Type) Type {
2062	var a = types[0];
2063	for (types[1..]) |b| {
2064	if (a == b) {
2065	continue;
2066	} else if (b == .never) {
2067	continue;
2068	} else if (a == .never) {
2069	a = b;
2070	} else {
2071	std.debug.panic(
2072	"TODO: when two non-equal types implicitly merge (if/match), this should generate a union type.\na: {}\nb: {}",
2073	.{
2074	a.dump(s.ip),
2075	b.dump(s.ip),
2076	},
2077	);
2078	return s.ip.get(s.gpa, .{ .@"union" = &.{ a, b } });
2079	}
2080	}
2081	return a;
2082	}
2083
2084	fn coerceArrayValue(s: *Sema, src: LazyNode, value: Value, item_type: Type) !Value {
2085	const array: InternPool.Tag.ArrayValue, var trail = value.valueData(s.ip, .array_value).getTrail(s.ip);
2086
2087	const scratch = try s.scratch.reserve(s.arena(), Value, array.items_len);
2088	defer scratch.deinit();
2089
2090	const from = trail.readValueSlice(array.items_len);
2091
2092	for (0..from.len) |i| {
2093	scratch.at(i).* = try s.coerceValue(src, from.get(s.ip)[i], item_type);
2094	}
2095
2096	return try s.makeValue(.{ .array_value = .{
2097	.type = try s.makeType(.{ .array_type = .{ .item_type = item_type } }),
2098	.items = try s.ip.extra.appendSlice(s.gpa, scratch.slice()),
2099	} });
2100	}
2101
2102	fn coerceTupleValue(
2103	s: *Sema,
2104	src: LazyNode,
2105	value: Value,
2106	value_type: Type,
2107	target_type: Type,
2108	target_key: InternPool.Key.TupleType,
2109	) !Value {
2110	const tuple_value = value.toKey(s.ip).tuple_value;
2111	if (tuple_value.items.len != target_key.items.len)
2112	return s.coercionError(src, value_type, target_type);
2113
2114	const len = tuple_value.items.len;
2115
2116	const scratch = try s.scratch.reserveMulti(
2117	s.arena(),
2118	.{ .values = Value, .types = Type },
2119	.{ @intCast(len), @intCast(len) },
2120	);
2121	defer scratch.deinit();
2122
2123	// This function will append new items to the intern pool, invalidating
2124	// existing ones. Copy all data into a stable slice first.
2125	@memcpy(scratch.items(.values), tuple_value.items.get(s.ip));
2126	@memcpy(scratch.items(.types), target_key.items.get(s.ip));
2127
2128	for (0..len) |i| {
2129	// `s.scratch` can be invalidated by having a tuple of tuples and coercing it.
2130	const coerced = try s.coerceValue(src, scratch.at(.values, i).*, scratch.at(.types, i).*);
2131	scratch.at(.values, i).* = coerced;
2132	}
2133
2134	return try s.makeValue(.{ .tuple_value = .{
2135	.type = target_type,
2136	.items = try s.ip.extra.appendSlice(s.gpa, scratch.items(.values)),
2137	} });
2138	}
2139
2140	fn lookupDecl(s: *Sema, name: NullTerminatedString) InternPool.DeclIndex {
2141	var nsi = s.ns_index;
2142	while (true) {
2143	const ns = s.ip.namespacePtr(nsi);
2144	if (ns.lookupDirect(s.comp, name)) |decl_id| {
2145	return decl_id;
2146	}
2147	nsi = ns.parent.unwrap() orelse
2148	unreachable; // transform ensures all identifiers get resolved
2149	}
2150	}
2151
2152	fn getDecl(s: *Sema, decl_index: Decl.Index) !Value {
2153	if (s.owner.kind == .decl) {
2154	if (decl_index == s.owner.unwrap().decl) {
2155	return s.ip.declPtr(decl_index).value();
2156	}
2157	}
2158	const decl_data = s.ip.declPtr(decl_index);
2159	try s.declareDependency(.{ .decl_val = decl_index });
2160	const au: AnalysisUnit = .wrap(.{ .decl = decl_index });
2161	switch (decl_data.analysis) {
2162	.unreferenced => {
2163	try s.comp.jobs.writeItem(.{ .analysis = .{ .au = au, .first_blocked_sema = s } });
2164	return error.Interrupt;
2165	},
2166	.in_progress => {
2167	const other_sema = s.comp.ongoing_analysis.get(au) orelse
2168	unreachable; // analysis stopped but did not update state
2169	try other_sema.blocked_semas.append(s.gpa, s);
2170	return error.Interrupt;
2171	},
2172	.complete => {
2173	return decl_data.value();
2174	},
2175	}
2176	}
2177
2178	/// Interrupts if there is an unresolved inferred return type.
2179	fn resolveFunctionPrototype(s: *Sema, ref: Air.Inst.Ref, ty: Type) !?InternPool.Key.FunctionType.Resolved {
2180	const proto = ty.toUnresolvedFunctionPrototype(s.ip) orelse
2181	return null; // not a function prototype
2182
2183	if (proto.return_type) |return_type|
2184	return .{
2185	.param_types = proto.param_types,
2186	.return_type = return_type,
2187	};
2188
2189	const value = ref.value() orelse
2190	unreachable; // cast functions cannot have inferred return types.
2191
2192	try s.declareDependency(.{ .resolved_func = value });
2193
2194	const func = value.toKey(s.ip).func;
2195	const au: AnalysisUnit = .wrap(.{ .func = value });
2196	switch (func.analysis.get(s.ip)) {
2197	.unreferenced => {
2198	try s.comp.jobs.writeItem(.{ .analysis = .{ .au = au, .first_blocked_sema = s } });
2199	return error.Interrupt;
2200	},
2201	.in_progress => {
2202	const other_sema = s.comp.ongoing_analysis.get(au) orelse
2203	unreachable; // analysis stopped but did not update state
2204	try other_sema.blocked_semas.append(s.gpa, s);
2205	return error.Interrupt;
2206	},
2207	.complete => unreachable, // analyzed but did not set return type
2208	}
2209	}
2210
2211	fn declareDependency(sema: *Sema, dependee: InternPool.Dependee) !void {
2212	try sema.ip.addDependency(sema.gpa, sema.owner, dependee);
2213	}
2214
2215	fn fieldAccessStruct(
2216	s: *Sema,
2217	lhs: Air.Inst.Ref,
2218	lhs_type: Type,
2219	struct_type: InternPool.Key.StructType,
2220	field: Hir.Inst.Ref,
2221	) !Air.Inst.Ref {
2222	const rhs = try s.getCoercedValue(s.lazyNode(.rhs), field, .string);
2223	const string = rhs.asString(s.ip);
2224
2225	const found_index: u32 = found_index: {
2226	const lookup = string.tryToNullTerminatedString(
2227	s.ip,
2228	s.gpa,
2229	) catch |err| switch (err) {
2230	error.HasNulls => break :found_index null,
2231	else => |e| return e,
2232	};
2233
2234	break :found_index for (struct_type.field_keys.get(s.ip), 0..) |key, i| {
2235	if (key == lookup)
2236	break @as(u32, @intCast(i));
2237	} else null;
2238	} orelse {
2239	return s.fail(.field_lookup_failed, .{
2240	.ty = lhs_type,
2241	.src = s.lazyNode(.lhs),
2242	.field = rhs,
2243	});
2244	};
2245
2246	switch (lhs.decode()) {
2247	.value => |value| {
2248	_, const trail = value.valueData(s.ip, .struct_value).getTrail(s.ip);
2249	return trail.at(&s.ip.extra, Value, found_index).toAir();
2250	},
2251	.index => |index| {
2252	try s.ensureAtRuntime(s.lazyNode(.lhs));
2253	return s.addRef(.field_struct, .{
2254	.base = index,
2255	.field_index = found_index,
2256	});
2257	},
2258	}
2259	}
2260
2261	fn fieldAccessArray(s: *Sema, lhs: Air.Inst.Ref, lhs_type: Type, rhs_teg: Hir.Inst.Ref) !Air.Inst.Ref {
2262	const rhs = s.getRef(rhs_teg, .marked);
2263
2264	switch (s.typeOfRef(rhs)) {
2265	.string => {
2266	const value = try s.getValue(s.lazyNode(.rhs), rhs_teg);
2267	const string = value.asString(s.ip).toSlice(s.ip);
2268	if (mem.eql(u8, string, "len")) {
2269	switch (lhs.decode()) {
2270	.value => |val| {
2271	return try s.makeValueAir(.{
2272	.int32 = @intCast(val.toKey(s.ip).array_value.items.len),
2273	});
2274	},
2275	.index => {
2276	try s.ensureAtRuntime(s.lazyNode(.main_node));
2277	return s.addRef(.array_len, .{
2278	.operand = lhs,
2279	});
2280	},
2281	}
2282	}
2283
2284	return s.fail(.field_lookup_failed, .{
2285	.ty = lhs_type,
2286	.src = s.lazyNode(.lhs),
2287	.field = value,
2288	});
2289	},
2290	else => {
2291	const index = try s.getCoercedRef(s.lazyNode(.rhs), rhs_teg, .int32, .marked);
2292
2293	if (lhs.kind == .value and index.kind == .value) {
2294	// TODO:
2295	}
2296
2297	try s.ensureAtRuntime(s.lazyNode(.main_node));
2298
2299	if (s.generate_safety_checks) {
2300	const is_above_bounds = try s.addRefMark(.ge, .{
2301	.lhs = index,
2302	.rhs = try s.addRefMark(.array_len, .{
2303	.operand = lhs,
2304	}),
2305	});
2306	const is_oob = switch (index.decode()) {
2307	.value => |value| is_oob: {
2308	const int = value.toInt32(s.ip) orelse unreachable;
2309	if (int < 0) @panic("TODO: always out of bounds");
2310	break :is_oob is_above_bounds;
2311	},
2312	.index => is_oob: {
2313	const is_below_zero = brk: {
2314	const mark = s.scratch.mark();
2315	defer mark.deinit();
2316
2317	const is_below_zero = try s.addRefMark(.lt, .{
2318	.lhs = index,
2319	.rhs = try s.makeValueAir(.{ .int32 = 0 }),
2320	});
2321
2322	break :brk try s.createRuntimeBlock(mark, is_below_zero);
2323	};
2324	break :is_oob try s.emitOrFromRefAndBlock(is_above_bounds, is_below_zero);
2325	},
2326	};
2327
2328	try s.emitSafetyCheck(is_oob, "array out of bounds");
2329	}
2330
2331	return s.addRef(.field_array, .{
2332	.lhs = lhs,
2333	.rhs = index,
2334	});
2335	},
2336	}
2337	}
2338
2339	fn emitOrFromRefAndBlock(s: *Sema, lhs: Air.Inst.Ref, short_circuiting_rhs: Air.Inst.Index) !Air.Inst.Ref {
2340	return try s.addRefMark(.@"if", .{
2341	.cond = lhs,
2342	.data = try s.func.?.extra.append(s.gpa, Air.If.Data, .{
2343	.yes = Value.bool_true.toAir(),
2344	.no = short_circuiting_rhs.toRef(),
2345	.union_ty = .bool,
2346	}),
2347	});
2348	}
2349
2350	fn fieldAccessTuple(
2351	s: *Sema,
2352	lhs: Air.Inst.Ref,
2353	lhs_type: Type,
2354	tuple_type: InternPool.Key.TupleType,
2355	field: Hir.Inst.Ref,
2356	) !Air.Inst.Ref {
2357	const index_value = try s.getCoercedValue(s.lazyNode(.rhs), field, .int32);
2358	const index_signed = index_value.toInt32(s.ip) orelse unreachable;
2359	if (index_signed < 0 or index_signed >= tuple_type.items.len) {
2360	return s.fail(.field_lookup_failed, .{
2361	.ty = lhs_type,
2362	.src = s.lazyNode(.lhs),
2363	.field = index_value,
2364	});
2365	}
2366	const index: u32 = @intCast(index_signed);
2367
2368	switch (lhs.decode()) {
2369	.value => |value| {
2370	return value.toKey(s.ip).tuple_value.items.at(s.ip, index).toAir();
2371	},
2372	.index => |lhs_index| {
2373	try s.ensureAtRuntime(s.lazyNode(.lhs));
2374	return s.addRef(.field_tuple, .{
2375	.base = lhs_index,
2376	.field_index = index,
2377	});
2378	},
2379	}
2380	}
2381
2382	const FunctionReserve = core.U32Stack.ReserveMulti(.{ .params = Type, .captures = Air.Inst.Ref });
2383
2384	fn postVisitFunctionPrototype(s: *Sema, reserve: FunctionReserve, return_type: ?Type) !void {
2385	const tracked_inst = try s.ip.trackInst(s.gpa, s.file, s.frame.currentIndex());
2386	const func_type = try s.makeType(.{
2387	.function_type = .{
2388	.param_types = try s.ip.extra.appendSlice(s.gpa, reserve.items(.params)),
2389	.return_type = return_type,
2390	},
2391	});
2392	const func_value = try s.makeValue(.{
2393	.func = .{
2394	.ty = func_type,
2395	.owner_decl = s.techDebtDeclIndex(), // TODO: ooh, this is a fun one!
2396	.teg_body_inst = tracked_inst,
2397	.analysis = undefined, // not used when appending
2398	},
2399	});
2400
2401	s.inst_map.add(s.frame.currentIndex(), func_value.toAir());
2402
2403	s.frame.advance();
2404
2405	reserve.deinit();
2406
2407	// TODO: move this queue once we perform one of these
2408	// - depend on the return type of an inferred-return-type function
2409	// - use the value in any runtime context ()
2410	try s.comp.jobs.writeItem(.{ .analysis = .{ .au = .wrap(.{ .func = func_value }) } });
2411	}
2412
2413	fn emitSafetyCheck(s: *Sema, should_panic: Air.Inst.Ref, panic_message: []const u8) !void {
2414	const yes = brk: {
2415	const mark = s.scratch.mark();
2416	defer mark.deinit();
2417
2418	_ = try s.addRefMark(.panic, .{
2419	.operand = try s.makeValueAir(.{ .string = panic_message }),
2420	});
2421
2422	break :brk try s.createRuntimeBlock(mark, null);
2423	};
2424	_ = try s.addRefMark(.@"if", .{
2425	.cond = should_panic,
2426	.data = try s.func.?.extra.append(s.gpa, Air.If.Data, .{
2427	.yes = yes.toRef(),
2428	.no = .void,
2429	.union_ty = .void,
2430	}),
2431	});
2432	}
2433
2434	//
2435
2436	fn tempAir(s: *const Sema) Air {
2437	return .{
2438	.insts = s.func.?.instructions.slice(),
2439	.extra = s.func.?.extra.constant(),
2440	};
2441	}
2442
2443	fn typeOfRef(s: *Sema, ref: Air.Inst.Ref) Type {
2444	return switch (ref.decode()) {
2445	.value => |v| v.typeOf(s.ip),
2446	.index => |i| s.tempAir().typeOfIndex(i, s.ip),
2447	};
2448	}
2449
2450	fn pushFrame(s: *Sema) !void {
2451	(try s.frame_stack.addOne(s.arena())).* = s.frame;
2452	s.frame = undefined;
2453	}
2454
2455	fn popFrame(s: *Sema) void {
2456	s.frame = s.frame_stack.pop() orelse unreachable;
2457	}
2458
2459	fn addIndexUntracked(s: *Sema, comptime tag: Air.Inst.Tag, data: tag.Data()) !Air.Inst.Index {
2460	assert(s.frame.mode == .run_time);
2461	try s.func.?.instructions.append(s.gpa, .{
2462	.tag = tag,
2463	.data = .encode(tag, data),
2464	.flags = .{},
2465	});
2466	return @enumFromInt(s.func.?.instructions.len - 1);
2467	}
2468
2469	fn addIndex(s: *Sema, comptime tag: Air.Inst.Tag, data: tag.Data()) !Air.Inst.Index {
2470	const index = try s.addIndexUntracked(tag, data);
2471	try s.scratch.add(s.arena(), Air.Inst.Index, index);
2472	return index;
2473	}
2474
2475	fn addRef(s: *Sema, comptime tag: Air.Inst.Tag, data: tag.Data()) !Air.Inst.Ref {
2476	return (try s.addIndex(tag, data)).toRef();
2477	}
2478
2479	fn addRefMark(s: *Sema, comptime tag: Air.Inst.Tag, data: tag.Data()) !Air.Inst.Ref {
2480	const inst = try s.addIndex(tag, data);
2481	s.markInst(inst);
2482	return inst.toRef();
2483	}
2484
2485	fn typeOfIndex(s: *Sema, i: Air.Inst.Index) Type {
2486	return s.tempAir().typeOfIndex(i, s.ip);
2487	}
2488
2489	fn namespace(s: *const Sema) *Namespace {
2490	return s.ip.namespacePtr(s.ns_index);
2491	}
2492
2493	fn makeValue(s: *Sema, key: InternPool.Key) !Value {
2494	return try s.ip.get(s.gpa, key);
2495	}
2496
2497	fn makeType(s: *Sema, key: InternPool.Key) !Type {
2498	return (try s.makeValue(key)).toTypeUnsafe(s.ip);
2499	}
2500
2501	fn makeValueAir(s: *Sema, key: InternPool.Key) !Air.Inst.Ref {
2502	return (try s.makeValue(key)).toAir();
2503	}
2504
2505	fn lazyNode(s: *const Sema, op: Report.Operand) LazyNode {
2506	return s.frame.currentIndex().op(op).lazyNode(s.techDebtDeclIndex());
2507	}
2508
2509	/// Using this function is incorrect because as of "Sema v5" rewrite,
2510	/// it is incorrect to use a Decl.Index as the source of truth.
2511	fn techDebtDeclIndex(s: *const Sema) Decl.Index {
2512	return switch (s.owner.unwrap()) {
2513	.decl => |decl| decl,
2514	.func => |func| s.ip.valueToKey(func).func.owner_decl,
2515	};
2516	}
2517
2518	fn addWarn(s: *Sema, comptime kind: Report.Err.FieldEnum, data: core.FieldType(Report.Err, kind)) !void {
2519	try s.report.warn(kind, data);
2520	}
2521
2522	fn addError(s: *Sema, comptime kind: Report.Err.FieldEnum, data: core.FieldType(Report.Err, kind)) !void {
2523	try s.report.err(kind, data);
2524	}
2525
2526	fn fail(s: *Sema, comptime kind: Report.Err.FieldEnum, data: core.FieldType(Report.Err, kind)) Error {
2527	try s.report.err(kind, data);
2528	return Error.AnalysisFail;
2529	}
2530
2531	fn coercionError(s: *Sema, src: LazyNode, from: Type, to: Type) Error {
2532	return s.fail(.coercion, .{
2533	.from = from,
2534	.to = to,
2535	.src = src,
2536	});
2537	}
2538
2539	fn assertHasFunction(s: *const Sema) void {
2540	assert(s.func_stack_len > 0);
2541	}
2542
2543	/// TODO: This function is designed incorrectly. it should be
2544	/// - "cannot be computed at comptime due to runtime operand"
2545	/// - <exact operation> cannot be performed at compile time
2546	fn ensureAtRuntime(s: *Sema, src: LazyNode) !void {
2547	if (s.frame.mode == .compile_time) {
2548	return s.fail(.cannot_be_comptime, .{ .src = src });
2549	}
2550	}
2551
2552	fn arena(s: *Sema) Allocator {
2553	return s.arena_state.allocator();
2554	}
2555
2556	fn debug(s: *Sema, comptime fmt: []const u8, args: anytype) void {
2557	if (s.comp.options.verbose_sema)
2558	s.comp.out.print(
2559	"sema {}: " ++ fmt ++ "\n",
2560	.{s.owner.dump(s.ip)} ++ args,
2561	) catch {};
2562	}
2563
2564	/// Frame uses @fieldParentPtr to do some pointer arithmetic. To ensure every
2565	/// pointer to `Sema` is valid, it has a field set to a specific 128-bit number.
2566	/// Failing assert(s.magic == .valid) means you have an invalid pointer.
2567	const Magic = if (runtime_safety) enum(u128) {
2568	valid = 0x57453ef77efd3a72c7a0ebe03f80878c,
2569	_,
2570	} else enum { valid };
2571
2572	const Sema = @This();
2573
2574	const std = @import("std");
2575	const mem = std.mem;
2576	const math = std.math;
2577	const assert = std.debug.assert;
2578	const Allocator = std.mem.Allocator;
2579	const DynamicBitSetUnmanaged = std.DynamicBitSetUnmanaged;
2580	const DynamicArray = std.ArrayListUnmanaged;
2581
2582	const core = @import("mod.zig");
2583	const runtime_safety = core.runtime_safety;
2584	const assertFailed = core.assertFailed;
2585	const StoredTrace = core.StoredTrace;
2586
2587	const Comp = core.Comp;
2588	const File = Comp.File;
2589	const Decl = Comp.Decl;
2590	const Namespace = Comp.Namespace;
2591
2592	const Hir = core.Hir;
2593
2594	const Air = core.Air;
2595	const Ast = core.Ast;
2596	const store = core.array;
2597
2598	const Report = core.Report;
2599	const LazyNode = Report.LazyNode;
2600
2601	const InternPool = core.InternPool;
2602	const Value = InternPool.Value;
2603	const Type = InternPool.Type;
2604	const AnalysisUnit = InternPool.AnalysisUnit;
2605	const NullTerminatedString = InternPool.NullTerminatedString;
2606
2607	const tracer = @import("tracer");