// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! An inclusive range of IPv6 addresses, from `first` to `last`. //! //! A range is what CIDR notation cannot write down. `2001:db8::a-2001:db8::14` is //! a perfectly ordinary thing for a DHCP pool or an access list to name, and //! it is not a network: it does not start on a power-of-two boundary and its //! size is not a power of two. Expressing it as networks takes four blocks, which //! `prefixes` will hand over, but the range is the thing that was meant and //! this is the type that holds it. //! //! Nothing in the IETF documents defines a text form for a range, so the one //! parsed and written here — two addresses with a `-` between them and no //! spaces — is a convention rather than a standard. It is the one `nmap` and //! most access lists use. const std = @import("std"); const json = @import("json.zig"); const Writer = std.Io.Writer; const Ipv6Address = @import("Ipv6Address.zig"); const Ipv6Network = @import("Ipv6Network.zig"); const Ipv6Range = @This(); /// The lowest address in the range. first: Ipv6Address, /// The highest address in the range, which is part of it. last: Ipv6Address, pub const InitError = error{ /// `last` was below `first`. A range is written low end first and an /// empty range cannot be represented, so there is nothing sensible to /// build from a pair the wrong way round. Inverted, }; /// Builds a range from its two ends, both of which are part of it. pub fn init(first: Ipv6Address, last: Ipv6Address) InitError!Ipv6Range { if (first.toInt() > last.toInt()) return error.Inverted; return .{ .first = first, .last = last }; } /// The range a network covers, from its network address to its last address. pub fn fromNetwork(n: Ipv6Network) Ipv6Range { return .{ .first = n.networkAddress(), .last = n.lastAddress() }; } /// The range holding one address. pub fn fromAddress(address: Ipv6Address) Ipv6Range { return .{ .first = address, .last = address }; } pub const ParseError = Ipv6Address.ParseError || InitError || error{ /// The text held no `-`, so there was only one address in it. A single /// address is a range of one, but it has to be built with `fromAddress` /// rather than parsed, so that text meant to name a range and missing /// half of it is an error rather than a range of one. MissingSeparator, }; /// Parses `first-last`, as in `2001:db8::a-2001:db8::14`. /// /// Both ends are parsed as strictly as `Ipv6Address.parse` parses anything, and /// no space is allowed around the `-`. `first` must not be above `last`. pub fn parse(text: []const u8) ParseError!Ipv6Range { const separator = std.mem.findScalar(u8, text, '-') orelse return error.MissingSeparator; const first = try Ipv6Address.parse(text[0..separator]); const last = try Ipv6Address.parse(text[separator + 1 ..]); return init(first, last); } /// Whether `text` is a valid range, discarding the reason when it is not. pub fn isValid(text: []const u8) bool { _ = parse(text) catch return false; return true; } /// The number of addresses in the range, which is never zero. The result is /// 129 bits wide because a range covering the whole address space does not fit in /// 128. pub fn addressCount(r: Ipv6Range) u129 { return @as(u129, r.last.toInt()) - r.first.toInt() + 1; } /// Whether the range holds exactly one address. pub fn isSingleAddress(r: Ipv6Range) bool { return r.first.eql(r.last); } /// Whether `address` falls inside the range. pub fn contains(r: Ipv6Range, address: Ipv6Address) bool { const value = address.toInt(); return value >= r.first.toInt() and value <= r.last.toInt(); } /// Whether every address of `other` is also in this range. pub fn containsRange(r: Ipv6Range, other: Ipv6Range) bool { return other.first.toInt() >= r.first.toInt() and other.last.toInt() <= r.last.toInt(); } /// Whether the two ranges have any address in common. pub fn overlaps(r: Ipv6Range, other: Ipv6Range) bool { return r.first.toInt() <= other.last.toInt() and other.first.toInt() <= r.last.toInt(); } /// The range as a single network, or null when it is not one. /// /// A range is a network exactly when it starts on a boundary its size allows /// and its size is a power of two, which is the same as saying that /// `prefixes` yields one block and stops. pub fn toNetwork(r: Ipv6Range) ?Ipv6Network { var it = r.prefixes(); const only = it.next() orelse return null; if (it.next() != null) return null; return only; } /// The smallest set of whole networks that covers the range exactly: no /// address outside the range, every address inside it, and no two blocks /// overlapping. /// /// This is the operation that turns what somebody wrote — a pool, an /// allocation, the span between two addresses in a log — into something a /// routing table or a firewall can hold, and it is not a conversion anyone /// gets right by hand. `2001:db8::a-2001:db8::14` is four blocks, in that order, /// and the blocks are not all the same size; the greedy rule that produces /// them is to take, at each step, the largest block that both starts where /// the range now starts and does not run past its end. /// /// The blocks come out in ascending address order and the iterator allocates /// nothing. There are at most 254 of them, which is the worst a range one /// address wider than a power of two at each end can force. pub fn prefixes(r: Ipv6Range) PrefixIterator { return .{ .next_value = r.first.toInt(), .end_value = r.last.toInt() }; } pub const PrefixIterator = struct { next_value: u129, end_value: u129, pub fn next(it: *PrefixIterator) ?Ipv6Network { if (it.next_value > it.end_value) return null; const first: u128 = @intCast(it.next_value); // The block starting here is bounded twice over: by how far `first` // is aligned, since a network cannot start in the middle of itself, // and by how much of the range is left, since it must not run past // the end. The smaller of the two wins. const alignment: u8 = @ctz(first); const remaining = it.end_value - it.next_value + 1; const span: u8 = 128 - @as(u8, @clz(remaining)); const bits: u8 = @min(alignment, span); it.next_value += @as(u129, 1) << @intCast(bits); return .{ .address = .fromInt(first), .prefix_len = Ipv6Address.bit_count - bits }; } test next { // A range that is a whole network comes out as that one network. var it = (try parse("2001:db8::-2001:db8::ff")).prefixes(); try std.testing.expect(it.next().?.eql(try Ipv6Network.parse("2001:db8::/120"))); try std.testing.expectEqual(null, it.next()); } }; /// Iterates over every address in the range. pub fn addresses(r: Ipv6Range) AddressIterator { return .{ .next_value = r.first.toInt(), .end_value = r.last.toInt() }; } pub const AddressIterator = struct { next_value: u129, end_value: u129, pub fn next(it: *AddressIterator) ?Ipv6Address { if (it.next_value > it.end_value) return null; const value: u128 = @intCast(it.next_value); it.next_value += 1; return .fromInt(value); } test next { var it = (try parse("2001:db8::1-2001:db8::4")).addresses(); var count: usize = 0; while (it.next()) |_| count += 1; try std.testing.expectEqual(@as(usize, 4), count); } }; /// Sorts `ranges` in place and folds it down to the smallest set covering /// exactly the same addresses, returning the prefix of the slice that /// survives. /// /// This is `Ipv6Network.merge`'s counterpart, and it folds more than that one /// can. Networks only combine when they are the two halves of a larger /// network, which is a question about alignment; ranges combine whenever /// there is no gap between them, which is a question about nothing but the /// addresses. So `2001:db8::1-2001:db8::5` and `2001:db8::6-2001:db8::9` become one range here, where the /// networks covering them would have stayed apart. /// /// Like the network version it takes a mutable slice rather than an /// allocator, sorts in place, and leaves the caller owning everything past /// the returned slice. pub fn merge(ranges: []Ipv6Range) []Ipv6Range { // Unstable for the same reason as `Ipv6Network.merge`: equal elements are // identical ranges, with no order between them to preserve. std.mem.sortUnstable(Ipv6Range, ranges, {}, lessThan); var kept: usize = 0; for (ranges) |candidate| { // One pass is enough, where the network version needs a loop. Sorted // by low end, the range kept last is the one reaching furthest right // of everything kept, so if the candidate does not join onto it, // nothing earlier will reach it either. if (kept > 0) { if (join(ranges[kept - 1], candidate)) |joined| { ranges[kept - 1] = joined; continue; } } ranges[kept] = candidate; kept += 1; } return ranges[0..kept]; } fn lessThan(_: void, a: Ipv6Range, b: Ipv6Range) bool { return a.order(b) == .lt; } /// The one range covering both exactly, when they overlap or touch, and null /// when a gap separates them. Order does not matter. /// /// Touching counts: `2001:db8::1-2001:db8::5` and `2001:db8::6-2001:db8::9` name one run of addresses /// written as two, and there is no address between them to leave out. That is /// the whole difference from `Ipv6Network.join`, which can only combine two /// networks that are the halves of a third. pub fn join(a: Ipv6Range, b: Ipv6Range) ?Ipv6Range { const lower = if (a.first.toInt() <= b.first.toInt()) a else b; const upper = if (a.first.toInt() <= b.first.toInt()) b else a; // Saturating, because the address one past the end of the space does not // exist -- and if `lower` already reaches the end, everything else is // inside it and joins anyway. if (upper.first.toInt() > lower.last.toInt() +| 1) return null; return .{ .first = lower.first, .last = if (lower.last.toInt() >= upper.last.toInt()) lower.last else upper.last, }; } pub fn eql(r: Ipv6Range, other: Ipv6Range) bool { return r.first.eql(other.first) and r.last.eql(other.last); } /// Orders by the low end first, then by the high end, so that a range sorts /// before the ranges that start inside it. pub fn order(r: Ipv6Range, other: Ipv6Range) std.math.Order { return switch (r.first.order(other.first)) { .eq => r.last.order(other.last), else => |result| result, }; } /// The longest text a range can format to: two addresses and the `-`. pub const max_text_len = Ipv6Address.max_text_len * 2 + "-".len; /// Writes the range as `first-last`. Use the `{f}` specifier. pub fn format(r: Ipv6Range, w: *Writer) Writer.Error!void { try r.first.format(w); try w.writeByte('-'); try r.last.format(w); } /// Formats into `buffer`, returning the written slice. The buffer must be at /// least `max_text_len` bytes. pub fn bufPrint(r: Ipv6Range, buffer: []u8) error{NoSpaceLeft}![]u8 { var w: Writer = .fixed(buffer); r.format(&w) catch return error.NoSpaceLeft; return w.buffered(); } /// Writes the value as a JSON string. See `json.stringify`. pub fn jsonStringify(value: Ipv6Range, jws: anytype) !void { return json.stringify(value, jws); } /// Reads a JSON string with `parse`. See `json.parse` for what happens to the /// reason when the text is rejected. pub fn jsonParse( allocator: std.mem.Allocator, source: anytype, options: std.json.ParseOptions, ) !Ipv6Range { _ = options; return json.parse(Ipv6Range, allocator, source); } const testing = std.testing; test init { const r = try Ipv6Range.init(try .parse("2001:db8::1"), try .parse("2001:db8::9")); try testing.expect(r.first.eql(try .parse("2001:db8::1"))); try testing.expect(r.last.eql(try .parse("2001:db8::9"))); // Both ends the same is a range of one, which is fine. _ = try Ipv6Range.init(try .parse("2001:db8::1"), try .parse("2001:db8::1")); // The other way round is not. try testing.expectError( error.Inverted, Ipv6Range.init(try .parse("2001:db8::9"), try .parse("2001:db8::1")), ); } test fromNetwork { const r = Ipv6Range.fromNetwork(try .parse("2001:db8::/120")); try testing.expect(r.eql(try parse("2001:db8::-2001:db8::ff"))); } test fromAddress { const r = Ipv6Range.fromAddress(try .parse("2001:db8::1")); try testing.expect(r.isSingleAddress()); try testing.expectEqual(@as(u129, 1), r.addressCount()); } test parse { const r = try parse("2001:db8::a-2001:db8::14"); try testing.expect(r.first.eql(try .parse("2001:db8::a"))); try testing.expect(r.last.eql(try .parse("2001:db8::14"))); // Strict at both ends, and no room for whitespace around the `-`. try testing.expectError(error.MissingSeparator, parse("2001:db8::1")); try testing.expectError(error.Inverted, parse("2001:db8::9-2001:db8::1")); try testing.expectError(error.EmptyGroup, parse("2001:db8:::1-2001:db8::14")); } test isValid { try testing.expect(Ipv6Range.isValid("2001:db8::a-2001:db8::14")); try testing.expect(!Ipv6Range.isValid("2001:db8::1")); } test addressCount { try testing.expectEqual(@as(u129, 11), (try parse("2001:db8::a-2001:db8::14")).addressCount()); // Never zero: a range always holds at least its own endpoints. try testing.expectEqual(@as(u129, 1), Ipv6Range.fromAddress(try .parse("2001:db8::1")).addressCount()); } test isSingleAddress { try testing.expect(Ipv6Range.fromAddress(try .parse("2001:db8::1")).isSingleAddress()); try testing.expect(!(try parse("2001:db8::a-2001:db8::14")).isSingleAddress()); } test contains { const r = try parse("2001:db8::a-2001:db8::14"); try testing.expect(r.contains(try .parse("2001:db8::a"))); try testing.expect(r.contains(try .parse("2001:db8::14"))); // Both ends are part of the range; one past either is not. try testing.expect(!r.contains((try Ipv6Address.parse("2001:db8::a")).prev().?)); try testing.expect(!r.contains((try Ipv6Address.parse("2001:db8::14")).next().?)); } test containsRange { const outer = try parse("2001:db8::a-2001:db8::14"); try testing.expect(outer.containsRange(outer)); try testing.expect(outer.containsRange(Ipv6Range.fromAddress(try .parse("2001:db8::a")))); try testing.expect(!outer.containsRange(try parse("2001:db8::100-2001:db8::10a"))); } test overlaps { const r = try parse("2001:db8::a-2001:db8::14"); try testing.expect(r.overlaps(r)); try testing.expect(!r.overlaps(try parse("2001:db8::100-2001:db8::10a"))); // Touching without sharing an address is not overlapping. try testing.expect(!r.overlaps(Ipv6Range.fromAddress((try Ipv6Address.parse("2001:db8::14")).next().?))); } test toNetwork { // A range that lines up with a network gives that network back. try testing.expect((try parse("2001:db8::-2001:db8::ff")).toNetwork().?.eql(try Ipv6Network.parse("2001:db8::/120"))); // One that does not line up is not a network at all. try testing.expectEqual(null, (try parse("2001:db8::a-2001:db8::14")).toNetwork()); } test prefixes { // The greedy rule at work: the blocks are not all the same size, and // they come out in ascending address order. var it = (try parse("2001:db8::a-2001:db8::14")).prefixes(); try testing.expect(it.next().?.eql(try Ipv6Network.parse("2001:db8::a/127"))); try testing.expect(it.next().?.eql(try Ipv6Network.parse("2001:db8::c/126"))); try testing.expect(it.next().?.eql(try Ipv6Network.parse("2001:db8::10/126"))); try testing.expect(it.next().?.eql(try Ipv6Network.parse("2001:db8::14/128"))); try testing.expectEqual(null, it.next()); // Whatever the range, the blocks cover it exactly. var total: u129 = 0; var parts = (try parse("2001:db8::a-2001:db8::14")).prefixes(); while (parts.next()) |part| total += part.addressCount(); try testing.expectEqual((try parse("2001:db8::a-2001:db8::14")).addressCount(), total); } test addresses { var it = (try parse("2001:db8::1-2001:db8::4")).addresses(); try testing.expect(it.next().?.eql(try .parse("2001:db8::1"))); var last: Ipv6Address = undefined; while (it.next()) |address| last = address; try testing.expect(last.eql(try .parse("2001:db8::4"))); } test merge { // Touching ranges become one, which is the thing networks cannot do: // there is no address between them to leave out. var touching = [_]Ipv6Range{ try .parse("2001:db8::6-2001:db8::9"), try .parse("2001:db8::1-2001:db8::5") }; const joined = Ipv6Range.merge(&touching); try testing.expectEqual(@as(usize, 1), joined.len); try testing.expect(joined[0].eql(try parse("2001:db8::1-2001:db8::9"))); // Overlapping, nested and duplicate ranges all collapse. var messy = [_]Ipv6Range{ try .parse("2001:db8::4-2001:db8::9"), try .parse("2001:db8::1-2001:db8::5"), try .parse("2001:db8::3-2001:db8::4"), }; try testing.expectEqual(@as(usize, 1), Ipv6Range.merge(&messy).len); // A gap of one address is still a gap. var gapped = [_]Ipv6Range{ try .parse("2001:db8::1-2001:db8::5"), try .parse("2001:db8::7-2001:db8::9") }; const apart = Ipv6Range.merge(&gapped); try testing.expectEqual(@as(usize, 2), apart.len); try testing.expect(apart[0].eql(try parse("2001:db8::1-2001:db8::5"))); var empty: [0]Ipv6Range = .{}; try testing.expectEqual(@as(usize, 0), Ipv6Range.merge(&empty).len); } test lessThan { try testing.expect(lessThan({}, try parse("2001:db8::1-2001:db8::5"), try parse("2001:db8::6-2001:db8::9"))); try testing.expect(!lessThan({}, try parse("2001:db8::6-2001:db8::9"), try parse("2001:db8::1-2001:db8::5"))); } test join { // Touching, in either order. try testing.expect(Ipv6Range.join(try parse("2001:db8::1-2001:db8::5"), try parse("2001:db8::6-2001:db8::9")).? .eql(try parse("2001:db8::1-2001:db8::9"))); try testing.expect(Ipv6Range.join(try parse("2001:db8::6-2001:db8::9"), try parse("2001:db8::1-2001:db8::5")).? .eql(try parse("2001:db8::1-2001:db8::9"))); // Overlapping, and one wholly inside the other. try testing.expect(Ipv6Range.join(try parse("2001:db8::1-2001:db8::5"), try parse("2001:db8::4-2001:db8::9")).? .eql(try parse("2001:db8::1-2001:db8::9"))); try testing.expect(Ipv6Range.join(try parse("2001:db8::1-2001:db8::9"), try parse("2001:db8::3-2001:db8::4")).? .eql(try parse("2001:db8::1-2001:db8::9"))); // One address of daylight between them is enough to keep them apart. try testing.expectEqual(null, Ipv6Range.join(try parse("2001:db8::1-2001:db8::5"), try parse("2001:db8::7-2001:db8::9"))); // And a range reaching the top of the space swallows anything after it // rather than overflowing. try testing.expect(Ipv6Range.join(try parse("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ff00-ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff"), try parse("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff-ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff")).? .eql(try parse("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ff00-ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff"))); } test eql { try testing.expect((try parse("2001:db8::a-2001:db8::14")).eql(try parse("2001:db8::a-2001:db8::14"))); try testing.expect(!(try parse("2001:db8::a-2001:db8::14")).eql(try parse("2001:db8::100-2001:db8::10a"))); } test order { try testing.expectEqual(.lt, (try parse("2001:db8::a-2001:db8::14")).order(try parse("2001:db8::100-2001:db8::10a"))); try testing.expectEqual(.eq, (try parse("2001:db8::a-2001:db8::14")).order(try parse("2001:db8::a-2001:db8::14"))); } test jsonStringify { // Driven directly, for the same reason `jsonParse` below is: handing the // hook a `Stringify` tests the function this test is named after rather // than `std.json.Stringify.value`'s reflection over the type. var buffer: [128]u8 = undefined; var w: Writer = .fixed(&buffer); var jws: std.json.Stringify = .{ .writer = &w }; try (try Ipv6Range.parse("2001:db8::a-2001:db8::14")).jsonStringify(&jws); // A JSON string holding exactly what `format` would have written. try testing.expectEqualStrings("\"2001:db8::a-2001:db8::14\"", w.buffered()); } test jsonParse { // The hook is driven directly rather than through `parseFromSlice`, so // that this tests the function it is named after and nothing else; // `root.zig` has the end-to-end one. var scanner = std.json.Scanner.initCompleteInput(testing.allocator, "\"2001:db8::a-2001:db8::14\""); defer scanner.deinit(); const value = try Ipv6Range.jsonParse(testing.allocator, &scanner, .{}); try testing.expect(value.eql(try Ipv6Range.parse("2001:db8::a-2001:db8::14"))); // As strict inside a JSON document as anywhere else, though the reason is // flattened to `InvalidCharacter` on the way out. var bad = std.json.Scanner.initCompleteInput(testing.allocator, "\"2001:db8::14-2001:db8::a\""); defer bad.deinit(); try testing.expectError( error.InvalidCharacter, Ipv6Range.jsonParse(testing.allocator, &bad, .{}), ); // Anything that is not a string is the wrong shape rather than a bad // address. var number = std.json.Scanner.initCompleteInput(testing.allocator, "42"); defer number.deinit(); try testing.expectError( error.UnexpectedToken, Ipv6Range.jsonParse(testing.allocator, &number, .{}), ); } test format { var buffer: [max_text_len]u8 = undefined; var w: Writer = .fixed(&buffer); try (try parse("2001:db8::a-2001:db8::14")).format(&w); try testing.expectEqualStrings("2001:db8::a-2001:db8::14", w.buffered()); } test bufPrint { var buffer: [max_text_len]u8 = undefined; try testing.expectEqualStrings("2001:db8::a-2001:db8::14", try (try parse("2001:db8::a-2001:db8::14")).bufPrint(&buffer)); var small: [4]u8 = undefined; try testing.expectError(error.NoSpaceLeft, (try parse("2001:db8::a-2001:db8::14")).bufPrint(&small)); }