heddle_object_model/object/
tree_canonical.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Streamable canonical Tree encoding (HTR4).
3//!
4//! Each entry is a length-prefixed frame, so a reader can yield one entry or
5//! a caller-sized page and resume at a byte offset without decoding the prefix.
6//! Whole-object compression is not part of this encoding: a resume cursor must
7//! be able to seek without decompressing earlier frames.
8
9use sley::{ObjectFormat as GitObjectFormat, ObjectId as GitObjectId};
10
11use super::tree::{git_format_from_tag, git_format_to_tag};
12use super::tree_stream::TreeStreamError;
13use super::{ContentHash, EntryType, FileMode, SpoolId, StateId, Tree, TreeEntry, TreeError};
14
15/// Durable encoding version stored in every HTR4 header and resume cursor.
16pub const TREE_ENCODING_VERSION: u8 = 4;
17/// Frame discriminator for a single canonical tree.
18pub const TREE_CANONICAL_MAGIC: &[u8; 4] = b"HTR4";
19/// Fixed header size: magic + version + tree id + counts.
20pub const TREE_HEADER_LEN: usize = 4 + 1 + 32 + 8 + 8 + 8;
21
22/// Parsed HTR4 header. Counts and payload length are known before any entry.
23#[derive(Clone, Debug, PartialEq, Eq)]
24pub struct TreeHeader {
25    pub version: u8,
26    pub tree_id: ContentHash,
27    pub entry_count: u64,
28    pub payload_len: u64,
29    pub logical_len: u64,
30}
31
32/// True when `bytes` begin with the canonical tree discriminator.
33pub fn is_canonical_tree(bytes: &[u8]) -> bool {
34    bytes.starts_with(TREE_CANONICAL_MAGIC)
35}
36
37impl Tree {
38    /// Encode this tree as uncompressed HTR4.
39    pub fn encode_canonical(&self) -> Result<Vec<u8>, TreeStreamError> {
40        self.validate()?;
41        let tree_id = self.hash();
42        let mut payload = Vec::new();
43        let mut logical_len = 0u64;
44        for entry in self.entries() {
45            logical_len = logical_len
46                .checked_add(entry.encoded_len() as u64)
47                .ok_or_else(|| TreeStreamError::Malformed("logical length overflow".into()))?;
48            let frame = encode_entry_frame(entry)?;
49            let frame_len = u32::try_from(frame.len()).map_err(|_| {
50                TreeStreamError::Malformed(format!("entry '{}' frame exceeds u32", entry.name()))
51            })?;
52            payload.extend_from_slice(&frame_len.to_le_bytes());
53            payload.extend_from_slice(&frame);
54        }
55        let mut out = Vec::with_capacity(TREE_HEADER_LEN + payload.len());
56        out.extend_from_slice(TREE_CANONICAL_MAGIC);
57        out.push(TREE_ENCODING_VERSION);
58        out.extend_from_slice(tree_id.as_bytes());
59        out.extend_from_slice(&(self.len() as u64).to_le_bytes());
60        out.extend_from_slice(&(payload.len() as u64).to_le_bytes());
61        out.extend_from_slice(&logical_len.to_le_bytes());
62        out.extend_from_slice(&payload);
63        Ok(out)
64    }
65
66    /// Decode a complete HTR4 body, validating order incrementally.
67    pub fn decode_canonical(data: &[u8]) -> Result<Self, TreeStreamError> {
68        let header = decode_header(data)?;
69        let expected_len = TREE_HEADER_LEN as u64 + header.payload_len;
70        if (data.len() as u64) < expected_len {
71            return Err(TreeStreamError::TruncatedFrame {
72                offset: data.len() as u64,
73            });
74        }
75        if (data.len() as u64) > expected_len {
76            return Err(TreeStreamError::TrailingBytes {
77                extra: data.len() as u64 - expected_len,
78            });
79        }
80        let mut entries = Vec::new();
81        let mut offset = TREE_HEADER_LEN;
82        let payload_end = data.len();
83        for _ in 0..header.entry_count {
84            let (entry, consumed) = decode_entry_at(data, offset, payload_end)?;
85            entries.push(entry);
86            offset += consumed;
87        }
88        if offset != payload_end {
89            return Err(TreeStreamError::TrailingBytes {
90                extra: (payload_end - offset) as u64,
91            });
92        }
93        let tree = Tree::try_from_decoded_entries(entries)?;
94        let found = tree.hash();
95        if found != header.tree_id {
96            return Err(TreeStreamError::HashMismatch {
97                expected: header.tree_id,
98                found,
99            });
100        }
101        if tree
102            .entries()
103            .iter()
104            .map(|entry| entry.encoded_len() as u64)
105            .sum::<u64>()
106            != header.logical_len
107        {
108            return Err(TreeStreamError::Malformed(
109                "declared logical length does not match entries".into(),
110            ));
111        }
112        Ok(tree)
113    }
114}
115
116/// Parse the fixed HTR4 header. Does not read entry frames.
117pub fn decode_header(data: &[u8]) -> Result<TreeHeader, TreeStreamError> {
118    if data.len() < TREE_HEADER_LEN {
119        return Err(TreeStreamError::TruncatedFrame { offset: 0 });
120    }
121    if !is_canonical_tree(data) {
122        return Err(TreeStreamError::Malformed(
123            "bytes are not a canonical HTR4 tree".into(),
124        ));
125    }
126    let version = data[4];
127    if version != TREE_ENCODING_VERSION {
128        return Err(TreeStreamError::UnsupportedVersion { found: version });
129    }
130    let tree_id = ContentHash::from_bytes(
131        data[5..37]
132            .try_into()
133            .map_err(|_| TreeStreamError::Malformed("tree id slice is not 32 bytes".into()))?,
134    );
135    let entry_count = u64::from_le_bytes(
136        data[37..45]
137            .try_into()
138            .map_err(|_| TreeStreamError::Malformed("entry count slice is not 8 bytes".into()))?,
139    );
140    let payload_len =
141        u64::from_le_bytes(data[45..53].try_into().map_err(|_| {
142            TreeStreamError::Malformed("payload length slice is not 8 bytes".into())
143        })?);
144    let logical_len =
145        u64::from_le_bytes(data[53..61].try_into().map_err(|_| {
146            TreeStreamError::Malformed("logical length slice is not 8 bytes".into())
147        })?);
148    Ok(TreeHeader {
149        version,
150        tree_id,
151        entry_count,
152        payload_len,
153        logical_len,
154    })
155}
156
157pub(crate) fn encode_entry_frame(entry: &TreeEntry) -> Result<Vec<u8>, TreeStreamError> {
158    let name = entry.name().as_bytes();
159    let name_len = u16::try_from(name.len()).map_err(|_| {
160        TreeStreamError::Malformed(format!("entry name '{}' exceeds u16", entry.name()))
161    })?;
162    let mut frame = Vec::new();
163    frame.push(entry.mode().to_byte());
164    frame.push(entry.entry_type().to_byte());
165    frame.extend_from_slice(&name_len.to_le_bytes());
166    frame.extend_from_slice(name);
167    encode_target(&mut frame, entry)?;
168    Ok(frame)
169}
170
171pub(crate) fn decode_entry_at(
172    data: &[u8],
173    offset: usize,
174    payload_end: usize,
175) -> Result<(TreeEntry, usize), TreeStreamError> {
176    if offset + 4 > payload_end {
177        return Err(TreeStreamError::TruncatedFrame {
178            offset: offset as u64,
179        });
180    }
181    let frame_len = u32::from_le_bytes(
182        data[offset..offset + 4]
183            .try_into()
184            .map_err(|_| TreeStreamError::Malformed("frame length slice is not 4 bytes".into()))?,
185    ) as usize;
186    let frame_start = offset + 4;
187    let frame_end = frame_start
188        .checked_add(frame_len)
189        .ok_or(TreeStreamError::TruncatedFrame {
190            offset: offset as u64,
191        })?;
192    if frame_end > payload_end {
193        return Err(TreeStreamError::TruncatedFrame {
194            offset: offset as u64,
195        });
196    }
197    let entry = decode_entry_frame(&data[frame_start..frame_end])?;
198    Ok((entry, 4 + frame_len))
199}
200
201pub(crate) fn decode_entry_frame(frame: &[u8]) -> Result<TreeEntry, TreeStreamError> {
202    if frame.len() < 4 {
203        return Err(TreeStreamError::TruncatedFrame { offset: 0 });
204    }
205    let mode = FileMode::from_byte(frame[0]).ok_or_else(|| {
206        TreeStreamError::Malformed(format!("malformed tree entry mode {}", frame[0]))
207    })?;
208    let kind = EntryType::from_byte(frame[1]).ok_or_else(|| {
209        TreeStreamError::Malformed(format!("malformed tree entry kind {}", frame[1]))
210    })?;
211    let name_len = u16::from_le_bytes([frame[2], frame[3]]) as usize;
212    let name_end = 4 + name_len;
213    if frame.len() < name_end {
214        return Err(TreeStreamError::TruncatedFrame { offset: 0 });
215    }
216    let name = std::str::from_utf8(&frame[4..name_end])
217        .map_err(|_| TreeStreamError::Malformed("tree entry name is not UTF-8".into()))?
218        .to_string();
219    let entry = decode_target(name, kind, mode, &frame[name_end..])?;
220    if entry.mode() != mode {
221        return Err(TreeStreamError::Malformed(format!(
222            "tree kind/mode mismatch for {}: {kind:?}/{mode:?}",
223            entry.name()
224        )));
225    }
226    Ok(entry)
227}
228
229fn encode_target(frame: &mut Vec<u8>, entry: &TreeEntry) -> Result<(), TreeStreamError> {
230    match entry.entry_type() {
231        EntryType::Blob | EntryType::Tree | EntryType::Symlink => {
232            frame.extend_from_slice(entry.require_content_hash().as_bytes());
233        }
234        EntryType::Gitlink => {
235            let target = entry.gitlink_target().ok_or_else(|| {
236                TreeStreamError::Malformed("gitlink entry is missing target".into())
237            })?;
238            frame.push(git_format_to_tag(target.format()));
239            frame.extend_from_slice(target.as_bytes());
240        }
241        EntryType::Spoollink => {
242            let (spool, state) = entry.spoollink_target().ok_or_else(|| {
243                TreeStreamError::Malformed("spoollink entry is missing target".into())
244            })?;
245            let spool_bytes = spool.as_str().as_bytes();
246            let spool_len = u16::try_from(spool_bytes.len())
247                .map_err(|_| TreeStreamError::Malformed("spool id exceeds u16".into()))?;
248            frame.extend_from_slice(&spool_len.to_le_bytes());
249            frame.extend_from_slice(spool_bytes);
250            frame.extend_from_slice(state.as_bytes());
251        }
252    }
253    Ok(())
254}
255
256fn decode_target(
257    name: String,
258    kind: EntryType,
259    mode: FileMode,
260    payload: &[u8],
261) -> Result<TreeEntry, TreeStreamError> {
262    match kind {
263        EntryType::Blob => TreeEntry::file(name, take_hash(payload)?, mode == FileMode::Executable)
264            .map_err(TreeStreamError::from),
265        EntryType::Tree => {
266            TreeEntry::directory(name, take_hash(payload)?).map_err(TreeStreamError::from)
267        }
268        EntryType::Symlink => {
269            TreeEntry::symlink(name, take_hash(payload)?).map_err(TreeStreamError::from)
270        }
271        EntryType::Gitlink => decode_gitlink(name, payload),
272        EntryType::Spoollink => decode_spoollink(name, payload),
273    }
274}
275
276fn take_hash(payload: &[u8]) -> Result<ContentHash, TreeStreamError> {
277    let bytes: [u8; 32] = payload
278        .try_into()
279        .map_err(|_| TreeStreamError::Malformed("malformed tree entry object id".into()))?;
280    Ok(ContentHash::from_bytes(bytes))
281}
282
283fn decode_gitlink(name: String, payload: &[u8]) -> Result<TreeEntry, TreeStreamError> {
284    if payload.is_empty() {
285        return Err(TreeStreamError::Malformed(
286            "malformed tree entry object id".into(),
287        ));
288    }
289    let format = git_format_from_tag(payload[0])?;
290    let oid = &payload[1..];
291    let expected = match format {
292        GitObjectFormat::Sha1 => 20,
293        GitObjectFormat::Sha256 => 32,
294    };
295    if oid.len() != expected {
296        return Err(TreeStreamError::Malformed(
297            "malformed tree entry object id".into(),
298        ));
299    }
300    let target = GitObjectId::from_raw(format, oid)
301        .map_err(|err| TreeError::InvalidStructure(format!("invalid gitlink target: {err}")))?;
302    TreeEntry::gitlink(name, target).map_err(TreeStreamError::from)
303}
304
305fn decode_spoollink(name: String, payload: &[u8]) -> Result<TreeEntry, TreeStreamError> {
306    if payload.len() < 2 {
307        return Err(TreeStreamError::TruncatedFrame { offset: 0 });
308    }
309    let spool_len = u16::from_le_bytes([payload[0], payload[1]]) as usize;
310    let spool_end = 2 + spool_len;
311    let state_end = spool_end + 32;
312    if payload.len() != state_end {
313        return Err(TreeStreamError::Malformed(
314            "malformed tree entry object id".into(),
315        ));
316    }
317    let spool = std::str::from_utf8(&payload[2..spool_end])
318        .map_err(|_| TreeStreamError::Malformed("spool id is not UTF-8".into()))?;
319    let spool_id = SpoolId::parse(spool)
320        .map_err(|err| TreeStreamError::Malformed(format!("invalid spool id: {err}")))?;
321    let state =
322        StateId::from_bytes(payload[spool_end..state_end].try_into().map_err(|_| {
323            TreeStreamError::Malformed("spoollink state id is not 32 bytes".into())
324        })?);
325    TreeEntry::spoollink(name, spool_id, state).map_err(TreeStreamError::from)
326}
heddle_object_model/object/tree_canonical.rs

heddle_object_model/object/
tree_canonical.rs
