19076069272

Committed 04 Nov 2025 04:42PM UTC coverage: 61.785% (-0.2%) from 61.976%

Build # 19076069272

Build Type

push

github

Committed by

vigna

Commit Message

Fixed doctests

Run Details

5143 of 8324 relevant lines covered (61.79%)

30278823.63 hits per line

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

53.62

/webgraph/src/graphs/bvgraph/load.rs

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

use super::*;
use crate::prelude::*;
use anyhow::{Context, Result};
use dsi_bitstream::prelude::*;
use dsi_bitstream::{dispatch::code_consts, dispatch::factory::CodesReaderFactoryHelper};
use epserde::deser::Owned;
use epserde::prelude::*;
use sealed::sealed;
use std::{
    io::BufReader,
    path::{Path, PathBuf},
};

/// Sequential or random access.
#[doc(hidden)]
#[sealed]
pub trait Access: 'static {}

#[derive(Debug, Clone)]
pub struct Sequential {}
#[sealed]
impl Access for Sequential {}

#[derive(Debug, Clone)]
pub struct Random {}
#[sealed]
impl Access for Random {}

/// [`Static`] or [`Dynamic`] dispatch.
#[sealed]
pub trait Dispatch: 'static {}

/// Static dispatch.
///
/// You have to specify all codes used of the graph. The defaults
/// are the same as the default parameters of the Java version.
#[derive(Debug, Clone)]
pub struct Static<
    const OUTDEGREES: usize = { code_consts::GAMMA },
    const REFERENCES: usize = { code_consts::UNARY },
    const BLOCKS: usize = { code_consts::GAMMA },
    const INTERVALS: usize = { code_consts::GAMMA },
    const RESIDUALS: usize = { code_consts::ZETA3 },
> {}

#[sealed]
impl<
        const OUTDEGREES: usize,
        const REFERENCES: usize,
        const BLOCKS: usize,
        const INTERVALS: usize,
        const RESIDUALS: usize,
    > Dispatch for Static<OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
{
}

/// Dynamic dispatch.
///
/// Parameters are retrieved from the graph properties.
#[derive(Debug, Clone)]
pub struct Dynamic {}

#[sealed]
impl Dispatch for Dynamic {}

/// Load mode.
///
/// The load mode is the way the graph data is accessed. Each load mode has
/// a corresponding strategy to access the graph and the offsets.
///
/// You can set both modes with [`LoadConfig::mode`], or set them separately with
/// [`LoadConfig::graph_mode`] and [`LoadConfig::offsets_mode`].
#[sealed]
pub trait LoadMode: 'static {
    type Factory<E: Endianness>;

    fn new_factory<E: Endianness, P: AsRef<Path>>(
        graph: P,
        flags: codecs::MemoryFlags,
    ) -> Result<Self::Factory<E>>;

    type Offsets: Offsets;

    fn load_offsets<P: AsRef<Path>>(
        offsets: P,
        flags: MemoryFlags,
    ) -> Result<MemCase<Self::Offsets>>;
}

/// A type alias for a buffered reader that reads from a memory buffer a `u32` at a time.
pub type MemBufReader<'a, E> = BufBitReader<E, MemWordReader<u32, &'a [u32]>>;
/// A type alias for a buffered reader that reads from a file buffer a `u32` at a time.
pub type FileBufReader<E> = BufBitReader<E, WordAdapter<u32, BufReader<std::fs::File>>>;
/// A type alias for the [`CodesReaderFactory`] associated with a [`LoadMode`].
///
/// This type can be used in client methods that abstract over endianness to
/// impose the necessary trait bounds on the factory associated with the load
/// mode: one has just to write, for example, for the [`Mmap`] load mode:
/// ```ignore
/// LoadModeFactory<E, Mmap>: CodesReaderFactoryHelper<E>
/// ```
///
/// Additional trait bounds on the [`CodesRead`] associated with the factory
/// can be imposed by using the [`LoadModeCodesReader`] type alias.
pub type LoadModeFactory<E, LM> = <LM as LoadMode>::Factory<E>;
/// A type alias for the code reader returned by the [`CodesReaderFactory`]
/// associated with a [`LoadMode`].
///
/// This type can be used in client methods that abstract over endianness to
/// impose bounds on the code reader associated to the factory associated with
/// the load mode, usually in conjunction with [`LoadModeFactory`]. For example,
/// for the [`Mmap`] load mode:
/// ```ignore
/// LoadModeFactory<E, Mmap>: CodesReaderFactoryHelper<E>
/// LoadModeCodesReader<'a, E, Mmap>: BitSeek
/// ```
pub type LoadModeCodesReader<'a, E, LM> =
    <LoadModeFactory<E, LM> as CodesReaderFactory<E>>::CodesReader<'a>;

/// The graph is read from a file; offsets are fully deserialized in memory.
///
/// Note that you must guarantee that the graph file is padded with enough
/// zeroes so that it can be read one `u32` at a time.
#[derive(Debug, Clone)]
pub struct File {}
#[sealed]
impl LoadMode for File {
    type Factory<E: Endianness> = FileFactory<E>;
    type Offsets = Owned<EF>;

    fn new_factory<E: Endianness, P: AsRef<Path>>(
        graph: P,
        _flags: MemoryFlags,
    ) -> Result<Self::Factory<E>> {
        FileFactory::<E>::new(graph)
    }

    fn load_offsets<P: AsRef<Path>>(
        offsets: P,
        _flags: MemoryFlags,
    ) -> Result<MemCase<Self::Offsets>> {
        let path = offsets.as_ref();
        unsafe {
            EF::load_full(path)
                .with_context(|| format!("Cannot load Elias-Fano pointer list {}", path.display()))
                .map(Into::into)
        }
    }
}

/// The graph and offsets are memory mapped.
///
/// This is the default mode. You can [set memory-mapping flags](LoadConfig::flags).
#[derive(Debug, Clone)]
pub struct Mmap {}
#[sealed]
impl LoadMode for Mmap {
    type Factory<E: Endianness> = MmapHelper<u32>;
    type Offsets = EF;

    fn new_factory<E: Endianness, P: AsRef<Path>>(
        graph: P,
        flags: MemoryFlags,
    ) -> Result<Self::Factory<E>> {
        MmapHelper::mmap(graph, flags.into())
    }

    fn load_offsets<P: AsRef<Path>>(
        offsets: P,
        flags: MemoryFlags,
    ) -> Result<MemCase<Self::Offsets>> {
        let path = offsets.as_ref();
        unsafe {
            EF::mmap(path, flags.into())
                .with_context(|| format!("Cannot map Elias-Fano pointer list {}", path.display()))
        }
    }
}

/// The graph and offsets are loaded into allocated memory.
#[derive(Debug, Clone)]
pub struct LoadMem {}
#[sealed]
impl LoadMode for LoadMem {
    type Factory<E: Endianness> = MemoryFactory<E, Box<[u32]>>;
    type Offsets = EF;

    fn new_factory<E: Endianness, P: AsRef<Path>>(
        graph: P,
        _flags: MemoryFlags,
    ) -> Result<Self::Factory<E>> {
        MemoryFactory::<E, _>::new_mem(graph)
    }

    fn load_offsets<P: AsRef<Path>>(
        offsets: P,
        _flags: MemoryFlags,
    ) -> Result<MemCase<Self::Offsets>> {
        let path = offsets.as_ref();
        unsafe {
            EF::load_mem(path)
                .with_context(|| format!("Cannot load Elias-Fano pointer list {}", path.display()))
        }
    }
}

/// The graph and offsets are loaded into memory obtained via `mmap()`.
///
/// You can [set memory-mapping flags](LoadConfig::flags).
#[derive(Debug, Clone)]
pub struct LoadMmap {}
#[sealed]
impl LoadMode for LoadMmap {
    type Factory<E: Endianness> = MemoryFactory<E, MmapHelper<u32>>;
    type Offsets = EF;

    fn new_factory<E: Endianness, P: AsRef<Path>>(
        graph: P,
        flags: MemoryFlags,
    ) -> Result<Self::Factory<E>> {
        MemoryFactory::<E, _>::new_mmap(graph, flags)
    }

    fn load_offsets<P: AsRef<Path>>(
        offsets: P,
        flags: MemoryFlags,
    ) -> Result<MemCase<Self::Offsets>> {
        let path = offsets.as_ref();
        unsafe {
            EF::load_mmap(path, flags.into())
                .with_context(|| format!("Cannot load Elias-Fano pointer list {}", path.display()))
        }
    }
}

/// A load configuration for a [`BvGraph`]/[`BvGraphSeq`].
///
/// A basic configuration is returned by
/// [`BvGraph::with_basename`]/[`BvGraphSeq::with_basename`]. The configuration
/// can then be customized using the methods of this struct.
#[derive(Debug, Clone)]
pub struct LoadConfig<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode> {
    pub(crate) basename: PathBuf,
    pub(crate) graph_load_flags: MemoryFlags,
    pub(crate) offsets_load_flags: MemoryFlags,
    pub(crate) _marker: std::marker::PhantomData<(E, A, D, GLM, OLM)>,
}

impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
    LoadConfig<E, A, D, GLM, OLM>
{
    /// Set the endianness of the graph and offsets file.
    pub fn endianness<E2: Endianness>(self) -> LoadConfig<E2, A, D, GLM, OLM>
    where
        GLM: LoadMode,
        OLM: LoadMode,
    {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: self.graph_load_flags,
            offsets_load_flags: self.offsets_load_flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
    LoadConfig<E, A, D, GLM, OLM>
{
    /// Choose between [`Static`] and [`Dynamic`] dispatch.
    pub fn dispatch<D2: Dispatch>(self) -> LoadConfig<E, A, D2, GLM, OLM> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: self.graph_load_flags,
            offsets_load_flags: self.offsets_load_flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
    LoadConfig<E, A, D, GLM, OLM>
{
    /// Choose the [`LoadMode`] for the graph and offsets.
    pub fn mode<LM: LoadMode>(self) -> LoadConfig<E, A, D, LM, LM> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: self.graph_load_flags,
            offsets_load_flags: self.offsets_load_flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, A: Access, D: Dispatch> LoadConfig<E, A, D, Mmap, Mmap> {
    /// Set flags for memory-mapping (both graph and offsets).
    pub fn flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, Mmap, Mmap> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: flags,
            offsets_load_flags: flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, A: Access, D: Dispatch> LoadConfig<E, A, D, LoadMmap, LoadMmap> {
    /// Set flags for memory obtained from `mmap()` (both graph and offsets).
    pub fn flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, LoadMmap, LoadMmap> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: flags,
            offsets_load_flags: flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
    LoadConfig<E, A, D, GLM, OLM>
{
    /// Choose the [`LoadMode`] for the graph only.
    pub fn graph_mode<NGLM: LoadMode>(self) -> LoadConfig<E, A, D, NGLM, OLM> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: self.graph_load_flags,
            offsets_load_flags: self.offsets_load_flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, A: Access, D: Dispatch, OLM: LoadMode> LoadConfig<E, A, D, Mmap, OLM> {
    /// Set flags for memory-mapping the graph.
    pub fn graph_flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, Mmap, OLM> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: flags,
            offsets_load_flags: self.offsets_load_flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, A: Access, D: Dispatch, OLM: LoadMode> LoadConfig<E, A, D, LoadMmap, OLM> {
    /// Set flags for memory obtained from `mmap()` for the graph.
    pub fn graph_flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, LoadMmap, OLM> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: flags,
            offsets_load_flags: self.offsets_load_flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, D: Dispatch, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Random, D, GLM, OLM> {
    /// Choose the [`LoadMode`] for the graph only.
    pub fn offsets_mode<NOLM: LoadMode>(self) -> LoadConfig<E, Random, D, GLM, NOLM> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: self.graph_load_flags,
            offsets_load_flags: self.offsets_load_flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, D: Dispatch, GLM: LoadMode> LoadConfig<E, Random, D, GLM, Mmap> {
    /// Set flags for memory-mapping the offsets.
    pub fn offsets_flags(self, flags: MemoryFlags) -> LoadConfig<E, Random, D, GLM, Mmap> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: self.graph_load_flags,
            offsets_load_flags: flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, D: Dispatch, GLM: LoadMode> LoadConfig<E, Random, D, GLM, LoadMmap> {
    /// Set flags for memory obtained from `mmap()` for the graph.
    pub fn offsets_flags(self, flags: MemoryFlags) -> LoadConfig<E, Random, D, GLM, LoadMmap> {
        LoadConfig {
            basename: self.basename,
            graph_load_flags: self.graph_load_flags,
            offsets_load_flags: flags,
            _marker: std::marker::PhantomData,
        }
    }
}

impl<E: Endianness, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Random, Dynamic, GLM, OLM> {
    /// Load a random-access graph with dynamic dispatch.
    pub fn load(
        mut self,
    ) -> anyhow::Result<BvGraph<DynCodesDecoderFactory<E, GLM::Factory<E>, OLM::Offsets>>>
    where
        <GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
        for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E> + BitSeek,
    {
        self.basename.set_extension(PROPERTIES_EXTENSION);
        let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)
            .with_context(|| {
                format!("Could not load properties file {}", self.basename.display())
            })?;
        self.basename.set_extension(GRAPH_EXTENSION);
        let factory = GLM::new_factory(&self.basename, self.graph_load_flags)
            .with_context(|| format!("Could not load graph file {}", self.basename.display()))?;
        self.basename.set_extension(EF_EXTENSION);
        let offsets = OLM::load_offsets(&self.basename, self.offsets_load_flags)
            .with_context(|| format!("Could not load offsets file {}", self.basename.display()))?;

        Ok(BvGraph::new(
            DynCodesDecoderFactory::new(factory, offsets, comp_flags)?,
            num_nodes,
            num_arcs,
            comp_flags.compression_window,
            comp_flags.min_interval_length,
        ))
    }
}

impl<E: Endianness, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Sequential, Dynamic, GLM, OLM> {
    /// Load a sequential graph with dynamic dispatch.
    pub fn load(
        mut self,
    ) -> anyhow::Result<
        BvGraphSeq<DynCodesDecoderFactory<E, GLM::Factory<E>, Owned<EmptyDict<usize, usize>>>>,
    >
    where
        <GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
        for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E>,
    {
        self.basename.set_extension(PROPERTIES_EXTENSION);
        let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;
        self.basename.set_extension(GRAPH_EXTENSION);
        let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;

        Ok(BvGraphSeq::new(
            DynCodesDecoderFactory::new(factory, EmptyDict::default().into(), comp_flags)?,
            num_nodes,
            Some(num_arcs),
            comp_flags.compression_window,
            comp_flags.min_interval_length,
        ))
    }
}

impl<
        E: Endianness,
        GLM: LoadMode,
        OLM: LoadMode,
        const OUTDEGREES: usize,
        const REFERENCES: usize,
        const BLOCKS: usize,
        const INTERVALS: usize,
        const RESIDUALS: usize,
    >
    LoadConfig<E, Random, Static<OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>, GLM, OLM>
{
    /// Load a random-access graph with static dispatch.
    pub fn load(
        mut self,
    ) -> anyhow::Result<
        BvGraph<
            ConstCodesDecoderFactory<
                E,
                GLM::Factory<E>,
                OLM::Offsets,
                OUTDEGREES,
                REFERENCES,
                BLOCKS,
                INTERVALS,
                RESIDUALS,
            >,
        >,
    >
    where
        <GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
        for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E> + BitSeek,
    {
        self.basename.set_extension(PROPERTIES_EXTENSION);
        let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;
        self.basename.set_extension(GRAPH_EXTENSION);
        let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;
        self.basename.set_extension(EF_EXTENSION);
        let offsets = OLM::load_offsets(&self.basename, self.offsets_load_flags)?;

        Ok(BvGraph::new(
            ConstCodesDecoderFactory::new(factory, offsets, comp_flags)?,
            num_nodes,
            num_arcs,
            comp_flags.compression_window,
            comp_flags.min_interval_length,
        ))
    }
}

impl<
        E: Endianness,
        GLM: LoadMode,
        OLM: LoadMode,
        const OUTDEGREES: usize,
        const REFERENCES: usize,
        const BLOCKS: usize,
        const INTERVALS: usize,
        const RESIDUALS: usize,
    >
    LoadConfig<
        E,
        Sequential,
        Static<OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>,
        GLM,
        OLM,
    >
{
    /// Load a sequential graph with static dispatch.
    pub fn load(
        mut self,
    ) -> anyhow::Result<
        BvGraphSeq<
            ConstCodesDecoderFactory<
                E,
                GLM::Factory<E>,
                Owned<EmptyDict<usize, usize>>,
                OUTDEGREES,
                REFERENCES,
                BLOCKS,
                INTERVALS,
                RESIDUALS,
            >,
        >,
    >
    where
        <GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
        for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E>,
    {
        self.basename.set_extension(PROPERTIES_EXTENSION);
        let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;
        self.basename.set_extension(GRAPH_EXTENSION);
        let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;

        Ok(BvGraphSeq::new(
            ConstCodesDecoderFactory::new(factory, EmptyDict::default().into(), comp_flags)?,
            num_nodes,
            Some(num_arcs),
            comp_flags.compression_window,
            comp_flags.min_interval_length,
        ))
    }
}

/// Read the .properties file and return the endianness
pub fn get_endianness<P: AsRef<Path>>(basename: P) -> Result<String> {
    let path = basename.as_ref().with_extension(PROPERTIES_EXTENSION);
    let f = std::fs::File::open(&path)
        .with_context(|| format!("Cannot open property file {}", path.display()))?;
    let map = java_properties::read(BufReader::new(f))
        .with_context(|| format!("cannot parse {} as a java properties file", path.display()))?;

    let endianness = map
        .get("endianness")
        .map(|x| x.to_string())
        .unwrap_or_else(|| BigEndian::NAME.to_string());

    Ok(endianness)
}

/// Read the .properties file and return the number of nodes, number of arcs and compression flags
/// for the graph. The endianness is checked against the expected one.
pub fn parse_properties<E: Endianness>(path: impl AsRef<Path>) -> Result<(usize, u64, CompFlags)> {
    let name = path.as_ref().display();
    let f =
        std::fs::File::open(&path).with_context(|| format!("Cannot open property file {name}"))?;
    let map = java_properties::read(BufReader::new(f))
        .with_context(|| format!("cannot parse {name} as a java properties file"))?;

    let num_nodes = map
        .get("nodes")
        .with_context(|| format!("Missing 'nodes' property in {name}"))?
        .parse::<usize>()
        .with_context(|| format!("Cannot parse 'nodes' as usize in {name}"))?;
    let num_arcs = map
        .get("arcs")
        .with_context(|| format!("Missing 'arcs' property in {name}"))?
        .parse::<u64>()
        .with_context(|| format!("Cannot parse arcs as usize in {name}"))?;

    let comp_flags = CompFlags::from_properties::<E>(&map)
        .with_context(|| format!("Cannot parse compression flags from {name}"))?;
    Ok((num_nodes, num_arcs, comp_flags))
}

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	use super::*;
9	use crate::prelude::*;
10	use anyhow::{Context, Result};
11	use dsi_bitstream::prelude::*;
12	use dsi_bitstream::{dispatch::code_consts, dispatch::factory::CodesReaderFactoryHelper};
13	use epserde::deser::Owned;
14	use epserde::prelude::*;
15	use sealed::sealed;
16	use std::{
17	io::BufReader,
18	path::{Path, PathBuf},
19	};
20
21	/// Sequential or random access.
22	#[doc(hidden)]
23	#[sealed]
24	pub trait Access: 'static {}
25
26	#[derive(Debug, Clone)]
27	pub struct Sequential {}
28	#[sealed]
29	impl Access for Sequential {}
30
31	#[derive(Debug, Clone)]
32	pub struct Random {}
33	#[sealed]
34	impl Access for Random {}
35
36	/// [`Static`] or [`Dynamic`] dispatch.
37	#[sealed]
38	pub trait Dispatch: 'static {}
39
40	/// Static dispatch.
41	///
42	/// You have to specify all codes used of the graph. The defaults
43	/// are the same as the default parameters of the Java version.
44	#[derive(Debug, Clone)]
45	pub struct Static<
46	const OUTDEGREES: usize = { code_consts::GAMMA },
47	const REFERENCES: usize = { code_consts::UNARY },
48	const BLOCKS: usize = { code_consts::GAMMA },
49	const INTERVALS: usize = { code_consts::GAMMA },
50	const RESIDUALS: usize = { code_consts::ZETA3 },
51	> {}
52
53	#[sealed]
54	impl<
55	const OUTDEGREES: usize,
56	const REFERENCES: usize,
57	const BLOCKS: usize,
58	const INTERVALS: usize,
59	const RESIDUALS: usize,
60	> Dispatch for Static<OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>
61	{
62	}
63
64	/// Dynamic dispatch.
65	///
66	/// Parameters are retrieved from the graph properties.
67	#[derive(Debug, Clone)]
68	pub struct Dynamic {}
69
70	#[sealed]
71	impl Dispatch for Dynamic {}
72
73	/// Load mode.
74	///
75	/// The load mode is the way the graph data is accessed. Each load mode has
76	/// a corresponding strategy to access the graph and the offsets.
77	///
78	/// You can set both modes with [`LoadConfig::mode`], or set them separately with
79	/// [`LoadConfig::graph_mode`] and [`LoadConfig::offsets_mode`].
80	#[sealed]
81	pub trait LoadMode: 'static {
82	type Factory<E: Endianness>;
83
84	fn new_factory<E: Endianness, P: AsRef<Path>>(
85	graph: P,
86	flags: codecs::MemoryFlags,
87	) -> Result<Self::Factory<E>>;
88
89	type Offsets: Offsets;
90
91	fn load_offsets<P: AsRef<Path>>(
92	offsets: P,
93	flags: MemoryFlags,
94	) -> Result<MemCase<Self::Offsets>>;
95	}
96
97	/// A type alias for a buffered reader that reads from a memory buffer a `u32` at a time.
98	pub type MemBufReader<'a, E> = BufBitReader<E, MemWordReader<u32, &'a [u32]>>;
99	/// A type alias for a buffered reader that reads from a file buffer a `u32` at a time.
100	pub type FileBufReader<E> = BufBitReader<E, WordAdapter<u32, BufReader<std::fs::File>>>;
101	/// A type alias for the [`CodesReaderFactory`] associated with a [`LoadMode`].
102	///
103	/// This type can be used in client methods that abstract over endianness to
104	/// impose the necessary trait bounds on the factory associated with the load
105	/// mode: one has just to write, for example, for the [`Mmap`] load mode:
106	/// ```ignore
107	/// LoadModeFactory<E, Mmap>: CodesReaderFactoryHelper<E>
108	/// ```
109	///
110	/// Additional trait bounds on the [`CodesRead`] associated with the factory
111	/// can be imposed by using the [`LoadModeCodesReader`] type alias.
112	pub type LoadModeFactory<E, LM> = <LM as LoadMode>::Factory<E>;
113	/// A type alias for the code reader returned by the [`CodesReaderFactory`]
114	/// associated with a [`LoadMode`].
115	///
116	/// This type can be used in client methods that abstract over endianness to
117	/// impose bounds on the code reader associated to the factory associated with
118	/// the load mode, usually in conjunction with [`LoadModeFactory`]. For example,
119	/// for the [`Mmap`] load mode:
120	/// ```ignore
121	/// LoadModeFactory<E, Mmap>: CodesReaderFactoryHelper<E>
122	/// LoadModeCodesReader<'a, E, Mmap>: BitSeek
123	/// ```
124	pub type LoadModeCodesReader<'a, E, LM> =
125	<LoadModeFactory<E, LM> as CodesReaderFactory<E>>::CodesReader<'a>;
126
127	/// The graph is read from a file; offsets are fully deserialized in memory.
128	///
129	/// Note that you must guarantee that the graph file is padded with enough
130	/// zeroes so that it can be read one `u32` at a time.
131	#[derive(Debug, Clone)]
132	pub struct File {}
133	#[sealed]
134	impl LoadMode for File {
135	type Factory<E: Endianness> = FileFactory<E>;
136	type Offsets = Owned<EF>;
137
138	fn new_factory<E: Endianness, P: AsRef<Path>>(	×
139	graph: P,
140	_flags: MemoryFlags,
141	) -> Result<Self::Factory<E>> {
142	FileFactory::<E>::new(graph)	×
143	}
144
145	fn load_offsets<P: AsRef<Path>>(	×
146	offsets: P,
147	_flags: MemoryFlags,
148	) -> Result<MemCase<Self::Offsets>> {
149	let path = offsets.as_ref();	×
150	unsafe {
151	EF::load_full(path)	×
152	.with_context(\|\| format!("Cannot load Elias-Fano pointer list {}", path.display()))	×
153	.map(Into::into)	×
154	}
155	}
156	}
157
158	/// The graph and offsets are memory mapped.
159	///
160	/// This is the default mode. You can [set memory-mapping flags](LoadConfig::flags).
161	#[derive(Debug, Clone)]
162	pub struct Mmap {}
163	#[sealed]
164	impl LoadMode for Mmap {
165	type Factory<E: Endianness> = MmapHelper<u32>;
166	type Offsets = EF;
167
168	fn new_factory<E: Endianness, P: AsRef<Path>>(	75✔
169	graph: P,
170	flags: MemoryFlags,
171	) -> Result<Self::Factory<E>> {
172	MmapHelper::mmap(graph, flags.into())	300✔
173	}
174
175	fn load_offsets<P: AsRef<Path>>(	36✔
176	offsets: P,
177	flags: MemoryFlags,
178	) -> Result<MemCase<Self::Offsets>> {
179	let path = offsets.as_ref();	108✔
180	unsafe {
181	EF::mmap(path, flags.into())	144✔
182	.with_context(\|\| format!("Cannot map Elias-Fano pointer list {}", path.display()))	36✔
183	}
184	}
185	}
186
187	/// The graph and offsets are loaded into allocated memory.
188	#[derive(Debug, Clone)]
189	pub struct LoadMem {}
190	#[sealed]
191	impl LoadMode for LoadMem {
192	type Factory<E: Endianness> = MemoryFactory<E, Box<[u32]>>;
193	type Offsets = EF;
194
195	fn new_factory<E: Endianness, P: AsRef<Path>>(	×
196	graph: P,
197	_flags: MemoryFlags,
198	) -> Result<Self::Factory<E>> {
199	MemoryFactory::<E, _>::new_mem(graph)	×
200	}
201
202	fn load_offsets<P: AsRef<Path>>(	×
203	offsets: P,
204	_flags: MemoryFlags,
205	) -> Result<MemCase<Self::Offsets>> {
206	let path = offsets.as_ref();	×
207	unsafe {
208	EF::load_mem(path)	×
209	.with_context(\|\| format!("Cannot load Elias-Fano pointer list {}", path.display()))	×
210	}
211	}
212	}
213
214	/// The graph and offsets are loaded into memory obtained via `mmap()`.
215	///
216	/// You can [set memory-mapping flags](LoadConfig::flags).
217	#[derive(Debug, Clone)]
218	pub struct LoadMmap {}
219	#[sealed]
220	impl LoadMode for LoadMmap {
221	type Factory<E: Endianness> = MemoryFactory<E, MmapHelper<u32>>;
222	type Offsets = EF;
223
224	fn new_factory<E: Endianness, P: AsRef<Path>>(	8✔
225	graph: P,
226	flags: MemoryFlags,
227	) -> Result<Self::Factory<E>> {
228	MemoryFactory::<E, _>::new_mmap(graph, flags)	24✔
229	}
230
231	fn load_offsets<P: AsRef<Path>>(	8✔
232	offsets: P,
233	flags: MemoryFlags,
234	) -> Result<MemCase<Self::Offsets>> {
235	let path = offsets.as_ref();	24✔
236	unsafe {
237	EF::load_mmap(path, flags.into())	32✔
238	.with_context(\|\| format!("Cannot load Elias-Fano pointer list {}", path.display()))	8✔
239	}
240	}
241	}
242
243	/// A load configuration for a [`BvGraph`]/[`BvGraphSeq`].
244	///
245	/// A basic configuration is returned by
246	/// [`BvGraph::with_basename`]/[`BvGraphSeq::with_basename`]. The configuration
247	/// can then be customized using the methods of this struct.
248	#[derive(Debug, Clone)]
249	pub struct LoadConfig<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode> {
250	pub(crate) basename: PathBuf,
251	pub(crate) graph_load_flags: MemoryFlags,
252	pub(crate) offsets_load_flags: MemoryFlags,
253	pub(crate) _marker: std::marker::PhantomData<(E, A, D, GLM, OLM)>,
254	}
255
256	impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
257	LoadConfig<E, A, D, GLM, OLM>
258	{
259	/// Set the endianness of the graph and offsets file.
260	pub fn endianness<E2: Endianness>(self) -> LoadConfig<E2, A, D, GLM, OLM>	70✔
261	where
262	GLM: LoadMode,
263	OLM: LoadMode,
264	{
265	LoadConfig {
266	basename: self.basename,	140✔
267	graph_load_flags: self.graph_load_flags,	140✔
268	offsets_load_flags: self.offsets_load_flags,	70✔
269	_marker: std::marker::PhantomData,
270	}
271	}
272	}
273
274	impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
275	LoadConfig<E, A, D, GLM, OLM>
276	{
277	/// Choose between [`Static`] and [`Dynamic`] dispatch.
278	pub fn dispatch<D2: Dispatch>(self) -> LoadConfig<E, A, D2, GLM, OLM> {	×
279	LoadConfig {
280	basename: self.basename,	×
281	graph_load_flags: self.graph_load_flags,	×
282	offsets_load_flags: self.offsets_load_flags,	×
283	_marker: std::marker::PhantomData,
284	}
285	}
286	}
287
288	impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
289	LoadConfig<E, A, D, GLM, OLM>
290	{
291	/// Choose the [`LoadMode`] for the graph and offsets.
292	pub fn mode<LM: LoadMode>(self) -> LoadConfig<E, A, D, LM, LM> {	8✔
293	LoadConfig {
294	basename: self.basename,	16✔
295	graph_load_flags: self.graph_load_flags,	16✔
296	offsets_load_flags: self.offsets_load_flags,	8✔
297	_marker: std::marker::PhantomData,
298	}
299	}
300	}
301
302	impl<E: Endianness, A: Access, D: Dispatch> LoadConfig<E, A, D, Mmap, Mmap> {
303	/// Set flags for memory-mapping (both graph and offsets).
304	pub fn flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, Mmap, Mmap> {	×
305	LoadConfig {
306	basename: self.basename,	×
307	graph_load_flags: flags,
308	offsets_load_flags: flags,
309	_marker: std::marker::PhantomData,
310	}
311	}
312	}
313
314	impl<E: Endianness, A: Access, D: Dispatch> LoadConfig<E, A, D, LoadMmap, LoadMmap> {
315	/// Set flags for memory obtained from `mmap()` (both graph and offsets).
316	pub fn flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, LoadMmap, LoadMmap> {	8✔
317	LoadConfig {
318	basename: self.basename,	16✔
319	graph_load_flags: flags,
320	offsets_load_flags: flags,
321	_marker: std::marker::PhantomData,
322	}
323	}
324	}
325
326	impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
327	LoadConfig<E, A, D, GLM, OLM>
328	{
329	/// Choose the [`LoadMode`] for the graph only.
330	pub fn graph_mode<NGLM: LoadMode>(self) -> LoadConfig<E, A, D, NGLM, OLM> {	×
331	LoadConfig {
332	basename: self.basename,	×
333	graph_load_flags: self.graph_load_flags,	×
334	offsets_load_flags: self.offsets_load_flags,	×
335	_marker: std::marker::PhantomData,
336	}
337	}
338	}
339
340	impl<E: Endianness, A: Access, D: Dispatch, OLM: LoadMode> LoadConfig<E, A, D, Mmap, OLM> {
341	/// Set flags for memory-mapping the graph.
342	pub fn graph_flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, Mmap, OLM> {	×
343	LoadConfig {
344	basename: self.basename,	×
345	graph_load_flags: flags,
346	offsets_load_flags: self.offsets_load_flags,	×
347	_marker: std::marker::PhantomData,
348	}
349	}
350	}
351
352	impl<E: Endianness, A: Access, D: Dispatch, OLM: LoadMode> LoadConfig<E, A, D, LoadMmap, OLM> {
353	/// Set flags for memory obtained from `mmap()` for the graph.
354	pub fn graph_flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, LoadMmap, OLM> {	×
355	LoadConfig {
356	basename: self.basename,	×
357	graph_load_flags: flags,
358	offsets_load_flags: self.offsets_load_flags,	×
359	_marker: std::marker::PhantomData,
360	}
361	}
362	}
363
364	impl<E: Endianness, D: Dispatch, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Random, D, GLM, OLM> {
365	/// Choose the [`LoadMode`] for the graph only.
366	pub fn offsets_mode<NOLM: LoadMode>(self) -> LoadConfig<E, Random, D, GLM, NOLM> {	×
367	LoadConfig {
368	basename: self.basename,	×
369	graph_load_flags: self.graph_load_flags,	×
370	offsets_load_flags: self.offsets_load_flags,	×
371	_marker: std::marker::PhantomData,
372	}
373	}
374	}
375
376	impl<E: Endianness, D: Dispatch, GLM: LoadMode> LoadConfig<E, Random, D, GLM, Mmap> {
377	/// Set flags for memory-mapping the offsets.
378	pub fn offsets_flags(self, flags: MemoryFlags) -> LoadConfig<E, Random, D, GLM, Mmap> {	×
379	LoadConfig {
380	basename: self.basename,	×
381	graph_load_flags: self.graph_load_flags,	×
382	offsets_load_flags: flags,
383	_marker: std::marker::PhantomData,
384	}
385	}
386	}
387
388	impl<E: Endianness, D: Dispatch, GLM: LoadMode> LoadConfig<E, Random, D, GLM, LoadMmap> {
389	/// Set flags for memory obtained from `mmap()` for the graph.
390	pub fn offsets_flags(self, flags: MemoryFlags) -> LoadConfig<E, Random, D, GLM, LoadMmap> {	×
391	LoadConfig {
392	basename: self.basename,	×
393	graph_load_flags: self.graph_load_flags,	×
394	offsets_load_flags: flags,
395	_marker: std::marker::PhantomData,
396	}
397	}
398	}
399
400	impl<E: Endianness, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Random, Dynamic, GLM, OLM> {
401	/// Load a random-access graph with dynamic dispatch.
402	pub fn load(	44✔
403	mut self,
404	) -> anyhow::Result<BvGraph<DynCodesDecoderFactory<E, GLM::Factory<E>, OLM::Offsets>>>
405	where
406	<GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
407	for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E> + BitSeek,
408	{
409	self.basename.set_extension(PROPERTIES_EXTENSION);	88✔
410	let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)	220✔
411	.with_context(\|\| {	44✔
412	format!("Could not load properties file {}", self.basename.display())	×
413	})?;
414	self.basename.set_extension(GRAPH_EXTENSION);	88✔
415	let factory = GLM::new_factory(&self.basename, self.graph_load_flags)	176✔
416	.with_context(\|\| format!("Could not load graph file {}", self.basename.display()))?;	44✔
417	self.basename.set_extension(EF_EXTENSION);	88✔
418	let offsets = OLM::load_offsets(&self.basename, self.offsets_load_flags)	176✔
419	.with_context(\|\| format!("Could not load offsets file {}", self.basename.display()))?;	44✔
420
421	Ok(BvGraph::new(	44✔
422	DynCodesDecoderFactory::new(factory, offsets, comp_flags)?,	176✔
423	num_nodes,	44✔
424	num_arcs,	44✔
425	comp_flags.compression_window,	44✔
426	comp_flags.min_interval_length,	44✔
427	))
428	}
429	}
430
431	impl<E: Endianness, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Sequential, Dynamic, GLM, OLM> {
432	/// Load a sequential graph with dynamic dispatch.
433	pub fn load(	39✔
434	mut self,
435	) -> anyhow::Result<
436	BvGraphSeq<DynCodesDecoderFactory<E, GLM::Factory<E>, Owned<EmptyDict<usize, usize>>>>,
437	>
438	where
439	<GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
440	for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E>,
441	{
442	self.basename.set_extension(PROPERTIES_EXTENSION);	78✔
443	let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;	195✔
444	self.basename.set_extension(GRAPH_EXTENSION);	78✔
445	let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;	156✔
446
447	Ok(BvGraphSeq::new(	39✔
448	DynCodesDecoderFactory::new(factory, EmptyDict::default().into(), comp_flags)?,	195✔
449	num_nodes,	39✔
450	Some(num_arcs),	39✔
451	comp_flags.compression_window,	39✔
452	comp_flags.min_interval_length,	39✔
453	))
454	}
455	}
456
457	impl<
458	E: Endianness,
459	GLM: LoadMode,
460	OLM: LoadMode,
461	const OUTDEGREES: usize,
462	const REFERENCES: usize,
463	const BLOCKS: usize,
464	const INTERVALS: usize,
465	const RESIDUALS: usize,
466	>
467	LoadConfig<E, Random, Static<OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>, GLM, OLM>
468	{
469	/// Load a random-access graph with static dispatch.
470	pub fn load(	×
471	mut self,
472	) -> anyhow::Result<
473	BvGraph<
474	ConstCodesDecoderFactory<
475	E,
476	GLM::Factory<E>,
477	OLM::Offsets,
478	OUTDEGREES,
479	REFERENCES,
480	BLOCKS,
481	INTERVALS,
482	RESIDUALS,
483	>,
484	>,
485	>
486	where
487	<GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
488	for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E> + BitSeek,
489	{
490	self.basename.set_extension(PROPERTIES_EXTENSION);	×
491	let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;	×
492	self.basename.set_extension(GRAPH_EXTENSION);	×
493	let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;	×
494	self.basename.set_extension(EF_EXTENSION);	×
495	let offsets = OLM::load_offsets(&self.basename, self.offsets_load_flags)?;	×
496
497	Ok(BvGraph::new(	×
498	ConstCodesDecoderFactory::new(factory, offsets, comp_flags)?,	×
499	num_nodes,	×
500	num_arcs,	×
501	comp_flags.compression_window,	×
502	comp_flags.min_interval_length,	×
503	))
504	}
505	}
506
507	impl<
508	E: Endianness,
509	GLM: LoadMode,
510	OLM: LoadMode,
511	const OUTDEGREES: usize,
512	const REFERENCES: usize,
513	const BLOCKS: usize,
514	const INTERVALS: usize,
515	const RESIDUALS: usize,
516	>
517	LoadConfig<
518	E,
519	Sequential,
520	Static<OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>,
521	GLM,
522	OLM,
523	>
524	{
525	/// Load a sequential graph with static dispatch.
526	pub fn load(	×
527	mut self,
528	) -> anyhow::Result<
529	BvGraphSeq<
530	ConstCodesDecoderFactory<
531	E,
532	GLM::Factory<E>,
533	Owned<EmptyDict<usize, usize>>,
534	OUTDEGREES,
535	REFERENCES,
536	BLOCKS,
537	INTERVALS,
538	RESIDUALS,
539	>,
540	>,
541	>
542	where
543	<GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
544	for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E>,
545	{
546	self.basename.set_extension(PROPERTIES_EXTENSION);	×
547	let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;	×
548	self.basename.set_extension(GRAPH_EXTENSION);	×
549	let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;	×
550
551	Ok(BvGraphSeq::new(	×
552	ConstCodesDecoderFactory::new(factory, EmptyDict::default().into(), comp_flags)?,	×
553	num_nodes,	×
554	Some(num_arcs),	×
555	comp_flags.compression_window,	×
556	comp_flags.min_interval_length,	×
557	))
558	}
559	}
560
561	/// Read the .properties file and return the endianness
562	pub fn get_endianness<P: AsRef<Path>>(basename: P) -> Result<String> {	44✔
563	let path = basename.as_ref().with_extension(PROPERTIES_EXTENSION);	132✔
564	let f = std::fs::File::open(&path)	132✔
565	.with_context(\|\| format!("Cannot open property file {}", path.display()))?;	44✔
566	let map = java_properties::read(BufReader::new(f))	176✔
567	.with_context(\|\| format!("cannot parse {} as a java properties file", path.display()))?;	44✔
568
569	let endianness = map	88✔
570	.get("endianness")
571	.map(\|x\| x.to_string())	92✔
572	.unwrap_or_else(\|\| BigEndian::NAME.to_string());	84✔
573
574	Ok(endianness)	44✔
575	}
576
577	/// Read the .properties file and return the number of nodes, number of arcs and compression flags
578	/// for the graph. The endianness is checked against the expected one.
579	pub fn parse_properties<E: Endianness>(path: impl AsRef<Path>) -> Result<(usize, u64, CompFlags)> {	83✔
580	let name = path.as_ref().display();	249✔
581	let f =	83✔
582	std::fs::File::open(&path).with_context(\|\| format!("Cannot open property file {name}"))?;	249✔
583	let map = java_properties::read(BufReader::new(f))	332✔
584	.with_context(\|\| format!("cannot parse {name} as a java properties file"))?;	83✔
585
586	let num_nodes = map	166✔
587	.get("nodes")
588	.with_context(\|\| format!("Missing 'nodes' property in {name}"))?	83✔
589	.parse::<usize>()
590	.with_context(\|\| format!("Cannot parse 'nodes' as usize in {name}"))?;	83✔
591	let num_arcs = map	166✔
592	.get("arcs")
593	.with_context(\|\| format!("Missing 'arcs' property in {name}"))?	83✔
594	.parse::<u64>()
595	.with_context(\|\| format!("Cannot parse arcs as usize in {name}"))?;	83✔
596
597	let comp_flags = CompFlags::from_properties::<E>(&map)	249✔
598	.with_context(\|\| format!("Cannot parse compression flags from {name}"))?;	83✔
599	Ok((num_nodes, num_arcs, comp_flags))	166✔
600	}

vigna / webgraph-rs / 19076069272

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