1use std::collections::hash_map::Entry;
40use std::collections::{HashMap, HashSet};
41use std::net::IpAddr;
42use std::sync::Arc;
43
44use crate::model::host::Host;
45use crate::model::mac::MacAddr;
46
47#[non_exhaustive]
52#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Default)]
53pub enum HostIdentity {
54 PrimaryAddress,
60
61 #[default]
67 AnyAddress,
68
69 Hardware,
77}
78
79#[derive(Debug, Clone, PartialEq, Eq)]
84pub(crate) struct Component {
85 pub(crate) baseline: Vec<usize>,
86 pub(crate) current: Vec<usize>,
87}
88
89#[derive(Debug, Clone, PartialEq, Eq, Hash)]
91enum Token {
92 Address(IpAddr, Option<Arc<str>>),
94 Hardware(MacAddr),
96}
97
98pub(crate) fn components(
102 baseline: &[&Host],
103 current: &[&Host],
104 identity: HostIdentity,
105) -> Vec<Component> {
106 let baseline_tokens: Vec<HashSet<Token>> =
107 baseline.iter().map(|host| tokens(host, identity)).collect();
108 let current_tokens: Vec<HashSet<Token>> =
109 current.iter().map(|host| tokens(host, identity)).collect();
110
111 let mut baseline_index = index(&baseline_tokens);
112 let mut current_index = index(¤t_tokens);
113
114 let mut baseline_seen = vec![false; baseline.len()];
115 let mut current_seen = vec![false; current.len()];
116 let mut components = Vec::new();
117
118 for start in 0..baseline.len() {
119 if baseline_seen[start] {
120 continue;
121 }
122 baseline_seen[start] = true;
123
124 let mut component = Component {
125 baseline: Vec::new(),
126 current: Vec::new(),
127 };
128 let mut baseline_queue = vec![start];
129 let mut current_queue: Vec<usize> = Vec::new();
130
131 while !baseline_queue.is_empty() || !current_queue.is_empty() {
137 while let Some(i) = baseline_queue.pop() {
138 component.baseline.push(i);
139 for token in &baseline_tokens[i] {
140 for j in current_index.remove(token).unwrap_or_default() {
141 if !current_seen[j] {
142 current_seen[j] = true;
143 current_queue.push(j);
144 }
145 }
146 }
147 }
148
149 while let Some(j) = current_queue.pop() {
150 component.current.push(j);
151 for token in ¤t_tokens[j] {
152 for i in baseline_index.remove(token).unwrap_or_default() {
153 if !baseline_seen[i] {
154 baseline_seen[i] = true;
155 baseline_queue.push(i);
156 }
157 }
158 }
159 }
160 }
161
162 component.baseline.sort_unstable();
163 component.current.sort_unstable();
164 components.push(component);
165 }
166
167 for (j, seen) in current_seen.iter().enumerate() {
170 if !seen {
171 components.push(Component {
172 baseline: Vec::new(),
173 current: vec![j],
174 });
175 }
176 }
177
178 components.sort_by_key(|component| {
179 (
180 component.baseline.first().copied().unwrap_or(usize::MAX),
181 component.current.first().copied().unwrap_or(usize::MAX),
182 )
183 });
184 components
185}
186
187pub(crate) fn groups(records: &[&Host], identity: HostIdentity) -> Vec<Vec<usize>> {
201 let mut sets = DisjointSet::new(records.len());
202 let mut first_holder: HashMap<Token, usize> = HashMap::new();
203
204 for (i, host) in records.iter().enumerate() {
205 for token in tokens(host, identity) {
206 match first_holder.entry(token) {
207 Entry::Occupied(held) => sets.union(*held.get(), i),
208 Entry::Vacant(slot) => {
209 slot.insert(i);
210 }
211 }
212 }
213 }
214
215 let mut grouped: HashMap<usize, Vec<usize>> = HashMap::new();
217 let mut order: Vec<usize> = Vec::new();
218 for i in 0..records.len() {
219 let root = sets.find(i);
220 grouped.entry(root).or_insert_with(|| {
221 order.push(root);
222 Vec::new()
223 });
224 grouped.get_mut(&root).expect("just inserted").push(i);
225 }
226
227 order
228 .into_iter()
229 .map(|root| grouped.remove(&root).expect("a root that was recorded"))
230 .collect()
231}
232
233struct DisjointSet {
235 parent: Vec<usize>,
236 size: Vec<usize>,
237}
238
239impl DisjointSet {
240 fn new(len: usize) -> Self {
241 Self {
242 parent: (0..len).collect(),
243 size: vec![1; len],
244 }
245 }
246
247 fn find(&mut self, mut i: usize) -> usize {
248 while self.parent[i] != i {
249 self.parent[i] = self.parent[self.parent[i]];
250 i = self.parent[i];
251 }
252 i
253 }
254
255 fn union(&mut self, a: usize, b: usize) {
256 let (mut a, mut b) = (self.find(a), self.find(b));
257 if a == b {
258 return;
259 }
260 if self.size[a] < self.size[b] {
261 std::mem::swap(&mut a, &mut b);
262 }
263 self.parent[b] = a;
264 self.size[a] += self.size[b];
265 }
266}
267
268fn tokens(host: &Host, identity: HostIdentity) -> HashSet<Token> {
270 let zone = host.zone().map(|zone| Arc::from(zone.name()));
271
272 let mut tokens: HashSet<Token> = match identity {
273 HostIdentity::PrimaryAddress => {
274 let ip = host.primary_ip();
275 HashSet::from([Token::Address(ip, scope_of(&ip, &zone))])
276 }
277 HostIdentity::AnyAddress | HostIdentity::Hardware => host
278 .ips()
279 .iter()
280 .map(|ip| Token::Address(*ip, scope_of(ip, &zone)))
281 .collect(),
282 };
283
284 if identity == HostIdentity::Hardware
285 && let Some(hardware) = host.hardware()
286 {
287 tokens.extend(hardware.macs().keys().copied().map(Token::Hardware));
288 }
289
290 tokens
291}
292
293fn scope_of(ip: &IpAddr, zone: &Option<Arc<str>>) -> Option<Arc<str>> {
296 is_link_local(ip).then(|| zone.clone()).flatten()
297}
298
299fn is_link_local(ip: &IpAddr) -> bool {
301 match ip {
302 IpAddr::V4(v4) => v4.is_link_local(),
303 IpAddr::V6(v6) => (v6.segments()[0] & 0xffc0) == 0xfe80,
304 }
305}
306
307fn index(tokens: &[HashSet<Token>]) -> HashMap<&Token, Vec<usize>> {
309 let mut index: HashMap<&Token, Vec<usize>> = HashMap::new();
310 for (i, set) in tokens.iter().enumerate() {
311 for token in set {
312 index.entry(token).or_default().push(i);
313 }
314 }
315 index
316}
317
318#[cfg(test)]
328mod tests {
329 use std::net::{Ipv4Addr, Ipv6Addr};
330
331 use super::*;
332 use crate::model::host::HostStatus;
333 use crate::model::ip::scoped::Zone;
334 use crate::model::mac::MacAddr;
335
336 fn v4(last: u8) -> IpAddr {
337 IpAddr::V4(Ipv4Addr::new(203, 0, 113, last))
338 }
339
340 fn host(primary: IpAddr) -> Host {
341 let mut host = Host::new(primary);
342 host.set_status(HostStatus::Up);
343 host
344 }
345
346 fn shape(components: &[Component]) -> Vec<(Vec<usize>, Vec<usize>)> {
348 let mut out: Vec<(Vec<usize>, Vec<usize>)> = components
349 .iter()
350 .map(|c| {
351 let mut b = c.baseline.clone();
352 let mut n = c.current.clone();
353 b.sort_unstable();
354 n.sort_unstable();
355 (b, n)
356 })
357 .collect();
358 out.sort();
359 out
360 }
361
362 #[test]
363 fn a_host_at_the_same_address_pairs_with_itself() {
364 let before = [host(v4(1))];
365 let after = [host(v4(1))];
366 let components = components(
367 &before.iter().collect::<Vec<_>>(),
368 &after.iter().collect::<Vec<_>>(),
369 HostIdentity::AnyAddress,
370 );
371 assert_eq!(shape(&components), vec![(vec![0], vec![0])]);
372 }
373
374 #[test]
375 fn hosts_sharing_no_address_do_not_pair() {
376 let before = [host(v4(1))];
377 let after = [host(v4(2))];
378 let components = components(
379 &before.iter().collect::<Vec<_>>(),
380 &after.iter().collect::<Vec<_>>(),
381 HostIdentity::AnyAddress,
382 );
383 assert_eq!(
384 shape(&components),
385 vec![(vec![], vec![0]), (vec![0], vec![])],
386 "one host went away and another arrived"
387 );
388 }
389
390 #[test]
392 fn a_shared_secondary_address_pairs_two_records() {
393 let mut before = host(v4(1));
394 before.add_ip(v4(50));
395 let after = host(v4(50));
396
397 let components = components(&[&before], &[&after], HostIdentity::AnyAddress);
398 assert_eq!(shape(&components), vec![(vec![0], vec![0])]);
399 }
400
401 #[test]
404 fn a_shared_secondary_address_does_not_pair_under_primary_address() {
405 let mut before = host(v4(1));
406 before.add_ip(v4(50));
407 let after = host(v4(50));
408
409 let components = components(&[&before], &[&after], HostIdentity::PrimaryAddress);
410 assert_eq!(
411 shape(&components),
412 vec![(vec![], vec![0]), (vec![0], vec![])]
413 );
414 }
415
416 #[test]
418 fn records_the_two_scans_grouped_differently_form_one_component() {
419 let mut merged = host(v4(1));
420 merged.add_ip(v4(2));
421 let split_a = host(v4(1));
422 let split_b = host(v4(2));
423
424 let components = components(&[&merged], &[&split_a, &split_b], HostIdentity::AnyAddress);
425 assert_eq!(shape(&components), vec![(vec![0], vec![0, 1])]);
426 }
427
428 #[test]
431 fn link_local_addresses_on_different_zones_are_different_hosts() {
432 let link_local = IpAddr::V6(Ipv6Addr::new(0xfe80, 0, 0, 0, 0, 0, 0, 1));
433
434 let mut before = Host::new(link_local);
435 before.set_zone(Zone::new(1, "en0"));
436 before.set_status(HostStatus::Up);
437
438 let mut after = Host::new(link_local);
439 after.set_zone(Zone::new(2, "en1"));
440 after.set_status(HostStatus::Up);
441
442 let components = components(&[&before], &[&after], HostIdentity::AnyAddress);
443 assert_eq!(
444 shape(&components),
445 vec![(vec![], vec![0]), (vec![0], vec![])],
446 "the same link-local address on two segments is two machines"
447 );
448 }
449
450 #[test]
451 fn hardware_identity_pairs_a_host_that_changed_address() {
452 let mac = MacAddr::new(0x2c, 0xcf, 0x67, 0x00, 0x00, 0x01);
453
454 let mut before = host(v4(1));
455 before.record_mac(mac);
456 let mut after = host(v4(2));
457 after.record_mac(mac);
458
459 let components = components(&[&before], &[&after], HostIdentity::Hardware);
460 assert_eq!(
461 shape(&components),
462 vec![(vec![0], vec![0])],
463 "a DHCP lease moving is not a host being replaced"
464 );
465 }
466
467 #[test]
468 fn groups_folds_records_that_share_an_address() {
469 let mut one = host(v4(1));
470 one.add_ip(v4(9));
471 let two = host(v4(9));
472 let three = host(v4(3));
473
474 let mut groups = groups(&[&one, &two, &three], HostIdentity::AnyAddress);
475 for group in &mut groups {
476 group.sort_unstable();
477 }
478 groups.sort();
479 assert_eq!(groups, vec![vec![0, 1], vec![2]]);
480 }
481}