Meg's Mirrors

zig

1	const RangeSet = @This();
2
3	list: std.MultiArrayList(Range),
4
5	pub const Range = struct {
6	first: Value,
7	last: Value,
8	src: LazySrcLoc,
9	};
10
11	pub const empty: RangeSet = .{ .list = .empty };
12
13	pub fn deinit(self: *RangeSet, allocator: Allocator) void {
14	self.list.deinit(allocator);
15	self.* = undefined;
16	}
17
18	pub fn ensureUnusedCapacity(set: *RangeSet, allocator: Allocator, additional_count: usize) Allocator.Error!void {
19	return set.list.ensureUnusedCapacity(allocator, additional_count);
20	}
21
22	pub fn addAssumeCapacity(set: *RangeSet, new: Range, ty: Type, zcu: *Zcu) ?Range {
23	assert(new.first.typeOf(zcu).eql(ty));
24	assert(new.last.typeOf(zcu).eql(ty));
25	assert(new.first.compareScalar(.lte, new.last, ty, zcu));
26
27	const idx = std.sort.lowerBound(Value, set.list.items(.last), @as(SearchCtx, .{
28	.val = new.first,
29	.zcu = zcu,
30	}), compare);
31
32	if (idx != set.list.len and // `new.first` is *not* greater than all `old.last`
33	new.last.compareScalar(.gte, set.list.items(.first)[idx], ty, zcu))
34	{
35	return set.list.get(idx); // `new` overlaps with existing range.
36	}
37	set.list.insertAssumeCapacity(idx, new);
38	return null;
39	}
40
41	pub fn spans(
42	set: *RangeSet,
43	allocator: Allocator,
44	first: Value,
45	last: Value,
46	ty: Type,
47	zcu: *Zcu,
48	) Allocator.Error!bool {
49	assert(first.typeOf(zcu).eql(ty));
50	assert(last.typeOf(zcu).eql(ty));
51	if (set.list.len == 0) return false;
52
53	assert(std.sort.isSorted(Value, set.list.items(.first), @as(SortCtx, .{ .ty = ty, .zcu = zcu }), lessThan));
54	assert(std.sort.isSorted(Value, set.list.items(.last), @as(SortCtx, .{ .ty = ty, .zcu = zcu }), lessThan));
55
56	if (!set.list.items(.first)[0].eql(first, ty, zcu) or
57	!set.list.items(.last)[set.list.len - 1].eql(last, ty, zcu))
58	{
59	return false;
60	}
61
62	const limbs = try allocator.alloc(
63	math.big.Limb,
64	math.big.int.calcTwosCompLimbCount(ty.intInfo(zcu).bits),
65	);
66	defer allocator.free(limbs);
67	var counter: math.big.int.Mutable = .init(limbs, 0);
68
69	var space: InternPool.Key.Int.Storage.BigIntSpace = undefined;
70
71	// look for gaps
72	for (
73	set.list.items(.first)[1..],
74	set.list.items(.last)[0 .. set.list.len - 1],
75	) |cur_first, prev_last| {
76	// prev_last + 1 == cur_first
77	counter.copy(prev_last.toBigInt(&space, zcu));
78	counter.addScalar(counter.toConst(), 1);
79
80	const cur_start_int = cur_first.toBigInt(&space, zcu);
81	if (!cur_start_int.eql(counter.toConst())) {
82	return false;
83	}
84	}
85
86	return true;
87	}
88
89	const SearchCtx = struct {
90	val: Value,
91	zcu: *const Zcu,
92	};
93	fn compare(ctx: SearchCtx, other: Value) math.Order {
94	return ctx.val.order(other, ctx.zcu);
95	}
96
97	const SortCtx = struct {
98	ty: Type,
99	zcu: *Zcu,
100	};
101	fn lessThan(ctx: SortCtx, a: Value, b: Value) bool {
102	return a.compareScalar(.lt, b, ctx.ty, ctx.zcu);
103	}
104
105	const std = @import("std");
106	const math = std.math;
107	const assert = std.debug.assert;
108	const Allocator = std.mem.Allocator;
109
110	const InternPool = @import("InternPool.zig");
111	const Type = @import("Type.zig");
112	const Value = @import("Value.zig");
113	const Zcu = @import("Zcu.zig");
114	const LazySrcLoc = Zcu.LazySrcLoc;