Skip to main content

kizz_core/
discovery.rs

1// Copyright (c) 2026 Sakura Industries LLC.
2//
3// SPDX-License-Identifier: AGPL-3.0-only
4
5//! Discovery of `kizz.md` files.
6//!
7//! Discovery starts in one directory and never looks above it. It finds every file
8//! named exactly `kizz.md` in that directory and every subdirectory, hidden
9//! directories included, with a concurrent walk of its own on the command's worker
10//! pool ([`WorkerPool`]), which consults no Git or ignore-file rule, so none hides a
11//! `kizz.md`. The walk reads the directories of each depth in parallel, then those of
12//! the next depth; it starts no thread of its own.
13//!
14//! Symbolic links to directories are followed, except a link that would make the walk
15//! recurse into one of its own parent directories, which is skipped with a warning:
16//! a link to a directory with the device and inode of the directory that holds it or
17//! of any directory on the walk's path to it. A path that cannot be read is a warning,
18//! with the system's error, except one that vanished during the walk, such as a
19//! dangling symbolic link, whose name is not `kizz.md`. A `kizz.md` reached through
20//! several paths is kept once, under the first of them in the default order of
21//! [`default_order`]. The files and warnings are sorted, so the order in which the
22//! walk finds them changes nothing.
23
24use 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
38/// The name of every file kizz reads to find work.
39pub const KIZZ_FILE_NAME: &str = "kizz.md";
40
41/// A discovered `kizz.md`.
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub struct KizzFile {
44    /// The absolute path through which discovery reached the file: the discovery
45    /// root joined with [`KizzFile::relative`].
46    pub path: PathBuf,
47    /// The path relative to the discovery root.
48    pub relative: PathBuf,
49}
50
51/// What discovery found.
52#[derive(Debug, Clone, Default, PartialEq, Eq)]
53pub struct Discovery {
54    /// The `kizz.md` files, each once, in the default order of [`default_order`].
55    pub files: Vec<KizzFile>,
56    /// The warnings, sorted, so their order is deterministic too.
57    pub warnings: Vec<Warning>,
58}
59
60/// One result that reading a directory reports.
61enum Found {
62    /// A `kizz.md`, by the path the walk reached it through.
63    File(PathBuf),
64    /// A problem that does not stop discovery.
65    Warning(Warning),
66}
67
68/// A directory on the walk's path.
69struct Ancestor {
70    /// The device and inode of the directory.
71    id: (u64, u64),
72    /// The path through which the walk reached it.
73    path: PathBuf,
74    /// The directory that the walk reached it from, or `None` for the root.
75    parent: Option<Arc<Ancestor>>,
76}
77
78impl Ancestor {
79    /// The directory with the device and inode `id` on the walk's path to this one,
80    /// this one included.
81    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
96/// A directory that the walk still has to read, with the walk's path to it.
97struct Pending {
98    /// The directory, which is the last directory of the path.
99    dir: Arc<Ancestor>,
100}
101
102/// What reading one directory found.
103#[derive(Default)]
104struct Read {
105    /// The files and warnings.
106    found: Vec<Found>,
107    /// The subdirectories to read next.
108    next: Vec<Pending>,
109}
110
111impl Read {
112    /// Note the warning for `error`, which reading `path` met, if it hides a
113    /// `kizz.md`.
114    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
126/// The device and inode of the file whose metadata is `metadata`.
127fn id_of(metadata: &fs::Metadata) -> (u64, u64) {
128    (metadata.dev(), metadata.ino())
129}
130
131/// Find every `kizz.md` under `root`, which should be an absolute directory path,
132/// with a concurrent walk on `pool`.
133///
134/// Problems with single entries, such as unreadable directories or recursive
135/// symbolic links, become warnings; discovery itself never fails.
136#[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
209/// Read the directory of `pending`: note each `kizz.md` in it, each warning, and
210/// each subdirectory to read next, following symbolic links to directories except
211/// those that lead back to a directory on the walk's path.
212fn 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        // A symbolic link is followed: what it leads to decides.
243        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/// The default order of `kizz.md` paths relative to the discovery root.
291///
292/// A directory's `kizz.md` comes before every `kizz.md` in its subdirectories, and
293/// sibling directories come in byte order of their names. Plain path sorting would
294/// put `a/b/kizz.md` before `a/kizz.md` instead.
295#[must_use]
296pub fn default_order(
297    a: &Path,
298    b: &Path,
299) -> Ordering {
300    /// The directory components of `path`, as bytes, and its file name.
301    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
315/// `path` relative to `root`, or `path` itself when it is not under `root`.
316fn 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
324/// The warning for `error`, which reading `path` met during the walk, or `None` for
325/// an error that hides no `kizz.md`: a path that vanished, such as a dangling
326/// symbolic link, whose name is not `kizz.md`.
327fn 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/// Unit tests for discovery and its order.
344#[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    /// A worker pool for one discovery.
362    fn pool() -> WorkerPool {
363        WorkerPool::new().unwrap()
364    }
365
366    /// Write `content` to `path` under `root`, creating its directories.
367    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    /// The relative paths of the files that discovery finds under `root`.
378    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    /// A parent directory's `kizz.md` comes before its subdirectories', and sibling
392    /// directories sort by name in byte order.
393    #[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    /// Discovery finds every file named exactly `kizz.md`, in hidden directories
425    /// too, never reads other Markdown, and ignores no file that Git or ignore files
426    /// exclude.
427    #[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        // The parallel walk always gives the same result.
461        for _ in 0..10 {
462            assert_eq!(found(root), expected);
463        }
464    }
465
466    /// Discovery never looks above its root.
467    #[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    /// An empty directory has no `kizz.md` files and no warnings.
480    #[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    /// The length at which Linux refuses to resolve a path: `PATH_MAX`, 4,096 bytes
487    /// with the final NUL byte.
488    const PATH_MAX: usize = 4_096;
489
490    /// Make under `root/deep` a chain of directories with long names, deeper than a
491    /// path can name, and return the path, relative to `root`, of the first one that
492    /// discovery cannot read: the first whose absolute path is [`PATH_MAX`] bytes or
493    /// longer, which even a process that may read every directory cannot read.
494    fn too_deep(root: &Path) -> PathBuf {
495        let long = "x".repeat(200);
496        let levels = 25;
497        // Short names first, then each is renamed, the deepest first, so no call
498        // names a path that is too long.
499        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    /// A tree with a hidden directory, a link to a parent, a link to a sibling and an
521    /// unreadable directory gives exactly the files, in order, and the warnings that
522    /// "Discovery" requires: the link to the parent is skipped with a warning, the
523    /// `kizz.md` reached through the sibling link is kept once, under its first path
524    /// in the default order, and the unreadable directory is a warning with the
525    /// system's error.
526    #[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}