1const std = @import("std");
2const assert = std.debug.assert;
3const Allocator = std.mem.Allocator;
4const Zcu = @import("Zcu.zig");
5const InternPool = @import("InternPool.zig");
6const Type = @import("Type.zig");
7const Value = @import("Value.zig");
8
9/// We use a tagged union here because while it wastes a few bytes for some tags, having a fixed
10/// size for the type makes the common `aggregate` representation more efficient.
11/// For aggregates, the sentinel value, if any, *is* stored.
12pub const MutableValue = union(enum) {
13 /// An interned value.
14 interned: InternPool.Index,
15 /// An error union value which is a payload (not an error).
16 eu_payload: SubValue,
17 /// An optional value which is a payload (not `null`).
18 opt_payload: SubValue,
19 /// An aggregate consisting of a single repeated value.
20 repeated: SubValue,
21 /// An aggregate of `u8` consisting of "plain" bytes (no undefined elements).
22 bytes: Bytes,
23 /// An aggregate with arbitrary sub-values.
24 aggregate: Aggregate,
25 /// A slice, containing a pointer and length.
26 slice: Slice,
27 /// An instance of a union.
28 un: Union,
29
30 pub const SubValue = struct {
31 ty: InternPool.Index,
32 child: *MutableValue,
33 };
34 pub const Bytes = struct {
35 ty: InternPool.Index,
36 data: []u8,
37 };
38 pub const Aggregate = struct {
39 ty: InternPool.Index,
40 elems: []MutableValue,
41 };
42 pub const Slice = struct {
43 ty: InternPool.Index,
44 /// Must have the appropriate many-ptr type.
45 /// TODO: we want this to be an `InternPool.Index`, but `Sema.beginComptimePtrMutation` doesn't support it.
46 ptr: *MutableValue,
47 /// Must be of type `usize`.
48 /// TODO: we want this to be an `InternPool.Index`, but `Sema.beginComptimePtrMutation` doesn't support it.
49 len: *MutableValue,
50 };
51 pub const Union = struct {
52 ty: InternPool.Index,
53 tag: InternPool.Index,
54 payload: *MutableValue,
55 };
56
57 pub fn intern(mv: MutableValue, pt: Zcu.PerThread, arena: Allocator) Allocator.Error!Value {
58 const zcu = pt.zcu;
59 const comp = zcu.comp;
60 const io = comp.io;
61 return Value.fromInterned(switch (mv) {
62 .interned => |ip_index| ip_index,
63 .eu_payload => |sv| try pt.intern(.{ .error_union = .{
64 .ty = sv.ty,
65 .val = .{ .payload = (try sv.child.intern(pt, arena)).toIntern() },
66 } }),
67 .opt_payload => |sv| try pt.intern(.{ .opt = .{
68 .ty = sv.ty,
69 .val = (try sv.child.intern(pt, arena)).toIntern(),
70 } }),
71 .repeated => |sv| return pt.aggregateSplatValue(.fromInterned(sv.ty), try sv.child.intern(pt, arena)),
72 .bytes => |b| try pt.intern(.{ .aggregate = .{
73 .ty = b.ty,
74 .storage = .{ .bytes = try zcu.intern_pool.getOrPutString(comp.gpa, io, pt.tid, b.data, .maybe_embedded_nulls) },
75 } }),
76 .aggregate => |a| {
77 const elems = try arena.alloc(InternPool.Index, a.elems.len);
78 for (a.elems, elems) |mut_elem, *interned_elem| {
79 interned_elem.* = (try mut_elem.intern(pt, arena)).toIntern();
80 }
81 return pt.aggregateValue(.fromInterned(a.ty), elems);
82 },
83 .slice => |s| try pt.intern(.{ .slice = .{
84 .ty = s.ty,
85 .ptr = (try s.ptr.intern(pt, arena)).toIntern(),
86 .len = (try s.len.intern(pt, arena)).toIntern(),
87 } }),
88 .un => |u| try pt.internUnion(.{
89 .ty = u.ty,
90 .tag = u.tag,
91 .val = (try u.payload.intern(pt, arena)).toIntern(),
92 }),
93 });
94 }
95
96 /// Un-interns the top level of this `MutableValue`, if applicable.
97 /// * Non-error error unions use `eu_payload`
98 /// * Non-null optionals use `eu_payload
99 /// * Slices use `slice`
100 /// * Unions use `un` (excluding packed unions)
101 /// * Aggregates use `repeated` or `bytes` or `aggregate` (excluding packed structs)
102 /// If `!allow_bytes`, the `bytes` representation will not be used.
103 /// If `!allow_repeated`, the `repeated` representation will not be used.
104 pub fn unintern(
105 mv: *MutableValue,
106 pt: Zcu.PerThread,
107 arena: Allocator,
108 allow_bytes: bool,
109 allow_repeated: bool,
110 ) Allocator.Error!void {
111 const zcu = pt.zcu;
112 const ip = &zcu.intern_pool;
113 switch (mv.*) {
114 .interned => |ip_index| switch (ip.indexToKey(ip_index)) {
115 .opt => |opt| if (opt.val != .none) {
116 const mut_payload = try arena.create(MutableValue);
117 mut_payload.* = .{ .interned = opt.val };
118 mv.* = .{ .opt_payload = .{
119 .ty = opt.ty,
120 .child = mut_payload,
121 } };
122 },
123 .error_union => |eu| switch (eu.val) {
124 .err_name => {},
125 .payload => |payload| {
126 const mut_payload = try arena.create(MutableValue);
127 mut_payload.* = .{ .interned = payload };
128 mv.* = .{ .eu_payload = .{
129 .ty = eu.ty,
130 .child = mut_payload,
131 } };
132 },
133 },
134 .slice => |slice| {
135 const ptr = try arena.create(MutableValue);
136 const len = try arena.create(MutableValue);
137 ptr.* = .{ .interned = slice.ptr };
138 len.* = .{ .interned = slice.len };
139 mv.* = .{ .slice = .{
140 .ty = slice.ty,
141 .ptr = ptr,
142 .len = len,
143 } };
144 },
145 .un => |un| {
146 const payload = try arena.create(MutableValue);
147 payload.* = .{ .interned = un.val };
148 mv.* = .{ .un = .{
149 .ty = un.ty,
150 .tag = un.tag,
151 .payload = payload,
152 } };
153 },
154 .aggregate => |agg| switch (agg.storage) {
155 .bytes => |bytes| {
156 const len: usize = @intCast(ip.aggregateTypeLenIncludingSentinel(agg.ty));
157 assert(ip.childType(agg.ty) == .u8_type);
158 if (allow_bytes) {
159 const arena_bytes = try arena.alloc(u8, len);
160 @memcpy(arena_bytes, bytes.toSlice(len, ip));
161 mv.* = .{ .bytes = .{
162 .ty = agg.ty,
163 .data = arena_bytes,
164 } };
165 } else {
166 const mut_elems = try arena.alloc(MutableValue, len);
167 for (bytes.toSlice(len, ip), mut_elems) |b, *mut_elem| {
168 mut_elem.* = .{ .interned = try pt.intern(.{ .int = .{
169 .ty = .u8_type,
170 .storage = .{ .u64 = b },
171 } }) };
172 }
173 mv.* = .{ .aggregate = .{
174 .ty = agg.ty,
175 .elems = mut_elems,
176 } };
177 }
178 },
179 .elems => |elems| {
180 assert(elems.len == ip.aggregateTypeLenIncludingSentinel(agg.ty));
181 const mut_elems = try arena.alloc(MutableValue, elems.len);
182 for (elems, mut_elems) |interned_elem, *mut_elem| {
183 mut_elem.* = .{ .interned = interned_elem };
184 }
185 mv.* = .{ .aggregate = .{
186 .ty = agg.ty,
187 .elems = mut_elems,
188 } };
189 },
190 .repeated_elem => |val| {
191 if (allow_repeated) {
192 const repeated_val = try arena.create(MutableValue);
193 repeated_val.* = .{ .interned = val };
194 mv.* = .{ .repeated = .{
195 .ty = agg.ty,
196 .child = repeated_val,
197 } };
198 } else {
199 const len = ip.aggregateTypeLenIncludingSentinel(agg.ty);
200 const mut_elems = try arena.alloc(MutableValue, @intCast(len));
201 @memset(mut_elems, .{ .interned = val });
202 mv.* = .{ .aggregate = .{
203 .ty = agg.ty,
204 .elems = mut_elems,
205 } };
206 }
207 },
208 },
209 .undef => |ty_ip| switch (Type.fromInterned(ty_ip).zigTypeTag(zcu)) {
210 .@"struct", .array, .vector => |type_tag| {
211 const ty = Type.fromInterned(ty_ip);
212 if (type_tag == .@"struct" and ty.containerLayout(zcu) == .@"packed") return;
213 const opt_sent = ty.sentinel(zcu);
214 if (type_tag == .@"struct" or opt_sent != null or !allow_repeated) {
215 const len_no_sent = ip.aggregateTypeLen(ty_ip);
216 const elems = try arena.alloc(MutableValue, @intCast(len_no_sent + @intFromBool(opt_sent != null)));
217 switch (type_tag) {
218 .array, .vector => {
219 const elem_ty = ip.childType(ty_ip);
220 const undef_elem = try pt.intern(.{ .undef = elem_ty });
221 @memset(elems[0..@intCast(len_no_sent)], .{ .interned = undef_elem });
222 },
223 .@"struct" => for (elems[0..@intCast(len_no_sent)], 0..) |*mut_elem, i| {
224 const field_ty = ty.fieldType(i, zcu).toIntern();
225 mut_elem.* = .{ .interned = try pt.intern(.{ .undef = field_ty }) };
226 },
227 else => unreachable,
228 }
229 if (opt_sent) |s| elems[@intCast(len_no_sent)] = .{ .interned = s.toIntern() };
230 mv.* = .{ .aggregate = .{
231 .ty = ty_ip,
232 .elems = elems,
233 } };
234 } else {
235 const repeated_val = try arena.create(MutableValue);
236 repeated_val.* = .{
237 .interned = try pt.intern(.{ .undef = ip.childType(ty_ip) }),
238 };
239 mv.* = .{ .repeated = .{
240 .ty = ty_ip,
241 .child = repeated_val,
242 } };
243 }
244 },
245 .@"union" => switch (Type.fromInterned(ty_ip).containerLayout(zcu)) {
246 .auto, .@"packed" => {},
247 .@"extern" => {
248 const payload = try arena.create(MutableValue);
249 const backing_ty = try Type.fromInterned(ty_ip).externUnionBackingType(pt);
250 payload.* = .{ .interned = try pt.intern(.{ .undef = backing_ty.toIntern() }) };
251 mv.* = .{ .un = .{
252 .ty = ty_ip,
253 .tag = .none,
254 .payload = payload,
255 } };
256 },
257 },
258 .pointer => {
259 const ptr_ty = ip.indexToKey(ty_ip).ptr_type;
260 if (ptr_ty.flags.size != .slice) return;
261 const ptr = try arena.create(MutableValue);
262 const len = try arena.create(MutableValue);
263 ptr.* = .{ .interned = try pt.intern(.{ .undef = ip.slicePtrType(ty_ip) }) };
264 len.* = .{ .interned = .undef_usize };
265 mv.* = .{ .slice = .{
266 .ty = ty_ip,
267 .ptr = ptr,
268 .len = len,
269 } };
270 },
271 else => {},
272 },
273 else => {},
274 },
275 .bytes => |bytes| if (!allow_bytes) {
276 const elems = try arena.alloc(MutableValue, bytes.data.len);
277 for (bytes.data, elems) |byte, *interned_byte| {
278 interned_byte.* = .{ .interned = try pt.intern(.{ .int = .{
279 .ty = .u8_type,
280 .storage = .{ .u64 = byte },
281 } }) };
282 }
283 mv.* = .{ .aggregate = .{
284 .ty = bytes.ty,
285 .elems = elems,
286 } };
287 },
288 else => {},
289 }
290 }
291
292 /// Get a pointer to the `MutableValue` associated with a field/element.
293 /// The returned pointer can be safety mutated through to modify the field value.
294 /// The returned pointer is valid until the representation of `mv` changes.
295 pub fn elem(
296 mv: *MutableValue,
297 pt: Zcu.PerThread,
298 arena: Allocator,
299 field_idx: usize,
300 ) Allocator.Error!*MutableValue {
301 const zcu = pt.zcu;
302 const ip = &zcu.intern_pool;
303 // Convert to the `aggregate` representation.
304 switch (mv.*) {
305 .eu_payload, .opt_payload, .un => unreachable,
306 .interned => {
307 try mv.unintern(pt, arena, false, false);
308 },
309 .bytes => |bytes| {
310 const elems = try arena.alloc(MutableValue, bytes.data.len);
311 for (bytes.data, elems) |byte, *interned_byte| {
312 interned_byte.* = .{ .interned = try pt.intern(.{ .int = .{
313 .ty = .u8_type,
314 .storage = .{ .u64 = byte },
315 } }) };
316 }
317 mv.* = .{ .aggregate = .{
318 .ty = bytes.ty,
319 .elems = elems,
320 } };
321 },
322 .repeated => |repeated| {
323 const len = ip.aggregateTypeLenIncludingSentinel(repeated.ty);
324 const elems = try arena.alloc(MutableValue, @intCast(len));
325 @memset(elems, repeated.child.*);
326 mv.* = .{ .aggregate = .{
327 .ty = repeated.ty,
328 .elems = elems,
329 } };
330 },
331 .slice, .aggregate => {},
332 }
333 switch (mv.*) {
334 .aggregate => |*agg| return &agg.elems[field_idx],
335 .slice => |*slice| return switch (field_idx) {
336 Value.slice_ptr_index => slice.ptr,
337 Value.slice_len_index => slice.len,
338 else => unreachable,
339 },
340 else => unreachable,
341 }
342 }
343
344 /// Modify a single field of a `MutableValue` which represents an aggregate or slice, leaving others
345 /// untouched. When an entire field must be modified, this should be used in preference to `elemPtr`
346 /// to allow for an optimal representation.
347 /// For slices, uses `Value.slice_ptr_index` and `Value.slice_len_index`.
348 pub fn setElem(
349 mv: *MutableValue,
350 pt: Zcu.PerThread,
351 arena: Allocator,
352 field_idx: usize,
353 field_val: MutableValue,
354 ) Allocator.Error!void {
355 const zcu = pt.zcu;
356 const ip = &zcu.intern_pool;
357 const is_trivial_int = field_val.isTrivialInt(zcu);
358 try mv.unintern(pt, arena, is_trivial_int, true);
359 switch (mv.*) {
360 .interned,
361 .eu_payload,
362 .opt_payload,
363 .un,
364 => unreachable,
365 .slice => |*s| switch (field_idx) {
366 Value.slice_ptr_index => s.ptr.* = field_val,
367 Value.slice_len_index => s.len.* = field_val,
368 else => unreachable,
369 },
370 .bytes => |b| {
371 assert(is_trivial_int);
372 assert(field_val.typeOf(zcu).toIntern() == .u8_type);
373 b.data[field_idx] = @intCast(Value.fromInterned(field_val.interned).toUnsignedInt(zcu));
374 },
375 .repeated => |r| {
376 if (field_val.eqlTrivial(r.child.*)) return;
377 // We must switch to either the `aggregate` or the `bytes` representation.
378 const len_inc_sent = ip.aggregateTypeLenIncludingSentinel(r.ty);
379 if (Type.fromInterned(r.ty).zigTypeTag(zcu) != .@"struct" and
380 is_trivial_int and
381 Type.fromInterned(r.ty).childType(zcu).toIntern() == .u8_type and
382 r.child.isTrivialInt(zcu))
383 {
384 // We can use the `bytes` representation.
385 const bytes = try arena.alloc(u8, @intCast(len_inc_sent));
386 const repeated_byte = Value.fromInterned(r.child.interned).toUnsignedInt(zcu);
387 @memset(bytes, @intCast(repeated_byte));
388 bytes[field_idx] = @intCast(Value.fromInterned(field_val.interned).toUnsignedInt(zcu));
389 mv.* = .{ .bytes = .{
390 .ty = r.ty,
391 .data = bytes,
392 } };
393 } else {
394 // We must use the `aggregate` representation.
395 const mut_elems = try arena.alloc(MutableValue, @intCast(len_inc_sent));
396 @memset(mut_elems, r.child.*);
397 mut_elems[field_idx] = field_val;
398 mv.* = .{ .aggregate = .{
399 .ty = r.ty,
400 .elems = mut_elems,
401 } };
402 }
403 },
404 .aggregate => |a| {
405 a.elems[field_idx] = field_val;
406 const is_struct = Type.fromInterned(a.ty).zigTypeTag(zcu) == .@"struct";
407 // Attempt to switch to a more efficient representation.
408 const is_repeated = for (a.elems) |e| {
409 if (!e.eqlTrivial(field_val)) break false;
410 } else true;
411 if (!is_struct and is_repeated) {
412 // Switch to `repeated` repr
413 const mut_repeated = try arena.create(MutableValue);
414 mut_repeated.* = field_val;
415 mv.* = .{ .repeated = .{
416 .ty = a.ty,
417 .child = mut_repeated,
418 } };
419 } else if (!is_struct and is_trivial_int and Type.fromInterned(a.ty).childType(zcu).toIntern() == .u8_type) {
420 // See if we can switch to `bytes` repr
421 for (a.elems) |e| {
422 if (!e.isTrivialInt(zcu)) break;
423 } else {
424 const bytes = try arena.alloc(u8, a.elems.len);
425 for (a.elems, bytes) |elem_val, *b| {
426 b.* = @intCast(Value.fromInterned(elem_val.interned).toUnsignedInt(zcu));
427 }
428 mv.* = .{ .bytes = .{
429 .ty = a.ty,
430 .data = bytes,
431 } };
432 }
433 }
434 },
435 }
436 }
437
438 /// Get the value of a single field of a `MutableValue` which represents an aggregate or slice.
439 /// For slices, uses `Value.slice_ptr_index` and `Value.slice_len_index`.
440 pub fn getElem(
441 mv: MutableValue,
442 pt: Zcu.PerThread,
443 field_idx: usize,
444 ) Allocator.Error!MutableValue {
445 return switch (mv) {
446 .eu_payload,
447 .opt_payload,
448 => unreachable,
449 .interned => |ip_index| {
450 const ty = Type.fromInterned(pt.zcu.intern_pool.typeOf(ip_index));
451 switch (ty.zigTypeTag(pt.zcu)) {
452 .array, .vector => return .{ .interned = (try Value.fromInterned(ip_index).elemValue(pt, field_idx)).toIntern() },
453 .@"struct", .@"union" => return .{ .interned = (try Value.fromInterned(ip_index).fieldValue(pt, field_idx)).toIntern() },
454 .pointer => {
455 assert(ty.isSlice(pt.zcu));
456 return switch (field_idx) {
457 Value.slice_ptr_index => .{ .interned = Value.fromInterned(ip_index).slicePtr(pt.zcu).toIntern() },
458 Value.slice_len_index => .{ .interned = switch (pt.zcu.intern_pool.indexToKey(ip_index)) {
459 .undef => .undef_usize,
460 .slice => |s| s.len,
461 else => unreachable,
462 } },
463 else => unreachable,
464 };
465 },
466 else => unreachable,
467 }
468 },
469 .un => |un| {
470 // TODO assert the tag is correct
471 return un.payload.*;
472 },
473 .slice => |s| switch (field_idx) {
474 Value.slice_ptr_index => s.ptr.*,
475 Value.slice_len_index => s.len.*,
476 else => unreachable,
477 },
478 .bytes => |b| .{ .interned = try pt.intern(.{ .int = .{
479 .ty = .u8_type,
480 .storage = .{ .u64 = b.data[field_idx] },
481 } }) },
482 .repeated => |r| r.child.*,
483 .aggregate => |a| a.elems[field_idx],
484 };
485 }
486
487 fn isTrivialInt(mv: MutableValue, zcu: *Zcu) bool {
488 return switch (mv) {
489 else => false,
490 .interned => |ip_index| switch (zcu.intern_pool.indexToKey(ip_index)) {
491 else => false,
492 .int => true,
493 },
494 };
495 }
496
497 pub fn typeOf(mv: MutableValue, zcu: *Zcu) Type {
498 return switch (mv) {
499 .interned => |ip_index| Type.fromInterned(zcu.intern_pool.typeOf(ip_index)),
500 inline else => |x| Type.fromInterned(x.ty),
501 };
502 }
503
504 pub fn unpackOptional(mv: MutableValue, zcu: *Zcu) union(enum) {
505 undef,
506 null,
507 payload: MutableValue,
508 } {
509 return switch (mv) {
510 .opt_payload => |pl| return .{ .payload = pl.child.* },
511 .interned => |ip_index| switch (zcu.intern_pool.indexToKey(ip_index)) {
512 .undef => return .undef,
513 .opt => |opt| if (opt.val == .none) .null else .{ .payload = .{ .interned = opt.val } },
514 else => unreachable,
515 },
516 else => unreachable,
517 };
518 }
519
520 pub fn unpackErrorUnion(mv: MutableValue, zcu: *Zcu) union(enum) {
521 undef,
522 err: InternPool.NullTerminatedString,
523 payload: MutableValue,
524 } {
525 return switch (mv) {
526 .eu_payload => |pl| return .{ .payload = pl.child.* },
527 .interned => |ip_index| switch (zcu.intern_pool.indexToKey(ip_index)) {
528 .undef => return .undef,
529 .error_union => |eu| switch (eu.val) {
530 .err_name => |name| .{ .err = name },
531 .payload => |pl| .{ .payload = .{ .interned = pl } },
532 },
533 else => unreachable,
534 },
535 else => unreachable,
536 };
537 }
538
539 /// Fast equality checking which may return false negatives.
540 /// Used for deciding when to switch aggregate representations without fully
541 /// interning many values.
542 fn eqlTrivial(a: MutableValue, b: MutableValue) bool {
543 const Tag = @typeInfo(MutableValue).@"union".tag_type.?;
544 if (@as(Tag, a) != @as(Tag, b)) return false;
545 return switch (a) {
546 .interned => |a_ip| a_ip == b.interned,
547 .eu_payload => |a_pl| a_pl.ty == b.eu_payload.ty and a_pl.child.eqlTrivial(b.eu_payload.child.*),
548 .opt_payload => |a_pl| a_pl.ty == b.opt_payload.ty and a_pl.child.eqlTrivial(b.opt_payload.child.*),
549 .repeated => |a_rep| a_rep.ty == b.repeated.ty and a_rep.child.eqlTrivial(b.repeated.child.*),
550 .bytes => |a_bytes| a_bytes.ty == b.bytes.ty and std.mem.eql(u8, a_bytes.data, b.bytes.data),
551 .aggregate => |a_agg| {
552 const b_agg = b.aggregate;
553 if (a_agg.ty != b_agg.ty) return false;
554 if (a_agg.elems.len != b_agg.elems.len) return false;
555 for (a_agg.elems, b_agg.elems) |a_elem, b_elem| {
556 if (!a_elem.eqlTrivial(b_elem)) return false;
557 }
558 return true;
559 },
560 .slice => |a_slice| a_slice.ty == b.slice.ty and
561 a_slice.ptr.interned == b.slice.ptr.interned and
562 a_slice.len.interned == b.slice.len.interned,
563 .un => |a_un| a_un.ty == b.un.ty and a_un.tag == b.un.tag and a_un.payload.eqlTrivial(b.un.payload.*),
564 };
565 }
566};