diff_trees/
lib.rs

1//! Diff two directory trees based on their contents and format the resulting diff.
2//!
3//! Construct a diff with [`Diff::new`], which can be formatted or inspected.
4
5#![deny(missing_docs)]
6
7use std::fmt::Display;
8use std::ops::Deref;
9use std::path::Path;
10
11use iddqd::IdOrdMap;
12use walkdir::WalkDir;
13
14mod candidate_is_same;
15mod diff_entry;
16mod diff_tag;
17mod display_diff;
18mod display_diff_opts;
19mod error;
20mod hash_file;
21mod path_info;
22mod strip_prefix;
23
24pub use diff_entry::DiffEntry;
25pub use diff_tag::DiffTag;
26pub use display_diff_opts::DisplayDiffOpts;
27pub use error::Error;
28pub use error::HashError;
29pub use error::MetadataError;
30pub use error::Result;
31pub use error::StripPrefixError;
32pub use error::TraverseError;
33pub use error::WalkDirMetadataError;
34
35use candidate_is_same::candidate_is_same;
36use display_diff::DisplayDiff;
37use path_info::PathInfo;
38use strip_prefix::strip_prefix;
39
40/// A diff of trees in terms of relative paths.
41#[derive(Debug)]
42pub struct Diff<'a> {
43    entries: IdOrdMap<DiffEntry<'a>>,
44}
45
46impl<'a> Deref for Diff<'a> {
47    type Target = IdOrdMap<DiffEntry<'a>>;
48
49    fn deref(&self) -> &Self::Target {
50        &self.entries
51    }
52}
53
54impl<'a> IntoIterator for Diff<'a> {
55    type Item = DiffEntry<'a>;
56
57    type IntoIter = iddqd::id_ord_map::IntoIter<Self::Item>;
58
59    fn into_iter(self) -> Self::IntoIter {
60        self.entries.into_iter()
61    }
62}
63
64impl<'a> IntoIterator for &'a Diff<'a> {
65    type Item = &'a DiffEntry<'a>;
66
67    type IntoIter = iddqd::id_ord_map::Iter<'a, DiffEntry<'a>>;
68
69    fn into_iter(self) -> Self::IntoIter {
70        (&self.entries).into_iter()
71    }
72}
73
74impl<'a> Diff<'a> {
75    /// Diff two directory trees.
76    ///
77    /// Paths are compared for equality with [`blake3`], which has good performance characteristics
78    /// in my testing. In the future, I hope to [add pluggable comparators][issue-2], [rename
79    /// detection][issue-9], and the [ability to produce a text diff of the compared
80    /// files][issue-3].
81    ///
82    /// Note that directory entries which appear in both trees are considered to be
83    /// [`DiffTag::Replace`]d, but this does not account for whether or not their contents have
84    /// changed. A future version of this library may do something more intuitive in this case.
85    ///
86    /// [issue-2]: https://github.com/9999years/diff-trees/issues/2
87    /// [issue-9]: https://github.com/9999years/diff-trees/issues/9
88    /// [issue-3]: https://github.com/9999years/diff-trees/issues/3
89    pub fn new(old: &'a Path, new: &'a Path) -> Result<Self> {
90        let mut diff = Self {
91            entries: IdOrdMap::new(),
92        };
93
94        diff.walk_removed_tree(old, new)?;
95        diff.walk_added_tree(new)?;
96
97        Ok(diff)
98    }
99
100    fn walk_removed_tree(&mut self, old: &'a Path, new: &'a Path) -> Result<()> {
101        let walker = WalkDir::new(old).follow_links(true);
102        let mut iterator = walker.into_iter();
103
104        loop {
105            let removed_entry = match iterator.next() {
106                Some(entry) => entry.map_err(|inner| {
107                    Error::Traverse(TraverseError {
108                        path: old.to_path_buf(),
109                        inner,
110                    })
111                }),
112                None => break,
113            }?;
114
115            if removed_entry.depth() == 0 {
116                continue;
117            }
118
119            let relative = strip_prefix(removed_entry.path(), old)?.to_path_buf();
120
121            let removed_metadata =
122                removed_entry
123                    .metadata()
124                    .map_err(|inner| WalkDirMetadataError {
125                        path: removed_entry.path().to_owned(),
126                        inner,
127                    })?;
128
129            let mut entry = DiffEntry {
130                relative,
131                tag: DiffTag::Delete,
132                deleted: None,
133                inserted: None,
134            };
135
136            let candidate = new.join(&entry.relative);
137            let candidate_metadata = match candidate.metadata() {
138                Ok(metadata) => Some(metadata),
139                Err(err) => {
140                    if err.kind() == std::io::ErrorKind::NotFound {
141                        None
142                    } else {
143                        return Err(MetadataError {
144                            path: candidate.clone(),
145                            inner: err,
146                        }
147                        .into());
148                    }
149                }
150            };
151
152            entry.tag = match candidate_metadata.as_ref() {
153                Some(candidate_metadata) => candidate_is_same(
154                    removed_entry.path(),
155                    &removed_metadata,
156                    &candidate,
157                    candidate_metadata,
158                )?,
159                None => DiffTag::Delete,
160            };
161
162            entry.inserted = candidate_metadata.map(|metadata| PathInfo {
163                metadata,
164                base: new,
165            });
166
167            if removed_entry.file_type().is_dir()
168                && let DiffTag::Delete = entry.tag
169            {
170                // Don't recurse if a directory has been removed.
171                iterator.skip_current_dir();
172            }
173
174            entry.deleted = Some(PathInfo {
175                metadata: removed_metadata,
176                base: old,
177            });
178
179            if let Some(overwritten) = self.entries.insert_overwrite(entry) {
180                tracing::debug!(?overwritten, "Got two diff entries for a single path");
181            }
182        }
183        Ok(())
184    }
185
186    fn walk_added_tree(&mut self, new: &'a Path) -> Result<()> {
187        let walker = WalkDir::new(new).follow_links(true);
188        let mut iterator = walker.into_iter();
189
190        loop {
191            let added_entry = match iterator.next() {
192                Some(entry) => entry.map_err(|inner| {
193                    Error::Traverse(TraverseError {
194                        path: new.to_path_buf(),
195                        inner,
196                    })
197                }),
198                None => break,
199            }?;
200
201            if added_entry.depth() == 0 {
202                continue;
203            }
204
205            let relative = strip_prefix(added_entry.path(), new)?.to_path_buf();
206
207            match self.entries.get(relative.as_path()) {
208                Some(diff_entry) => {
209                    if let DiffTag::Delete = diff_entry.tag {
210                        // Don't recurse if a directory has been removed.
211                        iterator.skip_current_dir();
212                        continue;
213                    }
214                }
215                None => {
216                    if added_entry.file_type().is_dir() {
217                        iterator.skip_current_dir();
218                    }
219
220                    if let Some(overwritten) = self.entries.insert_overwrite(DiffEntry {
221                        relative,
222                        tag: DiffTag::Insert,
223                        deleted: None,
224                        inserted: Some(PathInfo {
225                            metadata: added_entry.metadata().map_err(|inner| {
226                                WalkDirMetadataError {
227                                    path: added_entry.path().to_owned(),
228                                    inner,
229                                }
230                            })?,
231                            base: new,
232                        }),
233                    }) {
234                        tracing::debug!(?overwritten, "Got two diff entries for a single path");
235                    };
236                }
237            }
238        }
239        Ok(())
240    }
241
242    /// [`Display`] this diff with the given options.
243    ///
244    /// Note that [`Diff`] already implements [`Display`] with default options, but this method is
245    /// available to enable colored output.
246    pub fn display(&'a self, opts: DisplayDiffOpts) -> impl Display + 'a {
247        DisplayDiff { diff: self, opts }
248    }
249}
250
251/// Display the diff with default options (no ANSI colors).
252impl<'a> Display for Diff<'a> {
253    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
254        self.display(Default::default()).fmt(f)
255    }
256}
257
258#[cfg(test)]
259mod tests {
260    use super::*;
261    use testlib::TempTree;
262
263    #[test]
264    fn test_same_contents() -> Result<()> {
265        let mut old = TempTree::new().unwrap();
266        old.file("puppy", "puppy").unwrap();
267
268        let mut new = TempTree::new().unwrap();
269        new.file("puppy", "puppy").unwrap();
270
271        let diff = Diff::new(old.as_ref(), new.as_ref())?;
272
273        assert_eq!(
274            (&diff)
275                .into_iter()
276                .map(DiffEntry::as_pair)
277                .collect::<Vec<_>>(),
278            vec![(Path::new("puppy"), DiffTag::Equal)]
279        );
280
281        Ok(())
282    }
283
284    #[test]
285    fn test_different_contents() -> Result<()> {
286        let mut old = TempTree::new().unwrap();
287        old.file("puppy", "puppy").unwrap();
288
289        let mut new = TempTree::new().unwrap();
290        new.file("puppy", "doggy").unwrap();
291
292        let diff = Diff::new(old.as_ref(), new.as_ref())?;
293
294        assert_eq!(
295            (&diff)
296                .into_iter()
297                .map(DiffEntry::as_pair)
298                .collect::<Vec<_>>(),
299            vec![(Path::new("puppy"), DiffTag::Replace)]
300        );
301
302        Ok(())
303    }
304
305    #[test]
306    fn test_complex() -> Result<()> {
307        let mut old = TempTree::new().unwrap();
308        old.dir("a")
309            .unwrap()
310            .file("a/1", "1")
311            .unwrap()
312            .file("a/2", "2")
313            .unwrap()
314            .dir("b")
315            .unwrap()
316            .file("b/1", "1")
317            .unwrap()
318            .file("b/2", "2")
319            .unwrap()
320            .dir("c")
321            .unwrap()
322            .file("c/1", "1")
323            .unwrap()
324            .file("c/2", "2")
325            .unwrap();
326
327        let mut new = TempTree::new().unwrap();
328        new.dir("a")
329            .unwrap()
330            .file("a/1", "1")
331            .unwrap()
332            .file("a/2", "2")
333            .unwrap()
334            .dir("b")
335            .unwrap()
336            .file("b/1", "1x")
337            .unwrap()
338            .file("b/2", "2x")
339            .unwrap();
340
341        let diff = Diff::new(old.as_ref(), new.as_ref())?;
342
343        assert_eq!(
344            (&diff)
345                .into_iter()
346                .map(DiffEntry::as_pair)
347                .collect::<Vec<_>>(),
348            vec![
349                (Path::new("a"), DiffTag::Replace),
350                (Path::new("a/1"), DiffTag::Equal),
351                (Path::new("a/2"), DiffTag::Equal),
352                (Path::new("b"), DiffTag::Replace),
353                (Path::new("b/1"), DiffTag::Replace),
354                (Path::new("b/2"), DiffTag::Replace),
355                (Path::new("c"), DiffTag::Delete),
356            ]
357        );
358
359        Ok(())
360    }
361}
diff_trees/lib.rs

diff_trees/
lib.rs
