heddle_object_model/object/
tree_git_layout.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Git layout of a tree imported from a non-canonical Git tree (heddle#2018).
3//!
4//! Git accepts trees that Git itself never writes: zero-padded or odd modes
5//! (`040000`, `100664`) and entries out of Git's canonical order. Heddle keeps
6//! the canonical meaning of such a tree (a `100664` entry is a regular file) and
7//! records the source layout next to it, so export rebuilds the source tree
8//! byte-for-byte and the commit id and every descendant id survive.
9//!
10//! Both pieces are optional and present only when the source differs from what
11//! Git would write. Trees that do not use them hash and encode exactly as they
12//! did before the extension existed.
13//!
14//! On the wire the extension is a trailer after an entry's target, announced by
15//! two otherwise-unused bits of the entry's mode byte. The same trailer and the
16//! same flag bits go into the tree hash preimage, so both fields are part of
17//! the tree's identity and a fetch verifies them with no new transport.
18
19use std::{cmp::Ordering, num::NonZeroU32};
20
21use sley_core::{ObjectFormat as GitObjectFormat, ObjectId as GitObjectId};
22
23use super::{EntryType, TreeEntry, TreeError};
24
25/// Mode-byte flag: a raw Git mode trailer follows the entry's target.
26pub(crate) const ENTRY_FLAG_RAW_GIT_MODE: u8 = 0x80;
27/// Mode-byte flag: a source-position trailer follows the entry's target.
28pub(crate) const ENTRY_FLAG_SOURCE_POSITION: u8 = 0x40;
29/// Every flag bit. The remaining bits hold the mode byte (always `< 0x40`).
30pub(crate) const ENTRY_LAYOUT_FLAGS: u8 = ENTRY_FLAG_RAW_GIT_MODE | ENTRY_FLAG_SOURCE_POSITION;
31const RAW_GIT_MODE_TRAILER_LEN: usize = 5;
32const SOURCE_POSITION_TRAILER_LEN: usize = 4;
33/// Git's file-type bits (`S_IFMT`).
34const GIT_TYPE_MASK: u32 = 0o170000;
35
36/// A Git tree-entry mode exactly as written in a source tree.
37///
38/// Git writes a mode as octal digits without leading zeros. Git also *reads*
39/// zero-padded digits and permission bits it would never write. This keeps
40/// both: the numeric value plus the count of leading zeros reproduce the
41/// source digits exactly.
42#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
43pub struct RawGitMode {
44    // Never zero: a mode needs a significant digit. The niche keeps
45    // `Option<RawGitMode>` the size of `RawGitMode` on every tree entry.
46    value: NonZeroU32,
47    leading_zeros: u8,
48}
49
50impl RawGitMode {
51    /// Parse the octal digits of a tree-entry mode, as they appear before the
52    /// space in a raw Git tree.
53    pub fn parse(digits: &[u8]) -> Result<Self, TreeError> {
54        let invalid = || {
55            TreeError::InvalidStructure(format!(
56                "invalid git tree mode {:?}",
57                String::from_utf8_lossy(digits)
58            ))
59        };
60        let leading = digits.iter().take_while(|digit| **digit == b'0').count();
61        let significant = &digits[leading..];
62        if significant.is_empty() || !digits.iter().all(|digit| (b'0'..=b'7').contains(digit)) {
63            return Err(invalid());
64        }
65        let mut value = 0u32;
66        for digit in significant {
67            value = value
68                .checked_mul(8)
69                .and_then(|value| value.checked_add(u32::from(digit - b'0')))
70                .ok_or_else(invalid)?;
71        }
72        Ok(Self {
73            value: NonZeroU32::new(value).ok_or_else(invalid)?,
74            leading_zeros: u8::try_from(leading).map_err(|_| invalid())?,
75        })
76    }
77
78    /// The canonical mode Git writes for an entry of `entry_type`. `None` for
79    /// a spoollink, which is not a Git object.
80    pub fn canonical(entry_type: EntryType, executable: bool) -> Option<Self> {
81        let value = match entry_type {
82            EntryType::Tree => 0o040000,
83            EntryType::Blob if executable => 0o100755,
84            EntryType::Blob => 0o100644,
85            EntryType::Symlink => 0o120000,
86            EntryType::Gitlink => 0o160000,
87            EntryType::Spoollink => return None,
88        };
89        Some(Self {
90            value: NonZeroU32::new(value)?,
91            leading_zeros: 0,
92        })
93    }
94
95    /// The numeric mode.
96    pub fn value(self) -> u32 {
97        self.value.get()
98    }
99
100    /// The entry kind Git reads this mode as, or `None` for a mode Heddle
101    /// cannot represent. Follows Git's own reading: only the file-type bits
102    /// pick the kind.
103    pub fn entry_type(self) -> Option<EntryType> {
104        let value = self.value();
105        if value & !0o177777 != 0 {
106            return None;
107        }
108        match value & GIT_TYPE_MASK {
109            0o040000 => Some(EntryType::Tree),
110            0o100000 => Some(EntryType::Blob),
111            0o120000 => Some(EntryType::Symlink),
112            0o160000 => Some(EntryType::Gitlink),
113            _ => None,
114        }
115    }
116
117    /// Whether Git checks a regular file with this mode out as executable:
118    /// the owner execute bit, as in Git's `canon_mode`.
119    pub fn is_executable(self) -> bool {
120        self.entry_type() == Some(EntryType::Blob) && self.value() & 0o100 != 0
121    }
122
123    /// Append the exact source digits.
124    pub fn write_digits(self, out: &mut Vec<u8>) {
125        out.extend(std::iter::repeat_n(b'0', usize::from(self.leading_zeros)));
126        out.extend_from_slice(format!("{:o}", self.value()).as_bytes());
127    }
128
129    fn is_canonical_for(self, entry_type: EntryType, executable: bool) -> bool {
130        Self::canonical(entry_type, executable) == Some(self)
131    }
132}
133
134impl TreeEntry {
135    /// Check that `mode` describes this entry and is worth recording: it must
136    /// read as this entry's kind (and executable bit), and differ from the
137    /// mode Git would write for it.
138    pub(crate) fn check_raw_git_mode(&self, mode: RawGitMode) -> Result<(), TreeError> {
139        let entry_type = self.entry_type();
140        let executable = self.is_executable();
141        if mode.entry_type() != Some(entry_type)
142            || (entry_type == EntryType::Blob && mode.is_executable() != executable)
143        {
144            return Err(TreeError::InvalidStructure(format!(
145                "git mode {:o} does not describe {:?} entry '{}'",
146                mode.value(),
147                entry_type,
148                self.name()
149            )));
150        }
151        if mode.is_canonical_for(entry_type, executable) {
152            return Err(TreeError::InvalidStructure(format!(
153                "entry '{}' records its canonical git mode as a raw mode",
154                self.name()
155            )));
156        }
157        Ok(())
158    }
159
160    /// The mode-byte flags announcing this entry's layout trailer.
161    pub(crate) fn layout_flags(&self, source_position: Option<u32>) -> u8 {
162        let mut flags = 0;
163        if self.raw_git_mode().is_some() {
164            flags |= ENTRY_FLAG_RAW_GIT_MODE;
165        }
166        if source_position.is_some() {
167            flags |= ENTRY_FLAG_SOURCE_POSITION;
168        }
169        flags
170    }
171
172    /// Emit this entry's layout trailer: raw mode (`u32` LE value, `u8`
173    /// leading zeros) then source position (`u32` LE), each only when present.
174    pub(crate) fn write_layout_trailer(
175        &self,
176        source_position: Option<u32>,
177        mut emit: impl FnMut(&[u8]),
178    ) {
179        if let Some(mode) = self.raw_git_mode() {
180            emit(&mode.value().to_le_bytes());
181            emit(&[mode.leading_zeros]);
182        }
183        if let Some(position) = source_position {
184            emit(&position.to_le_bytes());
185        }
186    }
187}
188
189/// One entry of a raw Git tree object, with its mode exactly as written.
190#[derive(Clone, Debug, PartialEq, Eq)]
191pub struct GitTreeEntryRef<'a> {
192    pub mode: RawGitMode,
193    pub name: &'a [u8],
194    pub oid: GitObjectId,
195}
196
197/// Parse a raw Git tree body (`<mode> SP <name> NUL <oid>`...) in source
198/// order, keeping each mode's digits. Git porcelain parsers turn the digits
199/// into a number, which loses `040000` versus `40000`; importers that must
200/// reproduce the source tree read it through this instead.
201pub fn parse_git_tree(
202    format: GitObjectFormat,
203    body: &[u8],
204) -> Result<Vec<GitTreeEntryRef<'_>>, TreeError> {
205    let malformed = |what: &str| TreeError::InvalidStructure(format!("malformed git tree: {what}"));
206    let mut entries = Vec::new();
207    let mut rest = body;
208    while !rest.is_empty() {
209        let space = rest
210            .iter()
211            .position(|byte| *byte == b' ')
212            .ok_or_else(|| malformed("unterminated mode"))?;
213        let mode = RawGitMode::parse(&rest[..space])?;
214        rest = &rest[space + 1..];
215        let nul = rest
216            .iter()
217            .position(|byte| *byte == 0)
218            .ok_or_else(|| malformed("unterminated name"))?;
219        if nul == 0 {
220            return Err(malformed("empty name"));
221        }
222        let name = &rest[..nul];
223        rest = &rest[nul + 1..];
224        let oid_len = format.raw_len();
225        if rest.len() < oid_len {
226            return Err(malformed("truncated object id"));
227        }
228        let oid = GitObjectId::from_raw(format, &rest[..oid_len])
229            .map_err(|error| malformed(&error.to_string()))?;
230        rest = &rest[oid_len..];
231        entries.push(GitTreeEntryRef { mode, name, oid });
232    }
233    Ok(entries)
234}
235
236/// Byte length of the trailer announced by `flags`.
237pub(crate) fn layout_trailer_len(flags: u8) -> usize {
238    let mut len = 0;
239    if flags & ENTRY_FLAG_RAW_GIT_MODE != 0 {
240        len += RAW_GIT_MODE_TRAILER_LEN;
241    }
242    if flags & ENTRY_FLAG_SOURCE_POSITION != 0 {
243        len += SOURCE_POSITION_TRAILER_LEN;
244    }
245    len
246}
247
248/// Attach the trailer announced by `flags` (exactly [`layout_trailer_len`]
249/// bytes) to a decoded entry and return its source position. Rejects a raw
250/// mode that is canonical or does not describe the entry, so every tree has
251/// exactly one encoding.
252pub(crate) fn apply_layout_trailer(
253    entry: TreeEntry,
254    flags: u8,
255    trailer: &[u8],
256) -> Result<(TreeEntry, Option<u32>), TreeError> {
257    let malformed = || TreeError::InvalidStructure("malformed tree entry layout trailer".into());
258    if trailer.len() != layout_trailer_len(flags) {
259        return Err(malformed());
260    }
261    let mut rest = trailer;
262    let mut entry = entry;
263    if flags & ENTRY_FLAG_RAW_GIT_MODE != 0 {
264        let (mode, tail) = rest.split_at(RAW_GIT_MODE_TRAILER_LEN);
265        let value = u32::from_le_bytes(mode[..4].try_into().map_err(|_| malformed())?);
266        let mode = RawGitMode {
267            value: NonZeroU32::new(value).ok_or_else(malformed)?,
268            leading_zeros: mode[4],
269        };
270        entry.check_raw_git_mode(mode)?;
271        entry = entry.with_checked_raw_git_mode(mode);
272        rest = tail;
273    }
274    let position = if flags & ENTRY_FLAG_SOURCE_POSITION != 0 {
275        Some(u32::from_le_bytes(
276            rest.try_into().map_err(|_| malformed())?,
277        ))
278    } else {
279        None
280    };
281    Ok((entry, position))
282}
283
284/// Split a stored mode byte into its layout flags and the plain mode byte.
285pub(crate) fn split_layout_flags(byte: u8) -> (u8, u8) {
286    (byte & ENTRY_LAYOUT_FLAGS, byte & !ENTRY_LAYOUT_FLAGS)
287}
288
289/// Git's canonical tree order: byte order of the names, where a tree's name
290/// compares as if it ended in `/` (Git's `base_name_compare`).
291pub(crate) fn git_canonical_order(left: &TreeEntry, right: &TreeEntry) -> Ordering {
292    let left_name = left.name().as_bytes();
293    let right_name = right.name().as_bytes();
294    let shared = left_name.len().min(right_name.len());
295    left_name[..shared]
296        .cmp(&right_name[..shared])
297        .then_with(|| {
298            let terminator = |entry: &TreeEntry| if entry.is_tree() { b'/' } else { 0 };
299            let left_next = left_name.get(shared).copied().unwrap_or(terminator(left));
300            let right_next = right_name.get(shared).copied().unwrap_or(terminator(right));
301            left_next.cmp(&right_next)
302        })
303}
304
305#[cfg(test)]
306mod tests {
307    use super::*;
308    use crate::object::ContentHash;
309
310    fn mode(digits: &str) -> RawGitMode {
311        RawGitMode::parse(digits.as_bytes()).expect("valid mode")
312    }
313
314    fn digits(mode: RawGitMode) -> String {
315        let mut out = Vec::new();
316        mode.write_digits(&mut out);
317        String::from_utf8(out).expect("ascii")
318    }
319
320    #[test]
321    fn an_absent_raw_mode_costs_no_tag() {
322        assert_eq!(
323            std::mem::size_of::<Option<RawGitMode>>(),
324            std::mem::size_of::<RawGitMode>()
325        );
326    }
327
328    #[test]
329    fn raw_modes_reproduce_their_source_digits() {
330        for source in ["040000", "100664", "0100644", "40000", "120777", "160000"] {
331            assert_eq!(digits(mode(source)), source);
332        }
333    }
334
335    #[test]
336    fn raw_modes_read_as_git_reads_them() {
337        assert_eq!(mode("040000").entry_type(), Some(EntryType::Tree));
338        assert_eq!(mode("100664").entry_type(), Some(EntryType::Blob));
339        assert!(!mode("100664").is_executable());
340        assert!(mode("100744").is_executable());
341        // Git reads only the owner execute bit.
342        assert!(!mode("100645").is_executable());
343        assert_eq!(mode("120777").entry_type(), Some(EntryType::Symlink));
344        assert_eq!(mode("160000").entry_type(), Some(EntryType::Gitlink));
345        assert_eq!(mode("644").entry_type(), None);
346        assert_eq!(mode("1100644").entry_type(), None);
347    }
348
349    #[test]
350    fn malformed_mode_digits_are_rejected() {
351        for source in ["", "000", "1006a4", "100 644", "77777777777777"] {
352            assert!(
353                RawGitMode::parse(source.as_bytes()).is_err(),
354                "{source:?} must be rejected"
355            );
356        }
357    }
358
359    #[test]
360    fn git_tree_parser_keeps_mode_digits_and_source_order() {
361        let mut body = Vec::new();
362        for (mode, name, fill) in [("100664", "b", 1u8), ("040000", "a", 2u8)] {
363            body.extend_from_slice(mode.as_bytes());
364            body.push(b' ');
365            body.extend_from_slice(name.as_bytes());
366            body.push(0);
367            body.extend_from_slice(&[fill; 20]);
368        }
369        let entries = parse_git_tree(GitObjectFormat::Sha1, &body).unwrap();
370        let names: Vec<&[u8]> = entries.iter().map(|entry| entry.name).collect();
371        assert_eq!(names, [b"b".as_slice(), b"a".as_slice()]);
372        assert_eq!(digits(entries[1].mode), "040000");
373        assert!(parse_git_tree(GitObjectFormat::Sha1, &body[..body.len() - 1]).is_err());
374    }
375
376    #[test]
377    fn git_order_sorts_trees_as_if_they_end_in_a_slash() {
378        let hash = ContentHash::compute(b"x");
379        let dir = TreeEntry::directory("lib", hash).unwrap();
380        let file = TreeEntry::file("lib.rs", hash, false).unwrap();
381        let plain = TreeEntry::file("lib", hash, false).unwrap();
382        // Native byte order puts `lib` first; Git puts `lib.rs` before `lib/`.
383        assert_eq!(git_canonical_order(&file, &dir), Ordering::Less);
384        assert_eq!(git_canonical_order(&plain, &file), Ordering::Less);
385    }
386}
387
388#[cfg(test)]
389#[path = "tree_git_layout_tests.rs"]
390mod layout_tests;
heddle_object_model/object/tree_git_layout.rs

heddle_object_model/object/
tree_git_layout.rs
