use std::collections::BTreeSet;
use std::ops::Range;
use serde::{Deserialize, Serialize};
use crate::model::ip::set::{IpSet, Positions};
use crate::model::order::Permutation;
use crate::model::target::{PlannedTarget, Target, TargetIndex};
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Cursor {
watermark: u64,
above: BTreeSet<u64>,
walk: Option<Walked>,
}
impl Cursor {
pub fn new() -> Self {
Self::default()
}
pub fn walking(order: Permutation) -> Self {
Self::new().along(order)
}
pub fn from_checkpoint(checkpoint: &Checkpoint) -> Self {
let walk = checkpoint
.walked
.map(|walked| walked.clamped(checkpoint.watermark));
let mut cursor = Self {
watermark: checkpoint.watermark,
above: checkpoint
.settled_above
.iter()
.copied()
.filter(|position| *position >= checkpoint.watermark)
.filter(|position| !walk.is_some_and(|walk| walk.covers(*position)))
.collect(),
walk,
};
cursor.catch_up();
cursor
}
pub(crate) fn along(mut self, order: Permutation) -> Self {
if self.walk.is_none() {
self.walk = Some(Walked::start(order));
self.catch_up();
}
self
}
pub fn settle(&mut self, position: u64) {
if self.is_settled(position) {
return;
}
self.above.insert(position);
self.catch_up();
}
fn catch_up(&mut self) {
let Self {
watermark,
above,
walk,
} = self;
loop {
loop {
if above.remove(watermark) {
} else if let Some(walk) = walk.as_mut()
&& walk.covers(*watermark)
{
walk.ahead = walk.ahead.saturating_sub(1);
} else {
break;
}
*watermark = watermark.saturating_add(1);
}
let Some(walk) = walk.as_mut() else { return };
let mut walked = false;
while let Some(position) = walk.order().at(walk.reached) {
if position < *watermark {
} else if above.remove(&position) {
walk.ahead = walk.ahead.saturating_add(1);
} else {
break;
}
walk.reached += 1;
walked = true;
}
if !walked {
return;
}
}
}
pub fn watermark(&self) -> u64 {
self.watermark
}
pub fn settled_above(&self) -> impl Iterator<Item = u64> + '_ {
self.above.iter().copied()
}
pub fn is_settled(&self, position: u64) -> bool {
position < self.watermark
|| self.above.contains(&position)
|| self.walk.is_some_and(|walk| walk.covers(position))
}
pub fn settled_count(&self) -> u64 {
self.watermark
.saturating_add(self.walk.map_or(0, |walk| walk.ahead))
.saturating_add(self.above.len() as u64)
}
pub fn pending_count(&self) -> usize {
self.above.len()
}
pub fn checkpoint(&self) -> Checkpoint {
Checkpoint {
watermark: self.watermark,
settled_above: self.above.iter().copied().collect(),
walked: self.walk,
}
}
}
#[non_exhaustive]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
pub struct Walked {
pub seed: u64,
pub len: u64,
pub reached: u64,
pub ahead: u64,
}
impl Walked {
fn start(order: Permutation) -> Self {
Self {
seed: order.seed(),
len: order.len(),
reached: 0,
ahead: 0,
}
}
pub fn order(&self) -> Permutation {
Permutation::new(self.seed, self.len)
}
pub fn covers(&self, position: u64) -> bool {
self.order()
.index_of(position)
.is_some_and(|index| index < self.reached)
}
fn clamped(mut self, watermark: u64) -> Self {
self.reached = self.reached.min(self.len);
self.ahead = self
.ahead
.min(self.reached)
.min(self.len.saturating_sub(watermark));
self
}
}
#[non_exhaustive]
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
pub struct Checkpoint {
pub watermark: u64,
#[serde(default)]
pub settled_above: Vec<u64>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub walked: Option<Walked>,
}
impl Checkpoint {
pub fn new(watermark: u64, settled_above: impl IntoIterator<Item = u64>) -> Self {
let mut settled_above: Vec<u64> = settled_above
.into_iter()
.filter(|position| *position >= watermark)
.collect();
settled_above.sort_unstable();
settled_above.dedup();
Self {
watermark,
settled_above,
walked: None,
}
}
pub fn is_settled(&self, position: u64) -> bool {
position < self.watermark
|| self.settled_above.binary_search(&position).is_ok()
|| self.walked.is_some_and(|walked| walked.covers(position))
}
pub fn settled_count(&self) -> u64 {
let walked = self.walked.map(|walked| walked.clamped(self.watermark));
let above = self
.settled_above
.iter()
.filter(|position| **position >= self.watermark)
.filter(|position| !walked.is_some_and(|walked| walked.covers(**position)))
.count();
self.watermark
.saturating_add(walked.map_or(0, |walked| walked.ahead))
.saturating_add(above as u64)
}
pub fn remaining_addresses(&self, positions: &Positions) -> IpSet {
let mut remaining = IpSet::new();
for span in self.unsettled_spans(positions.total()) {
for range in positions.ranges_in(span) {
remaining.insert_range(range);
}
}
for range in positions.unnumbered() {
remaining.insert_range(*range);
}
remaining.canonicalize();
remaining
}
pub(crate) fn remaining_hosts(&self, index: &TargetIndex) -> IpSet {
let mut remaining = IpSet::new();
for span in self.left_in(index) {
for range in index.addresses_in(span) {
remaining.insert_range(range);
}
}
for range in index.unnumbered_addresses() {
remaining.insert_range(*range);
}
remaining.canonicalize();
remaining
}
fn unsettled_spans(&self, total: u64) -> Vec<Range<u64>> {
self.left_in(&Alone(total))
}
fn left_in(&self, runs: &impl HostRuns) -> Vec<Range<u64>> {
match self.walked {
Some(walked) => self.left_along(walked.clamped(self.watermark), runs),
None => self.spans_between(runs.total()),
}
}
fn left_along(&self, walked: Walked, runs: &impl HostRuns) -> Vec<Range<u64>> {
let total = runs.total();
if self.watermark >= total {
return Vec::new();
}
let first = runs.host_of(self.watermark);
let hosts = runs.hosts() - first;
let past = total - self.watermark;
let tail = walked.len - walked.reached;
let order = walked.order();
let listed = |position: u64| self.settled_above.binary_search(&position).is_ok();
if reads_the_tail(tail, hosts, past) {
let reached = order
.iter_from(walked.reached)
.filter(|position| *position >= self.watermark && *position < total)
.filter(|position| !listed(*position));
let unwalked = self
.gaps_from(walked.len.max(self.watermark), total)
.into_iter()
.flatten();
return marked(runs, first, hosts, reached.chain(unwalked));
}
let unsettled = |position: u64| {
position >= self.watermark
&& !listed(position)
&& !order
.index_of(position)
.is_some_and(|index| index < walked.reached)
};
host_by_host(runs, first..runs.hosts(), unsettled)
}
fn spans_between(&self, total: u64) -> Vec<Range<u64>> {
self.gaps_from(self.watermark, total)
}
fn gaps_from(&self, from: u64, total: u64) -> Vec<Range<u64>> {
let mut above = self.settled_above.clone();
above.sort_unstable();
let mut spans = Vec::with_capacity(above.len() + 1);
let mut from = from;
for settled in above {
if settled < from {
continue;
}
spans.push(from..settled.min(total));
from = settled.saturating_add(1);
}
spans.push(from..total);
spans.retain(|span| span.start < span.end);
spans
}
pub fn remaining<'a, I>(&'a self, targets: I) -> impl Iterator<Item = PlannedTarget> + 'a
where
I: IntoIterator<Item = Target> + 'a,
{
targets
.into_iter()
.enumerate()
.map(|(position, target)| PlannedTarget::new(position as u64, target))
.filter(move |planned| !self.is_settled(planned.position))
}
}
const MARKED_AT_MOST: u64 = 1 << 30;
fn reads_the_tail(tail: u64, hosts: u64, past: u64) -> bool {
let tail = u128::from(tail);
tail * tail < u128::from(hosts) * u128::from(past) && hosts <= MARKED_AT_MOST
}
trait HostRuns {
fn total(&self) -> u64;
fn hosts(&self) -> u64;
fn run(&self, host: u64) -> Range<u64>;
fn host_of(&self, position: u64) -> u64;
}
impl HostRuns for TargetIndex {
fn total(&self) -> u64 {
TargetIndex::total(self)
}
fn hosts(&self) -> u64 {
TargetIndex::hosts(self)
}
fn run(&self, host: u64) -> Range<u64> {
self.host_run(host)
}
fn host_of(&self, position: u64) -> u64 {
TargetIndex::host_of(self, position)
}
}
struct Alone(u64);
impl HostRuns for Alone {
fn total(&self) -> u64 {
self.0
}
fn hosts(&self) -> u64 {
self.0
}
fn run(&self, host: u64) -> Range<u64> {
host..host + 1
}
fn host_of(&self, position: u64) -> u64 {
position
}
}
fn host_by_host(
runs: &impl HostRuns,
hosts: Range<u64>,
mut unsettled: impl FnMut(u64) -> bool,
) -> Vec<Range<u64>> {
let mut spans = Vec::new();
for host in hosts {
let run = runs.run(host);
if run.clone().any(&mut unsettled) {
extend(&mut spans, run);
}
}
spans
}
fn marked(
runs: &impl HostRuns,
first: u64,
hosts: u64,
positions: impl Iterator<Item = u64>,
) -> Vec<Range<u64>> {
let mut bits = vec![0u64; hosts.div_ceil(64) as usize];
for position in positions {
let host = runs.host_of(position) - first;
bits[(host / 64) as usize] |= 1 << (host % 64);
}
let mut spans = Vec::new();
for (at, word) in bits.iter().enumerate() {
let mut word = *word;
while word != 0 {
let host = first + at as u64 * 64 + u64::from(word.trailing_zeros());
extend(&mut spans, runs.run(host));
word &= word - 1;
}
}
spans
}
fn extend(spans: &mut Vec<Range<u64>>, run: Range<u64>) {
match spans.last_mut() {
Some(span) if span.end == run.start => span.end = run.end,
_ => spans.push(run),
}
}
#[cfg(feature = "journal-format")]
mod persistence {
use std::io::Write;
use std::path::Path;
use super::Checkpoint;
use crate::journal::file::replace;
use crate::journal::format::JournalError;
impl Checkpoint {
pub fn write_atomically(&self, path: &Path) -> Result<(), JournalError> {
let text = serde_json::to_string(self).map_err(JournalError::json)?;
replace(path, &path.with_extension("tmp"), |mut file| {
file.write_all(text.as_bytes())
})?;
Ok(())
}
pub fn read(path: &Path) -> Result<Self, JournalError> {
let text = super::super::store::read_bounded(path, "a journal cursor")?;
let mut checkpoint: Self = serde_json::from_str(&text).map_err(JournalError::json)?;
checkpoint.settled_above.sort_unstable();
checkpoint.settled_above.dedup();
Ok(checkpoint)
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::net::IpAddr;
fn addresses(written: &str) -> IpSet {
written.parse().expect("a valid address specification")
}
#[test]
fn a_resumed_sweep_asks_about_exactly_what_did_not_settle() {
let plan = addresses("192.0.2.1-192.0.2.10");
let positions = plan.positions();
let checkpoint = Checkpoint {
watermark: 3,
settled_above: vec![5, 8],
walked: None,
};
let remaining = checkpoint.remaining_addresses(&positions);
let found: Vec<IpAddr> = remaining.iter().collect();
let expected: Vec<IpAddr> = plan
.iter()
.enumerate()
.filter(|(position, _)| !checkpoint.is_settled(*position as u64))
.map(|(_, ip)| ip)
.collect();
assert_eq!(found, expected);
assert_eq!(
found.len(),
5,
"ten addresses, three settled below, two above"
);
}
#[test]
fn a_sweep_that_settled_nothing_resumes_over_the_whole_plan() {
let plan = addresses("192.0.2.1-192.0.2.10,2001:db8::1-2001:db8::4");
let remaining = Checkpoint::default().remaining_addresses(&plan.positions());
assert_eq!(remaining, plan);
}
#[test]
fn a_sweep_of_an_unnumberable_plan_resumes_over_all_of_it() {
let plan = addresses("192.0.2.0/30,2001:db8::/64");
let positions = plan.positions();
let checkpoint = Checkpoint {
watermark: 4,
settled_above: Vec::new(),
walked: None,
};
let remaining = checkpoint.remaining_addresses(&positions);
assert!(
!remaining.is_empty(),
"the /64 was never numbered and so was never settled"
);
assert_eq!(remaining.v4(), &[], "the numbered half did settle");
assert_eq!(remaining.v6(), plan.v6());
}
#[test]
fn a_finished_sweep_resumes_over_nothing() {
let plan = addresses("192.0.2.1-192.0.2.4");
let checkpoint = Checkpoint {
watermark: 4,
settled_above: Vec::new(),
walked: None,
};
assert!(checkpoint.remaining_addresses(&plan.positions()).is_empty());
}
#[test]
fn a_resumed_sweep_keeps_the_original_numbering() {
let plan = addresses("192.0.2.1-192.0.2.10");
let positions = plan.positions();
let checkpoint = Checkpoint {
watermark: 4,
settled_above: Vec::new(),
walked: None,
};
let remaining = checkpoint.remaining_addresses(&positions);
let first = remaining.iter().next().expect("something is left");
assert_eq!(
positions.find(first),
Some(4),
"the fifth address is still the fifth, not the first of what is left"
);
}
#[test]
fn an_unsorted_checkpoint_narrows_the_same_way() {
let plan = addresses("192.0.2.1-192.0.2.10");
let positions = plan.positions();
let sorted = Checkpoint {
watermark: 2,
settled_above: vec![4, 6, 9],
walked: None,
};
let shuffled = Checkpoint {
watermark: 2,
settled_above: vec![9, 4, 6],
walked: None,
};
assert_eq!(
sorted.remaining_addresses(&positions),
shuffled.remaining_addresses(&positions)
);
}
fn ports_plan() -> TargetMap {
let mut map = TargetMap::new();
for (range, ports) in [
("192.0.2.1-192.0.2.5", "22, 80, u:53"),
("198.51.100.7", "443"),
("203.0.113.0/30", "1-4, s:2905"),
("2001:db8::1-2001:db8::3", "80, u:161"),
] {
map.add_unit(TargetSet::new(
range.parse::<IpSet>().expect("a range"),
ports.parse::<PortSet>().expect("ports"),
));
}
map
}
fn hosts_of_remaining(checkpoint: &Checkpoint, map: &TargetMap) -> IpSet {
let mut hosts = IpSet::new();
for planned in checkpoint.remaining(map.iter()) {
hosts.insert(planned.ip());
}
hosts.canonicalize();
hosts
}
#[test]
fn a_resumed_port_scan_sweeps_only_the_hosts_with_a_target_left() {
let map = plan("192.0.2.1-192.0.2.3", "22, 80, 443");
let index = TargetIndex::of(&map);
let finished_second = Checkpoint::new(4, [4, 5]);
assert_eq!(
finished_second.remaining_hosts(&index),
addresses("192.0.2.3"),
"the first two settled every port between the watermark and the \
positions above it"
);
let one_port_short = Checkpoint::new(4, [5]);
assert_eq!(
one_port_short.remaining_hosts(&index),
addresses("192.0.2.2-192.0.2.3"),
"the second host's port at position 4 is still outstanding"
);
}
fn walked(seed: u64, len: u64, reached: u64, watermark: u64, above: Vec<u64>) -> Checkpoint {
Checkpoint {
walked: Some(Walked {
seed,
len,
reached,
ahead: 0,
}),
..Checkpoint::new(watermark, above)
}
}
#[test]
fn a_resume_reads_whichever_of_the_hosts_and_the_tail_is_shorter() {
let hosts: u64 = 1 << 24;
let plan = hosts * 1_000;
assert!(!reads_the_tail(plan / 2, hosts, plan), "half way");
assert!(!reads_the_tail(plan / 16, hosts, plan), "a sixteenth left");
assert!(
reads_the_tail(plan / 64, hosts, plan),
"a sixty-fourth left"
);
assert!(reads_the_tail(plan / 10_000, hosts, plan), "nearly done");
assert!(reads_the_tail(hosts / 2, hosts, hosts), "a sweep half way");
assert!(
!reads_the_tail(1, MARKED_AT_MOST + 1, MARKED_AT_MOST + 1),
"more hosts than a bitmap is kept for"
);
}
#[test]
fn a_wide_port_scan_resumed_half_way_sweeps_every_host() {
let map = plan("198.51.0.0/16", "1-1024");
let index = TargetIndex::of(&map);
let len = index.total();
let remaining = walked(0x5EED, len, len / 2, 0, Vec::new()).remaining_hosts(&index);
assert_eq!(remaining, addresses("198.51.0.0/16"));
}
#[test]
fn a_finished_port_scan_resumes_with_no_host_to_sweep() {
let map = ports_plan();
let index = TargetIndex::of(&map);
let finished = Checkpoint::new(index.total(), []);
assert!(finished.remaining_hosts(&index).is_empty());
}
#[test]
fn a_port_scan_of_an_unnumberable_plan_sweeps_all_of_that_part() {
let mut map = plan("192.0.2.1", "22");
map.add_unit(TargetSet::new(
addresses("2001:db8::/64"),
"80".parse::<PortSet>().expect("ports"),
));
let index = TargetIndex::of(&map);
let remaining = Checkpoint::new(1, []).remaining_hosts(&index);
assert_eq!(remaining, addresses("2001:db8::/64"));
}
proptest::proptest! {
#[test]
fn the_hosts_swept_after_a_walk_are_the_addresses_of_what_is_left(
seed in proptest::prelude::any::<u64>(),
reached in 0u64..=72,
short in 0u64..4,
watermark in 0u64..70,
above in proptest::collection::vec(0u64..72, 0..24),
) {
let map = ports_plan();
let index = TargetIndex::of(&map);
let len = index.total() - short;
let checkpoint = walked(seed, len, reached.min(len), watermark, above);
proptest::prop_assert_eq!(
checkpoint.remaining_hosts(&index),
hosts_of_remaining(&checkpoint, &map)
);
}
#[test]
fn the_hosts_swept_are_the_addresses_of_what_is_left(
watermark in 0u64..70,
above in proptest::collection::vec(0u64..72, 0..24),
) {
let map = ports_plan();
let index = TargetIndex::of(&map);
let checkpoint = Checkpoint::new(watermark, above);
proptest::prop_assert_eq!(
checkpoint.remaining_hosts(&index),
hosts_of_remaining(&checkpoint, &map)
);
}
}
use crate::model::ip::set::IpSet;
use crate::model::port::PortSet;
use crate::model::target::{TargetMap, TargetSet};
fn plan(range: &str, ports: &str) -> TargetMap {
let mut map = TargetMap::new();
map.add_unit(TargetSet::new(
range.parse::<IpSet>().expect("a range"),
ports.parse::<PortSet>().expect("ports"),
));
map
}
#[test]
fn settling_in_order_leaves_nothing_pending() {
let mut cursor = Cursor::new();
for position in 0..10 {
cursor.settle(position);
assert_eq!(cursor.watermark(), position + 1);
assert_eq!(cursor.pending_count(), 0, "nothing should be held");
}
}
#[test]
fn one_unsettled_position_stalls_the_watermark() {
let mut cursor = Cursor::new();
cursor.settle(0);
cursor.settle(1);
for position in 3..1_000 {
cursor.settle(position);
}
assert_eq!(cursor.watermark(), 2, "the gap at 2 must hold the line");
assert!(!cursor.is_settled(2));
assert_eq!(cursor.settled_count(), 999);
cursor.settle(2);
assert_eq!(cursor.watermark(), 1_000);
assert_eq!(cursor.pending_count(), 0);
}
#[test]
fn a_shuffled_walk_holds_only_what_is_in_flight_when_counted_along_it() {
const PLAN: u64 = 4_096;
let order = Permutation::new(7, PLAN);
let asked: Vec<u64> = order.iter().collect();
let mut in_plan_order = Cursor::new();
let mut along = Cursor::walking(order);
for window in asked.chunks(16) {
for position in window.iter().rev() {
in_plan_order.settle(*position);
along.settle(*position);
}
assert!(along.pending_count() < 16, "{}", along.pending_count());
if along.settled_count() == PLAN / 2 {
assert!(
in_plan_order.pending_count() as u64 > PLAN * 2 / 5,
"halfway, {} settled positions wait above a watermark of {}",
in_plan_order.pending_count(),
in_plan_order.watermark()
);
}
}
for cursor in [&in_plan_order, &along] {
assert_eq!(cursor.settled_count(), PLAN);
assert_eq!(cursor.pending_count(), 0);
assert!((0..PLAN).all(|position| cursor.is_settled(position)));
}
}
#[test]
fn a_walked_cursor_settled_in_plan_order_holds_nothing_either() {
let mut cursor = Cursor::walking(Permutation::new(7, 1_000));
for position in 0..1_000 {
cursor.settle(position);
assert_eq!(cursor.pending_count(), 0, "at {position}");
}
assert_eq!(cursor.settled_count(), 1_000);
assert_eq!(cursor.watermark(), 1_000);
}
proptest::proptest! {
#[test]
fn two_watermarks_name_exactly_what_settled(
seed in proptest::prelude::any::<u64>(),
len in 1u64..300,
settled in proptest::collection::vec(0u64..320, 0..400),
walked_first in 0usize..300,
) {
let order = Permutation::new(seed, len);
let mut cursor = Cursor::walking(order);
let mut expected = BTreeSet::new();
for position in order.iter().take(walked_first) {
cursor.settle(position);
expected.insert(position);
}
for position in settled {
cursor.settle(position);
expected.insert(position);
}
let checkpoint = cursor.checkpoint();
let restored = Cursor::from_checkpoint(&checkpoint);
for position in 0..330 {
let want = expected.contains(&position);
proptest::prop_assert_eq!(cursor.is_settled(position), want, "cursor, {}", position);
proptest::prop_assert_eq!(checkpoint.is_settled(position), want, "checkpoint, {}", position);
proptest::prop_assert_eq!(restored.is_settled(position), want, "restored, {}", position);
}
proptest::prop_assert_eq!(cursor.settled_count(), expected.len() as u64);
proptest::prop_assert_eq!(checkpoint.settled_count(), expected.len() as u64);
proptest::prop_assert_eq!(restored.settled_count(), expected.len() as u64);
let total = len + 10;
let spans: Vec<u64> = checkpoint
.unsettled_spans(total)
.into_iter()
.flatten()
.collect();
let rest: Vec<u64> = (0..total).filter(|p| !expected.contains(p)).collect();
proptest::prop_assert_eq!(spans, rest);
}
}
#[test]
fn a_walk_joins_a_cursor_resumed_without_one() {
let order = Permutation::new(11, 64);
let earlier: Vec<u64> = order.iter().take(40).collect();
let checkpoint = Checkpoint::new(0, earlier.iter().copied());
let cursor = Cursor::from_checkpoint(&checkpoint).along(order);
assert_eq!(cursor.pending_count(), 0, "the walk reached all of it");
assert_eq!(cursor.settled_count(), 40);
assert!(earlier.iter().all(|position| cursor.is_settled(*position)));
}
#[cfg(feature = "journal-format")]
#[test]
fn an_older_reader_takes_a_walked_checkpoint_for_less_than_it_settled() {
#[derive(Deserialize)]
struct Older {
watermark: u64,
#[serde(default)]
settled_above: Vec<u64>,
}
let order = Permutation::new(3, 500);
let mut cursor = Cursor::walking(order);
for position in order.iter().take(300) {
cursor.settle(position);
}
cursor.settle(order.at(310).expect("inside the walk"));
let written = serde_json::to_string(&cursor.checkpoint()).expect("serializes");
let older: Older = serde_json::from_str(&written).expect("an older reader reads it");
let older = Checkpoint::new(older.watermark, older.settled_above);
assert!(older.settled_count() < cursor.settled_count());
for position in 0..500 {
assert!(
!older.is_settled(position) || cursor.is_settled(position),
"position {position} read as settled when it was not"
);
}
}
#[test]
fn the_watermark_is_independent_of_arrival_order() {
let forwards = {
let mut cursor = Cursor::new();
for position in 0..64 {
cursor.settle(position);
}
cursor
};
let backwards = {
let mut cursor = Cursor::new();
for position in (0..64).rev() {
cursor.settle(position);
}
cursor
};
let scattered = {
let mut cursor = Cursor::new();
for position in [7, 3, 63, 0, 1, 2, 4, 5, 6] {
cursor.settle(position);
}
for position in 8..63 {
cursor.settle(position);
}
cursor
};
assert_eq!(forwards.watermark(), 64);
assert_eq!(backwards.watermark(), 64);
assert_eq!(scattered.watermark(), 64);
assert_eq!(forwards, backwards);
assert_eq!(forwards, scattered);
}
#[test]
fn settling_the_same_position_twice_is_idempotent() {
let mut cursor = Cursor::new();
cursor.settle(0);
cursor.settle(0);
cursor.settle(0);
assert_eq!(cursor.watermark(), 1);
cursor.settle(5);
cursor.settle(5);
assert_eq!(cursor.pending_count(), 1);
assert_eq!(cursor.settled_count(), 2);
}
#[test]
fn a_cursor_survives_a_checkpoint() {
let mut cursor = Cursor::new();
for position in [0, 1, 2, 9, 11, 12] {
cursor.settle(position);
}
let restored = Cursor::from_checkpoint(&cursor.checkpoint());
assert_eq!(restored, cursor);
assert_eq!(restored.watermark(), 3);
assert!(restored.is_settled(9));
assert!(!restored.is_settled(3));
}
#[test]
fn remaining_yields_only_what_was_not_settled() {
let map = plan("192.0.2.1-192.0.2.4", "80,443");
let all: Vec<Target> = map.iter().collect();
assert_eq!(all.len(), 8, "four addresses on two ports");
let mut cursor = Cursor::new();
for position in [0, 1, 2, 5] {
cursor.settle(position);
}
let remaining: Vec<PlannedTarget> = cursor.checkpoint().remaining(map.iter()).collect();
assert_eq!(
remaining,
vec![
PlannedTarget::new(3, all[3]),
PlannedTarget::new(4, all[4]),
PlannedTarget::new(6, all[6]),
PlannedTarget::new(7, all[7]),
]
);
}
#[test]
fn the_empty_and_complete_cases_are_both_exact() {
let map = plan("192.0.2.1-192.0.2.4", "80,443");
let total = map.iter().count();
let untouched = Cursor::new().checkpoint();
assert_eq!(untouched.remaining(map.iter()).count(), total);
let mut finished = Cursor::new();
for position in 0..total as u64 {
finished.settle(position);
}
assert_eq!(finished.checkpoint().remaining(map.iter()).count(), 0);
assert_eq!(finished.watermark(), total as u64);
}
#[test]
fn positions_follow_the_plans_own_enumeration() {
let mut map = plan("192.0.2.1-192.0.2.2", "80,443");
map.add_unit(TargetSet::new(
"198.51.100.7".parse::<IpSet>().expect("a range"),
"22".parse::<PortSet>().expect("ports"),
));
let once: Vec<Target> = map.iter().collect();
let twice: Vec<Target> = map.iter().collect();
assert_eq!(once, twice, "the enumeration must be reproducible");
assert_eq!(once.len(), 5, "two units, four targets then one");
assert_eq!(
once[4].ip,
"198.51.100.7".parse::<std::net::IpAddr>().unwrap(),
"units are walked in the order they were added"
);
}
#[cfg(feature = "journal-format")]
#[test]
fn a_checkpoint_round_trips_through_a_file() {
let dir = std::env::temp_dir().join(format!(
"zond-cursor-{}-{:?}",
std::process::id(),
std::thread::current().id()
));
std::fs::create_dir_all(&dir).expect("scratch directory");
let path = dir.join("cursor.json");
let mut cursor = Cursor::new();
for position in [0, 1, 2, 9, 11, 12] {
cursor.settle(position);
}
cursor.checkpoint().write_atomically(&path).expect("writes");
assert_eq!(Checkpoint::read(&path).expect("reads"), cursor.checkpoint());
cursor.settle(3);
cursor
.checkpoint()
.write_atomically(&path)
.expect("rewrites");
let reread = Checkpoint::read(&path).expect("rereads");
assert_eq!(reread.watermark, 4);
assert!(
!dir.join("cursor.tmp").exists(),
"the temporary file must not survive the rename"
);
std::fs::remove_dir_all(&dir).ok();
}
#[cfg(feature = "journal-format")]
#[test]
fn a_checkpoint_with_an_unsorted_list_is_sorted_on_read() {
let dir = std::env::temp_dir().join(format!(
"zond-cursor-unsorted-{}-{:?}",
std::process::id(),
std::thread::current().id()
));
std::fs::create_dir_all(&dir).expect("scratch directory");
let path = dir.join("cursor.json");
std::fs::write(&path, r#"{"watermark":2,"settled_above":[9,4,7,4]}"#).expect("writes");
let checkpoint = Checkpoint::read(&path).expect("reads");
assert_eq!(
checkpoint.settled_above,
vec![4, 7, 9],
"sorted and deduped"
);
for position in [4, 7, 9] {
assert!(checkpoint.is_settled(position), "{position} is in the file");
}
assert!(!checkpoint.is_settled(3));
std::fs::remove_dir_all(&dir).ok();
}
#[test]
fn a_checkpoint_with_redundant_positions_normalises() {
let checkpoint = Checkpoint {
watermark: 5,
settled_above: vec![1, 2, 5, 6],
walked: None,
};
let cursor = Cursor::from_checkpoint(&checkpoint);
assert_eq!(cursor.watermark(), 7, "5 and 6 are contiguous with 5");
assert_eq!(cursor.pending_count(), 0);
assert_eq!(cursor.settled_count(), 7);
}
}