Ntree: a reimplementation of the tree utility

Question

tree is described as "a recursive directory listing command that produces a depth indented listing of files" on the homepage for its Linux implementation. I don't know the full history, but it seems too have originated in MS-DOS (correct me if I'm wrong).

I've used the Homebrew port of the Linux version as a reference implementation.

Basic usage

$ tree
.
├── Cargo.lock
├── Cargo.toml
├── LICENSE
├── README.md
└── src
    ├── dummy_processor.rs
    ├── filters.rs
    ├── lib.rs
    ├── main.rs
    ├── print_processor.rs
    ├── tree.rs
    └── tree_processor.rs

1 directory, 11 files

Ntree

I'm new to Rust was in need of a project to practice. tree is a tool I've used a lot and have had thoughts about how to improve and extend it.

ntree is not a finished project. What I'm posting is the first version, which implements the general structure and the options I felt are most important. In the future, I'm looking to add more filters, maybe more output formats like tree and options to show file permissions and the like. I don't plan to implement every single one of trees options (there are a lot).

The project is on Github at jacwah/ntree.

Goals

Apart from learning the Rust language, these are the improvements I want to make over tree:

• Modular and readable code. The source of tree is quite complex.
• Integration with Git. I often find myself wanting the output to filter out gitignored files. ntree supports this through the -g option.
• Improvements to the -I and -P options. These are not implemented yet.

External libraries

I use kbknapp/clap for processing command line arguments and generating the help message. The alexcrichton/git2-rs crate is used for filtering gitignored files. I'm considering rolling with BurntSushi/ignore instead, but I'm not sure.

Primary concerns

• The code dealing with the filters vectors is a mess. I've struggled a lot with the borrow checker and what you see is the result of trail and error until it compiles. There must be a better way to handle it!
• Is it even a good idea to decouple filters from tree::process? An alternative could be to simply create a Walk struct with options that implements each feature as a private method. This would be similar to BurntSushi/ignore.
• As the comment within says, is the implementation of filter_hidden_files sound?
  1. I'm not used to thinking in Unicode. Is it safe to assume a string starting with the byte "." actually starts with the character "."?
  2. I known this isn't how Windows usually represents hidden files. What do Windows users expect from a tool like ntree? Should it check some "permission bit" or do Window's command line tools also use the dot-prefix as hidden file marker?
• I find error handling in Rust hard, especially when it comes to iterators. Right now I've opted to just ignore errors in the filter functions, which I obviously rather wouldn't. What's an elegant way to handle errors in this case?

I've chosen to not include the full source for the project since it might be too long for Code Review. It's licensed under the MPL 2.0.

main.rs

#[macro_use]
extern crate clap;
extern crate ntree;

use std::path::Path;
use std::process;
use ntree::print_processor::{PrintProcessor, SummaryFormat};
use ntree::tree;
use ntree::filters::{filter_hidden_files, filter_non_dirs, GitignoreFilter};

fn main() {
    let argv_matches = clap::App::new("ntree")
        .version(crate_version!())
        .author(crate_authors!())
        .about("New tree -- a modern reimplementation of tree.")
        .arg(clap::Arg::with_name("DIR")
            .help("The directory to list")
            .index(1))
        .arg(clap::Arg::with_name("a")
             .help("Show hidden files")
             .short("a"))
        .arg(clap::Arg::with_name("d")
             .help("List directories only")
             .short("d"))
        .arg(clap::Arg::with_name("git-ignore")
             .help("Do not list git ignored files")
             .short("g"))
        .get_matches();

    let dir = Path::new(argv_matches.value_of("DIR").unwrap_or("."));

    let filter_hidden_files_ref = &filter_hidden_files;
    let filter_non_dirs_ref = &filter_non_dirs;
    let filter_gitignore_maybe = GitignoreFilter::new(dir);
    let filter_gitignore: GitignoreFilter;
    let filter_gitignore_clos;
    let filter_gitignore_ref;

    let mut filters: Vec<&Fn(&Path) -> bool> = Vec::new();

    let mut procor = PrintProcessor::new();

    if !argv_matches.is_present("a") {
        //filters.push(&filter_hidden_files);
        filters.push(filter_hidden_files_ref);
    }

    if argv_matches.is_present("d") {
        //filters.push(&filter_non_dirs);
        filters.push(filter_non_dirs_ref);
        procor.set_summary_format(SummaryFormat::DirCount);
    }

    if argv_matches.is_present("git-ignore") {
        match filter_gitignore_maybe {
            Ok(_) => {
                filter_gitignore = filter_gitignore_maybe.unwrap();
                filter_gitignore_clos = |p: &Path| filter_gitignore.filter(p);
                filter_gitignore_ref = &filter_gitignore_clos;
                filters.push(filter_gitignore_ref);
            },
            Err(err) => {
                println!("{}", err);
                process::exit(1);
            },
        }
    }

    match tree::process(&dir,
                        &mut procor,
                        &filters) {
        Ok(_) => (),
        Err(err) => {
            println!("error: {}", err);
            process::exit(1);
        }
    }
}

lib.rs

pub mod print_processor;
pub mod tree_processor;
pub mod dummy_processor;
pub mod tree;
pub mod filters;

tree.rs

use std::io;
use std::fs::{self, DirEntry};
use std::path::Path;
use std::ops::Fn;
use super::tree_processor::TreeProcessor;

pub fn process<T, F>(dir: &Path, procor: &mut T, filters: &Vec<F>) -> io::Result<()>
    where T: TreeProcessor,
          F: Fn(&Path) -> bool {
    let read_entries = try!(fs::read_dir(dir));

    let mut entries: Vec<DirEntry> = Vec::new();

    for entry in read_entries {
        entries.push(try!(entry));
    }

    entries.retain(|x| filters.iter().all(|f| f(&x.path())));
    procor.open_dir(dir, entries.len());

    for entry in entries {
        let path = entry.path();

        let file_type = try!(entry.file_type());

        if file_type.is_dir() {
            try!(process(&path, procor, filters));
        } else {
            procor.file(&path);
        }
    }

    procor.close_dir();

    Ok(())
}

filters.rs

extern crate git2;

use std::path::Path;
use std::os::unix::ffi::OsStrExt;
use self::git2::Repository;

pub struct GitignoreFilter {
    repo: Repository,
}

impl GitignoreFilter {
    pub fn new(path: &Path) -> Result<Self, git2::Error> {
        match Repository::discover(path) {
            Ok(repo) => Ok(GitignoreFilter { repo: repo }),
            Err(err) => Err(err),
        }
    }

    pub fn filter(&self, path: &Path) -> bool {
        // ./filename paths doesn't seem to work with should_ignore
        let path = path.canonicalize().unwrap();
        match self.repo.status_should_ignore(&path) {
            Ok(result) => !result,
            Err(_) => false,
        }
    }
}

pub fn filter_hidden_files(path: &Path) -> bool {
    // Is this implementation sound?
    static DOT: u8 = '.' as u8;
    let maybe_name = path.file_name();

    match maybe_name {
        Some(name) => name.as_bytes()[0] != DOT,
        _ => false,
    }
}

pub fn filter_non_dirs(path: &Path) -> bool {
    match path.metadata() {
        Ok(data) => data.is_dir(),
        Err(_) => false,
    }
}

Answer 1

main.rs

1. Unneeded unwrap on filter_gitignore_maybe.
2. Prefer if let instead of a match with only one interesting arm.

tree.rs

1. Opening curly brace starts on a line by itself when there is a multiline function declaration.
2. Don't accept a &Vec.
3. Instead of iterating over something and pushing into a vector, use collect; Note that Result can be collected into as well.
4. Use Vec<_> to avoid restating the type when collecting.

filters.rs

1. Check out the combinators on Option and Result. map is invaluable, unwrap_or is useful in this file.

2. Avoid unwrap. Prefer expect because it's much easier to track down when they eventually fail.

3. Can say b'.' to avoid casting with as u8. Can also use b"thing" for a byte string.

4. Use starts_with to be more clear about the operation you are trying to perform.

5. Not sure that the static "DOT" gains much; could just be a local or even inlined.

---

Ok, the big stuff:

I don't like procor as a name. Abbreviations should be extremely common to be used.

The code dealing with the filters vectors is a mess. I've struggled a lot with the borrow checker and what you see is the result of trail and error until it compiles. There must be a better way to handle it!

Since filtering is such a primary concept, my preference would be to promote it to first-class status. Create a trait that we can give names to.

pub trait PathFilter {
    fn filter(&self, path: &Path) -> bool;
}

In combination with this, create an AllFilters that bundles up the handling of dynamic dispatch to multiple filters. You can also implement the trait for any type that implements the Fn trait. These changes clean up the main method a bit. One tradeoff is that it uses heap allocation instead of references.

is the implementation of filter_hidden_files sound? I'm not used to thinking in Unicode. Is it safe to assume a string starting with the byte "." actually starts with the character "."?

In the UTF-8 encoding, the ASCII characters map directly. Anything beyond ASCII starts with the high bit of the leading byte set. However, I think that it's still cleaner to use a byte string.

The real problem with this code is that it is Unix only! You can tell by the use of std::os::unix::ffi::OsStrExt.

I find error handling in Rust hard, especially when it comes to iterators. Right now I've opted to just ignore errors in the filter functions, which I obviously rather wouldn't. What's an elegant way to handle errors in this case?

When you think error handling, think Result. In the easiest case, you can just return a Box<std::error::Error> from your functions. Check out libraries like quick-error or error-chain for more powerful alternatives.

---

main.rs

#[macro_use]
extern crate clap;
extern crate ntree;

use std::path::Path;
use std::process;
use ntree::print_processor::{PrintProcessor, SummaryFormat};
use ntree::tree;
use ntree::filters::{filter_hidden_files, filter_non_dirs, GitignoreFilter, AllFilters};

fn main() {
    let argv_matches = clap::App::new("ntree")
        .version(crate_version!())
        .author(crate_authors!())
        .about("New tree -- a modern reimplementation of tree.")
        .arg(clap::Arg::with_name("DIR")
            .help("The directory to list")
            .index(1))
        .arg(clap::Arg::with_name("a")
             .help("Show hidden files")
             .short("a"))
        .arg(clap::Arg::with_name("d")
             .help("List directories only")
             .short("d"))
        .arg(clap::Arg::with_name("git-ignore")
             .help("Do not list git ignored files")
             .short("g"))
        .get_matches();

    let dir = Path::new(argv_matches.value_of("DIR").unwrap_or("."));

    let mut filters = AllFilters::default();
    let mut procor = PrintProcessor::new();

    if !argv_matches.is_present("a") {
        filters.push(filter_hidden_files);
    }

    if argv_matches.is_present("d") {
        filters.push(filter_non_dirs);
        procor.set_summary_format(SummaryFormat::DirCount);
    }

    if argv_matches.is_present("git-ignore") {
        match GitignoreFilter::new(dir) {
            Ok(filter_gitignore) => {
                filters.push(filter_gitignore);
            },
            Err(err) => {
                println!("{}", err);
                process::exit(1);
            },
        }
    }

    if let Err(err) = tree::process(&dir, &mut procor, &filters) {
        println!("error: {}", err);
        process::exit(1);
    }
}

filters.rs

extern crate git2;

use std::path::Path;
use std::os::unix::ffi::OsStrExt;
use self::git2::Repository;

pub trait PathFilter {
    fn filter(&self, path: &Path) -> bool;
}

impl<F> PathFilter for F
    where F: Fn(&Path) -> bool
{
    fn filter(&self, path: &Path) -> bool {
        (self)(path)
    }
}

pub struct AllFilters {
    filters: Vec<Box<PathFilter>>,
}

impl AllFilters {
    pub fn push<F>(&mut self, f: F)
        where F: PathFilter + 'static
    {
        self.filters.push(Box::new(f))
    }
}

impl Default for AllFilters {
    fn default() -> Self {
        AllFilters {
            filters: Vec::new(),
        }
    }
}

impl PathFilter for AllFilters {
    fn filter(&self, path: &Path) -> bool {
        self.filters.iter().all(|f| f.filter(path))
    }
}

pub struct GitignoreFilter {
    repo: Repository,
}

impl GitignoreFilter {
    pub fn new(path: &Path) -> Result<Self, git2::Error> {
        Repository::discover(path).map(|repo| GitignoreFilter { repo: repo })
    }
}

impl PathFilter for GitignoreFilter {
    fn filter(&self, path: &Path) -> bool {
        // ./filename paths doesn't seem to work with should_ignore
        let path = path.canonicalize().unwrap();
        self.repo.status_should_ignore(&path)
            .map(|result| !result)
            .unwrap_or(false)
    }
}

pub fn filter_hidden_files(path: &Path) -> bool {
    // Is this implementation sound?
    path.file_name()
        .map(|name| !name.as_bytes().starts_with(b"."))
        .unwrap_or(false)
}

pub fn filter_non_dirs(path: &Path) -> bool {
    path.metadata()
        .map(|data| data.is_dir())
        .unwrap_or(false)
}

tree.rs

use std::io;
use std::fs;
use std::path::Path;
use super::tree_processor::TreeProcessor;
use super::filters::PathFilter;

pub fn process<T, F>(dir: &Path, procor: &mut T, filter: &F) -> io::Result<()>
    where T: TreeProcessor,
          F: PathFilter,
{
    let read_entries = try!(fs::read_dir(dir));

    let mut entries: Vec<_> = try!(read_entries.collect());
    entries.retain(|x| filter.filter(&x.path()));
    procor.open_dir(dir, entries.len());

    for entry in entries {
        let path = entry.path();

        let file_type = try!(entry.file_type());

        if file_type.is_dir() {
            try!(process(&path, procor, filter));
        } else {
            procor.file(&path);
        }
    }

    procor.close_dir();

    Ok(())
}

---

why make a boxed copy of filter functions in AllFilters::push?

As something like this grows, it's going to have more and more possible filters and ways of combining those filters. Using references, as the previous code did, works well for smaller amounts, but gets cumbersome when there's lots of options, and is basically untenable once you want to have multiple instances of the same filter (for example, files with "one" and "two" in the name).

Using a boxed trait object instead of a reference trait object is the way to make the code a bit more dynamic.

I chose to do it inside the push method because no one outside the method needs to know that is how we implemented it.