git_async/object/
tree.rs

1use crate::{
2    error::GResult,
3    file_system::FileSystem,
4    object::{Object, ObjectId},
5    parsing::{ParseError, ParseResult},
6    repo::Repo,
7    subslice_range::SubsliceRange,
8};
9use accessory::Accessors;
10use alloc::vec::Vec;
11use core::{fmt::Debug, iter::FusedIterator, ops::Range};
12use nom::{
13    Parser,
14    branch::alt,
15    bytes::complete::{tag, take, take_till},
16    character::complete::char,
17    combinator::all_consuming,
18    multi::many,
19    sequence::terminated,
20};
21
22/// The type of an entry in a tree
23#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Copy, Clone)]
24pub enum TreeEntryType {
25    /// A non-executable file pointing to a blob
26    File,
27    /// An executable file pointing to a blob
28    Executable,
29    /// A symbolic link
30    ///
31    /// Symbolic links in git are encoded as a tree entry of type symlink
32    /// pointing to a blob. The blob's content is the path of the symlink
33    /// target.
34    Symlink,
35    /// A sub-tree, i.e. a subdirectory
36    Tree,
37    /// A pointer to a commit
38    ///
39    /// This is used for git submodules.
40    Commit,
41}
42
43/// An entry in a tree object
44///
45/// It holds a reference to the data in the [`Tree`].
46#[derive(Accessors, Clone, PartialEq, Eq)]
47pub struct TreeEntry<'a> {
48    /// The name of the tree entry
49    #[access(get(cp))]
50    name: &'a [u8],
51
52    /// The type of the tree entry
53    #[access(get(cp))]
54    entry_type: TreeEntryType,
55
56    /// The [`ObjectId`] that the entry points to
57    #[access(get(cp))]
58    id: ObjectId,
59}
60
61impl TreeEntry<'_> {
62    /// Look up the target object using the provided [`Repo`].
63    ///
64    /// Returns `None` if the tree entry is a commit, because in that case it is
65    /// a pointer to a commit in an external repository.
66    pub async fn lookup<F: FileSystem>(&self, repo: &Repo<F>) -> GResult<Option<Object>> {
67        if self.entry_type == TreeEntryType::Commit {
68            Ok(None)
69        } else {
70            Ok(Some(repo.lookup_object(self.id).await?))
71        }
72    }
73}
74
75#[derive(Clone)]
76struct RangeTreeEntry {
77    name: Range<usize>,
78    entry_type: TreeEntryType,
79    id: ObjectId,
80}
81
82impl RangeTreeEntry {
83    fn parser(body: &[u8]) -> impl Fn(&[u8]) -> ParseResult<&[u8], Self> {
84        |input: &[u8]| {
85            let entry_type_parser = alt((
86                tag("40000").map(|_| TreeEntryType::Tree),
87                tag("100644").map(|_| TreeEntryType::File),
88                tag("100755").map(|_| TreeEntryType::Executable),
89                tag("120000").map(|_| TreeEntryType::Symlink),
90                tag("160000").map(|_| TreeEntryType::Commit),
91            ));
92            let mut p = (
93                terminated(entry_type_parser, char(' ')),
94                terminated(take_till(|c| c == b'\0'), char('\0')),
95                take(20usize)
96                    .map(|bytes| ObjectId::from_bytes(<[u8; 20]>::try_from(bytes).unwrap())),
97            );
98            let (rest, (entry_type, name, id)) = p.parse(input)?;
99            Ok((
100                rest,
101                RangeTreeEntry {
102                    name: body.subslice_range_stable(name).unwrap(),
103                    entry_type,
104                    id,
105                },
106            ))
107        }
108    }
109}
110
111/// An iterator over the entries in a tree object
112pub struct TreeEntryIter<'a> {
113    body: &'a [u8],
114    entries: &'a [RangeTreeEntry],
115    pos: usize,
116}
117
118impl<'a> Iterator for TreeEntryIter<'a> {
119    type Item = TreeEntry<'a>;
120
121    fn next(&mut self) -> Option<Self::Item> {
122        let entry = self.entries.get(self.pos)?;
123        self.pos += 1;
124        Some(TreeEntry {
125            name: &self.body[entry.name.clone()],
126            entry_type: entry.entry_type,
127            id: entry.id,
128        })
129    }
130
131    fn size_hint(&self) -> (usize, Option<usize>) {
132        (
133            self.entries.len() - self.pos,
134            Some(self.entries.len() - self.pos),
135        )
136    }
137}
138
139impl FusedIterator for TreeEntryIter<'_> {}
140impl ExactSizeIterator for TreeEntryIter<'_> {}
141
142/// A tree object
143#[derive(Accessors, Clone)]
144pub struct Tree {
145    /// The [`ObjectId`] of the tree
146    #[access(get(cp))]
147    id: ObjectId,
148
149    /// The raw data in the object
150    #[access(get(ty(&[u8])))]
151    body: Vec<u8>,
152
153    entries: Vec<RangeTreeEntry>,
154}
155
156impl PartialEq for Tree {
157    fn eq(&self, other: &Self) -> bool {
158        self.id == other.id
159    }
160}
161impl Eq for Tree {}
162impl PartialOrd for Tree {
163    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
164        Some(self.cmp(other))
165    }
166}
167impl Ord for Tree {
168    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
169        self.id.cmp(&other.id)
170    }
171}
172
173impl Tree {
174    /// Get an iterator over the entries in the tree.
175    pub fn entries(&self) -> TreeEntryIter<'_> {
176        TreeEntryIter {
177            body: self.body.as_slice(),
178            entries: self.entries.as_slice(),
179            pos: 0,
180        }
181    }
182
183    /// Wrap the [`Tree`] as a generic [`Object`].
184    pub fn as_object(self) -> Object {
185        Object::Tree(self)
186    }
187
188    pub(crate) fn parse(id: ObjectId, body: Vec<u8>) -> Result<Self, ParseError> {
189        let (_, entries): (_, Vec<_>) =
190            all_consuming(many(0.., RangeTreeEntry::parser(&body))).parse(&body)?;
191        Ok(Self { id, body, entries })
192    }
193}
194
195#[cfg(test)]
196mod tests {
197    use super::*;
198    use hex_literal::hex;
199
200    const ZERO_OID: ObjectId = ObjectId::from_bytes([0; 20]);
201
202    #[test]
203    fn parse_tree() {
204        let mut data = Vec::new();
205        data.extend_from_slice(b"40000 a-directory\0");
206        data.extend_from_slice(&hex!("3a4df67dd7fd7cb3ca82d9896dbdd28053d39bdb"));
207        data.extend_from_slice(b"100644 a-file\0");
208        data.extend_from_slice(&hex!("e69de29bb2d1d6434b8b29ae775ad8c2e48c5391"));
209        data.extend_from_slice(b"120000 a-symlink\0");
210        data.extend_from_slice(&hex!("7c35e066a9001b24677ae572214d292cebc55979"));
211        data.extend_from_slice(b"100755 an-executable-file\0");
212        data.extend_from_slice(&hex!("e69de29bb2d1d6434b8b29ae775ad8c2e48c5391"));
213        data.extend_from_slice(b"160000 a-commit\0");
214        data.extend_from_slice(&hex!("91ca81cfccb6f88a34807e9810bb0be409f32d70"));
215        let tree = Tree::parse(ZERO_OID, data).unwrap();
216        let entries = tree.entries();
217        assert_eq!(entries.len(), 5);
218        let expected = [
219            (
220                TreeEntryType::Tree,
221                ObjectId::from_bytes(hex!("3a4df67dd7fd7cb3ca82d9896dbdd28053d39bdb")),
222                b"a-directory".as_slice(),
223            ),
224            (
225                TreeEntryType::File,
226                ObjectId::from_bytes(hex!("e69de29bb2d1d6434b8b29ae775ad8c2e48c5391")),
227                b"a-file".as_slice(),
228            ),
229            (
230                TreeEntryType::Symlink,
231                ObjectId::from_bytes(hex!("7c35e066a9001b24677ae572214d292cebc55979")),
232                b"a-symlink".as_slice(),
233            ),
234            (
235                TreeEntryType::Executable,
236                ObjectId::from_bytes(hex!("e69de29bb2d1d6434b8b29ae775ad8c2e48c5391")),
237                b"an-executable-file".as_slice(),
238            ),
239            (
240                TreeEntryType::Commit,
241                ObjectId::from_bytes(hex!("91ca81cfccb6f88a34807e9810bb0be409f32d70")),
242                b"a-commit".as_slice(),
243            ),
244        ];
245        for (received, (entry_type, id, name)) in entries.zip(expected.into_iter()) {
246            assert_eq!(received.entry_type(), entry_type);
247            assert_eq!(received.id(), id);
248            assert_eq!(received.name(), name);
249        }
250    }
251}
git_async/object/tree.rs

git_async/object/
tree.rs
