diskr/analyzer/
duplicates.rs

1use crate::scanner::{hash, FsNode};
2use rayon::prelude::*;
3use serde::Serialize;
4use std::collections::{HashMap, HashSet};
5use std::path::{Path, PathBuf};
6
7const DEFAULT_IGNORE_SUBSTRINGS: &[&str] = &[
8    "/.local/share/flatpak/",
9    "/.var/app/",
10    "/.cache/",
11    "/steamapps/compatdata/",
12    "/steamapps/shadercache/",
13    "/Steam/compatibilitytools.d/",
14    "/.steam/",
15    "/.local/share/Steam/",
16    "/lutris/runners/",
17    "/lutris/runtime/",
18    "/.local/share/Trash/",
19    "/snap/",
20    "/var/lib/snapd/",
21    "/target/",
22    "/.cargo/registry/",
23    "/.wine/",
24    "/.local/share/gem/",
25    "/.config/cosmic/",
26    "/.config/google-chrome/",
27    "/.config/Code/",
28    "/.mozilla/",
29    "/.local/share/Trash/",
30];
31
32#[derive(Debug, Clone, Serialize)]
33pub struct DuplicateGroup {
34    pub size: u64,
35    pub paths: Vec<PathBuf>,
36    pub wasted: u64,
37    pub hardlinked: usize,
38}
39
40pub fn find_duplicates(root: &FsNode, min_size: u64) -> Vec<DuplicateGroup> {
41    find_duplicates_filtered(root, min_size, &[], true)
42}
43
44pub fn find_duplicates_filtered(
45    root: &FsNode,
46    min_size: u64,
47    extra_ignores: &[String],
48    use_default_ignores: bool,
49) -> Vec<DuplicateGroup> {
50    let mut files = Vec::new();
51    root.flatten_files(&mut files);
52
53    let is_ignored = |p: &Path| {
54        let s = p.to_string_lossy();
55        (use_default_ignores && DEFAULT_IGNORE_SUBSTRINGS.iter().any(|pat| s.contains(pat)))
56            || extra_ignores.iter().any(|pat| !pat.is_empty() && s.contains(pat.as_str()))
57    };
58
59    let mut by_size: HashMap<u64, Vec<(PathBuf, u64)>> = HashMap::new();
60    for f in files {
61        if f.size >= min_size && !is_ignored(&f.path) {
62            by_size.entry(f.size).or_default().push((f.path.clone(), f.inode));
63        }
64    }
65    by_size.retain(|_, v| v.len() > 1);
66
67    let quick_groups: Vec<(u64, Vec<(PathBuf, u64)>)> = by_size
68        .into_par_iter()
69        .flat_map(|(size, nodes)| {
70            let mut by_quick: HashMap<blake3::Hash, Vec<(PathBuf, u64)>> = HashMap::new();
71            for (path, inode) in nodes {
72                if let Ok(h) = hash::quick_hash(&path) {
73                    by_quick.entry(h).or_default().push((path, inode));
74                }
75            }
76            by_quick
77                .into_iter()
78                .filter(|(_, v)| v.len() > 1)
79                .map(|(_, v)| (size, v))
80                .collect::<Vec<_>>()
81        })
82        .collect();
83
84    let final_groups: Vec<DuplicateGroup> = quick_groups
85        .into_par_iter()
86        .flat_map(|(size, entries)| {
87            let mut by_full: HashMap<blake3::Hash, Vec<(PathBuf, u64)>> = HashMap::new();
88            for (path, inode) in entries {
89                if let Ok(h) = hash::full_hash(&path) {
90                    by_full.entry(h).or_default().push((path, inode));
91                }
92            }
93            by_full
94                .into_iter()
95                .filter(|(_, v)| v.len() > 1)
96                .filter(|(_, v)| {
97                    let paths: Vec<PathBuf> = v.iter().map(|(p, _)| p.clone()).collect();
98                    verify_group(&paths)
99                })
100                .filter(|(_, v)| {
101                    let unique_inodes: HashSet<u64> = v.iter().map(|(_, i)| *i).collect();
102                    unique_inodes.len() > 1
103                })
104                .map(|(_, v)| {
105                    let unique_inodes: HashSet<u64> = v.iter().map(|(_, i)| *i).collect();
106                    let hardlinked = v.len() - unique_inodes.len();
107                    let wasted = size * (unique_inodes.len() as u64 - 1);
108                    let paths = v.into_iter().map(|(p, _)| p).collect();
109                    DuplicateGroup { size, paths, wasted, hardlinked }
110                })
111                .collect::<Vec<_>>()
112        })
113        .collect();
114
115    let mut sorted = final_groups;
116    sorted.sort_by(|a, b| b.wasted.cmp(&a.wasted));
117    sorted
118}
119
120fn verify_group(paths: &[PathBuf]) -> bool {
121    if paths.len() < 2 {
122        return false;
123    }
124    let first = &paths[0];
125    paths[1..].iter().all(|p| hash::bytes_equal(first, p).unwrap_or(false))
126}
diskr/analyzer/duplicates.rs

diskr/analyzer/
duplicates.rs
