1use crate::{
2 Repo,
3 error::{Error, GResult},
4 file_system::FileSystem,
5 object::{Object, ObjectId, Tree, TreeEntry, TreeEntryType},
6};
7use accessory::Accessors;
8use alloc::format;
9use alloc::{string::String, vec::Vec};
10use core::convert::Infallible;
11use similar::{TextDiff, TextDiffConfig};
12
13#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
14pub struct Path(Vec<u8>);
15
16impl core::fmt::Debug for Path {
17 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
18 match str::from_utf8(&self.0) {
19 Ok(p) => f.debug_tuple("Path").field(&p).finish(),
20 Err(_) => f
21 .debug_tuple("Path")
22 .field(&String::from_utf8_lossy(&self.0))
23 .finish(),
24 }
25 }
26}
27
28impl Path {
29 pub fn as_slice(&self) -> &[u8] {
30 self.0.as_slice()
31 }
32
33 pub fn inner(self) -> Vec<u8> {
34 self.0
35 }
36}
37
38fn join(path: Option<&Path>, component: &[u8]) -> Path {
39 match path {
40 Some(p) => {
41 let mut out = Vec::with_capacity(p.0.len() + 1 + component.len());
42 out.extend_from_slice(&p.0);
43 out.push(b'/');
44 out.extend_from_slice(component);
45 Path(out)
46 }
47 None => Path(component.to_vec()),
48 }
49}
50
51#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone)]
52pub enum DiffEntry<Content> {
53 LeftOnly {
54 path: Path,
55 entry_type: TreeEntryType,
56 content: Content,
57 },
58 Both {
59 path: Path,
60 left_type: TreeEntryType,
61 right_type: TreeEntryType,
62 content: Content,
63 },
64 RightOnly {
65 path: Path,
66 entry_type: TreeEntryType,
67 content: Content,
68 },
69}
70
71impl<Content> DiffEntry<Content> {
72 pub fn content(&self) -> &Content {
73 match self {
74 DiffEntry::LeftOnly { content, .. }
75 | DiffEntry::Both { content, .. }
76 | DiffEntry::RightOnly { content, .. } => content,
77 }
78 }
79
80 pub fn path(&self) -> &Path {
81 match self {
82 DiffEntry::LeftOnly { path, .. }
83 | DiffEntry::Both { path, .. }
84 | DiffEntry::RightOnly { path, .. } => path,
85 }
86 }
87
88 pub fn map_content<T>(&self, fun: impl Fn(&Content) -> T) -> DiffEntry<T> {
89 self.map_content_res(|c| Ok::<T, Infallible>(fun(c)))
90 .unwrap()
91 }
92
93 pub fn map_content_res<T, E>(
94 &self,
95 fun: impl Fn(&Content) -> Result<T, E>,
96 ) -> Result<DiffEntry<T>, E> {
97 use DiffEntry::*;
98 Ok(match self {
99 LeftOnly {
100 path,
101 entry_type,
102 content,
103 } => DiffEntry::LeftOnly {
104 path: path.clone(),
105 entry_type: *entry_type,
106 content: fun(content)?,
107 },
108 Both {
109 path,
110 left_type,
111 right_type,
112 content,
113 } => DiffEntry::Both {
114 path: path.clone(),
115 left_type: *left_type,
116 right_type: *right_type,
117 content: fun(content)?,
118 },
119 RightOnly {
120 path,
121 entry_type,
122 content,
123 } => DiffEntry::RightOnly {
124 path: path.clone(),
125 entry_type: *entry_type,
126 content: fun(content)?,
127 },
128 })
129 }
130}
131
132#[derive(Accessors)]
133pub struct Diff {
134 #[access(get(ty(&[DiffEntry<TextDiff<'static, 'static, [u8]>>])))]
135 entries: Vec<DiffEntry<TextDiff<'static, 'static, [u8]>>>,
136}
137
138#[derive(Accessors)]
139pub struct TreeDiff {
140 #[access(get(ty(&[DiffEntry<(ObjectId, ObjectId)>])))]
141 entries: Vec<DiffEntry<(ObjectId, ObjectId)>>,
142}
143
144impl TreeDiff {
145 pub async fn new<G: FileSystem>(repo: &Repo<G>, left: &Tree, right: &Tree) -> GResult<Self> {
146 Self::new_cancelable(repo, left, right, async || false).await
147 }
148
149 #[allow(clippy::too_many_lines)]
150 pub async fn new_cancelable<G: FileSystem>(
151 repo: &Repo<G>,
152 left: &Tree,
153 right: &Tree,
154 mut cancel: impl AsyncFnMut() -> bool,
155 ) -> GResult<Self> {
156 if left.id() == right.id() {
157 return Ok(Self {
158 entries: Vec::new(),
159 });
160 }
161 let mut out: Vec<DiffEntry<(ObjectId, ObjectId)>> = Vec::new();
162 #[allow(clippy::type_complexity)]
163 let mut stack: Vec<(Option<Path>, Option<Tree>, Option<Tree>)> = Vec::new();
164 stack.push((None, Some(left.clone()), Some(right.clone())));
165
166 while let Some((parent_path, left, right)) = stack.pop() {
167 debug_assert!(left.is_some() || right.is_some());
171 debug_assert!(left.as_ref().map(Tree::id) != right.as_ref().map(Tree::id));
172 if cancel().await {
173 return Err(Error::DiffCanceled);
174 }
175 let (left, right) = match (left, right) {
176 (Some(left), Some(right)) => (left, right),
177 (Some(left), None) => {
178 for entry in left.entries() {
179 let path = join(parent_path.as_ref(), entry.name());
180 if entry.entry_type() == TreeEntryType::Tree {
181 let tree = tree(repo, entry.id()).await?;
182 stack.push((Some(path), None, Some(tree)));
183 } else {
184 out.push(DiffEntry::LeftOnly {
185 path,
186 entry_type: entry.entry_type(),
187 content: (entry.id(), ObjectId::zero()),
188 });
189 }
190 }
191 continue;
192 }
193 (None, Some(right)) => {
194 for entry in right.entries() {
195 let path = join(parent_path.as_ref(), entry.name());
196 if entry.entry_type() == TreeEntryType::Tree {
197 let tree = tree(repo, entry.id()).await?;
198 stack.push((Some(path), None, Some(tree)));
199 } else {
200 out.push(DiffEntry::RightOnly {
201 path,
202 entry_type: entry.entry_type(),
203 content: (ObjectId::zero(), entry.id()),
204 });
205 }
206 }
207 continue;
208 }
209 (None, None) => unreachable!(),
210 };
211
212 let mut left_only: Vec<TreeEntry> = Vec::new();
213 let mut right_only: Vec<TreeEntry> = Vec::new();
214 let mut both: Vec<(TreeEntry, TreeEntry)> = Vec::new();
215 for left_entry in left.entries() {
216 let right_entry = right.entries().find(|e| e.name() == left_entry.name());
217 match right_entry {
218 Some(e) => both.push((left_entry, e)),
219 None => left_only.push(left_entry),
220 }
221 }
222 for right_entry in right.entries() {
223 if both
224 .iter()
225 .find(|(_, e)| e.name() == right_entry.name())
226 .is_none()
227 {
228 right_only.push(right_entry);
229 }
230 }
231 for entry in left_only {
232 let path = join(parent_path.as_ref(), entry.name());
233 if entry.entry_type() == TreeEntryType::Tree {
234 let left_tree = tree(repo, entry.id()).await?;
235 stack.push((Some(path), Some(left_tree), None));
236 } else {
237 out.push(DiffEntry::LeftOnly {
238 path,
239 entry_type: entry.entry_type(),
240 content: (entry.id(), ObjectId::zero()),
241 });
242 }
243 }
244 for entry in right_only {
245 let path = join(parent_path.as_ref(), entry.name());
246 if entry.entry_type() == TreeEntryType::Tree {
247 let right_tree = tree(repo, entry.id()).await?;
248 stack.push((Some(path), None, Some(right_tree)));
249 } else {
250 out.push(DiffEntry::RightOnly {
251 path,
252 entry_type: entry.entry_type(),
253 content: (ObjectId::zero(), entry.id()),
254 });
255 }
256 }
257 for (left, right) in both {
258 if left.id() == right.id() {
259 continue;
260 }
261 let name = left.name();
262 match (left.entry_type(), right.entry_type()) {
263 (TreeEntryType::Tree, TreeEntryType::Tree) => {
264 let left = tree(repo, left.id()).await?;
265 let right = tree(repo, right.id()).await?;
266 let path = join(parent_path.as_ref(), name);
267 stack.push((Some(path), Some(left), Some(right)));
268 }
269 (TreeEntryType::Tree, _) => {
270 let path = join(parent_path.as_ref(), name);
271 out.push(DiffEntry::RightOnly {
272 path: path.clone(),
273 entry_type: right.entry_type(),
274 content: (ObjectId::zero(), right.id()),
275 });
276 let left_tree = tree(repo, left.id()).await?;
277 stack.push((Some(path), Some(left_tree), None));
278 }
279 (_, TreeEntryType::Tree) => {
280 let path = join(parent_path.as_ref(), name);
281 out.push(DiffEntry::LeftOnly {
282 path: path.clone(),
283 entry_type: left.entry_type(),
284 content: (left.id(), ObjectId::zero()),
285 });
286 let right_tree = tree(repo, right.id()).await?;
287 stack.push((Some(path), None, Some(right_tree)));
288 }
289 _ => {
290 out.push(DiffEntry::Both {
291 path: join(parent_path.as_ref(), name),
292 left_type: left.entry_type(),
293 right_type: right.entry_type(),
294 content: (left.id(), right.id()),
295 });
296 }
297 }
298 }
299 }
300 Ok(Self { entries: out })
301 }
302
303 pub async fn to_text_diff<G: FileSystem>(&self, repo: &Repo<G>) -> GResult<Diff> {
304 self.to_text_diff_full(repo, &TextDiffConfig::default(), async || false)
305 .await
306 }
307
308 pub async fn to_text_diff_full<G: FileSystem>(
309 &self,
310 repo: &Repo<G>,
311 config: &TextDiffConfig,
312 mut cancel: impl AsyncFnMut() -> bool,
313 ) -> GResult<Diff> {
314 let mut out: Vec<_> = Vec::with_capacity(self.entries.len());
315 for entry in &self.entries {
316 if cancel().await {
317 return Err(Error::DiffCanceled);
318 }
319 let entry = entry.resolve(repo, config.clone()).await?;
320 out.push(entry);
321 }
322 Ok(Diff { entries: out })
323 }
324}
325
326async fn tree<G: FileSystem>(repo: &Repo<G>, id: ObjectId) -> GResult<Tree> {
327 repo.lookup_object(id)
328 .await?
329 .peel_to_tree(repo)
330 .await?
331 .ok_or_else(|| Error::MalformedObject(id))
332}
333
334impl DiffEntry<(ObjectId, ObjectId)> {
335 pub async fn resolve<G: FileSystem>(
336 &self,
337 repo: &Repo<G>,
338 config: TextDiffConfig,
339 ) -> GResult<DiffEntry<TextDiff<'static, 'static, [u8]>>> {
340 match self {
341 DiffEntry::LeftOnly {
342 path,
343 entry_type,
344 content: (id, _),
345 } => {
346 let body = read_leaf(repo, *entry_type, *id).await?;
347 Ok(DiffEntry::LeftOnly {
348 path: path.clone(),
349 entry_type: *entry_type,
350 content: config.diff_lines(body, Vec::new()),
351 })
352 }
353 DiffEntry::RightOnly {
354 path,
355 entry_type,
356 content: (_, id),
357 } => {
358 let body = read_leaf(repo, *entry_type, *id).await?;
359 Ok(DiffEntry::RightOnly {
360 path: path.clone(),
361 entry_type: *entry_type,
362 content: config.diff_lines(Vec::new(), body),
363 })
364 }
365 DiffEntry::Both {
366 path,
367 left_type,
368 right_type,
369 content: (left_id, right_id),
370 } => {
371 let left_body = read_leaf(repo, *left_type, *left_id).await?;
372 let right_body = read_leaf(repo, *right_type, *right_id).await?;
373 let diff = config.diff_lines(left_body, right_body);
374 Ok(DiffEntry::Both {
375 path: path.clone(),
376 left_type: *left_type,
377 right_type: *right_type,
378 content: diff,
379 })
380 }
381 }
382 }
383}
384
385async fn read_leaf<G: FileSystem>(
386 repo: &Repo<G>,
387 entry_type: TreeEntryType,
388 id: ObjectId,
389) -> GResult<Vec<u8>> {
390 debug_assert!(entry_type != TreeEntryType::Tree);
391 if entry_type == TreeEntryType::Commit {
392 let s = format!("{id}");
393 return Ok(s.into_bytes());
394 }
395 let object = repo.lookup_object(id).await?;
396 if let Object::Blob(b) = object {
397 return Ok(b.data_owned());
398 }
399 unreachable!("Tree entry resolved object was not a blob")
400}
401
402#[cfg(test)]
403mod tests {
404 use crate::{
405 Repo,
406 reference::RefName,
407 test::{
408 helpers::{make_basic_repo, make_file},
409 impls::TestFileSystem,
410 },
411 };
412 use futures::executor::block_on;
413 use std::{
414 collections::BTreeSet,
415 fs::{create_dir, remove_file},
416 io::Write,
417 path::PathBuf,
418 };
419
420 use super::*;
421
422 fn head_tree(repo: &Repo<TestFileSystem>) -> Tree {
423 let head = block_on(repo.lookup_ref(&RefName::Head)).unwrap();
424 block_on(head.peel_to_tree(repo)).unwrap().unwrap()
425 }
426
427 #[test]
428 fn diff_same() {
429 let test_repo = make_basic_repo().unwrap();
430 let repo = test_repo.repo();
431 let tree = head_tree(&repo);
432 assert!(
433 block_on(TreeDiff::new(&repo, &tree, &tree))
434 .unwrap()
435 .entries()
436 .is_empty()
437 );
438 }
439
440 #[test]
441 fn basic_root_diff() {
442 let test_repo = make_basic_repo().unwrap();
443 let repo = test_repo.repo();
444 let mut file_a = make_file(&test_repo, "a").unwrap();
445 test_repo.run_git(["add", "--all"]).unwrap();
446 test_repo
447 .commit("a commit", "a user", "an-email", "2000-01-01T00:00:00Z")
448 .unwrap();
449 let before = head_tree(&repo);
450 file_a.write_all(b"some data").unwrap();
451 file_a.flush().unwrap();
452 let mut file_b = make_file(&test_repo, "b").unwrap();
453 file_b.write_all(b"some more data").unwrap();
454 test_repo.run_git(["add", "--all"]).unwrap();
455 test_repo
456 .commit("a commit", "a user", "an-email", "2000-01-01T00:00:00Z")
457 .unwrap();
458 let after = head_tree(&repo);
459 let the_diff = block_on(TreeDiff::new(&repo, &before, &after))
460 .unwrap()
461 .entries()
462 .iter()
463 .map(Clone::clone)
464 .collect::<BTreeSet<_>>();
465 assert_eq!(
466 the_diff,
467 vec![
468 DiffEntry::Both {
469 path: Path(b"a".to_vec()),
470 left_type: TreeEntryType::File,
471 right_type: TreeEntryType::File,
472 content: (
473 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
474 ObjectId::from_hex(b"7c0646bfd53c1f0ed45ffd81563f30017717ca58").unwrap(),
475 ),
476 },
477 DiffEntry::RightOnly {
478 path: Path(b"b".to_vec()),
479 entry_type: TreeEntryType::File,
480 content: (
481 ObjectId::zero(),
482 ObjectId::from_hex(b"dfa37ec69ffae3abcf7efbb386226cb84b510fa8").unwrap()
483 )
484 }
485 ]
486 .into_iter()
487 .collect()
488 );
489 let the_diff = block_on(TreeDiff::new(&repo, &after, &before))
490 .unwrap()
491 .entries()
492 .iter()
493 .map(Clone::clone)
494 .collect::<BTreeSet<_>>();
495 assert_eq!(
496 the_diff,
497 vec![
498 DiffEntry::Both {
499 path: Path(b"a".to_vec()),
500 left_type: TreeEntryType::File,
501 right_type: TreeEntryType::File,
502 content: (
503 ObjectId::from_hex(b"7c0646bfd53c1f0ed45ffd81563f30017717ca58").unwrap(),
504 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
505 ),
506 },
507 DiffEntry::LeftOnly {
508 path: Path(b"b".to_vec()),
509 entry_type: TreeEntryType::File,
510 content: (
511 ObjectId::from_hex(b"dfa37ec69ffae3abcf7efbb386226cb84b510fa8").unwrap(),
512 ObjectId::zero()
513 )
514 }
515 ]
516 .into_iter()
517 .collect()
518 );
519 }
520
521 #[test]
522 fn basic_subtree_diff() {
523 let test_repo = make_basic_repo().unwrap();
524 let repo = test_repo.repo();
525 create_dir(test_repo.location.path().join("dir")).unwrap();
526 let mut file_a = make_file(&test_repo, PathBuf::from("dir").join("a")).unwrap();
527 test_repo.run_git(["add", "--all"]).unwrap();
528 test_repo
529 .commit("a commit", "a user", "an-email", "2000-01-01T00:00:00Z")
530 .unwrap();
531 let before = head_tree(&repo);
532 file_a.write_all(b"some data").unwrap();
533 file_a.flush().unwrap();
534 test_repo.run_git(["add", "--all"]).unwrap();
535 test_repo
536 .commit("a commit", "a user", "an-email", "2000-01-01T00:00:00Z")
537 .unwrap();
538 let after = head_tree(&repo);
539 let the_diff = block_on(TreeDiff::new(&repo, &before, &after))
540 .unwrap()
541 .entries()
542 .iter()
543 .map(Clone::clone)
544 .collect::<BTreeSet<_>>();
545 assert_eq!(
546 the_diff,
547 vec![DiffEntry::Both {
548 path: Path(b"dir/a".to_vec()),
549 left_type: TreeEntryType::File,
550 right_type: TreeEntryType::File,
551 content: (
552 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
553 ObjectId::from_hex(b"7c0646bfd53c1f0ed45ffd81563f30017717ca58").unwrap(),
554 )
555 },]
556 .into_iter()
557 .collect()
558 );
559 let the_diff = block_on(TreeDiff::new(&repo, &after, &before))
560 .unwrap()
561 .entries()
562 .iter()
563 .map(Clone::clone)
564 .collect::<BTreeSet<_>>();
565 assert_eq!(
566 the_diff,
567 vec![DiffEntry::Both {
568 path: Path(b"dir/a".to_vec()),
569 left_type: TreeEntryType::File,
570 right_type: TreeEntryType::File,
571 content: (
572 ObjectId::from_hex(b"7c0646bfd53c1f0ed45ffd81563f30017717ca58").unwrap(),
573 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
574 ),
575 },]
576 .into_iter()
577 .collect()
578 );
579 }
580
581 #[test]
582 fn complex_subtree_diff() {
583 let test_repo = make_basic_repo().unwrap();
584 let repo = test_repo.repo();
585 make_file(&test_repo, "a").unwrap();
586 test_repo.run_git(["add", "--all"]).unwrap();
587 test_repo
588 .commit("a commit", "a user", "an-email", "2000-01-01T00:00:00Z")
589 .unwrap();
590 let before = head_tree(&repo);
591 remove_file(test_repo.location.path().join("a")).unwrap();
592 create_dir(test_repo.location.path().join("a")).unwrap();
593 make_file(&test_repo, PathBuf::from("a").join("b")).unwrap();
594 create_dir(test_repo.location.path().join("dir")).unwrap();
595 make_file(&test_repo, PathBuf::from("dir").join("c")).unwrap();
596 test_repo.run_git(["add", "--all"]).unwrap();
597 test_repo
598 .commit("a commit", "a user", "an-email", "2000-01-01T00:00:00Z")
599 .unwrap();
600 let after = head_tree(&repo);
601 let the_diff = block_on(TreeDiff::new(&repo, &before, &after))
602 .unwrap()
603 .entries()
604 .iter()
605 .map(Clone::clone)
606 .collect::<BTreeSet<_>>();
607 assert_eq!(
608 the_diff,
609 vec![
610 DiffEntry::RightOnly {
611 path: Path(b"a/b".to_vec()),
612 entry_type: TreeEntryType::File,
613 content: (
614 ObjectId::zero(),
615 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
616 )
617 },
618 DiffEntry::LeftOnly {
619 path: Path(b"a".to_vec()),
620 entry_type: TreeEntryType::File,
621 content: (
622 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
623 ObjectId::zero()
624 )
625 },
626 DiffEntry::RightOnly {
627 path: Path(b"dir/c".to_vec()),
628 entry_type: TreeEntryType::File,
629 content: (
630 ObjectId::zero(),
631 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
632 )
633 },
634 ]
635 .into_iter()
636 .collect()
637 );
638 let the_diff = block_on(TreeDiff::new(&repo, &after, &before))
639 .unwrap()
640 .entries()
641 .iter()
642 .map(Clone::clone)
643 .collect::<BTreeSet<_>>();
644 assert_eq!(
645 the_diff,
646 vec![
647 DiffEntry::LeftOnly {
648 path: Path(b"a/b".to_vec()),
649 entry_type: TreeEntryType::File,
650 content: (
651 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
652 ObjectId::zero()
653 )
654 },
655 DiffEntry::RightOnly {
656 path: Path(b"a".to_vec()),
657 entry_type: TreeEntryType::File,
658 content: (
659 ObjectId::zero(),
660 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
661 )
662 },
663 DiffEntry::LeftOnly {
664 path: Path(b"dir/c".to_vec()),
665 entry_type: TreeEntryType::File,
666 content: (
667 ObjectId::from_hex(b"e69de29bb2d1d6434b8b29ae775ad8c2e48c5391").unwrap(),
668 ObjectId::zero()
669 )
670 },
671 ]
672 .into_iter()
673 .collect()
674 );
675 }
676}