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

diff_trees/
lib.rs
