gix_object/tree/
mod.rs

1use std::{cell::RefCell, cmp::Ordering};
2
3use crate::{
4    Tree, TreeRef,
5    bstr::{BStr, BString},
6    tree,
7};
8
9///
10pub mod editor;
11
12mod ref_iter;
13pub use ref_iter::next_entry;
14
15/// Compare entry names according to Git's canonical tree ordering.
16///
17/// Trees compare as if their name had a trailing `/`, whereas non-tree entries compare as if their name ended in a
18/// NUL byte. This distinction matters when one name is a prefix of another.
19pub fn name_order(a: &[u8], a_is_tree: bool, b: &[u8], b_is_tree: bool) -> Ordering {
20    let common = a.len().min(b.len());
21    a[..common].cmp(&b[..common]).then_with(|| {
22        let a = a.get(common).or_else(|| a_is_tree.then_some(&b'/'));
23        let b = b.get(common).or_else(|| b_is_tree.then_some(&b'/'));
24        a.cmp(&b)
25    })
26}
27
28///
29pub mod write;
30
31/// The state needed to apply edits instantly to in-memory trees.
32///
33/// It's made so that each tree is looked at in the object database at most once, and held in memory for
34/// all edits until everything is flushed to write all changed trees.
35///
36/// The editor is optimized to edit existing trees, but can deal with building entirely new trees as well
37/// with some penalties.
38#[doc(alias = "TreeUpdateBuilder", alias = "git2")]
39#[derive(Clone)]
40pub struct Editor<'a> {
41    /// A way to lookup trees.
42    find: &'a dyn crate::FindExt,
43    /// The kind of hashes to produce>
44    object_hash: gix_hash::Kind,
45    /// All trees we currently hold in memory. Each of these may change while adding and removing entries.
46    /// null-object-ids mark tree-entries whose value we don't know yet, they are placeholders that will be
47    /// dropped when writing at the latest.
48    trees: std::collections::HashMap<BString, Tree>,
49    /// A buffer to build up paths when finding the tree to edit.
50    path_buf: RefCell<BString>,
51    /// Our buffer for storing tree-data in, right before decoding it.
52    tree_buf: Vec<u8>,
53}
54
55/// The mode of items storable in a tree, similar to the file mode on a unix file system.
56///
57/// Used in [`mutable::Entry`][crate::tree::Entry] and [`EntryRef`].
58///
59/// Note that even though it can be created from any `u16`, it should be preferable to
60/// create it by converting [`EntryKind`] into `EntryMode`.
61#[derive(Clone, Copy, PartialEq, Eq, Ord, PartialOrd, Hash)]
62#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
63pub struct EntryMode {
64    // Represents the value read from Git, except that "040000" is represented with 0o140000 but
65    // "40000" is represented with 0o40000.
66    internal: u16,
67}
68
69impl TryFrom<u32> for tree::EntryMode {
70    type Error = u32;
71    fn try_from(mode: u32) -> Result<Self, Self::Error> {
72        Ok(match mode {
73            0o40000 | 0o120000 | 0o160000 => EntryMode { internal: mode as u16 },
74            blob_mode if blob_mode & 0o100000 == 0o100000 => EntryMode { internal: mode as u16 },
75            _ => return Err(mode),
76        })
77    }
78}
79
80impl EntryMode {
81    /// Expose the value as u16 (lossy, unlike the internal representation that is hidden).
82    pub const fn value(self) -> u16 {
83        // Demangle the hack: In the case where the second leftmost octet is 4 (Tree), the leftmost bit is
84        // there to represent whether the bytes representation should have 5 or 6 octets.
85        if self.internal & IFMT == 0o140000 {
86            0o040000
87        } else {
88            self.internal
89        }
90    }
91
92    /// Return the representation as used in the git internal format, which is octal and written
93    /// to the `backing` buffer. The respective sub-slice that was written to is returned.
94    pub fn as_bytes<'a>(&self, backing: &'a mut [u8; 6]) -> &'a BStr {
95        if self.internal == 0 {
96            std::slice::from_ref(&b'0')
97        } else {
98            for (idx, backing_octet) in backing.iter_mut().enumerate() {
99                let bit_pos = 3 /* because base 8 and 2^3 == 8*/ * (6 - idx - 1);
100                let oct_mask = 0b111 << bit_pos;
101                let digit = (self.internal & oct_mask) >> bit_pos;
102                *backing_octet = b'0' + digit as u8;
103            }
104            // Hack: `0o140000` represents `"040000"`, `0o40000` represents `"40000"`.
105            if backing[1] == b'4' {
106                if backing[0] == b'1' {
107                    backing[0] = b'0';
108                    &backing[0..6]
109                } else {
110                    &backing[1..6]
111                }
112            } else {
113                &backing[0..6]
114            }
115        }
116        .into()
117    }
118
119    /// Construct an EntryMode from bytes represented as in the git internal format
120    /// Return the mode and the remainder of the bytes.
121    pub(crate) fn extract_from_bytes(i: &[u8]) -> Option<(Self, &'_ [u8])> {
122        let mut mode = 0;
123        if i.is_empty() {
124            return None;
125        }
126
127        // Happy path: space is at index 6
128        let space_pos = if i.get(6) == Some(&b' ') && i.get(5) != Some(&b' ') {
129            for b in i.iter().take(6) {
130                let b = b.wrapping_sub(b'0') as u16;
131                // Not a pure octal input.
132                // Performance matters here, so `!(b'0'..=b'7').contains(&b)` won't do.
133                if b > 7 {
134                    return None;
135                }
136                mode = (mode << 3) + b;
137            }
138            6
139        }
140        // Space is not at index 6, we must find it.
141        else {
142            let mut idx = 0;
143            let mut space_pos = 0;
144
145            // const fn, this is why we can't have nice things (like `.iter().any()`).
146            while idx < i.len() {
147                let b = i[idx].wrapping_sub(b'0') as u16;
148                // Delimiter, return what we got
149                if b == b' '.wrapping_sub(b'0') as u16 {
150                    space_pos = idx;
151                    break;
152                }
153                // Not a pure octal input.
154                // Performance matters here, so `!(b'0'..=b'7').contains(&b)` won't do.
155                if b > 7 {
156                    return None;
157                }
158                // More than 6 octal digits we must have hit the delimiter or the input was malformed.
159                if idx > 6 {
160                    return None;
161                }
162                mode = (mode << 3) + b;
163                idx += 1;
164            }
165
166            space_pos
167        };
168
169        // Hack: `0o140000` represents `"040000"`, `0o40000` represents `"40000"`.
170        if mode == 0o040000 && i[0] == b'0' {
171            mode += 0o100000;
172        }
173        Some((Self { internal: mode }, &i[(space_pos + 1)..]))
174    }
175
176    /// Construct an EntryMode from bytes represented as in the git internal format.
177    pub fn from_bytes(i: &[u8]) -> Option<Self> {
178        Self::extract_from_bytes(i).map(|(mode, _rest)| mode)
179    }
180}
181
182impl std::fmt::Debug for EntryMode {
183    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
184        write!(f, "EntryMode(0o{})", self.as_bytes(&mut Default::default()))
185    }
186}
187
188impl std::fmt::Octal for EntryMode {
189    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
190        write!(f, "{}", self.as_bytes(&mut Default::default()))
191    }
192}
193
194/// A discretized version of ideal and valid values for entry modes.
195///
196/// Note that even though it can represent every valid [mode](EntryMode), it might
197/// lose information due to that as well.
198#[derive(Clone, Copy, PartialEq, Eq, Debug, Ord, PartialOrd, Hash)]
199#[repr(u16)]
200#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
201pub enum EntryKind {
202    /// A tree, or directory
203    Tree = 0o040000u16,
204    /// A file that is not executable
205    Blob = 0o100644,
206    /// A file that is executable
207    BlobExecutable = 0o100755,
208    /// A symbolic link
209    Link = 0o120000,
210    /// A commit of a git submodule
211    Commit = 0o160000,
212}
213
214impl From<EntryKind> for EntryMode {
215    fn from(value: EntryKind) -> Self {
216        EntryMode { internal: value as u16 }
217    }
218}
219
220impl From<EntryMode> for EntryKind {
221    fn from(value: EntryMode) -> Self {
222        value.kind()
223    }
224}
225
226/// Serialization
227impl EntryKind {
228    /// Return the representation as used in the git internal format.
229    pub fn as_octal_str(&self) -> &'static BStr {
230        use EntryKind::*;
231        let bytes: &[u8] = match self {
232            Tree => b"40000",
233            Blob => b"100644",
234            BlobExecutable => b"100755",
235            Link => b"120000",
236            Commit => b"160000",
237        };
238        bytes.into()
239    }
240}
241
242const IFMT: u16 = 0o170000;
243
244impl EntryMode {
245    /// Discretize the raw mode into an enum with well-known state while dropping unnecessary details.
246    pub const fn kind(&self) -> EntryKind {
247        let etype = self.value() & IFMT;
248        if etype == 0o100000 {
249            if self.value() & 0o000100 == 0o000100 {
250                EntryKind::BlobExecutable
251            } else {
252                EntryKind::Blob
253            }
254        } else if etype == EntryKind::Link as u16 {
255            EntryKind::Link
256        } else if etype == EntryKind::Tree as u16 {
257            EntryKind::Tree
258        } else {
259            EntryKind::Commit
260        }
261    }
262
263    /// Return true if this entry mode represents a Tree/directory
264    pub const fn is_tree(&self) -> bool {
265        self.value() & IFMT == EntryKind::Tree as u16
266    }
267
268    /// Return true if this entry mode represents the commit of a submodule.
269    pub const fn is_commit(&self) -> bool {
270        self.value() & IFMT == EntryKind::Commit as u16
271    }
272
273    /// Return true if this entry mode represents a symbolic link
274    pub const fn is_link(&self) -> bool {
275        self.value() & IFMT == EntryKind::Link as u16
276    }
277
278    /// Return true if this entry mode represents anything BUT Tree/directory
279    pub const fn is_no_tree(&self) -> bool {
280        self.value() & IFMT != EntryKind::Tree as u16
281    }
282
283    /// Return true if the entry is any kind of blob.
284    pub const fn is_blob(&self) -> bool {
285        self.value() & IFMT == 0o100000
286    }
287
288    /// Return true if the entry is an executable blob.
289    pub const fn is_executable(&self) -> bool {
290        matches!(self.kind(), EntryKind::BlobExecutable)
291    }
292
293    /// Return true if the entry is any kind of blob or symlink.
294    pub const fn is_blob_or_symlink(&self) -> bool {
295        matches!(
296            self.kind(),
297            EntryKind::Blob | EntryKind::BlobExecutable | EntryKind::Link
298        )
299    }
300
301    /// Represent the mode as descriptive string.
302    pub const fn as_str(&self) -> &'static str {
303        use EntryKind::*;
304        match self.kind() {
305            Tree => "tree",
306            Blob => "blob",
307            BlobExecutable => "exe",
308            Link => "link",
309            Commit => "commit",
310        }
311    }
312}
313
314impl TreeRef<'_> {
315    /// Convert this instance into its own version, creating a copy of all data.
316    ///
317    /// This will temporarily allocate an extra copy in memory, so at worst three copies of the tree exist
318    /// at some intermediate point in time. Use [`Self::into_owned()`] to avoid this.
319    pub fn to_owned(&self) -> Tree {
320        self.clone().into()
321    }
322
323    /// Convert this instance into its own version, creating a copy of all data.
324    pub fn into_owned(self) -> Tree {
325        self.into()
326    }
327}
328
329/// An element of a [`TreeRef`][crate::TreeRef::entries].
330#[derive(PartialEq, Eq, Debug, Hash, Clone, Copy)]
331#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
332pub struct EntryRef<'a> {
333    /// The kind of object to which `oid` is pointing.
334    pub mode: tree::EntryMode,
335    /// The name of the file in the parent tree.
336    pub filename: &'a BStr,
337    /// The id of the object representing the entry.
338    // TODO: figure out how these should be called. id or oid? It's inconsistent around the codebase.
339    //       Answer: make it 'id', as in `git2`
340    #[cfg_attr(feature = "serde", serde(borrow))]
341    pub oid: &'a gix_hash::oid,
342}
343
344impl PartialOrd for EntryRef<'_> {
345    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
346        Some(self.cmp(other))
347    }
348}
349
350impl Ord for EntryRef<'_> {
351    fn cmp(&self, b: &Self) -> Ordering {
352        name_order(self.filename, self.mode.is_tree(), b.filename, b.mode.is_tree())
353    }
354}
355
356/// An entry in a [`Tree`], similar to an entry in a directory.
357#[derive(PartialEq, Eq, Debug, Hash, Clone)]
358#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
359pub struct Entry {
360    /// The kind of object to which `oid` is pointing to.
361    pub mode: EntryMode,
362    /// The name of the file in the parent tree.
363    pub filename: BString,
364    /// The id of the object representing the entry.
365    pub oid: gix_hash::ObjectId,
366}
367
368impl PartialOrd for Entry {
369    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
370        Some(self.cmp(other))
371    }
372}
373
374impl Ord for Entry {
375    fn cmp(&self, b: &Self) -> Ordering {
376        name_order(&self.filename, self.mode.is_tree(), &b.filename, b.mode.is_tree())
377    }
378}
gix_object/tree/mod.rs

gix_object/tree/
mod.rs
