file manager
git clone https://git.lucas.co/cce-files.git
src/services/scan.rs (9.1K)
1 //! Recursive directory scan feeding the Space (treemap) view.
2 //!
3 //! Unlike `read_directory_internal`, which reads one level and reports each
4 //! entry's own size, this walks the whole subtree and gives every directory
5 //! the sum of what it contains — the number a treemap's area encodes. It runs
6 //! on the `FsService` thread like every other request; the app sees it only as
7 //! progress messages followed by a completed tree.
8
9 use std::path::Path;
10 use std::os::unix::fs::MetadataExt;
11 use std::sync::atomic::{AtomicBool, Ordering};
12 use std::time::{Duration, Instant};
13
14 /// Deepest nesting the walk will descend. Ordinary trees are nowhere near
15 /// this; the cap exists so a pathological one cannot overflow the recursion
16 /// stack.
17 const MAX_DEPTH: u32 = 64;
18
19 /// How often a scan in flight reports what it has counted so far. Short
20 /// enough that the progress line moves, long enough that a fast tree is not
21 /// mostly channel traffic.
22 const PROGRESS_INTERVAL: Duration = Duration::from_millis(150);
23
24 /// One node of a scanned tree. `size` is the recursive total for a directory
25 /// and the apparent size for a file.
26 ///
27 /// Nodes deliberately carry no `PathBuf` — a large tree is millions of nodes,
28 /// and only the few thousand tiles that survive layout culling ever need a
29 /// path. The Space page rebuilds those from the names along the way down.
30 #[derive(Debug, Clone, Default)]
31 pub struct TreeNode {
32 pub name: String,
33 pub size: u64,
34 pub is_dir: bool,
35 /// Sorted descending by `size` — the order the squarified layout wants,
36 /// established once here rather than per frame.
37 pub children: Vec<TreeNode>,
38 }
39
40 #[derive(Debug, Clone, Default)]
41 pub struct ScanResult {
42 pub tree: TreeNode,
43 pub files: u64,
44 pub dirs: u64,
45 /// True when the scan stopped early because its cancel flag was raised —
46 /// the tree is a partial one and should be discarded, not drawn.
47 pub cancelled: bool,
48 }
49
50 struct Walker<'a> {
51 /// Device of the scan root. Entries on any other device are skipped, so
52 /// scanning `/` does not wander into `/proc`, `/sys`, or a mounted backup
53 /// drive — and cannot loop through a bind mount pointing back inside.
54 dev: u64,
55 cancel: &'a AtomicBool,
56 files: u64,
57 dirs: u64,
58 bytes: u64,
59 on_progress: &'a mut dyn FnMut(u64, u64),
60 last_report: Instant,
61 }
62
63 impl Walker<'_> {
64 fn walk(&mut self, dir: &Path, name: String, depth: u32) -> TreeNode {
65 let mut node = TreeNode { name, size: 0, is_dir: true, children: Vec::new() };
66 if depth >= MAX_DEPTH || self.cancel.load(Ordering::Relaxed) {
67 return node;
68 }
69 let Ok(rd) = std::fs::read_dir(dir) else {
70 // Unreadable directory (permissions, races) contributes nothing
71 // rather than aborting the scan around it.
72 return node;
73 };
74
75 for entry in rd.filter_map(|e| e.ok()) {
76 if self.cancel.load(Ordering::Relaxed) {
77 break;
78 }
79 // `DirEntry::metadata` does not traverse symlinks, which is what we
80 // want twice over: a link cannot pull its target's bytes into this
81 // subtree's total, and cannot loop the walk back into itself.
82 let Ok(meta) = entry.metadata() else { continue };
83 let ft = meta.file_type();
84 if ft.is_symlink() || meta.dev() != self.dev {
85 continue;
86 }
87
88 let child_name = entry.file_name().to_string_lossy().into_owned();
89 if ft.is_dir() {
90 self.dirs += 1;
91 let child = self.walk(&entry.path(), child_name, depth + 1);
92 node.size += child.size;
93 node.children.push(child);
94 } else if ft.is_file() {
95 let size = meta.len();
96 self.files += 1;
97 self.bytes += size;
98 node.size += size;
99 node.children.push(TreeNode {
100 name: child_name,
101 size,
102 is_dir: false,
103 children: Vec::new(),
104 });
105 }
106 // Sockets, fifos, and device nodes occupy no meaningful space and
107 // are dropped entirely.
108 self.maybe_report();
109 }
110
111 node.children.sort_unstable_by(|a, b| b.size.cmp(&a.size));
112 node
113 }
114
115 fn maybe_report(&mut self) {
116 if self.last_report.elapsed() >= PROGRESS_INTERVAL {
117 self.last_report = Instant::now();
118 (self.on_progress)(self.files, self.bytes);
119 }
120 }
121 }
122
123 /// Walk `root`, returning its tree with directory sizes summed.
124 ///
125 /// Returns `None` when `root` is not a readable directory. `cancel` is polled
126 /// per entry, so a superseded scan stops within a directory rather than
127 /// running to completion unwatched.
128 pub fn scan(
129 root: &Path,
130 cancel: &AtomicBool,
131 on_progress: &mut dyn FnMut(u64, u64),
132 ) -> Option<ScanResult> {
133 // The root is stat'd through symlinks — the user may well have navigated
134 // to one — while everything beneath it is not.
135 let meta = std::fs::metadata(root).ok()?;
136 if !meta.is_dir() {
137 return None;
138 }
139
140 let name = root
141 .file_name()
142 .map(|n| n.to_string_lossy().into_owned())
143 .unwrap_or_else(|| root.to_string_lossy().into_owned());
144
145 let mut walker = Walker {
146 dev: meta.dev(),
147 cancel,
148 files: 0,
149 dirs: 0,
150 bytes: 0,
151 on_progress,
152 last_report: Instant::now(),
153 };
154 let tree = walker.walk(root, name, 0);
155
156 Some(ScanResult {
157 tree,
158 files: walker.files,
159 dirs: walker.dirs,
160 cancelled: cancel.load(Ordering::Relaxed),
161 })
162 }
163
164 #[cfg(test)]
165 mod tests {
166 use super::*;
167 use std::fs;
168
169 /// A scratch tree: `<tmp>/cce_scan_test_<nanos>/`.
170 fn scratch(tag: &str) -> std::path::PathBuf {
171 let nanos = std::time::SystemTime::now()
172 .duration_since(std::time::UNIX_EPOCH)
173 .unwrap()
174 .as_nanos();
175 let dir = std::env::temp_dir().join(format!("cce_scan_test_{tag}_{nanos}"));
176 fs::create_dir_all(&dir).unwrap();
177 dir
178 }
179
180 #[test]
181 fn sums_sizes_recursively_and_sorts_descending() {
182 let root = scratch("sum");
183 fs::write(root.join("small.txt"), vec![b'a'; 10]).unwrap();
184 let sub = root.join("sub");
185 fs::create_dir(&sub).unwrap();
186 fs::write(sub.join("big.bin"), vec![b'b'; 5000]).unwrap();
187 fs::write(sub.join("mid.bin"), vec![b'c'; 500]).unwrap();
188
189 let cancel = AtomicBool::new(false);
190 let res = scan(&root, &cancel, &mut |_, _| {}).unwrap();
191
192 assert_eq!(res.files, 3);
193 assert_eq!(res.dirs, 1);
194 assert!(!res.cancelled);
195 // The directory carries what it contains, not its own inode size.
196 assert_eq!(res.tree.size, 5510);
197
198 // Children sorted descending: sub (5500) before small.txt (10).
199 assert_eq!(res.tree.children.len(), 2);
200 assert_eq!(res.tree.children[0].name, "sub");
201 assert_eq!(res.tree.children[0].size, 5500);
202 assert!(res.tree.children[0].is_dir);
203 assert_eq!(res.tree.children[1].name, "small.txt");
204
205 // ...and so are the grandchildren.
206 let sub_node = &res.tree.children[0];
207 assert_eq!(sub_node.children[0].name, "big.bin");
208 assert_eq!(sub_node.children[1].name, "mid.bin");
209
210 fs::remove_dir_all(&root).unwrap();
211 }
212
213 #[test]
214 fn symlinks_are_skipped_not_followed() {
215 let root = scratch("link");
216 let real = root.join("real");
217 fs::create_dir(&real).unwrap();
218 fs::write(real.join("data.bin"), vec![b'x'; 1000]).unwrap();
219 // A link back to the root would loop the walk if it were followed, and
220 // a link to the sibling directory would double-count its bytes.
221 std::os::unix::fs::symlink(&root, root.join("loop")).unwrap();
222 std::os::unix::fs::symlink(&real, root.join("alias")).unwrap();
223
224 let cancel = AtomicBool::new(false);
225 let res = scan(&root, &cancel, &mut |_, _| {}).unwrap();
226
227 assert_eq!(res.files, 1);
228 assert_eq!(res.tree.size, 1000);
229 assert_eq!(res.tree.children.len(), 1, "only `real` — both links dropped");
230
231 fs::remove_dir_all(&root).unwrap();
232 }
233
234 #[test]
235 fn cancel_flag_stops_the_walk() {
236 let root = scratch("cancel");
237 for i in 0..50 {
238 fs::write(root.join(format!("f{i}")), vec![b'z'; 100]).unwrap();
239 }
240
241 // Already-raised flag: the walk bails before reading any entry.
242 let cancel = AtomicBool::new(true);
243 let res = scan(&root, &cancel, &mut |_, _| {}).unwrap();
244
245 assert!(res.cancelled);
246 assert_eq!(res.files, 0);
247 assert!(res.tree.children.is_empty());
248
249 fs::remove_dir_all(&root).unwrap();
250 }
251
252 #[test]
253 fn non_directory_root_is_rejected() {
254 let root = scratch("file");
255 let file = root.join("plain.txt");
256 fs::write(&file, b"hello").unwrap();
257
258 let cancel = AtomicBool::new(false);
259 assert!(scan(&file, &cancel, &mut |_, _| {}).is_none());
260
261 fs::remove_dir_all(&root).unwrap();
262 }
263 }