George V. Reilly

Implementing the Tree command in Rust, part 2: Printing Trees

In Part 1, we saw how to walk directory trees, re­cur­sive­ly using fs::read_dir to construct an in-memory tree of FileNodes. In Part 2, we’ll implement the rest of the core of the tree command: printing the directory tree with Box Drawing characters.

Let’s take a look at some output from tree:

├── os
│   ├── wasi
│   │   ├──
│   │   ├──          ➊
│   │   └── net             ➋
│   │       └──
│   └── windows
│       ├──          ➌
│       ├──
│       ├── io
│       │   └──
│       ├──
│       └──
├── personality
│   ├── dwarf
│   │   ├──
│   │   ├──
│   │   └──
│   ├──
│   └──

The first thing that we notice is that most entries at any level, such as ➊, are preceded by ├──, while the last entry, ➋, is preceded by └──. This article about building a directory tree generator in Python calls them the tee and elbow connectors, and I’m going to use that ter­mi­nol­o­gy.

The second thing we notice is that there are multiple prefixes before the connectors, either │   (pipe) or     (space), one prefix for each level. The rule is that children of a last entry, such as os/windows ➌, get the space prefix, while children of other entries, such as os/wasi or per­son­al­i­ty, get the pipe prefix.

For both connectors and prefixes, the last entry at a particular level gets special treatment.

The print_tree function

A classic technique with recursion is to create a pair of functions: an outer public function that calls a private helper function with the initial set of parameters to visit re­cur­sive­ly.

Our print_tree function uses an inner visit function to re­cur­sive­ly do almost all of the work.

pub fn print_tree(root: &str, dir: &Directory) {
    const OTHER_CHILD: &str = "│   ";   // prefix: pipe
    const OTHER_ENTRY: &str = "├── ";   // connector: tee
    const FINAL_CHILD: &str = "    ";   // prefix: no more siblings
    const FINAL_ENTRY: &str = "└── ";   // connector: elbow

    println!("{}", root);                                           
    let (d, f) = visit(dir, "");
    println!("\n{} directories, {} files", d, f);

    fn visit(node: &Directory, prefix: &str) -> (usize, usize) {    
        let mut dirs: usize = 1; // counting this directory         ➌
        let mut files: usize = 0;
        let mut count = node.entries.len();                         
        for entry in &node.entries {
            count -= 1;
            let connector =
                if count == 0 { FINAL_ENTRY } else { OTHER_ENTRY }; 
            match entry {
                FileTree::DirNode(sub_dir) => {                     
                    println!("{}{}{}", prefix, connector,;
                    let new_prefix = format!(                       
                        if count == 0 { FINAL_CHILD } else { OTHER_CHILD }
                    let (d, f) = visit(&sub_dir, &new_prefix);      
                    dirs += d;
                    files += f;
                FileTree::LinkNode(symlink) => {
                        "{}{}{} -> {}", prefix, connector,
                    files += 1;
                FileTree::FileNode(file) => {
                    println!("{}{}{}", prefix, connector,;
                    files += 1;
        (dirs, files)                                               
  1. The outer function, print_tree, simply prints the name of the root node on a line by itself; calls the inner visit function with the dir node and an empty prefix; and finally prints the number of di­rec­to­ries and files visited. This is for com­pat­i­bil­i­ty with the output of tree.
  2. The inner visit function takes two parameters: node, a Directory, and prefix, a string which is initially empty.
  3. Keep track of the number of dirs and files seen at this level and in sub-di­rec­to­ries.
  4. We count downwards from the number of entries in this directory to zero. When count is zero, we are on the last entry, which gets special treatment.
  5. Compute the connector, └── (elbow) for the last entry; ├── (tee) otherwise.
  6. Match the FileTree::DirNode variant and de­struc­ture the value into sub_dir, a &Directory.
  7. Before re­cur­sive­ly visiting a sub-directory, we compute a new prefix, by appending the ap­pro­pri­ate sub-prefix to the current prefix. If there are further entries (count > 0), the sub-prefix for the current level is │   (pipe); otherwise, it’s     (spaces).
  8. Call visit re­cur­sive­ly, then add to the running totals of dirs and files.
  9. visit returns a tuple of the counts of di­rec­to­ries and files that were re­cur­sive­ly visited.

One subtlety that is not obvious from the above is that OTH­ER_CHILD actually contains two non-breaking spaces:

const OTHER_CHILD: &str = "│\u{00A0}\u{00A0} "; // prefix: pipe

This is for com­pat­i­bil­i­ty with the output of tree:

$ diff <(cargo run -q -- ./tests) <(tree ./tests) && echo "no difference"
no difference

Using process sub­sti­tu­tion to generate two different inputs for diff.

The main function

Let’s tie it all together.

fn main() -> io::Result<()> {
    let root = env::args().nth(1).unwrap_or(".".to_string());   
    let dir: Directory = dir_walk(                              
    print_tree(&root, &dir);                                    
  1. The simplest possible way to get a single, optional command-line argument. If omitted, we default to ., the current directory. For more so­phis­ti­cat­ed argument parsing, we could use Clap.
  2. Use dir_walk from Part 1 to re­cur­sive­ly build a directory of FileTree nodes.
  3. Create a PathBuf from root, a string; clone is needed because PathBuf::from takes ownership of the string buffer. Use the is_not_hid­den filter and the sort_by_­name comparator from Part 1.
  4. The postfix question mark operator, ?, is used to propagate errors.
  5. Let print_tree draw the diagram.
  6. Return the Ok unit result to indicate success.


You can find the Baum source code on GitHub.

In Part 3, we’ll discuss testing.


blog comments powered by Disqus
Implementing the Tree command in Rust, part 1: Walking Directories » « Compressing Tar Files in Parallel