22350210654

Committed 24 Feb 2026 12:10PM UTC coverage: 71.503% (-0.2%) from 71.724%

Build # 22350210654

Build Type

push

github

Committed by

vigna

Commit Message

code_to_str now returns None instead of panicking

Coverage Stats

10 of 33 new or added lines in 6 files covered. (30.3%)

5 existing lines in 1 file now uncovered.

6278 of 8780 relevant lines covered (71.5%)

51288774.37 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

75.0

/webgraph/src/traits/split.rs

/*
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

//! Traits and basic implementations to support parallel completion by splitting
//! the [iterator](SequentialLabeling::Lender) of a labeling into multiple
//! iterators.

use std::rc::Rc;

use impl_tools::autoimpl;

use super::{labels::SequentialLabeling, lenders::NodeLabelsLender};

/// A trait with a single method that splits a labeling into `n` parts which are
/// thread safe.
///
/// Labeling implementing this trait can be analyzed in parallel by calling
/// [`split_iter`](SplitLabeling::split_iter) to split the labeling
/// [iterator](SequentialLabeling::Lender) into `n` parts.
///
/// Each part is returned as a tuple `(usize, SplitLender)` where the first
/// element indicates the first node ID covered by that lender.
///
/// Note that the parts are required to be [`Send`] and [`Sync`], so that they
/// can be safely shared among threads.
///
/// Due to some limitations of the current Rust type system, we cannot provide
/// blanket implementations for this trait. However, we provide ready-made
/// implementations for the [sequential](seq) and [random-access](ra) cases. To
/// use them, you must implement the trait by specifying the associated types
/// `Lender` and `IntoIterator`, and then just return a [`seq::Iter`] or
/// [`ra::Iter`] structure.
#[autoimpl(for<S: trait + ?Sized> &S, &mut S, Rc<S>)]
pub trait SplitLabeling: SequentialLabeling {
    type SplitLender<'a>: for<'next> NodeLabelsLender<'next, Label = <Self as SequentialLabeling>::Label>
        + Send
        + Sync
    where
        Self: 'a;

    type IntoIterator<'a>: IntoIterator<Item = Self::SplitLender<'a>, IntoIter: ExactSizeIterator>
    where
        Self: 'a;

    fn split_iter(&self, n: usize) -> Self::IntoIterator<'_>;
}

/// Ready-made implementation for the sequential case.
///
/// This implementation walks through the iterator of a labeling and
/// clones it at regular intervals. To use it, you have to implement the
/// trait by specifying the associated types `Lender` and `IntoIterator`
/// using the [`seq::Lender`] and [`seq::IntoIterator`] types aliases,
/// and then return a [`seq::Iter`] structure.
///
/// # Examples
///
/// The code for [`BvGraphSeq`](crate::graphs::bvgraph::sequential::BvGraphSeq) is:
/// ```ignore
/// impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
/// where
///     for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
/// {
///     type SplitLender<'a> = split::seq::Lender<'a, BvGraphSeq<F>> where Self: 'a;
///     type IntoIterator<'a> = split::seq::IntoIterator<'a, BvGraphSeq<F>> where Self: 'a;
///
///     fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
///         split::seq::Iter::new(self.iter(), self.num_nodes(), how_many)
///     }
/// }
/// ```
pub mod seq {
    use crate::prelude::SequentialLabeling;

    pub struct Iter<L> {
        lender: L,
        nodes_per_iter: usize,
        how_many: usize,
        remaining: usize,
    }

    impl<L: lender::Lender> Iter<L> {
        pub fn new(lender: L, number_of_nodes: usize, how_many: usize) -> Self {
            let nodes_per_iter = number_of_nodes.div_ceil(how_many);
            Self {
                lender,
                nodes_per_iter,
                how_many,
                remaining: how_many,
            }
        }
    }

    impl<L: lender::Lender + Clone> Iterator for Iter<L> {
        type Item = lender::Take<L>;

        fn next(&mut self) -> Option<Self::Item> {
            if self.remaining == 0 {
                return None;
            }
            if self.remaining != self.how_many {
                self.lender.advance_by(self.nodes_per_iter).ok()?;
            }
            self.remaining -= 1;
            Some(self.lender.clone().take(self.nodes_per_iter))
        }

        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.remaining, Some(self.remaining))
        }

        fn count(self) -> usize {
            self.len()
        }
    }

    impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {
        fn len(&self) -> usize {
            self.remaining
        }
    }

    pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
    pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
}

/// Ready-made implementation for the random-access case.
///
/// This implementation uses the [`iter_from`](SequentialLabeling::iter_from) at
/// regular intervals. To use it, you have to implement the trait by specifying
/// the associated types `Lender` and `IntoIterator` using the [`ra::Lender`]
/// and [`ra::IntoIterator`] types aliases, and then return a [`ra::Iter`]
/// structure.
///
/// # Examples
///
/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
/// ```ignore
/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
/// where
///     for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
/// {
///     type SplitLender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
///     type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
///
///     fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
///         split::ra::Iter::new(self, how_many)
///     }
/// }
/// ```
pub mod ra {
    use crate::prelude::{RandomAccessLabeling, SequentialLabeling};

    pub struct Iter<'a, R: RandomAccessLabeling> {
        labeling: &'a R,
        nodes_per_iter: usize,
        how_many: usize,
        i: usize,
    }

    impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
        pub fn new(labeling: &'a R, how_many: usize) -> Self {
            let nodes_per_iter = labeling.num_nodes().div_ceil(how_many);
            Self {
                labeling,
                nodes_per_iter,
                how_many,
                i: 0,
            }
        }
    }

    impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
        type Item = Lender<'a, R>;

        fn next(&mut self) -> Option<Self::Item> {
            use lender::Lender;

            if self.i == self.how_many {
                return None;
            }
            let start_node = self.i * self.nodes_per_iter;
            self.i += 1;
            Some(
                self.labeling
                    .iter_from(start_node)
                    .take(self.nodes_per_iter),
            )
        }

        fn size_hint(&self) -> (usize, Option<usize>) {
            let len = self.how_many - self.i;
            (len, Some(len))
        }

        fn count(self) -> usize {
            self.len()
        }
    }

    impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {
        fn len(&self) -> usize {
            self.how_many - self.i
        }
    }

    pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
    pub type IntoIterator<'a, R> = Iter<'a, R>;
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Tommaso Fontana
3	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	//! Traits and basic implementations to support parallel completion by splitting
9	//! the [iterator](SequentialLabeling::Lender) of a labeling into multiple
10	//! iterators.
11
12	use std::rc::Rc;
13
14	use impl_tools::autoimpl;
15
16	use super::{labels::SequentialLabeling, lenders::NodeLabelsLender};
17
18	/// A trait with a single method that splits a labeling into `n` parts which are
19	/// thread safe.
20	///
21	/// Labeling implementing this trait can be analyzed in parallel by calling
22	/// [`split_iter`](SplitLabeling::split_iter) to split the labeling
23	/// [iterator](SequentialLabeling::Lender) into `n` parts.
24	///
25	/// Each part is returned as a tuple `(usize, SplitLender)` where the first
26	/// element indicates the first node ID covered by that lender.
27	///
28	/// Note that the parts are required to be [`Send`] and [`Sync`], so that they
29	/// can be safely shared among threads.
30	///
31	/// Due to some limitations of the current Rust type system, we cannot provide
32	/// blanket implementations for this trait. However, we provide ready-made
33	/// implementations for the [sequential](seq) and [random-access](ra) cases. To
34	/// use them, you must implement the trait by specifying the associated types
35	/// `Lender` and `IntoIterator`, and then just return a [`seq::Iter`] or
36	/// [`ra::Iter`] structure.
37	#[autoimpl(for<S: trait + ?Sized> &S, &mut S, Rc<S>)]
38	pub trait SplitLabeling: SequentialLabeling {
39	type SplitLender<'a>: for<'next> NodeLabelsLender<'next, Label = <Self as SequentialLabeling>::Label>
40	+ Send
41	+ Sync
42	where
43	Self: 'a;
44
45	type IntoIterator<'a>: IntoIterator<Item = Self::SplitLender<'a>, IntoIter: ExactSizeIterator>
46	where
47	Self: 'a;
48
49	fn split_iter(&self, n: usize) -> Self::IntoIterator<'_>;
50	}
51
52	/// Ready-made implementation for the sequential case.
53	///
54	/// This implementation walks through the iterator of a labeling and
55	/// clones it at regular intervals. To use it, you have to implement the
56	/// trait by specifying the associated types `Lender` and `IntoIterator`
57	/// using the [`seq::Lender`] and [`seq::IntoIterator`] types aliases,
58	/// and then return a [`seq::Iter`] structure.
59	///
60	/// # Examples
61	///
62	/// The code for [`BvGraphSeq`](crate::graphs::bvgraph::sequential::BvGraphSeq) is:
63	/// ```ignore
64	/// impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
65	/// where
66	/// for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
67	/// {
68	/// type SplitLender<'a> = split::seq::Lender<'a, BvGraphSeq<F>> where Self: 'a;
69	/// type IntoIterator<'a> = split::seq::IntoIterator<'a, BvGraphSeq<F>> where Self: 'a;
70	///
71	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
72	/// split::seq::Iter::new(self.iter(), self.num_nodes(), how_many)
73	/// }
74	/// }
75	/// ```
76	pub mod seq {
77	use crate::prelude::SequentialLabeling;
78
79	pub struct Iter<L> {
80	lender: L,
81	nodes_per_iter: usize,
82	how_many: usize,
83	remaining: usize,
84	}
85
86	impl<L: lender::Lender> Iter<L> {
87	pub fn new(lender: L, number_of_nodes: usize, how_many: usize) -> Self {	49✔
88	let nodes_per_iter = number_of_nodes.div_ceil(how_many);	196✔
89	Self {
90	lender,
91	nodes_per_iter,
92	how_many,
93	remaining: how_many,
94	}
95	}
96	}
97
98	impl<L: lender::Lender + Clone> Iterator for Iter<L> {
99	type Item = lender::Take<L>;
100
101	fn next(&mut self) -> Option<Self::Item> {	285✔
102	if self.remaining == 0 {	285✔
103	return None;	49✔
104	}
105	if self.remaining != self.how_many {	236✔
106	self.lender.advance_by(self.nodes_per_iter).ok()?;	748✔
107	}
108	self.remaining -= 1;	236✔
109	Some(self.lender.clone().take(self.nodes_per_iter))	708✔
110	}
111
112	fn size_hint(&self) -> (usize, Option<usize>) {	12✔
113	(self.remaining, Some(self.remaining))	12✔
114	}
115
NEW 116	fn count(self) -> usize {	×
NEW 117	self.len()	×
118	}
119	}
120
121	impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {
122	fn len(&self) -> usize {	×
123	self.remaining	×
124	}
125	}
126
127	pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
128	pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
129	}
130
131	/// Ready-made implementation for the random-access case.
132	///
133	/// This implementation uses the [`iter_from`](SequentialLabeling::iter_from) at
134	/// regular intervals. To use it, you have to implement the trait by specifying
135	/// the associated types `Lender` and `IntoIterator` using the [`ra::Lender`]
136	/// and [`ra::IntoIterator`] types aliases, and then return a [`ra::Iter`]
137	/// structure.
138	///
139	/// # Examples
140	///
141	/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
142	/// ```ignore
143	/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
144	/// where
145	/// for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
146	/// {
147	/// type SplitLender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
148	/// type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
149	///
150	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
151	/// split::ra::Iter::new(self, how_many)
152	/// }
153	/// }
154	/// ```
155	pub mod ra {
156	use crate::prelude::{RandomAccessLabeling, SequentialLabeling};
157
158	pub struct Iter<'a, R: RandomAccessLabeling> {
159	labeling: &'a R,
160	nodes_per_iter: usize,
161	how_many: usize,
162	i: usize,
163	}
164
165	impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
166	pub fn new(labeling: &'a R, how_many: usize) -> Self {	622,109✔
167	let nodes_per_iter = labeling.num_nodes().div_ceil(how_many);	3,110,545✔
168	Self {
169	labeling,
170	nodes_per_iter,
171	how_many,
172	i: 0,
173	}
174	}
175	}
176
177	impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
178	type Item = Lender<'a, R>;
179
180	fn next(&mut self) -> Option<Self::Item> {	3,110,511✔
181	use lender::Lender;
182
183	if self.i == self.how_many {	3,110,511✔
184	return None;	622,097✔
185	}
186	let start_node = self.i * self.nodes_per_iter;	4,976,828✔
187	self.i += 1;	2,488,414✔
188	Some(
189	self.labeling	4,976,828✔
190	.iter_from(start_node)	7,465,242✔
191	.take(self.nodes_per_iter),	2,488,414✔
192	)
193	}
194
195	fn size_hint(&self) -> (usize, Option<usize>) {	14✔
196	let len = self.how_many - self.i;	28✔
197	(len, Some(len))	14✔
198	}
199
NEW 200	fn count(self) -> usize {	×
NEW 201	self.len()	×
202	}
203	}
204
205	impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {
206	fn len(&self) -> usize {	×
207	self.how_many - self.i	×
208	}
209	}
210
211	pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
212	pub type IntoIterator<'a, R> = Iter<'a, R>;
213	}

vigna / webgraph-rs / 22350210654

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous