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