// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! An inclusive range of IPv4 addresses, from `first` to `last`. //! //! A range is what CIDR notation cannot write down. `10.0.0.10-10.0.0.20` 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 Ipv4Address = @import("Ipv4Address.zig"); const Ipv4Network = @import("Ipv4Network.zig"); const Ipv4Range = @This(); /// The lowest address in the range. first: Ipv4Address, /// The highest address in the range, which is part of it. last: Ipv4Address, 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: Ipv4Address, last: Ipv4Address) InitError!Ipv4Range { 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: Ipv4Network) Ipv4Range { return .{ .first = n.networkAddress(), .last = n.broadcastAddress() }; } /// The range holding one address. pub fn fromAddress(address: Ipv4Address) Ipv4Range { return .{ .first = address, .last = address }; } pub const ParseError = Ipv4Address.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 `10.0.0.10-10.0.0.20`. /// /// Both ends are parsed as strictly as `Ipv4Address.parse` parses anything, and /// no space is allowed around the `-`. `first` must not be above `last`. pub fn parse(text: []const u8) ParseError!Ipv4Range { const separator = std.mem.findScalar(u8, text, '-') orelse return error.MissingSeparator; const first = try Ipv4Address.parse(text[0..separator]); const last = try Ipv4Address.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 /// 64 bits wide because a range covering the whole address space does not fit in /// 32. pub fn addressCount(r: Ipv4Range) u64 { return @as(u64, r.last.toInt()) - r.first.toInt() + 1; } /// Whether the range holds exactly one address. pub fn isSingleAddress(r: Ipv4Range) bool { return r.first.eql(r.last); } /// Whether `address` falls inside the range. pub fn contains(r: Ipv4Range, address: Ipv4Address) 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: Ipv4Range, other: Ipv4Range) 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: Ipv4Range, other: Ipv4Range) 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: Ipv4Range) ?Ipv4Network { 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. `10.0.0.10-10.0.0.20` 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 62 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: Ipv4Range) PrefixIterator { return .{ .next_value = r.first.toInt(), .end_value = r.last.toInt() }; } pub const PrefixIterator = struct { next_value: u64, end_value: u64, pub fn next(it: *PrefixIterator) ?Ipv4Network { if (it.next_value > it.end_value) return null; const first: u32 = @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 = 63 - @as(u8, @clz(remaining)); const bits: u8 = @min(alignment, span); it.next_value += @as(u64, 1) << @intCast(bits); return .{ .address = .fromInt(first), .prefix_len = Ipv4Address.bit_count - bits }; } test next { // A range that is a whole network comes out as that one network. var it = (try parse("192.0.2.0-192.0.2.255")).prefixes(); try std.testing.expect(it.next().?.eql(try Ipv4Network.parse("192.0.2.0/24"))); try std.testing.expectEqual(null, it.next()); } }; /// Iterates over every address in the range. pub fn addresses(r: Ipv4Range) AddressIterator { return .{ .next_value = r.first.toInt(), .end_value = r.last.toInt() }; } pub const AddressIterator = struct { next_value: u64, end_value: u64, pub fn next(it: *AddressIterator) ?Ipv4Address { if (it.next_value > it.end_value) return null; const value: u32 = @intCast(it.next_value); it.next_value += 1; return .fromInt(value); } test next { var it = (try parse("10.0.0.1-10.0.0.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 `Ipv4Network.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 `10.0.0.1-10.0.0.5` and `10.0.0.6-10.0.0.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: []Ipv4Range) []Ipv4Range { // Unstable for the same reason as `Ipv4Network.merge`: equal elements are // identical ranges, with no order between them to preserve. std.mem.sortUnstable(Ipv4Range, 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: Ipv4Range, b: Ipv4Range) 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: `10.0.0.1-10.0.0.5` and `10.0.0.6-10.0.0.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 `Ipv4Network.join`, which can only combine two /// networks that are the halves of a third. pub fn join(a: Ipv4Range, b: Ipv4Range) ?Ipv4Range { 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: Ipv4Range, other: Ipv4Range) 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: Ipv4Range, other: Ipv4Range) 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 = Ipv4Address.max_text_len * 2 + "-".len; /// Writes the range as `first-last`. Use the `{f}` specifier. pub fn format(r: Ipv4Range, 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: Ipv4Range, 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: Ipv4Range, 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, ) !Ipv4Range { _ = options; return json.parse(Ipv4Range, allocator, source); } const testing = std.testing; test init { const r = try Ipv4Range.init(try .parse("10.0.0.1"), try .parse("10.0.0.9")); try testing.expect(r.first.eql(try .parse("10.0.0.1"))); try testing.expect(r.last.eql(try .parse("10.0.0.9"))); // Both ends the same is a range of one, which is fine. _ = try Ipv4Range.init(try .parse("10.0.0.1"), try .parse("10.0.0.1")); // The other way round is not. try testing.expectError( error.Inverted, Ipv4Range.init(try .parse("10.0.0.9"), try .parse("10.0.0.1")), ); } test fromNetwork { const r = Ipv4Range.fromNetwork(try .parse("192.0.2.0/24")); try testing.expect(r.eql(try parse("192.0.2.0-192.0.2.255"))); } test fromAddress { const r = Ipv4Range.fromAddress(try .parse("10.0.0.1")); try testing.expect(r.isSingleAddress()); try testing.expectEqual(@as(u64, 1), r.addressCount()); } test parse { const r = try parse("10.0.0.10-10.0.0.20"); try testing.expect(r.first.eql(try .parse("10.0.0.10"))); try testing.expect(r.last.eql(try .parse("10.0.0.20"))); // Strict at both ends, and no room for whitespace around the `-`. try testing.expectError(error.MissingSeparator, parse("10.0.0.1")); try testing.expectError(error.Inverted, parse("10.0.0.9-10.0.0.1")); try testing.expectError(error.LeadingZero, parse("10.0.0.01-10.0.0.20")); } test isValid { try testing.expect(Ipv4Range.isValid("10.0.0.10-10.0.0.20")); try testing.expect(!Ipv4Range.isValid("10.0.0.1")); } test addressCount { try testing.expectEqual(@as(u64, 11), (try parse("10.0.0.10-10.0.0.20")).addressCount()); // Never zero: a range always holds at least its own endpoints. try testing.expectEqual(@as(u64, 1), Ipv4Range.fromAddress(try .parse("10.0.0.1")).addressCount()); } test isSingleAddress { try testing.expect(Ipv4Range.fromAddress(try .parse("10.0.0.1")).isSingleAddress()); try testing.expect(!(try parse("10.0.0.10-10.0.0.20")).isSingleAddress()); } test contains { const r = try parse("10.0.0.10-10.0.0.20"); try testing.expect(r.contains(try .parse("10.0.0.10"))); try testing.expect(r.contains(try .parse("10.0.0.20"))); // Both ends are part of the range; one past either is not. try testing.expect(!r.contains((try Ipv4Address.parse("10.0.0.10")).prev().?)); try testing.expect(!r.contains((try Ipv4Address.parse("10.0.0.20")).next().?)); } test containsRange { const outer = try parse("10.0.0.10-10.0.0.20"); try testing.expect(outer.containsRange(outer)); try testing.expect(outer.containsRange(Ipv4Range.fromAddress(try .parse("10.0.0.10")))); try testing.expect(!outer.containsRange(try parse("10.0.1.0-10.0.1.10"))); } test overlaps { const r = try parse("10.0.0.10-10.0.0.20"); try testing.expect(r.overlaps(r)); try testing.expect(!r.overlaps(try parse("10.0.1.0-10.0.1.10"))); // Touching without sharing an address is not overlapping. try testing.expect(!r.overlaps(Ipv4Range.fromAddress((try Ipv4Address.parse("10.0.0.20")).next().?))); } test toNetwork { // A range that lines up with a network gives that network back. try testing.expect((try parse("192.0.2.0-192.0.2.255")).toNetwork().?.eql(try Ipv4Network.parse("192.0.2.0/24"))); // One that does not line up is not a network at all. try testing.expectEqual(null, (try parse("10.0.0.10-10.0.0.20")).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("10.0.0.10-10.0.0.20")).prefixes(); try testing.expect(it.next().?.eql(try Ipv4Network.parse("10.0.0.10/31"))); try testing.expect(it.next().?.eql(try Ipv4Network.parse("10.0.0.12/30"))); try testing.expect(it.next().?.eql(try Ipv4Network.parse("10.0.0.16/30"))); try testing.expect(it.next().?.eql(try Ipv4Network.parse("10.0.0.20/32"))); try testing.expectEqual(null, it.next()); // Whatever the range, the blocks cover it exactly. var total: u64 = 0; var parts = (try parse("10.0.0.10-10.0.0.20")).prefixes(); while (parts.next()) |part| total += part.addressCount(); try testing.expectEqual((try parse("10.0.0.10-10.0.0.20")).addressCount(), total); } test addresses { var it = (try parse("10.0.0.1-10.0.0.4")).addresses(); try testing.expect(it.next().?.eql(try .parse("10.0.0.1"))); var last: Ipv4Address = undefined; while (it.next()) |address| last = address; try testing.expect(last.eql(try .parse("10.0.0.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 = [_]Ipv4Range{ try .parse("10.0.0.6-10.0.0.9"), try .parse("10.0.0.1-10.0.0.5") }; const joined = Ipv4Range.merge(&touching); try testing.expectEqual(@as(usize, 1), joined.len); try testing.expect(joined[0].eql(try parse("10.0.0.1-10.0.0.9"))); // Overlapping, nested and duplicate ranges all collapse. var messy = [_]Ipv4Range{ try .parse("10.0.0.4-10.0.0.9"), try .parse("10.0.0.1-10.0.0.5"), try .parse("10.0.0.3-10.0.0.4"), }; try testing.expectEqual(@as(usize, 1), Ipv4Range.merge(&messy).len); // A gap of one address is still a gap. var gapped = [_]Ipv4Range{ try .parse("10.0.0.1-10.0.0.5"), try .parse("10.0.0.7-10.0.0.9") }; const apart = Ipv4Range.merge(&gapped); try testing.expectEqual(@as(usize, 2), apart.len); try testing.expect(apart[0].eql(try parse("10.0.0.1-10.0.0.5"))); var empty: [0]Ipv4Range = .{}; try testing.expectEqual(@as(usize, 0), Ipv4Range.merge(&empty).len); } test lessThan { try testing.expect(lessThan({}, try parse("10.0.0.1-10.0.0.5"), try parse("10.0.0.6-10.0.0.9"))); try testing.expect(!lessThan({}, try parse("10.0.0.6-10.0.0.9"), try parse("10.0.0.1-10.0.0.5"))); } test join { // Touching, in either order. try testing.expect(Ipv4Range.join(try parse("10.0.0.1-10.0.0.5"), try parse("10.0.0.6-10.0.0.9")).? .eql(try parse("10.0.0.1-10.0.0.9"))); try testing.expect(Ipv4Range.join(try parse("10.0.0.6-10.0.0.9"), try parse("10.0.0.1-10.0.0.5")).? .eql(try parse("10.0.0.1-10.0.0.9"))); // Overlapping, and one wholly inside the other. try testing.expect(Ipv4Range.join(try parse("10.0.0.1-10.0.0.5"), try parse("10.0.0.4-10.0.0.9")).? .eql(try parse("10.0.0.1-10.0.0.9"))); try testing.expect(Ipv4Range.join(try parse("10.0.0.1-10.0.0.9"), try parse("10.0.0.3-10.0.0.4")).? .eql(try parse("10.0.0.1-10.0.0.9"))); // One address of daylight between them is enough to keep them apart. try testing.expectEqual(null, Ipv4Range.join(try parse("10.0.0.1-10.0.0.5"), try parse("10.0.0.7-10.0.0.9"))); // And a range reaching the top of the space swallows anything after it // rather than overflowing. try testing.expect(Ipv4Range.join(try parse("255.255.255.0-255.255.255.255"), try parse("255.255.255.255-255.255.255.255")).? .eql(try parse("255.255.255.0-255.255.255.255"))); } test eql { try testing.expect((try parse("10.0.0.10-10.0.0.20")).eql(try parse("10.0.0.10-10.0.0.20"))); try testing.expect(!(try parse("10.0.0.10-10.0.0.20")).eql(try parse("10.0.1.0-10.0.1.10"))); } test order { try testing.expectEqual(.lt, (try parse("10.0.0.10-10.0.0.20")).order(try parse("10.0.1.0-10.0.1.10"))); try testing.expectEqual(.eq, (try parse("10.0.0.10-10.0.0.20")).order(try parse("10.0.0.10-10.0.0.20"))); } 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 Ipv4Range.parse("10.0.0.10-10.0.0.20")).jsonStringify(&jws); // A JSON string holding exactly what `format` would have written. try testing.expectEqualStrings("\"10.0.0.10-10.0.0.20\"", 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, "\"10.0.0.10-10.0.0.20\""); defer scanner.deinit(); const value = try Ipv4Range.jsonParse(testing.allocator, &scanner, .{}); try testing.expect(value.eql(try Ipv4Range.parse("10.0.0.10-10.0.0.20"))); // 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, "\"10.0.0.20-10.0.0.10\""); defer bad.deinit(); try testing.expectError( error.InvalidCharacter, Ipv4Range.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, Ipv4Range.jsonParse(testing.allocator, &number, .{}), ); } test format { var buffer: [max_text_len]u8 = undefined; var w: Writer = .fixed(&buffer); try (try parse("10.0.0.10-10.0.0.20")).format(&w); try testing.expectEqualStrings("10.0.0.10-10.0.0.20", w.buffered()); } test bufPrint { var buffer: [max_text_len]u8 = undefined; try testing.expectEqualStrings("10.0.0.10-10.0.0.20", try (try parse("10.0.0.10-10.0.0.20")).bufPrint(&buffer)); var small: [4]u8 = undefined; try testing.expectError(error.NoSpaceLeft, (try parse("10.0.0.10-10.0.0.20")).bufPrint(&small)); }