Search code examples
recursionrustborrow-checker

How to accumulate values in a recursive function?


I am trying to wrap my head around how the borrow checker works in a recursive function call situation:

fn visit_dirs_rec(dir: &Path, mut acc: Vec<PathBuf>) -> Result<Vec<PathBuf>, io::Error> {
    if dir.is_dir() {
        for entry in std::fs::read_dir(dir)? {
            let entry = entry?;
            let path = entry.path();
            if path.is_dir() {
                visit_dirs_rec(&path, &acc)?;
            } else if path.is_file() {
                acc.push(path)
            } else {
                error!("{:?}", path);
            }
        }
    }
    Ok(acc)
}

fn visit_dirs(dir: &Path) -> Result<Vec<PathBuf>, io::Error> {
    visit_dirs_rec(dir, vec![])
}
error[E0382]: use of moved value: `acc`
  --> src/main.rs:16:39
   |
10 | fn visit_dirs_rec(dir: &Path, mut acc: Vec<PathBuf>) -> Result<Vec<PathBuf>, io::Error> {
   |                               ------- move occurs because `acc` has type `Vec<PathBuf>`, which does not implement the `Copy` trait
11 |     if dir.is_dir() {
12 |         for entry in std::fs::read_dir(dir)? {
   |         ------------------------------------ inside of this loop
...
16 |                 visit_dirs_rec(&path, acc)?;
   |                                       ^^^ value moved here, in previous iteration of loop
   |
note: consider changing this parameter type in function `visit_dirs_rec` to borrow instead if owning the value isn't necessary
  --> src/main.rs:10:40
   |
10 | fn visit_dirs_rec(dir: &Path, mut acc: Vec<PathBuf>) -> Result<Vec<PathBuf>, io::Error> {
   |    -------------- in this function     ^^^^^^^^^^^^ this parameter takes ownership of the value
help: consider cloning the value if the performance cost is acceptable
   |
16 |                 visit_dirs_rec(&path, acc.clone())?;
   |                                          ++++++++

For more information about this error, try `rustc --explain E0382`.
warning: `api` (bin "api") generated 1 warning
error: could not compile `api` (bin "api") due to previous error; 1 warning emitted

Is there a way to make the borrow checker happy without .clone?


Solution

  • You can pass a mutable reference to the function, so all recursive calls will use the same array:

    
    // You need to explicitly mark the function as accepting a mutable reference
    fn visit_dirs_rec(dir: &Path, acc: &mut Vec<PathBuf>) -> Result<(), io::Error> {
        if dir.is_dir() {
            for entry in std::fs::read_dir(dir)? {
                let entry = entry?;
                let path = entry.path();
                if path.is_dir() {
                    visit_dirs_rec(&path, acc)?;
                } else if path.is_file() {
                    acc.push(path)
                } else {
                    error!("{:?}", path);
                }
            }
        }
        // Value is just added to the input variable, so no need to return anything
        Ok(())
    }
    
    fn visit_dirs(dir: &Path) -> Result<Vec<PathBuf>, io::Error> {
        // create a variable for the values to be outputted into
        let mut out = vec![]
        visit_dirs_rec(dir, &mut out)?;
        // return the output
        return Ok(out);
    }