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

cl_ast/
ast.rs
