18008720487

Committed 25 Sep 2025 01:16PM UTC coverage: 49.589% (-0.4%) from 49.949%

Build # 18008720487

Build Type

push

github

Committed by

vigna

Commit Message

Fixed fuzzing code for new epserde

Run Details

0 of 2 new or added lines in 1 file covered. (0.0%)

650 existing lines in 25 files now uncovered.

3862 of 7788 relevant lines covered (49.59%)

25127316.85 hits per line

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

66.67

/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.
///
/// 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>>
    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(), 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))
        }
    }

    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;
            }
            self.i += 1;
            Some(
                self.labeling
                    .iter_from((self.i - 1) * self.nodes_per_iter)
                    .take(self.nodes_per_iter),
            )
        }
    }

    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	/// Note that the parts are required to be [`Send`] and [`Sync`], so that they
26	/// can be safely shared among threads.
27	///
28	/// Due to some limitations of the current Rust type system, we cannot provide
29	/// blanket implementations for this trait. However, we provide ready-made
30	/// implementations for the [sequential](seq) and [random-access](ra) cases. To
31	/// use them, you must implement the trait by specifying the associated types
32	/// `Lender` and `IntoIterator`, and then just return a [`seq::Iter`] or
33	/// [`ra::Iter`] structure.
34	#[autoimpl(for<S: trait + ?Sized> &S, &mut S, Rc<S>)]
35	pub trait SplitLabeling: SequentialLabeling {
36	type SplitLender<'a>: for<'next> NodeLabelsLender<'next, Label = <Self as SequentialLabeling>::Label>
37	+ Send
38	+ Sync
39	where
40	Self: 'a;
41
42	type IntoIterator<'a>: IntoIterator<Item = Self::SplitLender<'a>>
43	where
44	Self: 'a;
45
46	fn split_iter(&self, n: usize) -> Self::IntoIterator<'_>;
47	}
48
49	/// Ready-made implementation for the sequential case.
50	///
51	/// This implementation walks through the iterator of a labeling and
52	/// clones it at regular intervals. To use it, you have to implement the
53	/// trait by specifying the associated types `Lender` and `IntoIterator`
54	/// using the [`seq::Lender`] and [`seq::IntoIterator`] types aliases,
55	/// and then return a [`seq::Iter`] structure.
56	///
57	/// # Examples
58	///
59	/// The code for [`BvGraphSeq`](crate::graphs::bvgraph::sequential::BvGraphSeq) is:
60	/// ```ignore
61	/// impl<F: SequentialDecoderFactory> SplitLabeling for BvGraphSeq<F>
62	/// where
63	/// for<'a> <F as SequentialDecoderFactory>::Decoder<'a>: Clone + Send + Sync,
64	/// {
65	/// type SplitLender<'a> = split::seq::Lender<'a, BvGraphSeq<F>> where Self: 'a;
66	/// type IntoIterator<'a> = split::seq::IntoIterator<'a, BvGraphSeq<F>> where Self: 'a;
67	///
68	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
69	/// split::seq::Iter::new(self.iter(), how_many)
70	/// }
71	/// }
72	/// ```
73	pub mod seq {
74	use crate::prelude::SequentialLabeling;
75
76	pub struct Iter<L> {
77	lender: L,
78	nodes_per_iter: usize,
79	how_many: usize,
80	remaining: usize,
81	}
82
83	impl<L: lender::Lender> Iter<L> {
84	pub fn new(lender: L, number_of_nodes: usize, how_many: usize) -> Self {	39✔
85	let nodes_per_iter = number_of_nodes.div_ceil(how_many);	156✔
86	Self {
87	lender,
88	nodes_per_iter,
89	how_many,
90	remaining: how_many,
91	}
92	}
93	}
94
95	impl<L: lender::Lender + Clone> Iterator for Iter<L> {
96	type Item = lender::Take<L>;
97
98	fn next(&mut self) -> Option<Self::Item> {	244✔
99	if self.remaining == 0 {	244✔
100	return None;	39✔
101	}
UNCOV 102	if self.remaining != self.how_many {	×
103	self.lender.advance_by(self.nodes_per_iter).ok()?;	664✔
104	}
105	self.remaining -= 1;	205✔
UNCOV 106	Some(self.lender.clone().take(self.nodes_per_iter))	×
107	}
108
UNCOV 109	fn size_hint(&self) -> (usize, Option<usize>) {	×
UNCOV 110	(self.remaining, Some(self.remaining))	×
111	}
112	}
113
114	impl<L: lender::Lender + Clone> ExactSizeIterator for Iter<L> {
115	fn len(&self) -> usize {	11✔
116	self.remaining	11✔
117	}
118	}
119
120	pub type Lender<'a, S> = lender::Take<<S as SequentialLabeling>::Lender<'a>>;
121	pub type IntoIterator<'a, S> = Iter<<S as SequentialLabeling>::Lender<'a>>;
122	}
123
124	/// Ready-made implementation for the random-access case.
125	///
126	/// This implementation uses the [`iter_from`](SequentialLabeling::iter_from) at
127	/// regular intervals. To use it, you have to implement the trait by specifying
128	/// the associated types `Lender` and `IntoIterator` using the [`ra::Lender`]
129	/// and [`ra::IntoIterator`] types aliases, and then return a [`ra::Iter`]
130	/// structure.
131	///
132	/// # Examples
133	///
134	/// The code for [`BvGraph`](crate::graphs::bvgraph::random_access::BvGraph) is
135	/// ```ignore
136	/// impl<F: RandomAccessDecoderFactory> SplitLabeling for BvGraph<F>
137	/// where
138	/// for<'a> <F as RandomAccessDecoderFactory>::Decoder<'a>: Send + Sync,
139	/// {
140	/// type SplitLender<'a> = split::ra::Lender<'a, BvGraph<F>> where Self: 'a;
141	/// type IntoIterator<'a> = split::ra::IntoIterator<'a, BvGraph<F>> where Self: 'a;
142	///
143	/// fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
144	/// split::ra::Iter::new(self, how_many)
145	/// }
146	/// }
147	/// ```
148	pub mod ra {
149	use crate::prelude::{RandomAccessLabeling, SequentialLabeling};
150
151	pub struct Iter<'a, R: RandomAccessLabeling> {
152	labeling: &'a R,
153	nodes_per_iter: usize,
154	how_many: usize,
155	i: usize,
156	}
157
158	impl<'a, R: RandomAccessLabeling> Iter<'a, R> {
159	pub fn new(labeling: &'a R, how_many: usize) -> Self {	12✔
160	let nodes_per_iter = labeling.num_nodes().div_ceil(how_many);	60✔
161	Self {
162	labeling,
163	nodes_per_iter,
164	how_many,
165	i: 0,
166	}
167	}
168	}
169
170	impl<'a, R: RandomAccessLabeling> Iterator for Iter<'a, R> {
171	type Item = Lender<'a, R>;
172
173	fn next(&mut self) -> Option<Self::Item> {	77✔
174	use lender::Lender;
175
176	if self.i == self.how_many {	77✔
177	return None;	1✔
178	}
179	self.i += 1;	×
180	Some(
181	self.labeling	×
UNCOV 182	.iter_from((self.i - 1) * self.nodes_per_iter)	×
UNCOV 183	.take(self.nodes_per_iter),	×
184	)
185	}
186	}
187
188	impl<R: RandomAccessLabeling> ExactSizeIterator for Iter<'_, R> {
189	fn len(&self) -> usize {	22✔
190	self.how_many - self.i	22✔
191	}
192	}
193
194	pub type Lender<'a, R> = lender::Take<<R as SequentialLabeling>::Lender<'a>>;
195	pub type IntoIterator<'a, R> = Iter<'a, R>;
196	}

vigna / webgraph-rs / 18008720487

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