objects/object/
tree.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Tree types: entries, structure, and supporting enums.
3
4use std::{fmt, path::Path};
5
6use serde::{Deserialize, Serialize};
7
8use super::ContentHash;
9
10// ── TreeError ───────────────────────────────────────────────────────
11
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub enum TreeError {
14    InvalidName(String),
15    InvalidStructure(String),
16}
17
18impl std::error::Error for TreeError {}
19
20impl fmt::Display for TreeError {
21    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
22        match self {
23            TreeError::InvalidName(msg) => write!(f, "invalid tree entry name: {}", msg),
24            TreeError::InvalidStructure(msg) => write!(f, "invalid tree structure: {}", msg),
25        }
26    }
27}
28
29// ── FileMode ────────────────────────────────────────────────────────
30
31#[repr(u8)]
32#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
33pub enum FileMode {
34    Normal,
35    Executable,
36    Symlink,
37}
38
39impl FileMode {
40    pub fn to_byte(&self) -> u8 {
41        match self {
42            FileMode::Normal => 0,
43            FileMode::Executable => 1,
44            FileMode::Symlink => 2,
45        }
46    }
47
48    pub fn from_byte(b: u8) -> Option<Self> {
49        match b {
50            0 => Some(FileMode::Normal),
51            1 => Some(FileMode::Executable),
52            2 => Some(FileMode::Symlink),
53            _ => None,
54        }
55    }
56
57    pub fn to_unix_mode(&self) -> u32 {
58        match self {
59            FileMode::Normal => 0o100644,
60            FileMode::Executable => 0o100755,
61            FileMode::Symlink => 0o120000,
62        }
63    }
64}
65
66// ── EntryType ───────────────────────────────────────────────────────
67
68#[repr(u8)]
69#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
70pub enum EntryType {
71    Blob,
72    Tree,
73    Symlink,
74}
75
76impl EntryType {
77    pub fn to_byte(&self) -> u8 {
78        match self {
79            EntryType::Blob => 0,
80            EntryType::Tree => 1,
81            EntryType::Symlink => 2,
82        }
83    }
84
85    pub fn from_byte(b: u8) -> Option<Self> {
86        match b {
87            0 => Some(EntryType::Blob),
88            1 => Some(EntryType::Tree),
89            2 => Some(EntryType::Symlink),
90            _ => None,
91        }
92    }
93}
94
95// ── TreeEntry ───────────────────────────────────────────────────────
96
97pub fn validate_name(name: &str) -> Result<(), TreeError> {
98    if name.is_empty() {
99        return Err(TreeError::InvalidName("entry name cannot be empty".into()));
100    }
101    if name == "." || name == ".." {
102        return Err(TreeError::InvalidName(format!(
103            "'{}' is not a valid entry name",
104            name
105        )));
106    }
107    if name.contains('/') || name.contains('\\') {
108        return Err(TreeError::InvalidName(
109            "entry name cannot contain path separators".into(),
110        ));
111    }
112    if name.bytes().any(|b| b < 0x20 || b == 0x7f) {
113        return Err(TreeError::InvalidName(
114            "entry name contains control characters".into(),
115        ));
116    }
117    Ok(())
118}
119
120#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
121pub struct TreeEntry {
122    pub name: String,
123    pub mode: FileMode,
124    pub entry_type: EntryType,
125    pub hash: ContentHash,
126}
127
128impl TreeEntry {
129    pub(crate) fn validate(&self) -> Result<(), TreeError> {
130        validate_name(&self.name)
131    }
132
133    pub fn file(
134        name: impl Into<String>,
135        hash: ContentHash,
136        executable: bool,
137    ) -> Result<Self, TreeError> {
138        let name = name.into();
139        validate_name(&name)?;
140        Ok(Self {
141            name,
142            mode: if executable {
143                FileMode::Executable
144            } else {
145                FileMode::Normal
146            },
147            entry_type: EntryType::Blob,
148            hash,
149        })
150    }
151
152    pub fn directory(name: impl Into<String>, hash: ContentHash) -> Result<Self, TreeError> {
153        let name = name.into();
154        validate_name(&name)?;
155        Ok(Self {
156            name,
157            mode: FileMode::Normal,
158            entry_type: EntryType::Tree,
159            hash,
160        })
161    }
162
163    pub fn symlink(name: impl Into<String>, hash: ContentHash) -> Result<Self, TreeError> {
164        let name = name.into();
165        validate_name(&name)?;
166        Ok(Self {
167            name,
168            mode: FileMode::Symlink,
169            entry_type: EntryType::Symlink,
170            hash,
171        })
172    }
173
174    pub fn is_tree(&self) -> bool {
175        self.entry_type == EntryType::Tree
176    }
177
178    pub fn is_blob(&self) -> bool {
179        self.entry_type == EntryType::Blob
180    }
181
182    pub fn is_executable(&self) -> bool {
183        self.mode == FileMode::Executable
184    }
185
186    pub(crate) fn encoded_len(&self) -> usize {
187        1 + 1 + self.hash.as_bytes().len() + self.name.len() + 1
188    }
189
190    pub(crate) fn update_hasher(&self, hasher: &mut blake3::Hasher) {
191        hasher.update(&[self.mode.to_byte()]);
192        hasher.update(&[self.entry_type.to_byte()]);
193        hasher.update(self.hash.as_bytes());
194        hasher.update(self.name.as_bytes());
195        hasher.update(&[0]);
196    }
197}
198
199// ── Tree ────────────────────────────────────────────────────────────
200
201#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
202pub struct Tree {
203    entries: Vec<TreeEntry>,
204}
205
206impl Tree {
207    pub fn new() -> Self {
208        Self {
209            entries: Vec::new(),
210        }
211    }
212
213    pub fn from_entries(mut entries: Vec<TreeEntry>) -> Self {
214        entries.sort_by(|a, b| a.name.cmp(&b.name));
215        Self { entries }
216    }
217
218    pub fn validate(&self) -> Result<(), TreeError> {
219        let mut previous_name: Option<&str> = None;
220        for entry in &self.entries {
221            entry.validate()?;
222            if let Some(previous) = previous_name
223                && previous >= entry.name.as_str()
224            {
225                return Err(TreeError::InvalidStructure(
226                    "entries must be strictly sorted by name".to_string(),
227                ));
228            }
229            previous_name = Some(&entry.name);
230        }
231        Ok(())
232    }
233
234    pub fn entries(&self) -> &[TreeEntry] {
235        &self.entries
236    }
237
238    pub fn get(&self, name: &str) -> Option<&TreeEntry> {
239        let index = self
240            .entries
241            .binary_search_by(|entry| entry.name.as_str().cmp(name))
242            .ok()?;
243        self.entries.get(index)
244    }
245
246    pub fn insert(&mut self, entry: TreeEntry) {
247        self.entries.retain(|e| e.name != entry.name);
248        let pos = self
249            .entries
250            .iter()
251            .position(|e| e.name > entry.name)
252            .unwrap_or(self.entries.len());
253        self.entries.insert(pos, entry);
254    }
255
256    pub fn remove(&mut self, name: &str) -> Option<TreeEntry> {
257        let pos = self.entries.iter().position(|e| e.name == name)?;
258        Some(self.entries.remove(pos))
259    }
260
261    pub fn is_empty(&self) -> bool {
262        self.entries.is_empty()
263    }
264
265    pub fn len(&self) -> usize {
266        self.entries.len()
267    }
268
269    pub fn hash(&self) -> ContentHash {
270        let total_len: usize = self.entries.iter().map(TreeEntry::encoded_len).sum();
271        ContentHash::compute_typed_with_len("tree", total_len as u64, |hasher| {
272            for entry in &self.entries {
273                entry.update_hasher(hasher);
274            }
275        })
276    }
277
278    pub fn iter(&self) -> impl Iterator<Item = &TreeEntry> {
279        self.entries.iter()
280    }
281
282    pub fn get_path(&self, path: &Path) -> Option<&TreeEntry> {
283        let name = path.file_name()?.to_str()?;
284        if path.parent().is_none_or(|p| p.as_os_str().is_empty()) {
285            self.get(name)
286        } else {
287            None
288        }
289    }
290}
291
292impl Default for Tree {
293    fn default() -> Self {
294        Self::new()
295    }
296}
297
298impl IntoIterator for Tree {
299    type Item = TreeEntry;
300    type IntoIter = std::vec::IntoIter<TreeEntry>;
301
302    fn into_iter(self) -> Self::IntoIter {
303        self.entries.into_iter()
304    }
305}
306
307impl<'a> IntoIterator for &'a Tree {
308    type Item = &'a TreeEntry;
309    type IntoIter = std::slice::Iter<'a, TreeEntry>;
310
311    fn into_iter(self) -> Self::IntoIter {
312        self.entries.iter()
313    }
314}
objects/object/tree.rs

objects/object/
tree.rs
