heddle_object_model/object/manifest/
extent.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Canonical pack-extent claims — the physical half of the reshape's read path.
3//!
4//! A manifest node names only immutable logical facts. Where an object's bytes
5//! actually live is a *mutable* control-plane fact, so it never enters the
6//! content root; repacking must change a read envelope, not a manifest hash.
7//! This module gives that envelope a canonical encoding of its own so it can be
8//! signed, transported, and checked byte-for-byte.
9//!
10//! Two rules from the downstream consumer are load-bearing and reproduced here
11//! exactly:
12//!
13//! * **Offset-canonical ordering.** Records are ordered by pack offset, not by
14//!   object key. Packs are laid out for delta compression, so object order and
15//!   physical order routinely disagree; ordering by object first makes valid
16//!   coalesced ranges fail their contiguity check (weft #1070, the bug fixed
17//!   after weft #1069 merged).
18//! * **Gap-free coverage.** A coalesced range carries a sorted partition of its
19//!   authorized records that covers `[start, end)` exactly — no gap, no
20//!   overlap. A pack may hold objects of mixed audience, so one physical range
21//!   read must never authorize an unselected byte gap between two authorized
22//!   records. Coalescing joins *exactly adjacent* extents only.
23//!
24//! ```text
25//! claim: "WPMX" | u8(version=1) | u16(pack_id_len) | pack_id
26//!               | u16(etag_len) | etag | u64(start) | u64(end)
27//!               | u32(record_count)
28//!               | count * ( u8(kind) | [u8;32](object_hash)
29//!                         | u64(decoded_size) | u64(offset) | u64(length)
30//!                         | [u8;32](encoded_digest) )
31//! ```
32
33use crate::object::{
34    ContentHash,
35    manifest::node::{ManifestKey, ManifestObject, ManifestObjectKind},
36};
37
38/// Magic prefix on every canonical pack-range claim.
39pub const PACK_CLAIM_MAGIC: [u8; 4] = *b"WPMX";
40/// The only claim format version this binary reads or writes.
41pub const PACK_CLAIM_VERSION: u8 = 1;
42
43/// One object's physical slice of a pack.
44///
45/// `encoded_digest` is the BLAKE3 of the *encoded record bytes* — the bytes as
46/// they sit in the pack, before decompression or delta resolution. It lets a
47/// receiver validate every record independently instead of trusting the whole
48/// range.
49#[derive(Clone, Copy, Debug, PartialEq, Eq)]
50pub struct PackRecord {
51    pub object: ManifestObject,
52    /// Byte offset of the encoded record within its pack.
53    pub offset: u64,
54    /// Encoded length in bytes. Zero-length records are not representable in a
55    /// gap-free partition and are rejected by fsck.
56    pub length: u64,
57    /// `BLAKE3(encoded record bytes)`.
58    pub encoded_digest: ContentHash,
59}
60
61impl PackRecord {
62    pub fn new(
63        object: ManifestObject,
64        offset: u64,
65        length: u64,
66        encoded_digest: ContentHash,
67    ) -> Self {
68        Self {
69            object,
70            offset,
71            length,
72            encoded_digest,
73        }
74    }
75
76    /// Exclusive end offset, or `None` on `u64` overflow.
77    pub fn end(&self) -> Option<u64> {
78        self.offset.checked_add(self.length)
79    }
80
81    pub fn key(&self) -> ManifestKey {
82        self.object.key()
83    }
84}
85
86/// One coalesced physical range read, plus the partition of authorized records
87/// it covers.
88#[derive(Clone, Debug, PartialEq, Eq)]
89pub struct PackRangeClaim {
90    pub pack_id: String,
91    /// Provider entity tag pinning the pack revision this claim was resolved
92    /// against. A repack changes the ETag, invalidating the claim without
93    /// touching any manifest.
94    pub etag: String,
95    pub start: u64,
96    pub end: u64,
97    records: Vec<PackRecord>,
98}
99
100impl PackRangeClaim {
101    /// Build a claim over `records`, sorting them into offset-canonical order.
102    ///
103    /// Sorting here is deliberate and is the whole point of weft #1070: the
104    /// canonical order is physical, so a pack whose object order differs from
105    /// its offset order still produces a contiguous, checkable partition.
106    pub fn new(
107        pack_id: impl Into<String>,
108        etag: impl Into<String>,
109        start: u64,
110        end: u64,
111        mut records: Vec<PackRecord>,
112    ) -> Self {
113        records.sort_by_key(|record| (record.offset, record.length, record.key()));
114        Self {
115            pack_id: pack_id.into(),
116            etag: etag.into(),
117            start,
118            end,
119            records,
120        }
121    }
122
123    /// Records in offset-canonical order.
124    pub fn records(&self) -> &[PackRecord] {
125        &self.records
126    }
127
128    /// Total bytes this claim authorizes, or `None` if the range is inverted.
129    pub fn byte_len(&self) -> Option<u64> {
130        self.end.checked_sub(self.start)
131    }
132
133    /// Encode to the single canonical byte string for this claim.
134    pub fn encode(&self) -> Vec<u8> {
135        let mut out = Vec::with_capacity(
136            4 + 1
137                + 2
138                + self.pack_id.len()
139                + 2
140                + self.etag.len()
141                + 8
142                + 8
143                + 4
144                + self.records.len() * 89,
145        );
146        out.extend_from_slice(&PACK_CLAIM_MAGIC);
147        out.push(PACK_CLAIM_VERSION);
148        push_short_string(&mut out, &self.pack_id);
149        push_short_string(&mut out, &self.etag);
150        out.extend_from_slice(&self.start.to_be_bytes());
151        out.extend_from_slice(&self.end.to_be_bytes());
152        out.extend_from_slice(&(self.records.len() as u32).to_be_bytes());
153        for record in &self.records {
154            out.push(record.object.kind.to_byte());
155            out.extend_from_slice(record.object.hash.as_bytes());
156            out.extend_from_slice(&record.object.decoded_size.to_be_bytes());
157            out.extend_from_slice(&record.offset.to_be_bytes());
158            out.extend_from_slice(&record.length.to_be_bytes());
159            out.extend_from_slice(record.encoded_digest.as_bytes());
160        }
161        out
162    }
163
164    /// The claim's content address — `BLAKE3` of its canonical bytes.
165    pub fn address(&self) -> ContentHash {
166        ContentHash::compute(&self.encode())
167    }
168
169    /// Decode strictly, rejecting truncation, trailing bytes, non-UTF-8 ids,
170    /// out-of-order records, and any non-canonical spelling.
171    pub fn decode(bytes: &[u8]) -> Result<Self, PackClaimDecodeError> {
172        let claim = Self::decode_inner(bytes)?;
173        if claim.encode() != bytes {
174            return Err(PackClaimDecodeError::NonCanonicalEncoding);
175        }
176        Ok(claim)
177    }
178
179    fn decode_inner(bytes: &[u8]) -> Result<Self, PackClaimDecodeError> {
180        let mut reader = ClaimReader { bytes, pos: 0 };
181
182        if reader.take(4)? != PACK_CLAIM_MAGIC {
183            return Err(PackClaimDecodeError::BadMagic);
184        }
185        let version = reader.u8()?;
186        if version != PACK_CLAIM_VERSION {
187            return Err(PackClaimDecodeError::UnsupportedVersion(version));
188        }
189
190        let pack_id = reader.short_string()?;
191        let etag = reader.short_string()?;
192        let start = reader.u64()?;
193        let end = reader.u64()?;
194        let count = reader.u32()?;
195
196        let mut records = Vec::with_capacity((count as usize).min(4096));
197        let mut previous: Option<(u64, u64, ManifestKey)> = None;
198        for _ in 0..count {
199            let kind_byte = reader.u8()?;
200            let kind = ManifestObjectKind::from_byte(kind_byte)
201                .ok_or(PackClaimDecodeError::UnknownObjectKind(kind_byte))?;
202            let hash = ContentHash::from_bytes(reader.hash()?);
203            let decoded_size = reader.u64()?;
204            let offset = reader.u64()?;
205            let length = reader.u64()?;
206            let encoded_digest = ContentHash::from_bytes(reader.hash()?);
207            let object = ManifestObject::new(kind, hash, decoded_size);
208            let order = (offset, length, object.key());
209            if let Some(prev) = previous
210                && prev >= order
211            {
212                return Err(PackClaimDecodeError::RecordsOutOfOffsetOrder);
213            }
214            previous = Some(order);
215            records.push(PackRecord::new(object, offset, length, encoded_digest));
216        }
217        if reader.pos != bytes.len() {
218            return Err(PackClaimDecodeError::TrailingBytes);
219        }
220
221        Ok(Self {
222            pack_id,
223            etag,
224            start,
225            end,
226            records,
227        })
228    }
229}
230
231struct ClaimReader<'a> {
232    bytes: &'a [u8],
233    pos: usize,
234}
235
236impl<'a> ClaimReader<'a> {
237    fn take(&mut self, len: usize) -> Result<&'a [u8], PackClaimDecodeError> {
238        let end = self
239            .pos
240            .checked_add(len)
241            .ok_or(PackClaimDecodeError::Truncated)?;
242        let slice = self
243            .bytes
244            .get(self.pos..end)
245            .ok_or(PackClaimDecodeError::Truncated)?;
246        self.pos = end;
247        Ok(slice)
248    }
249
250    fn u8(&mut self) -> Result<u8, PackClaimDecodeError> {
251        Ok(self.take(1)?[0])
252    }
253
254    fn u16(&mut self) -> Result<u16, PackClaimDecodeError> {
255        let bytes = self.take(2)?;
256        Ok(u16::from_be_bytes([bytes[0], bytes[1]]))
257    }
258
259    fn u32(&mut self) -> Result<u32, PackClaimDecodeError> {
260        let bytes = self.take(4)?;
261        Ok(u32::from_be_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]))
262    }
263
264    fn u64(&mut self) -> Result<u64, PackClaimDecodeError> {
265        let bytes = self.take(8)?;
266        let mut arr = [0u8; 8];
267        arr.copy_from_slice(bytes);
268        Ok(u64::from_be_bytes(arr))
269    }
270
271    fn hash(&mut self) -> Result<[u8; 32], PackClaimDecodeError> {
272        let bytes = self.take(32)?;
273        let mut arr = [0u8; 32];
274        arr.copy_from_slice(bytes);
275        Ok(arr)
276    }
277
278    fn short_string(&mut self) -> Result<String, PackClaimDecodeError> {
279        let len = usize::from(self.u16()?);
280        std::str::from_utf8(self.take(len)?)
281            .map(str::to_string)
282            .map_err(|_| PackClaimDecodeError::InvalidUtf8)
283    }
284}
285
286fn push_short_string(out: &mut Vec<u8>, value: &str) {
287    out.extend_from_slice(&(value.len() as u16).to_be_bytes());
288    out.extend_from_slice(value.as_bytes());
289}
290
291#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
292pub enum PackClaimDecodeError {
293    #[error("claim does not start with the WPMX magic")]
294    BadMagic,
295    #[error("unsupported pack claim version {0}")]
296    UnsupportedVersion(u8),
297    #[error("unknown manifest object kind {0}")]
298    UnknownObjectKind(u8),
299    #[error("claim bytes are truncated")]
300    Truncated,
301    #[error("claim has trailing bytes after its declared content")]
302    TrailingBytes,
303    #[error("pack id or etag is not valid UTF-8")]
304    InvalidUtf8,
305    #[error("records are not strictly ascending by pack offset")]
306    RecordsOutOfOffsetOrder,
307    #[error("claim bytes are a non-canonical spelling of their own content")]
308    NonCanonicalEncoding,
309}
310
311#[cfg(test)]
312mod tests {
313    use super::*;
314
315    fn record(offset: u64, length: u64, seed: u8) -> PackRecord {
316        PackRecord::new(
317            ManifestObject::new(
318                ManifestObjectKind::Blob,
319                ContentHash::from_bytes([seed; 32]),
320                length * 2,
321            ),
322            offset,
323            length,
324            ContentHash::from_bytes([seed.wrapping_add(100); 32]),
325        )
326    }
327
328    #[test]
329    fn records_canonicalize_by_offset_not_by_object_key() {
330        // Object key order (0x01 < 0x02 < 0x03) is the exact reverse of the
331        // physical offset order here — the weft #1070 shape.
332        let claim = PackRangeClaim::new(
333            "pack-a",
334            "etag-1",
335            0,
336            30,
337            vec![record(20, 10, 1), record(0, 10, 3), record(10, 10, 2)],
338        );
339        let offsets: Vec<u64> = claim.records().iter().map(|r| r.offset).collect();
340        assert_eq!(offsets, vec![0, 10, 20]);
341        let seeds: Vec<u8> = claim
342            .records()
343            .iter()
344            .map(|r| r.object.hash.as_bytes()[0])
345            .collect();
346        assert_eq!(
347            seeds,
348            vec![3, 2, 1],
349            "object order must not drive the layout"
350        );
351    }
352
353    #[test]
354    fn claim_round_trips_and_is_hash_stable() {
355        let claim = PackRangeClaim::new(
356            "pack-a",
357            "\"etag-xyz\"",
358            100,
359            140,
360            vec![record(120, 20, 2), record(100, 20, 1)],
361        );
362        let encoded = claim.encode();
363        let decoded = PackRangeClaim::decode(&encoded).unwrap();
364        assert_eq!(decoded, claim);
365        assert_eq!(decoded.encode(), encoded);
366        assert_eq!(decoded.address(), claim.address());
367    }
368
369    #[test]
370    fn decode_rejects_trailing_and_truncated_bytes() {
371        let claim = PackRangeClaim::new("p", "e", 0, 10, vec![record(0, 10, 1)]);
372        let encoded = claim.encode();
373
374        let mut trailing = encoded.clone();
375        trailing.push(0);
376        assert_eq!(
377            PackRangeClaim::decode(&trailing).unwrap_err(),
378            PackClaimDecodeError::TrailingBytes
379        );
380        assert_eq!(
381            PackRangeClaim::decode(&encoded[..encoded.len() - 1]).unwrap_err(),
382            PackClaimDecodeError::Truncated
383        );
384    }
385
386    #[test]
387    fn decode_rejects_records_written_out_of_offset_order() {
388        let claim = PackRangeClaim::new("p", "e", 0, 20, vec![record(0, 10, 1), record(10, 10, 2)]);
389        let encoded = claim.encode();
390        // Swap the two fixed-width record bodies.
391        let header = encoded.len() - 2 * 89;
392        let mut swapped = encoded.clone();
393        swapped[header..header + 89].copy_from_slice(&encoded[header + 89..]);
394        swapped[header + 89..].copy_from_slice(&encoded[header..header + 89]);
395        assert_eq!(
396            PackRangeClaim::decode(&swapped).unwrap_err(),
397            PackClaimDecodeError::RecordsOutOfOffsetOrder
398        );
399    }
400
401    #[test]
402    fn decode_rejects_a_bad_magic_and_version() {
403        let encoded = PackRangeClaim::new("p", "e", 0, 10, vec![record(0, 10, 1)]).encode();
404
405        let mut bad_magic = encoded.clone();
406        bad_magic[0] = b'Z';
407        assert_eq!(
408            PackRangeClaim::decode(&bad_magic).unwrap_err(),
409            PackClaimDecodeError::BadMagic
410        );
411
412        let mut bad_version = encoded;
413        bad_version[4] = 9;
414        assert_eq!(
415            PackRangeClaim::decode(&bad_version).unwrap_err(),
416            PackClaimDecodeError::UnsupportedVersion(9)
417        );
418    }
419}
heddle_object_model/object/manifest/extent.rs

heddle_object_model/object/manifest/
extent.rs
