递归类型、泛型与 trait：搭一棵 AST

1
use std::mem::size_of;
2

3
enum Expr {
4
    Int(i64),
5
    Add(Box<Expr>, Box<Expr>),
6
    List(Vec<Expr>),
7
}
8

9
fn eval(e: &Expr) -> i64 {
10
    match e {
11
        Expr::Int(n) => *n,
12
        Expr::Add(a, b) => eval(a) + eval(b),
13
        Expr::List(items) => items.iter().map(eval).sum(),
14
    }
15
}
16

17
fn main() {
18
    let tree = Expr::Add(
19
        Box::new(Expr::Int(1)),
20
        Box::new(Expr::Add(Box::new(Expr::Int(2)), Box::new(Expr::Int(3)))),
21
    );
22
    println!("eval = {}", eval(&tree));
23
    println!("Box<Expr>      = {} bytes", size_of::<Box<Expr>>());
24
    println!("Vec<Expr>      = {} bytes", size_of::<Vec<Expr>>());
25
    println!("Expr           = {} bytes", size_of::<Expr>());
26
    println!("Option<Box<Expr>> = {} bytes", size_of::<Option<Box<Expr>>>());
27
    println!("Option<i64>    = {} bytes", size_of::<Option<i64>>());
28
    let list = Expr::List(vec![Expr::Int(10), Expr::Int(20)]);
29
    println!("list = {}", eval(&list));
30
}

1
#![forbid(unsafe_code)]
2
//! The Pebble abstract syntax tree.
3
//!
4
//! The AST is where the language stops being text and starts being *structure*.
5
//! Three Rust ideas do most of the work here:
6
//!
7
//! * **Algebraic data types.** [`Expr`] and [`Stmt`] are recursive enums; a
8
//!   program is a `Vec<Stmt>` and an expression is a tree. Rust's `enum` is the
9
//!   single feature that makes writing a compiler pleasant.
10
//! * **`Box`.** Recursive enums need indirection, so child expressions are
11
//!   `Box<Expr>`.
12
//! * **Traits + a visitor.** [`Visit`] is a trait with default methods, and
13
//!   [`AstPrinter`] is one implementation.
14

15
use core::fmt;
16
use std::string::String;
17
use std::vec::Vec;
18

19
pub use pebble_span::{Span, Spanned};

1
/// An identifier: its name plus where it appeared.
2
#[derive(Clone, Debug, PartialEq)]
3
pub struct Ident {
4
    pub name: String,
5
    pub span: Span,
6
}
7

8
impl Ident {
9
    /// Builds an identifier.
10
    #[must_use]
11
    pub fn new(name: impl Into<String>, span: Span) -> Self {
12
        Self {
13
            name: name.into(),
14
            span,
15
        }
16
    }
17
}
18

19
impl fmt::Display for Ident {
20
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
21
        f.write_str(&self.name)
22
    }
23
}

1
/// A statement: something that happens, and may change state.
2
#[derive(Clone, Debug, PartialEq)]
3
pub enum Stmt {
4
    /// `let name = value;`
5
    Let {
6
        name: Ident,
7
        value: Expr,
8
        span: Span,
9
    },
10
    /// `fn name(params) { body }`
11
    Fn {
12
        name: Ident,
13
        params: Vec<Ident>,
14
        body: Vec<Stmt>,
15
        span: Span,
16
    },
17
    /// An expression evaluated for its side effects.
18
    Expr { expr: Expr, span: Span },
19
    /// `if cond { .. } else { .. }`
20
    If {
21
        cond: Expr,
22
        then_branch: Vec<Stmt>,
23
        else_branch: Vec<Stmt>,
24
        span: Span,
25
    },
26
    /// `while cond { .. }`
27
    While {
28
        cond: Expr,
29
        body: Vec<Stmt>,
30
        span: Span,
31
    },
32
    /// `for var in iter { .. }`
33
    For {
34
        var: Ident,
35
        iter: Expr,
36
        body: Vec<Stmt>,
37
        span: Span,
38
    },
39
    /// `return value?;`
40
    Return { value: Option<Expr>, span: Span },
41
    /// `break;`
42
    Break { span: Span },
43
    /// `continue;`
44
    Continue { span: Span },
45
}

1
/// An expression: something that produces a value.
2
#[derive(Clone, Debug, PartialEq)]
3
pub enum Expr {
4
    /// `nil`
5
    Nil { span: Span },
6
    /// `true` / `false`
7
    Bool { value: bool, span: Span },
8
    /// `42`
9
    Int { value: i64, span: Span },
10
    /// `4.2`
11
    Float { value: f64, span: Span },
12
    /// `"hi"`
13
    Str { value: String, span: Span },
14
    /// A variable reference.
15
    Var { name: Ident, span: Span },
16
    /// `[a, b, c]`
17
    List { items: Vec<Expr>, span: Span },
18
    /// `#{ key: value, .. }`
19
    Map {
20
        entries: Vec<(Expr, Expr)>,
21
        span: Span,
22
    },
23
    /// `-x`, `not x`
24
    Unary {
25
        op: UnaryOp,
26
        operand: Box<Expr>,
27
        span: Span,
28
    },
29
    /// `a + b`, `a < b`
30
    Binary {
31
        op: BinaryOp,
32
        lhs: Box<Expr>,
33
        rhs: Box<Expr>,
34
        span: Span,
35
    },
36
    /// `a and b`, short-circuiting
37
    Logical {
38
        op: LogicalOp,
39
        lhs: Box<Expr>,
40
        rhs: Box<Expr>,
41
        span: Span,
42
    },
43
    /// `target = value`
44
    Assign {
45
        target: Box<Expr>,
46
        value: Box<Expr>,
47
        span: Span,
48
    },
49
    /// `callee(args)`
50
    Call {
51
        callee: Box<Expr>,
52
        args: Vec<Expr>,
53
        span: Span,
54
    },
55
    /// `object[index]`
56
    Index {
57
        object: Box<Expr>,
58
        index: Box<Expr>,
59
        span: Span,
60
    },
61
    /// An anonymous function / closure.
62
    Fn {
63
        params: Vec<Ident>,
64
        body: Vec<Stmt>,
65
        span: Span,
66
    },
67
}

1
/// Prefix operators.
2
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
3
pub enum UnaryOp {
4
    /// `-`
5
    Neg,
6
    /// `not` / `!`
7
    Not,
8
}
9

10
/// Infix arithmetic and comparison operators.
11
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
12
pub enum BinaryOp {
13
    Add,
14
    Sub,
15
    Mul,
16
    Div,
17
    Rem,
18
    Eq,
19
    NotEq,
20
    Lt,
21
    LtEq,
22
    Gt,
23
    GtEq,
24
}
25

26
impl fmt::Display for BinaryOp {
27
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
28
        f.write_str(match self {
29
            BinaryOp::Add => "+",
30
            BinaryOp::Sub => "-",
31
            BinaryOp::Mul => "*",
32
            BinaryOp::Div => "/",
33
            BinaryOp::Rem => "%",
34
            BinaryOp::Eq => "==",
35
            BinaryOp::NotEq => "!=",
36
            BinaryOp::Lt => "<",
37
            BinaryOp::LtEq => "<=",
38
            BinaryOp::Gt => ">",
39
            BinaryOp::GtEq => ">=",
40
        })
41
    }
42
}
43

44
/// Short-circuiting logical operators.
45
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
46
pub enum LogicalOp {
47
    And,
48
    Or,
49
}

1
error[E0369]: binary operation `>` cannot be applied to type `T`
2
 --> src/bin/ch05_bound.rs:2:10
3
  |
4
2 |     if a > b { a } else { b }
5
  |        - ^ - T
6
  |        |
7
  |        T
8
  |
9
help: consider restricting type parameter `T` with trait `PartialOrd`
10
  |
11
1 | fn largest<T: std::cmp::PartialOrd>(a: T, b: T) -> T {
12
  |             ++++++++++++++++++++++
13

14
For more information about this error, try `rustc --explain E0369`.
15
error: could not compile `rust-lab` (bin "ch05_bound") due to 1 previous error

1
error[E0277]: the size for values of type `Self` cannot be known at compilation time
2
 --> src/bin/ch05_sized.rs:9:19
3
  |
4
9 |         walk_expr(self, expr);
5
  |         --------- ^^^^ doesn't have a size known at compile-time
6
  |         |
7
  |         required by a bound introduced by this call
8
  |
9
note: required by an implicit `Sized` bound in `walk_expr`
10
 --> src/bin/ch05_sized.rs:3:14
11
  |
12
3 | fn walk_expr<V: Visit>(visitor: &mut V, expr: &Expr) {
13
  |              ^ required by the implicit `Sized` requirement on this type parameter in `walk_expr`
14
help: consider further restricting `Self`
15
  |
16
8 |     fn visit_expr(&mut self, expr: &Expr) where Self: Sized {
17
  |                                           +++++++++++++++++
18
help: consider relaxing the implicit `Sized` restriction
19
  |
20
3 | fn walk_expr<V: Visit + ?Sized>(visitor: &mut V, expr: &Expr) {
21
  |                       ++++++++
22

23
For more information about this error, try `rustc --explain E0277`.
24
error: could not compile `rust-lab` (bin "ch05_sized") due to 1 previous error

1
struct Expr;
2

3
fn walk_expr<V: Visit + ?Sized>(visitor: &mut V, expr: &Expr) {
4
    visitor.visit_expr(expr);
5
}
6

7
trait Visit {
8
    fn visit_expr(&mut self, _expr: &Expr) {}
9
}
10

11
struct Counter(usize);
12
impl Visit for Counter {
13
    fn visit_expr(&mut self, _expr: &Expr) {
14
        self.0 += 1;
15
    }
16
}
17

18
fn main() {
19
    let mut counter = Counter(0);
20
    walk_expr(&mut counter, &Expr);
21
    println!("static dispatch: {}", counter.0);
22

23
    let dynamic: &mut dyn Visit = &mut counter;
24
    walk_expr(dynamic, &Expr);
25
    println!("dynamic dispatch: {}", counter.0);
26
}

1
/// Recursively visits every statement of a program.
2
pub fn walk_program<V: Visit + ?Sized>(visitor: &mut V, program: &Program) {
3
    for stmt in program {
4
        visitor.visit_stmt(stmt);
5
    }
6
}
7

8
/// Recursively visits a statement and its children.
9
pub fn walk_stmt<V: Visit + ?Sized>(visitor: &mut V, stmt: &Stmt) {
10
    match stmt {
11
        Stmt::Let { value, .. } => visitor.visit_expr(value),
12
        Stmt::Fn { body, .. } => {
13
            for stmt in body {
14
                visitor.visit_stmt(stmt);
15
            }
16
        }
17
        Stmt::Expr { expr, .. } => visitor.visit_expr(expr),
18
        Stmt::If {
19
            cond,
20
            then_branch,
21
            else_branch,
22
            ..
23
        } => {
24
            visitor.visit_expr(cond);
25
            for stmt in then_branch {
26
                visitor.visit_stmt(stmt);
27
            }
28
            for stmt in else_branch {
29
                visitor.visit_stmt(stmt);
30
            }
31
        }
32
        Stmt::While { cond, body, .. } => {
33
            visitor.visit_expr(cond);
34
            for stmt in body {
35
                visitor.visit_stmt(stmt);
36
            }
37
        }
38
        Stmt::For { iter, body, .. } => {
39
            visitor.visit_expr(iter);
40
            for stmt in body {
41
                visitor.visit_stmt(stmt);
42
            }
43
        }
44
        Stmt::Return { value, .. } => {
45
            if let Some(value) = value {
46
                visitor.visit_expr(value);
47
            }
48
        }
49
        Stmt::Break { .. } | Stmt::Continue { .. } => {}
50
    }
51
}

1
/// Recursively visits an expression and its children.
2
pub fn walk_expr<V: Visit + ?Sized>(visitor: &mut V, expr: &Expr) {
3
    match expr {
4
        Expr::Nil { .. }
5
        | Expr::Bool { .. }
6
        | Expr::Int { .. }
7
        | Expr::Float { .. }
8
        | Expr::Str { .. }
9
        | Expr::Var { .. } => {}
10
        Expr::List { items, .. } => {
11
            for item in items {
12
                visitor.visit_expr(item);
13
            }
14
        }
15
        Expr::Map { entries, .. } => {
16
            for (key, value) in entries {
17
                visitor.visit_expr(key);
18
                visitor.visit_expr(value);
19
            }
20
        }
21
        Expr::Unary { operand, .. } => visitor.visit_expr(operand),
22
        Expr::Binary { lhs, rhs, .. } | Expr::Logical { lhs, rhs, .. } => {
23
            visitor.visit_expr(lhs);
24
            visitor.visit_expr(rhs);
25
        }
26
        Expr::Assign { target, value, .. } => {
27
            visitor.visit_expr(target);
28
            visitor.visit_expr(value);
29
        }
30
        Expr::Call { callee, args, .. } => {
31
            visitor.visit_expr(callee);
32
            for arg in args {
33
                visitor.visit_expr(arg);
34
            }
35
        }
36
        Expr::Index { object, index, .. } => {
37
            visitor.visit_expr(object);
38
            visitor.visit_expr(index);
39
        }
40
        Expr::Fn { body, .. } => {
41
            for stmt in body {
42
                visitor.visit_stmt(stmt);
43
            }
44
        }
45
    }
46
}