steid
Sign in

@jamesgill /

steid

steid/src/infrastructure/git_query/parse_tree.rs
Rust13.5 KBCode·Blame·History·Raw
1//! Parsing what a raw tree object and a last-commit walk say about a listing.
2
3use std::collections::HashMap;
4
5use crate::{
6 application::port::GitQueryError,
7 domain::{EntryCommit, EntryKind, ObjectId, RefName, RepoPath, TreeEntry},
8};
9
10use super::unix_time;
11
12/// How git addresses a path inside a revision: `{rev}:{path}`, and `{rev}:` for the root.
13pub(super) fn tree_spec(rev: &RefName, path: &RepoPath) -> String {
14 format!("{}:{}", rev.as_str(), path.as_str())
15}
16
17/// What a last-commit walk reads: id, commit time, subject.
18///
19/// Every separator is a NUL, and `-z` NUL-terminates the paths too — so the whole stream
20/// is one NUL-separated sequence and a record boundary has to be recognised rather than
21/// counted. See [`attribute`].
22pub(super) const LAST_COMMIT_FORMAT: &str = "--format=%H%x00%ct%x00%s";
23
24/// Attributes each of a directory's entries to the most recent commit that touched it.
25///
26/// The stream is `<id> NUL <seconds> NUL <subject> NUL` followed by that commit's paths,
27/// each NUL-terminated, and then the next commit. Nothing marks a boundary — git writes
28/// one flat sequence — so a record is recognised by its shape: a full object id followed
29/// by a field that parses as a time. A file named like an object id would need the field
30/// after it to be a bare integer as well before it could be mistaken for one.
31///
32/// Newest first, so the **first** commit to mention a path is the one that owns it, and
33/// a path under a child directory attributes to the child: `src/web/page.rs` in a listing
34/// of `src` is `web`'s. Walking stops as soon as every entry has an answer, which is what
35/// makes the cap a worst case rather than the usual cost.
36///
37/// git prints no file list for a merge commit, so a change that arrived by merge is
38/// attributed to the commit inside the branch rather than to the merge — git's answer,
39/// and the more useful one.
40pub(super) fn attribute(
41 stdout: &[u8],
42 prefix: &str,
43 entries: &[String],
44) -> HashMap<String, EntryCommit> {
45 let mut wanted: std::collections::HashSet<&str> = entries.iter().map(String::as_str).collect();
46 let mut found: HashMap<String, EntryCommit> = HashMap::new();
47
48 let fields: Vec<&[u8]> = stdout.split(|byte| *byte == 0).collect();
49 let mut index = 0;
50
51 while index < fields.len() && !wanted.is_empty() {
52 let Some(commit) = record_at(&fields, index) else {
53 index += 1;
54 continue;
55 };
56
57 index += 3;
58
59 // Everything up to the next record is this commit's paths. The first of them
60 // carries the newline git writes between the formatted line and the file list.
61 while index < fields.len() && record_at(&fields, index).is_none() {
62 let path = String::from_utf8_lossy(fields[index]);
63 let path = path.trim_start_matches('\n');
64
65 index += 1;
66
67 let Some(child) = path.strip_prefix(prefix) else {
68 continue;
69 };
70
71 let child = child.split('/').next().unwrap_or_default();
72
73 if wanted.remove(child) {
74 found.insert(child.to_owned(), commit.clone());
75 }
76 }
77 }
78
79 found
80}
81
82/// Reads a commit record at `index`, if one starts there.
83fn record_at(fields: &[&[u8]], index: usize) -> Option<EntryCommit> {
84 let id = std::str::from_utf8(fields.get(index)?).ok()?;
85 let seconds = std::str::from_utf8(fields.get(index + 1)?).ok()?;
86 let summary = fields.get(index + 2)?;
87
88 if id.len() != 40 || !id.bytes().all(|byte| byte.is_ascii_hexdigit()) {
89 return None;
90 }
91
92 Some(EntryCommit {
93 id: ObjectId::new(id).ok()?,
94 summary: String::from_utf8_lossy(summary).trim().to_owned(),
95 committed_at: unix_time(seconds.trim().parse::<i64>().ok()?),
96 })
97}
98
99/// Parses a tree object as git stores it.
100///
101/// The format is one record per entry and nothing else: `<mode> SP <name> NUL <20 raw
102/// bytes of object id>`, with no terminator, no ordering guarantee a caller should rely
103/// on, and **no sizes** — a tree records what is in it, not how big. The mode is octal
104/// with no leading zero, so a directory is `40000` rather than `040000`; the name is raw
105/// bytes, which is why the split happens before any attempt to read it as text.
106///
107/// This replaces `ls-tree -z --long`, whose text format git generated from exactly these
108/// bytes. Sizes are asked for separately — see [`GitQuery::list_tree`].
109///
110/// A truncated record is an error rather than a short listing: half a directory is worse
111/// than a page that says something went wrong.
112pub(super) fn parse_tree_object(bytes: &[u8]) -> Result<Vec<TreeEntry>, GitQueryError> {
113 const ID_BYTES: usize = 20;
114
115 let mut entries = Vec::new();
116 let mut rest = bytes;
117
118 while !rest.is_empty() {
119 let Some(space) = rest.iter().position(|byte| *byte == b' ') else {
120 return Err(GitQueryError::new("a tree entry has no mode"));
121 };
122
123 let mode = std::str::from_utf8(&rest[..space])
124 .map_err(|_| GitQueryError::new("a tree entry's mode is not text"))?;
125
126 let after_mode = &rest[space + 1..];
127
128 let Some(nul) = after_mode.iter().position(|byte| *byte == 0) else {
129 return Err(GitQueryError::new("a tree entry's name is not terminated"));
130 };
131
132 let name = &after_mode[..nul];
133 let after_name = &after_mode[nul + 1..];
134
135 if after_name.len() < ID_BYTES {
136 return Err(GitQueryError::new("a tree entry has no object id"));
137 }
138
139 let id: String = after_name[..ID_BYTES]
140 .iter()
141 .map(|byte| format!("{byte:02x}"))
142 .collect();
143
144 entries.push(TreeEntry {
145 // Lossy, because `TreeEntry::name` is a `String` and a filename is not
146 // required to be UTF-8. A replacement character renders; refusing to list
147 // the whole directory because one file has an odd name does not.
148 name: String::from_utf8_lossy(name).into_owned(),
149 kind: EntryKind::from_mode(mode)
150 .map_err(|error| GitQueryError::new(format!("git listed {name:?}: {error}")))?,
151 id: ObjectId::from_trusted(id),
152 // Filled in by the caller for the kinds that have one; a tree object records
153 // no sizes at all.
154 size: None,
155 });
156
157 rest = &after_name[ID_BYTES..];
158 }
159
160 // Unsorted on purpose: ordering is `TreeEntry::ordering_key`'s decision, made once
161 // in the application rather than differently in each adapter.
162 Ok(entries)
163}
164
165#[cfg(test)]
166mod tests {
167 use super::*;
168
169 // Pure, so these are tested against bytes written by hand rather than against a
170 // fixture repository: the point is the format, and a fixture would only prove
171 // that git and this parser agree about the easy cases. The round trip through a
172 // real repository is covered by the fixture tests in `git_query_tests.rs`.
173
174 /// A tree record: `<mode> SP <name> NUL <20 raw bytes>`.
175 fn tree_record(mode: &str, name: &str, id: u8) -> Vec<u8> {
176 let mut record = format!("{mode} {name}").into_bytes();
177 record.push(0);
178 record.extend(std::iter::repeat_n(id, 20));
179 record
180 }
181
182 #[test]
183 fn a_tree_object_is_parsed_into_entries() {
184 let mut bytes = tree_record("100644", "README.md", 0xab);
185 bytes.extend(tree_record("40000", "src", 0xcd));
186
187 let entries = parse_tree_object(&bytes).expect("should parse");
188
189 assert_eq!(entries.len(), 2);
190 assert_eq!(entries[0].name, "README.md");
191 assert_eq!(entries[0].kind, EntryKind::Blob);
192 assert_eq!(entries[0].id.as_str(), "ab".repeat(20));
193 // A tree object carries no sizes; `list_tree` asks for them separately.
194 assert_eq!(entries[0].size, None);
195 assert_eq!(entries[1].name, "src");
196 assert_eq!(entries[1].kind, EntryKind::Tree);
197 }
198
199 #[test]
200 fn a_filename_containing_a_space_is_one_entry() {
201 // The mode is separated from the name by a space too, which is why the split is
202 // at the *first* space and the name runs to the NUL.
203 let bytes = tree_record("100644", "a file.txt", 0x01);
204
205 let entries = parse_tree_object(&bytes).expect("should parse");
206
207 assert_eq!(entries.len(), 1);
208 assert_eq!(entries[0].name, "a file.txt");
209 }
210
211 #[test]
212 fn a_submodule_entry_is_listed_as_one() {
213 let bytes = tree_record("160000", "vendor", 0x07);
214
215 let entries = parse_tree_object(&bytes).expect("should parse");
216
217 assert_eq!(entries[0].kind, EntryKind::Submodule);
218 // The id names a commit in a repository Steid cannot see, so nothing asks about
219 // it — the entry carries the id and no size.
220 assert_eq!(entries[0].id.as_str(), "07".repeat(20));
221 assert_eq!(entries[0].size, None);
222 }
223
224 #[test]
225 fn an_empty_tree_lists_nothing() {
226 assert!(parse_tree_object(&[]).expect("should parse").is_empty());
227 }
228
229 #[test]
230 fn a_truncated_tree_is_a_fault_rather_than_a_short_listing() {
231 let mut bytes = tree_record("100644", "a.txt", 0x01);
232 bytes.truncate(bytes.len() - 4);
233
234 assert!(parse_tree_object(&bytes).is_err());
235 }
236
237 /// One commit's worth of the `-z --name-only` stream: three NUL-terminated fields,
238 /// then its paths, the first of them carrying the newline git writes after the
239 /// formatted line.
240 fn walked(id: u8, at: i64, summary: &str, paths: &[&str]) -> Vec<u8> {
241 let mut bytes = Vec::new();
242
243 bytes.extend(format!("{id:02x}").repeat(20).into_bytes());
244 bytes.push(0);
245 bytes.extend(at.to_string().into_bytes());
246 bytes.push(0);
247 bytes.extend(summary.as_bytes());
248 bytes.push(0);
249
250 for (index, path) in paths.iter().enumerate() {
251 if index == 0 {
252 bytes.push(b'\n');
253 }
254
255 bytes.extend(path.as_bytes());
256 bytes.push(0);
257 }
258
259 bytes
260 }
261
262 fn names(values: &[&str]) -> Vec<String> {
263 values.iter().map(|value| (*value).to_owned()).collect()
264 }
265
266 #[test]
267 fn each_entry_takes_the_newest_commit_that_touched_it() {
268 let mut stream = walked(0x33, 300, "fix: the reader", &["src/read.rs"]);
269 stream.extend(walked(0x22, 200, "feat: a writer", &["src/write.rs"]));
270 stream.extend(walked(0x11, 100, "first", &["src/read.rs", "src/write.rs"]));
271
272 let found = attribute(&stream, "src/", &names(&["read.rs", "write.rs"]));
273
274 assert_eq!(found["read.rs"].summary, "fix: the reader");
275 assert_eq!(found["read.rs"].committed_at, unix_time(300));
276 assert_eq!(found["write.rs"].summary, "feat: a writer");
277 }
278
279 #[test]
280 fn a_path_under_a_child_directory_attributes_to_the_child() {
281 let stream = walked(0x44, 400, "docs: a page", &["src/web/page.rs"]);
282
283 let found = attribute(&stream, "src/", &names(&["web", "read.rs"]));
284
285 assert_eq!(found["web"].summary, "docs: a page");
286 assert!(!found.contains_key("read.rs"), "nothing touched it");
287 }
288
289 #[test]
290 fn the_root_of_a_repository_needs_no_prefix() {
291 let stream = walked(
292 0x55,
293 500,
294 "chore: the manifest",
295 &["Cargo.toml", "src/lib.rs"],
296 );
297
298 let found = attribute(&stream, "", &names(&["Cargo.toml", "src"]));
299
300 assert_eq!(found["Cargo.toml"].summary, "chore: the manifest");
301 assert_eq!(found["src"].summary, "chore: the manifest");
302 }
303
304 #[test]
305 fn a_rename_attributes_the_new_name_to_the_commit_that_made_it() {
306 // git lists both sides of a rename in the commit that made it, so the new name's
307 // first mention is that commit and the old name's is too — the old name is simply
308 // not in the listing any more, so nothing asks about it.
309 let mut stream = walked(0x66, 600, "refactor: rename it", &["new.rs", "old.rs"]);
310 stream.extend(walked(0x11, 100, "first", &["old.rs"]));
311
312 let found = attribute(&stream, "", &names(&["new.rs"]));
313
314 assert_eq!(found["new.rs"].summary, "refactor: rename it");
315 assert_eq!(found.len(), 1, "the old name is not in the listing");
316 }
317
318 #[test]
319 fn an_entry_the_walk_never_reached_is_absent_rather_than_wrong() {
320 // What the cap looks like from here: the stream ends with an entry unmentioned,
321 // and the answer says nothing about it rather than naming the oldest commit read.
322 let stream = walked(0x77, 700, "only this one", &["touched.rs"]);
323
324 let found = attribute(&stream, "", &names(&["touched.rs", "untouched.rs"]));
325
326 assert_eq!(found.len(), 1);
327 assert!(!found.contains_key("untouched.rs"));
328 }
329
330 #[test]
331 fn a_commit_that_lists_no_files_does_not_shift_the_ones_after_it() {
332 // A merge, which `--name-only` prints with no file list at all. The record after
333 // it must still be recognised as a record.
334 let mut stream = walked(0x88, 800, "merge: a branch", &[]);
335 stream.extend(walked(0x99, 900, "feat: the thing", &["thing.rs"]));
336
337 let found = attribute(&stream, "", &names(&["thing.rs"]));
338
339 assert_eq!(found["thing.rs"].summary, "feat: the thing");
340 }
341
342 #[test]
343 fn a_filename_containing_a_newline_is_still_one_path() {
344 // `-z` is why: without it git would quote this, and the quoting would have to be
345 // undone here.
346 let stream = walked(0xaa, 100, "add it", &["odd\nname.rs"]);
347
348 let found = attribute(&stream, "", &names(&["odd\nname.rs"]));
349
350 assert_eq!(found.len(), 1);
351 }
352
353 #[test]
354 fn nothing_is_attributed_from_an_empty_walk() {
355 assert!(attribute(&[], "", &names(&["a.rs"])).is_empty());
356 }
357}