//! # recv-dir
//!
//! Simple recursive directory traversal.
//!
//! ## Usage
//!
//! **recv-dir** implements a simple directory traversal, which supports selective directory visit.
//!
//! Since it is a simple iterator, you can use regular iterator functions like `filter` and `map` to
//! ignore individual files or directories, but it does not prevent them from being visited.
//!
//! To ignore directories from being visited, you will need to use a filtered iterator,
//! like the examples below.
//!
//! ## Example
//!
//! ### Visit all directories
//!
//! ```rust
//! use recv_dir::RecursiveDirIterator;
//! let dir = RecursiveDirIterator::from_root("test_dir").unwrap();
//!
//! for entry in dir {
//!    println!("{:?}", entry);
//! }
//! ```
//!
//! ### Ignore symlinks
//!
//! ```rust
//! use std::path::Path;
//! use recv_dir::RecursiveDirIterator;
//! let dir = RecursiveDirIterator::with_closure_filter("test_dir", |dir: &Path| !dir.is_symlink()).unwrap();
//!
//! for entry in dir {
//!    println!("{:?}", entry);
//! }
//! ```
//!
//! ### Control depth
//!
//! Visits only the files in `test_dir`:
//!
//! ```rust
//! use std::path::{Path, PathBuf};
//! use recv_dir::RecursiveDirIterator;
//! let root = PathBuf::from("test_dir");
//! let ancestors = root.ancestors().count();
//! let dir = RecursiveDirIterator::with_closure_filter(root, |dir: &Path| dir.ancestors().count() - ancestors <= 1).unwrap();
//!
//! for entry in dir {
//!    println!("{:?}", entry);
//! }
//! ```
//!
//! Visits the files in `test_dir` and in first-level sub directories:
//!
//! ```rust
//! use std::path::{Path, PathBuf};
//! use recv_dir::RecursiveDirIterator;
//! let root = PathBuf::from("test_dir");
//! let ancestors = root.ancestors().count();
//! let dir = RecursiveDirIterator::with_closure_filter(root, |dir: &Path| dir.ancestors().count() - ancestors <= 2).unwrap();
//!
//! for entry in dir {
//!    println!("{:?}", entry);
//! }
//! ```
//!
//! You can also compose the filters:
//!
//! ```rust
//! use std::num::NonZeroUsize;
//! use std::path::{Path, PathBuf};
//! use recv_dir::{Filter, MaxDepth, NoSymlink, RecursiveDirIterator};
//! let root = PathBuf::from("test_dir");
//! let dir = RecursiveDirIterator::with_filter(&root, NoSymlink.and(MaxDepth::new(&root, NonZeroUsize::new(2).unwrap()))).unwrap();
//!
//! for entry in dir {
//!    println!("{:?}", entry);
//! }
//! ```
//!
//! ## Order
//!
//! There is no guarantee on the order of the traversal, it may be OS-dependent, File System-dependent or completely
//! arbitrary.
//!
//! But it does not means that there is no guarantees at all, this crate relies on [`std::fs::read_dir`],
//! and it is expected that, at least, the same directory is not visited twice. Although it is extremely
//! unlikely to happen, it is still possible, mainly when considering symlink recursions.
//!
//! Some filesystems has a very consistent order of traversal, and others don't, directories are commonly
//! stored in B-trees (or B+ trees), and commonly respects their order, but it may vary.
//!
//! **recv-dir** does not guarantee that either directories or files are visited first, but it is
//! guaranteed that they are visited at some point if accessible, even if directories were already visited.
//!
//! ## Failures
//!
//! Walking the directory tree may fail and at the moment, **recv-dir** will only fail if the base directory
//! cannot be visited, but it will silently ignore the sub directories that are not accessible
//! or fails to open.
//!
//! ## Recursion
//!
//! **recv-dir** is stack-based, which means that it will never crash because of recursion limits,
//! however, recursion limits are good to prevent the tree-walk going too deep (and they are also
//! the worse way to handle this and have an extremely negative performance impact).
//!
//! Because it never crashes, if you do visit symlinks (which is the default), you can end up
//! in an infinite symlink recursion, which will cause high-cpu usage and can also cause the
//! stack to grow until it consumes all the available memory, which in a good scenario, means
//! that the program will crash, but in a bad scenario (and if the stack do not grow) it will
//! just run indefinitely.
//!
//! To avoid this, you can either configure a maximum depth or never visit symlinks, since, at the moment,
//! **recv-dir** does not provide a protection against infinite symlink recursion.
//!
//! ## Experiment
//!
//! **This project is part of the [Kores/rust-experiments](https://gitlab.com/Kores/rust-experiments).**
//!

mod filter;

pub use crate::filter::{Accept, Closure, Filter, MaxDepth, NoSymlink, This};
use std::fs::{read_dir, ReadDir};
use std::num::NonZeroUsize;
use std::path::{Path, PathBuf};

/// Reads the directory recursively without any filter.
///
/// Beaware of the risks of traversing a directory without any filter, like
/// infinite symlink recursion.
pub fn recursive_read_dir<P: AsRef<Path>>(
    dir: P,
) -> std::io::Result<impl Iterator<Item = PathBuf>> {
    RecursiveDirIterator::from_root(dir)
}

/// Holds the state of the directory recursion.
pub struct RecursiveDirIterator<F = Accept> {
    current_iter: Option<ReadDir>,
    dirs: Vec<PathBuf>,
    visit_filter: F,
}

impl RecursiveDirIterator {
    /// Creates a iterator that starts right from the provided directory.
    ///
    /// The iterator will visit all directories, regardless if they are symlinks or not.
    pub fn from_root(path: impl AsRef<Path>) -> std::io::Result<Self> {
        let r = read_dir(path)?;

        Ok(RecursiveDirIterator {
            current_iter: Some(r),
            dirs: vec![],
            visit_filter: Accept,
        })
    }
}

impl RecursiveDirIterator<NoSymlink> {
    /// Creates a iterator that starts right from the provided directory.
    ///
    /// The iterator will visit all directories but will ignore any symlinks.
    pub fn from_root_no_symlinks(path: impl AsRef<Path>) -> std::io::Result<Self> {
        let r = read_dir(path)?;

        Ok(RecursiveDirIterator {
            current_iter: Some(r),
            dirs: vec![],
            visit_filter: NoSymlink,
        })
    }
}

impl RecursiveDirIterator<MaxDepth> {
    /// Creates a iterator that starts right from the provided directory up to a max depth.
    pub fn from_root_max_depth(
        path: impl AsRef<Path>,
        max_depth: NonZeroUsize,
    ) -> std::io::Result<Self> {
        let initial_depth = path.as_ref().ancestors().count();
        let r = read_dir(path)?;

        Ok(RecursiveDirIterator {
            current_iter: Some(r),
            dirs: vec![],
            visit_filter: MaxDepth(initial_depth, max_depth),
        })
    }
}

impl<F> RecursiveDirIterator<Closure<F>> {
    /// Creates a iterator that starts right from the provided directory with a specific filter
    /// to decide which directories to visit.
    pub fn with_closure_filter(path: impl AsRef<Path>, filter: F) -> std::io::Result<Self>
    where
        F: Into<Closure<F>>,
    {
        let r = read_dir(path)?;

        Ok(RecursiveDirIterator {
            current_iter: Some(r),
            dirs: vec![],
            visit_filter: filter.into(),
        })
    }
}

impl<F> RecursiveDirIterator<This<F>> {
    /// Creates a iterator that starts right from the provided directory with a specific filter
    /// to decide which directories to visit.
    pub fn with_filter(path: impl AsRef<Path>, filter: F) -> std::io::Result<Self>
    where
        F: Filter,
    {
        let r = read_dir(path)?;

        Ok(RecursiveDirIterator {
            current_iter: Some(r),
            dirs: vec![],
            visit_filter: This::new(filter),
        })
    }
}

impl<F> Iterator for RecursiveDirIterator<F>
where
    F: Filter,
{
    type Item = PathBuf;

    fn next(&mut self) -> Option<Self::Item> {
        fn compute_next_iter<VF>(iter: &mut RecursiveDirIterator<VF>) -> Option<ReadDir> {
            while let Some(ref p) = iter.dirs.pop() {
                if let Ok(d) = read_dir(p) {
                    return Some(d);
                }
            }
            None
        }

        if let None = self.current_iter {
            self.current_iter = compute_next_iter(self);
        }

        while let Some(ref mut iter) = self.current_iter {
            while let Some(n) = iter.next() {
                if let Ok(n) = n {
                    let path = n.path();

                    if !self.visit_filter.filter(&path) {
                        continue;
                    }

                    if path.is_dir() {
                        self.dirs.push(path.clone());
                    }

                    return Some(path.clone());
                }
            }

            self.current_iter = compute_next_iter(self);
        }

        None
    }
}

#[cfg(test)]
mod tests {
    use crate::{Filter, MaxDepth, NoSymlink, RecursiveDirIterator};
    use std::collections::HashSet;
    use std::num::NonZeroUsize;
    use std::path::{Path, PathBuf};

    #[test]
    fn all_files() {
        let mut dirs = HashSet::new();
        let from_test_dir = RecursiveDirIterator::from_root("test_dir").unwrap();

        for x in from_test_dir {
            dirs.insert(x.to_string_lossy().to_string());
        }

        assert_eq!(dirs.len(), 14);
        assert!(dirs.contains("test_dir/foo"));
        assert!(dirs.contains("test_dir/bar"));
        assert!(dirs.contains("test_dir/baz"));
        assert!(dirs.contains("test_dir/fus"));
        assert!(dirs.contains("test_dir/baz/meow"));
        assert!(dirs.contains("test_dir/baz/meow/oof"));
        assert!(dirs.contains("test_dir/baz/meow/uuf"));
        assert!(dirs.contains("test_dir/baz/barbaz"));
        assert!(dirs.contains("test_dir/baz/foobaz"));
        assert!(dirs.contains("test_dir/fus/dragonborn"));
        assert!(dirs.contains("test_dir/fus/dragonborn/witchcraft"));
        assert!(dirs.contains("test_dir/fus/ro"));
        assert!(dirs.contains("test_dir/fus/ro/dah"));
        assert!(dirs.contains("test_dir/fus/ro/dah/dovahkiin"));
    }

    #[test]
    fn no_symlinks() {
        let mut dirs = HashSet::new();
        let from_test_dir =
            RecursiveDirIterator::with_closure_filter("test_dir", |p: &Path| !p.is_symlink())
                .unwrap();

        for x in from_test_dir {
            dirs.insert(x.to_string_lossy().to_string());
        }

        assert_eq!(dirs.len(), 14);
        assert!(dirs.contains("test_dir/foo"));
        assert!(dirs.contains("test_dir/bar"));
        assert!(dirs.contains("test_dir/baz"));
        assert!(dirs.contains("test_dir/fus"));
        assert!(dirs.contains("test_dir/baz/meow"));
        assert!(dirs.contains("test_dir/baz/meow/oof"));
        assert!(dirs.contains("test_dir/baz/meow/uuf"));
        assert!(dirs.contains("test_dir/baz/barbaz"));
        assert!(dirs.contains("test_dir/baz/foobaz"));
        assert!(dirs.contains("test_dir/fus/dragonborn"));
        assert!(dirs.contains("test_dir/fus/dragonborn/witchcraft"));
        assert!(dirs.contains("test_dir/fus/ro"));
        assert!(dirs.contains("test_dir/fus/ro/dah"));
        assert!(dirs.contains("test_dir/fus/ro/dah/dovahkiin"));
    }

    #[test]
    fn depth_1() {
        let mut dirs = HashSet::new();

        let root = PathBuf::from("test_dir");
        let ancestors = root.ancestors().count();

        let from_test_dir = RecursiveDirIterator::with_closure_filter(&root, |p: &Path| {
            p.ancestors().count() - ancestors <= 1
        })
        .unwrap();

        for x in from_test_dir {
            dirs.insert(x.to_string_lossy().to_string());
        }

        assert_eq!(dirs.len(), 4);
        assert!(dirs.contains("test_dir/foo"));
        assert!(dirs.contains("test_dir/bar"));
        assert!(dirs.contains("test_dir/baz"));
        assert!(dirs.contains("test_dir/fus"));
    }

    #[test]
    fn depth_2() {
        let mut dirs = HashSet::new();

        let root = PathBuf::from("test_dir");
        let ancestors = root.ancestors().count();

        let from_test_dir = RecursiveDirIterator::with_closure_filter(&root, |p: &Path| {
            p.ancestors().count() - ancestors <= 2
        })
        .unwrap();

        for x in from_test_dir {
            dirs.insert(x.to_string_lossy().to_string());
        }

        assert_eq!(dirs.len(), 9);
        assert!(dirs.contains("test_dir/foo"));
        assert!(dirs.contains("test_dir/bar"));
        assert!(dirs.contains("test_dir/baz"));
        assert!(dirs.contains("test_dir/fus"));
        assert!(dirs.contains("test_dir/baz/meow"));
        assert!(dirs.contains("test_dir/baz/barbaz"));
        assert!(dirs.contains("test_dir/baz/foobaz"));
        assert!(dirs.contains("test_dir/fus/dragonborn"));
        assert!(dirs.contains("test_dir/fus/ro"));
    }

    #[test]
    fn no_symlink_depth_2() {
        let mut dirs = HashSet::new();

        let root = PathBuf::from("test_dir");
        let ancestors = root.ancestors().count();

        let from_test_dir = RecursiveDirIterator::with_filter(
            &root,
            NoSymlink.and(MaxDepth::new(&root, NonZeroUsize::new(2).unwrap())),
        )
        .unwrap();

        for x in from_test_dir {
            dirs.insert(x.to_string_lossy().to_string());
        }

        assert_eq!(dirs.len(), 9);
        assert!(dirs.contains("test_dir/foo"));
        assert!(dirs.contains("test_dir/bar"));
        assert!(dirs.contains("test_dir/baz"));
        assert!(dirs.contains("test_dir/fus"));
        assert!(dirs.contains("test_dir/baz/meow"));
        assert!(dirs.contains("test_dir/baz/barbaz"));
        assert!(dirs.contains("test_dir/baz/foobaz"));
        assert!(dirs.contains("test_dir/fus/dragonborn"));
        assert!(dirs.contains("test_dir/fus/ro"));
    }
}