june_lang/
ast.rs

1use crate::token::Op;
2use crate::types::{FnDef, LocalBinding, Resolution, Type, Typed};
3use std::fmt;
4
5// We have two AST variants: Typed and Untyped. To avoid defining the AST twice
6// and keeping them in sync, we add an extra field, `cargo`, that is defined
7// via generics. The Untyped AST carries Unit () as its cargo and the Typed AST
8// holds type information. Since each AST node might need different type info,
9// we define traits for each of the AST variants and specify the per-node cargo
10// type via associated objects, a pattern similar to C++ policy-based design.
11//
12// This is overkill. But it's a fun exercise :)
13//
14// More ideas:
15//
16// - http://lambda-the-ultimate.org/node/4170
17// - http://blog.ezyang.com/2013/05/the-ast-typing-problem/
18// - https://news.ycombinator.com/item?id=37114976
19// - https://www.reddit.com/r/ProgrammingLanguages/comments/b7fvlv/ast_and_tast/
20// - https://www.reddit.com/r/Compilers/comments/x3d3r6/type_information_in_the_ast/
21
22pub trait ASTSpec {
23    type CallCargo: fmt::Debug + PartialEq + Eq + Clone;
24    type IdentCargo: fmt::Debug + PartialEq + Eq + Clone;
25    type ExprCargo: fmt::Debug + PartialEq + Eq + Clone;
26    type ParamCargo: fmt::Debug + PartialEq + Eq + Clone;
27    type FuncCargo: fmt::Debug + PartialEq + Eq + Clone;
28    type LetCargo: fmt::Debug + PartialEq + Eq + Clone;
29    type BinaryCargo: fmt::Debug + PartialEq + Eq + Clone;
30    type ProgramCargo: fmt::Debug + PartialEq + Eq + Clone;
31}
32
33#[derive(Debug, PartialEq, Eq, Clone)]
34pub struct UntypedAST;
35
36impl ASTSpec for UntypedAST {
37    type CallCargo = ();
38    type IdentCargo = ();
39    type ExprCargo = ();
40    type ParamCargo = ();
41    type FuncCargo = ();
42    type LetCargo = ();
43    type BinaryCargo = ();
44    type ProgramCargo = ();
45}
46
47#[derive(Debug, PartialEq, Eq, Clone)]
48pub struct TypedAST;
49
50impl ASTSpec for TypedAST {
51    type CallCargo = Type;
52    type IdentCargo = Resolution;
53    type ExprCargo = Type;
54    type ParamCargo = Type;
55    type FuncCargo = FnDef;
56    type LetCargo = LocalBinding;
57    type BinaryCargo = Type;
58    type ProgramCargo = usize;
59}
60
61// =============================================================================
62// Call
63
64#[derive(Debug, PartialEq, Eq, Clone)]
65pub struct Call<AST: ASTSpec = UntypedAST> {
66    pub target: Box<Expr<AST>>,
67    pub args: Vec<Expr<AST>>,
68    pub resolved_type: AST::CallCargo,
69}
70
71impl Call {
72    pub fn untyped(target: Expr, args: Vec<Expr>) -> Call {
73        Call { target: Box::new(target), args, resolved_type: () }
74    }
75}
76
77pub type TypedCall = Call<TypedAST>;
78
79impl Typed for TypedCall {
80    fn typ(&self) -> Type {
81        self.resolved_type.clone()
82    }
83}
84
85// =============================================================================
86// Literal
87
88#[derive(Debug, PartialEq, Eq, Clone)]
89pub struct Literal<T: PartialEq + Eq + Clone> {
90    pub value: T,
91}
92
93pub type IntLiteral = Literal<i64>;
94pub type StrLiteral = Literal<String>;
95
96impl<T: fmt::Debug + PartialEq + Eq + Clone> Literal<T> {
97    pub fn new<U: Into<T>>(value: U) -> Literal<T> {
98        Literal { value: value.into() }
99    }
100}
101
102impl Typed for Literal<String> {
103    fn typ(&self) -> Type {
104        Type::Str
105    }
106}
107
108impl Typed for Literal<i64> {
109    fn typ(&self) -> Type {
110        Type::Int
111    }
112}
113
114// =============================================================================
115// Ident
116
117#[derive(Debug, PartialEq, Eq, Clone)]
118pub struct Ident<AST: ASTSpec = UntypedAST> {
119    pub name: String,
120    pub resolution: AST::IdentCargo,
121}
122
123impl Ident {
124    pub fn untyped<S: ToString>(name: S) -> Ident {
125        Ident { name: name.to_string(), resolution: () }
126    }
127}
128
129pub type TypedIdent = Ident<TypedAST>;
130
131impl Typed for TypedIdent {
132    fn typ(&self) -> Type {
133        self.resolution.typ.clone()
134    }
135}
136
137// =============================================================================
138// BinaryExpr
139
140#[derive(Debug, PartialEq, Eq, Clone, Copy)]
141pub enum BinaryOp {
142    Add,
143    Sub,
144    Mul,
145    Div,
146}
147
148impl From<Op> for BinaryOp {
149    fn from(value: Op) -> Self {
150        match value {
151            Op::Plus => BinaryOp::Add,
152            Op::Minus => BinaryOp::Sub,
153            Op::Star => BinaryOp::Mul,
154            Op::Slash => BinaryOp::Div,
155        }
156    }
157}
158
159#[derive(Debug, PartialEq, Eq, Clone)]
160pub struct Binary<AST: ASTSpec = UntypedAST> {
161    pub op: BinaryOp,
162    pub lhs: Box<Expr<AST>>,
163    pub rhs: Box<Expr<AST>>,
164    pub cargo: AST::BinaryCargo,
165}
166
167pub type TypedBinary = Binary<TypedAST>;
168
169impl Binary {
170    pub fn untyped(op: BinaryOp, lhs: Expr, rhs: Expr) -> Binary {
171        Binary { op, lhs: Box::new(lhs), rhs: Box::new(rhs), cargo: () }
172    }
173}
174
175impl Typed for Binary<TypedAST> {
176    fn typ(&self) -> Type {
177        self.cargo.clone()
178    }
179}
180
181// =============================================================================
182// Expr
183
184#[derive(Debug, PartialEq, Eq, Clone)]
185pub enum Expr<AST: ASTSpec = UntypedAST> {
186    Ident(Ident<AST>),
187    Str(StrLiteral),
188    Int(IntLiteral),
189    Call(Call<AST>),
190    Binary(Binary<AST>),
191}
192
193impl<AST: ASTSpec> Expr<AST> {
194    pub fn as_ident(self) -> Option<Ident<AST>> {
195        if let Self::Ident(ident) = self {
196            Some(ident)
197        } else {
198            None
199        }
200    }
201}
202
203pub type TypedExpr = Expr<TypedAST>;
204
205impl Typed for TypedExpr {
206    fn typ(&self) -> Type {
207        use Expr::*;
208        match self {
209            Ident(expr) => expr.typ(),
210            Str(expr) => expr.typ(),
211            Int(expr) => expr.typ(),
212            Call(expr) => expr.typ(),
213            Binary(expr) => expr.typ(),
214        }
215    }
216}
217
218// =============================================================================
219// TypeSpec
220
221#[derive(Debug, PartialEq, Eq, Clone)]
222pub enum TypeSpec {
223    Void,
224    Simple(String),
225}
226
227impl TypeSpec {
228    pub fn simple<S: ToString>(s: S) -> TypeSpec {
229        TypeSpec::Simple(s.to_string())
230    }
231}
232
233// =============================================================================
234// Param
235
236#[derive(Debug, PartialEq, Eq, Clone)]
237pub struct Param<AST: ASTSpec = UntypedAST> {
238    pub name: String,
239    pub typ: TypeSpec,
240    pub resolved_type: AST::ParamCargo,
241}
242
243impl Param {
244    pub fn untyped<S: ToString>(name: S, typ: TypeSpec) -> Param {
245        Param { name: name.to_string(), typ, resolved_type: () }
246    }
247}
248
249pub type TypedParam = Param<TypedAST>;
250
251impl Typed for TypedParam {
252    fn typ(&self) -> Type {
253        self.resolved_type.clone()
254    }
255}
256
257// =============================================================================
258// Binding
259
260#[derive(Debug, PartialEq, Eq, Clone)]
261pub struct Binding<AST: ASTSpec = UntypedAST> {
262    pub name: String,
263    pub typ: TypeSpec,
264    pub expr: Expr<AST>,
265    pub resolved_type: AST::LetCargo,
266}
267
268pub type TypedBinding = Binding<TypedAST>;
269
270impl<AST: ASTSpec> Binding<AST> {
271    pub fn new(
272        name: String,
273        typ: TypeSpec,
274        expr: Expr<AST>,
275        resolved_type: AST::LetCargo,
276    ) -> Binding<AST> {
277        Binding { name, typ, expr, resolved_type }
278    }
279}
280
281// =============================================================================
282// Stmt
283
284#[derive(Debug, PartialEq, Eq, Clone)]
285pub enum Stmt<AST: ASTSpec = UntypedAST> {
286    Expr(Expr<AST>),
287    Block(Block<AST>),
288    Let(Binding<AST>),
289}
290
291pub type TypedStmt = Stmt<TypedAST>;
292
293// =============================================================================
294// Block
295
296#[derive(Debug, PartialEq, Eq, Clone)]
297pub struct Block<AST: ASTSpec = UntypedAST>(pub Vec<Stmt<AST>>);
298
299pub type TypedBlock = Block<TypedAST>;
300
301// =============================================================================
302// Func
303
304#[derive(Debug, PartialEq, Eq, Clone)]
305pub struct Func<AST: ASTSpec = UntypedAST> {
306    pub name: String,
307    pub params: Vec<Param<AST>>,
308    pub body: Block<AST>,
309    pub ret: Option<TypeSpec>,
310    pub resolved_type: AST::FuncCargo,
311}
312
313impl Func {
314    pub fn untyped<S: ToString>(
315        name: S,
316        params: Vec<Param>,
317        body: Block,
318        ret: Option<TypeSpec>,
319    ) -> Func {
320        Func { name: name.to_string(), params, body, ret, resolved_type: () }
321    }
322}
323
324pub type TypedFunc = Func<TypedAST>;
325
326// =============================================================================
327// Def
328
329#[derive(Debug, PartialEq, Clone)]
330pub enum Def<AST: ASTSpec = UntypedAST> {
331    FnDef(Func<AST>),
332}
333
334pub type TypedDef = Def<TypedAST>;
335
336// =============================================================================
337// Program
338
339#[derive(Debug, PartialEq, Clone)]
340pub struct Program<AST: ASTSpec = UntypedAST> {
341    pub defs: Vec<Def<AST>>,
342    pub main_def: AST::ProgramCargo,
343}
344
345pub type TypedProgram = Program<TypedAST>;
june_lang/ast.rs

june_lang/
ast.rs
