cl_ast/
ast.rs

1//! The Abstract Syntax Tree defines an interface between the parser and type checker
2
3use std::hash::Hash;
4
5mod display;
6
7pub mod fold;
8pub mod macro_matcher;
9pub mod types;
10pub mod visit;
11
12pub use types::DefaultTypes;
13
14/// Common bounds on AST nodes
15pub trait AstNode: Clone + std::fmt::Display + std::fmt::Debug + PartialEq + Eq + Hash {}
16
17impl<T: Clone + std::fmt::Debug + std::fmt::Display + PartialEq + Eq + Hash> AstNode for T {}
18
19pub trait AstTypes: AstNode {
20    /// An annotation on an arbitrary [Expr] or [Pat]
21    type Annotation: AstNode + Copy;
22
23    /// A literal value
24    type Literal: AstNode;
25
26    /// A (possibly interned) symbol or index which implements [`AsRef<str>`]
27    type MacroId: AstNode + Hash + AsRef<str>;
28
29    /// A (possibly interned) symbol or index
30    type Symbol: AstNode + Copy + Hash;
31
32    /// A (possibly compound) symbol or index
33    type Path: AstNode;
34}
35
36/// A value with an annotation.
37#[derive(Clone, PartialEq, Eq, Hash)]
38pub struct At<T: AstNode, A: AstTypes = DefaultTypes>(pub T, pub A::Annotation);
39
40impl<T: AstNode, A: AstTypes> At<T, A> {
41    pub fn value(&self) -> &T {
42        &self.0
43    }
44    pub fn a(&self) -> &A::Annotation {
45        &self.1
46    }
47    pub fn map<U: AstNode>(self, f: impl FnOnce(T) -> U) -> At<U, A> {
48        At(f(self.0), self.1)
49    }
50    pub fn map_ref<U: AstNode>(&self, f: impl FnOnce(&T) -> U) -> At<U, A> {
51        At(f(&self.0), self.1)
52    }
53    pub fn map_a<B: AstTypes>(self, f: impl FnOnce(A::Annotation) -> B::Annotation) -> At<T, B> {
54        At(self.0, f(self.1))
55    }
56}
57
58/// Expressions: The beating heart of Conlang.
59///
60/// A program in Conlang is a single expression which, at compile time,
61/// sets up the state in which a program will run. This expression binds types,
62/// functions, and values to names which are exposed at runtime.
63///
64/// Whereas in the body of a function, `do` sequences are ordered, in the global
65/// scope (or subsequent module scopes, which are children of the global module,)
66/// `do` sequences are considered unordered, and subexpressions may be reordered
67/// in whichever way the compiler sees fit. This is especially important when
68/// performing import resolution, as imports typically depend on the order
69/// in which names are bound.
70#[derive(Clone, Debug, PartialEq, Eq, Hash)]
71pub enum Expr<A: AstTypes = DefaultTypes> {
72    /// Omitted by semicolon insertion-elision rules
73    Omitted,
74    /// An identifier
75    Id(A::Path),
76    /// An escaped token for macro binding
77    MetId(A::MacroId),
78    /// A literal bool, string, char, or int
79    Lit(A::Literal),
80    /// use Use
81    Use(Use<A>),
82    /// `let Pat::NoTopAlt (= expr (else expr)?)?` |
83    /// `(fn | mod | impl) Pat::Fn Expr`
84    Bind(Box<Bind<A>>),
85    /// Expr { (Ident (: Expr)?),* }
86    Make(Box<Make<A>>),
87    /// `match Expr { (Pat => Expr),* }`
88    Match(Box<Match<A>>),
89    /// Op Expr | Expr Op | Expr (Op Expr)+ | Op Expr Expr else Expr
90    Op(Op, Vec<At<Self, A>>),
91}
92
93/// Conlang's AST is partitioned by data representation, so it
94/// considers any expression which is composed solely of keywords,
95/// symbols, and other expressions as operator expressions.
96///
97/// This includes:
98/// - Do-sequence expressions: `Expr ; Expr `
99/// - Type-cast expressions `Expr as Expr`
100/// - Binding-modifier expressions: `pub Expr`, `#[Expr] Expr`
101/// - Block and Group expressions: `{Expr?}`, `(Expr?)`
102/// - Control flow: `if`, `while`, `loop`, `match`, `break`, `return`
103/// - Function calls `Expr (Expr,*)`
104/// - Traditional binary and unary operators (add, sub, neg, assign)
105#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
106pub enum Op {
107    /// `Expr (; Expr)*`
108    Do,
109    /// `Expr as Expr`
110    As,
111    /// `{ Expr }`
112    Block,
113    /// `[ Expr,* ]`
114    Array,
115    /// `[ Expr ; Expr ]`
116    ArRep,
117    /// `( Expr )`
118    Group,
119    /// `Expr (, Expr)*`
120    Tuple,
121    /// `#![ Expr ]`
122    MetaInner,
123    /// `#[ Expr ]`
124    MetaOuter,
125
126    /// `Expr '?'`
127    Try,
128    /// `Expr [ Expr ]`
129    Index,
130    /// `Expr ( Expr )`
131    Call,
132
133    /// `pub Expr`
134    Pub,
135    /// `const Expr`
136    Const,
137    /// `static Expr`
138    Static,
139    /// `macro Expr`
140    Macro,
141    /// `loop Expr`
142    Loop,
143    /// `if Expr Expr (else Expr)?`
144    If,
145    /// `while Expr Expr (else Expr)?`
146    While,
147    /// `defer Expr`
148    Defer,
149    /// `break Expr`
150    Break,
151    /// `return Expr`
152    Return,
153    /// `continue`
154    Continue,
155
156    /// `Expr . Expr`
157    Dot,
158
159    /// `Expr? ..Expr`
160    RangeEx,
161    /// `Expr? ..=Expr`
162    RangeIn,
163    /// `-Expr`
164    Neg,
165    /// `!Expr`
166    Not,
167    /// `!!Expr`
168    Identity,
169    /// `&Expr`
170    Refer,
171    /// `*Expr`
172    Deref,
173
174    /// `Expr * Expr`
175    Mul,
176    /// `Expr / Expr`
177    Div,
178    /// `Expr % Expr`
179    Rem,
180
181    /// `Expr + Expr`
182    Add,
183    /// `Expr - Expr`
184    Sub,
185
186    /// `Expr << Expr`
187    Shl,
188    /// `Expr >> Expr`
189    Shr,
190
191    /// `Expr & Expr`
192    And,
193    /// `Expr ^ Expr`
194    Xor,
195    /// `Expr | Expr`
196    Or,
197
198    /// `Expr < Expr`
199    Lt,
200    /// `Expr <= Expr`
201    Leq,
202    /// `Expr == Expr`
203    Eq,
204    /// `Expr != Expr`
205    Neq,
206    /// `Expr >= Expr`
207    Geq,
208    /// `Expr > Expr`
209    Gt,
210
211    /// `Expr && Expr`
212    LogAnd,
213    /// `Expr ^^ Expr`
214    LogXor,
215    /// `Expr || Expr`
216    LogOr,
217
218    /// `Expr = Expr`
219    Set,
220    /// `Expr *= Expr`
221    MulSet,
222    /// `Expr /= Expr`
223    DivSet,
224    /// `Expr %= Expr`
225    RemSet,
226    /// `Expr += Expr`
227    AddSet,
228    /// `Expr -= Expr`
229    SubSet,
230    /// `Expr <<= Expr`
231    ShlSet,
232    /// `Expr >>= Expr`
233    ShrSet,
234    /// `Expr &= Expr`
235    AndSet,
236    /// `Expr ^= Expr`
237    XorSet,
238    /// `Expr |= Expr`
239    OrSet,
240}
241
242impl<A: AstTypes> Expr<A> {
243    /// Attaches this [Expr] to an [At] node with the provided [AstTypes::Annotation].
244    pub const fn at(self, annotation: A::Annotation) -> At<Expr<A>, A> {
245        At(self, annotation)
246    }
247
248    /// Attaches another expression to this one, continuing a [`do`](Op::Do) chain if possible.
249    pub fn and_do(self, annotation: A::Annotation, other: At<Expr<A>, A>) -> Self {
250        let Self::Op(Op::Do, mut exprs) = self else {
251            return Self::Op(Op::Do, vec![self.at(annotation), other]);
252        };
253        let At(Self::Op(Op::Do, mut other), _) = other else {
254            exprs.push(other);
255            return Self::Op(Op::Do, exprs);
256        };
257        exprs.append(&mut other);
258        Self::Op(Op::Do, exprs)
259    }
260
261    /// Removes omitted expressions from positions where expressions are allowed to be omitted.
262    pub fn deomit(self) -> Self {
263        let Self::Op(op @ (Op::Do | Op::Tuple | Op::Array), mut exprs) = self else {
264            return self;
265        };
266        exprs.retain(|expr| !matches!(expr.0, Self::Omitted));
267        Self::Op(op, exprs)
268    }
269
270    /// Turns this expression into a [`tuple`](Op::Tuple) if it isn't already one.
271    pub fn to_tuple(self, annotation: A::Annotation) -> Self {
272        match self {
273            Self::Op(Op::Tuple, _) => self,
274            _ => Self::Op(Op::Tuple, vec![self.at(annotation)]),
275        }
276    }
277
278    /// Returns whether `self` is a "place projection" expression (identifier, index, dot, or deref)
279    pub const fn is_place(&self) -> bool {
280        matches!(
281            self,
282            Self::Id(_) | Self::Op(Op::Index | Op::Dot | Op::Deref, _)
283        )
284    }
285
286    /// Returns whether `self` is NOT a "place projection" expression
287    pub const fn is_value(&self) -> bool {
288        !self.is_place()
289    }
290
291    /// If `self` is an [Expr::Op], returns the [Op] and a slice of its arguments.
292    #[allow(clippy::type_complexity)]
293    pub const fn as_slice(&self) -> Option<(Op, &[At<Expr<A>, A>])> {
294        match self {
295            Expr::Op(op, args) => Some((*op, args.as_slice())),
296            _ => None,
297        }
298    }
299}
300
301/// A pattern binding
302/// ```ignore
303/// let    Pat (= Expr (else Expr)?)?
304/// type   Pat (= Expr)?
305/// fn     Pat =? Expr
306/// mod    Pat =? Expr
307/// impl   Pat =? Expr
308/// struct Pat
309/// enum   Pat
310/// for    Pat in Expr Expr (else Expr)?
311/// ```
312#[derive(Clone, Debug, PartialEq, Eq, Hash)]
313pub struct Bind<A: AstTypes = DefaultTypes>(
314    pub BindOp,
315    pub Vec<A::Path>,
316    pub At<Pat<A>, A>,
317    pub Vec<At<Expr<A>, A>>,
318);
319
320/// The binding operation used by a [Bind].
321///
322/// See [Bind] for their syntactic representations
323#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
324pub enum BindOp {
325    /// A `let Pat (= Expr (else Expr)?)?` binding
326    Let,
327    /// A type-alias binding
328    Type,
329    /// A `fn Pat Expr` binding
330    Fn,
331    /// A `mod Pat Expr` binding
332    Mod,
333    /// An `impl Pat Expr` binding
334    Impl,
335    /// A struct definition
336    Struct,
337    /// An enum definition
338    Enum,
339    /// A `for Pat in Expr Expr (else Expr)?` binding
340    For,
341}
342
343/// Binding patterns for each kind of matchable value.
344///
345/// This covers both bindings and type annotations in [Bind] expressions.
346#[derive(Clone, Debug, PartialEq, Eq, Hash)]
347pub enum Pat<A: AstTypes = DefaultTypes> {
348    /// `_`: Matches anything without binding
349    Ignore,
350    /// `!`: Matches nothing, ever
351    Never,
352    /// `$Token`: Matches nothing; used for macro substitution
353    MetId(A::MacroId),
354    /// `Identifier`: Matches anything, and binds it to a name
355    Name(A::Symbol),
356    /// `Expr`: Matches a value by equality comparison
357    Value(Box<At<Expr<A>, A>>),
358    /// Matches a compound pattern
359    Op(PatOp, Vec<At<Pat<A>, A>>),
360}
361
362/// Operators on lists of patterns
363#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
364pub enum PatOp {
365    /// `#![ .* ] Pat`
366    MetaInner,
367    /// `#[ .* ] Pat`
368    MetaOuter,
369    /// Changes the visibility mode to "public"
370    Pub,
371    /// Changes the binding mode to "mutable"
372    Mut,
373    /// Matches the dereference of a pointer (`&pat`)
374    Ref,
375    /// Matches the dereference of a raw pointer (`*pat`)
376    Ptr,
377    /// Matches a partial decomposition (`..rest`) or upper-bounded range (`..100`)
378    Rest,
379    /// Matches an exclusive bounded range (`0..100`)
380    RangeEx,
381    /// Matches an inclusive bounded range (`0..=100`)
382    RangeIn,
383    /// Matches the elements of a record or struct { a, b, c }
384    Record,
385    /// Matches the elements of a tuple ( a, b, c )
386    Tuple,
387    /// Matches the elements of a slice or array [ a, b, c ]
388    Slice,
389    /// Matches a constant-size slice with repeating elements
390    ArRep,
391    /// Matches a type annotation or struct member
392    Typed,
393    /// Matches a prefix-type-annotated structure
394    TypePrefixed,
395    /// Matches a generic specialization annotation
396    Generic,
397    /// Changes the binding mode to "function-body"
398    Fn,
399    /// Matches a guard pattern (`Pat if Expr`)
400    Guard,
401    /// Matches one of a list of alternatives
402    Alt,
403}
404
405impl<A: AstTypes> Pat<A> {
406    /// Attaches this [Pat] to an [At] node with the provided [AstTypes::Annotation].
407    pub const fn at(self, annotation: A::Annotation) -> At<Pat<A>, A> {
408        At(self, annotation)
409    }
410    /// Turns this pattern into a [`tuple`](PatOp::Tuple) if it isn't already one.
411    pub fn to_tuple(self, annotation: A::Annotation) -> Self {
412        match self {
413            Self::Op(PatOp::Tuple, _) => self,
414            _ => Self::Op(PatOp::Tuple, vec![self.at(annotation)]),
415        }
416    }
417    /// Returns the single, unambiguous name bound by this pattern, if there is one.
418    ///
419    /// Else, returns [None].
420    pub fn name(&self) -> Option<A::Symbol> {
421        match self {
422            Self::Name(name) => Some(*name),
423            Self::Op(
424                PatOp::TypePrefixed
425                | PatOp::Typed
426                | PatOp::Pub
427                | PatOp::Mut
428                | PatOp::Generic
429                | PatOp::Guard,
430                pats,
431            ) if let [At(pat, _), ..] = &pats[..] => pat.name(),
432            _ => None,
433        }
434    }
435}
436
437/// A compound import declaration
438#[derive(Clone, Debug, PartialEq, Eq, Hash)]
439pub enum Use<A: AstTypes = DefaultTypes> {
440    /// "*"
441    Glob,
442    /// Identifier
443    Name(A::Symbol),
444    /// Identifier as Identifier
445    Alias(A::Symbol, A::Symbol),
446    /// Identifier :: Use
447    Path(A::Symbol, Box<Use<A>>),
448    /// { Use, * }
449    Tree(Vec<Use<A>>),
450}
451
452/// A make (constructor) expression
453/// ```ignore
454/// Expr { (Ident (: Expr)?),* }
455/// ```
456#[derive(Clone, Debug, PartialEq, Eq, Hash)]
457pub struct Make<A: AstTypes = DefaultTypes>(pub At<Expr<A>, A>, pub Vec<MakeArm<A>>);
458
459/// A single "arm" of a make expression
460/// ```text
461/// Identifier (':' Expr)?
462/// ```
463#[derive(Clone, Debug, PartialEq, Eq, Hash)]
464pub struct MakeArm<A: AstTypes = DefaultTypes>(pub A::Symbol, pub Option<At<Expr<A>, A>>);
465
466/// A match expression has a scrutinee and zero or more arms
467#[derive(Clone, Debug, PartialEq, Eq, Hash)]
468pub struct Match<A: AstTypes = DefaultTypes>(pub At<Expr<A>, A>, pub Vec<MatchArm<A>>);
469
470/// A single arm of a `match` expression
471/// ```text
472/// Pat => Expr
473/// ```
474#[derive(Clone, Debug, PartialEq, Eq, Hash)]
475pub struct MatchArm<A: AstTypes = DefaultTypes>(pub At<Pat<A>, A>, pub At<Expr<A>, A>);
cl_ast/ast.rs

cl_ast/
ast.rs
