use std::net::IpAddr;
use std::time::Duration;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Hop {
distance: u8,
answer: Answer,
rtt: Option<Duration>,
inferred: bool,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Answer {
Silent,
Router(IpAddr),
Withheld,
}
impl Hop {
pub fn answered(distance: u8, address: IpAddr, rtt: Option<Duration>) -> Self {
Self {
distance,
answer: Answer::Router(address),
rtt,
inferred: false,
}
}
pub fn silent(distance: u8) -> Self {
Self {
distance,
answer: Answer::Silent,
rtt: None,
inferred: false,
}
}
pub fn withheld(distance: u8) -> Self {
Self {
distance,
answer: Answer::Withheld,
rtt: None,
inferred: false,
}
}
#[must_use]
pub fn as_inferred(mut self) -> Self {
self.inferred = true;
self.rtt = None;
self
}
pub fn distance(&self) -> u8 {
self.distance
}
pub fn address(&self) -> Option<IpAddr> {
match self.answer {
Answer::Router(address) => Some(address),
Answer::Silent | Answer::Withheld => None,
}
}
pub fn rtt(&self) -> Option<Duration> {
self.rtt
}
pub fn is_withheld(&self) -> bool {
self.answer == Answer::Withheld
}
fn is_answer(&self) -> bool {
self.answer != Answer::Silent
}
pub fn inferred(&self) -> bool {
self.inferred
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct NetworkPath {
hops: Vec<Hop>,
}
impl NetworkPath {
pub fn new() -> Self {
Self::default()
}
pub fn record(&mut self, hop: Hop) {
match self
.hops
.binary_search_by_key(&hop.distance, |known| known.distance)
{
Ok(index) => {
let known = &self.hops[index];
let stronger = match (known.is_answer(), hop.is_answer()) {
(false, true) => true,
(true, false) => false,
_ => known.inferred && !hop.inferred,
};
if stronger {
self.hops[index] = hop;
}
}
Err(index) => self.hops.insert(index, hop),
}
}
pub(crate) fn withhold(&mut self, keep: impl Fn(&IpAddr) -> bool) -> bool {
let mut withheld = false;
for hop in &mut self.hops {
if let Answer::Router(address) = hop.answer
&& !keep(&address)
{
*hop = Hop {
inferred: hop.inferred,
..Hop::withheld(hop.distance)
};
withheld = true;
}
}
withheld
}
pub fn hops(&self) -> &[Hop] {
&self.hops
}
pub fn is_empty(&self) -> bool {
self.hops.is_empty()
}
pub fn length(&self) -> Option<u8> {
self.hops.last().map(Hop::distance)
}
pub fn at(&self, distance: u8) -> Option<IpAddr> {
self.hops
.binary_search_by_key(&distance, |hop| hop.distance)
.ok()
.and_then(|index| self.hops[index].address())
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::Ipv4Addr;
fn ip(last: u8) -> IpAddr {
IpAddr::V4(Ipv4Addr::new(10, 0, 0, last))
}
#[test]
fn an_answer_is_never_traded_for_a_silence_that_measured_it() {
let spliced = Hop::answered(4, ip(4), None).as_inferred();
let mut path = NetworkPath::new();
path.record(spliced);
path.record(Hop::silent(4));
assert_eq!(
path.at(4),
Some(ip(4)),
"a measured silence does not erase a router somebody found"
);
let mut reverse = NetworkPath::new();
reverse.record(Hop::silent(4));
reverse.record(spliced);
assert_eq!(reverse.at(4), Some(ip(4)));
let mut both = NetworkPath::new();
both.record(Hop::answered(1, ip(9), None).as_inferred());
both.record(Hop::answered(1, ip(1), None));
assert_eq!(both.at(1), Some(ip(1)), "a measurement beats an inference");
let mut neither = NetworkPath::new();
neither.record(Hop::silent(2));
neither.record(Hop::silent(2).as_inferred());
assert_eq!(neither.hops().len(), 1);
assert!(!neither.hops()[0].inferred());
}
#[test]
fn a_path_reads_in_order_of_distance_however_the_replies_arrived() {
let mut path = NetworkPath::new();
path.record(Hop::answered(3, ip(3), None));
path.record(Hop::answered(1, ip(1), None));
path.record(Hop::answered(2, ip(2), None));
let distances: Vec<u8> = path.hops().iter().map(Hop::distance).collect();
assert_eq!(distances, vec![1, 2, 3]);
assert_eq!(path.length(), Some(3));
assert_eq!(path.at(2), Some(ip(2)));
}
#[test]
fn a_silent_router_holds_its_place() {
let mut path = NetworkPath::new();
path.record(Hop::answered(1, ip(1), None));
path.record(Hop::silent(2));
path.record(Hop::answered(3, ip(3), None));
assert_eq!(path.hops().len(), 3);
assert_eq!(path.at(2), None);
assert_eq!(path.length(), Some(3), "the target is still three away");
}
#[test]
fn a_measurement_outranks_an_inference_and_an_answer_outranks_silence() {
let measured = Hop::answered(2, ip(2), Some(Duration::from_millis(5)));
let inferred = Hop::answered(2, ip(9), None).as_inferred();
let mut upgrading = NetworkPath::new();
upgrading.record(inferred);
upgrading.record(measured);
assert_eq!(upgrading.at(2), Some(ip(2)));
assert!(!upgrading.hops()[0].inferred());
let mut downgrading = NetworkPath::new();
downgrading.record(measured);
downgrading.record(inferred);
assert_eq!(downgrading.at(2), Some(ip(2)), "a measurement is not lost");
assert_eq!(downgrading.hops()[0].rtt(), Some(Duration::from_millis(5)));
let mut filling = NetworkPath::new();
filling.record(Hop::silent(2));
filling.record(measured);
assert_eq!(filling.at(2), Some(ip(2)));
let mut keeping = NetworkPath::new();
keeping.record(measured);
keeping.record(Hop::silent(2));
assert_eq!(
keeping.at(2),
Some(ip(2)),
"silence does not erase an answer"
);
}
#[test]
fn a_withheld_router_still_outranks_silence() {
let spliced = Hop::withheld(3).as_inferred();
let mut path = NetworkPath::new();
path.record(spliced);
path.record(Hop::silent(3));
assert!(path.hops()[0].is_withheld(), "{path:?}");
let mut measured = NetworkPath::new();
measured.record(Hop::answered(3, ip(3), None).as_inferred());
measured.record(Hop::withheld(3));
assert!(measured.hops()[0].is_withheld());
assert!(!measured.hops()[0].inferred());
}
#[test]
fn withholding_a_router_keeps_its_place_and_its_provenance() {
let mut path = NetworkPath::new();
path.record(Hop::answered(1, ip(1), Some(Duration::from_millis(1))));
path.record(Hop::answered(2, ip(2), Some(Duration::from_millis(2))).as_inferred());
path.record(Hop::answered(3, ip(3), Some(Duration::from_millis(3))));
assert!(path.withhold(|address| *address != ip(2)));
let withheld = path.hops()[1];
assert_eq!(withheld.distance(), 2);
assert!(withheld.is_withheld());
assert!(withheld.inferred(), "a spliced router stays marked as one");
assert_eq!(withheld.address(), None);
assert_eq!(withheld.rtt(), None);
assert_eq!(path.at(1), Some(ip(1)), "a permitted router is untouched");
assert_eq!(path.length(), Some(3));
assert!(
!path.withhold(|address| *address != ip(2)),
"there is nothing left to withhold"
);
}
#[test]
fn an_inferred_hop_reports_no_timing_of_its_own() {
let inferred = Hop::answered(4, ip(4), Some(Duration::from_millis(9))).as_inferred();
assert!(inferred.inferred());
assert_eq!(inferred.address(), Some(ip(4)));
assert_eq!(inferred.rtt(), None);
}
}