use super::range::{IpError, IpRange, Ipv4Range, Ipv6Range};
use std::{
borrow::Cow,
net::{IpAddr, Ipv4Addr, Ipv6Addr},
str::FromStr,
};
#[non_exhaustive]
#[derive(Debug, thiserror::Error)]
pub enum IpSetError {
#[error("Invalid target in set: {0}")]
InvalidTarget(#[from] IpError),
}
#[derive(Debug, Clone, Default, Eq)]
pub struct IpSet {
v4: Vec<Ipv4Range>,
v6: Vec<Ipv6Range>,
v4_dirty: bool,
v6_dirty: bool,
}
impl IpSet {
pub fn new() -> Self {
Self::default()
}
pub fn insert(&mut self, ip: IpAddr) {
match ip {
IpAddr::V4(v4) => self.push_v4_range(Ipv4Range::single(v4)),
IpAddr::V6(v6) => self.push_v6_range(Ipv6Range::single(v6)),
}
}
pub fn insert_range(&mut self, range: IpRange) {
match range {
IpRange::V4(r) => self.push_v4_range(r),
IpRange::V6(r) => self.push_v6_range(r),
}
}
pub fn push_v4_range(&mut self, range: Ipv4Range) {
self.v4.push(range);
self.v4_dirty = true;
}
pub fn push_v6_range(&mut self, range: Ipv6Range) {
self.v6.push(range);
self.v6_dirty = true;
}
pub fn canonicalize(&mut self) {
if self.v4_dirty {
if !self.v4.is_empty() {
self.merge_v4();
}
self.v4_dirty = false;
}
if self.v6_dirty {
if !self.v6.is_empty() {
self.merge_v6();
}
self.v6_dirty = false;
}
}
fn merge_v4(&mut self) {
self.v4.sort_by_key(|r| r.start_addr());
let mut merged: Vec<Ipv4Range> = Vec::with_capacity(self.v4.len());
let mut current = self.v4[0];
for next in self.v4.drain(1..) {
let curr_end = u32::from(current.end_addr());
let next_start = u32::from(next.start_addr());
if next_start <= curr_end.saturating_add(1) {
current.extend_end_to(next.end_addr());
} else {
merged.push(current);
current = next;
}
}
merged.push(current);
self.v4 = merged;
}
fn merge_v6(&mut self) {
self.v6.sort_by_key(|r| (r.zone(), r.start_addr()));
let mut merged: Vec<Ipv6Range> = Vec::with_capacity(self.v6.len());
let mut current = self.v6[0];
for next in self.v6.drain(1..) {
let curr_end = u128::from(current.end_addr());
let next_start = u128::from(next.start_addr());
if next.zone() == current.zone() && next_start <= curr_end.saturating_add(1) {
current.extend_end_to(next.end_addr());
} else {
merged.push(current);
current = next;
}
}
merged.push(current);
self.v6 = merged;
}
fn v6_runs(&self) -> impl Iterator<Item = &[Ipv6Range]> {
let mut rest = self.v6.as_slice();
std::iter::from_fn(move || {
let zone = rest.first()?.zone();
let (run, tail) = rest.split_at(rest.partition_point(|r| r.zone() == zone));
rest = tail;
Some(run)
})
}
pub fn contains(&self, ip: &IpAddr) -> bool {
if !self.v4_dirty && !self.v6_dirty {
return self.contains_canonical(ip);
}
match ip {
IpAddr::V4(v4) => self.v4.iter().any(|range| range.contains(v4)),
IpAddr::V6(v6) => self.v6.iter().any(|range| range.contains(v6)),
}
}
pub fn len(&self) -> u128 {
if !self.v4_dirty && !self.v6_dirty {
self.len_canonical()
} else {
let mut temp = self.clone();
temp.canonicalize();
temp.len_canonical()
}
}
pub fn is_empty(&self) -> bool {
self.v4.is_empty() && self.v6.is_empty()
}
pub fn len_gross(&self) -> u128 {
self.v4_len().saturating_add(self.v6_len())
}
pub fn iter(&self) -> Box<dyn Iterator<Item = IpAddr> + Send + '_> {
if self.v4_dirty || self.v6_dirty {
let mut temp = self.clone();
temp.canonicalize();
temp.into_iter()
} else {
let v4_iter = self.v4.iter().flat_map(|range| range.iter());
let v6_iter = self.v6.iter().flat_map(|range| range.iter());
Box::new(v4_iter.chain(v6_iter))
}
}
fn contains_canonical(&self, ip: &IpAddr) -> bool {
debug_assert!(
!self.v4_dirty && !self.v6_dirty,
"IpSet must be canonicalized before calling contains_canonical"
);
match ip {
IpAddr::V4(v4) => holds(&self.v4, u128::from(u32::from(*v4)), |range| {
(
u128::from(u32::from(range.start_addr())),
u128::from(u32::from(range.end_addr())),
)
}),
IpAddr::V6(v6) => {
let target = u128::from(*v6);
self.v6_runs().any(|run| {
holds(run, target, |range| {
(u128::from(range.start_addr()), u128::from(range.end_addr()))
})
})
}
}
}
fn len_canonical(&self) -> u128 {
debug_assert!(
!self.v4_dirty && !self.v6_dirty,
"IpSet must be canonicalized before calling len_canonical"
);
self.v4_len().saturating_add(self.v6_len())
}
pub fn v4_len(&self) -> u128 {
self.v4
.iter()
.fold(0u128, |total, r| total.saturating_add(r.len() as u128))
}
pub fn v6_len(&self) -> u128 {
self.v6
.iter()
.fold(0u128, |total, r| total.saturating_add(r.len()))
}
pub fn v4(&self) -> &[Ipv4Range] {
&self.v4
}
pub fn v6(&self) -> &[Ipv6Range] {
&self.v6
}
}
impl PartialEq for IpSet {
fn eq(&self, other: &Self) -> bool {
fn merged(set: &IpSet) -> Cow<'_, IpSet> {
if set.v4_dirty || set.v6_dirty {
let mut owned = set.clone();
owned.canonicalize();
Cow::Owned(owned)
} else {
Cow::Borrowed(set)
}
}
let (this, that) = (merged(self), merged(other));
this.v4 == that.v4 && this.v6 == that.v6
}
}
fn holds<R>(ranges: &[R], target: u128, bounds: impl Fn(&R) -> (u128, u128)) -> bool {
ranges
.binary_search_by(|range| {
let (start, end) = bounds(range);
if target < start {
std::cmp::Ordering::Greater
} else if target > end {
std::cmp::Ordering::Less
} else {
std::cmp::Ordering::Equal
}
})
.is_ok()
}
impl IntoIterator for IpSet {
type Item = IpAddr;
type IntoIter = Box<dyn Iterator<Item = IpAddr> + Send>;
fn into_iter(mut self) -> Self::IntoIter {
self.canonicalize();
let v4_iter = self.v4.into_iter().flat_map(|range| {
let start: u32 = range.start_addr().into();
let end: u32 = range.end_addr().into();
(start..=end).map(|ip| IpAddr::V4(Ipv4Addr::from(ip)))
});
let v6_iter = self.v6.into_iter().flat_map(|range| {
let start: u128 = range.start_addr().into();
let end: u128 = range.end_addr().into();
(start..=end).map(|ip| IpAddr::V6(Ipv6Addr::from(ip)))
});
Box::new(v4_iter.chain(v6_iter))
}
}
impl Extend<IpAddr> for IpSet {
fn extend<T: IntoIterator<Item = IpAddr>>(&mut self, iter: T) {
for ip in iter {
match ip {
IpAddr::V4(v4) => self.push_v4_range(Ipv4Range::single(v4)),
IpAddr::V6(v6) => self.push_v6_range(Ipv6Range::single(v6)),
}
}
}
}
impl FromIterator<IpAddr> for IpSet {
fn from_iter<I: IntoIterator<Item = IpAddr>>(iter: I) -> Self {
let mut set = IpSet::new();
set.extend(iter);
set.canonicalize();
set
}
}
impl FromIterator<IpRange> for IpSet {
fn from_iter<I: IntoIterator<Item = IpRange>>(iter: I) -> Self {
let mut set = IpSet::new();
for range in iter {
set.insert_range(range);
}
set.canonicalize();
set
}
}
impl FromIterator<IpSet> for IpSet {
fn from_iter<I: IntoIterator<Item = IpSet>>(iter: I) -> Self {
let mut master = IpSet::new();
for set in iter {
if !set.v4.is_empty() {
master.v4.extend(set.v4);
master.v4_dirty = true;
}
if !set.v6.is_empty() {
master.v6.extend(set.v6);
master.v6_dirty = true;
}
}
master.canonicalize();
master
}
}
impl From<IpAddr> for IpSet {
fn from(ip: IpAddr) -> Self {
let mut set = Self::new();
set.insert(ip);
set
}
}
impl From<IpRange> for IpSet {
fn from(range: IpRange) -> Self {
let mut set = Self::new();
set.insert_range(range);
set
}
}
impl TryFrom<&str> for IpSet {
type Error = IpSetError;
fn try_from(value: &str) -> Result<Self, Self::Error> {
let mut set = IpSet::new();
for part in value
.split([',', ' '])
.filter(|part| !part.trim().is_empty())
{
let range = part.parse::<IpRange>()?;
set.insert_range(range);
}
set.canonicalize();
Ok(set)
}
}
impl FromStr for IpSet {
type Err = IpSetError;
fn from_str(s: &str) -> Result<Self, Self::Err> {
Self::try_from(s)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn adjacent_addresses_merge_when_the_set_is_canonicalized() {
let mut set = IpSet::new();
set.insert(IpAddr::V4(Ipv4Addr::new(1, 1, 1, 1)));
set.insert(IpAddr::V4(Ipv4Addr::new(1, 1, 1, 2)));
assert_eq!(set.v4.len(), 2);
assert!(set.v4_dirty);
set.canonicalize();
assert_eq!(set.len(), 2);
assert!(!set.v4_dirty);
assert_eq!(set.v4.len(), 1);
}
#[test]
fn every_kind_of_overlap_collapses_to_one_range() {
let mut set = IpSet::new();
set.insert_range("10.0.0.10-10.0.0.20".parse().unwrap());
set.insert_range("10.0.0.5-10.0.0.15".parse().unwrap());
set.insert_range("10.0.0.15-10.0.0.25".parse().unwrap());
set.insert_range("10.0.0.30-10.0.0.40".parse().unwrap());
set.insert_range("10.0.0.0-10.0.0.50".parse().unwrap());
set.canonicalize();
assert_eq!(set.len(), 51);
assert_eq!(set.v4().len(), 1);
}
#[test]
fn the_top_of_the_ipv6_space_merges_without_overflowing() {
let mut set = IpSet::new();
let max_v6 = Ipv6Addr::from(u128::MAX);
let max_minus_1 = Ipv6Addr::from(u128::MAX - 1);
set.insert(IpAddr::V6(max_minus_1));
set.insert(IpAddr::V6(max_v6));
set.canonicalize();
assert_eq!(set.len(), 2);
assert_eq!(set.v6().len(), 1);
}
#[test]
fn iterating_yields_each_address_without_mutating_the_set() {
let mut set = IpSet::new();
set.insert(IpAddr::V4(Ipv4Addr::from(1)));
set.insert(IpAddr::V4(Ipv4Addr::from(2)));
set.canonicalize();
let ips: Vec<IpAddr> = set.iter().collect();
assert_eq!(ips.len(), 2);
assert!(!set.v4_dirty);
}
#[test]
fn an_empty_set_canonicalizes_and_counts_as_zero() {
let mut set = IpSet::new();
set.canonicalize();
assert_eq!(set.len_canonical(), 0);
assert!(set.v4().is_empty());
}
#[test]
fn extending_one_family_leaves_the_other_canonical() {
let mut set = IpSet::from_iter(vec![IpAddr::V6(Ipv6Addr::LOCALHOST)]);
assert!(!set.v4_dirty && !set.v6_dirty, "from_iter canonicalizes");
set.extend([IpAddr::V4(Ipv4Addr::LOCALHOST)]);
assert!(set.v4_dirty, "the family that gained a range");
assert!(!set.v6_dirty, "and only that one");
let mut untouched = IpSet::from_iter(vec![IpAddr::V4(Ipv4Addr::LOCALHOST)]);
untouched.extend([]);
assert!(!untouched.v4_dirty && !untouched.v6_dirty);
}
#[test]
fn a_written_set_may_mix_both_families_and_still_counts_distinctly() {
let set = IpSet::from_str("1.1.1.1/32, 1.1.1.1, ::1-::1, 10.0.0.1-10.0.0.2").unwrap();
assert_eq!(set.len(), 4);
}
#[test]
fn insertion_defers_the_merge_until_it_is_asked_for() {
let mut set = IpSet::new();
let ips = (0..100).map(|i| IpAddr::V4(Ipv4Addr::from(i)));
set.extend(ips);
assert_eq!(set.v4.len(), 100);
set.canonicalize();
assert_eq!(set.v4.len(), 1);
assert_eq!(set.len(), 100);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "must be canonicalized")]
fn a_membership_query_on_an_unmerged_set_trips_the_guard() {
let mut set = IpSet::new();
set.insert(IpAddr::V4(Ipv4Addr::LOCALHOST));
set.contains_canonical(&IpAddr::V4(Ipv4Addr::LOCALHOST));
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "must be canonicalized")]
fn a_count_on_an_unmerged_set_trips_the_guard() {
let mut set = IpSet::new();
set.insert(IpAddr::V4(Ipv4Addr::LOCALHOST));
set.len_canonical();
}
#[test]
fn a_membership_query_on_a_merged_set_answers() {
let set = IpSet::from_iter(vec![IpAddr::V4(Ipv4Addr::LOCALHOST)]);
assert!(!set.v4_dirty, "from_iter canonicalizes");
assert!(set.contains_canonical(&IpAddr::V4(Ipv4Addr::LOCALHOST)));
assert_eq!(set.len_canonical(), 1);
}
#[test]
fn ranges_on_different_interfaces_never_merge_however_adjacent() {
let one: Ipv6Addr = "fe80::1".parse().unwrap();
let five: Ipv6Addr = "fe80::5".parse().unwrap();
let six: Ipv6Addr = "fe80::6".parse().unwrap();
let ten: Ipv6Addr = "fe80::a".parse().unwrap();
let mut split = IpSet::new();
split.push_v6_range(Ipv6Range::scoped(one, five, Some(4)).unwrap());
split.push_v6_range(Ipv6Range::scoped(six, ten, Some(9)).unwrap());
split.canonicalize();
assert_eq!(split.v6().len(), 2, "adjacent, but on two segments");
let mut joined = IpSet::new();
joined.push_v6_range(Ipv6Range::scoped(one, five, Some(4)).unwrap());
joined.push_v6_range(Ipv6Range::scoped(six, ten, Some(4)).unwrap());
joined.canonicalize();
assert_eq!(joined.v6().len(), 1);
assert!(split.contains(&IpAddr::V6(five)));
assert!(split.contains(&IpAddr::V6(six)));
}
#[test]
fn two_sets_holding_the_same_addresses_are_equal_however_they_were_built() {
let canonical = IpSet::try_from("10.0.0.1-10.0.0.2, ::1").expect("parses");
let mut piecemeal = IpSet::new();
piecemeal.insert(IpAddr::V6(Ipv6Addr::LOCALHOST));
piecemeal.insert(IpAddr::V4(Ipv4Addr::new(10, 0, 0, 2)));
piecemeal.insert(IpAddr::V4(Ipv4Addr::new(10, 0, 0, 1)));
assert_eq!(canonical, piecemeal, "same addresses, different order");
assert_ne!(canonical, IpSet::try_from("10.0.0.1, ::1").expect("parses"));
}
#[test]
fn membership_answers_when_ranges_on_different_interfaces_overlap() {
let one: Ipv6Addr = "fe80::1".parse().unwrap();
let two: Ipv6Addr = "fe80::2".parse().unwrap();
let three: Ipv6Addr = "fe80::3".parse().unwrap();
let ten: Ipv6Addr = "fe80::a".parse().unwrap();
let mut set = IpSet::new();
set.push_v6_range(Ipv6Range::scoped(one, ten, Some(4)).unwrap());
set.push_v6_range(Ipv6Range::scoped(two, three, Some(9)).unwrap());
set.canonicalize();
for address in [one, two, three, ten] {
assert!(
set.contains(&IpAddr::V6(address)),
"{address} is covered by the range on interface 4"
);
}
assert!(!set.contains(&IpAddr::V6("fe80::b".parse().unwrap())));
}
}
#[cfg(test)]
mod property_tests {
use super::*;
use proptest::prelude::*;
fn any_ipv4() -> impl Strategy<Value = Ipv4Addr> {
any::<u32>().prop_map(Ipv4Addr::from)
}
fn any_ipv6() -> impl Strategy<Value = Ipv6Addr> {
any::<u128>().prop_map(Ipv6Addr::from)
}
fn any_zoned_v6_range() -> impl Strategy<Value = Ipv6Range> {
(0..64u128, 0..64u128, prop::option::of(0..4u32)).prop_map(|(a, b, zone)| {
let base = u128::from(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0));
let (low, high) = if a <= b { (a, b) } else { (b, a) };
Ipv6Range::scoped(
Ipv6Addr::from(base + low),
Ipv6Addr::from(base + high),
zone,
)
.expect("low <= high")
})
}
proptest::proptest! {
#[test]
fn zoned_membership_agrees_with_a_linear_scan(
ranges in prop::collection::vec(any_zoned_v6_range(), 1..12),
offsets in prop::collection::vec(0..80u128, 1..20),
) {
let mut set = IpSet::new();
for range in &ranges {
set.push_v6_range(*range);
}
set.canonicalize();
let base = u128::from(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0));
for offset in offsets {
let probe = Ipv6Addr::from(base + offset);
let expected = ranges.iter().any(|range| range.contains(&probe));
prop_assert_eq!(
set.contains(&IpAddr::V6(probe)),
expected,
"{} in {:?}", probe, ranges
);
}
}
#[test]
fn v4_membership_invariant(ips in proptest::collection::vec(any_ipv4(), 1..50)) {
let mut set = IpSet::new();
for &ip in &ips {
set.insert(IpAddr::V4(ip));
}
for ip in ips {
prop_assert!(set.contains(&IpAddr::V4(ip)));
}
}
#[test]
fn v6_membership_invariant(ips in proptest::collection::vec(any_ipv6(), 1..50)) {
let mut set = IpSet::new();
for &ip in &ips {
set.insert(IpAddr::V6(ip));
}
for ip in ips {
prop_assert!(set.contains(&IpAddr::V6(ip)));
}
}
#[test]
fn order_independence_mixed(
ips in proptest::collection::vec(
prop_oneof![
any_ipv4().prop_map(IpAddr::V4),
any_ipv6().prop_map(IpAddr::V6),
],
0..50
)
) {
let mut set1 = IpSet::new();
let mut set2 = IpSet::new();
for &ip in &ips { set1.insert(ip); }
let mut ips_rev = ips.clone();
ips_rev.reverse();
for &ip in &ips_rev { set2.insert(ip); }
set1.canonicalize();
set2.canonicalize();
prop_assert_eq!(set1, set2);
}
}
}