Skip to main content

zond_engine/model/ip/
set.rs

1// Copyright (c) 2026 Erik Lening (hollowpointer) and Contributors
2//
3// This file is part of Zond Engine, licensed under the GNU Affero General
4// Public License, version 3 or later. See the LICENSE file for details, or
5// <https://www.gnu.org/licenses/agpl-3.0.html>.
6//
7// SPDX-License-Identifier: AGPL-3.0-or-later
8
9//! # IP address sets
10//!
11//! [`IpSet`] holds the addresses a scan is about, as sorted non-overlapping
12//! ranges. In that form a `/8` costs one range rather than sixteen million
13//! addresses.
14//!
15//! ## Merging is lazy
16//!
17//! Insertion appends in constant time; sorting and merging is `O(n log n)` and happens
18//! once, at [`IpSet::canonicalize`]. A target file can name tens of thousands of ranges,
19//! and merging after each would make loading quadratic.
20//!
21//! Every query is correct either way: [`contains`](IpSet::contains) and
22//! [`len`](IpSet::len) take a fast path over merged ranges and a slower one otherwise.
23//! Canonicalize when a set stops being built and starts being read.
24//!
25//! [`TargetSet::new`](crate::model::target::TargetSet::new) canonicalizes what it is
26//! given, so everything downstream of a `TargetSet` reads merged ranges.
27
28use super::range::{IpError, IpRange, Ipv4Range, Ipv6Range};
29use std::cmp::Ordering;
30use std::ops::Range;
31use std::{
32    borrow::Cow,
33    net::{IpAddr, Ipv4Addr, Ipv6Addr},
34    str::FromStr,
35};
36
37/// Why a written address specification could not be read as a set.
38///
39/// Wraps the range grammar's error. For the richer
40/// [`IpParseError`](crate::model::parse::ip::IpParseError), which names both prefix
41/// bounds and quotes the expression, use [`to_set`](crate::model::parse::ip::to_set);
42/// `parse` depends on `ip`, so this module cannot use it.
43#[non_exhaustive]
44#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
45pub enum IpSetError {
46    /// The text named something that is not an address or a range.
47    #[error("Invalid target in set: {0}")]
48    InvalidTarget(#[from] IpError),
49}
50
51// ══════════════════════════════════════════════════════════════════════════════
52// IpSet core model
53// ══════════════════════════════════════════════════════════════════════════════
54
55/// A collection of unique IP addresses stored as sorted, non-overlapping ranges.
56///
57/// Merges overlapping and adjacent ranges lazily.
58///
59/// Equality is over the addresses held; see the hand-written [`PartialEq`].
60#[derive(Debug, Clone, Default, Eq)]
61pub struct IpSet {
62    v4: Vec<Ipv4Range>,
63    v6: Vec<Ipv6Range>,
64    v4_dirty: bool,
65    v6_dirty: bool,
66}
67
68/// How many ranges this thread has added to a set, a single address being a
69/// range of one, for a test that has to know a set was built from only what
70/// it needed to hold.
71///
72/// Counted where a range first enters a set. Per thread, so concurrent tests do not
73/// interfere.
74#[cfg(test)]
75pub(crate) mod ranges_added {
76    use std::cell::Cell;
77
78    thread_local! {
79        static ADDED: Cell<usize> = const { Cell::new(0) };
80    }
81
82    /// Counts one range added.
83    pub(super) fn note() {
84        ADDED.with(|added| added.set(added.get() + 1));
85    }
86
87    /// How many ranges this thread has added.
88    pub(crate) fn so_far() -> usize {
89        ADDED.with(Cell::get)
90    }
91}
92
93impl IpSet {
94    /// Creates a new, empty `IpSet`.
95    pub fn new() -> Self {
96        Self::default()
97    }
98
99    // ─── Insertion API ───────────────────────────────────────────────────────
100
101    /// Adds a single IP address to the set.
102    ///
103    /// Constant time: it appends and defers the merge.
104    pub fn insert(&mut self, ip: IpAddr) {
105        match ip {
106            IpAddr::V4(v4) => self.push_v4_range(Ipv4Range::single(v4)),
107            IpAddr::V6(v6) => self.push_v6_range(Ipv6Range::single(v6)),
108        }
109    }
110
111    /// Adds a unified IP range to the set.
112    pub fn insert_range(&mut self, range: IpRange) {
113        match range {
114            IpRange::V4(r) => self.push_v4_range(r),
115            IpRange::V6(r) => self.push_v6_range(r),
116        }
117    }
118
119    /// Appends an IPv4 range without immediate merging.
120    pub fn push_v4_range(&mut self, range: Ipv4Range) {
121        #[cfg(test)]
122        ranges_added::note();
123        self.v4.push(range);
124        self.v4_dirty = true;
125    }
126
127    /// Appends an IPv6 range without immediate merging.
128    pub fn push_v6_range(&mut self, range: Ipv6Range) {
129        #[cfg(test)]
130        ranges_added::note();
131        self.v6.push(range);
132        self.v6_dirty = true;
133    }
134
135    /// Sorts and merges the ranges, so that every read afterwards takes its
136    /// fast path.
137    ///
138    /// Call it once the set stops being built. Not required for correctness, but an
139    /// unmerged set answers by scanning, which a set read per received packet should
140    /// not.
141    pub fn canonicalize(&mut self) {
142        if self.v4_dirty {
143            if !self.v4.is_empty() {
144                self.merge_v4();
145            }
146            self.v4_dirty = false;
147        }
148        if self.v6_dirty {
149            if !self.v6.is_empty() {
150                self.merge_v6();
151            }
152            self.v6_dirty = false;
153        }
154    }
155
156    fn merge_v4(&mut self) {
157        self.v4.sort_by_key(|r| r.start_addr());
158        let mut merged: Vec<Ipv4Range> = Vec::with_capacity(self.v4.len());
159        let mut current = self.v4[0];
160
161        for next in self.v4.drain(1..) {
162            let curr_end = u32::from(current.end_addr());
163            let next_start = u32::from(next.start_addr());
164
165            if next_start <= curr_end.saturating_add(1) {
166                current.extend_end_to(next.end_addr());
167            } else {
168                merged.push(current);
169                current = next;
170            }
171        }
172        merged.push(current);
173        self.v4 = merged;
174    }
175
176    /// Sorts and merges the IPv6 ranges, keeping ranges on different interfaces
177    /// apart.
178    ///
179    /// The same link-local numbers on two interfaces are two sets of machines, so
180    /// ranges merge only when their zones agree.
181    ///
182    /// Sorted by zone first, leaving one run per interface, each sorted and disjoint,
183    /// which [`v6_runs`](Self::v6_runs) hands the binary search. Grouping by zone also
184    /// keeps same-zone ranges adjacent, so they always merge.
185    fn merge_v6(&mut self) {
186        self.v6.sort_by_key(|r| (r.zone(), r.start_addr()));
187        let mut merged: Vec<Ipv6Range> = Vec::with_capacity(self.v6.len());
188        let mut current = self.v6[0];
189
190        for next in self.v6.drain(1..) {
191            let curr_end = u128::from(current.end_addr());
192            let next_start = u128::from(next.start_addr());
193
194            if next.zone() == current.zone() && next_start <= curr_end.saturating_add(1) {
195                current.extend_end_to(next.end_addr());
196            } else {
197                merged.push(current);
198                current = next;
199            }
200        }
201        merged.push(current);
202        self.v6 = merged;
203    }
204
205    // ─── Set arithmetic ──────────────────────────────────────────────────────
206
207    /// Removes every address `other` holds from this set.
208    ///
209    /// This set is canonicalized first and left that way; `other` is read in whatever
210    /// state it is in. Afterwards [`contains`](Self::contains) answers `false` for every
211    /// address `other` contained, which makes this usable as a policy.
212    ///
213    /// Ignores zones, as [`contains`](Self::contains) does: a range in `other` removes
214    /// those addresses from every interface. The two must agree, since received replies
215    /// arrive as bare addresses. This errs toward removing more, which is the safe
216    /// direction for withholding addresses from a scan.
217    ///
218    /// Linear in the *ranges* of both sides: subtracting a `/24` from a `/8` is a
219    /// handful of comparisons.
220    pub fn subtract(&mut self, other: &IpSet) {
221        if other.is_empty() || self.is_empty() {
222            return;
223        }
224        self.canonicalize();
225
226        if !self.v4.is_empty() {
227            let cuts = merged_intervals(other.v4.iter().map(v4_bounds));
228            if !cuts.is_empty() {
229                self.v4 = subtract_run(&self.v4, &cuts, v4_bounds, |_, start, end| {
230                    // Both ends came from a `u32`-derived range and only narrow, so
231                    // the casts are exact.
232                    Ipv4Range::new(Ipv4Addr::from(start as u32), Ipv4Addr::from(end as u32))
233                        .unwrap_or_else(|_| unreachable!("a narrowed range keeps start <= end"))
234                });
235            }
236        }
237
238        if !self.v6.is_empty() {
239            let cuts = merged_intervals(other.v6.iter().map(v6_bounds));
240            if !cuts.is_empty() {
241                // One run per interface, since only within a run are the ranges
242                // disjoint. Each piece keeps its zone, so the result stays grouped
243                // as `merge_v6` left it.
244                let mut kept = Vec::with_capacity(self.v6.len());
245                for run in self.v6_runs() {
246                    kept.extend(subtract_run(run, &cuts, v6_bounds, |range, start, end| {
247                        Ipv6Range::scoped(Ipv6Addr::from(start), Ipv6Addr::from(end), range.zone())
248                            .unwrap_or_else(|_| unreachable!("a narrowed range keeps start <= end"))
249                    }));
250                }
251                self.v6 = kept;
252            }
253        }
254    }
255
256    /// The merged IPv6 ranges, one slice per interface.
257    ///
258    /// Each slice is sorted and disjoint, as [`holds`] needs; the vector as a whole is
259    /// not. One slice per distinct zone.
260    fn v6_runs(&self) -> impl Iterator<Item = &[Ipv6Range]> {
261        let mut rest = self.v6.as_slice();
262
263        std::iter::from_fn(move || {
264            let zone = rest.first()?.zone();
265            // Sorted by zone first, so this run is a prefix of what is left.
266            let (run, tail) = rest.split_at(rest.partition_point(|r| r.zone() == zone));
267            rest = tail;
268            Some(run)
269        })
270    }
271
272    // ─── Query API (Lazy) ────────────────────────────────────────────────────
273
274    /// Checks if the set contains the given IP address, on any interface.
275    ///
276    /// Ignores zones: callers filter received replies, which arrive as bare addresses,
277    /// and the receiving strategy is already bound to one segment.
278    ///
279    /// Correct in any state: a binary search when the address's family is merged, a
280    /// non-allocating linear scan when it is not. Checked per family, so an unmerged
281    /// IPv4 range does not slow IPv6 lookups.
282    pub fn contains(&self, ip: &IpAddr) -> bool {
283        if self.is_merged(ip) {
284            return self.contains_canonical(ip);
285        }
286        match ip {
287            IpAddr::V4(v4) => self.v4.iter().any(|range| range.contains(v4)),
288            IpAddr::V6(v6) => self.v6.iter().any(|range| range.contains(v6)),
289        }
290    }
291
292    /// The number of distinct addresses the set covers.
293    ///
294    /// Overlaps count once, so an unmerged set is merged on a clone first.
295    /// [`len_gross`](Self::len_gross) is the cheap over-estimate.
296    pub fn len(&self) -> u128 {
297        if !self.v4_dirty && !self.v6_dirty {
298            self.len_canonical()
299        } else {
300            let mut temp = self.clone();
301            temp.canonicalize();
302            temp.len_canonical()
303        }
304    }
305
306    /// Returns `true` if the set is empty.
307    pub fn is_empty(&self) -> bool {
308        self.v4.is_empty() && self.v6.is_empty()
309    }
310
311    /// How many addresses the ranges cover, counting overlaps once per range
312    /// they appear in.
313    ///
314    /// One pass and no allocation, unlike [`len`](Self::len) on an unmerged set. Never
315    /// lower than the true count, so a budget check errs early.
316    pub fn len_gross(&self) -> u128 {
317        self.v4_len().saturating_add(self.v6_len())
318    }
319
320    /// Every address the set covers, one at a time, IPv4 before IPv6.
321    ///
322    /// Each address once, however many ranges named it, so an unmerged set is merged
323    /// on a clone; call [`canonicalize`](Self::canonicalize) first to skip the copy.
324    ///
325    /// Lazy: nothing is materialized.
326    pub fn iter(&self) -> Box<dyn Iterator<Item = IpAddr> + Send + '_> {
327        if self.v4_dirty || self.v6_dirty {
328            let mut temp = self.clone();
329            temp.canonicalize();
330            temp.into_iter()
331        } else {
332            let v4_iter = self.v4.iter().flat_map(|range| range.iter());
333            let v6_iter = self.v6.iter().flat_map(|range| range.iter());
334            Box::new(v4_iter.chain(v6_iter))
335        }
336    }
337
338    /// Every address the set covers, each paired with the interface index it is
339    /// only meaningful on.
340    ///
341    /// The zone lives on the range, so [`iter`](Self::iter) cannot report it. An IPv6
342    /// address yields its range's zone; IPv4 always yields `None`.
343    ///
344    /// ```
345    /// use zond_engine::model::ip::{IpRange, set::IpSet};
346    /// use zond_engine::model::ip::range::Ipv6Range;
347    /// use std::net::{IpAddr, Ipv6Addr};
348    ///
349    /// let addr: Ipv6Addr = "fe80::1".parse().unwrap();
350    /// let mut set = IpSet::new();
351    /// set.insert_range(IpRange::V6(Ipv6Range::scoped(addr, addr, Some(7)).unwrap()));
352    ///
353    /// let held: Vec<_> = set.iter_scoped().collect();
354    /// assert_eq!(held, vec![(IpAddr::V6(addr), Some(7))]);
355    /// ```
356    pub fn iter_scoped(&self) -> Box<dyn Iterator<Item = (IpAddr, Option<u32>)> + Send> {
357        let (v4, v6) = if self.v4_dirty || self.v6_dirty {
358            let mut merged = self.clone();
359            merged.canonicalize();
360            (merged.v4, merged.v6)
361        } else {
362            (self.v4.clone(), self.v6.clone())
363        };
364
365        let v4 = v4.into_iter().flat_map(|range| {
366            let start: u32 = range.start_addr().into();
367            let end: u32 = range.end_addr().into();
368            (start..=end).map(|ip| (IpAddr::V4(Ipv4Addr::from(ip)), None))
369        });
370        let v6 = v6.into_iter().flat_map(|range| {
371            let zone = range.zone();
372            let start: u128 = range.start_addr().into();
373            let end: u128 = range.end_addr().into();
374            (start..=end).map(move |ip| (IpAddr::V6(Ipv6Addr::from(ip)), zone))
375        });
376
377        Box::new(v4.chain(v6))
378    }
379
380    // ─── Query API (Read-Only / Sync) ────────────────────────────────────────
381
382    /// Whether the family `ip` belongs to has been merged.
383    ///
384    /// What [`contains`](Self::contains) checks before its fast path, per family. Over a
385    /// thousand merged IPv6 ranges with one IPv4 address pushed afterwards, twenty
386    /// thousand lookups took 276 ms on the linear path and 6.5 ms on the merged one.
387    fn is_merged(&self, ip: &IpAddr) -> bool {
388        match ip {
389            IpAddr::V4(_) => !self.v4_dirty,
390            IpAddr::V6(_) => !self.v6_dirty,
391        }
392    }
393
394    /// The fast path [`contains`](Self::contains) takes on a merged family.
395    ///
396    /// Private, since only a debug assertion guards against searching unsorted ranges,
397    /// and a wrong answer decides whether a reply is credited.
398    ///
399    /// # Panics
400    ///
401    /// In debug builds, if the address's own family has unmerged ranges pending.
402    fn contains_canonical(&self, ip: &IpAddr) -> bool {
403        debug_assert!(
404            self.is_merged(ip),
405            "IpSet must be canonicalized before calling contains_canonical"
406        );
407        match ip {
408            IpAddr::V4(v4) => holds(&self.v4, u128::from(u32::from(*v4)), |range| {
409                (
410                    u128::from(u32::from(range.start_addr())),
411                    u128::from(u32::from(range.end_addr())),
412                )
413            }),
414            IpAddr::V6(v6) => {
415                let target = u128::from(*v6);
416                self.v6_runs().any(|run| {
417                    holds(run, target, |range| {
418                        (u128::from(range.start_addr()), u128::from(range.end_addr()))
419                    })
420                })
421            }
422        }
423    }
424
425    /// The fast path [`len`](Self::len) takes on a merged set. Private for the
426    /// same reason [`contains_canonical`](Self::contains_canonical) is.
427    ///
428    /// # Panics
429    ///
430    /// In debug builds, if the set has unmerged ranges pending.
431    fn len_canonical(&self) -> u128 {
432        debug_assert!(
433            !self.v4_dirty && !self.v6_dirty,
434            "IpSet must be canonicalized before calling len_canonical"
435        );
436        self.v4_len().saturating_add(self.v6_len())
437    }
438
439    /// How many addresses the IPv4 ranges cover, and how many the IPv6 ones do.
440    ///
441    /// Per family, for a sweep that spaces ARP against neighbour solicitation by their
442    /// relative volume. Overlaps count twice; these only steer pacing.
443    ///
444    /// Saturating, as [`Ipv6Range::len`](crate::model::ip::range::Ipv6Range::len) is.
445    pub fn v4_len(&self) -> u128 {
446        self.v4
447            .iter()
448            .fold(0u128, |total, r| total.saturating_add(r.len() as u128))
449    }
450
451    /// The IPv6 half of [`v4_len`](Self::v4_len).
452    pub fn v6_len(&self) -> u128 {
453        self.v6
454            .iter()
455            .fold(0u128, |total, r| total.saturating_add(r.len()))
456    }
457
458    /// Returns the underlying IPv4 ranges. If dirty, these ranges may be overlapping and un-merged.
459    pub fn v4(&self) -> &[Ipv4Range] {
460        &self.v4
461    }
462
463    /// Returns the underlying IPv6 ranges. If dirty, these ranges may be overlapping and un-merged.
464    pub fn v6(&self) -> &[Ipv6Range] {
465        &self.v6
466    }
467}
468
469impl PartialEq for IpSet {
470    /// Whether the two sets hold the same addresses.
471    ///
472    /// Hand-written, since a derive would compare the raw range vectors and dirty
473    /// flags.
474    ///
475    /// An unmerged set is merged on a clone, as in [`len`](Self::len). Two
476    /// canonicalized sets compare without allocating.
477    fn eq(&self, other: &Self) -> bool {
478        fn merged(set: &IpSet) -> Cow<'_, IpSet> {
479            if set.v4_dirty || set.v6_dirty {
480                let mut owned = set.clone();
481                owned.canonicalize();
482                Cow::Owned(owned)
483            } else {
484                Cow::Borrowed(set)
485            }
486        }
487
488        let (this, that) = (merged(self), merged(other));
489        this.v4 == that.v4 && this.v6 == that.v6
490    }
491}
492
493/// Where each of an [`IpSet`]'s addresses falls in its enumeration.
494///
495/// An address's index in [`IpSet::iter`]'s walk (merged IPv4 ranges ascending, then
496/// IPv6) is its **position**. A sweep is counted in positions, as a port scan is in
497/// [`PlannedTarget`](crate::model::target::PlannedTarget)s, so a journal records
498/// progress without listing addresses.
499///
500/// Built from the ranges: a `/8` costs one entry and a lookup is a binary search, so
501/// this is cheap enough to consult per probe.
502///
503/// # A set larger than a position can count
504///
505/// A position is a `u64`, and a `/64` is one address past what that counts. Ranges are
506/// numbered in order until one would not fit, and the rest is **unnumbered**:
507/// [`find`](Self::find) answers `None` and [`unnumbered`](Self::unnumbered) returns it
508/// whole. Unnumbered addresses are asked again on every sitting. IPv4 is numbered first,
509/// so it is never lost.
510#[derive(Debug, Clone, Default)]
511pub struct Positions {
512    /// The ranges in enumeration order, each with the position of its first
513    /// address. IPv4 before IPv6, ascending within each.
514    spans: Vec<Span>,
515    /// The stretches of `spans` that are sorted and disjoint *by address*, so
516    /// that a binary search inside one is valid.
517    ///
518    /// IPv4 is one run; IPv6 is one per interface, since the set sorts by zone first.
519    /// [`contains`](IpSet::contains) walks the same runs.
520    runs: Vec<Run>,
521    /// How many addresses are numbered, which is every address of every span.
522    total: u64,
523    /// The ranges the numbering could not reach, in enumeration order.
524    unnumbered: Vec<IpRange>,
525}
526
527/// One stretch of [`Positions::spans`] that a binary search may be run over.
528#[derive(Debug, Clone, Copy)]
529struct Run {
530    /// Where the stretch starts in `spans`.
531    from: usize,
532    /// Where it ends, exclusive.
533    to: usize,
534    /// Whether these are IPv6 ranges. The families never share a run.
535    v6: bool,
536}
537
538/// One range, and where its addresses sit in the enumeration.
539#[derive(Debug, Clone, Copy)]
540struct Span {
541    range: IpRange,
542    /// The position of the range's first address.
543    start: u64,
544    /// How many addresses it holds. Never zero: a range holds at least one.
545    len: u64,
546}
547
548impl Positions {
549    /// Numbers `set`'s addresses.
550    ///
551    /// An unmerged set is merged on a clone first, since positions count the canonical
552    /// enumeration.
553    pub fn of(set: &IpSet) -> Self {
554        if set.v4_dirty || set.v6_dirty {
555            let mut merged = set.clone();
556            merged.canonicalize();
557            return Self::of_canonical(&merged);
558        }
559        Self::of_canonical(set)
560    }
561
562    fn of_canonical(set: &IpSet) -> Self {
563        let ranges = set
564            .v4
565            .iter()
566            .copied()
567            .map(IpRange::V4)
568            .chain(set.v6.iter().copied().map(IpRange::V6));
569
570        let mut spans = Vec::new();
571        let mut runs: Vec<Run> = Vec::new();
572        let mut total: u64 = 0;
573        let mut group: Option<(bool, Option<u32>)> = None;
574        let mut unnumbered = Vec::new();
575
576        for range in ranges {
577            // The first range that will not fit ends the numbering, since positions
578            // must stay contiguous. The rest is kept so a resumed sitting asks
579            // about it.
580            if !unnumbered.is_empty() {
581                unnumbered.push(range);
582                continue;
583            }
584            let Ok(len) = u64::try_from(range.len()) else {
585                unnumbered.push(range);
586                continue;
587            };
588            let Some(next) = total.checked_add(len) else {
589                unnumbered.push(range);
590                continue;
591            };
592
593            let here = match range {
594                IpRange::V4(_) => (false, None),
595                IpRange::V6(v6) => (true, v6.zone()),
596            };
597            match runs.last_mut() {
598                Some(run) if group == Some(here) => run.to = spans.len() + 1,
599                _ => runs.push(Run {
600                    from: spans.len(),
601                    to: spans.len() + 1,
602                    v6: here.0,
603                }),
604            }
605            group = Some(here);
606
607            spans.push(Span {
608                range,
609                start: total,
610                len,
611            });
612            total = next;
613        }
614
615        Self {
616            spans,
617            runs,
618            total,
619            unnumbered,
620        }
621    }
622
623    /// How many addresses are numbered.
624    pub fn total(&self) -> u64 {
625        self.total
626    }
627
628    /// Whether nothing is numbered at all.
629    ///
630    /// A plan whose first range is too large is empty by this; see
631    /// [`unnumbered`](Self::unnumbered).
632    pub fn is_empty(&self) -> bool {
633        self.total == 0
634    }
635
636    /// The ranges the numbering could not reach, in enumeration order.
637    ///
638    /// Empty for every IPv4 plan and every IPv6 plan narrower than a `/64`. A resumed
639    /// sweep asks about these again, since nothing is recorded against them.
640    pub fn unnumbered(&self) -> &[IpRange] {
641        &self.unnumbered
642    }
643
644    /// Where `ip` falls in the enumeration, or `None` when the set does not hold
645    /// it or holds it beyond what a position can count.
646    ///
647    /// Addresses a sweep finds without being asked have no position.
648    pub fn find(&self, ip: IpAddr) -> Option<u64> {
649        let span = self.span_holding(ip)?;
650        let offset = offset_within(&span.range, ip)?;
651        Some(span.start + offset)
652    }
653
654    /// The address at `position`, or `None` past the end of the numbering.
655    pub fn address_at(&self, position: u64) -> Option<IpAddr> {
656        let index = self.span_at(position)?;
657        let span = &self.spans[index];
658        address_within(&span.range, position - span.start)
659    }
660
661    /// The addresses at every position in `wanted`, as ranges.
662    ///
663    /// For narrowing a plan to what a resumed sweep still has to ask, as a handful of
664    /// ranges.
665    pub fn ranges_in(&self, wanted: Range<u64>) -> Vec<IpRange> {
666        let end = wanted.end.min(self.total);
667        if wanted.start >= end {
668            return Vec::new();
669        }
670
671        let mut found = Vec::new();
672        let mut index = match self.span_at(wanted.start) {
673            Some(index) => index,
674            None => return found,
675        };
676
677        while index < self.spans.len() {
678            let span = &self.spans[index];
679            if span.start >= end {
680                break;
681            }
682
683            let from = wanted.start.saturating_sub(span.start);
684            let to = (end - span.start).min(span.len) - 1;
685            if let Some(part) = slice_of(&span.range, from, to) {
686                found.push(part);
687            }
688            index += 1;
689        }
690
691        found
692    }
693
694    /// The span holding `ip`, or `None` where no run holds it or more than one
695    /// does.
696    ///
697    /// An `IpAddr` carries no interface, so an address two segments hold cannot say
698    /// which position it means. `None` means it is asked again, which is safe; picking
699    /// one could skip an address nothing probed.
700    fn span_holding(&self, ip: IpAddr) -> Option<&Span> {
701        let v6 = ip.is_ipv6();
702        let key = widen(ip);
703        let mut found: Option<&Span> = None;
704
705        for run in self.runs.iter().filter(|run| run.v6 == v6) {
706            let spans = &self.spans[run.from..run.to];
707            let Ok(index) = spans.binary_search_by(|span| {
708                let (start, end) = bounds(&span.range);
709                if end < key {
710                    Ordering::Less
711                } else if start > key {
712                    Ordering::Greater
713                } else {
714                    Ordering::Equal
715                }
716            }) else {
717                continue;
718            };
719
720            if found.is_some() {
721                return None;
722            }
723            found = Some(&spans[index]);
724        }
725
726        found
727    }
728
729    /// The index of the span holding `position`.
730    fn span_at(&self, position: u64) -> Option<usize> {
731        if position >= self.total {
732            return None;
733        }
734
735        self.spans
736            .binary_search_by(|span| {
737                if span.start + span.len <= position {
738                    Ordering::Less
739                } else if span.start > position {
740                    Ordering::Greater
741                } else {
742                    Ordering::Equal
743                }
744            })
745            .ok()
746    }
747}
748
749impl IpSet {
750    /// Numbers this set's addresses, for counting how far a sweep of it got.
751    ///
752    /// See [`Positions`].
753    pub fn positions(&self) -> Positions {
754        Positions::of(self)
755    }
756}
757
758/// One address as a `u128`, so the two families compare the same way.
759fn widen(ip: IpAddr) -> u128 {
760    match ip {
761        IpAddr::V4(v4) => u128::from(u32::from(v4)),
762        IpAddr::V6(v6) => u128::from(v6),
763    }
764}
765
766/// A range's inclusive bounds, widened.
767fn bounds(range: &IpRange) -> (u128, u128) {
768    match range {
769        IpRange::V4(v4) => v4_bounds(v4),
770        IpRange::V6(v6) => (u128::from(v6.start_addr()), u128::from(v6.end_addr())),
771    }
772}
773
774/// How far into `range` the address `ip` sits, or `None` if it is not in it or
775/// belongs to the other family.
776fn offset_within(range: &IpRange, ip: IpAddr) -> Option<u64> {
777    let same_family = matches!(
778        (range, ip),
779        (IpRange::V4(_), IpAddr::V4(_)) | (IpRange::V6(_), IpAddr::V6(_))
780    );
781    if !same_family {
782        return None;
783    }
784
785    let (start, end) = bounds(range);
786    let key = widen(ip);
787    if key < start || key > end {
788        return None;
789    }
790    u64::try_from(key - start).ok()
791}
792
793/// The address `offset` addresses into `range`.
794fn address_within(range: &IpRange, offset: u64) -> Option<IpAddr> {
795    let (start, end) = bounds(range);
796    let at = start.checked_add(u128::from(offset))?;
797    if at > end {
798        return None;
799    }
800
801    Some(match range {
802        IpRange::V4(_) => IpAddr::V4(Ipv4Addr::from(u32::try_from(at).ok()?)),
803        IpRange::V6(_) => IpAddr::V6(Ipv6Addr::from(at)),
804    })
805}
806
807/// The part of `range` from its `from`th address to its `to`th, inclusive.
808fn slice_of(range: &IpRange, from: u64, to: u64) -> Option<IpRange> {
809    let start = address_within(range, from)?;
810    let end = address_within(range, to)?;
811
812    match (range, start, end) {
813        (IpRange::V4(_), IpAddr::V4(start), IpAddr::V4(end)) => {
814            Ipv4Range::new(start, end).ok().map(IpRange::V4)
815        }
816        // A slice of a zoned range keeps its zone.
817        (IpRange::V6(v6), IpAddr::V6(start), IpAddr::V6(end)) => {
818            Ipv6Range::scoped(start, end, v6.zone())
819                .ok()
820                .map(IpRange::V6)
821        }
822        _ => None,
823    }
824}
825
826/// The inclusive bounds of an IPv4 range, widened so one difference serves both
827/// families, as in [`holds`].
828fn v4_bounds(range: &Ipv4Range) -> (u128, u128) {
829    (
830        u128::from(u32::from(range.start_addr())),
831        u128::from(u32::from(range.end_addr())),
832    )
833}
834
835/// The IPv6 half of [`v4_bounds`]. Drops the zone, which is what makes
836/// [`IpSet::subtract`] blind to it.
837fn v6_bounds(range: &Ipv6Range) -> (u128, u128) {
838    (u128::from(range.start_addr()), u128::from(range.end_addr()))
839}
840
841/// Sorts and coalesces `intervals` into ascending, non-overlapping, non-adjacent
842/// inclusive pairs.
843///
844/// The subtrahend, flattened. IPv6 ranges may overlap across zones, and
845/// [`IpSet::subtract`] ignores zones, so they are coalesced first.
846fn merged_intervals(intervals: impl Iterator<Item = (u128, u128)>) -> Vec<(u128, u128)> {
847    let mut cuts: Vec<(u128, u128)> = intervals.collect();
848    cuts.sort_unstable();
849
850    let mut merged: Vec<(u128, u128)> = Vec::with_capacity(cuts.len());
851    for (start, end) in cuts {
852        match merged.last_mut() {
853            // Adjacent cuts coalesce too.
854            Some(last) if start <= last.1.saturating_add(1) => last.1 = last.1.max(end),
855            _ => merged.push((start, end)),
856        }
857    }
858    merged
859}
860
861/// Every part of `run` that no interval in `cuts` covers, in ascending order.
862///
863/// Both slices must be sorted by start and disjoint, so each is walked once. `run` is
864/// one family's merged ranges (for IPv6, one zone's run); `cuts` comes from
865/// [`merged_intervals`].
866///
867/// `bounds` reads a range's inclusive ends widened to `u128`, as in [`holds`].
868/// `rebuild` turns a surviving `[start, end]` back into a range, given the range being
869/// cut so a piece keeps its zone.
870fn subtract_run<R: Copy>(
871    run: &[R],
872    cuts: &[(u128, u128)],
873    bounds: impl Fn(&R) -> (u128, u128),
874    rebuild: impl Fn(&R, u128, u128) -> R,
875) -> Vec<R> {
876    let mut kept = Vec::with_capacity(run.len());
877    let mut first_live = 0usize;
878
879    for range in run {
880        let (start, end) = bounds(range);
881
882        // A cut left of this range is left of every later one, so this index only
883        // moves forward and the pass is linear.
884        while first_live < cuts.len() && cuts[first_live].1 < start {
885            first_live += 1;
886        }
887
888        let mut cursor = start;
889        let mut consumed = false;
890
891        // `first_live` stays: one cut may span several ranges.
892        let mut cut = first_live;
893        while cut < cuts.len() && cuts[cut].0 <= end {
894            let (cut_start, cut_end) = cuts[cut];
895
896            // The gap in front of this cut survives, if there is one.
897            if cut_start > cursor {
898                kept.push(rebuild(range, cursor, cut_start - 1));
899            }
900
901            // A cut reaching the range's end takes the tail, and stays for the next
902            // range.
903            if cut_end >= end {
904                consumed = true;
905                break;
906            }
907
908            // `cut_end < end <= u128::MAX`, so this cannot overflow.
909            cursor = cut_end + 1;
910            cut += 1;
911        }
912
913        if !consumed {
914            kept.push(rebuild(range, cursor, end));
915        }
916    }
917
918    kept
919}
920
921/// Whether any range in `ranges` holds `target`, by binary search.
922///
923/// `bounds` reads a range's inclusive ends, widened to `u128` so that one
924/// search serves both families.
925///
926/// `ranges` must be sorted by start and disjoint, or the search can step past the
927/// range holding the target. The IPv4 vector is disjoint once merged; the IPv6 vector
928/// only within one zone's run (see [`IpSet::v6_runs`]).
929fn holds<R>(ranges: &[R], target: u128, bounds: impl Fn(&R) -> (u128, u128)) -> bool {
930    ranges
931        .binary_search_by(|range| {
932            let (start, end) = bounds(range);
933            if target < start {
934                std::cmp::Ordering::Greater
935            } else if target > end {
936                std::cmp::Ordering::Less
937            } else {
938                std::cmp::Ordering::Equal
939            }
940        })
941        .is_ok()
942}
943
944// ══════════════════════════════════════════════════════════════════════════════
945// Conversion Traits
946// ══════════════════════════════════════════════════════════════════════════════
947
948impl IntoIterator for IpSet {
949    type Item = IpAddr;
950    type IntoIter = Box<dyn Iterator<Item = IpAddr> + Send>;
951
952    /// Consumes the `IpSet` and returns an iterator over its individual IP addresses.
953    fn into_iter(mut self) -> Self::IntoIter {
954        self.canonicalize();
955        let v4_iter = self.v4.into_iter().flat_map(|range| {
956            let start: u32 = range.start_addr().into();
957            let end: u32 = range.end_addr().into();
958            (start..=end).map(|ip| IpAddr::V4(Ipv4Addr::from(ip)))
959        });
960
961        let v6_iter = self.v6.into_iter().flat_map(|range| {
962            let start: u128 = range.start_addr().into();
963            let end: u128 = range.end_addr().into();
964            (start..=end).map(|ip| IpAddr::V6(Ipv6Addr::from(ip)))
965        });
966
967        Box::new(v4_iter.chain(v6_iter))
968    }
969}
970
971impl Extend<IpAddr> for IpSet {
972    /// Marks only the families that actually gained a range.
973    ///
974    /// Extending with IPv4 alone keeps IPv6 on its fast path, and extending with
975    /// nothing keeps a completed `canonicalize`.
976    fn extend<T: IntoIterator<Item = IpAddr>>(&mut self, iter: T) {
977        for ip in iter {
978            match ip {
979                IpAddr::V4(v4) => self.push_v4_range(Ipv4Range::single(v4)),
980                IpAddr::V6(v6) => self.push_v6_range(Ipv6Range::single(v6)),
981            }
982        }
983    }
984}
985
986impl FromIterator<IpAddr> for IpSet {
987    fn from_iter<I: IntoIterator<Item = IpAddr>>(iter: I) -> Self {
988        let mut set = IpSet::new();
989        set.extend(iter);
990        set.canonicalize();
991        set
992    }
993}
994
995impl FromIterator<IpRange> for IpSet {
996    fn from_iter<I: IntoIterator<Item = IpRange>>(iter: I) -> Self {
997        let mut set = IpSet::new();
998        for range in iter {
999            set.insert_range(range);
1000        }
1001        set.canonicalize();
1002        set
1003    }
1004}
1005
1006impl FromIterator<IpSet> for IpSet {
1007    fn from_iter<I: IntoIterator<Item = IpSet>>(iter: I) -> Self {
1008        let mut master = IpSet::new();
1009        for set in iter {
1010            if !set.v4.is_empty() {
1011                master.v4.extend(set.v4);
1012                master.v4_dirty = true;
1013            }
1014            if !set.v6.is_empty() {
1015                master.v6.extend(set.v6);
1016                master.v6_dirty = true;
1017            }
1018        }
1019        master.canonicalize();
1020        master
1021    }
1022}
1023
1024impl From<IpAddr> for IpSet {
1025    fn from(ip: IpAddr) -> Self {
1026        let mut set = Self::new();
1027        set.insert(ip);
1028        set
1029    }
1030}
1031
1032impl From<IpRange> for IpSet {
1033    fn from(range: IpRange) -> Self {
1034        let mut set = Self::new();
1035        set.insert_range(range);
1036        set
1037    }
1038}
1039
1040impl TryFrom<&str> for IpSet {
1041    type Error = IpSetError;
1042    fn try_from(value: &str) -> Result<Self, Self::Error> {
1043        let mut set = IpSet::new();
1044        for part in value
1045            .split([',', ' '])
1046            .filter(|part| !part.trim().is_empty())
1047        {
1048            let range = part.parse::<IpRange>()?;
1049            set.insert_range(range);
1050        }
1051        set.canonicalize();
1052        Ok(set)
1053    }
1054}
1055
1056impl FromStr for IpSet {
1057    type Err = IpSetError;
1058    fn from_str(s: &str) -> Result<Self, Self::Err> {
1059        Self::try_from(s)
1060    }
1061}
1062
1063// ╔════════════════════════════════════════════╗
1064// ║ ████████╗███████╗███████╗████████╗███████╗ ║
1065// ║ ╚══██╔══╝██╔════╝██╔════╝╚══██╔══╝██╔════╝ ║
1066// ║    ██║   █████╗  ███████╗   ██║   ███████╗ ║
1067// ║    ██║   ██╔══╝  ╚════██║   ██║   ╚════██║ ║
1068// ║    ██║   ███████╗███████║   ██║   ███████║ ║
1069// ║    ╚═╝   ╚══════╝╚══════╝   ╚═╝   ╚══════╝ ║
1070// ╚════════════════════════════════════════════╝
1071
1072#[cfg(test)]
1073mod tests {
1074    use super::*;
1075
1076    /// Two adjacent addresses stay two ranges until canonicalized, and the count is
1077    /// right either way.
1078    #[test]
1079    fn adjacent_addresses_merge_when_the_set_is_canonicalized() {
1080        let mut set = IpSet::new();
1081        set.insert(IpAddr::V4(Ipv4Addr::new(1, 1, 1, 1)));
1082        set.insert(IpAddr::V4(Ipv4Addr::new(1, 1, 1, 2)));
1083
1084        // Before canonicalization they stay separate.
1085        assert_eq!(set.v4.len(), 2);
1086        assert!(set.v4_dirty);
1087
1088        // A query never merges the set it reads.
1089        set.canonicalize();
1090        assert_eq!(set.len(), 2);
1091        assert!(!set.v4_dirty);
1092        assert_eq!(set.v4.len(), 1);
1093    }
1094
1095    /// Every arrangement of two ranges collapses to the single covering range.
1096    #[test]
1097    fn every_kind_of_overlap_collapses_to_one_range() {
1098        let mut set = IpSet::new();
1099        // Insert: [10-20]
1100        set.insert_range("198.51.100.10-198.51.100.20".parse().unwrap());
1101        // Insert: [5-15] (overlap start)
1102        set.insert_range("198.51.100.5-198.51.100.15".parse().unwrap());
1103        // Insert: [15-25] (overlap end)
1104        set.insert_range("198.51.100.15-198.51.100.25".parse().unwrap());
1105        // Insert: [30-40] (disjoint)
1106        set.insert_range("198.51.100.30-198.51.100.40".parse().unwrap());
1107        // Insert: [0-50] (subsume all)
1108        set.insert_range("198.51.100.0-198.51.100.50".parse().unwrap());
1109
1110        set.canonicalize();
1111        assert_eq!(set.len(), 51);
1112        assert_eq!(set.v4().len(), 1);
1113    }
1114
1115    /// Adjacency uses a saturating add, so addresses at the top of IPv6 still merge.
1116    #[test]
1117    fn the_top_of_the_ipv6_space_merges_without_overflowing() {
1118        let mut set = IpSet::new();
1119        // ::f...f (max)
1120        let max_v6 = Ipv6Addr::from(u128::MAX);
1121        let max_minus_1 = Ipv6Addr::from(u128::MAX - 1);
1122
1123        set.insert(IpAddr::V6(max_minus_1));
1124        set.insert(IpAddr::V6(max_v6));
1125
1126        set.canonicalize();
1127        assert_eq!(set.len(), 2);
1128        assert_eq!(set.v6().len(), 1);
1129    }
1130
1131    /// Iterating yields every address once and leaves the set unchanged.
1132    #[test]
1133    fn iterating_yields_each_address_without_mutating_the_set() {
1134        let mut set = IpSet::new();
1135        set.insert(IpAddr::V4(Ipv4Addr::from(1)));
1136        set.insert(IpAddr::V4(Ipv4Addr::from(2)));
1137
1138        set.canonicalize();
1139        let ips: Vec<IpAddr> = set.iter().collect();
1140        assert_eq!(ips.len(), 2);
1141        assert!(!set.v4_dirty);
1142    }
1143
1144    /// Canonicalizing an empty set is a no-op.
1145    #[test]
1146    fn an_empty_set_canonicalizes_and_counts_as_zero() {
1147        let mut set = IpSet::new();
1148        set.canonicalize();
1149        assert_eq!(set.len_canonical(), 0);
1150        assert!(set.v4().is_empty());
1151    }
1152
1153    /// Work on one family keeps the other's canonical state, and a read of the
1154    /// untouched family still takes its fast path.
1155    #[test]
1156    fn extending_one_family_leaves_the_other_canonical() {
1157        let mut set = IpSet::from_iter(vec![IpAddr::V6(Ipv6Addr::LOCALHOST)]);
1158        assert!(!set.v4_dirty && !set.v6_dirty, "from_iter canonicalizes");
1159
1160        set.extend([IpAddr::V4(Ipv4Addr::LOCALHOST)]);
1161
1162        assert!(set.v4_dirty, "the family that gained a range");
1163        assert!(!set.v6_dirty, "and only that one");
1164
1165        // Extending with nothing keeps a completed merge.
1166        let mut untouched = IpSet::from_iter(vec![IpAddr::V4(Ipv4Addr::LOCALHOST)]);
1167        untouched.extend([]);
1168        assert!(!untouched.v4_dirty && !untouched.v6_dirty);
1169
1170        // The other family keeps its binary search.
1171        let v6 = IpAddr::V6(Ipv6Addr::LOCALHOST);
1172        let v4 = IpAddr::V4(Ipv4Addr::LOCALHOST);
1173        assert!(set.is_merged(&v6), "an unmerged IPv4 range is not IPv6's");
1174        assert!(!set.is_merged(&v4), "and IPv4's own half is not merged");
1175
1176        // The guarded fast path accepts it.
1177        assert!(set.contains_canonical(&v6));
1178        assert!(set.contains(&v6));
1179        assert!(set.contains(&v4), "the slow path is still correct");
1180    }
1181
1182    /// One string naming both families, with a duplicate across two spellings
1183    /// that has to be counted once.
1184    #[test]
1185    fn a_written_set_may_mix_both_families_and_still_counts_distinctly() {
1186        let set =
1187            IpSet::from_str("1.1.1.1/32, 1.1.1.1, ::1-::1, 198.51.100.1-198.51.100.2").unwrap();
1188        // 1.1.1.1 (v4) + ::1 (v6) + 198.51.100.1, 198.51.100.2 (v4)
1189        assert_eq!(set.len(), 4);
1190    }
1191
1192    /// A hundred inserted addresses are a hundred ranges until `canonicalize` runs.
1193    #[test]
1194    fn insertion_defers_the_merge_until_it_is_asked_for() {
1195        let mut set = IpSet::new();
1196        let ips = (0..100).map(|i| IpAddr::V4(Ipv4Addr::from(i)));
1197        set.extend(ips);
1198
1199        assert_eq!(set.v4.len(), 100);
1200        set.canonicalize();
1201        assert_eq!(set.v4.len(), 1);
1202        assert_eq!(set.len(), 100);
1203    }
1204
1205    /// The debug assertion trips when `contains_canonical` is handed an unmerged set.
1206    /// Debug-only, as the assertion is.
1207    #[test]
1208    #[cfg(debug_assertions)]
1209    #[should_panic(expected = "must be canonicalized")]
1210    fn a_membership_query_on_an_unmerged_set_trips_the_guard() {
1211        let mut set = IpSet::new();
1212        set.insert(IpAddr::V4(Ipv4Addr::LOCALHOST));
1213        // Deliberately not canonicalized.
1214        set.contains_canonical(&IpAddr::V4(Ipv4Addr::LOCALHOST));
1215    }
1216
1217    /// The same for the count.
1218    #[test]
1219    #[cfg(debug_assertions)]
1220    #[should_panic(expected = "must be canonicalized")]
1221    fn a_count_on_an_unmerged_set_trips_the_guard() {
1222        let mut set = IpSet::new();
1223        set.insert(IpAddr::V4(Ipv4Addr::LOCALHOST));
1224        set.len_canonical();
1225    }
1226
1227    /// A merged set passes the guards.
1228    #[test]
1229    fn a_membership_query_on_a_merged_set_answers() {
1230        let set = IpSet::from_iter(vec![IpAddr::V4(Ipv4Addr::LOCALHOST)]);
1231        assert!(!set.v4_dirty, "from_iter canonicalizes");
1232        assert!(set.contains_canonical(&IpAddr::V4(Ipv4Addr::LOCALHOST)));
1233        assert_eq!(set.len_canonical(), 1);
1234    }
1235
1236    /// The same link-local numbers on two interfaces do not merge.
1237    #[test]
1238    fn ranges_on_different_interfaces_never_merge_however_adjacent() {
1239        let one: Ipv6Addr = "fe80::1".parse().unwrap();
1240        let five: Ipv6Addr = "fe80::5".parse().unwrap();
1241        let six: Ipv6Addr = "fe80::6".parse().unwrap();
1242        let ten: Ipv6Addr = "fe80::a".parse().unwrap();
1243
1244        let mut split = IpSet::new();
1245        split.push_v6_range(Ipv6Range::scoped(one, five, Some(4)).unwrap());
1246        split.push_v6_range(Ipv6Range::scoped(six, ten, Some(9)).unwrap());
1247        split.canonicalize();
1248
1249        assert_eq!(split.v6().len(), 2, "adjacent, but on two segments");
1250
1251        // On one interface they do merge.
1252        let mut joined = IpSet::new();
1253        joined.push_v6_range(Ipv6Range::scoped(one, five, Some(4)).unwrap());
1254        joined.push_v6_range(Ipv6Range::scoped(six, ten, Some(4)).unwrap());
1255        joined.canonicalize();
1256
1257        assert_eq!(joined.v6().len(), 1);
1258
1259        // Membership still answers.
1260        assert!(split.contains(&IpAddr::V6(five)));
1261        assert!(split.contains(&IpAddr::V6(six)));
1262    }
1263
1264    /// Equality compares the addresses held, merged or not.
1265    #[test]
1266    fn two_sets_holding_the_same_addresses_are_equal_however_they_were_built() {
1267        let canonical = IpSet::try_from("198.51.100.1-198.51.100.2, ::1").expect("parses");
1268
1269        let mut piecemeal = IpSet::new();
1270        piecemeal.insert(IpAddr::V6(Ipv6Addr::LOCALHOST));
1271        piecemeal.insert(IpAddr::V4(Ipv4Addr::new(198, 51, 100, 2)));
1272        piecemeal.insert(IpAddr::V4(Ipv4Addr::new(198, 51, 100, 1)));
1273
1274        assert_eq!(canonical, piecemeal, "same addresses, different order");
1275        assert_ne!(
1276            canonical,
1277            IpSet::try_from("198.51.100.1, ::1").expect("parses")
1278        );
1279    }
1280
1281    /// Ranges on different interfaces can overlap, which a single binary search cannot
1282    /// navigate; the search runs per zone.
1283    #[test]
1284    fn membership_answers_when_ranges_on_different_interfaces_overlap() {
1285        let one: Ipv6Addr = "fe80::1".parse().unwrap();
1286        let two: Ipv6Addr = "fe80::2".parse().unwrap();
1287        let three: Ipv6Addr = "fe80::3".parse().unwrap();
1288        let ten: Ipv6Addr = "fe80::a".parse().unwrap();
1289
1290        let mut set = IpSet::new();
1291        set.push_v6_range(Ipv6Range::scoped(one, ten, Some(4)).unwrap());
1292        set.push_v6_range(Ipv6Range::scoped(two, three, Some(9)).unwrap());
1293        set.canonicalize();
1294
1295        for address in [one, two, three, ten] {
1296            assert!(
1297                set.contains(&IpAddr::V6(address)),
1298                "{address} is covered by the range on interface 4"
1299            );
1300        }
1301        assert!(!set.contains(&IpAddr::V6("fe80::b".parse().unwrap())));
1302    }
1303    // ─── Positions ───────────────────────────────────────────────────────────
1304
1305    fn set(written: &str) -> IpSet {
1306        written.parse().expect("a valid address specification")
1307    }
1308
1309    /// A position is an index into `iter`, and the two agree address for address.
1310    #[test]
1311    fn a_position_is_the_index_the_set_enumerates_at() {
1312        let set = set("192.0.2.1-192.0.2.10,198.51.100.0/30,2001:db8::1-2001:db8::5");
1313        let positions = set.positions();
1314
1315        // `try_from`, since `as` would truncate to match a truncated numbering.
1316        assert_eq!(positions.total(), u64::try_from(set.len()).unwrap());
1317        assert!(positions.unnumbered().is_empty());
1318
1319        for (index, ip) in set.iter().enumerate() {
1320            let index = index as u64;
1321            assert_eq!(positions.find(ip), Some(index), "{ip} is not at {index}");
1322            assert_eq!(positions.address_at(index), Some(ip), "{index} is not {ip}");
1323        }
1324    }
1325
1326    /// A `/64`, the ordinary IPv6 subnet, is the first prefix the numbering cannot
1327    /// reach.
1328    #[test]
1329    fn a_range_too_large_to_number_is_kept_rather_than_dropped() {
1330        let positions = set("2001:db8::/64").positions();
1331
1332        assert_eq!(positions.total(), 0);
1333        assert_eq!(positions.unnumbered().len(), 1);
1334    }
1335
1336    /// An address outside the set has no position.
1337    #[test]
1338    fn an_address_outside_the_plan_has_no_position() {
1339        let positions = set("192.0.2.1-192.0.2.10").positions();
1340
1341        assert_eq!(
1342            positions.find("192.0.2.11".parse().expect("an address")),
1343            None
1344        );
1345        assert_eq!(
1346            positions.find("198.51.100.1".parse().expect("an address")),
1347            None
1348        );
1349        assert_eq!(
1350            positions.find("2001:db8::1".parse().expect("an address")),
1351            None,
1352            "the other family is not in the set either"
1353        );
1354        assert_eq!(positions.address_at(10), None, "past the end of the plan");
1355    }
1356
1357    /// IPv4 is numbered before IPv6, which is what the enumeration does.
1358    #[test]
1359    fn the_families_are_numbered_in_the_order_they_are_walked() {
1360        let set = set("2001:db8::1,192.0.2.1");
1361        let positions = set.positions();
1362
1363        assert_eq!(
1364            positions.find("192.0.2.1".parse().expect("an address")),
1365            Some(0)
1366        );
1367        assert_eq!(
1368            positions.find("2001:db8::1".parse().expect("an address")),
1369            Some(1)
1370        );
1371    }
1372
1373    /// Narrowing a plan gives back exactly the addresses at those positions.
1374    #[test]
1375    fn the_addresses_in_a_span_of_positions_are_exactly_those_positions() {
1376        let set = set("192.0.2.1-192.0.2.10,2001:db8::1-2001:db8::4");
1377        let positions = set.positions();
1378
1379        for (from, to) in [(0u64, 14u64), (0, 5), (3, 9), (9, 12), (13, 14), (7, 8)] {
1380            let mut narrowed = IpSet::new();
1381            for range in positions.ranges_in(from..to) {
1382                narrowed.insert_range(range);
1383            }
1384            narrowed.canonicalize();
1385
1386            let expected: Vec<IpAddr> = set
1387                .iter()
1388                .skip(from as usize)
1389                .take((to - from) as usize)
1390                .collect();
1391            let found: Vec<IpAddr> = narrowed.iter().collect();
1392
1393            assert_eq!(found, expected, "positions {from}..{to}");
1394        }
1395    }
1396
1397    /// A span past the end is clamped, and an empty one gives back nothing.
1398    #[test]
1399    fn a_span_outside_the_plan_yields_nothing() {
1400        let positions = set("192.0.2.1-192.0.2.4").positions();
1401
1402        assert!(positions.ranges_in(4..99).is_empty());
1403        assert!(positions.ranges_in(2..2).is_empty());
1404        assert_eq!(positions.ranges_in(0..99).len(), 1, "clamped to the plan");
1405    }
1406
1407    /// The numbering stops at an IPv6 range too large to count, and IPv4 keeps its
1408    /// positions.
1409    #[test]
1410    fn a_range_too_large_to_number_ends_the_numbering_without_losing_ipv4() {
1411        let set = set("192.0.2.1-192.0.2.4,2001:db8::/64,2001:db9::1");
1412        let positions = set.positions();
1413
1414        assert_eq!(positions.total(), 4, "only the IPv4 half is numbered");
1415        assert_eq!(
1416            positions.find("192.0.2.4".parse().expect("an address")),
1417            Some(3)
1418        );
1419        assert_eq!(
1420            positions.find("2001:db8::1".parse().expect("an address")),
1421            None,
1422            "an unnumbered address never settles, so it is asked again"
1423        );
1424        assert_eq!(
1425            positions.find("2001:db9::1".parse().expect("an address")),
1426            None,
1427            "and so is everything after it: positions have to stay contiguous"
1428        );
1429        assert_eq!(
1430            positions.unnumbered().len(),
1431            2,
1432            "both are kept, or a resumed sweep would never ask about them"
1433        );
1434    }
1435
1436    /// A slice of a zoned range keeps its zone.
1437    #[test]
1438    fn a_slice_of_a_zoned_range_keeps_its_zone() {
1439        let mut set = IpSet::new();
1440        set.insert_range(IpRange::V6(
1441            Ipv6Range::scoped(
1442                "fe80::1".parse().expect("an address"),
1443                "fe80::8".parse().expect("an address"),
1444                Some(7),
1445            )
1446            .expect("a range"),
1447        ));
1448        set.canonicalize();
1449
1450        let sliced = set.positions().ranges_in(2..5);
1451        assert_eq!(sliced.len(), 1);
1452        match sliced[0] {
1453            IpRange::V6(range) => assert_eq!(range.zone(), Some(7)),
1454            IpRange::V4(_) => panic!("an IPv6 range came back as IPv4"),
1455        }
1456    }
1457
1458    /// An address two interfaces hold has no position, since a bare address cannot
1459    /// say which it means.
1460    #[test]
1461    fn an_address_two_interfaces_both_hold_has_no_position() {
1462        let mut both = IpSet::new();
1463        for zone in [5u32, 7] {
1464            both.insert_range(IpRange::V6(
1465                Ipv6Range::scoped(
1466                    "fe80::1".parse().expect("an address"),
1467                    "fe80::4".parse().expect("an address"),
1468                    Some(zone),
1469                )
1470                .expect("a range"),
1471            ));
1472        }
1473        both.canonicalize();
1474
1475        let positions = both.positions();
1476        assert_eq!(
1477            positions.total(),
1478            8,
1479            "four addresses on each of two segments"
1480        );
1481        assert_eq!(
1482            positions.find("fe80::1".parse().expect("an address")),
1483            None,
1484            "two segments hold it and the address cannot say which"
1485        );
1486    }
1487
1488    /// An address one interface holds still resolves.
1489    #[test]
1490    fn an_address_one_interface_holds_keeps_its_position() {
1491        let mut set = IpSet::new();
1492        set.insert_range(IpRange::V6(
1493            Ipv6Range::scoped(
1494                "fe80::1".parse().expect("an address"),
1495                "fe80::4".parse().expect("an address"),
1496                Some(7),
1497            )
1498            .expect("a range"),
1499        ));
1500        set.insert_range(IpRange::V6(
1501            Ipv6Range::scoped(
1502                "fe80::9".parse().expect("an address"),
1503                "fe80::a".parse().expect("an address"),
1504                Some(5),
1505            )
1506            .expect("a range"),
1507        ));
1508        set.canonicalize();
1509
1510        let positions = set.positions();
1511        for (index, ip) in set.iter().enumerate() {
1512            assert_eq!(
1513                positions.find(ip),
1514                Some(index as u64),
1515                "{ip} is at {index} and no run but its own holds it"
1516            );
1517        }
1518    }
1519
1520    /// Numbering an unmerged set merges it first.
1521    #[test]
1522    fn an_unmerged_set_is_numbered_as_the_canonical_one() {
1523        let mut lazy = IpSet::new();
1524        lazy.insert("192.0.2.2".parse().expect("an address"));
1525        lazy.insert("192.0.2.1".parse().expect("an address"));
1526        lazy.insert("192.0.2.2".parse().expect("an address"));
1527
1528        let positions = lazy.positions();
1529        assert_eq!(positions.total(), 2, "the duplicate is one address");
1530        assert_eq!(
1531            positions.find("192.0.2.1".parse().expect("an address")),
1532            Some(0)
1533        );
1534        assert_eq!(
1535            positions.find("192.0.2.2".parse().expect("an address")),
1536            Some(1)
1537        );
1538    }
1539}
1540
1541#[cfg(test)]
1542mod property_tests {
1543    use super::*;
1544    use proptest::prelude::*;
1545
1546    fn any_ipv4() -> impl Strategy<Value = Ipv4Addr> {
1547        any::<u32>().prop_map(Ipv4Addr::from)
1548    }
1549
1550    fn any_ipv6() -> impl Strategy<Value = Ipv6Addr> {
1551        any::<u128>().prop_map(Ipv6Addr::from)
1552    }
1553
1554    /// Zoned ranges from a narrow band of `fe80::/64`, so they often overlap, across
1555    /// four zones.
1556    fn any_zoned_v6_range() -> impl Strategy<Value = Ipv6Range> {
1557        (0..64u128, 0..64u128, prop::option::of(0..4u32)).prop_map(|(a, b, zone)| {
1558            let base = u128::from(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0));
1559            let (low, high) = if a <= b { (a, b) } else { (b, a) };
1560            Ipv6Range::scoped(
1561                Ipv6Addr::from(base + low),
1562                Ipv6Addr::from(base + high),
1563                zone,
1564            )
1565            .expect("low <= high")
1566        })
1567    }
1568
1569    // ─── Set difference ──────────────────────────────────────────────────────
1570
1571    /// A small canonical set of both families, with several ranges in each and some
1572    /// IPv6 addresses on more than one interface.
1573    fn any_ipset() -> impl Strategy<Value = IpSet> {
1574        (
1575            prop::collection::vec((0u8..40, 0u8..6), 0..4),
1576            prop::collection::vec((0u16..40, 0u16..6, prop::option::of(1u32..3)), 0..4),
1577        )
1578            .prop_map(|(v4, v6)| {
1579                let mut set = IpSet::new();
1580                for (start, span) in v4 {
1581                    let first = Ipv4Addr::new(192, 0, 2, start);
1582                    let last = Ipv4Addr::new(192, 0, 2, start.saturating_add(span));
1583                    set.insert_range(IpRange::V4(
1584                        Ipv4Range::new(first, last).expect("ordered by construction"),
1585                    ));
1586                }
1587                for (start, span, zone) in v6 {
1588                    let first = Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, start);
1589                    let last =
1590                        Ipv6Addr::new(0x2001, 0xdb8, 0, 0, 0, 0, 0, start.saturating_add(span));
1591                    set.insert_range(IpRange::V6(
1592                        Ipv6Range::scoped(first, last, zone).expect("ordered by construction"),
1593                    ));
1594                }
1595                set.canonicalize();
1596                set
1597            })
1598    }
1599
1600    /// Builds a v4 set from `[start, end]` pairs written as last octets of
1601    /// `198.51.100.0/24`.
1602    fn v4_set(spans: &[(u8, u8)]) -> IpSet {
1603        let mut set = IpSet::new();
1604        for &(start, end) in spans {
1605            set.push_v4_range(
1606                Ipv4Range::new(
1607                    Ipv4Addr::new(198, 51, 100, start),
1608                    Ipv4Addr::new(198, 51, 100, end),
1609                )
1610                .expect("start <= end"),
1611            );
1612        }
1613        set.canonicalize();
1614        set
1615    }
1616
1617    /// The same shorthand, read back out.
1618    fn v4_spans(set: &IpSet) -> Vec<(u8, u8)> {
1619        set.v4()
1620            .iter()
1621            .map(|r| (r.start_addr().octets()[3], r.end_addr().octets()[3]))
1622            .collect()
1623    }
1624
1625    /// Every way one cut can meet one range: through the middle, off each end,
1626    /// swallowing it whole, and missing entirely.
1627    ///
1628    /// One arrangement per case; the middle cut is the one that produces more ranges.
1629    #[test]
1630    fn a_cut_takes_exactly_what_it_covers() {
1631        /// A target, what is cut from it, and what should be left, as last octets of
1632        /// `198.51.100.0/24`.
1633        type Case = (
1634            &'static [(u8, u8)],
1635            &'static [(u8, u8)],
1636            &'static [(u8, u8)],
1637        );
1638
1639        let cases: [Case; 6] = [
1640            // Through the middle: one range becomes two.
1641            (&[(10, 20)], &[(14, 16)], &[(10, 13), (17, 20)]),
1642            // Off the front, off the back.
1643            (&[(10, 20)], &[(5, 12)], &[(13, 20)]),
1644            (&[(10, 20)], &[(18, 25)], &[(10, 17)]),
1645            // Swallowed whole, and exactly.
1646            (&[(10, 20)], &[(5, 25)], &[]),
1647            (&[(10, 20)], &[(10, 20)], &[]),
1648            // Adjacent but not overlapping: nothing removed.
1649            (&[(10, 20)], &[(21, 30)], &[(10, 20)]),
1650        ];
1651
1652        for (target, cut, expected) in cases {
1653            let mut set = v4_set(target);
1654            set.subtract(&v4_set(cut));
1655            assert_eq!(v4_spans(&set), expected, "{target:?} minus {cut:?}");
1656        }
1657    }
1658
1659    /// One cut spanning several ranges, and several cuts inside one range.
1660    ///
1661    /// The first needs a cut to stay for the next range; the second moves the cursor
1662    /// repeatedly inside one range.
1663    #[test]
1664    fn the_difference_walks_both_sides_once() {
1665        let mut set = v4_set(&[(10, 20), (30, 40), (50, 60)]);
1666        set.subtract(&v4_set(&[(15, 55)]));
1667        assert_eq!(v4_spans(&set), vec![(10, 14), (56, 60)]);
1668
1669        let mut set = v4_set(&[(10, 40)]);
1670        set.subtract(&v4_set(&[(12, 14), (20, 22), (30, 32)]));
1671        assert_eq!(v4_spans(&set), vec![(10, 11), (15, 19), (23, 29), (33, 40)]);
1672    }
1673
1674    /// A range ending at the last address of its family, cut from below.
1675    ///
1676    /// The tail emission must not compute `end + 1`. Both families; for v6 the
1677    /// overflow would be in a `u128`.
1678    #[test]
1679    fn a_range_ending_at_the_last_address_survives_a_cut() {
1680        let mut set = IpSet::new();
1681        set.push_v4_range(
1682            Ipv4Range::new(
1683                Ipv4Addr::new(255, 255, 255, 250),
1684                Ipv4Addr::new(255, 255, 255, 255),
1685            )
1686            .expect("start <= end"),
1687        );
1688        set.push_v6_range(
1689            Ipv6Range::new(Ipv6Addr::from(u128::MAX - 5), Ipv6Addr::from(u128::MAX))
1690                .expect("start <= end"),
1691        );
1692        set.canonicalize();
1693
1694        let mut cuts = IpSet::new();
1695        cuts.insert(IpAddr::V4(Ipv4Addr::new(255, 255, 255, 252)));
1696        cuts.insert(IpAddr::V6(Ipv6Addr::from(u128::MAX - 2)));
1697
1698        set.subtract(&cuts);
1699
1700        assert!(!set.contains(&IpAddr::V4(Ipv4Addr::new(255, 255, 255, 252))));
1701        assert!(set.contains(&IpAddr::V4(Ipv4Addr::new(255, 255, 255, 255))));
1702        assert!(!set.contains(&IpAddr::V6(Ipv6Addr::from(u128::MAX - 2))));
1703        assert!(set.contains(&IpAddr::V6(Ipv6Addr::from(u128::MAX))));
1704    }
1705
1706    /// A subtraction cuts an address out of every interface it appears on, and
1707    /// leaves the zones of what survives intact.
1708    ///
1709    /// See `subtract`. Surviving pieces must keep their zone, or they could not be
1710    /// probed.
1711    #[test]
1712    fn subtracting_a_link_local_address_clears_it_from_every_interface() {
1713        let base = u128::from(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0));
1714        let mut set = IpSet::new();
1715        for zone in [1u32, 2u32] {
1716            set.push_v6_range(
1717                Ipv6Range::scoped(
1718                    Ipv6Addr::from(base + 10),
1719                    Ipv6Addr::from(base + 20),
1720                    Some(zone),
1721                )
1722                .expect("start <= end"),
1723            );
1724        }
1725        set.canonicalize();
1726
1727        // Named on one interface, removed from both.
1728        let mut cuts = IpSet::new();
1729        cuts.push_v6_range(
1730            Ipv6Range::scoped(
1731                Ipv6Addr::from(base + 15),
1732                Ipv6Addr::from(base + 15),
1733                Some(1),
1734            )
1735            .expect("start <= end"),
1736        );
1737        cuts.canonicalize();
1738
1739        set.subtract(&cuts);
1740
1741        assert!(!set.contains(&IpAddr::V6(Ipv6Addr::from(base + 15))));
1742        assert_eq!(set.len(), 20);
1743        assert_eq!(
1744            set.v6().iter().filter(|r| r.zone().is_none()).count(),
1745            0,
1746            "every surviving piece keeps the interface of the range it came from"
1747        );
1748    }
1749
1750    proptest::proptest! {
1751        /// The numbering and the enumeration agree over any set. An address several
1752        /// interfaces hold may answer `None` from `find`, never the wrong position.
1753        #[test]
1754        fn a_position_is_the_enumeration_index_for_any_set(
1755            set in any_ipset(),
1756        ) {
1757            let positions = set.positions();
1758            let walked: Vec<IpAddr> = set.iter().collect();
1759
1760            prop_assert_eq!(positions.total() as usize, walked.len());
1761            for (index, ip) in walked.iter().enumerate() {
1762                // A position names one address.
1763                prop_assert_eq!(positions.address_at(index as u64), Some(*ip));
1764
1765                let held_twice = walked.iter().filter(|other| *other == ip).count() > 1;
1766                match positions.find(*ip) {
1767                    Some(found) => prop_assert_eq!(found, index as u64),
1768                    None => prop_assert!(held_twice, "{} has one position and no answer", ip),
1769                }
1770            }
1771        }
1772
1773        /// Narrowing to a span of positions gives back exactly those addresses.
1774        #[test]
1775        fn a_span_of_positions_narrows_to_exactly_those_addresses(
1776            set in any_ipset(),
1777            from in 0usize..40,
1778            span in 0usize..40,
1779        ) {
1780            let positions = set.positions();
1781            let walked: Vec<IpAddr> = set.iter().collect();
1782
1783            let mut narrowed = IpSet::new();
1784            for range in positions.ranges_in(from as u64..(from + span) as u64) {
1785                narrowed.insert_range(range);
1786            }
1787            narrowed.canonicalize();
1788
1789            let expected: Vec<IpAddr> = walked.into_iter().skip(from).take(span).collect();
1790            let found: Vec<IpAddr> = narrowed.iter().collect();
1791            prop_assert_eq!(found, expected);
1792        }
1793
1794        /// Membership has to agree with a linear scan of the same ranges.
1795        ///
1796        /// Zones put overlapping ranges in one vector, which a binary search could step
1797        /// past; see also
1798        /// `membership_answers_when_ranges_on_different_interfaces_overlap`.
1799        #[test]
1800        fn zoned_membership_agrees_with_a_linear_scan(
1801            ranges in prop::collection::vec(any_zoned_v6_range(), 1..12),
1802            offsets in prop::collection::vec(0..80u128, 1..20),
1803        ) {
1804            let mut set = IpSet::new();
1805            for range in &ranges {
1806                set.push_v6_range(*range);
1807            }
1808            set.canonicalize();
1809
1810            let base = u128::from(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 0));
1811            for offset in offsets {
1812                let probe = Ipv6Addr::from(base + offset);
1813                let expected = ranges.iter().any(|range| range.contains(&probe));
1814                prop_assert_eq!(
1815                    set.contains(&IpAddr::V6(probe)),
1816                    expected,
1817                    "{} in {:?}", probe, ranges
1818                );
1819            }
1820        }
1821
1822        /// Membership after a difference, against the definition of one.
1823        ///
1824        /// An address survives exactly when it was there and was not cut, probed at
1825        /// the boundaries.
1826        #[test]
1827        fn a_difference_keeps_exactly_what_was_not_cut(
1828            target in prop::collection::vec((0..64u8, 0..64u8), 1..8),
1829            cuts in prop::collection::vec((0..64u8, 0..64u8), 0..8),
1830        ) {
1831            let spans = |raw: &[(u8, u8)]| -> Vec<(u8, u8)> {
1832                raw.iter()
1833                    .map(|&(a, b)| if a <= b { (a, b) } else { (b, a) })
1834                    .collect()
1835            };
1836            let target = spans(&target);
1837            let cuts = spans(&cuts);
1838
1839            let before = v4_set(&target);
1840            let cut_set = v4_set(&cuts);
1841            let mut after = before.clone();
1842            after.subtract(&cut_set);
1843
1844            for probe in 0..=65u8 {
1845                let ip = IpAddr::V4(Ipv4Addr::new(198, 51, 100, probe));
1846                prop_assert_eq!(
1847                    after.contains(&ip),
1848                    before.contains(&ip) && !cut_set.contains(&ip),
1849                    "{} after {:?} minus {:?}", ip, target, cuts
1850                );
1851            }
1852
1853            // The result must be canonical.
1854            let mut recanonicalized = after.clone();
1855            recanonicalized.canonicalize();
1856            prop_assert_eq!(after.v4(), recanonicalized.v4());
1857        }
1858
1859        #[test]
1860        fn v4_membership_invariant(ips in proptest::collection::vec(any_ipv4(), 1..50)) {
1861            let mut set = IpSet::new();
1862            for &ip in &ips {
1863                set.insert(IpAddr::V4(ip));
1864            }
1865            for ip in ips {
1866                prop_assert!(set.contains(&IpAddr::V4(ip)));
1867            }
1868        }
1869
1870        #[test]
1871        fn v6_membership_invariant(ips in proptest::collection::vec(any_ipv6(), 1..50)) {
1872            let mut set = IpSet::new();
1873            for &ip in &ips {
1874                set.insert(IpAddr::V6(ip));
1875            }
1876            for ip in ips {
1877                prop_assert!(set.contains(&IpAddr::V6(ip)));
1878            }
1879        }
1880
1881        #[test]
1882        fn order_independence_mixed(
1883            ips in proptest::collection::vec(
1884                prop_oneof![
1885                    any_ipv4().prop_map(IpAddr::V4),
1886                    any_ipv6().prop_map(IpAddr::V6),
1887                ],
1888                0..50
1889            )
1890        ) {
1891            let mut set1 = IpSet::new();
1892            let mut set2 = IpSet::new();
1893
1894            for &ip in &ips { set1.insert(ip); }
1895            let mut ips_rev = ips.clone();
1896            ips_rev.reverse();
1897            for &ip in &ips_rev { set2.insert(ip); }
1898
1899            set1.canonicalize();
1900            set2.canonicalize();
1901            prop_assert_eq!(set1, set2);
1902        }
1903    }
1904}