18429616840

Committed 11 Oct 2025 12:50PM UTC coverage: 47.997% (+0.03%) from 47.965%

Build # 18429616840

Build Type

push

github

Committed by

zommiommy

Commit Message

Unlabeled methods

Run Details

104 of 226 new or added lines in 9 files covered. (46.02%)

21 existing lines in 4 files now uncovered.

4001 of 8336 relevant lines covered (48.0%)

21818046.88 hits per line

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

66.67

/webgraph/src/utils/batch_codec/mod.rs

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

use anyhow::Result;

use super::ArcMmapHelper;
use dsi_bitstream::prelude::*;
use rdst::*;
use std::fs::File;
use std::io::BufWriter;
use std::path::Path;

pub mod gaps;
pub mod grouped_gaps;

/// The recommended default batch codec for unlabelled batches.
pub type DefaultBatchCodec = grouped_gaps::GroupedGapsCodec;

pub type BitWriter = BufBitWriter<NE, WordAdapter<usize, BufWriter<File>>>;
pub type BitReader = BufBitReader<NE, MemWordReader<u32, ArcMmapHelper<u32>>>;

/// A trait for encoding and decoding batches of sorted triples.
pub trait BatchCodec: Send + Sync {
    /// The label type of the triples to encode and decode.
    /// While the bounds are not really necessary, in all the practical cases
    /// we need them.
    type Label: Copy + Send + Sync + 'static;
    //// The type returned by `decode_batch`, the iterator of which yields the
    //// decoded triples in sorted order.
    ///
    /// The type `IntoIter` has to be `Send + Sync + Clone` because most often we want
    /// to use them in [`SortPairs`](crate::utils::sort_pairs::SortPairs) and
    /// then in [`ArcListGraph`](crate::graphs::arc_list_graph::ArcListGraph)
    /// which require them.
    type DecodedBatch: IntoIterator<
        Item = (usize, usize, Self::Label),
        IntoIter: Send + Sync + Clone,
    >;

    /// Given a batch of sorted triples, encodes them to disk and returns the number of bits written.
    fn encode_sorted_batch(
        &self,
        path: impl AsRef<Path>,
        batch: &[(usize, usize, Self::Label)],
    ) -> Result<usize>;

    /// Given a batch of triples, encodes them to disk and returns the number of bits written.
    /// The batch needs a mutable reference to allow the coded to sort-in-place if needed.
    fn encode_batch(
        &self,
        path: impl AsRef<Path>,
        batch: &mut [(usize, usize, Self::Label)],
    ) -> Result<usize>;

    /// Decodes a batch of triples from disk.
    /// The returned type's iterator yields the serialized triples in sorted order.
    fn decode_batch(&self, path: impl AsRef<Path>) -> Result<Self::DecodedBatch>;
}

/// Convenience alias to extract the iterator type of the decoded batch from a [`BatchCodec`].
pub type CodecIter<C> = <<C as BatchCodec>::DecodedBatch as IntoIterator>::IntoIter;

/// An arc expressed as a pair of nodes and the associated label.
///
/// Equality and order are defined only (lexicographically) on the pair of
/// nodes.
///
/// Since we use this to sort a batch of `(usize, usize, L)` triples, in order to
/// safely transmute between the two types, Triple HAS TO be `repr(transparent)`
/// of the same tuple type.
///
/// We use this to implement `RadixKey` for sorting batches of triples
/// using `rdst`.
#[derive(Clone, Copy, Debug)]
#[repr(transparent)]
pub struct Triple<L>((usize, usize, L));

impl<L> Triple<L> {
    /// Converts a mutable batch of `(usize, usize, L)` triples into a mutable slice of `Triple<L>`.
    ///
    /// This is safe because `Triple` is `repr(transparent)` of the same tuple type.
    pub fn cast_batch_mut(batch: &mut [(usize, usize, L)]) -> &mut [Triple<L>] {
        unsafe { std::mem::transmute(batch) }
    }
    /// Converts a batch of `(usize, usize, L)` triples into a slice of `Triple<L>`.
    ///
    /// This is safe because `Triple` is `repr(transparent)` of the same tuple type.
    pub fn cast_batch(batch: &[(usize, usize, L)]) -> &[Triple<L>] {
        unsafe { std::mem::transmute(batch) }
    }
}

impl<L> RadixKey for Triple<L> {
    const LEVELS: usize = 16;

    fn get_level(&self, level: usize) -> u8 {
        (if level < 8 {
            self.0 .1 >> ((level % 8) * 8)
        } else {
            self.0 .0 >> ((level % 8) * 8)
        }) as u8
    }
}

impl<L> PartialEq for Triple<L> {
    fn eq(&self, other: &Self) -> bool {
        self.0 .0 == other.0 .0 && self.0 .1 == other.0 .1
    }
}

impl<L> Eq for Triple<L> {}

impl<L> PartialOrd for Triple<L> {
    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
        Some(self.0 .0.cmp(&other.0 .0).then(self.0 .1.cmp(&other.0 .1)))
    }
}

impl<L> Ord for Triple<L> {
    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
        self.0 .0.cmp(&other.0 .0).then(self.0 .1.cmp(&other.0 .1))
    }
}

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 anyhow::Result;
8
9	use super::ArcMmapHelper;
10	use dsi_bitstream::prelude::*;
11	use rdst::*;
12	use std::fs::File;
13	use std::io::BufWriter;
14	use std::path::Path;
15
16	pub mod gaps;
17	pub mod grouped_gaps;
18
19	/// The recommended default batch codec for unlabelled batches.
20	pub type DefaultBatchCodec = grouped_gaps::GroupedGapsCodec;
21
22	pub type BitWriter = BufBitWriter<NE, WordAdapter<usize, BufWriter<File>>>;
23	pub type BitReader = BufBitReader<NE, MemWordReader<u32, ArcMmapHelper<u32>>>;
24
25	/// A trait for encoding and decoding batches of sorted triples.
26	pub trait BatchCodec: Send + Sync {
27	/// The label type of the triples to encode and decode.
28	/// While the bounds are not really necessary, in all the practical cases
29	/// we need them.
30	type Label: Copy + Send + Sync + 'static;
31	//// The type returned by `decode_batch`, the iterator of which yields the
32	//// decoded triples in sorted order.
33	///
34	/// The type `IntoIter` has to be `Send + Sync + Clone` because most often we want
35	/// to use them in [`SortPairs`](crate::utils::sort_pairs::SortPairs) and
36	/// then in [`ArcListGraph`](crate::graphs::arc_list_graph::ArcListGraph)
37	/// which require them.
38	type DecodedBatch: IntoIterator<
39	Item = (usize, usize, Self::Label),
40	IntoIter: Send + Sync + Clone,
41	>;
42
43	/// Given a batch of sorted triples, encodes them to disk and returns the number of bits written.
44	fn encode_sorted_batch(
45	&self,
46	path: impl AsRef<Path>,
47	batch: &[(usize, usize, Self::Label)],
48	) -> Result<usize>;
49
50	/// Given a batch of triples, encodes them to disk and returns the number of bits written.
51	/// The batch needs a mutable reference to allow the coded to sort-in-place if needed.
52	fn encode_batch(
53	&self,
54	path: impl AsRef<Path>,
55	batch: &mut [(usize, usize, Self::Label)],
56	) -> Result<usize>;
57
58	/// Decodes a batch of triples from disk.
59	/// The returned type's iterator yields the serialized triples in sorted order.
60	fn decode_batch(&self, path: impl AsRef<Path>) -> Result<Self::DecodedBatch>;
61	}
62
63	/// Convenience alias to extract the iterator type of the decoded batch from a [`BatchCodec`].
64	pub type CodecIter<C> = <<C as BatchCodec>::DecodedBatch as IntoIterator>::IntoIter;
65
66	/// An arc expressed as a pair of nodes and the associated label.
67	///
68	/// Equality and order are defined only (lexicographically) on the pair of
69	/// nodes.
70	///
71	/// Since we use this to sort a batch of `(usize, usize, L)` triples, in order to
72	/// safely transmute between the two types, Triple HAS TO be `repr(transparent)`
73	/// of the same tuple type.
74	///
75	/// We use this to implement `RadixKey` for sorting batches of triples
76	/// using `rdst`.
77	#[derive(Clone, Copy, Debug)]
78	#[repr(transparent)]
79	pub struct Triple<L>((usize, usize, L));
80
81	impl<L> Triple<L> {
82	/// Converts a mutable batch of `(usize, usize, L)` triples into a mutable slice of `Triple<L>`.
83	///
84	/// This is safe because `Triple` is `repr(transparent)` of the same tuple type.
85	pub fn cast_batch_mut(batch: &mut [(usize, usize, L)]) -> &mut [Triple<L>] {	440✔
86	unsafe { std::mem::transmute(batch) }	440✔
87	}
88	/// Converts a batch of `(usize, usize, L)` triples into a slice of `Triple<L>`.
89	///
90	/// This is safe because `Triple` is `repr(transparent)` of the same tuple type.
91	pub fn cast_batch(batch: &[(usize, usize, L)]) -> &[Triple<L>] {	440✔
92	unsafe { std::mem::transmute(batch) }	880✔
93	}
94	}
95
96	impl<L> RadixKey for Triple<L> {
97	const LEVELS: usize = 16;
98
99	fn get_level(&self, level: usize) -> u8 {	846,982,804✔
100	(if level < 8 {	846,982,804✔
101	self.0 .1 >> ((level % 8) * 8)	422,118,344✔
102	} else {
103	self.0 .0 >> ((level % 8) * 8)	424,864,460✔
NEW 104	}) as u8	×
105	}
106	}
107
108	impl<L> PartialEq for Triple<L> {
NEW 109	fn eq(&self, other: &Self) -> bool {	×
NEW 110	self.0 .0 == other.0 .0 && self.0 .1 == other.0 .1	×
111	}
112	}
113
114	impl<L> Eq for Triple<L> {}
115
116	impl<L> PartialOrd for Triple<L> {
117	fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {	38,585,535✔
118	Some(self.0 .0.cmp(&other.0 .0).then(self.0 .1.cmp(&other.0 .1)))	231,513,210✔
119	}
120	}
121
122	impl<L> Ord for Triple<L> {
NEW 123	fn cmp(&self, other: &Self) -> core::cmp::Ordering {	×
NEW 124	self.0 .0.cmp(&other.0 .0).then(self.0 .1.cmp(&other.0 .1))	×
125	}
126	}

vigna / webgraph-rs / 18429616840

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