1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
const std = @import("std");
const assert = std.debug.assert;
const Order = std.math.Order;
const InternPool = @import("InternPool.zig");
const Type = @import("Type.zig");
const Value = @import("Value.zig");
const Zcu = @import("Zcu.zig");
const RangeSet = @This();
const LazySrcLoc = Zcu.LazySrcLoc;
pt: Zcu.PerThread,
ranges: std.ArrayList(Range),
pub const Range = struct {
first: InternPool.Index,
last: InternPool.Index,
src: LazySrcLoc,
};
pub fn init(allocator: std.mem.Allocator, pt: Zcu.PerThread) RangeSet {
return .{
.pt = pt,
.ranges = std.ArrayList(Range).init(allocator),
};
}
pub fn deinit(self: *RangeSet) void {
self.ranges.deinit();
}
pub fn add(
self: *RangeSet,
first: InternPool.Index,
last: InternPool.Index,
src: LazySrcLoc,
) !?LazySrcLoc {
const pt = self.pt;
const ip = &pt.zcu.intern_pool;
const ty = ip.typeOf(first);
assert(ty == ip.typeOf(last));
for (self.ranges.items) |range| {
assert(ty == ip.typeOf(range.first));
assert(ty == ip.typeOf(range.last));
if (Value.fromInterned(last).compareScalar(.gte, Value.fromInterned(range.first), Type.fromInterned(ty), pt) and
Value.fromInterned(first).compareScalar(.lte, Value.fromInterned(range.last), Type.fromInterned(ty), pt))
{
return range.src; // They overlap.
}
}
try self.ranges.append(.{
.first = first,
.last = last,
.src = src,
});
return null;
}
/// Assumes a and b do not overlap
fn lessThan(pt: Zcu.PerThread, a: Range, b: Range) bool {
const ty = Type.fromInterned(pt.zcu.intern_pool.typeOf(a.first));
return Value.fromInterned(a.first).compareScalar(.lt, Value.fromInterned(b.first), ty, pt);
}
pub fn spans(self: *RangeSet, first: InternPool.Index, last: InternPool.Index) !bool {
const pt = self.pt;
const ip = &pt.zcu.intern_pool;
assert(ip.typeOf(first) == ip.typeOf(last));
if (self.ranges.items.len == 0)
return false;
std.mem.sort(Range, self.ranges.items, pt, lessThan);
if (self.ranges.items[0].first != first or
self.ranges.items[self.ranges.items.len - 1].last != last)
{
return false;
}
var space: InternPool.Key.Int.Storage.BigIntSpace = undefined;
var counter = try std.math.big.int.Managed.init(self.ranges.allocator);
defer counter.deinit();
// look for gaps
for (self.ranges.items[1..], 0..) |cur, i| {
// i starts counting from the second item.
const prev = self.ranges.items[i];
// prev.last + 1 == cur.first
try counter.copy(Value.fromInterned(prev.last).toBigInt(&space, pt));
try counter.addScalar(&counter, 1);
const cur_start_int = Value.fromInterned(cur.first).toBigInt(&space, pt);
if (!cur_start_int.eql(counter.toConst())) {
return false;
}
}
return true;
}
|
