recursion - 如何构建用于递归遍历文件树的迭代器？

Question

我想在对每个级别的 sibling 进行排序时，一个一个地懒惰地消费文件树的节点。

在 Python 中，我会使用同步生成器:

def traverse_dst(src_dir, dst_root, dst_step):
    """
    Recursively traverses the source directory and yields a sequence of (src, dst) pairs;

    """
    dirs, files = list_dir_groom(src_dir) # Getting immediate offspring.

    for d in dirs:
        step = list(dst_step)
        step.append(d.name)
        yield from traverse_dst(d, dst_root, step)

    for f in files:
        dst_path = dst_root.joinpath(step)
        yield f, dst_path

在 Elixir 中，一个(惰性)流:

def traverse_flat_dst(src_dir, dst_root, dst_step \\ []) do
  {dirs, files} = list_dir_groom(src_dir) # Getting immediate offspring.

  traverse = fn d ->
    step = dst_step ++ [Path.basename(d)]
    traverse_flat_dst(d, dst_root, step)
  end

  handle = fn f ->
    dst_path =
      Path.join(
        dst_root,
        dst_step
      )

    {f, dst_path}
  end

  Stream.flat_map(dirs, traverse)
  |> Stream.concat(Stream.map(files, handle))
end

可以看到一些解决递归问题的语言特性:yield from在 Python 中，flat_map在 Elixir 中；后者看起来像是经典的函数式方法。

看起来在 Rust 中任何惰性的东西，它总是一个迭代器。我应该如何在 Rust 中做大致相同的事情？

我想用 dirs 保留递归函数的结构和 files作为路径向量(它们可以选择排序和过滤)。

获取 dirs和 files已经按照我的喜好实现了:

fn folders(dir: &Path, folder: bool) -> Result<Vec<PathBuf>, io::Error> {
    Ok(fs::read_dir(dir)?
        .into_iter()
        .filter(|r| r.is_ok())
        .map(|r| r.unwrap().path())
        .filter(|r| if folder { r.is_dir() } else { !r.is_dir() })
        .collect())
}

fn list_dir_groom(dir: &Path) -> (Vec<PathBuf>, Vec<PathBuf>) {
    let mut dirs = folders(dir, true).unwrap();
    let mut files = folders(dir, false).unwrap();
    if flag("x") {
        dirs.sort_unstable();
        files.sort_unstable();
    } else {
        sort_path_slice(&mut dirs);
        sort_path_slice(&mut files);
    }
    if flag("r") {
        dirs.reverse();
        files.reverse();
    }
    (dirs, files)
}

Vec<PathBuf可以原样迭代，有标准flat_map方法。应该可以实现 Elixir 风格，我只是还想不出来。

这是我已经拥有的。真的工作 ( traverse_flat_dst(&SRC, [].to_vec()); )，我的意思是:

fn traverse_flat_dst(src_dir: &PathBuf, dst_step: Vec<PathBuf>) {
    let (dirs, files) = list_dir_groom(src_dir);

    for d in dirs.iter() {
        let mut step = dst_step.clone();
        step.push(PathBuf::from(d.file_name().unwrap()));
        println!("d: {:?}; step: {:?}", d, step);
        traverse_flat_dst(d, step);
    }
    for f in files.iter() {
        println!("f: {:?}", f);
    }
}

我想要的(还没有工作!):<​​/p>

fn traverse_flat_dst_iter(src_dir: &PathBuf, dst_step: Vec<PathBuf>) {
    let (dirs, files) = list_dir_groom(src_dir);

    let traverse = |d| {
        let mut step = dst_step.clone();
        step.push(PathBuf::from(d.file_name().unwrap()));
        traverse_flat_dst_iter(d, step);

    };
    // This is something that I just wish to be true!
    flat_map(dirs, traverse) + map(files)    
}

本着 Elixir 解决方案的精神，我希望此函数提供一个长的平面文件迭代器。我只是还不能应付必要的返回类型和其他语法。我真的希望这次能说清楚。

我设法编译并运行的内容(无意义，但签名是我真正想要的):

fn traverse_flat_dst_iter(
    src_dir: &PathBuf,
    dst_step: Vec<PathBuf>,
) -> impl Iterator<Item = (PathBuf, PathBuf)> {
    let (dirs, files) = list_dir_groom(src_dir);

    let _traverse = |d: &PathBuf| {
        let mut step = dst_step.clone();
        step.push(PathBuf::from(d.file_name().unwrap()));
        traverse_flat_dst_iter(d, step)
    };
    files.into_iter().map(|f| (f, PathBuf::new()))
}

我还缺少什么:

fn traverse_flat_dst_iter(
    src_dir: &PathBuf,
    dst_step: Vec<PathBuf>,
) -> impl Iterator<Item = (PathBuf, PathBuf)> {
    let (dirs, files) = list_dir_groom(src_dir);

    let traverse = |d: &PathBuf| {
        let mut step = dst_step.clone();
        step.push(PathBuf::from(d.file_name().unwrap()));
        traverse_flat_dst_iter(d, step)
    };
    // Here is a combination amounting to an iterator,
    // which delivers a (PathBuf, PathBuf) tuple on each step.
    // Flat mapping with traverse, of course (see Elixir solution).
    // Iterator must be as long as the number of files in the tree.
    // The lines below look very close, but every possible type is mismatched :(
    dirs.into_iter().flat_map(traverse)
        .chain(files.into_iter().map(|f| (f, PathBuf::new())))

}

Answer 1

有两种方法:

第一个是使用现有的 crate ，例如 walkdir .好处是它经过了很好的测试并提供了许多选项。

第二个是编写自己的 Iterator 实现。这是一个示例，也许是您自己的示例的基础:

struct FileIterator {
    dirs: Vec<PathBuf>, // the dirs waiting to be read
    files: Option<ReadDir>, // non recursive iterator over the currently read dir
}

impl From<&str> for FileIterator {
    fn from(path: &str) -> Self {
        FileIterator {
            dirs: vec![PathBuf::from(path)],
            files: None,
        }
    }
}

impl Iterator for FileIterator {
    type Item = PathBuf;
    fn next(&mut self) -> Option<PathBuf> {
        loop {
            while let Some(read_dir) = &mut self.files {
                match read_dir.next() {
                    Some(Ok(entry)) => {
                        let path = entry.path();
                        if let Ok(md) = entry.metadata() {
                            if md.is_dir() {
                                self.dirs.push(path.clone());
                                continue;
                            }
                        }
                        return Some(path);
                    }
                    None => { // we consumed this directory
                        self.files = None;
                        break; 
                    }
                    _ => { }
                }
            }
            while let Some(dir) = self.dirs.pop() {
                let read_dir = fs::read_dir(&dir);
                if let Ok(files) = read_dir {
                    self.files = Some(files);
                    return Some(dir);
                }
            }
            break; // no more files, no more dirs
        }
        return None;
    }
}

playground

编写自己的迭代器的优点是您可以根据自己的精确需求(排序、过滤、错误处理等)对其进行调整。但是您必须处理自己的错误。