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.templates]` section writes as
4//! quasi-quoted HIR (`while = "loop { if ${cond} {} else { break }; ${body} }"`).
5//! Templates are built programmatically with a [`TemplateBuilder`], or parsed
6//! from that text with [`Template::parse`] (the `text` module, a pure front
7//! 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 {
341        key: u32,
342        value: u32,
343    },
344    YieldFrom(u32),
345    Spawn(u32),
346    Tuple(TList),
347    Array(TList),
348    Closure {
349        params: TList,
350        body: u32,
351        implicit: Option<CaptureMode>,
352    },
353    Apply {
354        template: u32,
355        args: TList,
356    },
357    LetPlace {
358        binder: u16,
359        place: u32,
360        body: u32,
361    },
362    // ---- statements
363    Let {
364        pat: u32,
365        ty: u32,
366        init: u32,
367    },
368    ExprStmt(u32),
369    Defer(u32),
370    Stmts(u16),
371    // ---- patterns
372    PHole(u16),
373    PWild,
374    PBind(u16),
375    PLit(TLit),
376    PTuple(TList),
377    PCtor {
378        path: u32,
379        elems: TList,
380    },
381    // ---- types
382    THole(u16),
383    TPrim(Prim),
384    TNamed(u32),
385    TInfer,
386    TAny,
387    TUnion(TList),
388    TInter(TList),
389}
390
391/// A declared hole.
392#[derive(Clone, Debug, PartialEq)]
393pub(crate) struct HoleDecl {
394    pub(crate) name: Box<str>,
395    pub(crate) kind: HoleKind,
396    pub(crate) optional: bool,
397    pub(crate) default: Option<TLit>,
398}
399
400/// A declared binder or label.
401#[derive(Clone, Copy, Debug, PartialEq, Eq)]
402pub(crate) struct BinderDecl {
403    pub(crate) name: u32,
404    pub(crate) mutable: bool,
405}
406
407/// A finished, checked lowering template.
408///
409/// Register it in a mapping with
410/// [`MappingBuilder::template`](crate::MappingBuilder::template), then use it
411/// for a node kind ([`template_node`](crate::MappingBuilder::template_node))
412/// or an operator ([`OpSpec::Template`](crate::OpSpec::Template)).
413///
414/// # Examples
415///
416/// ```
417/// use lower_lang::templates;
418///
419/// let t = templates::while_loop();
420/// assert_eq!(t.name(), "while");
421/// assert_eq!(t.hole_count(), 3);
422/// ```
423#[derive(Clone, Debug, PartialEq)]
424pub struct Template {
425    pub(crate) name: Box<str>,
426    pub(crate) kind: ExpnKind,
427    pub(crate) nodes: Vec<TNode>,
428    pub(crate) lists: Vec<u32>,
429    pub(crate) texts: Vec<Box<str>>,
430    pub(crate) holes: Vec<HoleDecl>,
431    pub(crate) binders: Vec<BinderDecl>,
432    pub(crate) labels: Vec<BinderDecl>,
433    pub(crate) args: Vec<TArg>,
434    pub(crate) applies: Vec<u32>,
435    pub(crate) root: u32,
436    /// Set when registered: where this template's texts start in the
437    /// mapping's string table.
438    pub(crate) text_base: u32,
439}
440
441impl Template {
442    /// The template's name (also the expansion's name in HIR origins).
443    ///
444    /// # Examples
445    ///
446    /// ```
447    /// assert_eq!(lower_lang::templates::do_while().name(), "do-while");
448    /// ```
449    #[must_use]
450    pub fn name(&self) -> &str {
451        &self.name
452    }
453
454    /// The expansion kind instantiations record (`Template` by default,
455    /// `Desugar` for the built-in desugarings).
456    ///
457    /// # Examples
458    ///
459    /// ```
460    /// use hir_lang::ExpnKind;
461    ///
462    /// assert_eq!(lower_lang::templates::while_loop().expansion_kind(), ExpnKind::Desugar);
463    /// ```
464    #[must_use]
465    pub const fn expansion_kind(&self) -> ExpnKind {
466        self.kind
467    }
468
469    /// The number of holes; a node that uses the template binds one pick per
470    /// hole, in this order.
471    ///
472    /// # Examples
473    ///
474    /// ```
475    /// assert_eq!(lower_lang::templates::c_for().hole_count(), 5);
476    /// ```
477    #[must_use]
478    pub fn hole_count(&self) -> usize {
479        self.holes.len()
480    }
481
482    /// Hole `index`: its name, kind, and whether it may be absent.
483    ///
484    /// # Examples
485    ///
486    /// ```
487    /// use lower_lang::HoleKind;
488    ///
489    /// let t = lower_lang::templates::while_loop();
490    /// assert_eq!(t.hole(0), Some(("cond", HoleKind::Expr, false)));
491    /// assert_eq!(t.hole(2), Some(("label", HoleKind::Label, true)));
492    /// assert_eq!(t.hole(3), None);
493    /// ```
494    #[must_use]
495    pub fn hole(&self, index: usize) -> Option<(&str, HoleKind, bool)> {
496        self.holes
497            .get(index)
498            .map(|h| (&*h.name, h.kind, h.optional))
499    }
500
501    /// Parses a template written in HIR's textual template syntax (HIR spec
502    /// §20, LSF2 §15.8): the lazy path for `[semantics.templates]` and
503    /// inline `[semantics.lower]` texts.
504    ///
505    /// Holes are `${name}` (its kind — expression, pattern, type, or label —
506    /// follows from where it is written), `${name?}` (optional),
507    /// `${name?=<literal>}` (optional with a default), and `${...name}` (an
508    /// argument-list splice in a call, tuple, or array, or a statement
509    /// splice in a block). Holes are numbered in order of first appearance.
510    /// Names bound with `let`, `let_place`, a pattern, or a closure parameter
511    /// are template binders, fresh and hygienic per instantiation; labels
512    /// (`'l loop { … }`) likewise. Free names are written `global:a::b`,
513    /// host symbols `extern:mox.echo`. Operations are written by their OPS
514    /// name: `add(a, b)` takes the language's policies, `add<overflow=wrap>(a,
515    /// b)` exactly the ones written. `apply:<name>(…)` needs templates
516    /// registered before this one: use
517    /// [`MappingBuilder::parse_template`](crate::MappingBuilder::parse_template)
518    /// for it. The full grammar is in `docs/API.md`.
519    ///
520    /// # Errors
521    ///
522    /// [`TemplateError::Syntax`] with the byte range and a
523    /// [`SyntaxError`](crate::SyntaxError) for any text that is not a valid
524    /// template (never a panic, at any length or depth); `TooLarge` when the
525    /// result outgrows the template tables.
526    ///
527    /// # Examples
528    ///
529    /// ```
530    /// use lower_lang::{HoleKind, Template};
531    ///
532    /// // PHP's `&&`, which returns a bool.
533    /// let and = Template::parse("bool_and", "if ${lhs} { not(not(${rhs})) } else { false }")?;
534    /// assert_eq!(and.hole(0), Some(("lhs", HoleKind::Expr, false)));
535    /// assert_eq!(and.hole(1), Some(("rhs", HoleKind::Expr, false)));
536    ///
537    /// // `++$i`, with the place evaluated once.
538    /// let inc = Template::parse("pre_increment", "let_place p = ${place} in p = add(p, 1)")?;
539    /// assert_eq!(inc.hole_count(), 1);
540    /// # Ok::<(), lower_lang::TemplateError>(())
541    /// ```
542    pub fn parse(name: &str, text: &str) -> Result<Self, TemplateError> {
543        crate::text::parse(name, text, None)
544    }
545
546    /// Records `Desugar` expansions instead of `Template` ones (LSF2's
547    /// `{ text = …, desugar = true }`), so tools can re-sugar the output.
548    ///
549    /// # Examples
550    ///
551    /// ```
552    /// use hir_lang::ExpnKind;
553    /// use lower_lang::Template;
554    ///
555    /// let t = Template::parse("echo", "extern:mox.echo(${...values})")?.desugar();
556    /// assert_eq!(t.expansion_kind(), ExpnKind::Desugar);
557    /// # Ok::<(), lower_lang::TemplateError>(())
558    /// ```
559    #[must_use]
560    pub fn desugar(mut self) -> Self {
561        self.kind = ExpnKind::Desugar;
562        self
563    }
564
565    /// The index of the hole named `name`, for binding node fields to holes
566    /// by name (LSF2: a hole missing from `holes` takes the node's field of
567    /// the same name).
568    ///
569    /// # Examples
570    ///
571    /// ```
572    /// use lower_lang::Template;
573    ///
574    /// let t = Template::parse("new_object", "extern:mox.new(${class}, ${...args})")?;
575    /// assert_eq!(t.hole_index("args"), Some(1));
576    /// assert_eq!(t.hole_index("nope"), None);
577    /// # Ok::<(), lower_lang::TemplateError>(())
578    /// ```
579    #[must_use]
580    pub fn hole_index(&self, name: &str) -> Option<usize> {
581        self.holes.iter().position(|h| &*h.name == name)
582    }
583
584    pub(crate) fn node(&self, index: u32) -> Option<&TNode> {
585        self.nodes.get(index as usize)
586    }
587
588    pub(crate) fn list(&self, list: TList) -> &[u32] {
589        let (start, len) = (list.0 as usize, list.1 as usize);
590        self.lists
591            .get(start..start.saturating_add(len))
592            .unwrap_or(&[])
593    }
594}
595
596/// Why a template was refused.
597///
598/// # Examples
599///
600/// ```
601/// use lower_lang::{TemplateBuilder, TemplateError};
602///
603/// let mut t = TemplateBuilder::new("unused");
604/// let _x = t.expr_hole("x");
605/// let root = t.lit(lower_lang::TLit::Null);
606/// assert_eq!(t.finish(root), Err(TemplateError::HoleUnused { hole: 0 }));
607/// ```
608#[derive(Clone, Copy, Debug, PartialEq, Eq)]
609#[non_exhaustive]
610pub enum TemplateError {
611    /// A declared hole is never used. Use it, or remove it (every hole must
612    /// receive its user code somewhere, or that code would be lost).
613    HoleUnused {
614        /// The hole's index.
615        hole: usize,
616    },
617    /// A binder is used but no pattern or closure parameter binds it.
618    BinderUnbound {
619        /// The binder's index.
620        binder: usize,
621    },
622    /// A binder is bound by two patterns or parameters. Declare one binder
623    /// per binding site.
624    BinderBoundTwice {
625        /// The binder's index.
626        binder: usize,
627    },
628    /// A label is jumped to but no loop or block defines it.
629    LabelUndefined {
630        /// The label's index.
631        label: usize,
632    },
633    /// A label is defined by two loops or blocks.
634    LabelDefinedTwice {
635        /// The label's index.
636        label: usize,
637    },
638    /// An argument-list hole is spliced somewhere other than a call's
639    /// arguments or a tuple's or array's elements.
640    SpliceOutOfList {
641        /// The hole's index.
642        hole: usize,
643    },
644    /// A handle from another template builder (or a list longer than the
645    /// arena) was used.
646    ForeignHandle,
647    /// The tree, counting shared sub-trees at every use, has more than
648    /// [`MAX_TEMPLATE_SIZE`] nodes, or a table outgrew its index type.
649    TooLarge,
650    /// A template text ([`Template::parse`]) is not valid template syntax:
651    /// what is wrong, and the byte range of the text it is about.
652    Syntax {
653        /// The offending bytes of the template text.
654        at: hir_lang::Span,
655        /// What is wrong there.
656        error: crate::SyntaxError,
657    },
658}
659
660impl fmt::Display for TemplateError {
661    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
662        match self {
663            Self::HoleUnused { hole } => write!(f, "hole {hole} is never used"),
664            Self::BinderUnbound { binder } => write!(f, "binder {binder} is used but never bound"),
665            Self::BinderBoundTwice { binder } => write!(f, "binder {binder} is bound twice"),
666            Self::LabelUndefined { label } => write!(f, "label {label} is used but never defined"),
667            Self::LabelDefinedTwice { label } => write!(f, "label {label} is defined twice"),
668            Self::SpliceOutOfList { hole } => {
669                write!(
670                    f,
671                    "argument hole {hole} is spliced outside an argument or element list"
672                )
673            }
674            Self::ForeignHandle => f.write_str("a handle from another template builder was used"),
675            Self::TooLarge => f.write_str("the template is too large"),
676            Self::Syntax { at, error } => write!(
677                f,
678                "template text, bytes {}..{}: {error}",
679                at.start().to_usize(),
680                at.end().to_usize()
681            ),
682        }
683    }
684}
685
686impl core::error::Error for TemplateError {}
687
688/// Builds a [`Template`] bottom-up, like hir-lang's `Builder` builds HIR.
689///
690/// Declare holes and binders, build nodes, then [`finish`](Self::finish) with
691/// the root expression. Every method is infallible; problems (a foreign
692/// handle, an unbound binder, an unused hole) are reported by `finish`.
693///
694/// # Examples
695///
696/// `unless cond { body }` as `if cond {} else { body }`:
697///
698/// ```
699/// use lower_lang::TemplateBuilder;
700///
701/// let mut t = TemplateBuilder::new("unless");
702/// let cond = t.expr_hole("cond");
703/// let body = t.expr_hole("body");
704/// let c = t.hole(cond);
705/// let empty = t.block(&[], None);
706/// let b = t.hole(body);
707/// let root = t.if_(c, empty, Some(b));
708/// let unless = t.finish(root)?;
709/// assert_eq!(unless.hole_count(), 2);
710/// # Ok::<(), lower_lang::TemplateError>(())
711/// ```
712#[derive(Clone, Debug)]
713pub struct TemplateBuilder {
714    pub(crate) t: Template,
715    overflow: bool,
716}
717
718impl TemplateBuilder {
719    /// An empty template named `name`, recording `Template` expansions.
720    ///
721    /// # Examples
722    ///
723    /// ```
724    /// let t = lower_lang::TemplateBuilder::new("swap");
725    /// let _ = t;
726    /// ```
727    #[must_use]
728    pub fn new(name: &str) -> Self {
729        Self {
730            t: Template {
731                name: name.into(),
732                kind: ExpnKind::Template,
733                nodes: Vec::new(),
734                lists: Vec::new(),
735                texts: Vec::new(),
736                holes: Vec::new(),
737                binders: Vec::new(),
738                labels: Vec::new(),
739                args: Vec::new(),
740                applies: Vec::new(),
741                root: NONE,
742                text_base: 0,
743            },
744            overflow: false,
745        }
746    }
747
748    /// Records `Desugar` expansions instead (for built-in sugar such as
749    /// `while`, so tools can re-sugar it).
750    ///
751    /// # Examples
752    ///
753    /// ```
754    /// use hir_lang::ExpnKind;
755    /// use lower_lang::{TLit, TemplateBuilder};
756    ///
757    /// let mut t = TemplateBuilder::new("nothing").desugar();
758    /// let root = t.lit(TLit::Null);
759    /// assert_eq!(t.finish(root)?.expansion_kind(), ExpnKind::Desugar);
760    /// # Ok::<(), lower_lang::TemplateError>(())
761    /// ```
762    #[must_use]
763    pub fn desugar(mut self) -> Self {
764        self.t.kind = ExpnKind::Desugar;
765        self
766    }
767
768    // ---------------------------------------------------------------- tables
769
770    fn push(&mut self, node: TNode) -> u32 {
771        match u32::try_from(self.t.nodes.len()) {
772            Ok(i) if i < NONE => {
773                self.t.nodes.push(node);
774                i
775            }
776            _ => {
777                self.overflow = true;
778                NONE
779            }
780        }
781    }
782
783    fn list(&mut self, items: impl IntoIterator<Item = u32>) -> TList {
784        let start = self.t.lists.len();
785        self.t.lists.extend(items);
786        match (
787            u32::try_from(start),
788            u32::try_from(self.t.lists.len() - start),
789        ) {
790            (Ok(s), Ok(l)) => (s, l),
791            _ => {
792                self.overflow = true;
793                (0, 0)
794            }
795        }
796    }
797
798    fn text(&mut self, text: &str) -> u32 {
799        let i = self.t.texts.len();
800        self.t.texts.push(text.into());
801        u32::try_from(i).unwrap_or_else(|_| {
802            self.overflow = true;
803            0
804        })
805    }
806
807    fn hole_decl(
808        &mut self,
809        name: &str,
810        kind: HoleKind,
811        optional: bool,
812        default: Option<TLit>,
813    ) -> u16 {
814        let i = self.t.holes.len();
815        self.t.holes.push(HoleDecl {
816            name: name.into(),
817            kind,
818            optional,
819            default,
820        });
821        u16::try_from(i).unwrap_or_else(|_| {
822            self.overflow = true;
823            0
824        })
825    }
826
827    fn opt(e: Option<TExpr>) -> u32 {
828        e.map_or(NONE, |e| e.0)
829    }
830
831    // ----------------------------------------------------------------- holes
832
833    /// Declares a required expression hole.
834    ///
835    /// # Examples
836    ///
837    /// ```
838    /// let mut t = lower_lang::TemplateBuilder::new("t");
839    /// let h = t.expr_hole("value");
840    /// let root = t.hole(h);
841    /// assert!(t.finish(root).is_ok());
842    /// ```
843    pub fn expr_hole(&mut self, name: &str) -> ExprHole {
844        ExprHole(self.hole_decl(name, HoleKind::Expr, false, None))
845    }
846
847    /// Declares an optional expression hole. When the field is absent the hole
848    /// is `default` if given; otherwise it is left out where the slot is
849    /// optional (an `else`, a loop step, a `return` value) and is an error
850    /// where a value is required.
851    ///
852    /// # Examples
853    ///
854    /// ```
855    /// use lower_lang::TLit;
856    ///
857    /// let mut t = lower_lang::TemplateBuilder::new("t");
858    /// let cond = t.optional_expr_hole("cond", Some(TLit::Bool(true)));
859    /// let root = t.hole(cond);
860    /// assert_eq!(t.finish(root)?.hole(0).map(|h| h.2), Some(true));
861    /// # Ok::<(), lower_lang::TemplateError>(())
862    /// ```
863    pub fn optional_expr_hole(&mut self, name: &str, default: Option<TLit>) -> ExprHole {
864        ExprHole(self.hole_decl(name, HoleKind::Expr, true, default))
865    }
866
867    /// Declares a pattern hole; an absent optional pattern is `_`.
868    ///
869    /// # Examples
870    ///
871    /// ```
872    /// let mut t = lower_lang::TemplateBuilder::new("t");
873    /// let p = t.pat_hole("pat", false);
874    /// let pat = t.pat(p);
875    /// let unit = t.tuple(&[]);
876    /// let s = t.let_(pat, None, Some(unit));
877    /// let root = t.block(&[s], None);
878    /// assert!(t.finish(root).is_ok());
879    /// ```
880    pub fn pat_hole(&mut self, name: &str, optional: bool) -> PatHole {
881        PatHole(self.hole_decl(name, HoleKind::Pat, optional, None))
882    }
883
884    /// Declares a type hole; an absent optional type is left out where the
885    /// slot is optional and is `_` (inferred) elsewhere.
886    ///
887    /// # Examples
888    ///
889    /// ```
890    /// let mut t = lower_lang::TemplateBuilder::new("t");
891    /// let ty = t.ty_hole("ty", true);
892    /// let x = t.binder("x");
893    /// let pat = t.bind(x);
894    /// let ann = t.ty(ty);
895    /// let s = t.let_(pat, Some(ann), None);
896    /// let root = t.block(&[s], None);
897    /// assert!(t.finish(root).is_ok());
898    /// ```
899    pub fn ty_hole(&mut self, name: &str, optional: bool) -> TyHole {
900        TyHole(self.hole_decl(name, HoleKind::Ty, optional, None))
901    }
902
903    /// Declares a statement-list hole (zero or more statements).
904    ///
905    /// # Examples
906    ///
907    /// ```
908    /// let mut t = lower_lang::TemplateBuilder::new("t");
909    /// let body = t.stmts_hole("body");
910    /// let s = t.stmts(body);
911    /// let root = t.block(&[s], None);
912    /// assert!(t.finish(root).is_ok());
913    /// ```
914    pub fn stmts_hole(&mut self, name: &str) -> StmtsHole {
915        StmtsHole(self.hole_decl(name, HoleKind::Stmts, true, None))
916    }
917
918    /// Declares an argument-list hole (zero or more arguments).
919    ///
920    /// # Examples
921    ///
922    /// ```
923    /// let mut t = lower_lang::TemplateBuilder::new("echo");
924    /// let args = t.args_hole("args");
925    /// let callee = t.extern_("echo");
926    /// let spliced = t.splice(args);
927    /// let root = t.call(callee, &[spliced]);
928    /// assert!(t.finish(root).is_ok());
929    /// ```
930    pub fn args_hole(&mut self, name: &str) -> ArgsHole {
931        ArgsHole(self.hole_decl(name, HoleKind::Args, true, None))
932    }
933
934    /// Declares a label hole: the user's label (optional) for a loop or block
935    /// the template creates.
936    ///
937    /// # Examples
938    ///
939    /// ```
940    /// use lower_lang::LabelRef;
941    ///
942    /// let mut t = lower_lang::TemplateBuilder::new("t");
943    /// let l = t.label_hole("label");
944    /// let body = t.block(&[], None);
945    /// let root = t.loop_(Some(LabelRef::Hole(l)), body, None);
946    /// assert!(t.finish(root).is_ok());
947    /// ```
948    pub fn label_hole(&mut self, name: &str) -> LabelHole {
949        LabelHole(self.hole_decl(name, HoleKind::Label, true, None))
950    }
951
952    // -------------------------------------------------------- binders, labels
953
954    /// Declares an immutable local binder (hygienic: fresh per instantiation).
955    ///
956    /// # Examples
957    ///
958    /// ```
959    /// let mut t = lower_lang::TemplateBuilder::new("t");
960    /// let tmp = t.binder("tmp");
961    /// let pat = t.bind(tmp);
962    /// let one = t.lit(lower_lang::TLit::Int(1));
963    /// let s = t.let_(pat, None, Some(one));
964    /// let use_tmp = t.var(tmp);
965    /// let root = t.block(&[s], Some(use_tmp));
966    /// assert!(t.finish(root).is_ok());
967    /// ```
968    pub fn binder(&mut self, name: &str) -> TBinder {
969        self.binder_decl(name, false)
970    }
971
972    /// Declares a mutable local binder.
973    ///
974    /// # Examples
975    ///
976    /// ```
977    /// let mut t = lower_lang::TemplateBuilder::new("t");
978    /// let n = t.mutable_binder("n");
979    /// let pat = t.bind(n);
980    /// let zero = t.lit(lower_lang::TLit::Int(0));
981    /// let s = t.let_(pat, None, Some(zero));
982    /// let root = t.block(&[s], None);
983    /// assert!(t.finish(root).is_ok());
984    /// ```
985    pub fn mutable_binder(&mut self, name: &str) -> TBinder {
986        self.binder_decl(name, true)
987    }
988
989    fn binder_decl(&mut self, name: &str, mutable: bool) -> TBinder {
990        let name = self.text(name);
991        let i = self.t.binders.len();
992        self.t.binders.push(BinderDecl { name, mutable });
993        TBinder(u16::try_from(i).unwrap_or_else(|_| {
994            self.overflow = true;
995            0
996        }))
997    }
998
999    /// Declares a label the template defines on one of its loops or blocks.
1000    ///
1001    /// # Examples
1002    ///
1003    /// ```
1004    /// use lower_lang::LabelRef;
1005    ///
1006    /// let mut t = lower_lang::TemplateBuilder::new("t");
1007    /// let l = t.label("outer");
1008    /// let brk = t.break_(Some(LabelRef::Own(l)), None);
1009    /// let root = t.loop_(Some(LabelRef::Own(l)), brk, None);
1010    /// assert!(t.finish(root).is_ok());
1011    /// ```
1012    pub fn label(&mut self, name: &str) -> TLabel {
1013        let name = self.text(name);
1014        let i = self.t.labels.len();
1015        self.t.labels.push(BinderDecl {
1016            name,
1017            mutable: false,
1018        });
1019        TLabel(u16::try_from(i).unwrap_or_else(|_| {
1020            self.overflow = true;
1021            0
1022        }))
1023    }
1024
1025    // ----------------------------------------------------------- expressions
1026
1027    /// The value of an expression hole.
1028    ///
1029    /// # Examples
1030    ///
1031    /// ```
1032    /// let mut t = lower_lang::TemplateBuilder::new("t");
1033    /// let h = t.expr_hole("e");
1034    /// let e = t.hole(h);
1035    /// assert!(t.finish(e).is_ok());
1036    /// ```
1037    pub fn hole(&mut self, hole: ExprHole) -> TExpr {
1038        TExpr(self.push(TNode::Hole(hole.0)))
1039    }
1040
1041    /// The arguments of an argument-list hole, spliced in place; only valid
1042    /// directly in [`call`](Self::call), [`method`](Self::method),
1043    /// [`tuple`](Self::tuple), or [`array`](Self::array) lists.
1044    ///
1045    /// # Examples
1046    ///
1047    /// ```
1048    /// let mut t = lower_lang::TemplateBuilder::new("t");
1049    /// let args = t.args_hole("args");
1050    /// let items = t.splice(args);
1051    /// let root = t.array(&[items]);
1052    /// assert!(t.finish(root).is_ok());
1053    /// ```
1054    pub fn splice(&mut self, hole: ArgsHole) -> TExpr {
1055        TExpr(self.push(TNode::Splice(hole.0)))
1056    }
1057
1058    /// A literal.
1059    ///
1060    /// # Examples
1061    ///
1062    /// ```
1063    /// let mut t = lower_lang::TemplateBuilder::new("t");
1064    /// let root = t.lit(lower_lang::TLit::Float(0.5));
1065    /// assert!(t.finish(root).is_ok());
1066    /// ```
1067    pub fn lit(&mut self, lit: TLit) -> TExpr {
1068        TExpr(self.push(TNode::Lit(lit)))
1069    }
1070
1071    /// A string literal.
1072    ///
1073    /// # Examples
1074    ///
1075    /// ```
1076    /// let mut t = lower_lang::TemplateBuilder::new("t");
1077    /// let root = t.str("done");
1078    /// assert!(t.finish(root).is_ok());
1079    /// ```
1080    pub fn str(&mut self, text: &str) -> TExpr {
1081        let s = self.text(text);
1082        TExpr(self.push(TNode::Str(s)))
1083    }
1084
1085    /// A reference to one of the template's binders, resolved by
1086    /// construction.
1087    ///
1088    /// # Examples
1089    ///
1090    /// See [`binder`](Self::binder).
1091    pub fn var(&mut self, binder: TBinder) -> TExpr {
1092        TExpr(self.push(TNode::Var(binder.0)))
1093    }
1094
1095    /// A free name the template refers to (`iter`, `std::mem::swap`), split
1096    /// at `::`. It carries the expansion's hygiene mark, so a user variable of
1097    /// the same spelling cannot capture it; a resolver looks it up at the
1098    /// template's definition site.
1099    ///
1100    /// # Examples
1101    ///
1102    /// ```
1103    /// let mut t = lower_lang::TemplateBuilder::new("t");
1104    /// let f = t.global("core::mem::take");
1105    /// let root = t.call(f, &[]);
1106    /// assert!(t.finish(root).is_ok());
1107    /// ```
1108    pub fn global(&mut self, path: &str) -> TExpr {
1109        let s = self.text(path);
1110        TExpr(self.push(TNode::Global(s)))
1111    }
1112
1113    /// A host symbol (`[stdlib]`), already resolved to `Res::Extern`.
1114    ///
1115    /// # Examples
1116    ///
1117    /// ```
1118    /// let mut t = lower_lang::TemplateBuilder::new("t");
1119    /// let f = t.extern_("mox.iter");
1120    /// let root = t.call(f, &[]);
1121    /// assert!(t.finish(root).is_ok());
1122    /// ```
1123    pub fn extern_(&mut self, name: &str) -> TExpr {
1124        let s = self.text(name);
1125        TExpr(self.push(TNode::Extern(s)))
1126    }
1127
1128    /// `callee(args)`.
1129    ///
1130    /// # Examples
1131    ///
1132    /// See [`extern_`](Self::extern_).
1133    pub fn call(&mut self, callee: TExpr, args: &[TExpr]) -> TExpr {
1134        let args = self.list(args.iter().map(|a| a.0));
1135        TExpr(self.push(TNode::Call {
1136            callee: callee.0,
1137            args,
1138        }))
1139    }
1140
1141    /// `recv.name(args)`.
1142    ///
1143    /// # Examples
1144    ///
1145    /// ```
1146    /// let mut t = lower_lang::TemplateBuilder::new("t");
1147    /// let h = t.expr_hole("it");
1148    /// let it = t.hole(h);
1149    /// let root = t.method(it, "next", &[]);
1150    /// assert!(t.finish(root).is_ok());
1151    /// ```
1152    pub fn method(&mut self, recv: TExpr, name: &str, args: &[TExpr]) -> TExpr {
1153        let name = self.text(name);
1154        let args = self.list(args.iter().map(|a| a.0));
1155        TExpr(self.push(TNode::Method {
1156            recv: recv.0,
1157            name,
1158            args,
1159        }))
1160    }
1161
1162    /// `base.name`.
1163    ///
1164    /// # Examples
1165    ///
1166    /// ```
1167    /// let mut t = lower_lang::TemplateBuilder::new("t");
1168    /// let h = t.expr_hole("e");
1169    /// let e = t.hole(h);
1170    /// let root = t.field(e, "len");
1171    /// assert!(t.finish(root).is_ok());
1172    /// ```
1173    pub fn field(&mut self, base: TExpr, name: &str) -> TExpr {
1174        let name = self.text(name);
1175        TExpr(self.push(TNode::Field { base: base.0, name }))
1176    }
1177
1178    /// `base[index]`.
1179    ///
1180    /// # Examples
1181    ///
1182    /// ```
1183    /// use lower_lang::TLit;
1184    ///
1185    /// let mut t = lower_lang::TemplateBuilder::new("t");
1186    /// let h = t.expr_hole("e");
1187    /// let e = t.hole(h);
1188    /// let zero = t.lit(TLit::Int(0));
1189    /// let root = t.index(e, zero);
1190    /// assert!(t.finish(root).is_ok());
1191    /// ```
1192    pub fn index(&mut self, base: TExpr, index: TExpr) -> TExpr {
1193        TExpr(self.push(TNode::Index {
1194            base: base.0,
1195            index: index.0,
1196        }))
1197    }
1198
1199    /// An intrinsic operation with the language's policies (from the
1200    /// mapping's [`LangPolicy`](crate::LangPolicy)).
1201    ///
1202    /// # Examples
1203    ///
1204    /// ```
1205    /// use hir_lang::OpKind;
1206    ///
1207    /// let mut t = lower_lang::TemplateBuilder::new("not");
1208    /// let h = t.expr_hole("e");
1209    /// let e = t.hole(h);
1210    /// let root = t.op(OpKind::Not, &[e]);
1211    /// assert!(t.finish(root).is_ok());
1212    /// ```
1213    pub fn op(&mut self, kind: OpKind, args: &[TExpr]) -> TExpr {
1214        let args = self.list(args.iter().map(|a| a.0));
1215        TExpr(self.push(TNode::Op {
1216            op: Op::new(kind),
1217            exact: false,
1218            args,
1219        }))
1220    }
1221
1222    /// An intrinsic operation with exactly this policy.
1223    ///
1224    /// # Examples
1225    ///
1226    /// ```
1227    /// use hir_lang::{Op, OpKind, Overflow};
1228    ///
1229    /// let mut t = lower_lang::TemplateBuilder::new("inc");
1230    /// let h = t.expr_hole("e");
1231    /// let e = t.hole(h);
1232    /// let one = t.lit(lower_lang::TLit::Int(1));
1233    /// let root = t.op_with(Op::new(OpKind::Add).with_overflow(Overflow::Wrap), &[e, one]);
1234    /// assert!(t.finish(root).is_ok());
1235    /// ```
1236    pub fn op_with(&mut self, op: Op, args: &[TExpr]) -> TExpr {
1237        let args = self.list(args.iter().map(|a| a.0));
1238        TExpr(self.push(TNode::Op {
1239            op,
1240            exact: true,
1241            args,
1242        }))
1243    }
1244
1245    /// `target = value`.
1246    ///
1247    /// # Examples
1248    ///
1249    /// ```
1250    /// let mut t = lower_lang::TemplateBuilder::new("t");
1251    /// let p = t.expr_hole("place");
1252    /// let v = t.expr_hole("value");
1253    /// let (p, v) = (t.hole(p), t.hole(v));
1254    /// let root = t.assign(p, v);
1255    /// assert!(t.finish(root).is_ok());
1256    /// ```
1257    pub fn assign(&mut self, target: TExpr, value: TExpr) -> TExpr {
1258        TExpr(self.push(TNode::Assign {
1259            target: target.0,
1260            value: value.0,
1261        }))
1262    }
1263
1264    /// `{ stmts; tail }`.
1265    ///
1266    /// # Examples
1267    ///
1268    /// ```
1269    /// let mut t = lower_lang::TemplateBuilder::new("t");
1270    /// let root = t.block(&[], None);
1271    /// assert!(t.finish(root).is_ok());
1272    /// ```
1273    pub fn block(&mut self, stmts: &[TStmt], tail: Option<TExpr>) -> TExpr {
1274        let stmts = self.list(stmts.iter().map(|s| s.0));
1275        TExpr(self.push(TNode::Block {
1276            stmts,
1277            tail: Self::opt(tail),
1278            label: LabelSlot::None,
1279        }))
1280    }
1281
1282    /// `'label: { stmts; tail }`.
1283    ///
1284    /// # Examples
1285    ///
1286    /// ```
1287    /// use lower_lang::LabelRef;
1288    ///
1289    /// let mut t = lower_lang::TemplateBuilder::new("t");
1290    /// let l = t.label("done");
1291    /// let brk = t.break_(Some(LabelRef::Own(l)), None);
1292    /// let s = t.expr_stmt(brk);
1293    /// let root = t.labeled_block(LabelRef::Own(l), &[s], None);
1294    /// assert!(t.finish(root).is_ok());
1295    /// ```
1296    pub fn labeled_block(
1297        &mut self,
1298        label: LabelRef,
1299        stmts: &[TStmt],
1300        tail: Option<TExpr>,
1301    ) -> TExpr {
1302        let stmts = self.list(stmts.iter().map(|s| s.0));
1303        TExpr(self.push(TNode::Block {
1304            stmts,
1305            tail: Self::opt(tail),
1306            label: LabelSlot::of(Some(label)),
1307        }))
1308    }
1309
1310    /// `if cond { then } else { else_ }`.
1311    ///
1312    /// # Examples
1313    ///
1314    /// See [`TemplateBuilder`].
1315    pub fn if_(&mut self, cond: TExpr, then: TExpr, else_: Option<TExpr>) -> TExpr {
1316        TExpr(self.push(TNode::If {
1317            cond: cond.0,
1318            then: then.0,
1319            else_: Self::opt(else_),
1320        }))
1321    }
1322
1323    /// `match scrutinee { pat if guard => body, ... }`.
1324    ///
1325    /// # Examples
1326    ///
1327    /// ```
1328    /// use lower_lang::TLit;
1329    ///
1330    /// let mut t = lower_lang::TemplateBuilder::new("t");
1331    /// let h = t.expr_hole("e");
1332    /// let e = t.hole(h);
1333    /// let null = t.lit_pat(TLit::Null);
1334    /// let zero = t.lit(TLit::Int(0));
1335    /// let wild = t.wild();
1336    /// let one = t.lit(TLit::Int(1));
1337    /// let root = t.match_(e, &[(null, None, zero), (wild, None, one)]);
1338    /// assert!(t.finish(root).is_ok());
1339    /// ```
1340    pub fn match_(&mut self, scrutinee: TExpr, arms: &[(TPat, Option<TExpr>, TExpr)]) -> TExpr {
1341        let arms = self.list(arms.iter().flat_map(|(p, g, b)| [p.0, Self::opt(*g), b.0]));
1342        TExpr(self.push(TNode::Match {
1343            scrutinee: scrutinee.0,
1344            arms,
1345        }))
1346    }
1347
1348    /// `'label: loop { body } [step]` — HIR's one loop.
1349    ///
1350    /// # Examples
1351    ///
1352    /// See [`label_hole`](Self::label_hole).
1353    pub fn loop_(&mut self, label: Option<LabelRef>, body: TExpr, step: Option<TExpr>) -> TExpr {
1354        TExpr(self.push(TNode::Loop {
1355            label: LabelSlot::of(label),
1356            body: body.0,
1357            step: Self::opt(step),
1358        }))
1359    }
1360
1361    /// `break 'label value`.
1362    ///
1363    /// # Examples
1364    ///
1365    /// See [`label`](Self::label).
1366    pub fn break_(&mut self, label: Option<LabelRef>, value: Option<TExpr>) -> TExpr {
1367        TExpr(self.push(TNode::Break {
1368            label: LabelSlot::of(label),
1369            value: Self::opt(value),
1370        }))
1371    }
1372
1373    /// `continue 'label`.
1374    ///
1375    /// # Examples
1376    ///
1377    /// ```
1378    /// let mut t = lower_lang::TemplateBuilder::new("t");
1379    /// let c = t.continue_(None);
1380    /// let root = t.loop_(None, c, None);
1381    /// assert!(t.finish(root).is_ok());
1382    /// ```
1383    pub fn continue_(&mut self, label: Option<LabelRef>) -> TExpr {
1384        TExpr(self.push(TNode::Continue {
1385            label: LabelSlot::of(label),
1386        }))
1387    }
1388
1389    /// `return value`.
1390    ///
1391    /// # Examples
1392    ///
1393    /// ```
1394    /// let mut t = lower_lang::TemplateBuilder::new("t");
1395    /// let root = t.return_(None);
1396    /// assert!(t.finish(root).is_ok());
1397    /// ```
1398    pub fn return_(&mut self, value: Option<TExpr>) -> TExpr {
1399        TExpr(self.push(TNode::Return(Self::opt(value))))
1400    }
1401
1402    /// `throw value`.
1403    ///
1404    /// # Examples
1405    ///
1406    /// ```
1407    /// let mut t = lower_lang::TemplateBuilder::new("t");
1408    /// let h = t.expr_hole("e");
1409    /// let e = t.hole(h);
1410    /// let root = t.throw(e);
1411    /// assert!(t.finish(root).is_ok());
1412    /// ```
1413    pub fn throw(&mut self, value: TExpr) -> TExpr {
1414        TExpr(self.push(TNode::Throw(value.0)))
1415    }
1416
1417    /// `await value`.
1418    ///
1419    /// # Examples
1420    ///
1421    /// ```
1422    /// let mut t = lower_lang::TemplateBuilder::new("t");
1423    /// let h = t.expr_hole("e");
1424    /// let e = t.hole(h);
1425    /// let root = t.await_(e);
1426    /// assert!(t.finish(root).is_ok());
1427    /// ```
1428    pub fn await_(&mut self, value: TExpr) -> TExpr {
1429        TExpr(self.push(TNode::Await(value.0)))
1430    }
1431
1432    /// `yield value`.
1433    ///
1434    /// # Examples
1435    ///
1436    /// ```
1437    /// let mut t = lower_lang::TemplateBuilder::new("t");
1438    /// let root = t.yield_(None);
1439    /// assert!(t.finish(root).is_ok());
1440    /// ```
1441    pub fn yield_(&mut self, value: Option<TExpr>) -> TExpr {
1442        TExpr(self.push(TNode::Yield {
1443            key: NONE,
1444            value: Self::opt(value),
1445        }))
1446    }
1447
1448    /// `yield key => value`: a keyed yield (PHP and Mox generators), HIR
1449    /// `Yield { key, value }`.
1450    ///
1451    /// # Examples
1452    ///
1453    /// ```
1454    /// let mut t = lower_lang::TemplateBuilder::new("pair");
1455    /// let (k, v) = (t.expr_hole("key"), t.expr_hole("value"));
1456    /// let (k, v) = (t.hole(k), t.hole(v));
1457    /// let root = t.yield_kv(k, v);
1458    /// assert!(t.finish(root).is_ok());
1459    /// ```
1460    pub fn yield_kv(&mut self, key: TExpr, value: TExpr) -> TExpr {
1461        TExpr(self.push(TNode::Yield {
1462            key: key.0,
1463            value: value.0,
1464        }))
1465    }
1466
1467    /// `yield from source`: delegate to an inner generator or iterable; the
1468    /// expression's value is the inner generator's return value (HIR
1469    /// `YieldFrom`).
1470    ///
1471    /// # Examples
1472    ///
1473    /// ```
1474    /// let mut t = lower_lang::TemplateBuilder::new("delegate");
1475    /// let h = t.expr_hole("from");
1476    /// let source = t.hole(h);
1477    /// let root = t.yield_from(source);
1478    /// assert!(t.finish(root).is_ok());
1479    /// ```
1480    pub fn yield_from(&mut self, source: TExpr) -> TExpr {
1481        TExpr(self.push(TNode::YieldFrom(source.0)))
1482    }
1483
1484    /// `spawn callable`.
1485    ///
1486    /// # Examples
1487    ///
1488    /// ```
1489    /// let mut t = lower_lang::TemplateBuilder::new("t");
1490    /// let h = t.expr_hole("f");
1491    /// let f = t.hole(h);
1492    /// let root = t.spawn(f);
1493    /// assert!(t.finish(root).is_ok());
1494    /// ```
1495    pub fn spawn(&mut self, callable: TExpr) -> TExpr {
1496        TExpr(self.push(TNode::Spawn(callable.0)))
1497    }
1498
1499    /// `(elems)`; `()` is unit.
1500    ///
1501    /// # Examples
1502    ///
1503    /// ```
1504    /// let mut t = lower_lang::TemplateBuilder::new("t");
1505    /// let root = t.tuple(&[]);
1506    /// assert!(t.finish(root).is_ok());
1507    /// ```
1508    pub fn tuple(&mut self, elems: &[TExpr]) -> TExpr {
1509        let elems = self.list(elems.iter().map(|e| e.0));
1510        TExpr(self.push(TNode::Tuple(elems)))
1511    }
1512
1513    /// `[elems]`.
1514    ///
1515    /// # Examples
1516    ///
1517    /// See [`splice`](Self::splice).
1518    pub fn array(&mut self, elems: &[TExpr]) -> TExpr {
1519        let elems = self.list(elems.iter().map(|e| e.0));
1520        TExpr(self.push(TNode::Array(elems)))
1521    }
1522
1523    /// A closure with the given parameters (each binds one of the template's
1524    /// binders) and implicit-capture mode.
1525    ///
1526    /// # Examples
1527    ///
1528    /// ```
1529    /// use hir_lang::CaptureMode;
1530    ///
1531    /// let mut t = lower_lang::TemplateBuilder::new("thunk");
1532    /// let h = t.expr_hole("e");
1533    /// let e = t.hole(h);
1534    /// let root = t.closure(&[], e, Some(CaptureMode::ByRef));
1535    /// assert!(t.finish(root).is_ok());
1536    /// ```
1537    pub fn closure(
1538        &mut self,
1539        params: &[TBinder],
1540        body: TExpr,
1541        implicit: Option<CaptureMode>,
1542    ) -> TExpr {
1543        let params = self.list(params.iter().map(|p| u32::from(p.0)));
1544        TExpr(self.push(TNode::Closure {
1545            params,
1546            body: body.0,
1547            implicit,
1548        }))
1549    }
1550
1551    /// Instantiates another template here, one argument per hole of the
1552    /// applied template. The template must be registered in the same mapping
1553    /// before this one, so templates can never apply themselves; checked by
1554    /// [`MappingBuilder::template`](crate::MappingBuilder::template). Each
1555    /// application is a nested expansion, counted against
1556    /// [`Budget::max_expansion_depth`](crate::Budget).
1557    ///
1558    /// # Examples
1559    ///
1560    /// ```
1561    /// use hir_lang::OpKind;
1562    /// use lower_lang::{templates, MappingBuilder, TArg, TemplateBuilder};
1563    ///
1564    /// let mut m = MappingBuilder::<u8>::new();
1565    /// let while_loop = m.template(templates::while_loop())?;
1566    /// // until c { b }  ==  while !c { b }
1567    /// let mut t = TemplateBuilder::new("until");
1568    /// let (c, b) = (t.expr_hole("cond"), t.expr_hole("body"));
1569    /// let c = t.hole(c);
1570    /// let not_c = t.op(OpKind::Not, &[c]);
1571    /// let b = t.hole(b);
1572    /// let root = t.apply(while_loop, &[TArg::Expr(not_c), TArg::Expr(b), TArg::Absent]);
1573    /// let until = t.finish(root).expect("valid");
1574    /// assert!(m.template(until).is_ok());
1575    /// # Ok::<(), lower_lang::MappingError>(())
1576    /// ```
1577    pub fn apply(&mut self, template: TemplateId, args: &[TArg]) -> TExpr {
1578        let start = self.t.args.len();
1579        self.t.args.extend_from_slice(args);
1580        let list = match (u32::try_from(start), u32::try_from(args.len())) {
1581            (Ok(s), Ok(l)) => (s, l),
1582            _ => {
1583                self.overflow = true;
1584                (0, 0)
1585            }
1586        };
1587        TExpr(self.push(TNode::Apply {
1588            template: template.0,
1589            args: list,
1590        }))
1591    }
1592
1593    /// `let_place binder = place in body`: evaluates the operands of the place
1594    /// expression `place` once and makes `binder` name that place in `body`,
1595    /// for reads and writes (HIR `LetPlace`, binder kind `Place`). This is how
1596    /// `++`, `--`, and compound assignments with a non-OPS operator evaluate
1597    /// their place exactly once. The binder is bound here and must not be
1598    /// bound anywhere else; HIR forbids capturing it in a closure.
1599    ///
1600    /// # Examples
1601    ///
1602    /// `++place` with the place evaluated once:
1603    ///
1604    /// ```
1605    /// use hir_lang::OpKind;
1606    /// use lower_lang::{TLit, TemplateBuilder};
1607    ///
1608    /// let mut t = TemplateBuilder::new("pre++");
1609    /// let place = t.expr_hole("place");
1610    /// let p = t.binder("p");
1611    /// let target = t.hole(place);
1612    /// let read = t.var(p);
1613    /// let one = t.lit(TLit::Int(1));
1614    /// let sum = t.op(OpKind::Add, &[read, one]);
1615    /// let write = t.var(p);
1616    /// let body = t.assign(write, sum);
1617    /// let root = t.let_place(p, target, body);
1618    /// assert!(t.finish(root).is_ok());
1619    /// ```
1620    pub fn let_place(&mut self, binder: TBinder, place: TExpr, body: TExpr) -> TExpr {
1621        TExpr(self.push(TNode::LetPlace {
1622            binder: binder.0,
1623            place: place.0,
1624            body: body.0,
1625        }))
1626    }
1627
1628    // ------------------------------------------------------------ statements
1629
1630    /// `let pat: ty = init;`
1631    ///
1632    /// # Examples
1633    ///
1634    /// See [`binder`](Self::binder).
1635    pub fn let_(&mut self, pat: TPat, ty: Option<TTy>, init: Option<TExpr>) -> TStmt {
1636        TStmt(self.push(TNode::Let {
1637            pat: pat.0,
1638            ty: ty.map_or(NONE, |t| t.0),
1639            init: Self::opt(init),
1640        }))
1641    }
1642
1643    /// `expr;`
1644    ///
1645    /// # Examples
1646    ///
1647    /// See [`labeled_block`](Self::labeled_block).
1648    pub fn expr_stmt(&mut self, expr: TExpr) -> TStmt {
1649        TStmt(self.push(TNode::ExprStmt(expr.0)))
1650    }
1651
1652    /// `defer expr;`
1653    ///
1654    /// # Examples
1655    ///
1656    /// ```
1657    /// let mut t = lower_lang::TemplateBuilder::new("t");
1658    /// let h = t.expr_hole("cleanup");
1659    /// let e = t.hole(h);
1660    /// let s = t.defer(e);
1661    /// let root = t.block(&[s], None);
1662    /// assert!(t.finish(root).is_ok());
1663    /// ```
1664    pub fn defer(&mut self, expr: TExpr) -> TStmt {
1665        TStmt(self.push(TNode::Defer(expr.0)))
1666    }
1667
1668    /// The statements of a statement-list hole, spliced into the block.
1669    ///
1670    /// # Examples
1671    ///
1672    /// See [`stmts_hole`](Self::stmts_hole).
1673    pub fn stmts(&mut self, hole: StmtsHole) -> TStmt {
1674        TStmt(self.push(TNode::Stmts(hole.0)))
1675    }
1676
1677    // -------------------------------------------------------------- patterns
1678
1679    /// The pattern of a pattern hole.
1680    ///
1681    /// # Examples
1682    ///
1683    /// See [`pat_hole`](Self::pat_hole).
1684    pub fn pat(&mut self, hole: PatHole) -> TPat {
1685        TPat(self.push(TNode::PHole(hole.0)))
1686    }
1687
1688    /// `_`.
1689    ///
1690    /// # Examples
1691    ///
1692    /// See [`match_`](Self::match_).
1693    pub fn wild(&mut self) -> TPat {
1694        TPat(self.push(TNode::PWild))
1695    }
1696
1697    /// Binds one of the template's binders (by value).
1698    ///
1699    /// # Examples
1700    ///
1701    /// See [`binder`](Self::binder).
1702    pub fn bind(&mut self, binder: TBinder) -> TPat {
1703        TPat(self.push(TNode::PBind(binder.0)))
1704    }
1705
1706    /// Matches a literal.
1707    ///
1708    /// # Examples
1709    ///
1710    /// See [`match_`](Self::match_).
1711    pub fn lit_pat(&mut self, lit: TLit) -> TPat {
1712        TPat(self.push(TNode::PLit(lit)))
1713    }
1714
1715    /// `(elems)`.
1716    ///
1717    /// # Examples
1718    ///
1719    /// ```
1720    /// let mut t = lower_lang::TemplateBuilder::new("t");
1721    /// let k = t.pat_hole("key", true);
1722    /// let v = t.pat_hole("value", false);
1723    /// let (k, v) = (t.pat(k), t.pat(v));
1724    /// let pair = t.tuple_pat(&[k, v]);
1725    /// let unit = t.tuple(&[]);
1726    /// let s = t.let_(pair, None, Some(unit));
1727    /// let root = t.block(&[s], None);
1728    /// assert!(t.finish(root).is_ok());
1729    /// ```
1730    pub fn tuple_pat(&mut self, elems: &[TPat]) -> TPat {
1731        let elems = self.list(elems.iter().map(|p| p.0));
1732        TPat(self.push(TNode::PTuple(elems)))
1733    }
1734
1735    /// `Path(elems)`, the path written like [`global`](Self::global).
1736    ///
1737    /// # Examples
1738    ///
1739    /// ```
1740    /// let mut t = lower_lang::TemplateBuilder::new("t");
1741    /// let h = t.expr_hole("e");
1742    /// let e = t.hole(h);
1743    /// let v = t.binder("v");
1744    /// let bind = t.bind(v);
1745    /// let some = t.ctor_pat("Some", &[bind]);
1746    /// let use_v = t.var(v);
1747    /// let wild = t.wild();
1748    /// let zero = t.lit(lower_lang::TLit::Int(0));
1749    /// let root = t.match_(e, &[(some, None, use_v), (wild, None, zero)]);
1750    /// assert!(t.finish(root).is_ok());
1751    /// ```
1752    pub fn ctor_pat(&mut self, path: &str, elems: &[TPat]) -> TPat {
1753        let path = self.text(path);
1754        let elems = self.list(elems.iter().map(|p| p.0));
1755        TPat(self.push(TNode::PCtor { path, elems }))
1756    }
1757
1758    // ----------------------------------------------------------------- types
1759
1760    /// The type of a type hole.
1761    ///
1762    /// # Examples
1763    ///
1764    /// See [`ty_hole`](Self::ty_hole).
1765    pub fn ty(&mut self, hole: TyHole) -> TTy {
1766        TTy(self.push(TNode::THole(hole.0)))
1767    }
1768
1769    /// A primitive type.
1770    ///
1771    /// # Examples
1772    ///
1773    /// ```
1774    /// use hir_lang::Prim;
1775    ///
1776    /// let mut t = lower_lang::TemplateBuilder::new("t");
1777    /// let x = t.binder("x");
1778    /// let p = t.bind(x);
1779    /// let int = t.prim(Prim::I64);
1780    /// let s = t.let_(p, Some(int), None);
1781    /// let root = t.block(&[s], None);
1782    /// assert!(t.finish(root).is_ok());
1783    /// ```
1784    pub fn prim(&mut self, prim: Prim) -> TTy {
1785        TTy(self.push(TNode::TPrim(prim)))
1786    }
1787
1788    /// A named type, written like [`global`](Self::global).
1789    ///
1790    /// # Examples
1791    ///
1792    /// ```
1793    /// let mut t = lower_lang::TemplateBuilder::new("t");
1794    /// let x = t.binder("x");
1795    /// let p = t.bind(x);
1796    /// let ty = t.named_ty("Iterator");
1797    /// let s = t.let_(p, Some(ty), None);
1798    /// let root = t.block(&[s], None);
1799    /// assert!(t.finish(root).is_ok());
1800    /// ```
1801    pub fn named_ty(&mut self, path: &str) -> TTy {
1802        let path = self.text(path);
1803        TTy(self.push(TNode::TNamed(path)))
1804    }
1805
1806    /// `_`: a type to infer.
1807    ///
1808    /// # Examples
1809    ///
1810    /// ```
1811    /// let mut t = lower_lang::TemplateBuilder::new("t");
1812    /// let x = t.binder("x");
1813    /// let p = t.bind(x);
1814    /// let ty = t.infer_ty();
1815    /// let s = t.let_(p, Some(ty), None);
1816    /// let root = t.block(&[s], None);
1817    /// assert!(t.finish(root).is_ok());
1818    /// ```
1819    pub fn infer_ty(&mut self) -> TTy {
1820        TTy(self.push(TNode::TInfer))
1821    }
1822
1823    /// The gradual dynamic type.
1824    ///
1825    /// # Examples
1826    ///
1827    /// ```
1828    /// let mut t = lower_lang::TemplateBuilder::new("t");
1829    /// let x = t.binder("x");
1830    /// let p = t.bind(x);
1831    /// let ty = t.any_ty();
1832    /// let s = t.let_(p, Some(ty), None);
1833    /// let root = t.block(&[s], None);
1834    /// assert!(t.finish(root).is_ok());
1835    /// ```
1836    pub fn any_ty(&mut self) -> TTy {
1837        TTy(self.push(TNode::TAny))
1838    }
1839
1840    /// A union type `A | B` (HIR `Ty::Union`). Members are kept in the order
1841    /// given; hir-lang's `finish` puts them in canonical form (flattened,
1842    /// sorted, repeats dropped, a single member collapsed).
1843    ///
1844    /// # Examples
1845    ///
1846    /// ```
1847    /// use hir_lang::Prim;
1848    ///
1849    /// let mut t = lower_lang::TemplateBuilder::new("t");
1850    /// let x = t.binder("x");
1851    /// let p = t.bind(x);
1852    /// let (int, string) = (t.prim(Prim::I64), t.prim(Prim::Str));
1853    /// let ty = t.union_ty(&[int, string]);
1854    /// let s = t.let_(p, Some(ty), None);
1855    /// let root = t.block(&[s], None);
1856    /// assert!(t.finish(root).is_ok());
1857    /// ```
1858    pub fn union_ty(&mut self, members: &[TTy]) -> TTy {
1859        let members = self.list(members.iter().map(|m| m.0));
1860        TTy(self.push(TNode::TUnion(members)))
1861    }
1862
1863    /// An intersection type `A & B` (HIR `Ty::Intersection`), normalized like
1864    /// [`union_ty`](Self::union_ty).
1865    ///
1866    /// # Examples
1867    ///
1868    /// ```
1869    /// let mut t = lower_lang::TemplateBuilder::new("t");
1870    /// let x = t.binder("x");
1871    /// let p = t.bind(x);
1872    /// let (a, b) = (t.named_ty("Countable"), t.named_ty("Traversable"));
1873    /// let ty = t.intersection_ty(&[a, b]);
1874    /// let s = t.let_(p, Some(ty), None);
1875    /// let root = t.block(&[s], None);
1876    /// assert!(t.finish(root).is_ok());
1877    /// ```
1878    pub fn intersection_ty(&mut self, members: &[TTy]) -> TTy {
1879        let members = self.list(members.iter().map(|m| m.0));
1880        TTy(self.push(TNode::TInter(members)))
1881    }
1882
1883    // ---------------------------------------------------------------- finish
1884
1885    /// Checks the template rooted at `root` and returns it.
1886    ///
1887    /// # Errors
1888    ///
1889    /// A [`TemplateError`]: an unused hole, an unbound or twice-bound binder,
1890    /// an undefined or twice-defined label, an argument splice outside a list,
1891    /// a handle from another builder, or a tree larger than
1892    /// [`MAX_TEMPLATE_SIZE`].
1893    ///
1894    /// # Examples
1895    ///
1896    /// ```
1897    /// use lower_lang::{TemplateBuilder, TemplateError};
1898    ///
1899    /// let mut t = TemplateBuilder::new("bad");
1900    /// let x = t.binder("x");
1901    /// let root = t.var(x); // never bound
1902    /// assert_eq!(t.finish(root), Err(TemplateError::BinderUnbound { binder: 0 }));
1903    /// ```
1904    pub fn finish(mut self, root: TExpr) -> Result<Template, TemplateError> {
1905        if self.overflow {
1906            return Err(TemplateError::TooLarge);
1907        }
1908        self.t.root = root.0;
1909        let applies = check(&self.t)?;
1910        self.t.applies = applies;
1911        Ok(self.t)
1912    }
1913}
1914
1915/// Use and binding counts gathered by walking a template's tree.
1916struct Counts {
1917    hole_uses: Vec<u32>,
1918    binder_sites: Vec<u32>,
1919    binder_uses: Vec<u32>,
1920    label_defs: Vec<u32>,
1921    label_uses: Vec<u32>,
1922}
1923
1924/// Walks the template's tree from its root (iteratively, counting shared
1925/// sub-trees at every use) and checks it. Returns the `Apply` nodes reached.
1926fn check(t: &Template) -> Result<Vec<u32>, TemplateError> {
1927    let mut c = Counts {
1928        hole_uses: alloc::vec![0; t.holes.len()],
1929        binder_sites: alloc::vec![0; t.binders.len()],
1930        binder_uses: alloc::vec![0; t.binders.len()],
1931        label_defs: alloc::vec![0; t.labels.len()],
1932        label_uses: alloc::vec![0; t.labels.len()],
1933    };
1934    let mut applies = Vec::new();
1935    // (node, whether it sits directly in an argument/element list)
1936    let mut stack: Vec<(u32, bool)> = alloc::vec![(t.root, false)];
1937    let mut size: u32 = 0;
1938    while let Some((n, in_list)) = stack.pop() {
1939        if n == NONE {
1940            continue;
1941        }
1942        size += 1;
1943        if size > MAX_TEMPLATE_SIZE {
1944            return Err(TemplateError::TooLarge);
1945        }
1946        let node = *t.node(n).ok_or(TemplateError::ForeignHandle)?;
1947        let kids = |list: TList,
1948                    in_list: bool,
1949                    stack: &mut Vec<(u32, bool)>|
1950         -> Result<(), TemplateError> {
1951            let (start, len) = (list.0 as usize, list.1 as usize);
1952            let slice = t
1953                .lists
1954                .get(start..start.saturating_add(len))
1955                .ok_or(TemplateError::ForeignHandle)?;
1956            stack.extend(slice.iter().map(|&k| (k, in_list)));
1957            Ok(())
1958        };
1959        match node {
1960            TNode::Hole(h) | TNode::PHole(h) | TNode::THole(h) | TNode::Stmts(h) => {
1961                bump(&mut c.hole_uses, usize::from(h))?;
1962            }
1963            TNode::Splice(h) => {
1964                if !in_list {
1965                    return Err(TemplateError::SpliceOutOfList {
1966                        hole: usize::from(h),
1967                    });
1968                }
1969                bump(&mut c.hole_uses, usize::from(h))?;
1970            }
1971            TNode::Var(b) => bump(&mut c.binder_uses, usize::from(b))?,
1972            TNode::PBind(b) => bump(&mut c.binder_sites, usize::from(b))?,
1973            TNode::Lit(_)
1974            | TNode::Str(_)
1975            | TNode::Global(_)
1976            | TNode::Extern(_)
1977            | TNode::PWild
1978            | TNode::PLit(_)
1979            | TNode::TPrim(_)
1980            | TNode::TNamed(_)
1981            | TNode::TInfer
1982            | TNode::TAny => {}
1983            TNode::Call { callee, args } => {
1984                stack.push((callee, false));
1985                kids(args, true, &mut stack)?;
1986            }
1987            TNode::Method { recv, args, .. } => {
1988                stack.push((recv, false));
1989                kids(args, true, &mut stack)?;
1990            }
1991            TNode::Field { base, .. } => stack.push((base, false)),
1992            TNode::Index { base, index } => stack.extend([(base, false), (index, false)]),
1993            TNode::Op { args, .. } => kids(args, false, &mut stack)?,
1994            TNode::Assign { target, value } => stack.extend([(target, false), (value, false)]),
1995            TNode::Block { stmts, tail, label } => {
1996                define_label(&mut c, label)?;
1997                kids(stmts, false, &mut stack)?;
1998                stack.push((tail, false));
1999            }
2000            TNode::If { cond, then, else_ } => {
2001                stack.extend([(cond, false), (then, false), (else_, false)]);
2002            }
2003            TNode::Match { scrutinee, arms } => {
2004                stack.push((scrutinee, false));
2005                kids(arms, false, &mut stack)?;
2006            }
2007            TNode::Loop { label, body, step } => {
2008                define_label(&mut c, label)?;
2009                stack.extend([(body, false), (step, false)]);
2010            }
2011            TNode::Break { label, value } => {
2012                use_label(&mut c, label)?;
2013                stack.push((value, false));
2014            }
2015            TNode::Continue { label } => use_label(&mut c, label)?,
2016            TNode::Return(v)
2017            | TNode::Throw(v)
2018            | TNode::Await(v)
2019            | TNode::YieldFrom(v)
2020            | TNode::Spawn(v)
2021            | TNode::ExprStmt(v)
2022            | TNode::Defer(v) => stack.push((v, false)),
2023            TNode::Yield { key, value } => stack.extend([(key, false), (value, false)]),
2024            TNode::LetPlace {
2025                binder,
2026                place,
2027                body,
2028            } => {
2029                bump(&mut c.binder_sites, usize::from(binder))?;
2030                stack.extend([(place, false), (body, false)]);
2031            }
2032            TNode::TUnion(l) | TNode::TInter(l) => kids(l, false, &mut stack)?,
2033            TNode::Tuple(l) | TNode::Array(l) => kids(l, true, &mut stack)?,
2034            TNode::Closure { params, body, .. } => {
2035                let (start, len) = (params.0 as usize, params.1 as usize);
2036                let slice = t
2037                    .lists
2038                    .get(start..start.saturating_add(len))
2039                    .ok_or(TemplateError::ForeignHandle)?;
2040                for &p in slice {
2041                    bump(&mut c.binder_sites, p as usize)?;
2042                }
2043                stack.push((body, false));
2044            }
2045            TNode::Apply { args, .. } => {
2046                applies.push(n);
2047                let (start, len) = (args.0 as usize, args.1 as usize);
2048                let slice = t
2049                    .args
2050                    .get(start..start.saturating_add(len))
2051                    .ok_or(TemplateError::ForeignHandle)?;
2052                for arg in slice {
2053                    match *arg {
2054                        TArg::Expr(e) => stack.push((e.0, false)),
2055                        TArg::Pat(p) => stack.push((p.0, false)),
2056                        TArg::Ty(ty) => stack.push((ty.0, false)),
2057                        TArg::Stmts(h) => bump(&mut c.hole_uses, usize::from(h.0))?,
2058                        TArg::Args(h) => bump(&mut c.hole_uses, usize::from(h.0))?,
2059                        TArg::Label(l) => use_label(&mut c, LabelSlot::of(Some(l)))?,
2060                        TArg::Absent => {}
2061                    }
2062                }
2063            }
2064            TNode::Let { pat, ty, init } => {
2065                stack.extend([(pat, false), (ty, false), (init, false)])
2066            }
2067            TNode::PTuple(l) => kids(l, false, &mut stack)?,
2068            TNode::PCtor { elems, .. } => kids(elems, false, &mut stack)?,
2069        }
2070    }
2071    for (i, &n) in c.hole_uses.iter().enumerate() {
2072        if n == 0 {
2073            return Err(TemplateError::HoleUnused { hole: i });
2074        }
2075    }
2076    for (i, (&sites, &uses)) in c.binder_sites.iter().zip(&c.binder_uses).enumerate() {
2077        if sites > 1 {
2078            return Err(TemplateError::BinderBoundTwice { binder: i });
2079        }
2080        if sites == 0 && uses > 0 {
2081            return Err(TemplateError::BinderUnbound { binder: i });
2082        }
2083    }
2084    for (i, (&defs, &uses)) in c.label_defs.iter().zip(&c.label_uses).enumerate() {
2085        if defs > 1 {
2086            return Err(TemplateError::LabelDefinedTwice { label: i });
2087        }
2088        if defs == 0 && uses > 0 {
2089            return Err(TemplateError::LabelUndefined { label: i });
2090        }
2091    }
2092    Ok(applies)
2093}
2094
2095fn bump(counts: &mut [u32], i: usize) -> Result<(), TemplateError> {
2096    let slot = counts.get_mut(i).ok_or(TemplateError::ForeignHandle)?;
2097    *slot = slot.saturating_add(1);
2098    Ok(())
2099}
2100
2101fn define_label(c: &mut Counts, label: LabelSlot) -> Result<(), TemplateError> {
2102    match label {
2103        LabelSlot::None => Ok(()),
2104        LabelSlot::Own(l) => bump(&mut c.label_defs, usize::from(l)),
2105        LabelSlot::Hole(h) => bump(&mut c.hole_uses, usize::from(h)),
2106    }
2107}
2108
2109fn use_label(c: &mut Counts, label: LabelSlot) -> Result<(), TemplateError> {
2110    match label {
2111        LabelSlot::None => Ok(()),
2112        LabelSlot::Own(l) => bump(&mut c.label_uses, usize::from(l)),
2113        LabelSlot::Hole(h) => bump(&mut c.hole_uses, usize::from(h)),
2114    }
2115}
2116
2117#[cfg(test)]
2118mod tests {
2119    use super::*;
2120
2121    #[test]
2122    fn test_shared_subtrees_count_at_every_use() {
2123        let mut t = TemplateBuilder::new("blowup");
2124        let mut e = t.lit(TLit::Int(1));
2125        for _ in 0..40 {
2126            e = t.tuple(&[e, e]);
2127        }
2128        assert_eq!(t.finish(e), Err(TemplateError::TooLarge));
2129    }
2130
2131    #[test]
2132    fn test_foreign_handles_are_refused() {
2133        let mut t = TemplateBuilder::new("foreign");
2134        let root = TExpr(99);
2135        let _ = t.lit(TLit::Null);
2136        assert_eq!(t.finish(root), Err(TemplateError::ForeignHandle));
2137    }
2138
2139    #[test]
2140    fn test_label_rules() {
2141        let mut t = TemplateBuilder::new("labels");
2142        let l = t.label("l");
2143        let brk = t.break_(Some(LabelRef::Own(l)), None);
2144        assert_eq!(
2145            t.finish(brk),
2146            Err(TemplateError::LabelUndefined { label: 0 })
2147        );
2148
2149        let mut t = TemplateBuilder::new("labels");
2150        let l = t.label("l");
2151        let body = t.block(&[], None);
2152        let a = t.loop_(Some(LabelRef::Own(l)), body, None);
2153        let b = t.loop_(Some(LabelRef::Own(l)), body, None);
2154        let root = t.tuple(&[a, b]);
2155        assert_eq!(
2156            t.finish(root),
2157            Err(TemplateError::LabelDefinedTwice { label: 0 })
2158        );
2159    }
2160
2161    #[test]
2162    fn test_splice_outside_a_list_is_refused() {
2163        let mut t = TemplateBuilder::new("splice");
2164        let args = t.args_hole("args");
2165        let s = t.splice(args);
2166        let root = t.op(OpKind::Not, &[s]);
2167        assert_eq!(
2168            t.finish(root),
2169            Err(TemplateError::SpliceOutOfList { hole: 0 })
2170        );
2171    }
2172
2173    #[test]
2174    fn test_binder_bound_twice() {
2175        let mut t = TemplateBuilder::new("twice");
2176        let x = t.binder("x");
2177        let (p1, p2) = (t.bind(x), t.bind(x));
2178        let pair = t.tuple_pat(&[p1, p2]);
2179        let unit = t.tuple(&[]);
2180        let s = t.let_(pair, None, Some(unit));
2181        let root = t.block(&[s], None);
2182        assert_eq!(
2183            t.finish(root),
2184            Err(TemplateError::BinderBoundTwice { binder: 0 })
2185        );
2186    }
2187}