14999125721

Committed 13 May 2025 02:22PM UTC coverage: 49.654% (-5.7%) from 55.382%

Build # 14999125721

Build Type

push

github

Committed by

zommiommy

Commit Message

wip hyperball cli

Coverage Stats

4 of 147 new or added lines in 4 files covered. (2.72%)

477 existing lines in 46 files now uncovered.

3663 of 7377 relevant lines covered (49.65%)

25650535.86 hits per line

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

34.75

/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::prelude::*;
use sealed::sealed;
use std::{
    io::BufReader,
    path::{Path, PathBuf},
};
use sux::traits::IndexedSeq;

/// 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: IndexedSeq<Input = usize, Output = usize>;

    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 = 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();
        Ok(EF::load_full(path)
            .with_context(|| format!("Cannot load Elias-Fano pointer list {}", path.display()))?
            .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 = DeserType<'static, 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();
        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 = DeserType<'static, 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();
        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 = DeserType<'static, 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();
        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.
    #[allow(clippy::type_complexity)]
    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 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 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.
    #[allow(clippy::type_complexity)]
    pub fn load(
        mut self,
    ) -> anyhow::Result<
        BvGraphSeq<DynCodesDecoderFactory<E, GLM::Factory<E>, 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, MemCase::from(EmptyDict::default()), 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.
    #[allow(clippy::type_complexity)]
    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.
    #[allow(clippy::type_complexity)]
    pub fn load(
        mut self,
    ) -> anyhow::Result<
        BvGraphSeq<
            ConstCodesDecoderFactory<
                E,
                GLM::Factory<E>,
                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,
                MemCase::from(EmptyDict::default()),
                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 {} as a java properties file", name))?;

    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::prelude::*;
14	use sealed::sealed;
15	use std::{
16	io::BufReader,
17	path::{Path, PathBuf},
18	};
19	use sux::traits::IndexedSeq;
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: IndexedSeq<Input = usize, Output = usize>;
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 = 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	Ok(EF::load_full(path)	×
151	.with_context(\|\| format!("Cannot load Elias-Fano pointer list {}", path.display()))?	×
152	.into())	×
153	}
154	}
155
156	/// The graph and offsets are memory mapped.
157	///
158	/// This is the default mode. You can [set memory-mapping flags](LoadConfig::flags).
159	#[derive(Debug, Clone)]
160	pub struct Mmap {}
161	#[sealed]
162	impl LoadMode for Mmap {
163	type Factory<E: Endianness> = MmapHelper<u32>;
164	type Offsets = DeserType<'static, EF>;
165
166	fn new_factory<E: Endianness, P: AsRef<Path>>(	57✔
167	graph: P,
168	flags: MemoryFlags,
169	) -> Result<Self::Factory<E>> {
170	MmapHelper::mmap(graph, flags.into())	228✔
171	}
172
173	fn load_offsets<P: AsRef<Path>>(	30✔
174	offsets: P,
175	flags: MemoryFlags,
176	) -> Result<MemCase<Self::Offsets>> {
177	let path = offsets.as_ref();	90✔
178	EF::mmap(path, flags.into())	120✔
179	.with_context(\|\| format!("Cannot map Elias-Fano pointer list {}", path.display()))	30✔
180	}
181	}
182
183	/// The graph and offsets are loaded into allocated memory.
184	#[derive(Debug, Clone)]
185	pub struct LoadMem {}
186	#[sealed]
187	impl LoadMode for LoadMem {
188	type Factory<E: Endianness> = MemoryFactory<E, Box<[u32]>>;
189	type Offsets = DeserType<'static, EF>;
190
191	fn new_factory<E: Endianness, P: AsRef<Path>>(	×
192	graph: P,
193	_flags: MemoryFlags,
194	) -> Result<Self::Factory<E>> {
195	MemoryFactory::<E, _>::new_mem(graph)	×
196	}
197
198	fn load_offsets<P: AsRef<Path>>(	×
199	offsets: P,
200	_flags: MemoryFlags,
201	) -> Result<MemCase<Self::Offsets>> {
202	let path = offsets.as_ref();	×
203	EF::load_mem(path)	×
204	.with_context(\|\| format!("Cannot load Elias-Fano pointer list {}", path.display()))	×
205	}
206	}
207
208	/// The graph and offsets are loaded into memory obtained via `mmap()`.
209	///
210	/// You can [set memory-mapping flags](LoadConfig::flags).
211	#[derive(Debug, Clone)]
212	pub struct LoadMmap {}
213	#[sealed]
214	impl LoadMode for LoadMmap {
215	type Factory<E: Endianness> = MemoryFactory<E, MmapHelper<u32>>;
216	type Offsets = DeserType<'static, EF>;
217
218	fn new_factory<E: Endianness, P: AsRef<Path>>(	8✔
219	graph: P,
220	flags: MemoryFlags,
221	) -> Result<Self::Factory<E>> {
222	MemoryFactory::<E, _>::new_mmap(graph, flags)	24✔
223	}
224
225	fn load_offsets<P: AsRef<Path>>(	8✔
226	offsets: P,
227	flags: MemoryFlags,
228	) -> Result<MemCase<Self::Offsets>> {
229	let path = offsets.as_ref();	24✔
230	EF::load_mmap(path, flags.into())	32✔
231	.with_context(\|\| format!("Cannot load Elias-Fano pointer list {}", path.display()))	8✔
232	}
233	}
234
235	/// A load configuration for a [`BvGraph`]/[`BvGraphSeq`].
236	///
237	/// A basic configuration is returned by
238	/// [`BvGraph::with_basename`]/[`BvGraphSeq::with_basename`]. The configuration
239	/// can then be customized using the methods of this struct.
240	#[derive(Debug, Clone)]
241	pub struct LoadConfig<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode> {
242	pub(crate) basename: PathBuf,
243	pub(crate) graph_load_flags: MemoryFlags,
244	pub(crate) offsets_load_flags: MemoryFlags,
245	pub(crate) _marker: std::marker::PhantomData<(E, A, D, GLM, OLM)>,
246	}
247
248	impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
249	LoadConfig<E, A, D, GLM, OLM>
250	{
251	/// Set the endianness of the graph and offsets file.
252	pub fn endianness<E2: Endianness>(self) -> LoadConfig<E2, A, D, GLM, OLM>	58✔
253	where
254	GLM: LoadMode,
255	OLM: LoadMode,
256	{
257	LoadConfig {
258	basename: self.basename,	116✔
259	graph_load_flags: self.graph_load_flags,	116✔
260	offsets_load_flags: self.offsets_load_flags,	58✔
261	_marker: std::marker::PhantomData,
262	}
263	}
264	}
265
266	impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
267	LoadConfig<E, A, D, GLM, OLM>
268	{
269	/// Choose between [`Static`] and [`Dynamic`] dispatch.
270	pub fn dispatch<D2: Dispatch>(self) -> LoadConfig<E, A, D2, GLM, OLM> {	×
271	LoadConfig {
272	basename: self.basename,	×
273	graph_load_flags: self.graph_load_flags,	×
274	offsets_load_flags: self.offsets_load_flags,	×
275	_marker: std::marker::PhantomData,
276	}
277	}
278	}
279
280	impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
281	LoadConfig<E, A, D, GLM, OLM>
282	{
283	/// Choose the [`LoadMode`] for the graph and offsets.
284	pub fn mode<LM: LoadMode>(self) -> LoadConfig<E, A, D, LM, LM> {	8✔
285	LoadConfig {
286	basename: self.basename,	16✔
287	graph_load_flags: self.graph_load_flags,	16✔
288	offsets_load_flags: self.offsets_load_flags,	8✔
289	_marker: std::marker::PhantomData,
290	}
291	}
292	}
293
294	impl<E: Endianness, A: Access, D: Dispatch> LoadConfig<E, A, D, Mmap, Mmap> {
295	/// Set flags for memory-mapping (both graph and offsets).
296	pub fn flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, Mmap, Mmap> {	×
297	LoadConfig {
298	basename: self.basename,	×
299	graph_load_flags: flags,
300	offsets_load_flags: flags,
301	_marker: std::marker::PhantomData,
302	}
303	}
304	}
305
306	impl<E: Endianness, A: Access, D: Dispatch> LoadConfig<E, A, D, LoadMmap, LoadMmap> {
307	/// Set flags for memory obtained from `mmap()` (both graph and offsets).
308	pub fn flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, LoadMmap, LoadMmap> {	8✔
309	LoadConfig {
310	basename: self.basename,	16✔
311	graph_load_flags: flags,
312	offsets_load_flags: flags,
313	_marker: std::marker::PhantomData,
314	}
315	}
316	}
317
318	impl<E: Endianness, A: Access, D: Dispatch, GLM: LoadMode, OLM: LoadMode>
319	LoadConfig<E, A, D, GLM, OLM>
320	{
321	/// Choose the [`LoadMode`] for the graph only.
322	pub fn graph_mode<NGLM: LoadMode>(self) -> LoadConfig<E, A, D, NGLM, OLM> {	×
323	LoadConfig {
324	basename: self.basename,	×
325	graph_load_flags: self.graph_load_flags,	×
326	offsets_load_flags: self.offsets_load_flags,	×
327	_marker: std::marker::PhantomData,
328	}
329	}
330	}
331
332	impl<E: Endianness, A: Access, D: Dispatch, OLM: LoadMode> LoadConfig<E, A, D, Mmap, OLM> {
333	/// Set flags for memory-mapping the graph.
334	pub fn graph_flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, Mmap, OLM> {	×
335	LoadConfig {
336	basename: self.basename,	×
337	graph_load_flags: flags,
338	offsets_load_flags: self.offsets_load_flags,	×
339	_marker: std::marker::PhantomData,
340	}
341	}
342	}
343
344	impl<E: Endianness, A: Access, D: Dispatch, OLM: LoadMode> LoadConfig<E, A, D, LoadMmap, OLM> {
345	/// Set flags for memory obtained from `mmap()` for the graph.
346	pub fn graph_flags(self, flags: MemoryFlags) -> LoadConfig<E, A, D, LoadMmap, OLM> {	×
347	LoadConfig {
348	basename: self.basename,	×
349	graph_load_flags: flags,
350	offsets_load_flags: self.offsets_load_flags,	×
351	_marker: std::marker::PhantomData,
352	}
353	}
354	}
355
356	impl<E: Endianness, D: Dispatch, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Random, D, GLM, OLM> {
357	/// Choose the [`LoadMode`] for the graph only.
358	pub fn offsets_mode<NOLM: LoadMode>(self) -> LoadConfig<E, Random, D, GLM, NOLM> {	×
359	LoadConfig {
360	basename: self.basename,	×
361	graph_load_flags: self.graph_load_flags,	×
362	offsets_load_flags: self.offsets_load_flags,	×
363	_marker: std::marker::PhantomData,
364	}
365	}
366	}
367
368	impl<E: Endianness, D: Dispatch, GLM: LoadMode> LoadConfig<E, Random, D, GLM, Mmap> {
369	/// Set flags for memory-mapping the offsets.
370	pub fn offsets_flags(self, flags: MemoryFlags) -> LoadConfig<E, Random, D, GLM, Mmap> {	×
371	LoadConfig {
372	basename: self.basename,	×
373	graph_load_flags: self.graph_load_flags,	×
374	offsets_load_flags: flags,
375	_marker: std::marker::PhantomData,
376	}
377	}
378	}
379
380	impl<E: Endianness, D: Dispatch, GLM: LoadMode> LoadConfig<E, Random, D, GLM, LoadMmap> {
381	/// Set flags for memory obtained from `mmap()` for the graph.
382	pub fn offsets_flags(self, flags: MemoryFlags) -> LoadConfig<E, Random, D, GLM, LoadMmap> {	×
383	LoadConfig {
384	basename: self.basename,	×
385	graph_load_flags: self.graph_load_flags,	×
386	offsets_load_flags: flags,
387	_marker: std::marker::PhantomData,
388	}
389	}
390	}
391
392	impl<E: Endianness, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Random, Dynamic, GLM, OLM> {
393	/// Load a random-access graph with dynamic dispatch.
394	#[allow(clippy::type_complexity)]
395	pub fn load(	38✔
396	mut self,
397	) -> anyhow::Result<BvGraph<DynCodesDecoderFactory<E, GLM::Factory<E>, OLM::Offsets>>>
398	where
399	<GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
400	for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E> + BitSeek,
401	{
402	self.basename.set_extension(PROPERTIES_EXTENSION);	76✔
403	let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)	114✔
404	.with_context(\|\| {	38✔
NEW 405	format!("Could not load properties file {}", self.basename.display())	×
406	})?;
UNCOV 407	self.basename.set_extension(GRAPH_EXTENSION);	×
408	let factory = GLM::new_factory(&self.basename, self.graph_load_flags)	38✔
NEW 409	.with_context(\|\| format!("Could not graph file {}", self.basename.display()))?;	×
UNCOV 410	self.basename.set_extension(EF_EXTENSION);	×
411	let offsets = OLM::load_offsets(&self.basename, self.offsets_load_flags)	38✔
NEW 412	.with_context(\|\| format!("Could not offsets file {}", self.basename.display()))?;	×
413
414	Ok(BvGraph::new(	38✔
415	DynCodesDecoderFactory::new(factory, offsets, comp_flags)?,	×
416	num_nodes,	×
417	num_arcs,	×
418	comp_flags.compression_window,	×
419	comp_flags.min_interval_length,	×
420	))
421	}
422	}
423
424	impl<E: Endianness, GLM: LoadMode, OLM: LoadMode> LoadConfig<E, Sequential, Dynamic, GLM, OLM> {
425	/// Load a sequential graph with dynamic dispatch.
426	#[allow(clippy::type_complexity)]
427	pub fn load(	27✔
428	mut self,
429	) -> anyhow::Result<
430	BvGraphSeq<DynCodesDecoderFactory<E, GLM::Factory<E>, EmptyDict<usize, usize>>>,
431	>
432	where
433	<GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
434	for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E>,
435	{
436	self.basename.set_extension(PROPERTIES_EXTENSION);	54✔
437	let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;	81✔
438	self.basename.set_extension(GRAPH_EXTENSION);	×
439	let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;	27✔
440
441	Ok(BvGraphSeq::new(	27✔
442	DynCodesDecoderFactory::new(factory, MemCase::from(EmptyDict::default()), comp_flags)?,	×
443	num_nodes,	×
444	Some(num_arcs),	×
445	comp_flags.compression_window,	×
446	comp_flags.min_interval_length,	×
447	))
448	}
449	}
450
451	impl<
452	E: Endianness,
453	GLM: LoadMode,
454	OLM: LoadMode,
455	const OUTDEGREES: usize,
456	const REFERENCES: usize,
457	const BLOCKS: usize,
458	const INTERVALS: usize,
459	const RESIDUALS: usize,
460	>
461	LoadConfig<E, Random, Static<OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>, GLM, OLM>
462	{
463	/// Load a random-access graph with static dispatch.
464	#[allow(clippy::type_complexity)]
465	pub fn load(	×
466	mut self,
467	) -> anyhow::Result<
468	BvGraph<
469	ConstCodesDecoderFactory<
470	E,
471	GLM::Factory<E>,
472	OLM::Offsets,
473	OUTDEGREES,
474	REFERENCES,
475	BLOCKS,
476	INTERVALS,
477	RESIDUALS,
478	>,
479	>,
480	>
481	where
482	<GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
483	for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E> + BitSeek,
484	{
485	self.basename.set_extension(PROPERTIES_EXTENSION);	×
486	let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;	×
487	self.basename.set_extension(GRAPH_EXTENSION);	×
488	let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;	×
489	self.basename.set_extension(EF_EXTENSION);	×
490	let offsets = OLM::load_offsets(&self.basename, self.offsets_load_flags)?;	×
491
492	Ok(BvGraph::new(	×
493	ConstCodesDecoderFactory::new(factory, offsets, comp_flags)?,	×
494	num_nodes,	×
495	num_arcs,	×
496	comp_flags.compression_window,	×
497	comp_flags.min_interval_length,	×
498	))
499	}
500	}
501
502	impl<
503	E: Endianness,
504	GLM: LoadMode,
505	OLM: LoadMode,
506	const OUTDEGREES: usize,
507	const REFERENCES: usize,
508	const BLOCKS: usize,
509	const INTERVALS: usize,
510	const RESIDUALS: usize,
511	>
512	LoadConfig<
513	E,
514	Sequential,
515	Static<OUTDEGREES, REFERENCES, BLOCKS, INTERVALS, RESIDUALS>,
516	GLM,
517	OLM,
518	>
519	{
520	/// Load a sequential graph with static dispatch.
521	#[allow(clippy::type_complexity)]
522	pub fn load(	×
523	mut self,
524	) -> anyhow::Result<
525	BvGraphSeq<
526	ConstCodesDecoderFactory<
527	E,
528	GLM::Factory<E>,
529	EmptyDict<usize, usize>,
530	OUTDEGREES,
531	REFERENCES,
532	BLOCKS,
533	INTERVALS,
534	RESIDUALS,
535	>,
536	>,
537	>
538	where
539	<GLM as LoadMode>::Factory<E>: CodesReaderFactoryHelper<E>,
540	for<'a> LoadModeCodesReader<'a, E, GLM>: CodesRead<E>,
541	{
542	self.basename.set_extension(PROPERTIES_EXTENSION);	×
543	let (num_nodes, num_arcs, comp_flags) = parse_properties::<E>(&self.basename)?;	×
544	self.basename.set_extension(GRAPH_EXTENSION);	×
545	let factory = GLM::new_factory(&self.basename, self.graph_load_flags)?;	×
546
547	Ok(BvGraphSeq::new(	×
548	ConstCodesDecoderFactory::new(	×
549	factory,	×
550	MemCase::from(EmptyDict::default()),	×
551	comp_flags,	×
552	)?,
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> {	32✔
563	let path = basename.as_ref().with_extension(PROPERTIES_EXTENSION);	96✔
564	let f = std::fs::File::open(&path)	96✔
565	.with_context(\|\| format!("Cannot open property file {}", path.display()))?;	32✔
566	let map = java_properties::read(BufReader::new(f))	32✔
567	.with_context(\|\| format!("cannot parse {} as a java properties file", path.display()))?;	×
568
569	let endianness = map	×
570	.get("endianness")
571	.map(\|x\| x.to_string())	32✔
572	.unwrap_or_else(\|\| BigEndian::NAME.to_string());	32✔
573
574	Ok(endianness)	×
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)> {	65✔
580	let name = path.as_ref().display();	195✔
581	let f = std::fs::File::open(&path)	195✔
582	.with_context(\|\| format!("Cannot open property file {}", name))?;	65✔
583	let map = java_properties::read(BufReader::new(f))	65✔
584	.with_context(\|\| format!("cannot parse {} as a java properties file", name))?;	×
585
586	let num_nodes = map	65✔
587	.get("nodes")
588	.with_context(\|\| format!("Missing 'nodes' property in {}", name))?	×
589	.parse::<usize>()
UNCOV 590	.with_context(\|\| format!("Cannot parse 'nodes' as usize in {}", name))?;	×
591	let num_arcs = map	65✔
592	.get("arcs")
593	.with_context(\|\| format!("Missing 'arcs' property in {}", name))?	×
594	.parse::<u64>()
UNCOV 595	.with_context(\|\| format!("Cannot parse arcs as usize in {}", name))?;	×
596
597	let comp_flags = CompFlags::from_properties::<E>(&map)	65✔
598	.with_context(\|\| format!("Cannot parse compression flags from {}", name))?;	×
599	Ok((num_nodes, num_arcs, comp_flags))	×
600	}

vigna / webgraph-rs / 14999125721

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