1//! Large parts of this file are based on the Zig compiler's InternPool.
2//! https://github.com/ziglang/zig/blob/0.12.0/src/InternPool.zig
3//!
4//! All interned objects have both a Value and a Type. Type is a subset of
5//! Value, since Ix allows operating on types the same as values.
6//! This data structure is intended to be serializable for incremental
7//! compilation efforts.
8//!
9//! This data structure is self-contained, with the following exceptions:
10//! * Comp.Namespace has a pointer to Comp.File
11//!
12//! TODO: This structure does not really consider threads and concurrent
13//! access. Zig 0.14 has some interesting work that I have not yet studied:
14//! https://github.com/ziglang/zig/blob/master/src/InternPool.zig
15//! This file will likely to be rewritten to inherit Zig's improvements.
16
17/// Maps `Key` to `Value`. `Key` objects are not stored anywhere; they are
18/// constructed lazily. The `Value` is also stored out of line in `.items`. The
19/// ArrayHashMap functions as a list of hashes to allow fast lookups, and then
20/// reading it's data out of `.items` and `.extra` via the index lookup.
21///
22/// The preferred way to access these this data through `.get()` and the methods
23/// on `Value` and `Type`.
24map: std.AutoArrayHashMapUnmanaged(void, void) = .empty,
25items: std.MultiArrayList(Item) = .empty,
26extra: Extra = .empty,
27
28/// In order to store references to strings in fewer bytes, all string bytes are
29/// placed here. String bytes can be null. It is up to whoever is referencing
30/// the data here whether they want to store both index and length, thus
31/// allowing null bytes, or store only index, and use null-termination. The
32/// `string_bytes` array is agnostic to either usage.
33string_bytes: std.ArrayListUnmanaged(u8) = .empty,
34
35/// Used for finding the index inside `string_bytes`.
36string_table: std.HashMapUnmanaged(
37 u32,
38 void,
39 std.hash_map.StringIndexContext,
40 std.hash_map.default_max_load_percentage,
41) = .empty,
42
43/// An index into `tracked_insts` gives a reference to a single ZIR instruction which
44/// persists across incremental updates.
45tracked_insts: std.AutoArrayHashMapUnmanaged(TrackedInst, void) = .empty,
46
47/// Rather than allocating Decl objects with an Allocator, we instead allocate
48/// them with this SegmentedList. This provides four advantages:
49/// * Stable memory so that one thread can access a Decl object while another
50/// thread allocates additional Decl objects from this list.
51/// * It allows us to use u32 indexes to reference Decl objects rather than
52/// pointers, saving memory in Type, Value, and dependency sets.
53/// * Using integers to reference Decl objects rather than pointers makes
54/// serialization trivial.
55/// * It provides a unique integer to be used for anonymous symbol names, avoiding
56/// multi-threaded contention on an atomic counter.
57allocated_decls: std.SegmentedList(Comp.Decl, 0) = .{},
58/// When a Decl object is freed from `allocated_decls`, it is pushed into this stack.
59decls_free_list: std.ArrayListUnmanaged(DeclIndex) = .{},
60
61/// Same pattern as with `allocated_decls`.
62allocated_namespaces: std.SegmentedList(Comp.Namespace, 0) = .{},
63/// Same pattern as with `decls_free_list`.
64namespaces_free_list: std.ArrayListUnmanaged(NamespaceIndex) = .{},
65
66/// Dependencies on the source code hash associated with a ZIR instruction.
67/// * For a `declaration`, this is the entire declaration body.
68/// * For a `struct_decl`, `union_decl`, etc, this is the source of the fields (but not declarations).
69/// * For a `func`, this is the source of the full function signature.
70/// These are also invalidated if tracking fails for this instruction.
71/// Value is index into `dep_entries` of the first dependency on this hash.
72src_hash_deps: std.AutoArrayHashMapUnmanaged(TrackedInst.Index, DepEntry.Index) = .{},
73/// Dependencies on the value of a Decl.
74/// Value is index into `dep_entries` of the first dependency on this Decl value.
75decl_val_deps: std.AutoArrayHashMapUnmanaged(DeclIndex, DepEntry.Index) = .{},
76/// Dependencies on the value of a Decl.
77/// Value is index into `dep_entries` of the first dependency on this Decl value.
78resolved_func_deps: std.AutoArrayHashMapUnmanaged(Value, DepEntry.Index) = .{},
79
80/// Given a `Depender`, points to an entry in `dep_entries` whose `depender`
81/// matches. The `next_dependee` field can be used to iterate all such entries
82/// and remove them from the corresponding lists.
83first_dependency: std.AutoArrayHashMapUnmanaged(AnalysisUnit, DepEntry.Index) = .{},
84
85/// Stores dependency information. The hashmaps declared above are used to look
86/// up entries in this list as required. This is not stored in `extra` so that
87/// we can use `free_dep_entries` to track free indices, since dependencies are
88/// removed frequently.
89dep_entries: std.ArrayListUnmanaged(DepEntry) = .{},
90/// Stores unused indices in `dep_entries` which can be reused without a full
91/// garbage collection pass.
92free_dep_entries: std.ArrayListUnmanaged(DepEntry.Index) = .{},
93
94pub const Tag = enum(u8) {
95 /// This special tag represents a value that was removed from this pool via
96 /// `InternPool.remove`. The item remains allocated to preserve indices, but
97 /// lookups will consider it not equal to any other item, and all queries
98 /// assert not this tag. `data` is unused.
99 removed,
100
101 /// A function type
102 function_type,
103 /// A struct type
104 struct_type,
105 /// An array type
106 array_type,
107 /// A tuple type
108 tuple_type,
109 /// A type that can be represented with only an enum tag.
110 simple_type,
111
112 // --- before this are types ---
113 // --- past this are values ---
114
115 /// A value that can be represented with only an enum tag.
116 /// data is SimpleValue enum value.
117 simple_value,
118 /// A numeric literal that can be represented as a float.
119 /// Integers greater than 2^53 known at compile time are currently not supported.
120 comptime_float,
121 /// An int32 value
122 int32,
123 /// A float value
124 float,
125 /// A function
126 func,
127 /// A string
128 string,
129 /// An instance of a struct
130 struct_value,
131 /// An instance of an array
132 array_value,
133 /// An extern reference. For JS, this can be a property access
134 external_value,
135 /// A value masked as "opaque" type
136 opaque_value,
137 /// A tuple value
138 tuple_value,
139
140 pub fn Data(comptime tag: Tag) type {
141 return switch (tag) {
142 .removed => unreachable, // does not have a data
143
144 .simple_type => SimpleType,
145 .simple_value => SimpleValue,
146 .int32 => i32,
147 .opaque_value => Value,
148
149 else => Extra.Index(tag.Payload()),
150 };
151 }
152
153 /// When `data` is an extra index, this is the type of the payload.
154 pub fn Payload(comptime tag: Tag) type {
155 return switch (tag) {
156 .removed,
157 .simple_type,
158 .simple_value,
159 .int32,
160 .opaque_value,
161 => unreachable, // does not have a payload
162 .float, .comptime_float => Float,
163 .func => FuncDecl,
164 .function_type => FunctionType,
165 .string => String.WithLen,
166 .struct_value => StructValue,
167 .struct_type => StructType,
168 .array_type => ArrayType,
169 .array_value => ArrayValue,
170 .external_value => ExternalValue,
171 .tuple_type => TupleType,
172 .tuple_value => TupleValue,
173 };
174 }
175
176 /// Trailing: N/A
177 pub const FuncDecl = struct {
178 analysis: FuncAnalysis,
179 owner_decl: DeclIndex,
180 ty: Type,
181 teg_body_inst: TrackedInst.Index,
182
183 pub const ty_index = 2;
184 };
185
186 /// Trailing:
187 /// 0. param_type: Index to param type. Repeated .params_len
188 pub const FunctionType = struct {
189 params_len: u32,
190 return_type: Type.Optional,
191 };
192
193 /// Trailing:
194 /// 0. field_key: NullTerminatedString. Repeated .field_len
195 /// 1. field_type: Type. Repeated .field_len
196 pub const StructType = struct {
197 fields_len: u32,
198 };
199
200 /// Trailing:
201 pub const ArrayType = struct {
202 item_type: Type,
203 };
204
205 /// Trailing:
206 /// 1. item: Type. Repeated per .items_len
207 pub const ArrayValue = struct {
208 /// This is the array type, not the item type
209 type: Type,
210 items_len: u32,
211 };
212
213 /// Trailing:
214 /// 0. item: Type. Repeated per .items_len
215 pub const TupleType = struct {
216 items_len: u32,
217 };
218
219 /// Trailing:
220 /// 0. value: Value. Repeated per .items_len
221 pub const TupleValue = struct {
222 /// This is the tuple type, not the item type
223 type: Type,
224 items_len: u32,
225 };
226
227 /// Trailing:
228 /// 0. value: Value. Repeated .ty.structInfo().field_len
229 pub const StructValue = struct {
230 /// The type of this field
231 ty: Type,
232 };
233
234 /// Trailing:
235 /// 0. value: Value. Repeated .key_count
236 pub const ExternalValue = struct {
237 key_count: u32,
238 };
239};
240
241/// This is an index into .items
242pub const Value = enum(u32) {
243 pub const first_type: Value = .opaque_type;
244 pub const last_type: Value = .empty_tuple_type;
245 pub const first_value: Value = .void;
246 pub const last_value: Value = .empty_tuple;
247
248 opaque_type,
249 bool_type,
250 int32_type,
251 float_type,
252 string_type,
253 never_type,
254 type_type,
255 numeric_literal_type,
256 numeric_literal_array_type,
257 never_array_type,
258 empty_tuple_type,
259
260 void,
261 bool_true,
262 bool_false,
263 int32_zero,
264 float_zero,
265 nan,
266 empty_string,
267 empty_array,
268 empty_tuple,
269
270 none = std.math.maxInt(u32),
271 _,
272
273 pub const Slice = Extra.Slice(Value);
274
275 /// Used for a map of `Value` values to the index within a list of `Value` values.
276 const Adapter = struct {
277 values: []const Value,
278
279 pub fn eql(ctx: @This(), a: Value, b_void: void, b_map_index: usize) bool {
280 _ = b_void;
281 return a == ctx.values[b_map_index];
282 }
283
284 pub fn hash(ctx: @This(), a: Value) u32 {
285 _ = ctx;
286 return std.hash.uint32(@intFromEnum(a));
287 }
288 };
289
290 pub fn valueTag(value: Value, ip: *const InternPool) Tag {
291 return ip.items.items(.tag)[@intFromEnum(value)];
292 }
293
294 pub fn valueData(value: Value, ip: *const InternPool, comptime tag: Tag) tag.Data() {
295 return ip.items.items(.data)[@intFromEnum(value)].decode(tag, value.valueTag(ip));
296 }
297
298 pub fn toAir(value: Value) Air.Inst.Ref {
299 return .{ .kind = .value, .data = @intCast(@intFromEnum(value)) };
300 }
301
302 pub fn toKey(value: Value, ip: *const InternPool) Key {
303 return ip.valueToKey(value);
304 }
305
306 pub fn assertValid(value: Value, ip: *const InternPool) void {
307 assert(@intFromEnum(value) < ip.items.len);
308 assert(value != .none);
309 assert(ip.items.items(.tag)[@intFromEnum(value)] != .removed);
310 }
311
312 pub fn dump(value: Value, ip: *const InternPool) std.fmt.Formatter(Value.formatValue) {
313 return .{ .data = .{ .val = value, .ip = ip } };
314 }
315
316 fn formatValue(
317 ctx: struct { val: Value, ip: *const InternPool },
318 comptime _: []const u8,
319 _: std.fmt.FormatOptions,
320 writer: anytype,
321 ) !void {
322 // TODO: move the formatter out of Air.Dump
323 var state: Air.Dump.State = undefined;
324 state.ip = ctx.ip;
325 state.tty = core.detectTTYFromWriter(writer);
326 try Air.Dump.State.dumpValue(&state, writer, ctx.val);
327 }
328
329 pub fn typeOf(value: Value, ip: *const InternPool) Type {
330 return switch (value.valueTag(ip)) {
331 .removed => unreachable, // UAF
332
333 .function_type,
334 .simple_type,
335 .struct_type,
336 .array_type,
337 .tuple_type,
338 => .type,
339
340 .simple_value => switch (value.valueData(ip, .simple_value)) {
341 .true => .bool,
342 .false => .bool,
343 .void => .void,
344 },
345
346 .comptime_float => .numeric_literal,
347 .int32 => .int32,
348 .float => .float,
349 .string => .string,
350 .func => value.toKey(ip).func.ty,
351 .struct_value => value.toKey(ip).struct_value.ty,
352 .array_value => value.toKey(ip).array_value.type,
353 .external_value, .opaque_value => .@"opaque",
354 .tuple_value => value.toKey(ip).tuple_value.type,
355 };
356 }
357
358 /// Try to re-interpret this `Value` as a `Type`.
359 /// Returns `null` if the value is not a type.
360 pub fn toType(value: Value, ip: *const InternPool) ?Type {
361 return switch (value.valueTag(ip)) {
362 .removed => unreachable, // UAF
363
364 .function_type,
365 .struct_type,
366 .simple_type,
367 .array_type,
368 .tuple_type,
369 => @enumFromInt(@intFromEnum(value)),
370
371 // exception: void is a value AND a type
372 .simple_value => if (value == .void) .void else null,
373
374 else => null,
375 };
376 }
377
378 pub fn toTypeUnsafe(value: Value, proof_ip: *const InternPool) Type {
379 if (core.runtime_safety) {
380 return value.toType(proof_ip) orelse
381 std.debug.panic("{} is not a type", .{value.dump(proof_ip)});
382 }
383 return @enumFromInt(@intFromEnum(value));
384 }
385
386 pub fn asString(val: Value, ip: *const InternPool) InternPool.String.WithLen {
387 return val.valueData(ip, .string).get(ip);
388 }
389
390 pub fn toFloat(val: Value, ip: *const InternPool) ?f64 {
391 return switch (val.valueTag(ip)) {
392 inline .comptime_float, .float => |tag| val.valueData(ip, tag).get(ip).decode(),
393 .int32 => @floatFromInt(val.valueData(ip, .int32)),
394 else => null,
395 };
396 }
397
398 pub fn toInt32(val: Value, ip: *const InternPool) ?i32 {
399 return switch (val.valueTag(ip)) {
400 .int32 => val.valueData(ip, .int32),
401 else => null,
402 };
403 }
404
405 pub fn displayName(value: Value, ip: *const InternPool) std.fmt.Formatter(formatDisplayName) {
406 return .{ .data = .{ .value = value, .ip = ip } };
407 }
408
409 fn formatDisplayName(
410 ctx: struct { value: Value, ip: *const InternPool },
411 comptime _: []const u8,
412 _: std.fmt.FormatOptions,
413 writer: anytype,
414 ) !void {
415 const value = ctx.value;
416 const ip = ctx.ip;
417 const key = value.toKey(ip);
418 switch (key) {
419 inline .comptime_float, .int32, .float => |n| {
420 try writer.print("{d}", .{n});
421 },
422 else => |tag| std.debug.panic("TODO: print value .{s}", .{@tagName(tag)}),
423 }
424 }
425};
426
427/// Type is subset of Value which represents the values that have typeOf() == Value.type_type
428/// It is a bitcast, so going to and from are only the cost of ensuring the Value is a Type
429pub const Type = enum(u32) {
430 @"opaque" = @intFromEnum(Value.opaque_type),
431 bool = @intFromEnum(Value.bool_type),
432 int32 = @intFromEnum(Value.int32_type),
433 float = @intFromEnum(Value.float_type),
434 string = @intFromEnum(Value.string_type),
435 never = @intFromEnum(Value.never_type),
436 type = @intFromEnum(Value.type_type),
437 numeric_literal = @intFromEnum(Value.numeric_literal_type),
438 numeric_literal_array = @intFromEnum(Value.numeric_literal_array_type),
439 never_array = @intFromEnum(Value.never_array_type),
440 empty_tuple = @intFromEnum(Value.empty_tuple_type),
441 void = @intFromEnum(Value.void),
442 _,
443
444 // Restricted version of `InternPool.Tag`
445 pub const Tag = enum(u32) {
446 function_type = @intFromEnum(InternPool.Tag.function_type),
447 struct_type = @intFromEnum(InternPool.Tag.struct_type),
448 array_type = @intFromEnum(InternPool.Tag.array_type),
449 simple_type = @intFromEnum(InternPool.Tag.simple_type),
450 tuple_type = @intFromEnum(InternPool.Tag.tuple_type),
451 };
452
453 pub const Slice = Extra.Slice(Type);
454 const y = Slice{};
455
456 pub fn value(ty: Type) Value {
457 return @enumFromInt(@intFromEnum(ty));
458 }
459
460 pub fn assertValid(ty: Type, ip: *const InternPool) void {
461 ty.value().assertValid(ip);
462 }
463
464 pub fn tag(ty: Type, ip: *const InternPool) Type.Tag {
465 if (ty == .void) return .simple_type;
466 return @enumFromInt(@intFromEnum(ty.value().valueTag(ip)));
467 }
468
469 pub fn toUnresolvedFunctionPrototype(ty: Type, ip: *const InternPool) ?Key.FunctionType {
470 if (ty.tag(ip) != .function_type) return null;
471 return ip.valueToKey(ty.value()).function_type;
472 }
473
474 pub fn toStructType(ty: Type, ip: *const InternPool) ?Key.StructType {
475 if (ty.tag(ip) != .struct_type) return null;
476 return ip.valueToKey(ty.value()).struct_type;
477 }
478
479 pub fn toArrayType(ty: Type, ip: *const InternPool) ?Key.ArrayType {
480 if (ty.tag(ip) != .array_type) return null;
481 return ip.valueToKey(ty.value()).array_type;
482 }
483
484 pub fn toTupleType(ty: Type, ip: *const InternPool) ?Key.TupleType {
485 if (ty.tag(ip) != .tuple_type) return null;
486 return ip.valueToKey(ty.value()).tuple_type;
487 }
488
489 /// If it is possible to represent this type at runtime. Some types do not
490 /// have a defined representation, such as structs (to allow field renaming, unwrapping).
491 pub fn hasPossibleRepresentation(ty: Type, ip: *const InternPool) bool {
492 return switch (ty) {
493 .bool,
494 .int32,
495 .float,
496 .string,
497 .void,
498 .@"opaque",
499 => true,
500 .numeric_literal,
501 .type,
502 .never,
503 => false,
504 else => switch (ty.tag(ip)) {
505 .simple_type => unreachable, // all simple types are already printed
506 .struct_type,
507 .function_type,
508 => true,
509 .tuple_type => {
510 const tuple_type = ty.toTupleType(ip).?;
511 for (tuple_type.items.get(ip)) |item| {
512 if (!item.hasPossibleRepresentation(ip)) {
513 return false;
514 }
515 }
516 return true;
517 },
518 .array_type => ty.toArrayType(ip).?.item_type.hasPossibleRepresentation(ip),
519 },
520 };
521 }
522
523 /// A defined representation is a specific strategy for lowering values in
524 /// codegen that the developer is allowed to rely on.
525 pub fn hasDefinedRepresentation(ty: Type, ip: *const InternPool) bool {
526 return switch (ty) {
527 .bool,
528 .int32,
529 .float,
530 .string,
531 .@"opaque",
532 => true,
533 .void,
534 .numeric_literal,
535 .type,
536 .never,
537 => false,
538 else => switch (ty.tag(ip)) {
539 .simple_type => unreachable, // all simple types are already printed
540 .struct_type,
541 .function_type,
542 .tuple_type,
543 => false,
544 .array_type => ty.toArrayType(ip).?.item_type.hasDefinedRepresentation(ip),
545 },
546 };
547 }
548
549 pub fn displayName(ty: Type, ip: *const InternPool) std.fmt.Formatter(formatDisplayName) {
550 return .{ .data = .{ .type = ty, .ip = ip } };
551 }
552
553 pub fn dump(ty: Type, ip: *const InternPool) std.fmt.Formatter(Value.formatValue) {
554 return ty.value().dump(ip);
555 }
556
557 fn formatDisplayName(
558 ctx: struct { type: Type, ip: *const InternPool },
559 comptime _: []const u8,
560 _: std.fmt.FormatOptions,
561 writer: anytype,
562 ) !void {
563 const ty = ctx.type;
564 const ip = ctx.ip;
565
566 switch (ty) {
567 .@"opaque" => return try writer.writeAll("opaque"),
568 .bool => return try writer.writeAll("bool"),
569 .int32 => return try writer.writeAll("int"),
570 .float => return try writer.writeAll("float"),
571 .string => return try writer.writeAll("string"),
572 .never => return try writer.writeAll("never"),
573 .type => return try writer.writeAll("type"),
574 .numeric_literal => return try writer.writeAll("numeric literal"),
575 .void => return try writer.writeAll("void"),
576 else => {},
577 }
578
579 switch (ty.tag(ip)) {
580 .simple_type => unreachable, // all simple types are already printed
581 .function_type => {
582 const function_type = ty.toUnresolvedFunctionPrototype(ip).?;
583 try writer.writeAll("fn(");
584 for (function_type.param_types.get(ip), 0..) |param, i| {
585 if (i != 0) try writer.writeAll(", ");
586 try writer.print("{}", .{param.displayName(ip)});
587 }
588 try writer.writeAll(") -> ");
589 if (function_type.return_type) |return_type|
590 try writer.print("{}", .{return_type.displayName(ip)})
591 else
592 try writer.writeAll("[inferred]");
593 },
594 .struct_type => {
595 try writer.writeAll("[struct]");
596 },
597 .array_type => {
598 try writer.writeAll("[]");
599 const array_type = ty.toArrayType(ip).?;
600 try writer.print("{}", .{array_type.item_type.displayName(ip)});
601 },
602 .tuple_type => {
603 try writer.writeAll("(");
604 for (ty.toTupleType(ip).?.items.get(ip), 0..) |item, i| {
605 if (i != 0) try writer.writeAll(", ");
606 try writer.print("{}", .{item.displayName(ip)});
607 }
608 try writer.writeAll(")");
609 },
610 }
611 }
612
613 pub const Optional = enum(u32) {
614 none = std.math.maxInt(u32),
615 _,
616
617 pub fn init(opt: ?Type) Optional {
618 return if (opt) |o| @enumFromInt(@intFromEnum(o)) else .none;
619 }
620
621 pub fn unwrap(opt: Optional) ?Type {
622 return if (opt != .none) @enumFromInt(@intFromEnum(opt)) else null;
623 }
624 };
625};
626
627pub const Item = struct {
628 tag: Tag,
629 data: EncodedData,
630
631 pub fn encode(comptime tag: Tag, data: tag.Data()) Item {
632 return .{ .tag = tag, .data = .encode(tag, data) };
633 }
634};
635
636pub const Extra = dod.ExtraStore(.intern_pool, .@"var");
637pub const EncodedData = dod.EncodedData(Tag, u32);
638
639/// How many items in the InternPool are statically known.
640/// This is specified with an integer literal and a corresponding comptime
641/// assert below to break an unfortunate and arguably incorrect dependency loop
642/// when compiling.
643pub const static_len = Hir.Inst.Index.static_len;
644comptime {
645 // @compileLog(static_len, static_keys.len);
646 assert(static_len == static_keys.len);
647}
648
649pub const static_keys = [_]Key{
650 SimpleType.@"opaque".key(),
651 SimpleType.bool.key(),
652 SimpleType.int32.key(),
653 SimpleType.float.key(),
654 SimpleType.string.key(),
655 SimpleType.never.key(),
656 SimpleType.type.key(),
657 SimpleType.numeric_literal.key(),
658 .{ .array_type = .{ .item_type = .numeric_literal } },
659 .{ .array_type = .{ .item_type = .never } },
660 .{ .tuple_type = .{ .items = .empty } },
661
662 SimpleValue.void.key(),
663 SimpleValue.true.key(),
664 SimpleValue.false.key(),
665 .{ .int32 = 0 },
666 .{ .float = 0.0 },
667 .{ .float = Float.pure_nan.decode() },
668 .{ .array_value = .{
669 .type = .never_array,
670 .items = .empty,
671 } },
672 .{ .string = "" },
673 .{ .tuple_value = .{
674 .type = .empty_tuple,
675 .items = .empty,
676 } },
677};
678
679/// State that is mutable during semantic analysis. This data is not used for
680/// equality or hashing.
681pub const FuncAnalysis = packed struct(u32) {
682 state: AnalysisState,
683 _: u30 = 0,
684};
685
686/// An index into `string_bytes`.
687pub const String = enum(u32) {
688 /// An empty string.
689 empty = 0,
690 _,
691
692 pub const WithLen = struct {
693 string: String,
694 len: u32,
695
696 pub fn toSlice(self: WithLen, ip: *const InternPool) []const u8 {
697 return ip.string_bytes.items[@intFromEnum(self.string)..][0..@intCast(self.len)];
698 }
699
700 pub fn tryToNullTerminatedString(string: WithLen, ip: *InternPool, gpa: Allocator) !NullTerminatedString {
701 return string.string.tryToNullTerminatedString(string.len, ip, gpa);
702 }
703 };
704
705 pub fn toSlice(string: String, len: u64, ip: *const InternPool) []const u8 {
706 return ip.string_bytes.items[@intFromEnum(string)..][0..@intCast(len)];
707 }
708
709 pub fn withLen(string: String, len: u64) WithLen {
710 return .{ .string = string, .len = @intCast(len) };
711 }
712
713 pub fn at(string: String, index: u64, ip: *const InternPool) u8 {
714 return ip.string_bytes.items[@intCast(@intFromEnum(string) + index)];
715 }
716
717 pub fn toNullTerminatedString(string: String, len: u64, ip: *const InternPool) NullTerminatedString {
718 assert(std.mem.indexOfScalar(u8, string.toSlice(len, ip), 0) == null);
719 assert(string.at(len, ip) == 0);
720 return @enumFromInt(@intFromEnum(string));
721 }
722
723 pub fn tryToNullTerminatedString(
724 string: String,
725 len: u64,
726 ip: *InternPool,
727 gpa: Allocator,
728 ) !NullTerminatedString {
729 const slice = string.toSlice(len, ip);
730 if (std.mem.indexOfScalar(u8, slice, 0)) |_| {
731 return error.HasNulls;
732 }
733 if (string.at(len, ip) == 0) {
734 return @enumFromInt(@intFromEnum(string));
735 }
736 return ip.getOrPutString(gpa, slice, .no_embedded_nulls);
737 }
738};
739
740pub const NullTerminatedString = enum(u32) {
741 empty = 0,
742 _,
743
744 pub fn toString(self: NullTerminatedString) String {
745 return @enumFromInt(@intFromEnum(self));
746 }
747
748 pub fn toSlice(string: NullTerminatedString, ip: *const InternPool) [:0]const u8 {
749 const slice = ip.string_bytes.items[@intFromEnum(string)..];
750 return slice[0..std.mem.indexOfScalar(u8, slice, 0).? :0];
751 }
752
753 pub fn length(string: NullTerminatedString, ip: *const InternPool) u32 {
754 return @intCast(string.toSlice(ip).len);
755 }
756
757 pub fn eqlSlice(string: NullTerminatedString, slice: []const u8, ip: *const InternPool) bool {
758 return std.mem.eql(u8, string.toSlice(ip), slice);
759 }
760
761 const Adapter = struct {
762 strings: []const NullTerminatedString,
763
764 pub fn eql(ctx: @This(), a: NullTerminatedString, b_void: void, b_map_index: usize) bool {
765 _ = b_void;
766 return a == ctx.strings[b_map_index];
767 }
768
769 pub fn hash(ctx: @This(), a: NullTerminatedString) u32 {
770 _ = ctx;
771 return std.hash.uint32(@intFromEnum(a));
772 }
773 };
774
775 const FormatData = struct {
776 string: NullTerminatedString,
777 ip: *const InternPool,
778 };
779
780 fn format(
781 data: FormatData,
782 comptime specifier: []const u8,
783 _: std.fmt.FormatOptions,
784 writer: anytype,
785 ) @TypeOf(writer).Error!void {
786 const slice = data.string.toSlice(data.ip);
787 if (comptime std.mem.eql(u8, specifier, "")) {
788 try writer.writeAll(slice);
789 } else if (comptime std.mem.eql(u8, specifier, "i")) {
790 try writer.print("{p}", .{std.zig.fmtId(slice)});
791 } else @compileError("invalid format string '" ++ specifier ++ "' for '" ++ @typeName(NullTerminatedString) ++ "'");
792 }
793
794 pub fn fmt(self: NullTerminatedString, ip: *const InternPool) std.fmt.Formatter(format) {
795 return .{ .data = .{ .string = self, .ip = ip } };
796 }
797
798 pub const Slice = Extra.Slice(NullTerminatedString);
799};
800
801pub const TrackedInst = extern struct {
802 path_digest: Cache.BinDigest,
803 inst: Hir.Inst.Index,
804
805 comptime {
806 // The fields should be tightly packed. See also serialization logic in `Compilation.saveState`.
807 assert(@sizeOf(@This()) == Cache.bin_digest_len + @sizeOf(Hir.Inst.Index));
808 }
809
810 pub const Index = enum(u32) {
811 _,
812 pub fn resolve(i: TrackedInst.Index, ip: *const InternPool) Hir.Inst.Index {
813 return i.get(ip).inst;
814 }
815
816 pub fn get(i: TrackedInst.Index, ip: *const InternPool) TrackedInst {
817 return ip.tracked_insts.keys()[@intFromEnum(i)];
818 }
819
820 pub fn toOptional(i: TrackedInst.Index) Optional {
821 return @enumFromInt(@intFromEnum(i));
822 }
823
824 pub const Optional = enum(u32) {
825 none = std.math.maxInt(u32),
826 _,
827
828 pub fn unwrap(opt: Optional) ?TrackedInst.Index {
829 return switch (opt) {
830 .none => null,
831 _ => @enumFromInt(@intFromEnum(opt)),
832 };
833 }
834 };
835 };
836
837 pub fn jsonStringify(i: *const TrackedInst, json_writer: anytype) !void {
838 const jw = core.jsonWriterCast(json_writer);
839 try jw.beginObject();
840 try jw.objectField("path_digest");
841 try jw.write(std.fmt.bytesToHex(i.path_digest, .lower));
842 try jw.objectField("inst");
843 try jw.write(@intFromEnum(i.inst));
844 try jw.endObject();
845 }
846};
847
848pub const DeclIndex = enum(u32) {
849 _,
850
851 pub fn toOptional(i: DeclIndex) Optional {
852 return @enumFromInt(@intFromEnum(i));
853 }
854
855 pub const Optional = enum(u32) {
856 none = std.math.maxInt(u32),
857 _,
858
859 pub fn init(oi: ?DeclIndex) Optional {
860 return @enumFromInt(@intFromEnum(oi orelse return .none));
861 }
862
863 pub fn unwrap(oi: Optional) ?DeclIndex {
864 if (oi == .none) return null;
865 return @enumFromInt(@intFromEnum(oi));
866 }
867 };
868};
869
870pub const NamespaceIndex = enum(u32) {
871 _,
872
873 pub fn toOptional(i: NamespaceIndex) Optional {
874 return @enumFromInt(@intFromEnum(i));
875 }
876
877 pub const Optional = enum(u32) {
878 none = std.math.maxInt(u32),
879 _,
880
881 pub fn init(oi: ?NamespaceIndex) Optional {
882 return @enumFromInt(@intFromEnum(oi orelse return .none));
883 }
884
885 pub fn unwrap(oi: Optional) ?NamespaceIndex {
886 if (oi == .none) return null;
887 return @enumFromInt(@intFromEnum(oi));
888 }
889 };
890};
891
892const SimpleValue = enum {
893 true,
894 false,
895 void,
896
897 pub fn key(self: SimpleValue) Key {
898 return .{ .simple_value = self };
899 }
900};
901
902const SimpleType = enum {
903 @"opaque",
904 int32,
905 float,
906 string,
907 bool,
908 never,
909 type,
910 numeric_literal,
911
912 pub fn key(self: SimpleType) Key {
913 return .{ .simple_type = self };
914 }
915};
916
917pub const Key = union(enum) {
918 // Values
919 comptime_float: f64,
920 int32: i32,
921 float: f64,
922 string: []const u8,
923 simple_value: SimpleValue,
924 struct_value: StructValue,
925 func: Func,
926 array_value: ArrayValue,
927 opaque_value: Value,
928 tuple_value: TupleValue,
929 // Types
930 simple_type: SimpleType,
931 function_type: FunctionType,
932 struct_type: StructType,
933 array_type: ArrayType,
934 tuple_type: TupleType,
935 external_value: ExternalValue,
936
937 const Adapter = struct {
938 intern_pool: *const InternPool,
939
940 pub fn eql(ctx: @This(), a: Key, b_void: void, b_map_index: usize) bool {
941 _ = b_void;
942 if (ctx.intern_pool.items.items(.tag)[b_map_index] == .removed) return false;
943 return ctx.intern_pool.valueToKey(@enumFromInt(b_map_index)).eql(a, ctx.intern_pool);
944 }
945
946 pub fn hash(ctx: @This(), a: Key) u32 {
947 return a.hash32(ctx.intern_pool);
948 }
949 };
950
951 pub const FunctionType = struct {
952 param_types: Type.Slice,
953 /// If a return type is missing, it is inferred and not resolved yet.
954 /// When analysis figures out a return type, a new `FunctionType` with
955 /// the resolved return type.
956 return_type: ?Type,
957
958 pub const Resolved = struct {
959 param_types: Type.Slice,
960 return_type: Type,
961 };
962
963 pub fn hash(self: FunctionType, ip: *const InternPool, hasher: *Hash) void {
964 const t = tracer.trace(@src());
965 defer t.end();
966
967 for (self.param_types.get(ip)) |param_type| {
968 std.hash.autoHash(hasher, param_type);
969 }
970 std.hash.autoHash(hasher, self.return_type);
971 }
972
973 pub fn eql(a: FunctionType, b: FunctionType, ip: *const InternPool) bool {
974 return std.mem.eql(Type, a.param_types.get(ip), b.param_types.get(ip)) and
975 a.return_type == b.return_type;
976 }
977 };
978
979 pub const StructType = struct {
980 field_keys: NullTerminatedString.Slice,
981 field_types: Type.Slice,
982
983 /// TODO: store where the struct is declared to make this a nomial type
984 pub fn hash(self: StructType, ip: *const InternPool, hasher: *Hash) void {
985 for (self.field_keys.get(ip)) |value| {
986 std.hash.autoHash(hasher, value);
987 }
988 for (self.field_types.get(ip)) |value| {
989 std.hash.autoHash(hasher, value);
990 }
991 }
992 };
993
994 pub const StructValue = struct {
995 ty: Type,
996 field_values: Value.Slice,
997
998 pub fn hash(self: StructValue, ip: *const InternPool, hasher: *Hash) void {
999 std.hash.autoHash(hasher, self.ty);
1000 for (self.field_values.get(ip)) |value| {
1001 std.hash.autoHash(hasher, value);
1002 }
1003 }
1004 };
1005
1006 pub const ArrayType = struct {
1007 item_type: Type,
1008
1009 pub fn hash(self: ArrayType, ip: *const InternPool, hasher: *Hash) void {
1010 _ = ip;
1011 std.hash.autoHash(hasher, self.item_type);
1012 }
1013 };
1014
1015 pub const TupleType = struct {
1016 items: Type.Slice,
1017
1018 pub fn hash(self: TupleType, ip: *const InternPool, hasher: *Hash) void {
1019 _ = ip;
1020 std.hash.autoHashStrat(hasher, self.items, .Deep);
1021 }
1022 };
1023
1024 pub const ExternalValue = struct {
1025 /// A list of strings to generate the property access
1026 /// so `console.log` would be .{ "console", "log" }
1027 key: NullTerminatedString.Slice,
1028
1029 pub fn hash(self: ExternalValue, ip: *const InternPool, hasher: *Hash) void {
1030 std.hash.autoHashStrat(hasher, self.key.get(ip), .Shallow);
1031 }
1032 };
1033
1034 pub const ArrayValue = struct {
1035 /// This is the array type, not the item type
1036 type: Type,
1037 items: Value.Slice,
1038
1039 pub fn hash(self: ArrayValue, ip: *const InternPool, hasher: *Hash) void {
1040 std.hash.autoHash(hasher, self.type);
1041 std.hash.autoHashStrat(hasher, self.items.get(ip), .Deep);
1042 }
1043 };
1044
1045 pub const TupleValue = struct {
1046 /// This is the tuple type, not the item type
1047 type: Type,
1048 items: Value.Slice,
1049
1050 pub fn hash(self: TupleValue, ip: *const InternPool, hasher: *Hash) void {
1051 _ = ip;
1052 std.hash.autoHash(hasher, self.type);
1053 std.hash.autoHashStrat(hasher, self.items, .Deep);
1054 }
1055 };
1056
1057 pub const Func = struct {
1058 ty: Type,
1059 owner_decl: DeclIndex,
1060 teg_body_inst: TrackedInst.Index,
1061 analysis: Extra.Index(AnalysisState),
1062
1063 pub fn hash(self: Func, ip: *const InternPool, hasher: *Hash) void {
1064 _ = ip;
1065 std.hash.autoHash(hasher, self.ty);
1066 std.hash.autoHash(hasher, self.owner_decl);
1067 std.hash.autoHash(hasher, self.teg_body_inst);
1068 }
1069
1070 /// This should only be used to convert an inferred return type into a reified return type.
1071 pub fn updateType(self: Func, ip: *InternPool, new_type: Type) void {
1072 assert(new_type.tag(ip) == .function_type);
1073 ip.extra.set(Type, @intFromEnum(self.analysis) + Tag.FuncDecl.ty_index, new_type);
1074 }
1075 };
1076
1077 pub fn hash32(key: Key, ip: *const InternPool) u32 {
1078 return @truncate(key.hash64(ip));
1079 }
1080
1081 pub fn hash64(key: Key, ip: *const InternPool) u64 {
1082 const t = tracer.trace(@src());
1083 defer t.end();
1084
1085 const asBytes = std.mem.asBytes;
1086 const KeyTag = @typeInfo(Key).@"union".tag_type.?;
1087 const seed = @intFromEnum(@as(KeyTag, key));
1088
1089 return switch (key) {
1090 inline .int32,
1091 .simple_value,
1092 .simple_type,
1093 .opaque_value,
1094 => |x| Hash.hash(seed, asBytes(&x)),
1095 .string,
1096 => |x| Hash.hash(seed, x),
1097 .float, .comptime_float => |x| Hash.hash(seed, asBytes(&Float.assertPure(x))),
1098 inline .function_type,
1099 .func,
1100 .struct_value,
1101 .struct_type,
1102 .array_value,
1103 .array_type,
1104 .external_value,
1105 .tuple_type,
1106 .tuple_value,
1107 => |x| {
1108 var hasher = Hash.init(seed);
1109 x.hash(ip, &hasher);
1110 return hasher.final();
1111 },
1112 };
1113 }
1114
1115 pub fn eql(a: Key, b: Key, ip: *const InternPool) bool {
1116 const t = tracer.trace(@src());
1117 defer t.end();
1118
1119 const KeyTag = @typeInfo(Key).@"union".tag_type.?;
1120 const a_tag: KeyTag = a;
1121 const b_tag: KeyTag = b;
1122 if (a_tag != b_tag) return false;
1123 return switch (a) {
1124 inline .int32,
1125 .simple_value,
1126 .simple_type,
1127 .opaque_value,
1128 => |x, tag| x == @field(b, @tagName(tag)),
1129 .string,
1130 => |x| std.mem.eql(u8, x, b.string),
1131 .float => |x| Float.assertPure(x) == Float.assertPure(b.float),
1132 .comptime_float => |x| Float.assertPure(x) == Float.assertPure(b.comptime_float),
1133 .function_type => |x| x.eql(b.function_type, ip),
1134 .func => |a_info| {
1135 const b_info = b.func;
1136 if (a_info.owner_decl != b_info.owner_decl)
1137 return false;
1138 if (a_info.ty == b_info.ty)
1139 return true;
1140
1141 // TODO: zig has something extra here for inferred error sets
1142 return false;
1143 },
1144 .struct_type => {
1145 return false; // structs are nominal
1146 },
1147 .struct_value => |a_info| {
1148 const b_info = b.struct_value;
1149 return a_info.ty == b_info.ty and
1150 std.mem.eql(Value, a_info.field_values.get(ip), b_info.field_values.get(ip));
1151 },
1152 .array_type => |a_info| {
1153 return a_info.item_type == b.array_type.item_type;
1154 },
1155 .array_value => |a_info| {
1156 const b_info = b.array_value;
1157 return a_info.type == b_info.type and
1158 std.mem.eql(Value, a_info.items.get(ip), b_info.items.get(ip));
1159 },
1160 .external_value => |a_info| {
1161 const b_info = b.external_value;
1162 return std.mem.eql(NullTerminatedString, a_info.key.get(ip), b_info.key.get(ip));
1163 },
1164 .tuple_type => |a_info| {
1165 const b_info = b.tuple_type;
1166 return a_info.items.len == b_info.items.len and
1167 std.mem.eql(Type, a_info.items.get(ip), b_info.items.get(ip));
1168 },
1169 .tuple_value => |a_info| {
1170 const b_info = b.tuple_value;
1171 return a_info.type == b_info.type and
1172 std.mem.eql(Value, a_info.items.get(ip), b_info.items.get(ip));
1173 },
1174 };
1175 }
1176};
1177
1178const EmbeddedNulls = enum {
1179 no_embedded_nulls,
1180 maybe_embedded_nulls,
1181
1182 const OptionalNullTerminatedString = @compileError("TODO");
1183 const OptionalString = @compileError("TODO");
1184
1185 fn StringType(comptime embedded_nulls: EmbeddedNulls) type {
1186 return switch (embedded_nulls) {
1187 .no_embedded_nulls => NullTerminatedString,
1188 .maybe_embedded_nulls => String,
1189 };
1190 }
1191
1192 fn OptionalStringType(comptime embedded_nulls: EmbeddedNulls) type {
1193 return switch (embedded_nulls) {
1194 .no_embedded_nulls => OptionalNullTerminatedString,
1195 .maybe_embedded_nulls => OptionalString,
1196 };
1197 }
1198};
1199
1200/// Represents a single entity which undergoes semantic analysis.
1201/// This is the "source" of an incremental dependency edge.
1202pub const AnalysisUnit = packed struct(u32) {
1203 kind: enum(u1) { decl, func },
1204 index: u31,
1205
1206 pub const Unwrapped = union(enum) {
1207 decl: DeclIndex,
1208 func: Value,
1209 };
1210
1211 pub fn unwrap(as: AnalysisUnit) Unwrapped {
1212 return switch (as.kind) {
1213 .decl => .{ .decl = @enumFromInt(as.index) },
1214 .func => .{ .func = @enumFromInt(as.index) },
1215 };
1216 }
1217
1218 pub fn wrap(raw: Unwrapped) AnalysisUnit {
1219 return switch (raw) {
1220 .decl => |decl| .{ .kind = .decl, .index = @intCast(@intFromEnum(decl)) },
1221 .func => |func| .{ .kind = .func, .index = @intCast(@intFromEnum(func)) },
1222 };
1223 }
1224
1225 pub fn toOptional(as: AnalysisUnit) Optional {
1226 return @enumFromInt(@as(u32, @bitCast(as)));
1227 }
1228
1229 pub const Optional = enum(u32) {
1230 none = std.math.maxInt(u32),
1231 _,
1232
1233 pub fn unwrap(opt: Optional) ?AnalysisUnit {
1234 return switch (opt) {
1235 .none => null,
1236 _ => @bitCast(@intFromEnum(opt)),
1237 };
1238 }
1239 };
1240
1241 pub fn dump(au: AnalysisUnit, ip: *const InternPool) std.fmt.Formatter(formatImpl) {
1242 return .{ .data = .{ .au = au, .ip = ip } };
1243 }
1244
1245 fn formatImpl(
1246 data: struct { au: AnalysisUnit, ip: *const InternPool },
1247 comptime unused: []const u8,
1248 _: std.fmt.FormatOptions,
1249 w: std.io.AnyWriter,
1250 ) !void {
1251 comptime assert(unused.len == 0);
1252 try w.print("{s}: ", .{@tagName(data.au.kind)});
1253 switch (data.au.unwrap()) {
1254 .decl => |index| try w.print("^{d}", .{@intFromEnum(index)}),
1255 .func => |value| try w.print("'{s}'", .{
1256 data.ip.declPtrConst(value.toKey(data.ip).func.owner_decl).name.toSlice(data.ip),
1257 }),
1258 }
1259 }
1260};
1261
1262/// Every AU has a state.
1263/// For Decls, state is stored on the decl
1264/// For Functions, state is stored on the Key.Func
1265pub const AnalysisState = enum(u2) {
1266 /// This Unit corresponds to an AST Node that has not been referenced yet, and therefore
1267 /// because of Zig's lazy declaration analysis, it will remain unanalyzed until referenced.
1268 unreferenced,
1269 in_progress,
1270 complete,
1271};
1272
1273pub const Dependee = union(enum) {
1274 src_hash: TrackedInst.Index,
1275 decl_val: DeclIndex,
1276 resolved_func: Value,
1277};
1278
1279pub const DepEntry = extern struct {
1280 /// If null, this is a dummy entry. `next_dependee` is undefined. This is the first
1281 /// entry in one of `*_deps`, and does not appear in any list by `first_dependency`,
1282 /// but is not in `free_dep_entries` since `*_deps` stores a reference to it.
1283 depender: AnalysisUnit.Optional,
1284 /// Index into `dep_entries` forming a doubly linked list of all dependencies on this dependee.
1285 /// Used to iterate all dependers for a given dependee during an update.
1286 /// null if this is the end of the list.
1287 next: DepEntry.Index.Optional,
1288 /// The other link for `next`.
1289 /// null if this is the start of the list.
1290 prev: DepEntry.Index.Optional,
1291 /// Index into `dep_entries` forming a singly linked list of dependencies *of* `depender`.
1292 /// Used to efficiently remove all `DepEntry`s for a single `depender` when it is re-analyzed.
1293 /// null if this is the end of the list.
1294 next_dependee: DepEntry.Index.Optional,
1295
1296 pub const Index = enum(u32) {
1297 _,
1298
1299 pub fn toOptional(dep: DepEntry.Index) Optional {
1300 return @enumFromInt(@intFromEnum(dep));
1301 }
1302
1303 pub const Optional = enum(u32) {
1304 none = std.math.maxInt(u32),
1305 _,
1306 pub fn unwrap(opt: Optional) ?DepEntry.Index {
1307 return switch (opt) {
1308 .none => null,
1309 _ => @enumFromInt(@intFromEnum(opt)),
1310 };
1311 }
1312 };
1313 };
1314};
1315
1316// implementations:
1317
1318/// To construct, instantiate `.{}` then call this.
1319pub fn init(ip: *InternPool, gpa: Allocator) !void {
1320 const t = tracer.trace(@src());
1321 defer t.end();
1322
1323 assert(ip.items.len == 0);
1324
1325 // Reserve string index 0 for an empty string.
1326 assert((try ip.getOrPutString(gpa, "", .no_embedded_nulls)) == .empty);
1327
1328 // So that we can use `catch unreachable` below.
1329 try ip.items.ensureUnusedCapacity(gpa, static_keys.len);
1330 try ip.map.ensureUnusedCapacity(gpa, static_keys.len);
1331 try ip.extra.list.ensureUnusedCapacity(gpa, static_keys.len);
1332
1333 // This inserts all the statically known values into the intern pool in the
1334 // order expected.
1335 for (static_keys) |key| {
1336 _ = ip.get(gpa, key) catch unreachable;
1337 }
1338
1339 if (core.runtime_safety) {
1340 // Sanity check.
1341 assert(ip.valueToKey(.bool_true).simple_value == .true);
1342 assert(ip.valueToKey(.bool_false).simple_value == .false);
1343 }
1344
1345 assert(ip.items.len == static_keys.len);
1346}
1347
1348pub fn deinit(ip: *InternPool, gpa: Allocator) void {
1349 const t = tracer.trace(@src());
1350 defer t.end();
1351
1352 ip.map.deinit(gpa);
1353 ip.items.deinit(gpa);
1354 ip.extra.deinit(gpa);
1355 // ip.limbs.deinit(gpa);
1356 ip.string_bytes.deinit(gpa);
1357
1358 ip.allocated_decls.deinit(gpa);
1359 ip.decls_free_list.deinit(gpa);
1360
1361 var namespaces = ip.allocated_namespaces.iterator(0);
1362 while (namespaces.next()) |ns| {
1363 ns.decls.deinit(gpa);
1364 }
1365
1366 ip.namespaces_free_list.deinit(gpa);
1367 ip.allocated_namespaces.deinit(gpa);
1368
1369 // for (ip.maps.items) |*map| map.deinit(gpa);
1370 // ip.maps.deinit(gpa);
1371
1372 ip.string_table.deinit(gpa);
1373
1374 ip.tracked_insts.deinit(gpa);
1375
1376 ip.src_hash_deps.deinit(gpa);
1377 ip.decl_val_deps.deinit(gpa);
1378 // ip.func_ies_deps.deinit(gpa);
1379 // ip.namespace_deps.deinit(gpa);
1380 // ip.namespace_name_deps.deinit(gpa);
1381
1382 ip.first_dependency.deinit(gpa);
1383
1384 ip.dep_entries.deinit(gpa);
1385 ip.free_dep_entries.deinit(gpa);
1386
1387 ip.* = undefined;
1388}
1389
1390pub fn valueToKey(ip: *const InternPool, index: Value) Key {
1391 assert(index != .none);
1392 const item: Item = ip.items.get(@intFromEnum(index));
1393 const data = item.data;
1394 return switch (item.tag) {
1395 .removed => unreachable,
1396
1397 .simple_type => .{ .simple_type = data.decode(.simple_type, item.tag) },
1398 .simple_value => .{ .simple_value = data.decode(.simple_value, item.tag) },
1399 .opaque_value => .{ .opaque_value = data.decode(.opaque_value, item.tag) },
1400 .int32 => .{ .int32 = data.decode(.int32, item.tag) },
1401 .float => .{ .float = data.decode(.float, item.tag).get(ip).decode() },
1402 .comptime_float => .{
1403 .comptime_float = data.decode(.comptime_float, item.tag).get(ip).decode(),
1404 },
1405 .string => .{ .string = data.decode(.string, item.tag).get(ip).toSlice(ip) },
1406 .func => {
1407 const base_index = data.decode(.func, item.tag);
1408 const func = base_index.get(ip);
1409 return .{ .func = .{
1410 .ty = func.ty,
1411 .owner_decl = func.owner_decl,
1412 .teg_body_inst = func.teg_body_inst,
1413 .analysis = @enumFromInt(@intFromEnum(base_index)),
1414 } };
1415 },
1416 .function_type => .{
1417 .function_type = ip.extraTypeFunction(data.decode(.function_type, item.tag)),
1418 },
1419 .struct_type => {
1420 const payload: Tag.StructType, var trail =
1421 data.decode(.struct_type, item.tag).getTrail(ip);
1422
1423 return .{ .struct_type = .{
1424 .field_keys = trail.readNullTerminatedStringSlice(payload.fields_len),
1425 .field_types = trail.readTypeSlice(payload.fields_len),
1426 } };
1427 },
1428 .struct_value => {
1429 const payload: Tag.StructValue, var trail =
1430 data.decode(.struct_value, item.tag).getTrail(ip);
1431
1432 return .{ .struct_value = .{
1433 .ty = payload.ty,
1434 .field_values = trail.readValueSlice(
1435 payload.ty.value()
1436 .valueData(ip, .struct_type)
1437 .get(ip).fields_len,
1438 ),
1439 } };
1440 },
1441 .array_type => {
1442 const payload: Tag.ArrayType = data.decode(.array_type, item.tag).get(ip);
1443 return .{ .array_type = .{
1444 .item_type = payload.item_type,
1445 } };
1446 },
1447 .array_value => {
1448 const payload: Tag.ArrayValue, var trail = data.decode(.array_value, item.tag).getTrail(ip);
1449 return .{ .array_value = .{
1450 .type = payload.type,
1451 .items = trail.readValueSlice(payload.items_len),
1452 } };
1453 },
1454 .external_value => {
1455 const payload: Tag.ExternalValue, var trail = data.decode(.external_value, item.tag).getTrail(ip);
1456 return .{ .external_value = .{
1457 .key = trail.readNullTerminatedStringSlice(payload.key_count),
1458 } };
1459 },
1460 .tuple_type => {
1461 const payload: Tag.TupleType, var trail = data.decode(.tuple_type, item.tag).getTrail(ip);
1462 return .{ .tuple_type = .{
1463 .items = trail.readTypeSlice(payload.items_len),
1464 } };
1465 },
1466 .tuple_value => {
1467 const payload: Tag.TupleValue, var trail = data.decode(.tuple_value, item.tag).getTrail(ip);
1468 return .{ .tuple_value = .{
1469 .type = payload.type,
1470 .items = trail.readValueSlice(payload.items_len),
1471 } };
1472 },
1473 };
1474}
1475
1476// TODO: this function currently has a soft leak as `Key` requires slices into
1477// InternPool, so querying for a something with a slice (function_type) will
1478// always append it to `.extra` even if it becomes unused.
1479pub fn get(ip: *InternPool, gpa: Allocator, key: Key) !Value {
1480 const t = tracer.traceFmt(@src(), "{s}", .{@tagName(key)});
1481 defer t.end();
1482
1483 const adapter: Key.Adapter = .{ .intern_pool = ip };
1484 const gop = try ip.map.getOrPutAdapted(gpa, key, adapter);
1485 if (gop.found_existing) return @enumFromInt(gop.index);
1486 if (ip.items.len >= std.math.maxInt(u31) - 1) {
1487 return error.TooManyValues;
1488 }
1489
1490 const t2 = tracer.traceFmt(@src(), "(insert)", .{});
1491 defer t2.end();
1492
1493 try ip.items.ensureUnusedCapacity(gpa, 1);
1494 const item: Item = switch (key) {
1495 inline .int32,
1496 .simple_type,
1497 .simple_value,
1498 .opaque_value,
1499 => |s, tag| Item.encode(@field(Tag, @tagName(tag)), s),
1500 .string => |s| Item.encode(
1501 .string,
1502 try ip.extra.append(
1503 gpa,
1504 String.WithLen,
1505 (try ip.getOrPutString(gpa, s, .maybe_embedded_nulls)).withLen(s.len),
1506 ),
1507 ),
1508 .float => |f| Item.encode(
1509 .float,
1510 try ip.extra.append(gpa, Float, Float.encode(f)),
1511 ),
1512 .comptime_float => |f| Item.encode(
1513 .comptime_float,
1514 try ip.extra.append(gpa, Float, Float.encode(f)),
1515 ),
1516 .func => |f| brk: {
1517 const extra = try ip.extra.append(gpa, Tag.FuncDecl, .{
1518 .analysis = .{ .state = .unreferenced },
1519 .owner_decl = f.owner_decl,
1520 .ty = f.ty,
1521 .teg_body_inst = f.teg_body_inst,
1522 });
1523
1524 break :brk Item.encode(.func, extra);
1525 },
1526 .function_type => |f| brk: {
1527 for (f.param_types.get(ip)) |ty| ty.assertValid(ip);
1528
1529 const extra, var trail = try ip.extra.appendTrailing(gpa, Tag.FunctionType, .{
1530 .params_len = @intCast(f.param_types.len),
1531 .return_type = .init(f.return_type),
1532 }, f.param_types.len);
1533 defer trail.end();
1534 trail.writeSlice(f.param_types.get(ip));
1535 break :brk Item.encode(.function_type, extra);
1536 },
1537 .struct_type => |s| brk: {
1538 for (s.field_types.get(ip)) |ty| ty.assertValid(ip);
1539
1540 assert(s.field_keys.len == s.field_types.len);
1541 const extra, var trail = try ip.extra.appendTrailing(gpa, Tag.StructType, .{
1542 .fields_len = @intCast(s.field_keys.len),
1543 }, s.field_keys.len * 2);
1544 trail.writeSlice(s.field_keys.get(ip));
1545 trail.writeSlice(s.field_types.get(ip));
1546
1547 break :brk Item.encode(.struct_type, extra);
1548 },
1549 .struct_value => |s| brk: {
1550 assert(s.ty.value().toKey(ip).struct_type.field_keys.len == s.field_values.len);
1551 const extra, var trail = try ip.extra.appendTrailing(gpa, Tag.StructValue, .{
1552 .ty = s.ty,
1553 }, s.field_values.len);
1554 trail.writeSlice(s.field_values.get(ip));
1555 break :brk Item.encode(.struct_value, extra);
1556 },
1557 .array_type => |s| brk: {
1558 break :brk Item.encode(.array_type, try ip.extra.append(gpa, Tag.ArrayType, .{
1559 .item_type = s.item_type,
1560 }));
1561 },
1562 .array_value => |s| brk: {
1563 const extra, var trail = try ip.extra.appendTrailing(gpa, Tag.ArrayValue, .{
1564 .type = s.type,
1565 .items_len = @intCast(s.items.len),
1566 }, s.items.len);
1567 trail.writeSlice(s.items.get(ip));
1568 break :brk Item.encode(.array_value, extra);
1569 },
1570 .external_value => |s| brk: {
1571 const extra, var trail = try ip.extra.appendTrailing(gpa, Tag.ExternalValue, .{
1572 .key_count = @intCast(s.key.len),
1573 }, s.key.len);
1574 trail.writeSlice(s.key.get(ip));
1575 break :brk Item.encode(.external_value, extra);
1576 },
1577 .tuple_type => |s| brk: {
1578 const extra, var trail = try ip.extra.appendTrailing(gpa, Tag.TupleType, .{
1579 .items_len = @intCast(s.items.len),
1580 }, s.items.len);
1581 trail.writeSlice(s.items.get(ip));
1582 break :brk Item.encode(.tuple_type, extra);
1583 },
1584 .tuple_value => |s| brk: {
1585 const extra, var trail = try ip.extra.appendTrailing(gpa, Tag.TupleValue, .{
1586 .type = s.type,
1587 .items_len = @intCast(s.items.len),
1588 }, s.items.len);
1589 trail.writeSlice(s.items.get(ip));
1590 break :brk Item.encode(.tuple_value, extra);
1591 },
1592 };
1593 ip.items.appendAssumeCapacity(item);
1594 const index: Value = @enumFromInt(ip.items.len - 1);
1595 if (core.runtime_safety) {
1596 const key_added = ip.valueToKey(index);
1597 assert(key == .struct_type or key_added.eql(key, ip));
1598 }
1599 return index;
1600}
1601
1602fn extraTypeFunction(
1603 ip: *const InternPool,
1604 extra_index: Extra.Index(Tag.FunctionType),
1605) Key.FunctionType {
1606 const function_type, var trail = extra_index.getTrail(ip);
1607 const param_types = trail.readTypeSlice(function_type.params_len);
1608 const result: Key.FunctionType = .{
1609 .return_type = function_type.return_type.unwrap(),
1610 .param_types = param_types,
1611 };
1612 return result;
1613}
1614
1615pub fn getOrPutString(
1616 ip: *InternPool,
1617 gpa: Allocator,
1618 slice: []const u8,
1619 comptime embedded_nulls: EmbeddedNulls,
1620) Allocator.Error!embedded_nulls.StringType() {
1621 const t = tracer.trace(@src());
1622 defer t.end();
1623
1624 try ip.string_bytes.ensureUnusedCapacity(gpa, slice.len + 1);
1625 ip.string_bytes.appendSliceAssumeCapacity(slice);
1626 ip.string_bytes.appendAssumeCapacity(0);
1627 return ip.getOrPutTrailingString(gpa, slice.len + 1, embedded_nulls);
1628}
1629
1630fn getOrPutTrailingString(
1631 ip: *InternPool,
1632 gpa: Allocator,
1633 len: usize,
1634 comptime embedded_nulls: EmbeddedNulls,
1635) Allocator.Error!embedded_nulls.StringType() {
1636 const t = tracer.trace(@src());
1637 defer t.end();
1638
1639 const string_bytes = &ip.string_bytes;
1640 const str_index: u32 = @intCast(string_bytes.items.len - len);
1641 if (len > 0 and string_bytes.getLast() == 0) {
1642 _ = string_bytes.pop();
1643 } else {
1644 try string_bytes.ensureUnusedCapacity(gpa, 1);
1645 }
1646 const key: []const u8 = string_bytes.items[str_index..];
1647 const has_embedded_null = std.mem.indexOfScalar(u8, key, 0) != null;
1648 switch (embedded_nulls) {
1649 .no_embedded_nulls => assert(!has_embedded_null),
1650 .maybe_embedded_nulls => if (has_embedded_null) {
1651 string_bytes.appendAssumeCapacity(0);
1652 return @enumFromInt(str_index);
1653 },
1654 }
1655 const gop = try ip.string_table.getOrPutContextAdapted(
1656 gpa,
1657 key,
1658 std.hash_map.StringIndexAdapter{ .bytes = string_bytes },
1659 std.hash_map.StringIndexContext{ .bytes = string_bytes },
1660 );
1661 if (gop.found_existing) {
1662 string_bytes.shrinkRetainingCapacity(str_index);
1663 return @enumFromInt(gop.key_ptr.*);
1664 } else {
1665 gop.key_ptr.* = str_index;
1666 string_bytes.appendAssumeCapacity(0);
1667 return @enumFromInt(str_index);
1668 }
1669}
1670
1671pub fn trackInst(ip: *InternPool, gpa: Allocator, file: *Comp.File, inst: Hir.Inst.Index) Allocator.Error!TrackedInst.Index {
1672 const t = tracer.trace(@src());
1673 defer t.end();
1674
1675 const key: TrackedInst = .{
1676 .path_digest = file.path_digest.?,
1677 .inst = inst,
1678 };
1679 const gop = try ip.tracked_insts.getOrPut(gpa, key);
1680 return @enumFromInt(gop.index);
1681}
1682
1683pub fn addDependency(ip: *InternPool, gpa: Allocator, depender: AnalysisUnit, dependee: Dependee) Allocator.Error!void {
1684 const first_depender_dep: DepEntry.Index.Optional = if (ip.first_dependency.get(depender)) |idx| dep: {
1685 // The entry already exists, so there is capacity to overwrite it later.
1686 break :dep idx.toOptional();
1687 } else none: {
1688 // Ensure there is capacity available to add this dependency later.
1689 try ip.first_dependency.ensureUnusedCapacity(gpa, 1);
1690 break :none .none;
1691 };
1692
1693 // We're very likely to need space for a new entry - reserve it now to avoid
1694 // the need for error cleanup logic.
1695 if (ip.free_dep_entries.items.len == 0) {
1696 try ip.dep_entries.ensureUnusedCapacity(gpa, 1);
1697 }
1698
1699 // This block should allocate an entry and prepend it to the relevant `*_deps` list.
1700 // The `next` field should be correctly initialized; all other fields may be undefined.
1701 const new_index: DepEntry.Index = switch (dependee) {
1702 inline else => |dependee_payload, tag| new_index: {
1703 const gop = try switch (tag) {
1704 .src_hash => ip.src_hash_deps,
1705 .decl_val => ip.decl_val_deps,
1706 .resolved_func => ip.resolved_func_deps,
1707 }.getOrPut(gpa, dependee_payload);
1708
1709 if (gop.found_existing and ip.dep_entries.items[@intFromEnum(gop.value_ptr.*)].depender == .none) {
1710 // Dummy entry, so we can reuse it rather than allocating a new one!
1711 ip.dep_entries.items[@intFromEnum(gop.value_ptr.*)].next = .none;
1712 break :new_index gop.value_ptr.*;
1713 }
1714
1715 // Prepend a new dependency.
1716 const new_index: DepEntry.Index, const ptr = if (ip.free_dep_entries.pop()) |new_index| new: {
1717 break :new .{ new_index, &ip.dep_entries.items[@intFromEnum(new_index)] };
1718 } else .{ @enumFromInt(ip.dep_entries.items.len), ip.dep_entries.addOneAssumeCapacity() };
1719 ptr.next = if (gop.found_existing) gop.value_ptr.*.toOptional() else .none;
1720 gop.value_ptr.* = new_index;
1721 break :new_index new_index;
1722 },
1723 };
1724
1725 ip.dep_entries.items[@intFromEnum(new_index)].depender = depender.toOptional();
1726 ip.dep_entries.items[@intFromEnum(new_index)].prev = .none;
1727 ip.dep_entries.items[@intFromEnum(new_index)].next_dependee = first_depender_dep;
1728 ip.first_dependency.putAssumeCapacity(depender, new_index);
1729}
1730
1731pub fn declPtr(ip: *InternPool, index: DeclIndex) *Comp.Decl {
1732 return ip.allocated_decls.at(@intFromEnum(index));
1733}
1734
1735pub fn declPtrConst(ip: *const InternPool, index: DeclIndex) *const Comp.Decl {
1736 return ip.allocated_decls.at(@intFromEnum(index));
1737}
1738
1739pub fn namespacePtr(ip: *InternPool, index: NamespaceIndex) *Comp.Namespace {
1740 return ip.allocated_namespaces.at(@intFromEnum(index));
1741}
1742
1743pub fn namespacePtrConst(ip: *const InternPool, index: NamespaceIndex) *const Comp.Namespace {
1744 return ip.allocated_namespaces.at(@intFromEnum(index));
1745}
1746
1747pub fn createDecl(
1748 ip: *InternPool,
1749 gpa: Allocator,
1750 initialization: Comp.Decl,
1751) Allocator.Error!DeclIndex {
1752 const t = tracer.trace(@src());
1753 defer t.end();
1754
1755 if (ip.decls_free_list.pop()) |index| {
1756 ip.allocated_decls.at(@intFromEnum(index)).* = initialization;
1757 return index;
1758 }
1759 const ptr = try ip.allocated_decls.addOne(gpa);
1760 ptr.* = initialization;
1761 return @enumFromInt(ip.allocated_decls.len - 1);
1762}
1763
1764pub fn destroyDecl(ip: *InternPool, gpa: Allocator, index: DeclIndex) void {
1765 const t = tracer.trace(@src());
1766 defer t.end();
1767
1768 ip.declPtr(index).* = undefined;
1769 ip.decls_free_list.append(gpa, index) catch {
1770 // In order to keep `destroyDecl` a non-fallible function, we ignore memory
1771 // allocation failures here, instead leaking the Decl until garbage collection.
1772 };
1773}
1774
1775pub fn createNamespace(
1776 ip: *InternPool,
1777 gpa: Allocator,
1778 initialization: Comp.Namespace,
1779) Allocator.Error!NamespaceIndex {
1780 const t = tracer.trace(@src());
1781 defer t.end();
1782
1783 if (ip.namespaces_free_list.pop()) |index| {
1784 ip.allocated_namespaces.at(@intFromEnum(index)).* = initialization;
1785 return index;
1786 }
1787 const ptr = try ip.allocated_namespaces.addOne(gpa);
1788 ptr.* = initialization;
1789 return @enumFromInt(ip.allocated_namespaces.len - 1);
1790}
1791
1792pub fn destroyNamespace(ip: *InternPool, gpa: Allocator, index: NamespaceIndex) void {
1793 const t = tracer.trace(@src());
1794 defer t.end();
1795
1796 ip.namespacePtr(index).* = undefined;
1797 ip.namespaces_free_list.append(gpa, index) catch {
1798 // In order to keep `destroyNamespace` a non-fallible function, we ignore memory
1799 // allocation failures here, instead leaking the Namespace until garbage collection.
1800 };
1801}
1802
1803pub fn jsonStringify(ip: *const InternPool, json_writer: anytype) !void {
1804 const jw = core.jsonWriterCast(json_writer);
1805 try jw.beginObject();
1806 {
1807 try jw.objectField("values");
1808 try jw.beginArray();
1809 const hashes: []u32 = ip.map.entries.items(.hash);
1810 const values = ip.items.slice();
1811 for (
1812 @as([]Tag, values.items(.tag)),
1813 @as([]EncodedData, values.items(.data)),
1814 hashes,
1815 0..,
1816 ) |tag, encoded_data, hash, i| {
1817 if (tag == .removed) {
1818 try jw.write(null);
1819 continue;
1820 }
1821 try jw.beginObject();
1822 try jw.objectField("pretty");
1823 {
1824 var buf: [8192]u8 = undefined;
1825 try jw.print("", .{});
1826 try jw.stream.print("[{d}, ", .{i});
1827 try std.json.encodeJsonString(std.fmt.bufPrint(
1828 &buf,
1829 "{}",
1830 .{@as(Value, @enumFromInt(i)).dump(ip)},
1831 ) catch &buf, .{}, jw.stream);
1832 try jw.stream.print("]", .{});
1833 }
1834 try jw.objectField("tag");
1835 try jw.write(@tagName(tag));
1836 switch (tag) {
1837 .removed => unreachable,
1838 inline else => |comptime_tag| {
1839 const data = encoded_data.decode(comptime_tag, tag);
1840 _ = data;
1841 // try jw.objectField("data");
1842 // try jw.write(data);
1843 },
1844 }
1845 try jw.objectField("hash");
1846 try jw.write(hash);
1847 try jw.endObject();
1848 }
1849 try jw.endArray();
1850 }
1851 {
1852 try jw.objectField("string_bytes");
1853 try jw.write(ip.string_bytes.items);
1854 }
1855 {
1856 try jw.objectField("string_table");
1857 try jw.beginArray();
1858 var it = ip.string_table.keyIterator();
1859 while (it.next()) |k| {
1860 try jw.write(k.*);
1861 }
1862 try jw.endArray();
1863 }
1864 {
1865 try jw.objectField("tracked_insts");
1866 try jw.write(ip.tracked_insts.entries.items(.key));
1867 }
1868 try jw.endObject();
1869}
1870
1871const InternPool = @This();
1872
1873const std = @import("std");
1874const Allocator = std.mem.Allocator;
1875const Hash = std.hash.Wyhash;
1876const assert = std.debug.assert;
1877
1878const core = @import("mod.zig");
1879const Comp = core.Comp;
1880const Cache = core.Cache;
1881const Hir = core.Hir;
1882const Air = core.Air;
1883const dod = core.array;
1884const Float = dod.Float;
1885
1886const tracer = @import("tracer");
1887
1888test InternPool {
1889 const testing = std.testing;
1890 const a = testing.allocator;
1891
1892 std.testing.refAllDecls(@This());
1893
1894 var ip_struct: InternPool = .{};
1895 const ip = &ip_struct;
1896
1897 try ip.init(a);
1898 defer ip.deinit(a);
1899
1900 const str = try ip.getOrPutString(a, "hello", .no_embedded_nulls);
1901 try testing.expectEqualStrings("hello", str.toSlice(ip));
1902 const str2 = try ip.getOrPutString(a, "hello", .no_embedded_nulls);
1903 try testing.expectEqual(str, str2);
1904
1905 const int1 = try ip.get(a, .{ .int32 = 21483 });
1906 try testing.expectEqual(@as(i32, 21483), ip.valueToKey(int1).int32);
1907 const int2 = try ip.get(a, .{ .int32 = 21483 });
1908 try testing.expectEqual(int1, int2);
1909}