现在咱们现已能够得到希望的 AST

接下来就需求依据 AST 来完成咱们的详细需求

本文将依据拜访者形式来完成 AST 的遍历

源码: src/traversal/visitor.rs

拜访者形式

在全文开始之前, 先来介绍拜访者形式(Visitor Mode)

拜访者形式是一种能够将数据模型与逻辑分离的规划形式, 一般在面对需求继续保护很多不同类型的数据, 且针对不同类型的数据有不同的操作逻辑时, 拜访者形式会十分好用, 下面来举个来自refactoring的比方

设想有一位稳妥推销员, 他需求向不同类型的修建推销不同类型的稳妥, 比方

  • 向住所推销医疗稳妥
  • 向银行推销偷窃稳妥
  • 向咖啡店推销洪涝稳妥

在这个比方中, 不同的住所类型便是上面提到的 很多不同类型的数据, 而稳妥推销员便是 拜访者, 拜访者需求依据拜访到的数据的类型履行不同的操作, 以下用 TypeScript 写一段的简略的暗示代码

// 赋予对象拜访的能力
interface Visitor {
  visit_residential(r: Residential);
  visit_bank(b: Bank);
  visit_cafes(c: Cafes);
}
// 赋予对象被 Visitor 被拜访的能力
interface Visitable {
  accept(v: Visitor);
}
class Salesman implements Visitor {
  visit_residential(r: Residential);
  visit_bank(b: Bank);
  visit_cafes(c: Cafes);
}
class Residential implements Visitable {
  accept(v: Visitor) {
    v.visit_residential(this);
  }
}
class Bank implements Visitable {
  accept(v: Visitor) {
    v.visit_bank(this);
  }
}
class Cafes implements Visitable {
  accept(v: Visitor) {
    v.visit_cafes(this)
  }
}

如上就完成了简略的拜访者形式, 主要是为了将逻辑和数据分离, 以上比方中, 数据指的是 Residential, Bank, Cafes 三个类, 逻辑指的是 Visitor 接口中界说的 visit_xxx 办法的详细完成

有什么优点呢, Q&A 再来详谈

Why

为什么遍历个树形结构要用这么烦琐的规划形式呢

先来看节点界说

pub enum Node {
    Literal {
        kind: SyntaxKind,
        value: i32,
        raw: String,
    },
    Expr {
        kind: SyntaxKind,
        left: Box<Node>,
        op: SyntaxKind,
        right: Box<Node>,
    },
}

咱们需求 Literal 中的 value 字段, 也需求 Expr 中的 left, op, right 字段, 其中, 在遇到 left 和 right 时咱们应该测验递归解析, 由于 left 有或许也是一个 Expr

这意味着咱们针对 Literal 和 Expr 会有着不同的拜访逻辑, 咱们无法像遍历一般二叉树相同直接一个递归函数就写完, 再者说 tiny-expr-parser 中只需求两种节点类型, 而大多数的情况下, AST 需求几十种节点类型, 底子无法直接固定拜访逻辑, 因此拜访者形式在这种情境下就十分十分的合适

How

回到 Rust, 咱们正在测验对当前已有的 AST 完成拜访者形式, 咱们可以使用 Trait 来约束详细完成, 如下

pub trait Visitor {
    fn visit_num(&mut self, node: &Node);
    fn visit_expr(&mut self, node: &Node);
}

改善一下

以上界说好了 Literal 和 Expr 对应的拜访办法, 可存在点点问题

试想咱们的拜访者完成这个 Visitor Trait 时自界说拜访逻辑, 需求针对传入参数 node 的的类型做判断, 再界说拜访逻辑, 大致如下

struct V;
impl Visitor for V {
    fn visit_num(&mut self, node: &Node) {
        match node {
            Literal { kind, value, raw } => {
                // ...
            },
            Expr { kind, left, op, right } => {
                // ...
            },
        }
    }
    fn visit_expr(&mut self, node: &Node) {
        match node {
            Literal { kind, value, raw } => {
                // ...
            },
            Expr { kind, left, op, right } => {
                // ...
            },
        }
    }
}

这样的代码很丑很冗余, 咱们应该将拜访的逻辑单独抽离出来, 就像这样

pub trait Visitor {
    fn visit(&mut self, node: &Node) {
        match node {
            // 解构出需求的字段, 直接传入对应的拜访函数
            Node::Literal {
                value, raw, ..
            } => self.visit_num(*value, raw),
            Node::Expr {
                left, op, right, ..
            } => self.visit_expr(left, op.into_str(), right),
        }
    }
    fn visit_num(&mut self, value: i32, raw: &str);
    fn visit_expr(&mut self, left: &Node, op: &str, right: &Node);
}

咱们在 Visitor Trait 中界说 visit 办法并进行默许完成, 这样 visit_xxx 办法只需求承受相应的参数并进行处理即可, 逻辑上会简练不少

再改善一下

理论上拜访者形式貌似是没有返回值的, 可是考虑到后面需求完成求值, 给予返回值会更加方便一些, 使用泛型简略重构一下, 如下

pub trait Visitor<T> {
    fn visit(&mut self, node: &Node) -> T {
        match node {
            Node::Literal {
                value, raw, ..
            } => self.visit_num(*value, raw),
            Node::Expr {
                left, op, right, ..
            } => self.visit_expr(left, op.into_str(), right),
        }
    }
    fn visit_num(&mut self, value: i32, raw: &str) -> T;
    fn visit_expr(&mut self, left: &Node, op: &str, right: &Node) -> T;
}

这样咱们就界说好了咱们需求的 Visitor Trait, 接下来只需求专注于完成需求的 visitor 即可

Q&A

Q: 拜访者形式的优势?

A: 咱们的相关需求其实完全可以将逻辑直接耦合到数据中完成, 比方给 Node 完成一个 get_expr 之类的办法, 返回相应的数据, 可是这样会导致数据和逻辑耦合, 由于 Node 是数据的生产者, 顾客怎么消费数据是顾客的工作, 理应由顾客来完成这个逻辑, 而且悉数耦合在一起或许会不好保护

读者或许会觉得 “啊怎么好的没学到, 光学他人过度规划, 这些代码或许你这辈子都不会再改动”, 好骂! 实际上有一个比较重要的原因在于 tiny-expr-parser 需求完成格式化和求值的需求, 有两个不同的顾客, 需求两套不同的拜访逻辑, 如果将这个逻辑耦合在 Node 的界说中, 会十分厌恶, 写着厌恶, 我想着都厌恶, 所以就单独抽离了

实际上很多时候在拜访者形式的应用场景下是除了拜访者形式其他没得选, 比方硬件适配软件升级, 咱们不或许在升级时对硬件的逻辑进行更改, 软件经过 visitor 来拜访不同的硬件履行相关的逻辑, 硬件只能经过完成封装好的 accept 办法去进行适配

Q: 在这里完成拜访者形式究竟做了什么?

A: 依照我个人的理解, 我以为拜访者形式对于 AST 的遍历来说是完成了逻辑层面的头绪化, 一般对树形结构的头绪化分为前中后序头绪化三种, 这里咱们对 AST 使用 DFS 的遍历思路完成拜访者形式, 实际上是达到了中序头绪化的作用, 只不过一般头绪化会在节点中增加一个指针域去指向后继节点, 而这里咱们将后继隐含在了 visit_expr 的详细完成中, 因此称为逻辑层面的头绪化