返回 CodeWhale
delta.rs
根目录 / crates / tui / src / snapshot / delta.rs
1 //! Read-only views over two snapshots: what changed between them.
2 //!
3 //! The engine is the only snapshot writer. These methods only read the side
4 //! repo (`diff-tree`, `ls-tree`, `cat-file`), so a host can learn what a turn
5 //! changed from the `pre-turn`/`post-turn` pair the engine already took,
6 //! without a second snapshot or a second store.
7
8 use std::collections::HashSet;
9 use std::io::{self, BufRead, BufReader, Read, Write};
10 use std::path::{Component, Path};
11 use std::process::{Command, Stdio};
12
13 use sha2::{Digest, Sha256};
14
15 use super::{SnapshotId, SnapshotRepo};
16 use crate::dependencies::ExternalTool;
17
18 /// Blobs above this size are reported by size only: hashing them for a
19 /// Preview list is not worth the I/O, and the read route refuses them anyway.
20 pub const DELTA_HASH_MAX_BYTES: u64 = 16 * 1024 * 1024;
21
22 /// How one path changed between two snapshots.
23 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
24 pub enum DeltaChange {
25 Created,
26 Updated,
27 Deleted,
28 Renamed,
29 }
30
31 /// One changed path. `size`/`sha256` describe the content in the *newer*
32 /// snapshot; both are `None` for a deletion, and `sha256` is `None` above
33 /// [`DELTA_HASH_MAX_BYTES`].
34 #[derive(Debug, Clone, PartialEq, Eq)]
35 pub struct DeltaEntry {
36 /// Workspace-relative, `/`-separated.
37 pub path: String,
38 pub previous_path: Option<String>,
39 pub change: DeltaChange,
40 pub size: Option<u64>,
41 pub sha256: Option<String>,
42 }
43
44 /// Every regular-file change between two snapshots, bounded.
45 #[derive(Debug, Clone, Default, PartialEq, Eq)]
46 pub struct SnapshotDelta {
47 pub entries: Vec<DeltaEntry>,
48 /// Entries were cut at the limit.
49 pub truncated: bool,
50 /// Changes not listed: past the limit, a non-UTF-8 or unsafe path, or
51 /// not a regular file (symlink, submodule).
52 pub omitted: u64,
53 }
54
55 struct RawChange {
56 dst_mode: String,
57 dst_blob: String,
58 status: u8,
59 path: Vec<u8>,
60 previous_path: Option<Vec<u8>>,
61 }
62
63 fn git(repo: &SnapshotRepo) -> io::Result<Command> {
64 let mut command = crate::dependencies::Git::command()
65 .ok_or_else(|| io::Error::new(io::ErrorKind::NotFound, "git not found on PATH"))?;
66 command
67 .arg("--git-dir")
68 .arg(repo.git_dir())
69 .arg("--work-tree")
70 .arg(repo.work_tree());
71 Ok(command)
72 }
73
74 fn git_output(repo: &SnapshotRepo, args: &[&str]) -> io::Result<Vec<u8>> {
75 let output = git(repo)?.args(args).output()?;
76 if !output.status.success() {
77 return Err(io::Error::other(format!(
78 "git {} failed: {}",
79 args.first().copied().unwrap_or_default(),
80 String::from_utf8_lossy(&output.stderr).trim()
81 )));
82 }
83 Ok(output.stdout)
84 }
85
86 /// A workspace-relative display path, or `None` when the bytes are not
87 /// UTF-8, the path is not plainly relative, or it names `.git`.
88 fn safe_display(path: &[u8]) -> Option<String> {
89 let text = std::str::from_utf8(path).ok()?;
90 let mut parts = Vec::new();
91 for component in Path::new(text).components() {
92 match component {
93 Component::Normal(name) if !super::is_git_metadata_name(name) => {
94 parts.push(name.to_str()?)
95 }
96 _ => return None,
97 }
98 }
99 (!parts.is_empty()).then(|| parts.join("/"))
100 }
101
102 /// Parse `diff-tree -r -z --raw -M` output: `:<src mode> <dst mode> <src oid>
103 /// <dst oid> <status>\0<path>\0` and, for a rename or copy, a second path.
104 fn parse_raw(bytes: &[u8]) -> io::Result<Vec<RawChange>> {
105 let invalid = || io::Error::new(io::ErrorKind::InvalidData, "unexpected diff-tree output");
106 let mut fields = bytes.split(|byte| *byte == 0).filter(|f| !f.is_empty());
107 let mut changes = Vec::new();
108 while let Some(header) = fields.next() {
109 let header = std::str::from_utf8(header).map_err(|_| invalid())?;
110 let header = header.strip_prefix(':').ok_or_else(invalid)?;
111 let parts: Vec<&str> = header.split(' ').collect();
112 let [_, dst_mode, _, dst_blob, status] = parts.as_slice() else {
113 return Err(invalid());
114 };
115 let status = status.bytes().next().ok_or_else(invalid)?;
116 let first = fields.next().ok_or_else(invalid)?.to_vec();
117 let (path, previous_path) = if matches!(status, b'R' | b'C') {
118 let second = fields.next().ok_or_else(invalid)?.to_vec();
119 (second, Some(first))
120 } else {
121 (first, None)
122 };
123 changes.push(RawChange {
124 dst_mode: (*dst_mode).to_string(),
125 dst_blob: (*dst_blob).to_string(),
126 status,
127 path,
128 previous_path,
129 });
130 }
131 Ok(changes)
132 }
133
134 impl SnapshotRepo {
135 /// Every regular-file change from snapshot `from` to snapshot `to`,
136 /// with the size and SHA-256 of each new blob, bounded to `limit`
137 /// entries. Renames are detected (`-M`). Reads the side repo only.
138 ///
139 /// What the snapshots cannot see is not here either: paths excluded by
140 /// the built-in excludes or the workspace's `.gitignore` never enter a
141 /// snapshot, so a change to them never appears in a delta.
142 pub fn diff_snapshots(
143 &self,
144 from: &SnapshotId,
145 to: &SnapshotId,
146 limit: usize,
147 ) -> io::Result<SnapshotDelta> {
148 let raw = git_output(
149 self,
150 &[
151 "diff-tree",
152 "-r",
153 "-z",
154 "-M",
155 "--raw",
156 "--no-commit-id",
157 "--end-of-options",
158 from.as_str(),
159 to.as_str(),
160 ],
161 )?;
162 let mut delta = SnapshotDelta::default();
163 let mut pending_blobs = Vec::new();
164 for change in parse_raw(&raw)? {
165 let kind = match change.status {
166 b'A' | b'C' => DeltaChange::Created,
167 b'D' => DeltaChange::Deleted,
168 b'M' | b'T' => DeltaChange::Updated,
169 b'R' => DeltaChange::Renamed,
170 _ => {
171 delta.omitted += 1;
172 continue;
173 }
174 };
175 let regular = matches!(change.dst_mode.as_str(), "100644" | "100755");
176 if kind != DeltaChange::Deleted && !regular {
177 delta.omitted += 1;
178 continue;
179 }
180 let Some(path) = safe_display(&change.path) else {
181 delta.omitted += 1;
182 continue;
183 };
184 let previous_path = match change.previous_path.as_deref() {
185 Some(previous) => match safe_display(previous) {
186 Some(previous) => Some(previous),
187 None => {
188 delta.omitted += 1;
189 continue;
190 }
191 },
192 None => None,
193 };
194 if delta.entries.len() >= limit {
195 delta.truncated = true;
196 delta.omitted += 1;
197 continue;
198 }
199 if kind != DeltaChange::Deleted {
200 pending_blobs.push((delta.entries.len(), change.dst_blob));
201 }
202 delta.entries.push(DeltaEntry {
203 path,
204 previous_path,
205 // A copy (`C`) only appears with `-C`; treat it as a creation
206 // so its source is never reported as touched.
207 change: kind,
208 size: None,
209 sha256: None,
210 });
211 }
212 for (index, size, sha256) in self.blob_facts(&pending_blobs)? {
213 let entry = &mut delta.entries[index];
214 entry.size = Some(size);
215 entry.sha256 = sha256;
216 }
217 Ok(delta)
218 }
219
220 /// Size and SHA-256 of each blob in one `cat-file --batch` pass. Blobs
221 /// above [`DELTA_HASH_MAX_BYTES`] are streamed past without hashing.
222 fn blob_facts(
223 &self,
224 blobs: &[(usize, String)],
225 ) -> io::Result<Vec<(usize, u64, Option<String>)>> {
226 if blobs.is_empty() {
227 return Ok(Vec::new());
228 }
229 let mut child = git(self)?
230 .args(["cat-file", "--batch"])
231 .stdin(Stdio::piped())
232 .stdout(Stdio::piped())
233 .stderr(Stdio::null())
234 .spawn()?;
235 let mut stdin = child
236 .stdin
237 .take()
238 .ok_or_else(|| io::Error::other("cat-file stdin unavailable"))?;
239 let request: String = blobs.iter().map(|(_, oid)| format!("{oid}\n")).collect();
240 // Feed requests from another thread: git blocks on a full stdout
241 // pipe, and stops reading stdin until it drains.
242 let writer = std::thread::spawn(move || stdin.write_all(request.as_bytes()));
243 let stdout = child
244 .stdout
245 .take()
246 .ok_or_else(|| io::Error::other("cat-file stdout unavailable"))?;
247 let mut reader = BufReader::new(stdout);
248 let mut facts = Vec::with_capacity(blobs.len());
249 let mut header = String::new();
250 let mut buffer = vec![0_u8; 64 * 1024];
251 for (index, _) in blobs {
252 header.clear();
253 reader.read_line(&mut header)?;
254 let mut parts = header.split_whitespace();
255 let (Some(_), Some("blob"), Some(size)) = (parts.next(), parts.next(), parts.next())
256 else {
257 let _ = child.kill();
258 return Err(io::Error::other(format!(
259 "cat-file returned an unexpected header: {}",
260 header.trim()
261 )));
262 };
263 let size: u64 = size
264 .parse()
265 .map_err(|_| io::Error::other("cat-file returned an invalid size"))?;
266 let mut hasher = (size <= DELTA_HASH_MAX_BYTES).then(Sha256::new);
267 let mut remaining = size;
268 while remaining > 0 {
269 let want = usize::try_from(remaining.min(buffer.len() as u64)).unwrap_or(0);
270 let read = reader.read(&mut buffer[..want])?;
271 if read == 0 {
272 return Err(io::Error::new(
273 io::ErrorKind::UnexpectedEof,
274 "cat-file ended inside a blob",
275 ));
276 }
277 if let Some(hasher) = hasher.as_mut() {
278 hasher.update(&buffer[..read]);
279 }
280 remaining -= read as u64;
281 }
282 let mut newline = [0_u8; 1];
283 reader.read_exact(&mut newline)?;
284 facts.push((
285 *index,
286 size,
287 hasher.map(|hasher| crate::hashing::hex_bytes(hasher.finalize())),
288 ));
289 }
290 writer
291 .join()
292 .map_err(|_| io::Error::other("cat-file writer panicked"))??;
293 child.wait()?;
294 Ok(facts)
295 }
296
297 /// The bytes of regular file `rel` in snapshot `id`, or `None` when the
298 /// snapshot does not hold a regular file there. A blob larger than
299 /// `max_bytes` is refused with `FileTooLarge` before it is read.
300 pub fn read_blob(
301 &self,
302 id: &SnapshotId,
303 rel: &str,
304 max_bytes: u64,
305 ) -> io::Result<Option<Vec<u8>>> {
306 if safe_display(rel.as_bytes()).as_deref() != Some(rel) {
307 return Err(io::Error::new(
308 io::ErrorKind::InvalidInput,
309 "snapshot path must be a plain workspace-relative path",
310 ));
311 }
312 let entry = git_output(
313 self,
314 &[
315 "--literal-pathspecs",
316 "ls-tree",
317 "-z",
318 "--long",
319 "--end-of-options",
320 id.as_str(),
321 "--",
322 rel,
323 ],
324 )?;
325 // `<mode> blob <oid> <size>\t<path>\0`
326 let Some(line) = entry.split(|byte| *byte == 0).find(|line| !line.is_empty()) else {
327 return Ok(None);
328 };
329 let header = std::str::from_utf8(line)
330 .ok()
331 .and_then(|line| line.split('\t').next())
332 .unwrap_or_default();
333 let fields: Vec<&str> = header.split_whitespace().collect();
334 let [mode, "blob", oid, size] = fields.as_slice() else {
335 return Ok(None);
336 };
337 if !matches!(*mode, "100644" | "100755") {
338 return Ok(None);
339 }
340 let size: u64 = size
341 .parse()
342 .map_err(|_| io::Error::other("ls-tree returned an invalid size"))?;
343 if size > max_bytes {
344 return Err(io::Error::new(
345 io::ErrorKind::FileTooLarge,
346 "snapshot blob exceeds the read limit",
347 ));
348 }
349 git_output(self, &["cat-file", "blob", oid]).map(Some)
350 }
351
352 /// Which of `paths` snapshot `id` contains. A path absent from both
353 /// snapshots of a pair is one the snapshots cannot see (excluded or
354 /// ignored), which is different from one that did not change.
355 pub fn tracked_paths(&self, id: &SnapshotId, paths: &[String]) -> io::Result<HashSet<String>> {
356 if paths.is_empty() {
357 return Ok(HashSet::new());
358 }
359 let mut args = vec![
360 "--literal-pathspecs",
361 "ls-tree",
362 "-r",
363 "-z",
364 "--name-only",
365 "--end-of-options",
366 id.as_str(),
367 "--",
368 ];
369 args.extend(paths.iter().map(String::as_str));
370 let listed = git_output(self, &args)?;
371 Ok(listed
372 .split(|byte| *byte == 0)
373 .filter_map(safe_display)
374 .collect())
375 }
376 }
377
378 #[cfg(test)]
379 mod tests {
380 use super::*;
381 use crate::test_support::{EnvVarGuard, TestEnvLock, lock_test_env};
382 use std::fs;
383
384 struct Home {
385 _vars: Vec<EnvVarGuard>,
386 _lock: TestEnvLock,
387 }
388
389 fn repo(root: &Path) -> (SnapshotRepo, Home) {
390 let lock = lock_test_env();
391 let vars = vec![
392 EnvVarGuard::set("HOME", root),
393 EnvVarGuard::set("USERPROFILE", root),
394 EnvVarGuard::set("CODEWHALE_HOME", root.join(".codewhale")),
395 ];
396 let workspace = root.join("workspace");
397 fs::create_dir_all(&workspace).unwrap();
398 let repo = SnapshotRepo::open_or_init_with_cap(&workspace, 0).expect("snapshot repo");
399 (
400 repo,
401 Home {
402 _vars: vars,
403 _lock: lock,
404 },
405 )
406 }
407
408 fn sha(bytes: &[u8]) -> Option<String> {
409 Some(crate::hashing::sha256_hex(bytes))
410 }
411
412 #[test]
413 fn delta_reports_created_updated_deleted_and_renamed_with_facts() {
414 let root = tempfile::tempdir().unwrap();
415 let (repo, _home) = repo(root.path());
416 let work = repo.work_tree().to_path_buf();
417 fs::write(work.join("keep.txt"), "same\n").unwrap();
418 fs::write(work.join("edit.txt"), "before\n").unwrap();
419 fs::write(work.join("gone.txt"), "bye\n").unwrap();
420 fs::write(
421 work.join("move-me.txt"),
422 "a long enough body to be detected as a rename\n",
423 )
424 .unwrap();
425 let pre = repo.snapshot("pre-turn:1").unwrap();
426
427 // What a shell command does: plain filesystem writes, no receipts.
428 fs::create_dir(work.join("site")).unwrap();
429 fs::write(work.join("site/index.html"), "<h1>hi</h1>\n").unwrap();
430 fs::write(work.join("edit.txt"), "after\n").unwrap();
431 fs::remove_file(work.join("gone.txt")).unwrap();
432 fs::rename(work.join("move-me.txt"), work.join("moved.txt")).unwrap();
433 let post = repo.snapshot("post-turn:1").unwrap();
434
435 let delta = repo.diff_snapshots(&pre, &post, 100).unwrap();
436 assert!(!delta.truncated);
437 assert_eq!(delta.omitted, 0);
438 let mut entries = delta.entries.clone();
439 entries.sort_by(|a, b| a.path.cmp(&b.path));
440 assert_eq!(
441 entries,
442 vec![
443 DeltaEntry {
444 path: "edit.txt".into(),
445 previous_path: None,
446 change: DeltaChange::Updated,
447 size: Some(6),
448 sha256: sha(b"after\n"),
449 },
450 DeltaEntry {
451 path: "gone.txt".into(),
452 previous_path: None,
453 change: DeltaChange::Deleted,
454 size: None,
455 sha256: None,
456 },
457 DeltaEntry {
458 path: "moved.txt".into(),
459 previous_path: Some("move-me.txt".into()),
460 change: DeltaChange::Renamed,
461 size: Some(46),
462 sha256: sha(b"a long enough body to be detected as a rename\n"),
463 },
464 DeltaEntry {
465 path: "site/index.html".into(),
466 previous_path: None,
467 change: DeltaChange::Created,
468 size: Some(12),
469 sha256: sha(b"<h1>hi</h1>\n"),
470 },
471 ]
472 );
473
474 // The pair is diffable in either direction and bounded.
475 let bounded = repo.diff_snapshots(&pre, &post, 2).unwrap();
476 assert_eq!(bounded.entries.len(), 2);
477 assert!(bounded.truncated);
478 assert_eq!(bounded.omitted, 2);
479
480 // Tracked probes distinguish "unchanged" from "invisible".
481 let probes = ["keep.txt", "gone.txt", "never.txt"].map(String::from);
482 assert_eq!(
483 repo.tracked_paths(&pre, &probes).unwrap(),
484 HashSet::from(["keep.txt".to_string(), "gone.txt".to_string()])
485 );
486 }
487
488 #[test]
489 fn oversized_blobs_report_size_without_a_revision() {
490 let root = tempfile::tempdir().unwrap();
491 let (repo, _home) = repo(root.path());
492 let work = repo.work_tree().to_path_buf();
493 fs::write(work.join("seed.txt"), "seed\n").unwrap();
494 let pre = repo.snapshot("pre-turn:1").unwrap();
495 let big = vec![b'z'; (DELTA_HASH_MAX_BYTES + 1) as usize];
496 fs::write(work.join("big.txt"), &big).unwrap();
497 fs::write(work.join("small.txt"), "small\n").unwrap();
498 let post = repo.snapshot("post-turn:1").unwrap();
499 let delta = repo.diff_snapshots(&pre, &post, 100).unwrap();
500 let big_entry = delta.entries.iter().find(|e| e.path == "big.txt").unwrap();
501 assert_eq!(big_entry.size, Some(DELTA_HASH_MAX_BYTES + 1));
502 assert_eq!(big_entry.sha256, None);
503 // A later blob in the same batch is still read correctly.
504 let small = delta
505 .entries
506 .iter()
507 .find(|e| e.path == "small.txt")
508 .unwrap();
509 assert_eq!(small.sha256, sha(b"small\n"));
510 }
511
512 #[test]
513 fn read_blob_returns_exact_snapshot_bytes_and_refuses_unsafe_paths() {
514 let root = tempfile::tempdir().unwrap();
515 let (repo, _home) = repo(root.path());
516 let work = repo.work_tree().to_path_buf();
517 fs::create_dir(work.join("dir")).unwrap();
518 fs::write(work.join("dir/a.txt"), b"exact \x00 bytes").unwrap();
519 let id = repo.snapshot("post-turn:1").unwrap();
520 fs::write(work.join("dir/a.txt"), b"changed later").unwrap();
521 assert_eq!(
522 repo.read_blob(&id, "dir/a.txt", 1024).unwrap().as_deref(),
523 Some(&b"exact \x00 bytes"[..])
524 );
525 assert_eq!(repo.read_blob(&id, "dir/missing.txt", 1024).unwrap(), None);
526 assert_eq!(
527 repo.read_blob(&id, "dir", 1024).unwrap(),
528 None,
529 "a tree is not a file"
530 );
531 assert_eq!(
532 repo.read_blob(&id, "dir/a.txt", 3).unwrap_err().kind(),
533 io::ErrorKind::FileTooLarge
534 );
535 for unsafe_path in [
536 "../escape",
537 "/etc/passwd",
538 "dir/../dir/a.txt",
539 ".git/config",
540 "",
541 ] {
542 assert_eq!(
543 repo.read_blob(&id, unsafe_path, 1024).unwrap_err().kind(),
544 io::ErrorKind::InvalidInput,
545 "{unsafe_path:?}"
546 );
547 }
548 }
549
550 #[test]
551 fn unsafe_and_non_utf8_paths_are_not_displayed() {
552 assert_eq!(safe_display(b"a/b.txt").as_deref(), Some("a/b.txt"));
553 assert_eq!(safe_display(b"../x"), None);
554 assert_eq!(safe_display(b"/abs"), None);
555 assert_eq!(safe_display(b".git/config"), None);
556 assert_eq!(safe_display(b"bad\xff.txt"), None);
557 assert_eq!(safe_display(b""), None);
558 }
559 }
560
560 lines RUST