rustic_core/
blob.rs

1pub(crate) mod packer;
2pub(crate) mod tree;
3
4use std::{cmp::Ordering, num::NonZeroU32};
5
6use enum_map::{Enum, EnumMap};
7use serde_derive::{Deserialize, Serialize};
8use smallvec::{SmallVec, smallvec};
9
10use crate::define_new_id_struct;
11
12pub(super) mod constants {
13    /// The maximum size of pack-part which is read at once from the backend.
14    /// (needed to limit the memory size used for large backends)
15    pub(crate) const LIMIT_PACK_READ: u32 = 40 * 1024 * 1024; // 40 MiB
16    /// The maximum size of holes which are still read when repacking
17    pub(crate) const MAX_HOLESIZE: u32 = 256 * 1024; // 256 kiB
18}
19
20/// All [`BlobType`]s which are supported by the repository
21pub const ALL_BLOB_TYPES: [BlobType; 2] = [BlobType::Tree, BlobType::Data];
22
23#[derive(
24    Serialize,
25    Deserialize,
26    Clone,
27    Copy,
28    Debug,
29    PartialEq,
30    Eq,
31    PartialOrd,
32    Ord,
33    Hash,
34    Enum,
35    derive_more::Display,
36)]
37/// The type a `blob` or a `packfile` can have
38pub enum BlobType {
39    #[serde(rename = "tree")]
40    /// This is a tree blob
41    Tree,
42    #[serde(rename = "data")]
43    /// This is a data blob
44    Data,
45}
46
47impl BlobType {
48    /// Defines the cacheability of a [`BlobType`]
49    ///
50    /// # Returns
51    ///
52    /// `true` if the [`BlobType`] is cacheable, `false` otherwise
53    #[must_use]
54    pub(crate) const fn is_cacheable(self) -> bool {
55        match self {
56            Self::Tree => true,
57            Self::Data => false,
58        }
59    }
60}
61
62pub type BlobTypeMap<T> = EnumMap<BlobType, T>;
63
64/// Initialize is a new trait to define the method `init()` for a [`BlobTypeMap`]
65pub trait Initialize<T: Default + Sized> {
66    /// Initialize a [`BlobTypeMap`] by processing a given function for each [`BlobType`]
67    fn init<F: FnMut(BlobType) -> T>(init: F) -> BlobTypeMap<T>;
68}
69
70impl<T: Default> Initialize<T> for BlobTypeMap<T> {
71    /// Initialize a [`BlobTypeMap`] by processing a given function for each [`BlobType`]
72    ///
73    /// # Arguments
74    ///
75    /// * `init` - The function to process for each [`BlobType`]
76    ///
77    /// # Returns
78    ///
79    /// A [`BlobTypeMap`] with the result of the function for each [`BlobType`]
80    fn init<F: FnMut(BlobType) -> T>(mut init: F) -> Self {
81        let mut btm = Self::default();
82        for i in 0..BlobType::LENGTH {
83            let bt = BlobType::from_usize(i);
84            btm[bt] = init(bt);
85        }
86        btm
87    }
88}
89
90define_new_id_struct!(BlobId, "blob");
91
92/// A marker trait for Ids which identify Blobs in pack files
93pub trait PackedId: Copy + Into<BlobId> + From<BlobId> {
94    /// The `BlobType` of the blob identified by the Id
95    const TYPE: BlobType;
96}
97
98#[macro_export]
99/// Generate newtypes for `Id`s identifying packed blobs
100macro_rules! impl_blobid {
101    ($a:ident, $b: expr) => {
102        $crate::define_new_id_struct!($a, concat!("blob of type", stringify!($b)));
103        impl From<$crate::blob::BlobId> for $a {
104            fn from(id: $crate::blob::BlobId) -> Self {
105                (*id).into()
106            }
107        }
108        impl From<$a> for $crate::blob::BlobId {
109            fn from(id: $a) -> Self {
110                (*id).into()
111            }
112        }
113        impl $crate::blob::PackedId for $a {
114            const TYPE: $crate::blob::BlobType = $b;
115        }
116    };
117}
118
119impl_blobid!(DataId, BlobType::Data);
120
121/// `BlobLocation` contains information about a blob within a pack
122#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
123pub struct BlobLocation {
124    /// The offset of the blob within the pack
125    pub offset: u32,
126    /// The length of the blob
127    pub length: u32,
128    /// The uncompressed length of the blob
129    pub uncompressed_length: Option<NonZeroU32>,
130}
131
132impl PartialOrd<Self> for BlobLocation {
133    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
134        Some(self.cmp(other))
135    }
136}
137
138impl Ord for BlobLocation {
139    fn cmp(&self, other: &Self) -> Ordering {
140        self.offset.cmp(&other.offset)
141    }
142}
143
144impl BlobLocation {
145    /// Get the length of the data contained in this blob
146    pub const fn data_length(&self) -> u32 {
147        match self.uncompressed_length {
148            None => self.length - 32,
149            Some(length) => NonZeroU32::get(length),
150        }
151    }
152}
153
154#[derive(Debug, PartialEq, Eq)]
155pub struct BlobLocations<T> {
156    pub offset: u32,
157    pub length: u32,
158    pub blobs: SmallVec<[(BlobLocation, T); 1]>,
159}
160
161impl<T: Eq + PartialEq> PartialOrd<Self> for BlobLocations<T> {
162    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
163        Some(self.cmp(other))
164    }
165}
166
167impl<T: Eq> Ord for BlobLocations<T> {
168    fn cmp(&self, other: &Self) -> Ordering {
169        self.offset.cmp(&other.offset)
170    }
171}
172
173impl<T> BlobLocations<T> {
174    pub fn length(&self) -> u32 {
175        self.blobs.iter().map(|bl| bl.0.length).sum()
176    }
177
178    pub fn from_blob_location(location: BlobLocation, target: T) -> Self {
179        Self {
180            offset: location.offset,
181            length: location.length,
182            blobs: smallvec![(location, target)],
183        }
184    }
185    pub fn can_coalesce(&self, other: &Self) -> bool {
186        // if the blobs are (almost) contiguous and we don't trespass the limit, blobs can be read in one partial read
187        other.offset <= self.offset + self.length + constants::MAX_HOLESIZE
188            && other.offset >= self.offset + self.length
189            && other.offset + other.length - self.offset <= constants::LIMIT_PACK_READ
190    }
191
192    pub fn append(mut self, mut other: Self) -> Self {
193        self.length = other.offset + other.length - self.offset; // read till the end of other
194        self.blobs.append(&mut other.blobs);
195        self
196    }
197
198    #[allow(clippy::result_large_err)]
199    /// coalesce two `BlobLocations` if possible
200    pub fn coalesce(self, other: Self) -> Result<Self, (Self, Self)> {
201        if self.can_coalesce(&other) {
202            Ok(self.append(other))
203        } else {
204            Err((self, other))
205        }
206    }
207}
208
209#[cfg(test)]
210mod tests {
211    use super::*;
212    use rstest::rstest;
213
214    #[rstest]
215    #[case(12, 123, 0, 123, None)] // second before first
216    #[case(12, 123, 12, 123, None)] // second overlaps
217    #[case(12, 123, 134, 123, None)] // second still overlaps
218    #[case(12, 123, 135, 123, Some(246))] // second contiguous to first => OK
219    #[case(12, 123, 136, 123, Some(247))] // small hole => OK
220    #[case(12, 123, 135 + constants::MAX_HOLESIZE, 123, Some(246 + constants::MAX_HOLESIZE))] // maximum hole => OK
221    #[case(12, 123, 136 + constants::MAX_HOLESIZE, 123, None)] // hole too large
222    #[case(12, constants::LIMIT_PACK_READ - 15, constants::LIMIT_PACK_READ - 3, 15, Some(constants::LIMIT_PACK_READ))] // maximum length
223    #[case(12, constants::LIMIT_PACK_READ - 15, constants::LIMIT_PACK_READ - 3, 16, None)] // exceeds limit to read
224    #[case(12, constants::LIMIT_PACK_READ - 15, constants::LIMIT_PACK_READ, 12, Some(constants::LIMIT_PACK_READ))] // maximum length with hole
225    #[case(12, constants::LIMIT_PACK_READ - 15, constants::LIMIT_PACK_READ + 1, 12, None)] // exceeds limit
226    fn test_coalesce(
227        #[case] offset1: u32,
228        #[case] length1: u32,
229        #[case] offset2: u32,
230        #[case] length2: u32,
231        #[case] expected: Option<u32>,
232    ) {
233        // helper to create BlobLocations
234        let bl = |offset, length| {
235            BlobLocations::from_blob_location(
236                BlobLocation {
237                    offset,
238                    length,
239                    uncompressed_length: None,
240                },
241                (),
242            )
243        };
244
245        let coalesced_length = bl(offset1, length1)
246            .coalesce(bl(offset2, length2))
247            .ok()
248            .map(|bl| bl.length);
249        assert_eq!(coalesced_length, expected);
250    }
251}
rustic_core/blob.rs

rustic_core/
blob.rs
