如何在 Rust 中将扁平的目录路径列表转换为层次结构？

Question

我的输入是一个文件系统路径的扁平列表，它们都是单个顶层目录下的子目录（或其中的文件）。

我的最终输出应该是：

1. 文本层次结构显示路径，类似于UNIX tree命令。 2. 路径的分层JSON序列化，与(1)具有匹配的逻辑结构。

我创建了一种中间数据结构，这是一个自引用的 Dir 结构体，它具有名称和 Box 包装的子目录 Dir 的向量。

我可以成功地使用 Dir 表示任意目录树，如下面的输出所示。

我想使用堆栈处理列表，在每个子目录中添加一个 Dir 并在上升时弹出，但是我似乎无法像在 C 或其他语言中那样让Rust编译器成功。无论我尝试什么，都会得到编译器错误。

如何将扁平列表转换为 Dir 并使编译器满意？或者以其他方式实现(1)和(2)？

// A type to represent a path, split into its component parts
#[derive(Debug)]
struct Path {
    parts: Vec<String>,
}
impl Path {
    pub fn new(path: &str) -> Path {
        Path {
            parts: path.to_string().split("/").map(|s| s.to_string()).collect(),
        }
    }
}

// A recursive type to represent a directory tree.
// Simplification: If it has children, it is considered
// a directory, else considered a file.
#[derive(Debug)]
struct Dir {
    name: String,
    children: Vec<Box<Dir>>,
}

impl Dir {
    fn new(name: &str) -> Dir {
        Dir {
            name: name.to_string(),
            children: Vec::<Box<Dir>>::new(),
        }
    }

    fn has_child(&self, name: &str) -> bool {
        for c in self.children.iter() {
            if c.name == name {
                return true;
            }
        }
        false
    }

    fn add_child<T>(mut self, leaf: T) -> Self
    where
        T: Into<Dir>,
    {
        self.children.push(Box::new(leaf.into()));
        self
    }
}

fn dir(val: &str) -> Dir {
    Dir::new(val)
}

fn main() {
    // Form our INPUT:  a list of paths.
    let paths = vec![
        Path::new("root/child1/grandchild1.txt"),
        Path::new("root/child1/grandchild2.json"),
        Path::new("root/child2/grandchild3.pdf"),
        Path::new("root/child3"),
    ];
    println!("Input Paths:\n{:#?}\n", paths);

    // Transformation:
    // I need an algorithm here that converts the list of paths
    // above to a recursive struct (tree) below.
    // ie: paths --> dir
    let top = dir("root");
    let mut cwd = &top;
    for p in paths.iter() {
        for part in p.parts.iter() {
            if !cwd.has_child(part) {
                // cwd.add_child(dir(part));
                // cwd = &cwd.children[cwd.children.len() - 1];
            }
        }
    }

    // Intermediate Representation:
    // The above transformation should result in the following
    // hierarchical structure.
    let top = dir("root")
        .add_child(
            dir("child1")
                .add_child(dir("grandchild1.txt"))
                .add_child(dir("grandchild2.json")),
        )
        .add_child(dir("child2").add_child(dir("grandchild3.pdf")))
        .add_child(dir("child3"));
    println!("Intermediate Representation of Dirs:\n{:#?}\n\nOutput Tree Format:\n", top);

    // Output:  textual `tree` format
    print_dir(&top, 0);
}

// A function to print a Dir in format similar to unix `tree` command.
fn print_dir(dir: &Dir, depth: u32) {
    if depth == 0 {
        println!("{}", dir.name);
    } else {
        println!(
            "{:indent$}{} {}",
            "",
            "└──",
            dir.name,
            indent = ((depth as usize) - 1) * 4
        );
    }

    for child in dir.children.iter() {
        print_dir(child, depth + 1)
    }
}

输出：

$ ./target/debug/rust-tree                  
Input Paths:
[
    Path {
        parts: [
            "root",
            "child1",
            "grandchild1.txt",
        ],
    },
    Path {
        parts: [
            "root",
            "child1",
            "grandchild2.json",
        ],
    },
    Path {
        parts: [
            "root",
            "child2",
            "grandchild3.pdf",
        ],
    },
    Path {
        parts: [
            "root",
            "child3",
        ],
    },
]

Intermediate Representation of Dirs:
Dir {
    name: "root",
    children: [
        Dir {
            name: "child1",
            children: [
                Dir {
                    name: "grandchild1.txt",
                    children: [],
                },
                Dir {
                    name: "grandchild2.json",
                    children: [],
                },
            ],
        },
        Dir {
            name: "child2",
            children: [
                Dir {
                    name: "grandchild3.pdf",
                    children: [],
                },
            ],
        },
        Dir {
            name: "child3",
            children: [],
        },
    ],
}

Output Tree Format:

root
└── child1
    └── grandchild1.txt
    └── grandchild2.json
└── child2
    └── grandchild3.pdf
└── child3

- danda

---

看起来您的问题可能已经在Cannot move out of borrowed content / cannot move out of behind a shared reference的答案中得到了解答。如果不是，请**[编辑]**您的问题以解释差异。否则，我们可以将此问题标记为已回答。 - Shepmaster

值得指出的是，字符串并不是表示路径的好方法。这就是为什么 Rust 有 Path 类型和相关工具的原因。 - Shepmaster

谢谢，但表示路径不是我所询问的。将路径列表转换为分层结构才是我的目标。 - danda

我阅读了您提供的链接，但它并没有解决问题。我已经尝试了各种使用 &self 的方法，但都无济于事——而使用 clone() 是毫无意义的。因此，如果您将此问题标记为已回答，那么我离解决方案就没有更近了。我已经在 Google 上搜索了很多，但我没有找到任何人做我正在尝试做的事情的例子，这在 Rust 中可能是可行的，但对像我这样学习该语言的人来说并不明显。如果那个链接是相关的，也许您可以修改我提供的代码，并演示它如何解决问题。 - danda

很好，谢谢。但是，我仍然没有得到期望的转换。当我尝试添加一个堆栈时，它再次崩溃了。例如：let stack = Vec::<&mut Dir>::new(); ... stack.push(cwd); - danda

Answer 1

由于有人删除了我的先前带有工作代码链接的答案，所以我将在此发布完整的工作代码。

// A type to represent a path, split into its component parts
#[derive(Debug)]
struct Path {
    parts: Vec<String>,
}
impl Path {
    pub fn new(path: &str) -> Path {
        Path {
            parts: path.to_string().split("/").map(|s| s.to_string()).collect(),
        }
    }
}

// A recursive type to represent a directory tree.
// Simplification: If it has children, it is considered
// a directory, else considered a file.
#[derive(Debug, Clone)]
struct Dir {
    name: String,
    children: Vec<Box<Dir>>,
}

impl Dir {
    fn new(name: &str) -> Dir {
        Dir {
            name: name.to_string(),
            children: Vec::<Box<Dir>>::new(),
        }
    }

    fn find_child(&mut self, name: &str) -> Option<&mut Dir> {
        for c in self.children.iter_mut() {
            if c.name == name {
                return Some(c);
            }
        }
        None
    }

    fn add_child<T>(&mut self, leaf: T) -> &mut Self
    where
        T: Into<Dir>,
    {
        self.children.push(Box::new(leaf.into()));
        self
    }
}

fn dir(val: &str) -> Dir {
    Dir::new(val)
}

fn main() {
    // Form our INPUT:  a list of paths.
    let paths = vec![
        Path::new("child1/grandchild1.txt"),
        Path::new("child1/grandchild2.json"),
        Path::new("child2/grandchild3.pdf"),
        Path::new("child3"),
    ];
    println!("Input Paths:\n{:#?}\n", paths);

    // Transformation:
    // A recursive algorithm that converts the list of paths
    // above to Dir (tree) below.
    // ie: paths --> dir
    let mut top = dir("root");
    for path in paths.iter() {
        build_tree(&mut top, &path.parts, 0);
    }

    println!(
        "Intermediate Representation of Dirs:\n{:#?}\n\nOutput Tree Format:\n",
        top
    );

    // Output:  textual `tree` format
    print_dir(&top, 0);
}

fn build_tree(node: &mut Dir, parts: &Vec<String>, depth: usize) {
    if depth < parts.len() {
        let item = &parts[depth];

        let mut dir = match node.find_child(&item) {
            Some(d) => d,
            None => {
                let d = Dir::new(&item);
                node.add_child(d);
                match node.find_child(&item) {
                    Some(d2) => d2,
                    None => panic!("Got here!"),
                }
            }
        };
        build_tree(&mut dir, parts, depth + 1);
    }
}

// A function to print a Dir in format similar to unix `tree` command.
fn print_dir(dir: &Dir, depth: u32) {
    if depth == 0 {
        println!("{}", dir.name);
    } else {
        println!(
            "{:indent$}{} {}",
            "",
            "└──",
            dir.name,
            indent = ((depth as usize) - 1) * 4
        );
    }

    for child in dir.children.iter() {
        print_dir(child, depth + 1)
    }
}

- danda