• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

vigna / webgraph-rs / 18095358691

29 Sep 2025 11:26AM UTC coverage: 49.498% (-0.5%) from 49.949%
18095358691

Pull #103

github

web-flow
Merge 9d2b092f6 into d3762acb7
Pull Request #103: BVComp: Warn about empty lenders

1 of 6 new or added lines in 1 file covered. (16.67%)

663 existing lines in 24 files now uncovered.

3847 of 7772 relevant lines covered (49.5%)

23519398.62 hits per line

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

81.48
/webgraph/src/graphs/bvgraph/codecs/dec_dyn.rs
1
/*
2
 * SPDX-FileCopyrightText: 2023 Inria
3
 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
5
 *
6
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7
 */
8

9
use std::marker::PhantomData;
10

11
use super::super::*;
12
use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
13
use dsi_bitstream::dispatch::CodesReaderFactory;
14
use dsi_bitstream::prelude::*;
15

16
use epserde::deser::{MemCase, Owned};
17
use sux::traits::IndexedSeq;
18

19
#[derive(Debug)]
20
pub struct DynCodesDecoder<E: Endianness, CR: CodesRead<E>> {
21
    pub(crate) code_reader: CR,
22
    pub(crate) read_outdegree: FuncCodeReader<E, CR>,
23
    pub(crate) read_reference_offset: FuncCodeReader<E, CR>,
24
    pub(crate) read_block_count: FuncCodeReader<E, CR>,
25
    pub(crate) read_block: FuncCodeReader<E, CR>,
26
    pub(crate) read_interval_count: FuncCodeReader<E, CR>,
27
    pub(crate) read_interval_start: FuncCodeReader<E, CR>,
28
    pub(crate) read_interval_len: FuncCodeReader<E, CR>,
29
    pub(crate) read_first_residual: FuncCodeReader<E, CR>,
30
    pub(crate) read_residual: FuncCodeReader<E, CR>,
31
    pub(crate) _marker: core::marker::PhantomData<E>,
32
}
33

34
/// manual implementation to avoid the `E: Clone` bound
35
impl<E: Endianness, CR: CodesRead<E> + Clone> Clone for DynCodesDecoder<E, CR> {
36
    fn clone(&self) -> Self {
109✔
37
        Self {
38
            code_reader: self.code_reader.clone(),
327✔
39
            read_outdegree: self.read_outdegree.clone(),
327✔
40
            read_reference_offset: self.read_reference_offset.clone(),
327✔
41
            read_block_count: self.read_block_count.clone(),
327✔
42
            read_block: self.read_block.clone(),
327✔
43
            read_interval_count: self.read_interval_count.clone(),
327✔
44
            read_interval_start: self.read_interval_start.clone(),
327✔
45
            read_interval_len: self.read_interval_len.clone(),
327✔
46
            read_first_residual: self.read_first_residual.clone(),
327✔
47
            read_residual: self.read_residual.clone(),
218✔
48
            _marker: PhantomData,
49
        }
50
    }
51
}
52

53
impl<E: Endianness, CR: CodesRead<E>> DynCodesDecoder<E, CR> {
54
    pub fn new(code_reader: CR, cf: &CompFlags) -> anyhow::Result<Self> {
31,104✔
UNCOV
55
        Ok(Self {
×
56
            code_reader,
31,104✔
57
            read_outdegree: FuncCodeReader::new(cf.outdegrees)?,
62,208✔
58
            read_reference_offset: FuncCodeReader::new(cf.references)?,
31,104✔
59
            read_block_count: FuncCodeReader::new(cf.blocks)?,
31,104✔
60
            read_block: FuncCodeReader::new(cf.blocks)?,
31,104✔
61
            read_interval_count: FuncCodeReader::new(cf.intervals)?,
31,104✔
62
            read_interval_start: FuncCodeReader::new(cf.intervals)?,
31,104✔
63
            read_interval_len: FuncCodeReader::new(cf.intervals)?,
31,104✔
64
            read_first_residual: FuncCodeReader::new(cf.residuals)?,
31,104✔
65
            read_residual: FuncCodeReader::new(cf.residuals)?,
31,104✔
66
            _marker: core::marker::PhantomData,
31,104✔
67
        })
68
    }
69
}
70

71
impl<E: Endianness, CR: CodesRead<E> + BitSeek> BitSeek for DynCodesDecoder<E, CR> {
72
    type Error = <CR as BitSeek>::Error;
73

74
    #[inline(always)]
75
    fn set_bit_pos(&mut self, bit_index: u64) -> Result<(), Self::Error> {
×
UNCOV
76
        self.code_reader.set_bit_pos(bit_index)
×
77
    }
78

79
    #[inline(always)]
80
    fn bit_pos(&mut self) -> Result<u64, Self::Error> {
149,018,668✔
81
        self.code_reader.bit_pos()
298,037,336✔
82
    }
83
}
84

85
impl<E: Endianness, CR: CodesRead<E>> Decode for DynCodesDecoder<E, CR> {
86
    #[inline(always)]
87
    fn read_outdegree(&mut self) -> u64 {
250,456,510✔
88
        self.read_outdegree.read(&mut self.code_reader).unwrap()
1,001,826,040✔
89
    }
90

91
    #[inline(always)]
92
    fn read_reference_offset(&mut self) -> u64 {
169,498,402✔
93
        self.read_reference_offset
169,498,402✔
94
            .read(&mut self.code_reader)
338,996,804✔
95
            .unwrap()
96
    }
97

98
    #[inline(always)]
99
    fn read_block_count(&mut self) -> u64 {
118,298,421✔
100
        self.read_block_count.read(&mut self.code_reader).unwrap()
473,193,684✔
101
    }
102
    #[inline(always)]
103
    fn read_block(&mut self) -> u64 {
196,009,690✔
104
        self.read_block.read(&mut self.code_reader).unwrap()
784,038,760✔
105
    }
106

107
    #[inline(always)]
108
    fn read_interval_count(&mut self) -> u64 {
131,725,246✔
109
        self.read_interval_count
131,725,246✔
110
            .read(&mut self.code_reader)
263,450,492✔
111
            .unwrap()
112
    }
113
    #[inline(always)]
114
    fn read_interval_start(&mut self) -> u64 {
29,339,892✔
115
        self.read_interval_start
29,339,892✔
116
            .read(&mut self.code_reader)
58,679,784✔
117
            .unwrap()
118
    }
119
    #[inline(always)]
120
    fn read_interval_len(&mut self) -> u64 {
29,339,892✔
121
        self.read_interval_len.read(&mut self.code_reader).unwrap()
117,359,568✔
122
    }
123

124
    #[inline(always)]
125
    fn read_first_residual(&mut self) -> u64 {
129,847,214✔
126
        self.read_first_residual
129,847,214✔
127
            .read(&mut self.code_reader)
259,694,428✔
128
            .unwrap()
129
    }
130
    #[inline(always)]
131
    fn read_residual(&mut self) -> u64 {
1,008,520,892✔
132
        self.read_residual.read(&mut self.code_reader).unwrap()
2,147,483,647✔
133
    }
134
}
135

136
pub struct DynCodesDecoderFactory<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> {
137
    /// The owned data we will read as a bitstream.
138
    factory: F,
139
    /// The offsets into the data.
140
    offsets: MemCase<OFF>,
141
    /// The compression flags.
142
    compression_flags: CompFlags,
143
    // The cached functions to read the codes.
144
    read_outdegree: FactoryFuncCodeReader<E, F>,
145
    read_reference_offset: FactoryFuncCodeReader<E, F>,
146
    read_block_count: FactoryFuncCodeReader<E, F>,
147
    read_blocks: FactoryFuncCodeReader<E, F>,
148
    read_interval_count: FactoryFuncCodeReader<E, F>,
149
    read_interval_start: FactoryFuncCodeReader<E, F>,
150
    read_interval_len: FactoryFuncCodeReader<E, F>,
151
    read_first_residual: FactoryFuncCodeReader<E, F>,
152
    read_residual: FactoryFuncCodeReader<E, F>,
153
    /// Tell the compiler that's Ok that we don't store `E` but we need it
154
    /// for typing.
155
    _marker: core::marker::PhantomData<E>,
156
}
157

158
impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> DynCodesDecoderFactory<E, F, OFF>
159
where
160
    for<'a> &'a OFF::DeserType<'a>: IntoIterator<Item = usize>,
161
{
162
    /// Remaps the offsets in a slice of `usize`.
163
    ///
164
    /// This method is mainly useful for benchmarking and testing purposes, as
165
    /// representing the offsets as a slice increasing significantly the
166
    /// memory footprint.
167
    ///
168
    /// This method is used by [`BvGraph::offsets_to_slice`].
UNCOV
169
    pub fn offsets_to_slice(self) -> DynCodesDecoderFactory<E, F, Owned<Box<[usize]>>> {
×
170
        DynCodesDecoderFactory {
UNCOV
171
            factory: self.factory,
×
UNCOV
172
            offsets: self
×
173
                .offsets
174
                .uncase()
175
                .into_iter()
176
                .collect::<Vec<_>>()
177
                .into_boxed_slice()
178
                .into(),
UNCOV
179
            compression_flags: self.compression_flags,
×
UNCOV
180
            read_outdegree: self.read_outdegree,
×
UNCOV
181
            read_reference_offset: self.read_reference_offset,
×
UNCOV
182
            read_block_count: self.read_block_count,
×
UNCOV
183
            read_blocks: self.read_blocks,
×
UNCOV
184
            read_interval_count: self.read_interval_count,
×
UNCOV
185
            read_interval_start: self.read_interval_start,
×
UNCOV
186
            read_interval_len: self.read_interval_len,
×
UNCOV
187
            read_first_residual: self.read_first_residual,
×
UNCOV
188
            read_residual: self.read_residual,
×
189
            _marker: PhantomData,
190
        }
191
    }
192
}
193

194
impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets>
195
    DynCodesDecoderFactory<E, F, OFF>
196
{
197
    #[inline(always)]
198
    /// Returns a clone of the compression flags.
UNCOV
199
    pub fn get_compression_flags(&self) -> CompFlags {
×
UNCOV
200
        self.compression_flags
×
201
    }
202

203
    /// Creates a new builder from the data and the compression flags.
204
    pub fn new(factory: F, offsets: MemCase<OFF>, cf: CompFlags) -> anyhow::Result<Self> {
13,987✔
UNCOV
205
        Ok(Self {
×
206
            factory,
13,987✔
207
            offsets,
13,987✔
208
            read_outdegree: FactoryFuncCodeReader::new(cf.outdegrees)?,
27,974✔
209
            read_reference_offset: FactoryFuncCodeReader::new(cf.references)?,
13,987✔
210
            read_block_count: FactoryFuncCodeReader::new(cf.blocks)?,
13,987✔
211
            read_blocks: FactoryFuncCodeReader::new(cf.blocks)?,
13,987✔
212
            read_interval_count: FactoryFuncCodeReader::new(cf.intervals)?,
13,987✔
213
            read_interval_start: FactoryFuncCodeReader::new(cf.intervals)?,
13,987✔
214
            read_interval_len: FactoryFuncCodeReader::new(cf.intervals)?,
13,987✔
215
            read_first_residual: FactoryFuncCodeReader::new(cf.residuals)?,
13,987✔
216
            read_residual: FactoryFuncCodeReader::new(cf.residuals)?,
13,987✔
217
            compression_flags: cf,
13,987✔
UNCOV
218
            _marker: core::marker::PhantomData,
×
219
        })
220
    }
221
}
222

223
impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> RandomAccessDecoderFactory
224
    for DynCodesDecoderFactory<E, F, OFF>
225
where
226
    for<'a> <F as CodesReaderFactory<E>>::CodesReader<'a>: BitSeek,
227
{
228
    type Decoder<'a>
229
        = DynCodesDecoder<E, <F as CodesReaderFactory<E>>::CodesReader<'a>>
230
    where
231
        Self: 'a;
232

233
    #[inline(always)]
234
    fn new_decoder(&self, node: usize) -> anyhow::Result<Self::Decoder<'_>> {
63,240,999✔
235
        let mut code_reader = self.factory.new_reader();
189,722,997✔
236
        code_reader.set_bit_pos(unsafe { self.offsets.uncase().get_unchecked(node) } as u64)?;
252,963,996✔
237

238
        Ok(DynCodesDecoder {
63,240,999✔
239
            code_reader,
63,240,999✔
240
            read_outdegree: self.read_outdegree.get(),
63,240,999✔
241
            read_reference_offset: self.read_reference_offset.get(),
63,240,999✔
242
            read_block_count: self.read_block_count.get(),
63,240,999✔
243
            read_block: self.read_blocks.get(),
63,240,999✔
244
            read_interval_count: self.read_interval_count.get(),
63,240,999✔
245
            read_interval_start: self.read_interval_start.get(),
63,240,999✔
246
            read_interval_len: self.read_interval_len.get(),
63,240,999✔
247
            read_first_residual: self.read_first_residual.get(),
63,240,999✔
248
            read_residual: self.read_residual.get(),
63,240,999✔
249
            _marker: PhantomData,
63,240,999✔
250
        })
251
    }
252
}
253

254
impl<E: Endianness, F: CodesReaderFactoryHelper<E>, OFF: Offsets> SequentialDecoderFactory
255
    for DynCodesDecoderFactory<E, F, OFF>
256
{
257
    type Decoder<'a>
258
        = DynCodesDecoder<E, <F as CodesReaderFactory<E>>::CodesReader<'a>>
259
    where
260
        Self: 'a;
261

262
    #[inline(always)]
263
    fn new_decoder(&self) -> anyhow::Result<Self::Decoder<'_>> {
6,985✔
264
        Ok(DynCodesDecoder {
6,985✔
265
            code_reader: self.factory.new_reader(),
20,955✔
266
            read_outdegree: self.read_outdegree.get(),
20,955✔
267
            read_reference_offset: self.read_reference_offset.get(),
20,955✔
268
            read_block_count: self.read_block_count.get(),
20,955✔
269
            read_block: self.read_blocks.get(),
20,955✔
270
            read_interval_count: self.read_interval_count.get(),
20,955✔
271
            read_interval_start: self.read_interval_start.get(),
20,955✔
272
            read_interval_len: self.read_interval_len.get(),
20,955✔
273
            read_first_residual: self.read_first_residual.get(),
20,955✔
274
            read_residual: self.read_residual.get(),
13,970✔
275
            _marker: PhantomData,
6,985✔
276
        })
277
    }
278
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc