Skip to main content

lower_lang/lower/
mod.rs

1//! The lowering engine: an explicit-stack machine over the syntax tree.
2//!
3//! Lowering is recursive in nature (an expression contains expressions) and
4//! hir-lang's builder is bottom-up (children before parents), so the engine
5//! runs a work stack of tasks: *lower this element in this context* and
6//! *finish the innermost open frame*. Entering a node resolves its fields'
7//! picks, opens a frame, and schedules one task per selected child; every
8//! task leaves exactly one value on the value stack, so when the frame
9//! finishes its fields' values sit in order above the frame's base. Nothing
10//! recurses on the call stack, so any tree depth is safe.
11
12mod enter;
13mod finish;
14mod token;
15mod tpl;
16
17use alloc::collections::BTreeMap;
18use alloc::string::String;
19use alloc::vec::Vec;
20
21use hir_lang::{
22    Arg, ArgKind, BinderId, BinderKind, Builder, Capture, Effects, Expr, ExprId, FieldInit,
23    FieldPat, GenericArg, GenericParam, Hir, HirError, Item, ItemId, ItemKind, List, MapEntry,
24    Name, NodeRef, Ns, Origin, Param, ParamKind, Pat, PatId, Path, PathId, Res, Segment, Site,
25    Span, Stmt, StmtId, Ty, TyId, UnitId, VariantId, WherePred,
26};
27use intern_lang::{Interner, Symbol};
28use syntax_lang::{Element, Node, TokenKind};
29
30use crate::arch::Arch;
31use crate::mapping::{EffectMode, Mapping, OpSpec, TokenRole};
32use crate::pick::{self, Kid, Labeler, Pick};
33use crate::problem::{Context, LowerError, Problem, ProblemKind};
34use crate::template::TemplateId;
35
36/// A range of the run's attribute pool: (start, len).
37pub(crate) type AttrRange = (u32, u32);
38
39/// Limits on what one lowering may do. Untrusted trees and templates cannot
40/// exceed them; exceeding one is a reported problem or error, never a hang.
41///
42/// `#[non_exhaustive]`: start from [`Budget::default`] and assign fields.
43///
44/// # Examples
45///
46/// ```
47/// use lower_lang::Budget;
48///
49/// let mut budget = Budget::default();
50/// budget.max_nodes = 1_000;
51/// assert_eq!(budget.max_expansion_depth, 64);
52/// ```
53#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
54#[non_exhaustive]
55pub struct Budget {
56    /// The most HIR nodes (and list entries) one lowering may build, copies
57    /// for repeated template holes included; past it lowering stops with
58    /// [`LowerError::NodeBudget`]. Default `1 << 24` (16,777,216).
59    pub max_nodes: u64,
60    /// The deepest chain of template applications
61    /// ([`TemplateBuilder::apply`](crate::TemplateBuilder::apply)); a deeper
62    /// one becomes an error node and an
63    /// [`ExpansionTooDeep`](ProblemKind::ExpansionTooDeep) problem.
64    /// Default 64.
65    pub max_expansion_depth: u32,
66}
67
68impl Default for Budget {
69    fn default() -> Self {
70        Self {
71            max_nodes: 1 << 24,
72            max_expansion_depth: 64,
73        }
74    }
75}
76
77/// The result of lowering: a valid HIR unit and every problem found.
78///
79/// The HIR is valid even when there are problems: each broken construct is an
80/// HIR error form, and the rest of the unit is lowered normally.
81///
82/// # Examples
83///
84/// See [`lower`](crate::lower).
85#[derive(Clone, Debug)]
86#[non_exhaustive]
87pub struct Lowered {
88    /// The validated HIR.
89    pub hir: Hir,
90    /// Every problem, in source order (span start, then discovery).
91    pub problems: Vec<Problem>,
92}
93
94impl Lowered {
95    /// Whether any problem was found.
96    ///
97    /// # Examples
98    ///
99    /// ```
100    /// use lower_lang::{lower, Arch, MappingBuilder, Pick};
101    /// use syntax_lang::Node;
102    ///
103    /// # #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
104    /// # struct K(u8);
105    /// # impl syntax_lang::TokenKind for K {}
106    /// let mut b = MappingBuilder::new();
107    /// b.node(K(0), Arch::Module { name: Pick::Absent, items: Pick::Nodes });
108    /// let mapping = b.build()?;
109    /// let tree = Node::new(K(0), vec![]);
110    /// let mut names = intern_lang::Interner::new();
111    /// let out = lower(&tree, "", &mapping, &mut names).expect("within budget");
112    /// assert!(!out.has_problems());
113    /// # Ok::<(), lower_lang::MappingError>(())
114    /// ```
115    #[must_use]
116    pub fn has_problems(&self) -> bool {
117        !self.problems.is_empty()
118    }
119}
120
121/// Lowers syntax trees with one mapping: the configured path, for a budget,
122/// a compilation unit other than 0, or host-provided field labels.
123///
124/// # Examples
125///
126/// ```
127/// use hir_lang::UnitId;
128/// use lower_lang::{Arch, Budget, Lowerer, MappingBuilder, Pick};
129/// use syntax_lang::Node;
130///
131/// # #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
132/// # struct K(u8);
133/// # impl syntax_lang::TokenKind for K {}
134/// let mut b = MappingBuilder::new();
135/// b.node(K(0), Arch::Module { name: Pick::Absent, items: Pick::Nodes });
136/// let mapping = b.build()?;
137/// let tree = Node::new(K(0), vec![]);
138/// let mut names = intern_lang::Interner::new();
139/// let out = Lowerer::new(&mapping)
140///     .with_unit(UnitId::new(3))
141///     .with_budget(Budget::default())
142///     .lower(&tree, "", &mut names)
143///     .expect("within budget");
144/// assert_eq!(out.hir.unit(), UnitId::new(3));
145/// # Ok::<(), lower_lang::MappingError>(())
146/// ```
147pub struct Lowerer<'m, K> {
148    mapping: &'m Mapping<K>,
149    budget: Budget,
150    unit: UnitId,
151    labeler: Option<&'m dyn Labeler<K>>,
152}
153
154impl<'m, K> Lowerer<'m, K>
155where
156    K: Copy + Ord + TokenKind,
157{
158    /// A lowerer for `mapping`, with the default budget, unit 0, and no field
159    /// labels.
160    ///
161    /// # Examples
162    ///
163    /// See [`Lowerer`].
164    #[must_use]
165    pub fn new(mapping: &'m Mapping<K>) -> Self {
166        Self {
167            mapping,
168            budget: Budget::default(),
169            unit: UnitId::default(),
170            labeler: None,
171        }
172    }
173
174    /// Sets the budget.
175    ///
176    /// # Examples
177    ///
178    /// See [`Lowerer`].
179    #[must_use]
180    pub fn with_budget(mut self, budget: Budget) -> Self {
181        self.budget = budget;
182        self
183    }
184
185    /// Sets the compilation unit the HIR is built for.
186    ///
187    /// # Examples
188    ///
189    /// See [`Lowerer`].
190    #[must_use]
191    pub fn with_unit(mut self, unit: UnitId) -> Self {
192        self.unit = unit;
193        self
194    }
195
196    /// Uses `labeler` for [`Pick::Label`](crate::Pick::Label) fields.
197    ///
198    /// # Examples
199    ///
200    /// ```
201    /// use lower_lang::{Labeler, Lowerer, MappingBuilder};
202    /// use syntax_lang::Node;
203    ///
204    /// struct NoFields;
205    /// # #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
206    /// # struct K(u8);
207    /// # impl syntax_lang::TokenKind for K {}
208    /// impl Labeler<K> for NoFields {
209    ///     fn label(&self, _: &Node<K>, _: usize) -> Option<u16> { None }
210    /// }
211    /// let mapping = MappingBuilder::<K>::new().build()?;
212    /// let _lowerer = Lowerer::new(&mapping).with_labeler(&NoFields);
213    /// # Ok::<(), lower_lang::MappingError>(())
214    /// ```
215    #[must_use]
216    pub fn with_labeler(mut self, labeler: &'m dyn Labeler<K>) -> Self {
217        self.labeler = Some(labeler);
218        self
219    }
220
221    /// Lowers `tree` (parsed from `source`) into a validated HIR unit, with
222    /// names interned in `names`.
223    ///
224    /// # Errors
225    ///
226    /// Only for exhausted resources: [`LowerError::NodeBudget`],
227    /// [`LowerError::SymbolSpaceExhausted`], or [`LowerError::Hir`] when
228    /// hir-lang's arenas overflow. Problems in the code are never errors:
229    /// they are in [`Lowered::problems`].
230    ///
231    /// # Examples
232    ///
233    /// See [`Lowerer`].
234    pub fn lower(
235        &self,
236        tree: &Node<K>,
237        source: &str,
238        names: &mut Interner,
239    ) -> Result<Lowered, LowerError> {
240        Run::new(self, source, names)?.run(tree)
241    }
242}
243
244// ------------------------------------------------------------------ machine
245
246/// Where a pattern's binders are bound.
247#[derive(Clone, Copy, Debug, PartialEq, Eq)]
248pub(crate) struct PatSite {
249    /// A parameter (binders of kind `Param`) rather than a local.
250    pub(crate) param: bool,
251    /// The binders are mutable.
252    pub(crate) mutable: bool,
253    /// A `match` arm, where bare identifiers follow the language's
254    /// [`IdentPatterns`](crate::IdentPatterns) policy.
255    pub(crate) arm: bool,
256    /// A range bound: bare identifiers are constants, not bindings.
257    pub(crate) bound: bool,
258    /// The binders belong to the enclosing function: the pattern binds
259    /// hygienic temporaries that the consumer assigns to hoisted names.
260    pub(crate) persist: bool,
261}
262
263impl PatSite {
264    pub(crate) const LOCAL: Self = Self {
265        param: false,
266        mutable: false,
267        arm: false,
268        bound: false,
269        persist: false,
270    };
271    pub(crate) const ARM: Self = Self {
272        param: false,
273        mutable: false,
274        arm: true,
275        bound: false,
276        persist: false,
277    };
278}
279
280/// A function-scoped binding made by a pattern: the temporary the pattern
281/// binds, and the hoisted name it is assigned to.
282#[derive(Clone, Copy, Debug)]
283pub(crate) struct Persist {
284    pub(crate) tmp: BinderId,
285    pub(crate) sym: Symbol,
286    pub(crate) span: Span,
287}
288
289/// One piece of an interpolated string under construction.
290#[derive(Clone, Copy, Debug)]
291pub(crate) enum Piece {
292    /// Decoded text.
293    Text(hir_lang::TextRef, Span),
294    /// The next value of the frame's expression field.
295    Expr,
296}
297
298/// The context an element is lowered in, and so the kind of value it leaves.
299#[derive(Clone, Copy, Debug, PartialEq, Eq)]
300pub(crate) enum Want {
301    /// The root module.
302    Root,
303    /// An expression.
304    Expr,
305    /// An element of a block or module body: a statement, an expression, or
306    /// an item.
307    Stmt,
308    /// A member of a class, interface, or impl: an item or a field.
309    Member,
310    /// A pattern.
311    Pat(PatSite),
312    /// A type.
313    Ty,
314    /// A path in a namespace.
315    Path(Ns),
316    /// A path segment.
317    Segment,
318    /// A parameter.
319    Param,
320    /// A call argument.
321    Arg,
322    /// A match arm or catch clause.
323    Arm,
324    /// An explicit capture.
325    Capture,
326    /// A field definition.
327    Field,
328    /// A mixin rule.
329    Rule,
330    /// A sum variant.
331    Variant,
332    /// A generic parameter.
333    Generic,
334    /// A generic argument.
335    GArg,
336    /// A where-clause predicate.
337    Where,
338    /// A map-literal entry.
339    Entry,
340    /// A record-literal field initializer.
341    Init,
342    /// A record-pattern field.
343    FieldPat(PatSite),
344}
345
346impl Want {
347    pub(crate) const fn context(self) -> Context {
348        match self {
349            Self::Root | Self::Stmt => Context::Statement,
350            Self::Expr => Context::Expression,
351            Self::Member => Context::Member,
352            Self::Pat(_) | Self::FieldPat(_) => Context::Pattern,
353            Self::Ty => Context::Type,
354            Self::Path(_) => Context::Path,
355            Self::Segment => Context::Segment,
356            Self::Param => Context::Parameter,
357            Self::Arg => Context::Argument,
358            Self::Arm => Context::Arm,
359            Self::Capture => Context::Capture,
360            Self::Field => Context::Field,
361            Self::Rule => Context::Member,
362            Self::Variant => Context::Variant,
363            Self::Generic | Self::GArg | Self::Where => Context::Generic,
364            Self::Entry | Self::Init => Context::Entry,
365        }
366    }
367
368    /// Whether an expression's value adapts to this context.
369    pub(crate) const fn takes_expr(self) -> bool {
370        matches!(
371            self,
372            Self::Expr | Self::Stmt | Self::Arg | Self::Entry | Self::GArg
373        )
374    }
375}
376
377/// The value one lowered element leaves on the value stack.
378#[derive(Clone, Copy, Debug)]
379pub(crate) enum Val {
380    /// Nothing: an absent element, or a list element that failed and was
381    /// dropped (its problem already reported).
382    Err,
383    Expr(ExprId),
384    Stmt(StmtId),
385    Item(ItemId),
386    /// Several values from one element (a `Splice`, `global $a, $b`): a run of
387    /// the spill stack. Spill entries are never themselves spills.
388    Spill(u32, u32),
389    Pat(PatId),
390    /// A `..` marker in a pattern list, with its optional binding.
391    Rest(Option<PatId>),
392    Ty(TyId),
393    Path(PathId),
394    Seg(Segment),
395    /// A parameter, created as a node by the enclosing function so that list
396    /// markers can still adjust its kind; with its attributes.
397    Param(Param, Span, AttrRange),
398    /// A `*` or `/` marker in a parameter list.
399    Marker(ParamKind),
400    Arg(Arg),
401    Arm(hir_lang::Arm),
402    Cap(Capture),
403    /// A field definition, and whether it has a name.
404    Field(hir_lang::FieldId, bool),
405    Variant(VariantId),
406    Generic(GenericParam),
407    GArg(GenericArg),
408    Where(WherePred),
409    Entry(MapEntry),
410    Init(FieldInit),
411    FieldPat(FieldPat),
412    Rule(hir_lang::MixinRule),
413}
414
415/// A value on the value stack, with the span of the element it came from and
416/// whether it is a place (for place arguments).
417#[derive(Clone, Copy, Debug)]
418pub(crate) struct Slot {
419    pub(crate) v: Val,
420    pub(crate) span: Span,
421    pub(crate) place: bool,
422}
423
424/// A unit of work.
425#[derive(Clone, Copy)]
426pub(crate) enum Task<'t, K> {
427    /// Lower this element in this context.
428    Elem(&'t Element<K>, Want),
429    /// Lower this node in this context (the root).
430    Node(&'t Node<K>, Want),
431    /// Finish the innermost open frame.
432    Finish,
433    /// Record where the persistent-binding log stands (between the fields of
434    /// a template node, so each pattern hole's bindings are known).
435    Mark,
436}
437
438/// What a frame builds when it finishes.
439#[derive(Clone, Copy, Debug)]
440pub(crate) enum Build {
441    /// The frame's archetype, in its context.
442    Arch,
443    /// An operator node lowered through an operator spec.
444    Op(OpSpec),
445    /// A compound assignment through a non-OPS operator (`let_place`), and
446    /// the node count when its operands started (the charge for copying the
447    /// value into a template more than once).
448    Compound { spec: OpSpec, nodes_at: u64 },
449    /// A template instantiation.
450    Template {
451        id: TemplateId,
452        label: Option<BinderId>,
453        nodes_at: u64,
454    },
455    /// A synthetic module around a root that is not a module.
456    RootWrap,
457    /// `var x = init` hoisted: an assignment to the hoisted name.
458    HoistedLet { name: Symbol, name_span: Span },
459}
460
461/// An open construct whose fields are being lowered.
462#[derive(Clone, Copy, Debug)]
463pub(crate) struct Frame<K> {
464    pub(crate) arch: Arch<K>,
465    pub(crate) build: Build,
466    pub(crate) want: Want,
467    pub(crate) span: Span,
468    pub(crate) vals_base: usize,
469    pub(crate) counts_base: usize,
470    pub(crate) nfields: usize,
471    pub(crate) spill_base: usize,
472    pub(crate) label_mark: usize,
473    pub(crate) mods: u32,
474    pub(crate) fx: bool,
475    pub(crate) or: bool,
476    /// Names read synchronously at entry (declaration names, aliases,
477    /// members, labels).
478    pub(crate) name: Option<(Symbol, Span)>,
479    /// A second synchronous name (a mixin rule's alias).
480    pub(crate) alias: Option<(Symbol, Span)>,
481    /// A binder created or found at entry (a label, a pattern's binder).
482    pub(crate) binder: Option<BinderId>,
483    /// A tuple-field index (`a.0`).
484    pub(crate) index: Option<u32>,
485    /// An archetype-specific flag: a member access is a call, a generic
486    /// parameter is a region.
487    pub(crate) flag: bool,
488    /// A path's root, read from its leading tokens.
489    pub(crate) path_root: hir_lang::PathRoot,
490    /// The node's attributes in the run's pool.
491    pub(crate) attrs: AttrRange,
492    /// An archetype-specific range: an interpolation's pieces, or the
493    /// persistent-binding log mark of a hoisting `let`.
494    pub(crate) aux: (u32, u32),
495    /// The loop stack's height when the frame opened; a loop frame's own
496    /// entry sits right there, and finishing the frame pops back to it.
497    pub(crate) loop_mark: usize,
498}
499
500/// A function, closure, or module body under construction: its effects and
501/// its hoisted declarations.
502#[derive(Clone, Copy, Debug)]
503pub(crate) struct Fx {
504    pub(crate) declared: Effects,
505    pub(crate) inferred: Effects,
506    pub(crate) hoist_base: usize,
507    pub(crate) decl_base: usize,
508    /// Whether the implicit receiver is visible in this body.
509    pub(crate) recv: Recv,
510    /// Whether an explicit capture names the receiver (`use ($this)`), so
511    /// no implicit one is added.
512    pub(crate) recv_captured: bool,
513    /// Where this body's loops start on the loop stack (numeric break
514    /// levels never count loops outside their function).
515    pub(crate) loop_base: usize,
516}
517
518/// The implicit receiver's state in a function-like body.
519#[derive(Clone, Copy, Debug, PartialEq, Eq)]
520pub(crate) enum Recv {
521    /// Not a method, nor a closure inside one: the receiver name is an
522    /// ordinary name (resolution decides).
523    None,
524    /// A method's body, or a closure that captures the receiver.
525    Visible,
526    /// A `static` closure inside a method (or a closure nested in one): the
527    /// name would otherwise reach the method's receiver through implicit
528    /// captures, so reading it is reported.
529    Hidden,
530}
531
532/// A loop the numeric break levels can target: its label, when it has one
533/// yet (its own, or one made on demand for a `break N`).
534#[derive(Clone, Copy, Debug)]
535pub(crate) struct LoopEntry {
536    pub(crate) label: Option<BinderId>,
537    pub(crate) span: Span,
538}
539
540/// One lowering run.
541pub(crate) struct Run<'a, 't, K> {
542    pub(crate) m: &'a Mapping<K>,
543    pub(crate) src: &'t str,
544    pub(crate) labeler: Option<&'a dyn Labeler<K>>,
545    pub(crate) names: &'a mut Interner,
546    pub(crate) b: Builder,
547    pub(crate) nodes: u64,
548    pub(crate) budget: Budget,
549    pub(crate) syms: Vec<Symbol>,
550    pub(crate) empty: Symbol,
551    pub(crate) sym_failed: bool,
552    pub(crate) tasks: Vec<Task<'t, K>>,
553    pub(crate) vals: Vec<Slot>,
554    pub(crate) frames: Vec<Frame<K>>,
555    pub(crate) counts: Vec<usize>,
556    pub(crate) spill: Vec<Slot>,
557    pub(crate) kids: Vec<Kid<'t, K>>,
558    pub(crate) kids2: Vec<Kid<'t, K>>,
559    pub(crate) sel: Vec<&'t Element<K>>,
560    pub(crate) labels: BTreeMap<Symbol, Vec<BinderId>>,
561    pub(crate) label_log: Vec<Symbol>,
562    pub(crate) fx: Vec<Fx>,
563    pub(crate) hoist: Vec<(Symbol, Span)>,
564    pub(crate) declared: Vec<Symbol>,
565    pub(crate) or_depth: u32,
566    pub(crate) or_map: BTreeMap<Symbol, BinderId>,
567    pub(crate) problems: Vec<Problem>,
568    pub(crate) text: Vec<u8>,
569    pub(crate) scratch: String,
570    pub(crate) bufs: Vec<Vec<Slot>>,
571    pub(crate) tpl_scratch: tpl::TplScratch,
572    pub(crate) lists: Lists,
573    pub(crate) tfields: Vec<(Pick<K>, Want, bool)>,
574    /// Attribute elements of the node being entered.
575    pub(crate) attr_elems: Vec<&'t Element<K>>,
576    /// Attributes lowered so far, referenced by ranges.
577    pub(crate) attr_pool: Vec<hir_lang::Attr>,
578    /// The attributes of the node being entered, until a frame takes them.
579    pub(crate) pending_attrs: AttrRange,
580    /// Function-scoped bindings not yet assigned by their consumer.
581    pub(crate) persist: Vec<Persist>,
582    /// (frame depth, persist log length) at each `Task::Mark`.
583    pub(crate) persist_marks: Vec<(u32, u32)>,
584    /// Pieces of the interpolated strings being lowered.
585    pub(crate) pieces: Vec<Piece>,
586    /// The expansion name of hoisting temporaries (`hoist`).
587    pub(crate) hoist_sym: Symbol,
588    /// The expansion name of place-once compound assignments (`compound`).
589    pub(crate) compound_sym: Symbol,
590    /// The name of their place alias (`p`).
591    pub(crate) place_sym: Symbol,
592    /// The implicit receiver's name, when the policy sets one.
593    pub(crate) recv_sym: Option<Symbol>,
594    /// The expansion name of labels made for numeric break levels
595    /// (`break_level`).
596    pub(crate) level_sym: Symbol,
597    /// The loops around the element being lowered (numeric break levels
598    /// only; empty otherwise).
599    pub(crate) loops: Vec<LoopEntry>,
600}
601
602/// Typed scratch lists for building HIR lists without allocating per node.
603#[derive(Default)]
604pub(crate) struct Lists {
605    pub(crate) exprs: Vec<ExprId>,
606    pub(crate) tys: Vec<TyId>,
607    pub(crate) args: Vec<Arg>,
608    pub(crate) arms: Vec<hir_lang::Arm>,
609    pub(crate) stmts: Vec<StmtId>,
610    pub(crate) params: Vec<hir_lang::ParamId>,
611    pub(crate) gargs: Vec<GenericArg>,
612}
613
614impl<'a, 't, K> Run<'a, 't, K>
615where
616    K: Copy + Ord + TokenKind,
617{
618    fn new(
619        cfg: &Lowerer<'a, K>,
620        src: &'t str,
621        names: &'a mut Interner,
622    ) -> Result<Self, LowerError> {
623        let empty = names
624            .try_intern("")
625            .map_err(|_| LowerError::SymbolSpaceExhausted)?;
626        let hoist_sym = names
627            .try_intern("hoist")
628            .map_err(|_| LowerError::SymbolSpaceExhausted)?;
629        let compound_sym = names
630            .try_intern("compound")
631            .map_err(|_| LowerError::SymbolSpaceExhausted)?;
632        let place_sym = names
633            .try_intern("p")
634            .map_err(|_| LowerError::SymbolSpaceExhausted)?;
635        let level_sym = names
636            .try_intern("break_level")
637            .map_err(|_| LowerError::SymbolSpaceExhausted)?;
638        let mut syms = Vec::with_capacity(cfg.mapping.strings.len());
639        for s in &cfg.mapping.strings {
640            syms.push(
641                names
642                    .try_intern(s)
643                    .map_err(|_| LowerError::SymbolSpaceExhausted)?,
644            );
645        }
646        // `build` checked the receiver's name is one of the strings.
647        let recv_sym = cfg
648            .mapping
649            .policy
650            .implicit_receiver
651            .and_then(|r| syms.get(r.0 as usize).copied());
652        Ok(Self {
653            m: cfg.mapping,
654            src,
655            labeler: cfg.labeler,
656            names,
657            b: Builder::for_unit(cfg.unit),
658            nodes: 0,
659            budget: cfg.budget,
660            syms,
661            empty,
662            sym_failed: false,
663            tasks: Vec::new(),
664            vals: Vec::new(),
665            frames: Vec::new(),
666            counts: Vec::new(),
667            spill: Vec::new(),
668            kids: Vec::new(),
669            kids2: Vec::new(),
670            sel: Vec::new(),
671            labels: BTreeMap::new(),
672            label_log: Vec::new(),
673            fx: Vec::new(),
674            hoist: Vec::new(),
675            declared: Vec::new(),
676            or_depth: 0,
677            or_map: BTreeMap::new(),
678            problems: Vec::new(),
679            text: Vec::new(),
680            scratch: String::new(),
681            bufs: Vec::new(),
682            tpl_scratch: tpl::TplScratch::default(),
683            lists: Lists::default(),
684            tfields: Vec::new(),
685            attr_elems: Vec::new(),
686            attr_pool: Vec::new(),
687            pending_attrs: (0, 0),
688            persist: Vec::new(),
689            persist_marks: Vec::new(),
690            pieces: Vec::new(),
691            hoist_sym,
692            compound_sym,
693            place_sym,
694            recv_sym,
695            level_sym,
696            loops: Vec::new(),
697        })
698    }
699
700    fn run(mut self, tree: &'t Node<K>) -> Result<Lowered, LowerError> {
701        self.tasks.push(Task::Node(tree, Want::Root));
702        while let Some(task) = self.tasks.pop() {
703            match task {
704                Task::Elem(Element::Node(n), want) => self.lower_node(n, want),
705                Task::Elem(Element::Token(t), want) => self.lower_token(t, want),
706                Task::Node(n, want) => self.lower_node(n, want),
707                Task::Finish => self.finish(),
708                Task::Mark => {
709                    let depth = u32::try_from(self.frames.len()).unwrap_or(u32::MAX);
710                    let len = u32::try_from(self.persist.len()).unwrap_or(u32::MAX);
711                    self.persist_marks.push((depth, len));
712                }
713            }
714            if self.nodes > self.budget.max_nodes {
715                return Err(LowerError::NodeBudget {
716                    limit: self.budget.max_nodes,
717                });
718            }
719            if self.sym_failed {
720                return Err(LowerError::SymbolSpaceExhausted);
721            }
722        }
723        let root = match self.vals.pop().map(|s| s.v) {
724            Some(Val::Item(root)) => root,
725            _ => {
726                self.b.set_origin(Origin::new(tree.span()));
727                self.b.module(None, &[])
728            }
729        };
730        let (hir, errors) = self.b.finish_lenient(root).map_err(LowerError::Hir)?;
731        let mut problems = self.problems;
732        problems.reserve(errors.len());
733        for e in errors {
734            let span = hir_span(&hir, &e);
735            problems.push(Problem {
736                kind: ProblemKind::Hir(e),
737                span,
738            });
739        }
740        problems.sort_by_key(|p| p.span.start());
741        Ok(Lowered { hir, problems })
742    }
743
744    // ------------------------------------------------------------- dispatch
745
746    fn lower_node(&mut self, node: &'t Node<K>, want: Want) {
747        let span = node.span();
748        if self.m.is_error(node.kind()) {
749            self.report(ProblemKind::SyntaxError, span);
750            let v = self.error_val(want, span);
751            self.push(v, span);
752            return;
753        }
754        let mut attrs = core::mem::take(&mut self.attr_elems);
755        pick::collect_kids(node, self.labeler, self.m, &mut self.kids, Some(&mut attrs));
756        self.pending_attrs = (0, 0);
757        if !attrs.is_empty() {
758            self.pending_attrs = self.lower_attrs(&attrs);
759        }
760        self.attr_elems = attrs;
761        let (start, end) = self.m.rule_range(node.kind());
762        let mut chosen = None;
763        for &(_, rule) in self.m.by_kind.get(start..end).unwrap_or(&[]) {
764            let Some(rule) = self.m.rules.get(rule as usize) else {
765                continue;
766            };
767            if rule.when.is_absent() || pick::single(rule.when, &self.kids, self.m).is_some() {
768                chosen = Some(rule.arch);
769                break;
770            }
771        }
772        match chosen {
773            Some(arch) => self.enter(node, arch, want),
774            None => {
775                self.report(ProblemKind::Unmapped, span);
776                let v = self.error_val(want, span);
777                self.push(v, span);
778            }
779        }
780        // A construct that opened no frame (a wrapper, a capture, ...) has
781        // no node to carry its attributes.
782        if self.pending_attrs.1 > 0 {
783            self.pending_attrs = (0, 0);
784            self.report(ProblemKind::MisplacedAttribute, span);
785        }
786    }
787
788    /// Leaves a value for the element at `span`.
789    pub(crate) fn push(&mut self, v: Val, span: Span) {
790        self.vals.push(Slot {
791            v,
792            span,
793            place: false,
794        });
795    }
796
797    /// Leaves a value that may be a place.
798    pub(crate) fn push_place(&mut self, v: Val, span: Span, place: bool) {
799        self.vals.push(Slot { v, span, place });
800    }
801
802    // -------------------------------------------------------------- frames
803
804    /// Opens a frame for `node` and schedules its fields: each `(pick, want,
805    /// many)` is resolved against the node's children (already in
806    /// `self.kids`), and one task per selected child is pushed.
807    pub(crate) fn plan(&mut self, mut frame: Frame<K>, fields: &[(Pick<K>, Want, bool)]) {
808        let counts_base = self.counts.len();
809        self.sel.clear();
810        for &(p, _, many) in fields {
811            let before = self.sel.len();
812            if many {
813                pick::list(p, &self.kids, self.m, &mut self.sel);
814            } else if let Some(e) = pick::single(p, &self.kids, self.m) {
815                self.sel.push(e);
816            }
817            self.counts.push(self.sel.len() - before);
818        }
819        self.drop_shared_children(fields, counts_base);
820        frame.counts_base = counts_base;
821        frame.nfields = fields.len();
822        frame.vals_base = self.vals.len();
823        frame.spill_base = self.spill.len();
824        self.open(frame);
825        self.tasks.push(Task::Finish);
826        let mut end = self.sel.len();
827        for (i, &(_, want, _)) in fields.iter().enumerate().rev() {
828            let n = self.counts.get(counts_base + i).copied().unwrap_or(0);
829            let start = end.saturating_sub(n);
830            if let Some(slice) = self.sel.get(start..end) {
831                for &e in slice.iter().rev() {
832                    self.tasks.push(Task::Elem(e, want));
833                }
834            }
835            end = start;
836        }
837        self.sel.clear();
838    }
839
840    /// A child selected by an earlier field is not lowered again for a later
841    /// single-valued field: that field is left absent and the conflict is
842    /// reported. Positional picks alias this way in half-typed code (a
843    /// missing condition makes "the first node" the body).
844    fn drop_shared_children(&mut self, fields: &[(Pick<K>, Want, bool)], counts_base: usize) {
845        let mut offset = 0;
846        for (i, &(_, _, many)) in fields.iter().enumerate() {
847            let c = self.counts.get(counts_base + i).copied().unwrap_or(0);
848            if !many && c == 1 {
849                if let Some(&e) = self.sel.get(offset) {
850                    let earlier = self.sel.get(..offset).unwrap_or(&[]);
851                    if earlier.iter().any(|&x| core::ptr::eq(x, e)) {
852                        let _ = self.sel.remove(offset);
853                        if let Some(slot) = self.counts.get_mut(counts_base + i) {
854                            *slot = 0;
855                        }
856                        self.report(ProblemKind::AmbiguousChild, e.span());
857                        continue;
858                    }
859                }
860            }
861            offset += c;
862        }
863    }
864
865    /// Opens a frame like [`plan`](Self::plan), and records the
866    /// persistent-binding log before each field and after the last (template
867    /// nodes whose pattern holes bind function-scoped names).
868    pub(crate) fn plan_marked(&mut self, mut frame: Frame<K>, fields: &[(Pick<K>, Want, bool)]) {
869        let counts_base = self.counts.len();
870        self.sel.clear();
871        for &(p, _, many) in fields {
872            let before = self.sel.len();
873            if many {
874                pick::list(p, &self.kids, self.m, &mut self.sel);
875            } else if let Some(e) = pick::single(p, &self.kids, self.m) {
876                self.sel.push(e);
877            }
878            self.counts.push(self.sel.len() - before);
879        }
880        self.drop_shared_children(fields, counts_base);
881        frame.counts_base = counts_base;
882        frame.nfields = fields.len();
883        frame.vals_base = self.vals.len();
884        frame.spill_base = self.spill.len();
885        self.open(frame);
886        self.tasks.push(Task::Finish);
887        self.tasks.push(Task::Mark);
888        let mut end = self.sel.len();
889        for i in (0..fields.len()).rev() {
890            let n = self.counts.get(counts_base + i).copied().unwrap_or(0);
891            let start = end.saturating_sub(n);
892            if let Some(slice) = self.sel.get(start..end) {
893                let want = fields.get(i).map_or(Want::Expr, |f| f.1);
894                for &e in slice.iter().rev() {
895                    self.tasks.push(Task::Elem(e, want));
896                }
897            }
898            self.tasks.push(Task::Mark);
899            end = start;
900        }
901        self.sel.clear();
902    }
903
904    /// A frame for `node` with nothing scheduled yet.
905    pub(crate) fn frame(&self, arch: Arch<K>, want: Want, span: Span) -> Frame<K> {
906        Frame {
907            arch,
908            build: Build::Arch,
909            want,
910            span,
911            vals_base: 0,
912            counts_base: 0,
913            nfields: 0,
914            spill_base: 0,
915            label_mark: self.label_log.len(),
916            mods: 0,
917            fx: false,
918            or: false,
919            name: None,
920            alias: None,
921            binder: None,
922            index: None,
923            flag: false,
924            path_root: hir_lang::PathRoot::Relative,
925            attrs: (0, 0),
926            aux: (0, 0),
927            loop_mark: self.loops.len(),
928        }
929    }
930
931    /// Pushes an open frame; it takes the attributes of the node being
932    /// entered, which it attaches to its value when it finishes.
933    pub(crate) fn open(&mut self, mut frame: Frame<K>) {
934        frame.attrs = core::mem::take(&mut self.pending_attrs);
935        self.frames.push(frame);
936    }
937
938    /// The value range of field `i` of `f`.
939    pub(crate) fn field_range(&self, f: &Frame<K>, i: usize) -> (usize, usize) {
940        let counts = self
941            .counts
942            .get(f.counts_base..f.counts_base + f.nfields)
943            .unwrap_or(&[]);
944        let start = f.vals_base + counts.iter().take(i).sum::<usize>();
945        let len = counts.get(i).copied().unwrap_or(0);
946        (start, start + len)
947    }
948
949    /// The first value of field `i` (or `Val::Err` when absent).
950    pub(crate) fn one(&self, f: &Frame<K>, i: usize) -> Val {
951        self.slot(f, i).map_or(Val::Err, |s| s.v)
952    }
953
954    /// The first slot of field `i`.
955    pub(crate) fn slot(&self, f: &Frame<K>, i: usize) -> Option<Slot> {
956        let (s, e) = self.field_range(f, i);
957        if s < e {
958            self.vals.get(s).copied()
959        } else {
960            None
961        }
962    }
963
964    /// Whether field `i` selected an element at all (even one that failed).
965    pub(crate) fn present(&self, f: &Frame<K>, i: usize) -> bool {
966        let (s, e) = self.field_range(f, i);
967        s < e
968    }
969
970    /// The values of field `i`, spills flattened, into a pooled buffer.
971    pub(crate) fn many(&mut self, f: &Frame<K>, i: usize) -> Vec<Slot> {
972        let mut out = self.bufs.pop().unwrap_or_default();
973        out.clear();
974        let (s, e) = self.field_range(f, i);
975        for j in s..e {
976            match self.vals.get(j).copied() {
977                Some(Slot {
978                    v: Val::Spill(ss, sl),
979                    ..
980                }) => {
981                    let (ss, sl) = (ss as usize, sl as usize);
982                    if let Some(run) = self.spill.get(ss..ss.saturating_add(sl)) {
983                        out.extend_from_slice(run);
984                    }
985                }
986                Some(Slot { v: Val::Err, .. }) | None => {}
987                Some(slot) => out.push(slot),
988            }
989        }
990        out
991    }
992
993    /// Returns a buffer from [`many`](Self::many) to the pool.
994    pub(crate) fn give(&mut self, mut buf: Vec<Slot>) {
995        buf.clear();
996        self.bufs.push(buf);
997    }
998
999    // ------------------------------------------------------------- problems
1000
1001    pub(crate) fn report(&mut self, kind: ProblemKind, span: Span) {
1002        self.problems.push(Problem { kind, span });
1003    }
1004
1005    /// Reports a missing required field and returns an error expression.
1006    pub(crate) fn missing_expr(&mut self, field: &'static str, span: Span) -> ExprId {
1007        self.report(ProblemKind::MissingField { field }, span);
1008        self.err_expr(span)
1009    }
1010
1011    // ------------------------------------------------------- node creation
1012
1013    pub(crate) fn at(&mut self, span: Span) {
1014        self.b.set_origin(Origin::new(span));
1015    }
1016
1017    pub(crate) fn ex(&mut self, e: Expr) -> ExprId {
1018        self.nodes += 1;
1019        self.b.expr(e)
1020    }
1021
1022    pub(crate) fn st(&mut self, s: Stmt) -> StmtId {
1023        self.nodes += 1;
1024        self.b.stmt(s)
1025    }
1026
1027    pub(crate) fn pt(&mut self, p: Pat) -> PatId {
1028        self.nodes += 1;
1029        self.b.pat(p)
1030    }
1031
1032    pub(crate) fn ty(&mut self, t: Ty) -> TyId {
1033        self.nodes += 1;
1034        self.b.ty(t)
1035    }
1036
1037    pub(crate) fn it(&mut self, i: Item) -> ItemId {
1038        self.nodes += 1;
1039        self.b.item(i)
1040    }
1041
1042    pub(crate) fn path(&mut self, p: Path) -> PathId {
1043        self.nodes += 1;
1044        self.b.path(p)
1045    }
1046
1047    pub(crate) fn binder(&mut self, name: Name, kind: BinderKind, mutable: bool) -> BinderId {
1048        self.nodes += 1;
1049        self.b
1050            .binder(hir_lang::Binder::new(name, kind).with_mutable(mutable))
1051    }
1052
1053    pub(crate) fn list<T: hir_lang::Pooled>(&mut self, items: &[T]) -> List<T> {
1054        self.nodes += items.len() as u64;
1055        self.b.list(items)
1056    }
1057
1058    pub(crate) fn err_expr(&mut self, span: Span) -> ExprId {
1059        self.at(span);
1060        self.ex(Expr::Err)
1061    }
1062
1063    /// A one-segment unresolved path to a source name.
1064    pub(crate) fn name_path(&mut self, sym: Symbol, span: Span, ns: Ns) -> PathId {
1065        self.at(span);
1066        let seg = Segment::new(Name::new(sym), Origin::new(span));
1067        let segs = self.list(&[seg]);
1068        self.path(Path::new(segs, ns))
1069    }
1070
1071    pub(crate) fn name_expr(&mut self, sym: Symbol, span: Span) -> ExprId {
1072        let p = self.name_path(sym, span, Ns::Value);
1073        self.ex(Expr::Path(p))
1074    }
1075
1076    /// The error value for a context: an error node where the context keeps
1077    /// positions (expressions, statements, patterns, parameters, arguments),
1078    /// nothing where a list can simply lose the element.
1079    pub(crate) fn error_val(&mut self, want: Want, span: Span) -> Val {
1080        self.at(span);
1081        match want {
1082            Want::Root => {
1083                // The root must stay a module for hir-lang to accept the unit.
1084                self.nodes += 1;
1085                Val::Item(self.b.module(None, &[]))
1086            }
1087            Want::Member => Val::Item(self.it(Item::new(None, ItemKind::Err))),
1088            Want::Expr => Val::Expr(self.ex(Expr::Err)),
1089            Want::Stmt => Val::Stmt(self.st(Stmt::Err)),
1090            Want::Pat(_) => Val::Pat(self.pt(Pat::Err)),
1091            Want::Ty => Val::Ty(self.ty(Ty::Err)),
1092            Want::Path(_) => {
1093                let mut p = Path::new(List::EMPTY, Ns::Value);
1094                p.res = Res::Err;
1095                Val::Path(self.path(p))
1096            }
1097            Want::Param => {
1098                let pat = self.pt(Pat::Err);
1099                Val::Param(Param::new(pat), span, (0, 0))
1100            }
1101            Want::Arg => {
1102                let e = self.ex(Expr::Err);
1103                Val::Arg(Arg::positional(e))
1104            }
1105            Want::Entry => {
1106                let e = self.ex(Expr::Err);
1107                Val::Entry(MapEntry {
1108                    key: None,
1109                    value: e,
1110                })
1111            }
1112            Want::GArg => {
1113                let t = self.ty(Ty::Err);
1114                Val::GArg(GenericArg::Ty(t))
1115            }
1116            Want::Segment
1117            | Want::Arm
1118            | Want::Capture
1119            | Want::Field
1120            | Want::Variant
1121            | Want::Generic
1122            | Want::Where
1123            | Want::Init
1124            | Want::Rule
1125            | Want::FieldPat(_) => Val::Err,
1126        }
1127    }
1128
1129    /// Reports that a construct cannot appear in `want` and leaves its error
1130    /// value.
1131    pub(crate) fn not_here(&mut self, want: Want, span: Span) {
1132        self.report(
1133            ProblemKind::NotAllowedHere {
1134                expected: want.context(),
1135            },
1136            span,
1137        );
1138        let v = self.error_val(want, span);
1139        self.push(v, span);
1140    }
1141
1142    /// Converts an expression to the value a context takes.
1143    pub(crate) fn adapt_expr(&mut self, e: ExprId, place: bool, want: Want, span: Span) -> Val {
1144        match want {
1145            Want::Expr | Want::Stmt => Val::Expr(e),
1146            Want::Arg => Val::Arg(Arg {
1147                kind: ArgKind::Positional,
1148                value: e,
1149                place: place && self.m.policy.place_args == crate::PlaceArgs::Places,
1150            }),
1151            Want::Entry => Val::Entry(MapEntry {
1152                key: None,
1153                value: e,
1154            }),
1155            Want::GArg => Val::GArg(GenericArg::Const(e)),
1156            _ => {
1157                // Unreachable by construction (`enter` checks the context
1158                // first); keep the expression attached by wrapping it in an
1159                // error-free statement where possible.
1160                self.report(
1161                    ProblemKind::NotAllowedHere {
1162                        expected: want.context(),
1163                    },
1164                    span,
1165                );
1166                self.error_val(want, span)
1167            }
1168        }
1169    }
1170
1171    // ---------------------------------------------------------------- text
1172
1173    /// The source text of `span`, or `""` (and a problem) when the span lies
1174    /// outside the source.
1175    pub(crate) fn text_of(&mut self, span: Span) -> &'t str {
1176        let (s, e) = (span.start().to_usize(), span.end().to_usize());
1177        match self.src.get(s..e) {
1178            Some(t) => t,
1179            None => {
1180                self.report(ProblemKind::BadSpan, span);
1181                ""
1182            }
1183        }
1184    }
1185
1186    pub(crate) fn intern(&mut self, s: &str) -> Symbol {
1187        match self.names.try_intern(s) {
1188            Ok(sym) => sym,
1189            Err(_) => {
1190                self.sym_failed = true;
1191                self.empty
1192            }
1193        }
1194    }
1195
1196    /// The mapping string `i` (texts of templates, extern names) as a symbol.
1197    pub(crate) fn sym(&self, i: u32) -> Symbol {
1198        self.syms.get(i as usize).copied().unwrap_or(self.empty)
1199    }
1200
1201    /// The name an element spells: a name-like token (sigil stripped), or a
1202    /// `Pass` wrapper around one. Other tokens count by their text.
1203    pub(crate) fn name_of(&mut self, elem: &'t Element<K>) -> Option<(Symbol, Span)> {
1204        let mut cur = elem;
1205        loop {
1206            match cur {
1207                Element::Token(t) => {
1208                    let span = t.span();
1209                    let strip = match self.m.role_for(t.kind()) {
1210                        Some(TokenRole::Name) | None => 0,
1211                        Some(
1212                            TokenRole::Var { sigil }
1213                            | TokenRole::Label { sigil }
1214                            | TokenRole::Lifetime { sigil },
1215                        ) => usize::from(sigil),
1216                        Some(_) => return None,
1217                    };
1218                    let text = self.text_of(span);
1219                    let name = text.get(strip..).unwrap_or("");
1220                    return Some((self.intern(name), span));
1221                }
1222                Element::Node(n) => {
1223                    pick::collect_kids(n, self.labeler, self.m, &mut self.kids2, None);
1224                    let arch = self.m.rule_for(n.kind()).copied();
1225                    let inner = match arch {
1226                        Some(Arch::Pass { inner } | Arch::Segment { name: inner, .. }) => {
1227                            pick::single(inner, &self.kids2, self.m)
1228                        }
1229                        Some(Arch::Path { segments, .. }) => {
1230                            let mut out = Vec::new();
1231                            pick::list(segments, &self.kids2, self.m, &mut out);
1232                            if out.len() == 1 {
1233                                out.first().copied()
1234                            } else {
1235                                None
1236                            }
1237                        }
1238                        _ => None,
1239                    };
1240                    cur = inner?;
1241                }
1242            }
1243        }
1244    }
1245
1246    /// The modifiers among the node's direct significant children (and the
1247    /// tokens directly inside container children).
1248    pub(crate) fn mods(&self, arch: &Arch<K>) -> u32 {
1249        if self.m.modifiers.is_empty() && self.m.arch_modifiers.is_empty() {
1250            return 0;
1251        }
1252        // Per-archetype entries need the archetype's name; most mappings
1253        // have none, and skip the lookup.
1254        let name = (!self.m.arch_modifiers.is_empty()).then(|| arch.lsf_name());
1255        let mut bits = 0;
1256        for kid in &self.kids {
1257            match kid.elem {
1258                Element::Token(t) => {
1259                    bits |= crate::mapping::modifier_bits(self.m, t.kind(), name);
1260                }
1261                Element::Node(n) => {
1262                    if crate::pick::KindSets::is_container(self.m, n.kind()) {
1263                        for c in n.child_tokens() {
1264                            bits |= crate::mapping::modifier_bits(self.m, c.kind(), name);
1265                        }
1266                    }
1267                }
1268            }
1269        }
1270        bits
1271    }
1272
1273    // --------------------------------------------------------------- scopes
1274
1275    pub(crate) fn push_label(&mut self, sym: Symbol, b: BinderId) {
1276        self.labels.entry(sym).or_default().push(b);
1277        self.label_log.push(sym);
1278    }
1279
1280    pub(crate) fn pop_labels(&mut self, mark: usize) {
1281        while self.label_log.len() > mark {
1282            if let Some(sym) = self.label_log.pop() {
1283                if let Some(stack) = self.labels.get_mut(&sym) {
1284                    let _ = stack.pop();
1285                }
1286            }
1287        }
1288    }
1289
1290    pub(crate) fn find_label(&self, sym: Symbol) -> Option<BinderId> {
1291        self.labels.get(&sym).and_then(|s| s.last().copied())
1292    }
1293
1294    pub(crate) fn push_fx(&mut self, declared: Effects) {
1295        self.fx.push(Fx {
1296            declared,
1297            inferred: Effects::NONE,
1298            hoist_base: self.hoist.len(),
1299            decl_base: self.declared.len(),
1300            recv: Recv::None,
1301            recv_captured: false,
1302            loop_base: self.loops.len(),
1303        });
1304    }
1305
1306    /// The receiver state of the innermost function-like body.
1307    pub(crate) fn recv_state(&self) -> Recv {
1308        self.fx.last().map_or(Recv::None, |f| f.recv)
1309    }
1310
1311    /// Sets the receiver state of the innermost function-like body.
1312    pub(crate) fn set_recv(&mut self, recv: Recv) {
1313        if let Some(top) = self.fx.last_mut() {
1314            top.recv = recv;
1315        }
1316    }
1317
1318    /// Marks the innermost function-like frame as doing `effect`.
1319    pub(crate) fn infer(&mut self, effect: Effects) {
1320        if let Some(top) = self.fx.last_mut() {
1321            top.inferred = top.inferred.union(effect);
1322        }
1323    }
1324
1325    pub(crate) fn hoist_name(&mut self, sym: Symbol, span: Span) {
1326        if !self.fx.is_empty() {
1327            self.hoist.push((sym, span));
1328        }
1329    }
1330
1331    pub(crate) fn declare_name(&mut self, sym: Symbol) {
1332        if !self.fx.is_empty() {
1333            self.declared.push(sym);
1334        }
1335    }
1336
1337    /// Closes the innermost function-like frame: its effects, and the `let`
1338    /// statements for its hoisted names (deduplicated, minus the names a
1339    /// parameter, `global`, or `static` declares), in first-use order.
1340    pub(crate) fn pop_fx(&mut self, span: Span) -> (Effects, Vec<StmtId>) {
1341        let Some(fx) = self.fx.pop() else {
1342            return (Effects::NONE, Vec::new());
1343        };
1344        let policy = self.m.policy;
1345        let mut effects = fx.declared;
1346        for (mode, flag) in [
1347            (policy.throws, Effects::THROWS),
1348            (policy.yields, Effects::YIELD),
1349            (policy.asyncs, Effects::ASYNC),
1350        ] {
1351            let add = match mode {
1352                EffectMode::Declared => false,
1353                EffectMode::Inferred => fx.inferred.contains(flag),
1354                EffectMode::Always => true,
1355            };
1356            if add {
1357                effects = effects.union(flag);
1358            }
1359        }
1360        let mut stmts = Vec::new();
1361        if self.hoist.len() > fx.hoist_base {
1362            let mut names: Vec<(Symbol, Span)> = self.hoist.split_off(fx.hoist_base);
1363            let mut declared: Vec<Symbol> = self.declared.split_off(fx.decl_base);
1364            declared.sort();
1365            names.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.start().cmp(&b.1.start())));
1366            names.dedup_by(|later, first| later.0 == first.0);
1367            names.retain(|(s, _)| declared.binary_search(s).is_err());
1368            names.sort_by_key(|(_, sp)| sp.start());
1369            for (sym, sp) in names {
1370                self.at(sp);
1371                let b = self.binder(Name::new(sym), BinderKind::Local, true);
1372                let pat = self.pt(Pat::Bind {
1373                    binder: b,
1374                    mode: hir_lang::BindMode::Value,
1375                    sub: None,
1376                });
1377                stmts.push(self.st(Stmt::Let {
1378                    pat,
1379                    ty: None,
1380                    init: None,
1381                    else_: None,
1382                }));
1383            }
1384            self.at(span);
1385        } else {
1386            self.hoist.truncate(fx.hoist_base);
1387            self.declared.truncate(fx.decl_base);
1388        }
1389        (effects, stmts)
1390    }
1391
1392    // ----------------------------------------------- function-scoped binding
1393
1394    /// The temporary a function-scoped pattern binding binds: marked with a
1395    /// fresh `Desugar` expansion (so no user name can capture it), logged for
1396    /// its consumer, and its name hoisted to the enclosing function.
1397    pub(crate) fn persist_binder(&mut self, sym: Symbol, span: Span) -> BinderId {
1398        let expn = self.b.expansion(hir_lang::Expansion {
1399            kind: hir_lang::ExpnKind::Desugar,
1400            name: self.hoist_sym,
1401            call_site: span,
1402            parent: hir_lang::ExpnId::ROOT,
1403            def_site: hir_lang::ExpnId::ROOT,
1404        });
1405        self.at(span);
1406        let tmp = self.binder(Name::marked(sym, expn), BinderKind::Local, true);
1407        self.hoist_name(sym, span);
1408        self.persist.push(Persist { tmp, sym, span });
1409        tmp
1410    }
1411
1412    /// `name = tmp;` for each binding, in order.
1413    pub(crate) fn persist_assigns(&mut self, binds: &[Persist], out: &mut Vec<StmtId>) {
1414        for p in binds {
1415            let target = self.name_expr(p.sym, p.span);
1416            self.at(p.span);
1417            let value = self.b.use_binder(p.tmp);
1418            self.nodes += 2;
1419            let assign = self.ex(Expr::Assign {
1420                target,
1421                op: None,
1422                value,
1423            });
1424            out.push(self.st(Stmt::Expr(assign)));
1425        }
1426    }
1427
1428    /// `{ name = tmp; ...; body }`, or `body` without bindings.
1429    pub(crate) fn with_assigns(&mut self, binds: &[Persist], body: ExprId, span: Span) -> ExprId {
1430        if binds.is_empty() {
1431            return body;
1432        }
1433        let mut stmts = Vec::with_capacity(binds.len());
1434        self.persist_assigns(binds, &mut stmts);
1435        self.at(span);
1436        let list = self.list(&stmts);
1437        self.ex(Expr::Block(hir_lang::Block {
1438            stmts: list,
1439            tail: Some(body),
1440            label: None,
1441            is_unsafe: false,
1442        }))
1443    }
1444
1445    // ----------------------------------------------------------- attributes
1446
1447    /// Lowers attribute nodes (data only: literal and name arguments) into the
1448    /// pool; returns their range.
1449    fn lower_attrs(&mut self, elems: &[&'t Element<K>]) -> AttrRange {
1450        let start = u32::try_from(self.attr_pool.len()).unwrap_or(u32::MAX);
1451        let mut kids = Vec::new();
1452        let mut arg_kids = Vec::new();
1453        let mut args_sel: Vec<&'t Element<K>> = Vec::new();
1454        for &e in elems {
1455            let Element::Node(n) = e else { continue };
1456            let Some(Arch::Attr { name, args }) = self.m.rule_for(n.kind()).copied() else {
1457                continue;
1458            };
1459            pick::collect_kids(n, self.labeler, self.m, &mut kids, None);
1460            let Some(name_elem) = pick::single(name, &kids, self.m) else {
1461                self.report(ProblemKind::MissingField { field: "name" }, e.span());
1462                continue;
1463            };
1464            let name_span = name_elem.span();
1465            let sym = match name_elem {
1466                Element::Token(_) => self.name_of(name_elem).map(|(s, _)| s),
1467                Element::Node(_) => {
1468                    let text = self.text_of(name_span).trim();
1469                    Some(self.intern(text))
1470                }
1471            }
1472            .unwrap_or(self.empty);
1473            args_sel.clear();
1474            pick::list(args, &kids, self.m, &mut args_sel);
1475            let mut out_args: Vec<hir_lang::AttrArg> = Vec::new();
1476            for &a in &args_sel {
1477                let arg_rule = match a {
1478                    Element::Node(an) => self.m.rule_for(an.kind()).copied(),
1479                    Element::Token(_) => None,
1480                };
1481                if let (Some(Arch::AttrArg { key, value }), Element::Node(an)) = (arg_rule, a) {
1482                    pick::collect_kids(an, self.labeler, self.m, &mut arg_kids, None);
1483                    let key = pick::single(key, &arg_kids, self.m)
1484                        .and_then(|k| self.name_of(k))
1485                        .map(|(s, sp)| hir_lang::Ident::new(s, sp));
1486                    let value = pick::single(value, &arg_kids, self.m);
1487                    let value = match value {
1488                        Some(v) => match self.attr_value(v) {
1489                            Some(v) => Some(v),
1490                            None => continue,
1491                        },
1492                        None => None,
1493                    };
1494                    if key.is_none() && value.is_none() {
1495                        continue;
1496                    }
1497                    out_args.push(hir_lang::AttrArg { key, value });
1498                } else if let Some(v) = self.attr_value(a) {
1499                    out_args.push(hir_lang::AttrArg {
1500                        key: None,
1501                        value: Some(v),
1502                    });
1503                }
1504            }
1505            let list = self.list(&out_args);
1506            self.attr_pool.push(hir_lang::Attr {
1507                name: hir_lang::Ident::new(sym, name_span),
1508                args: list,
1509            });
1510        }
1511        let end = u32::try_from(self.attr_pool.len()).unwrap_or(u32::MAX);
1512        (start, end.saturating_sub(start))
1513    }
1514
1515    /// An attribute argument value: a literal or a name; anything else is
1516    /// reported and left out.
1517    fn attr_value(&mut self, e: &'t Element<K>) -> Option<hir_lang::AttrValue> {
1518        match e {
1519            Element::Token(t) => {
1520                let span = t.span();
1521                match self.m.role_for(t.kind()) {
1522                    Some(TokenRole::Name | TokenRole::Var { .. }) => {
1523                        let (sym, _) = self.token_name(span, TokenRole::Name);
1524                        Some(hir_lang::AttrValue::Name(hir_lang::Ident::new(sym, span)))
1525                    }
1526                    Some(
1527                        role @ (TokenRole::Int
1528                        | TokenRole::Float
1529                        | TokenRole::Number
1530                        | TokenRole::Str(_)
1531                        | TokenRole::RawStr
1532                        | TokenRole::Heredoc(_)
1533                        | TokenRole::Char(_)
1534                        | TokenRole::Bytes(_)
1535                        | TokenRole::True
1536                        | TokenRole::False
1537                        | TokenRole::Null),
1538                    ) => match self.token_lit(role, span, false) {
1539                        token::Decoded::Lit(l) => Some(hir_lang::AttrValue::Lit(l)),
1540                        token::Decoded::Bad => None,
1541                    },
1542                    _ => {
1543                        self.report(ProblemKind::AttributeArgument, span);
1544                        None
1545                    }
1546                }
1547            }
1548            Element::Node(n) => {
1549                let span = n.span();
1550                match self.m.rule_for(n.kind()).copied() {
1551                    Some(Arch::Path { .. } | Arch::Segment { .. }) => {
1552                        let text = self.text_of(span).trim();
1553                        let sym = self.intern(text);
1554                        Some(hir_lang::AttrValue::Name(hir_lang::Ident::new(sym, span)))
1555                    }
1556                    Some(Arch::Pass { .. }) => match self.name_of(e) {
1557                        Some((sym, sp)) => {
1558                            Some(hir_lang::AttrValue::Name(hir_lang::Ident::new(sym, sp)))
1559                        }
1560                        None => {
1561                            self.report(ProblemKind::AttributeArgument, span);
1562                            None
1563                        }
1564                    },
1565                    Some(Arch::Unary { op, operand }) => {
1566                        let mut kids = Vec::new();
1567                        pick::collect_kids(n, self.labeler, self.m, &mut kids, None);
1568                        let op_tok = pick::single(op, &kids, self.m);
1569                        let neg = match op_tok {
1570                            Some(Element::Token(t)) => {
1571                                let text = if self.m.has_op_text() {
1572                                    self.text_of(t.span())
1573                                } else {
1574                                    ""
1575                                };
1576                                matches!(
1577                                    self.m.op(crate::mapping::Fixity::Prefix, t.kind(), text),
1578                                    Some(OpSpec::Op(hir_lang::OpKind::Neg))
1579                                )
1580                            }
1581                            _ => false,
1582                        };
1583                        let num = match pick::single(operand, &kids, self.m) {
1584                            Some(Element::Token(t)) => Some(*t),
1585                            _ => None,
1586                        };
1587                        match (
1588                            neg,
1589                            num.and_then(|t| self.m.role_for(t.kind()).map(|r| (t, r))),
1590                        ) {
1591                            (
1592                                true,
1593                                Some((
1594                                    t,
1595                                    role @ (TokenRole::Int | TokenRole::Float | TokenRole::Number),
1596                                )),
1597                            ) => match self.token_lit(role, t.span(), true) {
1598                                token::Decoded::Lit(l) => Some(hir_lang::AttrValue::Lit(l)),
1599                                token::Decoded::Bad => None,
1600                            },
1601                            _ => {
1602                                self.report(ProblemKind::AttributeArgument, span);
1603                                None
1604                            }
1605                        }
1606                    }
1607                    _ => {
1608                        self.report(ProblemKind::AttributeArgument, span);
1609                        None
1610                    }
1611                }
1612            }
1613        }
1614    }
1615
1616    /// Attaches a frame's attributes to the node its value is.
1617    pub(crate) fn attach_attrs(&mut self, v: &mut Val, attrs: AttrRange, span: Span) {
1618        let (s, l) = (attrs.0 as usize, attrs.1 as usize);
1619        let Some(list) = self.attr_pool.get(s..s.saturating_add(l)) else {
1620            return;
1621        };
1622        let list: Vec<hir_lang::Attr> = list.to_vec();
1623        let node = match *v {
1624            Val::Item(i) => Some(NodeRef::Item(i)),
1625            Val::Expr(e) => Some(NodeRef::Expr(e)),
1626            Val::Stmt(st) => Some(NodeRef::Stmt(st)),
1627            Val::Pat(p) => Some(NodeRef::Pat(p)),
1628            Val::Ty(t) => Some(NodeRef::Ty(t)),
1629            Val::Path(p) => Some(NodeRef::Path(p)),
1630            Val::Field(f, _) => Some(NodeRef::Field(f)),
1631            Val::Variant(var) => Some(NodeRef::Variant(var)),
1632            Val::Arg(a) => Some(NodeRef::Expr(a.value)),
1633            Val::Param(p, sp, _) => {
1634                *v = Val::Param(p, sp, attrs);
1635                return;
1636            }
1637            Val::Spill(ss, sl) => {
1638                let (ss, sl) = (ss as usize, sl as usize);
1639                let nodes: Vec<NodeRef> = self
1640                    .spill
1641                    .get(ss..ss.saturating_add(sl))
1642                    .unwrap_or(&[])
1643                    .iter()
1644                    .filter_map(|slot| match slot.v {
1645                        Val::Item(i) => Some(NodeRef::Item(i)),
1646                        Val::Stmt(st) => Some(NodeRef::Stmt(st)),
1647                        Val::Expr(e) => Some(NodeRef::Expr(e)),
1648                        _ => None,
1649                    })
1650                    .collect();
1651                for n in nodes {
1652                    self.b.attach(n, &list);
1653                }
1654                return;
1655            }
1656            _ => None,
1657        };
1658        match node {
1659            Some(n) => self.b.attach(n, &list),
1660            None => self.report(ProblemKind::MisplacedAttribute, span),
1661        }
1662    }
1663
1664    /// `body`, or `{ hoisted lets; body }` when there are hoisted names.
1665    pub(crate) fn wrap_hoisted(&mut self, hoisted: &[StmtId], body: ExprId, span: Span) -> ExprId {
1666        if hoisted.is_empty() {
1667            return body;
1668        }
1669        self.at(span);
1670        let stmts = self.list(hoisted);
1671        self.ex(Expr::Block(hir_lang::Block {
1672            stmts,
1673            tail: Some(body),
1674            label: None,
1675            is_unsafe: false,
1676        }))
1677    }
1678}
1679
1680/// The span a HIR validation problem is about: its node's origin, or its
1681/// binder's or expansion's.
1682fn hir_span(hir: &Hir, e: &HirError) -> Span {
1683    match e.node() {
1684        Some(n) => hir.origin(n).span,
1685        None => match e {
1686            HirError::BinderBoundTwice { binder, .. }
1687            | HirError::BinderKind { binder, .. }
1688            | HirError::DuplicateBinding { binder, .. } => hir.binder_origin(*binder).span,
1689            HirError::Dangling {
1690                site: Site::Binder(b),
1691                ..
1692            } => hir.binder_origin(*b).span,
1693            HirError::Dangling {
1694                site: Site::Expansion(x),
1695                ..
1696            }
1697            | HirError::ExpansionOrder { expn: x } => {
1698                hir.expansion(*x).map_or(Span::empty(0), |x| x.call_site)
1699            }
1700            _ => hir.origin(NodeRef::Item(hir.root())).span,
1701        },
1702    }
1703}