use crate::model::ip::range::{IpRange, Ipv6Range};
use crate::model::ip::scoped::ZoneMap;
use crate::model::ip::set::{IpSet, Positions};
use crate::model::port::{PortSet, Protocol};
use std::{net::IpAddr, ops::Range, sync::Arc};
use thiserror::Error;
#[non_exhaustive]
#[derive(Debug, Clone, PartialEq, Eq, Error)]
pub enum TargetError {
#[error("Target calculation resulted in an integer overflow")]
CapacityOverflow,
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Target {
pub ip: IpAddr,
pub port: u16,
pub protocol: Protocol,
}
impl Target {
pub const fn new(ip: IpAddr, port: u16, protocol: Protocol) -> Self {
Self { ip, port, protocol }
}
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct PlannedTarget {
pub position: u64,
pub target: Target,
}
impl PlannedTarget {
pub fn new(position: u64, target: Target) -> Self {
Self { position, target }
}
pub fn ip(&self) -> IpAddr {
self.target.ip
}
pub fn port(&self) -> u16 {
self.target.port
}
pub fn protocol(&self) -> Protocol {
self.target.protocol
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct TargetSet {
ips: IpSet,
ports: PortSet,
}
impl TargetSet {
pub fn new(mut ips: IpSet, ports: PortSet) -> Self {
ips.canonicalize();
Self { ips, ports }
}
pub fn ips(&self) -> &IpSet {
&self.ips
}
pub fn into_ips(self) -> IpSet {
self.ips
}
pub fn into_parts(self) -> (IpSet, PortSet) {
(self.ips, self.ports)
}
pub fn ports(&self) -> &PortSet {
&self.ports
}
pub fn ip_count(&self) -> u128 {
self.ips.len()
}
pub fn port_count(&self) -> usize {
self.ports.len()
}
pub fn total_targets(&self) -> Result<u128, TargetError> {
let port_len = self.ports.len() as u128;
self.ips
.len()
.checked_mul(port_len)
.ok_or(TargetError::CapacityOverflow)
}
pub fn iter(&self) -> impl Iterator<Item = Target> + Send + '_ {
let ports_arc: Arc<[(u16, Protocol)]> = self.ports.to_vec().into();
self.ips.iter().flat_map(move |ip| {
let ports = Arc::clone(&ports_arc);
(0..ports.len()).map(move |i| {
let (port, protocol) = ports[i];
Target { ip, port, protocol }
})
})
}
pub fn is_empty(&self) -> bool {
self.ips.is_empty() || self.ports.is_empty()
}
}
#[non_exhaustive]
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct TargetMap {
pub units: Vec<TargetSet>,
}
impl TargetMap {
pub fn new() -> Self {
Self::default()
}
pub fn add_unit(&mut self, unit: TargetSet) {
self.units.push(unit);
}
pub fn names(&self, protocol: Protocol) -> bool {
self.units
.iter()
.any(|unit| !unit.ports().ranges(protocol).is_empty())
}
pub fn gross_targets(&self) -> Result<u128, TargetError> {
let mut total: u128 = 0;
for unit in &self.units {
let unit_total = unit.total_targets()?;
total = total
.checked_add(unit_total)
.ok_or(TargetError::CapacityOverflow)?;
}
Ok(total)
}
pub fn gross_ips(&self) -> Result<u128, TargetError> {
let mut total: u128 = 0;
for unit in &self.units {
total = total
.checked_add(unit.ip_count())
.ok_or(TargetError::CapacityOverflow)?;
}
Ok(total)
}
pub fn is_empty(&self) -> bool {
self.units.is_empty() || self.units.iter().all(|u| u.is_empty())
}
pub fn iter(&self) -> impl Iterator<Item = Target> + Send + '_ {
self.units.iter().flat_map(|unit| unit.iter())
}
pub fn withhold_ports(&mut self, excluded: &PortSet) {
if excluded.is_empty() {
return;
}
self.units = std::mem::take(&mut self.units)
.into_iter()
.filter_map(|unit| {
let (ips, ports) = unit.into_parts();
let kept = ports.difference(excluded);
(!kept.is_empty()).then(|| TargetSet::new(ips, kept))
})
.collect();
}
pub(crate) fn take_unprobeable(
&mut self,
interfaces: &[(u32, &str)],
walkable: impl Fn(&Ipv6Range) -> bool,
) -> Unprobeable {
let mut unscoped: Vec<Ipv6Range> = Vec::new();
let mut contested: Vec<Ipv6Range> = Vec::new();
let mut zones = ZoneMap::new();
for range in self.units.iter().flat_map(|unit| unit.ips().v6()) {
if range.is_ambiguous() {
unscoped.push(*range);
} else if zones.contests(range) {
contested.push(*range);
} else {
zones.insert(*range, interfaces);
}
}
self.keep_v6(|range| !unscoped.contains(range) && !contested.contains(range));
unscoped.sort_unstable_by_key(|range| range.start_addr());
unscoped.dedup();
let mut unwalkable: Vec<Ipv6Range> = self
.units
.iter()
.flat_map(|unit| unit.ips().v6().iter().copied())
.filter(|range| !walkable(range))
.collect();
if !unwalkable.is_empty() {
unwalkable.sort_unstable_by_key(|range| range.start_addr());
unwalkable.dedup();
self.keep_v6(&walkable);
}
Unprobeable {
zones,
unscoped,
contested,
unwalkable,
}
}
fn keep_v6(&mut self, keep: impl Fn(&Ipv6Range) -> bool) {
let mut kept = Vec::with_capacity(self.units.len());
for unit in std::mem::take(&mut self.units) {
let (ips, ports) = unit.into_parts();
let mut left = IpSet::new();
for range in ips.v4() {
left.push_v4_range(*range);
}
for range in ips.v6() {
if keep(range) {
left.push_v6_range(*range);
}
}
left.canonicalize();
if !left.is_empty() {
kept.push(TargetSet::new(left, ports));
}
}
self.units = kept;
}
}
pub(crate) struct Unprobeable {
pub(crate) zones: ZoneMap,
pub(crate) unscoped: Vec<Ipv6Range>,
pub(crate) contested: Vec<Ipv6Range>,
pub(crate) unwalkable: Vec<Ipv6Range>,
}
#[derive(Debug, Clone)]
pub struct TargetIndex {
units: Vec<UnitIndex>,
total: u64,
hosts: u64,
complete: bool,
unnumbered: Vec<IpRange>,
}
#[derive(Debug, Clone)]
struct UnitIndex {
addresses: Positions,
ports: Arc<[(u16, Protocol)]>,
start: u64,
len: u64,
first_host: u64,
}
impl TargetIndex {
pub fn of(map: &TargetMap) -> Self {
let mut units = Vec::with_capacity(map.units.len());
let mut total: u64 = 0;
let mut hosts: u64 = 0;
let mut complete = true;
let mut unnumbered = Vec::new();
for (at, unit) in map.units.iter().enumerate() {
let addresses = Positions::of(unit.ips());
let ports: Arc<[(u16, Protocol)]> = unit.ports().to_vec().into();
if ports.is_empty() {
continue;
}
let counted = u64::try_from(ports.len())
.ok()
.and_then(|ports| addresses.total().checked_mul(ports))
.filter(|_| addresses.unnumbered().is_empty());
let Some(len) = counted.filter(|len| total.checked_add(*len).is_some()) else {
complete = false;
for left_out in map.units[at..]
.iter()
.filter(|unit| !unit.ports().is_empty())
{
let ips = left_out.ips();
unnumbered.extend(ips.v4().iter().copied().map(IpRange::V4));
unnumbered.extend(ips.v6().iter().copied().map(IpRange::V6));
}
break;
};
let first_host = hosts;
hosts += addresses.total();
units.push(UnitIndex {
addresses,
ports,
start: total,
len,
first_host,
});
total += len;
}
Self {
units,
total,
hosts,
complete,
unnumbered,
}
}
pub fn total(&self) -> u64 {
self.total
}
pub fn is_complete(&self) -> bool {
self.complete
}
pub fn target_at(&self, position: u64) -> Option<Target> {
let unit = self.unit_at(position)?;
let local = position - unit.start;
let ports = unit.ports.len() as u64;
let (port, protocol) = unit.ports[(local % ports) as usize];
let ip = unit.addresses.address_at(local / ports)?;
Some(Target { ip, port, protocol })
}
pub(crate) fn addresses_in(&self, positions: Range<u64>) -> Vec<IpRange> {
let end = positions.end.min(self.total);
let mut found = Vec::new();
let first = self
.units
.partition_point(|unit| unit.start + unit.len <= positions.start);
for unit in &self.units[first..] {
if unit.start >= end {
break;
}
let from = positions.start.max(unit.start) - unit.start;
let to = end.min(unit.start + unit.len) - unit.start;
if from >= to {
continue;
}
let ports = unit.ports.len() as u64;
let addresses = from / ports..(to - 1) / ports + 1;
found.extend(unit.addresses.ranges_in(addresses));
}
found
}
pub(crate) fn runs_at(&self, ip: IpAddr) -> impl Iterator<Item = Range<u64>> + '_ {
self.units.iter().filter_map(move |unit| {
let ports = unit.ports.len() as u64;
let start = unit.start + unit.addresses.find(ip)? * ports;
Some(start..start + ports)
})
}
pub(crate) fn hosts(&self) -> u64 {
self.hosts
}
pub(crate) fn host_run(&self, host: u64) -> Range<u64> {
let at = self
.units
.partition_point(|unit| unit.first_host + unit.addresses.total() <= host);
let Some(unit) = self.units.get(at) else {
return self.total..self.total;
};
let ports = unit.ports.len() as u64;
let start = unit.start + (host - unit.first_host) * ports;
start..start + ports
}
pub(crate) fn host_of(&self, position: u64) -> u64 {
match self.unit_at(position) {
Some(unit) => unit.first_host + (position - unit.start) / unit.ports.len() as u64,
None => self.hosts,
}
}
pub(crate) fn unnumbered_addresses(&self) -> &[IpRange] {
&self.unnumbered
}
fn unit_at(&self, position: u64) -> Option<&UnitIndex> {
if position >= self.total {
return None;
}
let index = match self
.units
.binary_search_by_key(&position, |unit| unit.start)
{
Ok(index) => index,
Err(0) => return None,
Err(index) => index - 1,
};
self.units
.get(index)
.filter(|unit| position < unit.start + unit.len)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn ips(written: &str) -> IpSet {
written.parse().expect("a valid address specification")
}
fn ports(written: &str) -> PortSet {
written.parse().expect("a valid port specification")
}
fn awkward() -> TargetMap {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(ips("192.0.2.0/29"), ports("22, 80, u:53")));
map.add_unit(TargetSet::new(ips("198.51.100.7"), ports("443")));
map.add_unit(TargetSet::new(
ips("203.0.113.0/30, 192.0.2.200-192.0.2.203"),
ports("1-5, s:2905"),
));
map.add_unit(TargetSet::new(ips("2001:db8::/126"), ports("80, u:161")));
map
}
#[test]
fn a_position_names_the_target_the_plans_own_walk_numbers_it() {
let map = awkward();
let index = TargetIndex::of(&map);
let walked: Vec<Target> = map.iter().collect();
assert!(index.is_complete());
assert_eq!(index.total(), walked.len() as u64);
for (position, expected) in walked.iter().enumerate() {
assert_eq!(
index.target_at(position as u64).as_ref(),
Some(expected),
"position {position}"
);
}
assert_eq!(index.target_at(index.total()), None, "past the end");
}
#[test]
fn the_hosts_tile_the_numbering_one_address_each() {
let index = TargetIndex::of(&awkward());
let mut next = 0;
for host in 0..index.hosts() {
let run = index.host_run(host);
assert_eq!(run.start, next, "host {host} starts where the last ended");
assert!(!run.is_empty());
let first = index.target_at(run.start).expect("inside the numbering");
for position in run.clone() {
assert_eq!(index.host_of(position), host, "position {position}");
let target = index.target_at(position).expect("inside the numbering");
assert_eq!(target.ip, first.ip, "position {position}");
}
next = run.end;
}
assert_eq!(next, index.total(), "and cover it");
assert_eq!(index.host_of(index.total()), index.hosts(), "past the end");
}
#[test]
fn a_unit_with_no_ports_takes_no_positions() {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(ips("192.0.2.1"), ports("22")));
map.add_unit(TargetSet::new(ips("192.0.2.0/24"), PortSet::new()));
map.add_unit(TargetSet::new(ips("192.0.2.2"), ports("80")));
let index = TargetIndex::of(&map);
let walked: Vec<Target> = map.iter().collect();
assert_eq!(index.total(), 2);
assert_eq!(index.total(), walked.len() as u64);
assert_eq!(index.target_at(0).as_ref(), walked.first());
assert_eq!(index.target_at(1).as_ref(), walked.get(1));
}
#[test]
fn a_plan_wider_than_the_numbering_is_incomplete_and_says_so() {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(ips("192.0.2.1"), ports("22")));
map.add_unit(TargetSet::new(ips("2001:db8::/48"), ports("80")));
map.add_unit(TargetSet::new(ips("198.51.100.1"), ports("443")));
let index = TargetIndex::of(&map);
assert!(!index.is_complete());
assert_eq!(index.total(), 1, "only the units before the wide one");
assert_eq!(
index.target_at(1),
None,
"a position the numbering never reached names nothing"
);
}
#[test]
fn a_sixty_four_is_the_first_prefix_the_numbering_cannot_reach() {
let indexed = |prefix: &str| {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(ips(prefix), ports("80")));
TargetIndex::of(&map).is_complete()
};
assert!(indexed("2001:db8::/65"), "a /65 fits");
assert!(!indexed("2001:db8::/64"), "a /64 is one address too many");
assert!(!indexed("2001:db8::/48"), "and anything wider is too");
}
#[test]
fn an_empty_plan_numbers_nothing() {
let index = TargetIndex::of(&TargetMap::new());
assert!(index.is_complete());
assert_eq!(index.total(), 0);
assert_eq!(index.target_at(0), None);
}
#[test]
fn every_span_names_exactly_the_addresses_its_targets_are_at() {
let map = awkward();
let index = TargetIndex::of(&map);
let walked: Vec<Target> = map.iter().collect();
let total = walked.len();
for start in 0..=total {
for end in start..=total + 2 {
let mut expected = IpSet::new();
for target in &walked[start..end.min(total)] {
expected.insert(target.ip);
}
expected.canonicalize();
let mut named = IpSet::new();
for range in index.addresses_in(start as u64..end as u64) {
named.insert_range(range);
}
named.canonicalize();
assert_eq!(named, expected, "positions {start}..{end}");
}
}
assert!(index.unnumbered_addresses().is_empty(), "a complete index");
}
#[test]
fn the_units_past_the_numbering_are_left_out_whole() {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(ips("192.0.2.1"), ports("22")));
map.add_unit(TargetSet::new(ips("2001:db8::/64"), ports("80")));
map.add_unit(TargetSet::new(ips("198.51.100.0/24"), PortSet::new()));
map.add_unit(TargetSet::new(ips("203.0.113.9"), ports("443")));
let index = TargetIndex::of(&map);
let mut unnumbered = IpSet::new();
for range in index.unnumbered_addresses() {
unnumbered.insert_range(*range);
}
unnumbered.canonicalize();
assert!(!index.is_complete());
assert_eq!(unnumbered, ips("2001:db8::/64, 203.0.113.9"));
}
#[test]
fn a_map_says_which_transports_its_units_name() {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(ips("192.0.2.1"), ports("80, u:53")));
assert!(map.names(Protocol::Tcp));
assert!(map.names(Protocol::Udp));
assert!(!map.names(Protocol::Sctp));
map.add_unit(TargetSet::new(ips("192.0.2.2"), ports("s:2905")));
assert!(map.names(Protocol::Sctp));
}
#[test]
fn a_sets_target_count_is_its_addresses_times_its_ports() {
let ts = TargetSet::new(ips("192.0.2.0/24"), ports("80, 443"));
assert_eq!(ts.total_targets().unwrap(), 256 * 2);
}
#[test]
fn a_target_set_merges_its_addresses_on_construction() {
let mut overlapping = ips("192.0.2.0/24");
overlapping.insert_range("192.0.2.128/25".parse().expect("valid range"));
let ts = TargetSet::new(overlapping, ports("80"));
assert_eq!(ts.ip_count(), 256);
assert_eq!(ts.total_targets().unwrap(), 256);
}
#[test]
fn a_set_yields_every_address_paired_with_every_port() {
let ts = TargetSet::new(ips("192.0.2.1-192.0.2.2"), ports("80, u:53"));
let mut targets: Vec<(String, u16, Protocol)> = ts
.iter()
.map(|target| (target.ip.to_string(), target.port, target.protocol))
.collect();
targets.sort();
assert_eq!(
targets,
vec![
("192.0.2.1".to_string(), 53, Protocol::Udp),
("192.0.2.1".to_string(), 80, Protocol::Tcp),
("192.0.2.2".to_string(), 53, Protocol::Udp),
("192.0.2.2".to_string(), 80, Protocol::Tcp),
]
);
}
#[test]
fn a_map_iterates_its_units_in_the_order_they_were_added() {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(ips("192.0.2.1"), ports("80")));
map.add_unit(TargetSet::new(ips("192.0.2.2"), ports("u:53")));
let targets: Vec<(String, u16, Protocol)> = map
.iter()
.map(|target| (target.ip.to_string(), target.port, target.protocol))
.collect();
assert_eq!(
targets,
vec![
("192.0.2.1".to_string(), 80, Protocol::Tcp),
("192.0.2.2".to_string(), 53, Protocol::Udp),
]
);
}
#[test]
fn a_target_count_too_large_to_represent_is_refused_rather_than_wrapped() {
let two_ports = TargetSet::new(ips("::/0"), ports("80, 443"));
assert_eq!(
two_ports.total_targets(),
Err(TargetError::CapacityOverflow)
);
let one_port = TargetSet::new(ips("::/0"), ports("80"));
assert_eq!(one_port.total_targets().unwrap(), u128::MAX);
}
#[test]
fn a_maps_total_is_the_sum_of_its_units() {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(ips("192.0.2.1-192.0.2.5"), ports("80,443")));
assert_eq!(map.gross_targets().unwrap(), 10);
}
}