Как создать итератор для рекурсивного обхода файлового дерева?

Question

Я хочу лениво использовать узлы файлового дерева один за другим, сортируя братьев и сестер на каждом уровне.

В 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);
    }
}

Что я хочу ( не еще работает!):

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

Существует два подхода:

Первый - использовать существующий ящик, например 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;
    }
}

детская площадка

Преимущество написания собственного итератора в том, что вы настроите его для своеготочные потребности (сортировка, фильтрация, обработка ошибок и т. д.).Но вам придется иметь дело со своими собственными ошибками.

Answer 2

Это точное решение, которое я искал.Это не мое достижение;см. здесь .Комментарии приветствуются.

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 = move |d: PathBuf| -> Box<dyn Iterator<Item = (PathBuf, PathBuf)>> {
        let mut step = dst_step.clone();
        step.push(PathBuf::from(d.file_name().unwrap()));
        Box::new(traverse_flat_dst_iter(&d, step))
    };
    dirs.into_iter()
        .flat_map(traverse)
        .chain(files.into_iter().map(|f| (f, PathBuf::new())))
}

Еще один, более сложный способ.Нужно упаковать вещи, параметры клонирования, которые будут разделены между лямбдами, и т. Д., Чтобы удовлетворить компилятор.Все же это работает.Будем надеяться, что вы сможете освоить эту вещь.

fn traverse_dir(
    src_dir: &PathBuf,
    dst_step: Vec<PathBuf>,
) -> Box<dyn Iterator<Item = (PathBuf, Vec<PathBuf>)>> {
    let (dirs, files) = groom(src_dir);
    let destination_step = dst_step.clone(); // A clone for handle.

    let traverse = move |d: PathBuf| {
        let mut step = dst_step.clone();
        step.push(PathBuf::from(d.file_name().unwrap()));
        traverse_dir(&d, step)
    };
    let handle = move |f: PathBuf| (f, destination_step.clone());
    if flag("r") {
        // Chaining backwards.
        Box::new(
            files
                .into_iter()
                .map(handle)
                .chain(dirs.into_iter().flat_map(traverse)),
        )
    } else {
        Box::new(
            dirs.into_iter()
                .flat_map(traverse)
                .chain(files.into_iter().map(handle)),
        )
    }
}