Skip to main content

lower_lang/
template.rs

1//! Lowering templates: small HIR-shaped ASTs with `${field}` holes.
2//!
3//! A template is what LexerSketch's `[semantics.lower]` section writes as
4//! quasi-quoted HIR (`while = "loop { if ${cond} {} else { break }; ${body} }"`).
5//! In 0.2 templates are built programmatically with a [`TemplateBuilder`];
6//! the textual form arrives with hir-lang's textual syntax (0.5) as a pure
7//! front end that produces the same [`Template`] values.
8//!
9//! Every instantiation records its own HIR expansion. Binders and labels a
10//! template introduces are created fresh per instantiation, carry that
11//! expansion's hygiene mark, and are referenced by binder id, so they can
12//! neither capture nor be captured by user names. Free names the template
13//! writes ([`global`](TemplateBuilder::global)) carry the mark too and are
14//! resolved at the template's definition site; [`extern_`](TemplateBuilder::extern_)
15//! names a host symbol directly.
16
17use alloc::boxed::Box;
18use alloc::vec::Vec;
19use core::fmt;
20
21use hir_lang::{CaptureMode, ExpnKind, Op, OpKind, Prim};
22
23/// Marks an absent optional child in the node arena.
24pub(crate) const NONE: u32 = u32::MAX;
25
26/// The most nodes a template's tree may have once shared sub-trees are
27/// counted at every use; larger templates are refused by
28/// [`TemplateBuilder::finish`].
29pub const MAX_TEMPLATE_SIZE: u32 = 1 << 20;
30
31/// A template registered in a mapping, from
32/// [`MappingBuilder::template`](crate::MappingBuilder::template).
33///
34/// # Examples
35///
36/// ```
37/// use lower_lang::{templates, MappingBuilder};
38///
39/// let mut b = MappingBuilder::<u8>::new();
40/// let first = b.template(templates::while_loop())?;
41/// let second = b.template(templates::do_while())?;
42/// assert_eq!((first.index(), second.index()), (0, 1));
43/// # Ok::<(), lower_lang::MappingError>(())
44/// ```
45#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
46pub struct TemplateId(pub(crate) u32);
47
48impl TemplateId {
49    /// The registration position of the template in its mapping.
50    ///
51    /// # Examples
52    ///
53    /// ```
54    /// use lower_lang::{templates, MappingBuilder};
55    ///
56    /// let mut b = MappingBuilder::<u8>::new();
57    /// assert_eq!(b.template(templates::logical_or())?.index(), 0);
58    /// # Ok::<(), lower_lang::MappingError>(())
59    /// ```
60    #[must_use]
61    pub const fn index(self) -> usize {
62        self.0 as usize
63    }
64}
65
66/// What a hole is filled with, and where it may be used.
67///
68/// # Examples
69///
70/// ```
71/// use lower_lang::{HoleKind, TemplateBuilder};
72///
73/// let mut t = TemplateBuilder::new("id");
74/// let x = t.expr_hole("x");
75/// let root = t.hole(x);
76/// let template = t.finish(root)?;
77/// assert_eq!(template.hole(0), Some(("x", HoleKind::Expr, false)));
78/// # Ok::<(), lower_lang::TemplateError>(())
79/// ```
80#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
81pub enum HoleKind {
82    /// One expression.
83    Expr,
84    /// One pattern (its names bind as locals).
85    Pat,
86    /// One type.
87    Ty,
88    /// Zero or more statements, spliced into a block.
89    Stmts,
90    /// Zero or more call arguments, spliced into an argument or element list.
91    Args,
92    /// The user's label for a loop or block the template creates.
93    Label,
94}
95
96/// A literal a template writes (strings are written with
97/// [`TemplateBuilder::str`]).
98///
99/// # Examples
100///
101/// ```
102/// use lower_lang::TLit;
103///
104/// assert_ne!(TLit::Int(1), TLit::Bool(true));
105/// ```
106#[derive(Clone, Copy, Debug, PartialEq)]
107pub enum TLit {
108    /// An integer.
109    Int(i64),
110    /// A float.
111    Float(f64),
112    /// `true` / `false`.
113    Bool(bool),
114    /// `null`.
115    Null,
116    /// A character.
117    Char(char),
118}
119
120macro_rules! handle {
121    ($(#[$m:meta])* $name:ident, $int:ty) => {
122        $(#[$m])*
123        #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
124        pub struct $name(pub(crate) $int);
125    };
126}
127
128handle!(
129    /// An expression node of a template under construction.
130    TExpr,
131    u32
132);
133handle!(
134    /// A pattern node of a template under construction.
135    TPat,
136    u32
137);
138handle!(
139    /// A type node of a template under construction.
140    TTy,
141    u32
142);
143handle!(
144    /// A statement node of a template under construction.
145    TStmt,
146    u32
147);
148handle!(
149    /// A binder the template introduces (fresh and hygienic per instantiation).
150    TBinder,
151    u16
152);
153handle!(
154    /// A loop or block label the template introduces.
155    TLabel,
156    u16
157);
158handle!(
159    /// An expression hole.
160    ExprHole,
161    u16
162);
163handle!(
164    /// A pattern hole.
165    PatHole,
166    u16
167);
168handle!(
169    /// A type hole.
170    TyHole,
171    u16
172);
173handle!(
174    /// A statement-list hole.
175    StmtsHole,
176    u16
177);
178handle!(
179    /// An argument-list hole.
180    ArgsHole,
181    u16
182);
183handle!(
184    /// A label hole.
185    LabelHole,
186    u16
187);
188
189/// The label of a loop or block a template creates, or a jump's target.
190///
191/// # Examples
192///
193/// ```
194/// use lower_lang::{LabelRef, TemplateBuilder};
195///
196/// let mut t = TemplateBuilder::new("forever");
197/// let user = t.label_hole("label");
198/// let brk = t.break_(Some(LabelRef::Hole(user)), None);
199/// let body = t.block(&[], Some(brk));
200/// let root = t.loop_(Some(LabelRef::Hole(user)), body, None);
201/// assert!(t.finish(root).is_ok());
202/// ```
203#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
204pub enum LabelRef {
205    /// A label the template defines.
206    Own(TLabel),
207    /// The user's label, from a label hole.
208    Hole(LabelHole),
209}
210
211/// An argument of [`TemplateBuilder::apply`]: what fills one hole of the
212/// applied template, in its hole order.
213///
214/// # Examples
215///
216/// ```
217/// use lower_lang::TArg;
218///
219/// assert_eq!(TArg::Absent, TArg::Absent);
220/// ```
221#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
222pub enum TArg {
223    /// An expression for an expression hole.
224    Expr(TExpr),
225    /// A pattern for a pattern hole.
226    Pat(TPat),
227    /// A type for a type hole.
228    Ty(TTy),
229    /// This template's statement-list hole, forwarded.
230    Stmts(StmtsHole),
231    /// This template's argument-list hole, forwarded.
232    Args(ArgsHole),
233    /// A label for a label hole.
234    Label(LabelRef),
235    /// Nothing, for an optional hole.
236    Absent,
237}
238
239impl TArg {
240    pub(crate) const fn kind(self) -> Option<HoleKind> {
241        match self {
242            Self::Expr(_) => Some(HoleKind::Expr),
243            Self::Pat(_) => Some(HoleKind::Pat),
244            Self::Ty(_) => Some(HoleKind::Ty),
245            Self::Stmts(_) => Some(HoleKind::Stmts),
246            Self::Args(_) => Some(HoleKind::Args),
247            Self::Label(_) => Some(HoleKind::Label),
248            Self::Absent => None,
249        }
250    }
251}
252
253/// A label slot in the node arena.
254#[derive(Clone, Copy, Debug, PartialEq)]
255pub(crate) enum LabelSlot {
256    None,
257    Own(u16),
258    Hole(u16),
259}
260
261impl LabelSlot {
262    fn of(label: Option<LabelRef>) -> Self {
263        match label {
264            None => Self::None,
265            Some(LabelRef::Own(l)) => Self::Own(l.0),
266            Some(LabelRef::Hole(h)) => Self::Hole(h.0),
267        }
268    }
269}
270
271/// A list in the template's pool: `(start, len)`.
272pub(crate) type TList = (u32, u32);
273
274/// One template node. Children are indexes into the node arena.
275#[derive(Clone, Copy, Debug, PartialEq)]
276pub(crate) enum TNode {
277    // ---- expressions
278    Hole(u16),
279    Splice(u16),
280    Lit(TLit),
281    Str(u32),
282    Var(u16),
283    Global(u32),
284    Extern(u32),
285    Call {
286        callee: u32,
287        args: TList,
288    },
289    Method {
290        recv: u32,
291        name: u32,
292        args: TList,
293    },
294    Field {
295        base: u32,
296        name: u32,
297    },
298    Index {
299        base: u32,
300        index: u32,
301    },
302    Op {
303        op: Op,
304        exact: bool,
305        args: TList,
306    },
307    Assign {
308        target: u32,
309        value: u32,
310    },
311    Block {
312        stmts: TList,
313        tail: u32,
314        label: LabelSlot,
315    },
316    If {
317        cond: u32,
318        then: u32,
319        else_: u32,
320    },
321    Match {
322        scrutinee: u32,
323        arms: TList,
324    },
325    Loop {
326        label: LabelSlot,
327        body: u32,
328        step: u32,
329    },
330    Break {
331        label: LabelSlot,
332        value: u32,
333    },
334    Continue {
335        label: LabelSlot,
336    },
337    Return(u32),
338    Throw(u32),
339    Await(u32),
340    Yield(u32),
341    Spawn(u32),
342    Tuple(TList),
343    Array(TList),
344    Closure {
345        params: TList,
346        body: u32,
347        implicit: Option<CaptureMode>,
348    },
349    Apply {
350        template: u32,
351        args: TList,
352    },
353    // ---- statements
354    Let {
355        pat: u32,
356        ty: u32,
357        init: u32,
358    },
359    ExprStmt(u32),
360    Defer(u32),
361    Stmts(u16),
362    // ---- patterns
363    PHole(u16),
364    PWild,
365    PBind(u16),
366    PLit(TLit),
367    PTuple(TList),
368    PCtor {
369        path: u32,
370        elems: TList,
371    },
372    // ---- types
373    THole(u16),
374    TPrim(Prim),
375    TNamed(u32),
376    TInfer,
377    TAny,
378}
379
380/// A declared hole.
381#[derive(Clone, Debug, PartialEq)]
382pub(crate) struct HoleDecl {
383    pub(crate) name: Box<str>,
384    pub(crate) kind: HoleKind,
385    pub(crate) optional: bool,
386    pub(crate) default: Option<TLit>,
387}
388
389/// A declared binder or label.
390#[derive(Clone, Copy, Debug, PartialEq, Eq)]
391pub(crate) struct BinderDecl {
392    pub(crate) name: u32,
393    pub(crate) mutable: bool,
394}
395
396/// A finished, checked lowering template.
397///
398/// Register it in a mapping with
399/// [`MappingBuilder::template`](crate::MappingBuilder::template), then use it
400/// for a node kind ([`template_node`](crate::MappingBuilder::template_node))
401/// or an operator ([`OpSpec::Template`](crate::OpSpec::Template)).
402///
403/// # Examples
404///
405/// ```
406/// use lower_lang::templates;
407///
408/// let t = templates::while_loop();
409/// assert_eq!(t.name(), "while");
410/// assert_eq!(t.hole_count(), 3);
411/// ```
412#[derive(Clone, Debug, PartialEq)]
413pub struct Template {
414    pub(crate) name: Box<str>,
415    pub(crate) kind: ExpnKind,
416    pub(crate) nodes: Vec<TNode>,
417    pub(crate) lists: Vec<u32>,
418    pub(crate) texts: Vec<Box<str>>,
419    pub(crate) holes: Vec<HoleDecl>,
420    pub(crate) binders: Vec<BinderDecl>,
421    pub(crate) labels: Vec<BinderDecl>,
422    pub(crate) args: Vec<TArg>,
423    pub(crate) applies: Vec<u32>,
424    pub(crate) root: u32,
425    /// Set when registered: where this template's texts start in the
426    /// mapping's string table.
427    pub(crate) text_base: u32,
428}
429
430impl Template {
431    /// The template's name (also the expansion's name in HIR origins).
432    ///
433    /// # Examples
434    ///
435    /// ```
436    /// assert_eq!(lower_lang::templates::do_while().name(), "do-while");
437    /// ```
438    #[must_use]
439    pub fn name(&self) -> &str {
440        &self.name
441    }
442
443    /// The expansion kind instantiations record (`Template` by default,
444    /// `Desugar` for the built-in desugarings).
445    ///
446    /// # Examples
447    ///
448    /// ```
449    /// use hir_lang::ExpnKind;
450    ///
451    /// assert_eq!(lower_lang::templates::while_loop().expansion_kind(), ExpnKind::Desugar);
452    /// ```
453    #[must_use]
454    pub const fn expansion_kind(&self) -> ExpnKind {
455        self.kind
456    }
457
458    /// The number of holes; a node that uses the template binds one pick per
459    /// hole, in this order.
460    ///
461    /// # Examples
462    ///
463    /// ```
464    /// assert_eq!(lower_lang::templates::c_for().hole_count(), 5);
465    /// ```
466    #[must_use]
467    pub fn hole_count(&self) -> usize {
468        self.holes.len()
469    }
470
471    /// Hole `index`: its name, kind, and whether it may be absent.
472    ///
473    /// # Examples
474    ///
475    /// ```
476    /// use lower_lang::HoleKind;
477    ///
478    /// let t = lower_lang::templates::while_loop();
479    /// assert_eq!(t.hole(0), Some(("cond", HoleKind::Expr, false)));
480    /// assert_eq!(t.hole(2), Some(("label", HoleKind::Label, true)));
481    /// assert_eq!(t.hole(3), None);
482    /// ```
483    #[must_use]
484    pub fn hole(&self, index: usize) -> Option<(&str, HoleKind, bool)> {
485        self.holes
486            .get(index)
487            .map(|h| (&*h.name, h.kind, h.optional))
488    }
489
490    pub(crate) fn node(&self, index: u32) -> Option<&TNode> {
491        self.nodes.get(index as usize)
492    }
493
494    pub(crate) fn list(&self, list: TList) -> &[u32] {
495        let (start, len) = (list.0 as usize, list.1 as usize);
496        self.lists
497            .get(start..start.saturating_add(len))
498            .unwrap_or(&[])
499    }
500}
501
502/// Why a template was refused.
503///
504/// # Examples
505///
506/// ```
507/// use lower_lang::{TemplateBuilder, TemplateError};
508///
509/// let mut t = TemplateBuilder::new("unused");
510/// let _x = t.expr_hole("x");
511/// let root = t.lit(lower_lang::TLit::Null);
512/// assert_eq!(t.finish(root), Err(TemplateError::HoleUnused { hole: 0 }));
513/// ```
514#[derive(Clone, Copy, Debug, PartialEq, Eq)]
515#[non_exhaustive]
516pub enum TemplateError {
517    /// A declared hole is never used. Use it, or remove it (every hole must
518    /// receive its user code somewhere, or that code would be lost).
519    HoleUnused {
520        /// The hole's index.
521        hole: usize,
522    },
523    /// A binder is used but no pattern or closure parameter binds it.
524    BinderUnbound {
525        /// The binder's index.
526        binder: usize,
527    },
528    /// A binder is bound by two patterns or parameters. Declare one binder
529    /// per binding site.
530    BinderBoundTwice {
531        /// The binder's index.
532        binder: usize,
533    },
534    /// A label is jumped to but no loop or block defines it.
535    LabelUndefined {
536        /// The label's index.
537        label: usize,
538    },
539    /// A label is defined by two loops or blocks.
540    LabelDefinedTwice {
541        /// The label's index.
542        label: usize,
543    },
544    /// An argument-list hole is spliced somewhere other than a call's
545    /// arguments or a tuple's or array's elements.
546    SpliceOutOfList {
547        /// The hole's index.
548        hole: usize,
549    },
550    /// A handle from another template builder (or a list longer than the
551    /// arena) was used.
552    ForeignHandle,
553    /// The tree, counting shared sub-trees at every use, has more than
554    /// [`MAX_TEMPLATE_SIZE`] nodes, or a table outgrew its index type.
555    TooLarge,
556}
557
558impl fmt::Display for TemplateError {
559    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
560        match self {
561            Self::HoleUnused { hole } => write!(f, "hole {hole} is never used"),
562            Self::BinderUnbound { binder } => write!(f, "binder {binder} is used but never bound"),
563            Self::BinderBoundTwice { binder } => write!(f, "binder {binder} is bound twice"),
564            Self::LabelUndefined { label } => write!(f, "label {label} is used but never defined"),
565            Self::LabelDefinedTwice { label } => write!(f, "label {label} is defined twice"),
566            Self::SpliceOutOfList { hole } => {
567                write!(
568                    f,
569                    "argument hole {hole} is spliced outside an argument or element list"
570                )
571            }
572            Self::ForeignHandle => f.write_str("a handle from another template builder was used"),
573            Self::TooLarge => f.write_str("the template is too large"),
574        }
575    }
576}
577
578impl core::error::Error for TemplateError {}
579
580/// Builds a [`Template`] bottom-up, like hir-lang's `Builder` builds HIR.
581///
582/// Declare holes and binders, build nodes, then [`finish`](Self::finish) with
583/// the root expression. Every method is infallible; problems (a foreign
584/// handle, an unbound binder, an unused hole) are reported by `finish`.
585///
586/// # Examples
587///
588/// `unless cond { body }` as `if cond {} else { body }`:
589///
590/// ```
591/// use lower_lang::TemplateBuilder;
592///
593/// let mut t = TemplateBuilder::new("unless");
594/// let cond = t.expr_hole("cond");
595/// let body = t.expr_hole("body");
596/// let c = t.hole(cond);
597/// let empty = t.block(&[], None);
598/// let b = t.hole(body);
599/// let root = t.if_(c, empty, Some(b));
600/// let unless = t.finish(root)?;
601/// assert_eq!(unless.hole_count(), 2);
602/// # Ok::<(), lower_lang::TemplateError>(())
603/// ```
604#[derive(Clone, Debug)]
605pub struct TemplateBuilder {
606    t: Template,
607    overflow: bool,
608}
609
610impl TemplateBuilder {
611    /// An empty template named `name`, recording `Template` expansions.
612    ///
613    /// # Examples
614    ///
615    /// ```
616    /// let t = lower_lang::TemplateBuilder::new("swap");
617    /// let _ = t;
618    /// ```
619    #[must_use]
620    pub fn new(name: &str) -> Self {
621        Self {
622            t: Template {
623                name: name.into(),
624                kind: ExpnKind::Template,
625                nodes: Vec::new(),
626                lists: Vec::new(),
627                texts: Vec::new(),
628                holes: Vec::new(),
629                binders: Vec::new(),
630                labels: Vec::new(),
631                args: Vec::new(),
632                applies: Vec::new(),
633                root: NONE,
634                text_base: 0,
635            },
636            overflow: false,
637        }
638    }
639
640    /// Records `Desugar` expansions instead (for built-in sugar such as
641    /// `while`, so tools can re-sugar it).
642    ///
643    /// # Examples
644    ///
645    /// ```
646    /// use hir_lang::ExpnKind;
647    /// use lower_lang::{TLit, TemplateBuilder};
648    ///
649    /// let mut t = TemplateBuilder::new("nothing").desugar();
650    /// let root = t.lit(TLit::Null);
651    /// assert_eq!(t.finish(root)?.expansion_kind(), ExpnKind::Desugar);
652    /// # Ok::<(), lower_lang::TemplateError>(())
653    /// ```
654    #[must_use]
655    pub fn desugar(mut self) -> Self {
656        self.t.kind = ExpnKind::Desugar;
657        self
658    }
659
660    // ---------------------------------------------------------------- tables
661
662    fn push(&mut self, node: TNode) -> u32 {
663        match u32::try_from(self.t.nodes.len()) {
664            Ok(i) if i < NONE => {
665                self.t.nodes.push(node);
666                i
667            }
668            _ => {
669                self.overflow = true;
670                NONE
671            }
672        }
673    }
674
675    fn list(&mut self, items: impl IntoIterator<Item = u32>) -> TList {
676        let start = self.t.lists.len();
677        self.t.lists.extend(items);
678        match (
679            u32::try_from(start),
680            u32::try_from(self.t.lists.len() - start),
681        ) {
682            (Ok(s), Ok(l)) => (s, l),
683            _ => {
684                self.overflow = true;
685                (0, 0)
686            }
687        }
688    }
689
690    fn text(&mut self, text: &str) -> u32 {
691        let i = self.t.texts.len();
692        self.t.texts.push(text.into());
693        u32::try_from(i).unwrap_or_else(|_| {
694            self.overflow = true;
695            0
696        })
697    }
698
699    fn hole_decl(
700        &mut self,
701        name: &str,
702        kind: HoleKind,
703        optional: bool,
704        default: Option<TLit>,
705    ) -> u16 {
706        let i = self.t.holes.len();
707        self.t.holes.push(HoleDecl {
708            name: name.into(),
709            kind,
710            optional,
711            default,
712        });
713        u16::try_from(i).unwrap_or_else(|_| {
714            self.overflow = true;
715            0
716        })
717    }
718
719    fn opt(e: Option<TExpr>) -> u32 {
720        e.map_or(NONE, |e| e.0)
721    }
722
723    // ----------------------------------------------------------------- holes
724
725    /// Declares a required expression hole.
726    ///
727    /// # Examples
728    ///
729    /// ```
730    /// let mut t = lower_lang::TemplateBuilder::new("t");
731    /// let h = t.expr_hole("value");
732    /// let root = t.hole(h);
733    /// assert!(t.finish(root).is_ok());
734    /// ```
735    pub fn expr_hole(&mut self, name: &str) -> ExprHole {
736        ExprHole(self.hole_decl(name, HoleKind::Expr, false, None))
737    }
738
739    /// Declares an optional expression hole. When the field is absent the hole
740    /// is `default` if given; otherwise it is left out where the slot is
741    /// optional (an `else`, a loop step, a `return` value) and is an error
742    /// where a value is required.
743    ///
744    /// # Examples
745    ///
746    /// ```
747    /// use lower_lang::TLit;
748    ///
749    /// let mut t = lower_lang::TemplateBuilder::new("t");
750    /// let cond = t.optional_expr_hole("cond", Some(TLit::Bool(true)));
751    /// let root = t.hole(cond);
752    /// assert_eq!(t.finish(root)?.hole(0).map(|h| h.2), Some(true));
753    /// # Ok::<(), lower_lang::TemplateError>(())
754    /// ```
755    pub fn optional_expr_hole(&mut self, name: &str, default: Option<TLit>) -> ExprHole {
756        ExprHole(self.hole_decl(name, HoleKind::Expr, true, default))
757    }
758
759    /// Declares a pattern hole; an absent optional pattern is `_`.
760    ///
761    /// # Examples
762    ///
763    /// ```
764    /// let mut t = lower_lang::TemplateBuilder::new("t");
765    /// let p = t.pat_hole("pat", false);
766    /// let pat = t.pat(p);
767    /// let unit = t.tuple(&[]);
768    /// let s = t.let_(pat, None, Some(unit));
769    /// let root = t.block(&[s], None);
770    /// assert!(t.finish(root).is_ok());
771    /// ```
772    pub fn pat_hole(&mut self, name: &str, optional: bool) -> PatHole {
773        PatHole(self.hole_decl(name, HoleKind::Pat, optional, None))
774    }
775
776    /// Declares a type hole; an absent optional type is left out where the
777    /// slot is optional and is `_` (inferred) elsewhere.
778    ///
779    /// # Examples
780    ///
781    /// ```
782    /// let mut t = lower_lang::TemplateBuilder::new("t");
783    /// let ty = t.ty_hole("ty", true);
784    /// let x = t.binder("x");
785    /// let pat = t.bind(x);
786    /// let ann = t.ty(ty);
787    /// let s = t.let_(pat, Some(ann), None);
788    /// let root = t.block(&[s], None);
789    /// assert!(t.finish(root).is_ok());
790    /// ```
791    pub fn ty_hole(&mut self, name: &str, optional: bool) -> TyHole {
792        TyHole(self.hole_decl(name, HoleKind::Ty, optional, None))
793    }
794
795    /// Declares a statement-list hole (zero or more statements).
796    ///
797    /// # Examples
798    ///
799    /// ```
800    /// let mut t = lower_lang::TemplateBuilder::new("t");
801    /// let body = t.stmts_hole("body");
802    /// let s = t.stmts(body);
803    /// let root = t.block(&[s], None);
804    /// assert!(t.finish(root).is_ok());
805    /// ```
806    pub fn stmts_hole(&mut self, name: &str) -> StmtsHole {
807        StmtsHole(self.hole_decl(name, HoleKind::Stmts, true, None))
808    }
809
810    /// Declares an argument-list hole (zero or more arguments).
811    ///
812    /// # Examples
813    ///
814    /// ```
815    /// let mut t = lower_lang::TemplateBuilder::new("echo");
816    /// let args = t.args_hole("args");
817    /// let callee = t.extern_("echo");
818    /// let spliced = t.splice(args);
819    /// let root = t.call(callee, &[spliced]);
820    /// assert!(t.finish(root).is_ok());
821    /// ```
822    pub fn args_hole(&mut self, name: &str) -> ArgsHole {
823        ArgsHole(self.hole_decl(name, HoleKind::Args, true, None))
824    }
825
826    /// Declares a label hole: the user's label (optional) for a loop or block
827    /// the template creates.
828    ///
829    /// # Examples
830    ///
831    /// ```
832    /// use lower_lang::LabelRef;
833    ///
834    /// let mut t = lower_lang::TemplateBuilder::new("t");
835    /// let l = t.label_hole("label");
836    /// let body = t.block(&[], None);
837    /// let root = t.loop_(Some(LabelRef::Hole(l)), body, None);
838    /// assert!(t.finish(root).is_ok());
839    /// ```
840    pub fn label_hole(&mut self, name: &str) -> LabelHole {
841        LabelHole(self.hole_decl(name, HoleKind::Label, true, None))
842    }
843
844    // -------------------------------------------------------- binders, labels
845
846    /// Declares an immutable local binder (hygienic: fresh per instantiation).
847    ///
848    /// # Examples
849    ///
850    /// ```
851    /// let mut t = lower_lang::TemplateBuilder::new("t");
852    /// let tmp = t.binder("tmp");
853    /// let pat = t.bind(tmp);
854    /// let one = t.lit(lower_lang::TLit::Int(1));
855    /// let s = t.let_(pat, None, Some(one));
856    /// let use_tmp = t.var(tmp);
857    /// let root = t.block(&[s], Some(use_tmp));
858    /// assert!(t.finish(root).is_ok());
859    /// ```
860    pub fn binder(&mut self, name: &str) -> TBinder {
861        self.binder_decl(name, false)
862    }
863
864    /// Declares a mutable local binder.
865    ///
866    /// # Examples
867    ///
868    /// ```
869    /// let mut t = lower_lang::TemplateBuilder::new("t");
870    /// let n = t.mutable_binder("n");
871    /// let pat = t.bind(n);
872    /// let zero = t.lit(lower_lang::TLit::Int(0));
873    /// let s = t.let_(pat, None, Some(zero));
874    /// let root = t.block(&[s], None);
875    /// assert!(t.finish(root).is_ok());
876    /// ```
877    pub fn mutable_binder(&mut self, name: &str) -> TBinder {
878        self.binder_decl(name, true)
879    }
880
881    fn binder_decl(&mut self, name: &str, mutable: bool) -> TBinder {
882        let name = self.text(name);
883        let i = self.t.binders.len();
884        self.t.binders.push(BinderDecl { name, mutable });
885        TBinder(u16::try_from(i).unwrap_or_else(|_| {
886            self.overflow = true;
887            0
888        }))
889    }
890
891    /// Declares a label the template defines on one of its loops or blocks.
892    ///
893    /// # Examples
894    ///
895    /// ```
896    /// use lower_lang::LabelRef;
897    ///
898    /// let mut t = lower_lang::TemplateBuilder::new("t");
899    /// let l = t.label("outer");
900    /// let brk = t.break_(Some(LabelRef::Own(l)), None);
901    /// let root = t.loop_(Some(LabelRef::Own(l)), brk, None);
902    /// assert!(t.finish(root).is_ok());
903    /// ```
904    pub fn label(&mut self, name: &str) -> TLabel {
905        let name = self.text(name);
906        let i = self.t.labels.len();
907        self.t.labels.push(BinderDecl {
908            name,
909            mutable: false,
910        });
911        TLabel(u16::try_from(i).unwrap_or_else(|_| {
912            self.overflow = true;
913            0
914        }))
915    }
916
917    // ----------------------------------------------------------- expressions
918
919    /// The value of an expression hole.
920    ///
921    /// # Examples
922    ///
923    /// ```
924    /// let mut t = lower_lang::TemplateBuilder::new("t");
925    /// let h = t.expr_hole("e");
926    /// let e = t.hole(h);
927    /// assert!(t.finish(e).is_ok());
928    /// ```
929    pub fn hole(&mut self, hole: ExprHole) -> TExpr {
930        TExpr(self.push(TNode::Hole(hole.0)))
931    }
932
933    /// The arguments of an argument-list hole, spliced in place; only valid
934    /// directly in [`call`](Self::call), [`method`](Self::method),
935    /// [`tuple`](Self::tuple), or [`array`](Self::array) lists.
936    ///
937    /// # Examples
938    ///
939    /// ```
940    /// let mut t = lower_lang::TemplateBuilder::new("t");
941    /// let args = t.args_hole("args");
942    /// let items = t.splice(args);
943    /// let root = t.array(&[items]);
944    /// assert!(t.finish(root).is_ok());
945    /// ```
946    pub fn splice(&mut self, hole: ArgsHole) -> TExpr {
947        TExpr(self.push(TNode::Splice(hole.0)))
948    }
949
950    /// A literal.
951    ///
952    /// # Examples
953    ///
954    /// ```
955    /// let mut t = lower_lang::TemplateBuilder::new("t");
956    /// let root = t.lit(lower_lang::TLit::Float(0.5));
957    /// assert!(t.finish(root).is_ok());
958    /// ```
959    pub fn lit(&mut self, lit: TLit) -> TExpr {
960        TExpr(self.push(TNode::Lit(lit)))
961    }
962
963    /// A string literal.
964    ///
965    /// # Examples
966    ///
967    /// ```
968    /// let mut t = lower_lang::TemplateBuilder::new("t");
969    /// let root = t.str("done");
970    /// assert!(t.finish(root).is_ok());
971    /// ```
972    pub fn str(&mut self, text: &str) -> TExpr {
973        let s = self.text(text);
974        TExpr(self.push(TNode::Str(s)))
975    }
976
977    /// A reference to one of the template's binders, resolved by
978    /// construction.
979    ///
980    /// # Examples
981    ///
982    /// See [`binder`](Self::binder).
983    pub fn var(&mut self, binder: TBinder) -> TExpr {
984        TExpr(self.push(TNode::Var(binder.0)))
985    }
986
987    /// A free name the template refers to (`iter`, `std::mem::swap`), split
988    /// at `::`. It carries the expansion's hygiene mark, so a user variable of
989    /// the same spelling cannot capture it; a resolver looks it up at the
990    /// template's definition site.
991    ///
992    /// # Examples
993    ///
994    /// ```
995    /// let mut t = lower_lang::TemplateBuilder::new("t");
996    /// let f = t.global("core::mem::take");
997    /// let root = t.call(f, &[]);
998    /// assert!(t.finish(root).is_ok());
999    /// ```
1000    pub fn global(&mut self, path: &str) -> TExpr {
1001        let s = self.text(path);
1002        TExpr(self.push(TNode::Global(s)))
1003    }
1004
1005    /// A host symbol (`[stdlib]`), already resolved to `Res::Extern`.
1006    ///
1007    /// # Examples
1008    ///
1009    /// ```
1010    /// let mut t = lower_lang::TemplateBuilder::new("t");
1011    /// let f = t.extern_("mox.iter");
1012    /// let root = t.call(f, &[]);
1013    /// assert!(t.finish(root).is_ok());
1014    /// ```
1015    pub fn extern_(&mut self, name: &str) -> TExpr {
1016        let s = self.text(name);
1017        TExpr(self.push(TNode::Extern(s)))
1018    }
1019
1020    /// `callee(args)`.
1021    ///
1022    /// # Examples
1023    ///
1024    /// See [`extern_`](Self::extern_).
1025    pub fn call(&mut self, callee: TExpr, args: &[TExpr]) -> TExpr {
1026        let args = self.list(args.iter().map(|a| a.0));
1027        TExpr(self.push(TNode::Call {
1028            callee: callee.0,
1029            args,
1030        }))
1031    }
1032
1033    /// `recv.name(args)`.
1034    ///
1035    /// # Examples
1036    ///
1037    /// ```
1038    /// let mut t = lower_lang::TemplateBuilder::new("t");
1039    /// let h = t.expr_hole("it");
1040    /// let it = t.hole(h);
1041    /// let root = t.method(it, "next", &[]);
1042    /// assert!(t.finish(root).is_ok());
1043    /// ```
1044    pub fn method(&mut self, recv: TExpr, name: &str, args: &[TExpr]) -> TExpr {
1045        let name = self.text(name);
1046        let args = self.list(args.iter().map(|a| a.0));
1047        TExpr(self.push(TNode::Method {
1048            recv: recv.0,
1049            name,
1050            args,
1051        }))
1052    }
1053
1054    /// `base.name`.
1055    ///
1056    /// # Examples
1057    ///
1058    /// ```
1059    /// let mut t = lower_lang::TemplateBuilder::new("t");
1060    /// let h = t.expr_hole("e");
1061    /// let e = t.hole(h);
1062    /// let root = t.field(e, "len");
1063    /// assert!(t.finish(root).is_ok());
1064    /// ```
1065    pub fn field(&mut self, base: TExpr, name: &str) -> TExpr {
1066        let name = self.text(name);
1067        TExpr(self.push(TNode::Field { base: base.0, name }))
1068    }
1069
1070    /// `base[index]`.
1071    ///
1072    /// # Examples
1073    ///
1074    /// ```
1075    /// use lower_lang::TLit;
1076    ///
1077    /// let mut t = lower_lang::TemplateBuilder::new("t");
1078    /// let h = t.expr_hole("e");
1079    /// let e = t.hole(h);
1080    /// let zero = t.lit(TLit::Int(0));
1081    /// let root = t.index(e, zero);
1082    /// assert!(t.finish(root).is_ok());
1083    /// ```
1084    pub fn index(&mut self, base: TExpr, index: TExpr) -> TExpr {
1085        TExpr(self.push(TNode::Index {
1086            base: base.0,
1087            index: index.0,
1088        }))
1089    }
1090
1091    /// An intrinsic operation with the language's policies (from the
1092    /// mapping's [`LangPolicy`](crate::LangPolicy)).
1093    ///
1094    /// # Examples
1095    ///
1096    /// ```
1097    /// use hir_lang::OpKind;
1098    ///
1099    /// let mut t = lower_lang::TemplateBuilder::new("not");
1100    /// let h = t.expr_hole("e");
1101    /// let e = t.hole(h);
1102    /// let root = t.op(OpKind::Not, &[e]);
1103    /// assert!(t.finish(root).is_ok());
1104    /// ```
1105    pub fn op(&mut self, kind: OpKind, args: &[TExpr]) -> TExpr {
1106        let args = self.list(args.iter().map(|a| a.0));
1107        TExpr(self.push(TNode::Op {
1108            op: Op::new(kind),
1109            exact: false,
1110            args,
1111        }))
1112    }
1113
1114    /// An intrinsic operation with exactly this policy.
1115    ///
1116    /// # Examples
1117    ///
1118    /// ```
1119    /// use hir_lang::{Op, OpKind, Overflow};
1120    ///
1121    /// let mut t = lower_lang::TemplateBuilder::new("inc");
1122    /// let h = t.expr_hole("e");
1123    /// let e = t.hole(h);
1124    /// let one = t.lit(lower_lang::TLit::Int(1));
1125    /// let root = t.op_with(Op::new(OpKind::Add).with_overflow(Overflow::Wrap), &[e, one]);
1126    /// assert!(t.finish(root).is_ok());
1127    /// ```
1128    pub fn op_with(&mut self, op: Op, args: &[TExpr]) -> TExpr {
1129        let args = self.list(args.iter().map(|a| a.0));
1130        TExpr(self.push(TNode::Op {
1131            op,
1132            exact: true,
1133            args,
1134        }))
1135    }
1136
1137    /// `target = value`.
1138    ///
1139    /// # Examples
1140    ///
1141    /// ```
1142    /// let mut t = lower_lang::TemplateBuilder::new("t");
1143    /// let p = t.expr_hole("place");
1144    /// let v = t.expr_hole("value");
1145    /// let (p, v) = (t.hole(p), t.hole(v));
1146    /// let root = t.assign(p, v);
1147    /// assert!(t.finish(root).is_ok());
1148    /// ```
1149    pub fn assign(&mut self, target: TExpr, value: TExpr) -> TExpr {
1150        TExpr(self.push(TNode::Assign {
1151            target: target.0,
1152            value: value.0,
1153        }))
1154    }
1155
1156    /// `{ stmts; tail }`.
1157    ///
1158    /// # Examples
1159    ///
1160    /// ```
1161    /// let mut t = lower_lang::TemplateBuilder::new("t");
1162    /// let root = t.block(&[], None);
1163    /// assert!(t.finish(root).is_ok());
1164    /// ```
1165    pub fn block(&mut self, stmts: &[TStmt], tail: Option<TExpr>) -> TExpr {
1166        let stmts = self.list(stmts.iter().map(|s| s.0));
1167        TExpr(self.push(TNode::Block {
1168            stmts,
1169            tail: Self::opt(tail),
1170            label: LabelSlot::None,
1171        }))
1172    }
1173
1174    /// `'label: { stmts; tail }`.
1175    ///
1176    /// # Examples
1177    ///
1178    /// ```
1179    /// use lower_lang::LabelRef;
1180    ///
1181    /// let mut t = lower_lang::TemplateBuilder::new("t");
1182    /// let l = t.label("done");
1183    /// let brk = t.break_(Some(LabelRef::Own(l)), None);
1184    /// let s = t.expr_stmt(brk);
1185    /// let root = t.labeled_block(LabelRef::Own(l), &[s], None);
1186    /// assert!(t.finish(root).is_ok());
1187    /// ```
1188    pub fn labeled_block(
1189        &mut self,
1190        label: LabelRef,
1191        stmts: &[TStmt],
1192        tail: Option<TExpr>,
1193    ) -> TExpr {
1194        let stmts = self.list(stmts.iter().map(|s| s.0));
1195        TExpr(self.push(TNode::Block {
1196            stmts,
1197            tail: Self::opt(tail),
1198            label: LabelSlot::of(Some(label)),
1199        }))
1200    }
1201
1202    /// `if cond { then } else { else_ }`.
1203    ///
1204    /// # Examples
1205    ///
1206    /// See [`TemplateBuilder`].
1207    pub fn if_(&mut self, cond: TExpr, then: TExpr, else_: Option<TExpr>) -> TExpr {
1208        TExpr(self.push(TNode::If {
1209            cond: cond.0,
1210            then: then.0,
1211            else_: Self::opt(else_),
1212        }))
1213    }
1214
1215    /// `match scrutinee { pat if guard => body, ... }`.
1216    ///
1217    /// # Examples
1218    ///
1219    /// ```
1220    /// use lower_lang::TLit;
1221    ///
1222    /// let mut t = lower_lang::TemplateBuilder::new("t");
1223    /// let h = t.expr_hole("e");
1224    /// let e = t.hole(h);
1225    /// let null = t.lit_pat(TLit::Null);
1226    /// let zero = t.lit(TLit::Int(0));
1227    /// let wild = t.wild();
1228    /// let one = t.lit(TLit::Int(1));
1229    /// let root = t.match_(e, &[(null, None, zero), (wild, None, one)]);
1230    /// assert!(t.finish(root).is_ok());
1231    /// ```
1232    pub fn match_(&mut self, scrutinee: TExpr, arms: &[(TPat, Option<TExpr>, TExpr)]) -> TExpr {
1233        let arms = self.list(arms.iter().flat_map(|(p, g, b)| [p.0, Self::opt(*g), b.0]));
1234        TExpr(self.push(TNode::Match {
1235            scrutinee: scrutinee.0,
1236            arms,
1237        }))
1238    }
1239
1240    /// `'label: loop { body } [step]` — HIR's one loop.
1241    ///
1242    /// # Examples
1243    ///
1244    /// See [`label_hole`](Self::label_hole).
1245    pub fn loop_(&mut self, label: Option<LabelRef>, body: TExpr, step: Option<TExpr>) -> TExpr {
1246        TExpr(self.push(TNode::Loop {
1247            label: LabelSlot::of(label),
1248            body: body.0,
1249            step: Self::opt(step),
1250        }))
1251    }
1252
1253    /// `break 'label value`.
1254    ///
1255    /// # Examples
1256    ///
1257    /// See [`label`](Self::label).
1258    pub fn break_(&mut self, label: Option<LabelRef>, value: Option<TExpr>) -> TExpr {
1259        TExpr(self.push(TNode::Break {
1260            label: LabelSlot::of(label),
1261            value: Self::opt(value),
1262        }))
1263    }
1264
1265    /// `continue 'label`.
1266    ///
1267    /// # Examples
1268    ///
1269    /// ```
1270    /// let mut t = lower_lang::TemplateBuilder::new("t");
1271    /// let c = t.continue_(None);
1272    /// let root = t.loop_(None, c, None);
1273    /// assert!(t.finish(root).is_ok());
1274    /// ```
1275    pub fn continue_(&mut self, label: Option<LabelRef>) -> TExpr {
1276        TExpr(self.push(TNode::Continue {
1277            label: LabelSlot::of(label),
1278        }))
1279    }
1280
1281    /// `return value`.
1282    ///
1283    /// # Examples
1284    ///
1285    /// ```
1286    /// let mut t = lower_lang::TemplateBuilder::new("t");
1287    /// let root = t.return_(None);
1288    /// assert!(t.finish(root).is_ok());
1289    /// ```
1290    pub fn return_(&mut self, value: Option<TExpr>) -> TExpr {
1291        TExpr(self.push(TNode::Return(Self::opt(value))))
1292    }
1293
1294    /// `throw value`.
1295    ///
1296    /// # Examples
1297    ///
1298    /// ```
1299    /// let mut t = lower_lang::TemplateBuilder::new("t");
1300    /// let h = t.expr_hole("e");
1301    /// let e = t.hole(h);
1302    /// let root = t.throw(e);
1303    /// assert!(t.finish(root).is_ok());
1304    /// ```
1305    pub fn throw(&mut self, value: TExpr) -> TExpr {
1306        TExpr(self.push(TNode::Throw(value.0)))
1307    }
1308
1309    /// `await value`.
1310    ///
1311    /// # Examples
1312    ///
1313    /// ```
1314    /// let mut t = lower_lang::TemplateBuilder::new("t");
1315    /// let h = t.expr_hole("e");
1316    /// let e = t.hole(h);
1317    /// let root = t.await_(e);
1318    /// assert!(t.finish(root).is_ok());
1319    /// ```
1320    pub fn await_(&mut self, value: TExpr) -> TExpr {
1321        TExpr(self.push(TNode::Await(value.0)))
1322    }
1323
1324    /// `yield value`.
1325    ///
1326    /// # Examples
1327    ///
1328    /// ```
1329    /// let mut t = lower_lang::TemplateBuilder::new("t");
1330    /// let root = t.yield_(None);
1331    /// assert!(t.finish(root).is_ok());
1332    /// ```
1333    pub fn yield_(&mut self, value: Option<TExpr>) -> TExpr {
1334        TExpr(self.push(TNode::Yield(Self::opt(value))))
1335    }
1336
1337    /// `spawn callable`.
1338    ///
1339    /// # Examples
1340    ///
1341    /// ```
1342    /// let mut t = lower_lang::TemplateBuilder::new("t");
1343    /// let h = t.expr_hole("f");
1344    /// let f = t.hole(h);
1345    /// let root = t.spawn(f);
1346    /// assert!(t.finish(root).is_ok());
1347    /// ```
1348    pub fn spawn(&mut self, callable: TExpr) -> TExpr {
1349        TExpr(self.push(TNode::Spawn(callable.0)))
1350    }
1351
1352    /// `(elems)`; `()` is unit.
1353    ///
1354    /// # Examples
1355    ///
1356    /// ```
1357    /// let mut t = lower_lang::TemplateBuilder::new("t");
1358    /// let root = t.tuple(&[]);
1359    /// assert!(t.finish(root).is_ok());
1360    /// ```
1361    pub fn tuple(&mut self, elems: &[TExpr]) -> TExpr {
1362        let elems = self.list(elems.iter().map(|e| e.0));
1363        TExpr(self.push(TNode::Tuple(elems)))
1364    }
1365
1366    /// `[elems]`.
1367    ///
1368    /// # Examples
1369    ///
1370    /// See [`splice`](Self::splice).
1371    pub fn array(&mut self, elems: &[TExpr]) -> TExpr {
1372        let elems = self.list(elems.iter().map(|e| e.0));
1373        TExpr(self.push(TNode::Array(elems)))
1374    }
1375
1376    /// A closure with the given parameters (each binds one of the template's
1377    /// binders) and implicit-capture mode.
1378    ///
1379    /// # Examples
1380    ///
1381    /// ```
1382    /// use hir_lang::CaptureMode;
1383    ///
1384    /// let mut t = lower_lang::TemplateBuilder::new("thunk");
1385    /// let h = t.expr_hole("e");
1386    /// let e = t.hole(h);
1387    /// let root = t.closure(&[], e, Some(CaptureMode::ByRef));
1388    /// assert!(t.finish(root).is_ok());
1389    /// ```
1390    pub fn closure(
1391        &mut self,
1392        params: &[TBinder],
1393        body: TExpr,
1394        implicit: Option<CaptureMode>,
1395    ) -> TExpr {
1396        let params = self.list(params.iter().map(|p| u32::from(p.0)));
1397        TExpr(self.push(TNode::Closure {
1398            params,
1399            body: body.0,
1400            implicit,
1401        }))
1402    }
1403
1404    /// Instantiates another template here, one argument per hole of the
1405    /// applied template. The template must be registered in the same mapping
1406    /// before this one, so templates can never apply themselves; checked by
1407    /// [`MappingBuilder::template`](crate::MappingBuilder::template). Each
1408    /// application is a nested expansion, counted against
1409    /// [`Budget::max_expansion_depth`](crate::Budget).
1410    ///
1411    /// # Examples
1412    ///
1413    /// ```
1414    /// use hir_lang::OpKind;
1415    /// use lower_lang::{templates, MappingBuilder, TArg, TemplateBuilder};
1416    ///
1417    /// let mut m = MappingBuilder::<u8>::new();
1418    /// let while_loop = m.template(templates::while_loop())?;
1419    /// // until c { b }  ==  while !c { b }
1420    /// let mut t = TemplateBuilder::new("until");
1421    /// let (c, b) = (t.expr_hole("cond"), t.expr_hole("body"));
1422    /// let c = t.hole(c);
1423    /// let not_c = t.op(OpKind::Not, &[c]);
1424    /// let b = t.hole(b);
1425    /// let root = t.apply(while_loop, &[TArg::Expr(not_c), TArg::Expr(b), TArg::Absent]);
1426    /// let until = t.finish(root).expect("valid");
1427    /// assert!(m.template(until).is_ok());
1428    /// # Ok::<(), lower_lang::MappingError>(())
1429    /// ```
1430    pub fn apply(&mut self, template: TemplateId, args: &[TArg]) -> TExpr {
1431        let start = self.t.args.len();
1432        self.t.args.extend_from_slice(args);
1433        let list = match (u32::try_from(start), u32::try_from(args.len())) {
1434            (Ok(s), Ok(l)) => (s, l),
1435            _ => {
1436                self.overflow = true;
1437                (0, 0)
1438            }
1439        };
1440        TExpr(self.push(TNode::Apply {
1441            template: template.0,
1442            args: list,
1443        }))
1444    }
1445
1446    // ------------------------------------------------------------ statements
1447
1448    /// `let pat: ty = init;`
1449    ///
1450    /// # Examples
1451    ///
1452    /// See [`binder`](Self::binder).
1453    pub fn let_(&mut self, pat: TPat, ty: Option<TTy>, init: Option<TExpr>) -> TStmt {
1454        TStmt(self.push(TNode::Let {
1455            pat: pat.0,
1456            ty: ty.map_or(NONE, |t| t.0),
1457            init: Self::opt(init),
1458        }))
1459    }
1460
1461    /// `expr;`
1462    ///
1463    /// # Examples
1464    ///
1465    /// See [`labeled_block`](Self::labeled_block).
1466    pub fn expr_stmt(&mut self, expr: TExpr) -> TStmt {
1467        TStmt(self.push(TNode::ExprStmt(expr.0)))
1468    }
1469
1470    /// `defer expr;`
1471    ///
1472    /// # Examples
1473    ///
1474    /// ```
1475    /// let mut t = lower_lang::TemplateBuilder::new("t");
1476    /// let h = t.expr_hole("cleanup");
1477    /// let e = t.hole(h);
1478    /// let s = t.defer(e);
1479    /// let root = t.block(&[s], None);
1480    /// assert!(t.finish(root).is_ok());
1481    /// ```
1482    pub fn defer(&mut self, expr: TExpr) -> TStmt {
1483        TStmt(self.push(TNode::Defer(expr.0)))
1484    }
1485
1486    /// The statements of a statement-list hole, spliced into the block.
1487    ///
1488    /// # Examples
1489    ///
1490    /// See [`stmts_hole`](Self::stmts_hole).
1491    pub fn stmts(&mut self, hole: StmtsHole) -> TStmt {
1492        TStmt(self.push(TNode::Stmts(hole.0)))
1493    }
1494
1495    // -------------------------------------------------------------- patterns
1496
1497    /// The pattern of a pattern hole.
1498    ///
1499    /// # Examples
1500    ///
1501    /// See [`pat_hole`](Self::pat_hole).
1502    pub fn pat(&mut self, hole: PatHole) -> TPat {
1503        TPat(self.push(TNode::PHole(hole.0)))
1504    }
1505
1506    /// `_`.
1507    ///
1508    /// # Examples
1509    ///
1510    /// See [`match_`](Self::match_).
1511    pub fn wild(&mut self) -> TPat {
1512        TPat(self.push(TNode::PWild))
1513    }
1514
1515    /// Binds one of the template's binders (by value).
1516    ///
1517    /// # Examples
1518    ///
1519    /// See [`binder`](Self::binder).
1520    pub fn bind(&mut self, binder: TBinder) -> TPat {
1521        TPat(self.push(TNode::PBind(binder.0)))
1522    }
1523
1524    /// Matches a literal.
1525    ///
1526    /// # Examples
1527    ///
1528    /// See [`match_`](Self::match_).
1529    pub fn lit_pat(&mut self, lit: TLit) -> TPat {
1530        TPat(self.push(TNode::PLit(lit)))
1531    }
1532
1533    /// `(elems)`.
1534    ///
1535    /// # Examples
1536    ///
1537    /// ```
1538    /// let mut t = lower_lang::TemplateBuilder::new("t");
1539    /// let k = t.pat_hole("key", true);
1540    /// let v = t.pat_hole("value", false);
1541    /// let (k, v) = (t.pat(k), t.pat(v));
1542    /// let pair = t.tuple_pat(&[k, v]);
1543    /// let unit = t.tuple(&[]);
1544    /// let s = t.let_(pair, None, Some(unit));
1545    /// let root = t.block(&[s], None);
1546    /// assert!(t.finish(root).is_ok());
1547    /// ```
1548    pub fn tuple_pat(&mut self, elems: &[TPat]) -> TPat {
1549        let elems = self.list(elems.iter().map(|p| p.0));
1550        TPat(self.push(TNode::PTuple(elems)))
1551    }
1552
1553    /// `Path(elems)`, the path written like [`global`](Self::global).
1554    ///
1555    /// # Examples
1556    ///
1557    /// ```
1558    /// let mut t = lower_lang::TemplateBuilder::new("t");
1559    /// let h = t.expr_hole("e");
1560    /// let e = t.hole(h);
1561    /// let v = t.binder("v");
1562    /// let bind = t.bind(v);
1563    /// let some = t.ctor_pat("Some", &[bind]);
1564    /// let use_v = t.var(v);
1565    /// let wild = t.wild();
1566    /// let zero = t.lit(lower_lang::TLit::Int(0));
1567    /// let root = t.match_(e, &[(some, None, use_v), (wild, None, zero)]);
1568    /// assert!(t.finish(root).is_ok());
1569    /// ```
1570    pub fn ctor_pat(&mut self, path: &str, elems: &[TPat]) -> TPat {
1571        let path = self.text(path);
1572        let elems = self.list(elems.iter().map(|p| p.0));
1573        TPat(self.push(TNode::PCtor { path, elems }))
1574    }
1575
1576    // ----------------------------------------------------------------- types
1577
1578    /// The type of a type hole.
1579    ///
1580    /// # Examples
1581    ///
1582    /// See [`ty_hole`](Self::ty_hole).
1583    pub fn ty(&mut self, hole: TyHole) -> TTy {
1584        TTy(self.push(TNode::THole(hole.0)))
1585    }
1586
1587    /// A primitive type.
1588    ///
1589    /// # Examples
1590    ///
1591    /// ```
1592    /// use hir_lang::Prim;
1593    ///
1594    /// let mut t = lower_lang::TemplateBuilder::new("t");
1595    /// let x = t.binder("x");
1596    /// let p = t.bind(x);
1597    /// let int = t.prim(Prim::I64);
1598    /// let s = t.let_(p, Some(int), None);
1599    /// let root = t.block(&[s], None);
1600    /// assert!(t.finish(root).is_ok());
1601    /// ```
1602    pub fn prim(&mut self, prim: Prim) -> TTy {
1603        TTy(self.push(TNode::TPrim(prim)))
1604    }
1605
1606    /// A named type, written like [`global`](Self::global).
1607    ///
1608    /// # Examples
1609    ///
1610    /// ```
1611    /// let mut t = lower_lang::TemplateBuilder::new("t");
1612    /// let x = t.binder("x");
1613    /// let p = t.bind(x);
1614    /// let ty = t.named_ty("Iterator");
1615    /// let s = t.let_(p, Some(ty), None);
1616    /// let root = t.block(&[s], None);
1617    /// assert!(t.finish(root).is_ok());
1618    /// ```
1619    pub fn named_ty(&mut self, path: &str) -> TTy {
1620        let path = self.text(path);
1621        TTy(self.push(TNode::TNamed(path)))
1622    }
1623
1624    /// `_`: a type to infer.
1625    ///
1626    /// # Examples
1627    ///
1628    /// ```
1629    /// let mut t = lower_lang::TemplateBuilder::new("t");
1630    /// let x = t.binder("x");
1631    /// let p = t.bind(x);
1632    /// let ty = t.infer_ty();
1633    /// let s = t.let_(p, Some(ty), None);
1634    /// let root = t.block(&[s], None);
1635    /// assert!(t.finish(root).is_ok());
1636    /// ```
1637    pub fn infer_ty(&mut self) -> TTy {
1638        TTy(self.push(TNode::TInfer))
1639    }
1640
1641    /// The gradual dynamic type.
1642    ///
1643    /// # Examples
1644    ///
1645    /// ```
1646    /// let mut t = lower_lang::TemplateBuilder::new("t");
1647    /// let x = t.binder("x");
1648    /// let p = t.bind(x);
1649    /// let ty = t.any_ty();
1650    /// let s = t.let_(p, Some(ty), None);
1651    /// let root = t.block(&[s], None);
1652    /// assert!(t.finish(root).is_ok());
1653    /// ```
1654    pub fn any_ty(&mut self) -> TTy {
1655        TTy(self.push(TNode::TAny))
1656    }
1657
1658    // ---------------------------------------------------------------- finish
1659
1660    /// Checks the template rooted at `root` and returns it.
1661    ///
1662    /// # Errors
1663    ///
1664    /// A [`TemplateError`]: an unused hole, an unbound or twice-bound binder,
1665    /// an undefined or twice-defined label, an argument splice outside a list,
1666    /// a handle from another builder, or a tree larger than
1667    /// [`MAX_TEMPLATE_SIZE`].
1668    ///
1669    /// # Examples
1670    ///
1671    /// ```
1672    /// use lower_lang::{TemplateBuilder, TemplateError};
1673    ///
1674    /// let mut t = TemplateBuilder::new("bad");
1675    /// let x = t.binder("x");
1676    /// let root = t.var(x); // never bound
1677    /// assert_eq!(t.finish(root), Err(TemplateError::BinderUnbound { binder: 0 }));
1678    /// ```
1679    pub fn finish(mut self, root: TExpr) -> Result<Template, TemplateError> {
1680        if self.overflow {
1681            return Err(TemplateError::TooLarge);
1682        }
1683        self.t.root = root.0;
1684        let applies = check(&self.t)?;
1685        self.t.applies = applies;
1686        Ok(self.t)
1687    }
1688}
1689
1690/// Use and binding counts gathered by walking a template's tree.
1691struct Counts {
1692    hole_uses: Vec<u32>,
1693    binder_sites: Vec<u32>,
1694    binder_uses: Vec<u32>,
1695    label_defs: Vec<u32>,
1696    label_uses: Vec<u32>,
1697}
1698
1699/// Walks the template's tree from its root (iteratively, counting shared
1700/// sub-trees at every use) and checks it. Returns the `Apply` nodes reached.
1701fn check(t: &Template) -> Result<Vec<u32>, TemplateError> {
1702    let mut c = Counts {
1703        hole_uses: alloc::vec![0; t.holes.len()],
1704        binder_sites: alloc::vec![0; t.binders.len()],
1705        binder_uses: alloc::vec![0; t.binders.len()],
1706        label_defs: alloc::vec![0; t.labels.len()],
1707        label_uses: alloc::vec![0; t.labels.len()],
1708    };
1709    let mut applies = Vec::new();
1710    // (node, whether it sits directly in an argument/element list)
1711    let mut stack: Vec<(u32, bool)> = alloc::vec![(t.root, false)];
1712    let mut size: u32 = 0;
1713    while let Some((n, in_list)) = stack.pop() {
1714        if n == NONE {
1715            continue;
1716        }
1717        size += 1;
1718        if size > MAX_TEMPLATE_SIZE {
1719            return Err(TemplateError::TooLarge);
1720        }
1721        let node = *t.node(n).ok_or(TemplateError::ForeignHandle)?;
1722        let kids = |list: TList,
1723                    in_list: bool,
1724                    stack: &mut Vec<(u32, bool)>|
1725         -> Result<(), TemplateError> {
1726            let (start, len) = (list.0 as usize, list.1 as usize);
1727            let slice = t
1728                .lists
1729                .get(start..start.saturating_add(len))
1730                .ok_or(TemplateError::ForeignHandle)?;
1731            stack.extend(slice.iter().map(|&k| (k, in_list)));
1732            Ok(())
1733        };
1734        match node {
1735            TNode::Hole(h) | TNode::PHole(h) | TNode::THole(h) | TNode::Stmts(h) => {
1736                bump(&mut c.hole_uses, usize::from(h))?;
1737            }
1738            TNode::Splice(h) => {
1739                if !in_list {
1740                    return Err(TemplateError::SpliceOutOfList {
1741                        hole: usize::from(h),
1742                    });
1743                }
1744                bump(&mut c.hole_uses, usize::from(h))?;
1745            }
1746            TNode::Var(b) => bump(&mut c.binder_uses, usize::from(b))?,
1747            TNode::PBind(b) => bump(&mut c.binder_sites, usize::from(b))?,
1748            TNode::Lit(_)
1749            | TNode::Str(_)
1750            | TNode::Global(_)
1751            | TNode::Extern(_)
1752            | TNode::PWild
1753            | TNode::PLit(_)
1754            | TNode::TPrim(_)
1755            | TNode::TNamed(_)
1756            | TNode::TInfer
1757            | TNode::TAny => {}
1758            TNode::Call { callee, args } => {
1759                stack.push((callee, false));
1760                kids(args, true, &mut stack)?;
1761            }
1762            TNode::Method { recv, args, .. } => {
1763                stack.push((recv, false));
1764                kids(args, true, &mut stack)?;
1765            }
1766            TNode::Field { base, .. } => stack.push((base, false)),
1767            TNode::Index { base, index } => stack.extend([(base, false), (index, false)]),
1768            TNode::Op { args, .. } => kids(args, false, &mut stack)?,
1769            TNode::Assign { target, value } => stack.extend([(target, false), (value, false)]),
1770            TNode::Block { stmts, tail, label } => {
1771                define_label(&mut c, label)?;
1772                kids(stmts, false, &mut stack)?;
1773                stack.push((tail, false));
1774            }
1775            TNode::If { cond, then, else_ } => {
1776                stack.extend([(cond, false), (then, false), (else_, false)]);
1777            }
1778            TNode::Match { scrutinee, arms } => {
1779                stack.push((scrutinee, false));
1780                kids(arms, false, &mut stack)?;
1781            }
1782            TNode::Loop { label, body, step } => {
1783                define_label(&mut c, label)?;
1784                stack.extend([(body, false), (step, false)]);
1785            }
1786            TNode::Break { label, value } => {
1787                use_label(&mut c, label)?;
1788                stack.push((value, false));
1789            }
1790            TNode::Continue { label } => use_label(&mut c, label)?,
1791            TNode::Return(v)
1792            | TNode::Throw(v)
1793            | TNode::Await(v)
1794            | TNode::Yield(v)
1795            | TNode::Spawn(v)
1796            | TNode::ExprStmt(v)
1797            | TNode::Defer(v) => stack.push((v, false)),
1798            TNode::Tuple(l) | TNode::Array(l) => kids(l, true, &mut stack)?,
1799            TNode::Closure { params, body, .. } => {
1800                let (start, len) = (params.0 as usize, params.1 as usize);
1801                let slice = t
1802                    .lists
1803                    .get(start..start.saturating_add(len))
1804                    .ok_or(TemplateError::ForeignHandle)?;
1805                for &p in slice {
1806                    bump(&mut c.binder_sites, p as usize)?;
1807                }
1808                stack.push((body, false));
1809            }
1810            TNode::Apply { args, .. } => {
1811                applies.push(n);
1812                let (start, len) = (args.0 as usize, args.1 as usize);
1813                let slice = t
1814                    .args
1815                    .get(start..start.saturating_add(len))
1816                    .ok_or(TemplateError::ForeignHandle)?;
1817                for arg in slice {
1818                    match *arg {
1819                        TArg::Expr(e) => stack.push((e.0, false)),
1820                        TArg::Pat(p) => stack.push((p.0, false)),
1821                        TArg::Ty(ty) => stack.push((ty.0, false)),
1822                        TArg::Stmts(h) => bump(&mut c.hole_uses, usize::from(h.0))?,
1823                        TArg::Args(h) => bump(&mut c.hole_uses, usize::from(h.0))?,
1824                        TArg::Label(l) => use_label(&mut c, LabelSlot::of(Some(l)))?,
1825                        TArg::Absent => {}
1826                    }
1827                }
1828            }
1829            TNode::Let { pat, ty, init } => {
1830                stack.extend([(pat, false), (ty, false), (init, false)])
1831            }
1832            TNode::PTuple(l) => kids(l, false, &mut stack)?,
1833            TNode::PCtor { elems, .. } => kids(elems, false, &mut stack)?,
1834        }
1835    }
1836    for (i, &n) in c.hole_uses.iter().enumerate() {
1837        if n == 0 {
1838            return Err(TemplateError::HoleUnused { hole: i });
1839        }
1840    }
1841    for (i, (&sites, &uses)) in c.binder_sites.iter().zip(&c.binder_uses).enumerate() {
1842        if sites > 1 {
1843            return Err(TemplateError::BinderBoundTwice { binder: i });
1844        }
1845        if sites == 0 && uses > 0 {
1846            return Err(TemplateError::BinderUnbound { binder: i });
1847        }
1848    }
1849    for (i, (&defs, &uses)) in c.label_defs.iter().zip(&c.label_uses).enumerate() {
1850        if defs > 1 {
1851            return Err(TemplateError::LabelDefinedTwice { label: i });
1852        }
1853        if defs == 0 && uses > 0 {
1854            return Err(TemplateError::LabelUndefined { label: i });
1855        }
1856    }
1857    Ok(applies)
1858}
1859
1860fn bump(counts: &mut [u32], i: usize) -> Result<(), TemplateError> {
1861    let slot = counts.get_mut(i).ok_or(TemplateError::ForeignHandle)?;
1862    *slot = slot.saturating_add(1);
1863    Ok(())
1864}
1865
1866fn define_label(c: &mut Counts, label: LabelSlot) -> Result<(), TemplateError> {
1867    match label {
1868        LabelSlot::None => Ok(()),
1869        LabelSlot::Own(l) => bump(&mut c.label_defs, usize::from(l)),
1870        LabelSlot::Hole(h) => bump(&mut c.hole_uses, usize::from(h)),
1871    }
1872}
1873
1874fn use_label(c: &mut Counts, label: LabelSlot) -> Result<(), TemplateError> {
1875    match label {
1876        LabelSlot::None => Ok(()),
1877        LabelSlot::Own(l) => bump(&mut c.label_uses, usize::from(l)),
1878        LabelSlot::Hole(h) => bump(&mut c.hole_uses, usize::from(h)),
1879    }
1880}
1881
1882#[cfg(test)]
1883mod tests {
1884    use super::*;
1885
1886    #[test]
1887    fn test_shared_subtrees_count_at_every_use() {
1888        let mut t = TemplateBuilder::new("blowup");
1889        let mut e = t.lit(TLit::Int(1));
1890        for _ in 0..40 {
1891            e = t.tuple(&[e, e]);
1892        }
1893        assert_eq!(t.finish(e), Err(TemplateError::TooLarge));
1894    }
1895
1896    #[test]
1897    fn test_foreign_handles_are_refused() {
1898        let mut t = TemplateBuilder::new("foreign");
1899        let root = TExpr(99);
1900        let _ = t.lit(TLit::Null);
1901        assert_eq!(t.finish(root), Err(TemplateError::ForeignHandle));
1902    }
1903
1904    #[test]
1905    fn test_label_rules() {
1906        let mut t = TemplateBuilder::new("labels");
1907        let l = t.label("l");
1908        let brk = t.break_(Some(LabelRef::Own(l)), None);
1909        assert_eq!(
1910            t.finish(brk),
1911            Err(TemplateError::LabelUndefined { label: 0 })
1912        );
1913
1914        let mut t = TemplateBuilder::new("labels");
1915        let l = t.label("l");
1916        let body = t.block(&[], None);
1917        let a = t.loop_(Some(LabelRef::Own(l)), body, None);
1918        let b = t.loop_(Some(LabelRef::Own(l)), body, None);
1919        let root = t.tuple(&[a, b]);
1920        assert_eq!(
1921            t.finish(root),
1922            Err(TemplateError::LabelDefinedTwice { label: 0 })
1923        );
1924    }
1925
1926    #[test]
1927    fn test_splice_outside_a_list_is_refused() {
1928        let mut t = TemplateBuilder::new("splice");
1929        let args = t.args_hole("args");
1930        let s = t.splice(args);
1931        let root = t.op(OpKind::Not, &[s]);
1932        assert_eq!(
1933            t.finish(root),
1934            Err(TemplateError::SpliceOutOfList { hole: 0 })
1935        );
1936    }
1937
1938    #[test]
1939    fn test_binder_bound_twice() {
1940        let mut t = TemplateBuilder::new("twice");
1941        let x = t.binder("x");
1942        let (p1, p2) = (t.bind(x), t.bind(x));
1943        let pair = t.tuple_pat(&[p1, p2]);
1944        let unit = t.tuple(&[]);
1945        let s = t.let_(pair, None, Some(unit));
1946        let root = t.block(&[s], None);
1947        assert_eq!(
1948            t.finish(root),
1949            Err(TemplateError::BinderBoundTwice { binder: 0 })
1950        );
1951    }
1952}