如何在递归函数中累加值？Rust无Clone解决借用检查器问题

问题场景 #

尝试理解递归函数调用下Rust借用检查器的工作机制，编写了递归遍历目录并累加文件路径的代码：

use std::fs;
use std::path::{Path, PathBuf};
use std::io;
use log::error;

fn visit_dirs_rec(dir: &Path, mut acc: Vec<PathBuf>) -> Result<Vec<PathBuf>, io::Error> {
    if dir.is_dir() {
        for entry in 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![])
}

编译时出现错误：

错误[E0382]: 使用了已移动的值: `acc`
  --> src/main.rs:16:39
   |
10 | fn visit_dirs_rec(dir: &Path, mut acc: Vec<PathBuf>) -> Result<Vec<PathBuf>, io::Error> {
   |                               ------- 发生移动是因为`acc`的类型为`Vec<PathBuf>`，未实现`Copy` trait
11 |     if dir.is_dir() {
12 |         for entry in std::fs::read_dir(dir)? {
   |         ------------------------------------ 在此循环内部
...
16 |                 visit_dirs_rec(&path, acc)?;
   |                                       ^^^ 值在此处被移动，在循环的前一次迭代中
   |
提示: 如果不需要拥有所有权，考虑将`visit_dirs_rec`函数的参数类型改为借用
  --> src/main.rs:10:40
   |
10 | fn visit_dirs_rec(dir: &Path, mut acc: Vec<PathBuf>) -> Result<Vec<PathBuf>, io::Error> {
   |    -------------- 在此函数中     ^^^^^^^^^^^^ 该参数获取值的所有权
帮助: 如果性能成本可接受，考虑克隆该值
   |
16 |                 visit_dirs_rec(&path, acc.clone())?;
   |                                          ++++++++

有关此错误的更多信息，请尝试`rustc --explain E0382`。
警告: `api`（二进制文件"api"）生成了1个警告
错误: 由于之前的错误，无法编译`api`（二进制文件"api"）；已发出1个警告

提问：是否存在不使用.clone()就能让借用检查器通过的方法？

解决方案 #

当然可以，核心是避免所有权转移，以下是两种高效的实现方案：

方案一：传递可变引用共享集合 #

修改递归函数参数为可变引用，让所有递归调用共享同一个Vec，完全避免所有权转移：

use std::fs;
use std::path::{Path, PathBuf};
use std::io;
use log::error;

fn visit_dirs_rec(dir: &Path, acc: &mut Vec<PathBuf>) -> io::Result<()> {
    if dir.is_dir() {
        for entry in 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(())
}

fn visit_dirs(dir: &Path) -> io::Result<Vec<PathBuf>> {
    let mut acc = Vec::new();
    visit_dirs_rec(dir, &mut acc)?;
    Ok(acc)
}

这种方式没有额外内存开销，是性能最优的实现。

方案二：递归返回子目录结果并合并 #

如果不想使用可变引用，可以让每个递归调用返回当前目录的文件列表，再合并到上层集合中：

use std::fs;
use std::path::{Path, PathBuf};
use std::io;
use log::error;

fn visit_dirs_rec(dir: &Path) -> io::Result<Vec<PathBuf>> {
    let mut acc = Vec::new();
    if dir.is_dir() {
        for entry in fs::read_dir(dir)? {
            let entry = entry?;
            let path = entry.path();
            if path.is_dir() {
                let sub_files = visit_dirs_rec(&path)?;
                acc.extend(sub_files); // 高效合并子目录结果，无元素复制
            } else if path.is_file() {
                acc.push(path);
            } else {
                error!("{:?}", path);
            }
        }
    }
    Ok(acc)
}

fn visit_dirs(dir: &Path) -> io::Result<Vec<PathBuf>> {
    visit_dirs_rec(dir)
}

这种方式通过Vec的extend方法转移子目录列表的元素所有权，同样不需要clone，性能接近方案一。

内容的提问来源于stack exchange，提问作者Istvan