/rust/registry/src/index.crates.io-1949cf8c6b5b557f/diskann-0.54.0/src/internal/chain.rs

Source
/*
 * Copyright (c) Microsoft Corporation.
 * Licensed under the MIT license.
 */

/// An iterator chain that implements [`ExactSizeIterator`] by assuming the
/// combined length of `A` and `B` does not overflow `usize`.
///
/// [`std::iter::Chain`] deliberately does not implement `ExactSizeIterator`
/// because `a.len() + b.len()` can theoretically overflow. In our domain,
/// both sides are small (neighbor lists, candidate pools) so overflow is
/// impossible.
#[derive(Debug, Clone)]
pub(crate) struct Chain<A, B> {
    a: A,
    b: B,
}

impl<A, B> Chain<A, B> {
    fn new(a: A, b: B) -> Self {
        Self { a, b }
    }
}

pub(crate) fn chain<T, U>(a: T, b: U) -> Chain<T::IntoIter, U::IntoIter>
where
    T: IntoIterator,
    U: IntoIterator<Item = T::Item>,
{
    Chain::new(a.into_iter(), b.into_iter())
}

impl<A, B> Iterator for Chain<A, B>
where
    A: ExactSizeIterator,
    B: ExactSizeIterator<Item = A::Item>,
{
    type Item = A::Item;

    fn next(&mut self) -> Option<Self::Item> {
        self.a.next().or_else(|| self.b.next())
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let (a_lo, _) = self.a.size_hint();
        let (b_lo, _) = self.b.size_hint();
        #[expect(
            clippy::expect_used,
            reason = "internally - we should never even get close"
        )]
        let len = a_lo.checked_add(b_lo).expect("Chain length overflow");
        (len, Some(len))
    }
}

impl<A, B> ExactSizeIterator for Chain<A, B>
where
    A: ExactSizeIterator,
    B: ExactSizeIterator<Item = A::Item>,
{
    fn len(&self) -> usize {
        #[expect(
            clippy::expect_used,
            reason = "internally - we should never even get close"
        )]
        self.a
            .len()
            .checked_add(self.b.len())
            .expect("Chain length overflow")
    }
}

#[cfg(test)]
mod tests {
    use super::chain;

    #[test]
    fn empty_both() {
        let c = chain(std::iter::empty::<i32>(), std::iter::empty::<i32>());
        assert_eq!(c.len(), 0);
        assert_eq!(c.collect::<Vec<_>>(), Vec::<i32>::new());
    }

    #[test]
    fn empty_left() {
        let c = chain(std::iter::empty::<i32>(), [1, 2, 3]);
        assert_eq!(c.len(), 3);
        assert_eq!(c.collect::<Vec<_>>(), vec![1, 2, 3]);
    }

    #[test]
    fn empty_right() {
        let c = chain([1, 2, 3], std::iter::empty::<i32>());
        assert_eq!(c.len(), 3);
        assert_eq!(c.collect::<Vec<_>>(), vec![1, 2, 3]);
    }

    #[test]
    fn both_non_empty() {
        let c = chain([1, 2], [3, 4, 5]);
        assert_eq!(c.len(), 5);
        assert_eq!(c.collect::<Vec<_>>(), vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn len_decreases_as_consumed() {
        let mut c = chain([10, 20], [30]);
        assert_eq!(c.len(), 3);
        assert_eq!(c.next(), Some(10));
        assert_eq!(c.len(), 2);
        assert_eq!(c.next(), Some(20));
        assert_eq!(c.len(), 1);
        assert_eq!(c.next(), Some(30));
        assert_eq!(c.len(), 0);
        assert_eq!(c.next(), None);
    }

    #[test]
    fn clone_is_independent() {
        let c = chain([1, 2], [3]);
        let collected_clone = c.clone().collect::<Vec<_>>();
        let collected_orig = c.collect::<Vec<_>>();
        assert_eq!(collected_clone, collected_orig);
    }

    #[test]
    fn size_hint_matches_len() {
        let c = chain([1, 2, 3], [4, 5]);
        let (lo, hi) = c.size_hint();
        assert_eq!(lo, 5);
        assert_eq!(hi, Some(5));
        assert_eq!(c.len(), 5);
    }
}

Line	Count	Source
1		/*
2		* Copyright (c) Microsoft Corporation.
3		* Licensed under the MIT license.
4		*/
5
6		/// An iterator chain that implements [`ExactSizeIterator`] by assuming the
7		/// combined length of `A` and `B` does not overflow `usize`.
8		///
9		/// [`std::iter::Chain`] deliberately does not implement `ExactSizeIterator`
10		/// because `a.len() + b.len()` can theoretically overflow. In our domain,
11		/// both sides are small (neighbor lists, candidate pools) so overflow is
12		/// impossible.
13		#[derive(Debug, Clone)]
14		pub(crate) struct Chain<A, B> {
15		a: A,
16		b: B,
17		}
18
19		impl<A, B> Chain<A, B> {
20	0	fn new(a: A, b: B) -> Self {
21	0	Self { a, b }
22	0	} Unexecuted instantiation: <diskann::internal::chain::Chain<core::iter::sources::once::Once<u64>, core::iter::adapters::copied::Copied<core::slice::iter::Iter<u64>>>>::new Unexecuted instantiation: <diskann::internal::chain::Chain<_, _>>::new
23		}
24
25	0	pub(crate) fn chain<T, U>(a: T, b: U) -> Chain<T::IntoIter, U::IntoIter>
26	0	where
27	0	T: IntoIterator,
28	0	U: IntoIterator<Item = T::Item>,
29		{
30	0	Chain::new(a.into_iter(), b.into_iter())
31	0	} Unexecuted instantiation: diskann::internal::chain::chain::<core::iter::sources::once::Once<u64>, core::iter::adapters::copied::Copied<core::slice::iter::Iter<u64>>> Unexecuted instantiation: diskann::internal::chain::chain::<_, _>
32
33		impl<A, B> Iterator for Chain<A, B>
34		where
35		A: ExactSizeIterator,
36		B: ExactSizeIterator<Item = A::Item>,
37		{
38		type Item = A::Item;
39
40	0	fn next(&mut self) -> Option<Self::Item> {
41	0	self.a.next().or_else(\|\| self.b.next()) Unexecuted instantiation: <diskann::internal::chain::Chain<core::iter::sources::once::Once<u64>, core::iter::adapters::copied::Copied<core::slice::iter::Iter<u64>>> as core::iter::traits::iterator::Iterator>::next::{closure#0} Unexecuted instantiation: <diskann::internal::chain::Chain<_, _> as core::iter::traits::iterator::Iterator>::next::{closure#0}
42	0	} Unexecuted instantiation: <diskann::internal::chain::Chain<core::iter::sources::once::Once<u64>, core::iter::adapters::copied::Copied<core::slice::iter::Iter<u64>>> as core::iter::traits::iterator::Iterator>::next Unexecuted instantiation: <diskann::internal::chain::Chain<_, _> as core::iter::traits::iterator::Iterator>::next
43
44	0	fn size_hint(&self) -> (usize, Option<usize>) {
45	0	let (a_lo, _) = self.a.size_hint();
46	0	let (b_lo, _) = self.b.size_hint();
47		#[expect(
48		clippy::expect_used,
49		reason = "internally - we should never even get close"
50		)]
51	0	let len = a_lo.checked_add(b_lo).expect("Chain length overflow");
52	0	(len, Some(len))
53	0	} Unexecuted instantiation: <diskann::internal::chain::Chain<core::iter::sources::once::Once<u64>, core::iter::adapters::copied::Copied<core::slice::iter::Iter<u64>>> as core::iter::traits::iterator::Iterator>::size_hint Unexecuted instantiation: <diskann::internal::chain::Chain<_, _> as core::iter::traits::iterator::Iterator>::size_hint
54		}
55
56		impl<A, B> ExactSizeIterator for Chain<A, B>
57		where
58		A: ExactSizeIterator,
59		B: ExactSizeIterator<Item = A::Item>,
60		{
61	0	fn len(&self) -> usize {
62		#[expect(
63		clippy::expect_used,
64		reason = "internally - we should never even get close"
65		)]
66	0	self.a
67	0	.len()
68	0	.checked_add(self.b.len())
69	0	.expect("Chain length overflow")
70	0	} Unexecuted instantiation: <diskann::internal::chain::Chain<core::iter::sources::once::Once<u64>, core::iter::adapters::copied::Copied<core::slice::iter::Iter<u64>>> as core::iter::traits::exact_size::ExactSizeIterator>::len Unexecuted instantiation: <diskann::internal::chain::Chain<_, _> as core::iter::traits::exact_size::ExactSizeIterator>::len
71		}
72
73		#[cfg(test)]
74		mod tests {
75		use super::chain;
76
77		#[test]
78		fn empty_both() {
79		let c = chain(std::iter::empty::<i32>(), std::iter::empty::<i32>());
80		assert_eq!(c.len(), 0);
81		assert_eq!(c.collect::<Vec<_>>(), Vec::<i32>::new());
82		}
83
84		#[test]
85		fn empty_left() {
86		let c = chain(std::iter::empty::<i32>(), [1, 2, 3]);
87		assert_eq!(c.len(), 3);
88		assert_eq!(c.collect::<Vec<_>>(), vec![1, 2, 3]);
89		}
90
91		#[test]
92		fn empty_right() {
93		let c = chain([1, 2, 3], std::iter::empty::<i32>());
94		assert_eq!(c.len(), 3);
95		assert_eq!(c.collect::<Vec<_>>(), vec![1, 2, 3]);
96		}
97
98		#[test]
99		fn both_non_empty() {
100		let c = chain([1, 2], [3, 4, 5]);
101		assert_eq!(c.len(), 5);
102		assert_eq!(c.collect::<Vec<_>>(), vec![1, 2, 3, 4, 5]);
103		}
104
105		#[test]
106		fn len_decreases_as_consumed() {
107		let mut c = chain([10, 20], [30]);
108		assert_eq!(c.len(), 3);
109		assert_eq!(c.next(), Some(10));
110		assert_eq!(c.len(), 2);
111		assert_eq!(c.next(), Some(20));
112		assert_eq!(c.len(), 1);
113		assert_eq!(c.next(), Some(30));
114		assert_eq!(c.len(), 0);
115		assert_eq!(c.next(), None);
116		}
117
118		#[test]
119		fn clone_is_independent() {
120		let c = chain([1, 2], [3]);
121		let collected_clone = c.clone().collect::<Vec<_>>();
122		let collected_orig = c.collect::<Vec<_>>();
123		assert_eq!(collected_clone, collected_orig);
124		}
125
126		#[test]
127		fn size_hint_matches_len() {
128		let c = chain([1, 2, 3], [4, 5]);
129		let (lo, hi) = c.size_hint();
130		assert_eq!(lo, 5);
131		assert_eq!(hi, Some(5));
132		assert_eq!(c.len(), 5);
133		}
134		}

Coverage Report

Created: 2026-07-13 08:11