git_policy_cli/
repo_read_tree.rs

1//! What:
2//!  Trees and commits read in process: the entries of a tree, the flat list of a whole tree, and the header fields
3//!  and subject of a commit.
4//! Why:
5//!  The diff and listing readers compare a commit's tree with an index or another tree path by path, and `show` prints a
6//!  commit's subject; both need only these parses, and a commit with a header the parser does not know
7//!  (a different message encoding, a signature it must not interpret) returns `None` so Git answers.
8//!
9//! In TS you'd write (pseudocode):
10//! ```ts
11//! const entries = parseTree(bytes, hashLength); const flat = flattenTree(odb, treeName);
12//! ```
13
14#![cfg(unix)]
15
16use super::repo_read_object::{ObjectKind, name_length};
17use super::repo_read_layout::ObjectFormat;
18use super::repo_read_odb::ObjectDatabase;
19
20/// The deepest tree nesting the flattener follows.
21const TREE_DEPTH_LIMIT: usize = 256;
22
23/// The most entries a flat list may hold before the reader declines.
24const FLAT_ENTRY_LIMIT: usize = 4_000_000;
25
26/// The mode of a tree entry that is a directory.
27pub const MODE_TREE: u32 = 0o040_000;
28
29/// The mode of a gitlink (a submodule commit).
30pub const MODE_GITLINK: u32 = 0o160_000;
31
32/// One entry of a tree.
33#[derive(Clone, Debug, Eq, PartialEq)]
34pub struct TreeEntry {
35    /// The mode as stored (`0o100644`, `0o040000`, ...).
36    pub mode: u32,
37    /// The entry name, which holds no `/`.
38    pub name: Vec<u8>,
39    /// The object name.
40    pub id: Vec<u8>,
41}
42
43/// One non-directory entry of a flattened tree with its full path.
44#[derive(Clone, Debug, Eq, PartialEq)]
45pub struct FlatEntry {
46    /// The path from the top of the tree, `/` separated.
47    pub path: Vec<u8>,
48    /// The mode.
49    pub mode: u32,
50    /// The object name.
51    pub id: Vec<u8>,
52}
53
54/// The entries of a tree object's content, or `None` when any entry is malformed.
55pub fn parse_tree(bytes: &[u8], hash_length: usize) -> Option<Vec<TreeEntry>> {
56    let mut entries: Vec<TreeEntry> = Vec::new();
57    let mut cursor: usize = 0;
58    while cursor < bytes.len() {
59        let space: usize = cursor + bytes[cursor..].iter().position(|byte| { return *byte == b' '; })?;
60        let mode_text: &str = std::str::from_utf8(&bytes[cursor..space]).ok()?;
61        // Git writes `40000` for a directory and no leading zero for any mode; other spellings are left to Git.
62        if mode_text.is_empty() || mode_text.starts_with('0') {
63            return None;
64        }
65        let mode: u32 = u32::from_str_radix(mode_text, 8).ok()?;
66        // Git canonicalizes other spellings (`100664` reads as `100644`); only the canonical ones are read here.
67        if !matches!(mode, 0o100_644 | 0o100_755 | 0o120_000 | 0o160_000 | MODE_TREE) {
68            return None;
69        }
70        let nul: usize = space + 1 + bytes[space + 1..].iter().position(|byte| { return *byte == 0; })?;
71        let name: Vec<u8> = bytes[space + 1..nul].to_vec();
72        if name.is_empty() || name.contains(&b'/') {
73            return None;
74        }
75        let id: Vec<u8> = bytes.get(nul + 1..nul + 1 + hash_length)?.to_vec();
76        entries.push(TreeEntry { mode, name, id });
77        cursor = nul + 1 + hash_length;
78    }
79    return Some(entries);
80}
81
82/// Whether the mode names a directory.
83pub fn is_tree_mode(mode: u32) -> bool {
84    return mode & 0o170_000 == MODE_TREE;
85}
86
87/// What:
88///  Every non-directory entry below the tree `name`, with full paths, in the order Git walks them.
89/// Why:
90///   Tree order sorts a directory as if its name ended in `/`, which is the byte order of the full paths, so the list
91///  is sorted by path and two lists merge by one pass.
92///
93/// In TS you'd write (pseudocode):
94/// ```ts
95/// function flattenTree(odb: ObjectDatabase, tree: Uint8Array, format): FlatEntry[] | undefined;
96/// ```
97pub fn flatten_tree(database: &ObjectDatabase, tree: &[u8], format: ObjectFormat) -> Option<Vec<FlatEntry>> {
98    let mut flat: Vec<FlatEntry> = Vec::new();
99    walk(database, tree, format, &mut Vec::new(), 0, &mut flat)?;
100    return Some(flat);
101}
102
103/// Append the entries of `tree` below `prefix` to `flat`.
104fn walk(
105    database: &ObjectDatabase,
106    tree: &[u8],
107    format: ObjectFormat,
108    prefix: &mut Vec<u8>,
109    depth: usize,
110    flat: &mut Vec<FlatEntry>,
111) -> Option<()> {
112    if depth > TREE_DEPTH_LIMIT {
113        return None;
114    }
115    let object = database.read(tree)?;
116    if object.kind != ObjectKind::Tree {
117        return None;
118    }
119    for entry in parse_tree(object.bytes.as_slice(), name_length(format))? {
120        let length: usize = prefix.len();
121        prefix.extend_from_slice(entry.name.as_slice());
122        if is_tree_mode(entry.mode) {
123            prefix.push(b'/');
124            walk(database, entry.id.as_slice(), format, prefix, depth + 1, flat)?;
125        } else {
126            flat.push(FlatEntry { path: prefix.clone(), mode: entry.mode, id: entry.id });
127            if flat.len() > FLAT_ENTRY_LIMIT {
128                return None;
129            }
130        }
131        prefix.truncate(length);
132    }
133    return Some(());
134}
135
136/// The fields of a commit the readers use.
137#[derive(Clone, Debug, Eq, PartialEq)]
138pub struct CommitFields {
139    /// The root tree.
140    pub tree: Vec<u8>,
141    /// The parents in order.
142    pub parents: Vec<Vec<u8>>,
143    /// The message: everything after the blank line that ends the header.
144    pub message: Vec<u8>,
145}
146
147/// What:
148///  The tree, parents and message of a commit object's content;
149///  `None` for a header with an `encoding` line (Git would re-encode the message) or a malformed one.
150/// Why:
151///   `show --format=%s` prints the message converted to UTF-8; only a commit that needs no conversion is read here.
152///
153/// In TS you'd write (pseudocode):
154/// ```ts
155/// function parseCommit(bytes: Uint8Array, format): CommitFields | undefined;
156/// ```
157pub fn parse_commit(bytes: &[u8], format: ObjectFormat) -> Option<CommitFields> {
158    let split: usize = bytes.windows(2).position(|pair| { return pair == b"\n\n"; })?;
159    let header: &[u8] = &bytes[..split];
160    let mut tree: Option<Vec<u8>> = None;
161    let mut parents: Vec<Vec<u8>> = Vec::new();
162    for (index, line) in header.split(|byte| { return *byte == b'\n'; }).enumerate() {
163        if let Some(text) = line.strip_prefix(b"tree ") {
164            if index != 0 {
165                return None;
166            }
167            tree = Some(super::repo_read_object::from_hex(text, format)?);
168        } else if let Some(text) = line.strip_prefix(b"parent ") {
169            parents.push(super::repo_read_object::from_hex(text, format)?);
170        } else if line.starts_with(b"encoding ") {
171            return None;
172        }
173    }
174    return Some(CommitFields { tree: tree?, parents, message: bytes[split + 2..].to_vec() });
175}
176
177/// What:
178///  The subject `%s` prints for a message: the first paragraph with its lines joined by spaces.
179/// Why:
180///   Git skips leading blank lines, stops at the first blank line, trims each line's trailing white space and joins
181///  with a single space; any message the plain rule does not cover (a carriage return) returns `None`.
182///
183/// In TS you'd write (pseudocode):
184/// ```ts
185/// const subject = message.replace(/^\n+/, '').split(/\n\s*\n/)[0].split('\n').map((l) => l.trimEnd()).join(' ');
186/// ```
187pub fn subject_of(message: &[u8]) -> Option<Vec<u8>> {
188    if message.contains(&b'\r') || message.contains(&0) {
189        return None;
190    }
191    let mut subject: Vec<u8> = Vec::new();
192    let mut started: bool = false;
193    for line in message.split(|byte| { return *byte == b'\n'; }) {
194        let trimmed: &[u8] = line.trim_ascii_end();
195        let blank: bool = trimmed.is_empty();
196        if blank && !started {
197            continue;
198        }
199        if blank {
200            break;
201        }
202        if started {
203            subject.push(b' ');
204        }
205        started = true;
206        subject.extend_from_slice(line.trim_ascii_end());
207    }
208    return Some(subject);
209}
210
211#[cfg(test)]
212#[path = "repo_read_tree_tests.rs"]
213mod tests;
git_policy_cli/repo_read_tree.rs

git_policy_cli/
repo_read_tree.rs
