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

0.0

/webgraph/src/labels/bitstream.rs

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

//! Basic skeleton for a simple bitstream-based implementation of a labeling.
//!
//! Labels are stored as a bitstream, and are deserialized using a [custom
//! deserializer](BitDeserializer). An [`IndexedSeq`] provides pointers into the
//! bitstream. Both sequential and random access are provided.
//!
//! See the examples for a complete implementation based on memory mapping.

use crate::prelude::{BitDeserializer, Offsets};
use crate::prelude::{NodeLabelsLender, RandomAccessLabeling, SequentialLabeling};
use dsi_bitstream::traits::{BitRead, BitSeek, Endianness};
use epserde::deser::MemCase;
use lender::*;
use sux::traits::IndexedSeq;

/// A basic supplier trait.
///
/// This trait is used to supply readers on the bitstream containing the labels.
/// It will probably be replaced by a more general supplier trait in the future.
pub trait Supply {
    type Item<'a>
    where
        Self: 'a;
    fn request(&self) -> Self::Item<'_>;
}

/// A labeling based on a bitstream of labels and an indexed sequence of offsets.
pub struct BitStreamLabeling<E: Endianness, S: Supply, D, O: Offsets>
where
    for<'a> S::Item<'a>: BitRead<E> + BitSeek,
    for<'a> D: BitDeserializer<E, S::Item<'a>>,
{
    reader_supplier: S,
    bit_deser: D,
    offsets: MemCase<O>,
    _marker: std::marker::PhantomData<E>,
}

impl<E: Endianness, S: Supply, D, O: Offsets> BitStreamLabeling<E, S, D, O>
where
    for<'a> S::Item<'a>: BitRead<E> + BitSeek,
    for<'a> D: BitDeserializer<E, S::Item<'a>>,
{
    /// Creates a new labeling using the given suppliers and offsets.
    ///
    /// # Arguments
    ///
    /// * `reader_supplier`: A supplier of readers on the bitstream containing
    ///   the labels.
    ///
    /// * `bit_deser_supplier`: A supplier of deserializers for the labels.
    ///
    /// * `offsets`: An indexed sequence of offsets into the bitstream.
    pub fn new(reader_supplier: S, bit_deser: D, offsets: MemCase<O>) -> Self {
        Self {
            reader_supplier,
            bit_deser,
            offsets,
            _marker: std::marker::PhantomData,
        }
    }
}

pub struct Iter<'a, 'b, E, BR, D, O: Offsets> {
    reader: BR,
    bit_deser: &'a D,
    offsets: &'b MemCase<O>,
    next_node: usize,
    num_nodes: usize,
    _marker: std::marker::PhantomData<E>,
}

impl<'succ, E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>, O: Offsets>
    NodeLabelsLender<'succ> for Iter<'_, '_, E, BR, D, O>
{
    type Label = D::DeserType;
    type IntoIterator = SeqLabels<'succ, E, BR, D>;
}

impl<'succ, E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>, O: Offsets>
    Lending<'succ> for Iter<'_, '_, E, BR, D, O>
{
    type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
}

impl<E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>, O: Offsets> Lender
    for Iter<'_, '_, E, BR, D, O>
{
    #[inline(always)]
    fn next(&mut self) -> Option<Lend<'_, Self>> {
        if self.next_node >= self.num_nodes {
            return None;
        }
        self.reader
            .set_bit_pos(self.offsets.uncase().get(self.next_node) as u64)
            .unwrap();
        let res = (
            self.next_node,
            SeqLabels {
                reader: &mut self.reader,
                bit_deser: self.bit_deser,
                end_pos: self.offsets.uncase().get(self.next_node + 1) as u64,
                _marker: std::marker::PhantomData,
            },
        );
        self.next_node += 1;
        Some(res)
    }
}

pub struct SeqLabels<'a, E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>> {
    reader: &'a mut BR,
    bit_deser: &'a D,
    end_pos: u64,
    _marker: std::marker::PhantomData<E>,
}

impl<E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>> Iterator
    for SeqLabels<'_, E, BR, D>
{
    type Item = D::DeserType;

    fn next(&mut self) -> Option<Self::Item> {
        if self.reader.bit_pos().unwrap() >= self.end_pos {
            None
        } else {
            Some(self.bit_deser.deserialize(self.reader).unwrap())
        }
    }
}

impl<L, E: Endianness, S: Supply, D, O: Offsets> SequentialLabeling
    for BitStreamLabeling<E, S, D, O>
where
    for<'a> S::Item<'a>: BitRead<E> + BitSeek,
    for<'a> D: BitDeserializer<E, S::Item<'a>, DeserType = L>,
{
    type Label = L;
    type Lender<'node>
        = Iter<'node, 'node, E, S::Item<'node>, D, O>
    where
        Self: 'node;

    fn num_nodes(&self) -> usize {
        self.offsets.uncase().len() - 1
    }

    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
        Iter {
            offsets: &self.offsets,
            reader: self.reader_supplier.request(),
            bit_deser: &self.bit_deser,
            next_node: from,
            num_nodes: self.num_nodes(),
            _marker: std::marker::PhantomData,
        }
    }
}

// TODO: avoid duplicate implementation for labels

pub struct RanLabels<'a, E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>> {
    reader: BR,
    deserializer: &'a D,
    end_pos: u64,
    _marker: std::marker::PhantomData<E>,
}

impl<E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>> Iterator
    for RanLabels<'_, E, BR, D>
{
    type Item = <D as BitDeserializer<E, BR>>::DeserType;

    fn next(&mut self) -> Option<Self::Item> {
        if self.reader.bit_pos().unwrap() >= self.end_pos {
            None
        } else {
            self.deserializer.deserialize(&mut self.reader).ok()
        }
    }
}

impl<L, E: Endianness, S: Supply, D, O: Offsets> RandomAccessLabeling
    for BitStreamLabeling<E, S, D, O>
where
    for<'a> S::Item<'a>: BitRead<E> + BitSeek,
    for<'a> D: BitDeserializer<E, S::Item<'a>, DeserType = L>,
{
    type Labels<'succ>
        = RanLabels<'succ, E, S::Item<'succ>, D>
    where
        Self: 'succ;

    fn num_arcs(&self) -> u64 {
        todo!();
    }

    fn labels(&self, node_id: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {
        let mut reader = self.reader_supplier.request();
        reader
            .set_bit_pos(self.offsets.uncase().get(node_id) as u64)
            .unwrap();
        RanLabels {
            reader,
            deserializer: &self.bit_deser,
            end_pos: self.offsets.uncase().get(node_id + 1) as u64,
            _marker: std::marker::PhantomData,
        }
    }

    fn outdegree(&self, node_id: usize) -> usize {
        self.labels(node_id).count()
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	//! Basic skeleton for a simple bitstream-based implementation of a labeling.
9	//!
10	//! Labels are stored as a bitstream, and are deserialized using a [custom
11	//! deserializer](BitDeserializer). An [`IndexedSeq`] provides pointers into the
12	//! bitstream. Both sequential and random access are provided.
13	//!
14	//! See the examples for a complete implementation based on memory mapping.
15
16	use crate::prelude::{BitDeserializer, Offsets};
17	use crate::prelude::{NodeLabelsLender, RandomAccessLabeling, SequentialLabeling};
18	use dsi_bitstream::traits::{BitRead, BitSeek, Endianness};
19	use epserde::deser::MemCase;
20	use lender::*;
21	use sux::traits::IndexedSeq;
22
23	/// A basic supplier trait.
24	///
25	/// This trait is used to supply readers on the bitstream containing the labels.
26	/// It will probably be replaced by a more general supplier trait in the future.
27	pub trait Supply {
28	type Item<'a>
29	where
30	Self: 'a;
31	fn request(&self) -> Self::Item<'_>;
32	}
33
34	/// A labeling based on a bitstream of labels and an indexed sequence of offsets.
35	pub struct BitStreamLabeling<E: Endianness, S: Supply, D, O: Offsets>
36	where
37	for<'a> S::Item<'a>: BitRead<E> + BitSeek,
38	for<'a> D: BitDeserializer<E, S::Item<'a>>,
39	{
40	reader_supplier: S,
41	bit_deser: D,
42	offsets: MemCase<O>,
43	_marker: std::marker::PhantomData<E>,
44	}
45
46	impl<E: Endianness, S: Supply, D, O: Offsets> BitStreamLabeling<E, S, D, O>
47	where
48	for<'a> S::Item<'a>: BitRead<E> + BitSeek,
49	for<'a> D: BitDeserializer<E, S::Item<'a>>,
50	{
51	/// Creates a new labeling using the given suppliers and offsets.
52	///
53	/// # Arguments
54	///
55	/// * `reader_supplier`: A supplier of readers on the bitstream containing
56	/// the labels.
57	///
58	/// * `bit_deser_supplier`: A supplier of deserializers for the labels.
59	///
60	/// * `offsets`: An indexed sequence of offsets into the bitstream.
61	pub fn new(reader_supplier: S, bit_deser: D, offsets: MemCase<O>) -> Self {	×
62	Self {
63	reader_supplier,
64	bit_deser,
65	offsets,
66	_marker: std::marker::PhantomData,
67	}
68	}
69	}
70
71	pub struct Iter<'a, 'b, E, BR, D, O: Offsets> {
72	reader: BR,
73	bit_deser: &'a D,
74	offsets: &'b MemCase<O>,
75	next_node: usize,
76	num_nodes: usize,
77	_marker: std::marker::PhantomData<E>,
78	}
79
80	impl<'succ, E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>, O: Offsets>
81	NodeLabelsLender<'succ> for Iter<'_, '_, E, BR, D, O>
82	{
83	type Label = D::DeserType;
84	type IntoIterator = SeqLabels<'succ, E, BR, D>;
85	}
86
87	impl<'succ, E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>, O: Offsets>
88	Lending<'succ> for Iter<'_, '_, E, BR, D, O>
89	{
90	type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
91	}
92
93	impl<E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>, O: Offsets> Lender
94	for Iter<'_, '_, E, BR, D, O>
95	{
96	#[inline(always)]
UNCOV 97	fn next(&mut self) -> Option<Lend<'_, Self>> {	×
UNCOV 98	if self.next_node >= self.num_nodes {	×
UNCOV 99	return None;	×
100	}
UNCOV 101	self.reader	×
UNCOV 102	.set_bit_pos(self.offsets.uncase().get(self.next_node) as u64)	×
103	.unwrap();
UNCOV 104	let res = (	×
UNCOV 105	self.next_node,	×
UNCOV 106	SeqLabels {	×
UNCOV 107	reader: &mut self.reader,	×
UNCOV 108	bit_deser: self.bit_deser,	×
UNCOV 109	end_pos: self.offsets.uncase().get(self.next_node + 1) as u64,	×
UNCOV 110	_marker: std::marker::PhantomData,	×
111	},
112	);
113	self.next_node += 1;	×
UNCOV 114	Some(res)	×
115	}
116	}
117
118	pub struct SeqLabels<'a, E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>> {
119	reader: &'a mut BR,
120	bit_deser: &'a D,
121	end_pos: u64,
122	_marker: std::marker::PhantomData<E>,
123	}
124
125	impl<E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>> Iterator
126	for SeqLabels<'_, E, BR, D>
127	{
128	type Item = D::DeserType;
129
UNCOV 130	fn next(&mut self) -> Option<Self::Item> {	×
UNCOV 131	if self.reader.bit_pos().unwrap() >= self.end_pos {	×
UNCOV 132	None	×
133	} else {
UNCOV 134	Some(self.bit_deser.deserialize(self.reader).unwrap())	×
135	}
136	}
137	}
138
139	impl<L, E: Endianness, S: Supply, D, O: Offsets> SequentialLabeling
140	for BitStreamLabeling<E, S, D, O>
141	where
142	for<'a> S::Item<'a>: BitRead<E> + BitSeek,
143	for<'a> D: BitDeserializer<E, S::Item<'a>, DeserType = L>,
144	{
145	type Label = L;
146	type Lender<'node>
147	= Iter<'node, 'node, E, S::Item<'node>, D, O>
148	where
149	Self: 'node;
150
UNCOV 151	fn num_nodes(&self) -> usize {	×
UNCOV 152	self.offsets.uncase().len() - 1	×
153	}
154
UNCOV 155	fn iter_from(&self, from: usize) -> Self::Lender<'_> {	×
156	Iter {
UNCOV 157	offsets: &self.offsets,	×
UNCOV 158	reader: self.reader_supplier.request(),	×
UNCOV 159	bit_deser: &self.bit_deser,	×
160	next_node: from,
UNCOV 161	num_nodes: self.num_nodes(),	×
162	_marker: std::marker::PhantomData,
163	}
164	}
165	}
166
167	// TODO: avoid duplicate implementation for labels
168
169	pub struct RanLabels<'a, E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>> {
170	reader: BR,
171	deserializer: &'a D,
172	end_pos: u64,
173	_marker: std::marker::PhantomData<E>,
174	}
175
176	impl<E: Endianness, BR: BitRead<E> + BitSeek, D: BitDeserializer<E, BR>> Iterator
177	for RanLabels<'_, E, BR, D>
178	{
179	type Item = <D as BitDeserializer<E, BR>>::DeserType;
180
UNCOV 181	fn next(&mut self) -> Option<Self::Item> {	×
UNCOV 182	if self.reader.bit_pos().unwrap() >= self.end_pos {	×
UNCOV 183	None	×
184	} else {
UNCOV 185	self.deserializer.deserialize(&mut self.reader).ok()	×
186	}
187	}
188	}
189
190	impl<L, E: Endianness, S: Supply, D, O: Offsets> RandomAccessLabeling
191	for BitStreamLabeling<E, S, D, O>
192	where
193	for<'a> S::Item<'a>: BitRead<E> + BitSeek,
194	for<'a> D: BitDeserializer<E, S::Item<'a>, DeserType = L>,
195	{
196	type Labels<'succ>
197	= RanLabels<'succ, E, S::Item<'succ>, D>
198	where
199	Self: 'succ;
200
201	fn num_arcs(&self) -> u64 {	×
202	todo!();
203	}
204
UNCOV 205	fn labels(&self, node_id: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {	×
UNCOV 206	let mut reader = self.reader_supplier.request();	×
UNCOV 207	reader	×
UNCOV 208	.set_bit_pos(self.offsets.uncase().get(node_id) as u64)	×
209	.unwrap();
210	RanLabels {
211	reader,
UNCOV 212	deserializer: &self.bit_deser,	×
UNCOV 213	end_pos: self.offsets.uncase().get(node_id + 1) as u64,	×
214	_marker: std::marker::PhantomData,
215	}
216	}
217
UNCOV 218	fn outdegree(&self, node_id: usize) -> usize {	×
UNCOV 219	self.labels(node_id).count()	×
220	}
221	}

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