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

83.59

/webgraph/src/fuzz/bvcomp_and_read.rs

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

use crate::prelude::*;
use arbitrary::Arbitrary;
use dsi_bitstream::prelude::*;
use lender::prelude::*;
use sux::prelude::*;
use sux::traits::IndexedSeq;

#[derive(Clone, Debug, arbitrary::Arbitrary)]
pub enum CodeFuzz {
    Unary,
    Gamma,
    Delta,
    Zeta3,
}
impl From<CodeFuzz> for Codes {
    fn from(value: CodeFuzz) -> Self {
        match value {
            CodeFuzz::Unary => Codes::Unary,
            CodeFuzz::Gamma => Codes::Gamma,
            CodeFuzz::Delta => Codes::Delta,
            CodeFuzz::Zeta3 => Codes::Zeta { k: 3 },
        }
    }
}

#[derive(Clone, Debug, arbitrary::Arbitrary)]
pub struct CompFlagsFuzz {
    pub outdegrees: CodeFuzz,
    pub references: CodeFuzz,
    pub blocks: CodeFuzz,
    pub intervals: CodeFuzz,
    pub residuals: CodeFuzz,
    pub min_interval_length: u8,
    pub compression_window: u8,
    pub max_ref_count: u8,
}

impl From<CompFlagsFuzz> for CompFlags {
    fn from(value: CompFlagsFuzz) -> Self {
        CompFlags {
            outdegrees: value.outdegrees.into(),
            references: value.references.into(),
            blocks: value.blocks.into(),
            intervals: value.intervals.into(),
            residuals: value.residuals.into(),
            min_interval_length: value.min_interval_length as usize,
            compression_window: value.compression_window as usize,
            max_ref_count: value.max_ref_count as usize,
        }
    }
}

#[derive(Arbitrary, Debug)]
pub struct FuzzCase {
    pub compression_flags: CompFlagsFuzz,
    pub edges: Vec<(u8, u8)>,
}

pub fn harness(data: FuzzCase) {
    let comp_flags = data.compression_flags.into();
    // convert the edges to a graph
    let mut edges = data
        .edges
        .into_iter()
        .map(|(src, dst)| (src as usize, dst as usize))
        .collect::<Vec<_>>();
    edges.sort();
    let graph = BTreeGraph::from_arcs(edges);
    // Compress in big endian
    let mut codes_data_be: Vec<u64> = Vec::new();
    {
        let bit_writer = <BufBitWriter<BE, _>>::new(MemWordWriterVec::new(&mut codes_data_be));
        let codes_writer = <DynCodesEncoder<BE, _>>::new(bit_writer, &comp_flags).unwrap();
        let mut bvcomp = BvComp::new(
            codes_writer,
            comp_flags.compression_window,
            comp_flags.max_ref_count,
            comp_flags.min_interval_length,
            0,
        );
        bvcomp.extend(graph.iter()).unwrap();
        bvcomp.flush().unwrap();
    }
    // Compress in little endian
    let mut codes_data_le: Vec<u64> = Vec::new();
    {
        let bit_writer = <BufBitWriter<LE, _>>::new(MemWordWriterVec::new(&mut codes_data_le));
        let codes_writer = <DynCodesEncoder<LE, _>>::new(bit_writer, &comp_flags).unwrap();
        let mut bvcomp = BvComp::new(
            codes_writer,
            comp_flags.compression_window,
            comp_flags.max_ref_count,
            comp_flags.min_interval_length,
            0,
        );
        bvcomp.extend(graph.iter()).unwrap();
        bvcomp.flush().unwrap();
    }
    assert_eq!(codes_data_be.len(), codes_data_le.len());

    // convert to u32 for faster reader
    let data_be: &[u32] = unsafe {
        core::slice::from_raw_parts(
            codes_data_be.as_ptr() as *const u32,
            codes_data_be.len() * (core::mem::size_of::<u64>() / core::mem::size_of::<u32>()),
        )
    };
    let data_le: &[u32] = unsafe {
        core::slice::from_raw_parts(
            codes_data_le.as_ptr() as *const u32,
            codes_data_le.len() * (core::mem::size_of::<u64>() / core::mem::size_of::<u32>()),
        )
    };
    // create code reader builders
    let codes_reader_be = <DynCodesDecoderFactory<BE, _, _>>::new(
        MemoryFactory::from_data(data_be),
        <EmptyDict<usize, usize>>::default().into(),
        comp_flags,
    )
    .unwrap();
    let codes_reader_le = <DynCodesDecoderFactory<LE, _, _>>::new(
        MemoryFactory::from_data(data_le),
        <EmptyDict<usize, usize>>::default().into(),
        comp_flags,
    )
    .unwrap();

    // test sequential graphs and build the offsets
    let mut efb = EliasFanoBuilder::new(
        graph.num_nodes() + 1,
        (data_be.len() + 1) * 8 * core::mem::size_of::<u32>(),
    );
    let mut offsets = Vec::with_capacity(graph.num_nodes() + 1);
    offsets.push(0);
    efb.push(0);

    // create seq graphs
    let seq_graph_be = BvGraphSeq::new(
        codes_reader_be,
        graph.num_nodes(),
        Some(graph.num_arcs()),
        comp_flags.compression_window,
        comp_flags.min_interval_length,
    );
    let seq_graph_le = BvGraphSeq::new(
        codes_reader_le,
        graph.num_nodes(),
        Some(graph.num_arcs()),
        comp_flags.compression_window,
        comp_flags.min_interval_length,
    );
    // create seq iters
    let mut seq_iter = graph.iter();
    let mut seq_iter_be = seq_graph_be.iter();
    let mut seq_iter_le = seq_graph_le.iter();
    assert_eq!(seq_iter_be.bit_pos().unwrap(), 0);
    assert_eq!(seq_iter_le.bit_pos().unwrap(), 0);
    // verify that they are the same and build the offsets
    for _ in 0..graph.num_nodes() {
        let (node_id, succ) = seq_iter.next().unwrap();
        let (node_id_be, succ_be) = seq_iter_be.next().unwrap();
        let (node_id_le, succ_le) = seq_iter_le.next().unwrap();
        let succ_be = succ_be.collect::<Vec<_>>();
        let succ_le = succ_le.collect::<Vec<_>>();
        let succ = succ.into_iter().collect::<Vec<_>>();
        assert_eq!(node_id, node_id_be);
        assert_eq!(node_id_be, node_id_le);
        assert_eq!(
            seq_iter_be.bit_pos().unwrap(),
            seq_iter_le.bit_pos().unwrap()
        );
        assert_eq!(succ_be, succ_le);
        assert_eq!(succ, succ_be);
        offsets.push(seq_iter_be.bit_pos().unwrap());
        efb.push(seq_iter_be.bit_pos().unwrap() as usize);
    }

    let mut seq_iter_be = seq_graph_be.offset_deg_iter();
    let mut seq_iter_le = seq_graph_le.offset_deg_iter();
    // verify that they are the same and build the offsets
    for node_id in 0..graph.num_nodes() {
        let deg = graph.successors(node_id).count();
        let (offset_be, deg_be) = seq_iter_be.next().unwrap();
        let (offset_le, deg_le) = seq_iter_le.next().unwrap();
        assert_eq!(deg, deg_be);
        assert_eq!(deg_be, deg_le);
        assert_eq!(offset_be, offset_le);
    }
    // build elias-fano
    let ef = efb.build();
    let ef: EF = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _, 12, 4>::new) };

    // verify that elias-fano has the right values
    assert_eq!(ef.len(), offsets.len());
    for (i, offset) in offsets.iter().enumerate() {
        assert_eq!(ef.get(i) as u64, *offset);
    }

    // create code reader builders
    let codes_reader_be = <DynCodesDecoderFactory<BE, _, _>>::new(
        MemoryFactory::from_data(data_be),
        ef.clone().into(),
        comp_flags,
    )
    .unwrap();
    let codes_reader_le = <DynCodesDecoderFactory<LE, _, _>>::new(
        MemoryFactory::from_data(data_le),
        ef.clone().into(),
        comp_flags,
    )
    .unwrap();

    // Creates the two bvgraphs
    let graph_be: BvGraph<_> = BvGraph::new(
        codes_reader_be,
        graph.num_nodes(),
        graph.num_arcs(),
        comp_flags.compression_window,
        comp_flags.min_interval_length,
    );
    let graph_le: BvGraph<_> = BvGraph::new(
        codes_reader_le,
        graph.num_nodes(),
        graph.num_arcs(),
        comp_flags.compression_window,
        comp_flags.min_interval_length,
    );

    // Compare the three graphs
    assert_eq!(graph.num_arcs(), graph_be.num_arcs());
    assert_eq!(graph.num_arcs(), graph_le.num_arcs());

    assert_eq!(graph.num_nodes(), graph_be.num_nodes());
    assert_eq!(graph.num_nodes(), graph_le.num_nodes());

    for node_id in 0..graph.num_nodes() {
        assert_eq!(graph.outdegree(node_id), graph_be.outdegree(node_id));
        assert_eq!(graph.outdegree(node_id), graph_le.outdegree(node_id));

        let true_successors = graph.successors(node_id).collect::<Vec<_>>();
        let be_successors = graph_be.successors(node_id).collect::<Vec<_>>();
        let le_successors = graph_le.successors(node_id).collect::<Vec<_>>();

        assert_eq!(true_successors, be_successors);
        assert_eq!(true_successors, le_successors);
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use crate::prelude::*;
8	use arbitrary::Arbitrary;
9	use dsi_bitstream::prelude::*;
10	use lender::prelude::*;
11	use sux::prelude::*;
12	use sux::traits::IndexedSeq;
13
14	#[derive(Clone, Debug, arbitrary::Arbitrary)]
15	pub enum CodeFuzz {
16	Unary,
17	Gamma,
18	Delta,
19	Zeta3,
20	}
21	impl From<CodeFuzz> for Codes {
22	fn from(value: CodeFuzz) -> Self {	17,380✔
23	match value {	17,380✔
24	CodeFuzz::Unary => Codes::Unary,	6,560✔
25	CodeFuzz::Gamma => Codes::Gamma,	1,984✔
26	CodeFuzz::Delta => Codes::Delta,	4,516✔
27	CodeFuzz::Zeta3 => Codes::Zeta { k: 3 },
28	}
29	}
30	}
31
32	#[derive(Clone, Debug, arbitrary::Arbitrary)]
33	pub struct CompFlagsFuzz {
34	pub outdegrees: CodeFuzz,
35	pub references: CodeFuzz,
36	pub blocks: CodeFuzz,
37	pub intervals: CodeFuzz,
38	pub residuals: CodeFuzz,
39	pub min_interval_length: u8,
40	pub compression_window: u8,
41	pub max_ref_count: u8,
42	}
43
44	impl From<CompFlagsFuzz> for CompFlags {
45	fn from(value: CompFlagsFuzz) -> Self {	3,476✔
46	CompFlags {
47	outdegrees: value.outdegrees.into(),	10,428✔
48	references: value.references.into(),	10,428✔
49	blocks: value.blocks.into(),	10,428✔
50	intervals: value.intervals.into(),	10,428✔
51	residuals: value.residuals.into(),	10,428✔
52	min_interval_length: value.min_interval_length as usize,	6,952✔
53	compression_window: value.compression_window as usize,	3,476✔
54	max_ref_count: value.max_ref_count as usize,	3,476✔
55	}
56	}
57	}
58
59	#[derive(Arbitrary, Debug)]
60	pub struct FuzzCase {
61	pub compression_flags: CompFlagsFuzz,
62	pub edges: Vec<(u8, u8)>,
63	}
64
65	pub fn harness(data: FuzzCase) {	3,476✔
66	let comp_flags = data.compression_flags.into();	10,428✔
67	// convert the edges to a graph
68	let mut edges = data	6,952✔
69	.edges	3,476✔
70	.into_iter()
71	.map(\|(src, dst)\| (src as usize, dst as usize))	9,556✔
72	.collect::<Vec<_>>();
73	edges.sort();	3,476✔
74	let graph = BTreeGraph::from_arcs(edges);	10,428✔
75	// Compress in big endian
76	let mut codes_data_be: Vec<u64> = Vec::new();	10,428✔
77	{
78	let bit_writer = <BufBitWriter<BE, _>>::new(MemWordWriterVec::new(&mut codes_data_be));	17,380✔
79	let codes_writer = <DynCodesEncoder<BE, _>>::new(bit_writer, &comp_flags).unwrap();	20,856✔
80	let mut bvcomp = BvComp::new(
81	codes_writer,	6,952✔
82	comp_flags.compression_window,	6,952✔
83	comp_flags.max_ref_count,	6,952✔
84	comp_flags.min_interval_length,	6,952✔
85	0,
86	);
87	bvcomp.extend(graph.iter()).unwrap();	20,856✔
88	bvcomp.flush().unwrap();	6,952✔
89	}
90	// Compress in little endian
91	let mut codes_data_le: Vec<u64> = Vec::new();	10,428✔
92	{
93	let bit_writer = <BufBitWriter<LE, _>>::new(MemWordWriterVec::new(&mut codes_data_le));	17,380✔
94	let codes_writer = <DynCodesEncoder<LE, _>>::new(bit_writer, &comp_flags).unwrap();	20,856✔
95	let mut bvcomp = BvComp::new(
96	codes_writer,	6,952✔
97	comp_flags.compression_window,	6,952✔
98	comp_flags.max_ref_count,	6,952✔
99	comp_flags.min_interval_length,	6,952✔
100	0,
101	);
102	bvcomp.extend(graph.iter()).unwrap();	20,856✔
103	bvcomp.flush().unwrap();	6,952✔
104	}
105	assert_eq!(codes_data_be.len(), codes_data_le.len());	17,380✔
106
107	// convert to u32 for faster reader
108	let data_be: &[u32] = unsafe {
109	core::slice::from_raw_parts(
110	codes_data_be.as_ptr() as *const u32,	6,952✔
111	codes_data_be.len() * (core::mem::size_of::<u64>() / core::mem::size_of::<u32>()),	10,428✔
112	)
113	};
114	let data_le: &[u32] = unsafe {
115	core::slice::from_raw_parts(
116	codes_data_le.as_ptr() as *const u32,	6,952✔
117	codes_data_le.len() * (core::mem::size_of::<u64>() / core::mem::size_of::<u32>()),	10,428✔
118	)
119	};
120	// create code reader builders
121	let codes_reader_be = <DynCodesDecoderFactory<BE, _, _>>::new(
122	MemoryFactory::from_data(data_be),	6,952✔
123	<EmptyDict<usize, usize>>::default().into(),	6,952✔
124	comp_flags,	3,476✔
125	)
126	.unwrap();
127	let codes_reader_le = <DynCodesDecoderFactory<LE, _, _>>::new(
128	MemoryFactory::from_data(data_le),	6,952✔
129	<EmptyDict<usize, usize>>::default().into(),	6,952✔
130	comp_flags,	3,476✔
131	)
132	.unwrap();
133
134	// test sequential graphs and build the offsets
135	let mut efb = EliasFanoBuilder::new(
136	graph.num_nodes() + 1,	3,476✔
137	(data_be.len() + 1) * 8 * core::mem::size_of::<u32>(),	3,476✔
138	);
139	let mut offsets = Vec::with_capacity(graph.num_nodes() + 1);	10,428✔
140	offsets.push(0);	6,952✔
141	efb.push(0);	6,952✔
142
143	// create seq graphs
144	let seq_graph_be = BvGraphSeq::new(
145	codes_reader_be,	3,476✔
146	graph.num_nodes(),	6,952✔
147	Some(graph.num_arcs()),	3,476✔
148	comp_flags.compression_window,	3,476✔
149	comp_flags.min_interval_length,	3,476✔
150	);
151	let seq_graph_le = BvGraphSeq::new(
152	codes_reader_le,	3,476✔
153	graph.num_nodes(),	6,952✔
154	Some(graph.num_arcs()),	3,476✔
155	comp_flags.compression_window,	3,476✔
156	comp_flags.min_interval_length,	3,476✔
157	);
158	// create seq iters
159	let mut seq_iter = graph.iter();	10,428✔
160	let mut seq_iter_be = seq_graph_be.iter();	10,428✔
161	let mut seq_iter_le = seq_graph_le.iter();	10,428✔
162	assert_eq!(seq_iter_be.bit_pos().unwrap(), 0);	13,904✔
163	assert_eq!(seq_iter_le.bit_pos().unwrap(), 0);	13,904✔
164	// verify that they are the same and build the offsets
165	for _ in 0..graph.num_nodes() {	6,952✔
166	let (node_id, succ) = seq_iter.next().unwrap();	1,168,928✔
167	let (node_id_be, succ_be) = seq_iter_be.next().unwrap();	1,168,928✔
168	let (node_id_le, succ_le) = seq_iter_le.next().unwrap();	1,168,928✔
169	let succ_be = succ_be.collect::<Vec<_>>();	876,696✔
170	let succ_le = succ_le.collect::<Vec<_>>();	876,696✔
171	let succ = succ.into_iter().collect::<Vec<_>>();	1,168,928✔
172	assert_eq!(node_id, node_id_be);	292,232✔
173	assert_eq!(node_id_be, node_id_le);	292,232✔
174	assert_eq!(	292,232✔
175	seq_iter_be.bit_pos().unwrap(),	876,696✔
176	seq_iter_le.bit_pos().unwrap()	876,696✔
177	);
178	assert_eq!(succ_be, succ_le);	292,232✔
179	assert_eq!(succ, succ_be);	292,232✔
180	offsets.push(seq_iter_be.bit_pos().unwrap());	292,232✔
UNCOV 181	efb.push(seq_iter_be.bit_pos().unwrap() as usize);	×
182	}
183
184	let mut seq_iter_be = seq_graph_be.offset_deg_iter();	3,476✔
UNCOV 185	let mut seq_iter_le = seq_graph_le.offset_deg_iter();	×
186	// verify that they are the same and build the offsets
187	for node_id in 0..graph.num_nodes() {	292,232✔
188	let deg = graph.successors(node_id).count();	1,461,160✔
189	let (offset_be, deg_be) = seq_iter_be.next().unwrap();	1,168,928✔
190	let (offset_le, deg_le) = seq_iter_le.next().unwrap();	1,168,928✔
191	assert_eq!(deg, deg_be);	292,232✔
192	assert_eq!(deg_be, deg_le);	292,232✔
193	assert_eq!(offset_be, offset_le);	292,232✔
194	}
195	// build elias-fano
196	let ef = efb.build();	3,476✔
UNCOV 197	let ef: EF = unsafe { ef.map_high_bits(SelectAdaptConst::<_, _, 12, 4>::new) };	×
198
199	// verify that elias-fano has the right values
UNCOV 200	assert_eq!(ef.len(), offsets.len());	×
201	for (i, offset) in offsets.iter().enumerate() {	598,368✔
202	assert_eq!(ef.get(i) as u64, *offset);	887,124✔
203	}
204
205	// create code reader builders
206	let codes_reader_be = <DynCodesDecoderFactory<BE, _, _>>::new(
207	MemoryFactory::from_data(data_be),	×
NEW 208	ef.clone().into(),	×
UNCOV 209	comp_flags,	×
210	)
211	.unwrap();
212	let codes_reader_le = <DynCodesDecoderFactory<LE, _, _>>::new(
213	MemoryFactory::from_data(data_le),	×
NEW 214	ef.clone().into(),	×
UNCOV 215	comp_flags,	×
216	)
217	.unwrap();
218
219	// Creates the two bvgraphs
220	let graph_be: BvGraph<_> = BvGraph::new(
221	codes_reader_be,	×
222	graph.num_nodes(),	×
223	graph.num_arcs(),	×
224	comp_flags.compression_window,	×
UNCOV 225	comp_flags.min_interval_length,	×
226	);
227	let graph_le: BvGraph<_> = BvGraph::new(
228	codes_reader_le,	×
229	graph.num_nodes(),	×
230	graph.num_arcs(),	×
231	comp_flags.compression_window,	×
UNCOV 232	comp_flags.min_interval_length,	×
233	);
234
235	// Compare the three graphs
UNCOV 236	assert_eq!(graph.num_arcs(), graph_be.num_arcs());	×
237	assert_eq!(graph.num_arcs(), graph_le.num_arcs());	17,380✔
238
239	assert_eq!(graph.num_nodes(), graph_be.num_nodes());	17,380✔
240	assert_eq!(graph.num_nodes(), graph_le.num_nodes());	17,380✔
241
242	for node_id in 0..graph.num_nodes() {	299,184✔
243	assert_eq!(graph.outdegree(node_id), graph_be.outdegree(node_id));	2,045,624✔
244	assert_eq!(graph.outdegree(node_id), graph_le.outdegree(node_id));	2,045,624✔
245
246	let true_successors = graph.successors(node_id).collect::<Vec<_>>();	1,461,160✔
247	let be_successors = graph_be.successors(node_id).collect::<Vec<_>>();	1,461,160✔
248	let le_successors = graph_le.successors(node_id).collect::<Vec<_>>();	1,461,160✔
249
250	assert_eq!(true_successors, be_successors);	292,232✔
251	assert_eq!(true_successors, le_successors);	292,232✔
252	}
253	}

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