1use std::{
25 cmp::Ordering,
26 collections::HashSet,
27 ffi::OsStr,
28 fs, io, mem,
29 os::unix::fs::MetadataExt as _,
30 path::{Component, Path, PathBuf},
31 sync::Arc,
32};
33
34use rayon::iter::{IntoParallelIterator as _, ParallelIterator as _};
35
36use crate::{pool::WorkerPool, warning::Warning};
37
38pub const KIZZ_FILE_NAME: &str = "kizz.md";
40
41#[derive(Debug, Clone, PartialEq, Eq)]
43pub struct KizzFile {
44 pub path: PathBuf,
47 pub relative: PathBuf,
49}
50
51#[derive(Debug, Clone, Default, PartialEq, Eq)]
53pub struct Discovery {
54 pub files: Vec<KizzFile>,
56 pub warnings: Vec<Warning>,
58}
59
60enum Found {
62 File(PathBuf),
64 Warning(Warning),
66}
67
68struct Ancestor {
70 id: (u64, u64),
72 path: PathBuf,
74 parent: Option<Arc<Ancestor>>,
76}
77
78impl Ancestor {
79 fn find(
82 &self,
83 id: (u64, u64),
84 ) -> Option<&Self> {
85 let mut current = Some(self);
86 while let Some(ancestor) = current {
87 if ancestor.id == id {
88 return Some(ancestor);
89 }
90 current = ancestor.parent.as_deref();
91 }
92 None
93 }
94}
95
96struct Pending {
98 dir: Arc<Ancestor>,
100}
101
102#[derive(Default)]
104struct Read {
105 found: Vec<Found>,
107 next: Vec<Pending>,
109}
110
111impl Read {
112 fn warn(
115 &mut self,
116 root: &Path,
117 path: &Path,
118 error: &io::Error,
119 ) {
120 if let Some(warning) = walk_warning(root, path, error) {
121 self.found.push(Found::Warning(warning));
122 }
123 }
124}
125
126fn id_of(metadata: &fs::Metadata) -> (u64, u64) {
128 (metadata.dev(), metadata.ino())
129}
130
131#[must_use]
137pub fn discover(
138 root: &Path,
139 pool: &WorkerPool,
140) -> Discovery {
141 let mut items: Vec<Found> = Vec::new();
142 match fs::metadata(root) {
143 Ok(metadata) => {
144 let mut level = vec![Pending {
145 dir: Arc::new(Ancestor {
146 id: id_of(&metadata),
147 path: root.to_path_buf(),
148 parent: None,
149 }),
150 }];
151 while !level.is_empty() {
152 let reading = mem::take(&mut level);
153 let reads: Vec<Read> = pool.install(move || {
154 reading
155 .into_par_iter()
156 .map(|pending| read(root, &pending))
157 .collect()
158 });
159 for read in reads {
160 items.extend(read.found);
161 level.extend(read.next);
162 }
163 }
164 },
165 Err(error) => {
166 if let Some(warning) = walk_warning(root, root, &error) {
167 items.push(Found::Warning(warning));
168 }
169 },
170 }
171
172 let mut found: Vec<KizzFile> = Vec::new();
173 let mut warnings: Vec<Warning> = Vec::new();
174 for item in items {
175 match item {
176 Found::File(path) => {
177 found.push(KizzFile {
178 relative: relative_to(root, &path),
179 path,
180 });
181 },
182 Found::Warning(warning) => warnings.push(warning),
183 }
184 }
185 found.sort_by(|a, b| default_order(&a.relative, &b.relative));
186
187 let mut seen: HashSet<PathBuf> = HashSet::new();
188 let mut files: Vec<KizzFile> = Vec::new();
189 for file in found {
190 match fs::canonicalize(&file.path) {
191 Ok(real) => {
192 if seen.insert(real) {
193 files.push(file);
194 }
195 },
196 Err(error) => {
197 warnings.push(Warning::Unreadable {
198 path: file.relative,
199 reason: error.to_string(),
200 });
201 },
202 }
203 }
204 warnings.sort();
205 warnings.dedup();
206 Discovery { files, warnings }
207}
208
209fn read(
213 root: &Path,
214 pending: &Pending,
215) -> Read {
216 let mut read = Read::default();
217 let dir = &pending.dir;
218 let entries = match fs::read_dir(&dir.path) {
219 Ok(entries) => entries,
220 Err(error) => {
221 read.warn(root, &dir.path, &error);
222 return read;
223 },
224 };
225 for entry in entries {
226 let entry = match entry {
227 Ok(entry) => entry,
228 Err(error) => {
229 read.warn(root, &dir.path, &error);
230 continue;
231 },
232 };
233 let path = entry.path();
234 let file_type = match entry.file_type() {
235 Ok(file_type) => file_type,
236 Err(error) => {
237 read.warn(root, &path, &error);
238 continue;
239 },
240 };
241 let link = file_type.is_symlink();
242 let metadata = if link || file_type.is_dir() {
244 let metadata = if link {
245 fs::metadata(&path)
246 } else {
247 entry.metadata()
248 };
249 match metadata {
250 Ok(metadata) => Some(metadata),
251 Err(error) => {
252 read.warn(root, &path, &error);
253 continue;
254 },
255 }
256 } else {
257 None
258 };
259 let is_file = metadata
260 .as_ref()
261 .map_or(file_type.is_file(), fs::Metadata::is_file);
262 if is_file {
263 if entry.file_name() == OsStr::new(KIZZ_FILE_NAME) {
264 read.found.push(Found::File(path));
265 }
266 continue;
267 }
268 let Some(metadata) = metadata.filter(fs::Metadata::is_dir) else {
269 continue;
270 };
271 let id = id_of(&metadata);
272 if link && let Some(ancestor) = dir.find(id) {
273 read.found.push(Found::Warning(Warning::RecursiveLink {
274 link: relative_to(root, &path),
275 ancestor: relative_to(root, &ancestor.path),
276 }));
277 continue;
278 }
279 read.next.push(Pending {
280 dir: Arc::new(Ancestor {
281 id,
282 path,
283 parent: Some(Arc::clone(dir)),
284 }),
285 });
286 }
287 read
288}
289
290#[must_use]
296pub fn default_order(
297 a: &Path,
298 b: &Path,
299) -> Ordering {
300 fn key(path: &Path) -> (Vec<&[u8]>, &[u8]) {
302 let directories = path.parent().map_or_default(|parent| {
303 parent
304 .components()
305 .filter(|component| matches!(component, Component::Normal(_)))
306 .map(|component| component.as_os_str().as_encoded_bytes())
307 .collect()
308 });
309 let name = path.file_name().map_or_default(OsStr::as_encoded_bytes);
310 (directories, name)
311 }
312 key(a).cmp(&key(b))
313}
314
315fn relative_to(
317 root: &Path,
318 path: &Path,
319) -> PathBuf {
320 path.strip_prefix(root)
321 .map_or_else(|_| path.to_path_buf(), Path::to_path_buf)
322}
323
324fn walk_warning(
328 root: &Path,
329 path: &Path,
330 error: &io::Error,
331) -> Option<Warning> {
332 let path = relative_to(root, path);
333 let vanished = error.kind() == io::ErrorKind::NotFound;
334 if vanished && path.file_name() != Some(OsStr::new(KIZZ_FILE_NAME)) {
335 return None;
336 }
337 Some(Warning::Unreadable {
338 path,
339 reason: error.to_string(),
340 })
341}
342
343#[cfg(test)]
345#[allow(
346 clippy::disallowed_macros,
347 clippy::disallowed_methods,
348 reason = "test code: the tests assert and lock"
349)]
350mod tests {
351 use std::{
352 cmp::Ordering,
353 fs, io,
354 os::unix::fs::symlink,
355 path::{Path, PathBuf},
356 };
357
358 use super::{default_order, discover};
359 use crate::{pool::WorkerPool, warning::Warning};
360
361 fn pool() -> WorkerPool {
363 WorkerPool::new().unwrap()
364 }
365
366 fn write(
368 root: &Path,
369 path: &str,
370 content: &str,
371 ) {
372 let path = root.join(path);
373 fs::create_dir_all(path.parent().unwrap()).unwrap();
374 fs::write(path, content).unwrap();
375 }
376
377 fn found(root: &Path) -> Vec<String> {
379 let discovery = discover(root, &pool());
380 assert!(discovery.warnings.is_empty(), "{:?}", discovery.warnings);
381 discovery
382 .files
383 .iter()
384 .map(|file| {
385 assert_eq!(file.path, root.join(&file.relative));
386 file.relative.display().to_string()
387 })
388 .collect()
389 }
390
391 #[test]
394 fn default_order_puts_parents_before_subdirectories() {
395 let mut paths = vec![
396 "b/kizz.md",
397 "a/b/kizz.md",
398 "a/kizz.md",
399 "kizz.md",
400 "a-b/kizz.md",
401 "B/kizz.md",
402 "a/a/z/kizz.md",
403 "a/c/kizz.md",
404 ".hidden/kizz.md",
405 ];
406 paths.sort_by(|a, b| default_order(Path::new(a), Path::new(b)));
407 assert_eq!(paths, [
408 "kizz.md",
409 ".hidden/kizz.md",
410 "B/kizz.md",
411 "a/kizz.md",
412 "a/a/z/kizz.md",
413 "a/b/kizz.md",
414 "a/c/kizz.md",
415 "a-b/kizz.md",
416 "b/kizz.md",
417 ]);
418 assert_eq!(
419 default_order(Path::new("a/kizz.md"), Path::new("a/kizz.md")),
420 Ordering::Equal
421 );
422 }
423
424 #[test]
428 fn finds_every_kizz_md_in_order() {
429 let root = tempfile::tempdir().unwrap();
430 let root = root.path();
431 write(root, ".git/HEAD", "ref: refs/heads/main\n");
432 write(root, ".gitignore", "ignored/\nkizz.md\n*.md\n");
433 write(root, ".ignore", "ignored/\nkizz.md\n");
434 write(root, ".rgignore", "*\n");
435 write(root, "kizz.md", "");
436 write(root, "README.md", "");
437 write(root, "a/kizz.md", "");
438 write(root, "a/b/kizz.md", "");
439 write(root, "a/KIZZ.md", "");
440 write(root, "a/kizz.md.bak", "");
441 write(root, "a/other/notes.md", "");
442 write(root, ".hidden/kizz.md", "");
443 write(root, ".hidden/.deeper/kizz.md", "");
444 write(root, "ignored/kizz.md", "");
445 write(root, "b/kizz.md", "");
446 fs::create_dir_all(root.join("c/kizz.md")).unwrap();
447 write(root, "c/kizz.md/kizz.md", "");
448
449 let expected = [
450 "kizz.md",
451 ".hidden/kizz.md",
452 ".hidden/.deeper/kizz.md",
453 "a/kizz.md",
454 "a/b/kizz.md",
455 "b/kizz.md",
456 "c/kizz.md/kizz.md",
457 "ignored/kizz.md",
458 ];
459 assert_eq!(found(root), expected);
460 for _ in 0..10 {
462 assert_eq!(found(root), expected);
463 }
464 }
465
466 #[test]
468 fn never_looks_above_the_root() {
469 let root = tempfile::tempdir().unwrap();
470 write(root.path(), "kizz.md", "");
471 write(root.path(), "sub/kizz.md", "");
472 write(root.path(), "sub/deeper/kizz.md", "");
473 assert_eq!(found(&root.path().join("sub")), [
474 "kizz.md",
475 "deeper/kizz.md"
476 ]);
477 }
478
479 #[test]
481 fn an_empty_directory_finds_nothing() {
482 let root = tempfile::tempdir().unwrap();
483 assert_eq!(found(root.path()), Vec::<String>::new());
484 }
485
486 const PATH_MAX: usize = 4_096;
489
490 fn too_deep(root: &Path) -> PathBuf {
495 let long = "x".repeat(200);
496 let levels = 25;
497 let mut short = root.join("deep");
500 for _ in 0..levels {
501 short.push("d");
502 }
503 fs::create_dir_all(&short).unwrap();
504 for depth in (1..=levels).rev() {
505 let mut parent = root.join("deep");
506 for _ in 1..depth {
507 parent.push("d");
508 }
509 fs::rename(parent.join("d"), parent.join(&long)).unwrap();
510 }
511 let mut relative = PathBuf::from("deep");
512 loop {
513 relative.push(&long);
514 if root.join(&relative).as_os_str().len() >= PATH_MAX {
515 return relative;
516 }
517 }
518 }
519
520 #[test]
527 fn hidden_directories_links_and_unreadable_directories() {
528 let dir = tempfile::tempdir().unwrap();
529 let root = dir.path();
530 write(root, "kizz.md", "");
531 write(root, ".hidden/kizz.md", "");
532 write(root, "a/kizz.md", "");
533 write(root, "b/kizz.md", "");
534 write(root, "deep/kizz.md", "");
535 symlink("..", root.join("a/up")).unwrap();
536 symlink("../b", root.join("a/sibling")).unwrap();
537 let unreadable = too_deep(root);
538
539 let discovery = discover(root, &pool());
540 let files: Vec<PathBuf> = discovery
541 .files
542 .iter()
543 .map(|file| file.relative.clone())
544 .collect();
545 assert_eq!(
546 files,
547 [
548 "kizz.md",
549 ".hidden/kizz.md",
550 "a/kizz.md",
551 "a/sibling/kizz.md",
552 "deep/kizz.md"
553 ]
554 .map(PathBuf::from)
555 );
556 assert_eq!(discovery.warnings, [
557 Warning::RecursiveLink {
558 link: PathBuf::from("a/up"),
559 ancestor: PathBuf::new(),
560 },
561 Warning::Unreadable {
562 path: unreadable,
563 reason: io::Error::from_raw_os_error(36).to_string(),
564 },
565 ]);
566 }
567}