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, 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    /// <code>`Expr`</code>
142    Quote,
143    /// `loop Expr`
144    Loop,
145    /// `if Expr Expr (else Expr)?`
146    If,
147    /// `while Expr Expr (else Expr)?`
148    While,
149    /// `defer Expr`
150    Defer,
151    /// `break Expr`
152    Break,
153    /// `return Expr`
154    Return,
155    /// `continue`
156    Continue,
157
158    /// `Expr . Expr`
159    Dot,
160
161    /// `Expr? ..Expr`
162    RangeEx,
163    /// `Expr? ..=Expr`
164    RangeIn,
165    /// `-Expr`
166    Neg,
167    /// `!Expr`
168    Not,
169    /// `!!Expr`
170    Identity,
171    /// `&Expr`
172    Refer,
173    /// `*Expr`
174    Deref,
175
176    /// `Expr * Expr`
177    Mul,
178    /// `Expr / Expr`
179    Div,
180    /// `Expr % Expr`
181    Rem,
182
183    /// `Expr + Expr`
184    Add,
185    /// `Expr - Expr`
186    Sub,
187
188    /// `Expr << Expr`
189    Shl,
190    /// `Expr >> Expr`
191    Shr,
192
193    /// `Expr & Expr`
194    And,
195    /// `Expr ^ Expr`
196    Xor,
197    /// `Expr | Expr`
198    Or,
199
200    /// `Expr < Expr`
201    Lt,
202    /// `Expr <= Expr`
203    Leq,
204    /// `Expr == Expr`
205    Eq,
206    /// `Expr != Expr`
207    Neq,
208    /// `Expr >= Expr`
209    Geq,
210    /// `Expr > Expr`
211    Gt,
212
213    /// `Expr && Expr`
214    LogAnd,
215    /// `Expr ^^ Expr`
216    LogXor,
217    /// `Expr || Expr`
218    LogOr,
219
220    /// `Expr = Expr`
221    Set,
222    /// `Expr *= Expr`
223    MulSet,
224    /// `Expr /= Expr`
225    DivSet,
226    /// `Expr %= Expr`
227    RemSet,
228    /// `Expr += Expr`
229    AddSet,
230    /// `Expr -= Expr`
231    SubSet,
232    /// `Expr <<= Expr`
233    ShlSet,
234    /// `Expr >>= Expr`
235    ShrSet,
236    /// `Expr &= Expr`
237    AndSet,
238    /// `Expr ^= Expr`
239    XorSet,
240    /// `Expr |= Expr`
241    OrSet,
242}
243
244impl<A: AstTypes> Expr<A> {
245    /// Attaches this [Expr] to an [At] node with the provided [AstTypes::Annotation].
246    pub const fn at(self, annotation: A::Annotation) -> At<Expr<A>, A> {
247        At(self, annotation)
248    }
249
250    /// Attaches another expression to this one, continuing a [`do`](Op::Do) chain if possible.
251    pub fn and_do(self, annotation: A::Annotation, other: At<Expr<A>, A>) -> Self {
252        let Self::Op(Op::Do, mut exprs) = self else {
253            return Self::Op(Op::Do, vec![self.at(annotation), other]);
254        };
255        let At(Self::Op(Op::Do, mut other), _) = other else {
256            exprs.push(other);
257            return Self::Op(Op::Do, exprs);
258        };
259        exprs.append(&mut other);
260        Self::Op(Op::Do, exprs)
261    }
262
263    /// Removes omitted expressions from positions where expressions are allowed to be omitted.
264    pub fn deomit(self) -> Self {
265        let Self::Op(op @ (Op::Do | Op::Tuple | Op::Array), mut exprs) = self else {
266            return self;
267        };
268        exprs.retain(|expr| !matches!(expr.0, Self::Omitted));
269        Self::Op(op, exprs)
270    }
271
272    /// Turns this expression into a [`tuple`](Op::Tuple) if it isn't already one.
273    pub fn to_tuple(self, annotation: A::Annotation) -> Self {
274        match self {
275            Self::Op(Op::Tuple, _) => self,
276            _ => Self::Op(Op::Tuple, vec![self.at(annotation)]),
277        }
278    }
279
280    /// Returns whether `self` is a "place projection" expression (identifier, index, dot, or deref)
281    pub const fn is_place(&self) -> bool {
282        matches!(
283            self,
284            Self::Id(_) | Self::Op(Op::Index | Op::Dot | Op::Deref, _)
285        )
286    }
287
288    /// Returns whether `self` is NOT a "place projection" expression
289    pub const fn is_value(&self) -> bool {
290        !self.is_place()
291    }
292
293    /// If `self` is an [Expr::Op], returns the [Op] and a slice of its arguments.
294    #[allow(clippy::type_complexity)]
295    pub const fn as_slice(&self) -> Option<(Op, &[At<Expr<A>, A>])> {
296        match self {
297            Expr::Op(op, args) => Some((*op, args.as_slice())),
298            _ => None,
299        }
300    }
301}
302
303/// A pattern binding
304/// ```ignore
305/// let    Pat (= Expr (else Expr)?)?
306/// type   Pat (= Expr)?
307/// fn     Pat =? Expr
308/// mod    Pat =? Expr
309/// impl   Pat =? Expr
310/// struct Pat
311/// enum   Pat
312/// for    Pat in Expr Expr (else Expr)?
313/// ```
314#[derive(Clone, PartialEq, Eq, Hash)]
315pub struct Bind<A: AstTypes = DefaultTypes>(
316    pub BindOp,
317    pub Vec<A::Path>,
318    pub At<Pat<A>, A>,
319    pub Vec<At<Expr<A>, A>>,
320);
321
322/// The binding operation used by a [Bind].
323///
324/// See [Bind] for their syntactic representations
325#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
326pub enum BindOp {
327    /// A `let Pat (= Expr (else Expr)?)?` binding
328    Let,
329    /// A type-alias binding
330    Type,
331    /// A `fn Pat Expr` binding
332    Fn,
333    /// A `mod Pat Expr` binding
334    Mod,
335    /// An `impl Pat Expr` binding
336    Impl,
337    /// A struct definition
338    Struct,
339    /// An enum definition
340    Enum,
341    /// A `for Pat in Expr Expr (else Expr)?` binding
342    For,
343}
344
345/// Binding patterns for each kind of matchable value.
346///
347/// This covers both bindings and type annotations in [Bind] expressions.
348#[derive(Clone, PartialEq, Eq, Hash)]
349pub enum Pat<A: AstTypes = DefaultTypes> {
350    /// `_`: Matches anything without binding
351    Ignore,
352    /// `!`: Matches nothing, ever
353    Never,
354    /// `$Token`: Matches nothing; used for macro substitution
355    MetId(A::MacroId),
356    /// `Identifier`: Matches anything, and binds it to a name
357    Name(A::Symbol),
358    /// `Expr`: Matches a value by equality comparison
359    Value(Box<At<Expr<A>, A>>),
360    /// Matches a compound pattern
361    Op(PatOp, Vec<At<Pat<A>, A>>),
362}
363
364/// Operators on lists of patterns
365#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
366pub enum PatOp {
367    /// `#![ .* ] Pat`
368    MetaInner,
369    /// `#[ .* ] Pat`
370    MetaOuter,
371    /// Changes the visibility mode to "public"
372    Pub,
373    /// Changes the binding mode to "mutable"
374    Mut,
375    /// Matches the dereference of a pointer (`&pat`)
376    Ref,
377    /// Matches the dereference of a raw pointer (`*pat`)
378    Ptr,
379    /// Matches a partial decomposition (`..rest`) or upper-bounded range (`..100`)
380    Rest,
381    /// Matches an exclusive bounded range (`0..100`)
382    RangeEx,
383    /// Matches an inclusive bounded range (`0..=100`)
384    RangeIn,
385    /// Matches the elements of a record or struct { a, b, c }
386    Record,
387    /// Matches the elements of a tuple ( a, b, c )
388    Tuple,
389    /// Matches the elements of a slice or array [ a, b, c ]
390    Slice,
391    /// Matches a constant-size slice with repeating elements
392    ArRep,
393    /// Matches a type annotation or struct member
394    Typed,
395    /// Matches a prefix-type-annotated structure
396    TypePrefixed,
397    /// Matches a generic specialization annotation
398    Generic,
399    /// Changes the binding mode to "function-body"
400    Fn,
401    /// Matches a guard pattern (`Pat if Expr`)
402    Guard,
403    /// Matches one of a list of alternatives
404    Alt,
405}
406
407impl<A: AstTypes> Pat<A> {
408    /// Attaches this [Pat] to an [At] node with the provided [AstTypes::Annotation].
409    pub const fn at(self, annotation: A::Annotation) -> At<Pat<A>, A> {
410        At(self, annotation)
411    }
412    /// Turns this pattern into a [`tuple`](PatOp::Tuple) if it isn't already one.
413    pub fn to_tuple(self, annotation: A::Annotation) -> Self {
414        match self {
415            Self::Op(PatOp::Tuple, _) => self,
416            _ => Self::Op(PatOp::Tuple, vec![self.at(annotation)]),
417        }
418    }
419    /// Returns the single, unambiguous name bound by this pattern, if there is one.
420    ///
421    /// Else, returns [None].
422    pub fn name(&self) -> Option<A::Symbol> {
423        match self {
424            Self::Name(name) => Some(*name),
425            Self::Op(
426                PatOp::TypePrefixed
427                | PatOp::Typed
428                | PatOp::Pub
429                | PatOp::Mut
430                | PatOp::Generic
431                | PatOp::Guard,
432                pats,
433            ) if let [At(pat, _), ..] = &pats[..] => pat.name(),
434            _ => None,
435        }
436    }
437}
438
439/// A compound import declaration
440#[derive(Clone, Debug, PartialEq, Eq, Hash)]
441pub enum Use<A: AstTypes = DefaultTypes> {
442    /// "*"
443    Glob,
444    /// Identifier
445    Name(A::Symbol),
446    /// Identifier as Identifier
447    Alias(A::Symbol, A::Symbol),
448    /// Identifier :: Use
449    Path(A::Symbol, Box<Use<A>>),
450    /// { Use, * }
451    Tree(Vec<Use<A>>),
452}
453
454/// A make (constructor) expression
455/// ```ignore
456/// Expr { (Ident (: Expr)?),* }
457/// ```
458#[derive(Clone, Debug, PartialEq, Eq, Hash)]
459pub struct Make<A: AstTypes = DefaultTypes>(pub At<Expr<A>, A>, pub Vec<MakeArm<A>>);
460
461/// A single "arm" of a make expression
462/// ```text
463/// Identifier (':' Expr)?
464/// ```
465#[derive(Clone, Debug, PartialEq, Eq, Hash)]
466pub struct MakeArm<A: AstTypes = DefaultTypes>(pub A::Symbol, pub Option<At<Expr<A>, A>>);
467
468/// A match expression has a scrutinee and zero or more arms
469#[derive(Clone, Debug, PartialEq, Eq, Hash)]
470pub struct Match<A: AstTypes = DefaultTypes>(pub At<Expr<A>, A>, pub Vec<MatchArm<A>>);
471
472/// A single arm of a `match` expression
473/// ```text
474/// Pat => Expr
475/// ```
476#[derive(Clone, Debug, PartialEq, Eq, Hash)]
477pub struct MatchArm<A: AstTypes = DefaultTypes>(pub At<Pat<A>, A>, pub At<Expr<A>, A>);
cl_ast/ast.rs

cl_ast/
ast.rs
