基本结构

我们的设计目标是文件目录树，本质上是一个N叉树，N叉树的节点我们怎么设计呢？

enum Node {
    Dir(NodeDir),
    File(String),
}

struct NodeDir {
    name: String,
    children: Vec<Node>,
}

struct Tree {
    root: NodeDir,
}

节点为枚举，支持目录和文件，目录中包含子节点。
首先完善下我们的实现：

// directory tree
enum Node {
    Dir(NodeDir),
    File(NodeFile),
}

impl Node {
    fn new_dir(s: String) -> Self {
        Node::Dir(NodeDir::new(s))
    }
    fn new_file(s: String) -> Self {
        Node::File(NodeFile::new(s))
    }
}

struct NodeDir {
    name: String,
    children: Vec<Node>,
}

struct NodeFile {
    name: String,
}

impl NodeFile {
    fn new(name: String) -> Self {
        NodeFile { name }
    }
}

struct Tree {
    root: NodeDir,
}

impl NodeDir {
    fn new(name: String) -> Self {
        Self {
            name,
            children: vec![],
        }
    }

    fn add_child(&mut self, child: Node) {
        self.children.push(child);
    }

    fn print(&self) {
        print_by_ident(self, 0);
    }
}

fn print_by_ident(n: &NodeDir, level: usize) {
    let mut ident = String::new();
    for _ in 0..level {
        ident.push_str("  ");
    }
    println!("{}{}", ident, n.name);
    for child in &n.children {
        match child {
            Node::Dir(dir) => print_by_ident(dir, level + 1),
            Node::File(file) => println!("  {}{}", ident, file.name),
        }
    }
}

现在我们的节点已经支持打印文件目录树的结构

测试：

fn test1() {
    let mut root = NodeDir::new("/root".to_string());
    let mut fenix = NodeDir::new("fenix".to_string());

    let mut music = NodeDir::new("music".to_string());
    music.add_child(Node::new_file("music1.mp3".to_string()));

    fenix.add_child(Node::Dir(music));
    fenix.add_child(Node::new_dir("game".to_string()));
    root.add_child(Node::new_file("config".to_string()));
    root.add_child(Node::Dir(fenix));
    root.print();
}

----------

/root
  config
  fenix
    music
      music1.mp3
    game

判断目录是否存在

我们现在实现一个判断文件是否存在的函数。
现在我们要将传入的路径进行切分，逐层遍历，如果是目录则继续遍历，如果是文件则判断是不是路径最后一层：如果是则说明文件存在

fn exist(&self, path: String) -> bool {
    let mut cur = &self.root;
    let v = path.split("/").collect::<Vec<&str>>();
    for (i, e) in v.iter().enumerate() {
        let mut found = false;
        for n in &cur.children {
            match n {
                Node::Dir(d) => {
                    if d.name == *e {
                        cur = d;
                        found = true;
                        break;
                    }
                }
                // must be last one
                Node::File(f) => {
                    if i == v.len() - 1 && f.name == *e {
                        return true;
                    }
                }
            }
        }
        if !found {
            return false;
        }
    }
    false
}

测试代码

#[cfg(test)]
mod test {
    use crate::{Node, NodeDir, Tree};

    fn get_fs() -> Tree {
        let mut root = NodeDir::new("/root".to_string());
        let mut fenix = NodeDir::new("fenix".to_string());

        let mut music = NodeDir::new("music".to_string());
        music.add_child(Node::new_file("music1.mp3".to_string()));

        fenix.add_child(Node::Dir(music));
        fenix.add_child(Node::new_dir("game".to_string()));
        root.add_child(Node::new_file("config".to_string()));
        root.add_child(Node::Dir(fenix));

        Tree::from(root)
    }

    
    fn test1() {
        let t = get_fs();
        t.print();
    }

    
    fn test2() {
        let t = get_fs();

        assert!(!t.exist("/home".to_string()));
        assert!(t.exist("/root/config".to_string()));
    }
}

递归创建目录

现在我们实现一个功能：给出一个路径，然后递归创建其目录，如果路径上有文件，则报错

fn mkdir(&mut self, path: String) -> bool {
    let mut cur = &self.root;
    let v = path.split("/").collect::<Vec<&str>>();
    for (i, e) in v.iter().enumerate() {
        if e.len() == 0 {
            continue;
        }
        let r = Self::check_in_child(&cur.children, e);
        match r {
            Some(o) => match o {
                Node::Dir(d) => cur = d,
                Node::File(f) => return false,
            },
            None => {
                let g = NodeDir::new(e.to_string());
                cur.add_child(Node::Dir(g));
                cur = g;
            }
        }
    }
    false
}



fn check_in_child<'a, 'b>(children: &'a [Node], target: &'b str) -> Option<&'a Node> {
    for n in children {
        if n.name() == target {
            return Some(n);
        }
    }
    None
}

其中check_in_child用于判断给出的切片中目标节点是否存在，后续会优化为二分搜索实现。这里我们遍历每层名称，如果已经存在该节点则更新cur，如果该节点为file则报错。如果未找到则创建并将其加入子节点。

很快我们就会发现这个行不通 cur = d报错，因为d为不可变NodeDir，所以不能asign给cur

那将改为可变遍历呢？

fn check_in_child_mut<'a, 'b>(children: &'a mut [Node], target: &'b str) -> Option<&'a  mut Node> {
       for n in children {
           if n.name() == target {
               return Some(n);
           }
       }
       None
   }

   fn mkdir(&mut self, path: String) -> bool {
       let mut cur = &mut self.root;
       let v = path.split("/").collect::<Vec<&str>>();
       for (i, e) in v.iter().enumerate() {
           if e.len() == 0 {
               continue;
           }
           let r = Self::check_in_child_mut(&mut cur.children, e);
           match r {
               Some(o) => match o {
                   Node::Dir(d) => cur = d,
                   Node::File(f) => return false,
               },
               None => {
                   let g = NodeDir::new(e.to_string());
                   cur.add_child(Node::Dir(g));
               }
           }
       }
       false
   }

又报错了

1 2	cannot borrow `cur.children` as mutable more than once at a time `cur.children` was mutably borrowed here in the previous iteration of the looprustcClick f

不能在循环中使用可变引用。

以目前的结构来说，实现这样的在遍历的同时作修改似乎是不可能的。这里我们得改变思路了：总的来说，我们希望的是在遍历到目标后将其asgin给cur，这就就会存在遍历是ref 而 cur是mut ref的问题。我们希望NodeDir可以实现clone。我们这里可以将NodeDir改造为：

#[derive(Debug)]
struct NodeDir {
    name: String,
    state: State,
}

#[derive(Debug)]
struct State {
    children: Rc<RefCell<Vec<Node>>>,
}

这样就可以实现：

impl Clone for State {
    fn clone(&self) -> Self {
        Self {
            children: self.children.clone(),
        }
    }
}

impl Clone for NodeDir {
    fn clone(&self) -> Self {
        Self {
            name: self.name.clone(),
            state: self.state.clone(),
        }
    }
}

这种情况下我们就不必纠结ref转换的问题，因此我们的系统支持将Node所有权给出去

fn get(&self, path: String) -> Option<Node> {
    let mut cur = self.root.clone();
    let v = path.split("/").collect::<Vec<&str>>();
    for (i, e) in v.iter().enumerate() {
        if e.len() == 0 {
            continue;
        }
        let mut found = false;
        let cur_clone = cur.clone();
        for n in cur_clone.state.children.borrow().iter() {
            match n {
                Node::Dir(d) => {
                    if d.name == *e {
                        cur = d.clone();
                        found = true;
                        break;
                    }
                }
                // must be last one
                Node::File(f) => {
                    if i == v.len() - 1 && f.name == *e {
                        return Some(Node::File(f.clone()));
                    }
                }
            }
        }
        if !found {
            return None;
        }
    }
    None
}

我们一直烦恼的递归创建目录的问题：

fn mkdir(&mut self, path: String) -> Result<(), FileAlreadyExistError> {
    let mut cur = self.root.clone();
    let v = path.split("/").collect::<Vec<&str>>();
    for e in v {
        if e.len() == 0 {
            continue;
        }
        match cur.mkdir_child(e) {
            Ok(n) => {
                cur = n;
            }
            Err(e) => return Err(e),
        }
    }
    Ok(())
}

fn mkdir_child(&mut self, name: &str) -> Result<NodeDir, FileAlreadyExistError> {
    for ele in self.state.children.borrow().iter() {
        if ele.get_name() == name {
            if let Node::Dir(d) = ele {
                return Ok(d.clone());
            } else {
                return Err(FileAlreadyExistError);
            }
        }
    }
    let new_dir = NodeDir::new(name.to_string());
    self.add_child(Node::Dir(new_dir));
    let b = self.state.children.borrow();
    let g = b.last().unwrap();
    if let Node::Dir(n) = g {
        return Ok(n.clone());
    } else {
        panic!("error");
    }
}

这里mkdir_child中把新建的节点加入到children中，last().unwrap() 的方式有点丑陋。

顺利成章的，创建文件也就可以实现了。

创建文件

fn touch(&mut self, name: &str) {
    let mut cur = self.root.clone();
    let v = name.split("/").collect::<Vec<&str>>();
    for (i, e) in v.iter().enumerate() {
        if e.len() == 0 {
            continue;
        }
        if i == v.len() - 1 {
            cur.add_child(Node::new_file(e.to_string()));
        } else {
            match cur.mkdir_child(e) {
                Ok(n) => {
                    cur = n;
                }
                Err(_) => panic!("error"),
            }
        }
    }
}

我们还可以对打印文件树的方法做些，优化，令他们可以打印Node类型


fn print_by_ident(n: &NodeDir, level: usize) {
    let mut ident = String::new();
    for _ in 0..level {
        ident.push_str("  ");
    }
    println!("[dir] {}{}", ident, n.name);
    for child in &n.state.children.borrow()[..] {
        match child {
            Node::Dir(dir) => print_by_ident(dir, level + 1),
            Node::File(file) => println!("[file]  {}{}", ident, file.name),
        }
    }
}

测试一下

#[test]
fn test4() {
    let mut t = get_fs();
    t.print();
    t.mkdir("/root/music/1/2/3".to_string()).unwrap();
    t.mkdir("/root/music/1/2/3".to_string()).unwrap();
    assert!(t.get("/root/music/1/2/3".to_string()).is_some());
    t.print();
}

#[test]
fn test5() {
    let mut t = get_fs();
    t.print();
    t.mkdir("/root/music/1/2/3".to_string()).unwrap();
    t.touch("/root/abc");
    t.print();
    assert!(t.get("/root/abc".to_string()).is_some());
}

可见对于大量节点类型的数据结构，尤其是需要在遍历的同时做修改的，使用Rc可能是比较好的处理方式。

ByteDrift

Rust实现的文件目录树

基本结构

判断目录是否存在

递归创建目录

创建文件