1use 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#[non_exhaustive]
44#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
45pub enum IpSetError {
46 #[error("Invalid target in set: {0}")]
48 InvalidTarget(#[from] IpError),
49}
50
51#[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#[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 pub(super) fn note() {
84 ADDED.with(|added| added.set(added.get() + 1));
85 }
86
87 pub(crate) fn so_far() -> usize {
89 ADDED.with(Cell::get)
90 }
91}
92
93impl IpSet {
94 pub fn new() -> Self {
96 Self::default()
97 }
98
99 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 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 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 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 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 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 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 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 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 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 let (run, tail) = rest.split_at(rest.partition_point(|r| r.zone() == zone));
267 rest = tail;
268 Some(run)
269 })
270 }
271
272 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 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 pub fn is_empty(&self) -> bool {
308 self.v4.is_empty() && self.v6.is_empty()
309 }
310
311 pub fn len_gross(&self) -> u128 {
317 self.v4_len().saturating_add(self.v6_len())
318 }
319
320 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 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 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 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 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 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 pub fn v6_len(&self) -> u128 {
453 self.v6
454 .iter()
455 .fold(0u128, |total, r| total.saturating_add(r.len()))
456 }
457
458 pub fn v4(&self) -> &[Ipv4Range] {
460 &self.v4
461 }
462
463 pub fn v6(&self) -> &[Ipv6Range] {
465 &self.v6
466 }
467}
468
469impl PartialEq for IpSet {
470 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#[derive(Debug, Clone, Default)]
511pub struct Positions {
512 spans: Vec<Span>,
515 runs: Vec<Run>,
521 total: u64,
523 unnumbered: Vec<IpRange>,
525}
526
527#[derive(Debug, Clone, Copy)]
529struct Run {
530 from: usize,
532 to: usize,
534 v6: bool,
536}
537
538#[derive(Debug, Clone, Copy)]
540struct Span {
541 range: IpRange,
542 start: u64,
544 len: u64,
546}
547
548impl Positions {
549 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 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 pub fn total(&self) -> u64 {
625 self.total
626 }
627
628 pub fn is_empty(&self) -> bool {
633 self.total == 0
634 }
635
636 pub fn unnumbered(&self) -> &[IpRange] {
641 &self.unnumbered
642 }
643
644 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 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 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 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 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 pub fn positions(&self) -> Positions {
754 Positions::of(self)
755 }
756}
757
758fn 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
766fn 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
774fn 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
793fn 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
807fn 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 (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
826fn 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
835fn v6_bounds(range: &Ipv6Range) -> (u128, u128) {
838 (u128::from(range.start_addr()), u128::from(range.end_addr()))
839}
840
841fn 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 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
861fn 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 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 let mut cut = first_live;
893 while cut < cuts.len() && cuts[cut].0 <= end {
894 let (cut_start, cut_end) = cuts[cut];
895
896 if cut_start > cursor {
898 kept.push(rebuild(range, cursor, cut_start - 1));
899 }
900
901 if cut_end >= end {
904 consumed = true;
905 break;
906 }
907
908 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
921fn 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
944impl IntoIterator for IpSet {
949 type Item = IpAddr;
950 type IntoIter = Box<dyn Iterator<Item = IpAddr> + Send>;
951
952 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 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#[cfg(test)]
1073mod tests {
1074 use super::*;
1075
1076 #[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 assert_eq!(set.v4.len(), 2);
1086 assert!(set.v4_dirty);
1087
1088 set.canonicalize();
1090 assert_eq!(set.len(), 2);
1091 assert!(!set.v4_dirty);
1092 assert_eq!(set.v4.len(), 1);
1093 }
1094
1095 #[test]
1097 fn every_kind_of_overlap_collapses_to_one_range() {
1098 let mut set = IpSet::new();
1099 set.insert_range("198.51.100.10-198.51.100.20".parse().unwrap());
1101 set.insert_range("198.51.100.5-198.51.100.15".parse().unwrap());
1103 set.insert_range("198.51.100.15-198.51.100.25".parse().unwrap());
1105 set.insert_range("198.51.100.30-198.51.100.40".parse().unwrap());
1107 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 #[test]
1117 fn the_top_of_the_ipv6_space_merges_without_overflowing() {
1118 let mut set = IpSet::new();
1119 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 #[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 #[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 #[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 let mut untouched = IpSet::from_iter(vec![IpAddr::V4(Ipv4Addr::LOCALHOST)]);
1167 untouched.extend([]);
1168 assert!(!untouched.v4_dirty && !untouched.v6_dirty);
1169
1170 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 assert!(set.contains_canonical(&v6));
1178 assert!(set.contains(&v6));
1179 assert!(set.contains(&v4), "the slow path is still correct");
1180 }
1181
1182 #[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 assert_eq!(set.len(), 4);
1190 }
1191
1192 #[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 #[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 set.contains_canonical(&IpAddr::V4(Ipv4Addr::LOCALHOST));
1215 }
1216
1217 #[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 #[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 #[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 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 assert!(split.contains(&IpAddr::V6(five)));
1261 assert!(split.contains(&IpAddr::V6(six)));
1262 }
1263
1264 #[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 #[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 fn set(written: &str) -> IpSet {
1306 written.parse().expect("a valid address specification")
1307 }
1308
1309 #[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 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 #[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 #[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 #[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 #[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 #[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 #[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 #[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 #[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 #[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 #[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 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 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 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 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 #[test]
1630 fn a_cut_takes_exactly_what_it_covers() {
1631 type Case = (
1634 &'static [(u8, u8)],
1635 &'static [(u8, u8)],
1636 &'static [(u8, u8)],
1637 );
1638
1639 let cases: [Case; 6] = [
1640 (&[(10, 20)], &[(14, 16)], &[(10, 13), (17, 20)]),
1642 (&[(10, 20)], &[(5, 12)], &[(13, 20)]),
1644 (&[(10, 20)], &[(18, 25)], &[(10, 17)]),
1645 (&[(10, 20)], &[(5, 25)], &[]),
1647 (&[(10, 20)], &[(10, 20)], &[]),
1648 (&[(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 #[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 #[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 #[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 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 #[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 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 #[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 #[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 #[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 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}