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/examples/custom_codes_bfs.rs

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

use std::collections::VecDeque;
use std::path::PathBuf;

use anyhow::Result;
use clap::Parser;
use dsi_bitstream::{dispatch::factory::CodesReaderFactoryHelper, prelude::*};
use dsi_progress_logger::prelude::*;
use epserde::deser::{Deserialize, Flags, MemCase};
use mmap_rs::MmapFlags;
use sux::{bits::BitVec, traits::IndexedSeq};
use webgraph::prelude::*;

#[derive(Parser, Debug)]
#[command(about = "Reads a graph encoded with custom codes and does a BFS on it.", long_about = None)]
struct Args {
    // The basename of the graph.
    basename: PathBuf,

    /// The number of nodes in the graph
    num_nodes: usize,

    /// The number of arcs in the graph
    num_arcs: u64,

    #[clap(long, default_value = "false")]
    /// Whether to use mmap for the graph, otherwise it will be load in memory
    mmap: bool,
}

/// This is the factory that we can plug in BVGraph to read the custom codes
pub struct CustomDecoderFactory<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> {
    pub factory: F,
    // The [`MemCase`]` here is needed to memory-map the offsets, otherwise
    // it can just be `OFF`
    pub offsets: MemCase<OFF>,
    _marker: std::marker::PhantomData<E>,
}

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> CustomDecoderFactory<E, F, OFF> {
    pub fn new(factory: F, offsets: MemCase<OFF>) -> Self {
        Self {
            factory,
            offsets,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> RandomAccessDecoderFactory
    for CustomDecoderFactory<E, F, OFF>
where
    for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
{
    type Decoder<'a>
        = CustomDecoder<E, F::CodesReader<'a>>
    where
        Self: 'a;
    fn new_decoder(&self, node: usize) -> anyhow::Result<Self::Decoder<'_>> {
        let mut code_reader = self.factory.new_reader();
        code_reader.set_bit_pos(self.offsets.uncase().get(node) as u64)?;
        Ok(CustomDecoder::new(code_reader))
    }
}

impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> SequentialDecoderFactory
    for CustomDecoderFactory<E, F, OFF>
where
    for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
{
    type Decoder<'a>
        = CustomDecoder<E, F::CodesReader<'a>>
    where
        Self: 'a;
    fn new_decoder(&self) -> anyhow::Result<Self::Decoder<'_>> {
        Ok(CustomDecoder::new(self.factory.new_reader()))
    }
}

/// This is the decoder that will decode our custom codes and give them to BVGraph
pub struct CustomDecoder<E: Endianness, R: CodesRead<E>> {
    pub decoder: R,
    _marker: std::marker::PhantomData<E>,
}

impl<E: Endianness, R: CodesRead<E>> CustomDecoder<E, R> {
    pub fn new(decoder: R) -> Self {
        Self {
            decoder,
            _marker: std::marker::PhantomData,
        }
    }

    pub fn into_inner(self) -> R {
        self.decoder
    }
}

impl<E: Endianness, R: CodesRead<E>> Decode for CustomDecoder<E, R> {
    #[inline(always)]
    fn read_outdegree(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_reference_offset(&mut self) -> u64 {
        self.decoder.read_unary().unwrap()
    }
    #[inline(always)]
    fn read_block_count(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_block(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_interval_count(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_interval_start(&mut self) -> u64 {
        self.decoder.read_pi(2).unwrap()
    }
    #[inline(always)]
    fn read_interval_len(&mut self) -> u64 {
        self.decoder.read_gamma().unwrap()
    }
    #[inline(always)]
    fn read_first_residual(&mut self) -> u64 {
        self.decoder.read_pi(3).unwrap()
    }
    #[inline(always)]
    fn read_residual(&mut self) -> u64 {
        self.decoder.read_pi(2).unwrap()
    }
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let _ = env_logger::builder()
        .filter_level(log::LevelFilter::Debug)
        .try_init();

    let args = Args::parse();

    let offsets =
        unsafe { EF::load_mmap(args.basename.with_extension(EF_EXTENSION), Flags::default()) }?;

    if args.mmap {
        let graph = BvGraph::new(
            CustomDecoderFactory::<LE, _, _>::new(
                // This is MMap
                MmapHelper::mmap(
                    args.basename.with_extension(GRAPH_EXTENSION),
                    MmapFlags::empty(),
                )?,
                offsets,
            ),
            args.num_nodes,
            args.num_arcs,
            7, // default
            4, // default
        );

        visit(graph)?;
    } else {
        let graph = BvGraph::new(
            CustomDecoderFactory::new(
                MemoryFactory::<LE, _>::new_mmap(
                    args.basename.with_extension(GRAPH_EXTENSION),
                    MemoryFlags::default(),
                )?,
                offsets,
            ),
            args.num_nodes,
            args.num_arcs,
            7, // default
            4, // default
        );

        visit(graph)?;
    }

    Ok(())
}

fn visit(graph: impl RandomAccessGraph) -> Result<()> {
    let num_nodes = graph.num_nodes();
    let mut seen = BitVec::new(num_nodes);
    let mut queue = VecDeque::new();

    let mut pl = ProgressLogger::default();
    pl.display_memory(true)
        .item_name("node")
        .local_speed(true)
        .expected_updates(Some(num_nodes));
    pl.start("Visiting graph...");

    for start in 0..num_nodes {
        if seen[start] {
            continue;
        }
        queue.push_back(start as _);
        seen.set(start, true);

        while !queue.is_empty() {
            pl.light_update();
            let current_node = queue.pop_front().unwrap();
            for succ in graph.successors(current_node) {
                if !seen[succ] {
                    queue.push_back(succ);
                    seen.set(succ as _, true);
                }
            }
        }
    }

    pl.done();

    Ok(())
}

1	/*
2	* SPDX-FileCopyrightText: 2025 Tommaso Fontana
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use std::collections::VecDeque;
8	use std::path::PathBuf;
9
10	use anyhow::Result;
11	use clap::Parser;
12	use dsi_bitstream::{dispatch::factory::CodesReaderFactoryHelper, prelude::*};
13	use dsi_progress_logger::prelude::*;
14	use epserde::deser::{Deserialize, Flags, MemCase};
15	use mmap_rs::MmapFlags;
16	use sux::{bits::BitVec, traits::IndexedSeq};
17	use webgraph::prelude::*;
18
19	#[derive(Parser, Debug)]
20	#[command(about = "Reads a graph encoded with custom codes and does a BFS on it.", long_about = None)]
21	struct Args {
22	// The basename of the graph.
23	basename: PathBuf,
24
25	/// The number of nodes in the graph
26	num_nodes: usize,
27
28	/// The number of arcs in the graph
29	num_arcs: u64,
30
31	#[clap(long, default_value = "false")]
32	/// Whether to use mmap for the graph, otherwise it will be load in memory
33	mmap: bool,
34	}
35
36	/// This is the factory that we can plug in BVGraph to read the custom codes
37	pub struct CustomDecoderFactory<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> {
38	pub factory: F,
39	// The [`MemCase`]` here is needed to memory-map the offsets, otherwise
40	// it can just be `OFF`
41	pub offsets: MemCase<OFF>,
42	_marker: std::marker::PhantomData<E>,
43	}
44
45	impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> CustomDecoderFactory<E, F, OFF> {
UNCOV 46	pub fn new(factory: F, offsets: MemCase<OFF>) -> Self {	×
47	Self {
48	factory,
49	offsets,
50	_marker: std::marker::PhantomData,
51	}
52	}
53	}
54
55	impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> RandomAccessDecoderFactory
56	for CustomDecoderFactory<E, F, OFF>
57	where
58	for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
59	{
60	type Decoder<'a>
61	= CustomDecoder<E, F::CodesReader<'a>>
62	where
63	Self: 'a;
UNCOV 64	fn new_decoder(&self, node: usize) -> anyhow::Result<Self::Decoder<'_>> {	×
UNCOV 65	let mut code_reader = self.factory.new_reader();	×
UNCOV 66	code_reader.set_bit_pos(self.offsets.uncase().get(node) as u64)?;	×
UNCOV 67	Ok(CustomDecoder::new(code_reader))	×
68	}
69	}
70
71	impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> SequentialDecoderFactory
72	for CustomDecoderFactory<E, F, OFF>
73	where
74	for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
75	{
76	type Decoder<'a>
77	= CustomDecoder<E, F::CodesReader<'a>>
78	where
79	Self: 'a;
UNCOV 80	fn new_decoder(&self) -> anyhow::Result<Self::Decoder<'_>> {	×
UNCOV 81	Ok(CustomDecoder::new(self.factory.new_reader()))	×
82	}
83	}
84
85	/// This is the decoder that will decode our custom codes and give them to BVGraph
86	pub struct CustomDecoder<E: Endianness, R: CodesRead<E>> {
87	pub decoder: R,
88	_marker: std::marker::PhantomData<E>,
89	}
90
91	impl<E: Endianness, R: CodesRead<E>> CustomDecoder<E, R> {
UNCOV 92	pub fn new(decoder: R) -> Self {	×
93	Self {
94	decoder,
95	_marker: std::marker::PhantomData,
96	}
97	}
98
UNCOV 99	pub fn into_inner(self) -> R {	×
UNCOV 100	self.decoder	×
101	}
102	}
103
104	impl<E: Endianness, R: CodesRead<E>> Decode for CustomDecoder<E, R> {
105	#[inline(always)]
UNCOV 106	fn read_outdegree(&mut self) -> u64 {	×
107	self.decoder.read_gamma().unwrap()	×
108	}
109	#[inline(always)]
UNCOV 110	fn read_reference_offset(&mut self) -> u64 {	×
UNCOV 111	self.decoder.read_unary().unwrap()	×
112	}
113	#[inline(always)]
114	fn read_block_count(&mut self) -> u64 {	×
115	self.decoder.read_gamma().unwrap()	×
116	}
117	#[inline(always)]
UNCOV 118	fn read_block(&mut self) -> u64 {	×
UNCOV 119	self.decoder.read_gamma().unwrap()	×
120	}
121	#[inline(always)]
122	fn read_interval_count(&mut self) -> u64 {	×
UNCOV 123	self.decoder.read_gamma().unwrap()	×
124	}
125	#[inline(always)]
126	fn read_interval_start(&mut self) -> u64 {	×
UNCOV 127	self.decoder.read_pi(2).unwrap()	×
128	}
129	#[inline(always)]
130	fn read_interval_len(&mut self) -> u64 {	×
UNCOV 131	self.decoder.read_gamma().unwrap()	×
132	}
133	#[inline(always)]
134	fn read_first_residual(&mut self) -> u64 {	×
UNCOV 135	self.decoder.read_pi(3).unwrap()	×
136	}
137	#[inline(always)]
138	fn read_residual(&mut self) -> u64 {	×
UNCOV 139	self.decoder.read_pi(2).unwrap()	×
140	}
141	}
142
143	fn main() -> Result<(), Box<dyn std::error::Error>> {
144	let _ = env_logger::builder()
145	.filter_level(log::LevelFilter::Debug)
146	.try_init();
147
148	let args = Args::parse();
149
150	let offsets =
151	unsafe { EF::load_mmap(args.basename.with_extension(EF_EXTENSION), Flags::default()) }?;
152
153	if args.mmap {
154	let graph = BvGraph::new(
155	CustomDecoderFactory::<LE, _, _>::new(
156	// This is MMap
157	MmapHelper::mmap(
158	args.basename.with_extension(GRAPH_EXTENSION),
159	MmapFlags::empty(),
160	)?,
161	offsets,
162	),
163	args.num_nodes,
164	args.num_arcs,
165	7, // default
166	4, // default
167	);
168
169	visit(graph)?;
170	} else {
171	let graph = BvGraph::new(
172	CustomDecoderFactory::new(
173	MemoryFactory::<LE, _>::new_mmap(
174	args.basename.with_extension(GRAPH_EXTENSION),
175	MemoryFlags::default(),
176	)?,
177	offsets,
178	),
179	args.num_nodes,
180	args.num_arcs,
181	7, // default
182	4, // default
183	);
184
185	visit(graph)?;
186	}
187
188	Ok(())
189	}
190
UNCOV 191	fn visit(graph: impl RandomAccessGraph) -> Result<()> {	×
UNCOV 192	let num_nodes = graph.num_nodes();	×
UNCOV 193	let mut seen = BitVec::new(num_nodes);	×
UNCOV 194	let mut queue = VecDeque::new();	×
195
UNCOV 196	let mut pl = ProgressLogger::default();	×
UNCOV 197	pl.display_memory(true)	×
198	.item_name("node")
199	.local_speed(true)
UNCOV 200	.expected_updates(Some(num_nodes));	×
UNCOV 201	pl.start("Visiting graph...");	×
202
UNCOV 203	for start in 0..num_nodes {	×
UNCOV 204	if seen[start] {	×
205	continue;	×
206	}
207	queue.push_back(start as _);	×
208	seen.set(start, true);	×
209
210	while !queue.is_empty() {	×
211	pl.light_update();	×
UNCOV 212	let current_node = queue.pop_front().unwrap();	×
UNCOV 213	for succ in graph.successors(current_node) {	×
214	if !seen[succ] {	×
215	queue.push_back(succ);	×
UNCOV 216	seen.set(succ as _, true);	×
217	}
218	}
219	}
220	}
221
222	pl.done();	×
223
224	Ok(())	×
225	}

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